## Constructive recognition of $\mathrm {PSL}(2, q)$

HTML articles powered by AMS MathViewer

- by M. D. E. Conder, C. R. Leedham-Green and E. A. O’Brien PDF
- Trans. Amer. Math. Soc.
**358**(2006), 1203-1221 Request permission

## Abstract:

Existing black box and other algorithms for explicitly recognising groups of Lie type over $\mathrm {GF}(q)$ have asymptotic running times which are polynomial in $q$, whereas the input size involves only $\log q$. This has represented a serious obstruction to the efficient recognition of such groups. Recently, Brooksbank and Kantor devised new explicit recognition algorithms for classical groups; these run in time that is polynomial in the size of the input, given an oracle that recognises $\mathrm {PSL}(2,q)$ explicitly. The present paper, in conjunction with an earlier paper by the first two authors, provides such an oracle. The earlier paper produced an algorithm for explicitly recognising $\mathrm {SL}(2,q)$ in its natural representation in polynomial time, given a discrete logarithm oracle for $\mathrm {GF}(q)$. The algorithm presented here takes as input a generating set for a subgroup $G$ of $\mathrm {GL}(d,F)$ that is isomorphic modulo scalars to $\mathrm {PSL}(2,q)$, where $F$ is a finite field of the same characteristic as $\mathrm {GF}(q)$; it returns the natural representation of $G$ modulo scalars. Since a faithful projective representation of $\mathrm {PSL}(2,q)$ in cross characteristic, or a faithful permutation representation of this group, is necessarily of size that is polynomial in $q$ rather than in $\log q$, elementary algorithms will recognise $\mathrm {PSL} (2,q)$ explicitly in polynomial time in these cases. Given a discrete logarithm oracle for $\mathrm {GF}(q)$, our algorithm thus provides the required polynomial time oracle for recognising $\mathrm {PSL}(2,q)$ explicitly in the remaining case, namely for representations in the natural characteristic. This leads to a partial solution of a question posed by Babai and Shalev: if $G$ is a matrix group in characteristic $p$, determine in polynomial time whether or not $O_p(G)$ is trivial.## References

- 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 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. 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, Gene Cooperman, Larry Finkelstein, Eugene Luks, and Ákos Seress,
*Fast Monte Carlo algorithms for permutation groups*, J. Comput. System Sci.**50**(1995), no. 2, 296–308. 23rd Symposium on the Theory of Computing (New Orleans, LA, 1991). MR**1330259**, DOI 10.1006/jcss.1995.1024 - 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 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** - R. Brauer and C. Nesbitt,
*On the modular characters of groups*, Ann. of Math. (2)**42**(1941), 556–590. MR**4042**, DOI 10.2307/1968918 - 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 - 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** - 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 and C. R. Leedham-Green,
*Calculating the order of an invertible matrix*, Groups and computation, II (New Brunswick, NJ, 1995) DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol. 28, Amer. Math. Soc., Providence, RI, 1997, pp. 55–60. MR**1444130** - 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 - S. P. Glasby and R. B. Howlett,
*Writing representations over minimal fields*, Comm. Algebra**25**(1997), no. 6, 1703–1711. MR**1446124**, DOI 10.1080/00927879708825947 - G. H. Hardy and E. M. Wright,
*An introduction to the theory of numbers*, Oxford, at the Clarendon Press, 1954. 3rd ed. MR**0067125** - Derek F. Holt and Sarah Rees,
*Testing modules for irreducibility*, J. Austral. Math. Soc. Ser. A**57**(1994), no. 1, 1–16. MR**1279282**, DOI 10.1017/S1446788700036016 - Alexander Hulpke and Ákos Seress,
*Short presentations for three-dimensional unitary groups*, J. Algebra**245**(2001), no. 2, 719–729. MR**1863898**, DOI 10.1006/jabr.2001.8943 - Gábor Ivanyos and Klaus Lux,
*Treating the exceptional cases of the MeatAxe*, Experiment. Math.**9**(2000), no. 3, 373–381. MR**1795309**, DOI 10.1080/10586458.2000.10504414 - Vicente Landazuri and Gary M. Seitz,
*On the minimal degrees of projective representations of the finite Chevalley groups*, J. Algebra**32**(1974), 418–443. MR**360852**, DOI 10.1016/0021-8693(74)90150-1 - 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** - C. R. Leedham-Green and E. A. O’Brien,
*Tensor products are projective geometries*, J. Algebra**189**(1997), no. 2, 514–528. MR**1438187**, DOI 10.1006/jabr.1996.6881 - C. R. Leedham-Green and E. A. O’Brien,
*Recognising tensor products of matrix groups*, Internat. J. Algebra Comput.**7**(1997), no. 5, 541–559. MR**1470352**, DOI 10.1142/S0218196797000241 - 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 - D. S. Mitrinović, J. Sándor, and B. Crstici,
*Handbook of number theory*, Mathematics and its Applications, vol. 351, Kluwer Academic Publishers Group, Dordrecht, 1996. MR**1374329** - J.A. Todd, “A second note on the linear fractional group",
*Proc. London Math. Soc.***11**, 1936, 103–107. - Igor E. Shparlinski,
*Finite fields: theory and computation*, Mathematics and its Applications, vol. 477, Kluwer Academic Publishers, Dordrecht, 1999. The meeting point of number theory, computer science, coding theory and cryptography. MR**1745660**, DOI 10.1007/978-94-015-9239-0

## Additional Information

**M. D. E. Conder**- Affiliation: Department of Mathematics, University of Auckland, Private Bag 92019, Auckland, New Zealand
- MR Author ID: 50940
- ORCID: 0000-0002-0256-6978
- Email: conder@math.auckland.ac.nz
**C. R. Leedham-Green**- Affiliation: School of Mathematical Sciences, Queen Mary, University of London, London E1 4NS, United Kingdom
- Email: C.R.Leedham-Green@qmul.ac.uk
**E. A. O’Brien**- Affiliation: Department of Mathematics, University of Auckland, Private Bag 92019, Auckland, New Zealand
- MR Author ID: 251889
- Email: obrien@math.auckland.ac.nz
- Received by editor(s): January 17, 2003
- Received by editor(s) in revised form: May 4, 2004
- Published electronically: May 9, 2005
- Additional Notes: This work was supported in part by the Marsden Fund of New Zealand via grant UOA124.
- © Copyright 2005
American Mathematical Society

The copyright for this article reverts to public domain 28 years after publication. - Journal: Trans. Amer. Math. Soc.
**358**(2006), 1203-1221 - MSC (2000): Primary 20C20; Secondary 20C40
- DOI: https://doi.org/10.1090/S0002-9947-05-03756-6
- MathSciNet review: 2187651