Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

1 Answer

up vote 0 down vote accepted

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.

share|improve this answer
    
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. –  André Oct 25 '12 at 21:06
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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