Constructive recognition of finite alternating and symmetric groups acting as matrix groups on their natural permutation modules. (Q2577534)

The objective of the matrix recognition project is a computer program which accepts as input a subset \(X\subseteq\text{GL}(d,q)\) for some \(d\) and some power \(q\) of a prime \(p\), and determines (among other things) a composition series for \(G:=\langle X\rangle\) [see, for example, \textit{C. R. Leedham-Green} et al., ``Recognizing matrix groups over finite fields'' in Computer Algebra Handbook. Foundations, Applications, Systems. Springer-Verlag, Berlin (2003; Zbl 1017.68162), pp. 459-460]. An important part of the project involves recognizing matrix groups which are almost simple modulo scalars. The alternating and symmetric groups of degree \(n\) have irreducible projective representations in \(\text{GL}(d,q)\) when \(d=n-2\) (if \(p\mid n\)) and \(d=n-1\) (if \(p\nmid n\)); these are their smallest degree representations. The object of the present paper is to give a probabilistic (Las Vegas) algorithm to determine when a group \(G=\langle X\rangle\) of the appropriate dimension is alternating or symmetric and, if it is, to give an embedding of \(G\) into \(Z_{q-1}\times S_n\). For small fields and generating sets the algorithm runs in time \(O(d^{\omega+1/2})\) where \(d^\omega\) is the number of field operations required for a matrix operation and the implied constant depends logarithmically on the parameter which determines the probability of success. The idea of the algorithm is to first determine a matrix \(x\) which represents a \(3\)-cycle or \((2,2)\)-element, and then to find a conjugate \(x'\) of \(x\) such that the permutations corresponding to \(x\) and \(x'\) have exactly one common point in their supports. This common point is then identified with a vector from which a series of vectors are constructed to form a natural basis for the underlying vector space. The major part of the paper is a description of how to carry out this process in an efficient manner. The authors' algorithm has been implemented in GAP4 by Stephen Howe and Maska Law.