# Way to Burnside's Lemma

Burnside's Lemma 是一個好的數學理論，可以拿來解很多組合題目。

本文第一部分是用以證明 Burnside's lemma。
因為我的理解力不好，證明會寫的比較繁瑣。

第二部分是介紹一些這個 lemma 的 corollary，例如 [Fermat's little theorem](https://zh.wikipedia.org/zh-tw/%E8%B4%B9%E9%A9%AC%E5%B0%8F%E5%AE%9A%E7%90%86) and [Wilson's theorem](https://zh.wikipedia.org/zh-tw/%E5%A8%81%E5%B0%94%E9%80%8A%E5%AE%9A%E7%90%86)

第三部分提供個神經的證明 Burnside's lemma 的方式。

第四部分是介紹一個推論，闡述一些直觀理解，以及解一些好題目。
(todo)

請參考

* https://oi-wiki.org/math/algebra/group-theory/

* https://wuli.wiki/online/Group3.html

這兩篇好文章。

## Burnside's lemma 理論推導

以下闡述兩個跟 Burnside's lemma 非常非常之相關的定理：

* Lagrange's theorem

* Orbit stabilizer theorem

事實上後者可以視作是前者的群作用版本。

### Lagrange's Theorem

Statement : $[G:H]|H| = |G|$ ，即 coset 的個數乘以子群的大小就是整個群的個數。

proof sketch :
首先，對於任意 $g$， $\phi : H \to gH,\,\phi(h)=gh$ 是一個 bijection，所以 $G$ 的每個 left coset $gH$ 都有一樣的大小，即 $|gH| = |H|,\quad\forall g\in G$

再來，因為 $g_1H = g_2H \iff g_1^{-1}g_2 \in H$，又因為 relation $\sim$ given by
$$g_1 \sim g_2 \iff g_1^{-1}g_2 \in H$$
是一個 equivalence relation，則我們知道 $\{gH\}_g$ partitions $G$, i.e.
我們則可以把 $G$ 寫成一堆 coset 的 disjoint union:
$$G=\bigsqcup_{g\in\{g_1,g_2,\dots,g_{[G:H]}\}}gH$$
其中 $g_1,g_2,\dots,g_{[G:H]}$ is chosen so that they are from different coset.

則有
$$\begin{aligned}
|G|
&= \left|\bigsqcup_{g\in\{g_1,g_2,\dots,g_{[G:H]}\}}gH\right| \\
&= \sum_{g\in\{g_1,g_2,\dots,g_{[G:H]}\}} |gH| \\
&= \sum_{g\in\{g_1,g_2,\dots,g_{[G:H]}\}} |H| \\
&= [G:H]|H| \\
\end{aligned}$$

### Orbit-Stabilizer theorem

Statement : 假設 finite $G$ acts on finite $X$, 則 $$\forall x\in X,\,|G| = |G\cdot x||\text{Stab}(x)|$$
即 $G$ 的大小為 Orbit 的大小乘以 Stabilizer 的大小。定理因此得名。

proof sketch : 假設 $x\in X$ 已經給定。

首先，注意到這個等式一臉 Lagrange 樣，而且 $\text{Stab}(x)$ 又是一個 $G$ 的 subgroup ，所以能知道只要證明 $|G\cdot x| = [G:\text{Stab}(x)]$ 即可。

我們定義
$$\phi: G\cdot x \to G / \text{Stab}(x),\quad \phi(g\cdot x) = g \text{Stab}(x)$$

則，如果我們有 $g_1, g_2$
$$\begin{aligned}
g_1 \cdot x = g_2 \cdot x
&\iff g_1^{-1}g_2 \cdot x = x \\
&\iff g_1^{-1}g_2 \in \text{Stab}(x) \iff g_1 \text{Stab}(x) = g_2 \text{Stab}(x)
\end{aligned}$$

這個邏輯式從左到右說明 $\phi$ well define, 從右到左說明 $\phi$ is 1-1.

$\phi$ 根據定義當然是 onto 的，我們就得到了 $G\cdot x \to G / \text{Stab}(x)$ 的 bijection，因此終於 $|G\cdot x| = [G:\text{Stab}(x)]$

Follow up: 怎麼直觀理解？

#### 推論 1: 令 $G$ 按伴隨作用，作用於自身，則
$$\forall x\in G, \quad |G\cdot x||C_G(x)| = |G|$$

proof sketch:

$x$ 的 centralizer in $G$ 就是 $\text{Stab}(g)$，因為作用是 adjoint action.

套上面的定理就好了。

### Burnside's Lemma

要證明這個定理，我們需要兩個結論。

:::info
1. 藉由交換順序可得到的

$$\sum_{x\in X}|X^g| = \sum_{g\in G}{|\text{Stab}(g)|}$$

證明如下：

$$\begin{aligned}
\sum_{g\in G}|X^g|
&= \sum_{g\in G}\sum_{g\cdot x = x : x \in X}1 \\
&= \sum_{g\in G}\sum_{g\cdot x = x : x \in X}1 \\
&= \sum_{g\cdot x = x : g \in G, x\in X}1 \\
&= \sum_{x\in X}|\text{Stab}(x)| \\
\end{aligned}$$

2. Orbit Stabilizer Theorem

在上面已經證明過了。
:::

現在，我們推論出兩個跟 $\sum_{x\in X}\frac{|\text{Stab}(x)|}{|G|}$ 有關的等式來得出結論。

第一個等式用到上面說會用到的第一個結論

$$
\sum_{x\in X}\frac{|\text{Stab}(x)|}{|G|}
= \frac{1}{|G|}\sum_{x\in X}|\text{Stab}(x)|
= \frac{1}{|G|}\sum_{g\in G}|X^g|
$$

第二個等式交換累加順序，並用到上面說會用到的第二個結論

$$\boxed{\begin{aligned}
\sum_{x\in X}\frac{|\text{Stab}(x)|}{|G|}
&= \sum_{G\cdot x\in X/G}\sum_{x'\in G\cdot x} \frac{|\text{Stab}(x')|}{|G|} \\
&= \sum_{G\cdot x\in X/G} |G\cdot x| \frac{|\text{Stab}(x)|}{|G|} \\
&= \sum_{G\cdot x\in X/G} \frac{|G|}{|G|} \quad (\text{orbit stabilizer theorem}) \\
&= \sum_{G\cdot x\in X/G} 1 \\
&= |X/G|
\end{aligned}}$$

