Dan Hoey was the first to write concerning the Polya-Burnside theorem
(he used it in has calculation of the real size of cube space),
and Martin Schoenert recently posted a proof of the theorem.
I would like to add some additional comments.

First, I quote from Martin:

If $g \in G$, then I denote the set of elements that are really
equivalent to $g$ by $g^M$. Jerry denotes this set by {m'gm},
but $g^M$ is the more common notation in group theory.

I have just copied the {m'gm} notation from others on this list.
I haven't searched the archives to see when it first appeared.
In fact, what I really say is {m'Xm}. A few points:

1) {m'Xm} is a shorthand for {m'Xm | m in M}, where X is assumed
to be a fixed but arbitrary element of G.

2) m' is used rather than Martin's preferred m^(-1) as a concession
to the difficulties of using mathematical notation in E-mail.
Again I haven't searched the archives, but this convention seems to
go back to the earliest days of Cube-Lovers.

3) X is used rather than g throughout Cube-Lovers, I think due
to Singmaster. Singmaster uses upper case letters for processes
and lower case letters for the cycles of cubies.
Hence, we have such things as X=URB'L or Y=RL'UD', etc. For
most purposes, we simply identify processes such as X and Y
with the permutation which is effected by the respective
process, and there is no loss of generality from such
identification. I interpret g in G as being a permutation
directly, without regard to which process might
effect the permutation. But again, for most purposes there
is no loss of generality in identifying the X's with the g's.

