We study random generation in the symmetric group when cycle type restrictions are imposed. Given , we prove that and a random conjugate of are likely to generate at least provided only that and have not too many fixed points and not too many -cycles. As an application, we investigate the following question: For which positive integers should we expect two random elements of order to generate ? Among other things, we give a positive answer for any having any divisor in the range .
Revised:
Accepted:
Published online:
Classification: 20B30, 20P05
Keywords: symmetric group, random generation.
@article{ALCO_2021__4_1_1_0, author = {Eberhard, Sean and Garzoni, Daniele}, title = {Random generation with cycle type restrictions}, journal = {Algebraic Combinatorics}, pages = {1--25}, publisher = {MathOA foundation}, volume = {4}, number = {1}, year = {2021}, doi = {10.5802/alco.149}, language = {en}, url = {https://alco.centre-mersenne.org/articles/10.5802/alco.149/} }
Eberhard, Sean; Garzoni, Daniele. Random generation with cycle type restrictions. Algebraic Combinatorics, Volume 4 (2021) no. 1, pp. 1-25. doi : 10.5802/alco.149. https://alco.centre-mersenne.org/articles/10.5802/alco.149/
[1] The probability of generating the symmetric group, J. Combin. Theory Ser. A, Volume 52 (1989) no. 1, pp. 148-153 | Article | MR 1008166 | Zbl 0685.60012
[2] The probability of generating the symmetric group when one of the generators is random, Publ. Math. Debrecen, Volume 69 (2006) no. 3, pp. 271-280 | MR 2273979 | Zbl 1123.20003
[3] On fixed points of permutations, J. Algebraic Combin., Volume 28 (2008) no. 1, pp. 189-218 | Article | MR 2420785 | Zbl 1192.20001
[4] The probability of generating the symmetric group, Math. Z., Volume 110 (1969), pp. 199-205 | Article | MR 0251758 | Zbl 0176.29901
[5] Permutations contained in transitive subgroups, Discrete Anal. (2016), Paper no. 12, 34 pages | Article | MR 3555195 | Zbl 1346.05005
[6] Analytic combinatorics, Cambridge University Press, Cambridge, 2009, xiv+810 pages | Article | MR 2483235 | Zbl 1165.05001
[7] On the O’Nan–Scott theorem for finite primitive permutation groups, J. Austral. Math. Soc. Ser. A, Volume 44 (1988) no. 3, pp. 389-396 | Article | MR 929529 | Zbl 0647.20005
[8] Classical groups, probabilistic methods, and the -generation problem, Ann. of Math. (2), Volume 144 (1996) no. 1, pp. 77-125 | Article | MR 1405944 | Zbl 0865.20020
[9] Fuchsian groups, coverings of Riemann surfaces, subgroup growth, random quotients and random walks, J. Algebra, Volume 276 (2004) no. 2, pp. 552-601 | Article | MR 2058457 | Zbl 1068.20052
[10] On random generation of the symmetric group, Combin. Probab. Comput., Volume 2 (1993) no. 4, pp. 505-512 | Article | MR 1264722 | Zbl 0817.20002
[11] Random generation of simple groups by two conjugate elements, Bull. London Math. Soc., Volume 29 (1997) no. 5, pp. 571-576 | Article | MR 1458717 | Zbl 0904.20020