Basic Results on Imprimitive Groups

E. Dobson: Imprimitive Permutation Groups 23

2.1 Introduction

The O’Nan-Scott Theorem together with the Classification of the Finite Simple Groups is a powerful tool that give the structure of all primitive permutation groups, as well as their actions. This has allowed for the solution to many classical problems, and has opened the door to a deeper understanding of imprimitive permutation groups, as primitive per-mutation groups are the building blocks of imprimitive perper-mutation groups. We first give a more or less standard introduction to imprimitive groups, and then move to less well-known techniques, with an emphasis on studying automorphism groups of graphs.

A few words about these lecture notes. The lecture notes are an “expanded" version of the lecture - some of the lecture will be basically exactly these lecture notes, but in many cases the proofs of some background results (typically those that in my view are those whose proofs are primarily checking certain computations) are given in these lecture notes but will not be given in the lectures due to time constraints. Also, the material is organized into sections by topic, not by lecture.

24 2.2 Basic Results on Imprimitive Groups

Example 2.2.4 Defineρ,τ:2×5→2×5byρ(i,j) = (i,j+1)andτ(i,j) = (i+1, 2j).

Note that in these formulas, arithmetic is performed modulo 2 in the first coordinate and modulo 5 in the second coordinate. It is straightforward but tedious to check that〈ρ,τ〉

is a subgroup of the automorphism group of the Petersen graph with the labeling shown in Figure 2.1.

•(1, 0) (1, 4)•

(1, 3)•

(1, 2)• (•1, 1) (0, 0)•

(0, 4)•

(0, 3)• •

(0, 2)

•(0, 1)

Figure 2.1: The Petersen graph.

Additionally,τ⁻¹(i,j) = (i−1, 3j)as

τ⁻¹τ(i,j) =τ⁻¹(i+1, 2j) = (i+1−1, 3(2j)) = (i,j).

Also,

τ⁻¹ρτ(i,j) =τ⁻¹ρ(i+1, 2j) =τ⁻¹(i+1, 2j+1) = (i+1−1, 3(2j+1)) = (i,j+3) =ρ³(i,j) and so〈ρ〉〈ρ,τ〉. Then by Theorem 2.2.3 the orbits of〈ρ〉, which are the sets{{i,j}:j∈ 5}:i∈2}form a complete block system of〈ρ,τ〉.

Although we will not show this here, the full automorphism group of the Petersen graph is primitive.

A complete block system ofGformed by the orbits of normal subgroup ofGis called anormal complete block system ofG. Note that not every complete block systemof every transitive groupG is a complete block system ofG, as we shall see.

Now suppose thatG≤ nis a transitive group which admits a complete block system consistingmblocks of sizek. ThenGhas aninduced action on, which we denote byG/. Namely, for specificg ∈G, we defineg/(B) =B if and only ifg(B) = B, and setG/={g/:g∈G}. We also define thefixer ofinG, denoted fix_G(), to be{g ∈G :g/=1}. That is, fixG()is the subgroup ofG which fixes each block of set-wise. Furthermore, fixG()is the kernel of the induced homomorphismG→S, and as such is normal inG. Additionally,|G|=|G/| · |fixG()|.

A transitive groupGisregularif StabG(x) =1 for any (and so all)x.

E. Dobson: Imprimitive Permutation Groups 25

Theorem 2.2.5 Let G ≤ nbe transitive with an abelian regular subgroup H . Then any complete block system of G is normal, and is formed by the orbits of a subgroup of H . PROOF. We only need show that fixH()has orbits of size|B|,B ∈ . Now,H/ is transitive and abelian, and soH/ is regular (a transitive abelian group is regular as conjugation permutes the stabilizers of points - so in a transitive abelian group, point stabilizers are all equal). ThenH/ has degree||, and so there exists nontrivialK ≤ fix_H()of order|B|. Then the orbits of K form a complete block system ofH by Theorem 2.2.3, and each block ofis contained in a block of. AsKhas order|B|, we

conclude that=.

Lemma 2.2.6 Let G act transitively on X , and let x∈X . Let H≤G be such thatStab_G(x)≤ H . Then the orbit of H that contains x is a block of G .

PROOF. SetB={h(x):h∈H}(so thatB is the orbit ofHthat containsx), and letg∈G. We must show thatB is a block ofG, or equivalently, thatg(B) =B org(B)∩B =. Clearly ifg∈H, theng(B) =BasBis the orbit ofHthat containsxandx∈B. Ifg∈H, then towards a contradiction suppose thatg(B)∩B=, with sayz∈g(B)∩B. Then there existsy∈Bsuch thatg(y) =zandh,k∈Hsuch thath(x) =yandk(x) =z. Then

z=g(y) =g h(x) =k(x) =z,

and sog h(x) =k(x). Thusk⁻¹g h∈Stab_G(x). This then implies thatg ∈k·Stab_G(x)· h⁻¹≤H, a contradiction. Thus ifg∈H, theng(B)∩B=, andBis a block ofG.

Example 2.2.7 Consider the subgroup of the automorphism group of the Petersen graph

〈ρ τ〉that we saw before. Straightforward computations will show that|τ|=4, and so