就完成了。

#### Remark

終於證出來了！不知道為什麼有很多人都說這個定理很直觀啊，或者是會在他們的證明說

> ...顯然，我們有
> $$\sum_{x\in X}|X^g| = \sum_{g\in G}{\text{Stab}(g)}$$

> ...因為"一些神秘而且看起來毫無關聯的原因"，我們有
> $$|X/G| = \sum_{x\in X}{1 \over [G : \text{Stab}(x)]}$$

之類的暴論😫 然後就用幾個等號就完成了證明。

還有的只要用四個等號就能證明出來。現在人均拉馬努金了嗎...

## Corollary 及應用

### 定理1:

如果 $G$ acts on $X$ and $|G| = p^k,\,k\in \mathbb{N},\, p$ prime, then

$$|X| \equiv |X^G| \pmod p$$

proof sketch:
核心在於把 $X$ 拆成一堆軌道的聯集，
$$X = \bigsqcup_{G\cdot x\in X/G}G\cdot x$$

然後考察其中一個軌道 $G\cdot x \in X/G$ 的大小。

由 Orbit-Stabilizer theorem, 可以得到
$$|G\cdot x| = \frac{|G|}{|\text{Stab}(x)|}$$

右邊，分母是 $p^k$，而分子根據 Lagrange's theorem 也要整除 $p^k$，
所以這個軌道的大小是 $|G\cdot x| = p^n$ for some $n \in \{0,1,\cdots,k\}$
，要不是 $1$ 要不就被 $p$ 整除。

而且，$p \not\mid |G\cdot x|\iff |G\cdot x| = 1 \iff x \in X^G$

因此我們可以這樣分割計算 $|X|$

$$\begin{aligned}|X|
&= \left|\bigsqcup_{G\cdot x\in X/G}G\cdot x \,\right|\\
&= \sum_{x\in X^G}|G\cdot x| +\sum_{p \mid |G\cdot x|}|G\cdot x | \\
&= |X^G| + \underbrace{\sum_{p \mid |G\cdot x|}|G\cdot x|}_{\text{divisible by }p}
\end{aligned}$$

所以兩邊取 $\pmod p$，就有

$$\boxed{|X| \equiv |X^G| \pmod p}$$

### 定理2:

如果 $G$ acts on $X$ and $|G| = p,\,k\in \mathbb{N},\, p$ prime, then

$$|X| \equiv |X^G| \pmod p$$

proof sketch: 其實就是定理1 的 $k=1$ 的情況。

