Let \(S_ n\) be the symmetric group on n letters, and let N(\(\sigma)\) denote the group-theoretic order of \(\sigma\), for \(\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(\(\sigma)\) has an asymptotically normal distribution with mean \(2^{-1} \log^ 2n\) and standard deviation \(3^{-1/2} \log^{3/2}n\). For new proofs, see \textit{M. R. Best} [Indagationes Math. 32, 385-402 (1970; Zbl 0208.033)] 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. Acad. Sci. Hung. 45, 69-84 (1985; Zbl 0574.10044)]. Let \(\mu_ n\) denote the expectation of N, i.e., \(\mu_ n=\sum_{\sigma \in S_ 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)] estimated the number of different values of N(\(\sigma)\) in \(S_ n\). They promised a proof of the estimation log \(\mu_ n=O((n/\log n)^{1/2})\) but this proof never materialized. In the paper under review the author proves the conjecture of Erdős and Turán in the following form: \[ \log \mu_ n\quad <\quad 7.7(n/\log n)^{1/2}. \] The proof uses the result of P. Erdős and P. Turán on the number of different values of N(\(\sigma)\), a theorem of D. H. Lehmer about reciprocally weighted partitions and a logarithmically asymptotic result of the author for the number of partitions of n into parts that are pairwise relatively prime. The paper is closed with the following problem: Prove or disprove that log \(\mu_ n \sim 2\pi 6^{-1/2}(n/\log n)^{1/2}\).
- Distribution statistique de l'ordre d'un élément du groupe symétrique. (Statistical distribution of the order of an element of the symmetric group)
- Efficiency of a Good But Not Linear Set Union Algorithm
- scientific article; zbMATH DE number 3824115 (Why is no real title available?)
- On reciprocally weighted partitions
- On some problems of a statistical group-theory. IV
- Partitions whose parts are pairwise relatively prime
- Three problems in combinatorial asymptotics
- The average order of a matrix
- Subgroups of cyclic groups and values of the Riemann zeta function
- A proof of Pyber's base size conjecture
- Proof of a conjecture of Bollobás and Kohayakawa on the Erdős-Stone theorem
- Proof of Tomaszewski's conjecture on randomly signed sums
- Current trends in asymptotics: Some problems and some solutions
- The Expected order of a Random Permutation
- scientific article; zbMATH DE number 108289 (Why is no real title available?)
- scientific article; zbMATH DE number 3595272 (Why is no real title available?)
- Characterizing finite groups using the sum of the orders of the elements.
- scientific article; zbMATH DE number 796185 (Why is no real title available?)
- A proof of the Erdős-Faber-Lovász conjecture
- Proof of a conjecture by Erdős and Graham concerning the problem of Frobenius
This page was built for publication: Proof of a conjecture of Erdős and Turán
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1121937)
