Skip to content

Erdős Problem #8

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

The question in plain language

A covering system is a finite collection of congruences whose union contains every integer. Its positive moduli are required to be distinct and greater than one. Erdős Problem #8 asked whether every finite colouring of the positive integers has a colour containing all the moduli of some covering system.

The answer is no. This is a historical problem already disproved using Bob Hough's theorem on the smallest modulus of a distinct covering system. The word finite permits a very large number of colours, not just two.

A small example

Suppose there were a universal bound \(B\) such that every distinct covering system had at least one modulus at most \(B\). Colour the numbers \(1,2,\ldots,B\) using different colours, and colour all numbers greater than \(B\) with one new colour.

A monochromatic covering system cannot use the last colour, because every one of its moduli would exceed \(B\). It cannot use an earlier colour: that colour contains only one possible modulus \(m\), and a single congruence modulo \(m>1\) misses infinitely many integers. This is a complete elementary contradiction, conditional on the bound \(B\).

What is known

Hough, Solution of the minimum modulus problem for covering systems, Annals of Mathematics 181 (2015), 361–382, proved that the smallest modulus of any distinct covering system is at most \(10^{16}\). Thus the colouring construction with \(B=10^{16}\) settles Erdős #8 negatively. The public problem page illustrates the same argument with the looser cutoff \(10^{18}\); that is not a discrepancy in the theorem.

A related density formulation is also described as disproved by the registry, but its separate quantified premise is not reproduced or independently verified by this finite-colouring argument.

GCL's current state

Source audit #1277 identifies the exact covering-system convention and the transfer from Hough's deep theorem to a finite-colouring counterexample. The admitted frozen formal-provider snapshot had no file for this problem; the external theorem's complete proof was not replayed inside GCL.

What remains

Nothing remains to settle the original finite-colouring question. Further documentary or formal work should focus on explicitly importing Hough's theorem, checking the definition of a covering system, and separately documenting the density variant—not reopening the solved assertion as a conjecture.

Sources and claim boundaries

Catalogue and evidence provenance

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