# Group actions, the Orbit-Stabilizer Theorem and Burnside's Lemma.

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}$$

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$$

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)|$$

• +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) – Max May 30 '19 at 14:44
• 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? – Luca May 30 '19 at 16:30
• Not "belong to", I meant "are contained into". – Luca May 30 '19 at 16:37
• @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. – jgon May 30 '19 at 17:00
• The equality we want is then like saying that if we integrate out both variables, we get the same thing. – jgon May 30 '19 at 17:00