“An expert is someone who knows some of the worst mistakes that can be made in his subject, and how to avoid them.”
Heisenberg, Werner
PHYSICS AND BEYOND, 1971

This post shall survey, without proofs, some results on the group-theoretical structure of some of the permutation puzzle groups. We shall follow [GT] (see also [B], chapter 2, [NST], chapter 19) in our discussion of the pyraminx (tetrahedron), the 3×3 Rubik’s cube, and the megaminx (dodecahedron). Other puzzle groups are analyzed in [GT]. (Remember, all reference items can be found at the end of the introduction post.)

Notation: Let

* Gp (resp., GR, Gm) denote the permutation puzzle group generated by the basic moves of the pyraminx (resp., the Rubik’s cube, megaminx),

* Vp (resp., VR, Vm) denote the set of vertex pieces of the pyraminx (resp., the Rubik’s cube, megaminx),

* Ep (resp., ER, Em) denote the set of edge pieces of the pyraminx (resp., the Rubik’s cube, megaminx),

* Fp (resp., FR, Fm) denote the set of facets of the movable pieces of the pyraminx (resp., the Rubik’s cube, megaminx).

General remarks

Let G,V,E,F (resp.) denote either (Gp,Ep,Vp,Fp), (GR,ER,VR,FR), or (Gm,Em,Vm,Fm).

Lemma: G acts on the sets V, E, F (individually).

If g is any move in G then, since g acts on the sets V, E, and F, we may regard g

       as an element of the symmetric group S_V of V, 
       as an element of the symmetric group S_E of E, or
       as an element of the symmetric group S_F of F. 

These groups S_V, S_E, and S_F are different, so to distinguish these three ways of regarding g, let us write

         g_V for the element of S_V corresponding to g,
         g_E for the element of S_E corresponding to g,
         g_F for the element of S_F corresponding to g.

Lemma: (a) The function

                       f_V : G   -->  S_V
                             g  |-->  g_V

is a homomorphism.
(b) The function

                       f_E : G   -->  S_E
                             g  |-->  g_E

is a homomorphism.
(c) The function

                       f_F : G   -->  S_F
                             g  |-->  g_F

is a homomorphism.

What is the kernel of f_V? What is its image? To answer this question (actually, we shall not answer this precise question but one similar to it) we introduce a subgroup of the symmetric group.

Definition: Let S_X denote the symmetric group of a finite set X. Label the elements of X as X = { x1, x2, …, xn } and, using this labeling, identify S_X with Sn. Let A_X denote the set of all permutations of X which are even as an element of Sn (in the sense of chapter 2 above). This set is called the alternating group of X.

Lemma: The alternating group is a group.

Aside: The following remarkable result about the alternating group will not be needed but it is (believe it or not) connected with the fact that you cannot solve the general polynomial of degree 5 or higher using radicals.

Theorem: If X has 5 elements or greater then A_X has no non-trivial proper normal subgroups. In other words, if H <| A_X then either H = {1} or H = A_X.

end aside.

Parity conditions:

Consider the function

                       f_VE : G   -->   S_VxS_E
                              g  |-->  (g_V,g_E)

It is easy to check that this is a homomorphism.

Theorem: The image f_VE(G) of f_VE is isomorphic to

     /    A_VxA_E,           for the pyraminx or megaminx,
     |
     \ { (x,y) in S_VxS_E | x,y are both even or both odd },   for Rubik's cube.

To see what this means, we look at an example.

Example: Let G=GR. Can you find a move of the Rubik’s cube which flips a single edge subcube over, leaving the rest of the puzzle pieces unmoved? If so, then the image of f_EV would have to contain an element (x,y) with x=1 (since moving an edge only does not effect the vertices) and where y is a 2-cycle. But x=1 is even and a 2-cycle is odd. This contradicts the theorem, which says that x,y are either both even or both odd. Therefore, the answer is no: a single edge flip is impossible. (Incidentally, this is well-known to cube experts.)

Exercise: Is there a move on the Rubik’s cube which flips two corner subcubes over, without rotation (so it is a 2-cycle on the edges connected to the corner vertices being swapped), leaving the rest of the puzzle pieces unmoved?

Next, some more notation: let

                    K = ker(f_VE) < G       

denote the kernel of f_VE. This is a normal subgroup of G.

Example: In the case of the Rubik’s cube, this is the set of moves which may reorient (i.e., flip or rotate) a subcube but does not swap it with some other subcube. For example, the move

((D^2)^R*(U^2)^B)^2,

which twists the ufr corner clockwise and the bld corner counterclockwise, belongs to K. (Here x^y = y^(-1)*x*y, x^2=x*x.)

Theorem: G is a semi-direct product of K with f_VE(G):

                   G = K |x f_VE(G).

This is the desired determination of the structure of the permutation puzzle group. In the case of the 3×3 Rubik’s cube, some sketchy details are given in the next chapter. See also [GT] or [NST] chapter 19.