Erdős Problem #32
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
An additive complement to the primes is a set \(A\) such that every sufficiently large integer can be written \(n=p+a\) with \(p\) prime and \(a\in A\). Erdős Problem #32 asks how sparse such an \(A\) can be. In particular, can the number of its elements up to \(N\) grow more slowly than \((\log N)^2\) while still covering all sufficiently large integers? A separate historical bound asks for something on the scale of \(\log N\).
A statement that almost every integer has a representation is weaker than the eventual every-integer requirement.
A small example
A finite set of shifts can never work. For instance take \(A=\{1,2\}\). The number \(n=11\) is not of the form prime plus one of these two shifts: \(11-1=10\) and \(11-2=9\) are composite. In fact there are arbitrarily large such exceptions.
For any finite list \(A=\{a_1,\ldots,a_k\}\), choose distinct auxiliary primes \(q_1,\ldots,q_k\). The Chinese remainder theorem gives arbitrarily large integers \(n\) satisfying
Taking \(n\) sufficiently large makes every positive difference \(n-a_i\) a proper multiple of \(q_i\), hence composite. So any true additive complement must be infinite. This necessary condition says nothing about the optimal sparseness of infinite complements.
What is known
The maintained record distinguishes the unresolved sparse-complement questions from a separate published density-related result associated with Ruzsa. Their quantifiers must not be exchanged. The existing source audit does not claim to have independently verified the historical primary paper's exact pages, so its reported source outcomes are attributed rather than promoted.
GCL's current state
GCL audit #1301 confirms that the pinned formal predicate uses eventual existence of a prime-plus-shift representation, and derives the finite-complement obstruction above using elementary modular arithmetic. It does not give an example of an infinite complement satisfying the hoped-for sparse bounds or a kernel-checked proof of the conjecture.
What remains
Build an infinite set with the required eventual coverage and exceptionally slow counting growth, or establish a matching obstruction. The Chinese remainder theorem shows why finite sets fail but leaves the logarithmic versus squared-logarithmic scale unresolved.
Sources and claim boundaries
- Erdős Problems #32: maintained formulation and literature context.
- GCL source audit #1301: finite-set obstruction and statement boundaries; no global certification.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1301 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: PROTECTED_READY_BACKLOG.
- 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.