Bipartite $q$-Kneser graphs and two-generated irreducible linear groups

Abstract

Let $V:=({\mathbb{F}}_q{)}^d$ be a $d$-dimensional vector space over the field ${\mathbb{F}}_q$ of order $q$. Fix positive integers $e_1,e_2$ satisfying $e_1+e_2=d$. Motivated by analysing a fundamental algorithm in computational group theory for recognising classical groups, we consider a certain quantity $P(e_1,e_2)$ which arises in both graph theory and group representation theory: $P(e_1,e_2)$ is the proportion of $3$-walks in the `bipartite $q$-Kneser graph' $\hat{I}{“}_{e_1,e_2}$ that are closed $3$-arcs. We prove that, for a group $G$ satisfying ${\mathrm{SL}}_d(q)⩽G⩽{\mathrm{GL}}_d(q)$, the proportion of certain element-pairs in $G$ called `$(e_1,e_2)$-stingray duos' which generate an irreducible subgroup is also equal to $P(e_1,e_2)$. We give an exact formula for $P(e_1,e_2)$, and prove that $1-q^{-1}-q^{-2}<P(e_1,e_2)<1-q^{-1}-q^{-2}+2q^{-3}-2q^{-5}$ for $2⩽e_2⩽e_1$ and $q⩾2$.These bounds have implications for the complexity analysis of the state-of-the-art algorithms to recognise classical groups, which we discuss in the final section.

23 pages, 1 figure, includes referee suggestions; some minor typos corrected