# Diameter of classical groups generated by transvections

Sean Eberhard  Sean Eberhard, Mathematical Sciences Research Centre, Queen’s
University Belfast, Belfast BT7 1NN, UK<EMAIL_ADDRESS>
###### Abstract.

Let $G$ be a finite classical group generated by transvections, i.e., one of
$\operatorname{SL}_{n}(q)$, $\operatorname{SU}_{n}(q)$,
$\operatorname{Sp}_{2n}(q)$, or
$\operatorname{O}^{\pm}_{2n}(q)~{}(q~{}\text{even})$, and let $X$ be a
generating set for $G$ containing at least one transvection. Building on work
of Garonzi, Halasi, and Somlai, we prove that the diameter of the Cayley graph
$\operatorname{Cay}(G,X)$ is bounded by $(n\log q)^{C}$ for some constant $C$.
This confirms Babai’s conjecture on the diameter of finite simple groups in
the case of generating sets containing a transvection.

By combining this with a result of the author and Jezernik it follows that if
$G$ is one of $\operatorname{SL}_{n}(q)$, $\operatorname{SU}_{n}(q)$,
$\operatorname{Sp}_{2n}(q)$ and $X$ contains three random generators then with
high probability the diameter $\operatorname{Cay}(G,X)$ is bounded by
$n^{O(\log q)}$. This confirms Babai’s conjecture for non-orthogonal classical
simple groups over small fields and three random generators.

The author is supported by the Royal Society.

##  1\. Introduction

This paper represents another step in the direction of the long-standing
conjecture of Babai [BS92]*Conjecture 1.7 on the diameter of finite simple
groups with respect to arbitrary generating sets. Given $g\in
G=\left\langle{X}\right\rangle$, let $\ell_{X}(g)$ denote the minimal word
length of $g$ with respect to $X\cup X^{-1}$, and for $S\subseteq G$ let
$\ell_{X}(S)=\sup_{g\in S}\ell_{X}(g)$. Babai’s conjecture predicts that
$\ell_{X}(G)\leq(\log|G|)^{O(1)}$ for any (nonabelian) finite simple group $G$
and generating set $X$. We call $\ell_{X}(G)$ the _diameter_ of $G$ with
respect to $X$; it is equivalent to the diameter of the undirected Cayley
graph $\operatorname{Cay}(G,X)$.

The past two decades have seen a slew of progress on Babai’s conjecture. In
particular, following the seminal work of Helfgott [helfgott],
Breuillard–Green–Tao [BGT], and Pyber–Szabó [pyber--szabo], the conjecture is
now completely resolved in bounded Lie rank. In the case of alternating groups
$A_{n}$, while Babai’s conjecture predicts that the diameter should be bounded
by a polynomial in $n$, a result of Helfgott and Seress [helfgott--seress,
helfgott-unified] establishes a quasipolynomial bound. Recently Bajpai, Dona,
and Helfgott [BDH] proved a bound for classical Chevalley groups of large
characteristic of the form $(\log|G|)^{O(r^{5})}$, where $r$ is the rank of
$G$.

Much stronger results are known about diameter with respect to typical
generators (as opposed to worst-case generators, as in Babai’s conjecture). In
this formulation we assume the generators are chosen uniformly at random and
we are interested in results that fail with asymptotically negligible
probability. Polynomial (in $n$) bounds for the diameter of $A_{n}$ with
respect to typical generators were established in [babai--hayes, schlage-
puchta, HSZ]. More recently, it was proved in [EJ] that if
$G=\operatorname{Cl}_{n}(q)$ is a classical group with defining module
$\mathbf{F}_{q}^{n}$ (so $\log|G|\approx cn^{2}\log q$) then $\ell_{X}(G)\leq
q^{2}n^{O(1)}$ with high probability provided that $X$ includes at least
$q^{C}$ random generators.

Pyber has proposed111Personal communication. It was also previously emphasized
in the introductions to [H] and [EJ]. The programme was inspired by [BBS].
that Babai’s conjecture should be broken down into three parts. Since the
conjecture is resolved in bounded rank, we may assume that $G=A_{n}$ or
$G=\operatorname{Cl}_{n}(q)$, $q=p^{f}$, that is, one of the groups
$\operatorname{SL}_{n}(q)$, $\operatorname{SU}_{n}(\sqrt{q})$,
$\operatorname{Sp}_{n}(q)$, $\Omega_{n}^{\varepsilon}(q)$. The _degree_ of an
element $g\in G$ is the size of its support if $G=A_{n}$ or the rank of $g-1$
if $G=\operatorname{Cl}_{n}(q)$. Now let $X$ be an arbitrary generating set
for $G$. Pyber’s programme consists of the following subproblems:

  1. (1)

Find a nontrivial element $g\in G$ of polylogarithmic length over $X$ whose
degree is at most $(1-\epsilon)n$ for some constant $\epsilon>0$.

  2. (2)

Assuming $X$ includes an element of degree at most $(1-\epsilon)n$ as above,
find a nontrivial element $g\in G$ of polylogarithmic length over $X$ whose
degree is minimal in $G$.

  3. (3)

Assuming $X$ includes an element of minimal degree, show that every element of
$G$ has polylogarithmic length over $X$.

Part (1) is likely the most difficult. Part (2) has been solved for $G=A_{n}$
for $\epsilon=0.67$ in [BBS] and more recently for $\epsilon=0.37$ in [BGHHSS]
(doing the same for an arbitrary constant $\epsilon>0$ is a fascinating open
problem). Part (3) is actually trivial for $G=A_{n}$, since the number of
$3$-cycles in $A_{n}$ is less than $n^{3}$, but for classical groups it is not
at all trivial and in fact the focus of this paper.

Excluding the case of $\Omega_{n}^{\epsilon}(q)$ (which we leave to future
work), the elements of minimal degree in a classical group
$G=\operatorname{Cl}_{n}(q)$ are the transvections. By recent work of Halasi
and Garonzi–Halasi–Somlai [H, GHS] we have a suitable bound for $\ell_{X}(G)$
for $\operatorname{SL}_{n}(q)$, $\operatorname{SU}_{n}(\sqrt{q})$,
$\operatorname{Sp}_{n}(q)$ and any generating set $X$ containing a
transvection, excluding all cases of characteristic $2$ and a few cases of
characteristic $3$.

######  Theorem 1.1 (Garonzi–Halasi–Somlai, [GHS]*Theorem 1.5).

Let $G$ be one of the non-orthogonal classical groups
$\operatorname{SL}_{n}(q)$, $\operatorname{SU}_{n}(\sqrt{q})$ ($q$ square),
$\operatorname{Sp}_{n}(q)$ ($n$ even) with defining module
$\mathbf{F}_{q}^{n}$. Let $X$ be a generating set for $G$ containing a
transvection. Then

$\ell_{X}(G)\leq(n\log q)^{O(1)}$

provided that

  * •

$q$ is odd,

  * •

$q\neq 9,81$ if $G=\operatorname{SL}_{n}(q)$,

  * •

$q\neq 81$ if $G=\operatorname{SU}_{n}(\sqrt{q})$,

  * •

$q\neq 9$ if $G=\operatorname{Sp}_{n}(q)$.

In this paper we deal with the omissions above. It is also natural to include
the (imperfect) orthogonal groups in characteristic $2$. Our main theorem is
the following.

######  Theorem 1.2.

Let $G\leq\operatorname{SL}_{n}(q)$ be an irreducible classical group
generated by transvections, i.e., one of the following groups:

$\displaystyle\operatorname{SL}_{n}(q)$ $\displaystyle(n\geq 2),$
$\displaystyle\operatorname{SU}_{n}(\sqrt{q})$ $\displaystyle(n\geq
3,q=q_{0}^{2},(n,q_{0})\neq(3,2)),$ $\displaystyle\operatorname{Sp}_{n}(q)$
$\displaystyle(n=2m\geq 4),$ $\displaystyle\operatorname{O}_{n}^{\pm}(q)$
$\displaystyle(n=2m\geq 6,p=2).$

Let $X$ be a generating set for $G$ containing a transvection. Then

$\ell_{X}(G)\leq(n\log q)^{O(1)}.$

It follows that Babai’s conjecture [BS92]*Conjecture 1.7 holds for the simple
groups $\operatorname{PSL}_{n}(q)$, $\operatorname{PSU}_{n}(\sqrt{q})$, and
$\operatorname{PSp}_{n}(q)$, as well as the index-2 overgroup
$\operatorname{PO}_{n}^{\pm}(q)$ of the simple group
$\operatorname{P\Omega}_{n}^{\pm}(q)$ for $q$ even, for generating sets
containing the image of a transvection. By combining with [EJ]*Theorem 1.1, we
also get the following corollary, which confirms Babai’s conjecture for all
non-orthogonal classical groups over small fields with respect to three random
generators. (As above, this is new only for $p=2$ and a few $p=3$ cases.)

######  Corollary 1.3.

Let $G$ be in one of the following intervals:

$\displaystyle\operatorname{SL}_{n}(q)\leq G\leq\operatorname{GL}_{n}(q),$
$\displaystyle\operatorname{SU}_{n}(\sqrt{q})\leq
G\leq\operatorname{GU}_{n}(\sqrt{q}),$ $\displaystyle
G=\operatorname{Sp}_{2m}(q).$

Assume $\log q<cn/\log^{2}n$ for a sufficiently small constant $c>0$. Let
$X=\\{x,y,z\\}$ where $x,y,z\in G$ are uniformly random. Then with probability
$1-e^{-cn}$ we have

$\ell_{X}(G)\leq n^{O(\log q)}.$

The proof of Theorem 1.2thm:main does not consist merely in reviewing [GHS]
and dealing with technicalities. There is a much greater variety of
irreducible subgroups generated by transvections in characteristic $2$ than in
odd characteristic, and these subgroups arise as obstructions in the proof.
While Garonzi, Halasi, and Somlai relied on more elementary results of Dickson
and Humphries, our main tool is the following deep theorem of Kantor, building
on previous work of Wagner, Piper, and Pollatsek. The theorem classifies
irreducible subgroups of $\operatorname{SL}_{n}(q)$ generated by transvections
(and thus in particular gives additional context to Theorem 1.2thm:main).

######  Theorem 1.4 (Kantor).

Let $n\geq 2$, $K=\mathbf{F}_{q}$, $q=p^{f}$, and let
$G\leq\operatorname{SL}_{n}(q)$ be an irreducible subgroup generated by
transvections, not contained in a subfield subgroup. Then $G$ is one of the
following up to conjugacy:

  1. (1)

$\operatorname{SL}_{n}(q)$,

  2. (2)

$\operatorname{SU}_{n}(\sqrt{q})$ where $q$ is a square,

  3. (3)

$\operatorname{Sp}_{n}(q)$ where $n$ is even,

  4. (4)

$\operatorname{O}^{\pm}_{n}(q)$ where $n$ and $q$ are even,

  5. (5)

$C_{a}^{n-1}\rtimes S_{n}$ where $a>1$ is odd and $q$ is the smallest power of
$2$ such that $a\mid q-1$,

  6. (6)

$S_{n+1}$ or $S_{n+2}$ where $n$ is even and $q=2$,

  7. (7)

$\operatorname{SL}_{2}(5)<\operatorname{SL}_{2}(9)$,

  8. (8)

$3\cdot A_{6}<\operatorname{SL}_{3}(4)$,

  9. (9)

$3\cdot\operatorname{P\Omega}^{-,\pi}_{6}(3)<\operatorname{SL}_{6}(4)$.

######  Remark 1.5.

The proof of Theorem 1.4thm:classification is somewhat scattered in the
literature. For $q$ odd see [wagner] or [ZS]. If $q$ is even then
[pollatsek]*Theorem 1 (which depends on a result of Piper) asserts that
$G\cong 3\cdot A_{6}$ in $\operatorname{SL}_{3}(4)$ or the transvections in
$G$ form a single conjugacy class of odd transpositions in the sense of
Aschbacher. Now [kantor]*Theorem II (which depends on deep results of Fischer,
Aschbacher, and Timmesfeld) delineates the remaining possibilities.

In the rest of the paper, when $G$ is a irreducible linear group generated by
transvections, we say $G$ has _linear_ , _unitary_ , _symplectic_ ,
_orthogonal_ , _monomial_ , or _symmetric_ _type_ according to cases (1)–(6)
respectively of Theorem 1.4thm:classification. In the three remaining cases
(which will not concern us) we say $G$ has _exceptional type_. We refer to the
linear, unitary, symplectic, and orthogonal cases collectively as _classical_.

In the course of the paper we build on many of the ideas and tools already
developed in [GHS, H], particularly the transvection graph and its associated
features such as symplectic and unitary cycles. An effort has been made
however to keep the present paper reasonably self-contained and it should not
be necessary to refer to [GHS, H] extensively. Where a proposition in the
present paper closely parallels a corresponding proposition in [GHS, H], a
brief note is made to that effect. Moreover, while we are free to assume
$p\in\\{2,3\\}$ throughout, doing so would not simplify the paper in any way,
and simplifications are obtained for $p\geq 3$ (namely, we avoid many of the
difficult calculations of [GHS]*Sections 4.2–4.3).

### Acknowledgments

I am indebted to Laszlo Pyber, Bill Kantor, and Daniele Garzoni for comments
and guidance. I am also grateful to the anonymous referee for noticing an
important oversight, as well as correcting a great many minor errors/typos.

##  2\. Bounded rank

Babai’s conjecture is known for simple groups of Lie type of bounded rank.
This is a corollary of the independent work of Breuillard–Green–Tao and
Pyber–Szabó.

######  Theorem 2.1 (Breuillard–Green–Tao [BGT], Pyber–Szabó [pyber--szabo]).

Let $G$ be a finite simple group of Lie type of rank $n$ and let $X$ be a
generating set for $G$. Then

$\ell_{X}(G)\leq O{\left(\frac{\log|G|}{\log|X|}\right)}^{O_{n}(1)}.$

Theorem 1.2thm:main in bounded rank follows immediately from this and standard
tools, as detailed below.

######  Proposition 2.2.

In the situation of Theorem 1.2thm:main we have

$\ell_{X}(G)\leq O{\left(\frac{\log|G|}{\log|X|}\right)}^{O_{n}(1)}.$

###### Proof.

Assume $X=X^{-1}$ and $1\in X$ without loss of generality. Note that
$[G:G^{\prime}]=2$ in the orthogonal case and $G=G^{\prime}$ in the other
cases. Therefore by Schreier’s lemma $Y=X^{3}\cap G^{\prime}$ is a generating
set for $G^{\prime}$. Moreover $|Y|\geq|X|/2$. Indeed, if $G^{\prime}<G$,
since $X$ generates $G$ there is some $x_{0}\in X\smallsetminus G^{\prime}$.
Since $X\cap x_{0}G^{\prime}\subseteq x_{0}(X^{2}\cap G^{\prime})$, we have

$|X|=|X\cap G^{\prime}|+|X\cap x_{0}G^{\prime}|\leq 2|X^{2}\cap
G^{\prime}|\leq 2|Y|.$

Applying Theorem 2.1thm:babai-bounded-rank to the simple quotient
$S=G^{\prime}/Z(G^{\prime})$, it follows that $Y^{m}Z(G^{\prime})=G^{\prime}$,
where

$m\leq O(\log|S|/\log|Y|)^{O_{n}(1)}\leq O(\log|G|/\log|X|)^{O_{n}(1)}.$

In particular $|Y^{m}|\geq|G^{\prime}/Z(G^{\prime})|$. Applying Freiman’s 3/2
theorem (see [tao-book]*Theorem 1.5.2 and Proposition 1.5.4) we have (for any
$k\geq 1$) either $Y^{2^{k}m}=G^{\prime}$ or

$|Y^{2^{k}m}|\geq(3/2)^{k}|Y^{m}|\geq(3/2)^{k}|G^{\prime}/Z(G^{\prime})|.$

If $G$ is symplectic or orthogonal we have $|Z(G^{\prime})|\leq 2$, so with
$k=2$ we must have $Y^{4m}=G^{\prime}$ and thus $X^{12m+1}=G$.

If $G$ is linear or unitary we have $G=G^{\prime}$ and $|Z(G)|\leq n$, so

$|Y^{2^{k}m}|\geq\min(|G|,(3/2)^{k}|G|/n).$

By Landazuri–Seitz [landazuri--seitz] and [nikolov--pyber]*Corollary 2.5, the
minimal degree of a nontrivial complex representation of $G$ is at least
$|G|^{c/n}>q^{c^{\prime}n}$ for some constants $c,c^{\prime}>0$. Applying
[nikolov--pyber]*Theorem 1, we get $Y^{3\cdot 2^{k}m}=G$ provided that
$(3/2)^{k}/n>q^{-c^{\prime}n/3}$. It suffices to take $k$ to be a suitable
constant depending on $c^{\prime}$. Thus $Y^{m^{\prime}}=X^{3m^{\prime}}=G$
for some $m^{\prime}\leq O(\log|G|/\log|X|)^{O_{n}(1)}$. ∎

This special case is used in the proof of Theorem 1.2thm:main in two
essentially different ways. First, it allows us to assume that $n$ is larger
than any fixed constant, which enables to avoid low-rank pathologies. Second,
in the course of the proof of Theorem 1.2thm:main we will apply Proposition
2.2main-thm-bounded-rank to a wide variety of bounded-rank subgroups.

##  3\. The transvection graph

Following [H, GHS] we define a graph based on a collection of transvections.
To motivate the definition we first recall the concept of the transposition
graph (which we will also use).

If $T\subseteq\operatorname{Sym}(\Omega)$ is a set of transpositions, the
_transposition graph_ $\Gamma(T)$ is the graph with vertex set $\Omega$ and
edge set $\\{ij:(ij)\in T\\}$.

######  Proposition 3.1.

Let $T\subseteq\operatorname{Sym}(\Omega)$ be a set of transpositions and let
$G=\left\langle{T}\right\rangle$. Then $G$ is the direct product of the full
symmetric groups on the components of $\Gamma(T)$. In particular the following
are equivalent:

  1. (1)

$\Gamma(T)$ is connected;

  2. (2)

$G$ is transitive;

  3. (3)

$G=\operatorname{Sym}(\Omega)$.

###### Proof.

