Primitive permutation groups of bounded orbital diameter

Martin W. Liebeck  Dugald Macpherson  Katrin Tent

October 27, 2009

Abstract.

We give a description of infinite families of finite primitive permutation groups for which there is a uniform finite upper bound on the diameter of all orbital graphs. This is equivalent to describing families of finite permutation groups such that every ultraproduct of the family is primitive. A key result is that, in the almost simple case with socle of fixed Lie rank, apart from very specific cases, there is such a diameter bound. This is proved using recent results on the model theory of pseudofinite fields and difference fields.

2000 Mathematics Subject Classification 20B15 (primary), 03C60 (secondary).

1 Introduction

In this paper we classify classes of finite primitive permutation groups with a boundedness property which is motivated by logic — namely, the property that all orbital graphs have bounded diameter. This condition ensures that, in an obvious first order language for permutation groups, primitivity is implied by a first order expressible condition, so extends to ultraproducts. We believe that the bounded diameter property is also of group-theoretic interest.

Throughout, a permutation group will be regarded as a two-sorted structure (X, G) in a language L, with a definable group structure on G and a definable faithful action of G on the set X; so the language will have a binary operation (group multiplication) on the sort G, a unary operation (inversion) on G, a constant symbol for the group identity, and a binary function X × G → X for the group action.

A first order theory T has the finite model property if every sentence in T has a finite model. We consider complete theories T of infinite permutation groups such that T has the finite model property, and for all models (X, G) of T, the group G acts primitively on X. Equivalently, we consider ω-saturated pseudofinite permutation groups which are primitive, where a structure is said to be pseudofinite if it is elementarily equivalent to a non-principal ultraproduct of finite structures.

Recall that a transitive permutation group (X, G) is primitive if and only if each point stabiliser G_{x} (x ∈ X) is a maximal subgroup of G. In a permutation group viewed as an L-structure, any point stabiliser is parameterdefinable in L. Thus, by compactness, an ω-saturated permutation group (X, G) is primitive if and only if there is d ∈ ℕ such that for any x ∈ X and any g, h ∈ G \ G_{x}, h can be written as a word of length at most d in g, g^{−1} and elements from G_{x}; that is, G_{x} is boundedly maximal. Consequently the determination of ω-saturated primitive pseudofinite permutation groups amounts to classifying families of finite primitive permutation groups in which the point stabilisers are uniformly boundedly maximal.

Another interpretation of this problem comes from the theory of orbital graphs. If G is a transitive permutation group on X, then an orbital graph for (X, G) is a graph with vertex set X whose edge set is an orbit of G on X^{{2}}, the collection of unordered 2-element subsets of X. The criterion of D.G. Higman [18] states that a transitive permutation group (X, G) is primitive if and only if all orbital graphs are connected. Thus, an ω-saturated transitive permutation group (X, G) is primitive if there is d ∈ ℕ such that all orbital graphs have diameter at most d. We shall write diam(X, G) (or diam(G, H), where H is a point stabiliser G_{x}) for the supremum of the diameters of the orbital graphs of (X, G).

The above discussion shows that the following goals are essentially equivalent.

(i) Describe, for each d, the class of all finite primitive permutation groups (X, G) such that diam(X, G) ≤ d.

(ii) Describe, for each d, the class of all finite primitive permutation groups (X, G) such that for each g, h ∈ G \ G_{x}, h can be written as a word of length at most d in g, g^{−1} and elements of G_{x}.

(iii) Describe primitive ω-saturated pseudofinite permutation groups. (iv) Describe primitive infinite ultraproducts of finite permutation groups.

(v) Describe pseudofinite structures (G, H) (i.e. a group G, with a predicate for a subgroup H) such that H is boundedly maximal in G and is core-free in G (that is, ⋂_{g∈G} H^{g} = {1}).

In this paper we shall achieve each of these goals, up to some looseness in the classifications. Mostly, we work with condition (i), and we denote the class of primitive permutation groups described in (i) by F_{d}. We do not give a fully explicit description of F_{d}, but give tight structural information (see Theorems 1.1 and 1.2). A description of primitive infinite ultraproducts of finite permutation groups, as in (iv), follows, and we shall discuss this in Section 7.

In condition (iii) above, ω-saturation seems essential. However, we do not currently have an example of a primitive pseudofinite permutation group such that in any/some ω-saturated model of its theory, the group is not primitive. ‘Omitting types’ arguments appear not to work. Without pseudofiniteness there are many examples – for example any primitive automorphism group of an infinite locally finite graph.

Our treatment relies on the classification of finite simple groups (in a “weak” sense – we only assume that the number of sporadic groups is finite), and we use heavily the O’Nan-Scott Theorem and Aschbacher’s description of subgroups of classical groups [1], together with work of Liebeck and Seitz [38] on maximal subgroups of exceptional groups. A key starting point is the bound provided by Lemma 2.1 below. Model-theoretic techniques are used in Sections 4 and 5 to show that certain families of finite primitive permutation groups do have bounded diameter.

We see this project partly as an extension of work begun in [26]. Recall that a countably infinite first order structure is ω-categorical if it is determined up to isomorphism, among countably infinite structures, by its first order theory. By the Ryll-Nardzewski Theorem, a countably infinite structure is ω-categorical precisely if its automorphism group is oligomorphic, that is, has finitely many orbits on k-tuples for all k. If (X, G) is a finite permutation group, let g_{k}(G) be the number of orbits of G on X^{k}. In [26], a structural description was given, for any fixed d, of the class Σ_{d} of all finite primitive permutation groups (X, G) such that g_{5}(G) ≤ d. The description is tight enough that the bound d on g_{5}(G) implies, for each n, a bound (depending on d and n) on g_{n}(G). The permutation groups in Σ_{d} fall into families such that, in the ‘limit’, the group is the automorphism group of an ω-categorical ‘smoothly approximable’ structure. A very rich theory of smooth approximation (without any primitivity assumption) was then developed in [12].

It was shown in [41] that the assumption that g_{5}(G) is bounded can be weakened to an assumption that g_{4}(G) is bounded, with the same general theory, and the same examples in the limit, arising. However, if we just require a bound on g_{3}(G), many more examples arise. For example, the groups PGL(2, q), acting on the projective line, are triply transitive but the number of orbits on quadruples grows with q, so these do not approximate any ωcategorical limit. An essential point here is that there are no ω-categorical fields, so if a class of finite permutation groups is to have oligomorphic limit, one expects an absolute bound on the size of any fields involved.

It would be entirely feasible to describe all finite primitive permutation groups with a uniform bound on g_{2} (hence also on the permutation rank). The non-abelian socle case was already done in [13], and for the affine case, the key information should be contained in [17]. However, the families of permutation groups arising do not seem to have any model-theoretic meaning. For example, for n = 6, 7, 8 and m = \binom{n}{3}, the permutation groups of affine type V_{m}(q). GL_{n}(q) (q varying, GL_{n}(q) acting in its natural action on the exterior cube of V_{n}(q)) each have a bounded number of orbits on pairs, but for any fixed n ≥ 9, the number of orbits increases with q; and for any fixed n, these permutation groups are interpretable uniformly (as q varies) in the finite field 𝔽_{q}, so there seems to be no model-theoretic distinction between the cases n = 8 and n = 9.

Every orbital graph of a primitive permutation group (X, G) has diameter at most g_{2}(G) − 1. Thus, the collection of families of finite primitive permutation groups (X, G) with a uniform finite bound on diam(X, G) contains the collection of families with a uniform bound on g_{2}. So, in a sense, we are tackling a richer class of finite permutation groups than that given by bounding g_{2}, and at the same time gaining some model-theoretic meaning.

We now state our main results. The first theorem describes the classes of finite primitive groups of bounded orbital diameter (see (i) above). In order to state it we need to define some types of primitive groups. We use the notation

Cl_{n}(q)

to denote a quasisimple classical group with natural module V_{n}(q) of dimension n over 𝔽_{q}. Also, we define the L-rank of an almost simple group with socle G_{0} to be n if G_{0} = Alt_{n}, and to be the untwisted Lie rank if G_{0} is of Lie type. (We use the term L-rank rather than just rank, to avoid possible confusion with the rank of a permutation group.)

Affine groups

Fix a natural number t. We say that an affine primitive group (X, G) is of t-bounded classical type if

(i) G = V H ≤ AΓL_{n}(q), where X = V = V_{n}(q), H ≤ ΓL_{n}(q), (ii) H preserves a direct sum decomposition V = V_{1} ⊕ ⋯ ⊕ V_{k} with H

transitive on {V_{1}, …, V_{k}} and k ≤ t,

(iii) there is a tensor decomposition V_{1} = V_{m}(q) ⊗_{𝔽_{q}} Y such that H_{1} := H_{V_{1}}^{V_{1}}, the group induced by H on V_{1}, contains a normal subgroup Cl_{m}(q_{0})⊗1_{Y} acting naturally on V_{1}, where dim Y ≤ t and 𝔽_{q_{0}} is a subfield of 𝔽_{q} with |𝔽_{q} : 𝔽_{q_{0}}| ≤ t.

Almost simple groups

Fix a natural number t, and let G be a finite almost simple primitive permutation group on a set X, with socle G_{0} (a non-abelian simple group). We say that the primitive group (X, G) has a standard t-action if one of the following holds:

(a) G_{0} = Alt_{n} and X = I^{{t}}, the set of t-subsets of I = {1, …, n} with the natural action of Alt_{n};

(b) G_{0} = Cl_{n}(q) and X is an orbit of subspaces of dimension or codimension t in the natural module V_{n}(q); the subspaces are arbitrary if G_{0} = PSL_{n}(q), and otherwise are totally singular, non-degenerate, or, if G_{0} is orthogonal and q is even, are non-singular 1-spaces (in which case t = 1);

(c) G_{0} = PSL_{n}(q), G contains a graph automorphism of G_{0}, and X is an orbit of pairs of subspaces {U, W } of V = V_{n}(q), where either U ⊆ W or V = U ⊕ W, and dim U = t, dim W = n − t;

(d) G_{0} = Sp_{2m}(q), q is even, and a point stabilizer in G_{0} is O_{2m}^{±}(q) (here we take t = 1).

Simple diagonal actions

Let T be a non-abelian simple group, let k ≥ 2 and let T^{k} act in the usual way on the set X of right cosets of the diagonal subgroup {(t, …, t) : t ∈ T } in T^{k}. If G is a primitive subgroup of Sym(X) having socle T^{k}, we say (X, G) is a primitive group of simple diagonal type. (A little more detail about these can be found later in the paper in Section 2.)

Product actions Let H be a primitive group of almost simple or simple diagonal type on a set Y, and let k ≥ 2. Then H wr Sym_{k} acts naturally on the Cartesian product X = Y^{k}, and we say that (X, G) has a product action on X if G is a primitive subgroup of H wr Sym_{k} and G has socle Soc(H)^{k}.

We shall say that a class C of finite primitive permutation groups is bounded if C ⊂ F_{d} for some d – that is, all the orbital graphs of members of C are of diameter at most d.

Our first main result describes bounded (infinite) classes C of finite primitive permutation groups. All bounds implicit in the statement are in terms of d, where C ⊂ F_{d}. By passing to an infinite subset, and applying the O’Nan-Scott Theorem [33] (see Section 2), we may assume that the members of C are of one of the following types:

(1) affine;

(2) almost simple of unbounded L-rank;

(3) almost simple of bounded L-rank;

(4) simple diagonal actions;

(5) product actions;

(6) twisted wreath actions. (The actions in (6) do not arise in the theorem below – for more detail on them see Section 2 below, or [33].)

Below, and elsewhere in this paper, if G(q) is a Chevalley group, then a subfield subgroup is a group G(q_{0}) embedded naturally in G(q), where 𝔽_{q_{0}} is a subfield of 𝔽_{q}. We also regard as subfield subgroups twisted groups inside untwisted groups, for example PSU_{n}(q) < PSL_{n}(q^{2}).

Theorem 1.1 Let C be an infinite class of finite primitive permutation groups of one of the types (1) − (6) above, and suppose C is bounded.

(1) If C consists of affine groups, then these are all of t-bounded classical type, for some bounded t.

(2) If C consists of almost simple groups of unbounded L-ranks, then the socles of groups in C of sufficiently large L-rank are alternating or classical groups in standard t-actions, where t is bounded.

(3) If C consists of almost simple groups G of bounded L-rank, then point stabilizers G_{x} have unbounded orders; moreover, if G has socle G(q), of Lie type over 𝔽_{q}, and G_{x} is a subfield subgroup G(q_{0}), then |𝔽_{q} : 𝔽_{q_{0}}| is bounded.

(4) If C consists of primitive groups G of simple diagonal type, then these have socles of the form T^{k}, where T is a simple group of bounded L-rank and k is bounded.

(5) If C consists of primitive groups (X, G) of product action type, where X = Y^{k} and G ≤ H wr Sym_{k} for some primitive group (Y, H), then k is bounded, and (Y, H) has bounded diameter.

(6) No infinite bounded class C consists of primitive groups (X, G) of twisted wreath type.

There is a partial converse to this theorem. Essentially, if we take a class C of primitive groups satisfying the conclusions of (1)–(5), then C will be a bounded class. For affine groups our converse is somewhat weaker – see Lemma 3.1. For simple diagonal and product actions the converse is established in Section 5 (again, not quite a full converse). For alternating and classical groups in standard t-actions the diameter bound is proved in Proposition 4.1(ii).

Perhaps the most striking part of the converse is for almost simple groups of bounded L-rank, and we state this next.

Theorem 1.2 Let C be a class consisting of finite primitive almost simple groups G of bounded L-rank. Assume

(i) point stabilizers G_{x} (G ∈ C) have unbounded orders, and

(ii) if G ∈ C has socle G(q), of Lie type over 𝔽_{q}, and G_{x} is a subfield subgroup G(q_{0}), then |𝔽_{q} : 𝔽_{q_{0}}| is bounded.

Then the class C is bounded.

For example, the theorem tells us that if C consists of the groups E_{8}(q) (q varying) acting on the coset space E_{8}(q)/X(q) for some maximal subgroup X(q) arising from a maximal connected subgroup X(K) of the simple algebraic group E_{8}(K), where K = 𝔽̄_{q} (for example X(K) = D_{8}(K) or A_{1}(K)

– see [38]), then the diameters of all the orbital graphs are bounded by an absolute constant. It is not at all clear (to us) how to prove this fact using group theory, and indeed our proof has a large element of model theory, based on Theorem 4.3 in Section 4.

Theorem 1.2 has a consequence concerning distance-transitive graphs. Recall that a distance-transitive graph is one for which the automorphism group is transitive on pairs of vertices at any given distance apart. Thus a finite distance-transitive graph is an orbital graph for the automorphism group (acting on the vertex set) in which the diameter is equal to one less than the permutation rank. The following corollary can be deduced fairly quickly from Theorem 1.2 (it will be proved in Section 6).

Corollary 1.3 There is a function f : ℕ → ℕ such that the following holds. Let G be a finite almost simple group with socle G(q) of Lie type over 𝔽_{q}, and of L-rank r. Suppose G acts primitively on a set X, with G_{x} a non-parabolic subgroup, and suppose there exists a (non-complete) distance-transitive graph on X with automorphism group G. Then q < f(r).

There is currently a programme under way aimed at classifying all finite distance-transitive graphs (see [4] for a survey); in particular this classification is now reduced to cases where the automorphism group is primitive and almost simple, and Corollary 1.3 is a contribution to this case, showing that groups of Lie type in non-parabolic actions can only occur over bounded fields.

As a by-product of our proof of Theorem 1.2, we shall prove that maximal subgroups of finite simple groups of a fixed Lie type, apart from subfield subgroups corresponding to unbounded field extensions, are uniformly definable in the groups (see Corollary 4.11). This generalises [19, Theorem 8.1]. We also prove a uniform definability result for representations of a class of finite simple groups of given Lie type and highest weight (see 4.12).

As discussed at the start of the paper (see the goals (i)-(v)), Theorem 1.1 translates into a description of primitive non-principal ultraproducts of finite permutation groups. We shall give this description in Section 7.

We have tried to write the paper for both group theorists and model theorists, giving background in Section 2 on the O’Nan-Scott Theorem, and on some of the model theory needed. Most of the paper can be understood with very little knowledge of model theory. However, as mentioned above, the proof of Theorem 1.2 does use some substantial model theory: the main result needed – Theorem 4.3 – can be viewed as a “black box”, but some knowledge of model-theoretic definability (and interpretability) is needed to understand its use. The affine case of Theorem 1.1 is handled in Section 3, and the almost simple case in Section 4, where Theorem 1.2 is also proved. The remaining cases (simple diagonal, product action, twisted wreath action) are handled in Section 5. The last two sections contain the proof of Corollary 6 and the translation of our results into a description of primitive non-principal ultraproducts of finite permutation groups.

