§ Clean way to write burnside lemma

Burnside lemma says that ∣Orb(G)∣≡1/∣G∣∑g∈Gfix(g)|Orb(G)| \equiv 1/|G| \sum_{g \in G} fix(g). We prove this as follows:
∑g∈Gfix(g)=∑g∈G∣{x:g(x)=x}∣=∣{(g,x):g(x)=x}∣=∑x∈X∣{x:g(x)=x}∣=∑x∈XStab(x) \begin{aligned} &\sum_{g \in G} fix(g) \\ &= \sum_{g \in G} |\{x : g(x) = x \}| \\ &= |\{(g, x) : g(x) = x \}| \\ &= \sum_{x \in X}|\{x : g(x) = x \}| \\ &= \sum_{x \in X} Stab(x) \end{aligned}
  • From orbit stabilizer, we know that ∣Orb(x)∣∣Stab(x)∣=∣G∣|Orb(x)||Stab(x)| = |G|.
  • Since ∣Orb(x)|Orb(x) is the total cardinality of the orbit, each element in the orbit contributes 1/∣Orb(x)∣1/|Orb(x)| towards cardinality of the full orbit.
  • Thus, the sum over an orbit ∑x∈Orb(x)1/∣Orb(x)∣\sum_{x \in Orb(x)} 1/|Orb(x)| will be 1.
  • Suppose a group action has two orbits, O1O_1 and O2O_2. I can write the sum ∑x∈g1/∣Orb(x)∣\sum_{x \in g} 1/|Orb(x)| as: ∑x∈O11/∣O1∣+∑x∈O21/∣O2∣\sum_{x \in O_1} 1/|O_1| + \sum_{x \in O_2} 1/|O_2|, which is equal to 2.
  • I can equally write the sum as ∑o∈Orbits∑x∈o1/∣o∣\sum_{o \in Orbits} \sum_{x \in o} 1/|o|. But this sum is equal to ∑o∈Orbits∑x∈o1/∣Orb(x)∣\sum_{o \in Orbits} \sum_{x \in o} 1/|Orb(x)|.
  • This sum sums over the entire group, so it can be written as ∑x∈G1/∣Orb(x)∣\sum_{x \in G} 1/|Orb(x)|.
  • In general, the sum over the entire group ∑x∈g1/∣Orb(x)∣\sum_{x \in g} 1/|Orb(x)| will be the number of orbits, since the same argument holds for each orbit .
=∑x∈XStab(x)=∑x∈X∣G∣/∣Orb(x)∣=∣G∣∑o∈orbits∑x∈o1/∣o∣=∣G∣num.orbits \begin{aligned} &= \sum_{x \in X} Stab(x) \\ &= \sum_{x \in X} |G|/|Orb(x)| \\ &= |G| \sum_{o \in orbits} \sum_{x \in o} 1/|o| \\ &= |G| \texttt{num.orbits} \\ \end{aligned}
So we have derived:
∑g∈Gfix(g)=∣G∣num.orbits1/∣G∣(∑g∈Gfix(g))=num.orbits \begin{aligned} &\sum_{g \in G} fix(g) = |G| \texttt{num.orbits} \\ &1/|G| (\sum_{g \in G} fix(g)) = \texttt{num.orbits} \\ \end{aligned}
If we have a transformation that fixes many things, ie, fix(g)fix(g) is large, then this gg is not helping "fuse" orbits of xx together, so the number of orbits will increase.