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