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

Beals, Robert; Leedham-Green, Charles; Niemeyer, Alice; Praeger, Cheryl; Seress, Ákos

doi:10.1090/S0002-9947-03-03040-X

A black-box group algorithm for recognizing finite symmetric and alternating groups, I
HTML articles powered by AMS MathViewer

by Robert Beals, Charles R. Leedham-Green, Alice C. Niemeyer, Cheryl E. Praeger and Ákos Seress PDF

Trans. Amer. Math. Soc. 355 (2003), 2097-2113 Request permission

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

László Babai, Local expansion of vertex-transitive graphs and random generation in finite groups, Proc. $23$rd ACM Sympos. Theory Comp. 1991, pp. 164–174.
László Babai and Endre Szemerédi, On the complexity of matrix group problems, I, Proc. $25$th IEEE Sympos. Foundations Comp. Sci., 1984, pp. 229–240.
Robert Beals and László Babai, Las Vegas algorithms for matrix groups, Proc. $34$rd IEEE Sympos. Foundations Comp. Sci., 1993, pp. 427–436.
Robert Beals, Charles Leedham-Green, Alice Niemeyer, Cheryl Praeger, and Ákos Seress, A black-box algorithm for recognizing finite symmetric and alternating groups, II, (2002), preprint.
—, Constructive recognition of finite alternating and symmetric groups acting as matrix groups on their natural permutation modules, (2002), preprint.
Sergei Bratus, Recognition of finite black box groups, Ph.D. thesis, Northeastern University, 1999.
Sergey Bratus and Igor Pak, Fast constructive recognition of a black box group isomorphic to $S_n$ or $A_n$ using Goldbach’s conjecture, J. Symbolic Comput. 29 (2000), no. 1, 33–57. MR 1743388, DOI 10.1006/jsco.1999.0295
Peter A. Brooksbank, Constructive recognition of the finite simple classical groups, Ph.D. thesis, University of Oregon, 2001.
Peter A. Brooksbank and William M. Kantor, On constructive recognition of a black box ${\mathrm {{P}{S}{L}}}(d,q)$, Groups and Computation III (William M. Kantor and Ákos Seress, eds.), OSU Mathematical Research Institute Publications, vol. 8, Walter de Gruyter, 2001, pp. 95–111.
R. D. Carmichael, Abstract definitions of the symmetric and alternating groups and certain other permutation groups, Quart. J. of Math. 49 (1923), 226–270.
Frank Celler, Charles R. Leedham-Green, Scott H. Murray, Alice C. Niemeyer, and E. A. O’Brien, Generating random elements of a finite group, Comm. Algebra 23 (1995), no. 13, 4931–4948. MR 1356111, DOI 10.1080/00927879508825509
Gene Cooperman, Larry Finkelstein, and Steve Linton, Constructive recognition of a black box group isomorphic to $\textrm {GL}(n,2)$, Groups and computation, II (New Brunswick, NJ, 1995) DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol. 28, Amer. Math. Soc., Providence, RI, 1997, pp. 85–100. MR 1444132, DOI 10.1090/dimacs/028/07
H. S. M. Coxeter and W. O. J. Moser, Generators and relations for discrete groups, 4th ed., Ergebnisse der Mathematik und ihrer Grenzgebiete [Results in Mathematics and Related Areas], vol. 14, Springer-Verlag, Berlin-New York, 1980. MR 562913, DOI 10.1007/978-3-662-21943-0
Louis Weisner, Condition that a finite group be multiply isomorphic with each of its irreducible representations, Amer. J. Math. 61 (1939), 709–712. MR 32, DOI 10.2307/2371325
William M. Kantor and Kay Magaard, Black box exceptional groups of Lie type, (2002), In preparation.
William M. Kantor and Ákos Seress, Black box classical groups, Mem. Amer. Math. Soc. 149 (2001), no. 708, viii+168. MR 1804385, DOI 10.1090/memo/0708
Ivan Niven, Herbert S. Zuckerman, and Hugh L. Montgomery, An introduction to the theory of numbers, 5th ed., John Wiley & Sons, Inc., New York, 1991. MR 1083765
Richard Warlimont, Über die Anzahl der Lösungen von $x^{n}=1$ in der symmetrischen Gruppe $S_{n}$, Arch. Math. (Basel) 30 (1978), no. 6, 591–594 (German). MR 498814, DOI 10.1007/BF01226105