Suborbits in Infinite Primitive Permutation Groups

David M. Evans

School of Mathematics, University of East Anglia, Norwich NR4 7TJ email: d.evans@uea.ac.uk

Abstract: For every infinite cardinal κ, we construct a primitive permutation group which has a finite suborbit paired with a suborbit of size κ. This answers a question of Peter M. Neumann.

1 Introduction

In this paper we prove the following (see Corollary 2.10): Theorem For every infinite cardinal κ, there is a primitive permutation group which has a finite suborbit paired with a suborbit of size κ.

The existence of such groups answers a question raised by Peter M. Neumann ([8]), and completes a rough taxonomy of infinite, primitive permutation groups which we shall outline below. It may also retrieve some ‘lost’ examples of Ehud Hrushovski (see [8]).

As is easy to see, the theorem is equivalent to constructing a directed graph (we shall write digraph) with finite out-valency and in-valency κ, whose automorphism group is primitive on vertices and transitive on directed edges. The construction we give of such graphs is very similar to constructions used throughout model theory: we construct a digraph by amalgamating certain smaller digraphs in a systematic way, so that partial automorphisms of the large digraph can be extended to automorphisms. The reader unfamiliar with these types of constructions could look at [2] or [4] for the prototype (due to R. Fraïssé [5]), and also [7] for more recent variations due to Hrushovski. Our exposition is, however, reasonably self-contained.

In the remainder of the Introduction we give some background material about infinite permutation groups (although this is not necessary for the constructions in Section 2). The unreferenced material tends to be considered as folk-lore, but it might more properly be attributed to unpublished lectures of Peter M. Neumann from the 1980’s. Acknowledgements: I should like to thank Bernhard Herwig and Peter M. Neumann for helpful discussions and comments.

1.1 Suborbits and Orbitals

We shall assume a basic familiarity with permutation groups, all of which can be found in [2], for example. When we say that (G, Ω) is a permutation group, we mean that G is a subgroup of Sym(Ω), the full symmetric group on Ω. Assume henceforth that G is transitive on Ω, and let α be an element of Ω. Let G_{α} = {g ∈ G : gα = α}. Then the G_{α}-orbits on Ω are called the suborbits. The singleton {α} is the trivial suborbit. The G-orbits on Ω^{2} are called the orbitals and {(ω, ω) : ω ∈ Ω} is the trivial orbital. If Δ ⊆ Ω^{2} is a non-trivial orbital, then we may consider the corresponding orbital digraph. This is a directed graph with vertex set Ω and edge set Δ. It is clear that G acts as a group of automorphisms of this, and is transitive on vertices and on directed edges. If we ignore the orientation on the edges we obtain the orbital graph with vertex set Ω and edge set {{β, γ} : (β, γ) ∈ Δ}.

There is a natural correspondence between the suborbits and the orbitals. Suppose Γ is a suborbit and β ∈ Γ. Then the corresponding orbital is the G-orbit on Ω^{2} which contains (α, β). It is easy to check that this is well defined, and moreover, if Δ is any orbital then the corresponding suborbit is the one containing γ, where γ is any element of Ω such that (α, γ) ∈ Δ.

If Δ is an orbital then so is Δ^{∗} = {(γ, β) : (β, γ) ∈ Δ}. This is called the paired orbital. This pairing of the orbitals induces a pairing on the suborbits. If Γ is a suborbit and β ∈ Γ, let g ∈ G be such that gβ = α, and let γ = gα. Then Γ^{∗}, the paired suborbit, is the suborbit which contains γ.

The orbital digraphs provide a rather more enlightening way of saying this. Suppose Δ is an orbital with corresponding suborbit Γ. Then Γ is the set of out-vertices for α in the orbital digraph with edge set Δ. Moreover, Γ^{∗} is the set of in-vertices for α in this digraph. Hence we have the connection between the theorem and the construction of digraphs, as stated in the opening paragraphs.

We conclude this subsection with a very useful criterion for primitivity, due to D. G. Higman ([6]).

Lemma 1.1 The transitive permutation group (G, Ω) is primitive if and only if all its non-trivial orbital graphs are connected. □

1.2 A Taxonomy