#### Remark

對於 $G = \mathbb Z_p$ 的特殊情況，可以用 Burnside's lemma 證明。

proof sketch: 考慮群 $G = \mathbb Z_p, p$ prime, $G$ acts on $X$.

則我們有 $X^g = X^G$ if $g \not = e$, $X^e = X$.

所以根據 Burnside's lemma, 把 $\sum_{x\in G}$ 拆成 $e$ 跟不是 $e$ 就有
$$|X/G| = \frac{1}{p}\left(|X| + (p-1)|X^G|\right)$$

然後，因為 $|X/G|$ 是整數，把右邊的 $p$ 乘過去，就有

$$|X| + (p-1)|X^G| = p|X/G| \equiv 0 \pmod p$$

這也就是

$$\boxed{|X| \equiv |X^G| \pmod p}$$

之所以把這個看似奇怪但正確的事實特別羅列出來，
是因為他可以推得鼎鼎大名的 Fermat's theorem and Wilson's theorem.

方法如下：

### 定理3 (Fermat's theorem)

如果 $p$ is prime 而且 $a$ 是某個與 $p$ 互質的整數, 則有
$$a^{p-1} \equiv 1 \pmod p$$

proof sketch.

首先，先看一看初等證明。

我們有
$$\left\{1, 2 ,\dots,p-1\right\} = \left\{a, 2a ,\dots,(p-1)a\right\}$$

如果不是這樣的話，則左邊集合元素應比 $p-1$ 少，因此存在有 $1 \le s < t \le p-1$，使得

$$sa \equiv ta \pmod {p}$$

因為 $\gcd(a,p)=1$ 則可以把 $a$ 除掉，又得到 $s=t$ 之矛盾。

所以，左邊集合每個元素全部乘跟右邊集合每個元素全部乘是一樣的，即

$$1\cdot 2 \cdot \dots \cdot p-1 \equiv a\cdot 2a \cdot\dots \cdot (p-1)a \pmod p$$

也就是

$$(p-1)! \equiv a^{p-1}(p-1)! \pmod p$$

因為 $\gcd((p-1)!,p)=1$ 則可以把 $(p-1)!$ 除掉，得到

$$a^{p-1} \equiv 1 \pmod p$$

proof sketch 2.

現在介紹另一個用到上面定理的群論證明。

首先，給一個 notation: 如果 X, Y 為兩個集合，則有
$$Map(X,Y) = \left\{f : X \to Y : \text{f is a function}\right\}$$
如果 $X$, $Y$ 為兩個有限集，則根據乘法原理， $|Map(X,Y)| = |Y|^{|X|}$

> 別的地方也有
$$Y^X = \left\{f : X \to Y : \text{f is a function}\right\}$$
的寫法，這種寫法的好處在於 $\left|Y^X\right| = |Y|^{|X|}$ 的事實就立刻變得很形象。
不過現在會跟 $X^g$ 這種群作用的符號混淆，因此另訂符號 $Map$。

現在，考慮群 $G = \mathbb{Z}_p$ 作用在集合 $X = Z_p$ 上，
且作用方法為 $\forall g \in G, x \in X$
$$g \cdot x = g + x$$ 其中 $+$ 為 $\mathbb Z_p$ 的加法。

並且考慮群 $G = \mathbb{Z}_p$ 作用在函數集合 $X = Map(\mathbb{Z}_p,\mathbb{Z}_a)$ 上，
且作用方法為 $\forall g\in G, f \in X$
$$(g\cdot f)(x) = f(g^{-1}\cdot x)$$

> 可以驗證這的確是一個作用

現在，因為 $|X| = a^p$，根據上面那個定理，我們當然只要能證明 $|X^G| = a$ 就好了。

為了證明這個，假設有 $f \in X^G$ ，也就是說
$$\forall g \in G, \forall x \in \mathbb{Z}_p,\,f(x) = f(g^{-1}+x) = f(-g+x)$$

讓 $g=1$ 並且根據歸納法迭代，就有
$$f(x) = f(x+1) = f(x+2) = \dots$$

因此 $f(x)$ 是一個常數函數，$f$ 也就只能有 $|f(\mathbb Z_p)| = |Z_a| = a$ 種選擇。
反過來說，所有常數函數都容易驗證屬於 $X^G$，所以 $|X^G| = a$，從而有
$$\boxed{a^p = |X| \equiv |X^G| = a \pmod p}$$

#### Remark

