From:

~~~ Subject:

I wrote in my e-mail message of 1994/11/08

The way I view this is as follows. The entire cube group C is a

permutation group group on 6*9 points, generated by the six face turns U,

D, L, R, F, B; the three middle slice turns M_U, M_L, M_F; and the

reflection S. This group has a subgroup M of symmetries of the cube (of

order 48), generated by U M_U D', L M_L R', F M_F B', and S. Another

subgroup is G, generated by the six face turns, which has index 48 in G.

G is a normal divisor of C, G is the semidirect product of M and G. The

same is true for GE and GC.

Jerry Bryan writes in his e-mail message of 1994/11/08

I have discussed a similar view of things recently, except that I was

not brave enough to include a reflection in the generators. C is

normally used to denote the set of twenty-four rotations of the

cube (a sub-group of M), so let's call your "entire cube group"

big_G instead. My version of big_G was generated by Q plus the

slice moves (like yours without the reflection), or alternatively

by Q plus C. Your version of big_G is hence the same as the one

I discussed except that you added a reflection. C (the rotations C,

that is) is a sub-group of both versions of big_G. M is a sub-group

of your version of big_G, but not of mine.Your big_G has the obvious advantage of including M as a sub-group.

Mine has the advantage (?) of being physically realizable on a

real cube. That is, for X in your big_G, rX or Xr (r is a reflection)

is also in your big_G. For X in my big_G, rX or Xr is not in

big_G, and correspondingly a single reflection is not physically

realizable on a real cube. Of course, r'Xr is in big_G in either

case, r being in M. Also, cX and Xc are in either version of big_G

for all c in C.

OK, I guess I have to be a little bit more precise and also to adapt

my terminology to common usage. First a picture.

MG (48*|G|) /| / CG (24*|G|) / /| / / | / / | / / G (|G| = 8!*3^7 * 12!*2^11 / 2) / / | / / | / / | / / | / / | / / / / / / / / / (48) M / / |/ / (24) C / \ / \ / \ / <1>

The maximal cube group *MG* is a permutation group on 6*9 points.

It is generated by the six face turns < U, D, L, R, F, B >, the three

rotations of the entire cube < u, l, f >, and the reflection < x >.

The complete cube group *CG*, generated by < U, D, L, R, F, B > and

< u, l, f >, is a subgroup of MG of index 2.

The cube group *G*, generated by < U, D, L, R, F, B >, is a subgroup of

index 24 in CG. G can be viewed as a permutation group on 48 points,

since it fixes the 6 center cubies.

The group *M* of symmetries of the entire cube, generated by < u, l, f >

and < x >, is a subgroup of MG of size 48.

The group *C* of rotations of the entire cube, generated by < u, l, f >,

is a subgroup of CG of size 24.

(I would have preferred S instead of M and R instead of C, but M and C

are too widely used to change that notation. Of course MG is not called

MG because it is the maximal cube group, but as a reminder that it is the

product of M and G. Likewise for CG.)

Jerry continues

I tend to think that Singmaster's standard G=<Q> is not what people

think of when they hold a real cube in their hand. Rather, they

tend to think of big_G/C. That is, the cosets of C in big_G are

common sensically considered to be equivalent because rotating

a real cube in space is "doing nothing". Also, for my version

of big_G we have |big_G/C| = |G|.

True, what people really see is the complete cube group CG (what you call

big_C). That is, patterns corresponding to two different elements of CG

are distinct. Now if two patterns can be made equal by rotations of the

entire cube, they ``look alike'' and most people feel that they are

equivalent since rotations ``cost nothing''. Especially they feel that

any pattern corresponding to an element in C is solved. Mathematically

we describe this equivalence by saying that all 24 elements in each coset

of C are equivalent.

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.

First note that for each coset of C in CG, there is exactly one element

of G in this coset. This follows since C and G together generate CG and

have trivial intersection. We call this element the representative in G

of the coset. Thus G is a set of representatives for the cosets of C in

CG. In group theory terminology G is a *supplement* for C (if C was a

normal subgroup, then G would be called a complement of C). An immediate

consequence is that |G| = |CG| / |C|.

Next note that, if we assume that rotations ``cost nothing'' and middle

slice turns cost (at least) twice as much as face turns, then any two

