Symmetry and Counting

God decided to take the devil to court and settle their differences once and for all. When Satan heard of this, he grinned and said, -and where do you think you’re going to find a good fucking lawyer?

Recall.

1. If G is a group with identity element e and X is a set, then a (left) group action α of G on X is a function α: G x X → X that satisfies: α(e, x) = x, and α(g, α(h, x)) = α(gh, x) with α(g, x) often shortened to g·x, hence (i) e·x = x, (ii) g·(h·x) = (gh·x). The group G is said to act on X. A set X together with an action of G is called a G-set.
2. If G is a group on a set X, x ∈ X, the orbit of an element x ∈ X is the set of elements that x can reach via the action of some element of the group, Orb_G(x) = {g·x | g ∈ G}.
3. For every element x ∈ X, the stabilizer subgroup of G with respect to x is the set of all elements in G that fix x: G_x = stab_G(x) = {g ∈ G | g·x = x}.
4. Given a fixed group element g ∈ G, the stable set of g is the set of elements of X that are stabilized by g, that is, X_g = {x ∈ X: g·x = x} ⊆ X.

For any sets X and Y, the set of all functions f : X → Y is denoted as Y^X = {f | f: X → Y}. Let G be a group acting on X. Y_X has a natural G-set structure, that is, ·: G x Y_X → Y_X, g ∈ G, f ∈ Y_X, g·f: X → Y is defined as the function g·f(x) = f(g·x) ∀x ∈ X.

Lemma. Let G be a group whose identity is e. Let X be a set and ·:G x X → X be a group action. Then, the set of orbits of X under the action of G, written as X/G or X_G, forms a partition of X.

Proof:

Let’s define the relation x R_g y or, more succinctly, x ~ y ↭ y ∈ Orb(x) ↭ ∃g ∈ G: y = g·x. It is an equivalent relation. ∀x, y, z ∈ X:

1. Reflexivity. x ~ x because ∃e ∈ G (G is a group): x = e·x (i)
2. Symmetry: x ~ y ↭ y ∈ Orb(x) ↭ ∃g ∈ G: y = g·x ⇒ g^-1·y = g^-1·(g·x) ⇒[(ii)’s axiom action] g^-1·y = x ⇒ ∃g^-1 ∈ G: x = g^-1·y ⇒ x ∈ Orb(y) ⇒ y ~ x.
3. Transitivity: x ~ y and y ~ z ⇒ ∃g, g’ ∈ G: y = g·x, z = g’·y = g’·(g·x) =[(ii)’s axiom action] (g’g)·x, that is, z = (g’g)·x ⇒ z ∈ Orb(x) ⇒ x ~ z.

The quotient set X/R_g, that is, the set of orbits of the group action forms a partition of X.

Notice that the equivalent class of x is [x] = {y ∈ X | x ~ y} = {y ∈ X | y ∈ Orb(x)} = {y ∈ X | ∃g ∈ G: y = g·x}

Lemma. Let x and y be two elements in X, and let g be a group element such that y = g·x. Then, the two stabilizer groups G_x = Orb_G(x) and G_y = Orb_G(y) are related by G_y = gG_xg^-1 . In other words, the stabilizers of elements in the same orbit are conjugate to each other.

Proof.

Assume that x and y are two elements in X, and let g be a group element such that y = g·x.

Let’s prove that G_y ⊆ gG_xg^-1. ∀h ∈ G_y ↭ h·y = y ↭[y = g·x] h·(g·x) = g·x ⇒ [Applying g^-1 to both sides of this equality and taking (ii) into account yields…] (g^-1hg)·x = x ⇒ g^-1hg ∈ G_x ⇒ h = g(g^-1hg)g^-1 ∈ gG_xg^-1.

Next, let’s prove that gG_xg^-1 ⊆ G_y. y = g·x ⇒ x = g^-1·y. ∀h ∈ G_x ↭ h·x = x ⇒ h·(g^-1·y) = g^-1·y ⇒ [Applying g to both sides of this equality yields…] (ghg^-1)·y = y ↭ ghg^-1 ∈ G_y ∎

Let G be a group acting on a set X. We have demonstrated that the stabilizers of elements in the same orbit are conjugate to each other, that is, G_g·x = gG_xg^-1, and therefore they are isomorphic to each other G_x ≋ G_g·x via an inner automorphism. In particular, if x and y are G-equivalent, then |G_x| = |G_y|