Notation Throughout, 𝔽_{q} will denote a finite field of order q. The algebraic closure of a field K is denoted K̄. If H is a finite group, then H^{∞} denotes the last term in its derived series, and Soc(H) denotes the socle of H, that is, the direct product of its minimal normal subgroups. We use the term socle also for infinite groups, but only in situations where its meaning is clear (such as for the automorphism group of a Chevalley group over a pseudofinite field). We denote by Z_{n} the finite cyclic group of order n. The symmetric and alternating groups on {1, …, k} are denoted by Sym_{k} and Alt_{k} respectively, and we also write Sym(X) and Alt(X) for the symmetric and alternating groups on a set X. We generally write a power of a Frobenius automorphism of a field as x ↦ x^{q}, and the corresponding induced field automorphism of a Chevalley group over the field as x ↦ x^{(q)}.

Acknowledgement We thank Sasha Borovik for very helpful conversations at an early stage in this work, and Bob Guralnick for providing us with an argument given in the discussion following Lemma 3.2. The second author was partially funded by the Marie Curie Research Training Network MODNET (MRTN-CT-2004-512234).

2 Preliminaries

In this section we present some results from the literature that we shall need. They concern the O’Nan-Scott Theorem, and a little background on model theory.

The O’Nan-Scott Theorem

The following brief discussion is taken from [33]. Suppose (X, G) is a finite primitive permutation group, and let S = Soc(G). The O’Nan-Scott theorem states that there is a finite simple group T such that S is a direct product of copies of T, say S = T^{k}, and G is as in one of the following cases.

Case (1) (Affine case) Here S is elementary abelian and acts regularly on X. Identifying S with X, we may view X as a vector space V = V_{n}(p) of dimension n over 𝔽_{p} (p prime). The stabiliser H of the zero vector, in its action on S, acts linearly, and G = V H with H ≤ GL_{n}(p) irreducible.

In the remaining cases, T is non-abelian.

Case (2) (Almost simple case) Here the socle S = T is simple, and S ≤ G ≤ Aut(S) (so G is almost simple).

Case (3)(a) (Simple diagonal) Define W to be the following subgroup of Aut(T) wr Sym_{k}:

W := {(a_{1}, …, a_{k}).π : a_{i} ∈ Aut(T), π ∈ Sym_{k}, a_{i} ≡ a_{j} mod Inn T for all i, j}.

Define an action of W on X by identifying X with the right coset space of the stabiliser

W_{x} := {(a, …, a)π : a ∈ Aut(T), π ∈ Sym_{k}}.

In this case G is a subgroup of W which has socle Inn(T)^{k} ≅ T^{k} and acts primitively on X (if k > 2 this amounts to saying that G acts primitively on the set of simple factors of T^{k}). Case (3)(b) (Product action) Let H be a primitive permutation group on a finite set Y, of type (2) or (3)(a), and let K := Soc(H). For l > 1, let W = H wr Sym_{l} act on X = Y^{l} in the product action. In this case G is a primitive subgroup of W with socle S = K^{l}; in particular this means that G acts transitively on the l factors. Case (3)(c) (Twisted wreath product) Let P be a transitive permutation group on {1, …, k}, and Q := P_{1} (the stabiliser of 1). Suppose there is a homomorphism ϕ : Q → Aut(T) with image containing Inn(T). Define

B := {f : P → T : f(pq) = f(p)^{ϕ(q)} for all p ∈ P, q ∈ Q}.

Then B is a group under pointwise multiplication, and B ≅ T^{k}. Let P act on B by setting f^{p}(x) = f(px) for p, x ∈ P and f ∈ B. In this case G is the semidirect product BP, with action on X defined by setting G_{x} = P. Here |X| = |T |^{k}, Soc(G) = B (the unique minimal normal subgroup of G), and B acts regularly on X. Note that |T | ≤ (k − 1)!, and |G| ≤ k!((k − 1)!)^{k}.

Some model theory

Next, we give a little model theory background. We assume familiarity with the notions of first order language and structure, of a formula, of a first order theory, and with the compactness theorem. Given a complete theory T, a model M of T, and some set A ⊆ M, an n-type over A is a set of formulas in variables x_{1}, …, x_{n} which is consistent with T; that is, any finite subset of them is simultaneously realised in M. A complete n-type over A is a maximal such set. If p is a type over A, then by compactness there will be an elementary extension N of M and (b_{1}, …, b_{n}) ∈ N^{n} which realises p, that is, satisfies all formulas in p; and for any b̄ ∈ N^{n}, the set of formulas over A which are true of b̄ is a complete type over A. If λ is an infinite cardinal and N ⊧ T, we say that N is λ-saturated if, for every A ⊆ N with |A| < λ, every type over A is realised in N; and N is saturated if it is |N|-saturated. By standard compactness arguments, if M ⊧ T is infinite then, for every infinite cardinal λ, M has a λ-saturated elementary extension. However, for existence of saturated models one generally requires set-theoretic assumptions like the generalised continuum hypothesis.

Ultraproducts give a method of construction, of algebraic flavour, of ω_{1}- saturated models. Fix a countable language L, and let M_{i} (for i ∈ ω) be countable (possibly finite) L-structures. Let U be a non-principal ultrafilter on ω. We say that a property P holds almost everywhere (a.e.) if {i ∈ ω : M_{i} satisfies P } ∈ U. The ultraproduct N = Π_{i∈ω}M_{i}/U has domain (Π_{i∈ω}M_{i})/ ≡, where two sequences in the Cartesian product are equivalent modulo ≡ if they agree a.e. Let [(a_{i})] be the ≡-class of the sequence (a_{i}), where a_{i} ∈ M_{i} for each i. Put [(a_{i})]_{j} := [(a_{ij})], where j = 1, …, n and a_{ij} ∈ M_{i} for each i ∈ ω. If R is an n-ary relation symbol of L, then N ⊧ R[(a_{i})]_{1} … [(a_{i})]_{n} if and only if M_{i} ⊧ Ra_{i1} … a_{in} a.e.; this is welldefined. The interpretation of function and constant symbols of L is defined similarly. The main theorem about ultraproducts is Łos’s Theorem, which says the following: if ϕ(x_{1}, …, x_{n}) is any first order formula, and a_{ij} ∈ M_{i} for i ∈ ω and j = 1, …, n, then N ⊧ ϕ([(a_{i})]_{1}, … [(a_{i})]_{n}) if and only if M_{i} ⊧ ϕ(a_{i1} …, a_{in}) a.e.. Usually, applications of Łos’s theorem will not be made explicit. The ultraproduct N will be ω_{1}-saturated. Assuming the continuum hypothesis, N will be saturated.

A definable set in a structure M is the solution set in M of a first order formula, possibly with parameters. We assume familiarity with the notion of one first-order structure M being interpretable in another structure N (possibly with parameters). This means roughly that the domain of M is a definable subset of N^{k} for some k, modulo some definable equivalence relation; and the relations (and functions and constants) of M come from definable sets in N. In this paper we deal with the notion of a family C of structures being uniformly interpretable in a family of structures D. By this, we mean that there is an injection f : C → D, such that, for each M ∈ C, M is interpretable in f(M), and the interpretation is uniform across C. This means that there is a fixed k, and fixed formulas ϕ(x_{1}, …, x_{k}, z̄), ψ(x_{1}, …, x_{k}, y_{1}, …, y_{k}, w̄), such that for each M ∈ C, there are ā ∈ f(M)^{l(z̄)} and b̄ ∈ f(M)^{l(w̄)} such that M has domain {x̄ ∈ f(M)^{k} : f(M) ⊧ ϕ(x_{1}, …, x_{k}, ā)}/ ≡, where ≡ is an equivalence relation on f(M)^{k} defined by ψ(x̄, ȳ, b̄); and there are similar uniformity requirements for the definitions of the relations, functions, and constants of M. Slightly more generally, we say that C is uniformly interpretable in D if there are finitely many formulas ϕ_{i}, ψ_{j} as above such that for each M ∈ C, one of the ϕ_{i} and ψ_{j} suffices to interpret M in f(M); here, the formulas which define the relations on C can also range over a finite set.

In Section 4 we use some facts about supersimple theories, and pseudofinite fields. We shall not define supersimplicity, but refer to [56] for background. Roughly, a complete first order theory T is supersimple if, for each M ⊧ T, there is a good notion of independence between subsets of M, and if it is possible sensibly to assign, to each complete type, an ordinal-valued rank. There are various such notions of rank (e.g. D-rank, S_{1}-rank, SUrank), but if M has finite rank for any of these notions, then all ranks are finite, and they are equal. Note that any structure interpretable in a supersimple theory also has supersimple theory, and finiteness of rank is also preserved by interpretation. Supersimplicity is used via Theorem 4.3, where for convenience we work with measurable supersimple theories, in the sense of [43].

By a pseudofinite group (or field, or permutation group, etc.) we mean an infinite model of the theory of all finite groups. Any pseudofinite group will be elementarily equivalent to an ultraproduct of finite groups (and likewise for fields, etc.). The common theory of all pseudofinite groups is the collection of those sentences, in the language of groups, which hold in all but finitely many finite groups. The study of pseudofinite fields was initiated by Ax [2]. He characterised them algebraically as those fields F which are perfect, have a unique extension of each finite degree, and are pseudoalgebraically closed: that is, any absolutely irreducible variety defined over F has an F -rational point. By results from [9], any pseudofinite field has supersimple finite rank theory; in fact, the theory is measurable. Pseudofinite groups which are simple (in the sense of group theory) were classified by Wilson in [57]. They are exactly Chevalley groups, possibly twisted, over pseudofinite fields. (Wilson proved elementary equivalence, but this can be strengthened to isomorphism by the uniform bi-interpretability results of Ryten [47].)

A bound

We conclude this section with an easy bound which will be heavily used in our proofs. Recall that F_{d} is the collection of finite primitive permutation groups (X, G) with diam(X, G) ≤ d.

Lemma 2.1 Let (X, G) ∈ F_{d}, x ∈ X, and put H := G_{x} and n := |X| = |G : G_{x}|. Let Y be an orbit of H on X \ {x}. Then

(i) 1 + 2|Y | + … + (2|Y |)^{d} ≥ n.

(ii) |H| ≥ |Y |, so 1 + 2|H| + … + (2|H|)^{d} ≥ n. In particular, if |X| is large enough then |H| ≥ |Y | ≥ n^{1/(d+1)}.

(iii) If y ∈ Y, then |H : H_{y}|^{d+1} ≥ |G : H| for large enough n. In particular, if g ∈ G \ H then (|H : H ∩ g^{−1}Hg|)^{d+1} ≥ |G : H| for large enough n.

Proof. (i) Let E be the edge set of the orbital graph for (X, G) which includes edges {x, y} for y ∈ Y. Then, for each i the number of vertices at distance at most i from x is at most 1 + 2|Y | + ⋯ + (2|Y |)^{i}. Since (X, E) has diameter at most d, it follows that 1 + 2|Y | + … + (2|Y |)^{d} ≥ n.

(ii) By (i), (d + 1)(2|Y |)^{d} ≥ n, so |Y | ≥ \frac{1}{2}(\frac{n}{d+1})^{1/d} which is at least n^{1/(d+1)} for large enough n.

(iii) This is immediate from (ii), as |H : H_{y}| = |Y |. For the last assertion, identify y with the coset Hg. □

3 The affine case

Let G = V H ≤ AGL_{n}(p) be a primitive permutation group of affine type on V = V_{n}(p), where H ≤ GL_{n}(p) is irreducible. Let K ≤ End(V) be a maximal extension field of 𝔽_{p} such that H ≤ N_{GL_{n}(p)}(K) = ΓL_{d}(q), where |K| = q and n = d |K : 𝔽_{p}|, so that V = V_{d}(q) and G = V H ≤ AΓL_{d}(q). Write K^{∗} for the group of scalar matrices in ΓL_{d}(q).

Observe that if U is an orbit of H on V \{0}, then by the irreducibility of H, every vector v can be expressed as a sum of vectors in U ∪ {−u : u ∈ U}. Define l_{U}(v) to be the minimum length of such an expression. Then the diameter of the orbital graph corresponding to U is max{l_{U}(v) : v ∈ V }. We write diam(V, H) (instead of diam(V, V H)) for the maximum diameter of an orbital graph of G.

We begin by proving a partial converse to Theorem 1.1 for affine groups.

Lemma 3.1 (i) Assume that G = V_{d}(q).H ≤ AΓL_{d}(q) as above, and that H contains the group K^{∗} of scalar matrices. Then the primitive permutation group (V, G) lies in the class F_{d+1}.

(ii) Suppose that H contains a normal classical subgroup Cl_{r}(q), where V ↓ Cl_{r}(q) = V_{r}(q) ⊗ X, and Cl_{r}(q) acts naturally on V_{r}(q) and trivially on X. Let dim_{𝔽_{q}} X = t. Suppose also that H contains the scalars K^{∗}. Then there is a constant c = c(t) depending only on t, such that (V, G) lies in the class F_{c}.

(iii) Assume V = V_{1} ⊕ … ⊕ V_{r} with all dim(V_{i}) equal, that the affine primitive permutation group (V_{1}, V_{1}H_{1}) ∈ F_{d}, and that H = H_{1} wr T acts naturally in the imprimitive linear action on V, with T a transitive subgroup of Sym_{r}. Then (V, V H) ∈ F_{2dr}.

Proof. (i) Let U be an H-orbit not containing {0}. Then U corresponds to an orbital graph whose edge set E consists of all G-translates of the 2sets {0, u} (for u ∈ U). As H acts irreducibly, U does not generate a proper 𝔽_{q}-subspace of V, so contains a basis u_{1}, …, u_{d} of V. It follows that the orbital graph (X, E) has diameter at most d + 1. Indeed, if a_{1}, … a_{d} ∈ 𝔽_{q}^{∗} and ∼ denotes adjacency in this graph, then 0 ∼ a_{1}u_{1} ∼ a_{1}u_{1} + a_{2}u_{2} ∼ ⋯ ∼ a_{1}u_{1} + … + a_{d}u_{d}.

(ii) First note that since Cl_{r}(q) ◁ H, H normalizes GL_{r}(q) ⊗ GL(X) (see for example [30, 4.4.3]). Hence there is an H-orbit U consisting of some of the nonzero simple tensors v ⊗x. As U contains a basis of V = V_{r}(q)⊗X, it follows as in (i) that if x′ ∈ X \ {0}, then there is v′ ∈ V_{r}(q) \ {0} such that v′ ⊗ x′ is at distance at most t + 1 from 0 in the orbital graph corresponding to U. Moreover, any nonzero vector in V_{r}(q) is a sum of at most 2 vectors in the Cl_{r}(q)-orbit of v′. Thus, as Cl_{r}(q) acts trivially on X, v′′ ⊗ x′ is at most distance 2(t + 1) from 0 for any non-zero v′′ ∈ V_{r}(q). Since any vector in V ⊗ X is a sum of at most t simple tensors, the diameter of this orbital graph is at most 2t(t + 1).

Now let U be an arbitrary H-orbit on non-zero vectors of V_{r}(q) ⊗ X, and let w := Σ_{i=1}^{s}v_{i} ⊗ x_{i} ∈ U with s ≤ t. We may suppose v_{1}, …, v_{s} are linearly independent. We may also suppose that r > t, as otherwise the conclusion follows from (i). Choose u_{s} linearly independent from v_{1}, …, v_{s} and g ∈ Cl_{r}(q) with (v_{1}, …, v_{s})^{g} = (v_{1}, …, v_{s−1}, u_{s}). Then U contains w′ := v_{1}⊗x_{1}+…+v_{s−1}⊗x_{s−1}+u_{s}⊗x_{s}, and so w, w′ are at distance at most two in the orbital graph, and hence the simple tensor w −w′ = (v_{s} −u_{s})⊗x_{s} is at distance at most two from 0. Thus, by the last paragraph, the orbital graph has diameter at most 4t(t + 1).

(iii) First, let U be an H-orbit containing a vector v ∈ V_{1}. Then the graph corresponding to the V H-orbital containing {0, v} has diameter at most dr. More generally, if U is an arbitary H-orbit, containing say u = v_{1} + … + v_{r} with v_{i} ∈ V_{i} and v_{1} ≠ 0, choose h ∈ H fixing v_{2}, …, v_{r} with v_{1}^{h} ≠ v_{1}. Then v := v_{1}^{h} − v_{1} ∈ V_{1}, and a path of length dr of the (V, V H)- orbital graph with an edge {0, v} yields a path of length 2dr between the same two points for the orbital graph with edge {0, u}. □

Now we embark on the proof of Theorem 1.1 for the affine case. Let G be as at the beginning of this section, so that G = V H ≤ AΓL_{d}(q) ≤ AGL_{n}(p), where V = V_{d}(q) = V_{n}(p), H is an irreducible subgroup of GL_{n}(p) contained in ΓL_{d}(q), and K = 𝔽_{q} ≤ End(V) is a maximal extension field of 𝔽_{p} such that H ≤ N_{GL_{n}(p)}(K) = ΓL_{d}(q).

Assume that (V, G) lies in F_{s} for some s. In the ensuing argument, all statements that quantities are “bounded” mean that they are bounded in terms of s alone.

If d is bounded then the conclusion of Theorem 1.1 holds trivially (taking the relevant classical group just to be the trivial group). So we assume that d is unbounded.

