## Abstract

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.

Original language | English (US) |
---|---|

Pages (from-to) | 447-464 |

Number of pages | 18 |

Journal | Combinatorics Probability and Computing |

Volume | 11 |

Issue number | 5 |

DOIs | |

State | Published - Sep 2002 |

Externally published | Yes |

## All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Statistics and Probability
- Computational Theory and Mathematics
- Applied Mathematics