19 December 2008

Erdos papers available online, and the Erdos-Turan law for the order of elements in the symmetric group

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 Xn be the order of a permutation in Sn selected uniformly at random. Then

\lim_{n \to \infty} {\rm Prob} \left( {\log X_n - {1 \over 2} \log^2  n \over \sqrt{{1 \over 3} \log^3 n} } < y \right) = \Phi(y)


where Φ is the cumulative distribution function of a standard normal random variable. Informally, log Xn is normally distributed with mean (log2 n)/2 and variance (log3 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.

1 comment:

Anonymous said...

Nice to meet you!!!
[URL=http://superjonn.50webs.com/restaurant-week-new-york-january.html]restaurant week new york january[/URL]