Minimal generation of transitive permutation groups
Gareth M. Tracey∗
Mathematics Institute, University of Warwick,

arXiv:1504.07506v3 [math.GR] 30 Jan 2018

Coventry CV4 7AL, United Kingdom
October 30, 2017

Abstract
This paper discusses upper bounds on the minimal number of elements d(G) required to generate
a transitive permutation group G, in terms of its degree n, and its order |G|. In particular, we
reduce a conjecture of L. Pyber on the number of subgroups of the symmetric group Sym(n). We
also prove that our bounds are best possible.

1

Introduction

A well-developed branch of finite group theory studies properties of certain classes of permutation
groups as functions of their degree. The purpose of this paper is to study the minimal generation of
transitive permutation groups.
For a group G, let d(G) denote the minimal number of elements required to generate G. In [21],
√
[7], [26] and [28], it is shown that d(G) = O(n/ log n) whenever G is a transitive permutation group
of degree n ≥ 2 (here, and throughout this paper, “ log ” means log to the base 2). A beautifully

constructed family of examples due to L. Kovács and M. Newman shows that this bound is ‘asymptotically best possible’ (see Example 6.10), thereby ending the hope that a bound of d(G) = O(log n)
could be proved.
The constants involved in these theorems, however, were never estimated. We prove:
Theorem 1.1. Let G be a transitive permutation group of degree n ≥ 2. Then
j
k
p
cn
(1) d(G) ≤ √log
,where c := 1512660 log (219 15)/(219 15) = 0.920581 . . ., and;
n
(2) d(G) ≤

j

√c1 n
log n

k

, where c1 :=

√

3/2 = 0.866025 . . ., unless each of the following conditions hold:

(i) n = 2k v, where v = 5 and 17 ≤ k ≤ 26, or v = 15 and 15 ≤ k ≤ 35, and;
(ii) G contains no soluble transitive subgroups.
In fact, we prove a slightly stronger version of Theorem 1.1, which is given as Theorem 5.3. The
following corollary is immediate.
∗

Electronic address: G.M.Tracey@warwick.ac.uk

1

Corollary 1.2. Let G be a transitive permutation group of degree n, containing a soluble transitive
subgroup. Then

where c1 =


c1 n
,
d(G) ≤ √
log n


√
3/2.

As shown in [21], apart from the choice of constants, the bounds in our results are of the right
√
order. Moreover, the infimum of the set of constants c satisfying d(G) ≤ cn/ log n, for all soluble

transitive permutation groups G of degree n ≥ 2, is the constant c1 in Theorem 6.2, since d(G) = 4
when n = 8 and G ∼
= D8 ◦ D8 . We conjecture that the best ‘asymptotic’ bound, that is, the best

possible upper bound when one is permitted to exclude finitely many cases, is

e
cn
,
d(G) ≤ √
log n


where e
c is some constant satisfying
(see Example 6.10 for more details).

b/2 ≤ e
c < b :=

p

2/π

√
The constant b, and the function n/ log n, enter our work by means of the following combinatorial

result. For a partially ordered set P , w(P ) denotes the width of P , that is w(P ) denotes the size of
the largest antichain in P .
Theorem 1.3. Suppose that a partially ordered set P , of cardinality s ≥ 2, is a cartesian product of
P
the chains P1 , P2 , . . ., Pt , where each Pi has cardinality ki . Let K := ti=1 ki . Then




 
 
s
K
bs
bs
w(P ) ≤ K
,
≤ √
≤ √
2
⌊K/2⌋
log s
K

where b =

p

p
2/π. Furthermore, if each chain has the same cardinality p, then w(P ) ≤ ⌊bpt / t(p − 1)⌋.

We remark that an asymptotic version of this bound is proved in [7, Theorem 1.4].
To state the key application of Theorem 1.3, we require two definitions.

Definition 1.4. For a positive integer s with prime factorisation s = pr11 pr22 . . . prt t , set
P
P
P
ω(s) :=
ri , ω1 (s) := ri pi , K(s) := ω1 (s) − ω(s) =
ri (pi − 1) and
ω
e (s) =

s

2K(s)




K(s)
k .
j
K(s)
2

For a prime p, write sp for the p-part of s.
Definition 1.5. Let s be a positive integer, and let p be prime. We define sp to be the p-part of s,
lpp (s) = max{sq : q prime}, and








bs
s
,
E(s, p) := min  q
and Esol (s, p) := min {e
ω (s), sp }

lpp (s/sp ) 
(p − 1) log p sp

j q
k
where we take bs/ (p − 1) logp sp to be ∞ if sp = 1.
2

The mentioned application can now be given as follows.
Theorem 1.6. Let G be a finite group, let F be a field of characteristic p > 0, let H be a subgroup
of G, and let V be an F[H]-module, of dimension a. Let S be the group induced by G on the set of
(right) cosets of H. Define E ′ to be Esol if S contains a soluble transitive subgroup, and E ′ := E
′
otherwise. Let M be a submodule of the induced module V ↑G
H . Then dG (M ) ≤ aE (s, p).

Here, dG (M ) denotes the minimal number of elements required to generate M as a G-module. We
actually prove slightly stronger results than Theorem 1.6 - see Theorem 4.13 and Theorem 4.24.
Our next main result is motivated by a conjecture of L. Pyber, which states that: The number
1

2

of subgroups | Sub(Sym(n))| of Sym(n) is precisely 2( 16 +o(1))n [35]. For m ∈ N, let Subm (Sym(n))

denote the set of subgroups H of Sym(n) with the property that all H-orbits are of length at most
m. J.C. Schlage-Puchta (private correspondence) has proven that if the quantity
f (n) := max{d(G) log |G|/n2 : G ≤ Sym(n) transitive}
approaches 0 as n tends to ∞, then there exists an absolute constant c such that the number of
2

subgroups of Sym(n) is at most 2o(n ) Subc (Sym(n)). This reduces Pyber’s conjecture to counting the
number of subgroups that have all orbit lengths bounded above by c.
Motivated by this, we prove the following.
Theorem 1.7. There exists an absolute constant C such that


Cn2
√
d(G) ≤
log |G| log n



whenever G is a transitive permutation group of degree n ≥ 2.
In particular, the discussed reduction of Pyber’s conjecture follows. We remark that the bound in
Theorem 1.7 is ‘asymptotically best possible’. See Example 6.10 for more details.
Finally, we also discuss minimally transitive permutation groups. A transitive permutation group
G is said to be minimally transitive if every proper subgroup of G is intransitive. Since every transitive
group contains a minimally transitive subgroup, these groups arise naturally in reduction arguments.
Minimally transitive groups also have applications in Combinatorics (for counting vertex transitive
graphs; for example, see [3]), and in the theory of BFC-groups (see [31] and [37]). In this paper, we
use them to study minimal generator numbers in modules for permutation groups. Thus, some
information on their structure is desirable. Our main result is as follows.
Theorem 1.8. Let G be a minimally transitive permutation group of degree n = 2m 3. Then one of
the following holds:
(i) G is soluble, or:
(ii) G has a unique nonabelian chief factor, which is a direct product of copies of L2 (p), where p is
a Mersenne prime.
A minimally transitive group of prime power degree is a p-group (see Lemma 3.1), so is in particular
soluble; the motivation behind Theorem 1.8 is to study how far away from being soluble a minimally
3

transitive group of degree n := 2m 3 is. It would be interesting to study the same question for
minimally transitive groups of degree n := pm q, for arbitrary primes p and q. For an analysis of the
case n = pq, for distinct primes p and q, see [40], [23] and [13].
For information about minimal generator numbers in minimally transitive groups, see [38].
The layout of the paper is as follows: In Section 2, we discuss preliminary results in Permutation
Group Theory and Representation Theory. In Section 3 we discuss minimally transitive groups and
prove Theorem 1.8. Section 4 is the critical step of the paper: there, we prove upper bounds on the
minimal number of elements dG (M ) required to generate a submodule M of an induced module V ↑G
H

for a finite group G, and a subgroup H ≤ G. These bounds are derived in terms of dim V , |G : H|,

and some additional data when either the field involved is finite, or when G is insoluble. In particular,
we prove Theorem 1.6. We also prove Theorem 1.3 in Section 4. In Section 5, we prove a stronger
version of Theorem 5.3, while in Section 6 we prove Theorem 1.7.
Our proofs are theoretical, although we do use MAGMA [5] for computations of generator numbers
and composition factors for some groups of small order. In particular, we compute the maximum values
of d(G) as G runs over the transitive groups of degree n, for 2 ≤ n ≤ 32.

Notation: The following is a table of constants which will be used throughout the paper.
p
b
2/π = 0.797885 . . .
√
b1
2b = 1.12838 . . .
√
c1
3/2 = 0.866025 . . .
p
c 1512660 log (219 15)/(219 15) = 0.920581 . . .
c0

log9 48 + (1/3) log 9 24 = 2.24399 . . .

c′

ln 2/1.25506 = 0.552282 . . .

We will adopt the ATLAS [11] notation for group names, although we will usually write Sym(n) and
Alt(n) for the symmetric and alternating groups of degree n. Furthermore, these groups, and their
subgroups, act naturally on the set {1, . . . , n}; we will make no further mention of this.

The centre of a group G will be written as Z(G), the Frattini subgroup as Φ(G), and the Fitting

subgroup as F (G). The letters G, H, K and L will usually be used for groups, while U , V and W will
usually be modules. The letter M will usually denote a submodule. Finally, group homomorphisms
will be written on the right.
We finish by recording a definition which will be used throughout the paper.
Definition 1.9. Let G be a group.
(a) Write a(G) to denote the composition length of G.
(b) Let aab (G) and anonab (G) denote the number of abelian and non-abelian composition factors of
G, respectively.
(c) Let cnonab (G) denote the number of non-abelian chief factors of G.
The author is hugely indebted to his supervisor Professor Derek Holt for many useful discussions
and suggestions; without them, this paper would not be possible. He would also like to thank both
Dr. Tim Burness and the referee for many useful comments and suggestions. Finally, he would also
like to thank the Engineering and Physical Sciences Research Council for their financial support.
4

2

Preliminaries

2.1

Permutation groups

We begin with some notation. Suppose that G is a group acting on a set Ω, via the homomorphism
θ : G → Sym(Ω). When there is no ambiguity, we will abbreviate ω gθ to ω g , for g ∈ G, ω ∈ Ω. We

will also write

GΩ := Gθ, and KerG (Ω) := Ker(θ)
to denote the image and kernel of θ, respectively. The orbit ω Gθ of ω ∈ Ω under the action of G will

be abbreviated to ω G , while the stabiliser will be written as StabG (ω). If Ω is finite of cardinality n,
we have
(Sym(Ω), Ω) ∼
= (Sym(n), {1, . . . , n}).
Thus, in this case, we will usually write Sym (Ω) = Sym (n) = Sn , and say that a subgroup G ≤
Sym(Ω) is a permutation group of degree n. If, for 1 = 1, 2, Gi is a group acting on the set Ωi , we
∼ (G, Ω2 ) if (G1 , Ω1 ) ∼
will write (G1 , Ω1 ) =
= (G, Ω2 ) are permutation isomorphic.

Let ωiG , i ∈ I, denote the orbits in Ω under the action of G (the set I is an index set). The groups

ωiG

G

are called the transitive constituents of G on Ω.

Definition 2.1. Let Gi , i ∈ I, be a set of groups. A subgroup G of the direct product

Q

a subdirect product of the Gi if πi |G : G → Gi is surjective for each projection map πi :
We note the following easily proved proposition, which will be used frequently.

i

Q

Gi is called
i

Gi → Gi .

Proposition 2.2 ([8], Theorem 1.1). Let the group G act on the finite set Ω. Then GΩ is isomorphic
to a subdirect product of its transitive constituents.

2.2

Wreath products

Let R be a finite group, let S be a permutation group of degree s, and consider the wreath product
R ≀ S, as constructed in [8]. Let B be the base group of R ≀ S, so that B is isomorphic to the direct

product of s copies of R. Thus, for a subgroup L of R, B contains the direct product of s copies of
L: we will denote this direct product by BL (so that B1 = 1 and BR = B).
Now, for each 1 ≤ i ≤ s, set
R(i) := {(g1 , . . . , gs ) ∈ B : gj = 1 for all j 6= i} E B.

Q
Then R(i) ∼
= R(i) × (R ≀ StabS (i)). Hence, we
= R, and B = 1≤i≤s R(i) . Furthermore, NR≀S (R(i) ) ∼

may define the projection maps

ρi : NR≀S (R(γ) ) → R(i) .

(2.1)

We also define π : R ≀ S → S to be the quotient map by B. This allows us to define a special class of

subgroups of R ≀ S.

Definition 2.3. A subgroup G of R ≀ S is called large if
5

