Skip to content

Erdős Problem #16

Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: disproved (not automatically the live result).
Subject areas: number theory, additive basis, primes.

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

Let \(U\) contain the odd positive integers which cannot be expressed as the sum of a prime and a power of two. Erdős asked whether \(U\) could be decomposed into one infinite arithmetic progression together with a set of natural density zero.

Erdős Problem #16 has been disproved. The crucial distinction is that a set can contain an entire infinite arithmetic progression without being equal to a progression plus a negligible set. These statements say very different things about the rest of the exceptional integers.

A small example

The integer \(9=7+2\) is representable, as are \(11=3+8\) and \(13=11+2\). Including exponent zero also gives \(3=2+1\). But for an odd sum \(p+2^e\) with \(e=0\), the prime must be \(2\); therefore the exponent-zero convention only adds this one small odd represented number. Finite representation checks cannot decide the density or large-scale structure of all exceptions.

Suppose a theorem says that \(U\) is not a union of any finite collection of infinite arithmetic progressions plus a density-zero set. Then it certainly cannot be a union of one progression plus such a set. This logical implication is simple; proving the stronger input theorem is not.

What is known

Yong-Gao Chen, A conjecture of Erdős on \(p+2^k\), arXiv:2312.04120 (2023), proves the stronger negative statement: the set of odd integers not represented in this manner is not a finite union of infinite arithmetic progressions and a density-zero remainder. This resolves Erdős's one-progression conjecture negatively.

Erdős had earlier proved that the exceptional set contains an infinite arithmetic progression. The negative theorem does not contradict that earlier existence result.

GCL's current state

Source audit #1285 compares the published claim with the frozen Formal Conjectures definition. The pinned file contains a theorem annotated with an external Lean proof URL, but its own body is unfilled. GCL has not independently compiled the external formal proof or audited its axioms. The mathematical result is solved in the literature; GCL certification is a different question.

What remains

There is no unresolved mathematical assertion in the original one-progression conjecture. Potential follow-up is proof and formalization verification: check Chen's complete argument, distinguish zero-exponent conventions, and replay any independent Lean version under pinned dependencies and the proper certification rules.

Sources and claim boundaries

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #1285 — 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.

Back to catalogue · Compendium introduction