Large Sieve and Bombieri-Vinogradov

LARGE SIEVE AND BOMBIERI–VINOGRADOV THEOREM NICK HARLAND 1. INTRODUCTION Let pi(x; q; a) be the number of primes in an arithmetic progression up to x. More specifically, it is the cardinality of the set {p | p prime, p ≡ a (mod q), p ≤ x}. Notationally we can write this as pi(x; q; a) = ∑ p≡a (mod q) p≤x 1, where it’s understood that for the purposes of this paper that p will always denote a prime. A similar function is ψ(x; q; a) = ∑ n≤x n≡a (mod q) Λ(n), where Λ(n) = { log p n = pk 0 otherwise. Facts about the number of primes in an arithmetic progression can often be more easily studied by looking at the function ψ(x; q; a) rather than pi(x; q; a), and we can use Euler Summation to go from the latter to the former. The prime number theorem for arithmetic progressions asserts that for (a, q) = 1 and q ≤ logA x we have (see [6, Corollary 11.19]) ψ(x; q; a) = x φ(q) +OA ( x log−A x ) for any constant A. The error term, however is quite far from what we would expect. For example under the Generalized Riemann Hypothesis, we get that for (a, q) = 1, (see [6, Corollary 13.8]) ψ(x; q; a) = x φ(q) +O (√ x log2 x ) . (1) The Bombieri–Vinogradov Theorem is an unconditional result which says that while for any spe- cific q, the error term might be large, on average over a certain range, the error term resembles that of (1). That is over a sum of q ≤ Q, we should get that the error is Qx1/2log2x. We will get something close to that by proving the following theorem Theorem 1. [Bombieri–Vinogradov] Let A > 0 be fixed, and let E(x; q, a) = ψ(x; q; a) − x φ(q) . Then ∑ q≤Q max (a,q)=1 |E(x; q, a)| �A x log−A x, (2) where Q = x1/2 log−B x, for B = 2A+ 8. 1 Most proofs of the theorem involve the Large Sieve which we’ll start by discussing below. 2. THE ADDITIVE LARGE SIEVE A sieve in number theory is one meant to take a set S of natural numbers, and ”sift out” all the numbers lying in another set Ωp modulo primes p. For example the Sieve of Eratosthenes eliminates all numbers congruent to 0 modulo p except p itself. What’s left are the primes. Recall the notation e(z) = e2piiz which will be used in the following corollary as well as throughout the rest of the paper. The following is taken from [4, Chapter 7] We’ll start by proving the following, called the additive large sieve. Theorem 2. Let an be complex numbers, M and N be natural numbers with n ∈ {M + 1, ...,M + N}. Then we have the following ∑ q≤Q q∑ a=1 (a,q)=1 ∣∣∣∣ M+N∑ n=M+1 ane ( an q )∣∣∣∣ ≤ (Q2 +N − 1)‖~a‖2, (3) where ‖~a‖ = ∑ i |ai|2. The idea behind the proof is that we want to show if numbers are not too close together, then the sum in (3) can’t get too large. Then we use that the rational numbers are spaced out well enough. Note that the reason we call it the ”additive” large sieve is the use of the additive characters in the sum. In order to prove Theorem 2 we’ll need some preliminary definitions and lemmas. Before we get into our first lemma, recall the Cauchy–Schwartz inequality which we will use repeatedly.∣∣∣∣ n∑ i=1 xiy¯i ∣∣∣∣2 ≤ n∑ i=1 |xi|2 n∑ i=1 |yi|2 (4) We want to start with some lemmas first. They will be useful as we will have some double sums that we want to separate into cases where the indexes are equal to each other and where they are not. The next few lemmas are going to help treat the case where the indexes are not equal. Our first lemma is due to Montgomery and Vaughan [5] and is a generalization of the Hilbert Inequality. Lemma 3. Suppose λr are a finite collection of distinct real numbers with |λr − λs| ≥ δ if r 6= s for 0 < δ < 1 2 . Then for any complex numbers zr we have∣∣∣∣∑ (r,s) r 6=s zrzs λr − λs ∣∣∣∣ ≤ piδ ∑ r |zr|2. (5) Proof. First note that without loss of generality, we can order the λr such that λ1 < λ2 < ... and so we can replace the condition |λr − λs| ≥ δ with the condition |λr − λs| ≥ δ|r− s|. We’ll begin by proving ∑ r ∣∣∣∣∑ r 6=s zs λr − λs ∣∣∣∣2 ≤ pi2δ2 ∑ r |zr|2. (6) Note that 2 ∣∣∣∣∑ s f(s) ∣∣∣∣2 = (∑ s f(s) )(∑ t f(t) ) = (∑ s f(s) )(∑ t f(t) ) = ∑ s ∑ t f(s)f(t), so ∑ r ∣∣∣∣∑ r 6=s zs λr − λs ∣∣∣∣2 = ∑ (s,t) zszt ∑ r 6=s,t 1 (λr − λs)(λr − λt) , noting that there are no conjugates on the λ as they are real, we now separate the sum into two pieces based on whether s = t or s 6= t. The first sum is ∑ s |zs|2 ∑ r 6=s 1 (λr − λs)2 , while the second is ∑ (s,t) s 6=t zszt ∑ r 6=s,t 1 (λr − λs)(λr − λt) = ∑ (s,t) s 6=t zszt λs − λt ∑ r 6=s,t ( 1 λr − λs − 1 λr − λt ) = ∑ (s,t) s 6=t zszt λs − λt [∑ r 6=s 1 λr − λs − ∑ r 6=t 1 λr − λt + 2 λs − λt ] . Now as we sum over all s, t we notice that the two inner sums will cancel each other. Hence we are left with ∑ (s,t) s 6=t zszt λs − λt [ 2 λs − λt ] = ∑ (s,t) s 6=t 2zszt (λs − λt)2 . Now by using 2|zszt| ≤ |zs|2 + |zt|2, we get∣∣∣∣∑ (s,t) s 6=t 2zszt (λs − λt)2 ∣∣∣∣ ≤∑ s ∑ t6=s |zs|2 + |zt|2 (λs − λt)2 = 2 ∑ s |zs|2 ∑ t6=s 1 (λs − λt)2 , where the last equality is due to the pair (i, j) occurring once as s = i, t = j and once as s = j, t = i. Therefore we get ∑ r ∣∣∣∣∑ r 6=s zs λr − λs ∣∣∣∣2 = ∑ s |zs|2 ∑ r 6=s 1 (λr − λs)2 + 2 ∑ s |zs|2 ∑ t6=s 1 (λs − λt)2 = 3 ∑ s |zs|2 ∑ r 6=s 1 (λr − λs)2 . Since |λr − λs| ≥ δ|r − s|, we get 3 3 ∑ s |zs|2 ∑ r 6=s 1 (λr − λs)2 ≤ 3 δ2 ∑ s |zs|2 ∑ r 6=s 1 (r − s)2 ≤ 3 δ2 ∑ s |zs|2 ( 2 ∞∑ n=1 1 n2 ) = 6 δ2 pi2 6 ∑ s |zs|2 = pi2 δ2 ∑ s |zs|2. By Cauchy–Schwartz (4) we get ∣∣∣∣∑ (r,s) r 6=s zrzs λr − λs ∣∣∣∣2 ≤∑ r |zr|2 ∑ r ∣∣∣∣∑ (r,s) r 6=s zs λr − λs ∣∣∣∣2 ≤∑ r |zr|2 ( pi2 δ2 ∑ s |zs|2 ) = ( pi δ ∑ r |zr|2 )2 which implies our theorem. � We will also need the following identity in order to help with the next lemma. The proof of it will require Liousville’s Theorem in complex analysis. Lemma 4. If z is a complex number with z /∈ Z, then 1 z + 2z ∞∑ k=1 (−1)k z2 − k2 = pi sin piz . Proof. First note from the power series expansion that sin piz has simple zeros at k ∈ Z. Also note that lim z→k pi(z − k) sin piz = lim z→k pi pi cospiz = (−1)k so pi sinpiz has simple poles at k ∈ Z with residue (−1)k. Hence if we let S = 1 z + 2z ∞∑ k=1 (−1)k z2 − k2 = limK→∞ K∑ k=−K (−1)k k − z , we get that pi sinpiz − S is an entire function. It’s clear that as |z| → ∞ away from the integers, that S is bounded. Also sin z = eiz − e−iz 2i which is bounded away from 0 as long as z is not near pik for integer k, since as |Im(z)| → ∞ ⇒ |sin z| → ∞, and as |Re(z)| → ∞ for Im(z) = b 6= 0 we get |sin z| = lim |a|→∞ e−beia − ebe−ia 2i . 4 If this went to 0, then |e−beia| → |ebe−ia| However that implies eb = e−b which is impossible for b 6= 0. Hence sin z is bounded away from zero making pi sinpiz − S a bounded entire function. By Liousville’s Theorem in complex analysis, that means that pi sinpiz − S is constant. Hence pi sin piz − 1 z = C + 2z ∞∑ k=1 (−1)k z2 − k2 , so taking limits as z → 0 yields C = lim z→0 pi sin piz − 1 z = lim z→0 piz − sin piz z sinpiz = lim z→0 pi − pi cos piz sin piz + piz cos piz = lim z→0 pi2 sinpiz 2picospiz − z sin piz = 0. Hence C = 0 yielding our identity. � Lemma 3 yields some corollaries. Note that our summations are involving sine functions which are part of the definition of e(z). Corollary 5. If zr are complex numbers and αr ∈ R/Z with |αr − αs| ≥ δ, for 0 < δ < 12 , then∣∣∣∣∑ (r,s) r 6=s zrzs sin pi(αr − αs) ∣∣∣∣ ≤ δ−1∑ r |zr|2. Proof. Using Lemma 3 with the values zm,r = (−1)mzr and λm,r = m + αr for 1 ≤ m ≤ K, we get ∣∣∣∣ ∑ (r,m),(s,n) (r,m) 6=(s,n) (−1)m−n zrzs m− n+ αr − αs ∣∣∣∣ = ∣∣∣∣ ∑ (r,m),(s,n) (r,m)6=(s,n) zm,rzn,s λm,r − λn,s ∣∣∣∣ ≤ pi δ ∑ r |zm,r|2 ≤ piK δ ∑ r |zr|2, noting that the δ hasn’t changed since adding an integer or multiplying by (−1) won’t effect the spacing. Now if r = s we note that the term in the sum for m = i, n = j is (−1)i−j |zr| 2 i− j = −(−1) j−i |zr|2 j − i which is the negative of the term for m = j, n = i. Therefore they cancel out in the sum and hence the condition (r,m) 6= (s, n) can be simply replaced by r 6= s. Therefore we have 5 pi δ ∑ r |zr|2 ≥ 1 K ∣∣∣∣ ∑ r,s,m,n r 6=s (−1)m−n zrzs m− n+ αr − αs ∣∣∣∣ = ∣∣∣∣∑ r,s r 6=s zrzs K∑ k=−K N(k) K (−1)k k + αr − αs ∣∣∣∣ where N(k) is the number of pairs (m,n) with 1 ≤ m,n ≤ K such that m − n = k. Clearly N(k) = K − |k| and so we get pi δ ∑ r |zr|2 ≥ ∣∣∣∣∑ r,s r 6=s zrzs K∑ k=−K ( 1− |k| K ) (−1)k k + αr − αs ∣∣∣∣. By letting K →∞ and using Lemma 4 we get pi δ ∑ r |zr|2 ≥ ∣∣∣∣∑ r,s r 6=s pizrzs sin pi(αr − αs) ∣∣∣∣ yielding our corollary. � Now the previous corollary leads directly to Corollary 6. For any real number x, complex numbers zr and αr ∈ R/Z with |αr − αs| ≥ δ for 0 < δ < 1 2 , we have ∣∣∣∣∑ (r,s) r 6=s zrzs sin 2pix(αr − αs) sin pi(αr − αs) ∣∣∣∣ ≤ δ−1∑ r |zr|2. Proof. Using Lemma 5 with z′r = zre(xαr) and z ′′ r = zre(−xαr) and noticing that |z′′r | = |z′r| = |zr| we get ∣∣∣∣∑ (r,s) r 6=s zrzse(xαr − xαs) sin pi(αr − αs) ∣∣∣∣ ≤ δ−1∑ r |zr|2 and ∣∣∣∣∑ (r,s) r 6=s zrzse(−xαr + xαs) sin pi(αr − αs) ∣∣∣∣ ≤ δ−1∑ r |zr|2. Now using that e(z)− e(−z) = 2i sin(2piz) we get 6 ∣∣∣∣∑ (r,s) r 6=s zrzs sin 2pix(αr − αs) sin pi(αr − αs) ∣∣∣∣ = ∣∣∣∣∑ (r,s) r 6=s zrzs ( e(x(αr − αs))− e(x(αr − αs)) ) 2 sinpi(αr − αs) ∣∣∣∣ ≤ ∣∣∣∣∑ (r,s) r 6=s zrzse(xαr − xαs) 2 sinpi(αr − αs) ∣∣∣∣+ ∣∣∣∣∑ (r,s) r 6=s zrzse(−xαr + xαs) 2 sinpi(αr − αs) ∣∣∣∣ ≤ δ−1 ∑ r |zr|2. � Now we show the Duality Lemma. It allows us to interchange the order of summation. This will allow us to sum over the residues first in our theorem as opposed to over the n which will be useful. Lemma 7. Given a function φ(m,n). Suppose for any complex numbers βn we have∑ m ∣∣∣∣∑ n βnφ(m,n) ∣∣∣∣2 ≤ ∆‖~β‖2 (7) then for any complex numbers αn we get∑ n ∣∣∣∣∑ m αmφ(m,n) ∣∣∣∣2 ≤ ∆‖~α‖2. Proof. If we let βn = ∑ m αmφ(m,n), then ∑ n ∣∣∣∣∑ m αmφ(m,n) ∣∣∣∣2 = ∑ n (∑ m αmφ(m,n) )(∑ m′ αm′φ(m′, n) ) = ∑ n ∑ m αmβnφ(m,n) = ∑ m αm ∑ n βnφ(m,n). Now let this sum be Φ(m,n) then using Cauchy–Schwartz (4) we get, |Φ(m,n)|2 ≤ ∑ m |αm|2 ∑ m ∣∣∣∣∑ n βnφ(m,n) ∣∣∣∣2 ≤ ∆‖~α‖2‖~β‖2 by hypothesis (7). However note that Φ(m,n) = ∑ n ∣∣∣∣∑ m αmφ(m,n) ∣∣∣∣2 = ∑ n |βn|2 = ‖~β‖2 and so we are left with 7 Φ(m,n) ≤ ∆‖~α‖2 as needed. � We require one more lemma. It will use the duality lemma and the additive large sieve will be a simple corollary of it using rational numbers. Lemma 8. For any αr ∈ R/Z with |αr − αs| ≥ δ for 0 < δ < 12 and any complex numbers an with M < n ≤M +N, we have (a) ∑ r ∣∣∣∣ ∑ M 1 (11) We are going to need a technical lemma first. Lemma 17. Let β = (βn) be supported on {1, ..., N}, then for all natural numbers K, s we get∑ d|s d≤K µ(d) ∑ n≡0 (mod d) βnχ(n) = ∑ d|s d≤K µ(d) ∑ l|d µ(l) ∑ (n,l)=1 βnχ(n). Proof. By linearity of the finite sum, it suffices to show it’s true for β(n) = { 1 n = n0 0 otherwise . For this β(n), the left hand side is ∑ d|s d≤K µ(d) { 1 (n0, q) = 1, d | n0 0 otherwise ,