Recognition of finite exceptional groups of Lie type

Liebeck, Martin; O’Brien, E.

doi:10.1090/tran/6534

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