First assume $\Gamma(T)$ is connected. We will prove
$G=\operatorname{Sym}(\Omega)$ by induction on $n$, the result being obvious
if $n\leq 1$. We may assume $\Gamma(T)$ is a tree by replacing $T$ with a
subset. Let $i$ be a leaf of $\Gamma(T)$, let $t_{0}=(ij)\in T$, and let
$T_{0}=T\smallsetminus\\{t_{0}\\}$. Then $\Gamma(T_{0})$ can be identified
with a tree with vertex set $\Omega_{0}=\Omega\smallsetminus\\{i\\}$, so by
induction
$G_{0}=\left\langle{T_{0}}\right\rangle=\operatorname{Sym}(\Omega_{0})$, and
it follows easily that
$G=\left\langle{G_{0},(ij)}\right\rangle=\operatorname{Sym}(\Omega)$.

In general, let $\Omega_{1},\dots,\Omega_{k}$ be the components of $\Gamma(T)$
and let $T_{i}\subseteq T$ be the set of transpositions in $T$ supported on
$\Omega_{i}$. Then $T=T_{1}\cup\cdots\cup T_{k}$ and the elements of $T_{i}$
commute with the elements of $T_{j}$ for $i\neq j$, so
$G=G_{1}\times\cdots\times G_{k}$ where
$G_{i}=\left\langle{T_{i}}\right\rangle$. By the connected case,
$G_{i}=\operatorname{Sym}(\Omega_{i})$ for each $i$. ∎

Now let $K$ be a field of characteristic $p>0$ and let $V\cong K^{n}$ be a
vector space over $K$ of finite dimension $n\geq 2$. A _transvection_ is an
element $t\in\operatorname{SL}(V)$ such that $t-1$ is a rank-one map. Let
$\mathfrak{T}\subseteq\operatorname{SL}(V)$ be the set of transvections. Each
transvection $t\in\mathfrak{T}$ has the form

$t=1+v\otimes\phi\qquad(v\in V,\phi\in V^{*},\phi(v)=0).$

We make $\mathfrak{T}$ into a directed graph $\Gamma(\mathfrak{T})$ by
declaring there to be a directed edge $t\to s$ if and only if ${(t-1)(s-1)\neq
0}$. Put another way, there is an edge $1+v\otimes\phi\to 1+u\otimes\psi$ if
and only if $\phi(u)\neq 0$. For any subset $T\subseteq\mathfrak{T}$ we denote
by $\Gamma(T)$ the corresponding induced subgraph. We also define linear
subspaces $V(T)\leq V$ and $V^{*}(T)\leq V^{*}$ by

$\displaystyle V(T)$ $\displaystyle=\left\langle{v:1+v\otimes\phi\in
T}\right\rangle=\sum_{t\in T}\operatorname{im}(t-1)=[V,G],$ $\displaystyle
V^{*}(T)$ $\displaystyle=\left\langle{\phi:1+v\otimes\phi\in
T}\right\rangle=\sum_{t\in T}\operatorname{ker}(t-1)^{\perp}=(V^{G})^{\perp},$

where $G=\left\langle{T}\right\rangle$. Here $[V,G]$ denotes the commutator of
$V$ and $G$ as subgroups of $V\rtimes G$, and $V^{G}$ denotes the space of
$G$-invariants in $V$.

Let $T\subseteq\mathfrak{T}$ be an arbitrary set of transvections and let
$G=\left\langle{T}\right\rangle$. In the rest of this section we describe how
important properties of $G$ can be detected through careful examination of the
transvection graph $\Gamma(T)$ as well as the subspaces $V(T)$ and $V^{*}(T)$.
We start with irreducibility of $G$.

######  Proposition 3.2 ([GHS]*Theorem 3.1).

The group $G\leq\operatorname{SL}(V)$ is irreducible if and only if

  1. (1)

$V(T)=V$,

  2. (2)

$V^{*}(T)=V^{*}$,

  3. (3)

$\Gamma(T)$ is strongly connected.

###### Proof.

_Necessity:_ Suppose $G$ is irreducible. Then $[V,G]=V$ and $V^{G}=0$, so (1)
and (2) hold. Now suppose $S$ is a nonempty subset of $T$ with no incoming
edges in $\Gamma(T)$. Then, for $t\in T$ and $s\in S$,

$(t-1)(s-1)\neq 0\implies t\in S.$ (3.1)

Let $U=V(S)$. Then $U$ is nonzero and
$\left\langle{S}\right\rangle$-invariant, and the above equation shows that
$T\smallsetminus S$ acts trivially on $U$, so $U$ is $G$-invariant, so $U=V$.
Thus for every $t\in T$ there is some $s\in S$ such that $(t-1)(s-1)\neq 0$,
whence $t\in S$ by (3.1). Hence (3) holds.

_Sufficiency:_ Let $U\leq V$ be a nonzero $G$-invariant subspace. Let
$S\subseteq T$ be the set of $s$ such that $\operatorname{im}(s-1)\leq U$. Let
$u\in U\smallsetminus\\{0\\}$. By (2) there is at least one $t\in T$ such that
$(t-1)u\neq 0$. By $G$-invariance of $U$ it follows that
$\operatorname{im}(t-1)\leq U$, so $t\in S$. Hence $S$ is nonempty, and the
same calculation shows that $S$ has no incoming edges, so by (3) we have
$S=T$. Thus by (1) we have $U=V$. Hence $G$ is irreducible. ∎

We say $G$ _defined over_ a subfield $L\leq K$ if for some basis of $V$ the
elements of $G$ are represented by matrices with entries in $L$. The _defining
field_ of $G$ is the smallest field such that $G$ is defined over $L$.

Given transvections $t_{1},\dots,t_{k}\in\mathfrak{T}$, the _weight_ of the
tuple $(t_{1},\dots,t_{k})$ is defined as

$w(t_{1},\dots,t_{k})=\operatorname{tr}((t_{1}-1)\cdots(t_{k}-1)).$ (3.2)

If $t_{i}=1+v_{i}\otimes\phi_{i}$ for each $i$ then

$w(t_{1},\dots,t_{k})=\phi_{1}(v_{2})\phi_{2}(v_{3})\cdots\phi_{k}(v_{1}).$

Note that $w(t_{1},\dots,t_{k})\neq 0$ if and only if $t_{1},\dots,t_{k}$ is a
directed cycle in $\Gamma(\mathfrak{T})$.

If $T\subseteq\mathfrak{T}$ we denote by $L_{k}(T)$ the subfield generated by
the weights of the cycles of $\Gamma(T)$ of length at most $k$. Let
$L(T)=\bigcup_{k=1}^{\infty}L_{k}(T)$.

######  Proposition 3.3 (cf. [GHS]*Section 3.2).

Assume $G$ is irreducible. Then $L(T)$ is the defining field of $G$.

###### Proof.

It follows from (3.2) (and induction on $k$) that $L_{k}(T)$ is equal to the
field generated by $\\{\operatorname{tr}(g):\ell_{T}(g)\leq k\\}$, so
$L(T)=\bigcup_{k=1}^{\infty}L_{k}(T)$ is the field generated by
$\\{\operatorname{tr}(g):g\in G\\}$ (the _trace field_ of $G$). It is well-
known that the latter is precisely the defining field of $G$ in positive
characteristic (see [isaacs-book]*Corollaries 9.5(c) and 9.23). ∎

Again suppose $t_{1},\dots,t_{k}\in\mathfrak{T}$. We define

$d_{s}(t_{1},\dots,t_{k})=w(t_{1},\dots,t_{k})-(-1)^{k}w(t_{k},\dots,t_{1})$

and we call the tuple $(t_{1},\dots,t_{k})$ _symplectic_ if $d_{s}=0$.
Similarly, if $\theta$ is an involution of $K$, we define

$d_{\theta}(t_{1},\dots,t_{k})=w(t_{1},\dots,t_{k})-(-1)^{k}w(t_{k},\dots,t_{1})^{\theta},$

and we call the tuple $(t_{1},\dots,t_{k})$ $\theta$-_unitary_ if
$d_{\theta}=0$. (If $K$ is the field $\mathbf{F}_{q}$ where $q$ is a square
then there is a unique involution of $K$ and we may drop the “$\theta$-”
prefix.) Note that if $(t_{1},\dots,t_{k})$ is symplectic or $\theta$-unitary
then it is a cycle in $\Gamma(\mathfrak{T})$ if and only if it is a two-way
cycle.

######  Proposition 3.4 (cf. [GHS]*Theorem 3.12).

Assume $G$ is irreducible. Let $D$ be the directed diameter of $\Gamma(T)$.

  1. (1)

There is a $G$-invariant symplectic form if and only if every cycle of
$\Gamma(T)$ of length at most $2D+1$ is symplectic.

  2. (2)

There is a $G$-invariant $\theta$-unitary form if and only if every cycle of
$\Gamma(T)$ of length at most $2D+1$ is $\theta$-unitary.

###### Proof.

We can prove both statements at once by seeking a $G$-invariant nondegenerate
sesquilinear form $f$ such that $f(x,y)+f(y,x)^{\theta}=0$ identically, where
$\theta$ is an automorphism of $K$ of order at most $2$. If $\theta=1$ and
$p=2$ then we additionally require $f(x,x)=0$ identically. If $\theta$ is
nontrivial we obtain a unitary form by multiplying $f$ by a nonzero scalar
$\lambda$ such that $\lambda^{\theta}=-\lambda$. We use the unitary language
for both cases.

If $G$ preserves such a form $f$ then $V$ and $V^{*}$ can be identified by
defining $v^{*}(u)=f(u,v)$ for all $u,v\in V$, and the resulting map $v\mapsto
v^{*}$ is a $\theta$-semilinear isomorphism of $V$ with $V^{*}$. The
transvections in $\operatorname{Aut}(f)$ are precisely the transvections of
the form $1+\lambda v\otimes v^{*}$ with
$\lambda\in\operatorname{Fix}(\theta)$ and $f(v,v)=0$. Thus the weight of a
cycle $t_{1},\dots,t_{k}$, where $t_{i}=1+\lambda_{i}v_{i}\otimes v_{i}^{*}$,
is

$w(t_{1},\dots,t_{k})=\lambda_{1}\cdots\lambda_{k}f(v_{2},v_{1})\cdots
f(v_{1},v_{k})\\\ =(-1)^{k}w(t_{k},\dots,t_{1})^{\theta},$

so every cycle is unitary.

Conversely suppose every cycle in $\Gamma(T)$ of length at most $2D+1$ is
unitary. For each $t\in T$ fix a representation $t=1+v_{t}\otimes\phi_{t}$. We
claim we can choose nonzero scalars $\lambda_{t}\in\operatorname{Fix}(\theta)$
for each $t\in T$ such that

$\lambda_{t}\phi_{t}(v_{s})+\lambda_{s}\phi_{s}(v_{t})^{\theta}=0\qquad(t,s\in
T).$ (3.3)

Indeed, first note that every edge $(t,s)$ in $\Gamma(T)$ is two-way since
every edge is contained in a cycle of length at most $D+1$, and every such
cycle is unitary. Now for any path $\gamma=(t_{0},t_{1},\dots,t_{k})$ in
$\Gamma(T)$ of length at most $D+1$ define

$\lambda_{\gamma}=(-1)^{k}\frac{{\left(\phi_{0}(v_{1})\cdots\phi_{k-1}(v_{k})\right)}^{\theta}}{\phi_{k}(v_{k-1})\cdots\phi_{1}(v_{0})}.$

The cycle condition ensures that
$\lambda_{\gamma}=\lambda_{\gamma^{\prime}}^{\theta}$ whenever $\gamma$ and
$\gamma^{\prime}$ have the same endpoints and combined length at most $2D+1$.
In particular $\lambda_{\gamma}\in\operatorname{Fix}(\theta)$ if $\gamma$ has
length at most $D$. Choose $t_{0}\in T$ arbitrarily and define $\lambda_{t}$
to be the common value of $\lambda_{\gamma}$ for paths $\gamma$ from $t_{0}$
to $t$ of length at most $D$. Then $(\lambda_{t})$ is the required global
solution to (3.3).

Now define $L:K^{T}\to V\times V^{*}$ by

$L(x)=(L_{1}(x),L_{2}(x))={\left(\sum_{t\in T}x_{t}v_{t},\sum_{t\in
T}x_{t}^{\theta}\lambda_{t}\phi_{t}\right)}.$

By (3.3) we have

$\lambda_{t}\phi_{t}(L_{1}(x))+L_{2}(x)(v_{t})^{\theta}=0\qquad(t\in T,x\in
K^{T}).$

In particular, since $V(T)=V$ and $V^{*}(T)=V^{*}$, we have $L_{1}(x)=0$ if
and only if $L_{2}(x)=0$. Thus $\operatorname{im}(L)\subseteq V\times V^{*}$
is the graph of a $\theta$-semilinear isomorphism $*:V\to V^{*}$ such that
$v_{t}^{*}=\lambda_{t}\phi_{t}$ for all $t\in T$. Define $f(u,v)=v^{*}(u)$ for
$u,v\in V$. Then $f$ is sesquilinear and nondegenerate, and by (3.3) we have

$f(v_{s},v_{t})+f(v_{t},v_{s})^{\theta}=0\qquad(t,s\in T),$

which implies that $f$ is hermitian antisymmetric since
$\operatorname{im}(T)=V$. Moreover for every $t\in T$ we have

$f(v_{t},v_{t})=v_{t}^{*}(v_{t})=\lambda_{t}\phi_{t}(v_{t})=0.$

In particular if $p=2$ and $\theta=1$ then $f$ is alternating. Finally, since
each $t\in T$ has the form
$t=1+v_{t}\otimes\phi_{t}=1+\lambda_{t}^{-1}v_{t}\otimes v_{t}^{*}$ with
$\lambda_{t}\in\operatorname{Fix}(\theta)$, $f$ is $G$-invariant, as required.
∎

Finally, we explain how to determine from the transvection graph whether $G$
is contained in an orthogonal group. Note that this is only relevant in
characteristic $2$.

######  Proposition 3.5.

Assume $K$ is a perfect field of characteristic $2$. Assume $G$ is irreducible
and preserves a symplectic form $f$. Let $v\mapsto v^{*}$ be the isomorphism
$V\to V^{*}$ defined by $v^{*}(u)=f(u,v)$. Then for each $t\in T$ there is a
unique $v\in V$ such that $t=1+v\otimes v^{*}$, and $G$ preserves a quadratic
from associated to $f$ if and only if for every linear relation

$\sum_{i=1}^{m}\lambda_{i}v_{i}=0\qquad(t_{i}=1+v_{i}\otimes v_{i}^{*}\in
T~{}\text{for}~{}i=1,\dots,m)$ (3.4)

with $m\leq n+1$ we have the corresponding quadratic relation

$\sum_{i=1}^{m}\lambda_{i}^{2}+\sum_{1\leq i<j\leq
m}\lambda_{i}\lambda_{j}f(v_{i},v_{j})=0.$ (3.5)

###### Proof.

We noted in the proof of the previous proposition that each transvection
$t\in\mathfrak{T}\cap\operatorname{Aut}(f)$ can be written $t=1+\lambda
v\otimes v^{*}$ with $\lambda\in K$. Since $K$ is perfect, $\lambda=\mu^{2}$
for some $\mu\in K$, so $t=1+u\otimes u^{*}$ where $u=\mu v$. Moreover if
$u\otimes u^{*}=w\otimes w^{*}$ ($w\in V$) then $u=\lambda w$ for some
$\lambda$ such that $\lambda^{2}=1$, whence $\lambda=1$. Therefore each $t\in
T$ has the form $1+v_{t}\otimes v_{t}^{*}$ and $v_{t}$ is determined uniquely
by $t$.

Suppose $Q$ is a quadratic form associated to $f$. By a well-known direct
calculation, a transvection $t=1+v\otimes v^{*}$ preserves $Q$ if and only if
$Q(v)=1$. Suppose $G$ preserves a quadratic form $Q$. Then $Q(v)=1$ for all
$t=1+v\otimes v^{*}\in T$. By applying $Q$ to (3.4) we get (3.5).

Conversely, suppose (3.4) implies (3.5) identically. Since $G$ is irreducible,
$V(T)=V$ by Proposition 3.2prop:irreducible, so there is a basis
$v_{1},\dots,v_{n}$ among the vectors $v$ such that $1+v\otimes v^{*}\in T$.
There is a unique quadratic form $Q$ associated to $f$ such that $Q(v_{i})=1$
for $i=1,\dots,n$. Now, if $1+v\otimes v^{*}\in T$, because
$v_{1},\dots,v_{n}$ is a basis we have some linear relation

$v+\sum_{i=1}^{n}\lambda_{i}v_{i}=0.$

To this linear relation we can apply either (3.4) $\implies$ (3.5) or we can
apply the quadratic from $Q$. By comparing the results we find that $Q(v)=1$.
Thus $Q(v)=1$ for all $1+v\otimes v^{*}\in T$, so $Q$ is $G$-invariant. ∎

##  4\. Some splitting results

Continue to assume $K$ is a field of characteristic $p>0$ and $V\cong K^{n}$
is a vector space of dimension $n\geq 2$. As before
$\mathfrak{T}\subseteq\operatorname{SL}(V)$ denotes the set of transvections,
$T\subseteq\mathfrak{T}$, and $G=\left\langle{T}\right\rangle$.

By Proposition 3.2prop:irreducible, $G$ is irreducible if and only if
$\Gamma(T)$ is strongly connected and $V(T)=V$ and $V^{*}(T)=V^{*}$. In this
section we consider the situation in which $\Gamma(T)$ is strongly connected
but one or other of the latter conditions may fail.

Throughout this section,

$U=V(T)=[V,G],\qquad W=V(T)\cap V^{*}(T)^{\perp}=[V,G]^{G}.$

Observe that $U$ and $W$ are $G$-invariant subspaces, so $G$ acts naturally on
the section $U/W$. Let $g\mapsto\overline{g}$ denote the homomorphism
$G\to\operatorname{SL}(U/W)$.

######  Proposition 4.1.

Assume $\Gamma(T)$ is strongly connected. Then $\overline{T}$ is a set of
transvections of $U/W$ and the map $t\mapsto\overline{t}$ defines a graph
homomorphism $\Gamma(T)\to\Gamma(\overline{T})$ that is surjective on both
vertices and edges. Moreover, the weights of corresponding cycles are equal.
In particular, $\overline{G}$ is irreducible.

###### Proof.