Lemma 3.2 Suppose H preserves a direct sum decomposition of V over 𝔽_{p} as V = V_{1} ⊕ ⋯ ⊕ V_{k} (i.e. H permutes the subspaces V_{i}). Then

(i) k is bounded

(ii) diam(V_{1}, H_{1}) is bounded, where H_{1} = H_{V_{1}}^{V_{1}} is the group induced by H on V_{1}.

Proof. (i) Let U be a nonzero orbit of H contained in ⋃ V_{i}. If 0 ≠ v_{i} ∈ V_{i} and v = ∑_{1}^{k} v_{i}, then l_{U}(v) ≥ k, so k is bounded.

(ii) Let U_{1} be a nonzero orbit of H_{1} on V_{1}, and let U = ⋃_{h∈H} U_{1}h. Then U is a union of H-orbits and U ∩ V_{1} = U_{1}. As diam(V, V H) is bounded, every vector v_{1} ∈ V_{1} is a bounded sum of vectors in U, hence is a bounded sum of vectors in U ∩ V_{1} = U_{1}. This proves (ii). □

We shall assume from now on that H is primitive on V = V_{n}(p) (i.e. preserves no direct sum decomposition as above with k > 1). At the end of the proof we shall use the previous lemma to retrieve the general case.

We have H ≤ N_{GL_{n}(p)}(K) = ΓL_{d}(q). Write H_{0} = C_{H}(K) ≤ GL_{d}(q), so that H_{0} ◁ H. We may assume that E := End_{H}(V) = 𝔽_{r} ⊆ K, and we write q = p^{a} = r^{b} (so a = n/d).

We claim that V ↓ H_{0} is irreducible. Viewing V as V_{bd}(r), it is an absolutely irreducible 𝔽_{r}H-module. Now view V as an 𝔽_{q}H_{0}-module. Then U := V ⊗_{𝔽_{r}} 𝔽_{q}, as an 𝔽_{q}H_{0}-module, is the sum of b Frobenius twists of V. However H/H_{0} is cyclic of order at most b, so if V ↓ H_{0} were reducible, then U ↓ H would be reducible. But H is absolutely irreducible, so this is a contradiction. (We thank Bob Guralnick for providing us with this argument.)

Hence V ↓ H_{0} is irreducible, as claimed. As C_{End(V)}(H_{0}) is a field extension of K, the choice of K implies that C_{End(V)}(H_{0}) = K, and so V is an absolutely irreducible KH_{0}-module.

We now follow the argument given in [26, Section 3] quite closely. Write Z = Z(H_{0}), let S be the socle of H_{0}/Z, and write S = N_{1} ×⋯×N_{t} ×T with N_{i} non-abelian simple and T abelian. The preimages R_{i} of N_{i} and W of T generate a central product R = R_{1} ∘ ⋯ ∘ R_{t} ∘ W, a normal subgroup of H. By the primitivity of H and Clifford’s Theorem, V ↓ R is homogeneous, say V ↓ R = ∑_{1}^{l} V_{i} with all V_{i} isomorphic. As above we have K = C_{End(V_{1})}(H_{0}), and as in the proof of [26, 3.3], there are K-spaces V_{1} and A such that V = V_{1} ⊗_{K} A, R ≤ GL(V_{1}) ⊗ 1_{A}, H_{0} ≤ GL(V_{1}) ⊗ GL(A) and H normalizes GL(V_{1}) ⊗ GL(A).

We claim that dim_{K} V_{1} is unbounded. For suppose otherwise, so that dim V_{1} is bounded and dim A is unbounded. Now R = R_{1} ∘ ⋯ ∘ R_{t} ∘ W ≤ GL(V_{1}) ⊗ 1_{A}, and V_{1} is a tensor product of t + 1 irreducible modules, one for each R_{i} and one for W. As dim V_{1} is bounded, it follows that t is bounded, as is |W/Z| = |T | (see [25, 2.31]). However, modulo Z we have a projection map π_{A} : H_{0} → GL(A) with irreducible image, and since R ≤ ker(π_{A}), this image is a quotient of H_{0}/R, which is isomorphic to a subgroup of Out(N_{1} × ⋯ × N_{t} × T). Hence, as dim A is unbounded, Out(N_{i}) is unbounded for some i, and H_{0} must induce an unbounded group of field automorphisms of N_{i} acting linearly on V_{1}, which forces dim V_{1} to be unbounded, a contradiction.

Hence dim V_{1} is unbounded. Now H has an orbit Δ consisting of simple tensors in V_{1} ⊗ A. By assumption the corresponding orbital graph has bounded diameter, and hence dim A is bounded: for any vector not expressible as a sum of at most e simple tensors is at distance more than e from 0.

At this point we have proved the following.

Lemma 3.3 We have V ≅ V_{1} ⊗_{K} A with dim_{K} A bounded, dim_{K} V_{1} unbounded, R ≤ GL(V_{1}) ⊗ 1_{A}, H_{0} ≤ GL(V_{1}) ⊗ GL(A) and H normalizes GL(V_{1}) ⊗ GL(A).

Next we prove

Lemma 3.4 Let H as in Lemma 3.3 induce H_{1} ≤ ΓL(V_{1}). Then diam(V_{1}, K^{∗}H_{1}) is bounded.

Proof. Let Δ_{1} be an orbit of H_{1} on V_{1}. Then Δ = Δ_{1} ⊗ A is a union of H-orbits on V, so every v ∈ V is a sum of a bounded number of elements of Δ.

Let a_{1}, …, a_{k} be a K-basis of A, and let v_{1} ∈ V_{1}. Then v_{1} ⊗ a_{1} is a bounded sum of vectors in Δ, say

v_{1} ⊗ a_{1} = δ_{1} ⊗ α_{1} + ⋯ + δ_{r} ⊗ α_{r}

with δ_{i} ∈ Δ_{1}, α_{i} ∈ A. For each i write

α_{i} = ∑_{j=1}^{k} λ_{ij}a_{j} (λ_{ij} ∈ K).

Then

\begin{aligned}v_{1} ⊗ a_{1} & = ∑_{i=1}^{r} δ_{i} ⊗ ∑_{j=1}^{k} λ_{ij}a_{j} \\ & = (∑_{i=1}^{r} λ_{i1}δ_{i}) ⊗ a_{1} + ⋯ + (∑_{i=1}^{r} λ_{ik}δ_{i}) ⊗ a_{k}. \end{aligned}

Since every vector in V_{1} ⊗ A has a unique expression as ∑_{1}^{k} v_{i} ⊗ a_{i} where v_{i} ∈ V_{1}, it follows that

v_{1} = ∑_{i=1}^{r} λ_{i1}δ_{i}.

Since K^{∗} ≤ K^{∗}H_{1}, it follows that v_{1} is a sum of a bounded number of elements of Δ_{1}, as required. □

Assume now that V = V_{1}; at the end of the proof we will retrieve the general result from this case using 3.4. Thus we have H ≤ ΓL(V) and R ≤ GL(V) absolutely irreducible.

As in [26] (preamble to Lemma 3.4), write R = P_{1} ∘ ⋯ ∘ P_{m}, where each P_{i}/Z is either a non-abelian minimal normal subgroup of H/Z, or is an abelian Sylow subgroup of T. As in the proof of [26, 3.4], we have V = W_{1} ⊗ ⋯ ⊗ W_{m} with each P_{i} ≤ GL(W_{i}) absolutely irreducible, and H normalizes GL(W_{1}) ⊗ ⋯ ⊗ GL(W_{m}). Considering an orbit of H consisting of simple tensors, the boundedness of diam(V, H) shows that m is bounded, that some W_{i}, say W_{1}, has unbounded dimension, and that dim(W_{2} ⊗ ⋯ ⊗ W_{m}) is bounded. As in Lemma 3.4, diam(W_{1}, K^{∗}H_{1}) is bounded, where H_{1} ≤ ΓL(W_{1}) is the group induced by H.

The argument of [26, 3.5], together with Lemma 2.1, shows that P_{1}/Z is non-abelian, so it is a direct product N_{1} × ⋯ × N_{t} where the N_{i} are isomorphic simple groups. As in the proof of [26, 3.6] we have W_{1} = X_{1} ⊗ ⋯⊗X_{t} with dim W_{1} = (dim X_{1})^{t} constant and H_{1} ≤ L wr Sym_{t} where L ≤ ΓL(X_{1}). Then t is bounded by 2.1. This implies that dim X_{1} is unbounded. If t > 1 then the orbital graph corresponding to an orbit of H_{1} on simple tensors has unbounded diameter, which is a contradiction. Hence t = 1, and (writing Y = W_{2} ⊗ ⋯ ⊗ W_{m}), we have proved

Lemma 3.5 We have V = W_{1} ⊗ Y, where dim Y is bounded, dim W_{1} is unbounded, R_{1} ≤ GL(W_{1}) ⊗ 1_{Y} is absolutely irreducible on W_{1}, R_{1} ◁ H, H normalizes GL(W_{1}) ⊗ GL(Y), and R_{1}^{∞} is quasisimple. Moreover diam(W_{1}, K^{∗}H_{1}) is bounded, where H_{1} ≤ ΓL(W_{1}) is the group induced by H on W_{1}.

At this point we assume that V = W_{1} and retrieve the general case later using 3.5. Thus H ≤ ΓL(V) with E(H) = R^{∞} quasisimple and absolutely irreducible on V. The next proposition pins down the possibilities for the quasisimple group R^{∞}.

Proposition 3.6 There is a function f : ℕ → ℕ such that the following holds. Fix d ∈ ℕ. Let n ∈ ℕ, and let G = V H ≤ AΓL_{n}(q) be a primitive affine group on V, where V = V_{n}(q) and H is subgroup of ΓL_{n}(q) such that H^{∞} is quasisimple and absolutely irreducible on V. Suppose that all orbital graphs of G have diameter less than d. Then one of the following holds:

(i) n < f(d)

(ii) H^{∞} = Cl_{n}(q_{0}), a classical group of dimension n over a subfield 𝔽_{q_{0}} of 𝔽_{q}, where |𝔽_{q} : 𝔽_{q_{0}}| ≤ d.

Proof. Assume first that H^{∞} is a group of Lie type. Then Lemma 2.1(ii), together with [31], shows that provided |H^{∞}| is sufficiently large in terms of d, we have H^{∞} ∈ Lie(p), where p = char(𝔽_{q}) (i.e. H^{∞} is of Lie type in characteristic p). Say H^{∞} = H_{r}(q_{0}), a group of rank r over 𝔽_{q_{0}}. Now [30, 5.4.6-7] shows that one of the following holds:

(a) 𝔽_{q_{0}} is a subfield of 𝔽_{q};

(b) 𝔽_{q} is a subfield of 𝔽_{q_{0}} with [𝔽_{q_{0}} : 𝔽_{q}] = t > 1, and there is an irreducible 𝔽_{q_{0}}H^{∞}-module W such that V = W ⊗ W^{(q)} ⊗ ⋯ ⊗ W^{(q^{t−1})}, realised over 𝔽_{q} (for some cases where H^{∞} is a twisted group, we need to replace q by q^{1/2} or q^{1/3} in this description, but this makes no difference to the ensuing argument).

Suppose (b) holds. Writing w = dim W we have n = w^{t} and q_{0} = q^{t}. Then H has an orbit on V consisting of simple tensors, of which there are q^{wt} − 1 in total. This contradicts Lemma 2.1(ii) for large n.

Hence (a) holds. Then we have

|H| ≤ (q − 1)|Aut(H_{r}(q_{0}))| < (q − 1)q_{0}^{4r^{2}−1} < q^{4r^{2}}

and so Lemma 2.1(ii) implies that

n = dim V < 4(d + 1)r^{2}.

Now [40, 5.1] implies that for sufficiently large n, H^{∞} is a classical group, and, up to field and graph automorphisms, V is an H^{∞}-module of high weight λ_{1}, 2λ_{1}, λ_{2}, λ_{1} +p^{i}λ_{1}, λ_{1} +λ_{r} or λ_{1} +p^{i}λ_{r} (the last two cases only for H of type PSL_{r+1}^{ϵ}(q_{0})). In the first case we have H^{∞} = Cl_{n}(q_{0}); moreover H has an orbit on vectors of size at most qq_{0}^{n}, so |𝔽_{q} : 𝔽_{q_{0}}| ≤ d by 2.1. Hence conclusion (ii) of the proposition holds in this case. In the other cases, if W denotes the natural module for H^{∞}, then V is a section of S^{2}W, ∧^{2}W, W ⊗ W^{(p^{i})}, W ⊗ W^{∗} or W ⊗ W^{∗(p^{i})}, of small codimension: precise descriptions of the possibilities for V can be found in [39, p.102-3]. In all cases n ≥ r^{2}/2, and it is easy to see that H has an orbit on V of size at most q^{4r}. Hence Lemma 2.1 yields n ≤ 4(d + 1)r. This is a contradiction for large n since n ≥ r^{2}/2. This completes the proof of the proposition when H^{∞} is a group of Lie type.

Now suppose H^{∞}/Z(H^{∞}) ≅ Alt_{r}, an alternating group. Then Lemma 2.1(ii) implies that n/(d + 1) < r log r. If H^{∞} = 2. Alt_{r} then [55] gives n ≥ 2^{(r−log_{2} r−2)/2}, hence

2^{(r−log_{2} r−2)/2} ≤ n < (d + 1)r log r,

which implies that n is bounded in terms of d. And if H^{∞} = Alt_{r}, then the bound n < (d + 1)r log r, together with [23, Theorem 5], shows that V ↓ H^{∞} must be the nontrivial irreducible constituent of the usual permutation module, of dimension n = r − δ, where δ = 1 or 2. But then H has an orbit on V of size at most (q − 1) · r(r − 1)/2 (containing the vector corresponding to (1, −1, 0, …, 0) in the permutation module), and so Lemma 2.1 yields

(q − 1) · r(r − 1)/2 ≥ q^{(r−δ)/(d+1)},

implying that r, hence n, is bounded in terms of d. □

At this point we can complete the proof of Theorem 1.1 for affine groups. Let C be an infinite class of finite primitive permutation groups of affine type, and suppose C is bounded. Let G be a group in C. As remarked at the beginning of the proof (after the proof of Lemma 3.1), we have G = V H ≤ AΓL_{d}(q) ≤ AGL_{n}(p), where V = V_{d}(q) = V_{n}(p), H is an irreducible subgroup of ΓL_{d}(q) and K = 𝔽_{q} ≤ End(V) is a maximal extension of 𝔽_{p} such that H ≤ N_{GL_{n}(p)}(K) = ΓL_{d}(q). Moreover we may assume that d is unbounded.

Suppose first that H is primitive on V. Then by 3.3 - 3.6, we have V = V_{1}⊗_{K} Y with dim Y bounded, dim V_{1} = m unbounded, and H ▷Cl_{m}(q_{0})⊗1_{Y}, where 𝔽_{q_{0}} is a subfield of 𝔽_{q} with |𝔽_{q} : 𝔽_{q_{0}}| bounded. Hence the conclusion of Theorem 1.1(1) holds.

Now consider the case where H is imprimitive on V. Then by Lemma 3.2, H preserves a decomposition V = V_{1} ⊕ ⋯ ⊕ V_{k} with k bounded and diam(V_{1}, V_{1}H_{1}) bounded, where H_{1} = H_{V_{1}}^{V_{1}}. Taking k maximal, H_{1} is primitive on V_{1}, and so by the previous paragraph the conclusion of Theorem 1.1(1) again holds.

This completes the proof of Theorem 1.1 for affine groups.

4 The almost simple case

Recall that F_{d} denotes the collection of all finite primitive permutation groups (X, G) such that diam(X, G) ≤ d. In this section we consider bounded classes C (i.e. classes C ⊂ F_{d} for some d) consisting of (X, G) such that Soc(G) is a non-abelian simple group G_{0}, with G_{0} ≤ G ≤ Aut(G_{0}). We aim to prove Theorem 1.1(2),(3) and Theorem 1.2.

In our arguments, we work with fixed (X, G) ∈ C, assumed to be sufficiently large. We make one observation, used repeatedly. Suppose G_{0} ≤ G_{1} ≤ G, H := G_{x}, and H_{1} := H ∩ G_{1}. Then we may identify the coset space G_{1}/H_{1} with G/H in such a way that G_{1} embeds into G in the action on cosets. Thus, diam(G_{1}, H_{1}) ≥ diam(G, H).

The unbounded rank case

Our result here is the following, which implies Theorem 1.1(2) and its converse.

Proposition 4.1 (i) Let C be a bounded class consisting of almost simple finite primitive permutation groups (X, G) of unbounded L-ranks. Then the socles of groups in C of sufficiently large L-rank are alternating or classical groups in standard t-actions, where t is bounded.

(ii) Conversely, for any t, the class consisting of all alternating or classical groups in standard t-actions is bounded.

Proof. (i) We may suppose that all groups in C are of the same type – that is, all are alternating groups, or of type PSL, PSp, PSU or PΩ. Let (X, G) be a group of large L-rank in C, and write H = G_{x} (x ∈ X), a maximal subgroup of G.

Case (1): G_{0} is alternating

