God Plays Dice

Does anybody know what Barack Obama's Erdos number is? (In particular, is it even defined?)

I learned a few days ago that if the links are people who know each other, my distance from Barack Obama is at most four -- Joe Biden went to high school with the father of a friend of mine. (Yes, this only proves that I'm at distance at most three from Biden; proving that I'm at distance at most four from Obama is left as an exercise for the reader.

Then again, I'm not sure if Obama even has academic publications, or where I'd look to find out if he did. The relevant Wikipedia article says "he published no legal scholarship", citing this New York Times article, though.

The collected papers of Paul Erdös are available online.

I'm glad I found this. There's a theorem of Erdös and Turan that I've been curious about for a while. Namely, let X_n be the order of a permutation in S_n selected uniformly at random. Then



where Φ is the cumulative distribution function of a standard normal random variable. Informally, log X_n is normally distributed with mean (log² n)/2 and variance (log³ n)/3. Unfortunately the proof, in On some problems of a statistical group-theory, III, doesn't seem to explain this fact in any "probabilistic" way, so I'm not quite as excited to read the paper as I once was. But I had believed the proof was in the first paper in the (seven-paper) series, which is in storage at our library, and it's nearly the holidays, so I probably would have had to wait quite a while to get a copy just to see that it wasn't the one I wanted.

In fact, it was worrying that I had the wrong paper that led me to find this resource in the first place -- seeing the "I" in the citation I had got me curious, so I went to Google. What I expected to see in the Erdos-Turan paper, and what I actually wanted to see, was a "probabilistic" proof somehow based on the central limit theorem. This exists; it's in the paper of Bovey cited below. Also, Erdös seems to have not been good at titling papers; titles "On some problems in X", "Problems and results in Y", "Remarks on Z", "A note on W", etc. are typical. I guess he was too busy proving things to come up with good titles.

References
Bovey, J. D. (1980) An approximate probability distribution for the order of elements of the symmetric group. Bull. London Math. Soc. 12 41-46.
Erdos, P. and Turan, P. (1967) On some problems of a statistical group theory. 111. Acta Math. Acad. Sci. Hungar. 18 309-320.

Yesterday and today I read John Allen Paulos' Irreligion: A Mathematician Explains Why the Arguments for God Just Don't Add Up . A quite good book overall, although Paulos doesn't really cover any new ground here. (Paulos is a mathematician but the book is mostly devoid of mathematical content.) However, the book is a lot more lighthearted than some of the snarky anti-religion books that have been out there lately (say, Dawkins' The God Delusion, or Hitchens' God Is Not Great). Worth reading, although I'm not sure if it's worth paying 20ドル sure, since it's quite short.

But I just wanted to share the following:

Although an atheist, Erdos often referred to an imaginary book in which God has inscribed all the most beautiful mathematical proofs. Whenever he thought that a proof or argument led to a particularly exquisite epiphany, he'd say, "This one's from the book." (Alas, none of the arguments for the existence of God are even close to being in God's book.)

I suspect that some of the people who came up with such arguments thought they were proofs from the book, though. Indeed, are there any long arguments for the existence of God, or are all they all the sort of thing that can be written in half a page or so?

(And although Erdos' book is imaginary, Martin Aigner and Gunter Ziegler's Proofs from THE BOOK is real.)

Yesterday, the Mitchell Report, on steroid usage in baseball, was released. A large number of players were named as users or potential users.

The media coverage of this has routinely mentioned that amphetamines seem to be more common in baseball than steroids; one source I ran into said it's believed that half of baseball players use amphetamines regularly.

Now, when I think of amphetamines, I think of Paul Erdos, and the following story: Ron Graham bet Erdos that he couldn't quit amphetamines for a month, cold turkey. Erdos did. Graham paid up. Erdos said "you've set mathematics back a month".

As far as I know, we mathematicians don't have a drug problem. (Unless you count coffee. I'll freely admit I have a coffee problem.) But I don't think that anybody would say that Erdos should be stripped of any award he won because he was using drugs. The difference is that in sports, the players are competing against each other; thus a level playing field is essential. But in mathematics, we like to believe that we are not competing against each other but cooperating to discover truth; thus we may gladly accept all the chemical help we can get.

Terence Tao, at his blog, describes a rather interesting-sounding interdisciplinary conference he recently attended. At this conference, he gave a talk about Structure and Randomness in the Prime Numbers, which he describes as a shortened version of a similar talk he gave at UCLA. You can see the slides and video of his UCLA talk here. The slides are not terribly useful, because Tao is a good speaker. Like a good speaker, he doesn't just read his slides; the slides give you an idea of what he's talking about but leave out perhaps 90% of the context. The video's good, but it's in RealPlayer format, and RealPlayer and Windows XP don't cooperate -- I got a Blue Screen of Death while watching.

Anyway, one of the ideas he mentions in this talk -- and this is something that I was not aware of before hearing this talk -- is that the Riemann hypothesis, which isequivalent to a certain strengthenging of the prime number theorem, is in a sense a probabilistic result. The Riemann hypothesis is, according to Tao, equivalent to the idea that the primes do behave randomly -- they are distributed according to the prime number theorem, with an error term that is exactly what you'd expect from the law of large numbers. This does not appear to be mentioned in, say, the Clay Mathematics Institute description of the problem, which I think is a shame.