If $t\in T$, the strong connectedness of $\Gamma(T)$ ensures the existence of
$s,s^{\prime}\in T$ such that $(s-1)(t-1)\neq 0$ and $(t-1)(s^{\prime}-1)\neq
0$. Thus $\operatorname{im}(t-1)$ is not contained in $W$ and
$\operatorname{ker}(t-1)$ does not contain $U$, so $\overline{t}-1$ is a
nontrivial rank-one map of $U/W$. Thus $\overline{T}$ consists of
transvections of $U/W$. Moreover if $(t,s)$ is an edge of $\Gamma(T)$ then
$(t-1)(s-1)$ also descends to a nontrivial rank-one map of $U/W$, so
$(\overline{t},\overline{s})$ is an edge of $\Gamma(T)$, and conversely it is
clear that if $(\overline{t}-1)(\overline{s}-1)$ is nonzero so must be
$(t-1)(s-1)$. Thus $t\mapsto\overline{t}$ induces a graph homomorphism
$\Gamma(T)\to\Gamma(\overline{T})$ that is surjective on both vertices and
edges.

Suppose $(t_{1},\dots,t_{n})$ is a cycle of $\Gamma(T)$. Then
$w(t_{1},\dots,t_{n})=\operatorname{tr}(\alpha)$ where
$\alpha=(t_{1}-1)\cdots(t_{n}-1)$. Observe that $\alpha$ is a rank-one map
such that $\operatorname{im}(\alpha)\leq U$ and $\alpha(W)=0$. Therefore
$\operatorname{tr}(\alpha)=\operatorname{tr}(\overline{\alpha})$, where
$\overline{\alpha}$ is the image of $\alpha$ in $\operatorname{End}(U/W)$, so
$w(t_{1},\dots,t_{n})=w(\overline{t}_{1},\dots,\overline{t}_{n})$.

Finally, $V(\overline{T})=U/W$ and $V^{*}(\overline{T})^{\perp}=0$. Since
$\Gamma(T)$ is strongly connected, so its homomorphic image
$\Gamma(\overline{T})$. Thus
$\overline{G}=\left\langle{\overline{T}}\right\rangle$ is irreducible by
Proposition 3.2prop:irreducible. ∎

We say $T\subseteq\mathfrak{T}$ is _nondegenerate_ if the natural pairing

$V(T)\times V^{*}(T)\to K$

is nondegenerate. This is equivalent to the presence of a direct sum
decomposition

$V=V(T)\oplus V^{*}(T)^{\perp}=[V,G]\oplus V^{G}.$

We say $T$ is _weakly nondegenerate_ if the natural pairing has either zero
left kernel or zero right kernel. Observe that $T$ is nondegenerate if and
only if it is weakly nondegenerate and $\dim V(T)=\dim V^{*}(T)$.

######  Proposition 4.2.

Suppose $G$ preserves a nondegenerate sesquilinear form $f$. Then $\dim
V(T)=\dim V^{*}(T)$. In particular if $T$ is weakly nondegenerate then it is
nondegenerate.

###### Proof.

For $v\in V$ let $v^{*}\in V^{*}$ be defined by $v^{*}(u)=f(u,v)$. The
transvections in $\operatorname{Aut}(f)$ all have the form $1+\lambda v\otimes
v^{*}$ for some $\lambda\in K$. Since $v\mapsto v^{*}$ is semilinear it
follows that $V^{*}(T)=\\{v^{*}:v\in V(T)\\}$ and $\dim V(T)=\dim V^{*}(T)$. ∎

######  Proposition 4.3.

Assume

  1. (1)

$\Gamma(T)$ is strongly connected,

  2. (2)

$\overline{G}=\operatorname{SL}(U)$,

  3. (3)

$\dim U\geq 4$.

Then $G\cong\operatorname{SL}(U)\ltimes U^{d}$ for some $d\geq 0$ and there is
a basis for $V$ such that

$G=\left\\{\begin{pmatrix}\overline{g}&u&0\\\ 0&I&0\\\
0&0&I\end{pmatrix}:\overline{g}\in\operatorname{SL}(U),u\in U^{d}\right\\}.$

###### Proof.

Choose a basis for $V$ extending a basis for $U$. Since $G$ preserves
$U=[V,G]$ and acts trivially on $V/U$, the elements of $G$ take the form

$\begin{pmatrix}*&*\\\ 0&I\end{pmatrix}.$

The elements of $M=C_{G}(U)$ have the form

$\begin{pmatrix}I&*\\\ 0&I\end{pmatrix},$

and $M$ can be identified with a subspace of $\operatorname{Hom}(V/U,U)\cong
U^{m}$, where $m=\dim(V/U)$. Moreover the conjugation action of $G$ on $M$
corresponds to the natural action of $G$ on $U^{m}$.

Since $\dim U\geq 4>1$ and $\overline{G}=\operatorname{SL}(U)$, $G$ acts
transitively on $U\smallsetminus\\{0\\}$. In particular, $U$ is an irreducible
$kG$-module where $k=\mathbf{F}_{p}$ is the prime subfield of $K$.

Suppose $U_{1}$ is an irreducible $kG$-submodule of $U^{m}$. Then $U_{1}\cong
U$. Let $f:U\to U_{1}$ be an isomorphism. By composing with any of the $m$
coordinate projections $\pi_{i}:U^{m}\to U$ we get a map $\pi_{i}\circ
f\in\operatorname{End}_{kG}(U)$. It is easy to check that
$\operatorname{End}_{kG}(U)=K$ using the fact that each
$\alpha\in\operatorname{End}_{kG}(U)$ must commute with every transvection of
$U$.222Alternatively, by Schur’s lemma, $\operatorname{End}_{kG}(U)$ is a
division algebra containing $K$. If $K$ is finite, Wedderburn’s little theorem
implies that $\operatorname{End}_{kG}(U)$ is a field and therefore
$\operatorname{End}_{kG}(U)=\operatorname{End}_{KG}(U)=K$ since $U$ is an
absolutely irreducible $KG$-module. Therefore there is some $a_{i}\in K$ such
that $\pi_{i}\circ f(u)=a_{i}u$ for all $u\in U$. It follows that
$f(u)=(a_{1}u,\dots,a_{m}u)$ for all $u\in U$. This shows that all irreducible
$kG$-submodules of $U^{m}$ are equivalent up to the natural action of
$\operatorname{GL}_{m}(K)$. By induction on dimension, it follows that every
$kG$-submodule of $U^{m}$ is equivalent to $\\{0\\}^{m-d}\oplus U^{d}$ for
some $d$.

Since $M$ can be identified with a $kG$-submodule of $U^{m}$, it follows from
the previous paragraph that we can choose the basis so that

$M=\left\\{\begin{pmatrix}I&0&u\\\ 0&I&0\\\ 0&0&I\end{pmatrix}:u\in
U^{d}\right\\}$

for some $d\leq m$. Therefore

$G=\left\\{\begin{pmatrix}\overline{g}&f(\overline{g})&u\\\ 0&I&0\\\
0&0&I\end{pmatrix}:\overline{g}\in\operatorname{SL}(U),u\in U^{d}\right\\},$

for some well-defined map $f:\operatorname{SL}(U)\to U^{m-d}$. By direct
calculation, $f$ must be a crossed homomorphism.

By a result of Higman [higman]*Lemma 4, $H^{1}(\operatorname{SL}(U),U)=0$ for
$\dim U\geq 4$ (see also [pollatsek-H^1, cline-parshall-scott]). Therefore
$f(\overline{g})=\overline{g}u-u$ for some $u\in U^{m-d}$, and by conjugating
appropriately we can arrange that $f=0$. ∎

######  Lemma 4.4.

Let $H=\operatorname{SL}(V)\ltimes V^{d}$ and let $h\mapsto\overline{h}$ be
the natural map from $H$ to $\overline{H}=\operatorname{SL}(V)$. Let $X$ be a
generating set for $H$. Then

$\ell_{X}(H)\leq 6^{d}\ell_{\overline{X}}(\overline{H}).$

###### Proof.

Assume without loss of generality $X=X^{-1}$ and $1\in X$. We may also assume
that $\ell_{\overline{X}}(\overline{H})<\infty$. Let $W=V^{d}$ and let $U\cong
V$ be an irreducible submodule of $W$. Let
$H^{*}=H/U\cong\operatorname{SL}(V)\rtimes V^{d-1}$. By induction on $d$,
$L=\ell_{X^{*}}(H^{*})<\infty$. Therefore $X^{L}$ covers $H^{*}$ and
$\overline{H}$ a fortiori. If $X^{L+1}=X^{L}$ then $X^{L}=H$. Otherwise there
is some $x\in X^{L+1}\smallsetminus X^{L}$. Since $X^{L}$ covers $H^{*}$,
there is some $y\in X^{L}$ such that $u=xy^{-1}\in U$, and $u$ is nontrivial
since $x\neq y$. Now since $\overline{H}$ is transitive on
$U\smallsetminus\\{0\\}$ and $X^{L}$ covers $\overline{H}$ we have

$U\smallsetminus\\{0\\}\subseteq u^{X^{L}}\subseteq X^{4L+1}.$

Since $X^{L}$ covers $H^{*}\cong H/U$ it follows that $H\subseteq
X^{5L+1}\subseteq X^{6L}$. Thus $\ell_{X}(H)\leq 6\ell_{X^{*}}(H^{*})$, and
the claimed bound holds by induction. ∎

######  Proposition 4.5.

Assume

  1. (1)

$\Gamma(T)$ is strongly connected,

  2. (2)

$T$ is weakly nondegenerate,

  3. (3)

$\overline{G}=\operatorname{SL}(U/W)$,

  4. (4)

$\min(\dim V(T),\dim V^{*}(T))\geq 4$.

Then

$G\cap\mathfrak{T}=\\{1+v\otimes\phi:v\in V(T),\phi\in V^{*}(T)\\}.$

Moreover $\ell_{T}(G)\leq 6^{d}\ell_{\overline{T}}(\overline{G})$, where

$d=|\dim V(T)-\dim V^{*}(T)|\leq|T|.$

###### Proof.

For $v\in V$ and $\phi\in V^{*}$, let $\langle v,\phi\rangle=\phi(v)$. Then
$\langle,\rangle:V\times V^{*}\to K$ is a perfect pairing and for each
$g\in\operatorname{SL}(V)$ there is a corresponding element
$g^{*}\in\operatorname{SL}(V^{*})$ defined by

$\langle gv,\phi\rangle=\langle v,g^{*}\phi\rangle.$

Moreover $g\mapsto(g^{*})^{-1}$ is isomorphism
$\operatorname{SL}(V)\to\operatorname{SL}(V^{*})$ which exchanges $V(T)$ and
$V^{*}(T)$. To be precise, if $V_{1}=V^{*}$ then $V_{1}^{*}=V$ naturally, and
$T^{*}=\\{(t^{*})^{-1}:t\in T\\}$ is a set of transvections in
$\operatorname{SL}(V_{1})$ such that $V_{1}(T^{*})=V^{*}(T)$ and
$V_{1}^{*}(T^{*})=V(T)$. Therefore, up to replacing $G$ by
$G^{*}=\\{g^{*}:g\in G\\}$, we can assume that $V(T)\cap V^{*}(T)^{\perp}=0$,
i.e., $W=0$. Now the previous proposition applies, so $V=X\oplus V^{G}$ for
some $G$-invariant complement $X\leq V$ to $V^{G}$ (containing $U$) and

$G=\\{g\in\operatorname{SL}(V):(g-1)(X)\leq U,(g-1)(V^{G})=0\\}.$

In particular, if $t=1+v\otimes\phi\in\mathfrak{T}$, then $t\in G$ if and only
if $v\in U=V(G)$ and $\phi(V^{G})=0$, i.e., $\phi\in(V^{G})^{\perp}=V^{*}(T)$.

The last part follows from $G\cong\overline{G}\ltimes U^{d}$ and the previous
lemma. ∎

##  5\. Path shortening and other tricks

The method of this section is inspired by [GHS]*Lemma 4.1 and [H]*Lemma 2.4.

Given a vector $u\in V$ and a transvection $t=1+v\otimes\phi\in\mathfrak{T}$,
let us write $t\to u$ if $\phi(u)\neq 0$. Similarly given $\psi\in V^{*}$ let
us write $\psi\to t$ if $\psi(v)\neq 0$. This notation is compatible with the
corresponding notation for the transvection graph: if $t=1+v\otimes\phi$ and
$s=1+u\otimes\psi$ then

$t\to s\iff t\to u\iff\phi\to s\iff\phi(u)\neq 0.$

Call $T\subseteq\mathfrak{T}$ _dense_ if for every nonzero $v\in V$ and
nonzero $\phi\in V^{*}$ there is some $t\in T$ such that

$\phi\to t\to v.$

Clearly if $T$ is dense then $V(T)=V$, $V^{*}(T)=V^{*}$, and $\Gamma(T)$ is
strongly connected (in fact $\Gamma(T)$ has directed diameter at most $2$), so
$G=\left\langle{T}\right\rangle$ is irreducible by Proposition
3.2prop:irreducible. The following useful proposition is a partial converse.

######  Proposition 5.1.

Let $T\subseteq\mathfrak{T}$ be a symmetric set of transvections such that
$\left\langle{T}\right\rangle$ is irreducible. Then $T^{2n-1}\cap\mathfrak{T}$
is dense.

###### Proof.

Let $v\in V$ and $\phi\in V^{*}$ be both nonzero. By Proposition
3.2prop:irreducible, $V(T)=V$, $V^{*}(T)=V^{*}$, and $\Gamma(T)$ is strongly
connected. It follows that there are transvections $t_{1},\dots,t_{m}\in T$
for some $m\geq 1$ such that

$\phi\to t_{1}\to\cdots\to t_{m}\to v.$

Write $t_{i}=1+v_{i}\otimes\phi_{i}$ for $i=1,\dots,m$. Assume $m$ is minimal
for the existence of such $t_{1},\dots,t_{m}$. If $m=1$ we are done, so assume
$m>1$. By minimality of $m$,

  1. (1)

$\phi\not\to t_{2},\dots,t_{m}$,

  2. (2)

$t_{1},\dots,t_{m-1}\not\to v$,

  3. (3)

$t_{i}\not\to t_{j}$ for $j-i>1$.

In particular $v_{1},\dots,v_{m}$ must be linearly independent, so $m\leq n$.
Now consider

$t^{\prime}=t_{1}\cdots t_{m-1}t_{m}t_{m-1}^{-1}\cdots
t_{1}^{-1}=1+v^{\prime}\otimes\phi^{\prime},$

where

$\displaystyle v^{\prime}$ $\displaystyle=t_{1}\circ\cdots\circ
t_{m-1}(v_{m}),$ $\displaystyle\phi^{\prime}$ $\displaystyle=\phi_{m}\circ
t_{m-1}^{-1}\circ\cdots\circ t_{1}^{-1}.$

Using properties (1) and (3) above, we have

$\displaystyle\phi(v^{\prime})$
$\displaystyle=\phi(1+v_{1}\otimes\phi_{1})\cdots(1+v_{m-1}\otimes\phi_{m-1})(v_{m})$
$\displaystyle=\phi(v_{1})\phi_{1}(v_{2})\cdots\phi_{m-1}(v_{m})\neq 0.$

Similarly, by property (2),

$\displaystyle\phi^{\prime}(v)$
$\displaystyle=\phi_{m}(1-v_{m-1}\otimes\phi_{m-1})\cdots(1-v_{1}\otimes\phi_{1})(v)$
$\displaystyle=\phi_{m}(v)\neq 0.$

Thus $\phi\to t^{\prime}\to v$. Since $t^{\prime}\in
T^{2m-1}\cap\mathfrak{T}$, we are done. ∎

######  Proposition 5.2.

Let $T\subseteq\mathfrak{T}$ be a dense set of transvections. Let
$T_{0}\subseteq T$ be a nonempty subset and assume $\Gamma(T_{0})$ has $k$
strongly connected components. Then there is a set of transvections
$T_{1}\subseteq T$ such that

  1. (1)

$T_{0}\subseteq T_{1}$,

  2. (2)

$|T_{1}|\leq|T_{0}|+k$,

  3. (3)

$\Gamma(T_{1})$ is strongly connected.

If $G=\left\langle{T}\right\rangle$ preserves a symplectic or unitary form
then we can assume (2’) $|T_{1}|\leq|T_{0}|+k-1$.

###### Proof.

Let $t_{1},\dots,t_{k}\in T_{0}$ be representatives for the $k$ strongly
connected components of $\Gamma(T_{0})$. By density of $T$ there are
transvections $t^{\prime}_{1},\dots,t^{\prime}_{k}\in T$ such that

$t_{1}\to t^{\prime}_{1}\to t_{2}\to t^{\prime}_{2}\to\cdots\to
t^{\prime}_{k-1}\to t_{k}\to t^{\prime}_{k}\to t_{1}.$

Let $T_{1}=T_{0}\cup\\{t^{\prime}_{1},\dots,t^{\prime}_{k}\\}$. Then
$|T_{1}|\leq|T_{0}|+k$ and $\Gamma(T_{1})$ is strongly connected.

If $G$ preserves a symplectic or unitary form then all edges are two-way and
we can omit $t^{\prime}_{k}$. ∎

Recall that $T$ is weakly nondegenerate if $V(T)\cap V^{*}(T)^{\perp}=0$ or
$V(T)^{\perp}\cap V^{*}(T)=0$. The _defect_ of $T$ is

$\delta(T)=\min(\dim V(T)\cap V^{*}(T)^{\perp},\dim V(T)^{\perp}\cap
V^{*}(T)).$

######  Proposition 5.3.

Let $T\subseteq\mathfrak{T}$ be a dense set of transvections. Let
$T_{0}\subseteq T$ be a nonempty subset such that $\Gamma(T_{0})$ is strongly
connected. Then there is a set of transvections $T_{1}\subseteq T$ such that

  1. (1)

$T_{0}\subseteq T_{1}$,

  2. (2)

$|T_{1}|\leq|T_{0}|+\delta(T_{0})$,

  3. (3)

$\Gamma(T_{1})$ is strongly connected,

  4. (4)

$T_{1}$ is weakly nondegenerate.

###### Proof.

Consider the pairing $V(T_{0})\times V^{*}(T_{0})\to K$ and assume both the
left and right kernels are nonzero. Assume $0\neq u\in V(T_{0})\cap
V^{*}(T_{0})^{\perp}$ and $0\neq\psi\in V(T_{0})^{\perp}\cap V^{*}(T_{0})$. By
density there is some

$t_{1}=1+v_{1}\otimes\phi_{1}\in T$

