From:

Subject:

(With apologies, retransmitted to correct square brackets trashed by

our mailer.)

On 12/07/94 at 20:45:00 Martin Schoenert said:

Unfortunately C is *not* a normal subgroup of CG, and therefore CG/C is

*not* a group. If we want to apply group theory, we need a better model.

I argue that G is indeed a good model for the 3x3x3 cube.

Well, with great fear and trepidation, let's see if we can't interpret

CG/C in such a way that it is a group. I agree that your statement

above is correct, but I believe we are interpreting C, G, and CG

somewhat differently. I have discussed this subject before, but

armed with some better notation suggested via Dan Hoey, I think I

can do it again both more accurately and more succinctly.

Dan's suggestion is to carefully distinguish which of the various

types of cubies we are talking about. I have done a lot of work

with (for example) corners-only-cubes-without-centers, corners-only-

cubes-with-centers, etc. When we talk about the set C of rotations,

Dan suggests specifying such things as C[C] (Corners-only),

C[E] (Edges-only), C[C,F] (Corners-plus-Face-centers), etc. The

C[C] thing looks funny, using C in two such different ways, but

there are only so many letters. I want to reserve lower case c for

elements of C, so I will live with C[C].

I would suggest extending the notation to G and Q, so that (for example)

the corners-only with Face-centers group we have called GC could instead

be called G[C,F] = <Q[C,F]>, and the 2x2x2 cube could be called

G[C]=<Q[C]> because there are no Face-centers.

The "standard Singmaster model" (my terminology) would be written

as G[C,E,F] = <Q[C,E,F]>. (Well, I think Singmaster would write it as

G[C,E,F] = <Q[C,E,F], H[C,E,F]>, since I think he prefers to

accept H turns as single moves.)

However, I tend to work with G[C,E] = <Q[C,E]> instead. I consider

G[C,E] to be equivalent to G[C,E,F] for most purposes because G fixes

the Face-centers, as does M-conjugation. I have described this

equivalence before as the Face-centers simply providing a frame of

reference that can be provided in other ways. However, when you step

outside the friendly confines of G=<Q>, it does start to matter whether

the Face-centers are there or not. As an example important to this

discussion, if you consider CG=<Q,C>, then it makes a considerable

difference whether you are talking about CG[C,E] or CG[C,E,F].

For example, G[C,E] = <Q[C,E]> can be simulated on a real cube

by removing the color tabs from the Face-centers, by

restricting yourself to Q moves only (no whole cube rotations or

slices), and by declaring the cube solved only when the Up color

is up and the Front color is Front. Notice that with the Face

centers absent, you can make the cube look solved even when it

isn't. It will be rotated instead, but it won't be solved.

This model may seem a little simple-minded. Why are no rotations

allowed, and why don't you count it as solved when it looks solved?

But computers are simple-minded. My programs only consider things

equal when they are literally equal, and equivalence is something

I have to program in. As an example I have used before,

consider G[C]=<Q[C]>, modeled in the real world by a 2x2x2 pocket cube

or by removing both the edge and Face-center color tabs from a 3x3x3

cube. Take a solved cube in G[C] and perform RL'. The cube will still

look solved, but it will be rotated. The memory cells in my program

will not be the same for I as for RL', but I want to treat them as

equivalent, as would nearly everybody with a real world 2x2x2 cube

in their hands.

This is where I have claimed before that a model that treats RL' the same

as I is G[C]/C[C]. The idea is that G[C]/C[C] is a group with the

