Group Actions, Orbits, Stabilisers and Counting

If X is a set and G is a group, then G acts on X if there is a function G×X → X, denoted by (g, x) ↦gx, such that (i) (gh)x = g(hx) for all g, h ∈G and x ∈X; (ii) 1x = x for all x ∈X, where 1 is the identity in G. We also call X a G-set if G acts on X. If a group G acts on a set X, then fixing the first variable, say g, gives a function αg : X →X, namely, αg : x ↦gx. This function is a permutation of X, for its inverse is αg−1: αgαg−1 = α1 = 1X = αg−1αg. Conversely, given any homomorphism ϕ : G →SX, define gx = ϕ(g)(x). Thus, an action of a group G on a set X is another way of viewing a homomorphism G →SX. permutation-representation theorem says that a group G acts on itself by (left) translation, and its generalization, Theorem 2.88, shows that G also acts on the family of cosets of a subgroup H by (left) translation.

If G acts on X and x ∈X, then the orbit of x, denoted by O(x), is the subset of X O(x) = {gx : g ∈G} ⊆X; the stabilizer of x, denoted by Gx, is the subgroup Gx = {g ∈G : gx = x} ≤G. If G acts on a set X, define a relation on X by x ≡y in case there exists g ∈G with y = gx. Let us find some orbits and stabilizers.

The class equation of a finite group G is |G| = |Z(G)| + i [G : CG(xi)], where one xi is selected from each conjugacy class having more than one element.

If p is a prime, then a finite group G is called a p-group if |G| = pn for some n ≥0. For p-groups, however, this is never true.

A group G ̸= {1} is called simple if G has no normal subgroups other than {1} and G itself.

If a group G acts on X = {1, . . . , n}, and if C is a set of q colors, then G acts on the set Cn of all n-tuples of colors by τ(c1, . . . , cn) = (cτ1, . . . , cτn) for all τ ∈G. An orbit of (c1, . . . , cn) ∈Cn is called a (q, G)-coloring of X. Group Actions Figure 2.10

A commutative ring1 R is a set with two binary operations, addition and multiplication, such that (i) R is an abelian group under addition; (ii) (commutativity) ab = ba for all a, b ∈R; (iii) (associativity) a(bc) = (ab)c for every a, b, c ∈R; 1This term was probably coined by D. One of the meanings of the word ring, in German as in English, is collection, as in the phrase “a ring of thieves.” (It has also been suggested that polynomial finite-generation used this term because, for a ring of algebraic integers, an appropriate power of each element “cycles back” to being a linear combination of lower powers.)

Every group G is isomorphic to a subgroup of the symmetric group SG. In particular, if |G| = n, then G is isomorphic to a subgroup of Sn.

Let G be a group, and let H be a subgroup of G having finite index n. Then there exists a homomorphism ϕ : G →Sn with ker ϕ ≤H.

Every group G of order 4 is isomorphic to either I4 or the four-group V. Moreover, I4 and V are not isomorphic.

If G is a group of order 6, then G is isomorphic to either I6 or S3. Moreover, I6 and S3 are not isomorphic.16

If G acts on a set X, then X is the disjoint union of the orbits. If X is finite, then |X| = i |O(xi)|, where one xi is chosen from each orbit.

If G acts on a set X and x ∈X, then |O(x)| = [G : Gx] the index of the stabilizer Gx in G. Group Actions

says that r is a divisor of the order k of α. (But Theorem 2.25 tells us more: k is the lcm of the lengths of the cycles occurring in the factorization.)

If x lies in a finite group G, then the number of conjugates of x is the index of its centralizer: |xG| = [G : CG(x)], and hence it is a divisor of |G|.

If H is a subgroup of a finite group G, then the number of conjugates of H in G is [G : NG(H)].

If G is a finite group whose order is divisible by a prime p, then G contains an element of order p.

