Simple groups, fixed point ratios
and applications

arXiv:1707.03564v1 [math.GR] 12 Jul 2017

Timothy C. Burness
School of Mathematics, University of Bristol, Bristol BS8
1TW, United Kingdom

Abstract. The study of fixed point ratios is a classical topic in permutation group theory, with a long history stretching back to the origins
of the subject in the 19th century. Fixed point ratios arise naturally in
many different contexts, finding a wide range of applications. In this
survey article we focus on fixed point ratios for simple groups of Lie
type, highlighting some of the main results, applications and related
problems.

1. Introduction
The study of fixed point ratios is a classical topic in permutation group
theory, with a long history stretching all the way back to the early days
of group theory in the 19th century. The concept arises naturally in many
different contexts, finding a wide range of interesting (and often surprising)
applications. One of the main aims of this survey article is to highlight some
of these applications. For instance, we will explain how fixed point ratios
play a key role in the study of some remarkable generation properties of finite
groups. We will also see how probabilistic methods, based on fixed point
ratio estimates, have revolutionised the search for small bases of primitive
permutation groups. In a completely different direction, we will also describe
how bounds on fixed point ratios can be used to investigate the structure of
monodromy groups of coverings of the Riemann sphere.
In this introductory section we start by recalling some basic properties
of fixed point ratios and we present several standard examples that will
be useful later. We also highlight connections to some classical notions in
permutation group theory, such as minimal degree, fixity and derangements.
To whet the appetite of the reader, we close the introduction by presenting
three very different group-theoretic problems. It is interesting to note that
none of these problems have an obvious connection to fixed point ratios, but
we will show later that recent advances in our understanding of fixed point
ratios (in particular, recent results for (almost) simple groups of Lie type)
play an absolutely essential role in their solution.
Some of the main theorems on fixed point ratios will be highlighted in
Section 2, where we focus on the simple groups of Lie type. Finally, in
Sections 3, 4 and 5 we will discuss the three motivating problems mentioned
above. Here we will explain the connection to fixed point ratios and we will
sketch some of the main ideas. In particular, we will see how some of the
results presented in Section 2 play a key role, and we will report on more
recent developments and open problems.
Finally, we have also included an extensive bibliography, which we hope
will serve as a useful guide for further reading.
Acknowledgments. This article is based on a lecture series I gave at the
workshop Some problems in the theory of simple groups at the Centre Interfacultaire Bernoulli at the École Polytechnique Fédérale de Lausanne in
September 2016. This workshop was part of the semester programme Local
representation theory and simple groups at the CIB. It is a pleasure to thank
the organisers of this programme for inviting me to participate and for their

1. INTRODUCTION

3

generous hospitality. I would also like to thank Gunter Malle and Donna
Testerman for their helpful comments on an earlier version of this article.
1.1. Preliminaries. We start with some preliminary definitions. Let
G 6 Sym(Ω) be a permutation group on a finite set Ω. For α ∈ Ω we will
write Gα = {x ∈ G : αx = α} for the stabiliser of α in G. Similarly, the set
of fixed points of x ∈ G will be denoted by
CΩ (x) = {α ∈ Ω : αx = α}.
Definition 1.1. The fixed point ratio of x ∈ G, denoted by fpr(x, Ω) =
fpr(x), is the proportion of points in Ω fixed by x, i.e.
fpr(x) =

|CΩ (x)|
.
|Ω|

Notice that fpr(x) is the probability that a randomly chosen element of Ω
is fixed by x (with respect to the uniform distribution on Ω). This viewpoint
is often useful for applications. Indeed, in recent years probabilistic methods
have been used to solve many interesting problems in finite group theory.
Typically, the aim is to establish an existence result through a probabilistic
approach (rather than an explicit construction, for example) – this has been
a standard technique in combinatorics, number theory and other areas for
many years. As we will see later, bounds on fixed point ratios play a central
role in several applications of this flavour.
It is also worth noting that a fixed point ratio is a special type of character ratio; if π : G → C is the corresponding permutation character, then
fpr(x) =

π(x)
.
π(1)

The following lemma records some basic properties.
Lemma 1.2. Let G be a permutation group on a finite set Ω and let x be
an element of G.
(i) fpr(x) = fpr(y) for all y ∈ xG .
(ii) fpr(x) 6 fpr(xm ) for all m ∈ Z.
(iii) If G is transitive with point stabiliser H, then
fpr(x) =

|xG ∩ H|
.
|xG |

(iv) If the derived subgroup G0 is transitive, then there is a non-linear
irreducible constituent χ of the permutation character such that
fpr(x) 6

1 + |χ(x)|
.
1 + χ(1)

Proof. Parts (i) and (ii) are trivial.

4

(iii) For β ∈ Ω, g ∈ G define (β, g) = 1 if β g = β, otherwise (β, g) = 0.
Then


X
X X

|xG | |CΩ (x)| =
|CΩ (g)| =
(β, g)
g∈xG

g∈xG

β∈Ω


=

X


X



(β, g) =

g∈xG

β∈Ω

X

|xG ∩ Gβ |,

β∈Ω

which is equal to |Ω| |xG ∩ H| by the transitivity of G.
(iv) Set f = fpr(x) and write π = 1 + χ1 + · · · + χt with χi ∈ Irr(G).
Note that the transitivity of G0 implies that each χi is non-linear.
If 1 + |χi (x)| < f (1 + χi (1)) for all i then
X
X
f |Ω| = 1 +
χi (x) 6 1 +
|χi (x)|
i

i

=

X

(1 + |χi (x)|) − (t − 1)

i

<f

!
X
(1 + χi (1)) − (t − 1)
i

= f |Ω| − (1 − f )(t − 1),
which is a contradiction.



The formula in part (iii) of the previous lemma is a key tool for computing fixed point ratios for transitive groups. Indeed, it essentially reduces the
problem to determining the fusion of H-classes in G, which may be more
tractable.
Example 1.3. Sym(n) on 2-sets.
Let G = Sym(n) be the symmetric group of degree n > 5, let x = (1, 2,3) ∈
G and let Ω be the set of 2-element subsets of {1, . . . , n}. Then |Ω| = n2 and
the action of G is transitive, with point stabiliser H = Sym(n − 2) × Sym(2).
We compute fpr(x) in three different ways:
a. Direct calculation.
We have CΩ (x) = {{a, b} : a, b ∈ {4, . . . , n}}, so

n−3
|CΩ (x)| = 2 and thus
(1.1)

fpr(x) =

(n − 3)(n − 4)
.
n(n − 1)

b. Permutation character. Let π be the permutation character. The action
of G on Ω has rank 3 (that is, H has three orbits on Ω) and by Young’s
Rule we have
π = 1 + χ(n−1,1) + χ(n−2,2) ,
where χλ is the character of the irreducible Specht module S λ corresponding
to the partition λ of n (see [61, Section 14], for example). By applying

1. INTRODUCTION

5

the Hook Formula for dimensions and the Murnaghan-Nakayama Rule for
character values (see [61, Sections 20 and 21]), we calculate that
χ(n−1,1) (x) = χ(n−4,1) (1) = n − 4
and
χ(n−2,2) (x) = χ(n−5,2) (1) = (n − 3)(n − 6)/2
if n > 7 (one can check that χ(3,2) (x) = −1 and χ(4,2) (x) = 0), so
fpr(x) =

1 + (n − 4) + (n − 3)(n − 6)/2
(n − 3)(n − 4)
=
.
n(n − 1)/2
n(n − 1)

c. Conjugacy classes. All the 3-cycles in G are conjugate, so xG ∩ H is the
set of 3-cycles in H. This gives


 
n−2
n
G
H
G
|x ∩ H| = |x | = 2
, |x | = 2
3
3
and thus Lemma 1.2(iii) implies that (1.1) holds.
Example 1.4. GLn (q) on vectors.
Consider the action of G = GLn (q) on its natural module V = Fnq . For
x ∈ G we have fpr(x) = q d−n , where d is the dimension of the 1-eigenspace
of x on V .
Example 1.5. PGLn (q) on 1-spaces.
Similarly, we can consider the transitive action of G = PGLn (q) = GLn (q)/Z
on the set of 1-dimensional subspaces of V . Suppose q is odd and set x =
x̂Z ∈ G, where x̂ ∈ GLn (q) is the block-diagonal matrix [−I1 , In−1 ] with
respect to a basis {e1 , . . . , en } for V (here, and elsewhere, we use Im to
denote the m × m identity matrix). Then x fixes he1 i and every 1-space in
he2 , . . . , en i, and no others, so
fpr(x) =

q n−1 −1
q−1
q n −1
q−1

1+

=

q n−1 + q − 2
1
∼ .
n
q −1
q

Alternatively, note that a point stabiliser H = q n−1 :(GL1 (q) × GLn−1 (q))/Z
is a maximal parabolic subgroup of G and one checks that xG ∩ H is a union
of two H-classes. More precisely,
|GLn−1 (q)|
|GLn (q)|
|xG ∩ H| = q n−1 + q ·
, |xG | =
|GLn−2 (q)||GL1 (q)|
|GLn−1 (q)||GL1 (q)|
which provides another way to compute fpr(x) via Lemma 1.2(iii).
1.2. Problems. It is natural to consider the following problems, either
in the context of a specific permutation group, or more typically for an interesting family of permutation groups, such as primitive groups and almost
simple groups.
1. Given a permutation group G and x ∈ G, compute fpr(x).
2. Obtain upper and lower bounds on fpr(x) (in terms of parameters
depending on G and x).

6

3. Compute (or bound) the minimal and maximal fixed point ratios
min{fpr(x) : x ∈ G} and max{fpr(x) : 1 6= x ∈ G}.
4. We can also consider “local” versions. For example, given a (normal) subset S ⊆ G \ {1}, compute (or bound) min{fpr(x) : x ∈ S}
and max{fpr(x) : x ∈ S}.
For instance, we may be interested in the case where S is the set of
elements of prime order in G, or the set of involutions, etc. Note
that max{fpr(x) : 1 6= x ∈ G} and max{fpr(x) : x ∈ G, |x| prime}
are equal by Lemma 1.2(ii).
As we will see later, bounds on fixed point ratios (in particular, upper
bounds) are often sufficient for the applications we have in mind.
The above problems are closely related to some classical notions in permutation group theory. To see the connection, let us fix a permutation group
G 6 Sym(Ω) of degree n.
a. Minimal degree: The minimal degree µ(G) of G is defined to be the
smallest number of points moved by any non-identity element, i.e.


µ(G) = min (n − |CΩ (x)|) = n 1 − max fpr(x) .
16=x∈G

16=x∈G

For example, µ(Sym(n)) = 2 and µ(Alt(n)) = 3. This is a classical invariant
studied by Jordan, Bochert, Manning and others (see Section 2.2).
b. Fixity: Similarly, the largest number of fixed points of a non-identity
element is called the fixity of G, denoted by


f (G) = n max fpr(x) = n − µ(G).
16=x∈G

In addition, max16=x∈G fpr(x) is sometimes referred to as the fixity ratio.
This has been studied by Liebeck, Saxl, Shalev and others.
If we take S to be the set of involutions in G, then n (maxx∈S fpr(x))
is the involution fixity of G. This concept was studied by Bender in the
early 1970s, who classified the transitive groups with involution fixity 1 (for
example, the 3-transitive action of PSL2 (2m ) on the projective line has this
property). See [32, 35, 82] for more recent results in the context of almost
simple primitive groups.
c. Derangements: An element x ∈ G is a derangement if fpr(x) = 0, so
min fpr(x) = 0 ⇐⇒ G contains a derangement.

16=x∈G

The existence and abundance of derangements has been intensively studied
for many years, finding a wide range of applications. We refer the reader to
[25, Chapter 1], and the references therein.
1.3. Applications. The above problems have an intrinsic interest in
their own right, but much of the motivation for studying fixed point ratios
stems from the wide range of applications. In order to motivate some of these
applications, we close this introduction by presenting three very different

2. SIMPLE GROUPS

7

problems involving simple groups where fixed point ratios play a key role.
We will return to these problems in Sections 3, 4 and 5.
1. Generating graphs.
Let G be a finite group. The generating graph Γ(G) is a graph on the nonidentity elements of G so that two vertices x, y are joined by an edge if and
only if G = hx, yi.
Problem A. Let G be a nonabelian finite simple group. Prove that Γ(G)
is a connected graph with diameter 2.
2. Monodromy groups.
Let g be a non-negative integer and let E(g) be the set of nonabelian nonalternating composition factors of monodromy groups of branched coverings
f : X → P1 (C) of the Riemann sphere, where X is a compact connected
Riemann surface of genus g.
Problem B. Prove that E(g) is finite.
3. Bases.
Let G 6 Sym(Ω) be a permutation group. A subset B ⊆ Ω is a base for G
if the pointwise stabiliser of B in G is trivial. The base size b(G) of G is the
minimal size of a base for G.
Problem C. Let G 6 Sym(Ω) be a transitive nonabelian finite simple
group with point stabiliser H satisfying the following conditions:
(i) If G = Alt(m), then H acts primitively on {1, . . . , m}.
(ii) If G is a classical group, then H acts irreducibly on the natural
module.
Prove that b(G) 6 7, with equality if and only if G is the Mathieu group M24
in its natural action on 24 points.
2. Simple groups
In this section we focus on fixed point ratios for primitive simple groups
of Lie type. We start with a brief discussion of primitivity in Section 2.1,
before turning our attention to the connection between fixed point ratios and
the classical notion of minimal degree. In Section 2.3 we introduce a theorem
of Liebeck and Saxl (see Theorem 2.6), which provides an essentially best
possible upper bound on fixed point ratios for simple groups of Lie type.
For the remainder of the section, we look at ways in which this theorem can
be strengthened in special cases of interest. For example, we will explain
how much stronger bounds have been established for so-called non-subspace
actions of classical groups – later we will see that these improved fixed point
ratio estimates are essential for the applications we have in mind.
Finally, a word or two on notation. For the remainder of this article we
will adopt the notation for simple groups used by Kleidman and Liebeck

8

(see [68, Section 5.1]). Notice that this differs slightly from the notation in
the Atlas [34]. For instance, we will write PΩn (q) for a simple orthogonal
group (where  = ± when n is even) and On (q) is the isometry group of the
underlying quadratic form.

2.1. Primitivity. Let G 6 Sym(Ω) be a permutation group, with orbits Ωi , i ∈ I. Then G induces a transitive permutation group GΩi on each
Ωi ; these are called the transitive constituents of G. In some sense, G is built
from its transitive constituents; indeed, G is a subdirect product of the GΩi
(that is, the corresponding projection maps G → GΩi are surjective). For
example, G = {1, (1, 2)(3, 4)} has orbits Ω1 = {1, 2} and Ω2 = {3, 4} on
Ω = {1, 2, 3, 4}, and G is a proper subdirect product of GΩ1 = {1, (1, 2)}
and GΩ2 = {1, (3, 4)}. For the purposes of studying fixed point ratios, it is
natural to assume that G is transitive.
In turn, the transitive constituents themselves may be built from smaller
permutation groups in a natural way. This leads us to the notion of primitivity. This is an important irreducibility condition that allows us to define
the primitive groups, which are the basic building blocks of all permutation
groups.
Definition 2.1. A transitive group G 6 Sym(Ω) is imprimitive if Ω
admits a nontrivial G-invariant partition, otherwise G is primitive.
Here the trivial partitions are {Ω} and {{α} : α ∈ Ω}. It is an easy
exercise to show that G is primitive if and only if a point stabiliser H = Gα
is a maximal subgroup of G, which is a useful characterisation. For instance,
the action of G = Sym(n) on the set of k-element subsets of {1, . . . , n} is
primitive for all 1 6 k < n, k 6= n/2 (note that G is imprimitive if k = n/2
since Gα < Sym(n/2) o Sym(2) < G). Any transitive group of prime degree
is primitive and all 2-transitive groups are primitive.
It turns out that the abstract structure of a finite primitive group G
is rather restricted (observe that transitivity alone imposes no structural
restrictions whatsoever). For example, the socle of G (denoted soc(G)) is a
direct product of isomorphic simple groups (recall that the socle of a group
is the product of its minimal normal subgroups). In fact, we can say much
more. The main result is the O’Nan-Scott theorem (see [38, Chapter 4], for
example), which describes the structure and action of a primitive group in
terms of its socle. This is a very powerful tool for studying primitive groups.
Indeed, in many situations it can be used to reduce a general problem to
a much more specific problem concerning almost simple groups, at which
point one can appeal to the Classification of Finite Simple Groups (CFSG)
and the vast literature on simple groups and their subgroups, conjugacy
classes and representations. (Recall that a finite group G is almost simple
if soc(G) = G0 is a nonabelian simple group, so G0 6 G 6 Aut(G0 ).)
In view of these observations, in this article we will focus our attention
on fixed point ratios for almost simple primitive permutation groups.