such that $\psi\to t_{1}\to u$. Let $T_{1}=T_{0}\cup\\{t_{1}\\}$. Then
$\Gamma(T_{1})$ is again strongly connected. Moreover since $\psi\in
V^{*}(T_{1})$ and $V(T_{1})\cap\psi^{\perp}=V(T_{0})$ we have

$V(T_{1})\cap V^{*}(T_{1})^{\perp}=V(T_{0})\cap
V^{*}(T_{1})^{\perp}=V(T_{0})\cap V^{*}(T_{0})^{\perp}\cap\phi_{1}^{\perp}.$

Since $u\in V(T_{0})\cap V^{*}(T_{0})^{\perp}\smallsetminus\phi_{1}^{\perp}$,
this implies that

$\dim V(T_{1})\cap V^{*}(T_{1})^{\perp}=\dim V(T_{0})\cap
V^{*}(T_{0})^{\perp}-1$

and by a symmetric argument we have

$\dim V(T_{1})^{\perp}\cap V^{*}(T_{1})=\dim V(T_{0})^{\perp}\cap
V^{*}(T_{0})-1.$

Thus $\delta(T_{1})=\delta(T_{0})-1$ and we are done by induction on defect. ∎

##  6\. Certification

The main new idea in the present work is to leverage Theorem
1.4thm:classification using “certificates”. By a _certificate_ for $T$ we mean
a bounded-size subset $T_{0}\subseteq\left\langle{T}\right\rangle$ such that
$\ell_{T}(T_{0})\leq(n\log q)^{O(1)}$ and such that
$G_{0}=\left\langle{T_{0}}\right\rangle$ acts irreducibly on
$V_{0}=V(T_{0})=[V,G_{0}]$ with the same defining field and same type as $G$
itself. We may assume $\dim V_{0}\geq 10$ to avoid pathologies. As a
consequence of Kantor’s classification theorem, it follows in particular that
if $T_{0}\subseteq H\leq G$ and $H$ is irreducible then $H=G$.

Consider the containment diagram shown in Figure 1fig:classification between
the types of irreducible groups generated by transvections with defining field
$\mathbf{F}_{q}$. Here we have ignored the groups of exceptional type. This is
harmless as we can always choose $T_{0}$ so that $\dim V_{0}\geq 10$. Now our
strategy is to consider each of the possibilities above in turn. For example,
if $G$ is not contained in a symplectic group, then we aim to find a subset
$T_{0}$ of bounded size which is also not contained in a symplectic group:
this is actually easy using symplectic cycles. Some of the other types will
give us much more difficulty.

$\operatorname{SL}_{n}(q)$$\operatorname{Sp}_{n}(q)$$\operatorname{SU}_{n}(q_{0})$$\operatorname{O}^{\pm}_{n}(q)$$S_{n+1}$$S_{n+2}$$C_{a}^{n-1}\rtimes
S_{n}$$2\mid n$$q=q_{0}^{2}$$p=2$$q=2$$q=2,4\nmid n$$q=2$$p=2$$a\mid q_{0}+1$,
$p=2$ Figure 1. Containment between types of irreducible groups generated by
transvections with defining field $\mathbf{F}_{q}$

For the rest of the paper we assume $K=\mathbf{F}_{q}$ is a finite field of
characteristic $p$. As in previous sections, $T\subseteq\mathfrak{T}$ and
$G=\left\langle{T}\right\rangle$. We assume $G$ is irreducible. In
consideration of Proposition 5.1prop:density, we assume $T$ is dense.

###  6.1. Unitary and symplectic subgroups

######  Proposition 6.1 (cf. [GHS]*Lemma 4.8).

If $G$ does not preserve a nondegenerate symplectic (respectively, unitary)
form then $\Gamma(T)$ contains a non-symplectic (respectively, non-unitary)
cycle of length at most $5$.

###### Proof.

This is immediate from Proposition 3.4prop:invariant-form, since $\Gamma(T)$
has directed diameter at most $2$. ∎

_Warning_ : The definition of unitary cycle depends on the field. In
particular even if $T_{0}\subseteq T$ contains a cycle which is non-unitary
with respect to $\mathbf{F}_{q}$, it is still quite possible that
$G_{0}=\left\langle{T_{0}}\right\rangle$ is a unitary group with respect to
the subfield $L(T_{0})<L(T)$.

###  6.2. Symmetric-type subgroups

Let us review the construction of the irreducible linear groups of symmetric
type. Let $G=S_{m}$ and consider its standard permutation representation
$K^{m}$, where $K=\mathbf{F}_{2}$. The unique proper nontrivial submodules are
$\ell=(K^{m})^{G}=\left\langle{e}\right\rangle$, where $e=(1,\dots,1)$, and
$H=[K^{m},G]=\\{x:x_{1}+\cdots+x_{m}=0\\}$. If $m$ is odd, $W=\ell\oplus H$.
If $m$ is even, $\ell\leq H$. Let $V=H/\ell\cap H$ and $n=\dim V=m-\gcd(m,2)$.
The natural image of $G$ in $\operatorname{SL}(V)$ is a _group of symmetric
type_. We call $G$ _odd symmetric type_ if $m$ is odd and _even symmetric
type_ if $m$ is even.

The unique nonzero $G$-invariant alternating bilinear form on $K^{m}$ is given
by $f(x,y)=\sum_{i\neq j}x_{i}y_{j}$, and one checks $H^{\perp}=\ell$, so $f$
induces a $G$-invariant symplectic form on $V$. Thus $G$ is conjugate to a
subgroup of $\operatorname{Sp}_{n}(2)$. One may also check that $G$ preserves
a quadratic form on $V$ if and only if $m\not\equiv 2\pmod{4}$.

For small $m$ there are various coincidences with groups of classical type:

$\displaystyle S_{3}\cong S_{4}/V\cong\operatorname{SL}_{2}(2),$
$\displaystyle
S_{5}\cong\operatorname{O}_{4}^{-}(2)\cong\operatorname{SL}_{2}(4):2,$
$\displaystyle S_{6}\cong\operatorname{Sp}_{4}(2),$ $\displaystyle
S_{8}\cong\operatorname{O}_{6}^{+}(2)\cong\operatorname{SL}_{4}(2):2.$

It is therefore harmless to assume $m\geq 7$, $m\neq 8$. Unless
$m\in\\{2,4\\}$, an element of $G\cong S_{m}$ acts on $\\{1,\dots,m\\}$ as a
transposition if and only if it acts on $V$ as a transvection.

######  Lemma 6.2.

Let $G=S_{m}$ and let
$\rho:G\to\operatorname{SL}(V)\cong\operatorname{SL}_{n}(2)$ be the
representation defined above, where $n=m-\gcd(m,2)$. Assume $m\geq 5$. An
element $g\in G$ is a transposition if and only if $\rho(g)$ is transvection.

###### Proof.

Let $e_{1},\dots,e_{m}$ be the standard basis of $K^{m}$. Define
$e_{i}^{*}\in(K^{m})^{*}$ by $e_{i}^{*}(e_{j})=\delta_{ij}$. Let $g=(i,j)\in
G$. Then $g$ acts as $1+(e_{i}+e_{j})\otimes(e_{i}^{*}+e_{j}^{*})$ on $K^{m}$,
which descends to a transvection on $V$, so $\rho(g)$ is a transvection.
Conversely, suppose $\rho(g)$ is a transvection. Then $g$ is an involution, so
$g$ has cycle type $2^{k}$ for some $k$, say $g=(1,k+1)(2,k+2)\cdots(k,2k)$
without loss of generality. Then $g$ acts as
$1+\sum_{i=1}^{k}(e_{i}+e_{k+i})\otimes(e_{i}^{*}+e_{k+i}^{*})$ on $K^{m}$.
The subspace $(g-1)(H)$ consists of all vectors $x\in K^{m}$ such that
$x_{i}=x_{k+i}$ for $1\leq i\leq k$ and such that $x_{i}=0$ for $i>2k$, and
moreover such that $x_{1}+\cdots+x_{k}=0$ if $k=m/2$, so $\dim(g-1)(H)=k$ if
$k<m/2$ and $\dim(g-1)(H)=k-1$ if $k=m/2$. Also $(g-1)(H)\cap\ell=0$ unless
$k=m/2$ and $k$ is even. Thus $(g-1)|V$ has rank $k$ unless $k=m/2$, in which
case it has rank $k-1$ if $k$ is odd and $k-2$ if $k$ is even. Therefore in
order that $g$ acts a transvection on $V$ it is necessary that $k=1$. ∎

In the rest of this subsection, we consider the following question. Let
$K=\mathbf{F}_{2}$ and $V=K^{n}$, where $n$ is even. Given
$T\subseteq\mathfrak{T}\cap\operatorname{Sp}_{n}(2)$ such that
$G=\left\langle{T}\right\rangle$ is irreducible, how can we certify that $G$
is not contained in a group of symmetric type?

######  Lemma 6.3.

The following are equivalent:

  1. (1)

$G$ has odd symmetric type,

  2. (2)

there is a $G$-invariant spanning set $B\subseteq V$ of cardinality $n+1$.

Moreover $B$ is uniquely determined by $G$.

###### Proof.

_(1) $\implies$ (2):_ If $G=S_{n+1}$ acting on the hyperplane
$H\leq\mathbf{F}_{2}^{n+1}$ then $B=\left\\{\sum_{i\neq
j}e_{i}:j=1,\dots,n+1\right\\}$ is a $G$-invariant spanning set of cardinality
$n+1$.

_(2) $\implies$ (1):_ Let $B=\\{b_{1},\dots,b_{n+1}\\}$. Then
$b_{1}+\cdots+b_{n+1}\in V^{G}=0$, since $G$ is irreducible. Since $|B|=n+1$,
this is the unique nontrivial linear relation among the elements of $B$. In
particular $G$ must be transitive on $B$, for if $B_{0}\subseteq B$ is
$G$-invariant then $\sum_{b\in B_{0}}b=0$ by the same argument.

Let $W=V\oplus\ell$ where $\ell=\\{0,e\\}$ is a copy of the trivial
$1$-dimensional $G$-module $K^{1}$. Let $b^{\prime}_{i}=b_{i}+e$ for $1\leq
i\leq n+1$ and let $\Omega=\\{b^{\prime}_{1},\dots,b^{\prime}_{n+1}\\}$. Then
$\Omega$ is $G$-invariant and

$b^{\prime}_{1}+\cdots+b^{\prime}_{n+1}=b_{1}+\cdots+b_{n+1}+(n+1)e=e.$

It follows that $\Omega$ spans $W$, so $\Omega$ is a $G$-invariant basis of
$W$. Thus we may identify $W$ with $K^{\Omega}$, $V$ with the hyperplane
$H\leq K^{\Omega}$, and $G$ with a subgroup of $\operatorname{Sym}(\Omega)$.
Hence $G$ is a transitive subgroup of $\operatorname{Sym}(\Omega)$ generated
by transpositions (by Lemma 6.2lem:transpositions-transvections), so
$G=\operatorname{Sym}(\Omega)$ by Proposition 3.1prop:transposition-graph.

Now we argue that $B$ is uniquely determined. Assume $G$ has odd symmetric
type and $B,B^{\prime}\subseteq\mathbf{F}_{2}^{n}$ are two $G$-invariant
spanning sets of cardinality $n+1$. The above argument shows that
$G|B=\operatorname{Sym}(B)$ and $G|B^{\prime}=\operatorname{Sym}(B^{\prime})$.
Since $\operatorname{Aut}(S_{m})=S_{m}$ for $m\neq 2,6$ and $|B|$ is odd,
there is a $G$-equivariant bijection $f:B\to B^{\prime}$. Let $\tau\in G$ be a
transposition, say transposing $b,b^{\prime}\in B$. Then
$\operatorname{im}(\tau-1)=\left\langle{b+b^{\prime}}\right\rangle$. Also
$\tau$ transposes $f(b),f(b^{\prime})$, so
$\operatorname{im}(\tau-1)=\left\langle{f(b)+f(b^{\prime})}\right\rangle$. It
follows that $b+b^{\prime}=f(b)+f(b^{\prime})$ for any two $b,b^{\prime}\in
B$. Since $|B|$ is odd, we deduce that

$b=\sum_{b^{\prime}}(b+b^{\prime})=\sum_{b^{\prime}}(f(b)+f(b^{\prime}))=f(b)$

for all $b\in B$. Thus $B=B^{\prime}$. ∎

The main result of this subsection is the following proposition.

######  Proposition 6.4.

Assume $T\subseteq\mathfrak{T}\cap\operatorname{Sp}_{n}(2)$ is dense and
$n\geq 2000$. The following are equivalent:

  1. (1)

$G$ has symmetric type;

  2. (2)

for every subset $T_{0}\subseteq T$ of cardinality $|T_{0}|\leq 1000$ such
that $G_{0}=\left\langle{T_{0}}\right\rangle$ acts irreducibly on
$V_{0}=[V,G_{0}]$, the restriction $G_{0}|V_{0}$ has odd symmetric type.

###### Proof.

_(1) $\implies$ (2):_ Let $T_{0}\subseteq T$ be a set of cardinality
$|T_{0}|\leq 1000$ such that $G_{0}=\left\langle{T_{0}}\right\rangle$ acts
irreducibly on $V_{0}=[V,G_{0}]$. We can identify $G$ with $S_{m}$ for
$m\in\\{n+1,n+2\\}$ and $V$ with the section $H/(\ell\cap H)$ of the standard
permutation module $K^{m}$. Then $T\subseteq\operatorname{Sym}(\Omega)$ is a
set of transpositions. Let $\Gamma_{0}=\Gamma(T_{0})$ be the transposition
graph defined by $T_{0}$. Then $G_{0}=\left\langle{T_{0}}\right\rangle$ is the
direct product of the full symmetric groups on each component of $\Gamma_{0}$,
and $V_{0}$ is the image in $V$ of the space $W$ of all $x\in K^{m}$ such that
$\sum_{i\in C}x_{i}=0$ for each component $C$ of $\Gamma_{0}$. If $e\in W$
then every component of $\Gamma_{0}$ has even cardinality and
$|T_{0}|\geq(n+2)/2>1000$, contrary to hypothesis. Therefore $W\cap\ell=0$ and
$V_{0}\cong W$ as $G_{0}$-modules. Since $G_{0}|V_{0}$ is irreducible, it must
be that $\Gamma_{0}$ has only one non-singleton component, and it must have
odd order. Thus $G_{0}|V_{0}$ has odd symmetric type.

_(2) $\implies$ (1):_ Call $T_{0}\subseteq T$ _admissible_ if
$G_{0}=\left\langle{T_{0}}\right\rangle$ acts irreducibly on
$V_{0}=[V,G_{0}]$. Let $\mathcal{A}_{t}$ be the collection of admissible
subsets $T_{0}\subseteq T$ of cardinality $|T_{0}|\leq t$. By hypothesis,
$G_{0}|V_{0}$ has odd symmetric type for every $T_{0}\in\mathcal{A}_{1000}$.
In this case by Lemma 6.3lem:odd-sym-type there is a unique $G_{0}$-invariant
spanning set $B_{0}\subseteq V_{0}$ of cardinality $\dim V_{0}+1$. Define

$\Delta(T_{0})=\\{b+b^{\prime}:b,b^{\prime}\in B_{0},b\neq
b^{\prime}\\}\qquad(T_{0}\in\mathcal{A}_{1000}).$

Throughout this proof we will refer to the subgroup $G_{0}\leq G$, the
subspace $V_{0}\leq V$, and the subset $B_{0}\subseteq V_{0}$ constructed from
admissible sets $T_{0}$ in this way.

Suppose $T_{0}\subseteq T_{1}$ where $T_{0},T_{1}\in\mathcal{A}_{1000}$.
Correspondingly define $G_{i}$, $V_{i}$, $B_{i}$ for $i=0,1$. Then $G_{0}\leq
G_{1}$, $V_{0}\leq V_{1}$, and from our analysis of the implication _(1)
$\implies$ (2)_ we know that $B_{0}$ is related to $B_{1}$ in the following
rigid way: there is a $G_{0}$-equivariant injection $\iota:B_{0}\to B_{1}$
such that

$b=\iota(b)+\sum_{b^{\prime}\in
B_{1}\smallsetminus\iota(B_{0})}b^{\prime}\qquad\qquad(b\in B_{0}).$

Also $G_{0}$ acts trivially on $B_{1}\smallsetminus\iota(B_{0})$. In
particular $b+b^{\prime}=\iota(b)+\iota(b^{\prime})$ for $b,b^{\prime}\in
B_{0}$, so $\Delta(T_{0})\subseteq\Delta(T_{1})$.

Define

$\Delta=\bigcup_{T_{0}\in\mathcal{A}_{400}}\Delta(T_{0}).$

We claim that, for every $v\in\Delta$, there is in fact some
$T_{1}\in\mathcal{A}_{6}$ such that $v\in\Delta(T_{1})$. Suppose
$v\in\Delta(T_{0})$ for $T_{0}\in\mathcal{A}_{400}$. Then
$v=b_{0}+b_{0}^{\prime}$ for some $b_{0},b_{0}^{\prime}\in B_{0}$. By
consideration of the transposition graph defined by $T_{0}\subseteq
G_{0}\cong\operatorname{Sym}(B_{0})$, there are $t,t^{\prime}\in T_{0}$ that
move $b_{0},b_{0}^{\prime}$, respectively. By Proposition 5.3prop:winkle,
$\\{t,t^{\prime}\\}$ is contained in some $T_{1}\in\mathcal{A}_{6}$, and
$T_{0}\cup T_{1}$ is contained in some $T_{2}\in\mathcal{A}_{808}$ (note that
$|T_{0}\cup T_{1}|\leq 404$ and $\Gamma(T_{0}\cup T_{1})$ is strongly
connected). Consider the corresponding maps $\iota_{0}:B_{0}\to B_{2}$ and
$\iota_{1}:B_{1}\to B_{2}$. Since $t$ acts as a transposition on each of
$B_{0},B_{1},B_{2}$, it must be that $\iota_{0}(b_{0})=b_{2}=\iota_{1}(b_{1})$
for some $b_{2}\in B_{2}$ and $b_{1}\in B_{1}$, and likewise
$\iota_{0}(b^{\prime}_{0})=b^{\prime}_{2}=\iota_{1}(b^{\prime}_{1})$ for some
$b^{\prime}_{2}\in B_{2}$ and $b^{\prime}_{1}\in B_{1}$, whence

$v=b_{0}+b^{\prime}_{0}=b_{2}+b_{2}^{\prime}=b_{1}+b_{1}^{\prime}\in\Delta(T_{1}).$

