Group Theory and the Rubik's Cube

1 Group Theory and the Rubik s CubeJanet ChenA Note to the ReaderThese notes are based on a 2-week course that I taught for high school students at the Texas State HonorsSummer Math Camp. All of the students in my class had taken elementary number Theory at the camp, soI have assumed in these notes that readers are familiar with the integers modnas well as the units one goal of this class was a complete understanding of the Rubik s cube, I have tried to use notationthat makes discussing the Rubik s cube as easy as possible. For example, I have chosen to use right groupactions rather than left Group is some notation that will be used set of , 3, 2, 1,0,1,2,3,..Nthe set of positive integers 1,2,3,..Qthe set of rational numbers (fractions)Rthe set of real numbersZ/nZthe set of integers modn(Z/nZ) the set of units modnThe goal of these notes is to give an introduction to the subject of Group Theory , which is a branch of themathematical area called algebra (or sometimes abstract algebra).

2 You probably think of algebra as addition, multiplication , solving quadratic equations, and so on. Abstract algebra deals with all of this but, as thename suggests, in a much more abstract way! Rather than looking at a specific operation (like addition) ona specific set (like the set of real numbers, or the set of integers), abstract algebra is algebra done withoutreally specifying what the operation or set is. This may be the first math you ve encountered in whichobjects other than numbers are really studied!A secondary goal of this class is to solve the Rubik s cube. We will both develop methods for solving theRubik s cube and prove (using Group Theory !) that our methods always enable us to solve the Hofstadter wrote an excellent introduction to the Rubik s cube in the March 1981 issue ofScientificAmerican. There are several books about the Rubik s cube; my favorite isInside Rubik s Cube and Beyondby Christoph Bandelow.

3 David Singmaster, who developed much of the usual notation for the Rubik s cube,also has a book calledNotes on Rubik s Magic Cube, which I have not an introduction to Group Theory , I recommendAbstract Algebraby I. N. Herstein. This is a wonderfulbook with wonderful exercises (and if you are new to Group Theory , you should do lots of the exercises). Ifyou have some familiarity with Group Theory and want a good reference book, I recommendAbstract Algebraby David S. Dummit and Richard M. FunctionsTo understand the Rubik s cube properly, we first need to talk about some different properties of ormapffrom a domainDto a rangeR(we writef:D R) is a rule whichassigns to each elementx Da unique elementy R. We writef(x) =y. We say thatyis theimage ofxand thatxis apreimage ofy. Note that an element inDhas exactly one image, but an element ofRmayhave0,1, or more can define a functionf:R Rbyf(x) =x2.

4 Ifxis any real number, its image is thereal numberx2. On the other hand, ifyis a positive real number, it has two preimages, yand y. Thereal number 0 has a single preimage, 0; negative numbers have no will provide important examples of groups later on; we will also use functions to translate information from one Group to functionf:D Ris calledone-to-one ifx16=x2impliesf(x1)6=f(x2)forx1,x2 is, each element ofRhas at most one the functionf:Z Rdefined byf(x) =x+ 1. This function is one-to-one since,ifx16=x2, thenx1+ 16=x2+ 1. Ifx Ris an integer, then it has a single preimage (namely,x 1). Ifx Ris not an integer, then it has no functionf:Z Zdefined byf(x) =x2is not one-to-one, sincef(1) =f( 1) but 16= 1. Here, 1 hastwo preimages, 1 and functionf:D Ris calledonto if, for everyy R, there existsx Dsuch thatf(x) =y.

5 Equivalently, every element ofRhas at least one functionf:Z Rdefined byf(x) =x+ 1 is not onto since non-integers do not havepreimages. However, the functionf:Z Zdefined byf(x) =x+ 1 is functionf:Z Zdefined byf(x) =x2is not onto because there is nox Zsuch thatf(x) = you find a ..1.. function which is neither one-to-one nor onto?2.. function which is one-to-one but not onto?3.. function which is onto but not one-to-one?4.. function which is both one-to-one and onto?Definition functionf:D Ris called abijection if it is both one-to-one and onto. Equivalently,every element ofRhas exactly one functionf:Z Zdefined byf(x) =x+ 1 is a any set, then we can define a mapf:S Sbyf(x) =xfor allx S. This mapis called theidentitymap, and it is a :S1 S2andg:S2 S3, then we can define a new functionf g:S1 S3by(f g)(x) =g(f(x)). The operation is usually writes(g f)(x) =g(f(x))rather than(f g)(x) =g(f(x)).

