群论

群 \((G,\cdot)\)：指
满足
封闭性 (\(\forall a,b\in G,a\cdot b\in G\))、
结合律 (\(\forall a,b,c\in G,(a\cdot b)\cdot c=a\cdot (b\cdot c)\))，
唯一存在
单位元 (\(\exists e\in G,\forall a\in G\)，有 \(e\cdot a=a\cdot e=a\))、
逆元 (\(\forall a\in G\)，总有 \(\exists b\in G\)，有 \(a\cdot b=b\cdot a=e\)) 的
由集合 \(G\) 和二元运算符 \(\cdot\) 组成的二元组.

性质（消去律）：\(a\cdot x=a\cdot y\Rightarrow x=y\).

\((a\cdot b)^{-1}=b^{-1}\cdot a^{-1}\).
减法没有结合律、单位元等，不算群。
无限群：\(|G|\) 无限（\((\mathbb Z,+),(\mathbb Q,\times)\)）。
有限群：\(|G|\) 有限（\((\mathbb {Z}_n,+),(\mathbb {Z}_n^{\times},\times)\)）。
Abel 群（交换群） \((G,\cdot)\)：指满足交换律(\(\forall a,b\in G,a\cdot b=b\cdot a\)) 的群.
非交换群：不满足交换律的群（\((M_n(\mathbb{R}),+),(S_n\{(1\sim n)\to(1\sim n)\},\times)\)）（矩阵，置换群（\(e=\) 恒等，\(f^{-1}\)：\(f\) 的逆映射））
子群：群 \((G,\cdot),(H,\cdot)\)，满足 \(H\subseteq G\)，则 \((H,\cdot)\) 是 \((G,\cdot)\) 的子群。
最小子群：\((\{e\},\cdot)\)。
整数的子群都是某个数的倍数。
完系 \(\mathbb Z_n\) 的子群都是某个余数的 \(m\) 倍，其中 \(m\mid n\)，个数为 \(d(n)\)。
循环群 \(\left \langle a \right \rangle =(a,\cdot)\)：\(a=\{\cdot _{i=1}^m a|m\in\mathbb Z\}\).
有限循环群：\(\mathbb Z_n=\left \langle \overline 1 \right \rangle\)。
无限循环群：\(\mathbb Z=\left \langle 1\right \rangle\)。
循环群满足交换律。

同构：\(f:(a_1,*)\mapsto (a_2,*)\)（一一映射）且 \(f(g_1)*f(g_2)=f(g_1*g_2)\)，则称 \(g_1,g_2\) 同构，记作 \(g_1\cong g_2\)。

循环群只要元素个数一样就同构。
所以有限循环群 \(\cong \mathbb Z_n\)，无限循环群 \(\cong\mathbb Z\).

\(\mathbb Z_n\) 的生成元个数有 \(\varphi(n)\) 个。

\((\mathbb Z_n^{\times},\times)\cong(\mathbb Z_{n-1},+)\)。

群的阶
群 \(\mathcal{R}\) 的阶是它元素的个数，记作 \(o(\mathcal{R})\) 或 \(|\mathcal{R}|\)，无限群有无限阶。
群 \(\mathcal{R}\) 内的一个元素 \(a\) 的阶是使 \(a^{m}=e\) 成立的最小正整数 \(m\) ，记作 \(o(a)\) 或 \(|a|\)，等于 \(o(\langle a\rangle)\)。若这个数不存在，则称 \(a\) 有无限阶。有限群的所有元素都有有限阶。

拉格朗日定理：若 \(\mathcal{R}\) 为 \(\mathcal{S}\) 的子群 \(\Rightarrow o(\mathcal{R})\mid o(\mathcal{S})\).

若 \(\gcd(o(\mathcal{R}_1),o(\mathcal{R}_2))=1\Rightarrow o(\mathcal{R}_1\mathcal{R}_2)=o(\mathcal{R}_1)o(\mathcal{R}_2)\)，\(\mathcal{R}_1,\mathcal{R}_2\) 是交换群.

群和群的交集还是群，若两群阶互质，则交集为单位元。

例题：若 \(\mathcal{R}\) 是有限交换群，求证 \(\max\{o(g)\mid g\in\mathcal{R}\}=\operatorname{lcm}\{o(g)\mid g\in\mathcal{R}\}\).

设 \(o(g_1)=\max\{o(g)\mid g\in\mathcal{R}\}\)，若 \(\exists g_2\)，使 \(o(g_2)\nmid o(g_1)\)。
则 \(\exists p\)，使 \(v_p(o(g_2))>v_p(o(g_1))\)。
设 \(v_p(o(g_2))=k\)，则 \(o(g_2^{\frac{o(g_2)}{p^k}})=p^k,o(g_1^{p^{(v_p(o(g_1)))}})\)，所以 \(o(g_1)o(g_2)>o(g_1)\)，矛盾.

原根
原根存在性：\(\mathbb Z_p^{\times}=\left \langle \overline a \right \rangle\Leftrightarrow \max{(o(g)|g\in \mathbb Z_p^{\times})}<p-1\)，仅在 \(\mathbb Z_p^{\times}\) 上存在，设原根为 \(g\)，则有 \(\mathbb Z_p^{\times}=\{g^0,g^1,...,g^{p-2}\},(g^k)^{-1}=g^{p-k-1},g^mg^n=g^{m+n}\)，原根个数有 \(\varphi(p-1)\) 个。

