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
DOI: https://doi.org/10.1090/S0002-9947-05-03756-6
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?)


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
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
Email: obrien@math.auckland.ac.nz

DOI: https://doi.org/10.1090/S0002-9947-05-03756-6
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