%last modified 8-4-2007

%\documentclass[12pt,runningheads]{book}
\documentclass[10pt,runningheads]{book}

\usepackage{fancyvrb}
\usepackage{moreverb}
\usepackage{amsfonts}
\usepackage{helvet}
\usepackage{fancyheadings}
\usepackage{amsbsy}
\usepackage{amsthm}
\usepackage{amsgen}
\usepackage{amsfonts}
%\usepackage[german,english]{babel}
\usepackage{array, rotating} 
\usepackage{graphicx, amsmath}
\usepackage{texdraw}
\usepackage{amssymb}
\usepackage{makeidx}  % allows for index generation
\usepackage[all,arc,dvips]{xy}
%\usepackage{chess}
\usepackage{color}

\definecolor{DarkOlive}{rgb}{0.1047,0.2412,0.0064}
\definecolor{FireBrick}{rgb}{0.5812,0.0074,0.0083}
\definecolor{RoyalBlue}{rgb}{0.0236,0.0894,0.6179}
\definecolor{RoyalGreen}{rgb}{0.0236,0.6179,0.0894}
\definecolor{RoyalRed}{rgb}{0.6179,0.0236,0.0894}
\definecolor{LightBlue}{rgb}{0.8544,0.9511,1.0000}
\definecolor{Black}{rgb}{0.0,0.0,0.0}
\definecolor{FuncColor}{rgb}{1.0,0.0,0.0}
\usepackage{hyperref}
\usepackage{url}
\usepackage{xspace}


%\pagestyle{fancyplain}
%\lhead[\fancyplain{}{\rightmark}]{\fancyplain{}}
%\rhead[\fancyplain{}]{\fancyplain{}{\rightmark}}

\setlength{\parindent}{8pt}

\pagenumbering{roman}
\pagestyle{empty}
%\setcounter{page}{4}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{corollary}{Corollary}[section]
\newtheorem{conjecture}{Conjecture}[section]
\newtheorem{lemma}{Lemma}[section]
\newtheorem{proposition}{Proposition}[section]
\newtheorem{definition}{Definition}[section]
\newtheorem{example}{Example}[section]
\newtheorem{axiom}{Axiom}[section]
\newtheorem{remark}{Remark}[section]
\newtheorem{exercise}{Exercise}[section]
\newtheorem{ponderable}{Ponderable}[section]


\def\aaa{\mathbb{A}}
\def\nnn{\mathbb{N}}
\def\fff{\mathbb{F}}
\def\qqq{\mathbb{Q}}
\def\rrr{\mathbb{R}}
\def\ccc{\mathbb{C}}
\def\zzz{\mathbb{Z}}
\def\ppp{\mathbb{P}}
\def\hhh{{\cal H}}
\def\pf{{\bf Proof: \ }}
\def\qed{$\Box$}
\def\stab{{\rm stab}}
\def\beqn{\begin{equation}}
\def\eeqn{\end{equation}}

\newcommand{\SAGE}{{\sf SAGE}\xspace}
\newcommand{\sage}{\SAGE}

\makeindex

\begin{document}

\pagestyle{fancyplain}
\lhead[\fancyplain{}{\rightmark}]{\fancyplain{}}
\rhead[\fancyplain{}]{\fancyplain{}{\rightmark}}

\author{David Joyner}
\title{Adventures in Group Theory: Rubik's Cube, Merlin's Machine, and Other 
Mathematical Toys\thanks{$2^{nd}$ edition}}

\date{8-28-2007}

\maketitle


\vskip .1in

\addtocounter{page}{3}

{\small{
\begin{quotation}
In mathematics you don't understand things. You just get used to them.
\vskip .1in   {\em             Johann von Neumann }
\end{quotation}
}}

\newpage
\addtocounter{page}{1}
\begin{center}
\large{
{\bf Contents}
}
\end{center}
\vskip .3in

%\noindent

%\contentsline{chapter}
%{\numberline{}Preface}{ix}
%\contentsline{chapter}
%{\numberline{}Ackowledgements}{xi}
%\contentsline{chapter}
%{\numberline{}Where to begin}{xiii}
%\contentsline{chapter}
%{\numberline{1}Elementary my dear Watson}{1}
%\contentsline{chapter}
%{\numberline{2}`And you do addition?'}{11}
%\contentsline{chapter}
%{\numberline{3}Bell ringing and other permutations}{29}
%\contentsline{chapter}
%{\numberline{4}A procession of permutation puzzles}{47}
%\contentsline{chapter}
%{\numberline{5}What's commutative and purple?}{65}
%\contentsline{chapter}
%{\numberline{6}Welcome to the machine}{99}
%\contentsline{chapter}
%{\numberline{7}`God's algorithm' and graphs}{115}
%\contentsline{chapter}
%{\numberline{8}Symmetry and the Platonic solids}{125}
%\contentsline{chapter}
%{\numberline{9}The illegal cube group}{135}
%\contentsline{chapter}
%{\numberline{10}Words which move}{161}
%\contentsline{chapter}
%{\numberline{11}The (legal) Rubik's Cube group}{177}
%\contentsline{chapter}
%{\numberline{12}Squares, two faces, and other subgroups}{189}
%%: subgroups of the cube group}{189}
%\contentsline{chapter}
%{\numberline{13}Other Rubik-like puzzle groups}{205}
%\contentsline{chapter}
%{\numberline{14}Crossing the rubicon}{222}
%\contentsline{chapter}
%{\numberline{15}Some solution strategies}{233}
%\contentsline{chapter}
%{\numberline{16}Coda: questions and other directions}{249}
%\contentsline{chapter}
%{\numberline{}Bibliography}{251}
%\contentsline{chapter}
%{\numberline{}Index}{258}

