[next] [prev] [up] Date: Wed, 01 Jun 83 19:39:00 -0400 (EDT)
[next] [prev] [up] From: Dan Hoey <Hoey@CMU-CS-A >
~~~ ~~~ [up] Subject: Eccentric Slabism, Qubic, and S&LM

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 <I,J,R,V,N,X> is a
group of automorphisms on G4. [Actually, since R=NX and X=VNV,
M4=<I,J,V,N>. 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


[next] [prev] [up] [top] [help]