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
Anonymous
Great!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
voloch
I 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 Tao
Both 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
voloch
So EH implies existence of small primitive roots. That’s worth mentioning.
28 October, 2014 at 12:09 pm
Terence Tao
Hmm, 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 Tao
I 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
Anonymous
Notes for the first 8 pages of your paper:
– P. 1, l. 7: “follows the” –> “follows from the”
“small, e.g.,
“
”
– 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.
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
2802562155qqcom
ok great!
30 October, 2014 at 6:28 am
Anonymous
– Lemma 2.2: “
” –> “
” [a smaller space]
” –> “
” [insert a small space]
– At the end of the proof of Lemma 2.2: “
[This will be addressed in the next revision of the ms. – T.]?
29 October, 2014 at 9:37 am
Nikhil Bera
Dear 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
ashwin1729
I 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
Anonymous
what 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
Anonymous
You should turn to a psychologist rather than a mathematician.
4 November, 2014 at 6:03 am
tienhsiang
May 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
ashwin1729
Dear 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
tienhsiang
Thanks a lot!
21 November, 2014 at 10:04 am
Anonymous
Dear 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 Tao
Ah, 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 Tao
I’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
Anonymous
Nice improvements!
Notes to your arXiv paper:
–>
(in the exponent)
– In (1.9):
– References [25] and [26] should be updated.