# 6.2: Groups Acting on Sets

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)

We defined the rotation group \(C_4\) and the dihedral group \(D_4\) as groups of permutations of the vertices of a square. These permutations represent rigid motions of the square in the plane and in three-dimensional space respectively. The square has geometric features of interest other than its vertices; for example, its diagonals, or its edges. Any geometric motion of the square that returns it to its original location takes each diagonal to a possibly different diagonal, and takes each edge to a possibly different edge. In Figure 6.5 we show the results on the sides and diagonals of the rotations of a square. The rotation group permutes the sides of the square and permutes the diagonals of the square as it rotates the square. Thus we say the rotation group “acts” on the sides and diagonals of the square.

Exercise ◦279.

- Write down the two-line notation for the permutation ρ that a 90 degree rotation does to the sides of the square.
- Write down the two-line notation for the permutation ρ 2 that a 180 degree rotation does to the sides of the square.
- Is ρ 2 = ρ ◦ ρ? Why or why not?
- Write down the two-line notation for the permutation ρb that a 90 degree rotation does to the diagonals d13, and d24 of the square.
- Write down the two-line notation for the permutation ρc2 that a 180 degree rotation does to the diagonals of the square.
- Is ρc2 = ρb◦ ρb? Why or why not? What familiar permutation is ρc2 in this case?

3The phrase cyclic group applies in a more general (but similar) situation. Namely the set of all powers of any member of a group is called a cyclic group.

*Figure 6.5: The results on the sides and diagonals of rotating the square *

We have seen that the fact that we have defined a permutation group as the permutations of some specific set doesn’t preclude us from thinking of the elements of that group as permuting the elements of some other set as well. In order to keep track of which permutations of which set we are using to define our group and which other set is being permuted as well, we introduce some new language and notation. We are going to say that the group \(D_4\) “acts” on the edges and diagonals of a square and the group R of permutations of the vertices of a cube that arise from rigid motions of the cube “acts” on the edges, faces, diagonals, etc. of the cube.

•280. In Figure 6.3 we show a cube with the positions of its vertices and faces labeled. As with motions of the square, we let we let ϕ(x) be the label of the place where vertex previously in position x is now.

- In Problem 263 we wrote in two row notation the permutation ρ of the vertices that corresponds to rotating the cube 90 degrees around a vertical axis through the faces t (for top) and u (for underneath). (We rotated in a right-handed fashion around this axis, meaning that vertex 6 goes to the back and vertex 8 comes to the front.) Write in two row notation the permutation ρ of the faces that corresponds to this member ρ of R.
- In Problem 263 we wrote in two row notation the permutation ϕ that rotates the cube 120 degrees around the diagonal from vertex 1 to vertex 7 and carries vertex 8 to vertex 6. Write in two row notation the permutation ϕ of the faces that corresponds to this member of R.
- In Problem 263 we computed the two row notation for ρ ◦ ϕ. Now compute the two row notation for ρ ◦ ϕ (ρ was defined in Part 280a), and write in two row notation the permutation ρ ◦ ϕ of the faces that corresponds to the action of the permutation ρ ◦ ϕ on the faces of the cube (for this question it helps to think geometrically about what motion of the cube is carried out by ρ ◦ ϕ). What do you observe about ρ ◦ ϕ and ρ ◦ ϕ? We say that a permutation group G acts on a set S if, for each member σ of G there is a permutation σ of S such that σ ◦ ϕ = σ ◦ ϕ for every member σ and ϕ of G. In Problem 280c you saw one example of this condition. If we think intuitively of ρ and ϕ as motions in space, then following the action of ϕ by the action of ρ does give us the action of ρ ◦ ϕ. We can also reason directly with the permutations in the group R of rigid motions (rotations) of the cube to show that R acts on the faces of the cube. ◦281. Show that a group G of permutations of a set S acts on S with ϕ = ϕ for all ϕ in G.

