The weight-function threshold in the Erdős covering problem: which multiplicative weights force a positive density of uncovered integers

Balister, Bollobás, Morris, Sahasrabudhe and Tiba (Inventiones mathematicae, 2022) proved that if the moduli of a finite system of arithmetic progressions are distinct and sufficiently large, and a weighted reciprocal sum $C=\sum_i \mu(d_i)/d_i$ is bounded, where $\mu$ is the multiplicative function with $\mu(p^i)=1+(\log p)^{3+\varepsilon}/p$, then the set of integers left uncovered has density at least $e^{-O(C)}$; they also proved that no such lower bound depending only on $C$ holds for $\mu(p^i)=1+\lambda/p$ for any fixed $\lambda>0$, nor for $\mu\equiv 1$. The paper explicitly poses the problem of characterizing the weight functions $\mu$ for which the bounded weighted sum forces a lower bound $\delta(C)>0$ on the uncovered density. The threshold growth of $\mu(p)-1$ between $\lambda/p$ and $(\log p)^{3+\varepsilon}/p$ remains undetermined.

Background

A covering system is a finite collection of arithmetic progressions $A_1,\dots,A_k$ of the integers, of the form $A_i=\{n\in\mathbb Z: n\equiv a_i \pmod{d_i}\}$, whose union is all of $\mathbb Z$; the integers $d_i$ are the moduli, and the system is distinct when they are pairwise different. Erdős introduced covering systems in 1950 and asked whether distinct moduli can all be arbitrarily large; Hough resolved this minimum modulus problem in 2015 by bounding the least modulus by an absolute constant (at most $10^{16}$ in his paper, later reduced to $616000$ by Balister, Bollobás, Morris, Sahasrabudhe and Tiba, hereafter BBMST). Erdős and Graham initiated the study of the density (natural density, i.e. the limit of the proportion of the uncovered integers in $[-x,x]$ as $x\to\infty$) of the set left uncovered when a collection of distinct-modulus progressions fails to cover: they conjectured that distinct moduli all lying in an interval $[n,Cn]$ with $n$ large must leave a set of uncovered integers of density bounded below by a constant depending only on $C$. Filaseta, Ford, Konyagin, Pomerance and Yu (2007) proved this in a strong form and asked the natural strengthening: if all distinct moduli are at least some $M$ and $\sum_i 1/d_i < C$, must the uncovered set have density at least some $\varepsilon(C)>0$? Here a multiplicative weight means a function $\mu$ on the positive integers with $\mu(mn)=\mu(m)\mu(n)$ whenever $\gcd(m,n)=1$; such a function is determined by its values on prime powers. BBMST (arXiv 2018; Inventiones mathematicae 228 (2022) 377–414) answered the Filaseta–Ford–Konyagin–Pomerance–Yu question negatively: for every $M$ and $\varepsilon>0$ there are progressions with distinct (square-free) moduli at least $M$, with $\sum_i 1/d_i<1$, whose uncovered set has density below $\varepsilon$. Their main positive theorem uses the distortion method (a refinement of Hough's technique, in which a sequence of probability measures is revealed prime by prime and re-weighted so as to concentrate on the uncovered set): if $\mu(p^i)=1+(\log p)^{3+\varepsilon}/p$ for all primes $p$ and $i\ge 1$, then for all sufficiently large minimum modulus the uncovered set has density at least $e^{-O(C)}$, where $C=\sum_i \mu(d_i)/d_i$. However, they also showed the theorem is close to best possible: replacing the weight by $\mu(p^i)=1+\lambda/p$ for any fixed $\lambda>0$ destroys the conclusion, in the strong sense that for some $C(\lambda)$ and every $M$ and $\varepsilon>0$ there are families with distinct square-free moduli at least $M$ and weighted sum at most $C(\lambda)$ whose uncovered set has density below $\varepsilon$. So there is a gap of roughly $(\log p)^{3+\varepsilon}$ versus a constant factor in the per-prime excess $\mu(p)-1$, measured in units of $1/p$, and the paper states it would be extremely interesting to characterize the weights $\mu$ for which the conclusion survives.

Problem Statement

Call a multiplicative function $\mu:\mathbb N\to[1,\infty)$ admissible if for every $C>0$ there exist constants $M>0$ and $\delta=\delta(C)>0$ such that the following holds: whenever $A_1,\dots,A_k$ are arithmetic progressions with distinct moduli $d_1,\dots,d_k$ all at least $M$ and $\sum_{i=1}^k \mu(d_i)/d_i \le C$, the set of uncovered integers $\mathbb Z\setminus\bigcup_{i=1}^k A_i$ has natural density at least $\delta$. Characterize the admissible multiplicative functions $\mu$; this general characterization is the required target, and the concrete questions that follow are illustrative examples. In particular, the threshold growth of the per-prime excess $\mu(p)-1$ (measured in units of $1/p$) is the central case: BBMST proved that $\mu(p^i)=1+(\log p)^{3+\varepsilon}/p$ is admissible for every $\varepsilon>0$ (with uncovered density at least $e^{-O(C)}$), while $\mu(p^i)=1+\lambda/p$ is not admissible for any fixed $\lambda>0$. The question includes determining for which exponents $\gamma$ the weight $\mu(p^i)=1+(\log p)^{\gamma}/p$ is admissible, whether logarithmic factors smaller than any power of $\log p$ (such as $\log\log p$) suffice or fail, and whether the two bounds exhibited above — the admissible weight $\mu(p^i)=1+(\log p)^{3+\varepsilon}/p$ and the non-admissible weights $\mu(p^i)=1+\lambda/p$ — can be sharpened to meet. This is the problem posed explicitly by Balister, Bollobás, Morris, Sahasrabudhe and Tiba immediately after their Theorem 1.1 and their constructions in Section 10 of 'On the Erdős covering problem: the density of the uncovered set'.

References

1. Paul Balister, Béla Bollobás, Robert Morris, Julian Sahasrabudhe, Marius Tiba, 'On the Erdős covering problem: the density of the uncovered set', Inventiones mathematicae 228 (2022), 377–414. DOI 10.1007/s00222-021-01087-5, https://doi.org/10.1007/s00222-021-01087-5 (preprint arXiv:1811.03547, https://arxiv.org/abs/1811.03547)
2. Michael Filaseta, Kevin Ford, Sergei Konyagin, Carl Pomerance, Gang Yu, 'Sieving by large integers and covering systems of congruences', Journal of the American Mathematical Society 20 (2007), 495–517. DOI 10.1090/s0894-0347-06-00549-2, https://doi.org/10.1090/s0894-0347-06-00549-2
3. Bob Hough, 'Solution of the minimum modulus problem for covering systems', Annals of Mathematics (2) 181 (2015), 361–382. DOI 10.4007/annals.2015.181.1.6, https://doi.org/10.4007/annals.2015.181.1.6
4. Robert Hough, Pace P. Nielsen, 'Covering systems with restricted divisibility', Duke Mathematical Journal 168 (2019), 3261–3295. DOI 10.1215/00127094-2019-0058, https://doi.org/10.1215/00127094-2019-0058 (preprint arXiv:1703.02133, https://arxiv.org/abs/1703.02133)
5. Paul Erdős, 'On integers of the form 2^k+p and some related problems', Summa Brasiliensis Mathematicae 2 (1950), 113–123. zbMATH 0041.36808, https://zbmath.org/?q=an%3A0041.36808
6. Paul Erdős, Ronald L. Graham, 'Old and new problems and results in combinatorial number theory', Monographies de L'Enseignement Mathématique 28, Genève, 1980. zbMATH 0434.10001, https://zbmath.org/?q=an%3A0434.10001
7. Paul Balister, Béla Bollobás, Robert Morris, Julian Sahasrabudhe, Marius Tiba, 'The Erdős–Selfridge problem with square-free moduli', Algebra & Number Theory 15 (2021), 609–626. DOI 10.2140/ant.2021.15.609, https://doi.org/10.2140/ant.2021.15.609 (preprint arXiv:1901.11465, https://arxiv.org/abs/1901.11465)
8. Paul Balister, Béla Bollobás, Robert Morris, Julian Sahasrabudhe, Marius Tiba, 'The structure and number of Erdős covering systems', Journal of the European Mathematical Society (2023). DOI 10.4171/jems/1357, https://doi.org/10.4171/jems/1357 (preprint arXiv:1904.04806, https://arxiv.org/abs/1904.04806)
9. Paul Balister, Béla Bollobás, Robert Morris, Julian Sahasrabudhe, Marius Tiba, 'Erdős covering systems', Acta Mathematica Hungarica 161 (2020), 540–549. DOI 10.1007/s10474-020-01048-z, https://doi.org/10.1007/s10474-020-01048-z (expository note also at arXiv:2211.01417, https://arxiv.org/abs/2211.01417)
10. Paul Balister, 'Erdős Covering Systems', in Surveys in Combinatorics 2024, London Mathematical Society Lecture Note Series, Cambridge University Press, 2024. DOI 10.1017/9781009490559.003, https://doi.org/10.1017/9781009490559.003
11. Michael Filaseta, Alexandros Kalogirou, 'Covering systems with the sum of the reciprocals of the moduli close to 1', Transactions of the American Mathematical Society (2026). DOI 10.1090/tran/9670, https://doi.org/10.1090/tran/9670 (preprint arXiv:2407.15280, https://arxiv.org/abs/2407.15280)
12. Jonah Klein, Dimitris Koukoulopoulos, Simon Lemieux, 'On the jth smallest modulus of a covering system with distinct moduli', International Journal of Number Theory 20 (2024). DOI 10.1142/s1793042124500234, https://doi.org/10.1142/s1793042124500234 (preprint arXiv:2212.01299, https://arxiv.org/abs/2212.01299)
13. Maria Cummings, Michael Filaseta, Ognian Trifonov, 'An upper bound for the minimum modulus in a covering system with squarefree moduli', Acta Mathematica Hungarica 175 (2025), 1–25. DOI 10.1007/s10474-024-01496-x, https://doi.org/10.1007/s10474-024-01496-x (preprint arXiv:2211.08548, https://arxiv.org/abs/2211.08548)
14. Chris Bispels, Matthew Cohen, Joshua Harrington, Joshua Lowrance, Kaelyn Pontes, Leif Schaumann, Tony W. H. Wong, 'A further investigation on covering systems with odd moduli', Discrete Mathematics (2026). DOI 10.1016/j.disc.2026.115013, https://doi.org/10.1016/j.disc.2026.115013 (preprint arXiv:2507.16135, https://arxiv.org/abs/2507.16135)
15. Ibrahim Mian, Shayaan Siddique, 'Kernel-Checked Exclusions for the Erdős–Selfridge Odd Covering Problem: Any Odd Covering of $\mathbb{Z}$ Has lcm Exceeding 10000', arXiv:2607.25628 (2026), https://arxiv.org/abs/2607.25628