From cube-lovers-errors@mc.lcs.mit.edu Thu Apr 30 10:09:06 1998
Return-Path:
Received: from sun28.aic.nrl.navy.mil by mc.lcs.mit.edu (8.8.1/mc) with SMTP
id KAA02688; Thu, 30 Apr 1998 10:09:06 -0400 (EDT)
Precedence: bulk
Errors-To: cube-lovers-errors@mc.lcs.mit.edu
Mail-from: From cube-lovers-request@life.ai.mit.edu Thu Apr 30 09:59:19 1998
Date: Thu, 30 Apr 1998 09:57:20 -0400 (Eastern Daylight Time)
From: Jerry Bryan
Subject: Re: Various Cube Thoughts
In-Reply-To: <3546B17A.3419@idirect.com>
To: Mark Longridge
Cc: cube-lovers@ai.mit.edu
Message-Id:
On Wed, 29 Apr 1998, Mark Longridge wrote:
> ------------------------------------------------------------------
>
> No matter which cube you start searching from, e.g. pons asinorum,
> 12 flip, or any random cube, the dispersion of cubes is the same:
>
> 1, 12, 114, 1068, 10011... etc
>
> So much for trying to search backwards from the 12-flip to number
> the positions from (perhaps) antipode to start!
>
> ------------------------------------------------------------------
This has been discussed before on Cube-Lovers. There are several ways
to look at why it is true. I think at the most basic level that it
depends on the inverse property of groups. Let A be any non-empty
subset (not necessarily a subgroup) of G, and let x be any element of G.
Then xA contains the same number of elements as A. Hence, if A is (for
example) the set of all positions which are n moves from Start, then xA
is the set of all positions which are n moves from x, and xA is the same
size as A (remember that the distance from Start to a is the same as the
distance from x to xa for any a in A).
Notice that if A is a subgroup of G rather than just being a subset,
then xA is a coset. The fact that cosets are either equal or disjoint,
combined with the fact that A is the same size as xA, constitute the
basis for the proof that the size of a subgroup must divide evenly the
size of the group.
The inverse property is involved in showing that A and xA are the same
size as follows. Suppose we have A={a,b,c} which contains three
elements. Then we have xA={xa,xb,xc} which also appears to contain
three elements. The only way that xA would not have three elements
would be if some of the apparently distinct elements were really the
same, for example if xa and xc were really two different names for the
same element. But if xa=xc, then we have x'(xa)=x'(xc) so that
(x'x)a=(x'x)c so that ia=ic so that a=c. We know by definition that a
and c are distinct. Hence, xa and xc must be distinct.
Just to give one more illustration of the importance of the inverse
property in showing that A and xA are the same size, here is a false
counterexample. Consider the multiplicative group of the real numbers
or of the rational numbers. Suppose A={ 2/3, 3/4, 7} and x=4. Then,
xA={ 8/3, 3, 28}. So far, so good because both A and xA have three
elements. But suppose x=0. Then xA={0, 0, 0}={0} which has only one
element. Here we have A with three elements and xA with only one
element. So what is wrong. The problem is that any multiplicative
group of what we might call "normal" numbers (e.g., real or rational or
complex) must omit zero because 0 does not have a multiplicative
inverse. That is, there is no solution to the equation 0*x=1. So when I
let x=0, I was cheating by multiplying by a number which is not in the
multiplicative group and which does not have a multiplicative inverse.
The reason I know that this has been discussed before was that I was
involved in the discussion. At one point I incorrectly asserted that
what you are calling "the dispersion of the cubes" did depend on which
position was at the root of the search. Cube-Lovers was quick to
correct me, of course. However egregious was my error, it was still an
honest error. The reason for the honest error is that I accomplish
nearly all my searches by counting patterns (M-conjugacy classes) rather
than by counting positions. And when you count by patterns, "the
dispersion of the cubes" does depend upon which pattern is at the root
of the search. So my mistake was to make a statement about positions
which should have been applied only to patterns.
Your note reminded me of a question I have thought about off and on ever
since that previous discussion. Suppose you are searching by patterns.
Under what circumstances can you start the search with two different
patterns and still have the "dispersion of the cubes" be the same? I
suspect that there is a very simple answer, but I am having trouble
ascertaining what it is. I suspect that the only possibility is if the
two positions differ by superflip, that is if one of them is x then the
other one must be xf=fx, where f is the superflip. But I am simply not
sure if there are any more possibilities. Note that having the two
different patterns be M-conjugate is not an answer to the question
because if two patterns are M-conjugate then they are really just one
pattern.
As a last comment, readers of Cube-Lovers should be familiar with the
sequence 1, 12, 114... for positions in quarter turn searches. A search
for patterns in quarter turns begins 1, 1, 5... The first 1 is Start.
The second 1 (1q from Start) is Q, the set of twelve quarter turns. The
5 (2q from Start) represents the following five patterns: 1) any face
twisted twice in the same direction, 2) any two opposite faces twisted
once each in the same direction (an antislice), 3) any two opposite
faces twisted once each in the opposite direction (a slice), 4) any two
adjacent faces twisted once each in the same direction (e.g., UF or
U'F'), and 5) any two adjacent faces twisted once each in the opposite
direction (e.g., UF' or U'F). Beyond 2q from Start, it becomes too
complicated to calculate the patterns in my head.
= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =
Robert G. Bryan (Jerry Bryan) jbryan@pstcc.cc.tn.us
Pellissippi State (423) 539-7198
10915 Hardin Valley Road (423) 694-6435 (fax)
P.O. Box 22990
Knoxville, TN 37933-0990