Chapter 1
Primitive and quasiprimitive groups

Blocks and invariant partitions

We start with an example. Let G be the circular graph of degree n and D_2n = Aut(G) the dihedral group of order 2n. Recall that D_2n is generated by two elements a and b, where

a = (1,2,3,¼,n)   and    b = ën/2û Õ i = 1  (i,n-i+1)

(ën/2û denotes the largest integer that is not greater than n/2). If k is a divisor of n, and m = n/k then the vertex set of G can be partitioned into m subset each of size k as follows:

p1 = {1,m+1,¼,(k-1)m+1} p2 = {2,m+2,¼,(k-1)m+2,} : pm = {m,2m,¼,km}.

That is a belongs p_i if and only if a º i mod m. Then it is easy to see that the image of each p_i under any element g Î D_2n is some p_j. Thus the permutation group D_2n permutes the parts p₁,¼,p_m.

This motivates the following discussion.

Definition 1 Let G be a transitive permutation group on a set W and D Í W, such that D is non-empty. Then D is said to be a block for G if for all g Î G either D^g = D or DÇD^g = Æ.

The following easy lemma shows how we can obtain a partition of W from a block.

Lemma 2 Let G be a transitive permutation group on W and D Í W a block. Then

(i) È_{g Î G}D^g = W;
(ii) for all g₁, g₂ Î G we have that either D^g₁ = D^g₂ or D^g₁ÇD^g₂ = Æ.

PROOF. The proof of (i) is straightforward and is left to the reader. For (ii) suppose that g₁, g₂ Î G and w Î D^g₁ÇD^g₂. Then

wg1-1 Î Dg1g1-1ÇDg2g1-1 = DÇDg2g1-1.

As D is a block, we obtain that D = D^g₂g₁-1, and hence D^g₁ = D^g₂. ^[¯]

Exercise 3 Let G = D₁₂ = < (1,2,3,4,5,6),(1,6)(2,5)(3,4) > . Find all blocks for G containing the element 1.

Exercise 4 Let the additive group of the integers Z act on itself by right translation. That is for w,  Î Z define w^z = w+z. Show that if D is a block containing 1 then D is a subgroup of Z.

Exercise 5 Let G be a group and consider its right-regular representation. Can you describe all blocks for G containing the identity element? Can you describe all blocks for G?

Suppose that G and D are as in the previous lemma and let g₁,¼,g_k be elements of G such that D^g₁,¼,D^g_k is a list of all different images of D. That is D^g_i ¹ D^g_j if i ¹ j and

{Dg | g Î G} = {Dg1,¼,Dgk}.

Then by the previous lemma

W = Dg1 · È   ¼ · È   Dgk,

where [ · || (È)] denotes taking disjoint union of two sets. In other words the set

¶ = {Dg1,¼,Dgk}

is a partition of W and ¶ is invariant under the action of G. Such a partition is said to be a G-invariant partition. In other words, each block gives rise to a G-invariant partition of W. It is similarly easy to see that an element of a G-invariant partition is a block for G.

Blocks and subgroups

If G is a transitive group of W and ¶ is a G-invariant partition of W, then G acts transitively on ¶. This trivial fact is so important that it is worth noting in a lemma.

Lemma 6 Let G be a transitive permutation group and ¶ a G-invariant partition of W. Then G acts on ¶ and this action is transitive. In particular, each element of ¶ has the same size.

PROOF. Exercise ^[¯]

Note that in the previous lemma the G-action on ¶ is, in general, not faithful. The permutation group G^P induced by G is in general smaller than G and has smaller degree.

Recall that if G is a permutation group on W and G Í W then G_G denotes the setwise stabiliser of G, that is

GG = {g Î G | Gg = G} = {g Î G | gg Î G for all g Î G}.

Lemma 7 Let G be transitive permutation group on W and D a block for G. Then G_D is transitive on D and G_d £ G_D for all d Î D.

PROOF. Let d₁, d₂ Î D. Since G is transitive on W, there exists g Î G, such that d₁^g = d₂. Since d₂ Î DÇD^g and D is a block, we have that D = D^g, therefore g Î G_D. This shows that G_D is transitive on D.

If d Î D and g Î G_d, then d = d^g Î DÇD^g. As D is a block we have that D^g = D and hence g Î G_D. Thus G_d £ G_D. ^[¯]

Lemma 8 Let G be a transitive permutation group acting on W and w Î W a fixed element. Let H be a subgroup of G, such that G_w £ H. Then the orbit w^H of w under H is a block for G.

