I’ve just uploaded to the arXiv my paper “The Elliott-Halberstam conjecture implies the Vinogradov least quadratic nonresidue conjecture“. As the title suggests, this paper links together the Elliott-Halberstam conjecture from sieve theory with the conjecture of Vinogradov concerning the least quadratic nonresidue of a prime . Vinogradov established the bound

for any fixed . Unconditionally, the best result so far (up to logarithmic factors) that holds for all primes is by Burgess, who showed that

for any fixed . See this previous post for a proof of these bounds.

In this paper, we show that the Vinogradov conjecture is a consequence of the Elliott-Halberstam conjecture. Using a variant of the argument, we also show that the “Type II” estimates established by Zhang and numerically improved by the Polymath8a project can be used to improve a little on the Vinogradov bound (1), to

although this falls well short of the Burgess bound. However, the method is somewhat different (although in both cases it is the Weil exponential sum bounds that are the source of the gain over (1)) and it is conceivable that a numerically stronger version of the Type II estimates could obtain results that are more competitive with the Burgess bound. At any rate, this demonstrates that the equidistribution estimates introduced by Zhang may have further applications beyond the family of results related to bounded gaps between primes.

The connection between the least quadratic nonresidue problem and Elliott-Halberstam is follows. Suppose for contradiction we can find a prime with unusually large. Letting be the quadratic character modulo , this implies that the sums are also unusually large for a significant range of (e.g. ), although the sum is also quite small for large (e.g. ), due to the cancellation present in . It turns out (by a sort of “uncertainty principle” for multiplicative functions, as per this paper of Granville and Soundararajan) that these facts force to be unusually large in magnitude for some large (with for two large absolute constants ). By the periodicity of , this means that

must be unusually large also. However, because is large, one can factorise as for a fairly sparsely supported function . The Elliott-Halberstam conjecture, which controls the distribution of in arithmetic progressions on the average can then be used to show that is small, giving the required contradiction.

The implication involving Type II estimates is proven by a variant of the argument. If is large, then a character sum is unusually large for a certain . By multiplicativity of , this shows that correlates with , and then by periodicity of , this shows that correlates with for various small . By the Cauchy-Schwarz inequality (cf. this previous blog post), this implies that correlates with for some distinct . But this can be ruled out by using Type II estimates.

I’ll record here a well-known observation concerning potential counterexamples to any improvement to the Burgess bound, that is to say an infinite sequence of primes with . Suppose we let be the asymptotic mean value of the quadratic character at and the mean value of ; these quantities are defined precisely in my paper, but roughly speaking one can think of

and

Thanks to the basic Dirichlet convolution identity , one can establish the *Wirsing integral equation*

for all ; see my paper for details (actually far sharper claims than this appear in previous work of Wirsing and Granville-Soundararajan). If we have an infinite sequence of counterexamples to any improvement to the Burgess bound, then we have

while from the Burgess exponential sum estimates we have

These two constraints, together with the Wirsing integral equation, end up determining and completely. It turns out that we must have

and

and then for , evolves by the integral equation

For instance

and then oscillates in a somewhat strange fashion towards zero as . This very odd behaviour of is surely impossible, but it seems remarkably hard to exclude it without invoking a strong hypothesis, such as GRH or the Elliott-Halberstam conjecture (or weaker versions thereof).

## 21 comments

Comments feed for this article

28 October, 2014 at 4:36 am

AnonymousGreat!Terry,I’m seriously eager to wait Twin prime conjecture solved completely every seconds like in the fire.Once,twin prime conejecuture fell down,next Riemann hypothesis,next strong Goldbach conjecture.Good luck!

28 October, 2014 at 4:47 am

volochI assume the argument only works for real characters, otherwise you’d have stated something more general. Is this correct and do you expect to be able to overcome whatever difficulty there is to extend to arbitrary characters?

28 October, 2014 at 7:49 am

