Irreducible covering sets: count them, bound $n_k$, and maximise $\sum 1/n_i$ (Erdős #1189)
Statement
Call a set of distinct integers $1<n_1<\cdots<n_k$ a covering set if there is a choice of $a_i\pmod{n_i}$ for $1\leq i\leq k$ such that every integer satisfies at least one of these congruences. A set is an irreducible covering set if no proper subset is a covering set. How many irreducible covering sets of size $k$ are there? What is the minimum and maximum that $n_k$ can be? Determine or estimate $\max\sum\frac{1}{n_i}$, where the maximum ranges over all irreducible covering sets of size $k$. (Erdős also asked: are there infinitely many $n$ such that the divisors of $n$ greater than $1$ form an irreducible covering set? — this part is settled affirmatively; see background.)
Acceptance. FULLY RESOLVES: complete proofs determining, as functions of $k$: (i) the asymptotics of $\log I(k)$ (matching upper and lower bounds, sharpening the BBMST24 upper bound direction), (ii) the minimum and maximum possible value of $n_k$ over irreducible covering sets of size $k$, and (iii) the asymptotics of $\max\sum 1/n_i$ — machine-checkable (Lean/Coq) preferred, else full written proofs. The divisors question is already settled by Sun [Su07]; re-deriving it earns nothing. ADVANCES: exact computation of $I(k)$, the extremal values of $n_k$, and $\max\sum 1/n_i$ for all $k$ up to a stated bound $K$, by exhaustive search within Simpson's bound, with reproducible code and an exhaustiveness certificate (new data — none currently published; suitable for OEIS); a strict improvement of Simpson's $n_k\leq 2^{k-1}$ bound, or a matching lower-bound construction showing it is sharp (or not); a nontrivial lower bound on $I(k)$ growing faster than any bound stated in the background; or nontrivial upper bounds on $\max\sum 1/n_i$. Deliver the proof files, or the enumeration code plus verified tables.
Background
Asked by Erdős [Er80, p.95]; listed as open on erdosproblems.com/1189 (fetched 2026-07-13, status 'open', tagged 'number theory | covering systems'). Irreducibility is subtly stronger than the more usually studied minimality of covering systems: an irreducible covering set is the set of moduli of a minimal covering system, but not conversely, since irreducibility demands that no proper subset covers under ANY reassignment of residue classes. The divisors of $12$ exceeding $1$ form an irreducible covering set, and Sun [Su07] proved more generally that for every odd prime $p$ the divisors of $2^{p-1}p$ exceeding $1$ form an irreducible covering set — settling the final (divisors) question: infinitely many such $n$ exist. Simpson [Si85] proved that the largest element satisfies $n_k\leq 2^{k-1}$; consequently, for each fixed $k$ the irreducible covering sets of size $k$ form a finite, explicitly searchable family, and the counting and extremal questions are decidable by finite computation for each $k$. Writing $I(k)$ for the count, Balister, Bollobás, Morris, Sahasrabudhe, and Tiba [BBMST24] proved $$I(k)\leq \exp\left((c+o(1))\frac{k^{3/2}}{(\log k)^{1/2}}\right)$$ by showing the right-hand side is an asymptotic for the number of minimal covering systems on $k$ moduli. Trivially $\sum\frac{1}{n_i}>1$ for any irreducible covering set. The companion counting problem for minimal covering systems with bounded moduli is Erdős #1188 (erdosproblems.com/1188), posted alongside this one; the venue also hosts covering-system existence problems (Erdős #7, #273). No table of exact values of $I(k)$, of the extremal $n_k$, or of $\max\sum 1/n_i$ appears on the source page. The attacker's tools: exhaustive enumeration for small $k$ using Simpson's bound $n_k\leq 2^{k-1}$ to cap the search space (with pruning via $\sum 1/n_i>1$ and cheap coverability checks), producing certified exact values; and combinatorial constructions for lower bounds on $I(k)$ and on $\max\sum 1/n_i$.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #1189 (T. F. Bloom) | website |
| REF-02 | Erdős Problem #1188 — companion problem: counting minimal covering systems with bounded moduli | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.