1
$\begingroup$

Since I didn't feel confident about the subject as read so far, I've tried to deploy it somehow. This way I can go as far as the OST (Corollary 2), but I am stuck with the proof in Lemma 3, which is necessary to get to Burnside's Lemma (Corollary 3).

Could someone give me a hint how to prove the Lemma 3, please?


Driven by the "prototypical action" on a set, namely a permutation of its elements, we define action of the group $G$ on the set $S$ the map:

\begin{alignat*}{1} G \times S &\longrightarrow& S \\ (g,s)&\longmapsto& gs \end{alignat*}

with the following properties:

  1. $es=s, \forall s \in S$;
  2. $g(hs)=(gh)s, \forall g,h \in G, \forall s \in S$.

Given $s,t \in S$, we say:

$$t \stackrel{\cdot}{\sim}s \stackrel{(def.)}{\Longleftrightarrow} \exists g \in G \mid t=gs \tag 1$$

By virtue of action's properties, $\stackrel{\cdot}{\sim}$ turns out to be an equivalence relation on $S$. In fact:

  • $s \stackrel{\cdot}{\sim} s$, because $s=es$;
  • $t\stackrel{\cdot}{\sim}s \Rightarrow t=gs \Rightarrow g^{-1}t=g^{-1}(gs)=(g^{-1}g)s=es=s \Rightarrow s\stackrel{\cdot}{\sim}t$;
  • $(t\stackrel{\cdot}{\sim}s) \wedge (s\stackrel{\cdot}{\sim}r) \Rightarrow (t=gs) \wedge (s=hr) \Rightarrow t=g(hr)=(gh)(r) \Rightarrow t\stackrel{\cdot}{\sim}r$.

Thence, $S$ is partitioned into orbits:

$$\mathcal{O}:=S/\stackrel{\cdot}{\sim}=\lbrace O(s), s \in S\rbrace \tag 2$$

where

$$O(s):=[s]_{\stackrel{\cdot}{\sim}}=\lbrace t \in S \mid t\stackrel{\cdot}{\sim}s\rbrace=\lbrace t \in S \mid t=gs, g \in G \rbrace \tag 3$$

Given $s \in S$, distinct group's elements may "move" $s$ to one same element of $S$, and we say:

$$h\stackrel{s}{\sim}g \stackrel{(def.)}{\Longleftrightarrow} hs=gs \tag 4$$

$\stackrel{s}{\sim}$ is an equivalence relation on $G$; in fact:

  • $g\stackrel{s}{\sim}g$, because $gs=gs$;
  • $h\stackrel{s}{\sim}g \Rightarrow hs=gs \Rightarrow gs=hs \Rightarrow g\stackrel{s}{\sim}h$;
  • $(h\stackrel{s}{\sim}g) \wedge (g\stackrel{s}{\sim}k) \Rightarrow (hs=gs) \wedge (gs=ks) \Rightarrow hs=ks \Rightarrow h\stackrel{s}{\sim}k$.

Thence, given $s \in S$, $G$ is partitioned into stabilizers:

$$\mathcal{S}_s:=G/\stackrel{s}{\sim}=\lbrace \mathcal{Stab}_s(g), g \in G\rbrace \tag 5$$

where

$$\mathcal{Stab}_s(g):=[g]_{\stackrel{s}{\sim}}=\lbrace h \in G \mid h\stackrel{s}{\sim}g\rbrace=\lbrace h \in G \mid hs=gs\rbrace \tag 6$$


Lemma 1. The map:

\begin{alignat*}{1} \chi \colon \mathcal{S}_s &\longrightarrow& O(s) \\ \mathcal{Stab}_s(g) &\longmapsto& \chi(\mathcal{Stab}_s(g)):=gs \tag 7 \end{alignat*}

is well-defined and bijective.

Proof.

  • Let $h \in \mathcal{Stab}_s(g)$; then, $\chi(\mathcal{Stab}_s(h))=hs=gs=\chi(\mathcal{Stab}_s(g))$, and $\chi$ is well-defined.
  • $\chi(\mathcal{Stab}_s(h))=\chi(\mathcal{Stab}_s(g)) \Rightarrow hs=gs \Rightarrow h \in \mathcal{Stab}_s(g)$; but $h \in \mathcal{Stab}_s(h)$, then $\mathcal{Stab}_s(h)=\mathcal{Stab}_s(g)$, and $\chi$ is 1-1.
  • By definition of $O(s)$, $\forall t \in O(s), \exists g \in G$ such that $t=gs=\chi(\mathcal{Stab}_s(g))$, and $\chi$ is onto. $\Box$

Lemma 2. $\forall g,h \in G$, the map:

\begin{alignat*}{1} \xi \colon \mathcal{Stab}_s(g) &\longrightarrow& \mathcal{Stab}_s(h) \\ k &\longmapsto& \xi(k) :=hk^{-1}g \tag 8 \end{alignat*}

is bijective.

Proof. Firstly, $\forall k \in \mathcal{Stab}_s(g)$, it is $\xi(k) \in \mathcal{Stab}_s(h) \Leftrightarrow (hk^{-1}g)s=hs$, and this latter holds because $(hk^{-1}g)s=h(k^{-1}(gs))=h(k^{-1}(ks))=h((k^{-1}k)s)=h(es)=hs$. Besides, $\xi(k)=\xi(u)\Rightarrow k=u$, by group properties, and $\xi$ is 1-1. Finally, $\forall v \in \mathcal{Stab}_s(h)$, $v=\xi(gv^{-1}h)$, and $\xi$ is onto. $\Box$

