[next] [prev] [up] Date: Wed, 07 Dec 94 20:45:00 -0700 (PST)
[next] [prev] [up] From: Martin Schoenert <Martin.Schoenert@math.rwth-aachen.de >
[next] ~~~ [up] Subject: Models for the Cube
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        /
      \      /
       \    /
        \  /

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

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 Sch"onert,   Martin.Schoenert@Math.RWTH-Aachen.DE,   +49 241 804551
Lehrstuhl D f"ur Mathematik, Templergraben 64, RWTH, 52056 Aachen, Germany

[next] [prev] [up] [top] [help]