← All papers
First page of Kernel-Checked Exclusions for the Erdős-Selfridge Odd Covering Problem: Any Odd Covering of $\mathbb{Z}$ Has lcm Exceeding 10000

Kernel-Checked Exclusions for the Erdős-Selfridge Odd Covering Problem: Any Odd Covering of $\mathbb{Z}$ Has lcm Exceeding 10000

Ibrahim Mian, Shayaan Siddique

cs.LO Jul 28, 2026 · v1 math.NT
Lean 4 over Mathlib formalizes, with kernel-checked proofs, that any odd covering system of Z has lcm exceeding 10000.
The Erdős-Selfridge odd covering problem (Erdős problem #7) asks whether a covering system of $\mathbb{Z}$ exists whose moduli are all odd, distinct, and greater than 1. The problem is open. We present a Lean 4 formalization, checked end to end by the proof kernel, of the exclusion: any covering of $\mathbb{Z}$ by finitely many congruence classes with distinct odd moduli > 1 has lcm of the moduli exceeding 10000. The proof composes a formalized density argument (a covering by divisors of $N$ exceeding 1 forces $2N \le σ_1(N)$, so the lcm is abundant or perfect), a kernel-checked abundancy floor (no odd $N < 945$ qualifies), a family of Chinese-Remainder capacity certificates – decidable per-$N$ arithmetic inequalities each refuting every covering with distinct moduli > 1 dividing that $N$ – for all 23 odd abundant numbers below $10^4$, and a kernel-checked enumeration establishing that those 23 are the only odd non-deficient candidates. The result is transported to the official StrictCoveringSystem $\mathbb{Z}$ formulation of Erdős #7 in google-deepmind/formal-conjectures, with a bidirectional periodicity bridge between coverings of $\mathbb{Z}$ and finite checks over $\mathbb{Z}/N\mathbb{Z}$ suitable for consuming future SAT-style search output. All 63 published theorems depend on exactly propext, Classical.choice, and Quot.sound: no sorry, no native_decide, no solver in the trusted base. The mathematical content is known – the density argument is folklore, and far larger uncertified classifications of covering numbers exist – so the contribution is epistemic rather than mathematical: these exclusions are theorems of the Lean kernel, with an axiom gate enforced mechanically in continuous integration.

The Erdős-Selfridge odd covering problem (Erdős #7) asks whether a covering system of Z exists with all moduli odd, distinct, and greater than 1. The problem is open, and prior computational classifications rely on unverified solvers.

A Lean 4 formalization over Mathlib establishes an elementary exclusion tier without trusting unverified computation. It composes a density argument (a covering by divisors forces 2N ≤ σ₁(N), so N is perfect or abundant), a kernel-checked abundancy floor at 945, Chinese-Remainder capacity certificates refuting coverings for each of the 23 odd abundant numbers below 10⁴, and a kernel-checked enumeration confirming those 23 are the only candidates. A bidirectional periodicity bridge relates coverings of Z to finite decidable checks over Z/NZ, and results are transported to the official StrictCoveringSystem statement in google-deepmind/formal-conjectures.

Any covering of Z with distinct odd moduli > 1 has lcm exceeding 10000, proven as kernel-checked theorems. All 63 published theorems depend only on propext, Classical.choice, and Quot.sound, with no sorry, no native_decide, and no external solver in the trusted base; an axiom gate enforces this in CI.