From cube-lovers-errors@mc.lcs.mit.edu Thu Aug 6 11:20:35 1998
Return-Path:
Received: from sun28.aic.nrl.navy.mil by mc.lcs.mit.edu (8.8.8/mc) with SMTP
id LAA21031; Thu, 6 Aug 1998 11:20:34 -0400 (EDT)
Precedence: bulk
Errors-To: cube-lovers-errors@mc.lcs.mit.edu
Mail-from: From cube-lovers-request@life.ai.mit.edu Wed Aug 5 13:41:35 1998
Date: Wed, 05 Aug 1998 13:41:10 -0400 (Eastern Daylight Time)
From: Jerry Bryan
Subject: Re: superflip composed with four spot
In-Reply-To: <199808021247.IAA08734@cauchy.math.brown.edu>
To: michael reid
Cc: cube-lovers@ai.mit.edu
Message-Id:
On Sun, 02 Aug 1998 08:47:44 -0400 michael reid
wrote:
> 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.
Nobody has said so yet on the list, but I think this is
exciting news for Cube-Lovers, both the fact that a new
lower bound has been discovered for the diameter of the
cube group, and the fact that a new (and very long) local
maximum has been found by means other than computer search.
It seems to me that Mike's proof might provide an outline
for a method for looking for other local maxima. I have
not at this point been able to use his method to find other
local maxima, but here is how it might work.
> 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.
More generally, for any position x, calculate Symm(x)=K,
where K is as usual the subgroup of all k in M such that
x=k'xk, and where M is the group of 48 symmetries of the
cube. Conjugation by K and grouping the elements of Q into
conjugate equivalence classes induces a partition on Q, the
set of twelve quarter turns. In Mike's case, the partition
is {Q1,Q2} where Q1={U, U', D, D'} and Q2={R, R', F, F', L,
L', B, B'}.
The process I am going to describe is much simpler if we
confine ourselves to 2-way partitions of Q, such as Mike's
case. I think the process I am descibing can be
generalized to more than 2-way partitions of Q, but some of
the steps get more complicated. So for now we confine
ourselves to subgroups K of M which induce at most a 2-way
partition of Q.
Roughly speaking, this means that we need to find positions
that are fairly symmetric. I have been meaning for a long
time to calculate a table of partitions of Q for each of the
possible 98 subgroups of M. Perhaps Mike's new result will
provide sufficient motivation to perform the calculations.
The next hurdle is that we must find positions x such that
x is not in or , so that a maneuver for x must
contain quarter turns from both Q1 and Q2. Mike's position
certainly satisfies this criterion. Notice that if we get
this far, we can say that a maneuver for x must contain at
least one element from Q1 and at least one element from Q2,
but the elements from Q1 and Q2, respectively, need not
necessarily appear at the end of the maneuver. Also, by
the definition of Q1 and Q2, *any* maneuver from Q1 and Q2
can appear in a maneuver for x by K-conjugation.
So far, so good. I would go about this type of a search by
determining which subgroups K of M induce a 2-way partition
of Q, and then by thinking about what a K-symmetric
position must look like. But here's the rub -- the part I
cannot figure out *in general". In order to get the
elements of Q1 and Q2 to the end of the maneuver for x, we
need positions which may be cyclically shifted, either in
the normal sense or in Mike's new sense where the part of
the maneuver that is shifted is conjugated by K.
There is a good bit of discussion in the archives about
cyclical shiftiness. I'm going to go back and re-read that
discussion to see if it helps with this problem. But any
position x whose symmetry group induces a 2-way partition
{Q1,Q2} on Q, where x is not in or , and where x
is cyclically shiftable (possibly with K-conjugation of
the shifted part) is a local maximum in the quarter turn
metric.
----------------------
Jerry Bryan
jbryan@pstcc.cc.tn.us