(a) Gρi = R(i) for all i in 1 ≤ i ≤ s, and;
(b) Gπ = S.
Remark 2.4. Suppose, in addition, that R is a permutation group of degree r > 1. If s > 1 and G is
a large subgroup of R≀S, then G is a transitive, and imprimitive, permutation group of degree rs, with
a system of s blocks, each of cardinality r. (G acts on the cartesian product {1, . . . , r} × {1, . . . , s} in

this case.

In fact, it turns out that all imprimitive permutation groups arise as a large subgroup of a certain
wreath product.
Theorem 2.5 ([39], Theorem 3.3). Let G be an imprimitive permutation group on a set Ω1 , and
let ∆ be a block for G. Also, let Γ := ∆G be the set of G-translates of ∆, and set Ω2 := ∆ × Γ. Denote
G

by R and S the permutation groups StabG (∆)∆ , and G∆ , on ∆ and Γ respectively. Then
(i) G ∼
= GΩ2 is isomorphic to a large subgroup of R ≀ S, and;
(ii) (G, Ω1 ) and (G, Ω2 ) are permutation isomorphic.

If G is an imprimitive permutation group, and the block ∆ as in Theorem 2.5 is assumed to be
a minimal block for G, then the group R = StabG (∆)∆ is primitive. When Ω is finite we can iterate
this process, and deduce the following.
Corollary 2.6. Let G be a transitive permutation group on a finite set Ω. Then there exist primitive
permutation groups R1 , R2 , . . ., Rt such that G is a subgroup of R1 ≀ R2 ≀ . . . ≀ Rt .
Remark 2.7. The wreath product construction is associative, in the sense that R≀(S ≀T ) ∼
= (R≀S)≀T ,
so the iterated wreath product in Corollary 2.6 is well-defined.

Definition 2.8. The tuple (R1 , R2 , . . . , Rt ), where the Ri are as in Corollary 2.6, is called a tuple of
primitive components for G on Ω.
We caution the reader that a tuple of primitive components for an imprimitive permutation group
G on a set Ω is not necessarily unique - see [8, Page 13] for an example.
We close this subsection with an easy lemma concerning the alternating group Alt(d).
Lemma 2.9. Let D ∼
= Alt(d) be the alternating group of degree d ≥ 5, and let p be prime. Then D

contains a soluble subgroup E with at most two orbits, such that each orbit has p′ -length.

Proof. Assume first that p = 2. Then since n is either odd, or a sum of two odd numbers, we can
take E := hx1 x2 i, where x1 is a cycle of odd length, either x2 = 1 or x2 is a cycle of odd length, and

d is the sum of the orders (i.e. lengths) of x1 and x2 .

So assume that p > 2, and write d = tp + k, where 0 ≤ k ≤ p − 1. If k 6= p − 1, then take E1

to be a soluble transitive subgroup of Alt(tp − 1), and take E2 to be a soluble transitive subgroup of

Alt(k + 1). If k = p − 1, then take E1 to be a soluble transitive subgroup of Alt(tp + 1), and take E2

to be a soluble transitive subgroup of Alt(k − 1) (note that k − 1 > 0 since p > 2). Finally, taking

E := E1 × E2 ≤ D give us what we need, and proves the claim.
6

2.3

Asymptotic results for permutation groups

We will frequently use a result on composition length, due to Pyber. First, define the constant
c0 := log9 48 + (1/3) log 9 24 = 2.24399 . . .

(2.2)

The result of Pyber can now be given as follows. It is stated slightly different to how it is stated
in [34].
Theorem 2.10 ([34], Theorem 2.10). Let R be a primitive permutation group of degree r ≥ 2.

Then aab (R) ≤ (1 + c0 ) log r − (1/3) log 24, and anonab (R) ≤ log r.

We shall also require the following theorem of D. Holt and C. Roney-Dougal on generator numbers
in primitive groups.
Theorem 2.11 ([19], Theorem 1.1). Let H be a subnormal subgroup of a primitive permutation
∼ Sym(3).
group of degree r. Then d(H) ≤ ⌊log r⌋, except that d(H) = 2 when m = 3 and H =
We deduce the following easy consequence.
Corollary 2.12. Let G be an imprimitive permutation group of degree n, and suppose that G has a
minimal block ∆ of cardinality r ≥ 4. Let S denote the induced action of G on the set of distinct
G-translates of ∆. Then d(G) ≤ s⌊log r⌋ + d(S), where s := n/r.

Proof. Let R be the induced action of the block stabiliser StabG (∆) on ∆, and let K := KerG (Ω) be
the kernel of the action of G on the set Ω of distinct G-translates of ∆. Then K ∆ E R, and hence, by
Theorem 2.11, each normal subgroup of K ∆ can be generated by ⌊log r⌋ elements.
Since K E G, we have

(K, ∆) ∼
= (K, ∆g )

(2.3)

for all g ∈ G. Also, since R is primitive, K ∆ E R is either trivial or transitive. If K ∆ is trivial, then

K is trivial by 2.3, and hence d(G) = d(G/K) = d(S). So assume that K ∆ is transitive. Then K is

an iterated subdirect product of s copies of K ∆ , by Proposition 2.2. Hence, d(K) ≤ s⌊log r⌋ by the
previous paragraph. Since G/K ∼
= S, the claim follows.

2.4

Some results from Representation Theory

We now record two lemmas which will be key in the proof of Proposition 4.9. The first has a stronger
version which is stated in [19, Lemma 2.13], but we only require the following.
Lemma 2.13 ([19], Lemma 2.13). Let G ≤ GLn (F) be finite, let V = Fn be the natural module,

and assume that G acts irreducibly on V . Suppose that

1. V ↓L is homogeneous for each normal subgroup L of G; and
2. G has no non-trivial abelian quotients.

7

Then G is isomorphic to a subgroup of GLn/f (K) for some divisor f of n, and some extension field K
of F of degree f . Furthermore, if W denotes the natural module for GLn/f (K), then G acts irreducibly
on W and
(i) W ↓L is homogeneous for each normal subgroup L of G;
(ii) Z(G) is cyclic; and
(iii) Each abelian characteristic subgroup of G is contained in Z(GLn/f (K)).
Lemma 2.14. Let G ≤ GLn (F) be finite, let V be the natural module, and assume that V is irreducible.

Suppose that 1 6= E E L E G, and that V ↓L is homogeneous. Suppose that K ⊇ F is a splitting field

for all subgroups of L, and assume that the resulting extension K/F is normal. Then V K ↓E is a
non-trivial completely reducible K[E]-module.

Proof. Since L is homogeneous, V ↓L ∼
= eU , for some irreducible F[L]-module U and some positive
integer e. Since G is faithful on V and L 6= 1, L is faithful on U . Moreover, U K is completely

reducible, and each of its irreducible constituents are algebraically conjugate, by [12, Theorem 70.15].
It follows that L is faithful on V K ↓L , and hence V K ↓E is non-trivial. Also, since E E L, and
V K ↓E ∼
= V K ↓L ↓E ,

it follows from Clifford’s Theorem (see [12, Theorem 49.7]) that V K ↓E is completely reducible. This

completes the proof.

Remark 2.15. Let K be a splitting field for the finite group G, containing the field F. Then every
field E containing K is also a splitting field for G (for example, see [20, Corollary 9.8]). Thus, one can
always find a splitting field E for G such that E/F is a normal extension (for instance, by taking E to
be the normal closure of K/F).

2.5

Number Theory: The prime counting function

We close this section with a brief discussion of large prime power divisors of positive integers.
Definition 2.16. For a positive integer s and a prime p, write sp for the p-part of n. Also, define
lpp s = maxp prime sp to be the the largest prime power divisor of s.
Fix s ≥ 2, and let k = lpp s. By writing the prime factorization of s as s = kpr22 . . . prt t , one

immediately sees that s ≤ kδ(k) , where δ(k) denotes the number of primes less than or equal to k.
Hence, log s ≤ δ(k) log k. Also, it is proved in [36, Corollary 1] that
δ(k) < 1.25506k/ ln k
for k ≥ 2. Define the constant c′ by
c′ := ln 2/1.25506
We deduce the following.
8

(2.4)

Lemma 2.17. Let s be a positive integer. Then
lpp s ≥ (ln 2/1.25506) log s = c′ log s.

3

Minimally transitive groups of degree 2m 3

We begin our work towards the proof of Theorem 5.3 with a discussion of minimally transitive permutation groups. As mentioned in Section 1, we use these groups to study minimal generator numbers in
e is
modules for permutation groups. Specifically, if H ≤ G are finite groups, V is a G-module, and G
e

G
∼
,
a subgroup of G acting transitively on the set H\G of right cosets of H in G, then V ↑G
e
H = V ↑ G∩H

by Mackey’s Theorem (see [16, Proposition 6.20]). Thus, when studying induced modules, one may
often reduce to the case where G acts minimally transitively on H\G.

Note also that the bounds we obtain in Theorem 4.24 and its corollaries are strong enough to
prove Theorem 5.3 in most cases. Due to the nature of the bounds however, this is not the case when
|G : H| has the form 2m 3. Thus, we have to work harder, and try to obtain some information about

the structure of the minimally transitive groups of degree 2m 3. Recall from Section 1 that our main
result is as follows.
Theorem 1.8. Let G be a minimally transitive permutation group of degree n = 2m 3. Then one of
the following holds:
(i) G is soluble; or

(ii) G has a unique nonabelian chief factor, which is a direct product of copies of L2 (p), where p is
a Mersenne prime.
We begin preparations towards the proof of Theorem 1.8 with some easy observations on minimally
transitive groups.
Lemma 3.1. Let G be a transitive subgroup of Sn , let A be a point stabiliser in G, let 1 6= L be a

normal subgroup of G, and let Ω = {∆1 , . . . , ∆χ } be the set of L-orbits. Then

(i) Either L is transitive, or Ω forms a system of blocks for G. In particular, the size of an L-orbit
divides n.
(ii) (L, ∆1 ) is permutation isomorphic to (L, ∆j ), for all j.
(iii) |Ω| = |G : AL|.
(iv) G is minimally transitive if and only if the only subgroup X ≤ G satisfying AX = G is X = G.
(v) If G is minimally transitive, then GΩ is minimally transitively.
(vi) If n = pa for a prime p and G is minimally transitive, then G is a p-group.
Proof. Parts (i), (ii) and (iii) are clear. Also, a subgroup X of G is transitive if and only if AX = G.
Hence, Part (iv) follows.
Part (v) is proved in [13, Theorem 2.4]. Finally, Part (vi) follows since a Sylow p-subgroup of a
transitive group of degree pa acts transitively.
9

3.1

Subgroups of index 2m 3 in direct products of nonabelian simple groups

In [24, Corollary 6], information is given regarding the prime divisors of indices of subgroups of simple
groups. We utilise this work in the following proposition.
Proposition 3.2. Let T be a nonabelian finite simple group, and suppose that T has a proper subgroup
X of index n = 2i 3j , with 0 ≤ j ≤ 1. Then one of the following holds:
(i) T = M12 and X is contained in one of the two T -conjugacy classes of copies of M11 in M12 .
(ii) T = M11 or M24 , and X is T -conjugate to L2 (11) or M23 , respectively.
(iii) T = Ar , r = 2i 3j , and either X is T -conjugate to Ar−1 , or r = 6 and X is T -conjugate to L2 (5).
(iv) T = L2 (p) where p is a prime of the form p = 2f1 3f2 − 1 with f2 ≤ 1, and X is a subgroup of
index either 1 or 3 in a T -conjugate of the maximal subgroup M = Cp ⋊ C(p−1)/2 < L2 (p).

Proof. For a finite set F , let π(F ) denote the set of prime divisors of |F |. Thus, we have π(X) ⊆ π(T ),
since X ≤ T . We wish to reduce to the case π(X) = π(T ) and then use [24, Corollary 6]. However,

we first need to deal with some cases which are not covered by this approach. First, the classification
of the maximal subgroups of the simple classical groups of dimension up to 12 implies that T is not
L2 (8), L3 (3), U3 (3), Sp4 (8), U4 (2) or U5 (2) (see [6, Tables 8.1, 8.2, 8.3, 8.4, 8.5, 8.6, 8.10, 8.11, 8.14,
8.20 and 8.21]).
Assume next that T ∼
= L2 (p), for some prime p of the form p = 2f1 3f2 − 1, with f2 ≥ 0. Also, let

M be a maximal subgroup of T containing X. Then, since |T : M | divides |T : X| = 2i 3j with j ≤ 1,

we must have M = Cp ⋊ C(p−1)/2 , and f2 ≤ 1 (see [6, Table 8.1]). Set l := 1 if f2 = 0, and l := 3 if
f2 = 1. Since (p + 1)/l is the highest power of 2 dividing |T |, and |T : X| = 2i 3j with j ≤ 1, either

X = M ; or f2 = 0 and |M : X| = 3. This is the situation described in (iv).

Next, assume that T is one of the Mathieu groups M11 or M12 . Using the ATLAS [11], we find

that the only possibilities for X are T = M11 and X is T -conjugate to L2 (11) ≤ M11 (of index 12);
or T = M12 and X is a member of one of the two T -conjugacy classes of M11 ≤ M12 (of index 12).

Finally, assume that T is not one of the groups considered above, and let Π be the set of primes for

T given in the statement of [24, Corollary 6]. Then π(|T : X|) ⊆ {2, 3}, and q ≥ 5 for each q ∈ Π (the

cases where Π contains 2 or 3 have been dealt with in the preceding paragraphs - see [24, Corollary
6]). Thus, we must have Π ⊆ π(X). Hence [24, Corollary 6] gives π(X) = π(T ) and the possibilities
for T and X are as follows (see [24, Table 10.7]).

(1) T = Ar , Ak E X ≤ Sk × Sr−k , and k is greater than or equal to the largest prime p with p ≤ r (in

particular, k ≥ 5, since T is simple). Then |Ar : Ar ∩ (Sk × Sr−k )| = kr divides |T : X| = 2i 3j .


But a well-known theorem of Sylvester and Schur (see [17]) states that either kr = 1 or kr has
a prime divisor exceeding min {k, r − k}. Thus, since k ≥ 5 we must have k = r − 2 or k = r − 1.
Since r ≥ 5, k = r − 1 is the only option and hence X = Ar−1 , which gives us what we need.

(2) T = A6 , X = L2 (5). This, together with (1) above, gives precisely the situation described in (iii).
(3) T = PSp2m (q) (m, q even) or P Ω2m+1 (q) (m even, q odd), and Ω−
2m (q) E X. Then X ≤
−
i j
NT (Ω−
2m (q)), so |T : NT (Ω2m (q))| divides |T : X| = 2 3 . But

10

−
|NT (Ω−
2m (q)) : Ω2m (q)| = 2, by [22, Proposition 4.8.6] for T = PSp2m (q) and [22, Proposition
i+1 3j . Also, for each of the two choices
4.1.6] for T = P Ω2m+1 (q). Hence, |T : Ω−
2m (q)| divides 2

m m
m m
f
f
of T we get |T : Ω−
2m (q)| = q (q − 1). But q (q − 1) cannot be of the form 2 or 2 3, since

m > 1 and (m, q) 6= (2, 2) (as T is simple). Therefore, we have a contradiction.

(4) T = P Ω+
2m (q) (m even, q odd) and Ω2m−1 (q) E X. As above, X ≤ NT (Ω2m−1 (q)), and we use
[22, Proposition 4.1.6 Part (i)] to conclude that |NT (Ω2m−1 (q)) : Ω2m−1 (q)| = 2. It follows that
1 m−1 m
(q
2q

− 1) = |T : Ω2m−1 (q)| divides 2i+1 3j . This again gives a contradiction, since m ≥ 4.

(5) T = PSp4 (q) and PSp2 (q 2 ) E X. Then X ≤ NT (PSp2 (q 2 )), and [22, Proposition 4.3.10] gives

|NT (PSp2 (q 2 )) : PSp2 (q 2 )| = 2. It follows that q 2 (q 2 − 1) = |T : PSp2 (q 2 )| divides 2i+1 3j . Again,
this is impossible.

(6) In each of the remaining cases (see [22, Table 10.7]), we are given a pair (T , Y ), where T is L2 (8),
2
′
L3 (3), L6 (2), U3 (3), U3 (5), U4 (3), U6 (2), PSp4 (7), PSp4 (8), PSp6 (2), P Ω+
8 (2), G2 (3), F4 (2) ,

M24 , HS, McL, Co2 or Co3 , and Y is a subgroup of T containing X. Apart from when T = M24 ,
we find that |T : Y | does not divide 2i 3j , so we get a contradiction in each case. When T = M24 ,
the only possibility is when X is T -conjugate to M23 ≤ M24 (of index 24).

This completes the proof.
Our main tool in proving Theorem 1.8 is the Frattini argument. The result is well-known, but we
couldn’t find a reference so we include a proof here.
Lemma 3.3. Let G be a group, and let L be a normal subgroup of G. Suppose that H is a subgroup
of L with the property that H and H α are L-conjugate for each α ∈ Aut(L). Then G = NG (H)L.
Proof. Let g ∈ G. Then conjugation by g induces an automorphism of L, so H g = H l for some l ∈ L,

by hypothesis. Hence, gl−1 ∈ NG (H), so g ∈ NG (H)L, and this completes the proof.
With the Frattini argument in mind, the next corollary will be crucial.

Lemma 3.4. Let T be a nonabelian finite simple group, and suppose that T has a proper subgroup X
of index r := 2i 3j , with 0 ≤ j ≤ 1. Assume also that if T ∼
= L2 (p), with p a Mersenne prime, then

j = 0. Denote by Γ the set of right cosets of X in T . Then there exists a proper subgroup H of T
with the following properties:
(i) H and H α are conjugate in T for each automorphism α ∈ Aut(T ); and
(ii) NT (H)Γ is transitive.

Proof. By Proposition 3.2, the possibilities for the pair (T, X) (up to conjugation in T ) are as follows:
1. (T, X) = (Ar , Ar−1 ), with r = 2i 3j for some j ≤ 1, or (T, X) = (A6 , L2 (5)). Since T is

nonabelian simple, r ≥ 6, so r is even. If r is a power of 2, let H be a Sylow 2-subgroup of T .
Then H Γ itself is transitive, and properties (i) and (ii) are clearly satisfied.

Otherwise, let H = h(1, 2, 3), (4, 5, 6), . . . , (r − 1, r − 2, r)i. Then NT (H)Γ is transitive. Thus,

(ii) is satisfied. Property (i) is also easily seen to be satisfied (this includes the case r = 6, when

Out (A6 ) has order 4).
11

2. (T, X) = (M11 , L2 (11)): Let H be a Sylow 3-subgroup of T . Then NT (H) ∼
= M9 : 2 (see page
18 of the ATLAS of finite groups [11]) acts transitively on the cosets of X. Since Aut(M11 ) =
Inn(M11 ), (i) and (ii) are satisfied.
3. T = M12 and X is T -conjugate to one of the two copies of M11 in M12 ; or T = M24 and X is
T -conjugate M23 : In each case, let H be a subgroup of T generated by a fixed point free element
of order 3. When T = M12 , NT (H) ∼
= A4 × S3 (see [11, page 18]) is a maximal subgroup of T ,
and acts transitively on the cosets of X (for each copy of M11 ). Also, the unique non-identity

outer automorphism of M12 fixes the set of T -conjugates of H, so both (i) and (ii) are satisfied.
When T = M24 , NT (H) has order 1008, and acts transitively on the cosets of X (using MAGMA
[5], for example). Also, Out (T ) is trivial. Thus, (i) and (ii) are again satisfied.
4. T = L2 (p), with p = 2f1 3f2 −1 ≥ 7, f2 ≤ 1 and X = Cp ⋊C(p−1)/2 . Then |T : X| = p+1 = 2f1 3f2 .
Assume first that p ≥ 7, and let H be a dihedral group of order p + 1 contained in T . Since T

has a unique conjugacy class of maximal subgroups of dihedral groups of order p + 1, (i) follows.
Furthermore, |T : H| and |T : X| are coprime, so (ii) is also satisfied.
This just leaves the case p = 5, but in this case T = A5 and X is T -conjugate to D10 so taking
H = A4 gives us what we need.

Lemma 3.5. Let p ≥ 7 be a Mersenne prime, and let L = T1 × T2 × . . . × Te , where each Ti ∼
= L2 (p).

Also, let A be a subgroup of L such that |L : A| = 2a 3, for some a, and |Ti : Ti ∩ A| ∈ {p + 1, 3(p + 1)}

for all i, with |Ti : Ti ∩ A| = 3(p + 1) for at least one i. Then
(i) |L : A| = 3(p + 1)e .

(ii) Let P be a Sylow p-subgroup of L. Then NL (P ) is soluble, and has precisely 2e orbits on the set

∆ of (right) cosets of A in L, with ke orbits of size 3pk , for each k, 0 ≤ k ≤ e.

Proof. We first prove Part (i) by induction on e, with the case e = 1 being trivial. So assume that
e > 1, and fix k in the range 1 ≤ k ≤ e with |Tk : Tk ∩ A| = 3(p + 1). Also, fix i 6= k, and set

T̂i := T1 × . . . × Ti−1 × Ti+1 × . . . × Te and Âi = A ∩ T̂i . Then

|Tj : Tj ∩ Âi | = |Tj : Tj ∩ T̂i ∩ A| = |Tj : Tj ∩ A| ∈ {3(p + 1), p + 1}
for each j 6= i. In particular, |Tk : Tk ∩ Âi | = 3(p + 1). Also, |T̂i : Âi | = |T̂i A : A| divides |L : A|, and
is divisible by |Tk : Tk ∩ Âi | = |Tk Âi : Âi | = 3(p + 1), so |T̂i : Âi | = 2bi 3, for some bi ≤ a. Hence, the
inductive hypothesis implies that |T̂i : Âi | = 3(p + 1)e−1 .

Assume that the claim in Part (i) does not hold. Then since (p + 1)e is the highest power of 2

dividing |L|, we must have |L : T̂i A| = |L : A|/|T̂i : Âi | < p + 1. Hence, if ρi : L → Ti denotes

projection onto Ti , then |Ti : ρi (A)| = |ρi (L) : ρi (T̂i A)| = |L : T̂i A| < p + 1. But, as can be readily

checked using [6, Tables 8.1 and 8.2], no maximal subgroup of L2 (p) can have index a power of 2 and

strictly less than p + 1. Thus, we must have T̂i A = L, so A projects onto Ti . But then A ∩ Ti is a

12

normal subgroup of Ti , so A ∩ Ti = 1 or Ti . This contradicts |Ti : A ∩ Ti | ∈ {p + 1, 3(p + 1)}, and Part

(i) follows.

Finally, we prove (ii). Let N := NL (P ). By Proposition 3.2 Part (iii), each Tj ∩ A is contained in

a maximal subgroup Mj := Cp ⋊ C(p−1)/2 of Tj , and |Tj : Tj ∩ A| ∈ {p + 1, 3(p + 1)}. Thus, Tj ∩ A has
∼ Cp . Let Pe := P1 × . . . × Pe , so that Pe is a Sylow p-subgroup of L.
a normal Sylow p-subgroup Pj =
Since P and Pe are conjugate in L, we may assume, for the purposes of proving Part (ii), that Pe = P .

Since Mj = NTj (Pj ) is soluble, N = M1 × . . . × Me is soluble. Also, P E A since P is a characteristic
subgroup of (T1 ∩ A) × . . . × (Te ∩ A) E A, so A ≤ N .

Suppose first that e = 1. Then |L : A| = 3(p + 1), so A has index 3 in N , since |L : N | =

|L : M1 | = p + 1. Let x ∈ L\N , and let Γ ⊂ ∆ be the N -orbit corresponding to Ax. Then
|Γ| = |N : N ∩ Ax | =

|L:N ∩Ax |
|L:N | .

Since |L : N | = p + 1 is a power of 2 and |L : N ∩ Ax | is divisible by

|L : Ax | = 3(p + 1), it follows that 3 divides |Γ|. Also, as mentioned above, Ax and N have unique
Sylow p-subgroups P x and P , respectively. Since x does not normalise P , we have P x 6= P , so p, and

hence 3p, divides |N : N ∩ Ax | = |Γ|. Since |N : A| = 3 and |L : A| = 3(p + 1), it follows that |Γ| = 3p,
which proves the claim in the case e = 1.

We now consider the general case. Fix 1 ≤ i ≤ e, and xi ∈ Ti \Mi . Suppose first that |Ti : Ti ∩ A| =

3(p + 1). From the previous paragraph, we see that Mi has precisely two orbits on the cosets of Ti ∩ A

in Ti , of size 3 and 3p, represented by A and Axi respectively. Next, assume that |Ti : Ti ∩ A| = p + 1.

Then Mi = Ti ∩ A. Moreover, arguing as in the previous paragraph, p divides |Mi : Mi ∩ Axi |, from
which it follows that Mi again has two orbits on the cosets of A ∩ Ti in Ti , of size 1 and p, represented
by A and Axi respectively.

Let B := (T1 ∩A)×. . .×(Te ∩A)EA. It is clear, from the previous paragraph, that N = M1 ×. . .×Me

has 2e orbits on the cosets of B in L, represented by Bt1 t2 . . . te , where ti ∈ {1, xi }, for 1 ≤ i ≤ e.

Also, the orbit represented by the coset Bt1 t2 . . . te has cardinality 3d pk , where k is the number of
subscripts i with ti 6= 1, and d is the number of subscripts i with
|Ti : Ti ∩ A| = 3(p + 1).

(3.1)

Since B ≤ A, N has at most 2e orbits in ∆. Suppose there exist ti , e
ti ∈ {1, xi } for 1 ≤ i ≤ e,
and n = n1 n2 . . . ne ∈ N (with ni ∈ Mi ), such that At1 t2 . . . te = A(e
t1 e
t2 . . . e
te )(n1 n2 . . . ne ). Then
ti = ai e
ti ni , where a1 a2 . . . ae ∈ A. Since A ≤ N , it follows that ti = 1 if and only if e
ti = 1.
t2 . . . e
te . Thus, N has precisely 2e orbits in ∆, represented by At1 . . . te , where
Hence, t1 t2 . . . te = e
t1 e
ti ∈ {1, xi }. Since the size of the N -orbit corresponding to At1 t2 . . . te is
|N : N ∩ At1 t2 ...te | =

|N : N ∩ B t1 t2 ...te |
|N : N ∩ B t1 t2 ...te |
≥
,
|N ∩ At1 t2 ...te : N ∩ B t1 t2 ...te |
|At1 t2 ...te : B t1 t2 ...te |

and |At1 t2 ...te : B t1 t2 ...te | = |A : B| = |N : B|/|N : A| = 3d−1 , it now follows from (4.2.1) that
|N : N ∩ At1 t2 ...te | =

|N : N ∩ B t1 t2 ...te |
= 3pk
3d−1

where k is the number of subscripts i such that ti 6= 1. This proves (ii).

13

3.2

The proof of Theorem 1.8

First, we fix some notation which will be retained for the remainder of this section: Let G be a
minimally transitive permutation group of degree 2m 3; let A be the stabiliser in G of a point δ; let L
be a minimal normal subgroup of G; let Ω be the set of L-orbits; let K := Ker(GΩ ) be the kernel of
the action of G on Ω; and finally, let ∆ be the L-orbit containing δ.
Remark 3.6. GΩ acts minimally transitively on Ω, by Lemma 3.1 Part (v). Note also that, if |G : AL|

is a power of 2, then GΩ is a 2-group by Lemma 3.1 Part (vi).
We require the following easy proposition.

Proposition 3.7. There exists a subgroup E of G such that G = EL and E ∩ K is soluble.
Proof. Consider the (set-wise) stabiliser StabG (∆) of ∆ in G. Since L acts transitively on ∆, we have
LA = StabG (∆). Let E be a subgroup of G minimal with the property that EK = G. Then E ∩ K

is contained in the Frattini subgroup of E, and hence is soluble. Finally, G = EK ≤ E StabG (∆) =

ELA, so G = ELA. Thus, EL = G by minimal transitivity, as needed.

Corollary 3.8. If L is abelian, then the set of nonabelian chief factors of G equals the set of nonabelian
chief factors of GΩ . If L is nonabelian and |Ω| = |G : LA| is a power of 2, then L is the unique

nonabelian chief factor of G.

Proof. Let E be as in Proposition 3.7, and assume that either L is abelian or L is nonabelian and
|Ω| = |G : LA| is a power of 2. For a finite group X write NCF(X) for the set of nonabelian chief

factors of X. We need to prove that NCF(G) = NCF(GΩ ) if L is abelian, and NCF(G) = {L}
otherwise. Note that if |Ω| is a power of 2 then GΩ is soluble, by Remark 3.6.

Since E Ω is transitive, the minimal transitivity of GΩ implies that GΩ = E Ω ∼
= E/E ∩ K. Since

E ∩ K is soluble, it follows that NCF(GΩ ) = NCF(E). By hypothesis, either L is abelian, or L is

nonabelian and E Ω , and hence E, is soluble. Since G = EL, the claim follows, in either case.

Proposition 3.9. Suppose that L = T1 × . . . × Tf , where each Ti is isomorphic to a nonabelian

simple group T . Without loss of generality, assume that KerL (∆) = Te+1 × . . . × Tf , so that L∆ =

T1∆ × . . . × Te∆ . Then

(i) T ∼
= L2 (p) for some Mersenne prime p,
(ii) |Ti : Ti ∩ A| ∈ {p + 1, 3(p + 1)} for each 1 ≤ i ≤ e, and;
(iii) There exists at least one i in the range 1 ≤ i ≤ e such that |Ti : Ti ∩ A| = 3(p + 1).
Proof. Suppose that the proposition is false, and set Xi := Ti ∩ A. Note that |Ti : Xi | divides 2m 3 for
each i, by Lemma 3.1 Part (i). Hence, Proposition 3.2 implies that one of the following must hold:

(a) T ∼
6 L2 (p), for any Mersenne prime p. Then by Proposition 3.2, either Ti ∼
= M12 and each Xi is
=
contained in one of the two conjugacy classes of M11 in M12 ; or (Ti , Xi ) = (Ar , Ar−1 ), (A6 , L2 (5)),

(M11 , L2 (11)), (M24 , M23 ), or (L2 (p), Cp ⋊ C p−1 ) where p is a prime of the form p = 2f1 3 − 1.
2

Here, the group Xi is given up to conjugacy in Ti .
14

(b) T ∼
= L2 (p) for some Mersenne prime p. In this case, Proposition 3.2 implies that |Ti : Xi | = p + 1
for all i. In particular, Xi is Ti -conjugate to the maximal subgroup Mi := Cp ⋊ C p−1 of Ti . (We
2

remark that it is here where we use the assumption that the proposition is false. Specifically,
since |Ti : Xi | divides 2m 3 for each i, Proposition 3.2 implies that Xi is Ti -conjugate to either Mi ,
or an index 3 subgroup of Mi . Hence |Ti : Xi | ∈ {p + 1, 3(p + 1)} for each i. Thus, Part (iii) of

the proposition must fail, forcing |Ti : Xi | to be p + 1, and hence for Xi to be Ti -conjugate to Mi ,
for each i.)

Fix 1 ≤ i ≤ e, and write T = Ti . Note that T ∆ is isomorphic to T . Set Γ := δT ⊂ ∆, and set

X := T ∩ A. Then the pair (T, X) satisfies the hypothesis of Lemma 3.4. Thus, we conclude that T
contains a proper subgroup H such that

(i) H and H α are conjugate in T for each automorphism α ∈ Aut(T ); and
(ii) NT (H)Γ is transitive.
′

′

Fix a T -orbit Γ′ in ∆. We claim that NT (H)Γ is transitive. By Lemma 3.1 Part (ii), T Γ is
permutation isomorphic to T Γ . Hence, by (ii) above, there exists an automorphism α of T such that
NT (H)α = NT (H α ) acts transitively on Γ′ . Since H is T -conjugate to H α , it follows that NT (H) is
T -conjugate to NT (H)α . Thus, NT (H) acts transitively on Γ′ , as claimed.
Since Ti ∼
= Tj for all i, j, we can choose the subgroup Hj < Tj corresponding to H, and the
subgroup Nj < Tj corresponding to NT (H), for each 1 ≤ j ≤ f . Furthermore, each group Xi is
determined up to conjugacy in Ti by (a) and (b) above. Hence, by the previous paragraph
Nj acts transitively on each Tj -orbit in ∆ whenever 1 ≤ j ≤ e.

(3.2)

e = H1 × H2 × . . . × Hf < L, and N := N1 × N2 × . . . × Nf . Now, note that N ≤ NL (H).
e
Set H
e ∆.
Thus, N ∆ × N ∆ × . . . × N ∆ = N ∆ ≤ NL (H)
1

2

e

We will now prove that N ∆ is transitive. Indeed, let ǫ ∈ ∆, and let x ∈ L such that δx = ǫ. Write

x = t1 t2 . . . te , with tj ∈ Tj . By (ii) above, N1 acts transitively on δT1 . Hence, there exists n1 ∈ N1

such that δt1 = δn1 . We now inductively define the permutations n2 , . . ., ne by choosing nj ∈ Nj such

that (δn1 ···nj−1 )nj = δn1 ···nj−1 tj (this is possible since Nj acts transitively on (δn1 ...nj−1 )Tj , by (4.3.1)).
Then
ǫ = δt1 t2 ···te = (δt1 )t2 ···te = δn1 t2 ···te = (δn1 t2 )t3 ···te
= δn1 n2 t3 ···te = (δn1 n2 t3 )t4 ···te = · · · = δn1 n2 ···ne
Thus
N ∆ is transitive, as claimed.

(3.3)

Finally, let α ∈ Aut (L) ∼
= Aut (T ) ≀ Sym(f ). Then there exists τ ∈ Sym (f ) and αi ∈ Aut (T ) such

15

that
e α = H ατ1 × H ατ2 × . . . × H ατf
H
1
2
f
α

= H1 1τ

−1

α

× H2 2τ

−1

α

× . . . × Hf f

τ −1

α

By (i) above, there exists, for each 1 ≤ i ≤ f , an element ti ∈ Ti such that Hi

−1
iτ

= Hiti . Hence

e α = H t1 × H t2 × . . . × H tf = H
e t1 t2 ...tf .
H
1
2
f

e and H
e α are conjugate in L for all α ∈ Aut (L). Lemma 3.3 then implies that G =
Thus, H
e
e acts transitively on the set Ω of L-orbits. But NG (H)
e also acts transitively on
NG (H)L.
Thus, NG (H)
e is a transitive subgroup of G. By minimal transitivity
the fixed L-orbit ∆, by (4.3.2). Hence, NG (H)

e = G, so H
e is normal in G. But this is a contradiction, since 1 < H
e <L
of G, it follows that NG (H)

and L is a minimal normal subgroup of G. The proof is complete.

Property (iii) of Proposition 3.9 immediately implies the following.
Corollary 3.10. Suppose that L is isomorphic to a direct product of copies of L2 (p), where p is a
Mersenne prime. Then |∆| is divisible by 3.
Finally, we are ready to prove Theorem 1.8.
Proof of Theorem 1.8. Assume that G is a counterexample to the theorem of minimal degree. Note
that |Ω| = |G : LA| divides |G : A| = 2m 3, and is less than 2m 3. Furthermore, a minimally transitive

group of 2-power degree is soluble by Remark 3.6. Hence, the minimality of G as a counterexample
implies that GΩ = G/K satisfies either (i) or (ii) in the statement of the theorem.
If L is abelian, then Corollary 3.8 implies that the set of nonabelian chief factors of G equals the
set of nonabelian chief factors of GΩ . Thus, the result follow from the inductive hypothesis in this
case. So we may assume that L = T1 × T2 × . . . × Tf , where each Ti is isomorphic to a nonabelian finite
simple group T . Furthermore, Proposition 3.9 then implies that T ∼
= L2 (p), where p is a Mersenne
prime. Also, 3 divides |∆| by Corollary 3.10. But then |Ω| = |G : LA| is a power of 2, so L is the

unique nonabelian chief factor of G by Corollary 3.8. This contradiction completes the proof.

We also deduce two corollaries which will be vital in our application of Theorem 4.24 (see Section
4.3.2).
Corollary 3.11. Assume that G is insoluble, and let p := 2a − 1 be a Mersenne prime such that G

has a unique nonabelian chief factor isomorphic to a direct product of f copies of L2 (p). Then there
exists a triple of integers (e, t1 , t), with e ≥ 1, and t ≥ t1 ≥ 0, such that
(i) m = ea + t, and;
(ii) For some soluble subgroup N of G, N has 2e+t1 orbits, with
for each k, 0 ≤ k ≤ e.

16

e  t1
k 2

of them of length 3pk × 2t−t1 ,

Proof. Let E be as in Proposition 3.7, so that G = EL, and E ∩ K is soluble. We prove the claim by

induction on m. Suppose first that L is abelian. Then since EL = G and E ∩ K is soluble, GΩ = E Ω

e 3 and |∆| = 2m−m
e , for some m
is insoluble. Hence |Ω| = 2m
e with 1 ≤ m
e < m, by Lemma 3.1 Parts (i)
and (vi). The inductive hypothesis then implies that there exists a triple (e
e, te1 , e
t) such that

1. m
e = eea + e
t, and;

e of E Ω , N
e has 2ee+te1 orbits, with
2. For some soluble subgroup N
for each k, 0 ≤ k ≤ ee.

e  te1
e
k 2

e

of them of length 3pk ×2t−te1 ,

Set e := ee, t := m − m
e +e
t, and t1 := te1 , so that m = ea + t, which is what we need for (i). Also, let
e , and set N := LY . Then N is soluble, since the groups Y Ω , Y ∩ K and L
Y ≤ E such that Y Ω = N
are soluble. Moreover, N acts transitively on each L-orbit, since L ≤ N . Since each L-orbit has size

e , it follows that N has 2e+t1 orbits, with e × 2t1 of them of length 3pk 2e
t−e
t1 +m−m
e = 3pk 2t−t1 .
2m−m
k
This gives us what we need.

So assume that L = T1 × T2 × . . . × Tf , where each Ti ∼
= L2 (p). By Proposition 3.2 Part (iii), Ti ∩ A
is contained in the maximal subgroup Mi ∼
= Cp ⋊ C(p−1)/2 of Ti , and |Ti : Ti ∩ A| ∈ {p + 1, 3(p + 1)}

for all i. Furthermore, Proposition 3.9 implies that there exists at least one subscript i such that

|Ti : Ti ∩ A| = 3(p + 1). Lemma 3.5 now implies that |∆| = |L : L ∩ A| = 3(p + 1)e = 2ea 3, where e is

the number of direct factors of L acting non-trivially on ∆. It also follows that |Ω| = 2m−ea .

By relabeling the Ti if necessary, we may write L∆ = T1∆ × T2∆ × . . . × Te∆ . Let P be a Sylow p-

subgroup of L, and let N := NL (P ). By Lemma 3.5 Part (ii), N is soluble, and NL (P )∆ = NL∆ (P ∆ )

has 2e orbits on ∆, with ke of size 3pk , for each 0 ≤ k ≤ e. Since the action of L on each L-orbit is
permutation isomorphic to the action of L on ∆, it follows that N := NL (P ) has 2e orbits on each

L-orbit, with ke of size 3pk , for each 0 ≤ k ≤ e. Also, N acts trivially on the set Ω of L-orbits, so N

has 2e+m−ea orbits in total, with 2m−ea ke of them of size 3pk , for each 0 ≤ k ≤ e. Setting t := m − ea
and t1 := t now gives us what we need, and completes the proof.

Corollary 3.12. Let S be a transitive permutation group of degree s := 2m 3, and assume that S
contains no soluble transitive subgroups. Then there exists a Mersenne prime p := 2a − 1 and a triple

of integers (e, t1 , t), with e ≥ 1, and t ≥ t1 ≥ 0, such that
(i) m = ea + t, and;

(ii) For some soluble subgroup N of S, N has 2e+t1 orbits, with
for each k, 0 ≤ k ≤ e.

e  t1
k 2

of them of length 3pk × 2t−t1 ,

Proof. Let G be a minimally transitive subgroup of S. Then G is insoluble, so Corollary 3.11 applies,
and the result follows.

4

Generating submodules of induced modules for finite groups

The purpose of this paper is to study upper bounds for the function d on the class of finite transitive
permutation groups. As can be seen from Section 1, this essentially amounts to deriving upper bounds
on d(G) for subgroups G of wreath products R ≀ S. Our main strategy for doing this will be to reduce
17

modulo the base group B of R ≀ S and use induction to bound d(G/G ∩ B). In this way, all that

remains is to investigate the contribution of G ∩ B to d(G): The purpose of this section is to carry

out such an investigation.

As we will show in Lemma 5.8, the group G ∩ B is built, as a normal subgroup of G, from

submodules of induced modules for G, and nonabelian chief factors of G. Thus, the main aim of the

section will be to derive upper bounds for generator numbers in submodules of induced modules. The
strategy to do this will be to first view soluble groups as certain partially ordered sets: We prove
some properties of these partially ordered sets in Section 4.1. Our main results are Theorem 4.13 and
Theorem 4.24, which are proved in Sections 4.3.1 and 4.3.2 respectively. We remark that Theorem
4.13 improves [7, Theorem 1.5], while Theorem 4.24 improves [28, Lemma 4].

4.1

Partially ordered sets

Let P = (P, 4) be a finite partially ordered set, and let w(P ) denote the width of P . That is, w(P ) is
the maximum cardinality of an antichain in P . Suppose now that, with respect to 4, P is a cartesian
product of chains, and write P = P1 × P2 × . . . × Pt , where each Pi is a chain of cardinality ki . Then
P is poset-isomorphic to the set of divisors of the positive integer m = pk11 −1 pk22 −1 . . . ptkt −1 , where p1 ,

p2 , . . ., pt are distinct primes. We make this identification without further comment.
Next, recall that each divisor d of m can be written uniquely in the form d = pr11 pr22 . . . prt t , where
P
0 ≤ ri ≤ ki − 1, for each i, 1 ≤ i ≤ t. In this case, the rank of d is defined as r(d) = ti=1 ri . For
P
0 ≤ k ≤ K := ti=1 (ki − 1), let Rk denote the set of elements of P of rank k; clearly Rk is an antichain

in P . In fact, it is proved in [14] that w(P ) = max |Rk |. This maximal rank set occurs at k = ⌊K/2⌋,
and hence, by [2, Theorem 2], we have





s
K
w(P ) ≤ K
2
⌊K/2⌋
where s := |P | =

Qt

i=1 ki

(note that equality holds when t is even and each ki is 2, so this upper

bound is best possible). Stated more concisely, we have
Lemma 4.1. Suppose that a partially ordered set P , of cardinality s ≥ 2, is a cartesian product of
the chains P1 , P2 , . . ., Pt , where each Pi has cardinality ki . Then


K
s
w(P ) ≤ K
,
2
⌊K/2⌋


where K :=

Pt

i=1 (ki

− 1).

We now define a constant b,
b :=

r

2
.
π

Proposition 4.2. Let K be a positive integer. Then


K
⌊K/2⌋



18

b2K
≤√ .
K

(4.1)

Proof.

1

First consider the case where K = 2t (t ∈ N), and note that
  2
   


t 
2t 1
1 33
55
2t − 1 2t − 1
1Y
1
2t
=
...
=
1+
t 4t
2 24
46
2t − 2 2t
2
4j(j − 1)
j=2

By Wallis’ Formula, the expression in the middle converges to 2/π. Hence, since the expression on
√
  2

the right is increasing, we have 2t 2tt 41t ≤ 2/π, that is, 2tt ≤ b4t / 2t, as claimed. If K is odd,
 1

K
K+1
we have ⌊K/2⌋
= 2 ⌊(K+1)/2⌋
, and the bound in (4.2) follows from the even case above.
Proof of Theorem 1.3. By Lemma 4.1 and Proposition 4.2, we have
w(P ) ≤


 K

K
b2
s
bs
s
√
≤
=√
2K ⌊K/2⌋
2K
K
K

If each ki = p, then K = t(p − 1), and the second part of the claim follows. Since K =
Pt
i=1 log ki = log s, the first part also follows, and the proof is complete.

4.2
4.2.1

Pt

i=1 (ki − 1)

≥

Preliminary results on induced modules for finite groups
Composition factors in induced modules

Let F be a field, let G be a finite group, and let V be a module for G over F. Let
0 = N0 < N1 < . . . < Na = V
be a G-composition series for V , and say that a factor Ni /Ni−1 is complemented if there exists a
submodule Si of V containing Ni−1 such that V /Ni−1 = Ni /Ni−1 ⊕ Si /Ni−1 . Also, for an irreducible

F[G]-module W , write tW (V ) for the number of complemented composition factors of V isomorphic

to W .
Now, fix an irreducible F[G]-module W with tW (V ) ≥ 1. Then there exists a submodule M of V

with the property that V /M is G-isomorphic to W : Define RW (V ) to be the intersection of all such
M . In particular, RW (V ) contains the radical Rad(V ) of V .
Lemma 4.3. V /RW (V ) ∼
= W ⊕tW (V ) .
Proof. Let t := tW (V ), and write R := RW (V ) = M1 ∩ M2 ∩ . . . ∩ Me , where V /Mi is isomorphic to

W . Then

V /R ≤ (V /M1 ) ⊕ (V /M2 ) ⊕ . . . ⊕ (V /Me )
and hence V /R is a direct sum of k copies of W , where k ≤ e. Since tW (V ) = tW (V /R), we have
t = k, and this completes the proof.

Lemma 4.4. Suppose that V = U ↑G
H , for a subgroup H of G and an H-module U , and suppose that

W is a 1-dimensional F[G]-module. Then tW (V ) ≤ dim U .
1

The idea for this bound arose from a discussion at the url
http://math.stackexchange.com/questions/58560/elementary-central-binomial-coefficient-estimates.

19

Proof. Let R = RW (V ) and t = tW (V ). Writing bars to denote reduction modulo R, we have
V = N1 ⊕ N2 ⊕ . . . ⊕ Nt
where each Ni is isomorphic to W . In particular, if we write
V / Rad(V ) =

X

X fX (V ) ,

X an irreducible F[G]-module

then we have t ≤ fW (V ). Moreover, since dim W = 1, we have
fW (V ) = dim HomF[G] (V, W ) = dim HomF[H] (U, W ↓H ) = fW ↓H (U ) ≤ dim U
where the second equality above follows from Frobenius Reciprosity (see [4, Proposition 3.3.1]). This
completes the proof.
We will need an easy consequence of Lemma 4.4. To state it, we first require two definitions and
a remark.
Definition 4.5. Let G be a non-trivial finite group, and F a field. A projective representation of G
of dimension m over F is a homomorphism ρ : G → P GLm (F). Define
RF (G) := min {m : G has a non-trivial representation of dimension m over F} ; and
RF (G) := min {m : G has a non-trivial projective representation of dimension m over F} .
Also define

R(G) := min RF (G) : F a field
Definition 4.6. Let G be a finite group, let F be a field, and let V be an F[G]-module. Define dG (V )
to be the minimal number of elements required to generate V as an F[G]-module.
Remark 4.7. Let G, F and V be as in Definition 4.6, and let t be the number of complemented
G-composition factors of V . We claim that dG (V ) ≤ t. Note first that t is precisely the number of

irreducible constituents of V / Rad(V ). In particular, it follows that dG (V / Rad(V )) ≤ t: let v1 , . . .,

vt ∈ V such that V / Rad(V ) is generated, as a G-module, by {Rad(V ) + v1 , . . . , Rad(V ) + vt }. Let

M be the G-submodule of V generated by {v1 , . . . , vt }. Then V = M + Rad(V ). Since Rad(V ) is
contained in every maximal submodule of V , it follows that V = M , and hence dG (V ) ≤ t, as claimed.
The corollary of Lemma 4.4 can now be stated as follows.

Corollary 4.8. Let G be a finite group, let H be a subgroup of G, and let U be an H-module, over a
field F. Let V := U ↑G
H . Then
dG (V ) ≤

dim U |G : H| − dim U
+ dim U.
RF (G)

20

Proof. Write t for the number of complemented G-composition factors of V which are not isomorphic
to the trivial G-module 1G . By Remark 4.7, we have
dG (V ) ≤ t1G (V ) + t.
Since dim V = dim U |G : H|, we have
t≤

dim U |G : H| − dim U
.
RF (G)

The result now follows immediately from Lemma 4.4.
4.2.2

Induced modules for Frattini extensions of nonabelian simple groups

In this subsection, we make some observations on modules for Frattini extensions of nonabelian simple
groups. That is, modules for groups G with G/Φ(G) a non-abelian simple group.
The main result of this section reads as follows.
Proposition 4.9. Let G be a finite group with a normal subgroup N ≤ Φ(G) such that G/N ∼
= T,

where T is a non-abelian finite simple group. Also, let W be a nontrivial irreducible G-module, over
an arbitrary field F. Then
(i) Each proper normal subgroup of G is contained in N . In particular, N = Φ(G).
(ii) KerG (W ), the kernel of the action of G on W , is contained in N .
(iii) n := dim W ≥ R(T ).

Proof. Part (i) follows since N ≤ Φ(G) and G/N is simple. Part (ii) now follows from Part (i) since

W is non-trivial.

We will now prove (iii). By (ii), we may assume that G is faithful on W . In particular, we may
view G as a subgroup of GLn (F). Let L be a normal subgroup of G, and assume that W ↓L is non-

homogeneous. If K is the kernel of the action of G on the homogeneous components of W ↓L , then

K is a proper normal subgroup of G, so K ≤ N by Part (i). Thus, HN < G for some stabiliser H of

a homogeneous component. Hence, |G : H| ≥ |G : HN | = |G/N : HN/N | ≥ RF (T ), since any proper
subgroup E of T gives rise to a nontrivial permutation representation for T of dimension |T : E| over

F (a non-trivial projective representation of dimension |T : E| is then achieved by reducing modulo
scalars). Thus, the number of homogeneous components is at least RF (T ), and the result follows.

So we may assume that W ↓L is homogeneous for each normal subgroup L of G. Hence, by

Lemma 2.13, we may assume that Z(G) is cyclic and that each abelian characteristic subgroup of G
is contained in Z(GLn (F)).

Let L be the generalised Fitting subgroup of G, and extend the field F so that F is a splitting field
for each subgroup of L, and so that the resulting field extension is normal (see Remark 2.15).
We distinguish two cases.
1. L is soluble. In this case, since L > Z(G), Or (G) must be non-central, for some prime r, and
Or (G)CG (Or (G)) ≥ L. Also, since Or (G) is non-central, we have Or (G), CG (Or (G)) ≤ N by
21

Part (i). Thus, since N ≤ Φ(G) ≤ L, it follows that N = L = Or (G)CG (Or (G)). Hence, by [29,
Lemma 1.7], there exists a positive integer m such that

(1) Or (G) is a central product of its intersection with Z := Z(G) and an extraspecial group E
of order r 1+2m ;
(2) Z(E) coincides with the subgroup of Z of order r (recall that Z is cyclic);
(3) EZ/Z is a completely reducible Fr [G]-module under conjugation; and
(4) CG/Z (EZ/Z) = Or (G)CG (Or (G))/Z.
It follows from (4) that T ∼
= G/N = G/Or (G)CG (Or (G)) is a non-trivial completely reducible
subgroup of GL2m (r). It then follows that
RFr (T ) ≤ 2m.

(4.2)

Next, by Lemma 2.14, W ↓E is completely reducible and its irreducible constituents are non-

trivial. Let U be such a constituent. Since F is a splitting field for E, U is absolutely irreducible.
Hence, dim U ≥ r m , by [18, Theorem 5.5]. Thus, by (4.2), we have
R(T ) ≤ RFr (T ) ≤ 2m ≤ r m ≤ dim U ≤ dim W,
which gives us what we need.
2. L is insoluble. By [19, Lemma 2.14], L contains a normal subgroup X of G of the form X =
S1 ◦ . . . ◦ St , where each Si is isomorphic to a quasisimple group S. But since N ≤ Φ(G), N is

nilpotent. Also, G/N is simple, so we must have G = X and G is quasisimple. In particular,
N = Z ≤ Z(GLn (F)). Hence, T ∼
= G/Z ≤ P GLn (F) and dim W ≥ RF (T ) ≥ R(T ), as required.
This completes the proof.

4.3

Induced modules for finite groups

We begin with some terminology.
Definition 4.10. Let M be a group, acted on by another group G. A G-subgroup of M is a subgroup
of M which is stabilised by G. We say that M is generated as a G-group by X ⊂ M , and write

M = hXiG , if no proper G-subgroup of M contains X. We will write dG (M ) for the cardinality of
the smallest subset X of M satisfying hXiG = M . Finally, write M ∗ := M \{1}.

Note that the definition of dG (M ) is consistent with the notation introduced in Definition 4.6 in
the case where M is a G-module.
Definition 4.11. Let G be a group, acting on a set Ω. Write χ(G, Ω) for the number of orbits of G
on Ω.
The purpose of this section is to derive upper bounds for dG (M ) when M is a submodule of
an induced module for G. To this end, we introduce some notation which will be retained for the
remainder of the section:
22

• Let G be a finite group.
• Fix a subgroup H of G of index s ≥ 2.
• Fix a subgroup H1 of H of index d ≥ 1.
• Let U be a module for H1 of dimension a, over a field F.
• Let K := coreG (H), and fix a subgroup K ′ of K.
G
G∼
G
• Set V := U ↑H
H1 and W := V ↑H to be the induced modules. Note also that V ↑H = U ↑H1 .

• Denote the set of right cosets of H in G [respectively H1 in H] by Ω [resp. Ω1 ].
• Define

m := m(K ′ ) = min{χ(QΩ1 , Ω1 ) : Q ≤ K ′ and QV is semisimple}.

We do not exclude the case d = 1, that is, H = H1 .
4.3.1

Induced modules: The soluble case

This section is essentially an analogue of [7, Section 5]. We first recall the constant b,
b :=

r

2
.
π

We also recall, from Section 1, the following definition.
Definition 4.12. For a positive integer s with prime factorisation s = pr11 pr22 . . . prt t , set ω(s) :=
P
P
ω1 (s) := ri pi , K(s) := ω1 (s) − ω(s) = ri (pi − 1) and
ω
e (s) =

s

2K(s)



P

ri ,


K(s)
j
k .
K(s)
2

The main result of this section reads as follows.
Theorem 4.13. Suppose that GΩ contains a soluble transitive subgroup, and let M be a submodule
of W . Also, denote by χ = χ(K, V ∗ ) the number of orbits of K on the non-zero elements of V . Then
dG (M ) ≤ min
where b :=

p







ad − am
ad − am
bs
√
+ am, χ ω
e (s) ≤ min
+ am, χ
RF (K ′ )
RF (K ′ )
log s

2/π. Furthermore, if s = pt , with p prime, then
dG (M ) ≤ min



ad − am
+ am, χ
RF (K ′ )

$

p

bpt
t(p − 1)

%

.

Remark 4.14. If K has infinitely many orbits on the non-zero elements of V , then we assume, in
Theorem 4.13, and whenever it is used in the remainder of the paper, that
min



ad − am
+ am, χ
RF (K ′ )
23



=

ad − am
+ am.
RF (K ′ )

We begin our work towards the proof of Theorem 4.13 by first collecting a series of lemmas from
[7, Section 5].
Lemma 4.15 ([7], Lemma 5.1). Suppose that GΩ contains a soluble transitive subgroup. Then there
is a right transversal T to H in G, with a partial order 4 and a full order 6, satisfying the following
properties:

(i) Whenever t1 , t2 , t3 ∈ T with t1 < t2 4 t3 , we have t4 < t3 , where t4 is the unique element of T
such that t1 t−1
2 t3 ∈ Ht4 .

(ii) With respect to this partial order, T is a cartesian product of k chains, of length p1 , p2 , . . ., pk ,
where k = ω(s), and p1 , p2 , . . ., pk denote the (not necessarily distinct) prime divisors of s.

Proof. Let F be a subgroup of G such that F Ω is soluble and transitive. By [7, Lemma 5.1], there
exists a right transversal T for F ∩ H in F such that the image T Ω has a partial order 4′ and a full

order 6′ satisfying

(a) Whenever t1 , t2 , t3 ∈ T with t1 Ω <′ t2 Ω 4′ t3 Ω , we have t4 Ω <′ t3 Ω , where t4 is the unique element of
Ω
Ω Ω
T such that (t1 t−1
2 t3 ) ∈ (F ∩ H) t4 .

(b) With respect to this partial order, T Ω is a cartesian product of k chains, of length p1 , p2 , . . ., pk ,
where k = ω(|F : F ∩ H|) = ω(|G : H|) = ω(s), and p1 , p2 , . . ., pk denote the (not necessarily
distinct) prime divisors of s.

For t1 , t2 ∈ T , say now that t1 4 t2 if t1 Ω 4′ t2 Ω , and t1 6 t2 if t1 Ω 6′ t2 Ω . Since F Ω acts transitively

on the set of cosets of H in G, T is a right transversal for H in G. By definition, (a) and (b) above

imply that (i) and (ii) hold for this choice of 4 and 6. This gives us what we need.

For the remainder of Section 4.3 assume that GΩ contains a soluble transitive subgroup, and fix
T to be a right transversal for H in G as exhibited in Lemma 4.15. Then we may write the induced
L
module W = V ↑G
H as W =
t∈T V ⊗ t, where the action of G is given by
′

(v ⊗ t)ht = v h1 ⊗ t1 ,

where tht′ = h1 t1 , h, h1 ∈ H, t, t′ , t1 ∈ T . Thus, each element w in W may be written as
P
w = t∈T v(w, t) ⊗ t, with uniquely determined coefficients v(w, t) in V .

Definition 4.16 ([7], Section 5). Let w ∈ W be non-zero. The height of w, written τ (w), is the

largest element of the set {t ∈ T : v(w, t) 6= 0}, with respect to the full order 6. Also, we define

µ(w) := v(w, τ (w)). Thus, µ(w) is non-zero, and v(w, t) = 0 whenever t > τ (w). The element
µ(w) ⊗ τ (w) is called the leading summand of w.

Remark 4.17. In the language of Definition 4.16, Lemma 4.15 Part (i) states that if the height of
−1

w is t2 , and if t2 4 t3 , then the height of wt2

t3

−1

is t3 . Further, the leading summand of wt2

µ(w) ⊗ t3 .
The formulation in Remark 4.17 leads to an important technical point.
24

t3

is

Proposition 4.18. Let M be a submodule of W . Then M has a generating set X with the following
property: No subset Y of X, whose image τ (Y ) in T is a chain with respect to the partial order 4,

can have more than

min



ad − am
+ am, χ
RF (K ′ )



elements, where χ = χ(K, V ∗ ) denotes the number of orbits of K on the nonzero elements of V .
Before proving Proposition 4.18, we need a preliminary lemma.
Lemma 4.19. A K ′ -composition series for V contains at most am factors isomorphic to the trivial
module.
Proof. Let Q ≤ K ′ such that QV is semisimple and χ(QΩ1 , Ω1 ) = m. By Mackey’s Theorem,
m
M

∼
Ux i ,
V ↓Q = U ↑H
↓
=
Q
H1

(4.3)

i=1

where Uxi := (U ⊗ xi ) ↑Q
x , dim Uxi = dim U = a, for each i, and
Q∩H i
1

P

j

|Q : Q ∩ H1xi | = |H : H1 | = d.

Since QV is semisimple, the number of Q-composition factors of Uxi = (U ⊗ xi ) ↑Q
x isomorphic to
Q∩H i
1

the trivial module 1Q is precisely

dim HomF[Q] ((U ⊗ xi ) ↑Q
x , 1 ) = dim HomF[Q∩H xi ] ((U ⊗ xi ), 1Q∩H xi ),
Q∩H i Q
1

1

1

applying Frobenius Reciprosity. This is at most dim(U ⊗ xi ) = dim U = a. The result now follows

immediately from (4.3.1).

Proof of Proposition 4.18. Set e :=

ad−am
RF (K ′ ) + am,

and let X be a finite generating set for M , consisting

of non-zero elements. Suppose that Y := {w0 , w1 , . . . , we } is a subset of X whose image under τ forms

a chain in T : Say τ (w0 ) 4 τ (w1 ) 4 . . . 4 τ (we ).

Consider now the vectors µ(w0 ), µ(w1 ), . . ., µ(we ): For 1 ≤ i ≤ e + 1 let Wi denote the K ′ -module

generated by µ(w0 ), . . ., µ(wi−1 ), and consider the series of K ′ -modules
0 =: W0 ≤ W1 ≤ . . . ≤ We+1

(4.4)

Suppose that Wi < Wi+1 for all i. Then the series (4.4) can be extended to give a K ′ -composition series
for V . Thus, Lemma 4.19 implies that at most am of the factors Wi+1 /Wi are trivial. Furthermore,
P
the rest have dimension at least RF (K ′ ). It follows that dim We+1 = e+1
i=1 dim Wi /Wi−1 ≥ am + (e +

1 − am)RF (K ′ ) > ad, which is a contradiction, since dim V = ad.
Thus, we must have µ(wi ) ∈ Wi for some i. In this case,
µ(wi ) =

i−1 X
X

λj,k µ(wj )k ,

j=0 k∈K ′

for some scalars λj,k . Moreover, the element
x :=

i−1 X
X

k τ (wj ) τ (wj )−1 τ (wi )

λj,k wj

j=0 k∈K ′

25

of M has the same leading summand as wi , by Lemma 4.15 Part (i) (see also Remark 4.17). Hence,
either x = wi and wi may be removed from X, or wi may be replaced in X by the element wi − x,

which has height strictly preceding wi in the full order 6. In this way, the resulting (modified) set X

still generates M . This procedure can only be carried out a finite number of times, and when it can
no longer be repeated, the (modified) generating set can have no more than e elements.
If χ ≥ e, then we are done, so assume that χ < e. Let v and w be elements of X whose images

τ (v) and τ (w) are comparable (with respect to 4) in T : Say τ (v) 4 τ (w). Suppose that µ(w) and

µ(v) lie in the same K-orbit of V , and let g ∈ K such that µ(w)g = µ(v). Since K is normal in

G, the leading summand of wg is µ(v) ⊗ τ (w). Thus, by replacing w with wg , we may assume that
−1 τ (w)

µ(v) = µ(w). Then, using Lemma 4.15 Part (i) again, we see that v τ (v)
summand as w. Write v

τ (v)−1 τ (w)

has the same leading

= x + µ(v) ⊗ τ (w), and w = y + µ(v) ⊗ τ (w), for x, y ∈ V , and let
−1 τ (w)

u = y − x. Then, we see that, as in the proof of [7, Lemma 5.2], either u = 0, and w = v τ (v)
−1 τ (w)

may be omitted from X, or u 6= 0, and w = u + v τ (v)

may be replaced in X by the element

u, which has height strictly preceding τ (w) in the full order 6. This way, the resulting set obtained
from X still generates M . The procedure outlined above can only be carried out a finite number of
times, and when it can no longer be repeated, the (modified) generating set can contain no more than
χ elements. This completes the proof.
Before proving Theorem 4.13, we note the following easy consequence of Dilworth’s Theorem ([15,
Theorem 1.1]):
Lemma 4.20. If a partially ordered set P has no chain of cardinality greater than k, and no antichain
of cardinality greater than l, then P cannot have cardinality greater than kl.
Proof of Theorem 4.13. Let T be a right transversal for H in G with full and partial orders 6 and 4,

as in Lemma 4.15. Now define a partial order on the elements of W as follows: First, for each t ∈ T ,

choose a full order on the elements of W of height t. Now, for w1 and w2 in W , say that w1 < w2 if

τ (w1 ) is less than τ (w2 ) in (T , 4), or if τ (w1 ) = τ (w2 ) but w1 precedes w2 in the full order chosen for
elements of height τ (w1 ).
Then τ : W → T is a poset homomorphism which takes incomparable elements to incomparable

elements, so no antichain of its domain can have cardinality greater than ω
e (s), by Lemmas 4.1 and

4.15 Part (ii). Let X be a generating set for M with the properties guaranteed by Proposition 4.18.
Then no chain in X can have more than min{ ad−am
RF (K ′ ) + am, χ} elements. Lemma 4.20 then implies
that
|X| ≤ min







ad − am
ad − am
bs
√
,
+ am, χ ω
e (s) ≤ min
+ am, χ
RF (K ′ )
RF (K ′ )
log s

where the second inequality follows from Theorem 1.3. If s = pt for p prime, then
|X| ≤ min



ad − am
+ am, χ
RF (K ′ )

$

%
bpt
p
,
t(p − 1)

again by Lemma 4.20 and Theorem 1.3. This completes the proof.

26

4.3.2

Induced modules for finite groups: The general case

In this section, we prove a weaker form of Theorem 4.13 for general finite groups (i.e. those G for which
GΩ does not necessarily contain a soluble transitive subgroup). We retain the notation introduced at
the beginning of Section 4.3.
We begin with a definition. Recall the definitions of ω
e (s), sp , and lpp (s) from Definitions 1.4 and

1.5.

Definition 4.21. For a prime p, set








bs
s


q
E(s, p) := min
,
and Esol (s, p) := min {e
ω (s), sp }

lpp (s/sp ) 
(p − 1) log p sp

k
j q
where we take bs/ (p − 1) logp sp to be ∞ if sp = 1.

Proposition 4.22. Let p be prime. Then Esol (s, p) ≤ E(s, p).


Proof. By Theorem 1.3 we have ω
e (s) ≤ √ bs
. Also, it is clear that sp ≤
(p−1) logp sp

s
lpp (s/sp ) .

The

result follows.

Remark 4.23. For any finite group G and any G-module M , dG (M ) is bounded above by χ(G, M ∗ ).
For the remainder of this section, we will make a further assumption: that the field F has characteristic p > 0. We are now ready to state and prove the main result of this section.
Theorem 4.24. For a prime q 6= p, let Pq be a Sylow q-subgroup of G. Also, let P ′ be a maximal

p′ -subgroup of G. Let M be a submodule of the induced module W = V ↑G
H.
(i) If G is soluble, then
dG (M ) ≤ min




ad − aχ(P ′ ∩ K, Ω1 )
′
′
∗
+ aχ(P ∩ K, Ω1 ), χ(P ∩ K, V ) sp .
RF (P ′ ∩ K)

(ii) Let N be a subgroup of G such that N Ω is soluble, and let si , 1 ≤ i ≤ t, be the sizes of the orbits
of N on Ω. Then

(a) We have


ad − aχ(N ∩ P ′ ∩ K, Ω1 )
+ aχ(N ∩ P ′ ∩ K, Ω1 ),
RF (N ∩ P ′ ∩ K)
 X
t
′
∗
ω
e (si ).
χ(N ∩ P ∩ K, V ) ×

dG (M ) ≤ min

i=1

(b) If N is soluble, and PN′ is a p-complement in N , then


ad − aχ(PN′ ∩ K, Ω1 )
+ aχ(PN′ ∩ K, Ω1 ),
RF (PN′ ∩ K)
 X
t
Esol (si , p).
χ(PN′ ∩ K, V ∗ ) ×

dG (M ) ≤ min

i=1

27

(iii) dG (M ) ≤ min

n

ad−aχ(Pq ∩K,Ω1 )
RF (Pq ∩K)

(iv) Assume that sp > 1. Then

o
+ aχ(Pq ∩ K, Ω1 ), χ(Pq ∩ K, V ∗ ) s/sq .

dG (M ) ≤ min



%
$
bs
ad − am
p
.
+ am, χ(K, V ∗ )
RF (K ′ )
log sp

Proof. The proof is based on the idea of Lucchini et al. used in the proof of [28, Lemma 4]. Let Q be
a subgroup of G, and choose a full set {x1 , x2 , . . . , xt } of representatives for the (H, Q)-double cosets

in G. Also, for 1 ≤ i ≤ t, put si := |Q : Q ∩ H xi | (note that, by H xi , we mean, as usual, the conjugate

subgroup x−1
i Hxi ). By Mackey’s Theorem we have

W ↓Q = (V ↑G
H ) ↓Q =

t
M

Vx i

(4.5)

i=1

Q
where Vxi ∼
= (V ⊗ xi ) ↑Q∩H xi . Comparing dimensions of the left and right hand side of (4.5) above,

we get

ads = dim W =

t
X
i=1

so that
G.

Pt

i=1 si

ad|Q : Q ∩ H xi | = ad

t
X

si

i=1

= s. Clearly, the si represent the sizes of the orbits of Q on the right cosets of H in

Next, for 1 ≤ i ≤ t, set Vi := Vx1 ⊕ Vx2 ⊕ . . . ⊕ Vxi . Then, we have a chain 0 = V0 ≤ V1 ≤ . . . ≤

Vt = W of Q-submodules of W . This allows us to define the chain of Q-modules 0 = M0 ≤ M1 ≤

. . . ≤ Mt = M , where Mi := M ∩ Vi . Furthermore, in this case, the quotient Mi /Mi−1 is (isomorphic

to) a Q-submodule of Vxi . Hence

dG (M ) ≤ dQ (M ) ≤

t
X

dQ (Mi /Mi−1 ).

(4.6)

i=1

x

H i . Hence, Mackey’s Theorem
Note that V ⊗ xi is isomorphic to an induced module (U ⊗ xi ) ↑H
xi
1

implies that (V ⊗ xi ) ↓Q∩K is isomorphic to a direct sum
(V ⊗ xi ) ↓Q∩K ∼
=

M

Uxi,j ,

j

Q∩K
where Uxi,j ∼
= (U ⊗ xi,j ) ↑
xi,j is an induced module for Q ∩ K, and
Q∩K∩H
1
P
xi,j
| = |H xi : H1xi | = d.
j |Q ∩ K : Q ∩ K ∩ H1

28

(4.7)

Suppose that (|Q|, p) = 1. Then each Vxi is a semisimple F[Q]-module, so
dQ (Mi /Mi−1 ) ≤ dQ (Vxi )
≤ dQ∩H xi (V ⊗ xi )
≤ dQ∩K (V ⊗ xi )
X
≤
dQ∩K (Uxi,j )
j

≤

X

min

j



x

a|Q ∩ K : Q ∩ K ∩ H1 i,j | − a
+ a, χ(Q ∩ K,
RF (Q ∩ K)


[Uxi,j ] )

X a|Q ∩ K : Q ∩ K ∩ H xi,j | − a
X
1
≤ min
+ a,
χ(Q ∩ K,

RF (Q ∩ K)
j
j

[Uxi,j )]∗ )


