Where to begin.

Speaking personally, I am always fascinated to discover that one topic is connected in a surprising way with another completely dierent topic. The Rubiks Cube, a mechanical toy that has a reasonably ecient solution using pure mathematics (and no strategy), is a case in point. Its dicult to know where to begin to explain this connection: as Wodehouses character Bertie Wooster said, I dont know if you have the same experience, but the snag I come up against when Im telling a story is the dashed dicult problem of where to begin it. Lets begin with Rubik himself. Erno Rubik was born in the air-raid shelter of a Budapest hospital during World War II. His mother was a published poet, his father an aircraft engineer who started a company to build gliders. Rubik himself, far from being a mathematician, studied architecture and design at the Academy of Applied Arts and Design, remaining there as a professor, teaching interior design. In the mid1970s, he patented a cube-shaped mechanical puzzle that has since captured the imagination of millions of people worldwide. The Rubiks Cube was born. By 1982, Rubiks Cube was a household term, and became part of the Oxford English Dictionary. More than 100 million cubes have been sold worldwide. About 150 years earlier, in the late 1820s and early 1830s, a French teenager named Evariste Galois developed a new branch of mathematics: group theory was born from his attempts to understand the solvability of polynomial equations. In high school, students learn that x= b b2 4ac 2a
are the roots of the quadratic equation ax2 + bx + c = 0. There are similar but more complicated formulas for the cubic and quartic polynomials discovered during the Middle Ages (see, for example, [JKT] for more details). His work on group theory was motivated by what was perhaps the main unsolved mathematical problem of the day: does there exist an analogous algebraic formula involving radicals only in the coecients for an equation of fth degree or higher? This problem had remained unsolved for centuries despite the eorts of the best and brightest mathematical minds. Galois ideas succeeded where others had failed (although one must give credit to Runi and Abel here as well). Like Rubik, Galois life story is also interesting (see, for example, Calinger [Ca] xvii
and the article by Rothman [Ro]) and we shall read more of him later in this book. Groups measure symmetry. (Galois, for example, studied the symmetry group of the roots of a polynomial, now called Galois groups.) As the mathematician Hermann Weyl said in his wonderful book [We], symmetry is one idea by which man has tried throughout the ages to comprehend and create order, beauty, and perfection. Groups play a key role in the study of roots of polynomials, crystallography, elementary particle physics, campanology (or bell-ringing; see chapter 3 below), cryptography, and the Rubiks Cube, among others. Surprisingly enough, it turns out that it is possible to use group theory (and only the group-theoretical denition of the cube no knowledge of strategy or special moves) to solve the Rubiks Cube (see 10.2 below). This book will develop the basics of group theory and create group-theoretical models of Rubiks Cube-like puzzles. On the practical side, I also discuss the solution strategy for the Rubiks Cube in some detail. (For those wanting to see a solution strategy now, see section 15.1.) Some solution strategies are briey discussed for similar puzzles (the 15 Puzzle, the Rubik tetrahedron or Pyraminx, the Rubik dodecahedron or Megaminx, the Skewb, the Hockeypuck, and the Masterball) as well. The important point to remember, though, is that group theory is a powerful tool with many real-world applications. Solving puzzles happens to be just one of them. Because of our Rubiks Cube focus, the approach in this book is dierent from some texts: (a) there are a lot of non-standard, though relatively elementary, group theory topics; (b) I emphasize permutation groups via examples over general theory (such as Sylow theory); (c) I present some of the basic notions algorithmically (as in [Bu]); and (d) I include material which is interesting, from both the mathematical and puzzlists perspective, while keeping the level as low as possible for as long as possible. Moreover, most group theory texts prove everything. Here a lot of statements are proven; sometimes only a hint or sketch is provided, and the proof is left to the interested reader; other statements are supported only by an example. When a proof is not provided, a reference for a proof in the literature is given. To keep things as clear as possible, the start of a proof is denoted Proof: and the end by. Ive used the number system where a result or example in section a.b has a labeling of the form a.b.c. Chapters 1, 2 and 3 give some basic mathematical background. Chapter 4 introduces some of the puzzles and some notation we use for them. Except for the chapter on solutions, chapter 15, the remaining chapters discuss these puzzles using group theory, graph theory, linear algebra, or automata (nite xviii

state machines) theory. While the earlier chapters can probably be followed by a good high school student, chapters 12 and 14 are relatively advanced. They are, in my opinion, the most interesting, and illustrate some remarkable ways in which the Rubiks Cube is connected with other branches of mathematics, which is a continuing source of my fascination with the subject. The last chapter, chapter 16, gives some indications of directions which werent pursued and the present state of our, or at least my own, ignorance in this area. As it only gives some of the problems and questions that I dont have the answer to, it is not intended to be complete! A note to teachers: Based on my experience teaching at the U.S. Naval Academy, a reasonable semester course based on this book could aim for the First Fundamental Theorem of Cube Theory, in chapter 9, with lots of time for side trips and other material. It is possible to cover the Second Fundamental Theorem of Cube Theory, in chapter 11, in one semester but it is a race against time. For example, chapter 6 on Merlins Machine, or any uncovered sections, might be used for some very interesting term projects. A word about SAGE: New in this edition are numerous examples which use SAGE, a free and open-source computer algebra system. At the SAGE website (www.sagemath.org) there is ample documentation (a reference manual, tutorial, e-mail support lists, and so on) but it is worth taking some time here to explain how SAGE is used in this book. First, you dont have to know or care about SAGE to read the book. You may ignore the SAGE boxes if you wish. On the other hand, if you are fairly comfortable with computer software, the examples are added to help you relate to the constructions in a more interactive manner. There are two commonly used interfaces to SAGE: one is the command line (you type in a command and hit Enter to see the output) and the other is the graphical notebook interface (you type a command into a cell and hit Shift-Enter for the output). Since I prefer the command line, most examples are described that way. To keep publication costs down, SAGE plots and graphics are reproduced in greyscale in this book, though of course in SAGE they are in color.

