Count minimal covering systems with all moduli at most $x$: estimate $F(x)$ (Erdős #1188)
Statement
Call a set of distinct integers $1<n_1<\cdots<n_k$ with associated congruence classes $a_i\pmod{n_i}$ a distinct covering system if every integer satisfies at least one of these congruences. A minimal distinct covering system is one such that no proper subset forms a covering system. Let $F(x)$ count the number of minimal distinct covering systems with all moduli in $[1,x]$. Estimate $F(x)$.
Acceptance. FULLY RESOLVES: determine the growth rate of $\log F(x)$ — matching upper and lower bounds giving $\log F(x)$ up to a $(1+o(1))$ factor, or at minimum identifying its order (e.g. proving $\log F(x)=(\log x)^{c+o(1)}$ or $\log F(x)=x^{\theta+o(1)}$ with the exponent identified), with a complete proof — machine-checkable (Lean/Coq) preferred, else a full written proof. ADVANCES: strictly improve either bound stated in the background (lower bound above $\exp((\log x)^{3-o(1)})$, or upper bound below $\exp(O(x\log x))$), with proof; OR compute $F(x)$ exactly for all $x$ up to a stated bound via exhaustive enumeration, with reproducible code and an exhaustiveness certificate (new sequence data — none currently published); analogous new bounds or exact values for the companion count $G(x)$ of irreducible covering sets. Deliver the proof file, or the enumeration code plus the verified table of initial values.
Background
Asked by Erdős [Er80, p.95]; listed as open on erdosproblems.com/1188 (fetched 2026-07-13, status 'open', tagged 'number theory | covering systems'). Erdős originally posed the count without the minimality restriction, but that version is trivial: any system containing a fixed covering system still covers, giving $\gg 2^x$ systems, so minimality is the right normalisation. Erdős expected $F(x)\to\infty$ 'very slowly'. The known frontier says otherwise. That $F(x)\to\infty$ at all follows from Hough's solution of the minimum modulus problem (Erdős #2, erdosproblems.com/2) [Ho15], and van Doorn observed an elementary lower bound $F(x)\gg\log x$. Far stronger: the lower-bound construction of Balister, Bollobás, Morris, Sahasrabudhe, and Tiba [BBMST24] yields at least $\exp(k^{3+o(1)})$ minimal distinct covering systems with all moduli at most $\prod_{p<k}p=e^{(1+o(1))k}$, hence $$F(x)\geq \exp\left((\log x)^{3-o(1)}\right),$$ so $F(x)$ grows faster than any polynomial — likely contradicting Erdős's 'very slowly' guess (unless he meant the number of possible moduli sets). The trivial upper bound is $$F(x)\leq \exp(O(x\log x)),$$ leaving an enormous gap. Erdős also asked in [Er80] to estimate the number $G(x)$ of irreducible covering sets with moduli in $[1,x]$ (moduli sets containing no proper subset that covers under any choice of residues); trivially $G(x)\leq F(x)$ — that companion question is Erdős #1189 (erdosproblems.com/1189), whose SciNet version is posted alongside this one. The venue also hosts existence-flavoured covering problems (all moduli odd, Erdős #7; moduli of the form $p-1$, Erdős #273). No table of exact values of $F(x)$ appears on the source page or in the cited literature. The attacker's tools: exhaustive enumeration of minimal distinct covering systems for small $x$ (the moduli set is a subset of $[2,x]$ and coverability checks are cheap, so certified exact values of $F(x)$ for an initial range are within reach and would be new data, suitable for OEIS), plus the combinatorial/analytic machinery of BBMST24 for narrowing the gap between the two bounds.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #1188 (T. F. Bloom) | website |
| REF-02 | Erdős Problem #2 — the minimum modulus problem (solved by Hough), whose solution implies F(x) → ∞ | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.