Terence TaoBoth results work for arbitrary characters; the Elliott-Halberstam conjecture would imply that the least n for which chi(n) is not equal to 1 is for any character of prime conductor (and composite conductor would probably be doable too if one is more careful). I guess I should add a remark to that effect in the paper. The second result is already stated in the paper for arbitrary characters: a Type II estimate implies nontrivial character sum bounds beyond Polya-Vinogradov for arbitrary characters.

28 October, 2014 at 10:49 am

volochSo EH implies existence of small primitive roots. That’s worth mentioning.

28 October, 2014 at 12:09 pm

Terence TaoHmm, I hadn’t thought about that angle… my second argument (starting from a Type II hypothesis, which is a special case of a generalised Elliott-Halberstam conjecture) should give a bound on small primitive roots (because it bounds character sums with an arbitrary power of saved), but the first argument (starting from just EH) may be more difficult to adapt, because it only controls characters which are equal to 1 for all small numbers (so that factorises usefully as , allowing one to exploit the EH hypothesis to estimate sums such as ). If has only O(1) prime factors there may be a chance to do something there though; I’ll have to think about it.

28 October, 2014 at 3:35 pm

Terence TaoI think I can use EH to bound the least primitive root by assuming that has a bounded number of factors. What the argument gives directly is that for each non-principal character , that there is an of size such that . Unfortunately depends on and so one does not immediately get a primitive root this way. But with a bit of combinatorics exploiting the multiplicativity of characters and the bounded number of prime factors of p-1, one can show that if there are no small primitive roots, then there is at least one non-principal character for which for all small n, which on taking contrapositives gives the claim. For instance, in the simplest case when has just two prime factors , there are two generating characters . If one has an such that and an such that , then by multiplicativity and so is a generator. So the only way one doesn’t get a small generator is if for all small numbers or for all small numbers (or both). Things get combinatorially more complicated when the group of characters has higher rank, but the same basic argument turns out to work. I’ll put it in the next revision of the ms.

28 October, 2014 at 8:46 am

arch1“means that … to be unusually large” -> “means that … must be unusually large” ?

[Corrected, thanks – T.]28 October, 2014 at 12:36 pm

AnonymousNotes for the first 8 pages of your paper:

– P. 1, l. 7: “follows the” –> “follows from the”

– P. 3, Conj. 1.4, l. 5: Use `\colon’ instead of `:’ for maps

– P. 4, proof of Coro. 1.6, l 3: Use `\coloneqq’ from the mathtools package instead of `:=’

– P. 5, Remark 1.7, l. 9: Use `\coloneqq’ instead of `:=’

– P. 6, l. 9: Use `\colon’ instead of `:’ for maps

– P. 6, Sec. 2, l. 5: “small, e.g. “small, e.g., “”

The typographical comments also apply to the rest of the paper. :-)

[Thanks, these will be corrected in the next revision of the ms. – T.]29 October, 2014 at 1:01 am

2802562155qqcomok great！

30 October, 2014 at 6:28 am

Anonymous– Lemma 2.2: “” –> “” [a smaller space]

– At the end of the proof of Lemma 2.2: “” –> “” [insert a small space]

[This will be addressed in the next revision of the ms. – T.]?29 October, 2014 at 9:37 am

Nikhil BeraDear Prof. Terri Tao,

I’m a post graduate student from India. I have been suffering from a problem from my 1st year graduate courses. I want to do mathematics. But there is some other problem. I sub-consciously turn to find a meaning for life. What does it mean to live a life? We live we die and everything apparently gets finished. Then what does it mean to live a life?Sometimes I tried to find a answer, a logical answer, which will be the most believable to me, but never got a permanent satisfactory answer. Now a days I’m trying ran away from this problem so that I can concentrate in mathematics properly.Please reply to me. Give me a answer please or a motivation to forget this question.

29 October, 2014 at 8:09 pm

ashwin1729I believe anyone who does science comes across this when young.The best thing you can do is to convince yourselves that you don’t have enough tools to attack the problem and leave it for the future.