Chapter 1

Elementary, my dear Watson
If logic is the hygiene of the mathematician, it is not his source of food; the great problems furnish the daily bread on which he thrives. Andr Weil, The future of mathematics, American Mathematical e Monthly, May 1950
Think of a scrambled Rubiks Cube as a car you want to x on your own. You not only need some tools but you need to know how to use them. This chapter, among others, provides you with some of the tools needed to get the job done. As one of our goals is to discuss the mathematics of the Rubiks Cube, and other games, we start with some fundamentals. The basic purpose of this chapter is to introduce standard set theory notation and some basic notions of mathematical logic. Logic and set theory are as basic to mathematics as light is to the real world. The background presented here hopefully will make some of the terminology and notation introduced later a little easier to follow for those who either havent seen or may have forgotten the mathematical notation. In any case, this is not intended to be a serious introduction to mathematical logic nor to set theory.

3.3. CYCLE NOTATION Note the manner of inputing a permutation such as (2, 4)(1, 3): rst you must dene the group G it belongs to (the SymmetricGroup(4) is SAGE notation for S4 , the permutations of {1, 2, 3, 4}), then enter (2, 4)(1, 3) as a list of disjoint cycles [(2, 4), (1, 3)] which are coerced into G using the command G([(2, 4), (1, 3)]). (More examples will be given below but you can also nd more details in the section Permutation group elements in the SAGE reference manual [S].) Ponderable 3.3.1. The disjoint cycle decomposition of (2, 3, 7)(3, 7, 10) is either (2, 3)(7, 10) or (2, 7)(3, 10). Which one is it? Ponderable 3.3.2. Divide a square into 4 subsquares (facets) and label them 1, 2, 3, 4. For example,

s 1 s 3 s

s 2 s 4 s
Let r denote counterclockwise rotation by 90 degrees. Then, as a permutation on the facets, r = (1, 3, 4, 2). Let fx denote reection about the horizonal line dividing the square in two, let fy denote reection about the vertical line dividing the square in two. Use the cycle notation to determine the permutations of the facets (a) r2 , (b) r3 , (c) fx , (d) fy , (e) fx rfx , (f ) fx fy. For those wanting to do this using SAGE, here is an example.
SAGE sage: G = SymmetricGroup(4) sage: r = G([(1,3,4,2)]); r (1,3,4,2) sage: r*r (1,4)(2,3)
This tells you that the answer to (a) is (1, 4)(2, 3).
3.3. CYCLE NOTATION Ponderable 3.3.3. Label the 24 facets of the 2 Rubiks Cube as follows:

1 U L D 9 F

13 R 17 B 20 18
(You may want to xerox this page and then cut this cube out and tape it together for this.) Let X denote rotation clockwise by 90 degrees of the face labeled x, where x {r, l, f, b, u, d} (so, for example, if x = f then X = F ). Use the cycle notation to determine the permutations of the facets given by (a) R, (b) L, (c) F , (d) B, (e) U , (f ) D. Lemma 3.3.3. A cyclic permutation is even if and only if the length of its cycle is odd. A general permutation f : Zn Zn is odd if and only if the number of cycles of even length in its disjoint cycle decomposition is odd. This follows from the denition of an even/odd permutation (see Denition 3.1.1), the fact that sign(p1 p2.pk ) = sign(p1 )sign(p2 ).sign(pk ), for permutations pi (because of Lemma 3.1.2), and the fact that any k-cycle can be written as a product of k 1 transpositions, (a1 , a2 ,., ak ) = (a1 , ak )(a1 , ak1 ).(a1 , a2 ). (3.1)
(Equation (3.1) can be proven by mathematical induction. The argument is left to the reader. For details, refer to the related results in chapter 1 of Rotman [R] or Theorem 3.3 in Gaglione [G], 3.2, for example.) 53
3.4. AN ALGORITHM TO LIST ALL THE PERMUTATIONS Lemma 3.3.4. The order of a permutation is the least common multiple (lcm) of the lengths r1 , r2 ,., rk of the disjoint cycles in its cycle decomposition. Example 3.3.2. The order of (1, 3)(2, 4) is 2. It is even. The order of (1, 3)(2, 4, 5) is 6. It is odd. Here is an example of using SAGE to compute with orders and signs of permutations.

