# The relational complexity of linear groups
acting on subspaces

Saul D. Freedman  SAUL D. FREEDMAN, School of Mathematics and Statistics,
University of St Andrews, St Andrews, KY16 9SS, UK Current address: Centre for
the Mathematics of Symmetry and Computation, The University of Western
Australia, Crawley, WA 6009, Australia<EMAIL_ADDRESS>,  Veronica
Kelsey  VERONICA KELSEY, Department of Mathematics, University of Manchester,
Manchester, M13 9PL, UK<EMAIL_ADDRESS>and  Colva M. Roney-
Dougal  COLVA M. RONEY-DOUGAL, School of Mathematics and Statistics,
University of St Andrews, St Andrews, KY16 9SS, UK colva.roney-dougal@st-
andrews.ac.uk

###### Abstract.

The relational complexity of a subgroup $G$ of $\mathrm{Sym}({\Omega})$ is a
measure of the way in which the orbits of $G$ on $\Omega^{k}$ for various $k$
determine the original action of $G$. Very few precise values of relational
complexity are known. This paper determines the exact relational complexity of
all groups lying between $\mathrm{PSL}_{n}(\mathbb{F})$ and
$\mathrm{PGL}_{n}(\mathbb{F})$, for an arbitrary field $\mathbb{F}$, acting on
the set of $1$-dimensional subspaces of $\mathbb{F}^{n}$. We also bound the
relational complexity of all groups lying between $\mathrm{PSL}_{n}(q)$ and
$\mathrm{P}\Gamma\mathrm{L}_{n}(q)$, and generalise these results to the
action on $m$-spaces for $m\geq 1$.

###### Key words and phrases:

Relational complexity, linear groups, subspace actions

###### 2020 Mathematics Subject Classification:

20B15, 20G40, 03C13

##  1\. Introduction

The study of relational complexity began with work of Lachlan in model theory
as a way of studying _homogeneous_ relational structures: those in which every
isomorphism between induced substructures extends to an automorphism of the
whole structure. For the original definition see, for example, [11]; an
equivalent definition in terms of permutation groups was given by Cherlin [1],
and, apart from a slight generalisation to group actions, is the one we now
present.

Let $\Omega$ be an arbitrary set and let $H$ be a group acting on $\Omega$.
Fix $k\in\mathbb{Z}$, and let
$X:=(x_{1},\ldots,x_{k}),Y:=(y_{1},\ldots,y_{k})\in\Omega^{k}$. For $r\leq k$,
we say that $X$ and $Y$ are _$r$ -equivalent_ under $H$, denoted
$X{\underset{H,r}{\sim}}Y$, if for every $r$-subset of indices
$\\{i_{1},\ldots,i_{r}\\}\subseteq\\{1,\ldots,k\\}$, there exists an $h\in H$
such that $(x_{i_{1}}^{h},\ldots,x_{i_{r}}^{h})=(y_{i_{1}},\ldots,y_{i_{r}})$.
If $X{\underset{H,k}{\sim}}Y$, i.e. if $Y\in X^{H}$, then $X$ and $Y$ are
_equivalent_ under $H$. The _relational complexity_ of $H$, denoted
$\mathrm{RC}(H,\Omega)$, or $\mathrm{RC}(H)$ when $\Omega$ is clear, is the
smallest $r\geq 1$ such that $X{\underset{H,r}{\sim}}Y$ implies $Y\in X^{H}$,
for all $X,Y\in\Omega^{k}$ and all $k\geq r$. Equivalently, $\mathrm{RC}(H)$
is the smallest $r$ such that $r$-equivalence of tuples implies equivalence of
tuples. Note that $\mathrm{RC}(H)\geq 2$ if $H\neq 1$ and $|\Omega|>1$, as $X$
or $Y$ may contain repeated entries.

Calculating the precise relational complexity of a group is often very
difficult. A major obstacle is that if $K<H\leq\mathrm{Sym}({\Omega})$, then
there is no uniform relationship between $\mathrm{RC}(K,\Omega)$ and
$\mathrm{RC}(H,\Omega)$. For example, if $n\geq 4$, then the relational
complexities of the regular action of $C_{n}$ and natural actions of
$\mathrm{A}_{n}$ and $\mathrm{S}_{n}$ are $2$, $n-1$ and $2$, respectively. In
[1], Cherlin gave three families of finite primitive binary groups (groups
with relational complexity two) and conjectured that this list was complete.
In a dramatic recent breakthrough, this conjecture was proved by Gill, Liebeck
and Spiga in [6]; this monograph also contains an extensive literature review.

In [1, 2], Cherlin determined the exact relational complexity of
$\mathrm{S}_{n}$ and $\mathrm{A}_{n}$ in their actions on $k$-subsets of
$\\{1,\ldots,n\\}$. The relational complexity of the remaining large-base
primitive groups is considered in [4]. Looking at finite primitive groups more
generally, Gill, Lodà and Spiga proved in [7] that if
$H\leq\mathrm{Sym}({\Omega})$ is primitive and not large-base, then
$\mathrm{RC}(H,\Omega)<9\log|\Omega|+1$ (our logarithms are to the base $2$).
This bound was tightened by the second and third author in [10] to
$5\log|\Omega|+1$. Both [7] and [10] bounded the relational complexity via
base size, and the groups with the largest upper bounds are classical groups
acting on subspaces of the natural module, and related product action groups.
This motivated us to obtain further information about the relational
complexity of these groups; this paper confirms that these bounds are tight,
up to constants.

We now fix some notation for use throughout this paper. Let $n$ be a positive
integer, $\mathbb{F}$ a field, $V=\mathbb{F}^{n}$, and
$\Omega_{m}=\mathcal{PG}_{m}(V)$ be the set of $m$-dimensional subspaces of
$V$. We shall study the relational complexity of the almost simple groups
$\overline{H}$ with
${\mathrm{PSL}_{n}(\mathbb{F})\trianglelefteq\overline{H}\leq\mathrm{P}\Gamma\mathrm{L}_{n}(\mathbb{F})}$,
acting on $\Omega_{m}$. We will generally work with the corresponding groups
$H$ with ${\mathrm{SL}_{n}(\mathbb{F})\trianglelefteq
H\leq\Gamma\mathrm{L}_{n}(\mathbb{F})}$, as these naturally have the same
relational complexity when acting on $\Omega_{m}$.

Several of our results focus on the case $\mathbb{F}=\mathbb{F}_{q}$. We begin
with the following theorem of Cherlin.

######  Theorem 1.1 ([1, Example 3]).

The relational complexity of $\mathrm{GL}_{n}(q)$ acting on the nonzero
vectors of $\mathbb{F}_{q}^{n}$ is equal to $n$ when $q=2$, and $n+1$ when
$q\geq 3$. Hence $\mathrm{RC}(\mathrm{PGL}_{n}(2),\Omega_{1})=n$.

More generally, for
$\mathrm{PSL}_{n}(q)\trianglelefteq\overline{H}\leq\mathrm{PGL}_{n}(q)$, Lodà
[12, Corollary 5.2.7] shows that
$\mathrm{RC}(\overline{H},\Omega_{1})<2\log|\Omega_{1}|+1$. Other results
imply an alternative upper bound on $\mathrm{RC}(\overline{H},\Omega_{1})$. We
first note that the _height_ of a permutation group $K$ on a set $\Omega$,
denoted $\mathrm{H}(K)$ or $\mathrm{H}(K,\Omega)$, is the maximum size of a
subset $\Delta$ of $\Omega$ with the property that $K_{(\Gamma)}<K_{(\Delta)}$
for each $\Gamma\subsetneq\Delta$. It is easy to show (see [7, Lemma 2.1])
that $\mathrm{RC}(K)\leq\mathrm{H}(K)+1$. By combining this with immediate
generalisations of results of Hudson [9, §5.3-5.4] and Lodà [12, Prop 5.2.1],
we obtain the following (for $|\mathbb{F}|=2$, see Theorem 1.1; we also omit a
few small exceptional cases for brevity).

######  Proposition 1.2.

Let
$\mathrm{PSL}_{n}(\mathbb{F})\trianglelefteq\overline{H}\leq\mathrm{PGL}_{n}(\mathbb{F})$
and $|\mathbb{F}|\geq 3$.

  1. (i)

Suppose that $n=2$, with $|\mathbb{F}|=q\geq 7$ if
$\overline{H}\neq\mathrm{PGL}_{2}(\mathbb{F})$. If $|\mathbb{F}|\geq 4$, then
$\mathrm{H}(\overline{H},\Omega_{1})=3$ and
$\mathrm{RC}(\overline{H},\Omega_{1})=n+2=4$, whilst
$\mathrm{RC}(\mathrm{PGL}_{2}(3),\Omega_{1})=n=2$.

  2. (ii)

If $n\geq 3$, then $\mathrm{H}(\overline{H},\Omega_{1})=2n-2$ and
$\mathrm{RC}(\overline{H},\Omega_{1})\leq 2n-1$.

Our first theorem gives the exact relational complexity of groups between
$\mathrm{PSL}_{n}(\mathbb{F})$ and $\mathrm{PGL}_{n}(\mathbb{F})$ for $n\geq
3$, acting naturally on 1-spaces.

######  Theorem A.

Let $n\geq 3$, and let $\mathbb{F}$ be any field. Then the following hold.

  1. (i)

$\mathrm{RC}(\mathrm{PGL}_{n}(\mathbb{F}),\Omega_{1})=\begin{cases}n&\text{ if
}|\mathbb{F}|\leq 3,\\\ n+2&\text{ if }|\mathbb{F}|\geq 4.\end{cases}$

  2. (ii)

If
$\mathrm{PSL}_{n}(\mathbb{F})\trianglelefteq\overline{H}<\mathrm{PGL}_{n}(\mathbb{F})$,
then

$\mathrm{RC}(\overline{H},\Omega_{1})=\begin{cases}2n-1&\text{ if }n=3,\\\
2n-2&\text{ if }n\geq 4.\end{cases}$

For most groups, we see that the relational complexity is very close to the
bound in Proposition 1.2(ii). However, the difference between the height and
the relational complexity of $\mathrm{PGL}_{n}(\mathbb{F})$ increases with $n$
when $|\mathbb{F}|\geq 3$. This addresses a recent question of Cherlin and
Wiscons (see [6, p. 23]): there exists a family of finite primitive groups
that are not large-base, where the difference between height and relational
complexity can be arbitrarily large. Theorem A also provides infinitely many
examples of almost simple groups $\overline{H}$ with
$\mathrm{RC}(\mathrm{Soc}(\overline{H}))>\mathrm{RC}(\overline{H})$.

We next bound the relational complexity of the remaining groups with socle
$\mathrm{PSL}_{n}(q)$ that act on $\Omega_{1}$. For $k\in\mathbb{Z}_{>0}$, the
number of distinct prime divisors of $k$ is denoted by $\omega(k)$, with
$\omega(1)=0$.

######  Theorem B.

Let $\overline{H}$ satisfy
$\mathrm{PSL}_{n}(q)\leq\overline{H}\leq\mathrm{P}\Gamma\mathrm{L}_{n}(q)$,
and let $e:=|\overline{H}:\overline{H}\cap\mathrm{PGL}_{n}(q)|$. Suppose that
$e>1$, so that $q\geq 4$ and $\overline{H}\not\leq\mathrm{PGL}_{n}(q)$.

  1. (i)

If $n=2$ and $q\geq 8$, then
$4+\omega(e)\geq\mathrm{RC}(\overline{H},\Omega_{1})\geq 4$, except that
$\mathrm{RC}(\mathrm{P}\Sigma\mathrm{L}_{2}(9),\Omega_{1})=3$.

  2. (ii)

If $n\geq 3$, then

$2n-1+\omega(e)\geq\mathrm{RC}(\overline{H},\Omega_{1})\geq\begin{cases}n+2&\text{
always},\\\ n+3&\text{ if }\mathrm{PGL}_{n}(q)<\overline{H},\\\ 2n-2&\text{ if
}\overline{H}\leq\mathrm{P}\Sigma\mathrm{L}_{n}(q)\neq\mathrm{P}\Gamma\mathrm{L}_{n}(q).\end{cases}$

In fact, the lower bound of $2n-2$ holds for a larger family of groups; see
Proposition 3.7.

######  Theorem C.

Let $\overline{H}$ satisfy
$\mathrm{PSL}_{n}(q)\leq\overline{H}\leq\mathrm{P}\Gamma\mathrm{L}_{n}(q)$ and
let $e:=|\overline{H}:\overline{H}\cap\mathrm{PGL}_{n}(q)|$. Fix
$m\in\\{2,\ldots,{\lfloor\frac{n}{2}\rfloor}\\}$. Then

$(m+1)n-2m+2+\omega(e)\geq\mathrm{RC}(\overline{H},\Omega_{m})\geq
mn-m^{2}+1.$

GAP [5] calculations using [3] yield
$\mathrm{RC}(\mathrm{P}\Gamma\mathrm{L}_{2}(3^{5}),\Omega_{1})=5=4+\omega(5)$
and $\mathrm{RC}(\mathrm{P}\Gamma\mathrm{L}_{4}(9),\Omega_{1})=8=7+\omega(2)$,
so the upper bounds of Theorem B cannot be improved in general. On the other
hand, $\mathrm{RC}(\mathrm{P}\Gamma\mathrm{L}_{3}(2^{6}),\Omega_{1})$ achieves
the lower bound of $6=3+3<7=5+\omega(6)$. Additionally,
$\mathrm{RC}(\mathrm{PSL}_{4}(2),\Omega_{2})$ achieves the lower bound of $5$
from Theorem C, while $\mathrm{RC}(\mathrm{PSL}_{4}(3),\Omega_{2})=6$ and
$\mathrm{RC}(\mathrm{PGL}_{4}(3),\Omega_{2})=\mathrm{RC}(\mathrm{PSL}_{4}(4),\Omega_{2})=\mathrm{RC}(\mathrm{P}\Gamma\mathrm{L}_{4}(4),\Omega_{2})=8$.

It is straightforward to use our results to bound the relational complexity in
terms of the degree. For example,
$\mathrm{RC}(\mathrm{PGL}_{n}(q),\Omega_{1})<\log(|\Omega_{1}|)+3$. Many of
our arguments also apply to the case where $\mathbb{F}$ is an arbitrary field;
see Theorem 3.1, Lemmas 3.5 and 3.6, and Propositions 3.7 and 4.1.

This paper is structured as follows. In Section 2, we fix some more notation
and prove some elementary lemmas, then prove upper bounds on the relational
complexity of the relevant actions on $1$-spaces. In Section 3, we shall prove
corresponding lower bounds, and then prove Theorems A and B. Finally, in
Section 4, we prove Theorem C.

