Erdős Problem #337
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: disproved (not automatically the live result).
Subject areas: number theory, additive combinatorics, additive basis.
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
Take a set \(A\) of natural numbers that is an additive basis: some fixed finite number of elements of \(A\) suffices to make every sufficiently large integer as a sum. Suppose that \(A\) is sparse, in the precise sense that the number of elements of \(A\) up to \(N\) is \(o(N)\). The question asks whether adding \(A\) to itself twice must nevertheless create overwhelmingly many more numbers. In symbols, with \(A+A=\{a+a':a,a'\in A\}\), does
The quantifiers matter. The claim is universal over every sparse additive basis, and the basis order is allowed to be any finite order. It is not a question about a particular sequence or about a finite initial computation. The denominator is the counting function of the original set, while the numerator counts distinct sums, not representations with multiplicity.
The answer recorded by the primary literature is no. This is Erdős Problem 337, whose original issue-specific audit is MATH-PROGRAMME issue #1607. The problem page and the catalogue use the usual asymptotic-basis convention, allowing finitely many initial exceptions.
A small example
Here is a finite exact check of the sumset arithmetic used in the later argument. Let \(X=\{0,1,3\}\). Direct enumeration gives
Thus \(|X|=3\), \(|3X|=9=3|X|\), and \(|2X|=6\leq 3^2|X|=27\). This is a reproducible exact-arithmetic check of the finite-set inequality used in Ruzsa–Turjányi’s proof: if \(|3X|=s|X|\), then their Theorem 3 gives \(|kX|\leq s^k|X|\). A minimal Python verification is:
X = {0, 1, 3}
def ksum(k):
S = {0}
for _ in range(k):
S = {x + y for x in S for y in X}
return S
assert ksum(2) == {0, 1, 2, 3, 4, 6}
assert ksum(3) == {0, 1, 2, 3, 4, 5, 6, 7, 9}
assert len(ksum(3)) == 3 * len(X)
assert len(ksum(2)) <= 3**2 * len(X)
The calculation does not produce a counterexample to Problem 337. A finite set is not an infinite additive basis, and one verified inequality at one scale says nothing about a limit. Its purpose is narrower: it makes the finite sumset interface and the cardinality convention concrete before discussing the asymptotic proof.
What is known
The decisive source is I. Z. Ruzsa and S. Turjányi, “A note on additive bases of integers,” Publ. Math. Debrecen 32 (1985), 101–104, DOI and full-text record. On page 101 the authors state the original Erdős–Graham ratio and explain that Turjányi had already disproved it.
Their Theorem 1 gives, for every integer h at least 3, a basis of order h with sparse counting function and finite lower limit for the (h minus 1)-fold sumset ratio. Taking h equal to 3 refutes the two-fold assertion.
The same paper separates the false statement from a surviving positive result. Its Conjecture 1 proposes the scaled ratio \(A_2(2x)/A(x)\to\infty\), while Theorem 2 proves the three-fold statement \(A_3(3x)/A(x)\to\infty\). The proof uses a finite-set sumset inequality and truncates the basis to \(X=A\cap[1,x]\); because a fixed-order sumset covers all sufficiently large integers, the resulting sumset has at least linear size, while sparsity makes \(A(x)\) sublinear. This is an external published proof, not a GCL certification.
The maintained Erdős Problems entry, accessed 2026-10-12, agrees that the answer is no, credits Turjányi’s counterexample, and records the Ruzsa–Turjányi three-fold theorem and scaled two-fold conjecture. Its bibliography identifies Turjányi’s “A note on basis sequences” (1984) and the Ruzsa–Turjányi paper. The live page also reports one forum comment dated 2025-12-10 about a Lean formalization; comments are evidence to inspect, not peer-reviewed mathematical authority.
GCL's current state
The frozen catalogue source is teorth/erdosproblems at commit 536408716724a2402bdfa7c1d764bf83d64a8c89, specifically data/problems.yaml, Git blob 4e60263a80af6207aca494d2e1388e44fa372889. Entry 337 says informal status “disproved,” formal status “Lean,” and formalized “yes,” all last updated 2025-12-10. This is provenance and status metadata, not a theorem certificate.
The admitted FormalConjectures provider snapshot FC-GDM-85F86371 points to upstream commit 85f863718beeec7b58a3a1926ee92e3472bc2020; that exact tree contains no FormalConjectures/ErdosProblems/337.lean. Therefore no pinned GCL FormalConjectures statement file is available for this problem. The later live upstream file at FormalConjectures commit 817d8a74e6bcd505ac8407388cc12ac3cfda3d0d, blob e6ee852cb2544be4e844d0ac4fb4dae9f63463e9, contains the expected statement and variants, but its theorem bodies are by sorry. An external proof file is linked at the exact plby/lean-proofs revision 68da20b96673899166e94638f5a7fffeb7231d35; it has not been replayed here.
What remains
The useful bounded successor is a source-normalization and interface check, not a new attack on the mathematics. It should compare the published definitions of basis, counting function, and h-fold sumset with the formal definitions, then record separately: the counterexample theorem, the positive three-fold theorem, and the unproved scaled two-fold conjecture. It should verify the indexing shift between natural-number intervals and real-variable counting functions, check the harmless treatment of finitely many exceptions, and identify whether the h-at-least-2 formal variant is inherited from the h-plus-1 counterexample theorem or from another source.
Acceptance should require a line-by-line semantic table and an exact source hash for every formal file used. Falsification is any mismatch in quantifiers, basis order, interval endpoints, or the direction of a limit. The task stops when those interfaces are either reconciled or an explicitly named source ambiguity remains. No Lean build is needed for this bounded audit.
Sources and claim boundaries
The mathematical resolution claimed here comes from the published Ruzsa–Turjányi paper, especially pages 101–104, with Turjányi’s earlier counterexample cited there. The finite computation above is independently reproducible but is not an asymptotic proof. The catalogue and live page establish provenance and reported status; neither establishes GCL mathematical certification. The live formal file and external Lean file are formalization evidence, and the sorry bodies in the pinned-absent/current FormalConjectures record must not be described as checked proofs.
Frozen catalogue evidence and the primary PDF are the source lock for this article; the downloaded primary PDF had SHA-256 ea0e7cf927353078d45384dd752c9c0d5f4b5909b001998e6bd69a383a300555. The original source-audit RESULT/1 citation is authenticated original RESULT/1. Accepted coverage, if any, is decided by the V2 ledger alone; this article supplies neither acceptance, certification, publication authority, nor an award claim.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1607 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: OUTSIDE_STRICT_OPEN_TRIAGE.
- Formal-statement coverage: No statement was confirmed in GCL's pinned formal-provider snapshot. Presence does not mean the statement or proof has been checked.
- External mathematical status: consult current problem page and its dated bibliography.