Identifying long cycles in finite alternating and symmetric groups acting on subsets

Abstract

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,\ldots,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$.

Keywords

• Symmetric and alternating groups in subset actions, Large base permutation groups, Finding long cycles

References

1. 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, 2097-2113, 2003.
2. S. Bratus and I. Pak, Fast constructive recognition of a black box group isomorphic to Snor Anusing Goldbach’s conjecture, J. Symbolic Comput., 29(1), 33-57, 2000. GAP - Groups, The GAP Group, Algorithms, and Programming, Version 4.7.7, 2015, http://www.gap-system.org.
3. P. Erdős, and P. Turán, On some problems of a statistical group-theory. I, Wahrscheinlichkeitstheorie Verw. Gebiete, 4, 175-186, 1965.
4. P. Erdős, and P. Turán, On some problems of a statistical group-theory. III, Acta Math. Acad. Sci. Hungar., 18 , 309-320, 1967.
5. S. Linton, A. C. Niemeyer and C. E. Praeger, Constructive recognition of Snin its action on k-sets, in preparation. Y. Negi, Recognising large base actions of finite alternating groups, Honours Thesis, School of Math- ematics and Statistifcs, The University of Western Australia, 2006.
6. A. C. Niemeyer and C. E. Praeger, On permutations of order dividing a given integer, J. Algebraic Combinatorics, 26, 125-142, 2007.
7. A. C. Niemeyer and C. E. Praeger, On the proportion of permutations of order a multiple of the degree, J. London Math. Soc., 76, 622-632, 2007.
8. A. C. Niemeyer, C. E. Praeger and Á. Seress, Estimation problems and randomised group algorithms, Probabilistic group theory, combinatorics, and computing, Lecture Notes in Math., 2070, Springer, London, 35-82, 2013.

9. I. Niven, H. S. Zuckerman and H. L. Montgomery, An Introduction to the Theory of Numbers, John Wiley & Sons Inc., New York, fifth edition, 1991.
10. Á. Seress, Permutation group algorithms, Cambridge Tracts in Mathematics, 152, Cambridge Uni- versity Press, Cambridge, 2003.
11. R. Warlimont, Über die Anzahl der Lösungen von xn= 1 in der symmetrischen Gruppe Sn, Arch. Math., 30, 591-594, 1978.