Throughout this subsection Ω is an infinite set and G is a primitive permutation group on Ω. We claim that such groups divide into three cases: Case A: There is no (non-trivial) finite suborbit; Case B: There is a (non-trivial) finite suborbit Γ and Γ^{∗} is finite; Case C: There is a finite suborbit Γ with Γ^{∗} infinite.

To see that Cases B and C do not overlap, we have:

Lemma 1.2 In Case B all suborbits are finite, and Ω is countable.

Proof. Let Δ be the orbital corresponding to Γ and consider the orbital graph from this (so this has edge set Δ ∪ Δ^{∗}). This is locally finite and connected. So Ω is countable, and any element of Ω lies in a finite G_{α}-orbit (as there are only finitely many points at any given distance from α in the graph). □

It is reasonable to view Case A as the ‘typical’ case. Corollary 2.10 says that Case C is non-empty. In Case B the orbital digraphs are locally finite, and their automorphism groups are (in a natural way) locally compact groups. There are some highly non-trivial results concerning such permutation groups. For example, the ‘Tarski monsters’ of Ol’shanskii provide examples of infinite groups satisfying the hypotheses of the following result.

Theorem 1.3 (G. Schlichting [10], G. Bergman and H. Lenstra [1]) If there is a (finite) bound on the size of the suborbits, then G_{α} is finite.

The following is due to C. Praeger ([9]). See also the work of V. Trofimov [11], and [3] (Praeger’s paper is cited incorrectly in the latter).

Theorem 1.4 In Case B, we have |Γ| = |Γ^{∗}|, for all suborbits Γ.

It should be clear that Lemma 1.2 generalises in various ways. For example, if G (still primitive) has a suborbit of size κ ≥ ℵ_{0} paired with a suborbit of size λ ≥ κ, then |Ω| = λ. Examples with κ < λ are described in [8].

2 The Construction

Throughout, our digraphs are anti-symmetric, loopless, and have no multiple edges. Suppose we have a digraph with vertex set A and edge set E ⊆ A^{2}. If B ⊆ A then the subdigraph on B has vertex set B and edge set E ∩ B^{2}. Henceforth, we shall use the same notation for a digraph and its vertex set (thus, the above digraphs would be called simply A and B). If A_{1}, A_{2} are digraphs a function α : A_{1} → A_{2} is a digraph embedding if it is an isomorphism between A_{1} and the subdigraph of A_{2} on α(A_{1}).

If a ∈ A then (as in [3]) a^{⇒} is the set of vertices which are reachable from a by an outwarddirected path (this includes a). We say that A is finitely generated (f.g.) if A is the union of a finite number of subsets of this form. If X ⊆ A then X^{⇒} = ⋃{a^{⇒} : a ∈ X}. The (outward) directed binary tree is denoted by T. We work with digraphs A satisfying:

C1 for all a ∈ A we have a^{⇒} ≅ T.

Notation 2.1 Suppose X ⊆ A. Write X ≤ A to mean that if a ∈ A and a^{⇒} \ X^{⇒} is finite then a ∈ X. Write X ≤^{+} A if additionally a^{⇒} ∩ X is f.g. for all a ∈ A.

Lemma 2.2 (i) If X ≤ A then X = X^{⇒}. (ii) If X ≤ A and Y ⊆ A is such that Y^{⇒} = Y, then X ∩ Y ≤ Y. (iii) If X ≤ Y ≤ A, then X ≤ A. (iv) If X ≤^{+} Y ≤^{+} A, then X ≤^{+} A.

Proof. (i)-(iii) are left to the reader. For (iv), let a ∈ A. Then a^{⇒} ∩ Y = ⋃_{i≤n} y\overrightarrow{i} for some y_{1}, …, y_{n} ∈ Y. Then a^{⇒} ∩ X = ⋃_{i≤n}(y\overrightarrow{i} ∩ X), which is finitely generated. Then (iv) follows, by (iii). □

Remarks 2.3 In any digraph A satisfying C1, the following two relations on vertices are equivalence relations invariant under all automorphisms of A:

a ∼ b ⇔ a^{⇒} △ b^{⇒} is finite
a ≃ b ⇔ a^{⇒} ∩ b^{⇒} is dense in a^{⇒} and b^{⇒}.

