From:

~~~ ~~~ Subject:

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