Skip to Main Content

Transactions of the American Mathematical Society

Published by the American Mathematical Society since 1900, Transactions of the American Mathematical Society is devoted to longer research articles in all areas of pure and applied mathematics.

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

The 2020 MCQ for Transactions of the American Mathematical Society is 1.48.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

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
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
  • 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