In the previous set of notes, we saw how zero-density theorems for the Riemann zeta function, when combined with the zero-free region of Vinogradov and Korobov, could be used to obtain prime number theorems in short intervals. It turns out that a more sophisticated version of this type of argument also works to obtain prime number theorems in arithmetic progressions, in particular establishing the celebrated theorem of Linnik:

Theorem 1 (Linnik’s theorem)Let be a primitive residue class. Then contains a prime with .

In fact it is known that one can find a prime with , a result of Xylouris. For sake of comparison, recall from Exercise 65 of Notes 2 that the Siegel-Walfisz theorem gives this theorem with a bound of , and from Exercise 48 of Notes 2 one can obtain a bound of the form if one assumes the generalised Riemann hypothesis. The probabilistic random models from Supplement 4 suggest that one should in fact be able to take .

We will not aim to obtain the optimal exponents for Linnik’s theorem here, and follow the treatment in Chapter 18 of Iwaniec and Kowalski. We will in fact establish the following more quantitative result (a special case of a more powerful theorem of Gallagher), which splits into two cases, depending on whether there is an exceptional zero or not:

Theorem 2 (Quantitative Linnik theorem)Let be a primitive residue class for some . For any , let denote the quantityAssume that for some sufficiently large .

- (i) (No exceptional zero) If all the real zeroes of -functions of real characters of modulus are such that , then
for all and some absolute constant .

- (ii) (Exceptional zero) If there is a zero of an -function of a real character of modulus with for some sufficiently small , then
for all and some absolute constant .

The implied constants here are effective.

Note from the Landau-Page theorem (Exercise 54 from Notes 2) that at most one exceptional zero exists (if is small enough). A key point here is that the error term in the exceptional zero case is an *improvement* over the error term when no exceptional zero is present; this compensates for the potential reduction in the main term coming from the term. The splitting into cases depending on whether an exceptional zero exists or not turns out to be an essential technique in many advanced results in analytic number theory (though presumably such a splitting will one day become unnecessary, once the possibility of exceptional zeroes are finally eliminated for good).

Exercise 3Assuming Theorem 2, and assuming for some sufficiently large absolute constant , establish the lower boundwhen there is no exceptional zero, and

when there is an exceptional zero . Conclude that Theorem 2 implies Theorem 1, regardless of whether an exceptional zero exists or not.

Remark 4The Brun-Titchmarsh theorem (Exercise 33 from Notes 4), in the sharp form of Montgomery and Vaughan, gives thatfor any primitive residue class and any . This is (barely) consistent with the estimate (1). Any lowering of the coefficient in the Brun-Titchmarsh inequality (with reasonable error terms), in the regime when is a large power of , would then lead to at least some elimination of the exceptional zero case. However, this has not led to any progress on the Landau-Siegel zero problem (and may well be just a reformulation of that problem). (When is a relatively small power of , some improvements to Brun-Titchmarsh are possible that are not in contradiction with the presence of an exceptional zero; see this paper of Maynard for more discussion.)

Theorem 2 is deduced in turn from facts about the distribution of zeroes of -functions. We first need a version of the truncated explicit formula that does not lose unnecessary logarithms:

Exercise 5 (Log-free truncated explicit formula)With the hypotheses as above, show thatfor any non-principal character of modulus , where we assume for some large ; for the principal character establish the same formula with an additional term of on the right-hand side. (

Hint:this is almost immediate from Exercise 45(iv) and Theorem 21 ofNotes 2) with (say) , except that there is a factor of in the error term instead of when is extremely large compared to . However, a closer inspection of the proof (particularly with regards to the truncated Perron formula in Proposition 12 of Notes 2) shows that the factor can be replaced fairly easily by . To get rid of the final factor of , note that the proof of Proposition 12 used the rather crude bound . If one replaces this crude bound by more sophisticated tools such as the Brun-Titchmarsh inequality, one will be able to remove the factor of .

Using the Fourier inversion formula

(see Theorem 69 of Notes 1), we thus have

