Skip to content

Erdős Problem #429

Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: disproved (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 an infinite set \(A\) of positive integers so sparse that its elements are far apart. Could there be one integer shift \(n\) that makes every number \(n+a\), with \(a\in A\), prime? Erdős Problem 429 asks whether this should be possible whenever the set is sufficiently sparse and there is no obvious modular obstruction.

The modular condition is called admissibility. For every prime \(p\), the set \(A\) must miss at least one residue class modulo \(p\). If \(A\) occupied all residue classes modulo some prime \(p\), then every shift \(n\) would place at least one member of \(n+A\) in residue class zero modulo \(p\). For a large enough element, that number would be composite. Thus missing a residue class for every prime is an obvious necessary condition for translating an infinite set wholly into the primes.

The subtle point is whether this necessary condition is sufficient when the set is very sparse. The question is different from the prime-tuple conjecture of order \(k\), which concerns finite admissible patterns. A result about each finite prefix separately does not provide a single shift that works for every element of an infinite set.

A small example

Consider the finite set \(A=\{2,4\}\). It is admissible. Modulo \(2\), both elements are congruent to zero, so residue class \(1\) is missing. For any odd prime \(p\), the two members occupy at most two residue classes, fewer than the \(p\geq3\) available classes, so at least one class is missing. Moreover, the shift \(n=1\) makes

\[ n+A=\{3,5\}, \]

and both numbers are prime.

This example shows that the modular condition is compatible with a finite prime translate; it does not prove the desired property for every admissible set. It also does not say anything about the existence of a single prime translate for an infinite set. Even if every finite prefix had some suitable shift, those shifts could vary with the size of the prefix and need not agree.

The modular necessity argument is fully rigorous for infinite sets: if an infinite \(A\) covers all residue classes modulo \(p\), then for every shift \(n\) there is an entire infinite subsequence to consider only if an infinite congruence class is populated; the simple finite covering argument alone needs care because a single number divisible by \(p\) might equal \(p\) itself. For sufficiently large fixed finite subsets that repeat the residue obstructions, one can force composites; the historical admissibility condition is the standard necessary local test for prime-rich patterns. The negative solution constructs a much stronger obstruction that survives despite this local admissibility.

What is known

The question appears in P. Erdős, A survey of problems in combinatorial number theory, Annals of Discrete Mathematics (1980), printed p. 111, and in Erdős and Graham, Old and New Problems and Results in Combinatorial Number Theory (1980), printed p. 85 of the scanned book.

Desmond Weisenberg settled the conjecture negatively in Sparse Admissible Sets and a Problem of Erdős and Graham, published in INTEGERS 24 (2024), Article A89. His paper shows that there are arbitrarily sparse infinite admissible sets \(A\) for which there exists no integer \(n\) making every element of \(n+A\) prime. The constructions are explicit in a mathematical sense and use properties of powers of primitive roots; the paper provides four approaches. The result demonstrates that even severe sparseness together with the absence of local residue-class obstructions is not sufficient.

The maintained Erdős Problems #429 page, last edited on April 8, 2026, labels the answer DISPROVED (LEAN) and attributes the negative result to Weisenberg. A related question replaces primes with squarefree integers and asks whether a set omitting some residue class modulo every \(p^2\) admits infinitely many shifts whose translates are all squarefree. The maintained source also reports a negative answer through a variant of Weisenberg's construction. The squarefree variant has different local conditions and cannot be silently merged into the original prime question.

The negative result does not contradict the prime-tuple conjecture of order \(k\). That conjecture concerns any specified finite admissible set; each finite subset of the constructed infinite \(A\) can be treated as a different finite pattern. It does not promise that one shift succeeds for all infinitely many members simultaneously.

GCL's current state

The original source issue #1699 pins teorth/erdosproblems at commit 536408716724a2402bdfa7c1d764bf83d64a8c89, file data/problems.yaml and Git blob 4e60263a80af6207aca494d2e1388e44fa372889. Its frozen status says disproved, consistent with the maintained mathematical page and the published 2024 paper.

The protected source issue explicitly records that no 429.lean statement file exists in the admitted FormalConjectures revision 85f863718beeec7b58a3a1926ee92e3472bc2020. A later upstream 429.lean now links an external formalization and includes an answer(False) statement, but its proof body is a placeholder in the current displayed file. This newer file has a different provenance and cannot be described as part of the pinned provider or as an independently replayed GCL proof.

The authenticated source record is original issue #1699, RESULT/1 comment #6157408525. Documentary source custody is separate from GCL mathematical certification and the protected V2 editorial admissions ledger.

What remains

The primary mathematical problem has a published negative answer. A bounded next task is therefore to reconstruct a precise source-to-statement comparison, rather than to propose a new unqualified solution. Read Weisenberg's original theorems and identify exactly how the constructed set can meet an arbitrarily prescribed sparseness threshold while omitting at least one residue class for every prime, and why no integer shift makes all its members prime.

A useful exact finite fixture should enumerate residues of a few chosen admissible sets modulo small primes, and distinguish finite admissibility checks from the infinite statement, which quantifies over every prime. Separately compare Weisenberg's squarefree construction, whose modulus is \(p^2\) rather than \(p\). The task succeeds when all quantifiers and constructions align with the original source, and fails if a finite modular check is treated as proof of infinite admissibility or if the later unpinned Lean file is silently substituted for the frozen source. Stop after this documentary audit and finite checksum; mathematical or formal certification would need its own separately validated evidence.

Sources and claim boundaries

Primary historical sources: Erdős (1980), printed p. 111, and Erdős–Graham (1980), p. 85. Resolving publication: Weisenberg (2024), arXiv:2405.12310, and the INTEGERS 24 Article A89 record. Maintained status: Erdős Problem #429. GCL provenance: original issue #1699, frozen catalogue and authenticated source return.

The finite admissible example is directly checkable. The counterexample theorem is attributed to Weisenberg's published paper, not newly proved by GCL. External Lean status is not represented as independently verified, and no protected editorial admission is claimed.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #1699 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
  • GCL triage: OUTSIDE_STRICT_OPEN_TRIAGE.
  • Formal-statement coverage: No statement was confirmed in GCL's pinned formal-provider 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