ad − aχ(Q ∩ K, Ω1 )
∗
+ aχ(Q ∩ K, Ω1 ), χ(Q ∩ K, V )
= min
RF (Q ∩ K)
∗

The fourth inequality above follows from (4.7), while the fifth follows from Corollary 4.8 and Remark
4.23. Thus
dG (M ) ≤ min




ad − aχ(Q ∩ K, Ω1 )
∗
+ aχ(Q ∩ K, Ω1 ), χ(Q ∩ K, V ) t
RF (Q ∩ K)

(4.8)

by (4.6).
Write sp := pβ and sq := q α . Also, write s = pβ q α k and |H| = pδ q γ l, where |H|p = pδ , |H|q = q γ .

We are now ready to prove the theorem.

(i) Suppose that G is soluble, and take Q := P ′ to be a p-complement in G. Then |Q| = q α+γ kl.
P
Hence, si = |Q : Q ∩ H xi | ≥ q α k = s/sp . Part (i) now follows from (4.8), since s = ti=1 si ≥
ts/sp .

(ii) Take Q := N . By Theorem 4.13, we have


ad − aχ(Q ∩ P ′ ∩ K, Ω1 )
+ aχ(Q ∩ P ′ ∩ K, Ω1 ),
RF (Q ∩ P ′ ∩ K)