This proves our claim.

In particular it follows that $\Delta$ is $G$-invariant. Indeed, it suffices
to prove that if $v\in\Delta$ and $t\in T$ then $t(v)\in\Delta$. By the
previous paragraph, $v\in\Delta(T_{0})$ for some $T_{0}\in\mathcal{A}_{6}$. By
Propositions 5.2 and 5.3prop:connect-up,prop:winkle, $T_{0}\cup\\{t\\}$ is
contained in some $T_{1}\in\mathcal{A}_{16}$. Since $\Delta(T_{1})$ is
$G_{1}$-invariant and $t\in G_{1}$, $t(v)\in\Delta(T_{1})\subseteq\Delta$.

Similarly, $G$ is transitive on $\Delta$. Consider $v,v^{\prime}\in\Delta$.
Then $v\in\Delta(T_{0})$ and $v^{\prime}\in\Delta(T_{0}^{\prime})$ for
$T_{0},T_{0}^{\prime}\in\mathcal{A}_{6}$. By Propositions 5.2 and
5.3prop:connect-up,prop:winkle, $T_{0}\cup T_{0}^{\prime}$ is contained in
some $T_{1}\in\mathcal{A}_{26}$. We have
$v,v^{\prime}\in\Delta(T_{0})\cup\Delta(T_{0}^{\prime})\subseteq\Delta(T_{1})$.
Since $G_{1}=\left\langle{T_{1}}\right\rangle\cong\operatorname{Sym}(B_{1})$
is transitive on $\Delta(T_{1})$, it follows that some element of $G_{1}$ maps
$v$ to $v^{\prime}$, and $G_{1}\leq G$.

Next we define a symmetric relation $E$ on $\Delta$ by

$E=\\{(u,v)\in\Delta^{2}:u+v\in\Delta\\}.$

Plainly $E$ is $G$-invariant, so $G$ acts on the graph $(\Delta,E)$ by
automorphisms. Moreover we can describe the relation $E$ another way as
follows. Suppose $(u,v)\in\Delta^{2}$ and suppose $u,v\in\Delta(T_{0})$ for
some $T_{0}\in\mathcal{A}_{400}$. Then $u=b_{1}+b_{2}$ and $v=b_{3}+b_{4}$ for
some $b_{1},b_{2},b_{3},b_{4}\in B_{0}$. We claim that $(u,v)\in E$ if and
only if $|\\{b_{1},b_{2}\\}\cap\\{b_{3},b_{4}\\}|=1$. Indeed, if say
$b_{1}=b_{3}$ but $b_{2}\neq b_{4}$ then
$u+v=b_{2}+b_{4}\in\Delta(T_{0})\subseteq\Delta$. Conversely, suppose
$w=u+v\in\Delta$. Then $w\in\Delta(T_{1})$ for some $T_{1}\in\mathcal{A}_{6}$.
By Propositions 5.2 and 5.3prop:connect-up,prop:winkle there is a set
$T_{2}\in\mathcal{A}_{814}$ containing $T_{0}\cup T_{1}$. Since
$u,v,w\in\Delta(T_{0})\cup\Delta(T_{1})\subseteq\Delta(T_{2})$, each of
$u,v,w$ is the sum of two distinct elements of $B_{2}$. Moreover the
expressions for $u$ and $v$ are $u=\iota(b_{1})+\iota(b_{2})$ and
$v=\iota(b_{3})+\iota(b_{4})$, where $\iota:B_{0}\to B_{2}$ is the usual map.
If $b_{1},b_{2},b_{3},b_{4}$ are all distinct then
$w=\iota(b_{1})+\iota(b_{2})+\iota(b_{3})+\iota(b_{4})$ is not the sum of two
elements of $B_{2}$, since the unique nontrivial linear relation among the
elements of $B_{2}$ is $\sum_{b\in B_{2}}b=0$ and $|B_{2}|$ is odd. Therefore
$|\\{b_{1},b_{2}\\}\cap\\{b_{3},b_{4}\\}|=1$, as claimed.

Let $\Omega$ be the set of maximal cliques $C$ of $(\Delta,E)$ of cardinality
$|C|>3$, and note that $\Omega$ inherits a $G$-action from $(\Delta,E)$.

We claim that each clique $C\in\Omega$ is determined by any two of its
elements, i.e., $|C\cap C^{\prime}|\leq 1$ for distinct
$C,C^{\prime}\in\Omega$. Suppose $C,C^{\prime}\in\Omega$ share two vertices
$v_{1},v_{2}\in\Delta$. We will show that $C\cup C^{\prime}$ is a clique,
whence $C=C^{\prime}=C\cup C^{\prime}$ by maximality. Let $v_{3},v_{4}\in C$
and $v_{3}^{\prime},v^{\prime}_{4}\in C^{\prime}$ be distinct from
$v_{1},v_{2}$. By Propositions 5.2 and 5.3prop:connect-up,prop:winkle, there
is some $T_{0}\in\mathcal{A}_{82}$ such that
$v_{1},v_{2},v_{3},v_{4},v_{3}^{\prime},v_{4}^{\prime}\in\Delta(T_{0})$. By
our alternative characterization of $E$, each $v_{i}$ and $v^{\prime}_{i}$
corresponds to a $2$-subset of $B_{0}$ in such a way that adjacent vertices
correspond to overlapping subsets. Since $\\{v_{1},v_{2},v_{3},v_{4}\\}$ is a
clique, we must have $v_{i}=b_{0}+b_{i}$ for $i=1,2,3,4$ for some
$b_{0},b_{1},b_{2},b_{3},b_{4}\in B_{0}$, and similarly we must have
$v^{\prime}_{3}=b_{0}+b^{\prime}_{3}$ and
$b^{\prime}_{4}=b_{0}+b^{\prime}_{4}$. Thus
$v_{3}+v^{\prime}_{3}=b_{3}+b^{\prime}_{3}\in\Delta\cup\\{0\\}$, and since
$v_{3}$ and $v^{\prime}_{3}$ were arbitrary this implies that $C\cup
C^{\prime}$ is a clique, as claimed.

In fact we claim that $|C\cap C^{\prime}|=1$ for any two distinct cliques
$C,C^{\prime}\in\Omega$. Let $v_{1},v_{2},v_{3},v_{4}\in C$ be distinct and
let $v^{\prime}_{1},v^{\prime}_{2},v^{\prime}_{3},v^{\prime}_{4}\in
C^{\prime}$ be distinct. By maximality and distinctness of $C$ and
$C^{\prime}$, we may assume that $v_{1}\neq v^{\prime}_{1}$ and
$(v_{1},v^{\prime}_{1})\notin E$. By the usual arguments,
$v_{1},v_{2},v_{3},v_{4},v^{\prime}_{1},v^{\prime}_{2},v^{\prime}_{3},v^{\prime}_{4}\in\Delta(T_{0})$
for some $T_{0}\in\mathcal{A}_{110}$. As above, $v_{1},v_{2},v_{3},v_{4}$
correspond to $2$-subsets of $B_{0}$ overlapping in pairs, so we must have
$v_{i}=b_{0}+b_{i}$ for $i=1,2,3,4$ and some $b_{0},b_{1},b_{2},b_{3},b_{4}\in
B_{0}$, and similarly $v^{\prime}_{i}=b^{\prime}_{0}+b^{\prime}_{i}$ for
$i=1,2,3,4$ for some
$b^{\prime}_{0},b^{\prime}_{1},b^{\prime}_{2},b^{\prime}_{3},b^{\prime}_{4}\in
B_{0}$. Let $w=b_{0}+b^{\prime}_{0}$, and observe that $w\neq 0$ since
$v_{1}\neq v^{\prime}_{1}$ and $(v_{1},v^{\prime}_{1})\notin E$. Then
$\\{v_{1},v_{2},v_{3},v_{4},w\\}$ is a clique of cardinality at least $4$
containing $v_{1},v_{2}$, so it must be contained in $C$. This shows $w\in C$
and symmetrically $w\in C^{\prime}$, so $w\in C\cap C^{\prime}$.

We make one further observation. Let $C,C^{\prime},C^{\prime\prime}\in\Omega$
be distinct cliques. Let $w\in C\cap C^{\prime}$ and $w^{\prime}\in
C^{\prime}\cap C^{\prime\prime}$. Then

$w+w^{\prime}\in C\cap C^{\prime\prime}.$ (6.1)

Indeed, let $v_{i}\in C,v^{\prime}_{i}\in C^{\prime},v^{\prime\prime}_{i}\in
C^{\prime\prime}$ for $i=1,2,3,4$ as above. Find $T_{0}\in\mathcal{A}_{166}$
such that $v_{i},v^{\prime}_{i},v^{\prime\prime}_{i}\in\Delta(T_{0})$ for
$i=1,2,3,4$. Then we must have representations of the form
$v_{i}=b_{0}+b_{i},v^{\prime}_{i}=b^{\prime}_{0}+b^{\prime}_{i},v^{\prime\prime}_{i}=b^{\prime\prime}_{0}+b^{\prime\prime}_{i}$,
and $w=b_{0}+b^{\prime}_{0}$,
$w^{\prime}=b^{\prime}_{0}+b^{\prime\prime}_{0}$, and
$w^{\prime\prime}=b_{0}+b^{\prime\prime}_{0}$.

Finally, we claim that $G|\Omega=\operatorname{Sym}(\Omega)$. It suffices to
prove that for any two distinct $C,C^{\prime}\in\Omega$, there is an element
of $G$ transposing $C$ and $C^{\prime}$ and fixing every other element of
$\Omega$. Exactly as above let $v_{1},v_{2},v_{3},v_{4}\in C$ be distinct, let
$v^{\prime}_{1},v^{\prime}_{2},v^{\prime}_{3},v^{\prime}_{4}\in C^{\prime}$ be
distinct, and find $T_{0}\in\mathcal{A}_{110}$ such that
$v_{i},v^{\prime}_{i}\in\Delta(T_{0})$ for $i=1,2,3,4$. We have
$v_{i}=b_{0}+b_{i}$ and $v^{\prime}_{i}=b^{\prime}_{0}+b^{\prime}_{i}$
($i=1,2,3,4$) for some $b_{i},b^{\prime}_{i}\in B_{0}$ ($i=0,1,2,3,4$). Since
$G_{0}\cong\operatorname{Sym}(B_{0})$, there is some $t\in G_{0}$ transposing
$b_{0}$ and $b^{\prime}_{0}$ and fixing every other element of $B_{0}$.
Observe that
$\\{v_{1},v_{2},v_{3},v_{4},t(v^{\prime}_{1}),t(v^{\prime}_{2}),t(v^{\prime}_{3}),t(v^{\prime}_{4})\\}$
is a clique. Since $C$ is the unique maximal clique containing
$v_{1},v_{2},v_{3},v_{4}$ and $t(C^{\prime})$ is the unique maximal clique
containing $v^{\prime}_{1},v^{\prime}_{2},v^{\prime}_{3},v^{\prime}_{4}$, it
follows that $t(C^{\prime})=C$, and similarly $t(C)=C^{\prime}$. Now consider
any other $C^{\prime\prime}\in\Omega$ and let
$v^{\prime\prime}_{1},v^{\prime\prime}_{2},v^{\prime\prime}_{3},v^{\prime\prime}_{4}\in
C^{\prime\prime}$. We can find $T_{1}\in\mathcal{A}_{276}$ containing $T_{0}$
such that
$v^{\prime\prime}_{1},v^{\prime\prime}_{2},v^{\prime\prime}_{3},v^{\prime\prime}_{4}\in\Delta(T_{1})$,
and as above we must have
$v^{\prime\prime}_{i}=b^{\prime\prime}_{0}+b^{\prime\prime}_{i}$ ($i=1,2,3,4$)
for some $b^{\prime\prime}_{i}\in B_{1}$ ($i=0,1,2,3,4$). If say
$b^{\prime\prime}_{0}=\iota(b_{0})$ then
$\\{v_{1},v_{2},v^{\prime\prime}_{1},v^{\prime\prime}_{2}\\}$ is a clique,
which implies $C^{\prime\prime}=C$. Likewise
$b^{\prime\prime}_{0}=\iota(b^{\prime}_{0})$ implies
$C^{\prime\prime}=C^{\prime}$. Otherwise $b^{\prime\prime}_{0}$ is fixed by
$t$, so
$\\{v^{\prime\prime}_{1},v^{\prime\prime}_{2},t(v^{\prime\prime}_{1}),t(v^{\prime\prime}_{2})\\}$
is a clique, which implies $C^{\prime\prime}=t(C^{\prime\prime})$, and this is
what we wanted to prove.

At last we can complete the proof. Consider the $G$-space $K^{\Omega}$ and let
$H\leq K^{\Omega}$ be the hyperplane $\\{x\in
K^{\Omega}:\sum_{C\in\Omega}x_{C}=0\\}$. Fix any $C_{0}\in\Omega$ and observe
that $\\{e_{C_{0}}+e_{C}:C\neq C_{0}\\}$ is a basis of $H$. Define $f:H\to V$
by sending $e_{C_{0}}+e_{C}$ to the unique element of $C_{0}\cap C$ (recalling
that the elements of $\Omega$ are by definition cliques of $(\Delta,E$)) and
linearly extending to $H$. It follows from (6.1) that $f$ sends
$e_{C}+e_{C^{\prime}}$ to the unique element of $C\cap C^{\prime}$ for all
$C,C^{\prime}\in\Omega$, $C\neq C^{\prime}$. Hence $f$ is a nonzero $G$-module
homomorphism, and it must be surjective since $V$ is irreducible. Thus $G$ has
symmetric type, as claimed. ∎

######  Remark 6.5.

In the above proof, it follows a posteriori that $|\Omega|\in\\{n+1,n+2\\}$,
and $G$ has odd type or even type according to these two cases.

###  6.3. Monomial subgroups

Let $K=\mathbf{F}_{q}$ be a finite field of characteristic $2$ and let $a$ be
a divisor of $q-1$. Let $M_{n}(a)$ be the subgroup of
$\operatorname{SL}_{n}(q)$ consisting of those elements which are represented
in the standard basis by monomial matrices with all nonzero entries being
$a$th roots of unity. Then $M_{n}(a)\cong C_{a}^{n-1}\rtimes S_{n}$ and
$M_{n}(a)$ is a subgroup of $\operatorname{SL}_{n}(q)$ generated by
transvections, irreducible for $a>1$. The transvections in $M_{n}(a)$ are the
elements represented as

$\begin{pmatrix}0&x^{-1}&0\\\ x&0&0\\\ 0&0&I_{n-2}\end{pmatrix}$

up to permuting axes.

In general if $G\leq\operatorname{GL}(V)$, a _$G$ -invariant monomial
structure_ on $V$ is a set of lines $L=\\{Kb_{1},\dots,Kb_{n}\\}$ permuted by
$G$ such that $b_{1},\dots,b_{n}$ is a basis for $V$.

######  Lemma 6.6.

If $a>1$ there is a unique $M_{n}(a)$-invariant monomial structure on
$V=K^{n}$.

###### Proof.

First observe that if $N\trianglelefteq C_{a}^{n-1}\rtimes S_{n}$ and $N$ is
not contained in $C_{a}^{n-1}$ then $N$ contains $C_{a}^{n-1}$. Indeed, $N$
contains some element with nontrivial image $\pi$ in $S_{n}$, so $N$ contains
$[C_{a}^{n-1},\pi]$. Now it follows by a short argument that $N$ must contain
all of $C_{a}^{n-1}$. In particular if $N$ is normal and abelian then $N\leq
C_{a}^{n-1}$.

Now let $G=M_{n}(a)\cong C_{a}^{n-1}\rtimes S_{n}$. The fact that
$\\{Ke_{1},\dots,Ke_{n}\\}$ is a $G$-invariant monomial structure is obvious
from the definition of $G$. Suppose $L=\\{Kb_{1},\dots,Kb_{n}\\}$ is another
$G$-invariant monomial structure. The kernel $C_{G}(L)$ of the action of $G$
on $L$ is abelian and normal, so by the above argument it must be contained in
the diagonal subgroup $D\cong C_{a}^{n-1}$ of $G$. Moreover $G/C_{G}(L)$ is
isomorphic to a subgroup of $\operatorname{Sym}(L)\cong S_{n}$; it follows
that $C_{G}(L)=D$. Hence $b_{1},\dots,b_{n}$ are joint eigenvectors of $D$.
However it is straightforward to check that the only joint eigenvectors of $D$
are the scalar multiples of $e_{1},\dots,e_{n}$, so
$\\{Kb_{1},\dots,Kb_{n}\\}=\\{Ke_{1},\dots,Ke_{n}\\}$. ∎

Note that $M_{n}(a)$ does _not_ preserve a symplectic form on $V$ if $a>1$.
Indeed, the only bilinear forms invariant on the diagonal subgroup of
$M_{n}(a)$ are those proportional to $\sum_{i=1}^{n}x_{i}y_{i}$, and the only
such form that is alternating is the zero form. By similar reasoning
$M_{n}(a)$ preserves a unitary form if and only if $a\mid q+1$.

######  Proposition 6.7.

Let $T\subseteq\mathfrak{T}$ be a dense set of transvections in
$\operatorname{SL}_{n}(q)$. Assume that $G$ does not preserve a symplectic
form. Then the following are equivalent:

  1. (1)

$G$ has monomial type;

  2. (2)

for every subset $T_{0}\subseteq T$ of cardinality $|T_{0}|\leq 1000$,

    1. (1)

if $T_{0}$ is weakly nondegenerate then it is nondegenerate, and

    2. (2)

if $G_{0}=\left\langle{T_{0}}\right\rangle$ acts irreducibly on
$V_{0}=[V,G_{0}]$ then $G_{0}|V_{0}$ has monomial type or odd symmetric type.

###### Proof.

