You are currently browsing the tag archive for the ‘douglas hofstadter’ tag.

These notes are a wonderful introduction to group theory! Though only 39 pages in length, it covers a fair amount of the subject in a very clear fashion by relating the theory to the study of the Rubik’s Cube.

A Rubik’s Cube is a 3\times3\times3 cube in which the 26 subcubes on the outside are internally hinged in such a way that rotation (by a quarter turn in either direction or a half turn) is possible in any plane of cubes. Each of the six sides is painted a distinct color, and the goal of the puzzle is to return the cube to a state in which each side has a single color after it has been randomized by repeated rotations. The puzzle was invented in the 1970s by the Hungarian Ernő Rubik and sold millions of copies worldwide over the next decade.

The number of possible positions of the Rubik’s cube is

\frac{8!\cdot12!\cdot3^{8}\cdot2^{12}}{2\cdot3\cdot2}=43252003274489856000

(Turner and Gold 1985, Schönert). Hoey showed using the Pólya-Burnside lemma that there are 901083404981813616 positions up to conjugacy by whole-cube symmetries.

The group of operations on the Rubik’s cube is known as Rubik’s group, and the Cayley graph of that group is called Rubik’s graph. The minimum number of turns required to solve the cube from an arbitrary starting position is equal to the graph diameter of Rubik’s graph, and is sometimes known as God’s number. While algorithms exist for solving a cube from an arbitrary initial position, they are not necessarily optimal (i.e., requiring a minimum number of turns) and computation of God’s number is very difficult. It had been known since 1995 that a lower bound on the number of moves for the solution (in the worst case) was 20, it was not known until demonstrated by Rokicki et al. (2010) that no configuration requires more than 20 moves, thus establishing that God’s number is 20.

A Note to the Reader

These notes are based on a 2-week course that I taught for high school students at the Texas State Honors Summer Math Camp. All of the students in my class had taken elementary number theory at the camp, so I have assumed in these notes that readers are familiar with the integers mod n as well as the units mod n.

Because one goal of this class was a complete understanding of the Rubik’s cube, I have tried to use notation that makes discussing the Rubik’s cube as easy as possible. For example, I have chosen to use right group actions rather than left group actions.

Introduction

The goal of these notes is to give an introduction to the subject of group theory, which is a branch of the mathematical area called algebra (or sometimes abstract algebra). You probably think of algebra as addition, multiplication, solving quadratic equations, and so on. Abstract algebra deals with all of this but, as the name suggests, in a much more abstract way! Rather than looking at a specific operation (like addition) on a specific set (like the set of real numbers, or the set of integers), abstract algebra is algebra done without really specifying what the operation or set is. This may be the first math you’ve encountered in which objects 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 the
Rubik’s cube and prove (using group theory!) that our methods always enable us to solve the cube.

References

Douglas Hofstadter wrote an excellent introduction to the Rubik’s cube in the March 1981 issue of Scientific American. There are several books about the Rubik’s cube; my favorite is Inside Rubik’s Cube and Beyond by Christoph Bandelow. David Singmaster, who developed much of the usual notation for the Rubik’s cube, also has a book called Notes on Rubik’s ’Magic Cube,’ which I have not seen.

For an introduction to group theory, I recommend Abstract Algebra by I. N. Herstein. This is a wonderful book with wonderful exercises (and if you are new to group theory, you should do lots of the exercises). If you have some familiarity with group theory and want a good reference book, I recommend Abstract Algebra by David S. Dummit and Richard M. Foote.

Topics covered are:

  • Functions
  • Groups
  • The Rubik’s Cube and Subgroups
    • Cube Notation
    • Making the Rubik’ Cube into a Group
    • Subgroups
    • Simplifying Group Notation
  • Generators
  • The Symmetric Group
    • Disjoint Cycle Decomposition
    • Rubik’s Cube
  • Group Homomorphisms
  • The Sign Homomorphisms
  • The Alternating Group
  • Group Actions
  • Valid Configurations of the Rubik’s Cube

Read the article here.

Visit Janet Chen’s website here.

Advertisements

RSS PolyMath Wiki Recent Changes

  • An error has occurred; the feed is probably down. Try again later.

Enter your email address to follow this blog and receive notifications of new posts by email.