##  2\. Action on 1-spaces: upper bounds

In this section we present several preliminary lemmas, and then determine
upper bounds for the relational complexity of groups $H$, with
$\mathrm{SL}_{n}(\mathbb{F})\trianglelefteq H\leq\mathrm{GL}_{n}(\mathbb{F})$,
acting on $\Omega_{1}$.

We begin with some notation that we will use throughout the remainder of the
paper. Let $\\{e_{1},\ldots,e_{n}\\}$ be a basis for $V$. For a set $\Gamma$,
a tuple $X=(x_{i})_{i=1}^{k}\in\Gamma^{k}$ and a permutation
$\sigma\in\mathrm{S}_{k}$, we write $X^{\sigma}$ to denote the $k$-tuple
$(x_{1^{\sigma^{-1}}},\ldots,x_{k^{\sigma^{-1}}})$. For a tuple
$X\in\Omega_{m}^{k}$, we write $\langle X\rangle$ to denote the subspace of
$V$ spanned by all entries in $X$. For $i\in\\{1,\ldots,k\\}$, we shall write
$(X\setminus x_{i})$ to denote the subtuple of $X$ obtained by deleting
$x_{i}$.

In the remainder of this section, let $\Omega:=\Omega_{1}=\mathcal{PG}_{1}(V)$
and let $H$ be a group such that $\mathrm{SL}_{n}(\mathbb{F})\trianglelefteq
H\leq\mathrm{GL}_{n}(\mathbb{F})$. Recall from Theorem 1.1 that
$\mathrm{RC}(\mathrm{GL}_{n}(\mathbb{F}),\Omega)=n$ when $|\mathbb{F}|=2$.
Thus we shall assume throughout this section that $|\mathbb{F}|\geq 3$ and
$n\geq 2$.

We write $D$ to denote the subgroup of diagonal matrices of
$\mathrm{GL}_{n}(\mathbb{F})$ (with respect to the basis
$\\{e_{1},\ldots,e_{n}\\}$), and $\Delta:=\big{\\{}\langle e_{i}\rangle\mid
i\in\\{1,\ldots,n\\}\big{\\}}$. Observe that $D\cap H$ is the pointwise
stabiliser $H_{(\Delta)}$. For a vector $v=\sum_{i=1}^{n}\alpha_{i}e_{i}\in
V$, the _support_ $\mathrm{supp}({v})$ of $v$ is the set
$\\{i\in\\{1,\ldots,n\\}\mid\alpha_{i}\neq 0\\}$. Additionally, the _support_
$\mathrm{supp}({W})$ of a subset $W$ of $V$ is the set $\bigcup_{w\in
W}\mathrm{supp}({w})$, and similarly for tuples. In particular, $\Delta$ is
the set of subspaces of $V$ with support of size $1$, and
$\mathrm{supp}({W})=\mathrm{supp}({\langle W\rangle})$ for all subsets $W$ of
$V$.

###  2.1. Preliminaries

We begin our study of the action of $H$ on $\Omega$ with a pair of lemmas that
will enable us to consider only tuples of a very restricted form.

######  Lemma 2.1.

Let $k\geq n$, and let $X,Y\in\Omega^{k}$ be such that
$X{\underset{H,n}{\sim}}Y$. Additionally, let $a:=\mathrm{dim}(\langle
X\rangle)$. Then there exist
$X^{\prime}=(x^{\prime}_{1},\ldots,x^{\prime}_{k}),Y^{\prime}=(y^{\prime}_{1},\ldots,y^{\prime}_{k})\in\Omega^{k}$
such that

  1. (i)

$x^{\prime}_{i}=y^{\prime}_{i}=\langle e_{i}\rangle$ for
$i\in\\{1,\ldots,a\\}$, and

  2. (ii)

$X{\underset{H,r}{\sim}}Y$ if and only if
$X^{\prime}{\underset{H,r}{\sim}}Y^{\prime}$, for each $r\in\\{1,\ldots,k\\}$.

###### Proof.

Observe that there exists $\sigma\in\mathrm{S}_{k}$ such that $\langle
X^{\sigma}\rangle=\langle
x_{1^{\sigma^{-1}}},\ldots,x_{a^{\sigma^{-1}}}\rangle$. Since
$X{\underset{H,n}{\sim}}Y$ and $a\leq n$, the definition of $a$-equivalence
yields $X^{\sigma}{\underset{H,a}{\sim}}Y^{\sigma}$. Hence there exists an
$f\in H$ such that $x_{i^{\sigma^{-1}}}^{f}=y_{i^{\sigma^{-1}}}$ for all
$i\in\\{1,\ldots,a\\}$, and so $\langle Y^{\sigma}\rangle=\langle
y_{1^{\sigma^{-1}}},\ldots,y_{a^{\sigma^{-1}}}\rangle$. Since
$\mathrm{SL}_{n}(\mathbb{F})$ is transitive on $n$-tuples of linearly
independent $1$-spaces, there exists $h\in\mathrm{SL}_{n}(\mathbb{F})\leq H$
such that $x_{i^{\sigma^{-1}}}^{fh}=y_{i^{\sigma^{-1}}}^{h}=\langle
e_{i}\rangle$ for $i\in\\{1,\ldots,a\\}$. Define
$X^{\prime},Y^{\prime}\in\Omega^{k}$ by
$x_{i}^{\prime}=x_{i^{\sigma^{-1}}}^{fh}$ and
$y_{i}^{\prime}=y_{i^{\sigma^{-1}}}^{h}$, so that $X^{\prime}=X^{\sigma fh}$
and $Y^{\prime}=Y^{\sigma h}$. Then
$X^{\prime}{\underset{H,r}{\sim}}Y^{\prime}$ if and only if
$X^{\sigma}{\underset{H,r}{\sim}}Y^{\sigma}$, which holds if and only if
$X{\underset{H,r}{\sim}}Y$. ∎

######  Lemma 2.2.

Let $k\geq r\geq n$, and let $X,Y\in\Omega^{k}$ be such that
$X{\underset{H,r}{\sim}}Y$. Additionally, let ${a:=\mathrm{dim}(\langle
X\rangle)}$ and assume that $a<n$. If $a=1$, or if
$\mathrm{RC}(\mathrm{GL}_{a}(\mathbb{F}),\mathcal{PG}_{1}(\mathbb{F}^{a}))\leq
r$, then $Y\in X^{H}$.

###### Proof.

If $a=1$, then all entries of $X$ are equal, so since $r\geq n\geq 2$, we see
that $X{\underset{H,r}{\sim}}Y$ directly implies $Y\in X^{H}$. We will
therefore suppose that $a\geq 2$ and
$\mathrm{RC}(\mathrm{GL}_{a}(\mathbb{F}),\mathcal{PG}_{1}(\mathbb{F}^{a}))\leq
r$. By Lemma 2.1, we may assume without loss of generality that $\langle
X\rangle=\langle Y\rangle=\langle e_{1},\ldots,e_{a}\rangle$. As
$X{\underset{H,r}{\sim}}Y$ and
$\mathrm{RC}(\mathrm{GL}_{a}(\mathbb{F}),\mathcal{PG}_{1}(\mathbb{F}^{a}))\leq
r$, there exists an element $g\in\mathrm{GL}_{a}(\mathbb{F})$ mapping $X$ to
$Y$, considered as tuples of subspaces of $\langle e_{1},\ldots,e_{a}\rangle$.
We now let $h$ be the diagonal matrix $\mathrm{diag}(\det({g}^{-1}),1,\ldots
1)\in\mathrm{GL}_{n-a}(\mathbb{F})$, and observe that $g\oplus
h\in\mathrm{SL}_{n}(\mathbb{F})$ maps $X$ to $Y$, and so $Y\in X^{H}$. ∎

We now begin our study of some particularly nice $k$-tuples.

######  Lemma 2.3.

Let $k\geq n+1$, and let $X,Y\in\Omega^{k}$ be such that $x_{i}=y_{i}=\langle
e_{i}\rangle$ for $i\in\\{1,\ldots,n\\}$ and $X{\underset{H,n+1}{\sim}}Y$.
Then $\mathrm{supp}({x_{i}})=\mathrm{supp}({y_{i}})$ for all
$i\in\\{1,\ldots,k\\}$.

###### Proof.

It is clear that $\mathrm{supp}({x_{i}})=\\{i\\}=\mathrm{supp}({y_{i}})$ when
$i\in\\{1,\ldots,n\\}$. Assume therefore that $i>n$. Since
$X{\underset{H,n+1}{\sim}}Y$, there exists $g\in H$ such that $(\langle
e_{1}\rangle,\ldots,\langle e_{n}\rangle,x_{i})^{g}=(\langle
e_{1}\rangle,\ldots,\langle e_{n}\rangle,y_{i})$. Observe that $g\in
H_{(\Delta)}=D\cap H$, and so $\mathrm{supp}({x_{i}})=\mathrm{supp}({y_{i}})$.
∎

Our final introductory lemma collects several elementary observations
regarding tuples of subspaces in $\overline{\Delta}:=\Omega\setminus\Delta$,
the set of $1$-dimensional subspaces of support size greater than $1$. For
$r\geq 1$ and $A,B\in\overline{\Delta}^{r}$, we let $\mathbb{M}_{A,B}$ consist
of all matrices in $\mathbb{M}_{n,n}(\mathbb{F})$ that fix $\langle
e_{i}\rangle$ for $1\leq i\leq n$ and map $a_{j}$ into $b_{j}$ for $1\leq
j\leq r$. Notice that all matrices in $\mathbb{M}_{A,B}$ are diagonal, and
that if $g,h\in\mathbb{M}_{A,B}$, then $a_{j}^{g+h}=a_{j}^{g}+a_{j}^{h}\leq
b_{j}$, so $\mathbb{M}_{A,B}$ is a subspace of $\mathbb{M}_{n,n}$. For an
$n\times n$ matrix $g=(g_{ij})$ and a subset $I$ of $\\{1,\ldots,n\\}$, we
write $g|_{I}$ to denote the submatrix of $g$ consisting of the rows and
columns with indices in $I$.

######  Lemma 2.4.

Let $r\geq 1$, and let
$A=(a_{1},\ldots,a_{r}),B=(b_{1},\ldots,b_{r})\in\overline{\Delta}^{\,r}$.

  1. (i)

Let $a_{i}$ and $a_{j}$ be (possibly equal) elements of $A$ such that
$\mathrm{supp}({a_{i}})\cap\mathrm{supp}({a_{j}})\neq\varnothing$, and let
$g\in\mathbb{M}_{A,A}$. Then $g|_{\mathrm{supp}({a_{i},a_{j}})}$ is a scalar.

  2. (ii)

Suppose that $A{\underset{D,1}{\sim}}B$. Then for $1\leq i\leq r$, the space
$(\mathbb{M}_{(a_{i}),(b_{i})})|_{\mathrm{supp}({a_{i}})}$ is one-dimensional,
so the dimension of $\mathbb{M}_{(a_{i}),(b_{i})}$ is equal to
$n+1-|\mathrm{supp}({a_{i}})|$.

  3. (iii)

For a subtuple $A^{\prime}$ of $A$, let
$S:=\\{1,\ldots,n\\}\setminus\mathrm{supp}({A^{\prime}})$. Then
$\mathrm{dim}((\mathbb{M}_{A^{\prime},A^{\prime}})|_{S})=|S|$.

###### Proof.

Part (i) is clear. For Part (ii), by assumption, there is an invertible
diagonal matrix mapping $a_{i}$ to $b_{i}$, so
$\mathrm{supp}({a_{i}})=\mathrm{supp}({b_{i}})$. Let $k$ and $\ell$ be
distinct elements of $\mathrm{supp}({a_{i}})$, which exist as
$a_{i}\in\overline{\Delta}$. If $a_{i}^{g}\leq b_{i}$, then $e_{k}^{g}=\lambda
e_{k}$ for some $\lambda\in\mathbb{F}$, and the value of $\lambda$ completely
determines the image $\mu e_{\ell}$ of $e_{\ell}$ under $g$. The result
follows. Part (iii) is now just a slight generalisation (with $B=A$). ∎

###  2.2. Upper bounds for $\mathrm{SL}_{n}(\mathbb{F})\trianglelefteq
H\leq\mathrm{GL}_{n}(\mathbb{F})$ on 1-spaces

In this subsection, we will suppose that $n\geq 4$ and $|\mathbb{F}|\geq 3$,
and let $H$ be any group such that
${\mathrm{SL}_{n}(\mathbb{F})\trianglelefteq
H\leq\mathrm{GL}_{n}(\mathbb{F})}$. Our main result is Theorem 2.7, which
gives upper bounds on $\mathrm{RC}(H,\Omega)$.

######  Lemma 2.5.

If $X{\underset{H,2n-2}{\sim}}Y$ implies that $X{\underset{H,2n-1}{\sim}}Y$,
for all $X,Y\in\Omega^{2n-1}$ with $x_{i}=y_{i}=\langle e_{i}\rangle$ for
$i\in\\{1,\ldots,n\\}$, then $\mathrm{RC}(H,\Omega)\leq 2n-2$.

###### Proof.

Let $k$ be at least $2n-1$, and let $A,B\in\Omega^{k}$ satisfy
$A{\underset{H,2n-2}{\sim}}B$. Let $A^{\prime}$ be a subtuple of $A$ of length
$2n-1$, and $B^{\prime}$ the corresponding $(2n-1)$-subtuple of $B$. We shall
show that $B^{\prime}\in{A^{\prime}}^{H}$ for all such $A^{\prime}$ and
$B^{\prime}$, so that $A{\underset{H,2n-1}{\sim}}B$. It will then follow from
Proposition 1.2(ii) that $A\in B^{H}$, as required.

Let $a:=\mathrm{dim}(\langle A^{\prime}\rangle)$, and suppose first that
$a<n$. We observe from Proposition 1.2 that if $a\geq 2$, then
$\mathrm{RC}(\mathrm{GL}_{a}(\mathbb{F}),\mathcal{PG}_{1}(\mathbb{F}^{a}))<2n-2$.
As $A^{\prime}{\underset{H,2n-2}{\sim}}B^{\prime}$, Lemma 2.2 yields
$B^{\prime}\in{A^{\prime}}^{H}$. If instead $a=n$, then by Lemma 2.1 there
exist $X$ and $Y$ in $\Omega^{2n-1}$, such that $x_{i}=y_{i}=\langle
e_{i}\rangle$ for each $i\in\\{1,\ldots,n\\}$, and such that for all $r\geq
1$, the relations $A^{\prime}{\underset{H,r}{\sim}}B^{\prime}$ and
$X{\underset{H,r}{\sim}}Y$ are equivalent. Now,
$A^{\prime}{\underset{H,2n-2}{\sim}}B^{\prime}$, so
$X{\underset{H,2n-2}{\sim}}Y$. If $X{\underset{H,2n-2}{\sim}}Y$ implies that
$X{\underset{H,2n-1}{\sim}}Y$, then $B^{\prime}\in{A^{\prime}}^{H}$, as
required. ∎

