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.

Burnsides theorem

If $G$ has $t$ orbits on $\Omega$, then $t=\frac{1}{|G|} \sum_{g \in G} |\operatorname{fix}_{\Omega} (g)|$

It seems to be done by counting in two ways , then saying that the $G$-orbits $\Omega= \Delta_{1} \cup \Delta_{2} \cup\cdots \cup \Delta_{t}$.

However, don't see you can concludes for $g \in G$, $\operatorname{fix}_{\Omega}(g)=\operatorname{fix}_{\Delta_1} \cup \cdots \cup \operatorname{fix}_{\Delta_{t}}(g)$.

I just don't see what $\operatorname{fix}_{\Omega}(g)$ is doing. Can you please help me understand this proof?

share|improve this question
    
Here's a nice (albeit wordless) proof: en.wikipedia.org/wiki/Burnside's_lemma#Proof, where your $\Omega=X$, your $t=|X/G|$, and $fix_\Omega(g)=X^g$. It's using the orbit-stabilizer theorem (en.wikipedia.org/wiki/Orbit-stabilizer_theorem) and counting the number of pairs $(g,x)\in G\times X$ for which $g(x)=x$. –  bgins Jan 20 '12 at 11:13
add comment

1 Answer

up vote 1 down vote accepted

I will summarize the main idea but leave you some details. Let me know if you'd like those details as well.

The idea is to count the pairs $(g,\omega)$ where $g\in G, \omega\in \Omega$, and $g\omega = \omega$, i.e. the pairs (group element, element of $\Omega$ fixed by this group element), in two different ways. $\mathrm{fix}_{\Omega}(g)$ is notation for the set of elements of $\Omega$ fixed by a particular group element $g$. Here are the two ways of counting involved in the proof:

Way number 1: sum over the elements of the set $\Omega$; organize these elements by orbit to clean up the sum.

When we fix $\omega\in \Omega$, the set of group elements fixing $\omega$ is $\omega$'s stabilizer. So the sum looks like

$$\sum_{\omega\in\Omega} \text{size of}\;\omega\text{'s stabilizer}$$

It is convenient to break this sum down into orbits:

$$\sum_{\omega\in\Delta_1}+\sum_{\omega\in\Delta_2}+\dots+\sum_{\omega\in\Delta_t}$$

When it is broken down this way, it becomes possible to conclude that the total is $t|G|$. Can you see why? This is the proof's key step. Also, it's the only point in the proof where the decomposition $\Omega=\Delta_1\cup\Delta_2\cup\dots\cup\Delta_t$ is used.

Way number 2: sum over the elements of the group.

Now the sum looks like

$$\sum_{g\in G} \text{number of elements of}\;\Omega\;\text{fixed by}\;g$$

But $\mathrm{fix}_{\Omega}(g)$ is just the name for the set of elements of $\Omega$ fixed by $g$, so this sum can be written

$$\sum_{g\in G}|\mathrm{fix}_{\Omega}(g)|$$

The proof can be completed from here.

Now it seems to me since you asked about it that it is actually true that $\mathrm{fix}_{\Omega}(g)=\mathrm{fix}_{\Delta_1}(g)\cup\dots\cup\mathrm{fix}_{\Delta_t}(g)$, because the left side is the set of all elements of $\Omega$ fixed by $g$, and the right side is the disjoint union of the set of elements fixed by $g$ that are in each individual orbit. But the proof I've outlined here doesn't make use of this.

share|improve this answer
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.