A polynomial-time reduction algorithm for groups of semilinear or subfield class. (Q731236): Difference between revisions

Let \(G\) be an absolutely irreducible subgroup of \(\text{GL}(d,q)\) defined by a set of generators \(g_1,\dots,g_m\). Suppose that either \(G\) lies in the Aschbacher class \(\mathcal C_3\) (the class of semilinear groups) or \(\mathcal C_5\) (the class of groups conjugate in \(\text{GL}(d,q)\) to a group over a smaller field modulo the scalars) or the derived group \(G'\) is not absolutely irreducible. Then the authors describe a Las Vegas algorithm to find a nontrivial reduction of \(G\) with a running time of \[ O(d^3(m+d\log(\log d)\log q)+A\log(\log d)+Bd\log q) \] where (for a certain subgroup \(H\) of \(G'\) which can be generated by \(O(d\log q)\) elements) \(A\) bounds the number of field operations required to generate independent uniformly distributed random elements in \(G\) or \(H\), and similarly \(B\) bounds the number required to generate random elements in the normal closure of \(H\) in \(G\). The algorithm has been implemented in GAP and appears to work quite well on groups of degrees up to 100 when the field is not too large. The authors announce that it will be part of a GAP package \texttt{recog} for constructive group recognition.