Covering systems of congruences

Statement

A covering system of congruences (Erdős, 1950) is a finite list of congruences $$ a_1 \pmod{m_1},\ a_2\pmod{m_2},\ \ldots,\ a_k\pmod{m_k}, \qquad m_i \ge 2, $$ such that every integer $n$ satisfies at least one of them, i.e. $$ \mathbb Z \;=\; \bigcup_{i=1}^k \{n : n\equiv a_i \pmod{m_i}\}. $$ (en.wikipedia.org/wiki/Covering_system, fetched directly — "a covering system is a collection of finitely many residue classes whose union contains every integer.")

Standard terminology (all from the same source):

- Distinct / incongruent covering system: all moduli $m_1<m_2<\cdots<m_k$ are different (and $>1$). This is the setting of the two most famous Erdős questions about covering systems (minimum modulus, odd moduli — see Facts). - Disjoint / exact covering system: no two residue classes overlap, i.e. the union is a *partition* of $\mathbb Z$. - $m$-cover: every integer is covered at least $m$ times; an exact $m$-cover covers every integer exactly $m$ times. - Irredundant (minimal) system: every congruence is individually necessary — deleting any one leaves some integer uncovered.

Canonical example (Erdős's original 1950 construction, motivating the whole subject): $$ 0\bmod 2,\quad 0\bmod 3,\quad 1\bmod 4,\quad 5\bmod 6,\quad 7\bmod 12 $$ covers every integer, has minimum modulus $2$, distinct moduli $\{2,3,4,6,12\}$ all dividing $12=\mathrm{lcm}$, and was built to prove that the number $n=7629217$ (odd) has the property that $n\cdot 2^k+1$ is composite for every $k\ge 0$ — the residue of $k\bmod 12$ always forces $n\cdot2^k+1$ to be divisible by one of $3,5,7,13,17,241$ (the classical Sierpiński-number covering-congruence trick; en.wikipedia.org/wiki/Covering_system and en.wikipedia.org/wiki/Sierpi%C5%84ski_number).

Facts

- Mirsky–Newman theorem: no *disjoint* (exact) covering system has all moduli distinct and $>1$ — any exact cover with pairwise-disjoint residue classes must repeat some modulus. Conjectured by Erdős (1950), proved by Mirsky and Newman (unpublished), with independent proofs by Davenport and Rado (en.wikipedia.org/wiki/Covering_system). This is the oldest hard structural constraint on the object and rules out the "easiest" kind of covering system (a partition) from having distinct moduli. - Newman–Znám theorem (1968–1971): in a disjoint covering system, if the largest modulus $M$ occurs $\ell$ times, then $\ell$ is at least the smallest prime factor of $M$ (en.wikipedia.org/wiki/Covering_system). - Herzog–Schönheim conjecture (still open): for an exact cover with distinct moduli $m_1,\ldots,m_k>1$, the $m_i$ cannot form a partition of $\mathbb Z$ unless at least two of the $m_i$ coincide — a strengthening in the same family as Mirsky–Newman, unresolved as of this writing. - Minimum modulus problem (Erdős's "perhaps my favorite problem," \$1000 prize) — can $m_1$, the smallest modulus in a distinct covering system, be arbitrarily large? Resolved NO by Robert Hough, "Solution of the minimum modulus problem for covering systems," arXiv:1307.0874, *Ann. of Math.* 181 (2015) 361–382: $m_1\le 10^{16}$ always. Sharpened to $m_1\le 616{,}000$ by Balister–Bollobás–Morris–Sahasrabudhe–Tiba, "Erdős covering systems," arXiv:2211.01417, via a technique they name the distortion method (see Distortion method (Hough; Balister–Bollobás–Morris–Sahasrabudhe–Tiba) for covering-system impossibility bounds). Further sharpened to $m_1\le 118$ under the extra restriction that all moduli be squarefree (Cummings–Filaseta–Trifonov). This is Erdős #2 — minimum modulus of a covering system cannot be arbitrarily large in this wiki (status: DISPROVED). - Erdős–Selfridge conjecture (odd covering systems) — does there exist a distinct covering system with all moduli odd (and $>1$)? Still OPEN as of 2026-07-02 (Open Problem Garden "Odd incongruent covering systems"; arXiv:2507.16135 "A further investigation on covering systems with odd moduli," 2025, treats it as unresolved). Partial computational/structural results constrain any hypothetical odd counterexample to have many distinct prime factors in its overall modulus (progressively pushed up by successive papers, e.g. arXiv:2104.00602 "Covering systems with odd moduli," arXiv:1901.11465 "The Erdős–Selfridge problem with square-free moduli"). Do not confuse this with the minimum-modulus problem above — that one is resolved, this one is not; both are Erdős conjectures about *distinct* covering systems but ask orthogonal questions (size of smallest modulus vs. parity of all moduli). - Erdős–Graham density-of-the-uncovered-set conjecture — if the moduli of a covering-type system are distinct elements of an interval $[n, Cn]$ and $n$ is large, is the density of integers left *uncovered* bounded below by a constant depending only on $C$? Resolved (affirmatively) by Balister–Bollobás–Morris–Sahasrabudhe–Tiba, "On the Erdős Covering Problem: the density of the uncovered set," arXiv:1811.03547, *Invent. Math.* 228 (2022) 377–414 — again via the distortion method. A third, separate, now-closed Erdős question in this family. - Jacobsthal-function covering problem — for the *specific* system that assigns one residue class per prime $p\le x$ (not an arbitrary distinct-modulus system), the maximal interval $[1,y]$ that can be fully covered defines $Y(x)$, with best known bounds $x\frac{\log x\log\log\log x}{\log\log x}\ll Y(x)\ll x^2$ (Ford–Green–Konyagin–Maynard–Tao 2018 lower bound / Iwaniec 1978 upper bound, both cited in Erdős #687 — estimate the Jacobsthal covering function Y(x), OPEN in this wiki). This is the object underlying the Erdős–Rankin construction for large prime gaps: a covering of $(0,y]$ by residues mod primes $\le x$ certifies $(n,n+y]$ prime-free for suitable $n$ — see Erdős–Rankin construction (covering-congruences translation for large prime gaps). - Applications outside pure existence questions: covering systems are the classical tool for proving that a set of *odd* $k$ satisfies "$k\cdot2^n+1$ is composite for all $n\ge0$" (Sierpiński numbers) or "$k\cdot2^n-1$ is composite for all $n\ge0$" (Riesel numbers) — the covering congruence forces every exponent residue class to yield a multiple of some small fixed prime (en.wikipedia.org/wiki/Sierpi%C5%84ski_number; en.wikipedia.org/wiki/Covering_system). The same "cover the exponent/index set, force divisibility" idea generalizes to any problem of the shape "show every member of an infinite family is composite/reducible/non-extremal by exhibiting a covering system on the family's index."

Technique

WHY it works (the mechanism). A covering system converts a *universal* claim over an infinite index set ("for every $n$, property $Q(n)$ fails" / "for every $n$, some fixed divisibility forces compositeness/non-primality/reducibility") into a finite combinatorial certificate: a finite list of (modulus, residue, associated witness) triples such that every $n$ falls into at least one residue class, and inside that class a fixed, checkable reason (e.g. divisibility by a small prime, or membership in a previously-handled case) kills $Q(n)$. The infinitude of the index set is absorbed by the periodicity of congruences — a finite covering automatically handles infinitely many $n$ because residue classes are periodic. This is why covering systems are a generic device for existence proofs by explicit finite construction over statements that are ostensibly about *all* integers.

HOW it is used to prove things (recombination steps)

1. Identify a periodic/divisibility-detectable obstruction. Find, for each candidate modulus $m$ in some pool (primes up to $x$, or small integers), a witness (typically: a fixed prime $q\mid m$, or a fixed small "escape" value) such that whenever $n\equiv a\pmod m$ for the right residue $a$, the target quantity (e.g. $k\cdot2^n+1$, or "$n$ itself" in an interval, or an exponent/parameter in some other family) is automatically disposed of (divisible by $q$, hence composite; or directly hitting a prime $p\le x$, hence composite). 2. Assemble a covering. Choose enough (modulus, residue) pairs so their union is all of $\mathbb Z$ (or all of the target interval $[1,y]$, or all residues mod the relevant period). This is a *finite* search/construction problem — often solved by explicit small examples (Sierpiński-number covers use $\mathrm{lcm}=12$ or $\mathrm{lcm}=24$; the Erdős–Rankin construction covers a much larger interval by combining trivial small-prime coverage with a density bound on the residual set, then a matching/nibble argument on large primes — see Erdős–Rankin construction (covering-congruences translation for large prime gaps)). 3. Read off the theorem. Existence of the covering *is* the proof: every $n$ lands in some class, hence is disposed of by that class's witness, hence the universal claim holds. No further analytic work is needed once the covering is exhibited and checked (this is why lower-bound/existence-type covering-system results are, in principle, mechanically verifiable — see problems/687.md's "Oracle" discussion of this asymmetry). 4. The dual direction — proving no covering exists (impossibility). The harder, structurally different task (minimum-modulus problem, odd-moduli conjecture, Herzog–Schönheim) is to show a covering cannot achieve some extremal property (all moduli large; all moduli odd; distinct moduli plus exact partition). This is *not* a construction problem and needs a genuinely different toolkit: the distortion method (Hough 2015; simplified/strengthened by Balister–Bollobás–Morris–Sahasrabudhe–Tiba, arXiv:2211.01417 — see Distortion method (Hough; Balister–Bollobás–Morris–Sahasrabudhe–Tiba) for covering-system impossibility bounds) reveals the covering's moduli in stages and tracks a weighted probability measure on the not-yet-covered residues, combining Lovász-Local-Lemma-style and moment/variance estimates to show the uncovered density cannot be driven to zero if the moduli are constrained (e.g. all $>10^{16}$, or all odd in weaker partial results) — turning "no covering exists with property $P$" into a quantitative density-can't-vanish theorem. 5. When it does or doesn't apply: covering-system *construction* (steps 1–3) applies whenever the target claim reduces to "every element of an infinite periodic-indexed family is disposed of by a finite union of arithmetic-progression-triggered witnesses" — this includes Sierpiński/Riesel numbers, the Jacobsthal function / Erdős–Rankin prime-gap machine, and (per this wiki) is the reusable engine flagged in Erdős–Rankin construction (covering-congruences translation for large prime gaps) for "any problem reducing to covering-system existence." Covering-system *impossibility* (step 4, the distortion method) applies specifically to "can some covering-system parameter (min modulus, parity, density of escapees) be pushed to an extreme" questions, and is a much newer (2015+), narrower, harder-to-wield toolkit — most of the still-open Erdős questions in this family (odd moduli; Jacobsthal upper bound $Y(x)\ll x^{1+o(1)}$) sit exactly on this harder impossibility side.

Related

- Erdős–Rankin construction (covering-congruences translation for large prime gaps) — the direct application of covering systems (residues mod primes $\le x$) to certify long prime-free intervals; the Jacobsthal function $Y(x)$ is the pure covering-system core of that construction. - Distortion method (Hough; Balister–Bollobás–Morris–Sahasrabudhe–Tiba) for covering-system impossibility bounds — the staged-revelation / weighted-density-measure technique (Hough 2015; BBMST 2022) that proves covering-system *impossibility* results (minimum modulus bounded, density-of-uncovered-set bounded below); the tool for the "no covering exists with property $P$" direction that plain construction cannot reach. - Pippenger–Spencer hypergraph covering theorem (and the FGKMT generalization) and Rödl nibble / semi-random greedy method — iterated small-random-selection for near-perfect hypergraph matchings, packings, and colourings — the semi-random hypergraph-covering machinery (Pippenger–Spencer-style, via the Rödl nibble) used to *build* record-strength covering systems for the Jacobsthal-function lower bound (FGKMT 2018). - Erdős #2 — minimum modulus of a covering system cannot be arbitrarily large — minimum modulus of a distinct covering system cannot be arbitrarily large: DISPROVED (Hough 2015, $\le10^{16}$; BBMST 2022, $\le616{,}000$); the canonical fully-resolved precedent for a covering-system impossibility proof. - Erdős #687 — estimate the Jacobsthal covering function Y(x) — Jacobsthal covering function $Y(x)$ (one residue per prime $p\le x$, cover $[1,y]$): OPEN, upper bound side ($Y(x)\ll x^2$, Iwaniec 1978) unimproved since 1978 — a live target for either a sharper construction or a distortion-method-style impossibility argument. - Erdős #688 — the ε_n covering variant: how few large primes can cover [1,n]? — $\epsilon_n$-restricted variant of the Jacobsthal covering problem (primes confined to $(n^{\epsilon_n},n]$). - Erdős #689 — double covering by prime residues: all-moduli case SOLVED (erdos/1205, F(x)~log x); primes-only case OPEN with two 2026 proof claims unverified — double-covering variant of the Jacobsthal problem (every integer hit by $\ge2$ classes). - Erdős–Selfridge odd-covering conjecture (no dedicated erdos/N page found in this wiki as of 2026-07-02) — still OPEN: does a distinct covering system with all moduli odd exist? The most notorious *unresolved* impossibility question in this family; distinguished here from the resolved minimum-modulus problem (Erdős #2 — minimum modulus of a covering system cannot be arbitrarily large) and the resolved Erdős–Graham density conjecture (BBMST 2022, arXiv:1811.03547), with which it is easily confused. - Finite-field / projective-plane constructions for extremal additive sets — a contrasting "explicit algebraic construction" technique family; covering systems are instead a *combinatorial/arithmetic-progression* construction device, with a genuinely different (density/distortion, not algebraic) toolkit for their impossibility side.