PROOF. Let D denote w^H and let g Î G, and w¢ Î W such that w¢ Î DÇD^g. Then, as w¢ Î D, there is some h₁ Î H, such that w¢ = w^h₁. Since w¢ = D^g we also have that there is some h₂ Î H, such that w¢ = w^h₂g. Then w^{h₁g-1h₂-1} = w, and so h₁g^-1h₂^-1 Î G_w. Set g¢ = h₁g^-1h₂^-1; note that g¢ Î G_w. Then g = h₁^-1g¢h₂, and since h₁, h₂ Î H and g¢ Î G_w £ H we have that g Î H. As D is invariant under H, we have D^g = D as required. ^[¯]

Theorem 9 If G is a transitive permutation group on W and w is a fixed element of W then the correspondence H®w^H is a bijection between the set of subgroups containing G_w and the set of blocks containing w. Moreover for any two such subgroups H₁ and H₂, we have that w^H₁ Í w^H₂ if and only if H₁ £ H₂.

PROOF. Let j denote the map H®w^H. If D is a block then G_D is transitive on D and G_w £ G_D (see Lemma 0.2). Thus D = w^G_D = j(G_D), and so j is surjective. Let H₁ and H₂ be subgroups of G, such that G_w £ H₁ÇH₂, and w^H₁ = w^H₂. Let h₁ Î H₁. As w^h₁ Î w^H₁ and w^H₁ = w^H₂ it follows that there exists h₂ Î H₂, such that w^h₁ = w^h₂. Then g = h₁h₂^-1 Î G_w, and so h₁ = gh₂. Since G_w £ H₂ we have that h₁ = gh₂ Î H₂. This shows that H₁ £ H₂, and similar argument shows that H₂ £ H₁. Thus H₁ = H₂ and hence j is injective.

The proof of the last statement is left as an exercise. ^[¯]

Primitive and quasiprimitive groups

If w Î W then the singleton {w} is a block and it gives rise to the partition {{w} | w Î W} of W. Similarly W is also a block, and the corresponding partition is {W}. These blocks are called trivial blocks.

Definition 10 A transitive permutation group is said to be primitive if it only has trivial blocks. Otherwise it is said to be imprimitive.

If G is a transitive permutation group and D is a non-trivial block then D is also called a block of imprimitivity for G. The corresponding G-invariant partition {D^g | g Î G} of W is referred to as a system of imprimitivity for G.

In a group G a subgroup H is said to be maximal if H is not contained in any proper subgroup of G. In other words, if K £ G, such that H < K then K = G.

Corollary 11 A transitive permutation group is primitive if and only if a point stabiliser is a maximal subgroup.

PROOF. This immediately follows from Theorem 0.2. Details are left as an exercise. ^[¯]

Exercise 12 Recall that a permutation group G on W is said to be 2-transitive if for all a₁, a₂, b₁, b₂ Î W, such that a₁ ¹ a₂ and b₁ ¹ b₂ there exists some g Î G, such that a₁^g = b₁ and a₂^g = b₂. Prove that any 2-transitive group is primitive.

Exercise 13 Show that the action of S₅ on the vertices of the Petersen graph is primitive.

Theorem 14 Let G be a transitive permutation group on W and N a normal subgroup of G. Then the orbits of N on W form a G-invariant partition of W. In particular, each such orbit is a block for G.

PROOF. We already know that the N-orbits form a partition of W, so we only have to prove that this partition is G-invariant. Let D be an N-orbit and choose w Î D. As D is an N-orbit, we have that D = w^N. If g Î G, then, as N is a normal subgroup, Ng = gN and we obtain that

Dg = {wng | n Î N} = {wgn | n Î N} = (wg)N.

That is D^g is the N-orbit containing w^g, and so the set of N-orbits is G-invariant. We noted earlier that the elements of a G-invariant partition are blocks. ^[¯]

Definition 15 A permutation group is said to be quasiprimitive if all its non-trivial subgroups are transitive.

Corollary 16 A primitive permutation group is quasiprimitive.

PROOF. This follows immediately from Theorem 0.2. ^[¯]

Exercise 17 Not all quasiprimitive groups are primitive. Can you show an example of a quasiprimitive group that is not primitive.

Graphs and primitive groups

The following important result is due to Charles Sims.

Theorem 18 [Sims] Let G be a transitive permutation group on W. Then G is primitive if and only if each orbital di-graph corresponding to a G-orbital on W is connected.

PROOF. Suppose first that G is primitive and let G = (W,E) be an orbital di-graph corresponding to the G-orbital E on W. Let {D₁,¼,D_k} be the partition of W to the vertex sets of the connected components of G. That is, w₁, w₂ Î D_i for some i, if and only if there is a path from w₁ to w₂. We only have to show that this partition is G-invariant. Let D_i be a member of this partition, and a Î D_i. If b Î D_i^g then there is some a¢ Î D_i, such that b = a¢^g. As a¢ Î D_i, there is a path a₀ = a,a₁,¼,a_k = a¢ from a¢ to a¢. Taking the image of this path under the element g, we obtain a path from a^g to a¢^g = b. Thus D_i^g is contained in the connected component of a^g. Similar argument shows that the connected component of a^g is contained in D_i^g, therefore D_i^g is the connected component of a^g. Hence G permutes the connected components and {D₁,¼,D_k} is a G-invariant partition of W. As G is an orbital graph, each such a connected component has size at least two. The primitivity of G then implies that k = 1 and D₁ = W. Thus G is connected.

