Sparse rulers: determine the limit of F(N)/√N for minimal difference bases of {0,...,N} (Erdős #170)
Statement
Let $F(N)$ be the smallest possible size of a set $A\subset\{0,1,\ldots,N\}$ such that $\{0,1,\ldots,N\}\subset A-A$, where $A-A=\{a-a' : a,a'\in A\}$ — equivalently, $A$ is a sparse ruler of length $N$: every distance $0\leq d\leq N$ is realised as a difference of two marks. Find the value of $$\lim_{N\to\infty}\frac{F(N)}{N^{1/2}}.$$
Acceptance. FULLY RESOLVES: a determination of $\lim_{N\to\infty}F(N)/N^{1/2}$ with complete proof — e.g. a proof that the limit equals $\sqrt{3}$ (matching the Wichmann construction), or a proof of any other exact value; machine-checkable (Lean 4, building on the formalised statement) preferred, else a complete written proof. No finite computation can determine the limit. ADVANCES: (a) a proven improvement of either rigorous bound stated in the background — raising the $1.56$ lower bound or lowering the $\sqrt{3}$ upper bound by an explicit amount; (b) a certified extension of the exact values of $F(N)$ (OEIS A046693): new terms beyond the currently recorded ones, each with reproducible exhaustive-search or ILP/SAT code and an optimality certificate (both the ruler achieving $F(N)$ and a proof that no smaller set works); (c) a proven structural theorem about optimal sparse rulers (e.g. constraints on their form) that certifiably reduces the search space, with proof or verified computation. Deliver the proof file, or the search code plus rulers and optimality certificates.
Background
The sparse ruler (perfect difference basis) problem. Rédei asked whether the limit exists, and Erdős and Gál [ErGa48] proved that it does; listed as open on erdosproblems.com/170 (fetched 2026-07-13, status 'open', tagged 'additive combinatorics'). Since the $\binom{|A|}{2}$ positive differences must cover $\{1,\ldots,N\}$, trivial counting gives a limit of at least $\sqrt{2}\approx 1.414$. The limit is known to lie in $[1.56,\sqrt{3}]$: the lower bound $1.56$ is due to Leech [Le56] (who also improved the early bounds), and the upper bound $\sqrt{3}\approx 1.732$ comes from the explicit ruler constructions of Wichmann [Wi63]. Computational evidence by Pegg [Pe20] strongly suggests the Wichmann upper bound is the truth, i.e. that the limit equals $\sqrt{3}$. The exact values of $F(N)$ (equivalently, the sizes of smallest difference bases) are OEIS A046693. The statement is formalised in Lean in google-deepmind/formal-conjectures. Bloom's page notes the variant question where $A$ need not be contained in $\{0,1,\ldots,N\}$ (restricted vs unrestricted difference bases). The attacker's tool: exhaustive/ILP/SAT search with optimality certificates to extend the exact $F(N)$ table and test the $\sqrt{3}$ prediction at larger scales, plus construction theory (Wichmann-type families) and counting arguments for the rigorous bounds.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #170 (T. F. Bloom) | website |
| REF-02 | OEIS A046693 — size of smallest subset S of {0,...,n} such that S-S covers {0,...,n} | website |
| REF-03 | Sparse ruler (Wikipedia) | website |
| REF-04 | Lean formalisation of Erdős #170 (google-deepmind/formal-conjectures) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.