Algorithms to identify abundant \(p\)-singular elements in finite classical groups. (Q2907021)

The original aim of the recognition project was to find an algorithm which would quickly determine when a given set \(X\) of matrices from a special linear group \(\mathrm{SL}(n,q)\) generates the whole of the group [see \textit{P. M. Neumann} and \textit{C. E. Praeger}, Proc. Lond. Math. Soc., III. Ser. 65, No. 3, 555-603 (1992; Zbl 0770.20010)]. The project was extended to other subgroups of \(\mathrm{GL}(n,q)\); for example, to determine when \(X\) generates one of the classical linear groups \(G\). A fruitful idea has been to show that \(G\) contains many, easily identifiable, elements of a particular form. Then, if sufficiently many random elements from the group \(\langle X\rangle\) fail to be of this form, we can deduce with high probability that \(\langle X\rangle\neq G\). On the other hand, if elements of this form do occur (and certain other conditions hold), then we can deduce that \(\langle X\rangle=G\).NEWLINENEWLINE The authors introduce a new class (the \(p\)-abundant elements) which is useful for this purpose when \(G\) is one of the classical groups. Let \(p\) be a prime different from the characteristic of the underlying field, let \(m\) be an integer with \(n/2<m\leq n\) and let \(\Delta\) be the \(p'\)-part of \(q^m-1\). Suppose \(g\in\mathrm{GL}(n,q)\). Then \(g\) is a \((p,m)\)-abundant irreducible element if the characteristic polynomial of \(g\) has an irreducible factor \(h(x)\) of degree \(m\) such that \(x^\Delta-1\) is not divisible by \(h(x)\) (the roots of \(h(x)\) are necessarily \(p\)-power roots of \(1\), so \(g\) is a \(p\)-singular element). Very similar definitions hold for the other classical groups and also for reducible \((p,m)\)-abundant elements. For each of the classical groups \(G\) the paper by \textit{A. C. Niemeyer, T. Popiel} and \textit{C. E. Praeger} [``Abundant \(p\)-singular elements in finite classical groups'', \url{arXiv:1205.1454}] contains a complete classification of the pairs \(p,m\) for which \(G\) contains \((p,m)\)-abundant elements. The present paper gives an algorithm to determine whether an element \(g\) is \(p\)-abundant; the bit complexity of the algorithm is bounded by \((\log q)^{2+o(1)}\) times the cost of computing a characteristic polynomial.