From:

Subject:

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.

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