Mfcttrf

I studied group theory a long time ago. Back then, I didn't understand how to use the group theory-specific idioms to write short proofs. I still don't.

Below is a proof of Burnside's Lemma using as little group theory as possible, by which I mean it uses few commonly-known lemmas. The basic thrust of the argument is showing that both sides count the number of fixed points of $varphi(g)$ for each $g$ in the group $G$ .

What are some good ways of proving Burnside's lemma without spending much ink and idiomatically using other results that are "more basic" than Burnside's Lemma?

I'm attaching below my proof of the lemma. I looked at Wikipedia to get the statement of the theorem, but did not read the proof section until I completed the proof.

Proof of Burnside's lemma.

First a word on notation.

The notation $[psi]$ for a proposition $psi$ is $1$ if the expression is true and $0$ if the expression is false. It is called an Iverson bracket.

A group $G$ acts on a set $X$ . Equivalently, there exists a function $varphi : G to (X to X) $ that sends each $g$ to a function from $X$ to itself. $varphi$ is not required to be injective. $varphi$ is not completely arbitrary; it satisfies some laws that I won't enumerate here.

Let $langle g, x rangle$ denote the group action.

$$ langle g,x rangle stackrelmathrmdef= (, varphi(g),)(x) $$

Let $G(x)$ denote the orbit of $x$ in $G$ .

$$ G(x) stackrelmathrmdef= g in G ; $$

Let $simeq_G$ be a binary predicate that is true if and only if there exists a $g$ that sends the left argument to the right argument.

$$ x simeq_G y stackrelmathrmdefiff left(exists g in G mathop. langle g, x rangle = y right) $$

Note that

$$ x simeq_G y iff x in G(y) $$

and

$$ x simeq_G y iff y in G(x) $$

Let's show that the negation of Burnside's Lemma is absurd.

$$ |X/G|cdot|G| ne sum_g in G |X^g| $$

$$ |X/G|cdot|G| ne sum_g in G left|left langle g, x rangle = x rightright| $$

$$ |X/G|cdot|G| ne sum_g in Gsum_x in X [langle g, x rangle = x ] $$

$$ |G|cdot|X/G| ne sum_g in Gsum_x in X [langle g, x rangle = x ] $$

$$ |G|cdotsum_x in X frac1G(x) ne sum_g in Gsum_x in X [langle g, x rangle = x ] $$

$$ |G|cdotsum_x in X frac1G(x) ne sum_g in Gsum_x in Xsum_y in X [langle g, x rangle = y ][ x = y ] $$

If we relax the restriction that $x = y$ and insist instead that $x simeq_G y$, then we can count each $x$ at $frac1G(x) = frac1$ value.

$$ |G|cdotsum_x in X frac1G(x) ne sum_g in Gsum_x in Xsum_y in X [langle g, x rangle = y ]cdotfrac[x simeq_G y]G(x) $$

However, the condition $x simeq_G y$ is redundant if we already know that $langle g, x rangle = y$ for some particular $g in G$ .

$$ |G|cdotsum_x in X frac1G(x) ne sum_g in Gsum_x in Xsum_y in X [langle g, x rangle = y ]cdotfrac1G(x) $$

$$ sum_x in X |G| cdot frac1G(x) ne sum_g in Gsum_x in Xsum_y in X [langle g, x rangle = y ]cdotfrac1G(x) $$

Replace $|G|$ with a sum counting $1$ for each item in $G$.

$$ sum_x in X left( sum_g in G 1 right) cdot frac1G(x) ne sum_g in Gsum_x in Xsum_y in X [langle g, x rangle = y ]cdotfrac1G(x) $$

The group element $g$ acting on the set $X$ sends a particular $x in X$ to exactly one destination.

$$ sum_x in X left( sum_g in G sum_y in X [langle g, x rangle = y] right) cdot frac1G(x) ne sum_g in Gsum_x in Xsum_y in X [langle g, x rangle = y ]cdotfrac1G(x) $$

$$ sum_x in X sum_g in G sum_y in X [langle g, x rangle = y] cdot frac1G(x) ne sum_g in Gsum_x in Xsum_y in X [langle g, x rangle = y ]cdotfrac1G(x) $$

All sub-expressions are positive, we can reorder.

$$ sum_g in G sum_x in X sum_y in X [langle g, x rangle = y] cdot frac1G(x) ne sum_g in Gsum_x in Xsum_y in X [langle g, x rangle = y ]cdotfrac1G(x) $$

$$ bot $$

Therefore $ | X/ G | cdot |G| = sum_g in G |X^g| $ as desired.

Hint:

Prescribe function $chi:Gtimes Xto mathbb0,1$ by stating that: $$chi(g,x)=1iff gx=x$$ Then automatically $chi(g,x)=0$ if $gxneq x$.

Then the theorem of Burnside will show up if we work out the equality:$$frac1sum_gin Gsum_xin Xchi(g,x)=frac1sum_xin Xsum_gin Gchi(g,x)$$

Give it a try.

edit:

Essential for working out the RHS is the following observation.

If $mathcalP$ denotes a partition of finite set $X$ and for every
$x$ the $PinmathcalP$ with $xin P$ is denoted as $left[xright]$
then: $$sum_xin Xfrac1left[xright]=sum_pinmathcalPsum_xin Pfrac1left[xright]=sum_pinmathcalP1=left|mathcalPright|$$