[next] [prev] [up] Date: Thu, 08 Dec 94 13:59:48 -0500
[next] [prev] [up] From: Jerry Bryan <BRYAN@wvnvm.wvnet.edu >
[next] [prev] [up] Subject: Re: Models for the Cube
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
GC=<QC> 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 CGC,E or CGC,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 GC 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=<QC,E,CC,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 CC, CE, and CC,E are all normal
subgroups of their respective CG's, but that CC,F, CE,F, and
CC,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 <QC> by 24*48 times. However, everybody else
who worked on the problem had modeled it as something like
<DC,BC,LC>, 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.) <DC,BC,LC> is 24 times smaller than <QC> in the first
place, and as I said earlier, <QC> is equivalent to <QC,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 <QC,F>. Since the model was <QC>,
there really was a reduction of 24*48. But <QC> 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 <DC,BC,LC>,
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 <DC,BC,LC>,
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 <DC,BC,LC>.
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 <DC,BC,LC> is isomorphic to a coset model
such as <QC>/CC, 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

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