Symmetry and Local Maxima
-- Dan Hoey
   Jim Saxe

1. Introduction
===============

In this note, we attempt to give a uniform treatment of the
issues raised in the recent discussions of symmetry and local
maxima. We have attempted to restate and justify the correct
observations on these subjects that have been made in mail to
cube-lovers in recent days and also to refute a number of incorrect
ones. We include a description of 71 local maxima, which we believe
to be all of the local maxima that can be proven using known
techniques other than exhaustive search.

We let G denote the "Rubik group", consisting of all
transformations of the cube which can be achieved by twisting
faces. G does not include transformations which require movements
of the whole cube. Also, G does not take account of the
orientations of the face centers. We will defer discussion of the
Supergroup, in which face center orientations are significant (but
whole-cube motions still excluded), to Section 5 of this message.
We will sometimes (particularly towards the end of this message)
take the liberty of identifying a transformation with the position
reached by applying that transformation to SOLVED.

We let Q = {U, D, L, R, F, B, U', D', L', R', F', B'} be
the set of all possible quarter-twists. Q is a subset, but not a
subgroup, of G. The set {U, D, L, R, F, B} of all clockwise
quarter-twists is called Q+, and the set {UU, DD, LL, RR, FF, BB}
of all half-twists is called Q2. The "length" of an element s of G
(denoted |s|) is the length of the shortest sequence of quarter-
twists whose product is s. The "distance" between two elements, s
and t, of G is the length of the shortest r such that t = s r. Note
that the length of s is same as the distance between s and the
identity permutation. Note also that we are measuring distance in
the "quarter-twist metric." We defer discussion of the "half-twist
metric" to Section 5.

Two elements, s and t, of G are "neighbors" if there is
some q in Q such that t = s q (i.e., if the distance between s and
t is 1). An element, s, of G is said to be a "local maximum" if no
neighbor of s is longer than s. It is a consequence of parity
considerations that all neighbors of any local maximum, s, have the
same length, namely |s| - 1. Conversely, any element s of G (except
for the identity permutation) whose neighbors are all equally long
must be a local maximum. [Anyone who *still* doesn't understand why
neighbors cannot be equally long in the quarter-twist metric should
either send mail to one of the authors, or learn about even and odd
permutations from a book on group theory and think about how a
quarter-twist permutes the positions of the corner cubies.]

2. Symmetry
===========

It has been asserted that any "symmetric" element of G must
have all its neighbors equally long and must therefore be a local
maximum (or the identity). The first occurrence of this assertion
in cube-lovers mail was by Alan Bawden in his message of 10 Sep
1980, 11:09 pm PDT. The recent spate of messages on this subject
has made it clear that Bawden's notion of symmetry was not clearly
defined. In what follows, we make the notion of symmetry more
precise and categorize those kinds of symmetry for which the above
assertion is correct.

We let M denote the group generated by all rotations and
reflections of the whole cube and C denote the subgroup of M which
contains only the rotations. C has 24 elements (any of the six
faces can be put on top, after which any of the four adjacent faces
can be put in front, uniquely determining the positions of the
remaining faces). M has 48 elements (six choices for U, then four
for F, then two for L). [Our use of G and C agrees with that in
McKeeman's note of 8 Dec 1980, 17:03 PST. Hoey's note of 9 Dec
1980, 16:38 EST used the letter R rather than C for the latter
group, a practice which we hereby retract.]

Let G+M be the group of all transformations achievable by
any sequence of face twists and/or whole cube moves, including
reflections. Note that G is a subgroup of G+M and that the elements
of G are precisely those elements of G+M which leave the positions
of the face centers fixed (to forestall possible confusion, we
remark, at certain risk of belaboring the obvious, that the phrases
"face center positions" and "face center orientations" have
different meanings). We say that two elements, s and t, of G+M are
"M-conjugates" of each other if there exists some m in M such that
t = m' s m. We assert the following results without proof because
they are obvious.

Fact 1: Any M-conjugate of an element of Q is an element of Q,
and any M-conjugate of an element of G is an element of G.

Fact 2: If two elements of G are M-conjugates, they are equally
long.

[Anyone who does not consider the preceding facts obvious is urged
to direct further inquiries to one of us rather than bothering
everyone on the mailing list. The same goes for anyone who believes
that any other assertions made in this message are in error; this
procedure will help to reduce either duplication of erratum notices
or proliferation of false counterexamples.]

