From cube-lovers-errors@mc.lcs.mit.edu Sun Aug 2 17:46:24 1998
Return-Path:
Received: from sun28.aic.nrl.navy.mil by mc.lcs.mit.edu (8.8.8/mc) with SMTP
id RAA08130; Sun, 2 Aug 1998 17:46:24 -0400 (EDT)
Precedence: bulk
Errors-To: cube-lovers-errors@mc.lcs.mit.edu
Mail-from: From cube-lovers-request@life.ai.mit.edu Sun Aug 2 08:47:54 1998
Date: Sun, 2 Aug 1998 08:47:44 -0400
From: michael reid
Message-Id: <199808021247.IAA08734@cauchy.math.brown.edu>
To: cube-lovers@ai.mit.edu
Subject: superflip composed with four spot
with my new optimal solver, i can show that the position
superflip composed with four spot
is exactly 26 quarter turns from start. this gives a new lower bound
for the diameter of the cube group. the previous lower bound, 24q, was
from the position superflip, and was first established by jerry bryan.
let F2 B2 U D' R2 L2 U D' be our choice of orientation of
four spot. although four spot is not central, the position
F2 B2 U D' R2 L2 U D' C_U2
moves only face center cubies: (F, B) (R, L). (here C_U2 denotes
whole cube rotation by 180 degrees about the U-D axis.) since quarter
turns do not move face center cubies, we see that the sequence above
commutes with any sequence of quarter turns. the same is also true
for
superflip . four spot . C_U2
in terms of singmaster's fixed face model, this means that we can
cyclically shift a maneuver for superflip composed with four spot,
but the part that is cyclically shifted gets conjugated by the cube
rotation C_U2. for example:
(B U2 L) (U' D L2 F2 R2 B U2 R' L' D R2 D F2 U R2 D B)
creates this position. if we cyclically shift the first three twists
to the end, we get another maneuver for this position:
(U' D L2 F2 R2 B U2 R' L' D R2 D F2 U R2 D B) (F U2 R)
this observation about cyclic shifting enables us to prove
proposition 1. superflip composed with four spot is a local
maximum in the quarter turn metric.
proof. we need to show that any quarter turn takes us closer to
start. the 12 different twists split up into two different
types under the symmetry of this position: {U, U', D, D'}
and {R, R', F, F', L, L', B, B'}. we claim that any maneuver
for superflip composed with four spot must contain twists of
both types. a maneuver consisting only of twists in
{U, U', D, D'} clearly cannot produce this position. also,
a maneuver consisting only of twists in
{R, R', F, F', L, L', B, B'} cannot flip any edges. thus
both twist types must occur. now consider a minimal
maneuver for superflip composed with four spot. we may
cyclically shift (and apply symmetry) so that the last twist
is U'. thus, applying U cancels this last twist and
brings us closer to start. similarly, we can cyclically shift
to get a minimal maneuver ending with R', so applying R
also brings us closer to start. since any twist is equivalent
to U or R , we have proved local maximality. qed
the significance of this proposition is that this is the first case
beyond the hoey-saxe local maxima in which we can prove local
maximality without computer searching. (please correct me if i'm
wrong about this.)
dan hoey noted (a long time ago) that the position four spot is a
local maximum. however, i don't see that this can be proved without
computer search. the sticking point is that four spot can be achieved
using only {R, R', F, F', L, L', B, B'}. however, no minimal maneuver
consists only of these twists, a fact determined by computer search.
similar to the transformations for superflip, we have three
transformations to apply to maneuvers for superflip composed with
four spot.
we may conjugate by any of the 16 cube symmetries that fix
the U-D axis.
we may cyclically shift the maneuver, as described above.
we may invert the maneuver.
proposition 2. by using the three transformations above, any maneuver
for superflip composed with four spot can be transformed
into one that begins with one of the six sequences
R U R' U D R' U F'
R' U R' R' U B' R' U L'
proof. as shown in prop. 1, any sequence for superflip composed with
four spot contains both types of twists. thus, the two types
occur as consecutive twists. by cyclic shifting, and applying
symmetry, we may suppose that the first two quarter turns are
either R U or R' U. (this would already be enough reduction
for my program). we can cut down the case R' U further.
there are eleven possibilities for the third quarter turn;
only U' is not allowed. the case R' U U = R' U2 is
equivalent under symmetry to R U2, which is part of the case
beginning with R U. the case R' U D' is equivalent under
symmetry to R D' U = R U D', again part of the case beginning
with R U. the case R' U B inverts to B' U' R, and this is
equivalent to R U B', which is part of the case beginning with
R U. similarly, the cases beginning with R' U R , R' U F
and R' U L invert to R U R' , R U F' and R U L',
respectively. this leaves only the sequences listed above. qed
my program exhaustively searched the positions
superflip. four spot . R U through 22q and
superflip. four spot . R' U D \
superflip. four spot . R' U F' \
superflip. four spot . R' U R' > all through 21q
superflip. four spot . R' U B' /
superflip. four spot . R' U L' /
and found no maneuvers. thus superflip composed with four spot
requires more than 24 quarter turns. the total search time was about
153 hours. to see that superflip composed with four spot can be
achieved in 26 quarter turns, use
U2 D2 L F2 U' D R2 B U' D' R L F2 R U D' R' L U F' B' (26q*, 21f)
it might be reasonable to ask for all 26q maneuvers. this is probably
out of reach for now. however, i suspect that there will be so many
different 26q maneuvers that it would not be of much use to see a long
list of maneuvers. (i have a bunch already.)
superflip composed with four spot also requires 20f.
proposition 3. any maneuver for superflip composed with four spot
of length <= 20f can be transformed to one that begins
with one of the sequences U2 R , R2 F or R2 U .
the proof is very similar to the reductions for superflip in the face
turn metric.
using this, a complete search for 20f maneuvers is straightforward.
there are two inequivalent 20f maneuvers for superflip composed with
four spot:
F U2 R L D F2 U R2 D F2 D F' B' U2 L F2 R2 B2 U' D (20f*, 28q)
F U2 R L D F2 U R2 D F2 D F' B' U2 L U' D R2 B2 L2 (20f*, 28q)
this also shows that no maneuver is simultaneously minimal in both
metrics.
mike