# Most squares in the first half-interval

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?

-
Note that this is trivial for $p \equiv 1 \pmod 4$ because then $-1$ is a quadratic residue, and any $k$ is a quadratic residue if and only if $p-k$ is. So exactly half lie in your interval, exactly half lie in the interval from $(p+1)/2$ to $p-1.$ –  Will Jagy May 19 '10 at 22:07
Another reference: "Introduction to Cyclotomic Fields", L. C. Washington, pp 45, exercise 4.5. –  Dror Speiser May 19 '10 at 22:08

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.

-
I'm pretty sure this is not the book I had in mind, but it is fine nevertheless. –  Andrea Ferretti May 19 '10 at 20:46

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.

-
Very helpful answer, thank you! In Russian 3rd edition of Borevich and Shafarevich, last paragraph on p. 383, Venkov's reference is OK (no typo). –  Victor Protsak May 19 '10 at 23:07
Very informative! +1 –  Cam McLeman May 19 '10 at 23:28
У меня нет копии русского варианта. Опечатка в первом русском изданием? Английский перевод появился в 1966 г., а второе русское издание вышло в 1972 г. (см. lib.mexmat.ru/books/4065) –  KConrad May 19 '10 at 23:32
(For others: I'm asking whether the first Russian edition of B/S has the typo, since only the first Russian edition was out when it was translated.) –  KConrad May 19 '10 at 23:34
Keith Matthews showed me a copy of the original (Russian) 1st edition of Borevich-Shafarevich from 1964 and its reference to Venkov does not have the typographical error from the English translation that I wrote about in my answer above. –  KConrad Jun 6 '11 at 4:32