Exhibit a covering system of the integers with all moduli odd, or prove none exists (Erdős #7)
Statement
A distinct covering system is a finite set of congruences $a_1\ (\mathrm{mod}\ n_1),\ldots,a_k\ (\mathrm{mod}\ n_k)$ with distinct moduli $1<n_1<\cdots<n_k$ such that every integer satisfies at least one of the congruences. Is there a distinct covering system all of whose moduli are odd?
Acceptance. FULLY RESOLVES (yes direction): an explicit odd distinct covering system — the full list of congruences $a_i\ (\mathrm{mod}\ n_i)$ with all $n_i$ odd, distinct, and $>1$, plus a machine check that every residue class modulo $\mathrm{lcm}(n_1,\ldots,n_k)$ satisfies at least one congruence; fully machine-checkable. FULLY RESOLVES (no direction): a proof that no odd distinct covering system exists — machine-checkable (Lean/Coq; the statement is formalized in the DeepMind formal-conjectures repository) preferred, else a complete written proof. ADVANCES: new proved structural constraints on a hypothetical odd covering strictly beyond those stated in the background (e.g. strengthening the lcm-divisible-by-9-or-15 constraint, or lower bounds on the number of moduli or the least possible lcm); or a reproducible exhaustive search certifying that no odd covering exists with lcm of moduli at most an explicit bound $L$, or with moduli drawn from a stated finite set, with code and verifiable exhaustiveness certificates (e.g. DRAT/UNSAT proofs). Deliver the covering list plus checker script, or the proof file, or the search encoding plus certificates and the attained bound.
Background
Asked by Erdős and Selfridge (sometimes also attributed with Schinzel), appearing across Erdős's problem papers from [Er57] and [Er61] onwards; listed as open on erdosproblems.com/7 (fetched 2026-07-13, status 'verifiable', tagged 'number theory | covering systems'). The prize history is famously two-sided [FFK00]: Erdős, convinced an odd covering exists, offered $25 for a proof that none exists, while Selfridge, convinced of the opposite, offered $300 for an explicit example and later raised his award to $2000 (no award was promised for a non-constructive existence proof). Known constraints: the stronger question with odd AND squarefree moduli has a negative answer, proved by Balister, Bollobás, Morris, Sahasrabudhe, and Tiba [BBMST22]; Hough and Nielsen [HoNi19] proved that every distinct covering system has a modulus divisible by $2$ or $3$ (so an odd covering must use a modulus divisible by $3$), with a simpler proof in [BBMST22], which also shows that the lcm of the moduli of any odd covering must be divisible by $9$ or $15$. Selfridge showed (reported in [Sc67]) that an odd covering would follow from a covering system whose moduli form an antichain under divisibility, but such coverings were later shown not to exist (Erdős #586, erdosproblems.com/586). Closely related to (but distinct from) the venue problem asking for a covering system whose moduli are all of the form $p-1$ for primes $p\geq 5$ (Erdős #273). The attacker's tool: exact-cover/SAT encodings over candidate odd modulus sets (fixing a target lcm $L$ with $9\mid L$ or $15\mid L$, residues as variables, coverage of all classes mod $L$ as clauses), giving finite certifiable searches per $L$, alongside the recursive constructions traditionally used to build covering systems.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #7 (T. F. Bloom) | website |
| REF-02 | Lean formalization of Erdős #7 (DeepMind formal-conjectures) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.