◦282. The group \(D_4\) is a group of permutations of {1, 2, 3, 4} as in Problem 255. We are going to show in this problem how this group acts on the two-element subsets of {1, 2, 3, 4}. In Problem 287 we will see a natural geometric interpretation of this action. In particular, for each two-element subset {i, j} of {1, 2, 3, 4} and each member σ of D4 we define σ({i, j}) = {σ(i), σ(j)}. Show that with this definition of σ, the group \(D_4\) acts on the two-element subsets of {1, 2, 3, 4}.

·283. Suppose that σ and ϕ are permutations in the group R of rigid motions of the cube. We have argued already that each rigid motion sends a face to a face. Thus σ and ϕ both send the vertices on one face to the vertices on another face. Let {h, i, j, k} be the set of labels next to the vertices on a face F.

- What are the labels next to the vertices of the face F 0 that F is sent to by ϕ? (The function ϕ may appear in your answer.)
- What are the next to the vertices of the face F 00 that F 0 is sent to by σ?
- What are the labels next to the vertices of the face F 000 that F is sent to by σ ◦ ϕ?
- How have you just shown that the group R acts on the faces?

### 6.2.1 Groups acting on colorings of sets

Recall that when you were asked in Problem 45 to find the number of ways to place two red beads and two blue beads at the corners of a square free to move in three-dimensional space, you were not able to apply the quotient principle to answer the question. Instead you had to see that you could divide the set of six lists of two Rs and two Bs into two sets, one of size two in which the Rs and Bs alternated and one of size four in which the two reds (and therefore the two blues) would be side-by-side on the square. Saying that the square is free to move in space is equivalent to saying that two arrangements of beads on the square are equivalent if a member of the dihedral group carries one arrangement to the other. Thus an important ingredient in the analysis of such problems will be how a group can act on colorings of a set of vertices. We can describe the coloring of the square in Figure 6.6 as the function f with f(1) = R, f(2) = R, f(3) = B, and f(4) = B, but it is more compact and turns out to be more suggestive to represent the coloring in Figure 6.6 as the set of ordered pairs (1, R),(2, R),(3, B),(4, B). (6.1)

*Figure 6.6: The colored square with coloring {(1, R),(2, R),(3, B),(4, B)} R 1 R 2 B 4 B 3 *

This gives us an explicit list of which colors are assigned to which vertex.4 Then if we rotate the square through 90 degrees, we see that the set of ordered pairs becomes {(ρ(1), R),(ρ(2), R),(ρ(3), B),(ρ(4), B)} (6.2) which is the same as {(2, R),(3, R),(4, B),(1, B)}. or, in a more natural order, {(1, B),(2, R),(3, R),(4, B)}. (6.3) The reordering we did in 6.3 suggests yet another simplification of notation. So long as we know we that the first elements of our pairs are labeled by the members of [n] for some integer n and we are listing our pairs in increasing order by the first component, we can denote the coloring {(1, B),(2, R),(3, R),(4, B)} by BRRB. In the case where we have numbered the elements of the set S we are coloring, we will call this list of colors of the elements of S in order the standard notation for the coloring. We will call the ordering used in 6.3 the standard ordering of the coloring. Thus we have three natural ways to represent a coloring of a set as a function, as a set of ordered pairs, and as a list. Different representations are useful for different things. For example, the representation by ordered pairs will provide a natural way to define the action of a group on colorings of a set. Given a coloring as a function f, we denote the set of ordered pairs {(x, f(x))|x ∈ S}, suggestively as (S, f) for short. We use f(1)f(2)· · · f(n) to stand for a particular coloring (S, f) in the standard notation.

◦284. Suppose now that instead of coloring the vertices of a square, we color its edges. We will use the shorthand 12, 23, 34, and 41 to stand for the edges of the cube between vertex 1 and vertex 2, vertex 2 and vertex

Note

4The reader who has studied Appendix A will recognize that this set of ordered pairs is the relation of the function f, but we won’t need to make any specific references to the idea of a relation in what follows.

