for sufficiently large $X$, improving upon recent bounds of the first, second, third, and fifth authors and of the fourth author. Our main new ingredient is a generalization of a hypergraph covering theorem of Pippenger and Spencer, proven using the Rödl nibble method.
1. Introduction
Let $p_n$ denote the $n^{\operatorname {th}}$ prime, and let
as the average gap between the prime numbers which are $\leqslant X$ is $\sim \log X$. In 1931, Westzynthius Reference 46 proved that infinitely often, the gap between consecutive prime numbers can be an arbitrarily large multiple of the average gap, that is, $G(X)/\log X\to \infty$ as $X\to \infty$, improving upon prior results of Backlund Reference 2 and Brauer-Zeitz Reference 5. Moreover, he proved the quantitative boundFootnote1
1
As usual in the subject, $\log _2 x = \log \log x$,$\log _3 x = \log \log \log x$, and so on. The conventions for asymptotic notation such as $\ll$ and $o()$ will be defined in Section 2.
$$\begin{equation*} G(X) \gg \frac{\log X \log _2X}{(\log _3X)^2}, \end{equation*}$$
and in 1938 Rankin Reference 40 made a subsequent improvement
$$\begin{equation*} G(X) \geqslant (c + o(1)) \frac{\log X \log _2 X \log _4 X}{(\log _3 X)^2} \end{equation*}$$
with $c = \frac{1}{3}$. The constant $c$ was increased several times: to $\frac{1}{2}e^{\gamma }$ by Schönhage Reference 43, then to $c = e^{\gamma }$ by Rankin Reference 41, to $c = 1.31256 e^{\gamma }$ by Maier and Pomerance Reference 32, and, most recently, to $c = 2e^{\gamma }$ by Pintz Reference 36.
Recently, in two independent papers Reference 13Reference 35, the authors lshowed that $c$ could be taken to be arbitrarily large, answering in the affirmative a long-standing conjecture of Erdős Reference 12. The methods of proof in Reference 13 and Reference 35 both introduced estimates on primes in very short arithmetic progressions, but these differed in some key aspects. The arguments in Reference 13 used recent results Reference 21Reference 22Reference 23 on the number of solutions to linear equations in primes, whereas the arguments in Reference 35 instead relied on multidimensional prime-detecting sieves introduced in Reference 33. Our main theorem is the following quantitative improvement.
Our overall approach combines ideas from the two previous papers Reference 13Reference 35. There are two key ingredients which allow us to obtain the quantitative improvement. First, we incorporate a uniform version of the multidimensional sieve approach as worked out in Reference 34, which gives a quantitative improvement to the underlying estimates about primes. Second, we prove a generalization of a hypergraph covering theorem of Pippenger and Spencer Reference 37, which allows for an essentially optimal means of translating such estimates into a result on large gaps between primes. It is this covering theorem which is the key new ingredient in our work and may be of independent interest.
All approaches which obtain quantitative improvements beyond the average bound $G(X)\gg \log {X}$ have used a sieving argument which is conjectured to be unable to produce a result stronger than $G(X)\gg \log {X} (\log _2{X})^{2+o(1)}$. Moreover, in light of the essentially optimal bounds in our covering theorem for this problem and the current limitations of the multidimensional sieve estimates, Theorem 1 appears to be the strongest result one can hope to prove without improvements toward the Hardy-Littlewood prime $k$-tuples conjecture, or a radically new approach.
In a sequel Reference 15 to this paper, a subset of the authors will extend the above theorem to also cover chains of consecutive large gaps between primes, by combining the methods in this paper with the Maier matrix method. In view of this, we have written some of the key propositions in this paper in slightly more generality than is strictly necessary to prove Theorem 1, as the more general versions of these results will be useful in the sequel Reference 15.
The results and methods of this paper have also subsequently been applied by Maier and Rassias Reference 31 (extending the method of the first author, Heath-Brown, and the third author Reference 14) to obtain large prime gaps (of the order of that in Theorem 1) that contain a perfect $k^{\operatorname {th}}$ power of a prime for a fixed $k$, and by Baker and Freiberg Reference 3 to obtain lower bounds on the density of limit points of prime gaps normalized by any function that grows slightly more slowly than the one in Theorem 1. We refer the interested reader to these papers for further details.
1.1. Historical background
Based on a probabilistic model of primes, Cramér Reference 8 conjectured that
Granville Reference 20 offered a refinement of Cramér’s model and has conjectured that the $\limsup$ above is in fact at least $2e^{-\gamma }=1.1229\ldots$. These conjectures are well beyond the reach of our methods. Cramér’s model also predicts that the normalized prime gaps $\frac{p_{n+1}-p_n}{\log p_n}$ should have exponential distribution, that is, $p_{n+1}-p_n \geqslant C\log p_n$ for about $e^{-C}\pi (X)$ primes $\leqslant X$, for any fixed $C>0$. Numerical evidence from prime calculations up to $4\cdot 10^{18}$Reference 44 matches this prediction quite closely, with the exception of values of $C$ close to $\log X$, for which there are very little data available. In fact, $\max _{X\leqslant 4\cdot 10^{18}} G(X)/\log ^2 X \approx 0.9206$, slightly below the predictions of Cramér and Granville.
Unconditional upper bounds for $G(X)$ are far from the conjectured truth, the best being $G(X) \ll X^{0.525}$ and due to Baker, Harman, and Pintz Reference 4. Even the Riemann hypothesisFootnote2 furnishes only the bound $G(X)\ll X^{1/2}\log X$Reference 7.
2
Some slight improvements are available if one also assumes some form of the pair correlation conjecture; see Reference 26.
All works on lower bounds for $G(X)$ have followed a similar overall plan of attack: they show that there are at least $G(X)$ consecutive integers in $(X/2,X]$, each of which has a “very small” prime factor. To describe the results, we make the following definition.
The relation between this function $Y$ and gaps between primes is encoded in the following simple lemma.
By the prime number theorem we have $P(x) = e^{(1 + o(1))x}$. Thus the bound of Lemma 1.1 implies that
$$G(X) \geqslant Y\big ((1 + o(1)) \log X\big )$$
as $X \to \infty$. In particular, Theorem 1 is a consequence of the bound
which we will establish later in this paper. This improves on the bound $Y(x) \gg \frac{x \log x\log _3 x}{\log _2^2 x}$ obtained by Rankin Reference 40.
The function $Y$ is intimately related to Jacobsthal’s function$j$. If $n$ is a positive integer, then $j(n)$ is defined to be the maximal gap between integers coprime to $n$. In particular $j(P(x))$ is the maximal gap between numbers free of prime factors $\leqslant x$, or equivalently $1$ plus the longest string of consecutive integers, each divisible by some prime $p \leqslant x$. The Chinese remainder theorem construction given in the proof of Lemma 1.1 in fact proves that
This observation, together with results in the literature, gives upper bounds for $Y$. The best upper bound known is $Y(x) \ll x^2$, which comes from Iwaniec’s work Reference 28 on Jacobsthal’s function. It is conjectured by Maier and Pomerance that in fact $Y(x) \ll x (\log x)^{2 + o(1)}$. This places a serious (albeit conjectural) upper bound on how large gaps between primes we can hope to find via lower bounds for $Y(x)$: a bound in the region of $G(X) \gtrapprox \log X (\log \log X)^{2 + o(1)}$, far from Cramér’s conjecture, appears to be the absolute limit of such an approach.
The lower bound on certain values of Jacobsthal’s function provided by Equation 1.1, Equation 1.2 can be inserted directly into Reference 39, Theorem 1 to obtain a lower bound for the maximum over $l$ of $p(k,l)$, the least prime in the arithmetic progression $l\bmod k$, in the case when the modulus $k$ has no small prime factors. We have the following corollary.
In view of Reference 39, Theorem 3, one may also expect to be able to prove a lower bound of the form
$$\begin{equation} M(k) \gg \phi (k) \frac{\log k \log _2 k \log _4 k}{\log _3 k} \cssId{Mk}{\tag{1.3}} \end{equation}$$
for a set of natural numbers $k$ of density $1$, but we were unable to find a quick way to establish this from the results in this paper.Footnote3
3
Inequality Equation 1.3 has recently been established by Li, Pratt, and Shakan Reference 30 for every positive integer $k$ except those with more than $\exp \{(1/2-\varepsilon )\log _2 k \log _4 k/\log _3 k \}$ prime factors, $\varepsilon >0$ fixed.
Our methods here are a combination of those in our previous papers Reference 13Reference 35, which are in turn based in part on arguments in earlier papers, particularly those of Rankin Reference 40 and Maier-Pomerance Reference 32. In order to make the lower bound in Theorem 1 as efficient as possible, we combine these ideas with a generalization of some arguments of Pippenger and Spencer Reference 37.
As noted above, to prove Theorem 1, it suffices to sieve out an interval $[y]$ by residue classes $a_p \bmod p$ for each prime $p \leqslant x$, where $y \asymp \frac{x \log x \log _3 x}{\log _2 x}$. Actually, it is permissible to have $O(\frac{x}{\log x})$ survivors in $[y]$ that are not sieved out by these residue classes, since one can easily eliminate such survivors by increasing $x$ by a constant multiplicative factor. Also, for minor technical reasons, it is convenient to sieve out $[y] \backslash [x]$ rather than $[y]$.
Following Reference 13, we will sieve out $[y] \backslash [x]$ by the residue classes $0 \bmod p$ for both very small primes $p$($p \leqslant \log ^{20} x$) and medium primes $p$ (between $z \coloneq x^{\log _3 x/(4\log _2 x)}$ and $x/2$). The survivors of this process are essentially the set $\mathcal{Q}$ of primes between $x$ and $y$. After this initial sieving, the next stage will be to randomly sieve out residue classes $\mathbf{\tilde{a}} = (\mathbf{a}_s \bmod s)_{s \in \mathcal{S}}$ for small primes $s$ (between $\log ^{20} x$ and $z$). (This approach differs slightly from the approach taken in Reference 35 and earlier papers, in which a fixed residue class is used for all small (and very small) primes instead.) This cuts down the set of primes $\mathcal{Q}$ to a smaller set $\mathcal{Q}\cap S(\mathbf{\tilde{a}})$, whose cardinality is typically on the order of $\frac{x}{\log x} \log _2 x$. The remaining task is then to select integers $n_p$ for each prime $p$ between $x/2$ and $x$, such that the residue classes $n_p \bmod p$ cut down $\mathcal{Q}\cap S(\mathbf{\tilde{a}})$ to a set of survivors of size $O( \frac{x}{\log x})$.
Assuming optimistically that one can ensure that the different residue classes $n_p \bmod p$ largely remove disjoint sets from $\mathcal{Q}\cap S(\mathbf{\tilde{a}})$, we are led to the need to select the integers $n_p$ so that each $n_p \bmod p$ contains about $\log _2 x$ of the primes in $\mathcal{Q}\cap S(\mathbf{\tilde{a}})$. In Reference 13, the approach taken was to use recent results on linear equations in primes Reference 21Reference 22Reference 23 to locate arithmetic progressions $q, q+r! p, \dots , q+(r-1)r!p$ consisting entirely of primes for some suitable $r$, and then to take $n_p = q$. Unfortunately, due to various sources of ineffectivity in the known results on linear equations in primes, this method only works when $r$ is fixed or growing extremely slowly in $x$, whereas here we would need to take $r$ of the order of $\log _2 x$. To get around this difficulty, we use instead the methods from Reference 35, which are based on the multidimensional sieve methods introduced in Reference 33 to obtain bounded intervals with many primes. A routine modification of these methods gives tuples $q+h_1 p, \dots , q+h_k p$ which contain $\gg \log k$ primes, for suitable large $k$; in fact, by using the calculations in Reference 34, one can take $k$ as large as $\log ^c x$ for some small absolute constant $c$ (e.g. $c=1/5$), so that the residue class $q \bmod p$ is guaranteed to capture $\gg \log _2 x$ primes in $\mathcal{Q}$.
There is, however, a difficulty due to the overlap between the residue classes $n_p \bmod p$. In both of the previous papers Reference 13Reference 35, the residue classes were selected randomly and independently of each other, but this led to a slight inefficiency in the sieving: with each residue class $n_p \bmod p$ containing approximately $\log _2 x$ primes, probabilistic heuristics suggest that one would have needed the original survivor set $\mathcal{Q}\cap S(\mathbf{\tilde{a}})$ to have a size about $\frac{x}{\log x} \frac{\log _2 x}{\log _3 x}$ rather than $\frac{x}{\log x} \log _2 x$ if one is to arrive at $O( \frac{x}{\log x} )$ after the final sieving process. This ultimately leads to the bound
as worked out in unpublished work of the fourth author—an additional loss of $\log _4 x$ compared to Theorem 1.
To avoid this difficulty, we use some ideas from the literature on efficient hypergraph covering. Of particular relevance is the work of Pippenger and Spencer Reference 37 in which it is shown that whenever one has a large hypergraph $G = (V,E)$ which is uniform both in the sense of edges $e \in E$ having constant cardinality and also in the sense of the degrees $\# \{ e \in E: v \in e \}$ being close to constant in $v$, one can efficiently cover most of $V$ by almost disjoint edges in $E$. Unfortunately, the results in Reference 37 are not directly applicable for a number of technical reasons, the most serious of which is that the analogous hypergraph in this case (in which the vertices are the sifted set $\mathcal{Q}\cap S(\mathbf{\tilde{a}})$ and the edges are sets of the form $\{ q \in \mathcal{Q}\cap S(\mathbf{\tilde{a}}): q \equiv n_p \mkern 7mu(\mathrm{mod}\,\,p) \}$ for various $n_p,p$) does not have edges of constant cardinality. However, by modifying the “Rödl nibble” or “semi-random” method used to prove the Pippenger-Spencer theorem, we are able to obtain a generalization of that theorem in which the edges are permitted to have variable cardinality. This generalization is purely combinatorial in nature and may be of independent interest beyond the application here to large prime gaps.
We will make a series of reductions to prove Theorem 1. To aid the reader, we summarize the chain of implications below, indicating in which section each implication or theorem is proven (above or below), and in which section one may find a statement of each theorem (in parentheses),
The deduction of Theorem 1 from Theorem 2 is easy and codifies the reduction of the problem to that of finding residue classes for primes in $S \cup (x/2,x]$ which cover all the primes in $\mathcal{Q}$ with $O(x/\log x)$ exceptions. Theorem 5, proved using the sieve methods from Reference 34, postulates the existence of a weight function with certain average properties. It implies the existence of residue classes $n_p \bmod p$ for primes $p\in (x/2,x]$, each containing many primes of $Q$, and moreover that each prime $q\in \mathcal{Q}\cap S(\mathbf{\tilde{a}})$ is covered by about the same number of these congruence classes $n_p\bmod p$. These properties are quantified in Theorem 4. Showing that Theorem 4 implies Theorem 2, i.e. that there exist choices for $n_p$ which efficiently cover most of the primes in $q\in \mathcal{Q}\cap S(\mathbf{\tilde{a}})$, is accomplished with our new hypergraph covering tool. The fundamental result is Theorem 3, which is written in a very general form and is consequently rather long to state. Corollary 4 is a somewhat shorter version specialized for our purposes.
For ease of reading, we have endeavored to separate the combinatorial arguments of Sections 4, 5, and 6 from the number theoretic arguments of Sections 7 and 8. Indeed, a reader only interested in our hypergraph covering result Theorem 3 can read Sections 4 and 5 as a stand-alone paper. A reader only interested in the number theoretic part of Theorem 1 can just read Sections 7 and 8 provided they are willing to assume the reduction of Theorem 2 to Theorem 5. The deduction of Theorem 2 from the purely combinatorial Corollary 4 and the purely number theoretic Theorem 5 is performed in the second half of Section 4 and in Section 6, and does not require reading the more specialized Section 5, 7, or 8.
2. Notational conventions
In most of the paper, $x$ will denote an asymptotic parameter going to infinity, with many quantities allowed to depend on $x$. The symbol $o(1)$ will stand for a quantity tending to zero as $x \to \infty$. The same convention applies to the asymptotic notation $X \sim Y$, which means $X=(1+o(1))Y$. We use $X = O(Y)$,$X \ll Y$, and $Y \gg X$ to denote the claim that there is a constant $C>0$ such that $|X| \leqslant CY$ throughout the domain of the quantity $X$. We adopt the convention that $C$ is independent of any parameter unless such dependence is indicated, e.g. by subscript such as $\ll _k$. In all of our estimates here, the constant $C$ will be effective (we will not rely on ineffective results such as Siegel’s theorem). If we can take the implied constant $C$ to equal $1$, we write $f = O_{\leqslant }(g)$ instead. Thus for instance
$$X = (1 + O_{\leqslant }(\varepsilon )) Y$$
is synonymous with
$$(1-\varepsilon ) Y \leqslant X \leqslant (1+\varepsilon ) Y.$$
Finally, we use $X \asymp Y$ synonymously with $X \ll Y \ll X$.
When summing or taking products over the symbol $p$, it is understood that $p$ is restricted to be prime.
Given a modulus $q$ and an integer $n$, we use $n \bmod q$ to denote the congruence class of $n$ in $\mathbb{Z}/q\mathbb{Z}$.
Given a set $A$, we use $1_A$ to denote its indicator function, and thus $1_A(x)$ is equal to $1$ when $x \in A$ and zero otherwise. Similarly, if $E$ is an event or statement, we use $1_E$ to denote the indicator, equal to $1$ when $E$ is true and $0$ otherwise. Thus for instance $1_A(x)$ is synonymous with $1_{x \in A}$.
We use $\# A$ to denote the cardinality of $A$, and for any positive real $z$, we let $[z] \coloneq \{ n \in \mathbf{N}: 1 \leqslant n \leqslant z \}$ denote the set of natural numbers up to $z$.
Our arguments will rely heavily on the probabilistic method. Our random variables will mostly be discrete (in the sense that they take at most countably many values), although we will occasionally use some continuous random variables (e.g. independent real numbers sampled uniformly from the unit interval $[0,1]$). As such, the usual measure-theoretic caveats such as “absolutely integrable,” “measurable,” or “almost surely” can largely be ignored by the reader in the discussion below. We will use boldface symbols such as $\mathbf{X}$ or $\mathbf{a}$ to denote random variables (and non-boldface symbols such as $X$ or $a$ to denote deterministic counterparts of these variables). Vector-valued random variables will be denoted in arrowed boldface, e.g. $\vec{\mathbf{a}} = (\mathbf{a}_s)_{s \in \mathcal{S}}$ might denote a random tuple of random variables $\mathbf{a}_s$ indexed by some index set $\mathcal{S}$.
We write $\mathbb{P}$ for probability, and $\mathbb{E}$ for expectation. If $\mathbf{X}$ takes at most countably many values, we define the essential range of $\mathbf{X}$ to be the set of all $X$ such that $\mathbb{P}( \mathbf{X} = X )$ is non-zero, and thus $\mathbf{X}$ almost surely takes values in its essential range. We also employ the following conditional expectation notation. If $E$ is an event of non-zero probability, we write
$$\mathbb{P}( F | E ) \coloneq \frac{\mathbb{P}( F \wedge E )}{\mathbb{P}(E)}$$
for any event $F$, and
$$\mathbb{E}( \mathbf{X} | E ) \coloneq \frac{\mathbb{E}({\mathbf{X}} 1_E)}{\mathbb{P}(E)}$$
for any (absolutely integrable) real-valued random variable ${\mathbf{X}}$. If $\mathbf{Y}$ is another random variable taking at most countably many values, we define the conditional probability $\mathbb{P}(F|\mathbf{Y})$ to be the random variable that equals $\mathbb{P}(F|\mathbf{Y}=Y)$ on the event $\mathbf{Y}=Y$ for each $Y$ in the essential range of $\mathbf{Y}$, and similarly we define the conditional expectation $\mathbb{E}( \mathbf{X} | \mathbf{Y} )$ to be the random variable that equals $\mathbb{E}( \mathbf{X} | \mathbf{Y} = Y)$ on the event $\mathbf{Y}=Y$. We observe the idempotency property
We begin by using a variant of the Westzynthius-Erdős-Rankin method to reduce this problem to a problem of sieving a set $\mathcal{Q}$ of primes in $[y] \backslash [x]$, rather than integers in $[y] \backslash [x]$.
Given a large real number $x$, define
$$\begin{equation} y \coloneq c x \frac{\log x \log _3 x}{\log _2 x}, \cssId{ydef}{\tag{3.1}} \end{equation}$$
where $c$ is a certain (small) fixed positive constant. Also let
$$\begin{equation} z \coloneq x^{\log _3 x/(4\log _2 x)}, \cssId{zdef}{\tag{3.2}} \end{equation}$$
and introduce the three disjoint sets of primes
$$\begin{align} \mathcal{S}& \coloneq \{ \text{$s$ prime} : \log ^{20} x < s \leqslant z \},\cssId{s-def}{\tag{3.3}}\\ \mathcal{P}& \coloneq \{ \text{$p$ prime}: x/2 < p \leqslant x\},\cssId{p-def}{\tag{3.4}}\\ \mathcal{Q}& \coloneq \{ \text{$q$ prime}: x < q \leqslant y\}. \cssId{q-def}{\tag{3.5}} \end{align}$$
For residue classes $\vec{a} = (a_s \bmod s)_{s\in \mathcal{S}}$ and $\vec{b} = (b_p \bmod p)_{p\in \mathcal{P}}$, define the sifted sets
$$S(\vec{a}) \coloneq \{ n \in \mathbb{Z}: n \not \equiv a_s \mkern 7mu(\mathrm{mod}\,\,s) \text{ for all } s \in \mathcal{S}\}$$
and likewise
$$S(\vec{b}) \coloneq \{ n \in \mathbb{Z}: n \not \equiv b_p \mkern 7mu(\mathrm{mod}\,\,p) \text{ for all } p \in \mathcal{P}\}.$$
We then have the following theorem.
We prove Theorem 2 in subsequent sections. Here, we show how this theorem implies Equation 1.1, and hence Theorem 1.
Let $\vec{a}$ and $\vec{b}$ be as in Theorem 2. We extend the tuple $\vec{a}$ to a tuple $(a_p)_{p \leqslant x}$ of congruence classes $a_p \bmod p$ for all primes $p \leqslant x$ by setting $a_p \coloneq b_p$ for $p \in \mathcal{P}$ and $a_p \coloneq 0$ for $p \not \in \mathcal{S}\cup \mathcal{P}$, and consider the sifted set
$${\mathcal{T}} \coloneq \{ n \in [y]\backslash [x] : n \not \equiv a_p \mkern 7mu(\mathrm{mod}\,\,p) \text{ for all } p \leqslant x \}.$$
The elements of ${\mathcal{T}}$, by construction, are not divisible by any prime in $(0,\log ^{20} x]$ or in $(z,x/2]$. Thus, each element either must be a $z$-smooth number (i.e. a number with all prime factors at most $z$) or must consist of a prime greater than $x/2$, possibly multiplied by some additional primes that are all at least $\log ^{20} x$. However, from Equation 3.1 we know that $y=o(x\log x)$. Thus, we see that an element of ${\mathcal{T}}$ is either a $z$-smooth number or a prime in $\mathcal{Q}$. In the second case, the element lies in $\mathcal{Q}\cap S(\vec{a}) \cap S(\vec{b})$. Conversely, every element of $\mathcal{Q}\cap S(\vec{a}) \cap S(\vec{b})$ lies in ${\mathcal{T}}$. Thus, ${\mathcal{T}}$ only differs from $\mathcal{Q}\cap S(\vec{a}) \cap S(\vec{b})$ by a set $\mathcal{R}$ consisting of $z$-smooth numbers in $[y]$.
To estimate $\# \mathcal{R}$, let
$$u \coloneq \frac{\log y}{\log z},$$
so from Equation 3.1, Equation 3.2 one has $u \sim 4 \frac{\log _2 x}{\log _3 x}$. By standard counts for smooth numbers (e.g. de Bruijn’s theorem Reference 6) and Equation 3.1, we thus have
$$\begin{equation*} \# \mathcal{R}\ll y e^{-u\log u + O( u \log \log (u+2) ) } = \frac{y}{\log ^{4+o(1)} x} = o\left( \frac{x}{\log x}\right). \end{equation*}$$
Thus, we find that $\# \mathcal{T} \ll x/\log x$.
Next, let $C$ be a sufficiently large constant such that $\# \mathcal{T}$ is less than the number of primes in $(x,Cx]$. By matching each of these surviving elements to a distinct prime in $(x,Cx]$ and choosing congruence classes appropriately, we thus find congruence classes $a_p \bmod p$ for $p\leqslant Cx$ which cover all of the integers in $(x,y]$. In the language of Definition 1, we thus have
It remains to establish Theorem 2. This is the objective of the remaining sections of the paper.
4. Efficient hypergraph covering
In the previous section we reduced matters to obtaining residue classes $\vec{a}$,$\vec{b}$ such that the sifted set $\mathcal{Q}\cap S(\vec{a}) \cap S(\vec{ b})$ is small. In this section we use a hypergraph covering theorem, generalizing a result of Pippenger and Spencer Reference 37, to reduce the task to that of finding residue classes $\vec{b}$ that have large intersections with $\mathcal{Q}\cap S(\vec{a})$.
4.1. Heuristic discussion
Consider the following general combinatorial problem. Let $(V,E_i)_{i \in I}$ be a collection of (non-empty) hypergraphs on a fixed finite vertex set $V$ indexed by some finite index set $I$. In other words, $V$ and $I$ are finite sets, and for each $i \in I$,$E_i$ is a (non-empty) collection of subsets of $V$. The problem is then to select a single edge $e_i$ from each set $E_i$ in such a way that the union $\bigcup _{i \in I} e_i$ covers as much of the vertex set $V$ as possible. (In the context considered in Reference 37, one considers choosing many edges from a single hypergraph $(V,E)$, which in our context would correspond to the special case when $(V,E_i)$ was independent of $i$.) One should think of the set $V \backslash \bigcup _{i \in I} e_i$ as a sifted version of $V$, with each $e_i$ representing one step of the sieve.
One simple way to make this selection is a random one: one chooses a random edge $\mathbf{e}_i$ uniformly at random from $E_i$, independently in $i$. In that case, the probability that a given vertex $v \in V$ survives the sifting (that is, it avoids the random union $\bigcup _{i \in I} \mathbf{e}_i$) is equal to
In applications, the index set $I$ is large and the probabilities $\mathbb{P}( v \in \mathbf{e}_i )$ are small, in which case the above expression may be well approximated by
$$\exp ( - d_I(v) ),$$
where we define the normalized degree$d_I(v)$ of $v$ to be the quantity
One has $d_I(v) \approx d$ for all (or almost all) vertices $v$,
we thus expect the sifted set $V \backslash \bigcup _{i \in I} \mathbf{e}_i$ to have density approximately $\exp (-d)$.
Can one do better than this? Choosing the $\mathbf{e}_i$ independently is somewhat inefficient because it allows different random edges $\mathbf{e}_i, \mathbf{e}_j$ to collide with each other. If we could somehow modify the coupling between the $\mathbf{e}_i$ so that they were always disjoint, then the probability that a given vertex $v \in V$ survives the sieve would now become
This suggests that one could in principle lower the density of the sifted set from $\exp (-d)$ to $1-d$ (or $\max (1-d,0)$, since the density clearly cannot be negative), and in particular to sift out $V$ almost completely as soon as $d$ exceeds $1$.
Suppose for the moment that such an optimal level of sieve efficiency is possible, and return briefly to consideration of Theorem 2. We set the vertex set $V$ equal to $\mathcal{Q}\cap S(\vec{a})$ for some suitable choice of $\vec{a}$. If we set
$$y \coloneq c x \frac{\log x \log _3 x}{\log _2 x}$$
for some small $c>0$ (in accordance with Equation 3.1), then standard probabilistic heuristics (together with Mertens’ theorem and Equation 3.1, Equation 3.3) suggest that $V$ should have cardinality about
so in particular this set is roughly $c \log _2 x$ times larger than $\mathcal{P}$. In later sections, we will use the multidimensional sieve from Reference 35, Reference 34 to locate for most primes $p$ in $\mathcal{P}$ a large number of residue classes $b_p \bmod p$ that each intersect $\mathcal{Q}\cap S(\vec{a})$ in roughly $\asymp \log _2 x$ elements on the average. If we let $E_p$ be the set of all such intersections $(b_p \bmod p) \cap V$, then the task of making $\mathcal{Q}\cap S(\vec{a}) \cap S(\vec{b})$ small is essentially the same as making the sifted set $V \backslash \bigcup _{p \in \mathcal{P}} e_p$ small, for some suitable edges $e_p$ drawn from $E_p$. By double counting, the expected density $d$ here should be roughly
and so one should be able to sieve out $\mathcal{Q}\cap S(\vec{a})$ more or less completely once $c$ is small enough if one had optimal sieving. In contrast, if one used independent sieving, one would expect the cardinality of $\mathcal{Q}\cap S(\vec{a}) \cap S(\vec{b})$ to be something like $\exp ( - 1/c ) \times c \frac{x}{\log x} \log _2 x$, which would only be acceptable if $c$ was slightly smaller than $\frac{1}{\log _3 x}$. This loss of $\log _3 x$ ultimately leads to the loss of $\log _4 X$ in Equation 1.4 as compared against Theorem 1.
It is thus desirable to obtain a general combinatorial tool for achieving near-optimal sieve efficiency for various collections $(V,E_i)_{i \in I}$ of hypergraphs. The result of Pippenger and Spencer Reference 37 (extending previous results of Rödl Reference 42 and Frankl and Rödl Reference 17, as well as unpublished work of Pippenger) asserts, very roughly speaking, that one can almost attain this optimal efficiency under some further assumptions beyond (i), which we state informally as follows:
(ii)
The hypergraphs $(V,E_i)$ do not depend on $i$.
(iii)
The normalized codegrees$\sum _{i \in I} \mathbb{P}( v, w \in \mathbf{e}_i )$ for $v \neq w$ are small.
(iv)
The edges $e_i$ of $E_i$ are of constant size, and thus there is a $k$ such that $\# e_i = k$ for all $i$ and all $e_i \in E_i$.
The argument is based on the Rödl nibble from Reference 42, which is a variant of the semi-random method from Reference 1. Roughly speaking, the idea is to break up the index set $I$ into smaller pieces $I_1,\dots ,I_m$. For the first $I_1$, we perform a “nibble” by selecting the $\mathbf{e}_i$ for $i \in I_1$ uniformly and independently. For the next nibble at $I_2$, we restrict (or condition) the $\mathbf{e}_i$ for $i \in I_2$ to avoid the edges arising in the first nibble, and then select $\mathbf{e}_i$ for $i \in I_2$ independently at random using this conditioned distribution. We continue performing nibbles at $I_3,\dots ,I_m$ (restricting the edges at each nibble to be disjoint from the edges of previous nibbles) until the index set $I$ is exhausted. Intuitively, this procedure enjoys better disjointness properties than the completely independent selection scheme, but it is harder to analyze the probability of success. To achieve the latter task, Pippenger and Spencer rely heavily on the four hypotheses (i)–(iv).
In our context, hypothesis (iii) is easily satisfied, and (i) can also be established. Hypothesis (ii) is not satisfied (the $E_p$ vary in $p$), but it turns out that the argument of Pippenger and Spencer can easily be written in such a way that this hypothesis may be discarded. But it is the failure of hypothesis (iv) which is the most severe difficulty: the size of the sets $e_p = (b_p \bmod p) \cap V$ can fluctuate quite widely for different choices of $p$ or $b_p$. This creates an undesirable bias in the iterative nibbling process: with each nibble, larger edges $\mathbf{e}_i$ have a reduced chance of survival compared with smaller edges, simply because they have more elements that could potentially intersect previous nibbles. Given that one expects the larger edges to be the most useful for the purposes of efficient sieving, this bias is a significant problem. One could try to rectify the issue by partitioning the edge sets $E_i$ depending on the cardinality of the edges, and working on one partition at a time, but this seriously impacts hypothesis (i) in a manner that we were not able to handle.
Our resolution to this problem is to modify the iterative step of the nibbling process by reweighting the probability distribution of the $\mathbf{e}_i$ at each step to cancel out the bias incurred by conditioning an edge $\mathbf{e}_i$ to be disjoint from previous nibbles. It turns out that there is a natural choice of reweighting for this task even when the normalized degrees $d_I(v)$ vary in $v$. As a consequence, we can obtain a version of the Pippenger-Spencer theorem in which hypothesis (ii) is essentially eliminated and (i), (iv) significantly weakened, leaving only (iii) as the main hypothesis. We remark that a somewhat similar relaxation of hypotheses (i)–(iv) was obtained by Kahn in Reference 29, although the statement in Reference 29 is not exactly in a form convenient for our applications here.
4.2. Statement of covering theorem
We now rigorously state the hypergraph covering theorem that we will use. In order to apply this theorem for our application, we will need a probabilistic formulation of this theorem which does not, at first glance, bear much resemblance to the combinatorial formulation appearing in Reference 37; we will discuss the connections between these formulations shortly. We will also phrase the theorem in a completely quantitative fashion, avoiding the use of asymptotic notation; this will be convenient for the purposes of proving the theorem via induction (on the number $m$ of “nibbles”).
We prove this theorem in Section 5. It is likely that the smallness condition Equation 4.1 can be relaxed, for instance by modifying the techniques from Reference 45. However, this would not lead to any significant improvement in the final bound on $G(X)$ in Theorem 1, as in our application the condition Equation 4.1 is already satisfied with some room to spare. The parameter $r$ does not appear explicitly in the smallness requirement Equation 4.1, but is implicit in that requirement since the conclusion is trivially true unless $2r < A$.
One may deduce special cases of this theorem which are close to the original hypergraph covering lemma of Pippenger and Spencer. These were included in an earlier draft of this paper (as Corollaries 2 and 3), and will now be described in a future, separate paper.
4.3. Applying the covering theorem
We now specialize Theorem 3 to a situation relevant for the application to large prime gaps, given by Corollary 4. Very roughly, this states that if we have a large collection $\{\mathbf{e}_p:\,p\in \mathcal{P}'\}$ of random subsets of a set $\mathcal{Q}'$, then there is a realization of these random variables which covers almost all of $\mathcal{Q}'$, provided the subsets are suitably “uniform” and all elements of $\mathcal{Q}$ are covered more than once on average. Clearly we cannot hope to cover $\mathcal{Q}$ unless almost all elements are covered at least once on average, and similarly if the subsets are too highly correlated, then one can easily produce examples where $\mathcal{Q}'$ will not be covered. Thus some form of both of these assumptions is necessary. For our application to prime gaps, the random sets $\mathbf{e}_p$ will be all elements of $\mathcal{Q}'$ in a randomly chosen residue class $\bmod {p}$ (which will be produced by the multidimensional sieve in the later sections).
Remarks. For the arguments in this paper, we only need the case $\mathcal{Q}'' = \mathcal{Q}'$, but the more general situation $\mathcal{Q}'' \subset \mathcal{Q}'$ will be of use in the sequel Reference 15 of this paper when we consider chains of large gaps.
Now let $\vec{\mathbf{a}}$ and $\vec{\mathbf{n}}$ be the random vectors guaranteed by Theorem 4. Suppose that we are in the probability $1-o(1)$ event that $\vec{\mathbf{a}}$ takes a value $\vec{a}$ which is good and such that Equation 4.28 holds. Fix some $\vec{a}$ within this event. We may apply Corollary 4 with $\mathcal{P}'=\mathcal{P}$ and $\mathcal{Q}'=\mathcal{Q}\cap S(\vec{a})$ for the random variables $\mathbf{n}_p$ conditioned to $\vec{\mathbf{a}}=\vec{a}$. A few hypotheses of the corollary must be verified. First, Equation 4.15 follows from Equation 4.29. The small codegree condition Equation 4.14 is also quickly checked. Indeed, for distinct $q_1,q_2\in \mathcal{Q}'$, if $q_1,q_2 \in \mathbf{e}_p(\vec{a})$, then $p|q_1-q_2$. But $q_1-q_2$ is a nonzero integer of size at most $x\log x$ and is thus divisible by at most one prime $p_0\in \mathcal{P}'$. Hence
the sum on the left side being zero if $p_0$ does not exist. By Corollary 4, there exist random variables $\mathbf{e}'_p(\vec{a})$, whose essential range is contained in the essential range of $\mathbf{e}_p(\vec{a})$ together with $\emptyset$, and satisfying
with probability $1-o(1)$, where we have used Equation 4.28. Since $\mathbf{e}'_p(\vec{a})=\{\mathbf{n}'_p+h_i p : 1\leqslant i\leqslant r\} \cap \mathcal{Q}\cap S(\vec{a})$ for some random integer $\mathbf{n}'_p$, it follows that
$$\{ q\in \mathcal{Q}\cap S(\vec{a}) : q\not \equiv \mathbf{n}'_p\mkern 7mu(\mathrm{mod}\,\,p) \text{ for all }p\in \mathcal{P}\} \ll \frac{x}{\log x}$$
with probability $1-o(1)$. Taking a specific $\vec{\mathbf{n}}'=\vec{n}'$ for which this relation holds and setting $b_p=n'_p$ for all $p$ concludes the proof of the claim Equation 3.6 and establishes Theorem 2.
It remains to establish Theorem 4. This will be achieved in later sections.
5. Proof of the covering theorem
We now prove Theorem 3. Let $C_0$ be a sufficiently large absolute constant.
We induct on $m$. The case $m=0$ is vacuous, so suppose that $m \geqslant 1$ and that the claim has already been proven for $m-1$. Let $D,r,A,\kappa ,\delta ,I_j,\mathbf{e}_i,V$ be as in the theorem. By the induction hypothesis, we can already find random variables $\mathbf{e}'_i$ for $i \in \bigcup _{j=1}^{m-1} I_j$ obeying the conclusions (a), (b) of the theorem for $m-1$. In particular, we may form the partially sifted set
whenever $e\subset V$ has cardinality $\# e \leqslant A - 2r(m-1)$.
Our task is then to construct random variables $\mathbf{e}'_i$ for $i \in I_m$, possibly coupled with existing random variables such as $\mathbf{W}$, whose essential range is contained in that of $\mathbf{e}_i$ together with the empty set, and such that
for all finite subsets $e$ of $V$ with $\# e \leqslant A - 2rm$. Note that we may assume that $A > 2rm$, as the claim Equation 4.10 is trivial otherwise. In particular we have
$$\begin{equation} A - 2r(m-1) > 2r. \cssId{e2r}{\tag{5.3}} \end{equation}$$
whenever $j=1,\dots ,m$ and all $\tilde{e} \subset V$. In particular, by Equation 5.4 and Equation 4.2, whenever $\tilde{e}_i$ is in the essential range of $\mathbf{e}_i$, we have
We will see shortly, and this is crucial to our argument, that $X_i(\mathbf{W})$ concentrates to 1. With this in mind, we let $F_i = F_i(\mathbf{W})$ be the event that
Very small values of $X_i(W)$, in particular sets $W$ with $X_i(W)=0$, are problematic for us and must be avoided. Fortunately, this occurs with very small probability.
We now define the random variables $\mathbf{e}'_i$ for $i \in I_m$. If $F_i(\mathbf{W})$ fails, we set $\mathbf{e}_i'=\emptyset$. Otherwise, if $F_i(\mathbf{W})$ holds, then after conditioning on a fixed value $W$ of $\mathbf{W}$, we choose $\mathbf{e}'_i$ from the essential range of $\mathbf{e}_i$ using the conditional probability distribution
for all $\tilde{e}_i$ in the essential range of $\mathbf{e}_i$, and we also require that the $\mathbf{e}'_i$ are conditionally jointly independent for $i \in I_m$ on each event $\mathbf{W}=W$. Note from Equation 5.7 that Equation 5.9 defines a probability distribution, and so the $\mathbf{e}'_i$ are well defined as random variables. Informally, $\mathbf{e}'_i$ is $\mathbf{e}_i$ conditioned to the event $\mathbf{e}_i \subset W$, and then reweighted by $P_{m-1}(\mathbf{e}_i)$ to compensate for the bias caused by this conditioning.
It remains to verify Equation 5.2. Let $e$ be a fixed subset of $V$ with
$$\begin{equation} \# e \leqslant A - 2rm. \cssId{E-bound-quant}{\tag{5.12}} \end{equation}$$
For any $W$ in the essential range of $\mathbf{W}$, let $Y(W)$ denote the quantity
$$Y( W ) \coloneq \mathbb{P}\left( e \subset W \backslash \bigcup _{i \in I_m} \mathbf{e}'_i | \mathbf{W} = W \right).$$
Suppose that $W$ is in the essential range of $\mathbf{W}$ with $e \subset W$. As the $\mathbf{e}'_i$,$i \in I_m$, are jointly conditionally independent on the event $\mathbf{W}=W$, we may factor $Y(W)$ as
$$Y(W) = \prod _{i \in I_m} (1 - \mathbb{P}( e \cap \mathbf{e}'_i \neq \emptyset | \mathbf{W} = W ) ).$$
Since $\mathbf{e}_i'=\emptyset$ if $F_i(W)$ fails, we may write
$$\begin{align*} & \mathbb{P}( e \cap \mathbf{e}'_i \neq \emptyset | \mathbf{W} = W )\\ &\quad = \sum _{v \in e} \mathbb{P}( v \in \mathbf{e}'_i | \mathbf{W}=W) - O\left( \sum _{v,w \in e: v \neq w} \mathbb{P}( v, w \in \mathbf{e}'_i | \mathbf{W}=W) \right). \end{align*}$$
The error term is handled by summing Equation 5.9 over all $\tilde{e}_i$ with $v,w\in \tilde{e}_i$, and using Equation 5.8 and Equation 5.5. For distinct $v,w \in e$, we have
with probability $1 - O( \delta ^{ \frac{1}{8 \times 10^m} } )$, conditionally on the event that $e \subset \mathbf{W}$. From Equation 5.12, Equation 5.6, and the union bound, it thus suffices to show that for each $v \in e$, one has
Thus, by Markov’s inequality, this error is $O( \delta ^{ \frac{1}{7 \times 10^m} } )$ with probability $1 - O( \delta ^{ \frac{1}{7 \times 10^m} } )$, conditionally on $e \subset \mathbf{W}$. By the triangle inequality, it thus suffices to show that the main term satisfies
with probability $1 - O( \delta ^{ \frac{1}{7 \times 10^m} } )$, conditionally on $e \subset \mathbf{W}$.
By a conditional version of Lemma 2.1 (replacing $\mathbb{E}X$ and $\mathbb{E}X^2$ with $\mathbb{E}(X|E)$ and $\mathbb{E}(X^2|E)$, respectively), together with Equation 4.8, Equation 4.1, it suffices to show that
As in the proof of Lemma 5.1, $P_{m-1}(\tilde{e}_i\cap e \backslash \{v\})$ equals 1 unless $\tilde{e}_i$ and $e \backslash \{v\}$ have a common element, in which case it is $\geqslant \kappa ^{r}$ by Equation 5.5. Thus
$$\frac{1}{P_{m-1}(\tilde{e}_i\cap e \backslash \{v\})} = 1 + O\left( \kappa ^{-r} \sum _{w \in e \backslash \{v\}} 1_{w \in \tilde{e}_i} \right).$$
The quantity $\frac{P_{m-1}(v)^2 P_{m-1}( \tilde{e}_i\cup \hat{e}_i\cup e )}{P_{m-1}(\tilde{e}_i) P_{m-1}(\hat{e}_i) P_{m-1}(e)}$ is equal to $1$ when the intersection of any two of $\tilde{e}_i,\hat{e}_i$, and $e$ is $\{v\}$, and is $O(\kappa ^{-2r})$ otherwise thanks to Equation 5.5. Hence we may estimate this ratio by
If $r$ is a natural number, an admissible $r$-tuple is a tuple $(h_1,\dots ,h_r)$ of distinct integers $h_1,\dots ,h_r$ that do not cover all residue classes modulo $p$, for any prime $p$. For instance, the tuple $(p_{\pi (r)+1},\dots ,p_{\pi (r)+r})$ consisting of the first $r$ primes larger than $r$ is an admissible $r$-tuple.
We will establish Theorem 4 by a probabilistic argument involving a certain weight function, the details of which may be found in the following.
The proof of this theorem will rely on the estimates for multidimensional prime-detecting sieves established by the fourth author in Reference 34, and will be the focus of subsequent sections. In this section, we show how Theorem 5 implies Theorem 4.
Let $x, c, y, z, \mathcal{S}, \mathcal{P}, \mathcal{Q}$ be as in Theorem 4. We set $r$ to be the maximum value permitted by Theorem 5, namely
$$\begin{equation} r \coloneq \lfloor \log ^{1/5} x \rfloor , \cssId{r-def}{\tag{6.8}} \end{equation}$$
and let $(h_1,\dots ,h_r)$ be the admissible $r$-tuple consisting of the first $r$ primes larger than $r$; thus $h_i = p_{\pi (r)+i}$ for $i=1,\dots ,r$. From the prime number theorem we have $h_i = O( r \log r )$ for $i=1,\dots ,r$, and so we have $h_i \in [2r^2]$ for $i=1,\dots ,r$ if $x$ is large enough (there are many other choices possible, e.g. $(h_1,\ldots ,h_r)=(1^2,3^2,\ldots ,(2r-1)^2)$). We now invoke Theorem 5 to obtain quantities $\tau ,u$ and a weight $w: \mathcal{P}\times \mathbb{Z}\to \mathbb{R}^+$ with the stated properties.
For each $p \in \mathcal{P}$, let $\tilde{\mathbf{n}}_p$ denote the random integer with probability density
for all $n \in \mathbb{Z}$ (we will not need to impose any independence conditions on the $\tilde{\mathbf{n}}_p$). From Equation 6.4, Equation 6.5 we have
for all $p \in \mathcal{P}$ and $n \in \mathbb{Z}$.
We choose the random vector $\vec{\mathbf{a}} \coloneq (\mathbf{a}_s \bmod s)_{s \in \mathcal{S}}$ by selecting each $\mathbf{a}_s \bmod s$ uniformly at random from $\mathbb{Z}/s\mathbb{Z}$, independently in $s$ and independently of the $\tilde{\mathbf{n}}_p$. The resulting sifted set $S(\vec{\mathbf{a}})$ is a random periodic subset of $\mathbb{Z}$ with density
In light of Lemma 6.1, we expect most primes in $\mathcal{P}$ to lie in $\mathcal{P}(\vec{a})$, and this will be confirmed below (Lemma 6.3). We now define the random variables $\mathbf{n}_p$ as follows. Suppose we are in the event $\vec{\mathbf{a}} = \vec{a}$ for some $\vec{a}$ in the range of $\vec{\mathbf{a}}$. If $p \in \mathcal{P}\backslash \mathcal{P}(\vec{a})$, we set $\mathbf{n}_p=0$. Otherwise, if $p \in \mathcal{P}(\vec{a})$, we define $\mathbf{n}_p$ to be the random integer with conditional probability distribution
with the $\mathbf{n}_p$($p\in \mathcal{P}(\vec{a})$) jointly independent, conditionally on the event $\vec{\mathbf{a}} = \vec{a}$. From Equation 6.14 we see that these random variables are well defined.
Let $\vec{a}$ be good (recall the definition from Theorem 4) and $q\in \mathcal{Q}\cap S(\vec{a})$. Substituting definition Equation 6.16 into the left-hand side of Equation 6.17, using Equation 6.15, and observing that $q=\mathbf{n}_p+h_ip$ is possible only if $p\in \mathcal{P}(\vec{\mathbf{a}})$ (since $\mathbf{n}_p=0$ for $p\in \mathcal{P}\backslash \mathcal{P}(\vec{a})$), we find that
where $\mathbf{e}_p(\vec{a}) = \{ \mathbf{n}_p+h_ip:1\leqslant i\leqslant r \} \cap \mathcal{Q}\cap S(\vec{a})$ is as defined in Theorem 4. Relation Equation 4.29 (that is, $\vec{\mathbf{a}}$ is good with probability $1-o(1)$) follows upon noting that by Equation 6.8, Equation 6.3, and Equation 6.11,
Before proving Lemma 6.2, we first confirm that $\mathcal{P}\backslash \mathcal{P}(\vec{\mathbf{a}})$ is small with high probability.
It remains to establish Theorem 5. This is the objective of the remaining sections of the paper.
7. Multidimensional sieve estimates
We now recall a technical multidimensional sieve estimate from Reference 34 (a minor variant of Reference 34, Proposition 6.1). In this section we will follow the notation from Reference 34, which is a little different from that in the rest of this paper, with the exception that we will take the set denoted $\mathcal{P}$ in that paper to be equal to the set $\mathscr{P}$ of all primes from the outset.
A linear form will be a function $L: \mathbb{Z}\to \mathbb{Z}$ of the form $L(n) = l_1 n + l_2$ with integer coefficients $l_1,l_2$, and $l_1 \neq 0$. Let ${\mathcal{A}}$ be a set of integers. Given a linear form $L(n) = l_1 n + l_2$, we define the sets
$$\begin{align*} {\mathcal{A}}(x) & \coloneq \{ n \in {\mathcal{A}}: x \leqslant n \leqslant 2x\}, \\ {\mathcal{A}}(x;q,a) & \coloneq \{ n \in {\mathcal{A}}(x): n \equiv a\ \mkern 7mu(\mathrm{mod}\,\,q)\}, \\ {\mathscr{P}}_{L,{\mathcal{A}}}(x) & \coloneq L({\mathcal{A}}(x)) \cap {\mathscr{P}}, \\ {\mathscr{P}}_{L,{\mathcal{A}}}(x; q,a) & \coloneq L({\mathcal{A}}(x;q,a)) \cap {\mathscr{P}}, \end{align*}$$
for any $x > 0$ and congruence class $a \bmod q$, and define the quantity
since $\varphi (X)/X$ is smallest when $X$ is composed only of primes $\ll \log {X}$. Thanks to this bound, most factors of the form $\frac{X}{\varphi (X)}$ appearing below become relatively harmless, and we recommend that they may be ignored for a first reading.
A finite set ${\mathcal{L}} = \{ L_1,\dots ,L_k\}$ of linear forms is said to be admissible if $\prod _{i=1}^k L_i(n)$ has no fixed prime divisor; that is, for every prime $p$ there exists an integer $n_p$ such that $\prod _{i=1}^k L_i(n_p)$ is not divisible by $p$.
In Reference 34 this definition was only given in the case ${\mathcal{L}}'={\mathcal{L}}$, but we will need the (mild) generalization to the case in which ${\mathcal{L}}'$ is a (possibly empty) subset of ${\mathcal{L}}$.
As is common in analytic number theory, we will have to address the possibility of an exceptional Siegel zero. As we want to keep all our estimates effective, we will not rely on Siegel’s theorem or its consequences (such as the Bombieri-Vinogradov theorem). Instead, we will rely on the Landau-Page theorem, which we now recall. Throughout, $\chi$ denotes a Dirichlet character.
We can then eliminate the exceptional character by deleting at most one prime factor of $q_Q$—an idea used previously by Hildebrand and Maier Reference 27.
We will only need the above definition in the following special case.
We now recall the construction of sieve weights from Reference 34, Section 7. On first reading we recommend the reader not pay too much attention to the details; the key point is the existence of a weight $w(n)$ which will establish Theorem 5. The reason it is necessary to know the construction is the technical issue that the weights $w(n)$ depend on a given admissible set of linear forms, and we require that the final estimates obtained are essentially uniform over similar admissible sets.
Let $W \coloneq \prod _{p \leqslant 2k^2;\, p \nmid B} p$. For each prime $p$ not dividing $B$, let $r_{p,1}({\mathcal{L}}) < \dots < r_{p,\omega _{\mathcal{L}}(p)}({\mathcal{L}})$ be the elements $n$ of $[p]$ for which $p| \prod _{i=1}^k L_i(n)$. If $p$ is also coprime to $W$, then for each $1 \leqslant a \leqslant \omega _{\mathcal{L}}(p)$, let $j_{p,a} = j_{p,a}({\mathcal{L}})$ denote the least element of $[k]$ such that $p | L_{j_{p,a}}( r_{p,a}({\mathcal{L}}) )$.
We note that the restriction of the support of $F$ to $\mathcal{R}_k$ means that $\lambda _{(d_1,\dots ,d_k)}(\mathcal{L})$ and $y_{(r_1,\dots ,r_k)}$ are supported on the set
We then have the following result, a slightly modified form of Proposition 6.1 from Reference 34.
We remark that the estimate Equation 7.8 is only needed here to establish the estimate Equation 6.6 which is not, strictly speaking, necessary for the results of this paper, but will be useful in a subsequent work Reference 15 based on this paper.
8. Verification of sieve estimates
We can now prove Theorem 5. Let $x,y,r,h_1,\dots ,h_r$ be as in that theorem.
for $p \in \mathcal{P}$ and $n \in \mathbb{Z}$, where ${\mathcal{L}}_p$ is the (ordered) collection of linear forms $n \mapsto n+h_i p$ for $i=1,\dots ,r$, and $w_{k, {\mathcal{L}}_p, B, R}$ was defined in Equation 7.4. Note that the admissibility of the $r$-tuple$(h_1,\dots ,h_r)$ implies the admissibility of the linear forms $n \mapsto n+h_i p$.
A key point is that many of the important components of $w_{k, {\mathcal{L}}_p, B, R}$ are essentially uniform in $p$. Indeed, for any prime $s$, the polynomial $\prod _{i=1}^k (n+h_i p)$ is divisible by $s$ only at the residue classes $-h_i p \bmod s$. From this we see that
$$\omega _{{\mathcal{L}}_{p}}(s) =\#\{h_i\mkern 7mu(\mathrm{mod}\,\,s)\} \text{ whenever } s \neq p.$$
In particular, $\omega _{{\mathcal{L}}_{p}}(s)$ is independent of $p$ as long as $s$ is distinct from $p$, so
for some ${\mathfrak{S}}$,${\mathfrak{S}}_{BW}$ independent of $p$, with the error terms uniform in $p$. Moreover, if $s\nmid WB$, then $s>2k^2$, so all the $h_i$ are distinct $\bmod {s}$ (since the $h_i$ are less than $2k^2$). Therefore, if $s\nmid pWB$ we have $\omega _{\mathcal{L}_p}(s)=k$ and
Since all $p\in \mathcal{P}$ are at least $x/2>R$, we have $s\ne p$ whenever $s\leqslant R$. From this we see that $\mathcal{D}_k(\mathcal{L}_p)\cap \{(d_1,\dots ,d_k):\prod _{i=1}^k d_i\leqslant R\}$ is independent of $p$, and so we have
and so we have the lower bound Equation 6.2. (In fact, we also have a matching upper bound $\tau \leqslant x^{o(1)}$, but we will not need this.)
It remains to verify the estimates Equation 6.4, Equation 6.5, and Equation 6.6. We begin with Equation 6.4. Let $p$ be an element of $\mathcal{P}$. We shift the $n$ variable by $3{\left\lfloor {y} \right\rfloor }$ and rewrite
where ${\mathcal{L}}_p - 3{\left\lfloor {y} \right\rfloor }$ denotes the set of linear forms $n \mapsto n+h_ip - 3{\left\lfloor {y} \right\rfloor }$ for $i=1,\dots ,k$. This set of linear forms remains admissible, and
The claim Equation 6.4 now follows from Equation 8.2 and the first conclusion Equation 7.6 of Theorem 6 (with $x$ replaced by $2{\left\lfloor {y} \right\rfloor }$,${\mathcal{L}}'=\emptyset$, and ${\mathcal{L}} = {\mathcal{L}}_p - 3{\left\lfloor {y} \right\rfloor }$), using Lemma 7.2 to obtain Hypothesis 1.
Now we prove Equation 6.5. Fix $q \in \mathcal{Q}$ and $i\in \{1,\dots ,k\}$. We introduce the set $\tilde{\mathcal{L}}_{q,i}$ of linear forms $\tilde{L}_{q,i,1},\dots , \tilde{L}_{q,i,k}$, where
are $n\equiv 0$ and $n\equiv -q(h_j-h_i)^{-1}\mkern 7mu(\mathrm{mod}\,\,s)$ for $h_j\not \equiv h_i\mkern 7mu(\mathrm{mod}\,\,s)$, the number of which is equal to $\#\{h_j\mkern 7mu(\mathrm{mod}\,\,s)\}$. Thus,
as before. Again, for $s\nmid WB$ we have that the $h_i$ are distinct $\mkern 7mu(\mathrm{mod}\,\,s)$, and so if $s<R$ and $s\nmid WB$, we have $\omega _{\tilde{\mathcal{L}}_{q,i}}(s) =k$ and
whenever $p \in \mathcal{P}$ (note that the $d_i$ summation variable implicit on both sides of this equation is necessarily equal to $1$). Thus, recalling that $\mathcal{P}=\mathscr{P}\cap (x/2,x]$, we can write the left-hand side of Equation 6.5 as
Applying the second conclusion Equation 7.7 of Theorem 6 (with $x$ replaced by $x/2$,${\mathcal{L}}'= \{\tilde{L}_{q,i,i}\}$, and ${\mathcal{L}} = \tilde{\mathcal{L}}_{q,i}$) and using Lemma 7.2 to obtain Hypothesis 1, this expression becomes
Finally, we prove Equation 6.6. Fix $h=O(y/x)$ not equal to any of the $h_i$, and fix $p \in \mathcal{P}$. By the prime number theorem, it suffices to show that
Now $h-h_i = O(y/x) = O( \log x )$ for each $i$, hence $\Delta \leqslant (O(x\log x))^k$, and it follows from Equation 7.1, Equation 8.4, and Equation 6.1 that
This concludes the proof of Theorem 5, and hence Theorem 1.
Acknowledgments
The research of the third author was partially performed while he was visiting the first author at the University of Illinois at Urbana–Champaign. The research of the first and third authors was also carried out in part at the University of Chicago. The first and third authors are thankful to Prof. Wilhelm Schlag for hosting these visits. The first author also thanks the Institute of Mathematics and Informatics of the Bulgarian Academy of Sciences for the hospitality.
Also, the research of the third and the fifth authors was partially performed while the third author was visiting the Institute for Pure and Applied Mathematics (IPAM) at UCLA, which is supported by the National Science Foundation.
The research of the fourth author was conducted partly while he was a CRM-ISM postdoctoral fellow at the Université de Montréal, and partly while he was a Fellow by Examination at Magdalen College, Oxford. He also thanks Andrew Granville and Daniel Fiorilli for many useful comments and suggestions. The fifth author also thanks Noga Alon and Van Vu for help with the references.
M. Ajtai, J. Komlós, and E. Szemerédi, A dense infinite Sidon sequence, European J. Combin. 2 (1981), no. 1, 1–11, DOI 10.1016/S0195-6698(81)80014-5. MR611925, Show rawAMSref\bib{aks}{article}{
author={Ajtai, Mikl\'os},
author={Koml\'os, J\'anos},
author={Szemer\'edi, Endre},
title={A dense infinite Sidon sequence},
journal={European J. Combin.},
volume={2},
date={1981},
number={1},
pages={1\textendash 11},
issn={0195-6698},
review={\MR {611925}},
doi={10.1016/S0195-6698(81)80014-5},
}
Reference [2]
R. J. Backlund, Über die Differenzen zwischen den Zahlen, die zu den ersten $n$ Primzahlen teilerfremd sind, Commentationes in honorem E. L. Lindelöf. Annales Acad. Sci. Fenn. 32 (1929), Nr. 2, 1–9.
Reference [3]
R. C. Baker and T. Freiberg, Limit points and long gaps between primes, Quart. J. Math. Oxford 67 (2016), no. 2, 233–260. MR3509992, Show rawAMSref\bib{BF}{article}{
author={Baker, R. C.},
author={Freiberg, T.},
title={Limit points and long gaps between primes},
journal={Quart. J. Math. Oxford},
volume={67},
date={2016},
number={2},
pages={233\textendash 260},
review={\MR {3509992}},
}
Reference [4]
R. C. Baker, G. Harman, and J. Pintz, The difference between consecutive primes. II, Proc. Lond. Math. Soc. (3) 83 (2001), no. 3, 532–562, DOI 10.1112/plms/83.3.532. MR1851081, Show rawAMSref\bib{BHP}{article}{
author={Baker, R. C.},
author={Harman, G.},
author={Pintz, J.},
title={The difference between consecutive primes. {\rm II}},
journal={Proc. Lond. Math. Soc. (3)},
volume={83},
date={2001},
number={3},
pages={532\textendash 562},
issn={0024-6115},
review={\MR {1851081}},
doi={10.1112/plms/83.3.532},
}
Reference [5]
A. Brauer and H. Zeitz, Über eine zahlentheoretische Behauptung von Legendre, Sitzungsberichte Berliner Math. Ges. 29 (1930), 116–125.
Reference [6]
N. G. de Bruijn, On the number of positive integers $\leqslant x$ and free of prime factors $>y$, Nederl. Acad. Wetensch. Proc. Ser. A. 54 (1951), 50–60. MR0046375, Show rawAMSref\bib{deB}{article}{
author={de Bruijn, N. G.},
title={On the number of positive integers $\le x$ and free of prime factors $>y$},
journal={Nederl. Acad. Wetensch. Proc. Ser. A.},
volume={54},
date={1951},
pages={50\textendash 60},
review={\MR {0046375}},
}
Reference [7]
H. Cramér, Some theorems concerning prime numbers, Ark. Mat. Astr. Fys. 15 (1920), 1–33.
Reference [8]
H. Cramér, On the order of magnitude of the difference between consecutive prime numbers, Acta Arith. 2 (1936), 396–403.
Reference [9]
H. Davenport, Multiplicative number theory, 3rd ed., Graduate Texts in Mathematics, vol. 74, Springer-Verlag, New York, 2000. Revised and with a preface by Hugh L. Montgomery. MR1790423, Show rawAMSref\bib{Da}{book}{
author={Davenport, Harold},
title={Multiplicative number theory},
series={Graduate Texts in Mathematics},
volume={74},
edition={3},
note={Revised and with a preface by Hugh L. Montgomery},
publisher={Springer-Verlag, New York},
date={2000},
pages={xiv+177},
isbn={0-387-95097-4},
review={\MR {1790423}},
}
[10]
L. E. Dickson, History of the theory of numbers, vol. III, Carnegie Inst. of Washington, Washington, DC, 1919, 1920, 1923.
Reference [11]
P. Erdős, On the difference of consecutive primes, Quart. J. Math. Oxford Ser. 6 (1935), 124–128.
Reference [12]
P. Erdős, Some of my favourite unsolved problems, A tribute to Paul Erdős, Cambridge Univ. Press, Cambridge, 1990, pp. 467–478. MR1117038, Show rawAMSref\bib{Erd90}{article}{
author={Erd\H os, Paul},
title={Some of my favourite unsolved problems},
conference={ title={A tribute to Paul Erd\H os}, },
book={ publisher={Cambridge Univ. Press, Cambridge}, },
date={1990},
pages={467\textendash 478},
review={\MR {1117038}},
}
Reference [13]
K. Ford, B. Green, S. Konyagin, and T. Tao, Large gaps between consecutive prime numbers, Ann. of Math. (2) 183 (2016), no. 3, 935–974, DOI 10.4007/annals.2016.183.3.4. MR3488740, Show rawAMSref\bib{FGKT}{article}{
author={Ford, Kevin},
author={Green, Ben},
author={Konyagin, Sergei},
author={Tao, Terence},
title={Large gaps between consecutive prime numbers},
journal={Ann. of Math. (2)},
volume={183},
date={2016},
number={3},
pages={935\textendash 974},
issn={0003-486X},
review={\MR {3488740}},
doi={10.4007/annals.2016.183.3.4},
}
Reference [14]
K. Ford, D. R. Heath-Brown, and S. Konyagin, Large gaps between consecutive prime numbers containing perfect powers, Analytic number theory, Springer, Cham, 2015, pp. 83–92. MR3467391, Show rawAMSref\bib{FHBK}{article}{
author={Ford, Kevin},
author={Heath-Brown, D. R.},
author={Konyagin, Sergei},
title={Large gaps between consecutive prime numbers containing perfect powers},
conference={ title={Analytic number theory}, },
book={ publisher={Springer, Cham}, },
date={2015},
pages={83\textendash 92},
review={\MR {3467391}},
}
Reference [15]
K. Ford, J. Maynard, and T. Tao, Chains of large gaps between primes, to appear in the book “Irregularities in the distribution of prime numbers,” dedicated to Helmut Maier.
Reference [16]
S. Foucart and H. Rouhut, A mathematical introduction to compressive sensing, Birkhaüser/Springer, New York, 2013. MR3100033, Show rawAMSref\bib{FR}{book}{
author={Foucart, S.},
author={Rouhut, H.},
title={A mathematical introduction to compressive sensing},
publisher={Birkha\"user/Springer, New York},
date={2013},
review={\MR {3100033}},
}
Reference [17]
P. Frankl and V. Rödl, Near perfect coverings in graphs and hypergraphs, European J. Combin. 6 (1985), no. 4, 317–326, DOI 10.1016/S0195-6698(85)80045-7. MR829351, Show rawAMSref\bib{rodl}{article}{
author={Frankl, P.},
author={R\"odl, V.},
title={Near perfect coverings in graphs and hypergraphs},
journal={European J. Combin.},
volume={6},
date={1985},
number={4},
pages={317\textendash 326},
issn={0195-6698},
review={\MR {829351}},
doi={10.1016/S0195-6698(85)80045-7},
}
[18]
J. Friedlander and H. Iwaniec, Opera de cribro, American Mathematical Society Colloquium Publications, vol. 57, American Mathematical Society, Providence, RI, 2010, DOI 10.1090/coll/057. MR2647984, Show rawAMSref\bib{FI}{book}{
author={Friedlander, John},
author={Iwaniec, Henryk},
title={Opera de cribro},
series={American Mathematical Society Colloquium Publications},
volume={57},
publisher={American Mathematical Society, Providence, RI},
date={2010},
pages={xx+527},
isbn={978-0-8218-4970-5},
review={\MR {2647984}},
doi={10.1090/coll/057},
}
[19]
P. X. Gallagher, A large sieve density estimate near $\sigma =1$, Invent. Math. 11 (1970), 329–339. MR0279049, Show rawAMSref\bib{gallagher}{article}{
author={Gallagher, P. X.},
title={A large sieve density estimate near $\sigma =1$},
journal={Invent. Math.},
volume={11},
date={1970},
pages={329\textendash 339},
review={\MR {0279049}},
}
Reference [20]
A. Granville, Harald Cramér and the distribution of prime numbers, Scand. Actuar. J. (1995), 12–28. MR1349149, Show rawAMSref\bib{Gra}{article}{
author={Granville, A.},
title={Harald Cram\'er and the distribution of prime numbers},
journal={Scand. Actuar. J.},
date={1995},
pages={12\textendash 28},
review={\MR {1349149}},
}
Reference [21]
B. Green and T. Tao, The quantitative behaviour of polynomial orbits on nilmanifolds, Ann. of Math. (2) 175 (2012), no. 2, 465–540, DOI 10.4007/annals.2012.175.2.2. MR2877065, Show rawAMSref\bib{gt-nilmobius}{article}{
author={Green, Ben},
author={Tao, Terence},
title={The quantitative behaviour of polynomial orbits on nilmanifolds},
journal={Ann. of Math. (2)},
volume={175},
date={2012},
number={2},
pages={465\textendash 540},
issn={0003-486X},
review={\MR {2877065}},
doi={10.4007/annals.2012.175.2.2},
}
Reference [22]
B. Green and T. Tao, Linear equations in primes, Ann. of Math. (2) 171 (2010), no. 3, 1753–1850. MR2680398, Show rawAMSref\bib{gt-linearprimes}{article}{
author={Green, Ben},
author={Tao, Terence},
title={Linear equations in primes},
journal={Ann. of Math. (2)},
volume={171},
date={2010},
number={3},
pages={1753\textendash 1850},
review={\MR {2680398}},
}
Reference [23]
B. Green, T. Tao, and T. Ziegler, An inverse theorem for the Gowers $U^{s+1}[N]$-norm, Ann. of Math. (2) 176 (2012), no. 2, 1231–1372, DOI 10.4007/annals.2012.176.2.11. MR2950773, Show rawAMSref\bib{GTZ}{article}{
author={Green, Ben},
author={Tao, Terence},
author={Ziegler, Tamar},
title={An inverse theorem for the Gowers $U^{s+1}[N]$-norm},
journal={Ann. of Math. (2)},
volume={176},
date={2012},
number={2},
pages={1231\textendash 1372},
issn={0003-486X},
review={\MR {2950773}},
doi={10.4007/annals.2012.176.2.11},
}
[24]
H. Halberstam and H.-E. Richert, Sieve methods, Academic Press [A subsidiary of Harcourt Brace Jovanovich, Publishers], London-New York, 1974. London Mathematical Society Monographs, No. 4. MR0424730, Show rawAMSref\bib{HR}{book}{
author={Halberstam, H.},
author={Richert, H.-E.},
title={Sieve methods},
note={London Mathematical Society Monographs, No. 4},
publisher={Academic Press [A subsidiary of Harcourt Brace Jovanovich, Publishers], London-New York},
date={1974},
pages={xiv+364 pp. (loose errata)},
review={\MR {0424730}},
}
[25]
G. H. Hardy and J. E. Littlewood, Some problems of “Partitio numerorum”; III: On the expression of a number as a sum of primes, Acta Math. 44 (1923), no. 1, 1–70, DOI 10.1007/BF02403921. MR1555183, Show rawAMSref\bib{hl}{article}{
author={Hardy, G. H.},
author={Littlewood, J. E.},
title={Some problems of \textquotedblleft Partitio numerorum\textquotedblright ; III: On the expression of a number as a sum of primes},
journal={Acta Math.},
volume={44},
date={1923},
number={1},
pages={1\textendash 70},
issn={0001-5962},
review={\MR {1555183}},
doi={10.1007/BF02403921},
}
Reference [26]
D. R. Heath-Brown, Gaps between primes, and the pair correlation of zeros of the zeta function, Acta Arith. 41 (1982), no. 1, 85–99. MR667711, Show rawAMSref\bib{heath}{article}{
author={Heath-Brown, D. R.},
title={Gaps between primes, and the pair correlation of zeros of the zeta function},
journal={Acta Arith.},
volume={41},
date={1982},
number={1},
pages={85\textendash 99},
issn={0065-1036},
review={\MR {667711}},
}
Reference [27]
A. Hildebrand and H. Maier, Irregularities in the distribution of primes in short intervals, J. Reine Angew. Math. 397 (1989), 162–193. MR993220, Show rawAMSref\bib{hild-maier}{article}{
author={Hildebrand, Adolf},
author={Maier, Helmut},
title={Irregularities in the distribution of primes in short intervals},
journal={J. Reine Angew. Math.},
volume={397},
date={1989},
pages={162\textendash 193},
issn={0075-4102},
review={\MR {993220}},
}
Reference [28]
H. Iwaniec, On the problem of Jacobsthal, Demonstratio Math. 11 (1978), no. 1, 225–231. MR499895, Show rawAMSref\bib{Iw}{article}{
author={Iwaniec, Henryk},
title={On the problem of Jacobsthal},
journal={Demonstratio Math.},
volume={11},
date={1978},
number={1},
pages={225\textendash 231},
issn={0420-1213},
review={\MR {499895}},
}
Reference [29]
J. Kahn, A linear programming perspective on the Frankl-Rödl-Pippenger theorem, Random Structures Algorithms 8 (1996), no. 2, 149–157, DOI 10.1002/(SICI)1098-2418(199603)8:2<149::AID-RSA5>3.3.CO;2-S. MR1607104, Show rawAMSref\bib{kahn}{article}{
author={Kahn, Jeff},
title={A linear programming perspective on the Frankl-R\"odl-Pippenger theorem},
journal={Random Structures Algorithms},
volume={8},
date={1996},
number={2},
pages={149\textendash 157},
issn={1042-9832},
review={\MR {1607104}},
doi={10.1002/(SICI)1098-2418(199603)8:2<149::AID-RSA5>3.3.CO;2-S},
}
Reference [30]
J. Li, K. Pratt, and G. Shakan, A lower bound for the least prime in an arithmetic progression, preprint, arXiv:1607.02543
Reference [31]
H. Maier and M. Th. Rassias, Large gaps between consecutive prime numbers containing perfect $k$-th powers of prime numbers. J. Functional Anal., to appear. arXiv:1512.03936.
Reference [32]
H. Maier and C. Pomerance, Unusually large gaps between consecutive primes, Trans. Amer. Math. Soc. 322 (1990), no. 1, 201–237, DOI 10.2307/2001529. MR972703, Show rawAMSref\bib{MP}{article}{
author={Maier, Helmut},
author={Pomerance, Carl},
title={Unusually large gaps between consecutive primes},
journal={Trans. Amer. Math. Soc.},
volume={322},
date={1990},
number={1},
pages={201\textendash 237},
issn={0002-9947},
review={\MR {972703}},
doi={10.2307/2001529},
}
Reference [33]
J. Maynard, Small gaps between primes, Ann. of Math. (2) 181 (2015), no. 1, 383–413, DOI 10.4007/annals.2015.181.1.7. MR3272929, Show rawAMSref\bib{maynard-gaps}{article}{
author={Maynard, James},
title={Small gaps between primes},
journal={Ann. of Math. (2)},
volume={181},
date={2015},
number={1},
pages={383\textendash 413},
issn={0003-486X},
review={\MR {3272929}},
doi={10.4007/annals.2015.181.1.7},
}
Reference [34]
J. Maynard, Dense clusters of primes in subsets, Compos. Math. 152 (2016), no. 7, 1517–1554, DOI 10.1112/S0010437X16007296. MR3530450, Show rawAMSref\bib{maynard-dense}{article}{
author={Maynard, James},
title={Dense clusters of primes in subsets},
journal={Compos. Math.},
volume={152},
date={2016},
number={7},
pages={1517\textendash 1554},
issn={0010-437X},
review={\MR {3530450}},
doi={10.1112/S0010437X16007296},
}
Reference [35]
J. Maynard, Large gaps between primes, Ann. of Math. (2) 183 (2016), no. 3, 915–933, DOI 10.4007/annals.2016.183.3.3. MR3488739, Show rawAMSref\bib{maynard-large}{article}{
author={Maynard, James},
title={Large gaps between primes},
journal={Ann. of Math. (2)},
volume={183},
date={2016},
number={3},
pages={915\textendash 933},
issn={0003-486X},
review={\MR {3488739}},
doi={10.4007/annals.2016.183.3.3},
}
Reference [36]
J. Pintz, Very large gaps between consecutive primes, J. Number Theory 63 (1997), no. 2, 286–301, DOI 10.1006/jnth.1997.2081. MR1443763, Show rawAMSref\bib{P}{article}{
author={Pintz, J\'anos},
title={Very large gaps between consecutive primes},
journal={J. Number Theory},
volume={63},
date={1997},
number={2},
pages={286\textendash 301},
issn={0022-314X},
review={\MR {1443763}},
doi={10.1006/jnth.1997.2081},
}
Reference [37]
N. Pippenger and J. Spencer, Asymptotic behavior of the chromatic index for hypergraphs, J. Combin. Theory Ser. A 51 (1989), no. 1, 24–42, DOI 10.1016/0097-3165(89)90074-5. MR993646, Show rawAMSref\bib{pippenger}{article}{
author={Pippenger, Nicholas},
author={Spencer, Joel},
title={Asymptotic behavior of the chromatic index for hypergraphs},
journal={J. Combin. Theory Ser. A},
volume={51},
date={1989},
number={1},
pages={24\textendash 42},
issn={0097-3165},
review={\MR {993646}},
doi={10.1016/0097-3165(89)90074-5},
}
[38]
D. H. J. Polymath, Variants of the Selberg sieve, and bounded intervals containing many primes, Res. Math. Sci. 1 (2014), Art. 12, 83, DOI 10.1186/s40687-014-0012-7. MR3373710, Show rawAMSref\bib{polymath8b}{article}{
author={Polymath, D. H. J.},
title={Variants of the Selberg sieve, and bounded intervals containing many primes},
journal={Res. Math. Sci.},
volume={1},
date={2014},
pages={Art. 12, 83},
issn={2197-9847},
review={\MR {3373710}},
doi={10.1186/s40687-014-0012-7},
}
Reference [39]
C. Pomerance, A note on the least prime in an arithmetic progression, J. Number Theory 12 (1980), no. 2, 218–223, DOI 10.1016/0022-314X(80)90056-6. MR578815, Show rawAMSref\bib{Pom}{article}{
author={Pomerance, Carl},
title={A note on the least prime in an arithmetic progression},
journal={J. Number Theory},
volume={12},
date={1980},
number={2},
pages={218\textendash 223},
issn={0022-314X},
review={\MR {578815}},
doi={10.1016/0022-314X(80)90056-6},
}
Reference [40]
R. A. Rankin, The difference between consecutive prime numbers, J. London Math. Soc. S1-11 (1938), no. 4, 242, DOI 10.1112/jlms/s1-13.4.242. MR1574971, Show rawAMSref\bib{R1}{article}{
author={Rankin, R. A.},
title={The difference between consecutive prime numbers},
journal={J. London Math. Soc.},
volume={S1-11},
date={1938},
number={4},
pages={242},
review={\MR {1574971}},
doi={10.1112/jlms/s1-13.4.242},
}
Reference [41]
R. A. Rankin, The difference between consecutive prime numbers. V, Proc. Edinburgh Math. Soc. (2) 13 (1962/1963), 331–332, DOI 10.1017/S0013091500025633. MR0160767, Show rawAMSref\bib{rankin-1963}{article}{
author={Rankin, R. A.},
title={The difference between consecutive prime numbers. V},
journal={Proc. Edinburgh Math. Soc. (2)},
volume={13},
date={1962/1963},
pages={331\textendash 332},
issn={0013-0915},
review={\MR {0160767}},
doi={10.1017/S0013091500025633},
}
Reference [42]
V. Rödl, On a packing and covering problem, European J. Combin. 6 (1985), no. 1, 69–78, DOI 10.1016/S0195-6698(85)80023-8. MR793489, Show rawAMSref\bib{nibble}{article}{
author={R\"odl, Vojt\v ech},
title={On a packing and covering problem},
journal={European J. Combin.},
volume={6},
date={1985},
number={1},
pages={69\textendash 78},
issn={0195-6698},
review={\MR {793489}},
doi={10.1016/S0195-6698(85)80023-8},
}
Reference [43]
A. Schönhage, Eine Bemerkung zur Konstruktion grosser Primzahllücken(German), Arch. Math. (Basel) 14 (1963), 29–30, DOI 10.1007/BF01234916. MR0146154, Show rawAMSref\bib{schonhage}{article}{
author={Sch\"onhage, Arnold},
title={Eine Bemerkung zur Konstruktion grosser Primzahll\"ucken},
language={German},
journal={Arch. Math. (Basel)},
volume={14},
date={1963},
pages={29\textendash 30},
issn={0003-889X},
review={\MR {0146154}},
doi={10.1007/BF01234916},
}
Reference [44]
T. Oliveira e Silva, S. Herzog, and S. Pardi, Empirical verification of the even Goldbach conjecture and computation of prime gaps up to $4\cdot 10^{18}$, Math. Comp. 83 (2014), no. 288, 2033–2060, DOI 10.1090/S0025-5718-2013-02787-1. MR3194140, Show rawAMSref\bib{numerical-tos}{article}{
author={Oliveira e Silva, Tom\'as},
author={Herzog, Siegfried},
author={Pardi, Silvio},
title={Empirical verification of the even Goldbach conjecture and computation of prime gaps up to $4\cdot 10^{18}$},
journal={Math. Comp.},
volume={83},
date={2014},
number={288},
pages={2033\textendash 2060},
issn={0025-5718},
review={\MR {3194140}},
doi={10.1090/S0025-5718-2013-02787-1},
}
Reference [45]
V. H. Vu, New bounds on nearly perfect matchings in hypergraphs: higher codegrees do help, Random Structures Algorithms 17 (2000), no. 1, 29–63, DOI 10.1002/1098-2418(200008)17:1<29::AID-RSA4>3.0.CO;2-W. MR1768848, Show rawAMSref\bib{vanvu}{article}{
author={Vu, Van H.},
title={New bounds on nearly perfect matchings in hypergraphs: higher codegrees do help},
journal={Random Structures Algorithms},
volume={17},
date={2000},
number={1},
pages={29\textendash 63},
issn={1042-9832},
review={\MR {1768848}},
doi={10.1002/1098-2418(200008)17:1<29::AID-RSA4>3.0.CO;2-W},
}
Reference [46]
E. Westzynthius, Über die Verteilung der Zahlen, die zu den $n$ ersten Primzahlen teilerfremd sind, Commentationes Physico-Mathematicae, Societas Scientarium Fennica, Helsingfors 5, no. 25, (1931) 1–37.
The first author was supported by NSF grants DMS-1201442 and DMS-1501982.
The second author was supported by ERC Starting Grant 279438, Approximate algebraic structure, and by a Simons Investigator grant.
The fifth author was supported by a Simons Investigator grant, by the James and Carol Collins Chair, by the Mathematical Analysis & Application Research Fund Endowment, and by NSF grant DMS-1266164.
Note. To explore an equation, focus it (e.g., by clicking on it) and use the arrow keys to navigate its structure. Screenreader users should be advised that enabling speech synthesis will lead to duplicate aural rendering.