From:

Subject:

Jerry Bryan wrote in his e-mail message of 1994/12/08

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.

I think that we agree much more than we actually realize, and that it is

mostly a matter of language. So your clarification was most welcome, and

I hope mine is too.

Jerry continued

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.

Let's see whether I understand this correct.

Let CG again be the complete cube group generated by the face turns and

the rotations, let G be its subgroup of index 24 generated by the face

turns, and C the subgroup of size 24 generated by the rotations.

CG can be represented as a permutation group on 54 points. On this set

it makes three orbits, called C(orners), E(dges), and F(ace-centers), of

sizes 24, 24, and 6.

[A sidenote. Old e-mails in Cube-Lovers often talk about the 12

``orbits'' of the cube group G in the group that you get when you

are allowed to take the cube apart. This group has structure

(S(8) <wreath-product> 3) <direct-product> (S(12) <wreath-product> 2).

Strictly speaking, these are not ``orbits'' but ``cosets'' instead.]

We can now look at the operation of CG (and C and G) on the 8 sets [],

[C], [E], [C,E], [F], [C,F], [E,F], and [C,E,F] (where [X,Y] here means

the (disjoint) union of the orbits X and Y). This gives us 8 groups to

look at, together with their respective subgroups induced by C and G.

Clearly CG[] is trivial, and CG[C,E,F] = CG. Such a group, e.g., CG[C],

is a model for what we get when we remove the color tabs from the other

orbits, e.g., for CG[C] we would remove the color tabs from the edges and

the faces.

A little bit of group theory. Each of those 8 groups CG[<orbits>] is

a homorphic image of CG. That means there is a homomorphism from

CG to CG[<orbits>]. This homomorphism is actually very easy to describe:

you get the image of an element by simply forgetting what that

element does on the other orbits. The kernel of this homomorphism

is the subgroup of elements of CG that do nothing on <orbits> and

only permute the points in the other orbits. What this means is that

each CG[<orbits>] is a factor group of CG.

Jerry continued

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].

Correct. Since G fixes the faces, G[C,E,F] and G[C,E] are isomorphic.

But CG[C,E,F] and CG[C,E] are not isomorphic, and neither are

C[C,E,F] and C[C,E].

Jerry continued

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.

Maybe a little convention would help. We could say that a cube is

*completely solved* if all the up-color tabs are on the up-face,

all the right-color tabs are on the right-face, etc. And a cube is

*solved up to rotations* if all the tabs on each face have the same

color, i.e., if it can be completely solved with a rotation of the entire

cube. Talking about the groups, only the identity is completely solved,

but all elements in C[<orbits>] are solved up to rotations.

In this language CG[C] is a model for the complete solution of the

2x2x2 cube, and a supplement for C[C] in CG[C] is a model for the

solution up to rotations of the 2x2x2 cube. And of course, most

of the time we are interested in solutions up to rotations.

Jerry continued

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.

I agree mostly but not completely.

First I claim that we are interested not in the cosets of C[C] in G[C],

but rather in the cosets of C[C] in CG[C]. Now since G[C] = CG[C] this

doesn't seem to make any difference. But for a different set of orbits,

G[<orbits>] may be different from CG[<orbits>], and C[<orbit>] will then

not be a subgroup of G[<orbits>]. So in those cases it doesn't make

sense to speak of the cosets of C[<orbits>] in G[<orbits>].

Second your usage of G/H. Many group theory textbooks restrict

this notation to the case when H is a normal subgroup of G.

Others use G/H in general for the set of cosets of H in G.

But whenever they write ``the group G/H'' or ``G/H is a group'',

they always mean that H is normal in G, and that G/H is the factor group.

I would be happy if you wrote about ``the set G[C]/C[C] with the

multiplication defined by ... is a group'' instead of ``G[C]/C[C] is a

group''. The reason why I think it is important to be carefull is that

many properties carry over from G to a proper factor group G/H, but do

not carry over from G to ``the set G/C with the multiplication

defined by ...''. I shall return to this point below.

I agree that G[C]* is indeed a group. You do exactely the same thing

that I did in my message. You pick a set of represtatives that forms a

subgroup, which I called a supplement for C[C]. Then you define the

multiplication using those representatives. I think that it is easier to

work with the supplement instead of the structure G[C]/C[C] with

the induced multiplication, but that is clearly a matter of taste.

Jerry continued

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

an edge cubie instead of a corner cubie.

Almost. But there is a tricky problem here. Again G[E] = CG[E],

so it doesn't matter whether we talk about G[E]/C[E] (as you prefer)

or about CG[E]/C[E] (as I prefer). Again we can find a supplement

for C[E] in CG[E], namely the subgroup of all elements of CG[E]

that leave a particular edge cubie fixed. Assume that we fix the

upper-right edge cubie, then this supplement is <L[E],D[E],F[E],B[E]>.

But this does *not* respect costs. That is take an element e of CG[E].

Let r be its representative in <L[E],D[E],F[E],B[E]>, i.e., c e = r,