3.5. PERMUTATIONS AND BELL RINGING It was a knowledge of the permutations in Kent Treble Bob Major, a ringing of eight bells, which helped Lord Peter Wimsey solve a murder mystery in Dorothy Sayers The Nine Tailors [Sa]. A good reference for this section is A. White [Wh].

Chapter 4

A procession of permutation puzzles
How can it be that mathematics, being after all a product of human thought independent of experience, is so admirably adapted to the objects of reality? Albert Einstein
I shall describe several permutation puzzles in this chapter. After presenting a lot of mathematics, we shall nally have a chance to have fun attacking some real puzzles! Though Einstein was talking about relativity in his quote, youll see for yourself how admirably adapted combinatorics (and later group theory) is to describing these puzzles. First, we nail down for the sake of discussion a denition of what a permutation puzzle is. A one-person game is a sequence of moves that follow certain rules: There are nitely many moves at each stage. There is a nite sequence of moves that yields a solution. There are no chance or random moves. There is complete information about each move. Each move depends only on the present position, not on the existence or non-existence of a certain previous move (such as chess, where castling is made illegal if the king has been moved previously). (The reader will nd a fascinating discussion of two-person games in the book by Berlekamp, Conway, and Guy [BCG].) A permutation puzzle is a one-person game with a nite set T of puzzle pieces satisfying the four properties listed below: 61
4.1. 15 PUZZLE (1) For some n > 1 depending only on the puzzles construction, each move of the puzzle corresponds to a unique permutation of the numbers in Zn. (2) If the permutation of Zn in (1) corresponds to more than one puzzle move, then the two positions reached by those two respective moves must be indistinguishable. (3) Each move, say M , must be invertible in the sense that there must exist another move, say M 1 , which restores the puzzle to the position it was at before M was performed. (4) If M1 is a move corresponding to a permutation f1 of T and if M2 is a move corresponding to a permutation f2 of T , then M1 M2 (the move M1 followed by the move M2 ) is either. not a legal move, or corresponds to the permutation f1 f2. Notation: As in step 4 above, we shall always write successive puzzle moves left-to-right.

This handy mnemonic device indicates that ij = k, since the ordering is consistent with the arrows, and ji = k, since the ordering is not consistent with the arrows. Though Hamilton discovered the quaternions (though Gauss may have known of them earlier), it may have been Cayley who rst noticed that the unit quaternions form a group.

Finite cyclic groups

Consider the set of Rubiks Cube moves G = {1, R, R2 , R3 }. We make several more or less obvious observations: If you make any other rotations of the right face of the cube you wont get any new moves, i.e., ones not already included G. In particular, if you compose any two moves in this set you get another move in this set. The move that undoes the eect of R is in this set (in fact, R followed by R3 is the identity move 1, so R3 must undo R). If : G G G is simply the map dened by sending a pair (Ri , Rj ), with 0 i, j 3, to the composition of these two moves, Ri Rj = Ri+j , then is a binary operation. It turns out that this set G with this operation is an example of a group. Example 5.2.1. Let C12 be the set whose elements are {0, 1,. , 11} and for which the group operation is simply addition mod 12. This is how one adds time on a clock (except that we call 12 oclock 0 oclock). Thus 5 + 8 = 1, 1 + 11 = 0, and so on. Questions: What is the (inverse) element that, when added to 5, gives you 0? What is the inverse element of 1? This group is called the cyclic group of order 12. 85
5.3. THE DIHEDRAL GROUP Denition 5.2.1. Let n > 1 be an integer and let Cn be the group whose elements are {0, 1,. , n 1} and for which the group operation is simply addition modulo n. This group is called the (additive) cyclic group of order n. It is oftentimes also denoted by Z/nZ. Geometrically, this may be regarded as the group of all possible rotations of a regular n-gon. This idea is explored in more detail in 5.3 below.

The dihedral group

Pick an integer n > 2 and let R be a regular n-gon centered about the origin in the plane. If n = 3 then R is an equilateral triangle, if n = 4 then R is a square, if n = 5 then R is a pentagon, and so on. Let G denote the set of all linear transformations of the plane to itself that preserve the gure R. The binary operation : G G G given by composition of functions gives G the structure of a group. This group is called the group of symmetries of R. Incidentally, if we regard R as a gure in 3-space centered above the origin and let G denote the set of all linear transformations of 3-space, then we obtain a slightly larger group in some cases (see Example 9.3.4 below and [NST] for more details). Label the vertices of the n-gon as 1, 2,. , n. The group G permutes these vertices amongst themselves; hence, each g G may be regarded as a permutation of the set of vertices V = {1, 2,. , n}. In this way, we may regard G as a permutation group, since it is the subgroup of Sn generated by the elements of G. The fact that this group has 2n elements follows from a simple counting argument: Let r G denote the element that rotates R by 2/n radians counterclockwise about the center. Let L be a line of symmetry of R that bisects the gure into two halves. Let s denote the element of G that is reection about L. There are n rotations by a multiple of 2/n radians about the center in G: 1, r, r2 ,. , rn1. There are n elements of G that are composed of a reection about L and a rotations by a multiple of 2/n radians about the center: s, s r, s r2 ,. , s rn1. These comprise all the elements of G. The symmetry group of R is known as the dihedral group of order 2n, denoted Dn. (Note: Some people denote this group instead by D2n.) Example 5.3.1. Let G be the symmetry group of the square, i.e., the group of symmetries of the square generated by the rigid motions g0 = 90 degrees clockwise rotation about O, g1 = reection about 1 , g2 = reection about 2 , g3 = reection about 3 , g4 = reection about 4 , where 1 , 2 , 3 denote the lines of symmetry in the picture below: 86