_(1) $\implies$ (2):_ Assume $G=M_{n}(a)\leq\operatorname{SL}_{n}(q)$ and
recall $M_{n}(a)\cong C_{a}^{n-1}\rtimes S_{n}$. Let $T_{0}\subseteq T$ be a
subset (of any cardinality). Observe that the image of $T_{0}$ under the
natural map $M_{n}(a)\to S_{n}$ is a set of transpositions. Let $\Gamma_{0}$
be the corresponding transposition graph. Then by Proposition
3.1prop:transposition-graph the image of $G_{0}$ in $S_{n}$ is the direct
product of the full symmetric groups on each component $C$ of $\Gamma_{0}$.
The group $G_{0}$ itself is the direct product of monomial groups $M_{d}(b)$
for $b\geq 1$, say $G_{0}=\prod_{i=1}^{k}M_{d_{i}}(b_{i})$, where $\sum
d_{i}=n$, $d_{i}\geq 1$, and we take $b_{i}=1$ if $d_{i}=1$. Correspondingly
$[V,G_{0}]$ is the direct sum of subspaces $U_{i}\leq K^{d_{i}}$, of
codimension $1$ if $b_{i}=1$ and codimension zero if $b_{i}>1$, while
$V^{G_{0}}$ is the direct sum of subspaces $W_{i}\cong K$ if $b_{i}=1$ and
$W_{i}=0$ if $b_{i}>1$. Therefore $\dim V(T_{0})=\dim[V,G_{0}]=n-\ell$ where
$\ell$ is the number of $b_{i}=1$ and also $\dim V^{*}(T_{0})=n-\dim
V^{G_{0}}=n-\ell$. Therefore $\dim V(T_{0})=\dim V^{*}(T_{0})$, so weak
nondegeneracy implies nondegeneracy.

Now assume $G_{0}|V_{0}$ is irreducible. Since
$V_{0}=\bigoplus_{i:d_{i}>1}U_{i}$ and the $U_{i}$ are $G_{0}$-invariant,
there must be exactly one $d_{i}>1$, say $d_{1}>1$ (i.e., $\Gamma_{0}$ is
connected apart from isolated vertices). Moreover $G_{0}|V_{0}$ is monomial
type or symmetric type $1$ according to whether $b_{1}>1$ or $b_{1}=1$, and in
the latter case $d_{1}$ must be odd.

_(2) $\implies$ (1):_ Since $G$ does not preserve a symplectic form, by
Proposition 6.1prop:unitary-symplectic-certificate there is a set $T_{0}$ of
cardinality $|T_{0}|\leq 5$ inducing a non-symplectic cycle. Let
$\mathcal{A}_{t}$ be the set of subsets $T_{1}\subseteq T$ of cardinality
$|T_{1}|\leq t$ containing $T_{0}$ such that $\Gamma(T_{1})$ is strongly
connected and $T_{1}$ is weakly nondegenerate. By hypothesis, every
$T_{1}\in\mathcal{A}_{1000}$ is nondegenerate. Thus
$G_{1}=\left\langle{T_{1}}\right\rangle$ acts irreducibly on $V_{1}=[V,G_{1}]$
and we have a direct sum decomposition $V=V_{1}\oplus V^{G_{1}}$. Moreover,
since $T_{0}\subseteq G_{1}$, $G_{1}$ does not have symmetric type, so it must
have monomial type. By the previous lemma, there is a unique $G_{1}$-invariant
monomial structure $L_{1}$ on $V_{1}$. Let $L$ be the union of the sets
$L_{1}$ over all $T_{1}\in\mathcal{A}_{100}$. Note that $L\neq\emptyset$ since
Proposition 5.3prop:winkle implies $T_{0}$ is contained in some
$T_{1}\in\mathcal{A}_{10}$.

Let $t\in T$. We claim that $t$ transposes some two lines $Kb,Kb^{\prime}\in
L$ and acts trivially on every other line in $L$. By Propositions 5.2 and
5.3prop:connect-up,prop:winkle, $T_{0}\cup\\{t\\}$ is contained in some
$T_{1}\in\mathcal{A}_{16}$. The group $G_{1}$ has monomial type, and therefore
the transvections in $G_{1}$ act as transpositions on $L_{1}$. Thus $t\in
G_{1}$ transposes some two lines $Kb,Kb^{\prime}\in L_{1}$. Now let
$Kb^{\prime\prime}\in L$ be any other line. Then $Kb^{\prime\prime}\in L_{2}$
for some $T_{2}\in\mathcal{A}_{100}$, and by Propositions 5.2 and
5.3prop:connect-up,prop:winkle the set $T_{1}\cup T_{2}$ is contained in some
$T_{3}\in\mathcal{A}_{236}$. Now $G_{3}|V_{3}$ is monomial type with unique
monomial structure $L_{3}$ such that $L_{1}\cup L_{2}\subseteq L_{3}$. By the
structure of transvections in monomial groups, $t$ acts trivially on each line
in $L_{3}\smallsetminus\\{Kb,Kb^{\prime}\\}$, including $Kb^{\prime\prime}$.

In particular, $L$ is $G$-invariant. To complete the proof it suffices to show
that the lines of $L$ are linearly independent, i.e., if
$L=\\{Kb_{1},\dots,Kb_{m}\\}$ then $b_{1},\dots,b_{m}$ are linearly
independent. Indeed, since $L$ is $G$-invariant it follows by irreducibility
that $m=n$ and $L$ is a $G$-invariant monomial structure. This shows that $G$
is a subgroup of a group of monomial type, and, by the argument we used to
show _(1) $\implies$ (2)_, any irreducible subgroup generated by transvections
of a group of monomial type not preserving a symplectic form itself must be of
monomial type.

Suppose

$\lambda_{1}b_{1}+\cdots+\lambda_{m}b_{m}=0\qquad(\lambda_{1},\dots,\lambda_{m}\in
K).$

Say $Kb_{1}\in L_{1}$ for some $T_{1}\in\mathcal{A}_{100}$. Since $G_{1}$ has
monomial type, $G_{1}$ contains some element $g$ mapping $b_{1}\mapsto xb_{1}$
($x\neq 1$) and say $b_{2}\mapsto x^{-1}b_{2}$, and acting trivially on every
other line of $L_{1}$. Consider any other line $Kb\in L$. We have $Kb\in
L_{2}$ for some $T_{2}\in\mathcal{A}_{100}$ and by Propositions 5.2 and
5.3prop:connect-up,prop:winkle we have $T_{1}\cup T_{2}\subseteq T_{3}$ for
some $T_{3}\in\mathcal{A}_{404}$. Since $G_{1}$ is a monomial-type subgroup of
the monomial-type group $G_{3}$, the element $g$ acts trivially on $Kb$. Thus
$g(b_{1})=xb_{1}$, $g(b_{2})=x^{-1}(b_{2})$, and $g(b_{i})=b_{i}$ for $i>2$.
Applying $g-1$, we thus have

$\lambda_{1}(x-1)b_{1}+\lambda_{2}(x^{-1}-1)b_{2}=0.$

Since $Kb_{1}\cap Kb_{2}=0$, this implies $\lambda_{1}=\lambda_{2}=0$. Since
this argument works for each index, it follows that $b_{1},\dots,b_{m}$ are
linearly independent, as required. ∎

Summarizing this subsection and the previous one, if $T\subseteq\mathfrak{T}$
is dense and $G=\left\langle{T}\right\rangle$ is classical, we can find a
bounded-size certificate $T_{0}\subseteq T$ for the classicality of $G$. This
is the content of the next proposition.

######  Lemma 6.8 ([GHS]*Lemma 4.3).

If $T$ is dense then $L_{5}(T)=L(T)$.

######  Proposition 6.9.

Let $n$ be sufficiently large. Let $T\subseteq\mathfrak{T}$ be dense and
assume $G=\left\langle{T}\right\rangle$ has classical type and defining field
$L(T)=\mathbf{F}_{q}$. Then there is a subset $T_{0}\subseteq T$ of
cardinality $|T_{0}|\leq 10^{5}$ such that
$G_{0}=\left\langle{T_{0}}\right\rangle$ acts irreducibly on the section
$W=[V,G_{0}]/[V,G_{0}]^{G_{0}}$ with classical type (over some subfield of
$\mathbf{F}_{q}$) and $\dim W>10$.

###### Proof.

By simply taking a union of suitable sets we can find a set $T_{1}\subseteq T$
of cardinality $|T_{1}|\leq 10^{4}$ with the following properties:

  1. (1)

$\dim V(T_{1})\geq 2000$;

  2. (2)

if $q\neq 2$, $\Gamma(T_{1})$ contains a cycle of length at most $5$ whose
weight is not contained in $\mathbf{F}_{2}$ (Lemma 6.8lem:L5);

  3. (3)

if $G$ does not preserve a symplectic form then $\Gamma(T_{1})$ contains a
non-symplectic cycle of length at most $5$ (Proposition 6.1prop:unitary-
symplectic-certificate);

  4. (4)

if $q=2$ and $G$ preserves a symplectic form then $T_{1}$ has a subset $T_{2}$
of cardinality $|T_{2}|\leq 1000$ such that
$G_{2}=\left\langle{T_{2}}\right\rangle$ acts irreducibly on $V_{2}=[V,G_{2}]$
and the restriction $G_{2}|V_{2}$ does not have odd symmetric type
(Proposition 6.4prop:sym-type-certificate);

  5. (5)

if $G$ does not preserve a symplectic form and $p=2$ then there is a subset
$T_{2}\subseteq T_{1}$ such that either

    1. (1)

$T_{2}$ is weakly nondegenerate but degenerate, or

    2. (2)

$G_{2}=\left\langle{T_{2}}\right\rangle$ acts irreducibly on $V_{2}=[V,G_{2}]$
with neither monomial type nor odd symmetric type

(Proposition 6.7prop:monomial-type-certificate).

By density of $T$, there is a set $T_{1}^{\prime}\subseteq T$ of cardinality
$|T_{1}^{\prime}|\leq 2|T_{1}|$ such that $V(T_{1})\cap
V^{*}(T_{1}^{\prime})^{\perp}=0$ and $V^{*}(T_{1})\cap
V(T_{1}^{\prime})^{\perp}=0$. Finally, by Proposition 5.2prop:connect-up,
$T_{1}\cup T_{1}^{\prime}$ is contained in a set $T_{0}\subseteq T$ of
cardinality $|T_{0}|\leq 6|T_{1}|\leq 10^{5}$ such that $\Gamma(T_{0})$ is
strongly connected.

Now consider the image $G_{0}|W$ of $G_{0}$ in $\operatorname{GL}(W)$, where
$W$ is the section $[V,G_{0}]/[V,G_{0}]^{G_{0}}$. By Proposition
4.1prop:irreducible-section, $G_{0}|W$ is irreducible and there is natural
surjective graph homomorphism $\Gamma(T_{0})\to\Gamma(T_{0}|W)$ respecting the
weights of cycles. We claim that $T_{0}|W$ inherits the properties listed
above. Apart from (5)(a), this is clear. In the case of (5)(a), the argument
is as follows. Note that, since $V(T_{1})\cap V^{*}(T_{0})^{\perp}\leq
V(T_{1})\cap V^{*}(T_{1}^{\prime})^{\perp}=0$, the subspace $V(T_{1})\leq
V(T_{0})$ maps injectively into $W$. Similarly, $W^{*}$ is naturally
identified with $V^{*}(T_{0})/V^{*}(T_{0})\cap V(T_{0})^{\perp}$, and since
$V^{*}(T_{1})\cap V(T_{0})^{\perp}=0$ it follows that $V^{*}(T_{1})$ maps
injectively into $W^{*}$. Thus if $T_{2}\subseteq T_{1}$ is weakly
nondegenerate but degenerate then so is its restriction $T_{2}|W$.

It follows from Proposition 6.4prop:sym-type-certificate and Proposition
6.7prop:monomial-type-certificate that $G_{0}|W$ has neither symmetric type
nor monomial type, and $\dim W>6$, so $G_{0}|W$ must have classical type. ∎

###  6.4. Subfield subgroups

Now let $K=\mathbf{F}_{q}$ be an arbitrary finite field,
$T\subseteq\mathfrak{T}$,
$G=\left\langle{T}\right\rangle\leq\operatorname{SL}_{n}(q)$. Assume $T$ is
dense, $G$ is classical, and $K=L(T)$. We aim to find a certificate
$T_{0}\subseteq T^{(\log q)^{O(1)}}$ of cardinality $|T_{0}|\leq 3$ such that
$L(T_{0})=K$.

######  Lemma 6.10.

Let $G\leq\operatorname{SL}_{n}(q)$ be a classical group generated by
transvections with defining field $\mathbf{F}_{q}$. Then there is a subset
$T_{0}\subseteq G\cap\mathfrak{T}$ of cardinality $|T_{0}|\leq 3$ such that
$L(T_{0})=\mathbf{F}_{q}$.

###### Proof.

Let $\lambda\in\mathbf{F}_{q}$ be a primitive element.

If $G=\operatorname{SL}_{2}(q)$ then we can take $T_{0}=\\{t,s\\}$ for
$t=1+\lambda e_{1}\otimes e_{2}^{*}$ and $s=1+e_{2}\otimes e_{1}^{*}$. Here
$e_{i}^{*}$ is defined by $e_{i}^{*}(e_{j})=\delta_{ij}$. Observe that

$w(t,s)=\operatorname{tr}((t-1)(s-1))=\operatorname{tr}(\lambda e_{1}\otimes
e_{1}^{*})=\lambda.$

Therefore $L(T_{0})$ contains $\mathbf{F}_{p}(\lambda)=\mathbf{F}_{q}$. This
completes the proof for linear and symplectic groups since both contain copies
of $\operatorname{SL}_{2}(q)$.

Now consider $G=\operatorname{SU}_{3}(\sqrt{q})$. Since all unitary forms are
equivalent it suffices to consider the unitary form

$f(x,y)=x_{1}y_{2}^{\theta}+x_{2}y_{1}^{\theta}+x_{3}y_{3}^{\theta},$

where $x^{\theta}=x^{\sqrt{q}}$ is the involutary automorphism. Now for $v\in
V=\mathbf{F}_{q}^{3}$ let us denote by $v^{*}\in V^{*}$ the map $u\mapsto
f(u,v)$. Note that $e_{1},e_{2}$ is a hyperbolic pair. Let
$\epsilon\in\mathbf{F}_{q}$ be such that $\epsilon^{\theta}=-\epsilon$ and
consider $t_{i}=1+\epsilon v_{i}\otimes v_{i}^{*}$ for $i=1,2,3$, where
$v_{1}=e_{1}$, $v_{2}=e_{2}$, and

$v_{3}=\epsilon^{-3}\lambda e_{1}+e_{2}+ze_{3},$

where $z$ is chosen so that $v_{3}$ is singular (recall that
$\operatorname{Fix}(\theta)=\\{zz^{\theta}:z\in K\\}$ for finite fields).
Since $v_{1},v_{2},v_{3}$ are singular, we have $t_{1},t_{2},t_{3}\in G$, and

$w(t_{1},t_{2},t_{3})=\epsilon^{3}f(v_{2},v_{1})f(v_{3},v_{2})f(v_{1},v_{3})=\lambda.$

Since $\operatorname{SU}_{3}(\sqrt{q})\leq\operatorname{SU}_{n}(\sqrt{q})$ for
$n\geq 3$ this completes the proof for unitary groups.

Finally consider an orthogonal group $G=\operatorname{O}_{n}^{\pm}(q)$, $n\geq
6$, $p=2$. The transvections in $G$ are precisely those of the form
$1+v\otimes v^{*}$ where $Q(v)=1$ and $v^{*}$ is defined by $v^{*}(u)=f(u,v)$.
Observe that

$w(1+u\otimes u^{*},1+v\otimes v^{*})=f(u,v)^{2}.$

Let $H\leq V$ be a $4$-dimensional hyperbolic subspace (see [aschbacher-
book]*(21.2)) and let $e_{1},e_{2},e_{3},e_{4}$ be a hyperbolic basis for $H$.
With respect to this basis we have, for $x,y\in H$,

$\displaystyle Q(x)$ $\displaystyle=x_{1}x_{2}+x_{3}x_{4},$ $\displaystyle
f(x,y)$ $\displaystyle=x_{1}y_{2}+x_{2}y_{1}+x_{3}y_{4}+x_{4}y_{3}.$

Let $u=e_{1}+e_{2}$ and $v=\lambda e_{1}+e_{3}+e_{4}$. Then $Q(u)=Q(v)=1$ and
$f(u,v)=\lambda$. Since finite fields are perfect, $\lambda^{2}$ generates
$\mathbf{F}_{q}$, so it suffices to take $T_{0}=\\{1+u\otimes u^{*},1+v\otimes
v^{*}\\}$. ∎

######  Proposition 6.11.

Let $T\subseteq\mathfrak{T}$ be dense, $G=\left\langle{T}\right\rangle$
classical, $L(T)=\mathbf{F}_{q}$, and assume $n$ is sufficiently large. Then
there is a subset $S\subseteq T^{(\log q)^{O(1)}}\cap\mathfrak{T}$ of
cardinality $|S|\leq 3$ such that $L(S)=\mathbf{F}_{q}$.

###### Proof.

First assume $G\neq\operatorname{SL}_{n}(q)$. Then there is a $G$-invariant
symplectic or unitary form $f$. The presence of this form simplifies the
argument enough that it is worth keeping it separate from the
$\operatorname{SL}_{n}(q)$ case.

First, by Proposition 6.9prop:classical-certificate and Proposition
5.3prop:winkle, there is a nondegenerate subset $T_{0}\subseteq T$ of bounded
cardinality such that $G_{0}=\left\langle{T_{0}}\right\rangle$ acts
irreducibly on $U_{0}=[V,G_{0}]$ with quasisimple classical type. Let
$K_{0}=L(T_{0})$. Now for $i>0$ proceed as follows. Assume
$T_{i-1}\subseteq\mathfrak{T}$ is a nondegenerate set of transvections of
bounded cardinality such that $G_{i-1}=\left\langle{T_{i-1}}\right\rangle$
acts on $U_{i-1}=[V,G_{i-1}]$ with quasisimple classical type and defining
field $K_{i-1}=L(T_{i-1})$. If $K_{i-1}=\mathbf{F}_{q}$, stop. Otherwise, let
$H_{i}\leq G_{i-1}$ be a quasisimple classical subgroup with the same defining
field as $G_{i-1}$ and of rank at most $6$ (e.g., a copy of
$\operatorname{SL}_{2}$, $\operatorname{SU}_{3}$, or
$\operatorname{O}_{6}^{\pm}$ over $K_{i-1}$). By the previous lemma, there is
a subset $T_{i}^{0}\subseteq H_{i}\cap\mathfrak{T}$ of cardinality at most
$10$ generating $H_{i}$. By Lemma 6.8lem:L5, there is a cycle $T_{i}^{1}$ in
$\Gamma(T)$ of length at most $5$ whose weight is not contained in $K_{i-1}$.
Applying Propositions 5.2 and 5.3prop:connect-up,prop:winkle, $T_{i}^{0}\cup
T_{i}^{1}$ is contained in a nondegenerate set $T_{i}\subseteq
T\cup(G_{i-1}\cap\mathfrak{T})$ of cardinality $|T_{i}|\leq 34$ such that
$\Gamma(T_{i})$ is strongly connected. Let
$G_{i}=\left\langle{T_{i}}\right\rangle$ and $K_{i}=L(T_{i})$. Let
$U_{i}=[V,G_{i}]$. Then $V=U_{i}\oplus U_{i}^{\perp}$ since $T_{i}$ is
nondegenerate, and $G_{i}$ acts irreducibly on $U_{i}=[V,G_{i}]$ by
Proposition 4.1prop:irreducible-section. Since $H_{i}\leq G_{i}$ and $H_{i}$
has quasisimple classical type, it follows from Theorem 1.4thm:classification
that $G_{i}$ also has quasisimple classical type on $U_{i}$. Moreover, $G_{i}$
has defining field $K_{i}>K_{i-1}$.

