Estimates for sums over primes

18.1 Principles of the method

Let

S = ∑_{n≤N} f(n)Λ(n) .

If f is monotonic, then we can estimate S by using the Prime Number Theorem and integration by parts. If f is multiplicative, then we can gain information concerning S by studying the properties of the associated Dirichlet series ∑ f(n)n^{−s}. This has already been especially successful when f is of the form f(n) = χ(n)n^{−s}. We now introduce an entirely different method that is most successful when f is far from being multiplicative. Let P = ∏_{p≤\sqrt{N}} p. Vinogradov (1937) had the idea of writing

f(1) + ∑_{\sqrt{N}<p≤N} f(p) = ∑_{\begin{matrix}1≤n≤N \\ (n,P)=1 \end{matrix}} f(n) = ∑_{\begin{matrix}t|P \\ t≤N \end{matrix}} μ(t) ∑_{r≤N/t} f(rt) .

If we can demonstrate that there is considerable cancellation the inner sum on the right, then we can obtain a non-trivial estimate for the left hand side. However, when t is near N in size, one expects to have little cancellation, and indeed when N/2 < t ≤ N the sum has only one term, and hence no cancellation at all. Hence the terms on the right must be rearranged before satisfactory estimates can be derived. This approach, known as Vinogradov’s method for prime number sums, is rather complicated, but Vaughan (1977) devised a much simpler variant (Vaughan’s version of Vinogradov’s method), which we now describe.

Our first step involves expressing Λ(n) as a linear combination of several other arithmetic functions. Put

(18.1)  F (s) = ∑_{m≤U} Λ(n)n^{−s},  G(s) = ∑_{d≤V} μ(d)d^{−s} .

Clearly

(18.2)  \begin{aligned}− \frac{ζ′}{ζ} (s) & = F (s) − ζ(s)F (s)G(s) − ζ′(s)G(s) \\ & + ( − \frac{ζ′}{ζ} (s) − F (s))(1 − ζ(s)G(s)) \end{aligned}

for σ > 1. By calculating the Dirichlet series coefficients of the four Dirichlet series on the right hand side, we deduce that

(18.3)  Λ(n) = a_{1}(n) + a_{2}(n) + a_{3}(n) + a_{4}(n)

where

