Erdős Problem #332
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: open (not automatically the live result).
Subject areas: number theory.
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
Erdős Problem 332 asks how much regularity a set of recurring differences must have. Start with a set \(A\) of natural numbers. A number \(d\) is a recurring difference when there are infinitely many pairs of elements of \(A\) whose difference is \(d\). The question is: what assumptions on \(A\) guarantee that these recurring differences do not leave arbitrarily long gaps?
For comparison with the original literature, use nonnegative differences:
Here “bounded gaps” means that some fixed \(M\) works so that every interval of \(M\) consecutive nonnegative integers contains an element of \(D_\infty(A)\). This is the usual syndeticity condition. The live page phrases the problem with \(A\subseteq\mathbb N\) and \(a_1-a_2\), without spelling out whether negative differences are included. Erdős and Graham’s cited source, and Stewart and Tijdeman’s primary paper, use nonnegative differences and include \(0\).
The distinction matters for formalization. The pinned Lean file instead defines \(D_A(A)\) as a subset of \(\mathbb Z\), allowing both signs, and states bounded gaps on all of \(\mathbb Z\). That is a reasonable symmetric variant, but it is not automatically identical to the original nonnegative formulation.
A small example
Take the even numbers, \(A=2\mathbb N_0\). Every even \(d\) occurs infinitely often: for each \(n\geq 0\), the pair \(2(n+d/2)\) and \(2n\) has difference \(d\). No odd number is a difference of two even numbers. Thus
which has gaps of at most \(2\).
There is also a finite exact check behind this example. For \(A_N=\{0,2,4,\ldots,2(N-1)\}\), direct integer enumeration gives
For \(N=5\), the multiplicities for differences \(0,2,4,6,8\) are respectively \(5,4,3,2,1\). This is reproducible by counting the pairs \((2i,2j)\) with \(i-j=d\); there are exactly \(N-d\) choices of \(j\). The finite calculation checks the pattern and illustrates recurring differences, but it does not prove infinitude for an arbitrary set, a density theorem, or the Erdős question itself.
What is known
The original catalogue entry points to P. Erdős and R. L. Graham, Old and New Problems and Results in Combinatorial Number Theory (1980), p. 50. The maintained page reports that Prikry, Tijdeman, Stewart, and others showed positive density is sufficient, and it points to C. L. Stewart’s 1978 survey and R. Tijdeman’s 1979 survey. It also asks related questions about positive density of \(D_\infty(A)\), divergence of \(\sum_{d\in D_\infty(A)}1/d\), and mere nonemptiness.
A directly inspectable primary source is C. L. Stewart and R. Tijdeman, “On Infinite-Difference Sets,” Canadian Journal of Mathematics 31 (1979), 897–910, DOI 10.4153/CJM-1979-085-6. On p. 897 they define the infinite-difference set for an infinite increasing sequence of nonnegative integers. On p. 898, Theorem 2 says that if the sequence has positive upper asymptotic density, finitely many translates of its infinite-difference set cover \(\mathbb N_0\). The paper then explains that such a finite covering prevents arbitrarily long gaps. Its Corollary 1, proved on p. 902, gives the further density inequality \(\underline d(D_\infty(A))\geq\overline d(A)\) in the relevant notation.
This is a verified sufficient condition, not a complete characterization. The primary paper also shows that the resulting difference sets can have more complicated density behavior, so “positive density of \(A\)” should not be silently upgraded to a precise best-possible description of all sets with bounded-gap difference sets. The maintained page currently displays the problem as open, with one unverified discussion comment, zero proof claims, and no proof exposition. The comment sketches a possible strengthening from positive asymptotic density to positive upper Banach density; it is explicitly user-generated and has not been treated here as established evidence.
GCL's current state
The source packet is bound to original issue #1602, assignment ERDOS-CATALOGUE-0332-S01. The frozen catalogue is teorth/erdosproblems at commit 536408716724a2402bdfa7c1d764bf83d64a8c89, with data/problems.yaml blob 4e60263a80af6207aca494d2e1388e44fa372889. At that snapshot, Problem 332 is open, its solution is unformalized, and its statement is marked formalized.
The protected formal provider is google-deepmind/formal-conjectures at commit 85f863718beeec7b58a3a1926ee92e3472bc2020, file FormalConjectures/ErdosProblems/332.lean, blob cd66b30a7d502f16968e2a8ef99473d8ec541e7a. It defines the signed-integer version described above and uses answer(sorry) for the unknown sufficient condition, followed by by sorry. This is formal statement infrastructure, not a Lean proof or a certified semantic match.
The local GCL triage record classifies the item as PROTECTED_READY_BACKLOG, with manual statement-level triage required; it does not authorize a Solve campaign or certification. No GCL mathematical certification is supplied here. V2 ledger evidence alone decides accepted compendium coverage; an article, source audit, or formal declaration cannot substitute for that ledger.
What remains
The next useful bounded task is statement-level reconciliation. First decide whether the canonical object is \(D_\infty(A)\subseteq\mathbb N_0\) or the signed set in the Lean file. Then compare the exact density hypothesis in Stewart–Tijdeman with the live wording “positive density,” recording whether this means positive upper asymptotic density, an existing natural density, or upper Banach density. Only after that should a formal statement be edited or a research task selected.
A bounded research successor could formalize or independently reprove the finite-translate consequence under one explicitly chosen density definition. Its acceptance test should check every quantifier, the ambient number system, and the implication from finite translates to a numerical gap bound. A failure would be a counterexample to the proposed normalization or a documented mismatch with the primary theorem, not evidence against the original open question.
The upper-Banach-density comment deserves separate checking because it is stronger than the frozen packet and is not a primary source. The finite example above is useful for regression tests, but it cannot settle this issue. The open problem also asks about weaker conclusions and broader hypotheses; Stewart–Tijdeman’s positive-density theorem does not answer all of those variants.
Sources and claim boundaries
The documentary anchor is Erdős Problem 332, read with its displayed revision date of 28 October 2025 and its current discussion counters. The original problem citation is the Erdős–Graham book entry [ErGr80,p.50]; the maintained bibliography identifies it as P. Erdős and R. L. Graham (1980), Old and New Problems and Results in Combinatorial Number Theory. The related survey records are C. L. Stewart (1978), “On difference sets of sets of integers,” and R. Tijdeman (1979), “Distance sets of sequences of integers.” The primary theorem used here is Stewart–Tijdeman (1979), pages 897–898 and 902; the downloaded PDF was checked with SHA-256 a6787d60c102f0a312ca1034790e94aa4227faab3705951db6f80f5af2f05ee.
The original GCL SOURCE RESULT/1 citation is https://github.com/grandchallenge/MATH-PROGRAMME/issues/1602#issuecomment-6138457208. No future issue-comment URL is invented. The frozen commit and blob identifiers above are source locks, not proof certificates. The live page’s status and forum material are current documentary evidence, while its user comment is unverified. The Lean file’s sorry is an explicit unresolved proof boundary. None of these materials independently certifies the mathematics, changes the V2 coverage decision, or establishes a complete characterization.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1602 — 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.