Date:  9 December 1980 1638-EST (Tuesday)
From: Dan Hoey at CMU-10A
To: McKeeman.PA at PARC-MAXC
Subject:  Re: A Proposed Definition of Symmetry
CC: Cube-Lovers at MIT-MC
In-Reply-To:  McKeeman.PA@PARC-MAXC's message of 8 Dec 80 20:03-EST
Message-Id: <09Dec80 163821 DH51@CMU-10A>

Given a subroup G of permutations, we may define a cube position P to be
G-symmetric if every permutation in G preserves P up to color
relabelling.  Explicitly, if x and y are two facelets which have the
same color in position P, then g(x) and g(y) also have the same color
in P.

Consider, for instance, the group R of whole-cube moves.  The Pons
Asinorum is R-symmetric.  Any whole-cube move moves the set of blue
facelets to positions occupied (before the move) by facelets of some
single other color.  In fact, even if the cube were reflected, this
would be true.  This can be verified by looking at one blue facelet of
the cube and realizing that you know from that alone where all the
other blue facelets are.  Letting the M denote the group composed of R
augmented by the set of whole-cube mirror reflections.  The Pons
Asinorum is also M-symmetric.

McKeeman has stated that any R-symmetric position (with the exception
of the solved state) is a local maximum.  I do not know if this is true,
but I can show that any M-symmetric position (with the same exception)
is a local maximum.

Consider a robot cubenik which knows how to do whole-cube moves, but
can only QTW the "up" face.  Clearly, this robot has no problems,
because it can move any face to the top, perform U or U', and move it
back.  The robot could get along without U' by doing U^3 instead, but if
we're counting QTWs it's not going to win any races.  Solution?  Build a
transdimensional robot which can perform whole-cube reflections.  This
robot performs U' by reflecting the cube, performing U, and reflecting
it back.  The point of this parable is that for any two QTWs x and y,
there is an element m in M for which y = (m x m').  Note also that for
any m in M, the permutation (m x m') is a QTW.

Let P be an M-symmetric position, and let (x1 x2 ...  xn) = P' be the
shortest solution of P in QTWs.  Assume that P is not the solved
position, so n > 0.  For any QTW y, I will demonstrate an n-step
solution of P which begins with y.  Write y = (m x1 m').  Since P is
M-symmetric, (P m) is a relabelling of P.  This implies that (P m P')
and therefore (P m P' m') are relabellings of I.  Therefore the sequence
((m x1 m') (m x2 m') ...  (m xn m')) = (m P' m') will essentially solve
P, up to a whole-cube move.  The existance of an n-step solution
starting with an arbitrary QTW y implies that P is a local maximum.

There is a twelve-element subgroup T of M which will suffice instead of
M for this argument.  Representing elements as permutations of faces, T
is generated by the permutations (represented as cycles):

	(F L U)(R D B)	-- Rotating the cube about the FLU-RBD axis
	(F B)(U R)(L D) -- Rotation exchanging corners FLU and RBD
	(L U)(R B)	-- Reflection in the LU-RB plane

Question:  Does there exist a position other than the solved position
and the Pons Asinorum which is T-symmetric or R-symmetric?