Date: 14 December 1980 1916-EST (Sunday) From: Dan Hoey, Jim Saxe To: Cube-lovers at MIT-MC Subject: Symmetry and Local Maxima (long message) Reply-To: Dan Hoey at CMU-10A Message-Id: <14Dec80 191649 DH51@CMU-10A> 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 from Q to Q defined by the rule (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 (*)(q) is definitionally equivalent to ((q)). Call this group . The function <> which maps each element m of M to the corresponding element of 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, (*)(q) = ((q)) = n' (m' q m) n = (m n)' q (m n) = (q) The isomorphism <> maps each subgroup of W of M into a subgroup of , while is in turn a subgroup of the group of all permutations of Q. If W is Q-transitive, then is transitive on Q in the usual group-theoretic sense that for any two elements p and q of Q there is some element of such that (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 be a transitive subgroup of . We must show that has a multiple of twelve elements. Let q be any element of Q and let V be the subgroup of containing all elements of such that (q) = q. For any element of , the right coset V of V is the set {* | is in V} Since (*)(q) = ((q)) is equal to (q) iff (q) = q, V consists of precisely those elements of which map q to (q). All cosets must have the same size, so the number of elements of must be a multiple of the number of cosets, which is the number of distinct values of (q). Since 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)