From:

~~~ Subject:

Date: 31 Aug 1982 1022-PDT From: ISAACS at SRI-KLCould you explain to me how you got the formula of your message

of 23 Aug.

There are SF different shallow hypermoves and DF different deep

hypermoves, and two similar hypermoves in succession can be

collapsed into one. The formula expresses the number of

alternating sequences of length at most four, which is the sum of

the ``Number'' column below.

Length Type Number 0 1 1 S SF 1 D DF 2 SD SF * DF 2 DS SF * DF 3 SDS SF^2 * DF 3 DSD SF * DF^2 4 SDSD SF^2 * DF^2 4 DSDS SF^2 * DF^2

I can see more-or-less what you're doing, but I haven't been

able to parse the formula.

Well, I did leave out the multiplication signs.

Also, I haven't seen your notation before. I take it that "U3"

is equivalent to "D1'", except hold the D1 in place.

Right. I used this notation in "Lower Bounds for the 4x4x4" on 2

June and "Invisible Revenge" on 9 August.

How do you represent half twists? Only by two quarters, or is

there a shorthand?

There is U3^2, not much of a shorthand. For the U slice move, I

hinted at U21'.

From a group theory perspective, is it easier to talk about

hypermoves than slice moves?

Hypermoves are a curiosity that Jim Saxe dreamed up. Any sequence

of depth 1 (or 3) moves is a single hypermove, as is any sequence

of depth 2 moves. I assume you mean to ask whether it's easier to

talk the way I usually talk, in terms of what I will call "twist

moves" to distinguish them from "slice moves".

The question boils down to what set of generators (moves) you want

to use when counting the length of a process. This topic was

endlessly rehashed in 1980 when people were trying to decide

whether to call a half-twist a single move or two. Jim Saxe nearly

sent a message in 1980 about using only two generators to solve

Rubik's cube. [As I recall, computer failure trashed the message

and he never retyped it.] Certainly we can all do slices and

half-twists. The question is how many moves to charge for such an

operation. The richer the set of generators, the fewer the number

of moves, but the more complex the explanation of the generators.

I use the "quarter-twist" convention for the 3^3. The generators

are 90-degree rotations of faces. This seems natural, because it

is the minimal set that satisfies the following criteria.

1. Every possible cube position can be created using these

generators, up to whole-cube moves. This is a basic

criterion.

2. The inverse of every generator is a generator. This is

necessary so that we have a metric.

3. Any position that can be reached by performing part of a

generator is a generator. This criterion ties the

mechanical operations used in the cube to the

permutation group. Otherwise we could have generators

like FUF and F'U' and perform F with their composition.

Charging two moves for F in that circumstance is

somewhat bizarre.

4. Every M-conjugate of a generator is a generator. This is

an aesthetic consideration. We could leave out the D

and D' twists and still solve the 3^3, but that breaks

up the symmetry of the puzzle.

Why do I want the generator set to be minimal? Well, we could make

it maximal, but then we would have ``over 3 billion'' generators.

What I am looking for is a canonical set, and minimality seems like

the best way of choosing among metrics. Thus we exclude slice

moves as generators because they are not necessary.

For the 3^3, this set is particularly fortunate, because the

converse of criterion 4 holds: Every two generators are

M-conjugate. This allows us to identify some local maxima without

long computations (14 December 1980) and to tighten lower bounds

using parity principles (9 January 1981).

Will that also be true on the 5^3, 6^3, etc?

I would just as soon stick with a compatible metric. This is not

to say that there cannot be abbreviations for these moves, simply

that for the sake of asking ``how many moves does this take'' we

count the number of quarter-twists.

We unfortunately don't have the converse of criterion 4 for cubes

larger than 3^3. For the 4^3, for instance, there are two flavors

of move: deep and shallow. Dave Plummer (26 September 1981)

described certain positions of the 4^3 as local maxima, but I have

convinced him that we cannot demonstrate the truth of that

assertion using known techniques other than exhaustive search. My

note of 2 June was able to use only one kind of parity in the lower

bound argument. Both problems are due to the lack of the converse.

From a solving perspective, it seems clumsy.

I'll agree that the generators are few in this scheme, but it is

possible to generate macros. For instance, consider describing a

slice move on the 3^3 cube. Singmaster uses the notation Fs to

denote the F1B1' = F12'3 slice move. We can now also talk about

the F12' slice move, which is how everyone actually does the move.

I think this is much easier to remember than Allan Wechsler's IJK

notation (introduced 18 July 1980) or Doug Landauer's HPS notation

(27 August 1980) for dealing with whole-cube moves.

I'm still not too happy about the state of RubikSong, but I think

it's a matter of human engineering, and I like to stick with the

mathematics.