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
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
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
- Erdős Problems #27: DISPROVED statement and status.
- Filaseta–Ford–Konyagin–Pomerance–Yu (2007), author manuscript; DOI.
- GCL source return #1296: elementary calculation and source boundaries, not theorem certification.
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.