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 {n(p)} of a prime {p}. Vinogradov established the bound

\displaystyle n(p) \ll p^{\frac{1}{2\sqrt{e}}} \log^2 p \ \ \ \ \ (1)

and conjectured that

\displaystyle n(p) \ll p^\varepsilon \ \ \ \ \ (2)

for any fixed {\varepsilon>0}. Unconditionally, the best result so far (up to logarithmic factors) that holds for all primes {p} is by Burgess, who showed that

\displaystyle n(p) \ll p^{\frac{1}{4\sqrt{e}}+\varepsilon} \ \ \ \ \ (3)

for any fixed {\varepsilon>0}. 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

\displaystyle n(p) \ll p^{(\frac{1}{2}-\frac{1}{34})\frac{1}{\sqrt{e}} + \varepsilon},

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 {q} with {n(q)} unusually large. Letting {\chi} be the quadratic character modulo {q}, this implies that the sums {\sum_{n \leq x} \chi(n)} are also unusually large for a significant range of {x} (e.g. {x < n(q)}), although the sum is also quite small for large {x} (e.g. {x > q}), due to the cancellation present in {\chi}. It turns out (by a sort of “uncertainty principle” for multiplicative functions, as per this paper of Granville and Soundararajan) that these facts force {\sum_{n\leq x} \chi(n) \Lambda(n)} to be unusually large in magnitude for some large {x} (with {q^C \leq x \leq q^{C'}} for two large absolute constants {C,C'}). By the periodicity of {\chi}, this means that

\displaystyle \sum_{n\leq x} \chi(n) \Lambda(n+q)

must be unusually large also. However, because {n(q)} is large, one can factorise {\chi} as {f * 1} for a fairly sparsely supported function {f = \chi * \mu}. The Elliott-Halberstam conjecture, which controls the distribution of {\Lambda} in arithmetic progressions on the average can then be used to show that {\sum_{n \leq x} (f*1)(n) \Lambda(n+q)} is small, giving the required contradiction.

The implication involving Type II estimates is proven by a variant of the argument. If {n(q)} is large, then a character sum {\sum_{N\leq n \leq 2N} \chi(n)} is unusually large for a certain {N}. By multiplicativity of {\chi}, this shows that {\chi} correlates with {\chi * 1_{[N,2N]}}, and then by periodicity of {\chi}, this shows that {\chi(n)} correlates with {\chi * 1_{[N,2N]}(n+jq)} for various small {q}. By the Cauchy-Schwarz inequality (cf. this previous blog post), this implies that {\chi * 1_{[N,2N]}(n+jq)} correlates with {\chi * 1_{[N,2N]}(n+j'q)} for some distinct {j,j'}. 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 {p} with {n(p) = p^{\frac{1}{4\sqrt{e}} + o(1)}}. Suppose we let {a(t)} be the asymptotic mean value of the quadratic character {\chi} at {p^t} and {b(t)} the mean value of {\chi \Lambda}; these quantities are defined precisely in my paper, but roughly speaking one can think of

\displaystyle a(t) = \lim_{p \rightarrow \infty} \frac{1}{p^t} \sum_{n \leq p^t} \chi(n)

and

\displaystyle b(t) = \lim_{p \rightarrow \infty} \frac{1}{p^t} \sum_{n \leq p^t} \chi(n) \Lambda(n).

Thanks to the basic Dirichlet convolution identity {\chi(n) \log(n) = \chi * \chi\Lambda(n)}, one can establish the Wirsing integral equation

\displaystyle t a(t) = \int_0^t a(u) b(t-u)\ du

for all {t \geq 0}; 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

\displaystyle a(t)=b(t) = 1 \hbox{ for } t < \frac{1}{4\sqrt{e}}

while from the Burgess exponential sum estimates we have

\displaystyle a(t) = 0 \hbox{ for } t > \frac{1}{4}.

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

\displaystyle b(t) = -1 \hbox{ for } \frac{1}{4\sqrt{e}} \leq t \leq \frac{1}{4}

and

\displaystyle a(t) = 1 - 2 \log(4 \sqrt{e} t) \hbox{ for } \frac{1}{4\sqrt{e}} \leq t \leq \frac{1}{4}

and then for {t > \frac{1}{4}}, {b} evolves by the integral equation

\displaystyle b(t) = \int_{1/4\sqrt{e}}^{1/4} b(t-u) \frac{2du}{u}.

For instance

\displaystyle b(t) = 1 \hbox{ for } \frac{1}{4} < t \leq \frac{1}{2\sqrt{e}}

and then {b} oscillates in a somewhat strange fashion towards zero as {t \rightarrow \infty}. This very odd behaviour of {\sum_n \chi(n) \Lambda(n)} 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).