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

arXiv (Cornell University)

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' $Γ_{e_1,e_2}$ that are closed $3$-arcs. We prove that, for a group $G$ satisfying ${\rm SL}_d(q)\leqslant G\leqslant{\rm 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\leqslant e_2\leqslant e_1$ and $q\geqslant2$.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.

Authors 3

1. S. P. Glasby Aachen Chair for Algebra and Representation Theory

   RWTH Aachen University

   Affiliation as printed

   Chair for Algebra and Representation Theory , RWTH Aachen University , Pontdriesch 10-16 , 52062 , Aachen , Germany

2. Alice C. Niemeyer

   The University of Western Australia

   Affiliation as printed

   Centre for the Mathematics of Symmetry and Computation , The University of Western Australia , 35 Stirling Highway , 6009 , Perth , Australia

3. Cheryl E. Praeger

   The University of Western Australia

   Affiliation as printed

   Centre for the Mathematics of Symmetry and Computation , The University of Western Australia , 35 Stirling Highway , 6009 , Perth , Australia