From:

~~~ Subject:

I said I wasn't going to write again about Shamir's method until

I had a working program. Well, I don't have a working program

yet but this is only indirectly about Shamir. Rather, it is

about how we might represent the cube compactly in a way that is

easy to work with. We would like a compact representation that

is usable by Shamir's method. But more importantly, we would

like a compact representation that is easily usable for forming

compositions in general. The compact representation I will

describe is useful in a number of contexts, not just Shamir's

method.

My standard model is an S24 x S24 model, modeling the corner and

edge facelets separately and not modeling the face centers. At

one byte per facelet, this representation requires 48 bytes per

position without packing.

David Moews has described a wreath product representation (e.g.,

23 Feb 1996) which requires 40 bytes without packing. There are

8 bytes to describe the position of each corner cubie, and 8 more

bytes to describe the twist of each corner cubie. Similarly,

there are 12 bytes to describe the position of each edge cubie,

and 12 more bytes to describe the flip of each edge cubie. This

representation has the virtue of being 8 bytes smaller than the

S24 X S24 representation, while still being easy to work with and

manipulate.

For my very large searches, I always used a supplement

representation for the external files. That is, I only stored

one facelet from each of the 8 corner cubies and one facelet from

each of the 12 corner cubies for a total of 20 bytes unpacked.

(I also packed the 20 bytes into 13 bytes to use less tape, but

that is not important for this particular story.)

However, I found the supplement representation awkward to

manipulate, so I always expanded the supplement representation to

a full S24 x S24 representation inside the program. None of my

programs were more than a few K (not a few Meg, just a few K

because the storage was external), so the extra few bytes were a

non-issue. But now that I want to implement Shamir, my programs

will be very large. Therefore, I wanted to figure out how to

manipulate the supplement representation directly. The

representation itself is not new, but the technique to manipulate

it is. Here is what I have come up with. I think it is

applicable to Shamir programs and non-Shamir programs alike.

I will use the corners as an example. Similar comments would

apply to the edges. My standard supplement for the corners is

the Front facelets and the Back facelets. The way I number the

facelets, these are facelets 1 through 4 for the Front and 21

through 24 for the Back. In the vector notation we have been

talking about in this thread, the supplement of the identity is

[1,2,3,4,21,22,23,24]. 1 is mapped to 1, 2 is mapped to 2, 3 is

mapped to 3, and 4 is mapped to 4. However, 5 is not mapped to

21. Rather, 21 is mapped to 21, 22 is mapped to 22, etc.. You

have to think of the last 4 indexes as being offset by 16 because

16 of the facelets are left out. From this vector, we can

reconstruct the fact that 5 is mapped to 5, 6 is mapped to 6,

etc. based on which facelets are part of which cubies.

Composition of these supplement vectors can be hard or easy

depending on what we are trying to do. Suppose X is a

permutation on the corners represented by an 8 byte supplement

vector and q is a quarter-turn on the corners represented by a 24

byte permutation vector. Then, the calculation of Xq more or

less "just works", and the composition is an 8 byte supplement

vector. For some kinds of things you have to worry a little bit

about the offset of the last 4 indexes, but the computer coding

is basically very straightforward. The code even runs faster

than the code for composing two 24 byte permutation vectors.

But suppose for some reason we need to form qX instead of Xq.

The q vector will map into values that simply aren't there in the

X vector. The programming symptom will be an out-of-bounds

subscript.

It doesn't help to use two supplement vectors. If X and Y are

both supplement vectors, then neither the product XY nor the

product YX can be formed. The same problem occurs anytime a

supplement vector is pre-multiplied, no matter whether it is

pre-multiplied by another supplement vector or whether it is

pre-multiplied by a full-length permutation vector.

With some searches you can probably get by with only post-multiplying

supplement vectors by full-length permutation

vectors. I think you could form a breadth first search tree that

way by always post-multiplying by full-length vectors q in Q.

But I always want to form M-conjugates m'Xm, so I have to be able

to pre-multiply. Here is how to do it with supplement vectors.

As I said, my old programs expand an 8 byte supplement vector for

