Skip to content

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

\[ 1,\ 2,\ 1,\ 2,\ 2,\ 1. \]

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,

\[ \sum_{t=2}^{2N}r_F(t)=k^2. \]

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

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.

Back to catalogue · Compendium introduction