這種群論證明的難點就難在要找出奇怪的群 $G$, 奇怪的集合 $X$ 以及奇怪的作用方式，然後套定理。

### 定理4 (Wilson's theorem)

Recall 一下命題內容： 如果 $p$ prime, 則
$$(p-1)! \equiv p-1 \pmod p-1$$

proof sketch.

老套路，用那個定理。令 $S_p$ 為 symmetric group, $C_p \le S_p$ 為 permutation cyclic group generated by $\langle\sigma\rangle$,

> recall [symmetric group, permutation group](/w_kZBvIORnGXMfLDtrq4Sg)

$$\sigma =
\begin{pmatrix}
1 & 2 & 3 & \dots & p \\
p & 1 & 2 & \dots & p-1
\end{pmatrix}$$

則根據 Lagrange theorem 有

$$|S_p / C_p| = \frac{|S_p|}{|C_p|} = \frac{p!}{p} = (p-1)!$$

如果令 $X = |S_p / C_p|$，最後一步就是找到神秘的 $G$ 和作用在 $X$ 的方式，
使得 $|X^G| = p-1$ 就結束了。然而這是很大的一步。

經過與柯西、歐拉及印度女神的溝通，我們發現可以令 $G = C_p, X=S_p / C_p$, 按照以下伴隨作用作用於 $S_p$
$$\forall \sigma \in C_p,\,\tau\in S_p \quad \sigma\cdot \tau = \sigma\tau\sigma^{-1}$$

並且讓 $G$ 按照以下(由上面那個作用所「誘導」的作用)作用在 $X=S_p / C_p$
$$\forall \sigma \in C_p,\,\tau\in S_p \quad \sigma \cdot (\tau S_p) = (\sigma \cdot \tau)S_p$$

現在，因為有
$$C_p^{S_p} = N_{S_p}(C_p), \text{ i.e. }(S_p / C_p)^{C_p} = N_{S_p}(C_p) / C_p$$
我們就有 the size of fixed point $\left|(S_p / C_p)^{C_p}\right| = |N_{S_p}(C_p) / C_p|$ = $\frac{|N_{S_p}(C_p)|}{p}$，再次根據 Lagrange.

> 上述不是顯然的事實，但可以按照定義簡單證出，此處省略。
> recall [normalizer](/w_kZBvIORnGXMfLDtrq4Sg)

現在我們要證明的就是 $|N_{S_p}(C_p)| = p(p-1)$

::: spoiler Proof details

本質上要說明 $\tau \in N_{S_p}(C_p)$ 若且唯若 $\tau$ 形如 $ki + l$, for some $k \in 1, 2,\dots,p-1$, and some $l \in 1, 2,\dots, p$

"$\ge$": 假設 $\tau \in N_{S_p}(C_p) \subset N_{S_p}(\sigma)$，則 $\tau \sigma \tau^{-1} \in C_p$, 因此

$$\begin{aligned}
&\tau \sigma \tau^{-1} = \sigma^{k} \text{ for some } k \in \{1,2,\dots,p-1\} \\
&\Rightarrow \tau \sigma = \sigma^{k} \tau \\
&\Rightarrow \tau(i+1) = \tau(i) + k \quad\forall i \\
&\Rightarrow \tau(i) = ki + l \quad\exists l \in \{1,2,\dots,p\}\,\forall i \\
\end{aligned}$$

以上的加法是 modulo $p$ 加法。因為 $k$ 跟 $l$ 所提供的自由度個別為 $p$, $p-1$，
所以 $\tau$ 最多有 $p(p-1)$ 個可能。

"$\le$": 假設 $$\tau = ki + l, \quad\text{some } k \in 1, 2,\dots,p-1,\,l \in 1, 2,\dots, p$$

則單純計算如下
$$\begin{aligned}
\tau\sigma\tau^{-1}(i)
&= \tau\sigma(k^{-1}(i - l)) \\
&= \tau(k^{-1}(i - l) + 1) \\
&= k(k^{-1}(i - l) + 1)+l \\
&= i+k = \sigma^k(i)
\end{aligned}$$

也就是 $\tau\sigma\tau^{-1} \in N_{S_p}(C_p)$

所以就有 $|N_{S_p}(C_p)| = p(p-1)$
:::

