Long gaps in sieved sets (Q2659444)

The paper proves that sifted sets contain large gaps. To make this precise, let \(I_p\subset {\mathbb Z}/p{\mathbb Z}\) be a sieving system which is nondegenerate (so \(|I_p|\le p-1\) for all primes \(p\)), bounded (so \(|I_p|\le B\) for some fixed \(B\) and all primes \(p\)), one dimensional (so \(\prod_{p\le x} (1-|I_p|/p)\sim C_1/\log x\) for some positive constant \(C_1\) as \(x\) tends to infinity), and \(\rho\)-supported, meaning that the relative density of the set of primes \(p\) with \(|I_p|\ge 1\) is \(\rho(>0)\). Then the main theorem says that the sifted set \({\mathbb Z}-\bigcup_{p\le x} I_p\) contains gaps of size at least \(x/(\log x)^{C(\rho)}\), where \(C(\rho)>e^{-1-1/4/\rho}\) is an explicit constant indicated in the paper. The main result has several interesting corollaries concerning strings of consecutive natural numbers for which a given polynomial \(f(x)\in {\mathbb Z}[x]\) is composite. For example, if \(f\) is irreducible, of degree \(d\ge 2\) with full symmetric Galois group \(S_d\), then for large \(X\) there is a string of consecutive natural numbers \(n\in [1,X]\) of length \(>(\log X)(\log\log X)^{1/6001}\) for which \(f(n)\) is composite. The proof uses the Chinese Remainder Theorem and a greedy sieving strategy based on a hypergraph covering lemma of their own inspired by a result from [\textit{A. C. Cojocaru} and \textit{M. R. Murty}, An introduction to sieve methods and their applications. Cambridge: Cambridge University Press (2006; Zbl 1121.11063)], which the authors prove in the appendix.