Proof of a conjecture of Erdős and Turán (Q1121937)

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}\).