From mschoene@math.rwth-aachen.de  Mon Feb 13 05:57:30 1995
Return-Path: <mschoene@math.rwth-aachen.de>
Received: from samson.math.rwth-aachen.de by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA27480; Mon, 13 Feb 95 05:57:30 EST
Received: from hobbes.math.rwth-aachen.de by samson.math.rwth-aachen.de with smtp
	(Smail3.1.28.1 #11) id m0rdyQX-000MPAC; Mon, 13 Feb 95 11:54 MET
Received: by hobbes.math.rwth-aachen.de (Smail3.1.28.1 #19)
	id m0rdyQW-00025cC; Mon, 13 Feb 95 11:54 WET
Message-Id: <m0rdyQW-00025cC@hobbes.math.rwth-aachen.de>
Date: Mon, 13 Feb 95 11:54 WET
From: "Martin Schoenert" <Martin.Schoenert@math.rwth-aachen.de>
To: Cube-Lovers@ai.mit.edu
In-Reply-To: "Jerry Bryan"'s message of Sat, 21 Jan 1995 12:44:42 EST <9501212203.AA05451@life.ai.mit.edu>
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.

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