We shall therefore let $X$ and $Y$ be elements of $\Omega^{2n-1}$ with
$x_{i}=y_{i}=\langle e_{i}\rangle$ for $i\in\\{1,\ldots,n\\}$, such that
$X{\underset{H,2n-2}{\sim}}Y$. Additionally, for $i\in\\{1,\ldots,2n-1\\}$ and
$j\in\\{1,\ldots,n\\}$, define

(1) $\alpha_{ij},\beta_{ij}\in\mathbb{F}\mbox{ so that
}x_{i}=\langle\sum_{j=1}^{n}\alpha_{ij}e_{j}\rangle\mbox{ and
}y_{i}=\langle\sum_{j=1}^{n}\beta_{ij}e_{j}\rangle.$

######  Lemma 2.6.

If at least one of the following holds, then $Y\in X^{H}$.

  1. (i)

There exist $i,j\in\\{n+1,\ldots,2n-1\\}$ with $i\neq j$ and
$\mathrm{supp}({x_{i}})\subseteq\mathrm{supp}({x_{j}})$.

  2. (ii)

There exists a nonempty $R\subseteq\\{n+1,\ldots,2n-1\\}$ with $|\bigcap_{i\in
R}\mathrm{supp}({x_{i}})|=1$.

  3. (iii)

There exists $i\in\\{n+1,\ldots,2n-1\\}$ such that $\mathrm{supp}({x_{i}})\geq
4$.

###### Proof.

We begin by noting that Lemma 2.3 yields
$\mathrm{supp}({y_{i}})=\mathrm{supp}({x_{i}})$ for all
$i\in\\{1,\ldots,2n-1\\}$.

  1. (i)

Since $X{\underset{H,2n-2}{\sim}}Y$, there exists an $h\in H$ mapping
$(X\setminus x_{i})$ to $(Y\setminus y_{i})$, and such an $h$ is necessarily
diagonal, with fixed entries in $\mathrm{supp}({x_{j}})$ (up to scalar
multiplication).

Now, let $\ell\in\\{n+1,\ldots,2n-1\\}\setminus\\{i,j\\}$ (this is possible as
$n\geq 4$). There exists an $h^{\prime}\in H$ mapping $(X\setminus x_{\ell})$
to $(Y\setminus y_{\ell})$, and as before each such $h^{\prime}$ is diagonal.
Hence every matrix in $H\cap D$ mapping $x_{j}$ to $y_{j}$ maps $x_{i}$ to
$y_{i}$, and in particular $x_{i}^{h}=y_{i}$ and so $X^{h}=Y$.

  2. (ii)

Let $\\{\ell\\}:=\bigcap_{i\in R}\mathrm{supp}({x_{i}})$. Then
$\alpha_{i\ell}\neq 0$ for all $i\in R$. Since $X{\underset{H,2n-2}{\sim}}Y$,
there exists $h\in H$ such that $(X\setminus x_{\ell})^{h}=(Y\setminus
y_{\ell})$. It follows that for all
$k\in\\{1,\ldots,n\\}\backslash\\{\ell\\}$, there exists
$\gamma_{k}\in\mathbb{F}^{*}$ such that $e_{k}^{h}=\gamma_{k}e_{k}$. Thus for
each $i\in R$,

$y_{i}=x_{i}^{h}=\Big{\langle}\sum_{k\in\mathrm{supp}({x_{i}})}\alpha_{ik}e_{k}^{h}\Big{\rangle}=\Big{\langle}\alpha_{i\ell}e_{\ell}^{h}+\sum_{k\in\mathrm{supp}({x_{i}})\setminus\\{\ell\\}}\alpha_{ik}\gamma_{k}e_{k}\Big{\rangle}.$

Since $\alpha_{i\ell}\neq 0$, we deduce that
$\mathrm{supp}({e_{\ell}^{h}})\subseteq\mathrm{supp}({y_{i}})=\mathrm{supp}({x_{i}})$.
As this holds for all $i\in R$, we obtain
$\mathrm{supp}({e_{\ell}^{h}})=\\{\ell\\}$. Thus $x_{\ell}^{h}=\langle
e_{\ell}\rangle^{h}=\langle e_{\ell}\rangle=y_{\ell}$, so $X^{h}=Y$.

  3. (iii)

Permute the last $n-1$ coordinates of $X$ and $Y$ so that
$\mathrm{supp}({x_{n+1}})\geq 4$. By (ii), we may assume that
$x_{i}\not\in\Delta$ for all $i\geq n+1$. For each
$k\in{\\{n+1,\ldots,2n-1\\}}$, we define $X_{n+1}^{k}:=(x_{n+1},\ldots,x_{k})$
and $Y_{n+1}^{k}:=(y_{n+1},\ldots,y_{k})$. As
$\mathrm{supp}({x_{i}})=\mathrm{supp}({y_{i}})$ for all $i$, we see that
$X_{n+1}^{k}{\underset{D,1}{\sim}}Y_{n+1}^{k}$, so $X_{n+1}^{k}$ and
$Y_{n+1}^{k}$ satisfy the conditions of Lemma 2.4(ii).

Suppose first that there exists $j\in{\\{n+2,\ldots,2n-1\\}}$ such that
$\mathbb{M}_{X_{n+1}^{j},Y_{n+1}^{j}}=\mathbb{M}_{X_{n+1}^{j-1},Y_{n+1}^{j-1}}$.
As $X{\underset{H,2n-2}{\sim}}Y$, there exists $h\in H\cap D$ such that
$(X\setminus x_{j})^{h}=(Y\setminus y_{j})$. Hence
$h\in\mathbb{M}_{X_{n+1}^{j-1},Y_{n+1}^{j-1}}$, and so
$h\in\mathbb{M}_{X_{n+1}^{j},Y_{n+1}^{j}}$. Therefore, $x_{j}^{h}=y_{j}$ and
$X^{h}=Y$.

Hence we may assume instead that
$\mathbb{M}_{X_{n+1}^{j},Y_{n+1}^{j}}<\mathbb{M}_{X_{n+1}^{j-1},Y_{n+1}^{j-1}}$
for all $j\in{\\{n+2,\ldots,2n-1\\}}$. Then
$\mathrm{dim}(\mathbb{M}_{X_{n+1}^{j},Y_{n+1}^{j}})\leq\mathrm{dim}(\mathbb{M}_{X_{n+1}^{j-1},Y_{n+1}^{j-1}})-1$.
Lemma 2.4(ii) yields
$\mathrm{dim}(\mathbb{M}_{X_{n+1}^{n+1},Y_{n+1}^{n+1}})\leq{n-3}$, and hence
$\mathbb{M}_{X_{n+1}^{2n-2},Y_{n+1}^{2n-2}}=\\{0\\}=\mathbb{M}_{X_{n+1}^{2n-1},Y_{n+1}^{2n-2}}$,
contradicting our assumption. ∎

We now prove the main result of this subsection.

######  Theorem 2.7.

Suppose that $n\geq 4$ and $|\mathbb{F}|\geq 3$, and let $H$ be any group with
${\mathrm{SL}_{n}(\mathbb{F})\trianglelefteq
H\leq\mathrm{GL}_{n}(\mathbb{F})}$. Then $\mathrm{RC}(H,\Omega)\leq 2n-2$.

###### Proof.

Let $X,Y\in\Omega^{2n-1}$ be as defined before Lemma 2.6. By Lemma 2.5 it
suffices to show that $Y\in X^{H}$, so assume otherwise. We may also assume
that all subspaces in $X$ are distinct, so that
$|\mathrm{supp}({x_{i}})|\in\\{2,3\\}$ for each $i\in\\{n+1,\ldots,2n-1\\}$ by
Lemma 2.6(iii).

For $k\in\\{2,3\\}$, let $R_{k}$ be the set of all $i\in\\{n+1,\ldots,2n-1\\}$
such that $|\mathrm{supp}({x_{i}})|=k$. Then

(2) $|R_{2}|+|R_{3}|=n-1.$

Observe from Lemma 2.6(i)–(ii) that if $i\in R_{2}$, then
$\mathrm{supp}({x_{i}})\cap\mathrm{supp}({x_{j}})=\varnothing$ for each
$j\in{\\{n+1,\ldots,2n-1\\}\setminus\\{i\\}}$. Hence $2|R_{2}|\leq n$ and

(3) $|U|:=\bigg{|}\bigcup_{j\in
R_{3}}\mathrm{supp}({x_{j}})\bigg{|}\leq\bigg{|}\\{1,\ldots,n\\}\setminus\Big{(}\dot{\bigcup_{i\in
R_{2}}}\mathrm{supp}({x_{i}})\Big{)}\bigg{|}=n-2|R_{2}|.$

We now determine an expression for $|U|$ involving $|R_{3}|$. Observe first
that $|R_{3}|\geq 1$, else $|R_{2}|=n-1$ by (2), contradicting $2|R_{2}|\leq
n$. Define a relation $\sim$ on $R_{3}$ by $i\sim j$ if
$\mathrm{supp}({x_{i}})\cap\mathrm{supp}({x_{j}})\neq\varnothing$, and let
$\mathcal{P}$ be the equivalence classes of the transitive closure of $\sim$.
Let $P$ be a class of $\mathcal{P}$. By Lemma 2.6(i)–(ii),
$|\mathrm{supp}({x_{i}})\cap\mathrm{supp}({x_{j}})|\in\\{0,2\\}$ for all
distinct $i,j\in R_{3}$. Thus if $|P|=1$, then $|\bigcup_{c\in
P}\mathrm{supp}({x_{c}})|=3$, and if $|P|=2$, then $|\bigcup_{c\in
P}\mathrm{supp}({x_{c}})|=4$.

Now suppose that $|P|\geq 3$. Then there exist distinct $c_{1},c_{2},c_{3}\in
P$ with $c_{1}\sim c_{2}$ and $c_{2}\sim c_{3}$. Let
$I:=\bigcap_{i=1}^{3}\mathrm{supp}({x_{c_{i}}})$. We observe that $|I|\neq 0$,
and so Lemma 2.6(ii) shows that $I$ has size two and is equal to
$\mathrm{supp}({x_{c_{1}}})\cap\mathrm{supp}({x_{c_{3}}})$. Hence $c_{1}\sim
c_{3}$ and
$\bigcup_{i=1}^{3}\mathrm{supp}({x_{c_{i}}})=I\dot{\cup}\big{(}\dot{\bigcup}_{i=1}^{3}(\mathrm{supp}({x_{c_{i}}})\setminus
I)\big{)}$. If $|P|>3$, then there exists $c_{4}\in
P\setminus\\{c_{1},c_{2},c_{3}\\}$ such that, without loss of generality,
$c_{4}\sim c_{1}$. As $c_{1}\sim c_{j}$ for each $j\in\\{2,3\\}$, the above
argument shows that $\bigcap_{i\in\\{1,j,4\\}}\mathrm{supp}({x_{c_{i}}})=I$
and
$\bigcup_{i=1}^{4}\mathrm{supp}({x_{c_{i}}})=I\dot{\cup}\big{(}\dot{\bigcup}_{i=1}^{4}(\mathrm{supp}({x_{c_{i}}})\setminus
I)\big{)}$. Repeating this argument inductively on $|P|$ shows that
${\bigcup}_{c\in
P}\mathrm{supp}({x_{c}})=I\dot{\cup}\big{(}\dot{\bigcup}_{c\in
P}(\mathrm{supp}({x_{c}})\setminus I)\big{)}$, which has size $2+|P|$.

Finally, let $r\geq 1$ be the number of parts of $\mathcal{P}$. As
$|R_{3}|=\sum_{P\in\mathcal{P}}|P|$, we deduce that $|U|=2r+|R_{3}|\geq
2+|R_{3}|$. Thus (3) yields $2+|R_{3}|\leq n-2|R_{2}|$. Hence
$2|R_{2}|+|R_{3}|\leq n-2<n-1$, which is equal to $|R_{2}|+|R_{3}|$ by (2), a
contradiction. ∎

###  2.3. Upper bounds for $\mathrm{GL}_{n}(\mathbb{F})$ on 1-spaces

In this subsection, we determine a much smaller upper bound on
$\mathrm{RC}(\mathrm{GL}_{n}(\mathbb{F}),\Omega)$ via our main result, Theorem
2.12. We shall assume throughout that $n$ and $|\mathbb{F}|$ are at least $3$,
and write $G:=\mathrm{GL}_{n}(\mathbb{F})$. Since $D$ is the pointwise
stabiliser of $\Delta$ in $G$, we will prove Theorem 2.12 by combining Lemmas
2.1 and 2.2 with information about the action of $D$ on $r$-tuples $A$ and $B$
of subspaces in $\overline{\Delta}=\Omega\setminus\Delta$. If these tuples are
$(r-1)$-equivalent under $D$, then by acting on one with a suitable element of
$\overline{\Delta}$ we may assume that their first $r-1$ entries are equal. We
shall denote the nonzero entries of elements $g$ of $D$ by just
$g_{1},\ldots,g_{n}$ rather than $g_{11},\ldots,g_{nn}$, since $g$ is
necessarily diagonal.

######  Lemma 2.8.

Let $r\geq 3$, and let $A,B\in\overline{\Delta}^{\,r}$ be such that
$(a_{1},\ldots,a_{r-1})=(b_{1},\ldots,b_{r-1})$, $A{\underset{D,r-1}{\sim}}B$,
and $B\notin A^{D}$. Let $C=\\{a_{1},\ldots,a_{r-1}\\}$ and assume also that
$\mathrm{supp}({C})=\\{1,\ldots,n\\}$. Then (after reordering the basis for
$V$ and $(a_{1},\ldots,a_{r-1})$ if necessary) the following statements hold.

  1. (i)

There exist integers $2\leq i_{1}<i_{2}<\ldots<i_{r-1}=n$ such that, for each
$t\in\\{1,\ldots,r-1\\}$, $\mathrm{supp}({a_{1},\ldots,a_{t}})$ is equal to
$\\{1,\ldots,i_{t}\\}$.

  2. (ii)

Let $t\in\\{1,\ldots,r-3\\}$. Then
$\mathrm{supp}({a_{t}})\cap\mathrm{supp}({a_{u}})=\varnothing$ for all
$u\in\\{t+2,\ldots,r-1\\}$.

  3. (iii)

The support of $a_{2}$ does not contain $1$.

  4. (iv)