elements in a coset of C have the same *cost*, i.e., distance from the

solved cube, and this is equal to the cost of the representative in G.

This is a simple consequence of the fact that we can transform each

process p_1 p_2 ... p_l, where each p_i is either a face turn or a

rotation of the entire cube, into one which has a single rotation of the

entire cube first and then only face turns afterwards. This can be done

using the rule <face-turn> <rotation> => <rotation> <another-face-turn>,

which obviously doesn't change the cost of the process (remember

rotations cost nothing).

Finally note that G's structure as a group is in a certain sense CG

without C. Namely G is a normal subgroup of CG, and the factor group

CG/G is isomorphic to C. Ideally we would like to have G be isomorphic

to CG modulo C, but this is not well defined, as C is not a normal

subgroup. Put another way, CG is the semidirekt product of G with C.

Unfortunately the existence of this model is particular to the 3x3x3

cube. It does not work as well for other cubes.

First take the 2x2x2 cube group CG_2 (I use a _2 to distinguish the 2x2x2

subgroups from their 3x3x3 counterparts). Again we have a subgroup C_2,

generated by the rotations, of size 24. But the subgroup G_2, generated

by the six face turns, is in fact equal to CG_2. In particular it is not

a supplement to C_2.

But we can make a similar construction. Namely in the case of the 3x3x3

we can view CG as generated by the six face turns and the three middle

slice turns < M_U, M_D, M_F > (instead of the six face turns and the

three rotations < u, d, f >). And our supplement G was the subgroup of

CG generated by 6 of those 9 generators, were the 3 removed ones are

pairwise perpendicular. In the case of the 2x2x2 cube we can take the

subgroup H_2 that is generated by three turns < U, L, F >. Using the

transformations <face-turn> <rotation> => <rotation> <another-face-turn>

and D => u' U, R => l' L, B => f' F, we can again transform any process

into one which has a single rotation first and then only < U, L, F >

turns afterwards, without changing the cost of the process (again

rotations cost nothing).

Thus H_2, of size 7!*3^6, is a good model to use when one is looking for

God's algorithm for the 2x2x2 cube. Nothing of this is really new, I

have just casted it into a different language. For example see

'http://www.math.rwth-aachen.de:8000/~mschoene/Cube-Lovers/

Jerry_Bryan__God's_Algorithm_for_the_2x2x2_Pocket_Cube.html'.

But H_2 is *not* normal, and is not CG_2 without C_2 (in the sense in

which G was CG without C). For example CG_2 has a factor group

isomorphic to S8, but there is no such factor in H_2.

Things get worse when we look at the nxnxn cube groups CG_n. We can find

again find a supplement H_n for C_n, if we leave out three pairwise

perpendicular slice turns. If n is odd and if we leave out the three

middle slice turns, then H_n is again a normal subgroup (and in the same

sense as above, it is again CG_n without C_n). On the other hand if n is

even then H_n is never a normal subgroup. Moreover if 3 < n, then the

transformation rules tell us to replace one of the removed slice turns by

a rotation and the product of the n-1 parallel slice turns. Thus the

transformation would only respect the cost, if we assume that the removed

three slice turns have cost n-1. While this is arguably true for n = 3,

where most people feel that the middle slice turns have cost 2, I don't

think anybody feels that for the 4x4x4 cube nine of the slice turns have

cost 1 and 3 have cost 3.

And now for something completely different (no, not really ;-).

I have argued that G is a good model for the 3x3x3 cube assuming that

rotations of the entire cube cost nothing, and that middle slice turns

have cost 2 (or higher). In a certain sense, we got rid of C. That

doesn't mean we can't use C anymore. In fact, C is still very useful.

Namely let c be any element of C, and g be any element of G. Then c' g c

is another element of G, because G is a normal subgroup. Moreover the

cost of c' g c is the same as the cost of g. This is trivial because

each process effecting g can be turned into a process effecting c' g c,

by replacing each generator x in this process by c' x c.

But C is not the largest such group. The largest such group is M, i.e.,

the full group of symmetries of the entire cube. This is the reason why

I prefer to view G as a subgroup of MG, which is the semidirekt product

of M and G, even though I realize that MG is not physically realizable.

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