29
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ It seems to me that the answers so far ignore the actual question. It's not about a proof of Burnside's lemma. $\endgroup$ Dec 21, 2010 at 9:10
  • 1
    $\begingroup$ @Martin: my answer to the actual question is "no," and to support that position I needed to introduce a proof. $\endgroup$ Dec 21, 2010 at 9:38
  • $\begingroup$ @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. $\endgroup$ Dec 21, 2010 at 18:08
  • 1
    $\begingroup$ Somehow related : these notes by Tom Leinster : maths.ed.ac.uk/~tl/whitepoint/euler.pdf that suggest there may be a categorification (for instance in these notes he explains how $|S/M| = |S|/|M|$ for a free action is a consequence of some categorical stuff). Since you mentioned categorification, I'm mentioning them $\endgroup$ Aug 1, 2018 at 15:01
  • 1
    $\begingroup$ This question mathoverflow.net/questions/382630/… and answers to it discuss a formula for the Euler characteristic of an orbit space that categorifies Burnside's lemma. $\endgroup$ Jan 31, 2021 at 6:43

4 Answers 4

45
$\begingroup$

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.

Thanks to @Arrow who pointed out the link in my comment was broken. Here's hopefully a link that works to the same one-page document.

$\endgroup$
4
  • 1
    $\begingroup$ Here's a 1-page PDF document with the details of my answer: dl.dropbox.com/u/5096148/Polya.pdf $\endgroup$ Dec 21, 2010 at 6:25
  • $\begingroup$ Dear José, the link in your comment is broken. $\endgroup$
    – Arrow
    Aug 1, 2018 at 13:48
  • $\begingroup$ @Arrow Thanks for letting me know. I am not sure what happened. It's still in the Dropbox. I'll obtain a new link and edit. $\endgroup$ Aug 1, 2018 at 13:54
  • $\begingroup$ I read your answer as follows, which I miss to see why it actually answers the OP:\begin{alignat}{1} |X/G| &= \frac{1}{|G|}\sum_{g\in G}|X^g| \\ &= \frac{1}{|G|}\sum_{x\in X}|G_x| \\ &= \frac{1}{|G|}\sum_{x\in X}\frac{|G|}{|O_x|} \\ &= \sum_{x\in X}\frac{1}{|O_x|} \\ \end{alignat} $\endgroup$
    – citadel
    Feb 16, 2023 at 22:27
41
$\begingroup$

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.

$\endgroup$
1
  • 2
    $\begingroup$ 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. $\endgroup$ Dec 27, 2010 at 5:22
19
$\begingroup$

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.)

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ Dec 21, 2010 at 6:41
  • 6
    $\begingroup$ 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. $\endgroup$ Dec 21, 2010 at 6:50
6
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.