identity being C[C] itself (i.e., rotating the cube is "doing

nothing".) The proof is fairly simple. From each element (coset) of

G[C]/C[C], pick the unique permutation that fixes a particular

corner, say UFR, and form a new set G[C]* containing the one element

chosen from each coset. The elements of G[C]/C[C]

are sets (namely cosets), but the elements of G[C]* are permutations

which are also in G[C]. In particular, G[C]* = <D[C],B[C],L[C]>.

Hence, G[C]* is a group.

Note that the generators of G[C]* are

the twists of those faces which are diagonally opposed to the

corner fixed by the selection function from G[C]/C[C] to G[C]*.

Hence, the generators fix the same corner as the selection function,

showing that <D[C],B[C],L[C]> is really the same set as G[C]*,

namely the set of all cubes in G[C] for which the UFR corner is

fixed. Finally, there is an obvious isomorphism between G[C]/C[C]

and <D[C],B[C],L[C]>. Namely, to multiply two cosets, map each

to <D[C],B[C],L[C]> via the selection function, perform the multiplication

there using standard cube multiplication, and map the

product back to a coset. Hence, G[C]/C[C] is a group.

A similar argument applies to G[E]/C[E] except that we have to fix

an edge cubie instead of a corner cubie. A similar argument applies

to G[C,E]/C[C,E] except we have to fix an edge cubie and restrict C to

even permutations. Dan calls the set of even rotations E, so let's

call it G[C,E]/E[C,E]. (Still wish we had letters whose use

did not conflict so blatantly.)

But when we started, we were talking about CG/C, not about G/C.

However, notice that when our model does not include Face-centers,

we have <Q[C]> = <Q[C],C[C]>, <Q[E]> = <Q[E],C[E]>,

and <Q[C,E]> = <Q[C,E],E[C,E]>. (I mean that the groups are equal, not

that the Cayley graphs are the same.) Hence, speaking generically of

the first two cases, we have C is in G, CG=G, and both CG/C and G/C are

groups. In the last case, we have to say E is in G, EG=G, and EG/E is

a group. But we can go one step further. Since there are no Face-centers,

we can admit Slice moves or C as generators (it doesn't matter which),

and we no longer have to restrict ourselves to even rotations.

We can say G+[C,E]=<Q[C,E],C[C,E]> and we will have C is in G+,

CG+=G+, and CG+/C is a group which is the same size as EG/E. (G+ is twice

as big as G, of course.)

I guess this must mean that C[C], C[E], and C[C,E] are all normal

subgroups of their respective CG's, but that C[C,F], C[E,F], and

C[C,E,F] are not. That should not be surprising. Having the

Face-centers there only as a frame of reference and never moving

is not the same as having them there and really moving (as when you

rotate the entire cube).

After joining Cube-Lovers, I discovered that others

had solved God's algorithm for the 2x2x2 long before me. I was expecting

my solution to be 24*48 times smaller than theirs because I was using

cosets of C and M-conjugates. But my solution was only

48 times smaller than theirs. By taking both cosets and M-conjugates

I really had reduced <Q[C]> by 24*48 times. However, everybody else

who worked on the problem had modeled it as something like

<D[C],B[C],L[C]>, fixing a corner. (Any other corner would do as well.

There are eight conjugate groups, any of which would do as well as any

other.) <D[C],B[C],L[C]> is 24 times smaller than <Q[C]> in the first

place, and as I said earlier, <Q[C]> is equivalent to <Q[C,F]> for

most purposes anyway because of the fixed Face-centers. Hence,

everybody else had a 24 times head start on me. (At the time,

Dan suggested that I was increasing the size of the problem by 24 and

then reducing it by 24*48 for a net reduction of 48. But that would

only be true if the model were <Q[C,F]>. Since the model was <Q[C]>,

there really was a reduction of 24*48. But <Q[C]> does not really

model the 2x2x2 cube, and is 24 times larger than it needs to be in

the first place if you are trying to model the 2x2x2.)

Modeling cubes without centers such as the 2x2x2 is trickier than it

looks because of the requirement that rotations be treated as

equivalent. I did it by using cosets of rotations; everybody else

did it by fixing a corner. But before I realized all this, I went on

a Quixotic chase for a model which would simultaneously be a true

model for a 2x2x2 cube and would retain the cubic symmetry of the

problem (whatever that means). There are articles in the archives

concerning this subject, with the conclusion that no such model is

possible because any true model would be isomorphic to <D[C],B[C],L[C]>,

which does not have "cubic symmetry".

I guess the "cubic symmetry of the problem" means that you should use

M-conjugate classes. Recall that when I solved <U,R> I used what

Dan calls W-conjugate classes because W is the symmetry group

for <U,R>, and W-conjugate classes reduced the size of the problem

by four times. This leads me to a question. The way I modeled

the 2x2x2, I used M-conjugate classes of cosets and reduced the size of

the problem by 48 times. If I were going to model <D[C],B[C],L[C]>,

I would be very inclined not to use M-conjugate classes, but rather to

use a subgroup of M which was the symmetry group of <D[C],B[C],L[C]>.

The subgroup would have less than 48 elements, and I would get less

than a 48 times reduction in the size of the problem. But a fixed

corner model such as <D[C],B[C],L[C]> is isomorphic to a coset model

such as <Q[C]>/C[C], and M-conjugates are appropriate to the coset

model. Therefore, my analysis of the situation is obviously very

flawed. Can anybody see what is wrong?

= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = 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