Permutations with restricted cycle structure and an algorithmic application

Let q be an integer with q ≥ 2. We give a new proof of a result of Erdös and Turán determining the proportion of elements of the finite symmetric group S_n having no cycle of length a multiple of q. We then extend our methods to the more difficult case of obtaining the proportion of such elements in the finite alternating group A_n. In both cases, we derive an asymptotic formula with error term for the above mentioned proportion, which contains an unexpected occurrence of the Gamma-function. We apply these results to estimate the proportion of elements of order 2f in S_n, and of order 3f in A_n and S_n, where gcd (2,f) = 1, and gcd(3, f) = 1, respectively, and log f is polylogarithmic in n. We also give estimates for the probability that the fth power of such elements is a transportation or a 3-cycle, respectively. An algorithmic application of these results to computing in A_n or S_n, given as a black-box group with an order oracle, is discussed.