a_{1}(n) = \{ \begin{matrix}Λ(n) & if n ≤ U, \\ 0 & if n > U, \end{matrix}
a_{2}(n) = − ∑_{\begin{matrix}mdr=n \\ m≤U \\ d≤V \end{matrix}} Λ(m)μ(d),

a_{3}(n) = ∑_{\begin{matrix}hd=n \\ d≤V \end{matrix}} μ(d) log h,

a_{4}(n) = − ∑_{\begin{matrix}mk=n \\ m>V \\ k>1 \end{matrix}} Λ(n) ∑_{\begin{matrix}d|k \\ d≤V \end{matrix}} μ(d) .

We multiply (18.3) through by f(n) and sum to see that

S = S_{1} + S_{2} + S_{3} + S_{4}

where

S_{i} = ∑_{n≤N} f(n)a_{i}(n) .

We generally estimate S_{1} trivially, but the other terms require individual treatment. We note that

(18.4)  S_{2} = ∑_{t≤UV} b(t) ∑_{r≤N/t} f(rt)

where

b(t) = − ∑_{\begin{matrix}md=t \\ m≤U \\ d≤V \end{matrix}} μ(d)Λ(m) .

Since |b(t)| ≤ ∑_{m|t} Λ(m) = log t ≤ log UV, it follows that

(18.5)  S_{2} ≪ (log UV) ∑_{t≤UV} | ∑_{r≤N/t} f(rt)| .

As for S_{3}, we find that

(18.6)

S_{3} = ∑_{d≤V} μ(d) ∑_{h≤N/d} f(dh) log h = ∑_{d≤V} μ(d) ∑_{h≤N/d} f(dh) ∫_{1}^{h} \frac{dw}{w}

= ∫_{1}^{N} ∑_{d≤V} μ(d) ∑_{w≤h≤N/d} f(dh)\frac{dw}{w}

≪ (log N) ∑_{d≤V} max_{w≥1} | ∑_{w≤h≤N/d} f(dh)| .

Let

c(k) = ∑_{\begin{matrix}d|k \\ d≤V \end{matrix}} μ(d) .

Since c(k) = 0 for 1 < k ≤ V, it follows that

S_{4} = ∑_{U<m≤N/V} Λ(m) ∑_{V <k≤N/m} c(k)f(mk) .

Suppose that Δ(M) = Δ(M, N, f) is defined so that

(18.7) | ∑_{M<m≤2M} b_{m} ∑_{k≤N/m} c_{k}f(mk)| ≤ Δ(M)( ∑_{M<m≤2M} |b_{m}|^{2})^{1/2}( ∑_{k≤N/M} |c_{k}|^{2})^{1/2}

for arbitrary complex numbers b_{m} and c_{k}. By cutting the interval U ≤ m ≤ N/V into ≪ log N subintervals of the form M < m ≤ 2M, we deduce that

S_{4} ≪ (log N) max_{U≤M≤N/V} Δ(M)( ∑_{M<m≤2M} Λ(m)^{2})^{1/2}( ∑_{k≤N/M} |c(k)|^{2})^{1/2} .

Here the sum over m is ≤ ψ(2M) log 2M ≪ M log 2M. Since |c(k)| ≤ d(k) for all k, we deduce by (2.31) that the sum over k is ≪ NM^{−1}(log N)^{3}. Hence

(18.8)  S_{4} ≪ N^{1/2}(log N)^{3} max_{U≤M≤N/V} Δ(M) .

We interrupt our development at this point in order to assess the situation. For purposes of discussion, in this paragraph only, we assume that |f(n)| ≤ 1 for all n. The bound S ≪ N is trivial, and if f is oscillatory we hope to show that S = o(N). Trivially S_{1} ≪ U, so S_{1} poses no problem provided that U = o(N). In (18.5) the trivial bound would be that

S_{2} ≪ (log UV) ∑_{t≤UV} \frac{N}{t} ≪ N(log UV)^{2}

Thus in order to get a bound that is o(N) we only need to demonstrate a modest amount of cancellation in the sum over r in (18.5), and even this only on average over t. We note, however, that there will be little or no cancellation if the inner sum has very few terms (a single term is the worst case). For this reason it will be necessary to choose the parameters U and V so that UV is considerably smaller than N. Similar remarks apply to (18.6) where the situation is even more favorable since the range of d in (18.6) is shorter than that of t in (18.5). To obtain a trivial bound for Δ(M) we first observe that

| ∑_{M<m≤2M} b_{m} ∑_{k≤N/m} c_{k}f(mk)| ≤ ∑_{M<m≤2M} |b_{m}| ∑_{k≤N/M} |c_{k}| .

By Cauchy’s inequality, this in turn is

≪ (M · N/M)^{1/2}( ∑_{M<m≤2M} |b_{m}|^{2})^{1/2}( ∑_{k≤N/M} |c_{k}|^{2})^{1/2} .

Thus the bound Δ(M) ≪ N^{1/2} is trivial. By inserting this in (18.8) we deduce that S_{4} ≪ N(log N)^{3} trivially. That is, we will be able to show that S_{4} = o(N) if we can obtain a bound for Δ(M) that is only a power of a logarithm smaller than trivial. In summary, it seems that we have not dug ourselves into too deep a hole, and that we can expect to show that S = o(N) whenever we can derive estimates that are only moderately better than trivial. We note, however, that if f were to be unimodular and totally multiplicative, then we might obtain nontrivial estimates for S_{2} and S_{3}, but no nontrivial estimate for Δ(M) can hold because of the possibility that b_{m} = \overline{f(m)} and c_{k} = \overline{f(k)}. Despite this observation, we shall find in Chapters 20 and 25 that we can still use our present approach when we average over several multiplicative functions f_{i}.

In order to estimate Δ(M), we first observe that by Cauchy’s inequality the left hand side of (18.7) is

≤ ( ∑_{M<m≤2M} |b_{m}|^{2})^{1/2}( ∑_{M<m≤2M} | ∑_{k≤N/m} c_{k}f(mk)|^{2} )^{1/2} .

Here the second sum over m is

(18.9)  = ∑_{j≤N/M} c_{j} ∑_{k≤N/M} \overline{c_{k}} ∑_{\begin{matrix}M<m≤2M \\ m≤N/j \\ m≤N/k \end{matrix}} f(mj)\overline{f(mk)} .

By the arithmetic-geometric mean inequality we know that |c_{j}c_{k}| ≤ \frac{1}{2}|c_{j}|^{2} + \frac{1}{2}|c_{k}|^{2}. Thus the above is

(18.10) ≪ ∑_{k≤N/M} |c_{k}|^{2} ∑_{j≤N/M} | ∑_{\begin{matrix}M≤m≤2M \\ m≤N/j \\ m≤N/k \end{matrix}} f(mj)\overline{f(mk)} |^{2}

≤ ( ∑_{k≤N/M} |c_{k}|^{2})( max_{k≤N/M} ∑_{j≤N/M} | ∑_{\begin{matrix}M≤m≤2M \\ m≤N/j \\ m≤N/k \end{matrix}} f(mj)\overline{f(mk)} |^{2}) .

Thus

(18.11)  Δ(M) ≪ ( max_{k≤N/M} ∑_{j≤N/M} | ∑_{\begin{matrix}M<m≤2M \\ m≤N/j \\ m≤N/k \end{matrix}} f(mj)\overline{f(mk)} |^{2})^{1/2},

and so by (18.8) we conclude that

S_{4} ≪ N^{1/2}(log N)^{3}

(18.12) × max_{U≤M≤N/V} max_{k≤N/M} ( ∑_{j≤N/M} | ∑_{\begin{matrix}M<m≤2M \\ m≤N/j \\ m≤N/k \end{matrix}} f(mj)\overline{f(mk)} |^{2})^{1/2} .

Clearly our bound (18.5) for S_{2} becomes better when UV is reduced. On the other hand, our bound above for S_{4} becomes better when U and V are increased. In practice, we choose the parameters to optimize these bounds.

Our strategy for bounding S_{4} may be inferior, for two reasons. In the first place, we need to bound the double sum on the left hand side of (18.7) not for arbitrary b_{m} and c_{k} but only in the special case that b_{m} = Λ(m) and c_{k} = c(k). Secondly, the double sum on the left hand side of (18.7) is a linear function of the b_{m}, and is also linear in the c_{k}. Such an expression is known as a bilinear form, and in Appendix F we develop a general theory concerning bounds for bilinear forms. Indeed, we could have passed directly from (18.7) to (18.11) simply by appealing to Corollary F.4. Although we have taken a more elementary route, the general theory offers some insights. From Theorem F.1 we see that from (18.7) up to (18.9) we have thrown nothing away. In (18.9) we again have a bilinear form, but this time the coefficient matrix is not only square, but Hermitian as well, and hence normal. Thus by Corollary F.11 the problem is to determine (or estimate) the spectral radius of this matrix. In passing from (18.9) to (18.10) we have in effect derived a bound for this spectral radius, but our bound may be considerably larger than the truth.

An expression of the form

(18.13)  ∑_{m≤W} b_{m} ∑_{X≤k≤N/m} f(mk)

is known as a ‘Type I sum’. Thus S_{2} and S_{3} are Type I sums. An expression of the form

(18.14)  ∑_{Y ≤m≤Z} ∑_{k≤N/m} b_{m}c_{k}f(mk)

is known as a ‘Type II sum’. Thus S_{4} is a Type II sum.

In some situations, the estimate we derive can be improved by playing the following trick: We take a Type I sum (such as S_{2}) and write it as

∑_{m≤W} b_{m} ∑_{X≤k≤N/m}f(mk) = ∑_{m≤Y} b_{m} ∑_{X≤k≤N/m}f(mk) + ∑_{Y <m≤W} b_{m} ∑_{X≤k≤N/m}f(mk)

= S_{I} + S_{II}, (18.15)

say. Here S_{I} is treated as a Type I sum, but the estimate is better because Y is smaller than W, and we treat S_{II} as a Type II sum.

18.1.1 Exercises

1. Suppose that Δ′(M) = Δ′(M, N, V, f) is defined so that (18.16)

| ∑_{M<m≤2M} b_{m} ∑_{V <k≤N/m} c_{k}f(mk)| ≤ Δ′(M)( ∑_{M<m≤2M} |b_{m}|^{2})^{1/2}( ∑_{V <k≤N/M} |c_{k}|^{2})^{1/2}

for arbitrary complex numbers b_{m} and c_{k}.

(a) Show that

(18.17)  S_{4} ≪ N^{1/2}(log N)^{3} max_{U≤M≤N/V} Δ′(M) .

(b) Deduce that

(18.18)  Δ′(M) ≪ ( max_{V <k≤N/M} ∑_{V <j≤N/M} | ∑_{\begin{matrix}M<m≤2M \\ m≤N/j \\ m≤N/k \end{matrix}} f(mj)\overline{f(mk)} |^{2})^{1/2},

(c) Conclude that

S_{4} ≪ N^{1/2}(log N)^{3}

(18.19) × max_{U≤M≤N/V} max_{V <k≤N/M} ( ∑_{V <j≤N/M} | ∑_{\begin{matrix}M≤m≤2M \\ m≤N/j \\ m≤N/k \end{matrix}} f(mj)\overline{f(mk)} |^{2})^{1/2} .

2. Let S_{2} be defined as in (18.4), and write

S_{2} = ∑_{t≤V} b(t) ∑_{r≤N/t} f(rt) + ∑_{V <t≤UV} b(t) ∑_{r≤N/t} f(rt)
= S_{I} + S_{II},

say. Show that

(18.20)  S_{II} ≪ N^{1/2}(log N)^{2} max_{V ≤M≤UV} Δ(M) .

3. Let Δ(M) denote the best constant in the bilinear form inequality (18.7). By appealing to an apropriate result from Appendix F, or otherwise, show also that if |f(n)| ≥ 1 for all n, then

Δ ≥ max(M^{1/2}, (N/M)^{1/2}).

(Hence our method, as presently constituted, never gives an upper bound better than N^{3/4} when f is unimodular.)

4. (Linnik 1961) Let d′_{k}(n) = card{(n_{1}, …, n_{k}) : n_{1}n_{2} ⋯ n_{k} = n, n_{i} > 1}. Show that

\frac{Λ(n)}{log n} = ∑_{k=1}^{K}(−1)^{k}d′_{k}(n)/k

if K ≥ (log n)/ log 2.

5. (Montgomery & Vaughan 1981) Let G(s) be defined as in (18.1). From the identity

(18.21)  \frac{1}{ζ(s)} = 2G(s) − G(s)^{2}ζ(s) + (\frac{1}{ζ(s)} − G(s)) (1 − ζ(s)G(s)),

or otherwise, show that

μ(n) = a_{0}(n) + a_{1}(n) + a_{2}(n)

where

a_{0}(n) = \{ \begin{matrix}2μ(n) & n ≤ V, \\ 0 & n > V, \end{matrix}
a_{1}(n) = − ∑_{\begin{matrix}dem=n \\ d≤V \\ e≤V \end{matrix}} μ(d)μ(e),

a_{2}(n) = − ∑_{\begin{matrix}dk=n \\ d>V \\ k>V \end{matrix}} μ(d)( ∑_{\begin{matrix}e|k \\ e≤V \end{matrix}} μ(e)).

6. Show that if 1 ≤ V ≤ N, then

∑_{n=1}^{N} μ(n)f(n) = T_{0} + T_{1} + T_{2}

624 Estimates for sums over primes

where

(18.22)  T_{1} = 2 ∑_{n=1}^{V} μ(n)f(n),
(18.23)  T_{2} = − ∑_{m≤V^{2}} b_{m} ∑_{n≤N/m} f(mn),  b_{m} = ∑_{\begin{matrix}de=m \\ d,e≤V \end{matrix}} μ(d)μ(e),

and

(18.24)  T_{3} = − ∑_{V <m≤N/V} ∑_{V <n≤N/m} μ(m)c_{n}f(mn),  c_{n} = ∑_{\begin{matrix}d|n \\ d≤V \end{matrix}} μ(d).

7. With the T_{i} defined as above, show that

(18.25)  T_{0} ≪ ∑_{n≤V} |f(n)|,
(18.26)  T_{1} ≪ ∑_{r≤V^{2}} d(r)| ∑_{k≤N/r} f(rk)|,

and

T_{2} ≪ N^{1/2}(log N)^{5/2}

(18.27)

× max_{V ≤M≤N/V} max_{j≤N/M} ( ∑_{k≤N/M} | ∑_{\begin{matrix}M<m≤2M \\ m≤N/k \\ m≤N/j \end{matrix}} f(mj)\overline{f(mk)} |)^{1/2}.

2. Applications

We begin with an historically important example, which will be invaluable in Chapter 21. Theorem 18.1 For N ≥ 2, let

(18.28)  S(α) = ∑_{n=1}^{N} Λ(n)e(nα) .

If (a, q) = 1 and |α − a/q| ≤ 1/q^{2}, then

(18.29)  S(α) ≪ (Nq^{−1/2} + N^{4/5} + N^{1/2}q^{1/2})(log N)^{4} .

Here e(θ) = e^{2πiθ} is the complex exponential with period 1.

Proof. By the formula for a segment of a geometric series we see that if β is not an integer, then

∑_{n=1}^{N} e(nβ) = \frac{e((N + 1)β) − e(β)}{e(β) − 1}

= e((N + 1)β/2)\frac{e(Nβ/2) − e(−Nβ/2)}{e(β/2) − e(−β/2)}

= e((N + 1)β/2)\frac{sin πNβ}{sin πβ} .

But | sin πβ| ≥ 2∥β∥ where ∥β∥ denotes the distance from β to the nearest integer, ∥β∥ = min_{n∈ℤ} |β − n|, so

(18.30)  | ∑_{n=1}^{N} e(nβ)| ≤ min (N, \frac{1}{2∥β∥}) .

Thus

(18.31)  ∑_{0<t≤T} max_{w≥1} | ∑_{w≤r≤N/t} e(rtα)| ≪ ∑_{0<t≤T} min (\frac{N}{t} , \frac{1}{∥tα∥}) .

To estimate the right hand side, we write t = hq + r and sum over 0 ≤ h ≤ T/q and 1 ≤ r ≤ q. Let δ = α − a/q. We consider first the case in which h = 0 and 1 ≤ r ≤ q/2. Since |δ| ≤ 1/q^{2}, ∥rα∥ differs from ∥ra/q∥ by at most 1/(2q). But ∥ra/q∥ ≥ 1/q for these r, and hence ∥rα∥ ≍ ∥ra/q∥. Consequently

∑_{1≤r≤q/2} \frac{1}{∥rα∥} ≪ ∑_{1≤r≤q/2} \frac{1}{∥ra/q∥} ≪ ∑_{1≤r≤q/2} \frac{q}{r} ≪ q log 2q .

For all other terms we have hq + r ≫ (h + 1)q. Thus it suffices to estimate

(18.32)  ∑_{0≤h≤T/q} ∑_{r=1}^{q} min (\frac{N}{(h + 1)q} , \frac{1}{∥hqα + ra/q + rδ∥}) .

For any given h, the q points hqα + ra/q + rδ are uniformly within 1/q of the equallyspaced points hqα + ra/q. Thus if ∥hqα + ra/q + rδ∥ < 1/q, then ∥hqα + ra/q∥ < 2/q, and this holds for at most 4 values of r. For all other r, the numbers ∥hqα + ra/q + rδ∥ are comparable to the numbers ∥r/q∥ for 0 < r < q. Hence the double sum (18.32) is

≪ ∑_{0≤h≤T/q} (\frac{N}{(h + 1)q} + q log 2q) ≪ \frac{N}{q} log 2T/q + T log 2q + q log 2q .

626 Estimates for sums over primes That is, we have shown that

(18.33)  ∑_{0<t≤T} min (\frac{N}{t} , \frac{1}{∥tα∥}) ≪ (N/q + T + q) log 2T q .

By (18.5) we deduce that

S_{2} ≪ (N/q + UV + q)(log 2qUV)^{2} .

Similarly, from (18.6) we see that

S_{3} ≪ (N/q + V + q)(log 2qV N)^{2}

By (18.12) and (18.30) we find that

S_{4} ≪ N^{1/2}(log N)^{3} max_{U≤M≤N/V} max_{k≤N/M} ( ∑_{j≤N/M} min (M, \frac{1}{∥(j − k)α∥}))^{1/2} .

Here the sum over j is

≪ M + ∑_{0<j≤N/M} min (M, \frac{1}{∥jα∥}) ≪ M + ∑_{0<j≤N/M} min (\frac{N}{j} , \frac{1}{∥jα∥})

since M ≤ N/j for j ≤ N/M. Thus by a further application of (18.33) we deduce that

S_{4} ≪ (Nq^{−1/2} + NU^{−1/2} + NV^{−1/2} + N^{1/2}q^{1/2})(log 2qN)^{4} .

By taking U = V = N^{2/5} we deduce that

S(α) ≪ (Nq^{−1/2} + N^{4/5} + N^{1/2}q^{1/2})(log 2qN)^{4}

To complete the argument it suffices to note that we may assume that q ≤ N, since otherwise the estimate (18.29) is weaker than the trivial estimate S(α) ≪ N.

18.2.1 Exercises

1. Show that if |α − a/q| ≤ 1/q^{2} and (a, q) = 1, then

∑_{n≤N} μ(n)e(nα) ≪ N(log N)^{3}(Nq^{−1/2} + N^{4/5+ε} + N^{1/2}q^{1/2})(log N)^{3}.

2. Show that if q is a positive integer, then for any integer c,

e(c/q) = ∑_{\begin{matrix}d|q \\ d|c \end{matrix}} \frac{1}{ϕ(q/d)} ∑_{\begin{matrix}χ \\ (mod q/d) \end{matrix}} τ(\overline{χ})χ(c/d).

3. Let

M(x; χ, δ) = ∑_{n≤x} χ(n)μ(n)e(nδ)

where χ is a Dirichlet character, x is real, and δ ∈ 𝕋. Let A and B be given positive real numbers. Show that if α = a/q + δ with (a, q) = 1, then

∑_{n≤x} μ(n)e(nα) = ∑_{d|q} \frac{μ(d)}{ϕ(q/d)} ∑_{\begin{matrix}χ \\ (mod q/d) \end{matrix}} τ(\overline{χ})χ(a)M(x/d; χχ_{0(d)}, δ)

where χ_{0(d)} denotes the principal character modulo d.

4. Let M(x; χ, δ) be defined as in the preceding problem. Show that if χ is a character modulo q and q ≤ (log x)^{A}, then

M(x; χ, δ) ≪ (1 + x∥δ∥)x(log x)^{−B}.

5. (Davenport 1937a,b) Show that if |α − a/q| ≤ 1/q^{2}, (a, q) = 1, and q ≤ (log x)^{A}, then

(18.34)  ∑_{n≤x} μ(n)e(nα) ≪ x(log x)^{−B}.

By combining this with the result of Exercise 1, show that the above estimate holds uniformly in α.

6. Show that the series

∑_{n=1}^{∞} \frac{μ(n)}{n}e(nα)

is uniformly convergent, and thus defines a continuous function on 𝕋.

Suppose that

F (n) = ∑_{d|n} f(d)

for all n, and let s(x) denote the saw-tooth function with period 1,

s(x) = \{ \begin{matrix}\{x\} − 1/2 & (x ∉ ℤ), \\ 0 & (x ∈ ℤ). \end{matrix}

By the Fourier series expansion of Lemma D.1, we see that

(18.35)  ∑_{d=1}^{∞} \frac{f(d)}{d}s(dα) = − ∑_{d=1}^{∞} \frac{f(d)}{d} ∑_{m=1}^{∞} \frac{sin 2πmdα}{πm}

= − ∑_{n=1}^{∞} \frac{F (n)}{πn} sin 2πnα, (18.36)

by grouping together those pairs m, d for which md = n. This is merely a formal argument, since we have not justified the reorganization of terms in passing from (18.35) to (19.36). In the next several exercises, we treat this issue in the interesting case that f(d) = μ(d).

7. Let

(18.37)  S_{D}(α) = ∑_{d≤D} \frac{μ(d)}{d}s(dα) .

(a) Let N be a parameter to be chosen later such that N > D, and let E_{K}(x) be defined as in Lemma D.1. Show that

S_{D}(α) = \frac{−1}{π} sin 2πα + T_{1}(α) + T_{2}(α)

where

T_{1} = \frac{1}{π} ∑_{D<d≤N} \frac{μ(d)}{d} ∑_{n≤N/d} \frac{sin 2πndα}{πn},

T_{2} = ∑_{d≤D} \frac{μ(d)}{d}E_{N/d}(α) .

(b) Show that

T_{1} = ∑_{n≤N/D} \frac{1}{n} ∑_{D<d≤N/n} \frac{μ(d)}{d} sin 2πndα

(c) Use (18.34) to show that T_{1} ≪ (log D)^{−B}(log N/D)^{2}.

(d) Explain why E_{K}(0) = 0.

(e) Show that if (a, q) = 1 and q ≤ D, then T_{2}(a/q) ≪ DN^{−1} log 2q.

(f) Take N = D(log D)^{A}, and deduce that

(18.38)  S_{D}(α) = \frac{−1}{π} sin 2πα + O((log D)^{−B})

when α = a/q, (a, q) = 1, and q ≤ D.

8. Let S_{D}(α) be defined as in (18.37). (a) Show that S_{D}(α) is piecewise linear with slope M(D) = ∑_{d≤D} μ(d) and jump discontinuities at the Farey fractions of order D.

(b) Write

x ∑_{\begin{matrix}n≤x \\ (n,q)=1 \end{matrix}} \frac{μ(n)}{n} = ∑_{\begin{matrix}n≤x \\ (n,q)=1 \end{matrix}} μ(n)[x/n] + ∑_{\begin{matrix}n≤x \\ (n,q)=1 \end{matrix}} μ(n)x/n

= Σ_{1} + Σ_{2},

say. Show that Σ_{1} is the number of integers not exceeding x that are composed entirely of prime numbers that divide q. Hence deduce that |Σ_{1}| ≤ x.

(c) Explain why |Σ_{2}| ≤ x.

(d) Deduce that

| ∑_{\begin{matrix}n≤x \\ (n,q)=1 \end{matrix}} \frac{μ(n)}{n}| ≤ 2

uniformly in x and q.

(e) Let S_{D}(α) be defined as in (18.37) and let a/q denote a Farey fraction of order D. Show that the jump discontinuity of S_{D}(α) at α = a/q is

− ∑_{\begin{matrix}d≤D \\ q|d \end{matrix}} \frac{μ(d)}{d} .

(f) Show that the above expression has absolute value not exceeding 2/q.

(g) Let ℛ denote the set of numbers composed entirely of primes dividing q. Show that

∑_{\begin{matrix}d|n \\ d∈ℛ \end{matrix}} μ(n/d) = \{ \begin{matrix}μ(n) & if (n, q) = 1, \\ 0 & otherwise. \end{matrix}

(h) Deduce that

∑_{\begin{matrix}n≤x \\ (n,q)=1 \end{matrix}} \frac{μ(n)}{n} = ∑_{\begin{matrix}d≤x \\ d∈ℛ \end{matrix}} \frac{1}{d} ∑_{m≤x/d} \frac{μ(m)}{m} .

(i) By adapting the techniques developed in §7.1, show that if q ≤ x^{2}, then the number of members of ℛ not exceeding x is ≪ x^{ε}.

(j) Deduce that if q ≤ x, then

∑_{\begin{matrix}n≤x \\ (n,q)=1 \end{matrix}} \frac{μ(n)}{n} ≪ exp ( − c\sqrt{log x} ) .

(k) (Davenport 1937a,b) Conclude that (18.38) holds uniformly in α.

9. (Montgomery & Vaughan 1981; continued from Exercise 13.2.1.16.) Let

S(x, y) = ∑_{d≤y} μ(d)B_{1}({x/d^{2}})

where B_{1}(u) = u − 1/2 is the first Bernoulli polynomial.

(a) By van der Corput’s method, or otherwise, show that

∑_{d≤D} μ(d)e(W/d^{2}) ≪ W^{1/2}D^{17/24}(log D)^{A}

for D^{31/14} ≤ W ≤ D^{7/2}.

(b) Deduce that S(x, y) ≪ for

(c) Conclude that if RH is true, then the number Q(x) of squarefree numbers not exceeding x is

Q(x) = \frac{6}{π^{2}} x + O(x^{21/64+ε}) .