2022

These authors contributed equally to this work.

[2]Ramón Esteban-Romero These authors contributed equally to this work.

These authors contributed equally to this work.

1]Departament de Matemàtiques, Universitat de València, Dr. Moliner, 50,
Burjassot, 46100, València, Spain

[2]Departament de Matemàtiques, Universitat de València, Dr. Moliner, 50,
Burjassot, 46100, València, Spain

3]Departamento de Matemáticas, Universidad de Zaragoza, Pedro Cerbuna, 12,
Zaragoza, 50009, Zaragoza, Spain

# Maximal subgroups of small index of finite almost simple groups

Adolfo Ballester-Bolinches<EMAIL_ADDRESS><EMAIL_ADDRESS>Paz
Jiménez-Seral<EMAIL_ADDRESS>[  *  [

###### Abstract

We prove in this paper that every almost simple group $R$ with socle
isomorphic to a simple group $S$ possesses a conjugacy class of core-free
maximal subgroups whose index coincides with the smallest index
$\operatorname{l}(S)$ of a maximal subgroup of $S$ or a conjugacy class of
core-free maximal subgroups with a fixed index
$v_{S}\leq\operatorname{l}(S)^{2}$, depending only on $S$. We also prove that
the number of subgroups of the outer automorphism group of $S$ is bounded by
$\log^{3}{\operatorname{l}(S)}$ and $\operatorname{l}(S)^{2}<\lvert S\rvert$.

###### keywords:

finite group, maximal subgroup, simple group, almost simple group

###### pacs:

[

MSC Classification]20E28, 20E32, 20B15

##  1 Introduction

All groups considered in this paper will be finite.

Given a group $G$, one can ask how many elements one should choose uniformly
and at random to generate $G$ with a certain given probability. The fact that
an ordered $r$-tuple $(g_{1},\dots,g_{r})$ generates $G$ is equivalent to the
fact that $\\{g_{1},\dots,g_{r}\\}$ is not contained in any maximal subgroup
$M$ of $G$. The probability that $\\{g_{1},\dots,g_{r}\\}$ is contained in a
maximal subgroup $M$ of $G$ is $1/\lvert G:M\rvert^{r}$. Consequently, it is
of relevant interest to find good bounds for the number
$\operatorname{m}_{n}(G)$ of maximal subgroups of a group $G$ of a given index
$n$.

Note that if $M$ is a maximal subgroup of $G$, then $G/M_{G}$, where $M_{G}$
denotes the core of $M$ in $G$, is a primitive group. Consequently, the proof
of many results in this field relies on the subgroup structure of such groups.

According to the theorem of Baer Baer57  (see also (BallesterEzquerro06, ,
Theorem 1.1.7)), there are three types of primitive groups, according to
whether they have a unique abelian minimal normal subgroup (type 1), a unique
non-abelian minimal normal subgroup (type 2), or two non-abelian minimal
normal subgroups (type 3). The theorem of O’Nan and Scott (see
(BallesterEzquerro06, , Theorem 1.1.52)) describes the different possibilities
for a primitive pair $(G,U)$ composed of a primitive group $G$ of type 2 and a
core-free maximal subgroup $U$ of $G$. In all cases, the corresponding
primitive pair is related to a primitive pair corresponding to an almost
simple group with socle $S$, where the minimal normal subgroup of $G$ is a
direct product of copies of $S$. This makes crucial the study of the indices
of core-free maximal subgroups of almost simple groups in the study of core-
free maximal subgroups of primitive groups of type 2.

######  Notation 1.

We denote by $\operatorname{l}(X)$ the least degree of a faithful transitive
permutation representation of a group $X$, that is, the smallest index of a
core-free subgroup of $G$.

The aim of this paper is to prove that every almost simple group $R$ with
socle isomorphic to a simple group $S$ possesses a conjugacy class of core-
free maximal subgroups whose index coincides with the smallest index
$\operatorname{l}(S)$ of a maximal subgroup of $S$ or a conjugacy class of
core-free maximal subgroups with a fixed index
$v_{S}\leq\operatorname{l}(S)^{2}$, depending only on $S$. We also prove that
the number of subgroups of the outer automorphism group of $S$ is bounded by
$\log^{3}{\operatorname{l}(S)}$ and that $\operatorname{l}(S)^{2}<\lvert
S\rvert$.

These results will be applied in BallesterEstebanJimenez-maximal-bounds-appl
to obtain lower bounds for the number of elements needed to generate a group
with a certain probability and to obtain good lower bounds for the number of
maximal subgroups of a given index of a group. They are also useful to
estimate the number of possible socles of primitive groups of type 2 with a
core-free maximal subgroup of a given index.

Our first main result includes relevant information over the smallest index
${\operatorname{l}(S)}$ of a maximal subgroup of a non-abelian simple group
$S$ and shows the existence of relevant subgroups of small index in an almost
simple group with socle $S$. Moreover, we see that the order of the outer
automorphism group of $S$ is bounded by $3\log\lvert S\rvert$. Here we reserve
the symbol $\log$ to denote the logarithm to the base $2$. This last bound
clarifies and improves the one used in the proof of (BorovikPyberShalev96, ,
Lemma 2.3), $\lvert\operatorname{Out}S\rvert\leq\operatorname{O}(\log^{2}n)$,
and, as we will show in Remark 6, this bound is best possible. The bound
$\lvert{\operatorname{Out}S}\rvert\leq 3\log\operatorname{l}(S)$ also appears
in (GuralnickMarotiPyber17, , Lemma 7.7), we present here a proof for
completeness.

We say that a maximal subgroup of a simple group $S$ is _ordinary_ if its
conjugacy class in $S$ coincides with its conjugacy class in
$\operatorname{Aut}(S)$. Most simple groups $S$ possess a conjugacy class of
ordinary maximal subgroups of the smallest possible index
$\operatorname{l}(S)$ and, by Lemma 2.1 below, every almost simple group with
socle $S$ possesses a maximal subgroup of index $\operatorname{l}(S)$.
However, some simple groups do not have ordinary maximal subgroups of the
smallest possible index. These groups constitute the classes $\mathfrak{X}$
and $\mathfrak{Y}$ that we define below.

######  Notation 2.

Let $\mathfrak{X}$ be the class of simple groups composed of the following
groups:

  1. 1.

the linear groups $\operatorname{PSL}_{3}(q)$, where $q=p^{f}>3$ is a power of
a prime $p$ with $f$ odd;

  2. 2.

the linear groups $\operatorname{PSL}_{n}(q)$, with $q$ a prime power and
$n=5$ or $n\geq 7$;

  3. 3.

the symplectic groups $\operatorname{PSp}_{4}(2^{f})$, $f\geq 2$.

######  Notation 3.

Let $\mathfrak{Y}$ be the class of simple groups composed of the following
groups:

  1. 1.

the Mathieu group $\mathrm{M}_{12}$;

  2. 2.

the O’Nan group $\mathrm{O^{\prime}N}$;

  3. 3.

the Tits group ${}^{2}\\!F_{4}(2)^{\prime}$;

  4. 4.

the linear groups $\operatorname{PSL}_{2}(7)\cong\operatorname{PSL}_{3}(2)$,
$\operatorname{PSL}_{2}(9)\cong\operatorname{Alt}(6)$,
$\operatorname{PSL}_{2}(11)$, $\operatorname{PSL}_{3}(3)$;

  5. 5.

the linear groups $\operatorname{PSL}_{3}(q_{0}^{2})$, with $q_{0}$ a prime
power;

  6. 6.

the linear groups $\operatorname{PSL}_{4}(q)$, with $q$ a prime power, $q>2$;

  7. 7.

the linear groups $\operatorname{PSL}_{6}(q)$, with $q$ a prime power;

  8. 8.

the unitary group $\operatorname{PSU}_{3}(5)$;

  9. 9.

the orthogonal groups $\operatorname{O}_{8}^{+}(q)$, with $q$ a prime power;

  10. 10.

the orthogonal groups $\operatorname{O}_{n}^{+}(3)$, with $n\geq 10$;

  11. 11.

the exceptional groups of Lie type $G_{2}(3^{f})$, with $f\geq 1$;

  12. 12.

the exceptional groups of Lie type $F_{4}(2^{f})$, with $f\geq 1$;

  13. 13.

the exceptional groups of Lie type $E_{6}(q)$, with $q$ a prime power.

In the simple groups $S$ of the class $\mathfrak{Y}$, there are no ordinary
maximal subgroups of index $\operatorname{l}(S)$, but we can find a number
$v_{S}\leq\operatorname{l}(S)^{2}$ that depends only on $S$ such that $S$ has
a conjugacy class of ordinary maximal subgroups of index $v_{S}$. Again by
Lemma 2.1, every almost simple group with socle $S$ possesses a conjugacy
class of maximal subgroup of this index $v_{S}$. In other words, $v_{S}$
appears as a common index of a core-free maximal subgroup for all almost
simple groups with socle $S$. The class $\mathfrak{X}$ is composed of the rest
of the simple groups, that is, all simple groups that do not have a conjugacy
class of ordinary maximal subgroups with index bounded by
$\operatorname{l}(S)^{2}$. However, we will prove that in the groups of the
class $\mathfrak{X}$, we can find a number $v_{S}\leq\operatorname{l}(S)^{2}$
such that every almost simple group $R$ with socle $S$ possesses a maximal
subgroup of order $\operatorname{l}(S)$ or a maximal subgroup of index
$v_{S}$. We present this in detail in Theorem A.

######  Theorem A.

Let $S$ be a simple group.

  1. 1.

If $S$ does not belong to $\mathfrak{X}\cup\mathfrak{Y}$, then $S$ has a
conjugacy class of ordinary maximal subgroups. In particular, if $R$ is an
almost simple group with $S\leq R\leq\operatorname{Aut}(S)$, then $R$ has a
conjugacy class of core-free maximal subgroups of index $\operatorname{l}(S)$.

  2. 2.

If $S$ belongs to $\mathfrak{Y}$, then $S$ has at least two conjugacy classes
of maximal subgroups of the smallest index ${\operatorname{l}(S)}$ and there
exists a number $v_{S}\leq{\operatorname{l}(S)}^{2}$, depending only on $S$,
such that if $R$ is an almost simple group with $S\leq
R\leq\operatorname{Aut}(S)$, then $R$ has a conjugacy class of core-free
maximal subgroups with index $v_{S}$.

  3. 3.

If $S$ belongs to $\mathfrak{X}$, then $S$ has at least two conjugacy classes
of maximal subgroups of the smallest index ${\operatorname{l}(S)}$ and there
exists a number $v_{S}\leq{\operatorname{l}(S)}^{2}$, depending only on $S$,
such that if $R$ is an almost simple group with $S\leq
R\leq\operatorname{Aut}(S)$, then $R$ has at least two conjugacy classes of
core-free maximal subgroups with index ${\operatorname{l}(S)}$ or one
conjugacy class of core-free maximal subgroups with index $v_{S}$.

  4. 4.

In all cases, ${\operatorname{l}(S)}^{2}<\lvert S\rvert$ and
$\lvert{\operatorname{Out}S}\rvert\leq 3\log{\operatorname{l}(S)}$.

  5. 5.

If, in addition,

    1. (a)

$S\not\cong\operatorname{Alt}(6)$;

    2. (b)

$S$ is not of the form $\operatorname{PSL}_{n}(q)$ with $q=p^{f}$ and

      1. i.

$n\geq 3$, $p\in\\{2,3,5,7\\}$, and $\gcd(n,q-1)>1$, or

      2. ii.

$n=2$ and $q=3^{f}$;

    3. (c)

$S$ is not of the form $\operatorname{PSU}_{n}(q)$ with $q=p^{f}$ and

      1. i.

$n=3$ and $p=3$, or

      2. ii.

$n=3$ and $q=5$, or

      3. iii.

$n\geq 4$, $p=2$, $f>1$ and $\gcd(n,q+1)>1$, or

      4. iv.

$p=3$, $n=5$, and

    4. (d)

$S\not\cong{\operatorname{O}_{8}^{+}(q)}$ with $q=p^{f}$ and
$p\in\\{3,5,7,11,13\\}$,

then $\lvert\operatorname{Out}S\rvert\leq\log{\operatorname{l}(S)}$.

######  Remark 1.

According to Atlas85 , the automorphism group of the O’Nan simple group
$S\cong{\operatorname{O^{\prime}N}}$ has all core-free maximal subgroups of
index greater than its order, so Theorem A (4) cannot be extended to the core-
free maximal subgroups of almost simple groups.

######  Theorem B.

The number of subgroups of the outer automorphism group of a non-abelian
simple group $S$ is bounded by $\log^{3}{\operatorname{l}(S)}$.

Unless otherwise stated, we will follow the notation of the books
DoerkHawkes92  and BallesterEzquerro06 . Detailed information about primitive
groups and chief factors of a group can be found in (BallesterEzquerro06, ,
Chapter 1).

##  2 Proofs

|  |  |  |
---|---|---|---|---
|  |  |
|  |  |
|  |  |  |
|
$\textstyle{A_{l}\colon}$$\underset{1}{\bullet}$$\underset{2}{\bullet}$$\underset{3}{\bullet}$$\underset{l-3}{\bullet}$$\underset{l-2}{\bullet}$$\underset{l-1}{\bullet}$$\underset{l}{\bullet}$$\textstyle{B_{l}\colon}$$\underset{1}{\bullet}$$\underset{2}{\bullet}$$\underset{3}{\bullet}$$\underset{l-3}{\bullet}$$\underset{l-2}{\bullet}$$\underset{l-1}{\bullet}$$\underset{l}{\bullet}$$\textstyle{C_{l}\colon}$$\underset{1}{\bullet}$$\underset{2}{\bullet}$$\underset{3}{\bullet}$$\underset{l-3}{\bullet}$$\underset{l-2}{\bullet}$$\underset{l-1}{\bullet}$$\underset{l}{\bullet}$$\underset{\quad
l-1}{\bullet}$$\textstyle{D_{l}\colon}$$\underset{1}{\bullet}$$\underset{2}{\bullet}$$\underset{3}{\bullet}$$\underset{l-3}{\bullet}$$\underset{l-2\quad}{\bullet}$$\underset{l}{\bullet}$$\textstyle{E_{6}\colon}$$\underset{1}{\bullet}$$\underset{3}{\bullet}$$\overset{4}{\bullet}$$\underset{5}{\bullet}$$\underset{6}{\bullet}$$\underset{2}{\bullet}$$\textstyle{E_{7}\colon}$$\underset{1}{\bullet}$$\underset{3}{\bullet}$$\overset{4}{\bullet}$$\underset{5}{\bullet}$$\underset{6}{\bullet}$$\underset{7}{\bullet}$$\underset{2}{\bullet}$$\textstyle{E_{8}\colon}$$\underset{1}{\bullet}$$\underset{3}{\bullet}$$\overset{4}{\bullet}$$\underset{5}{\bullet}$$\underset{6}{\bullet}$$\underset{7}{\bullet}$$\underset{8}{\bullet}$$\underset{2}{\bullet}$$\textstyle{F_{4}\colon}$$\underset{1}{\bullet}$$\underset{2}{\bullet}$$\underset{3}{\bullet}$$\underset{4}{\bullet}$$\textstyle{G_{2}\colon}$$\underset{1}{\bullet}$$\underset{2}{\bullet}$
Figure 1: Dynkin diagrams for the simple groups of Lie type

Our results will depend heavily on the classification of simple groups. For
the simple groups of Lie type, we number the nodes of the corresponding Dynkin
diagrams as in Figure 1 and denote accordingly the associated parabolic
subgroups. The values of ${\operatorname{l}(S)}$ for the simple groups of Lie
type have been computed in the series of papers of Mazurov Mazurov93 ,
Vasil’ev and Mazurov VasilevMazurov94 , and Vasilyev Vasilyev96 ; Vasilyev97 ;
Vasilyev98 .

######  Lemma 2.1.

Suppose that $S$ is a non-abelian simple group and let
$A=\operatorname{Aut}(S)$. We identify $S$ with the subgroup of $A$ composed
by all inner automorphisms induced by $S$. If $M$ is a maximal subgroup of $S$
such that the conjugacy class of $M$ in $S$ is invariant under the action of
$A$, then $W=\operatorname{N}_{A}(M)$ is a maximal subgroup of $A$, $W\cap
S=M$, and $\lvert S:M\rvert=\lvert A:W\rvert$.

Proof: Note that the length of the conjugacy class of $M$ in $S$ is equal to
the length of the conjugacy class of $M$ in $A$. Since this length coincides
with the index of the corresponding normalisers, we have that $\lvert
S:\operatorname{N}_{S}(M)\rvert=\lvert A:\operatorname{N}_{A}(M)\rvert$. In
particular, if $S\leq T\leq A$, then the conjugacy class of $M$ in $T$
coincides with the conjugacy class of $M$ in $S$. Since the length of the
conjugacy class coincides with the index of the normaliser and
$M=\operatorname{N}_{S}(M)$, we have that

$\lvert S:M\rvert=\lvert T:{\operatorname{N}_{T}(M)}\rvert=\lvert
A:{\operatorname{N}_{A}(M)}\rvert$ (1)

for every $T$ with $S\leq T\leq A$. Let $W=\operatorname{N}_{A}(M)$. Then
$W\cap S=\operatorname{N}_{S}(M)=M$ since $M$ is a maximal subgroup and $S$ is
a non-abelian simple group. We prove now that $W$ is a maximal subgroup of
$A$. Suppose that $W\leq V\leq A$. By taking intersections with $S$, we obtain
that $M\leq V\cap S\leq S$. Since $M$ is maximal in $S$, $M=V\cap S$ or $V\cap
S=S$. In the first case, since $M=V\cap S$ is a normal subgroup of $V$, we
obtain that $V\leq\operatorname{N}_{A}(M)=W$ and so $V=W$. In the second case,
$S\leq V$. As $\operatorname{N}_{A}(M)=\operatorname{N}_{V}(M)$, by (1), it
turns out that $V=A$.

By Lemma 2.1, if $X$ is an almost simple group with
$\operatorname{Soc}(X)\cong S$ and $M$ is an ordinary maximal subgroup of $S$,
then $\operatorname{N}_{X}(M)$ is a maximal subgroup of $X$ of index $\lvert
S:M\rvert$. We will use this fact without mentioning it explicitly.

Proof: [Proof of Theorem A] We will analyse the different possibilities for
$S$ in the classification of finite simple groups. We note that the condition
${\operatorname{l}(S)}^{2}<\lvert S\rvert$ is equivalent to affirming that
there is a maximal subgroup of $S$ with index less than its order. We warn the
reader that the information about the maximal subgroups comes from several
sources and, in order to make it easier to check the results, we have
preferred to adhere to the notation of the corresponding source, even if in
some cases there appear some inconsistencies in the notation.

_Sporadic simple groups_

Suppose first that $S$ is a sporadic simple group. It is clear that if the
outer automorphism group of $S$ is trivial, then
$S\notin\mathfrak{X}\cup\mathfrak{Y}$ and the result is trivially valid. In
the other cases, the outer automorphism group has order $2$. In the sporadic
simple groups $\mathrm{M}_{22}$, $\mathrm{J}_{2}$, $\mathrm{Suz}$,
$\mathrm{HS}$, $\mathrm{McL}$, $\mathrm{He}$, $\mathrm{Fi}_{22}$,
$\mathrm{HN}$, and $\mathrm{J_{3}}$, according to the Atlas Atlas85 , the
largest maximal subgroups are ordinary and so
${\operatorname{l}^{*}(A)}={\operatorname{l}(S)}$. The maximal subgroups of
the group $\mathrm{Fi}_{24}^{\prime}$ and its automorphism group
$\mathrm{Fi}_{24}$ have been studied in LintonFischer91 . The smallest index
maximal subgroup $\mathrm{Fi}_{23}$ is ordinary. In the Mathieu group
$\mathrm{M}_{12}$, there are two classes of the smallest index maximal
subgroup, with index $12$ and there is a class of ordinary maximal subgroups
of index $144=12^{2}$ (see Atlas85 ). In the O’Nan group
$S\cong\mathrm{O^{\prime}N}$, according again to Atlas85 , there are two
conjugacy classes of maximal subgroups of type $\mathrm{L}_{3}(7):2$, of the
smallest index $122\,760$, fused under the outer automorphism, giving a
conjugacy class of novel maximal subgroups of type $7^{1+2}_{+}:(3\times
D_{16})$ and index $55\,978\,560\leq{\operatorname{l}(S)}^{2}$.

For all the sporadic groups $S$, we also see that the inequality
${\operatorname{l}(S)}^{2}<\lvert S\rvert$ holds for all groups whose maximal
subgroups have been described in Atlas85 . The conclusion for the Baby Monster
group $B$ follows, by Wilson99 , for the smallest index maximal subgroup
$2.{}^{2}\\!E_{6}(2):2$. The conclusion for the Monster group $M$ is also
true, by Wilson10-Moonshine ; NortonWilson13 , with the maximal subgroup
$2.B$. Finally, it is clear that $\lvert\operatorname{Out}S\rvert\leq
2\leq\log{\operatorname{l}(S)}$ for all sporadic simple groups $S$.

According to Atlas85 , the Tits group ${}^{2}\\!F_{4}(2)^{\prime}$ has an
outer automorphism group of order $2$ and two conjugacy classes of subgroups
of type $\operatorname{PSL}_{3}(3):2$ of the smallest possible index,
$1\,600$, fused under the graph automorphism, and an ordinary maximal subgroup
of type $2.[2^{8}]:5:4$ of index $1\,755\leq 1\,600^{2}$. Furthermore,
${\operatorname{l}(S)}^{2}<\lvert S\rvert$ and
$\lvert\operatorname{Out}S\rvert\leq 2\leq\log{\operatorname{l}(S)}$.

_Alternating groups_

Suppose now that $S\cong{\operatorname{Alt}(n)}$ with $n\geq 7$ or $n=5$. Then
$\operatorname{Alt}({n-1})$ is an ordinary maximal subgroup of $S$ of the
smallest possible order, $n$. If
$S\cong\operatorname{Alt}(6)\cong\operatorname{PSL}_{2}(9)$, we see in Atlas85
that the smallest index of a maximal subgroup of $S$ is $6$, while $S$
possesses an ordinary maximal subgroup of type $3^{2}:4$ and index $10<6^{2}$.
Clearly,
$\operatorname{l}\bigl{(}{\operatorname{Alt}(n)}\bigr{)}^{2}<\lvert{\operatorname{Alt}(n)}\rvert$
for all $n\geq 5$ and
$\lvert\operatorname{Out}\operatorname{Alt}(n)\rvert=2\leq\log{\operatorname{l}(\operatorname{Alt}(n))}$
if $n\neq 6$, and $\lvert\operatorname{Out}\operatorname{Alt}(6)\rvert=4\leq
3\log{\operatorname{l}(\operatorname{Alt}(6))}$.

_Linear groups_

We start with the linear groups on dimension $2$. Suppose first that
$S\cong\operatorname{PSL}_{2}(q)$ with $q\in\\{5,7,8,9,11\\}$. We have that
$S=\operatorname{PSL}_{2}(5)\cong{\operatorname{Alt}(5)}$ and
$S=\operatorname{PSL}_{2}(9)\cong{\operatorname{Alt}(6)}$ have been studied
before. Moreover, according to Atlas85 , $S=\operatorname{PSL}_{2}(7)$ has two
conjugacy classes of maximal subgroups of index ${\operatorname{l}(S)}=7$ and
a class of ordinary maximal subgroups of index $8$,
$S=\operatorname{PSL}_{2}(8)$ has an ordinary maximal subgroup of index
${\operatorname{l}(S)}=9$, and $S\cong\operatorname{PSL}_{2}(11)$ has two
conjugacy classes of maximal subgroups of index ${\operatorname{l}(S)}=11$ and
another conjugacy class of ordinary maximal subgroups of index
$12<{\operatorname{l}(S)}^{2}$. We can see in Atlas85  the existence of
maximal subgroups in $S$ and in all almost simple groups with the prescribed
indices and that
$\lvert\operatorname{Out}\operatorname{PSL}(2,q)\rvert\leq\log{\operatorname{l}(S)}$
when $q\in\\{5,7,8,11\\}$ and that $\lvert\operatorname{PSL}(2,9)\rvert\leq
3\log{\operatorname{l}(S)}$. Since the parabolic subgroups have index $q+1$
and order $q(q-1)/d$ with $d=\gcd(q-1,2)$, we see that
${\operatorname{l}(S)}\leq q+1\leq q(q-1)/d$ and so
${\operatorname{l}(S)}^{2}<\lvert S\rvert$.

Suppose that $S\cong\operatorname{PSL}_{2}(q)$, with $q=p^{f}\geq 13$. Then
the parabolic (Borel) subgroups are the smallest index maximal subgroups and
are ordinary by (Mazurov93, , Theorem 1). Their index is
${\operatorname{l}(S)}=q+1$ and their order is $q(q-1)/d$. Then
$q^{2}-3q-2=q(q-3)-2\geq 0$, which implies that $\operatorname{l}(S)=q+1\leq
q(q-1)/2\leq q(q-1)/d$ and so $\operatorname{l}(S)^{2}\leq\lvert S\rvert$.
Furthermore, $\lvert\operatorname{Out}S\rvert=\gcd(2,q-1)\cdot f\leq 2f\leq
2\log p^{f}\leq 2\log{\operatorname{l}(S)}$. If, in addition $p\geq 5$, then
$2f\leq\log p^{f}\leq\log{\operatorname{l}(S)}$, while if $p=2$, then
$\lvert\operatorname{Out}S\rvert=1\cdot f\cdot
1\leq\log{\operatorname{l}(S)}$.

We consider now the linear groups on dimension greater than $2$. The groups
$\operatorname{PSL}_{3}(2)\cong\operatorname{PSL}_{2}(7)$ and
$\operatorname{PSL}_{4}(2)\cong{\operatorname{Alt}(8)}$ have been considered
before. Let $R$ be an almost simple group with
$S=\operatorname{Soc}(R)\cong\operatorname{PSL}_{n}(q)$, where $n\geq 3$, that
is, $S\leq R\leq A$ with $A\cong\operatorname{Aut}(S)$, and suppose that
$(n,q)\notin\\{(3,2),(4,2)\\}$. According to (Mazurov93, , Theorem 1),
${\operatorname{l}(S)}=(q^{n}-1)/(q-1)$ is the index of a parabolic subgroup.
Then the outer automorphism group of $S$ is isomorphic to
$[C_{d}][C_{f}]C_{2}=\langle\delta,\phi,\gamma\rangle$, with $q=p^{f}$, $p$ a
prime, and $d=\gcd(n,q-1)$ (see, for example, Atlas85 ). If $R/S$ is contained
in $\langle\delta,\phi\rangle$, the parabolic subgroups of type $P_{1}$, which
are the stabilisers of a $1$-dimensional subspace, induce maximal subgroups of
$R$ of index $(q^{n}-1)/(q-1)$ since they are stabilised by
$\langle\delta,\phi\rangle$. If $R/S$ is not contained in
$\langle\delta,\phi\rangle$, then the double parabolic subgroups $P_{1,n-1}$,
stabilisers of pairs of subspaces $(W,U)$ with $W<U$ and $1=\dim W=n-\dim U$,
induce maximal subgroups of $R$ of index
$v_{S}=(q^{n}-1)(q^{n-1}-1)/(q-1)^{2}$ since they are stabilised by
$\langle\delta,\phi,\gamma\rangle$. Then $R$ has a maximal subgroup of index
$\operatorname{l}(S)=(q^{n}-1)/(q-1)$ or of index
$v_{S}=(q^{n}-1)(q^{n-1}-1)/(q-1)^{2}\leq{\operatorname{l}(S)}^{2}$, according
to whether or not $R/S$ is contained in $\langle\delta,\phi\rangle$,
respectively. In particular,
$\operatorname{l}^{*}(R)\leq{\operatorname{l}(S)}^{2}$. It is clear that

${\operatorname{l}(S)}^{2}=\left(\frac{q^{n}-1}{q-1}\right)^{2}<\frac{q^{n(n-1)/2}(q^{n}-1)(q^{n-1}-1)\dotsm(q^{2}-1)}{\gcd(n,q-1)}=\lvert
S\rvert.$

If $S\cong\operatorname{PSL}_{4}(2)$, then
$\lvert\operatorname{Out}S\rvert=2<\log{\operatorname{l}(S)}$. Furthermore,
for $S=\operatorname{PSL}_{n}(q)$ with $n\geq 3$, $(n,q)\neq(4,2)$, we have
that ${\operatorname{l}(S)}=(q^{n}-1)/(q-1)$ and so

$\displaystyle\lvert\operatorname{Out}S\rvert$ $\displaystyle\leq n\cdot
f\cdot 2\leq(3/2)(n-1)\cdot f\cdot 2$
$\displaystyle=3\log\bigl{(}(2^{f})^{n-1}\bigr{)}\leq 3\log
q^{n-1}<3\log{\operatorname{l}(S)}.$

If, in addition, $p\geq 11$, then
$3\log(2^{f})^{n-1}\leq\log(p^{f})^{n-1}\leq\log{\operatorname{l}(S)}$.
Furthermore, if $p\geq 2$ and $\gcd(n,q-1)=1$, then
$\lvert\operatorname{Out}S\rvert=2f\leq q^{2}+1\leq\operatorname{l}(S)$.

Now we analyse the cases for which $G\notin\mathfrak{X}$. Note that, according
to Atlas85 , the group $S\cong\operatorname{PSL}_{3}(3)$ has two conjugacy
classes of maximal subgroups of index ${\operatorname{l}(S)}=13$ and a
conjugacy class of ordinary maximal subgroups of type $13:3$ and index
$144<{\operatorname{l}(S)}^{2}<\lvert S\rvert$ and
$S\cong\operatorname{PSL}_{3}(4)$ has two conjugacy classes of maximal
subgroups of index ${\operatorname{l}(S)}=21$ and a conjugacy class of
ordinary maximal subgroups of type $3^{2}:Q_{8}$ and index
$280<{\operatorname{l}(S)}^{2}<\lvert S\rvert$.

Suppose that $S=\operatorname{PSL}_{3}(q)$ with $q=q_{0}^{2}$, where $q_{0}$ a
prime power, $q_{0}>2$. We have that
$\operatorname{l}(S)=(q^{3}-1)(q-1)=(q_{0}^{6}-1)/(q_{0}^{2}-1)$. Then
$\gcd(q_{0}+1,3)=1$ or $\gcd(q_{0}-1,3)=1$. By (BrayHoltRoneyDougal13, , Table
8.3), in the first case, $\operatorname{SL}_{3}(q)$ has an ordinary maximal
subgroup isomorphic to $\operatorname{SL}_{3}(q_{0})$ of index
$q_{0}^{3}(q_{0}^{3}+1)(q_{0}^{2}+1)=q_{0}^{8}+q_{0}^{6}+q_{0}^{5}+q_{0}^{3}<(q_{0}^{4}+q_{0}^{2}+q_{0})^{2}={\operatorname{l}(S)}^{2}$,
while, in the second case, $\operatorname{SL}_{3}(q)$ has an ordinary maximal
subgroup isomorphic to $\operatorname{SU}_{3}(q_{0})$, of index
$q_{0}^{3}(q_{0}^{3}-1)(q_{0}^{2}+1)<\bigl{(}(q_{0}^{6}-1)/(q_{0}^{2}-1)\bigr{)}^{2}={\operatorname{l}(S)}^{2}$.

For the group $S\cong\operatorname{PSL}_{4}(q)$, $q>2$, according to
(BrayHoltRoneyDougal13, , Table 8.8), we have that $\operatorname{SL}_{4}(q)$
has two classes of maximal subgroups of the smallest index
${\operatorname{l}(S)}=(q^{4}-1)/(q-1)$ and a conjugacy class of ordinary
maximal subgroups of type
$E_{q}^{4}:{\operatorname{SL}_{2}(q)}\times{\operatorname{SL}_{2}(q)}:(q-1)$
and index $v_{S}=(q^{2}+1)(q^{3}-1)/(q-1)$. Therefore
$v_{S}/{\operatorname{l}(S)}^{2}=(q-1)(q^{3}-1)/((q^{2}-1)(q^{4}-1))<1$ and so
$v_{S}<{\operatorname{l}(S)}^{2}$.

For the group $S\cong\operatorname{PSL}_{6}(q)$, according to
(BrayHoltRoneyDougal13, , Table 8.24), we have that $\operatorname{SL}_{6}(q)$
has two classes of maximal subgroups of the smallest index
${\operatorname{l}(S)}=(q^{6}-1)/(q-1)$ and a conjugacy class of ordinary
maximal subgroups of type
$E_{q}^{9}:{\operatorname{SL}_{3}(q)}\times{\operatorname{SL}_{3}(q)}:(q-1)$
and index $v_{S}=(q^{5}-1)(q^{4}-1)(q^{3}+1)/((q-1)^{2}(q+1))$. Therefore
$v_{S}/{\operatorname{l}(S)}^{2}=(q^{5}-1)(q^{2}+1)(q^{2}-1)/((q^{6}-1)(q+1)^{2}(q^{3}-1))<1$
and so $v_{S}<{\operatorname{l}(S)}^{2}$.

_Symplectic groups_

Now suppose that $S\cong\operatorname{PSp}_{n}(q)$ with $n\geq 4$ even. Then

$\lvert
S\rvert=\frac{1}{d}q^{(n/2)^{2}}\Biggl{(}\prod_{i=1}^{n/2}(q^{2i}-1)\Biggr{)},$

where $d=\gcd(2,q-1)$. The smallest index maximal subgroups of $S$ are
described in (Mazurov93, , Theorem 2). If $(n,q)=(4,3)$ then
$S\cong\operatorname{PSU}_{4}(2)$ and $G$ has an ordinary maximal subgroup of
type $2^{4}:{\operatorname{Alt}(5)}$, of index ${\operatorname{l}(S)}=27$ and
order $960$. In this case,
$\lvert\operatorname{Out}S\rvert=2<\log{\operatorname{l}(S)}$.

Suppose that $n\geq 6$ and $q=2$. Then
$S\cong\operatorname{PSp}_{n}(2)\cong{\operatorname{O}_{n+1}(2)}$ and the
smallest index maximal subgroup of $S$ is isomorphic to
$\operatorname{O}_{n}^{-}(2)$ and has index $2^{n/2-1}(2^{n/2}-1)$. By
(BrayHoltRoneyDougal13, , Tables 8.28, 8.48, 8.64, 8.80) and
(KleidmanLiebeck90, , Table 3.5.C), this subgroup is ordinary. It is clear
that this index is smaller than the order of this subgroup, namely
$2^{(n/2)(n/2-1)}(2^{n/2}+1)\prod_{i=1}^{n/2-1}(q^{2i}-1)$, and that
$\lvert\operatorname{Out}S\rvert=1<\log{\operatorname{l}(S)}$.

If $n=4$ and $q=2^{f}$, then $\lvert S\rvert=q^{4}(q^{4}-1)(q^{2}-1)$ and
there are two conjugacy classes of parabolic maximal subgroups of type
$E_{q}^{3}:{\operatorname{GL}_{2}(q)}$ and index
${\operatorname{l}(S)}=(q^{4}-1)/(q-1)$ fused under the graph automorphism, by
(BrayHoltRoneyDougal13, , Table 8.14). There is a novelty subgroup
$[q^{4}]:(C_{q-1})^{2}$, maximal under subgroups not contained in the subgroup
$\langle\phi\rangle$ generated by the field automorphism, of index

$\frac{(q^{4}-1)(q+1)}{q-1}<\left(\frac{q^{4}-1}{q-1}\right)^{2}={\operatorname{l}(S)}^{2}.$

In this case,

$\lvert\operatorname{Out}S\rvert=1\cdot f\cdot 2=2f\leq\log
q^{2}\leq\log{\operatorname{l}(S)}.$

For the rest of the values of $(n,q)$, the smallest index maximal subgroup is
a parabolic subgroup, which can be taken to have the form
$[q^{n-1}]:((q-1).\operatorname{PSp}_{n-2}(q))$, with index
${\operatorname{l}(S)}=(q^{n}-1)/(q-1)$ and order

$\frac{1}{d}q^{n-1}(q-1)q^{((n-2)/2)^{2}}\prod_{i=1}^{(n-2)/2}(q^{2i}-1)>q^{n}\geq\frac{q^{n}-1}{q-1}={\operatorname{l}(S)}.$

Here $\lvert\operatorname{Out}S\rvert=\gcd(2,q-1)\cdot f\cdot 1=2f$ if $p$ is
odd and $\lvert\operatorname{Out}S\rvert=\gcd(2,q-1)\cdot f\cdot 1=f$ if
$p=2$. In any case,

$\lvert\operatorname{Out}S\rvert\leq 2f\leq\log
q^{n-1}\leq\log{\operatorname{l}(S)}.$

_Unitary groups_

Suppose now that $S\cong\operatorname{PSU}_{n}(q)$ with $n\geq 3$ and $q>2$ if
$n=3$; then $\lvert\operatorname{Out}S\rvert\leq n\cdot f\cdot 1$ with
$p^{f}=q^{2}$. The smallest index of a maximal subgroup of $S$ is given in
(Mazurov93, , Theorem 3).

We consider first the case $S\cong\operatorname{PSU}_{3}(5)$. We see in
Atlas85  that the automorphism group of $S$ is isomorphic to $S_{3}$ and that
there are three conjugacy classes of maximal subgroups of the smallest
possible index, of type $\operatorname{Alt}(7)$ and index
${\operatorname{l}(S)}=50$ and order $2\,520$. Moreover, there is an ordinary
maximal subgroup of type $5_{+}^{1+2}:8$ and index $126\leq 50^{2}$. In this
case, $\lvert\operatorname{Out}S\rvert=3\cdot 2\cdot 1=6\leq
3\log{\operatorname{l}(S)}$.

Suppose that $n=3$, $q\notin\\{2,5\\}$. Then $S$ has a conjugacy class of
parabolic ordinary maximal subgroups of type $[q^{3}]:((q^{2}-1)/d)$, with
$d=\gcd(3,q+1)$ and index ${\operatorname{l}(S)}=q^{3}+1$, as we can see in
(BrayHoltRoneyDougal13, , Table 8.5). Clearly,
${\operatorname{l}(S)}^{2}<\lvert S\rvert$ and
$\lvert\operatorname{Out}S\rvert\leq\gcd(3,q-1)\cdot 2f\leq\log 2^{6f}$. If
$p\geq 5$, $\log 2^{6f}\leq\log q^{3}\leq\log{\operatorname{l}(S)}$. If $p=3$,
then $\log 2^{6f}\leq\log 3^{4f}=(4/3)\log
3^{3f}\leq(4/3)\log{\operatorname{l}(S)}$.

Now assume that $n=4$. Then $S$ has a conjugacy class of parabolic maximal
subgroups of type $[q^{4}].{\operatorname{SL}_{2}(q^{2})}:((q-1)/d)$, with
$d=\gcd(q+1,4)$, whose index is ${\operatorname{l}(S)}=(q^{3}+1)(q+1)$ and
whose order is $q^{6}(q^{4}-1)(q-1)>{\operatorname{l}(S)}$. These subgroups
are ordinary, as shown in (BrayHoltRoneyDougal13, , Table 8.10). Moreover,
$\lvert\operatorname{Out}S\rvert=\gcd(4,q+1)\cdot 2f\cdot 1=8f\leq 2\log
2^{4f}\leq 2\log q^{4}\leq 2\log{\operatorname{l}(S)}$. If, in addition,
$p\notin\\{2,3\\}$, then $\lvert\operatorname{Out}S\rvert=8f\leq\log
q^{4}\leq\log{\operatorname{l}(S)}$.

Assume now that $n>4$, and that $q>2$ if $n$ is even. In this case, the
smallest index maximal subgroups are the parabolic subgroups of type
$[q^{2n-3}]:{\operatorname{SU}_{n-2}(q)}:((q^{2}-1)/d)$, with $d=\gcd(n,q+1)$.
These subgroups have index
${\operatorname{l}(S)}=(q^{n}-(-1)^{n})(q^{n-1}-(-1)^{n-1})/(q^{2}-1)$. By
(BrayHoltRoneyDougal13, , Tables 8.20, 8.26, 8.37, 8.46, 8.56, 8.62, 8.72, and
8.78) and (KleidmanLiebeck90, , Table 3.5.B), we see that these maximal
subgroups are ordinary. Since they have order

$\frac{1}{d}q^{n(n-1)/2}(q^{2}-1)\prod_{i=1}^{n-3}(q^{i+1}-(-1)^{i+1}),$

$(q^{n}+1)<q^{2}(q^{n-2}+1)$ and $q^{n-1}-1<q^{n-1}$ if $n$ is odd, and
$(q^{n-1}+1)<q^{2}(q^{n-3}+1)$ and $q^{n}-1<q^{n}$ if $n$ is even, we see that
the index of these subgroups is smaller than their order. Observe that

$\displaystyle\operatorname{l}(S)$
$\displaystyle=\begin{cases}(q^{n-1}-q^{n-2}+\dots-q+1)(q^{n-2}+q^{n-3}+\dots+q+1)&\text{($n$
odd)}\\\ (q^{n-1}+q^{n-2}+\dots+q+1)(q^{n-2}-q^{n-3}+\dots-q+1)&\text{($n$
even)}\end{cases}$
$\displaystyle=\begin{cases}((q-1)(q^{n-2}+q^{n-4}+\dots+q)+1)(q^{n-2}+q^{n-3}+\dots+1)&\text{($n$
odd)}\\\
(q^{n-1}+q^{n-2}+\dots+1)((q-1)(q^{n-3}+q^{n-5}+\dots+q)+1)&\text{($n$
even)}\end{cases}$ $\displaystyle\geq\begin{cases}q^{n-2}q^{n-2}&\text{($n$
odd)}\\\ q^{n-1}q^{n-3}&\text{($n$ even)}\end{cases}$
$\displaystyle=q^{2n-4}.$

It follows that $\log\operatorname{l}(S)\geq(2n-4)\log q=(2n-4)f\log p$.
Suppose that $p\geq 5$ or that $p=3$ and $n\geq 6$. Then $n\leq(n-2)\log p$
and so

$\lvert\operatorname{Out}S\rvert\leq n\cdot 2f\cdot 1\leq(2n-4)f\log
p\leq\log\operatorname{l}(S).$

Suppose now that $p=2$ and $n\geq 5$, or that $p=3$ and $n=5$, and
$\gcd(n,q+1)=1$. In this case, $\lvert\operatorname{Out}S\rvert=2f$ and so

$\lvert\operatorname{Out}S\rvert\leq 2f\cdot(2n-4)f\log
2\leq\log\operatorname{l}(S).$

Suppose now that $p=2$ and $n\geq 5$ or that $p=3$ and $n=5$, and that
$\gcd(n,q+1)>1$. In this case, $n\leq 3(n-2)\log p$ and so

$\lvert\operatorname{Out}S\rvert\leq 2nf\leq 3(2n-4)f\log p\leq
3\log\operatorname{l}(S).$

Finally, assume that $n\geq 6$, $n$ is even, and $q=2$. Then the smallest
index maximal subgroups of $S$ have type $\operatorname{SU}_{n-1}(2):(3/d)$,
with $d=\gcd(3,m)$, and index ${\operatorname{l}(S)}=2^{n-1}(2^{n}-1)/3$, and,
since $2^{n-1}\leq 2^{(n-1)(n-2)/2}$ and $2^{n}-1<2^{n}+2=2(2^{n-1}+1)$, we
obtain that ${\operatorname{l}(S)}^{2}<\lvert S\rvert$. By
(BrayHoltRoneyDougal13, , Tables 8.26, 8.46, 8.62, and 8.78) and
(KleidmanLiebeck90, , Table 3.5.B), we conclude that these maximal subgroups
are ordinary. In this case,
$\lvert\operatorname{Out}S\rvert=2\leq\log{\operatorname{l}(S)}$ if $n$ is not
divisible by $6$, while $\lvert\operatorname{Out}S\rvert=3\cdot
2=6\leq\log{\operatorname{l}(S)}$ if $n$ is divisible by $6$.

_Orthogonal groups_

Suppose now that $S\cong{\operatorname{O}_{n}^{\varepsilon}(q)}$ is an
orthogonal group with $n\geq 7$, $n$ even if $q=2^{f}$. The smallest index
maximal subgroups of $S$ have been described in (VasilevMazurov94, , Theorem).

Assume first that $n=8$, $\varepsilon={+}$ and $q>3$. Then we have that
${\operatorname{l}(S)}=(q^{4}-1)(q^{3}+1)/(q-1)$ and we can take a maximal
subgroup $H$ of type $q^{6}.({\Omega_{6}^{+}(q)}\times(q-1)/d).e$, where
$d=\gcd(q^{4}-1,4)$, $e=\gcd(q^{4}-1,2)$. Hence $\lvert
H\rvert=q^{12}(q^{3}-1)(q^{4}-1)(q^{2}-1)(q-1)/e$. Since $(q^{3}-1)(q-1)>2$,
we conclude that $q(q^{3}-1)=q^{4}-q>q^{3}+1$, and so
${\operatorname{l}(S)}<\lvert H\rvert$. By (BrayHoltRoneyDougal13, , Table
8.50), $S$ possesses an ordinary maximal subgroup in the Aschbacher class
$\mathcal{C}_{1}$ of type
$E_{q}^{1+8}(\frac{1}{e}{\operatorname{GL}_{2}(q)}\times\Omega_{4}^{+}(q)\bigr{)}.e$
with index $v=(q+1)(q^{2}-q+1){(q^{2}+1)}^{2}(q^{2}+q+1)$. Therefore

$\frac{v}{{\operatorname{l}(S)}^{2}}=\frac{q^{3}-1}{(q+1)^{2}(q^{3}+1)(q-1)}<1.$

It follows that $v<{\operatorname{l}(S)}^{2}$. In this case, we have three
conjugacy classes of maximal subgroups of index ${\operatorname{l}(S)}$, fused
under the triality outer automorphism. Moreover,
$\lvert\operatorname{Out}S\rvert=\gcd(2,q-1)^{2}\cdot f\cdot 3!$. If $p\neq
2$, then $2^{8}<3^{6}$ and so $\lvert\operatorname{Out}S\rvert\leq 24f\leq
3\log 2^{8f}\leq 3\log p^{6f}\leq 3\log{\operatorname{l}(S)}$. If $p\geq 17$,
then $2^{4}\leq p$ and so $\lvert\operatorname{Out}S\rvert\leq 24f\leq\log
2^{24f}\leq\log p^{6f}\leq\log{\operatorname{l}(S)}$. If $p=2$, then
$\lvert\operatorname{Out}S\rvert=6f\leq\log
q^{6}\leq\log{\operatorname{l}(S)}$.

Suppose now that $S\cong{\operatorname{O}_{n}^{+}(2)}$ with $n=2t$ even. Then
there is at least one conjugacy class of maximal subgroups of smallest index
of type $H\cong\Omega_{n-1}(2)$ and index
${\operatorname{l}(S)}=2^{t-1}(2^{t}-1)$, and order

$\lvert
H\rvert=2^{(n/2-1)^{2}}(2^{n/2}-1)(2^{n/2-1}-1)\dotsm(2^{2}-1)\mathchar
24635\relax\;$

clearly ${\operatorname{l}(S)}<\lvert H\rvert$. In this case,
$\lvert\operatorname{Out}S\rvert\leq 6\leq\log{\operatorname{l}(S)}$.

By Atlas85 , if $n=8$, then there are three conjugacy classes of maximal
subgroups of smallest index fused under the triality automorphism; moreover,
${\operatorname{l}(S)}=120$ and $S$ has an ordinary maximal subgroup of type
$2_{+}^{1+8}:(S_{3}\times S_{3}\times S_{3})$ and index
$1575<120^{2}={\operatorname{l}(S)}^{2}$. Assume that $n\geq 10$. By
(BrayHoltRoneyDougal13, , Tables 8.66 and 8.82) and (KleidmanLiebeck90, ,
Table 3.5.E), this subgroup is ordinary. Furthermore,
$\lvert\operatorname{Out}S\rvert=6<\log{\operatorname{l}(S)}$.

Assume now that $S\cong{\operatorname{O}_{n}(3)}$, where $n=2t+1$ is odd. Then
there exists a conjugacy class of maximal subgroups isomorphic to
$H\cong\Omega_{n-1}^{-}(3).2$, with index
${\operatorname{l}(S)}=3^{t}(3^{t}-1)/2$ and

$\lvert
H\rvert=3^{t(t-1)}(3^{t}+1)(3^{2t-2}-1)(3^{2t-4}-1)\dotsm(3^{4}-1)(3^{2}-1),$

so that ${\operatorname{l}(S)}<\lvert H\rvert$. Furthermore, by
(BrayHoltRoneyDougal13, , Tables 8.39, 8.58, and 8.74) and (KleidmanLiebeck90,
, Table 3.5.D), these maximal subgroups are ordinary. In this case,
$\lvert\operatorname{Out}S\rvert=2\cdot 1\cdot 2=4<\log{\operatorname{l}(S)}$.

Assume that $S\cong{\operatorname{O}_{n}^{+}(3)}$, where $n=2t$ is even. The
maximal subgroups of the smallest index have type $H\cong\Omega_{n-1}(3).h$,
where $h=\gcd(t-1,2)$. Their index is
${\operatorname{l}(S)}=3^{t-1}(3^{t}-1)/2$, clearly smaller than their order
$\lvert H\rvert=(1/2)3^{(t-1)^{2}}\prod_{i=1}^{t-1}(3^{2i}-1)$. In this case,
$\lvert\operatorname{Out}S\rvert=2^{2}\cdot 1\cdot
2=8<\log{\operatorname{l}(S)}$ if $n\geq 10$.

In the case that $S\cong{\operatorname{O}_{8}^{+}(3)}$,
${\operatorname{l}(S)}=1\,080$, there are six conjugacy classes of maximal
subgroups isomorphic to $H$, the outer automorphism group of $S$ is isomorphic
to $S_{4}$ and there is an ordinary subgroup of type
$3_{+}^{1+8}:2({\operatorname{Alt}(4)}\times\operatorname{Alt}(4)\times\operatorname{Alt}(4)).2$,
according to Atlas85 , of index $36\,400<{\operatorname{l}(S)}^{2}$. Moreover,
$\lvert\operatorname{Out}S\rvert=24<3\log 1\,080=3\log{\operatorname{l}(S)}$.

Assume that $n=2t\geq 10$. By (BrayHoltRoneyDougal13, , Tables 8.66 and 8.82)
and (KleidmanLiebeck90, , Table 3.5.E), there are two conjugacy classes of
subgroups of the smallest index $\operatorname{l}(S)=3^{t}(3^{t}-1)/2$. On the
other hand, there is an ordinary maximal parabolic subgroup of type
$3^{n-2}.(\Omega^{+}_{n-2}(3).2)$, of index
$(3^{t}-1)(3^{t-1}+1)/2<{\operatorname{l}(S)}^{2}$. In this case,
$\lvert\operatorname{Out}S\rvert=\gcd(2,3-1)^{2}\cdot 1\cdot 2=8$ and, since
$\operatorname{l}(S)\geq 3^{5}(3^{5}-1)/2>2^{8}$, we conclude that the
inequality $\lvert\operatorname{Out}S\rvert<\log\operatorname{l}(S)$ also
holds in this case.

Suppose that $S\cong{\operatorname{O}_{n}(q)}$ where $n=2t+1$ is odd,
$q=p^{f}\neq 3$, and $p$ is an odd prime. Then the smallest index of a maximal
subgroup of $S$ corresponds to
$H\cong[q^{n-2}].((\Omega_{n-2}(q)\times(q-1)/2).2)$, of index
$(q^{n-1}-1)/(q-1)$. Since $\lvert
H\rvert=(1/2)q^{n-2}q^{(t-1)^{2}}\prod_{i=1}^{t-1}(q^{2i}-1)$, it is clear
that $\lvert H\rvert>{\operatorname{l}(S)}$. By (BrayHoltRoneyDougal13, ,
Tables 8.39, 8.58, and 8.74) and (KleidmanLiebeck90, , Table 3.5.D), these
maximal subgroups are ordinary. Moreover,
$\lvert\operatorname{Out}S\rvert=2^{2}\cdot f\cdot 1\leq 2\log 2^{f}\leq 2\log
q<\log{\operatorname{l}(S)}$.

Suppose now that $n=2t$, $q=2^{f}$, $f\geq 2$, and that
$(n,\varepsilon)\neq(8,{+})$. In this case, the smallest index of a maximal
subgroup corresponds to subgroups of type
$H=[q^{n-2}].(\Omega_{n-2}^{\varepsilon}(q)\times(q-1))$, of index
${\operatorname{l}(S)}=(q^{t}-\varepsilon)(q^{t+1}+\varepsilon)/(q-1)$ and
order $\lvert
H\rvert=q^{n-2}q^{(t-1)(t-2)}(q^{t-1}-\varepsilon)\prod_{i=1}^{t-1}(q^{2i}-1)$.
We can see that $\lvert H\rvert>{\operatorname{l}(S)}$. By
(BrayHoltRoneyDougal13, , Tables 8.52, 8.66, 8.68, 8.82, and 8.84) and
(KleidmanLiebeck90, , Tables 3.5.E and 3.5.F), we see that these subgroups are
ordinary. Furthermore, $\lvert\operatorname{Out}S\rvert=f\cdot 2$ if
$\varepsilon={+}$ and $\lvert\operatorname{Out}S\rvert=2f\cdot 1$ if
$\varepsilon={-}$. In both cases,
$\lvert\operatorname{Out}S\rvert\leq\log{\operatorname{l}(S)}$.

Finally, suppose that $n=2t$, $q=p^{f}$, $p$ is an odd prime, the pair
$(m,\varepsilon)$ is different from $(8,{+})$, and $(q,\varepsilon)$ is
different from $(3,{+})$. Then the smallest index of a maximal subgroup
corresponds to the subgroups of type $H\cong
p^{f(m-2)}.((\Omega_{m-2}^{\varepsilon}(q)\times(q-1)/h).j$, where
$(h,j)=(2,2)$ if $\gcd(q^{t}-\varepsilon,4)=2$, $(h,j)=(2,1)$ if
$\gcd(q^{t}-\varepsilon,4)=4$ and $\varepsilon(q^{t-1}-\varepsilon,4)=2$, and
$(h,j)=(4,2)$ if $\gcd(q^{t}-\varepsilon,4)=4$ and
$\gcd(q^{t-1}-\varepsilon,4)=1$. This index is
${\operatorname{l}(S)}=(q^{t}-\varepsilon)(q^{t-1}+\varepsilon)/(q-1)$. As in
the previous cases, ${\operatorname{l}(S)}<\lvert H\rvert$. This subgroup is
ordinary by (BrayHoltRoneyDougal13, , Tables 8.52, 8.66, 8.68, 8.82, and 8.84)
and (KleidmanLiebeck90, , Tables 3.5.E and 3.5.F). Furthermore,
$\lvert\operatorname{Out}S\rvert\leq 2^{2}\cdot f\cdot 2\leq\log
q^{6}\leq\log{\operatorname{l}(S)}$.

_Groups of type $G_{2}(q)$_

The maximal subgroups of smallest index of the simple groups $G_{2}(q)$,
$q>2$, have been studied in (Vasilyev96, , Theorem 1).

Assume that $S\cong G_{2}(3)$. Then $P\cong\operatorname{PSU}_{3}(3):2$ is a
maximal subgroup of the smallest possible index ${\operatorname{l}(S)}=351$
and order $12\,096>{\operatorname{l}(S)}$. By Atlas85 , there are two
conjugacy classes of maximal subgroups of this index and there is a conjugacy
class of ordinary maximal subgroups of type $\operatorname{PSL}_{2}(8):3$ and
index $2\,808<{\operatorname{l}(S)}^{2}$. In this case,
$\lvert\operatorname{Out}S\rvert=2<\log{\operatorname{l}(S)}$.

Assume that $S\cong G_{2}(4)$. Then $P\cong J_{2}$ is a maximal subgroup of
the smallest possible index ${\operatorname{l}(S)}=416$ and order
$604\,800>{\operatorname{l}(S)}$. According to Atlas85 , this subgroup is
ordinary. Moreover,
$\lvert\operatorname{Out}S\rvert=2<\log{\operatorname{l}(S)}$.

Suppose now that $S\cong G_{2}(q)$ with $q\geq 5$. Then
${\operatorname{l}(S)}=(q^{6}-1)/(q-1)$.

Assume that $S\cong G_{2}(q)$ with $q=2^{f}$, $f\geq 3$. Then
$P_{1}\cong(2^{f}.2^{4f}):({\operatorname{PSL}_{2}(q)}\times(q-1))$ and
$P_{2}\cong(2^{2f}.2^{3f}):({\operatorname{PSL}_{2}(q)}\times(q-1))$ are
maximal subgroups of $S$ of the smallest possible index. We see in
(BrayHoltRoneyDougal13, , Table 8.30) that these subgroups are ordinary.
Clearly, ${\operatorname{l}(S)}<\lvert P\rvert$ and
$\lvert\operatorname{Out}S\rvert=f\leq\log{\operatorname{l}(S)}$.

Assume that $S\cong G_{2}(3^{f})$ with $f\geq 2$. Then the smallest index
maximal subgroups of $S$ are of type $P\cong(3^{f}.3^{2f}\times
3^{2f}):(2.({\operatorname{PSL}_{2}(q)}\times(q-1)/2).2)$. Note that $\lvert
P\rvert>{\operatorname{l}(S)}$. By (BrayHoltRoneyDougal13, , Table 8.42),
there are two conjugacy classes of subgroups of this type. There is a
conjugacy class of ordinary subgroups of type
$({\operatorname{SL}_{2}(q)}\circ{\operatorname{SL}_{2}(q)}).2$ and index
$q^{4}(q^{4}+q^{2}+1)=q^{4}(q^{6}-1)/(q^{2}-1)<{\operatorname{l}(S)}^{2}$.
Moreover, $\lvert\operatorname{Out}T\rvert=2f\leq\log{\operatorname{l}(S)}$.

Now assume that $q=p^{s}$, with $p$ a prime, $p>3$. Then there are two
conjugacy classes of maximal subgroups of the smallest index, namely
$P_{1}\cong(p^{2f}.(p^{f}.p^{2f})):(2.({\operatorname{PSL}_{2}(q)}\times(q-1)/2).2)$
and
$P_{2}\cong(p^{f}.p^{4f}):(2.({\operatorname{PSL}_{2}(q)}\times(q-1)/2).2)$.
Again, $\lvert P_{1}\rvert>{\operatorname{l}(S)}$,
$\lvert\operatorname{Out}S\rvert=f\leq\log{\operatorname{l}(S)}$ and, by
(BrayHoltRoneyDougal13, , Table 8.41), these subgroups are ordinary.

_Groups of type $F_{4}(q)$_

The smallest index maximal subgroups of $F_{4}(q)$ have been studied in
(Vasilyev96, , Theorem 2). This index is

${\operatorname{l}(S)}=\frac{(q^{12}-1)(q^{4}+1)}{q-1}$

and is attained by a parabolic subgroup. Since the order of this subgroup is
$\lvert P\rvert=q^{24}(q^{4}-1)(q^{6}-1)(q^{2}-1)(q-1)$, we have that $\lvert
P\rvert>{\operatorname{l}(S)}$. Moreover, $\lvert\operatorname{Out}S\rvert$ is
$f$ if $p\neq 2$ and $2f$ if $p=2$. In both cases,
$\lvert\operatorname{Out}S\rvert\leq\log q^{4}\leq\log{\operatorname{l}(S)}$.

Assume first that $q=2^{f}$. Then there are two conjugacy classes of parabolic
maximal subgroup isomorphic to $P\cong(2^{f}.2^{8f}\times
2^{6f}):({\operatorname{PSp}_{6}(q)}\times(q-1))$. By
(LiebeckSaxlSeitz92-plms, , Table 5.1), $S$ has an ordinary maximal subgroup
of type $H\cong e.\bigl{(}L_{3}^{\varepsilon}(q)\times
L_{3}^{\varepsilon}(q)\bigr{)}.e.2$, where $\varepsilon=\pm 1$,
$e=\gcd(3,q-\varepsilon)$, $L_{3}^{+1}(q)=\operatorname{PSL}_{3}(q)$ and
$L_{3}^{-1}(q)=\operatorname{PSU}_{3}(q)$. Then $v=\lvert
S:H\rvert=q^{18}(q+1)^{2}(q^{2}-q+1)^{2}(q^{2}+1)^{2}(q^{4}-q^{2}+1)(q^{4}+1)$
and we can check that $v\leq{\operatorname{l}(S)}^{2}$.

Assume that $q=p^{f}$ with $p$ a prime different from $2$. Then
$P_{1}=(p^{f}.p^{14f}):(2.({\operatorname{PSp}_{4}(q)}\times(q-1)/2).2)$ or
$P_{4}=(p^{7f}.p^{8f}):(2.({\operatorname{O}_{7}(q)}\times(q-1)/2).2)$ are
parabolic maximal subgroups of $S$ of the smallest index. The conjugacy
classes of both subgroups are fixed under the outer automorphism group of $S$
since both are parabolic.

_Groups of type $E_{6}(q)$_

The maximal subgroups of smallest index of $S\cong E_{6}(q)$ have been studied
in (Vasilyev97, , Theorem 1). The smallest index of a maximal subgroup of $S$
is
${\operatorname{l}(S)}=(q^{9}-1)(q^{8}+q^{4}+1)/(q-1)=(q^{9}-1)(q^{12}-1)/\bigl{(}(q^{4}-1)(q-1)\bigr{)}$,
corresponding to two conjugacy classes of parabolic subgroups
$P_{1}=p^{16f}:(e.{\operatorname{O}_{10}^{+}(q)}\times(q-1)/e^{\prime}).e)$,
where $e=\gcd(q-1,4)$, $e^{\prime}=e\cdot\gcd(q-1,3)$, interchanged by the
graph automorphism. Clearly, ${\operatorname{l}(S)}<\lvert P_{1}\rvert$.
Moreover, $\lvert\operatorname{Out}S\rvert=\gcd(3,q-1)\cdot f\cdot 2\leq
6f\leq\log q^{8}\leq\log{\operatorname{l}(S)}$. The parabolic subgroup $P_{2}$
is ordinary and is of type $[q^{21}]:H$ where $H$ has a section isomorphic to
$\operatorname{PSL}_{6}(q)$ (see also (Craven21-arXiv-max-sgps-except, , Table
7.3)) and so its index divides $v=(q^{12}-1)(q^{4}+1)(q^{9}-1)/(q^{3}-1)$.
Then

$\frac{v}{{\operatorname{l}(S)}^{2}}=\frac{(q^{8}-1)(q^{4}-1)(q-1)^{2}}{(q^{12}-1)(q^{9}-1)(q^{3}-1)}<1,$

therefore $v<{\operatorname{l}(S)}^{2}$. We conclude that $\lvert
S:P_{2}\rvert\leq v\leq{\operatorname{l}(S)}^{2}$.

_Groups of type $E_{7}(q)$_

The maximal subgroups of smallest index of $S\cong E_{7}(q)$ for $q=p^{f}$
have been studied in (Vasilyev97, , Theorem 2). They are the parabolic
subgroups $P\cong p^{27f}:(d^{\prime}.(E_{6}(q)\times(q-1)/c).d^{\prime})$,
with $d^{\prime}=\gcd(q-1,3)$, $c=\gcd(q-1,2)\cdot d^{\prime}$, of index
${\operatorname{l}(S)}=(q^{14}-1)(q^{9}+1)(q^{5}+1)/(q-1)$. Clearly $P_{1}$ is
ordinary, ${\operatorname{l}(S)}<\lvert P_{1}\rvert$, and
$\lvert\operatorname{Out}S\rvert=\gcd(2,q-1)\cdot f\cdot 1\leq 2f\leq\log
q^{5}\leq\log{\operatorname{l}(S)}$.

_Groups of type $E_{8}(q)$_

The maximal subgroups of smallest index of $S\cong E_{8}(q)$ for $q=p^{f}$
have been studied in (Vasilyev97, , Theorem 3). They are the parabolic
subgroups $P\cong(p^{f}.p^{56f}):(d.(E_{7}(q)\times(q-1)/d).d)$, with
$d=\gcd(q-1,2)$, of index
${\operatorname{l}(S)}=(q^{20}-1)(q^{12}+1)(q^{10}+1)(q^{6}+1)/(q-1)$. Clearly
$P$ is ordinary and ${\operatorname{l}(S)}<\lvert P_{1}\rvert$, and
$\lvert\operatorname{Out}T\rvert=f\leq\log
q^{6}\leq\log{\operatorname{l}(S)}$.

_Twisted groups_

In (Vasilyev98, , Theorem 1), it is shown that if $S\cong{}^{2}\\!B_{2}(q)$,
with $q=2^{f}$, $f$ an odd integer greater than $1$, the smallest index of a
maximal subgroup of $S$ corresponds to the parabolic subgroup
$P\cong(2^{f}.2^{f}):(q-1)$, with index ${\operatorname{l}(S)}=q^{2}+1$. By
(BrayHoltRoneyDougal13, , Table 8.16), these subgroups are ordinary and,
clearly, ${\operatorname{l}(S)}<\lvert P\rvert$ and
$\lvert\operatorname{Out}S\rvert=f=\log q\leq\log{\operatorname{l}(S)}$.

In (Vasilyev98, , Theorem 2), it is shown that if $S\cong{}^{2}\\!G_{2}(q)$,
with $q=3^{f}$ and $f$ an odd integer greater than $1$, there is a class of
smallest index maximal subgroups isomorphic to
$P\cong(3^{f}.3^{f}.3^{f}):(q-1)$ and index $q^{3}+1$. By
(BrayHoltRoneyDougal13, , Table 8.43), these subgroups are ordinary and,
clearly, ${\operatorname{l}(S)}<\lvert P\rvert$ and
$\lvert\operatorname{Out}S\rvert=f\leq\log q\leq\log{\operatorname{l}(S)}$.

In (Vasilyev98, , Theorem 3), it is shown that if $S\cong{}^{3}\\!D_{4}(q)$,
with $q=p^{f}$, the smallest index maximal subgroups of $S$ are isomorphic to
$P\cong(p^{f}.p^{8f}):(d.({\operatorname{PSL}_{2}(q^{3})}\times(q-1)/d).d)$,
where $d=\gcd(2,q-1)$, with index
${\operatorname{l}(S)}=(q^{8}+q^{4}+1)(q+1)$. By (BrayHoltRoneyDougal13, ,
Table 8.51), these subgroups are ordinary. Moreover, $\lvert
P\rvert=dq^{12}(q^{6}-1)(q-1)=dq^{12}(q-1)^{2}(q+1)(q^{4}+q^{2}+1)>{\operatorname{l}(S)}$
and $\lvert\operatorname{Out}S\rvert=f\leq\log
q\leq\log{\operatorname{l}(S)}$.

In (Vasilyev98, , Theorem 4), it is shown that for $S\cong{}^{2}\\!E_{6}(q)$,
with $q=p^{f}$, the smallest index maximal subgroups of $S$ are isomorphic to
$P\cong(p^{f}.p^{20f}):(d_{+}.{\operatorname{PSU}_{6}(q)}\times(q-1)/d^{\prime}_{+}).d^{\prime}_{+}$,
where $d_{+}=\gcd(2,q+1)$, $d_{+}^{\prime}=\gcd(3,q+1)$. Their index is
${\operatorname{l}(S)}=(q^{12}-1)(q^{6}-q^{3}+1)(q^{4}+1)/(q-1)$. These
subgroups are clearly ordinary because they are parabolic. Clearly, $\lvert
P\rvert>{\operatorname{l}(S)}$ and
$\lvert\operatorname{Out}S\rvert=\gcd(3,q+1)\cdot f\cdot 1\leq 3f\leq\log
q^{11}\leq\log{\operatorname{l}(S)}$.

By (Vasilyev98, , Theorem 5), if $S\cong{}^{2}\\!F_{4}(q)$, with $q=2^{f}$,
$f>1$ odd, the smallest index maximal subgroups of $S$ are isomorphic to
$P\cong(2^{f}.2^{4f}.2^{5f}):({}^{2}\\!B_{2}(q)\times(q-1))$, with index
${\operatorname{l}(S)}=(q^{6}+1)(q^{3}+1)(q+1)$ and order $\lvert
P\rvert=q^{12}(q^{2}+1)(q-1)^{2}$. It is clear that $\lvert
P\rvert<{\operatorname{l}(S)}$ and $\lvert\operatorname{Out}S\rvert=f\leq\log
q\leq\log{\operatorname{l}(S)}$. Moreover, the subgroup $P$ is ordinary
because it is a parabolic subgroup.

######  Remark 2.

We thank one of the anonymous referees for drawing our attention to the
interesting paper AlaviBurness15  of Alavi and Burness. These authors have
obtained in their Theorems 2–5 for each simple group $G$ and in their Theorem
7 for each almost simple group $G$ the list of all maximal subgroups $H$ of
$G$ with $\lvert H\rvert^{3}\geq\lvert G\rvert$. They call them _large_. In
fact, all maximal subgroups appearing in the proof of Theorem A are large in
this sense and so all of them are mentioned in AlaviBurness15 .

######  Remark 3.

Note that the smallest index of a smallest core-free maximal subgroup of an
almost simple group with socle $\operatorname{PSL}_{n}(q)$ with $n\geq 3$ can
be different from the indices of the parabolic and the double parabolic
subgroups. According to Atlas85 , if $S=\operatorname{PSL}_{3}(4)$, then the
extension $S.2_{1}$ contains a maximal subgroup of type $\mathrm{M}_{10}$ and
least index $56$, different from the indices of the parabolic subgroups of
type $P_{1}$, of index $21$, that do not exist in this extension, and the
double parabolic subgroups of type $P_{1,2}$, of index $105$, that also appear
as a maximal subgroup of $S.2_{1}$.

######  Remark 4.

Let $S=\operatorname{PSL}_{n}(2)\cong\operatorname{GL}_{n}(2)$, where $n$ is a
prime, $n\geq 5$. There is a unique class of ordinary maximal subgroups of $S$
of geometric type by Tables 8.18, 8.19, 8.36, 8.37, 8.70, 8.71 of
BrayHoltRoneyDougal13  and (KleidmanLiebeck90, , Table 3.5.A), namely the
subgroup $M=\operatorname{GL}_{1}(2^{n}):n$ in the Aschbacher class
$\mathcal{C}_{3}$. Note that $\lvert
S\rvert=(2^{n}-1)(2^{n}-2)\dotsm(2^{n}-2^{n-1})$, while $\lvert
M\rvert=(2^{n}-1)n$. Consequently, $\lvert
S:M\rvert=(2^{n}-2)\dotsm(2^{n}-2^{n-1})/n$. The smallest index of a core-free
maximal subgroup of $S$ is smaller or equal than the index of the parabolic
subgroup $P_{1}$, corresponding to the stabiliser of a vector subspace of
dimension $1$. Since $\lvert
P_{1}\rvert=2^{n-1}(2^{n-1}-1)(2^{n-1}-2)\dotsm(2^{n-1}-2^{n-2})$, we have
that $\lvert S:P_{1}\rvert=2^{n}-1$. Now the largest power of $2$ dividing
$\lvert S:M\rvert$ is $2\cdot 2^{2}\dotsm 2^{n-1}=2^{n(n-1)/2}$. Therefore
$\lvert
S:M\rvert={(2^{n})}^{(n-1)/2}>{(2^{n}-1)}^{(n-1)/2}\geq{\operatorname{l}(S)}^{(n-1)/2}$.
In particular, there cannot exist a constant $c$ such that if
$\operatorname{l}_{1}(S)$ is the common index of a maximal subgroup of
geometric type in all almost simple groups associated with the non-abelian
simple group $S$, $\operatorname{l}_{1}(S)\leq{\operatorname{l}(S)}^{c}$ for
all non-abelian simple groups $S$.

######  Remark 5.

The groups $\operatorname{PSL}_{n}(q)$ for $n\geq 3$, $q=q_{0}^{2}$, $q_{0}$ a
prime power, contain always a maximal subgroup of the form
$\operatorname{PSL}_{n}(q_{0})$ or $\operatorname{PSU}_{n}(q_{0})$, but their
indices in $\operatorname{PSL}_{n}(q)$ are polynomials on $q_{0}$ of degree
larger than the degree of
${\operatorname{l}({\operatorname{PSL}_{n}(q)})}^{2}=(q_{0}^{2n}-1)^{2}/(q_{0}^{2}-1)^{2}$
when $n\geq 4$. Hence this construction cannot be extended further. The groups
$\operatorname{PSL}_{2m}(q)$ for $m\geq 2$, $q$ a prime power,
$(2m,q)\neq(4,2)$, contain a parabolic subgroup $P_{m}$ that is ordinary.
However, for $m\geq 4$, this subgroup has index in
$\operatorname{PSL}_{2m}(q)$ that is a polynomial on $q$ of degree larger than
the one of
${\operatorname{l}({\operatorname{PSL}_{2m}(q)})}^{2}=(q^{2m}-1)^{2}/(q-1)^{2}$.
This justifies that these constructions cannot be extended further and so
$\operatorname{PSL}_{3}(q_{0}^{2})$, $\operatorname{PSL}_{4}(q)$,
$\operatorname{PSL}_{6}(q)$ belong to the class $\mathfrak{Y}$, but not the
linear groups in larger dimensions.

######  Remark 6.

Let $S=\operatorname{PSL}_{m}(2^{f})$ with $m\geq 3$ and $m\mid 2^{f}-1$ (for
example, $m-1\mid f$). Then $\lvert{\operatorname{Out}S}\rvert=(2^{f}-1)\cdot
f\cdot 2$ and ${\operatorname{l}(S)}=(2^{mf}-1)/(2^{f}-1)$. Since

$\lim_{f}\frac{\log((2^{mf}-1)/(2^{f}-1))}{m\cdot f\cdot 2}=\frac{m-1}{2m},$

it follows that the bound $\lvert\operatorname{Out}S\rvert\leq
3\log{\operatorname{l}(S)}$ cannot be improved.

Proof: [Proof of Theorem B] The result is clear for sporadic and alternating
groups, since then the outer automorphism group is trivial, isomorphic to
$C_{2}$, or isomorphic to $C_{2}\times C_{2}$. It only remains to consider the
case when $S$ is a simple group of Lie type. According to (Atlas85, , Table
5), the outer automorphism group is isomorphic to an extension of a metacyclic
group by a cyclic group, with the possible exception of
$\operatorname{O}_{2m}^{+}(q)$ with $m\geq 4$, $m$ even. By (Kleidman87, ,
page 181),

$\operatorname{Out}({\operatorname{O}_{8}^{+}(q)})\cong\begin{cases}\operatorname{Sym}(3)\times
C_{f}&\text{if $q$ is even,}\\\ \operatorname{Sym}(4)\times C_{f}&\text{if $q$
is odd.}\end{cases}$

If $m\geq 6$ is even, the same arguments show that

$\operatorname{Out}({\operatorname{O}_{2m}^{+}(q)})\cong\begin{cases}D_{8}\times
C_{f}&\text{if $q$ is even,}\\\ C_{2}\times C_{f}&\text{if $q$ is
odd.}\end{cases}$

By considering the normal subgroup isomorphic to $C_{f}$, we see that all
subgroups of $\operatorname{Out}({\operatorname{O}_{2m}^{+}(q)})$ for $m\geq
4$, $m$ even, can also be generated by at most $3$ generators. In all other
cases, all subgroups of $\operatorname{Out}S$ are extensions of a metacyclic
group by a cyclic group and so they are also $3$-generated.

If $\lvert\operatorname{Out}S\rvert\leq\log{\operatorname{l}(S)}$, then given
a subgroup of $G$, we have at most $\log^{3}{\operatorname{l}(S)}$
possibilities for a generating set. It follows that the number of subgroups of
$\operatorname{Out}S$ is at most $\log^{3}{\operatorname{l}(S)}$. Therefore we
must study the cases in which the inequality
$\lvert\operatorname{Out}S\rvert\leq\log{\operatorname{l}(S)}$ can fail, that
is, the cases mentioned in Theorem A (5).

We begin with the linear groups $S=\operatorname{PSL}_{m}(q)$. Suppose first
that $m=2$ and that $q=3^{f}$. Then

$\lvert\operatorname{Out}S\rvert=2\cdot f\cdot 1=\frac{2}{\log 3}\log
3^{f}\leq\frac{2}{\log 3}\log{\operatorname{l}(S)}.$

Note that $\operatorname{Out}S$ and all its subgroups are $2$-generated. One
of the generators can be taken in the subgroup of order $2$, while the other
one can be chosen in $2f$ different ways. This gives for the number of
subgroups an upper bound of

$4f\leq 2\cdot\frac{2}{\log 3}\log{\operatorname{l}(S)}=\frac{4}{\log
3}\log{\operatorname{l}(S)}.$

Since $4/{\log 3}\leq\log^{2}5\leq\log^{2}{\operatorname{l}(S)}$, we conclude
that the number of subgroups of $\operatorname{Out}S$ is bounded by
$\log^{3}{\operatorname{l}(S)}$.

Let $S=\operatorname{PSL}_{m}(q)$ with $m\geq 3$. Then

$\displaystyle\lvert\operatorname{Out}S\rvert$ $\displaystyle=\gcd(m,q-1)\cdot
f\cdot 2\leq 2mf$ $\displaystyle=\frac{2m}{(m-1)\log p}\log
p^{(m-1)f}\leq\frac{2m}{(m-1)\log p}\log{\operatorname{l}(S)}.$

Note that

$\frac{2m}{(m-1)\log p}\leq 3.$

Suppose that $f=1$. Since $\operatorname{l}({\operatorname{PSL}_{3}(2)})=7$
and $\lvert{\operatorname{Out}{\operatorname{PSL}_{3}(2)}}\rvert=2$, and
$\operatorname{l}({\operatorname{PSL}_{4}(2)})=8$ and
$\lvert{\operatorname{Out}{\operatorname{PSL}_{4}(2)}}\rvert=2$, we can assume
that $(m,q)\notin\\{(3,2),(4,2)\\}$. Consequently,
$\operatorname{l}(S)=(q^{m}-1)/(q-1)=q^{m-1}+q^{m-2}+\dots+q+1$ and so
$\log\operatorname{l}(S)>(m-1)\log q$. We have that $\operatorname{Out}S$ is
$2$-generated and has order $\gcd(m,q-1)\cdot 2$. Moreover, all subgroups of
$\operatorname{Out}S$ are $2$-generated, the first generator can be taken in
the normal cyclic subgroup of order $\gcd(m,q-1)$ and the second one in
$\operatorname{Out}S$. This gives at most $\gcd(m,q-1)^{2}\cdot 2$
possibilities for a subgroup of $\operatorname{Out}S$. Since
$(m-1)^{3}\log^{3}q-2m^{2}>0$ for $m\geq 3$ if $q\geq 3$ and
$(m-1)^{3}\log^{3}2-2m^{2}=(m-1)^{3}-2m^{2}>0$ for $m\geq 5$, we have that

$\gcd(m,q-1)^{2}\cdot 2\leq
2m^{2}\leq(m-1)^{3}\log^{3}q\leq\log^{3}\operatorname{l}(S)$

for $m\geq 3$, $(m,q)\notin\\{(3,2),(4,2)\\}$.

Hence we can assume that $f\geq 2$. Every subgroup of $\operatorname{Out}S$ is
$3$-generated, and the generators can be taken one in the group of diagonal
automorphisms of order $\gcd(m,q-1)$, another one in the group generated by
the diagonal and field automorphisms of order $\gcd(m,q-1)f$, and the third
one in $\operatorname{Out}S$. It follows that the number of possible choices
is at most $2f^{2}\gcd(m,q-1)^{3}$. Suppose first that $\gcd(m,q-1)<m$, then
$\gcd(m,q-1)\leq m/2$ and so the number of possible subgroups is bounded by

$2f^{2}\frac{m^{3}}{8}\leq\frac{1}{8}\frac{(2fm)^{3}}{8}\leq\frac{1}{8}\frac{m^{3}}{(m-1)^{3}\log^{3}p}\log^{3}{\operatorname{l}(S)}<\log^{3}{\operatorname{l}(S)}.$

Therefore we can assume that $\gcd(m,q-1)=m$, that is, $m\mid q-1$. The number
of possible subgroups of $\operatorname{Out}S$ is bounded by

$2f^{2}m^{3}\leq\frac{(2fm)^{3}}{8}\leq\frac{m^{3}}{(m-1)^{3}\log^{3}p}\log^{3}{\operatorname{l}(S)}.$

If $p\geq 3$, then $m^{3}<(m-1)^{3}\log^{3}p$ and so the number of possible
subgroups of $\operatorname{Out}S$ is again bounded by
$\log^{3}{\operatorname{l}(S)}$. Therefore we can suppose that $p=2$. In
particular, $m$ must be odd. Assume that $m$ is a prime. Then the number of
choices of the element of the group of diagonal automorphisms can be reduced
from $m$ to $2$, namely the trivial element and a generator. This gives that
the number of possible subgroups of $\operatorname{Out}S$ is bounded by

$2\cdot mf\cdot
2mf=(2mf)^{2}\leq\frac{4m^{2}}{(m-1)^{2}}\log^{2}{\operatorname{l}(S)}.$

If $m=5$, then ${\operatorname{l}(S)}\geq(2^{4})^{4}=2^{16}$, and so
$\log{\operatorname{l}(S)}\geq 16$. It follows that
$4m^{2}/(m-1)^{2}<\log{\operatorname{l}(S)}$. If $m=7$, then
${\operatorname{l}(S)}\geq(2^{3})^{6}=2^{18}$ and so
$\log{\operatorname{l}(S)}\geq 18$. Consequently,
$4m^{2}/(m-1)^{2}<\log{\operatorname{l}(S)}$. Hence for $m\in\\{5,7\\}$, the
number of subgroups of $\operatorname{Out}S$ is bounded by
$\log^{3}{\operatorname{l}(S)}$. Assume now that $m\geq 9$ is odd. The number
of choices of the element of the group of diagonal automorphisms can be
reduced to the number of subgroups of this cyclic group, which coincides with
the number of divisors of $m$. Since $m$ is odd, this number is not greater
than $2m/3$. The number of possible choices for the generators of a subgroup
of $\operatorname{Out}S$ is bounded by

$(2m/3)\cdot mf\cdot
2mf=\frac{1}{6f}(2mf)^{3}\leq\frac{1}{12}\frac{8m^{3}}{(m-1)^{3}}\log^{3}{\operatorname{l}(S)},$

and $8m^{3}/\bigl{(}12(m-1)^{3}\bigr{)}\leq 243/256$, so that this number is
bounded by $\log^{3}{\operatorname{l}(S)}$. It only remains the case $m=3$. In
this case, the group of outer automorphisms of $S$ has the presentation

$\operatorname{Out}S=\langle x,y,z\mid
x^{3}=y^{f}=z^{2}=1,x^{y}=x^{-1},x^{z}=x^{-1},y^{z}=y^{-1}\rangle.$

Note that $\langle y^{2}\rangle$ centralises $\langle x\rangle$. Now

$\operatorname{Out}S/\langle y^{2}\rangle\cong\langle a,b\mid
a^{3}=b^{2}=1,a^{b}=a^{-1}\rangle\times\langle c\mid
c^{2}=1\rangle\cong\operatorname{Sym}(3)\times C_{2},$

where $a=\bar{x}$, $b=\bar{z}$, $c=\bar{y}\bar{z}$. Note that every subgroup
of $\operatorname{Sym}(3)\times C_{2}$ is $2$-generated. A pair of generators
can be obtained by taking an element of $\langle a,b\rangle$ and an element of
the set $\\{1,c,ac,bc,abc,a^{2}bc\\}$. The preimages of these sets under the
natural epimorphism from $\operatorname{Out}S$ onto
$(\operatorname{Out}S)/\langle y^{2}\rangle$ have $6(f/2)=3f$ elements each.
Hence every element of $\operatorname{Out}S$ can be obtained by considering an
element of $\langle y^{2}\rangle$, for which we have $f/2$ choices, and the
$3f$ choices for each element of the preimages. This gives a bound for the
number of subgroups of
$(f/2)(3f)^{2}=9f^{3}/2=9(2f)^{3}/16<(9/16)\log^{3}{\operatorname{l}(S)}<\log^{3}{\operatorname{l}(S)}$.
This completes the proof for the linear case.

If $S\cong\operatorname{PSU}_{3}(5)$, then
$\operatorname{Out}S\cong\operatorname{Sym}(3)$ has $6$ subgroups, clearly
$6\leq\log^{3}50=\log^{3}{\operatorname{l}(S)}$ by Atlas85 . Suppose that
$S\cong\operatorname{PSU}_{3}(q)$ with $q\notin\\{2,5\\}$. Then
${\operatorname{l}(S)}=q^{3}+1$ by (Mazurov93, , Theorem 3) and
$\operatorname{Out}S$ is a metacyclic group of order $3\cdot 2f=6f$ and all
its subgroups are also $2$-generated. Then the number of choices for a couple
of generators for a subgroup of $G$ is bounded by $3f\cdot
6f\leq(2/3)\log{\operatorname{l}(S)}\cdot(4/3)\log{\operatorname{l}(S)}<\log^{2}{\operatorname{l}(S)}<\log^{3}{\operatorname{l}(S)}$.
Assume now that $S\cong\operatorname{PSU}_{m}(q)$ with $q>2$ if $m$ is even
and $q^{2}=p^{f}$, with $p$ a prime. By (Mazurov93, , Theorem 3),
${\operatorname{l}(S)}=(q^{m}-(-1)^{m})(q^{m-1}-(-1)^{m-1})/(q^{2}-1)$.
Moreover, $\lvert\operatorname{Out}S\rvert=m\cdot(2f)\cdot 1$ is
$2$-generated. Since $2mf\leq 3\log{\operatorname{l}(S)}^{2}$, we have that
the number of choices for the pair of generators of a subgroup of
$\operatorname{Out}S$ is bounded by $mf\cdot
2mf\leq(9/2)\log^{2}{\operatorname{l}(S)}\leq\log^{3}{\operatorname{l}(S)}$,
because $9/2\leq\log
28=\log^{3}{\operatorname{l}\bigl{(}{\operatorname{PSU}_{3}(3)}\bigr{)}}<\log{\operatorname{l}(S)}$
by Atlas85 .

Finally, suppose that $G\cong{\operatorname{O}_{8}^{+}(q)}$, where $q=p^{f}$
and $p\in\\{3,5,7,11,13\\}$. Now
${\operatorname{l}(S)}=(q^{3}+q^{2}+q+1)(q^{3}+1)$ by (VasilevMazurov94, ,
Theorem) and $\operatorname{Out}S\cong\operatorname{Sym}(4)\times C_{f}$. All
subgroups of $\operatorname{Out}S$ are $3$-generated, and one generator can be
taken in $C_{f}$, another one in $\operatorname{Alt}(4)\times C_{f}$ and the
other one in the whole group. This gives at most
$f\cdot(12f)\cdot(24f)=288f^{3}$ possibilities for a subgroup of
$\operatorname{Out}S$. Since $24f\leq 3\log{\operatorname{l}(S)}$, we have
that $8f\leq\log{\operatorname{l}(S)}$. Consequently, $288f^{3}\leq
512f^{3}\leq\log^{3}{\operatorname{l}(S)}$. This completes the proof of the
theorem.

######  Remark 7.

We note that in the Janko sporadic group $S\cong J_{3}$ of order
$50\,232\,960$ and with ${\operatorname{l}(S)}=6\,156$, if $\xi=\log
50\,232\,960/\log 6\,156\approx 2.0323$, we have that $\lvert
S\rvert=\operatorname{l}(S)^{\xi}$. Therefore the exponent $2$ in
$\operatorname{l}(S)^{2}\leq\lvert S\rvert$ cannot be increased too much.

## Acknowledgement

Open Access funding provided thanks to the CRUE-CSIC agreement with Springer
Nature. We thank the anonymous referees for their huge effort in reading
carefully the manuscript and for identifying several typos and incorrect
statements. Their contributions have improved considerably the presentation of
the results of this paper and their proofs. We also thank the Editor-in-Chief,
Professor Fernando Etayo, for his kind help in the revision of the manuscript
and for his empathy and his patience with our concerns.

## Declarations

### Funding

These results are part of the R+D+i project supported by the Grant
PGC2018-095140-B-I00, funded by MCIN/AEI/10.13039/501100011033 and by “ERDF A
way of making Europe”, as well as by the Grant PROMETEO/2017/057 funded by
GVA/10.13039/501100003359, and partially supported by the Grant E22 20R,
funded by Departamento de Ciencia, Universidades y Sociedad del Conocimiento,
Gobierno de Aragón/10.13039/501100010067.

### Conflict of interest/Competing interests

The authors have no relevant financial or non-financial interests to disclose.

### Consent to participate

Not applicable

### Consent for publication

Not applicable

### Availability of data and materials

Not applicable

### Code availability

Not applicable

### Authors’ contributions

All authors have contributed equally to this paper.

## References

  *   * (1) Baer, R.: Classes of finite groups and their properties. Illinois J. Math. 1, 115–187 (1957). https://doi.org/10.1215/IJM/1255379396
  * (2) Ballester-Bolinches, A., Ezquerro, L.M.: Classes of Finite Groups. Mathematics and Its Applications, vol. 584. Springer, Dordrecht (2006). https://doi.org/10.1007/1-4020-4719-3. https://doi.org/10.1007/1-4020-4719-3
  * (3) Ballester-Bolinches, A., Esteban-Romero, R., Jiménez-Seral, P.: Bounds on the number of maximal subgroups of finite groups: applications. Mathematics 10, 1153–25 (2022). https://doi.org/10.3390/math10071153
  * (4) Borovik, A.V., Pyber, L., Shalev, A.: Maximal subgroups in finite and profinite groups. Trans. Amer. Math. Soc. 348(9), 3745–3761 (1996). https://doi.org/10.1090/S0002-9947-96-01665-0
  * (5) Guralnick, R.M., Maróti, A., Pyber, L.: Normalizers of primitive permutation groups. Adv. Math. 310, 1017–1063 (2017). https://doi.org/10.1016/j.aim.2017.02.012
  * (6) Conway, J.H., Curtis, R.T., Norton, S.P., Parker, R.A., Wilson, R.A.: Atlas of Finite Groups. Oxford Univ. Press, London (1985)
  * (7) Doerk, K., Hawkes, T.: Finite Soluble Groups. De Gruyter Expositions in Mathematics, vol. 4, p. 891. Walter de Gruyter & Co., Berlin (1992). https://doi.org/10.1515/9783110870138. https://doi.org/10.1515/9783110870138
  * (8) Mazurov, V.D.: Minimal permutation representations of finite simple classical groups. Special linear, symplectic, and unitary groups. Algebra Logic 32(3), 142–153 (1993). https://doi.org/10.1007/BF02261693
  * (9) Vasil’ev, V.A., Mazurov, V.D.: Minimal permutation representations of finite simple orthogonal groups. Algebra Logic 33(6), 1994 (1994). https://doi.org/10.1007/BF00756348
  * (10) Vasilyev, A.V.: Minimal permutation representations of finite simple exceptional groups of types ${G}_{4}$ and ${F}_{4}$. Algebra Logic 35(6), 371–383 (1996). https://doi.org/10.1007/BF02366397
  * (11) Vasilyev, A.V.: Minimal permutation representations of finite simple exceptional groups of types ${E}_{6}$, ${E}_{7}$, and ${E}_{8}$. Algebra Logic 36(5), 302–310 (1997). https://doi.org/10.1007/bf02671607
  * (12) Vasilyev, A.V.: Minimal permutation representations of finite simple exceptional twisted groups. Algebra Logic 37(1), 9–20 (1998). https://doi.org/10.1007/BF02684081
  * (13) Linton, S.A., Wilson, R.A.: The maximal subgroups of the Fischer groups ${\mathit{{F}i}_{24}}$ and ${\mathit{{F}i}_{24}^{\prime}}$. Proc. London Math. Soc. (3) 63, 113–164 (1991). https://doi.org/10.1112/plms/s3-63.1.113
  * (14) Wilson, R.A.: The maximal subgroups of the Baby Monster, I. J. Algebra 211, 1–14 (1999). https://doi.org/10.1006/jabr.1998.7601
  * (15) Wilson, R.A.: New computations in the Monster. In: Lepowsky, J., McKay, J., Tuite, M.P. (eds.) Moonshine: the First Quarter Century and Beyond. London Math. Soc. Lecture Note Ser., vol. 372, pp. 393–403. Cambridge Univ. Press, Cambridge (2010)
  * (16) Norton, S.P., Wilson, R.A.: A correction to the $41$-structure of the Monster, a construction of a new maximal subgroup ${\mathrm{{L}}_{2}(41)}$ and a new Moonshine phenomenon. J. London Math. Soc. (2) 87, 943–962 (2013). https://doi.org/10.1112/jlms/jds078
  * (17) Bray, J., Holt, D., Roney-Dougal, C.: The Maximal Subgroups of the Low-dimensional Finite Classical Groups. London Math. Soc. Lect. Note Ser., vol. 407. Cambridge Univ. Press, Cambridge, UK (2013). https://doi.org/10.1017/CBO9781139192576
  * (18) Kleidman, P.B., Liebeck, M.W.: The Subgroup Structure of the Finite Classical Groups. London Math. Soc. Lecture Notes Series, vol. 129. Cambridge Univ. Press, Cambridge, UK (1990). https://doi.org/10.1017/CBO9780511629235
  * (19) Liebeck, M.W., Saxl, J., Seitz, G.M.: Subgroups of maximal rank in finite exceptional groups of Lie type. Proc. London Math. Soc. (3) 65, 297–325 (1992). https://doi.org/10.1112/plms/s3-65.2.297
  * (20) Craven, D.A.: The maximal subgroups of the exceptional groups ${F}_{4}(q)$, $E_{6}(q)$ and ${}^{2}\\!{E}_{6}(q)$ and related almost simple groups. arXiv 2103.04869 (2021). https://doi.org/10.48550/arXiv.2103.04869
  * (21) Alavi, S.H., Burness, T.C.: Large subgroups of simple groups. J. Algebra 421, 187–233 (2015). https://doi.org/10.1016/j.jalgebra.2014.08.026
  * (22) Kleidman, P.B.: The maximal subgroups of the finite $8$-dimensional orthogonal groups $P\Omega^{+}(q)$ and of their automorphism groups. J. Algebra 110(1), 173–242 (1987). https://doi.org/10.1016/0021-8693(87)90042-1


$\displaystyle{}+\underbrace{\left.\frac{\partial(\boldsymbol{\alpha}^{k+1}\odot\tilde{X}^{k+1})}{\partial\tilde{X}^{k}}\right|_{\boldsymbol{\alpha}^{k+1}}-\left.\frac{\partial(\boldsymbol{\alpha}^{k+1}\odot
X^{k+1})}{\partial X^{k}}\right|_{\boldsymbol{\alpha}^{k+1}}}_{(Q)}$

By induction we have
$\left\lVert{\tilde{\boldsymbol{\alpha}}^{k+1}-\boldsymbol{\alpha}^{k+1}}\right\rVert_{2}\leq
I_{k+1}\cdot r$ and bounded gradients tells us
$\left\lVert{\frac{\partial\tilde{X}^{k+1}}{\partial\tilde{X}^{k}}}\right\rVert_{2}\leq
B$ giving us $\left\lVert{(P)}\right\rVert_{2}\leq I_{k+1}B\cdot r$. To
analyze the term $\left\lVert{(Q)}\right\rVert_{2}$, recall that we have
$X^{k+1}=f(X^{k};E^{k+1})$ and since the overall task loss is $H$ smooth, so
must be the function $f$. Abusing notation to let $H$ denote the Lipschitz
constant of the network gives us
$\left\lVert{\tilde{X}^{k}-X^{k}}\right\rVert_{2}\leq H\cdot r$. Then we have

$\displaystyle\frac{\partial(\tilde{X}^{k+1})}{\partial\tilde{X}^{k}}-\frac{\partial
X^{k+1}}{\partial X^{k}}$
$\displaystyle=f^{\prime}(\tilde{X}^{k};\tilde{E}^{k+1})-f^{\prime}(X^{k};E^{k+1})$
$\displaystyle=\underbrace{f^{\prime}(\tilde{X}^{k};\tilde{E}^{k+1})-f^{\prime}(X^{k};\tilde{E}^{k+1})}_{(M)}+\underbrace{f^{\prime}(X^{k};\tilde{E}^{k+1})-f^{\prime}(X^{k};E^{k+1})}_{(N)}$

Applying smoothness, we have $\left\lVert{(M)}\right\rVert_{2}\leq H^{2}\cdot
r$ as well as $\left\lVert{(N)}\right\rVert_{2}\leq H\cdot r$. Together with
bounded gradients that gives us
$\left\lVert{\boldsymbol{\alpha}^{k+1}}\right\rVert_{2}\leq B$, we have
$\left\lVert{(Q)}\right\rVert_{2}\leq BH(H+1)\cdot r$. Together, we have

$\left\lVert{\tilde{\boldsymbol{\alpha}}^{k}-\boldsymbol{\alpha}^{k}}\right\rVert_{2}\leq
B(H(H+1)+I_{k+1})\cdot r,$

telling us that $I_{k}\leq B(H(H+1)+I_{k+1})$.

The above tells us that in Algorithm 2, suppose the parameter update steps
i.e. step 7 and step 10 are executed by effecting $\tau$ mini-batch SGD steps
or else $\tau$ full-batch GD steps each time, with step length $\eta$, then
the amount of travel in any model parameter is bounded above by $\tau\eta B$
i.e. $\left\lVert{\tilde{E}^{k}-E^{k}}\right\rVert_{2}\leq\tau\eta B$ and so
on. Now, incomplete task gradients $\boldsymbol{\alpha}^{k}$ are updated only
after model parameters for all layers have been updated once and the algorithm
loops back to step 6. Thus, Lipschitzness of the gradients tells us that the
staleness in the incomplete task gradients, for any $k\in[K]$, is upper
bounded by

$\left\lVert{\tilde{\boldsymbol{\alpha}}^{k}-\boldsymbol{\alpha}^{k}}\right\rVert_{2}\leq\tau\eta\cdot
IB,$

where we take $I=\max_{k\leq K}I_{k}$ for sake of simplicity. Now, since
$\left\lVert{\frac{\partial X^{k}_{ip}}{\partial E^{k}}}\right\rVert_{2}\leq
B$ as gradients are bounded, we have $\sigma_{\max}(Z^{k})\leq N\cdot d_{k}B$.
Then, combining with the result in Equation (2) gives us

$\left\lVert{\frac{\widetilde{\partial{\mathcal{L}}}}{\partial
E^{k}}-\frac{\partial{\mathcal{L}}}{\partial
E^{k}}}\right\rVert_{2}\leq\tau\eta\cdot IB^{2}d_{k}$

Taking in contributions of gradients of all layers and the final classifier
layer gives us the bias in the total gradient using triangle inequality as

$\left\lVert{\widetilde{\nabla{\mathcal{L}}}-\nabla{\mathcal{L}}}\right\rVert_{2}\leq\sum_{k\in[K]}\left\lVert{\frac{\widetilde{\partial{\mathcal{L}}}}{\partial
E^{k}}-\frac{\partial{\mathcal{L}}}{\partial
E^{k}}}\right\rVert_{2}+\left\lVert{\frac{\widetilde{\partial{\mathcal{L}}}}{\partial
W^{K+1}}-\frac{\partial{\mathcal{L}}}{\partial
W^{K+1}}}\right\rVert_{2}\leq\tau\eta\cdot IB^{2}d_{\max}(K+1),$

where $d_{\max}=\max_{k\in K}\ d_{k}$ is the maximum embedding dimensionality
of any layer.

###  C.6 Step 4 (i): Convergence Guarantee (mini-batch SGD)

Let us analyze convergence in the case when updates are made using mini-batch
SGD in steps 7, 10 of Algorithm 2. The discussion above establishes an upper
bound on the _absolute_ bias in the gradients. However, our proofs later
require a _relative_ bound which we tackle now. Let us decide to set the step
length to $\eta=\frac{1}{C\sqrt{T}}$ for some constant $C>0$ that will be
decided later and also set some value $\phi<1$. Then two cases arise

  1. 1.

Case 1: The relative gradient bias is too large i.e. $\tau\eta\cdot
IB^{2}d_{\max}(K+1)>\phi\cdot\left\lVert{\nabla{\mathcal{L}}}\right\rVert_{2}$.
In this case we are actually done since we get

$\left\lVert{\nabla{\mathcal{L}}}\right\rVert_{2}\leq\frac{\tau\cdot
IB^{2}d_{\max}(K+1)}{\phi\cdot C\sqrt{T}},$

i.e. we are already at an approximate first-order stationary point.

  2. 2.

Case 2: The relative gradient bias is small i.e. $\tau\eta\cdot
IB^{2}d_{\max}(K+1)\leq\phi\cdot\left\lVert{\nabla{\mathcal{L}}}\right\rVert_{2}$.
In this case we satisfy the relative bias bound required by Lemma 5 (part 2)
with $\delta=\phi$.

This shows that either Case 1 happens in which case we are done or else Case 2
keeps applying which means that Lemma 5 (part 2) keeps getting its
prerequisites satisfied. If Case 1 does not happen for $T$ steps, then Lemma 5
(part 2) assures us that we will arrive at a point where

${\mathbb{E}}\left[{{\left\lVert{\nabla{\mathcal{L}}}\right\rVert_{2}^{2}}}\right]\leq\frac{2C({\mathcal{L}}^{0}-{\mathcal{L}}^{\ast})+H\sigma^{2}/C}{(1-\phi)\sqrt{T}}$

where ${\mathcal{L}}^{0},{\mathcal{L}}^{\ast}$ are respectively the initial
and optimal values of the loss function which we recall is $H$-smooth and
$\sigma^{2}$ is the variance due to mini-batch creation and we set
$\eta=\frac{1}{C\sqrt{T}}$. Setting
$C=\sqrt{\frac{H\sigma^{2}}{2({\mathcal{L}}^{0}-{\mathcal{L}}^{\ast})}}$ tells
us that within $T$ steps, either we will achieve

$\left\lVert{\nabla{\mathcal{L}}}\right\rVert_{2}^{2}\leq\frac{2\tau^{2}\cdot
I^{2}B^{4}d_{\max}^{2}(K+1)^{2}({\mathcal{L}}^{0}-{\mathcal{L}}^{\ast})}{\phi^{2}H\sigma^{2}T},$

or else we will achieve

${\mathbb{E}}\left[{{\left\lVert{\nabla{\mathcal{L}}}\right\rVert_{2}^{2}}}\right]\leq\frac{2\sigma\sqrt{2({\mathcal{L}}^{0}-{\mathcal{L}}^{\ast})H}}{(1-\phi)\sqrt{T}}$

Setting
$\tau=T^{\frac{1}{4}}\cdot\left({\frac{\sqrt{\sigma^{3}H\sqrt{H}}}{({\mathcal{L}}^{0}-{\mathcal{L}}^{\ast})^{\frac{1}{4}}IB^{2}d_{\max}(K+1)}}\right)$
balances the two quantities in terms of their dependence on $T$ (module
absolute constants such as $\phi$). Note that as expected, as the quantities
$I,B,d_{\max},K$ increase, the above limit on $\tau$ goes down i.e. we are
able to perform fewer and fewer updates to the model parameters before a
refresh is required. This concludes the proof of Theorem 4 for the second
case.

###  C.7 Step 4 (ii): Convergence Guarantee (full-batch GD)

In this case we similarly have either the relative gradient bias to be too
large in which case we get

$\left\lVert{\nabla{\mathcal{L}}}\right\rVert_{2}\leq\frac{\tau\eta\cdot
IB^{2}d_{\max}(K+1)}{\phi},$

or else we satisfy the relative bias bound required by Lemma 5 (part 1) with
$\delta=\phi$. This shows that either Case 1 happens in which case we are done
or else Case 2 keeps applying which means that Lemma 5 (part 1) keeps getting
its prerequisites satisfied. If Case 1 does not happen for $T$ steps, then
Lemma 5 (part 1) assures us that we will arrive at a point where

$\left\lVert{\nabla{\mathcal{L}}}\right\rVert_{2}^{2}\leq\frac{2({\mathcal{L}}^{0}-{\mathcal{L}}^{\ast})}{\eta(1-\phi)T}$

In this case, for a given value of $\tau$, setting
$\eta=\left({\frac{2({\mathcal{L}}^{0}-{\mathcal{L}}^{\ast})}{(1-\phi)\tau^{2}I^{2}B^{4}d_{\max}^{2}(K+1)^{2}T}}\right)^{\frac{1}{3}}$
gives us that within $T$ iterations, we must achieve

$\left\lVert{\nabla{\mathcal{L}}}\right\rVert_{2}^{2}\leq\left({\frac{2\tau({\mathcal{L}}^{0}-{\mathcal{L}}^{\ast})IB^{2}d_{\max}(K+1)}{(1-\phi)}}\right)^{\frac{2}{3}}\cdot\frac{1}{T^{\frac{2}{3}}}$

In this case, it is prudent to set $\tau={\cal O}\left({{1}}\right)$ so as to
not deteriorate the convergence rate. This concludes the proof of Theorem 4
for the first case.

###  C.8 Generic Convergence Results

######  Lemma 5 (First-order Stationarity with a Smooth Objective).

Let $f:\boldsymbol{\Theta}\rightarrow{\mathbb{R}}$ be an $H$-smooth objective
over model parameters $\theta\in\boldsymbol{\Theta}$ that is being optimized
using a gradient oracle and the following update for step length $\eta$:

$\boldsymbol{\theta}^{t+1}=\boldsymbol{\theta}^{t}-\eta\cdot{{\mathbf{g}}}^{t}$

Let $\boldsymbol{\theta}^{\ast}$ be an optimal point i.e.
$\boldsymbol{\theta}^{\ast}\in\arg\min_{\boldsymbol{\theta}\in\boldsymbol{\Theta}}\
f(\boldsymbol{\theta})$. Then, the following results hold depending on the
nature of the gradient oracle:

  1. 1.

If a non-stochastic gradient oracle with bounded bias is used i.e. for some
$\delta\in(0,1)$, for all $t$, we have ${{\mathbf{g}}}^{t}=\nabla
f(\boldsymbol{\theta}^{t})+\boldsymbol{\Delta}^{t}$ where
$\left\lVert{\boldsymbol{\Delta}^{t}}\right\rVert_{2}\leq\delta\cdot\left\lVert{\nabla
f(\boldsymbol{\theta}^{t})}\right\rVert_{2}$ and if the step length satisfies
$\eta\leq\frac{(1-\delta)}{2H(1+\delta^{2})}$, then for any $T>0$, for some
$t\leq T$ we must have

$\left\lVert{\nabla
f(\boldsymbol{\theta}^{t})}\right\rVert_{2}^{2}\leq\frac{2(f(\boldsymbol{\theta}^{0})-f(\boldsymbol{\theta}^{\ast}))}{\eta(1-\delta)T}$

  2. 2.

If a stochastic gradient oracle is used with bounded bias i.e. for some
$\delta\in(0,1)$, for all $t$, we have
${\mathbb{E}}\left[{{\,|\,{{{\mathbf{g}}}^{t}}\boldsymbol{\theta}^{t}}}\right]=\nabla
f(\boldsymbol{\theta}^{t})+\boldsymbol{\Delta}^{t}$ where
$\left\lVert{\boldsymbol{\Delta}^{t}}\right\rVert_{2}\leq\delta\cdot\left\lVert{\nabla
f(\boldsymbol{\theta}^{t})}\right\rVert_{2}$, as well as bounded variance i.e.
for all $t$, we have
${\mathbb{E}}\left[{{\,|\,{\left\lVert{{{\mathbf{g}}}^{t}-\nabla
f(\boldsymbol{\theta}^{t})-\boldsymbol{\Delta}^{t}}\right\rVert_{2}^{2}}\boldsymbol{\theta}^{t}}}\right]\leq\sigma^{2}$
and if the step length satisfies
$\eta\leq\frac{(1-\delta)}{2H(1+\delta^{2})}$, as well as
$\eta=\frac{1}{C\sqrt{T}}$ for some $C>0$, then for any
$T>\frac{4H^{2}(1+\delta^{2})^{2}}{C^{2}(1-\delta)^{2}}$, for some $t\leq T$
we must have

${\mathbb{E}}\left[{{\left\lVert{\nabla
f(\boldsymbol{\theta}^{t})}\right\rVert_{2}^{2}}}\right]\leq\frac{2C(f(\boldsymbol{\theta}^{0})-f(\boldsymbol{\theta}^{\ast}))+H\sigma^{2}/C}{(1-\delta)\sqrt{T}}$

###### Proof (of Lemma 5).

To prove the first part, we notice that smoothness of the objective gives us

$f(\boldsymbol{\theta}^{t+1})\leq
f(\boldsymbol{\theta}^{t})+\left\langle{\nabla
f(\boldsymbol{\theta}^{t})},{\boldsymbol{\theta}^{t+1}-\boldsymbol{\theta}^{t}}\right\rangle+\frac{H}{2}\left\lVert{\boldsymbol{\theta}^{t+1}-\boldsymbol{\theta}^{t}}\right\rVert_{2}^{2}$

Since we used the update
$\boldsymbol{\theta}^{t+1}=\boldsymbol{\theta}^{t}-\eta\cdot{{\mathbf{g}}}^{t}$
and we have ${{\mathbf{g}}}^{t}=\nabla
f(\boldsymbol{\theta}^{t})+\boldsymbol{\Delta}^{t}$, the above gives us

$\displaystyle f(\boldsymbol{\theta}^{t+1})$ $\displaystyle\leq
f(\boldsymbol{\theta}^{t})-\eta\cdot\left\langle{\nabla
f(\boldsymbol{\theta}^{t})},{{{\mathbf{g}}}^{t}}\right\rangle+\frac{H\eta^{2}}{2}\left\lVert{{{\mathbf{g}}}^{t}}\right\rVert_{2}^{2}$
$\displaystyle=f(\boldsymbol{\theta}^{t})-\eta\cdot\left\langle{\nabla
f(\boldsymbol{\theta}^{t})},{\nabla
f(\boldsymbol{\theta}^{t})+\boldsymbol{\Delta}^{t}}\right\rangle+\frac{H\eta^{2}}{2}\left({\left\lVert{\nabla
f(\boldsymbol{\theta}^{t})+\boldsymbol{\Delta}^{t}}\right\rVert_{2}^{2}}\right)$
$\displaystyle=f(\boldsymbol{\theta}^{t})-\eta\cdot\left\lVert{\nabla
f(\boldsymbol{\theta}^{t})}\right\rVert_{2}^{2}-\eta\cdot\left\langle{\nabla
f(\boldsymbol{\theta}^{t})},{\boldsymbol{\Delta}^{t}}\right\rangle+\frac{H\eta^{2}}{2}\left({\left\lVert{\nabla
f(\boldsymbol{\theta}^{t})+\boldsymbol{\Delta}^{t}}\right\rVert_{2}^{2}}\right)$

Now, the Cauchy-Schwartz inequality along with the bound on the bias gives us
$-\eta\cdot\left\langle{\nabla
f(\boldsymbol{\theta}^{t})},{\boldsymbol{\Delta}^{t}}\right\rangle\leq\eta\delta\cdot\left\lVert{\nabla
f(\boldsymbol{\theta}^{t})}\right\rVert_{2}^{2}$ as well as
$\left\lVert{\nabla
f(\boldsymbol{\theta}^{t})+\boldsymbol{\Delta}^{t}}\right\rVert_{2}^{2}\leq
2(1+\delta^{2})\cdot\left\lVert{\nabla
f(\boldsymbol{\theta}^{t})}\right\rVert_{2}^{2}$. Using these gives us

$\displaystyle f(\boldsymbol{\theta}^{t+1})$ $\displaystyle\leq
f(\boldsymbol{\theta}^{t})-\eta(1-\delta-\eta
H(1+\delta^{2}))\cdot\left\lVert{\nabla
f(\boldsymbol{\theta}^{t})}\right\rVert_{2}^{2}$ $\displaystyle\leq
f(\boldsymbol{\theta}^{t})-\frac{\eta(1-\delta)}{2}\cdot\left\lVert{\nabla
f(\boldsymbol{\theta}^{t})}\right\rVert_{2}^{2},$

since we chose $\eta\leq\frac{(1-\delta)}{2H(1+\delta^{2})}$. Reorganizing,
taking a telescopic sum over all $t$, using $f(\boldsymbol{\theta}^{T+1})\geq
f(\boldsymbol{\theta}^{\ast})$ and making an averaging argument tells us that
since we set , for any $T>0$, it must be the case that for some $t\leq T$, we
have

$\left\lVert{\nabla
f(\boldsymbol{\theta}^{t})}\right\rVert_{2}^{2}\leq\frac{2(f(\boldsymbol{\theta}^{0})-f(\boldsymbol{\theta}^{\ast}))}{\eta(1-\delta)T}$

This proves the first part. For the second part, we yet again invoke
smoothness to get

$f(\boldsymbol{\theta}^{t+1})\leq
f(\boldsymbol{\theta}^{t})+\left\langle{\nabla
f(\boldsymbol{\theta}^{t})},{\boldsymbol{\theta}^{t+1}-\boldsymbol{\theta}^{t}}\right\rangle+\frac{H}{2}\left\lVert{\boldsymbol{\theta}^{t+1}-\boldsymbol{\theta}^{t}}\right\rVert_{2}^{2}$

Since we used the update
$\boldsymbol{\theta}^{t+1}=\boldsymbol{\theta}^{t}-\eta\cdot{{\mathbf{g}}}^{t}$,
the above gives us

$\displaystyle f(\boldsymbol{\theta}^{t+1})$ $\displaystyle\leq
f(\boldsymbol{\theta}^{t})-\eta\cdot\left\langle{\nabla
f(\boldsymbol{\theta}^{t})},{{{\mathbf{g}}}^{t}}\right\rangle+\frac{H\eta^{2}}{2}\left\lVert{{{\mathbf{g}}}^{t}}\right\rVert_{2}^{2}$
$\displaystyle=f(\boldsymbol{\theta}^{t})-\eta\cdot\left\langle{\nabla
f(\boldsymbol{\theta}^{t})},{{{\mathbf{g}}}^{t}}\right\rangle+\frac{H\eta^{2}}{2}\left({\left\lVert{\nabla
f(\boldsymbol{\theta}^{t})+\boldsymbol{\Delta}^{t}}\right\rVert_{2}^{2}+\left\lVert{{{\mathbf{g}}}^{t}-\nabla
f(\boldsymbol{\theta}^{t})-\boldsymbol{\Delta}^{t}}\right\rVert_{2}^{2}}\right)$
$\displaystyle\quad-H\eta^{2}\left\langle{\nabla
f(\boldsymbol{\theta}^{t})+\boldsymbol{\Delta}^{t}},{{{\mathbf{g}}}^{t}-\nabla
f(\boldsymbol{\theta}^{t})-\boldsymbol{\Delta}^{t}}\right\rangle$

Taking conditional expectations on both sides gives us

${\mathbb{E}}\left[{{\,|\,{f(\boldsymbol{\theta}^{t+1})}\boldsymbol{\theta}^{t}}}\right]\leq
f(\boldsymbol{\theta}^{t})-\eta\cdot\left\lVert{\nabla
f(\boldsymbol{\theta}^{t})}\right\rVert_{2}^{2}-\eta\cdot\left\langle{\nabla
f(\boldsymbol{\theta}^{t})},{\boldsymbol{\Delta}^{t}}\right\rangle+\frac{H\eta^{2}}{2}\left({\left\lVert{\nabla
f(\boldsymbol{\theta}^{t})+\boldsymbol{\Delta}^{t}}\right\rVert_{2}^{2}+\sigma^{2}}\right)$

Now, the Cauchy-Schwartz inequality along with the bound on the bias gives us
$-\eta\cdot\left\langle{\nabla
f(\boldsymbol{\theta}^{t})},{\boldsymbol{\Delta}^{t}}\right\rangle\leq\eta\delta\cdot\left\lVert{\nabla
f(\boldsymbol{\theta}^{t})}\right\rVert_{2}^{2}$ as well as
$\left\lVert{\nabla
f(\boldsymbol{\theta}^{t})+\boldsymbol{\Delta}^{t}}\right\rVert_{2}^{2}\leq
2(1+\delta^{2})\cdot\left\lVert{\nabla
f(\boldsymbol{\theta}^{t})}\right\rVert_{2}^{2}$. Using these and applying a
total expectation gives us

$\displaystyle{\mathbb{E}}\left[{{f(\boldsymbol{\theta}^{t+1})}}\right]$
$\displaystyle\leq{\mathbb{E}}\left[{{f(\boldsymbol{\theta}^{t})}}\right]-\eta(1-\delta-\eta
H(1+\delta^{2}))\cdot{\mathbb{E}}\left[{{\left\lVert{\nabla
f(\boldsymbol{\theta}^{t})}\right\rVert_{2}^{2}}}\right]+\frac{H\eta^{2}}{2}\cdot\sigma^{2}$
$\displaystyle\leq{\mathbb{E}}\left[{{f(\boldsymbol{\theta}^{t})}}\right]-\frac{\eta(1-\delta)}{2}\cdot{\mathbb{E}}\left[{{\left\lVert{\nabla
f(\boldsymbol{\theta}^{t})}\right\rVert_{2}^{2}}}\right]+\frac{H\eta^{2}}{2}\cdot\sigma^{2}$

where the second step follows since we set
$\eta\leq\frac{(1-\delta)}{2H(1+\delta^{2})}$. Reorganizing, taking a
telescopic sum over all $t$, using $f(\boldsymbol{\theta}^{T+1})\geq
f(\boldsymbol{\theta}^{\ast})$ and making an averaging argument tells us that
for any $T>0$, it must be the case that for some $t\leq T$, we have

${\mathbb{E}}\left[{{\left\lVert{\nabla
f(\boldsymbol{\theta}^{t})}\right\rVert_{2}^{2}}}\right]\leq\frac{2(f(\boldsymbol{\theta}^{0})-f(\boldsymbol{\theta}^{\ast}))}{\eta(1-\delta)T}+\frac{H\eta\sigma^{2}}{1-\delta}$

However, since we also took care to set $\eta=\frac{1}{C\sqrt{T}}$, we get

${\mathbb{E}}\left[{{\left\lVert{\nabla
f(\boldsymbol{\theta}^{t})}\right\rVert_{2}^{2}}}\right]\leq\frac{2C(f(\boldsymbol{\theta}^{0})-f(\boldsymbol{\theta}^{\ast}))+H\sigma^{2}/C}{(1-\delta)\sqrt{T}}$

which proves the second part and finishes the proof. ∎