Date: 1 June 1983 1939-EDT (Wednesday) From: Dan Hoey@CMU-CS-A To: cube-lovers@MIT-MC Subject: Eccentric Slabism, Qubic, and S&LM Message-Id: <01Jun83.193917.DH51@CMU-CS-A> I don't know whether Isaacs or Singmaster know just what a bombshell was contained in the Cubic Circular. I am somewhat frightened at the possibilities. Section 1 discusses the history of metrics for N^3 puzzles and proposes a new one. Section 2 describes new symmetries of the generators of the 4^3 puzzle. Section 3 outlines a theory of symmetry and local maxima for the 4^3 puzzle. Section 4 indicates directions for further work. 1. Cutism, Slabism, and Eccentric Slabism ========================================= Let's start with the question that was posed by Stan Isaacs in his message of 26 May: what is a quarter-turn on the 4^3 or larger cube? On the N^3 puzzle, each set of N-1 parallel ``cuts'' divides the cube into N ``slabs''. There seem to be two straightforward metrics. The Slabist defines a move to be a turn of one slab with respect to the rest of the cube. The Cutist defines a move to be a turn of a connected part of the cube with respect to another connected part, the two parts being separated by a cut. [In the terminology I used on 2 September 1982, the Slabist counts ``slice moves'' while the Cutist counts ``twist moves.''] I have heretofore espoused Cutist theory. For one thing, it agrees with our current theories on the 3^3 in disallowing a turn of a center slice as a single move. This seems to be a good idea, since the current quarter-turn theory has the advantage of conjugate generators, which it would lack if we allowed center-slice moves. [This is presumably not a problem for Singmaster, who allows the squared moves, which are not conjugate.] Another reason for Cutism is that it makes it easier to equate positions that arise from a whole-cube move of the N^3. A third reason is that it makes the parity hack (see my message of 1 June 1982) easier. The last two reasons are for convenience only; the arguments can still be made in a Slabist formulation. But as I admitted, I solve the cube as a Slabist. Slabs are probably convenient because they minimize the degree of each generator. I casually dismissed this tawdry practicality until I was struck by Evisceration. In the course of my examination of Evisceration I have experienced an epiphany which converted me to Eccentric Slabism. I now define a move to be a turn of any slab except one whose interior contains the center of the cube. In other words, any slab except a center slice. At first glance, Eccentric Slabism looks like a hack, since there is an excluded slab only in the case of a puzzle of odd size. I believe that the truth is more complicated, but the explanation is partly beyond the scope of this note and partly beyond my knowledge. If you really want an answer I suggest you study tic-tac-toe. 2. Evisceration, Inflection, and Exflection =========================================== The (Eccentric) Slabist moves of the 4^3 puzzle form the 24-element set Q4={B,B',b,b',...,r'}, where upper-case refers to turning a side (an outslab move) and lower-case refers to turning the adjacent internal slab (an inslab move). We consider these moves as generators of G4, the ``Theoretical Invisible Group'' [Invisible Revenge, 9 August 1982] in which the inslabs turn the eight stomach cubies like a 2^3 puzzle. Thus two positions in G4 are equal if and only if all sixty-four pieces of the cube are in their home position and orientation. [Actually, this is not quite the Theoretical Invisible Group, since we do not equate positions that differ by a whole-cube move. I feel confident that the identification can be performed, but I will speak of the unidentified group here.] Consider the following permutations on Q4: Rotations: I=(FRBL)(F'R'B'L')(frbl)(f'r'b'l'), J=(FUBD)(F'U'B'D')(fubd)(f'u'b'd'), Reflection: R=(FB')(F'B)(RL')(R'L)(UD')(U'D)(fb')(f'b)(rl')(r'l)(ud')(u'd), Evisceration: V=(Ff)(F'f')(Bb)(B'b')(Rr)(R'r')(Ll)(L'l')(Uu)(U'u')(Dd)(D'd'), Inflection: N=(fb')(f'b)(rl')(r'l)(ud')(u'd), Exflection: X=(FB')(F'B)(RL')(R'L)(UD')(U'D). Permutations I, J, and R are familiar generators of M, the group of rotations and reflections of the cube. Singmaster introduced Evisceration, which consists of swapping each outslab with the adjacent inslab. I extend the list with Inflection and Exflection. Inflection consists in swapping each inslab with the inverse of its parallel inslab; Exflection swaps each outslab with the inverse of its parallel outslab. It is well known that M is a group of automorphisms on G4. Singmaster observed that Evisceration is also an automorphism. I observe that Inflection and Exflection are automorphisms, too. Thus M4, the 192-element group generated by is a group of automorphisms on G4. [Actually, since R=NX and X=VNV, M4=. The group M4 is also the automorphism group of the game of Qubic, or 4^3 tic-tac-toe.] I began to doubt Cutism when I noticed that M4 sometimes maps cut moves to pairs of cut moves. I went home last night wondering why this might be so. I nearly got to sleep before I realized the big news: M4 is Q4-transitive! Eccentric slabs are conjugate! 3. Symmetry and Local Maxima ============================ This section relies especially heavily on ``Symmetry and Local Maxima'' [14 December 1980; available as file "MC:ALAN;CUBE S&LM" on MIT-MC]. Following the argument in S&LM, consider the symmetry group of the Pons Asinorum (with the face-centers each half-twisted, as is customary). We already know Pons is M-symmetric; by examination, the symmetry group of Pons also contains Evisceration and Inflection. Thus Pons is M4-symmetric. The result is that Pons is a local maximum in G4. This is the first local maximum to be found in a close relative of Rubik's Revenge. It is not hard to show that we can dispense with fixing the Pons in space, and it is only slightly harder to carry out in general. Unfortunately, I see no way of showing that Pons is a local maximum if we ignore the stomach cubies without ignoring the corners. 4. Open problems ================ This is a pretty random collection of directions for further work. Some of these were posed in the text. The ones I think likely to be impossible are labeled (*). Conjecture: The automorphism group of the Eccentric Slabs of the N^3 puzzle is the same as the automorphism group of N^3 tic-tac-toe. I don't believe this has been rigorously done for any N>1. Stronger conjecture: The automorphism groups of the N^D puzzle and N^D tic-tac-toe are the same. (Hint: There are at least two definitions of the N^D puzzle. I think both work.) Extension: The relation between the automorphism groups is too amazing to be accidental. What is really going on here? Search: There is published literature on tic-tac-toe automorphisms; in particular the group of automorphisms of N^D tic-tac-toe is well known. I seem to recall seeing some horribly theoretical work, approaching the problem from the standpoint of algebraic geometry or some such. At that time I settled for scanning the results. Now I have questions that need a general treatment. If the world's leading expert on Qubic has his bibliography on line, I think there's a reference I'd appreciate. Actually, I'll take references from anybody and send the compilation to any requestors. Query: Why must slabism be eccentric? Query: Can Cutism be saved? Are cut moves conjugate in some sense? Easy extension: Equate positions that differ by whole-cube moves. Hard extensions (*): Equate positions that differ only internally. Equate positions that differ only in the permutation of like-colored face cubies. Problem: Prove that the Pons requires 12 quarter-turns in the 4^3 puzzle. Ditto for 12 qtw in the N^3 puzzle(*?). Prove or disprove for 4D qtw in the N^D puzzle (*). Problem: Find the Q4-transitive subgroups of M4, then list all the Q4-symmetric local maxima in the 4^3. Problem: Describe all symmetric local maxima of the N^3(*), or place useful conditions on them. Problem: Demonstrate an infinite class of local maxima (Ponses?). Final query: Did someone ask if Cubism was dead? Dan Hoey HOEY@CMUA.ARPA