(Here, X ⊆ T is dense if (∀t ∈ T)t^{⇒} ∩ X ≠ ∅.) The conditions below will ensure that these relations are trivial in the digraphs we work with.

Definition 2.4 Let C be the following category. The objects are digraphs A satisfying C1 and: C2 we have a ≤^{+} A for all a ∈ A; C3 for all finite X ⊆ A there exists a finitely generated Y ≤ A with X ⊆ Y.

The morphisms of C are digraph embeddings ϕ : A → B with ϕ(A) ≤^{+} B (we shall refer to these simply as embeddings).

Remarks 2.5 (i) By Lemma 2.2 the composition of two morphisms is a morphism. Also, by C2, it is easy to see that if Y ≤ A is f.g. then Y ≤^{+} A. (ii) If A ≤^{+} B and B ∈ C then A ∈ C. Indeed, as A ≤ B we have A^{⇒} = A, so C1 holds. For C2 we have a^{⇒} ≤ A for a ∈ A (by Lemma 2.2) and a^{⇒} ∩ b^{⇒} is f.g. for all b ∈ B. Finally, suppose X ⊆ A is finite. Let Y ≤^{+} B be f.g. and contain X. Then Y ∩ A ≤ A and Y ∩ A is f.g. (as A ≤^{+} B). Thus C3 holds. (iii) Suppose A ∈ C. Then for all finite X ⊆ A there is a smallest Y ≤ A with X ⊆ Y, and moreover this is finitely generated. To see this, note that by C3 in A, we may assume that A itself is finitely generated. It is then clear that {a ∈ A : a^{⇒} \ X^{⇒} is finite } ≤ A and this is finitely generated. Thus, this is equal to Y. We denote this by cl_{A}(X). Note that X^{⇒} is cofinite in this.

Lemma 2.6 (Amalgamation) Suppose A, B_{1}, B_{2} ∈ C and A ≤^{+} B_{i}. Let C be the disjoint union of B_{1} and B_{2} over A. Then C ∈ C and B_{i} ≤^{+} C.

Proof. Note that for any c ∈ C, if c ∈ B_{i} then c^{⇒} ⊆ B_{i}. Thus C satisfies C1. We show B_{i} ≤^{+} C, and then C2 follows. Note that if c ∈ B_{2} then c^{⇒} ∩ B_{1} = c^{⇒} ∩ A. So c^{⇒} ∩ B_{1} is f.g., and if it is cofinite in c^{⇒}, then c ∈ A, as A ≤^{+} B_{2}. It follows that B_{1} ≤^{+} C, as required.

For C3 let X be a finite subset of C and X_{i} = X ∩ B_{i}. As A ≤^{+} B_{i} we have that A_{i} = X\overrightarrow{i} ∩ A is finitely generated. In the notation of Remark 2.5(iii), let A^{0} = cl_{A}(A_{1} ∪ A_{2}). Let X^{i} = cl_{B_{i}}(A^{0} ∪ X_{i}). Note that these are finitely generated. Claim 1: X^{i} ∩ A = A^{0}. By Remark 2.5(iii) it is enough to show that if a ∈ A and a^{⇒} \ (A^{0} ∪ X\overrightarrow{i}) is finite, then a ∈ A^{0}. But this is immediate, as X\overrightarrow{i} ∩ A ⊆ A^{0} and A^{0} ≤ A. Claim 2: X^{1} ∪ X^{2} ≤ C. Let c ∈ C be such that c^{⇒} \ (X^{1} ∪ X^{2}) is finite. Without loss of generality, c ∈ B_{1}. We show c ∈ X^{1}. Now,

c^{⇒} ∩ (X^{1} ∪ X^{2}) = (c^{⇒} ∩ X^{1}) ∪ (c^{⇒} ∩ X^{2}).

By Claim 1,

c^{⇒} ∩ X^{2} = c^{⇒} ∩ A ∩ X^{2} = c^{⇒} ∩ A^{0}.

Thus c^{⇒} ∩ (X^{1} ∪ X^{2}) = c^{⇒} ∩ X^{1}. This is supposed to be cofinite in c^{⇒}, so as X^{1} ≤ B_{1} we have c ∈ X^{1}, as required. This completes the verification of C3. □

