[next] [prev] [up] Date: Mon, 13 Feb 95 11:54:00 WET
[next] [prev] [up] From: Martin Schoenert <Martin.Schoenert@math.rwth-aachen.de >
[next] [prev] [up] Subject: Re: Re: superflip in quarter turn metric
Jerry Bryan wrote in his e-mail message of 1995/01/21

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.

First we have to make certain that we agree how to multiply permutations.
If I write <g> <h>, then I mean *first* do <g> and *then* do <h>.
So I compute the image of a point <p> under the permutation (<g> <h>) by
first computing the image of <p> under <g> and then computing the image
of that point under <h>. For this order of multiplication it is usual
to write <p>^<g> for the image of a point <p> under a permutation <g>
(instead of writing <g>(<p>), which would be better for the other order).
For this order of multiplication we must define conjugation of <g> by <h>
as <g>^<h> := <h>^-1 <g> <h> (instead of <g>^<h> := <h> <g> <h>^-1).

In this notation, it is certainly true that d(<id>,<h>) = d(<g>,<g><h>).
This is because each process that transforms <id> to the state <h>,
will also transform <g> to <g><h>, and likewise each process that
transforms <g> to <g><h> will also transform <id> to <h>.

In a certain sense we don't need this though. What you are looking
for is a process <p> that effects the state <g>, i.e., <id> <p> = <g>.
If such a process of length 22 exists, then there exist two processes
<p_1> and <p_2> of length 11, such that <id> <p_1> <p_2> = <g>.
We can rewrite this as <id> <p_1> = <g> <p_2>^-1. Let T be the set of
elements reachable from <id> by a process of length 11. Note T^-1 = T.
So we see that if there is a process of length 22 effecting <g>,
then the intersection (<id> T) <inter> (<g> T) must be nonempty.
As mentioned above, you can interpret the set (<g> T) as the set
of elements at distance 11 from <g>, but you don't have to.

Now for the superflip <z> you even have d(<id>,<h>) = d(<z>,<h><z>),
since <h><z> = <z><h> because the central <z> commutes with every <h>.
Put differently this means that (<z> T) = (T <z>), i.e., instead
of multiplying each element of T from the left by <z>, you can instead
multiply each element from the right.

Have a nice day.


-- .- .-. - .. -.  .-.. --- ...- . ...  .- -. -. .. -.- .-
Martin Sch"onert,   Martin.Schoenert@Math.RWTH-Aachen.DE,   +49 241 804551
Lehrstuhl D f"ur Mathematik, Templergraben 64, RWTH, 52056 Aachen, Germany

[next] [prev] [up] [top] [help]