Erdős Problem #331
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: disproved (not automatically the live result).
Subject areas: number theory, 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
Erdős Problem 331 asks whether two sufficiently large sets of natural numbers must have a repeated nonzero difference. Write
The question assumes that, for some fixed positive constant, both \(A(x)\) and \(B(x)\) are at least a constant multiple of \(x^{1/2}\) for all sufficiently large \(x\). It then asks whether there must be infinitely many solutions of
with \(a_1,a_2\in A\) and \(b_1,b_2\in B\). Equivalently, after rearranging, it asks whether the equation \(a_1+b_2=a_2+b_1\) must have infinitely many nontrivial solutions.
The answer supplied by the primary source is no. The key idea is to reserve alternating binary digit positions for the two sets. The two sets can each have square-root-scale counting functions, while every nonnegative integer has a unique decomposition as one element from each set. Unique decomposition prevents the required nonzero difference from occurring.
A small example
Let \(A\) contain numbers whose binary expansion has nonzero digits only in even positions, and let \(B\) contain numbers whose nonzero digits occur only in odd positions. Restricting attention to numbers below \(32\) gives
and
There are \(8\cdot4=32\) ordered pairs \((a,b)\), and exact integer enumeration gives the set of sums
Each sum occurs once. For example, \(13=5+8\), and no other listed pair produces \(13\). The verification is finite and uses ordinary integer arithmetic; it is a check of the initial segment, not a proof about all natural numbers. The reason the pattern continues is structural: the two summands never use the same binary position, so their addition creates no carry, and the binary expansion of the sum recovers both summands uniquely.
The inclusion of \(0\) in this illustration follows the primary paper's normalization. Removing \(0\), or shifting the sets to positive integers, changes only finitely many values and does not change the asymptotic lower bounds or the nonzero-difference conclusion.
What is known
The direct primary evidence is P. Erdős and Robert Freud, “On disjoint sets of differences,” Journal of Number Theory 18 (1984), 99–109. Its introduction quotes the original Erdős–Graham formulation from [ErGr80, p. 50] and then gives the binary construction. On the paper's printed pp. 100–101, it explains that the binary representations using even powers of two for \(A\) and odd powers for \(B\) have only trivial solutions to the difference equation. It also records the quantitative fact
so the example meets the square-root growth requirement with room to spare. The paper therefore resolves the original question negatively, rather than merely giving a computation or heuristic.
The maintained Erdős Problems entry reports the same construction, labels the problem “DISPROVED (LEAN),” and records a stronger-looking variant suggested by Ruzsa: replace lower bounds of square-root order by asymptotic relations \(A(x)\sim c_Ax^{1/2}\) and \(B(x)\sim c_Bx^{1/2}\) with positive constants. The original counterexample does not automatically settle that variant, and this article does not call the variant solved.
GCL's current state
The source-audit issue is MATH-PROGRAMME issue #1601, assignment ERDOS-CATALOGUE-0331-S01. Its protected catalogue packet classifies #331 as disproved, with triage class OUTSIDE_STRICT_OPEN_TRIAGE. No issue comment or existing RESULT/1 was present at audit time; the original SOURCE RESULT/1 citation is therefore https://github.com/grandchallenge/MATH-PROGRAMME/issues/1601#issuecomment-6138453689.
The frozen catalogue file is teorth/erdosproblems at commit 536408716724a2402bdfa7c1d764bf83d64a8c89, entry 331, Git blob 4e60263a80af6207aca494d2e1388e44fa372889. Its recorded informal status is disproved, last updated 2026-01-31; its formal status is Lean.
The pinned FormalConjectures declaration is at commit 85f863718beeec7b58a3a1926ee92e3472bc2020, blob 5d7208f87c0a3f33f6af72118153cd438397becd. It quantifies over sets \(A,B\subseteq\mathbb N\), expresses the lower bounds as square-root \(=O\) counting conditions, and encodes infinitely many quadruples satisfying the difference equation. The theorem is declared with answer(False), but its body is by sorry; the file is a formal statement and metadata record, not a replayed proof or GCL certification. Its variant theorem is explicitly still open.
What remains
The original lower-bound question has a primary counterexample. What remains is careful interface work: check the imported counting convention against the source's interval convention, document the harmless treatment of zero, and compare every formal quantifier with the printed statement. The Ruzsa asymptotic variant remains a separate mathematical question in the pinned formal file and on the maintained page.
A bounded successor could formalize the finite binary lemma: for a fixed digit length, prove by exact induction that alternating-position digit sets map bijectively to the corresponding initial interval under addition, then derive the finite counting formulas. Acceptance would require a checked theorem whose hypotheses and indexing are recorded; failure would be any collision, missing sum, or mismatch with the source normalization. This would improve reuse without pretending to settle the asymptotic variant.
Sources and claim boundaries
- Original issue #1601: assignment, source packet, and status evidence. The original SOURCE RESULT/1 citation is https://github.com/grandchallenge/MATH-PROGRAMME/issues/1601#issuecomment-6138453689.
- Erdős and Freud (1984), publisher scan, pp. 99–101, DOI 10.1016/0022-314X(84)90046-5: primary statement quotation and binary counterexample. The fetched PDF SHA-256 was
1d08335e65da7cf40d1c4a7ba0088e0f39b9c5a4b2e42de95fc9ffa69fb96c7a. - Maintained problem page: live wording, variant, and page date 08 February 2026; it identifies ErGr80, p. 50 as the original reference.
- Frozen catalogue entry and pinned formal file: exact commits and blobs are recorded above; neither alone certifies the mathematics.
The finite calculation is independently reproducible exact arithmetic. The published counterexample is attributed to its authors and source pages. V2 ledger state, not this explanatory article, decides accepted coverage; no editorial text here supplies mathematical certification.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1601 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: OUTSIDE_STRICT_OPEN_TRIAGE.
- 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.