Corollary 2.7 The category C has direct limits and the amalgamation property.

Proof. This is now very easy. □

Definition 2.8 Let M ∈ C. A partial automorphism of M is an isomorphism ϕ : A → B where A, B ≤^{+} M. If A (and B) is f.g. then (for want of better terminology) refer to this as a finite partial automorphism.

Theorem 2.9 (a) For every cardinal μ there exists a digraph M ∈ C with in-valency at least μ and satisfying the following:

(1) For every f.g. A ≤^{+} M and embedding ϕ : A → B in C with B f.g., there exists an embedding ψ : B → M with ψ ∘ ϕ = id_{A}.

(2) Any finite partial automorphism of M can be extended to an automorphism of M.

(b) With M as in (a), Aut(M) is highly arc transitive and primitive on M.

Corollary 2.10 For every infinite cardinal κ there exists a primitive permutation group (G, D) which has a finite suborbit paired with a suborbit of size κ.

Proof of the Theorem. (a) This is fairly routine, but we give a few details. The main point is to prove the following:

Lemma 2.11 Let L ∈ C and suppose Φ = (φ_{i} : i ∈ I) is a family of partial automorphisms of L. Then there exists N ∈ C with L ≤^{+} N and φ̄_{i} ∈ Aut(N), for all i ∈ I, with φ_{i} ⊆ φ̄_{i}.

Once we have this, take M_{1} ∈ C of in-valency at least μ and such that all finitely generated A ∈ C embed into M_{1}. Now construct M_{1} ≤^{+} M_{2} ≤^{+} ⋯, where M_{i+1} is obtained from M_{i} by applying the lemma with L = M_{i} and Φ all partial automorphisms of M_{i} (it is possible to be more economical). Let M be the direct limit ⋃_{i<ω} M_{i}. Then (2) holds, and (1) follows.

To prove the lemma, it is enough to deal with a single partial automorphism φ (for the general case, we build N as a direct limit N = ⋃_{j<β} N_{j}; at stage j we replace a single partial automorphism φ_{i} by an automorphism of N_{j+1}, and for each i ∈ I the set of stages j at which φ_{i} is replaced is unbounded in β). We construct L = L_{0} ≤^{+} L_{1} ≤^{+} L_{2} ≤^{+} ⋯ in C and partial automorphisms θ_{i} of L_{i} such that θ_{0} = φ, θ_{i} ⊆ θ_{i+1}, L_{i} ⊆ im(θ_{i+1}) ∩ dom(θ_{i+1}). Letting N = ⋃_{i<ω} L_{i} and φ̄ = ⋃_{i<ω} θ_{i} gives what we require.

Suppose L_{i} and θ_{i} have been constructed. Let A = dom(θ_{i}) and B = im(θ_{i}). There is L′ ∈ C with B ≤^{+} L′ and an isomorphism ψ : L_{i} → L′ such that θ_{i}(a) = ψ(a) for all a ∈ A. Amalgamate L_{i} and L′ over B, using Lemma 2.6, and let L_{i+1} be the resulting structure. Then θ_{i+1} = ψ is a partial automorphism of L_{i+1} which has L_{i} in its domain and extends θ_{i}. We can similarly arrange that L_{i} is in the image of θ_{i+1} (repeat the process with θ_{i+1}^{−1} and adjust the notation).

(b) Note that the high arc transitivity follows from property (2) in (a) and C1,C2 in M. To show that Aut(M) is primitive on M, we show that all orbital graphs are connected. This is similar to the proof of ([3], Lemma 2.7), with some simplifications suggested by Peter M. Neumann. We already know that Aut(M) is transitive on M. To show that it is primitive, we prove that if a ≠ b then the orbital graph Σ with vertices M and edges {{ga, gb} : g ∈ Aut(M)} is connected. Note that as M itself is connected, it is enough to show that if x, y ∈ M are such that (x, y) is an edge of M, then x, y lie in the same connected component of Σ. By vertex transitivity, we may assume that x = a. Let C_{1} = cl_{M}(a, b). Thus C_{1} ≤^{+} M and C_{1} is finitely generated. Case 1: a^{⇒} ∩ b^{⇒} = ∅.

