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

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.