Most squares in the first half-interval - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T23:32:06Z http://mathoverflow.net/feeds/question/25263 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/25263/most-squares-in-the-first-half-interval Most squares in the first half-interval Andrea Ferretti 2010-05-19T18:43:47Z 2010-05-19T23:29:47Z <p>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]$.</p> <p>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.</p> <p>Sadly I forgot both the formula and the book. So the purpose of the question is double:</p> <blockquote> <p>1) Has any simple way been found to derive the fact mentioned above?</p> <p>2) Does anybody know a reference for the analytic number theory route to the proof?</p> </blockquote> http://mathoverflow.net/questions/25263/most-squares-in-the-first-half-interval/25268#25268 Answer by Cam McLeman for Most squares in the first half-interval Cam McLeman 2010-05-19T19:17:30Z 2010-05-19T23:29:47Z <p>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.</p> <p>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.</p> http://mathoverflow.net/questions/25263/most-squares-in-the-first-half-interval/25292#25292 Answer by KConrad for Most squares in the first half-interval KConrad 2010-05-19T22:36:31Z 2010-05-19T23:25:22Z <p>There is a method of explaining this without using analytic methods. I will get to that at the end of this answer. </p> <p>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 <em>more</em> 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.</p> <p>For a proof by analytic methods, see Borevich-Shafarevich's "Number Theory", Theorem 4 on p. 346. It is <em>not</em> 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.</p> <p>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. </p> <p>In 1978 the <em>whole problem was solved</em>. 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. </p>