Amalgamate C_{1} with a copy C_{2} of C_{1}, identifying b^{⇒} with y^{⇒}. Let a′ be the copy of a in C_{2}. So we have a digraph with a^{′⇒} ∩ b^{⇒} = ∅. Adjoining new vertices we obtain a digraph in which the closure C_{3} of a′, b is isomorphic to C_{1}. Let E be the resulting graph. So E is the union of C_{1}, C_{2}, C_{3}, and C_{1} ∩ C_{3} = b^{⇒}, C_{3} ∩ C_{2} = a^{′⇒} and C_{2} ∩ C_{1} = y^{⇒}. Moreover any edge is contained entirely in some C_{i}. We claim that E ∈ C. Once we have this it follows (from properties (1) and (2) of M) that x, y are at distance at most 3 in the orbital graph Σ.

Clearly C1 holds for E as e^{⇒} is contained in some C_{i}, for every e ∈ E. For C2, let e, f ∈ E. Then e^{⇒} ∪ f^{⇒} ⊆ C_{i} ∪ C_{j} for some i, j, and by the amalgamation lemma this is in C. So e^{⇒} ∩ f^{⇒} is finitely generated, and if f^{⇒} \ e^{⇒} is finite, then f ∈ e^{⇒}. Thus C2 holds. As E is f.g., there is nothing to prove for C3. Case 2: b ∈ a^{⇒}.

Let b_{0} be the predecessor of b in a^{⇒} (that is, (b_{0}, b) is an edge in M), and let b_{1} ∈ a^{⇒} be its other successor. There is an automorphism of M which fixes a and interchanges b and b_{1}. Thus b_{1} and b are connected in the orbital graph Σ. As b^{⇒} ∩ b\overrightarrow{1} = ∅, Case 1 implies that the orbital graph having {b, b_{1}} as an edge is connected. Thus Σ is connected also. Case 3: b^{⇒} \ a^{⇒} and a^{⇒} \ b^{⇒} are infinite.

Let x_{1}, …, x_{r} be a minimal generating set for a^{⇒} ∩ b^{⇒} (so x\overrightarrow{i} ∩ x\overrightarrow{j} = ∅ for i ≠ j), and let z_{i} be the predecessor of x_{i} in a^{⇒} and y_{i} its other successor in a^{⇒} (for i = 1, …, r). Note that {x_{1}, …, x_{r}} and {y_{1}, …, y_{r}} are disjoint. By properties (1) and (2) of M, there is an automorphism g of M fixing a and interchanging each x_{i} and y_{i}, and such that gb^{⇒} ∩ b^{⇒} = ∅. Now b and gb are connected in Σ, and by Case 1, the orbital graph having {b, gb} as an edge is connected. So Σ is connected. □

Proof of the Corollary. Take μ ≥ κ and M as in Theorem 2.9. Let (Ω_{i} : i ∈ I) be the (non-trivial) orbital digraphs for Aut(M) on M. Let D_{0} be a subdigraph of M of cardinality κ and in-valency κ, with D\overrightarrow{0} = D_{0}. Let G_{0} = \{1\}. We build D as a union of a chain of subgraphs D = ⋃_{i<ω} D_{i} and construct a chain of subgroups G_{i} of Aut(M).

To construct D_{i+1} and G_{i+1} from D_{i} and G_{i}, do the following:

(1) Increase D_{i} to D′_{i} so that if x, y ∈ D_{i} and (x, y) ∈ Ω_{j} then Ω_{j}|D′_{i} (the restriction of Ω_{j} to D′_{i}) is connected.

(2) If (x, y), (x′, y′) ∈ (D′_{i})^{2} lie in the same Aut(M)-orbit then include g ∈ G_{i+1} such that g(x, y) = (x′, y′).

(3) Increase D′_{i} to D_{i+1} so that gD_{i+1} = D_{i+1} for all g ∈ G_{i+1}. Note that we can do all this and keep |D_{i}|, |G_{i}| ≤ κ for all i < ω. Let G^{0} = ⋃_{i<ω} G_{i}. Then D = ⋃_{i<ω} D_{i} is invariant under G^{0}. Let G be the restriction of G^{0} to D. By construction, all orbital graphs of G on D are restrictions of the Ω_{j} to D, and are connected. Thus G is primitive on D. But also G is transitive on directed edges of D, so D is an orbital digraph. As it has out-valency 2 and in-valency κ, it satisfies our requirements. □