and so it suffices by the triangle inequality (bounding very crudely by , as the contribution of the low-lying zeroes already turns out to be quite dominant) to show that

when no exceptional zero is present, and

when an exceptional zero is present.

To handle the former case (2), one uses two facts about zeroes. The first is the classical zero-free region (Proposition 51 from Notes 2), which we reproduce in our context here:

Proposition 6 (Classical zero-free region)Let . Apart from a potential exceptional zero , all zeroes of -functions with of modulus and are such thatfor some absolute constant .

Using this zero-free region, we have

whenever contributes to the sum in (2), and so the left-hand side of (2) is bounded by

where we recall that is the number of zeroes of any -function of a character of modulus with and (here we use conjugation symmetry to make non-negative, accepting a multiplicative factor of two).

In Exercise 25 of Notes 6, the grand density estimate

is proven. If one inserts this bound into the above expression, one obtains a bound for (2) which is of the form

Unfortunately this is off from what we need by a factor of (and would lead to a weak form of Linnik’s theorem in which was bounded by rather than by ). In the analogous problem for prime number theorems in short intervals, we could use the Vinogradov-Korobov zero-free region to compensate for this loss, but that region does not help here for the contribution of the low-lying zeroes with , which as mentioned before give the dominant contribution. Fortunately, it is possible to remove this logarithmic loss from the zero-density side of things:

Theorem 7 (Log-free grand density estimate)For any and , one hasThe implied constants are effective.

We prove this estimate below the fold. The proof follows the methods of the previous section, but one inserts various sieve weights to restrict sums over natural numbers to essentially become sums over “almost primes”, as this turns out to remove the logarithmic losses. (More generally, the trick of restricting to almost primes by inserting suitable sieve weights is quite useful for avoiding any unnecessary losses of logarithmic factors in analytic number theory estimates.)

Now we turn to the case when there is an exceptional zero (3). The argument used to prove (2) applies here also, but does not gain the factor of in the exponent. To achieve this, we need an additional tool, a version of the Deuring-Heilbronn repulsion phenomenon due to Linnik:

Theorem 9 (Deuring-Heilbronn repulsion phenomenon)Suppose is such that there is an exceptional zero with small. Then all other zeroes of -functions of modulus are such thatIn other words, the exceptional zero enlarges the classical zero-free region by a factor of . The implied constants are effective.

Exercise 10Use Theorem 7 and Theorem 9 to complete the proof of (3), and thus Linnik’s theorem.

Exercise 11Use Theorem 9 to give an alternate proof of (Tatuzawa’s version of) Siegel’s theorem (Theorem 62 of Notes 2). (Hint:if two characters have different moduli, then they can be made to have the same modulus by multiplying by suitable principal characters.)

Theorem 9 is proven by similar methods to that of Theorem 7, the basic idea being to insert a further weight of (in addition to the sieve weights), the point being that the exceptional zero causes this weight to be quite small on the average. There is a strengthening of Theorem 9 due to Bombieri that is along the lines of Theorem 7, obtaining the improvement

with effective implied constants for any and in the presence of an exceptional zero, where the prime in means that the exceptional zero is omitted (thus if ). Note that the upper bound on falls below one when for a sufficiently small , thus recovering Theorem 9. Bombieri’s theorem can be established by the methods in this set of notes, and will be given as an exercise to the reader.

Remark 12There are a number of alternate ways to derive the results in this set of notes, for instance using the Turan power sums method which is based on studying derivatives such asfor and large , and performing various sorts of averaging in to attenuate the contribution of many of the zeroes . We will not develop this method here, but see for instance Chapter 9 of Montgomery’s book. See the text of Friedlander and Iwaniec for yet another approach based primarily on sieve-theoretic ideas.

Remark 13When one optimises all the exponents, it turns out that the exponent in Linnik’s theorem isextremelygood in the presence of an exceptional zero – indeed Friedlander and Iwaniec showed can even get a bound of the form for some , which is even stronger than one can obtain from GRH! There are other places in which exceptional zeroes can be used to obtain results stronger than what one can obtain even on the Riemann hypothesis; for instance, Heath-Brown used the hypothesis of an infinite sequence of Siegel zeroes to obtain the twin prime conejcture.