In this case (as we may assume |G_{0}| > | Alt_{6} |), we have Alt_{n} ≤ G ≤ Sym_{n}. We claim that (for |G_{0}| large enough) there exists a bounded t such that X may be identified with the collection of t-subsets of {1, …, n}, with G acting in the natural way.

First, if H is intransitive on {1, …, n}, then by maximality, H is the stabiliser of a t-subset of {1, …, n}, and the action of G on X is its induced action on t-sets. The action on t-sets is equivalent to the action on (n − t)- sets, so we may suppose that t ≤ n/2. Form a graph on X, where two t-sets are adjacent if they intersect in a (t − 1)-set (this is an orbital graph). It is easily seen that this graph has diameter t, and hence t is bounded.

Next, suppose that H is transitive but imprimitive on {1, …, n}. Then n = kℓ for some k, ℓ > 1, and H is the stabiliser of a partition of {1, …, n} into ℓ k-sets. Consider the orbital graph in which two partitions U_{1} ∪…∪U_{ℓ} and V_{1} ∪ … ∪ V_{ℓ} are joined if (after re-indexing) U_{i} = V_{i} for i = 1, …, ℓ − 2 and |U_{ℓ−1}△V_{ℓ−1}| = 2. It is easily checked that the diameter of this graph tends to infinity with n, so this case does not arise.

Finally, suppose that H is primitive on {1, …, n}. We have H ≠ Alt_{n}, Sym_{n}. Thus, by the main theorem of [46], |H| ≤ 4^{n}. Hence |X| ≥ \frac{n!}{2.4^{n}}. By Lemma 2.1, 1 + d(2|H|)^{d} ≥ |X| (where C ⊂ F_{d}). This forces 1 + d4^{dn} ≥ n!/2^{d+1}4^{n}, which is impossible for fixed d and large n.

Case (2): G_{0} = PSL_{n}(q)

In this case, we claim that there exists a bounded t such that X may be identified with the set of t-subspaces of V = V_{n}(q), or (if G contains a graph automorphism of G_{0}) on an orbit of pairs (U, W) where U is a t-dimensional subspace of V, and W is an (n − t)-dimensional subspace of d such that U ⊆ W or V = U ⊕ W.

To see this, we use the result of Aschbacher [1] on the maximal subgroups of classical groups. According to this result, either H lies in one of the classes C_{1} − C_{8} of subgroups of G defined in [1], or H is almost simple, and its socle acts absolutely irreducibly on V.

If H ∈ C_{1} then H ∩PGL_{n}(q) is reducible on V_{n}(q), and it is the stabiliser of a t-subspace or pair (U, W) as above; moreover it is easy to see that there is an orbital graph of diameter at least t for these actions, so this is a standard t-action with t bounded, as required.

If H ∈ C_{2} then it is an imprimitive linear group on V = V_{n}(q), so it is the stabiliser of a direct sum decomposition V = V_{1} ⊕…⊕V_{ℓ} into k-dimensional subspaces V_{i}, and an argument as in Case (1) (the partition case) eliminates this (remember that the dimension n is unbounded). A similar argument shows that H is not the stabiliser of a tensor decomposition of V (even up to permutation of the tensor components), which eliminates H ∈ C_{4} ∪ C_{7}.

Next suppose H ∈ C_{5}, so that H^{∞} = PSL_{n}(q_{0}) where q_{0}^{r} = q for some prime r. By Lemma 2.1, r is bounded. Let g ∈ G be the image of a diagonal matrix with entries (a, a^{−1}, 1, …, 1) with a ∈ 𝔽_{q} \ 𝔽_{q_{0}}. Then H ∩ g^{−1}Hg ≥ PSL_{n−2}(q_{0}), so Lemma 2.1(iii) eliminates this case. Similar reasoning deals with the case where H ∈ C_{3} (where H^{∞} = PSL_{n/r}(q^{r})).

If H ∈ C_{6} then there is a prime r|q −1 such that n = r^{m}, the preimage of H is the normalizer of an extraspecial r-group of order r^{1+2m}, and |H∩G_{0}| ≤ (q − 1) · r^{2m} · | Sp_{2m}(r)|. An application of Lemma 2.1 eliminates this.

Suppose next that H ∈ C_{8}, so that H^{∞} is a classical group PSp_{n}(q), PSU_{n}(q^{1/2}) or PΩ_{n}(q). Consider the first case (the others are entirely similar). Here we may view G as acting on the set of all symplectic forms on V = V_{n}(q) (viewed up to scalar multiplication). Put n = 2m, and take H to be the stabilizer of a symplectic form with standard basis e_{1}, …, e_{m}, f_{1}, …, f_{m}. There exists g ∈ G such that g^{−1}Hg stabilizes the symplectic form with standard basis f_{1}, f_{2}, e_{3}, …, e_{n}, e_{1}, e_{2}, f_{3}, …, f_{n}. Then H∩g^{−1}Hg ≥ PSp_{2(m−2)}(q), and Lemma 2.1(iii) eliminates this.

It remains to consider the case where H is almost simple, with socle acting absolutely irreducibly on V; we may suppose moreover that H is contained in no member of any C_{i}. Then by the main theorem of [32], either |H| ≤ q^{3n} or Soc(G) = Alt_{n+δ} with δ = 1 or 2. Now |G| ≥ | PSL_{n}(q)| ≥ cq^{n^{2}−2} for some constant c > 0. This contradicts Lemma 2.1.

Case (3): G_{0} a symplectic, orthogonal, or unitary group These cases are handled in the same way as Case (2). Again, the case where H ∈ C_{1} leads to standard actions on t-subspaces. Note that in even characteristic, the case where G = Sp_{n}(q) and H = O_{n}^{±}(q) ∈ C_{8} also arises; this is again a standard action.

(ii) Now we prove the converse, that any class consisting of alternating or classical groups in standard t-actions is bounded. We will here (perhaps unnecessarily) be using Proposition 4.2(ii), which is the main result in the bounded rank case below (so its proof comes later). We remarked in Section 1 that any class of finite primitive permutation groups of bounded permutation rank is bounded. This takes care of alternating groups in standard t-actions and also classical groups in parabolic actions, i.e. acting on totally singular t-spaces.

It remains to consider four cases:

(a) classical groups Cl_{n}(q) acting on an orbit X of non-degenerate tsubspaces of the natural module V_{n}(q),

(b) G_{0} = PSL_{n}(q) acting on pairs (U, W) with dim U = t and V_{n}(q) = U ⊕ W,

(c) G_{0} is an orthogonal group, q is even, and G_{0} acts on an orbit of non-singular 1-spaces,

(d) G_{0} = Sp_{n}(q) (q even) and H = O_{n}^{±}(q). Consider case (a). First observe that the subclass of classical groups Cl_{n}(q) acting on an orbit of non-degenerate t-spaces, where n ≤ 6t, is a bounded class, with diameter at most r = r(t), say: this follows from Proposition 4.2(ii) below.

Now consider (a) in general, with n ≥ 6t. Let Δ be an arbitrary orbital of pairs from X, let (U, W) ∈ Δ and let U′ ∈ X. There is a non-degenerate subspace V_{0} of V_{n}(q) of dimension at most 6t containing U, W and U′. Let H be the group induced by Cl_{n}(q) on V_{0} by its setwise stabiliser. By the last paragraph, there is a path of length at most r from U to U′ in the orbital graph of H acting on non-degenerate t-subspaces of V_{0} containing the edge {U, W }. This is also a path from U to U′ in the orbital graph of Δ (with the action of Cl_{n}(q) on X). Thus, the orbital graph of Δ has diameter at most r.

Cases (b) and (c) can be handled in similar fashion to case (a), and we leave them to the reader.

Finally, in case (d) all orbital graphs have diameter at most 2, by [24, Theorem 2]. □

The bounded rank case

Our result here is the following, which implies Theorems 1.1(3) and 1.2.

Proposition 4.2 Let C be a class consisting of almost simple primitive permutation groups (X, G) with G of bounded L-rank.

(i) Suppose that C is bounded. Then |G_{x}| → ∞ as |G| → ∞, and there is an integer t such that if G has socle G(q) of Lie type over 𝔽_{q}, and G_{x} is a subfield subgroup G(q_{0}), then the degree [𝔽_{q} : 𝔽_{q_{0}}] ≤ t.

(ii) Conversely, any class C satisfying the conclusions of (i) is bounded.

Part (i) of the proposition is immediate from Lemma 2.1. The main issue is (ii) (which is Theorem 1.2). We prove this using some recent modeltheoretic results, together with some substantial information about maximal subgroups of almost simple groups of Lie type. We present all these results in 4.3 – 4.10. The proof of 4.2 can be found after 4.10.

We work in the context of measurable first order theories; see [43] or [14]. In a measurable theory, every definable set has an assigned ‘dimension’ and ‘measure’, satisfying various properties. Measurable theories are in particular supersimple and of finite rank (i.e. S_{1} rank or SU-rank, which will be equal). The dimension of a definable set may not equal its S_{1}-rank, but is an upper bound for the S_{1}-rank. If M has measurable theory, then any structure obtained by adjoining to M finitely many sorts from M^{eq} also has measurable theory, so there is no distinction between the hypotheses ‘definable in a measurable theory’ and ‘interpretable in a measurable theory’.

We say the permutation group (X, G) is definably primitive if there is no proper non-trivial definable G-congruence on X, or equivalently, if, for x ∈ X, there is no definable H with G_{x} < H < G; here definability is in the structure (X, G).

First, we state the following result of Elwes and Ryten (Theorem 6.2 of [15]).

Theorem 4.3 [15, Theorem 6.2] Let (X, G) be a definably primitive permutation group definable in a structure with measurable theory, and assume that G_{x} is infinite for x ∈ X. Then (X, G) is primitive.

Corollary 4.4 Let C be a class of finite primitive permutation groups such that every non-principal ultraproduct of members of C is definable in a structure with measurable theory. Assume that for (X, G) ∈ C and x ∈ X, |G_{x}| → ∞ as |X| → ∞. Then C is a bounded class.

Proof. Let (X^{∗}, G^{∗}) be a non-principal ultraproduct of groups (X, G) ∈ C, and let x ∈ X^{∗}. Then G_{x} is infinite. Furthermore, (X^{∗}, G^{∗}) is definably primitive: for a definable group H^{∗} with G_{x}^{∗} < H^{∗} < G^{∗} would yield, by Łos’s Theorem, uniformly definable groups H with G_{x} < H < G for infinitely many (X, G) ∈ C, contrary to primitivity. Thus, by Theorem 4.3, (X^{∗}, G^{∗}) is primitive.

It follows, as discussed in the introduction, that C is a bounded class. Indeed, otherwise, one could find an infinite subclass C′ of C containing, for each d ∈ ℕ, just finitely many (X, G) of diameter at most d. Let U be a non-principal ultrafilter on the set C such that C′ ∈ U (so C′ is ‘large’). Then by Łos’s theorem, if (X^{∗}, G^{∗}) is an ultraproduct of C with respect to U then for each d ∈ ℕ, (X^{∗}, G^{∗}) has an orbital graph of diameter at least d. It follows, by compactness and ω_{1}-saturation of ultraproducts, that (X^{∗}, G^{∗}) has a disconnected orbital graph, contrary to primitivity. □

Note that these saturation arguments in the above proof actually just require ω-saturation of ultraproducts.

In our proof of Proposition 4.2, we shall actually be using Theorem 4.7 below, which is a slight adaptation of Corollary 4.4. Thus we shall require that ultraproducts of certain classes C of permutation groups (X, G), where G is almost simple of bounded L-rank, are definable in a structure with measurable theory; this amounts to showing that the permutation groups (X, G) are uniformly definable in finite fields or difference fields. Here, a difference field is a structure (F, σ), where F is a field and σ ∈ Aut(F). The automorphism is required for definability when G or the point stabiliser is a Suzuki or Ree group.

Before addressing the permutation groups, we need some results on ultraproducts of the almost simple groups G (as abstract groups, ignoring the permutation group setting).

Lemma 4.5 Let C be a family of finite simple groups Y (q) of fixed Chevalley type (possibly twisted).

(i) Any non-principal ultraproduct of the finite fields 𝔽_{q} has measurable theory.

(ii) Any non-principal ultraproduct of difference fields (𝔽_{2^{2k+1}}, x ↦ x^{2^{k}}) or (𝔽_{3^{2k+1}}, x ↦ x^{3^{k}}) has measurable theory.

(iii) Any class of finite simple groups of fixed Lie type (possibly twisted) is uniformly interpretable in the class of finite fields, or in the difference fields (𝔽_{2^{2k+1}}, x ↦ x^{2^{k}}) or (𝔽_{3^{2k+1}}, x ↦ x^{3^{k}}).

(iv) Any non-principal ultraproduct of members of C is simple (as a group), and has measurable theory.

(v) If D is a class of finite groups such that Soc(G) ∈ C for all G ∈ D, then Soc(G) is uniformly definable in G (for G ∈ D).

Proof. (i) This follows from the main theorem of [9]. See also [43, Example 3.2, Lemma 5.4]; Example 3.2 asserts that finite fields form a 1-dimensional asymptotic class, and Lemma 5.4 that any non-principal ultraproduct of a 1-dimensional aymptotic class has measurable theory.

(ii) See Chapter 3 of [47]. In particular, [47, Theorem 3.5.8] yields that the finite difference fields form an asymptotic class, and the result then follows from [43, Lemma 5.4].

(iii) For all cases other than the Suzuki and Ree groups, the Chevalley groups Y (q) are uniformly interpretable in the finite fields 𝔽_{q}. This was folklore, but is explicitly proved by Ryten in [47] (Theorem 5.2.4 in the untwisted case, and Theorem 5.3.3 in the twisted case). Note there that the subgroup PSU_{n}(q) of PSL_{n}(q^{2}) is uniformly (as q varies) interpretable in 𝔽_{q}, but not in 𝔽_{q^{2}}. In the field 𝔽_{q} one can interpret 𝔽_{q^{2}}, define the automorphism x ↦ x^{q} by specifying it on a basis, and then interpret PSU_{n}(q). But in 𝔽_{q^{2}} one cannot interpret PSU_{n}(q), for otherwise it would be possible to define the subfield 𝔽_{q}, contrary to the asymptotic results of [9].

The groups ^{2}F_{4}(2^{2k+1}) and ^{2}B_{2}(2^{2k+1}) are uniformly interpretable in the difference fields (𝔽_{2^{2k+1}}, x ↦ x^{2^{k}}), and ^{2}G_{2}(3^{2k+1}) are uniformly interpretable in the difference fields (𝔽_{3^{2k+1}}, x ↦ x^{3^{k}}). Again, this has been known for some time, but made explicit in [47, Corollary 5.4.3].

(iv) Let Y^{∗} be such an ultraproduct. By Propositions 1 and 2 of [45], Y^{∗} is the Chevalley group Y (F) (possibly twisted) over a pseudofinite field F, and by [45, Corollary 1], Y^{∗} is a simple group. The measurability follows from [47, Theorem 1.1.1] and the proof of [43, Lemma 5.4] (which, formally, is for one-dimensional asymptotic classes).

(v) By the simplicity of the ultraproducts Y^{∗} in (iv), there is a bound d = d(C) such that for any Y = Y (q) ∈ C and g, h ∈ Y \ {1}, h is a product of at most d conjugates of g and g^{−1}. Indeed, otherwise, we could choose an ultrafilter to obtain an ultraproduct Y^{∗} so that, by compactness and ω_{1}-saturation of ultraproducts, there are g, h ∈ Y^{∗} \ {1} such that h is not a product of finitely many conjugates of g and g^{−1}; then the normal closure of ⟨g⟩ in Y^{∗} is a proper non-trivial normal subgroup of Y^{∗}, contrary to simplicity. Hence, for any G ∈ D and g ∈ Soc(G) \ {1}, Soc(G) is definable in G as the set of elements of G expressible as a product of at most d G-conjugates of g and g^{−1}. □

Because the groups considered in Proposition 4.2 are almost simple rather than simple, we need to go beyond the previous result and address the uniform definability of various families of almost simple groups. We do this in the next result. In the statement, by a graph automorphism of a finite Chevalley group we mean one of the automorphisms defined in [7, 12.2.3, 12.3.3, 12.4.1].

Lemma 4.6 Let C be a family of finite simple groups of fixed Chevalley type (possibly twisted).

(i) Graph automorphisms of G ∈ C are uniformly definable in G; that is, there are finitely many formulas ϕ_{1}(x_{1}, x_{2}, y), …, ϕ_{r}(x_{1}, x_{2}, y) such that for any G ∈ C and graph automorphism α of G, there is a tuple a in G and some i such that {(x_{1}, x_{2}) ∈ G^{2} : α(x_{1}) = x_{2}} = {(x_{1}, x_{2}) ∈ G^{2} : ϕ_{i}(x_{1}, x_{2}, a) holds}.

(ii) If t ∈ ℕ then the class D of almost simple groups G such that Soc(G) ∈ C and |G : Soc(G)| ≤ t is uniformly interpretable in the class of finite fields or difference fields (𝔽_{2^{2k+1}}, x ↦ x^{2^{k}}) or (𝔽_{3^{2k+1}}, x ↦ x^{3^{k}}).