Let W be a subgroup of M. Then an element s of G is said to
be W-symmetric iff s w = w s (or, equivalently, w s w' = s) for
every w in W. [This definition is equivalent to Hoey's definition
(9 Dec 1980, 16:38 EST) as we will now show. By a "recoloring" of
the cube, we intuitively mean an operation which "consistently"
changes the colorings of all facelets of the cube. Note that the
permutation performed by a recoloring depends not only on the
chosen mapping of colors to colors, but also on the configuration
the cube is in when we start recoloring. Thus, a particular mapping
of colors to colors doesn't appear to correspond to any fixed
element of G+M. This is not a particularly satisfying situation. We
can rectify this situation by always doing the recolorings when the
cube is in the SOLVED state, that is, by thinking of recoloring a
configuration as pre-multiplication of the permutation that
achieves that configuration (from SOLVED) by a recoloring of SOLVED.
More succinctly, two elements, s and t, of G+M are equivalent up to
recoloring iff there is some m in M such that t = m s. Thus, by
Hoey's definition, an element s of G is W-symmetric iff for every w
in W there is some m in M such that
s w = m s.
But s doesn't move the face centers. So the only way m can be chosen
so that m s will leave the face-centers in the same places as s w is
to pick m = w.]

3. Transitivity
===============

For which choices of W can we guarantee that W-symmetric
patterns are local maxima? To approach this question, we introduce
the notion of Q-transitivity. Recall that Q is the set (not a
group) of all quarter-twists. We define a subgroup W of M to be
"Q-transitive" iff for each two elements p and q of Q there is some
w in W such that q = w' p w. (Q+-transitivity and Q2-transitivity
are defined analogously) We now come to our principal result:

Theorem 1: Let W be any Q-transitive subgroup of M and let s be
any W-symmetric element of G. Then any two neighbors of s
are m-conjugates of each other.

   Proof:  Let p and q be any two elements of Q.  We must show that
       sq is an M-conjugate of sp.  Since W is Q-transitive, produce
       some w in W such that q = w' p w.  Thus,
		s q = s w' p w
		    = w' (s p) w.
       Since W is a subgroup of M, w must be an element of M.  So
the definition of M-conjugacy is satisfied.
Q.E.D.

Corollary: Let W be any Q-transitive subgroup of M and let s be
any W-symmetric element of G other than the identity. Then
s is a local maximum.

If an element s of G is both V-symmetric and W-symmetric,
where V and W are subgroups of M, then it follows that s is
V+W-symmetric, where V+W is the closure of the union of V and W
(that is, V+W is the group of all elements of M which can be
expressed as the product of a sequence of elements of the union of
V and W). Thus we may unambiguously define the "symmetry group" of
any element s of G as the largest subgroup W of M such that s is
W-symmetric. The elements of this group will be precisely those
elements of M which commute with s. To see that this set of
elements forms a group, simply note that for any elements v and w
of M that commute with s,
1. (v w) s = v (w s) = v (s w) = (v s) w = (s v) w = s (v w),
and
2. v' s = v' s v v' = v' v s v' = s v'.

By the corollary to Theorem 1, any element of G (except the
identity) whose symmetry group is Q-transitive is a local maximum.
In order to find local maxima, we will first find the Q-transitive
subgroups of M. The search for Q-transitive subgroups is simplified
by realizing that the number of elements of any Q-transitive
subgroup W must be a multiple of twelve. To show this, it will be
useful to introduce another way of looking at the group M, namely
as a group of permutations on the set Q. We associate each element
m of M with a 1-1 function <m> from Q to Q defined by the rule
<m>(q) = m' q m for all q in Q.
These functions form a group under the operation of functional
composition, which we will write in the left-to-right manner so
that (<m>*<n>)(q) is definitionally equivalent to <n>(<m>(q)). Call
this group <M>. The function <> which maps each element m of M to
the corresponding element <m> of <M> is an isomorphism as may be
seen by noting that for any two elements m and n of M and for any
element q of Q,
(<m>*<n>)(q) = <n>(<m>(q))
= n' (m' q m) n
= (m n)' q (m n)
= <m n>(q)
The isomorphism <> maps each subgroup of W of M into a subgroup <W>
of <M>, while <M> is in turn a subgroup of the group of all
permutations of Q. If W is Q-transitive, then <W> is transitive on
Q in the usual group-theoretic sense that for any two elements p
and q of Q there is some element <w> of <W> such that <w>(p) = q.
This may be taken as motivation/"justification" for our use of the
term "transitive" in the former context. It is a well-known result
of group theory that every transitive group of permutations on a
set X has a number of elements that is a multiple of the number of
elements of X. This proves our claim that each Q-transitive
subgroup of M has a multiple of twelve elements. [For those not
familiar with the group-theoretic result mentioned above, the proof
for this specific case goes like this. Let <W> be a transitive
subgroup of <M>. We must show that <W> has a multiple of twelve
elements. Let q be any element of Q and let V be the subgroup of
<W> containing all elements <v> of <W> such that <v>(q) = q. For
any element <w> of <W>, the right coset V<w> of V is the set
{<v>*<w> | <v> is in V}
Since (<x>*<w>)(q) = <w>(<x>(q)) is equal to <w>(q) iff <x>(q) = q,
V<w> consists of precisely those elements of <W> which map q to
<w>(q). All cosets must have the same size, so the number of
elements of <W> must be a multiple of the number of cosets, which
is the number of distinct values of <w>(q). Since <W> is transitive
on Q, the set of such values is all of Q, which has twelve
elements.]