** — 1. Log-free density estimate — **

We now prove Theorem 7. We will make no attempt here to optimise the exponents in this theorem, and so will be quite wasteful in the choices of numerical exponents in the argument that follows in order to simplify the presentation.

By increasing if necessary we may assume that

(say); we may also assume that is larger than any specified absolute constant. We may then replace by in the estimate, thus we wish to show that

Observe that in the regime

the claim already follows from the non-log-free density estimate (4). Thus we may assume that

for some , and the claim is now to show that there are at most zeroes of -functions with , , and a character of modulus . We may assume that , since the case follows from the case (and also essentially follows from the classical zero-free region, in any event).

For minor technical reasons it is convenient to first dispose of the contribution of the principal character. In this case, the zeroes are the same as those of the Riemann zeta function. From the Vinogradov-Korobov zero-free region we conclude there are no zeroes with and . Thus we may restrict attention to non-principal characters .

Suppose we have a zero of a non-principal character of modulus with and . From equation (48) of Notes 2 we then have

(say) for all . One can of course obtain more efficient truncations than this, but as mentioned previously we are not trying to optimise the exponents. If one subtracts the term from the left-hand side, this already gives a zero-detecting polynomial, but it is not tractable to work with because it contains too many terms with small (and is also not concentrated on those that are almost prime). To fix this, we weight the previous Dirichlet polynomial by , where is an arithmetic function supported on to be chosen later obeying the bound . We expand

and hence by (7) and the upper bound on

Since , one sees from the divisor bound and the hypothesis that is large that

If we have , then we can extract the term and obtain a zero-detecting polynomial:

We now select the weights . There are a number of options here; we will use a variant of the “continuous Selberg sieve” from Section 2 of Notes 4. Fix a smooth function that equals on and is supported on ; we allow implied constants to depend on . For any , define

Observe from Möbius inversion that for all . The weight was used as an upper bound Selberg sieve in Notes 4.

We will need the following general bound:

Lemma 14 (Sieve upper bound)Let , and let be a completely multiplicative function such that for all primes . Then

*Proof:* Clearly, we can restrict to those numbers whose prime factors do not exceed , for some large absolute constant .

By a Fourier expansion we can write

for some rapidly decreasing function , and thus the left-hand side of (10) may be written as

where we implicitly restrict to numbers whose prime factors do not exceed (note that this makes the integrand absolutely summable and integrable, so that Fubini’s theorem applies). We may factor this as

By the rapid decrease of , it thus suffices to show that

By Taylor expansion we can bound the left-hand side by

By Mertens theorem we can replace the constraint with . Since , it thus suffices to show that

But we can factor

and the claim follows from Mertens’ theorem.

We record a basic corollary of this estimate:

Corollary 15For any , we have

*Proof:* Writing , we can write the left-hand side of (12) as

Since is supported on and is bounded above by , the contribution of the error is which is acceptable. By Lemma 14 with , the contribution of the main term is , and the claim then follows from Mertens’ theorem.

Now we prove (13). Using Rankin’s trick, it suffices to show that

The left-hand side factorises as

From Lemma 14 with , we see that

(using Mertens theorem to control the error between and ) and the claim follows.

We will work primarily with the cutoff

the reason for the separate scales and will become clearer later. The function is supported on , equals at , and is bounded by , so from the previous discussion we thus have the zero-detector inequality

whenever with of modulus , , and . Our objective is to show that the number of such zeroes is .

We first control the number of zeroes that are very close together. From equation (48) of Notes 2 with (say), we see that

whenever , , and is non-principal of modulus ; also from equation (45) of Notes 2 we have

From Jensen’s theorem (Theorem 16 of Supplement 2), we conclude that for any given non-principal and any , there are at most zeroes of (counting multiplicity, of course) with and . To prove Theorem 7, it thus suffices by the usual covering argument to establish the bound

whenever one has a sequence of zeroes with a non-principal character of conductor , , and , obeying the separation condition

