Identifying long cycles in finite alternating and symmetric groups acting on subsets
DOI:
https://doi.org/10.13069/jacodesmath.28239Keywords:
Symmetric and alternating groups in subset actions, Large base permutation groups, Finding long cyclesAbstract
Let $H$ be a permutation group on a set $\Lambda$, which is permutationally isomorphic to a finite alternating or symmetric group $A_n$ or $S_n$ acting on the $k$-element subsets of points from $\{1,...,n\}$, for some arbitrary but fixed $k$. Suppose moreover that no isomorphism with this action is known. We show that key elements of $H$ needed to construct such an isomorphism $\varphi$, such as those whose image under $\varphi$ is an $n$-cycle or $(n-1)$-cycle, can be recognised with high probability by the lengths of just four of their cycles in $\Lambda$.
Downloads
References
R. M. Beals, C. R. Leedham-Green, A. C. Niemeyer, C. E. Praeger, and Á. Seress, A black-box algorithm for recognizing finite symmetric and alternating groups, I, Trans. Amer. Math. Soc. 355 (2003) 2097-2113.
S. Bratus and I. Pak, Fast constructive recognition of a black box group isomorphic to $S_n$ or $A_n$ using Goldbach's conjecture, J. Symbolic Comput. 29(1) (2000) 33-57.
The GAP Group, GAP - Groups, Algorithms, and Programming, Version 4.7.7 (2015).
P. Erdős and P. Turán, On some problems of a statistical group-theory. I, Z. Wahrscheinlichkeitstheorie Verw. Gebiete 4 (1965) 175-186.
P. Erdős and P. Turán, On some problems of a statistical group-theory. III, Acta Math. Acad. Sci. Hungar. 18 (1967) 309-320.
S. Linton, A. C. Niemeyer, and C. E. Praeger, Constructive recognition of $S_n$ in its action on $k$-sets, in preparation.
Y. Negi, Recognising large base actions of finite alternating groups, Honours Thesis, School of Mathematics and Statistics, The University of Western Australia (2006).
A. C. Niemeyer and C. E. Praeger, On permutations of order dividing a given integer, J. Algebraic Combin. 26 (2007) 125-142.
A. C. Niemeyer and C. E. Praeger, On the proportion of permutations of order a multiple of the degree, J. London Math. Soc. 76 (2007) 622-632.
A. C. Niemeyer, C. E. Praeger, and Á. Seress, Estimation problems and randomised group algorithms, in Probabilistic Group Theory, Combinatorics, and Computing, Lecture Notes in Math. 2070, Springer, London (2013) 35-82.
I. Niven, H. S. Zuckerman, and H. L. Montgomery, An Introduction to the Theory of Numbers, 5th Edition, John Wiley & Sons, New York (1991).
Á. Seress, Permutation Group Algorithms, Cambridge Tracts in Mathematics 152, Cambridge University Press, Cambridge (2003).
R. Warlimont, Über die Anzahl der Lösungen von $x^n = 1$ in der symmetrischen Gruppe $S_n$, Arch. Math. 30 (1978) 591-594.
