Can Gauss sums derandomize any heuristic arguments? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T07:08:34Z http://mathoverflow.net/feeds/question/52803 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/52803/can-gauss-sums-derandomize-any-heuristic-arguments Can Gauss sums derandomize any heuristic arguments? Timothy Chow 2011-01-22T00:54:09Z 2011-07-24T08:07:00Z <p>I've always been fascinated by the fact that the classical <a href="http://en.wikipedia.org/wiki/Gauss_sum" rel="nofollow">Gauss sum</a> has absolute value $\sqrt p$, which is exactly what we would expect if we were to interpret the Gauss sum as a random walk. In particular, I have long wondered whether this apparent link between number theory and probability theory is just a curiosity, or whether it is a symptom of a deeper connection. For example, there are many heuristic arguments in number theory that treat primes as being "random." Is there any example of such a heuristic argument that can be made rigorous by using the above observation about Gauss sums?</p> http://mathoverflow.net/questions/52803/can-gauss-sums-derandomize-any-heuristic-arguments/52823#52823 Answer by Pete L. Clark for Can Gauss sums derandomize any heuristic arguments? Pete L. Clark 2011-01-22T09:03:31Z 2011-01-22T09:03:31Z <p><em>Caveat lector</em>: as an answer to Timothy's question, this is tangential at best. </p> <p>Regarding Gerry and Kevin's comments, people might be interested in Section 2 of <a href="http://math.uga.edu/~pete/4400pnt.pdf" rel="nofollow">these notes of mine</a> from an undergraduate number theory course, in which the philosophy of "almost square root error" is batted around for a while, especially with regard to the Riemann hypothesis. This is maybe my favorite set of lecture notes from this course, perhaps because I got a chance to (talk and) write excitedly about things I hardly understand: I certainly do not claim a professional level of insight here. (Indeed some regulars on this site could do far better, and I would be interested to hear their critiques.) </p> <p>The upshot though is that of agreement with Gerry and Kevin: having size $\sqrt{p}$ <strong>on the nose</strong> is just a little bit better than random, but the little bit makes a big difference: to me this suggests very precise structure rather than randomness.</p> <p>Please <a href="http://www.math.harvard.edu/~mazur/papers/nature_sato_tate.pdf" rel="nofollow">see here</a> for another take on the subject of almost square root error in the context of the Sato-Tate Conjecture. This latter article was written at almost the same time as mine, and the author happens to be my former thesis advisor. I am reasonably sure that both of these coincidences are indeed coincidental.</p> http://mathoverflow.net/questions/52803/can-gauss-sums-derandomize-any-heuristic-arguments/52824#52824 Answer by Charles Matthews for Can Gauss sums derandomize any heuristic arguments? Charles Matthews 2011-01-22T10:30:27Z 2011-01-22T10:30:27Z <p>The thing is that it is well known that for the quadratic Gauss sums, expressed as an exponential sum rather than with Legendre symbols, the path is very much not a random walk when you plot it in the complex plane. There is plenty of structure visible as approximate Cornu spirals. </p> <p>Such sums are not the only Gauss sums, as I know to my cost; and the quadratic case is atypical (perhaps). But from a high-flown point of view, a Gauss sum is a special function in the theory of finite fields (like a Gamma function). There seems to be more mileage in asking about what is special about it.</p> http://mathoverflow.net/questions/52803/can-gauss-sums-derandomize-any-heuristic-arguments/71111#71111 Answer by unknown (yahoo) for Can Gauss sums derandomize any heuristic arguments? unknown (yahoo) 2011-07-24T08:07:00Z 2011-07-24T08:07:00Z <p>Actually I would think there are connections. Even if the the coincidence $\sqrt{p}$ seems ordinary, there are low-correlation sequences which owe their low correlation to Gauss sum estimates and looking from a probabilistic view point sequences, I would think there would be interpretations from a view point of uncorrelated random variables. Your starting point could be low-correlation sequences used in communications systems and beyond that I would think Nicholas Katz and Sarnak's dive into random matrices would help. <a href="http://books.google.com/books?id=wXyOPbzvowsC&amp;printsec=frontcover&amp;dq=inauthor:%22Nicholas+M.+Katz%22&amp;hl=en&amp;ei=j9IrTu24CpKnsAKG5c3DCw&amp;sa=X&amp;oi=book_result&amp;ct=result&amp;resnum=5&amp;ved=0CD8Q6AEwBA#v=onepage&amp;q&amp;f=false" rel="nofollow">http://books.google.com/books?id=wXyOPbzvowsC&amp;printsec=frontcover&amp;dq=inauthor:%22Nicholas+M.+Katz%22&amp;hl=en&amp;ei=j9IrTu24CpKnsAKG5c3DCw&amp;sa=X&amp;oi=book_result&amp;ct=result&amp;resnum=5&amp;ved=0CD8Q6AEwBA#v=onepage&amp;q&amp;f=false</a></p>