Note from the existing grand zero-density estimate in (4) that

We write (14) for the zeroes as

and

and is a smooth function supported on which equals on . Note that the term in is .

We use the generalised Bessel inequality (Proposition 2 from Notes 3) with to conclude that

where are complex numbers with . (Strictly speaking, one needs to deal with the issue that the are not finitely supported, but there is enough absolute convergence here that this is a routine matter.) From Corollary 15 we have

(note how the logarithmic factors cancel, which is crucial to obtaining our “log-free” estimate) and so from (18), the inequality and symmetry it suffices to show that

We now estimate the expression

From (9), the factor vanishes unless , and from the support of we see that the inner sum vanishes unless . From Exercise 44 of Notes 2, we then have

so we see from (17) and (6) that the contribution of the error term to (19) is acceptable. For the main term in (22), we see from Corollary 15 that

so (as the main term in (22) is independent of ) the remaining contribution to (19) is bounded by

Making the change of variables , this becomes

The integral is bounded by , and from two integration by parts it is also bounded by

On the other hand, for , the are -separated by hypothesis, and so

and the claim follows.

** — 2. Consequences of an exceptional zero — **

In preparation for proving Theorem 9, we investigate in this section the consequences of a Landau-Siegel zero, that is to say a real character of some modulus with a zero

for some with small. For minor technical reasons we will assume that is a multiple of , so that ; this condition can be easily established by multiplying by a principal character of modulus dividing . (We will not need to assume here that is primitive.)

In Notes 2, we already observed that the presence of an exceptional zero was associated with a small (but positive) value of ; indeed, from Lemmas 57 and 59 of Notes 2 we see that

Also, from the class number formula (equation (56) from Notes 2) we have

For the arguments below, one could also use the slightly weaker estimates in Exercise 67 of Notes 2 or Exercise 57 of Notes 3 and still obtain comparable results. We will however *not* rely on Siegel’s theorem (Theorem 62 of Notes 2) in order to keep all bounds effective.

We now refine this analysis. We begin with a complexified version of Exercise 58 from Notes 2:

Exercise 16Let be a non-principal character of modulus . Let with and for some . Show thatfor any . (

Hint:use the Dirichlet hyperbola method and Exercise 44 from Notes 2.)If is a non-principal character of modulus with , show that

For technical reasons it will be convenient to work with a completely multiplicative variant of the function . Define the arithmetic function to be the completely multiplicative function such that for all ; this is equal to at square-free numbers, but is a bit larger at other numbers. Observe that is non-negative, and has the factorisation

where is a multiplicative function that vanishes on primes and obeys the bounds

for all and primes . In particular is non-negative and for , since we assumed . From Euler products we see that

for any , so in particular the Dirichlet series is analytic and uniformly bounded on . (The constraint is needed to ensure convergence of the geometric series.) This implies that

whenever with .

Taking Dirichlet series, we see that

whenever ; more generally, we have

for any character . Now we look at what happens inside the critical strip:

Exercise 17Let be a real character of modulus a multiple of , and let be as above. Let with and for some . Show thatfor any and .

If is a non-principal character of modulus with , show that

for any and .

We record a nice corollary of these estimates due to Bombieri, which asserts that the exceptional zero forces to vanish (or equivalently, to become ) on most large primes:

Lemma 18 (Bombieri’s lemma)Let be a real character of modulus with an exceptional zero at for some sufficiently small . Then for any , we have

Informally, Bombieri’s lemma asserts that for most primes between and . The exponent of here can be lowered substantially with a more careful analysis, but we will not do so here. For primes much larger than , becomes equidistributed; see Exercise 24 below.

*Proof:* Without loss of generality we may take to be a multiple of . We may assume that , as the claim follows from Mertens’ theorem otherwise; in particular .

By (28) for we have

for any . Since and , we see from (25), (27) that the error term is dominated by the main term, thus

Next, applying (30) with replaced by and subtracting, we have

As , we have by Taylor expansion. As before, the error term can be bounded by the main term and so

Since is non-negative and completely multiplicative, one has

and thus (since )

