probability in number theory - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T21:53:01Z http://mathoverflow.net/feeds/question/13011 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/13011/probability-in-number-theory probability in number theory ex falso quodlibet 2010-01-26T04:33:39Z 2010-07-01T13:34:01Z <p>Hi,</p> <p>I am hearing that there are some great applications of probability theory (or more general measure theory) to number theory. Could anyone recommend some good book(s) on that (or other types of references)?</p> <p>Please one source per answer as I would like to make this community wiki.</p> <p>Thanks in advance!</p> http://mathoverflow.net/questions/13011/probability-in-number-theory/13013#13013 Answer by Qiaochu Yuan for probability in number theory Qiaochu Yuan 2010-01-26T04:46:26Z 2010-01-26T04:46:26Z <p>I learned <a href="http://www.springerlink.com/content/y16081665jv19k87/" rel="nofollow">from Gian-Carlo Rota</a> the following probabilistic motivation for looking at the Riemann zeta function: "subject to technical assumptions," the only probability measures on $\mathbb{N}$ for which the events of being divisible by distinct primes are independent are the ones which assign to a positive integer $n$ the probability $\frac{1}{n^s \zeta(s)}$ for some $s$.</p> http://mathoverflow.net/questions/13011/probability-in-number-theory/13015#13015 Answer by Ben Weiss for probability in number theory Ben Weiss 2010-01-26T05:12:42Z 2010-01-26T15:33:41Z <p>The one I learned from is <a href="http://www.amazon.com/Introduction-Analytic-Probabilistic-Cambridge-Mathematics/dp/0521412617/ref=sr%5F1%5F4?ie=UTF8&amp;s=books&amp;qid=1264482606&amp;sr=1-4" rel="nofollow">Tenenbaum</a>. </p> <p>My personal favorite application is to derive heuristics for the twin prime conjecture (and more general Hardy-Littlewood conjecture). For an excellent exposition on this, see <a href="http://www.ams.org/bull/2007-44-01/S0273-0979-06-01142-6/S0273-0979-06-01142-6.pdf" rel="nofollow">Soundararajan's</a> article.</p> http://mathoverflow.net/questions/13011/probability-in-number-theory/13043#13043 Answer by John Mangual for probability in number theory John Mangual 2010-01-26T14:15:46Z 2010-01-26T14:15:46Z <p>Have you read <a href="http://www.amazon.com/Probabilistic-Wiley-Interscience-Discrete-Mathematics-Optimization/dp/0471370460" rel="nofollow">The Probabilistic Method</a> by Joel Spencer and Noga Alon? </p> <p>Although originally developed by Erdos, here's an example of the probabilistic method taken from combinatoricist <a href="http://www.math.cmu.edu/~ploh/docs/math/mop2009/prob-comb.pdf" rel="nofollow">Po-Shen Loh</a>: </p> <p>$A_1, \dots, A_s \subseteq { 1, 2, \dots, M }$ such that $A_i \not \subset A_j$ and let $a_i = |A_i|$. Show that $$\sum_{i=1}^s \frac{1}{\binom{M}{a_i}} \leq 1$$ The hint is to consider a random permutation $\sigma = (\sigma_1, \dots, \sigma_M)$. Loh defines the event $E_i$ when $\{ \sigma_1, \dots, \sigma_{a_i}\} = A_i$. Then he observes the events $E_i$ are mutually exclusive and that $\mathbb{P}(E_i)$ is relevant to our problem... </p> <p>There are probably a lot of olympiad combinatorics problems that can be solved this way. Err... you were asking for number theory, but you will find both in Spencer and Alon's book.</p> http://mathoverflow.net/questions/13011/probability-in-number-theory/13046#13046 Answer by Mark Meckes for probability in number theory Mark Meckes 2010-01-26T15:09:27Z 2010-01-26T15:09:27Z <p>This may not be the kind of thing you have in mind, but there are deep and not yet well-understood connections between analytic number theory and random matrix theory. Try <a href="http://www.amazon.com/Recent-Perspectives-Mathematical-Society-Lecture/dp/0521620589/ref=sr_1_2?ie=UTF8&amp;s=books&amp;qid=1264518467&amp;sr=8-2" rel="nofollow">these 2004 summer school proceedings</a> edited by Mezzadri and Snaith for an extremely thorough introduction.</p> http://mathoverflow.net/questions/13011/probability-in-number-theory/13049#13049 Answer by Cam McLeman for probability in number theory Cam McLeman 2010-01-26T15:31:52Z 2010-01-26T15:31:52Z <p>Statistical Independence in Probability, Analysis, and Number Theory, by Mark Kac -- an amazingly potent piece of mathematical writing given its rather minuscule size. While now slightly out of date in terms of best possible bounds, he fairly seamlessly collects some of the most important results in analytic number theory. This was the first book (for me) that calculated not only expected values for the standard arithmetic functions (various divisor-counting functions, sum-of-divisors function,etc.), but also the expected deviation, in terms of a probability distribution function, from this value. These types of results don't get emphasized enough -- almost as important as knowing asymptotic values for a quantity in question is knowing how frequently the value is far from that asymptote.</p> http://mathoverflow.net/questions/13011/probability-in-number-theory/13055#13055 Answer by maks for probability in number theory maks 2010-01-26T17:51:31Z 2010-01-26T17:51:31Z <p>Elliott's "Probabilistic number theory" ! It's not an easy read, but it's worth reading.</p> <p>(Probability in number theory was applied most intensely to study the distribution of values of additive (and multiplicative!) functions)</p> http://mathoverflow.net/questions/13011/probability-in-number-theory/13056#13056 Answer by maks for probability in number theory maks 2010-01-26T18:02:15Z 2010-01-26T18:02:15Z <p>Also, for a very brief (but excellent!) introduction, see: <a href="http://algo.inria.fr/seminars/sem96-97/deshouillers.pdf" rel="nofollow">http://algo.inria.fr/seminars/sem96-97/deshouillers.pdf</a></p> <p>Baez-Duarte, wrote a beautiful article, giving us a "probabilistic" derivation of the Hardy-Ramanujan asymptotic for p(n). He's essentially interpreting "probabilistically" the saddle-point method, and this type of thinking was central to me for a long time. </p> <p>The exact reference for his paper is: MR1427803 (98b:60036) Báez-Duarte, Luis Hardy-Ramanujan's asymptotic formula for partitions and the central limit theorem. Adv. Math. 125 (1997), no. 1, 114--120</p> <p>It's online, but I can't post more than one link... :-(</p> <p>Finally, I recommend visiting the home-pages of Kevin Ford and Gerald Tenenbaum...</p> http://mathoverflow.net/questions/13011/probability-in-number-theory/13092#13092 Answer by Will Jagy for probability in number theory Will Jagy 2010-01-27T02:52:30Z 2010-01-27T02:52:30Z <p>The AMS Notices are now freely available online. Nice summary article by Brian Conrey on the Riemann Hypothesis, including the recent links with random matrices mentioned. His own work is not a reference in the survey article, but Conrey is the one who showed that at least forty percent of the zeros in the critical strip lie on the line with real part 1/2. See<br /> <a href="http://www.ams.org/notices/200303/index.html" rel="nofollow">http://www.ams.org/notices/200303/index.html</a></p> http://mathoverflow.net/questions/13011/probability-in-number-theory/27741#27741 Answer by coudy for probability in number theory coudy 2010-06-10T20:44:53Z 2010-06-10T21:44:31Z <p>The book by G. Tennenbaum, "Introduction a la theorie analytique et probabiliste des nombres" is well written. It has a translation in english called <em>"Introduction To Analytic And Probabilistic Number Theory"</em>, Cambridge University Press (2004).</p> http://mathoverflow.net/questions/13011/probability-in-number-theory/27783#27783 Answer by Peter Humphries for probability in number theory Peter Humphries 2010-06-11T04:50:47Z 2010-06-11T04:50:47Z <p>Tenenbaum's book is indeed one of the best on the subject; it's well-motivated and quite accessible. If you go a bit further back, there are also the <em>Probabilistic Number Theory</em> books by P. D. T. A. Elliot; volume I is on Mean Value Theorems, while volume II is on Central Limit Theorems. These are both a bit more specialised and slightly outdated. Even older still is <em>Probabilistic Methods In the Theory of Numbers</em> by J. Kubilius.</p> http://mathoverflow.net/questions/13011/probability-in-number-theory/27832#27832 Answer by To be cont'd for probability in number theory To be cont'd 2010-06-11T16:02:39Z 2010-06-11T16:02:39Z <p>Here are three:</p> <ol> <li><p>Analytic and probabilistic methods in number theory: proceedings of the ... By Fritz Schweiger, E. Manstavičius (This is a bit specialized but good.)</p></li> <li><p><a href="http://home.a-eskwadraat.nl/~wouter/b_thesis.pdf" rel="nofollow">Probabilistic Number Theory</a> by Wouter Duivesteijn</p></li> <li><p><a href="http://math.uga.edu/~pete/probnumtalk1.pdf" rel="nofollow">PROBABILISTIC IDEAS AND METHODS IN ANALYTIC NUMBER THEORY</a> (This is from our most reputed MO-ist Pete L. Clark)</p></li> </ol> http://mathoverflow.net/questions/13011/probability-in-number-theory/30131#30131 Answer by LaLone for probability in number theory LaLone 2010-07-01T02:39:46Z 2010-07-01T13:34:01Z <p>I recently noticed a connection, while looking at a campy sort of problem.</p> <p>The problem goes like this A strange sort of prison has 1200 cells and 1200 guards (each numbered 1-1200). Whenever a guard turns his key in a lock it either locks the cell or unlocks the cell. Every night guard 1 goes through and turns his key in each cell, locking all of them. Then guard 2 turns his key in each cell that is divisible by 2 (which unlocks each of these) and so on until all the guards have gone through their round. So the question is at the end of the night how many cells are locked, which cells are they. </p> <p>So you can figure out pretty easily that if a cell has an even number of divisors then it will be unlocked at the end of the night. Whereas if the cell has an odd number of divisors then it will end up locked. You can use the tau function to think about when a number will have an even number of divisors and when it will have an odd number of divisors. (I won't ruin the solution for anyone) While I was working on this I noticed that the probability of an integer having an odd number of divisors decreases by a factor of 1/2 whenever a new prime factor is added to the prime factorization of the integer. In other words to compute the probability that an integer has an odd number of divisors you can raise 1/2 to the number of distinct primes in the prime factorization. </p> <p>Once you figure out which cells are locked at the end of the night this conclusion will probably seem pretty worthless but it got me interested in the connection between number theory and probability</p>