, and so on. Then a coloring of the edges with 12 red, 23 blue, 34 red and 41 blue can be represented as {(12, R),(23, B),(34, R),(41, B)}. (6.4) If ρ is the rotation through 90 degrees, then we have a permutation ρ acting on the edges. This permutation acts on the colorings to give us a permutation ρ of the set of colorings. (a) What is ρ of the coloring in 6.4? (b) What is ρ 2 of the coloring in 6.4? If G is a group that acts the set S, we define the action of G on the colorings (S, f) by σ((S, f)) = σ({(x, f(x))|x ∈ S}) = {(σ(x), f(x))|x ∈ S}. (6.5) We have the two bars over σ, because σ is a permutation of one set that gives us a permutation σ of a second set, and then σ acts to give a permutation σ of a third set, the set of colorings. For example, suppose we want to anlayze colorings of the faces of a cube under the action of the rotation group of the cube as we have defined it on the vertices. Each vertex-permutation σ in the group gives a permutation σ of the faces of the cube. Then each permutation σ of the faces gives us a permutation σ of the colorings of the faces. In the special case that G is a group of permutations of S rather than a group acting on S, Equation 6.5 becomes σ((S, f)) = σ({(x, f(x))|x ∈ S}) = {(σ(x), f(x))|x ∈ S}. In the case where G is the rotation group of the square acting on the vertices of the square, the example of acting on a coloring by ρ that we saw in 6.3 is an example of this kind of action. In the standard notation, when we act on a coloring by σ, the color in position i moves to position σ(i). 285. Why does the action we have defined on colorings in Equation 6.5 take a coloring to a coloring?

286. Show that if G is a group of permutations of a set S, and f is a coloring function on S, then the equation σ({(x, f(x))|x ∈ S}) = {(σ(x), f(x))|x ∈ S} defines an action of G on the colorings (S, f) of S. Online hint.

### 6.2.2 Orbits

•287. In Problem 282

- What is the set of two element subsets that you get by computing σ({1, 2}) for all σ in D4?
- What is the multiset of two-element subsets that you get by computing σ({1, 2}) for all σ in D4? (c) What is the set of two-element subsets you get by computing σ({1, 3}) for all σ in D4?
- What is the multiset of two-element subsets that you get by computing σ({1, 3}) for all σ in D4?
- Describe the two sets in parts (a) and (c) geometrically in terms of the square.

◦288. This problem uses the notation for permutations in the dihedral group of the square introduced before Problem 259. What is the effect of a 180 degree rotation ρ 2 on the diagonals of a square? What is the effect of the flip ϕ1|3 on the diagonals of a square? How many elements of D4 send each diagonal to itself? How many elements of D4 interchange the diagonals of a square? In Problem 287 you saw that the action of the dihedral group D4 on two element subsets of {1, 2, 3, 4} seems to split them into two blocks, one with two elements and one with 4. We call these two blocks the “orbits” of D4 acting on the two element subsets of {1, 2, 3, 4}. More generally, given a group G acting on a set S, the orbit of G determined by an element x of S is the set {σ(x)|σ ∈ G}, and is denoted by Gx. In Problem 287 it was possible to have Gx = Gy. In fact in that problem, Gx = Gy for every y in Gx. 289. Suppose a group acts on a set S. Could an element of S be in two different orbits? (Say why or why not.) Online hint. A second online hint. Problem 289 almost completes the proof of the following theorem. Theorem 9 Suppose a group acts on a set S. The orbits of G form a partition of S.