′
∗
χ(Q ∩ P ∩ K, V ) ω
e (si ).

dQ (Mi /Mi−1 ) ≤ min

Part (a) of (ii) now follows from (4.6). Next, assume that N is soluble, with a p-complement
PN′ . Then


ad − aχ(Q ∩ P ′ ∩ K, Ω1 )
+ aχ(Q ∩ P ′ ∩ K, Ω1 ),
RF (Q ∩ P ′ ∩ K)

′
∗
χ(Q ∩ P ∩ K, V ) (si )p

dQ (Mi /Mi−1 ) ≤ min

29

by Part (i). Also, PN′ = N ∩ P ′ for some maximal p′ -subgroup P ′ of G, so Part (b) follows from
(4.6) by combining the above with Part (ii)(a).

(iii) In the general case, take Q := Pq . Then |Q| = q α+γ , so si = |Q : Q ∩ H xi | ≥ q α . Also,
P
s = ti=1 si ≥ tq α = tsq . Part (iii) then follows from (4.8).

(iv) Here, we have β > 0 since sp > 0. Let P be a Sylow p-subgroup of G, and set Q = KP . Then
si = |Q : Q ∩ H xi | = |QH xi |/|H xi | ≥ |P H xi |/|H xi | = |P : P ∩ H xi | ≥ pβ , for each i. Since

