Note 2

Subgroups #

In the previous reading, we mentioned that one of the goals of the class is to get you to not only solve the Rubik’s Cube but to understand the underlying structure behind the cube. For instance, try solving the cube after twisting one corner. This position is unsolvable. Why is this?

To understand this phenomenon, we first need to understand the idea of a subgroup. If you think of a group as a large collection of objects, a subgroup is a portion of those objects that form a group on its own.

Definition #

More formally, we write a subgroup $(H, *)$ of $(G, *)$ using $H \leq G$, where $*$ is the binary operation shared between the groups. $H$ is a subset of $G$, meaning all elements of $H$ are contained in $G$, but all elements of G are not necessarily in $H$. A subgroup has to satisfy the following conditions

  1. $H \neq \emptyset,$ meaning $H$ cannot be empty
  2. $H$ is closed under *. If $x$ and $y$ are elements of H, $x * y$ is also an element of $H$
  3. Any element $x$ of $H$ has an inverse $x^{-1}$ in $H$ such that $x * x^{-1} = x^{-1} * x = e$

Although this may seem rather silly, we will observe that subgroups are a key aspect of groups which allow us to isolate areas of groups and investigate them without having to worry about other irrelevant elements of the group. For instance, suppose you wanted to solve the Rubik’s Cube while only using the moves R, U and their inverses. This group actually forms a subgroup of the Rubik’s Cube group! Try and verify it after reading through the examples.

Examples #

Let’s consider the group $(\mathbb{R}, +)$, the additive group of real numbers. Is $(\mathbb{Z}, +)$ a subgroup of $(\mathbb{R}, +)$?

  1. $\mathbb{Z}$ is a subset of $\mathbb{R}$, and $\mathbb{Z}$ is not empty, so the first condition is satisfied

  2. Addition is closed over the integers - if I add two integers, I get an integer, so the second condition is satisfied

  3. And finally, any integer $a$ has an inverse $-a$ such that $a + (-a) = 0$, and $-a$ is also an integer, so the third condition is satisfied

So, $(\mathbb{Z}, +)$ forms a subgroup! How about the other way around, is $(\mathbb{R}, +)$ a subgroup of $(\mathbb{Z}, +)$? Well, no because the real numbers are not a subset of the integers - not all real numbers are integers.

Let’s try a proof! Consider a group $(G, *)$. Does the group $H = G$ form a subgroup of $G$?

  1. Any element in H is also an element in G, since they are equal, and H is not empty, so the first condition is satisfied
  2. Consider two elements $a, b$ in $H$. $a * b$ is in $G$, since $(G, *)$ forms a group. Since $G = H$, $a * b$ is also in $H$!
  3. An element $a$ in $H$ has an inverse $a^{-1}$ in $G$, since $G$ forms a group. Furthermore, $a^{-1}$ is also in $H$, since $G = H$.

And so, $H$ forms a subgroup of $G$! Here’s something for you to try. Consider a group $(G, *)$ and its identity $e$. Does $({e}, *)$ form a subgroup of $G$?

Generators #

When introducing subgroups, we talked about the group of Rubik’s cube states only accessible through R and U moves. This actually turns out to be a useful concept which merits its own name. In particular, if we can write all elements of a group $G$ using a subset of the group elements $S$ and their inverses, then we say that $S$ is a set of generators of $G$, or that $S$ generates $G.$ This is notated using $G = \left<S\right>.$

For instance, the Rubik’s Cube group, which consists of all possible combinations of the cube, is preposterously large and complex. However, we know that every valid arrangement of the cube comes about from manipulating the cube using the $6$ basic moves. Hence, we conclude that $\{$U, R, F, L, B, D$\}$ generates the Rubik’s Cube group. We are able to break down the complexity of the Rubik’s Cube puzzle by expressing each of its elements as a combination of the 6 generating elements.

Order #

Just how complex is the Rubik’s Cube? Can we measure that? We can do so using the notion of order. For a group $G$, the order of $G$, also given by $|G|$, is defined by the number of elements in $G$. Order effectively describes the size of the group. For instance, the order of the Rubik’s Cube group is the number of combinations possible on the Rubik’s Cube. While calculating this is nontrivial, using combinatorics one can find this order is $\frac{8!\cdot3^8\cdot 12!\cdot 2^{12}}{3 \cdot 2 \cdot 2}.$

There exists a similar idea of order for group elements. For an element $a$, we define the order of $a$, notated as $|a|$, to be the smallest positive integer $m$ such that $$a^m = \underbrace{a\cdot a \cdot \ldots \cdot a}_{m\ \text{times}} = e.$$ This is equivalent to the order of the subgroup generated by $a$, or $|a| = |\left<a\right>|.$ For instance, consider the move U on the Rubik’s Cube. Starting from a solved cube, how many times must this move be repeated before we end up with a solved cube? The answer is 4. This implies the order of U is 4.

Lagrange’s Theorem #

Now that we have covered the concepts of order and subgroups, we can now discuss Langrange’s theorem, one of the most consequential results in group theory.

Simplified Theorem Statement #

Suppose $G$ is a group and $H$ is a subgroup of $G$. Then the order of $|H|$ divides the order of $|G|.$

This is an important result since it shows that information about a subgroup tells us something about the group and vise versa. Suppose you had a group with order $|G| = 77.$ Then you can conclude any subgroup $H\leq G$ must have order $1, 7,$ or $77.$

The full theorem statement actually outlines what the quotient is after dividing, but we’re not going to describe that in this reading.

Examples #

The order of the Rubik’s Cube group is $43,252,003,274,489,856,000$. The three zeros at the end tell us that the Rubik’s Cube group can have an order of $100$.