1. Introduction
In this paper, we study a number of different statistics pertaining to primitive permutation groups. We are interested in understanding which families of primitive permutation groups exhibit large values for these various statistics.
From here on, let G be a finite primitive permutation group on a set
$\Omega $
of size
$t<\infty $
. The statistic of most interest to us is the relational complexity of a permutation group,
$\textrm{RC}(G)$
, a statistic that was first introduced in [Reference Cherlin, Martin and SaracinoCMS96]. We were motivated by a remark in the same paper in which the authors suggest that it should be possible to classify those primitive groups G for which
$\textrm{RC}(G)>\sqrt {t}$
. Our main result (more or less) yields this classification; indeed, it applies with the
$\sqrt {t}$
replaced by the asymptotically weaker
$9\log t+1$
(here, and everywhere, logarithms are base
$2$
).
In the course of our investigations, we were inspired by the following result of Liebeck [Reference LiebeckLie84] concerning the minimum base size,
$\textrm{b}(G)$
, of the permutation group G. The definition of this quantity is given below.
Theorem 1.1. Let G be a finite primitive group of degree t. Then, one of the following holds:
-
1. G is a subgroup of
$\mathop {\textrm{Sym}}(m) \wr \mathop {\textrm{Sym}}(r)$
containing
$(\mathop {\textrm{Alt}}(m))^r$
, where the action of
$\mathop {\textrm{Sym}}{(m)}$
is on k-subsets of
$\{ 1, \dots, m\}$
and the wreath product has the product action of degree
$t= \binom {m}{k} ^r$
; -
2.
$\textrm{b}(G) < 9 \log {t} $
.
Theorem 1.1 leads us to make the following definition.
Definition 1.2. The group G is a primitive large–base group if G is a subgroup of
$\mathop {\textrm{Sym}}(m) \wr \mathop {\textrm{Sym}}(r)$
containing
$(\mathop {\textrm{Alt}}(m))^r$
, where the action of
$\mathop {\textrm{Sym}}{(m)}$
is on k-subsets of
$\{ 1, \dots, m\}$
and the wreath product has the product action of degree
$t= \binom {m}{k} ^r$
.
In this paper, we prove two results which are variants of the main result of Theorem 1.1; in both, the family of primitive large–base groups appear in a similar way to Theorem 1.1, in that they exhibit exceptional behavior with respect to certain statistics. In order to state these results, we must first define the statistics of interest.Footnote 1
1.1 Definition of statistics
For
$\Lambda = \{\omega _{1},\dots,\omega _{k}\} \subseteq \Omega $
, we write
$G_{(\Lambda)}$
or
$G_{\omega _{1}, \omega _{2}, \dots, \omega _{k}}$
for the pointwise stabilizer. If
$G_{(\Lambda)} = \{1\}$
, then we say that
$\Lambda $
is a base. The size of a smallest possible base is known as the base size of G and is denoted
$\textrm{b}(G)$
.
We say that a base is a minimal base if no proper subset of it is a base. We denote the maximum size of a minimal base by
$\textrm{B}(G)$
.
Given an ordered sequence of elements of
$\Omega $
,
$[\omega _{1},\omega _{2},\dots, \omega _{k}]$
, we can study the associated stabilizer chain:
$$ \begin{align*} G \geq G_{\omega_{1}} \geq G_{\omega_{1}, \omega_{2}}\geq G_{\omega_{1}, \omega_{2}, \omega_{3}} \geq \dots \geq G_{\omega_{1}, \omega_{2}, \dots, \omega_{k}}. \end{align*} $$
If all the inclusions given above are strict, then the stabilizer chain is called irredundant. If, furthermore, the group
$G_{\omega _{1},\omega _{2},\dots, \omega _{k}}$
is trivial, then the sequence
$[\omega _{1},\omega _{2},\dots, \omega _{k}]$
is called an irredundant base. The size of the longest possible irredundant base is denoted
$\textrm{I}(G)$
. Note that an irredundant base is not a base (because it is an ordered sequence, not a set).
Finally, let
$\Lambda $
be any subset of
$\Omega $
. We say that
$\Lambda $
is an independent set if its pointwise stabilizer is not equal to the pointwise stabilizer of any proper subset of
$\Lambda $
. We define the height of G to be the maximum size of an independent set, and we denote this quantity
$\textrm{H}(G)$
.
There is a basic connection between the four statistics we have defined so far:
$$ \begin{align} \textrm{b}(G) \leq \textrm{B}(G) \leq \textrm{H}(G) \leq \textrm{I}(G) \leq \textrm{b}(G)\log t. \end{align} $$
The proof of (1.1) goes as follows: the first inequality is obvious. For the second, suppose that
$\Lambda =\{\omega _{1},\dots,\omega _{k}\}$
is a minimal base; then, observe that
$\Lambda $
is also an independent set. For the third, suppose that
$\Lambda =\{\omega _{1},\dots,\omega _{k}\}$
is an independent set; then, observe that the ordered list
$[\omega _{1},\dots, \omega _{k}]$
can be extended to form an irredundant base.
The fourth inequality has been attributed to Blaha [Reference BlahaBla92], who, in turn, describes it as an observation of Babai [Reference BabaiBab81]. Suppose that G has a base of size
$b=\textrm{b}(G)$
. Then, in particular,
$|G|\leq t^b$
. On the other hand, any irredundant base has size at most
$\log |G|$
. We conclude that
$\textrm{I}(G) \leq \log (t^b)$
, and the result follows.
We have one more statistic to define. To start, suppose that
$r,n\in \mathbb {N}$
with
$r\leq n$
. If
$I,J\in \Omega ^n$
, then we write
, and say that I is r-equivalent to J with respect to the action of G, if G contains elements that map every subtuple of size r in I to the corresponding subtuple in J, that is,
$$ \begin{align*} \text{for every } k_1, k_2, \dots, k_r\kern1.5pt{\in}\kern1.5pt\{ 1, \ldots, n\}\kern-1pt, \text{ there exists } h \in G \text{ with }I_{k_i}^h=J_{k_i}, \text{ for every }i \kern1.5pt{\in}\kern1.5pt\{ 1, \ldots, r\}\kern-1pt. \end{align*} $$
Here,
$I_k$
denotes the
$k^{\text {th}}$
element of tuple I and
$I^g$
denotes the image of I under the action of g. Note that n-equivalence simply requires the existence of an element of G mapping I to J.
The group G is said to be of relational complexity r if r is the smallest integer such that, for all
$n\in \mathbb {N}$
with
$n\geq r$
and for all n-tuples
$I, J \in \Omega ^n$
,
In this case, we write
$\textrm{RC}(G)=r$
. The fact that relational complexity is well defined takes a little proving. There is an equivalent definition of
$\textrm{RC}(G)$
in terms of relational structures:
$\textrm{RC}(G)$
is the least k for which G can be viewed as an automorphism group acting naturally on a homogeneous relational system whose relations are k-ary [Reference CherlinChe16].
The relationship between relational complexity and the statistics defined above is given by the following inequality (which is proved in Section 2):
$$ \begin{align} \textrm{RC}(G) \leq \textrm{H}(G) + 1. \end{align} $$
Note that in what follows, we may sometimes include the set on which we are acting in our statistical notation, if this set is in any doubt. So, for instance,
$\textrm{H}(H)$
and
$\textrm{H}(H,\Delta)$
both mean the height of the permutation group H on a set
$\Delta $
.
1.2. Main results
Our first main result is a Liebeck-type result for height.
Theorem 1.3. Let G be a finite primitive group of degree t. If G is not a primitive large–base group, then
$$ \begin{align*} \textrm{H}(G) <9 \log{t}. \end{align*} $$
Equation (1.2) immediately yields the following corollary.
Corollary 1.4. Let G be a finite primitive group of degree t. If G is not a primitive large–base group, then
$$ \begin{align*} \textrm{RC}(G) < 9 \log{t}+1. \end{align*} $$
Corollary 1.4 yields the classification proposed in [Reference Cherlin, Martin and SaracinoCMS96] in a very strong form (since our bound is logarithmic in t, whereas the original suggestion was for
$\sqrt {t}$
). Note, however, that we do not assert that all of the primitive large–base groups genuinely violate the bound in Corollary 1.4. A precise analysis of the relational complexity of the primitive large–base groups was started in [Reference Cherlin, Martin and SaracinoCMS96], but, although a great deal of progress was made, much remains to be done. Note, however, that [Reference CherlinChe16, Theorem 2] implies that the family of primitive large–base groups contain an infinite number of groups violating the bound in Corollary 1.4 including, in particular, the alternating groups in their natural action. It is clear that the same is true with respect to Theorem 1.3: both
$\mathop {\textrm{Alt}}(t)$
and
$\mathop {\textrm{Sym}}(t)$
in their natural action violate the bound in Theorem 1.3 for t large enough. In future work, we will show that the same is true of
$\mathop {\textrm{Alt}}(t)$
and
$\mathop {\textrm{Sym}}(t)$
in their action on k-sets.
Equation (1.1) yields a second corollary.
Corollary 1.5. Let G be a finite primitive group of degree t. If G is not a primitive large–base group, then
$$ \begin{align*} \textrm{B}(G) < 9 \log{t}. \end{align*} $$
Of course, we could get yet another corollary by replacing
$\textrm{B}(G)$
by
$\textrm{b}(G)$
here, but this would only reprise Theorem 1.1. What, then, of
$\textrm{I}(G)$
? Our main result concerning this statistic is the following.
Theorem 1.6. Let G be a finite primitive group of degree t. Then, one of the following holds:
-
1. There exists an almost simple group A, with socle S, such that G is a subgroup of
$A \wr \mathop {\textrm{Sym}}(r)$
containing
$S^r$
, the action of A is one of the following:-
(a) the action of
$\mathop {\textrm{Sym}}{(m)}$
on k-subsets of
$\{ 1, \dots, m\}$
(so degree
$s=\binom {m}{k}$
); -
(b) the action of a classical group on a set of subspaces of the natural module, or on a set of pairs of subspaces;
and the action of the wreath product has the product action of degree
$t=s^r$
, where s is the degree of the action of A. -
-
2.
$\textrm{I}(G) < 7\log t$
.
The listed possible actions of A are a subset of the so-called standard actions of almost simple groups. In the second case, let V be a finite-dimensional vector space over
$\mathbb {F}_q$
; if
$S=\textrm{PSL}(V)$
, then such an action is on all subspaces of some fixed dimension k in V; if
$S=\text {Cl}(V)$
, one of the other classical groups defined on V, then such an action is either on all nondegenerate subspaces of some fixed dimension k in V, or on totally isotropic subspaces of some fixed dimension k and of a given type in V.
Theorem 1.6 is not as strong as we would like—we would like to eliminate the groups listed at item (1b), so that we end up with the same exceptional family as in the other main results. Indeed, we conjecture that something like Theorem 1.3 should hold for
$\textrm{I}(G)$
also.
Conjecture 1.7. There exists a constant
$C>0$
such that if G is a finite primitive group of degree t that is not a primitive large–base group, then
$$ \begin{align*} \textrm{I}(G) < C \log{t}. \end{align*} $$
1.3. Structure of the paper
Our proofs of Theorems 1.3 and 1.6 make use of the O’Nan–Scott theorem, which divides the class of primitive permutation groups into various families. There are various ways of stating the O’Nan–Scott theorem; in this paper, we make use of the division into eight types which is described in [Reference PraegerPra90].
After proving some useful background lemmas in Section 2, the work in Sections 3–5 when combined with the O’Nan–Scott theorem reduces the problem of proving Theorem 1.6 to a question about almost simple groups. This question is addressed in Section 6, where the proof of Theorem 1.6 is completed.
The work in Section 5, when combined with Theorem 1.6, reduces the problem of proving Theorem 1.3 to a question about almost simple groups. This question is addressed in Section 7, where the proof of Theorem 1.3 is completed.
2. Some background lemmas
In this section, we collect together a number of lemmas, mostly about height, which will be useful later. We also introduce one final statistic: for a group G, we define
$\ell (G)$
to be the length of the longest subgroup chain in G. It is clear that
$\ell (G)$
is greater than or equal to
$\textrm{I}(G)$
(and, hence, all the other statistics appearing in Equation (1.1)); it is equally clear that
$\ell (G)\leq \log |G|$
.
We start with a proof of (1.2).
Lemma 2.1.
$\textrm{RC}(G) \leq \textrm{H}(G) + 1$
.
Proof. Let
$h = \textrm{H}(G)$
and consider a pair
$(I,J)\in \Omega ^n$
such that
with
$r=h+1$
. We must show that
.
Observe that we can reorder the tuples without affecting their equivalence. Hence, without loss of generality, we can assume that
$$ \begin{align*} G_{I_1}> G_{I_1,I_2}> \dots > G_{I_1, I_2, \dots, I_{\ell}}, \end{align*} $$
for some
$\ell \leq h$
, and then this chain stabilizes, that is,
$$ \begin{align*} G_{I_1, \dots, I_{\ell}} = G_{I_1, \dots, I_{\ell+j}}, \end{align*} $$
for all
$1 \leq j \leq n-\ell $
. From the assumption of
${(h+1)}$
-equivalence, it follows that there exists an element
$g \in G$
such that
$I_i ^g = J_i$
, for all
$1 \leq i \leq \ell $
, and observe that the set of all such elements g forms a coset of
$G_{I_1, \dots, I_{\ell }}$
.
The assumption of
${(h+1)}$
-equivalence implies, moreover, that for all
$1 \leq j \leq n-\ell $
, there exists
$g_j \in G$
such that
$$ \begin{align*} \begin{cases} I_i ^{g_j} = J_i, \quad \text{for} \quad 1\leq i \leq \ell; \\ I_{\ell+j}^{g_j} = J_{\ell+j}. \end{cases} \end{align*} $$
The set of all such elements
$g_j$
forms a coset of
$G_{I_1, \dots, I_{\ell }, I_{\ell +j}}$
, which is, again, a coset of
$G_{I_1, \dots, I_{\ell }}$
. Indeed, since any coset of
$G_{I_1,\dots, I_{\ell }}$
is defined by the image of the points
$I_1,\dots, I_{\ell }$
under an element of the coset, we conclude that elements of the same coset of
$G_{I_1, \dots, I_{\ell }}$
map
$I_{\ell +j}$
to
$J_{\ell +j}$
, for all
$1 \leq j \leq n-\ell $
. In particular,
, as required.
The next two lemmas are little more than observations and require no proof.
Lemma 2.2. Let
$H \leq G$
and let
$\Lambda \subseteq \Omega $
be an independent set with respect to H. Then,
$\Lambda $
is an independent set with respect to G. In particular,
$\textrm{H}(H)\le \textrm{H}(G)$
.
Lemma 2.3. Let
$\Lambda = \{\alpha _1, \dots, \alpha _n\}$
. Then,
$\Lambda $
is independent if and only if
$$ \begin{align*} G_{(\Lambda)} \lneqq G_{(\Lambda \setminus \{\alpha_i\})}, \end{align*} $$
for all
$i=1, \dots, n$
.
Lemma 2.4. Let
$\Lambda \subseteq \Omega $
. Then, there exists
$\Gamma \subseteq \Lambda $
such that
$\Gamma $
is independent and
$G_{(\Lambda)}= G_{(\Gamma)}$
.
Proof. If
$\Lambda $
is an independent set, then the claim is trivially true. So, assume it is not. Then, there exists a proper subset
$\Lambda _0 \subset \Lambda $
such that
$G_{(\Lambda _0)}= G_{(\Lambda)}$
. If
$\Lambda _0$
is independent, then we are done; otherwise, consider
$\Lambda _0$
and repeat the same argument.
The next three results give information about the behavior of the statistics
$\textrm{H}(G)$
,
$\textrm{I}(G)$
, and
$\ell (G)$
when the permutation group G is a direct product.
Lemma 2.5. Let A and B be permutation groups on
$\Omega _1$
and
$\Omega _2$
, then
$$ \begin{align*} \textrm{H}(A\times B,\Omega_1\times \Omega_2)\le \textrm{H}(A,\Omega_1)+\textrm{H}(B,\Omega_2). \end{align*} $$
Proof. Let
$\pi _A:A\times B\to A$
be the projection onto A and observe that the kernel of
$\pi _A$
is
$\{1\}\times B$
. Let
$\Lambda =\{(\alpha _1,\beta _1),\ldots,(\alpha _k,\beta _k)\}$
be an independent set for
$A\times B$
. Set
$G:=A\times B$
, and, for every
$j\in \{1,\ldots,k\}$
, set
$G_j:=G_{(\alpha _1,\beta _1)}\cap \cdots \cap G_{(\alpha _j,\beta _j)}$
.
Now, consider the set
$\Lambda _1 = \{\alpha _1, \dots, \alpha _k\} \subseteq \Omega _1$
. Observe that, a priori, this set may not be independent. However, by Lemma 2.4, there exists a subset
$\{j_1, \dots, j_s\} \subseteq \{1, \dots, k\}$
such that the set
$\Delta _1 = \{\alpha _{j_1}, \dots, \alpha _{j_s} \}$
is independent and
$A_{(\Delta _1)}= A_{(\Lambda _1)}$
. After relabeling elements, we can assume
$\Delta _1= \{\alpha _1, \dots, \alpha _s\}$
and observe that
$A_{(\Delta _1)}= \pi _A(G_s)$
. In particular,
$s \leq \textrm{H}(A,\Omega _1)$
.
Now, let
$H:= G_s$
. It is clear that the set
$\{(\alpha _{s+1},\beta _{s+1}),\ldots,(\alpha _k,\beta _k)\}$
is independent with respect to H. Moreover, for all
$j \in \left \{s+1, \dots, k\right \}$
, we have
$$ \begin{align*} \pi_A \left(\bigcap_{i=s+1}^{k}{H_{(\alpha_i,\beta_i)}}\right)=\pi_A\left(\bigcap_{\substack{i=s+1 \\ i \neq j}}^{k}{H_{(\alpha_i,\beta_i)}}\right), \end{align*} $$
and this implies that
$$ \begin{align*} \bigcap_{i=s+1}^{k}{H_{(\alpha_i,\beta_i)}} \cap (\{1\}\times B) \lneqq \left(\bigcap_{\substack{i=s+1 \\ i \neq j}}^{k}{H_{(\alpha_i,\beta_i)}} \right)\cap (\{1\}\times B). \end{align*} $$
Therefore, by Lemma 2.3, the set
$\Delta _2=\{\beta _{s+1}, \dots, \beta _k\}$
is an independent set for
$B\cap H$
, and hence,
$k-s \leq \textrm{H}(B \cap H,\Omega _2)$
. As
$\textrm{H}(B \cap H,\Omega _2) \leq \textrm{H}(B,\Omega _2)$
, by Lemma 2.2, we have
$$ \begin{align*} k \leq \textrm{H}(A, \Omega_1)+ \textrm{H}(B, \Omega_2), \end{align*} $$
and we conclude that
$\textrm{H}(G, \Omega _1 \times \Omega _2) \leq \textrm{H}(A, \Omega _1)+ \textrm{H}(B, \Omega _2).$
Lemma 2.6. Let A and B be nonidentity permutation groups on
$\Omega _1$
and
$\Omega _2$
, then
$$ \begin{align*} \textrm{I}(A\times B,\Omega_1\times \Omega_2)= \textrm{I}(A,\Omega_1)+\textrm{I}(B,\Omega_2)-1. \end{align*} $$
Proof. Let
$[\alpha _1,\ldots,\alpha _k]$
and
$[\beta _1,\ldots,\beta _s]$
be irredundant bases for A and B acting on
$\Omega _1$
and on
$\Omega _2$
and with
$k:=\textrm{I}(A,\Omega _1)$
and
$s:=\textrm{I}(B,\Omega _2)$
. As A and B are not the identity,
$s,k\ge 1$
. Now, consider the ordered sequence
$$ \begin{align*} [(\alpha_1,\beta_1),(\alpha_1,\beta_2),\ldots,(\alpha_1,\beta_s),(\alpha_2,\beta_s),(\alpha_3,\beta_s),\ldots,(\alpha_k,\beta_s)]. \end{align*} $$
Using the fact that
$[\alpha _1,\ldots,\alpha _k]$
and
$[\beta _1,\ldots,\beta _s]$
are irredundant bases, it follows that this sequence of elements of
$\Omega _1\times \Omega _2$
is an irredundant base for
$A\times B$
acting on
$\Omega _1\times \Omega _2$
. Thus,
$$ \begin{align*} \textrm{I}(A\times B,\Omega_1\times\Omega_2)\ge s+k-1=\textrm{I}(A,\Omega_1)+\textrm{I}(B,\Omega_2)-1. \end{align*} $$
Now, let
$[(\alpha _1,\beta _1),\ldots,(\alpha _t,\beta _t)]$
be an irredundant base for
$A\times B$
acting on
$\Omega _1\times \Omega _2$
with
$t=\textrm{I}(A\times B,\Omega _1\times \Omega _2)$
. Let
$\mathcal {S}_A:=\{i\in \{2,\ldots,t\}\mid A_{\alpha _1,\ldots,\alpha _{i-1}}>A_{\alpha _1,\ldots,\alpha _{i-1},\alpha _{i}}\}$
and
$\mathcal {S}_B:=\{i\in \{2,\ldots,t\}\mid B_{\beta _1,\ldots,\beta _{i-1}}>B_{\beta _1,\ldots,\beta _{i-1},\beta _{i}}\}.$
As, for each
$i\in \{2,\ldots,t\}$
, we have
$$ \begin{align*} A_{\alpha_1,\ldots,\alpha_{i-1}} \times B_{\beta_1,\ldots,\beta_{i-1}}= \bigcap_{j=1}^{i-1}(A\times B)_{(\alpha_j,\beta_j)}>\bigcap_{j=1}^{i}(A\times B)_{(\alpha_j,\beta_j)}=A_{\alpha_1,\ldots,\alpha_{i}} \times B_{\beta_1,\ldots,\beta_{i}},\end{align*} $$
we deduce
$\mathcal {S}_A\cup \mathcal {S}_B=\{2,\ldots,t\}$
. Moreover, if
$\mathcal {S}_A=\{i_1,i_2,\ldots,i_r\}$
, then
$[\alpha _1,\alpha _{i_1},\alpha _{i_2},\ldots,\alpha _{i_r}]$
is an irredundant base for A acting on
$\Omega _1$
, and hence,
$\textrm{I}(A,\Omega _1)\ge |\mathcal {S}_A|+1$
. Similarly,
$\textrm{I}(B,\Omega _2)\ge |\mathcal {S}_B|+1$
. Therefore,
$$ \begin{align*} \textrm{I}(A,\Omega_1)+\textrm{I}(B,\Omega_2)&\ge |\mathcal{S}_A|+|\mathcal{S}_B|+2\ge|\mathcal{S}_{A}\cup\mathcal{S}_B|+2=|\{2,\ldots,t\}|+2=t+1\\ &=\textrm{I}(A\times B,\Omega_1\times\Omega_2)+1. \\[-40pt]\end{align*} $$
Lemma 2.7. Let A and B be groups. Then,
$\ell (A\times B)\leq \ell (A)+\ell (B)$
.
Proof. Let
$G=A\times B$
, and let
$$ \begin{align*} G_{\kappa}<G_{\kappa-1}<\cdots<G_1<G_0=G \end{align*} $$
be a chain of subgroups of length
$\kappa $
. Let
$\pi:G\to B$
be the projection onto B. Let
$$ \begin{align*} \mathcal{I}:=\{i\in\{0,\ldots,\kappa-1\}\mid \pi(G_i)>\pi(G_{i+1})\}, \end{align*} $$
and let
$s:=|\mathcal {I}|$
. We may write
$\mathcal {I}=\{i_1,\ldots,i_s\}$
with
$i_1<i_2<\cdots <i_s$
. Now,
$$ \begin{align*} \pi(G_{i_s+1})<\pi(G_{i_s})<\cdots<\pi(G_{i_2})<\pi(G_{i_1})\le B \end{align*} $$
is a strictly increasing chain of subgroups of B, and hence,
$s\leq \ell (B)$
.
Let j be an arbitrary element in
$\{1,\ldots,s-1\}$
. Define
$i_{s+1}=\kappa $
. By definition,
$$ \begin{align} \pi(G_{i_{j+1}})=\cdots=\pi(G_{i_j+3})=\pi(G_{i_j+2})=\pi(G_{i_j+1}). \end{align} $$
Since, by assumption, we have the strictly increasing sequence
$$ \begin{align*}G_{i_{j+1}}<\cdots<G_{i_j+3}<G_{i_j+2}<G_{i_j+1},\end{align*} $$
the first isomorphism theorem and (2.1) give
$$ \begin{align*}A\cap G_{i_{j+1}}<\cdots<A\cap G_{i_j+3}<A\cap G_{i_j+2}<A\cap G_{i_j+1}.\end{align*} $$
This increasing sequence consists of
$i_{j+1}-i_j$
subgroups.
The argument in the previous paragraph can be applied for every
$j\in \{1,\ldots,s-1\}$
, and hence, we obtain s chains of strictly increasing sequences of subgroups of A consisting of
$i_1-i_2,i_2-i_3,\ldots,i_{s-1}-i_s$
terms. By sticking these strictly increasing sequences together, we obtain a longer increasing sequence of subgroups of A of length
$\kappa $
. This longer increasing sequence is not necessarily strictly increasing; however, the only positions where an equality can occur are the positions where we attach two strictly increasing chains, that is, in the positions
$$ \begin{align*} A\cap G_{i_{j+1}}\le A\cap G_{i_{j+1}-1}. \end{align*} $$
Since the number of these positions is s and since
$s\le \ell (B)$
, we have a strictly increasing chain in A of length
$\kappa -\ell (B)$
. We conclude that
$\kappa -\ell (B)\leq \ell (A)$
, and the result follows.
Lemma 2.8. Let
$G \leq \mathop {\textrm{Sym}}(\Omega)$
and let
$N \unlhd G$
. Then,
$$ \begin{align*} \textrm{H}(G) \leq \textrm{H}(N) + \ell(G / N) \end{align*} $$
and
$$ \begin{align*}\textrm{I}(G)\le \textrm{I}(N)+\ell(G/N). \end{align*} $$
Proof. Let
$\{\omega _1,\ldots,\omega _k\}$
be an independent set for G in its action on
$\Omega $
.
Let us consider the action of N on
$\Omega $
. Observe that, a priori, the set
$\{\omega _1,\ldots,\omega _k\}$
is not independent for this action. However, by Lemma 2.4, there exists a subset
$J:= \{j_1, \dots, j_s\} \subseteq \{1, \dots, k\}$
, such that
$\{\omega _{j_1}, \dots, \omega _{j_s}\}$
is independent for N on
$\Omega $
and
$$ \begin{align*} N \cap \left(\bigcap_{i=1}^{s}{G_{\omega_{j_i}}}\right) = N \cap \left(\bigcap_{i=1}^{k}{G_{\omega_{i}}}\right). \end{align*} $$
After relabeling elements, we can assume
$ J=\{1, \dots, s\}.$
In particular, this yields that
$$ \begin{align*} s \leq \textrm{H}(N,\Omega). \end{align*} $$
Observe that, for all
$j \in \{s, \dots, k\}$
, we have
$$ \begin{align} N \cap \left(\bigcap_{i=1}^{s}{G_{\omega_{i}}}\right)= N \cap \left(\bigcap_{i=1}^{j}{G_{\omega_{i}}}\right). \end{align} $$
Let
$\pi \colon G \to G/N$
be the natural projection, and let
$I= \{s, \dots, k\}$
. Suppose that there exist
$i_1, i_2 \in I$
, with
$i_1 < i_2$
, such that
$$ \begin{align*} \pi \left( \bigcap_{j=1}^{i_1}{G_{\omega_j}} \right) = \pi \left( \bigcap_{j=1}^{i_2}{G_{\omega_j}} \right). \end{align*} $$
This equality, (2.2), and the first isomorphism theorem imply that
$$ \begin{align*} \bigcap_{j=1}^{i_1}{G_{\omega_j}}=\bigcap_{j=1}^{i_2}{G_{\omega_j}}. \end{align*} $$
Therefore,
$$ \begin{align*} \bigcap_{j=1}^{k}{G_{\omega_j}} = \bigcap_{j=1}^{i_2}{G_{\omega_j}} \cap \bigcap_{j=i_2+1}^{k}{G_{\omega_j}}= \bigcap_{j=1}^{i_1}{G_{\omega_j}} \cap \bigcap_{j=i_2+1}^{k}{G_{\omega_j}}. \end{align*} $$
Since
$\{1, \dots, i_1\} \cup \{i_2+1, \dots, k\} \subsetneq \{1, \dots, k\}$
, we have a contradiction with the independence of
$\{\omega _1, \dots, \omega _k\}$
for the action of G on
$\Omega $
. We conclude that, for
$i_1,i_2 \in I=\{s,\dots, k\}$
, with
$i_1 < i_2$
, we have
$$ \begin{align*} \pi \left( \bigcap_{j=1}^{i_1}{G_{\omega_j}} \right) < \pi \left( \bigcap_{j=1}^{i_2}{G_{\omega_j}} \right). \end{align*} $$
We conclude that
$\ell (G/N) \geq k-s = \textrm{H}(G) - \textrm{H}(N)$
, as required.
We now prove that
$\textrm{I}(G)\le \textrm{I}(N)+\ell (G/N)$
. Let
$[\omega _1,\ldots,\omega _s]$
be an irredundant base for G with
$s:=\textrm{I}(G)$
. Now, set
$G_0:=G$
and, for
$i\in \{1,\ldots,t\}$
,
$G_i:=\cap _{j=1}^iG_{\omega _j}$
. In particular, we have a strictly decreasing chain
$$ \begin{align*} G_0>G_1>\cdots>G_{s-1}>G_s=1. \end{align*} $$
Now, let
$\mathcal {S}_1:=\{i\in \{0,\ldots,s-1\}\mid G_iN>G_{i+1}N\}$
and
$\mathcal {S}_2:=\{i\in \{0,\ldots,s-1\}\mid G_i\cap N>G_{i+1}\cap N\}$
. We claim that
$\mathcal {S}_1\cup \mathcal {S}_2=\{0,\ldots,s-1\}$
. We argue by contradiction, and we let
$i\in \{0,\ldots,s-1\}\setminus (\mathcal {S}_1\cup \mathcal {S}_2)$
. This means that
$G_iN=G_{i+1}N$
and
$G_i\cap N=G_{i+1}\cap N$
. Let
$g\in G_i\subseteq G_{i+1}N$
. Then, there exist
$h\in G_{i+1}$
and
$n\in N$
with
$g=hn$
. Thus,
$h^{-1}g=n\in G_i\cap N=G_{i+1}\cap N$
. As
$h\in G_{i+1}$
, this yields
$g\in G_{i+1}$
. Therefore,
$G_{i}=G_{i+1}$
, which is clearly a contradiction.
We have
$|\mathcal {S}_1|\le \ell (G/N)$
. Now, let
$\mathcal {S}_2=\{i_1,i_2,\ldots,i_r\}$
with
$i_1<i_2<\cdots <i_r$
, and consider the sequence
$[\omega _{i_1+1},\omega _{i_2+1},\ldots,\omega _{i_r+1}]$
. We claim that this is an irredundant sequence for N, from which it follows that
$\textrm{I}(N)\ge r=|\mathcal {S}_2|$
. Suppose, by contradiction, that
$$ \begin{align*}N_{\omega_{i_1+1}}\cap \cdots \cap N_{\omega_{i_j+1}}=N_{\omega_{i_1+1}}\cap \cdots \cap N_{\omega_{i_j+1}}\cap N_{\omega_{i_{j+1}+1}}.\end{align*} $$
This gives
$$ \begin{align*}G_{\omega_{i_1+1}}\cap \cdots \cap G_{\omega_{i_j+1}}\cap N=G_{\omega_{i_1+1}}\cap \cdots \cap G_{\omega_{i_j+1}}\cap G_{\omega_{i_{j+1}+1}}\cap N.\end{align*} $$
We now intersect both sides of this equality with
$G_{i_{j+1}}=\bigcap _{u=1}^{i_{j+1}}G_{\omega _u}$
, and we obtain
$$ \begin{align*}G_{i_{j+1}}\cap N=(G_{i_{j+1}}\cap G_{\alpha_{i_{j+1}+1}})\cap N=G_{i_{j+1}+1}\cap N,\end{align*} $$
contradicting the fact that
$i_{j+1}\in \mathcal {S}_2$
.
Summing up,
$$ \begin{align*}\textrm{I}(N)+\ell(G/N)\ge |\mathcal{S}_1|+|\mathcal{S}_2|\ge |\mathcal{S}_1\cup\mathcal{S}_2|=|\{0,\ldots,s-1\}|=s=\textrm{I}(G).\\[-40pt]\end{align*} $$
3. Groups with a regular normal subgroup
In this section, we prove Theorem 1.6 under the supposition that G contains a regular normal subgroup. In fact, here, we use a general argument, which also holds in the case of imprimitive groups containing a regular normal subgroup. The primitive groups containing a regular normal subgroup are the groups of type HA, TW, HS, or HC in the language of [Reference PraegerPra90].
The main result of this section is the following.
Proposition 3.1. Let G be a permutation group on a finite set
$\Omega $
of size t. If G contains a regular normal subgroup, then
$$ \begin{align*} \textrm{I}(G) \le \log t+1. \end{align*} $$
Proof. Suppose that G has a regular normal subgroup N, and fix
$\omega _0 \in \Omega $
. The action of G on
$\Omega $
is permutation isomorphic to the affine action of G on N, where the group N acts on N via translations and the group
$G_{\omega _0}$
acts by group conjugation. In particular, if
$n,v\in N$
and
$x\in G_{\omega }$
, then
$$ \begin{align*}v^{xn}=v^x \cdot n = x^{-1}vx\cdot n.\end{align*} $$
In what follows, we identify
$\Omega $
with N. We let
$[\omega _1,\ldots,\omega _k]$
be an irredundant base, and we set
$H:=G_{\omega _0}$
. We may assume, without loss of generality, that
$\omega _1=1\in N$
. Now,
$H_{\omega _2}={C}_{{H}}{{()}}{\omega _2}$
fixes
$\omega _2$
, and hence, it fixes each element of
$\langle \omega _2\rangle $
. Similarly,
$$ \begin{align*}H_{\omega_2,\omega_3}={C}_{{H}}{{(\omega_2)}}\cap {C}_{{H}}{{(\omega_3)}}={C}_{{H}}{{(\langle \omega_2,\omega_3\rangle)}}.\end{align*} $$
Continuing in this way, we obtain a chain of subgroups of H,
$$ \begin{align} H&\ge H_{\omega_2}={C}_{{H}}{{(\omega_2)}}\ge H_{\omega_2,\omega_3}={C}_{{H}}{{(\langle \omega_2,\omega_3\rangle)}}\ge\cdots\\\nonumber &\cdots\ge H_{\omega_2,\omega_3,\ldots,\omega_k}={C}_{{H}}{{(\langle \omega_2,\omega_3,\cdots,\omega_k\rangle)}}, \end{align} $$
and a chain of subgroups of N,
$$ \begin{align} \langle 1\rangle&\le \langle \omega_2\rangle\le\cdots\le\langle \omega_2,\ldots,\omega_k\rangle\le N. \end{align} $$
Since
$[\omega _1,\ldots,\omega _k]$
is an irredundant base, the inequalities in (3.1) are strict inequalities. This yields that the inequalities in (3.2) must also be strict. In particular,
$$ \begin{align*}k\le \log|N|+1.\\[-40pt]\end{align*} $$
4. Diagonal action
In this section, we prove Theorem 1.6 under the supposition that G is a primitive group of type SD (see [Reference PraegerPra90]). Our main result is the following.
Proposition 4.1. Let G be a primitive permutation group on a finite set
$\Omega $
of size t. If G is of type SD, then
$$ \begin{align*} \textrm{I}(G) \le\log t. \end{align*} $$
We start by reviewing the structure of primitive groups of diagonal type; this will also help us to set some notation.
Let T be a nonabelian simple group, let m be a positive integer with
$m\ge 2$
, and let
$S:=T^m$
be the Cartesian product of m copies of T. We denote by
$D:=\{(t,\ldots,t)\mid t\in T\}$
the diagonal subgroup of S, and we set
$$ \begin{align*}\Omega:= [ D:S ]\end{align*} $$
the set of right cosets of D in S. Each element of
$\Omega $
has a distinguished coset representative, that is, an element whose first coordinate begins with a
$1$
. In other words,
$$ \begin{align*}D(t_1,t_2,\ldots,t_m)=D(1,t_1^{-1}t_2,\cdots,t_1^{-1}t_m).\end{align*} $$
In particular,
$\Omega $
is in one-to-one correspondence with the elements of
$T^{m-1}$
and hence
$$ \begin{align} \log |\Omega|=(m-1)\log |T|. \end{align} $$
Observe, first, that the elements of S act on
$\Omega $
by coset multiplication, that is, for every
$D(t_1,\ldots,t_m)\in \Omega $
and
$(x_1,\ldots,x_m)\in S$
, we have
$$ \begin{align*}D(t_1,\ldots,t_m)^{(x_1,\ldots,x_m)}=D(t_1x_1,\ldots,t_m x_m).\end{align*} $$
Observe, second, that the elements of
$\text {Aut}(T)$
act on
$\Omega $
componentwise, that is, for every
$D(t_1,\ldots,t_m)\in \Omega $
and
$\varphi \in \mathop {\text {Aut}}(T)$
, we have
$$ \begin{align*}D(t_1,\ldots,t_m)^{\varphi}=D(t_1^{\varphi},\ldots,t_m^{\varphi}).\end{align*} $$
Two comments are in order. First, this does indeed define an action of
$\mathop {\text {Aut}}(T)$
on
$\Omega $
, because D is
$\mathop {\text {Aut}}(T)$
-invariant. Second, the inner automorphisms of
$\mathop {\text {Aut}}(T)$
induce on
$\Omega $
permutations appearing in S. Let us denote by
$\iota _x$
the innerautomorphism of T defined by
$x\in T$
. Indeed, for every
$D(t_1,\ldots,t_m)\in \Omega $
and
$x\in T$
, we have
$$ \begin{align*} D(t_1,\ldots,t_m)^{\iota_x}&=D(t_1^x,\ldots,t_m^x)=D(x^{-1}t_1x,\ldots,x^{-1}t_m x)\\ &=D(t_1x,\ldots,t_m x)=D(t_1,\ldots,t_m)^{(x,\ldots,x)}. \end{align*} $$
Therefore,
$\iota _x$
and
$(x,\ldots,x)$
induce the same permutation on
$\Omega $
.
Observe, third, that
$\mathop {\textrm{Sym}}(m)$
acts on
$\Omega $
by permuting the coordinates. Again, this action is well defined, because D is
$\mathop {\textrm{Sym}}(m)$
-invariant. It is easy to see that
$\mathop {\text {Aut}}(T)$
and
$\mathop {\textrm{Sym}}(m)$
centralize each other and they normalize S. We define
$$ \begin{align*}W:=S(\mathop{\text{Aut}}(T)\times \mathop{\text{Sym}}(m))\cong T^{m}\cdot (\text{Out}(T)\times \mathop{\text{Sym}}(m)).\end{align*} $$
The group W acts primitively on
$\Omega $
and any subgroup G of W containing the socle S and projecting primitively on
$\mathop {\textrm{Sym}}(m)$
is said to be a primitive group of diagonal type. With the notation just established, we have the following.
Lemma 4.2. Let G be a primitive group of SD type with socle
$T^m$
, for some nonabelian simple group T and for some integer
$m\ge 2$
. Then,
$$ \begin{align*} \textrm{I}(G) \le \begin{cases} \frac{3m}{2} + \log |\mathop{\mathrm{Aut}}(T)|,&\text{when }m\ge 3,\\ \log|T|,&\text{when }m=2. \end{cases} \end{align*} $$
Proof. By Lemma 2.2, we can assume
$G=W$
. Set
$\omega:=D(1,\ldots,1)$
. A computation shows that
$$ \begin{align*}W_{\omega}=\mathop{\text{Aut}}(T)\times \mathop{\text{Sym}}(m).\end{align*} $$
Suppose first that
$m\ge 3$
. Lemma 2.7 implies that
$$ \begin{align*} \ell(W_{\omega})\leq \ell(\mathop{\text{Aut}}(T))+\ell(\mathop{\text{Sym}}(m)). \end{align*} $$
By [Reference Cameron, Solomon and TurullCST89], we know that
$\ell (\mathop {\textrm{Sym}}(m))\le \frac {3m}{2}$
. On the other hand,
$\ell (\mathop {\text {Aut}}(T))\leq \log |\mathop {\text {Aut}}(T)|-1$
, where the
$-1$
accounts for the fact that
$|T|$
is divisible by at least two distinct odd primes. We conclude that
$$ \begin{align} \textrm{I}(G) \leq \ell(W_{\omega})+1 \leq \frac{3m}{2}+\log |\mathop{\text{Aut}}(T)|. \end{align} $$
Suppose next that
$m=2$
. We identify
$\Omega $
with T. Set
$H:=T^2\cdot \mathop {\text {Out}}(T)$
, and observe that H has a regular normal subgroup and that
$|W:H|=2$
. Arguing as in the proof of Proposition 3.1, we deduce that
$$ \begin{align*}\textrm{I}(H)\le \omega(|T|)+1,\end{align*} $$
where
$\omega (|T|)$
is the number of prime divisors of
$|T|$
. Write
$|T|=2^v o$
, where
$v,o\in \mathbb {N}$
and o is odd. If
$o\ge 43$
, we have
$\log _3(o)\le \log (o)-2$
, and hence,
$\omega (|T|)\le \log (2^v)\log _3(o)\le \log |T|-2$
, and hence,
$\textrm{I}(H)\le \log |T|-1$
. If
$o<43$
, then T has a Sylow
$2$
-subgroup of index at most
$41$
in T, and hence, T admits a faithful primitive permutation representation of degree at most
$41$
. Thus, we have only a finite number of simple groups satisfying this property. A direct analysis yields that T is either
$\mathop {\textrm{Alt}}(5)$
or
$\textrm{PSL}_3(2)$
. When
$T=\textrm{PSL}_3(2)$
, we have
$\omega (|T|)=5<\log |T|-2$
, and hence, we obtain again
$\textrm{I}(H)\le \log |T|-1$
. Therefore, except when
$T=\mathop {\textrm{Alt}}(5)$
, as
$|G:H|=2$
, we have
$\textrm{I}(G)\le \textrm{I}(H)+1\le \log |T|$
. When
$T=\mathop {\textrm{Alt}}(5)$
, we have checked that
$\textrm{I}(G)=5\le \log |T|$
.
Proof Proof of Proposition 4.1
When
$m=2$
, the proof follows immediately from Lemma 4.2. Assume that
$m\ge 3$
. Lemma 4.2 and (4.1) imply that it is sufficient to prove that
$$ \begin{align*} \frac{3m}{2}+\log |\mathop{\text{Aut}}(T)| \leq (m-1)\log |T|. \end{align*} $$
We argue by contradiction, and we suppose that this inequality does not hold.
In [Reference QuickQui04, Lemma 2.2], it is shown that, for a nonabelian simple group T,
$$ \begin{align*} \frac{|T|}{|\mathop{\text{Out}}(T)|} \geq 30. \end{align*} $$
Now, for a centerless group, we have
$|\mathop {\text {Aut}}(T)| = |\mathop {\text {Out}}(T)||T|$
; hence,
$|\mathop {\text {Aut}}(T)| \leq \frac {1}{30}|T|^2$
. Thus,
$$ \begin{align*} \frac{3m}{2}+\log |\mathop{\text{Aut}}(T)|\leq \frac{3m}{2} +2 \log |T| - \log 30. \end{align*} $$
Therefore,
$$ \begin{align*}(m-1)\log|T|< \frac{3m}{2} +2 \log |T| - \log 30.\end{align*} $$
Rearranging the terms and dividing by
$\log |T|$
, we obtain
$$ \begin{align*}m-3<\frac{3m}{2\log |T|}-\frac{\log 30}{\log |T|}.\end{align*} $$
An easy computation (using
$|T|\ge 60$
) shows that this is never satisfied.
5. Product actions
In the breakdown described in [Reference PraegerPra90], there are three classes of groups left to deal with to prove Theorems 1.3 and 1.6. In this section, we deal with groups of type CD or PA. Note that our result for type CD will be definitive, whereas our result for type PA will involve input from groups of type AS—and these will be dealt with in the remainder of the paper.
Note, furthermore, that we will need a result for groups of type PA that is specific to
$\textrm{I}(G)$
, and another that is specific to
$\textrm{H}(G)$
. In all cases, we let H be a primitive nonregular group on
$\Delta $
of type AS or SD and let n be a positive integer with
$n\ge 2$
. We define
$W:=H\text {wr}\mathop {\textrm{Sym}}(m)$
endowed with its primitive product action on the Cartesian product
$\Omega:=\Delta ^m$
, that is, for every
$(h_1 \dots, h_{m})\sigma \in W$
and
$(\delta _1, \dots, \delta _{m}) \in \Omega $
, we have
$$ \begin{align*} \left(\delta_1, \dots, \delta_{m} \right)^{\left( h_1, \dots, h_{m}\right)\sigma} = \left(\delta_1^{h_1}, \dots, \delta_{m}^{h_{m}}\right)^{\sigma}= \left( \delta_{1^{\sigma^{-1}}}^{h_{1^{\sigma^{-1}}}}, \dots, \delta_{m^{\sigma^{-1}}}^{h_{m^{\sigma^{-1}}}} \right). \end{align*} $$
Let
$t:= |\Omega |= |\Delta |^{m}$
, and let
$\pi:W\to \mathop {\textrm{Sym}}(m)$
be the natural projection. Observe that the kernel of
$\pi $
is the base group of W, that is,
$H^m$
.
With the notation just established, the result we need is the following.
Proposition 5.1. Let G be a primitive permutation group on a finite set,
$\Omega =\Delta ^m$
, of size t.
-
1. If H is of type SD, then
$\textrm{I}(G) < 2 \log t$
. -
2. If H is of type AS and
$\textrm{I}(H,\Delta) < C\log |\Delta |$
, then
$\textrm{I}(G) < (C+\frac {3}{2\log |\Delta |})\log t$
. -
3. If H is of type AS and
$\textrm{H}(H,\Delta) < C\log |\Delta |$
, then
$\textrm{H}(G) < (C+\frac {3}{2\log |\Delta |})\log t$
.
Proof. We use, once again, the fact that a subgroup chain in
$\mathop {\textrm{Sym}}(m)$
has length at most
$\frac 32m$
, that is,
$\ell (\mathop {\textrm{Sym}}(m))\leq \frac 32m$
[Reference Cameron, Solomon and TurullCST89].
We start with (1): from Lemma 2.8, we have
$$ \begin{align*} \textrm{I}(W,\Omega)\le \textrm{I}(H^m,\Delta^m)+\ell(W/H^m)= \textrm{I}(H^m,\Delta^m)+\ell(\mathop{\text{Sym}}(m))\le \textrm{I}(H^m,\Delta^m)+\frac{3m}{2}. \end{align*} $$
Now, Lemma 2.6 yields
$\textrm{I}(G,\Omega)\le m\textrm{I}(H,\Delta)+3m/2$
. Thus,
$$ \begin{align} \textrm{I}(W,\Omega) \leq m\textrm{I}(H,\Delta) +\frac{3}{2}m. \end{align} $$
Let
$G \leq W$
be primitive. Then, we obtain that
$$ \begin{align*} \textrm{I}(G,\Omega)\le m \textrm{I}(H,\Delta)+\frac{3m}{2}. \end{align*} $$
If H is of type SD, then Proposition 4.1 implies that
$\textrm{I}(H, \Delta) \le \log |\Delta |$
, and hence,
$$ \begin{align*} \textrm{I}(G) &\le m \log|\Delta| + \frac{3}{2}m < 2m \log|\Delta|=2\log t, \end{align*} $$
where the second inequality follows with a computation using
$|\Delta |\ge 60$
.
For (2) and (3), recall that if H is of type AS, then G is of type PA. Now, for item (2), we know, by supposition, that
$\textrm{I}(H) <C \log t$
. This fact combined with (5.1) yields the result. For item (3), the argument is the same, provided all occurrences of
$\textrm{I}(X,Y)$
are replaced with
$\textrm{H}(X,Y)$
(for varying X and Y) and replacing Lemma 2.6 with Lemma 2.5.
6. Almost simple groups: Bounds for
$\text {I}(G)$
Here, we deal with groups of type AS in the language of [Reference PraegerPra90]; in other words, we study almost simple primitive permutation groups. The main result of this section is the following.
Proposition 6.1. Let G be a primitive almost simple permutation group on a set,
$\Omega $
, of size t. Either
$\textrm{I}(G)\le 6 \log t$
or else G is one of the groups listed at (1) in Theorem 1.6.
The proof of Proposition 6.1 splits into several parts. To start with, we use well-known results bounding
$\textrm{b}(G)$
to deal with the so-called non-standard actions. The terminology below follows [Reference BurnessBur07].
Definition 6.2. Let G be a classical group with socle
$G_0$
, and associated natural module V. A subgroup H of G not containing
$G_0$
is a subspace subgroup if for each maximal subgroup M of
$G_0$
containing
$H \cap G_0$
one of the following holds:
-
1. M is the stabilizer in
$G_0$
of a proper nonzero subspace U of V, where U is totally singular, nondegenerate, or, if
$G_0$
is orthogonal and
$p=2$
, a nonsingular
$1$
-space (U can be any subspace if
$G_0=\textrm{PSL}(V)$
). -
2.
$G_0= \textrm{Sp}_{2m}(q)$
,
$p=2$
, and
$M= \textrm{O}^{\pm }_{2m}(q)$
.
A subspace action of the classical group G is the action of G on the coset space
$\left [G:H \right ]$
, where H is a subspace subgroup of G.
Note that the definition above amounts precisely to this: a maximal subgroup of G is a subspace subgroup if it lies in any
$\mathcal {C}_1$
class, or is the even-characteristic symplectic case in the
$\mathcal {C}_8$
class. This definition requires that we follow [Reference Kleidman and LiebeckKL90] in labeling the classes
$\mathcal {C}_1$
–
$\mathcal {C}_8$
. A small extra collection of maximal subgroups arises when
$G_0=\textrm{Sp}_4(2^a)$
, and G contains a graph automorphism, or if
$G_0=\textrm{P}\Omega _8^+(q)$
and G contains a triality graph automorphism. We note that [Reference Kleidman and LiebeckKL90] explicitly exclude these cases.
Definition 6.3. A transitive action of G on a set
$\Omega $
is said to be standard if, up to equivalence of actions, one of the following holds:
-
1.
$G_0 = \mathop {\textrm{Alt}}(m)$
and
$\Omega $
is an orbit of subsets or uniform partitions of
$\left \{1, \dots, m \right \}$
. -
2. G is a classical group in a subspace action.
For an almost simple primitive permutation group in a nonstandard action, the base size is bounded by an absolute constant. This was conjectured by Cameron and Kantor ([Reference CameronCam92], [Reference Cameron and KantorCK97]) and then settled in the affirmative by Liebeck and Shalev in [Reference Liebeck and ShalevLS99, Theorem 1.3]. The constant was then made explicit in subsequent work [Reference Burness, Guralnick and SaxlBGS11], [Reference Burness, Liebeck and ShalevBLS09], [Reference Burness, O’Brien and WilsonBOW10], [Reference BurnessBur07]. The following theorem summarizes these results.
Theorem 6.4. Let G be a finite almost simple group in a primitive faithful nonstandard action. Then,
$\textrm{b}(G) \leq 7$
, with equality if and only if G is the Mathieu group
$\textrm{M}_{24}$
in its natural action of degree 24.
Theorem 6.4 and (1.1) immediately yield Proposition 6.1 for nonstandard actions.
Lemma 6.5. Let G be a finite almost simple permutation group on a set
$\Omega $
of size t, in a nonstandard action. Then,
$$ \begin{align*} \textrm{I}(G) \leq 6 \log t. \end{align*} $$
One can compute that
$\textrm{I}(M_{24})=8$
(where we consider the natural action of
$M_{24}$
on
$24$
points); hence, we have a constant 6 in the statement of Lemma 6.5 rather than 7.
6.1. Standard actions of
$A_n$
and
$S_n$
Let G be
$\mathop {\textrm{Sym}}(n)$
or
$\mathop {\textrm{Alt}}{(n)}$
. We must prove Theorem 1.6 for the action of G on partitions of n. Let
$n=ab$
for some positive integers
$a,b$
with
$a \geq 2$
and
$b \geq 2$
. We denote by
$\Omega _a^b$
the set of all uniform partitions of n, with a parts of size b. Let
$t = | \Omega _a^b |$
, then
$$ \begin{align*} t = \frac{(ab)!}{a! (b!)^a}. \end{align*} $$
We consider the action of G on
$\Omega _a^b$
. We have the following result.
Lemma 6.6. Let G be an almost simple group with socle
$\mathop {\textrm{Alt}}(n)$
acting on
$\Omega =\Omega _a^b$
. Then,
$$ \begin{align*} \textrm{I}(G) < 2 \log t. \end{align*} $$
Proof. By [Reference Guest, Morris, Praeger and SpigaGMPS15, Lemma 5.6], we know that if
$a \geq 2$
,
$b \geq 2$
, and
$n \geq 17$
, then
$$ \begin{align*} \frac{(ab)!}{(b!)^a(a!)} \geq 3^{ab/2}. \end{align*} $$
Hence,
$$ \begin{align} \log t \geq \frac{\log (3)}{2}ab. \end{align} $$
Once again, we use the fact that
$\ell (\mathop {\textrm{Sym}}(n))\leq \frac 32n=\frac 32ab$
. As
$3/2<\log (3)$
for
$n\geq 17$
, we have
$$ \begin{align*} \textrm{I}(G)\leq \ell(G) \leq \frac{3}{2}ab < \log(3)ab\le 2\log t, \end{align*} $$
and the result follows. If
$n<17$
, we check directly that
$\frac {3}{2} ab < 2 \log t$
, unless
$$ \begin{align*}(a,b)\in \{( 2, 3), ( 3, 2), ( 4, 2), ( 5, 2), ( 6, 2)\}.\end{align*} $$
For these remaining cases, we have computed explicitly the value of
$\mathop {\textrm{Sym}}(n)$
acting on partitions of
$\{1,\ldots,n\}$
in b parts of cardinality a, and we have verified that in each case
$\textrm{I}(G)<2\log t$
.
6.2 The symplectic/orthogonal case
In this section, we deal with the actions listed at item (2) of Definition 6.2. In particular, G is almost simple with socle
$G_0=\textrm{Sp}_{2m}(q)$
, q a power of
$2$
. Consulting [Reference Bray, Holt and Roney-DougalBHR13] and [Reference Kleidman and LiebeckKL90], it is clear that if H is a maximal subgroup of G not containing
$G_0$
, and
$H\cap G_0$
is a subgroup of
$M=\textrm{O}_{2m}^{\pm }(q)$
, then
$H\cap G_0=M$
. In light of this, the result that we need is the following.
Lemma 6.7. Let G be almost simple with socle
$G_0=\textrm{Sp}_{2m}(q)$
, q a power of
$2$
. Let H be a subgroup of G such that
$H\cap \textrm{Sp}_{2m}(q)=\textrm{O}_{2m}^{\pm }(q)$
, let
$\Omega $
be the set of cosets of H in G, and write
$t=|\Omega |$
. Then,
$$ \begin{align*} \textrm{I}(G,\Omega)<\frac{11}{3}\log t. \end{align*} $$
The treatment that follows is inspired by [Reference Dixon and MortimerDM96, Section 7.7], where the case of
$\textrm{Sp}_{2m}(2)$
is considered. Let e and m be positive integers, let
$q:=2^e$
, let
$\mathbb {F}_q$
be the finite field with q elements, and let
$V:=\mathbb {F}_q^{2m}$
be the
$2m$
-dimensional vector space of row vectors over
$\mathbb {F}_q$
. To start with, we adjust notation slightly, and assume that G is simple: let
$G:=\textrm{Sp}_{2m}(q)$
be the symplectic group defined by the symmetric matrix
$$ \begin{align*} f:=\begin{pmatrix} 0&I\\ I&0 \end{pmatrix}, \end{align*} $$
where
$0$
and I are the zero and identity
$m\times m$
-matrices, respectively. In particular, G is the group of invertible matrices preserving the bilinear form
$\varphi:V\times V\to \mathbb {F}_q$
defined by
$$ \begin{align*} \varphi(u,v):=ufv^{T}, \end{align*} $$
for every
$u,v\in V$
, that is,
$$ \begin{align*} G = \left\{g \in \text{GL}_{2m}(q) \mid gfg^{T}=f\right\}. \end{align*} $$
Note that the bilinear form
$\varphi $
is alternating, that is, for all
$u \in V$
, we have
$$ \begin{align} \varphi(u,u)=0. \end{align} $$
Moreover, since
$\mathbb {F}_q$
is of characteristic 2, the form
$\varphi $
is symmetric, that is, for all
$u,v \in V$
, we have
$$ \begin{align} \varphi(u,v)= \varphi(v,u). \end{align} $$
Now, we let
$\Omega $
be the set of quadratic forms
$\theta:V\to \mathbb {F}_q$
polarizing to
$\varphi $
. Recall that this means that
$\theta:V\to \mathbb {F}_q$
is a function satisfying
-
•
$\theta (u+v)-\theta (u)-\theta (v)=\varphi (u,v)$
, for every
$u,v\in V$
, and -
•
$\theta (cu)=c^2u$
, for every
$c\in \mathbb {F}_q$
and
$u\in V$
.
Next, consider the matrix
$$ \begin{align*} e:=\begin{pmatrix} 0&I\\ 0&0 \end{pmatrix} \end{align*} $$
and the quadratic form
$\theta _0:V\to \mathbb {F}_q$
defined by
$$ \begin{align*}\theta_0(u):=ueu^T,\end{align*} $$
for every
$u\in V$
. For every
$u,v\in V$
, we have
$$ \begin{align} \begin{array}{ll} \theta_0(u+v)-\theta_0(u)-\theta_0(v)&:=(u+v)e(u+v)^T-ueu^T-vev^T\\ &=ueu^T+vev^T+uev^T+veu^T-ueu^T-vev^T\\ &=uev^T+veu^T=uev^T+ue^Tv^T=u(e+e^T)v^T=ufv^T\\ &=\varphi(u,v). \end{array} \end{align} $$
In particular, θ
0 is a quadratic form whose polarisation is the symplectic form
$\varphi $
, and hence,
$\theta _0\in \Omega $
.
Let
$\theta \in \Omega $
and define
$\lambda:=\theta -\theta _0$
. We have
$$ \begin{align*} \lambda(u+v)=\,&\theta(u+v)-\theta_0(u+v)=\theta(u)+\theta(v)+\varphi(u,v)-\theta_0(u)-\theta_0(v)-\varphi(u,v)\\ =\,&\lambda(u)+\lambda(v),\\ \lambda(cu)=\,&\theta(cu)-\theta_0(cu)=c^2\theta(u)-c^2\theta_0(u)=c^2\lambda(u), \end{align*} $$
for every
$u,v\in V$
and for every
$c\in \mathbb {F}_q$
. Therefore, since
$\mathbb {F}_q$
is of characteristic
$2$
, the function
$\lambda:V\to \mathbb {F}_q$
is semilinear, and hence, there exists a unique
$b\in V$
such that
$\lambda (u)=(u\cdot b^T)^2$
, for every
$u\in V$
(see Lemma 7.3 for a precise statement). Since f is an invertible matrix, there exists a unique
$a\in V$
with
$b=af$
, and hence,
$$ \begin{align*} \lambda(u)=(ufa^T)^2=\varphi(u,a)^2, \end{align*} $$
for every
$u\in V$
. Summing up, we have shown that an arbitrary element of
$\Omega $
is of the form
$$ \begin{align*} u\mapsto \theta_0(u)+\varphi(u,a)^2, \end{align*} $$
where
$a\in V$
. We denote this element of
$\Omega $
simply by
$\theta _a$
. Thus,
$$ \begin{align} \theta_a(u)=\theta_0(u)+\varphi(u,a)^2,\quad\text{for every }u\in V. \end{align} $$
In particular, the elements of
$\Omega $
are parameterized by the vectors of V. Moreover, if
$\theta _{a}=\theta _{a'}$
, for some
$a, a' \in V$
, then
$\theta _{a}(u)=\theta _{a'}(u)$
, for every
$u \in V$
, and this implies
$\varphi (u, a)= \varphi (u, a')$
, for every
$u \in V$
. Since
$\varphi $
is nondegenerate, we obtain
$a=a'$
. Hence, the set
$\Omega $
is in one-to-one correspondence with V. This, in particular, yields that
$|\Omega |= q^{2m}$
.
Lemma 6.8. The group G acts on the set
$\Omega $
.
Proof. First, we show that for every
$x\in G$
and for every
$\theta \in \Omega $
, the mapping
$$ \begin{align} \begin{array}{ll} \theta^x &\colon V\to\mathbb{F}_q\\ & u \mapsto \theta(ux^{-1}) \end{array} \end{align} $$
gives rise to an element of
$\Omega $
. For every
$u,v\in V$
, we have
$$ \begin{align*} \theta^x(u+v)&=\theta((u+v)x^{-1})=\theta(ux^{-1}+vx^{-1})=\theta(ux^{-1})+\theta(vx^{-1})+\varphi(ux^{-1},vx^{-1})\\ &=\theta(ux^{-1})+\theta(vx^{-1})+\varphi(u,v)=\theta^{x}(u)+\theta^x(v)+\varphi(u,v). \end{align*} $$
Observe that in the fourth equality, we used the fact that
$x\in G$
and hence x preserves the bilinear form
$\varphi $
. Moreover,
$$ \begin{align*} \theta^x(cu)&=\theta((cu)x^{-1})=\theta(c(ux^{-1}))=c^2\theta(ux^{-1})=c^2\theta^x(u). \end{align*} $$
Therefore,
$\theta ^x\in \Omega $
. Finally, for every
$x,y\in G$
,
$\theta \in \Omega $
and
$u\in V$
, we have
$$ \begin{align*}(\theta^{x})^y(u)=\theta^x(uy^{-1})=\theta((uy^{-1})x^{-1})=\theta(u(xy)^{-1})=\theta^{xy}(u).\end{align*} $$
Therefore,
$(\theta ^{x})^y=\theta ^{xy}$
, and hence, G defines a genuine right action on
$\Omega $
.
Before continuing our discussion, we gather some information on G. Let
$a\in V$
, and we define the mapping
$$ \begin{align} \begin{array}{ll} t_a \colon &V\to V\\ &u \mapsto u+\varphi(u,a)a. \end{array} \end{align} $$
Such a function is called a transvection. For every
$u,v \in V$
and
$c \in \mathbb {F}_q$
, we have
$$ \begin{align*} (u+v)t_a & = (u+v) + \varphi(u+v,a)a = (u + \varphi(u,a)a) + (v + \varphi(v,a)a) = (u)t_a +(v)t_a; \\ (cu)t_a & = cu + \varphi(cu,a)a = c(u+\varphi(u,a)a)= c(u) t_a. \end{align*} $$
Hence,
$t_a$
is linear. Moreover, for every
$u\in V$
, we have
$$ \begin{align*} (u)t_a^2&=(u+\varphi(u,a)a)t_a=u+\varphi(u,a)a+\varphi(u+\varphi(u,a)a,a)a\\ &=u+\varphi(u,a)a+\varphi(u,a)a+\varphi(u,a)\varphi(a,a)a=u+2\varphi(u,a)a+\varphi(u,a)\varphi(a,a)a\\ &=u+\varphi(u,a)\varphi(a,a)a \underset{6.2}{=} u, \end{align*} $$
where in the second-last equality we use the fact that the characteristic of
$\mathbb {F}_q$
is
$2$
. This shows that
$t_a$
is an involution. Finally, for every
$u,v\in V$
, we have
$$ \begin{align*} \varphi((u)t_a,(v)t_a)&=\varphi(u+\varphi(u,a)a,v+\varphi(v,a)a)\\ &=\varphi(u,v)+\varphi(v,a)\varphi(u,a)+\varphi(u,a)\varphi(a,v)+\varphi(u,a)\varphi(v,a)\varphi(a,a)\\ &\underset{6.3}{=}\varphi(u,v) + 2 \varphi(v,a)\varphi(u,a) + \varphi(u,a)\varphi(v,a)\varphi(a,a) \\ &= \varphi(u,v) + \varphi(u,a)\varphi(v,a)\varphi(a,a)\\ &\underset{6.2}{=}\varphi(u,v). \end{align*} $$
Therefore,
$t_a$
preserves
$\varphi $
and hence lies in the symplectic group G.
We are now interested in computing the image of
$\theta _a$
under the transvection
$t_c$
. First, recall that, in a field of characteristic 2, since
$x= -x$
for every
$x \in \mathbb {F}_q$
, the square root
$\sqrt {\cdot } \colon \mathbb {F}_q \to \mathbb {F}_q$
is a well-defined map. Moreover, for every
$a,b,x,y \in \mathbb {F}_q$
such that
$x=a^2$
and
$y=b^2$
, we have
$(\sqrt {x}+\sqrt {y})^2= (a+b)^2= a^2+b^2= x+y$
, which implies
$\sqrt {x}+\sqrt {y}=\sqrt {x+y}$
. Moreover, recall that
$\theta _a$
is a quadratic form polarising to
$\varphi $
and that
$t_a$
is an involution, in particular
$t_c=t_c^{-1}$
. By using these facts, given
$v\in V$
, we have
$$ \begin{align*} \theta_a^{t_c}(u)&\underset{6.6}{=}\theta_a(ut_c^{-1})=\theta_a(ut_c)\underset{6.7}{=} \theta_a(u+\varphi(u,c)c)\\ &=\theta_a(u)+\theta_a(\varphi(u,c)c)+\varphi(u,\varphi(u,c)c)\\ &=\theta_a(u)+\varphi(u,c)^2\theta_a(c)+\varphi(u,c)^2\\ &=\theta_a(u)+(\theta_a(c)+1)\varphi(u,c)^2=\theta_a(u)+(\sqrt{\theta_a(c)+1}\varphi(u,c))^2\\ &=\theta_a(u)+\varphi(u,(\sqrt{\theta_a(c)}+1)c)^2\underset{6.5}{=}\theta_0(u)+\varphi(u,a)^2+\varphi(u,(\sqrt{\theta_a(c)}+1)c)^2\\ &=\theta_0(u)+\varphi(u,a+(\sqrt{\theta_a(c)}+1)c)^2\\ &\underset{6.5}{=}\theta_{a+(\sqrt{\theta_a(c)}+1)c}(u). \end{align*} $$
From this, we deduce
$$ \begin{align} \theta_a^{t_c}= \theta_{a+(\sqrt{\theta_a(c)}+1)c}. \end{align} $$
We now recall some facts about Galois theory. For a reference, see [Reference LangLan02, Chapter VI]. The Frobenius mapping
$\phi \colon x \mapsto x^2$
from
$\mathbb {F}_q$
to itself is a generator of the Galois group of
$\mathbb {F}_q$
over
$\mathbb {F}_2$
. There exists a well-defined
$\mathbb {F}_2$
-linear trace mapping
$\text {Tr}:\mathbb {F}_q\to \mathbb {F}_2$
. In what follows, we need only two basic facts about
$\text {Tr}$
: first,
$\text {Tr}$
is surjective, and second, from Hilbert’s 90 theorem, the kernel of
$\text {Tr}$
consists of the set
$\{x^2+x\mid x\in \mathbb {F}_q\}$
and has cardinality
$q/2$
.
Define
$$ \begin{align*} \Omega^+:=\{\theta_a\mid \text{Tr}(\theta_0(a))=0\},\\ \Omega^-:=\{\theta_a\mid\text{Tr}(\theta_0(a))=1\}. \end{align*} $$
Observe that the above definition is a generalization of the definition of
$\Omega ^+$
and
$\Omega ^-$
in [Reference Dixon and MortimerDM96, Corollary 7.7 A]. Indeed, if
$q=2$
, then the Galois group is the trivial group, and hence, the trace map is the identity.
Let
$N:=\langle t_a\mid a\in V\rangle $
be the subgroup of G generated by the transvections. Observe that, for all
$a,u \in V$
and
$x \in G$
, we have
$$ \begin{align*} (u)x^{-1}t_ax= (ux^{-1}+\varphi(ux^{-1},a)a)x= u+\varphi(u,ax)ax = (u)t_{ax}. \end{align*} $$
In particular, this shows that
$N\unlhd G$
.
Lemma 6.9. The sets
$\Omega ^+$
and
$\Omega ^-$
are N-orbits on
$\Omega $
, with
$$ \begin{align*}|\Omega^+|=\frac{q^m(q^m+1)}{2},\quad |\Omega^-|=\frac{q^m(q^m-1)}{2}.\end{align*} $$
These are also orbits for G.
Proof. We first prove that
$$ \begin{align*}|\Omega^+|=\frac{q^m(q^m+1)}{2},\quad |\Omega^-|=\frac{q^m(q^m-1)}{2}.\end{align*} $$
Clearly, it suffices to prove the first equality, because the second follows from the equality
$$ \begin{align*}|\Omega^-|=|\Omega|-|\Omega^+|=q^{2m}-|\Omega^+|.\end{align*} $$
By definition,
$\theta _0(a)=aea^T$
. Moreover, by using the canonical basis of V, we have
$$ \begin{align*}\text{Tr}\left(\theta_0\left(\sum_{i=1}^{2m}a_ie_i\right)\right)= \text{Tr}\left(\sum_{i=1}^{m}a_ia_{i+m}\right)=\sum_{i=1}^m\text{Tr}(a_ia_{i+m}).\end{align*} $$
Using this equation, we may compute the cardinality of
$|\Omega ^+|$
arguing inductively on m. When
$m=1$
, we have
$\text {Tr}(a_1a_2)=0$
. When
$a_1=0$
, we have q solutions for
$a_2$
; however, for every
$a_1\in \mathbb {F}_q\setminus \{0\}$
, we have
$q/2$
solutions for
$a_2$
. Therefore, when
$m=1$
, we have
$$ \begin{align*}q+(q-1)\frac{q}{2}=\frac{q^2}{2}+\frac{q}{2}=\frac{q(q+1)}{2}\end{align*} $$
solutions to the equation
$\text {Tr}(a_1a_2)=0$
and we have
$\frac {q(q-1)}{2}$
solutions to the equation
$\text {Tr}(a_{1}a_2)=1$
. Arguing inductively, we may assume that
$$ \begin{align*}\sum_{i=1}^{m-1}\text{Tr}(a_ia_{i+m})\end{align*} $$
is equal to 0 for
$q^{m-1}(q^{m-1}+1)/2$
choices of
$(a_1, \dots, a_{m-1})$
and is equal to 1 for
$q^{m-1}(q^{m-1}-1)/2$
choices of
$a_1, \dots, a_{m-1}$
. Now,
$$ \begin{align*}\sum_{i=1}^{m}\text{Tr}(a_ia_{i+m})=\sum_{i=1}^{m-1}\text{Tr}(a_ia_{i+m})+\text{Tr}(a_ma_{2m})\end{align*} $$
has value
$0$
if and only if
$\sum _{i=1}^{m-1}\text {Tr}(a_ia_{i+m})$
and
$\text {Tr}(a_ma_{2m})$
have the same value. Therefore, altogether, the number of solutions of
$\sum _{i=1}^{m}\text {Tr}(a_ia_{i+m})=0$
is
$$ \begin{align*} \frac{q^{m-1}(q^{m-1}+1)}{2}\frac{q(q+1)}{2}+\frac{q^{m-1}(q^{m-1}-1)}{2}\frac{q(q-1)}{2}=\frac{q^{m}(q^{m}+1)}{2}. \end{align*} $$
Next, we prove that
$\Omega ^+$
and
$\Omega ^-$
are N-orbits. We start by considering
$\Omega ^+$
. We first prove that
$\Omega ^+$
is N-invariant. To this end, it suffices to show that if
$\theta _a\in \Omega ^+$
and
$c\in V$
, then
$\theta _a^{t_c}\in \Omega ^+$
. In other words, using (6.8), if
$\text {Tr}(\theta _0(a))=0$
, then
$\text {Tr}(\theta _0(a+(\sqrt {\theta _a(c)}+1)c))=0$
. So let
$\text {Tr}(\theta _0(a))=0$
and recall that
$\text {Tr}$
is a linear map. We have
$$ \begin{align} \begin{array}{ll} \text{Tr}(\theta_0(a+(\sqrt{\theta_a(c)}+1)c)) &\underset{6.4}{=}\text{Tr} \left(\theta_0(a)+\theta_0((\sqrt{\theta_a(c)}+1)c)+ \varphi(a,(\sqrt{\theta_a(c)}+1)c)\right)\\ &=\text{Tr}\left(\theta_0(a)\right)+\text{Tr}\left(\kern-1pt\theta_0((\sqrt{\theta_a(c)}+1)c)\!\right)+\text{Tr}\left(\kern-1pt\varphi(a,(\sqrt{\theta_a(c)}+1)c)\!\right)\\ &=\text{Tr}\left(\theta_0((\sqrt{\theta_a(c)}+1)c)\right)+\text{Tr}\left(\varphi(a,(\sqrt{\theta_a(c)}+1)c)\right)\\ &=\text{Tr}\left((\sqrt{\theta_a(c)}+1)^2\theta_0(c)\right)+\text{Tr}\left(\varphi(a,(\sqrt{\theta_a(c)}+1)c)\right)\\ &=\text{Tr}\left((\theta_a(c)+1)\theta_0(c)\right)+\text{Tr}\left((\sqrt{\theta_a(c)}+1)\varphi(a,c)\right)\\ &=\text{Tr}\left(\theta_a(c)\theta_0(c)\right)+\text{Tr}\left(\theta_0(c)\right)+\text{Tr}(\sqrt{\theta_a(c)}\varphi(a,c))+\text{Tr}(\varphi(a,c)). \end{array} \end{align} $$
Using
$\theta _a(c)=\theta _0(c)+\varphi (a,c)^2$
and
$\text {Tr}(x^2)=\text {Tr}(x)$
, for every
$x\in \mathbb {F}_q$
, we obtain
$$ \begin{align} \begin{array}{ll} \text{Tr}\left(\theta_a(c)\theta_0(c)\right)&=\text{Tr}(\theta_0(c)^2)+\text{Tr}(\varphi(a,c)^2\theta_0(c))\\ &=\text{Tr}(\theta_0(c))+\text{Tr}(\varphi(a,c)^2\theta_0(c)), \end{array} \end{align} $$
$$ \begin{align} \begin{array}{ll} \text{Tr}(\sqrt{\theta_a(c)}\varphi(a,c))&=\text{Tr}(\sqrt{\theta_0(c)}\varphi(a,c))+\text{Tr}(\varphi(a,c)^2)\\ &=\text{Tr}(\sqrt{\theta_0(c)}\varphi(a,c))+\text{Tr}(\varphi(a,c)). \end{array} \end{align} $$
Putting (6.10) and (6.11) into (6.9), we obtain
$$ \begin{align*} \text{Tr}(\theta_0(a+(\sqrt{\theta_a(c)}+1)c))= \,&\text{Tr}(\theta_0(c))+\text{Tr}(\varphi(a,c)^2\theta_0(c))+ \text{Tr}\left(\theta_0(c)\right)\\ &+ \text{Tr}(\sqrt{\theta_0(c)}\varphi(a,c))+\text{Tr}(\varphi(a,c)) + \text{Tr}(\varphi(a,c))\\ =&\,0. \end{align*} $$
As
$\Omega ^-=\Omega \setminus \Omega ^+$
, we obtain that
$\Omega ^-$
is also N-invariant.
Next, we show that
$\Omega ^+$
is an N-orbit. Actually, we prove something stronger, we show that
$$ \begin{align*}\Omega^+=\{\theta_0^{t_c}\mid c\in V\}.\end{align*} $$
For every
$a\in V$
with
$\text {Tr}(\theta _0(a))=0$
, we need to show that there exists
$c\in V$
such that
$$ \begin{align} \theta_a=\theta_0^{t_c}. \end{align} $$
If
$\theta _0(a)=0$
, then we may take
$c:=a$
and (6.8) yields
$$ \begin{align*}\theta_0^{t_a}=\theta_{0+(\sqrt{\theta_0(a)}+1)a}=\theta_{a}\end{align*} $$
and we are finished. Suppose
$\theta _0(a)\ne 0$
. Since
$\text {Tr}(\theta _0(a))=0$
, from Hilbert’s 90 theorem, there exists
$x\in \mathbb {F}_q$
with
$\theta _0(a)=x+x^2$
. Since
$\theta _0(a)\ne 0$
, we have
$x\ne 0$
. Let
$y\in \mathbb {F}_q\setminus \{0\}$
with
$y^2=x$
, and set
$c:=y^{-1}a$
. Thus,
$$ \begin{align*} \sqrt{\theta_0(c)}+1&=\sqrt{\theta_0(y^{-1}a)}+1=\sqrt{y^{-2}\theta_0(a)}+1=y^{-1}\sqrt{\theta_0(a)}+1\\ &=y^{-1}\sqrt{x+x^2}+1=y^{-1}(y+y^2)+1=y. \end{align*} $$
From (6.8), we have
$$ \begin{align*} \theta_0^{t_c} &=\theta_{0+(\sqrt{\theta_0(c)}+1)c}=\theta_{yc}=\theta_{yy^{-1}a}=\theta_a. \end{align*} $$
Next, we show that
$\Omega ^-$
is an N-orbit. Actually, we prove something stronger, we show that
$$ \begin{align*}\Omega^-=\{\theta_{\varepsilon}^{t_c}\mid c\in V\}.\end{align*} $$
First, we select a distinguished element of
$\Omega ^-$
. Let
$\epsilon \in \mathbb {F}_q$
with
$\text {Tr}(\epsilon)=1$
, and set
$\varepsilon:=\epsilon e_1+e_{m+1}$
, where
$(e_i)_{i\in \{1,\ldots,2m\}}$
is the standard basis of V. Since
$\theta _0(\epsilon e_1)=0=\theta _0(e_{m+1})$
, we have
$$ \begin{align*} \theta_0(\varepsilon)=\theta_0(\epsilon e_1)+\theta_0(e_{m+1})+\varphi(\epsilon e_1,e_{m+1})=\epsilon\varphi(e_1,e_{m+1})=\epsilon, \end{align*} $$
and hence,
$\text {Tr}(\theta _0(\varepsilon))=\text {Tr}(\epsilon)=1$
. Therefore,
$\theta _{\varepsilon }\in \Omega ^-$
.
For every
$a\in V$
with
$\text {Tr}(\theta _0(a))=1$
, we need to show that there exists
$c\in V$
such that
$$ \begin{align} \theta_a=\theta_{\varepsilon}^{t_c}. \end{align} $$
If
$\theta _{\varepsilon }(a+\varepsilon)=0$
, then we may take
$c:=a+\varepsilon $
and (6.8) yields
$$ \begin{align*} \theta_{\varepsilon}^{t_{c}}=\theta_{\varepsilon+(\sqrt{\theta_{\varepsilon}(c)}+1)c}=\theta_{\varepsilon+c}=\theta_a \end{align*} $$
and we are finished. Suppose
$\theta _{\varepsilon }(a+\varepsilon)\ne 0$
. We have
$$ \begin{align*} \theta_{\varepsilon}(a+\varepsilon)&\underset{6.5}{=}\theta_0(a+\varepsilon)+\varphi(a+\varepsilon,\varepsilon)^2= \theta_0(a+\varepsilon)+\varphi(a,\varepsilon)^2 + \varphi(\varepsilon,\varepsilon)^2\\ &\underset{6.2}{=}\theta_0(a+\varepsilon)+\varphi(a,\varepsilon)^2\\ &\underset{6.4}{=}\theta_0(a)+\theta_0(\varepsilon)+\varphi(a,\varepsilon)+\varphi(a,\varepsilon)^2. \end{align*} $$
Since
$\text {Tr}(\theta _0(a))=1=\text {Tr}(\theta _0(\varepsilon))$
, by using the previous equality, we deduce that
$$ \begin{align*} \text{Tr}(\theta_{\varepsilon}(a+\varepsilon))=0. \end{align*} $$
From Hilbert’s 90 theorem, there exists
$x\in \mathbb {F}_q$
with
$\theta _{\varepsilon }(a+\varepsilon)=x+x^2$
. Since
$\theta _{\varepsilon }(a+\varepsilon)\ne 0$
, we have
$x\ne 0$
. Let
$y\in \mathbb {F}_q\setminus \{0\}$
with
$y^2=x$
and set
$c:=y^{-1}(a+\varepsilon)$
. Thus,
$$ \begin{align*} \sqrt{\theta_{\varepsilon}(c)}+1&=\sqrt{\theta_{\varepsilon}(y^{-1}(a+\varepsilon))}+1=\sqrt{y^{-2}\theta_{\varepsilon}(a+\varepsilon)}+1=y^{-1}\sqrt{\theta_{\varepsilon}(a+\varepsilon)}+1\\ &=y^{-1}\sqrt{x+x^2}+1=y^{-1}(y+y^2)+1=y. \end{align*} $$
From (6.8), we have
$$ \begin{align*} \theta_{\varepsilon}^{t_c} &=\theta_{\varepsilon+(\sqrt{\theta_{\varepsilon}(c)}+1)c}=\theta_{\varepsilon+yc}=\theta_{\varepsilon+yy^{-1}(a+\varepsilon)}=\theta_a. \end{align*} $$
The fact that
$\Omega ^-$
and
$\Omega ^+$
are also G-orbits follows from the fact that
$N \unlhd G$
and
$\left |\Omega ^+\right |\ne \left |\Omega ^-\right |$
.
We now compute the maximum length of a stabilizer chain in these two actions. Let
$\epsilon \in \{+,-\}$
(we deal simultaneously with both cases). Let
$\{\theta _{a_1},\theta _{a_2},\ldots,\theta _{a_k}\}$
be a subset of
$\Omega ^{\epsilon }$
such that the corresponding chain of stabilizers is strictly decreasing. Without loss of generality, we may suppose that
$a_1=0$
when
$\epsilon =+$
and
$a_1=\varepsilon $
when
$\epsilon =-$
. Recall that
$\varepsilon $
is an element of V for which
$\theta _{\varepsilon }$
is a distinguished element of
$\Omega ^-$
; the definition of
$\varepsilon $
was given in the proof of the previous lemma.
Let us define
$$ \begin{align*}{C}_{{G_{\theta_{a_1}}}}{{(a_1+a_i)}}=\{x\in G_{\theta_{a_1}}\mid (a_1+a_i)x=a_1+a_i\},\end{align*} $$
that is, the set of matrices in
$G_{\theta {a_1}}$
fixing the vector
$a_1+a_i\in V$
.
Lemma 6.10. For every
$i\in \{2,\ldots,k\}$
,
$$ \begin{align}G_{\theta_{a_1}}\cap G_{\theta_{a_i}}={C}_{{G_{\theta{a_1}}}}{{(a_1+a_i)}}. \end{align} $$
Proof. First observe that, given
$j\in \{1,\ldots,k\}$
,
$x \in G_{\theta _{a_j}}$
if and only if, for every
$u \in V $
, we have
$$ \begin{align} \theta_0(ux^{-1})+\varphi(ux^{-1},a_j)^2= \theta_0(u)+\varphi(u,a_j)^2. \end{align} $$
Fix
$i\in \{2,\ldots,k\}$
and let
$x \in G_{\theta _{a_1}} \cap G_{\theta _{a_i}}$
. Then, by applying (6.15) with
$j:=1$
and with
$j:=i$
and by using the fact that the characteristic of
$\mathbb {F}_q$
is
$2$
, we obtain that, for every
$u \in V$
,
$$ \begin{align*} \varphi(ux^{-1}, a_1+a_i)^2 = \varphi(u, a_1+a_i)^2. \end{align*} $$
Since
$\varphi $
is G-invariant, then
$\varphi (ux^{-1}, a_1+a_i)^2 = \varphi (u, (a_1+a_i)x)^2$
. Therefore, as
$\varphi $
is nondegenerate,
$(a_1+a_i)x=a_1+a_i$
and hence
$x \in {C}_{{G_{\theta _{a_1}}}}{{(a_1+a_i)}}$
.
Conversely, let
$x \in {C}_{{G_{\theta _{a_1}}}}{{(a_1+a_i)}}$
. Then,
$x \in G_{\theta _{a_1}}$
and
$(a_1+a_i)x= a_1+a_i$
. We need to show that
$x \in G_{\theta _{a_i}}$
. Note that (6.15) applied with
$j=1$
and the fact that we are in characteristic 2 imply that
$$ \begin{align} \theta_0(ux^{-1})= \theta_0(u)+\varphi(u,a_1)^2+\varphi(ux^{-1},a_1)^2. \end{align} $$
For every
$u \in V$
, we have:
$$ \begin{align*} \theta_{a_i}^x(u) & \underset{6.6}{=} \theta_{a_i}(ux^{-1}) \underset{6.5}{=} \theta_0(ux^{-1})+\varphi(ux^{-1},a_i)^2\\ &\underset{6.16}{=} \theta_0(u) +\varphi(ux^{-1},a_1)^2+\varphi(u,a_1)^2+\varphi(ux^{-1},a_i)^2 \\ &= \theta_0(u)+\varphi(ux^{-1},a_1+a_i)^2+\varphi(u,a_1)^2 \\ & =\theta_0(u)+\varphi(u,(a_1+a_i)x)^2+\varphi(u,a_i)^2 \\ & = \theta_0(u)+\varphi(u,a_1+a_i)^2+\varphi(u,a_1)^2 \\ &= \theta_0(u)+\varphi(u,a_1)^2+\varphi(u,a_i)^2 + \varphi(u,a_1)^2\\ &= \theta_0(u)+2 \varphi(u,a_1)^2+\varphi(u,a_i)^2\\ &= \theta_0(u)+\varphi(u,a_i)^2 \underset{6.5}{=} \theta_{a_i}(u). \end{align*} $$
Observe that in the sixth and seventh equalities we use, respectively, the fact that x preserves
$\varphi $
and the fact that x fixes the vector
$(a_1+a_i)$
. Hence,
$x \in G_{\theta _{a_i}}$
and therefore
$x \in G_{\theta _{a_1}} \cap G_{\theta _{a_i}}$
.
For simplicity, for each
$i\in \{1,\ldots,k\}$
, write
$G_i:=G_{\theta _{a_1}}\cap \cdots \cap G_{\theta _{a_i}}$
and, for each
$i\in \{2,\ldots,k\}$
, write
$b_i:=a_1+a_i$
. From (6.14), the strictly decreasing sequence
$$ \begin{align*}G_1>G_2>\cdots>G_{k-1}>G_k\end{align*} $$
equals
$$ \begin{align*} G_1>& {C}_{{G_1}}{{(b_2)}} = {C}_{{G_1}}{{(\left\langle b_2 \right\rangle_{\mathbb{F}_q})}} > {C}_{{G_1}}{{(b_2,b_3)}}= {C}_{{G_1}}{{(\left\langle b_2,b_3 \right\rangle_{\mathbb{F}_q})}}>\cdots\\ >& {C}_{{G_1}}{{(b_2,\ldots,b_{k-1})}}={C}_{{G_1}}{{(\left\langle b_2,\ldots,b_{k-1} \right\rangle_{\mathbb{F}_q})}}> {C}_{{G_1}}{{(b_2,\ldots,b_k)}}={C}_{{G_1}}{{(\left\langle b_2,\ldots,b_k \right\rangle_{\mathbb{F}_q})}}. \end{align*} $$
Here, if
$v_1,\dots, v_j\in V$
, then we write
$\left \langle v_1,\dots, v_j \right \rangle _{\mathbb {F}_q}$
to denote the
$\mathbb {F}_q$
-vector space generated by the
$v_1,\dots, v_j$
. We obtain that
$$ \begin{align*}0<\left\langle b_2 \right\rangle_{\mathbb{F}_q}<\left\langle b_2,b_3 \right\rangle_{\mathbb{F}_q}<\cdots<\left\langle b_2,\ldots,b_k \right\rangle_{\mathbb{F}_q}\le V.\end{align*} $$
Observe that a strict inclusion in the above chain implies that the dimension has to go down by at least one at each step. Therefore,
$k\le 1+2m$
. Thus, we have proved the following lemma.
Lemma 6.11. Let
$G:= \textrm{Sp}_{2m}(q)$
act on
$\Omega ^{\epsilon }$
, where
$\epsilon \in \{+,-\}$
. Then,
$\textrm{I}(G, \Omega ^{\epsilon }) \leq 1+2m$
.
We are now able to prove Lemma 6.7 for
$m\geq 3$
. The proof is virtually identical when
$m=2$
; however, to avoid annoying details, we will use the fact that when
$m=2$
the result follows from Lemma 6.12 which we prove in a moment.
Proof Proof of Lemma 6.7
for
$m\geq 3$
. Let
$q=2^e$
. Since
$m\geq 3$
,
$$ \begin{align*} \text{Sp}_{2m}(q) \unlhd G \leq \Gamma \text{Sp}_{2m}(q) =\text{Sp}_{2m}(q) \rtimes \mathcal{C}_e. \end{align*} $$
Since a strictly descending chain of subgroups of
$\mathcal {C}_e$
has length at most
$\log e$
, we conclude that
$$ \begin{align*} \textrm{I}(\Gamma \text{Sp}_{2m}(q), \Omega^{\epsilon}) \le 2m +1 + \log e. \end{align*} $$
Suppose
$2m+1+\log e\ge 2\log t^{\epsilon }$
. Recall the cardinality of
$\Omega ^{\epsilon }$
from Lemma 6.9. Then,
$$ \begin{align*}2^{2m+1}\cdot e \ge (t^{\epsilon})^2= 2^{2em-2}\left(2^{em} +\epsilon 1\right)^2 \geq 2^{2em-2}\left(2^{em} - 1\right)^2.\end{align*} $$
When
$e\ge 2$
, with an easy computation, we obtain a contradiction. When
$e=1$
, we have
$2^{2m+1}\ge 2^{2m-2}(2^{m}-1)^2$
, which implies
$2^3\ge (2^m-1)^2$
. Again, this is a contradiction, because
$m\ge 3$
.
Putting these things together, we obtain that
$\textrm{I}(G, \Omega ^{\epsilon }) < 2\log t^{\epsilon }.$
6.3. Cases involving graph automorphisms
We remarked after Definition 6.2 that the almost simple groups with socle
$\textrm{Sp}_4(2^a)$
or
$\textrm{P}\Omega _8^{+}(q)$
containing a graph automorphism or a triality graph automorphism were not covered by the definition. We briefly deal with these groups here.
Lemma 6.12. Let G be an almost simple group with socle
$G_0= \textrm{Sp}_4(2^a)'$
, and let G act faithfully and primitively on
$\Omega $
, a set of size t. Then,
$$ \begin{align*} \textrm{I}(G,\Omega)< \frac{11}{3}\log t. \end{align*} $$
Proof. If
$a=1$
, then
$G\leq \textrm{P}\Gamma \textrm{L}_2(9)$
. It is not hard to verify that the longest strictly increasing chain of subgroups of
$\textrm{P}\Gamma \textrm{L}_2(9)$
has length
$6$
. Thus,
$\textrm{I}(G)\leq 6$
. On the other hand,
$t\geq 6$
, and so the result follows. Assume, then, that
$a>2$
. Note that
$$ \begin{align*} G_0 \leq G \leq \mathop{\text{Aut}}(\text{Sp}_4(2^a))= \Gamma \text{Sp}_4(2^a). \langle \gamma \rangle, \end{align*} $$
where
$\gamma $
is a graph automorphism of order
$2a$
. We obtain that
$$ \begin{align} \begin{array}{ll} |G| &\leq |\mathop{\text{Aut}}(\text{Sp}_4(2^a))| = |\text{Sp}_4(2^a)|\cdot 2 \cdot a \\ &= 2^{4a}(2^{2a}-1)(2^{4a}-1) \cdot 2 \cdot a \leq 2^{11a}. \end{array} \end{align} $$
On the other hand, [Reference Kleidman and LiebeckKL90, Theorem 5.2.2] implies that
$$ \begin{align} t \geq \frac{2^{4a}-1}{2^a-1}= 2^{3a}+2^{2a}+2^a+1>2^{3a}. \end{align} $$
$$ \begin{align*} \textrm{I}(G) \leq \log 2^{11a} = \log (2^{3a})^{\frac{11}{3}} = \frac{11}{3} \log 2^{3a} < \frac{11}{3} \log t.\\[-30pt] \end{align*} $$
Lemma 6.13. Let G be an almost simple group with socle
$G_0=\textrm{P}\Omega _8^+(q)$
, where
$q=p^f$
for some prime p and positive integer f, and let G act primitively on
$\Omega $
, a set of size t. Then,
$$ \begin{align*} \textrm{I}(G,\Omega)< \frac{16}{3}\log t. \end{align*} $$
Proof. Note that
$$ \begin{align*} G_0 \leq G \leq \mathop{\text{Aut}}(\text{P}\Omega_8^+(q))= \text{P}\Gamma\text{O}_8^+(q). \langle \tau \rangle, \end{align*} $$
with
$\tau $
a triality graph automorphism of order 3. Now, using the fact that
$6f<q^4$
, and recalling that
$$ \begin{align*} & |G_0|= \frac{1}{d} q^{12}(q^4-1) \prod_{i=1}^{3}{(q^{2i}-1)},\\ & |\mathop{\text{Out}}(G_0)|=6df, \end{align*} $$
where
$d=(4,q^4-1)$
, we obtain that
$$ \begin{align} \begin{array}{ll} |G| &\leq |\mathop{\text{Aut}}(G_0)|=|G_0|\cdot|\mathop{\text{Out}}(G_0)|\\ &= 6df \cdot \frac{1}{d} q^{12}(q^4-1)(q^2-1)(q^4-1)(q^6-1) \\ &< 6fq^{28} < q^{32}. \end{array} \end{align} $$
On the other hand, [Reference Kleidman and LiebeckKL90, Section 5.2] implies that
$$ \begin{align} \begin{cases} t \geq \frac{(q^4-1)(q^3+1)}{(q-1)} = (q^3+q^2+q+1)(q^3+1)> q^6, & \text{ for } q>2; \\ t \geq 2^3(2^4-1) > 2^6, & \text{ for } q = 2. \end{cases} \end{align} $$
$$ \begin{align*} \textrm{I}(G) \leq \log q^{32} = \log (q^6)^{\frac{32}{6}} < \frac{16}{3} \log t. \\[-40pt]\end{align*} $$
Now Proposition 6.1 is a consequence of Lemmas 6.5–6.7, 6.12, and 6.13. Similarly, Theorem 1.6 is a consequence of Propositions 3.1, 4.1, 5.1, and 6.1 (observe that in Proposition 5.1 we are using the fact that
$|\Delta |\ge 5$
and hence
$3/(2\log |\Delta |)<1$
).
7. Almost simple groups: Bounds on
$\text {H}(G)$
Now that Theorem 1.6 is proved, we turn our attention to the proof of Theorem 1.3. In light of Theorem 1.6 and Proposition 5.1, all that is required is that we deal with the almost simple groups listed at item (1b) of Theorem 1.6—we must show that these conform to the bound given in Theorem 1.3. Thus, the result that we need is the following.
Proposition 7.1. Let G be an almost simple group with socle,
$G_0$
, a simple classical group. Let V be the associated natural module, of dimension n over a field
$\mathbb {F}_q$
, let m be an integer with
$0<m<n$
, let
$\Omega $
be a set of m-dimensional subspaces of V on which G acts primitively, and let
$t=|\Omega |$
. Then,
$$ \begin{align*} \textrm{H}(G)<\frac{17}{2}\log t. \end{align*} $$
7.1.
$G_0=\text {PSL}_n(q)$
and elements of
$\Omega $
are m-spaces
In this case, we suppose that
$G_0=\textrm{PSL}_n(q)$
, and that
$\Omega $
is the set of all m-dimensional subspaces of V, where V is the natural n-dimensional module for
$G_0$
over
$\mathbb {F}_q$
. Note that G is transitive on
$\Omega $
. We prove the following result.
Lemma 7.2. Let G be an almost simple group with socle
$\textrm{PSL}_n(q)$
acting on
$\Omega $
, the set of all m-spaces in V. Then,
$$ \begin{align*} \textrm{H}(G) < \frac{11}{2}\log t. \end{align*} $$
Moreover, if
$q=p^f$
with p a prime number and
$G\le \textrm{P}\Gamma \textrm{L}_n(q)$
, then
$$ \begin{align} \textrm{H}(G) < 2\min(m,n-m)n + \log \log_p{q}. \end{align} $$
Using the fact that duality conjugates m-space stabilizers to
$(n-m)$
-space stabilizers, in what follows, we may suppose that
$m\le n/2$
. Two notes concerning the actions considered in Lemma 7.2. First, it is easy to check that
$$ \begin{align} t> q^{m(n-m)}. \end{align} $$
Second, we note that if
$m<\frac {n}{2}$
, then
$G\leq \textrm{P}\Gamma \textrm{L}_n(q)$
. If
$m=\frac {n}{2}$
, then we must allow for the possibility that G contains a graph automorphism of
$\textrm{PSL}_n(q)$
.
7.2. Some preliminaries
Let V and W be finite-dimensional vector spaces over
$\mathbb {F}_q$
. We denote by
$\text {End}^s_{\mathbb {F}_q}{(V)}$
the set of all semilinear transformations
$V \to V$
. Moreover, we write
$\text {Hom}_{\mathbb {F}_q}{(V,W)}$
for the set of all linear maps
$V \to W$
and
$\text {Hom}^s_{\mathbb {F}_q}{(V,W)}$
for the set of all semilinear maps
$V \to W$
.
If
$n=\dim (V)$
, then we write
$M_n(q)$
to denote the set of linear transformations
$V\to V$
; where a basis has been chosen, we also allow
$M=M_n(q)$
to denote the set of all n-by-n matrices over
$\mathbb {F}_q$
. If
$W_1,\dots, W_k\leq V$
, then we define
$$ \begin{align*} M_{W_1,\dots, W_k} = \{ g\in M \mid W_ig\leq W_i \text{ for all }i=1,\dots, k\}. \end{align*} $$
Using this definition, it is natural to extend the concept of base, irredundant base, and independent set in the context of the algebra
$M=M_n(q)$
. For instance, given a set
$\Lambda:=\{W_1,\ldots,W_k\}$
of subspaces of V, we say that
$\Lambda $
is an independent set for
$M=M_n(q)$
if, for each
$i\in \{1,\ldots,k\}$
, we have
$$ \begin{align*}M_{W_1,\ldots,W_k}<M_{W_1,\ldots,W_{i-1},W_{i+1},\ldots,W_{k}}.\end{align*} $$
Recall that any element of
$\operatorname {\mathrm {Aut}}(\mathbb {F}_q)$
induces an automorphism of V: we first fix a basis for V and then act coordinatewise. The following lemma is standard, but we include it for completeness.
Lemma 7.3. Let
$g \in \text {Hom}^s_{\mathbb {F}_q}{(V,W)}$
,
$g \neq 0$
. Then:
-
(a) there exists a unique
$\sigma \in \mathop {\text {Aut}}(\mathbb {F}_q)$
such that g is
$\sigma $
-semilinear. We say that
$\sigma $
is the associated automorphism of g; -
(b) if
$\sigma $
is the associated automorphism of g, then
$g\sigma ^{-1} \in \text {Hom}_{\mathbb {F}_q}{(V,W)}$
; -
(c) there exists a unique
$h \in \text {Hom}_{\mathbb {F}_q}{(V,W)}$
such that
$g= h\sigma $
.
Proof.
-
(a) Assume that there exist
$\sigma _1,\sigma _2 \in \mathop {\text {Aut}}(\mathbb {F}_q)$
such that g is
$\sigma _1$
-semilinear and
$\sigma _2$
-semilinear. Hence, for any
$v \in V$
and
$k \in \mathbb {F}_q$
, we have
$(kv)g=k^{\sigma _1}(vg)=k^{\sigma _2}(vg)$
. In particular, as
$g \neq 0$
, there exists
$v_0 \in V$
such that
$(v_0)g \neq 0$
. Therefore,
$k^{\sigma _1}(v_0 g)=k^{\sigma _2}(v_0 g)$
, which implies
$k^{\sigma _1}=k^{\sigma _2}$
, for any
$k \in \mathop {\text {Aut}}{(\mathbb {F}_q)}$
, and so
$\sigma _1=\sigma _2$
. -
(b) Let
$v_1, v_2 \in V$
and
$k \in \mathbb {F}_q$
, then-
–
$(v_1 + v_2)g \sigma ^{-1}= (v_1)g \sigma ^{-1} + (v_2)g \sigma ^{-1}$
; -
–
$(kv_1)g \sigma ^{-1}= (k^{\sigma }(v_1g))\sigma ^{-1}= k((v_1)g \sigma ^{-1})$
.
Hence,
$g\sigma ^{-1}$
is linear. -
-
(c) From (b), it follows that there exists
$h \in \text {Hom}_{\mathbb {F}_q}{(V,W)}$
such that
$g\sigma ^{-1}=h$
. Hence,
$g=h\sigma $
. Assume that there exist
$h_1,h_2 \in \text {Hom}_{\mathbb {F}_q}{(V,W)}$
such that
$g=h_1\sigma =h_2\sigma $
. Then, for any
$v \in V$
, we have
$(v)h_1 \sigma =(v)h_2 \sigma $
, which implies that
$(v)h_1=(v)h_2$
. So, we conclude that
$h_1=h_2$
.
Now, let
$V= W \oplus X$
, for some
$W,X \leq V$
. Then, every
$v \in V$
can be written uniquely as
$v=w+x$
, for some
$w \in W$
and
$x \in X$
. Let
$f_W \in \text {End}^s_{\mathbb {F}_q}{(W)}$
and
$f_X \in \text {End}^s_{\mathbb {F}_q}{(X)}$
. We define
$f_W \oplus f_X \in \text {End}^s_{\mathbb {F}_q}{(V)}$
as
$v(f_W \oplus f_X) = wf_W + xf_X $
.
Remark 7.4. Let
$V = W \oplus X$
, for some
$W,X \leq V$
. Let
$g \in \text {End}^s_{\mathbb {F}_q}{(V)}$
. Then, g can be written as
, provided
$g(W) \leq W$
and
$g(X) \leq X$
.
Finally, if
$v_1,\dots, v_k \in V$
, then we write
$\left \langle v_1,\dots, v_k \right \rangle _{\mathbb {F}_q}$
to denote the
$\mathbb {F}_q$
-span of
$v_1,\dots, v_k$
.
7.3.
$G\leq \text {PGL}_n(q)$
Let V be n-dimensional over
$\mathbb {F}_q$
. In what follows, we write
${\textrm{M}}_{{n}}{{(q)}}$
for the set of all linear transformations
$V\to V$
. Note that it will be convenient to swap between thinking of
$\textrm{GL}_n(q)$
or
$\text {PGL}_n(q)$
, depending on context—this makes no difference to the calculations in question, as the center of
$\textrm{SL}_n(q)$
is the kernel of the action on
$\Omega $
.
The following lemma is crucial.
Lemma 7.5. Let
$\textrm{SL}_{n}{(q)} \leq G \subset \textrm{GL}_n(q)$
act on
$\Omega $
. Let
$\Lambda = \left \{W_1, \dots, W_{\ell }\right \} \subseteq \Omega $
be an independent set for the action of G on
$\Omega $
, of maximal size. Then,
$$ \begin{align*}\dim \left\langle W_1, \dots, W_{\ell} \right\rangle_{\mathbb{F}_q}> n-m.\end{align*} $$
Proof. Let
$W = \left \langle W_1, \dots, W_{\ell } \right \rangle _{\mathbb {F}_q} $
and suppose, first, that
$k = \dim {W} = n-m$
. Then, we can assume, by transitivity, that
$W= \left \langle e_1, \dots, e_{n-m} \right \rangle _{\mathbb {F}_q}$
.
Hence,
$$ \begin{align*} G_{(\Lambda)} \leq \left\{ \left(\begin{array}{@{}c|c@{}} \begin{matrix} A \end{matrix} & \begin{matrix} 0 \end{matrix}\\ \hline \begin{matrix} B \end{matrix} & \begin{matrix} C \end{matrix} \end{array} \right) \mid A \in {\textrm{M}}_{{n-m}}{{(q)}}, B \in {\textrm{M}}_{{m,n-m}}{{(q)}}, C \in {\textrm{M}}_{{m}}{{(q)}} \right\}. \end{align*} $$
Now, we add to
$\Lambda $
the following m-subspace:
$$ \begin{align*} X= \left\langle e_{n-m+1}, \dots, e_n \right\rangle_{\mathbb{F}_q}, \end{align*} $$
and we denote
$\bar {\Lambda }= \Lambda \cup \lbrace X \rbrace $
. Hence, by the maximality of
$\Lambda $
, we get
$$ \begin{align*} G_{(\bar{\Lambda})}= G_{(\bar{\Delta})}, \end{align*} $$
for some
$\bar {\Delta } \subseteq \bar {\Lambda }$
.
We distinguish three cases:
-
Case I : if
$\bar {\Delta } = \Lambda $
, then
$G_{(\bar {\Lambda })}=G_{(\Lambda)}$
. Now, but
$$ \begin{align*} G_{(\bar{\Lambda})} \leq \left\{ \left(\begin{array}{@{}c|c@{}} \begin{matrix} A \end{matrix} & \begin{matrix} 0 \end{matrix}\\ \hline \begin{matrix} 0 \end{matrix} & \begin{matrix} C \end{matrix} \end{array} \right) \mid A \in {\textrm{M}}_{{n-m}}{{(q)}}, C \in {\textrm{M}}_{{m}}{{(q)}} \right\}, \end{align*} $$
and this is a contradiction.
$$ \begin{align*} G_{(\Lambda)} \geq \left\{ \left(\begin{array}{@{}c|c@{}} \begin{matrix} I \end{matrix} & \begin{matrix} 0 \end{matrix}\\ \hline \begin{matrix} B \end{matrix} & \begin{matrix} I \end{matrix} \end{array} \right) \mid B \in {\textrm{M}}_{{m,n-m}}{{(q)}}, B \neq 0 \right\}, \end{align*} $$
-
Case II : if
$\bar {\Delta } \subset \Lambda $
, then
$G_{(\Lambda)} \leq G_{(\bar {\Delta })}$
. On the other hand,
$ G_{(\bar {\Delta })} = G_{(\bar {\Lambda })} \leq G_{(\Lambda)} $
, which implies
$G_{(\Lambda)} = G_{(\bar {\Delta })}$
, and hence a contradiction of the independence of
$\Lambda $
. -
Case III : if
$\bar {\Delta } \subsetneq \Lambda $
, then
$X \in \bar {\Delta }$
and we denote
$\Delta = \bar {\Delta } \setminus \lbrace X \rbrace $
. It is sufficient to prove that
$G_{(\Lambda)} = G_{(\Delta)}$
, as this leads to a contradiction. Observe that
$V = W \oplus X$
, and so, for any
$g \in \text {End}_{\mathbb {F}_q}{(V)}$
, we can defineand
$$ \begin{align*} \pi_W \colon \text{End}_{\mathbb{F}_q}{(V)} &\to \text{Hom}_{\mathbb{F}_q}{(W,V)} \\ g &\mapsto g\raise-.5ex\hbox{$|$}_{W} \end{align*} $$
$$ \begin{align*} \pi_X \colon \text{End}_{\mathbb{F}_q}{(V)} &\to \text{Hom}_{\mathbb{F}_q}{(X,V)} \\ g &\mapsto g\raise-.5ex\hbox{$|$}_{X}. \end{align*} $$
Now, if
$g \in G_{(\bar {\Lambda })}$
or if
$g \in G_{(\bar {\Delta })}$
, then
and
, which, by Remark 7.4, imply that
. Therefore, we have thatandHence,
$G_{(\bar {\Lambda })}= G_{(\bar {\Delta })}$
implies (7.3)On the other hand,
$$ \begin{align} \pi_W(G_{(\Lambda)})=\pi_W(G_{(\Delta)}). \end{align} $$
and
$$ \begin{align*} g \in G_{(\Lambda)} \Leftrightarrow g\raise-.5ex\hbox{$|$}_{W} \in \pi_W(G_{(\Lambda)}) \end{align*} $$
Therefore, by (7.3), we get
$$ \begin{align*} g \in G_{(\Delta)} \Leftrightarrow g\raise-.5ex\hbox{$|$}_{W} \in \pi_W(G_{(\Delta)}). \end{align*} $$
$G_{(\Lambda)}= G_{(\Delta)}$
.
Finally, if
$k < n-m$
, then we can assume, by transitivity, that
$W = \left \langle e_1, \dots, e_k \right \rangle _{\mathbb {F}_q}$
and consider
$V_0 = \left \langle e_1, \dots, e_{k+m} \right \rangle _{\mathbb {F}_q} \leq V$
. Let
$X= \left \langle e_{k+1}, \dots, e_{k+m} \right \rangle _{\mathbb {F}_q}$
. Hence, we can apply to
$V_0$
the same argument as before, which leads to a contradiction.
The next lemma yields Lemma 7.2 provided
$G\leq \text {PGL}_n(q)$
.
Lemma 7.6. Let G be an almost simple group with socle
$\textrm{PSL}_n(q)$
, such that
$\textrm{PSL}_n(q) \unlhd G \leq \text {PGL}_n(q)$
, acting on
$\Omega $
, the set of all m-spaces in V. Then,
$$ \begin{align*} \textrm{H}(G) <4 \log t. \end{align*} $$
Moreover,
$$ \begin{align*}\textrm{H}(G)<2\min(m,n-m)n.\end{align*} $$
Proof. As usual, we may suppose
$m\le n/2$
and
$G=\text {PGL}_n(q)$
. Moreover, from the opening paragraph of Section 7.3, we may work with the linear group
$\textrm{GL}_n(q)$
and hence we may suppose
$G=\textrm{GL}_n(q)$
. Let
$\Lambda $
be an independent set for the action of G on
$\Omega $
, of maximal size. The previous lemma allows us to order
$\Lambda = \left \{W_1, \dots, W_k, \dots \right \}$
, so that
$$ \begin{align*} \dim \left\langle W_1, \dots, W_j \right\rangle_{\mathbb{F}_q}> \dim \left\langle W_1, \dots, W_{j-1} \right\rangle_{\mathbb{F}_q}, \end{align*} $$
for
$j \leq k$
, where
$\dim {(\Lambda)}= \dim (\left \langle W_1, \dots, W_k \right \rangle _{\mathbb {F}_q})> n-m$
. Now,
$\Lambda $
is an independent set for
$M=M_n(q)$
(see Section 7.2 for the definition of independent set for the algebra of n-by-n matrices over the finite field
$\mathbb {F}_q$
). Consider the following iterated process for
$i \leq k$
:
-
Step 1. Let
$W_1 \in \Omega $
. We define
$W = W_1$
. We recall that we may assume, without loss of generality, that
$W = \left \langle e_1, \dots, e_m \right \rangle _{\mathbb {F}_q}$
and that
$$ \begin{align*} M_W = \left\{ \left(\begin{array}{@{}c|c@{}} \begin{matrix} A \end{matrix} & \begin{matrix} 0 \end{matrix}\\ \hline \begin{matrix} B \end{matrix} & \begin{matrix} C \end{matrix} \end{array}\right) \mid A \in {\textrm{M}}_{{m}}{{(q)}}, B \in {\textrm{M}}_{{n-m,m}}{{(q)}}, C \in {\textrm{M}}_{{n-m}}{{(q)}} \right\}. \end{align*} $$
-
Step i . We have
$W_1, \dots, W_{i-1}$
and we define
$W = \left \langle W_1, \dots, W_{i-1} \right \rangle _{\mathbb {F}_q}$
. Let
$\dim W = h$
and assume, without loss of generality, that
$W=\left \langle e_1, \dots, e_{h} \right \rangle _{\mathbb {F}_q}$
. Since we have chosen a specific ordering, we have that
$W_i$
satisfies Consider
$$ \begin{align*}\dim \left\langle W_1, \dots, W_i \right\rangle_{\mathbb{F}_q}> \dim W.\end{align*} $$
$V / W$
and
$(W_i+W) / W\cong W_i/(W_i\cap W)$
. Now let
$\dim (W_i+W)/W= j$
, observe that
$j \in \left \{1, \dots, m\right \}$
. Then, we may assume for some
$$ \begin{align*} W_i = \left\langle v_1, \dots, v_{m-j}, e_{h+1}, \dots, e_{h+j} \right\rangle_{\mathbb{F}_q}, \end{align*} $$
$v_1, \dots, v_{m-j} \in W$
and
$e_{h+1}, \dots, e_{h+j} \notin W$
.
Hence,
$\dim \left (W \cap W_i\right) = m-j$
, and we can write
$$ \begin{align*} W_i = (W \cap W_i) \oplus \left\langle e_{h+1}, \dots, e_{h+j} \right\rangle_{\mathbb{F}_q}. \end{align*} $$
Let
$r\in \{h+1,\ldots,h+j\}$
, and let
$g \in M_{W_1, \dots, W_i}$
; observe that
$e_{r}^g \in W_i$
. Hence,
$e_{r}^g = u_1 + u_2$
, for some
$u_1 \in W \cap W_i$
and
$u_2 \in \left \langle e_{h+1}, \dots, e_{h+j} \right \rangle _{\mathbb {F}_q}$
. Therefore, we have
$$ \begin{align*} \dim \left\langle \right\{ e_r^g \mid g \in M_{W_1, \dots, W_i} \left\} \right\rangle_{\mathbb{F}_q}\le m,\,\,\, \mbox{ for all } r =h+1, \dots, h+j. \end{align*} $$
This iteration will end after k steps, and hence,
$$ \begin{align*} \dim M_{W_1, \dots, W_{k}} \leq m(n-s) + ns, \end{align*} $$
where
$s:=n-\dim \langle W_1,\ldots,W_k\rangle $
. We conclude that
$|\Lambda | \leq k+ m(n-s) + ns$
, and so we have
$$ \begin{align*} \textrm{H}(G) \leq k+ m(n-s) + ns. \end{align*} $$
Now, observe that k is maximum when
$j=1$
at each step, in which case
$k = n-m-s$
. Hence,
$$ \begin{align} \textrm{H}(G) \leq (n-m-s)+ ns+ m(n-s). \end{align} $$
By Lemma 7.5, we have
$s\le m-1.$
We conclude that the right-hand-side of (7.4) is maximized when
$s=m-1$
. Then,
$$ \begin{align*} \textrm{H}(G) \leq 2mn-m^2-m+1, \end{align*} $$
and, as
$m \geq 1$
implies
$m^2+m-1>0$
, we conclude that
$$ \begin{align*} \textrm{H}(G) < 2mn. \end{align*} $$
Now, observe that
$$ \begin{align*} \frac{mn}{m(n-m)} \leq 2 \Leftrightarrow m \leq \frac{n}{2}. \end{align*} $$
Then, as
$\log q \geq 1$
, we have
$$ \begin{align*} \frac{mn}{m(n-m)} \leq 2 \leq 2 \log q. \end{align*} $$
This implies that
$$ \begin{align*}2mn \leq 4 \log q^{m(n-m)}. \end{align*} $$
Hence, using (7.2), we obtain
$$ \begin{align*}\textrm{H}(G) < 2mn < 4 \log t.\\[-40pt] \end{align*} $$
Note that, in Bianca Lodà’s thesis, a precise version of Lemma 7.6 is given for the case
$m=1$
. It turns out that, for
$\textrm{PSL}_n(q)\unlhd G\leq \text {PGL}_n(q)$
acting on
$\Omega $
, the set of all
$1$
-spaces in V, we have
$$ \begin{align*} \textrm{H}(G,\Omega)=\begin{cases} n, & \text{if} q=2; \\ 2n-2, & \text{if} q>2. \end{cases} \end{align*} $$
7.4.
$G\not \leq \text {PGL}_n(q)$
We can finally prove Lemma 7.2.
Proof Proof of Lemma 7.2
Let
$q=p^f$
. Suppose, first, that
$$ \begin{align*} \text{PSL}_n(q) \unlhd G \leq \text{P}\Gamma\text{L}_n(q) = \text{PGL}_n(q) \rtimes \mathcal{C}_f. \end{align*} $$
Now, Lemma 2.8 implies that
$$ \begin{align*} \textrm{H}(G) \leq \textrm{H}(\text{PGL}_n(q)) + \ell(\mathcal{C}_f), \end{align*} $$
where
$\ell (\mathcal {C}_f)$
is the maximum length of a strictly descending chain of subgroups in
$\mathcal {C}_f$
. Since
$\ell (\mathcal {C}_f) \leq \log f =\log \log _p q$
, we obtain
$$ \begin{align*} \textrm{H}(G) < \textrm{H}(\text{PGL}_n(q))+\log \log_p{q}. \end{align*} $$
From Lemma 7.6, we immediately deduce (7.1) when
$m<n/2$
and we also get
$$ \begin{align*} \textrm{H}(G) < 4\log t+\log \log_p{q}. \end{align*} $$
By (7.2), we easily conclude
$\log \log _pq<\log t$
and hence
$$ \begin{align*} \textrm{H}(G) < 5 \log t. \end{align*} $$
We must deal with the possibility that
$G\not \leq \textrm{P}\Gamma \textrm{L}_n(q)$
, that is, G contains a graph automorphism. In this case,
$n\geq 4$
,
$m=\frac {n}{2}$
, and G contains a subgroup, H, of index
$2$
that lies in
$\textrm{P}\Gamma \textrm{L}_n(q)$
. By the argument above, we know that
$$ \begin{align*} \textrm{H}(H)<5\log t. \end{align*} $$
Now, Lemma 2.8 implies that
$$ \begin{align*} \textrm{H}(G)<5\log t+1 <\frac{11}{2}\log t.\\[-40pt] \end{align*} $$
We remark that in Lemma 7.6 we chose a particular ordering of our independent set
$\Lambda $
when we came to study the associated stabilizer chain. We can do this because we are studying
$\textrm{H}(G)$
rather than
$\textrm{I}(G)$
—it is precisely this ordering step which has prevented us from proving a strong enough version of Theorem 1.6 to confirm Conjecture 1.7.
7.5.
$G_0=\text {PSL}_n(q)$
and elements of
$\Omega $
are pairs of subspaces
In this section, we consider the primitive subspace actions of those almost simple groups with socle
$\textrm{PSL}_n(q)$
that contain an automorphism of the Dynkin diagram.
Let
$n \geq 3$
, and fix m, an integer satisfying
$1\le m<\frac {n}{2}$
. We denote by
$\Omega _m$
the set of all m-subspaces of V. We consider the action of G on
$\Omega ^{(i)}$
, for
$i=1,2$
, where
$$ \begin{align*} &\Omega^{(1)}= \left\{ \{U,W\} \mid U,W \leq V, \dim{U}=m, \dim{W}=n-m \text{ with } m< \frac{n}{2} \text{ and } U \oplus W= V \right\},\\ &\Omega^{(2)}= \left\{ \{U,W\} \mid U,W \leq V, \dim{U}=m, \dim{W}=n-m \text{ with } m< \frac{n}{2} \text{ and } U<W \right\}. \end{align*} $$
The main result of this section is the following.
Lemma 7.7. Let G be an almost simple group with socle
$\textrm{PSL}_n(q)$
acting on
$\Omega ^{(1)}$
or
$\Omega ^{(2)}$
. Then,
$$ \begin{align*} \textrm{H}(G) < \frac{17}{2}\log t. \end{align*} $$
We set
$t^{(i)}:= |\Omega ^{(i)}|$
, for
$i=1,2$
. Then, we have
$$ \begin{align*}t^{(1)}=\frac{q^{m(n-m)}\prod_{i=1}^{n}{(q^i-1)}}{\prod_{i=1}^{m}{(q^i-1)}\prod_{i=1}^{n-m}{(q^i-1)}} \,\,\text{ and }\,\, t^{(2)}=\frac{\prod_{i=1}^{n}{(q^i-1)}}{\prod_{i=1}^{m}{(q^i-1)^2}\prod_{i=1}^{n-2m}{(q^i-1)}}.\end{align*} $$
We saw already, in (7.2), that
$|\Omega _m|>q^{m(n-m)}$
. We obtain immediately that
$$ \begin{align} t^{(i)}\geq q^{m(n-m)}. \end{align} $$
For the time being, for various technical reasons, we consider
$G\le \textrm{P}\Gamma \textrm{L}_n(q)$
(although the corresponding actions are not primitive any longer). We simultaneously study the action of G on
$\Omega ^{(1)}$
and
$\Omega ^{(2)}$
. Let
$\Lambda \subset \Omega ^{(i)}$
be an independent set for the action of G on
$\Omega ^{(i)}$
, with
$k:=|\Lambda |$
. We define
$$ \begin{align} &\mathcal{U} = \lbrace U\in\Omega_m\mid \text{there exists }W\in \Omega_{n-m} \text{ with }\{U,W\}\in\Lambda \rbrace; \end{align} $$
$$ \begin{align} & \mathcal{W} =\lbrace W\in\Omega_{n-m}\mid \text{there exists }U\in \Omega_{m} \text{ with }\{U,W\}\in\Lambda \rbrace. \end{align} $$
Let
$k_U:=|\mathcal {U}|$
and
$k_W:=|\mathcal {W}|$
. Clearly,
$k_U,k_W \leq |\Lambda |=k$
.
Notice that, since
$G\le \textrm{P}\Gamma \textrm{L}_n(q)$
, G acts naturally on
$\Omega _m$
and
$\Omega _{n-m}$
; however, observe that, a priori, the independence of
$\Lambda $
does not imply the independence of
$\Lambda _U$
and
$\Lambda _W$
. The result that we need is the following.
Lemma 7.8.
$k \leq \textrm{H}(G,\Omega _m)+ \textrm{H}(G,\Omega _{n-m}).$
In order to prove Lemma 7.8, we first need to define a graph
$\Gamma $
associated with
$\Lambda $
in the following way:
$\Gamma = (V,\Lambda)$
, where
$V= \mathcal {U} \cup \mathcal {W}$
is the vertex set and the edge set is
$\Lambda $
.
From here, we will first prove a general fact about the length of paths in the graph
$\Gamma $
, and we will then split our proof of Lemma 7.8 into two steps: the first is a special case, which illustrates the general case; this general case will come second.
Lemma 7.9. The graph
$\Gamma $
can only have paths of length at most 2.
Proof. Assume that in
$\Gamma $
we have a path of length at least 3. Then, relabeling if necessary, we have
for some
$1 \leq i < k_U$
,
$1 \leq j < k_W$
. As
$G\le \textrm{P}\Gamma \textrm{L}_n(q)$
, G preserves the two parts
$\Lambda _U$
and
$\Lambda _W$
of the natural bipartition of
$\Gamma $
. Hence,
$$ \begin{align*} G_{\{U_i,W_j\},\{U_{i+1},W_{j+1}\}}=G_{U_i}\cap G_{W_j}\cap G_{U_{i+1}}\cap G_{W_{j+1}}=G_{\{U_i,W_j\},\{U_{i},W_{j+1}\},\{U_{i+1},W_{j+1}\}}. \end{align*} $$
As
$\{U_i,W_{j}\}$
,
$\{U_{i},W_{j+1}\}$
,
$\{U_{i+1},W_{j+1}\}$
are elements in
$\Lambda $
, this contradicts the independence of
$\Lambda $
.
7.6. Suppose that
$\Gamma $
is a complete matching
In other words, we suppose
$\Gamma $
has no paths of length
$2$
. This case will illustrate the general argument very well.
In this case,
$\Lambda =\{\{U_1,W_1\},\ldots,\{U_k,W_k\}\}$
. Let us consider the action of G on
$\Omega _m$
. By Lemma 2.4, there exists
$\mathcal {I} \subset \{1, \dots, k\}$
, say
$\mathcal {I}= \{i_1, \dots, i_s\}$
, such that
$\{U_{i_1}, \dots, U_{i_s}\}$
is an independent set and
$$ \begin{align*} \bigcap_{j=1}^{k}{G_{U_i}}=\bigcap_{j=1}^{s}{G_{U_{i_j}}}. \end{align*} $$
After relabeling elements, we can assume
$\mathcal {I}= \{1, \dots, s\}$
. This yields
$$ \begin{align*} s \leq \textrm{H}(G, \Omega_{m}). \end{align*} $$
Let
$$ \begin{align*} H:= \bigcap_{i=1}^{s}{\left(G_{U_i} \cap G_{W_i}\right)} \end{align*} $$
and consider its action on
$\Omega ^{(i)}$
, for
$i \in \{1,2\}$
. Recall that, by Lemma 2.2, the set
$$ \begin{align*} \Delta=\{\{U_{s+1}, W_{s+1}\}, \dots, \{U_k,W_k\}\} \end{align*} $$
is independent with respect to H. Now, consider the action of H on
$\Omega _{n-m}$
.
Lemma 7.10. The set
$\{W_{s+1}, \dots, W_k\}$
is independent with respect to the action of H on
$\Omega _{n-m}$
.
Proof. Assume, for contradiction, that the set
$\{W_{s+1}, \dots, W_k\}$
is not independent with respect to H. Then, by Lemma 2.3, there would exist
$j \in \{s+1, \dots k\}$
such that
$$ \begin{align*}\bigcap_{i=s+1}^{k}{H_{W_i}}=\bigcap_{\substack{i=s+1\\i \neq j}}^{k}{H_{W_i}}.\end{align*} $$
Observe that
$$ \begin{align*} \bigcap_{i=1}^{s}{G_{U_i}}=\bigcap_{i=1}^{k}{G_{U_i}}=\bigcap_{\substack{i=1\\i \neq j}}^{k}{G_{U_i}}. \end{align*} $$
Therefore, we have
$$ \begin{align*} G_{(\Lambda)}&= H \cap \bigcap_{i=s+1}^{k}{G_{W_i}} = \bigcap_{i=s+1}^{k}{H_{W_i}} = \bigcap_{\substack{i=s+1 \\ i \neq j}}^{k}{H_{W_i}} \\ &= H \cap \left(\bigcap_{\substack{i=s+1 \\ i \neq j}}^{k}{G_{W_i}}\right) = \left( \bigcap_{i=1}^{s}{G_{U_i}} \cap \bigcap_{i=1}^{s}{G_{W_i}} \right) \cap \left(\bigcap_{\substack{i=s+1 \\ i \neq j}}^{k}{G_{W_i}} \right) \\ &= \left( \bigcap_{\substack{i=1 \\ i \neq j}}^{k}{G_{U_i}} \right) \cap \left( \bigcap_{\substack{i=1 \\ i \neq j}}^{k}{G_{W_i}} \right) = \bigcap_{\substack{i=1 \\ i \neq j}}^{k}{\left(G_{U_i} \cap G_{W_i}\right)} \\ &= G_{(\Lambda \setminus \{\{U_j,W_j\}\})}. \end{align*} $$
This contradicts the independence of
$\Lambda $
.
The previous lemma implies that
$$ \begin{align*}k-s \leq \textrm{H}(H, \Omega_{n-m}). \end{align*} $$
Now, by Lemma 2.2, we have
$\textrm{H}(H, \Omega _{n-m}) \leq \textrm{H}(G, \Omega _{n-m})$
. Putting these things together yields that
$$ \begin{align*}k \leq \textrm{H}(G,\Omega_m)+ \textrm{H}(G,\Omega_{n-m}),\end{align*} $$
and Lemma 7.8 is proved in this special case.
7.7. Suppose that
$\Gamma $
is not a complete matching
The general argument is very similar but requires some more notation. After reordering the vertices of
$\Gamma $
and using a suitable labeling, the fact that
$\Gamma $
has no paths of length
$3$
implies that
$\Gamma $
is isomorphic to the graph in Figure 1, where
$\ell _1,\dots,\ell _b, s_1,\ldots, s_c \geq 2$
.
The graph
$\Gamma $
in the general case.
Observe that, by definition, we have
$k_U$
vertices on the left,
$k_W$
vertices on the right, and k edges, because these are the elements of
$\Lambda $
. Let us consider the action of G on
$\Omega _m$
, that is, we focus on the action of G on the vertices on the left-hand side of the graph. By Lemma 2.4, there exists a subset
$\mathcal {U}_1$
of
$\mathcal {U}$
, such that
$\mathcal {U}_1$
is an independent set and
$$ \begin{align} \bigcap_{U \in \mathcal{U}}{G_{U}}= \bigcap_{U \in \mathcal{U}_1}{G_{U}}. \end{align} $$
Let
$s:= |\mathcal {U}_1|.$
We reorder the vertices on the left-hand side of the graph, so that the elements of
$\mathcal {U}_1$
occur in the top s positions. Simultaneously, we take to the top exactly one edge, chosen arbitrarily, having one end in U, for each
$U \in \mathcal {U}_1$
. Note that here we allow crossings between edges. Observe that Lemma 7.9 implies that this operation is well defined. We have
$$ \begin{align*} s \leq \textrm{H}(G,\Omega_m). \end{align*} $$
Let
$\Lambda _{\mathcal {U}_1} \subset \Lambda $
be the set of those chosen edges and note that
$|\Lambda _{\mathcal {U}_1}|=s$
. We define
$$ \begin{align*} \mathcal{W}_1 &= \left\{ W \in \mathcal{W} \mid W \text{ is an end point for an edge in } \Lambda_{\mathcal{U}_1} \right\}, \\ \mathcal{W}_2 &=\mathcal{W}\setminus \mathcal{W}_1. \end{align*} $$
Observe that
$|\mathcal {W}_1| \leq s$
.
Lemma 7.11. Let
$H:= G_{(\Lambda _{\mathcal {U}_1})}$
. Let
$\lambda \in \Lambda \setminus \Lambda _{\mathcal {U}_1}$
, and let
$U_{\lambda }$
and
$W_{\lambda }$
be, respectively, its left-hand end point and right-hand end point. Then, we have that
-
1. the function
is a bijection. In particular,
$$ \begin{align*} f \colon &\Lambda \setminus \Lambda_{\mathcal{U}_1} \to \mathcal{W}_2 \\ &\lambda \mapsto W_{\lambda} \end{align*} $$
$|\mathcal {W}_2|=|\Lambda \setminus \Lambda _{\mathcal {U}_1}| =k-s$
;
-
2.
$G_{(\Lambda)}= H_{(\mathcal {W}_2)}$
.
Proof. To prove claim (1), we first prove that f is well defined. We claim that
$W_{\lambda } \in \mathcal {W}_2$
. Indeed, if
$W_{\lambda } \in \mathcal {W}_1$
, then
$$ \begin{align*} G_{(\Lambda_{\mathcal{U}_1})} &= \bigcap_{\substack{U \in \mathcal{U}_1 \\ W \in \mathcal{W}_1}}{\left(G_{U} \cap G_{W}\right)} \\ &= \left(\bigcap_{U \in \mathcal{U}_1 \cup \left\{U_{\lambda}\right\}}{G_U}\right)\cap\left(\bigcap_{W \in \mathcal{W}_1}{G_W}\right) \\ &= G_{(\Lambda_{\mathcal{U}_1} \cup \left\{\lambda\right\})}, \end{align*} $$
which contradicts the independence of
$\Lambda $
. This fact implies that f is well defined. Moreover, it is onto by definition. Finally, we prove that f is one-to-one. Assume that there exist two distinct edges
$\lambda, \mu \in \Lambda \setminus \Lambda _{\mathcal {U}_1}$
such that
$W_{\lambda }=W_{\mu }$
. Then, by using (7.8), we have
$$ \begin{align*} G_{(\Lambda_{\mathcal{U}_1} \cup \left\{\lambda,\mu\right\})} &= \bigcap_{\substack{U \in \mathcal{U}_1 \\ W \in \mathcal{W}_1}}{\left(G_{U} \cap G_{W}\right)} \cap \left(G_{U_{\lambda}}\cap G_{W_{\lambda}}\right) \cap \left(G_{U_{\mu}}\cap G_{W_{\mu}}\right)\\ &= \left(\bigcap_{U \in \mathcal{U}_1 \cup \left\{U_{\lambda}\right\} \cup \left\{U_{\mu}\right\}}{G_U}\right)\cap \left(\bigcap_{W \in \mathcal{W}_1 \cup \left\{W_{\lambda}\right\}}{G_W}\right) \\ &= \left(\bigcap_{U \in \mathcal{U}_1 \cup \left\{U_{\lambda}\right\}}{G_U}\right)\cap \left(\bigcap_{W \in \mathcal{W}_1 \cup \left\{W_{\lambda}\right\}}{G_W}\right) \\ &= G_{(\Lambda_{\mathcal{U}_1} \cup \left\{\lambda\right\})}, \end{align*} $$
which is a contradiction. Hence, f is a bijection, in particular
$|\mathcal {W}_2|=|\Lambda \setminus \Lambda _{\mathcal {U}_1}|= k-s$
.
For part (2), by using the previous result and (7.8), we have
$$ \begin{align*} G_{(\Lambda)} &= G_{(\Lambda_{\mathcal{U}_1})} \cap G_{(\Lambda \setminus \Lambda_{\mathcal{U}_1})} = H \cap G_{(\Lambda \setminus \Lambda_{\mathcal{U}_1})} \\ &= H \cap \left( \bigcap_{\lambda \in \Lambda \setminus \Lambda_{\mathcal{U}_1}}{G_{U_{\lambda}} \cap G_{W_{\lambda}}}\right) \\ &= \left(H \cap \bigcap_{\lambda \in \Lambda \setminus \Lambda_{\mathcal{U}_1}}{G_{U_{\lambda}}}\right) \cap \left(H \cap \bigcap_{\lambda \in \Lambda \setminus \Lambda_{\mathcal{U}_1}}{G_{W_{\lambda}}}\right) \\ &= H \cap \left(\bigcap_{W \in \mathcal{W}_2}{G_W}\right) =H_{(\mathcal{W}_2)}.\\[-40pt] \end{align*} $$
Now, consider the action of H on
$\Omega _{n-m}$
, namely we focus on the vertices on the right-hand side of the graph. As a consequence of the previous lemma, we obtain the following corollary.
Corollary 7.12. The set
$\mathcal {W}_2$
is independent for the action of H on
$\Omega _{n-m}$
.
Proof. Assume not, then there would exist
$\lambda \in \Lambda \setminus \Lambda _{\mathcal {U}_1}$
such that
$$ \begin{align*} H_{(\mathcal{W}_2)} =\bigcap_{W \in \mathcal{W}_2 }{H_{W}} = \bigcap_{\substack{W \in \mathcal{W}_2 \\ W \neq W_{\lambda}} }{H_{W}}. \end{align*} $$
If
$U_{\lambda } \in \mathcal {U}_1$
, then there exists
$\mu \in \Lambda _{\mathcal {U}_1}$
such that
$U_{\lambda }=U_{\mu }$
. If
$U_{\lambda } \not \in \mathcal {U}_1$
, then
$\bigcap \limits _{U\in \mathcal {U}} G_U = \bigcap \limits _{U\in \mathcal {U}, U\neq U_{\lambda }} G_U$
.
In either case, this, along with (7.8) and part (2) of the previous lemma, implies that
$$ \begin{align*} G_{(\Lambda \setminus \left\{\lambda \right\})}&= \left(\bigcap_{U \in \mathcal{U} }{G_{U}}\right) \cap \left(\bigcap_{\substack{W \in \mathcal{W} \\ W \neq W_{\lambda}}}{G_{W}}\right)\\ &= \left(\bigcap_{U \in \mathcal{U}_1}{G_{U}} \cap \bigcap_{W \in \mathcal{W}_1}{G_{W}}\right) \cap \left(\bigcap_{\substack{W \in \mathcal{W}_2 \\ W \neq W_{\lambda}}}{G_{W}} \right) \\ &= H \cap \bigcap_{\substack{W \in \mathcal{W}_2 \\ W \neq W_{\lambda}} }{G_{W}} \\ &= \bigcap_{\substack{W \in \mathcal{W}_2 \\ W \neq W_{\lambda}} }{H_{W}}=H_{(\mathcal{W}_2)}=G_{(\Lambda)}. \end{align*} $$
This contradicts the independence of
$\Lambda $
.
The previous lemma implies that
$$ \begin{align*}k-s \leq \textrm{H}(H, \Omega_{n-m}). \end{align*} $$
Now, by Lemma 2.2, we have
$\textrm{H}(H, \Omega _{n-m}) \leq \textrm{H}(G, \Omega _{n-m})$
. Putting these things together yields that
$$ \begin{align*}k \leq \textrm{H}(G,\Omega_m)+ \textrm{H}(G,\Omega_{n-m}),\end{align*} $$
and Lemma 7.8 is proved in the general case. We are ready to prove Lemma 7.7.
Proof Proof of Lemma 7.7
Suppose, first, that
$G\leq \textrm{P}\Gamma \textrm{L}_n(q)$
. Recall that the actions of G on
$\Omega _m$
and
$\Omega _{n-m}$
are permutation isomorphic. Thus, Lemma 7.8 and (7.1) imply that
$$ \begin{align*} \textrm{H}(G, \Omega^{(i)}) < 4mn+2\log\log_pq. \end{align*} $$
Here, we are tacitly assuming that
$m<n/2$
, because, for instance, (7.1) does use the hypothesis that
$m<n/2$
. However, this is not a restriction, because the duality conjugates the m-space stabilisers in
$(n-m)$
-space stabilisers.
Now, let
$G \nleq \textrm{P}\Gamma \textrm{L}_n{(q)}$
, that is, G contains the inverse transpose automorphism. Let
$H = G \cap \textrm{P}\Gamma \textrm{L}_n(q)$
. Then, H is a normal subgroup of G of index 2. Then, by Lemma 2.8, we have
$$ \begin{align*} \textrm{H}(G, \Omega^{(i)}) \leq \textrm{H}(H, \Omega^{(i)})+1, \end{align*} $$
and therefore,
$$ \begin{align} \textrm{H}(G, \Omega^{(i)}) < 4mn+2\log\log_pq +1. \end{align} $$
In view of (7.5), to prove the result, it is sufficient to check that
$$ \begin{align*} 4mn+2\log\log_pq +1 < \frac{17}{2}\log(q^{m(n-m)}). \end{align*} $$
The result follows directly.
7.8. The other classical groups
In this subsection, we suppose that
$G_0=\text {Cl}(V)$
is one of the other classical groups defined on a vector space V of dimension n over
$\mathbb {F}_q$
. In this case, m is an integer such that
$0<m<n$
and
$\Omega $
is a G-orbit on the set of totally isotropic/totally singular/nondegenerate subspaces of dimension m in V. As usual, we set
$t=|\Omega |$
.
The result that we need is the following.
Lemma 7.13. Let G be an almost simple group with socle
$\text {Cl}_n(q)$
, and consider G as a permutation group in a subspace action. Then,
$$ \begin{align*} \textrm{H}(G) < \frac{17}{2}\log t. \end{align*} $$
In [Reference Burness and GiudiciBG16, Table 4.1.2], we find a list of the degrees of all such actions and, using the notation just established, one can easily verify the following fact.
Lemma 7.14. Either
$G_0\cong \textrm{P}\Omega _n^+(q)$
and
$m=\frac {n}{2}$
or
$t>q^{\frac 12 m(n-m)}$
.
Proof. The proof of this lemma is rather tedious: it is simply a case-by-case analysis of the cases described in Table 4.1.2 of [Reference Burness and GiudiciBG16].
We make a couple of brief remarks about the proof and leave the details to the reader. Observe, first, that for a number of the cases (III, X with q odd, XI with q odd, XIII, XV, and XVI), t is divisible by
$q^{\frac 12 m(n-m)}$
, and so the result follows immediately.
For the rest, one must demonstrate the bound directly. To illustrate, we consider Case VI which is where the exception occurs; in this case,
$G_0\cong \textrm{P}\Omega _n^+(q)$
and
$m\leq \frac {n}{2}$
. Then, we have
$$ \begin{align*} t &= \frac{(q^{n/2}-1)(q^{(n-2m)/2}+1) \prod_{i=(n-2m)/2+1}^{(n-2m)/2+(m-1)}(q^{2i}-1)}{\prod_{i=1}^m(q^i-1)} \\ &= \frac{(q^{n/2}-1)(q^{(n-2m)/2}+1)}{q^m-1} \cdot \prod_{i=1}^{m-1}\left(\frac{q^{n-2m+2i}-1}{q^i-1}\right) \\ &> \frac{(q^{n/2}-1)(q^{(n-2m)/2}+1)}{q^m-1} \cdot \prod_{i=1}^{m-1}q^{n-2m+i} \\ &> q^{n/2-m+n/2-m} \cdot q^{(n-2m)(m-1)+\frac12(m-1)m} \\ &=q^{nm-\frac32m^2-m}. \end{align*} $$
Now, it is easy to check that the bound is satisfied if and only if
$m<\frac {n}{2}$
, as required.
We are ready to prove Lemma 7.13.
Proof Proof of Lemma 7.13
Observe, first, that
$G\leq \textrm{P}\Gamma \textrm{L}_n(q)$
and that the action we are studying is an action on
$\Gamma $
, the set of m-spaces. Then, Lemma 2.2 implies that
$$ \begin{align*} \textrm{H}(G,\Omega)\leq \textrm{H}(\text{P}\Gamma\text{L}_n(q), \Gamma). \end{align*} $$
In Lemma 7.2, we give an upper bound for
$\textrm{H}(\textrm{P}\Gamma \textrm{L}_n(q), \Gamma)$
:
$$ \begin{align*} \textrm{H}(G) < 2\min(m,n-m)n + \log \log_p{q}. \end{align*} $$
Thus, in light of Lemma 7.14, provided we do not have
$(G_0,m)=(\textrm{P}\Omega _n^+(q),\frac {n}{2})$
, it is enough to prove that
$$ \begin{align*} 2\min(m,n-m)n + \log \log_p{q} < \frac{17}{2}\log (q^{\frac12 m(n-m)}). \end{align*} $$
This is easily verified. Assume that
$(G_0,m)=(\textrm{P}\Omega _n^+(q),\frac {n}{2})$
. In this case,
$t\geq q^{\frac {n^2}{8}-\frac {n}{4}}$
. Lemma 6.13 implies that we can assume that
$n\geq 10$
, and thus,
$$ \begin{align*} |G|\leq 2fq^{n(n-2)/4}(q^{n/2}-1) \prod_{i=1}^{n/2-1}(q^{2i}-1) < 2f q^{\frac{n^2}{2}-\frac{n}{2}} \leq q^{\frac{n^2}{2}-\frac{n}{2}+1}. \end{align*} $$
Now, observe that
$$ \begin{align*} \textrm{H}(G) \leq \log |G| < \log(q^{\frac{n^2}{2}-\frac{n}{2}+1}) < 5 \log( q^{\frac{n^2}{8}-\frac{n}{4}}) < 5 \log t, \end{align*} $$
and we are done.
Proposition 7.1 is a consequence of Lemmas 7.2, 7.7, and 7.13.
Proof Proof of Theorem 1.3
Observe that
$17/2+3/(2x)<9$
, as long as
$x>3$
(so
$|\Delta |>8$
). With this remark, the proof follows from Theorem 1.6, and Propositions 5.1 and 7.1, except when G is a primitive group of PA type with
$G\le H\wr \mathop {\textrm{Sym}}(\ell)$
and the domain of G is
$\Omega =\Delta ^{\ell }$
and
$|\Delta |\le 8$
. If
$H=\mathop {\textrm{Alt}}(\Delta)$
or
$H=\mathop {\textrm{Sym}}(\Delta)$
, then G is a large–base group, and hence, we may omit these cases for the rest of the proof. As H is a primitive group of degree
$5,6,7$
, or
$8$
and as H is neither
$\mathop {\textrm{Alt}}(\Delta)$
nor
$\mathop {\textrm{Sym}}(\Delta)$
, we deduce that one of the following holds:
-
•
$|\Delta |=6$
and
$H=\textrm{PSL}_2(5)$
or
$H=\text {PGL}_2(5)$
in its natural action on the projective line, -
•
$|\Delta |=7$
and
$H=\textrm{PSL}_3(2)$
in its natural action on the projective plane, -
•
$|\Delta |=8$
and
$H=\textrm{PSL}_2(7)$
or
$H=\text {PGL}_2(7)$
in its natural action on the projective line.
In each of these groups, we have
$\textrm{H}(H)\le 3$
, and hence, from (5.1), we have
$\textrm{H}(G)\le 3\ell +3\ell /2=9\ell /2$
. As
$9\ell /2<9\log (t)$
, the proof is completed.
Acknowledgments
The results in this paper are based on the Ph.D. thesis of Bianca Lodà. The authors would like to thank Colva Roney-Dougal and Dugald Macpherson, who, in the course of examining the thesis, made many useful remarks which have helped to improve the current paper.
