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)

 
 

 

Recognition of finite exceptional groups of Lie type


Authors: Martin W. Liebeck and E. A. O’Brien
Journal: Trans. Amer. Math. Soc. 368 (2016), 6189-6226
MSC (2010): Primary 20C20, 20C40
DOI: https://doi.org/10.1090/tran/6534
Published electronically: December 2, 2015
MathSciNet review: 3461031
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Let $ q$ be a prime power and let $ G$ be an absolutely irreducible subgroup of $ GL_d(F)$, where $ F$ is a finite field of the same characteristic as $ \mathbb{F}_q$, the field of $ q$ elements. Assume that $ G \cong G(q)$, a quasisimple group of exceptional Lie type over $ \mathbb{F}_q$ which is neither a Suzuki nor a Ree group. We present a Las Vegas algorithm that constructs an isomorphism from $ G$ to the standard copy of $ G(q)$. If $ G \not \cong {}^3\!D_4(q)$ with $ q$ even, then the algorithm runs in polynomial time, subject to the existence of a discrete log oracle.


References [Enhancements On Off] (What's this?)

  • [1] Michael Aschbacher and Gary M. Seitz, Involutions in Chevalley groups over fields of even order, Nagoya Math. J. 63 (1976), 1-91. MR 0422401 (54 #10391)
  • [2] H. Bäärnhielm, Algorithmic problems in twisted groups of Lie type, PhD thesis, Queen Mary, University of London, 2006.
  • [3] Henrik Bäärnhielm, Recognising the Suzuki groups in their natural representations, J. Algebra 300 (2006), no. 1, 171-198. MR 2228642 (2007f:20031), https://doi.org/10.1016/j.jalgebra.2006.02.010
  • [4] Henrik Bäärnhielm, Recognising the small Ree groups in their natural representations, J. Algebra 416 (2014), 139-166. MR 3232797, https://doi.org/10.1016/j.jalgebra.2014.06.017
  • [5] L. Babai and E. Szemerédi, On the complexity of matrix group problems, I, in Proc. $ 25$th IEEE Sympos. Foundations Comp. Sci., 1984, pp. 229-240.
  • [6] L. Babai, Local expansion of vertex-transitive graphs and random generation in finite groups, Theory of Computing (Los Angeles, 1991), Association for Computing Machinery, New York, 1991, pp. 164-174.
  • [7] 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 (98h:20044), https://doi.org/10.1006/jabr.1996.6980
  • [8] 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 (2000h:20089)
  • [9] László Babai and Aner Shalev, Recognizing simplicity of black-box groups and the frequency of $ p$-singular elements in affine groups, Groups and computation, III (Columbus, OH, 1999) Ohio State Univ. Math. Res. Inst. Publ., vol. 8, de Gruyter, Berlin, 2001, pp. 39-62. MR 1829470 (2002f:20021)
  • [10] 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 (2003i:20022), https://doi.org/10.1515/jgth.2002.010
  • [11] László Babai, Péter P. Pálfy, and Jan Saxl, On the number of $ p$-regular elements in finite simple groups, LMS J. Comput. Math. 12 (2009), 82-119. MR 2507573 (2010f:20017), https://doi.org/10.1112/S1461157000000036
  • [12] Wieb Bosma, John Cannon, and Catherine Playoust, The Magma algebra system. I. The user language, J. Symbolic Comput. 24 (1997), no. 3-4, 235-265. Computational algebra and number theory (London, 1993). MR 1484478, https://doi.org/10.1006/jsco.1996.0125
  • [13] N. Bourbaki, Éléments de mathématique. Fasc. XXXIV. Groupes et algèbres de Lie. Chapitre IV: Groupes de Coxeter et systèmes de Tits. Chapitre V: Groupes engendrés par des réflexions. Chapitre VI: systèmes de racines, Actualités Scientifiques et Industrielles, No. 1337, Hermann, Paris, 1968 (French). MR 0240238 (39 #1590)
  • [14] John N. Bray, An improved method for generating the centralizer of an involution, Arch. Math. (Basel) 74 (2000), no. 4, 241-245. MR 1742633 (2001c:20063), https://doi.org/10.1007/s000130050437
  • [15] John N. Bray, Derek F. Holt, and Colva M. Roney-Dougal, The maximal subgroups of the low-dimensional finite classical groups, London Mathematical Society Lecture Note Series, vol. 407, Cambridge University Press, Cambridge, 2013. With a foreword by Martin Liebeck. MR 3098485
  • [16] Peter A. Brooksbank, Constructive recognition of classical groups in their natural representation, J. Symbolic Comput. 35 (2003), no. 2, 195-239. MR 1958954 (2004c:20082), https://doi.org/10.1016/S0747-7171(02)00132-3
  • [17] Peter A. Brooksbank, Fast constructive recognition of black-box unitary groups, LMS J. Comput. Math. 6 (2003), 162-197. MR 2051584 (2005e:20075), https://doi.org/10.1112/S1461157000000437
  • [18] 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 (2007f:20085), https://doi.org/10.1016/j.jalgebra.2006.02.024
  • [19] Peter A. Brooksbank, Fast constructive recognition of black box symplectic groups, J. Algebra 320 (2008), no. 2, 885-909. MR 2422320 (2009f:20071), https://doi.org/10.1016/j.jalgebra.2008.03.021
  • [20] Roger W. Carter, Simple groups of Lie type, John Wiley & Sons, London-New York-Sydney, 1972. Pure and Applied Mathematics, Vol. 28. MR 0407163 (53 #10946)
  • [21] 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 (96h:20115), https://doi.org/10.1080/00927879508825509
  • [22] 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 (2005a:20068), https://doi.org/10.1090/S0025-5718-03-01582-5
  • [23] A. M. Cohen and D. E. Taylor, Row reduction for twisted groups of Lie type, preprint.
  • [24] Arjeh M. Cohen and Scott H. Murray, An algorithm for Lang's Theorem, J. Algebra 322 (2009), no. 3, 675-702. MR 2531217 (2010j:20069), https://doi.org/10.1016/j.jalgebra.2009.04.013
  • [25] Arjeh M. Cohen and Dan Roozemond, Computing Chevalley bases in small characteristics, J. Algebra 322 (2009), no. 3, 703-721. MR 2531218 (2010d:17025), https://doi.org/10.1016/j.jalgebra.2009.04.038
  • [26] M. D. E. Conder, C. R. Leedham-Green, and E. A. O'Brien, Constructive recognition of $ {\rm PSL}(2,q)$, Trans. Amer. Math. Soc. 358 (2006), no. 3, 1203-1221 (electronic). MR 2187651 (2006j:20017), https://doi.org/10.1090/S0002-9947-05-03756-6
  • [27] C. W. Curtis, Modular representations of finite groups with split $ (B,\,N)$-pairs, Seminar on Algebraic Groups and Related Finite Groups (The Institute for Advanced Study, Princeton, N.J., 1968/69) Springer, Berlin, 1970, pp. 57-95. MR 0262383 (41 #6991)
  • [28] I. G. Dick, Constructive recognition of black-box $ F_4(q)$ in odd characteristic. PhD thesis, Queen Mary, University of London, 2014.
  • [29] Heiko Dietrich, C. R. Leedham-Green, Frank Lübeck, and E. A. O'Brien, Constructive recognition of classical groups in even characteristic, J. Algebra 391 (2013), 227-255. MR 3081630, https://doi.org/10.1016/j.jalgebra.2013.04.031
  • [30] Heiko Dietrich, C. R. Leedham-Green, and E. A. O'Brien, Effective black-box constructive recognition of classical groups, J. Algebra 421 (2015), 460-492. MR 3272392, https://doi.org/10.1016/j.jalgebra.2014.08.039
  • [31] Peter B. Gilkey and Gary M. Seitz, Some representations of exceptional Lie algebras, Geom. Dedicata 25 (1988), no. 1-3, 407-416. Geometries and groups (Noordwijkerhout, 1986). MR 925845 (89h:20056), https://doi.org/10.1007/BF00191935
  • [32] S. P. Glasby, C. R. Leedham-Green, and E. A. O'Brien, Writing projective representations over subfields, J. Algebra 295 (2006), no. 1, 51-61. MR 2188850 (2006h:20002), https://doi.org/10.1016/j.jalgebra.2005.03.037
  • [33] 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 (98j:20011)
  • [34] Derek F. Holt, Bettina Eick, and Eamonn A. O'Brien, Handbook of computational group theory, Discrete Mathematics and its Applications (Boca Raton), Chapman & Hall/CRC, Boca Raton, FL, 2005. MR 2129747 (2006f:20001)
  • [35] R. B. Howlett, L. J. Rylands, and D. E. Taylor, Matrix generators for exceptional groups of Lie type, J. Symbolic Comput. 31 (2001), no. 4, 429-445. MR 1823074 (2002c:20078), https://doi.org/10.1006/jsco.2000.0431
  • [36] William M. Kantor and Ákos Seress, Black box classical groups, Mem. Amer. Math. Soc. 149 (2001), no. 708, viii+168. MR 1804385 (2001m:68066), https://doi.org/10.1090/memo/0708
  • [37] William M. Kantor and Ákos Seress, Prime power graphs for groups of Lie type, J. Algebra 247 (2002), no. 2, 370-434. MR 1877859 (2003a:20026), https://doi.org/10.1006/jabr.2001.9016
  • [38] 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 (2010d:20018), https://doi.org/10.1016/j.jalgebra.2009.05.004
  • [39] W. M. Kantor and K. Magaard, Black box exceptional groups of Lie type, Trans. Amer. Math. Soc. 365 (2013), no. 9, 4895-4931. MR 3066774, https://doi.org/10.1090/S0002-9947-2013-05822-9
  • [40] 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 (89f:20024), https://doi.org/10.1016/0021-8693(88)90290-6
  • [41] C. R. Leedham-Green and E. A. O'Brien, Recognising tensor-induced matrix groups, J. Algebra 253 (2002), no. 1, 14-30. MR 1925006 (2003g:20089), https://doi.org/10.1016/S0021-8693(02)00041-8
  • [42] C. R. Leedham-Green and E. A. O'Brien, Constructive recognition of classical groups in odd characteristic, J. Algebra 322 (2009), no. 3, 833-881. MR 2531225 (2010e:20075), https://doi.org/10.1016/j.jalgebra.2009.04.028
  • [43] 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 (2008i:20058), https://doi.org/10.1112/jlms/jdm028
  • [44] Martin W. Liebeck and Jan Saxl, Minimal degrees of primitive permutation groups, with an application to monodromy groups of covers of Riemann surfaces, Proc. London Math. Soc. (3) 63 (1991), no. 2, 266-314. MR 1114511 (92f:20003), https://doi.org/10.1112/plms/s3-63.2.266
  • [45] 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 (93e:20026), https://doi.org/10.1112/plms/s3-65.2.297
  • [46] Martin W. Liebeck and Aner Shalev, The probability of generating a finite simple group, Geom. Dedicata 56 (1995), no. 1, 103-113. MR 1338320 (96h:20116), https://doi.org/10.1007/BF01263616
  • [47] Martin W. Liebeck and Gary M. Seitz, Unipotent and nilpotent classes in simple algebraic groups and Lie algebras, Mathematical Surveys and Monographs, vol. 180, American Mathematical Society, Providence, RI, 2012. MR 2883501
  • [48] S. A. Linton, The art and science of computing in large groups, Computational algebra and number theory (Sydney, 1992) Math. Appl., vol. 325, Kluwer Acad. Publ., Dordrecht, 1995, pp. 91-109. MR 1344924 (96h:20002)
  • [49] F. Lübeck, K. Magaard, and E. A. O'Brien, Constructive recognition of $ {\rm SL}_3(q)$, J. Algebra 316 (2007), no. 2, 619-633. MR 2356848 (2008j:20039), https://doi.org/10.1016/j.jalgebra.2007.01.020
  • [50] E. A. O'Brien, Algorithms for matrix groups, Groups St Andrews 2009 in Bath. Volume 2, London Math. Soc. Lecture Note Ser., vol. 388, Cambridge Univ. Press, Cambridge, 2011, pp. 297-323. MR 2858866 (2012m:20083)
  • [51] Igor Pak, The product replacement algorithm is polynomial, 41st Annual Symposium on Foundations of Computer Science (Redondo Beach, CA, 2000) IEEE Comput. Soc. Press, Los Alamitos, CA, 2000, pp. 476-485. MR 1931844, https://doi.org/10.1109/SFCS.2000.892135
  • [52] 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 (2011j:20032), https://doi.org/10.1016/j.jalgebra.2010.05.013
  • [53] Ákos Seress, Permutation group algorithms, Cambridge Tracts in Mathematics, vol. 152, Cambridge University Press, Cambridge, 2003. MR 1970241 (2004c:20008)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2010): 20C20, 20C40

Retrieve articles in all journals with MSC (2010): 20C20, 20C40


Additional Information

Martin W. Liebeck
Affiliation: Department of Mathematics, Imperial College, London SW7 2BZ, United Kingdom
Email: m.liebeck@imperial.ac.uk

E. A. O’Brien
Affiliation: Department of Mathematics, University of Auckland, Auckland, New Zealand
Email: e.obrien@auckland.ac.nz

DOI: https://doi.org/10.1090/tran/6534
Received by editor(s): October 10, 2013
Received by editor(s) in revised form: August 7, 2014
Published electronically: December 2, 2015
Article copyright: © Copyright 2015 American Mathematical Society

American Mathematical Society