Skip to content

Erdős Problem #2

Editorial depth: Legacy authored exemplar — not separately admitted.
Snapshot classification: disproved (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.

Legacy editorial exemplar

This early authored explanation predates the manuscript-acceptance ledger. It is provided as a qualified educational exemplar, not a separate source-verified editorial acceptance or mathematical certification.

The question in plain language

Imagine choosing a finite collection of repeating schedules that between them cover every integer, even though no two schedules repeat at the same interval. Each schedule is a residue class, such as all integers leaving remainder 1 when divided by 4. The repeat interval is called its modulus.

Erdős asked whether it is possible to cover every integer using only very large, pairwise distinct moduli. Could the smallest modulus exceed a million—or any proposed bound?

A small example

One covering system uses the residue classes

\[ 0\pmod 2,\quad 0\pmod 3,\quad 1\pmod 4,\quad 5\pmod 6,\quad 7\pmod{12}. \]

Every integer falls into at least one class, as checking the 12 residue possibilities confirms. The moduli are distinct, but the smallest is 2. Erdős wanted to know whether all small moduli could be avoided.

What is known

The original question was answered no. Bob Hough proved in 2015 that any such covering system must have some modulus at most \(10^{16}\). Work by Balister, Bollobás, Morris, Sahasrabudhe, and Tiba subsequently brought the published universal upper bound to 616,000.

The largest known example of the smallest modulus is 42 (Owens). This leaves an enormous gap between construction and impossibility bounds. A negative answer to Erdős's original unlimited-growth question does not determine the optimal ceiling.

GCL's current state

GCL's Erdős #2 intake record is registered for a source-and-method provenance review. At the last checked state it had no returned mathematical source audit. Neither a GCL reproduction of Hough's proof nor an independent formal proof replay is on record.

The protected catalogue snapshot reports a Lean-related status, but the public problem page and GCL's source packet do not themselves establish a verified formal proof. The discrepancy needs reconciliation, not an invented completed check.

What remains

The original conjecture is settled. Improving the interval between 42 and 616,000, understanding why large congruence schedules inevitably leave uncovered numbers, and formalizing the strongest proofs are legitimate open directions.

Sources and claim boundaries

  • Erdős Problems #2 — statement, dated bound summary and bibliography.
  • B. Hough, Solution of the minimum modulus problem for covering systems, Annals of Mathematics (2015).
  • P. Balister, B. Bollobás, R. Morris, J. Sahasrabudhe and M. Tiba, On the Erdős covering problem: the density of the uncovered set, Inventiones Mathematicae (2022).
  • GCL source-audit #1271 — operational evidence, not mathematical certification.

Catalogue and evidence provenance

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