Skip to content

Erdős Problem #125

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

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 \(A\) consist of nonnegative integers whose base-three expansion uses only digits zero and one, and let \(B\) consist of nonnegative integers whose base-four expansion also uses only zero and one. Form their sumset

\[ C=A+B=\{a+b:a\in A,\ b\in B\}. \]

Erdős #125 asks whether \(C\) has positive lower asymptotic density: does there exist a constant \(c>0\) such that, for all sufficiently large \(X\),

\[ |C\cap[1,X]|\ge cX? \]

This is stronger than requiring positive upper density along a subsequence. If lower density is zero, the original conjecture is false even if the sumset remains sizeable on some scales.

A small example

The first few members of \(A\) are \(0,1,3,4,9,10,12,13,\ldots\); the first few of \(B\) are \(0,1,4,5,16,17,20,21,\ldots\). Therefore \(2=1+1\), \(3=3+0\) and \(5=1+4\) belong to \(C\). However, \(62\) does not belong to \(C\): enumerating the allowed base-three and base-four digit patterns up to \(62\) yields no pair with sum \(62\). Finite omissions or local density measurements do not settle asymptotic lower density.

What is known

DISPROVED in the lower-density interpretation. A DeepMind-associated Lean proof, discussed on Erdős #125 and in the original March–April 2026 discussion, establishes that the lower asymptotic density of \(C\) is zero. The maintained source links the formal proof revision.

The proof explanation iterates a scale-dependent density reduction. Near pairs of powers \(3^k\) and \(4^\ell\), certain gaps constrain the “top digits” of members of \(C\). A map separating top and bottom digits yields, at selected scales, a density at most a fixed fraction (described as 99%) of the density at an earlier scale. Iteration forces the liminf to vanish. This does not, by itself, show the limsup vanishes. Thus the question of positive upper density remains separate.

Earlier Melfi and Hasler–Melfi obtained power-law lower counts, including \(|C\cap[1,X]|\gg X^{0.9777}\), which are fully compatible with zero lower density. In the March 2026 discussion, the proof authors also flag a bibliographic uncertainty about purported Pach–Pintz references. That is a source-fidelity issue; one should not repeat those citations without checking them.

GCL's current state

The pinned and maintained catalogue status is DISPROVED for the positive-lower-density statement. The original issue is #1394. GCL read the protected Formal Conjectures 125 file: it separates positive lower density, positive upper density, and zero density into distinct statements and contains proof holes. The external completed formalization has not been independently built and axiom-audited here.

The original issue contains an authenticated RESULT/1 source report. This is unadjudicated source evidence only, not independent mathematical certification or editorial admission.

What remains

A bounded successor is to enumerate the binary-digit-restricted sets up to \(X=10^5\) and compute \(|C\cap[1,X]|\) exactly at each power-of-three and power-of-four cutoff. Acceptance: independent digit-parser and constructive-set implementations agree, zero belongs to both \(A,B\), and no finite density observation is misrepresented as proving a liminf result. An optional formal audit should replay the external lower-density theorem at its pinned commit and independently verify its dependencies.

Sources and claim boundaries

No theorem about upper density, GCL-certified Lean replay or editorial admission is claimed.

Catalogue and evidence provenance

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