Editing Quadratic residue (section)

===The Pólya&ndash;Vinogradov inequality===

The values of <math>(\tfrac{a}{p})</math> for consecutive values of ''a'' mimic a random variable like a [[coin flip]].<ref>Crandall & Pomerance, ex 2.38, pp 106&ndash;108 discuss the similarities and differences. For example, tossing ''n'' coins, it is possible (though unlikely) to get ''n''/2 heads followed by that many tails. V-P inequality rules that out for residues.</ref> Specifically, [[George Pólya|Pólya]] and [[Ivan Matveevich Vinogradov|Vinogradov]] proved<ref>{{harvnb|Davenport|2000|pp=135–137}}, (proof of P&ndash;V, (in fact big-O can be replaced by 2); journal references for Paley, Montgomery, and Schur)</ref> (independently) in 1918 that for any nonprincipal [[Dirichlet character]] χ(''n'') modulo ''q'' and any integers ''M'' and ''N'',

:<math>\left|\sum_{n=M+1}^{M+N}\chi(n)\right| =O\left( \sqrt q \log q\right),</math>

in [[big O notation]]. Setting

:<math> \chi(n) = \left(\frac{n}{q}\right),</math>

this shows that the number of quadratic residues modulo ''q'' in any interval of length ''N'' is

:<math>\frac{1}{2}N + O(\sqrt q\log q).</math>

It is easy<ref>Planet Math: Proof of Pólya&ndash;Vinogradov Inequality in [[#External links|external links]]. The proof is a page long and only requires elementary facts about Gaussian sums</ref> to prove that

:<math> \left| \sum_{n=M+1}^{M+N} \left( \frac{n}{q} \right) \right| < \sqrt q \log q.</math>

In fact,<ref>Pomerance & Crandall, ex 2.38 pp.106&ndash;108. result from T. Cochrane, "On a trigonometric inequality of Vinogradov", ''J. Number Theory'', 27:9&ndash;16, 1987</ref>

:<math> \left| \sum_{n=M+1}^{M+N} \left( \frac{n}{q} \right) \right| < \frac{4}{\pi^2} \sqrt q \log q+0.41\sqrt q +0.61.</math>

[[Hugh Montgomery (mathematician)|Montgomery]] and [[Robert Charles Vaughan (mathematician)|Vaughan]] improved this in 1977, showing that, if the [[generalized Riemann hypothesis]] is true then

:<math>\left|\sum_{n=M+1}^{M+N}\chi(n)\right|=O\left(\sqrt q \log  \log q\right).</math>

This result cannot be substantially improved, for [[Issai Schur|Schur]] had proved in 1918 that

:<math>\max_N \left|\sum_{n=1}^{N}\left(\frac{n}{q}\right)\right|>\frac{1}{2\pi}\sqrt q</math>

and [[Raymond Paley|Paley]] had proved in 1932 that

:<math>\max_N \left|\sum_{n=1}^{N}\left(\frac{d}{n}\right)\right|>\frac{1}{7}\sqrt d \log \log d</math>

for infinitely many ''d'' > 0.