Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 

 

A black-box group algorithm for recognizing finite symmetric and alternating groups, I


Authors: Robert Beals, Charles R. Leedham-Green, Alice C. Niemeyer, Cheryl E. Praeger and Ákos Seress
Journal: Trans. Amer. Math. Soc. 355 (2003), 2097-2113
MSC (2000): Primary 20P05, 20C40; Secondary 20B30, 68Q25
DOI: https://doi.org/10.1090/S0002-9947-03-03040-X
Published electronically: January 14, 2003
MathSciNet review: 1953539
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We present a Las Vegas algorithm which, for a given black-box group known to be isomorphic to a symmetric or alternating group, produces an explicit isomorphism with the standard permutation representation of the group. This algorithm has applications in computations with matrix groups and permutation groups.

In this paper, we handle the case when the degree $n$ of the standard permutation representation is part of the input. In a sequel, we shall treat the case when the value of $n$ is not known in advance.

As an important ingredient in the theoretical basis for the algorithm, we prove the following result about the orders of elements of $S_n$: the conditional probability that a random element $\sigma \in S_n$is an $n$-cycle, given that $\sigma^n=1$, is at least $1/10$.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2000): 20P05, 20C40, 20B30, 68Q25

Retrieve articles in all journals with MSC (2000): 20P05, 20C40, 20B30, 68Q25


Additional Information

Robert Beals
Affiliation: IDA Center for Communications Research, 805 Bunn Drive, Princeton, New Jersey 08540, USA
Email: beals@idaccr.org

Charles R. Leedham-Green
Affiliation: School of Mathematical Sciences, Queen Mary and Westfield College, London E1 4NS, United Kingdom
Email: crlg@maths.qmw.ac.uk

Alice C. Niemeyer
Affiliation: Department of Mathematics and Statistics, University of Western Australia, Crawley, Western Australia 6009, Australia
Email: alice@maths.uwa.edu.au

Cheryl E. Praeger
Affiliation: Department of Mathematics and Statistics, University of Western Australia, Crawley, Western Australia 6009, Australia
Email: praeger@maths.uwa.edu.au

Ákos Seress
Affiliation: Department of Mathematics, The Ohio State University, Columbus, Ohio 43210, USA
Email: akos@math.ohio-state.edu.

DOI: https://doi.org/10.1090/S0002-9947-03-03040-X
Keywords: Black-box groups, constructive recognition, symmetric groups, probabilistic method
Received by editor(s): September 1, 2000
Received by editor(s) in revised form: February 18, 2002
Published electronically: January 14, 2003
Additional Notes: The third and fourth authors are partially supported by an Australian Research Council Large Grant
The fifth author is partially supported by the National Science Foundation
Article copyright: © Copyright 2003 American Mathematical Society