where c is a rotation of the entire cube. The the costs of the two

elements, viewed as elements of CG[E] is clearly the same (remember,

rotations cost nothing). But the cost of r, viewed as an element of

<L[E],D[E],F[E],B[E]> *with this generating system*, may be higher.

For example take R[E] * r[E]' (where r is the rotation of the entire

cube). In CG[E] this element has cost 1. And this element lies in

<L[E],D[E],F[E],B[E]>, since it fixes the upper-right edge cubie.

But the cost of this element *with respect to the generating system

L[E],D[E],F[E],B[E]* is not 1.

We can repair this by choosing a different generating system for

<L[E],D[E],F[E],B[E]>, for example the system

L[E],D[E],F[E],B[E],R[E]*r[E]',U[E]*u[E]'.

So in general a model for the solution up to rotations for a

certain set <orbits>, is a supplement of C[<orbits>] in CG[<orbits>],

with a generating system that respects costs.

Jerry continued

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.)

This is the reason why I think that it is better to talk about

CG[C,E]/C[C,E]. As you say G[C,E] <> CG[C,E] (it has index 2),

and C[C,E] is not a subgroup of G[C,E]. That your model works

depends on the fact that their is a bijection between the set

CG[C,E]/C[C,E] and G[C,E]/E[C,E]. This follows by a standard

argument from the fact that E[C,E] = Intersection( G[C,E], C[C,E] ).

Jerry continued

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).

It would be most surprising. In fact C[C], C[E], and C[C,E] are

*not* normal in their respective CG's. I don't see what face

centers should have to do with it.

Jerry continued

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.)

Allow me to translate this to a more group theoretic language.

You are interested in finding God's algorithm for CG[C].

If e is any element of this group, then clearly it has the same costs as

(c * e), where c is any element of C[C]. Thus you need only compute the

cost for one representative of each right coset (C[C] * e). All those

cosets have size 24, so using cosets reduces the problem by a factor 24.

However, (c' * e * c) also has the same cost, so you only need one

representative of each conjugacy class (e ^ C[C]). Taking those two

approaches together means, that you need only look at one representative

of the set { c1 * (c2' * e * c2) | c1, c2 in C[C] }.

But we can also write this set as { c1 * e * c2 | c1, c2 in C[C] }. Such

a set if usually called a *double coset* and written as (C[C]*e*C[C]).

Most of those double cosets have size 576 = 24*24, but some are smaller

(but of course all sizes are always multiples of 24, since each double

coset is the union of single cosets). Thus using double cosets reduces

the problem by a factor almost 576.

Finally e has the same cost as (x' e x), where x is the reflection. Thus

you only need one representative from each set { y' * c1 * e * c2 * y |

c1, c2 in C[C], y in M[C] }. This reduces the problem by an total factor

almost 1152.

Jerry continued

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.

Lets first take a look at the 3x3x3 cube, i.e., CG[C,E,F] = CG.

In this case you can use G as a supplement for C, i.e., as a system of

representatives for the cosets (C * e). Now G is normal in CG,

thus you can conjugate the elemenents of G with elements of C and stay

in G. So there is a bijection between the representatives of the

conjugacy classes of G under the conjugation by C and the representatives

for the double cosets (C * e * C). In fact G is normal in MG,

and there is a bijection between the representatives of the

conjugacy classes of G under the conjugation by M and the representatives

for the sets ((C * e * C)^M). This is the basis for applying

the ``Lemma that is not Burnside's'' to count the number of such sets,

as the real size of the cube.

But in the case of the 2x2x2 cube without centers, i.e., CG[C],

this is not possible. Finding such a model would mean finding

a supplement of C[C] that is normal in CG[G], i.e., is fixed

under conjugation by C[C]. And no such supplement exists.

Jerry continued

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?

Yes I can ;-). The problem is in the statement ``and M-conjugates are

appropriate to the coset model''. I think this problem comes from

your unusual usage of the notation G[C]/C[C]. If C[C] was a normal

subgroup of G[C] and G[C]/C[C] was the proper factor group, then

the operation of M-conjugation would carry over from G[C] to the

factor group (any such operation carries over to a factor group,

provided that the normal subgroup is fixed, which is certainly the

case here). But G[C]/C[C] is not the proper factor group, so there

is no reason why the M-conjugation should carry over, and in fact

it does not.

Finally allow to correct a non-standard language again. In group theory

one usually does not speak of the symmetry group of another group, but of

the *automorphism group* of another group. Moreover you don't want to

know the ``subgroup of M which was *the* automorphism group of

<D[C],B[C],L[C]>'', but the ``subgroup of M which was *also a subgroup

of* the automorphism group of <D[C],B[C],L[C]>'', because the

automorphism group of <D[C],B[C],L[C]> is in fact much larger. In other

word, you want to know the subgroup of M that fixes <D[C],B[C],L[C]>.

This is a cyclic group of size 3, namely the rotation along the diagonal

axis of the cube that goes through your fixed center and cyclically

permutes D[C], B[C], and L[C].

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