Permutation Groups

By Donald S. Passman

This volume by a prominent authority on permutation groups consists of lecture notes that provide a self-contained account of distinct classification theorems. A ready source of frequently quoted but usually inaccessible theorems, it is ideally suited for professional group theorists as well as students with a solid background in modern algebra.
The three-part treatment begins with an introductory chapter and advances to an economical development of the tools of basic group theory, including group extensions, transfer theorems, and group representations and characters. The final chapter features thorough discussions of the work of Zassenhaus on Frobenius elements and sharply transitive groups in addition to an exploration of Huppert's findings on solvable doubly transitive groups.

• Language: English
• Publisher: Dover Publications
• Release date: Oct 3, 2013
• ISBN: 9780486310916

Donald S. Passman

Donald S. Passman practices law in Los Angeles, California and has specialized in the music business for over forty years, primarily representing artists. The Harvard Law grad is the author of All You Need to Know About the Music Business and has received numerous industry recognitions.   

Book preview

Index

CHAPTER I

Introduction

1. The Symmetric Group

All groups considered in this text, except possibly for those given by generators and relations, are assumed to be finite.

Let A be a finite set and let Sym(A), for the moment, denote the set of one-to-one functions from A onto A, that is the set of permutations of A. If a ∈ A and f ∈ Sym(A), then we denote by af the image of the element a. If f, g ∈ Sym(A), then we define the function fg by a(fg) = (af)g. It is easy to see that Sym(A), with this composition multiplication, forms a group, the symmetric group on set A.

Let A and B be two finite sets of the same size. Then there is an obvious isomorphism of Sym(A) with Sym(B) which commutes with the given one-to-one correspondence between the two sets. Specifically, if ρ: A → B is the latter one-to-one correspondence and if f ∈ Sym( A), then ρ−1f ρ ∈ Sym(B), and the map f ρ−1fρ from Sym(A) to Sym(B) is a group isomorphism. Thus it suffices to choose a fixed set of each finite size. Given integer n 1, if A = {1,2, …,n}, then we write Sym(n) for Sym(A). A permutation group is a subgroup of Sym(n). Here n is its degree.

Let f ∈ Sym(n), so that f is uniquely determined by the set of ordered pairs {(a, af) | a = 1, 2,… ,n}. We tilt these ordered pairs a quarter turn and write a above af. Moreover we place all these n expressions adjacent to each other and have

This correspondence is one-to-one provided we understand that the information contained in the symbol ( aaf ) is just the relationship of the first row to the second. Thus the ordering of the columns is unimportant. For example, with n = 3, we have

Using this fact, we can obtain an easy rule of multiplication.

Given f,g ∈ Sym(n) and let

We reorder the columns of (aaf ) until the top row looks like the bottom row of (aaf ). Then

and

Hence, if the columns of f and g are properly ordered, then multiplication essentially amounts to cancellation.

Now the symbol ( aaf ) is not typographically convenient, Moreover, it does not always show clearly the effect of the function. A more graphical notation is to write f as a product of cycles. Given f and choose any a ∈ {1, 2,…, n}. The cycle of f that starts with a is

where r is minimal with afr = a. Since Sym(n) is a finite group, such an integer r exists. By the minimality of r, it is easy to see that all elements in this cycle are distinct. We say that two cycles are the same if one can be obtained from the other by circularly shifting the elements. For example the cycles (1 2 3 4 5) and (3 4 5 1 2) are the same. With this convention, we see easily that any two cycles of f are either the same or disjoint, that is have no elements in common. We write the distinct cycles of f adjacent to each other on a line in any order, and we use this as an alternate notation for f. For example

It is obvious that this correspondence is one-to-one up to the order in which the cycles are written and the choice of the first element of each cycle.

As a short hand, we will drop all cycles of length one from this notation. Thus if (1 2 3) ∈ Sym(5), then this function fixes 4 and 5. Now consider the permutation

So far we have considered the expression (1 2 3)(4 5) as merely the juxtaposition of the cycles (1 2 3) and (4 5). However, with the short hand convention, (1 2 3) and (4 5) are permutations, and thus (1 2 3)(4 5) could mean the product of the two. A little thought will show that juxtaposition and multiplication yield the same result here. Hence we have shown that every permutation can be written as the product of disjoint cycles.

