# Shortest interval over which there are more quadratic residues than nonresidues

Hi, I refer to formula (8) in Chapter 1 of H. Davenport, Multiplicative Number Theory, Third Edition, Springer (2000), which says that for primes $q\equiv 3 \bmod 4$:

$$L\left(\left(\frac{\cdot}{q}\right),1\right) = \frac{\pi}{q^{1/2}\left(2-\left(\frac{2}{q}\right)\right)}\sum_{0<m<q/2}\left(\frac{m}{q}\right).$$

This formula is due to Dirichlet and implies that for primes $q\equiv 3 \bmod 4$, there are more quadratic residues than nonresidues in $(0,q/2)$. It seems that this approach can be mimicked so that a general formula can be produced which says that for primes $q\equiv 3 \bmod 4$, and any prime $r$, one has

$$L\left(\left(\frac{\cdot}{q}\right),1\right) = \frac{\pi}{q^{1/2}\left(r-\left(\frac{r}{q}\right)\right)}\sum_{0<m<q/2}\left(\frac{m}{q}\right)\left(r-1-2\left\lfloor\frac{mr}{q}\right\rfloor\right).$$

By plugging in $r=2$, one obtains the first formula. By plugging in $r=3$, one obtains

$$L\left(\left(\frac{\cdot}{q}\right),1\right) = \frac{2\pi}{q^{1/2}\left(3-\left(\frac{3}{q}\right)\right)} \sum_{0<m<q/3} \left(\frac{m}{q}\right).$$

This implies that there are more quadratic residues than nonresidues in $(0,q/3)$ for primes $q \equiv 3 \bmod 4$. However, by (28) and (29) of "Elementary Trigonometric Sums related to Quadratic Residues" by Laradji, Mignotte and Tzanakis, there are as many quadratic residues as nonresidues in $(0,(q-3)/4]$ and more quadratic residues than nonresidues in $[(q+1)/4,(q-1)/2]$ for primes $q \equiv 3\bmod 8$, with the situation reversed when $q \equiv 7 \bmod 8$. Combined with the above, this means there are more quadratic residues than nonresidues in $[(q+1)/4,q/3)$ when $q\equiv 3 \bmod 8$. This last interval has length about $q/12$.

So I'm wondering what is the smallest $\beta>0$ over which one can prove that there are more quadratic residues than nonresidues in an interval of length $\beta q$? (For a positive density of primes $q$.) And also it'd be nice if it is the same interval, eg $(\delta q, (\delta+\beta) q)$. Thanks.

• I can't seem to make the first three equations display properly. Here is the first one: $$L\left(\left(\frac{\cdot}{q}\right),1\right) = \frac{\pi}{q^{1/2}\left(2-\left(\frac{2}{q}\right)\right)}\sum_{0<m<q/2}\left(\frac{m}{q}\right)$$ – Timothy Foo Oct 28 '11 at 6:52
• The second one: $$L\left(\left(\frac{\cdot}{q}\right),1\right) = \frac{\pi}{q^{1/2}\left(r-\left(\frac{r}{q}\right)\right)}\sum_{0<m<q/2}\left(\frac{m}{q}\right)\left(r-1-2\left\lfloor\frac{mr}{q}\right\rfloor\right)$$ and the third one: $$L\left(\left(\frac{\cdot}{q}\right),1\right) = \frac{2\pi}{q^{1/2}\left(3-\left(\frac{3}{q}\right)\right)}\sum_{0<m<q/3}\left(\frac{m}{q}\right)$$ – Timothy Foo Oct 28 '11 at 6:53
• Fixed your LaTeX - the trick is to put backtick marks around your displayed maths – Yemon Choi Oct 28 '11 at 7:46
• A bit late, but I asked recently mathoverflow.net/questions/106359/… for an evaluation of the sum of $\left( \frac{.}{p} \right)$ over intervals $aq <n <bq$. What I wrote in my question implies that the answer to your question for $\beta= \frac{1}{6}$ depends only on $p \mod 24$. – js21 Oct 14 '12 at 20:25
• Thanks so much for your comment. I actually saw your question but couldn't say anything noteworthy about it off the top of my head. What wonderful implications what you wrote has. I hope that there will be more interesting facts that will emerge, whether on MO or not, in regards to this topic. Thanks again. – Timothy Foo Oct 20 '12 at 11:01