K ≤ coreQ (Q ∩ H xi ), we have χ(coreQ (Q ∩ H xi ), (V ⊗ xi )∗ ) ≤ χ(K, V ∗ ) =: χ for each i. Then
(4.6) and Theorem 4.13 give

t
X



ad − am
+ am, χ
RF (K ′ )



bs
√ i
min
dG (M ) ≤
log si
i=1



t
X
ad − am
bsi
√
min
≤
+ am, χ
RF (K ′ )
β
i=1
%

 $X
t
ad − am
bsi
√
≤ min
+ am, χ
RF (K ′ )
β
i=1



bs
ad − am
√
+ am, χ
= min
′
RF (K )
β



This proves (iv).

Since

ad−f
e

+ f ≤ ad for positive integers e and f , the following corollary is immediate.

Corollary 4.25. Let M be a submodule of W . Also, let q, Pq and P ′ be as in Theorem 4.24. Then
(i) If G is soluble, then dG (M ) ≤ min {ad, χ(P ′ ∩ K, V ∗ )} sp .
(ii) Let N be a subgroup of G such that N Ω is soluble, and let si , 1 ≤ i ≤ t, be the sizes of the orbits
of N on Ω. Then

(a) We have dG (M ) ≤ min {ad, χ(N ∩ P ′ ∩ K, V ∗ )}

Pt

e (si ).
i=1 ω

(b) If N is soluble, and PN′ is a p-complement in N , then

t
X

Esol (si , p).
dG (M ) ≤ min ad, χ(PN′ ∩ K, V ∗ )
i=1

(iii) dG (M ) ≤ min {ad, χ(Pq ∩ K, V ∗ )} s/sq .


bs
∗
(iv) dG (M ) ≤ min {ad, χ(K, V )} √
.
log sp

We also record the following, which is an immediate consequence of Corollary 4.25. Note that
Theorem 1.6
Corollary 4.26. Define E ′ to be Esol if GΩ contains a soluble transitive subgroup, and E ′ := E
otherwise. Let M be a submodule of W . Then dG (M ) ≤ adE ′ (s, p).
30

Note that Theorem 1.6 follows from Corollary 4.26. Using the definition of E(s, p), and Lemma
2.17, we also deduce the following.
Corollary 4.27. Let M be a submodule of W , and fix 0 < α < 1.
$ q %
bs 1
√ α
log s

(i) If sp ≥ sα , then dG (M ) ≤ adE(s, p) ≤ ad

(ii) If sp ≤

sα ,

(iii) We have

then dG (M ) ≤ adE(s, p) ≤ ad



1
s
1−α
′
c log s

;



;

j
k

 2ads
′
c log s ,
dG (M ) ≤ adE(s, p) ≤ j
√ k

2
 adbs
√
,
log s

if 2 ≤ s ≤ 1260,
if s ≥ 1261.

Proof. Part (i) follows immediately from the definition of E(s, p), while Part (ii) follows from the
definition and Lemma 2.17. Finally, set α := 1/2. Then
√
2ads
adbs 2
≤ √
c′ log s
log s
for s ≥ 1261, so Part (iii) also follows.
The following is also immediate, from Part (ii) of Theorem 4.24.
Corollary 4.28. Let M be a submodule of W . If G contains a soluble subgroup N , acting transitively
on Ω, then
dG (M ) ≤ min




ad − aχ(PN′ ∩ K, Ω1 )
′
′
∗
+ aχ(PN ∩ K, Ω1 ), χ(PN ∩ K, V )
RF (PN′ ∩ K)

× E(s, p)
where PN′ is a p-complement in N .

4.4

An application to induced modules for bottom heavy groups

The proofs of the main results of this paper will usually only require the bounds on dG (M ) from
Corollary 4.25. For a specific case of the proof of Theorem 1.7 however, we will need the stronger
bounds provided by Theorem 4.24. This case is the ‘bottom heavy case’, which we will now define.
Throughout, we retain the notation introduced at the beginning of Section 4.3. In particular, H is a
subgroup of G of index of index s ≥ 2, H1 is a subgroup of H of index d ≥ 1, Ω is the set of right

cosets of H in G, Ω1 is the set of right cosets of H1 in H, and K := KerG (Ω). Note that we also
continue to assume that the field F has characteristic p > 0.
Definition 4.29. Assume that K Ω1 , viewed as a subgroup of Sym (d), contains Alt(d). Then we say
that the triple (G, H, H1 ) is bottom heavy.
Before stating the main result of this section, we introduce Vinogradov notation: we will write
A≪B
31

to mean A = O(B). The main result can now be stated as follows.
Proposition 4.30. Assume that d ≥ 5 and that (G, H, H1 ) is bottom heavy. Let M be a submodule
of W . Then

(i) dG (M ) ≤ 2as, and;
(ii) If sp > 1, then dG (M ) ≪ √ as

log sp

.

Before proving Proposition 4.30, we require the following:
Proposition 4.31. Assume that (G, H, H1 ) is bottom heavy and that d ≥ 5. Choose K ′ to be a
subgroup of K minimal with the property that K ′Ω1 ∼
= Alt(d). Then a K ′ -composition series for
V ↓K ′ has at most 2a factors isomorphic to the trivial K ′ -module.
Proof. By the minimality of K ′ , we have C := coreH (H1 ) ∩ K ′ ≤ Φ(K ′ ), and hence C is soluble. Let

E be a subgroup of K ′ containing C such that E/C is soluble and, viewed as a subgroup of Sym (d),
has at most two orbits, such that each orbit is of p′ -length (such a subgroup exists by Lemma 2.9).
Then E is soluble, so we may choose a p-complement F in E. Then F/F ∩ C also has at most two

orbits (and each F -orbit has p′ -length).

′
Next, consider the F -module X := V ↓F ∼
= U ↑H
H1 ↓F . Since F ≤ K , it suffices to prove that X

has at most 2a trivial composition factors. To see this, note that since F has at most two orbits on
Ω1 (i.e. the cosets of H1 in H), represented by x1 and x2 , say, Mackey’s Theorem yields
X∼
= X1 ⊕ X2 or X ∼
= X1
where Xi ∼
= (U ⊗ xi ) ↑FF ∩H xi . Now, since F has p′ -order, Xi is a semisimple F -module. Hence, the
1

number of trivial factors in an F -composition series for Xi is precisely the number of trivial summands
of Xi , which is
dim HomF[F ] (Xi , 1F ),
where 1F denotes the trivial F -module. By Frobenius Reciprosity, this is equal to
dim HomF[F ∩H xi ] (U ↓F ∩H xi , 1F ∩H xi ) ≤ dim U = a.
1

1

1

The claim follows.
Proof of Proposition 4.30. Choose K ′ to be a subgroup of K minimal with the property that K ′Ω1 ∼
=
Alt(d). Then
coreH (H1 ) ∩ K ′ ≤ Φ(K ′ ).

(4.9)

Hence, since
Alt(d) ∼
= K ′Ω ∼
= K ′ /coreH (H1 ) ∩ K ′ ,
Proposition 4.9 applies: RF (K ′ ) ≥ R(Alt(d)). Note also that m ≤ 2 by Lemma 2.9. Since d ≪

R(Alt(d)) (see [22, Proposition 5.3.7]), Part (ii) now follows from Theorem 4.24 Part (iv).
32

We now prove (i). It follows from Lemma 2.9 that K ′ has a subgroup N such that N Ω1 is soluble
and has at most 2 orbits. Furthermore, each orbit has p′ -length. Also, N is soluble, by (4.9).
We now want to apply Corollary 4.25 Part (ii)(b), with (G, H, H1 , V, Ω) replaced by (H, H1 , H1 , U, Ω1 )
(also, (a, s, d) is replaced by (a, d, 1)): let di , for i ≤ 2, denote the lengths of the N Ω1 orbits. Then
Esol (di , p) ≤ (di )p = 1,
so Esol (di , p) = 1. Hence for each H-submodule M ′ of the induced module V = U ↑H
H1 , we have
′

dH (M ) ≤ a

t
X
i=1

Esol (di , p) ≤ 2a.

Since M is a submodule of
U

∼
↑G
H1 =

V

∼
↑G
H=

s
X
i=1

V ⊗ ti

where each V ⊗ ti is isomorphic, as an H-module, to V , the result now follows.

5

Minimal generation of transitive permutation groups

In this section, we restate and prove the first main result of this paper, which is stated as Theorem
1.1 in Section 1. The theorem follows in the primitive case from Theorem 2.11, so this section deals
predominantly with the case when G ≤ Sym(n) is imprimitive. In this case, G is a large subgroup
of a wreath product R ≀ S, where R is primitive of degree r ≥ 2, S is transitive of degree s ≥ 2, and

n = rs. Due to the nature of our bounds, the most difficult cases to deal with are when R = Sym(2)

or R = Sym(4), i.e. when G has a minimal block of cardinality either 2 or 4. (Essentially, this is
because Sym(2) and Sym(4) have large composition lengths relative to their degree.) We deal with
the Sym(4) case in Corollary 5.11; the idea being that we can use the transitive action of the Sylow
3-subgroup in Sym(4) on the non-identity elements of the Klein 4-group V E Sym(4) to reduce the
contribution of V to our bounds (this is the primary reason we include the invariant χ in our bounds
in Section 4).
However, no such option is available to us when R ∼
= Sym(2), since Sym(2) is abelian. If G has
another minimal block, of cardinality larger than 2, then we can avoid the problem by using this block
instead. However, we cannot do this if all minimal blocks for G have cardinality 2, so assume that
this is the case. Then, as we will prove in Section 5.2 below, we have d(G) ≤ E(s, 2) + d(S). Now,

since we just need to bound d(S), we apply the same methods to the transitive group S ≤ Sym(s).

Apart from finitely many cases, our methods yield the upper bound we want: the only problems

occur when we “repeatedly get” blocks of cardinality 2. This is encapsulated in the following nonstandard definition.
Definition 5.1. Let G be a transitive permutation group, and let
X := (R1 , R2 , . . . , Rt )

33

be a tuple of primitive components for G, where each Ri has degree ri ≥ 2. Define
blX,2 (G) := min {i : ri 6= 2} − 1, and
bl2 (G) := min {blX,2 (G) : X a tuple of primitive components for G} .
We call bl2 (G) the 2-block number of G.
Alternatively, the 2-block number of a transitive permutation group G can be defined inductively
as follows: if G is primitive, or if G is imprimitive with a minimal block of cardinality greater than
2, then set bl2 (G) := 0. Otherwise, G is imprimitive and all minimal blocks for G have cardinality 2.
Let ∆ be such a minimal block, and let Γ := {∆g : g ∈ G} be the set of G-translates of ∆. Also, let
K := KerG (Γ). Then define bl2 (G) := 1 + bl2 (G/K).

For example, a transitive 2-group G of degree 2k will have bl2 (G) = k. In other words, any tuple
of primitive components for G will consist entirely of Sym(2)s. This is because for any prime p, any
minimal block of any transitive p-group has cardinality p.
Remark 5.2. If bl2 (G) ≥ 1, then G has a block of size 2bl2 (G) , by Remark 2.4.
We can now restate Theorem 1.1 more precisely as follows.
Theorem 5.3. Let G be a transitive permutation group of degree n ≥ 2. Then
j
k
p
cn
(1) d(G) ≤ √log
,where
c
:=
1512660
log (219 15)/(219 15) = 0.920581 . . ..
n

(2) d(G) ≤

j

√c1 n
log n

k

, where c1 :=

√

3/2 = 0.866025 . . ., unless each of the following conditions hold:

(i) n = 2k v, where v = 5 and 17 ≤ k ≤ 26, or v = 15 and 15 ≤ k ≤ 35;
(ii) G contains no soluble transitive subgroups; and
(iii) bl2 (G) ≥ f , where f is specified in the middle column of Table A.2 (see Appendix A).
In these exceptional cases, the bounds for d(G) in Table A.2 hold.
Recall that by “log”, we always mean log to the base 2. The following is immediate from Theorem
5.3. Note also that Corollary 1.2 follows immediately from Theorem 5.3.
As can be seen from the proof of Theorem 5.3, and the statement of the theorem itself, the cases
when bl2 (G) is large are the most difficult to deal with using our methods. We believe that the finite
number of exceptions given in Theorem 5.3 Part (2) are not exceptions at all, that is, we believe that
√
the bound d(G) ≤ ⌊c1 n/ log n⌋ should hold for all n and all G.

Note also that, as shown in [21], the bounds in our results are of the right order. Moreover, the
√
infimum of the set of constants c satisfying d(G) ≤ cn/ log n, for all soluble transitive permutation

groups G of degree n ≥ 2, is the constant c1 in Theorem 5.3, since d(G) = 4 when n = 8 and
G ∼
= D8 ◦ D8 . We conjecture that the best “asymptotic” bound, that is, the best possible upper
√
bound when one is permitted to exclude finitely many cases, is d(G) ≤ ⌊e
cn/ log n⌋, where e
c is some
p
constant satisfying b/2 ≤ e
c < b = 2/π (see Example 6.10 for more details).
In Section 5.1 we discuss an application of the results of Section 4 to wreath products. We reserve

Section 5.2 for the proof of Theorem 5.3.

34

5.1

An application of the results in Section 4 to wreath products

We first make the following easy observation.
Proposition 5.4. Let A = T1 × T2 × . . . × Tf , where each Ti is isomorphic to the nonabelian finite
simple group T . Suppose that M ≤ A is a subdirect product of A, and suppose that M ′ E M is also a
subdirect product of A. Then M ′ = M .

Proof. We prove the claim by induction on f , and the case f = 1 is trivial, so assume that f > 1.
Since M is subdirect, each M ∩ Ti is normal in Ti . If M = A, then since the only normal subgroups
Q
of A are the groups i∈Y Ti , for Y ⊆ {1, . . . , f }, the result is clear. So assume that M ∩ Ti = 1 for
Q
some i. Then M ′ ∩ Ti = 1, and M ′ Ti /Ti and M Ti /Ti are subdirect products of j6=i Tj . It follows,
using the inductive hypothesis, that M ′ Ti = M Ti . Hence M ′ = M , since M ∩ Ti = 1, and the proof

is complete.

We also need the following result of Lucchini and Menegazzo.
Theorem 5.5 ([25] and [27]). Let L be a proper minimal normal subgroup of the finite group G.
Then d(G) ≤ d(G/L) + 1. Furthermore, if L is the unique minimal normal subgroup of G, then

d(G) ≤ max {2, d(G/L)}.

We will now fix some notation which will be retained for the remainder of the section.
• Let R be a finite group (we do not exclude the case R = 1).
• Let S be a transitive permutation group of degree s ≥ 2.
• Let G be a large subgroup of the wreath product R ≀ S (see Definition 2.3).
• Write B := R(1) × R(2) × . . . × R(s) for the base group of R ≀ S.
• write π : G → S for the projection homomorphism onto the top group.
• Let H := NG (R(1) ) = π −1 (StabS (1)).
• Let Ω := H\G.
• Let K := G ∩ B = coreG (H) = KerG (Ω).
Recall that for a subgroup N of R, BN ∼
= N s denotes the direct product of the distinct S-conjugates
of N . In particular, if N E R, then BN E R ≀ S. Throughout, we will view R as a subgroup of B by

