HIGHER CORRELATIONS OF DIVISOR SUMS RELATED TO PRIMES I: TRIPLE CORRELATIONS

D. A. Goldston^{1}

Department of Mathematics and Computer Science, San Jose State University, San Jose, CA 95192

                        goldston@mathcs.sjsu.edu

C. Y. Yıldırım

Department of Mathematics, Bog̃aziçi University, Istanbul 34342, Turkey

                           yalciny@boun.edu.tr

Received: 4/29/02, Revised: 4/18/03, Accepted: 4/18/03, Published: 4/22/03

Abstract

We obtain the triple correlations for a truncated divisor sum related to primes. We also obtain the mixed correlations for this divisor sum when it is summed over the primes, and give some applications to primes in short intervals.

1. Introduction

This is the first in a series of papers concerned with the calculation of higher correlations of short divisor sums that are approximations for the von Mangoldt function Λ(n), where Λ(n) is defined to be log p if n = p^{m}, p a prime, m a positive integer, and to be zero otherwise. These higher correlations have applications to the theory of primes which is our motivation for their study. In this first paper we will calculate the pair and triple correlations for

Λ_{R}(n) = ∑_{{d|n \atop d≤R}} μ(d) log(R/d),  for n ≥ 1,  (1.1)

and Λ_{R}(n) = 0 if n ≤ 0. In later papers in this series we will examine quadruple and higher correlations, and also examine the more delicate divisor sum

λ_{R}(n) = ∑_{r≤R} \frac{μ^{2}(r)}{ϕ(r)} ∑_{{d|r \atop d|n}} dμ(d),  for n ≥ 1,  (1.2)

1The first author was supported in part by an NSF Grant

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 3 (2003), #A05 2

and λ_{R}(n) = 0 if n ≤ 0. The correlations we are interested in evaluating are

S_{k}(N, j, a) = ∑_{n=1}^{N} Λ_{R}(n + j_{1})^{a_{1}}Λ_{R}(n + j_{2})^{a_{2}} ⋯ Λ_{R}(n + j_{r})^{a_{r}}  (1.3)

and

S̃_{k}(N, j, a) = ∑_{n=1}^{N} Λ_{R}(n + j_{1})^{a_{1}}Λ_{R}(n + j_{2})^{a_{2}} ⋯ Λ_{R}(n + j_{r−1})^{a_{r−1}}Λ(n + j_{r})  (1.4)

where j = (j_{1}, j_{2}, …, j_{r}) and a = (a_{1}, a_{2}, … a_{r}), the j_{i}’s are distinct integers, a_{i} ≥ 1 and ∑_{i=1}^{r} a_{i} = k. In (1.4) we assume that r ≥ 2 and take a_{r} = 1. For later convenience we define

S̃_{1}(N, j, a) = ∑_{n=1}^{N} Λ(n + j_{1}) ∼ N  (1.5)

with |j_{1}| ≤ N by the prime number theorem. For k = 1 and k = 2 these correlations have been evaluated before [8] (and for λ_{Q}(n) they have been evaluated in [9]); the results show that Λ_{R} and λ_{R} mimic the behavior of Λ, and this is also the case in arithmetic progressions, see [17], [18], [11].

When k ≥ 3 the procedure for evaluating these correlations is complicated, and it is easy to make mistakes in the calculations. Therefore we have chosen to first treat the triple correlations in detail. The main terms in the theorems can often be obtained in an easier way by evaluating the multiple sums in a different order or with a different decomposition of the initial summands; the method used here was chosen to control the error terms and generalize to higher correlations. Recently we have found a somewhat different method which is preferable for higher values of k. This method will be used in the third paper in this series. We can not compute correlations which contain a factor Λ(n)Λ(n+k), k ≠ 0, without knowledge about prime twins. This limits our applications, and further the mixed correlations (1.4) can only be calculated for shorter divisor sums than the pure correlations (1.3) of Λ_{R}(n), which degrades to some extent the results we obtain. When we assume the Elliott-Halberstam conjecture we can eliminate this latter problem and obtain stronger results.

One motivation for the study of the correlations of Λ_{R}(n) or λ_{R}(n) is to provide further information on the moments

M_{k}(N, h, ψ) = ∑_{n=1}^{N}(ψ(n + h) − ψ(n))^{k}  (1.6)

where ψ(x) = ∑_{n≤x} Λ(n). We always take N → ∞, and let

h ∼ λ log N,  (1.7)

where we will usually be considering the case λ ≪ 1. When h is larger we need to subtract the expected value h in the moments above, which leads to more delicate questions which we will not consider in this paper (see [23]). Gallagher [6] proved that the moments in (1.6) may be computed from the Hardy-Littlewood prime r-tuple conjecture [14]. This conjecture states that for j = (j_{1}, j_{2}, …, j_{r}) with the j_{i}’s distinct integers,

ψj(N) = ∑_{n=1}^{N} Λ(n + j_{1})Λ(n + j_{2}) ⋯ Λ(n + j_{r}) ∼ 𝔖(j)N  (1.8)

when 𝔖(j) ≠ 0, where

𝔖(j) = ∏_{p} (1 − \frac{1}{p})^{−r} (1 − \frac{ν_{p}(j)}{p})  (1.9)

and ν_{p}(j) is the number of distinct residue classes modulo p that the j_{i}’s occupy. If r = 1 we see 𝔖(j) = 1, and for |j_{1}| ≤ N equation (1.8) reduces to (1.5), which is the only case where (1.8) has been proved. To compute the moments in (1.6) we have

M_{k}(N, h, ψ) = ∑_{n=1}^{N} ( ∑_{1≤m≤h} Λ(n + m))^{k}

= ∑_{{1≤m_{i}≤h \atop 1≤i≤k}} ∑_{n=1}^{N} Λ(n + m_{1})Λ(n + m_{2}) ⋯ Λ(n + m_{k}).

Now suppose that the k numbers m_{1}, m_{2}, …, m_{k} take on r distinct values j_{1}, j_{2}, …, j_{r} with j_{i} having multiplicity a_{i}, so that ∑_{1≤i≤r} a_{i} = k. Grouping the terms above, we have that

M_{k}(N, h, ψ) = ∑_{r=1}^{k} ∑_{a_{1},a_{2},... ,a_{r} ; a_{i}≥1,∑ a_{i}=k} ( \begin{matrix}k \\ a_{1}, a_{2}, …, a_{r} \end{matrix} ) ∑_{1≤j_{1}<j_{2}<···<j_{r}≤h} ψ_{k}(N, j, a), (1.10)

where

ψ_{k}(N, j, a) = ∑_{n=1}^{N} Λ(n + j_{1})^{a_{1}}Λ(n + j_{2})^{a_{2}} ⋯ Λ(n + j_{r})^{a_{r}}  (1.11)

and the multinomial coefficient counts the number of different innermost sums that occur. If n + j_{i} is a prime then Λ(n + j_{i})^{a_{i}} = Λ(n + j_{i})(log(n + j_{i}))^{a_{i}−1}, and we easily see that

ψ_{k}(N, j, a) = (1 + o(1))(log N)^{k−r} ∑_{n=1}^{N} Λ(n + j_{1})Λ(n + j_{2}) ⋯ Λ(n + j_{r}) + O(N^{\frac{1}{2} +ϵ})
= (1 + o(1))(log N)^{k−r}ψj(N) + O(N^{\frac{1}{2} +ϵ}).

(1.12)

Hence we may apply the conjecture (1.8) assuming it is valid uniformly for max_{i} |j_{i}| ≤ h and obtain

M_{k}(N, h, ψ) ∼ N ∑_{r=1}^{k}(log N)^{k−r} ∑_{a_{1},a_{2},... ,a_{r} ; a_{i}≥1,∑ a_{i}=k} ( \begin{matrix}k \\ a_{1}, a_{2}, …, a_{r} \end{matrix} ) ∑_{1≤j_{1}<j_{2}<···<j_{r}≤h} 𝔖(j).

Gallagher [6] proved that, as h → ∞,

∑_{1≤j_{1},j_{2},··· ,j_{r}≤h distinct} 𝔖(j) ∼ h^{r},  (1.13)

and since this sum includes r! permutations of the specified vector j when the components are ordered, we have

M_{k}(N, h, ψ) ∼ N(log N)^{k} ∑_{r=1}^{k} \frac{1}{r!}(\frac{h}{log N})^{r} ∑_{a_{1},a_{2},... ,a_{r} ; a_{i}≥1,∑ a_{i}=k} ( \begin{matrix}k \\ a_{1}, a_{2}, …, a_{r} \end{matrix} ) .

Letting \{ \begin{matrix}k \\ r \end{matrix} \} denote the Stirling numbers of the second type, then it may be easily

verified (see [12]) that

∑_{a_{1},a_{2},... ,a_{r} ; a_{i}≥1,∑ a_{i}=k} ( \begin{matrix}k \\ a_{1}, a_{2}, …, a_{r} \end{matrix} ) = r! \{ \begin{matrix}k \\ r \end{matrix} \} .  (1.14)

We conclude that for h ∼ λ log N,

M_{k}(N, h, ψ) ∼ N(log N)^{k} ∑_{r=1}^{k} \{ \begin{matrix}k \\ r \end{matrix} \} λ^{r},  (1.15)

which are the moments of a Poisson distribution with mean λ. The first 4 moments are, for λ ≪ 1,

M_{1}(N, h, ψ) ∼ λN log N,
M_{2}(N, h, ψ) ∼ (λ + λ^{2})N log^{2} N,
M_{3}(N, h, ψ) ∼ (λ + 3λ^{2} + λ^{3})N log^{3} N,
M_{4}(N, h, ψ) ∼ (λ + 7λ^{2} + 6λ^{3} + λ^{4})N log^{4} N.

The asymptotic formula for the first moment is known to be true as a simple consequence of the prime number theorem. The other moment formulas have never been proved. It is known that the asymptotic formula for the second moment follows from the assumption of the Riemann Hypothesis and the pair correlation conjecture for zeros of the Riemann zeta-function [10].

Turning to our approximation Λ_{R}(n), we define

ψ_{R}(x) = ∑_{n≤x} Λ_{R}(n)  (1.16)

and first wish to examine the moments M(N, h, ψ_{R}) defined as in (1.6). The same computation used for ψ to obtain (1.10) clearly applies and therefore we obtain

M_{k}(N, h, ψ_{R}) = ∑_{r=1}^{k} ∑_{a_{1},a_{2},... ,a_{r} ; a_{i}≥1,∑ a_{i}=k} ( \begin{matrix}k \\ a_{1}, a_{2}, …, a_{r} \end{matrix} ) ∑_{1≤j_{1}<j_{2}<···<j_{r}≤h} S_{k}(N, j, a), (1.17)

where S_{k}(N, j, a) is the correlation given in (1.3). Since Λ_{R}(n) is not supported on the primes and prime powers as Λ(n) is, we can not use (1.12) to reduce the problem to correlations without powers, and as we will see these powers sometimes effect the correlations for Λ_{R}(n). Our main result on these correlations is contained in the following theorem.

Theorem 1.1 Given 1 ≤ k ≤ 3, let j = (j_{1}, j_{2}, …, j_{r}) and a = (a_{1}, a_{2}, … a_{r}), where the j_{i}’s are distinct integers, and a_{i} ≥ 1 with ∑_{i=1}^{r} a_{i} = k. Assume max_{i} |j_{i}| ≪ R^{ϵ} and R ≫ N^{ϵ}. Then we have

S_{k}(N, j, a) = (C_{k}(a)𝔖(j) + o(1))N(log R)^{k−r} + O(R^{k}),  (1.18)

where C_{k}(a) has the values

C_{1}(1) = 1,
C_{2}(2) = 1, C_{2}(1, 1) = 1,
C_{3}(3) = \frac{3}{4}, C_{3}(2, 1) = 1, C_{3}(1, 1, 1) = 1.

Here we have used the notational convention of dropping extra parentheses, so for example C_{2}((1, 1)) = C_{2}(1, 1). The method of proof used in this paper is not limited to k ≤ 3, but it does become extremely complicated even for k = 4. Using the new method mentioned before we will prove Theorem 1.1 holds for all k in the third paper in this series. The computation of the constants C_{k}(a) as k gets larger becomes increasingly difficult. We also believe the error term O(R^{k}) can be improved. This has been done in the case k = 2 (unpublished) where the error term O(R^{2}) may be replaced by O(R^{2−δ}) for a small constant δ. In the special case of S_{2}(N, (0), (2)) Graham [13] has removed the error term O(R^{2}) entirely.

In proving Theorem 1.1 we will assume j_{1} = 0. This may be done without loss of generality since we may shift the sum over n in S_{k} to m = n + j_{1} and then return to the original summation range with an error O(N^{ϵ}) since |j_{1}| ≪ R^{ϵ} and Λ_{R}(n) ≪ n^{ϵ}. Further 𝔖(j) = 𝔖(j − j_{1}) where j_{1} is a vector with j_{1} in every component, and so the singular series are unaffected by this shift.

We now apply Theorem 1.1 in (1.17), and obtain immediately using (1.13) that

M_{k}(N, h, ψ_{R}) = (1 + o(1))P_{k}(λ, R)N(log R)^{k} + O(h^{k}R^{k})  (1.19)

where

P_{k}(λ, R) = ∑_{r=1}^{k} \frac{1}{r!} (\frac{h}{log R})^{r} ∑_{a_{1},a_{2},... ,a_{r} ; a_{i}≥1,∑ a_{i}=k} ( \begin{matrix}k \\ a_{1}, a_{2}, …, a_{r} \end{matrix} ) C_{k}(a).  (1.20)

Using the values of the constants C(a) in Theorem 1.1 we obtain the following result on moments of ψ_{R}.

Corollary 1.2 For h ∼ λ log N, λ ≪ R^{ϵ}, and R = N^{θ_{k}}, where θ_{k} is fixed and 0 < θ_{k} < \frac{1}{k} for 1 ≤ k ≤ 3, we have

M_{1}(N, h, ψ_{R}) ∼ λN log N,
M_{2}(N, h, ψ_{R}) ∼ (θ_{2}λ + λ^{2})N log^{2} N,
M_{3}(N, h, ψ_{R}) ∼ (\frac{3}{4}θ_{3}^{2}λ + 3θ_{3}λ^{2} + λ^{3})N log^{3} N.

We next consider the mixed moments

M̃_{k}(N, h, ψ_{R}) = ∑_{n=1}^{N}(ψ_{R}(n + h) − ψ_{R}(n))^{k−1}(ψ(n + h) − ψ(n))  (1.21)

for k ≥ 2, while if k = 1 we take

M̃_{1}(N, h, ψ_{R}) = M_{1}(N, h, ψ) ∼ λN log N  (1.22)

for 1 ≤ R ≤ N by the prime number theorem. Now assume k ≥ 2. On multiplying out and grouping as before for the terms involving Λ_{R} we have

M̃_{k}(N, h, ψ_{R}) =∑_{r=2}^{k} ∑_{a_{1},a_{2},... ,a_{r−1} ; a_{i}≥1,∑ a_{i}=k−1} \frac{1}{(r − 1)!} ( \begin{matrix}k − 1 \\ a_{1}, a_{2}, …, a_{r−1} \end{matrix} ) ∑_{1≤j_{1},j_{2},··· ,j_{r−1}≤h distinct}V_{r−1}(N, j, a),

(1.23)

where

V_{r−1}(N, j, a) = ∑_{1≤m≤h} ∑_{n=1}^{N} Λ_{R}(n + j_{1})^{a_{1}}Λ_{R}(n + j_{2})^{a_{2}} ⋯ Λ_{R}(n + j_{r−1})^{a_{r−1}}Λ(n + m)

Since, provided n + j > R and n + j ≠ p^{m} for some m ≥ 2 and p < R, we have

Λ_{R}(n + j)^{a}Λ(n + j) = (log R)^{a}Λ(n + j),

we see

V_{r−1}(N, j, a)

= ∑_{i=1}^{r−1}(log R)^{a_{i}} ∑_{n=1}^{N} ( ∏_{{1≤s≤r−1 \atop s≠i}} Λ_{R}(n + j_{s})^{a_{s}})Λ(n + j_{i})

+ ∑_{{1≤j_{r}≤h \atop j_{r}≠j_{i}} ; 1≤i≤r−1} ∑_{n=1}^{N} Λ_{R}(n + j_{1})^{a_{1}}Λ_{R}(n + j_{2})^{a_{2}} ⋯ Λ_{R}(n + j_{r−1})^{a_{r−1}}Λ(n + j_{r}) + O(RN^{ϵ})

= ∑_{i=1}^{r−1}(log R)^{a_{i}} S̃_{k−a_{i}}(N, j_{i}, a_{i}) + ∑_{{1≤j_{l}≤h \atop j_{l}≠j_{i}} ; 1≤i≤r−1} S̃_{k}(N, j, a) + O(RN^{ϵ})

where

j_{i} = (j_{1}, j_{2}, …, j_{i−1}, j_{i+1}, …, j_{r−1}, j_{i}), a_{i} = (a_{1}, a_{2}, …, a_{i−1}, a_{i+1}, …, a_{r−1}, 1). (1.24)

We conclude for k ≥ 2

M̃_{k}(N, h, ψ_{R}) = ∑_{r=2}^{k} ∑_{a_{1},a_{2},... ,a_{r−1} ; a_{i}≥1,∑ a_{i}=k−1} \frac{1}{(r − 1)!} ( \begin{matrix}k − 1 \\ a_{1}, a_{2}, …, a_{r−1} \end{matrix} ) W_{r}(N, j, a) + O(RN^{ϵ}), (1.25)

where

W_{r}(N, j, a) = ∑_{i=1}^{r−1}(log R)^{a_{i}} ∑_{1≤j_{1},j_{2},··· ,j_{r−1}≤h distinct} S̃_{k−a_{i}}(N, j_{i}, a_{i}) + ∑_{1≤j_{1},j_{2},··· ,j_{r}≤h distinct} S̃_{k}(N, j, a).

(1.26)

We have reduced the calculation of the mixed moments to mixed correlations. Our method for evaluating the mixed correlations will prove as a by-product that the mixed correlations are asymptotically equal to the corresponding pure correlations in a certain range of R. Our results depend on the uniform distribution of primes in arithmetic progressions. We let

ψ(x; q, a) = ∑_{{n≤x \atop n≡a(q)}} Λ(n),  (1.27)

and