5.9. CONJUGATION Example 5.8.2. This example shows how to use SAGE to test if the two squares subgroup of the cube group is solvable.
SAGE sage: sage: sage: sage: sage: True rubik = CubeGroup() r = rubik.R() u = rubik.U() G = PermutationGroup([r2,u2]) G.is_solvable()
Next, let us consider the commutator g = [R, U ] = RU R1 U 1. Recall and n-cycle is a cyclic permutation of order n. As Example 5.8.1 predicts, SAGE tells us that, indeed, [R, U ]2 is composed of 3-cycles and [R, U ]3 is composed of 2-cycles:
SAGE sage: g = r*u*r(-1)*u(-1) sage: g2 (1,35,9)(2,5,21)(3,27,33)(8,25,19)(24,30,43)(26,28,34) sage: g3 (1,33)(3,35)(8,43)(9,27)(19,30)(24,25)

Conjugation

Besides composing two moves together and using the commutator, another operation that takes place frequently on the Rubiks Cube is the operation move 1, then move 2, then inverse of move 1. This type of move is called a conjugation. Denition 5.9.1. If g, h are two elements of a group G, then we call the element g h = h1 g h the conjugate of g by h. Note that g h = g if and only if g, h commute. Thus the conjugates may be regarded as a rough measurement of the lack of commutativity. The exponential notation is justied by the following facts, which are easy to verify. Ponderable 5.9.1. Show that
h h (a) (g1 g2 )h = g1 g2 ,
(b) g h1 h2 = (g h1 )h2. 105
5.9. CONJUGATION Ponderable 5.9.2. Let G = S3 , the symmetric group on 3 letters, in the notation of Example 5.4.1. Compute the conjugations ss2 , 1 ss1. 2
Ponderable 5.9.3. Let R, U be as in the notation for the Rubiks Cube moves introduced in the previous chapter. Determine the order of the move RU. (Answer: 4) Denition 5.9.2. We say that two elements g1 , g2 of G are conjugate if there h is an element h G such that g2 = g1. It turns out that it is easy to see when two permutations g, h Sn are conjugate: they are conjugate if and only if the cycles in their respective disjoint cycle decompositions have the same length when arranged from shortest to longest. (This result is due to Cauchy.) For example, the elements g = (6, 9)(1, 3, 4)(2, 5, 7, 8), h = (1, 2)(3, 4, 5)(6, 7, 8, 9)
are conjugate in S9. We shall leave the details and the proof for later (see 9.3.1). Ponderable 5.9.4. Show that the notion of conjugate denes an equivalence relation. That is, show that (a) any element g G is conjugate to itself (reexive); (b) if g is conjugate to h (g, h belonging to G), then h is conjugate to g (symmetry); (c) if g1 is conjugate to g2 and g2 is conjugate to g3 then g1 is conjugate to g3 (transitivity). Notation: The set of equivalence classes of G under the equivalence relation given by conjugation will be denoted G. Ponderable 5.9.5. Let G be a nite group. Show that (a) |G | |G|, and (b) |G| = |G | if and only if G is abelian. The polynomial pG (t) =

6.5. THE MATHEMATICS OF THE MACHINE We interpret the input Ei,j to mean that the (i, j)th button of the array was pressed. The eect of pressing any button is to toggle the button itself and those which are directly north, south, east, or west of the button pressed. There is no wraparound (at least not in the most basic version) so there are 3 buttons toggled in case a corner button is pressed, 4 buttons toggled in case an edge button is pressed, 5 buttons toggled in case a central button is pressed. To model this as a nite-state machine, let the transition function f : S I S be dened by f (s, E) = s + t(E), s S, E I,
where addition is coordinate-wise mod 2 and t(E) is the toggle matrix: Ei,j + Ei1,j + Ei,j1 + Ei+1,j + Ei,j+1 , 1 < i < M, 1 < j < N, Ei,j + Ei1,j + Ei+1,j + Ei,j+1 , 1 < i < M, j = 1, Ei,j + Ei+1,j + Ei,j+1 , i = 1, j = 1, Ei,j + Ei1,j + Ei,j+1 , i = M, j = 1, Ei,j + Ei,j1 + Ei+1,j + Ei,j+1 , i = 1, 1 < j < N, t(Ei,j ) = Ei,j + Ei1,j + Ei,j1 + Ei,j+1 , i = M, 1 < j < N, Ei,j + Ei1,j + Ei,j1 + Ei+1,j , 1 < i < M, j = N, Ei,j + Ei,j1 + Ei+1,j , i = 1, j = N, Ei,j + Ei1,j + Ei,j1 , i = M, j = N. For example, if M = N = 3 and E = E1,2 then 1 t(E) = 0 , 0 and if E = E22 then t(E) =
Finally, let the output function g : S I O be the same as the transition function g = f. This describes Lights Out as a nite-state machine.