All this got me thinking. I knew that there was a certain heuristic that is often used to determine what results about prime numbers "should be" true -- one assumes that a number which is approximately N has probability 1/log N of being prime. This works quite well, which led Paul Erdos to say: "God may not play dice with the universe, but something strange is going on with the prime numbers." This, for example, leads to a probabilistic argument for the Goldbach conjecture. The Goldbach conjecture states that every even integer greater than or equal to four is the sum of two primes: 4=2+2, 6=3+3, 8=3+5, 10=3+7=5+5, 12=5+7, 14=3+11=5+9, 16=3+13=5+11, 18=5+13=7+11, 20=3+17=7+13, and so on. For small numbers this seems like an accident. But there are, for example, six ways to write 100 as a sum of two primes:

100 =わ 3 +たす 97 =わ 11 +たす 89 =わ 17 +たす 83 =わ 29 +たす 71 =わ 41 +たす 59 =わ 47 +たす 53.

and if we pick a random good-sized even number there are lots of ways to write it as a sum of two primes. For example, the even numbers 4000, 4002, ..., 4020 can be written as a sum of two primes in 65, 106, 72, 52, 104, 65, 54, 108, 55, 66, 133 ways respectively. So we start to get the feeling that there are lots of ways to write even integers as sums of primes, and so it would be astonishingly shocking if the Great Mathematician In The Sky had stacked the deck so that, say, 4045580440 couldn't be witten as a sum of two primes.

On the other hand, there are infinitely many even integers. Let's say that by "astonishingly shocking" I meant that the "probability" that 2N can't be written as a sum of two primes is 1/N. Then, since the sum 1 + 1/2 + 1/3 + 1/4 + ... diverges, not only would Goldbach's conjecture be false, but it would be false infinitely many times.

As it turns out, though, we can make a guess at the probability that n can't be written as a sum of two primes. First, we try to estimate the number of ways to write n as the sum of two primes. This is the "probability" that 3 and n-3 are both prime, plus the "probability" that 4 and n-4 are both prime, plus the "probability" that 5 and n-5 are both prime, and so on up to the probability that n/2 and n/2 are both prime. (I know, you're saying "3 is prime! 4 isn't prime! What are you talking about?") Next, we assume that k and n-k being prime are independent, which isn't true. Then the expected number of ways that n can be written as a sum of two primes is

1/(log(3) log(n-3)) + 1/(log(4) log(n-4)) + ... + 1/(log(n/2) log(n/2))

which turns out to be about n/(2 log² n). This is actually an underestimate, the actual value conjectured by Hardy and Littlewood being something like 1.3 n/(log² n); the basic idea is that if k is prime, then n-k turns out to be more likely to be prime. For example, since n is even, and k must be odd, then n-k is odd, which makes it more likely to be prime. (This is pointed out at the Wikipedia article.) But even the independent result is quite strong. Since being prime is a "rare" property, I'll assume that the "distribution" (and I am using this word quite loosely) of the number of ways in which n can be written as a sum of two primes is a Poisson distribution with parameter n/(2 log² n). This means that the "probability" that an even number n can't be written as a sum of two primes is

f(n) = exp(-n/(2 log² n))

which is quite small for decent-sized numbers. For n = 10,000, for example, it's about 2.5 × 10^-26. For n equal to one million, it's around 10^-1138. The sum f(2) + f(4) + f(6) + ... converges to a number somewhere around 29, and what's more it converges quite quickly. So if there's a counterexample, it's small; if we can show that Goldbach is true for, say, numbers up to a million (which is easy to do with modern computers), then this heuristic shows it's "almost certainly" true.

There's a similar heuristic argument for why there are no odd perfect numbers, due to Pomerance; unfortunately this argument shows there are no even perfect numbers, as well. But it turns out that the even perfect numbers have a special sort of structure.

And one wants to know that the primes don't have this special sort of structure -- that they are in fact psuedorandom, as Tao calls it. (I'm not sure if "psuedorandom" is a well-defined term in any branch of mathematics; Tao uses it in two different ways in his talk, and explicitly points out that his two uses are different.)

Of course, this whole idea of thinking of primes probabilistically is sort of silly. In A Mathematician's Apology*, G. H. Hardy wrote that "317 is a prime, not because we think so, or because our minds are shaped in one way rather than another, but because it is so, because mathematical reality is built that way." Yet we don't know what the really big primes are. From a philosophical standpoint, why not act as if the primes are randomly distributed until we have evidence to the contrary? Proving the Riemann hypothesis would show that this way of looking at things is indeed valid.

A note on notation: when doing mathematics "log" means the natural logarithm; I can't think of a single place where the common, or base-10, logarithm appears in mathematics. Sometime base-2 logs appear, especially in questions in the analysis of algorithms where the analysis has some sort of structure that involves breaking things up in half. Base-10 logarithms are useful as a computational aid and nothing more. At one point I was teaching a calculus class and had a form on my web page where students could leave anonymous comments about the class. (I do not recommend this technique if you have a thin skin, but it seemed like a good idea at the time.) One of the students said, essentially, "please use 'ln' instead of 'log', it confuses me when you use 'log'. I didn't know how to respond to this. Fortunately, since the comment was anonymous, I didn't have to.)