E_{a,b} = \{ \begin{matrix}1, & if (a, b) = 1, \\ 0, & if (a, b) > 1. \end{matrix}  (1.28)

On taking

E(x; q, a) = ψ(x; q, a) − E_{a,q} \frac{x}{ϕ(q)},  (1.29)

the estimate we need is, for some fixed 0 < ϑ ≤ 1,

∑_{1≤q≤x^{ϑ−ϵ}} max_{{a \atop (a,q)=1}} |E(x; q, a)| ≪ \frac{x}{log^{A} x},  (1.30)

for any ϵ > 0, any A = A(ϵ) > 0, and x sufficiently large. This is a weakened form of the Bombieri-Vinogradov theorem if ϑ = \frac{1}{2}, and therefore (1.30) holds unconditionally if ϑ ≤ \frac{1}{2}. Elliott and Halberstam conjectured (1.30) is true with ϑ = 1. The range of R where our results on mixed correlations hold depends on ϑ in (1.30). We first prove the following general result.

Theorem 1.3 Given k ≥ 2, let j = (j_{1}, j_{2}, …, j_{r}) and a = (a_{1}, a_{2}, … a_{r}), where the j_{i}’s are distinct integers, a_{i} ≥ 1, a_{r} = 1, and ∑_{i=1}^{r} a_{i} = k . Assume max_{i} |j_{i}| ≪ R^{\frac{1}{k}} and that N^{ϵ} ≪ R ≪ N^{min( \frac{ϑ}{k−1} , \frac{1}{k})−ϵ}. Then we have, with A from (1.30),

S̃_{k}(N, j, a) = S_{k}(N, j, a) + O(R^{k}) + O(\frac{N}{(log N)^{\frac{A}{2} −4^{k−3/2}+2^{k−1}−1}} ).  (1.31)

The proof of Theorem 1.3 involves proving that both S̃_{k}(N, j, a) and S_{k}(N, j, a) are asymptotic to the same main term and therefore they are asymptotic to each other in the range where both asymptotic formulas hold. Using Theorems 1.1 and 1.3 we can now immediately evaluate the mixed moments. There is, however, an inefficiency in the use of Theorem 1.3 which imposes the condition that R ≪ N^{min( \frac{ϑ}{k−1} , \frac{1}{k})−ϵ}. The restriction R ≪ N^{\frac{1}{k} −ϵ} in this condition arises from applying Theorem 1.1, but by directly evaluating the main term that arises in the proof of Theorem 1.3 we can remove this condition and prove the following result.

Theorem 1.4 Given 2 ≤ k ≤ 3, let j = (j_{1}, j_{2}, …, j_{r}) and a = (a_{1}, a_{2}, … a_{r}), where r ≥ 2, a_{r} = 1, and where the j_{i}’s are distinct integers, and a_{i} ≥ 1 with ∑_{i=1}^{r} a_{i} = k. Assume max_{i} |j_{i}| ≪ R^{ϵ}. Then we have, for N^{ϵ} ≪ R ≪ N^{\frac{ϑ}{k−1} −ϵ} where (1.30) holds with ϑ,

S̃_{k}(N, j, a) = (𝔖(j) + o(1))N(log R)^{k−r}.  (1.32)

For larger k the constants C(a) will appear in this theorem as in Theorem 1.1, but for k ≤ 3 all these constants for the mixed correlations are equal to 1.

Next, using (1.25) we are able to evaluate the first three mixed moments.

Corollary 1.5 For h ∼ λ log N, λ ≪ R^{ϵ}, and R = N^{θ_{k}}, where θ_{k} is fixed, 0 < θ_{1} ≤ 1, and 0 < θ_{k} < \frac{ϑ}{k−1} for 2 ≤ k ≤ 3, we have,

M̃_{1}(N, h, ψ_{R}) ∼ λN log N,
M̃_{2}(N, h, ψ_{R}) ∼ (θ_{2}λ + λ^{2})N log^{2} N,
M̃_{3}(N, h, ψ_{R}) ∼ (θ_{3}^{2}λ + 3θ_{3}λ^{2} + λ^{3})N log^{3} N.

The starting point of Bombieri and Davenport’s [1] work on small gaps between primes is essentially equivalent to the inequality

∑_{n=N+1}^{2N} ((ψ(n + h) − ψ(n)) − (ψ_{R}(n + h) − ψ_{R}(n)))^{2} ≥ 0.  (1.33)

Letting

M′_{k}(N, h, ψ) = M_{k}(2N, h, ψ) − M_{k}(N, h, ψ),  (1.34)

with the corresponding definition for M′_{k}(N, h, ψ_{R}) and M̃′_{k}(N, h, ψ_{R}), we see that Corollary 1.2 holds with M_{k}(N, h, ψ_{R}) replaced by M′_{k}(N, h, ψ_{R}) and Corollary 1.5 holds with M̃_{k}(N, h, ψ_{R}) replaced with M̃′_{k}(N, h, ψ_{R}). On expanding (1.33) we have

M′_{2}(N, h, ψ) ≥ 2M̃′_{2}(N, h, ψ_{R}) − M′_{2}(N, h, ψ_{R})

which implies on taking θ_{2} = 1/2 − ϵ in Corollaries 1.2 and 1.5 that

M′_{2}(N, h, ψ) ≥ (\frac{1}{2}λ + λ^{2} − ϵ)N log^{2} N.  (1.35)

Let p_{j} denote the j-th prime. If it is the case that p_{j+1} − p_{j} > h = λ log N for all \frac{N}{2} < p_{j} ≤ 2N, then each of the intervals (n, n + h] for N < n ≤ 2N contains at most one prime. Hence, since the prime powers may be removed with a negligible error, we have that M′_{2}(N, h, ψ) ∼ (log N)M′_{1}(N, h, ψ) ∼ λN log^{2} N so that (1.35) implies

λ ≥ \frac{1}{2}λ + λ^{2} − ϵ

which is false if λ > \frac{1}{2}. We conclude that

lim inf_{n→∞} (\frac{p_{n+1} − p_{n}}{log p_{n}} ) ≤ \frac{1}{2}.  (1.36)

More generally, we define for r any positive integer

Ξ_{r} = lim inf_{n→∞} (\frac{p_{n+r} − p_{n}}{log p_{n}} )  (1.37)

and see that if p_{n+r} − p_{n} > h = λ log N for N < p_{n} ≤ 2N then

M′_{2}(N, h, ψ) ≤ (r + ϵ)(log N)M′_{1}(N, h, ψ) ≤ (r + ϵ)λN log^{2} N

which then implies that

rλ ≥ \frac{1}{2}λ + λ^{2} − ϵ

and hence

Ξ_{r} ≤ r − \frac{1}{2}.  (1.38)

Bombieri and Davenport were also able to improve (1.36) by incorporating an earlier method of Erdös into their argument. This method depends on the sieve upper bound for primes differing by an even number k given by

∑_{n≤N} Λ(n)Λ(n + k) ≤ (B + ϵ)𝔖(k)N  (1.39)

where 𝔖(k) = 𝔖(j) with j = (0, k), and B is a constant. In [1] Bombieri and Davenport proved that (1.39) holds with B = 4, and using this value they improved (1.36) and obtained

Ξ_{1} ≤ \frac{2 + \sqrt{3}}{8} = 0.46650 ….  (1.40)

While (1.35) has never been improved, the refinements based on the Erdös method together with the choice of certain weights in a more general form of (1.35) has led to further improvements. Huxley [20] [21] proved that, letting θ_{r} be the smallest positive solution of

θ_{r} + sin θ_{r} = \frac{π}{Br}, sin θ_{r} < (π + θ_{r}) cos θ_{r} ,  (1.41)

then

Ξ_{r} ≤ \frac{2r − 1}{4Br} \{Br + (Br − 1)\frac{θ_{r}}{sin θ_{r}} \} .  (1.42)

With the value B = 4 this gives

Ξ_{1} ≤ 0.44254 …, Ξ_{2} ≤ 1.41051 …, Ξ_{3} ≤ 2.39912 …, Ξ_{4} ≤ 3.39326 ….

We note that the expression on the right-hand side of (1.42) is equal to

r − \frac{1 + \frac{1}{B}}{2} + O(\frac{1}{r}),

and thus for large r this bound approaches r − \frac{5}{8} with B = 4.

The best result known for B which holds uniformly for all k is B = 3.9171 … due to Chen [4]. However, in the application to obtain (1.42) one only needs (1.39) to hold uniformly for a restricted range of k; the condition 0 < |k| ≤ log^{2} N is more than sufficient. In this case there have been a string of improvements. For ease of comparison with the value B = 4 used above, the value B = 3.5 obtained by Bombieri, Friedlander, and Iwaniec [2] gives the values

Ξ_{1} ≤ 0.43493 …, Ξ_{2} ≤ 1.39833 …, Ξ_{3} ≤ 2.38519 …, Ξ_{4} ≤ 3.37842 ….

All of these results above actually hold for a positive percentage of gaps. Maier [22] introduced a new method to prove that

lim inf_{n→∞} (\frac{p_{n+1} − p_{n}}{log p_{n}} ) ≤ e^{−γ} = 0.56145 ….  (1.43)

This method, which applies to special sets of sparse intervals, may be combined with the earlier methods to include this factor of e^{−γ} times the earlier results. The argument was carried out with B = 4 in [22], which then gives in particular

Ξ_{1} ≤ 0.24846 …, Ξ_{2} ≤ 0.79194 …, Ξ_{3} ≤ 1.34700 …, Ξ_{4} ≤ 1.90518 ….

Our approach for examining gaps between primes is to consider the mixed third moment

M̃′_{3}(N, h, ψ_{R}, C) = ∑_{n=N+1}^{2N} (ψ(n + h) − ψ(n))(ψ_{R}(n + h) − ψ_{R}(n) − C log N)^{2}, (1.44)

Here C may be chosen as a function of h and R to optimize the argument. The idea behind the use of M̃′_{3}(N, h, ψ_{R}, C) is that it will approximate and thus provide some of the same information as the third moment M′_{3}(N, h, ψ). If p_{n+r} − p_{n} > h = λ log N for all N < p_{n} ≤ 2N then, removing prime powers as before, we have

M̃′_{3}(N, h, ψ_{R}, C) ≤ (r + ϵ) log N ∑_{n=N+1}^{2N} (ψ_{R}(n + h) − ψ_{R}(n) − C log N)^{2}.  (1.45)

Corollaries 1.2 and 1.5 allow us to evaluate both sides of (1.45), and on choosing C appropriately we are able to prove the following result.

Theorem 1.6 For r ≥ 1, we have

Ξ_{r} ≤ r − \frac{1}{2}\sqrt{r}.  (1.46)

Further, assuming that for h ≪ log N and R ≤ N^{\frac{1}{4}}

M_{4}(N, h, ψ_{R}) ≪ N log^{4} N,  (1.47)

then we have that, for h = λ log N and λ > r − \frac{1}{2} \sqrt{r},

∑_{\begin{matrix}N+1≤p_{n}≤2N \\ p_{n+r}−p_{n}<h \end{matrix}} 1 ≫_{λ} \frac{N}{log N} .  (1.48)

Thus we have

Ξ_{1} ≤ \frac{1}{2}, Ξ_{2} ≤ 1.29289 …, Ξ_{3} ≤ 2.13397 …, Ξ_{4} ≤ 3.

We see that our result improves on the results of Huxley when r ≥ 2, although Maier’s results are still better. Our theorem corresponds to (1.38) in that it does not use the Erdös method. It is possible to incorporate the Erdös method into our method too, but this requires we first obtain an asymptotic formula for M_{4}(N, h, ψ_{R}). One should also be able to incorporate Maier’s method as well, which would then give better results than are currently known for r ≥ 2.

The result in (1.48) shows that the small gaps produced in the theorem form a positive proportion of all the gaps assuming that (1.47) holds. We will prove (1.47) in a later paper in this series and thus show that (1.48) holds unconditionally.

We will actually prove

Ξ_{r} ≤ r − \sqrt{\frac{ϑr}{2}},  (1.49)

where ϑ is the number in (1.30). Therefore, assuming the Elliott-Halberstam Conjecture in the form that one may take ϑ = 1 in (1.30), we have

Ξ_{r} ≤ r − \sqrt{\frac{r}{2}}

which in particular gives

Ξ_{1} ≤ 0.29289 …, Ξ_{2} ≤ 1, Ξ_{3} ≤ 1.77525 …, Ξ_{4} ≤ 2.58578 ….

These results are in contrast to the method of Bombieri and Davenport where the Elliott-Halberstam conjecture does not improve their results directly. (The Elliott-Halberstam conjecture does allow one to take B = 2 in (1.39), and therefore leads to small improvements in Huxley’s results, which for r ≥ 2 are weaker than the result in Theorem 1.6.) We cannot extend these last results obtained assuming an Elliott-Halberstam conjecture to a positive proportion of gaps because we can not prove (1.47) for θ > \frac{1}{4}. Our proof gives that the number of gaps we produce in this case is ≫ N log^{−B} N for some positive constant B > 1.

Our method can also be used to examine larger than average gaps between primes. In this case much more is known than for small gaps; the latest result being that [24]

max_{p_{n}≤N} \frac{p_{n+1} − p_{n}}{log p_{n}} ≥ (2e^{γ} − o(1))\frac{log log N log log log log N}{(log log log N)^{2}} .  (1.50)

If one were to ask however for a positive proportion of gaps larger than the average, then it is a remarkable fact that nothing non-trivial is known. ^{2} What can be proved is that a positive proportion of the interval (N, 2N] is contained between consecutive primes whose difference is a little larger than average. To formalize this, we let Θ_{r} be the supremum over all λ for which

∑_{\begin{matrix}N<p_{n}≤2N \\ p_{n+r}−p_{n}≥λ log N \end{matrix}}(p_{n+r} − p_{n}) ≫_{λ} N  (1.51)

for all sufficiently large N. Then using the Erdös method one finds that [3]

Θ_{1} ≥ 1 + \frac{1}{2B}  (1.52)

where B is the number in (1.39).

To apply (1.44) to this problem, we assume that p_{j+r} − p_{j} < h = λ log N for all N < p_{j} ≤ 2N in which case the interval (n, n + h] always contains at least r primes, and therefore (1.45) holds with the inequality reversed. On optimizing C we obtain the following result.

Theorem 1.7 Assume that (1.47) holds. For r ≥ 1 we have that

Θ_{r} ≥ r + \frac{1}{2}\sqrt{r}.  (1.53)

As mentioned above, we will prove (1.47) in a later paper in this series, which will show that Theorem 1.7 holds unconditionally.

The proof of Theorems 1.6 and 1.7 only require the asymptotic formula for the third mixed moment in Corollary 1.5 and the second moment for ψ_{R} in Corollary 1.2. Thus the results in sections 6–10 which are concerned with triple correlations of ψ_{R} may be skipped by the reader who is only interested in our applications to primes.

Notation. In this paper N will always be a large integer, p denotes a prime number, and sums will start at 1 if a lower limit is unspecified. When a sum is denoted with a dash as ∑′ this always indicates we will sum over all variables expressed by inequalities in the conditions of summation and these variables will all be pairwise relatively prime with each other. We will always take the value of a void sum to be zero and the value of a void product to be 1. The letter ϵ will denote a small positive number which may change in each equation. We will also use the Iverson notation [12] that putting brackets around a true-false statement will replace the statement by 1 if it is true, and 0 if it is false:

2The first-named author of this paper learned of this from Carl Pomerance after a talk in which the author had claimed to have such a result.

[P (x)] = \{ \begin{matrix}1, & if P (x) is true, \\ 0, & if P (x) is false. \end{matrix}  (1.54)

As usual, (a, b) denotes the greatest common divisor of a and b and [a_{1}, a_{2}, ⋯, a_{n}] denotes the least common multiple of a_{1}, a_{2}, …, a_{n}.

Acknowledgements

A preliminary version of this paper was presented at the First Workshop on L-functions and Random Matrices at the American Institute of Mathematics in May, 2001. Thanks to a suggestion of Peter Sarnak during the talk, and encouragement of John Friedlander after the talk, the authors found an alternative method for proving Theorem 1.1 which generalizes to the case of k-correlations. This new method has its own complications which make it very easy for mistakes to creep into the calculations. Following the conference, the first-named author visited AIM where these problems were solved jointly with Brian Conrey and David Farmer. Farmer has written a program in Mathematica to compute the constants C_{k}(a) and has found that C_{4}(4) = \frac{3}{4}, C_{5}(5) = \frac{11065}{2^{14}} = .67535 …, and C_{6}(6) = \frac{11460578803}{2^{34}} = .66709 . . .. The authors would like to thank these individuals and the American Institute of Mathematics.

2. Lemmas

For j a non-negative integer, we define the arithmetic function ϕ_{j}(n) on the primes by

ϕ_{j}(p) = p − j,  (2.1)

ϕ_{j}(1) = 1, and extend the definition to squarefree integers by multiplicativity. Thus for n squarefree ϕ_{0}(n) = n, and ϕ_{1}(n) = ϕ(n). We will not need to extend the definition beyond the squarefree integers here. Letting

p(j) = \{ \begin{matrix}j, & if j is a prime, \\ 1, & otherwise, \end{matrix}  (2.2)

we next define

H_{j}(n) = ∏_{{p|n \atop p≠j−1, p≠j}} (1 + \frac{1}{p − j} ) = ∏_{{p|n \atop p≠j−1, p≠j}} (1 + \frac{1}{ϕ_{j}(p)}) = ∑_{{d|n \atop (d,p(j−1)p(j))=1}} \frac{μ^{2}(d)}{ϕ_{j}(d)}. (2.3)

We see that for n squarefree H_{0}(n) = σ(n)/n, H_{1}(n) = n/ϕ(n), and in general for j ≥ 1

H_{j}(n) = ∏_{{p|n \atop p≠j−1, p≠j}} (\frac{p − j + 1}{p − j}) = \frac{ϕ_{j−1}(\frac{n}{(n,p(j−1)p(j))})}{ϕ_{j}(\frac{n}{(n,p(j−1)p(j))})},  (μ^{2}(n) ≠ 0).  (2.4)

Next, we define the singular series for j ≥ 1 and n ≠ 0 by

𝔖_{j}(n) = \{ \begin{matrix}C_{j}G_{j}(n)H_{j}(n), & if p(j)|n, \\ 0, & otherwise. \end{matrix}  (2.5)

where

G_{j}(n) = ∏_{{p|n \atop p=j−1 or p=j}} (\frac{p}{p − 1}) ,  (2.6)

and

C_{j} = ∏_{{p \atop p≠j−1, p≠j}} (1 − \frac{j − 1}{(p − 1)(p − j + 1)}) .  (2.7)

The case of j = 3 is special because it is the only case where p(j − 1) and p(j) are both greater than one. We see that for j = 1 and n ≠ 0

𝔖_{1}(n) = ∏_{p|n} (\frac{p}{p − 1}) = \frac{n}{ϕ(n)}  (2.8)

and for j = 2 we have the familiar singular series for the Goldbach and prime twins conjectures

𝔖_{2}(n) = \{ \begin{matrix}2C_{2} ∏_{{p|n \atop p>2}} (\frac{p − 1}{p − 2}) , & if n is even, n ≠ 0; \\ 0, & if n is odd; \end{matrix}  (2.9)

where

C_{2} = ∏_{p>2} (1 − \frac{1}{(p − 1)^{2}} ) .  (2.10)

Lemma 2.1 For R ≥ 1, j ≥ 0, p(j)|k, and 0 ≤ log |k| ≪ log R, we have

∑_{{d≤R \atop (d,k)=1}} \frac{μ(d)}{ϕ_{j}(d)} log \frac{R}{d} = 𝔖_{j+1}(k) + r_{j}(R, k),  (2.11)

where

r_{j}(R, k) ≪_{j} e^{−c_{1}\sqrt{log R}},  (2.12)

and c_{1} is an absolute positive constant. Also,

∑_{{d≤R \atop (d,k)=1}} \frac{μ(d)}{ϕ_{j}(d)} ≪_{j} e^{−c_{1}\sqrt{log R}}.  (2.13)

Special cases of Lemma 2.1 have been proved before. When j = 0 this was used by Selberg [25], and also Graham [13], but we have made the error term stronger with regard to k by an argument suggested in [5]. It is easy to make the j dependence explicit in the error term, but in this paper we will assume j is fixed (actually we only use j ≤ 2.) We will sometimes use Lemma 2.1 in the weaker form

∑_{{d≤R \atop (d,k)=1}} \frac{μ(d)}{ϕ_{j}(d)} log \frac{R}{d} = 𝔖_{j+1}(k) + O_{j}(\frac{1}{(log 2R)^{A}})

for A any positive number, and assuming the same conditions as in Lemma 2.1. Further, in handling error terms, we will need to remove the restriction 0 ≤ log |k| ≪ log R in Lemma 2.1, in which case we have the error estimate

r_{j}(R, k) ≪_{j} m(k)e^{−c_{1}\sqrt{log R}},  (2.14)

which holds uniformly for k ≥ 1 and R ≥ 1, where m(k) is defined below in equation (2.18). This estimate also holds in (2.13).

The next lemma is a generalization of a result of Hildebrand [15].

Lemma 2.2 For R ≥ 1, j ≥ 1 and p(j)|k, we have

∑_{{d≤R \atop (d,k)=1}} \frac{μ^{2}(d)}{ϕ_{j}(d)} = \{ \begin{matrix}\frac{1}{𝔖_{j}(k)} (log R + D_{j} + h_{j}(k)) + O(\frac{m(k)}{\sqrt{R}}) & if p(j − 1)|k, \\ O(\frac{m(k)}{\sqrt{R}}), & if p(j − 1) |̸ k, \end{matrix}  (2.15)

where

D_{j} = γ + ∑_{p≠j−1} \frac{(2 − j) log p}{(p − j + 1)(p − 1)},  (2.16)

h_{j}(k) = ∑_{p|k} \frac{log p}{p − 1} − ∑_{{p|k \atop p≠j−1}} \frac{(2 − j) log p}{(p − j + 1)(p − 1)}

= ∑_{{p|k \atop p≠j−1}} \frac{log p}{(p − j + 1)} + [(p(j − 1), k) > 1]\frac{log(j − 1)}{j − 2},

(2.17)

and

m(k) = ∑_{d|k} \frac{μ^{2}(d)}{\sqrt{d}} = ∏_{p|k} (1 + \frac{1}{\sqrt{p}}) .  (2.18)

The case j = 1 of this lemma is Hilfssatz 2 of [15]. The proof of this generalization only requires minor modifications in Hildebrand’s proof which we sketch. In applying this lemma we will sometimes use the simple estimates (see [11])

h_{j}(k) ≪_{j} log log 3k,  m(k) ≪ exp (\frac{c\sqrt{log k}}{log log 3k} ) .  (2.19)

We will frequently use the estimate, for p(j)|k and log |k| ≪ log R,

∑_{\begin{matrix}d≤R \\ (d,k)=1 \end{matrix}} \frac{μ^{2}(d)}{ϕ_{j}(d)} ≪ log 2R  (2.20)

which follows immediately from Lemma 2.2 or may be seen directly. We also need the following result that is obtained by partial summation in Lemma 2.2. For j ≥ 1 and p(j)|k, we have

∑_{{d≤R \atop (d,k)=1}} \frac{μ^{2}(d)}{ϕ_{j}(d)} log \frac{R}{d}

= \{ \begin{matrix}\frac{1}{𝔖_{j}(k)} (\frac{1}{2} log^{2} R + (D_{j} + h_{j}(k)) log R + E_{j}(k)) + O(\frac{m(k)}{\sqrt{R}}) & if p(j − 1)|k, \\ E_{j}(k) + O(\frac{m(k)}{\sqrt{R}}), & if p(j − 1) |̸ k, \end{matrix}

(2.21)

where E_{j}(k) is given by

E_{j}(k) = ∫_{1}^{∞} ( ∑_{{d≤u \atop (d,k)=1}} \frac{μ^{2}(d)}{ϕ_{j}(d)} − \frac{1}{𝔖_{j}(k)} (log u + D_{j} + h_{j}(k)) ) \frac{du}{u}.  (2.22)

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 3 (2003), #A05 18

Lemma 2.3 For R ≥ 1, j ≥ 1, p(j)|k, and 0 ≤ log |k| ≪ log R, we have

∑_{{d≤R \atop (d,k)=1}} \frac{μ(d)}{ϕ_{j}(d)}𝔖_{j+1}(dk) log \frac{R}{d}

= μ(p(j + 1))μ((k, p(j + 1)))𝔖_{j+1}(kp(j + 1))(𝔖_{j+2}(kp(j + 1))  (2.23)

+r_{j+1}(\frac{R(k, p(j + 1))}{p(j + 1)}, kp(j + 1))),

where r_{j}(R, k) is the error term in Lemma 2.1. Lemma 2.4 For R ≥ 1, j ≥ 1 and p(j)|k, we have

\begin{aligned}∑_{{d≤R \atop (d,k)=1}} \frac{μ^{2}(d)}{ϕ_{j}(d)}𝔖_{j+1}(dk) & = log (\frac{R(k, p(j + 1))}{p(j + 1)}) + D_{j+1} + h_{j+1}(kp(j + 1)) \\ & + O (\frac{𝔖_{j+1}(kp(j + 1))m(kp(j + 1))}{\sqrt{\frac{R(k,p(j+1))}{p(j+1)}}} ) \end{aligned}  (2.24)

and

∑_{{d|r \atop (d,k)=1}} \frac{μ^{2}(d)}{ϕ_{j}(d)}𝔖_{j+1}(dk) = 𝔖_{j+1}(rk).  (2.25)

Our final lemma relates the singular series given in (1.9) for r equal to two and three to the singular series in (2.5). Lemma 2.5 For k = (0, k), with k ≠ 0, we have

𝔖(k) = 𝔖_{2}(k),  (2.26)

and for k = (0, k_{1}, k_{2}), k_{1} ≠ k_{2} ≠ 0, κ = (k_{1}, k_{2}), and Δ = k_{1}k_{2}(k_{2} − k_{1}), we have

𝔖(k) = 𝔖_{2}(κ)𝔖_{3}(Δ).  (2.27)

3. Proof of the Lemmas

Proof of Lemma 2.1. We assume p(j)|k. Let s = σ + it, σ > 0, and define

F (s) = ∑_{{n=1 \atop (n,k)=1}}^{∞} \frac{μ(n)}{ϕ_{j}(n)n^{s}} = ∏_{p |̸k} (1 − \frac{1}{(p − j)p^{s}} )

= \frac{1}{ζ(s + 1)} ∏_{p|k} (1 − \frac{1}{p^{s+1}} )^{−1} ∏_{p |̸k} (1 − \frac{1}{(p − j)p^{s}} ) (1 − \frac{1}{p^{s+1}} )^{−1}

= \frac{1}{ζ(s + 1)} ∏_{p|k} (1 − \frac{1}{p^{s+1}} )^{−1} ∏_{p |̸k} (1 − \frac{j}{(p − j)(p^{s+1} − 1)})

= \frac{1}{ζ(s + 1)}g_{k}(s)h_{k}(s).  (3.1)

We see the product for h_{k}(s) converges absolutely for Re(s) > −1, and therefore F (s) is an analytic function in this half-plane except possibly for poles at the zeros of ζ(s + 1).

We now apply the formula, for m ≥ 2 and b > 0,

\frac{(m − 1)!}{2πi} ∫_{b−i∞}^{b+i∞} \frac{x^{s}}{s^{m}} ds = \{ \begin{matrix}0, & if 0 < x ≤ 1, \\ (log x)^{m−1}, & if x ≥ 1, \end{matrix}

which, in the case m = 2, gives

∑_{{d≤R \atop (d,k)=1}} \frac{μ(d)}{ϕ_{j}(d)} log \frac{R}{d} = \frac{1}{2πi} ∫_{b−i∞}^{b+i∞} F (s)\frac{R^{s}}{s^{2}} ds.  (3.2)

By Theorem 3.8 and (3.11.8) of [26] there exists a small positive constant c such that ζ(σ + it) ≠ 0 in the region σ ≥ 1 − \frac{c}{log(|t|+2)} and all t, and further

\frac{1}{ζ(σ + it)} ≪ log(|t| + 2)  (3.3)

in this region. (There are stronger results but this suffices for our needs.) We now move the contour to the left to the path L given by s = −\frac{c}{log(|t|+2)} +it. When p(j +1) |̸ k, h_{k}(s) has a simple zero at s = 0 and hence F (s)/s^{2} is analytic at s = 0 and no contribution occurs, but when p(j + 1)|k (including p(j + 1) = 1), F (s)/s^{2} has a simple pole at s = 0

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 3 (2003), #A05 20

which gives a contribution from the residue of

g_{k}(0)h_{k}(0) = ∏_{p|k} (1 − \frac{1}{p})^{−1} ∏_{p |̸k} (1 − \frac{j}{(p − 1)(p − j)})
= ∏_{{p|k \atop p=j or p=j+1}} (\frac{p}{p − 1}) ∏_{{p|k \atop p≠j, p≠j+1}} (1 − \frac{1}{p})^{−1} (1 − \frac{j}{(p − 1)(p − j)})^{−1}
∏_{{p \atop p≠j, p≠j+1}} (1 − \frac{j}{(p − 1)(p − j)})
= G_{j+1}(k) ∏_{{p \atop p≠j,p≠j+1}} (1 − \frac{j}{(p − 1)(p − j)}) ∏_{{p|k \atop p≠j, p≠j+1}} (\frac{p − j}{p − j − 1})
= C_{j+1}G_{j+1}(k)H_{j+1}(k).

Hence we have

∑_{{d≤R \atop (d,k)=1}} \frac{μ(d)}{ϕ_{j}(d)} log \frac{R}{d} = 𝔖_{j+1}(k) + \frac{1}{2πi} ∫_{L} F (s)\frac{R^{s}}{s^{2}} ds = 𝔖_{j+1}(k) + r_{j}(R, k).  (3.4)

It remains to estimate the integral in (3.4). On L we have −\frac{1}{4} ≤ σ < 0, and therefore

|h_{k}(s)| ≪ ∏_{p} (1 + O_{j}(\frac{1}{p^{2+σ}})) ≪_{j} 1.

For g_{k}(s), we see that g_{1}(s) = 1 since the product defining g_{1}(s) is void, and for k > 1

log |g_{k}(s)| ≤ − ∑_{p|k} log(1 − \frac{1}{p^{σ+1}} )
≪ ∑_{p|k} \frac{1}{p^{σ+1}}
≪ ∑_{p<2 log 2k} \frac{1}{p^{σ+1}} ≪ (log k)^{−σ}

and hence

|g_{k}(s)| ≪ e^{\sqrt[4]{log k}}, for k ≥ 1.  (3.5)

Thus the integral in (3.4) is

≪_{j} e^{\sqrt[4]{log k}} ∫_{−∞}^{∞} R^{− \frac{c}{log(|t|+2)}} log(|t| + 2)\frac{1}{(\frac{c}{log(|t|+2))})^{2} + t^{2}} dt

This last integral is, for any w ≥ 2,

≪ ∫_{0}^{w} R^{− \frac{c}{log(|t|+2)}} dt + ∫_{w}^{∞} \frac{log t}{t^{2}} dt ≪ we^{\frac{−c log R}{log w}} + \frac{log w}{w}

and hence, on choosing log w = \frac{1}{2} \sqrt{c log R} we have, since log |k| ≪ log R, that the error term is

≪_{j} e^{\sqrt[4]{log k}} (e^{−\sqrt{c log R}} + \sqrt{c log R}e^{− \frac{1}{2} \sqrt{c log R}}) ≪_{j} e^{−c_{1}\sqrt{log R}},

which proves the first part of Lemma 1.

The bound in equation (2.14) follows from the previous argument when we replace the estimate for g_{k}(s) used above by the bound, for −\frac{1}{4} < σ < 0,

|g_{k}(s)| ≪ ∏_{p|k} (1 + \frac{1}{p^{1+σ}} ) ≪ m(k),

which follows from

log |g_{k}(s)| ≤ − ∑_{p|k} log(1 − \frac{1}{p^{σ+1}} )

= ∑_{p|k} (log(1 + \frac{1}{p^{σ+1}} ) + O(\frac{1}{p^{2(σ+1)}} ))

= ∑_{p|k} log(1 + \frac{1}{p^{σ+1}} ) + O(∑_{p} \frac{1}{p^{\frac{3}{2}}} )

= ∑_{p|k} log(1 + \frac{1}{p^{σ+1}} ) + O(1).

To prove (2.13), we apply Perron’s formula (see [26], Chapter 3) in the usual way to obtain, with b = 1/ log R,

∑_{{d≤R \atop (d,k)=1}} \frac{μ(d)}{ϕ_{j}(d)} = \frac{1}{2πi} ∫_{b−iT}^{b+iT} F (s)\frac{R^{s}}{s} ds + O_{j}(\frac{log^{2} R}{T}).

Moving the contour to the left to L for −T ≤ t ≤ T we have no residue, and we may estimate the integral along L and the upper and lower horizontal paths by

≪_{j} e^{\sqrt[4]{log k}}( log^{2} T e^{−c \frac{log R}{log T}} + \frac{log T}{T} ).

Now log |k| ≪ log R, and taking T = e^{\sqrt{log R}} shows the above error is ≪ e^{−c_{1}\sqrt{log R}} for a sufficiently small constant c_{1}. This completes the proof of Lemma 2.1.

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 3 (2003), #A05 22

Proof of Lemma 2.2. We follow Hildebrand’s proof of the case j = 1, indicating only the main steps. We assume p(j)|k, and j ≥ 1. Letting

f_{k}(n) = \{ \begin{matrix}\frac{μ^{2}(n)n}{ϕ_{j}(n)}, & if (n, k) = 1, \\ 0, & otherwise, \end{matrix}  (3.6)

and defining g_{k}(n) by

f_{k}(n) = ∑_{d|n} g_{k}(d)

so that

g_{k}(p^{m}) = f_{k}(p^{m}) − f_{k}(p^{m−1}) = \{ \begin{matrix}\frac{j}{p−j} , & m = 1, p |̸k, \\ −1, & m = 1, p|k, \\ \frac{−p}{p−j} & m = 2, p |̸k, \\ 0, & m = 2 and p|k, or m > 2, \end{matrix}  (3.7)

then we have

∑_{{d≤R \atop (d,k)=1}} \frac{μ^{2}(d)}{ϕ_{j}(d)} = ∑_{n≤R} \frac{f_{k}(n)}{n}
= ∑_{n≤R} \frac{1}{n} ∑_{d|n} g_{k}(d)
= ∑_{d≤R} \frac{g_{k}(d)}{d} ∑_{m≤R/d} \frac{1}{m}
= ∑_{d≤R} \frac{g_{k}(d)}{d} (log \frac{R}{d} + γ + O(\frac{d}{R}))
= ∑_{d≤R} \frac{g_{k}(d)}{d} log \frac{R}{d} + γ ∑_{d≤R} \frac{g_{k}(d)}{d} + O(\frac{1}{R} ∑_{d≤R} |g_{k}(d)|)
= S_{1} + γS_{2} + O(\frac{1}{R}S_{3}).  (3.8)

Using (3.7) and the multiplicativity of g_{k}(n) we easily verify that

M_{j}(k) = ∑_{d=1}^{∞} \frac{g_{k}(d)}{d} = \{ \begin{matrix}\frac{1}{𝔖_{j}(k)}, & if p(j − 1)|k, \\ 0, & if p(j − 1) |̸k. \end{matrix}

As in [15] we find

S_{3} ≪_{j} \sqrt{R}m(k)

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 3 (2003), #A05 23

which by partial summation implies

∑_{d>R} \frac{g_{k}(d)}{d} ≪ \frac{m(k)}{\sqrt{R}}.

These results now imply

S_{2} = M_{j}(k) + O(\frac{m(k)}{\sqrt{R}})

and

S_{1} = M_{j}(k) log R − ∑_{d=1}^{∞} \frac{g_{k}(d) log d}{d} + O(\frac{m(k)}{\sqrt{R}}).

Finally, letting

G_{k}(s) = ∑_{n=1}^{∞} \frac{g_{k}(n)}{n^{s+1}},

we have

− ∑_{d=1}^{∞} \frac{g_{k}(d) log d}{d} = G_{k}′(0)

which on using (2.16) and the Euler product for G_{k}(s) gives G_{k}′(0) = M_{j}(k)(D_{j} +h_{j}(k)− γ) where h_{j}(k) is given by (2.17).

Proof of Lemma 2.3. We have, assuming p(j)|k,

∑_{{d≤R \atop (d,k)=1}} \frac{μ(d)}{ϕ_{j}(d)}𝔖_{j+1}(dk) log \frac{R}{d}

= C_{j+1}G_{j+1}(k)H_{j+1}(k) ∑_{{d≤R \atop (d,k)=1} ; p(j+1)|dk} \frac{μ(d)}{ϕ_{j}(d)}G_{j+1}(d)H_{j+1}(d) log \frac{R}{d}
= C_{j+1}G_{j+1}(k)H_{j+1}(k) ∑_{d≤R ; {(d,k)=1 \atop \frac{p(j+1)}{(k,p(j+1))} |d}} \frac{μ(d)}{ϕ_{j}(d)}G_{j+1}(d)H_{j+1}(d) log \frac{R}{d}
= μ(p(j + 1))μ((k, p(j + 1)))C_{j+1}G_{j+1}(kp(j + 1))H_{j+1}(k)
∑_{{m≤ \frac{R(k,p(j+1))}{p(j+1)} \atop (m,kp(j+1))=1}} \frac{μ(m)}{ϕ_{j+1}(m)} log (\frac{R(k, p(j + 1))}{mp(j + 1)})
= μ(p(j + 1))μ((k, p(j + 1)))𝔖_{j+1}(kp(j + 1))

(𝔖_{j+2}(kp(j + 1)) + r_{j+1}(\frac{R(k, p(j + 1))}{p(j + 1)}, kp(j + 1))),

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 3 (2003), #A05 24

by Lemma 2.1.

Proof of Lemma 2.4. The same argument used above to prove Lemma 2.3 shows that the sum in (2.24) is equal to

𝔖_{j+1}(kp(j + 1)) ∑_{{m≤ \frac{R(k,p(j+1))}{p(j+1)} \atop (m,kp(j+1))=1}} \frac{μ^{2}(m)}{ϕ_{j+1}(m)}.

Since p(j)|k, equation (2.24) now follows from Lemma 2.2.

To prove (2.25), we proceed as before in the proof of Lemma 2.3 to obtain

∑_{{d|r \atop (d,k)=1}} \frac{μ^{2}(d)}{ϕ_{j}(d)}𝔖_{j+1}(dk) = C_{j+1}G_{j+1}(k)H_{j+1}(k) ∑_{{d|r \atop (d,k)=1} ; p(j+1)|dk} \frac{μ^{2}(d)}{ϕ_{j}(d)}G_{j+1}(d)H_{j+1}(d). (3.9)

Suppose first that p(j + 1)|k. Then since p(j)|k also we have that G_{j+1}(d) = 1 in the sum on the right, and hence our expression becomes

= C_{j+1}G_{j+1}(k)H_{j+1}(k) ∑_{{d|r \atop (d,k)=1}} \frac{μ^{2}(d)}{ϕ_{j}(d)}H_{j+1}(d)
= C_{j+1}G_{j+1}(k)H_{j+1}(k) ∑_{{d|r \atop (d,k)=1}} \frac{μ^{2}(d)}{ϕ_{j+1}(d)}
= C_{j+1}G_{j+1}(k)H_{j+1}(k) ∏_{{p|r \atop p |̸k}} (1 + \frac{1}{p − j − 1})
= C_{j+1}G_{j+1}(k)H_{j+1}(rk) = 𝔖_{j+1}(rk)

since here G_{j+1}(k) = G_{j+1}(p(j)p(j + 1)) = G_{j+1}(rk).

Now assume the alternative case that p(j + 1) |̸ k. Then the right-hand side of (3.9) is

= C_{j+1}G_{j+1}(k)H_{j+1}(k) ∑_{{p(j+1)e|r \atop (e,kp(j+1))=1}} \frac{μ^{2}(e)}{ϕ_{j}(e)}G_{j+1}(ep(j + 1))H_{j+1}(e).

If p(j + 1) |̸ r this sum has no terms and is zero which proves (2.25) in this case. If

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 3 (2003), #A05 25

p(j + 1)|r our expression becomes

= C_{j+1}G_{j+1}(p(j)p(j + 1))H_{j+1}(k) ∑_{{e|r \atop (e,kp(j+1))=1}} \frac{μ^{2}(e)}{ϕ_{j+1}(e)}
= C_{j+1}G_{j+1}(p(j)p(j + 1))H_{j+1}(k) ∏_{{p|r \atop p |̸kp(j+1)}} (1 + \frac{1}{p − j − 1})
= 𝔖_{j+1}(rk),

which completes the proof of Lemma 2.4.

Proof of Lemma 2.5. For the case k = (0, k) we have by (1.9) that

𝔖(k) = 4 (1 − \frac{ν_{2}(k)}{2}) ∏_{p>2} (1 − \frac{1}{p})^{−2} (1 − \frac{ν_{p}(k)}{p}) .

Now ν_{p}(k) = 1 if p|k and ν_{p}(k) = 2 if p |̸ k, and hence

𝔖(k) = 2[2|k] ∏_{\begin{matrix}p|k \\ p>2 \end{matrix}} (1 − \frac{1}{p})^{−1} ∏_{\begin{matrix}p |̸k \\ p>2 \end{matrix}} (1 − \frac{1}{p})^{−2} (1 − \frac{2}{p})
= 2[2|k] ∏_{\begin{matrix}p|k \\ p>2 \end{matrix}} (1 − \frac{1}{p}) (1 − \frac{2}{p})^{−1} ∏_{p>2} (1 − \frac{1}{p})^{−2} (1 − \frac{2}{p})
= 2[2|k] ∏_{\begin{matrix}p|k \\ p>2 \end{matrix}} (\frac{p − 1}{p − 2}) ∏_{p>2} (1 − \frac{1}{(p − 1)^{2}} )
= 𝔖_{2}(k).

Next, in general,

𝔖(k) = ∏_{p} (1 − \frac{1}{p})^{−r} (1 − \frac{ν_{p}(k)}{p})
= (1 − \frac{1}{2})^{−r}(1 − \frac{1}{3})^{−r}(1 − \frac{ν_{2}(k)}{2})(1 − \frac{ν_{3}(k)}{3}) ∏_{p>3} (\frac{p}{p − 1})^{r−1}(\frac{p − ν_{p}(k)}{p − 1}) .

With r = 3, k = (0, k_{1}, k_{2}), κ = (k_{1}, k_{2}), and Δ = k_{1}k_{2}(k_{2} − k_{1}) we have

ν_{2}(k) = \{ \begin{matrix}1, & if 2|κ , \\ 2, & if 2 |̸κ, \end{matrix}

and for p ≥ 3

ν_{p}(k) = \{ \begin{matrix}1, & if p|κ, \\ 2, & if p|Δ, p |̸κ, \\ 3, & if p |̸Δ. \end{matrix}

We now see that 𝔖(k) = 0 if 2 |̸ κ or 3 |̸ Δ, which by (2.5) proves the lemma in these cases. Thus we now assume that 2|κ and 3|Δ, and have

𝔖(k) = \frac{9}{ν_{3}(k)} ∏_{p>3} (\frac{p}{p − 1})^{2} (\frac{p − ν_{p}(k)}{p − 1})

= \frac{9}{ν_{3}(k)} ∏_{p>3} (\frac{p}{p − 1})^{2} (\frac{p − 3}{p − 1}) ∏_{{p|κ \atop p>3}} (\frac{p − 1}{p − 3}) ∏_{{p|Δ \atop p |̸κ} ; p>3} (\frac{p − 2}{p − 3})

= \frac{9}{ν_{3}(k)} ∏_{p>3} (1 − \frac{1}{(p − 1)^{2}} ) (1 − \frac{2}{(p − 1)(p − 2)}) ∏_{{p|κ \atop p>3}} (\frac{p − 1}{p − 2}) ∏_{{p|Δ \atop p>3}} (\frac{p − 2}{p − 3})

= 6C_{2}C_{3}H_{2}(κ)H_{3}(Δ)
= 𝔖_{2}(κ)𝔖_{3}(Δ),

which proves Lemma 2.5.

4. Proof of Theorem 1.3

We now prove that the mixed correlations can be reduced to the pure correlations through an application of the Bombieri-Vinogradov theorem. For k ≥ 2 we consider the general sum, for R ≤ P ≤ N,

S_{P} (N, j) = ∑_{n=1}^{N} Λ_{R}(n + j_{1})Λ_{R}(n + j_{2}) ⋯ Λ_{R}(n + j_{k−1})Λ_{P} (n)  (4.1)

where the j_{i}’s are not necessarily distinct, but satisfy

j_{i} ≠ 0, 1 ≤ i ≤ k − 1.  (4.2)

Note that for 1 < n ≤ N, Λ_{N}(n) = Λ(n). We prove Theorem 1.3 by proving the following theorem which shows that both S_{R}(N, j) and S_{N}(N, j) in certain ranges are asymptotic to the same main term. Let

W_{R}(j) = ∑_{\begin{matrix}d_{1},d_{2},... ,d_{k−1}≤R \\ (d_{i},j_{i})=1, 1≤i≤k−1 \\ (d_{r},d_{s})|j_{s}−j_{r}, 1≤r<s≤k−1 \end{matrix}} \frac{1}{ϕ(D_{k−1})} ∏_{i=1}^{k−1} μ(d_{i}) log \frac{R}{d_{i}},  (4.3)

where

D_{k−1} = [d_{1}, d_{2}, …, d_{k−1}].  (4.4)

Theorem 4.1 We have, for k ≥ 2, N^{ϵ} ≤ R ≤ N^{\frac{1}{k}}, and max_{i} |j_{i}| ≪ R^{\frac{1}{k}},

S_{R}(N, j) = NW_{R}(j) + O(R^{k}) + O_{k}(N(log^{4^{k−1}+k−2} N)e^{−c_{1}\sqrt{log _{\frac{R}{max |j_{i}|^{k−1}}}}} ),  (4.5)

and, for N^{ϵ} ≤ R ≤ N^{\frac{ϑ}{k−1} −ϵ},

S_{N}(N, j) = NW_{R}(j) + O_{k}(\frac{N}{(log N)^{\frac{A}{2} −4^{k−3/2}+2^{k−1}−1}} ).  (4.6)

We have

S_{P} (N, j) = ∑_{d_{1},d_{2},... ,d_{k−1}≤R} ( ∏_{i=1}^{k−1} μ(d_{i}) log \frac{R}{d_{i}})( ∑_{\begin{matrix}n=1 \\ d_{i}|n+j_{i}, 1≤i≤k−1 \end{matrix}}^{N} Λ_{P} (n)).  (4.7)

Let

T_{P} (N, j) = ∑_{\begin{matrix}n=1 \\ d_{i}|n+j_{i}, 1≤i≤k−1 \end{matrix}}^{N} Λ_{P} (n).  (4.8)

The k −1 congruence relations n ≡ −j_{i}(mod d_{i}) will have no solutions unless (d_{r}, d_{s})|j_{s} − j_{r} for all 1 ≤ r < s ≤ k − 1. If these divisibility conditions hold, then by the Chinese remainder theorem there exists a unique solution to these congruences n ≡ a(mod [d_{1}, d_{2}, …, d_{k−1}]) for some a = a(d, j). Here a satisfies the original congruences a ≡ −j_{i}(mod d_{i}) for 1 ≤ i ≤ k − 1. Thus we have

T_{P} (N, j) = [(d_{r}, d_{s})|j_{s} − j_{r}, 1 ≤ r < s ≤ k − 1]( ∑_{\begin{matrix}1≤n≤N \\ n≡a(mod D_{k−1}) \end{matrix}} Λ_{P} (n))

= [(d_{r}, d_{s})|j_{s} − j_{r}, 1 ≤ r < s ≤ k − 1]ψ_{P} (N; D_{k−1}, a).  (4.9)

We next have that

ψ_{P} (N; D_{k−1}, a) = ∑_{d≤P} μ(d) log \frac{P}{d} ∑_{\begin{matrix}1≤n≤N \\ n≡a(mod D_{k−1}) \\ n≡0(mod d) \end{matrix}} 1.

The two congruences in this sum are solvable provided (d, D_{k−1})|a, in which case we have that n runs through a residue class modulo [D_{k−1}, d]. Hence

ψ_{P} (N; D_{k−1}, a) = N ∑_{\begin{matrix}d≤P \\ (d,D_{k−1})|a \end{matrix}} \frac{μ(d)}{[D_{k−1}, d]} log \frac{P}{d} + O(P).

We now write d = gd′, where g = (d, D_{k−1}). Hence [d, D_{k−1}] = D_{k−1}d′, and by Lemma 2.1

ψ_{P} (N; D_{k−1}, a) = \frac{N}{D_{k−1}} ∑_{\begin{matrix}g|D_{k−1}, g|a \\ g≤P \end{matrix}} μ(g) ∑_{\begin{matrix}d′≤ \frac{P}{g} \\ (d′,D_{k−1})=1 \end{matrix}} \frac{μ(d′)}{d′} log \frac{P}{gd′} + O(P)

= \frac{N}{ϕ(D_{k−1})} ∑_{\begin{matrix}g|D_{k−1}, g|a \\ g≤P \end{matrix}} μ(g)

+O(\frac{N}{D_{k−1}} ∑_{\begin{matrix}g|D_{k−1}, g|a \\ g≤P \end{matrix}} μ^{2}(g)e^{−c_{1}\sqrt{log(P/g)}}) + O(P).

Since a ≡ −j_{i}(mod d_{i}) for 1 ≤ i ≤ k − 1 and g|a we see that (g, d_{i})|j_{i} for 1 ≤ i ≤ k − 1, and conversely since g|D_{k−1} these divisibility conditions imply that g|a. Hence

ψ_{P} (N; D_{k−1}, a) = \frac{N}{ϕ(D_{k−1})} ∑_{\begin{matrix}g|D_{k−1} \\ g≤P \\ (g,d_{i})|j_{i}, 1≤i≤k−1 \end{matrix}} μ(g)

+O(\frac{N}{D_{k−1}} ∑_{\begin{matrix}g|D_{k−1} \\ g≤P \\ (g,d_{i})|j_{i}, 1≤i≤k−1 \end{matrix}} μ^{2}(g)e^{−c_{1}\sqrt{log(P/g)}}) + O(P). (4.10)

The truncated Möbius function sum complicates the calculations of our pure correlations when one or more of the j_{i} = 0, but when all the j_{i} ≠ 0 the truncation problem disappears. Thus, we see in this sum that g ≤ ∏_{i=1}^{k−1} |j_{i}| ≤ max |j_{i}|^{k−1}, and hence provided

max_{1≤i≤k−1} |j_{i}| ≤ P^{\frac{1}{k−1}}  (4.11)

we have

∑_{\begin{matrix}g|D_{k−1} \\ g≤P \\ (g,d_{i})|j_{i}, 1≤i≤k−1 \end{matrix}} μ(g) = ∑_{\begin{matrix}g|D_{k−1} \\ (g,d_{i})|j_{i}, 1≤i≤k−1 \end{matrix}} μ(g) = \{ \begin{matrix}1, & if (d_{i}, j_{i}) = 1, 1 ≤ i ≤ k − 1, \\ 0, & otherwise. \end{matrix}

We conclude that subject to (4.11),

\begin{aligned}ψ_{P} (N; D_{k−1}, a) & = [(d_{i}, j_{i}) = 1, 1 ≤ i ≤ k − 1]\frac{N}{ϕ(D_{k−1})} \\ & + O(\frac{N}{D_{k−1}} d(D_{k−1})e^{−c_{1}\sqrt{log(P/ max |j_{i}|^{k−1})}}) + O(P). \end{aligned}  (4.12)

Hence by (4.3), (4.7), (4.8), (4.9), and (4.12), we obtain

S_{P} (N, j) =NW_{R}(j) + O(P R^{k−1})

+ O(N log^{k−1} Ne^{−c_{1}\sqrt{log _{\frac{P}{max |j_{i}|^{k−1}}}}} ∑_{d_{1},d_{2},... ,d_{k−1}≤R} \frac{d(D_{k−1})}{D_{k−1}}). (4.13)

We now estimate the sum in the second error term sufficiently well for our needs. Letting

D_{R}(n) = ∑_{\begin{matrix}e|n \\ e≤R \end{matrix}} d(e),

then

∑_{n≤N} D_{R}(n)^{m} = ∑_{n≤N} ∑_{\begin{matrix}e_{1},e_{2},... ,e_{m}≤R \\ e_{i}|n, 1≤i≤m \end{matrix}} d(e_{1})d(e_{2}) … d(e_{m})

= ∑_{e_{1},e_{2},... ,e_{m}≤R} d(e_{1})d(e_{2}) … d(e_{m}) ∑_{\begin{matrix}n≤N \\ e_{i}|n,1≤i≤m \end{matrix}} 1

= N ∑_{e_{1},e_{2},... ,e_{m}≤R} \frac{d(e_{1})d(e_{2}) … d(e_{m})}{[e_{1}, e_{2}, …, e_{m}]} + O(( ∑_{e≤R} d(e))^{m}).

The last error term is O(R^{m} log^{m} R), and D_{R}(n) ≤ ∑_{e|n} d(n) = d^{2}(n). Hence, using the estimate [19]

∑_{m≤N} d(m)^{k} ≪_{k} N log^{2^{k}−1} N,  (4.14)

we have

∑_{n≤N} D_{R}(n)^{m} ≤ ∑_{n≤N} d(n)^{2m} ≪_{m} N log^{4^{m}−1} N.

Thus

\begin{aligned}∑_{d_{1},d_{2},... ,d_{m}≤R} \frac{d(D_{m})}{D_{m}} & ≤ ∑_{e_{1},e_{2},... ,e_{m}≤R} \frac{d(e_{1})d(e_{2}) … d(e_{m})}{[e_{1}, e_{2}, …, e_{m}]} \\ & ≪_{m} log^{4^{m}−1} N + \frac{R^{m} log^{m} R}{N}. \end{aligned}

Hence we conclude

S_{P} (N, j) =NW_{R}(j) + O(P R^{k−1})
+ O_{k}((N log^{4^{k−1}+k−2} N + R^{k−1} log^{2k−2} N)e^{−c_{1}\sqrt{log _{\frac{P}{max |j_{i}|^{k−1}}}}} ).

(4.15)

Taking P = R proves the first part of Theorem 4.1. Equation (4.15) may also be useful when P is not too large but larger than R.

We next turn to the case P = N. In this case ψ_{P} (N; q, a) = ψ(N; q, a) + O(log N), the error term coming from Λ_{N}(1). We apply (1.29) and have

ψ(N; D_{k−1}, a) = [(D_{k−1}, a) = 1]\frac{N}{ϕ(D_{k−1})} + E(N; D_{k−1}, a).

The condition that (D_{k−1}, a) = 1 is equivalent to having (d_{i}, a) = 1 for 1 ≤ i ≤ k −1, and since a ≡ −j_{i}(mod d_{i}) these conditions are equivalent to (d_{i}, j_{i}) = 1 for 1 ≤ i ≤ k − 1. We conclude that

ψ(N; D_{k−1}, a) = [(d_{i}, j_{i}) = 1, 1 ≤ i ≤ k − 1]\frac{N}{ϕ(D_{k−1})} + E(N; D_{k−1}, a).  (4.16)

By (4.9) we thus obtain in place of (4.13)

S_{N}(N, j) = NW_{R}(j) + O( log^{k−1} N ∑_{d_{1},d_{2},... ,d_{k−1}≤R} μ^{2}(D_{k−1})|E(N; D_{k−1}, a)|)

+ O(log N log^{k−1} R ∏_{i=1}^{k−1} d(1 + j_{i})),

(4.17)

the last error term coming from the n = 1 term. This last error will be negligible since it is ≪ (log N(max_{i} |j_{i}|)^{ϵ})^{k} ≪_{k} N^{ϵ} since max_{i} |j_{i}| ≪ R^{\frac{1}{k}}. For the sum in the error term, we have

∑_{d_{1},d_{2},... ,d_{k−1}≤R}μ^{2}(D_{k−1})|E(N; D_{k−1}, a)|

= ∑_{m≤R^{k−1}} μ^{2}(m) max_{a(mod m)} |E(N; m, a)| ∑_{\begin{matrix}m=D_{k−1} \\ d_{1},d_{2},... ,d_{k−1}≤R \end{matrix}} 1

≤ ∑_{m≤R^{k−1}} μ^{2}(m) max_{a(mod m)} |E(N; m, a)|d_{l}(m),

where l = 2^{k−1} − 1. The factor of d_{l}(m) arises since, given m, the number of solutions of m = D_{r} is bounded by d_{2^{r}−1}(m), since the least common multiple of r squarefree numbers can always be expressed uniquely as the product of up to 2^{r}−1 numbers which are pairwise relatively prime, determined by exactly which of the original numbers d_{1}, d_{2}, ⋯, d_{r} each factor divides. (We will use this decomposition in later sections.) Applying Cauchy’s inequality we see the previous expression is

≪ \sqrt{∑_{m≤R^{k−1}} \frac{d_{l}(m)^{2}}{m}} \sqrt{∑_{m≤R^{k−1}} m max_{a(mod m)} |E(N; m, a)|^{2}}.

We now use the generalization of (4.14)

∑_{m≤N} d_{r}(m)^{k} ≪_{k} N log^{r^{k}−1} N,  (4.18)

and the trivial estimate |E(N; m, a)| ≪ \frac{N log N}{m} to see the error term above is

≪_{l} \sqrt{(log R)^{l^{2}}N log N ∑_{m≤R^{k−1}} max_{a(mod m)} |E(N; m, a)|}.

We now apply (1.30) to conclude this error is, for R^{k−1} ≤ N^{ϑ−ϵ},

≪_{k} \frac{N}{(log N)^{\frac{A}{2} −4^{k−3/2}+2^{k−1}−1}} ,

which finishes the proof of Theorem 4.1.

5. Pair Correlation of Λ_{R}(n)

We first prove the case k = 1 of Theorem 1.1. We have

S_{1}(N, j, (1)) = ∑_{n≤N} Λ_{R}(n + j) = ∑_{d≤R} μ(d) log \frac{R}{d} ∑_{{1≤n≤N \atop d|n+j}} 1

= N ∑_{d≤R} \frac{μ(d)}{d} log \frac{R}{d} + O(R)
= N + O(\frac{N}{(log R)^{A}}) + O(R)  (5.1)

by Lemma 2.1. This proves Theorem 1.1 in this case.

We now examine the case k = 2 of Theorem 1.1. These results have been proved before in [8]. The proof we give here models the procedure we will use for higher correlations without any of the truncation complications which will arise there. In view of the comment following Theorem 1.1, we need to consider

S_{2}(k) = ∑_{n=1}^{N} Λ_{R}(n)Λ_{R}(n + k),  (5.2)

In our earlier notation, we have S_{2}(k) = S_{2}(N, (0, k), (1, 1)) if k ≠ 0, and S_{2}(0) = S_{2}(N, (0), (2)).

Theorem 5.1 We have

S_{2}(0) = N log R + O(N) + O(R^{2}),  (5.3)

and for 0 < |k| ≤ R and any A > 0, we have

S_{2}(k) = 𝔖_{2}(k)N + O(\frac{k}{ϕ(k)} \frac{N}{(log 2R/k)^{A}}) + O(R^{2}).  (5.4)

Graham [13] has proved (5.3) for 1 ≤ R ≤ N with the error term O(R^{2}) removed. By Theorem 5.1 we see that Theorem 1.1 is true for k = 2, with C(2) = 1 and C(1, 1) = 1.

Proof of Theorem 5.1. Applying the definition of Λ_{R}(n), we have

S_{2}(k) = ∑_{d,e≤R} μ(d) log(R/d)μ(e) log(R/e) ∑_{{n≤N \atop d|n,e|n+k}} 1.

In the inner sum the two divisibility conditions imply that n will run through a residue class modulo [d, e] provided (d, e)|k, and there will be no solution for n otherwise. Therefore we have

S_{2}(k) = N ∑_{{d,e≤R \atop (d,e)|k}} \frac{μ(d) log(R/d)μ(e) log(R/e)}{[d, e]} + O( ∑_{d,e≤R} log(R/d) log(R/e))

= NT_{2}(k) + O(R^{2}).

(5.5)

To evaluate T_{2}(k) we break the sum into relatively prime summands in order to handle [d, e]. We let d = a_{1}b_{12} and e = a_{2}b_{12} where b_{12} = (d, e) so that a_{1}, a_{2}, and b_{12} are pairwise relatively prime. For higher correlations this decomposition notation will be used as well. Hence we have

T_{2}(k) = ^{∑′} ; {a_{1}b_{12}≤R \atop a_{2}b_{12}≤R} ; b_{12}|k \frac{μ^{2}(b_{12})}{b_{12}} \frac{μ(a_{1})}{a_{1}} \frac{μ(a_{2})}{a_{2}} log \frac{R}{a_{1}b_{12}} log \frac{R}{a_{2}b_{12}}

= ^{∑′} ; {a_{2}b_{12}≤R \atop b_{12}|k} \frac{μ^{2}(b_{12})}{b_{12}} \frac{μ(a_{2})}{a_{2}} log \frac{R}{a_{2}b_{12}} ∑_{{a_{1}≤R/b_{12} \atop (a_{1},a_{2}b_{12})=1}} \frac{μ(a_{1})}{a_{1}} log \frac{R/b_{12}}{a_{1}} ,

where the prime on the summation indicates that all the summands are relatively prime to each other. We now apply Lemma 2.1 with j = 0 to obtain for any B > 0

T_{2}(k) = ^{∑′} ; {a_{2}b_{12}≤R \atop b_{12}|k} \frac{μ^{2}(b_{12})}{ϕ(b_{12})} \frac{μ(a_{2})}{ϕ(a_{2})} log \frac{R}{a_{2}b_{12}} + O( ^{∑′} ; {a_{2}b_{12}≤R \atop b_{12}|k} \frac{μ^{2}(b_{12})μ^{2}(a_{2}) log \frac{R/b_{12}}{a_{2}}}{b_{12}a_{2} log^{B}(2R/b_{12})} ).

For the main term above we sum over a_{2} and apply Lemma 2.1 again with j = 1 to see this term is equal to

∑_{{b_{12}≤R \atop b_{12}|k}} \frac{μ^{2}(b_{12})}{ϕ(b_{12})}𝔖_{2}(b_{12}) + O( ∑_{{b_{12}≤R \atop b_{12}|k}} \frac{μ^{2}(b_{12})}{ϕ(b_{12}) log^{B}(2R/b_{12})}).

Summing over a_{2} in the error term in the formula for T_{2}(k) above, we conclude

T_{2}(k) = ∑_{{b_{12}≤R \atop b_{12}|k}} \frac{μ^{2}(b_{12})}{ϕ(b_{12})}𝔖_{2}(b_{12}) + O( ∑_{{b_{12}≤R \atop b_{12}|k}} \frac{μ^{2}(b_{12})}{ϕ(b_{12}) log^{B−2}(2R/b_{12})}).  (5.6)

We now consider two cases. If k = 0 the main term is

∑_{b_{12}≤R} \frac{μ^{2}(b_{12})}{ϕ(b_{12})}𝔖_{2}(b_{12}) = log R + O(1)

by Lemma 2.4 with j = 1, and the error term in (5.6) is also O(1). This proves (5.3). If 0 < |k| ≤ R the main term is

∑_{b_{12}|k} \frac{μ^{2}(b_{12})}{ϕ(b_{12})}𝔖_{2}(b_{12}) = 𝔖_{2}(k)

by the second part of Lemma 2.4, and the error term is

≪ \frac{1}{(log 2R/k)^{B−2}} ∑_{b_{12}|k} \frac{μ^{2}(b_{12})}{ϕ(b_{12})} = \frac{k}{ϕ(k)(log 2R/k)^{B−2}} ,

which proves (5.4).

It is worth noting that we can also give a very short proof of (5.4) using Theorem 4.1 from the last section. With j = (0, k), we have

W_{R}(j) = ∑_{\begin{matrix}d_{1}≤R \\ (d_{1},k)=1 \end{matrix}} \frac{μ(d_{1})}{ϕ(d_{1})} log(R/d_{1})

= 𝔖_{2}(k) + O(e^{−c_{1}\sqrt{log R}})  (5.7)

by Lemma 2.1. By Theorem 4.1 this proves (5.4) and also evaluates the mixed second correlation as well.

6. Triple correlation for Λ_{R}(n)

To prove Theorem 1.1 when k = 3 we need to evaluate the sums

S_{3}(k) = ∑_{n=1}^{N} Λ_{R}^{2}(n)Λ_{R}(n + k),  (6.1)

and, for non-zero k_{1} ≠ k_{2},

S_{3}(k_{1}, k_{2}) = ∑_{n=1}^{N} Λ_{R}(n)Λ_{R}(n + k_{1})Λ_{R}(n + k_{2})  (6.2)

In the notation of Theorem 1.1 we have S_{3}(0)=S_{3}(N, (0), (3)), S_{3}(k)=S_{3}(N, (0, k), (2, 1)) if k ≠ 0, and S_{3}(k_{1}, k_{2}) = S_{3}(N, (0, k_{1}, k_{2}), (1, 1, 1)) for non-zero k_{1} ≠ k_{2}. We will obtain the following results on these correlations.

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 3 (2003), #A05 34

Theorem 6.1 We have

S_{3}(0) = \frac{3}{4}N log^{2} R + O(N log N(log log R)^{18}) + O(R^{3}),  (6.3)

and, for k ≠ 0, |k| ≤ R^{\frac{1}{2} −ϵ},

S_{3}(k) = 𝔖_{2}(k)N log R + O(N(log log R)^{13}) + O(R^{3}),  (6.4)

and letting k = (0, k_{1}, k_{2}), k_{1} ≠ k_{2} ≠ 0, if (k^{∗})^{2} < R/2, where k^{∗} = max(|k_{1}|, |k_{2}|), then

S_{3}(k_{1}, k_{2}) = 𝔖(k)N + O (Ne^{−c_{1}\sqrt{log(\frac{R}{2(k^{∗})^{2}} )}} log^{8} R) + O(R^{3}).  (6.5)

We consider the general situation and specialize later. Let

S_{3}(k_{1}, k_{2}, k_{3}) = ∑_{n=1}^{N} Λ_{R}(n + k_{1})Λ_{R}(n + k_{2})Λ_{R}(n + k_{3})  (6.6)

Expanding, we have

S_{3}(k_{1}, k_{2}, k_{3}) = ∑_{d_{1},d_{2},d_{3}≤R} μ(d_{1}) log(R/d_{1})μ(d_{2}) log(R/d_{2})μ(d_{3}) log(R/d_{3}) ∑_{{n≤N \atop d_{1}|n+k_{1}} ; d_{2}|n+k_{2} ; d_{3}|n+k_{3}} 1.

The sum over n is zero unless (d_{1}, d_{2})|k_{2} − k_{1}, (d_{1}, d_{3})|k_{3} − k_{1}, and (d_{2}, d_{3})|k_{3} − k_{2}, in which case the sum runs through a residue class modulo [d_{1}, d_{2}, d_{3}], and we have

∑_{{n≤N \atop d_{1}|n+k_{1}} ; d_{2}|n+k_{2} ; d_{3}|n+k_{3}} 1 = \frac{N}{[d_{1}, d_{2}, d_{3}]} + O(1).

We conclude

S_{3}(k_{1}, k_{2}, k_{3}) = N ∑_{{d_{1},d_{2},d_{3}≤R \atop (d_{1},d_{2})|k_{2}−k_{1}} ; (d_{1},d_{3})|k_{3}−k_{1} ; (d_{2},d_{3})|k_{3}−k_{2}}\frac{μ(d_{1}) log(R/d_{1})μ(d_{2}) log(R/d_{2})μ(d_{3}) log(R/d_{3})}{[d_{1}, d_{2}, d_{3}]} + O(R^{3})
= NT_{3}(k_{1}, k_{2}, k_{3}) + O(R^{3}).

(6.7)

We now decompose d_{1}, d_{2}, and d_{3} into relatively prime factors

d_{1} = a_{1}b_{12}b_{13}a_{123}
d_{2} = a_{2}b_{12}b_{23}a_{123}
d_{3} = a_{3}b_{13}b_{23}a_{123}

where a_{χ} or b_{χ} is a divisor of the d_{i}’s where i occurs in χ. Since the d_{i}’s are squarefree, these new variables are pairwise relatively prime. The letters a and b reflect the parity of the number of d_{i}’s that the new variable divides. We will let D denote the set of a_{χ}’s and b_{χ}’s which satisfy the conditions

a_{1}b_{12}b_{13}a_{123} ≤ R
a_{2}b_{12}b_{23}a_{123} ≤ R  (6.8)
a_{3}b_{13}b_{23}a_{123} ≤ R
b_{12}a_{123}|k_{2} − k_{1}, b_{13}a_{123}|k_{3} − k_{1},  b_{23}a_{123}|k_{3} − k_{2}.  (6.9)

Letting

L_{i}(R) = log \frac{R}{d_{i}},

we have

\begin{aligned}T_{3}(k_{1}, k_{2}, k_{3}) & = \begin{matrix}∑ & ′ \\ D \end{matrix} \frac{μ(a_{1})μ(a_{2})μ(a_{3})μ^{2}(b_{12})μ^{2}(b_{13})μ^{2}(b_{23})μ(a_{123})}{a_{1}a_{2}a_{3}b_{12}b_{13}b_{23}a_{123}}L_{1}(R)L_{2}(R)L_{3}(R) \\ & = \begin{matrix}∑ & ′ \\ D \end{matrix} f_{R}(d_{1}, d_{2}, d_{3}). \end{aligned} (6.10)

We now will sum over a_{1}, a_{2}, and a_{3} using Lemma 2.1 and Lemma 2.3. In order to apply these lemmas we need each a_{i} to range over a long enough interval, and therefore we need to restrict the ranges of some of the other variables. The excluded ranges will later be shown to make a lower order contribution. If D is a product of some of the variables in D, we let D(D) denote the subset of D where the variables not occuring in D are eliminated from the inequalities in (6.8) and divisibility conditions in (6.9). Thus, letting D_{1} = a_{2}a_{3}b_{12}b_{13}b_{23}a_{123}, we have that D(D_{1}) no longer includes the variable a_{1} and we take a_{1} = 1 in (6.8). We now obtain on summing over a_{1} using Lemma 2.1 and taking R_{1} < R,

T_{3}(k_{1}, k_{2}, k_{3}) = ^{∑′} ; {D \atop b_{12}b_{13}a_{123}≤R_{1}} f_{R}(d_{1}, d_{2}, d_{3}) + ^{∑′} ; {D \atop R_{1}<b_{12}b_{13}a_{123}≤R} f_{R}(d_{1}, d_{2}, d_{3})

= ^{∑′} ; {D(D_{1}) \atop b_{12}b_{13}a_{123}≤R_{1}} \frac{μ(a_{2})μ(a_{3})μ(a_{123})μ^{2}(D_{1})}{ϕ(D_{1})}L_{2}(R)L_{3}(R) + E_{1}(R)

+ ^{∑′} ; {D \atop R_{1}<b_{12}b_{13}a_{123}≤R} f_{R}(d_{1}, d_{2}, d_{3})

= U_{3}(k_{1}, k_{2}, k_{3}) + E_{1}(R) + E_{f}(D),  (6.11)

where

E_{1}(R) = ^{∑′} ; {D \atop b_{12}b_{13}a_{123}≤R_{1}} \frac{μ(a_{2})μ(a_{3})μ(a_{123})μ^{2}(D_{1})}{D_{1}}L_{2}(R)L_{3}(R)r_{0}(\frac{R}{b_{12}b_{13}a_{123}} , D_{1})

≪ e^{−c_{1}\sqrt{log(R/R_{1})}} log^{8} R.

Hence

T_{3}(k_{1}, k_{2}, k_{3}) = U_{3}(k_{1}, k_{2}, k_{3}) + O(e^{−c_{1}\sqrt{log(R/R_{1})}} log^{8} R) + E_{f}(D).  (6.12)

Denote the summand for U_{3}(k_{1}, k_{2}, k_{3}) by g_{R}(d_{1}, d_{2}, d_{3}), which does not depend on a_{1}. Because of the symmetry in our original variables in (6.10), we could equally well have summed over a_{2} or a_{3} above and obtained the same expression for g_{R}(d_{1}, d_{2}, d_{3}) with the appropriate change in variables and renumbering of the k′_{i}s. We will later make use of this fact for some of our error terms, and will let the summation conditions D(D) determine which variables appear in g_{R} and subsequent summands. Returning to (6.11), we obtain on summing over a_{2} using Lemma 2.1 that, with D_{2} = a_{3}b_{12}b_{13}b_{23}a_{123} and R_{2} < R,

U_{3}(k_{1}, k_{2}, k_{3}) = ^{∑′} ; {D(D_{1}) \atop b_{12}b_{13}a_{123}≤R_{1}} ; b_{12}b_{23}a_{123}≤R_{2} g_{R}(d_{1}, d_{2}, d_{3}) + ^{∑′} ; {D(D_{1}) \atop b_{12}b_{13}a_{123}≤R_{1}} ; R_{2}<b_{12}b_{23}a_{123}≤R g_{R}(d_{1}, d_{2}, d_{3})

= ^{∑′} ; {D(D_{2}) \atop b_{12}b_{13}a_{123}≤R_{1}} ; b_{12}b_{23}a_{123}≤R_{2} \frac{μ(a_{3})μ(a_{123})μ^{2}(D_{2})}{ϕ(D_{2})}L_{3}(R)𝔖_{2}(D_{2})

+ O(e^{−c_{1}\sqrt{log(R/R_{2})}} log^{6} R) + ^{∑′} ; {D(D_{1}) \atop b_{12}b_{13}a_{123}≤R_{1}} ; R_{2}<b_{12}b_{23}a_{123}≤R g_{R}(d_{1}, d_{2}, d_{3})

= V_{3}(k_{1}, k_{2}, k_{3}) + O(e^{−c_{1}\sqrt{log(R/R_{2})}} log^{6} R) + E_{g}(D(D_{1})). (6.13)

Finally, we denote the summand in V_{3}(k_{1}, k_{2}, k_{3}) by h_{R}(d_{1}, d_{2}, d_{3}) and we let D_{3} = b_{12}b_{13}b_{23}a_{123} and R_{3} < R. Then by Lemma 2.3 with j = 1 we obtain

V_{3}(k_{1}, k_{2}, k_{3}) = ^{∑′} ; {D(D_{2}) \atop b_{12}b_{13}a_{123}≤R_{1}} ; b_{12}b_{23}a_{123}≤R_{2} ; b_{13}b_{23}a_{123}≤R_{3} h_{R}(d_{1}, d_{2}, d_{3}) + ^{∑′} ; {D(D_{2}) \atop b_{12}b_{13}a_{123}≤R_{1}} ; b_{12}b_{23}a_{123}≤R_{2} ; R_{3}<b_{13}b_{23}a_{123}≤R h_{R}(d_{1}, d_{2}, d_{3})

= − ^{∑′} ; {D(D_{3}) \atop b_{12}b_{13}a_{123}≤R_{1}} ; b_{12}b_{23}a_{123}≤R_{2} ; b_{13}b_{23}a_{123}≤R_{3} \frac{μ^{2}(D_{3})μ(a_{123})μ((D_{3}, 2))}{ϕ(D_{3})}𝔖_{2}(2D_{3})𝔖_{3}(2D_{3})

+ O(e^{−c_{1}\sqrt{log(R/R_{3})}} log^{4} R) + ^{∑′} ; {D(D_{2}) \atop b_{12}b_{13}a_{123}≤R_{1}} ; b_{12}b_{23}a_{123}<R_{2} ; R_{3}<b_{13}b_{23}a_{123}<R h_{R}(d_{1}, d_{2}, d_{3})

= W_{3}(k_{1}, k_{2}, k_{3}) + O(e^{−c_{1}\sqrt{log(R/R_{3})}} log^{4} R) + E_{h}(D(D_{2})). (6.14)

We now prove Theorem 6.1 by considering each case separately. We first prove (6.5) which is the case where the error terms are the easiest to handle.

7. Evaluation of S_{3}(k_{1}, k_{2})

We consider S_{3}(k_{1}, k_{2}) by taking k_{1} ≠ k_{2} ≠ 0 and k_{3} = 0 in (6.9) which therefore becomes

b_{12}a_{123}|k_{2} − k_{1}, b_{13}a_{123}|k_{1}, b_{23}a_{123}|k_{2}.  (7.1)

These conditions imply, letting k^{∗} = max(|k_{1}|, |k_{2}|), that

b_{12}b_{13}a_{123} < 2(k^{∗})^{2}, b_{12}b_{23}a_{123} < 2(k^{∗})^{2}, b_{13}b_{23}a_{123} < 2(k^{∗})^{2}.  (7.2)

Hence, taking R_{1} = R_{2} = R_{3} = 2(k^{∗})^{2} < R, we see that the error terms E_{f}, E_{g}, and E_{h} in (6.11), (6.13), and (6.14) are identically zero, and therefore

T_{3}(k_{1}, k_{2}) = W_{3}(k_{1}, k_{2}) + O(e^{−c_{1}\sqrt{log(\frac{R}{2(k^{∗})^{2}} )}} log^{8} R).  (7.3)

Now that the variables a_{1}, a_{2}, and a_{3} have been eliminated, the bounds on the variables in D are automatically satisfied from (7.2), and, provided (k^{∗})^{2} < R/2, we have

W_{3}(k_{1}, k_{2}) = − ^{∑′} ; {b_{13}a_{123}|k_{1} \atop b_{23}a_{123}|k_{2}} ; b_{12}a_{123}|k_{2}−k_{1} \frac{μ^{2}(D_{3})μ(a_{123})μ((D_{3}, 2))}{ϕ(D_{3})}𝔖_{2}(2D_{3})𝔖_{3}(2D_{3}).  (7.4)

This sum is over square-free divisors, and therefore we let

k_{1} = s_{1}K_{1}, k_{2} = s_{2}K_{2},  (7.5)

where K_{1} and K_{2} are the largest square-free divisors of k_{1} and k_{2}, and let

κ = (k_{1}, k_{2}), K_{12} = (K_{1}, K_{2}).  (7.6)

Then we may rewrite W_{3} as

W_{3}(k_{1}, k_{2}) = − ^{∑′} ; {b_{13}a_{123}|K_{1} \atop b_{23}a_{123}|K_{2}} ; b_{12}a_{123}|k_{2}−k_{1} \frac{μ^{2}(D_{3})μ(a_{123})μ((D_{3}, 2))}{ϕ(D_{3})}𝔖_{2}(2D_{3})𝔖_{3}(2D_{3}).  (7.7)

The proof of (6.5) will follow from (6.7), (7.3) and Lemma 2.5 once we prove that

W_{3}(k_{1}, k_{2}) = 𝔖_{2}(K_{12})𝔖_{3}(Δ) = 𝔖_{2}(κ)𝔖_{3}(Δ) = 𝔖(k).  (7.8)

We now let

K_{1} = K_{12}j_{1}, K_{2} = K_{12}j_{2}, k_{2} − k_{1} = K_{12}(s_{2}j_{2} − s_{1}j_{1})  (7.9)

where K_{12}, j_{1}, and j_{2} are square-free and pairwise relatively prime (s_{2}j_{2} − s_{1}j_{1} may not be square-free or relatively prime with K_{12}.) Next, let

b_{13} = c_{13}d_{13}, b_{23} = c_{23}d_{23}  (7.10)

where c_{13}, c_{23}|K_{12}, d_{13}|j_{1}, d_{23}|j_{2}, and c_{13}, d_{13}, c_{23}, d_{23}, b_{12}, a_{123} are thus all pairwise relatively prime. We also see that a_{123}|K_{12}. Thus, with D_{3} = b_{12}c_{13}c_{23}d_{13}d_{23}a_{123},

W_{3}(k_{1}, k_{2}) = −\begin{matrix}∑ & ′ \\ c_{13}c_{23}a_{123}|K_{12} \end{matrix} μ(a_{123}) ^{∑′} ; {b_{12}|k_{2}−k_{1} \atop d_{13}|j_{1}} ; d_{23}|j_{2} \frac{μ^{2}(D_{3})μ((D_{3}, 2))}{ϕ(D_{3})}𝔖_{2}(2D_{3})𝔖_{3}(2D_{3}). (7.11)

We first sum over d_{13} in the inner sum. To do this, we take D_{4} = b_{12}c_{13}c_{23}d_{23}a_{123} and have

∑_{{d_{13}|j_{1} \atop (d_{13},D_{4})=1}} \frac{μ^{2}(D_{3})μ((D_{3}, 2))}{ϕ(D_{3})}𝔖_{2}(2D_{3})𝔖_{3}(2D_{3})

= 2C_{2} \frac{μ^{2}(D_{4})}{ϕ(D_{4})} ∑_{{d_{13}|j_{1} \atop (d_{13},D_{4})=1}} \frac{μ^{2}(d_{13})}{ϕ(d_{13})}μ((d_{13}D_{4}, 2))H_{2}(2d_{13}D_{4})𝔖_{3}(2d_{13}D_{4}).

We now break the sum on the right into two sums according to whether d_{13} is even or odd, in the former case we let d_{13} = 2d, and on using Lemma 2.4 we obtain that the right-hand side is

= \frac{2C_{2}μ^{2}(D_{4})H_{2}(D_{4})}{ϕ(D_{4})}\{ − [(D_{4}, 2) = 1] ∑_{{2d|j_{1} \atop (d,2D_{4})=1}} \frac{μ^{2}(d)}{ϕ_{2}(d)}𝔖_{3}(2dD_{4})

+μ((D_{4}, 2)) ∑_{{d_{13}|j_{1} \atop (d_{13},2D_{4})=1}} \frac{μ^{2}(d_{13})}{ϕ_{2}(d_{13})}𝔖_{3}(2d_{13}D_{4})\}

= \frac{2C_{2}μ^{2}(D_{4})H_{2}(D_{4})}{ϕ(D_{4})}( − [(D_{4}, 2) = 1][2|j_{1}] + μ((D_{4}, 2)))𝔖_{3}(2D_{4}j_{1}).

We will denote

B(d) = \frac{2C_{2}μ^{2}(d)H_{2}(d)}{ϕ(d)}.  (7.12)

Now substituting into (7.11), and letting D_{5} = b_{12}c_{13}c_{23}a_{123}, the sum over d_{23} is equal to

B(D_{5}) ∑_{(d_{23},D_{5})=1^{d_{23}|j_{2}}} \frac{μ^{2}(d_{23})H_{2}(d_{23})}{ϕ(d_{23})}( − [(d_{23}D_{5}, 2) = 1][2|j_{1}] + μ((d_{23}D_{5}, 2)))𝔖_{3}(2d_{23}D_{5}j_{1}).

Since (j_{1}, j_{2}) = 1, and d_{23}|j_{2}, we may replace the condition (d_{23}, D_{5}) = 1 in the sum by (d_{23}, j_{1}D_{5}) and divide the sum into two sums with even or odd terms as above to see that this expression is

= −B(D_{5})[(D_{5}, 2) = 1][2|j_{2}] ∑_{{2d|j_{2} \atop (d,2j_{1}D_{5})=1}} \frac{μ^{2}(d)}{ϕ_{2}(d)}𝔖_{3}(2dD_{5}j_{1})

+B(D_{5})( − [(D_{5}, 2) = 1][2|j_{1}] + μ((D_{5}, 2))) ∑_{{d_{23}|j_{2} \atop (d_{23},2j_{1}D_{5})=1}} \frac{μ^{2}(d_{23})}{ϕ_{2}(d_{23})}𝔖_{3}(2d_{23}D_{5}j_{1})

= B(D_{5})( − [(D_{5}, 2) = 1]([2|j_{1}] + [2|j_{2}]) + μ((D_{5}, 2)))𝔖_{3}(2D_{5}j_{1}j_{2}).

Now let

Δ = k_{1}k_{2}(k_{2} − k_{1}) = s_{1}s_{2}K_{12}^{2}j_{1}j_{2}(k_{2} − k_{1}) = s_{1}s_{2}K_{12}^{3}j_{1}j_{2}(s_{2}j_{2} − s_{1}j_{1}).  (7.13)

We substitute the last result into (7.11) and sum over b_{12}. Let D_{6} = c_{13}c_{23}a_{123}. We claim that the relatively prime condition (b_{12}, D_{6}) = 1 may be replaced by (b_{12}, D_{6}j_{1}j_{2}) = 1. To see this, note that j_{1}, j_{2}, and K_{12} are pairwise relatively prime, and further (s_{1}, j_{2}) = 1 and (s_{2}, j_{1}) = 1. Thus

(k_{2} − k_{1}, j_{1}) = (K_{12}(s_{2}j_{2} − s_{1}j_{1}), j_{1}) = (s_{2}, j_{1}) = 1

and similarly (k_{2} − k_{1}, j_{2}) = 1. Hence, since b_{12}|k_{2} − k_{1}, we have (b_{12}, j_{1}j_{2}) = 1. Now summing over b_{12} our sum is

= B(D_{6}) ∑_{{b_{12}|k_{2}−k_{1} \atop (b_{12},D_{6}j_{1}j_{2})=1}} ( − [(b_{12}D_{6}, 2) = 1]([2|j_{1}] + [2|j_{2}]) + μ((b_{12}D_{6}, 2)))

× \frac{μ^{2}(b_{12})H_{2}(b_{12})}{ϕ(b_{12})}𝔖_{3}(2b_{12}D_{6}j_{1}j_{2})

= B(D_{6}) ∑_{{2b|k_{2}−k_{1} \atop (b,2D_{6}j_{1}j_{2})=1}} \frac{μ^{2}(b)}{ϕ_{2}(b)}( − [2|k_{2} − k_{1}][(D_{6}, 2) = 1])𝔖_{3}(2bD_{6}j_{1}j_{2})

+B(D_{6}) ∑_{{b_{12}|k_{2}−k_{1} \atop (b_{12},2D_{6}j_{1}j_{2})=1}} \frac{μ^{2}(b_{12})}{ϕ_{2}(b_{12})}(− [(D_{6}, 2) = 1]([2|j_{1}] + [2|j_{2}]) + μ((D_{6}, 2)))𝔖_{3}(2b_{12}D_{6}j_{1}j_{2})

= B(D_{6})(− [(D_{6}, 2) = 1]([2|j_{1}]+[2|j_{2}]+[2|k_{2} − k_{1}])+μ((D_{6}, 2)))𝔖_{3}(2D_{6}j_{1}j_{2}(k_{2} − k_{1})).

Now D_{6}|K_{12}|Δ, and hence

𝔖_{3}(2D_{6}j_{1}j_{2}(k_{2} − k_{1})) = 𝔖_{3}(2D_{6}Δ) = 𝔖_{3}(Δ).

We conclude that

W_{3}(k_{1}, k_{2})= −𝔖_{3}(Δ)\begin{matrix}∑ & ′ \\ D_{6}|K_{12} \end{matrix}μ(a_{123})B(D_{6})(−[(D_{6}, 2)=1]([2|j_{1}]+[2|j_{2}]+[2|k_{2} − k_{1}])+μ((D_{6}, 2))). (7.14)

If K_{12} is odd, then exactly one of the variables j_{1}, j_{2}, and k_{2} − k_{1} is even and the other two are odd. If K_{12} is even, then j_{1} and j_{2} are odd and k_{2} − k_{1} is even. Hence in either case

[2|j_{1}] + [2|j_{2}] + [2|k_{2} − k_{1}] = 1,

and therefore

W_{3}(k_{1}, k_{2}) = −𝔖_{3}(Δ)\begin{matrix}∑ & ′ \\ D_{6}|K_{12} \end{matrix} μ(a_{123})B(D_{6})( − [(D_{6}, 2) = 1] + μ((D_{6}, 2))).  (7.15)

When K_{12} is odd the expression in parentheses is zero, and hence

W_{3}(k_{1}, k_{2}) = 0, if K_{12} is odd.

If K_{12} is even, then the expression in parentheses in (7.15) is zero if D_{6} is odd, and is equal to −1 when D_{6} is even. Hence, we conclude

W_{3}(k_{1}, k_{2}) = [2|K_{12}]𝔖_{3}(Δ) ^{∑′} ; \begin{matrix}D_{6}|K_{12} \\ 2|D_{6} \end{matrix} μ(a_{123})B(D_{6}).  (7.16)

We could now evaluate this sum as before by summing over each variable in turn, but there is an easier approach, based on the observation that if a square-free number is a product of some factors, then necessarily those factors must be relatively prime with each other. Let z = vwy, and A be a set of natural numbers. Then for any arithmetic function a(z) we have

\begin{aligned}\begin{matrix}∑ & ′ \\ z∈A \end{matrix} μ^{2}(z)a(z)μ(y) & = ∑_{z∈A} μ^{2}(z)a(z) ∑_{w|z} ∑_{y| \frac{z}{w}} μ(y) \\ & = ∑_{z∈A} μ^{2}(z)a(z) ∑_{\begin{matrix}w|z \\ w=z \end{matrix}} 1 \\ & = ∑_{z∈A} μ^{2}(z)a(z). \end{aligned}  (7.17)

The sum in (7.16) is of this form, and therefore we have

W_{3}(k_{1}, k_{2}) = [2|K_{12}]𝔖_{3}(Δ) ∑_{\begin{matrix}z|K_{12} \\ 2|z \end{matrix}} B(z)

= 2C_{2}[2|K_{12}]𝔖_{3}(Δ) ∑_{\begin{matrix}2z′|K_{12} \\ (z′,2)=1 \end{matrix}} \frac{μ^{2}(z′)}{ϕ_{2}(z′)}

= 2C_{2}[2|K_{12}]𝔖_{3}(Δ)H_{2}(K_{12}),

where we used (2.3) in the last line. We conclude by (2.5) that

W_{3}(k_{1}, k_{2}) = 𝔖_{2}(K_{12})𝔖_{3}(Δ) = 𝔖_{2}(κ)𝔖_{3}(Δ),  (7.18)

which completes the proof of (7.8).

8. Evaluation of S_{3}(k), k ≠ 0

We now take k_{1} = k ≠ 0, k_{2} = k_{3} = 0 so that the divisibility conditions in (6.9) become

b_{12}a_{123}|k, b_{13}a_{123}|k,

and since our variables are relatively prime

b_{12}b_{13}a_{123}|k.  (8.1)

Taking R_{1} = k < R we see that E_{f} in (6.12) is identically zero. We will take R_{2} = R_{3} ≥ k^{2} to be chosen later as a function of R, and conclude from (6.12), (6.13), and (6.14) that

T_{3}(k) = W_{3}(k) + E_{g}(D(D_{1})) + E_{h}(D(D_{2})) + O(e^{−c_{1}\sqrt{log(R/R_{2})}} log^{8} R).  (8.2)

Now, summing over a_{3} using Lemma 2.1, we have

E_{g}(D(D_{1})) = ^{∑′} ; {D(D_{1}) \atop b_{12}b_{13}a_{123}≤R_{1}} ; R_{2}<b_{12}b_{23}a_{123}≤R ; b_{13}b_{23}a_{123}≤R_{3} g_{R}(d_{1}, d_{2}, d_{3}) + ^{∑′} ; {D(D_{1}) \atop b_{12}b_{13}a_{123}≤R_{1}} ; R_{2}<b_{12}b_{23}a_{123}≤R ; R_{3}<b_{13}b_{23}a_{123}≤R g_{R}(d_{1}, d_{2}, d_{3})

= ^{∑′} ; {D(a_{2}D_{3}) \atop b_{12}b_{13}a_{123}≤R_{1}} ; R_{2}<b_{12}b_{23}a_{123}≤R ; b_{13}b_{23}a_{123}≤R_{3} h_{R}(d_{1}, d_{2}, d_{3}) + O(e^{−c_{1}\sqrt{log(R/R_{3})}} log^{6} R)

+ ^{∑′} ; {D(D_{1}) \atop b_{12}b_{13}a_{123}≤R_{1}} ; R_{2}<b_{12}b_{23}a_{123}≤R ; R_{3}<b_{13}b_{23}a_{123}≤R g_{R}(d_{1}, d_{2}, d_{3}).  (8.3)

The first sum above is the same as E_{h}(D(D_{2})) with the appropriate relabeling of variables, and the estimate we now obtain applies to both expressions. We see in this sum that a_{2} ≤ \frac{R}{b_{12}b_{23}a_{123}} ≤ \frac{R}{R_{2}} , and hence the sum is

≪ log(R/R_{2}) ∑_{b_{12}b_{13}a_{123}|k} ∑_{\frac{R_{2}}{b_{12}a_{123}} <b_{23}≤ \frac{R}{b_{12}a_{123}}} \frac{μ^{2}(D_{3})}{ϕ(D_{3})} ∑_{\begin{matrix}a_{2}≤ \frac{R}{R_{2}} \\ (a_{2},D_{3})=1 \end{matrix}} \frac{μ^{2}(a_{2})}{ϕ(a_{2})}𝔖_{2}(a_{2}D_{3})

≪ log^{2}(R/R_{2}) log log R ∑_{b_{12}b_{13}a_{123}|k} ∑_{\frac{R_{2}}{b_{12}a_{123}} <b_{23}≤ \frac{R}{b_{12}a_{123}}} \frac{μ^{2}(D_{3})}{ϕ(D_{3})}

≪ log^{3}(R/R_{2}) log log R (∑_{b|k} \frac{μ^{2}(b)}{ϕ(b)})^{3}

≪ log^{3}(R/R_{2}) log log R(\frac{k}{ϕ(k)})^{3},

by Lemma 2.4, and hence, since \frac{k}{ϕ(k)} ≪ log log 3k,

E_{h}(D(D_{2})) ≪ log^{3}(R/R_{2})(log log R)^{4}.  (8.4)

Similarly, for the second sum in (8.3) both a_{2} ≤ \frac{R}{R_{2}} and a_{3} ≤ \frac{R}{R_{2}} , so that the sum is

≪ log^{5}(R/R_{2})(log log 3k)^{3}

and hence

E_{g}(D(D_{1})) ≪ log^{5}(R/R_{2})(log log R)^{3} + e^{−c_{1}\sqrt{log(R/R_{2})}} log^{6} R.  (8.5)

We take

R_{2} = R_{3} = Re^{−c_{2}(log log R)^{2}}  (8.6)

where c_{2} is a sufficiently large constant, and conclude by (8.2), (8.4), and (8.5) that, for |k| ≤ R^{\frac{1}{2} −ϵ},

T_{3}(k) = W_{3}(k) + O((log log R)^{13}),  (8.7)

where

W_{3}(k) = − ^{∑′} ; {b_{12}b_{23}a_{123}≤R_{2} \atop b_{13}b_{23}a_{123}≤R_{2}} ; b_{12}b_{13}a_{123}|k \frac{μ^{2}(D_{3})μ(a_{123})μ((D_{3}, 2))}{ϕ(D_{3})}𝔖_{2}(2D_{3})𝔖_{3}(2D_{3}),  (8.8)

and as before D_{3} = b_{12}b_{13}b_{23}a_{123}. Since b_{23} is the only variable not constrained by the divisibility condition, we have on letting

R_{4} = \frac{R_{2}}{a_{123}} min(\frac{1}{b_{12}} , \frac{1}{b_{13}} ),  (8.9)

and E = b_{12}b_{13}a_{123}, that

W_{3}(k) = − \begin{matrix}∑ & ′ \\ E|k \end{matrix} \frac{μ^{2}(E)}{ϕ(E)}μ(a_{123}) ∑_{{b_{23}≤R_{4} \atop (b_{23},E)=1}} \frac{μ^{2}(b_{23})}{ϕ(b_{23})}μ((b_{23}E, 2))𝔖_{2}(2b_{23}E)𝔖_{3}(2b_{23}E).

We break the inner sum into two subsums according to whether b_{23} is even or odd, the former case forcing (E, 2) = 1. We thus obtain, on taking b_{23} = 2b in the first subsum and applying (2.4)

W_{3}(k) = ^{∑′} ; {E|k \atop (E,2)=1} \frac{μ^{2}(E)𝔖_{2}(2E)}{ϕ(E)}μ(a_{123}) ∑_{{b≤ \frac{R_{4}}{2} \atop (b,2E)=1}} \frac{μ^{2}(b)}{ϕ_{2}(b)}𝔖_{3}(2bE)

− \begin{matrix}∑ & ′ \\ E|k \end{matrix} \frac{μ^{2}(E)𝔖_{2}(2E)}{ϕ(E)}μ((E, 2))μ(a_{123}) ∑_{{b_{23}≤R_{4} \atop (b_{23},2E)=1}} \frac{μ^{2}(b_{23})}{ϕ_{2}(b_{23})}𝔖_{3}(2b_{23}E).

The inner sums in both sums above are by Lemma 2.4 and the estimate (2.19)

= log R_{4} + O(log log 3k) + O(\begin{matrix}exp & (\frac{c\sqrt{log k}}{log log 3k}) \\ √ & \overline{R_{4}} \end{matrix}).

Substituting we now see that the main term from the first sum is canceled by the part of the main term in the second sum when (E, 2) = 1, and hence we obtain

W_{3}(k)

= \begin{matrix}∑ & ′ \\ E|k \end{matrix} \frac{μ^{2}(E)𝔖_{2}(2E)}{ϕ(E)}(μ(a_{123})[2|E] log R_{4} + +O(log log 3k) + O(\begin{matrix}exp & (\frac{c\sqrt{log k}}{log log 3k}) \\ √ & \overline{R_{4}} \end{matrix}))

= log R_{2} ^{∑′} ; \begin{matrix}E|k \\ 2|E \end{matrix} \frac{μ^{2}(E)𝔖_{2}(2E)}{ϕ(E)}μ(a_{123})

+ O ( \begin{matrix}∑ & ′ \\ E|k \end{matrix} \frac{μ^{2}(E)𝔖_{2}(2E)}{ϕ(E)}( log E + log log 3k + \begin{matrix}exp & (\frac{c\sqrt{log k}}{log log 3k}) \\ √ & \overline{\frac{R_{2}}{E}} \end{matrix} )

= Y_{3}(k) log R_{2} + O (( ∑_{b|k} \frac{μ^{2}(b) log b}{ϕ(b)})^{3} log log 3k)

+ O (\begin{matrix}exp & (\frac{c\sqrt{log k}}{log log 3k}) \\ √ & \overline{R_{2}} \end{matrix}( ∑_{b|k} \frac{μ^{2}(b)\sqrt{b}}{ϕ(b)})^{3}) ,

where we used the estimate 𝔖_{2}(k) ≪ log log 3k in the last two error terms. By Lemma 5 of [11], the sum in the first error term is

= \frac{kh_{1}(k)}{ϕ(k)} ≪ (log log 3k)^{2}

where h_{1}(k) is given by (2.17). The sum in the second error term is

≪ exp (c ∑_{n<log k} \frac{μ^{2}(n)\sqrt{n}}{ϕ(n)}) ≪ e^{c\sqrt{log k}}

and hence we conclude that

W_{3}(k) = Y_{3}(k) log R_{2} + O((log log R)^{7}).  (8.10)

We complete the evaluation of W_{3}(k) by proving

Y_{3}(k) = 𝔖_{2}(k).  (8.11)

We note first that if 2 |̸ k then the sum defining Y_{3}(k) is empty and therefore Y_{3}(k) = 0, in agreement with 𝔖_{2}(k). Therefore by (7.17)

Y_{3}(k) = [2|k] ∑_{\begin{matrix}E|k \\ 2|E \end{matrix}} \frac{μ^{2}(E)𝔖_{2}(2E)}{ϕ(E)}

= 2C_{2}[2|k] ∑_{\begin{matrix}2E′|k \\ (E′,2)=1 \end{matrix}} \frac{μ^{2}(E′)}{ϕ_{2}(E′)}

= 2C_{2}[2|k]H_{2}(k) = 𝔖_{2}(k),

which proves (8.11).

9. Evaluation of S_{3}(0): Main Term

We now consider k_{1} = k_{2} = k_{3} = 0. On applying equations (6.12), (6.13), and (6.14) and taking

S = R_{1} = R_{2} = R_{3}

we have that

T_{3}(0) = W_{3}(0) + O(e^{−c_{1}\sqrt{log(R/S)}} log^{8} R) + E_{f}(D) + E_{g}(D(D_{1})) + E_{h}(D(D_{2})), (9.1)

where we relabel variables for simplicity and have

W_{3}(0) = − ^{∑′} ; {uvy≤S \atop uwy≤S} ; vwy≤S \frac{μ(y)μ^{2}(D)μ((D, 2))}{ϕ(D)}𝔖_{2}(2D)𝔖_{3}(2D),  (9.2)

and D = uvwy. We will prove in this section that

W_{3}(0) = \frac{3}{4} log^{2} S + O(log S).  (9.3)

In the next section we will prove that E_{f}(D), E_{g}(D(D_{1})), and E_{h}(D(D_{2})) all satisfy the bound

≪ log^{9}(\frac{R}{S}) log R  (9.4)

from which we conclude from (9.1) and (9.3) on taking

S = Re^{−c_{2}(log log R)^{2}}

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 3 (2003), #A05 46

that

T_{3}(0) = \frac{3}{4} log^{2} R + O(log R(log log R)^{18})  (9.5)

and therefore by (6.7) we obtain (6.3).

The first step in evaluating W_{3}(0) is to sum over u in (9.2) by separating into sums according to whether u is even or odd, and apply Lemma 2.4. We let z = vwy, and have

∑_{{u≤min( \frac{S}{vy} , \frac{S}{wy}) \atop (u,z)=1}} \frac{μ^{2}(u)}{ϕ(u)}μ((uz, 2))𝔖_{2}(2uz)𝔖_{3}(2uz)

= 2C_{2}H_{2}(2z) ∑_{{u≤ \frac{S}{z} min(v,w) \atop (u,z)=1}} \frac{μ^{2}(u)}{ϕ(u)}μ((uz, 2))H_{2}(2u)𝔖_{3}(2uz)

= 2C_{2}H_{2}(2z)( − [(z, 2) = 1] ∑_{{2u′≤ \frac{S}{z} min(v,w) \atop (u′,2z)=1}} \frac{μ^{2}(u′)}{ϕ_{2}(u′)}𝔖_{3}(2u′z)

+ μ((z, 2)) ∑_{{u≤ \frac{S}{z} min(v,w) \atop (u,2z)=1}} \frac{μ^{2}(u)}{ϕ_{2}(u)}𝔖_{3}(2uz).)

= 2C_{2}H_{2}(2z)( − [(z, 2) = 2]( log (\frac{S(z, 3)}{3z} min(v, w)) + D_{3}

+ h_{3}(6z)) + [(z, 2) = 1] log 2 + O(\frac{m(6z)}{\sqrt{\frac{S}{z} min(v, w)}})).

Substituting this result into (9.2) we obtain

W_{3}(0) =2C_{2} ^{∑′} ; {z≤S \atop 2|z} \frac{μ^{2}(z)μ(y)}{ϕ(z)}H_{2}(2z)( log (\frac{S(z, 3)}{3z} min(v, w)) + D_{3} + h_{3}(6z))

− 2C_{2} log 2 ^{∑′} ; {z≤S \atop (z,2)=1} \frac{μ^{2}(z)μ(y)}{ϕ(z)}H_{2}(2z) + O( \begin{matrix}∑ & ′ \\ z≤S \end{matrix} \frac{μ^{2}(z)m(6z)}{ϕ(z)\sqrt{\frac{S}{z} min(v, w)}}H_{2}(2z)).

(9.6)

Except for the factor of log min(v, w), the sums above are of the form considered in (7.17).

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 3 (2003), #A05 47

Hence we have

2C_{2} ^{∑′} ; {z≤S \atop 2|z} \frac{μ^{2}(z)μ(y)}{ϕ(z)}H_{2}(2z) log \frac{S}{z} = 2C_{2} ∑_{{z≤S \atop 2|z}} \frac{μ^{2}(z)}{ϕ(z)}H_{2}(2z) log \frac{S}{z}
= 2C_{2} ∑_{{2z′≤S \atop (z′,2)=1}} \frac{μ^{2}(z′)}{ϕ_{2}(z′)} log \frac{S}{2z′}
= \frac{1}{2} log^{2} S + O(log S),  (9.7)

where we used (2.21). Similarly we have, by Lemma 2.2

2C_{2} ^{∑′} ; {z≤S \atop 2|z} \frac{μ^{2}(z)μ(y)}{ϕ(z)}H_{2}(2z) = log S + O(1).  (9.8)

We also see that the condition 2|z in (9.8) may be replaced by (z, 2) = 1 and (9.8) will still hold. Similarly it is clear that

2C_{2} ^{∑′} ; {z≤S \atop 2|z} \frac{μ^{2}(z)μ(y)}{ϕ(z)}H_{2}(2z) log((z, 3)) ≪ log S,  (9.9)

and also that

2C_{2} ^{∑′} ; {z≤S \atop 2|z} \frac{μ^{2}(z)μ(y)}{ϕ(z)}H_{2}(2z)h_{3}(6z)

≪ ∑_{{z≤S \atop 2|z}} \frac{μ^{2}(z)}{ϕ(z)}H_{2}(2z)h_{3}(6z)

≪ ∑_{p≤S} \frac{log p}{p} ∑_{{z≤S \atop p|z}} \frac{μ^{2}(z)}{ϕ(z)}H_{2}(2z)

≪ ∑_{3≤p≤S} \frac{log p}{pϕ_{2}(p)} ∑_{{m≤ \frac{S}{p} \atop (m,p)=1}} \frac{μ^{2}(m)}{ϕ(m)}H_{2}(2m)

≪ log S.

(9.10)

We conclude that

W_{3}(0) =\frac{1}{2} log^{2} S + O(log S) + 2C_{2} ^{∑′} ; {z≤S \atop 2|z} \frac{μ^{2}(z)μ(y)}{ϕ(z)}H_{2}(2z) log(min(v, w))

+ O( \begin{matrix}∑ & ′ \\ z≤S \end{matrix} \frac{μ^{2}(z)m(6z)}{ϕ(z)\sqrt{\frac{S}{z} min(v, w)}}H_{2}(2z)).

(9.11)

We now evaluate the first sum in (9.11), and show that

2C_{2} ^{∑′} ; {z≤S \atop 2|z} \frac{μ^{2}(z)μ(y)}{ϕ(z)}H_{2}(2z) log(min(v, w)) = \frac{1}{4} log^{2} S + O(log S).  (9.12)

By the symmetry in the variables v and w we have that the sum above is

= 4C_{2} ^{∑′} ; {vwy≤S \atop 2|vwy} ; v<w \frac{μ^{2}(v)μ^{2}(w)μ(y)}{ϕ(vwy)}H_{2}(2vwy) log v,  (9.13)

since the condition (v, w) = 1 implies that the only term with v = w is when v = w = 1, and this term is zero. We will sum over w and apply Lemma 2.2 according to the parity of w, which gives

∑_{{v<w≤ \frac{S}{vy} \atop 2|vwy} ; (w,vy)=1} \frac{μ^{2}(w)}{ϕ(w)}H_{2}(w) = [(vy, 2) = 1] ∑_{{v<2w′≤ \frac{S}{vy} \atop (w′,2vy)=1}} \frac{μ^{2}(w′)}{ϕ_{2}(w′)} + [2|vy] ∑_{{v<w≤ \frac{S}{vy} \atop (w,2vy)=1}} \frac{μ^{2}(w)}{ϕ_{2}(w)}

= ([(vy, 2) = 1] + [2|vy]) (\frac{1}{𝔖_{2}(2vy)} log \frac{S}{v^{2}y} ) + O(\frac{m(2vy)}{\sqrt{v}})
= \frac{1}{𝔖_{2}(2vy)} log \frac{S}{v^{2}y} + O(\frac{m(2vy)}{\sqrt{v}}).

Substituting this result into (9.13) we find that this sum is

=4C_{2} ∑_{v≤\sqrt{S}} \frac{μ^{2}(v)}{ϕ(v)}H_{2}(v) log v ∑_{{y≤ \frac{S}{v^{2}} \atop (y,v)=1}} \frac{μ(y)}{ϕ(y)}H_{2}(y) (\frac{1}{𝔖_{2}(2vy)} log \frac{S}{v^{2}y} + O(\frac{m(2vy)}{\sqrt{v}}))

=2 ∑_{v≤\sqrt{S}} \frac{μ^{2}(v)}{ϕ(v)} log v ∑_{{y≤ \frac{S}{v^{2}} \atop (y,v)=1}} \frac{μ(y)}{ϕ(y)} log \frac{S}{v^{2}y}

+ O( ∑_{v≤\sqrt{S}} \frac{μ^{2}(v)H_{2}(v)}{\sqrt{v}ϕ(v)}m(v) log v ∑_{y≤ \frac{S}{v^{2}}} \frac{μ^{2}(y)H_{2}(y)}{ϕ(y)}m(y)).

The inner sum in the error term here is

≪ ∑_{y≤S} \frac{μ^{2}(y)H_{2}(y)}{ϕ(y)} ∑_{d|y} \frac{μ^{2}(d)}{\sqrt{d}}

= ∑_{d≤S} \frac{μ^{2}(d)H_{2}(d)}{\sqrt{d}ϕ(d)} ∑_{\begin{matrix}m≤S/d \\ (m,d)=1 \end{matrix}} \frac{μ^{2}(m)H_{2}(m)}{ϕ(m)}

≪ log S,

and by (2.19) the sum over v in the error term converges; hence the error term is O(log S). Thus by Lemma 2.1 and partial summation in Lemma 2.4 the above expression is

= 2 ∑_{v≤\sqrt{S}} \frac{μ^{2}(v)}{ϕ(v)}𝔖_{2}(v) log v + O( ∑_{v≤\sqrt{S}} (\frac{μ^{2}(v)}{ϕ(v)} log v) e^{−c_{1}\sqrt{log( \frac{S}{v^{2}} )}}) + O(log S)
= log^{2} \sqrt{S} + O(log S),

which proves (9.12).

It remains to deal with the error term in (9.11). By symmetry we may assume that v ≤ w, and thus the error term is

≪ \frac{1}{\sqrt{S}} ^{∑′} ; {vwy≤S \atop (vwy,2)=1} \frac{μ^{2}(vwy)\sqrt{wy}}{ϕ_{2}(vwy)} m(vwy)

≪ \frac{1}{\sqrt{S}} ∑_{w≤S} \frac{μ^{2}(w)\sqrt{w}}{ϕ_{2}(w)}m(w) ^{∑′} ; {v≤ \frac{S}{w} \atop (v,2)=1} \frac{μ^{2}(v)}{ϕ_{2}(v)}m(v) ^{∑′} ; {y≤ \frac{S}{vw} \atop (y,2)=1} \frac{μ^{2}(y)\sqrt{y}}{ϕ_{2}(y)} m(y).

The inner sum over y is

≪ ∑_{{y≤ \frac{S}{vw} \atop (y,2)=1}} \frac{μ^{2}(y)\sqrt{y}}{ϕ_{2}(y)} ∑_{d|y} \frac{μ^{2}(d)}{\sqrt{d}}

≪ ∑_{{d≤ \frac{S}{vw} \atop (d,2)=1}} \frac{μ^{2}(d)}{ϕ_{2}(d)} ∑_{(m,2)=1^{m≤ \frac{S}{dvw}}} \frac{μ^{2}(m)\sqrt{m}}{ϕ_{2}(m)}

≪ \sqrt{\frac{S}{vw}} ∑_{{d≤ \frac{S}{vw} \atop (d,2)=1}} \frac{μ^{2}(d)}{ϕ_{2}(d)\sqrt{d}}

≪ \sqrt{\frac{S}{vw}}.

Substituting we see the sum over v now converges, and on summing over w and treating m(w) as in the previous estimate we see the error is O(log S). This completes the proof of (9.3).

10. Evaluation of S_{3}(0): Error Terms

We now treat the error terms E_{f}(D), E_{g}(D(D_{1})), and E_{h}(D(D_{2})). We proceed as we did before in (8.3); in E_{f}(D) we break the sum into two sums according to whether b_{12}b_{23}a_{123} ≤ R_{1} or R_{1} < b_{12}b_{23}a_{123} ≤ R, in the former sum we sum over a_{2} using Lemma 2.1 and obtain a sum of the same form as E_{g}(D(D_{1})) and an error term

≪ e^{−c_{1}\sqrt{log(R/R_{1})}} log^{8} R.  (10.1)

In the second sum where R_{1} < b_{12}b_{23}a_{123} we have a_{2} ≤ \frac{R}{R_{1}} and we do not sum over a_{2}. We continue this process with regard to a_{3}, and likewise deal with the error term E_{g}(D(D_{1})). The result of this process is that we are left with errors bounded by (10.1) and three types of sums of the forms

E_{1} = ∑_{a≤R/R_{1}} \frac{μ(a)}{ϕ(a)} ^{∑′} ; {uvy≤R_{1} \atop uwy≤R_{1}} ; R_{1}<vwy≤R/a \frac{μ(y)μ^{2}(D)}{ϕ(D)}𝔖_{2}(aD) log \frac{R}{avwy} ,  (10.2)

E_{2} = \begin{matrix}∑ & ′ \\ a,b≤R/R_{1} \end{matrix} \frac{μ(ab)}{ϕ(ab)} ^{∑′} ; {uvy≤R_{1} \atop R_{1}<uwy≤R/a} ; R_{1}<vwy≤R/b \frac{μ(y)μ^{2}(D)}{ϕ(D)} log \frac{R}{auwy} log \frac{R}{bvwy} ,  (10.3)

and

E_{3} = \begin{matrix}∑ & ′ \\ a,b,c≤R/R_{1} \end{matrix} \frac{μ(abc)}{abc} ^{∑′} ; {R_{1}<uvy≤R/a \atop R_{1}<uwy≤R/b} ; R_{1}<vwy≤R/c \frac{μ(y)μ^{2}(D)}{D} log \frac{R}{auvy} log \frac{R}{buwy} log \frac{R}{cvwy} ,  (10.4)

where D = uvwy.

We can handle E_{3} immediately. Estimating trivially, we have

E_{3} ≪ (log R/R_{1})^{6} ∑_{{R_{1}<uvy≤R \atop R_{1}<uwy≤R} ; R_{1}<vwy≤R} \frac{1}{uvwy} .

The top two inequalities in the summation conditions imply

(\frac{R_{1}}{u} )^{2} < vwy^{2} ≤ (\frac{R}{u})^{2}

and hence

(\frac{R_{1}}{u} )^{2} \frac{1}{vwy} < y ≤ (\frac{R}{u})^{2} \frac{1}{vwy}

Thus the bottom inequality in the summation conditions implies

(\frac{R_{1}}{u} )^{2} \frac{1}{R} < y ≤ (\frac{R}{u})^{2} \frac{1}{R_{1}} ,

and therefore the sum above is

≪ ∑_{u≤R} \frac{1}{u} ∑_{(\frac{R_{1}}{u})^{2} \frac{1}{R} <y≤(\frac{R}{u})^{2} \frac{1}{R_{1}}} \frac{1}{y} ∑_{\frac{R_{1}}{uy} <w≤ \frac{R}{uy}} \frac{1}{w} ∑_{\frac{R_{1}}{uy} <v≤ \frac{R}{uy}} \frac{1}{v}

≪ log R(log R/R_{1})^{3}.

Thus

E_{3} ≪ log R(log R/R_{1})^{9}.  (10.5)

Consider next E_{2}. The trivial estimate used for E_{3} would give the bound ≪ log^{2} R(log R/R_{1})^{6}, and therefore we need to save a factor of log R, which will occur when we sum over y. We first note that the conditions on the summation variables for the sum in (10.3) imply that u, v ≤ w. Next, we extend the summation range uvy ≤ R_{1} to uvy ≤ R, which may be done with an error ≪ log R(log R/R_{1})^{7} in the same way that (10.5) was obtained. Finally, the terms with R_{1} < wy also contribute this same error, since this condition implies with the other summation conditions that u, v ≤ \frac{R}{R_{1}} and \frac{R_{1}}{uy} < w < \frac{R}{uy}, so that only y has a full summation range. Hence we have

E_{2} = \begin{matrix}∑ & ′ \\ a,b≤R/R_{1} \end{matrix} \frac{μ(ab)}{ϕ(ab)} ^{∑′} ; \begin{matrix}u,v≤w \\ wy≤R_{1} \\ R_{1}<uwy≤R/a \\ R_{1}<vwy≤R/b \end{matrix} \frac{μ(y)μ^{2}(D)}{ϕ(D)} log \frac{R}{auwy} log \frac{R}{bvwy} + O( log R(log(R/R_{1}))^{7}).

(10.6)

We now sum over u, which satisfies

\frac{R_{1}}{wy} < u ≤ min(\frac{R}{awy} , w).

If min(\frac{R}{awy}, w) = w then w^{2} ≤ \frac{R}{ay} and there will only be terms when \frac{R_{1}}{y} < w^{2}. We conclude in this case that

\sqrt{\frac{R_{1}}{y}} < w ≤ \sqrt{\frac{R}{ay}} .

Hence, as in the estimate to obtain (10.5), these terms contribute at most ≪ log R(log(R/R_{1}))^{7} since only the variable y runs through a full summation range. We conclude, with z = vwy,

E_{2} = \begin{matrix}∑ & ′ \\ a,b≤R/R_{1} \end{matrix} \frac{μ(ab)}{ϕ(ab)} ^{∑′} ; \begin{matrix}v≤w \\ wy≤R_{1} \\ R_{1}<z≤R/b \end{matrix} \frac{μ(y)μ^{2}(z)}{ϕ(z)} log \frac{R}{bz} ∑_{\begin{matrix}\frac{R_{1}}{wy} <u≤ \frac{R}{awy} \\ (u,abz)=1 \end{matrix}} \frac{μ^{2}(u)}{ϕ(u)} log \frac{R}{auwy}

+ O( log R(log(R/R_{1}))^{7}).

(10.7)

To evaluate the inner sum, we use the relation, for 1 ≤ S ≤ R, p(j)|k,

∑_{\begin{matrix}\frac{R}{S} <d≤R \\ (d,k)=1 \end{matrix}} \frac{μ^{2}(d)}{ϕ_{j}(d)} log \frac{R}{d} = \frac{1}{2𝔖_{j}(k)} log^{2} S + O(\frac{m(k)}{\sqrt{\frac{R}{S}}} log S).  (10.8)

This result follows immediately on writing the sum on the left-hand side above as

= ∑_{\begin{matrix}d≤R \\ (d,k)=1 \end{matrix}} \frac{μ^{2}(d)}{ϕ_{j}(d)} log \frac{R}{d} − ∑_{\begin{matrix}d≤ \frac{R}{S} \\ (d,k)=1 \end{matrix}} \frac{μ^{2}(d)}{ϕ_{j}(d)}( log \frac{R}{Sd} + log S)

and applying (2.21) and Lemma 2.2. Thus we have

∑_{\begin{matrix}\frac{R_{1}}{wy} <u≤ \frac{R}{awy} \\ (u,abz)=1 \end{matrix}} \frac{μ^{2}(u)}{ϕ(u)} log \frac{R}{auwy} = \frac{ϕ(abz)}{2abz} log^{2} \frac{R}{aR_{1}} + O(\frac{m(abz)}{\sqrt{\frac{R_{1}}{wy}}} log \frac{R}{aR_{1}} ).  (10.9)

Substituting this expression into (10.7) we obtain

E_{2} = \frac{1}{2}\begin{matrix}∑ & ′ \\ a,b≤R/R_{1} \end{matrix} \frac{μ(ab)}{ab} log^{2} \frac{R}{aR_{1}} ^{∑′} ; \begin{matrix}v≤w \\ wy≤R_{1} \\ R_{1}<z≤R/b \end{matrix} \frac{μ(y)μ^{2}(z)}{z} log \frac{R}{bz} + O( log R(log(R/R_{1}))^{7}),

(10.10)

once we show that the contribution

≪ \begin{matrix}log & 2 & \frac{R}{R_{1}} \\ √ & \overline{R_{1}} \end{matrix} \begin{matrix}∑ & ′ \\ a,b≤R/R_{1} \end{matrix} \frac{μ^{2}(ab)m(ab)}{ϕ(ab)} ^{∑′} ; \begin{matrix}v≤w \\ wy≤R_{1} \\ R_{1}<z≤R/b \end{matrix} \frac{μ^{2}(z)\sqrt{wy}m(z)}{ϕ(z)}

from the error term in (10.9) is covered by the error term in (10.10). This expression is of the same form as the error term in (9.11) estimated at the end of the last section, except it is over a more restricted summation range. The factors m(ab) and m(z) are handled as in that argument, and make no contribution, so we may ignore them. Hence the expression above is, by Lemma 2.2,

≪ \begin{matrix}log & 4 & \frac{R}{R_{1}} \\ √ & \overline{R_{1}} \end{matrix} ∑_{\begin{matrix}v≤w \\ wy≤R_{1} \\ R_{1}<vwy≤R \end{matrix}} \frac{μ^{2}(vwy)\sqrt{wy}}{ϕ(vwy)}

≪ \begin{matrix}log & 4 & \frac{R}{R_{1}} \\ √ & \overline{R_{1}} \end{matrix} ∑_{w≤R_{1}} \frac{\sqrt{w}}{ϕ(w)} ∑_{y≤ \frac{R_{1}}{w}} \frac{\sqrt{y}}{ϕ(y)} ∑_{\frac{R_{1}}{wy} <v≤ \frac{R}{wy}} \frac{μ^{2}(v)}{ϕ(v)}

≪ log R_{1} log^{5} \frac{R}{R_{1}} ,

which is acceptable. Thus we have established (10.10).

We now treat the sum in (10.10) and show it is also bounded by the error term, from which we conclude that

E_{2} ≪ log R(log R/R_{1})^{7}.  (10.11)

To see this, consider the sum over y in equation (10.10)

∑_{\begin{matrix}\frac{R_{1}}{vw} <y≤min( \frac{R_{1}}{w} , \frac{R}{bvw}) \\ (y,abvw)=1 \end{matrix}} \frac{μ(y)}{y} log \frac{R}{bvwy} .

For the terms with min (\frac{R_{1}}{w} , \frac{R}{bvw}) = \frac{R_{1}}{w}, we have v ≤ \frac{R}{bR_{1}} , and the sum in (10.10) is

≪ log^{5} \frac{R}{R_{1}} ∑_{v≤ \frac{R}{R_{1}}} \frac{μ^{2}(v)}{v} ∑_{w≤R_{1}} \frac{μ^{2}(w)}{w} ∑_{\frac{R_{1}}{vw} <y≤ \frac{R_{1}}{w}} \frac{μ^{2}(y)}{y}

≪ log^{5} \frac{R}{R_{1}} ∑_{v≤ \frac{R}{R_{1}}} \frac{μ^{2}(v)}{v} ∑_{w≤R_{1}} \frac{μ^{2}(w)}{w} ([vw ≤ R_{1}] log v + [vw > R_{1}] log \frac{R_{1}}{w} )

≪ log R log^{5} \frac{R}{R_{1}} ( ∑_{v≤ \frac{R}{R_{1}}} \frac{μ^{2}(v) log v}{v} + ∑_{v≤ \frac{R}{R_{1}}} \frac{μ^{2}(v)}{v} ∑_{\frac{R_{1}}{v} <w≤R_{1}} \frac{μ^{2}(w)}{w})

≪ log R log^{7} \frac{R}{R_{1}} ,

which is acceptable. For the remaining terms when min (\frac{R_{1}}{w} , \frac{R}{bvw}) = \frac{R}{bvw}, we have \frac{R}{bR_{1}} < v, and by Lemma 2.1 with the error term estimate (2.14) the sum over y is

= ∑_{\begin{matrix}y≤ \frac{R}{bvw} \\ (y,abvw)=1 \end{matrix}} \frac{μ(y)}{y} log \frac{R}{bvwy} − [vw ≤ R_{1}] ∑_{\begin{matrix}y≤ \frac{R_{1}}{vw} \\ (y,abvw)=1 \end{matrix}} \frac{μ(y)}{y}( log \frac{R_{1}}{vwy} + log \frac{R}{bR_{1}} )

= (1 − [vw ≤ R_{1}])𝔖_{1}(abvw) + O(m(abvw)e^{−c_{1}\sqrt{log( \frac{R}{bvw})}})

+ [vw ≤ R_{1}]O(m(abvw)e^{−c_{1}\sqrt{log( \frac{R_{1}}{vw})}} log \frac{R}{R_{1}} ).

Hence the sum in (10.10) is in this case

≪ log^{5}(R/R_{1}) ∑_{vw≤R_{1}} \frac{m(vw)}{vw}e^{−c_{1}\sqrt{log \frac{R_{1}}{vw}}}

+ log^{4}(R/R_{1}) ∑_{R_{1}<vw≤R} \frac{1}{vw}(𝔖_{1}(vw) + m(vw))

≪ log R(log(R/R_{1}))^{5},

where as before the factors of m(vw) and 𝔖(vw) make no contribution to the error when they are summed. This finishes the proof of (10.11).

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 3 (2003), #A05 54

Finally consider E_{1}. The inner sum in (10.2) is, with E = uwy,

∑′ ; \begin{matrix}uvy≤R_{1} \\ uwy≤R_{1} \\ R_{1}<vwy≤R/a \\ (D,a)=1 \end{matrix} \frac{μ(y)μ^{2}(D)}{ϕ(D)}𝔖_{2}(aD) log \frac{R}{avwy} = 2C_{2} ^{∑′} ; \begin{matrix}E≤R_{1} \\ (E,a)=1 \end{matrix} \frac{μ(y)μ^{2}(E)}{ϕ(E)}H_{2}(aE)S_{R}(E),

where

S_{R}(E) = ∑_{\begin{matrix}\frac{R_{1}}{wy} <v≤min( \frac{R}{awy} , \frac{R_{1}}{uy}) \\ (v,aE)=1 \end{matrix}} χ(aE, v)\frac{μ^{2}(v)H_{2}(v)}{ϕ(v)} log \frac{R}{avwy}

and

χ(aE, v) = [2|v][(aE, 2) = 1] + [(v, 2) = 1][2|aE].

We apply (10.8) and Lemma 2.2 to evaluate S_{R}(E). When min(\frac{R}{awy}, \frac{R_{1}}{uy}) = \frac{R}{awy} then in (10.8) S = \frac{R}{aR_{1}} , and

S_{R}(E) = \frac{1}{2𝔖_{2}(2aE)} log^{2} \frac{R}{aR_{1}} + O(\frac{m(2aE) log \frac{R}{aR_{1}}}{\sqrt{\frac{R_{1}}{wy}}});

while if min(\frac{R}{awy}, \frac{R_{1}}{uy}) = \frac{R_{1}}{uy} then 1 < S = \frac{w}{u} ≤ \frac{R}{aR_{1}} , whence u < w ≤ \frac{R}{aR_{1}} u, and thus we obtain

S_{R}(E) = \frac{1}{2𝔖_{2}(2aE)} log \frac{w}{u} log ((\frac{R}{aR_{1}} )^{2} \frac{u}{w}) + O(\frac{m(2aE) log \frac{R}{aR_{1}}}{\sqrt{\frac{R_{1}}{wy}}}).

On substituting, the inner sum in (10.2) becomes

=\frac{1}{2} log^{2} \frac{R}{aR_{1}} ^{∑′} ; \begin{matrix}uw≤R_{1} \\ \frac{R}{aR_{1}} ≤ \frac{w}{u} \\ (uw,a)=1 \end{matrix} \frac{μ^{2}(uw)}{ϕ(uw)} ∑_{\begin{matrix}y≤ \frac{R_{1}}{uw} \\ (y,auw)=1 \end{matrix}} \frac{μ(y)}{ϕ(y)}

+ \frac{1}{2} ^{∑′} ; \begin{matrix}uw≤R_{1} \\ 1< \frac{w}{u} < \frac{R}{aR_{1}} \\ (uw,a)=1 \end{matrix} \frac{μ^{2}(uw)}{ϕ(uw)} log \frac{w}{u} log ((\frac{R}{aR_{1}} )^{2} \frac{u}{w}) ∑_{\begin{matrix}y≤ \frac{R_{1}}{uw} \\ (y,auw)=1 \end{matrix}} \frac{μ(y)}{ϕ(y)}

+ O( ^{∑′} ; \begin{matrix}uw≤R_{1} \\ (uw,a)=1 \end{matrix} \frac{μ^{2}(uw)}{ϕ(uw)}( ∑_{\begin{matrix}y≤ \frac{R_{1}}{uw} \\ (y,auw)=1 \end{matrix}} \frac{μ^{2}(y)H_{2}(2auwy)}{ϕ^{(}y)} \frac{m(2auwy) log \frac{R}{aR_{1}}}{\sqrt{\frac{R_{1}}{wy}}} )).

As before, in estimating the contribution of the error term above to (10.2) the factor m(2auwy) may be ignored, and therefore this contribution is

≪ \begin{matrix}log & 2 & \frac{R}{R_{1}} \\ √ & \overline{R_{1}} \end{matrix} ∑_{\begin{matrix}uwy≤R_{1} \\ (uwy,2)=1 \end{matrix}} \frac{μ^{2}(uwy)\sqrt{wy}}{ϕ_{2}(uwy)}

≪ \begin{matrix}log & 2 & \frac{R}{R_{1}} \\ √ & \overline{R_{1}} \end{matrix} ∑_{\begin{matrix}u≤R_{1} \\ (u,2)=1 \end{matrix}} \frac{μ^{2}(u)}{ϕ_{2}(u)} ∑_{\begin{matrix}w≤ \frac{R_{1}}{u} \\ (w,2)=1 \end{matrix}} \frac{μ^{2}(w)\sqrt{w}}{ϕ_{2}(w)} ∑_{\begin{matrix}y≤ \frac{R_{1}}{uw} \\ (y,2)=1 \end{matrix}} \frac{μ^{2}(y)\sqrt{y}}{ϕ_{2}(y)}

≪ log^{2} \frac{R}{R_{1}} ∑_{\begin{matrix}u≤R_{1} \\ (u,2)=1 \end{matrix}} \frac{μ^{2}(u)}{\sqrt{u}ϕ_{2}(u)} ∑_{\begin{matrix}w≤ \frac{R_{1}}{u} \\ (w,2)=1 \end{matrix}} \frac{μ^{2}(w)}{ϕ_{2}(w)}

≪ log R_{1} log^{2} \frac{R}{R_{1}} .

Next, for the main terms above the sum over y is ≪ m(auw)e^{−c_{2}\sqrt{log \frac{R_{1}}{uw}}} by Lemma 2.1 with the error term in (2.14), and hence both sums contribute to (10.2)

≪ log^{3} \frac{R}{R_{1}} ∑_{u≤R_{1}} \frac{μ^{2}(u)m(u)}{ϕ(u)} ∑_{w≤R_{1}/u} \frac{μ^{2}(w)m(w)}{ϕ(w)}e^{−c_{1}\sqrt{log \frac{R_{1}}{uw}}}

≪ log R log^{3} \frac{R}{R_{1}} .

We conclude

E_{1} ≪ log R(log R/R_{1})^{3}.  (10.12)

By (10.1),(10.5),(10.11), and (10.12) we have proved (9.4) and thus completed the proof of (5.3).

11. Mixed Triple Correlations

The case k = 2 of Theorem 1.4 has already been handled by (1.5) and (5.7). In this section we evaluate W_{R}(k) from Section 4 in the case k = 3. This will not only prove Theorem 1.4 but will also give an alternative and simpler proof of the second two parts of Theorem 6.1.

We let k = (k_{1}, k_{2}, 0) and

W_{R}(k) = ∑_{\begin{matrix}d_{1},d_{2}≤R \\ (d_{1},k_{1})=1, (d_{2},k_{2})=1 \\ (d_{1},d_{2})|k_{2}−k_{1} \end{matrix}} \frac{μ(d_{1})μ(d_{2})}{ϕ([d_{1}, d_{2}])} log \frac{R}{d_{1}} log \frac{R}{d_{2}} .  (11.1)

The results we obtain are contained in the following theorem. Recall H_{j}(m) is defined in (2.3), h_{j}(m) is defined in (2.17), and H_{j}(m), h_{j}(m) ≪_{j} log log 3m.

Theorem 11.1 If k = (k, k, 0), k ≠ 0, and log |k| ≪ log R, we have

W_{R}(k) = 𝔖(k) log R + O(H_{2}(k)h_{3}(6k)),  (11.2)

and if k = (k_{1}, k_{2}, 0) and k_{1} ≠ k_{2} ≠ 0, letting Δ = k_{1}k_{2}(k_{2} −k_{1}), and assuming Δ < R/2, we have

W_{R}(k) = 𝔖(k) + O(\frac{k_{1}}{ϕ(k_{1})}H_{2}(Δ)e^{−c_{1}\sqrt{log R/2Δ}}).  (11.3)

We decompose into relatively prime variables by letting d_{1} = a_{1}b_{12} and d_{2} = a_{2}b_{12} where (d_{1}, d_{2}) = b_{12} and thus a_{1}, a_{2}, and b_{12} are pairwise relatively prime. Then we have

W_{R}(k) = ^{∑′} ; \begin{matrix}a_{1}b_{12}≤R \\ a_{2}b_{12}≤R \\ (a_{1}b_{12},k_{1})=1, (a_{2}b_{12},k_{2})=1 \\ b_{12}|k_{2}−k_{1} \end{matrix} \frac{μ(a_{1})μ(a_{2})μ^{2}(b_{12})}{ϕ(a_{1}a_{2}b_{12})} log \frac{R}{a_{1}b_{12}} log \frac{R}{a_{2}b_{12}} .  (11.4)

We first sum over a_{1} and apply Lemma 2.1 to see that

∑_{\begin{matrix}a_{1}≤R/b_{12} \\ (a_{1},a_{2}b_{12}k_{1})=1 \end{matrix}} \frac{μ(a_{1})}{ϕ(a_{1})} log \frac{R}{a_{1}b_{12}} = 𝔖_{2}(a_{2}b_{12}k_{1}) + r_{1}(\frac{R}{b_{12}} , a_{2}b_{12}k_{1}),  (11.5)

and hence we have

\begin{aligned}W_{R}(k) & = ^{∑′} ; \begin{matrix}a_{2}b_{12}≤R \\ (b_{12},k_{1})=1, (a_{2}b_{12},k_{2})=1 \\ b_{12}|k_{2}−k_{1} \end{matrix} \frac{μ(a_{2})μ^{2}(b_{12})𝔖_{2}(a_{2}b_{12}k_{1})}{ϕ(a_{2}b_{12})} log \frac{R}{a_{2}b_{12}} + E_{1}(R) \\ & = V_{R}(k) + E_{1}(R), \end{aligned}  (11.6)

where

E_{1}(R) = ^{∑′} ; \begin{matrix}a_{2}b_{12}≤R \\ (b_{12},k_{1})=1, (a_{2}b_{12},k_{2})=1 \\ b_{12}|k_{2}−k_{1} \end{matrix} \frac{μ(a_{2})μ^{2}(b_{12})r_{1}(\frac{R}{b_{12}} , a_{2}b_{12}k_{1})}{ϕ(a_{2}b_{12})} log \frac{R}{a_{2}b_{12}}

≪ ∑_{\begin{matrix}b_{12}≤R \\ b_{12}|k_{2}−k_{1} \end{matrix}} \frac{μ^{2}(b_{12})}{ϕ(b_{12})}e^{−c_{1}\sqrt{log(R/b_{12})}} ∑_{a_{2}≤R/b_{12}} \frac{μ^{2}(a_{2})}{ϕ(a_{2})} log \frac{R}{a_{2}b_{12}}

≪ ∑_{\begin{matrix}b_{12}≤R \\ b_{12}|k_{2}−k_{1} \end{matrix}} \frac{μ^{2}(b_{12})}{ϕ(b_{12})}e^{−c_{2}\sqrt{log(R/b_{12})}}.  (11.7)

We first consider the case when k_{1} = k_{2} = k. Then from (11.7) we see that

E_{1}(R) ≪ 1.  (11.8)

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 3 (2003), #A05 57

By Lemma 2.3 we have

V_{R}(k) = ^{∑′} ; \begin{matrix}a_{2}b_{12}≤R \\ (a_{2}b_{12},k)=1 \end{matrix} \frac{μ(a_{2})μ^{2}(b_{12})𝔖_{2}(a_{2}b_{12}k)}{ϕ(a_{2}b_{12})} log \frac{R}{a_{2}b_{12}}
= ∑_{\begin{matrix}b_{12}≤R \\ (b_{12},k)=1 \end{matrix}} \frac{μ^{2}(b_{12})}{ϕ(b_{12})} ∑_{\begin{matrix}a_{2}≤R/b_{12} \\ (a_{2},b_{12}k)=1 \end{matrix}} \frac{μ(a_{2})𝔖_{2}(a_{2}b_{12}k)}{ϕ(a_{2})} log \frac{R}{a_{2}b_{12}}
= − ∑_{\begin{matrix}b_{12}≤R \\ (b_{12},k)=1 \end{matrix}} \frac{μ^{2}(b_{12})μ((b_{12}k, 2))}{ϕ(b_{12})}𝔖_{2}(2b_{12}k)𝔖_{3}(2b_{12}k)

+ O ( ∑_{b_{12}≤R} \frac{μ^{2}(b_{12})H_{2}(b_{12})}{ϕ(b_{12}) log^{A}(2R/b_{12})})

= Y_{R}(k) + O(1).  (11.9)

To evaluate Y_{R}(k) we divide into even terms and odd terms and apply Lemma 2.4. Thus

V_{R}(k) = [(k, 2) = 1] ∑_{\begin{matrix}2b≤R \\ (b,2k)=1 \end{matrix}} \frac{μ^{2}(b)}{ϕ(b)}𝔖_{2}(2bk)𝔖_{3}(2bk)

−μ((k, 2)) ∑_{\begin{matrix}b_{12}≤R \\ (b_{12},2k)=1 \end{matrix}} \frac{μ^{2}(b_{12})}{ϕ(b_{12})}𝔖_{2}(2b_{12}k)𝔖_{3}(2b_{12}k)

= 2C_{2}H_{2}(k)([(k, 2) = 1] ∑_{\begin{matrix}b≤R/2 \\ (b,2k)=1 \end{matrix}} \frac{μ^{2}(b)}{ϕ_{2}(b)}𝔖_{3}(2bk)

−μ((k, 2)) ∑_{\begin{matrix}b_{12}≤R \\ (b_{12},2k)=1 \end{matrix}} \frac{μ^{2}(b_{12})}{ϕ_{2}(b_{12})}𝔖_{3}(2b_{12}k))

= 2C_{2}H_{2}(k)(([(k, 2) = 1] − μ((k, 2))) log R + O(h_{3}(6k)) + O(\frac{𝔖_{3}(6k)m(k)}{\sqrt{R}})))
= 2C_{2}[2|k]H_{2}(k) log R + O(H_{2}(k)h_{3}(6k))
= 𝔖_{2}(k) log R + O(H_{2}(k)h_{3}(6k)).

On combining these results we have proved the first part of Theorem 11.1.

We now turn to the case that k_{2} ≠ k_{1}. As in Lemma 2.5 we let κ = (k_{1}, k_{2}) and Δ = k_{1}k_{2}(k_{2} −k_{1}). As before let k^{∗} = max(|k_{1}|, |k_{2}|). In this case we see from (11.7) that

E_{1}(R) ≪ H_{1}(k_{2} − k_{1})e^{−c_{2}\sqrt{log(R/2k^{∗})}}.  (11.10)

We now let k_{1} = s_{1}K_{1}, k_{2} = s_{2}K_{2}, where K_{1} and K_{2} are the largest squarefree divisors of k_{1} and k_{2} respectively. Let K_{12} = (K_{1}, K_{2}). Then we have

V_{R}(k) = ^{∑′} ; \begin{matrix}a_{2}b_{12}≤R \\ (b_{12},K_{1})=1, (a_{2}b_{12},K_{2})=1 \\ b_{12}|k_{2}−k_{1} \end{matrix} \frac{μ(a_{2})μ^{2}(b_{12})𝔖_{2}(a_{2}b_{12}K_{1})}{ϕ(a_{2}b_{12})} log \frac{R}{a_{2}b_{12}}

Next let a_{2} = c_{2}d_{2} where c_{2}|K_{1} and (d_{2}, K_{1}) = 1 so that (a_{2}, K_{1}) = c_{2}, from which we see

V_{R}(k) = ^{∑′} ; \begin{matrix}c_{2}d_{2}b_{12}≤R \\ (d_{2}b_{12},K_{1})=1, (c_{2}d_{2}b_{12},K_{2})=1 \\ b_{12}|k_{2}−k_{1}, c_{2}|K_{1} \end{matrix} \frac{μ(c_{2})μ(d_{2})μ^{2}(b_{12})𝔖_{2}(d_{2}b_{12}K_{1})}{ϕ(c_{2}d_{2}b_{12})} log \frac{R}{c_{2}d_{2}b_{12}}

On summing over d_{2} by dividing the sum according to whether d_{2} is even or odd, we see on applying Lemma 2.1 that

∑_{\begin{matrix}d_{2}≤R/c_{2}b_{12} \\ (d_{2},b_{12}K_{1}K_{2})=1 \end{matrix}} \frac{μ(d_{2})𝔖_{2}(d_{2}b_{12}K_{1})}{ϕ(d_{2})} log \frac{R}{c_{2}d_{2}b_{12}}

= 2C_{2}H_{2}(b_{12}K_{1}) ∑_{\begin{matrix}d_{2}≤R/c_{2}b_{12} \\ (d_{2},b_{12}K_{1}K_{2})=1 \\ 2|d_{2}b_{12}K_{1} \end{matrix}} \frac{μ(d_{2})}{ϕ(d_{2})}H_{2}(d_{2}) log \frac{R}{c_{2}d_{2}b_{12}}

= 2C_{2}H_{2}(b_{12}K_{1})( − [(K_{1}K_{2}b_{12}, 2) = 1] ∑_{\begin{matrix}2d≤R/c_{2}b_{12} \\ (d,2b_{12}K_{1}K_{2})=1 \end{matrix}} \frac{μ(d)}{ϕ_{2}(d)} log \frac{R}{2c_{2}db_{12}}

+ [2|b_{12}K_{1}] ∑_{\begin{matrix}d_{2}≤R/c_{2}b_{12} \\ (d_{2},2b_{12}K_{1}K_{2})=1 \end{matrix}} \frac{μ(d_{2})}{ϕ_{2}(d_{2})} log \frac{R}{c_{2}d_{2}b_{12}} )

= 2C_{2}H_{2}(b_{12}K_{1})χ(b_{12})𝔖_{3}(2b_{12}K_{1}K_{2}) + O(H_{2}(b_{12}K_{1})e^{−c_{1}\sqrt{log(R/2c_{2}b_{12})}}),

where

χ(b_{12}) = −[(K_{1}K_{2}b_{12}, 2) = 1] + [2|b_{12}K_{1}].

Since c_{2}b_{12}|K_{1}(k_{2} − k_{1}), we see that the condition |Δ| < R/2 implies c_{2}b_{12} ≤ R/2 is automatically satisfied. Therefore we have

\begin{aligned}V_{R}(k) & = 2C_{2} ∑_{\begin{matrix}b_{12}|k_{2}−k_{1}, c_{2}|K_{1} \\ (b_{12},K_{1}K_{2})=1, (c_{2},K_{2})=1 \end{matrix}} \frac{μ(c_{2})μ^{2}(b_{12})H_{2}(b_{12}K_{1})χ(b_{12})𝔖_{3}(2b_{12}K_{1}K_{2})}{ϕ(c_{2})ϕ(b_{12})} + E_{2}(R) \\ & = Y_{R}(k) + E_{2}(R), \end{aligned} (11.11)

where

E_{2}(R) ≪ \frac{k_{1}}{ϕ(k_{1})}H_{2}(Δ)e^{−c_{1}\sqrt{log R/2Δ}}.

Since

∑_{\begin{matrix}c_{2}|K_{1} \\ (c_{2},K_{2})=1 \end{matrix}} \frac{μ(c_{2})}{ϕ(c_{2})} = ∏_{p| \frac{K_{1}}{K_{12}}} (1 − \frac{1}{p − 1}) = [(K_{1}/K_{12}, 2) = 1]\frac{H_{2}(K_{12})}{H_{2}(K_{1})},

we have

Y_{R}(k) = 2C_{2}[(K_{1}/K_{12}, 2) = 1]\frac{H_{2}(K_{12})}{H_{2}(K_{1})} ∑_{\begin{matrix}b_{12}|k_{2}−k_{1} \\ (b_{12},K_{1}K_{2})=1 \end{matrix}} \frac{μ^{2}(b_{12})H_{2}(b_{12}K_{1})χ(b_{12})𝔖_{3}(2b_{12}K_{1}K_{2})}{ϕ(b_{12})}. (11.12)

We divide the sum in the equation above according to the parity of b_{12} and apply Lemma 2.4 to see that the sum is

= [(K_{1}K_{2}, 2) = 1] ∑_{\begin{matrix}2b|k_{2}−k_{1} \\ (b,2K_{1}K_{2})=1 \end{matrix}} \frac{μ^{2}(b)H_{2}(bK_{1})χ(2b)𝔖_{3}(2bK_{1}K_{2})}{ϕ(b)}

+ ∑_{\begin{matrix}b_{12}|k_{2}−k_{1} \\ (b_{12},2K_{1}K_{2})=1 \end{matrix}} \frac{μ^{2}(b_{12})H_{2}(b_{12}K_{1})χ(b_{12})𝔖_{3}(2b_{12}K_{1}K_{2})}{ϕ(b_{12})}

= η(K_{1}, K_{2})H_{2}(K_{1}) ∑_{\begin{matrix}b|k_{2}−k_{1} \\ (b,2K_{1}K_{2})=1 \end{matrix}} \frac{μ^{2}(b)𝔖_{3}(2bK_{1}K_{2})}{ϕ_{2}(b)}

= η(K_{1}, K_{2})H_{2}(K_{1})𝔖_{3}(2K_{1}K_{2}(k_{2} − k_{1})),

where

η(K_{1}, K_{2}) = [(K_{1}K_{2}, 2) = 1][2|k_{2} − k_{1}] − [(K_{1}K_{2}, 2) = 1] + [2|K_{1}]

On substituting we have that

Y_{R}(k) = 2C_{2}[(K_{1}/K_{12}, 2) = 1]η(K_{1}, K_{2})H_{2}(K_{12})𝔖_{3}(2K_{1}K_{2}(k_{2} − k_{1})).

Now [(K_{1}/K_{12}, 2) = 1] = 0 if K_{1} is even and K_{2} is odd, and η(K_{1}, K_{2}) = 0 if both K_{1} and K_{2} are odd or K_{1} is odd and K_{2} is even. Hence Y_{R}(k) is zero unless K_{12} is even, and therefore

Y_{R}(k) = [2|K_{12}]2C_{2}H_{2}(K_{12})𝔖_{3}(2K_{1}K_{2}(k_{2} − k_{1})) = 𝔖_{2}(κ)𝔖_{3}(Δ) = 𝔖(k),

by Lemma 2.5. This completes the proof of Theorem 11.1 12. Application to primes

The use of correlations of short divisor sums to study primes goes back at least to Selberg’s work on the sieve. Our mixed correlation result that, for R ≤ N^{\frac{1}{4} −ϵ},

S̃_{3}(N, k) = ∑_{n=1}^{N} Λ_{R}^{2}(n)Λ(n + k) = 𝔖_{2}(k)N log R + o(N log N)  (12.1)

provides the upper bound for prime pairs in (1.39) with B = 4, since for n ≥ R

μ^{2}(n)Λ(n) ≤ \frac{log n}{log^{2} R}Λ_{R}^{2}(n),

and the prime powers make a contribution ≪ N^{1/2+ϵ}. The Selberg sieve provides the same information, and λ_{R}(n) in (1.2) gives the optimal majorant in the Selberg sieve for this problem when the appropriate normalization is used.

To study primes in short intervals, we consider the modified moments

M′_{k}(N, h, ψ_{R}, C) = ∑_{n=N+1}^{2N} (ψ_{R}(n + h) − ψ_{R}(n) − C log N)^{k},  (12.2)

and

M̃′_{k}(N, h, ψ_{R}, C) = ∑_{n=N+1}^{2N} (ψ(n + h) − ψ(n))(ψ_{R}(n + h) − ψ_{R}(n) − C log N)^{k−1}, (12.3)

where C is a function of h and R that will be chosen to optimize our applications. If we take C = 0 these moments reduce to the moments considered in Section 1. We will assume in this section that h = λ log N, λ ≪ 1, and thus

h ≪ log N,  (12.4)

which we will make free use of in our estimates. We now consider, for ρ ≥ 0,

M(h, ρ) = M̃′_{3}(N, h, ψ_{R}, C) − ρ log NM′_{2}(N, h, ψ_{R}, C)

= ∑_{n=N+1}^{2N} (ψ(n + h) − ψ(n) − ρ log N)(ψ_{R}(n + h) − ψ_{R}(n) − C log N)^{2}. (12.5)

To evaluate M(h, ρ) we see first that

M̃′_{3}(N, h, ψ_{R}, C) = M̃′_{3}(N, h, ψ_{R}) − 2C log NM̃′_{2}(N, h, ψ_{R}) + C^{2} log^{2} NM̃′_{1}(N, h, ψ_{R}).

We apply Corollary 1.5 (which as mentioned in Section 1 applies immediately to M̃′_{k} as well as M̃_{k}), with R = N^{θ} and 0 < θ < \frac{ϑ}{2},

M̃′_{3}(N, h, ψ_{R}, C) ∼ ((θ^{2}λ + 3θλ^{2} + λ^{3}) − 2C(θλ + λ^{2}) + C^{2}λ)N log^{3} N

and by Corollary 1.2, for 0 < θ ≤ \frac{1}{2},

M′_{2}(N, h, ψ_{R}, C) ∼ (θλ + λ^{2} − 2Cλ + C^{2})N log^{2} N.

We therefore see that M(h, ρ) is quadratic in C when λ ≠ ρ, and therefore on completing the square we find that, for λ ≠ ρ, and 0 < θ < \frac{ϑ}{2},

M(h, ρ) ∼ ((λ − ρ)(C − \frac{λ(λ − ρ + θ)}{λ − ρ})^{2} + \frac{λθ}{λ − ρ}((λ − ρ)^{2} − θρ))N log^{3} N.

By choosing

C = \frac{λ(λ − ρ + θ)}{λ − ρ} = λ(1 + \frac{θ}{λ − ρ})  (12.6)

we maximize M(h, ρ) if λ < ρ and minimize it if λ > ρ. We conclude that with this choice of C, and 0 < θ < \frac{ϑ}{2},

M(h, ρ) ∼ \frac{λθ}{λ − ρ}((λ − ρ)^{2} − θρ)N log^{3} N.  (12.7)

We see that M(h, ρ) is positive (and ≫ N log^{3} N ) when λ is a fixed number in the range ρ − \sqrt{θρ} < λ < ρ but is negative when ρ < λ < ρ + \sqrt{θρ}.

We now let P_{r}(N, h) denote the number of integers N < n ≤ 2N for which the interval (n, n + h] contains exactly r primes. Thus

P_{r}(N, h) = ∑_{\begin{matrix}n=N+1 \\ π(n+h)−π(n)=r \end{matrix}}^{2N} 1.  (12.8)

The Poisson model for primes in short intervals (see [6]) is equivalent to the conjecture that

P_{r}(N, h) ∼ \frac{λ^{r}e^{−λ}}{r!} N.  (12.9)

We let

Q_{r}^{−}(N, h) = ∑_{m=0}^{r} P_{m}(N, h) = ∑_{\begin{matrix}n=N+1 \\ π(n+h)−π(n)≤r \end{matrix}}^{2N} 1  (12.10)

and

Q_{r}^{+}(N, h) = ∑_{m=r+1}^{∞} P_{m}(N, h) = ∑_{\begin{matrix}n=N+1 \\ π(n+h)−π(n)>r \end{matrix}}^{2N} 1.  (12.11)

Thus we have

Q_{r}^{−}(N, h) + Q_{r}^{+}(N, h) = N.  (12.12)

We let p_{j_{0}} = p_{j_{0}}(N) and p_{j_{1}} = p_{j_{1}}(N) denote respectively the smallest and the largest primes in the interval [N + 1, 2N]. For smaller than average gaps between primes, we use the relation, for r ≥ 1,

Q_{r}^{+}(N, h) = ∑_{\begin{matrix}N+1≤n<p_{j_{0}} \\ π(n+h)−π(n)>r \end{matrix}} 1 + ∑_{j=j_{0}}^{j_{1}} ∑_{\begin{matrix}p_{j}≤n<p_{j+1} \\ p_{j+r+1}≤n+h \end{matrix}} 1 − ∑_{\begin{matrix}2N<n<p_{j_{1}+1} \\ π(n+h)−π(n)>r \end{matrix}} 1.

The first and third sums are O(Ne^{−c_{1}\sqrt{log N}}) by the prime number theorem with error term, and hence

Q_{r}^{+}(N, h) = ∑_{N+1≤p_{j}≤2N} ∑_{\begin{matrix}p_{j}≤n<p_{j+1} \\ p_{j+r+1}≤n+h \end{matrix}} 1 + O(Ne^{−c_{1}\sqrt{log N}})

= ∑_{\begin{matrix}N+1≤p_{j}≤2N \\ p_{j+r+1}−p_{j+1}<h \end{matrix}} (p_{j+1} − max(p_{j}, p_{j+r+1} − ⌊h⌋)) + O(Ne^{−c_{1}\sqrt{log N}})

≤ h ∑_{\begin{matrix}N+1≤p_{j}≤2N \\ p_{j+r+1}−p_{j+1}<h \end{matrix}} 1 + O(Ne^{−c_{1}\sqrt{log N}}).  (12.13)

For larger than average gaps between primes a similar argument shows, for r ≥ 0,

Q_{r}^{−}(N, h) = ∑_{N+1≤p_{j}≤2N} ∑_{\begin{matrix}p_{j}≤n<p_{j+1} \\ p_{j+r+1}>n+h \end{matrix}} 1 + O(Ne^{−c_{1}\sqrt{log N}})

= ∑_{\begin{matrix}N+1≤p_{j}≤2N \\ p_{j+r+1}−p_{j}>h \end{matrix}} ( min(p_{j+1}, p_{j+r+1} − ⌊h⌋) − p_{j}) + O(Ne^{−c_{1}\sqrt{log N}})

≤ ∑_{\begin{matrix}N+1≤p_{j}≤2N \\ p_{j+r+1}−p_{j}>h \end{matrix}}(p_{j+r+1} − p_{j}) + O(Ne^{−c_{1}\sqrt{log N}}).  (12.14)

Next, we have

Q_{r}^{+}(N, h) = ∑_{\begin{matrix}n=N+1 \\ ψ(n+h)−ψ(n)≥ρ log N \end{matrix}}^{2N} 1 + O(N^{\frac{1}{2}} ),  (12.15)

where ρ can be taken to be any number in the range r < ρ < r + 1, since the prime powers may be discarded with an error ≪ N^{\frac{1}{2}} . Also

Q_{r}^{−}(N, h) = ∑_{\begin{matrix}n=N+1 \\ ψ(n+h)−ψ(n)≤ρ log N \end{matrix}}^{2N} 1 + O(N^{\frac{1}{2}} ),  (12.16)

where again ρ can be taken to be any number in the range r < ρ < r + 1. Returning to (12.5), we see on applying Cauchy’s inequality twice and using (12.15) that

M(h, ρ) ≤ ∑_{\begin{matrix}n=N+1 \\ ψ(n+h)−ψ(n)≥ρ log N \end{matrix}}^{2N} (ψ(n + h) − ψ(n))(ψ_{R}(n + h) − ψ_{R}(n) − C log N)^{2}

≤ ( ∑_{\begin{matrix}n=N+1 \\ ψ(n+h)−ψ(n)≥ρ log N \end{matrix}}^{2N} 1)^{\frac{1}{4}} ( ∑_{n=N+1}^{2N}(ψ(n + h) − ψ(n))^{4})^{\frac{1}{4}}

( ∑_{n=N+1}^{2N}(ψ_{R}(n + h) − ψ_{R}(n) − C log N)^{4})^{\frac{1}{2}}

= (Q_{r}^{+}(N, h) + O(N^{\frac{1}{2}} ))^{\frac{1}{4}} M′_{4}(N, h, ψ)^{\frac{1}{4}} M′_{4}(N, h, ψ_{R}, C)^{\frac{1}{2}} . (12.17)

The same argument also shows that

−M(h, ρ) ≤ ρ log N(Q_{r}^{−}(N, h) + O(N^{\frac{1}{2}} ))^{\frac{1}{2}} M′_{4}(N, h, ψ_{R}, C)^{\frac{1}{2}} ,  (12.18)

and therefore we conclude that for any r < ρ < r + 1

\begin{aligned}−(Q_{r}^{−}(N, h) + O(N^{\frac{1}{2}} ))^{\frac{1}{2}} & ≤ \frac{M(h, ρ)}{ρ log NM′_{4}(N, h, ψ_{R}, C)^{\frac{1}{2}}} \\ & ≤ (Q_{r}^{+}(N, h) + O(N^{\frac{1}{2}} ))^{\frac{1}{4}} (\frac{M′_{4}(N, h, ψ)^{\frac{1}{4}}}{ρ log N} ) \end{aligned} (12.19)

To prove the first part of Theorem 1.6 we estimate the moments M′_{4}(N, h, ψ) and M′_{4}(N, h, ψ_{R}, C) trivially when h ≫ 1 using the inequality

|abcd| ≤ \frac{1}{4}(a^{4} + b^{4} + c^{4} + d^{4})

and the equation above (1.10) to see that

M′_{4}(N, h, ψ) = ∑_{\begin{matrix}1≤m_{i}≤h \\ 1≤i≤4 \end{matrix}} ∑_{n=N+1}^{2N} Λ(n + m_{1})Λ(n + m_{2})Λ(n + m_{3})Λ(n + m_{4})

≪ h^{4} ∑_{n≤3N} Λ(n)^{4}

≪ h^{4}N log^{3} N, and similarly

M′_{4}(N, h, ψ_{R}, C) ≪ M′_{4}(N, h, ψ_{R}) + N log^{4} N
≪ h^{4} ∑_{n≤3N} Λ_{R}(n)^{4} + N log^{4} N
≪ h^{4} log^{4} R ∑_{n≤3N} d(n)^{4}
≪ h^{4}N log^{19} N

by (4.14). Hence, subject to (12.4), we see by (12.7), (12.13), and (12.19) that, for r ≥ 1, and some positive constant C,

∑_{\begin{matrix}N+1≤p_{j}≤2N \\ p_{j+r+1}−p_{j+1}<h \end{matrix}} 1 ≫ \frac{N}{log^{C} N}  (12.20)

provided ρ − \sqrt{θρ} < λ < ρ, r < ρ < r + 1, and 0 < θ < \frac{ϑ}{2}. Since ρ can be taken as close to r as we wish, we conclude that

Ξ_{r} ≤ r − \sqrt{θr},

where unconditionally we may take any 0 < θ < 1/4. This proves the first part of Theorem 1.6. If we assume ϑ = 1 we can take 0 < θ < \frac{1}{2}. The corresponding result for larger than average gaps between primes is proved in the same way.

In order to obtain positive proportion results, we need to use the generalization of the sieve upper bound (1.39) for prime k-tuples. This result states that for the function ψj(N) defined in (1.8) where j = (j_{1}, j_{2}, …, j_{r}) with the j_{i}’s distinct and 𝔖(j) ≠ 0

ψj(N) ≤ (2^{r}r! + ϵ)𝔖(j)N,  (12.21)

see Theorem 5.7 of [16]. On applying this bound to the formulas leading to (1.15) we see that, subject to (12.4),

M_{k}(N, h, ψ) ≪ N(log N)^{k},  (12.22)

which implies the same estimate holds for M′_{k}(N, h, ψ). Next, as above

M′_{4}(N, h, ψ_{R}, C) ≪ M′_{4}(N, h, ψ_{R}) + N log^{4} N,

and therefore assuming (1.47) we have, for 0 < θ < \frac{1}{4},

M′_{4}(N, h, ψ_{R}, C) ≪ N log^{4} N.  (12.23)

Using these estimates in (12.19) we obtain

∑_{\begin{matrix}N+1≤p_{j}≤2N \\ p_{j+r+1}−p_{j+1}<h \end{matrix}} 1 ≫ \frac{N}{log N}  (12.24)

under the same conditions as (12.20) and 0 < θ < \frac{1}{4}. This proves the remaining part of Theorem 1.6.

In an identical fashion we see that if M(h, ρ) < 0 then assuming (1.47) we have

∑_{\begin{matrix}N+1≤p_{j}≤2N \\ p_{j+r+1}−p_{j}>h \end{matrix}}(p_{j+r+1} − p_{j}) ≫ N,  (12.25)

where r ≥ 0, r < ρ < r + 1, ρ < λ < ρ + \sqrt{θρ}, and 0 < θ < \frac{1}{4}. Since ρ can be taken as close to r + 1 and θ as close to \frac{1}{4} as we wish, this completes the proof of Theorem 1.7.

References

[1] E. Bombieri and H. Davenport, Small differences between prime numbers, Proc. Roy. Soc. Ser. A, 293 (1966), 1–18.

[2] E. Bombieri, J. B. Friedlander, and H. Iwaniec, Primes in arithmetic progressions to large moduli, Acta Math. 156 (1986), no. 3-4, 203–251.

[3] A. Y. Cheer and D. A. Goldston, Longer than average intervals containing no primes, Transactions of the AMS, 304 No.2 (1987), 469–486.

[4] J.-R. Chen, On the Goldbach problem and the sieve methods, Sci. Sinica 21 (1978), 701–739.

[5] J. B. Friedlander and D. A. Goldston, Some singular series averages and the distribution of Goldbach numbers in short intervals, Illinois J. of Math. 39 No. 1,(1995), 158–180.

[6] P. X. Gallagher, On the distribution of primes in short intervals, Mathematika 23 (1976), 4–9.

[7] D. A. Goldston, The second moment for prime numbers, Quart. J. Math. Oxford (2) 35 (1984), 153–163.

[8] D. A. Goldston, On Bombieri and Davenport’s theorem concerning small gaps between primes, Mathematika 39 (1992), 10–17.

[9] D. A. Goldston, A lower bound for the second moment of primes in short intervals, Expo. Math. 13 (1995), 366–376.

[10] D. A. Goldston and H. L. Montgomery, Pair correlation of zeros and primes in short intervals, Analytic Number Theory and Diophantine Problems, Birkhaüser, Boston, Mass., 1987, 183–203.

[11] D. A. Goldston and C. Y. Yıldırım, On the second moment for primes in an arithmetic progression, Acta Arithmetica C.1 (2001), 85–104.

[12] R. L. Graham, D. E. Knuth, and O. Patashnik, Concrete Mathematics. A foundation for computer science, Second Edition. Addison-Wesley Publishing Company, Reading, MA, 1994.

[13] S. Graham, An asymptotic estimate related to Selberg’s sieve, J. Number Theory 10 (1978), 83–94.

[14] 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), 1–70.

[15] A. Hildebrand, Über die punktweise Konvergenz von Ramanujan-Entwicklungen zahlentheoretischer Funktionen, Acta Arithmetica XLIV (1984), 109–140.

[16] H. Halberstam and H. -E. Richert, Sieve methods Academic Press, London-New York, 1974.

[17] D. R. Heath-Brown, The ternary Goldbach problem, Rev. Mat. Iberoamericana 1 (1985), no. 1, 45–59.

[18] C. Hooley, On the Barban-Davenport-Halberstam theorem XIII, Acta Arithmetica XCIV (2000), no. 1, 53–86.

[19] Loo Keng Hua, Introduction to number theory, Translated from the Chinese by Peter Shiu, Springer-Verlag, Berlin-New York, 1982.

[20] M. N. Huxley, Small differences between consecutive primes II, Mathematika 24 (1977), 142–152.

[21] M. N. Huxley, An application of the Fouvry-Iwaniec theorem, Acta Arithmetica XLIII (1984), 441–443.

[22] H. Maier, Small differences between prime numbers, Michigan Math. J. 35 (1988), 323–344.

[23] H. L. Montgomery and K. Soundararajan, Beyond pair correlation, preprint 1999, 1–20.

[24] J. Pintz, Very large gaps between consecutive primes, J. of Number Theory 63 (1997), 286–301.

[25] A. Selberg, Contributions to the theory of Dirichlet’s L-functions, Skrifter utgitt ay Det Norske Videnskaps-Akademi i Oslo I. Mat.-Naturv. Klasse (1946), No. 3, 1–62.

[26] E. C. Titchmarsh, The theory of the Riemann zeta-function, Second edition. Edited and with a preface by D. R. Heath-Brown. The Clarendon Press, Oxford University Press, New York, 1986.