0 1. 0

The mathematics of the machine
We shall follow Anderson and Feils [AF] presentation to begin with. The idea is generalized and extended considerably in the papers of Goldwasser, Klostermeyer, et al. referenced below. The essential idea presented in this section was 129
6.5. THE MATHEMATICS OF THE MACHINE posted on the sci.math newsgroup in Feb. 1998, months before [AF] appeared, rst by Carsten Haese and then by Dave Rusin [Rus]. It appears that Haese thought of the idea independently of Anderson and Feil.

The square case

Suppose, to begin, that M = N. Represent each state s MN (Z/2Z) as an N 2 -tuple s = (s1,1 , s1,2 ,., s1,N , s2,1 ,., sN,N ). Let B denote the N N banded matrix with 1s and superdiagonal, and 0s elsewhere: 0 0. 1 0. B = 1 1. . . 0 0. Let IN denote the N N identity matrix. Let B IN IN B IN 0 A = 0 IN B IN . . 0 0. 0 on the diagonal, subdiagonal,

Denition 9.4.1. Let H be a subgroup of G. We say that H is a normal subgroup if, for each g G, g 1 H g = H (i.e., for each g G and each h H, g 1 h g belongs to H). Notation: Sometimes we denote H is a normal subgroup of G by H G 178
Examples of non-normal subgroups
We saw above that examples of normal subgroups are easy to construct. For instance, the kernel of any homomorphism f : G H is a normal subgroup of G. For example, the kernel of the sgn homomorphism is normal: An Sn (see Example 9.4.1). More generally, if G is any group then the commutator subgroup, G , is a normal subgroup of G. (The commutator subgroup of Sn is An.) What about non-normal subgroups? Examples of subgroups which are not normal are easy to come by. Example 9.4.2. (a) If n > 5 and H is any non-trivial proper subgroup of An (for example, any non-trivial cyclic subgroup) then H is not normal in An (see Theorem 9.4.1 below). (b) Any subgroup of S6 of order 2 is non-normal. (c) Here is a way to get SAGE (rather GAP, via SAGE) to return the normal subgroups of a group:
SAGE sage: G = SymmetricGroup(5) sage: GG = gap(G) sage: GG.NormalSubgroups() [ Group( () ), AlternatingGroup( [ 1. 5 ] ), SymmetricGroup( [ 1. 5 ] ) ] sage: G = DihedralGroup(5) sage: GG = gap(G) sage: GG.NormalSubgroups() [ Group( () ), Group( [ (1,2,3,4,5) ] ), Group( [ (1,2,3,4,5), (1,5)(2,4) ] ) ]
This tells us the following facts. 1. Any subgroup of S5 other than itself, A5 , and the trivial group, is not normal. 2. Any subgroup of D5 other than itself, C5 = (1, 2, 3, 4, 5) , and the trivial group, is not normal. We have already shown the following result. Lemma 9.4.3. If f : G1 G2 is a homomorphism between two groups then ker(f ) is a normal subgroup of G1. Example 9.4.3. Here is an example of how to use SAGE to compute the kernel of a group homomorphism. 179
SAGE sage: G = CyclicPermutationGroup(10) sage: g0 = G.gens()[0] sage: phi = PermutationGroupMorphism_im_gens(G,G,[g0],[g02]) sage: phi.kernel() Group([ (1,6)(2,7)(3,8)(4,9)(5,10) ]) sage: ker = PermutationGroup(["(1,6)(2,7)(3,8)(4,9)(5,10)"]) sage: ker.order() 2
This tells us the kernel of the homomorphism of abelian groups, : C10 C10 given by (x) = x2 , is {1, (1, 6)(2, 7)(3, 8)(4, 9)(5, 10)} (a subgroup of order 2).

The alternating group

The following remarkable result about the alternating group will not be needed to understand the structure of the Rubiks Cube. However, the theorem below is interesting because of its connection with the fact (due to Runi and Abel) that you cannot solve the general polynomial of degree 5 or higher using radicals, i.e., that there is no analog of the quadratic formula for polynomials of degree 5 or higher. Explaining this connection would, unfortunately, take us too far from our main topic. Theorem 9.4.1. If X has 5 elements or greater, then AX has no non-trivial proper normal subgroups. In other words, if H AX is a normal subgroup, then either H = {1} or H = AX. This will not be proven here. (For a proof, see, for example, [R] or [Ar], chapter 14.) However, the next fact about the alternating group will be needed later in our determination of the structure of the Rubiks Cube group. This fact also arose in connection with our discussion of the legal positions of the 15 Puzzle in chapter 4 (see 4.1). Proposition 9.4.1. Let H be the subgroup of Sn generated by all the 3-cycles in Sn ; then H = An. Proof: Since sgn : Sn {1} is a homomorphism, and since any 3-cycle is even, any product of 3-cycles must also be even. Therefore, H An. If g An then g must swap an even number of the inequalities 1 < 2 <. < n 1 < n, by Denition 3.1.1. Therefore (since any permutation may be written as a product of 2-cycles, Theorem 3.4.1), g must be composed of permutations of the form (i, j)(k, l) or (i, j)(j, k). But (i, j)(k, l) = (i, j, k)(j, k, l) and (i, j)(j, k) = (i, j, k). Therefore, g H. This implies An H, so An = H. The following more precise result is very useful for the purposes of the analysis of permutation puzzles. 180

