×

Recognising the Suzuki groups in their natural representations. (English) Zbl 1102.20012

The so-called ‘matrix group recognition project’ aims to produce effective algorithms to compute structural information about arbitrary groups defined by a generating set of matrices over a finite field. An important component is constructive recognition of simple groups, which is generally taken to mean setting up an isomorphism with a standard copy of the group, in such a way that images of arbitrary elements under the isomorphism and its inverse can be effectively computed.
In the case of simple groups of Lie type the obvious approach is to proceed by induction on the Lie rank, and deal with the base cases individually. For example, the base case \(\text{PSL}_2(q)\) is dealt with (in its natural representation) by M. Conder and C. R. Leedham-Green [Groups and computation III. Ohio State Univ. Math. Res. Inst. Publ. 8, 113-121 (2001; Zbl 1012.20043)], and provides the model for the case \(\text{Sz}(q)\) dealt with in the present paper. The crucial step is to find generators for a Borel subgroup (of index \(q^2+1\)), which is achieved by solving a complicated system of equations. Assuming that this system of equations always has a solution (no counterexample has yet been found!) the resulting algorithms are shown to run in Las Vegas polynomial time, given a random element oracle and a discrete logarithm oracle.
An implementation in MAGMA deals comfortably with \(\text{Sz}(2^{111})\), a group whose order is approximately the square of the order of the Monster sporadic simple group.

MSC:

20C40 Computational methods (representations of groups) (MSC2010)
20G40 Linear algebraic groups over finite fields
20-04 Software, source code, etc. for problems pertaining to group theory
68W30 Symbolic computation and algebraic computation
20F05 Generators, relations, and presentations of groups

Citations:

Zbl 1012.20043

Software:

matrixss; MeatAxe; R; Magma
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Aschbacher, M., On the maximal subgroups of the finite classical groups, Invent. Math., 76, 469-514 (1984) · Zbl 0537.20023
[2] H. BäÄrnhielm, Tensor decomposition of the Suzuki groups, 2005, submitted for publication; H. BäÄrnhielm, Tensor decomposition of the Suzuki groups, 2005, submitted for publication
[3] Babai, L., Local expansion of vertex-transitive graphs and random generation in groups, (Proc. 23rd ACM Symp. Theory of Computing. Proc. 23rd ACM Symp. Theory of Computing, Los Angeles (1991), Association for Computing Machinery), 164-174
[4] Babai, L.; Kantor, W. M.; Pálfy, P. P.; Seress, Á., Black-box recognition of finite simple groups of Lie type by statistics of element orders, J. Group Theory, 5, 383-401 (2002) · Zbl 1015.20013
[5] Bosma, W.; Cannon, J.; Playoust, C., The Magma algebra system I: The user language, J. Symbolic Comput., 24, 235-265 (1997) · Zbl 0898.68039
[6] Celler, F.; Leedham-Green, C. R., Calculating the order of an invertible matrix, (Finkelstein, L.; Kantor, W. M., Groups and Computation II. Groups and Computation II, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol. 28 (1997), Amer. Math. Soc.), 55-60 · Zbl 0877.20034
[7] Celler, F.; Leedham-Green, C. R.; Murray, S. H.; Niemeyer, A. C.; O’Brien, E. A., Generating random elements of a finite group, Comm. Algebra, 23, 4931-4948 (1995) · Zbl 0836.20094
[8] Conder, M. D.E.; Leedham-Green, C. R.; O’Brien, E. A., Constructive recognition of \(PSL(2, q)\), Trans. Amer. Math. Soc., 358, 1203-1221 (2006) · Zbl 1105.20013
[9] Coppersmith, D., Fast evaluation of logarithms in fields of characteristic two, IEEE Trans. Inform. Theory, IT-30, 4, 587-594 (1984) · Zbl 0554.12013
[10] Curtis, C. W.; Reiner, I., Representation Theory of Finite Groups and Associative Algebras (1962), Wiley · Zbl 0131.25601
[11] Glasby, S. P.; Leedham-Green, C. R.; O’Brien, E. A., Writing projective representations over subfields, J. Algebra, 295, 51-61 (2006) · Zbl 1103.20009
[12] Holt, D. F.; Eick, B.; O’Brien, E. A., Handbook of Computational Group Theory (January 2005), Chapman & Hall/CRC
[13] Holt, D. F.; Rees, S., Testing modules for irreducibility, J. Austral. Math. Soc. Ser. A, 57, 1-16 (1994) · Zbl 0833.20021
[14] Huppert, B.; Blackburn, N., Finite Groups, Grundlehren Math. Wiss., vol. 3 (1982), Springer-Verlag: Springer-Verlag Berlin · Zbl 0514.20002
[15] Ivanyos, G.; Lux, K., Treating the exceptional cases of the MeatAxe, Experiment. Math., 9, 373-381 (2000) · Zbl 0966.16028
[16] Leedham-Green, C. R., The computational matrix group project, (Groups and Computation III. Groups and Computation III, Ohio State Univ. Math. Res. Inst. Publ., vol. 8 (2001), de Gruyter), 113-121 · Zbl 1052.20034
[17] Mitrinovic, D. S.; Sándor, J.; Crstici, B., Handbook of Number Theory, Math. Appl., vol. 351 (1996), Kluwer · Zbl 0862.11001
[18] Ono, T., An identification of Suzuki groups with groups of generalized Lie type, Ann. of Math., 75, 2, 251-259 (1962) · Zbl 0113.25701
[19] R Development Core Team, R: A language and environment for statistical computing, R Foundation for Statistical Computing, Vienna, Austria, 2005, 3-900051-07-0; R Development Core Team, R: A language and environment for statistical computing, R Foundation for Statistical Computing, Vienna, Austria, 2005, 3-900051-07-0
[20] Seress, Á., Permutation Group Algorithms, Cambridge Tracts in Math., vol. 152 (2003), Cambridge Univ. Press · Zbl 1028.20002
[21] Steinberg, R., Representations of algebraic groups, Nagoya Math. J., 22, 33-56 (1963) · Zbl 0271.20019
[22] Steinberg, R., On theorems of Lie-Kolchin, Borel and Lang, (Contributions to Algebra, Collection of Papers Dedicated to Ellis Kolchin (1977), Academic Press: Academic Press New York), 349-354
[23] Suzuki, M., On a class of doubly transitive groups, Ann. of Math., 75, 1, 105-145 (1962) · Zbl 0106.24702
[24] von zur Gathen, J.; Gerhard, J., Modern Computer Algebra (2003), Cambridge Univ. Press: Cambridge Univ. Press Cambridge · Zbl 1055.68168
[25] R.A. Wilson, Finite simple groups, preprint, 2005; R.A. Wilson, Finite simple groups, preprint, 2005
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.