On the Erdős-Turán theorem on the logarithm of the order of a random permutation
type: Item
instance of: scholarly article
title: On the Erdős-Turán theorem on the logarithm of the order of a random permutation
zbMATH Open document ID: 0894.05004
author: A. I. Pavlov
published in: Doklady Mathematics
publication date: 1998-06-23T00:00:00Z
review text: 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)], \textit{P. Erdős} and \textit{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.
Mathematics Subject Classification ID: 05A05
Mathematics Subject Classification ID: 60C05
Mathematics Subject Classification ID: 11K99
zbMATH DE Number: 1148058
zbMATH Keywords: uniform probability distribution
zbMATH Keywords: random permutation
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 1148058