[next] [prev] [up] Date: Sat, 10 Dec 94 15:12:00 -0700 (PST)
[next] [prev] [up] From: Martin Schoenert <Martin.Schoenert@math.rwth-aachen.de >
[next] [prev] [up] Subject: Re: Re: Models for the Cube
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

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