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)

Request Permissions   Purchase Content 
 
 

 

Black box exceptional groups of Lie type


Authors: W. M. Kantor and K. Magaard
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
Published electronically: May 28, 2013
MathSciNet review: 3066774
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [Baa1] H. Bäärnhielm, Recognising the Suzuki groups in their natural representations. J. Algebra 300 (2006) 171-198. MR 2228642 (2007f:20031)
  • [Baa2] H. Bäärnhielm, Tensor decomposition of the Suzuki groups (unpublished).
  • [Baa3] H. Bäärnhielm, Recognising the Ree groups in their natural representations (unpublished).
  • [Baa4] H. Bäärnhielm, Algorithmic problems in twisted groups of Lie type. Ph.D. thesis, Queen Mary, U. of London 2007.
  • [Bab] 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.
  • [BB] L. Babai and R. Beals, A polynomial-time theory of black-box groups I, pp. 30-64 in: Groups St. Andrews 1997 in Bath (eds. C. M. Campbell et al.), LMS Lecture Note Series 260, Cambridge U. Press, Cambridge 1999. MR 1676609 (2000h:20089)
  • [BGKLP] 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) 79-112. MR 1461483 (98h:20044)
  • [BKPS] L. Babai, W. M. Kantor, P. P. Pálfy and Á. Seress, Black-box recognition of finite simple groups of Lie type by statistics of element orders. J. Group Theory 5 (2002) 383-401. MR 1931364 (2003i:20022)
  • [BLNPS] R. Beals, C. R. Leedham-Green, A. C. Niemeyer, C. E. Praeger and Á. Seress, A black-box group algorithm for recognizing finite symmetric and alternating groups. I. Trans. Amer. Math. Soc. 355 (2003) 2097-2113. MR 1953539 (2003k:20002)
  • [Bor] A. V. Borovik, Centralisers of involutions in black box groups, pp. 7-20 in: Computational and statistical group theory (Las Vegas, NV/Hoboken, NJ, 2001), Contemp. Math. 298, Amer. Math. Soc., Providence 2002. MR 1929713 (2003i:60010)
  • [Br] J. N. Bray, An improved method for generating the centralizer of an involution. Arch. Math. 74 (2000) 241-245. MR 1742633 (2001c:20063)
  • [BrB] J. N. Bray and H. Bäärnhielm, Standard generators for the Suzuki groups (unpublished).
  • [Br1] P. A. Brooksbank, Constructive recognition of classical groups in their natural representation. J. Symbolic Computation 35 (2003) 195-239. MR 1958954 (2004c:20082)
  • [Br2] P. A. Brooksbank, Fast constructive recognition of black box unitary groups. LMS J. Comput. Math. 6 (2003) 162-197. MR 2051584 (2005e:20075)
  • [Br3] P. A. Brooksbank, Fast constructive recognition of black box symplectic groups. J. Algebra 320 (2008) 885-909. MR 2422320 (2009f:20071)
  • [BrK1] P. A. Brooksbank and W. M. Kantor, On constructive recognition of a black box $ \mathrm {PSL}(d,q)$, pp. 95-111 in: Groups and Computation III (eds. W. M. Kantor and Á. Seress), Ohio State Univ. Math. Res. Inst. Publ. 8, de Gruyter, Berlin-New York, 2001. MR 1829473 (2002m:20078)
  • [BrK2] P. A. Brooksbank and W. M. Kantor, Fast constructive recognition of black box orthogonal groups. J. Algebra 300 (2006) 256-288. MR 2228648 (2007f:20085)
  • [Ca1] R. W. Carter, Simple groups of Lie type. Wiley, London-New York-Sydney 1972. MR 0407163 (53:10946)
  • [Ca2] R. W. Carter, Finite groups of Lie type. Conjugacy classes and complex characters. Wiley, New York 1985. MR 794307 (87d:20060)
  • [CHM] A. M. Cohen, S. Haller and S. H. Murray, Computing with root subgroups of twisted reductive groups (preprint).
  • [CLG] F. Celler and C. R. Leedham-Green, A constructive recognition algorithm for the special linear group, pp. 11-26 in: The atlas of finite groups: ten years on (Birmingham, 1995), LMS Lecture Note Series 249, Cambridge U. Press, Cambridge 1998. MR 1647410 (99g:20001)
  • [CLMNO] F. Celler, C. R. Leedham-Green, S. H. Murray, A. C. Niemeyer and E. A. O'Brien, Generating random elements of a finite group. Comm. Alg. 23 (1995) 4931-4948. MR 1356111 (96h:20115)
  • [CM] A. M. Cohen and S. H. Murray, An algorithm for Lang's Theorem. J. Algebra 322 (2009) 675-702. MR 2531217 (2010j:20069)
  • [CMT] A. M. Cohen, S. H. Murray and D. E. Taylor, Computing in groups of Lie type. Math. Comp. 73 (2004) 1477-1498. MR 2047097 (2005a:20068)
  • [CR] A. M. Cohen and D. Roozemond, Computing Chevalley bases in small characteristics. J. Algebra 322 (2009) 703-721. MR 2531218 (2010d:17025)
  • [CFL] G. Cooperman, L. Finkelstein and S. Linton, Recognizing $ {\mathrm {GL}}(n,2)$ in non-standard representation, pp. 85-100 in: Groups and Computation II, Proc. DIMACS Workshop (eds. L. Finkelstein and W. M. Kantor), Amer. Math. Soc., Providence 1997. MR 1444132 (98d:20054)
  • [CoLG] M. Conder and C. R. Leedham-Green, Fast recognition of classical groups over large fields, pp. 113-121 in: Groups and Computation III (eds. W. M. Kantor and Á. Seress), Ohio State Univ. Math. Res. Inst. Publ. 8, de Gruyter, Berlin-New York 2001. MR 1829474 (2002g:20001)
  • [CoLGO] M. D. E. Conder, C. R. Leedham-Green and E. A. O'Brien, Constructive recognition of $ \mathrm {PSL}(2, q).$ Trans. Amer. Math. Soc. 358 (2006) 1203-1221. MR 2187651 (2006j:20017)
  • [Coo] B. N. Cooperstein, The geometry of root subgroups in exceptional groups. I. Geom. Dedicata 8 (1979) 317-381. MR 550374 (81e:20022)
  • [CKS] C. W. Curtis, W. M. Kantor and G. M. Seitz, The 2-transitive permutation representations of the finite Chevalley groups. Trans. Amer. Math. Soc. 218 (1976) 1-59. MR 0422440 (54:10429)
  • [DF] D. I. Deriziotis and A. P. Fakiolas, The maximal tori of the finite Chevalley groups of type $ E_6$, $ E_7$ and $ E_8$. Comm. Alg. 19 (1991) 889-903. MR 1102992 (92c:20081)
  • [Di] L. E. Dickson, Linear Groups, with an Exposition of the Galois Field Theory (1900). Reprinted, Dover, New York, 1958. MR 0104735 (21:3488)
  • [Dix] J. D. Dixon, Generating random elements in finite groups. Electronic J. Combinatorics 13 (2008), $ \char93 $R94. MR 2426157 (2009j:20093)
  • [FJ] P. Fleischmann and I. Janiszczak, The semisimple conjugacy classes and the generic class number of the finite simple groups of Lie type $ E\sb 8$. Comm. Alg. 22 (1994) 2221-2303. MR 1268550 (95b:20025)
  • [GLS] D. Gorenstein, R. Lyons and R. Solomon, The classification of the finite simple groups. No. 3. Part I. Chapter A. Almost simple K-groups. Amer. Math. Soc., Providence 1998. MR 1490581 (98j:20011)
  • [GKKL1] 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) 711-774. MR 2393425 (2010c:20011)
  • [GKKL2] R. M. Guralnick, W. M. Kantor, M. Kassabov and A. Lubotzky, Presentations of finite simple groups: a computational approach. J. Eur. Math. Soc. 13 (2011) 391-458. MR 2746771 (2011m:20035)
  • [GPPS] R. M. Guralnick, T. Penttila, C. E. Praeger and J. Saxl, Linear groups with orders having certain primitive prime divisors. Proc. Lond. Math. Soc. 78 (1999) 167-214. MR 1658168 (99m:20113)
  • [HLORW] 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) 747-763. MR 2466905 (2009i:20001)
  • [Ka1] W. M. Kantor, Subgroups of classical groups generated by long root elements. Trans. Amer. Math. Soc. 248 (1979) 347-379. MR 522265 (80g:20057)
  • [Ka2] W. M. Kantor, Primitive permutation groups of odd degree, and an application to finite projective planes. J. Algebra 106 (1987) 15-45. MR 878466 (88b:20007)
  • [Ka3] W. M. Kantor, Simple groups in computational group theory, pp. 77-86 in: Proc. International Congress of Mathematicians, Vol. II, Documenta Math., Berlin 1998. MR 1648058 (99h:20002)
  • [Kl1] P. B. Kleidman, The maximal subgroups of the Chevalley groups $ G_2(q$) with $ q$ odd, the Ree groups $ {^2\!G_2}(q)$, and their automorphism groups. J. Algebra 117 (1988) 30-71. MR 955589 (89j:20055)
  • [Kl2] P. B. Kleidman, The maximal subgroups of the finite Steinberg triality groups $ {^3\!D_4}(q)$ and of their automorphism groups. J. Algebra 115 (1988) 182-199. MR 937609 (89f:20024)
  • [KS1] W. M. Kantor and Á. Seress, Black box classical groups. Mem. Amer. Math. Soc. 149 (2001), No. 708. MR 1804385 (2001m:68066)
  • [KS2] W. M. Kantor and Á. Seress, Permutation group algorithms via black box recognition algorithms, pp. 436-446 in: Groups St Andrews 1997 in Bath (eds. C. Campbell et al.), LMS Lectures Notes Series 261, Cambridge U. Press, Cambridge 1999. MR 1676640 (2000h:20007)
  • [KS3] W. M. Kantor and Á. Seress, Prime power graphs for groups of Lie type. J. Algebra 247 (2002) 370-434. MR 1877859 (2003a:20026)
  • [KS4] W. M. Kantor and Á. Seress, Large element orders and the characteristic of Lie-type simple groups. J. Algebra 322 (2009) 802-832. MR 2531224 (2010d:20018)
  • [LG] C. R. Leedham-Green, The computational matrix group project, pp. 229-247 in: Groups and Computation III (eds. W. M. Kantor and Á. Seress), Ohio State Univ. Math. Res. Inst. Publ. 8, de Gruyter, Berlin-New York 2001. MR 1829483 (2002d:20084)
  • [LO] M. W. Liebeck and E. A. O'Brien, Finding the characteristic of a group of Lie type. J. Lond. Math. Soc. 75 (2007) 741-754. MR 2352733 (2008i:20058)
  • [LS] M. W. Liebeck and G. M. Seitz, Subgroups generated by root elements in groups of Lie type. Ann. of Math. 139 (1994) 293-361. MR 1274094 (95d:20078)
  • [LSS] M. W. Liebeck, J. Saxl and G. M. Seitz, Subgroups of maximal rank in finite exceptional groups of Lie type. Proc. Lond. Math. Soc. 65 (1992) 297-325. MR 1168190 (93e:20026)
  • [LMO] F. Lübeck, K. Magaard and E. A. O'Brien, Constructive recognition of $ \mathrm {SL}(3,q)$. J. Algebra 316 (2007) 619-633. MR 2356848 (2008j:20039)
  • [NP] P. M. Neumann and C. E. Praeger, A recognition algorithm for special linear groups. Proc. Lond. Math. Soc. 65 (1992), 555-603. MR 1182102 (93m:20063)
  • [PW] C. W. Parker and R. A. Wilson, Recognizing simplicity of black-box groups by constructing involutions and their centralisers. J. Algebra 324 (2010) 885-915. MR 2659204 (2011j:20032)
  • [Ri] R. J. Riebeek, Computations in association schemes. Ph.D. thesis, Techn. U. Eindhoven 1998. MR 1620656 (99d:05089)
  • [Ser] Á. Seress, Permutation group algorithms, Cambridge U. Press, Cambridge 2002. MR 1970241 (2004c:20008)
  • [Shi] K. Shinoda, The conjugacy classes of Chevalley groups of type $ F_4$ over fields of characteristic 2. J. Fac. Sci. Univ. Tokyo 21 (1974) 133-159. MR 0349863 (50:2356)
  • [Sho] T. Shoji, The conjugacy classes of Chevalley groups of type $ F_4$ over fields of characteristic $ \neq 2$. J. Fac. Sci. Univ. Tokyo 21 (1974) 1-17. MR 0357641 (50:10109)
  • [St] R. Steinberg, Generators, relations and coverings of algebraic groups, II. J. Algebra 71 (1981) 527-543. MR 630615 (83d:14025)
  • [Zs] K. Zsigmondy, Zur Theorie der Potenzreste. Monatsh. Math. Phys. 3 (1892) 265-284. MR 1546236

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2010): 20D06, 20G40, 20B40, 20G41, 20P05, 68Q25

Retrieve articles in all journals with MSC (2010): 20D06, 20G40, 20B40, 20G41, 20P05, 68Q25


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
Email: k.magaard@bham.ac.uk

DOI: https://doi.org/10.1090/S0002-9947-2013-05822-9
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.
Article copyright: © Copyright 2013 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society