Skip to content

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:

\[ F(N)=\min\{|A|:\ A\subseteq\{0,\ldots,N\},\ \{0,\ldots,N\}\subseteq A-A\}. \]

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

\[ L=\lim_{N\to\infty}\frac{F(N)}{\sqrt N} \]

was established by Erdős and Gál (1948). The precise constant is still OPEN. The maintained Erdős #170 gives the interval

\[ 1.56\le L\le\sqrt3. \]

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

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.

Back to catalogue · Compendium introduction