The Expected order of a Random Permutation

From MaRDI portal





Let \(S_n\) be the symmetric group on \(n\) letters, and let \(N_n(\sigma)\) denote the group-theoretic order of \(\sigma\in S_n\). \textit{P. Erdős} and \textit{P. Turán} [Acta Math. Acad. Sci. Hung. 18, 309--320 (1967; Zbl 0235.20003)] proved that \(\log N_n(\sigma)\) has an asymptotically normal distribution with mean \(2^{-1}\log^2n\) and standard deviation \(3^{-1/2}\log^{3/2}n\). For other proofs, see \textit{M. R. Best} [Nederl. Akad. Wet., Proc., Ser. A 73, 385--402 (1970; Zbl 0208.03303)] and \textit{J. D. Bovey} [Bull. Lond. Math. Soc. 12, 41--46 (1980; Zbl 0436.20001)]. For a refined version, see \textit{J.-L. Nicolas} [Acta Math. Hung. 45, 69--84 (1985; Zbl 0574.10044)]. Let \(\mu_n\) denote the expectation of \(N_n\), i.e., \(\mu_n=\sum_{\sigma\in S_n} N_n(\sigma)/n!\). \textit{P. Erdős} and \textit{P. Turán} [Acta Math. Acad. Sci. Hung. 19, 413--435 (1968; Zbl 0235.20004)] mentioned the estimation \(\log \mu_n = O((n/\log n)^{1/2})\) without proof. \textit{E. Schmutz} [J. Number Theory 31, 260--271 (1989; Zbl 0675.10033)] proved that \(\log \mu_n < 7.7(n/\log n)^{1/2}\). In the paper under review the authors prove that \(\log \mu_n\sim c(n/\log n)^{1/2}\) where \(c=2(2\int^ \infty_0 \log\log(e/(1-e^{-t})) \,dt)^{1/2}\). The proof compares \(\mu_n\) with the sum of the weights of a certain set of weighted partitions of \(n\).











This page was built for publication: The Expected order of a Random Permutation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3978865)