A black-box group algorithm for recognizing finite symmetric and alternating groups, I
Loading...
Date
2003
Journal Title
Journal ISSN
Volume Title
Publisher
American Mathematical Society
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 is an element of S-n is an n-cycle, given that sigma(n) = 1, is at least 1/10.
Description
First published in Transactions of the American Mathematical Society in volume 355, issue 5, published by the American Mathematical Society.
Keywords
Citation
Robert Beals et al, "A black-box group algorithm for recognizing finite symmetric and alternating groups, I," Transcations of the American Mathematical Society 355, no. 5 (2003), doi:10.1090/S0002-9947-03-03040-X