# The sparse ruler constant

A ruler of length $N$ with marks at $0$ and $N$ can measure every whole-number distance up to $N$ using only about $\sqrt{3N}$ marks if they are placed cleverly. How few marks are really needed? Erdős and Gál showed that the minimum, divided by $\sqrt N$, tends to a limit, but its value is unknown: it lies between $1.56$ and $\sqrt3\approx1.732$.

## Problem

Let $F(N)$ be the smallest size of a set $A\subseteq\{0,1,\dots,N\}$ such that every integer $0\le d\le N$ is a difference of two elements of $A$, that is, $\{0,1,\dots,N\}\subseteq A-A$. Such a set is a **sparse** (or complete) ruler of length $N$. Determine

$$
\lim_{N\to\infty}\frac{F(N)}{\sqrt N}.
$$

## Background

Rédei asked whether this limit exists, and Erdős and Gál proved in 1948 that it does. Leech (1956) improved the bounds and showed that the limit equals $\inf_N (F(N)+2)/\sqrt{N+1}$, so every explicit ruler yields a rigorous upper bound. Wichmann (1963) found an infinite family of rulers that gives the upper bound $\sqrt3$. A similar question can be asked for difference bases that are not required to lie inside $[0,N]$.

## What is known

- **Bounds.** The limit lies in $[1.56,\sqrt3]$: the lower bound is due to Leech (1956), the upper bound to Wichmann's construction (1963).
- **Computation.** Computational evidence collected by Pegg (2020) suggests that Wichmann's bound $\sqrt3$ is the truth. By Leech's infimum formula, if the limit equals $\sqrt3$ then $F(N)=\sqrt{3N}+O(1)$.
- **Unrestricted version.** For difference bases that need not lie in $[0,N]$, Bernshteyn and Tait (2019) raised Leech's lower bound by a small amount.

## What would count as progress

- A ruler $A$ of some length $N$ with $(\lvert A\rvert+2)/\sqrt{N+1}<\sqrt3$, which by Leech's formula would beat Wichmann's bound; it is checked by computing $A-A$.
- A lower bound above $1.56$ for the restricted problem, with a complete proof or a certified computation.
- Exact values of $F(N)$ for new ranges of $N$, with certificates of optimality.
- A formal proof against the Lean statement in [formal-conjectures](https://github.com/google-deepmind/formal-conjectures/blob/main/FormalConjectures/ErdosProblems/170.lean).

## References

1. J. Leech, On the representation of $1,2,\dots,n$ by differences, *J. London Math. Soc.* 31 (1956), 160–169. [doi:10.1112/jlms/s1-31.2.160](https://doi.org/10.1112/jlms/s1-31.2.160)
2. B. Wichmann, A note on restricted difference bases, *J. London Math. Soc.* 38 (1963), 465–466. [doi:10.1112/jlms/s1-38.1.465](https://doi.org/10.1112/jlms/s1-38.1.465)
3. A. Bernshteyn and M. Tait, Improved lower bound for difference bases, *J. Number Theory* 205 (2019), 50–58. [doi:10.1016/j.jnt.2019.05.002](https://doi.org/10.1016/j.jnt.2019.05.002)
4. E. Pegg, Hitting all the marks: exploring new bounds for sparse rulers and a Wolfram Language proof, Wolfram Blog (2020). [blog.wolfram.com](https://blog.wolfram.com/2020/02/12/hitting-all-the-marks-exploring-new-bounds-for-sparse-rulers-and-a-wolfram-language-proof/)

## Source

Imported from [Erdős Problems 170](https://www.erdosproblems.com/170), curated by Thomas Bloom. Open according to the source as of 2026-10-20. The statement above is written in our own words; see the source for the original wording, history and discussion.