Skip to content

Erdős Problem #279

Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: open (not automatically the live result).
Subject areas: number theory, covering systems, 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.

Editorial authority: The protected GCL V2 admissions ledger alone determines publication status. This source-bounded explanation is not mathematical certification.

The question in plain language

Give each prime number \(p\) one residue class: choose an integer \(r_p\) with \(0\le r_p<p\), and then consider all numbers congruent to \(r_p\) modulo \(p\). Every member of that class can be written as \(r_p+tp\). The question asks whether the classes can be chosen so that, for every integer \(k\ge 3\), every sufficiently large integer \(n\) has at least one representation with \(t\ge k\).

In symbols, the proposed choice must satisfy

\[ \forall k\ge 3\;\exists (r_p)_{p\ \mathrm{prime}}\;\exists N\;\forall n\ge N\;\exists p,t: \]
\[ p\ \mathrm{prime},\qquad 0\le r_p<p,\qquad t\ge k,\qquad n=r_p+tp. \]

The threshold \(N\) may depend on \(k\), and the residue assignment may also depend on \(k\). What cannot vary with \(n\) is the assignment once \(k\) has been fixed: each prime gets one permanent class. The inequality \(t\ge k\) is important. It says that the representation must occur at least \(k\) steps along the progression, so necessarily \(n\ge kp\). This is stronger than merely asking whether every large integer belongs to one of the chosen residue classes.

The intended answer is currently unknown. “All sufficiently large” means all integers beyond one fixed threshold, not merely a large proportion, not infinitely many integers, and not a different threshold chosen separately for each finite experiment.

A small example

Here is a finite check that makes the quantifiers concrete. Take \(k=3\), use the primes at most \(31\), and try the simple assignment \(r_p=p-1\). For this assignment, a number \(n\) is covered by \(p\) exactly when

\[ n\equiv p-1\pmod p\qquad\text{and}\qquad 3p\le n. \]

For \(n=59\), the witnesses include

\[ 59=1+29\cdot2=2+19\cdot3=4+11\cdot5. \]

Thus \(p=2,3,5\) all work, with \(t=29,19,11\) respectively. For \(n=60\), an eligible prime would have to satisfy \(p\le 60/3=20\) and divide \(61\), because \(60\equiv-1\pmod p\). No such prime exists, so \(60\) is not covered by this assignment.

An independent enumeration of \(30\le n\le100\) found \(55\) covered values and these \(16\) uncovered values:

\[ 30,36,40,42,46,52,58,60,66,70,72,78,82,88,96,100. \]

This is a valid finite certificate against this particular assignment on this particular interval. It is not evidence that every possible assignment fails, and it is not evidence that the Erdős question is false. Conversely, a finite assignment that covers a long interval would not establish eventual coverage. The distinction between a finite window and one assignment covering the entire tail is the central logical hazard in this problem.

What is known

The original source is Erdős and Graham’s Old and New Problems and Results in Combinatorial Number Theory, Monographies de l’Enseignement Mathématique 28 (Geneva, 1980), printed p. 29. In the paragraph that introduces this problem, they explain that if a sequence of moduli satisfies \(\sum_i1/n_i=\infty\), then almost all integers can be represented as \(a_i+tn_i\) with \(t\ge2\). They immediately distinguish this density-one statement from coverage of all sufficiently large integers. They then ask whether, for some fixed \(k\), all but finitely many integers can be represented with \(t\ge k\), and note that the prime-modulus case already seems difficult for \(k=3\).

That passage supplies the historical formulation and a useful comparison, not a solution. “Almost all” permits an exceptional set of density zero; problem #279 asks for no exceptions after a finite point. Those are very different conclusions.

There is related sieve technology, but it does not close this question. For example, Ford, Green, Konyagin, and Tao prove in Theorem 1 on p. 936 of their 2016 Annals of Mathematics paper that long intervals of consecutive composite numbers exist, using a random construction of residue classes to cover a suitable finite set of primes. Their construction is designed for finite prime-gap intervals. It does not provide one fixed residue class for every prime that covers every sufficiently large integer with the lower-bound condition \(t\ge k\).

The authenticated source return identifies the strongest safe finite interface as follows. For fixed \(k,N,M\), let \(F(k,N,M)\) say that residues can be chosen for the primes \(p\le M/k\) so that every \(N\le n\le M\) has a witness:

