Erdős Problem #28
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: open (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
A set \(A\) of positive integers is an additive basis of order two when every sufficiently large integer can be expressed as \(a+b\) with \(a,b\in A\). Let \(r_A(n)\) count the ordered pairs \((a,b)\) that represent \(n\), so that \(a+b\) and \(b+a\) are counted separately when \(a\ne b\).
Erdős Problem #28, the Erdős–Turán conjecture, asks whether the numbers \(r_A(n)\) must be unbounded for every such additive basis. It remains open.
A small example
With \(A=\{1,2,4\}\), the ordered representation counts at sums 2, 3, 4, 5, 6 and 8 are respectively
The total is nine, the number of ordered pairs from the three-element set. More generally, for \(F=A\cap[1,N]\) with \(k\) elements,
Consequently some sum has at least \(\lceil k^2/(2N-1)\rceil\) representations. This finite average bound can be only a constant when \(k\) is around \(\sqrt N\), so it does not settle the conjecture.
What is known
Erdős constructed additive bases with representation counts growing no faster than a constant multiple of \(\log n\), showing that representations can remain very sparse. Whether their counts can be uniformly bounded is the outstanding issue. An explicit sparse construction satisfying a related subpolynomial upper bound is a different, now-solved Erdős Problem #29.
Even finding a basis for which every integer has at most 100 representations would disprove #28, but no such global construction has been established in the reviewed record.
GCL's current state
Source audit #1297 fixes the ordered-count convention, records the finite double-counting identity and the eventual-coverage predicate, and separates the related #40 conditional formal statement. The audit neither constructs a bounded-representation additive basis nor proves that no such basis exists.
What remains
Prove that every order-two additive basis has arbitrarily large representation counts, or exhibit one with a fixed finite upper bound for every sum. Finite convolution identities, positive representation counts and average-case estimates do not supply the required global extremal conclusion.
Sources and claim boundaries
- Erdős Problems #28: OPEN mathematical statement.
- Erdős Problems exposition on additive bases: historical construction context, not a replacement for original proofs.
- GCL source return #1297: finite identity and precise quantifiers, no proof certification.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1297 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: DEFER_UNTIL_NEW_MECHANISM.
- 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.