Rubik’s cube notes – introduction

MATHEMATICS OF THE RUBIK’S CUBE

Lecture notes form a fall 1996 course at the US Naval Academy

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

 

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
  • 2×2 Rubik’s cube
  • 3×3 Rubik’s cube
  • 4×4 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
    • 3×3 cube
    • 4×4 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

 

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.

 

REFERENCES

[A] J. Adams, HOW TO SOLVE RUBIK’S REVENGE, Dial Press, NY, 1982

[Ar] M. Artin, ALGEBRA, Prentice-Hall, 1991

[B] C. Bandelow, INSIDE RUBIK’S CUBE AND BEYOND, Birkhauser, Boston, 1980

[BCG] Berlekamp, J. Conway, R. Guy, WINNING WAYS, II, Academic Press,

[BH] R. Banerji, D. Hecker, “The slice group in Rubik’s cube”, Math. Mag. vol 58, 1985, pp 211-218

[Bu] G. Butler, FUNDAMENTAL ALGORITHMS FOR PERMUTATION GROUPS, Springer-Verlag, Lecture Notes in Computer Science, vol 559, 1991

[C] J. Crossley, et al, WHAT IS MATHEMATICAL LOGIC?, Dover, 1972

[CL] ftp archives of the “cube-lovers” list

[EK] J. Ewing, C. Kosniowski, PUZZLE IT OUT, CUBES, GROUPS, AND PUZZLES, Cambridge Univ Press, 1982

[G] A. Gaglione, AN INTRODUCTION TO GROUP THEORY, NRL, 1992 (pdf). This book is in the public domain.

[GT] K. Gold, E. Turner, “Rubik’s group”, Amer. Math. Monthly, vol 92, 1985, pp 617-629

[L] M. E. Larsen, “Rubik’s revenge: the group theoretical solution”, Amer. Math. Monthly, vol 92, 1985, pp 381-390

[M] R. E. Moritz, MEMORABILIA MATHEMATICA, MacMillan Co, NY, 1914

[NST] P. Neumann, G. Stoy, E. Thompson, GROUPS AND GEOMETRY, Oxford Univ. Press, 1994

[R] J. J. Rotman, AN INTRODUCTION TO THE THEORY OF GROUPS, 4th ed, Springer-Verlag, Grad Texts in Math #148, 1995

[Ru] E. Rubik, et al, RUBIK’S CUBIC COMPENDIUM, Oxford Univ Press, 1987

[S] R. Schmalz, OUT OF THE MOUTHS OF MATHEMATICIANS, Math. Assoc. Amer., 1993

[Si] D. Singmaster, NOTES ON RUBIK’S MAGIC CUBE, Enslow, 1981

[St] R. Stoll, SET THEORY AND LOGIC, Dover, 1963

[T] Thai, “The winning solution to Rubik’s Revenge”, Banbury Books, 1982