Erdős Problem #170
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: open (not automatically the live result).
Subject areas: additive combinatorics.
Read this status correctly
The status above is reproduced from GCL's immutable external-catalogue snapshot. It is not a new claim of current mathematical resolution, a source-semantic review, an independent proof check, or GCL certification. A published proof and a GCL replay are separate events.
The question in plain language
A sparse ruler is a set \(A\subseteq\{0,\ldots,N\}\) of marks such that every distance \(0,1,\ldots,N\) occurs as a difference of two marks. Write \(F(N)\) for the smallest number of marks:
Erdős and Gál asked about the normalized minimum \(F(N)/\sqrt N\). The limit is known to exist; Erdős #170 asks for its exact value.
A small example
Take \(N=5\) and \(A=\{0,1,3,5\}\). The positive differences are \(1,2,3,4,5\): for example, \(5-1=4\) and \(3-1=2\). Thus \(F(5)\le4\). Counting the \(\binom{|A|}{2}\) unordered pairs gives the general bound \(\binom{|A|}{2}\ge N\), and hence \(F(N)\ge(1+\sqrt{1+8N})/2\).
This elementary lower bound yields limiting constant at least \(\sqrt2\), weaker than the best known constant. A ruler with repeated distances is permitted: every required distance need occur at least once, not exactly once.
What is known
The existence of
was established by Erdős and Gál (1948). The precise constant is still OPEN. The maintained Erdős #170 gives the interval
Leech (1956) supplied the lower bound; Wichmann (1963) supplied the upper. Computational work by Pegg (2020) suggests that the upper value \(\sqrt3\) may be exact, but computations on a finite collection of rulers do not prove an asymptotic extremal constant.
The related problem where the marks are not required to lie in \(\{0,\ldots,N\}\) is different and should not be substituted for the protected statement.
GCL's current state
Pinned and maintained status: OPEN for the numerical evaluation, while limit existence is proved. Original issue: #1439. A statement is present in the frozen Formal Conjectures provider; no proof is implied by that presence. The Leech and Wichmann historical full constructions were not independently replayed.
The original issue contains an authenticated RESULT/1 source report. This is unadjudicated source evidence only, not independent mathematical certification or editorial admission.
What remains
A bounded successor enumerates minimum rulers through \(N=12\) by exact bitmask difference coverage, checks the witness for \(N=5\), and derives the pair-count lower bound. Acceptance: an exact independent difference-set checker and witnesses for each optimum. Stop without extrapolating numerical ratios to \(L\) or claiming to improve the \(1.56\) and \(\sqrt3\) bounds.
Sources and claim boundaries
- Erdős #170, sources [ErGa48], [Le56], [Wi63] and [Pe20].
- Original GCL issue #1439.
No new sparse-ruler construction, exact limit determination or editorial admission is claimed.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1439 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: PROTECTED_READY_BACKLOG.
- Formal-statement coverage: A provider statement was included in the pinned snapshot. Presence does not mean the statement or proof has been checked.
- External mathematical status: consult current problem page and its dated bibliography.