A REMARK ON GOLDSTON-YILDIRIM CORRELATION ESTIMATES

TERENCE TAO

Abstract. In recent work of Goldston and Yildirim, correlation estimates for the truncated divisor sums

Λ_{R}(n) = ∑_{d|n;d<R} μ(d) log \frac{R}{d}

were obtained. A key feature of these estimates is that the error term was o(1) of the main term; this played an essential role in the recent establishment in [4] of arbitrarily long arithmetic progressions in the primes.

The correlation estimates were obtained using the theory of the Riemann zeta function, and in particular exploited the non-trivial classical zero-free region {ℜ(z) > 1 − \frac{c}{ℑ(z)}\}. In this note we show that one does not in fact need this region if one wishes to obtain a qualitative result of the same type, and can in fact proceed purely from the elementary fact that the Riemann zeta function has a simple pole of order 1 at z = 1.

The author thanks Alex Kontorovich for some corrections.

1. Products over primes

Consider the Riemann zeta function, defined for ℜ(s) > 1 by the formula

ζ(s) := ∑_{n=1}^{∞} \frac{1}{n^{s}} .

There are many estimates available for this function, but we shall just use a very crude one (which basically asserts that ζ has a simple pole at 1 with residue 1): Lemma 1.1. If ℜ(s) > 1 and s = O(1), then ζ(s) = \frac{1}{s−1} + O(1). Proof. Since

\frac{1}{s − 1} = ∫_{1}^{∞} \frac{dx}{x^{s}} = ∑_{n=1}^{∞} ∫_{n}^{n+1} \frac{dx}{x^{s}}

we see that

