Skip to content

Erdős Problem #424

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

Start with the two positive integers \(2\) and \(3\). Whenever two distinct values \(x\) and \(y\) have already appeared, add the integer \(xy-1\) to the collection. Repeat this process indefinitely, using new entries as well as old ones. Erdős Problem 424 asks whether the resulting set of positive integers contains a positive proportion of the integers, in an appropriate asymptotic sense.

This formulation was suggested by Douglas Hofstadter. It is not a conventional linear recurrence: each generation may contain many new integers, and previously generated values can participate in many different products. The set of all eventual values, not their order of discovery, is the mathematical object under study.

The word density needs particular care. Positive lower density means that a fixed positive fraction of integers up to \(X\) belongs to the set for every sufficiently large \(X\). Positive ordinary natural density additionally requires the density ratio to converge to a limit. These statements are related but not identical. A stronger historical formulation, that almost all integers occur, has a simple counterargument.

A small example

The initial set is \(\{2,3\}\). Combining its two different elements gives \(2\cdot3-1=5\). Combining \(5\) with the earlier entries gives \(2\cdot5-1=9\) and \(3\cdot5-1=14\). Continuing yields \(2\cdot9-1=17\) and \(3\cdot9-1=26\), among many other values. This explains the familiar prefix \(2,3,5,9,14,17,26,\ldots\) associated with OEIS A005244.

There is a rigorous invariant hidden in this simple arithmetic. Both starting values lie in the residue classes \(0\) or \(2\) modulo \(3\). If \(x,y\) are each congruent to \(0\) or \(2\) modulo \(3\), then \(xy-1\) is again congruent to \(0\) or \(2\) modulo \(3\):

\[ 0\cdot0-1\equiv2,\quad 0\cdot2-1\equiv2,\quad 2\cdot2-1\equiv0\pmod3. \]

By induction, no generated integer is congruent to \(1\) modulo \(3\). These excluded integers have natural density \(1/3\). Consequently the eventual generated set has upper density at most \(2/3\); in particular, it cannot contain almost every positive integer. This is a complete elementary argument, not just a finite computational pattern. It does not, however, prove that the generated set has any positive lower density.

What is known

The question appears in Erdős, Problems and results on combinatorial number theory, III (1977), printed p. 71, and Erdős and Graham, Old and New Problems and Results in Combinatorial Number Theory (1980), printed p. 84 of the scanned book. The maintained Erdős Problems #424 page explains that the 1980 “almost all” wording is too strong, using the modulo-3 obstruction attributed to Stefan Steinerberger. It interprets the intended question as one about positive density, likely positive lower density.

The maintained page, last edited on March 31, 2026, labels the question OPEN. There is also newer source material not automatically covered by that status. A public candidate proof claim attributes an argument for positive lower density to Samuel Korsky with AI assistance, accompanied by a separate Lean formalization associated with Boris Alexeev. External reports describe a successful Lean build of that formalization. They do not, by themselves, establish that the formal theorem exactly matches the intended historical problem.

This distinction is mathematically substantive. The external formal development identifies its result as positive lower density, while the older pinned FormalConjectures statement uses a predicate named HasPosDensity. The exact semantics of that predicate, the generated-set definitions and the implications between the two claims require comparison. A machine can correctly verify one proposition without establishing that it is the one the historical author intended. No GCL-independent reproduction of the external 6,394-line build was performed for this article.

GCL's current state

The original source-audit issue #1694 freezes the teorth catalogue at commit 536408716724a2402bdfa7c1d764bf83d64a8c89, data/problems.yaml Git blob 4e60263a80af6207aca494d2e1388e44fa372889. The frozen catalogue records the problem as open, and the maintained page likewise remains open at the last checked source version.

The pinned FormalConjectures 424.lean has Git blob 2d30dd4fcfe7b5af34b055e1b8f25d9a39d8bb9d. It defines a next-generation operation on sets using \(xy-1\) for distinct \(x,y\), takes repeated unions from \(\{2,3\}\), and states a positive-density conjecture. Its theorem body is by sorry, so that pinned snapshot is a statement interface rather than a completed proof. The later external formalization is a separate source and must not be substituted for the pinned one without an explicit provenance review.

The authenticated source audit is original issue #1694, RESULT/1 comment #6157245654. This editorial article preserves the statement conflict and candidate-evidence status; the V2 admissions ledger remains the authority for accepted coverage.

What remains

The next bounded task is a semantic and formal-source comparison, not a fresh unqualified solution announcement. Read the 1977 statement, the corrected maintained formulation, the frozen FormalConjectures predicate definition and the newer Lean theorem signature. Verify whether the newer proof establishes positive lower density, an existing positive natural density limit, or another precise property. Match the initial set and the distinct-element rule throughout. Record exact commits, file hashes and trusted axioms for any claim of formal replay.

A small independent fixture should generate the closure through a few stages by exact multiplication and prove the mod-3 invariant. Its acceptance condition is a complete source-to-statement concordance and an explicit logical implication if one theorem is claimed to answer another. It fails if an external build is treated as proof of source equivalence, or if positive lower density is silently identified with a positive existing density limit. Stop after these bounded checks, leaving mathematical and editorial certification to the appropriate governed process.

Sources and claim boundaries

Historical statement: Erdős (1977), p. 71, and Erdős–Graham (1980), p. 84. Maintained statement and the modulo-3 observation: Erdős Problem #424. Newer candidate evidence: proof-claim reference and external Lean source. Frozen GCL provenance: original issue #1694, catalogue, pinned formal statement, and authenticated RESULT/1.

The residue-class obstruction is proved directly. The later density assertion is treated as an externally reported candidate, not as a GCL-certified proof. Neither protected publication nor V2 editorial admission is asserted.

Catalogue and evidence provenance

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