Distortion method (Hough; Balister–Bollobás–Morris–Sahasrabudhe–Tiba) for covering-system impossibility bounds

Statement

Informal. The distortion method is a technique for proving that a "covering-type" structure built from progressively revealed, distinct, ordered building blocks (moduli of a covering system; hyperplanes of a combinatorial box) *cannot* actually cover its ambient space once the blocks are constrained to come from a sufficiently sparse index set (e.g. all moduli exceeding a threshold $N$). It replaces the classical *static* density bound $\sum 1/m_i \ge 1$ (necessary but far too weak) with a *dynamic* one: reveal the blocks in stages, carry along an explicitly reweighted ("distorted") probability measure that tracks how much of the space is still uncovered, and show by a second-moment argument that this measure's mass on the uncovered set can never be driven to $0$.

Formal abstraction (Balister–Bollobás–Morris–Sahasrabudhe–Tiba, arXiv:2211.01417, Theorem 2.1). Covering systems are recast as *hyperplane covers of a discrete box*: let $Q = S_1 \times S_2 \times \cdots \times S_n$ with $|S_k|\ge 2$ and $\liminf_k |S_k|/k > 3$. A "hyperplane" $A$ fixes coordinates on some finite index set $F(A)\subset\{1,\dots,n\}$; a covering system's congruence $a\pmod m$ becomes a hyperplane whose fixed coordinates $F(A)$ correspond to the prime-power factors of $m$. Two hyperplanes are *parallel* if they fix the same coordinate set with different values there and hence never intersect. Theorem. If a collection of pairwise non-parallel hyperplanes covers $Q$, then some hyperplane $A$ in the collection has $F(A)\subset\{1,\dots,C\}$ for an absolute constant $C$ (depending only on the growth rate of $|S_k|$). Specialized back to $\mathbb Z$ (moduli $=$ products of the first several prime powers, $S_k$ built from a set of primes with $|S_k|\asymp k$), this is exactly: the minimum modulus of a distinct covering system is bounded by an absolute, explicit constant — Erdős's question, answered *negatively*.

The distortion recursion (Definition 3.1, quoted structure). Reveal hyperplanes/congruences in $n$ rounds. Maintain probability measures $\mathbb P_0,\mathbb P_1,\dots,\mathbb P_n$ on $Q$ (initially uniform), each supported so that mass migrates toward the still-uncovered points. At round $k$, for a point $x$ in the base and its fiber $S_k$, let $\alpha_k(x)$ be the proportion of that fiber newly covered in round $k$, and fix a threshold $\delta\in(0,1)$: $$ \mathbb P_k(x,y) \;=\; \begin{cases} \max\!\Big\{0,\ \dfrac{\alpha_k(x)-\delta}{\alpha_k(x)(1-\delta)}\Big\}\cdot \dfrac{\mathbb P_{k-1}(x)}{|S_k|} & \text{if } (x,y) \text{ was covered in round } k,\\[2mm] \min\!\Big\{\dfrac{1}{1-\alpha_k(x)},\ \dfrac{1}{1-\delta}\Big\}\cdot \dfrac{\mathbb P_{k-1}(x)}{|S_k|} & \text{if } (x,y) \text{ is still uncovered,} \end{cases} $$ chosen so total mass is preserved fiber-by-fiber: $\sum_y \mathbb P_k(x,y)=\mathbb P_{k-1}(x)$. In words: if a fiber is *lightly* covered ($\alpha_k(x)\le\delta$) the measure is simply zeroed out on the covered points and redistributed onto the survivors (an exact, "clean" update); if a fiber is *heavily* covered ($\alpha_k(x)>\delta$) the update is *capped* — uncovered points' mass is boosted by at most $1/(1-\delta)$ rather than the full $1/(1-\alpha_k(x))$, and covered points retain a controlled residual instead of vanishing. This capping — the "distortion" of the naive conditional-measure update — is exactly what stops the argument from degenerating when a single round covers almost everything.

Master criterion (Lemma 3.2). If $$ \tfrac14\,\delta(1-\delta)\sum_{k=1}^{n} \mathbb E\big[\alpha_k(x)^2\big] \;<\; 1, $$ then the hyperplane collection does not cover $Q$ — i.e. $\mathbb P_n$ retains strictly positive mass on uncovered points. So the entire proof reduces to a second-moment bound on the per-round coverage proportions $\alpha_k(x)$.

Facts

