A Universe of Sorts

§ Clean way to write burnside lemma

Burnside lemma says that

|Orb(G)| \equiv 1/|G| \sum_{g \in G} fix(g)

. We prove this as follows:

\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|$ .
Since $|Orb(x)$ is the total cardinality of the orbit, each element in the orbit contributes $1/|Orb(x)|$ towards cardinality of the full orbit.
Thus, the sum over an orbit $\sum_{x \in Orb(x)} 1/|Orb(x)|$ will be 1.
Suppose a group action has two orbits, $O_1$ and $O_2$ . I can write the sum $\sum_{x \in g} 1/|Orb(x)|$ as: $\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 $\sum_{o \in Orbits} \sum_{x \in o} 1/|o|$ . But this sum is equal to $\sum_{o \in Orbits} \sum_{x \in o} 1/|Orb(x)|$ .
This sum sums over the entire group, so it can be written as $\sum_{x \in G} 1/|Orb(x)|$ .
In general, the sum over the entire group $\sum_{x \in g} 1/|Orb(x)|$ will be the number of orbits, since the same argument holds for each orbit .

\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:

\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)$ is large,
then this $g$ is not helping "fuse" orbits of $x$ together, so the number of
orbits will increase.

Reference