# Abstract Algebra questions related to Burnside's Lemma

I am trying to understand these two derivations in class.

Here $g \in G$ and $x \in S$.

$\displaystyle\sum_{x \in S} |G_x| = \sum_{\text{orbits} \hspace{ 1mm} Gx} \hspace{ 1mm} \sum_{y \in Gx} |G_y| = \sum_{\text{orbits} \hspace{ 1mm} Gx} |Gx| |G_x| = \sum_{\text{orbits} \hspace{1mm} Gx} |G| = |S/G||G|$

What I mainly don't understand is the double summation as in how: $\displaystyle\sum_{\text{orbits} \hspace{ 1mm} Gx} \hspace{ 1mm} \sum_{y \in Gx} |G_y| = \sum_{\text{orbits} \hspace{1 mm} Gx} |Gx| |G_x|$

My other question is how do we know that $\displaystyle\sum_{y \in Gx} 1 = |Gx|$

-

To take the second question first: the sum $\sum\limits_{y\in Gx}1$ has one term for every $y\in Gx$, and each of those terms is $1$, so it’s just adding $|Gx|$ copies of the number $1$; the result, of course, is $|Gx|$. If you want to make that even more explicit, let $m=|Gx|$ and enumerate the elements of $Gx$ as $y_1,\dots,y_m$. For each $y\in Gx$ let $f(y)=1$. Then $$\sum_{y\in Gx}1=\sum_{y\in Gx}f(y)=\sum_{k=1}^mf(y_k)=\sum_{k=1}^m 1=m\cdot1=m=|Gx|\;.$$

Now let’s look at the first question. You’re starting with $$\sum_{\text{orbits} \hspace{ 1mm} Gx} \hspace{ 1mm} \sum_{y \in Gx} |G_y|\;.\tag{1}$$ I think that this might be clearer if we gave a name to the set of orbits: let $\Omega$ be the set of orbits. Then $(1)$ can be rewritten as $$\sum_{\omega\in\Omega}~\sum_{y\in\omega}|G_y|\;.\tag{2}$$ The next thing to realize is that if $x$ and $y$ are in the same orbit, then $|G_x|=|G_y|$.

Proof: If $x$ and $y$ are in the same orbit, then $y=gx$ for some $g\in G$. Then $h\in G_y$ iff $hy=y$ iff $hgx=gx$ iff $g^{-1}hgx=x$ iff $g^{-1}hg\in G_x$, and the map $h\mapsto g^{-1}hg$ is a bijection. $\dashv$

Thus, for any orbit $\omega\in\Omega$ there is a number $n(\omega)$ such that $|G_x|=n(\omega)$ for each $x\in\omega$. Thus, $(2)$ can be rewritten as $$\sum_{\omega\in\Omega}~\sum_{y\in\omega}n(\omega)=\sum_{\omega\in\Omega}|\omega|\,n(\omega)\;,\tag{3}$$ since the inner sum on the lefthand side is just adding up $|\omega|$ copies of the number $n(\omega)$.

We could now pick out a particular element $x_\omega$ of each orbit $\omega$ use these elements to identify the orbits. If we do this, $(3)$ becomes

$$\sum_{\omega\in\Omega}|Gx_\omega||\omega|=\sum_{\omega\in\Omega}|Gx_\omega||G_{x_\omega}|\;,$$

which is just a slightly more careful way of writing

$$\sum_{\text{orbits}} |Gx| |G_x|\;.$$

-