\documentclass[12pt]{article}
 \usepackage[top=2cm, bottom=2cm, left=2cm, right=2cm]{geometry} 
\usepackage{graphicx}
\usepackage{amssymb}
\usepackage{cite}

\usepackage{amsmath}
\usepackage{lgarron}
\usepackage{subfig}
\usepackage{hyperref}

\usepackage{fancyhdr}
\pagestyle{fancy}

\newtheorem{outl}{Outline Content}
\newtheorem{idea}{Idea}
\newtheorem{proposition}{Proposition}

\newcommand{\e}[1]{{\bf{#1}}}


\begin{document} 

\title{An Introduction to Group Theory and the Rubik's Cube}
\author{Lucas Garron}
\maketitle

\begin{center}
\includegraphics[width=60mm]{img/top_cube.png}
\end{center}

\section{Introduction and Motivation}

If you've done enough math or speedcubing, you've probably heard that the Rubik's Cube is a very useful example for studying the mathematical subject of \e{group theory}. The states of the Rubik's Cube form a \e{group}, which means that they satisfy certain properties; the Rubik's Cube is also moderately complicated, which means that a lot of parts of it have interesting properties that can be used to visualize important concepts in group theory. In particular, the Rubik's cube group also contains many \e{subgroups} that we can use to understand parts of the cube. This paper is intended to be a layman's informal introduction to the Rubik's Cube Group through a look at its subgroups. I am assuming that you have some experience with Rubik's Cubes and mathematical thinking, but I will try to assume little about what you actually know.


\section{Groups and the  Rubik's Cube}

\subsection{Groups}

\e{Groups} are not some esoteric and complicated mathematical concept; in fact, the reason gruop theory is so important is that many mathematical structures you might be familiar with are actually groups.

{\example ``The integers under addition'' is a description of a common group. Since the \e{set}\footnote{In mathematics, a \e{set} of objects is simply a collection of objects, often written like $\{2, 5, 20\}$ or $\{house, carrot, imagination\}$. It can be useful to think of it as a ``list of things'', except that the order doesn't matter -- something is either in a certain set or not. For example, $\{1, 2, 3\}$ and $\{3, 1, 2, 1\}$ are descriptions of the same set, because ``Is $X$ in the set?'' has the same answer for both sets, no matter what $X$ is. Sets can also be infinite and complicated, so that it wouldn't make sense to write them down -- which is why it's good to think of a set in terms of what's in them and what's not. For example, ``the set of prime numbers'' is infinite, but it's easy to tell whether something is in the set or not, assuming we can tell what a prime number is.} $\{..., -3, -2, -1, 0, 1, 2, 3, ...\}$ is sometimes called $\Z$, this group is often written as $(\Z, +)$.}\\

The fact that $(\Z, +)$ is a group means that it is possible to add integers to each other, and that addition in this sense is ``well-behaved''. Let's look at some examples:

\begin{itemize}
\item  If we add two integers, we always get another integer -- the integers are \e{closed} under addition. (If this seems to obvious, notice that $1/2$ is not an integer, so we would say the integers are not closed under division -- $(\Z, \div)$ is not a group.)
\item If we're adding $1+2+3$, it also doesn't make a difference whether we consider it $(1+2)+3$ or $1+(2+3)$ -- this is because the integers are \e{associative}.
\item In fact, it doesn't matter in what order we add two integers: $x+y = y+x$, no matter what integers $x$ and $y$ we pick -- the integers also happen to be \e{commutative}.
\item There is also a very important number in the integers: $0$. If we add $0$ to anything, we always get back the original number. $0$ is called the \e{identity}.
\item Every integer $x$ also has an \e{inverse} $-x$, and if we add them together we always get the identity: $0$.
\end{itemize}

Each of these properties might seem obvious, but addition would be more confusing if these properties were not true -- and in fact there are similar mathematical structures that don't have some of these properties. However, a group is a structure (a set with an operation) that has the following properties from above: \e{being closed, associative, having an identity, and having inverses}. Groups also may or may not be $commutative$.

{\definition A group $(G, \star)$ is a set $G$ with an operation $\star$, such that:
\begin{enumerate}
\item Identity: There is an element $e$ such that $e \star g = g \star e$ for every $e$ in $G$.
\item Closure: If $g$ and $h$ are both in $G$, then $g \star h$ is also in $G$
\item Inverses: If $g$ is in $G$, then there is some other element $h$ such that $g \star h = h \star g = e$. This value of $h$ is given the notation $g^{-1}$ (or $-g$, when $\star$ is addition).
\item Associativity: If we combine three elements $g, h,$ and $k$ (each in $G$, then $(g \star h) \star k$ is always the same as $g \star (h \star k)$
\end{enumerate}

If $g \star h = h \star g$ is true for any $g$ and $h$ in $G$, then the group is called \e{commutative} or \e{abelian}.
}\\

For the integers, we can see that $G = \Z$, $``\star" = ``+''$, and $e = 0$, making these statements agree with our earlier look at the integers.\\

There is also one more important concept which shows up commonly in the study of the cube: the \e{order} of a group or an element.

{\definition The \e{order} of a group $(G, \star)$ is the number of elements in $G$, written as $|G|$.}

{\definition The \e{order} of an element $g$ in a group $(G, \star)$ is the smallest number of times we have to repeat it to get back to the identity. If we write $\underbrace{g \star g \star ... \star g}_{n}$ as $g^n$, then the order of $g$ is the smallest positive integer $i$ such that $g^i = e$. We write the order of $g$ as $|g|$.}\\

(In case you're wondering, the reason that these definitions use the same word is that the \e{powers} $g^0, g^1, ...$ form a subgroup of of $G$ \e{generated} by $g$ which has the same order as $g$. This should become more clear when we define those terms below.)\\

It might be the case that an element doesn't have an order; for example, $1$ doesn't have an order in $(\Z, +)$; no multiple of $1$ is equal to $0$. In this case, we often say that the order of $1$ is infinite. However, the following is true:

{\theorem If $(G, \star)$ is a finite group (i.e. $G$ has only finitely many elements), then every element has an order.}\\

\e{Proof}: Since $G$ is finite, it can't be the case that $g^0, g^1, g^2, g^3, ...$ are all different, so there must be some element $g^i$ that is equal to another element $g^j$ that comes after it. Using some implicit, but hopefully logical, notation: $g^{-i}$ is the inverse of $g^i$, so we can ``unwind'' to show that $g^{j-i} = g^j g^{-i} = g^i g^{-i} = e$. Thus, $j-i$ (which is positive) is an upper bound for the order of $g$. It might be the order, or the order is some smaller number.

Since the Rubik's Cube has a finite number of states, this means that every algorithm has an order. For example $|R| = 4$. However, we're getting ahead of ourselves; to understand what this all should mean, let's take a look at the Rubik's Cube.

\begin{figure}[b]
	\centering 
  \subfloat[A Rubik's Cube in its unique solved state.]{\includegraphics[width=0.2\textwidth]{img/rubiks_cube.png}\label{cube:1}}
  \hspace{0.03\textwidth}
  \subfloat[A solved Rubik's Cube after one move performed on its right side: $R$.]{\includegraphics[width=0.2\textwidth]{img/rubiks_cube_turned.png}\label{cube:2}}
  \hspace{0.03\textwidth}
  \subfloat[An arbitrary arrangement of the cube, reached by performing successive turns.]{\includegraphics[width=0.2\textwidth]{img/rubiks_cube_wr_scramble.jpg}\label{cube:3}}
 \label{exp}
\end{figure}

\subsection{A Crash Course in Rubik's Cube Terminology and Notation}
A 3x3x3 Rubik's Cube has $26$ \e{cubies} with $54$ \e{stickers} on $6$ \e{faces} (9 stickers), which we call $\{$back, front, up, down, left, right$\}$, abbreviated respectively as $\{B,F,U,D,L,R\}$. Of these cubies, there are $8$ \e{edges}, $12$ \e{corners}, and $6$ \e{centers}. Each side is composed of $9$ ``cubies'' ($4$ edges, $4$ corners, and $1$ center).

A Rubik's Cube has $43252003274489856000$\footnote{It is an amusing curiosity that the number of \e{unsolved} states of the Rubik's Cube, 43252003274489855999, is a prime number, \href{http://games.groups.yahoo.com/group/speedsolvingrubikscube/message/36357}{as observed by Chris Hardwick and discussed in June of 2007}. By the prime number theorem, this is not particularly likely. I found this property to hold for the 3x3x3, 8x8x8, and 11x11x11 cube, but no others until 40x40x40.} distinct states that can be reached by performing moves on the sides of the cube.

If we look the side $R$ and turn it clockwise around the center, then this is also the move denoted $R$. If we turn it counter-clockwise, the move is $R'$, and if we turn it either way twice it is $R2$. Exactly the same holds for other sides in place of $R$. Note that ``do an $R$ move followed by a $U'$ move'' is traditionally denoted as $R\ U'$ when we are studying the cube. Such a move sequence is also called an \e{algorithm}. These definitions are contrary to mathematical convention, but they are clearly established for the study of the Rubik's Cube.

\subsection{The Rubik's Cube}
I stated earlier that the Rubik's Cube is a group. The states of a Rubik's cube are a set, which we'll call $G$ (and which has order $|G| = 43252003274489856000$). but if we want an operation $\star$, what should it in this case? How do you add two states? One reasonable suggestion might be to consider what happens if we perform some moves on a cube. Lets say we perform some algorithm $A$ that puts the cube into some state $X$, and another algorithm $B$ that puts the cube into state $Y$. It would be nice if ``$X \star Y$'' happened to be the state you get if you perform the algorithms after each other, $A\ B$. Since every position can be created by \e{some} sequence of moves, this allows us to assume that you can add any two positions, even if you don't know what moves might create those positions. It turns out that this exactly defines the group $(G, \star)$.

As with any such definition, we should check whether it is \e{well-defined}. There are multiple algorithms for each state, and it is not guaranteed that the definition always gives us the same ``sum''. To see why this is an issue, consider the algorithms $T_1 = \href{http://alg.garron.us/?alg=R_U_R-_U-_R-_F_R2_U-_R-_U-_R_U_R-_F-&name=T_Permutation_1&cube=4x4x4&notation=WCA}{R U R' U' R' F R2 U' R' U' R U R' F'}$ and $T_2 = \href{http://alg.garron.us/?alg=R2_U-_R2_U_R2_U_D-_R2_U_R2_U-_R2_D&name=T_Permutation_2&cube=4x4x4&notation=WCA}{R2 U' R2 U R2 U D' R2 U R2 U' R2 D}$ on the 4x4x4 cube. Both of these seem to be algorithms for the same state -- the so-called \e{T-Permutation}. Now consider the algorithm \href{http://alg.garron.us/?alg=r&name=Inner_Slice_Turn:_r&cube=4x4x4&notation=WCA}{$r$} (an inner layer), and what happens if we perform \href{http://alg.garron.us/?alg=r&name=Inner_Slice_Turn:_r&cube=4x4x4&notation=WCA}{$r$} followed by a T-Permutation: it matters which T-Permutation we use, because the center pieces are affected differently! $\href{http://alg.garron.us/?alg=(r)_(R_U_R-_U-_R-_F_R2_U-_R-_U-_R_U_R-_F-)&name=r_composed_with_T_Permutation_1&cube=4x4x4&notation=WCA}{r \star T_1} \!= \href{http://alg.garron.us/?alg=(r)_(R2_U-_R2_U_R2_U_D-_R2_U_R2_U-_R2_D)&name=r_composed_with_T_Permutation_2&cube=4x4x4&notation=WCA}{r \star T_2}$; the action is not \e{faithful} unless we can distinguish all the cubies, e.g. when the center cubies are labeled on a \e{supercube}. Therefore, the states of the 4x4x4 cube do not form a group unless we are careful about the definition of ``state''.

\begin{figure}[b]
	\centering 
  \subfloat[The result of either T-Permutation algorithm]{\includegraphics[width=0.2\textwidth]{img/s_T2.png}\label{cube:4}}
  \hspace{0.03\textwidth}
  \subfloat[The algorithm \href{http://alg.garron.us/?alg=r&name=Inner_Slice_Turn:_r&cube=4x4x4&notation=WCA}{r}]{\includegraphics[width=0.2\textwidth]{img/s_r.png}\label{cube:5}}
  \hspace{0.03\textwidth}
  \subfloat[The algorithm \href{http://alg.garron.us/?alg=(r)_(R_U_R-_U-_R-_F_R2_U-_R-_U-_R_U_R-_F-)&name=r_composed_with_T_Permutation_1&cube=4x4x4&notation=WCA}{(r) $\star$ (R U R' U' R' F R2 U' R' U' R U R' F')}]{\includegraphics[width=0.2\textwidth]{img/s_r_T1.png}\label{cube:6}}
  \hspace{0.03\textwidth}
  \subfloat[The algorithm \href{http://alg.garron.us/?alg=(r)_(R2_U-_R2_U_R2_U_D-_R2_U_R2_U-_R2_D)&name=r_composed_with_T_Permutation_2&cube=4x4x4&notation=WCA}{(r) $\star$ (R2 U' R2 U R2 U D' R2 U R2 U' R2 D)}]{\includegraphics[width=0.2\textwidth]{img/s_r_T2.png}\label{cube:7}}
 \label{exp}
\end{figure}

It turns out that this is not an issue on the 3x3x3 cube. This cube is small enough (each cubie) that it is possible to tell where every sticker in a state came from. Any algorithms for the same state move the stickers in the same \e{permutation}. Therefore, on a 3x3x3 cube it is justifiable to think of \href{http://alg.garron.us/?alg=R_U_R-_U-_R-_F_R2_U-_R-_U-_R_U_R-_F-&name=T_Permutation_1_(on_3x3x3)}{$R U R' U' R' F R2 U' R' U' R U R' F'$} and \href{http://alg.garron.us/?alg=R2_U-_R2_U_R2_U_D-_R2_U_R2_U-_R2_D&name=T_Permutation_2_(on_3x3x3)}{$R2 U' R2 U R2 U D' R2 U R2 U' R2 D$}, as well as the resulting state, all as representations of the T-Permutation. A \e{state} and an \e{algorithm} describe exactly the same thing, although there are only a finite number of states, and an infinite number of algorithms for each state. Both algorithms result in the same state starting from solved, and it is guaranteed that ``applying'' these algorithms to other states will always give the same result. In fact, we can omit the $\star$ symbol because composing moves by writing them one after the other is well-defined. In group theory, the operation of such a group (where we take an element and apply it to another one to get a new element) is often called a \e{composition}. This is why cube theorists sometimes use descriptions like ``the superflip position composed with four dots''. It is possible to think about cube moves mainly as permutations, but it is often nice to understand that we could always just ``do the moves'' because the cube is a group. For example, $R$ is a $1$-move algorithm, and $R\ R'$ is an alternate description for the solved state

Now, our definitions for the Rubik's Cube satisfy all the properties of a group:

\begin{itemize}
\item The set of elements, $G$, is simply the set of Rubik's Cube states (all of which which can be described by multiple algorithms), and $\star$ is composition
\item Identity: $e$ is the solved state. Composing the solved state with something is idempotent (it does nothing to the other state).
\item Closure: Two states can always be composed.
\item Inverses: Every state has an inverse. For example, the inverse of $(\href{http://alg.garron.us/?alg=R_U_R-_F-_U2}{R U R' F' U2})$ is $(\href{http://alg.garron.us/?alg=U2_F_R_U-_R-}{U2 F R U' R'})$. However, $(\href{http://alg.garron.us/?alg=L-_U-_L_F_U2}{L' U' L F U2})$ is also an inverse. Thus it must be the case that $(\href{http://alg.garron.us/?alg=R_U_R-_F-_U2}{R U R' F' U2}) = (\href{http://alg.garron.us/?alg=L-_U-_L_F_U2}{L' U' L F U2})$; both of these are descriptions of the inverse state.
\item Associativity: If we have compose three states as $A_1 A_2 A_3$, it makes no difference if we compute an algorithm for $A_2 A_3$ and apply it to $A_1$, or if we apply $A_3$ to an algorithm for $A_1$; the result is the same.
\end{itemize}


\begin{figure}[b]
	\centering 
  \subfloat[Labeled Stickers in a flattened view]{\includegraphics[width=0.5\textwidth]{img/gap_label.eps}\label{cube:8}} \label{exp}
\end{figure}

\subsection{Getting Specificational: Permutations}
Although it is good to establish the intuitive grounds behind the definitions, it is important to understand how puzzles like the Rubik's Cube are mathematically defined, and that is through permutations. A \e{permutation} is an operation that takes some arrangement elements, and shuffles them around. For example, when we scramble a Rubik's Cube we move its $26$ cubies around, and when we are done each cubie has moved to some new position (possibly the same). We say that our scramble \e{induces} a permutation on the cubies. Similarly, it induces a permutation on the stickers of the cube. Ignoring the centers of each side (because they never move), the Rubik's Cube has 48 stickers that can move. If we perform the move $R$, then the sticker at position $25$ moves to the one at position $27$, which moves to $32$, which moves to $30$, which moves back to $25$. This is called a \e{cycle} of stickers, and it would be written as $(25\ 27\ 32\ 30)$. It should make sense that every state can be described in terms of how it moves the stickers. For example, $R$ induces the permutation with the following \e{cycle structure}:

\[R = (25\ 27\ 32\ 30)(26\ 29\ 31\ 28)( 3\ 38\ 43\ 19)( 5\ 36\ 45\ 21)( 8\ 33\ 48\ 24)\]

We can figure out where any sticker goes by looking at the cycles: sticker $38$ moves to the position of sticker $43$; sticker $28$ to $26$ (since a cycle permutes the stickers in a loop), and sticker $20$ stays in place because it is not moved by any cycle. Instead of writing down the cycle structure, it would also have been useful to write down the actual \e{permutation map} $(1 \mapsto 1, 2 \mapsto 2, 3 \mapsto 38, 4 \mapsto 5, \mapsto 36, ...)$, or $\left(
\begin{array}{cccccc}
 1 & 2 & 3 & 4 & 5 & ... \\
 1 & 2 & 38 & 4 & 36 & ...
\end{array}
\right)$ that tells us where each sticker goes, but this takes up more space.

It should now make more sense to say what a state is: A state of the Rubik's Cube is a permutation of stickers. An algorithm that turns a solved cube into that state will induce exactly the same permutation of stickers. If we want to \e{compose two permutations}, we simply figure out where each sticker is moved by the first permutation, then where the new position of that sticker is moved by the second permutation. Thus, $R\ U$ is the state defined by the permutation that results when we compose $R$ with $U$ -- which exactly corresponds to how the stickers permute when we apply those two moves. However, we can now do something cooler: If we have two arbitrary states of the Rubik's Cube, we can compose them just by composing their successive permutations, without having to find an algorithm for either one! That we can \emph{also} do this through algorithms (such that the answer is well-defined) comes from the fact that an algorithm is really just an explicit composition of the permutations that are basic moves of the Rubik's Cube.

To be precise, the permutations of the stickers are not the Rubik's Cube group; instead, the Rubik's Cube group \e{acts} on the set of stickers, and the permutations of this \e{group action} give us full information about the Rubik's Cube group.

\section{Subgroups}
A subgroup is simply a group that is contained in another group. We can use the definition of a group to find out the criteria for a subgroup.

{\definition $(H, \star)$ is a subgroup of $(G, \star)$ if $H$ is a subset of $G$ (that is, all the elements of $H$ are also in $G$), and the following are true:
\begin{itemize}
\item $e$ is in $H$, since every group must have an identity, and $e$ is the only candidate in $G$
\item $H$ is closed: if $h_1$ and $h_2$ are in $H$, then $h_1 \star h_2$ must also be in $H$ for $H$ to be a group.
\item $H$ has inverses: for any $h$ in $H$, the inverse of $h$ must also be. Else, again, the corresponding condition of a group is violated.
\item The elements of $H$ are associative: This is automatically true, since 
\end{itemize}
}

{\proposition If $R$ is in a certain subgroup of the Rubik's Cube, so are $R2$ and $R'$.}\\

\e{Proof}: Since a subgroup is closed, $R \star R = R2$ must also be in the group. The inverse, $R'$, must also be in the group.\\

What if we consider a subgroup containing both $R$ and $U$? It must be the case that $R2$ and $R'$ are in the subgroup, as well as $R\ U$ and $U'\ R2$... In fact, any algorithm composed of $U$-turns and $R$-turns must be in the subgroup. There may be other states in the subgroup (we didn't say $L$ is not in the group), but there are at least some elements that must be guaranteed to be in such a subgroup. In fact, mathematicians have a name for ``the smallest subgroup containing $R$ and $U$''; it is called ``the subgroup \e{generated by} $R$ and $U$''.

{\definition Given a set of elements of a group $G$ (e.g. cube states) $g_1, g_2, g_3, ...$, the smallest subgroup containing all these elements is denoted $\langle g_1, g_2, g_3, ... \rangle$. Such a subgroup always exists.}\\

\e{Proof}: Note that such a set is always guaranteed to exist, since $G$ is such a set. However, it is not immediate that this set is a subgroup. However, let's consider all subgroups that contain $g_1, g_2, g_3, ...$. There must be some minimum set that they all contain (their \e{intersection}); let's call it $X$. If we go through the conditions of a group again, we can show that $X$ must be a group:

\begin{itemize}
\item $X$ contains the identity, since it is an element of all these subgroups.
\item $X$ is closed: If $g$ and $h$ are in $X$, they are in every one of these subgroups, as is $g \star h$
\item $X$ contains the inverses of all its elements. Similarly, if $g$ is in $X$, it is in all these subgroup, as is $g\i$ -- thus $g\i$ is in $X$.
\item $X$ is obviously associative, since the original group was.
\end{itemize}

Thus, by definition, $X$ ``forces'' itself to be a group, and it is unambiguous. to refer to a subgroup generated by any arbitrary elements.

{\theorem Any subgroup can be written using generators.}\\

\e{Proof}: If we take a subgroup, and consider the subgroup generated by its elements, we obviously get\ldots itself. There may be a shorter representation, but there is guaranteed to be a presentation using generators.

\subsection{Examples of Rubik's Cube Subgroups} 

Here are some examples of subgroups of the cube:

\begin{itemize}
\item Cubers will be familiar with $\langle R, U \rangle$ as a \e{two-gen} subgroup.
\item The so-called \e{PLLs} (Permutations of the Last Layer, preserving sticker orientation) form a subgroup. It can be written as $\langle\ \href{http://alg.garron.us/?alg=U&name=U&stage=PLL}{U}\ ,\ \href{http://alg.garron.us/?alg=R-_U_R-_U-_R-_U-_R-_U_R_U_R2&name=Ub_Permutation&stage=PLL}{R' U R' U' R' U' R' U R U R2}\ ,\ \href{http://alg.garron.us/?alg=R_B-_R_F2_R-_B_R_F2_R2&name=Ab_Permutation&stage=PLL}{R B' R F2 R' B R F2 R2}\ \rangle$, which might be characterized as ``the PLLs are generated by $U$, the $Ub$-Permutation, and the $Ab$-Permutation''. (If you have a cube in front of you, try it out! Set up an arbitrary PLL and check that it can be solved by \href{http://www.speedsolving.com/wiki/index.php/PLL#U_Permutation_:_b}{$Ub$} and \href{http://www.speedsolving.com/wiki/index.php/PLL#A_Permutation_:_b}{$Ab$} and AUFs ($U$-turns).)

\item $\langle e \rangle$ is the \e{trivial subgroup}. It might seem silly, but it it is good to know by name. For example, the trivial subgroup is a subgroup of every other subgroup.

\item Every valid state of the Rubik's Cube can be reached by turning the six sides. Thus, $G = \langle B, F, U, D, L, R\rangle$.

\item It is possible to generate any move using the $5$ others, as with $\href{http://alg.garron.us/?alg=D&name=D_turn}{D} = \href{http://alg.garron.us/?alg=(L-_R_F2_B2_L-_R)_U_(L-_R_F2_B2_L-_R)&name=D_turn_without_D}{(L' R F2 B2 L' R) U (L' R F2 B2 L' R)}$. Thus, it is also true that $G = \langle B, F, U, L, R\rangle$, since any state has algorithm using all six generators that can be rewritten by replacing $D$ using that algorithm. Informally, we might say that the cube is \e{five-gen}.

\item It is a little-known fact (among cubers) that the entire Rubik's Cube Group is actually two-gen. For example, $G = \langle \href{http://alg.garron.us/?alg=U_B_L_U_L-_U-_B-}{U B L U L' U' B'}\ ,\ \href{http://alg.garron.us/?alg=R2_F_L_D-_R-}{R2 F L D' R'}\rangle$. There are some interesting properties which were discussed \href{http://www.speedsolving.com/forum/showthread.php?19751-The-entire-cube-is-2-gen!}{on the speedsolving.com forum in March 2010}. In particular, Tom Rokicki found that if you take \e{any} two random states of the cube, there is about a $50\%$ chance that these two states generate the entire group. It is also possible to generate the cube using two elements of orders as low as $2$ and $4$; this demonstrates how easily two algorithms can ``tangle''.

\item If we take any state $X$ of the Rubik's Cube, then $\langle X \rangle$ is a subgroup. Notice that it is always commutative, since all the elements can be written as $X^i$ for some integer $i$, and that $|X| = |\langle X \rangle|$. It is sometimes unclear to cubers that repeating an algorithm repeatedly will always return to the original state, but this is a simple fact from a group-theoretic perspective.

We can ask what possible subgroups we can get from this, and the most important question to answer is what possible orders subgroups generated by one element can have (note from above that two elements can already generate the entire group). By analyzing all possible cycle decompositions of states, we can show that there are $73$ possible orders:

\[\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 18, 20, 21, 22,\]
\[24, 28, 30, 33, 35, 36, 40, 42, 44, 45, 48, 55, 56, 60, 63, 66, 70, 72,\]
\[77, 80, 84, 90, 99, 105, 110, 112, 120, 126, 132, 140, 144, 154, 165, 168, 180, 198,\]
\[210, 231, 240, 252,280, 315, 330, 336, 360, 420, 462, 495, 504, 630, 720, 840, 990, 1260\}\]

The solved state is obviously the only state with order $1$. There are many states with order 1260, such as $\href{http://alg.garron.us/?alg=(R_F2_B-_U_B-)1260&name=An_algorithm_of_order_1260}{R F2 B' U B'}$. There was a discussion in \href{
http://www.speedsolving.com/forum/showthread.php?23185-Possible-orders-of-Rubik-s-Cube-positions
}{August 2010} that covers a little more of this. It is also known how many states of each order, \href{http://www.jaapsch.net/puzzles/cubic3.htm#p35}{as reported in the Cubic Circular by David Singmaster in 1982}, but the combinatorics behind this are more complicated.

\item \e{Sylow Subgroups} are important subgroups of any group. The order of the Rubik's Cube factors as:

\[|G| = 43252003274489856000 = 2^{27} \* 3^{14} \* 5^{3} \* 7^{2} \* 11^{1}\]

One of the Sylow's theorems states that $G$ contains certain Sylow subgroups of each of the following orders: $2^27$, $3^14$, $5^3$, $7^2$, $11^1$, and that the Sylow subgroups of any given order are all ``similar'' in an important sense (they are \e{conjugate}). I \href{http://www.speedsolving.com/forum/showthread.php?20018-Sylow-Subgroups-of-the-Cube-Group}{constructed explicit generators} for these groups in March 2010.

\end{itemize}


\end{document}