From:

~~~ ~~~ Subject:

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