Erdős Problem #1188 — Minimal Distinct Covering Systems

At least 73 years old · documented by 1952

A congruence class $(n,a)$ represents the integers congruent to $a\pmod n$ , where $2\le n$ and $0\le a<n$ . A finite set of such classes is a minimal distinct covering system if every integer belongs to at least one class, no two classes have the same modulus, and no proper subset still covers all integers. Let $F(x)$ be the number of minimal distinct covering systems whose moduli satisfy $2\le n\le x$ . Estimate $F(x)$ . The conjectured estimate is

\frac{\log\!\bigl(\log F(x)\bigr)}{\log x}\longrightarrow 1\qquad (x\to\infty).

References

Primary source

The Formal Conjectures Authors, Formal Conjectures (2025); independently edited from the pinned source file.

Additional references

Pinned Formal Conjectures source, Apache-2.0.

covering-systems number-theory

InErdős Problems

Posted 2 months ago · edited 3 weeks ago

Progress summary

Refreshed 1 month ago

Claimed progress

The count is known to grow much faster than any polynomial, but no close estimate is known.

The problem asks for the growth of the number $F(x)$ of minimal distinct covering systems whose moduli are at most $x$ . Erdős posed a related counting question in 1952 and 1980; the minimal-system formulation is now treated as an alternative interpretation.

Known results

Hough, 2015: the minimum-modulus theorem implies $F(x)\to\infty$ .
An elementary construction gives $F(x)\gg\log x$ .
The trivial upper bound is $F(x)\leq\exp\big(O(x\log x)\big)$ .
A separate result counts systems by their number of members, not by the modulus cutoff $x$ .

2024 superpolynomial lower bound

Balister, Bollobás, Morris, Sahasrabudhe, and Tiba constructed enough systems to prove $F(x)\geq\exp\big((\log x)^{3-o(1)}\big)$ . Thus $F(x)$ grows faster than every polynomial, but no matching upper bound or complete asymptotic estimate has been reported.

Current status (as of June 2025): $F(x)$ is known to diverge and to satisfy a superpolynomial lower bound, while its sharp growth rate remains open.

Sources

No solutions have been posted yet.