Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



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

Authors: M. D. E. Conder, C. R. Leedham-Green and E. A. O'Brien
Journal: Trans. Amer. Math. Soc. 358 (2006), 1203-1221
MSC (2000): Primary 20C20; Secondary 20C40
Published electronically: May 9, 2005
MathSciNet review: 2187651
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • 1. László Babai, William M. Kantor, Peter 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), 383-401. MR 1931364 (2003i:20022)
  • 2. 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), 39-62, Ohio State Univ. Math. Res. Inst. Publ., 8. MR 1829470 (2002f:20021)
  • 3. 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), 79-112. MR 1461483 (98h:20044)
  • 4. László Babai, Gene Cooperman, Larry Finkelstein, Eugene Luks, and Ákos Seress, ``Fast Monte Carlo algorithms for permutation groups", 23rd Symposium on the Theory of Computing (New Orleans, LA, 1991), J. Comput. System Sci. 50 (1995), 296-308. MR 1330259 (97a:68067)
  • 5. Peter A. Brooksbank, ``Constructive recognition of classical groups in their natural representation", J. Symbolic Comput. 35 (2003), 195-239. MR 1958954 (2004c:20082)
  • 6. Peter A. Brooksbank and William M. Kantor, ``On constructive recognition of a black box ${\rm PSL}(d,q)$", Groups and computation, III (Columbus, OH, 1999), 95-111, Ohio State Univ. Math. Res. Inst. Publ., 8, de Gruyter, Berlin, 2001. MR 1829473 (2002m:20078)
  • 7. R. Brauer and C. Nesbitt, ``On the modular characters of groups", Ann. of Math. 42, 556-590, 1941. MR 0004042 (2:309c)
  • 8. Wieb Bosma, John Cannon, and Catherine Playoust, ``The MAGMA algebra system I: The user language",
    J. Symbolic Comput., 24, 235-265, 1997. MR 1484478
  • 9. Marston Conder and Charles R. Leedham-Green, ``Fast recognition of classical groups over large fields", Groups and computation, III (Columbus, OH, 1999), 113-121, Ohio State Univ. Math. Res. Inst. Publ., 8, de Gruyter, Berlin, 2001. MR 1829474 (2002g:20001)
  • 10. 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), 11-26, London Math. Soc. Lecture Note Ser., 249, Cambridge Univ. Press, Cambridge, 1998. MR 1647410 (99g:20001)
  • 11. Frank Celler and C.R. Leedham-Green,
    ``Calculating the order of an invertible matrix",
    Groups and Computation II, Amer. Math. Soc. DIMACS Series 28, 55-60. (DIMACS, 1995), 1997. MR 1444130 (98g:20001)
  • 12. Frank Celler, C.R. Leedham-Green, Scott H. Murray, Alice C. Niemeyer, and E.A. O'Brien, ``Generating random elements of a finite group", Comm. Algebra 23, 4931-4948, 1995. MR 1356111 (96h:20115)
  • 13. S.P. Glasby and R.B. Howlett, ``Writing representations over minimal fields", Comm. Algebra, 25, 1703-1711, 1997. MR 1446124 (98c:20019)
  • 14. G.H. Hardy and E.M. Wright. An Introduction to the Theory of Numbers. Fourth edition. OUP. Oxford. MR 0067125 (16,673c)
  • 15. Derek F. Holt and Sarah Rees, ``Testing modules for irreducibility",
    J. Austral. Math. Soc. Ser. A, 57, 1-16, 1994. MR 1279282 (95e:20023)
  • 16. Alexander Hulpke and Ákos Seress, ``Short presentations for three-dimensional unitary groups", J. Algebra 245 (2001), 719-729. MR 1863898 (2002m:20079)
  • 17. Gábor Ivanyos and Klaus Lux, ``Treating the exceptional cases of the MeatAxe", Experiment. Math. 9 (2000), 373-381. MR 1795309 (2001j:16067)
  • 18. Vicente Landazuri and Gary M. Seitz.
    ``On the minimal degrees of projective representations of the finite Chevalley groups",
    J. Algebra 32, 418-443, 1974. MR 0360852 (50:13299)
  • 19. Charles R. Leedham-Green, ``The computational matrix group project", in Groups and Computation, III (Columbus, OH, 1999), 229-247, Ohio State Univ. Math. Res. Inst. Publ., 8, de Gruyter, Berlin, 2001. MR 1829483 (2002d:20084)
  • 20. C.R. Leedham-Green and E.A. O'Brien,
    ``Tensor products are projective geometries",
    J. Algebra, 189, 514-528, 1997. MR 1438187 (98b:20073)
  • 21. C.R. Leedham-Green and E.A. O'Brien,
    ``Recognising tensor products of matrix groups",
    Internat. J. Algebra Comput., 7, 541-559, 1997. MR 1470352 (98h:20018)
  • 22. William M. Kantor and Ákos Seress. Black box classical groups. Mem. Amer. Math. Soc. 149, 2001. MR 1804385 (2001m:68066)
  • 23. D.S. Mitrinovic, J. Sándor and B. Crstici, Handbook of Number Theory, Mathematics and Its Applications 351, Kluwer Academic Publishers, 1996. MR 1374329 (97f:11001)
  • 24. J.A. Todd, ``A second note on the linear fractional group", Proc. London Math. Soc. 11, 1936, 103-107.
  • 25. Igor E. Shparlinski, Finite fields: theory and computation. The meeting point of number theory, computer science, coding theory and cryptography. Mathematics and its Applications, 477. Kluwer Academic Publishers, Dordrecht, 1999. MR 1745660 (2001g:11188)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2000): 20C20, 20C40

Retrieve articles in all journals with MSC (2000): 20C20, 20C40

Additional Information

M. D. E. Conder
Affiliation: Department of Mathematics, University of Auckland, Private Bag 92019, Auckland, New Zealand

C. R. Leedham-Green
Affiliation: School of Mathematical Sciences, Queen Mary, University of London, London E1 4NS, United Kingdom

E. A. O'Brien
Affiliation: Department of Mathematics, University of Auckland, Private Bag 92019, Auckland, New Zealand

Keywords: Constructive recognition, $\mathrm{PSL}(2, q)$
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.
Article copyright: © Copyright 2005 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society