It is probably worth pointing out that this theorem tells us that the orbit Gx is also the orbit Gy for any element y of Gx. 290. Complete the proof of Theorem 9. Notice that thinking in terms of orbits actually hides some information about the action of our group. When we computed the multiset of all results of acting on {1, 2} with the elements of D4, we got an eight-element multiset containing each side twice. When we computed the multiset of all results of acting on {1, 3} with the elements of D4, we got an eight-element multiset containing each diagonal of the square four times. These multisets remind us that we are acting on our two-element sets with an eight-element group. The multiorbit of G determined by an element x of S is the multiset {σ(x)|σ ∈ G}, and is denoted by Gxmulti. When we used the quotient principle to count circular seating arrangements or necklaces, we partitioned up a set of lists of people or beads into blocks of equivalent lists. In the case of seating n people around a round table, what made two lists equivalent was, in retrospect, the action of the rotation group Cn. In the case of stringing n beads on a string to make a necklace, what made two lists equivalent was the action of the dihedral group. Thus the blocks of our partitions were orbits of the rotation group or the dihedral group, and we were counting the number of orbits of the group action. In Problem 45, we were not able to apply the quotient principle because we had blocks of different sizes. However, these blocks were still orbits of the action of the group D4. And, even though the orbits have different sizes, we expect that each orbit corresponds naturally to a multiorbit and that the multiorbits all have the same size. Thus if we had a version of the quotient rule for a union of multisets, we could hope to use it to count the number of multiorbits.

◦291.

- (a) Find the orbit and multiorbit of D4 acting on the coloring {(1, R),(2, R),(3, B),(4, B)}, or, in standard notation, RRBB, of the vertices of a square.
- (b) How many group elements map the coloring RRBB to itself? What is the multiplicity of RRBB in its multiorbit?
- (c) Find the orbit and multiorbit of D4 acting on the coloring {(1, R),(2, B),(3, R),(4, B)}.
- (d) How many elements of the group send the coloring RBRB to itself? What is the multiplicity of RBRB in its orbit?

292.

(a) If G is a group, how is the set {τσ|τ ∈ G} related to G? (b) Use this to show that y is in the multiorbit Gxmulti if and only if Gxmulti = Gymulti. Problem 292b tells us that, when G acts on S, each element x of S is in one and only one multiorbit. Since each orbit is a subset of a multiorbit and each element x of S is in one and only one orbit, this also tells us there is a bijection between the orbits of G and the multiorbits of G, so that we have the same number of orbits as multiorbits. When a group acts on a set, a group element is said to fix an element of x ∈ S if σ(x) = x. The set of all elements fixing an element x is denoted by Fix(x). 293. Suppose a group G acts on a set S. What is special about the subset Fix(x) for an element x of S?

•294. Suppose a group G acts on a set S. What is the relationship of the multiplicity of x ∈ S in its multiorbit and the size of Fix(x)? 295. What can you say about relationships between the multiplicity of an element y in the multiorbit Gxmulti and the multiplicites of other elements? Try to use this to get a relationship between the size of an orbit of G and the size of G. Online hint.

We suggested earlier that a quotient principle for multisets might prove useful. The quotient principle came from the sum principle, and we do not have a sum principle for multisets. Such a principle would say that the size of a union of disjoint multisets is the sum of their sizes. We have not yet defined the union of multisets or disjoint multisets, because we haven’t needed the ideas until now. We define the union of two multisets S and T to be the multiset in which the multiplicity of an element x is the maximum5 of the multiplicity of x in S and its multiplicity in T. Similarly, the union of

5We choose the maximum rather than the sum so that the union of sets is a special case of the union of multisets.

a family of multisets is defined by defining the multiplicity of an element x to be the maximum of its multiplicities in the members of the family. Two multisets are said to be disjoint if no element is a member of both, that is, if no element has multiplicity one or more in both. Since the size of a multiset is the sum of the multiplicities of its members, we immediately get the sum principle for multisets. The size of a union of disjoint multisets is the sum of their sizes. Taking the multisets all to have the same size, we get the product principle for multisets. The union of a set of m disjoint multisets, each of size n has size mn. The quotient principle for multisets then follows immediately. If a p-element multiset is a union of q disjoint multisets, each of size r, then q = p/r.

