A BOUND FOR PROGRESSIONS OF LENGTH k IN THE PRIMES

BEN GREEN AND TERENCE TAO

Abstract. From our paper in [1], we extract a quantitative upper bound for the size of the first arithmetic progression of primes of length k; the argument shows that those primes are bounded by an exponential tower in k of height seven.

1. Notation

We assume complete familiarity with our paper [1], and all equations, Lemmas, etc. refer to that paper.

We use x ↑ y as shorthand for x^{y}. Similarly x ↑ y ↑ z for x^{y^{z}}, etc.

We will take w = w(k) to be a fixed large number depending only on k (as opposed to depending on N as is done in the main argument). The quantity W is basically e^{w}. The quantity W/ϕ(W) is basically log w.

2. Quantitative bounds for the Goldston-Yildirim estimates

The purpose of this section is to quantify the dependence of constants in Propositions 8.5 and 8.6. For us the parameters m and t are exponential in k, thus at most 2 ↑ O(k); we can thus set R to be N ↑ 2 ↑ −O(k), and σ to be 2 ↑ −O(k). In Lemma 10.1 we can then take β = 2 ↑ −O(k).

In Lemma 10.2, the quantity B is always O(1). we can take δ to be \sqrt{β}/4, and thus δ = 2 ↑ −O(k). The factor of (β log R)^{B/2} can then be absorbed as long as N is sufficiently large, e.g. N ≫ 2 ↑ 2 ↑ 2 ↑ O(k) will certainly work here; in that case we can take the O_{B}(1) bound in (10.2) to just be O(1). The bound in (10.3) is also O(1).

In Lemma 10.3, the bounds O_{m}(1) can in fact just be O(1) by taking N large again, for instance N ≫ 2 ↑ 2 ↑ 2 ↑ O(k).

In Lemma 9.4, the factors of O_{m,δ}(1) that we lose are at most δ^{−O(m)}, which is 2 ↑ 2 ↑ O(k). The second factor of O_{m,δ}(1) can thus be absorbed by shrinking δ and assuming N ≫ 2 ↑ 2 ↑ 2 ↑ O(k).

Now we begin the inspection of the proof of Proposition 8.5. The first large constants appear in Lemma 9.3. Here the C^{m} bounds on G_{1} are of the form m^{O(m)}, which is 2 ↑ 2 ↑ O(k). The o_{m}(1) error is of the form m^{O(m)}O(w^{−1/O(m)}), which is at most w ↑ −1/(2 ↑ 2 ↑ O(k)) if we assume w ≫ 2 ↑ 2 ↑ 2 ↑ O(k). The bound on G_{2} is like O(mw) ↑ O(mw), which is 2 ↑ w ↑ O(1) again taking w ≫ 2 ↑ 2 ↑ 2 ↑ O(k). Putting this together we see that the C^{m} bounds for G_{1} are also of the form 2 ↑ w ↑ O(1); this allows one to make the hypothesis (9.10) obeyed with bounded constants if N ≫ 2 ↑ w ↑ O(1).

Of the two error terms in Lemma 9.4, the first is the larger one, contributing O(∥G∥_{C^{m}}/ log R) to the o_{m,t}(1) term in (9.2). By the preceding estimates, this error is basically (2 ↑ w ↑ O(1))/ log N, which will be certainly smaller than w ↑ −1/(2 ↑ 2 ↑ O(k)) if N ≫ 2 ↑ 2 ↑ w ↑ O(1). The other error term to (9.1) is much smaller for this range of N and w and can thus be ignored. We have thus obtained a quantitative error term of w ↑ −1/(2 ↑ 2 ↑ O(k)) assuming that w ≫ 2 ↑ 2 ↑ 2 ↑ O(k) and N ≫ 2 ↑ 2 ↑ w ↑ O(1).

1991 Mathematics Subject Classification. 11N13, 11B25, 374A5.

The first author is a PIMS postdoctoral fellow at the University of British Columbia, Vancouver, Canada. The second author is a Clay Prize Fellow and is supported by a grant from the Packard Foundation.

Now we turn to Proposition 8.6. In (9.12), the constants O_{m}(1) are of the form m ↑ O(m) = 2 ↑ 2 ↑ O(k). Similarly in (9.13), but we can eliminate those constants by taking N large (we are already needing N ≫ 2 ↑ 2 ↑ 2 ↑ 2 ↑ 2 ↑ O(k), and this is more than sufficient). Now consider the three terms used to estimate (9.5) at the end of the argument. The third term is very small compared to the second and will be ignored. The second term contributes an error of the form (2 ↑ w ↑ O(1))/ log log N, which will be O(1) if N ≫ 2 ↑ 2 ↑ 2 ↑ w ↑ O(1). We can then replace the right-hand side of (8.1) by

O(1)(\frac{W log R}{ϕ(W)})^{m} ∏_{p|Δ}(1 + (2 ↑ 2 ↑ O(k))p^{−1/2})

(estimating the o_{m}(1) term crudely by O(1)).

Note that we already need

N ≫ 2 ↑ 2 ↑ 2 ↑ 2 ↑ 2 ↑ 2 ↑ O(k)

and

w ≫ 2 ↑ 2 ↑ 2 ↑ O(k).

Finally, we observe that the density δ := k^{−1}2^{−k−5}ϵ_{k} we need in the proof of Theorem 1.1 is 2 ↑ −k ↑ O(1), so by Gowers’ estimate, the quantity c(k, δ) is

c(k, δ) = 2 ↑ −2 ↑ 2 ↑ 2 ↑ O(k).

