Black box exceptional groups of Lie type
HTML articles powered by AMS MathViewer
- by W. M. Kantor and K. Magaard PDF
- Trans. Amer. Math. Soc. 365 (2013), 4895-4931 Request permission
Abstract:
If a black box group is known to be isomorphic to an exceptional simple group of Lie type of (twisted) rank $>1$, other than any $^2\kern -.8pt F_4(q)$, over a field of known size, a Las Vegas algorithm is given to produce a constructive isomorphism. In view of its timing, this algorithm yields an upgrade of all known nearly linear time Monte Carlo permutation group algorithms to Las Vegas algorithms when the input group has no composition factor isomorphic to any group $^2\kern -.8pt F_4(q)$ or $^2G_2(q)$.References
- Henrik Bäärnhielm, Recognising the Suzuki groups in their natural representations, J. Algebra 300 (2006), no. 1, 171–198. MR 2228642, DOI 10.1016/j.jalgebra.2006.02.010
- H. Bäärnhielm, Tensor decomposition of the Suzuki groups (unpublished).
- H. Bäärnhielm, Recognising the Ree groups in their natural representations (unpublished).
- H. Bäärnhielm, Algorithmic problems in twisted groups of Lie type. Ph.D. thesis, Queen Mary, U. of London 2007.
- L. Babai, Local expansion of vertex-transitive graphs and random generation in finite groups, pp. 164–174 in: Proc. ACM Symp. on Theory of Computing 1991.
- László Babai and Robert Beals, A polynomial-time theory of black box groups. I, Groups St. Andrews 1997 in Bath, I, London Math. Soc. Lecture Note Ser., vol. 260, Cambridge Univ. Press, Cambridge, 1999, pp. 30–64. MR 1676609
- L. Babai, A. J. Goodman, W. M. Kantor, E. M. Luks, and P. P. Pálfy, Short presentations for finite groups, J. Algebra 194 (1997), no. 1, 79–112. MR 1461483, DOI 10.1006/jabr.1996.6980
- László Babai, William M. Kantor, Péter P. Pálfy, and Ákos Seress, Black-box recognition of finite simple groups of Lie type by statistics of element orders, J. Group Theory 5 (2002), no. 4, 383–401. MR 1931364, DOI 10.1515/jgth.2002.010
- Robert Beals, Charles R. Leedham-Green, Alice C. Niemeyer, Cheryl E. Praeger, and Ákos Seress, A black-box group algorithm for recognizing finite symmetric and alternating groups. I, Trans. Amer. Math. Soc. 355 (2003), no. 5, 2097–2113. MR 1953539, DOI 10.1090/S0002-9947-03-03040-X
- Alexandre V. Borovik, Centralisers of involutions in black box groups, Computational and statistical group theory (Las Vegas, NV/Hoboken, NJ, 2001) Contemp. Math., vol. 298, Amer. Math. Soc., Providence, RI, 2002, pp. 7–20. MR 1929713, DOI 10.1090/conm/298/05111
- John N. Bray, An improved method for generating the centralizer of an involution, Arch. Math. (Basel) 74 (2000), no. 4, 241–245. MR 1742633, DOI 10.1007/s000130050437
- J. N. Bray and H. Bäärnhielm, Standard generators for the Suzuki groups (unpublished).
- Peter A. Brooksbank, Constructive recognition of classical groups in their natural representation, J. Symbolic Comput. 35 (2003), no. 2, 195–239. MR 1958954, DOI 10.1016/S0747-7171(02)00132-3
- Peter A. Brooksbank, Fast constructive recognition of black-box unitary groups, LMS J. Comput. Math. 6 (2003), 162–197. MR 2051584, DOI 10.1112/S1461157000000437
- Peter A. Brooksbank, Fast constructive recognition of black box symplectic groups, J. Algebra 320 (2008), no. 2, 885–909. MR 2422320, DOI 10.1016/j.jalgebra.2008.03.021
- Peter A. Brooksbank and William M. Kantor, On constructive recognition of a black box $\textrm {PSL}(d,q)$, Groups and computation, III (Columbus, OH, 1999) Ohio State Univ. Math. Res. Inst. Publ., vol. 8, de Gruyter, Berlin, 2001, pp. 95–111. MR 1829473
- Peter A. Brooksbank and William M. Kantor, Fast constructive recognition of black box orthogonal groups, J. Algebra 300 (2006), no. 1, 256–288. MR 2228648, DOI 10.1016/j.jalgebra.2006.02.024
- Roger W. Carter, Simple groups of Lie type, Pure and Applied Mathematics, Vol. 28, John Wiley & Sons, London-New York-Sydney, 1972. MR 0407163
- Roger W. Carter, Finite groups of Lie type, Pure and Applied Mathematics (New York), John Wiley & Sons, Inc., New York, 1985. Conjugacy classes and complex characters; A Wiley-Interscience Publication. MR 794307
- A. M. Cohen, S. Haller and S. H. Murray, Computing with root subgroups of twisted reductive groups (preprint).
- F. Celler and C. R. Leedham-Green, A constructive recognition algorithm for the special linear group, The atlas of finite groups: ten years on (Birmingham, 1995) London Math. Soc. Lecture Note Ser., vol. 249, Cambridge Univ. Press, Cambridge, 1998, pp. 11–26. MR 1647410, DOI 10.1017/CBO9780511565830.007
- 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
- Arjeh M. Cohen and Scott H. Murray, An algorithm for Lang’s Theorem, J. Algebra 322 (2009), no. 3, 675–702. MR 2531217, DOI 10.1016/j.jalgebra.2009.04.013
- Arjeh M. Cohen, Scott H. Murray, and D. E. Taylor, Computing in groups of Lie type, Math. Comp. 73 (2004), no. 247, 1477–1498. MR 2047097, DOI 10.1090/S0025-5718-03-01582-5
- Arjeh M. Cohen and Dan Roozemond, Computing Chevalley bases in small characteristics, J. Algebra 322 (2009), no. 3, 703–721. MR 2531218, DOI 10.1016/j.jalgebra.2009.04.038
- 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
- Marston Conder and Charles R. Leedham-Green, Fast recognition of classical groups over large fields, Groups and computation, III (Columbus, OH, 1999) Ohio State Univ. Math. Res. Inst. Publ., vol. 8, de Gruyter, Berlin, 2001, pp. 113–121. MR 1829474
- M. D. E. Conder, C. R. Leedham-Green, and E. A. O’Brien, Constructive recognition of $\textrm {PSL}(2,q)$, Trans. Amer. Math. Soc. 358 (2006), no. 3, 1203–1221. MR 2187651, DOI 10.1090/S0002-9947-05-03756-6
- Bruce N. Cooperstein, The geometry of root subgroups in exceptional groups. I, Geom. Dedicata 8 (1979), no. 3, 317–381. MR 550374, DOI 10.1007/BF00151515
- Charles W. Curtis, William M. Kantor, and Gary M. Seitz, The $2$-transitive permutation representations of the finite Chevalley groups, Trans. Amer. Math. Soc. 218 (1976), 1–59. MR 422440, DOI 10.1090/S0002-9947-1976-0422440-8
- D. I. Deriziotis and A. P. Fakiolas, The maximal tori in the finite Chevalley groups of type $E_6,$ $E_7$ and $E_8$, Comm. Algebra 19 (1991), no. 3, 889–903. MR 1102992, DOI 10.1080/00927879108824176
- Leonard Eugene Dickson, Linear groups: With an exposition of the Galois field theory, Dover Publications, Inc., New York, 1958. With an introduction by W. Magnus. MR 0104735
- John D. Dixon, Generating random elements in finite groups, Electron. J. Combin. 15 (2008), no. 1, Research Paper 94, 13. MR 2426157
- Peter Fleischmann and Ingo Janiszczak, The semisimple conjugacy classes and the generic class number of the finite simple groups of Lie type $E_8$, Comm. Algebra 22 (1994), no. 6, 2221–2303. MR 1268550, DOI 10.1080/00927879408824962
- Daniel Gorenstein, Richard Lyons, and Ronald Solomon, The classification of the finite simple groups. Number 3. Part I. Chapter A, Mathematical Surveys and Monographs, vol. 40, American Mathematical Society, Providence, RI, 1998. Almost simple $K$-groups. MR 1490581, DOI 10.1090/surv/040.3
- R. M. Guralnick, W. M. Kantor, M. Kassabov, and A. Lubotzky, Presentations of finite simple groups: a quantitative approach, J. Amer. Math. Soc. 21 (2008), no. 3, 711–774. MR 2393425, DOI 10.1090/S0894-0347-08-00590-0
- R. M. Guralnick, W. M. Kantor, M. Kassabov, and A. Lubotzky, Presentations of finite simple groups: a computational approach, J. Eur. Math. Soc. (JEMS) 13 (2011), no. 2, 391–458. MR 2746771, DOI 10.4171/JEMS/257
- Robert Guralnick, Tim Penttila, Cheryl E. Praeger, and Jan Saxl, Linear groups with orders having certain large prime divisors, Proc. London Math. Soc. (3) 78 (1999), no. 1, 167–214. MR 1658168, DOI 10.1112/S0024611599001616
- P. E. Holmes, S. A. Linton, E. A. O’Brien, A. J. E. Ryba, and R. A. Wilson, Constructive membership in black-box groups, J. Group Theory 11 (2008), no. 6, 747–763. MR 2466905, DOI 10.1515/JGT.2008.047
- William M. Kantor, Subgroups of classical groups generated by long root elements, Trans. Amer. Math. Soc. 248 (1979), no. 2, 347–379. MR 522265, DOI 10.1090/S0002-9947-1979-0522265-1
- William M. Kantor, Primitive permutation groups of odd degree, and an application to finite projective planes, J. Algebra 106 (1987), no. 1, 15–45. MR 878466, DOI 10.1016/0021-8693(87)90019-6
- William M. Kantor, Simple groups in computational group theory, Proceedings of the International Congress of Mathematicians, Vol. II (Berlin, 1998), 1998, pp. 77–86. MR 1648058
- Peter B. Kleidman, The maximal subgroups of the Chevalley groups $G_2(q)$ with $q$ odd, the Ree groups $^2G_2(q)$, and their automorphism groups, J. Algebra 117 (1988), no. 1, 30–71. MR 955589, DOI 10.1016/0021-8693(88)90239-6
- Peter B. Kleidman, The maximal subgroups of the Steinberg triality groups $^3D_4(q)$ and of their automorphism groups, J. Algebra 115 (1988), no. 1, 182–199. MR 937609, DOI 10.1016/0021-8693(88)90290-6
- 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
- William M. Kantor and Ákos Seress, Permutation group algorithms via black box recognition algorithms, Groups St. Andrews 1997 in Bath, II, London Math. Soc. Lecture Note Ser., vol. 261, Cambridge Univ. Press, Cambridge, 1999, pp. 436–446. MR 1676640, DOI 10.1017/CBO9780511666148.007
- William M. Kantor and Ákos Seress, Prime power graphs for groups of Lie type, J. Algebra 247 (2002), no. 2, 370–434. MR 1877859, DOI 10.1006/jabr.2001.9016
- William M. Kantor and Ákos Seress, Large element orders and the characteristic of Lie-type simple groups, J. Algebra 322 (2009), no. 3, 802–832. MR 2531224, DOI 10.1016/j.jalgebra.2009.05.004
- Charles R. Leedham-Green, The computational matrix group project, Groups and computation, III (Columbus, OH, 1999) Ohio State Univ. Math. Res. Inst. Publ., vol. 8, de Gruyter, Berlin, 2001, pp. 229–247. MR 1829483
- Martin W. Liebeck and E. A. O’Brien, Finding the characteristic of a group of Lie type, J. Lond. Math. Soc. (2) 75 (2007), no. 3, 741–754. MR 2352733, DOI 10.1112/jlms/jdm028
- Martin W. Liebeck and Gary M. Seitz, Subgroups generated by root elements in groups of Lie type, Ann. of Math. (2) 139 (1994), no. 2, 293–361. MR 1274094, DOI 10.2307/2946583
- Martin W. Liebeck, Jan Saxl, and Gary M. Seitz, Subgroups of maximal rank in finite exceptional groups of Lie type, Proc. London Math. Soc. (3) 65 (1992), no. 2, 297–325. MR 1168190, DOI 10.1112/plms/s3-65.2.297
- F. Lübeck, K. Magaard, and E. A. O’Brien, Constructive recognition of $\textrm {SL}_3(q)$, J. Algebra 316 (2007), no. 2, 619–633. MR 2356848, DOI 10.1016/j.jalgebra.2007.01.020
- Peter M. Neumann and Cheryl E. Praeger, A recognition algorithm for special linear groups, Proc. London Math. Soc. (3) 65 (1992), no. 3, 555–603. MR 1182102, DOI 10.1112/plms/s3-65.3.555
- Christopher W. Parker and Robert A. Wilson, Recognising simplicity of black-box groups by constructing involutions and their centralisers, J. Algebra 324 (2010), no. 5, 885–915. MR 2659204, DOI 10.1016/j.jalgebra.2010.05.013
- Remko Juriën Riebeek, Computations in association schemes, Thesis Publishers, Amsterdam, 1998 (English, with Dutch summary). Dissertation, Technische Universiteit Eindhoven, Eindhoven, 1998. MR 1620656
- Ákos Seress, Permutation group algorithms, Cambridge Tracts in Mathematics, vol. 152, Cambridge University Press, Cambridge, 2003. MR 1970241, DOI 10.1017/CBO9780511546549
- Ken-ichi Shinoda, The conjugacy classes of Chevalley groups of type $(F_{4})$ over finite fields of characteristic $2$, J. Fac. Sci. Univ. Tokyo Sect. I A Math. 21 (1974), 133–159. MR 0349863
- Toshiaki Shoji, The conjugacy classes of Chevalley groups of type $(F_{4})$ over finite fields of characteristic $p\not =2$, J. Fac. Sci. Univ. Tokyo Sect. IA Math. 21 (1974), 1–17. MR 357641
- Robert Steinberg, Generators, relations and coverings of algebraic groups. II, J. Algebra 71 (1981), no. 2, 527–543. MR 630615, DOI 10.1016/0021-8693(81)90193-9
- K. Zsigmondy, Zur Theorie der Potenzreste, Monatsh. Math. Phys. 3 (1892), no. 1, 265–284 (German). MR 1546236, DOI 10.1007/BF01692444
Additional Information
- W. M. Kantor
- Affiliation: Department of Mathematics, University of Oregon, Eugene, Oregon 97403
- Email: kantor@uoregon.edu
- K. Magaard
- Affiliation: School of Mathematics, University of Birmingham, Edgbaston, Birmingham B15 2TT United Kingdom
- MR Author ID: 252279
- Email: k.magaard@bham.ac.uk
- Received by editor(s): November 1, 2009
- Received by editor(s) in revised form: November 6, 2009, and December 13, 2011
- Published electronically: May 28, 2013
- Additional Notes: This research was supported in part by NSF grants DMS 9731421, DMS 0242983 and DMS 0753640, and NSA grant MDA-9049810020.
- © Copyright 2013
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - Journal: Trans. Amer. Math. Soc. 365 (2013), 4895-4931
- MSC (2010): Primary 20D06, 20G40; Secondary 20B40, 20G41, 20P05, 68Q25
- DOI: https://doi.org/10.1090/S0002-9947-2013-05822-9
- MathSciNet review: 3066774