Since , we have , and the claim follows.

Exercise 19With the hypotheses of Bombieri’s lemma, show thatfor any natural number .

Now we can give a more precise version of (24):

Proposition 20Let be a real character of modulus with an exceptional zero at for some sufficiently small . Thenfor any with .

Observe that (24) is a corollary of the case of this proposition thanks to Mertens’ theorem and the trivial bounds . We thus see from this proposition and Bombieri’s lemma that the exceptional zero controls at primes larger than , but that is additionally sensitive to the values of at primes below this range. For an even more precise formula for , see this paper of Goldfeld and Schinzel, or Exercise 25 below.

*Proof:* By Bombieri’s lemma and Mertens’ theorem, it suffices to prove the asymptotic for .

We begin with the upper bound

Applying (26) with and we have

The left-hand side is non-negative and , so we conclude (using (25)) that

From Euler products and Mertens’ theorem we have

But from Lemma 18 and Mertens’ theorem we see that

and the claim follows.

Now we establish the matching lower bound

Applying (26) with and we have

For , we have , and thus by (25)

Inserting this into (31) and using (25) and we conclude that

and the claim then follows from the preceding calculations.

Remark 21One particularly striking consequence of an exceptional zero is that the spacing of zeroes of other -functions become extremely regular; roughly speaking, for most other characters whose conductor is somewhat (but not too much) larger than the conductor of , the zeroes of (at moderate height) mostly lie on the critical line and are spaced in approximate arithmetic progression; this “alternative hypothesis” is in contradiction to to the pair correlation conjecture discussed in Section 4 of Supplement 4. This phenomenon was first discovered by Montgomery and Weinberger and can roughly be explained as follows. By an approximate functional equation similar to Exercise 54 of Supplement 3, one can approximately write as the sum of plus times a gamma factor which oscillates like when . The smallness of on average for medium-sized (as suggested for instance by Bombieri’s lemma) suggests that these sums should be well approximated by much shorter sums, which oscillate quite slowly in . This gives an approximation to that is of the form for slowly varying , which can then be used to place the zeroes of this function in approximate arithmetic progression on the real line.

** — 3. The Deuring-Heilbronn repulsion phenomenon — **

We now prove Theorem 9. Let be such that there is an exceptional zero with small, associated to some quadratic character of modulus :

From the class number bound (equation (56) of Notes 2; one could also use Exercise 67 of Notes 2 for a similar bound) we have

Let , let be a character of modulus (possibly equal to or the principal character), and suppose we have

for some , with . Our task is to show that

(say), since the claim is trivial otherwise. By multiplying by the principal character of modulus if necessary, we may assume as before that is a multiple of , so that we can utilise the multiplicative function from the previous section. By enlarging , we may assume as in Section 1 that

we may also assume that is larger than any specified absolute constant. From the classical zero-free region and the Landau-Page theorem we have

The task (35) is then equivalent to showing that

We recall the sieve cutoffs

from Section 1, which were used in the zero detector. The main difference is that we will “twist” the polynomial by the completely multiplicative function :

Proposition 22 (Zero-detecting polynomial)Let the notation and assumptions be as above.

*Proof:* First suppose that is not equal to or the principal character. Since , we see from (29), (37), (36), (38) that

(say) for any . In particular, as is supported on and one has from the divisor bound, one has

(say), thanks to (36). Since equals for , we thus conclude (40) since is assumed to be large.

Now suppose that is or the principal character, so that . From (28), (37), (36), (38) we then have

for . By a similar calculation to before, we have

where we have used (38) and Proposition 20 in the last line. The claim (41) then follows from Lemma 14.

Using the estimates from the previous section, we can establish the following bound:

The point here is that the sieve weights and are morally restricting to almost primes, and that should be small on such numbers by Bombieri’s lemma. Assuming this proposition, we conclude that the left-hand sides of (40) or (41) are , and (39) follows.

*Proof:* By the Cauchy-Schwarz inequality it suffices to show that

We begin with the second bound (42), which we establish by quite crude estimates. By a Fourier expansion we can write

for some rapidly decreasing function , and thus

