Pólya-Burnside Enumeration

My previous post regarding the need to study notwithstanding, I want to talk about Pólya-Burnside enumeration*. It's a way to count the number of orbits of elements subject to a group action. This sounds all technical and uninteresting, until one realizes that molecules, under the set of "rigid" operations that leave the molecule invariant, is such a set of elements, with the operations themselves being the group action. (By "rigid", it pretty much means rotations only. In particular, no mirrors. However, I don't see why this theorem won't work with point groups - after all, point groups are groups!)

To make things more formal and rigorous, I need to talk about groups and group actions for a bit.

Well. First things first. A group G is a nonempty set S with a binary operation, *, satisfying four things:

• S is closed under the operation. In particular if a, b are in G, then a*b is in G
• * is associative. That is, if a, b, c are in S then

  a*(b*c) = (a*b)*c

• There exists an identity element: that is, there exists an e in S such that for all a in S, e*a = a*e = a
• Every element has an inverse: for all a in S, there exists a b in S such that a*b = b*a = e, where e is defined as in the previous point

Alot of things are groups: examples include the set of rationals under addition and the set of bijections under composition. It is easy to show that e and the inverse of a (which I'll start to call a^-1) are unique.

Second thing up: group action. Given a group G and a set X (X doesn't have to be a group), a group action is a function

\Psi: G \times X \to X

satisfying two things:

• Ψ (e, x) = x for all x in X
• Ψ (g, Ψ (h, x)) = Ψ (gh, x) for all g and h in G, x in X

If G has a group action with X, we say that G acts on X.

This definition is actually pretty natural. If our group happens to be the set of rotations, one of which is g, and x happens to be a molecule, a group action is the act of performing a rotation g on the molecule x.

The set of g in G such that Ψ (g, x) = x is called the stabilizer of x, written as S_G(x).

We can define a binary operation ~ on X, by saying x ~ y if there exists a g in G such that Ψ (g, x) = y. We can show things like this binary operation is an equivalence relation, that the stabilizer is a subgroup of G (i.e. a subset in G that is a group), and more interestingly, that if G and X are finite, then

|[a]| = \displaystyle{\frac{|G|}{|S_G(a)|}}

where [a] is the equivalence class of a, also called the orbit of a.
(I won't prove the last point although it's relevant to our discussion, because then I'll have to talk about Lagrange's Theorem and cosets and stuff and that'll make this blog post too long).

Theorem (this theorem has waaaaay too many names, like Cauchy-Frobenius Lemma and Burnside's Theorem)

Suppose that the finite group G acts on a finite set X. Then the number of orbits [X/G] is given by

[X/G]=\frac{1}{G}\sum_{g \in G}F(g)

where F(g) is the number of elements in X that's fixed by g (i.e. the set of x's such that g is in the stabilizer of x).

The proof is short and sweet. Fix x in X. Consider

\sum_{g \in G}F(g)

The element x is counted in the sum once, every single time g is in S_G(x). So x is counted |S_G(x)| times.

But we are counting orbits not elements. Every element in a particular orbit is counted |S_G(x)| times, and there's

\displaystyle{\frac{|G|}{|S_G(x)|}}

elements in an orbit, so in total an orbit is counted

S_G(x)\cdot\displaystyle{\frac{|G|}{|S_G(x)|}}=|G|

times. In other words,

\sum_{g \in G}F(g) = [X/G]\cdot|G|

Ok, what's this good for? I'll give one example in the next post.

Apparently Pólya's original paper is awesome, but I can't read it because it's in German. There's an English translation in my school's library, but someone borrowed it!

(Random tangent: hey, the featured article of the day is the aldol reaction! Cool!)

*My group theory professor spent a lecture on this, so that's why I know about it.