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

zbMATH Open1361.20007arXiv1205.6586MaRDI QIDQ307919FDOQ307919

Authors: Alice C. Niemeyer, Cheryl E. Praeger, S. A. Linton 

Publication date: 5 September 2016

Published in: Journal of Algebra Combinatorics Discrete Structures and Applications (Search for Journal in Brave)

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$.

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

Recommendations

• Economical generating sets for the symmetric and alternating groups consisting of cycles of a fixed length.
• Fast recognition of alternating groups of unknown degree.
• A black-box group algorithm for recognizing finite symmetric and alternating groups, I
• Symmetric and alternating groups generated by a full cycle and another element.
• Finite primitive permutation groups and regular cycles of their elements.

zbMATH Keywords

finding long cycleslarge base permutation groupssymmetric and alternating groups in subset actions

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Combinatorial probability (60C05) Symmetric groups (20B30) Probabilistic methods in group theory (20P05)

Cites Work

• Title not available (Why is that?)
• On some problems of a statistical group-theory. III
• Title not available (Why is that?)
• Über die Anzahl der Lösungen von \(x^n=1\) in der symmetrischen Gruppe \(S_n\)
• Fast constructive recognition of a black box group isomorphic to \(S_n\) or \(A_n\) using Goldbach's conjecture
• On permutations of order dividing a given integer
• Estimation problems and randomised group algorithms.
• A black-box group algorithm for recognizing finite symmetric and alternating groups, I
• On the proportion of permutations of order a multiple of the degree
• On some problems of a statistical group-theory. I

Cited In (2)

• Bijections and symmetries for the factorizations of the long cycle
• Finding a cycle base of a permutation group in polynomial time

Uses Software

• GAP

This page was built for publication: Identifying long cycles in finite alternating and symmetric groups acting on subsets

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