\(f(a)=0 \Rightarrow x-a\mid f(x)\).

置换群

定义：\(S_n:(\{1\sim n\}\mapsto\{1\sim n\},(一一)映射复合)\).

\(\alpha=(i_{1,1}i_{1,2}...i_{1,k})\circ(i_{2,1},...)...(i_{r,1},...,i_{r,k})\)（轮换）：任意一个置换都可以分解为若干不相交的循环置换的乘积，且满足交换律，\(o(\alpha)=\left[|i_1|,|i_2|,...,|i_r|\right]\)。

Burnside 引理：

设 \(A\) 和 \(B\) 为有限集合，\(X\) 为一些从 \(A\) 到 \(B\) 的映射组成的集合。 \(G\) 是 \(A\) 上的置换群，且 \(X\) 中的映射在 \(G\) 中的置换作用下封闭。 \(X / G\) 表示 \(G\) 作用在 \(X\) 上产生的所有等价类的集合 (若 \(X\) 中的两个映射经过 \(G\) 中的置换作用后相等，则它们在同一等价类中）。\(X^g\) 表示对于某一种操作 \(g\)，所有等价类集合中，经过 \(g\) 这种操作后不变的集合，则

\[|X / G|=\frac{1}{|G|} \sum_{g \in G}\left|X^{g}\right| \]

其中 \(|S|\) 表示集合 \(S\) 中元素的个数，且

\[X^{g}=\{x \mid x \in X, g(x)=x\} \]

轨道稳定子定理：\(G\) 和 \(X\) 的定义同上， \(\forall x \in X, G^{x}=\{g \mid g(x)=x, g \in G\}, G(x)=\{g(x) \mid g \in G\}\)，
其中 \(G^{x}\) 称为 \(x\) 的稳定子， \(G(x)\) 称为 \(x\) 的轨道，则有

\[|G|=\left|G^{x}\right||G(x)| \]

轨道稳定子定理的证明：首先可以证明 \(G^{x}\) 是 \(G\) 的子群，因为

封闭性: 若 \(f, g \in G\)，则 \(f \circ g(x)=f(g(x))=f(x)=x\)，所以 \(f \circ g \in G^{x}\).
结合律：显然置换的乘法满足结合律.
单位元: 因为 \(I(x)=x\) ，所以 \(I \in G^{x}\) ( \(I\) 为恒等置换)
逆元: 若 \(g \in G^{x}\)，则 \(g^{-1}(x)=g^{-1}(g(x))=g^{-1} \circ g(x)=I(x)=x\)，所以 \(g^{-1} \in G^{x}\).
则由群论中的拉格朗日定理，可得

\[|G|=\left|G^{x}\right|\left[G: G^{x}\right] \]

其中 \(\left[G: G^{x}\right]\) 为 \(G^{x}\) 不同的左陪集个数。接下来只需证明 \(|G(x)|=\left[G: G^{x}\right]\)，我们将其转化为证明存在一个从 \(G(x)\) 到 \(G^{x}\) 所有不同左陪集的双射。令 \(\varphi(g(x))=g G^{x}\)，下证 \(\varphi\) 为双射

若 \(g(x)=f(x)\) ，两边同时左乘 \(f^{-1}\) ，可得 \(f^{-1} \circ g(x)=I(x)=x\)，所以 \(f^{-1} \circ g \in G^{x}\)，由陪集的性质可得 \(\left(f^{-1} \circ g\right) G^{x}=G^{x}\)，即 \(g G^{x}=f G^{x}\).
反过来可证，若 \(g G^{x}=f G^{x}\)，则有 \(g(x)=f(x)\).
以上两点说明对于一个 \(g(x)\)，只有一个左陪集与其对应，即 \(\varphi\) 是一个从 \(G(x)\) 到左陪集的映射.
又显然 \(\varphi\) 有逆映射，因此 \(\varphi\) 是一个双射.
Burnside 引理的证明：

\[\begin{aligned} \sum_{g \in G}\left|X^{g}\right| & =|\{(g, x) \mid(g, x) \in G \times X, g(x)=x\}| \\ & =\sum_{x \in X}\left|G^{x}\right| \\ & =\sum_{x \in X} \frac{|G|}{|G(x)|} \quad \text { (轨道稳定子定理) } \\ & =|G| \sum_{x \in X} \frac{1}{|G(x)|} \\ & =|G| \sum_{Y \in X / G} \sum_{x \in Y} \frac{1}{|G(x)|} \\ & =|G| \sum_{Y \in X / G} \sum_{x \in Y} \frac{1}{|Y|} \\ & =|G| \sum_{Y \in X / G} 1 \\ & =|G||X / G| \end{aligned} \]

所以有

\[|X / G|=\frac{1}{|G|} \sum_{g \in G}\left|X^{g}\right| \]

Pólya 定理

在与 Burnside 引理相同的前置条件下，若 \(X\) 为所有从 \(A\) 到 \(B\) 的映射，内容修改为

\[|X / G|=\frac{1}{|G|} \sum_{g \in G}|B|^{c(g)} \]

其中 \(c(g)\) 表示置换 \(g\) 能拆分成的不相交的循环置换的数量。
Pólya 定理的证明
在 Burnside 引理中，显然 \(g(x)=x\) 的充要条件是 \(x\) 将 \(g\) 中每个循环置换的元素都映射到了 \(B\) 中的同一元素，所以 \(\left|X^{g}\right|=|B|^{c(g)}\)，即可得 Pólya 定理。