## § 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)|$
• We replace cardinality with weight, giving us the statement:
\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.

#### § Proof

• 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)$.
• The full derivation is:
\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}

#### § Example, Unweighted

• 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