Last month Jerry Bryan <BRYAN%WVNVM.BITNET@mitvma.mit.edu> posted a
sequence of articles about counting the number of M-conjugacy classes
of Rubik's cube positions. Having calculated the number of conjugacy
classes of the corner and edge groups separately, his idea was to
combine these to calculate the number of conjugacy classes of the
entire group. Eventually, he withdrew the calculation, after
realizing that he had not found enough information to determine the
answer. This article is about how we might calculate the answer from
separate searches of the edge and corner groups.

My first idea is to formalize the concept of symmetry in the conjugacy
classes that Jerry used in his searches. Recall that the conjugacy
class of a position X is defined to be the set of all positions m'Xmc,
where m is an element of M, the 48-element symmetry group of the cube,
and c is an element of C, the 24-element subgroup of M consisting of
rigid rotations of the cube in space. The reason some positions have
more symmetry than others is that for some positions, there are
nontrivial elements m and c such that m'Xmc=X. The way in which this
arises can be formalized as a kind of symmetry group of X.

For an edge-group position X, let CSymm(X) be the set of all f in M
such that X'f'Xf is an element of C. First, I'll claim that CSymm(X)
is a subgroup of M [see proof 1, below]. Second, I note that CSymm(X)
is the set of all m in M such that there exists c in C with m'Xmc=X
[proof: m'Xmc=X iff X'm'Xm=c']. Third, I'll claim that if m'Xmc=Y,
then CSymm(X) and CSymm(Y) are conjugate subgroups of M [proof 2]. So
when Jerry says that a position X has order-N symmetry, he is saying
that CSymm(X) has 1152/N elements. But the identity of CSymm(X) has
more information than just its size, and I believe this information is
crucial if we are to combine symmetry groups. It looks to me as if it
would be sufficient to record the conjugacy class of CSymm(X), and
there are only 33 possibilities.

Now the usual symmetry group of X, Symm(X), is defined to be the group
consisting of all f in M such that X'f'Xf=I [or, equivalently, Xf=fX.
Symm(X) is the largest group such that X is Symm(X)-symmetric, in the
sense of the Symmetry and Local Maxima article]. The first step in
combining the corner and edge sets is to calculate the symmetry groups
of the rotations of a position X, AllSymms(X)={Symm(Xc) : c in C}.
This corresponds to computing the symmetry groups of the edges-and-
centers group from the symmetry groups of the edges group. I suspect
there is a way of computing this from CSymm(X), but I do not know it.
I am not even sure that AllSymms(X) is determined by CSymm(X). One
useful experiment would be to calculate CSymm(X) and AllSymms(Xc) for
all elements of the corner group and see what the correspondence is.

Barring an ability to calculate AllSymms(X) from CSymm(X), we could
calculate AllSymms(X) directly. This involves a great number of
calculations, though: 24 symmetry group calculations for each element
of the edge group. My first thought was to try to split the problem
up further, to deal with the group of permutations separately from the
group of orientations. But I abandoned this when I realized there is
a problem that shows up when we try this with the corner group. The
permutation of the corners that takes each cubie to its antipode is
clearly M-symmetric, and no matter how we decide to measure
orientation, there is a way to perform this permutation leaving the
cubies in their `home' orientation. But there is no way to compose
the two together in an M-symmetric way. I suspect the same problem
arises in the edge group.

But there may be some help from the edge search available in calcu-
lating AllSymms(X). For take a position Y in the edges-and-centers
group; Y is also a rotated position in the edges group, so Y=m'Xmc for
some X in Jerry Bryan's list. So for f in Symm(Y), Y'f'Yf=I is an
element of C, so f is in CSymm(Y). This says that Symm(Y) is a
subgroup of CSymm(Y), which is a conjugate of CSymm(X). So if Symm(Y)
is nontrivial, then CSymm(X) will also be nontrivial. So to find the
symmetry groups of the edges-and-centers group we need only look at
those positions that have nontrivial groups in Jerry's list (i.e. less
than order-1152 symmetry), as all the others will have Symm(Y)=I. So,
Jerry, do you have the data on how many positions of the edge group
have less than order-1152 symmetry, and which positions those are?

So, on to finding the symmetry groups of the Rubik's group positions.
We need to calculate Symm(X) for every element X of the edges-and-cen-
ters group and Symm(Y) for every element Y of the corners-and-centers
group, while keeping track of the permutation parity of X and Y. (The
permutation parity will be constant over each Symm(X), Symm(Y)). The
symmetry groups in the Rubik's group will be the intersections of
symmetry groups of edge and corner positions of the same parity. We
need not keep track of the particular positions here, only the numbers
for each parity and each (conjugacy class of) symmetry group. I have
a program that could produce a table easily enough. Recently, I took
a look in Paul B. Yale's _Geometry_and_Symmetry_ and it looks like
this is the sort of problem we could use the Polya-Burnside theorem
on. Unfortunately, I don't understand it yet, and it looks like the
number of cases here might be too large to conveniently carry out by
hand. So it would help to go after this problem computationally.

The rest of this article has the proofs for the claims I mentioned in
the second paragraph.
================================================================
Proof 1: Suppose f, g are elements of CSymm(X); it suffices to show
that f'g is an element of CSymm(X).
    X'(f'g)'X(f'g)=X(g'f)X(f'g)
                  =X'g'(Xgg'ff'X')fXf'g
                  =(X'g'Xg) g'f (f'X'fX) f'g,
                  =(X'g'Xg) (f'g)' (X'f'Xf)' (f'g).
Since we assumed f, g in CSymm(X), X'g'Xg and X'f'Xf must be in C.
(f'g)' and (f'g) are elements of M that are either both in C or
neither.  So the product is in C, so f'g is in CSymm(X).  Therefore
CSymm(X) is a group, QED.

Proof 2: Suppose Y=m'Xmc. First let f be an element of CSymm(X), so
that X'f'Xf is in C. I will first show that m'fm is an element of
CSymm(Y).

Y'(m'fm)'Y(m'fm)=(m'Xmc)'(m'fm)'(m'Xmc)(m'fm)
                =(c'm'X'm)(m'f'm)(m'Xmc)(m'fm)
                =c'm'(X'f'X)(mcm'fm)
                =c'm'(X'f'Xf)(f'mcm'fm)
All of which are elements of M, with an even number in C. Therefore
the expression is in C, so m'fm is in CSymm(Y).

Now let g be an element of CSymm(Y), so that Y'g'Yg is in C. Let
f=mgm', so f is an element of M such that m'fm is in CSymm(Y). I will
show that f is an element of CSymm(X):

X'f'Xf=(mc)(mc)'X'(mm')f'(mm')Xf(f'mcm'fm)(f'mcm'fm)'
      =(mc)(m'Xmc)'(m'fm)'(m'Xmc)(m'fm)(f'mcm'fm)'
      =(mc)Y'(m'fm)'Y(m'fm)(f'mcm'fm)'
      =(mc)Y'g'Yg(f'mcm'fm)',

which is in C, so f is in CSymm(X).

I've shown that for every element f of CSymm(X), m'fm is an element of
CSymm(Y), and that every element of CSymm(Y) is m'fm for some f in
CSymm(X).  Therefore CSymm(Y)=m' CSymm(X) m, QED.
================================================================
Dan Hoey
Hoey@AIC.NRL.Navy.Mil