From BRYAN@wvnvm.wvnet.edu Fri Oct 13 15:46:51 1995
Return-Path:
Received: from WVNVM.WVNET.EDU by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA08454; Fri, 13 Oct 95 15:46:51 EDT
Received: from WVNVM.WVNET.EDU by WVNVM.WVNET.EDU (IBM VM SMTP V2R3)
with BSMTP id 1264; Fri, 13 Oct 95 11:47:44 EDT
Received: from WVNVM.WVNET.EDU (NJE origin BRYAN@WVNVM) by WVNVM.WVNET.EDU
(LMail V1.2a/1.8a) with BSMTP id 2160; Fri, 13 Oct 1995 11:47:44 -0400
Message-Id:
Date: Fri, 13 Oct 1995 11:47:43 -0400 (EDT)
From: "Jerry Bryan"
To: "Dan Hoey" ,
Subject: Re: Using 5 Generators
In-Reply-To: Message of 10/11/95 at 22:56:15 from hoey@aic.nrl.navy.mil
On 10/11/95 at 22:56:15 hoey@aic.nrl.navy.mil said:
>> But I can report that my search found 16 unique (*not* unique up to
>> conjugacy) half-way positions. I use the term "half-way" advisedly.
>> The "half-way" positions are 9q from Start and 8q from B or vice
>> versa. I guess you could say that the vice versa gives you a total
>> of 32=16+16 half-way positions, but the whole concept of "half-way"
>> is pretty slippery in this case anyway.
>If I understand this, there are 16 positions at 9q from Start and 8q
>from B, and there are 16 other positions at 8q from Start 9q from B.
>Is each of the first bunch adjacent to exactly one of the other? And
>vice versa? It would be good to get them reduced by Q2-conjugacy, as
>well.
I don't think I can answer your questions without further analysis,
and I don't have much time to devote to the problem. But let me
clarify as follows. First, the search looked as follows:
Distance from Distance from Total Number of
Start B Distance Matching
Positions
0 1 1 0
1 2 3 0
2 3 5 0
3 4 7 0
4 5 9 0
5 6 11 0
6 7 13 0
7 8 15 0
8 9 17 16
There is a certain arbitrariness in at least two respects. For one
example, to test for a total distance of 11, you could just as well use
distances from Start and B respectively of 4 and 7 instead of 5 and 6.
For another example, the Start-rooted tree and the B-rooted tree have
identical structures, so the first two columns could be reversed.
Indeed, you could get the B-rooted tree simply by pre-multiplying the
Start-rooted tree by B. (This reminds me of one of my most
foolish errors on Cube-Lovers. For search trees where the nodes are
conjugacy classes (or representatives of conjugacy classes), the
tree looks different depending on which class or representative is at
the root. But when the nodes are all the positions, then the tree is
essentially the same in all cases, just pre-multiplied by the root.
I once claimed the tree structure depended on the root for trees
containing all positions, confusing that situation with the situation
for trees of conjugacy classes. Arrg!)
Hence, I am not especially comfortable talking about "half-way" positions.
But continuing anyway, denote the 16 positions which are 8 moves from
Start and 9 moves from B as X_i for i in 1..16. Then, the 16 positions
which are 8 moves from B and 9 moves from Start are B(X_i) for i
in 1..16. A solution to the problem would then look something like
(X_j)Y(X_k)', where Y is in Q-{B,B'}. But I don't think we can say
a priori that there is no Z in Q-{B,B'} and no X_m such that
(X_j)Z(X_m)' is also a solution (Z not equal Y and X_m not equal X_k).
I think to analyze the problem properly you would have to take the
positions X_i for i in 1..16 and the positions B(X_j) for j in 1..16
and match up each X_i with each B(X_j) to see which ones differ
by a quarter turn. Each X_i is going to match up with at least one
B(X_j) and vice versa, but there might be more than 16 matches
overall.
Reduction by Q2-conjugacy is important, but I don't think it would
tell you how many solutions there are that you would really want to
consider to be unique. Recall the solution of Pons Asinorum by
half-depth searches. There are 5 positions unique up to M-conjugacy
which are 6q from Start and 6q from Pons. But most people would
consider that there are only two minimal solutions to Pons that are
really different. The trouble is that 4 of the 5 half-way positions
for the Pons are in the middle of a sub-process which commutes.
= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =
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