9.6. DABBLING IN DIRECT PRODUCTS Solution: The answer is no. The reason is that the slice moves can only rotate a given edge subcube within the slice it belongs to. This completes the solution. It follows, therefore, that the permutations of the edge subcube and centers determine a unique element of the slice group. In other words, we have proven the following Proposition 9.6.1. The homomorphism f : H SX is an embedding. Ponderable 9.6.6. The analog of this for the Rubiks Cube group is false! Why? H acts on the set ERL , so we have a homomorphism rRL : H SERL and similarly, rU D : H SEU D , rF B : H SEF B. H acts on each of the sets E and C, so we have homomorphisms r = rRL rU D rF B : H SERL SEU D SEF B SE , which we can put together to obtain an injective homomorphism r s : H SERL SEF B SEU D SC. To determine H, we determine the image of H in SERL SEF B SEU D SC. To do this, we rst look at the image of H in each of SERL , SEF B , and SEU D. This is easy enough: the image of H in SERL is MR C4 , = the image of H in SEF B is MF C4 , = s : H SC ,
the image of H in SEU D is MU C4. = Later, we shall want to think of C4 as {0, 1, 2, 3}, with addition mod 4, and the image of an element h H under one of the homomorphisms above, rRL : H SEF B , say, as an integer 0 rRL (h) 3. Next, we must determine the image of H in SC. This is easy if its looked at in the right way. As far as the movements of the center facets are concerned, the slice moves may be replaced by their corresponding rotations of the entire cube about an axis of symmetry. In this case, we see that the image of H in SC is the same as the image of the orientation-preserving symmetry group of the cube! This we know, by the discussion in Example 9.3.4 above, is isomorphic to S4. Putting all this together, we see that the image of H in SERL SEF B SEU D SC is isomorphic to a subgroup of

3 C4 S4.

9.6. DABBLING IN DIRECT PRODUCTS We may represent the elements of H , therefore, as 4-tuples (h1 , h2 , h3 , h4 ), with h1 , h2 , h3 C4 and h4 S4. Since each of the generating moves of H (namely, MR , MU , and MF ) satises sgn(r(h)) = sgn(s(h)),
3 for all h H, the image of H cannot be all of C4 S4. 3 Proposition 9.6.2. The image of H in C4 S4 is isomorphic to the kernel of the map 3 t : C4 S4 {1} (h1 , h2 , h3 , h4 ) sgn(h1 ) sgn(h2 ) sgn(h3 ) sgn(h4 ),
where each sgn is the sign of the permutation, regarded as an element of SX. Ponderable 9.6.7. Show that |ker(t)| = (43 4!)/2 = 768.
3 Solution: We have shown that H is isomorphic to a subgroup of C4 S4. In fact, we know that the basic slice moves MR , MU , MF (which generate H) all 3 belong to the kernel of t, so H is isomorphic to a subgroup of ker(t) C4 S4. It remains to show that every element in ker(t) belongs to H. To do this, we consider the projection homomorphism

n Theorem 10.5.1. The group Cm Sn+1 is given by generators a1 ,., an , h1 ,., hn and relations
(ai aj )mij = 1, provided 1 i, j n, = 1, hi hj = hj hi , provided 1 i, j n ai hj a1 = hj , provided |i j| > 1, i ai hi a1 = h1 , i i ai1 hj a1 = hi hi1. i1
Remark 10.5.1. Essentially the same presentation may be found in the paper [DM] by Davies and Morris. I only sketch the proof since it is in [DM].

10.5.2

Idea of the proof
Here is a sketch of the proof (for which I thank Dennis Spellman) of the above theorem. Let P denote the group presented in the above theorem. The claim is, n of course, that Cm Sn+1 P. There is a surjective homomorphism f : P = n Cm Sn+1 given by sending the generators to the generators. The problem is to show that this is injective. Let K = ker(f ), so
n |P | = |P/K||K| |P/K| = |Cm Sn+1 | = mn (n + 1)!. m Note that H = h1 ,., hn | hi = 1, hi hj = hj hi P is a normal subgroup of P since each ai sends a generator of H to a product of them or their inverses. n Also, note that H = Cm. We claim that P/H = Sn+1. From this it will follow that |P | = mn (n + 1)!, proving that |K| = 1, as desired. To establish P/H Sn+1 , we verify that the presentation on P/H one = gets from Theorem 2.1 in [MKS] is the same as that of Sn+1. Indeed, if
10.5. THE PRESENTATION PROBLEM W (a1 ,., an , h1 ,., hn ) = 1 is a relation in the presentation, we must determine the word W (a1 ,., an , h1 ,., hn )H in P/H. Note that every relation collapses and becomes trivial except for the relations (ai aj )mij = 1. These relations dene the presentation for Sn+1 , as desired. Ponderable 10.5.2. How many generators and relations are specied by this theorem when (a) n = 7 and m = 3, (b) n = 11 and m = 2?