31 October, 2014 at 6:05 am

Anonymouswhat ashwin basically means is that if you’ve descended from pure mathematics to finding the mere meaning of life (lol) you are probably stuck.

Anyway the answer’s quite simple really……………………………………………..42

I highly recommend you read “The Hitchhiker’s Guide to The Galaxy”- Douglas Adams, and go back to things that first got you interested in maths, read proofs that simply blew your mind again, and read a little biography of the greats – Euler, Gauss etc.

29 October, 2014 at 5:41 pm

AnonymousYou should turn to a psychologist rather than a mathematician.

4 November, 2014 at 6:03 am

tienhsiangMay I ask a limit question？ How to find out the limit of (1-1/4)(1-1/4^2)……(1-1/4^n) when n goes to infinity？Hope you are not offended.

4 November, 2014 at 11:03 am

ashwin1729Dear tienhsiang,you can ask all your math related querries and get valid answers at:

http://math.stackexchange.com/

Good Luck!

4 November, 2014 at 5:12 pm

tienhsiangThanks a lot！

21 November, 2014 at 10:04 am

AnonymousDear Terry,

On page 8 of your paper, you wrote “Since $\chi$ has mean zero on intervals of length $q$, it is easy to see that $A_q=o(1)$”. I don’t quite see this, wouldn’t this imply a better bound for $L(1,\chi)$, namely $o(\log q)$ instead of $O(\log q)$?

Thanks.

21 November, 2014 at 4:21 pm

Terence TaoAh, that is a typo: the claim should be that for ; it should only be that vanishes in this region, not . I’ll update the paper in the next revision to reflect this.

12 January, 2015 at 8:34 am

Terence TaoI’ve managed to improve the exponent of in the above bounds to , although this is still well short of the Burgess exponents of (in the cube-free case) and (in the non-cube-free case). There are two arguments, one using the classical level of distribution of the divisor function at exponent 2/3, and the second using the more recent result of Fouvry, Kowalski, and Iwaniec that the third divisor function has level of distribution 4/7 on smooth moduli.

Roughly speaking, the argument is as follows. Suppose that is large for some . Then has large correlation with on an interval of length a little bit larger than for some . As is periodic with period q, the Cauchy-Schwarz argument in my paper then shows that has unusually high correlation with for some non-zero j. This implies that , and hence , has irregular distribution at moduli . But this contradicts (the proof of) the fact that has level of distribution .

A similar argument using with and and the Fouvry-Kowalski-Iwaniec argument giving the 4/7 level of distribution for predicts that at least one of the sums or exhibits cancellation. (This is enough to bound the least quadratic nonresidue by .)

To improve on the non-cube-free Burgess result by these methods, one would need a level of distribution of above 2/3; to improve upon the cube-free Burgess result, one would need a level of distribution of above 3/4. Unfortunately this is a fair bit beyond current technology. (There is some “well-factorable” structure in the weights, but it is not clear how to use that to go beyond the existing results.)

On the other hand, one can at least now improve upon the Vinogradov exponent of without using any of the Weil conjectures: using the elementary Kloosterman bound on Kloosterman sums (saving a gain instead of the full gain), one can get an exponent of (I think).

ADDED LATER: More generally, getting beyond an exponent of by these methods looks to be roughly equivalent to that of getting the predicted asymptotic for for . Kloosterman sums do the job for (cf. the Titchmarsh divisor problem; also automorphic forms methods are available too, at least in the regime ), but (which would beat the non-cube-free Burgess) is already a little bit beyond current technology, and (which would beat Burgess in general) looks hopeless at present. (The limiting case is a slightly simpler cousin of the twin prime and even Goldbach conjectures, but still considered extremely difficult.)

12 January, 2015 at 8:04 pm

AnonymousNice improvements!

Notes to your arXiv paper:

– In (1.9): –> (in the exponent)

– References [25] and [26] should be updated.