Let G be a group. For any g ∈ G, define the map c_g: G → G, given by c_g(x) = gxg^-1. c_g is an automorphism of G, and is termed as an inner automorphism.

Burnside’s Theorem. If G is a finite group acting on X, then the number k of G-orbits of X is $\frac{1}{|G|}\sum_{g∈G}|X_g|$

Proof:

Consider the equation g·x = x of two variables g ∈ G, x ∈ X. How many solutions does it have?

For each g ∈ G, the number of such pairs is $|X_g|$, so it is $\sum_{g∈G}|X_g|$. For each x ∈ X, the number of such pairs is |G_x|, so the total is $\sum_{x∈X}|G_x|$ and obviously $\sum_{g∈G}|X_g|=\sum_{x∈X}|G_x|$ 🚀

The Fundamental Counting Principle Let G be a group acting on X and x an element of X. Then, the cardinality of an orbit is equal to the index of its stabilizer, that is, |O_x| = [G:G_x]

$\sum_{y∈\mathbb{O_x}}|G_y|$ =[|G_y| = |G_x| if y ∈ $\mathbb{O_x}$ (x and y are in the same orbit)] $\sum_{y∈\mathbb{O_x}}|G_x| = |\mathbb{O_x}||G_x|$ = [The Fundamental Counting Principle] = [G:G_x]|G_x| = [By Lagrange’s Theorem] |G|. Therefore, $\sum_{y∈\mathbb{O_x}}|G_y|=|G|$

$\sum_{g∈G}|X_g|=🚀\sum_{x∈X}|G_x|$ = [Since we have just demonstrated that orbits partition X, we are going to have |G| as many times as orbits, that is, k] k|G| ⇒ k = $\frac{1}{|G|}\sum_{g∈G}|X_g|$

Examples.

• Let X = {1, 2, 3, 4, 5} and G = {1, (13), (13)(25), (25)}. G naturally acts on X. There are three orbits, so X = {1, 3} ∪ {4} ∪ {2, 5}.

Alternatively, X_id = X, X₍₁₃₎ = {2, 4, 5}, X_((13)(25)) = {4}, X₍₂₅₎ = {1, 3, 4}.

The number k of G-orbits of X is $\frac{1}{|G|}\sum_{g∈G}|X_g|=\frac{1}{4}(5+3+1+3)=3$

• Using two colors, say black and white, in how many ways can the vertices of a square be colored? It seems pretty obvious that 2⁴ = 16. However, assuming that reflections and rotations are allowed, that is, colors obtained from rigid motions are considered equivalent, so we have over-counted (Figure 2).

If Y = {1, 2, 3, 4}, then D₄ acts on Y in a natural way, and coloring of the vertices is a function f: Y → {B, W}. Let X = {B, W}^Y = {f| f: {1, 2, 3, 4} → {B, W}}, |X| = 16, and D₄ acts on X naturally. Therefore, our original question is the same as asking how many orbits does D₄ have on the set of X?

|X_id| = 2⁴ = 16. |X_r| =₍₁₂₃₄₎ 2, |X_r²| =_(13)(24) 4, |X_r³| =₍₁₄₃₂₎ 2, |X_s| =_(14)(23) 4, |X_rs| =₍₂₄₎ 8, |X_r²s| = 4, |X_r³s| = 8 (Figure 3).

|X_g| = 2^a where 2 = |{B, W}|. a = number of cycles in the cycle decomposition of each permutation because vertices in the same cycle need to share the same color if the square was to be fixed.

Two designs A and B are equivalent under a group G of permutations if there is an element Φ ∈ G: Φ(A) = B, that is, they are in the same orbit of G. Therefore, the number of nonequivalent designs under G is the number of orbits of designs under G.

k = [Burnside’s Theorem] $\frac{1}{|G|}\sum_{g∈G}|X_g|$=[|X_g| = 2^a where 2 = |{B, W}|. a = number of cycles in the cycle decomposition of each permutation because vertices in the same cycle need to share the same color if the square was to be fixed.] = $\frac{1}{8}(16+2+4+2+4+8+4+8)=6$ (Figure 4)