identifying R with R(1) . We also note that
• |G : H| = s; and
• S = GΩ .

In particular, the notation is consistent with the notation introduced at the beginning of Section 4.3.
Remark 5.6. The results in this section will be obtained by applying the results in Section 4 with
H = H1 and d = 1 (see the notation introduced at the beginning of Section 4.3).
35

Remark 5.7. If R is a transitive permutation group, acting on a set ∆, then G is an imprimitive
permutation group acting on the set ∆ × {1, 2, . . . , s}, and H = StabG ((∆, 1)). Furthermore H ∆ = R,
since G is large (see Remark 2.7).

Our strategy for proving Theorem 5.3 can now be summarised as follows:
Step 1: Show that K is “built” from induced modules for G, and non-abelian G-chief factors.
Step 2: Derive bounds on d(G) in terms of the factors from Step 1 and d(S).
Step 3: Use Theorem 5.5, together with the results from Section 4, to bound the contributions from
the factors in Step 1 to the bound from Step 2.
Step 4: Use induction to bound d(S).
We begin with Step 1.
Lemma 5.8. Suppose that R > 1 and that 1 := N0 ≤ N1 ≤ . . . ≤ Ne = R is a normal series for

R, where each factor is either elementary abelian, or a nonabelian chief factor of R. Consider the
corresponding normal series 1 := G ∩ BN0 ≤ G ∩ BN1 ≤ . . . ≤ G ∩ BNe = G for G. Let Vi := Ni /Ni−1
and Mi := G ∩ BNi /G ∩ BNi−1 .

(i) If Vi is elementary abelian, then Mi is a submodule of the induced module Vi ↑G
H.
(ii) If Vi is a nonabelian chief factor of R, then Mi is either trivial, or a nonabelian chief factor of
G.
Proof. Assume first that Vi is elementary abelian, of order pa say. Then BNi /BNi−1 is a module for
G of dimension as = a|G : H| over the finite field of order p. Furthermore, BNi /BNi−1 is generated,
as a G-module, by the H-module Vi . It now follows from [1, Corollary 3, Page 56] that BNi /BNi−1 is
isomorphic to the induced module Vi ↑G
H . This proves (i).

Next, suppose that Vi is a nonabelian chief factor of R. Write bars to denote reduction modulo

BNi−1 . Then G is a large subgroup of the wreath product R ≀ S, and Ni is a nonabelian minimal
normal subgroup of R. So we just need to prove that G ∩ BNi is either trivial or a nonabelian minimal

normal subgroup of G. To this end, consider the projection maps
ρj : NG (R(j) ) → R(j)

defined in (2.1.1). Suppose that M is a normal subgroup of G contained in G ∩ BNi . Then M ≤
NG (R(1) ), and hence ρ1 (M ) is a normal subgroup of ρ1 (NG (R(1) )) = R(1) contained in the minimal

normal subgroup of R(1) corresponding to Ni . If ρ1 (M ) = 1 then ρj (M ) = 1 for all j, since π(G) = S
is transitive. Hence, in this case, we have M = 1. Otherwise, ρ1 (M ) ∼
= Ni , and M is a subdirect
product of s copies of Ni . In this case, since a minimal normal subgroup of a finite group is a direct
product of simple groups, we must have M = G ∩ BNi by Proposition 5.4. Thus, if G ∩ BNi is

non-trivial, then G ∩ BNi is a nonabelian minimal normal subgroup of G, as required.

36

For the remainder of this section, suppose that 1 := N0 ≤ N1 ≤ . . . ≤ Ne = R is a chief series for

R, and let Vi := Ni /Ni−1 and Mi := G ∩ BNi /G ∩ BNi−1 . If Vi is abelian we will also write |Vi | = pai i ,

for pi prime.

We now have Step 2.
Corollary 5.9. We have
d(G) ≤

X

dG (Mi ) + cnonab (R) + d(S)

Vi abelian

Proof. We will prove the corollary by induction on |R|. If |R| = 1 then the bound is trivial, since
G∼
= S in that case, so assume that |R| > 1, and note that
G/M1 is a large subgroup of (R/V1 ) ≀ S.

(5.1)

Suppose first that V1 is abelian. Then M1 is a G-module, so
d(G) ≤ dG (M1 ) + d(G/M1 ).
Since cnonab (R) = cnonab (R/V1 ), (5.1) and the inductive hypothesis give the result.
So we may assume that V1 is nonabelian. Then M1 is either trivial or a minimal normal subgroup
of G, by Lemma 5.8 Part (ii). Hence, d(G) ≤ d(G/M1 ) + 1 by Theorem 5.5. The result now follows,

again from (5.1) and the inductive hypothesis.

Before stating our next corollary, we refer the reader to Definition 4.21 for a reminder of the
definitions of the functions E and Esol . The next two corollaries deal with Step 3.
Corollary 5.10. Define E ′ to be Esol if S contains a soluble transitive subgroup, and E ′ := E
otherwise. Then
(i) d(G) ≤

P

Vi abelian

ai E ′ (s, pi ) + cnonab (R) + d(S).

(ii) Suppose that |R| = 2 and s = 2m q, where q is odd, and that S has a tuple of primitive components

X = (R2 , . . . , Rt ), where blX,2 (S) ≥ 1. Let Γ be a full set of blocks for S of size 2blX,2 (S) , and
set Se := S Γ . Then
blX,2 (S)
X
e
d(G) ≤
E ′ (2m−i q, 2) + d(S).
i=0

(iii) Suppose that |R| = 2 and s = 2m 3, and that S contains no soluble transitive subgroups. Then by
Corollary 3.12 there exists a Mersenne prime p1 = 2a − 1 and a triple of integers (e, t1 , t), with
e ≥ 1, and t ≥ t1 ≥ 0, such that

(1) m = ea + t, and;
(2) There exists a subgroup N of G, such that N Ω is soluble and has 2e+t1 orbits, with
them of length

3pk1

×

2t−t1 ,

for each 0 ≤ k ≤ e.

37

e  t1
k 2

of

Here, we have
d(G) ≤

e
X

t−t1

2

k=0

 
e
Esol (3pk1 2t1 , 2) + d(S).
k

Proof. By Corollary 5.9, we have
d(G) ≤

X

dG (Mi ) + cnonab (R) + d(S).

Vi abelian

Now, by Corollary 4.26, dG (Mi ) ≤ ai E ′ (s, pi ). This proves (i).

To prove (iii) first note that, by Corollary 3.12, and as mentioned in the statement of (iii), there

exists a Mersenne prime p1 := 2a − 1, and a triple (e, t1 , t), with e ≥ 1, and t ≥ t1 ≥ 0, such that
(i) m = ea + t, and;
(ii) There exists a subgroup N of G, such that N Ω is soluble and has 2e+t1 orbits, with
them of length

3pk1

×

2t−t1 ,

for each 0 ≤ k ≤ e.

e  t1
k 2

of

Note that, since |R| = 2, the base group K ≤ Rs of G is soluble. Hence, since N Ω ∼
= N/N ∩ K is

soluble, it follows that N itself is also soluble. Corollary 4.25 Part (ii)(b) (with ad = 1) then implies
that
dG (M1 ) ≤

e
X

2t1

k=0

 
e
Esol (3pk1 2t−t1 , 2)
k

Since |R| = 2, we have d(G) ≤ dG (M1 ) + d(S), and the result follows.
Finally, we prove Part (ii). We will show that
blX,2 (S)

d(S) ≤

X
i=1

e
E(2m−i q, 2) + d(S)

(5.2)

by induction on blX,2 (S). The result will then follow, since d(G) ≤ E ′ (2m q, 2) + d(S) by Part (i).

Now, by hypothesis, S has a tuple of primitive components X = (R2 , . . . , Rt ). Also, |R2 | = 2 since

blX,2 (S) ≥ 1. Hence, by Theorem 2.5, S is a large subgroup of a wreath product R2 ≀ S2 , where either

S2 = 1, or S2 is a transitive permutation group of degree 2m−1 q, with a tuple Y := (R3 , . . . , Rt ) of
primitive components. If S2 = 1 then the result follows, since s = 4 and Se = 1 in that case. So

assume that S2 > 1. By Part (i), we have

d(S) ≤ E ′ (2m−1 q, 2) + d(S2 )

(5.3)

If blX,2 (S) = 1 then S2 = Se and (5.2) follows from (5.3). So assume that blX,2 (S) > 1. Then
PblY,2 (S2 )
blY,2 (S2 ) = blX,2 (S) − 1 ≥ 1. The inductive hypothesis then yields d(S2 ) ≤ i=1
E(2m−1−i q, 2) +
P
e = blX,2 (S) E(2m−i q, 2) + d(S).
e The bound (5.2) now follows immediately from (5.3), which
d(S)
i=2

completes the proof.

The next corollary will be key in our proof of Theorem 5.3 when G is imprimitive with minimal
block size 4.

38

Corollary 5.11. Assume that R = S4 or R = A4 . Define E ′ to be Esol if S contains a soluble
transitive subgroup, and E ′ := E otherwise. Then
d(G) ≤ E ′ (s, 2) + min



√

bs
s
,
log s2 s3



+ E ′ (s, 3) + d(S).

Proof. Let ∆ := {1, 2, 3, 4}, so that R is transitive on ∆. We have V1 ∼
= 22 , V2 ∼
= 3, and V3 ∼
= 2 if
∆
∆
∆
R∼
= S4 . Since K is a normal subgroup of H = R (see Remark 5.7), K is isomorphic to either 22 ,
A4 , or S4 . In the first two cases M3 is trivial, so
d(G) ≤ dG (M1 ) + dG (M2 ) + d(S) ≤ 2E ′ (s, 2) + E ′ (s, 3) + d(S)
by Corollaries 5.9 and 4.26. So assume that K ∆ ∼
= S4 . Then a Sylow 3-subgroup P3 of K ∆ acts
transitively on the non-identity elements of V1 . Thus, χ(P3 ∩ K, V1∗ ) = 1, so
dG (M1 ) ≤ min



s
bs
√
,
log s2 s3



by Corollary 4.25 Parts (iii) and (iv), with (p, q) := (2, 3). The result follows.

5.2

The proof of Theorem 5.3

In this section, we prove Theorem 5.3. First, we deal with Step 4: the inductive step. As mentioned
at the beginning of Section 5, the cases where bl2 (G) is large are the most difficult to deal with using
our methods. In these cases, we have d(G) ≤ E(s, 2) + d(S) and usually the bounds on d(S) which

come from the inductive hypothesis then suffice to prove the theorem. However in some small cases

the inductive hypothesis does not suffice, and we have to work harder. These cases, of which there are
finitely many, are the subject of Appendix A, and include both the exceptional cases from Theorem
5.3 (Table A.2), and some additional cases which have a large 2-part (Table A.1). The purpose of
Lemma 5.12 is to prove that the bounds in Appendix A hold.
Throughout this section, we retain the same notation as introduced immediately following Theorem
5.5, with one additional assumption: that R is a primitive permutation group of degree r ≥ 2. Hence,

G is a transitive permutation group of degree n := rs, and Remark 5.7 applies. Also, set E ′ to be
Esol if S contains a soluble transitive subgroup, and E ′ := E otherwise.
Recall also that pai i denote the orders of the abelian chief factors of R, for pi prime.
Lemma 5.12. Assume that Theorem 5.3 holds for degrees less than n. Then
(i) The bounds in Table A.1 (see Appendix A) hold, and;
(ii) If n and f are as in Table A.2, and either
(a) G contains a soluble transitive subgroup; or
(b) bl2 (G) < f ,
√
then d(G) ≤ ⌊c1 n/ log n⌋, where c1 =

√

3
2 .

(iii) If n and f are as in Table A.2, and
39

(a) G contains no soluble transitive subgroup; and
(b) bl2 (G) ≥ f ,
then, the bounds in Table A.2 (Appendix A) hold.
Proof. We first recall some bounds which will be used throughout the proof. We have
d(G) ≤ s⌊log r⌋ + d(S), if r ≥ 4; and
X
d(G) ≤
ai E ′ (s, pi ) + cnonab (R) + d(S).

(5.4)
(5.5)

i

These bounds follow from Corollary 2.12 and Corollary 5.10 Part (i) respectively.
To bound d(S) above, we use the database of transitive groups of degree up to 32 in MAGMA
([10]) if 2 ≤ s ≤ 32; otherwise, we use either the previous rows of Tables A.1 and A.2; or the bound
√
d(S) ≤ ⌊c1 s/ log s⌋ (from the hypothesis of the lemma) if s is not in Tables A.1 or A.2.
We will first prove (i) and (ii).

(i) and (ii) The values of n occurring in Table A.1 are n = 2m for 6 ≤ m ≤ 11; n = 2m+1 3 for

3 ≤ m ≤ 19; n = 2m 5 for 3 ≤ m ≤ 16; and n = 2m 15 for 2 ≤ m ≤ 14. We distinguish a number

of cases. Recall that n = rs. Throughout, we define E ′′ := Esol if s is of the form s = 2m ,

and E ′′ := E otherwise. (Note that a transitive group of prime power degree always contains a
soluble transitive subgroup.)
1. r > 16. Then d(G) ≤ s⌊log r⌋ + d(S) by (5.4). Combining this with the bounds on d(S)
described above gives the required for each n in Table A.1, and each possible pair (r, s)
with r > 16 and n = rs, except when (n, r, s) = (3145728, 24, 131072). However, each
primitive group of degree 24 is either simple, or has a simple normal subgroup of index 2
(using the MAGMA [5] database). Hence, in this case, (5.5), together with the hypothesis
√
of the lemma, gives d(G) ≤ E(s, 2) + 1 + ⌊c1 s/ log s⌋ = 52895. This gives us what we

need.

2. r = 2. We distinguish two sub-cases.
(a) S contains a soluble transitive subgroup. Then d(G) ≤ Esol (s, 2) + d(S) by (5.5), and
this, together with the bounds on d(S) described above gives the bounds in Table A.1

in each of the relevant cases.
(b) S contains no soluble transitive subgroups. Then s is not of the form s = 2m . We
distinguish each of the relevant cases.
i s = 2m 3, for some 3 ≤ m ≤ 19. By using the MAGMA database [5], we see
that each transitive permutation group of degree 24 contains a soluble transitive

subgroup, so we must have s = 2m 3 ≥ 48. In particular, 4 ≤ m ≤ 19. By Corollary

5.10 Part (iii) there exists a Mersenne prime p1 = 2a − 1 and a triple of integers
(e, t1 , t), with e ≥ 1, and t ≥ t1 ≥ 0, such that m = ea + t, and
d(G) ≤

e
X

t−t1

2

k=0

40

 
e
Esol (3pk1 2t1 , 2) + d(S).
k

(5.6)

Since 4 ≤ m ≤ 19, the possibilities for n and the triple (a, e, t) are as follows:
Table 5.1
n

(a, e, t)

48

(3, 1, 1)

96

(3, 1, 2), (5, 1, 0)

192

(3, 1, 3), (3, 2, 0), (5, 1, 1)

384

(3, 1, 4), (3, 2, 1), (5, 1, 2), (7, 1, 0)

768

(3, 1, 5), (3, 2, 2), (5, 1, 3), (7, 1, 1)

1536

(3, 1, 6), (3, 2, 3), (3, 3, 0), (5, 1, 4), (7, 1, 2)

3072

(3, 1, 7), (3, 2, 4), (3, 3, 1), (5, 1, 5), (7, 1, 3), (5, 2, 0)

6144

(3, 1, 8), (3, 2, 5), (3, 3, 2), (5, 1, 6), (7, 1, 4), (5, 2, 1)

12288

(3, 1, 9), (3, 2, 6), (3, 3, 3), (3, 4, 0), (5, 1, 7), (7, 1, 5), (5, 2, 2)
Table 5.1 ctd.

n
24576

49152

Table 5.1 ctd.

(a, e, t)

n

(3, 1, 10),

(3, 2, 7),

(3, 3, 4),
(5, 1, 8),

393216

(3, 1, 14),

(3, 2, 11),

(3, 4, 1),

(3, 3, 8),

(3, 4, 5),

(7, 1, 6),

(3, 5, 2),

(5, 1, 12),

(13, 1, 0), (5, 2, 3)

(7, 1, 10),

(13, 1, 4),

(3, 1, 11),

(3, 2, 8),

(17, 1, 0),

(5, 2, 7),

(3, 3, 5),

(3, 4, 2),

(7, 2, 3), (5, 3, 2)

(5, 1, 9),

(7, 1, 7),

(13, 1, 1),

(5, 2, 4),

786432

(7, 2, 0)
98304

196608

(a, e, t)

(3, 1, 15),

(3, 2, 12),

(3, 3, 9),

(3, 4, 6),

(3, 5, 3),

(3, 6, 0),

(3, 1, 12),

(3, 2, 9),

(5, 1, 13),

(7, 1, 11),

(3, 3, 6),

(3, 4, 3),

(13, 1, 5),

(17, 1, 1),

(3, 5, 0),

(5, 1, 10),

(7, 1, 8),

(13, 1, 2),

(5, 2, 8), (7, 2, 4), (5, 3, 3)
1572864

(3, 1, 16),

(3, 2, 13),

(5, 2, 5), (7, 2, 1), (5, 3, 0)

(3, 3, 10),

(3, 4, 7),

(3, 1, 13),

(3, 2, 10),

(3, 5, 4),

(3, 6, 1),

(3, 3, 7),

(3, 4, 4),

(5, 1, 14),

(7, 1, 12),

(3, 5, 1),

(5, 1, 11),

(13, 1, 6),

(17, 1, 2),

(7, 1, 9),

(13, 1, 3),

(19, 1, 0),

(5, 2, 9),

(5, 2, 6), (7, 2, 2), (5, 3, 1)

(7, 2, 5), (5, 3, 4)

Going through each of the relevant values of n in the first column of Table A.1,
each triple (a, e, t) in the last column of Table 5.1, and each possible value of t1 ≤ t,

with n/2 = 2ea+t 3, the required bound follows from (5.6) each time.

ii s = 2m 5, for some 2 ≤ m ≤ 15; or s = 2m 15 for some 1 ≤ m ≤ 14. Then the
bound d(G) ≤ E(s, 2) + d(S), together with the bounds on d(S) described above,
give the bounds in Table A.1 in each case.

41

3. r = 3. Here, d(G) ≤ E ′′ (s, 3) + E ′′ (s, 2) + d(S), and the bounds from Table A.1 follow in
each case from applying the usual upper bounds on d(S).

4. r = 4. Then
d(G) ≤ E ′′ (s, 2) + min



√

bs
s
,
log s2 s3



+ E ′′ (s, 3) + d(S)

(5.7)

by Corollary 5.11. Combining this with the bounds on d(S) described above again gives
the bound from the second column of Table A.1 for each of the values of n in the first
column, as required.
5. r = 5. The possible lists of chief factors of the primitive group R of degree 5 can be
obtained from the MAGMA database [5]. In particular, applying (5.5) yields
d(G) ≤ 2E ′′ (s, 2) + E ′′ (s, 5) + d(S).
Again, combining this with the bounds on d(S) described above yields the required bound
from Table A.1 in each case.
6. r = 6. Again, we take the possible lists of chief factors of the primitive group R of degree
6 from the MAGMA database [5], and apply (5.5). We get
d(G) ≤ E ′′ (s, 2) + 1 + d(S).
Combining this with the bounds on d(S) described above yields the required bound from
Table A.1 in each of the relevant cases.
7. r = 8. After obtaining the possible chief factors of R from the MAGMA database, we
again apply (5.5) and get
d(G) ≤ 3E ′′ (s, 2) + E ′′ (s, 3) + E ′′ (s, 7) + d(S).
Using the above with the bounds on d(S) described previously gives the required bound
from Table A.1 in each case.
8. 10 ≤ r ≤ 16. In each case, we use the same approach as in the previous case, so to avoid

being too repetitive we will just check the r = 16 case. Again we can take the possible lists
of chief factors of the primitive groups R of degree 16 from the MAGMA database, and
apply (5.5). We get
d(G) ≤ 7E ′′ (s, 2) + E ′′ (s, 3) + max{E ′′ (s, 3), E ′′ (s, 5)} + d(S).

