MATHEMATICS OF THE RUBIK'S CUBE Fall 1996 course at the US Naval Academy Annapolis, MD Instructor: Assoc Prof W. D. Joyner office: Ch 328 phone: (410)293-6738 email: wdj@sma.usna.navy.mil or wdj@nadn.navy.mil Mathematical Quotes: "By and large it is uniformly true that in mathematics that there is a time lapse between a mathematical discovery and the moment it becomes useful; and that this lapse can be anything from 30 to 100 years, in some cases even more; and that the whole system seems to function without any direction, without any reference to usefulness, and without any desire to do things which are useful." John von Neumann COLLECTED WORKS, VI, p489 "[Lefschetz and Einstein] had a running debate for many years. Lefschetz insisted that there was difficult mathematics. Einstein said that there was no difficult mathematics, only stupid mathematicians. I think that the history of mathematics is on the side of Einstein." Richard Bellman EYE OF THE HURRICANE, 1984 "The advantage is that mathematics is a field in which one's blunders tend to show very clearly and can be corrected or erased with a stroke of the pencil. It is a field which has often been compared with chess, but differs from the latter in that it is only one's best moments that count and not one's worst." Norbert Wiener EX-PRODIGY: MY CHILDHOOD AND YOUTH For more quotes, see [M], [S] or the www page at http://math.furman.edu/~mwoodard/mquot.html Course Outline Introduction 0. Logic and sets 1. Functions on finite sets injective fcns, surjective fcns 2. Permutations inverse permutations and even, odd permutations 3. Permutation puzzles * 15 puzzle * devil's circles * equator * masterball * 2x2 Rubik's cube * 3x3 Rubik's cube * 4x4 Rubik's cube * megaminx 4. Groups, I symmetric group of a finite set, permutation groups, basic terms (subgroups, order, conjugates, commutators) 5. Orbits, actions, and cosets basic definitions (free and transitive actions, stabilizers), relationship between orbit and stabilizer 6. Strategies solution strategy and special moves for * 3x3 cube * 4x4 cube * rainbow masterball Appendix: A catalog of Rubik's cube moves 7. Cayley graphs and God's algorithm A graphical interpretation of a solution of a permutation puzzle 8. Symmetry groups of the Platonic solids * background on isometries of 3-space * the tetrahedral group * the octahedral group * the icosahedral group (orders, stabilizer subgroups, and description of symmetries) 9. Groups, II homomorphisms, the homomorphism theorems, normal subgroups, kernels, direct products, semi-direct products, wreath products 10. Structure of the Rubik's cube group orientation conditions 11. Rubika Esoterica 12. Advanced topic: Realizing PGL(2,F5) inside the Rubik's cube group References Notation N = {1,2,...} = the set of natural numbers, Z = {...,-2,-1,0,1,2,...} = the set of integers Let S, T be finite sets. "s in S" means s belongs to S "S subset T" means S is a subset of T SxT = {(s,t) | s in S and t in T} = set of all pairs of the form (s,t) such that s belongs to S and t belongs to T = Cartesian product of S and T, S union T = {x | x in S or x in T} = the set of all elements of S or T = the union of S and T, S intersection T = {x | x in S and x in T} = the set of all elements belonging to both S and T = the intersection of S and T, |S| = #S = the number of distinct elements in S. "S <> T" means S does not equal T In general, we shall use double quotes around a word we are defining, an underscore "_" will usually indicate a subscript and a caret "^" will usually denote a superscript. INTRODUCTION Groups measure symmetry and nowhere is this more evident than in the study of symmetry in 2- and 3-dimensional geometric figures. The Rubik's cube, and related puzzles, manifest this symmetry in a manipulation puzzle. This is a course about creating a group-theoretical model of Rubik's cube-like puzzles. In other words, we will use group theory to learn as much as we reasonably can (given the limitations of the course) about these types of permutation puzzles. What we need from group theory will, for the most part, be proven and all that is really required from the student is a certain amount of mathematical sophistication, energy, and some geometrical intuition. The ulterior motive for this course (and there is one) is to teach some group theory. If there is a different slant to our approach compared to others it is that we've stressed example. There is also an attempt to present some of the basic notions algorithmically (as in [Bu]), consistent with our concrete point of view. Group theory is one of those topics which occurs in a surprisingly large variety of seemingly disparate situations. Basically, any time there is symmetry, don't be surprised if there is a group hiding in the background. The Rubik's cube has a lot of symmetry but so do lots of other things - crystallography, elementary particle physics, to name just a few. As Hilbert said, the art to doing mathematics is to pick a good example to learn from. Hopefully, the Rubik's cube will be a good example. How much group theory do we hope to teach you? This course, if successful, should prepare you to study more group theory from one of the standard group theory texts, say Rotman [R]. This course covers the material in most of chapter 1, parts of chapters 2 and 3 in [R]. We shall assume, in some of the later chapters, some familiarity with matrices (matrix multiplication, transposes, some properties of the determinant and the inverse matrix). This course, with a course in linear algebra, will give the student more than enough background to begin reading Rotman [R]. I thank Dan Bump, Micheal Fourte, Mark Meyerson, and Andrew Southern for their suggestions on this material. 