Skip to content

Erdős Problem #275

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

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

An arithmetic progression here means a set of integers

\[ A_i=a_i+n_i\mathbb Z=\{a_i+t n_i:t\in\mathbb Z\}, \]

where \(a_i\in\mathbb Z\) and \(n_i\in\mathbb Z_{>0}\). Repetitions among the moduli are allowed. A finite family \(A_1,\ldots,A_r\) covers a set if every integer in that set lies in at least one \(A_i\); it covers all integers if

\[ \forall x\in\mathbb Z\;\exists i\in\{1,\ldots,r\}\quad x\equiv a_i\pmod{n_i}. \]

Problem 275 asks whether a family of \(r\) progressions that covers one block of \(2^r\) consecutive integers must cover every integer. In exact quantifier form, the assertion is

\[ \left(\exists k\in\mathbb Z\;\forall x\in\mathbb Z,\ k\le x<k+2^r\Rightarrow\exists i\le r,\ x\equiv a_i\pmod{n_i}\right) \Rightarrow \left(\forall x\in\mathbb Z\;\exists i\le r,\ x\equiv a_i\pmod{n_i}\right). \]

The location of the block is irrelevant: translating all the progressions and the block by the same integer preserves the question. The important quantifiers are that the same finite family must cover the whole block, while the witnessing index \(i\) may depend on \(x\).

A small example

The power \(2^r\) is sharp. For \(r=4\), take

\[ A_1=1\pmod 2,\quad A_2=2\pmod 4,\quad A_3=4\pmod 8,\quad A_4=8\pmod {16}. \]

These four classes cover each of \(1,2,\ldots,15\): an integer is assigned according to the position of its first \(1\) in binary, with \(1\) handled by the first class. But \(0\) is in none of them, so this family does not cover \(\mathbb Z\). Thus \(2^r-1\) consecutive integers do not suffice in general, even though \(2^r\) do.

Here is a reproducible finite check of the theorem’s pattern for all ordered triples whose moduli are at most \(4\). Because such a family is periodic with period the least common multiple of its moduli, checking one period is exact for this finite experiment.

from itertools import product
from math import gcd

def lcm(a, b): return a*b//gcd(a, b)
def hit(x, A): return any((x-a) % m == 0 for a, m in A)

checked = witnesses = 0
for S in product(*[[(a,m) for m in range(1,5) for a in range(m)] for _ in range(3)]):
    checked += 1
    q = 1
    for _, m in S: q = lcm(q, m)
    if any(all(hit(x, S) for x in range(k, k+8)) for k in range(q)):
        witnesses += 1
        assert all(hit(x, S) for x in range(q))
print(checked, witnesses)

The verified output is 1000 337: all \(1000\) finite systems were tested, and \(337\) covered some eight-term block; every one of those \(337\) covered its whole period. This is finite evidence, not a proof of the general statement.

What is known

The result is proved externally. R. B. Crittenden and C. L. Vanden Eynden’s announcement, “A proof of a conjecture of Erdős,” Bulletin of the AMS 75 (1969), 1326–1329, and their full paper, “Any \(n\) arithmetic progressions covering the first \(2^n\) integers cover all integers,” Proceedings of the AMS 24 (1970), 475–481, are the original resolution cited by the source packet. The 1970 paper’s opening statement and Lemma 1 are the cited proof and sharpness locations; the original AMS full text was not directly retrievable in this audit, so no stronger page-level inspection is claimed here.

An accessible primary mathematical proof is P. Balister, B. Bollobás, R. Morris, J. Sahasrabudhe, and M. Tiba, “Covering intervals with arithmetic progressions,” Acta Mathematica Hungarica 161 (2020), 197–200. Its Theorem 1 (PDF p. 1, journal p. 197) states the arbitrary-consecutive-block form. The proof (PDF pp. 1–2) reduces to a period \(q\), constructs a polynomial whose zero set records the covered residue classes, and obtains \(2^r+1\) linearly independent translates inside a space of dimension at most \(2^r\), a contradiction. The same paper gives the powers-of-two family as the sharpness example.

GCL's current state

The pinned catalogue packet is the number: "275" entry in teorth/erdosproblems data/problems.yaml, commit 536408716724a2402bdfa7c1d764bf83d64a8c89, Git blob 4e60263a80af6207aca494d2e1388e44fa372889. It records informal status proved, formal status Lean, and formalized: yes, with the relevant updates dated 2026-01-20 (formalization dated 2026-01-18). These are catalogue facts, not certification.

The authenticated original issue is #1545. Its RESULT/1 comment, comment ID 6135326251, exists and begins with ERDOS-CATALOGUE-0275-S01, PROBLEM_ID: 275, and DISPOSITION: PARTIAL. It reports that the live problem page’s indexed status agrees with the pinned catalogue, but direct retrieval of that page returned HTTP 403; that access limitation remains material.

The pinned FormalConjectures file at commit 85f863718beeec7b58a3a1926ee92e3472bc2020 (blob b3c15bfb0c09b8a7eb1429eadea526e4f4a0dbaf) has the right broad interval quantifiers, using Ico k (k + 2 ^ r), but its theorem body is by sorry. It also permits n : Fin r → ℕ, without an explicit hypothesis \(0<n_i\); modulus-zero behavior in Lean therefore needs a separate semantic review. External proof, statement formalization, a Lean-checked proof, and GCL mathematical certification are four different claims. Only the first is established by the evidence summarized here.

What remains

The external theorem itself is not an open conjecture. The bounded formalization question remains: either replay the proof with explicit positive-modulus hypotheses, or prove that the current modulus-zero encoding is harmless and semantically equivalent to the intended statement. A satisfactory Lean result would compile with no sorry, introduce no unverified axioms, and compare the interval formulation with the congruence formulation, including the exact \(2^r\) cardinality and the sharpness family.

The source-audit return deliberately remains PARTIAL because the original 1969/1970 source text was not directly page-audited and because the pinned Lean theorem is not a checked proof. Those limitations do not undo the published mathematical result, but they prevent upgrading the formal or documentary claims. The finite program above can catch transcription and boundary errors; it cannot replace the proof.

Sources and claim boundaries

This manuscript is a local documentary draft for critical editorial review. It is not accepted: publication ledger status alone decides acceptance, and neither this article nor its editorial explanation certifies the mathematics.

Catalogue and evidence provenance

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