Sufficient conditions for the infinitely-recurring difference set $D(A)$ to have bounded gaps (Erdős #332)
Statement
Let $A\subseteq\mathbb{N}$. Define $D(A)$ to be the set of all positive integers $d$ that occur infinitely often as a difference $a_1-a_2$ with $a_1,a_2\in A$ (that is, $d$ for which $a_1-a_2=d$ has infinitely many solutions in $A$). Find natural conditions on $A$ sufficient to guarantee that $D(A)$ has bounded gaps, i.e. that there is a constant $C=C(A)$ such that every interval of length $C$ contains an element of $D(A)$ (equivalently, consecutive elements of $D(A)$ differ by at most $C$). One may also seek conditions ensuring the weaker conclusions that $D(A)$ has positive density, that $\sum_{d\in D(A)}\frac1d=\infty$, or merely that $D(A)\neq\emptyset$.
Acceptance. FULLY RESOLVES: a complete proof characterizing the conditions on $A$ that force $D(A)$ to have bounded gaps (a sharp sufficient condition together with a matching necessity example) — machine-checkable in Lean/Coq preferred, otherwise a full written proof with all steps. ADVANCES (each independently checkable): (a) prove a sufficient condition strictly weaker than positive density — an explicit density-zero or structural hypothesis $H$, with a proof that $H$ implies $D(A)$ has bounded gaps and an example set satisfying $H$ but not having positive density; or (b) under a stated hypothesis weaker than positive density, prove one of the weaker conclusions (positive density of $D(A)$, $\sum_{d\in D(A)}1/d=\infty$, or $D(A)\neq\emptyset$); or (c) construct a counterexample delimiting what is impossible. Any claimed sufficient condition must be strictly weaker than the positive-density hypothesis stated in the background. Deliver a proof file (Lean preferred) or a complete written proof.
Background
Posed by Erdős and Graham [ErGr80, p.50] and listed as open on erdosproblems.com/332 (fetched 2026-07-13, status 'open', tagged 'number theory'). The one hypothesis known to suffice is positive density: if $A$ has positive upper density then $D(A)$ has bounded gaps, a result obtained by Prikry, Tijdeman, and Stewart and surveyed by Stewart [St78] and Tijdeman [Ti79]. The question is how far this can be relaxed — whether a suitable density-zero or structural condition already forces bounded gaps in $D(A)$, and likewise which weaker hypotheses guarantee only positive density of $D(A)$, a divergent reciprocal sum $\sum_{d\in D(A)}1/d=\infty$, or mere nonemptiness of $D(A)$. No precise (necessary-and-sufficient) characterization is known even for the weakest conclusion. Erdős attached no prize. A machine-checkable Lean statement of the problem is maintained in DeepMind's formal-conjectures project. The attacker's tool: additive-combinatorial and Fourier-analytic recurrence arguments applied to carefully engineered density-zero families, together with a Lean/formal proof to certify any new sufficient condition.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #332 (T. F. Bloom) | website |
| REF-02 | Lean 4 formalisation of Erdős #332 (DeepMind formal-conjectures) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.