Erdős Problem #31
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
An additive complement to a set \(A\) is another set \(B\) such that the sumset \(A+B\) contains every sufficiently large integer. Erdős Problem #31, proposed by Erdős and Straus, asks whether every infinite set of nonnegative integers \(A\) has such a complement \(B\) of natural density zero.
The answer is yes, proved by G. G. Lorentz in 1954. The complementary set may depend on \(A\), and density zero does not mean finite.
A small example
Let \(A=\{0,2,4,6,\ldots\}\) consist of all even nonnegative integers, and let \(B=\{0,1\}\). Their sumset is every nonnegative integer: an even number comes from adding zero and an odd number from adding one. The finite set \(B\) has density zero.
This illustration is much easier than the general theorem. An arbitrary infinite \(A\) may be extraordinarily sparse, and its complement \(B\) need not be finite.
What is known
Lorentz, On a problem of additive number theory, Proceedings of the American Mathematical Society 5 (1954), 838–841, proved the affirmative statement. The result is an existence theorem about arbitrary infinite sets: it does not say that the same sparse \(B\) works for all \(A\), or that \(A+B\) covers every nonnegative integer without a finite exceptional prefix.
GCL's current state
Source audit #1300 records the universal-then-existential quantifier order and the parity example. It also notes that the maintained problem registry reports an external Lean verification, but GCL has not replayed its dependencies and axioms. Documentary recognition of Lorentz's theorem is distinct from GCL mathematical certification.
What remains
The historical problem is settled. Independent formalization work could establish the precise natural-density and eventual-coverage predicates and replay Lorentz's full argument. No new solution to the original question is claimed here.
Sources and claim boundaries
- Erdős Problems #31: PROVED mathematical status and historical attribution.
- Lorentz (1954), On a problem of additive number theory, Proceedings of the AMS 5, 838–841: published theorem, proof not reproduced here.
- GCL source return #1300: exact semantics and elementary example, not kernel certification.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1300 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: OUTSIDE_STRICT_OPEN_TRIAGE.
- 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.