Chapter 11

The (legal) Rubiks Cube group
The advantage is that mathematics is a eld in which ones blunders tend to show very clearly and can be corrected or erased with a stroke of the pencil. It is a eld which has often been compared with chess, but diers from the latter in that it is only ones best moments that count and not ones worst. Norbert Wiener, Ex-prodigy: my childhood and youth
In this chapter, we build on the material in the previous chapters to describe mathematically the group of (legal) moves of the Rubiks Cube. For rsttimers, it might seem like weve just nished a long steep climb to the top of a hill. However, we are not done! Though the terrain may atten out, there is still a bit of a hike until we get to our destination.
Mathematical description of the 3 cube moves
In this section, we describe mathematically the moves of the 3 Rubiks Cube. As we will see, this will lead eventually to the description of the Rubiks Cube group as a subgroup of index 12 of a direct product of two wreath products.

11.2. STRUCTURE OF THE CUBE GROUP does not correspond to an element of the subset AE AV of the Rubiks Cube group because an edge 2-cycle is an odd permutation of the edges. Therefore, if we consider the subgroup of SE SV generated by all three types of moves we will obtain either all of SE SV or some subgroup of index 2 which properly contains AE AV. The rst possibility can be ruled out since it contradicts the parity condition in (a). The only subgroup of SE SV of index 2 which properly contains AE AV is the subgroup of elements satisfying the parity condition in (a). It follows that the if part of the theorem is true in the case that v and w are both zero. The theorem is a consequence of these special cases because of the following. Claim: No matter what position the Rubiks Cube is in, there is always a move which does not permute any subcubes but solves the orientation of the cube so that v and w are both zero. Ponderable 11.2.3. Prove this claim. Finally, the proof of the theorem is nished. Corollary 11.2.1. The Rubiks Cube group is given by G = {g = (v, r, w, s) H | (a), (b), (c) hold}, where (a), (b), (c) are as in the above theorem. Now we show that the center of the Rubiks Cube group consists of the identity and the superip. Corollary 11.2.2. The center of G consists of two elements: the identity and the superip element z = (v, r, w, s) where w = (1, 1,., 1) C2 , v = 0 C3 , s = 1 S12 and r = 1 S8. Proof: The proof given here is essentially the same as that of Bandelow [B1]. Again, write v in place of v, for simplicity. Recall that the center of Sn , n > 2, is trivial (see Ponderable 5.6.2 above). Fix (v, r, w, s) G. We have (v, r, w, s) (v , r , w , s ) = (v + P (r)(v ), rr , w + P (s)(w ), ss ) = (v , r , w , s ) (v, r, w, s) = (v + P (r )(v), r r, w + P (s )(w), s s), for all (v , r , w , s ) G, only if r = 1 and s = 1. This implies that v + v = v + P (r )v, for all r S8. This forces v to be either (0, 0,., 0) or (1, 1,., 1) or (2, 2,., 2). Since it must satisfy conservation of twists, it cant be (1, 1,., 1) or (2, 2,., 2). Similarly, w + w = w + P (s )w, for all s S12 forces w to be either (0, 0,., 0) or (1, 1,., 1). Either of these choices is okay since they both satisfy conservation of ips. 227

12.4.2

Kleins 4-group and crossing the Pyraminx
We leave the main result of this section as an exerciseactually more of a projectfor the interested reader. Ponderable 12.4.3. Show that the subgroup of SV generated by the twistuntwist moves of the Pyraminx is isomorphic to the Klein 4-group C2 C2. The determination of the cross group for the Megaminx is due to J. Conway. It will be presented in chapter 14. As a kind of a hint, the following SAGE code is given. Notice that it produces the right group.
SAGE sage: sage: sage: sage: sage: 12 sage: S4 = SymmetricGroup(4) F = S4([(1,3,2)]); R = S4([(1,4,3)]) D = S4([(2,3,4)]); L = S4([(1,2,4)]) G = PermutationGroup([F,R,D,L]) G.order() c1 = F*R-1; c2 = D*R-1; c3 = L*F-1
sage: sage: sage: 4 sage: True c4 = L*R-1; c5 = D*L-1; c6 = D*R-1 C = PermutationGroup([c1,c2,c3,c4,c5,c6]) C.order() KleinFourGroup().is_isomorphic(C)
Can you solve ponderable 12.4.3 now?

Chapter 13

Other Rubik-like puzzle groups
The youthful impulse is rather to prowl about the problem for awhile, looking perhaps not for an open window or a door with a weak lock, for if these were available some earlier malefactor would have discovered them, but for some wall that can be scaled or some unsuspected underground access. Robert Langlands
Weve spent a lot of time thinking about the Rubiks Cube and how to solve itwe scaled that wall using group theory. What about the Megaminx, or other puzzles? This chapter says something about the group-theoretical structure of some of the other permutation puzzle groups.

