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

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?)

  • 1. 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.
  • 2. 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.
  • 3. Robert Beals and László Babai, Las Vegas algorithms for matrix groups, Proc. $34$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$_n(2)$ 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 $x^n=1$ in der symmetrischen Gruppe ${S}_n$, Arch. Math. 30 (1978), 591-594.MR 58:16851

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

American Mathematical Society