Black box exceptional groups of Lie type

Kantor, W.; Magaard, K.

doi:10.1090/S0002-9947-2013-05822-9

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