Erdős #2 — minimum modulus of a covering system cannot be arbitrarily large

Statement

A distinct covering system (or "covering system with distinct moduli") is a finite list of congruences $$a_1 \pmod{m_1},\ a_2 \pmod{m_2},\ \ldots,\ a_k \pmod{m_k}, \qquad 1 < m_1 < m_2 < \cdots < m_k,$$ such that every integer satisfies at least one of the $k$ congruences (i.e. the union of the residue classes is all of $\mathbb Z$). Erdős introduced these systems in 1950 (motivated by a problem on Riesel/Sierpiński-type covering of $2^n\pm k$) and asked: can the minimum modulus $m_1$ of a distinct covering system be arbitrarily large? Equivalently: does there exist, for every $N$, a distinct covering system with $m_1 > N$? Erdős called this "perhaps my favorite problem" and offered \$1000 for a resolution.

Facts

- Origin: P. Erdős, 1950, motivated by covering the integers to study numbers of the form $2^n+k$ that are never prime (the original covering system used had minimum modulus $2$: moduli $\{2,3,4,6,12\}$). - Trivially, coverings with small minimum modulus abound (e.g. the classical example above has $m_1=2$); the question is whether $m_1$ can be pushed up without bound by cleverer, larger constructions. - Related classical fact: the Mirsky–Newman theorem shows there is no *disjoint* (exact) distinct covering system, i.e. covering systems with distinct moduli necessarily have overlapping residue classes — a structural constraint the eventual proof exploits. - Solved (negatively) in 2015 by Robert (Bob) Hough: the minimum modulus of *any* distinct covering system is bounded, specifically $m_1 \le 10^{16}$. So the answer to Erdős's question is NO — $m_1$ cannot be arbitrarily large; it is a bounded, universal constant. Source: R. D. Hough, "Solution of the minimum modulus problem for covering systems," arXiv:1307.0874, published *Annals of Mathematics* 181 (2015), no. 1, 361–382 (annals.math.princeton.edu/2015/181-1/p06). Abstract: "We answer a question of Erdős by showing that the least modulus of a distinct covering system is at most $10^{16}$." - Hough's proof built on structural/heuristic work of Filaseta, Ford, Konyagin, Pomerance & Yu (2007) on covering systems with restricted, small minimum modulus, which suggested a bound should exist but did not prove one unconditionally for all systems. - Improved bound: Paul Balister, Béla Bollobás, Robert Morris, Julian Sahasrabudhe, Marius Tiba, "Erdős covering systems," arXiv:2211.01417 — introduced a simplified, more powerful variant they name the distortion method and reduced the bound to $m_1 \le 616{,}000$. - Further improved for restricted moduli: Cummings, Filaseta, Trifonov (arXiv:2211.08548 / Acta Math. Hungarica) show that if the moduli are additionally required to be squarefree, the minimum modulus is at most $118$. - The technique generalizes beyond $\mathbb Z$: analogues of the minimum-modulus bound have since been proved for covering systems of number fields (arXiv:2302.05946) and of polynomial rings over finite fields / global function fields (arXiv:2308.05378, arXiv:2402.03810, arXiv:2408.10460) — all citing Hough's / BBMST's method as the starting point. - Related open problem still standing: the Erdős–Selfridge conjecture — that there is no distinct covering system all of whose moduli are *odd* (with min modulus $>1$) — remains open; partial computational/structural work shows such a system, if it exists, would need the overall modulus to have at least 22 distinct prime factors.

Solution

Answer: NO — the minimum modulus is bounded (Hough 2015: $\le 10^{16}$; sharpened by Balister–Bollobás–Morris–Sahasrabudhe–Tiba 2022 to $\le 616{,}000$; sharpened further to $\le118$ under a squarefree restriction by Cummings–Filaseta–Trifonov).

The transferable idea — the distortion method (probabilistic covering-density argument, revealed in stages):

1. Set-up as a covering/density problem. Suppose for contradiction a distinct covering system exists with minimum modulus $m_1 = N$ very large. The moduli $m_1 < m_2 < \cdots < m_k$ can be grouped by their largest prime factor / by scale, and the "weight" (density) contributed by the residue class of modulus $m_i$ is $1/m_i$. Since the classes must cover $\mathbb Z$, the total weighted density $\sum 1/m_i \geq 1$ is a necessary condition — but this alone (the classical, Erdős-era heuristic) is far too weak to force a bound on $m_1$, because you can have $\sum 1/m_i$ diverge slowly while $m_1\to\infty$.

