From reid@math.berkeley.edu  Fri May  8 17:58:59 1992
Return-Path: <reid@math.berkeley.edu>
Received: from math.berkeley.edu by life.ai.mit.edu (4.1/AI-4.10) id AA26323; Fri, 8 May 92 17:58:59 EDT
Received: from digel.berkeley.edu.berkeley.edu by math.berkeley.edu (4.1/1.33(math))
	id AA21236; Fri, 8 May 92 14:58:49 PDT
Date: Fri, 8 May 92 14:58:49 PDT
From: reid@math.berkeley.edu (michael reid)
Message-Id: <9205082158.AA21236@math.berkeley.edu>
To: Dik.Winter@cwi.nl, cube-lovers@life.ai.mit.edu
Subject: Re:  Are we approaching God's algorithm?
Cc: dseal@armltd.co.uk

>  >             now how about "superflip," and also "supertwist?"
> I will try to contact him to see what he has to say about those.

of course, these aren't exactly the patterns to test.  apply your
favorite quarter turn to either of these patterns, and you're
one move closer to START.

how do i know that we're one move closer to start?  the patterns
"superflip," "supertwist" and "superfliptwist" each have the
following three properties:

1. the group of symmetries of the pattern acts transitively on the
   set of "oriented" faces of the cube.
2. the pattern commutes with the square of each face turn.
3. the pattern is NOT in the subgroup generated by the squares of
   face turns.

now suppose that a pattern with the above properties requires
N  face turns to return to START.  let  A B C  be a minimal sequence
of face turns to solve this pattern, where  A, B,  and  C  are
subsequences such that:  A  consists only of squares of face turns,
B  is a quarter turn of some face and  C  is the rest of the sequence.
we can dissect the sequence into these three parts from hypothesis 3.
from hypothesis 2, the sequences  A B C  and  B C A  have the same
effect.  finally, from hypothesis 1, the quarter twist  B  may as well
be our favorite quarter twist.

see the hoey-saxe message on "symmetry and local maxima," for a good
discussion of this idea.  (in the archives, cube-mail-1, 14 dec 1980)

my apologies if this is obvious to everyone.

on the other hand, the kociemba algorithm isn't completely symmetric.
thus it may be wise for him to test 2 patterns: "super----" followed
by  U,  and "super----" followed by  R.  the tradeoff is testing 2
patterns for being 1 move closer.  i'd say this is probably a good trade.

now to correct something misleading i posted earlier:

) i believe that the diameters of the respective coset spaces are exactly
) those numbers listed in the "Best Possible" line.  can anyone confirm
) this?  i've finally written a few programs, and those are the diameters
) i get.  i'm surprised that thistlethwaite didn't just do an exhaustive
) search on these coset spaces.  perhaps it's just a matter of not having
) the technology when he did his work (~12 years ago).

oops!  i don't mean to say "diameter" here!  these are coset spaces, so
there's no reason to suppose that (the group of automorphisms of the)
graph is vertex transitive.  what my programs calculated was the maximal
distance from the identity coset in each of these spaces.  (i am told
that the graph theory term is the "eccentricity" of the given vertex.)

mike