Thus the ε we need in the proof of Theorem 3.5 is also

ε = 2 ↑ −2 ↑ 2 ↑ 2 ↑ O(k),

and the maximal number of steps K_{0} in the Furstenberg tower is

K_{0} = 2 ↑ 2 ↑ 2 ↑ 2 ↑ O(k).

3. Pseudorandomness bounds

Now we can quantify the pseudorandomness of ν. We begin with the linear forms condition. We are certainly taking w large enough so that \sqrt{w}/2 > (k + 1)!. All the O_{m,t}(1) bounds are at most 2 ↑ 2 ↑ O(k), and if we take Q := w ↑ −1/(2 ↑ 2 ↑ O(k)), one can then replace the o(1) error in the linear forms condition by w ↑ −1/(2 ↑ 2 ↑ O(k)).

Now we look at Lemma 8.9. As computed earlier, the O_{m}(1) constants are 2 ↑ 2 ↑ O(k), which effectively replaces q by q̃:= (2 ↑ 2 ↑ O(k))q (this is the O_{m}(q) expression in the text). The final O_{m,q}(1) bound is polynomial in 2 ↑ q̃ ↑ O(1), and thus

𝔼(τ^{q}) ⩽ 2 ↑ 2 ↑ 2 ↑ O(k) + 2 ↑ q ↑ O(1).

4. Uniformity and anti-uniformity

Now we quantify Sections 5,6. The o(1) bound in Lemma 5.2 comes from the linear forms condition and is thus w ↑ −1/(2 ↑ 2 ↑ O(k)). Similarly for the Von Neumann theorem, Proposition 5.3, as well as the uniform bound in (6.5) (at this point w is so huge that the exponential factors of k appearing are negligible).

Now look at Lemma 6.3. Assume the coefficients of P are bounded by some M; then we lose a factor of Md^{K} in order to reduce to the dK-monomial. Applying the correlation condition with q = dK we thus see that

O_{K,d,P} (1) ⩽ Md^{K}(2 ↑ 2 ↑ 2 ↑ O(k) + 2 ↑ dK ↑ O(1)).

Now turn to Lemma 6.5. The bound for (6.9) is of the form O(ε^{−2K}σ^{1/100}). Next, we observe that the function Φ is essentially the K^{th} tensor power of a σ-smoothed out indicator of the unit cube, rescaled by ε. One can approximate this fairly well (up to errors of O(K)σ) by a polynomial of degree d = O(Kσ^{−O(1)}) and coefficients M = 2 ↑ O(Kσ^{−O(1)}). Thus

𝔼((ν − 1)Φ) ⩽ O(K)σ + Md^{K}(2 ↑ 2 ↑ 2 ↑ O(k) + 2 ↑ dK ↑ O(1))w ↑ −1/(2 ↑ 2 ↑ O(k)).

Write K′ := max(K, 2 ↑ 2 ↑ O(k)), then this simplifies a bit to

𝔼((ν − 1)Φ) ⩽ O(K′)σ + 2 ↑ ((K′)^{O(1)}σ^{−O(1)}) × w ↑ −1/(2 ↑ 2 ↑ O(k)).

If one then sets σ := (K′)^{O(1)}(log log N)^{−c}, we thus obtain

𝔼((ν − 1)Φ) ⩽ (K′)^{O(1)}w ↑ −1/(2 ↑ 2 ↑ O(k))

and thus the bound in (6.10) is also of the form (K′)^{O(1)}w ↑ −1/(2 ↑ 2 ↑ O(k)), while the bound in (6.9) is O(ε^{−2K′}(K′)^{O(1)}w ↑ −1/(2 ↑ 2 ↑ O(k)). Inserting our bounds for ε and K_{0} from the Furstenberg argument, we thus obtain a bound of

(2 ↑ 2 ↑ 2 ↑ 2 ↑ O(k))w ↑ −1/(2 ↑ 2 ↑ O(k))

for (6.10) and

(2 ↑ 2 ↑ 2 ↑ 2 ↑ 2 ↑ O(k))w ↑ −1/(2 ↑ 2 ↑ O(k))

for (6.9). Both of these are at most w ↑ −1/(2 ↑ 2 ↑ O(k)) if we assume

w ≫ 2 ↑ 2 ↑ 2 ↑ 2 ↑ 2 ↑ O(k)

and hence

N ≫ 2 ↑ 2 ↑ w ↑ O(1) ≫ 2 ↑ 2 ↑ 2 ↑ 2 ↑ 2 ↑ 2 ↑↑ O(k).

This is also ensures that the errors o_{j,ε}(1) in the Furstenberg tower construction are manageable (i.e. smaller than ε). Also with N this large it is clear that c(k, δ)N^{2} is much larger than N, and so we have shown that a non-trivial progression of primes of length k exists with all primes less than

O(NW) ⩽ 2 ↑ 2 ↑ 2 ↑ 2 ↑ 2 ↑ 2 ↑ 2 ↑ O(k).

It is likely that the implicit constant in O(k) is quite manageable, e.g. 100k will certainly suffice, basically because almost all of the O(1) bounds encountered in the above analysis will eventually be hit with several logarithms.

References

[1] B.J. Green and T. Tao, The primes contain arbitrarily long arithmetic progressions, preprint.

Pacific Institute for the Mathematical Sciences, Room 205, 1933 West Mall, University of British Columbia, Vancouver BC, Canada,

E-mail address: bjg23@hermes.cam.ac.uk

Department of Mathematics, University of California at Los Angeles, Los Angeles CA 90095

E-mail address: tao@math.ucla.edu