Group Theory

Group theory is a branch of theoretical mathematics that can be used to describe the way the functioning of the Rubik's Cube and various related puzzles. Although pure group theory can get extremely complicated (there is one proof, a classification of what are known as simple groups, which took an estimated tens of thousands of pages in its first incarnation) there are several simple applications of group theory to twisty puzzles.

First, we should explain what a group is. A group is nothing more than a set of elements and some binary operation on those elements; so we could make a group out of the set of integers and the operation +. Generally people describe a group just as the set of elements, since the operation is usually obvious from context. A group also has to satisfy several properties:
- Closure: Whenever we apply the operation to two elements in our group, the result is an element in the group.
- Associativity: If a, b, and c are in the group, and * is our operation, then (a * b) * c and a * (b * c) are always the same thing. This means that we can write things like a * b * c * a * c without needing large numbers of parentheses, which is very convenient.
- Identity: There is some identity element, so that if we apply the operation to the identity element and any element a the result will just be a again.
- Inverse: Every element has an inverse in the group, so that if you apply the operation to the element and its inverse it becomes the identity.

This is a pretty abstract concept, but fortunately it isn't too difficult to use. Basically, each puzzle has one group, with the elements being the puzzle's possible positions. Our operation is composition. Basically, suppose we have two elements in the group, A and B. Then A * B is what you get when you take the moves you would use to reach B from a solved cube, and apply them to A instead of a solved cube. This is a very simple and useful operation for several reasons. First, the identity is the solved state, which is easy to work with. Second, if we define a set of basic moves (for example F, R, U, B, L, and D, and their inverses, for a 3x3x3) we can get to every position from the identity using some sequence of these moves, which means that every element in the group can be written as some sequence like F * B * L inverse * D * D, and we can even describe positions by the way that they can be written like this. Third, the inverse of a position is also easy to find: group theory tells us that the inverse of A * B * ... * Z is Z inverse * .... * B inverse * A inverse. Since the inverse of basic moves are basic moves, we can very easily find the inverse of a certain position by just switching the order of the basic moves that bring you to that position and then inverting each one of them. Note that the inverse of the inverse of any position P is just P again.

By the way, since the operation * is always implied, we often write a series of moves in what is called multiplicative notation, where we write the separate moves next to each other without a *, and use exponents (like in algebra) to indicate doing something multiple times or inverting it. This means that we would write something like F B L^-1 D^2 instead of F * B * L inverse * D * D. This is the origin of our modern notational system, which has been simplified so that the inverse sign (which normally looks like a superscript "-1") is changed to a ' and the square sign (a superscript "2") is changed to a normal 2. I believe it was David Singmaster who created the modern Rubik's Cube notation this way. As for my notation system, it works just like this, but includes many more basic moves so that sequences of moves can be written more succinctly.

Along with the concept of a group comes the idea of a subgroup. A subgroup is what you get when you find a normal group and create another group with the same operation but only some of the elements. Because puzzle groups are only finitely large, it turns out that all you need to check to make sure a subgroup is valid is closure, so it's easy to find subgroups. Note that a subgroup always has to contain the identity (solved state). Since we always use the same operation, you can think of a subgroup as basically describing a sub-puzzle of a normal puzzle. A few interesting subgroups of the 3x3x3 are:
- The "two-generator" subgroup, all positions which can be solved using only R and U turns;
- The orientation-only subgroup, positions where all pieces are in place, but can have any orientation;
- The half turn subgroup or square group, positions that can be solved using only 180-degree turns.

The concept of a subgroup is closely tied in with the idea of a generator. A generator for a group is a set of moves or algorithms in that group, so that you can reach any position in the group only using moves or algorithms from that set (or their inverses). * For a given set of moves, there is always some group that is generated by them, that is, some group that contains exactly the positions that you can reach using those moves (in some order and doing them as many times as you want). For any set of moves, say the set R, U, and F2, we write the group generated by them as <R,U,F2>. One particularly famous generated group is a subgroup which we have already discussed: the subgroup of 3x3x3 positions which can be solved using only R and U turns. This is known as the 2-generator group, since it is <R,U>, the group generated by moves of two adjacent faces. Playing with generators can create a lot of new and interesting challenges out of a normally non-challenging puzzle.

Another useful result of group theory is the use of so-called "cycle notation". Imagine a group where, instead of a normal puzzle, you have a bunch of pieces labeled 1 through n, and you can put them in any order (permutation) you want. We can still use the composition operation for this group, and it works a lot like the puzzle groups we have looked at. The question is: how do we represent objects in this group? What we will do is represent a permutation by following where pieces go. Give each piece a spot, labeled 1 through n, which represents its original location; so we can write down a permutation by writing the list of numbers we see, following the locations from 1 to n. So if we have five pieces and the permutation leaves them looking like "3 4 2 1 5" we can use this to represent the permutation. There is a better way, though: instead of just looking at each piece, follow where pieces are actually sent. In this case, the piece that was at position 1 is now at position 4; the piece at position 4 is now at position 2; the piece at position 2 is now at position 3; and the piece at position 3 is now at position 1. We can encode all of this information by writing (1 4 2 3). This is what we call a cycle, and we can imagine making this permutation by simultaneously moving all of the pieces in it to the location where it will go. More specifically this is a 4-cycle, because it has 4 elements. Now what about the piece at position 5? It's still there, and although we could write this as a 1-cycle we usually do not, because that piece doesn't have to move at all. This is really useful, because (1 4 2 3) is a valid permutation for ANY number of pieces, as long as you have at least 4 of them! If we have more than one cycle at the same time, we can write them by writing them next to each other. So if 1 goes to 2 and 2 goes to 1, and 3 goes to 4 and 4 goes to 3, we will write this as (1 2)(3 4).

We call a cycle with n elements an n-cycle. In puzzles we usually consider permutations on the pieces of the puzzle. Because of some more complicated math that will be discussed later, the basic unit that you can use to solve puzzles is the 3-cycle, which moves three pieces around. You may already know a few 3-cycles of pieces on the 3x3x3. Permutations of the pieces, however, is very important in the study of how to solve puzzles, as well as integral to blindfold solving.

There are two last useful mathematical terms which are very useful to understand cubing. They are conjugation and commutation. In conjugation you take two move sequences, which we will call X and Y, and then you make the sequence X Y X^-1. The interesting thing about this is that we end up with the same cycles as in Y, just with different pieces being moved around. You can use this to make other algorithms out of a given one, because the pieces that are moved in the conjugated algorithm are actually the pieces that X puts in the spots Y moves around. Commutation is similar: for two move sequences X and Y the commutator is X Y X^-1 Y^-1. In theory this can make many of the cube's possible patterns, but in practice we mostly use commutators to create nice 3-cycle maneuvers, or to flip/twist two pieces on a puzzle. The way it works is this: have X be a single turn, and then choose Y so that it modifies just one piece on the layer. If Y flips or twists the piece, you will end up with one piece in X's layer flipped/twisted and another flipped/twisted the same amount in the opposite direction. If Y replaces the piece with some piece from another layer, you will end up with a 3-cycle. The really useful thing about commutators is that if you understand them well enough you can literally make up commutators quickly while you are solving a puzzle, and do any 3-cycle you want in just a few seconds.

Well, those are most of the group theory topics you are likely to see. I've tried to explain them simply, but if you don't understand you can look them up on Wikipedia or look for a topic on the speedsolving.com forum. Again, good luck!