With most of my large breadth-first searches of God's Algorithm, I have
used M-conjugacy, where M is the set (and group) of 48 rotations and
reflections of the cube. Using M-conjugacy reduces the size of the
problem by about 48 times, and allows me to search one or two levels
deeper than would be possible without M-conjugacy.

I haven't even written a basic program for Shamir's method yet, but it
occurs to me that if Shamir's algoritm could be combined with M-conjugacy,
tremendous benefits would accrue.

As before, we define Q[n] to be the set of positions which are n quarter
turns from start, and T[n] to be the union of Q[k] for k in 0..n. I have
been thinking in terms of using Shamir's method on T[5] to get Q[6]
through Q[10]. But T[5] isn't exactly tiny as it contains 105046
elements. Plus, we already have Q[0] through Q[11] calculated by other
means, so we wouldn't be learning anything new.

Define Q*[n] to be the set of representative elements of M-conjugacy
classes of length n, and T*[n] to be the union of Q*[k] for k in 0..n.
T*[5] only contains 2229 elements, which is much more manageable than
105046 elements. T*[6] contains 20624 elements. This is still quite
manageable, and might well permit us to calculate Q[12], which would be
something new. T*[7] contains 192153 elements. This is right on the bare
edge (maybe past the bare edge) of what could be handled on most machines.
But if we could handle it, we possibly could calculate Q[13] and Q[14] --
a really major advance in our knowledge of God's algorithm.

I haven't yet figured out entirely how to marry Shamir's method with
M-conjugacy. But let me provide a general outline of what would have to
be done, and identify the major problem areas.

Without repeating all the details, recall that we can in theory modify
Shamir's method to calculate T[2n] (and all the respective Q[k]'s) as the
product (T[n] x T[n]). Very, very roughly speaking, we seek to calculate
T*[2n] as the product {T*[n] x T*[n]). But there are many, many
complications along the way.

Here are some preliminaries.

First, given a representative X in Q*[n], we can calculate its entire
M-conjugacy class as {m'Xm | m in M}. I usually just write this set as
{m'Xm}. In group theory, an element m'Xm is often written as X^m and the
set {m'Xm} is often written as X^M. I will adopt the group theory
notation to some extent in the remainder of this paper.

Given Q*[n], we can create Q[n] by simply expanding the M-conjugacy
classes for each X in Q*[n]. In most of my work, the Q[n] which is thus
created is sort of virtualized -- created but not stored. I will denote
the virtualized version of Q[n] as Q*^M[n] to distinguish it from the real
version. Notice that we do have Q*^M[n]=Q[n], so Q*^M[n] can serve as a
surrogate for Q[n] most anytime we need it to. Similarly, we denote the
virtualized version of T[n] as T*^M[n].

Second, we define * to be a function (not a permutation) which can be
composed with permutations to calculate a representative element. We
define X* to be Repr(X), which is really Repr{X^M}. So we can have such
things as XY* or (X*)(Y*).

I have generally implemented X* as min{X^M}. By this, we mean place X^M
in lexicographic order, and choose the first element. Basing the
representative element of X^M on lexicographic order fits in well with
Shamir's method.

We now return to the idea of calculating T*[2n] as the product (T*[n] x
T*[n]). We first note that the product of representatives is not
necessarily a representative, so we would have to calculate (T*[n] x
T*[n])* to assure that all we have is representatives.

We also note that if we simply calculate all the products st* for s and t
in T*[n], we will have about 48 times too few products. On the other
hand, if we calculate st* for s and t in T*^M[n], we will have about 48
times more products than we need. What is required is to calculate st*
for s in T*[n] and t in T*^M[n]. In other words, we expand the
equivalence classes for t but not for s.

In a sense, this is what I have always done for my non-Shamir searches,
except that I have only advanced by one level of the search at a time.
That is, I have calculated (Q*[n] x Q*^M[1])* to get to Q*[n+1]. But
remember that Q*^M[1] is just Q[1], which in turn is just Q, the set of
quarter turns.

That was the sanitized version. The dirty version is that you have to
calculate (in lexicographic order) o'(s(m'tm))o, for all o in M, for all m
in M, and for all t in T*[n]. The s is a fixed element of T*[n], and the
results for all s in T*[n] are merged in standard Shamir fashion.
Finally, these products will include representatives and
non-representatives alike, and you have to keep only representatives and
throw away the non-representatives.

Calculating these products is trivial. Getting them to come out in
lexicographic order is the hard part. As I said at the beginning, I am
not sure I know how to do it yet. But I have some ideas about it that I
will be sharing.

 = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =
Robert G. Bryan (Jerry Bryan)                jbryan@pstcc.cc.tn.us
Pellissippi State                            (423) 539-7127
10915 Hardin Valley Road                     (423) 694-6435 (fax)
P.O. Box 22990
Knoxville, TN 37933-0990