|〈ρ,τ〉|=20 as|ρ|=5. By the Orbit-Stabilizer Theorem, we have that Stab_〈ρ,τ〉(0, 0)has order 2, and asτ²stabilizes(0, 0), Stab〈ρ,τ〉(0, 0) =〈τ²〉. Then〈τ〉 ≤ 〈ρ,τ〉and contains Stab_〈ρ,τ〉(0, 0). Then the orbit of〈τ〉that contains(0, 0)is a block of〈ρ,τ〉as well. This orbit is{(0, 0),(1, 0)}. So the corresponding complete block system of〈ρ,τ〉consists of the vertices of the “spoke" edges of the Petersen graph.

Just as we may examine the stabilizer of a point in a transitive groupG, we may also examine thestabilizer of the blockBin an imprimitive groupG. It is denoted StabG(B), is a subgroup ofG, and Stab_G(B) ={g∈G:g(B) =B}.

Theorem 2.2.8 Let G act transitively on X , and let x∈X . LetΩbe the set of all blocks B of G which contain x , and S be the set of all subgroups H≤G that containStab_G(x). Define φ:Ω→S byφ(B) =StabG(B). Thenφis a bijection, and if B,C∈Ω, then B⊆C if and only ifStabG(B)≤StabG(C).

PROOF. First observe that Stab_G(x) ≤Stab_G(B)for every blockB withx ∈ B, soφ is indeed a map fromΩtoS. We first show thatφis onto. LetH∈Sso that Stab_G(x)≤H. By Lemma 2.2.6,B={h(x):h∈H}is a block ofG. ThenH≤φ(B). Towards a contradiction, suppose there existsg∈φ(B)such thatg∈H. Theng(B) =B, andHis transitive in its action onB (Exercise 2.2.12). Hence there existsh∈H such thath(x) =g(x), and so

26 2.2 Basic Results on Imprimitive Groups

h⁻¹g(x) =x∈Stab_G(x)≤H. Thush⁻¹g∈H sog∈H, a contradiction. Thusφ(B) =H andφis onto.

We now show thatφ is one-to-one. Suppose B,C ∈ Ωandφ(B) =φ(C). Then Stab_G(B) =Stab_G(C). Towards a contradiction, suppose thaty∈Bbuty∈C. As Stab_G(B) is transitive onB, there existsh∈Stab_G(B)such thath(x) =y. But thenh∈Stab_G(C) = StabG(B)and soy is in the orbit of StabG(C)that containsx, which isC, a contradiction.

Thusφis one-to-one and onto, and so a bijection.

Finally, it remains to show that if B,C ∈Ω, then B ⊆C if and only if StabG(B) ≤ Stab_G(C). First suppose that Stab_G(B)≤Stab_G(C). Then the orbit of Stab_G(C)that con-tainsxcertainly contains the orbit of Stab_G(B)that containsx, and soB⊆C. Conversely, suppose thatB⊆C. Letg∈Stab_G(B). Theng(x)∈B⊆C, and sox∈C∩g(C). AsCis a block ofG, we have thatg(C) =Cso thatg∈Stab_G(C). Thus StabG(B)≤Stab_G(C).

Theorem 2.2.9 Let G be a transitive group acting on X . If≡is an equivalence relation on X such that x≡y if and only if g(x)≡g(y)for all g ∈G (a G-congruence), then the equivalence classes of≡form a complete block system of G .

PROOF. LetBxbe an equivalence class of≡that containsx, andx∈X,g∈G. Then

g(B_x) = {g(y):y ∈Xandx≡y}

= {g(y):g(y)≡g(x)}

= B_g(x).

As the equivalence classes of≡form a partition ofX, it follows thatg(Bx)∩B_x=orB_x, and soBx is a block ofG. Also, asg(Bx) =Bg(x), the set of all blocks conjugate toBx is

just the set of equivalence classes of≡.

A common application of the above result is to stabilizers of points, as in a transitive group, any two point stabilizers are conjugate (Exercise ?.?).

Exercise 2.2.10 Verify that if B is a block of G , then g(B)is also a block of G for every g∈G .

Exercise 2.2.11 Verify that ifis a complete block system of G acting on X , thenis a partition of X .

Exercise 2.2.12 Let G act transitively on X , and suppose that B is a block of G . Then Stab_G(B)is transitive on B .

Exercise 2.2.13 Show that a transitive group of prime degree is primitive.

Exercise 2.2.14 Let G≤ nwitha complete block system of G . Ifφ∈ n, thenφ()is aφGφ⁻¹-invariant partition.

Exercise 2.2.15 A group G acting on X isdoubly-transitiveif whenever(x1,y1),(x2,y2)∈ X×X such that x1=y1and x2=y2, then there exists g∈G such that g(x1,y1) = (x2,y2).

Show that a doubly-transitive group is primitive.

E. Dobson: Imprimitive Permutation Groups 27

Exercise 2.2.16 Let G ≤ n contain a regular cyclic subgroup R =〈(0 1 . . . n−1)and admit a complete block systemconsisting of m blocks of size k . Show thatconsists of cosets of the unique subgroup ofnof order k .

Exercise 2.2.17 Let p and q be distinct primes such that q divides p−1. Determine the number of complete block systems of G_Lwhere G is the nonabelian group of order pq that consist of blocks of cardinality q and of cardinality p .

Exercise 2.2.18 Let G be a transitive group of square-free degree (an integer that is square-freeis not divisible by the square of any prime). Show that G has at most one normal G -invariant partition with blocks of prime size p . (Hint: Suppose there are at least two such G -invariant partitions1and2. Consider what happens tofix_G(2)in G/1.) Exercise 2.2.19 Let G≤ nbe transitive. Show that G is primitive if and only ifStab_G(x) is a maximal subgroup of G for every x∈n.