Proof. (i) This is proved by Ryten in the proofs of 5.3.3 and 5.4.1(2) of [47], though it is implicit. For example, in the proof of 5.3.3, Ryten shows that the graph automorphisms are uniformly definable in the corresponding finite fields. Since (and this is the main content of [47, Ch. 5]) the finite fields are uniformly bi-interpretable (over parameters) with the corresponding finite simple groups, it follows that the graph automorphisms are also uniformly definable in the simple groups. Discussion 5.4.1(2) gives the corresponding definability (in the field) of graph automorphisms for types B_{2}, G_{2} and F_{4}.

(ii) First, by Lemma 4.5(iv), the members of C are uniformly interpretable in finite fields or difference fields. Every element of G ∈ D is a product idgf of inner, diagonal, graph, and field automorphisms of Soc(G). By (i), graph automorphisms of G are uniformly definable in G, and hence interpretable in (difference) fields; and diagonal and field automorphisms of bounded order are also uniformly interpretable in (difference) fields. Note here that for a > 1 the automorphism x ↦ x^{(q)} of PSL_{n}(q^{a}) is definable in 𝔽_{q}, but not in 𝔽_{q^{a}}. Since these automorphisms are given as permutations of the structure G, we may now reconstruct the group multiplication on pairs (i, d, g, f), (i′, d, g′, f′) to define the almost simple group. □

Despite the previous results, it is certainly not the case that ultraproducts of arbitrary classes of almost simple Chevalley groups with socles of fixed type Y (q) always have measurable (or just supersimple) theory. Indeed, groups in such classes may contain arbitrary field automorphisms, and the theory of all pairs (F, σ) (F a finite field, σ ∈ Aut(F)) is model-theoretically very wild; it interprets the theory of pairs of finite fields (F, Fix(σ)), which is known to be undecidable (see for example [8, Section 4]).

In the situation of Proposition 4.2, we have a class of primitive permutation groups (X, G) with G almost simple of bounded rank, and by passing to an infinite subclass we may suppose that the groups G have socles of fixed type Y (q). If the socle Y (q) is also primitive on X, then in our proof of 4.2 we shall replace G by Y (q), in order to ensure that the ultraproduct is definable in a measurable theory. However, it is not always the case that the socle is primitive on X. We shall show in Theorem 4.8, at least in the key case (i)(d), that a point stabilizer in the socle, while not being maximal, is second-maximal in the socle; here we say that a proper subgroup H of a group K is second-maximal in K if there is a maximal subgroup W of K such that H is a maximal subgroup of W.

The next result shows how we can exploit this second-maximal property.

Theorem 4.7 Let C be a class of finite transitive permutation groups (X, G) such that any non-principal ultraproduct of members of C is definable in a measurable theory. Assume that there is a Chevalley type Y (q) (possibly twisted) such that for each (X, G) ∈ C and x ∈ X, G is a simple group of type Y (q), G_{x} is either maximal or second-maximal in G, and that |G_{x}| → ∞ as |X| → ∞. Then there is d ∈ ℕ such that if (X, G) ∈ C and G_{1} is a primitive subgroup of Sym(X) normalising G, then diam(X, G_{1}) ≤ d.

Proof. If G_{x} is maximal in G for all (X, G) ∈ C, the result is immediate from Corollary 4.4. This does not use simplicity of G.

Thus, we may suppose that G_{x} is second-maximal in G for all (X, G) ∈ C, and that this is witnessed by W; that is, G_{x} is maximal in W which is maximal in G. Then in any non-principal ultraproduct (X^{∗}, G^{∗}) of C, there is W^{∗} (the ultraproduct of the groups W) with G_{x}^{∗} < W^{∗} < G^{∗}. Let E^{∗} denote the congruence corresponding to W^{∗} – that is, the G^{∗}-congruence on X^{∗} with {x^{g} : g ∈ W^{∗}} as a block. For y ∈ X^{∗}, let y_{E^{∗}} denote its E^{∗}-class.

Let G_{1}^{∗} be the ultraproduct of the groups G_{1}. As the groups G are simple of fixed Lie type, G^{∗} is simple by 4.5(iv), and G_{1}^{∗} ≤ N_{Sym(X^{∗})}(G^{∗}).

Consider the relation ∼ on X^{∗}, where x ∼ y if and only if |G_{x}^{∗} : G_{xy}^{∗}| < ∞. By [15, Proposition 6.1], ∼ is a definable G^{∗}-congruence on X^{∗}.

Recall that two subgroups H, K of a group are called commensurable if |H : H ∩ K| and |K : H ∩ K| are both finite.

Claim 1. The G^{∗}-congruence ∼ is trivial.

Proof of Claim. As G_{1}^{∗} ≤ N_{Sym(X^{∗})}(G^{∗}), by its definition ∼ is preserved by G_{1}^{∗}. Hence, as G_{1}^{∗} is primitive, if ∼ is not trivial it is universal on X^{∗}. In the latter case, for every x ∈ X^{∗} and g ∈ G_{1}^{∗}, we have |G_{x}^{∗} : G_{x}^{∗} ∩ (G_{x}^{∗})^{g}| < r – that is, G_{x}^{∗} is uniformly commensurable with all its G_{1}^{∗}-conjugates. Then, by Schlichting’s Theorem [49] (independently due to Bergman and Lenstra [3]) there is N ◁G^{∗} normalised by G_{1}^{∗} and commensurable with G_{x}^{∗}. As X^{∗} is infinite, N ≠ G^{∗}, so as G^{∗} is simple, N = 1, so G_{x}^{∗} is finite, a contradiction.

Claim 2.

(i) W^{∗} is definable in (X^{∗}, G^{∗}),

(ii) W is uniformly definable in (X, G).

Proof of Claim. (i) Choose H such that

(a) H is a definable subgroup of W^{∗} containing G_{x}^{∗},

(b) |G_{x}^{∗} : G_{x}^{∗} ∩ H| is finite, and

(c) H has maximal rank (meaning SU-rank, as mentioned briefly in Section 2 above) subject to (a) and (b). Note that H = G_{x}^{∗} already satisfies (a) and (b).

Now Claims 6.2.2 and 6.2.3 of the proof of [15, Theorem 6.2] go through with only small changes. We find

(d) if g ∈ G_{x}^{∗} then H and H^{g} are commensurable.

Indeed, suppose not. Then by Remark 3.5 of [15] there is a definable subgroup K of Π_{g∈W^{∗}}H^{g}, normalised by G_{x}^{∗}, and such that H^{g}/K is finite for each g ∈ G_{x}^{∗}. The SU-rank of K is greater than that of H; otherwise, H and H^{g} are commensurable. Hence KG_{x}^{∗} is a definable subgroup of W^{∗} containing G_{x}^{∗} and of SU-rank greater than that of H, a contradiction.

Using the fact that ∼ is trivial on X^{∗}, it then follows as in [15] that H has greater SU-rank than G_{x}^{∗}. Thus, G_{x}^{∗} < H ≤ W^{∗}. Then H = W^{∗}, for otherwise, by definability of H in (X^{∗}, G^{∗}), for almost all (X, G) ∈ C, G_{x} is not maximal in W. It follows that W^{∗} is definable.

(ii) This follows immediately from (i). For suppose that the above ultraproduct is with respect to the non-principal ultrafilter U on C, and that ϕ(x, ā) defines W^{∗} in (X^{∗}, G^{∗}). Then there is a set U ∈ U such that for all (X, G) ∈ U, there are parameters ā_{i} in (X, G) such that ϕ(x, ā_{i}) defines W in (X, G). Since this holds for any non-principal ultrafilter U on C, there is a finite set of formulas which uniformly define W across C.

Given the claim, there is a uniformly (across (X, G) ∈ C) definable equivalence relation E on X such that if x_{E} denotes the E-class of x, then W = G_{{x_{E}}}. We use the notation G, X, W, x where (X, G) ∈ C is sufficiently large, so sometimes omit the phrase ‘for (X, G) ∈ C’.

In the following claim, we allow the possibility that |W : G_{x}| is bounded above as (X, G) ranges through C.

Claim 3. For (X, G) ∈ C, |G_{x} : ⋂_{g∈W} G_{x}^{g}| → ∞ as |W : G_{x}| → ∞.

Proof. If not, then by appropriate choice of the ultraproduct, we may suppose |W^{∗} : G_{x}^{∗}| is infinite and |G_{x}^{∗} : ⋂_{g∈W^{∗}}(G_{x}^{∗})^{g}| is finite. This says that the block x_{E^{∗}} is infinite but G^{∗} induces a group on it with finite point stabiliser. It follows that if y ∈ x_{E^{∗}} then |G_{x}^{∗} : G_{xy}^{∗}| < ∞, contrary to Claim 1.

We now return to finite permutation groups (X, G) ∈ C. By the maximality assumptions, W acts primitively on x_{E}. As G is simple, G acts faithfully on Y := X/E. The point stabiliser in this action is W, which contains G_{x} so by faithfulness, and as |G| is unbounded, the permutation groups (Y, G) have unbounded degree. By Claim 2, all E and hence Y are uniformly definable in the (X, G), so all non-principal ultraproducts of the (Y, G) have S_{1}-theory. Hence, by the primitive case at the start of the proof, there is t_{1} ∈ ℕ such that diam(Y, G) ≤ t_{1}. Also, by Claim 3 and the uniform definability of W (and the primitive case above) there is t_{2} ∈ ℕ such that diam(x_{E}, W̄) ≤ t_{2}, where W̄ is the permutation group induced on x_{E} by W. Put t := max{t_{1}, t_{2}}.

Let Γ be a G_{1}-orbital containing some (u, v) ∈ x_{E}^{2}. By primitivity of G_{1}, there is g ∈ G_{1} such that u^{g}, v^{g} are E-inequivalent. Now let v′ ∈ X \ x_{E}. Then as diam(Y, G) ≤ t, there is a sequence u = u_{0}, u_{1}, …, u_{s} = v′′, with s ≤ t, such that Ev′v′′ and for each i, (u_{i}, u_{i+1}) ∈ Γ ∪ Γ^{∗}; here Γ^{∗} denotes the orbital paired with Γ, that is, Γ^{∗} := {(z, y) : (y, z) ∈ Γ}. Now as G induces a t-bounded group on v_{E}, there is a path in Γ ∪ Γ^{∗} of length at most t from v′′ to v′, so a path of length at most 2t from u to v′.

Now consider an orbital Δ of (X, G_{1}) which contains no E-equivalent pair. Write d_{Δ} for the distance function in the corresponding orbital graph.

Claim 4. There are distinct E-equivalent v, v′ ∈ X with d_{Δ}(v, v′) ≤ 3t. This claim proves the theorem, for it then follows (by the above argument

for Γ), that the orbital graph of Δ has diameter at most 6t^{2}. Hence, 6t^{2} is an upper bound of the diameter of all orbital graphs of (X, G_{1}). As t is independent of G_{1}, we may put d := 6t^{2}.

Proof of Claim 4. Suppose that the claim is false, and consider the relation ≡ on X: u_{1} ≡ u_{2} if and only if d_{Δ}(u_{1}, u_{2}) ≤ t. Clearly ≡ is reflexive and symmetric, and we will show it is also transitive. If u ∈ X and B is an E-class not containing u, then there is some v ∈ B with d_{Δ}(u, v) ≤ t (as diam(Y, G) ≤ t) and for any v′ ∈ B \ {v}, d_{Δ}(u, v′) > 2t (as otherwise d_{Δ}(v, v′) ≤ 3t). Thus, if u ≡ v and v ≡ w, then d_{Δ}(u, w) ≤ 2t, so either u = w or u and w are in distinct E-classes, in which case d_{Δ}(u, w) ≤ t and u ≡ w.

Thus, ≡ is a proper non-trivial G_{1}-congruence, each ≡ -class meeting each E-class in a singleton. This contradicts the primitivity of (X, G_{1}). □

The next theorem is our main source of information on the possible point stabilizers in the primitive groups in 4.2, which are of course maximal subgroups of almost simple groups of Lie type. In the statement, recall that a Frobenius morphism of a simple algebraic group G is an endomorphism σ whose fixed point group G_{σ} is finite; it can be written as a product of field and graph morphisms of G.

Theorem 4.8 Let p be a prime, K = \overline{𝔽}_{p}, and let G be a simple algebraic group of adjoint type over K of L-rank n. Let σ be a Frobenius morphism such that (G_{σ})′ = G_{0} = G(q) is a finite simple group of Lie type over 𝔽_{q}. Let G_{1} be an almost simple group with socle G_{0}, and let M_{1} be a maximal subgroup of G_{1}. Write M_{0} = M_{1} ∩ G_{0}.

(i) There is a constant c = c(n) such that one of the following holds. (a) |M_{0}| < c;

(b) M_{0} = G(q_{0}), a subgroup of the same type as G (possibly twisted) over a subfield 𝔽_{q_{0}} of 𝔽_{q} with [𝔽_{q} : 𝔽_{q_{0}}] prime; the number of conjugacy classes of such maximal subgroups is at most c log log q;

(c) M_{0} is a parabolic subgroup of G_{0};

(d) M_{0} = N_{G_{0}}(H_{σ} ∩ G_{0}), where H is a σ-stable reductive subgroup of G of positive dimension. The number of G-conjugacy classes of such H, and of G_{σ}-classes of H_{σ}, is at most c.

(ii) If M_{0} is as in (d) of part (i), then it is either maximal or second-maximal in G_{0}; and if M_{0} is as in (b) of (i), it is maximal in G_{0}.

(iii) Assume M_{0} is as in (d) of part (i), and the characteristic p is sufficiently large. Then there is a (possibly trivial) graph automorphism ρ of G stabilizing the subgroup H in (i)(d), such that H⟨ρ⟩ is maximal of positive dimension in G⟨ρ⟩. Moreover, in all cases where ρ ≠ 1 and H is nonmaximal in G, the derived group of H⟨ρ⟩ contains the connected component H^{0}, and has bounded index in H.

Proof. (i) For G of exceptional type, this follows from [38, Corollary 4] and the discussion following this result.

Now suppose that G is of classical type with G_{σ} a finite classical group. If G′_{σ} = D_{4}(q) or C_{2}(q) (q even) and G_{1} contains a graph automorphism, the conclusion follows from [27] or [1] respectively, so assume neither of these cases hold. Then it follows from [35, Theorem 2] that either one of (a)-(d) holds, or M_{0} is almost simple with socle M_{0}^{∗}, say, acting absolutely irreducibly on the natural module for G_{0}. Suppose the latter occurs. By [31], if M_{0}^{∗} is not in Lie(p), where p = char(𝔽_{q}), then (a) holds, so assume M_{0}^{∗} ∈ Lie(p). Say M_{0}^{∗} = M(q_{1}). Assuming that q_{1} is large compared to the rank n (as we may, since otherwise (a) holds), [37, Corollary 3] now shows that (d) holds.

Finally, for G classical and G_{σ} an exceptional group ^{3}D_{4}(q) or ^{2}B_{2}(q), the conclusion follows from the known lists of maximal subgroups of these groups in [29, 54].

(ii) First observe that subfield subgroups M_{0} as in (b) of part (i) are maximal in G_{0}, by [6].

Now let M_{0} be as in (i)(d).

Assume first that G_{0} is of exceptional Lie type. By [38, Theorem 1], the reductive subgroup H is either of maximal rank in G, or it is as in [38, Theorem 1(b,c,d)]. In the latter case M_{0} = N_{G_{0}}(H_{σ} ∩ G_{0}) is maximal in G_{0}, so assume H is reductive of maximal rank. Then M_{0} is as in [34, Tables 5.1,5.2]. For large q, the only cases where M_{0} fails to be maximal in G_{0} occur when G_{0} = F_{4}(q) (p = 2) or G_{2}(q) (p = 3), G_{1} contains a graph automorphism of G_{0}, and M_{0} is as follows:

G_{0}  M_{0}  K
F_{4}(q) B_{2}(q)^{2}.2  B_{4}(q)
B_{2}(q^{2}).2  B_{4}(q)
(q ± 1)^{4}.W (F_{4})  D_{4}(q).S_{3}
(q^{2} + 1)^{2}.(4 ∘ GL_{2}(3))  D_{4}(q).S_{3}
(q^{2} + q + 1)^{2}.(3 × SL_{2}(3) ^{3}D_{4}(q).3
(q^{4} − q^{2} + 1).12  ^{3}D_{4}(q).3
G_{2}(q) (q ± 1)^{2}.W (G_{2})  A_{2}(q).2
(q^{2} + ϵq + 1).6 (ϵ = ±) A_{2}^{ϵ}(q).2
E_{6}(q) N_{G_{0}}(D_{5}(q))  P_{1}

In each case we have indicated a maximal subgroup K of G_{0} in the table, such that M_{0} < K < G_{0} and M_{0} is maximal in K (as can be seen using [27, 29] for the F_{4}(q), G_{2}(q) cases). For the E_{6}(q) case, P_{1} is a D_{5}-parabolic subgroup and M_{0} is a Levi subgroup of P_{1}; here P_{1} = QM_{0} with Q = q^{16} an irreducible module for M_{0}, and so M_{0} is maximal in P_{1}. Hence in all cases M_{0} is second-maximal in G_{0}, as required.

Now suppose that G_{0} is a classical group, with natural module V = V_{n}(q) of dimension n over 𝔽_{q}. Assume that M_{0} is non-maximal in G_{0}.

First, the case where G_{0} = P Ω_{8}^{+}(q) can be dealt with using [27]: this shows that the possibilities for M_{0} non-maximal in G_{0} are G_{2}(q), N_{1}, N_{2} or N_{3} (notation of [27]), all occurring only when G_{1} contains an element inducing a triality automorphism on G_{0}. Each of these is second-maximal as witnessed by containments M_{0} < K < G_{0} with K = Ω_{7}(q), R_{−2}, R_{+2} or I_{−4}, respectively (notation of [27]). Likewise the case where G_{0} = Sp_{4}(q) with q even is handled using [1, Section 14]: the non-maximal possibilities for M_{0} occur when G_{1} contains a graph automorphism, and are (q ± 1)^{2}.[8] and (q^{2} + 1).4; these are second-maximal in G_{0}, as witnessed by a subgroup K = O_{4}^{±}(q). So we suppose from now on that G_{0} ≠ P Ω_{8}^{+}(q) or Sp_{4}(q) (q even).

According to [1], the subgroup M_{0} lies in either one of the Aschbacher families C_{i} (or C′_{1} if G_{0} = L_{n}(q) and G_{1} contains a graph automorphism), or M_{0} is almost simple and its socle is absolutely irreducible on the natural module for G_{0}; in the latter case we write M_{0} ∈ S, as in [30]. Write C for the union of the C_{i} (and C′_{1}).

Suppose now that M_{0} ∈ C. If the dimension n ≥ 13, Tables 3.5H,I in [30] list all triples M_{0} < K < G_{0} where M_{0} ∈ C and K ∈ C ∪ S; the same can be gleaned from [28] when n ≤ 12. In our situation the maximality of M_{1} means that N_{G_{1}}(M_{0}) ≰ N_{G_{1}}(K), so that in the language of [30, p.66], M_{0} is a G_{1}-novelty with respect to K. From the lists we see that for q large, the possibilities are as follows:

(1) G_{0} = L_{n}(q), M_{0} = stab_{G_{0}}(U, W) (where V = U ⊕ W), K = stab_{G_{0}}(U) or stab_{G_{0}}(W);

(2) G_{0} = P Ω_{n}^{+}(q) (n even, n/2 odd), M_{0} of type GL_{n/2}(q).2, K parabolic of type P_{n/2}

(3) G_{0} = P Ω_{n}^{+}(q) (4|n, q odd), M_{0} of type O_{4}^{+}(q) ⊗ O_{n/4}(q), K of type Sp_{2}(q) ⊗ Sp_{n/2}(q). In case (1) it is easy to see that M_{0} is maximal in K and K is maximal in G_{0}. In case (2), M_{0} is a Levi subgroup of K, and K = QM_{0} where the unipotent radical Q is abelian and has the structure of an irreducible M_{0}-module (the alternating square of the natural module); hence again M_{0} is maximal in K and K is maximal in G_{0}. And in case (3) the precise structures of M_{0} and K are given by [30, 4.4.12, 4.4.14], from which we deduce the same conclusion. Hence M_{0} is second-maximal, as required.

Finally, suppose that M_{0} ∈ S. As we are assuming that M_{0} is nonmaximal in G_{0}, we have M_{0} < K < G_{0} for some K ∈ C ∪S. Let V̄ = V ⊗\overline{𝔽}_{p}. Then F^{∗}(M_{0}) is irreducible on V̄, hence so is the reductive group H^{0}, the connected component of the group H of (i)(d). Hence H^{0} is semisimple. If H^{0} is not simple, it preserves a tensor decomposition of V̄, and we deduce that M_{0} lies in the family C_{4}^{′′σ} of [35, Theorem 2]: so F^{∗}(M_{0}) = Cl_{m}(q^{r}) and G_{0} = Cl_{m^{r}}(q) for some r > 1. Such embeddings are analysed in full in [48], and in all cases M_{0} is maximal in G_{0}, contrary to assumption.

Hence H^{0} is simple (and also tensor-indecomposable). Also M_{0} does not lie in any member of C, so K ∈ S, and so as before, F^{∗}(K) ∈ Lie(p). As q is large, [37, Theorem 11] shows that the embedding F^{∗}(M_{0}) < F^{∗}(K) < G_{0} lifts to an embedding H^{0} < K̄ < G, where K̄ is a simple algebraic group of the same type as F^{∗}(K). All such triples (H^{0}, K̄, G) are listed in [51, Table 1,p.282]. As observed in [51, Corollary 4], with one exception H^{0} is maximal connected in K̄ and K̄ is maximal connected in G (the exception is H^{0} = A_{2} < G_{2} < B_{3} < SO_{27} = G). The same observation applies to the triple M_{0} < K < G_{0}, noting that M_{0} = N_{G_{0}}(F^{∗}(M_{0})), K = N_{G_{0}}(F^{∗}(K)) (the exceptional case does not occur since A_{2}.2 < G_{2} so there is no novelty). Thus M_{0} is second-maximal in G_{0}, as required.

(iii) This is immediate if M_{0} is maximal in G_{0} (since then we take ρ to be trivial). So suppose now that the characteristic p is large and M_{0} is non-maximal in G_{0}. Then from the proof of (ii), either G_{0} = E_{6}(q) and M_{0} = N_{G_{0}}(D_{5}(q)), or G_{0} is classical and M_{0} < K < G_{0}, where the triple M_{0}, K, G_{0} is either as in (1), (2) or (3) above, or arises from one of the triples of algebraic groups H^{0} < K̄ < G given in [51, Table 1, p.282]; moreover M_{0} is a G_{1}-novelty with respect to K. This novelty must arise from a graph automorphism of G normalizing H^{0} but not K̄, and hence (iii) holds. The last sentence of (iii) follows also, as in all the cases above, the connected reductive group H^{0} is either semisimple, or has centre a rank 1 torus inverted by the graph automorphism ρ, whence (H⟨ρ⟩)′ contains H^{0}. □

We shall also use the following theorem.

Theorem 4.9 (i) For any Lie type Y of simple algebraic groups, there exist t, n ∈ ℕ such that if K is an algebraically closed field of characteristic 0 or p > n, and G = Y (K) has adjoint type, then G has exactly t conjugacy classes of maximal subgroups of positive dimension.

(ii) For the groups G⟨ρ⟩ in Theorem 4.8(iii), the assertion of (i) also holds, for maximal subgroups H⟨ρ⟩ of positive dimension.

Proof. (i) For X of exceptional type this is a consequence of [38, Theorem 1]. And for X = Cl(V) of classical type, [35, Theorem 1] implies that every maximal subgroup H of positive dimension either lies in a collection C, which fall into a constant number of conjugacy classes, or is simple, and acts irreducibly and tensor-indecomposably on the natural module V. Say V = V_{H}(λ), where λ is a restricted dominant weight. By [53, 4.3], for sufficiently large p the possibilities for λ are the same as they are for characteristic 0. Moreover, [51] shows that the weights λ for which H < Cl(V_{H}(λ)) is nonmaximal are also independent of the (large) prime p. The result follows.

(ii) This follows using the proof of Theorem 4.8(iii). □

As a corollary, we obtain the following uniform definability result (parts (ii), (iii) below) for maximal subgroups of positive dimension. This may have independent interest. Of course, as K is uniformly bi-interpretable with Y (K), we can also view the result as giving uniform interpretability of the subgroups in the group.

Corollary 4.10 (i) For any Lie type Y, there are finitely many formulas ψ_{1}(x̄, ȳ_{1}), …, ψ_{l}(x̄, ȳ_{l}) such that if K is an algebraically closed field then there is ā ∈ K^{l(ȳ)} and i ∈ {1, …, l} such that G = Y (K) (the simple algebraic group of adjoint type of Lie type Y) is definable in K by the formula ψ_{i}(x̄, ā)).

(ii) For any Lie type Y, there are finitely many formulas ϕ_{1}(x̄, ȳ_{1}), …, ϕ_{k}(x̄, ȳ_{k}) such that if K is an algebraically closed field and H is a maximal closed subgroup of G = Y (K) of positive dimension, and G is identified with an affine variety in K^{n}, then for some i = 1, …, k and ā ∈ K^{l(ȳ_{i})}, H = {x̄ ∈ K^{n} : K ⊧ ϕ_{i}(x̄, ā)}.

(iii) The assertion of (ii) holds for maximal subgroups H⟨ρ⟩ < G⟨ρ⟩ as in Theorem 4.8(iii).

(iv) In (iii) above, the groups H are uniformly definable in the H⟨ρ⟩ (i.e., as in (ii), finitely many formulas are required).

Proof. (i) For each characteristic, Y (K) is definable in K by some formula. In particular, it is definable in characteristic 0. By standard modeltheoretic transfer arguments (together with facts about existence of simple algebraic groups of appropriate dimension in each field), the same formula defines Y (K) over algebraically closed fields of sufficiently large prime characteristic; these transfer arguments are given in more detail in (ii) (1), (2) below. The remaining characteristics are handled case by case.

(ii) This follows from the following well-known and elementary modeltheoretic facts (see Sections 2.2 and 3.2 of [44]):

(1) any two algebraically closed fields of the same characteristic satisfy the same first order sentences;

(2) for any sentence σ in the language of rings, if σ is true in the complex field then for all but finitely many primes p, σ is true in every algebraically closed field of characteristic p.

Also, we note

(3) if G is an algebraic group, and H is infinite, core-free in G, and maximal subject to being a closed subgroup of G, then H is maximal in G; this follows from Proposition 2.7 of [42], where it is shown that any definably primitive permutation group of finite Morley rank with infinite point stabiliser is primitive.

Hence we obtain

(4) if G is an algebraic group and H is an infinite maximal subgroup of G which is closed, then H is boundedly maximal; indeed, otherwise, by moving to a saturated elementary extension of the structure (G, H), we would find an algebraic group G_{1} with a subgroup H_{1} which is maximal subject to being closed, but not maximal, contrary to (3).

Assume, using Theorem 4.9, that Y (ℂ) has exactly t pairwise nonconjugate maximal subgroups of positive dimension. Then there is a sentence σ true of ℂ which expresses that there are b̄_{1}, …, b̄_{t} such that the formulas ψ_{1}(x̄, b̄_{1}), …, ψ_{t}(x̄, b̄_{t}) define pairwise non-conjugate maximal subgroups of Y (ℂ) of positive dimension; note here that maximality is expressible, by (4). The sentence is then true in all algebraically closed fields K of sufficiently large prime characteristics; and by Theorem 4.9 (i), if the characteristic is large enough then up to conjugacy all maximal subgroups of Y (K) of positive dimension are defined by one of the ψ_{i}. The remaining characteristics can be handled case by case using (1) and the fact that there are finitely many conjugacy classes of maximal closed subgroups of positive dimension (which is true in any characteristic – see [38, Corollary 3]).

(iii) This is as in (ii).

(iv) The main point here is that by Theorem 4.8(iii), the derived subgroup of H⟨ρ⟩ has bounded index in H. Now in a group X with measurable theory, the derived subgroup X′ is always definable, and each element is a product of a bounded number of commutators. (This is proved for ‘S_{1}-theories’ by Hrushovski [20, Corollary 7.1]; the same proof applies for measurable theories, in view of the ‘Indecomposability Theorem’ in the formulation for example of [15, Remark 3.5].) If arbitrarily many commutators were required as the characteristic increased, then in characteristic 0, there would be an example for which the derived subgroup is not definable, a contradiction. Thus, (H⟨ρ⟩)′ is uniformly definable, and as H is a union of boundedly many cosets of it, H is also uniformly definable (in H⟨ρ⟩, and hence also in K). □

Now we can at last prove 4.2.

Proof of Proposition 4.2

We have already noted that part (i) of 4.2 is an easy consequence of Lemma 2.1.

We now prove part (ii) (which is Theorem 1.2). Let C_{1} be a class of finite almost simple primitive permutation groups with socles of bounded L-rank, satisfying the conditions of 4.2 (namely, that point stabilizers are unbounded, and point stabilizers which are subfield subgroups correspond to extensions of bounded degree). By passing to an infinite subclass we may assume that all the groups in C_{1} are of the same Lie type, of L-rank n, say. Let G_{1} be a member of C_{1}, and M_{1} a point stabilizer in G_{1}. Define C_{0} to be the class obtained from C_{1} by replacing each pair (G_{1}, M_{1}) in C_{1} by (G_{0}, M_{0}), where G_{0} = Soc(G_{1}) and M_{0} = M_{1} ∩ G_{0}.

Our goal is, roughly speaking, to show that the groups in C_{0} are uniformly interpretable in finite fields or difference fields, using Theorem 4.8. The interpretability yields that the corresponding non-principal ultraproducts are each definable in a measurable theory. We then use Theorem 4.7 and Corollary 4.4 to deduce that the class C_{1} is bounded. The maximality or second-maximality required in Theorem 4.7 is explicit in cases (i)(b) and (i)(d) of Theorem 4.8, by (ii). For case (i)(c), (second)-maximality does not have to be checked – see the end of the proof below.

Let c = c(n) be as in Theorem 4.8(i). Groups (G_{1}, M_{1}) of type (i)(a) in 4.8 are excluded as M_{1} is unbounded by assumption, and we postpone types (i)(b) and (c) to the end.

So suppose (G_{1}, M_{1}) has type (i)(d) of 4.8. Define G, σ as in 4.8, over a field K = 𝔽̄_{p}. The simplest case is that in which σ is just a field morphism x ↦ x^{(q)}; that is, the case where G_{0} is untwisted. We emphasise that this field automorphism of G is induced by the field automorphism x ↦ x^{q} of K, where G is viewed as a structure definable in K. Now the algebraic groups G and H are definable in the algebraically closed field K by quantifier-free formulas, say ϕ(x̄, b̄) and ψ(x̄, c̄), by quantifier-elimination for algebraically closed fields ([44, Theorem 3.2.2]). By Corollary 4.10(i), the group G is uniformly defined, by one of finitely many formulas, as the characteristic varies. Working over any given algebraically closed field K, we claim that the set of G-conjugates of such definable H is uniformly definable in K. Indeed, H is definable in K, and hence definable in G as K is G-definable. Thus, all the conjugates of H are uniformly definable in G, and hence uniformly definable in K, using the bi-interpretability (over parameters) of K and G. Since, in Theorem 4.8(i)(d), there are finitely many such subgroups H up to G-conjugacy, this proves the claim. We claim furthermore that the possible H are uniformly definable in the field K (by finitely many formulas ψ) as the characteristic of K varies. This follows from Corollary 4.10(ii), (iii), since by the above claim, we may exclude finitely many characteristics. Note that, in cases where a graph automorphism ρ is involved (in Theorem 4.8(iii)), the graph automorphism ρ has the form gτ for some g ∈ G and fixed graph automorphism τ, so G⟨ρ⟩ is uniformly definable from K, and H⟨ρ⟩ is uniformly definable by Corollary 4.10(iii). Finally, H is uniformly definable in H⟨ρ⟩ (and hence in K), by Corollary 4.10(iv).

Since the theory of algebraically closed fields has elimination of imaginaries (see [44]), we may choose the defining parameters c̄ for H canonically, so c̄ is fixed by σ (as H is σ-stable) and hence lies in 𝔽_{q}. Again, this holds for all σ-invariant G-conjugates of H. If G, an affine algebraic group, is identified with a subset of K^{r}, then, as it is quantifier-free, ϕ(x̄, b̄) defines in 𝔽_{q} the set (𝔽_{q})^{r} ∩ G, which is exactly G_{σ}; likewise for ψ(x̄, c̄). Thus, the same formulas ϕ and ψ define G_{σ} and H_{σ} in 𝔽_{q}. Furthermore, the above uniformity ensures that for each σ-stable conjugate H^{g} (g ∈ G), (H^{g})_{σ} is defined by a formula from this finite family. (Note here that σ may not act on H^{g} as a field morphism – in general it will act as wσ_{0} where w ∈ H/H^{0} and σ_{0} is a field morphism – see [36, Example 1.13] for a discussion of this. But this is not relevant to the uniform definability of the (H^{g})_{σ}.)

Now, G_{0} is uniformly definable in G_{σ}, and hence in 𝔽_{q}, by Lemma 4.5(iii), (v), and M_{0} is uniformly definable in 𝔽_{q} as it has form M_{0} = N_{G_{0}}(H_{σ} ∩ G_{0}). By Theorem 4.8(ii), M_{0} is maximal or second maximal in G_{0}. By 4.5 every ultraproduct of 𝔽_{q} has measurable theory, and the same is true for ultraproducts of the groups (G_{0}, M_{0}). Since G_{1} ≤ N_{Sym(X)}(G_{0}), where X is the space of cosets of M_{0} in G_{0}, we finish by applying Theorem 4.7.

