From:

~~~ ~~~ Subject:

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 UL 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 BD 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 UL 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 BD 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 BD 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 UU 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 RB 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 DL 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)