- Origin. Robert (Bob) Hough, "Solution of the minimum modulus problem for covering systems," arXiv:1307.0874, *Annals of Mathematics* 181 (2015), no. 1, 361–382. Proves the *un-named* precursor of the method: moduli are processed in stages organized by prime thresholds $P_0<P_1<P_2<\cdots$; $\mathbb Z/Q_{i+1}\mathbb Z$ is viewed as fibred over $\mathbb Z/Q_i\mathbb Z$ (for $Q_i$ the product of primes used so far); an explicitly reweighted measure $\mu_i$ on residues is carried from stage to stage; a *relative* (well-distributedness) form of the Lovász Local Lemma controls how much of the reweighted measure any single new congruence class can remove. Conclusion: minimum modulus $m_1 \le 10^{16}$. - Renaming and simplification. Paul Balister, Béla Bollobás, Robert Morris, Julian Sahasrabudhe, Marius Tiba, "Erdős covering systems," arXiv:2211.01417 (8-page expository note). States explicitly it gives "a simpler and stronger variant of Hough's method," names the reweighting device the distortion method, replaces Hough's Lovász-Local-Lemma machinery with the direct second-moment stopping criterion (Lemma 3.2 above), recasts the whole problem as covering a combinatorial box $Q=S_1\times\cdots\times S_n$ by non-parallel hyperplanes (Theorem 2.1), and sharpens the bound to $m_1 \le 616{,}000$. - Precursor use in the same author group. Balister, Bollobás, Morris, Sahasrabudhe, Tiba, "The Erdős–Selfridge problem with square-free moduli," arXiv:1901.11465 — an earlier paper (2019) already using a proto-distortion / reweighted-measure argument to show a covering system with squarefree moduli must contain an even modulus; historically this is where the reweighting idea was developed before being abstracted and named in the 2022 note. - Further sharpening. Cummings, Filaseta, Trifonov, arXiv:2211.08548 (Acta Math. Hungarica) — apply the *same* distortion method, with parameters retuned for the squarefree-moduli restriction, to push the bound down to $m_1 \le 118$. - Ported to structurally analogous "covering by cosets" problems: - Klein–Koukoulopoulos–Lemieux — generalize Hough's original result to covering systems "of multiplicity" (each residue allowed to be covered a bounded number of times rather than once). - Number fields: arXiv:2302.05946 (minimum-modulus analogue for covering systems of a number field's ring of integers). - Polynomial rings over finite fields: arXiv:2308.05378. - Global function fields: arXiv:2402.03810, arXiv:2408.10460 (bounds for Erdős covering systems in this setting). - All of the above explicitly cite Hough's staged-reweighting idea and/or the BBMST distortion method as their starting machinery (WebSearch-corroborated from titles/abstracts; not all fetched in full). - Direction of the result. The method proves *impossibility* (non-existence / boundedness), not existence — it is the negative counterpart to constructive covering-system tools like the Erdős–Rankin method (Erdős–Rankin construction (covering-congruences translation for large prime gaps)), which instead *builds* coverings to prove long composite runs / large prime gaps exist. Distortion shows a covering *cannot* be built once minimum modulus is forced too large. - Related open problem the method has not closed: the Erdős–Selfridge conjecture (no distinct covering system with all moduli *odd*) remains open even after the squarefree case was settled; current partial results require any counterexample to have $\ge 22$ distinct prime factors.

Technique

WHEN it applies. Any problem of the shape: "a structure is built by revealing, in some natural order, a sequence of *set-restriction* events (congruence classes, hyperplanes fixing coordinates, cosets of increasing index) drawn from an index set whose 'resource' (density $1/m_i$, or fiber size $1/|S_k|$) is controlled — show that if the *minimum* resource-cost per event is bounded below too strongly (moduli too large / fibers too small), the events *cannot* jointly cover the whole space." The hyperplane-box abstraction ($Q=S_1\times\cdots\times S_n$, non-parallel hyperplanes) is deliberately general: any indexed family of "coordinate-fixing" restrictions with a controlled growth rate on fiber sizes is a candidate, not just literal integer congruences.

WHY it works (the mechanism). 1. Static density bounds are too weak because they discard order information. $\sum 1/m_i \ge 1$ is necessary for a cover but is compatible with $m_1\to\infty$ (you can have infinitely many terms with slowly diverging reciprocal sum, all individually huge). A bound on $m_1$ requires exploiting *how* the covering must be assembled, not just its final aggregate density. 2. Track a measure, not a set. Instead of asking "is the uncovered set empty?", track a full probability measure on the *not-yet-covered* points, updated stage by stage. This turns a single yes/no covering question into a controllable stochastic process whose terminal mass on uncovered points can be lower-bounded. 3. The distortion (capping) step is what makes the recursion tractable. A naive "conditional measure given still-uncovered" update is fine when each round removes a small fraction $\alpha_k(x)\le\delta$ of a fiber's mass, but blows up combinatorially (unbounded reweighting factor $1/(1-\alpha_k(x))$) when a round removes almost all of a fiber. Capping the reweighting factor at $1/(1-\delta)$ — at the cost of *not* fully zeroing the measure on freshly-covered points, i.e. deliberately introducing bounded "distortion" from the true conditional measure — keeps the whole recursion Lipschitz/bounded, so its behavior can be analyzed by second moments alone. 4. Second moments, not a full local-lemma machine. Lemma 3.2 reduces the entire non-covering conclusion to bounding $\sum_k \mathbb E[\alpha_k(x)^2]$ — an ordinary second-moment computation over how much of a random fiber a new hyperplane/congruence can hit, exploiting that distinct moduli / non-parallel hyperplanes cannot "double count" the same coordinate pattern (Lemma 4.2's bound $\mathbb P_k(A)\le\prod_{j\in F(A)}1/((1-\delta)|S_j|)$ on any single hyperplane's measure). This is *why* BBMST call their variant simpler than Hough's: it replaces a relative/well-distributedness form of the Lovász Local Lemma with a single explicit second-moment sum, decoupling "does the process terminate with uncovered mass" (Lemma 3.2, model-independent) from "how big can each round's contribution be" (Lemma 4.1, the only place number-theoretic input about primes/moduli enters).

HOW to use it to prove things (recombination steps)

1. Recast your covering-type object as staged coordinate-fixing events on a box $Q=S_1\times\cdots\times S_n$. For classical covering systems: order primes/prime-powers, let $S_k$ enumerate the possible residues mod the $k$-th prime power used, and each congruence $a\pmod m$ becomes the hyperplane fixing exactly the coordinates corresponding to $m$'s prime-power factors. 2. Verify the growth condition $|S_k|\ge2$, $\liminf |S_k|/k>3$ (or the analogue in your setting) — this is what lets the later second-moment sum converge; it is the abstract stand-in for "moduli grow like the primes/prime-powers, not sparser." 3. Set up the distortion recursion with a tunable cap parameter $\delta$: at each stage, update the measure by the two-case rule (clean removal below $\delta$, capped boost above $\delta$), preserving total fiber mass. 4. Bound $\mathbb E[\alpha_k(x)^2]$ using structural non-degeneracy (distinct moduli $\Rightarrow$ non-parallel hyperplanes $\Rightarrow$ Lemma 4.2's product bound on any single hyperplane's probability mass) — this is the step that must be redone for each new setting (number fields, function fields, multiplicity-covering, squarefree-restricted), but it is a self-contained, purely combinatorial second-moment computation, decoupled from the general machine. 5. Apply the master criterion (Lemma 3.2): if the resulting $\sum_k\mathbb E[\alpha_k(x)^2]$ sum is small enough (forced when the minimum "resource cost," e.g. minimum modulus, is assumed too large), conclude the cover fails — contradiction, so the minimum modulus/resource cost must in fact be bounded by an absolute constant, which the same computation makes explicit and numeric (not just finite). 6. Optimize $\delta$ and the prime/coordinate thresholds to push the resulting numeric constant down — this is where essentially all of the improvement chain ($10^{16}\to616{,}000\to118$ for squarefree) lives; the *structure* of the argument (steps 1–5) is unchanged across all of these papers. 7. When it does not directly apply: the method proves *non-existence above a threshold*, not a matching construction or the *exact* extremal value — it gives an upper bound on the minimum modulus, not the true minimum modulus (unknown; conjectured much smaller, e.g. Erdős's own examples have $m_1=2$, and Erdős conjectured the truth might be a small constant, far below $616{,}000$/$118$). It also currently requires the covering's building blocks to have a controlled, roughly-linear-in-index growth rate ($|S_k|\gtrsim k$) — problems where this fails need a different combinatorial encoding before the machine applies.