6 However, as longas we are consistent, the choice does not make a big difference. We are using this convention because itmatches the convention usually used for the Rubik s Which of the following functions are one-to-one? Which are onto?(a)f:Z Zdefined byf(x) =x2+ 1.(b)f:N Ndefined byf(x) =x2+ 1.(c)f:Z Zdefined byf(x) = 3x+ 1.(d)f:R Rdefined byf(x) = 3x+ Supposef1:S1 S2andf2:S2 S3are one-to-one. Prove thatf1 f2is Supposef1:S1 S2andf2:S2 S3are onto. Prove thatf1 f2is Letf1:S1 S2,f2:S2 S3, andf3:S3 S4. Prove thatf1 (f2 f3) = (f1 f2) LetSbe a set.(a) Prove that there exists a functione:S Ssuch thate f=fandf e=ffor all bijectionsf:S S. Prove thateis a (b) Prove that, for every bijectionf:S S, there exists a bijectiong:S Ssuch thatf g=eandg f= Iff:D Ris a bijection andDis a finite set withnelements, prove thatRis also a finite set GroupsExample get an idea of what groups are all about, let s start by looking at two familiar , consider the integers mod 4.

7 Remember thatZ/4 Zis a set with 4 elements: 0, 1, 2, and 3. One ofthe first things you learned in modular arithmetic was how to add numbers modn. Let s write an additiontable forZ/4Z.+012300123112302230133012 Now, we re going to rewrite the addition table in a way that might seem pretty pointless; we re just goingto use the symbol instead of + for addition, and we ll writee= 0,a= 1,b= 2, andc= 3. Then, ouraddition table looks like e a b cee a b caa b c ebb c e acc e a bLet s do the same thing for (Z/5Z) , the set of units mod 5. The units mod 5 are 1, 2, 3, and 4. If you addtwo units, you don t necessarily get another unit; for example, 1 + 4 = 0, and 0 is not a unit. However, ifyou multiply two units, you always get a unit. So, we can write down a multiplication table for (Z/5Z) .Here it is: 1 2 4 311 2 4 322 4 3 144 3 1 233 1 2 4 Again, we re going to rewrite this using new symbols.

8 Let mean multiplication , and lete= 1,a= 2,b= 4,andc= 3. Then, the multiplication table for (Z/5Z) looks like e a b cee a b caa b c ebb c e acc e a bNotice that this is exactly the same as the table for addition onZ/4Z!Why is it interesting that we get the same tables in these two different situations? Well, this enables us totranslate algebraic statements about addition of elements ofZ/4 Zinto statements about multiplication ofelements of (Z/5Z) . For example, the equationx+x= 0 inZ/4 Zhas two solutions,x= 0 andx= our alternate set of symbols, this is the same as saying that the equationx x=ehas solutionsx=eandx=b. If we translate this to (Z/5Z) , this says that the solutions ofx x= 1 in (Z/5Z) arex= 1andx= 4. That is, 1 and 4 are the square roots of 1 in (Z/5Z) , which is exactly right!In mathematical language, we say thatZ/4 Zwith addition and (Z/5Z) with multiplication are isomorphicgroups.

9 The word isomorphic means roughly that they have the same algebraic structure; we ll get intothis later. For now, let s just see what a Group (G, )consists of a setGand an operation such closed under . That is, ifa,b G, thena b : Z/4 Zis closed under+; after all, we wrote down the addition table , which tells us how to addany two elements ofZ/4 Zand get another element ofZ/4Z. Similarly,(Z/5Z) is closed undermultiplication. Zis closed under+: ifa,b Z, thena+b Z. Similarly,Zis also closed under . Ris closed under multiplication : if we multiply two real numbers, we get a real number. The set of negative numbers is not closed under multiplication : if we multiply two negative num-bers, we get a positive is associative. That is, for anya,b,c G,a (b c) = (a b) : Addition and multiplication are associative. Subtraction is not associative becausea (b c)6= (a b) There is an identity element e Gwhich satisfiesg=e g=g efor allg : For(Z/4Z,+),0is an identity element becauseg= 0 +g=g+ 0for anyg Z/4Z.

10 For((Z/5Z) , ),1is an identity element becauseg= 1 g=g 1for anyg (Z/5Z) . For(Z,+),0is an identity element becauseg= 0 +g=g+ 0for anyg Z. For(R, ),1is an identity element becauseg= 1 g=g 1for anyg Inverses exist; that is, for anyg G, there exists an elementh Gsuch thatg h=h g=e. (hiscalled aninverse ofg.)Examples: Using the addition table forZ/4Z, we can find inverses of all the elements ofZ/4Z. For instance,we can see from the table that1 + 3 = 3 + 1 = 0, so3is the inverse of1. Similarly, since thetable for(Z/5Z) is identical, all elements of(Z/5Z) have inverses. For(Z,+), the inverse ofn Zis nbecausen+ ( n) = ( n) +n= 0. For(R, ), not every element has an inverse namely,0does not have an inverse. However, ifx6= 0, then1xis an inverse ofxbecausex 1x=1x x= (Z/4Z,+) and ((Z/5Z) , ) are groups. In fact, as we said earlier, these should be thought of as the same Group , but we won t go into this until (Z,+) is a Group .