Estimates for character sums
Theorem 1 (Pólya-Vinogradov). Let $q$ be a positive integer and $\chi$ a character $\pmod q$. Then we have the bound
\[\begin{eqnarray}\left|\sum_{M\leq n\leq N}\chi(n)\right|\leq 2 \sqrt{q}\log q.\end{eqnarray}\]
Proof. We may assume that $q>1$. We follow an elegant proof by Schur, from his paper. First let $\chi$ be primitive, and use its Fourier representation to get some cancellation. From this earlier post on Gaussian sums, we know for primitive $\chi$ that
\[\begin{eqnarray}\chi(n)=\frac{1}{\tau(\bar{\chi})}\sum_{k=1}^{q-1}\bar{\chi}(k)e^{\frac{2\pi i k n}{q}},\end{eqnarray}\]
(in that post $\chi$ was a real character, but it has no impact on the computations). We also saw in the earlier post that $|\tau(\chi')|=\sqrt{q}$. Now substituting this, we get
\[\begin{eqnarray}\left|\sum_{M\leq n\leq N}\chi(n)\right|&=&\frac{1}{\sqrt{q}}\left|\sum_{M\leq n\leq N}\sum_{k=1}^{q-1}\bar{\chi}(k)e^{\frac{2\pi i k n}{q}}\right|\\&=&\frac{1}{\sqrt{q}}\left|\sum_{k=1}^{q-1}\bar{\chi}(k) \sum_{M\leq n\leq N} e^{\frac{2\pi i k n}{q}}\right|\\&=&\frac{1}{\sqrt{q}}\left|\sum_{k=1}^{q-1}\bar{\chi}(k) \frac{e^{\frac{\pi i (N-M+1)}{q}}-e^{\frac{\pi i (N-M+1)}{q}}}{e^{\frac{\pi i k}{q}}-e^{\frac{-\pi i k}{q}}} \right|.\end{eqnarray}\]
At this point, we already have a promising square root factor in the denominator, so we just need to show that the exponential terms we are summing are not terribly large. By the trivial inequality $|e^{ix}-e^{iy}|\leq 2$, it follows that
\[\begin{eqnarray}\left|\sum_{M\leq n\leq N}\chi(n)\right|&\leq \frac{1}{\sqrt{q}}\sum_{k=1}^{q-1} \frac{1}{\sin(\frac{\pi k}{q})}.\end{eqnarray}\]
We see that this expression is a Riemann sum for $\sin(\pi x)^{-1}$. Therefore, we would like to show
\[\begin{eqnarray}\frac{1}{\sqrt{q}}\sum_{k=1}^{q-1} \frac{1}{\sin(\frac{\pi k}{q})}\leq \frac{1}{\sqrt{q}}\int_{(2q)^{-1}}^{1-(2q)^{-1}} \frac{dx}{\sin(\pi x)}.\end{eqnarray}\]
We can indeed make this comparison, owing to the inequality
\[\begin{eqnarray}q\int_{\frac{k}{q}-\frac{1}{2q}}^{\frac{k}{q}+\frac{1}{2q}}\frac{dx}{\sin(\pi x)}\geq \frac{1}{\sin(\frac{\pi k}{q})},\end{eqnarray}\]
which is just Jensen's inequality applied to the convex function $f(x)=\sin(\pi x)^{-1}$. Finally, by symmetry and using $\sin(\pi x)>2x$ for $x\in (0,\frac{1}{2})$, we get
\[\begin{eqnarray}\left|\sum_{M\leq n\leq N}\chi(n)\right|&<& \frac{2}{\sqrt{q}}\int_{(2q)^{-1}}^{\frac{1}{2}} \frac{dx}{2x}\\&=&\sqrt{q}\left(\log \frac {1}{2}-\log{\frac{1}{2q}}\right)=\sqrt{q}\log q.\end{eqnarray}\]
This completes the proof for primitive characters.
Assume then that $\chi$ is induced by a character $\chi_1\pmod{q'}$, with $q=q'r.$ Then $\chi_1(n)$ is equal to $\chi(n)$ whenever $(n,r)=1$, and in other cases $\chi(n)=0$, so
\[\begin{eqnarray}\left|\sum_{M\leq n\leq N}\chi(n)\right|&=&\left|\sum_{M\leq n\leq N\atop (n,r)=1}\chi_1(n)\right|.\end{eqnarray}\]
We use the Möbius function to represent the characteristic function of $(n,d)=1$ (which is $1$ if and only if $n$ and $d$ are coprime). Then
\[\begin{eqnarray}\left|\sum_{M\leq n\leq N\atop (n,r)=1}\chi_1(n)\right|&=&\left|\sum_{M\leq n\leq N}\sum_{d\mid(n,r)}\mu(d)\chi_1(n)\right|\\&=&\left|\sum_{d\mid r}\mu(d)\sum_{\frac{M}{d}\leq m\leq \frac{N}{d}}\chi_1(dm)\right|.\end{eqnarray}\]
When we apply the Pólya-Vinogradov inequality to the primitive character $\chi_1$, we see that this sum is at most
\[\begin{eqnarray}\sqrt{q_1}\log q_1\left|\sum_{d\mid r}\mu(d)\chi_1(d)\right|\leq \sqrt{q_1}\log q_1 d(r),\end{eqnarray}\]
where $d(\cdot)$ is the number of divisors function. We have the elementary inequality $d(r)\leq 2\sqrt{r}$, since the number of divisors up to $\sqrt{r}$ is at most $\sqrt{r}$, and the number of all divisors is at most twice that. Hence,
\[\begin{eqnarray}\left|\sum_{M\leq n\leq N}\chi(n)\right|&\leq 2\sqrt{q}\log q.\end{eqnarray}\]
This finishes the proof. ■
An immediate corollary is that the numbers of quadratic residues and nonresidues $\pmod q$ are very close to each other on intervals of length much larger than $\sqrt{q}\log q$.
Corollary. The number of quadratic residues $\pmod q$ on any interval of length $x$ is $\frac{x}{2}+O(\sqrt{q}\log q)$. In particular, every interval of length $\geq c\sqrt{q}\log q$ contains a quadratic residue, as well as a nonresidue.
One of the beauties of the Pólya-Vinogradov inequality is that, despite being entirely elementary, it is optimal up to the logarithmic factor. Moreover, one has not been able to reduce the logarithmic factor generally. Perhaps surprisingly, the lower bound of $O(\sqrt{q})$ is also elementary, and it is from the same paper of Schur as the proof above.
Theorem 2 (Schur). Let $S_{N}(\chi)=\sum_{n=1}^N \chi(n)$. Then $\frac{1}{q}\sum_{n=1}^{q-1} |S_{n}(\chi)|\geq \frac{\sqrt{q}}{2\pi}$. Thus the character sum $S_n(\chi)$ is $\gg \sqrt{q}$ on average.
Proof. All we need to do is to use partial summation to the formula
\[\begin{eqnarray}\tau(\chi)=\sum_{k=1}^{q-1}\chi(k)e^{\frac{2\pi i k}{q}}.\end{eqnarray}\]
The formula becomes
\[\begin{eqnarray}\tau(\chi)=\sum_{k=1}^{q-1}S_k(\chi)e^{\frac{2\pi i k}{q}}(e^{\frac{2\pi i }{q}}-1).\end{eqnarray}\]
Thus
\[\begin{eqnarray}\sqrt{q}=|\tau(\chi)|\leq\sum_{n=1}^{q-1} |S_{n}(\chi)|\cdot 2 \sin \frac{\pi }{q}<\frac{2\pi}{q}\sum_{n=1}^{q-1} |S_{n}(\chi)|,\end{eqnarray}\]
as wanted. ■
Application to primitive roots
We give an application of the Pólya Vinogradov inequality to bounding the size of the smallest primitive root $g(q)$ modulo $q$, where $q$ is a prime. For the basic properties of primitive roots, see this post. There are a lot of primitive roots $\pmod q$, namely $\varphi(q-1)$, and this is a large number:
\[\begin{eqnarray}\varphi(q-1)=(q-1)\prod_{p\mid q-1}\left(1-\frac{1}{p}\right)\geq (q-1)\prod_{2\leq k\leq \log_2(q-1)+1}\left(1-\frac{1}{k}\right)\gg \frac{q}{\log q}\end{eqnarray}\]
by trivial estimates. Therefore we expect the smallest primitive root to be small, and indeed Y. Wang showed under generalized Riemann hypothesis that it is $\ll \log^{8}q$. This was improved to $\ll \log^6 q$ by V. Shoup. However, as usual, unconditional bounds are nowhere near such results, and the best that is known is due to Burgess, namely $g(p)\ll q^{\frac{1}{4}+\varepsilon}.$ We will prove the following bound.
Theorem 3. We have $g(q)\leq 2^{\omega(q-1)+1}\sqrt{q}\log q\cdot \frac{q}{\varphi(q-1)}\ll q^{\frac{1}{2}+\varepsilon}$ for any $\varepsilon>0$, where $\omega(m)$ is the number of prime factors of $m$. More generally, any interval of length $x$ has
\[\begin{eqnarray}\frac{\varphi(q-1)}{q}x+O(q^{\frac{1}{2}+\varepsilon})\end{eqnarray}\]
primitive roots modulo $q$.
Proof. As in finding the smallest quadratic residue, the key to this proof is that being a primitive root is a property that can be expressed analytically in terms of characters. Notice that $g$ is a primitive root $\pmod q$ if and only if it is not an $p$th power $\pmod q$ for any prime divisor $p$ of $q-1$. Indeed, it is clear that $g$ cannot be a power, and if $g$ is not a power modulo any $p\mid q-1$, then its order is coprime to each such $p$ and hence to $q-1$. Observe then that the following identity holds.
\[\begin{eqnarray}\frac{1}{p}\sum_{\chi\pmod q\atop \chi^p=\chi_0}\chi(a)=\begin{cases}1,\, a\,\text{an}\, m\text{th power}\\0,\,\text{otherwise}.\end{cases}\end{eqnarray}\]
To verify the identity, write $a\equiv g^{mk+r}$, where $g$ is some primitive root $\pmod q$ and $0\leq r<m$. Now
\[\begin{eqnarray}\frac{1}{p}\sum_{\chi\pmod q\atop \chi^p=\chi_0}\chi(a)=\frac{1}{p}\sum_{\chi\pmod q\atop \chi^p=\chi_0}\chi(g)^r=\frac{1}{m}\sum_{j=0}^{m-1}e^{\frac{2\pi i jr}{m}},\end{eqnarray}\]
since setting $\chi(q)=e^{\frac{2\pi i j}{m}}$ yields a unique chracter for $j=0,1,...,m-1$ as $g$ is a primitive root, and all characters with $\chi^m=\chi_0$ are obtained in this way. The last sum is $1$ if $r=0$ and $0$ otherwise.
Let $\text{Prim}_q(\cdot)$ be the characteristic function of primitive roots $\pmod q$. Denoting by $\text{sq}(n)$ the square-free part of $n$, we obtain
\[\begin{eqnarray}\text{Prim}_q(n)=\prod_{p\mid q-1}\left(1-\frac{1}{p}\sum_{\chi\pmod q\atop \chi^m=\chi_0}\chi(n)\right)=\sum_{d\mid \text{sq}(q-1)}\frac{\mu(d)}{d}\sum_{\chi\pmod q\atop \chi^d=\chi_0}\chi(n),\end{eqnarray}\]
where the last formula comes from multiplying out the second last formula. Finally, we may compute the number of primitive roots on an interval $[N,N+x]$:
\[\begin{eqnarray}\sum_{N\leq n\leq N+x}\text{Prim}_q(n)&=&\sum_{d\mid \text{sq}(q-1)}\frac{\mu(d)}{d}\sum_{\chi\pmod q\atop \chi^d=\chi_0}\sum_{N\leq n\leq N+x}\chi(n)\\&=&x\sum_{d\mid \text{sq}(q-1)}\frac{\mu(d)}{d}+\sum_{d\mid \text{sq}(q-1)}\frac{\mu(d)}{d}\sum_{\substack{\chi\pmod q\\ \chi^d=\chi_0\\\chi\neq \chi_0}}\sum_{N\leq n\leq N+x}\chi(n)\\&=&\prod_{p\mid q-1}\left(1-\frac{1}{p}\right)x+\theta\cdot \sum_{d\mid \text{sq}(q-1)}\frac{1}{d}\sum_{\chi\pmod q\atop \chi^d=\chi_0}2\sqrt{q}\log q\\&=&\frac{\varphi(q-1)}{q}x+2\theta' \tau(\text{sq}(q-1))\sqrt{q}\log q\\&=&\frac{\varphi(q-1)}{q}x+\theta'\cdot 2^{\omega(q-1)+1}\sqrt{q}\log q\end{eqnarray}\]
by the Pólya-Vinogradov inequality. Here $|\theta|,|\theta'|\leq 1$ ($\theta$ and $\theta'$of course depend on $q,N$ and $x$), and $\tau(m)$ is the number of positive divisors of $m$. We see that the number of primitive roots is at least one for
\[\begin{eqnarray}x>2^{\omega(q-1)+1}\sqrt{q}\log q\cdot \frac{q}{\varphi(q-1)},\end{eqnarray}\]
and the claim follows because it is well-known (and easy to see) that $2^{\omega(m)}\leq \tau(m)\ll m^{\varepsilon}$ for any $\varepsilon>0$. ■
Assuming the GRH
We will strengthen the bounds from the previous subsection significantly under the generalized Riemann hypothesis. The form of GRH we need tells that the prime number theorem in arithmetic progressions has a nearly optimal error term.
Theorem 4. Let
\[\begin{eqnarray}\theta(x,\chi):=\sum_{p\leq x}\chi(p)\log p.\end{eqnarray}\]
The GRH is equivalent to the following holding for every Dirichlet character:
\[\begin{eqnarray}\psi(x,\chi)= \begin{cases}O(\sqrt{x}\log^2(qx)),\,\chi\neq \chi_0\\x+O(\sqrt{x}\log^2(qx),\chi\neq \chi_0).\end{cases}\end{eqnarray}\]
For a proof see M. Ram Murty's Problems in analytic number theory. Now we can state the following.
Theorem 5. Assume the GRH. Then the smallest prime primitive root $\pmod q$ is $\ll 2^{\omega(q-1)}\log^4 q\ll q^{\varepsilon}$ for any fixed $\varepsilon>0$, and the smallest prime quadratic nonresidue is $\ll \log^4 q$.
Proof. We have by the GRH
\[\begin{eqnarray}\sum_{p\leq x}Prim_q(p)\log p&=&\frac{\varphi(q-1)}{q-1}x+\sum_{d\mid \text{sq}(q-1)}\frac{\mu(d)}{d}\sum_{\substack{\chi\pmod q\\\chi^d=\chi_0\\\chi\neq \chi_0}}\theta(x,\chi)\\&=&\frac{\varphi(q-1)}{q-1}x+O(2^{\omega(q-1)}\sqrt{x}\log^2(qx))\\&=&\frac{\varphi(q-1)}{q-1}x+O(2^{\omega(q-1)}\sqrt{x}\log^2 q)\end{eqnarray}\]
for $0\leq x\leq q$m, and when $x>C\frac{q-1}{\varphi(q-1)}4^{\omega(q-1)}\log^2 q$, the result is positive. In particular, for $x>C\cdot 2^{\omega(q-1)}\log^4 q$, the result is positive. By the prime number theorem or Chebychev's estimate, we have $\omega(q)\ll \frac{\log q}{\log \log q}$ so that the least prime primitive root is $\ll q^{o(1)}$.
When it comes to quadratic nonresidues, $\frac{1}{2}\left(1-\left(\frac{n}{q}\right)\right)$ is their characteristic function, and we find
\[\begin{eqnarray}\sum_{p\leq x}\frac{1}{2}\left(1-\left(\frac{p}{q}\right)\right)\log p=\frac{x}{2}+O(\sqrt{x}\log^2(qx))=\frac{x}{2}+O(\sqrt{x}\log^2 q)\end{eqnarray}\]
for $0\leq x\leq q$. For $x>C\log^4 q$, this is positive. ■
