Intuitive explanation of Burnside's Lemma - MathOverflow

Intuitive explanation of Burnside's Lemma

2010-12-21T05:42:22Z

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$))"

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

Answer by José Figueroa-O'Farrill for Intuitive explanation of Burnside's Lemma

2010-12-21T06:21:48Z

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.

Answer by Qiaochu Yuan for Intuitive explanation of Burnside's Lemma

2010-12-21T06:27:18Z

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

Answer by Terry Tao for Intuitive explanation of Burnside's Lemma

2010-12-21T07:08:32Z

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.

Answer by Zhen Lin for Intuitive explanation of Burnside's Lemma

2010-12-21T07:36:06Z

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.