Suppose now that G is transitive on W and each orbital graph corresponding to a G-orbital on W is connected. Let {D₁,¼,D_k} be a G-invariant partition of W, such that the size of D₁ (and hence that of each D_i) is at least two. Let a, b Î D₁, and let E = (a,b)^G be the orbit of (a,b) under the action of G on W×W. Then E is a G-orbital. Let (g,d) Î E, such that g Î D₁. Then, as G is transitive on E there is an element g Î G, such that (a,b)^g = (g,d), that is a^g = g and b^g = d. Now g = a^g Î D₁ÇD₁^g, and, since D₁ is a block, we have that D₁^g = D₁. As b Î D₁, this implies that b^g = d Î D₁. Thus if the initial vertex of an arc is in D₁ then so is its terminal vertex. Similar argument shows that the previous sentence remains true after interchanging the words initial and terminal. Hence D₁ contains the vertices of a connected component of G. By assumption, G is connected and hence D₁ = W and so G is primitive. ^[¯]

A glimpse of what's beyond

A structure theorem, usually referred to as the O'Nan-Scott Theorem, of primitive permutation groups was proved in the 1980's. Besides M. O'Nan and L. Scott, many mathematicians contributed to an appropriate formulation and proof of this result. They include, among others, P. Cameron, L. Kovács, M. Liebeck, J. Saxl, C. Praeger. This theorem divides primitive permutation groups into several classes and gives detailed information about the structure of the group and properties of its action in each class. A similar theorem for quasiprimitive groups was proved by C. Praeger in 1993. The discussion of these two theorems is beyond the scope of this course, because it involves constructions, such as wreath product, twisted wreath product. However, in the the following exercises you can taste the flavour of the more involved theory of primitive and quasiprimitive groups. Be warned that these exercises might be a bit more challenging than the previous ones.

Let G be a group and N a normal subgroup of G. Then N is said to be a minimal normal subgroup if N does not contain any non-trivial normal subgroup of G. In other words, if M is a normal subgroup of G, such that M < N then M = 1.

Exercise 19 Show that if N₁ and N₂ are two minimal normal subgroup of G, then either N₁ = N₂ or N₁ÇN₂ = 1. Deduce that in the latter case N₁ and N₂ centralise each other. That is n₁n₂ = n₂n₁ for all n₁ Î N₁ and n₂ Î N₂.

Exercise 20 Prove that in a group a minimal normal subgroup N is a direct product of isomorphic simple groups. (This might be a bit difficult. However, most group theory textbooks will have such a result; consult one.) In particular, if N is abelian then there is some prime p, such that N @ C_p×¼×C_p, where C_p is the cyclic group of order p.

Exercise 21 Let p be a prime and F_p be the field of p elements and V an finite-dimensional vector space over F_p. Let [`V] be the image of the right-regular representation of V. That is [`V] = {[`v] | v Î V} where for each v Î V, the permutation [`v] is defined as

w[`v] = w+v   for all    w Î V.

Let GL(V) denote the group of linear transformations of V.

(i) Show that < [`V],GL(V) > = [`V]GL(V) = [`V]\rtimes GL(V). The group [`V]\rtimes GL(V) is called the affine linear group and is denoted by AGL(n,p).
(ii) Show that AGL(n,p) is 2-transitive, and hence primitive, on V.
(iii) Show that [`V] is the unique minimal normal subgroup of AGL(n,p).
(iv) Let G be a subgroup of GL(V). The G is said to be irreducible if {0} and V are the only G-invariant subspaces of G. Show that the following are equivalent:
1. G is irreducible;
2. [`V] is a minimal normal subgroup of [`V]\rtimesG;
3. [`V]\rtimes G is primitive on V;
4. [`V]\rtimes G is quasiprimitive on G.

Exercise 23 Let T be a finite simple group and Aut(T) its automorphism group. Let [`T] denote the image of the right regular representation of T.

(i) Show that < [`T],Aut(T) > = [`T]Aut(T) = [`T]\rtimesAut(T). The group [`T]\rtimesAut(T) is called the holomorph of T and is denoted by Hol T. Thus Hol T £ Sym T.
(ii) Prove that Hol T is primitive on T.
(iii) Let G be a subgroup of Aut(T). Then show that the following are equivalent:
1. Inn(T) £ G;
2. the only G-invariant subgroups of T are 1 and T;
3. [`T]\rtimes G is primitive on T;
4. [`T]\rtimes G is quasiprimitive on T.