2. Reveal the covering progressively and track a sequence of probability measures. The key innovation (Hough's original method, refined into the "distortion method" by BBMST) is to *not* analyze the final covering all at once. Instead, the moduli are processed in increasing order (by prime-factorization structure), and after each stage one maintains a probability measure on the yet-uncovered residues (equivalently, a "distortion" of the uniform/Haar measure on $\hat{\mathbb Z}$-type profinite space, or concretely a weighted density over $\mathbb Z/M\mathbb Z$ for the LCM $M$ of moduli seen so far). Each new congruence class removes a controllable chunk of this measure's mass, and the argument tracks how much distortion (deviation from a "generic"/expected density decay) each step can introduce.

3. A second-moment / local-lemma-flavored obstruction. The proof shows that if $m_1$ is too large, the moduli available at each stage are too sparse (too few primes with the right small prime factors, since minimum modulus large forces all moduli to be composed of large-ish primes) to reduce the uncovered-density measure to zero — i.e. no matter how the covering is assembled, some positive-density (in the weighted, moment sense) set of residues survives uncovered, contradicting that the system covers all of $\mathbb Z$. This combines ideas from the Lovász Local Lemma (bounding the probability that "bad events" — residues remaining uncovered — can be avoided simultaneously) with explicit moment/second-moment estimates on the distortion of the density measure at each stage, giving a *quantitative*, quite strong obstruction rather than a purely existential local-lemma statement.

4. Why this cracked the problem where earlier heuristics failed. Earlier work (Erdős's own remarks, and Filaseta–Ford–Konyagin–Pomerance–Yu) used static, aggregate density/sieve bounds ($\sum 1/m_i \geq 1$, character-sum/sieve estimates) that could rule out *specific small* minimum moduli but could not close the argument for all $N$ simultaneously, because they didn't account for how the *order* in which congruences are added constrains the remaining freedom. The distortion method's dynamic, staged-revelation viewpoint turns covering into an "process/martingale-like" argument: it bounds not just the final density but the whole *trajectory* of how density can be removed, which is what makes the bound uniform and effective (an explicit numeric constant, not just "eventually bounded").

5. Transferability. The method is explicitly presented (BBMST, arXiv:2211.01417) as a general-purpose tool — "distortion method" — for any problem of the shape "show a covering/packing-type structure indexed by a divisor/modulus lattice cannot avoid some residual density," and has already been ported to: number fields (arXiv:2302.05946), polynomial rings over finite fields (arXiv:2308.05378), and global function fields (arXiv:2402.03810, arXiv:2408.10460), and to sharper restricted-modulus variants (squarefree case, Cummings–Filaseta–Trifonov, bound 118). This is the concept to link as `Distortion method (Hough; Balister–Bollobás–Morris–Sahasrabudhe–Tiba) for covering-system impossibility bounds`.

Bottom line for downstream use: the "distortion method" = (i) never analyze a covering system as a static final object; instead (ii) reveal moduli in stages and maintain an explicit weighted/probability measure on the not-yet-covered residues, (iii) use local-lemma-style + moment estimates to bound how much that measure's density can be "distorted" (reduced) per stage given constraints on available moduli, (iv) conclude no assembly of large-minimum-modulus congruences can drive the uncovered density to $0$. Any open problem asking whether some combinatorial/number-theoretic covering-type quantity can be pushed arbitrarily far is a candidate for this technique.

Related

- Distortion method (Hough; Balister–Bollobás–Morris–Sahasrabudhe–Tiba) for covering-system impossibility bounds — the transferable technique itself (staged revelation + weighted density measure + local-lemma/moment obstruction), coined by Balister–Bollobás–Morris–Sahasrabudhe–Tiba (arXiv:2211.01417) as a refinement of Hough's original 2015 argument. - Lovász Local Lemma (symmetric, general/asymmetric, and algorithmic/random-recoloring variants) — probabilistic existence when bad events are individually non-negligible but sparsely dependent — the probabilistic-method ingredient bounding simultaneous avoidance of "residue left uncovered" bad events. - concept/covering-system — the underlying object (finite union of residue classes covering $\mathbb Z$); Mirsky–Newman theorem (no disjoint distinct covering system) is a structural precursor fact used in this area. - erdos/erdos-selfridge (odd covering systems conjecture, still OPEN) — the natural next-hardest question in this family: whether a distinct covering system with all moduli odd (min modulus $>1$) can exist at all; unresolved, and the distortion method has not yet closed it (only partial computational bounds, e.g. requiring $\geq22$ prime factors, are known). - concept/sieve-methods — classical density/character-sum tools (Filaseta–Ford–Konyagin–Pomerance–Yu 2007) that gave the pre-2015 heuristic evidence a bound should exist, but could not prove it unconditionally.