Let $t\in\\{1,\ldots,r-1\\}$. Then
$i_{t}\in\mathrm{supp}({a_{t}})\cap\mathrm{supp}({a_{t+1}})$.

  5. (v)

Each integer in $\mathrm{supp}({a_{r}})$ lies in the support of a unique
subspace in $C$.

###### Proof.

We begin by fixing notation related to
$a_{r}=\langle\sum_{\ell=1}^{n}\alpha_{\ell}e_{\ell}\rangle$ and
$b_{r}=\langle\sum_{\ell=1}^{n}\beta_{\ell}e_{\ell}\rangle$. Since
$A{\underset{D,r-1}{\sim}}B$, there exists an element in $D$ mapping $a_{r}$
to $b_{r}$, and so $\mathrm{supp}({b_{r}})=\mathrm{supp}({a_{r}})$. On the
other hand, $B\notin A^{D}$, and so $a_{r}\neq b_{r}$. Therefore, by scaling
the basis vectors for $a_{r}$ and $b_{r}$, there exist
$j,k\in\\{1,\ldots,n\\}$ such that $j<k$, $\alpha_{j}=\beta_{j}=1$, and
$\alpha_{k}$ and $\beta_{k}$ are distinct and nonzero. Reordering
$\\{e_{1},\ldots,e_{n}\\}$ if necessary, we may assume that $j=1$. Then each
element of $D$ that maps $a_{r}$ to $b_{r}$ also maps $\langle
e_{1}+\alpha_{k}e_{k}\rangle$ to $\langle e_{1}+\beta_{k}e_{k}\rangle$; we
will use this fact throughout the proof.

  1. (i)

We show first that there is no partition of $C$ into proper subsets
$C^{\prime}$ and $C^{\prime\prime}$ such that
$\mathrm{supp}({C^{\prime}})\cap\mathrm{supp}({C^{\prime\prime}})=\varnothing$,
so suppose otherwise, for a contradiction. Then, as $|C^{\prime}|<r-1$ and
$A{\underset{D,r-1}{\sim}}B$, there exists an $f\in D_{(C^{\prime})}$ such
that $a_{r}^{f}=b_{r}$. Multiplying $f$ by a scalar if necessary, we may
assume that $f_{1}=1$. Then $f_{i}=\beta_{i}/\alpha_{i}$ for each
$i\in\mathrm{supp}({a_{r}})$. Similarly, there exists $g\in
D_{(C^{\prime\prime})}$ with the same properties. As
$\mathrm{supp}({C^{\prime}})\cap\mathrm{supp}({C^{\prime\prime}})=\varnothing$,
there exists an $h\in D$ such that
$h|_{\mathrm{supp}({C^{\prime}})}=f|_{\mathrm{supp}({C^{\prime}})}$ and
$h|_{\mathrm{supp}({C^{\prime\prime}})}=g|_{\mathrm{supp}({{C^{\prime\prime}}})}$.
Since $\mathrm{supp}({C})=\\{1,\ldots,n\\}$, we observe that
$h|_{\mathrm{supp}({a_{r}})}=f|_{\mathrm{supp}({a_{r}})}=g|_{\mathrm{supp}({a_{r}})}$.
Hence $a_{r}^{h}=b_{r}$. Furthermore, by construction, $h\in
D_{(C^{\prime})}\cap D_{(C^{\prime\prime})}=D_{C}$. Thus $B\in A^{D}$, a
contradiction.

Next, by reordering $a_{1},\ldots,a_{r-1}$ if necessary, we may assume that
$1\in\mathrm{supp}({a_{1}})$. Then by reordering $\\{e_{2},\ldots,e_{n}\\}$ if
necessary, we may assume that $\mathrm{supp}({a_{1}})$ is equal to
$\\{1,2,\ldots,i_{1}\\}$ for some $i_{1}\geq 2$, since
$a_{1}\in\overline{\Delta}$. Thus the result holds for $t=1$. We will use
induction to prove the result in general, and to show that, for all
$s\in\\{2,\ldots,r-1\\}$,

(4) $\text{ there exists }w\in\\{1,\ldots,s-1\\}\text{ such that
}\mathrm{supp}({a_{s}})\cap\mathrm{supp}({a_{w}})\neq\varnothing.$

Let $t\in\\{2,\ldots,r-1\\}$, let $U_{t-1}:=\\{a_{1},\ldots,a_{t-1}\\}$ and
assume inductively that $\mathrm{supp}({U_{t-1}})=\\{1,2,\ldots,i_{t-1}\\}$.
If $t\geq 3$ assume also that (4) holds for all $s\in\\{2,\ldots,t-1\\}$.
Since $C$ cannot be partitioned into two parts whose support has trivial
intersection,
$\mathrm{supp}({a_{1},\ldots,a_{t-1}})\cap\mathrm{supp}({a_{t},\ldots,a_{r-1}})\neq\varnothing$,
so we may reorder $\\{a_{t},\ldots,a_{r-1}\\}$ so that (4) holds when $s=t$.

Suppose for a contradiction that
$\mathrm{supp}({a_{t}})\subseteq\mathrm{supp}({U_{t-1}})$. Then (4) (applied
to each $s\in\\{2,\ldots,t-1\\}$) and Lemma 2.4 imply that $D_{(C)}$ is equal
to $D_{(C\setminus a_{t})}$. Since $A{\underset{D,r-1}{\sim}}B$, the latter
stabiliser contains an element mapping $a_{r}$ to $b_{r}$. Hence the same is
true for $D_{(C)}$, contradicting the fact that $B\notin A^{D}$. Therefore, we
can reorder $\\{e_{i_{t-1}+1},\ldots,e_{n}\\}$ so that
$\mathrm{supp}({a_{t}})$ contains $\\{i_{t-1}+1,\ldots,i_{t}\\}$ for some
$i_{t}>i_{t-1}$, and the result and (4) follow by induction. Note in
particular that $i_{r-1}=n$, since $\mathrm{supp}({C})=\\{1,\ldots,n\\}$.

  2. (ii)

Let $m\in\\{1,\ldots,r-1\\}$ be such that $\mathrm{supp}({a_{m}})$ contains
the integer $k$ from the first paragraph of this proof, and let
$\mathcal{I}:=\\{1,\ldots,m\\}$. Then, using (4) (for each
$s\in\mathcal{I}\setminus\\{1\\}$) and Lemma 2.4(i), we observe that every
$g\in D_{(a_{1},\ldots,a_{m})}$ satisfies $g_{1}=g_{k}$. Therefore,
$a_{r}^{g}\neq b_{r}$ for all $g\in D_{(a_{1},\ldots,a_{m})}$. As
$A{\underset{D,r-1}{\sim}}B$, we deduce that $m=r-1$. In particular, $a_{r-1}$
is the unique subspace in $C$ whose support contains $k$. Swapping $e_{k}$ and
$e_{n}$ if necessary, we may assume that $k=n$.

Now, for a contradiction, suppose that
$\mathrm{supp}({a_{t}})\cap\mathrm{supp}({a_{u}})\neq\varnothing$ for some
$t\in\\{1,\ldots,r-3\\}$ and $u\in\\{t+2,\ldots,r-1\\}$, and assume that $u$
is the largest integer with this property. Then (4) and the maximality of $u$
imply that $\mathrm{supp}({a_{s}})\cap\mathrm{supp}({a_{s-1}})\neq\varnothing$
for all $s\in\\{u+1,\ldots,r-1\\}$. It now follows from Lemma 2.4(i), together
with a further application of (4) to each $s\in\\{2,\ldots,t\\}$, that every
$g\in E:=D_{(a_{1},\ldots,a_{t},a_{u},\ldots,a_{r-1})}$ satisfies
$g_{1}=g_{n}$. Therefore, $a_{r}^{g}\neq b_{r}$ for all $g\in E$. However,
$|(a_{1},\ldots,a_{t},a_{u},\ldots,a_{r-1})|<r-1$, contradicting the fact that
$A{\underset{D,r-1}{\sim}}B$.

  3. (iii)–(iv)

As in the proof of (ii), we may assume that $k=n$. We observe from (ii) and
(4) that $\mathrm{supp}({a_{t}})\cap\mathrm{supp}({a_{t+1}})\neq\varnothing$
for all $t\leq r-2$. Hence if $1\in\mathrm{supp}({a_{2}})$ then Lemma 2.4(i)
shows that every $g\in D_{(a_{2},\ldots,a_{r-1})}$ satisfies $g_{1}=g_{n}$
(since $k=n$). This contradicts the fact that $A{\underset{D,r-1}{\sim}}B$,
and so (iii) holds. Finally, since
$\mathrm{supp}({a_{t}})\cap\mathrm{supp}({a_{t+1}})\neq\varnothing$ for each
$t\leq r-2$, we obtain (iv) by defining $i_{0}:=1$ and reordering the vectors
in $\\{e_{i_{t-1}+1},\ldots,e_{i_{t}}\\}$ if necessary. In particular, for
$t=r-1$, the assumption that $i_{r-1}=n=k\in\mathrm{supp}({a_{r}})$ gives the
result.

  4. (v)

Suppose for a contradiction that some $\ell\in\mathrm{supp}({a_{r}})$ lies in
the support of more than one subspace in $C$. If $r=3$, then
$\ell\in{\mathrm{supp}({a_{1}})\cap\mathrm{supp}({a_{2}})}$ and we set $t:=2$,
and if $r>3$, then (ii) implies that $\ell\in\mathrm{supp}({a_{t}})$ for some
$t\in\\{2,\ldots,r-2\\}$. Moreover, $\ell\neq 1$, since
$1\not\in\mathrm{supp}({a_{2}})$ by (iii), and
$1\not\in\mathrm{supp}({a_{u}})$ for $u\in\\{3,\ldots,r-2\\}$ by (i)–(ii).
Furthermore, (i) shows that $\ell\neq i_{r-1}=n$.

Suppose first that $\alpha_{\ell}=\beta_{\ell}\;(\neq 0)$. Since the supports
of $a_{t},a_{t+1},\ldots,a_{r-1}$ consecutively overlap, Lemma 2.4(i) shows
that $g_{\ell}=g_{n}$ for each $g\in D_{(a_{t},\ldots,a_{r-1})}$. Since
$\alpha_{n}\neq\beta_{n}$, no such $g$ maps $a_{r}$ to $b_{r}$, contradicting
the fact that $A{\underset{D,r-1}{\sim}}B$. Hence
$\alpha_{\ell}\neq\beta_{\ell}$. However, each $g\in D_{a_{1}}$ satisfies
$g_{1}=g_{\ell}$ if $r=3$, as does each $g\in D_{(a_{1},\ldots,a_{t})}$ if
$r>3$. Again, no such matrix $g$ maps $a_{r}$ to $b_{r}$, a contradiction. ∎

Recall that $G$ denotes $\mathrm{GL}_{n}(\mathbb{F})$, with
$n,|\mathbb{F}|\geq 3$. Our next result is a key ingredient in the proof that
$\mathrm{RC}(G,\Omega)$ is at most $n+2$.

######  Lemma 2.9.

Let $r\geq 2$, and let $A,B\in\overline{\Delta}^{\,r}$ be such that
$A{\underset{D,r-1}{\sim}}B$ and $B\notin A^{D}$. Then there exists a subset
$\Gamma$ of $\Delta$ of size $n+2-r$ such that $B\notin A^{G_{(\Gamma)}}$.

###### Proof.

If $r=2$, then set $\Gamma=\Delta$. Since $G_{(\Gamma)}=D$ and $B\notin
A^{D}$, we are done. Assume therefore that $r\geq 3$. We will suppose for a
contradiction that $n$ is the smallest dimension for which the present lemma
does not hold, for this value of $r$. Since $A{\underset{D,r-1}{\sim}}B$, we
may also assume that $(a_{1},\ldots,a_{r-1})=(b_{1},\ldots,b_{r-1})$. Let
$C=\\{a_{1},\ldots,a_{r-1}\\}$. As $B\notin A^{D}$, no element of $D_{(C)}$
maps $a_{r}$ to $b_{r}$. Therefore, $B\notin A^{G_{(\Gamma)}}$ for a given
subset $\Gamma$ of $\Delta$ if and only if no element of $G_{(\Gamma\cup C)}$
maps $a_{r}$ to $b_{r}$. We split the remainder of the proof into two cases,
depending on whether or not $|\mathrm{supp}({C})|=n$.

Case $\mathbf{|\mathrm{supp}({C})|<n}$: Let $\Delta_{C}:=\\{\langle
e_{j}\rangle\mid j\in\mathrm{supp}({C})\\}$, let $L$ be the subspace
$\langle\Delta_{C}\rangle$ of $V$, and let $a_{\ell}$ and $b_{\ell}$ be the
projections onto $L$ of $a_{r}$ and $b_{r}$, respectively. Lemma 2.4(iii)
shows that the diagonal entries corresponding to
$\\{1,\ldots,n\\}\setminus\mathrm{supp}({C})$ of elements of $D_{(C)}$ can
take any multiset of nonzero values. Since no element of $D_{(C)}$ maps
$a_{r}$ to $b_{r}$, it follows that there is no matrix in $D_{(C)}$ whose
restriction to $L$ maps $a_{\ell}$ to $b_{\ell}$. By the minimality of $n$,
there exists a subset $\Gamma_{C}$ of $\Delta_{C}$ of size $|\Delta_{C}|+2-r$
such that no element of $\mathrm{GL}(L)_{(\Gamma_{C}\cup C)}$ maps $a_{\ell}$
to $b_{\ell}$. Setting $\Gamma$ to be
$\Gamma_{C}\cup(\Delta\setminus\Delta_{C})$, so that $|\Gamma|=n+2-r$, we
observe that no element of $G_{(\Gamma\cup C)}$ maps $a_{r}$ to $b_{r}$. This
is a contradiction, and so the lemma follows in this case.

Case $\mathbf{|\mathrm{supp}({C})|=n}$: In this case, Lemma 2.8 applies, so
with the notation of that lemma, let

$\Gamma:=\Delta\setminus\\{\langle e_{i_{1}}\rangle,\ldots,\langle
e_{i_{r-2}}\rangle\\}.$

Then $|\Gamma|=n+2-r$ and $\langle e_{1}\rangle,\langle
e_{n}\rangle\in\Gamma$, since $i_{1}\geq 2$ and $i_{r-1}=n$.

