Permutations with restricted cycle structure and an algorithmic application

Robert Beals, Charles R. Leedham-Green, Alice C. Niemeyer, Ákos Seress

Research output: Contribution to journalArticlepeer-review

16 Scopus citations


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 Sn 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 An. 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 Sn, and of order 3f in An and Sn, 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 An or Sn, given as a black-box group with an order oracle, is discussed.

Original languageEnglish (US)
Pages (from-to)447-464
Number of pages18
JournalCombinatorics Probability and Computing
Issue number5
StatePublished - Sep 2002
Externally publishedYes

ASJC Scopus subject areas

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


Dive into the research topics of 'Permutations with restricted cycle structure and an algorithmic application'. Together they form a unique fingerprint.

Cite this