Transactions of the American Mathematical Society

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

Author(s): Robert Beals; Charles R. Leedham-Green; Alice C. Niemeyer; Cheryl E. Praeger; Ákos Seress
Journal: Trans. Amer. Math. Soc. 355 (2003), 2097-2113.
MSC (2000): Primary 20P05, 20C40; Secondary 20B30, 68Q25
Posted: January 14, 2003
Retrieve article in: PDF DVI PostScript

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

of the standard permutation representation is part of the input. In a sequel, we shall treat the case when the value of

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

: the conditional probability that a random element $\sigma \in S_n$ is an

-cycle, given that $\sigma^n=1$ , is at least

1.: László Babai, Local expansion of vertex-transitive graphs and random generation in finite groups, Proc. rd ACM Sympos. Theory Comp. 1991, pp. 164-174.
2.: László Babai and Endre Szemerédi, On the complexity of matrix group problems, I, Proc. th IEEE Sympos. Foundations Comp. Sci., 1984, pp. 229-240.
3.: Robert Beals and László Babai, Las Vegas algorithms for matrix groups, Proc. rd IEEE Sympos. Foundations Comp. Sci., 1993, pp. 427-436.CMP 95:11
4.: 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.
5.: -, Constructive recognition of finite alternating and symmetric groups acting as matrix groups on their natural permutation modules, (2002), preprint.
6.: Sergei Bratus, Recognition of finite black box groups, Ph.D. thesis, Northeastern University, 1999.
7.: 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), 33-57.MR 2001c:11137
8.: Peter A. Brooksbank, Constructive recognition of the finite simple classical groups, Ph.D. thesis, University of Oregon, 2001.
9.: 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.CMP 2001:12
10.: R. D. Carmichael, Abstract definitions of the symmetric and alternating groups and certain other permutation groups, Quart. J. of Math. 49 (1923), 226-270.
11.: 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), 4931-4948.MR 96h:20115
12.: Gene Cooperman, Larry Finkelstein, and Steven A. Linton, Recognizing GL in non-standard representation, Groups and Computation II (Larry Finkelstein and William Kantor, eds.), Amer. Math. Soc. DIMACS Series, vol. 28, (DIMACS, 1995), 1997, pp. 85-100.MR 98d:20054
13.: H.S.M. Coxeter and W.O.J. Moser, Generators and relations for discrete groups, 4th ed., Ergeb. Math. Grenzgeb., vol. 14, Springer-Verlag, Berlin, Göttingen, Heidelberg, 1957.MR 81a:20001
14.: P. Erdos and P. Turán, On some problems of a statistical group-theory. I., Z. Wahrscheinlichkeitstheorie und Verw. Gebiete 4 (1965), 175-186; II., Acta Math. Acad. Sci. Hungar. 18 (1967), 151-163; III., Acta Math. Acad. Sci. Hungar. 18 (1967), 309-320; IV., Acta Math. Acad. Sci. Hungar. 19 (1968), 413-435; V., Period. Math. Hungar. 1 (1971), 5-13; VI., J. Indian Math. Soc. 34 (1970), 175-192; VII., Period. Math. Hungar. 2 (1972), 149-163. MR 32:2465; MR 34:7624; MR 35:6743; MR 38:1156; MR 44:6638; MR 58:21974; MR 56:5470
15.: William M. Kantor and Kay Magaard, Black box exceptional groups of Lie type, (2002), In preparation.
16.: William M. Kantor and Ákos Seress, Black box classical groups, Memoirs Amer. Math. Soc. 149 (2001), no. 708.MR 2001m:68066
17.: Ivan Niven, Herbert S. Zuckerman, and Hugh L. Montgomery, An Introduction to the Theory of Numbers, 5th ed., John Wiley and Sons, New York, 1991.MR 91i:11001
18.: Richard Warlimont, Über die Anzahl der Lösungen von in der symmetrischen Gruppe ${S}_n$ , Arch. Math. 30 (1978), 591-594.MR 58:16851

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

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: 10.1090/S0002-9947-03-03040-X
PII: S 0002-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
Posted: 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
Copyright of article: Copyright 2003, American Mathematical Society

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-6850(e) ISSN 0002-9947(p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues Previous Article \| Next Article


	Comments: webmaster@ams.org © Copyright 2008, American Mathematical Society Privacy Statement		Search the AMS