Let $g\in G_{(\Gamma\cup C)}$. To complete the proof, we will show that
$a_{r}^{g}=a_{r}\neq b_{r}$, by showing that $g|_{\mathrm{supp}({a_{r}})}$ is
scalar. We will first show that $g$ is lower triangular. It is clear that $g$
stabilises $\langle e_{1}\rangle\in\Gamma$. Suppose inductively that $g$
stabilises $\langle e_{1},e_{2},\ldots,e_{s}\rangle$ for some
$s\in\\{1,\ldots,n-1\\}$. If $\langle e_{s+1}\rangle\in\Gamma$, then $g$
stabilises $E_{s+1}:=\langle e_{1},e_{2},\ldots,e_{s}\rangle+\langle
e_{s+1}\rangle=\langle e_{1},e_{2},\ldots,e_{s+1}\rangle$. Otherwise,
$s+1=i_{t}$ for some $t\in\\{1,\ldots,r-2\\}$, and then Lemma 2.8(i) shows
that $\\{s+1\\}\subsetneq\mathrm{supp}({a_{t}})\subseteq\\{1,\ldots,s+1\\}$.
In this case, $g$ again stabilises $\langle
e_{1},e_{2},\ldots,e_{s}\rangle+a_{t}=E_{s+1}$. Hence by induction, $g$ is
lower triangular.

Now, let $\mathcal{I}:=\\{i_{1},\ldots,i_{r-1}\\}$, let $\mathcal{U}$ be the
set of integers that each lie in the support of a unique subspace in $C$, and
let $\mathcal{J}:=\mathcal{I}\cup\mathcal{U}$. We will show next that
$g|_{\mathcal{J}}$ is diagonal, by fixing $j\in\mathcal{J}$ and proving that
$g_{kj}=0$ whenever $k>j$. First, if $\langle e_{k}\rangle\in\Gamma$, then
$g_{kj}=0$, so $g_{nj}=0$. Hence we may also assume that
$k\in\mathcal{I}\setminus\\{i_{r-1}\\}$.

Suppose inductively that $g_{i_{u},j}=0$ for some $u\geq 2$ (the base case
here is $u=r-1$, so that $i_{u}=n$). We will show that if $i_{u-1}>j$, then
$g_{i_{u-1},j}=0$. By Lemma 2.8(iv), $i_{u-1},i_{u}\in\mathrm{supp}({a_{u}})$
and furthermore Lemma 2.8(i)–(ii) shows that
$\mathrm{supp}({a_{u}})\cap\mathcal{I}=\\{i_{u-1},i_{u}\\}$. Thus by the
previous paragraph and our inductive assumption, $g_{kj}=0$ for all
$k\in\mathrm{supp}({a_{u}})\setminus\\{j,i_{u-1}\\}$. In fact, Lemma
2.8(i)–(ii) shows that each integer in $\mathrm{supp}({a_{u}})$ less than
$i_{u-1}$ lies in $\mathrm{supp}({a_{u-1}})$. As $i_{u-1}>j\in\mathcal{J}$, we
deduce from the definition of $\mathcal{J}$ that
$j\notin\mathrm{supp}({a_{u}})$. Thus $g_{kj}=0$ for all
$k\in\mathrm{supp}({a_{u}})\setminus\\{i_{u-1}\\}$. As $g$ stabilises $a_{u}$,
we deduce that $g_{i_{u-1},j}=0$. Therefore, by induction, $g_{kj}=0$ for all
$k\neq j$ and so $g|_{\mathcal{J}}$ is diagonal.

Finally, we will show that $g|_{\mathcal{J}}$ is scalar. Let
$j,k\in\mathcal{J}\cap\mathrm{supp}({a_{t}})$ for some
$t\in\\{1,\ldots,r-1\\}$. As $g$ stabilises $a_{t}$, and as $g|_{\mathcal{J}}$
is diagonal, we deduce that

(5) $g_{jj}=g_{kk}.$

Now, by Lemma 2.8(iv),
$i_{t}\in\mathrm{supp}({a_{t}})\cap\mathrm{supp}({a_{t+1}})$ for each
$t\in\\{1,\ldots,r-2\\}$, so
$i_{t}\in\mathcal{J}\cap\mathrm{supp}({a_{t}})\cap\mathrm{supp}({a_{t+1}})$.
Thus starting from $t=1$ and proceeding by induction on $t$, it follows from
(5) that $g_{jj}=g_{kk}$ for all $j,k\in\mathcal{J}$, i.e. $g|_{\mathcal{J}}$
is a scalar. Since $\mathrm{supp}({a_{r}})\subseteq\mathcal{J}$ by Lemma
2.8(v), we deduce that $a_{r}^{g}=a_{r}\neq b_{r}$, as required. ∎

The following lemma is strengthening of Lemma 2.9 in the case $|\mathbb{F}|=3$
and $r=2$, in which the subset $\Gamma$ now has size $n+1-r=n-1$.

######  Lemma 2.10.

Suppose that $|\mathbb{F}|=3$, and let $A,B\in\overline{\Delta}^{\,2}$.
Suppose also that $A{\underset{D,1}{\sim}}B$ and $B\notin A^{D}$. Then there
exists a subset $\Gamma$ of $\Delta$ of size $n-1$ such that $B\notin
A^{G_{(\Gamma)}}$.

###### Proof.

Since $A{\underset{D,1}{\sim}}B$, without loss of generality $a_{1}=b_{1}$,
and there exists an element of $D$ mapping $a_{2}$ to $b_{2}$. Hence $a_{2}$
and $b_{2}$ have equal supports. Reordering the basis for $V$ if necessary, we
may also assume that $\mathrm{supp}({a_{1}})=\\{1,2,\ldots,m\\}$ for some
$m\geq 2$. Then by Lemma 2.4, the upper-left $m\times m$ submatrix of each
matrix in $D_{a_{1}}$ is a scalar, while the remaining diagonal entries can be
chosen independently. As $B\notin A^{D}$, no matrix in $D_{a_{1}}$ maps
$a_{2}$ to $b_{2}$. We may therefore assume (by reordering the basis vectors
in $\\{e_{1},\ldots,e_{m}\\}$ and/or swapping $A$ and $B$ if necessary) that
the projections of $a_{2}$ and $b_{2}$ onto $\langle e_{1},e_{2}\rangle$ are
$\langle e_{1}+e_{2}\rangle$ and $\langle e_{1}-e_{2}\rangle$, respectively.

Now, let $\Gamma:=\Delta\setminus\\{\langle e_{2}\rangle\\}$, let $g\in
G_{(\Gamma\cup\\{a_{1}\\})}$, and notice that $g$ is diagonal outside of the
second row. Write $a_{1}$ as $\langle\sum_{i=1}^{m}\alpha_{i}e_{i}\rangle$,
with $\alpha_{1}=1$ and $\alpha_{i}\neq 0$ for all $i\in\\{2,\ldots,m\\}$.
Since $a_{1}^{g}=a_{1}$ we deduce that without loss of generality the top left
$2\times 2$ submatrix of $g$ is

$\left(\begin{array}[]{cc}1&0\\\ g_{21}&1+\alpha_{2}g_{21}\end{array}\right).$

Let $v$ be the projection of $(e_{1}+e_{2})^{g}$ onto $\langle
e_{1},e_{2}\rangle$. Recall that $\alpha_{2}\neq 0$, and note that $g_{22}\neq
0$, since $g$ is invertible. Hence if $g_{21}=1$, then $\alpha_{2}=1$ and
$v=-e_{1}-e_{2}$; if $g_{21}=-1$, then $\alpha_{2}=-1$ and $v=-e_{2}$; and if
$g_{21}=0$, then $v=e_{1}+e_{2}$. Hence, in each case, $v$ does not span
$\langle e_{1}-e_{2}\rangle=b_{2}|_{\langle e_{1},e_{2}\rangle}$. Therefore
$a_{2}^{g}\neq b_{2}$, and hence $B\not\in A^{G_{(\Gamma)}}$. ∎

Although the next result holds for all $\mathbb{F}$, it will only be useful in
the case $|\mathbb{F}|=3$.

######  Proposition 2.11.

Let $X,Y\in\Omega^{n+1}$ such that $X{\underset{G,n}{\sim}}Y$, and suppose
that $\langle X\rangle=V$. Then $Y\in X^{G}$.

###### Proof.

As $\mathrm{dim}(\langle X\rangle)=n$, we may assume by Lemma 2.1 that
$x_{i}=y_{i}=\langle e_{i}\rangle$ for $i\in\\{1,\ldots,n\\}$. Let
$S:=\mathrm{supp}({x_{n+1}})$ and $T:=\mathrm{supp}({y_{n+1}})$. We will show
that $S=T$; it will then follow that there exists an element of
$D=G_{(\Delta)}$ mapping $x_{n+1}$ to $y_{n+1}$, and so $Y\in X^{G}$.

If $S=\\{1,\ldots,n\\}=T$, then we are done. Otherwise, exchanging $X$ and $Y$
if necessary (note that $\langle Y\rangle=V$), we may assume that there exists
an element $t\in\\{1,\ldots,n\\}\setminus S$. Let
$\Gamma:=\Delta\setminus\\{\langle e_{t}\rangle\\}$. Then since
$X{\underset{G,n}{\sim}}Y$, there exists an element of $G_{(\Gamma)}$ mapping
$x_{n+1}$ to $y_{n+1}$. As $G_{(\Gamma)}$ stabilises each subspace $\langle
e_{i}\rangle$ with $i\in S$, it follows that $S=T$, as required. ∎

We are now able to prove this section’s main theorem.

######  Theorem 2.12.

Suppose that $n$ and $|\mathbb{F}|$ are at least 3. Then
$\mathrm{RC}(\mathrm{GL}_{n}(\mathbb{F}),\Omega)$ is at most $n+2$. Moreover,
$\mathrm{RC}(\mathrm{GL}_{n}(3),\Omega)\leq n$.

###### Proof.

Let $k\in\\{n,n+1,n+2\\}$, with $k=n+2$ if $|\mathbb{F}|>3$. Additionally, let
$X,Y\in\Omega^{u}$ for some $u>k$, such that $X{\underset{G,k}{\sim}}Y$. It
suffices to prove that $Y\in X^{G}$. Suppose, for a contradiction, that $n$ is
the minimal dimension for which the theorem does not hold (for a fixed
$\mathbb{F}$), and that $Y\notin X^{G}$. Then for each
$m\in\\{2,\ldots,n-1\\}$, using Proposition 1.2(i) in the case $m=2$, we
obtain
$\mathrm{RC}(\mathrm{GL}_{m}(\mathbb{F}),\mathcal{PG}_{1}(\mathbb{F}^{m}))<k$.
Since $Y\notin X^{G}$, Lemma 2.2 yields $\langle X\rangle=V$. Hence by Lemma
2.1, we may assume without loss of generality111If the basis vectors for $V$
are reordered, as required by several of this section’s earlier proofs, then
we can reorder the subspaces in $(x_{1},\ldots,x_{n})$ and
$(y_{1},\ldots,y_{n})$ in the same way to preserve this equality. that
$x_{i}=y_{i}=\langle e_{i}\rangle$ for $i\in\\{1,\ldots,n\\}$, and furthermore
that all subspaces in $X$ are distinct, so that
$x_{i},y_{i}\in\overline{\Delta}$ for each $i\geq n+1$.

We will first consider the case $k\geq n+1$. Since
$X{\underset{G,n+1}{\sim}}Y$, Lemma 2.3 yields
$\mathrm{supp}({x_{i}})=\mathrm{supp}({y_{i}})$ for all $i$. However, $Y\notin
X^{G}$. Hence there exists an integer $r\geq 2$ and subtuples $A$ of $X$ and
$B$ of $Y$, with $A,B\in\overline{\Delta}^{\,r}$, such that
$(x_{1},\ldots,x_{n},a_{1},\ldots,a_{r})$ and
$(x_{1},\ldots,x_{n},b_{1},\ldots,b_{r})$ are $(n+r-1)$-equivalent, but not
equivalent, under $G$. Equivalently, $A{\underset{D,r-1}{\sim}}B$ and $B\notin
A^{D}$.

If $k=n+2$, then by Lemma 2.9, there exists a set $\Gamma:=\\{\langle
e_{i_{1}}\rangle,\ldots,\langle e_{i_{k-r}}\rangle\\}$ such that $B\notin
A^{G_{(\Gamma)}}$. However, this means that the subtuples
$(x_{i_{1}},\ldots,x_{i_{k-r}},a_{1},\ldots,a_{r})$ and
$(x_{i_{1}},\ldots,x_{i_{k-r}},b_{1},\ldots,b_{r})$ are not equivalent under
$G$. This contradicts the assumption that $X{\underset{G,k}{\sim}}Y$. Hence in
this case, $Y\in X^{G}$, as required, so $\mathrm{RC}(G)\leq n+2$. If
$|\mathbb{F}|>3$, then we are done.

Therefore, assume for the rest of the proof that $|\mathbb{F}|=3$ and suppose
first that $k=n+1$. By the previous paragraph, $\mathrm{RC}(G)\leq n+2$.
Therefore, to prove that $\mathrm{RC}(G)\leq k$, it suffices to show that
$X{\underset{G,n+2}{\sim}}Y$ whenever $X{\underset{G,k}{\sim}}Y$. Thus by
replacing $X$ and $Y$ by suitable subtuples, if necessary, we may assume that
$u=n+2$. In this case, $r=2$, and by Lemma 2.10, there exists a subset
$\Gamma$ of $\Delta$ of size $k-r$ such that $B\notin A^{G_{(\Gamma)}}$.
Arguing as in the previous paragraph, this contradicts the assumption that
$X{\underset{G,k}{\sim}}Y$. Thus $\mathrm{RC}(G)\leq n+1$.

Finally, suppose that $k=n$. Since $\mathrm{RC}(G)\leq n+1$, we may assume
that $u=n+1$. However, since $X{\underset{G,n}{\sim}}Y$ and $\langle
X\rangle=V$, Proposition 2.11 shows that $Y\in X^{G}$. Therefore,
$\mathrm{RC}(G)\leq n$. ∎

##  3\. Action on 1-spaces: lower bounds

In this section, we again assume that $|\mathbb{F}|\geq 3$, and write
$\Omega:=\Omega_{1}=\mathcal{PG}_{1}(V)$. We drop the assumption that $n\geq
3$ and permit $n=2$. We shall now prove lower bounds for the relational
complexity of each group $H$ satisfying
${\mathrm{SL}_{n}(\mathbb{F})\trianglelefteq
H\leq\Gamma\mathrm{L}_{n}(\mathbb{F})}$, acting on $\Omega$.

