Permutations with restricted cycle structure and an algorithmic application

TY - JOUR

T1 - Permutations with restricted cycle structure and an algorithmic application

AU - Beals, Robert

AU - Leedham-Green, Charles R.

AU - Niemeyer, Alice C.

AU - Seress, Ákos

PY - 2002/9

Y1 - 2002/9

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0036025697&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0036025697&partnerID=8YFLogxK

U2 - https://doi.org/10.1017/S0963548302005217

DO - https://doi.org/10.1017/S0963548302005217

M3 - Article

SN - 0963-5483

VL - 11

SP - 447

EP - 464

JO - Combinatorics Probability and Computing

JF - Combinatorics Probability and Computing

IS - 5

ER -