The process ends with some $K_{r}=\mathbf{F}_{q}$. Then
$K_{0}<\cdots<K_{r}=\mathbf{F}_{q}$. For each $i$, by Proposition 2.2main-thm-
bounded-rank, we have

$\ell_{T_{i}\cup H_{i}}(G_{i})\leq
O{\left(\frac{\log|G_{i}|}{\log|H_{i}|}\right)}^{O(1)}=O{\left(\frac{\log|K_{i}|}{\log|K_{i-1}|}\right)}^{O(1)}.$

Also $\ell_{T_{0}}(G_{0})\leq O(\log|K_{0}|)^{O(1)}$. Therefore, since
$H_{i}\leq G_{i-1}$ for each $i$,

$\displaystyle\ell_{T}(G_{r})\leq\ell_{T}(G_{0})\prod_{i=1}^{r}\ell_{T\cup
H_{i}}(G_{i})$ $\displaystyle\leq
O(\log|K_{0}|)^{O(1)}\prod_{i=1}^{r}O{\left(\frac{\log|K_{i}|}{\log|K_{i-1}|}\right)}^{O(1)}$
$\displaystyle\leq O(1)^{r}{\left(\log|K_{r}|\right)}^{O(1)}.$

Now since $|K_{i}|\geq|K_{i-1}|^{2}$ for each $i$ we have $q\geq 2^{2^{r}}$,
so it follows that

$\ell_{T}(G_{r})\leq O(\log q)^{O(1)}.$

Finally, by the previous lemma there is a subset $S\subseteq
G_{r}\cap\mathfrak{T}$ of cardinality $|S|\leq 3$ such that
$L(S)=\mathbf{F}_{q}$, as required.

Now suppose $G=\operatorname{SL}_{n}(q)$. We argue similarly but because we
cannot guarantee nondegeneracy we instead work with the section
$W_{i}=[V,G_{i}]/[V,G_{i}]^{G_{i}}$ throughout the argument. First we define a
bounded-cardinality starting set $T_{0}\subseteq T$. Using Proposition
6.1prop:unitary-symplectic-certificate we may include in $T_{0}$ a non-
symplectic cycle of length at most $5$. If $q$ is a square, we also include a
non-unitary cycle, as well as a cycle whose weight is not in
$\mathbf{F}_{\sqrt{q}}$, using Lemma 6.8lem:L5. Using Propositions 6.9, 5.2,
and 5.3prop:classical-certificate,prop:connect-up,prop:winkle, we may assume
$T_{0}$ is weakly nondegenerate, $\Gamma(T_{0})$ is strongly connected, and
$G_{0}=\left\langle{T_{0}}\right\rangle$ acts irreducibly and classically on
$W_{0}=[V,G_{0}]/[V,G_{0}]^{G_{0}}$, and $\dim W_{0}>10$. Because of the
presence of non-symplectic and non-unitary cycles,
$G_{0}|W_{0}\cong\operatorname{SL}_{\dim W_{0}}(K_{0})$ where
$K_{0}=L(T_{0})$. Now for $i>0$ proceed as follows. Assume
$T_{i-1}\subseteq\mathfrak{T}$ is a weakly nondegenerate set of transvections
of bounded cardinality such that $G_{i-1}=\left\langle{T_{i-1}}\right\rangle$
induces $\operatorname{SL}_{\dim W_{i-1}}(K_{i-1})$ on
$W_{i-1}=[V,G_{i-1}]/[V,G_{i-1}]^{G_{i-1}}$, and $\dim W_{i-1}>10$. If
$K_{i-1}=\mathbf{F}_{q}$, stop. Otherwise, by the previous lemma and
Proposition 4.5prop:tv-in-SL-sections there is a subset $T_{i}^{0}\subseteq
G_{i-1}\cap\mathfrak{T}$ of cardinality at most $3$ (actually $2$) such that
$L(T_{i}^{0})=K_{i-1}$. By Lemma 6.8lem:L5, there is a cycle $T_{i}^{1}$ in
$\Gamma(T)$ of length at most $5$ whose weight is not contained in $K_{i-1}$.
Let $t=1+v\otimes\phi\in T_{i}^{0}$ and let $H_{i}=1+K_{i-1}v\otimes\phi\cong
K_{i-1}$ be the full transvection subgroup over $K_{i-1}$ generated by $t$. It
follows from Proposition 4.5prop:tv-in-SL-sections that $H_{i}\leq G_{i-1}$.
Applying Propositions 5.2 and 5.3prop:connect-up,prop:winkle, $T_{0}\cup
T_{i}^{0}\cup T_{i}^{1}$ is contained in a bounded-cardinality weakly
nondegenerate set $T_{i}\subseteq T\cup(G_{i-1}\cap\mathfrak{T})$ such that
$\Gamma(T_{i})$ is strongly connected. Let
$G_{i}=\left\langle{T_{i}}\right\rangle$ and
$W_{i}=[V,G_{i}]/[V,G_{i}]^{G_{i}}$ and $K_{i}=L(T_{i})$. Then $K_{i}>K_{i-1}$
and, since $T_{0}\subseteq T_{i}$, $G_{i}|W_{i}\cong\operatorname{SL}_{\dim
W_{i}}(K_{i})$. Since $W_{0}$ is a section of $W_{i}$, $\dim W_{i}\geq\dim
W_{0}>10$.

As before the process ends with some $K_{r}=\mathbf{F}_{q}$. Then
$K_{0}<\cdots<K_{r}=\mathbf{F}_{q}$. Now we use Proposition 2.2main-thm-
bounded-rank in combination with the diameter bound in Proposition 4.5prop:tv-
in-SL-sections. For each $i$ we have

$\ell_{T_{i}\cup H_{i}}(G_{i})\leq
O{\left(\frac{\log|G_{i}|}{\log|(H_{i}|W_{i})|}\right)}^{O(1)}=O{\left(\frac{\log|K_{i}|}{\log|K_{i-1}|}\right)}^{O(1)}.$

Also $\ell_{T_{0}}(G_{0})\leq O(\log|K_{0}|)^{O(1)}$. Since $H_{i}\leq
G_{i-1}$ for each $i$ we get $\ell_{T}(G_{r})\leq O(\log q)^{O(1)}$ as before.
Finally we apply the previous lemma in combination with Proposition
4.5prop:tv-in-SL-sections again to find $S\subseteq G_{r}\cap\mathfrak{T}$ as
required. ∎

###  6.5. Orthogonal subgroups

The last thing remaining is distinguish orthogonal groups from symplectic
groups. Throughout this subsection assume $K=\mathbf{F}_{q}$ is a finite field
of characteristic $2$.

######  Lemma 6.12.

Let $(V,Q)$ be a nondegenerate quadratic space over a finite field
$K=\mathbf{F}_{q}$. Let $w+H\subseteq V$ be an affine subspace of codimension
$2$. Assume $\dim V\geq 10$. Then $Q(w+H)=K$.

###### Proof.

For $v\in H\cap w^{\perp}$ we have $Q(w+v)=Q(w)+Q(v)$, so it suffices to show
that $Q(H_{1})=K$ for $H_{1}=H\cap w^{\perp}$. Write $H_{1}=(H_{1}\cap
H_{1}^{\perp})\oplus H_{2}$. Then $H_{2}$ is nondegenerate and $H_{2}$ has
codimension at most $6$, so $\dim H_{2}\geq 4$. It follows from the
classification of quadratic forms over finite fields [aschbacher-book]*(21.2)
that $Q(H_{2})=K$. ∎

Now assume $T\subseteq\mathfrak{T}\cap\operatorname{Sp}_{n}(q)$ is dense,
$L(T)=K=\mathbf{F}_{q}$, and $G=\left\langle{T}\right\rangle$ is classical.

######  Proposition 6.13.

There is a constant $C$ such that the following are equivalent:

  1. (1)

$G$ is an orthogonal group,

  2. (2)

every nondegenerate subset $T_{0}\subseteq T^{(n\log q)^{O(1)}}$ of
cardinality at most $C$ generates a subgroup
$G_{0}=\left\langle{T_{0}}\right\rangle$ that preserves an orthogonal
structure on $V_{0}=V(T_{0})=[V,G_{0}]$.

###### Proof.

_(1) $\implies$ (2):_ Suppose $G$ preserves an orthogonal form $Q$ with
corresponding symplectic form $f$. If $T_{0}\subseteq T$ is nondegenerate then
$V_{0}=V(T_{0})$ is an $f$-nondegenerate subspace of $V$. Thus $Q_{0}=Q|V_{0}$
is a $G_{0}$-invariant orthogonal form on $V_{0}$.

_(2) $\implies$ (1):_ First, by Propositions 6.9, 6.11, 5.2, and
5.3prop:classical-certificate,prop:subfield,prop:connect-up,prop:winkle, there
is a bounded-cardinality nondegenerate subset $T_{0}\subseteq T^{(\log
q)^{O(1)}}$ such that $G_{0}=\left\langle{T_{0}}\right\rangle$ acts
irreducibly and classically on $V_{0}=V(T_{0})$ , $\dim V_{0}\geq 10$, and
$L(T_{0})=K$. Note $G_{0}$ must be an orthogonal group. By Proposition
2.2main-thm-bounded-rank,

$\ell_{T}(G_{0})\leq O(\log
q)^{O(1)},\qquad\ell_{G_{0}\cap\mathfrak{T}}(G_{0})\leq O(1).$

Thus by replacing $T$ with $T^{(\log q)^{O(1)}}\cap\mathfrak{T}$ we may assume
$T_{0}\subseteq T$ and $\ell_{T}(G_{0})\leq O(1)$.

Now we apply Proposition 3.5prop:orthogonal. For each $t\in T$ there is a
unique $v_{t}\in V$ such that $t=1+v_{t}\otimes v_{t}^{*}$. Consider some
linear relation

$\sum_{t\in T}\lambda_{t}v_{t}=0.$

Suppose $\lambda$ is supported on $t_{1},\dots,t_{m}$, and we may assume
$m\leq n+1$. We must show that $\tilde{Q}(\lambda)=0$, where

$\tilde{Q}(\lambda)=\sum_{t\in
T}\lambda_{t}^{2}+\sum_{\\{t,s\\}\in\binom{T}{2}}\lambda_{s}\lambda_{t}f(v_{s},v_{t}).$

Define also

$\tilde{f}(\lambda,\lambda^{\prime})=\tilde{Q}(\lambda+\lambda^{\prime})-\tilde{Q}(\lambda)-\tilde{Q}(\lambda^{\prime})=\sum_{\begin{subarray}{c}t,s\in
T\\\ t\neq s\end{subarray}}\lambda_{s}\lambda^{\prime}_{t}f(v_{s},v_{t}).$

We may think of $\lambda$ as an element of $K^{\mathfrak{T}}$, and $\tilde{Q}$
defines an orthogonal form on $K^{\mathfrak{T}}$ with corresponding symplectic
form $\tilde{f}$.

We aim to reduce the support of $\lambda$ as much as possible. Suppose $m\geq
10$, i.e., the support of $\lambda$ contains at least $10$ transvections
$t_{1},\dots,t_{10}$. Applying Propositions 5.2 and 5.3prop:connect-
up,prop:winkle, $T_{0}\cup\\{t_{1},\dots,t_{10}\\}$ is contained in a bounded-
cardinality nondegenerate set $T_{1}\subseteq T$ such that
$G_{1}=\left\langle{T_{1}}\right\rangle$ acts irreducibly on $V_{1}=V(T_{1})$.
Since $T_{0}\subseteq T_{1}$, $G_{1}$ must act classically, and therefore
$G_{1}$ must be an orthogonal group by hypothesis. Since $G_{0}\leq G_{1}$, by
Proposition 2.2main-thm-bounded-rank we have

$\ell_{T}(G_{1})\leq\ell_{T_{1}\cup G_{0}}(G_{1})\ell_{T}(G_{0})\leq O(1).$

By Lemma 6.12lem:Q-surjective-on-affine-subspace, we can find a transvection
$t\in G_{1}\subseteq T^{L}$ (for some constant $L$) such that $t=1+v\otimes
v^{*}$ for

$v\in\lambda_{1}v_{1}+\lambda_{2}v_{2}+Kv_{3}+\cdots+Kv_{10}.$

Hence we split the given linear relation into two shorter linear relations

$\displaystyle
v+\lambda_{1}v_{1}+\lambda_{2}v_{2}+\mu_{3}v_{3}+\cdots+\mu_{10}v_{10}$
$\displaystyle=0,$ $\displaystyle
v+(\lambda_{3}+\mu_{3})v_{3}+\cdots+(\lambda_{10}+\mu_{10})v_{10}+\sum_{i>10}\lambda_{i}v_{i}$
$\displaystyle=0.$

Repeating this argument for $\left\lfloor{m/10}\right\rfloor$ disjoint subsets
of $\\{t_{1},\dots,t_{m}\\}$ of size $10$, we find that we can add $\leq m/10$
transvections $t_{i}=1+v_{i}\otimes v_{i}^{*}\in T^{O(1)}$ such that our
original linear relation can be written as a sum of linear relations of
support $\leq 11$ and one of support at most $\left\lceil{9m/10}\right\rceil$,
i.e., $\lambda=\lambda^{(1)}+\cdots+\lambda^{(s)}$ where each $\lambda^{(j)}$
has support size at most $\left\lceil{9m/10}\right\rceil$ and

$\sum_{t\in T^{L}}\lambda_{t}^{(j)}v_{t}=0\qquad(j=1,\dots,s).$

Now we repeat this argument for $T^{L}$ and each of the $\lambda^{(j)}$, etc,
$\log n$ times. The end result is that $\lambda$ gets written as a sum of some
$\mu^{(1)},\dots,\mu^{(N)}$ where each vector $\mu$ has support size $O(1)$,
and

$\sum_{t\in T^{L^{\log n}}}\mu^{(j)}_{t}v_{t}=0\qquad(j=1,\dots,N).$

Note that $L^{\log n}=n^{O(1)}$. Finally we use

$\tilde{Q}(\lambda)=\tilde{Q}{\left(\sum_{j=1}^{N}\mu^{(j)}\right)}=\sum_{j=1}^{N}\tilde{Q}(\mu^{(j)})+\sum_{1\leq
j<j^{\prime}\leq N}\tilde{f}(\mu^{(j)},\mu^{(j^{\prime})}).$ (6.2)

We claim that each term on the right-hand side of (6.2) is zero. Indeed, first
consider some $\tilde{Q}(\mu)$, $\mu=\mu^{(j)}$. We know that $\mu$ is
supported on a set of $O(1)$ transvections $t\in T^{L^{\log n}}$. By
Propositions 5.2 and 5.3prop:connect-up,prop:winkle, the union of $T_{0}$ with
the support of $\mu$ is contained in a bounded-cardinality nondegenerate set
$T_{1}\subseteq T^{L^{\log n}}$ such that
$G_{1}=\left\langle{T_{1}}\right\rangle$ acts irreducibly on
$V_{1}=[V,T_{1}]$. Since $T_{0}\subseteq T_{1}$, $G_{1}$ acts classically and
therefore as an orthogonal group on $V_{1}$. Applying the forward direction of
Proposition 3.5prop:orthogonal, we find that $\tilde{Q}(\mu)=0$. By the same
argument applied to the union of the supports of $\mu$ and $\mu^{\prime}$,
$\mu^{\prime}=\mu^{(j^{\prime})}$, we also have
$\tilde{Q}(\mu+\mu^{\prime})=\tilde{Q}(\mu)+\tilde{Q}(\mu^{\prime})+\tilde{f}(\mu,\mu^{\prime})=0$,
and since $\tilde{Q}(\mu)=\tilde{Q}(\mu^{\prime})=0$ we have
$\tilde{f}(\mu,\mu^{\prime})=0$. This proves the claim. Hence
$\tilde{Q}(\lambda)=0$ and the proof is complete. ∎

###  6.6. Conclusion

######  Theorem 6.14 (Certification).

Let $n$ be sufficient large. Let
$T\subseteq\mathfrak{T}\subseteq\operatorname{SL}_{n}(q)$ be a set of
transvections such that $G=\left\langle{T}\right\rangle$ is an irreducible
classical group. Then there is a subset $T_{0}\subseteq T^{(n\log q)^{O(1)}}$
of cardinality $O(1)$ such that, for any subset $T_{1}\subseteq
G\cap\mathfrak{T}$ containing $T_{0}$ such that $\Gamma(T_{1})$ is strongly
connected, the group $G_{1}=\left\langle{T_{1}}\right\rangle$ acts on the
section $W=[V,G_{1}]/[V,G_{1}]^{G_{1}}$ as an irreducible classical group with
the same type and defining field as $G$ itself, and moreover $\dim W>10$.

###### Proof.

In brief, combine Propositions 6.1, 6.4, 6.7, 6.11, and 6.13prop:unitary-
symplectic-certificate,prop:sym-type-certificate,prop:monomial-type-
certificate,prop:subfield,prop:orthogonal-certificate.

