Number of quadratic residues in an interval

Question

Using the Pólya-Vinogradov inequality, one can apparently show that the number of quadratic residues modulo $q$ in any interval of length $N$ is $N/2 + O(q^{1/2}\log q)$.

I feel like I am missing something really simple here, because I do not see how this holds. If we take $q$ to be prime, then the number of quadratic residues modulo $q$ is $(q-1)/2$ (excluding $0$) so taking $k$ of these intervals, say from $1$ to $kq$, we get $k (q-1)/2$ quadratic residues in an interval of length $kq$ and the error term depends on $k$. What am I doing wrong here?

Also, how does the correct formula follow from the Pólya-Vinogradov inequality?

Answer 1

Suppose that $q$ is prime. The Polya-Vinogradov formula states that $$\sum_{n=M+1}^{M+N} \chi(n) = O(\sqrt{q} \log q)$$ For quadratic residues, the character being used here is $$\chi(n) = \left\{\begin{array}{rl} 1 & \textrm{ if } n \textrm{ is a non-zero quadratic residue} \\ -1 & \textrm{ if } n \textrm{ is a non-zero quadratic non-residue} \\ 0 & \textrm{ if } q \textrm{ divides } n \end{array}\right.$$

The key thing here is that a Dirichlet character is $0$ (and not $\pm 1$) on multiples of $q$.

Suppose now that I look at the interval $[1, kq]$. If I let $y$ be the number of quadratic residues in this interval which are not multiples of $q$, then the character is equal to $1$ exactly $y$ times, and equal to $0$ exactly $q$ times, so is equal to $-1$ a total of $kq-q-y=k(q-1)-y$ times. So the character sum is $$y - [(k(q-1)-y] = k(q-1)-2y$$ Plugging this into the Polya-Vinogradov formula gives that $$y=\frac{q-1}{2} k + O(\sqrt{q \log q})$$ Which is consistent with your observations.

The difference between what Polya-Vinogradov actually gives you and $\frac{N}{2}$ comes from the handling of places where $\chi(n)=0$. In practice, usually when Polya-Vinogradov is applied it is for $N$ which is smaller than $q$ (since the character always adds to $0$ on intervals of length $q$ anyway). Once you restrict down to that size interval, the case where $q|n$ can only change the sum by $1$, so is insignificant.