Erdős Problem #29
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: proved (not automatically the live result).
Subject areas: number theory, 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
Can one construct an additive basis of order two explicitly, while ensuring that no integer has very many representations? Erdős Problem #29 asks for a single computably described set \(A\) of nonnegative integers with
where \(r_A(n)\) counts ordered pairs from \(A\) summing to \(n\). The problem is solved.
This differs from Problem #28: subpolynomial growth still permits representation counts that increase without bound. It also differs from proving existence by a random construction.
A small example
Because \(0\in A+A\), any such set must contain 0. Then, to represent 1, it must contain 1 as well. The finite example \(A=\{0,1,2\}\) represents every integer from 0 through 4, with ordered counts \(1,2,3,2,1\).
That finite success gives no assurance of representing 5 or any larger integer. An actual explicit infinite basis needs a coherent membership rule and a proof covering all nonnegative targets.
What is known
Jain, Pham, Sawhney and Zakharov, An explicit economical additive basis (2024), give an explicit construction answering Erdős's question affirmatively. Earlier probabilistic work by Erdős established the existence of economical bases, but an explicit construction was a separate outstanding challenge.
The published construction establishes small representation counts in the subpolynomial sense required by the problem; it does not prove representations can be bounded by one fixed constant, which would be relevant to the open Problem #28.
GCL's current state
Source audit #1298 compares the explicit and probabilistic claims, checks the zero-element boundary and proposes a pinned finite-prefix replay of the published construction. The complete source proof and any externally reported formalization have not been kernel-replayed under GCL controls.
What remains
Nothing remains to resolve the historical explicit-construction question. A useful separate task is to implement the authors' actual membership algorithm with deterministic witness tests and a reproducible formal proof of its asymptotic bound.
Sources and claim boundaries
- Erdős Problems #29: PROVED statement and historical context.
- Jain–Pham–Sawhney–Zakharov, author paper: explicit construction, not independently re-proved in this article.
- GCL source return #1298: source and finite boundary checks, not mathematical certification.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1298 — 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.