\newpage
\tableofcontents

\newpage

\addtocounter{page}{1}
\input cubebook_preface.tex

\newpage

\addtocounter{page}{1}

\input cubebook_ack.tex


\newpage

\addtocounter{page}{1}


\begin{center}
\LARGE{Where to begin... }
\end{center}


Speaking personally, I am always fascinated
to discover that one topic is connected 
in a surprising way with another
completely different topic.
The Rubik's Cube, a mechanical toy that
has a reasonably efficient solution using pure
mathematics (and no `strategy'), is a case in
point.
It's difficult to know where to begin to
explain this connection:
as Wodehouse's character Bertie Wooster said,
`I don't know if you have the same experience, but
the snag I come up against when I'm telling a story is the
dashed difficult problem of where to begin it'.
Let's 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 mid 1970's, he patented a 
cube-shaped mechanical puzzle
that has since captured the imagination of
millions of people worldwide.
The Rubik's Cube was born. By
1982, `Rubik's 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 1820's and early 1830's, 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=\frac{-b\pm \sqrt{b^2-4ac}}{2a}
\]
are the roots of the quadratic equation $ax^2+bx+c=0$.
There are similar but more complicated formulas
for the cubic and quartic polynomials discovered during the
middle ages (see for example \cite{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 coefficients
for an equation of fifth degree or higher?
This problem had remained unsolved for centuries
despite the efforts of the best and brightest 
mathematical minds. 
Galois' ideas succeeded where others had failed
(although, one must give credit to Ruffini and Abel here as well).
Like Rubik,
Galois' life story is also interesting (see, for example,
Calinger \cite{Ca} and the article by Rothman \cite{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 \cite{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 \ref{ch:perm} below), 
cryptography, and the Rubik's Cube, among others. 
Surprisingly enough, it
turns out that it is possible to use group theory
(and only the `group-theoretical
definition' of the cube - no knowledge of strategy
or special moves)
to solve the Rubik's Cube (see \S \ref{section:word}
below). 

In this book, we'll develop the basics of
group theory and 
create group-theoretical models of
Rubik's Cube-like puzzles. On the practical side,
we also discuss the
solution strategy for the Rubik's Cube in some
detail. (For those wanting to see a solution strategy now,
see section \ref{section:solution}.)
Some solution strategies are briefly
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 Rubik's Cube focus,
the approach in this book is different from
some texts:
 
\begin{itemize}

\item[(a)] there are a lot of non-standard, though relatively
elementary, group theory topics;

\item[(b)] we emphasize permutation groups via 
examples over general theory (such as Sylow theory);

\item[(c)] we present some of the basic notions 
algorithmically 
(as in \cite{Bu}); and

\item[(d)] we 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.
\end{itemize}

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 \pf and the end by \qed.
I've used the number system where a result
or example in section a.b has a labeling
of the form a.b.c. 

Chapters \ref{ch:1}, \ref{ch:2} and \ref{ch:3}
give some basic mathematical background.
Chapter \ref{ch:4} introduces some of the puzzles and some 
notation we use for them.
Except for the chapter on solutions, chapter \ref{ch:15},
the remaining chapters discuss these puzzles using
group theory, graph theory, linear algebra, or automata
(finite state machines) theory.
It must be confessed that while the earlier chapters 
can probably be followed by a good high school student,
chapters \ref{ch:advanced} and \ref{ch:advanced2} are
relatively advanced. 
They are, in my opinion, the most interesting,
and illustrate some remarkable 
ways in which the Rubik's Cube 
is connected with other branches of
mathematics, which is a continuing source of 
my fascination with the subject. 

The last chapter, chapter \ref{ch:16},
gives some indications of directions which weren't 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 don't have the answer to, it is not intended to
be complete!

\vskip .2in

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 \ref{ch:illegal}, with lots of time for 
`side trips' and other material. It is possible to 
cover the Second Fundamental 
Theorem of Cube Theory, in chapter \ref{ch:legal}, 
in one semester but it is a race against time.
For example, chapter \ref{ch:merlin} on `Merlin's 
Machine', or any uncovered sections, might be used for some very 
interesting term projects.

\vskip .2in
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
(\verb+www.sagemath.org+) there is ample documentation (a reference
manual, tutorial, email support lists, and so on) but 
it is worth taking some time here 
to explain how \sage is used in this book. 
First, you don't 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 {\tt Enter} to
see the output) and the other is the graphical
``notebook'' interface (you type a command into a ``cell''
and hit {\tt 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.
Detailed acknowledgements for \sage are on the acknowledgements page.

 
%\vskip .5in
%Added for the 2nd edition: There has been some progress on 
%the hard problems mentioned:
%Ponderable 6.5.1 has been solved by
%Werner Nickel and Peter Maier in their paper \cite{MN}.

\newpage

\pagenumbering{arabic}
\input agt2_1.tex
\input agt2_2.tex
\input agt2_3.tex
\input agt2_4.tex
\input agt2_5.tex
\input agt2_6.tex
\input agt2_7.tex
\input agt2_8.tex
\input agt2_9.tex
\input agt2_10.tex
\input agt2_11.tex
\input agt2_12.tex
\input agt2_13.tex 
\input agt2_14.tex
\input agt2_15.tex
\input agt2_16.tex
\input agt2_r.tex

%\newpage

%\ \ 

%\newpage

\printindex
\end{document}