On the Erdős covering problem: the density of the uncovered set (Q2118065)

Let \(A=a\mod d\) denote an arithmetic progression with difference/modulus \(d\). If a collection of \(k\) arithmetic progressions \(A_1,\dots, A_k\) covers all of the integers, that is, \(\bigcup_{i=1}^kA_i=\mathbb Z\), it is said to be a covering system. The study of covering systems was initiated by Erdős and continues to gain steam, with a number of significant recent results. If a finite set of moduli \(D=\{d_i\}\) cannot be used to generate a collection of progressions \(\{A_i\}\) covering all of \(\mathbb Z\), it is of interest to estimate the minimum density of the uncovered sets \(\mathbb Z\setminus\bigcup_iA_i\) in terms of the set \(D\). The following question was raised by \textit{M. Filaseta} et al. [J. Am. Math. Soc. 20, No. 2, 495--517 (2007; Zbl 1210.11020)] and serves to illustrate the point. \textbf{Question 1.} Is it true that for each \(C>0\), there exist constants \(M>0\) and \(\epsilon>0\) such that any collection of progressions \(\{A_i\}\) with \emph{distinct} moduli \(\{d_i\}\) satisfying \(d_i\ge M\) and \(\sum_i\dfrac1{d_i}<C\) will leave a set of density \(\ge\epsilon\) uncovered? The main aim of the paper under review is to develop a general method -- a specialized sieving technique -- for bounding the uncovered set. The authors point out that the aforementioned work of Filaseta et al. and the more recent breakthrough of \textit{B. Hough} [Ann. Math. (2) 181, No. 1, 361--382 (2015; Zbl 1344.11015)] were the inspiration for their research. It turns out that the answer to the stated question is in the negative, more on this below, but the main result of the paper is as follows. \textbf{Theorem 2.} Fix \(\epsilon>0\) and let \(\mu\) be the multiplicative function defined by \[ \mu(p^i)=1+\frac{(\log p)^{3+\epsilon}}p, \] for all primes \(p\) and integers \(i\ge1\). There exists \(M>0\) so that if \(A_1,\dots,A_k\) are arithmetic progressions with distinct moduli \(d_1,\dots,d_k\ge M\) and \(C=\sum_i\mu(d_i)/d_i\), then the density of the uncovered set \(\mathbb Z\setminus\bigcup_iA_i\) is at least \(e^{-4C}/2\). \textit{P. Erdős} asked [Summa Brasil. Math. 2, 113--123 (1950; Zbl 0041.36808)] whether there exist covering systems \(\{A_i\}\) with arbitrarily large distinct moduli \(\{d_i\}\)? This minimum modulus problem was finally settled in the aforementioned work of Hough, who showed that in every covering system with distinct moduli, the minimum modulus is at most \(10^{16}\). The new estimate on density of uncovered sets furnishes an independent proof of Hough's theorem. Moreover, the authors were able to lower the minimum modulus estimate of Hough to \(10^6\). Addressing the optimality of their function \(\mu\), the authors show that the analogue of Theorem 2 with their \(\mu\) replaced by the constant function \(\mu\equiv1\) (as in Question 1) or even weakening (1) to the condition \(\mu(p^i)=1+\frac{\lambda}p\), where \(\lambda>0\) is fixed, fails to hold. For example, they show that there are collections \(\{A_i\}\) with arbitrarily large distinct moduli \(\{d_i\}\) with \(\sum_i1/d_i<1\), such that the density of \(\mathbb Z\setminus\bigcup_iA_i\) is arbitrarily small. In addition to their results on uncovered sets, the authors were able to apply their new method to tackle several other long-standing open problems, and we conclude this review with a quick list of these. \textbf{Theorem 3} [Schinzel's conjecture]. In every covering system, one of the moduli divides another. \textbf{Theorem 4} [Square-free version of Erdős-Selfridge problem]. In a covering system with distinct square-free moduli, at least one of the moduli must be even. \textbf{Theorem 5} [On Erdős-Selfridge problem]. Let \(\{A_i\}\) be a covering system with distinct moduli \(\{d_i\}\) and put \(Q=\text{lcm}\{d_i\}\). Then \(Q\) must be divisible by either 2, or 9, or 15.