Remark 2.12 The construction can be done more economically in the countable case, and in fact, a similar simplification can be made in the general case if we assume the existence of a strongly inaccessible cardinal at least as large as κ.

Theorem 2.13 There is a countable M ∈ C such that for all f.g. A, B ∈ C and embeddings α : A → M, ϕ : A → B, there exists an embedding ψ : B → M with ψ ∘ ϕ = α. Such an M is unique and any finite partial isomorphism of M extends to an automorphism of M.

It is easy to see that M in the above has infinite in-valency, and by the previous results Aut(M) is primitive and highly arc transitive. The theorem follows from the amalgamation lemma (but we only need this for f.g. elements of C, and it is rather easier in this case as clause C3 becomes redundant), and the following, which shows that we only have to amalgamate a countable number of embeddings to achieve the required property of M:

Lemma 2.14 (1) There are countably many isomorphism types of f.g. digraph in C.

(2) Given f.g. A, B ∈ C there are (up to equivalence) only countably many embeddings ϕ : A → B.

Proof. (1) If C ∈ C is f.g. then we can write C = c\overrightarrow{1} ∪ … ∪ c\overrightarrow{n} for some natural number n. We show by induction on n that the number of isomorphism types of such n-generator digraphs in C is countable. Let C_{1} = c\overrightarrow{1} ∪ … ∪ c\overrightarrow{n−1}. Then, in the notation of ([3], 2.2 and 2.3), for some finite tuples x̄, ȳ of (independent) elements in C_{1} and T we have that C ≅ (C_{1}, x̄) ∗ (T, ȳ). As there are only countably many possibilities for x̄, ȳ we have the inductive step.

(2) We call embeddings ϕ : A → B and χ : A → B′ equivalent if there exists an isomorphism θ : B → B′ with θ ∘ ϕ = χ. We prove by induction on n, the number of generators of A, that up to equivalence there are only countably many embeddings ϕ : A → B, for fixed B. Write A = A_{1} ∪ a\overrightarrow{n}, where A_{1} can be generated by n − 1 elements. Regard ϕ|A_{1} and ϕ(a_{n}) = b as fixed. Then for some natural number k, any automorphism of b^{⇒} which fixes all vertices at out-distance at most k from b can be extended to an automorphism of B which fixes every element of ϕ(A_{1}) (as B is f.g.). Thus, there are now only finitely many possibilities for ϕ, up to equivalence. □

References

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

[2] Peter J. Cameron, Oligomorphic Permutation Groups, London Math. Soc. Lecture Notes Series, 152, Cambridge University Press, Cambridge, 1990.

[3] David M. Evans, ‘An infinite highly arc-transitive digraph’, Europ. J. Combinatorics, 18 (1997), 281–286.

[4] David M. Evans, ‘Examples of ℵ_{0}-categorical structures’, in Automorphisms of First-Order Structures, eds. Richard Kaye and Dugald Macpherson, Oxford University Press, Oxford, 1994, 33–72.

[5] R. Fraïssé, ‘Sur certaines relations qui généralisent l’ordre des nombres rationels’, Comptes Rendus de l’Académie des Sciences de Paris, 237 (1953), 540–542.

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

[7] D. W. Kueker and C. Laskowski, ‘On generic structures’, Notre Dame J. Formal Logic, 33 (1992), 175–183.

[8] Peter M. Neumann, Postscript to Review of [2], Bull. London Math. Soc., 24 (1992), 404–407.

[9] C. E. Praeger, ‘On homomorphic images of edge-transitive digraphs’, Austral. J. Combinatorics, 3 (1991), 207–210.

[10] G. Schlichting, ‘Operationen mit periodischen Stabilisatoren’, Arch. Math. (Basel), 34 (1980), 97–99.

[11] V. I. Trofimov, ‘Groups of automorphisms of graphs as topological groups’, Math. Notes, 38 (1985), 717–720.