2023/12/09 by S. P. Glasby, Alice C. Niemeyer, Glasby, S. P. +3
Computer Science · Mathematics · #05C35 #05C50 #20-08 #20C30 #Coding theory and cryptography #Combinatorics (math.CO) #FOS: Mathematics #Finite Group Theory Research #Group Theory (math.GR) #Limits and Structures in Graph Theory
paper · doi:10.48550/arxiv.2312.05529
openalex publication_date 2023/12/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let V:=(\mathbbFq)d be a d-dimensional vector space over the field \mathbbFq of order q. Fix positive integers e1,e2 satisfying e1+e2=d. Motivated by analysing a fundamental algorithm in computational group theory for recognising classical groups, we consider a certain quantity P(e1,e2) which arises in both graph theory and group representation theory: P(e1,e2) is the proportion of 3-walks in the `bipartite q-Kneser graph' Γe1,e2 that are closed 3-arcs. We prove that, for a group G satisfying \rm SLd(q)\leqslant G\leqslant\rm GLd(q), the proportion of certain element-pairs in G called `(e1,e2)-stingray duos' which generate an irreducible subgroup is also equal to P(e1,e2). We give an exact formula for P(e1,e2), and prove that 1-q-1-q-2< P(e1,e2)< 1-q-1-q-2+2q-3-2q-5 for 2\leqslant e2\leqslant e1 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.