MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

## 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
show 1 more comment