The probability that two elements with large $1$-eigenspaces generate a classical group

Abstract

With high probability, among $O(\log n)$ independent randomly selected elements from a finite $n$-dimensional classical group, some pair of elements power to a $2$-element generating set for a naturally embedded classical subgroup of dimension $O(\log n)$. The $2$-element generating set produced consists of certain elements with large $1$-eigenspaces, called stingray elements. Underpinning this result is a new theorem on the generation of a finite classical group by a pair of stingray elements. In particular we show that, for classical groups not containing ${\mathrm{SL}}_n(q)$, the probability of generation is at least $0.975$. The explicit probability bounds we obtain will be applied to justify complexity analyses for new constructive recognition algorithms for finite classical groups.

80 pages, 19 tables