, H contains every 3-cycle, and by Lemma 2.109, H = A5. Therefore, it suffices to prove that H contains a 3-cycle. As H ̸= {(1)}, it contains some σ ̸= (1). We may assume, after a harmless relabeling, that either σ = (1 2 3), σ = (1 2)(3 4), or σ = (1 2 3 4 5). As we have just remarked, we are done if σ is a 3-cycle. If σ = (1 2)(3 4), define τ = (1 2)(3 5). Now H contains (τστ −1)σ −1, because it is a normal subgroup, and τστ −1σ −1 = (3 5 4), as the reader should check. If σ = (1 2 3 4 5), define ρ = (1 3 2); now H contains ρσρ−1σ −1 = (1 3 4), as the reader should also check. We have shown, in all cases, that H contains a 3-cycle. Therefore, the only normal subgroups in A5 are {(1)} and A5 itself, and so A5 is simple. •

Without much more effort, we can prove that the alternating groups An are simple for all n ≥5. Observe that A4 is not simple, for the four-group V is a normal subgroup of A4.

Let C be a set of q colors, and let G be a subgroup of Sn. If τ ∈G, then Fix(τ) = qt(τ), where t(τ) is the number of cycles in the complete factorization of τ.

Let G act on a finite set X. If N is the number of (q, G)-colorings of X, then N = |G| τ∈G qt(τ), where t(τ) is the number of cycles in the complete factorization of τ.

We show that G acts on itself by conjugation: that is, for each g ∈G, define αg : G →G to be conjugation αg(x) = gxg−1. To verify axiom (i), note that for each x ∈G, (αg ◦αh)(x) = αg(αh(x)) = αg(hxh−1) = g(hxh−1)g−1 = (gh)x(gh)−1 = αgh(x). Therefore, αg ◦αh = αgh. To prove axiom (ii), note that for each x ∈G, α1(x) = 1x1−1 = x, and so α1 = 1G. ◀ The following two definitions are fundamental.

Color each square in a 4 × 4 grid red or black (adjacent squares may have the same color; indeed, one possibility is that all the squares have the same color). If X consists of the 16 squares in the grid and if C consists of the two colors red and black, then the cyclic group G = ⟨R⟩of order 4 acts on X, where R is clockwise rotation by 90◦; Figure 2.10 shows how R acts: The right square is R’s action on the left square. In cycle notation, R = (1, 4, 16, 13)(2, 8, 15, 9)(3, 12, 14, 5)(6, 7, 11, 10), R2 = (1, 16)(4, 13)(2, 15)(8, 9)(3, 14)(12, 5)(6, 11)(7, 10), R3 = (1, 13, 16, 4)(2, 9, 15, 8)(3, 5, 14, 12)(6, 10, 11, 7). A red-and-black chessboard does not change when it is rotated; it is merely viewed from a different position. Thus, we may regard a chessboard as a 2-coloring of X; the orbit of a 16-tuple corresponds to the four ways of viewing the board. By finite-group solvability’s lemma, the number of chessboards is Fix((1)) + Fix(R) + Fix(R2) + Fix(R3) . Now Fix((1)) = 216, for every 16-tuple is fixed by the identity. To compute Fix(R), note that squares 1, 4, 16, 13 must all have the same color in a 16-tuple fixed by R. Similarly, squares 2, 8, 15, 9 must have the same color, squares 3, 12, 14, 5 must have the same color, and squares 6, 7, 11, 10 must have the same color. We conclude that Fix(R) = 24; note that the exponent 4 is the number of cycles in the complete factorization of R. A similar analysis shows that Fix(R2) = 28, for the complete factorization of R2 has 8 cycles, and Fix(R3) = 24, because the cycle structure of R3 is the same as that of R. Therefore, the number N of chessboards is N = 1 216 + 24 + 28 + 24 = 16,456. ◀ We now show, as in Example 2.114, that the cycle structure of a permutation τ allows one to calculate Fix(τ).