From:

~~~ Subject:

Jerry Bryan <BRYAN%WVNVM.BITNET@mitvma.mit.edu> asked a bunch of

questions a couple of weeks ago, and I'll try to get to them all.

The first bunch has to do with some fairly basic stuff, that I thought

had been pretty well understood since the beginning of the mailing

list, but maybe we need a refresher, or an explicit statement.

In the message of Tue, 14 Dec 1993 20:50:51 EST, Jerry describes his

representation of cube positions and transformations.

In my computer model, the corner facelets are simply numbered from

1 to 24, and any configuration of the corners is an order-24 row

vector. The rotation and reflection operators are also order-24 row

vectors, again with each cell simply containing a number from 1 to

24.

That is the most usual way of doing it, but it's important to specify

what you represent by those vectors. When I do it, I number the

corner facelet locations from 1 to 24, and these locations retain

their numbers through manipulations of the cube. I use a vector A to

specify a position in which the facelet whose home location is i has

been moved to location A(i), for each i. I use a vector P to specify

the transformation that moves the facelet in location i to location

A(i), for each i. I'll assume you're doing the same, though you

could, for instance, be representing the inverse of the operators, or

the locations from which the facelets originate. Note that a position

is represented by the same vector that represents the transformation

that takes SOLVED to that position.

Well, if P is a rotation operator, you could perform a rotation

two ways. I guess one is pre-multiplication and one is

post-multiplication.1) For i = 1 to 24 B(i) = A(P(i))

I would write this as B = P A, and say that A is premultiplied by P,

or equivalently that P is postmultiplied by A. In a general group, we

could have B = P A where the multiplication is not considered to be

the composition of permutations. But it turns out we can restrict our

attention to permutation groups without loss of generality. For

instance, when we are dealing with the supergroup, we can consider the

orientation of a face center to be a permutation of the corners of the

face center.

2) For i = 1 to 24 B(i) = P(A(i))

Here B = A P, A is postmultiplied by P, and P is premultiplied by A.

(Note that the operator or position name appears in the reverse order

from the prefix format. Algebraists sometimes avoid this by writing

(i)B = ((i)A)P. I kid you not.)

(As an aside, this illustrates the question I raised in my previous

post about "which is the operator and which is the thing being

operated on?" Is P operating on A, or is A operating on P?)

Well, the answer is ``both''. I agree it's easy to get confused,

which is why proofs are a good idea.

Finally, if Q is a reflection (actually, if Q1 is the identity and

Q2 is the reflection), then we haveFor j = 1 to 24 for k = 1 to 24 for m = 1 to 2 for i = 1 to 24 Bj,k,m(i) = Qm(Pj(A(Qm(Pk(i)))))I believe this loop calculates Dan Hoey's M.

On the the theory that proofs are a good idea, let's see what this

loop calculates. I'm going to put brackets around the subscripts.

Then I'll substitute "R" for "Q", because I use Q for the set of

quarter-turns of faces. Furthermore, I'll use "C" instead of "P",

because the P[j] are just the elements of C, the group of cube

rotations. So you are computing

B[j,k,m] = C[k] R[m] A C[j] R[m] (1)

for j in {1,...,24}, k in {1,...,24}, and m in {1,2}. Now every

member of M (the group of cube rotations and reflections) has a unique

representation as M[n] = C[k] R[m]. Let us define Cind() and Rind()

as the functions for which M[n]=C[Cind(M[n])] R[Rind(M[n])]. So we

can write (1) as

B[j,k,m] = M[n] A M'[n] (M[n] C[j] R[Rind(M[n])])

Note that (M[n] C[j] R[Rind(M(n))] must be an element of C. So B is a set of elements of the form M[n] A M'[n] C[o]. To see that we have all such elements, first observe that (M[n]' C[o] R[Rind(M[n])]') is an element of C, say C[j]. So equation (1) includes:

C[Cind(M[n])] R[Rind(M[n])] A C[j] R[Rind(M[n])] = M[n] A (M[n]' C[o] R[Rind(M[n])]') R[Rind(M[n])] = M[n] A M'[n] C[o].

Thus the set of all B[j,k,m] is the set of all M[n] A M'[n] C[o]. Or

in English, that's the set of all M-conjugates of A, operated on by

all whole-cube rotations.

In my data base, I store the minimum of Bj,k,m over j = 1 to 24,

k = 1 to 24, and m = 1 to 2. I tend to call the minimum of Bj,k,m a

canonical form. I am not sure if that is the best terminology. The

minimal element is not any simpler than any other. It is just that

I need a function to choose an element from a set, and picking the

minimal element seems very natural. Any other element would do as

well, provided I could always be sure of picking the same element.

It's pretty common terminology. You might be slightly better off

calling it a ``representative element,'' as that connotes that the

element is ordinary except in that it represents the equivalence class

(like representatives in the U.S. Congress).

Also, my criterion for equivalence is slightly

different (but isomorphic, I think) than the one described by

Dan Hoey. Suppose A and B are two cubes.

Rather than mapping A to B or B to A in M, I map both A and B

to their respective canonical forms. A and B are equivalent if

their respective canonical forms are equal.

This is straightforward once we show that M-conjugacy is an

equivalence relation, and B[j,k,m] is an equivalence class.

If A ~ Representative[A] = Representative[B] ~ B, then by transitivity

A ~ B. Conversely, if A ~ B, then Class[A] = Class[B], and therefore

Representative[A] = Representative[B]. This shows that the criteria

are equivalent.

Now, as to the centers. I still sometimes have a certain doubt

about the centers. They are fixed, so how can you reduce the

problem (i.e., increase the size of the equivalence classes)

by both rotating the cube and rotating the colors (by both pre-

and post-multiplication)?

What you have done is to increase the size of the whole cube problem

by a factor of 24, by dealing with all rotations of the cube, and the

equivalence classes expand by the same factor, from 48 to 1152. This

has allowed you to calculate something like M-conjugacy classes for

cube problems that lack face centers. But the size of the equivalence

classes doesn't shrink the problem for cubes that have face centers.

You could have just calculated M-conjugates and got the same answer.

I am not sure if this answers Dan's question about my model

with centers added.

It's clear now. I hadn't realized you were rotating the cube in space

when the face centers were present. I expected that to be a wasted

effort. But I am impressed by the way it allows you to shrink the

database by storing positions together that differ only by whole-cube

moves of the face centers. I think it should be possible to shrink

the database without the effort, though.

In your message of Thu, 16 Dec 1993 15:36:58 EST, on the ``Duality of Operators and Operatees'':

I have mentioned several times my discomfort about "an operator" as

opposed to "the thing being operated on" when it comes to groups. I

am never quite sure just which of the two it is that people are

talking about, even (or especially) when I am listening to myself

talk.

It is hard to keep it straight. Sometimes we all get it wrong. The

best way to avoid errors, as far as possible, is to avoid such

language and talk about group multiplication. But then we have to

explain what is going on with the cube, so we get caught into talking

about operators again. It's a discomfort that must be endured.

The code to translate between the ASCII string X and

the EBCDIC string Y is something like

for i = 1 to n Y(i) = T(X(i))

where T is the translate table.

Yes, or Y = X T as above.

I am going to continue reading, but perhaps I could pose a question to

Dan Hoey anyway: is reversing the role of X and T in the TRANSLATE

function above essentially the same thing as switching between

pre-multiplication and post-multiplication?

Yes.

Dan Hoey

Hoey@AIC.NRL.Navy.Mil