Related

- Erdős #2 — minimum modulus of a covering system cannot be arbitrarily large — Erdős's minimum-modulus-of-a-covering-system question: SOLVED (negatively) by Hough 2015 ($m_1\le10^{16}$), sharpened by this exact technique (BBMST 2022, $m_1\le616{,}000$; Cummings–Filaseta–Trifonov, squarefree case, $m_1\le118$). The canonical target application and origin of the method. - Erdős–Rankin construction (covering-congruences translation for large prime gaps) — the constructive counterpart: builds covering systems of congruences to *force* long composite runs / large prime gaps to exist. Distortion is the matching *impossibility* tool for the same class of objects (covering systems), proving they cannot be pushed past a threshold rather than that they can be built. - 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 in Hough's original 2015 proof (a relative/well-distributedness form), which BBMST's distortion method replaces with a more elementary, purely second-moment argument (Lemma 3.2) while keeping the same staged-revelation philosophy. - Second moment method / Paley–Zygmund inequality — variance-based random-structure existence proofs — the master criterion of the distortion method (Lemma 3.2) is itself a second-moment bound on per-round coverage proportions $\alpha_k(x)$; this is the concrete probabilistic tool doing the load-bearing work once the distortion recursion sets up the measure. - Concept referenced but not yet its own page: "covering systems of congruences" (the underlying combinatorial object; Mirsky–Newman theorem — no *disjoint* distinct covering system exists — is a related structural precursor fact, already noted in erdos/2.md) and "Erdős–Selfridge conjecture" (odd covering systems, still OPEN; the distortion method has been applied to the squarefree case but not yet to close the fully general odd-moduli conjecture).