Long gaps in sieved sets

  • Kevin Ford

    University of Illinois at Urbana-Champaign, USA
  • Sergey Konyagin

    Steklov Mathematical Institute, Moscow, Russia
  • James Maynard

    University of Oxford, UK
  • Carl B. Pomerance

    Dartmouth College, Hanover, USA
  • Terence Tao

    University of California, Los Angeles, USA
Long gaps in sieved sets cover
Download PDF

This article is published open access under our Subscribe to Open model.


For each prime pp, let IpZ/pZI_p \subset \mathbb{Z}/p\mathbb{Z} denote a collection of residue classes modulo pp such that the cardinalities Ip|I_p| are bounded and about 1 on average. We show that for sufficiently large xx, the sifted set {nZ:n(modp)∉Ipforallpx}\{n \in \mathbb{Z}: n (\mathrm {mod}\: p) \not \in I_p \: \mathrm {for \: all} p \leq x\} contains gaps of size x(logx)δx (\log x)^{\delta} depends only on the densitiy of primes for which IpI_p \neq \emptyset. This improves on the "trivial'' bound of x\gg x. As a consequence, for any non-constant polynomial f:ZZf: \mathbb{Z} \to \mathbb{Z} with positive leading coefficient, the set {nX:f(n)  composite}\{n \leq X: f(n) \; \mathrm {composite}\} contains an interval of consecutive integers of length (logX)(loglogX)δ\ge (\log X) (\log\log X)^{\delta} for sufficiently large XX, where δ>0\delta > 0 depends only on the degree of ff.

Cite this article

Kevin Ford, Sergey Konyagin, James Maynard, Carl B. Pomerance, Terence Tao, Long gaps in sieved sets. J. Eur. Math. Soc. 23 (2021), no. 2, pp. 667–700

DOI 10.4171/JEMS/1020