We may assume $G$ has defining field $K=\mathbf{F}_{q}$. By Proposition
5.1prop:density and replacing $T$ with $T^{2n-1}\cap\mathfrak{T}$, we may
assume $T$ is dense. By Proposition 6.11prop:subfield, there is a subset
$S_{0}\subseteq T^{(\log q)^{O(1)}}$ of cardinality $|S_{0}|\leq 3$ such that
$L(S_{0})=K$. By Proposition 6.1prop:unitary-symplectic-certificate there is a
set $S_{1}\subseteq T$ of cardinality at most $10$ such that $S_{1}$ contains
a non-symplectic cycle if $T$ does and $S_{1}$ contains a non-unitary cycle if
$T$ does. By Proposition 6.4prop:sym-type-certificate, if $q=2$ and $G$ is
contained in a symplectic group, there is a subset $S_{2}\subseteq T$ of
cardinality $|S_{2}|\leq 2000$ that is not contained in a symmetric-type
subgroup. By Proposition 6.7prop:monomial-type-certificate, if $G$ is not
contained in a symplectic group, there is a subset $S_{3}\subseteq T$ of
cardinality $|S_{3}|\leq 1000$ that is not contained in a monomial subgroup.
By Proposition 6.13prop:orthogonal-certificate, if
$G=\operatorname{Sp}_{n}(q)$ there is a subset $S_{4}\subseteq T^{(n\log
q)^{O(1)}}$ of cardinality $O(1)$ that is not contained in an orthogonal
subgroup. Finally, by density of $T$ there is a bounded-cardinality set
$T_{0}\subseteq T$ such that for each $i$ (such that $S_{i}$ is defined) we
have $S_{i}\subseteq T_{0}$, moreover the natural maps

$\displaystyle V(S_{i})\to V(T_{0})/V(T_{0})\cap V^{*}(T_{0})^{\perp},$
$\displaystyle V^{*}(S_{i})\to V^{*}(T_{0})/V^{*}(T_{0})\cap V(T_{0})^{\perp}$

are injective, and moreover both spaces on the right have dimension at least
$2000$.

Let $T_{1}\subseteq\mathfrak{T}$ be a set containing $T_{0}$ such that
$\Gamma(T_{1})$ is strongly connected. By Proposition 4.1prop:irreducible-
section, $G_{1}=\left\langle{T_{1}}\right\rangle$ acts on
$W=[V,G_{1}]/[V,G_{1}]^{G_{1}}$ irreducibly. Let $\overline{G}_{1}=G_{1}|W$
and let $\overline{T}_{1}$ be the image of $T_{1}$ in $\overline{G}_{1}$. By
Proposition 4.1prop:irreducible-section, $\Gamma(T_{1})$ and
$\Gamma(\overline{T}_{1})$ are naturally identified and the weights of
corresponding cycles are equal. In particular,
$L(\overline{T}_{1})=L(T_{1})=K$, so $\overline{G}_{1}$ has defining field
$K$. Also $\Gamma(\overline{T}_{1})$ contains symplectic cycles if and only if
$\Gamma(T_{1})$ does, and ditto for unitary cycles. We also have $\dim W\geq
2000$. The symmetric-type and monomial-type certificates ensure that
$\overline{G}_{1}$ has neither symmetric type nor monomial type. Thus
$\overline{G}_{1}$ must have the same type as $G$. ∎

##  7\. Bounding the diameter

Finally we turn to the proof of our main theorem, Theorem 1.2thm:main. Let $G$
be one of the groups in scope and let $X$ be a generating set for $G$
containing a transvection $t$. Let

$T_{m}=\\{t^{x_{1}\cdots x_{m}}:x_{1},\dots,x_{m}\in X\\},\qquad
G_{m}=\left\langle{T_{m}}\right\rangle.$

Then $G_{0}\leq G_{1}\leq\cdots$ is an increasing sequence of subgroups of $G$
such that $G_{i}=G_{i+1}$ implies $G_{i}=\left\langle{t^{G}}\right\rangle=G$.
Let $m$ be the first index such that $G_{m}=G$. Then $2^{m}\leq|G_{m}|=|G|$,
so $m\leq\log_{2}|G|$, and $\left\langle{T_{m}}\right\rangle=G$. This
demonstrates that for the purpose of proving Theorem 1.2thm:main it is
sufficient to assume $X\subseteq\mathfrak{T}$ (cf. [GHS]*Lemma 2.1).

Thus assume $T\subseteq\mathfrak{T}$ is a generating set for $G$. In
particular, $\left\langle{T}\right\rangle$ is irreducible. Now we apply
Theorem 6.14thm:certification to obtain a certificate $T_{0}\subseteq
T^{(n\log q)^{O(1)}}$ of cardinality $O(1)$. We may assume $T_{0}$ is weakly
nondegenerate and $\Gamma(T_{0})$ is strongly connected. Let
$G_{0}=\left\langle{T_{0}}\right\rangle$. Unless $G=\operatorname{SL}(V)$,
$T_{0}$ is in fact nondegenerate and $G_{0}$ is a classical group with the
same type as $G$, defining field $K$, and domain $V_{0}=[V,G_{0}]$ of
dimension $\dim V_{0}\leq|T_{0}|=O(1)$. By Proposition 2.2main-thm-bounded-
rank, $\ell_{T_{0}}(G_{0})\leq O(\log q)^{O(1)}$. By replacing $T$ with
$T^{(n\log q)^{O(1)}}\cap\mathfrak{T}$ we may thus assume $T_{0}\subseteq
G_{0}\cap\mathfrak{T}\subseteq T$.

If $G=\operatorname{SL}(V)$, $T_{0}$ may only be weakly nondegenerate, but
$G_{0}|W_{0}=\operatorname{SL}(W_{0})$ where $W_{0}=V_{0}/V_{0}^{G_{0}}$,
$V_{0}=[V,G_{0}]$, and $\dim W_{0}>10$. By Propositions 2.2 and 4.5main-thm-
bounded-rank,prop:tv-in-SL-sections we have $\ell_{T_{0}}(G_{0})\leq O(\log
q)^{O(1)}$. Thus again by replacing $T$ with $T^{(n\log
q)^{O(1)}}\cap\mathfrak{T}$ we may assume $T_{0}\subseteq
G_{0}\cap\mathfrak{T}\subseteq T$.

Let $V=\mathbf{F}_{q}^{n}$ be the natural module for $G$. Then $V$ is a
linear, unitary, symplectic, or characteristic-2 orthogonal space. Let us call
a vector $v\in V$ _transvective_ if there is a transvection $t\in
G\cap\mathfrak{T}$ such that $[V,t]=\left\langle{v}\right\rangle$. If $V$ is
linear or symplectic, all vectors are transvective; if $V$ is unitary, a
vector is transvective if and only if it is singular; if $V$ is orthogonal, a
vector is transvective if and only if it is nonsingular.

######  Lemma 7.1.

Let $v=\sum_{i=1}^{k}v_{i}$ for transvective vectors $v_{1},\dots,v_{k}$. Then
$v-\lambda v_{i}-\mu v_{j}$ is transvective for some $i,j\in\\{1,\dots,k\\}$
and $\lambda,\mu\in K$.

###### Proof.

Clearly we may assume $V$ is unitary or orthogonal, as otherwise all vectors
are transvective.

_Unitary case._ (Cf. [GHS]*Lemma 4.19, which assumes $q$ is odd). We will take
$\mu=0$. If $v$ is singular then we can take $\lambda=0$. If $v$ is
nonsingular then

$f(v,v)=\sum_{i=1}^{k}f(v_{i},v)\neq 0,$

so $f(v_{i},v)\neq 0$ for some $i$ and

$f(v-\lambda v_{i},v-\lambda v_{i})=f(v,v)-\operatorname{tr}(\lambda
f(v_{i},v)).$

Since the trace map $\operatorname{tr}:\mathbf{F}_{q}\to\mathbf{F}_{\sqrt{q}}$
is surjective and $f(v,v)\in\mathbf{F}_{\sqrt{q}}$, we can choose $\lambda\in
K$ so that $f(v,v)=\operatorname{tr}(\lambda f(v_{i},v))$, and it follows that
$v-\lambda v_{i}$ is singular, as required.

_Orthogonal case._ Observe that

$Q(v-\lambda v_{i})=Q(v)-\lambda f(v,v_{i})+\lambda^{2}Q(v_{i}).$

Since $Q(v_{i})\neq 0$, there are at most two $\lambda\in K$ for which this is
zero, so we are done unless $q=2$, $Q(v)=0$, and $f(v,v_{i})=1$ for all $i$.
In this case there must be some $i,j$ such that $f(v_{i},v_{j})\neq 0$, and

$Q(v-v_{i}-v_{j})=Q(v_{i})+Q(v_{j})+f(v,v_{i})+f(v,v_{j})+f(v_{i},v_{j})=1,$

so we are done. ∎

######  Lemma 7.2.

Let $b_{1},\dots,b_{n}$ be a basis for $V$ with $b_{1},\dots,b_{n}$
transvective. For $v=\sum_{i=1}^{n}x_{i}b_{i}\in V$, let $s(v)$ be the number
of nonzero coefficients $x_{i}$. Then any transvective vector $v$ with
$s(v)=k$ is the sum of $4$ transvective vectors $v_{1},v_{2},v_{3},v_{4}$ with
$s(v_{i})\leq k/2+2$ for each $i$.

###### Proof.

Clearly we may write $v=u_{1}+u_{2}$ for some (not necessarily transvective)
$u_{1},u_{2}\in V$ such that $s(u_{1})\leq k/2+1$ and $s(u_{2})\leq k/2$. By
Lemma 7.1lem:transvective-1, there are indices $i,j$ and $\lambda,\mu\in K$
such that $v_{1}=u_{1}-\lambda b_{i}-\mu b_{j}$ is transvective and
$s(v_{1})\leq s(u_{1})\leq k/2+1$. Let $u_{2}^{\prime}=u_{1}+\lambda b_{i}+\mu
b_{j}$. Applying Lemma 7.1lem:transvective-1 again, there are indices
$i^{\prime},j^{\prime}$ and $\lambda^{\prime},\mu^{\prime}\in K$ such that
$v_{2}=u_{2}^{\prime}-\lambda^{\prime}b_{i^{\prime}}-\mu^{\prime}b_{j^{\prime}}$
is transvective and $s(v_{2})\leq s(u_{2}^{\prime})\leq k/2+2$. Let
$v_{3}=\lambda^{\prime}b_{i^{\prime}}$ and $v_{4}=\mu^{\prime}b_{j^{\prime}}$.
Then $v=v_{1}+v_{2}+v_{3}+v_{4}$, by construction $v_{1},v_{2},v_{3},v_{4}$
are transvective, and $s(v_{1})\leq k/2+1$, $s(v_{2})\leq k/2+2$, and
$s(v_{3}),s(v_{4})\leq 1$. ∎

######  Proposition 7.3.

$T^{n^{O(1)}}\supseteq G\cap\mathfrak{T}$.

###### Proof.

_Case $G\neq\operatorname{SL}_{n}(q)$_. Assume $V$ is a symplectic, unitary,
or orthogonal space. Let $f$ be the invariant form and for each $v\in V$ let
$v^{*}$ be the dual element associated to $v$ by $f$. Recall that a vector
$v\in V$ is transvective if and only if there is a transvection $t\in
G\cap\mathfrak{T}$ such that $t=1+\lambda v\otimes v^{*}$ for some $\lambda\in
K$. By Proposition 3.2prop:irreducible, there is a (transvective) basis
$b_{1},\dots,b_{n}$ for $V$ such that $1+\mu_{i}b_{i}\otimes b_{i}^{*}\in T$
for some $\mu_{i}\in K$ for each $i=1,\dots,n$. Let $s:V\to\\{0,\dots,n\\}$ be
the support function defined in Lemma 7.2lem:transvective-2 and for each
$k\geq 1$ let $T^{(k)}$ be the set of transvections $t=1+\lambda v\otimes
v^{*}\in G\cap\mathfrak{T}$ such that $s(v)\leq k$. It suffices to prove that
$T^{(5)}\subseteq T^{O(1)}$ and $T^{(2k)}\subseteq(T^{(k+2)})^{O(1)}$ for each
$k\geq 1$, for then it follows that

$G\cap\mathfrak{T}=T_{n}\subseteq
T^{O(1)^{\left\lceil{\log_{2}n}\right\rceil}}=T^{n^{O(1)}}.$

Let $t\in T^{(5)}$, say $t=1+\lambda v\otimes v^{*}$ and
$v=\sum_{i=1}^{k}x_{i}b_{i}$, $k\leq 5$. By Propositions 5.2 and
5.3prop:connect-up,prop:winkle, $T_{0}\cup\\{1+\mu_{i}b_{i}\otimes
b_{i}^{*}:1\leq i\leq k\\}$ is contained in a nondegenerate set
$T_{1}\subseteq T$ of cardinality $O(1)$ such that $\Gamma(T_{1})$ is strongly
connected. Then $G_{1}=\left\langle{T_{1}}\right\rangle$ is a classical group
with the same type as $G$ and defining field $K$ and domain $V_{1}=[V,G_{1}]$.
Since $b_{1},\dots,b_{k}\in V_{1}$ it follows that $v\in V_{1}$ and $t\in
G_{1}$. By Proposition 2.2main-thm-bounded-rank and the fact that $T$ contains
$G_{0}\cap\mathfrak{T}$ and $\log|G_{0}\cap\mathfrak{T}|\geq\log q$, we have
$G_{1}\subseteq T^{O(1)}$. Thus $T^{(5)}\subseteq T^{O(1)}$.

Similarly, let $k\geq 1$ and let $t\in T^{(2k)}$, say $t=1+\lambda v\otimes
v^{*}$ where $s(v)\leq 2k$. By Lemma 7.2lem:transvective-2,
$v=v_{1}+v_{2}+v_{3}+v_{4}$ where $s(v_{i})\leq k+2$ for each $i$. Let
$t_{i}\in T^{(k+2)}$ be a transvection of the form $1+\lambda_{i}v_{i}\otimes
v_{i}^{*}$ for $i=1,2,3,4$. By Propositions 5.2 and 5.3prop:connect-
up,prop:winkle, $T_{0}\cup\\{1+\lambda_{i}v_{i}\otimes v_{i}^{*}:i=1,2,3,4\\}$
is contained in a nondegenerate set $T_{1}\subseteq T^{(k+2)}$ of cardinality
$O(1)$ such that $\Gamma(T_{1})$ is strongly connected. Then
$G_{1}=\left\langle{T_{1}}\right\rangle$ is a classical group with the same
type as $G$ and defining field $K$ and domain $V_{1}=[V,G_{1}]$. Since
$v_{1},v_{2},v_{3},v_{4}\in V_{1}$, it follows exactly as above using
Proposition 2.2main-thm-bounded-rank that $t\in
G_{1}\subseteq(T^{(k+2)})^{O(1)}$. Thus $T^{(2k)}\subseteq(T^{(k+2)})^{O(1)}$,
as required.

_Case $G=\operatorname{SL}_{n}(q)$._ Now all vectors are transvective. Again
by Proposition 3.2prop:irreducible there are elements $1+b_{i}\otimes f_{i}\in
T$ ($1\leq i\leq n$) such that $b_{1},\dots,b_{n}$ is a basis for $V$, as well
as elements $1+c_{i}\otimes g_{i}\in T$ ($1\leq i\leq n$) such that
$g_{1},\dots,g_{n}$ is a basis for $V^{*}(T)$. Define $s(v)$ exactly as before
with respect to the basis $b_{1},\dots,b_{n}$ and $s(\phi)$ analogously for
$\phi\in V^{*}$ with respect to the basis $g_{1},\dots,g_{n}$. For each $k\geq
1$ let $T^{(k)}$ be the set of all transvections
$t=1+v\otimes\phi\in\mathfrak{T}$ such that $s(v)\leq k$ and $s(\phi)\leq k$.
It suffices to prove that $T^{(1)}\subseteq T^{O(1)}$ and
$T^{(2k)}\subseteq(T^{(k)})^{O(1)}$ for each $k\geq 1$.

Let $t\in T^{(1)}$, so without loss of generality $t=1+\lambda b_{i}\otimes
g_{j}$ for some indices $i,j$ and $\lambda\in K$. By Propositions 5.2 and
5.3prop:connect-up,prop:winkle, $T_{0}\cup\\{1+b_{i}\otimes
f_{i},1+c_{j}\otimes g_{j}\\}$ is contained in a bounded-cardinality weakly
nondegenerate set $T_{1}\subseteq T$ such that $\Gamma(T_{1})$ is strongly
connected. Applying Proposition 4.5prop:tv-in-SL-sections and Proposition
2.2main-thm-bounded-rank, $t\in G_{1}=\left\langle{T_{1}}\right\rangle$ and
$G_{1}\subseteq T^{O(1)}$. Since $t$ was arbitrary this proves
$T^{(1)}\subseteq T^{O(1)}$.

Similarly, let $k\geq 1$ and let $t\in T^{(2k)}$, say $t=1+v\otimes\phi$ where
$s(v)\leq 2k$ and $s(\phi)\leq 2k$. Write $v=v_{1}+v_{2}$ and
$\phi=\phi_{1}+\phi_{2}$ where $s(v_{1}),s(v_{2}),s(\phi_{1}),s(\phi_{2})\leq
k$. Let $t_{i}=1+v_{i}\otimes\phi_{i}$ for $i=1,2$ and observe that
$t_{1},t_{2}\in T^{(k)}$. By Propositions 5.2 and 5.3prop:connect-
up,prop:winkle, $T_{0}\cup\\{t_{1},t_{2}\\}$ is contained in a weakly
nondegenerate set $T_{1}\subseteq T^{(k)}$ of cardinality $O(1)$ such that
$\Gamma(T_{1})$ is strongly connected. Observe that $v=v_{1}+v_{2}\in
V(T_{1})$ and $\phi=\phi_{1}+\phi_{2}\in V^{*}(T_{1})$, so $t\in
G_{1}=\left\langle{T_{1}}\right\rangle$. Exactly as before we have
$G_{1}\subseteq(T^{(k)})^{O(1)}$, so we have proved that
$T^{(2k)}\subseteq(T^{(k)})^{O(1)}$, as required. ∎

######  Proposition 7.4.

$\ell_{T}(G)\leq n^{O(1)}$.

###### Proof.

By the previous proposition, $\ell_{T}(G\cap\mathfrak{T})\leq n^{O(1)}$. By
the Liebeck–Shalev theorem [liebeck-shalev]*Theorem 1.1 we have
$\ell_{G\cap\mathfrak{T}}(G)\leq O(n)$. Thus

$\ell_{T}(G)\leq\ell_{T}(G\cap\mathfrak{T})\ \ell_{G\cap\mathfrak{T}}(G)\leq
n^{O(1)},$

as claimed. ∎

This completes the proof of Theorem 1.2thm:main, since $\ell_{X}(T)\leq(n\log
q)^{O(1)}$.

## References