As you all know, the length of a cube X is defined as the shortest
process P such that XP = I, and is denoted as |X|. One definition
of God's Algorithm is simply that God's algorithm is the knowledge
of |X| for all cubes. I wish to make some observations about
|X| as related to various models of the cubes and their symmetries.

The set C is the set of 24 rotations of the cube. The set M is the
set of 48 rotations and reflections of the cube, where half of M is
C and the other half of M is C reflected.

The first (obvious) observation is that |X| = |m'Xm| for all m in M.
That is, the set of all M-conjugates of a cube have the same
length. Another way to say the same thing is that |m'Xm| = |n'Xn|
for all m and n in M.

Actually, there is an even more obvious observation that probably
should be made. The set G is the set of all cubes, where
G is generated as G=<Q>, where Q is the set of 12 quarter-turns
of the cube. The *really* obvious observation is that if X
is in G, then m'Xm is in G for all m in M. Furthermore, if GC
is the set of corners-only cubes, then X in GC implies m'Xm in GC,
and if GE is the set of edges-only cubes, then X in GE implies
m'Xm in GE. Finally, the observation that |X| = |m'Xm| remains
true whether X is in G, in GC, or in GE.

The process of forming M-conjugates in G (or in GC or in GE)
induces a partition which is an equivalence relation. Hence, the
set {m'Xm} for all m in M is an equivalence class. Since,
|m'Xm| = |n'Xn| for all m and n in M, it is meaningful to speak
of the length of {m'Xm}, namely |{m'Xm}| = |Y|, where Y is
any element of {m'Xm}.

Now, consider cubes of the form Xc where X is in G and c is in C.
We first observe that Xc is in G if and only if c is even. Half the
elements in C are even, and half are odd. An odd permutation in C is
even on the corners but is odd on the edges; hence, Xc is not in G when
c is odd. On the other hand, Xc is in GC for all X in GC, and Xc is in
GE for all X in GE.

The fact that Xc is in G only for even elements of C is why I thought
it was important to make the "really obvious" observation that
m'Xm is in G for all X in G and all m in M. The two cases m'Xm and
Xc are similar on the surface, but different when you dig a
little bit deeper.

With respect to lengths, we can observe that |Xc| >= |X| whenever
Xc is well-defined (that is, whenever c is even for G, or for all c
for GC and GE).

The process of performing rotations in G (even rotations in G, or any
rotation in GC or in GE) induces a partition which is an equivalence
relation. Hence, the set {Xc} for all (or even, as appropriate) c
in C is an equivalence class. The collection of all sets of the form
{Xc} can serve as a model for cubes without centers.

However, it is not the case that |Xc| = |Xd| for all c and d in C.
Nonetheless, it is meaningful to speak of |{Xc}|.  Namely,
|{Xc}| = min{|Xd|} for all (or even) d in C.  Hence, we have
|{Xc}| <= |Xd| for all (or even) d in C.

The definition |{Xc}| = min{|Xd|} probably requires a bit of
justification. For a cube without centers, the solved or Start
state is {Ic} for all (or even) c in C. Hence, Start is C (or
C[even]), and we need the shortest process P such that XP is in C
in order to calculate |{Xc}|.

Consider the set {P[1], P[2], ... P[24]} where P[n] is the shortest
process for which (Xc[n])P[n] = I.  Observe, that XP[n] is in C for
all n in 1..24.  This immediately gives us |P| <= |P[n]| for all
n in 1..24.

Conversely, if XP is in C, then there exists some c[n] in C such that
Xc[n]P = I.  This gives us |P[n]| <= |P| for some n in 1..24.
Therefore, |P| = min{|P[n]|} for n in 1..24.

Note that we have |{Xc}| <= |X| <= |Xd|. On its face, this may seem
somewhat paradoxical, but I believe that it is entirely correct.
There is a huge difference is speaking of |{Xc}| as opposed to
speaking of |Xd|. Xd is an (atomic) element of G; {Xc} is a set.
Elements of {Xc} are also in G, but the *set* {Xc} is not in G.

My model for cubes without centers is really {m'Xmc} rather than
{Xc}. However, the results from above are readily combined. That is,
we can speak of |{m'Xmc}|, namely |{m'Xmc}| = min{|(m'Xm)d|} for all
(or even) d in C. As before, we have |{m'Xmc}| <= |m'Xm| <= |m'Xmd|.
Note that in the middle of this last string of inequalities we could
insert any of |X| = |m'Xm| = |{m'Xm}|.

In my God's algorithm data base for cubes without centers, I store
ordered pairs of the form (Y,|{m'Xmc}|), where Y is a representative
element of the set {m'Xmc}. Note that Y is in G (or GC or GE, as
appropriate). It is a picky point, but the data base does *not*
consist of ordered pairs of the form (Y,|Y|). Remember that
|Y| >= |{m'Xmc}|.

My God's algorithm data base for cubes with centers nominally consists
of ordered pairs of the form (Z,|{m'Xm}|), where Z is a representative
element of the set {m'Xm}. Unlike the case without centers, we do
have |Z| = |{m'Xm}|, so we could also say the data base elements are
of the form (Z,|Z|).

However, the data representation is really a bit different to take
advantage of the relationship between sets of the form {m'Xmc}
and sets of the form {m'Xm}. A set of the form {m'Xmc} can be
partitioned into (up to) twenty-four sets of the form {m'Xm},
where the (up to) twenty-four sets are indexed by C.

Let Y=Repr({m'Xmc}). Then, the data base is ordered pairs of the form
(Yc[i],|Yc[i]|) for i in 1..24. Note that Yc[i] is in G, but can be
said to be a representative element for sets of the form {m'(Yc[i])m},
which in turn is a set of the form {m'Xm} for some X in G.

Finally, there is no real need to store the Yc[i]; it is only
necessary to store the lengths. Hence, a data base
element for cubes with centers is really, really of the form:

(Y,|{m'Xmc}|,|Yc[1]|,|Yc[2]|, .... |Yc[24]|),

where Y is a representative element of {m'Xmc}.

Note that this is a very compressed format. The representative element
Y is stored only once for the 24 different values for c. Note also that
the solution for cubes without centers is stored in the same data base
as the solution for cubes with centers. Finally, since
|m'Yc[i]m| = |Yc[i]|, we have stored the length of all cubes by storing
the length of only one cube for each M-conjugancy class.

It is not really necessary explicitly to store the solution for cubes
without centers to have the solution for cubes without centers in the same
data base. That is, |{m'Xmc}|=min(|Yc[i]|) for i in 1..24. But it takes
very little space to do so and is convenient for certain calculations.

(to be continued)

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

If you don't have time to do it right today, what makes you think you are
going to have time to do it over again tomorrow?