Most squares in the first half-interval - MathOverflow

Most squares in the first half-interval

2010-05-19T18:43:47Z

It is well known that if $p$ is an odd prime, exactly one half of the numbers $1, \dots, p-1$ are squares in $\mathbb{F}_p$. What is less obvious is that among these $(p-1)/2$ squares, at least one half lie in the interval $[1, (p-1)/2]$.

I remember reading this fact many years ago on a very popular book in number theory, where it was claimed that this is an easy consequence of a more sophisticated formula of analytic number theory.

Sadly I forgot both the formula and the book. So the purpose of the question is double:

1) Has any simple way been found to derive the fact mentioned above?

2) Does anybody know a reference for the analytic number theory route to the proof?

Answer by Cam McLeman for Most squares in the first half-interval

2010-05-19T19:17:30Z

Nope! Amazingly enough, no elementary proof of this fact is yet known (Edit: See KConrad's answer). The difficulty is tied up in some pretty fantastic algebraic/analytic number theory, namely the analytic class number formula. But, without getting into that, here's the short form of the story: let $L(s)$ be the $L$-function attached to the character arising from the Kronecker symbol mod $q$. Then one can compute analytically via the Euler product formula for this $L$-function that (for an explicit positive constant $C$), $$ L(1)=C\left[\sum_{m=0}^{q/2}\left(\frac{m}{q}\right)-\sum_{m=q/2}^{q}\left(\frac{m}{q}\right)\right]=\frac{\pi}{\left(2-\left(\frac{2}{q}\right)\right)q^{1/2}}\sum_{m=0}^{q/2}\left(\frac{m}{q}\right), $$ the positivity of which gives the desired statement about the distribution of quadratic residues.

For a reference (from whence I pulled this out of), Davenport's "Multiplicative Number Theory" is pretty fantastic. This is all done in the first 4-5 pages.

Answer by KConrad for Most squares in the first half-interval

2010-05-19T22:36:31Z

There is a method of explaining this without using analytic methods. I will get to that at the end of this answer.

First, if $p \equiv 1 \bmod 4$ then this result is clear since -1 is a square mod $p$. So here exactly half the squares mod $p$ lie in the first half of $[1,p-1]$. The real problem is for $p \equiv 3 \bmod 4$, where analytic methods show there are more squares mod $p$ lying in the first half of that interval than in the second half because there is a formula for the class number of ${\mathbf Q}(\sqrt{-p})$ that is 1 or 1/3 times $S - N$, where $S$ is the number of squares mod $p$ in $[1,(p-1)/2]$ and $N$ is the number of nonsquares mod $p$ in $[1,(p-1)/2]$. Class numbers are positive integers, so $S > N$, which means in $[1,(p-1)/2]$ the squares mod $p$ outnumber nonsquares mod $p$. Since there are as many squares as nonsquares mod $p$ on $[1,p-1]$, the square vs. nonsquare bias on the first half of this interval forces there to be more squares mod $p$ on the first half than squares mod $p$ on the second half.

For a proof by analytic methods, see Borevich-Shafarevich's "Number Theory", Theorem 4 on p. 346. It is not true that no non-analytic derivations of this bias are known. For instance, Borevich and Shafarevich say on p. 347 that Venkov gave a non-analytic proof for some cases in 1928 (which came out in German in 1931: see Math Z. Vol. 33, 350--374). I should clarify this point since there is a bad typo in Borevich and Shafarevich here. What Venkov did was give a non-analytic proof of Dirichlet's class number formula for imaginary quadratic fields having discriminant $D \not\equiv 1 \bmod 8$. Here the book unfortunately has $D \equiv 1 \bmod 8$. (It's clear from the book that something is wrong because shortly after saying Venkov treated $D \equiv 1 \bmod 8$ by non-analytic methods they say the case $D \equiv 1 \bmod 8$ still awaits a non-analytic proof.) The class number formula only gets an interpretation about squares or nonsquares for the fields ${\mathbf Q}(\sqrt{-p})$, but Venkov was working on non-analytic proofs of the class number formula for imaginary quadratic fields without having this restrictive case as the only one in mind. R. W. Davis (Crelle 286/287 (1976), 369--379) made simplifications to Venkov's argument.

What cases for ${\mathbf Q}(\sqrt{-p})$ are covered by Venkov? When $p \equiv 3 \bmod 4$, the discriminant of ${\mathbf Q}(\sqrt{-p})$ is $-p$. If $p \equiv 3 \bmod 8$ then $-p \equiv 5 \bmod 8$, while if $p \equiv 7 \bmod 8$ then $-p \equiv 1 \bmod 8$, so Venkov had non-analytically proved the formula when $p \equiv 3 \bmod 8$. The case $p \equiv 7 \bmod 8$ remained open.

In 1978 the whole problem was solved. Davis, in a second paper (Crelle 299/300 (1978), 247--255), handled some but not all cases of imaginary quadratic fields with discriminant $1 \bmod 8$ (corresponding to $p \equiv 7 \bmod 8$ for the fields ${\mathbf Q}(\sqrt{-p})$) by non-analytic methods and in the same year H. L. S. Orde settled everything by non-analytic methods. See his paper "On Dirichlet's class number formula", J. London Math. Soc. 18 (1978), 409--420.