Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
2  
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
1  
Another reference: "Introduction to Cyclotomic Fields", L. C. Washington, pp 45, exercise 4.5. –  Dror Speiser May 19 '10 at 22:08
add comment

2 Answers 2

up vote 13 down vote accepted

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.

share|improve this answer
    
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
add comment

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.

share|improve this answer
    
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
1  
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
show 6 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.