此處終於證明完畢。
最後只要把東西跟已知的套一套，就有
$$\boxed{\begin{aligned}
(p-1)!
&\equiv |S_p/C_p| \\
&\equiv |(S_p/C_p)^{C_p}| \\
&\equiv |N_{S_p}(C_p)/C_p| \\
&\equiv \frac{|N_{S_p}(C_p)|}{|C_p|} \\
&\equiv \frac{p(p-1)}{p} \\
&\equiv p-1 \pmod p
\end{aligned}}$$

### Remark (總結一下所使用的技巧以及反思)

首先，在證明 Fermat's 跟 Wilson's 定理，為了要引用 $|X|\equiv|X^G|$ 我們都各自找出了某個莫名其妙的群及作用。

就 Fermat's 而言，我們本質上是利用了:
> 如果群 $G$ 作用在 $X$ 上，，則 $G$ 也有一個在 $Map(X,G)$ 上的誘導作用
> $$G \text{ acts on } Map(X,G) \text{ by } g\cdot f(x) := f(g^{-1} \cdot x)$$

就 Wilson's 而言，我們本質上是利用了:

> 如果群 $H$ 作用在 $G$ 上，其中 $H\le G$ 是個子群，則 $H$ 也有一個在 $G/H$ 上的誘導作用
> $$H \text{ acts on } G/H \text{ by } h \cdot (gH) := (h\cdot g) H$$

不僅如此，我們還要讓 $H$ 伴隨作用於 $G$ 而不能是其他作用 (e.g. 左乘作用)。

## Burnside's lemma 另證

:warning: :warning: :warning:
以下的證明比較複雜。再繼續之前，請確保看懂了上面的內容。
:warning: :warning: :warning:

### Remark

首先，就像上面那個反思說的，假設 $G$ 作用在 $X$，則我們也有一個作用 $G$ 在 $Map(X,C)$ 上，其中 $C$ 是某集合，方法是$\forall f \in Map(X,C)$
$$\forall x \in X,\,(g\cdot f)(x) = f(g^{-1}\cdot x)$$

可以驗證這的確是群作用。這個群作用也被用在上面 Fermat's little theorem 的證明。

### Lemma 1

假設有限 $G$ 作用在有限 $X$，且 $C$ 是某有限集合，則
$$Map(X,C)^G \cong Map(X/G,C)$$

proof sketch.

考慮 $f \in Map(X,C)^G$, 則
$$f(g \cdot x) = x \quad\forall g\in G,\,\forall x\in X$$
也就是 is constant on each orbit $G\cdot x$

這就對應到了 $Map(X/G,C)$ 的一個函數，$\bar{f}(G\cdot x) := c_x \forall x$.

反過來類似。

### Lemma 2

假設有限 $G$ 作用在有限 $X$，且 $W$ is a vector space over $\mathbb Q$，
則 $\forall w\in Map(X,W)^G$，以及 $\bar{w}\in Map(X/G,W)$ corresponding to $w$ by lemma 1, 都有
$$\sum_{O\in X/G}\bar{w}(O) = \frac{1}{|G|}\sum_{g\in G}\sum_{x\in X^g}w(x)$$

proof sketch.

其實也跟 Burnside's lemma 的證明差不了多少。

$$\begin{aligned}
\sum_{g\in G}\sum_{x\in X^g} w(x)
&= \sum_{x\in X}\sum_{g\in \text{Stab}(x)} w(x) & (\text{Fubini theorem})\\
&= \sum_{x\in X} |\text{Stab}(x)| w(x) \\
&= \sum_{x\in X} \frac{|G|}{|G\cdot x|} w(x) & (\text{Orbit-stabilizer thm.}) \\
&= \sum_{O\in X/G}\sum_{x\in O} \frac{|G|}{|G\cdot x|} w(x) & (\text{split X into orbits}) \\
&= |G|\sum_{O\in X/G}\sum_{x\in O} \frac{w(x)}{|O|} \\
&= |G|\sum_{O\in X/G}|O| \frac{\bar{w}(O)}{|O|} & (w \text{ is constantly } \bar{w}(O) \text{ on } O \text{ by definition}) \\
&= |G|\sum_{O\in X/G}\bar{w}(O)
\end{aligned}$$

所以
$$\boxed{\sum_{O\in X/G}\bar{w}(O) = \frac{1}{|G|}\sum_{g\in G}\sum_{x\in X^g}w(x)}$$
現在來用這個定理證明 Burnside's Lemma.

### Burnside's Lemma again

proof sketch. Take $W = \mathbb Q$ and $w = 1$ in the lemma above. (wtf)

此時僅需驗證與 $w=1$ 對應的 $\bar{w}$ 也是 $1$ 即可。