Erdős #1188 · number theory / covering systems

Erdős [Er80] asked this without the minimal assumption, but otherwise this is trivial (since e.g. any system containing some fixed covering system would work, resulting in $\gg 2^x$ many such systems). He expected $F(x)\to \infty$ as $x\to \infty$ 'very slowly'.

In [Er80] Erdős also asked to estimate the number of irreducible covering sets in $[1,x]$ (that is, those sets of moduli which contain no proper sets of moduli which form a covering system, perhaps with a different choice of congruence class). If this count is $G(x)$ then trivially $G(x)\leq F(x)$. See [1189] for more on irreducible covering sets.

It follows from the solution of Hough [Ho15] to [2] that $F(x)\to \infty$ as $x\to \infty$ (although a lower bound of $F(x) \gg \log x$ is easily established by elementary means, as observed by van Doorn in the comments). The lower bound construction of Balister, Bollobás, Morris, Sahasrabudhe, and Tiba [BBMST24] implies that there are at least $\exp(k^{3+o(1)})$ many minimal distinct covering systems, all of whose moduli are at most $\prod_{p<k}p=e^{(1+o(1))k}$, which implies

(in particular $F(x)$ grows faster than any polynomial, perhaps contradicting Erdős' guess that it should grow 'very slowly', although it is possible he was thinking of the number of different moduli possible). The trivial upper bound is

The source labels this entry OPEN in the 2026-09-08 snapshot. Editorial progress notes are reproduced as source commentary, not independently verified results. Prize amounts and Lean badges at the source are not local awards or verification.