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