A uniform approach

This section provides a uniform discussion of the Pyraminx, the Rubiks Cube, and the Megaminx. Notation: Let Gp (resp., GR , Gm ) denote the permutation puzzle group generated by the basic moves of the Pyraminx (resp., the Rubiks Cube, Megaminx), Vp (resp., VR , Vm ) denote the set of vertex pieces of the Pyraminx (resp., the Rubiks Cube, Megaminx), Ep (resp., ER , Em ) denote the set of edge pieces of the Pyraminx (resp., the Rubiks Cube, Megaminx), Fp (resp., FR , Fm ) denote the set of facets of the movable pieces of the Pyraminx (resp., the Rubiks Cube, Megaminx). 251

13.1. A UNIFORM APPROACH

13.1.1

General remarks

Let G, V, E, F (resp.) denote either Gp , Ep , Vp , Fp (resp.), or GR , ER , VR , FR (resp.), or Gm , Em , Vm , Fm (resp.). Lemma 13.1.1. G acts on the set V (resp., E, F ). 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 SV of V , as an element of the symmetric group SE of E, or as an element of the symmetric group SF of F. These groups SV , SE , and SF are dierent, so to distinguish these three ways of regarding g, let us write gV for the element of SV corresponding to g, gE for the element of SE corresponding to g, gF for the element of SF corresponding to g. What is the kernel of fV ? What is its image? To answer this question (actually, we shall not answer this precise question but one similar to it) we introduce a certain subgroup of the symmetric group. Recall the alternating group AX is the subgroup of all even permutations of X (in the sense of Example 5.6.3 above).

15.3. RAINBOW MASTERBALL 1. We want to get the middle two entries in column 2 aligned. Call the color in the (2, 3)-entry color 2. We want to get color 2 in the (2, 2)-entry. The remaining large color 2 tile is what we will sh for. Hold the ball in front of you in such a way that column 2 is slightly to the left of center and column 3 is slightly to the right of center. There are 4 facets in the right upper middle band, 4 facets in the left upper middle band, 4 facets in the right lower middle band, and 4 facets in the left lower middle band. A ip about the center on the right half (i.e., perform f2 ) exchanges these. We may assume that color 2 is on one of the 4 facets in the right lower middle band. (If it isnt, you need 1 to apply f2 rst). Now perform r2 f2 r2 f2 : rst perform r2 (this 1 is baiting the hook), then f2 (putting the hook in the water), then r2 (setting the hook), and nally f2 (reeling in the hook). You may or may not have color 2 in the (2, 2) place, but the color 1 stripe is intact. If necessary, try again. After at most 4 tries youll be successful. Step 2 : Repeat this shing strategy to get color 2 in the (1,2) position (using r1 f2 r1 f2 in place of r2 f2 r2 f2 ). Now, by turning the ball over if necessary, repeat this idea to get color 2 in the (4, 2) position. Now you have two aligned stripes on your ballcolor 1 in column 1 and color 2 in column 2. We say, in this case, that columns 1 and 2 have been solved. Step 3 : Repeat the analogs of Steps 1 and 2 for columns 3 and 4. Step 4 : Use the moves in the catalog in Figure 15.3.1 below to nish the puzzle. (I believe the only moves needed are the equator2swap36 and the polar2swap36 below, along with suitable, cleverly chosen set-up moves.)

15.3.1

A catalog of Masterball moves
Column moves We number the columns as 1,. , 8. We will use a signed cycle notation to denote an action of a move on the columns of the Masterball. Example 15.3.1. A move which switches the 1st and 3rd column but ips both of them over will be denoted by (1, 3). A move which sends the 4th column to the 6-th column, the 6th column to the 5th column, and switches the 2nd and 3rd column but ips both of them over will be denoted by (2, 3) (6, 5, 4). We have used a as a subscript to indicate the ip. Finally, (f1 f2 f3 f4 )2 r1 r2 r3 r4 swaps the 7,8 columns and leaves all the others xed but ipped over. 292
15.3. RAINBOW MASTERBALL Move f1 f2 f3 f4 f5 f6 f7 f8 f1 f2 f1 f1 f2 f1 f2 f1 f3 f1 f2 f3 f2 f1 f4 f1 f1 f5 f1 f1 f8 f1 f8 f1 f8 f2 f1 f2 f3 f1 f3 f8 f1 f2 Cycle (1, 4) (2, 3) (2, 5) (3, 4) (3, 6) (4, 5) (4, 7) (5, 6) (5, 8) (6, 7) (1, 6) (7, 8) (2, 7) (1, 8) (3, 8) (1, 2) (1, 2) (3, 5) (5, 4, 3, 2, 1) (1, 5)(2, 6) (2, 3) (6, 5, 4) (1, 7)(5, 6) (5, 8) (6, 7) (2, 8)(3, 4) (1, 8) (4, 3, 2) (1, 3)(4, 5) (1, 3)(4, 8) (1, 4) (2, 3, 8, 5) Cycle 84)(44, 81)(44, 84)(11, 14)(31, 64)(11, 13)(32, 63)(12,