Skip to content

Erdős Problem #246

Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: proved (not automatically the live result).
Subject areas: number theory.

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

Suppose we choose two integers \(a,b\geq 2\) having no common factor greater than \(1\). We are allowed to use the numbers

\[ a^k b^\ell,\qquad k,\ell\in\{0,1,2,\ldots\}. \]

For example, with \(a=3\) and \(b=5\), the permitted numbers begin with \(1,3,5,9,15,25,27,45,75,81,\ldots\). In a sum, each permitted number may be used at most once. Does there exist a threshold \(N(a,b)\) such that every integer greater than that threshold is a sum of these distinct permitted numbers?

Yes. B. J. Birch proved this in 1959. A set with this eventual representation property is called additively complete. It is not required to represent every small number, and it is not enough merely to represent infinitely many large numbers: the assertion covers every integer beyond a fixed, base-dependent threshold.

The assumptions \(a,b\geq2\) matter. The shortened wording “\(\gcd(a,b)=1\)” alone, found in some catalogue descriptions, would wrongly allow \(a=1,b=3\): then only powers of \(3\) are available, and numbers congruent to \(2\) modulo \(3\) cannot be expressed as sums of distinct such powers.

A small example

For \(a=3\) and \(b=5\), the permitted numbers include \(3^0 5^0=1\), \(3\), \(5\), \(9\), \(15\), \(25\), \(27\) and \(45\). Here are four distinct-summand representations:

\[ \begin{aligned} 23 &= 15+5+3,\\ 37 &= 25+9+3,\\ 41 &= 25+15+1,\\ 100 &= 45+25+15+9+5+1. \end{aligned} \]

Birch states \(N(3,5)=22\) on p. 370 of the original paper. We independently checked the finite interval \(1\leq n\leq500\) by enumerating all distinct permitted numbers at most \(500\), and updating the reachable subset sums once for each permitted number. The only unreachable positive integers in that interval are

\[ 2,\quad 7,\quad 11,\quad 22. \]

Thus the explicit computation verifies coverage for \(23\) through \(500\) and matches Birch's reported threshold in that range. A finite computation cannot establish that every integer above \(500\) is representable. The general assertion is supplied by Birch's mathematical proof, not by this experiment.

For reproducibility, the source-audit return provides a small Python subset-sum program and its exact expected result.

What is known

Classically proved. Birch, Note on a problem of Erdős (1959), pp. 370–373, establishes eventual completeness for coprime bases greater than \(1\). The paper begins with the main theorem (p. 370), then develops preliminary lemmas and the progression/gap argument in the subsequent pages. We have inspected the primary paper's statement and proof structure, but have not independently checked every proof step.

Birch records Davenport's observation that the exponent of one base can be bounded independently of the represented integer. The paper explicitly says it omits the details of that strengthening. Later studies obtain quantitative bounds; the maintained catalogue mentions Hegyvári (2000), Fang and Chen (2017), and Yu (2024). Those quantitative refinements have not been independently verified for this article and are not used here to prove the main claim.

Cassels (1960), pp. 111–124, gives a more general theory of complete sets of distinct summands. The maintained catalogue reports that it implies Birch's result. We have verified the bibliographic identity and location, but not replayed the special-case deduction.

Important wording issue. On p. 370, the scan of Birch's theorem appears to say that the exponent pairs are positive integers. Taken literally, that would make all summands divisible by \(ab\) and contradict the claimed representation of arbitrary large integers. The rest of the discussion, including the binary-base observation, requires zero exponents. The pinned FormalConjectures declaration explicitly uses \(k,\ell\in\mathbb N\) and \(a,b\geq2\). This ambiguity is recorded as a source-normalization exception, not silently repaired.

GCL's current state

The original authenticated source audit is ERDOS-CATALOGUE-0246-S01, with disposition SOURCE_LOCK_READY. It identifies the original proof and preserved source hashes, checks the theorem's essential quantifiers, and reproduces a finite subset-sum example.

The pinned formal-provider file is FormalConjectures/ErdosProblems/246.lean at blob 59690c128cbbc77b13f9ba425f0e7d61f96381f3. Its theorem has assumptions \(2\leq a\), \(2\leq b\), and Nat.Coprime a b, with a conclusion expressed using IsAddComplete. The pinned theorem body uses sorry but carries metadata pointing to an external Lean proof. The external proof and its kernel certificate have not been replayed by this audit.

For the frozen GCL catalogue, the informal historical status is proved. The maintained Erdős Problems entry is indexed as PROVED (LEAN); that formal-verification designation is reported from the upstream site, not independently certified by GCL. This manuscript is a documentary unaccepted draft until the protected batch editorial admission and public readback complete.

What remains

The classical problem is not presented here as open. The obligations are documentary and formal-fidelity checks: resolve the original exponent-index wording against the complete paper, expand and compare the formal IsAddComplete definition with the exact set-theoretic claim, pin and replay the linked Lean proof in its actual toolchain, and verify the supplementary Cassels deduction before using it as an independent proof route.

Any claim about optimal bounds, external formal certification or mathematical novelty needs its own primary-source evidence and, where applicable, a separate mathematical certification process. The finite examples above do not settle those additional questions.

Sources and claim boundaries

Claim boundaries: Birch's historically proved theorem is distinguished from finite GCL recomputation, external reports of Lean verification, unreviewed quantitative refinements, and separate protected mathematical authority. None of these editorial records claims an original GCL theorem.

Catalogue and evidence provenance

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