As before, combining this with the usual bounds for d(S) gives the bounds in Table A.1 in
each case.
(iii) We now consider the bounds in Table A.2., i.e. the exceptional cases from Theorem 5.3. Thus,
either n = 2m 5 and 17 ≤ m ≤ 26, or n = 2m 15 and 15 ≤ m ≤ 35. Note that 0 ≤ bl2 (G) ≤ m.
42

If bl2 (G) = 0 then (5.4) for r > 16, and (5.5) for 2 < r ≤ 16, as in our proofs in (i) and (ii)

above yields the required bounds in each case.
So assume that bl2 (G) ≥ 1. Then
bl2 (G)

d(G) ≤

X
i=1

e
E(2m−i 5, 2) + d(S)

(5.8)

where Se is transitive of degree 2m−bl2 (G) v, by Corollary 5.10 Part (ii).

Now, fix a transitive permutation group G of degree n where n is one of the values from the
first column of Table A.2. Suppose first that bl2 (G) ≤ f , where f is the corresponding value to
e above, we use the database of transitive
n in the second column of Table A.2. To bound d(S)
permutation groups of degree up to 32 in MAGMA (see [10]) if 2 ≤ 2m−bl2 (G) v ≤ 32; otherwise,
e with (5.8)
we use the previous rows of Tables A.1 and A.2. Combining these bounds for d(S)
√
yields d(G) ≤ ⌊c1 n/ log n⌋ in each case, as required.

If G contains a soluble transitive subgroup, then the bound at (5.8) with E replaced by Esol
√
holds, and yields d(G) ≤ ⌊c1 n/ log n⌋ in each case, as needed.
So we may assume that bl2 (G) > f , and that G contains so soluble transitive subgroups. In
particular, the bound at (5.8) again holds. If Se is primitive of degree 2m−bl2 (G) v, then the bound

e ≤ ⌊log (2m−bl2 (G) v)⌋ of Theorem 2.11 gives us the required bound in Table A.2 in each case.
d(S)
r.
So assume that Se is imprimitive, with minimal block size re > 2. Also, write se := 2m−fG v/e

With (r, s) replaced by (e
r , se), we can now apply (5.4) if re > 16, and (5.5) for 2 < r ≤ 16, as
e is bounded above using the database of transitive
in cases (i) and (ii) above. (Note that d(S)

permutation groups of degree up to 32 in MAGMA (see [10]) if 2 ≤ se ≤ 32). This gives us

the required bound in Table A.2 in each case. (We perform these calculations for each possible
value of fG , and each pair (e
r , se) with re > 2 and 2m−fG v = rese.) This completes the proof.

We are now ready to prove Theorem 5.3.
Proof of Theorem 5.3. The proof is by induction on n. Suppose first that G is primitive. The result
√
clearly holds when n ≤ 3. When n ≥ 4, we have log n ≤ c1 n/ log n, so the result follows immediately

from Theorem 2.11. This can serve as the initial step.

The inductive step concerns imprimitive G. For this, we now use the notation introduced immediately following Theorem 5.5. Write Vi for the abelian chief factors of R, and write |Vi | = pai i .
P
Recall that a(R) denotes the composition length of R. In particular, a(R) ≥ i ai + cnonab (R). The

43

inductive hypothesis, together with the bounds obtained in Corollaries 4.27 and 2.12, give

 
c1 s
2a(R)s
d(G) ≤
+ √
c′ log s
log s
$
√ % 

cs
a(R)b 2s
√
+ √
d(G) ≤
log s
log s
$
% 

a(R) 2′ s
cs
d(G) ≤ √ c
+ √
log s
log s


cs
d(G) ≤ s⌊log r⌋ + √
log s


(if 2 ≤ s ≤ 1260)

(5.9)

(if s ≥ 1261)

(5.10)

(for all s ≥ 2)

(5.11)

(for r ≥ 4, s ≥ 2)

(5.12)

respectively. Note that (5.9) and (5.10) follow from Corollaries 4.27 and 5.10 Part (i), and together
imply (5.11), while (5.12) follows from Corollary 2.12. Recall that we need to prove that d(G) ≤
√
c1 rs/ log rs for all cases apart from those listed in Theorem 5.3 Part (2).
Suppose first that r ≥ 481. Then (5.11), together with Theorem 2.10, gives
d(G) ≤

([(2 + c0 ) log r − (1/3) log 24] c2′ + c)s
√
.
log s

√
This is less than c1 rs/ log rs for r ≥ 481 and s ≥ 2, which gives us what we need.

So we may assume that 2 ≤ r ≤ 480. Suppose first that 10 ≤ r ≤ 480, and consider the function
√
√
(eb 2 + c) z + w
√
f (e, z, w) =
2z w

defined on triples of positive real numbers. Clearly when the pair (e, z) is fixed, f becomes a decreasing
function of w. We distinguish two sub-cases:
(a) s ≥ 1261. For each of the cases 10 ≤ r ≤ 480, we compute the maximum value aprim (r) of
the composition lengths of the primitive groups of degree r, using MAGMA. Each time, we get
f (aprim(r), log r, log s) ≤ f (aprim (r), log r, log 1261)

< c1 , and the result then follows, in each case, from (5.10).
(b) 2 ≤ s ≤ 1260. For each fixed r, 10 ≤ r ≤ 480, and each s, 2 ≤ s ≤ 1260, we explicitly
√
compute min {⌊2aprim (r)s/(c′ log s)⌋, s⌊log r⌋} + ⌊c1 s/ log s⌋. Each time, except when r = 16
√
and 72 ≤ s ≤ 1260, this integer is less than or equal to ⌊c1 rs/ log rs⌋, which, after appealing
to the inequalities at (5.9) and (5.12), gives us what we need. If r = 16, and 72 ≤ s ≤ 1260,
√
we have d(G) ≤ 7E(s, 2) + 2E(s, 3) + ⌊c1 s/ log s⌋, by Corollary 5.10 Part (i), and this gives the

required bound in each case (the chief factors of the primitive groups of degree 16 are computed
using MAGMA - see Table B.2).

Finally, we deal with the cases 2 ≤ r ≤ 9. In considering each of the relevant cases, we take the

possible lists of chief factors of R from the MAGMA database. In each case, we bound d(S) above

by using the database of transitive permutation groups of degree up to 32 in MAGMA (see [10]) if
2 ≤ s ≤ 32, Lemma 5.12 if s is in the left hand column of Table A.1 or Table A.2, or the inductive

hypothesis otherwise.

44

(a) r = 2. Corollary 5.10 Part (i) gives d(G) ≤ E(s, 2) + d(S). Write s = 2m q, where q is odd,

and assume first that s < 1066 . Assume first that lpp(q) ≥ 19. Then d(G) ≤ s/19 + d(S), and
√
the bounds on d(S) described above, yield d(G) ≤ 2c1 s/ log 2s for s < 1066 . So assume further
that lpp(q) ≤ 17. Then q is of the form q = 3l3 5l5 7l7 11l11 13l13 17l17 , where 0 ≤ l3 ≤ 2, and
0 ≤ li ≤ 1, for i = 5, 7, 11, 13 and 17. Fix one such q. Then 0 ≤ m ≤ m(q) := ⌊log (1066 /q)⌋,

and d(G) ≤ E(2m q, 2) + d(S). Now, by using the upper bounds on d(S) described above, we get
√
d(G) ≤ 2c1 s/ log 2s, for each of the 96 possible values of q, and each 0 ≤ m ≤ m(q). This gives

us what we need.

Thus, we may assume that s ≥ 1066 . We distinguish two sub-cases.

p
√
√
(i) s2 ≥ s858/1000 . Then E(s, 2) ≤ bs/ log s2 ≤ bs 1000/858/ log s. Hence, d(G) ≤
p
√
√
√
bs 1000/858/ log s+c1 s/ log s, and this is less than or equal to 2c1 s/ log 2s for s ≥ 1066 ,
as required.

(ii) s/s2 ≥ s142/1000 . Then, by Lemma 2.17, we have
E(s, 2) ≤ s/(c′ log (s/s2 )) ≤ (1000/142)s/c′ log s,
√
and hence d(G) ≤ (1000/142)s/(c′ log s) + c1 s/ log s. Again, this is less than or equal to
√
2c1 s/ log 2s, for s ≥ 1066 .
(b) r = 3. Here, Corollary 5.10 Part (i) gives d(G) ≤ E(s, 3) + E(s, 2) + d(S). Using the bounds for
d(S) described above, this gives us what we need whenever 2 ≤ s ≤ 5577, and whenever S is one

of the exceptional cases listed in Theorem 5.3 Part (2) )in these cases, we take the bounds for
d(S) from Table A.2). Otherwise, s ≥ 5578, and we use Corollary 4.27 to distinguish two cases,

with α = 1/3.

√
(i) s2 , s3 ≤ s1/3 . Then d(G) ≤ 3s/(c′ log s) + c1 s/ log s, and this is less than or equal to
√
3c1 s/ log 3s for s ≥ 3824.
√ √
(ii) s2 ≥ s1/3 , or s3 ≥ s1/3 . Then lpp (s/s3 ) ≥ s1/3 or lpp (s/s2 ) ≥ s1/3 , so d(G) ≤ b 3s/ log s+
√
√
s2/3 + c1 s/ log s, and this is at most 3c1 s/ log 3s, for s ≥ 5578.
(c) r = 4. Here Corollary 5.11 implies that
d(G) ≤ E(s, 2) + min



√

s
bs
,
log s2 s3



+ E(s, 3) + d(S).

(5.13)

Using the bounds on d(S) described above, this yields the required upper bound whenever S is
one of the exceptional cases of Theorem 5.3 Part (2), and whenever 7 ≤ s ≤ 49435925. When

2 ≤ s ≤ 6, G is transitive of degree 4s, and the result follows by using Table B.1. So assume that

s ≥ 115063, and that s is not one of those cases listed in Theorem 5.3 Part (2). We distinguish

three cases.

√
(i) s2 , s3 ≤ s21/50 . Then d(G) ≤ (200/29)s/(c′ log s) + c1 s/ log s by Corollary 4.27 (with
√
alpha = 21/50), and this is less than or equal to 4c1 s/ log 4s for s ≥ 49435925, as needed.

45

p
√
(ii) s2 ≥ s21/50 . Then E(s, 2) ≤
50/21bs/ log s, and E(s, 3) ≤ s/ lpp (s/s3 ) ≤ s/s2 ≤
p
√
√
s29/50 . Hence, d(G) ≤ 2 50/21bs/ log s + s29/50 + c1 s/ log s by (5.13). This is at most
√
4c1 s/ log 4s, for s ≥ 28090868.
p
√
√
(iii) s3 ≥ s21/50 . Then d(G) ≤ 50/21bs/ log s + 2s29/50 + c1 s/ log s using a similar argument
√
to (ii) above. This is less than or equal to 4c1 s/ log 4s, for s ≥ 56. This completes the
proof of the theorem in the case r = 4.

(d) r = 5. Corollary 5.10 Part (i) gives d(G) ≤ E(s, 5) + 2E(s, 2) + d(S). Again, this gives us what
we need for each s in the range 3 ≤ s ≤ 552, and each exceptional S. Also, s = 2 implies that

G is transitive of degree 10, and the result follows from Table B.1. Thus, we may assume that
s ≥ 553. Applying Corollary 4.27, with α = 2/5, yields three cases.

√
(i) s2 , s5 ≤ s2/5 . Then d(G) ≤ 5s/(c′ log s) + c1 s/ log s, which is less than or equal to
√
5c1 s/ log 5s for s ≥ 553, as required.
p
√
√
(ii) s2 ≥ s2/5 . Then d(G) ≤ 2b 5/2s/ log s + s3/5 + c1 s/ log s, and this is no greater than
√
5c1 s/ log 5s when s ≥ 139.
p
√
√
(iii) s5 ≥ s2/5 . Then d(G) ≤ b 5/2s/ log s + 2s3/5 + c1 s/ log s, which is less than or equal to
√
5c1 s/ log 5s for s ≥ 17.

(e) r = 6. Here, Corollary 5.10 Part (i), together with the inductive hypothesis, gives d(G) ≤
√
E(s, 2)+1+d(S). Using the usual bounds on d(S), this is at most ⌊6cs/ log 6s⌋ for 2 ≤ s ≤ 1260,
√
and whenever S is one of the exceptional cases. Otherwise, s ≥ 1261, and d(S) ≤ c1 s/ log s.
√ √
√
Hence, by Corollary 4.27 Part (iii), d(G) ≤ b 2s/ log s + 1 + c1 s/ log s, which is less than or
√
equal to 6c1 s/ log 6s for s ≥ 2. This completes the proof of the theorem in the case r = 6.
(f) r = 7. Here, d(G) ≤ E(s, 2) + E(s, 3) + E(s, 7) + d(S), again using Corollary 5.10 Part (i).
√
Bounding d(S) as described previously, this is at most ⌊7c1 s/ log 7s⌋ for each s in the range
2 ≤ s ≤ 1260, and each exceptional S. Otherwise, s ≥ 1261, and by Corollary 4.27 Part (iii)
√ √
√
√
d(G) ≤ 3b 2s/ log s + c1 s/ log s. This is less than 7c1 s/ log 7s for s ≥ 7, and, again, we have
what we need.

(g) r = 8. Using Corollary 5.10 Part (i), d(G) ≤ 3E(s, 2) + E(s, 3) + E(s, 7) + d(S). In each of

the cases 2 ≤ s ≤ 272, and each exceptional case, this bound, together with the bounds on d(S)

described above, give us what we need. Thus, we may assume that s ≥ 273. Then the inductive
√
hypothesis gives d(S) ≤ c1 s/ log s, and applying Corollary 4.27, with α = 37/100, yields three

cases.

√
(i) max {s2 , s3 , s7 } ≤ s37/100 . Then d(G) ≤ (500/63)s/(c′ log s) + c1 s/ log s, which is less than
√
or equal to 8c1 s/ log 8s for s ≥ 273, as required.
p
√
√
(ii) s2 ≥ s37/100 . Then d(G) ≤ 3b 100/37s/ log s+2s63/100 +c1 s/ log s, and this is no greater
√
than 8c1 s/ log 8s when s ≥ 98.
p
√
√
(iii) max {s3 , s7 } ≥ s37/100 . Then d(G) ≤ 2b 100/37s/ log s + 3s63/100 + c1 s/ log s, which is
√
less than or equal to 8c1 s/ log 8s for s ≥ 27.
46

(h) r = 9. By Corollary 5.10 Part (i), d(G) ≤ 4E(s, 2) + 3E(s, 3) + d(S). When 3 ≤ s ≤ 2335, and
when S is one of the exceptional cases, this bound, together with the usual bounds on d(S), give

us what we need. If s = 2, then G is transitive of degree 18, and the result follows from Table
√
A.1. Otherwise, s ≥ 2336, and d(S) ≤ c1 s/ log s, using the inductive hypothesis. We now use
Corollary 4.27 to distinguish three cases, with α = 37/100.

√
(i) s2 , s3 ≤ s37/100 . Then d(G) ≤ (700/63)s/(c′ log s) + c1 s/ log s, and this is less than or
√
equal to 9c1 s/ log 9s for s ≥ 2336, as needed.
p
√
√
(ii) s2 ≥ s37/100 . Then d(G) ≤ 4b 100/37s/ log s + 3s63/100 + c1 s/ log s, which is no larger
√
than 9cs/ log 9s, whenever s ≥ 1197.
p
√
√
(iii) s3 ≥ s37/100 . Here, d(G) ≤ 3b 100/37s/ log s + 4s63/100 + c1 s/ log s, and this is less than
√
or equal to 9c1 s/ log 9s for s ≥ 148.
This completes the proof of Theorem 5.3.

6

The proof of Theorem 1.7

In proving Theorem 1.7, we will omit reference to the constant C, and just use the Vinogradov
notation defined immediately after Definition 4.29. We will now restate some results from Sections 2,
3 and 4 in this language for the convenience of the reader.
We begin with Theorems 2.10 and 1.1.
Theorem 6.1. Let R be a primitive permutation group of degree r. Then a(R) ≪ log r.

√
Theorem 6.2. Let S be a transitive permutation group of degree s ≥ 2. Then d(S) ≪ s/ log s.
We also note the following useful consequence of Corollaries 5.9 and 4.27, and Theorem 6.2.
Corollary 6.3. Let R be a finite group, let S be a transitive permutation group of degree s ≥ 2, and
let G be a large subgroup of the wreath product R ≀ S. Then
a(R)s
d(G) ≪ √
.
log s
Theorem 2.11 reads as follows in Vinogradov notation.
Theorem 6.4 ([19], Theorem 1.1). Let H be a subnormal subgroup of a primitive permutation
group of degree r. Then d(H) ≪ log r.
Finally, we will need the following theorem of Cameron, Solomon and Turull; note that we only

give a simplified version of their result here.
Theorem 6.5 ([9], Theorem 1). Let G be a permutation group of degree n ≥ 2. Then a(G) ≪ n.

47

6.1

Orders of transitive permutation groups

We now turn to bounds on the order of a transitive permutation group G, of degree n. First, we
fix some notation which will be retained for the remainder of the section. Let G be a transitive
permutation group of degree n, and let (R1 , . . . , Rt ) be a tuple of primitive components for G, where
Q
each Ri is primitive of degree ri , and i ri = n. Furthermore, we will write π1 for the identity map

G → G, and for i ≥ 2, we will write πi to denote the projection πi : Gπi−1 ≤ Ri−1 ≀(Ri ≀Ri+1 ≀. . .≀Rt ) →

Ri ≀ Ri+1 ≀ . . . ≀ Rt .

The following is a simplified version of a theorem of C. Praeger and J. Saxl [33] (which was later

improved by A. Maróti in [30]).
Theorem 6.6 ([33], Main Theorem). Let G be a primitive permutation group of degree r, not
containing Alt(r). Then log |G| ≪ r.
Since the symmetric and alternating groups are 2-generated, the next corollary follows immediately
from Theorems 6.4 and 6.6.
Corollary 6.7. Let G be a subnormal subgroup of a primitive permutation group of degree r. Then
d(G) log |G| ≪ r log r.

6.2

The proof of Theorem 1.7

Before proceeding to the proof of Theorem 1.7, we require an application of the results in Section 5.1.
First, we need a preliminary lemma.
Lemma 6.8. Let R and S be transitive permutation groups of degree r ≥ 2 and s ≥ 1 respectively, let

D be a subgroup of Sym(d) containing Alt(d), let P be a large subgroup of the wreath product D ≀ S,
and let G be a large subgroup of R ≀ P . Also, write Ui for the abelian chief factors of R. Suppose that

d ≥ 5. Then

(i) There exists a large subgroup Q of the wreath product R ≀ D, and an embedding θ : G → Q ≀ S,
such that Gθ is a large subgroup of Q ≀ S.

(ii) Let H := NQ (R(1) ). Then Q has a normal series
1 = N0 ≤ N1 ≤ . . . < Nt < Nt+1 ≤ Nt+2 = Q,
where for each abelian Ui with i ≤ t, Ni /Ni−1 is contained in the Q-module Ui ↑Q
H ; and for each

non-abelian Ui with i ≤ t, Ni /Ni−1 is either trivial or a non-abelian chief factor of Q. Also,
Nt+1 /Nt ∼
= Alt(d), and |Nt+2 /Nt+1 | ≤ 2.

Proof. Note first that G is an imprimitive permutation group of degree rds, with a block ∆1 of size
r, by Remark 2.4. Now, by Remark 2.7, G is also a subgroup of the wreath product X := (R ≀ D) ≀ S.

Hence, G also has a block of size rd, again using Remark 2.4. Let ∆ be a block of size rd containing

∆1 . Let H1 := StabG (∆1 ) and H := StabG (∆) = NQ (R(1) ). Then H1 ≤ H, and ∆1 is a block for

H ∆ of size r, with block stabiliser H1∆ . Let Γ1 be the set of H-translates of ∆1 , and let Γ be the
set of G-translates of ∆. Then G is a large subgroup of H ∆ ≀ GΓ , while H ∆ is a large subgroup of
48

H1∆1 ≀ H Γ1 , by Theorem 2.5. By Definition 2.3, H1∆1 ∼
= R. Thus, to complete the proof of Part (i) we
Γ
Γ
∼
∼
1
just need to show that H = D and G = S (we then take Q = H ∆ ).
First, let π : G ≤ R ≀ P → P denote projection over the top group. Note that Hπ ≤ P is a