Consider a typical cycle (a1 a2 … ar) of length r. We see easily that this element has order r. Also

so that this cycle can be written as a product of r – 1 transpositions. Here, of course, a transposition is a cycle of length 2. We note also that two disjoint cycles commute with each other. Thus if

is a product of disjoint cycles, then using o(f) to denote the order of f, we have

and f transpositions. In particular, the set of transpositions generates Sym(n).

To each permutation f we associate a real number σ(f) as follows.

If

set

where the product is over all subsets {i, j} of size 2. Note that the product expression does not depend on the order of the columns and that the quotient (ai – aj)/(bi – bj) is in fact a function of the set {i, j}. Hence σ(f) is well defined. We use the cancellative form of permutation multiplication below. Write

so that

Hence σ is a homomorphism of Sym(n) into the multiplicative group of nonzero real numbers and we denote the kernel by Alt(n), the alternating group of degree n.

Let t be a transposition. We find σ(t). It suffices to assume that

In this form, it is easy to see that

Since Sym(n) is generated by transpositions, we see that σ(f) = +1 or −1 according to whether f can be written as a product of an even or odd number of transpositions. Obviously this parity is preserved no matter how we write f as a product of transpositions. Thus we speak of even and odd permutations. We see that Alt(n) is the set of all even permutations and that |Sym(n) : Alt(n)| = 2 when n 2.

2. Wreath Products

Let G be a permutation group on set A and let H be a permutation group on set B. We assume A and B are disjoint, |A| = α and |B| = β. It is easy to combine these to get a permutation group on A ∪ B. Let K = G × H, the direct product of G and H. Then every element of K is written uniquely as g × h with g ∈ G,h ∈ H. We define the action of K on A ∪ B by

We see easily that K ⊆ Sym(A∪B). Finally we note that |K| = |G|·|H| and deg K = deg G + deg H.