Corollary 1. (Here $|X|$ stands for the cardinality of $X$.) $\forall g \in G$:

$$|\mathcal{Stab}_s(g)|=|\mathcal{Fix}(s)| \tag 9$$

where:

$$\mathcal{Fix}(s):=\lbrace h \in G \mid hs=s\rbrace \tag {10}$$

Proof. By the Lemma 2, $\forall g \in G, |\mathcal{Stab}_s(g)|=|\mathcal{Stab}_s(e)|$, and $\mathcal{Stab}_s(e)$ is precisely $\mathcal{Fix}(s)$. $\Box$

Corollary 2. (Orbit-Stabilizer Theorem.) If $G$ is finite, then:

$$|\mathcal{Fix}(s)||O(s)|=|G|, \forall s \in S \tag {11}$$

Proof. Given $s \in S$, $G$ is partitioned into $|O(s)|$ subsets (by Lemma 1) of $|\mathcal{Fix}(s)|$ elements each (by Corollary 1). $\Box$

For any $g \in G$, we call:

$$\operatorname{Fix}(g):=\lbrace s \in S \mid gs=s \rbrace \tag {12}$$

(EDIT on the basis of the accepted answer and therein comments.)

Lemma 3. If $G$ and $S$ are finite, then:

$$\sum_{g \in G}|\operatorname{Fix}(g)|=\sum_{s \in S}|\mathcal{Fix}(s)| \tag {13}$$

Proof. By $(10)$ and $(12)$:

$$\lbrace \mathcal{Fix}(s) \times \lbrace s \rbrace, s \in S \rbrace = \lbrace (g,s) \in G \times S \mid gs=s \rbrace = \lbrace \lbrace g \rbrace \times \operatorname{Fix}(g), g \in G \rbrace$$

from which $(13)$ follows for $G$ and $S$ finite. $\Box$

Corollary 3. (Burnside's Lemma.) If $G$ and $S$ are finite, then:

$$|\mathcal{O}|=\frac{1}{|G|}\sum_{g \in G}|\operatorname{Fix}(g)| \tag {14}$$

Proof. By $(2)$ and $(11)$:

\begin{alignat}{1} \sum_{s \in S}|\mathcal{Fix}(s)| &= \sum_{O(s) \in \mathcal{O}}\sum_{t \in O(s)}|\mathcal{Fix}(s)| \\ &= \sum_{O(s) \in \mathcal{O}}|\mathcal{Fix}(s)|\sum_{t \in O(s)}1 \\ &= \sum_{O(s) \in \mathcal{O}}|\mathcal{Fix}(s)||O(s)| \\ &= \sum_{O(s) \in \mathcal{O}}|G| \\ &= |G|\sum_{O(s) \in \mathcal{O}}1 \\ &= |G||\mathcal{O}| \tag {15} \end{alignat}

and $(14)$ follows from the Lemma 3. $\Box$

enter image description here

$\endgroup$
2
$\begingroup$

Lemma 3 is the following observation.

Let $[P]$ be the Iverson bracket of $P$, i.e., it is $1$ if $P$ is true, and $0$ if $P$ is false, where $P$ is a statement.

Then observe that $$|\operatorname{Fix}(g)|=\sum_{s\in S} [gs=s],$$ and that $$|\mathcal{Fix}(s)| = \sum_{g\in G} [gs=s].$$

Thus we have $$\sum_{g\in G}|\operatorname{Fix}(g)|=\sum_{g\in G}\sum_{s\in S} [gs=s] = \sum_{s\in S}|\mathcal{Fix}(s)|$$

$\endgroup$
  • $\begingroup$ +1. Didn't know there was a notation and a name for this $[P]$ ! (I usually just use $\mathbb{1}$ for indicator functions, as this is essentially what the bracket does) $\endgroup$ – Max May 30 '19 at 14:44
  • 1
    $\begingroup$ Maybe I got your point: think of a set $A$ as a subset of a "universe-set" $U$, namely $A=\lbrace u \in U \mid P_A(u) \rbrace$, where $P_A$ is the characteristic property of $A$; now, if $U$ is finite, we get: $|A|=\sum_{u \in U}[P_A(u)]$. In our case, the two "Fix" sets belong to two different (finite) "universes" ($G$ and $S$) but share the same characteristic property. Is it so? $\endgroup$ – Luca May 30 '19 at 16:30
  • $\begingroup$ Not "belong to", I meant "are contained into". $\endgroup$ – Luca May 30 '19 at 16:37
  • 1
    $\begingroup$ @Luca I think your comment is essentially the idea yes. While the two fix sets are subsets of $G$ and $S$, since each of the fix sets are functions of a parameter from the other set, it might be more productive to think of them as being two different views of a single $g \text{ fix } s$ relation on $G\times S$, where we say $g\text{ fix } s$ if and only if $gs = s$. If you're familiar with probability, the fix sets are like integrating out one of the variables to obtain the marginal distribution on the other. $\endgroup$ – jgon May 30 '19 at 17:00
  • $\begingroup$ The equality we want is then like saying that if we integrate out both variables, we get the same thing. $\endgroup$ – jgon May 30 '19 at 17:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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