Next, consider the case where G_{0} is twisted, but not a Suzuki or Ree group. As before, the pair (G, H) is uniformly definable. Suppose the Dynkin diagram symmetry involved in σ has order a, so a ∈ {2, 3}. Now σ^{a} is just the field morphism x ↦ x^{(q^{a})} of G. As in the untwisted case, the pair (G_{σ^{a}}, H_{σ^{a}}) is uniformly definable in the field 𝔽_{q^{a}}, by quantifier-free formulas. Furthermore, as 𝔽_{q^{a}} is an extension of 𝔽_{q} of fixed degree a, it is uniformly definable in 𝔽_{q} (this is standard); likewise, the automorphism x ↦ x^{q} of 𝔽_{q^{a}} is uniformly definable in 𝔽_{q}, as it suffices to specify its action on a basis of 𝔽_{q^{a}} over 𝔽_{q}. Hence the field automorphism σ_{0} : x ↦ x^{(q)} of G_{σ^{a}} is uniformly definable in 𝔽_{q}. Again, using Corollary 4.10, all the definability so far is uniform across characteristics. Likewise, by Lemma 4.6(i), the graph automorphism τ of G_{σ^{a}} is uniformly definable in 𝔽_{q}, and hence so is G_{σ} = (G_{σ^{a}})_{τσ_{0}}. Also H_{σ} = (H_{σ^{a}})_{τσ_{0}}. As before, the definition of H_{σ} is uniform as H varies through a conjugacy class in G. As in the untwisted case, we now define (G_{0}, M_{0}) uniformly in 𝔽_{q} and finish as before.

The remaining case is where G_{0} is a Ree or Suzuki group. We consider the case where G_{0} = ^{2}F_{4}(2^{2k+1}), the other cases being similar. Here, one does not drop in two steps to a field 𝔽_{q_{0}}. Rather, let σ_{1} be the field automorphism x ↦ x^{(2^{2k+1})}, and σ_{0} be x ↦ x^{(2^{k})}. We shall freely identify σ or σ_{1} with its restriction to a substructure. Put G = F_{4}(K), where K = 𝔽̄_{2}. A maximal subgroup in 4.8(i)(d) arises from some maximal subgroup H of G of positive dimension. Now (G_{σ_{1}}, H_{σ_{1}}) is uniformly definable in 𝔽_{2^{2k+1}}, by the same quantifier-free formulas which defines (G, H) in K; again, only finitely many formulas are needed as H ranges through a conjugacy class.

Now work in the difference field (𝔽_{2^{2k+1}}, σ_{0}) where we identify σ_{0} with its restriction. The Frobenius morphism σ of (d) has the form τσ_{0}, where τ is a graph automorphism. By Lemma 4.6(i), σ is definable in (𝔽_{2^{2k+1}}, σ_{0}), and hence so is (G_{σ}, H_{σ}) = ((G_{σ_{1}})_{σ}, (H_{σ_{1}})_{σ}). We then finish as above, using Lemma 4.5(ii).

The cases where (G_{0}, M_{0}) is of type 4.8(i)(b) or (c) are easier than the above. For (b), the above arguments show that the finite simple groups G(q) of fixed Lie type are uniformly definable in 𝔽_{q}, as q varies. It follows that a pair (G(q), N_{G(q)}(G(q_{0}))) is uniformly definable in 𝔽_{q_{0}} (or in the corresponding difference field if G(q) is a Suzuki or Ree group). We require here that the field extension 𝔽_{q_{0}} < 𝔽_{q} has bounded degree, so that 𝔽_{q} is uniformly definable in 𝔽_{q_{0}}. The same applies if G(q) is untwisted but G(q_{0}) is twisted. Here, if G(q_{0}) is a Suzuki or Ree group, we obtain definability in the appropriate difference field (𝔽_{q}, σ). Since M_{0} is maximal in G_{0} by 4.8(ii), Theorem 4.7 applies.

Finally, in case 4.8(c), the permutation groups (G_{0}, P_{0}), where P_{0} is a parabolic subgroup, have bounded permutation rank. Hence, the diameters of the corresponding primitive groups (G_{1}, M_{1}) are bounded.

This completes the proof of Proposition 4.2. □

Finally, we give two other uniform definability results for finite simple groups, which follow easily from the above arguments. The first generalises Proposition 8.1 of [19], which is stated only for simple groups over prime fields.

Corollary 4.11 Let C be a class of finite simple groups G(q) of fixed Lie type, and let e ∈ ℕ. Then there are finitely many formulas ϕ_{1}(x, ȳ_{1}), …, ϕ_{t}(x, ȳ_{t}) such that if G ∈ C and M is a maximal subgroup of G which is not a subfield subgroup G(q_{0}) with |𝔽_{q} : 𝔽_{q_{0}}| > e, then there is i ∈ {1, …, t} and b̄ ∈ G^{l(ȳ_{i})} such that in G, M is defined by the formula ϕ_{i}(x, b̄).

Proof. First, observe that maximal subgroups of bounded finite size, though they do not yield bounded classes of primitive groups, will automatically be uniformly definable in the groups: simply name the elements of the maximal subgroup using parameters.

For the other cases, we have above shown that the class of pairs (G, M) (G simple of fixed Lie rank, M maximal and not a subfield subgroup with respect to unbounded field extensions) is uniformly definable in (difference) fields. By work of Ryten (Chapter 5 of [47]), the difference fields are uniformly definable in the groups G, and hence M is definable in G, uniformly across the class. □

In the next result, when we say that an F G-module M is F -definable, we mean that the F -vector space M, the group G, and the action of G on M are all definable. Equivalently, the triple (G, M, ρ) is definable, where G has the structure of a group, M that of a F -vector space, and ρ : G → GL(M) is the representation. We sometimes omit the symbol for ρ.

In the statement, we refer to some of the basic representation theory of groups of Lie type in the natural characteristic, which can be found, for example, in [22]. Let G(q) be a quasisimple group of simply connected Lie type over 𝔽_{q}, and λ be a restricted dominant weight for G(q), meaning that λ = ∑ c_{i}λ_{i} where the λ_{i} are the fundamental dominant weights and the coefficients c_{i} are integers with 0 ≤ c_{i} ≤ p − 1, where p = char(𝔽_{q}). For such λ, there is a Weyl module W_{λ} for G(q) over 𝔽̄_{q} of highest weight λ; W_{λ} has a quotient V_{λ} of highest weight λ which is an irreducible 𝔽̄_{q}G(q)-module. This module is realised over 𝔽_{q^{a}} (a ≤ 3), since this is a splitting field for G(q), and we let V_{λ}(q) be the corresponding irreducible 𝔽_{q^{a}}G(q)-module of highest weight λ.

Proposition 4.12 Let C be a class of structures (G(q), V_{λ}(q)), ρ_{λ}(q)) where G(q) is quasisimple and simply connected of fixed Lie type (possibly twisted), λ is a restricted weight, and ρ_{λ}(q) is the corresponding representation. Then the members of C are uniformly definable in 𝔽_{q} (or in the corresponding difference fields in the cases of Suzuki and Ree groups).

Proof. Let G be the Chevalley group over 𝔽̄_{q} corresponding to G(q), and let σ be a Frobenius morphism such that G_{σ} = G(q). The construction on pp.192-193 of [22] makes clear that the triple (G, W_{λ}, ρ_{λ}) is definable in 𝔽̄_{q}. The module V_{λ} is an irreducible quotient of W_{λ}, so is also definable in 𝔽̄_{q} (it suffices to specify by parameters an 𝔽̄_{q}-basis for the submodule factored out). Furthermore, the definition is uniform in q: there are finitely many formulas, such that in each characteristic, one of these formulas suffices to define the module. Indeed, the corresponding representation is definable in characteristic 0; by standard model-theoretic transfer arguments the same definition applies in all but finitely many finite characteristics, and the rest can be handled independently. Also, for example by working with sufficiently large q, any parameters in the definition can be chosen to be fixed by x ↦ x^{q}.

If G(q) is untwisted, then the quadruple Z_{λ}(q) := (𝔽_{q}, V_{λ}(q), G(q), ρ_{λ}(q)) (where ρ_{λ}(q) is the corresponding representation) is obtained from Z_{λ} := (𝔽̄_{q}, V_{λ}, G, ρ_{λ}) by taking the fixed point set of the Frobenius morphism σ : x ↦ x^{q}. By quantifier elimination in algebraically closed fields, Z_{λ} is definable in 𝔽̄_{q} by a quantifier-free formula. The same formula then defines Z_{λ}(q) in 𝔽_{q}.

Suppose now that G(q) is twisted, say G(q) < G^{∗}(q^{a}), where G^{∗} is untwisted and a ≤ 3. Thus, G(q) is the fixed point set of an automorphism (a product of field and graph automorphisms) of G^{∗}(q^{a}). The module V_{λ}(q) is the restriction of the irreducible module V_{λ}(q^{a}) of G^{∗}(q^{a}), and the structure Z_{λ}(q^{a}) := (𝔽_{q^{a}}, V_{λ}(q^{a}), G^{∗}(q^{a}), ρ_{λ}(q^{a})) is uniformly definable in 𝔽_{q^{a}}, by the last paragraph. In the case when G(q) = PSU_{n}(q) < PSL_{n}(q^{2}), the field 𝔽_{q^{2}} is (uniformly) definable in 𝔽_{q}, as is the graph automorphism τ and the field automorphism x ↦ x^{(q)} of G^{∗}(q^{a}), and it follows that Z_{λ}(q) is uniformly definable in 𝔽_{q} (just take fixed point sets). The same argument applies in all cases except for the Suzuki and Ree groups. So consider for example the case G(q) = ^{2}G_{2}(3^{2k+1}) < G^{∗}(q) = G_{2}(3^{2k+1}). Here, the irreducible module of highest weight λ of G_{2}(3^{2k+1}) is (uniformly) definable in 𝔽_{3^{2k+1}}, as is the corresponding structure Z_{λ}(3^{2k+1}) which codes the representation of G_{2}(3^{2k+1}) of weight λ. Hence the twisted group G(q), and indeed Z_{λ}(q) is definable in (𝔽_{3^{2k+1}}, x ↦ x^{3^{k}}) (take fixed points of the product of a field automorphism x ↦ x^{(3^{k})} and a graph automorphism). The same argument applies for the groups ^{2}F_{4}(2^{2k+1}) and ^{2}B_{2}(2^{2k+1}). □

5 The remaining cases

In this section we complete the proof of Theorem 1.1 and its converse. First, we consider primitive permutation groups (X, G) of simple diagonal type. The following result proves Theorem 1.1(4) and its partial converse.

Lemma 5.1 (i) If C is a bounded class consisting of primitive groups G of simple diagonal type, then these all have socles of the form T^{k}, where T is a simple group of bounded L-rank and k is bounded.

(ii) Conversely, suppose C consists of primitive groups (X, G) of simple diagonal type satisfying the conditions in (i). Suppose further that there is t ∈ ℕ, and for all (X, G) ∈ C there are primitive L ≤ Sym_{k} and P ≤ G such that P is primitive on X and satisfies T^{k} ≤ P ≤ H wr L, where Soc(H) = T and |H : T | ≤ t. Then C is bounded.

Proof. (i) Suppose that C is a bounded class of finite primitive permutation groups (X, G) of simple diagonal type. For a typical member of C we adopt the notation of Section 2, case (3)(a). Thus G has socle T^{k} for some non-abelian simple group T.

First, we show k is bounded. For ease of notation, we consider primitive groups of simple diagonal type of the form G = T wr Sym_{k} acting on the right cosets of D × Sym_{k}, where D is a diagonal subgroup of T^{k}. Write H = D × Sym_{k}. We may identify x ∈ X with H, pick g ∈ T \ {1}, and consider the orbital graph which has an edge between H and H(1, …, 1, g). A vertex at distance i from x is a coset of the form H(g_{1}, …, g_{k}), where the g_{j} can be chosen so that at most i of them are non-identity. Thus, if C ⊂ F_{d}, then k ≤ d.

We claim next that the groups T are uniformly simple, that is, all ultraproducts of the groups T are simple. Indeed, pick any g ∈ T \ {1}, and as above consider the orbital graph whose edge set E on X has an edge between H and H(1, …, 1, g). Any coset of H in G has the form H(g_{1}, …, g_{k}) for some g_{1}, …, g_{k} ∈ T.

We claim that if a coset H(g_{1}, …, g_{k}) is at distance at most j from H in the graph (X, E), then the representative (g_{1}, …, g_{k}) can be chosen so that each g_{i} is a product of at most j T -conjugates of g and g^{−1}. To see this, observe that the neighbours of vertex H have the form H(1, …, 1, g)h where h ∈ H, so have the form H(h_{1}, …, h_{k}) where at most one of the h_{i} is non-identity, and that element is a conjugate of g. Hence, the neighbours of H(g_{1}, …, g_{k}) have the form H(h_{1}, …, h_{k})(g_{1}, …, g_{k}), with (h_{1}, …, h_{k}) as above. The claim follows by induction. It follows that there is bounded e such that if g, h ∈ T \ {1} then h is a product of at most e conjugates of g and g^{−1}; that is, the groups T are uniformly simple. From this, it follows easily that the L-rank of T is bounded. For example, if the groups T are of the form PSL_{n}(q), and Z is the conjugacy class of transvections, and t is least such that Z^{t} = PSL_{n}(q), then t → ∞ as n → ∞.

(ii) The groups T are uniformly definable in finite fields (or possibly difference fields). Hence, using Lemma 4.6(ii), the group H wr L is uniformly so definable, as is its stabiliser in the action on X. Now P is a union of a bounded number of cosets of T^{k} in H wr L, so P, and its action on X, are uniformly definable. It follows from Corollary 4.4 that there is a uniform bound on the diameter of the permutation groups (X, P), and as P ≤ G ≤ Sym(X), this bound holds also for C. □

Next we prove Theorem 1.1(5) and its partial converse.

Lemma 5.2 Let C be a class of finite primitive permutation groups (X, G) of product action type, with G ≤ H wr Sym_{ℓ} (product action on Y^{ℓ}) where (Y, H) is of almost simple or simple diagonal type and Soc(G) = Soc(H)^{l}.

(i) If C ⊂ F_{m} for some m, then there is a bound on the values of ℓ which occur. Also, diam(Y, H) ≤ m.

(ii) If C is a class of groups of almost simple or simple diagonal type with C ⊂ F_{m}, and ℓ ∈ ℕ, then

{(Y^{ℓ}, H wr Sym_{ℓ}) (product action) : (Y, H) ∈ C} ⊂ F_{ℓm}.

Proof. (i) Any orbital graph for (X, G) whose edges are translates of the pair (y_{1}, y_{2}, …, y_{ℓ}), (y′_{1}, y_{2}, …, y_{ℓ}) (with y_{1} ≠ y′_{1}) will have diameter at least ℓ. For the second assertion, note that if Δ is an orbital of (Y, H) with graph having diameter e > m, and (y_{1}, y′_{1}) ∈ Δ, then any orbital graph containing an edge {(y_{1}, y_{2}…. , y_{l}), (y′_{1}, y_{2}, …, y_{l})} has diameter at least e.

(ii) We leave this to the reader. □

Finally we complete the proof of Theorem 1.1(6).

Lemma 5.3 There is no infinite subset of F_{m} consisting entirely of permutation groups of twisted wreath type.

Proof. A group (X, G) of twisted wreath type has socle of form B = T^{k} acting regularly on X, so identifiable with X. It can be checked (e.g. from the description in Section 2) that if x, y ∈ T^{k} differ in one coordinate, then the orbital graph for (X, G) with {x, y} as an edge has diameter at least k. Also, as noted in Section 2, |G| ≤ k!((k − 1)!)^{k}. Thus, a bounded class of primitive groups of twisted wreath type contains just finitely many groups. □

6 Proof of Corollary 1.3

To prove Corollary 1.3, we must show that for any given Lie type Y, there are only finitely many values of q such that there exists an almost simple group with socle Y (q) which has a primitive, distance-transitive, non-parabolic action on the vertex set of a (non-complete) graph Γ_{q}.

So assume this is false for some Lie type Y, and let C be the infinite class of such primitive distance-transitive permutation groups. Let (X, G) ∈ C with Soc(G) = Y (q) and let H = G_{x} be a point stabilizer, so that H is a maximal non-parabolic subgroup of G. As shown in [5, 7.7.2], distancetransitivity implies that |H| ≥ (|G|/k(G))^{1/2}, where k(G) is the number of irreducible characters of G. Since k(G) is of the order of q^{r} where r is the Lie rank of Y (q), it follows that if H is a subfield subgroup G(q_{0}), then [𝔽_{q} : 𝔽_{q_{0}}] is bounded. Hence Theorem 1.2 shows that C is a bounded class, and so diam(Γ_{q}) < c, where c is a constant (depending only on the Lie type Y). Since Γ_{q} is distance-transitive, the permutation rank of G on X is equal to 1 + diam(Γ_{q}), hence is also bounded. However, the main result of [50] shows that the rank of any non-parabolic permutation representation of Y (q) is unbounded as q → ∞, so this is a contradiction. This completes the proof of Corollary 6.

