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.

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
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
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
4. E. Pegg, Hitting all the marks: exploring new bounds for sparse rulers and a Wolfram Language proof, Wolfram Blog (2020). blog.wolfram.com

Source

Imported from Erdős Problems 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.