On 01/21/95 at 09:05:55 der Mouse said:
>> The superflip is especially amenable to a "two half depth search".
>> Normally, you would have to build one tree with Start at the root,
>> and a second tree with X at the root, where X is the position you
>> were testing. But a search tree with superflip at the root is
>> identical to a search tree with Start at the root except that the
>> superflip tree has each element superflipped as compared to the
>> respective element of the tree with Start at the root.

Isn't this equally true of any other position, except that the
conversion from a Start-rooted tree's position to an X-rooted tree's
position is more complicated than just superflipping? Just think of
your tree, instead of describing positions as "cubie <x> in cubicle
<y>", as describing positions as "cubie that started in cubicle <x> in
cubicle <y>".

I am taking the liberty of CC'ing Cube-Lovers as well. A search tree
giving distances from Start calculates d(I,IY) for all positions IY
in the domain of inquiry. With an X-rooted tree, distances are of
the form d(X,XZ) for all positions XZ in the domain of inquiry.
In general, it is not the case that d(I,IY)=d(X,XY). Hence,
we cannot simply take Z=Y, and elements of the form XY do not produce
the X-rooted tree. Therefore, to perform
two half-depth searches to connect I and X, you really do have to
construct a standard Start-rooted tree as well as an X-rooted tree.
You are looking for a position IY=XZ such that |IY|=|XZ|=|X|/2.

However, in the case of the Superflip E, it is the case that
d(I,IY)=d(E,EY). Hence, in order to construct an
E-rooted tree, it is sufficient to calculate all elements of
the form EY from your existing I-rooted tree of the form IY.

Or are you storing only M-conjugate-class representatives, and I'm
exposing my ignorance of basic group theory? :-)

Yes, I am storing only M-conjugate-class representatives, but that
isn't the problem (see above). However, it does make the processing
a bit less trivial than I have indicated. For every Y in the
Start-rooted tree, I first form EY, then {m'(EY)m}, and finally
Repr{m'(EY)m}. These representatives are sorted and then compared
against all the Y's (which are themselves representative elements,
of course). We are looking for some V and W such that
Repr{m'(IV)m}=Repr{m'(EW)m}, and this will be a "half-way" position.
What I *really* want is some V such that Repr{m'(IV)m}=Repr{m'(EV)m}.
It seems to me that all half way positions should be "symmetric"
in this fashion, but I cannot prove it. The recent discussions
by Mike Reid and Mark Longridge about the 24q superflips are
suggestive in this regard.

 = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =
Robert G. Bryan (Jerry Bryan)                        (304) 293-5192
Associate Director, WVNET                            (304) 293-5540 fax
837 Chestnut Ridge Road                              BRYAN@WVNVM
Morgantown, WV 26505                                 BRYAN@WVNVM.WVNET.EDU