Skip to content

Erdős Problem #27

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

An almost covering system consists of finitely many congruences with distinct moduli that collectively miss only a small proportion of integers. Erdős Problem #27 asked whether there is one constant \(C>1\) such that, for every desired uncovered proportion \(\varepsilon>0\) and every lower cutoff \(N\), one can choose all moduli between \(N\) and \(CN\) and still leave at most an \(\varepsilon\) proportion uncovered.

The answer is no. Requiring one fixed multiplicative interval is too restrictive.

A small example

For distinct moduli \(m_1,\ldots,m_k\), independently choose one residue uniformly modulo each \(m_i\). For any fixed integer \(x\), the probability that none of the random congruences contains \(x\) is

\[ \prod_{i=1}^k\left(1-\frac1{m_i}\right). \]

Averaging over one period of the combined congruences shows there is some residue selection whose uncovered density is at most that product. This is a probability calculation about independently chosen residues, not an assumption that the moduli themselves are coprime.

For all integer moduli from \(N\) through \(M\), the product telescopes to

\[ \prod_{m=N}^{M}\left(1-\frac1m\right)=\frac{N-1}{M}. \]

When \(M\) is approximately \(CN\), the product approaches \(1/C\), not zero.

What is known

Filaseta, Ford, Konyagin, Pomerance and Yu, Sieving by large integers and covering systems of congruences, Journal of the American Mathematical Society 20 (2007), 495–517, prove a strong uncovered-density lower bound for large distinct moduli lying in a fixed multiplicative interval. In particular, for any fixed \(C>1\), one cannot make the uncovered proportion arbitrarily small merely by choosing residues and moduli within \([N,CN]\) as \(N\) grows.

The hard theorem supplies the lower bound for all residue choices. The elementary averaging calculation above supplies a useful upper choice but does not, by itself, prove the negative answer.

GCL's current state

Source audit #1296 records the exact quantifier order and links to the published paper and author manuscript. It derives the independent-residue averaging identity and distinguishes an almost covering from an exact covering. No complete replay of the deep sieve argument or GCL mathematical certificate is claimed.

What remains

The historical question has been answered negatively. Further work would concern faithful formalization of the quantitative lower bound, its uniform dependence on the interval width, or strengthened covering-system results—not a fresh solution to the original conjecture.

Sources and claim boundaries

Catalogue and evidence provenance

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