For some results in this section, we will assume that
$\mathbb{F}=\mathbb{F}_{q}$ is finite, and when doing so we fix a primitive
element $\omega$, and assume that $q=p^{f}$ for $p$ prime. Additionally, we
will write
$\mathrm{P}\Gamma\mathrm{L}_{n}(q)/\mathrm{PSL}_{n}(q)=\langle\delta,\phi\rangle$,
with $\mathrm{PGL}_{n}(q)/\mathrm{PSL}_{n}(q)=\langle\delta\rangle$. Here, the
automorphism $\phi$ can be chosen to be induced by the automorphism of
$\mathrm{GL}_{n}(q)$ which raises each matrix entry to its $p$th power, and
with a slight abuse of notation, we will also write $\phi$ to denote this
automorphism of $\mathrm{GL}_{n}(q)$, and to denote a generator for
$\mathrm{Aut}(\mathbb{F}_{q})$. If $\mathbb{F}$ is an arbitrary field, then
the group $\Gamma\mathrm{L}_{n}(\mathbb{F})$ is still a semi-direct product of
$\mathrm{GL}_{n}(\mathbb{F})$ by $\mathrm{Aut}(\mathbb{F})$ (see, for example,
[13, Theorem 9.36]), but of course
$\mathrm{GL}_{n}(\mathbb{F})/\mathrm{SL}_{n}(\mathbb{F})$ and
$\mathrm{Aut}(\mathbb{F})$ need not be cyclic.

We let $Z:=Z(\mathrm{GL}_{n}(\mathbb{F}))$, and will write $I_{n}$ for the
$n\times n$ identity matrix, and $E_{ij}$ for the $n\times n$ matrix with $1$
in the $(i,j)\text{-th}$ position and $0$ elsewhere. We write $A\oplus B$ for
the block diagonal matrix with blocks $A$ and $B$.

Our first result is completely general and easy to prove, although we shall
later prove much tighter bounds for various special cases.

######  Theorem 3.1.

Let $\mathbb{F}$ be arbitrary, and let $H$ satisfy
$\mathrm{SL}_{n}(\mathbb{F})\trianglelefteq
H\leq\Gamma\mathrm{L}_{n}(\mathbb{F})$. Then $\mathrm{RC}(H,\Omega)\geq n$.

###### Proof.

Define $X,Y\in\Omega^{n}$ by $x_{i}=y_{i}=\langle e_{i}\rangle$ for
$i\in\\{1,\ldots,n-1\\}$, with $x_{n}=\langle\sum_{i=1}^{n}e_{i}\rangle$ and
$y_{n}=\langle\sum_{i=1}^{n-1}e_{i}\rangle$. Then $\mathrm{dim}(\langle
X\rangle)=n$ and $\mathrm{dim}(\langle Y\rangle)=n-1$, so no element of
$\Gamma\mathrm{L}_{n}(\mathbb{F})$ maps $X$ to $Y$. Hence $Y\not\in X^{H}$.

Now, let $h_{\ell}:=I_{n}-E_{\ell n}$ for each $\ell\in\\{1,\ldots,n-1\\}$,
and $h_{n}:=I_{n}$. Then $h_{\ell}\in\mathrm{SL}_{n}(\mathbb{F})\leq H$ and
$(X\setminus x_{\ell})^{h_{\ell}}=(Y\setminus y_{\ell})$, for each
$\ell\in\\{1,\ldots,n\\}$. Therefore $X{\underset{H,n-1}{\sim}}Y$, and so the
result follows. ∎

Our next two results focus on the special cases $n=2$ and $n=3$.

######  Lemma 3.2.

Assume that $q\geq 8$, and let $H$ satisfy $\mathrm{SL}_{2}(q)\trianglelefteq
H\leq\Gamma\mathrm{L}_{2}(q)$. Then $\mathrm{RC}(H)\geq 4$, except that
$\mathrm{RC}(\Sigma\mathrm{L}_{2}(9))=3$.

###### Proof.

The claim about $\Sigma\mathrm{L}_{2}(9)$ is an easy computation in GAP using
[3], so exclude this group from now on. We divide the proof into two cases.
For each, we define $X,Y\in\Omega^{4}$ such that $X{\underset{H,3}{\sim}}Y$
but $Y\not\in X^{H}$. In both cases, we set $(X\setminus x_{4})=(Y\setminus
y_{4})=(\langle e_{1}\rangle,\langle e_{2}\rangle,\langle
e_{1}+e_{2}\rangle)$.

Case (a): Either $q$ is even, or $H\not\leq\langle
Z,\Sigma\mathrm{L}_{2}(q)\rangle$. If $q$ is odd, then let
$\alpha\in\mathbb{F}_{p}^{\ast}\setminus\\{1\\}$, and otherwise let
$\alpha=\omega^{3}$, so that $\alpha$ is not in the orbit
$\omega^{\langle\phi\rangle}$. Then let $x_{4}=\langle e_{1}+\omega
e_{2}\rangle$ and $y_{4}=\langle e_{1}+\alpha e_{2}\rangle$.

The stabiliser in $H$ of $(X\setminus x_{4})=(Y\setminus y_{4})$ is contained
in $\langle Z,\phi\rangle$. As $\alpha\not\in\omega^{\langle\phi\rangle}$, no
element of this stabiliser maps $x_{4}$ to $y_{4}$, and so $Y\not\in X^{H}$.
On the other hand, for each $j\in\\{1,2,3,4\\}$, the matrix
$g_{j}\in\mathrm{GL}_{2}(q)$ given below maps $(X\setminus x_{j})$ to
$(Y\setminus y_{j})$.

$\begin{array}[]{c}g_{1}=\begin{pmatrix}1&(\alpha-\omega)(1-\omega)^{-1}\\\
0&1-(\alpha-\omega)(1-\omega)^{-1}\end{pmatrix},\quad
g_{2}=\begin{pmatrix}1-(\omega\alpha^{-1}-1)(\omega-1)^{-1}&0\\\
(\omega\alpha^{-1}-1)(\omega-1)^{-1}&1\end{pmatrix},\\\
g_{3}=\begin{pmatrix}1&0\\\ 0&\alpha\omega^{-1}\end{pmatrix},\quad
g_{4}=I_{2}.\end{array}$

If $q$ is even, then some scalar multiple of $g_{j}$ lies in $H$ for all $j$,
so $X{\underset{H,3}{\sim}}Y$ and we are done. If instead $q$ is odd, then our
assumption that $H\not\leq\langle Z,\Sigma\mathrm{L}_{2}(q)\rangle$ implies
that $H$ contains a scalar multiple of an element
$\mathrm{diag}(\omega,1)\phi^{i}$ for some $i\geq 0$, as
$\mathrm{diag}(\omega,1)$ induces the automorphism $\delta$ of
$\mathrm{PSL}_{2}(q)$. Hence for each $j$, there exists
$\phi^{i_{j}}\in\mathrm{Aut}(\mathbb{F}_{q})$ such that a scalar multiple of
$g_{j}\phi^{i_{j}}$ lies in $H$. Since $\alpha\in\mathbb{F}_{p}^{\ast}$, each
$\phi^{i_{j}}$ fixes $Y$, and thus $X{\underset{H,3}{\sim}}Y$.

Case (b): $q$ is odd and $H\leq\langle Z,\Sigma\mathrm{L}_{2}(q)\rangle$.
Since $H\neq\Sigma\mathrm{L}_{2}(9)$, and since Proposition 1.2(i) yields the
result when $H=\mathrm{SL}_{2}(9)$, we may assume that $q>9$. We generalise
Hudson’s [9, §5.4] proof that $\mathrm{RC}(\mathrm{SL}_{2}(q),\Omega)\geq 4$.
First, let $\mathcal{S}:=\mathbb{F}_{q}\setminus\\{0,1,-1\\}$ and
$\mathcal{T}:=\mathbb{F}_{q}\setminus\\{0,1\\}$, and for each
$\lambda\in\mathcal{S}$ define a map
$\theta_{\lambda}:\mathcal{T}\to\mathbb{F}_{q}$ by
$\mu\mapsto(1-\lambda^{2}\mu)(1-\mu)^{-1}$. We will show that there exist
elements $\lambda\in\mathcal{S}$ and $\tau\in\mathcal{T}$ satisfying the
following conditions:

(i) $(\tau)\theta_{\lambda}$ is a square in $\mathbb{F}_{q}^{*}$, and (ii) no
automorphism of $\mathbb{F}_{q}$ maps $\tau$ to $\lambda^{2}\tau$.

It is easy to see that for each $\lambda\in\mathcal{S}$, the image
$\mathrm{im}(\theta_{\lambda})=\mathbb{F}_{q}\setminus\\{1,\lambda^{2}\\}$, so
the map $\theta_{\lambda}$ is injective, and the preimage of any nonzero
square in $\mathrm{im}(\theta_{\lambda})$ lies in $\mathcal{T}$ and satisfies
Condition (i). Hence for each $\lambda\in\mathcal{S}$, there are precisely
$(q-1)/2-2$ choices for $\tau\in\mathcal{T}$ satisfying Condition (i).

Given $\lambda\in\mathcal{S}$, since $\lambda^{2}\neq 1$, Condition (ii) is
equivalent to requiring that $\lambda^{2}\tau\neq\tau^{p^{k}}$ for all
$k\in\\{1,\ldots,f-1\\}$, i.e. $\lambda^{2}\neq\tau^{p^{k}-1}$ for all $k$.
There are exactly $(q-3)/2=(q-1)/2-1$ distinct squares of elements of
$\mathcal{S}$, and precisely $(q-1)/(p-1)$ elements in $\mathbb{F}_{q}^{*}$
that are $(p-1)$-th powers. Hence if $p>3$, then there exists
$\lambda\in\mathcal{S}$ such that $\lambda^{2}$ is not a $(p-1)$-th power in
$\mathbb{F}_{q}$. Observe that then $\lambda^{2}$ is not a $(p^{k}-1)$-th
power for any $k$, and so this $\lambda$ and any corresponding $\tau$ from the
previous paragraph satisfy both conditions.

Suppose instead that $p=3$, and fix $\lambda\in\mathcal{S}$. The number of
elements $\tau\in\mathbb{F}_{3^{f}}^{*}$ not satisfying (ii), i.e. with
$\lambda^{2}=\tau^{3^{k}-1}$ for some $k\in\\{1,\ldots,f-1\\}$, is at most

$(3-1)+(3^{2}-1)+\cdots+(3^{f-1}-1)=(3+3^{2}+\cdots+3^{f-1})-(f-1).$

On the other hand, we established that the number of elements
$\tau\in\mathcal{T}$ satisfying (i) is equal to

$(3^{f}-1)/2-2=(3-1)(1+3+3^{2}+\cdots+3^{f-1})/2-2=(3+3^{2}+\cdots+3^{f-1})-1.$

Since $q>9$, and hence $f>2$, there again exists $\tau\in\mathcal{T}$
satisfying both conditions.

Finally, fix such a $\lambda\in\mathcal{S}$ and $\tau\in\mathcal{T}$, and
complete the definition of $X,Y\in\Omega^{4}$ by setting $x_{4}=\langle
e_{1}+\tau e_{2}\rangle$ and $y_{4}=\langle e_{1}+\lambda^{2}\tau
e_{2}\rangle$. The stabiliser in $H$ of $(X\setminus x_{4})=(Y\setminus
y_{4})$ is contained in $\langle Z,\phi\rangle$. By Condition (ii), no such
element maps $x_{4}$ to $y_{4}$, so $Y\notin X^{H}$. However, the proof of [9,
Theorem 5.4.6] shows that $X{\underset{\mathrm{SL}_{2}(q),3}{\sim}}Y$.
Therefore, $X{\underset{H,3}{\sim}}Y$, and the result follows. ∎

######  Lemma 3.3.

Assume that $\mathrm{PSL}_{3}(\mathbb{F})\neq\mathrm{PGL}_{3}(\mathbb{F})$,
and let $H$ satisfy $\mathrm{SL}_{3}(\mathbb{F})\trianglelefteq
H\leq\Gamma\mathrm{L}_{3}(\mathbb{F})$. If $\mathbb{F}$ is finite, or if
$H\leq\mathrm{GL}_{3}(\mathbb{F})$, then $\mathrm{RC}(H)\geq 5$.

###### Proof.

If $|\mathbb{F}|=4$, then we verify the result in GAP using [3], so assume
that $|\mathbb{F}|\geq 7$. If $\mathbb{F}$ is finite, then let
$\lambda:=\omega$, whilst if $\mathbb{F}$ is infinite, then let $\lambda$ be
any element of $\mathbb{F}^{\ast}$ of multiplicative order at least $3$.
Define $X,Y\in\Omega^{5}$ by $x_{i}=y_{i}=\langle e_{i}\rangle$ for
$i\in\\{1,2,3\\}$, $x_{4}=y_{4}=\langle e_{1}+e_{2}+e_{3}\rangle$,
$x_{5}=\langle e_{1}+\lambda e_{2}+\lambda^{2}e_{3}\rangle$, and
$y_{5}=\langle e_{1}+\lambda^{-1}e_{2}+\lambda^{-2}e_{3}\rangle$, so that
$x_{5}\neq y_{5}$.

We first show that $Y\not\in X^{H}$. The stabiliser in $H$ of $(X\setminus
x_{5})=(Y\setminus y_{5})$ lies in $H\cap\langle
Z,\mathrm{Aut}(\mathbb{F})\rangle$, so if $\mathbb{F}$ is infinite then we are
done. Assume therefore that $\mathbb{F}=\mathbb{F}_{q}$. If
$x_{5}^{\phi^{i}}=y_{5}$, then
$\lambda^{p^{i}}=\lambda^{-1}=\lambda^{p^{f}-1}$. Since
$i\in\\{0,\ldots,f-1\\}$ and $\lambda=\omega$, we deduce that
$(p,f,i)\in\\{(2,2,1),(3,1,0)\\}$, contradicting $q\geq 7$. Thus $Y\not\in
X^{H}$.

Next, for all $\mathbb{F}$, we show that $X{\underset{H,4}{\sim}}Y$. Let

$\begin{array}[]{c}g_{1}:=\begin{pmatrix}\lambda&\lambda+1&\lambda+\lambda^{-1}\\\
0&-1&0\\\ 0&0&-\lambda^{-1}\end{pmatrix},\quad
g_{2}:=\begin{pmatrix}-\lambda&0&0\\\ \lambda+1&1&1+\lambda^{-1}\\\
0&0&-\lambda^{-1}\end{pmatrix},\\\ \\\ g_{3}:=\begin{pmatrix}-\lambda&0&0\\\
0&-1&0\\\ \lambda+\lambda^{-1}&1+\lambda^{-1}&\lambda^{-1}\end{pmatrix},\quad
g_{4}:=\begin{pmatrix}\lambda^{2}&0&0\\\ 0&1&0\\\
0&0&\lambda^{-2}\end{pmatrix},\ \mbox{ and }\ \ g_{5}:=I_{3}.\end{array}$