7 Infinite primitive ultraproducts of finite permutation groups

As discussed in the Introduction (see the goals (i)-(v)), Theorem 1.1 translates into a description of primitive non-principal ultraproducts of finite permutation groups. We sketch the description here. See Section 2 for more background on the ultraproduct construction.

By a ‘large’ set, we always mean a set in the ultrafilter. In arguments below, we may always replace a class of finite primitive permutation groups by a large subclass, and restrict the ultrafilter to this subclass. So, let (X^{∗}, G^{∗}) be a primitive ultraproduct of a class C of finite permutation groups, with respect to some non-principal ultrafilter. We may suppose the members of C are all primitive, since an ultraproduct of non-trivial congruences will give a G^{∗}-congruence on X^{∗}. For any d, if the subset of C lying in F_{d} is not large, then some orbital graph of (X^{∗}, G^{∗}) has diameter at least d. Thus, by primitivity, after replacing C be a large subset, we may suppose that C ⊆ F_{d}. By the O’Nan-Scott Theorem, each group in C belongs to one of the classes (1)-(6) of primitive permutation groups listed in the Introduction before Theorem 1.1, and there will be a large subclass of groups all of fixed type; for example, if the groups in C are of almost simple type, and there is no large subclass of type (3), then C itself has type (2), and in any non-principal ultraproduct, the group will resemble an infinite dimensional classical group. Hence we may assume C consists of groups of one of the types (1)-(6), so Theorem 1.1 applies.

The exact description of the ultraproducts is hard to state. However, the following should indicate the rough structure, and more information can be extracted as needed.

(a) A primitive non-principal ultraproduct of affine primitive permutation groups of the form (V_{d}(q), V_{d}(q)H), where d is fixed, q increasing, and H ≤ GL_{d}(q) is irreducible, will have the form (V, V H), where V = V_{d}(K), H ≤ GL_{d}(K) is irreducible, and K is a pseudofinite field. To see that irreducibility is preserved, observe that we can view the fields 𝔽_{q} as part of the structures, so express irreducibility by a first order sentence. It then holds in the ultraproduct, by Łos’s Theorem (see Section 2).

(b) A non-principal ultraproduct of affine groups (V_{n}(q), V_{n}(q) Cl_{n}(q_{0})), where n → ∞ as |V_{n}(q)| → ∞ and |𝔽_{q} : 𝔽_{q_{0}}| = t, has the form (V, V H), where V = V_{2^{ℵ_{0}}} (K), K is a finite or pseudofinite field, and H is a subgroup of Cl_{2^{ℵ_{0}}} (L) where |K : L| = t and H is an ultraproduct of the corresponding finite classical groups, with the corresponding action.

(c) An arbitrary non-principal ultraproduct (X, G) of groups of type (1) has the following form. There is a finite or pseudofinite field L with a finite extension K, a K-vector space U_{1} of dimension 2^{ℵ_{0}}, a t-dimensional Kvector space U_{2}, such that V = V_{1} ⊕…⊕V_{r}, and V_{1} = U_{1} ⊗U_{2} ≅ V_{2}, …, V_{r}. There is a group H ≤ GL(V_{1}) wr Sym_{r} preserving the above direct sum decomposition, inducing a transitive group on {V_{1}, …, V_{r}}, and inducing on V_{1} a group H_{1} which contains a normal subgroup with the same orbits on finite tuples as Cl_{2^{ℵ_{0}}} (L) ⊗ 1_{U_{2}} acting naturally. The group (X, G) has the form (V, V H).

(d) Let (X, G) be a non-principal ultraproduct of groups of type (2), that is almost simple groups with alternating or classical socle of unbounded Lrank, in a standard t-action. We have no clear description in this case, beyond the above. For example, X could be the collection of t-dimensional subspaces of a 2^{ℵ_{0}}-dimensional vector space over a finite or pseudofinite field, and G an ultraproduct of groups PSL_{n}(q) with n → ∞.

(e) If C consist of permutation groups (X, G) of type (3), then, by cutting down to a large subclass of C, we may suppose that G is always of the same Lie type. Now there is a subgroup H^{∗} of G^{∗} such that (X^{∗}, H^{∗}) is definable in a pseudofinite field K^{∗} or difference field (K^{∗}, σ). The group G^{∗} has a unique minimal normal subgroup, which is equal to the unique minimal normal subgroup of H^{∗} and is a simple pseudofinite group. The difference fields which arise are those associated with Suzuki and Ree groups – ultraproducts of difference fields (𝔽_{2^{2k+1}}, x ↦ x^{2^{k}}) or (𝔽_{3^{2k+1}}, x ↦ x^{3^{k}}). In the notation of [47] these infinite difference fields satisfy the theories PSF_{1,2,2} and PSF_{1,2,3} respectively.

(f) If C consists of groups of simple diagonal type, then, essentially, (X^{∗}, G^{∗}) is of simple diagonal type, with Soc(G^{∗}) having form T^{k} for some k ∈ ℕ and pseudofinite simple group T.

(g) An ultraproduct of groups (X, G) of type (5), where X = Y^{k} and G ≤ H wr Sym_{k} will embed in a group of form H^{∗} wr Sym_{k} in product action on a set (Y^{∗})^{k}. More information can be extracted; for example, (Y^{∗}, H^{∗}) will be of one of the types (d)-(f).

Likewise, the partial converses to Theorem 1.1 yield that, when the above descriptions are made more precise (and with extra assumptions in the affine case and cases (f) and (g)), the corresponding groups are primitive. In case (e), it is important that, given a bound on the Lie rank and a bound on field extensions for subfield subgroups, finitely many formulas suffice to define the possible finite permutation groups. This last point was central to the proof of Proposition 4.2.

The description of primitive pseudofinite ω-saturated permutation groups is somewhat looser. For example, for the fields involved, we can only assert that they are pseudofinite if, in the ultraproduct case, they are definable. This definability issue is delicate. As an illustration, in Lemma 3.1(i) we assumed that K^{∗} ≤ H. This suffices to ensure definability of the field in the ultraproduct, but there may be bounded classes without K^{∗} ≤ H, and without this definability.

Initially, we hoped for a close connection between primitive ultraproducts (X^{∗}, G^{∗}) of finite permutation groups and simple theories, analogous to the smoothly approximable structures ([26], [12]). We cannot hope in general for the ultraproducts of the permutation groups to have simple theory, as the unbounded L-rank case is completely wild. One might have hoped that there is a supersimple structure M^{∗} with domain X^{∗} such that G^{∗} = Aut(M^{∗}), or, better (to avoid problems with field automorphisms), so that Aut(M^{∗}) ≤ G^{∗} ≤ N_{Sym(X^{∗})}(Aut(M^{∗})). The latter seems correct, with the exception of cases where ultraproducts of unbounded L-rank symplectic, orthogonal or unitary groups, over unbounded fields, are involved. It was shown by Grainger [16, Proposition 7.4.1] that the theories of infinite dimensional vector spaces carrying a non-degenerate sesquilinear form, over an infinite field, parsed in a two-sorted language, do not have simple theory. In Grainger’s thesis some independence theory is developed for such structures (over an algebraically closed field), so there may be a reasonable model theory for all such structures M^{∗}.

References

[1] M. Aschbacher, ‘On the maximal subgroups of the finite classical groups’, Invent. Math. 76 (1984) 469–514.

[2] J. Ax, ‘The elementary theory of finite fields’, Ann. Math. 88 (1968) 239–271.

[3] G.M. Bergman, H.W. Lenstra, ‘Subgroups close to normal subgroups’, J. Alg. 127 (1989) 80–97.

[4] J. van Bon, ‘Finite primitive distance-transitive graphs’, European J. Combin. 28 (2007) 517–532.

[5] A.E. Brouwer, A.M. Cohen and A. Neumaier, Distance-regular graphs, Ergebnisse der Mathematik und ihrer Grenzgebiete, Springer-Verlag, Berlin, 1989.

[6] N. Burgoyne, R. Griess, and R. Lyons, ‘Maximal subgroups and automorphisms of Chevalley groups’, Pacific J. Math. 71 (1977) 365–403.

[7] R.W. Carter, Simple groups of Lie type, Wiley, London, 1972.

[8] Z. Chatzidakis, ‘Model theory of finite fields and pseudofinite fields’, Ann. Pure Appl. Logic 88 (1997) 95–108.

[9] Z. Chatzidakis, L. van den Dries, A.J. Macintyre, ‘Definable sets over finite fields’, J. reine und angew. Math. 427 (1992) 107–135.

[10] Z. Chatzidakis, E. Hrushovski, ‘The model theory of difference fields’, Trans. Amer. Math. Soc. 351 (1999) 2997–3071.

[11] Z. Chatzidakis, E. Hrushovski, Y. Peterzil, ‘Model theory of difference fields. II. Periodic ideals and the trichotomy in all characteristics’, Proc. London Math. Soc. (3) 85 (2002) 257–311.

[12] G. Cherlin, E. Hrushovski, Finite structures with few types, Annals of Mathematics Studies No. 152, Princeton University Press, Princeton, 2003.

[13] G. Cherlin, A.H. Lachlan, ‘Stable finitely homogeneous structures’, Trans. Amer. Math. Soc. 296 (1986) 815–850.

[14] R. Elwes, H.D. Macpherson, ‘A survey of asymptotic classes and measurable structures’, in Model theory with applications to algebra and analysis, Vol.2 (Eds. Z. Chatzidakis, H.D. Macpherson, A. Pillay, A. Wilkie), London Math. Soc. Lecture Notes Vol. 350, Cambridge University Press, Cambridge, pp. 125–159.

[15] R. Elwes, M.J. Ryten, ‘Measurable groups of low dimension’, Math. Logic Quarterly 54 (2008) 374–386.

[16] N. Grainger, Stability, simplicity, and the model theory of bilinear forms, Ph.D thesis, University of Manchester, 1999.

[17] R.M. Guralnick, M.W. Liebeck, H.D. Macpherson, G.M. Seitz, ‘Modules for algebraic groups with finitely many orbits on subspaces’, J. Algebra 196 (1997) 211–250.

[18] D.G. Higman, ‘Intersection matrices for finite permutation groups’, J. Algebra 6 (1967) 22–42.

[19] E. Hrushovski, A. Pillay, ‘Definable subgroups of algebraic groups over finite fields’, J. reine und angew. Math. 462 (1995) 69–91.

[20] E. Hrushovski, ‘Pseudofinite fields and related structures’, in Model theory and applications (Eds. L. Bélair, Z. Chatzidakis, P. D’Aquino, D. Marker, M. Otero, F. Point, A. Wilkie), Quaderni di Matematica vol. 11, Seconda Università si Napoli, pp. 151–212.

[21] E. Hrushovski, ‘The elementary theory of the Frobenius automorphism’, preprint, arXiv:math/0406514v1 [math.LO].

[22] J.E. Humphreys, Linear algebraic groups, Graduate Texts in Mathematics, Springer, New York, 1987.

[23] G.D. James, ‘On the minimal dimensions of irreducible representations of symmetric groups’, Math. Proc. Cambridge Philos. Soc. 94 (1983) 417–424.

[24] N.F.J. Inglis, ‘The embedding O(2m, 2^{k}) ≤ Sp(2m, 2^{k})’, Arch. Math. (Basel) 54 (1990) 327–330.

[25] I.M. Isaacs, Character theory of finite groups, Pure and Applied Mathematics, No. 69, Academic Press, 1976.

[26] W.M. Kantor, M.W. Liebeck, H.D. Macpherson, ‘ℵ_{0}-categorical structures smoothly approximated by finite substructures’, Proc. London Math. Soc. 59 (1989) 439–463.

[27] 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.

[28] P.B. Kleidman, The subgroup structure of some finite simple groups, PhD Thesis, University of Cambridge, 1987.

[29] P.B. Kleidman, ‘The maximal subgroups of the Steinberg triality groups 3D_{4}(q) and of their automorphism groups’, J. Algebra 115 (1988) 182–199.

[30] P.B. Kleidman and M.W. Liebeck, The subgroup structure of the finite classical groups, London Math. Soc. Lecture Note Series 129, Cambridge Univ. Press, Cambridge, 1990.

[31] V. Landazuri and G.M. Seitz, ‘On the minimal degrees of projective representations of the finite Chevalley groups’, J. Algebra 32 (1974) 418–443.

[32] M.W. Liebeck, ‘On the orders of maximal subgroups of the finite classical groups’, Proc. London Math. Soc. 50 (1985) 426–446.

[33] M.W. Liebeck, C.E. Praeger, J. Saxl, ‘On the O’Nan-Scott Theorem for finite primitive permutation groups’, J. Austral. Math. Soc. (Ser. A) 44 (1988) 389–396.

[34] M.W. Liebeck, J. Saxl, G.M. Seitz, ‘Subgroups of maximal rank in finite exceptional groups of Lie type’, Proc. London Math. Soc. 65 (1992) 297–325.

[35] M.W. Liebeck, G.M. Seitz, ‘On the subgroup structure of classical groups’, Invent. Math. 134 (1998) 427–453.

[36] M.W. Liebeck, ‘Subgroups of simple algebraic groups and of related finite and locally finite groups of Lie type’, in Finite and Locally Finite Groups (Eds. B. Hartley, G.M. Seitz, A.V. Borovik, R.M. Bryant), Proceedings of the NATO Advanced Study Institute on Finite and Locally Finite Groups, Istanbul, Turkey, 1994, Kluwer, Dordrecht, 1995, 71–96.

[37] M.W. Liebeck and G.M. Seitz, ‘On the subgroup structure of exceptional groups of Lie type’, Trans. Amer. Math. Soc. 350 (1998) 3409–3482.

[38] M.W. Liebeck, G.M. Seitz, ‘The maximal subgroups of positive dimension in exceptional algebraic groups’, Mem. Amer. Math. Soc. No. 802 2004.

[39] M.W. Liebeck and A. Shalev, ‘Bases of primitive linear groups’, J. Algebra 252 (2002) 95–113.

[40] F. Lübeck, ‘Small degree representations of finite Chevalley groups in defining characteristic’, LMS J. Comput. Math. 4 (2001) 135–169.

[41] H.D. Macpherson, ‘Homogeneous and smoothly approximated structures’, in Algebraic model theory (eds. B.T. Hart, A.H. Lachlan, M.A. Valeriote), NATO ASI series, Kluwer, Dordrecht, 1997, pp. 161–179.

[42] H.D. Macpherson and A. Pillay, ‘Primitive permutation groups of finite Morley rank’, Proc. London Math. Soc. 70 (1995) 481–504.

[43] H.D. Macpherson and C. Steinhorn, ‘One-dimensional asymptotic classes of finite structures’, Trans. Amer. Math. Soc. 360 (2008) 411–448 [44] D. Marker, Model Theory: An Introduction, Graduate Texts in Mathematics,

Springer, New York, 2002.

[45] F. Point, ‘Ultraproducts and Chevalley groups’, Arch. Math. Logic 38 (1999) 355–372.

[46] C.E. Praeger, J. Saxl, ‘On the orders of finite primitive permutation groups’, Bull. London Math. Soc. 12 (1980) 303–307.

[47] M.J. Ryten, Model theory of finite difference fields and simple groups, Ph.D thesis, University of Leeds, 2007. http://www.maths.leeds.ac.uk/pure/staff/macpherson/ryten1.pdf

[48] M. Schaffer, ‘Twisted tensor product subgroups of finite classical groups’, Comm. Algebra 27 (1999) 5097-5166.

[49] G. Schlichting, ‘Operationen mit periodischen Stabilisatoren’, Archiv der Mathematik (Basel) 34 (1980) 97–99.

[50] G.M. Seitz, ‘Small rank permutation representations of finite Chevalley groups’, J. Algebra 28 (1974) 508–517.

[51] G.M Seitz, ‘The maximal subgroups of classical algebraic groups’, Mem. Amer. Math. Soc. No. 365 (1987).

[52] G.M. Seitz, ‘Representations and maximal subgroups of finite groups of Lie type’, Geom. Dedicata 25 (1988) 391-406.

[53] T.A. Springer, ‘Weyl’s character formula for algebraic groups’, Invent. Math. 5 (1968) 85–105.

[54] M. Suzuki, ‘On a class of doubly transitive groups: I, II’, Ann. of Math. 75 (1962) 105–145; 79 (1964) 514–589.

[55] A. Wagner, ‘An observation on the degrees of projective representations of the symmetric and alternating group over an arbitrary field’, Arch. Math. 29 (1977) 583–589.

[56] F. Wagner, Simple theories, Kluwer, Dordrecht, 2000.

[57] J.S. Wilson, ‘On pseudofinite simple groups’, J. London Math. Soc. 51 (1995) 471–490.

Martin Liebeck, Department of Mathematics, Imperial College, London SW7 2BZ, UK m.liebeck@imperial.ac.uk Dugald Macpherson, School of Mathematics, University of Leeds, Leeds LS2 9JT, UK h.d.macpherson@leeds.ac.uk

Katrin Tent, Institut für Mathematische Logik, Universität Münster, Einsteinstrasse 62, 48149 Münster, Germany, tent@uni-muenster.de