×

zbMATH — the first resource for mathematics

On the Erdős-Turán theorem on the logarithm of the order of a random permutation. (English. Russian original) Zbl 0894.05004
Dokl. Math. 54, No. 2, 688-691 (1996); translation from Dokl. Akad. Nauk, Ross. Akad. Nauk 350, No. 2, 170-173 (1996).
Let \(S_n\) be the symmetrical group of degree \(n\), i.e., the set of all permutations of the numbers \(1,2,\dots, n\). We introduce a uniform probability distribution on \(S_n\) by assigning the probability \(\frac{1}{n!}\) to each permutation \(T\in S_n\). Let \(O_n(T)\) be the order of a permutation \(T\) as an element of the finite group \(S_n\), i.e., the least integer \(k\geq 1\) such that the permutation \(T^k\) is the identity. In the work [Acta Math. Acad. Sci. Hung. 18, 309-320 (1967; Zbl 0235.20003)], P. Erdős and P. Turán proved that for fixed \(x\in (-\infty,\infty)\), the equality \[ \lim_{n\to\infty} {\mathbf P} \Biggl\{ \ln O_n(T)- \frac 12 \ln^2n< x\biggl( \frac 13 \ln^3 n\biggr)^{1/2} \Biggr\}= \frac{1}{\sqrt{2\pi}} \int_{-\infty}^x e^{-t^2/2} dt \] holds, where \({\mathbf P}\{\lambda< C\}\) is the probability that \(\lambda<C\).
We show that this result can be augmented as follows.
Let \(S_n^{(1)}\) be the set of permutations of degree \(n\), each containing no cycles of equal lengths. We introduce a uniform probability distribution on \(S_n^{(1)}\) by assigning the probability \(| S_n^{(1)}|^{-1}\), where \(| S_n^{(1)}|\) is the number of elements in the finite set \(S_n^{(1)}\), to each permutation \(T\in S_n^{(1)}\). Let us consider the random variable \(\eta_n= \ln O_n\), where \(O_n= O_n(T)\) is the order of the random permutation \(T\in S_n^{(1)}\). Theorem: If \(\eta_n'= (\eta_n- \frac 12 \ln^2n) (\frac 13 \ln^3n)^{-1/2}\) and \(x\in (-\infty,\infty)\) is fixed, then \[ \lim_{n\to\infty}{\mathbf P} \{\eta_n'<x\}= \frac{1}{\sqrt{2\pi}} \int_{-\infty}^x e^{-t^2/2} dt. \] This theorem can easily be extended to the set \(S_n^{(k)}\) of permutations of degree \(n\) each having not more than \(k\) cycles of equal lengths.

MSC:
05A05 Permutations, words, matrices
60C05 Combinatorial probability
11K99 Probabilistic theory: distribution modulo \(1\); metric theory of algorithms
PDF BibTeX XML Cite