the corners into a 24 byte permutation vectors on the corners

when a position is read from a file into memory. Two special 24

byte vectors are used in the process. One of the 24 byte vectors

defines which facelet is to the right of each other facelet on

the corner cubies, and the other of the 24 byte vectors defines

which facelet is to the left of each other facelet on the corner

cubies. So the supplement is expanded by mapping each of the

8 bytes in the supplement into itself, and in addition by mapping

each of the 8 bytes into its respective right and left.

These "right of" and "left of" vectors can be identified with the

permutations which twist each corner cubie right and left,

respectively. These permutations are not in the Start orbit.

But we can nonetheless observe that both of them commute with

every other permutation.

I am focusing this example on the corners, but my old programs

also have to expand a 12 byte supplement vector for the edges

into a 24 byte permutation vector. The vector which accomplishes

this mapping defines for each edge facelet the other facelet

which is on the same edge cubie. This permutation can be

identified with Superflip, and Superflip also commutes with every

other permutation.

The center of G consists of the identity plus Superflip. These

permutations fix the corners and either fix or flip the edges.

But the center of the constructable group consists of fixing or

flipping the edges composed with fixing or twisting right or

twisting left the corners. So there are six positions in the

center of the constructable group, and it is precisely these six

permutations which are required to make composition of supplement

vectors work.

I normally write an M-conjugate in E-mail just as m'Xm. But for

this example, let me write it as (i)m'Xm, where i is the argument

of the permutation and where i runs from 1 to 24 for the corners.

The trick to make composition of supplements work is going to be

to write the permutation as something like (i)m'k'Xkm, where k is

not really a permutation. Rather, it is some magic to be defined

below.

The trick is not just for M-conjugation. It is for pre-multiplication

in general. The Xm part of m'Xm is not a problem;

it is the m'X part which is a problem. Similarly, to multiply

supplement X (or full-length vector X) by supplement Y, the k

trick would be Xk'Yk, which we could group as X(k'Yk) for

emphasis. As with M-conjugation, I will make the argument

explicit and write (i)Xk'Yk.

But just what is this k? For the corners, we define k[1] as the

identity, k[2] as twist all corners right, and k[3] as twist all

corners left. We also define a 24 byte vector j which defines

which corner facelets are in the supplement (a value of 1), right

of the supplement (a value of 2), or left of the supplement (a

value of 3). j is a function, but is not a permutation. With my

particular numbering scheme and choice of supplement, j looks

something like [1,1,1,1,2,3,2,3,......3,2,3,2,1,1,1,1]. That is,

only the first four and last four facelets are in the supplement.

The j vector is used to index k. For the edges we would define

k[1] as the identity and k[2] as Superflip.

An M-conjugate would then be calculated as

(i)m' k[j[t]]' X k[j[t]] m

for i in 1..24 and where t=(i)m'. Effectively, k'

maps (i)m' into the supplement so that X operates only on the

supplement, and k undoes (untwists and/or unflips) whatever k'

does. However, the k-conjugation must be applied on a facelet by

facelet basis. k[1] might be used for one facelet, k[2] for

another facelet, and k[3] for still another. Nonetheless, since

each of the k's is in the center of the constructable group, we

have X=k'Xk for all X, irrespective of which k is used for a

particular facelet.

It is not strictly necessary, but this procedure would be

slightly simpler if the facelets were renumbered. That is,

renumber the supplement 1 to 8 for the corners and 1 to 12 for

the edges.

It is easy to see how to construct the tree required by Shamir's

method using this supplement representation. The supplement

representation does not reduce the number of potential branches

out of each node. But it does reduce the number of levels of nodes.

I plan to have the branching for the first 8 levels of my tree be

controlled by the supplement for the corners, and the branching

for the next 12 levels of my tree be controlled by the supplement

for the edges.

= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = Robert G. Bryan (Jerry Bryan) jbryan@pstcc.cc.tn.us Pellissippi State (423) 539-7127 10915 Hardin Valley Road (423) 694-6435 (fax) P.O. Box 22990 Knoxville, TN 37933-0990