But let's go along with Martin for a moment and write {m'gm}.
We normally interpret this as {m'gm | m in M}, but we could
just as well interpret it as {m'gm | g in G}. This new interpretation
simply yields G, but in a different order. To say "in a different
order" is a bit of a corruption because sets don't have order. But
it's useful to think about the "different order" anyway.

M-conjugation for a fixed m in M can be viewed as a permutation on
the set of quarter turns Q. (See for example Hoey and Saxe's
_Symmetry and Local Maxima_). But it can also be viewed as a
permutation on G itself. So for each of the forty-eight m in M,
M-conjugation is a different permutation on G. This will shortly prove
to be very useful.

What if we interpret {m'gm} as {m'gm | m in M and g in G}?
Again, this is a bit of a corruption, because "m in M and g in G"
will list each element of G forty-eight times, and Set Theory 101
says each element of a set is listed only once. But
let's ignore that difficulty and picture "m in M and g in G"
as creating a matrix with forty-eight columns indexed by M and
|G| rows indexed by G. Each column is a different permutation
on G.

Now we detour a minute and note that this matrix contains
|G|*|M| cells. Given that, how big is G? Well, it is (|G|*|M|)/|M|.
This may seem tautological, but not quite. That is, I am not
asking how many rows in a 7 by 3 matrix. Rather, I am asking
how many rows in a matrix if the matrix has 21 cells and 3 columns.
Trivial though it may be, we have to perform the division to determine
the answer.

I am reminded of an old joke. A mathematician is asked how many
legs a horse has. The mathematician observes that the horse has
two front legs, two back legs, two left legs, and two right legs
for a total of eight. But this procedure counts each leg twice,
so the mathematician divides by two to obtain the correct answer.

Many counting formulas work in a similar fashion. They overstate
the correct number, and then adjust by dividing out or subtracting
out the excess. In this manner, the number of cells in the
|G|*|M| matrix overstates the size of G by forty-eight, so we must divide
by forty-eight to get the true size of G.

The Polya-Burnside theorem has to do with counting conjugacy classes.
Martin's proof does not mention the word "matrix", but it effectively
creates a binary matrix with dimension |G|*|M| where each
cell contains the Boolean value (g == m'gm). In other words, the cell
contains a 1 if g=m'gm and 0 otherwise. Martin's proof shows that the
number of M-conjugacy classes is the number of 1's divided by forty-eight.

In his note about the real size of cube space,
Dan mentions a book called *Geometry and Symmetry* by Paul Yale.
Yale's book includes a Polya-Burnside proof similar to Martin's.
In an example accompanying his proof, Yale shows a matrix where the
cells are either blank or contain a check mark. Yale counts the
check marks, and Martin counts the 1's. Martin's approach has the
advantage that you can count 1's simply by summing them.

To me, the key point in both proofs is the observation that
you get the same answer whether you count the 1's or checkmarks
by row, or whether you count them by column. This observation
manifests itself in Martin's proof as follows:

Thus the number of M-conjugacy classes is
$1/|M| \sum_{g \in G} \sum_{m \in M} {(g^m == g)}$.

Now we can simply change the order of the two summations, so we get
$1/|M| \sum_{m \in M} \sum_{g \in G} {(g^m == g)}$.

(When I read this last sentence in Martin's proof, the thought that
came to mind was "He transposed the matrix!", even though there is
no matrix there explicitly.)

The essence of Polya-Burnside is that summing by row gives us the
answer we desire (namely the number of M-conjugacy classes),
but summing by column is the calculation which is possible in
practice. And serendipitously, both sums give us the same answer.

Let us consider each sum in turn. (Actually, the matrix I am
describing is transposed compared to the one in Yale's book, but
we will continue with |G| rows and |M| columns for the purposes
of this note.)

Martin's proof gives a good explanation why summing by row gives us
the answer we desire. Let me give a slightly different (but I think
equivalent) explanation.

Suppose |{m'Xm}|=48. This is the case where Symm(X)=I, so that the
position is "completely asymmetric". The row indexed by X will
contain a single 1 and forty-seven 0's. The single 1 will appear
in the column indexed by the identity in M. The other forty-seven
elements of {m'Xm} will similarly appear in a row containing only
a single 1. Hence, the number of 1's in these forty-eight rows
will be 48*1, and the number of M-conjugacy classes represented by
these forty-eight rows will be (48*1)/48. The number of 1's has
overstated the number of conjugacy classes by exactly 48.

Now suppose |{m'Xm}|=24. We have |Symm(X)|=2. The row indexed
by X will contain two 1's and forty-six zeros. Similarly, the
rows indexed by the other twenty-three elements of {m'Xm} will
also contain two 1's and forty-six 0's. The number of 1's in these
twenty-four rows will be 24*2, and the number of M-conjugacy classes
represented by these twenty-four rows will be (24*2)/48. Again,
the number of 1's has overstated the number of conjugacy classes
by exactly 48.

The pattern should be clear. If |{m'Xm}|=16, we will have
(16*3)/48 M-conjugacy classes scattered over three rows.
If |{m'Xm}|=12, we will have (12*4)/48 M-conjugacy classes scattered
over four rows. Etc. In all cases, summing the 1's
overstates the number of M-conjugacy classes by exactly forty-eight,
so in all cases we must divide by forty-eight to compensate.
It is therefore clear that to calculate the total number of
conjugacy classes, we simply sum the entire binary matrix and divide
by forty-eight. It doesn't really matter whether we sum by rows,
sum by columns, some in some other order, or sum in no order at
all.

Polya-Burnside essentially says that we can sum by columns. The
forty-eight column sums are the number of elements of G which
are fixed by conjugation by the respective elements of M. Polya-
Burnside is usually stated something like "the number of conjugacy
classes is equal to the average of the number of fixed points ....",
where there is sufficient language to make sure that the fixed
points in question are the points in G fixed by conjugation by M.
In the matrix at hand, we form the forty-eight column sums,
add them up, and divide by forty-eight.

If that is not an average (adding up forty-eight numbers and dividing
by forty-eight), then I don't know what is. But I confess this does
not look and feel like an averaging problem to me. Rather, it looks
and feels like a horse's legs problem where we are overstating the
answer and dividing out the excess. It feels more comfortable to me
just to add up the entire binary matrix without regard to rows and
columns and then to divide by forty-eight, but that is not the way
Polya-Burnside works.

Forming the forty-eight column sums is no small problem. Martin's
little GAP program accomplished this task using the Centralizer function.
Unless my E-mail system has lost it, we are still awaiting a description
of GAP's algorithm for calculating the Centralizer.

Dan's method was a "by hand" calculation of the column sums. He
determined the number of elements of G fixed by m based on an
argument concerning the cycle structure of elements of G.
Dan took one very nice shortcut. There really is no need to
calculate all forty-eight column sums. A number of the elements
of M are themselves M-conjugate and there are ten conjugacy classes,
so Dan only had to calculate ten column sums.

One of the ten calculations really wasn't necessary. The column
indexed by the identity in M contains |G| 1's, so we have
one of the ten required column sums without further ado. This column
alone shows that the number of M-conjugacy classes is at least
|G|/|M| = |G|/48. As it turns out, this is very close to the
true value. The other forty-seven columns of the matrix are extremely
sparse, so relatively speaking, there are not many more
conjugacy classes than |G|/48.

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