A Universe of Sorts

§ Weighted Burnside Lemma

I'm learning the weighted burnside lemma as a preamble to polya enumeration.
Define for a set $X$ with a group action $G$ , a weight function on the orbits $O$ . Said differently, we have a weight function $w: X \to W$ such that $w(x) = w(g(x))$ for all $x \in X$ and $g \in G$ .
We wish to count the orbits of $X$ weighted by the weight function $w: X \to W$ (where $W$ is a commutative ring). So we wish to find $\sum_{o \in Orb(X)} w(o)$ .
Recall that Burnside tells us that:

|X/G| = \sum_{g \in G} |Fix(g)|

\begin{aligned} &w(X/G) = 1/|G| (\sum_{g \in G} w(Fix(g))) \\ &=\sum_{[o] \in X/G} w(o) = 1/|G| (\sum_{g \in G} \sum_{x \in Fix(g)} w(x) ) \end{aligned}

In english, this reads: for each orbit in $X/G$ , pick an equivalence class representative $o$ . The sum of weights of the representatives equals the average over $G$ of the fixpoint-weights.

We begin by considering the LHS:
$y = \sum_{g \in G} \sum_{x \in Fix(g)} w(x)$ .
We switch the order of summation to get $y = \sum_{x \in X} \sum_{g \in G} [gx = x] w(x)$ where $[gx = x]$ is the Iverson bracket --- it evaluates to 1 if $gx = x$ and $0$ if $gx \neq x$ .
We pull the constant $w(x)$ out to get $y = \sum_{x \in X} w(x) (\sum_{g \in G} [gx = x])$ .
We see that $\sum_{g \in G} [gx = x]$ is the cardinality of the stabilizer of $x$ , written as $|Stab(G, x)|$ . So we write this as $y = \sum_{x \in X} |Stab(G, x)| w(x)$ .
By orbit stabilizer, we use $|Stab(G, x)| \cdot |Orb(G, x)| = |G|$ . Thus, we get $y = |G| \sum_{x \in X} w(x) / |Orb(G, x)|$ .
Since the set of orbits partitions $X$ , we write the above as
$y = |G| \sum_{[o] \in G/X} \sum_{x \in [o]} w(x)/|Orb(G, x)|$ .
Since $[o]$ is the orbit of $x$ , we replace $Orb(G, x)$ with $o$ , giving $y = |G| \sum_{[o] \in G/X} \sum_{x \in [o]} w(x)/|[o]|$ .
Since the weight is constant on orbits, we replace $w(x)$ by $w(o)$ giving $y = |G| \sum_{[o] \in G/X} \sum_{x \in [o]} w(o)/|[o]|$ .
We pull the inner terms out giving $y = |G| \sum_{[o] \in X/G} w(o)/|[o]| \sum_{x \in [o]} 1$ .
Since $\sum_{x \in [o]} 1 = |o|$ , we get $|G| \sum_{[o] \in X/G} w(o)/|[o]| |[o]|$ which simplies to $y = |G| \sum_{[o] \in X/G} w(o)$ .
We are done, since we have shown that $\sum_{g \in G} \sum_{x \in Fix(g)} w(x) = |G| \sum_{[o] \in X/G} w(o)$ .

\begin{aligned} &y = \sum_{g \in G} \sum_{x \in Fix(g)} w(x) \\ &= \sum_{g \in G} \sum_{x \in X} [gx = x] w(x) \\ &= \sum_{x \in X} \sum_{g \in G} [gx = x] w(x) \\ &= \sum_{x \in X} w(x) \sum_{g \in G} [gx = x] \\ &= \sum_{x \in X} w(x) Stab(x) \\ &= \sum_{x \in X} w(x) |G|/|Orb(G, x) \\ &=|G| \sum_{x \in X} w(x)/|Orb(G, x) \\ &=|G| \sum_{[o] \in X/G} \sum_{x \in O} w(x) / |Orb(G, x)| \\ &=|G| \sum_{[o] \in X/G} \sum_{x \in O} w(o) / |Orb(G, x)| \\ &=|G| \sum_{[o] \in X/G} \sum_{x \in O} w(o) / |o| \\ &=|G| \sum_{[o] \in X/G} w(o) / |o| \sum_{x \in O} 1 \\ &=|G| \sum_{[o] \in X/G} w(o) / |o| \cdot |o| \\ &=|G| \sum_{[o] \in X/G} w(o)\\ \end{aligned}

Suppose we squares acted on by rotations $e, r, r^2, r^3$ . It takes the square:

a b
c d

to the squares:

e     r     r^2   r^3
----|-----|-----|-----
1 2 | 4 1 | 4 2 | 4 3
3 4 | 3 2 | 3 1 | 1 2