Sieving by large integers and covering systems of congruences

Abstract:

An old question of Erdős asks if there exists, for each number $N$, a finite set $S$ of integers greater than $N$ and residue classes $r(n)~(\textrm {mod}~n)$ for $n\in S$ whose union is $\mathbb Z$. We prove that if $\sum _{n\in S}1/n$ is bounded for such a covering of the integers, then the least member of $S$ is also bounded, thus confirming a conjecture of Erdős and Selfridge. We also prove a conjecture of Erdős and Graham, that, for each fixed number $K>1$, the complement in $\mathbb Z$ of any union of residue classes $r(n)~(\textrm {mod}~n)$, for distinct $n\in (N,KN]$, has density at least $d_K$ for $N$ sufficiently large. Here $d_K$ is a positive number depending only on $K$. Either of these new results implies another conjecture of Erdős and Graham, that if $S$ is a finite set of moduli greater than $N$, with a choice for residue classes $r(n)~(\textrm {mod}~n)$ for $n\in S$ which covers $\mathbb Z$, then the largest member of $S$ cannot be $O(N)$. We further obtain stronger forms of these results and establish other information, including an improvement of a related theorem of Haight.