From mreid@ptc.com  Sat Jan 14 17:07:00 1995
Return-Path: <mreid@ptc.com>
Received: from ptc.com (poster.ptc.com) by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA28724; Sat, 14 Jan 95 17:07:00 EST
Received: from ducie.ptc.com by ptc.com (5.0/SMI-SVR4-NN)
	id AA14825; Sat, 14 Jan 95 17:05:36 EST
Received: by ducie.ptc.com (1.38.193.4/sendmail.28-May-87)
	id AA27289; Sat, 14 Jan 1995 17:18:30 -0500
Date: Sat, 14 Jan 1995 17:18:30 -0500
From: mreid@ptc.com (michael reid)
Message-Id: <9501142218.AA27289@ducie.ptc.com>
To: cube-lovers@ai.mit.edu
Subject: more on superflip
Content-Length: 3294

recently i said:

> when searching for superflip in the face turn metric, it's
> sufficient to search through depth 17 in stage 1!

since posting this, i've realized that we can do much better.
here's my current approach.  everything below refers to the
face turn metric.  (i have similar reductions for quarter turns,
but they're not quite as good.)

proposition 1.  there is a minimal sequence for superflip of the form

                      sequence_1  sequence_2

                where  sequence_1  is in stage 1,  sequence_2  is in
                stage 2, and  sequence_1  is at most  17f  long.

proof.  consider the different possibilities for the length of a
        minimal sequence for superflip:  20f, 19f, 18f, 17f  or less.
        in the first case, we already know a maneuver of the form.
        in the second case, my discussion on thursday shows that
        we'll have such a maneuver.  in the case of  18f , we may
        suppose that the last face turned is  U , so we'll have such
        a maneuver.  and in the last case, we may take  sequence_2
        to be the empty sequence.  this proves prop. 1.

proposition 2.  there is a minimal sequence for superflip of the form

                    R1  sequence_1  sequence_2

                where  sequence_1  is in stage 1,  sequence_2  is in
                stage 2, and  sequence_1  is at most  16f  long.

proof.  consider the maneuver given by prop. 1.  by applying one of
        the 16 symmetries that fix the  U - D axis, we may suppose
        that the first turn of  sequence_1  is either  U1, U2, R1,
        or  R2.  in the case of

                    U1  sequence_1  sequence_2,

        replace this by

                    sequence_1  sequence_2  U1,

        and try again.  handle the cases starting with  U2  and  R2
        similarly.  we will either exhaust the stage 1 part of the
        sequence (which is impossible, since superflip isn't in
        the subgroup of stage 2) or we'll wind up with a manuever
        starting with  R1 , as desired.  this proves prop. 2.

there's still some more symmetry left to exploit.

proposition 3.  there is a minimal sequence for superflip of one of the
                forms

                          R1 F1  sequence_1  sequence_2,
                          R1 F2  sequence_1  sequence_2,
                          R1 F3  sequence_1  sequence_2,
                          R1 U1  sequence_1  sequence_2,
                          R1 U2  sequence_1  sequence_2,
                          R1 U3  sequence_1  sequence_2,
                          R1 L1  sequence_1  sequence_2,   or
                          R1 L3  sequence_1  sequence_2,

                where  sequence_1  is in stage 1,  sequence_2  is in
                stage 2, and  sequence_1  is at most  15f  long.

proof.  by applying the symmetry  C_R2  if necessary, we may suppose
        that the second turn of the maneuver given by prop. 2 is one
        of  F1, F2, F3, U1, U2, U3, L1, L2  or  L3.  this gives nine
        cases.  in the case

                R1 L2  sequence_1  sequence_2,

        replace this by

                R1  sequence_1  sequence_2  L2

        and try again.  this proves prop. 3.


i have these cases running right now, and i hope to have results soon!

mike