We generated the 98 subgroups of M by computer, and found
that only 9 of them had a multiple of 12 elements. We examine these
subgroups below. In the preceding proof, we found it useful to
think of elements of M as permutations on the set Q. In what
follows, we will sometimes find it useful to think of elements of M
as permutations of the set of face center positions. An element of
M will be called "even" or "odd" according as it induces an even or
odd permutation on the six face centers. Also, we refer to elements
of M which are not rotations of the cube as "reflections". This
applies even to permutations which are not simple geometric
reflections but must be expressed as the composition of a
reflection and a rotation. An example is the element of M which
permutes face centers in the cycle (U,B,R,D,F,L).

The largest subgroup of M is, of course, M itself (48
elements). M has three subgroups of size 24: the group C of
rotations of the cube, the group of all even elements of M, which
we call AM (for alternating M), and the group of elements which are
in either both or neither of C and AM. We will call this third
group H. Thus the group H contains the even rotations and the odd
reflections. M has five subgroups of size 12. One of these is the
group of all even rotations, which we call AC. The other four are
of the kind called "T" by Hoey in his message of 9 Dec 1980, 16:38
EST (corrected by Bawden, same date, 23:57 EST). Let Z be any of
the four long diagonals of the cube (e.g., UFL-DRB). Then T(Z) is
the contains all elements of M which map the corner cubies at the
ends of Z either to themselves or to each other. Of these nine
groups, all except C and AC are Q-transitive.

4. A Catalog of Local Maxima
============================

In this section, we examine the seven Q-transitive subgroups of M,
and describe the 72 corresponding symmetric positions. In general,
given a geometric interpretation of a subgroup W of M, verifying
that a position is W-symmetric is immediate, and no proof will be
given. To prove that our catalog contains all W-symmetric positions
is more difficult, and we defer this to a later message.

There are four M-symmetric positions: SOLVED, the Pons
Asinorum (reached by RRLL UUDD FFBB), SOLVED with all edges flipped
(Bawden, 9 Dec 1980, 23:57 EST), and the Pons Asinorum with all
edges flipped. The Pons Asinorum is interesting in that it is our
only example of a PROVEN local maximum which has been PROVEN NOT to
be a global maximum (it is known to have a length of at most 12,
while the global maximum must be longer because |G| > 12^12). This
was pointed out by Plummer (7 Dec 1980, 07:24 EST).

The only AM-symmetric elements of G are those which are
also M-symmetric. Since the symmetry group of a position is the
largest subgroup W of M such that the position is W-symmetric,
there is no position which has AM as its symmetry group.

Plummer (10 Dec 1980, 23:27 EST) has already presented an
example of an H-symmetric position which is not M-symmetric. The
position is SOLVED with adjacent corners rotated in opposite
directions. Another position, whose H-symmetry leads to our choice
of nomenclature, is shown below.

U U U
D U D
U U U

	L L L  F B F  R R R  B F B
	R L R  F F F  L R L  B B B
L L L  F B F  R R R  B F B

D D D
U D U
D D D

There are two such "six-H" positions; composing the two yields the
Pons Asinorum. This gives four possibilities for edge cubie
positions. The corners of an H-symmetric position may be in any of
three orientations, all home, Plummer's configuration, or Plummer's
configuration with the twists reversed. In any position, the edges
may all be flipped or not. Composing the choices yields twenty-four
H-symmetric positions, twenty of which are not M-symmetric.

