Recognition of finite exceptional groups of Lie type
HTML articles powered by AMS MathViewer
- by Martin W. Liebeck and E. A. O’Brien PDF
- Trans. Amer. Math. Soc. 368 (2016), 6189-6226 Request permission
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
- Michael Aschbacher and Gary M. Seitz, Involutions in Chevalley groups over fields of even order, Nagoya Math. J. 63 (1976), 1–91. MR 422401
- H. Bäärnhielm, Algorithmic problems in twisted groups of Lie type, PhD thesis, Queen Mary, University of London, 2006.
- 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
- Henrik Bäärnhielm, Recognising the small Ree groups in their natural representations, J. Algebra 416 (2014), 139–166. MR 3232797, DOI 10.1016/j.jalgebra.2014.06.017
- 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.
- 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.
- 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 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á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
- 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
- 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, DOI 10.1112/S1461157000000036
- 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, DOI 10.1006/jsco.1996.0125
- 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 [Current Scientific and Industrial Topics], No. 1337, Hermann, Paris, 1968 (French). MR 0240238
- 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
- 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, DOI 10.1017/CBO9781139192576
- 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 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
- 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
- Roger W. Carter, Simple groups of Lie type, Pure and Applied Mathematics, Vol. 28, John Wiley & Sons, London-New York-Sydney, 1972. MR 0407163
- 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, 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
- A. M. Cohen and D. E. Taylor, Row reduction for twisted groups of Lie type, preprint.
- 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 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
- 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
- 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
- I. G. Dick, Constructive recognition of black-box $F_4(q)$ in odd characteristic. PhD thesis, Queen Mary, University of London, 2014.
- 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, DOI 10.1016/j.jalgebra.2013.04.031
- 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, DOI 10.1016/j.jalgebra.2014.08.039
- 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, DOI 10.1007/BF00191935
- 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, DOI 10.1016/j.jalgebra.2005.03.037
- 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
- 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, DOI 10.1201/9781420035216
- 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, DOI 10.1006/jsco.2000.0431
- 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, 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
- 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, DOI 10.1090/S0002-9947-2013-05822-9
- 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
- C. R. Leedham-Green and E. A. O’Brien, Recognising tensor-induced matrix groups, J. Algebra 253 (2002), no. 1, 14–30. MR 1925006, DOI 10.1016/S0021-8693(02)00041-8
- 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, DOI 10.1016/j.jalgebra.2009.04.028
- 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 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, DOI 10.1112/plms/s3-63.2.266
- 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
- Martin W. Liebeck and Aner Shalev, The probability of generating a finite simple group, Geom. Dedicata 56 (1995), no. 1, 103–113. MR 1338320, DOI 10.1007/BF01263616
- 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, DOI 10.1090/surv/180
- 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
- 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
- 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
- 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, DOI 10.1109/SFCS.2000.892135
- 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
- Ákos Seress, Permutation group algorithms, Cambridge Tracts in Mathematics, vol. 152, Cambridge University Press, Cambridge, 2003. MR 1970241, DOI 10.1017/CBO9780511546549
Additional Information
- Martin W. Liebeck
- Affiliation: Department of Mathematics, Imperial College, London SW7 2BZ, United Kingdom
- MR Author ID: 113845
- ORCID: 0000-0002-3284-9899
- Email: m.liebeck@imperial.ac.uk
- E. A. O’Brien
- Affiliation: Department of Mathematics, University of Auckland, Auckland, New Zealand
- MR Author ID: 251889
- Email: e.obrien@auckland.ac.nz
- Received by editor(s): October 10, 2013
- Received by editor(s) in revised form: August 7, 2014
- Published electronically: December 2, 2015
- © Copyright 2015 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 368 (2016), 6189-6226
- MSC (2010): Primary 20C20, 20C40
- DOI: https://doi.org/10.1090/tran/6534
- MathSciNet review: 3461031