Skip to content

Erdős Problem #10

Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: open (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

Erdős Problem #10 asks whether one fixed bound on the number of powers of two suffices to express every sufficiently large integer as a prime plus those powers. Precisely: are there integers \(K,N_0\) such that

\[ \forall n\ge N_0\quad \exists p\text{ prime},\ t\le K,\ e_1,\ldots,e_t\in\mathbb N: \quad n=p+\sum_{i=1}^{t}2^{e_i}\;? \]

Exactly one prime is used. The number \(t\) can be zero, exponent zero is permitted (\(2^0=1\)), and exponents may repeat. The bound \(K\) concerns the number of summands, not how large an exponent may be. The global existence question remains open in the October 2026 reviewed source record.

A small example

For a given prime \(p\le n\), the minimum number of powers of two adding to \(n-p\) equals the number of ones in its binary expansion, its popcount. Two copies of \(2^e\) can be carried into a single \(2^{e+1}\); repeated carrying reaches the unique binary expansion. Conversely that expansion is already a representation. Therefore

\[ n\text{ is representable with at most }K\text{ powers} \iff \exists p\le n\text{ prime}: \mathrm{popcount}(n-p)\le K. \]

For example,

\[ 50=11+32+4+2+1. \]

A more stringent verified finite test from the GCL #10 audit is

\[ 1{,}117{,}175{,}146 =1{,}117{,}175{,}107+1+2+4+32. \]

The audit reports deterministic verification that the first summand is prime, and a complete check of 462 candidate offsets showing this integer is not representable with three or fewer powers. It therefore needs exactly four under the stated rules. A single finite example does not constrain all sufficiently large integers.

What is known

A density theorem associated with P. X. Gallagher, Primes and powers of 2, Inventiones Mathematicae 29 (1975), 125–142, says that for every \(\varepsilon>0\) some \(K(\varepsilon)\) permits representations for integers of lower density at least \(1-\varepsilon\). The allowed number of powers depends on \(\varepsilon\); even density arbitrarily close to one does not imply that every sufficiently large integer has a representation. This theorem interface is reported in the public registry; an exact original-text proof replay was not undertaken for this article.

Crocker's 1971 covering-congruence techniques give nonrepresentability results for restricted numbers of powers. An external 2026 formal-verification report concerns an infinite family of even integers not representable with at most three powers. Its reported Lean kernel result is for that narrower statement, and its publication review was marked draft: it is not a GCL MATHCERT certificate. Even a fully verified obstruction at three powers does not rule out an eventual fixed bound of four or more.

Related small-bound claims, including parity-sensitive conjectures, remain conjectural, not established universal representations.

GCL's current state

The GCL source audit #1279 checks the pinned Formal Conjectures definition: a finite multiset of powers (including repetitions and exponent zero) plus a prime. The frozen headline uses all integers \(n\ge2\), while later upstream uses all sufficiently large integers. Although worded differently, these two existence of some bound assertions are equivalent.

Indeed, suppose some \(K\) works beyond \(N_0\). Each of the finitely many integers \(2\le n<N_0\) has some representation: use prime \(2\) for even \(n\), prime \(3\) for odd \(n\ge3\), and express the nonnegative remainder in binary. Take the maximum of \(K\) and the finite number of powers required across this prefix. That larger bound represents every \(n\ge2\). This is an elementary normalization, not a proof that such an eventual \(K\) exists.

What remains

A positive result needs one universal \(K\) beyond a threshold. A negative result requires proving that every candidate \(K\) fails for arbitrarily large \(n\). Neither high-density results nor any fixed finite computation establishes either conclusion.

This article reports source-based mathematical exposition and finite checks, not a GCL-certified solution or independent replay of external Lean proofs. Editorial acceptance remains distinct from mathematical certification.

Sources and claim boundaries

Catalogue and evidence provenance

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

Back to catalogue · Compendium introduction