There are four groups of the form T(Z). To make our
presentation more specific, we will fix Z as the (UFL-DRB)
diagonal. We define the "girdle" of the cube as the set containing
all the corner cubies other than UFL and DRB and all edge cubies
which are NOT adjacent to either UFL or DRB. Thus,
Girdle = {ULB, LB, DBL, DL, DLF, DF,
DFR, RF, URF, UR, UBR, UB}
A position which is T-symmetric but not M-symmetric (T has no
proper supergroups in M except for M itself) may be obtained by
flipping all edges on the girdle, as shown.

U B U
U U R
U U U

L L L  F F F  R U R  B U B
B L L  F F R  F R R  B B L
L D L  F D F  R R R  B B B

D F D
L D D
D D D

Also, each edge on the girdle may be swapped with the diametrically
opposite edge, provided that the corners on the girdle are swapped
with their opposites as well.

R D D
U U D
U U B

D L L  F F D  L L F  L F F
R L L  F F B  L R R  B B F
R R B  R B B  U R R  B B U

U U L
U D D
F D D

These positions may be composed with each other and with the four
M-symmetric positions to yield sixteen T-symmetric positions,
twelve of which are not M-symmetric. Counting the positions
symmetric with respect to the four different T groups yields 48
positions whose symmetry groups are T groups.

This completes the catalog of positions with Q-transitive
symmetry groups. Summarizing the numbers of positions of each kind,
we have

M-symmetric					 4
AC-symmetric but not M-symmetric	 4-4  =  0
H-symmetric but not M-symmetric     24-4  = 20
T-symmetric but not M-symmetric  4*(16-4) = 48

for a total of 72 positions, one of which is the identity and 71 of
which are local maxima.

5.  Generalizations
===================

The group of whole cube rotations, C, is Q+-transitive, but
not Q-transitive, because U = c U' c' has no solution for c in C.
This means that McKeeman's suggestion (8 Dec 1980, 17:03 PST) that
C-symmetry was a sufficient condition for being a local maximum is
not an immediate corollary of Theorem 1. However, it happens that
all C-symmetric positions are also M-symmetric and they are
therefore local maxima with the exception of the identity. Thus
McKeeman's claim turns out to be true "by accident". However, the
case for the Supergroup is a different story.

Analysis of the Supergroup, in which the orientations of
the face centers are significant, is trivial given the analysis for
G. The only operations on the face centers which yield Q-transitive
symmetry groups are to leave them all alone or two rotate them all
by 180 degrees. Thus there are a total of 72 * 2 = 144 elements of
the Supergroup which have Q-transitive symmetry groups. One of
these is the identity and the other 143 are local maxima.
Considering face orientations as significant also allows us to
construct a position which is C-symmetric but not M-symmetric,
namely Big Ben, the position reached from SOLVED by turning all the
face centers 90 degrees clockwise. Big Ben is a good candidate for
a counterexample (in the Supergroup) to McKeeman's (8 Dec 1980,
17:03 PST) suggestion that C-symmetric positions are local maxima.
Possibly Big Ben is a local maximum, but it sure isn't obvious to
us that, say, U and U' will lead to positions equally near to
SOLVED).

Those who are interested in counting half-twists as single
moves may be pleased to hear that all 71 (143 in the Supergroup)
positions described above are also local maxima in the half-twist
metric. To see this, first note that every Q-transitive subgroup of
M is also Q2-transitive. This means that for any position p among
those 71 (or 143), all positions reached by quarter-twists from p
are M-conjugate (and thus equally far from SOLVED) and all positions
reached by half-twists are also M-conjugate. The positions in one
of these two sets must all be one step closer to SOLVED (in this
metric) than p. The positions in the other set cannot be further
from SOLVED than p since they are only one move away from positions
in the first set. Note that this proof depends on BOTH
Q-transitivity and Q2-transitivity. We do NOT make the claim that
any position whose symmetry group is Q2-transitive must be a local
maximum in the half-twist metric (in fact, we suspect that the
six-spot pattern mentioned below is a counterexample).

6.  On Conjectures
==================

The point of this section is not to make conjectures, but
to examine conjectures which have recently appeared in the light of
our results. As an example, we will first discuss a conjecture that
has not been made, but which would likely have been baldly stated
as fact had anyone thought to do so.

