Intuitive explanation of Burnside's Lemma - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-20T05:29:48Z http://mathoverflow.net/feeds/question/50033 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/50033/intuitive-explanation-of-burnsides-lemma Intuitive explanation of Burnside's Lemma Zev Chonoles 2010-12-21T05:42:22Z 2010-12-21T07:36:06Z <p>Burnside's Lemma states that, given a set $X$ acted on by a group $G$, </p> <p>$$|X/G|=\frac{1}{|G|}\sum_{g\in G}|X^g|$$</p> <p>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$.</p> <p>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 <a href="http://mathoverflow.net/questions/50025/problems-where-we-cant-make-a-canonical-choice-solved-by-looking-at-all-choices" rel="nofollow">here</a> 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.</p> <p>"number of orbits = average over $g\in G$ of (number of orbits satisfying (something to do with $g$))"</p> <p>or </p> <p>"number of orbits = average over $g\in G$ of (number of orbits of some new action which depends on $g$)"</p> <p>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.</p> http://mathoverflow.net/questions/50033/intuitive-explanation-of-burnsides-lemma/50036#50036 Answer by JosÃ© Figueroa-O'Farrill for Intuitive explanation of Burnside's Lemma JosÃ© Figueroa-O'Farrill 2010-12-21T06:21:48Z 2010-12-21T06:21:48Z <p>I'm not sure I'd call this a categorification, but the way I think of Burnside's Lemma is as follows.</p> <p>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$.</p> <p>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.</p> http://mathoverflow.net/questions/50033/intuitive-explanation-of-burnsides-lemma/50037#50037 Answer by Qiaochu Yuan for Intuitive explanation of Burnside's Lemma Qiaochu Yuan 2010-12-21T06:27:18Z 2010-12-21T06:27:18Z <p>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 <em>not</em> of the same kind, so perhaps it's not natural to expect them to be any more closely related than that.</p> <p>(I tried a categorification in $G\text{-Set}$ but it didn't lead anywhere interesting.)</p> http://mathoverflow.net/questions/50033/intuitive-explanation-of-burnsides-lemma/50039#50039 Answer by Terry Tao for Intuitive explanation of Burnside's Lemma Terry Tao 2010-12-21T07:08:32Z 2010-12-21T07:08:32Z <p>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.</p> <p>Nevertheless: given a measure-preserving action of an amenable group $G$ on a space $X$, the mean ergodic theorem tells us that</p> <p>$${\bf E}_{g \in G} \langle T_g f, f \rangle_{L^2(X)} = \| \pi(f) \|_{L^2(X)}^2,$$</p> <p>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$.</p> <p>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</p> <p>$${\bf E}_{g \in G} |X^g| = |X/G|$$</p> <p>which is Burnside's lemma.</p> http://mathoverflow.net/questions/50033/intuitive-explanation-of-burnsides-lemma/50041#50041 Answer by Zhen Lin for Intuitive explanation of Burnside's Lemma Zhen Lin 2010-12-21T07:36:06Z 2010-12-21T07:36:06Z <p>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 <code>$\{ (g, x) \in G \times X : g \cdot x = x \}$</code> (Z in the notation of José's post).</p> <p>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.</p>