# Intuitive explanation of Burnside's Lemma

Burnside's Lemma states that, given a set $X$ acted on by a group $G$,

$$|X/G|=\frac{1}{|G|}\sum_{g\in G}|X^g|$$

where $|X/G|$ is the number of orbits of the action, and $|X^g|$ is the number of fixed points of $g$. In other words, the number of orbits is equal to the average number of fixed points of an element of $G$.

Is there any way in which the fixed points of an element $g$ can be thought of as orbits? I had wondered aloud on my recent question here how (or if) Burnside's Lemma can be interpreted as having the same kind of object on both sides, so as to be a "true" average theorem, e.g.

"number of orbits = average over $g\in G$ of (number of orbits satisfying (something to do with $g$))"

or

"number of orbits = average over $g\in G$ of (number of orbits of some new action which depends on $g$)"

Since Qiaochu stated the comments to my question that he suspects Burnside's Lemma can be categorified, and that this may be related, I have also added that tag.

-
It seems to me that the answers so far ignore the actual question. It's not about a proof of Burnside's lemma. – Martin Brandenburg Dec 21 '10 at 9:10
@Martin: my answer to the actual question is "no," and to support that position I needed to introduce a proof. – Qiaochu Yuan Dec 21 '10 at 9:38
@Martin: leaving aside that "intuitive explanation" is perhaps somewhat subjective, I think that my answer qualifies. It shows that the formula results from counting the same finite set in two ways. – José Figueroa-O'Farrill Dec 21 '10 at 18:08

I'm not sure I'd call this a categorification, but the way I think of Burnside's Lemma is as follows.

Consider the subset $Z \subset G \times X$ consisting of pairs $(g,x)$ such that $g\cdot x =x$, where by $\cdot$ I just mean the action of $G$ on $X$.

The cartesian product $G \times X$ comes with the two surjections $\pi_G : G \times X \to G$ and $\pi_X : G \times X \to X$, and you can compute the cardinality of $Z$ either along the fibres of $\pi_G$ or along the fibres of $\pi_X$: the former gives you the sum over the fixed point sets, whereas the latter gives you a sum over the stabilizers. Then the orbit-stabilizer theorem does the rest.

-
Here's a 1-page PDF document with the details of my answer: dl.dropbox.com/u/5096148/Polya.pdf – José Figueroa-O'Farrill Dec 21 '10 at 6:25

One can view Burnside's lemma as a special case of the mean ergodic theorem, which links time averages to spatial averages, which may qualify as "equating two objects of the same type". On the other hand, the mean ergodic theorem is more complicated than Burnside's lemma, so this may not qualify as an intuitive explanation.

Nevertheless: given a measure-preserving action of an amenable group $G$ on a space $X$, the mean ergodic theorem tells us that

$${\bf E}_{g \in G} \langle T_g f, f \rangle_{L^2(X)} = \| \pi(f) \|_{L^2(X)}^2,$$

where $\pi(f)$ is the orthogonal projection of $f$ to the $G$-invariant functions, and $T_g f(x) := f(g^{-1} x)$, and ${\bf E}_{g \in G}$ is a mean on $G$.

If one applies this to the one-sided action $g: (x,y) \to (gx,y)$ on the product space $X \times X$ equipped with counting measure, with $f$ equal to the Kronecker delta function $f(x,y) = \delta_{x,y}$, $\pi(f)$ is equal to $1/|O|$ on the square $O \times O$ of each orbit $O$, and so one obtains

$${\bf E}_{g \in G} |X^g| = |X/G|$$

which is Burnside's lemma.

-
Thanks! This is really an amazing interpretation, though I'm afraid I don't have the knowledge necessary to fully grasp the proof. However, I was wondering to what extent this lets us make sense of Burnside's Lemma when there are infinitely many orbits / there is at least one element of the group with infinitely many fixed points, by using a measure other than the counting measure? It would be really neat if there were seemingly unrelated theorems, say in analysis, that are actually special cases of this version of Burnside's Lemma. – Zev Chonoles Dec 27 '10 at 5:22

Some thoughts. $X$ defines a representation $V = \mathbb{C}^X$ of $G$ with character $\chi(g) = \text{Fix}(g)$, and the projection from $V$ to its invariant subspace is $\frac{1}{|G|} \sum_{g \in G} g$, so the trace of the projection (which is the dimension of its image) is $\frac{1}{|G|} \sum_{g \in G} \chi(g)$. On the other hand, the invariant subspace of $\mathbb{C}^X$ is spanned by sums over orbits, so its dimension is the number of orbits. Phrased this way Burnside's lemma can be thought of as a "trace formula" relating a "geometric" quantity (the number of orbits) to a "spectral" quantity (the sum of fixed points). The value of other stronger results of this kind is precisely that the objects on both sides are not of the same kind, so perhaps it's not natural to expect them to be any more closely related than that.

(I tried a categorification in $G\text{-Set}$ but it didn't lead anywhere interesting.)

-
Thanks for taking the time to think about it; I'm perfectly happy with the two sides being fundamentally different, especially since (as you point out) that is the exactly what makes this and many other theorems so valuable. – Zev Chonoles Dec 21 '10 at 6:41
Yeah, my intuition here is that these are two different bases for the same space but there's no canonical identification between them. On the other hand, as John Baez is fond of pointing out, you can often replace Vec categorifications with Set categorifications if you allow spans as morphisms. Then you end up with exactly Jose's answer. – Noah Snyder Dec 21 '10 at 6:50

I saw a discussion of this lemma in a combinatorics article just very recently. It goes along lines like this: We want to count orbits of X under the action of G. We don't know how to pick representatives of each orbit, so let's just count all of them (thus relating this to your other question?), appropriately discounted. So, $$|X/G| = \sum_{x \in X} \frac{1}{|Gx|}$$ where $Gx$ is the orbit of $x \in X$ under the action of G. An application of the orbit-stabiliser theorem yields $$|X/G| = \frac{1}{|G|} \sum_{x \in X} |G_x|$$ and then the usual formula follows by recognising that the sum is nothing more than the cardinality of the set $\{ (g, x) \in G \times X : g \cdot x = x \}$ (Z in the notation of José's post).

I suppose the natural (pun intended) question to ask is whether there's a natural bijection between the $G \times X/G$ and the disjoint union $Z = \displaystyle \coprod_{g \in G} X^g$. If there is one, it's not immediately obvious to me... I suspect there isn't, simply because $G \times X/G$ is a disjoint union over G of sets of the same size, whereas $Z$ is a disjoint union over G of sets of different sizes.

-