Observe that $\det(g_{\ell})=1$ for each $\ell\in\\{1,\ldots,5\\}$, and so
$g_{\ell}\in\mathrm{SL}_{3}(\mathbb{F})\leq H$. It is also easy to check that
$(X\setminus x_{\ell})^{g_{\ell}}=(Y\setminus y_{\ell})$ for each $\ell$. Thus
$X{\underset{H,4}{\sim}}Y$, and so $\mathrm{RC}(H)\geq 5$. ∎

Our remaining results hold for all sufficiently large $n$. The first is
specific to $\mathrm{GL}_{n}(\mathbb{F})$.

######  Proposition 3.4.

If $n\geq 3$ and $|\mathbb{F}|\geq 4$, then
$\mathrm{RC}(\mathrm{GL}_{n}(\mathbb{F}),\Omega)\geq n+2$.

###### Proof.

Since $|\mathbb{F}|\geq 4$, there exists an element
$\lambda\in\mathbb{F}^{\ast}$ such that $\lambda\neq\lambda^{-1}$ (so
$\lambda\neq-1$). Define $X,Y\in\Omega^{n+2}$ by $x_{i}=y_{i}=\langle
e_{i}\rangle$ for $i\in\\{1,\ldots,n\\}$,
$x_{n+1}=y_{n+1}=\langle\sum_{i=1}^{n}e_{i}\rangle$, $x_{n+2}=\langle
e_{1}+\lambda e_{2}\rangle$ and $y_{n+2}=\langle
e_{1}+\lambda^{-1}e_{2}\rangle$.

The stabiliser in $\mathrm{GL}_{n}(\mathbb{F})$ of $(X\setminus
x_{n+2})=(Y\setminus y_{n+2})$ is the group of scalar matrices, so $Y\not\in
X^{\mathrm{GL}_{n}(\mathbb{F})}$. Additionally, it is easily verified that,
for each $j\in\\{1,\ldots,n+2\\}$, the matrix $g_{j}\in\mathrm{GL}_{n}(q)$
given below maps $(X\setminus x_{j})$ to $(Y\setminus y_{j})$.

$\begin{array}[]{c}g_{1}=\begin{pmatrix}\lambda&1+\lambda\\\
0&-1\end{pmatrix}\oplus\lambda I_{n-2},\quad g_{2}=\begin{pmatrix}-1&0\\\
1+\lambda^{-1}&\lambda^{-1}\end{pmatrix}\oplus\lambda^{-1}I_{n-2},\quad
g_{n+1}=\mathrm{diag}(\lambda,\lambda^{-1},\lambda,\ldots,\lambda),\\\
g_{j}=g_{n+1}+(\lambda-\lambda^{-1})E_{j2}\ \mbox{ for
$j\in\\{3,\ldots,n\\}$},\quad g_{n+2}=I_{n}.\end{array}$

Hence $X{\underset{\mathrm{GL}_{n}(\mathbb{F}),n+1}{\sim}}Y$, and so the
result follows. ∎

In the light of Proposition 3.4, the next result in particular bounds the
relational complexity of all remaining groups when
$\mathrm{PSL}_{n}(\mathbb{F})=\mathrm{PGL}_{n}(\mathbb{F})$.

######  Lemma 3.5.

Let $\mathbb{F}$ be arbitrary, assume that $n\geq 3$, and let $H$ satisfy
$\mathrm{GL}_{n}(\mathbb{F})\trianglelefteq
H\leq\Gamma\mathrm{L}_{n}(\mathbb{F})$ and $H\neq\mathrm{GL}_{n}(\mathbb{F})$.
Then $\mathrm{RC}(H)\geq n+3$.

###### Proof.

Since $\mathrm{GL}_{n}(\mathbb{F})$ is a proper subgroup of $H$, there exists
a nontrivial $\psi\in H\cap\mathrm{Aut}(\mathbb{F})$ and an element
$\lambda\in\mathbb{F}^{*}$ with $\lambda^{\psi}\neq\lambda$. We define
$X,Y\in\Omega^{n+3}$ by $x_{i}=y_{i}=\langle e_{i}\rangle$ for
$i\in\\{1,\ldots,n\\}$,

$x_{n+1}=y_{n+1}=\Big{\langle}\sum_{i=1}^{n}e_{i}\Big{\rangle},\
x_{n+2}=y_{n+2}=\langle e_{1}+e_{2}+\lambda e_{3}\rangle,\ x_{n+3}=\langle
e_{1}+\lambda e_{2}\rangle,\ y_{n+3}=\langle
e_{1}+\lambda^{\psi}e_{2}\rangle.$

We claim that $X{\underset{H,n+2}{\sim}}Y$, but $Y\not\in X^{H}$, from which
the result will follow.

The stabiliser in $H$ of $(x_{1},\ldots,x_{n+1})=(y_{1},\ldots,y_{n+1})$ is
contained in $\langle Z,\mathrm{Aut}(\mathbb{F})\rangle$. However, no element
of $\langle Z,\mathrm{Aut}(\mathbb{F})\rangle$ maps $(x_{n+2},x_{n+3})$ to
$(y_{n+2},y_{n+3})$, so $Y\not\in X^{H}$. The reader may verify that, for each
$j\in\\{1,\ldots,n+3\\}$, the element
$h_{j}\in\langle\mathrm{GL}_{n}(\mathbb{F}),\psi\rangle\leq H$ given below
maps $(X\setminus x_{j})$ to $(Y\setminus y_{j})$, where we define
$\tau:=(\lambda-1)^{-1}$ (notice that $\lambda\neq 1$).

$\begin{array}[]{c}h_{1}=\begin{pmatrix}1&-\tau(\lambda^{\psi}-\lambda)\\\
0&1+\tau(\lambda^{\psi}-\lambda)\end{pmatrix}\oplus I_{n-2},\quad
h_{2}=\begin{pmatrix}1-\tau(\lambda(\lambda^{-1})^{\psi}-1)&0\\\
\tau(\lambda(\lambda^{-1})^{\psi}-1)&1\end{pmatrix}\oplus I_{n-2},\\\
h_{3}=\left(\begin{pmatrix}1-\tau(\lambda(\lambda^{-1})^{\psi^{-1}}-1)&0&0\\\
0&1-\tau(\lambda(\lambda^{-1})^{\psi^{-1}}-1)&0\\\
\tau(\lambda(\lambda^{-1})^{\psi^{-1}}-1)&\tau(\lambda(\lambda^{-1})^{\psi^{-1}}-1)&1\end{pmatrix}\oplus
I_{n-3}\right)\psi,\\\
h_{j}=\left(\mathrm{diag}(1,1,\lambda^{-1}\lambda^{\psi^{-1}},1,\ldots,1)+(1-\lambda^{-1}\lambda^{\psi^{-1}})E_{j3}\right)\psi\
\mbox{ for $j\in\\{4,\ldots,n\\}$},\\\
h_{n+1}=\mathrm{diag}(1,1,\lambda^{-1}\lambda^{\psi^{-1}},1,\ldots,1)\psi,\quad
h_{n+2}=\psi,\quad h_{n+3}=I_{n}.\end{array}$

Hence $X{\underset{H,n+2}{\sim}}Y$, and the result follows. ∎

######  Lemma 3.6.

Let $\mathbb{F}$ be arbitrary, assume that $n\geq 4$, and let $H$ satisfy
$\mathrm{SL}_{n}(\mathbb{F})\trianglelefteq
H\leq\Gamma\mathrm{L}_{n}(\mathbb{F})$ and
$H\not\leq\mathrm{GL}_{n}(\mathbb{F})$. Then $\mathrm{RC}(H)\geq n+2$.

###### Proof.

Since $H\not\leq\mathrm{GL}_{n}(\mathbb{F})$, there exist elements $h\psi\in
H$ and $\lambda\in\mathbb{F}^{*}$ such that $h\in\mathrm{GL}_{n}(q)$,
$\psi\in\mathrm{Aut}(\mathbb{F}_{q})$, and $\lambda^{\psi}\neq\lambda$. Let
$X,Y\in\Omega^{n+2}$ be as in the proof of Lemma 3.5, but supported only on
the first $n-1$ basis vectors, so that $\langle e_{n}\rangle$ lies in neither
$X$ nor $Y$, and $x_{n}=y_{n}=\langle\sum_{i=1}^{n-1}e_{i}\rangle$. Just as in
that proof, one may check that $Y\not\in X^{H}$, but
$X{\underset{H,n+1}{\sim}}Y$. ∎

The next result applies, in particular, to all groups $H$ such that
$\mathrm{SL}_{n}(\mathbb{F})\trianglelefteq H$ and either
$H<\mathrm{GL}_{n}(\mathbb{F})$ or
$H\leq\Sigma\mathrm{L}_{n}(\mathbb{F})\neq\Gamma\mathrm{L}_{n}(\mathbb{F})$.
We write $\mathbb{F}^{\times n}$ for the subgroup of $\mathbb{F}^{\ast}$
consisting of $n$-th powers, which is the set of possible determinants of
scalar matrices in $\mathrm{GL}_{n}(\mathbb{F})$.

######  Proposition 3.7.

Assume that $n\geq 4$ and $|\mathbb{F}|\geq 3$, and let $H$ satisfy
$\mathrm{SL}_{n}(\mathbb{F})\trianglelefteq
H\leq\Gamma\mathrm{L}_{n}(\mathbb{F})$. Assume also that the set
$\\{\det(g)^{\psi}\mathbb{F}^{\times n}\mid g\psi\in H$ with
$g\in\mathrm{GL}_{n}(\mathbb{F}),\psi\in\mathrm{Aut}(\mathbb{F})\\}$ is a
proper subset of $\mathbb{F}^{\ast}/\mathbb{F}^{\times n}$. Then
$\mathrm{RC}(H)\geq 2n-2.$

###### Proof.

By assumption, there exists an $\alpha\in\mathbb{F}^{\ast}$ such that
$\alpha\neq\det(gz)^{\psi}$ for all $g\psi\in H$ and $z\in Z$. Define
$X,Y\in\Omega^{2n-2}$ as follows:

$\displaystyle X$ $\displaystyle:=\big{(}\langle e_{2}\rangle,\ldots,\langle
e_{n}\rangle,\langle e_{1}+e_{2}\rangle,\ldots,\langle
e_{1}+e_{n}\rangle\big{)};\text{ and}$ $\displaystyle Y$
$\displaystyle:=\big{(}\langle e_{2}\rangle,\ldots,\langle
e_{n}\rangle,\langle\alpha e_{1}+e_{2}\rangle,\ldots,\langle\alpha
e_{1}+e_{n}\rangle\big{)}.$

We show first that $Y\not\in X^{H}$, so suppose for a contradiction that there
exists $g\psi\in H$, with $g\in\mathrm{GL}_{n}(\mathbb{F})$ and
$\psi\in\mathrm{Aut}(\mathbb{F})$, such that $X^{g\psi}=Y$. As $g\psi$ fixes
$\langle e_{2}\rangle$ and $\langle e_{3}\rangle$, and maps $\langle
e_{1}+e_{2}\rangle$ and $\langle e_{1}+e_{3}\rangle$ to $\langle\alpha
e_{1}+e_{2}\rangle$ and $\langle\alpha e_{1}+e_{3}\rangle$, respectively, we
deduce that $e_{1}^{g\psi}\in\langle e_{1},e_{2}\rangle\cap\langle
e_{1},e_{3}\rangle=\langle e_{1}\rangle$. Therefore $\langle
e_{i}\rangle^{g\psi}=\langle e_{i}\rangle$ for each $i\in\\{1,\ldots,n\\}$,
and so $g$ is diagonal. Let $\mu:=\alpha^{\psi^{-1}}$. As $\langle
e_{1}+e_{i}\rangle^{g\psi}=\langle\alpha e_{1}+e_{i}\rangle$ for each
$i\in\\{2,\ldots,n\\}$, we deduce that $g=\mathrm{diag}(\mu,1,\ldots,1)z$ for
some $z\in Z$. Hence $(\det(gz^{-1}))^{\psi}=\mu^{\psi}=\alpha$, a
contradiction. Hence $Y\not\in X^{H}$.

Now, for each $i\in\\{2,\ldots,n\\}$, let
$h_{i}:=\mathrm{diag}(\alpha,1,\ldots,1,\alpha^{-1},1,\ldots,1)$, where the
$\alpha^{-1}$ appears in entry $i$. First, for $j\in\\{1,\ldots,n-1\\}$, let
$k:=j+1$ so that $x_{j}=y_{j}=\langle e_{k}\rangle$. It is easy to verify that
$h_{k}+(1-\alpha)E_{k1}$ has determinant $1$ and maps $(X\setminus x_{j})$ to
$(Y\setminus y_{j})$. Finally, for $j\in\\{n,\ldots,2n-2\\}$, let $k:=j+2-n$,
so that $x_{j}=\langle e_{1}+e_{k}\rangle$ and $y_{j}=\langle\alpha
e_{1}+e_{k}\rangle$. Then $h_{k}$ has determinant $1$ and maps $(X\setminus
x_{j})$ to $(Y\setminus y_{j})$. Therefore, $X{\underset{H,2n-3}{\sim}}Y$, and
so $\mathrm{RC}(H)\geq 2n-2$. ∎

###### Proof of Theorem A.

When $|\mathbb{F}|=2$, this result is clear from Theorem 1.1. For the
remaining fields $\mathbb{F}$, the fact that Part (i) gives an upper bound on
$\mathrm{RC}(\mathrm{PGL}_{n}(\mathbb{F}))$ is proved in Theorem 2.12, whilst
we prove that it gives a lower bound in Theorem 3.1 for $|\mathbb{F}|=3$ and
Proposition 3.4 for $|\mathbb{F}|\geq 4$. That Part (ii) gives upper bounds on
$\mathrm{RC}(\overline{H})$ is immediate from Theorem 1.2(ii) for $n=3$, and
from Theorem 2.7 for $n\geq 4$. Lemma 3.3 and Proposition 3.7 show that these
are also lower bounds. ∎

Recall that $\omega(k)$ denotes the number of distinct prime divisors of the
positive integer $k$.

######  Lemma 3.8 ([8, Lemma 3.1]).

Let $K\leq\mathrm{Sym}({\Gamma})$ be a finite group with normal subgroup $N$
such that $K/N$ is cyclic. Then
$\mathrm{H}(K,\Gamma)\leq\mathrm{H}(N,\Gamma)+\omega(|K/N|)$.

###### Proof of Theorem B.

For the upper bound in Part (i), we combine Proposition 1.2(i) with Lemma 3.8
to deduce that $\mathrm{H}(\overline{H},\Omega_{1})=3+\omega(e)$, so
$\mathrm{RC}(\overline{H},\Omega_{1})\leq 4+\omega(e)$. The lower bound (and
the case $\overline{H}=\mathrm{P}\Sigma\mathrm{L}_{2}(9)$) is Lemma 3.2.