\frac{1}{s − 1} − ζ(s) = ∑_{n=1}^{∞}(∫_{n}^{n+1} dx(\frac{1}{x^{s}} − \frac{1}{n^{s}}).

From the mean value theorem and the hypotheses s = O(1), ℜ(s) > 1 we have \frac{1}{x^{s}} − \frac{1}{n^{s}} = O(\frac{1}{n^{2}} ); summing this we obtain the claim.

From unique factorization we have the Euler product formula

ζ(s) = ∏_{p}(1 + \frac{1}{p^{s}} + \frac{1}{p^{2s}} + …) = ∏_{p}(1 − \frac{1}{p^{s}})^{−1}

1991 Mathematics Subject Classification. 11N13, 11B25, 374A5. The author is a Clay Prize Fellow and is supported by a grant from the Packard Foundation. Thanks

to Le Thai Hoang for corrections.

and thus we have

∏_{p}(1 − \frac{1}{p^{s}})^{−1} = \frac{1}{s − 1} + O(1)

when ℜ(s) > 1 and s = O(1). Taking reciprocals, we obtain the crude formula

∏_{p}(1 − \frac{1}{p^{s}}) = (1 + o(1))(s − 1)  (1.1)

when ℜ(s) > 1 and s = 1 + o(1).

The formula (1.1) is incredibly primitive when compared with modern knowledge of the zeta function (let alone what we could say once we have the Riemann hypothesis), yet it is still enough to give good control on certain functions adapted to the “almost primes”, as we shall soon see. We begin by modifying (1.1) to handle several other products over primes.

Lemma 1.2. Let s_{1}, …, s_{k} be complex numbers such that ℜ(s_{j}) > 1 and s_{j} = 1 + o(1) for all 1 ⩽ j ⩽ k. For each prime p, let c_{p,1}, …, c_{p,k} be bounded complex numbers (thus c_{p,j} = O(1) for all p, j), and let c_{1}, …, c_{k} be integers with the property that c_{p,j} = c_{j} for all primes p outside of a finite set P. Then

∏_{p}(1 − ∑_{j=1}^{k} \frac{c_{p,j}}{p^{s_{j}}}) = (G + o_{k}(H)) ∏_{j=1}^{k}(s_{j} − 1)^{c_{j}}

where G is the “arithmetic factor”

G = ∏_{p} \frac{1 − (∑_{j=1}^{k} c_{p,j})/p}{(1 − 1/p)^{c_{1}+...+c_{k}}}

(note that the factors are 1 + O_{k}(1/p^{2}) for all p ∉ P, and so this product is convergent), and H is the quantity

H = exp(O_{k}(∑_{p∈P} \frac{1}{p})).

We remark that while H can get somewhat large, this is quite rare because the sum ∑_{p} \frac{1}{p} is only very slowly divergent and in general P will be quite sparse (typically P will be the set of prime factors of a given number). One can improve the error term o_{k}(H) substantially, for instance by using the standard zero-free region for the zeta function, but this crude estimate will suffice for our application. Proof. Since [1 − (∑_{j=1}^{k} c_{p,j})/p]/(1 − 1/p)^{c_{1}+...+c_{n}} is bounded by 1 + O_{k}(1/p^{2}) when p ∉ P and by 1 + O_{k}(1/p) when p ∈ P, we see that G = O_{k}(H). From (1.1) we have

∏_{p} ∏_{j=1}^{k}(1 − 1/p^{s_{j}})^{c_{j}} = (1 + o_{k}(1)) ∏_{j=1}^{k}(s_{j} − 1)^{c_{j}}

and so it suffices to show that

∏_{p} \frac{1 − ∑_{j=1}^{k} \frac{c_{p,j}}{p^{s_{j}}}}{∏_{j=1}^{k}(1 − 1/p^{s_{j}})^{c_{j}}} = G + o_{k}(H).

When p ∉ P, Taylor expansion shows

\frac{1 − ∑_{j=1}^{k} \frac{c_{p,j}}{p^{s_{j}}}}{∏_{j=1}^{k}(1 − 1/p^{s_{j}})^{c_{j}}} = 1 + O_{k}(1/p^{2})

whereas a computation of the derivative (or log-derivative) in the s_{j} variables shows

\frac{1 − ∑_{j=1}^{k} \frac{c_{p,j}}{p^{s_{j}}}}{∏_{j=1}^{k}(1 − 1/p^{s_{j}})^{c_{j}}} = \frac{1 − ∑_{j=1}^{k} \frac{c_{p,j}}{p}}{(1 − 1/p)^{c_{1}+...+c_{k}}} + o_{k}(log p/p^{2});

similarly, when p ∈ P, we have

\frac{1 − ∑_{j=1}^{k} \frac{c_{p,j}}{p^{s_{j}}}}{∏_{j=1}^{k}(1 − 1/p^{s_{j}})^{c_{j}}} = \frac{1 − ∑_{j=1}^{k} \frac{c_{p,j}}{p}}{(1 − 1/p)^{c_{1}+...+c_{k}}} + o_{k}(log p/p) = 1 + O_{k}(1/p),

and the claim follows by multiplying all these estimates together, extracting the main term of G, and bounding everything else by o_{k}(H).

We can specialize this lemma to estimate certain arithmetic sums. Recall the Möbius function μ(d), defined to equal (−1)^{k} when d is the product of k distinct prime factors, and equal to zero otherwise (i.e. when n is not square-free).

Proposition 1.3. For each set I ⊆ {1, …, k} and each prime p, let c_{p,I} be a bounded complex number such that c_{p,∅} = 1. Suppose there is a finite set of primes P such that c_{p,I} = c_{I} for all p ∉ P and all sets I. Let g(d_{1}, …, d_{k}) denote the function

g(d_{1}, …, d_{k}) := ∏_{p} c_{p,{1⩽j⩽k:p|d_{j}}}

and let [d_{1}, …, d_{k}] denote the least common multiple of d_{1}, …, d_{k}. Let z_{1}, …, z_{k} be complex numbers such that ℜ(z_{j}) > 0 and z_{j} = o(1) for 1 ⩽ j ⩽ k. Then we have

∑_{d_{1},...,d_{k}∈ℤ^{+}} \frac{g(d_{1}, …, d_{k})}{[d_{1}, …, d_{k}]} ∏_{j=1}^{k} \frac{μ(d_{j})}{d_{j}^{z_{j}}} = (G + o_{k}(H)) ∏_{I⊆\{1,...,k\}:I≠∅}(∑_{j∈I} z_{j})^{(−1)^{|I|+1}c_{I}}

where G is the “arithmetic factor”

G = ∏_{p}(1 + ∑_{I⊆{1,...,k}:I≠∅}(−1)^{|I|}c_{p,I}/p)(1 − 1/p)^{∑_{I⊆{1,...,k}:I≠∅}(−1)^{|I|}c_{I}}

and

H = exp(O_{k}(∑_{p∈P} \frac{1}{p})).

Proof. By unique factorization, the left-hand side factorizes as

∏_{p}( ∑_{d_{1},...,d_{k}∈p^{ℕ}} \frac{g(d_{1}, …, d_{k})}{[d_{1}, …, d_{k}]} ∏_{j=1}^{k} \frac{μ(d_{j})}{d_{j}^{z_{j}}})

where p^{ℕ} = {1, p, p^{2}, …} are the powers of p. Actually, the factors μ(d_{j}) ensure that we may restrict d_{1}, …, d_{k} to the two-element set {1, p}. Because ℜ(z_{1}), …, ℜ(z_{k}) > 0, the expression inside the product is 1 + O_{k}(1/p^{1+ε}) for some ε > 0 and so the product is absolutely convergent. Letting I denote the set of indices j such that d_{j} = p and isolating the I = ∅ case, we can thus rewrite the above expression as

∏_{p} 1 − ∑_{I⊆\{1,...,k\}:I≠∅} \frac{(−1)^{|I|+1}c_{p,I}}{p^{1+∑_{j∈I} z_{j}}} .

The claim now follows from the previous lemma.

These estimates, combined with some Fourier analysis and the Chinese remainder theorem, will allow us to prove correlation estimates for (smoothed out) Goldston-Yildirim sums, which we turn to next.

2. Goldston-Yildirim sums

The von Mangoldt function Λ(n), defined to equal log p when n is a power of a prime p and zero otherwise, plays a key role in the analytic number theory of the prime numbers; for instance, the prime number theorem can be restated in an equivalent form as

∑_{n⩽N} Λ(n) = (1 + o_{N→∞}(1))N.

However, higher order correlations of this function are still very poorly understood. For instance, it is not even known whether the sum

∑_{n=1}^{∞} Λ(n)Λ(n + 2)

is infinite or not; this is essentially equivalent to the twin prime conjecture.

However, one can obtain much better estimates if one replaces the function Λ (which essentially localizes to the primes) by a somewhat “smoother” function, which essentially localizes to almost primes - numbers which do not contain any prime factors less than R, for some threshold R (typically equal to a small power of the range N of primes under consideration). This is of course one of the principal ideas underlying the ideas of sieve theory. There are many ways to obtain functions localized to the almost primes. One way, studied by Goldston and Yildirim [1], [2], [3], is to begin with the familiar formula

Λ(n) = ∑_{d|n} μ(d) log \frac{n}{d},

and then introduce the truncated divisor sums

Λ_{R}(n) = ∑_{d|n:d<R} μ(d) log \frac{R}{d}.

One can easily check, for instance, that Λ_{R}(n) = log R if n is an almost prime (i.e. has no prime factors less than R). It is then possible to obtain correlation asymptotics for these functions. For instance, in [2] the estimates

∑_{n=1}^{N} Λ_{R}(n + j_{1}) … Λ_{R}(n + j_{k}) = (C_{k}(a)G(j) + o_{R→∞;k}(1))N log^{k−r} R + O_{k}(R^{k})

for any integers j_{1}, …, j_{k}, where r := |{j_{1}, …, j_{k}}| is the number of distinct integers occupied by the j_{1}, …, j_{k}, where G(j) is the standard arithmetic factor

G(j) := ∏_{p}(1 − \frac{1}{p})^{−r}(1 − \frac{ν_{p}(j)}{p}),

1 ⩽ ν_{p}(j) ⩽ r is the number of distinct residue classes in ℤ/pℤ occupied by j_{1}, …, j_{k}, and C_{k}(a) is an in principle computable rational number depending only on k and the multiplicities a_{1}, …, a_{r} of the j_{1}, …, j_{k} (i.e. if the set {j_{1}, …, j_{k}} is arranged in order as {J_{1}, …, J_{r}}, then a_{m} is the number of times the value J_{m} is attained). The O(R^{k}) error ensures that we must keep R to be at most a small power of N in order for this asymptotic to be useful. It is worth noting that the error term o_{k}(1) does not depend on the shifts j. The argument proceeded by rewriting the left-hand side as a multiple contour integral involving Riemann zeta functions, and estimating that using shifting of the contour, as well as the classical zero-free region of the Riemann zeta function.

In this note we show that one can achieve qualitatively similar results without recourse to contour shifting or to zero-free regions (other than that given by Lemma 1.1). The only catch is that one must mollify the truncated divisor sums, introducing the functions

Λ_{R,χ}(n) = log R ∑_{d|n:d<R} μ(d)χ(\frac{log d}{log R}),

where χ : ℝ → ℝ is a smooth function which is supported on the interval [−1, 1]. (The original function Λ_{R} then corresponds to the triangular function χ(x) := max(1−|x|, 0), which is Lipschitz continuous but not smooth). Our main result here is then to establish the estimate

∑_{n=1}^{N} Λ_{R,χ}(n+j_{1}) … Λ_{R,χ}(n+j_{k}) = (C_{k,χ}(a)G(j)+o_{R→∞;k,χ}(H(j)))N log^{k−r} R+O_{k,χ}(R^{k} log^{k} R)

(2.1)

for some explicitly computable quantities C_{k,χ}(a), and where H is the quantity

H = exp(O_{k}( ∑ ; p| ∏_{1⩽i<i′⩽k} |j_{i}−j_{i′}| 1/p)).

The log^{k} R factor on the right can be eliminated by sieve theory techniques but we will not do so here to keep the exposition simple. This result can be used as a substitute for the Goldston-Yildirim result in [4]. (A related “linear forms” estimate, also used in [4], can also be deduced by a modification of the method).

2.1. Elimination of N. The first task is to eliminate the role of the parameter N. By substituting the formula for Λ_{R,χ}(n), we can rewrite the left-hand side of (2.1) as

log^{k} R ∑_{d_{1},...,d_{k}⩽R}(∏_{m=1}^{k} μ(d_{m})χ(\frac{log d_{m}}{log R})) ∑_{1⩽n⩽N:d_{1}|n+j_{1};...d_{k}|n+j_{r}} 1.

But from the Chinese remainder theorem we have

∑_{1⩽n⩽N:d_{1},...,d_{k}|n} 1 = \frac{Ng(d_{1}, …, d_{k})}{[d_{1}, …, d_{k}]} + O(1)

where [d_{1}, …, d_{k}] is the least common multiple of d_{1}, …, d_{k}, and g(d_{1}, …, d_{k}) is the number of solutions in ℤ/[d_{1}, …, d_{k}]ℤ to the equations d_{1}|n + j_{1}, …, d_{k}|n + j_{r}; note from the definition of least common multiple that g is always either 0 or 1. The error term O(1) will contribute at most O_{k,χ}(R^{k} log^{k} R) by very crude estimates, and so we are reduced to showing that

∑_{d_{1},...,d_{k}} \frac{g(d_{1}, …, d_{k}) ∏_{m=1}^{k} μ(d_{m})χ(\frac{log d_{m}}{log R})}{[d_{1}, …, d_{k}]} = (C_{k,χ}(a)G(j) + o_{R→∞;k,χ}(H(j))) log^{−r} R.

(2.2)

Note that we have dropped the restriction d_{1}, …, d_{k} ⩽ R as it is already incorporated into the χ cutoff.

2.2. Fourier expansion. The next step is to Fourier expand χ(x), or more precisely the function e^{x}χ(x), which is still smooth and compactly supported. Such a Fourier expansion allows us to write

e^{x}χ(x) = ∫_{−∞}^{∞} ψ(t)e^{−ixt} dt

for some function ψ (depending on χ, of course) which is rapidly decreasing, i.e. obeys the bounds ψ(t) = O_{A}((1 + |t|)^{−A}) for any A > 0. In particular we have

χ(\frac{log d_{m}}{log R}) = d_{m}^{−(1+it)/ log R} ∫_{−∞}^{∞} ψ(t) dt.

We truncate this integral^{1} at [− log^{1/2} R, log^{1/2} R], using the rapid decrease of ψ, to obtain

χ(\frac{log d_{m}}{log R}) = ∫_{− log^{1/2} R}^{log^{1/2} R} d_{m}^{−(1+it_{m})/ log R}ψ(t_{m}) dt_{m} + O_{A,ϵ,χ}(d_{m}^{−1/ log R} log_{R}^{−A})

for any A > 0.

The contribution of the error terms O_{A,χ}(log_{R}^{−A}) to (2.2) is at most

O_{A,χ,k}(log_{R}^{−A} ∑_{d_{1},...,d_{k}} \frac{1}{[d_{1}, …, d_{k}](d_{1} … d_{k})^{1/ log R}}).

We can expand the sum as an Euler product

∑_{d_{1},...,d_{k}} \frac{1}{[d_{1}, …, d_{k}](d_{1} … d_{k})^{1/ log R}} = ∏_{p} ∑_{d_{1},...,d_{k}∈p^{ℤ_{+}}} \frac{1}{[d_{1}, …, d_{k}](d_{1} … d_{k})^{1/ log R}}

where p^{ℤ_{+}} = {1, p, p^{2}, p^{3}, …} are the powers of p. An easy calculation shows that

∑_{d_{1},...,d_{k}∈p^{ℤ_{+}}} \frac{1}{[d_{1}, …, d_{k}](d_{1} … d_{k})^{1/ log R}} = (1 − \frac{1}{p^{1+1/ log R}})^{−k}(1 + O_{k}(1/p^{2}))

(because the terms where [d_{1}, …, d_{k}] = 1 or [d_{1}, …, d_{k}] = p will dominate) and so

∑_{d_{1},...,d_{k}} \frac{1}{[d_{1}, …, d_{k}](d_{1} … d_{k})^{1/ log R}} = (∏_{p}(1 − \frac{1}{p^{1+1/ log R}}))^{−k}(∏_{p}(1 + O_{k}(1/p^{2})).

1This is the one step which differs from the Goldston-Yildirim argument, and which allows us to avoid using any knowledge of the Riemann zeta function ζ(s) outside of the interval s = 1 + \frac{1}{log R} + it for |t| ⩽ log^{−1/2} R.

The second product is convergent to O_{k}(1), while the first product is equal to ζ(1 + 1/ log R)^{k} = O_{k}(log^{k} R), and so thanks to the log^{−A} R factor, this error term is bounded (and in particular the sum we were manipulating was in fact absolutely convergent). Thus we can eliminate all the error terms and reduce to showing that

∫_{− log^{1/2} R}^{log^{1/2} R} … ∫_{− log^{1/2} R}^{log^{1/2} R} ∑_{d_{1},...,d_{k}} g(d_{1}, …, d_{k})\frac{∏_{m=1}^{k} μ(d_{m})d_{m}^{−(1+it_{m})/ log R}}{[d_{1}, …, d_{k}]} ∏_{m=1}^{k} ψ(t_{m}) dt_{m}

= (C_{k,χ}(a)G(j) + o_{R→∞;k,χ}(H(j))) log^{−r} R. (2.3)

Note that the previous computation ensured that we had enough absolute convergence to justify interchanging sums and integrals.

2.3. Conclusion of argument. Observe from the Chinese remainder theorem that

g(d_{1}, …, d_{k}) := ∏_{p} c_{p,{1⩽j⩽k:p|d_{j}}}

where c_{p,I} is defined to equal 1 if j_{i} = j_{i′} mod p for all i, i′ ∈ I, and equal to zero otherwise. If we let P be the set of all primes which divide a non-zero difference of the form j_{i} − j_{i′}, we then see that P is finite and c_{p,I} = c_{I} for all p ∉ P, where c_{I} is defined to equal 1 if j_{i} = j_{i′} for all i ∈ I, and equal to zero otherwise. We can then apply Proposition 1.3 to obtain

∑_{d_{1},...,d_{k}} g(d_{1}, …, d_{k})\frac{∏_{m=1}^{k} μ(d_{m})d_{m}^{−(1+it_{m})/ log R}}{[d_{1}, …, d_{k}]} = (G+o_{k}(H(j))) ∏_{I⊆\{1,...,k\}:I≠∅}(∑_{j∈I} \frac{1 + it_{j}}{log R})^{(−1)^{|I|+1}c_{I}}

(2.4)

where G is the “arithmetic factor”

G := ∏_{p}(1 + ( ∑_{I⊆{1,...,k}:I≠∅}(−1)^{|I|}c_{p,I}/p)(1 − 1/p)^{∑_{I⊆{1,...,k}:I≠∅}(−1)^{|I|}c_{I}}

and

H(j) := exp(O_{k}(∑_{p∈P} \frac{1}{p})).

Let us simplify this expression a little bit, beginning with the computation of the expression

∑_{I⊆{1,...,k}:I≠∅}(−1)^{|I|}c_{I}.

Observe that this can be rewritten as

∑_{b∈ℤ} ∑_{I⊆{1⩽i⩽k:j_{i}=b}:I≠∅}(−1)^{|I|}

which by the binomial formula can be rewritten as

∑_{b∈ℤ}[(1 − 1)^{|{1⩽i⩽k:j_{i}=b}|} − 1).

Recalling that r is the number of distinct integers j_{i}, this expression is thus −r. A similar computation gives

∑_{I⊆{1,...,k}:I≠∅}(−1)^{|I|}c_{p,I} = −ν_{p}(j)

where ν_{p}(j) is the number of distinct residue classes j_{i} mod p. We can thus write (2.4) as

log^{−r} R(G(j) + o_{k}(H(j)))) ∏_{I⊆{1,...,k}:I≠∅}(∑_{j∈I}(1 + it_{j}))^{(−1)^{|I|+1}c_{I}}.

Thus the left-hand side of (2.3) can be written as

log^{−r} R ∫_{− log^{1/2} R}^{log^{1/2} R} … ∫_{− log^{1/2} R}^{log^{1/2} R}(G(j)+o_{k}(H(j)))) ∏_{I⊆{1,...,k}:I≠∅}(∑_{j∈I}(1+it_{j}))^{(−1)^{|I|+1}c_{I}} ∏_{m=1}^{k} ψ(t_{m}) dt_{m}.

But the rapid decay of the ψ ensures that this integral is rapidly convegent, and we may replace the limits of integration here by ℝ at the cost of o(1) factors. Thus we obtain (2.3) as desired, with

C_{k,χ}(a) := ∫_{ℝ} … ∫_{ℝ} ∏_{I⊆{1,...,k}:I≠∅}(∑_{j∈I}(1 + it_{j}))^{(−1)^{|I|+1}c_{I}} ∏_{m=1}^{k} ψ(t_{m}) dt_{m}.

This expression depends only on ψ (which in turn depends on χ) and on the multiplicities a_{1}, …, a_{r}. Indeed we see that we may factor

C_{k,χ}(a) = ∏_{i=1}^{r} C_{χ}(a_{i})

where

C_{χ}(a) := ∫_{ℝ} … ∫_{ℝ} ∏_{I⊆{1,...,a}:I≠∅}(∑_{j∈I}(1 + it_{j}))^{(−1)^{|I|+1}} ∏_{m=1}^{a} ψ(t_{a}) dt_{a}

which can be computed explicitly for various choices of χ; for instance when χ(x) = max(1 − |x|, 0) then the first few of these numbers were computed in [2].

References

[1] D. Goldston and C.Y. Yildirim Higher correlations of divisor sums related to primes, I: Triple correlations, Integers 3 (2003) A5, 66pp.

[2] , Higher correlations of divisor sums related to primes, III: k-correlations, preprint (available at AIM preprints)

[3] , Small gaps between primes, I, preprint.

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

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

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