Burnside 定理的證明

    這是一個計數定理，用來計算一個有限集合被群作用(排列)下的等價類個數。其實這定理不是 Burnside 發現或證明的，只是 Burnside 最早把它寫進教科書。證明這定理要用到一些群論的定理，雖然這些定理的證明也可以直接全部寫入本定理的證明當中，但是證明會變得很冗長，其實會更不容易懂。假設一個有限集 X = {a, b, c, ...} 被一個群 G = {α, β, γ, ...} 作用。其實 G 中的元素都是 $X \to X$ 的一對一且映成(雙射)的函數， 群作用的意思就是做這些函數的映射。也就是說如果規定一個 X 中的元素的排列順序，群作用就是把它變成另一個排列而已，所以 G 中的元素也叫排列。在 G 上規定函數複合為元素間的二元運算($\circ$)，那 G 就形成一個群，所以才叫群作用。

令 $Stab(x) = \{\pi | \pi(x) = x, \pi \in  G\}$，白話就是$Stab(x)$是使得 $x$ 映射到自身的所有排列，稱之為穩定子(stabilizer)。$Stab(x)$是一個群，證明省略。

$\pi \ Stab(x) = \{\pi\circ \rho|\rho \in  Stab(x)\}$，$\pi \ Stab(x)$稱為$Stab(x)$的一個左陪集。

$Stab(x)$有一個很重要的性質，假定某個把 $x$ 映射到 $y$ 的排列 $\pi_{xy}$，$\pi_{xy}Stab(x)$的所有元素都把 $x$ 映射到 $y$，並且任意把 $x$ 映射到 $y$ 的排列都屬於$\pi_{xy}Stab(x)$。這個性質就像線性方程組的解，$Stab(x)$就是零解，$\pi_{xy}$就是特解，通解一定可以寫成零解加上特解。甚至連證明的過程也類似。以下來證明這一點。

$\pi_{xy}\ Stab(x)$中的元素把 $x$ 映射到 $y$，這很明顯，因為$Stab(x)$的元素把 $x$ 映射到 $x$，而$\pi_{xy}$把 $x$ 映射到 $y$ ，複合之後當然是把 $x$ 映射到 $y$。

對於任意把 $x$ 映射到 $y$ 的 $\pi$，${\pi_{xy}}^{-1}\circ \pi$把 $x$ 映射到 $x$，故屬於$Stab(x)$，因此$\pi_{xy}\circ ({\pi_{xy}}^{-1}\circ \pi)$屬於$\pi_{xy}Stab(x)$，而$\pi_{xy}\circ ({\pi_{xy}}^{-1}\circ \pi)=(\pi_{xy}\circ {\pi_{xy}}^{-1})\circ \pi=\pi$。$\square$

我們把 $x$ 被 G 中的排列作用後，得到的元素集稱為$O_x$($x$的orbit)。$O_x = \{y|y=\pi(x),\pi \in  G\}$ 。所有 X 中的元素的 orbit，可以對 X 形成一分割：$\{O_1,O_2,\cdots,O_N\}$。分割的大小為N。

$O_x$可以和$Stab(x)$的所有左陪集形成一個雙射：$\pi_{xy}Stab(x)  \to y$，這個映射是雙射可以由上面剛剛證明過的$Stab(x)$的性質看出。所以$Stab(x)$在 G 中的 index (群論術語)，等於$O_x$的大小($|O_x|$)，即
$$\frac{|G|}{|Stab(x)|} = |O_x| $$。令$f(x)={1}/{|O_x|}$，並引入一示性函數 $\chi(P)$，P是命題，如果P為真則 $\chi(P)=1$，如果P為假則 $\chi(P)=0$。

現用兩種方式來計數$\Sigma_{x \in X} \ f(x)$。首先依X的orbit分割來分組：$$\sum_{x \in X}\ f(x)=\sum_{i=1}^{N}\sum_{x \in O_i}\frac{1}{|O_i|}=\sum_{i=1}^{N}1=N$$。其次我們運用上面得到的$|O_x|$公式：$$\begin{align*}
\sum_{x \in X}\ f(x) &=\sum_{x \in X}\frac{|Stab(x)|}{|G|}=\frac{1}{|G|}\sum_{x \in X}\sum_{\pi \in G}\chi(\pi(x)=x) \\
 &=\frac{1}{|G|}\sum_{\pi \in G}\sum_{x \in X}\chi(\pi(x)=x)=\frac{1}{|G|}\sum_{\pi \in G}|Fix(\pi)|\end{align*}$$。其實$Fix(\pi)$的定義由上式也很明白，$Fix(\pi)=\{x|x \in X,\pi(x)=x\}$。結論是：$$N=\frac{1}{|G|}\sum_{\pi \in G}|Fix(\pi)|$$。這就是Burnside定理。