The Large Sieve

19.1 Analytic principles

Bessel’s inequality asserts that if ϕ_{1}, ϕ_{2}, …, ϕ_{R} are orthonormal vectors in an inner product space V, then

(19.1)  ∑_{r=1}^{R} |(ξ, ϕ_{r})|^{2} ≤ ∥ξ∥^{2}

for all ξ ∈ V. The proof of this is quite simple: For arbitrary y_{r},

0 ≤ ∥ξ − ∑_{r=1}^{R} y_{r}ϕ_{r}∥^{2} = ∥ξ∥^{2} − 2ℜ ∑_{r=1}^{R} \overline{y_{r}}(ξ, ϕ_{r}) + ∥ ∑_{r=1}^{R} y_{r}ϕ_{r}∥^{2}

= ∥ξ∥^{2} − 2ℜ ∑_{r=1}^{R} \overline{y_{r}}(ξ, ϕ_{r}) + ∑_{r=1}^{R} |y_{r}|^{2}. (19.2)

Set y_{r} = (ξ, ϕ_{r}). Then the expression (19.2) is ∥ξ∥^{2} − ∑_{r} |(ξ, ϕ_{r})|^{2}, so the proof is complete. However, in analytic number theory we often need to estimate a sum such as the one in (19.1) but with vectors ϕ_{r} that are not quite orthogonal. It is therefore fortunate that we can extend Bessel’s inequality to arbitrary vectors ϕ_{r} with a constant that we can characterize in terms of the extent that the inner product matrix [(ϕ_{r}, ϕ_{s})] resembles the identity matrix.

Theorem 19.1 Let ϕ_{1}, ϕ_{2}, …, ϕ_{R} be arbitrary vectors in an inner product space V. For nonnegative real numbers Δ, the following three assertions are equivalent:

(i) For every vector ξ ∈ V,

(19.3)  ∑_{r=1}^{R} |(ξ, ϕ_{r})|^{2} ≤ Δ^{2}∥ξ∥^{2};

(ii) For every vector ξ ∈ V and every vector y ∈ ℂ^{R},

(19.4)  | ∑_{r=1}^{R}(ξ, ϕ_{r})y_{r}| ≤ Δ∥ξ∥( ∑_{r=1}^{R} |y_{r}|^{2})^{1/2}.

(iii) For every vector y ∈ ℂ^{R},

(19.5)  ∑_{r=1}^{R} ∑_{s=1}^{R}(ϕ_{r}, ϕ_{s})y_{r}\overline{y_{s}} ≤ Δ^{2} ∑_{r=1}^{R} |y_{r}|^{2} .

This contains Bessel’s inequality as a special case, for if the ϕ_{r} happen to be orthonormal, then the inequality (19.5) holds as an identity with Δ = 1, and then (19.3) is Bessel’s inequality. The coefficient matrix C = [(ϕ_{r}, ϕ_{s})] in (19.5)is Hermitian, and so by Corollary F.11 the best constant Δ for which the inequality (19.5) holds is the modulus of the largest eigenvalue of C. This quantity is known as the spectral radius of C; in symbols, Δ = ρ(C).

Proof (i) ⟹ (ii). By Cauchy’s inequality,

| ∑_{r=1}^{R}(ξ, ϕ_{r})y_{r}| ≤ ( ∑_{r=1}^{R} |(ξ, ϕ_{r})|^{2})^{1/2}( ∑_{r=1}^{R} |y_{r}|^{2})^{1/2} .

We apply the bound (19.3) to the first sum on the right above to obtain (19.4). (ii) ⟹ (iii). Take ξ = ∑_{r=1}^{R} y_{r}ϕ_{r}. Then

(19.6)  ∑_{r=1}^{R} ∑_{s=1}^{R}(ϕ_{r}, ϕ_{s})y_{r}\overline{y_{s}} = ∥ξ∥^{2} .

But

∥ξ∥^{2} = ∑_{s=1}^{R}(ξ, ϕ_{s})\overline{y_{s}} ≤ Δ∥ξ∥( ∑_{s=1}^{R} |y_{s}|^{2})^{1/2}

by (19.4). If ξ = 0, then the left hand side of (19.5) is 0, so there is nothing to prove. Otherwise, ∥ξ∥ > 0, so we may cancel ∥ξ∥ from both sides above, and then square both sides. This gives (19.5), in view of (19.6). (iii) ⟹ (i). We take the proof of Bessel’s inequality as a model. For arbitrary y_{r},

0 ≤ ∥ξ − ∑_{r=1}^{R} y_{r}ϕ_{r}∥^{2} = ∥ξ∥^{2} − 2ℜ ∑_{r=1}^{R} \overline{y_{r}}(ξ, ϕ_{r}) + ∥ ∑_{r=1}^{R} y_{r}ϕ_{r}∥^{2} .

Here the last term is

∑_{r=1}^{R} ∑_{s=1}^{R}(ϕ_{r}, ϕ_{s})y_{r}\overline{y_{s}} .

Thus by (iii) we see that

0 ≤ ∥ξ∥^{2} − 2ℜ ∑_{r=1}^{R} \overline{y_{r}}(ξ, ϕ_{r}) + Δ^{2} ∑_{r=1}^{R} |y_{r}|^{2} .

By taking y_{r} = (ξ, ϕ_{r})/Δ^{2} we find that

0 ≤ ∥ξ∥^{2} − \frac{1}{Δ^{2}} ∑_{r=1}^{R} |(ξ, ϕ_{r})|^{2},

which gives (i). □

If the ϕ_{r} are nearly orthonormal in the sense that the inner product matrix C is nearly the identity matrix, then we would expect that (19.3) holds with a constant not much larger than 1. The most immediate observation in this direction is as follows.

Theorem 19.2 In the notation of Theorem 19.1, the inequalities (19.3)–(19.5) hold with

(19.7)  Δ^{2} = max_{1≤r≤R} ∑_{s=1}^{R} |(ϕ_{r}, ϕ_{s})| .

Proof By the arithmetic–geometric mean inequality we know that |y_{r}y_{s}| ≤ \frac{1}{2}|y_{r}|^{2}+ \frac{1}{2}|y_{s}|^{2}. Thus

∑_{r=1}^{R} ∑_{s=1}^{R}(ϕ_{r}, ϕ_{s})y_{r}\overline{y_{s}} ≤ ∑_{r=1}^{R} ∑_{s=1}^{R} |(ϕ_{r}, ϕ_{s})y_{r}\overline{y_{s}}|

≤ ∑_{r=1}^{R} |y_{r}|^{2} ∑_{s=1}^{R} |(ϕ_{r}, ϕ_{s})|

≤ ( max_{1≤r≤R} ∑_{s=1}^{R} |(ϕ_{r}, ϕ_{s})|) ∑_{r=1}^{R} |y_{r}|^{2} .

Thus (19.5) holds with Δ as in (19.7), so the proof is complete. □

Of the various situations in which near orthogonality occurs, we select three for detailed treatment.

1. Trigonometric polynomials. If we need to know that a trigonometric polynomial is not often large, then we might seek a bound for

∑_{r=1}^{R} | ∑_{n=1}^{N} c_{n}e(nx_{r})|^{2}

where the x_{r} are well-spaced (mod 1). Here we take ξ = (c_{n}) ∈ ℂ^{N}, and the ϕ_{r} = (e(−nx_{r})) ∈ ℂ^{N} are nearly orthogonal if ∥x_{r} − x_{s}∥ is large compared with 1/N whenever r ≠ s.

2. Arithmetic progressions. If we want to understand how some numbers c_{n} are distributed when n is restricted to various arithmetic progressions a_{r} (mod q_{r}), then we might seek a bound for the expression

