On the frequency of permutations containing a long cycle.

DOI10.1016/J.JALGEBRA.2006.02.026MaRDI QIDQ2496867zbMATH OpenOpenAlexWikidataFDO

Authors Alice C. Niemeyer, Cheryl E. Praeger

Publication date 20 July 2006

Published in Journal of Algebra (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0603554

zbMATH Keywords

black-box recognition algorithmsconditional probabilitiescyclesfinite alternating groupsfinite symmetric groups

Mathematics Subject Classification ID

Symmetric groups (20B30) Probabilistic methods in group theory (20P05) Combinatorial probability (60C05)

Abstract: A general explicit upper bound is obtained for the proportion $P(n,m)$ of elements of order dividing $m$, where $n-1lemlecn$ 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 $sleq3$. 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.

Recommendations

• On permutations of order dividing a given integer
• On the proportion of permutations of order a multiple of the degree
• Distribution statistique de l'ordre d'un élément du groupe symétrique. (Statistical distribution of the order of an element of the symmetric group)
• The probability of generating the symmetric group
• Permutations with Restricted Cycle Structure and an Algorithmic Application

Cites work

• A black-box group algorithm for recognizing finite symmetric and alternating groups, I
• scientific article; zbMATH DE number 51347 (Why is no real title available?)
• On permutations of order dividing a given integer
• On some problems of a statistical group-theory. I
• On some problems of a statistical group-theory. III
• On the frequency of permutations containing a long cycle.
• On the proportion of permutations of order a multiple of the degree

Cited in

(7)

• The average number of cycles.
• Proportions of elements with given 2-part order in finite classical groups of odd characteristic.
• On permutations of order dividing a given integer
• On the frequency of permutations containing a long cycle.
• Permutations with Restricted Cycle Structure and an Algorithmic Application
• On the proportion of permutations of order a multiple of the degree
• Using recurrence relations to count certain elements in symmetric groups

Describes a project that uses

Uses Software

• GAP

This page was built for publication: On the frequency of permutations containing a long cycle.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2496867)