§ Clean way to write burnside lemma

Burnside lemma says that Orb(G)1/GgGfix(g)|Orb(G)| \equiv 1/|G| \sum_{g \in G} fix(g). We prove this as follows:
gGfix(g)=gG{x:g(x)=x}={(g,x):g(x)=x}=xX{x:g(x)=x}=xXStab(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 xOrb(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 xg1/Orb(x)\sum_{x \in g} 1/|Orb(x)| as: xO11/O1+xO21/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 oOrbitsxo1/o\sum_{o \in Orbits} \sum_{x \in o} 1/|o|. But this sum is equal to oOrbitsxo1/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 xG1/Orb(x)\sum_{x \in G} 1/|Orb(x)|.
  • In general, the sum over the entire group xg1/Orb(x)\sum_{x \in g} 1/|Orb(x)| will be the number of orbits, since the same argument holds for each orbit .
=xXStab(x)=xXG/Orb(x)=Goorbitsxo1/o=Gnum.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:
gGfix(g)=Gnum.orbits1/G(gGfix(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.