2. SIMPLE GROUPS

9

2.2. Minimal degree. Let G 6 Sym(Ω) be a primitive permutation
group of degree n. Recall that


µ(G) = min (n − |CΩ (x)|) = n 1 − max fpr(x)
16=x∈G

16=x∈G

is the minimal degree of G. This invariant has been studied since the 19th
century. In particular, a classical problem is to find lower bounds on µ(G)
in terms of n, assuming G 6= Alt(n), Sym(n), which is equivalent to finding
upper bounds on max16=x∈G fpr(x). We record some results:
• Jordan [62], 1871: µ(G) tends to infinity as n tends to infinity.
In particular, there are only finitely many primitive groups with a
given minimal degree bigger than 3.
• Bochert [12], 1892: µ(G) > n/4 − 1 if G is 2-transitive.
√
• Babai [7, 8], 1981/2: µ(G) > ( n − 1)/2 (independent of CFSG).
√
• Liebeck & Saxl [75], 1991: µ(G) > 2( n − 1) (using CFSG).
Remark 2.2. The bounds obtained by Babai and Liebeck & Saxl are
essentially best possible. To see this, consider the primitive product action
of G = Sym(m) o Sym(2) on n = m2 points (with m > 3), so

((γ1 )x1 , (γ2 )x2 ) if π = 1
(x1 ,x2 )π
(γ1 , γ2 )
=
((γ2 )x2 , (γ1 )x1 ) if π = (1, 2)
for all γ1 , γ2 ∈ {1, . . . , m} and (x1 , x2 )π ∈ G. One checks that every nonidentity element x ∈ G moves at least 2m points, with equality if and only
2
if x is of the form (y, 1) or (1, y) in
√ the base group Sym(m) , where y is a
transposition. Therefore µ(G) = 2 n.
The following theorem of Guralnick and Magaard is a simplified version
of [52, Theorem 1]; it is the best known result on the minimal degree of
primitive groups.
Theorem 2.3. Let G 6 Sym(Ω) be a primitive group of degree n with
µ(G) < n/2. Then one of the following holds:
(i) G = Sym(n) or Alt(n);
(ii) G 6 L o Sym(r) acts with its product action on Ω = Γr for some
r > 1, where L 6 Sym(Γ) is an almost simple primitive group with
socle L0 and either
(a) L0 = Alt(m) and Γ is the set of k-element subsets of {1, . . . , m}
for some k > 1; or
(b) L0 = Ωm (2) is an orthogonal group over F2 and Γ is a set of
1-dimensional subspaces of the natural L0 -module.
By carefully analysing the cases arising in (b), Guralnick and Magaard
establish the following striking corollary (see [52, Corollary 1]).
Corollary 2.4. Let G be a finite primitive group and assume that the
socle of G is not a product of alternating groups. Then
4
max fpr(x) 6 .
16=x∈G
7

10

Remark 2.5.
(i) The upper bound in Corollary 2.4 is best possible. For example,
suppose
G = O7 (2) ∼
= Sp6 (2), H = Gα = O−
6 (2)
and x ∈ G is a transvection (in other words, x is an involution
with Jordan form [J2 , J14 ] on the natural module for Sp6 (2), where
Ji denotes a standard unipotent Jordan block of size i). All the
transvections in H (and also in G) are conjugate, so
|xG ∩ H| = |xH | =

|O−
|Sp (2)|
6 (2)|
= 36, |xG | = 5 6
= 63
2|Sp4 (2)|
2 |Sp4 (2)|

and thus fpr(x) = 36/63 = 4/7 (the respective centraliser orders
can be read off from [6, Sections 7 and 8], noting that x is a b1 -type
involution in both H and G).
(ii) Note that the conclusion is false if we allow groups whose socle is
a product of alternating groups. For instance, in Example 1.3 we
observed that


lim
max fpr(x) = 1
n→∞

16=x∈G

for the action of G = Sym(n) on 2-sets.
We refer the reader to [66] for results on the minimal degree of arbitrary
finite permutation groups and some interesting applications to quantum
computing.
2.3. Fixed point ratios for simple groups. In this section we discuss fixed point ratios for almost simple groups of Lie type. With a view
towards applications, we are primarily interested in obtaining upper bounds,
so it is natural to focus on primitive actions and prime order elements.
We start by recalling a theorem of Liebeck and Saxl [75, Theorem 1],
which is the most general result in this area.
Theorem 2.6. Let G 6 Sym(Ω) be a transitive almost simple group
of Lie type over Fq with socle G0 and point stabiliser H. Assume G0 6=
PSL2 (q). Then either
(2.1)

max fpr(x) 6

16=x∈G

4
3q

or G0 ∈ {PSL4 (2), PSp4 (3), PΩ−
4 (3)}.
Remark 2.7.
(i) This is a simplified version of [75, Theorem 1], which includes the
case G0 = PSL2 (q) and gives a precise description of the triples
(G, H, x) with fpr(x) > 4/3q.
(ii) The upper bound is essentially best possible. For instance, in Example 1.5 (G = PGLn (q) on 1-spaces) we observed that there are
elements x ∈ G with fpr(x) ∼ 1/q.

2. SIMPLE GROUPS

11

(iii) Consider the special case G0 = PSL4 (2) ∼
= Alt(8) appearing in the
statement of the theorem. If G = G0 .2 = Sym(8), |Ω| = 8 and
x = (1, 2), then fpr(x) = 6/8 > 4/6.
The proof of Theorem 2.6 proceeds by induction, with the ultimate goal
of eliminating the existence of a minimal counterexample (minimal with
respect to the order of the group). The details of the argument are somewhat
complicated by the fact that there are a small number of groups for which
the bound in (2.1) is false. To give a flavour of the main ideas, we provide a
brief sketch to show that (2.1) holds when G = PSLn (q) with n > 6. Below
we use the notation Pm for the stabiliser in G of an m-dimensional subspace
of the natural module V for G.
Sketch proof of Theorem 2.6 (G = PSLn (q), n > 6). Suppose
fpr(x) > 4/3q for some 1 6= x ∈ G. Set H = Gα and write x = x̂Z, where
x̂ ∈ SLn (q) and Z = Z(SLn (q)). In view of Lemma 1.2, we may assume that
H is maximal (so G is primitive) and x has prime order r, so x is either
semisimple (if r 6= p) or unipotent (if r = p), where p is the characteristic of
Fq . Replacing x by a suitable conjugate, if necessary, we may assume that
x ∈ H. Note that
(2.2)

|Ω| <

3q|CG (x)|
4

by Lemma 1.2(iii).
Our first goal is to reduce to the case where x stabilises a nontrivial
decomposition V = V1 ⊕ V2 . Suppose otherwise.
If x is semisimple then it acts irreducibly on V and we deduce that
|CG (x)| 6 (q n − 1)/(q − 1). In view of (2.2), this implies that H = P1 (the
smallest permutation representation of G has degree (q n − 1)/(q − 1)), which
means that x fixes a 1-space. This is incompatible with the irreducibility
of x. Similarly, if x is unipotent then it must be regular (i.e. it has Jordan
form [Jn ] on V ) and by considering |CG (x)| we again deduce that H = P1 .
But a regular unipotent element fixes a unique 1-dimensional subspace of
V , so |CΩ (x)| = 1 and once again we have reached a contradiction.
Let V = V1 ⊕ V2 be a nontrivial decomposition fixed by x with 1 6 a1 6
a2 , where ai = dim Vi . Assume a1 is minimal. We claim that a1 6 2.
Suppose a1 > 3. Set Ai = SLai (q), Bi = GLai (q) and write x̂ =
(x̂1 , x̂2 ) ∈ B1 × B2 . Let
X = hA1 × A2 , x̂i 6 SLn (q).
Let xi be the automorphism of the simple group Ai /Z(Ai ) induced by x̂i .
The minimality of a1 implies that neither x̂1 nor x̂2 is a scalar, so each xi is
nontrivial.
The key step in the proof is to study the orbits Ω1 , . . . , Ωk of X on
Ω, together with the action of A1 and A2 on each orbit. The case where
H = Pa1 can be handled directly, so assume otherwise. For convenience,
let us also assume that neither A1 /Z(A1 ) nor A2 /Z(A2 ) are exceptions to
the statement of the main theorem. Then using induction and a technical

12

lemma [75, Lemma 2.8] one can show that |CΩj (x)| 6 4|Ωj |/3q for each j,
which implies that fpr(x) 6 4/3q, a contradiction.
We now have a1 6 2 and a2 > 4 since n > 6. By considering the orbits of
A2 on Ω and applying induction, one can reduce to the case where A2 6 H.
From here it follows that H = P1 or P2 (using work of Kantor [64], given
the fact that H contains long root elements of G), and it is not too difficult
to eliminate these two possibilities.
2
Theorem 2.6 plays a central role in the proof of√[75, Theorem 2], which
yields the aforementioned lower bound µ(G) > 2( n − 1) on the minimal
degree of a primitive group G of degree n that does not contain Alt(n). To
derive this bound, it suffices to show that µ(G) > n/3 unless G satisfies the
conditions in part (ii)(a) of Theorem 2.3. We briefly sketch the argument.
Consider a counterexample G 6 Sym(Ω) of minimal order, with point
stabiliser H. Fix x ∈ H of prime order such that fpr(x) > 2/3. By applying
the O’Nan-Scott theorem, we can reduce to the case where G is almost
simple. For example, if G is either an affine group or a twisted wreath
product, then N = soc(G) is regular (that is, H ∩ N = 1), so
|CΩ (x)| = |CN (x)| 6

n
|N |
=
2
2

and thus fpr(x) 6 1/2, a contradiction.
Now assume G is almost simple with socle G0 . If G0 is a simple group of
Lie type over Fq then Theorem 2.6 immediately gives µ(G) > n/2 if q > 2,
and µ(G) > n/3 if q = 2. If G0 is a sporadic group and µ(G) > n/2 then
Lemma 1.2(iv) implies that
1 + |χ(x)| >

1 + χ(1)
2

for some non-linear character χ ∈ Irr(G). By inspecting the relevant character tables in the Atlas [34], one checks that no such character exists.
Finally, suppose G0 = Alt(m) is an alternating group and consider the
action of H on Γ = {1, . . . , m}. The situation where H is intransitive or
imprimitive on Γ can be handled directly, working with a concrete description of the action of G on subsets or partitions. Suppose H is primitive.
The minimality of |G| implies that µ(H) > m/3 with respect to the action
of H on Γ. This immediately translates into a lower bound of the form
|xG | > f (m) for some function f and thus |H| > 23 f (m) since fpr(x) > 2/3.
But H is a primitive group of degree m, so |H| < g(m) for some function
g (for instance, we can take g(m) = 4m by a theorem of Praeger and Saxl
[91]). Together, these bounds imply that m 6 750 and by inspecting lists of
small degree primitive groups one can reduce this to m 6 24. The remaining
possibilities can be eliminated one-by-one.
2.4. Classical groups. As observed in Remark 2.7, the upper bound
in Theorem 2.6 is essentially best possible. However, it would be desirable
to have bounds on fpr(x) that depend on the element x in some way. We
might also try to establish stronger bounds, at the expense of excluding some

2. SIMPLE GROUPS

13

specific actions. In this section we report on recent work in this direction
for almost simple classical groups.
Let G 6 Sym(Ω) be an almost simple primitive classical group over Fq
with socle G0 and point stabiliser H. Let V be the natural module for G0
and set n = dim V . Write q = pf with p prime. The possibilities for G0 are
recorded in Table 2.1. Note that we may assume the given conditions on n
and q due to several exceptional isomorphisms among the low-dimensional
classical groups (see [68, Proposition 2.9.1] for example).
Type
Linear
Unitary
Symplectic

Notation
PSLn (q)
PSUn (q)
PSpn (q)0

Ωn (q)
Orthogonal
PΩ±
n (q)

Conditions
n > 2, (n, q) 6= (2, 2), (2, 3)
n > 3, (n, q) 6= (3, 2)
n > 4 even
nq odd, n > 7
n > 8 even