For the upper bound in Part (ii), we similarly combine Proposition 1.2(ii)
with Lemma 3.8. As for the lower bound, first let $n=3$, and notice that in
this case $2n-2=4<n+2=5$. If $\overline{H}$ properly contains
$\mathrm{PGL}_{3}(q)$, then the lower bound of $6$ is proved in Lemma 3.5.
Otherwise, $\mathrm{PSL}_{3}(q)\neq\mathrm{PGL}_{3}(q)$, and so the lower
bound of $5$ follows from Lemma 3.3. Now assume that $n\geq 4$. The general
lower bound is Lemma 3.6, the bound of $n+3$ for groups properly containing
$\mathrm{PGL}_{n}(q)$ is Lemma 3.5, and the bound of $2n-2$ is Proposition
3.7. ∎

##  4\. Action on $m$-spaces for $m\geq 2$

In this section, we consider the action of $H$ on
$\Omega_{m}=\mathcal{PG}_{m}(V)$, where
$\mathrm{SL}_{n}(\mathbb{F})\trianglelefteq
H\leq\Gamma\mathrm{L}_{n}(\mathbb{F})$, as before, but now $2\leq
m\leq\frac{n}{2}$. The main work is to prove a lower bound on
$\mathrm{RC}(H,\Omega_{m})$, as the upper bound follows from existing
literature.

######  Proposition 4.1.

Let $\mathbb{F}$ be arbitrary, let $n\geq 2m\geq 4$, and let $H$ satisfy
$\mathrm{SL}_{n}(\mathbb{F})\trianglelefteq
H\leq\Gamma\mathrm{L}_{n}(\mathbb{F})$. Then $\mathrm{RC}(H,\Omega_{m})\geq
mn-m^{2}+1$.

###### Proof.

For each $i\in\\{1,\ldots,m\\}$ and $j\in\\{m+1,\ldots,n-1\\}$, let
$B_{i}:=\\{e_{1},e_{2},\ldots,e_{m}\\}\setminus\\{e_{i}\\}$, $U_{ij}:=\langle
B_{i},e_{j}\rangle=\langle
e_{1},\ldots,e_{i-1},e_{i+1},\ldots,e_{m},e_{j}\rangle$, $V_{i}:=\langle
B_{i},e_{i}+e_{n}\rangle$, and $W_{i}:=\langle B_{i},e_{n}\rangle$, so that
$U_{ij},V_{i},W_{i}\in\Omega_{m}$. Define $X,Y\in\Omega_{m}^{mn-m^{2}+1}$ as
follows:

$\displaystyle x_{mn-m^{2}+1}:=\langle
e_{1}+e_{2},\ldots,e_{1}+e_{m},\sum_{i=1}^{n}e_{i}\rangle;$ $\displaystyle
y_{mn-m^{2}+1}:=\langle
e_{1}+e_{2},\ldots,e_{1}+e_{m},-e_{1}+\sum_{i=m+1}^{n}e_{i}\rangle;$
$\displaystyle
X:=\Big{(}U_{1(m+1)},U_{1(m+2)},\ldots,U_{m(n-1)},V_{1},V_{2},\ldots,V_{m},x_{mn-m^{2}+1}\Big{)};\text{
and}$ $\displaystyle
Y:=\Big{(}U_{1(m+1)},U_{1(m+2)},\ldots,U_{m(n-1)},W_{1},W_{2},\ldots,W_{m},y_{mn-m^{2}+1}\Big{)}.$

We shall first show that $Y\not\in X^{\Gamma\mathrm{L}_{n}(\mathbb{F})}$, so
in particular $Y\not\in X^{H}$, and then that
$X{\underset{H,mn-m^{2}}{\sim}}Y$.

Assume for a contradiction that $Y\in X^{\Gamma\mathrm{L}_{n}(\mathbb{F})}$.
Since each subspace in $Y$ is spanned by vectors of the form
$\sum_{i=1}^{n}\lambda_{i}e_{i}$ with $\lambda_{i}\in\\{-1,0,1\\}$, it follows
that there exists $g\in\mathrm{GL}_{n}(\mathbb{F})$ with $X^{g}=Y$. For each
$i\in\\{1,\ldots,m\\}$, choose $k\in\\{1,\ldots,m\\}\setminus\\{i\\}$. Then

$\langle
e_{i}\rangle=\bigcap\limits_{\ell\in\\{1,\ldots,m\\}\setminus\\{i\\}}U_{\ell(m+1)}\cap
V_{k}=\bigcap\limits_{\ell\in\\{1,\ldots,m\\}\setminus\\{i\\}}U_{\ell(m+1)}\cap
W_{k},$

so $g$ fixes $\langle e_{i}\rangle$. Similarly, $g$ fixes $\langle
e_{j}\rangle=\bigcap\limits_{i=1}^{m}U_{ij}$ for each
$j\in\\{m+1,\ldots,n-1\\}$.

Therefore, there exist $\lambda_{1},\ldots,\lambda_{n}\in\mathbb{F}^{*}$ and
$\mu_{1},\ldots,\mu_{n-1}\in\mathbb{F}$ such that $g$ maps $e_{i}$ to
$\lambda_{i}e_{i}$ for all $i\in\\{1,\ldots,n-1\\}$, and maps $e_{n}$ to
$\lambda_{n}e_{n}+\sum_{i=1}^{n-1}\mu_{i}e_{i}$. It now follows that for each
$i\in\\{2,\ldots,m\\}$, the element $g$ maps $e_{1}+e_{i}\in x_{mn-m^{2}+1}$
to $\lambda_{1}e_{1}+\lambda_{i}e_{i}$, which must lie in $y_{mn-m^{2}+1}$,
and hence $\lambda_{i}=\lambda_{1}$. Similarly, $V_{i}^{g}=W_{i}$ for each
$i\in\\{1,\ldots,m\\}$, and so $W_{i}=\langle B_{i},e_{n}\rangle$ contains

$(e_{i}+e_{n})^{g}=\lambda_{1}e_{i}+\lambda_{n}e_{n}+\sum_{k=1}^{n-1}\mu_{k}e_{k}.$

Hence $\mu_{i}=-\lambda_{1}$, and $\mu_{j}=0$ for all
$j\in\\{m+1,\ldots,n-1\\}$. It now follows that $g$ maps
$\sum_{i=1}^{n}e_{i}\in x_{mn-m^{2}+1}$ to $\sum_{i=m+1}^{n}\lambda_{i}e_{i}$,
which is clearly not in $y_{mn-m^{2}+1}$, a contradiction. Thus $Y\not\in
X^{H}$.

We now show that $X{\underset{H,mn-m^{2}}{\sim}}Y$, by identifying an element
$g_{\ell}\in\mathrm{SL}_{n}(\mathbb{F})\leq H$ that maps $(X\setminus
x_{\ell})$ to $(Y\setminus y_{\ell})$, for each
$\ell\in\\{1,\ldots,mn-m^{2}+1\\}$. We divide the proof into three cases,
which together account for all values of $\ell$. To simplify our expressions,
let $z:=e_{1}+e_{2}+\ldots+e_{m}$, $\alpha_{1}:=-1$, and $\alpha_{r}:=1$ for
all $r\in\\{2,\ldots,m\\}$. In each case the element $g_{\ell}$ will be lower
unitriangular, and so will have determinant $1$.

Case (a): $\ell\in\\{1,\ldots,m(n-m-1)\\}$. Let $r\in\\{1,\ldots,m\\}$ and
$s\in\\{m+1,\ldots,n-1\\}$ be such that $\ell=(n-m-1)(r-1)+(s-m)$, so that
$x_{\ell}=y_{\ell}=U_{rs}$. Additionally, let $g_{\ell}$ fix $e_{i}$ for all
$i\notin\\{s,n\\}$, map $e_{s}$ to $e_{s}+\alpha_{r}e_{r}$, and map $e_{n}$ to
$e_{n}-z$. Then $g_{\ell}$ fixes $U_{ij}$ provided $(i,j)\neq(r,s)$, and maps
$e_{i}+e_{n}\in V_{i}$ to $e_{i}+e_{n}-z\in W_{i}$, and hence $V_{i}$ to
$W_{i}$, for all $i\in\\{1,\ldots m\\}$. Finally,

$\Big{(}\sum_{i=1}^{n}e_{i}\Big{)}^{g_{\ell}}=\alpha_{r}e_{r}+\sum_{i=m+1}^{n}e_{i}\in
y_{mn-m^{2}+1},$

where we have used the fact that
$e_{r}+\sum_{i=m+1}^{n}e_{i}=(e_{1}+e_{r})+(-e_{1}+\sum_{i=m+1}^{n}e_{i})$
when $r>1$. Hence $g_{\ell}$ maps $x_{mn-m^{2}+1}$ to $y_{mn-m^{2}+1}$, as
required.

Case (b): $\ell={m(n-m-1)+r}$, where $r\in\\{1,\ldots,m\\}$. Here,
$x_{\ell}=V_{r}$ and $y_{\ell}=W_{r}$. Let $g_{\ell}$ fix $e_{i}$ for each
$i\in\\{1,\ldots,n-1\\}$ and map $e_{n}$ to $\alpha_{r}e_{r}+e_{n}-z$. Then
$g_{\ell}$ fixes $U_{ij}$ for all $i$ and $j$, and maps $e_{i}+e_{n}\in V_{i}$
to $e_{i}+\alpha_{r}e_{r}+e_{n}-z\in W_{i}$, and hence $V_{i}$ to $W_{i}$, for
all $i\in\\{1,\ldots,m\\}\setminus\\{r\\}$. Finally,

$\Big{(}\sum_{i=1}^{n}e_{i}\Big{)}^{g_{\ell}}=\alpha_{r}e_{r}+\sum_{i=m+1}^{n}e_{i}\in
y_{mn-m^{2}+1},$

as in Case (a).

Case (c): $\ell={mn-m^{2}+1}$. Let $g_{\ell}$ fix $e_{i}$ for each
$i\in\\{1,\ldots,n-1\\}$, and map $e_{n}$ to $e_{n}-z$. Then $g$ fixes
$U_{ij}$ for all $i$ and $j$, and maps $e_{i}+e_{n}\in V_{i}$ to
$e_{i}+e_{n}-z\in W_{i}$ for all $i$, as required. ∎

The _irredundant base size_ $\mathrm{I}(K,\Gamma)$ of a group $K$ acting
faithfully on a set $\Gamma$ is the largest size of a tuple
$(\alpha_{1},\ldots,\alpha_{k})$ of elements of $\Gamma$ such that
$K>K_{\alpha_{1}}>K_{(\alpha_{1},\alpha_{2})}>\cdots>K_{(\alpha_{1},\ldots,\alpha_{k})}=1$,
with all inclusions strict. It is clear that $\mathrm{I}(K,\Gamma)$ is bounded
below by the height $\mathrm{H}(K,\Gamma)$, which we recall (from §1) is
bounded below by $\mathrm{RC}(K,\Gamma)-1$.

###### Proof of Theorem C.

In [10, Thm 3.1], it is proved that
$\mathrm{I}(\mathrm{PGL}_{n}(\mathbb{F}),\Omega_{m})\leq(m+1)n-2m+1$. Since
the irredundant base size of a subgroup is at most the irredundant base size
of an overgroup, and the height is at most the irredundant base size, we
deduce that $\mathrm{H}(\overline{H},\Omega_{m})\leq(m+1)n-2m+1$ for all
$\overline{H}\leq\mathrm{PGL}_{n}(\mathbb{F})$. From Lemma 3.8, we then see
that for all $\overline{H}$ as in the statement,
$\mathrm{H}(\overline{H},\Omega_{m})\leq(m+1)n-2m+1+\omega(e)$, and hence the
upper bound follows. The lower bound is immediate from Proposition 4.1, so the
proof is complete. ∎

Acknowledgments The authors would like to thank the Isaac Newton Institute for
Mathematical Sciences for support and hospitality during the programme
“Groups, representations and applications: new perspectives”, when work on
this paper was undertaken. This work was supported by EPSRC grant no.
EP/R014604/1, and also partially supported by a grant from the Simons
Foundation. The first author was supported by the University of St Andrews (St
Leonard’s International Doctoral Fees Scholarship & School of Mathematics and
Statistics PhD Funding Scholarship), and by EPSRC grant no. EP/W522422/1. The
second author is funded by the Heilbronn Institute.
In order to meet institutional and research funder open access requirements,
any accepted manuscript arising shall be open access under a Creative Commons
Attribution (CC BY) reuse licence with zero embargo.

Competing interests The authors declare none.

## References

  * [1] G. Cherlin.  Sporadic homogeneous structures.  In The Gelfand Mathematical Seminars, 1996–1999, pages 15–48. Birkhäuser, Boston, MA, 2000.
  * [2] G. Cherlin.  On the relational complexity of a finite permutation group.  J. Algebraic Combin., 43(2):339–374, 2016.
  * [3] G. Cherlin and J. Wiscons.  RComp (GAP code), June 9, 2016.
https://webpages.csus.edu/wiscons/research/code/RComp.html.

  * [4] G.L. Cherlin, G.A. Martin, and D.H. Saracino.  Arities of permutation groups: wreath products and $k$-sets.  J. Combin. Theory Ser. A, 74(2):249–286, 1996.
  * [5] The GAP Group.  GAP – Groups, Algorithms, and Programming, Version 4.12.2, 2022\.
  * [6] N. Gill, M.W. Liebeck, and P. Spiga.  Cherlin’s conjecture for finite primitive binary permutation groups, volume 2302 of Lecture Notes in Mathematics.  Springer, Cham, 2022.
  * [7] N. Gill, B. Lodà, and P. Spiga.  On the height and relational complexity of a finite permutation group.  Nagoya Math. J., 246:372–411, 2022.
  * [8] S. Harper.  The maximal size of a minimal generating set.  Forum Math. Sigma, 11:Paper No. e70, 2023.
  * [9] S. Hudson.  Calculating the Height and Relational Complexity of the Primitive Actions of $PSL_{2}(q)$ and $PGL_{2}(q)$.  PhD thesis, University of South Wales, November 2022.
  * [10] V. Kelsey and C.M. Roney-Dougal.  On relational complexity and base size of finite primitive groups.  Pacific J. Math., 318:89–108, 2022.
  * [11] A.H. Lachlan.  On countable stable structures which are homogeneous for a finite relational language.  Israel J. Math., 49(1-3):69–153, 1984.
  * [12] B. Lodà.  The height and relational complexity of finite primitive permutation groups.  PhD thesis, University of South Wales, January 2020.
  * [13] J.J. Rotman.  An introduction to the theory of groups, volume 148 of Graduate Texts in Mathematics.  Springer-Verlag, New York, fourth edition, 1995.