∑_{r=1}^{R} | ∑_{\begin{matrix}n=1 \\ n≡a_{r} (q_{r}) \end{matrix}}^{N} c_{n} − \frac{1}{q_{r}} ∑_{n=1}^{N} c_{n}|^{2}.

Here ξ = (c_{n}) ∈ ℂ^{N} and the ϕ_{r} = (ϕ_{r n}) ∈ ℂ^{N} given by

ϕ_{r n} = \{ \begin{matrix}1 − 1/q_{r} & if n ≡ a_{r} (mod q_{r}) \\ −1/q_{r} & otherwise \end{matrix}

are nearly orthogonal if the q_{r} are pairwise coprime.

3. Character sums. In order to show that a character sum is not too large on average, we might seek a bound for the expression

∑_{r=1}^{R} | ∑_{n=1}^{N} c_{n}χ_{r}(n)|^{2}

where the χ_{r} run over a family of Dirichlet characters. Then we take ξ = (c_{n}) ∈ ℂ^{N}, and we expect the ϕ_{r} = (\overline{χ_{r}}(n)) ∈ ℂ^{N} to be nearly orthogonal if \overline{χ_{r}}χ_{s} is nonprincipal whenever r ≠ s.

The desired approximate orthogonality is a little elusive in the second two cases above, but is easy to establish in the first. Thus we start by treating trigonometric polynomials, and then derive information concerning arithmetic progressions by means of the finite Fourier transform, and for characters by means of Gauss sums.

19.1.1 Exercises

1. The object of this exercise is to derive Theorem 19.1 as an application of the duality principle of Theorem F.1. Let e_{1}, e_{2}, …, e_{K} be an orthonormal basis for W = span(ϕ_{1}, ϕ_{2}, …, ϕ_{R}), and write

ϕ_{r} = ∑_{k=1}^{K} a_{rk}e_{k}

(a) Show that

∑_{r=1}^{R} ∑_{s=1}^{R}(ϕ_{r}, ϕ_{s})y_{r}\overline{y_{s}} = ∥ ∑_{r=1}^{R} y_{r}ϕ_{r}∥^{2} = ∑_{k=1}^{K} | ∑_{r=1}^{R} a_{rk}y_{r}|^{2} .

(b) Put v_{k} = (ξ, e_{k}), and define ζ so that

ξ = ζ + ∑_{k=1}^{K} v_{k}e_{k} .

Thus ζ ∈ W^{⊥}. Show that

(ξ, ϕ_{r}) = ∑_{k=1}^{K} \overline{a_{rk}} v_{k} .

(c) Deduce that

∑_{r=1}^{R}(ξ, ϕ_{r})y_{r} = ∑_{r=1}^{R} ∑_{k=1}^{K} \overline{a_{rk}}y_{r}v_{k},

and also that

∑_{r=1}^{R} |(ξ, ϕ_{r})|^{2} = ∑_{r=1}^{R} | ∑_{k=1}^{K} \overline{a_{rk}}v_{k}|^{2} .

(d) Show that

∑_{k=1}^{K} |v_{k}|^{2} ≤ ∥ξ∥^{2}.

(e) Use Theorem F.1 to prove Theorem 19.1.

2. The object of this exercise is to use Theorem 19.1 to prove Theorem F.1. Let ξ = (x_{1}, x_{2}, …, x_{N}) ∈ ℂ^{N}, and for r = 1, 2, …, R take ϕ_{r} = (a_{r1}, a_{r2}, …, a_{rN}).

(a) Explain why

∑_{r=1}^{R} |(ξ, ϕ_{r})|^{2} = ∑_{r=1}^{R} | ∑_{n=1}^{N} a_{rn}x_{n}|^{2} .

(b) Show that

∑_{r=1}^{R}(ξ, ϕ_{r})y_{r} = ∑_{r=1}^{R} ∑_{n=1}^{N} a_{rn}x_{n}y_{r} .

(c) Explain why

∥ ∑_{r=1}^{R} y_{r}ϕ_{r}∥^{2} = ∑_{n=1}^{N} | ∑_{r=1}^{R} a_{rn}y_{r}|^{2} .

(d) Use Theorem 19.1 to prove Theorem F.1.

3. (Selberg, unpublished; cf Bombieri 1971) Let ϕ_{1}, ϕ_{2}, …, ϕ_{R} be elements of an inner product space V.

(a) Show that for any ξ ∈ V,

∑_{r=1}^{R} |(ξ, ϕ_{r})|^{2}( ∑_{s=1}^{R} |(ϕ_{r}, ϕ_{s})|)^{−1} ≤ ∥ξ∥^{2} .

(b) Use the above to derive Theorem 19.2.

4. Let ϕ_{1}, ϕ_{2}, …, ϕ_{R} and ψ_{1}, ψ_{2}, …, ψ_{S} be any members of an inner product space V. Show that

∑_{r=1}^{R} ∑_{s=1}^{S} |(ϕ_{r}, ψ_{s})|^{2} ≤ ( ∑_{r_{1}=1}^{R} ∑_{r_{2}=1}^{R} |(ϕ_{r_{1}}, ϕ_{r_{2}})|^{2})^{1/2}( ∑_{s_{1}=1}^{S} ∑_{s_{2}=1}^{S} |(ψ_{s_{1}}, ψ_{s_{2}})|^{2})^{1/2}.

19.2 Trigonometric polynomials

Let

(19.8)  T (x) = ∑_{n=M+1}^{M+N} c_{n}e(nx)

be a trigonometric polynomial. Suppose that δ > 0, and that the points x_{r} are well-spaced (mod 1) in the sense that

(19.9)  ∥x_{r} − x_{s}∥ ≥ δ

whenever r ≠ s. We seek an inequality of the form

(19.10)  ∑_{r=1}^{R} |T (x_{r})|^{2} ≤ Δ ∑_{n=M+1}^{M+N} |c_{n}|^{2},

which is to hold for all possible choices of the c_{n}. Our object is to determine how Δ must depend on N and δ. When R = 1 it is easy to establish an inequality of this form, since by Cauchy’s inequality

(19.11)  |T (x_{1})|^{2} ≤ N ∑_{n=M+1}^{M+N} |c_{n}|^{2}.

This is best possible, for if c_{n} = e(−nx_{1}), then T (x_{1}) = N. Thus if (19.10) holds for all c_{n}, then Δ ≥ N. We also observe that

∫_{0}^{1} ∑_{r=1}^{R} |T (x + r/R)|^{2} dx = R ∫_{0}^{1} |T (x)|^{2} dx = R ∑_{n=M+1}^{N} |c_{n}|^{2}.

Hence there is an x for which

∑_{r=1}^{R} |T (x + r/R)|^{2} ≥ R ∑_{n=M+1}^{N} |c_{n}|^{2}.

For any given δ > 0 we can choose R = [1/δ], and then the points x + r/R satisfy (19.9). Hence if Δ satisfies (19.10), then Δ ≥ R ≥ 1/δ − 1.

We now show that (19.10) holds with a value of Δ not much larger than necessitated by the above considerations. Our first result in this direction is somewhat inferior, but the approach is very direct, and generalizes usefully to other situations. For each r let 𝔐_{r} = (x_{r} − δ/2, x_{r} + δ/2) be a short interval centred at x_{r}. We note that if the x_{r} satisfy (19.9), then the intervals 𝔐_{r} are disjoint (mod 1). The idea is that |T (x_{r})|^{2} approximately the average of |T (x)|^{2} over 𝔐_{r} unless T′(x) is very large, in which case the integral of |T′(x)|^{2} over 𝔐_{r} is large. To put this intuitive principle on a sound footing we prove Lemma 19.3 If f′(x) is continuous on [−a, a], then

|f(0)| ≤ \frac{1}{2a} ∫_{−a}^{a} |f(x)| dx + \frac{1}{2} ∫_{−a}^{a} |f′(x)| dx.

Proof By integration by parts we see that

∫_{0}^{a} f(x) dx = f(x)(x − a)|_{0}^{a} − ∫_{0}^{a} f′(x)(x − a) dx = af(0) − ∫_{0}^{a} f′(x)(x − a) dx,

and similarly that

∫_{−a}^{0} f(x) dx = f(x)(x + a)|_{−a}^{0} − ∫_{−a}^{0} f′(x)(x + a) dx = af(0) − ∫_{−a}^{0} f′(x)(x + a) dx.

On summing we deduce that

2af(0) = ∫_{−a}^{a} f(x) dx + ∫_{−a}^{0} f′(x)(x + a) dx + ∫_{0}^{a} f′(x)(x − a) dx.

Hence by the triangle inequality

|f(0)| ≤ \frac{1}{2a} ∫_{−a}^{a} |f(x)| dx + \frac{1}{2a} ∫_{−a}^{0} |f′(x)(x + a)| dx + \frac{1}{2a} ∫_{0}^{a} |f′(x)(x − a)| dx.

Since |x + a| ≤ a for −a ≤ x ≤ 0 and |x − a| ≤ a for 0 ≤ x ≤ a, this gives the result. □

Suppose that U(x) is a trigonometric polynomial of the special form

U(x) = ∑_{k=−K}^{K} b_{k}e(kx).

By applying the Lemma with f(x) = U(x + x_{r})^{2}, a = δ/2, and summing, we deduce that

∑_{r=1}^{R} |U(x_{r})|^{2} ≤ \frac{1}{δ} ∑_{r=1}^{R} ∫_{𝔐_{r}} |U(x)|^{2} dx + ∑_{r=1}^{R} ∫_{𝔐_{r}} |U(x)U′(x)| dx

≤ \frac{1}{δ} ∫_{0}^{1} |U(x)|^{2} dx + ∫_{0}^{1} |U(x)U′(x)| dx

since the intervals 𝔐_{r} are non-overlapping (mod 1). Here the first integral is ∑ |b_{k}|^{2}. By the Cauchy–Schwarz inequality the second integral is

≤ ( ∫_{0}^{1} |U(x)|^{2} dx)^{1/2}( ∫_{0}^{1} |U′(x)|^{2} dx)^{1/2} = ( ∑_{−K}^{K} |b_{k}|^{2})^{1/2}( ∑_{−K}^{K} |2πikb_{k}|^{2})^{1/2}.

Since |2πik| ≤ 2πK for −K ≤ k ≤ K, the above is ≤ 2πK ∑ |b_{k}|^{2}. That is,

∑_{r=1}^{R} | ∑_{k=−K}^{K} b_{k}e(kx_{r})|^{2} ≤ (\frac{1}{δ} + 2πK) ∑_{k=−K}^{K} |b_{k}|^{2}.

This is a special case of (19.10). To obtain the general case let K = [N/2], put L = K + M + 1, and set U(x) = T (x)e(−Lx). Then U(x) is of the required shape, |U(x)| = |T (x)|, and 2K ≤ N, so we have proved Theorem 19.4 Suppose that M and N are integers, N ≥ 1, and that T (x) is a trigonometric polynomial as given in (19.8). Suppose that δ > 0, and that the points x_{r} are well-spaced in the sense that (19.9) holds. Then

∑_{r=1}^{R} |T (x_{r})|^{2} ≤ (\frac{1}{δ} + πN) ∑_{n=M+1}^{M+N} |c_{n}|^{2}.

For purposes of estimating character sums, the above estimate is perfectly satisfactory, but when dealing with arithmetic progressions the coefficient of N on the right hand side becomes important. To optimize this dependence we adopt a different line of attack. The quantity to be estimated is a bilinear form in the coefficients c_{n}. Often when presented with the problem of estimating a bilinear form we simply expand, take the outer summation inside, and estimate the resulting innermost sum:

∑_{r=1}^{R} | ∑_{n=M+1}^{M+N} c_{n}e(nx_{r})|^{2} = ∑_{m=M+1}^{M+N} ∑_{n=M+1}^{M+N} c_{m}\overline{c_{n}} ∑_{r=1}^{R} e((m − n)x_{r}).

Unfortunately, we have little control over the inner sum on the right, so this approach, in its most direct form, leads nowhere. However, every bilinear form inequality has a dual, and we have the option of passing to the dual before performing the above manipulations. More precisely, by Theorem F.1 we see that the inequality (19.10) holds for all choices of the c_{n} if and only if

(19.12)  ∑_{n=M+1}^{M+N} | ∑_{r=1}^{R} y_{r}e(nx_{r})|^{2} ≤ Δ ∑_{r=1}^{R} |y_{r}|^{2}

for all y_{r}. On expanding and taking the sum over n inside we find that the above is

∑_{r=1}^{R} ∑_{s=1}^{R} y_{r}\overline{y_{s}} ∑_{n=M+1}^{M+N} e(n(x_{r} − x_{s})).

By applying (18.30) to estimate the innermost sum we could demonstrate that Δ ≤ N + O(δ^{−1} log δ^{−1}), which is good for N but inferior for δ. The extra logarithm results from the the inverse first power decay of the exponential sum, which in turn is attributable to the jump discontinuity of the characteristic function χ_{ℐ}(x) of the interval ℐ = [M + 1, M + N]. To obtain an exponential sum that decays faster, we introduce a smooth weighting factor.

Theorem 19.5 Suppose that M and N are integers, N ≥ 1, and that T (x) is a trigonometric polynomial as given by (19.8). Suppose that 0 < δ ≤ 1, and that the points x_{r} are well-spaced in the sense that (19.9) holds. Then

∑_{r=1}^{R} |T (x_{r})|^{2} ≤ (N + \frac{1}{δ} − 1) ∑_{n=M+1}^{M+N} |c_{n}|^{2}.

Proof If R = 1, then we have the stated result by Cauchy’s inequality, as in (19.11). If R ≥ 2, then δ ≤ 1/2. We proceed to (19.12), but before expanding we introduce a weighting factor w(n). If χ_{ℐ}(n) ≤ w(n) for all n, then the left hand side of (19.12) is

≤ ∑_{n} w(n)| ∑_{r=1}^{R} y_{r}e(nx_{r})|^{2} = ∑_{r=1}^{R} ∑_{s=1}^{R} y_{r}\overline{y_{s}} ∑_{n} w(n)e(n(x_{r} − x_{s})).

Let the innermost sum be W (x_{r} − x_{s}). If w(n) is piecewise linear, then W (x) decays like an inverse square, and by choosing parameters carefully one may show that Δ ≤ N + 2/δ. However, by employing the more sophisticated weighting given in Theorem E.4 we find that we can actually ensure that W (x) = 0 for ∥x∥ ≥ δ, so that the bilinear form above consists only of diagonal terms. Moreover, with this choice of the w(n) we find that W (0) = N − 1 + 1/δ, so the proof is complete. □

In most arithmetic applications of the large sieve, the x_{r} are rational numbers whose denominators are limited in size, as below.

Corollary 19.6 Let M and N be integers, N ≥ 1, and suppose that T (x) is a trigonometric polynomial of the form (19.8). Then for any positive integer Q,

∑_{q=1}^{Q} \begin{matrix}q \\ ∑ & ∗ \\ a=1 \end{matrix} |T (a/q)|^{2} ≤ (N + Q^{2}) ∑_{n=M+1}^{M+N} |c_{n}|^{2}.

Proof If a/q and a′/q′ are distinct rational numbers, then

|\frac{a}{q} − \frac{a′}{q′} | = |\frac{aq′ − a′q}{qq′} | ≥ \frac{1}{qq′}

since aq′ − a′q is a non-zero integer. If q ≤ Q and q′ ≤ Q, then the above is ≥ 1/Q^{2}, so we may apply Theorem 19.5 with δ = 1/Q^{2}. □

19.2.1 Exercises

1. Suppose that f′(x) is continuous for 0 ≤ x ≤ 1. (a) Show that if 0 ≤ x ≤ 1, then

f(x) = ∫_{0}^{1} f(u) du + ∫_{0}^{x} f′(u)u du + ∫_{x}^{1} f′(u)(u − 1) du.

(b) Deduce that

max_{0≤x≤1} |f(x)| ≤ ∫_{0}^{1} |f(u)| du + ∫_{0}^{1} |f′(u)| du.

2. Suppose that f(x, y) has continuous derivatives through the second order on [0, 1]^{2}. (a) Show that if 0 ≤ x ≤ 1 and 0 ≤ y ≤ 1, then

|f(x, y)| ≤ ∫_{0}^{1} ∫_{0}^{1} |f(u, v)| + |f_{1}(u, v)| + |f_{2}(u, v)| + |f_{12}(u, v)| du dv.

(b) Show that

|f(1/2, 1/2)| ≤ ∫_{0}^{1} ∫_{0}^{1} |f(u, v)| + \frac{1}{2}|f_{1}(u, v)| + \frac{1}{2}|f_{2}(u, v)| + \frac{1}{4}|f_{12}(u, v)| du dv.

3. (a) Suppose that ∫_{0}^{∞} f(x) dx is a convergent improper Riemann sum. Show that if f′(x) → 0 as x → ∞, then f(x) → ∞.

(b) Show that if f(x) → 0 as x → ∞ and f′′(x) → 0 as x → ∞, then f′(x) → 0 as x → ∞.

4. Let x_{1}, x_{2}, …, x_{R} be points in 𝕋. For δ > 0 let N_{δ}(x) denote the number r for which ∥x_{r} − x∥ < δ.

(a) Show that

∑_{\begin{matrix}1≤r≤R \\ ∥x_{r}−x∥≤δ/2 \end{matrix}} \frac{1}{N_{δ}(x_{r})} ≤ 1

for all x ∈ 𝕋.

(b) Show that if M and N are integers, N ≥ 1, and T (x) is given by (19.8), then

∑_{r=1}^{R} \frac{|T (x_{r})|^{2}}{N_{δ}(x_{r})} ≤ (\frac{1}{δ} + πN) ∑_{n=M+1}^{M+N} |c_{n}|^{2}

for all δ > 0.

(c) Show that the above includes Theorem 19.2.

5. Let μ be a non-negative measure on 𝕋.

(a) Show that if T (x) is given as in (19.8), and if δ > 0, then

∫_{𝕋} |T (x)|^{2} dμ(x) ≤ ( max_{x∈𝕋} μ((x − δ/2, x + δ/2)))(\frac{1}{δ} + πN) ∑_{n=M+1}^{M+N} |c_{n}|^{2}.

(b) Derive Theorem 19.4 from the above.

6. Suppose that δ > 0 and that the points x_{r} satisfy (19.9). Show that for any y_{r} there is a number θ, −1 ≤ θ ≤ 1 such that

∑_{n=M+1}^{M+N} | ∑_{r=1}^{R} y_{r}e(nx_{r})|^{2} = (N − 1 + \frac{θ}{δ} ) ∑_{r=1}^{R} |y_{r}|^{2}.

7. (Montgomery 1978) Let M and N ≥ 1 be integers, and suppose that T (x) is given by (19.8). For given positive integers Q, X, let Δ = Δ(N, Q, X) be the optimal constant in the inequality

∑_{q∈𝒬} \begin{matrix}q \\ ∑ & ∗ \\ a=1 \end{matrix} |T (a/q)|^{2} ≤ Δ ∑_{n=M+1}^{M+N} |c_{n}|^{2}

where the c_{n} are arbitrary and 𝒬 is a set of X positive integers not exceeding Q. Show that Δ(N, Q, X) ≍ min(N + Q^{2}, X(N + Q)).

8. (Burgess 1971) Let N_{δ}(x) be defined as in Exercise 4, but take the x_{r} to be as in the preceding exercise, namely the points a/q with (a, q) = 1 and q ∈ 𝒬.

(a) Show that if δ = (QX)^{−1}, then

∑_{q∈𝒬} \begin{matrix}q \\ ∑ & ∗ \\ a=1 \end{matrix} N_{δ}(a/q) ≪ QX.

(b) By using Cauchy’s inequality and applying the above and Exercise 4, show that

∑_{q∈𝒬} \begin{matrix}q \\ ∑ & ∗ \\ a=1 \end{matrix} |T (a/q)| ≪ (QX(N + QX) ∑_{n=M+1}^{M+N} |c_{n}|^{2})^{1/2}.

19.3 Mean square distribution in arithmetic progressions

Suppose that we have a sequence of numbers c_{n} for M +1 ≤ n ≤ M +N. We now consider how these numbers are distributed when n falls in various arithmetic progressions. Let

(19.13)  Z(q, h) = ∑_{\begin{matrix}n=M+1 \\ n≡h (q) \end{matrix}}^{M+N} c_{n}.

If T (x) is given as in (19.8), then

T (a/q) = ∑_{h=1}^{q} Z(q, h)e(ah/q),

and hence by the orthogonality of the additive characters (mod q) (or, in other words, Parseval’s identity for the finite Fourier transform, as we treated in §4.1) it follows that

∑_{a=1}^{q} |T (a/q)|^{2} = q ∑_{h=1}^{q} |Z(q, h)|^{2}.

In Corollary 19.6 the a (mod q) are restricted to reduced residue classes, so some alteration is required before we can appeal to that estimate. To that end, put

(19.14)  Z = Z(1, 0) = T (0) = ∑_{n=M+1}^{M+N} c_{n}.

Thus the average of the Z(q, h) is Z/q. It is natural to consider the mean square difference of the Z(q, h) from its mean (called the ‘variance’ in probability theory). We note that

∑_{h=1}^{q} |Z(q, h) − Z/q|^{2} = ∑_{h=1}^{q} |Z(q, h)|^{2} − 2ℜ\frac{\overline{Z}}{q} ∑_{h=1}^{q} Z(q, h) + \frac{|Z|^{2}}{q} .

Here the second sum on the right hand side is Z, so the above is

(19.15)  = ∑_{h=1}^{q} |Z(q, h)|^{2} − \frac{|Z|^{2}}{q} = \frac{1}{q} ∑_{a=1}^{q} |T (a/q)|^{2} − \frac{|T (0)|^{2}}{q} = \frac{1}{q} ∑_{a=1}^{q−1} |T (a/q)|^{2}.

This is a step in the right direction, since now the a are restricted to non-zero residue classes (mod q). Moreover, if q is prime, then the reduced residue classes and the non-zero residue classes coincide. This permits us to prove

Theorem 19.7 Let 𝒩 be a set of Z integers in the interval [M + 1, M + N]. Let Z(q, h) denote the number of n ∈ 𝒩 such that n ≡ h (mod q). Then for any positive integer Q,

∑_{p≤Q} p ∑_{h=1}^{p}(Z(p, h) − Z/p)^{2} ≤ (N + Q^{2})Z.

Proof Take c_{n} = 1 if n ∈ 𝒩, and c_{n} = 0 otherwise. In (19.15), replace q by p, sum over p ≤ Q, and then apply Corollary 19.6. □

From the above estimate we see that most of the numbers Z(p, h) are near their mean, Z/p. In particular, we note the following consequence.

Corollary 19.8 Let 𝒩 be a set of Z integers in the interval [M + 1, M + N]. Choose τ, 0 < τ ≤ 1, and let 𝒫 denote the set of primes p ≤ Q such that Z(p, h) = 0 for at least τp residue classes h (mod p). Put P = card(𝒫). Then

Z ≤ \frac{N + Q^{2}}{τP} .

Here we at last see how the large sieve got its name: We are estimating how many integers remain in an interval after a large amount of sifting has been done. We find, not surprisingly, that Z must be small if P is large, and vice versa.

Proof If p ∈ 𝒫, then the inner sum in Theorem 19.7 is (Z/p)^{2} for at least τp values of h. Hence the prime p contributes at least τZ^{2} to the left hand side, so we see that

τP Z^{2} ≤ (N + Q^{2})Z.

If Z = 0, then there is nothing to prove. Otherwise Z > 0, and we may cancel Z from both sides to obtain the stated inequality. □

To exemplify the sorts of arithmetic applications that these tools might find, we apply Corollary 19.8 to show that the least quadratic non-residue of a prime p > 2 is not often very large. For an odd prime p, let n_{2}(p) denote the least positive quadratic non-residue. The distribution of this quantity is quite easy to determine: We first observe that n_{2}(p) is a prime number, for if n_{2}(p) = ab, then (\frac{ab}{p}) = −1, and hence (\frac{a}{p}) = −1 or (\frac{b}{p}) = −1. We note by quadratic reciprocity that n_{2}(p) = 2 if p ≡ ±1 (mod 8), which by the prime number theorem for arithmetic progressions is the case for asymptotically 1/2 of the primes p. Also, n_{2}(p) = 3 if (\frac{2}{p}) = 1 and (\frac{3}{p}) = −1. That is, either p ≡ 3 (mod 8) and (\frac{p}{3}) = 1 or if p ≡ 5 (mod 8) and (\frac{p}{3}) = −1. Hence n_{2}(p) = 3 for asymptotically 1/4 of the primes. Let p_{1} < p_{2} < p_{3} < … be the prime numbers listed in increasing order. Then by continuing in this way we see that n_{2}(p) = p_{k} for asymptotically 2^{−k} of the primes. Using the Siegel-Walfisz theorem (Corollary 11.19) to the modulus q = 4 ∏_{j=1}^{k} p_{j} < e^{(1+ε)k log k}, we can state this quantitatively:

(19.16)  card\{p ≤ x : n_{2}(p) = p_{k}\} = \frac{li x}{2^{k}} + O(x exp(−c\sqrt{log x}))

for p_{k} ≪ log log x. For somewhat larger k we can appeal to the Brun–Titchmarsh inequality (Theorem 3.9). Thus we see that

(19.17)  card\{p ≤ x : n_{2}(p) ≥ p_{k}\} ≪ \frac{x}{2^{k} log x}

uniformly for p_{k} ≤ \frac{1}{2} log x. The presumption that this bound might hold for still larger p_{k} suggests the conjecture that

(19.18)  n_{2}(p) ≤ (1 + o(1))(log p) log log p

for all odd primes p. This is stronger than the bound we derived from the Generalized Riemann Hypothesis (cf Theorem 13.11). To bound the frequency with which n_{2}(p) might be larger, we employ Corollary 19.8.

Theorem 19.9 Let a be fixed, a > 2. The number of primes p ≤ x for which n_{2}(p) > (log p)^{a} is < x^{2/a+o(1)}.

Proof We apply Corollary 19.8 with N = Q^{2}, 𝒩 = {n ∈ [1, N] : p|n ⇒ p < (log Q/2)^{a}}, and 𝒫 = {p ∈ (Q/2, Q] : n_{2}(p) > (log p)^{a}}. Thus if n ∈ 𝒩 and p ∈ 𝒫, then all the prime factors of n are so small that they are quadratic residues (mod p), and hence (\frac{n}{p}) = 1. Hence Z(p, h) = 0 for at least (p + 1)/2 residue classes h (mod p), and so we may take τ = 1/2. By Corollary 7.9 we know that Z = N^{1−1/a+o(1)}. Consequently P ≪ N^{1/a+o(1)} = Q^{2/a+o(1)}. To complete the proof it suffices to set Q = 2^{−j}x and sum over j = 0, 1, 2, . . .. □

We recall from Chapter 9 that Vinogradov’s Hypothesis asserts that n_{2}(p) ≪_{ε} p^{ε} for all ε > 0. Although this has not yet been proved for all p, we can use the above method to show that any possible exceptions are exceedingly rare.

Theorem 19.10 (Linnik) If δ > 0, then the number of primes p ≤ x for which n_{2}(p) > p^{δ} is ≪_{δ} log log x.

Proof Let 𝒫 be the set of primes p, Q^{1/2} < p ≤ Q, for which n_{2}(p) > p^{δ}. We show that P ≪_{δ} 1; then the stated result follows on summing over Q = x^{1/2^{j}}. Put N = Q^{2}, and let 𝒩 be the set of integers n, 1 ≤ n ≤ N, composed entirely of prime numbers not exceeding N^{δ/4}. As in the preceding proof we may take τ = 1/2 in Corollary 19.8. By Dickman’s theorem (Theorem 7.2) we know that Z ≫_{δ} N. Hence by Corollary 19.8 we see that P ≪_{δ} 1, and the proof is complete. □

Since we have determined the distribution function of the n_{2}(p), and have also shown that large values of n_{2}(p) are rare, we can deduce that a moment of the n_{2}(p) tends to the moment of the distribution function.

Theorem 19.11 (Erdős) Suppose that δ ≥ 0 is chosen so that n_{2}(p) < p^{δ+ε} for all p > p_{0}(ε). Let γ be a fixed real number such that γ < 1/δ. Then

(19.19)  ∑_{2<p≤x} n_{2}(p)^{γ} ∼ c(γ)π(x)

as x tends to infinity, where

c(γ) = ∑_{k=1}^{∞} p_{k}^{γ}/2^{k}.

From (19.19) it is easy to deduce that n_{2}(p) ≪ p^{1/γ}, so it is to be expected that we can prove (19.19) only under the assumption that γ < 1/δ. By our remarks following Theorem 9.27 we may take δ = 1/(4\sqrt{e}). Thus it follows that (19.19) holds for all γ < 4\sqrt{e} = 6.59 . . ..

Proof By (19.16) we see that the primes p ≤ x for which n_{2}(p) ≤ log log x contribute to the left hand side of (19.19) an amount that is asymptotic to the right hand side of (19.19). Thus it remains to show that those p for which n_{2}(p) is larger make a smaller contribution. Suppose that log log x < p_{k} ≤ \frac{1}{2} log x. By (19.17) we see that the number of p ≤ x for which n_{2}(p) = p_{k} is ≪ 2^{−k}π(x). On summing this over the appropriate range of k we obtain a contribution that is o(π(x)). Next suppose that \frac{1}{2} log x < p_{k} ≤ (log x)^{C} where C is to be determined later. By (19.17) we see that the number of p ≤ x for which n_{2}(p) falls in this range is ≪ x exp(−c(log x)/ log log x). The maximum contribution made by such a prime is (log x)^{C}. Since the product of these last two quantities is o(π(x)) this suffices. Finally consider primes p for which n_{2}(p) > (log x)^{C}. By Theorem 19.9 the number of such primes is < x^{2/C+ε}. The maximum contribution made by such a prime is < x^{γ(δ+ε)}. Hence the total contribution by all such primes is < x^{γ(δ+ε)+2/C+ε}. Now γδ < 1, so we may choose ε > 0 so small that γ(δ +ε) ≤ 1−3ε. If we take C = 2/ε, then the contribution in question is < x^{1−ε} = o(π(x)), so the proof is complete. □

Suppose that we try to use Theorem 19.7 as a small sieve. For example, suppose that 𝒩 = {p : N^{1/2} < p ≤ N} and that Q = N^{1/2}. Then Z(p, 0) = 0 for all p ≤ Q, and hence we obtain the estimate

Z ≪ \frac{N}{∑_{p≤Q} 1/p} ≪ \frac{N}{log log N} ,

which is vastly inferior to the bounds we obtained by Selberg’s method (cf Theorem 3.3). Of course the log log N arises because the sum is restricted to primes. If we were able to sum over all q ≤ Q, then we might expect to get a bound O(N/ log N), comparable to our prior estimates. We now show that this can be done.

Lemma 19.12 For M + 1 ≤ n ≤ M + N let the numbers c_{n} be given. For each prime p let 𝒟(p) be the collection of those residue classes d (mod p) for which c_{n} = 0 whenever n ≡ d (mod p). Let δ(p) = card 𝒟(p), and let ℛ(p) be the complementary set of p − δ(p) residue classes (mod p). For general q let ℛ(q) be the collection of those residue classes r (mod q) such that r ∈ ℛ(p) for all p|q. Put r(q) = card ℛ(q). Finally, let T (x), Z(q, h), and Z be defined as in (19.8), (19.13), and (19.14). If q is squarefree, then

(19.20)  \begin{matrix}q \\ ∑ & ∗ \\ a=1 \end{matrix} |T (a/q)|^{2} = |Z|^{2} ∏_{p|q} \frac{δ(p)}{p − δ(p)} + \begin{matrix}q \\ ∑ & ∗ \\ a=1 \end{matrix} | ∑_{r∈ℛ(q)} e(ar/q)(Z(q, r) − Z/r(q))|^{2}.

We think of the residue classes 𝒟(p) as being deleted, so that ℛ(q) is the set of residue classes that remain.

Proof We first show that if k ∈ ℛ(q), then

(19.21)  ∑_{h∈ℛ(q)} c_{q}(h − k) = ∏_{p|q} δ(p)

where c_{q}(n) is Ramanujan’s sum. By Theorem 4.1, the left hand side above is

∑_{h∈ℛ(q)} ∑_{\begin{matrix}d|q \\ d|(h−k) \end{matrix}} dμ(q/d) = ∑_{d|q} dμ(q/d) ∑_{\begin{matrix}h∈ℛ(q) \\ h≡k (d) \end{matrix}} 1.

In the inner sum, h (mod p) is fixed if p|d, but is free take on any value in ℛ(p) if p ∤ d. Thus there are ∏_{p|q/d}(p − δ(p)) such h, and hence the expression above is

= ∑_{d|q} dμ(q/d) ∏_{p|q/d} (p − δ(p)) = ∏_{p|q} (p − (p − δ(p))),

and so we have (19.21).

To establish (19.20) we expand the second term on the right hand side, and find that it is

\begin{matrix}q \\ ∑ & ∗ \\ a=1 \end{matrix} | ∑_{h∈ℛ(q)} Z(q, h)e(ah/q)|^{2} − 2ℜ\frac{\overline{Z}}{r(q)} \begin{matrix}q \\ ∑ & ∗ \\ a=1 \end{matrix} ∑_{h∈ℛ(q)} Z(q, h) ∑_{k∈ℛ(q)} e(a(h − k)/q)

+ \frac{|Z|^{2}}{r(q)^{2}} \begin{matrix}q \\ ∑ & ∗ \\ a=1 \end{matrix} | ∑_{h∈ℛ(q)} e(ah/q)|^{2}

= T_{1} − 2ℜT_{2} + T_{3},

say. Clearly T_{1} is equal to the left hand side of (19.20). By taking the sum over a inside and applying (19.21) we see that

T_{2} = \frac{\overline{Z}}{r(q)} ∑_{h∈ℛ(q)} Z(q, h) ∏_{p|q} δ(p) = \overline{Z}( ∏_{p|q} \frac{δ(p)}{p − δ(p)}) ∑_{h∈ℛ(q)} Z(q, h) = |Z|^{2} ∏_{p|q} \frac{δ(p)}{p − δ(p)}.

Finally, we see that

T_{3} = \frac{|Z|^{2}}{r(q)^{2}} ∑_{k∈ℛ(q)} ∑_{h∈ℛ(q)} c_{q}(h − k),

which by (19.21) is

= \frac{|Z|^{2}}{r(q)^{2}} ∑_{k∈ℛ(q)} ∏_{p|q} δ(p).

The number of terms in the sum is r(q), so

T_{3} = |Z|^{2} ∏_{p|q} \frac{δ(p)}{p − δ(p)}.

On combining these observations we obtain (19.20), and the proof is complete. □

Theorem 19.13 Let 𝒩 be a set of Z integers in the interval M + 1 ≤ n ≤ M + N. For each prime p let δ(p) denote the number of residue classes (mod p) not represented by any member n ∈ 𝒩. Then for any integer Q ≥ 1,

Z ≤ \frac{N + Q^{2}}{L}

where

L = ∑_{q≤Q} μ^{2}(q) ∏_{p|q} \frac{δ(p)}{p − δ(p)}.

Precisely the same estimate can be obtained by Selberg’s λ^{2} method, if Theorem E.4 is used to eliminate the non-diagonal terms (see Exercise 5 below).

Proof By Lemma 19.12 it is clear that

(19.22)  \begin{matrix}q \\ ∑ & ∗ \\ a=1 \end{matrix} |T (a/q)|^{2} ≥ Z^{2}μ^{2}(q) ∏_{p|q} \frac{δ(p)}{p − δ(p)}.

We sum this over q ≤ Q and apply Corollary 19.6 to see that

Z^{2}L ≤ (N + Q^{2})Z.

If Z = 0, then there is nothing to prove. If Z > 0, then we cancel Z from both sides to obtain the stated inequality. □

19.3.1 Exercises

1. Let 𝒬 be a set of pairwise coprime positive integers not exceeding Q, suppose that T (x) is given as in (19.8), and that Z(q, h) is defined by (19.13).

(a) Show that

∑_{q∈𝒬} ∑_{a=1}^{q−1} |T (a/q)|^{2} ≤ (N + Q^{2}) ∑_{n=M+1}^{M+N} |c_{n}|^{2}.

(b) Show that

∑_{q∈𝒬}q ∑_{h=1}^{q} |Z(q, h) − Z/q|^{2} ≤ (N + Q^{2}) ∑_{n=M+!}^{M+N} |c_{n}|^{2}.

(c) Show that this includes Theorem 19.7.

2. Let ℛ(p) and δ(p) be defined as in Lemma 19.12. Show that if q is squarefree, then

∑_{h=1}^{q} ( ∏_{\begin{matrix}p|q \\ h∈ℛ(p) \end{matrix}} \frac{δ(p)}{p − δ(p)})^{2} = q ∏_{p|q} \frac{δ(p)}{p − δ(p)}.

3. Let T (x) be defined as in (19.8), and Z(q, h) be defined as in (19.13). Put f(a) = T (a/q) if (a, q) = 1, f(a) = 0 otherwise. Let f̂(h) = \frac{1}{q} ∑_{a=1}^{q} f(a)e(−ah/q) be the finite Fourier transform of f.

(a) Show that

f̂(h) = \frac{1}{q} ∑_{d|q} μ(q/d)dZ(d, h).

(b) Deduce that

\begin{matrix}q \\ ∑ & ∗ \\ a=1 \end{matrix} |T (a/q)|^{2} = \frac{1}{q} ∑_{h=1}^{q} | ∑_{d|q} μ(q/d)dZ(d, h)|^{2}.

4. Let w_{±}(n) be defined as in Theorem E.4. Show that if q ≤ 1/δ, then

∑_{n≡a (q)} w_{±}(n) = W_{±}(0)/q

for all a (mod q).

5. Let w_{+} and W_{+} be as in Theorem E.4, let f(x) be a polynomial with integral coefficients, and let δ(p) denote the number of solutions of the congruence f(x) ≡ 0 (mod p). Suppose that λ_{d} is real and subject to the conditions λ_{1} = 1, λ_{d} = 0 for d > z. Assume that P is a positive squarefree integer.

(a) Explain why

(19.23)  ∑_{\begin{matrix}n=M+1 \\ (f(n),P)=1 \end{matrix}}^{M+N} 1 ≤ ∑_{\begin{matrix}n \\ (f(n),P)=1 \end{matrix}} w_{+}(n) ≤ ∑_{n} w_{+}(n)( ∑_{\begin{matrix}d|f(n) \\ d|P \end{matrix}} λ_{d})^{2}.

(b) Show that if q is squarefree, then

∑_{\begin{matrix}n \\ q|f(n) \end{matrix}} w_{+}(n) = W_{+}(0)\frac{δ(q)}{q}

if q ≤ 1/δ, where δ(q) = ∏_{p|q} δ(p).

(c) Explain why it may be assumed that δ(p) > 0 for all p|P.

(d) Set δ = z^{−2}, and show that the right hand side of (19.23) is

(19.24)  = (N − 1 + z^{2}) ∑_{\begin{matrix}d_{i}|P \\ d_{i}≤z \\ i=1,2 \end{matrix}} \frac{λ_{d_{1}}δ(d_{1})}{d_{1}} \frac{λ_{d_{2}}δ(d_{2})}{d_{2}} \frac{(d_{1}, d_{2})}{δ((d_{1}, d_{2}))}.

(e) Put g(q) = ∏_{p|q}(p − δ(p))/δ(p). Show that if q is squarefree, then

∑_{d|q} g(d) = \frac{q}{δ(q)}.

(f) Show that the right hand side of (19.24) is

(19.25)  = (N − 1 + z^{2}) ∑_{\begin{matrix}q|P \\ q≤z \end{matrix}} g(q)y_{q}^{2}

where

(19.26)  y_{q} = ∑_{\begin{matrix}d \\ q|d|P \\ d≤z \end{matrix}} \frac{λ_{d}δ(d)}{d}.

(g) Show that if the y_{q} are given as above, then

(19.27)  λ_{d} = \frac{d}{δ(d)} ∑_{\begin{matrix}q \\ d|q|P \\ q≤z \end{matrix}} μ(q/d)y_{q}.

(h) Show that the y_{q} are real, that y_{q} = 0 if q > z, and that

∑_{\begin{matrix}q|P \\ q≤z \end{matrix}} μ(q)y_{q} = 1.

(i) Show that configurations of y_{q} with the properties described in the preceding part are in one-to-one correspondence with admissible choices of the λ_{d}.

(j) Show that the sum in (19.25) is

= ∑_{\begin{matrix}q|P \\ q≤z \end{matrix}} g(q)(y_{q} − \frac{μ(q)}{g(q)L})^{2} + \frac{1}{L}

where

L = ∑_{\begin{matrix}q|P \\ q≤z \end{matrix}} \frac{μ^{2}(q)}{g(q)}.

(k) Show that y_{q} = μ(q)/(g(q)L) is an admissible choice of the y_{q}, and hence deduce that

card\{n ∈ [M + 1, M + n] : (f(n), P) = 1\} ≤ \frac{N − 1 + z^{2}}{L} .

(l) Show that for each prime p a set 𝒟(p) of δ(p) residue classes is given. Show that there is a polynomial f(x) such that if p|P, then f(x) ≡ 0 (mod p) if and only if x ∈ 𝒟(p).

6. (The ‘Larger Sieve’ of Gallagher 1971) Let 𝒩 be a subset of Z of the integers in an interval [M + 1, M + N], and let Z(q, h) denote the number of n ∈ 𝒩 such that n ≡ h (mod q). For any primepower q let r(q) denote the number of h (mod q) for which Z(q, h) > 0.

(a) Explain why

Z^{2} = ( ∑_{h=1}^{q} Z(q, h))^{2} ≤ r(q) ∑_{h=1}^{q} Z(q, h)^{2}.

(b) Let 𝒬 be a finite set of primepowers. Deduce that

Z^{2} ∑_{q∈𝒬} \frac{Λ(q)}{r(q)} ≤ ∑_{q∈𝒬}Λ(q) ∑_{\begin{matrix}n_{1},n_{2}∈𝒬 \\ n_{1}≡n_{2} (q) \end{matrix}} 1.

(c) Group pairs n_{1}, n_{2} of members of 𝒩 according to their common difference, and hence show that the right hand side above is

= ∑_{d=−N+1}^{N−1} ∑_{\begin{matrix}n_{1},n_{2}∈𝒩 \\ n_{1}−n_{2}=d \end{matrix}} ∑_{\begin{matrix}q∈𝒬 \\ q|d \end{matrix}} Λ(q).

(d) Show that

∑_{d≠0} ∑_{\begin{matrix}n_{1},n_{2}∈𝒩 \\ n_{1}−n_{2}=d \end{matrix}} 1 = Z^{2} − Z.

(e) Deduce that the expression in (c) is

≤ Z ∑_{q∈𝒬}Λ(q) + (Z^{2} − Z) log N.

(f) Conclude that

Z ≤ \frac{∑_{q∈𝒬} Λ(q) − log N}{∑_{q∈𝒬} Λ(q)/r(q) − log N}

provided that the denominator is positive.

19.4 Character sums

Let

(19.28)  S(χ) = ∑_{n=M+1}^{M+N} c_{n}χ(n).

We recall (cf Theorem 9.7) that if χ is a primitive character (mod q), then χ(n) can be expressed in a simple way in terms of the additive characters e(an/q), namely

(19.29)  τ(\overline{χ})χ(n) = ∑_{a=1}^{q} \overline{χ}(a)e(an/q)

for all n. On multiplying by c_{n} and summing, we see that

τ(\overline{χ})S(χ) = ∑_{a=1}^{q} \overline{χ}(a)T (a/q)

where T (x) is defined as in (19.8). Since |τ(χ)| = \sqrt{q} for all primitive χ, on taking the modulus-squared and summing over primitive χ it follows that

q \begin{matrix}∑ & ∗ \\ χ \end{matrix} |S(χ)|^{2} = \begin{matrix}∑ & ∗ \\ χ \end{matrix} | ∑_{a=1}^{q} \overline{χ}(a)T (a/q)|^{2}

where ∑_{χ}^{∗} denotes a sum over all primitive characters (mod q). On the right hand side we drop the condition that χ be primitive, and invoke the orthogonality of characters (as expressed in (4.14)) to see that the above is

≤ φ(q) \begin{matrix}q \\ ∑ & ∗ \\ a=1 \end{matrix} |T (a/q)|^{2}

where ∑_{a}^{∗} denotes a sum over reduced residue classes a (mod q). On combining this with Corollary 19.6 we obtain Theorem 19.14 Let M and N be integers with N ≥ 1, and let S(χ) be defined as in (19.28). Then for any integer Q ≥ 1,

∑_{q≤Q} \frac{q}{φ(q)} \begin{matrix}∑ & ∗ \\ χ \end{matrix} |S(χ)|^{2} ≤ (N + Q^{2}) ∑_{n=M+1}^{M+N} |c_{n}|^{2}

where ∑_{χ}^{∗} denotes a sum over all primitive characters χ (mod q).

19.4.1 Exercises

1. Let χ_{1} be a primitive character (mod q_{1}), and suppose that q_{1} ≤ N. Set c_{n} = \overline{χ}_{1}(n) for all n. Show that

S(χ_{1}) = ∑_{n=M+1}^{M+N} |c_{n}|^{2} ≍ Nφ(q_{1})/q_{1},

and hence that

\frac{q_{1}}{φ(q_{1})}|S(χ_{1})|^{2} ≍ N ∑_{n=M+1}^{M+N} |c_{n}|^{2}

for this particular choice of the c_{n}.

2. (a) Show that

∫_{0}^{1} | ∑_{n=M+1}^{M+N} e(nθ)χ(n)|^{2} dθ = ∑_{\begin{matrix}n=M+1 \\ (n,q)=1 \end{matrix}}^{M+N} 1 ≍ Nφ(q)/q

if q ≤ N.

(b) Show that

∑_{q≤Q} \begin{matrix}∑ & ∗ \\ χ \end{matrix} 1 ≍ Q^{2}.

(c) Deduce that there exist unimodular c_{n} such that

∑_{q≤Q} \begin{matrix}∑ & ∗ \\ χ \end{matrix} |S(χ)|^{2} ≍ Q^{2}N

if Q ≤ N.

3. Recall that (19.29) holds for all χ if (n, q) = 1.

(a) Show that if c_{n} = 0 whenever (n, q) > 1, then

∑_{χ} |τ(χ)|^{2}|S(χ)|^{2} = φ(q) \begin{matrix}q \\ ∑ & ∗ \\ a=1 \end{matrix} |T (a/q)|^{2}.

(b) Suppose that c_{n} = 0 whenever n has a prime factor ≤ Q. Show that

∑_{q≤Q} \frac{1}{φ(q)} ∑_{χ} |τ(χ)|^{2}|S(χ)|^{2} ≤ (N + Q^{2}) ∑_{n=M+1}^{M+N} |c_{n}|^{2}.

(c) Suppose that c_{n} = 0 whenever (n, q) > 1, and that the character χ (mod q) is induced by the primitive character χ^{∗} (mod d). Show that S(χ) = S(χ^{∗}). Recall also that τ(χ) = τ(χ^{∗})μ(q/d) if (q/d, d) = 1 and that τ(χ) = 0 otherwise.

(d) Show that if the c_{n} are as in (b), then

∑_{q≤Q} \frac{q}{φ(q)}( \begin{matrix}∑ & ∗ \\ χ \end{matrix} |S(χ)|^{2})( ∑_{\begin{matrix}k≤Q/q \\ (k,q)=1 \end{matrix}} \frac{μ(k)^{2}}{φ(k)} ) ≤ (N + Q^{2}) ∑_{n=M+1}^{M+N} |c_{n}|^{2}.

(e) Show that if the c_{n} are as in (b), then

∑_{q≤Q} ( log Q/q) \begin{matrix}∑ & ∗ \\ χ \end{matrix} |S(χ)|^{2} ≤ (N + Q^{2}) ∑_{n=M+1}^{M+N} |c_{n}|^{2}.

(f) Let 𝒩 be the set of those integers n ∈ [M + 1, M + N] such that (n, q) = 1 for all q ≤ Q. Put Z = card 𝒩. Show that

Z^{2} log Q + ∑_{1<q≤Q} ( log Q/q) \begin{matrix}∑ & ∗ \\ χ \end{matrix} | ∑_{n∈𝒩} χ(n)|^{2} ≤ (N + Q^{2})Z.

4. (a) Use results from Chapter 9 as appropriate to show that if χ is a primitive character (mod q) and (k, q) = 1, then

∑_{\begin{matrix}a=1 \\ (a,qk)=1 \end{matrix}}^{qk} \overline{χ}(a)e(an/(qk)) = \overline{χ}(k)χ(n)τ(\overline{χ})c_{k}(n)

where c_{k}(n) is Ramanujan’s sum.

(b) Show that

∑_{\begin{matrix}q,k \\ qk≤Q \\ (q,k)=1 \end{matrix}} \frac{q}{φ(qk)} ^{∑∗} | ∑_{n=M+1}^{M+N} c_{n}χ(n)c_{k}(n)|^{2} = ∑_{\begin{matrix}q,k \\ qk≤Q \\ (q,k)=1 \end{matrix}} \frac{1}{φ(qk)} ^{∑∗} | ∑_{\begin{matrix}a=1 \\ (a,qk)=1 \end{matrix}}^{qk} \overline{χ}(a)T (a/(qk))|^{2}|^{2}.

(c) Explain why

∑_{\begin{matrix}q,k \\ qk≤Q \end{matrix}} \frac{1}{φ(qk)} ^{∑∗} | ∑_{\begin{matrix}a=1 \\ (a,qk)=1 \end{matrix}}^{qk} \overline{χ}(a)T (a/(qk))|^{2}|^{2} = ∑_{q≤Q} \frac{1}{φ(q)} ∑_{χ} | ∑_{a=1}^{q} \overline{χ}(a)T (a/q)|^{2}

= ∑_{q≤Q} \begin{matrix}q \\ ∑ & ∗ \\ a=1 \end{matrix} |T (a/q)|^{2}.

(d) (Selberg; cf p. 27 of Bombieri 1974) Conclude that

∑_{\begin{matrix}q,k \\ qk≤Q \\ (q,k)=1 \end{matrix}} \frac{q}{φ(qk)} \begin{matrix}∑ & ∗ \\ χ \end{matrix} | ∑_{n=M+1}^{M+N} c_{n}χ(n)c_{k}(n)|^{2} ≤ (N + Q^{2}) ∑_{n=M+1}^{M+N} |c_{n}|^{2}.

(e) Show that this includes both part (d) of the preceding Exercise and also Theorem 19.14 as special cases.

5. (Erdős & Shapiro 1957) Let χ be a primitive character modulo q. (a) Show that

∑_{m=1}^{q} χ(m + n_{1})\overline{χ}(m + n_{2}) = c_{q}(n_{1} − n_{2})

where c_{q} is Ramanujan’s sum, as defined in (4.5).

(b) Deduce that for arbitrary numbers b_{n},

∑_{m=1}^{q} | ∑_{n=1}^{q} b_{n}χ(m + n)|^{2} = ∑_{\begin{matrix}a=1 \\ (a,q)=1 \end{matrix}}^{q} | ∑_{n=1}^{q} b_{n}e(an/q)|^{2} .

(c) Explain why the right hand side above is

≤ q ∑_{n=1}^{q} |b_{n}|^{2} . (19.30)

(d) Show that

| ∑_{m=1}^{q} ∑_{n=1}^{q} a_{m}b_{n}χ(m + n)|^{2} ≤ \sqrt{q}( ∑_{m=1}^{q} |a_{m}|^{2})^{1/2}( ∑_{n=1}^{q} |b_{n}|^{2})^{1/2}

for arbitrary numbers a_{m} and b_{n}.

(e) Show that equality holds in (19.30) if b_{n} = e(cn/q) with (c, q) = 1.

(f) Show that equality holds in (19.30) if b_{n} = χ(n).

(g) Compare the results here with those of Exercise F.2.15.

24 The Large Sieve