On the frequency of permutations containing a long cycle

Abstract

A general explicit upper bound is obtained for the proportion \(P(n,m)\) of elements of order dividing \(m\), where \(n-1 \le m \le cn\) for some constant \(c\), in the finite symmetric group \(S_n\). This is used to find lower bounds for the conditional probabilities that an element of \(S_n\) or \(A_n\) contains an \(r\)-cycle, given that it satisfies an equation of the form \(x^{rs}=1\) where \(s\leq3\). For example, the conditional probability that an element \(x\) is an \(n\)-cycle, given that \(x^n=1\), is always greater than 2/7, and is greater than 1/2 if \(n\) does not divide 24. Our results improve estimates of these conditional probabilities in earlier work of the authors with Beals, Leedham-Green and Seress, and have applications for analysing black-box recognition algorithms for the finite symmetric and alternating groups.