"Of course, the inverse of a local maximum is also a local
maximum." Easily said, but is it true? All local maxima we know
about have Q-transitive symmetry groups, and the symmetry groups of
an element and its inverse are equal. But suppose the local maximum
were not symmetric. Consider the position reached from SOLVED by
performing the twists (U F F). From this position, either F or F'
will move the cube closer to SOLVED. From its inverse, (F' F' U'),
only U will move closer to SOLVED. Is it not conceivable that from
some position, any of the twelve twists would move closer to SOLVED,
yet only eleven or fewer would move its inverse closer? Such a
position would be a counterexample to the first statement of this
paragraph. Of course, the example we provide is not a local
maximum, and indeed there may exist no local maxima except the
(symmetric) ones we have found. But there is also no reason to
believe they can't exist, and there is no reason to believe that
their inverses are local maxima. Of course, the inverse of a global
maximum is also a global maximum.

The symmetry group of a Plummer cross has six elements and
is the intersection of H with T(Z) for an appropriate choice of
diagonal Z. This group is not Q-transitive, but is Q2-transitive.
Consequently if the algorithm presented by Saxe in his message of 3
Dec 1980, 00:50 EST, is optimal, then the Plummer cross is a local
maximum. The reason for this is that Saxe's algorithm ends with a
half-twist. This means that, if the algorithm is optimal, then, by
virtue of the Q2-transitivity of the symmetry group, performing any
half-twist on a Plummer cross brings you two qtw closer to SOLVED.
This implies that performing any quarter-twist on a Plummer cross
would bring you one qtw closer to SOLVED, since the quarter-twist
could be continued into a half-twist for a total gain of two qtw.
This observation (Saxe's algorithm optimal => Plummer cross a local
maximum) was first made by David Plummer (5 Dec 1980, 20:29 EST),
who offered a slightly different, but correct, proof. We emphasize
that this is all based on the purely speculative conjecture that
Saxe's algorithm is optimal. The Plummer cross is NOT known to be a
local maximum merely by virtue of its symmetry, Greenberg's (bogus)
statement of 7 Dec 1980, 12:18 EST ("Yet, we know, intuitively,
that CP is 'highly symmetric', and it is a local maximum.")
notwithstanding. To drive this point home, consider the six-spot
configuration (Pavelle, 16 Jul 1980, 20:51 EDT) produced by moving
(L R' F B' U' D L R'). This position has exactly the same symmetry
group as the Plummer cross, but is not a local maximum. Any of the
six quarter-twists L', R, F', B, U, or D' will bring you closer to
SOLVED (obvious), any of the other six quarter-twists will take you
further away (based on exhaustive search by computer). An even more
symmetric position is the twelve-L's [not to be confused with
Singmaster's less symmetric but visually similar 6-2L, obtained
from SOLVED by (F B U D R' L' F B)]:

L R R
L U R
L L R

B F F  U U U  F B B  U U U
B L F  U F D  F R B  U B D
B B F  D D D  F F B  D D D

L R R
L D R
L L R

The symmetry group of this position is AC, the group of even
rotations. AC is Q+-symmetric, so all clockwise twists have the
same effect, and all counterclockwise twists have the same effect.
If the two sets of neighbors should happen to have the same
lengths, then this position would be a local maximum. Need we say
that there is no reason to believe this to be the case?

Michael Aramini (7 Dec 1980, 01:08 EST) mentions the
possibility that two maxima might be one half-twist apart in the
half-twist metric. This was claimed impossible by Plummer (7 Dec
1980, 07:24 EST). We do not follow the reasoning, and we conjecture
that he misread "half" as quarter and then mistyped "quarter" as
half. We also do not see anything to prevent two (local or global)
maxima in the half-twist metric from being a quarter-twist apart or
two maxima in the quarter-twist metric from being a half-twist
apart. Parity considerations do not stand in the way of such
occurrences and, while none of the known (symmetric) local maxima
are so close to each other, we have no proof that either local or
global maxima must be symmetric. We have no proof that such closely
neighboring maxima (or any non-symmetric maxima at all) *do* exist,
either.

While we know 71 local maxima, we know only 25 distinct
ones up to M-conjugacy (3 having symmetry group H, 12 having
symmetry group T, and 10 [yes, 10] having symmetry group H).
McKeeman (6 Dec 1980, 16:42 PST) has correctly (provided we
substitute our corrected definition of symmetry) noted that, if we
could show that maxima had to be symmetric, then the maximum of the
best known solutions to these configurations would bound the length
of the global maximum. Unfortunately, we have no proof of this
conjecture, nor any strong reason to think it true.

Dan Hoey (Hoey @ CMU-10A)
Jim Saxe (Saxe @ CMU-10A)