Table 2.1. The finite simple classical groups
Since G is primitive, H is a maximal subgroup of G with G = G0 H. The
possibilities for H are described by a fundamental theorem of Aschbacher.
In [2], Aschbacher introduces eight geometric families of subgroups of G,
denoted by C1 , . . . , C8 , which are defined in terms of the underlying geometry
of V . For example, these collections include the stabilisers of certain types
of subspaces of V , and the stabilisers of appropriate direct sum and tensor
product decompositions. Roughly speaking, Aschbacher’s main theorem
implies that H is either contained in one of the Ci collections, or H is almost
simple and the socle of H acts absolutely irreducibly on V . Following [68],
we use S to denote the latter collection of non-geometric subgroups. In
turn, we write S = S1 ∪ S2 where a subgroup H ∈ S is in S1 if its socle is
a group of Lie type in the defining characteristic p. A brief description of
these subgroup collections is presented in Table 2.2.
Some further conditions are imposed on the subgroups in S to avoid
containment in a geometric subgroup collection. For instance, suppose G0 =
PSLn (q) and H ∈ S has socle H0 . Let
b 0 → GL(V )
ρ:H
b 0 is the
be the corresponding absolutely irreducible representation (where H
b 0 ) does not fix a non-degenerate form
full covering group of H0 ). Then ρ(H
on V and the representation cannot be realised over a proper subfield of Fq
b 0 )).
(see [68, p.3] for a complete list of the conditions satisfied by ρ(H
It turns out that a small additional subgroup collection (denoted by N )
arises when G0 = PSp4 (q)0 (with q even) or PΩ+
8 (q), due to the existence
of certain exceptional automorphisms (the maximal subgroups in the latter
case have been determined by Kleidman [67]).
The definitive reference for information on the structure, maximality and
conjugacy of the geometric subgroups is the book by Kleidman and Liebeck

14

C1
C2
C3
C4
C5
C6
C7
C8
S
N

Stabilisers of subspaces, or pairs of subspaces, of V
L
Stabilisers of decompositions V = ti=1 Vi , where dim Vi = a
Stabilisers of prime degree extension fields of Fq
Stabilisers of decompositions V = V1 ⊗ V2
Stabilisers of prime index subfields of Fq
Normalisers of symplectic-type r-groups, r 6= p
N
Stabilisers of decompositions V = ti=1 Vi , where dim Vi = a
Stabilisers of nondegenerate forms on V
Almost simple absolutely irreducible subgroups
0
Novelty subgroups (G0 = PΩ+
8 (q) or PSp4 (q) (p = 2), only)
Table 2.2. Aschbacher’s subgroup collections

[68]. More recently, the maximal subgroups of the low-dimensional classical
groups with n 6 12 have been completely determined by Bray, Holt and
Roney-Dougal in [14].
Example 2.8. If G0 = PSL6 (q) then the subgroups comprising the geometric Ci collections are described below (note that the C6 and C7 collections
are empty). Here we refer to the type of a subgroup H, which provides an
approximate description of the group-theoretic structure of H (the precise
structure is presented in [14, 68]).
C1 : Parabolic subgroups Pm with m ∈ {1, 2, 3, 4, 5}, where Pm = GU for
an m-dimensional subspace U of V .
In addition, if G contains a graph (or graph-field) automorphism τ of
G0 then C1 also includes the stabilisers of the form GU,W , where U, W are
non-zero subspaces of V with 6 = dim U + dim W and either U ⊂ W or
V = U ⊕ W . (Note that if G = hG0 , τ i and m 6= 3 then Pm < G0 < G since
dim U τ = 6 − m.)
C2 : Stabilisers of direct sum decompositions of the form V = V1 ⊕ V2 or
V = U1 ⊕ U2 ⊕ U3 , where dim Vi = 3 and dim Ui = 2. These subgroups are
of type GL3 (q) o Sym(2) and GL2 (q) o Sym(3), respectively.
C3 : Field extension subgroups of type GL3 (q 2 ) and GL2 (q 3 ).
C4 : Tensor product subgroups of type GL3 (q) ⊗ GL2 (q).
C5 : Subfield subgroups of type GL6 (q0 ), where q = q0k for some prime k.
C8 : Classical subgroups of type Sp6 (q) and O±
6 (q) (with q odd in the
2
latter case), and also type GU6 (q0 ) if q = q0 .
In addition, the possible socles of the subgroups in S are as follows (see
[14, Table 8.25]):
Alt(6), Alt(7), PSL2 (11), M12 , PSL3 (4), PSU4 (3), PSL3 (q).
Note that the latter subgroup arises from the symmetric-square representation S 2 (W ) of SL3 (q), where W is the natural module for SL3 (q).

2. SIMPLE GROUPS

15

When studying fixed point ratios for classical groups, it is natural to
distinguish between those actions which permute subspaces of the natural
module and those which do not. This leads us naturally to the following
definition.
Definition 2.9. Let G 6 Sym(Ω) be an almost simple primitive classical group over Fq with socle G0 , natural module V and point stabiliser H.
The action of G on Ω is a subspace action if one of the following holds for
each maximal subgroup M of G0 containing H ∩ G0 :
(i) M is the stabiliser in G0 of a proper non-zero subspace U of V ,
where U is totally singular, non-degenerate or, if G0 is orthogonal
and q is even, a non-singular 1-space (U can be any subspace if
G0 = PSLn (q)).
(ii) M = O±
n (q) if G0 = Spn (q) and q is even.
Example 2.10. If G0 = PSp6 (q) then the subspace actions correspond
to the following maximal subgroups H of G:
C1 : H = Pm = GU is a maximal parabolic subgroup, where U is a
totally singular m-space and m ∈ {1, 2, 3}.
C1 : H = GW is of type Sp4 (q) × Sp2 (q), where W is a non-degenerate
2-space.
−
C8 : H is of type O+
6 (q) or O6 (q), and q is even.
Note that a subgroup H of the latter type is the stabiliser of a non-degenerate
quadratic form on V . However, if we consider the isomorphism Sp6 (q) ∼
=
O7 (q) (where O7 (q) is the isometry group of a non-singular quadratic form
on a 7-dimensional space over Fq ), then H corresponds to the stabiliser of
an appropriate non-degenerate 6-space. This explains why we include these
subgroups in Definition 2.9.
In general, notice that subspace actions correspond to maximal subgroups in the collection C1 (in addition to the special C8 -subgroups that
arise when G is a symplectic group in even characteristic).
As previously remarked, it is sensible to make a distinction between subspace and non-subspace actions when studying fixed point ratios for classical
groups. In general, the stabilisers for subspace actions tend to be large subgroups, such as maximal parabolic subgroups, so it is natural to expect that
fpr(x) = |xG ∩ H|/|xG | will also be large in this situation. For example,
we demonstrated the sharpness of Theorem 2.6 by considering the action
of PGLn (q) on 1-spaces. Therefore, it is reasonable to expect that better
bounds can be established if we exclude subspace actions. In addition, we
have a very concrete description of subspace actions, which may permit direct calculation, so it also makes sense to treat them separately from this
point of view.
2.5. Subspace actions of classical groups. Let G 6 Sym(Ω) be a
primitive almost simple classical group over Fq in a subspace action with
socle G0 and natural module V . Fix an element x ∈ G ∩ PGL(V ) and write
x = x̂Z, where x̂ ∈ GL(V ) and Z denotes the centre of GL(V ). Since we
can identify Ω with a collection of subspaces (or pairs of subspaces) of V , it

16

is natural to expect that fpr(x) will reflect certain properties of the action
of x on V . For instance, in Example 1.4 we observed that fpr(x) = q d−n
for the natural action of GLn (q) on V = Fnq , where d = dim CV (x) is the
dimension of the 1-eigenspace of x on V . To formalise this, we introduce the
following notation (recall that if y ∈ GL(W ), then [W, y] is the subspace of
W spanned by the vectors of the form w − wy, for w ∈ W ).
Definition 2.11. For x ∈ PGL(V ), let x̂ be a pre-image of x in GL(V )
and define
ν(x) = min{dim[V̄ , λx̂] : λ ∈ K × },
where V̄ = V ⊗ K and K is the algebraic closure of Fq . Note that ν(x) is
equal to the codimension of the largest eigenspace of x̂ on V̄ .
Example 2.12. Consider the action of G = PSpn (q) on the set Ω of
2-dimensional non-degenerate subspaces of V . Assume q is odd and set
x = x̂Z, where x̂ = [−Im , In−m ] and 0 < m < n/2 with respect to an
appropriate symplectic basis of V . The eigenspaces U and W of x̂ are nondegenerate, so m = dim U = ν(x) is even and x stabilises the orthogonal
decomposition V = U ⊥ W . Since G acts transitively on Ω we have
|Ω| =

|Spn (q)|
∼ q 2(n−2) .
|Sp2 (q)||Spn−2 (q)|

Clearly, x fixes a non-degenerate 2-space if and only if it is contained in
either U or W , so
|CΩ (x)| =

|Spn−m (q)|
|Spm (q)|
+
∼ q 2(m−2) + q 2(n−m−2)
|Sp2 (q)||Spm−2 (q)| |Sp2 (q)||Spn−m−2 (q)|
∼ q 2(n−m−2)

and thus fpr(x) ∼ q −2m = q −2ν(x) .
The most general result for subspace actions is the following theorem
of Frohardt and Magaard [44], which shows that the previous example is
typical for all subspace actions.
Theorem 2.13. Fix  > 0 and let G 6 Sym(Ω) be a primitive almost
simple classical group over Fq with natural module V , where Ω is an appropriate set of k-subspaces of V . Then there exists an integer N = N (q, )
such that if dim V > N then
fpr(x) < q −ν(x)k + 
for all 1 6= x ∈ G ∩ PGL(V ).
This is a somewhat simplified version of their main result. Indeed, [44]
provides a suitably modified version of the theorem that holds for all nonidentity elements in G, together with explicit upper and lower bounds on
fpr(x). For instance, [44, Theorem 1] states that if G0 = PSLn (q), n > 5
and Ω is the set of k-dimensional subspaces of V , then either
(a) fpr(x) 6 9q −(n−1)/2 , or
(b) x ∈ G ∩ PGL(V ), ν(x) 6 n/2k and
q −ν(x)k − q −n 6 fpr(x) 6 q −ν(x)k + 11q −n/2 .

2. SIMPLE GROUPS

17

We also refer the reader to [51, Section 3] for some alternative upper
bounds on max16=x∈G fpr(x) for subspace actions (this work of Guralnick and
Kantor was motivated by very different applications, which we will discuss
in Section 3).
2.6. Non-subspace actions of classical groups. Now let us turn to
the non-subspace actions of classical groups. Here it is natural to distinguish between geometric and non-geometric actions. For geometric actions,
we have a rather concrete description of the embedding of H = Gα in G,
which permits a detailed analysis of the conjugacy classes in H and, more
importantly, their fusion in G. In this way, it is possible to compute accurate
fixed point ratio estimates for geometric actions.
Example 2.14. Suppose G = PSp12 (q) and H is a C2 -subgroup of G of
type Sp4 (q) o Sym(3), so H is the stabiliser of an orthogonal decomposition
V = V1 ⊥ V2 ⊥ V3 and each Vi is a nondegenerate 4-space. Let Z denote
the centre of Sp12 (q). Assume q ≡ 1 (mod 3) and set x = x̂Z ∈ G where
x̂ = [I6 , λI3 , λ2 I3 ] and λ ∈ Fq is a primitive cube root of unity (here we are
thinking of x̂ as a diagonal matrix, with respect to an appropriate basis).
Since two semisimple elements in a symplectic group are conjugate if and
only if they have the same eigenvalues (in a splitting field), we see that
H
3
xG ∩ H = xH
1 ∪ x2 where x̂1 , x̂2 ∈ Sp4 (q) are as follows:
x̂1 = ([I4 ], [I2 , λ, λ2 ], [λI2 , λ2 I2 ]), x̂2 = ([I2 , λ, λ2 ], [I2 , λ, λ2 ], [I2 , λ, λ2 ]).
Therefore
|Sp4 (q)|
|Sp4 (q)|
·
+
|x ∩ H| = 3! ·
|Sp2 (q)||GL1 (q)| |GL2 (q)|
G



|Sp4 (q)|
|Sp2 (q)||GL1 (q)|

3

∼ 6q 12 + q 18
and
|xG | =

|Sp12 (q)|
∼ q 48 ,
|Sp6 (q)||GL3 (q)|

so fpr(x) ∼ q −30 ∼ |xG |−5/8 (we refer the reader to [25, Chapter 3] for
detailed information on the centralisers of elements of prime order in finite
classical groups).
We require different methods to handle the non-geometric actions of
classical groups. Indeed, in general we are unable to determine the maximal
subgroups H ∈ S for a given classical group G. Of course, we do not even
know the dimensions of the irreducible representations of simple groups,
let alone information on the embedding of H in G that might allow us
to understand the fusion of the relevant conjugacy classes! However, as
described below in Section 2.7, there are ways to overcome these obstacles
for the purposes of estimating fixed point ratios.
A key result on non-subspace actions is the following theorem of Liebeck
and Shalev [81], which plays a major role in several important applications.
A nice feature of this result is that the upper bound depends on the size of
the conjugacy class of the element.

18

Theorem 2.15. There is an absolute constant  > 0 such that
fpr(x) < |xG |−
for all x ∈ G of prime order and for every primitive almost simple classical
group G in a non-subspace action.
It is easy to see that this result does not extend to subspace actions.
For example, if we consider the action of G = PGLn (q) on 1-spaces and
we choose x ∈ G with ν(x) = 1 then |xG | ∼ q 2n−2 but fpr(x) ∼ q −1 .
In particular, Theorem 2.15 implies that fpr(x) tends to 0 as |G| tends to
infinity (for classical groups acting on subspaces of a fixed dimension, we
only get this limiting behaviour as the field size tends to infinity).
The constant  in Theorem 2.15 is undetermined and with applications
in mind it is desirable to pin down an explicit estimate. The main theorem
of [19] implies that  ∼ 1/2 is optimal.
Theorem 2.16. Let G be a primitive almost simple classical group in a
non-subspace action with point stabiliser H and natural module of dimension
n. Then
1
fpr(x) < |xG |− 2 +η
for all x ∈ G of prime order, where η → 0 as n → ∞.
This is a simplified version of [19, Theorem 1], which is proved in the
sequence of papers [20, 21, 22]. Indeed, one can take −1/2 + 1/n + δ for
the exponent, where δ = 0, or (G, H, δ) is one of a small number of known
exceptions (in every case, δ → 0 as n → ∞). The next example shows that
there is not much room for improvement in this exponent.
Example 2.17. Suppose G = PSLn (q) and H is a C8 -subgroup of type
O+
(q),
so n is even and q is odd. Let x ∈ G be an involution such that
n
x̂ = [−Im , In−m ] with m even. Then
|xG ∩ H| =

|O+
n (q)|
+
|Om (q)||O+
n−m (q)|

and
|xG | =

+

|O+
n (q)|
−
|Om (q)||O−
n−m (q)|

∼ q m(n−m)

|GLn (q)|
∼ q 2m(n−m)
|GLm (q)||GLn−m (q)|

so fpr(x) ∼ q −m(n−m) ∼ |xG |−1/2 .
There are many other examples that demonstrate the accuracy of the
bound in Theorem 2.16. For instance, if q = q02 and H is a subfield subgroup
of G defined over Fq0 then |xG ∩ H| ∼ |xG |1/2 for all x ∈ G with fixed points,
so fpr(x) ∼ |xG |−1/2 .
The proof of Theorem 2.16 is given in [20, 21, 22]. To handle the
relevant geometric actions we combine detailed information on the structure
of the maximal geometric subgroups in [68] (which is organised according
to the subgroup collections arising in Aschbacher’s theorem) with a careful
analysis of the conjugacy classes and fusion of elements of prime order.
A different approach is needed to deal with the non-geometric actions
corresponding to the maximal subgroups in the collection S. We will briefly
describe the main ingredients in the next section.

2. SIMPLE GROUPS

19

2.7. S-actions of classical groups. Let G, H and n be given as in
the statement of Theorem 2.16. Let G0 be the socle of G, which is a simple
classical group over Fq (for q = pf , p prime) with natural module V of
b 0 → GL(V ) be the
dimension n. Assume H ∈ S has socle H0 and let ρ : H
corresponding absolutely irreducible representation.
If n is small, say n 6 5, then the possibilities for (G, H, ρ) are well known
(see [14]) and it is straightforward to work directly with the representation
ρ (and its Brauer character) to obtain sufficient information on the fusion
of H-classes in G to compute (or accurately estimate) fixed point ratios.
Now assume n > 6. Let us write H ∈ A if q = p, H0 = Alt(m) is an
alternating group and V is the fully deleted permutation module for H0 over
Fq (in which case n = m − 2 or m − 1). We can now state the following
result, which combines the main theorem of [73] with [54, Theorem 7.1].
Theorem 2.18. Let G be a primitive almost simple classical group over
Fq with socle G0 , point stabiliser H ∈ S \ A and natural module V of dib 0 → GL(V ) be the corresponding representation.
mension n > 6. Let ρ : H
Then the following hold:
(i) |H| < q 3nα , where α = 2 if G0 is unitary, otherwise α = 1;
√
(ii) Either ν(x) > max{2, n/2} for all 1 6= x ∈ H ∩ PGL(V ), or
n 6 10 and (G, H, ρ) belongs to a short list of known exceptions.
Remark 2.19.
(a) The bound in part (i) of the theorem can be sharpened, at the
expense of some additional (known) exceptions. For instance, see
[73, Theorem 4.2] and [27, Theorem 2.10] for improvements with
q 3nα replaced by q (2n+4)α and q 2n+4 , respectively (for example, the
case (G, H) = (PSL27 (q), E6 (q)) is an exception to the bound |H| <
q 2n+4 ).
(b) We can view the bound in (ii) as a linear analogue of the aforementioned bounds of Babai, Liebeck and Saxl on the minimal degree
of a primitive permutation group (with irreducibility in place of
primitivity); see Section 2.2.
(c) The bound in (ii) is close to best possible if we impose the condition
that the only exceptions occur in small dimensions. To see this,
suppose n = m2 where m > 3 is odd. If q is chosen appropriately
then G = PSLn (q) has a maximal subgroup H ∈ S with socle H0 =
PSLm (q 2 ), which is embedded in G via the module W ⊗ W (q) for
b 0 = SLm (q 2 ), where W is the natural module for H0 and W (q) is
H
the q-power Frobenius twist of W . If we take x =
√ [−Im−1 , I1 ] ∈ H0
then it is easy to check that ν(x) = 2m − 2 < 2 n.
The proof of Theorem 2.15 also uses the bound in part (i) of Theorem
2.18, but the bound in (ii) is a crucial new ingredient in the proof of Theorem
2.16. The cases in A, and also the small number of low-dimensional exceptions arising in part (ii) of Theorem 2.18, are well understood embeddings
and they can be handled directly.
Generically, Theorem 2.18 tells us that H is small and the elements
in H ∩ PGL(V ) have relatively small eigenspaces on V . In particular, the

20

latter property yields a lower bound |xG | > f (n, q) for all x ∈ H ∩ PGL(V )
of prime order, so we get
(2.3)

fpr(x) =

|xG ∩ H|
|H|
q 3nα
<
<
.
|xG |
|xG |
f (n, q)

Note that if x ∈ H \ PGL(V ) has prime order then x is either a field, graph
or graph-field automorphism of G0 and it is straightforward to check that
the inequality |xG | > f (n, q) still holds, so (2.3) is valid for all x ∈ H of
prime order.
Example 2.20. Suppose G = PSLn (q), H ∈ S \ A and√n > 10. Let
x ∈ H be an element of prime order with ν(x) = s, so s > d n/2e = β by
Theorem 2.18(ii). It is not too difficult to show that
1
|xG | > q 2β(n−β)
2
(see [20, Corollary 3.38]) so we get fpr(x) < |xG |−1/2 if
1
q 6n < q 2β(n−β) .
2
One checks that this inequality holds if n > 36, so we may assume that
n 6 36. In fact, if we replace the bound in part (i) of Theorem 2.18 by
|H| < q 2n+4 (at the expense of a small number of known exceptions (see
[73, Theorem 4.2]), which can be handled separately), then we can reduce
to the case where n 6 16. At this point we can turn to results of Lübeck
[84] (in defining characteristic) and Hiss and Malle [59, 60] (in non-defining
characteristic) to determine the possibilities for (G, H, ρ) and we can then
work directly with these cases.
2.8. Exceptional groups. Finally, let us say a few words on fixed
point ratios for exceptional groups. Let G 6 Sym(Ω) be a primitive almost simple exceptional group of Lie type over Fq with socle G0 and point
stabiliser H. Recall that Theorem 2.6 gives
max fpr(x) 6

16=x∈G

4
3q

and it is natural to ask if this upper bound can be improved.
In [46], Frohardt and Magaard obtain close to best possible upper bounds
in the special case where the rank of G is at most 2. For example, they prove
that
(
1
if G0 ∈ {G2 (q), 2 G2 (q)} and q > 4,
q 2 −q+1
max fpr(x) =
1
if G0 = 3 D4 (q).
16=x∈G
q 4 −q 2 +1
In [71], using different methods, Lawther, Liebeck and Seitz present a
detailed analysis of fixed point ratios for all the exceptional groups. For
instance, [71, Theorem 1] gives

1

 q8 (q4 −1) if G0 = E8 (q)
1
if G0 ∈ {E7 (q), 2 E6 (q)}
max fpr(x) 6
q 6 −q 3 +1

16=x∈G
1

if G0 ∈ {E6 (q), F4 (q)},
q 4 −q 2 +1

2. SIMPLE GROUPS

21

with equality if G0 = E6 (q), 2 E6 (q) or F4 (q). More detailed bounds are given
in [71, Theorem 2], which depend not only on G, but also on the choice of
H and x to some extent. For example, if G = E8 (q) and H does not contain
a maximal torus of G, then [71, Theorem 2] states that fpr(x) 6 q −48 for
all non-identity semisimple elements x ∈ G.
As for classical groups, the proofs rely on detailed information on the
subgroup structure and conjugacy classes of the finite exceptional groups.
In particular, there is a fundamental reduction theorem for subgroups due
to Liebeck and Seitz, which plays a similar role to Aschbacher’s theorem for
classical groups (see [77, Theorem 8], for example). We finish by highlighting
two other important ingredients in [71].
2.8.1. Parabolic actions. The special case where H is a maximal parabolic subgroup is studied using tools from the character theory of finite
groups of Lie type, such as the Deligne-Lusztig theory and Green functions.
These sophisticated techniques can be used to obtain very precise fixed point
ratio estimates.
For example, suppose G = E8 (q), H = P8 and x ∈ G is unipotent
(here our notation indicates that H corresponds to the 8-th node in the
Dynkin diagram of G, labelled in the usual way, so the Levi factor of H is
of type E7 (q)). Then |Ω| ∼ q 57 and one can show that the corresponding
permutation character admits the decomposition
X
1G
(x)
=
nφ Rφ (x)
H
c
φ∈W

= Rφ1,0 (x) + Rφ8,1 (x) + Rφ35,2 (x) + Rφ112,3 (x) + Rφ84,4 (x),
c = Irr(W ) and W is the Weyl group of G. The Rφ are almost
where W
characters of G and the coefficients are given by nφ = h1W
WP , φi, where WP
is the corresponding parabolic subgroup of W . The restriction of the Rφ
to unipotent elements x ∈ G are called Green functions; each Rφ (x) is a
polynomial in q with non-negative coefficients. Lübeck has implemented an
algorithm of Lusztig to compute the relevant Green functions (modulo a sign
issue for certain elements) and his calculations yield very precise estimates
for fpr(x) (see [71, Section 2] for more details). For example, if x ∈ G
is a long root element then 1G
H (x) can be computed precisely in this way;
we get a certain monic polynomial in q of degree 45, which implies that
fpr(x) 6 1/q 8 (q 4 − 1). This turns out to be the largest fixed point ratio for
any non-identity element of G.
2.8.2. Algebraic groups. Results on the dimensions of fixed point spaces
for primitive actions of exceptional algebraic groups also play a key role in
[71]. In the general set up, Ḡ is a simple algebraic group over the algebraic
closure K = F̄q and σ is a Frobenius morphism of Ḡ such that G0 is the
derived subgroup of Ḡσ = {x ∈ Ḡ : xσ = x}. Let H̄ be a σ-stable closed
subgroup of Ḡ and let Γ = Ḡ/H̄ be the corresponding coset variety, which
is naturally a Ḡ-variety over K. Then the fixed point space CΓ (x) is a
subvariety for each x ∈ Ḡ, and we may compare the dimensions of Γ and
CΓ (x). In analogy with Lemma 1.2(iii), we have
dim CΓ (x) − dim Γ = dim(xḠ ∩ H̄) − dim xḠ

22

for all x ∈ H̄ (see [70, Proposition 1.14]). Moreover, if we set H = H̄σ then
fpr(x) =

|xG ∩ H|
Ḡ
Ḡ
∼ q dim(x ∩H̄)−dim x
G
|x |

for all x ∈ H (see [71, Lemma 4.5], for example). In this way, if H corresponds to a σ-stable closed subgroup of Ḡ, then it is possible to use dimension bounds at the algebraic group level to study fixed point ratios for the
finite group G.
This interplay between finite and algebraic groups is applied repeatedly
in [71], using results obtained for primitive actions of exceptional algebraic
groups in the companion paper [70]. Similar considerations also play a role
in the analysis of geometric actions of finite classical groups in the proof of
Theorem 2.16, using results for classical algebraic groups in [18].
3. Generation and random generation
In this section we discuss applications of fixed point ratios to problems
concerning the generation and random generation of finite groups. In particular, we will explain how fixed point ratios play a key role in the solution to
Problem A on generating graphs of simple groups stated in the introduction.
3.1. Simple groups. Recall that a group is n-generated if it can be
generated by n elements. For instance, dihedral and symmetric groups are
2-generated, e.g. we have Sym(n) = h(1, 2), (1, 2, . . . , n)i. The following
theorem (essentially due to Steinberg [98]) is the starting point for the
investigation of many interesting problems.
Theorem 3.1. Every finite simple group is 2-generated.
The proof relies on CFSG. The alternating groups are easy:

h(1, 2, 3), (1, 2, . . . , n)i n odd,
Alt(n) =
h(1, 2, 3), (2, 3, . . . , n)i n even.
In [98], Steinberg presents explicit generating pairs for each simple group of
Lie type. For instance, PSL2 (q) = hxZ, yZi, where Z = Z(SL2 (q)) and




µ 0
−1 1
x=
, y=
−1 0
0 µ−1
with F×
q = hµi. In [4], Aschbacher and Guralnick complete the proof of the
theorem by showing that every sporadic group is 2-generated.
Remark 3.2. By a theorem of Dalla Volta and Lucchini [36], every
almost simple group is 3-generated (there are such groups that really need
3 generators, e.g. take G = Aut(PSLn (q)) with nq odd and q = p2f with p
prime).
In view of Theorem 3.1, it is natural to consider the abundance of generating pairs in a finite simple group (or a sequence of such groups), or the
existence of generating pairs with special properties (such as prescribed orders). Problems of this flavour have been intensively investigated in recent
years.

3. GENERATION AND RANDOM GENERATION

23

3.2. Random generation. Let G be a finite group, let k be a positive
integer and let
P(G, k) =

|{(x1 , . . . , xk ) ∈ Gk : G = hx1 , . . . , xk i}|
|G|k

be the probability that k randomly chosen elements generate G.
Conjecture 3.3 (Netto [88], 1882). “If we arbitrarily select two or
more substitutions of n elements, it is to be regarded as extremely probable
that the group of lowest order which contains these is the symmetric group,
or at least the alternating group.”
In our terminology, Netto is claiming that limn→∞ P(Alt(n), 2) = 1.
This remarkable conjecture was proved by Dixon [37] in a highly influential
paper published in 1969, which relies in part on the pioneering work of Erdös
and Turán in the mid-1960s on statistical properties of symmetric groups.
In the same paper, Dixon makes the bold conjecture that all finite simple
groups are strongly 2-generated in the sense of Netto.
Conjecture 3.4. Let (Gn ) be any sequence of finite simple groups such
that |Gn | tends to infinity with n. Then limn→∞ P(Gn , 2) = 1.
Dixon’s conjecture was eventually proved in the 1990s. In [65], Kantor
and Lubotzky establish the conjecture for classical groups and low rank
exceptional groups, and the remaining exceptional groups were handled by
Liebeck and Shalev [78].
In both papers, the strategy of the proof is based on an elementary
observation. Let M be the set of maximal subgroups of G and let x, y ∈ G
be randomly chosen elements. If G 6= hx, yi then x, y ∈ H for some H ∈ M.
The probability of this event is |G : H|−2 , so
X
1 − P(G, 2) 6
|G : H|−2 =: Q(G).
H∈M

By carefully studying M, using recent advances in our understanding of the
subgroup structure of the simple groups of Lie type (such as Aschbacher’s
theorem for classical groups), one shows that Q(G) → 0 as |G| tends to
infinity, and the result follows.
Note that this probabilistic approach shows that every sufficiently large
finite simple group is 2-generated, without the need to explicitly construct
a pair of generators. Many interesting related results have been established
in more recent years. For example, the following result is [87, Theorem 1.1].
Theorem 3.5. We have P(G, 2) > 53/90 for every finite simple group
G, with equality if and only if G = Alt(6).
3.3. Spread. The following 2-generation property was introduced by
Brenner and Wiegold [15] in the 1970s.
Definition 3.6. Let G be a finite group and let k be a positive integer.
Then G has spread at least k if for any non-identity elements x1 , . . . , xk ∈ G
there exists y ∈ G such that G = hxi , yi for all i. We say that G is 32 generated if it has spread at least 1.

24

We will also be interested in the more restrictive notion of uniform
spread, which was introduced more recently in [16].
Definition 3.7. We say that G has uniform spread at least k if there
exists a fixed conjugacy class C of G such that for any non-identity elements
x1 , . . . , xk ∈ G there exists y ∈ C such that G = hxi , yi for all i.
Clearly, every cyclic group has uniform spread at least k for all k ∈ N,
so for the remainder of this discussion let us assume G is non-cyclic. Set
s(G) = max{k ∈ N0 : G has spread at least k}
u(G) = max{k ∈ N0 : G has uniform spread at least k}
(so u(G) = 0 if G does not have uniform spread at least 1, etc.). Note that
u(G) 6 s(G) < |G| − 1 and there are examples with u(G) < s(G). For
example, if G = Sym(6) then u(G) = 0 and s(G) = 2. Note that G is
3
2 -generated if and only if s(G) > 1.
In [15], Brenner and Wiegold study the spread of the simple groups
Alt(n) and PSL2 (q). Among other things, they prove that s(Alt(2m)) = 4
if m > 4 and s(PSL2 (q)) = q − 2 if q is even.
The following theorem of Breuer, Guralnick and Kantor is the main
result on the spread of simple groups (see [16, Corollary 1.3]).
Theorem 3.8. Let G be a nonabelian finite simple group. Then u(G) >
2, with equality if and only if
(3.1)

G ∈ {Alt(5), Alt(6), Ω+
8 (2), Sp2m (2) (m > 3)}.

It turns out that u(G) = s(G) = 2 for each of the groups in (3.1).
Remark 3.9. The weaker bound u(G) > 1 was originally obtained by
Stein [97], and independently by Guralnick and Kantor [51]. In the latter
paper, the authors prove that there is a conjugacy class C of G such that
each non-identity element of G generates G with at least 1/10 of the elements
in C, and they also establish some related results for almost simple groups.
In [16], the constant 1/10 is replaced by 13/42 (for G = Ω+
8 (2), this is best
possible). In fact, with the exception of a known finite list of small groups,
plus the family of symplectic groups over F2 , 1/10 can be replaced by 2/3
(see [16, Theorem 1.1]). As explained below, this result is the key ingredient
in the proof of Theorem 3.8. We also note that in an earlier paper, Guralnick
and Shalev proved that u(G) > 2 for all sufficiently large simple groups G
(see [55, Theorem 1.2]).
Fixed point ratios play a central role in the proof of Theorem 3.8. Let
us explain the connection. Let G be a finite group. For x, y ∈ G, let
|{z ∈ y G : G = hx, zi}|
|y G |
be the probability that x and a randomly chosen conjugate of y generate G.
Set
Q(x, y) = 1 − P(x, y).
P(x, y) =

Lemma 3.10. Suppose there exists an element y ∈ G and a positive
integer k such that Q(x, y) < 1/k for all 1 6= x ∈ G. Then u(G) > k.

3. GENERATION AND RANDOM GENERATION

25

Proof. Let x1 , . . . , xk ∈ G be non-identity elements and let E denote
the event E1 ∩· · ·∩Ek , where Ei is the event that G = hxi , zi for a randomly
chosen conjugate z ∈ y G . Let P(E) be the probability that E occurs and let
Ē be the complementary event (and similarly for P(Ei ) and Ēi ). We need
to show that P(E) > 0. To see this, we note that
P(E) = 1 − P(Ē) = 1 − P(Ē1 ∪ · · · ∪ Ēk ) > 1 −

k
X

P(Ēi ) = 1 −

i=1

so P(E) > 1 − k ·

1
k

= 0 and the result follows.

k
X

Q(xi , y)

i=1



Let M(y) be the set of maximal subgroups of G containing y. The
following result is the main tool in the proof of Theorem 3.8.
Corollary 3.11. Suppose there is an element y ∈ G and a positive
integer k such that
X
1
fpr(x, G/H) <
k
H∈M(y)

for all elements x ∈ G of prime order. Then u(G) > k.
Proof. In view of Lemma 3.10, it suffices to show that
X
Q(x, y) 6
fpr(x, G/H)
H∈M(y)

for all 1 6= x ∈ G. Fix a non-identity element x ∈ G and let z ∈ y G . Then
G 6= hx, zi if and only if hx0 , yi 6 H for some x0 ∈ xG and H ∈ M(y), so we
have
X
Q(x, y) 6
Px (H),
H∈M(y)

where Px (H) is the probability that a randomly chosen conjugate of x lies
in H. Now
|xG ∩ H|
= fpr(x, G/H)
Px (H) =
|xG |
and the result follows.

The key step in applying Corollary 3.11 is to carefully choose y ∈ G
so that it belongs to very few maximal subgroups of G, with the essential
extra property that we can explicitly determine the subgroups in M(y), or
at least a collection of maximal subgroups containing M(y) that is not too
much bigger. This means that there is some flexibility in the approach – the
optimal choice of y is not always obvious (in practice, it seems that there
are many valid possibilities, but some will require more work than others).
Example 3.12. Let’s use this approach to prove that u(Alt(5)) > 2.
Set G = Alt(5) and y = (1, 2, 3, 4, 5) ∈ G. The maximal subgroups of
G are isomorphic to Sym(3), Alt(4) and D10 , and it is easy to see that
M(y) = {K} with
K = h(1, 2, 3, 4, 5), (1, 2)(3, 5)i = D10 .

26

We now compute

 1/3 |x| = 2
0
|x| = 3
fpr(x, G/H) = fpr(x, G/K) =

1/6 |x| = 5
H∈M(y)
X

and thus u(G) > 2 by Corollary 3.11. In fact, we have u(G) = 2 (see
Theorem 3.8), which shows that the strictness of the inequality in Corollary
3.11 is essential. As an aside, one can check that the class of 3-cycles has
the uniform spread 1 property, but not spread 2.
Example 3.13. We claim that u(G) > 3 if G = Alt(n) and n > 8 is
even (recall the result of Brenner and Wiegold, which states that s(G) = 4).
To see this, set n = 2m and k = m − (2, m − 1). Fix y ∈ G with cycle-shape
[k, n − k] and note that (k, n − k) = 1. We claim that M(y) consists of
a single intransitive subgroup H of type Sym(k) × Sym(n − k). It is clear
that H is the only intransitive subgroup in M(y), so assume M ∈ M(y) is
transitive. The cycle-shape of y implies that M is primitive, but hyi contains
a k-cycle and thus M = G by a classical result of Marggraf (1892), which is
a contradiction (Marggraf’s theorem implies that the only primitive groups
of degree n containing a cycle of length ` < n/2 are Sym(n) and Alt(n); see
[101, Theorem 13.5]). This justifies the claim. It remains to estimate fixed
point ratios with respect to the action of G on k-sets. A straightforward
combinatorial argument shows that fpr(x) < 1/3 for all x ∈ G of prime
order (see the proof of [16, Proposition 6.3]) and the result follows.
Remark 3.14. The analysis of odd degree alternating groups is slightly
more complicated. In this situation, no elements have precisely two cycles,
so one is forced to work with n-cycles, which may belong to several maximal
subgroups.
Remark 3.15. By a theorem of Guralnick and Shalev [55, Theorem 1.1],
if Gi = Alt(ni ) and ni tends to infinity with i, then s(Gi ) tends to infinity if
and only if p(ni ) tends to infinity, where p(ni ) is the smallest prime divisor
of ni .
Let us also comment on the proof of Theorem 3.8 for classical groups,
which require the most work. To illustrate some of the main ideas, we
will assume that G = PSLn (q) and n > 13 is odd. Following [16], fix a
semisimple element y ∈ G preserving a decomposition V = U ⊕ W of the
natural module, where dim U = k = (n − 1)/2 and y acts irreducibly on U
and W . We claim that M(y) = {GU , GW }, which quickly implies that
X
1
fpr(x, G/H) = 2 · fpr(x, G/GU ) <
3
H∈M(y)

for all x ∈ G of prime order (note that the actions of G on k-subspaces
and (n − k)-subspaces of V are permutation isomorphic and fpr(x, G/GU ) =
fpr(x, G/GW ) for all x ∈ G). For example, if q > 8 then fpr(x, G/GU ) 6 1/6
by Theorem 2.6. In particular, we conclude that u(G) > 3.
In order to determine the subgroups in M(y), it is very helpful to observe
that |y| is divisible by a primitive prime divisor of q n−k − 1 (that is, a prime
r such that n − k is the smallest positive integer i such that r divides q i − 1;

3. GENERATION AND RANDOM GENERATION

27

a2
a3

a

ab

a3 b

b

a2 b

Figure 3.1. The generating graph of D8 = ha, b | a4 = b2 =
1, ab = a−1 i

a classical theorem of Zsigmondy (1892) establishes the existence of such
primes if n − k > 3 and (n − k, q) 6= (6, 2)). The subgroups of classical
groups containing such ppd elements are studied in [53], where the analysis
is organised according to Aschbacher’s subgroup structure theorem. The
main theorem of [53] severely limits the possible subgroups in M(y), and
many of these possibilities can be ruled out by considering the order of y
(which is roughly (q n − 1)/(q − 1) since (k, n − k) = 1). We refer the reader
to the proof of [16, Proposition 5.23] for the details.
3.4. Generating graphs. The following notion first appeared in a paper by Liebeck and Shalev [80] on random generation.
Definition 3.16. Let G be a finite group. The generating graph Γ(G)
is a graph on the non-identity elements of G so that two vertices x, y are
joined by an edge if and only if G = hx, yi.
This graph encodes many interesting generation properties of the group.
For example,
G is 2-generated ⇐⇒ The edge-set of Γ(G) is non-empty
G has spread 1 ⇐⇒ Γ(G) has no isolated vertices
G has spread 2 =⇒ Γ(G) is connected with diameter at most 2
Moreover, the interplay between groups and graphs suggests many natural problems. For instance, what is the (co)-clique number and chromatic
number of Γ(G)? Does Γ(G) contain a Hamiltonian cycle?
In view of Theorem 3.1, it makes sense to study the generating graphs
of finite simple groups. Moreover, the fact that simple groups are strongly
2-generated (in the probabilistic sense of Netto and Dixon (see Conjecture
3.4), for example, or in the sense of spread, as in Theorem 3.8) suggests that
the corresponding generating graphs should have lots of edges and therefore
strong connectivity properties.
Example 3.17. If G = Alt(5) then Γ(G) has 59 vertices and one checks
that there are 1140 edges. It also has clique number 8, chromatic number

28

9 and coclique number 15 (for example, a maximal coclique is given by the
set of 15 elements of order 2).
The following result summarises some of the main results on generating
graphs for simple groups.
Theorem 3.18. Let G be a nonabelian finite simple group and let Γ(G)
be its generating graph.
(i) Γ(G) has no isolated vertices.
(ii) Γ(G) is connected and has diameter 2.
(iii) Γ(G) contains a Hamiltonian cycle if |G| is sufficiently large.
Proof. Clearly, (ii) implies (i), and (ii) is an immediate corollary of
Theorem 3.8. Part (iii) is one of the main results in [17] and we briefly
sketch the argument in the case where G is a group of Lie type. The three
main ingredients are as follows:
(a) By the proof of Dixon’s conjecture, we know that P(G, 2) → 1 as |G|
tends to infinity. More precisely, a theorem of Liebeck and Shalev
(see [80, Theorem 1.6]) states that there is a positive constant c1
such that
c1
P(G, 2) > 1 −
m(G)
for any nonabelian finite simple group G, where m(G) is the minimal index of a proper subgroup of G. Note that G 6 Sym(m(G)),
so m(G) tends to infinity with |G|.
(b) Set |G| = m + 1 (so m is odd) and let di be the degree of the i-th
vertex of Γ(G), where the vertices are labelled so that di 6 di+1
for all i. By a theorem of Fulman and Guralnick [48], there is a
positive constant c2 such that
d1 > c2 (m + 1)
(the constant c2 is independent of the choice of G).
(c) Pósa’s criterion: Γ(G) has a Hamiltonian cycle if dk > k + 1 for
all k < m/2 (see [83, Exercise 10.21(b)]).
If di > m/2 for all i then Pósa’s criterion immediately implies that Γ(G)
has a Hamiltonian cycle, so assume otherwise. Let t be maximal such that
dt < m/2 and observe that
m
X
1
1
2
(m+1) ·P(G, 2) =
di < (m−1)t+(m−t)(m+1) < (m+1)2 − (m+1)t.
2
2
i=1

Therefore, applying (a) we get
c1
t
1−
6 P(G, 2) 6 1 −
m(G)
2(m + 1)
and thus
2c1 (m + 1)
t6
6 c2 (m + 1) − 1
m(G)
if |G| is sufficiently large, where c2 is the constant in (b). It follows that if
1 6 k 6 t then
dk > d1 > c2 (m + 1) > t + 1 > k + 1.

3. GENERATION AND RANDOM GENERATION

29

Similarly, if t + 1 6 k < m/2 then dk > (m + 1)/2 > k + 1. Therefore,
Pósa’s criterion is satisfied and we conclude that Γ(G) has a Hamiltonian
cycle.

Let G be a 2-generated finite group and let N be a nontrivial normal
subgroup of G. Observe that if Γ(G) has no isolated vertices, then G/N
is cyclic (indeed, if 1 6= x ∈ N and G = hx, yi for some y ∈ G, then
G/N = hyN i is cyclic). The following conjecture is a combination (and
strengthening) of conjectures in [16, 17]:
Conjecture 3.19. Let G be a finite group with |G| > 4. Then the
following are equivalent:
(i) G has spread 1.
(ii) G has spread 2.
(iii) Γ(G) has no isolated vertices.
(iv) Γ(G) is connected.
(v) Γ(G) is connected with diameter at most 2.
(vi) Γ(G) contains a Hamiltonian cycle.
(vii) G/N is cyclic for every nontrivial normal subgroup N .
Remark 3.20. Some comments on the status of this conjecture:
(a) Note that any of the first six statements implies (vii). The following
implications are also obvious:
(i) ⇐⇒ (iii), (ii) =⇒ (v), (vi) =⇒ (iv) =⇒ (iii),
(v) =⇒ (iv) =⇒ (iii)
(b) By [17, Proposition 1.1], (vi) and (vii) are equivalent for soluble
groups.
(c) The conjectured equivalence of (i) and (vii) is [16, Conjecture 1.8],
and that of (vi) and (vii) is [17, Conjecture 1.6].
Notice that if the conjecture is true, then there is no finite group with
spread 1, but not spread 2.
Let us focus on the following weaker conjecture of Breuer, Guralnick and
Kantor.
Conjecture 3.21. Let G be a finite group. Then G has spread 1 if and
only if G/N is cyclic for every nontrivial normal subgroup N of G.
As noted above, Conjecture 3.21 has been verified for soluble groups.
More importantly, Guralnick has recently established the following reduction
theorem.
Theorem 3.22. It is sufficient to prove Conjecture 3.21 for almost simple groups.
In view of this result, we focus our attention on almost simple groups G
of the form G = hG0 , xi, where G0 is simple and x ∈ Aut(G0 ). The goal is
to prove that G has spread 1 (in fact, we aim for s(G) > 2). This is work
in progress:
• G0 = Alt(n) or sporadic: s(G) > 2 by results in [16].

30

• G0 = PSLn (q): s(G) > 2 by the main theorem of [26].
• G0 ∈ {PSpn (q), Ωn (q) (nq odd)}: s(G) > 2 by work of Scott Harper
(2016) in his PhD thesis (see [58]).
The goal is to use Corollary 3.11 to show that u(G) > 2. To do this,
we need to find a suitable element y ∈ G0 x so that we can determine the
maximal overgroups M(y) and estimate
X
fpr(x, G/H)
H∈M(y)

for all x ∈ G of prime order (to get spread 1, recall that we need to show
that this sum is less than 1). The set-up here is complicated by the fact
that we have to choose y in the coset G0 x, where x is typically a field or
graph automorphism of G0 . The following example illustrates some of the
main ideas in the situation where x is a field automorphism.
Example 3.23 (Harper). Let G0 = Spn (q), where q = q0e is even, e > 5
and n = 2m with m > 3 odd. Let X = Spn (K) be the ambient simple
algebraic group over the algebraic closure K = F̄q and let σ : X → X be a
Frobenius morphism such that Xσe = G0 . Set H0 = Xσ = Spn (q0 ) < G0 .
Suppose G = hG0 , xi, where x is the restriction of σ to G0 (this is a
field automorphism of order e). By the Lang-Steinberg theorem (see [99,
Theorem 10.1]), for each sx in the coset G0 x there exists a ∈ X such that
s = a−σ a. This allows us to define a map
(3.2)

f : {G0 -classes in G0 x} → {H0 -classes in H0 }

by sending (sx)G0 to (a(sx)e a−1 )H0 . One checks that f is well-defined and
bijective (this map is sometimes called the Shintani correspondence). One
can also show that f has nice fixed point properties for suitable actions of
G and H0 (see [26, Theorem 2.14], for example).
The strategy is to choose an element z ∈ H0 so that the maximal overgroups of z in H0 are somewhat restricted; hopefully this will allow us to control the maximal subgroups of G containing a representative y ∈ G0 x of the
corresponding G0 -class in the coset G0 x. To do this, we take a semisimple
element of the form z = [A, B] ∈ H0 , where A ∈ Sp2 (q0 ) and B ∈ Spn−2 (q0 )
are irreducible (so z preserves an orthogonal decomposition V0 = U ⊥ W of
the natural module V0 for H0 , with dim U = 2). Fix an element y ∈ G0 x
such that f (y G0 ) = z H0 .
We need to determine the maximal subgroups of G containing y. To do
this, it is helpful to observe that (|A|, |B|) = 1 so ν(y ` ) = 2 for some positive
integer `. This quickly rules out maximal subgroups in the collections C3 ,
C4 and C7 , and [54, Theorem 7.1] (cf. Theorem 2.18) can be used to further
restrict the possibilities for H. By exploiting some additional properties of
the bijection in (3.2) one can show that there is a unique reducible subgroup
in M(y) (of type Sp2 (q) × Spn−2 (q)) and also a unique C8 -subgroup of type
O±
n (q).
By carefully studying the subgroups in C2 ∪C5 , and by applying the fixed
point ratio bounds in Theorems 2.6 and 2.16, one can show that
X
fpr(x, G/H) < α
H∈M(y)

4. MONODROMY GROUPS

31

for all x ∈ G of prime order, where
 (4q + 4)1/2−1/2m
4 
α = 2· + 1 + 2(m−1,e) + (log(e) + 1)(q0 + 1)(q0m−1 + 1) ·
3q
q m−1
Now q > 32 since q = q0e with e > 5, and it is straightforward to show that
α < 1/3. Therefore u(G) > 3 by Corollary 3.11.
4. Monodromy groups
In this section we turn to an application of fixed point ratios in the study
of coverings of Riemann surfaces, focussing on the solution to Problem B
stated in the introduction.
4.1. Preliminaries. Let X be a compact connected Riemann surface
of genus g > 0 and let Y = P1 (C) be the Riemann sphere. Let f : X → Y
be a branched covering of degree n. This means that f is a meromorphic
function with a finite set of branch points B = {y1 , . . . , yk } ⊂ Y (with
k > 2) such that the restriction of f to X 0 = X \ f −1 (B) is a covering map
of degree n (that is, |f −1 (y)| = n for all y ∈ Y 0 = Y \ B, so generically f is
an “n-to-1” mapping).
Fix y0 ∈ Y 0 and let Ω = f −1 (y0 ) = {x1 , . . . , xn } be the fibre of y0 . Let γ
be a loop in Y 0 based at y0 . For each xi ∈ Ω, we can lift γ via f to a path γ̃i
in X beginning at xi . The endpoint γ̃i (1) is also in Ω and the corresponding
map σγ : xi 7→ γ̃i (1) is a permutation of Ω, which is independent of the
homotopy type of γ. In this way, we obtain a homomorphism
ϕ : π1 (Y 0 , y0 ) → Sym(Ω), [γ] 7→ σγ
from the fundamental group of Y 0 with base point y0 . The image of this
map is a permutation group of degree n. Moreover, the path connectedness
of Y 0 implies that the group we obtain in this way is independent of the
choice of base point y0 ∈ Y 0 , up to permutation isomorphism. This allows
us to make the following definition.
Definition 4.1. The monodromy group Mon(X, f ) of f is defined to be
the image of ϕ.
Since X has genus g, we refer to Mon(X, f ) as a monodromy group of
genus g. The connectedness of X implies that Mon(X, f ) is a transitive
permutation group.
Example 4.2. Let n > 2 be an integer and consider the map f : X → Y
given by f (z) = z n , where X = Y = P1 (C). This is a branched covering of
degree n with branch points B = {0, ∞} and Ω = f −1 (1) = {e2πik/n : k =
0, 1, . . . , n − 1}. Here the monodromy group is cyclic of order n, generated
by the permutation α 7→ ζα of Ω, with ζ = e2πi/n .
There is a natural generating set {γ1 , . . . , γk } for π1 (Y 0 , y0 ), where γi is
a loop that encircles the i-th branch point yi (and no other branch point)
with the property that the γi only meet at y0 . Moreover, by relabelling if
necessary, one can show that the product γ1 · · · γk is homotopy equivalent

32

to the trivial loop based at y0 , so γ1 · · · γk = 1 and by a theorem of Hurwitz
(1891) we have
π1 (Y 0 , y0 ) = hγ1 , . . . , γk | γ1 · · · γk = 1i.
This implies that Mon(X, f ) = hσ1 , . . . , σk i and σ1 · · · σk = 1, where σi = σγi
as above.
Question. Which transitive permutation groups G 6 Sym(Ω) of degree
n occur as the monodromy group of a branched covering f : X → P1 (C) of
genus g and degree n?
A necessary and sufficient condition is provided by the Riemann Existence Theorem below (see [100] for a modern treatment). In the statement,
recall that ind(x) = n − t is the index of a permutation x ∈ Sym(Ω), where
t is the number of cycles of x on Ω. Equivalently, ind(x) is the minimal
` such that x is a product of ` transpositions.
P Note that if x1 , . . . , xk are
permutations of Ω with x1 · · · xk = 1, then i ind(xi ) is even.
Theorem 4.3 (Riemann Existence Theorem). Let G 6 Sym(Ω) be a
transitive group of degree n. Then G is isomorphic to a monodromy group
Mon(X, f ) for some compact connected Riemann surface X of genus g and
branched covering f : X → P1 (C) if and only if G has a generating set
{g1 , . . . , gk } such that g1 · · · gk = 1 and
(4.1)

k
X

ind(gi ) = 2(n + g − 1).

i=1

This fundamental result allows us to translate questions about monodromy groups to purely group-theoretic problems concerning finite permutation groups. One of the main problems is to understand the structure
of monodromy groups of genus g, specifically in terms of the composition
factors of such groups. This is formalised in a highly influential conjecture
of Guralnick and Thompson from 1990 [56], which we will discuss below.
Remark 4.4. There is a well understood connection between branched
covers of P1 (C) and finite extensions of the field C(t). More precisely, if
f : X → P1 (C) is a branched covering then C(X)/C(t) is a finite extension,
where C(X) and C(t) denote the function fields of X and P1 (C), respectively. It turns out that the Galois group of the normal closure of this
extension is the monodromy group Mon(X, f ). Therefore, Theorem 4.3 can
be interpreted in terms of the inverse Galois problem. In particular, this
viewpoint permits natural generalisations in which C is replaced by some
other algebraically closed field (of any characteristic). We will return to this
more general set-up at the end of the section.
4.2. The Guralnick-Thompson conjecture. Motivated by the discussion above, we define the genus of a finite group as follows.
Definition 4.5. Let G 6 Sym(Ω) be a finite transitive permutation
group and let E = {g1 , . . . , gk } be a generating set for G with g1 · · · gk = 1.
Define the genus g = g(G, Ω, E) as in (4.1) and define g(G, Ω) to be the
minimal value of g(G, Ω, E) over all such generating sets E (for any k). We

4. MONODROMY GROUPS

33

say that a finite group G has genus g if it has a faithful transitive G-set Ω
such that g(G, Ω) 6 g.
Example 4.6. Let G = hg1 i be a cyclic group of order n. Set E =
{g1 , g1−1 } and consider the regular action of G on itself. Then ind(g1 ) =
ind(g1−1 ) = n − 1, so (4.1) implies that G has genus zero.
Example 4.7. Let G = Sym(n) = hg1 , g2 , g2−1 g1−1 i, where g1 = (1, 2)
and g2 = (1, 2, . . . , n), and consider the natural action of G of degree n. The
indices of the respective generators are 1, n − 1 and n − 2, hence G has genus
zero. Similarly, every alternating group has genus 0.
Fix a non-negative integer g and let C(g) be the set of composition
factors of groups of genus g. Note that C(0) ⊆ C(g). In view of the above
examples, it follows that C(g) contains every simple cyclic and alternating
group. Therefore we focus on E(g), which is the set of nonabelian, nonalternating composition factors of groups of genus g.
The following theorem establishes a conjecture of Guralnick and Thompson [56], which we stated as Problem B in the introduction.
Theorem 4.8. E(g) is finite for each g.
Sketch proof. We briefly sketch the main steps, highlighting the central role played by fixed point ratios.
Step 1. Reduction to almost simple primitive groups.
By work of Aschbacher, Guralnick, Neubauer, Thompson and others
[3, 49, 56, 89], it is sufficient to show that there are only finitely many
primitive almost simple groups of Lie type of genus g. The key ingredient in
this highly nontrivial reduction is the Aschbacher-O’Nan-Scott theorem (as
formulated in [5]) on the structure of finite groups with a core-free maximal
subgroup. See [49, Section 5] for more details.
Step 2. Fixed point ratio estimates.
The next result provides the connection to fixed point ratios (see [49,
Corollary 2]).
Proposition 4.9. Let X be the set of nonabelian, non-alternating finite
simple groups such that
(4.2)

max fpr(x, Ω) 6

16=x∈G

1
86

for every almost simple primitive group G 6 Sym(Ω) with socle G0 ∈ X .
Then X ∩ E(g) is finite for every non-negative integer g.
Proof. Let G 6 Sym(Ω) be a primitive almost simple group of degree
n with socle G0 ∈ X , so (4.2) holds. Fix a generating set {g1 , . . . , gk } for G
such that g1 · · · gk = 1 and define g as in (4.1). Note that k > 3. Let di be
the order of gi and let orb(gi ) be the number of cycles of gi on Ω. Without
loss of generality, we may assume that di 6 di+1 for all i.

34

By the orbit-counting lemma we have

X
n
n
orb(gi ) =
fpr(x, Ω) = 1 +
di
di
x∈hgi i


X

fpr(x, Ω)

16=x∈hgi i

and thus
k
X

ind(gi ) =

i=1

k
X
i=1

k

85 X di − 1
.
(n − orb(gi )) > n
86
di
i=1

Since G is insoluble and G 6∼
= Alt(5), [56, Proposition 2.4] implies that
k
X
di − 1

(4.3)

i=1

di

>

85
.
42

(Note that equality holds if and only if k = 3 and (d1 , d2 , d3 ) = (2, 3, 7), so
G is a Hurwitz group, such as PSL2 (7).) Therefore
2(n + g − 1) =

k
X

ind(gi ) >

i=1

85 85
· n
86 42

and thus n 6 7224(g − 1). The result follows.



Step 3. Bounded rank.
We combine Proposition 4.9 with Theorem 2.6, noting that 4/3q 6 1/86
when q > 113 (the almost simple groups with socle PSL2 (q) excluded in
Theorem 2.6 can be handled separately).
Therefore, to complete the proof of the theorem we may assume that
G is an almost simple classical group of large rank (in other words, we
may assume that the dimension of the natural module of the socle of G is
arbitrarily large).
Step 4. Classical groups in non-subspace actions.
Let G 6 Sym(Ω) be an almost simple primitive group over Fq with socle
G0 in a non-subspace action (see Definition 2.9). Let m be the dimension
of the natural module for G0 . By Theorem 2.15 there is a constant δ > 0
such that
max fpr(x) < q −δm ,
16=x∈G

so there are at most finitely many groups G with max16=x∈G fpr(x) > 1/86.
Now apply Proposition 4.9.
Step 5. Classical groups in subspace actions.
To complete the proof it remains to handle the subspace actions of classical groups. It is sufficient to prove the following result (see [45]).
Proposition 4.10. Fix a prime power q and non-negative integer g.
Then there exists a constant N = N (q) such that if G 6 Sym(Ω) is any
primitive almost simple classical group over Fq in a subspace action of genus
g then either m 6 N or n 6 2000g, where m is the dimension of the natural
module and n is the degree of G.

4. MONODROMY GROUPS

35

In other words, if the dimension of the natural module V is large enough,
then the degree of G is bounded above by a (linear) function of g and the
result follows. The key tool is Theorem 2.13 – the details are rather technical,
so we only provide a rough outline of the argument.
Let G = hg1 , . . . , gk i be a generating set such that g1 · · · gk = 1 and (4.1)
holds. Let di be the order of gi and label the gi so that di 6 di+1 for all i.
Let ϕ be Euler’s function and set
ν(d) = min{ν(x) : x ∈ G, |x| = d},
1X
ϕ(a)q −ν(a)
α0 (d) = 1 −
d
a|d

for each natural number d. Note that α0 (d) > 1/4 if d > 2. Set
k

α(gi ) =

X
ind(gi )
, σ=
α(gi )
n
i=1

and observe that it suffices to show that σ > 2.001 if m is sufficiently large
(where m is the dimension of the natural module).
We may assume that m is large enough so that Theorem 2.13 gives
fpr(x) < q −ν(x) + 10−3
for all 1 6= x ∈ G ∩ PGL(V ). Then


di
di
X
j
1
1 X
fpr(gij ) > 1 − 
q −ν(|gi |)  − 10−3
α(gi ) = 1 −
di
di
j=1
j=1


1 X
=1−
ϕ(a)q −ν(a)  − 10−3
di
a|di

= α0 (di ) − 10−3
which is at least 0.249, whence σ > 0.249k. Therefore, we may assume that
k 6 8. With further work it is possible to reduce to the minimal case k = 3,
where the final analysis splits into several subcases according to the values
of d1 , d2 and d3 . It is worth noting that an important tool in the latter
reduction is the fact that
k
X
ν(gi ) > 2m,
i=1

which follows from a well known theorem of Scott [93].



4.3. Genus zero groups. It remains an open problem to explicitly
determine the simple groups in E(g), although there has been some significant recent progress in the low genus cases, and in particular the special
case g = 0. For example, the sporadic groups in E(0) have been determined
by Magaard [85]; the examples are as follows:
M11 , M12 , M22 , M23 , M24 , J1 , J2 , Co3 , HS.

36

By work of Frohardt and Magaard [42, 43], the only exceptional groups in
E(0) are 2 B2 (8), G2 (2)0 ∼
= PSU3 (3) and 2 G2 (3)0 ∼
= PSL2 (8). The relevant
groups of the form PSL2 (q) and PSU3 (q) are determined in [40]:
PSL2 (q) : q ∈ {7, 8, 11, 13, 16, 17, 19, 25, 27, 29, 31, 32, 37, 41, 43, 64}
PSU3 (q) : q ∈ {3, 4, 5}
There is work in progress by Frohardt, Guralnick, Hoffman and Magaard
to extend the results in [40] to higher rank classical groups, leading to a
complete classification of all primitive permutation groups of genus zero. In
fact, the ultimate aim is to determine the primitive groups of genus at most
two, building on earlier work in [41]. It is anticipated that these results will
have interesting number-theoretic applications.
At a conference in July 2016 (Algebraic Combinatorics and Group Actions, Herstmonceux Castle, UK), Frohardt announced that the groups in
E(0) have been determined. The complete list is as follows:
PSL2 (q), 7 6 q 6 43, q 6= 9, 23
PSL2 (64)
PSL3 (q), q ∈ {3, 4, 5, 7}
PSL4 (3), PSL4 (4), PSL5 (2), PSL5 (3), PSL6 (2)
PSU3 (3), PSU3 (4), PSU3 (5)
PSp4 (3), PSp4 (4), PSp4 (5)
PSp6 (2), PSp8 (2)
−
PΩ+
8 (2), PΩ8 (2)
2 B (8)
2
M11 , M12 , M22 , M23 , M24 , J1 , J2 , Co3 , HS
Example 4.11. Notice that G = PSL2 (23) 6∈ E(0). To see that G does
not have a primitive genus zero action, first observe that G has five conjugacy
classes of maximal subgroups, represented by
Z23 :Z11 , D24 , D22 , Sym(4) (two classes).
Fix a maximal subgroup M and set n = |G : M |. As recorded in the
following table, it is straightforward to compute ind(x) for each non-identity
x ∈ G (with respect to the action of G on G/M ):
M
n 2n − 2 |x| = 2 3
4
6
11 12 23
Z23 :Z11 24
46
12
16 18 20 20 22 22
D24
253
504
120
168 186 208 230 230 242
D22
276
550
132
184 208 238 250 252 264
Sym(4) 253
504
122
166 186 208 230 230 242
Seeking
a contradiction, suppose that G = hg1 , . . . , gk i with g1 · · · gk = 1
P
and i ind(gi ) = 2n − 2. As before, let di denote the order of gi and assume
di 6 di+1 for all i.
Suppose M is the Borel subgroup Z23 :Z11 , so 2n − 2 = 46. From the
above
table, it follows that k = 3, d1 = 2 and d2 ∈ {2, 3}. If d2 = 2 then
P
(d
−
1)/di < 2, which contradicts the bound in (4.3). Therefore, d2 = 3
i i

5. BASES

37

and a second application of (4.3) forces d3 > 11. But this implies that
k
X

ind(gi ) > 12 + 16 + 20 > 46,

i=1

which is a contradiction. The other cases are similar.
4.4. Generalisations. As noted in Remark 4.4, there are natural generalisations to other fields. Let k be an algebraically closed field of characteristic p > 0 and let f : X → Y be a finite separable cover of smooth projective
curves over k. Let G be the corresponding monodromy group, which is the
Galois group of the normal closure of the extension k(X)/k(Y ) of function
fields. As for p = 0, in positive characteristic we can seek restrictions on the
structure of G according to the genus of X. There is still a translation of
the problem to group theory, but the set-up is much more complicated. For
example, there is no known analogue of Riemann’s Existence Theorem and
further complications arise if the given cover f is wildly ramified (the proof
of the Guralnick-Thompson conjecture goes through essentially unchanged
in the tamely ramified case).
The following conjecture of Guralnick is the positive characteristic analogue of the Guralnick-Thompson conjecture (see [50, Conjecture 1.6]). In
order to state the conjecture, let p be a prime and let S be a nonabelian
simple group. We say that S has genus g (in characteristic p) if S is a composition factor of the monodromy group of a finite separable cover f : X → Y
of smooth projective curves over an algebraically closed field of characteristic
p with X of genus at most g.
Conjecture 4.12. Let g > 0 be an integer and let Ep (g) be the set of
nonabelian non-alternating simple groups of genus g in characteristic p > 0.
Then


[
Ep (g) ∩ 
Lie(r)
r6=p

is finite, where Lie(r) is the set of finite simple groups of Lie type in characteristic r.
The condition r 6= p in the conjecture is necessary. For example, work
of Abhyankar (see [1] and the references therein) shows that Ep (0) contains
every simple classical group in characteristic p. Guralnick’s conjecture is
still open in its full generality, and we refer the reader to the survey article
[50] for further details. Here it is worth highlighting [50, Theorem 1.5],
which shows that the conjecture holds if we replace Lie(r) by the set of
finite simple groups of Lie type in characteristic r of bounded dimension.
5. Bases
In this final section we introduce the classical notion of a base for a
permutation group and we discuss how probabilistic methods, based on fixed
point ratio estimates, have been used to establish strong results on the
minimal size of bases for simple groups. In particular, we will sketch a
solution to Problem C in the introduction.

38

5.1. Preliminaries. We begin by defining the base size of a permutation group.
Definition 5.1. Let
T G 6 Sym(Ω) be a permutation group. A subset B
of Ω is a base for G if α∈B Gα = 1. The base size of G, denoted by b(G),
is the minimal cardinality of a base.
Examples 5.2.
1. b(G) = 1 if and only if G has a regular orbit on Ω.
2. b(G) = n − 1 for the natural action of G = Sym(n) on Ω =
{1, . . . , n}.
3. b(G) = dim V for the natural action of G = GL(V ) on Ω = V .
4. b(G) = dim V + 1 for the action of G = PGL(V ) on the set of
1-dimensional subspaces of V .
Remark 5.3. Bases arise naturally in several different contexts:
a. Abstract group theory. Let G be a finite group and let H be a corefree subgroup, so we may view G as a permutation group on Ω = G/H.
In
T this xcontext, b(G) is the size of the smallest subset S ⊆ G such that
x∈S H = 1.
b. Permutation group theory. Let G be a permutation group of degree n
and let B be a base for G. If x, y ∈ G then
\
αx = αy for all α ∈ B ⇐⇒ xy −1 ∈
Gα ⇐⇒ x = y
α∈B

n|B| .

and thus |G| 6
In this way, (upper) bounds on b(G) can be used to
bound the order of G.
c. Computational group theory. The concept of a base and strong generating
set was introduced by Sims [96] in the early 1970s, and it plays a fundamental role in the computational study of finite permutation groups (e.g.
for computing the order of the group, and testing membership). See [95,
Section 4] for more details.
d. Graph theory. Let Γ be a graph with vertices V and automorphism group
G = Aut(Γ) 6 Sym(V ). Then
b(G) = the fixing number of Γ
= the determining number of Γ
= the rigidity index of Γ
is a well-studied graph invariant. See the survey article by Bailey and
Cameron [9] for further details.
Let G be a permutation group of degree n. In general, it is very difficult
to compute b(G) precisely (indeed, algorithmically, this is known to be an
NP-hard problem; see [10]), so we focus on bounds, and in particular upper
bounds in view of applications. It is easy to see that
log |G|
6 b(G) 6 log2 |G|
(5.1)
log n

5. BASES

39

and it is straightforward to construct transitive groups G such that b(G)
is at either end of this range. A well known conjecture of Pyber [92] from
the early 1990s asserts that the situation for primitive groups is rather more
restrictive, in the sense that there is an absolute constant c such that
log |G|
b(G) 6 c
log n
for any primitive group G of degree n. This conjecture has very recently
been proved by Duyan, Halasi and Maróti [39], building on the earlier work
of many authors.
The following lemma reveals a connection between the base size and the
minimal degree of a transitive group (cf. Section 2.2).
Lemma 5.4. Let G 6 Sym(Ω) be a transitive group of degree n. Then
b(G)µ(G) > n.
Proof. Let B be a base of minimal size and let S be the support of an
element 1 6= g ∈ G of minimal degree. If B x ∩ S = ∅ for some x ∈ G, then
B x ⊆ Ω \ S, so g fixes every element of B x , but this is not possible since B x
is a base. Therefore |B x ∩ S| > 1 for all x ∈ G.
Next we claim that |{x ∈ G : α ∈ B x }| = |B||G|/n for all α ∈ Ω.
Consider α1 ∈ B. Fix y ∈ G such that αy = α1 . Then
{x ∈ G : α = α1x } = {x ∈ G : α = αyx } = {x ∈ G : yx ∈ Gα } = y −1 Gα ,
so |{x ∈ G : α ∈ B x }| = |B||Gα | = |B||G|/n as claimed. We conclude that
X
X
|G| 6
|B x ∩ S| =
|{x ∈ G : α ∈ B x }| = |S||B||G|/n
x∈G

α∈S

and thus µ(G)b(G) = |S||B| > n.



Let G 6 Sym(Ω) be a primitive group of degree n. Since
b(Sym(n)) = n − 1, b(Alt(n)) = n − 2
we will assume that G 6= Alt(n), Sym(n). Determining upper bounds on
b(G) in terms of n is an old problem. We record some results:
• Bochert [11], 1889: b(G) 6 n/2
√
• Babai [7], 1981: b(G) 6 c n log n for some constant c (independent
of CFSG)
√
• Liebeck [72], 1984: b(G) 6 c n (using CFSG)
Remark 5.5. It is easy to see that Liebeck’s bound is best possible. For
example, if G = Sym(m) and Ω is the√set of 2-element subsets of {1, . . . , m},
2
then n = m
2 and b(G) ∼ 3 m = O( n). For instance, if m ≡ 1 (mod 12)
then
{{1, 2}, {2, 3}, {4, 5}, {5, 6}, . . . , {m − 3, m − 2}, {m − 2, m − 1}}
is a base of size 2(m − 1)/3 (this is optimal).
Stronger bounds are attainable if we focus on specific families of primitive groups. For instance, a striking theorem of Seress [94] states that
b(G) 6 4 if G is soluble. For the remainder we will focus on almost simple
primitive groups.

40

5.2. Simple groups and probabilistic methods. Let G 6 Sym(Ω)
be a primitive almost simple group of degree n, with socle G0 and point
stabiliser H. In studying the base size of such groups, it is natural to make
a distinction between standard and non-standard groups, according to the
following definition (see Definition 2.9 for the notion of a subspace action of
a classical group).
Definition 5.6. We say that G is standard if one of the following holds:
(i) G0 = Alt(m) and Ω is an orbit of subsets or partitions of {1, . . . , m};
(ii) G is a classical group in a subspace action.
Otherwise, G is non-standard. (Note that we will only use the terms standard
and non-standard in the context of a primitive group.)
In general, if G is standard then H is “large” in the sense that |G| is
not bounded above by a polynomial in n = |G : H| of fixed degree. For
example, if we take the standard action of G = PGLm (q) on 1-spaces then
2
|G| ∼ q m −1 and n ∼ q m−1 . In view of (5.1), this implies that the base size
of such a standard group can be arbitrarily large (indeed, we already noted
that b(G) = m + 1 for the given action of PGLm (q)).
Now assume G is non-standard. By a theorem of Cameron, there is
an absolute constant c such that |G| 6 nc for any such group G. In later
work, Liebeck [72] showed that c = 9 is sufficient, and this was extended by
Liebeck and Saxl [76] to give the following.
Theorem 5.7. Let G be a non-standard group of degree n. Then either
|G| 6 n5 , or (G, n) = (M23 , 23) or (M24 , 24).
This result suggests that non-standard groups may admit small bases.
Indeed, the following striking theorem of Liebeck and Shalev [81] shows that
this is true in a very strong sense. The proof uses probabilistic methods
based on fixed point ratio estimates.
Theorem 5.8. There is an absolute constant c such that if G 6 Sym(Ω)
is a non-standard permutation group then the probability that a randomly
chosen c-tuple in Ω is a base for G tends to 1 as |G| tends to infinity.
Remark 5.9. This asymptotic result was conjectured by Cameron and
Kantor [33], and they showed that it holds for alternating and symmetric
groups with the best possible constant c = 2.
Let us explain the connection between fixed point ratios and base sizes.
Let c be a positive integer and let Q(G, c) be the probability that a randomly
chosen c-tuple of points in Ω is not a base for G, so
b(G) 6 c ⇐⇒ Q(G, c) < 1.
Observe that a c-tuple in Ω fails to be a base if and only if it is fixed by an
element x ∈ G of prime order, and note that the probability that a randomly
chosen c-tuple is fixed by x is equal to fpr(x)c . Let P be the set of elements
of prime order in G, and let x1 , . . . , xk represent the G-classes in P. Then
(5.2)

Q(G, c) 6

X
x∈P

fpr(x)c =

k
X
i=1

c
b
|xG
i | · fpr(xi ) =: Q(G, c).

5. BASES

41

We have thus established the following key lemma, which allows us to exploit
upper bounds on fixed point ratios to bound the base size.
b
Lemma 5.10. If Q(G,
c) < 1 then b(G) 6 c.
Sketch proof of Theorem 5.8. Let G0 denote the socle of G. In
view of the work of Cameron and Kantor in [33], we may assume that G0
is a group of Lie type over Fq .
First we claim that b(G) 6 500 if G0 is an exceptional group. To see
this, we apply Theorem 2.6, which states that
4
fpr(x) 6
3q
for all non-identity elements x ∈ G. Now |G| 6 |Aut(E8 (q))| < q 249 , so
 500 X
 500
k
4
4
G
b
|G|
Q(G, 500) 6 Q(G,
500) 6
|xi | <
3q
3q
i=1

q −1

q 249 .

which is at most
since |G| <
The claim follows. Similarly, if G0
is a non-standard classical group of rank r, then the same argument yields
b(G) 6 c(r) (with Q(G, c(r)) → 0 as q tends to infinity).
The key tool to handle the remaining non-standard classical groups of
arbitrarily large rank is Theorem 2.15, which states that there is a constant
 > 0 such that
fpr(x) < |xG |−

(5.3)

for all x ∈ G of prime order (recall that the non-standard hypothesis is
essential). Let m be the dimension of the natural module for G0 . We need
two facts:
1. G has at most q 4m conjugacy classes of elements of prime order (for
example, this follows from [74, Theorem 1]); and
2. |xG | > q m/2 for all x ∈ G of prime order.
Set c = d11/e. Then
b
Q(G,
c) =

k
X
i=1

c
|xG
i | · fpr(xi ) <

k
X

−10
|xG
6 k · (q m/2 )−10 6 q −m
i |

i=1

and thus Q(G, c) tends to 0 as |G| tends to infinity, as required.



5.3. Further results. As the above sketch proof indicates, the constant c in Theorem 5.8 depends on the constant  in (5.3), and is therefore
undetermined. However, by applying the stronger fixed point ratio estimates in [19, 20, 21, 22] and [71], it is possible to show that c = 6 is optimal. Indeed, the following result, which is proved in the sequence of papers
[23, 27, 30, 31], reveals a striking dichotomy for almost simple primitive
groups: either the base size can be arbitrarily large (standard groups), or
there exists an extremely small base (non-standard groups). This solves
Problem B as stated in the introduction.
Theorem 5.11. Let G 6 Sym(Ω) be a non-standard permutation group.
Then b(G) 6 7, with equality if and only if G = M24 in its natural action

42

on 24 points. Moreover, the probability that a random 6-tuple in Ω forms a
base for G tends to 1 as |G| tends to infinity.
Example 5.12. To illustrate the proof of Theorem 5.11 for exceptional
groups, let us briefly sketch an argument to show that b(G) 6 5 for G =
E8 (q).
b
First assume H is small, say |H| 6 q 88 , and write Q(G,
5) = α + β
where α is the contribution to the summation from elements x ∈ G with
|xG | 6 12 q 112 . Observe that



5
1 112 2|H| 5 1 112 2q 88
6 q
= 16q −8 .
β< q
2
q 112
2
q 112
Suppose x ∈ G has prime order and |xG | 6 12 q 112 . The sizes of the conjugacy
classes of elements of prime order in G are available in the literature and
by inspection we see that x is unipotent of type A1 or 2A1 (in terms of the
standard Bala-Carter labelling of unipotent classes). There are fewer than
2q 92 such elements in G, and [71, Theorem 2] implies that fpr(x) 6 2q −24 ,
hence
α < 2q 92 (2q −24 )5 = 64q −28
and the result follows.
To complete the analysis, we may assume |H| > q 88 . As discussed in
Section 2.8, if H is a maximal parabolic subgroup then it is possible to
compute very accurate fixed point ratio estimates using character-theoretic
methods (recall that for unipotent elements, this relies on Lübeck’s work
on Green functions for exceptional groups). This allows us to obtain strong
upper bounds on b(G) for parabolic actions. Moreover, when combined with
the trivial lower bound b(G) > log |G|/ log |Ω|, we get the exact base size
in all but one case (here Pi denotes the maximal parabolic subgroup of G
corresponding to the i-th node in the Dynkin diagram of G with respect to
the standard Bourbaki [13] labelling):
P1 P2 P3 P4 P5 P6
P7
P8
H
b(G) 4 3 3 3 3 3 3 or 4 5
Note that log |G|/ log |Ω| = 3 − o(1) when H = P7 , so we expect b(G) = 4 is
the correct answer in this case.
Finally, let us assume |H| > q 88 and H is non-parabolic. By applying
a fundamental subgroup structure theorem of Liebeck and Seitz (see [77,
Theorem 8]), we deduce that H is of type D8 (q), E7 (q)A1 (q) or E8 (q0 ) with
q = q02 . Let us assume H is of type D8 (q); the other cases are similar. Let
K be the algebraic closure of Fq and set Ḡ = E8 (K) and H̄ = D8 (K),
so we may view G as Ḡσ , and similarly H as H̄σ , for a suitable Frobenius
b
morphism σ of Ḡ. Write Q(G,
5) = α + β, where α is the contribution from
semisimple elements.
Let x ∈ G be a semisimple element of prime order. By applying [71,
Lemma 4.5], we have


|W (Ḡ):W (H̄)| · 2(q + 1)8
q + 1 8 −δ(x)
fpr(x) 6
= 270
q
,
q−1
q δ(x) (q − 1)8

5. BASES

43

where W (X̄) is the Weyl group of X̄ and δ(x) = dim xḠ − dim(xḠ ∩ H̄).
If CḠ (x)0 is not of type D8 , E7 T1 nor E7 A1 , then [70, Theorem 2] implies
that δ(x) > 80 and we deduce that fpr(x) < q −59 . Therefore, if α1 denotes
the contribution to α from these elements then
α1 < |G| · (q −59 )5 < q 248 · q −295 = q −47 .
There are fewer than q 130 remaining semisimple elements in G and by
applying [71, Theorem 2] we deduce that their contribution is less than
q 130 · (q −37 )5 = q −55 . In particular,
α < q −47 + q −55
is tiny.
For unipotent elements there is a distinction between the cases q even
and q odd (recall that we are only interested in elements of prime order).
In any case, the fusion in Ḡ of unipotent classes in H̄ has been determined
by Lawther [69] and using these results it is straightforward to show that β
is also small (and tends to zero as q tends to infinity). See the proof of [30,
Lemma 4.5] for the details.
For classical groups, Theorem 2.16 is the key ingredient in the proof of
Theorem 5.11, which roughly states that  ∼ 1/2 is optimal in (5.3). In
order to use it, let m be the dimension of the natural module for G0 and set
ηG (t) =

k
X

−t
|xG
i |

i=1

for t ∈ R, where x1 , . . . , xk represent the G-classes of elements of prime order
in G. If m > 6, then careful calculation reveals that ηG (1/3) < 1. Therefore,
by combining this with the generic upper bound fpr(x) < |xG |−1/2+1/m from
Theorem 2.16, we deduce that
b
Q(G,
4) <

k
X

1

1

1+4(− 2 + m )
|xG
6 ηG (1/3) < 1
i |

i=1

if m > 6, and thus b(G) 6 4. In this way, we can establish the following
sharpened version of Theorem 5.11 for classical groups (see [23, Theorem
1]).
Theorem 5.13. Let G be a non-standard classical group with point stabiliser H. Then b(G) 6 5, with equality if and only if G = PSU6 (2).2 and
H = PSU4 (3).22 . Moreover, the probability that a random 4-tuple in Ω
forms a base for G tends to 1 as |G| tends to infinity.
The problem of determining the precise base size of every non-standard
group is an ongoing project of the author with Guralnick and Saxl. We
finish by reporting on some recent work towards this goal.
5.3.1. Alternating and sporadic groups. If G0 is a (non-standard) alternating or sporadic group, then b(G) has been calculated in all cases. For
example, if G0 = Alt(n) then [27, Theorem 1.1] implies that b(G) = 2 if
n > 12 (if G = Alt(12) and H = M12 , then b(G) = 3). Similarly, if G = M

44

is the Monster sporadic group, then b(G) = 2 unless H = 2.B, in which case
b(G) = 3 (see [31]).
To handle the symmetric and alternating groups, we first observe that
H is a primitive subgroup (this follows from the non-standard hypothesis),
so we can use a well known result of Maróti [86] to bound |H| from above.
This is combined with Theorem 2.3 on the minimal degree of H, which tells
us that either µ(H) > n/2, or H is a product-type group arising from the
action of a symmetric group on k-sets. The latter situation can be handled
directly, whereas in the general case we translate the bound on µ(H) into a
lower bound on |xG | for all x ∈ H of prime order. This is useful because
b
Q(G,
2) < |H|2 max |xG |−1 .
16=x∈H

The proof for sporadic groups relies heavily on computational methods,
together with detailed information on their conjugacy classes, irreducible
characters and subgroup structure that is available in GAP [47]. Further
work is needed to handle the Baby Monster and the Monster (see [31, 90]
for more details).
As an aside, it is worth noting that determining the exact base size for
the standard groups with an alternating socle is a difficult combinatorial
problem. Indeed, this is an open problem, even for the action of Sym(n) on
k-sets. See [57] for the best known results in this particular case.
5.3.2. Classical groups. Suppose G0 is a classical group, so H is either
geometric or non-geometric. In [28], probabilistic methods are used to determine the precise base size of all non-geometric actions of classical groups.
Here the key ingredient is Theorem 2.18, combined with a detailed analysis
of the low-dimensional irreducible representations of quasisimple groups. As
discussed in Section 2.7, the lower bound on ν(x) in part (ii) of Theorem
2.18 yields a lower bound on |xG |, so our approach is somewhat similar to
the one we used for symmetric and alternating groups (although the details
are more complicated in this situation).
The following result is a simplified version of [28, Theorem 1].
Theorem 5.14. Let G 6 Sym(Ω) be a non-standard classical group
with socle G0 and point stabiliser H ∈ S. Assume n > 8, where n is the
dimension of the natural module for G0 . Then one of the following holds:
(i) b(G) = 2;
−
(ii) b(G) = 3 and (G, H) = (O+
14 (2), Sym(16)), (O12 (2), Sym(13)),
−
−
(Ω12 (2), Alt(13)) or (Ω10 (2), Alt(12));
(iii) b(G) = 4 and (G, H) = (O−
10 (2), Sym(12)).
The analysis of the geometric actions of classical groups is more difficult,
and so far we only have partial results. For example, we can show that
b(G) = 2 if H is a subfield subgroup corresponding to a subfield of Fq of
odd prime index. The analysis in some cases is rather delicate; for example,
it can be difficult to decide if b(G) = 2 or 3. This sort of situation tends to
arise when |H| ∼ |G|1/2 , which often corresponds to a case where H is the
centraliser in G of an involution (at least when q is odd). We anticipate that

5. BASES

45

our recent work in [29] on base sizes for primitive actions of simple algebraic
groups will play a role in this analysis.
5.3.3. Non-standard groups with large base size. The proof of Theorem
5.11 reveals that there are infinitely many exceptional groups with b(G) >
5. In fact, it has recently been shown that there are infinitely many with
b(G) = 6 (see [29, Theorem 11]) and with some additional work it is possible
to determine them all (see [24]).
Theorem 5.15. Let G 6 Sym(Ω) be a non-standard permutation group
with socle G0 and point stabiliser H. Then b(G) = 6 if and only if one of
the following holds:
(i) (G, H) = (M23 , M22 ), (Co3 , McL.2), (Co2 , PSU6 (2).2),
or (Fi22 .2, 2.PSU6 (2).2);
(ii) G0 = E7 (q) and H = P7 ;
(iii) G0 = E6 (q) and H = P1 or P6 .
In cases (ii) and (iii), the usual estimates via fixed point ratios yield
b(G) ∈ {5, 6}, so more work is needed to pin down the precise answer. To
do this we apply some recent results from [29] on bases for simple algebraic
groups.
For example, consider case (ii). Let Ḡ = E7 and H̄ be the corresponding
algebraic groups over F̄q (so H̄ is a maximal parabolic subgroup of Ḡ with
Levi factor of type E6 ) and let σ be a Frobenius morphism of Ḡ such that
(Ḡσ )0 = G0 . We may assume that H̄ is σ-stable. In [29, Section 5] we
show that the generic 5-point stabiliser in Ḡ with respect to the action on
the coset variety Ḡ/H̄ is 8-dimensional (here generic means that there is
a non-empty open subvariety U of (Ḡ/H̄)5 such that the stabiliser in Ḡ of
any tuple in U is 8-dimensional). By considering the fixed points under σ,
we deduce that every 5-point stabiliser in the finite group G is nontrivial,
for any q, and the result follows. Note that the connected component of
the generic 5-point stabiliser is not a torus (because it is 8-dimensional), so
there are no complications with split tori when q = 2.

Bibliography
[1] S.S. Abhyankar and N. Inglis, Galois groups of some vectorial polymomials, Trans.
Amer. Math. Soc. 353 (2001), 2941–2969.
[2] M. Aschbacher, On the maximal subgroups of the finite classical groups, Invent. Math.
76 (1984), 469–514.
[3] M. Aschbacher, On conjectures of Guralnick and Thompson, J. Algebra 135 (1990),
277–343.
[4] M. Aschbacher and R. Guralnick, Some applications of the first cohomology group, J.
Algebra 90 (1984), 446–460.
[5] M. Aschbacher and L. Scott, Maximal subgroups of finite groups, J. Algebra 92 (1985),
44–80.
[6] M. Aschbacher and G.M. Seitz, Involutions in Chevalley groups over fields of even
order, Nagoya Math. J. 63 (1976), 1–91.
[7] L. Babai, On the order of uniprimitive permutation groups, Annals of Math. 113
(1981), 553–568.
[8] L. Babai, On the order of doubly transitive permutation groups, Invent. Math. 65
(1982), 473–484.
[9] R.F. Bailey and P.J. Cameron, Base size, metric dimension and other invariants of
groups and graphs, Bull. London Math. Soc. 43 (2011), 209–242.
[10] K.D. Blaha, Minimum bases for permutation groups: the greedy approximation, J.
Algorithms 13 (1992), 297–306.
[11] A. Bochert, Über die Zahl verschiedener Werte, die eine Funktion gegebener Buchstaben durch Vertauschung derselben erlangen kann, Math. Ann. 33 (1889), 584–590.
[12] A. Bochert, Ueber die Classe der transitiven Substitutionengruppen, Math. Ann. 40
(1892), 176–193.
[13] N. Bourbaki, Lie Groups and Lie Algebras (Chapters 4-6), Springer, 2002.
[14] J.N. Bray, D.F. Holt and C.M. Roney-Dougal, The Maximal Subgroups of the Lowdimensional Finite Classical Groups, London Math. Soc. Lecture Note Series, vol.
407, Cambridge University Press, 2013.
[15] J.L. Brenner and J. Wiegold, Two-generator groups I, Michigan Math. J. 22 (1975),
53–64.
[16] T. Breuer, R.M. Guralnick and W.M. Kantor, Probabilistic generation of finite simple
groups, II, J. Algebra 320 (2008), 443–494.
[17] T. Breuer, R.M. Guralnick, A. Lucchini, A. Maróti, and G.P. Nagy, Hamiltonian
cycles in the generating graph of finite groups, Bull. London Math. Soc. 42 (2010),
621–633.
[18] T.C. Burness, Fixed point spaces in actions of classical algebraic groups, J. Group
Theory 7 (2004), 311–346.
[19] T.C. Burness, Fixed point ratios in actions of finite classical groups, I, J. Algebra
309 (2007), 69–79.
[20] T.C. Burness, Fixed point ratios in actions of finite classical groups, II, J. Algebra
309 (2007), 80–138.
[21] T.C. Burness, Fixed point ratios in actions of finite classical groups, III, J. Algebra
314 (2007), 693–748.
[22] T.C. Burness, Fixed point ratios in actions of finite classical groups, IV, J. Algebra
314 (2007), 749–788.
[23] T.C. Burness, On base sizes for actions of finite classical groups, J. London Math.
Soc. 75 (2007), 545–562.
47

48

BIBLIOGRAPHY

[24] T.C. Burness, On base sizes for almost simple primitive groups, in preparation.
[25] T.C. Burness and M. Giudici, Classical groups, derangements and primes, vol. 25,
Lecture Notes Series of the Aust. Math. Soc., Cambridge University Press, 2016.
[26] T.C. Burness and S. Guest On the uniform spread of almost simple linear groups,
Nagoya Math. J. 209 (2013), 35–109.
[27] T.C. Burness, R.M. Guralnick and J. Saxl, On base sizes for symmetric groups, Bull.
London Math. Soc. 43 (2011), 386–391.
[28] T.C. Burness, R.M. Guralnick and J. Saxl, Base sizes for S-actions of finite classical
groups, Israel J. Math. 199 (2014), 711–756.
[29] T.C. Burness, R.M. Guralnick and J. Saxl, On base sizes for algebraic groups, J.
European Math. Soc. (JEMS) 19 (2017), 2269–2341.
[30] T.C. Burness, M.W. Liebeck and A. Shalev, Base sizes for simple groups and a
conjecture of Cameron, Proc. London Math. Soc. 98 (2009), 116–162.
[31] T.C. Burness and E.A. O’Brien and R.A. Wilson, Base sizes for sporadic simple
groups, Israel J. Math. 177 (2010), 307–334.
[32] T.C. Burness and A.R. Thomas, On the involution fixity of exceptional groups of Lie
type, preprint.
[33] P.J. Cameron and W.M. Kantor, Random permutations: some group-theoretic aspects,
Combin. Probab. Comput. 2 (1993), 257–262.
[34] J.H. Conway, R.T. Curtis, S.P. Norton, R.A. Parker and R.A. Wilson, Atlas of Finite
Groups, Oxford University Press, Eynsham, 1985.
[35] E. Covato, The involution fixity of simple groups, PhD thesis, University of Bristol,
2017.
[36] F. Dalla Volta and A. Lucchini, Generation of almost simple groups, J. Algebra 178
(1995), 194–223.
[37] J.D. Dixon, The probability of generating the symmetric group, Math. Z. 110 (1969),
199–205.
[38] J.D. Dixon and B. Mortimer, Permutation Groups, Springer Graduate Texts in Math.
163, Springer-Verlag, New York, 1996.
[39] H. Duyan, Z. Halasi and A. Maróti, A proof of Pyber’s base size conjecture, submitted
(arxiv:1611.09487).
[40] D. Frohardt, R. Guralnick and K. Magaard, Genus 0 actions of groups of Lie rank
1, in Arithmetic fundamental groups and noncommutative algebra (Berkeley, CA,
1999), 449–483, Proc. Sympos. Pure Math., vol. 70, Amer. Math. Soc., Providence,
RI, 2002.
[41] D. Frohardt, R. Guralnick and K. Magaard, Primitive monodromy groups of genus
at most two, J. Algebra 417 (2014), 234–274.
[42] D. Frohardt and K. Magaard, Monodromy composition factors among exceptional
groups of Lie type, in Group theory (Granville, OH, 1992), 134–143, World Sci. Publ.,
River Edge, NJ, 1993.
[43] D. Frohardt and K. Magaard, About a conjecture of Guralnick and Thompson, in
Groups, difference sets, and the Monster (Columbus, OH, 1993), 43–54, Ohio State
Univ. Math. Res. Inst. Publ., vol. 4, de Gruyter, Berlin, 1996.
[44] D. Frohardt and K. Magaard, Grassmannian fixed point ratios, Geom. Dedicata 82
(2000), 21–104.
[45] D. Frohardt and K. Magaard, Composition factors of monodromy groups, Annals of
Math. 154 (2001), 327–345.
[46] D. Frohardt and K. Magaard, Fixed point ratios in exceptional groups of rank at most
two, Comm. Algebra 30 (2002), 571–602.
[47] The GAP Group, GAP – Groups, Algorithms, and Programming, Version 4.4, 2004.
[48] J. Fulman and R.M. Guralnick, The probability of generating an irreducible subgroup,
in preparation.
[49] R.M. Guralnick, The genus of a permutation group, in Groups, combinatorics &
geometry (Durham 1990), 351–363, London Math. Soc. Lecture Note Ser. vol. 165,
Cambridge University Press, 1992.

BIBLIOGRAPHY

49

[50] R.M. Guralnick, Monodromy groups of coverings of curves, in Galois groups and
fundamental groups, Math. Sci. Res. Inst. Publ. 41, 1–46, Cambridge University
Press, 2003.
[51] R.M. Guralnick and W.M. Kantor, Probabilistic generation of finite simple groups, J.
Algebra 234 (2000), 743–792.
[52] R.M. Guralnick and K. Magaard, On the minimal degree of a primitive permutation
group, J. Algebra 207 (1998), 127–145.
[53] R. Guralnick, T. Pentilla, C.E. Praeger, and J. Saxl, Linear groups with orders having
certain large prime divisors, Proc. London Math. Soc. 78 (1999), 167–214.
[54] R.M. Guralnick and J. Saxl, Generation of finite almost simple groups by conjugates,
J. Algebra 268 (2003), 519–571.
[55] R.M. Guralnick and A. Shalev, On the spread of finite simple groups, Combinatorica
23 (2003), 73–87.
[56] R.M. Guralnick and J.G. Thompson, Finite groups of genus zero, J. Algebra 131
(1990), 303–341.
[57] Z. Halasi, On the base size for the symmetric group acting on subsets, Studia Sci.
Math. Hungar. 49 (2012), 492–500.
[58] S. Harper, On the uniform spread of almost simple symplectic and orthogonal groups,
J. Algebra, to appear.
[59] G. Hiss and G. Malle, Low dimensional representations of quasi-simple groups, LMS
J. Comput. Math. 4 (2001), 22–63.
[60] G. Hiss and G. Malle, Corrigenda: Low dimensional representations of quasi-simple
groups, LMS J. Comput. Math. 5 (2002), 95–126.
[61] G.D. James, The Representation Theory of the Symmetric Groups, Springer Lecture
Notes in Math. 682, Springer, Berlin, 1978.
[62] C. Jordan, Théorèmes sur les groupes primitifs, J. Math. Pures Appl. (Liouville) 16
(1871), 383–408.
[63] C. Jordan, Recherches sur les substitutions, J. Math. Pures Appl. (Liouville) 17
(1872), 351–367.
[64] W.M. Kantor, Subgroups of classical groups generated by long root elements, Trans.
Amer. Math. Soc. 248 (1979), 347–379.
[65] W.M. Kantor and A. Lubotzky, The probability of generating a finite classical group,
Geom. Dedicata 36 (1990), 67–87.
[66] J. Kempe, L. Pyber and A. Shalev, Permutation groups, minimal degrees and quantum
computing, Groups Geom. Dyn. 1 (2007), 553–584.
[67] P.B. Kleidman, The maximal subgroups of the finite 8-dimensional orthogonal groups
PΩ+
8 (q) and of their automorphism groups, J. Algebra 110 (1987), 173–242.
[68] P.B. Kleidman and M.W. Liebeck, The Subgroup Structure of the Finite Classical
Groups, London Math. Soc. Lecture Note Series, vol. 129, Cambridge University
Press, 1990.
[69] R. Lawther, Unipotent classes in maximal subgroups of exceptional algebraic groups,
J. Algebra 322 (2009), 270–293.
[70] R. Lawther, M.W. Liebeck and G.M. Seitz, Fixed point spaces in actions of exceptional
algebraic groups, Pacific J. Math. 205 (2002), 339–391.
[71] R. Lawther, M.W. Liebeck and G.M. Seitz, Fixed point ratios in actions of finite
exceptional groups of Lie type, Pacific J. Math. 205 (2002), 393–464.
[72] M.W. Liebeck, On minimal degrees and base sizes of primitive permutation groups,
Arch. Math. 43 (1984), 11–15.
[73] M.W. Liebeck, On the orders of maximal subgroups of the finite classical groups, Proc.
London Math. Soc. 50 (1985), 426–446.
[74] M.W. Liebeck and L. Pyber, Upper bounds for the number of conjugacy classes of a
finite group, J. Algebra 198 (1997), 538–562.
[75] M.W. Liebeck and J. Saxl, Minimal degrees of primitive permutation groups, with
an application to monodromy groups of coverings of Riemann surfaces, Proc. London
Math. Soc. 63 (1991), 266–314.

50

BIBLIOGRAPHY

[76] M.W. Liebeck and J. Saxl, Maximal subgroups of finite simple groups and their automorphism groups, Proceedings of the International Conference on Algebra, Part 1
(Novosibirsk, 1989), 243–259, Contemp. Math. 131, Amer. Math. Soc., 1992.
[77] M.W. Liebeck and G.M. Seitz, A survey of of maximal subgroups of exceptional groups
of Lie type, in Groups, combinatorics & geometry (Durham, 2001), 139–146, World
Sci. Publ., River Edge, NJ, 2003.
[78] M.W. Liebeck and A. Shalev, The probability of generating a finite simple group,
Geom. Dedicata 56 (1995), 103–113.
[79] M.W. Liebeck and A. Shalev, Classical groups, probabilistic methods, and the (2, 3)generation problem, Annals of Math. 144 (1996), 77–125.
[80] M.W. Liebeck and A. Shalev, Simple groups, probabilistic methods, and a conjecture
of Kantor and Lubotzky, J. Algebra 184 (1996), 31–57.
[81] M.W. Liebeck and A. Shalev, Simple groups, permutation groups, and probability, J.
Amer. Math. Soc. 12 (1999), 497–520.
[82] M.W. Liebeck and A. Shalev, On fixed points of elements in primitive permutation
groups, J. Algebra 421 (2015), 438–459.
[83] L. Lovász, Combinatorial problems and exercises, North-Holland, Amsterdam, 1979.
[84] F. Lübeck, Small degree representations of finite Chevalley groups in defining characteristic, LMS J. Comput. Math. 4 (2001), 135–169.
[85] K. Magaard, Monodromy and sporadic groups, Comm. Algebra 21 (1993), 4271–4297.
[86] A. Maróti, On the order of primitive groups, J. Algebra 258 (2002), 631–640.
[87] N.E. Menezes, M. Quick and C.M. Roney-Dougal, The probability of generating a
finite simple group, Israel J. Math. 198 (2013), 371–392.
[88] E. Netto, Substitutionentheorie und ihre Anwendungen auf die Algebra, Teubner,
Leipzig, 1882; English transl. 1892, second edition, Chelsea, New York, 1964.
[89] M.G. Neubauer, On monodromy groups of fixed genus, J. Algebra 153 (1992), 215–
261.
[90] M. Neunhöffer, F. Noeske, E.A. O’Brien and R.A. Wilson, Orbit invariants and an
application to the Baby Monster, J. Algebra 341 (2011), 297–305.
[91] C.E. Praeger and J. Saxl, On the orders of primitive permutation groups, Bull. London
Math. Soc. 12 (1980), 303–307.
[92] L. Pyber, Asymptotic results for permutation groups, in Groups and Computation
(eds. L. Finkelstein and W. Kantor), DIMACS Series, vol. 11, pp.197–219, 1993.
[93] L. Scott, Matrices and cohomology, Annals of Math. 105 (1977), 473–492.
[94] Á. Seress, The minimal base size of primitive solvable permutation groups, J. London
Math. Soc. 53 (1996), 243–255.
[95] Á. Seress, Permutation Group Algorithms, Cambridge Tracts in Mathematics 152,
Cambridge University Press, 2003.
[96] C.C. Sims, Computation with permutation groups, Proc. Second Sympos. on Symbolic
and Algebraic Manipulation, (ACM, New York), pp.23–28, 1971.
[97] A. Stein, 1 21 -generation of finite simple groups, Beiträge Algebra Geom. 39 (1998),
349–358.
[98] R. Steinberg, Generators for simple groups, Canad. J. Math. 14 (1962), 277–283.
[99] R. Steinberg, Endomorphisms of linear algebraic groups, Mem. Amer. Math. Soc. 80
(1968).
[100] H. Völklein, Groups as Galois Groups: An Introduction, Cambridge Studies in Advanced Math. 53, Cambridge University Press, 1996.
[101] H. Wielandt, Finite Permutation Groups, Academic Press, New York, 1964.