permutation group of degree ds, stabilising a block of size d. Furthermore, since Ker(π) = coreG (H1 ) ≤
H1 ≤ H, we have s = |G : H| = |Gπ : Hπ|. Thus, Hπ is the full (set-wise) stabiliser of a block for P
of size d. It follows that H Γ1 ∼
= D, since P is large in D ≀ S.

Γ
Γ
Γ ∼
Since Ker(π) = KerG (∆G
1 ) ≤ KerG (Γ), we have G = π(G) = P = S, as needed. Finally, since
Q is a large subgroup of R ≀ D, and D ∼
= Alt(d) or D ∼
= Sym(d), Part (ii) follows from Lemma 5.8.

The mentioned application can now be given as follows.
Proposition 6.9. Let R be a finite group, let S be a transitive permutation group of degree s ≥ 2, let

D be a subgroup of Sym(d) containing Alt(d), let P be a large subgroup of the wreath product D ≀ S,
and let G be a large subgroup of R ≀ P . Also, let K1 be the kernel of the action of P ≤ D ≀ S on a
set of blocks of size d, and let A be the induced action of K1 on a fixed block ∆ for P . Assume that

d
A 6= 1, that d ≥ 5, and set g(d, s) := max{1, √log
}. Then
s

(i) d(G) ≪ a(R)s; and
(ii) d(G) ≪

a(R)g(d,s)s
√
.
log s

Proof. Let Ui , for 1 ≤ i ≤ t say, denote the chief factors of R. Also, if Ui is abelian, write |Ui | = pai i ,
for pi prime. By Lemma 6.8 Part (i), G is a large subgroup of Q ≀ S, where Q is a large subgroup of
R ≀ D. Let H1 := NQ (R(1) ). By Lemma 6.8 Part (ii), Q has a normal series
1 = N0 ≤ N1 ≤ . . . ≤ Nt < Nt+1 ≤ Nt+2 = Q,
where each abelian factor Ni /Ni−1 , for i ≤ t, is contained in the Q-module Ui ↑Q
H1 , and each nonabelian
∼
factor is a chief factor of Q. Also, Nt+1 /Nt = Alt(d), and |Nt+2 /Nt+1 | ≤ 2. In particular,
cnonab (Q) ≤ cnonab (R) + 1.

(6.1)

Denote by B the base group of Q ≀ S, and consider the corresponding normal series
1 = G ∩ B N0 ≤ G ∩ B N1 ≤ G ∩ B N2 ≤ . . . ≤ G ∩ B Nt
< G ∩ BNt+1 ≤ G ∩ BNt+2 = G ∩ B

(6.2)
(6.3)

for G ∩ B. Let Mi be the abelian factors in (6.2). Then
d(G) ≪

X

Ui abelian

dG (Mi ) + cnonab (R) + √

s
log s

(6.4)

by Corollary 5.9 and Theorem 6.2. Viewing G as a subgroup of Q ≀ S, let H := NG (Q(1) ). Also, let

π : R ≀ P → P denote projection over the top group. Since Hπ ≤ P stabilises a block of size d, we

may assume, without loss of generality, that

Hπ = StabP (∆)
49

(recall that ∆ is a block of size d for P ≤ D ≀ S). Note also that Mi is a submodule of the induced
G∼
G
module Ui ↑H
H1 ↑H = Ui ↑H1 , by Lemmas 5.8 and 6.1.
√
Fix i in the range 1 ≤ i ≤ t such that Ui is abelian. Suppose first that spi ≤ s. Then Corollary

4.27 Part (ii), with α := 1/2, gives

dG (Mi ) ≪
Assume next that spi >

√

ai g(d, s)s
ai ds
≤ √
log s
log s

(6.5)

s for some fixed i. Let K := coreG (H). Note that Kπ = K1 ≤ P , since

Hπ = StabP (∆) is a block stabiliser. Then

1 < A = (Kπ)∆ E (Hπ)∆ = D,
so (Kπ)∆ ≥ Alt(d). Hence, Proposition 4.30 Part (ii) implies that
√
ai g(d, s)s
ai s
2ai s
≤√
≪ √
.
dG (Mi ) ≪ p
log s
log s
log spi

(6.6)

Thus, (6.4), (6.5) and (6.6) yield:
d(G) ≪

X

Ui abelian

ai g(d, s)s
s
√
+ cnonab (R) + √
log s
log s

s
a(R)g(d, s)s
√
+√
log s
log s
a(R)g(d, s)s g(d, s)s
a(R)g(d, s)s
√
√
≪
+ √
≪
log s
log s
log s
≪

and this proves Part (ii).
Finally, 6.4 and Proposition 4.30 Part (i) give
d(G) ≪

Ui

X

s
ai s + cnonab (R) + √
log s
abelian

≪ a(R)s + √

s
≪ a(R)s
log s

and this completes the proof.
We are now ready to prove Theorem 1.7.
√
Proof of Theorem 1.7. Let f (G) = d(G) log |G| log n/n2 . We will prove, by induction on n, that

f (G) ≪ 1. If G is primitive, then f (G) ≪ (log n)3/2 /n by Corollary 6.7, and the claim follows.
For the inductive step, assume that G is imprimitive. Fix a tuple

(R1 , R2 , . . . , Rt ) of primitive components for G, where each Ri is primitive of degree ri , say. Also, for
1 ≤ i ≤ t − 1, let ∆i be a block of size ri for πi (G) ≤ Ri ≀πi+1 (Ri ), and denote by Ai the induced action

of Kerπi (G) ({∆i g : g ∈ πi (G)}) on ∆i (in particular, note that Ai E Ri ). Finally, set At := πt (G).

50

Then
|G| ≤

t
Y
i=1

n

|Ai | r1 ...ri

(6.7)

Next, for 1 ≤ i ≤ t, we define the functions fi as follows

√
√
d(G) log |Ai | log n
d(G)n log |Ai | log n
=
fi (G) :=
r1 r2 . . . ri n2
r1 r2 . . . ri n

The inequality at 6.7 then yields f (G) ≤

Pt

i=1 fi (G).

(6.8)

We claim that fi (G) ≪

(i−1)
2i−1

for 2 ≤ i ≤ t,

and that f1 (G) ≪ 1 (the implied constants here are independent on i). The result will then follow.
P
i−1
Indeed, in this case, f (G) ≪ ∞
i=1 2i−1 ≪ 1.

To this end, first fix i in the range 2 ≤ i ≤ t. Clearly we may assume that Ai is non-trivial. Let

D = Ri , S := πi (G), and note that G is a large subgroup of a wreath product R ≀ P , where R is
transitive of degree r := r1 r2 . . . ri−1 , and P is a large subgroup of D ≀ S. Set d := ri , s := ri+1 . . . rt ,

and m := max {r, d, s}. Suppose first that d ≥ 5 and that D contains the alternating group Alt(d).

(In particular, we are in the “bottom heavy” situation of Proposition 6.9.) Then Ai , being a nontrivial
normal subgroup of D, also contains Alt(d). Note that |Ai | ≤ dd . We distinguish two cases. Note
throughout that log n ≤ log m3 ≪ log m.

2

2

1. s ≤ 2(log d) . Then n = rds ≤ m21 2(log m1 ) , where m1 := max {r, d}. Thus, log n ≤ 2 log m1 +
(log m1 )2 ≪ (log m1 )2 . Since a(R) ≪ r by Theorem 6.5, Proposition 6.9 Part (i) then implies

that d(G) ≪ rs. Hence, from 6.8 we deduce
fi (G) ≪

rsd log d log m1
log d log m1
log r
(i − 1)
=
≪
≤ i−1
r 2 d2 s
rd
r
2

since r ≥ 2i−1 , and this gives us what we need.
2. s >

2
2(log d) .

n
o
d
√
Note that m ∈ {r, s} in this case. Set g(d, s) := max 1, log s . Then
g(d, s) log d ≤ d

since

√

(6.9)

log s > log d. Now, Theorem 6.5 gives a(R) ≪ r. Hence, Proposition 6.9 Part (ii) gives

d(G) ≪

rg(d,s)s
√
.
log s

Hence, since n ≤ m3 , we have

√
rg(d, s)sd log d log m
√
fi (G) ≪
r 2 d2 s log s
√
g(d, s) log d log m
√
=
rd log s
√
d log m
≤ √
rd log s
√
√
log r
i−1
≤ i−1
≤
r
2

by (6.9),
since m ∈ {r, s}.

This gives us what we need.
Next, suppose that either d ≤ 4, or that D does not contain Alt(d). Then log |Ai | ≪ d by Theorem
51

6.6. Now, G is a large subgroup of R ≀ P , where P is transitive of degree ds. Also, a(R) ≪ r by

Theorem 6.5. Then, by Corollary 6.3 we have

d(G) ≪ √

rds
.
log ds

Thus
√
√
√
√
rdsd log m
log m
log r
i−1
= √
≤
fi (G) ≪ 2 2 √
≤ i−1
r
2
r d s log ds
r log ds
and again this gives us what we need.
Finally, we deal with the case i = 1. Here, set r := r1 , s := r2 r3 . . . rt , and m = max {r, s}. Then

|Ai | ≤ r r and log n ≪ log m. Also, G is a large subgroup of a wreath product R ≀ S, where R is

primitive of degree r, and S is transitive of degree s. Thus, a(R) ≪ log r by Theorem 6.1. Thus,
√
Corollary 6.3 implies that d(G) ≤ s log r/ log s, and hence
√
√
(log r)2 log m
(log r)5/2
(log r)sr log r log m
√
√
=
≤
fi (G) ≪
≪ 1.
r
r 2 s log s
r log s
This completes the proof.
We conclude with an example which shows that the bounds of Theorems 5.3 and 1.7 are asymptotically best possible.
Example 6.10. Let A be an elementary abelian group of order 22k−1 , and write R for the radical of
the group algebra F2 [A]. Consider the 2-group G := Rk−1 ⋊ A.
The largest trivial submodule of F2 [A] is 1-dimensional, while dim (Rk−1 ) > 1, by [21, 3.2]. Hence,
the centraliser CA (Rk−1 ) of Rk−1 in A is a proper characteristic subgroup of A; since A is characteristically simple, it follows that CA (Rk−1 ) = 1. Thus, CG (Rk−1 ) = Rk−1 , so Z := Z(G) = CRk−1 (A).
Again, since the largest trivial submodule of Fp [A] is 1-dimensional, and Z is nontrivial, it follows
that Z has order 2, and hence Z is the unique minimal normal subgroup of G. Let H be a subspace
complement to Z in Rk−1 . Then H has codimension 1 in Rk−1 , and hence has index 22k in G. It is
also clear that H is core-free in G, so G is a transitive permutation group of degree 22k .
Next, note that
√



    
1/2
 1/2
k 
Y
1 33
55
2k − 1 2k − 1
1
2k 1
1
 .
=
=
...
1+
2k
k
2 24
46
2k − 2 2k
2
4j(j − 1)
k 4




j=2

As in the proof of Theorem 1.3, the expression in the middle converges to b =

p

2/π, by Wallis’

formula. Hence, since the expression on the right is increasing, we conclude that for all ǫ > 0, there
√
√
1

2k
k
exists a positive integer k such that 2k 2k
k 4k ≥ b − ǫ, that is, k ≥ (b − ǫ)4 / 2k.
Now, the derived subgroup G′ of G is Rk , and G/G′ ∼
= (Rk−1 /Rk ) × A is elementary abelian of

rank 2k−1
k−1 + 2k − 1, again using [21, 3.2]. Thus, for large enough k we have
d(G) =




 
2k − 1
1 2k
(b − ǫ)22k
√
+ 2k − 1.
+ 2k − 1 =
+ 2k − 1 ≥
k−1
2 k
2 2k
52

P2k−1

2k−1 −2k−2
(2k−1
i ) = 22
∼ 2n/2 . Hence, |G| ∼ 2n−1 , which shows that
√
d(G) log |G| is at least a constant times n2 / log n.

Furthermore, |Rk−1 | = 2

i=k−1

53

Appendices
A

Upper bounds for d(G) for some transitive groups of small degree

The groups G in the right hand column of Table A.1 below are transitive permutation groups of degree
d, where d is as specified in the left hand column. In Table A.2, the groups are transitive permutation
groups of degree d which have at least f 2-blocks (see Section 1).
Table A.1

Table A.1 ctd

Table A.1 ctd

Table A.1 ctd

d

d

d

d

d(G) ≤

48

16

211 3

64
96

d(G) ≤
1431

26 5

20

212 3

31

213 3

128
192

d(G) ≤

d(G) ≤

66

23 15

2718

27 5

130

24 15

52

5292

28 5

258

25 15

100

40

214 3

10118

29 5

514

26 15

196

57

2153

19770

210 5

1026

27 15

388

256

75

216 3

38002

211 5

2050

28 15

772

384

109

217 3

74467

212 5

4098

29 15

1540

512

145

218 3

143750

213 5

8194

210 15

3076

28 3

203

219 3

282317

214 5

16386

211 15

6148

210

271

220 3

546854

215 5

32770

212 15

12292

29 3

392

23 5

9

216 5

65538

213 15

24580

211

523

24 5

18

22 15

15

214 15

49156

210 3

738

25 5

34

Table A.2

Table A.2 ctd

27

Table A.2 ctd

d

f

d(G) ≤

d

f

d(G) ≤

d

f

d(G) ≤

217 5

5

130900

216 15

4

196612

226 15

4

164176748

3

392700

227 15

4

321692696

3

773166

228 15

4

630835627

4

1237980292

218 5

4

257722

217 15

219 5

4

504220

218 15

3

1512660

229 15

3

2952202

230 15

5

2431149936

5

4777379825

220 5

4

984067

219 15

221 5

4

1919461

220 15

3

5758386

231 15

3

11235497

232 15

5

9393534359

6

18480443646

222 5

4

3745164

221 15

223 5

5

7312620

222 15

3

21937865

233 15

3

42872110

234 15

7

36376783048

83859059

235 15

8

71639170628

224 5

5

14290701

223 15

225 5

6

27953017

224 15
225 15

226 5

7

54725580

215 15

6

98308

3

References
[1] Alperin, J.L. Local Representation Theory. Cambridge University Press, Cambridge, 1986.

54

[2] Anderson, I. On primitive sequences. J. London Math. Soc. 42 (1967) 137-148.
[3] Babai, L.; Sòs, V.T. Sidon sets in groups and induced subgraphs of Cayley graphs. Europe. J.
Combin. 6(2) (1985) 101-114.
[4] Benson, D.J. Representations and Cohomology: Volume 1, Basic Representation Theory of Finite
Groups and Associative Algebras. Cambridge University Press, Cambridge, 1998.
[5] Bosma, W.; Cannon, J.; Playoust, C. The Magma algebra system. I. The user language. J.
Symbolic Comput. 24 (1997) 235-265.
[6] Bray, J. N.; Holt, D. F.; Roney-Dougal, C. M. The maximal subgroups of the low-dimensional
finite classical groups. London Math. Soc., Lecture Note Series 407, Cambridge, 2013.
[7] Bryant, R.M.; Kovács, L.G.; Robinson, G.R. Transitive permutation groups and irreducible linear
groups. Quart J. Math. 46 (1995) 385-407.
[8] Cameron, P.J. Permutation Groups, London Math. Soc. (Student Texts), vol. 45, CUP, Cambridge, 1999.
[9] Cameron, P.J.; Solomon, R.G.; Turull, A. Chains of subgroups in symmetric groups. J. Algebra
127 (1989) 340-352.
[10] Cannon, J.J.; Holt, D.F. The transitive permutation groups of degree up to 32. Experimental
Math. 17 (2008) 307-314.
[11] Conway, J. H.; Curtis, R. T.; Norton, S. P.; Parker, R. A.; Wilson, R. A. An ATLAS of Finite
Groups. Clarendon Press, Oxford, 1985; reprinted with corrections 2003.
[12] Curtis, C.W.; Reiner, I. Representation Theory of Finite Groups and Associative Algebras: Volume I, Wiley, New York, 1988.
[13] Dalla Volta, F.; Siemons, J. On Solvable Minimally Transitive Permutation Groups. Codes,
Designs, Cryptography 44 nn. 1-3 (2007) 143-150.
[14] de Bruijn, N.G.; van Ebbenhorst Tengbergen, Ca.; Kruyswijk, D. On the set of divisors of a
number. Nieuw Arch. Wiskunde 23 (1951) 191-193.
[15] Dilworth, R.P. A decomposition theorem for partially ordered sets. Ann. of Math. 51(2) (1950)
161-166.
[16] Doerk, K.; Hawkes, T. Finite Soluble Groups. de Gruyter, Berlin, 1992.
[17] Erdos, P. A Theorem of Sylvester and Schur. J. London Math. Soc. 9 (1934) 282-288.
[18] Gorenstein, D. Finite Groups. Harper and Row, New York, 1968.
[19] Holt, D.F.; Roney-Dougal, C.M. Minimal and random generation of permutation and matrix
groups. J. Algebra 387 (2013) 195-223.
[20] Isaacs, I.M. Character Theory of Finite Groups. Dover, New York, 1994.
55

[21] Kovács, L.G.; Newman, M.F. Generating transitive permutation groups. Quart. J. Math. Oxford
(2) 39 (1988) 361-372.
[22] Kleidman, P.; Liebeck, M. W. The subgroup structure of the finite classical groups. CUP, Cambridge, 1990.
[23] Kopylova, T.I. Solvable minimal transitive groups of permutations of degree pq. (Russian)
VestsīAkad. Navuk BSSR Ser. Fīz.-Mat. Navuk (6) 126 (1985) 5460.
[24] Liebeck, M. W.; Praeger, C. E.; Saxl, J. Transitive subgroups of primitive permutation groups.
J. Algebra 234 (2000) 291-361.
[25] Lucchini, A. Generators and minimal normal subgroups. Arch. Math 64 (1995) 273-276.
[26] Lucchini, A. Enumerating transitive finite permutation groups. Bull. London Math. Soc. 30
(1998) 569-577.
[27] Lucchini, A.; Menegazzo, F. Generators for finite groups with a unique minimal normal subgroups
Rend. Sem. Math. Univ. Padova 98 (1997) 173-191.
[28] Lucchini, A.; Menegazzo, F.; Morigi, M. Asymptotic results for transitive permutation groups.
Bull. London. Math. Soc. 32 (2000) 191-195.
[29] Lucchini, A.; Menegazzo, F.; Morigi, M. On the number of generators and composition length of
finite linear groups. J. Algebra 243 (2001) 227-247.
[30] Maroti, A. On the orders of primitive groups. J. Algebra 258 (2) (2002) 631-640.
[31] Neumann, P.M.; Vaughan-Lee, M.R. An essay on BFC-groups. Proc. London. Math. Soc. 35
(1977), 213237.
[32] Pálfy, P.P. A polynomial bound for the orders of primitive solvable groups. J. Algebra 77 (1982)
127-137.
[33] Praeger, C.; Saxl, J. On the order of primitive permutation groups. Bull. London Math. Soc. 12
(1980) 303-308.
[34] Pyber, L. Asymptotic results for permutation groups. Groups and Computation DIMACS Ser.
Discrete Math. Theoret. Computer Sci. 11 (ed. Finkelstein, L. and Kantor, W.M., Amer. Math.
Soc., Providence, 1993) 197-219.
[35] Pyber, L. Enumerating finite groups of given order. Ann. Math., (2) 137 (1993), 203220.
[36] Rosser, J.B.; Schoenfeld, L. Approximate formulas for some functions of prime numbers. Illinois
J. Math. 6 (1962) 64-97.
[37] Shepperd, J.A.M.; Wiegold, J. Transitive groups and groups with finite derived groups. Math. Z.
81 (1963) 279-285.

56

[38] Tracey, G.M. Generating minimally transitive permutation groups. J. Algebra 460 (2016) 380386.
[39] Suprunenko, D.A. Matrix Groups. Translations of Mathematical Monographs, 45. Amer. Math.
Soc., Providence, 1976.
[40] Suprunenko, D.A. Solvable minimal transitive permutation groups of degree pq. Soviet. Math.
Dokl. 27 (1986) 337-340.
[41] Wallis, J. Arithmetica Infinitorum. Oxford, England, 1656.

57

