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?
> 
> 
> 



Most squares in the first half-interval
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.


