# Q on a proof of Burnside's Lemma

A proof of Burnside's lemma first claims the number of equivalence classes on G, the given set of permutations, $\sigma$'s, to be applied to an object (i.e. a beaded necklace to be colored), is equal to

$\sum_{k\in K}\frac{1}{|O_k|}$. (1)

$k$ is a certain coloring of the object (e.g. a 4-bead necklace with k=bbww means first two are black and last two are white) in the set $K$ of all colorings, and $O_k$ is the orbit set of that $k$.

From here, the proof lets $O_{k_m}=\{k_1, k_2, ...,k_m\}$ for some $k_m$. (2)

$\Rightarrow|O_{k_m}|=m$ ($m$ is the number of 'colors' available; $C=\{$white$,$ black$\}$, $m=2$).

$\Rightarrow O_{k_1}=O_{k_2}=...=O_{k_m}$. (3)

The proof goes on to show that the presented Burnside's Lemma, $\frac{1}{|G|}\sum_{\sigma\in G}|$Inv$(\sigma)|=\sum_{k\in K}\frac{1}{|O_k|}$, where Inv($\sigma$) is the invariant set of $\sigma$.

My questions are about (1),(2),(3):

How was (1) claimed right off the bat? Is there an intuitive reason?

(2) seems to imply that there is a coloring $k_m$ that can become any other coloring via some $\sigma$. Wouldn't this mean that there is only one equivalence class? (3) seems to show this as well. Clearly, there are situations where there is more than one equivalence class..

I don't understand how they are claiming these crucial steps for the proof.

EDIT: Original can be found next to 'download' near the top at http://ntnu.diva-portal.org/smash/record.jsf?pid=diva2:348745. Proof is on page 12 of the pdf.

-

## 1 Answer

Let $|X^g|= \{x \in X \mid g(x) = x \}$ . If you look at $Y:= \{(g,x) \in G \times X \mid g(x) = x \}$ then first $|Y| = \sum_{g \in G} |X^g|$ and $|Y| = \sum_{x \in X} |G_x| = \sum_{x \in X} \frac{|G|}{|G(x)|}$ Because the orbits are a partition of X let $$X = \bigcup_{i =1}^r X_i = \bigcup_{i=1}^r G(x_i)$$ for representatns $x_i \in X_i$. Then we have $$|Y| = \sum_{x \in X} \frac{|G|}{|G(x)|} = \sum_{i=1}^r \sum_{x\in X_i} \frac{|G|}{|G(x_i)|} = \sum_{i=1}^r |X_i| \frac{|G|}{|X_i|} = r|G|$$ and thus $$r|G| = \sum_{g\in G}|X^g|\rightarrow r = \frac 1 {|G|} \sum_{g \in G} |X|^g$$ where $r$ is the number of orbits. I hope this is a bit clearer.

-
Is G(x) the orbit set of x? And is r analog of my m? Sorry, I am pretty new to this stuff.. –  James Oct 25 '12 at 19:33
I am not sure about the $m$ eventhough i read the proof. But what he says in (1) is : number of orbits $= r = \sum_{k \in K} \frac 1 {|O_k|}$ but $\frac 1 {|O_k|} = \frac{|G|}{|G_k|}$ so that (1) is $$\frac{1}{|G|} \sum_{k \in K} |G_k| = \frac 1 {|G|} \sum_{g \in G } |K^g|$$ where $G_k$ the sabilizer is. There you see why these are equivalent. –  Andre Oct 25 '12 at 21:06