A more complicated situation is the Wreath product. Here, we take β copies of G and A, say G1, G2, …, Gβ, A1, A2, …, Aβ with Gi acting on Ai. Then as above we let G1 × G2 × … × Gβ act on A1 ∪ A2 ∪ … ∪ Aβ in the obvious manner. Finally, we let H act on A1, A2, …, Aβ by permuting the subscripts in the same way that H acts on B. We now describe this more precisely. Let B = {b1, b2, …, bβ} and set K = G H, the Wreath product of G and H, in that order. K is a subgroup of Sym(A × B) and each element of K is written uniquely as (g1 × g2 … × gβ; h where gi ∈ G, h ∈ H. We define the action of K on A × B by

It is easy to check that K is closed under function composition so that K is indeed a subgroup of Sym(A × B). We see easily that |K| = |G|β·|H| and deg K = (deg G)(deg H).

Note that, if we identify (A ∪ B) ∪ C = A ∪ (B ∪ C) and also (A × B) × C = A × (B × C), then products and Wreath products are associative operations.

Let p be a prime and let J be the cyclic subgroup of order p of Sym(p) generated by the cycle (1 2 … p). Thus J has order p and degree p. Then J J has degree p² and order p¹+p, J J J has degree p³ and order p¹+p+p² and in general

has degree pr and order p¹+p+…+pr−1. For convenience we will write this group as J r with J ⁰ = Sym(1). Let n be any integer and write

where 0 ≤ ai < p. Then by taking isomorphic copies of the above groups, so as to act on different sets, we see that

has degree a0 + a1p + a2p² + … + akpk = n and order |S| = pN where

Now |Sym(n)| = n! obviously. Let Sp be a Sylow p-subgroup of Sym(n) and suppose that |SP| = pM. Then pM is the p-part of nn/p numbers ≤ n that are divisible by pn/pare divisible by pn/pi are divisible by pi. This implies easily that

since a number pst ≤ n contributes s to the exponent M and also occurs in the first s sets whose sizes are the summands on the right hand side of the above. Using n = a0 + a1p + a2p² + … + akpk with 0 ≤ ai < p we obtain easily

and hence S is a Sylow p-subgroup of Sym(n). In this way, we have found the Sylow subgroups of the symmetric groups.

3. Multiple Transitivity

Let G be a permutation group on set A. If a, b ∈ A, we say a~ b if and only if there exists g ∈ G with ag = b. We see easily that a ~ b is an equivalence relation and we call the equivalence classes the orbits of G. Thus A is the disjoint union of orbits under the action of G. We say G is 1/2-transitive if all the orbits have the same size, and G is transitive if A is an orbit.

If a ∈ G, set Ga = {g ∈ G | ag = a} so that Ga is clearly a subgroup of G. We see easily that if a ∈ A, g ∈ G, then

Suppose a ~ b so that ah = b. Then {g ∈ G | ag = b} = Gah. Thus if G is transitive, then there is a one-to-one correspondence between the elements of A and the right cosets of Ga given by Gah ↔ b if and only if ah = b. Hence |A| = |G : Ga|.

For each g ∈ G, define θ(g) to be the number of a ∈ A with ag = a.

PROPOSITION 3.1. If G is a permutation group, then Σg∈Gθ(g) = t·|G| where t equals the number of orbits of G on A.

PROOF. It suffices to assume that G is transitive. Consider the set

and we find |S| by counting in two different ways. For each a ∈ A, the number of g with (a,g) ∈ S is |Ga|. Hence since these groups all have the same size, we have |S| = |Ga|·|A| = |G|. Now for each g ∈ G, the number of a with (a, g) ∈ S is θ(g). Hence Σg∈Gθ(g) = |S| = |C| and the result follows.

Note that G is 1/2-transitive if and only if |Ga| is the same for all a ∈ A. A special case of this occurs when Ga = (1) for all a ∈ A. In this case, we say that G is semiregular. If in addition G is transitive, then we say that G is regular.

PROPOSITION 3.2. If H is a transitive abelian group, then H is regular.

PROOF. Fix a ∈ A. If b ∈ A, then there exists h ∈ H with ah = b. Now Hb = Hah = (Ha)h = Ha, so Ha fixes b. Hence Ha = 〈1〉. Since H is transitive, it is regular.

Let G be transitive. A subset B of A is a subset of imprimitivity if, for all g,h ∈ G, we have either Bg = Bh or Bg ∩ Bh . This is equivalent to either Bg = B or Bg ∩ B . We assume here that B . If B = A or |B| = 1, then certainly B is a subset of imprimitivity. We call these trivial. A group G is said to be imprimitive if it has a nontrivial subset of imprimitivity. Otherwise, it is primitive. If B exists, then A = ∪Bg is a disjoint union and hence |B| divides |A|. This yields

PROPOSITION 3.3. Let G be a transitive permutation group of prime degree. Then G is primitive.

We can tell whether G is primitive or not with the following result.

PROPOSITION 3.4. Let G be a transitive permutation group. Then G is primitive if and only if Ga is a maximal subgroup.

PROOF. Suppose G is imprimitive with nontrivial subset of imprimitivity B. Let H = {g ∈ G | Bg = B}. Let a ∈ B. If g ∈ Ga then a ∈ B ∩ Bg so B = Bg and g ∈ H. Hence Ga ⊆ H ⊆ G. Since G is transitive and A ≠ B we have H ≠ G. Since |B| ≠ 1, choose b ∈ B with b ≠ a. By transitivity there exists h ∈ G with ah = b so that h ∉ Ga. Now b ∈ B ∩ Bh so B = Bh and h ∈ H \ Ga. Thus H ∈ Ga and hence Ga is not a maximal subgroup.

Conversely suppose we have Ga < H < G for some subgroup H. Let B = aH. Since H > Ga we have |B| ≠ 1. If B = A, then H is transitive and hence |A| = |G : Ga| = |H : Ga|, a contradiction since G ≠ H. Finally, suppose B ∩ Bg so that b ∈ B ∩ Bg. Thus for some h1, h2 ∈ H we have ah1 = b = ah2g and hence h2gh1-1 ∈ Ga ⊆ H. This yields g ∈ H and thus B = Bg.

Let m ≤ deg G be a positive integer. We say G is m-transitive if given any two ordered subsets {a1, a2, …, am} and {b1, b2,…, bm} of A of size to, there exists g ∈ G with aig = bi. If m ≥ 2, then m-transitivity clearly implies (to m − 1)-transitivity.

PROPOSITION 3.5. Let |A| = n. Then Sym(A) is n-transitive and Alt(A) is (n – 2)-transitive but not (n – 1)-transitive.

PROOF. Obviously Sym( A) is n-transitive. Given {a1, a2, …, an-2} and {b1, b2,…, bn-2}. Then precisely one of

is even. Here an-1, an, bn-1, bn are the obvious remaining elements. Thus Alt(A) is (n – 2)-transitive but not (n – 1)-transitive.

PROPOSITION 3.6. Let G be a transitive permutation group on set A. If m ≥ 2, then G is m-transitive on A if and only if Ga is (m − 1)-transitive on A \ {a}.

PROOF. Obviously if G is m-transitive, then Ga is (m— 1)-transitive on A \ {a}. Now let G be transitive and let Ga be (m— 1)-transitive on A \ {a}. Note since G is transitive, this holds for all a ∈ A. Given any two ordered subsets {a1, a2,..., am},{b1, b2, … , bm} choose g ∈ G with a1g = b1. Now choose h ∈ Gb1 with (aig)h = bi for i = 2,... ,m. Then for i = 1, 2,..., m we have ai(gh) = bi since a1g = b1 and h ∈ Gb1.

We now obtain a few simple facts about doubly transitive groups.

PROPOSITION 3.7. Let G be transitive. Then G is doubly transitive if and only if for all g ∈ G \ Ga we have G = Ga ∩ GagGa.

PROOF. Suppose G is doubly transitive. Given g ∈ G \ Ga. If h ∈ G\Ga then ah = b and ag = c with b, c ≠ a. Since Ga is transitive on A \ {a} we can find k ∈ Ga with bk = c. Hence ahk = bk = c = ag and hkg-1 ∈ Ga so h ∈ GagGa.

Now let G = Ga ∩ GagGa. Given b, c ∈ A \ {a}, then since G is transitive, we can find h1, h2 ∈ G with ah1 = b, ah2 = c. Clearly h1, h2 ∉ Ga so we must have h2 = k1h1k2 for some k1, k2 ∈ Ga. Then c = ah2 = ak1h1k2 = ah1k2 = bk2, so Ga is transitive on A \ {a}.

Since the above subgroups are obviously maximal, we have

PROPOSITION 3.8. If G is doubly transitive, then G is primitive.

PROPOSITION 3.9. Let G be transitive and let Ga have s orbits on A. Then ∑g∈Gθ(g)² = s|G|. In particular, the permutation group G is doubly transitive if and only if ∑g∈Gθ(g)² = 2|G|.

PROOF. Let S = {(g,a,b) | g ∈ G, a,b ∈ A, g ∈ Ga ∩ Gb}. We compute the size of S. For each g the number of ordered pairs (a, b) with (g,a,b) ∈ S is clearly θ(g)². Thus |S| = ∑g∈Gθ(g)². Now since G is transitive, we see that |S| = |A|·|T|, where the set T is defined by T = {(g, b) | g ∈ Ga, b ∈ A, bg = b} for some fixed a ∈ A. As in the proof of Proposition 3.1, |T| = |Ga|s. Hence

and the result follows.

4. Normal Subgroups

We now study normal subgroups of transitive groups. The relationship of our first result to this will be apparent later.

PROPOSITION 4.1. Let N be a finite group and let G be a group of automorphisms of N. Then G acts as a permutation group on N# = N \ {1}.

i.  If G is transitive, then N is an elementary abelian p-group for some prime p.

ii.  If G is doubly transitive, then either |N| = 3 or N is an elementary abelian 2-group.

iii.  If G is triply transitive, then |N| =4.

iv.  G cannot be quadruply transitive.

PROOF. Let p be a prime dividing |N|. Since G is transitive every nonidentity element of N has order p and hence TV is a p-group. Since G must fix