Steve Linton, Alice C. Niemeyer, Cheryl E. Praeger

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

Let $H$ be a permutation group on a set $\Lambda$, which is permutationallyisomorphic to a finite alternating or symmetric group $A_n$ or $S_n$ actingon the $k$-element subsets of points from $\{1,\ldots,n\}$, for somearbitrary but fixed $k$. Suppose moreover that no isomorphism with thisaction is known. We show that key elements of $H$ needed to construct suchan isomorphism $\varphi$, such as those whose image under $\varphi$ is an $n$%-cycle or $(n-1)$-cycle, can be recognised with high probability by thelengths of just four of their cycles in $\Lambda$.

Keywords:

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

PDF

___

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.
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.
P. Erdős, and P. Turán, On some problems of a statistical group-theory. I, Wahrscheinlichkeitstheorie Verw. Gebiete, 4, 175-186, 1965.
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.
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.
A. C. Niemeyer and C. E. Praeger, On permutations of order dividing a given integer, J. Algebraic Combinatorics, 26, 125-142, 2007.
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.
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.
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.
Á. Seress, Permutation group algorithms, Cambridge Tracts in Mathematics, 152, Cambridge Uni- versity Press, Cambridge, 2003.
R. Warlimont, Über die Anzahl der Lösungen von xn= 1 in der symmetrischen Gruppe Sn, Arch. Math., 30, 591-594, 1978.