Bounding , we thus have

for any . Squaring and using Cauchy-Schwarz, we conclude that

for any . In particular, for , we have

and so we can bound the left-hand side of (43) by

which we bound by

By Mertens’ theorem we have

and the claim follows by taking large enough.

Now we establish (42). By dyadic decomposition it suffices to show that

for all . The left-hand side may be written as as

From the hyperbola method we see that

for any , and thus

Since is supported on and is bounded by , the contribution of the is easily seen to be acceptable (using (33), (37)). The contribution of the main term is

but this is acceptable by Lemma 14, (27), and Proposition 20.

The proof of Theorem 9 is now complete.

Exercise 24Let be a real quadratic character of modulus with a zero at for some small . Show thatand hence

for all and some absolute constant . (

Hint:use (3) and the explicit formula.) Roughly speaking, this exercise asserts that is equidistributed for primes with much larger than .

Exercise 25Let be a real quadratic character of modulus with a zero at for some small . Show thatif is a sufficiently large absolute constant. (

Hint:use Exercise 81, Lemma 40, and Theorem 41 of Notes 1, as well as Exercise 24.

Exercise 26 (Bombieri’s zero density estimate)Under the hypotheses of Theorem 9, establish the estimate (5). (Hint:repeat the arguments in Section 1, but now “twisted” by .)

## 10 comments

Comments feed for this article

22 February, 2015 at 10:51 am

Douglas J. KeenanRegarding Xylouris, he has since shown that the exponent can be reduced to 5. See “Über die Nullstellen der Dirichletschen L-Funktionen und die kleinste Primzahl in einer arithmetischen Progression“. (The link is to his 2011 dissertation.)

[Reference updated, thanks – T.]23 February, 2015 at 1:34 am

AnonymousThe link to Notes 2 (line 2 below theorem 1) is to Xylouris paper.

[Corrected, thanks – T.]24 February, 2015 at 2:58 am

AnonymousConcerning the probabilistic prediction (below theorem 1) that , what is known about the size of this term, and is it possible to eliminate it?

24 February, 2015 at 10:18 am

Terence TaoIn this paper of Granville and Pomerance it is conjectured that the least p should be comparable to , and a lower bound a little bit larger than is established for some . (The problem is similar to Cramer’s conjecture on large prime gaps. Actually, there is a good chance that the recent progress on large prime gaps can be adapted to improve the results of Granville and Pomerance; a graduate research project, perhaps?)

24 February, 2015 at 7:50 am

AnonymousIn the box with Theorem 2, one of the lines containing math sticks into the margin. Maybe moving the last term to the next line will help.

24 February, 2015 at 11:40 am

254A, Supplement 6: A cheap version of the theorems of Halasz and Matomaki-Radziwill (optional) | What's new[…] ingredients are in a similar spirit to the “log-free density theorem” from Theorem 6 of Notes 7. See the Matomaki-Radziwill paper for details (in the non-cheap […]

30 March, 2015 at 12:49 pm

254A, Notes 8: The Hardy-Littlewood circle method and Vinogradov’s theorem | What's new[…] replaced by “log-free” versions (analogous to the log-free zero-density theorems in Notes 7), combined with careful numerical optimisation of constants and also some numerical work on the […]

17 June, 2017 at 9:14 pm

Repelling Numbers | Gaurish4Math[…] important fact in the theory of prime numbers is the Deuring-Heilbronn phenomenon, which roughly says […]

3 August, 2018 at 2:53 am

PrahladI don’t see how the statement just after Remark 4 follows just from the truncated explicit formula as mentioned. The error term should been $O(x\log^2(x)/q^2)$ from the referred exercise.

3 August, 2018 at 7:32 am

Terence TaoAh, right; as with all the other components of the proof of Linnik’s theorem, one needs the log-free version of the truncated explicit formula, which was not quite the one in the referred exercise. Basically one has to replace the somewhat crude analysis in the proof of the truncated Perron formula in those notes with the log-free bound provided by the Brun-Titchmarsh inequality. I’ve now made this formula an exercise.