\[ F(k,N,M):\quad\exists(r_p)_{p\le M/k}\;\forall N\le n\le M\;\exists p\le n/k: \]
\[ p\ \mathrm{prime},\qquad n\equiv r_p\pmod p,\qquad 0\le r_p<p. \]

A single fixed \(N\) for which \(F(k,N,M)\) is satisfiable for every \(M\ge N\) would, by compactness, give the global tail statement. Solutions whose thresholds or residue choices drift with \(M\) would not be enough.

GCL's current state

The pinned catalogue packet records #279 as open, with informal status last updated 2025-08-31, formal status unformalized, and statement-formalized metadata marked yes. The protected catalogue source is teorth/erdosproblems commit 536408716724a2402bdfa7c1d764bf83d64a8c89, entry number: "279", Git blob 4e60263a80af6207aca494d2e1388e44fa372889. The corresponding GCL issue is original issue #1549, whose pinned body identity is SHA-256 f75bc34b97a4831aa3b334074b7815cfa8d5a0b09d16ad8e9cdd9c0bc5221ab9 in the local registry entry.

The authenticated SOURCE RESULT/1 comment is marked PARTIAL. It confirms the source lock, the finite interface above, and the missing global permanence lemma: a multiscale construction would have to control the hard survivors at each scale while preserving all earlier coverage. That is a research interface, not a theorem.

The pinned FormalConjectures file is ErdosProblems/279.lean at commit 85f863718beeec7b58a3a1926ee92e3472bc2020, blob e62a02a940d033ac38e9aee19173d2d13bf8541e. Its quantified statement matches the normalization above. In Lean, a : Nat → Nat is total, but only its values at prime arguments are constrained by a p < p. The theorem is answer(sorry) ↔ ... and ends by sorry. A formal file containing sorry is not a Lean proof and does not change the open status.

The 2026 GPT-generated proof claim associated with the public Chen manuscript remains unreviewed and unverified. It is recorded in the source return only as an external claim requiring specialist checking of its global estimates, tail bookkeeping, and formal dependency surface. #279 therefore remains OPEN.

What remains

The first useful successor task is finite and falsifiable: fix \(k=3\), \(N=30\), and \(M=100\), specify every residue \(r_p\) for \(p\le M/3\), and emit either a witness \((n,p,t)\) for every target or the first uncovered target together with all eligible primes. Every witness must satisfy primality, \(0\le r_p<p\), \(t\ge3\), and \(n=r_p+tp\). Independent recomputation should reproduce the result.

That task is only a test of an assignment. The substantive missing step is uniform permanence. A proof would need to show that, as new scales and new primes are introduced, the remaining uncovered integers are small enough for the available fresh residue classes, while all previously covered integers retain a valid witness. The bookkeeping must work for every scale, not just for a chosen list of intervals. A computation can locate patterns or refute a proposed assignment; it cannot certify termination of this infinite process.

The clean stopping rule is therefore conservative: stop at the prescribed finite bound, or at the first uncovered target, invalid residue, failed maturity inequality, or unsupported source hypothesis. Do not promote finite success to a global theorem.

Sources and claim boundaries

The documentary source lock is the local catalogue registry, whose source.source_sha256 lock is be65b0db56fe13becec3178f2937685ee7e6a2f5df9325712474722c279c4182; the exact catalogue commit and blob, issue, result comment, and FormalConjectures commit/blob are recorded above. The primary references checked for the claims made here are:

  • P. Erdős and R. L. Graham, Old and New Problems and Results in Combinatorial Number Theory, Monographies de l’Enseignement Mathématique 28, Geneva, 1980, p. 29, source scan.
  • The Erdős Problems #279 page, cited for the live catalogue context in the authenticated source return.
  • K. Ford, B. Green, S. Konyagin, and T. Tao, “Large gaps between consecutive prime numbers,” Annals of Mathematics 183 (2016), 935–974, Theorem 1, p. 936, journal record.
  • The unreviewed claim is the Chen manuscript at its cited commit; it is not treated as evidence of proof.

This article does not import neighboring problem results. In particular, any odd greedy computation for #282 must never reuse a denominator, and a finite computation cannot settle its termination. The separate #286 width issue remains an EXACT_BLOCKER because the Erdos–Graham \((e-1)k\) coefficient and Croot’s different width formulation have a material source-semantic conflict; that conflict is neither investigated nor erased here. These boundaries do not alter #279’s status.

Catalogue and evidence provenance

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