• Therefore, if we could use four colors, the result would be k = [Burnside’s Theorem] $\frac{1}{|G|}\sum_{g∈G}|X_g|$=[|X_g| = 4^a where a = number of cycles in the cycle decomposition of each permutation because vertices in the same cycle need to share the same color if the square was to be fixed.] $=\frac{1}{8}(4^4+4^1+4^2+4^1+4^2+4^3+4^2 +4^3) = 55$

• How many ways can a tetrahedron be labeled (Figure 5)? A₄ is the rotational symmetry group for the tetrahedron, |A₄| = 12. It has the identity, three 2-2 cycles -each of which fixes no vertex, (12)(34), (14)(23), (13)(24)-, and eight 3-cycles -each of which fixes one vertex, e.g., we have two rotations keeping 4 fixed (132), (123), and obviously there are six rotations more which keeps vertices 1, 2, and 3 fixed.-. However, the only element that fixes any such labeling is the identity, and |X_id| = 4!, so k = [Burnside’s Theorem, a = 4] $\frac{1}{|G|}\sum_{g∈G}|X_g|=\frac{1}{12}(4!+3·0+8·0) = 2$

• Given three colors, say red, green, and blue, how many ways can a cube be colored (counting rotations)? k = [Burnside’s Theorem, a = 4] $\frac{1}{|G|}\sum_{g∈G}|X_g|$

1. First, we need to know |G|. We are going to use the Orbit-stabilizer theorem but on a simpler action, once that simply act on the cube’s faces. Let’s pick the top face as labeled it as “x”. x can be rotated to any other face ⇒ |orb_G(x)| = 6. What are the symmetries that fix this face? It could only be the group of rotation symmetries around the perpendicular axis to this face: id, r_90°, r_180°, and r_270° ⇒ |stab_G(x)| = 4 ⇒ [The orbit-stabilizer theorem] |G| = |orb_G(x)|·|stab_G(x)| = 6·4 = 24 (Figure A).

    

2. Let’s consider |X_id| = 3⁶ where 3 is the number of colors available, and 6 faces of the cube.

3. Let’s consider a rotation about the vertical axis (Figure b). Let’s think of the rotation by 90° clockwise or counterclockwise, what does this rotation fix? Suppose that the face shown in b.1 is red, the face on the left would be rotated to the red face, so obviously the face on the left has to be red in the first place (figure b.2). Using the same argument, all four lateral faces of the cube must also share the same color, so there are 3³ possibilities (3² because there are no restriction on the top and bottom faces and 3 for the shared color of the four lateral faces.) Futhermore, there are three axes (figure b.3), and for each one of them, we can rotate 90° either clockwise or anticlockwise, so we need to count this 6 times.

    

4. If we consider the same three axis, we need to consider the 180° rotation, but in this case we have more choices, because there are no restriction on the top and bottom faces, but we can also choose two different colors for two of the four lateral faces, therefore there are 3⁴ possibilities (top + bottom + 2 laterals), and there are three of those 180° rotations.

5. Let’s take into account the eight rotations about the long diagonal by 120° (figure c). Faces around vertices where the rotation axis crosses need to be of the same color in order to be fixed (figure c, the faces 1, 2 and 3 need to be of the same color, as well as 4, 5, and 6), so there are only 3² possibilities, one color for each vertex.

    

6. Finally, we need to consider the six rotations passing through each pair of opposites edges (Figure D). We can chose the color for three of the faces, so there are 3³ possibilities.

k = [Burnside’s Theorem, a = 4] $\frac{1}{|G|}\sum_{g∈G}|X_g| = \frac{1}{24}(3^6+6·3^3+3·3^4+8·3^2+6·3^3)=\frac{1368}{24}=57.$

Bibliography

1. NPTEL-NOC IITM, Introduction to Galois Theory.
2. Algebra, Second Edition, by Michael Artin.
3. LibreTexts, Abstract and Geometric Algebra, Abstract Algebra: Theory and Applications (Judson).
4. Field and Galois Theory, by Patrick Morandi. Springer.
5. Michael Penn (Abstract Algebra), and MathMajor.
6. Contemporary Abstract Algebra, Joseph, A. Gallian.
7. Andrew Misseldine: College Algebra and Abstract Algebra.