•296. How does the size of the union of the set of multiorbits of a group G acting on a set S relate to the number of multiorbits and the size of G? •297. How does the size of the union of the set of multiorbits of a group G acting on a set S relate to the numbers |Fix(x)|?

•298. In Problems 296 and 297 you computed the size of the union of the set of multiorbits of a group G acting on a set S in two different ways, getting two different expressions which must be equal. Write the equation that says they are equal and solve for the number of multiorbits, and therefore the number of orbits.

### 6.2.3 The Cauchy-Frobenius-Burnside Theorem

•299. In Problem 298 you stated and proved a theorem that expresses the number of orbits in terms of the number of group elements fixing each element of S. It is often easier to find the number of elements fixed by a given group element than to find the number of group elements fixing an element of S.

- For this purpose, how does the sum P x:x∈S |Fix(x)| relate to the number of ordered pairs (σ, x) (with σ ∈ G and x ∈ S) such that σ fixes x?
- Let χ(σ) denote the number of elements of S fixed by σ. How can the number of ordered pairs (σ, x) (with σ ∈ G and x ∈ S) such that σ fixes x be computed from χ(σ)? (It is ok to have a summation in your answer.)
- (What does this tell you about the number of orbits?

300. A second computation of the result of problem 299 can be done as follows. (a) Let ˆχ(σ, x) = 1 if σ(x) = x and let ˆχ(σ, x) = 0 otherwise. Notice that ˆχ is different from the χ in the previous problem, because it is a function of two variables. Use ˆχ to convert the single summation in your answer to Problem 298 into a double summation over elements x of S and elements σ of G. (b) Reverse the order of the previous summation in order to convert it into a single sum involving the function χ given by χ(σ) = the number of elements of S left fixed by σ. In Problem 299 you gave a formula for the number of orbits of a group G acting on a set X. This formula was first worked out by Cauchy in the case of the symmetric group, and then for more general groups by Frobenius. In his pioneering book on Group Theory, Burnside used this result as a lemma, and while he attributed the result to Cauchy and Frobenius in the first edition of his book, in later editions, he did not. Later on, other mathematicians who used his book named the result “Burnside’s Lemma,” which is the name by which it is still most commonly known.

Let us agree to call this result the Cauchy-Frobenius-Burnside Theorem, or CFB Theorem for short in a compromise between historical accuracy and common usage. 301. In how many ways may we string four (identical) red, six (identical) blue, and seven (identical) green beads on a necklace? Online hint. 302. If we have an unlimited supply of identical red beads and identical blue beads, in how many ways may we string 17 of them on a necklace? 303. If we have five (identical) red, five (identical) blue, and five (identical) green beads, in how many ways may we string them on a necklace?

In how many ways may we paint the faces of a cube with six different colors, using all six? 305. In how many ways may we paint the faces of a cube with two colors of paint? What if both colors must be used? Online hint. 306. In how many ways may we color the edges of a (regular) (2n + 1)-gon free to move around in the plane (so it cannot be flipped) if we use red n times and blue n + 1 times? If this is a number you have seen before, identify it. Online hint. ∗307. In how many ways may we color the edges of a (regular) (2n + 1)-gon free to move in three-dimensional space so that n edges are colored red and n + 1 edges are colored blue? Your answer may depend on whether n is even or odd. ∗308. (Not unusually hard for someone who has worked on chromatic polynomials.) How many different proper colorings with four colors are there of the vertices of a graph which is a cycle on five vertices? (If we get one coloring by rotating or flipping another one, they aren’t really different.) ∗309. How many different proper colorings with four colors are there of the graph in Figure 6.7? Two graphs are the same if we can redraw one of the graphs, not changing the vertex set or edge set, so that it is identical to the other one. This is equivalent to permuting the vertices in some way so that when we apply the permutation to the endpoints of the edges to get a new edge set, the new edge set is equal to the old one. Such a permutation is called an automorphism of the graph. Thus two colorings are different if there is no automorphism of the graph that carries one to the other one. Online hint. A second online hint.