这里是群论学习笔记。
所有接下来短时间内会用到的定理与定义全都会被<u>下划线</u>。因此，如果您只打算粗略浏览，可以跳过所有非下划线的定理与定义。但是，思考全部定理有助于加深对重要定理的理解。
推荐配合 Ctrl+F 食用，因为知识点太多很有可能看了后面忘前面。
I.群初步
I.基础定义
<u>定义</u>：群由一个集合 \mathbb S 和一个二元运算 \cdot 构成。其有如下性质：
-
封闭性：\forall a,b\in\mathbb S,a\cdot b\in\mathbb S。
-
结合律：\forall a,b,c\in\mathbb S,(a\cdot b)\cdot c=a\cdot(b\cdot c)。
-
单位元/幺元：\exists e\in\mathbb S,\operatorname{s.t.}\forall a\in\mathbb S,e\cdot a=a\cdot e=a。
-
逆元：\forall a\in\mathbb S,\exists b\in\mathbb S,\operatorname{s.t.}a\cdot b=b\cdot a=e。称 b 为 a 的逆元，记作 a^{-1}。
如满足如上性质，则称 (\mathbb S,\cdot) 构成一个群。
在本文中，群与集合都会使用 \mathbb 字体的定义来呈现，而所有非 \mathbb 字体的定义都是其它东西。（有例外，就是 \text 字体的定义来表示一些专有的群或集合）
在本文中，群中元素一般会使用常规小写字体的定义来呈现。
一个等价的定义是：
-
封闭性：\forall a,b\in\mathbb S,a\cdot b\in\mathbb S。
-
结合律：\forall a,b,c\in\mathbb S,(a\cdot b)\cdot c=a\cdot(b\cdot c)。
-
左单位元/幺元：\exists e\in\mathbb S,\operatorname{s.t.}\forall a\in\mathbb S,e\cdot a=a。
-
左逆元：\forall a\in\mathbb S,\exists b\in\mathbb S,\operatorname{s.t.}b\cdot a=e。称 b 为 a 的左逆元，记作 a^{-1}。
该等价定义虽然是原定义的子定义，但是二者是等价的，即左幺元等于右幺元，左逆元等于右逆元。
Proof 1.左单位元等于右单位元
设左单位元为 e_l，右单位元为 e_r。则 e_le_r=e_l（e_r 是右单位元），且 e_le_r=e_r（e_l 是左单位元），故 e_l=e_r。
Proof 2.单位元唯一
设有两单位元 e,e'。则 ee'=e=e'。
Proof 3.左逆元等于右逆元
设 a 的左逆元为 b，右逆元为 c，则 ba=e=ac，则 bac=ec，则 be=ec，则 b=c。
-
消去律：在群中如果 ab=ac，则 b=c。可以直接左乘 a^{-1} 得证。
这被称作“左消去律”，该性质是左逆元存在的直接推论。
同理有右逆元的推论——右消去律。
因为在群中左右逆元均存在，所以二者被合并作了消去律。
由消去律可以直接证得左右逆元均唯一，进而证得逆元的逆元是本身。
定义：如果 \cdot 运算满足交换律，则该群被称作交换群，或者阿贝尔群。
因为 + 是最常见的满足交换律的运算，因此交换群有时也被称作加群，此时运算常直接用 + 代替、单位元常记作 0、逆元常记作 -a，也称负元。
<u>定义</u>：如果 \mathbb G 中元素有限，则称其为有限群，否则则为无限群。有限群存在阶，即为群中元素个数，记作 |\mathbb G|。
II.基础含义
群中内容常常被看作是变换。例如，群 (\mathbb Z,+) 中元素可以被看作是整数，也可以被看作是将某物增加该数的变换，即一个一维向量。因此，+ 操作便定义了一种合并两个变换的规则，即映射 (a,b)\rightarrow c。
同理，群 (\mathbb C,+) 是在复平面上的移动，而 (\mathbb C,\times) 是在复平面上的旋转与翻转。
还有一些更奇妙的群。例如 n 阶实方阵全体 \R_n^2 与矩阵乘法 \times 构成的群，这里如果把矩阵乘法看作是变换就会很好理解。例如对正 n 边形的顶点重标号的变换，旋转重标号与翻转重编号一起构成了一个群，运算是重编号（置换）的复合，向量空间关于加法也成群。
III.扩展定义
定义：半群是集合与运算的二元组，该运算在该集合上满足结合律和封闭性。
定义：幺半群是性质更强的半群，其还存在幺元（单位元）。
<u>群判定定理</u>：半群 \mathbb G 是群的充要条件是 \forall a,b\in\mathbb G,\exists x\in\mathbb G\text{ s.t. }xa=b,\exists y\in\mathbb G\text{ s.t. }ay=b。
Proof：
必要性显然，因为若其是群则左右同乘 a 的逆元即证。
充分性：先证单位元。若令 a=b，则由上，方程 xb=b 有解，设为 e。那么如果 \forall a\in\mathbb G,ea=a 则 e 是单位元。因 by=a 有解，故设解为 c 则 ea=e(bc)=(eb)c=bc=a。
逆元显然存在。
<u>有限群判定定理</u>：有限半群是群当且仅当消去律成立。
Proof：
必要性显然。
考虑令 \mathbb G 中所有元素全都左乘 a 得到一集合 \mathbb G'。因为 \mathbb G 是群，所以 \mathbb G'\subseteq\mathbb G。因为 \mathbb G 中无相同元素，所以由消去律 \mathbb G' 中亦无相同元素，则 |\mathbb G'|=|\mathbb G|，即二者相同，即方程 ay=b 必有解。同理 xa=b 亦有解。
注意该 Proof 在 \mathbb G 是无限群时不一定成立，这涉及到无限的知识，与群论就不太紧密了，暂且忽略。
IV.群的子系统
<u>定义</u>：子群是群的子集，且关于母群的运算成群。\mathbb{H\leq G} 意为 \mathbb H 是 \mathbb G 的子群。
定义：平凡子群是阶为一（如果阶为一则元素仅包含单位元）或为本身的子群。非平凡子群为其它子群。真子群为所有非本身的子群（包括阶为一的群）。\mathbb{H<G} 意为 \mathbb H 是 \mathbb G 的真子群。
<u>定理</u>：子母群的单位元相同；如一个元素在子母群中同时出现，则其逆元相同。
前者由单位元唯一和母群消去律得证；后者由逆元唯一和母群消去律得证。
<u>子群判定定理</u>：\mathbb{H\leq G} 当且仅当 \forall a,b\in\mathbb H,ab^{-1}\in\mathbb H。
有限群子群判定定理：对于有限群 \mathbb G 的子集 \mathbb H，\mathbb{H\leq G} 当且仅当 \mathbb H 满足封闭性。
update on 2022.2.22：增加了“子集”的描述。之前写的时候漏掉了这一点，导致出现了很无厘头的定理。感谢 @1kri 的指出。
<u>性质</u>：子群之交仍是子群（由子群判定定理）。子群之并不一定是子群。
定理：任两个真子群的并均不可能得到母群。
Proof：
考虑 \mathbb{G=F\cup H}。
则必然存在 f\notin\mathbb F,h\notin\mathbb H（不然就不是真子群了）。
则必然有 f\in\mathbb H,h\in\mathbb F。
考虑 hf。
如 hf\in\mathbb F，则 h^{-1}hf\in{\mathbb F}，则 f\in\mathbb F，与前提相悖。同理可排除 hf\in{\mathbb H} 的场景。
V.群元素的阶
<u>定义</u>：群元素 a 的阶是满足 a^n=e 的最小正整数 n，记作 |a|。
必有 $|a|=|a^{-1}|$——这是简单得证的。由此可知阶大于 $2$ 的元素定有偶数个（阶为 $1$ 的元素唯一，即为幺元；阶为 $2$ 的元素自身与逆元相同且不为单位根，但可能不唯一；阶大于 $2$ 的元素自身与逆元不可能相同（否则阶就是 $2$），故其与其逆元一一对应），进而知偶数阶群必有 $2$ 阶元素。
<u>定理</u>：如 $a^m=e$，则 $m$ 是 $|a|$ 的整数倍。证明显然。
<u>定理</u>：$|a^k|=\dfrac{|a|}{\gcd(k,|a|)}$。
> Proof：
>
> 证明 $|a|=n$ 时，常用套路是先证 $a^n=e$，再证 $n$ 是最小的。
>
> 应用到本处时，前者显然，后者就用如果 $(a^k)^m=e$ 那么 $km$ 必是 $|a|$ 的倍数而这最小的 $m$ 即为上式值。
定理：对于元素 $a,b$，如 $|a|=m,|b|=n,ab=ba,\gcd(n,m)=1$，则 $|ab|=mn$。
> Proof：
>
> $(ab)^{mn}=e$ 显然。
>
> 如 $(ab)^r=e$，则 $(ab)^{rm}=e$，即 $b^{rm}=e$，这等价于 $n|rm$，又 $\gcd(n,m)=1$，则 $n|r$，则最小 $r$ 即为 $mn$。
定理：在交换群中，设所有元素的阶的最大值是非无穷大数 $m$，则所有元素的阶都必为 $m$ 的因数。
> Proof：
>
> 考虑反证。假设存在 $|a|=n$ 且 $n\nmid m$。则必存在一个质数 $p$，使得 $n$ 中 $p$ 的次数大于 $m$ 中 $p$ 的次数。
>
> 现设 $m$ 对应的元素是 $b$（即 $|b|=m$）。
>
> 不妨令 $n=p^Nn',m=p^Mm'$，则应有 $N>M$。则 $|b^{p^M}|=\dfrac{m}{\gcd(p^M,m)}=m',|a^{n'}|=p^N$。
>
> 交换群、互质，上一个定理的条件齐全，得到 $|b^{p^M}a^{n'}|=m'p^N$。因为 $N>M$，所以 $m'p^N>m$，与 $m$ 是最大阶的前提矛盾。
## VI.特殊群
定义：所有元素的阶有限的群被称作**周期群**，亦称**挠群**。
> 闲话一句：这里的“挠群”听上去有些怪，但是其英文是 `torsion group`，翻译过来就是 `扭曲的群`。而“挠”字在汉语中除了“抓挠”的意思外，也有“扭曲”的意思，如“不屈不挠”。
>
> 我觉得起这个名称纯粹是因为“扭曲群”这种翻译太怪了。
>
> 接下来我会一直称其为挠群，因为周期群容易和下面介绍的循环群混淆。
例：模质数意义下某数的所有次幂与乘法构成的群是挠群。
定义：除 $e$ 外其余元素的阶无限的群被称作**无扭群**。（扭起来了扭起来了）
例：$(\Z,+)$。
定义：非周期群且非无扭群的群为**混合群**。
有限群周期性定理：有限群必是挠群。
> Proof：$a$ 的次幂必成环，否则显然群不可能有限。
>
> 顺带提一句，这并不意味着无限群就一定不是挠群，典型例子如令 $\Omega_i$ 表示 $i$ 次单位根全集，则全体 $\Omega_i$ 的并集是挠群。
定义：若 $\mathbb S$ 是某群的非空真子集，则**尖括号** $\left<\mathbb S\right>$ 表示所有包含 $\mathbb S$ 的子群中大小最小的一个，换句话说就是 $\mathbb S$ 中所有元素不断进行 $\cdot$ 操作直到满足封闭性时得到的子群。
<u>定义</u>：某元素 $a$ 的所有整数幂次构成的集合与 $\cdot$ 运算构成的群称作**循环群**，而 $a$ 为该循环群的**生成元**。显然，循环群总有 $\left<\{a\}\right>$ 的形式。
定理：循环群必是交换群。这是显然的。
定理：如 $\left<\{a\}\right>$ 是无限群，则 $|a|=+\infty$。这可以轻松反证。
<u>定理</u>：如 $\left<\{a\}\right>$ 是有限群，则 $|a|=|\left<\{a\}\right>|$。这个式子看上去很怪，事实上其左边是群元素的阶，右边是群的阶。
> 这很显然，因为 $a$ 的次幂定是关于 $|a|$ 成环的。
<u>其逆定理</u>：$n$ 阶群是循环群当且仅当其中存在 $n$ 阶元素。
循环群结构定理：无限循环群同构于 $(\Z,+)$，有限循环群——设其阶为 $n$——同构于 $(\Omega_n,\times)$。
> 一对一映射是可能的，只需要找到循环群的生成元然后拿它去一一对应即可。
循环群生成元定理：无限循环群有两个生成元，其是同构于 $(\Z,+)$ 中 $-1,1$ 的元；有限循环群有 $\varphi(n)$ 个生成元。
循环子群定理：循环群的子群仍是循环群。
> Proof：不妨设母循环群其中一个生成元是 $a$。考虑将其子群中所有元素写成 $a^k$ 的形式并找到 $k$ 最小的一个。则因为是子群，所以所有 $a^{ik}$ 都在群中，其中 $i$ 是整数。如果还有其它 $a$ 的非 $ik$ 次幂在子群中，则恰大于其的一个 $ik$ 次幂与其逆元之积是一个 $a$ 的小于 $k$ 次幂，与 $k$ 是幂次最小的一个的前提相悖。则该子群是循环群，一个生成元是 $a^k$。
循环子群个数定理：无限循环群有无限多个子群；阶为 $n$ 的有限循环群有 $d(n)$ 个子群，其中 $d$ 是因数个数函数，且每个子群都是 $\left<a^k\right>$，其中 $k$ 是 $n$ 的某个因子。
> Proof：无限循环群情形显然。有限循环群下，考虑令 $n=pq$，则 $|a^q|=p$，故 $\left<a^q\right>$ 阶数为 $p$。考虑若 $\left<a^r\right>$ 阶数亦为 $p$，则 $|a^r|=p=\dfrac nq$。且有 $|a^r|=\dfrac{n}{\gcd(n,r)}$，则 $q=\gcd(n,r)=r$。
# II.变换群与置换群
## I.映射与同构初步
> 这部分是为了让定义严密而出现的，与群论关系不大
>
> 不了解这些东西不会对**本章**的**大部分**东西的理解产生影响，但是窃以为您会在读到 IV 章时后悔的。
<u>定义</u>：**映射**是将集合 $\mathbb A$ 中每个元素与集合 $\mathbb B$ 中每个元素建立对应关系的操作，记作 $\varphi:\mathbb{A\rightarrow B}$。这时，称 $\mathbb A$ 中元素是**原像/逆像**，与之对应的 $\mathbb B$ 中元素是**像**。称 $\mathbb A$ 是定义域，$\mathbb B$ 是值域。如果 $\mathbb A$ 中元素 $a$ 映射到了 $\mathbb B$ 中元素 $b$，这一关系记作 $a\mapsto b$。
在本文中，**希腊字母** $\varphi,\tau,\sigma$ 等是比较常见的映射表达方式。
<u>定义</u>：一个元素 $a$ 在映射 $\varphi$ 下产生的像亦可被记作 $\varphi(a)$。一个集合 $\mathbb G$ 在一个映射 $\varphi$ 下产生的所有像的集合被记作 $\varphi(\mathbb G)$。
> 这个定义以后还会改头换面再次出现。
<u>定义</u>：**单射**是 $\mathbb B$ 中每个元素最多是 $\mathbb A$ 中一个元素的像的映射，而**满射**则要求至少是 $\mathbb A$ 中一个元素的像。如果映射既单又满，则是**双射**。
<u>定义</u>：$\varphi^{-1}(b)$ 是元素 $b$ 所有原像构成的集合，**并不一定表示映射的逆**。同理有 $\varphi^{-1}(\mathbb B)$，表示 $\mathbb B$ 集合中所有元素的 $\varphi^{-1}$ 的并。
定理：向量空间对**同维度**向量空间的**线性**映射，如果是单射则亦是满射，如果是满射则亦是单射，换句话说就是只要单射满射至少满足一个就是双射。
> Proof：
>
> **向量空间**间**线性映射**可以由矩阵 $A$ 刻画。因为是同维度，所以 $A$ 是方阵。
>
> 如果是单射则方程 $A\mathbf x=\mathbf b$ 有至多一解，即 $A$ 的列线性无关，即 $A$ 的列空间等于全集，即 $A$ 满射。
>
> 如果是满射则方程 $A\mathbf x=\mathbf b$ 有至少一解，即 $\mathbf b$ 位于 $A$ 的列空间中，即 $A$ 的列空间等于全集，即 $A$ 的列线性无关，即 $A$ 可逆。那么求逆即可由 $\bf b$ 逆推出 $\bf x$，则是单射。
定理：**等大小有限集**间的映射同上，如果是单射则亦是满射，如果是满射则亦是单射，换句话说就是只要单射满射至少满足一个就是双射。
> 这很显然。
<u>定义</u>：映射的**复合**是先经历一种映射，再经历另一种映射后最终呈现的结果。这需要保证前一种映射的值域是后一种映射的定义域，这一点于矩阵乘法极其相似。用符号表示就是 $f\circ g$。这也可被称作变换之积。
<u>定义</u>：称两个群间的映射 $\varphi:\mathbb A\to\mathbb B$ 是**同态**的，当且仅当 $\forall a_1\mapsto b_1,a_2\mapsto b_2$，有 $a_1\cdot a_2\mapsto b_1\cdot b_2$。注意这里的两个 $\cdot$ 意义可能不同，因为其是分别定义在 $\mathbb{A,B}$ 两个群中的运算。
<u>定义</u>：对于同态映射 $\varphi$，如其是单射则是**单同态**，如其是满射则是**满同态**。
<u>定义</u>：如两个群间存在满同态（单纯是同态不行），则称其**同态**，记作 $\mathbb{G\sim H}$。如两个群间存在**双射同态**，则称其**同构**，记作 $\mathbb{G\cong H}$。
> update on 2023.8.6:
>
> 在写环论的过程中发现此处的纰漏，并修改了此处描述。现在此处的描述应该是最常见的描述。
## II.置换与置换群初步
定义：**变换**是**集合到自身的映射**。
<u>定义</u>：**置换**是**集合到自身的双射**。
> 这里大家可能有一个疑问：集合间的元素不应该是无序的吗，那么集合到自身的双射，结果难道不是定为集合本身吗？
>
> 确实是这样，但是这是因为侧重点错误。在研究置换时，不应该关注集合本身，而应该关注集合中的每个元素——只有对每个元素来说，置换才是有意义的。
**正规**的置换表达方式长得比较别致：对于一集合，如其可被表示为 $\{s_1,s_2,\dots,s_n\}$，其上的置换记作 $\begin{pmatrix}1&2&3&\dots&n\\p_1&p_2&p_3&\dots&p_n\end{pmatrix}$，第 $i$ 列的数字表示将元素 $s_i$ 映射到 $s_{p_i}$。但是光看到这个式子大家应该就能猜想到它究竟有多长多麻烦了，因此我们下文只记录第二行的内容，其构成一序列 $p$。
<u>定义</u>：因为置换首先是映射，所以**映射的复合**符号 $\circ$ 针对置换仍然成立。
<u>定义</u>：对于一个集合 $\mathbb S$ 上所有 $|\mathbb S|!$ 个置换所构成的集合 $\mathbb P$ 以及 $\circ$ 操作，它们构成一个群 $(\mathbb P,\circ)$，称作**对称群**，集合 $\mathbb A$ 上的对称群被记作 $\text S(\mathbb A)$。假如 $\mathbb A$ 是有限的且 $|\mathbb A|=n$，则 $\text S(\mathbb A)$ 被称作 **$n$ 次对称群**。
显然所有的 $n$ 次对称群都是同构的。因而，我们亦可记 $\text S_n$ 为任一 $n$ 次对称群。
定义：**单位置换**为所有元素都映射到其自身的置换。
<u>定义</u>：对称群的任意子群都被称作**置换群**。
**注意，按照定义，置换群中的所有置换的长度都须相同。如果不相同的话，就要使用置换群列的形式（如 $\mathbf G=\mathbb G_0+\mathbb G_1+\dots$）来定义。**
## III.置换群进阶
Cayley 定理：任意群都同构于一置换群。
> Proof：
>
> 设有一群 $\mathbb G$。现在有一个变换 $\tau_a:x\mapsto ax$，其中 $a,x\in\mathbb G$。
>
> 因为 $\mathbb G$ 是群，所以显然也有 $ax\in\mathbb G$。
>
> 显然这个变换是满射的，因为对于每个 $ax$ 只需要左乘 $a$ 的逆元就能得到与之对应的 $x$。
>
> 显然这个变换是单射的，因为左消去律在群中成立。
>
> 故这个变换是双射的，即其是置换。
>
> 考虑所有置换 $\tau_a$ 与变换复合运算 $\circ$ 构成的二元组。
>
> 显然其是封闭的：$\tau_a\circ\tau_b=\tau_{ab}$。
>
> 显然其是结合的，因为 $\circ$ 是结合的。
>
> 显然其有单位元，即为恒等变换 $\tau_e$。显然其有逆元，因为置换是双射所以其逆一定存在。
>
> 则该二元组是群。设其为 $\mathbb T$。
>
> 考虑构建映射 $\varphi:\mathbb{G\to T},a\mapsto \tau_a$。
>
> 显然该映射是双射。
>
> 显然映射前的 $\cdot$ 运算与映射后的 $\circ$ 运算等价。
>
> 则 $\mathbb{G,T}$ 同构。
定义：上述证明中给出的置换群 $\mathbb T$ 为群 $\mathbb G$ 上的**对称群** $\text S(\mathbb G)$。可以发现它与之前给出的集合上对称群有着相同的名称。
<u>定义</u>：**子置换**是母置换仅保留定义域中部分元素的映射的结果，并且让保留范围外的元素全都映射到其自身。
> “保留范围”这个术语不正规，但是我暂时找不到有相同意义的正规术语，那就暂且先这么用罢。
<u>定义</u>：**轮换/循环置换**是保留范围中无法再产生新的更小的子置换的子置换。换句话说，其保留范围中的映射首尾相接构成一个完整的环。$K$-轮换为保留范围大小为 $K$ 的轮换。
<u>定义</u>：**对换**为保留范围大小为 $2$ 的轮换，即 $2$-轮换。
<u>定义</u>：**不相交轮换**是保留范围无交的轮换。
<u>定理</u>：不相交轮换的复合存在交换律。
> 显然只有两不相交轮换的保留范围中的元素在复合中的结果是不平凡的。而它们的保留范围无交，故所有此中元素必经历一次平凡映射（到自身的映射）与一次非平凡映射。其结果必为该非平凡映射，且无论是先进行平凡映射还是先进行非平凡映射都是一样的。
定理：任一置换均可被表示为不相交轮换之积；任一轮换均可被表示为对换之复合。进而，任一置换均可表示为对换之复合。
定理：置换在分解为对换之复合时可能有多种分解方式，但是对换数量的**奇偶性**对于每个置换是固定的。
> 考虑把置换写成序列的形式。
>
> 每对换一次，显然序列的逆序对数会变化一，也即奇偶性会变化。
>
> 显然在分解为对换之复合时，我们可以再复合一个单位置换，其逆序对数为 $0$。
>
> 假设我们有一组合法的分解序列。考虑在其基础上通过增加或删除某些对换以得到其它分解序列。每增加或删除一个对换，序列逆序对数的奇偶性亦会翻转，这就意味着我们还需要再增加或删除一个对换以扳平逆序对数的奇偶性。
>
> 这就表示奇偶性是固定的。
定义：**奇置换**是上述奇偶性为奇的置换，**偶置换**则为偶。
定理：任一置换群，或者奇偶置换数量相同，或者全为偶置换。
> Proof：
>
> 奇偶置换之积的奇偶性同奇偶数之和的奇偶性类似，即有 $\text{奇}\times\text{奇}=\text{偶},\text{奇}\times\text{偶}=\text{奇},\text{偶}\times\text{偶}=\text{偶}$。则显然置换群中可以没有奇置换。
>
> 现假设群中有至少一个奇置换。则我们令群中所有元素全都左乘该奇置换得到了一个新结构，因为消去律存在所以该新结构中元素两两不同，又因为封闭性存在所以该新结构就是原群。而左乘的操作翻转了所有置换的奇偶性，所以便得到了该群中奇偶置换数量相同。
定义：**交代群/交错群**是 $\text S_n$ 中全部偶置换构成的子群。因为 $|\text S_n|=n!$，又按照上述定理其中奇偶数量相同，所以交代群的阶即为 $\dfrac{n!}2$。定义 $\text S_n$ 对应的交代群为 $\text A_n$，即 $n$ 次交代群。
定理：$K$-轮换的阶为 $K$；置换的阶为其拆分作的轮换之阶的最小公倍数。
> 前者显然。后者因为不相交轮换间乘法有交换律，所以 $\text{置换}^{\text{幂}}=\text{轮换之积}^{\text{幂}}=\text{轮换}^{\text{幂}}\text{之积}$，进而得到最小公倍数的结论。
# III.子群扩展
我们已经知道了子群的概念。本章将进一步揭示有关子群的更多内容。
## I.陪集初步
<u>定义</u>：群的**子集** $\mathbb H$ 与群中**元素** $a$ 的**左乘法** $a\mathbb H$ 表示集合 $\{ab|b\in\mathbb H\}$，同理有**右乘法** $\mathbb Ha$ 表示集合 $\{ba|b\in\mathbb H\}$。因为群中有结合律，所以可以有诸如 $abc\mathbb Hdef$ 这种记法，表示 $\mathbb H$ 左乘 $abc$ 后右乘 $def$（或者相反，但反正有结合律）。
现在我们有群 $\mathbb G$ 的一个子群 $\mathbb H$。
<u>定义</u>：$\mathbb H$ 关于 $\mathbb G$ 中元素 $a$ 的**左陪集**为集合 $\{ab|b\in\mathbb H\}$，即 $\mathbb H$ 中所有元素左乘 $a$ 构成的集合，按照上述结论即可记作 $a\mathbb H$。同理有**右陪集**，即右乘 $a$ 得到的集合，记作 $\mathbb Ha$。在 $\mathbb H$ 满足特殊性质使得左右陪集相同时，其还可被进一步合并为**陪集**。当然，就算 $\mathbb H$ 不满足该性质，用陪集作为左右陪集的合称也是合理的。
> 具体是什么性质呢？在 IV 章中就能见到了。
<u>定理</u>：某个 $\mathbb H$ 的所有左陪集的大小相同，都等于 $|\mathbb H|$。
> Proof：
>
> $\mathbb H$ 中所有元素左乘 $a$ 后显然仍两两不同，故 $|a\mathbb H|=|\mathbb H|$。
<u>定理</u>： $a\in\mathbb H\Leftrightarrow a\mathbb H=\mathbb H$。
> Proof：
>
> $\Rightarrow$：因为 $\mathbb H$ 是群，所以 $a\mathbb H$ 是 $\mathbb H$ 的**子集**。又由左消去律的逆否命题，$\mathbb H$ 中不相等的两个数在左乘 $a$ 后亦不可能相等，则 $|a\mathbb H|=|\mathbb H|$，即 $a\mathbb H=\mathbb H$。
>
> $\Leftarrow$：显然有 $a\in a\mathbb H$（由 $\mathbb H$ 中单位元得到），进而 $a\in\mathbb H$。
定理：$a\mathbb H$ 是群 $\Leftrightarrow a\in\mathbb H$。
> $\Leftarrow$：由上显然。
>
> $\Rightarrow$：群中必有单位元，单位元存在则必有 $a^{-1}\in\mathbb H$，进而有 $a\in\mathbb H$。
定义：关于 $\mathbb G$ 的子群 $\mathbb H$ 的**左同余关系** $\text R_\mathbb H$。对于 $a,b\in\mathbb G$，$a\operatorname R_\mathbb Hb$ 当且仅当 $a\mathbb H=b\mathbb H$。同理可以定理**右同余关系** $\overline{\text R}_\mathbb H$。左同余关系还可被记作 $a\equiv b\pmod{\mathbb H}$，同理有右同余关系的记法 $a\equiv_r b\pmod{\mathbb H}$。在 $\mathbb H$ 确定的时候也可以忽略 $\mathbb H$。
> Update on 2022.2.23：修改一处手癌。感谢 @1kri 指出。
定理：左同余关系间构成**等价类**，右同余同理。
> 因为左同余关系的实质是左陪集相等，而相等关系具有传递性，因而成等价类。
现在我们考虑这种等价类应该如何构造。
定理：$a\equiv b\pmod{\mathbb H}\Leftrightarrow b\in a\mathbb H$。
> Proof：
>
> $\Rightarrow$：显然 $b\in b\mathbb H$（由 $\mathbb H$ 中单位元得到），进而 $b\in a\mathbb H$。
>
> $\Leftarrow$：若 $b\in a\mathbb H$，则显然存在 $c\in\mathbb H$ 满足 $b=ac$。则 $b\mathbb H=(ac)\mathbb H\xlongequal{群上运算的结合律} a(c\mathbb H)\xlongequal{c\in\mathbb H\Leftrightarrow c\mathbb H=\mathbb H}a\mathbb H$，也即 $a\equiv b\pmod{\mathbb H}$。
<u>定理</u>：$a\equiv b\pmod{\mathbb H}\Leftrightarrow a^{-1}b\in\mathbb H\Leftrightarrow ab^{-1}\in\mathbb H$。
> Proof：
>
> 后一个等价符号只需交换 $a,b$ 即可由前一个等价符号证明。下只证前一个等价符号。
>
> 由前一个证明，$a\equiv b\pmod{\mathbb H}\Leftrightarrow b\in a\mathbb H$，则 $b\in a\mathbb H\Leftrightarrow b=ac,c\in\mathbb H\Leftrightarrow a^{-1}b\in\mathbb H$。
## II.陪集分解
<u>定理</u>：左陪集间要么等价，要么无交。
> Proof：
>
> 如 $a\mathbb H\cap b\mathbb H\neq\varnothing$，则设 $c\in(a\mathbb H\cap b\mathbb H)$，显然有 $c\in a\mathbb H,c\in b\mathbb H$，按照上面的定理则有 $a\equiv c\equiv b$，即左陪集有交等价于左陪集等价，逆否命题就是左陪集不等价等价于左陪集无交。
然后我们发现这些等价类具有很好的性质。
定理：对于母群 $\mathbb G$ 的任何子群 $\mathbb H$，其所有左陪集等价类包含了 $\mathbb G$ 中所有元素各恰一次。
> Proof：
>
> 各一次：显然 $a\in a\mathbb H$，则所有 $a\mathbb H$ 之并等于全集。
>
> 恰一次：显然等价类间不可能再等价，故它们只可能无交，则显然所有元素最多在一个等价类中出现。
由该定理，我们便可以给出一个定义。
定义：$\mathbb H$ 的所有左陪集等价类构成了 $\mathbb G$ **关于 $\mathbb H$ 的左陪集分解**。显然上述所有定理在右陪集时亦有效，故亦有**右陪集分解**。
定理：关于 $\mathbb H$ 的左右陪集分解间存在双射。
> Proof：
>
> 令左右陪集分解分别为 $\mathbb{L,R}$。
>
> 构造 $\varphi:\mathbb L\to\mathbb R,a\mathbb H\mapsto \mathbb Ha^{-1}$。显然其是双射。
推论：$\mathbb H$ 的左右陪集分解的大小相等。
## III.子群指数与拉格朗日定理
定义：$\mathbb H$ 的左陪集分解（由上述推论，右陪集亦可）的大小被称作 $\mathbb H$ 在 $\mathbb G$ 中的**指数**，记作 $(\mathbb G:\mathbb H)$。
<u>拉格朗日定理</u>：若 $\mathbb H$ 是 $\mathbb G$ 的子群，则 $|\mathbb H|$ 是 $|\mathbb G|$ 的因数。
> Proof：
>
> 首先，$\mathbb H$ 的所有陪集的大小相等，这个在以前就证过了。
>
> 其次，关于 $\mathbb H$ 的陪集分解中所有陪集无交且并为 $\mathbb G$。
>
> 这就直接得到了拉格朗日定理。
拉格朗日定理限制了子群的数目，让针对子群的讨论更加轻松了。
<u>定理</u>：有限群中每个元素的阶都整除群的阶。
> Proof：
>
> 首先我们在很久以前就证过了有限群中元素的阶非无穷。
>
> 那么我们令子群 $\mathbb H=\left<a\right>$，显然其阶就等于 $a$ 的阶。
>
> 依据拉格朗日定理，$|\mathbb H|$ 是 $|\mathbb G|$ 的因数，则 $|a|$ 是 $|\mathbb G|$ 的因数。
定理：阶为素数的群定为循环群且仅有平凡子群。
> Proof：
>
> 依据拉格朗日定理，此群的子群之阶只有可能为 $1$ 或该素数。
>
> 阶为 $1$ 的子群显然只可能仅包含单位元。阶为该素数的子群显然就是该群本身。
>
> 同理，群中元素的阶也仅可能为 $1$ 或该素数。显然阶为 $1$ 的元素仅可能为单位元。
>
> 故该有限群中存在阶等于该群的阶的元素。我们前面已经证过了，其为循环群。
定理：在有限群 $\mathbb G$ 中，如有 $\mathbb{F\leq H\leq G}$，则 $(\mathbb G:\mathbb H)(\mathbb H:\mathbb F)=(\mathbb G:\mathbb F)$。
> $(\mathbb G:\mathbb H)|\mathbb H|=|\mathbb G|$，然后就易证了。
# IV.群间运算与关系
## I.群同态进阶
我们已经知道了**同态**的基本概念，即**保持运算成立的映射**。
我们也有**群同态**的概念，即两群间存在同态关系。
我们也有**群同构**的概念，即两群间存在双射同态关系。
<u>定理</u>：满同态传递结合律。
> Proof：
>
> 设满同态映射为 $\varphi$。因为同态，故 $\varphi(a)\varphi(b)=\varphi(ab)$。
>
> 则有 $\Big(\varphi(a)\varphi(b)\Big)\varphi(c)=\varphi(ab)\varphi(c)=\varphi(abc)=\varphi(a)\varphi(bc)=\varphi(a)\Big(\varphi(b)\varphi(c)\Big)$。
>
> 因为是满同态，所以值域中任一元素均可被表示成至少一个 $\varphi(a)$ 的形式，进而该运算在其中满足结合律。
<u>群结构在满同态上的传递性定理</u>：与群 $\mathbb G$ 满同态的结构亦为群。
> Proof：
>
> 设该满同态映射为 $\varphi:\mathbb G\to\mathbb G'$。则因为同态，所以 $\varphi(a)\varphi(b)=\varphi(ab)$。
>
> 现验证群的各项要求：
>
> - 结合律，上方已证过。
> - 单位元。$\varphi(e)\varphi(a)=\varphi(ea)=\varphi(a)$。
> - 逆元。$\varphi(a^{-1})\varphi(a)=\varphi(a^{-1}a)=\varphi(e)$。
>
> 又因为是满同态，所以 $\mathbb G'$ 中任一元素均可被表示成至少一个 $\varphi(a)$ 的形式，进而满足其是群。
<u>定理</u>：设 $\varphi:\mathbb G\to\mathbb G'$ 是两群间的同态。设 $e,e'$ 分别是两群中的单位元。则有：
- $\varphi(e)=e'$。
- $\varphi(a^{-1})=\varphi(a)^{-1}$（注意这里的两个 $-1$ 是在不同群中的逆元）。
> Proof：
>
> 虽然 $\varphi$ 不是 $\mathbb G$ 与 $\mathbb G'$ 间的满同态，但定是 $\mathbb G$ 与 $\varphi(\mathbb G)$ 间的满同态。由群结构在满同态上的传递性定理，$\varphi(\mathbb G)$ 亦是群，则其是 $\mathbb G'$ 的子群。故上述两性质成立。
<u>定理</u>：设 $\varphi:\mathbb G\to\mathbb G'$ 是两群间的同态。对于 $\mathbb G$ 的子群 $\mathbb H$，$\varphi(\mathbb H)$ 亦是 $\mathbb G'$ 的子群，反之亦然（即 $\varphi(\mathbb H)$ 是 $\mathbb G'$ 的子群可推出 $\mathbb H$ 是 $\mathbb G$ 的子群）。
> Proof：
>
> $\Rightarrow$：因为在 $\mathbb H$ 上的 $\varphi$ 是满射，且 $\mathbb H$ 是群，则 $\varphi$ 在 $\mathbb H$ 上是满同态，进而由群结构在满同态上的传递性定理，$\varphi(\mathbb H)$ 亦是群，则其是 $\mathbb G'$ 的子群。
>
> $\Leftarrow$：由上个定理，$\mathbb H$ 中有逆元和单位元，且可证得对于 $\varphi(a),\varphi(b)\in\mathbb \varphi(\mathbb H)$，总有 $a^{-1}b\in\mathbb H$，进而有封闭性，进而是群。
<u>定理</u>：群同态是单同态当且仅当 $e'$ 的原像唯一。
> Proof：
>
> 必要性显然。
>
> 充分性：若 $\varphi(a)=\varphi(b)$，则 $\varphi(a^{-1})\varphi(b)=\varphi(a)^{-1}\varphi(b)=e'$，若原像唯一（显然此时其仅可能为 $e$）则可得到 $a^{-1}b=e$，即 $a=b$。
## II.积
定义：两个群 $\mathbb{G,H}$ 的**直积**为一个新群 $\mathbb F=\Big\{(g,h):g\in\mathbb G,h\in\mathbb H\Big\}$，即 $\mathbb G$ 中所有元素与 $\mathbb H$ 中所有元素构成的**有序二元组**构成的群。$\mathbb F$ 中的运算被定义为二元组的每一元分别进行对应群中的 $\cdot$ 操作。符号记作 $\mathbb G\times\mathbb H=\mathbb F$，或者简洁记作 $\mathbb{GH=F}$。
聪明的读者一定已经发现了，我们的直积好像与集合论中的**笛卡尔积**长得很像。事实上，直积只不过是笛卡尔积在群论方面的另一种称呼。~~为了少打两个字~~，我们将继续用直积称呼这种运算，或者直接粗暴地叫它“积”。
<u>定义</u>：某群 $\mathbb G$ 的两个子群 $\mathbb{F,H}$ 的**子群积**为一个新**集合** $\mathbb D=\Big\{fh:f\in\mathbb F,h\in\mathbb H\Big\}$。**注意这里特别标明是集合而不是群，原因接下来会提到。**
> 子群积也大量、普遍、泛用地被叫做“积”，符号同样是 $\mathbb D=\mathbb F\times\mathbb H$，并同样可以被省略乘号。也就是说，它与直积在符号上区分不开。但是，一般都可以简单判定到底是哪种积。
<u>子群积的等价定义</u>：$\mathbb D=\bigcup\limits_{f\in\mathbb F}f\mathbb H=\bigcup\limits_{h\in\mathbb H}\mathbb Fh$。
<u>扩展定义</u>：定义子群积不仅可以作用于两个子群间，亦可以作用于两个子集间，此时定义同上。
显然子群积是左右乘法的扩展：在形如 $a\mathbb H$ 的左乘法上，亦可以把 $a$ 看作是元素只有 $a$ 一个的子集，右乘法同理。
<u>定理</u>：子群积与左右乘法间存在结合律。
> 只需展开子群积即可。
性质：子群积**不一定**是子群，就算其乘号两边都是子群。
> Counterexample：
>
> 设有两个矩阵 $A,B$ 满足 $A^2=I,B^2=I,A\neq B$。现考虑它们生成的群 $\left<A,B\right>$。$\{I,A\}\times\{I,B\}=\{I,A,B,AB\}$，其并非 $\left<A,B\right>$ 的子群，因为 $BA$ 不在其中。
定理：如 $\mathbb{FH=D}$，则 $\mathbb{F\subseteq D,H\subseteq D}$。
> 注意到这里用的是**子集符号** $\subseteq$ 而非**子群符号** $\leq$，原因是 $\mathbb{F,H}$ 不一定是群，再大大咧咧地用群的符号好像不太对劲。
>
> 证明显然，因为只需要考虑乘上的是单位元即可。
定理：设 $\mathbb{F,H}$ 为 $\mathbb G$ 的**有限**子群。则 $|\mathbb{FH}|=\dfrac{|\mathbb F||\mathbb H|}{|\mathbb F\cap\mathbb H|}$。
> Proof：
>
> 显然 $\mathbb{F\cap H}$ 是 $\mathbb F$ 的子群，进而有 $\mathbb F$ 关于 $\mathbb{F\cap H}$ 的左陪集分解：$\mathbb F=\bigcup\limits_{f_i\in\mathbb F}f_i(\mathbb{F\cap H})$。显然 $f_i$ 的个数即为 $\mathbb{\dfrac{|F|}{|F\cap H|}}$。
>
> 显然 $\mathbb H\subseteq\mathbb{FH}\subseteq\mathbb G$。进而定可构造出 $\mathbb{FH}=\bigcup\limits_{h_i\in\mathbb F}h_i\mathbb H$，因为显然全体 $\mathbb F$ 中元素即为一组合法的 $h$。因为显然 $h_i\mathbb H$ 中亦有等价类存在且不同等价类中的元素无交，故我们仍可对于每个等价类仅保留一个元素。但注意这并非左陪集分解，因为 $\mathbb{FH}$ 甚至连群都不是。
>
> 显然 $h$ 仅取 $\mathbb F$ 中元素是可行的。考虑什么样的 $h$ 是合法的 $h$。$h_i\mathbb H=h_j\mathbb H\Leftrightarrow h_ih_j^{-1}\in\mathbb H$。又 $h_i,h_j\in\mathbb F$，则 $h_ih_j^{-1}\in\mathbb F$，则 $h_ih_j^{-1}\in\mathbb{F\cap H}$，则 $f_i(\mathbb{F\cap H})=f_j(\mathbb{F\cap H})$。这条性质反过来仍然可推证。故 $h_i\mathbb H=h_j\mathbb H\Leftrightarrow f_i(\mathbb{F\cap H})=f_j(\mathbb{F\cap H})$。这说明全体 $f$ 即为一组合法的 $h$。
>
> 则 $f_i$ 的个数就等于 $h_i$ 的个数，即 $\mathbb{\dfrac{|F|}{|F\cap H|}}$。然后每个 $h_i\mathbb H$ 的大小显然都是 $|\mathbb H|$，故得出 $|\mathbb{FH}|=\dfrac{|\mathbb F||\mathbb H|}{|\mathbb F\cap\mathbb H|}$。
## III.正规子群
<u>定义</u>：**正规子群**是每对左右陪集全部相同的子群，即满足 $\forall a\in\mathbb G,a\mathbb H=\mathbb Ha$ 的子群。如果 $\mathbb H$ 是 $\mathbb G$ 的正规子群，可记作 $\mathbb H\unlhd\mathbb G$。显然两个平凡子群必为正规子群，故将两个形容词合并，叫做**平凡正规子群**。其它正规子群同理，为**非平凡正规子群**。同理，既是真子群又是正规子群的子群为**真正规子群**，记作 $\mathbb H\lhd\mathbb G$。
定义：**单群**是阶非一且仅有平凡正规子群的群。
> Update on 2022.2.21：删除“正规子群的子群仍是正规子群”这一定理。这里写的时候还不太理解，导致我想当然了。感谢 @chenxia25 指出。希望大家多多指正，多多挑错，让这篇文章变得更加严谨。
定理：指数为 $2$ 的子群定是正规子群。
> Proof：
>
> 指数为 $2$ 表明其左/右陪集分解的大小都为 $2$。而因为陪集分解中必然包括该子群本身（关于该子群内部元素的陪集），所以分解中另一个陪集必然是该子群的补集，并且该补集在左右分解中都是相同的。故而，此时的左右陪集分解是相同的，因而是正规子群。
<u>正规子群判定定理</u>：子群 $\mathbb H\unlhd\mathbb G\Leftrightarrow\forall(g\in\mathbb G,h\in\mathbb H),ghg^{-1}\in\mathbb H$。
> Proof：
>
> $\forall a\in\mathbb G,a\mathbb H=\mathbb Ha$，此式是正规子群的定义。
>
> 因为有结合律，所以上式等价于 $\forall a\in\mathbb G,a\mathbb Ha^{-1}=\mathbb H$。
>
> 因为左右消去律在群中存在，所以只需要证明所有 $aba^{-1}\in\mathbb H$ 即可，其中 $b\in\mathbb H$。
>
> 而这就是上式。
<u>正规子群在满同态上的传递性定理</u>：对于满同态 $\varphi:\mathbb G\to\mathbb G'$，$\mathbb H\unlhd\mathbb G\Leftrightarrow\varphi(\mathbb H')\unlhd\mathbb G'$。
> Proof：
>
> 首先我们前面已经证过了如 $\mathbb H$ 是子群则 $\varphi(\mathbb H)$ 亦是子群，反之亦然。
>
> 然后，在同态群上显然有 $aba^{-1}=\varphi(a)\varphi(b)\varphi(a)^{-1}$。
>
> 上面的性质在**常规同态**上也是成立的；但是正规子群还要求是**满同态**，就是因为常规同态下仅保证 $\varphi(\mathbb G)\leq\mathbb G'$，这意味着有一些 $\mathbb G'$ 中元素可能不存在原像，进而在 $aba^{-1}=\varphi(a)\varphi(b)\varphi(a)^{-1}$ 一式中找不到对应的 $a$，以至于上式可能不成立。然而在满同态上每个 $\mathbb G'$ 中元素都有原像，进而上式必然成立。
<u>定理</u>：正规子群与常规子群的子群积仍是子群。
> Proof：
>
> 设 $\mathbb D=\mathbb{FH}=\bigcup\limits_{f\in\mathbb F}f\mathbb H$，并且 $\mathbb F$ 是常规子群、$\mathbb H$ 是正规子群。
>
> 应用子群判定定理，只需证明 $\forall(f_1,f_2\in\mathbb F,h_1,h_2\in\mathbb H),f_1h_1(f_2h_2)^{-1}\in\mathbb D$ 即可。
>
> $(f_2h_2)^{-1}=h_2^{-1}f_2^{-1}$。则 $f_1h_1(f_2h_2)^{-1}=f_1h_1h_2^{-1}f_2^{-1}$。
>
> 显然有 $h_1h_2^{-1}\in\mathbb H$，则设其为 $h$。则有上式等于 $f_1hf_2^{-1}$。
>
> 显然有 $f_1h\in f_1\mathbb H=\mathbb Hf_1$，即 $f_1h$ 定可被表示成 $h_3f_3$ 的形式。
>
> 上式等于 $h_3f_3f_2^{-1}$。显然 $f_3f_2^{-1}\in\mathbb F$，故设其为 $f$。
>
> 则上式等于 $h_3f$。显然有 $h_3f\in\mathbb Hf=f\mathbb H$，即 $h_3f\in\mathbb D$，即 $f_1h_1(f_2h_2)^{-1}\in\mathbb D$。
>
> 证毕。
<u>定理</u>：正规子群与正规子群的子群积仍是正规子群。
> Proof：
>
> 设 $\mathbb D=\mathbb{FH}=\bigcup\limits_{f\in\mathbb F}f\mathbb H$，并且 $\mathbb{F,H}$ 均是正规子群。
>
> 首先 $\mathbb D$ 是母群 $\mathbb G$ 的子群。
>
> 然后即证 $\forall(g\in\mathbb G,d\in\mathbb D),gdg^{-1}\in\mathbb D$。
>
> 显然 $d=fh=fg^{-1}gh$。则要证 $gfg^{-1}ghg^{-1}\in\mathbb D$。显然 $gfg^{-1}\in\mathbb F$，$ghg^{-1}\in\mathbb H$。则上式可表示成 $f'h'\in\mathbb D$，而这个式子即是 $\mathbb D$ 的定义。
<u>定理</u>：正规子群与正规子群的交仍是正规子群。
> 这是显然的。
正规化子是衡量一个子群到底有多“相近”于正规子群的工具。
定义：群 $\mathbb G$ 的子集 $\mathbb S$ 的**正规化子**是所有满足 $x\mathbb S=\mathbb Sx$ 的元素构成的集合，记作 $\text N(\mathbb S)$。
定理：对于 $\mathbb{H\leq G}$，必有 $\mathbb H\unlhd\text N(\mathbb H)\leq\mathbb G$。
> Proof：
>
> - $\text N(\mathbb H)\leq\mathbb G$。
>
> 首先显然有 $\text N(\mathbb H)\subseteq\mathbb G$。
>
> 然后用子群判定定理，即证 $\forall a,b\in\text N(\mathbb H),ab^{-1}\in\text N(\mathbb H)$。
>
> 显然 $a\mathbb Ha^{-1}=\mathbb H,b\mathbb Hb^{-1}=\mathbb H$。则证 $ab^{-1}\mathbb H(ab^{-1})^{-1}=\mathbb H$。
>
> $ab^{-1}\mathbb H(ab^{-1})^{-1}=ab^{-1}\mathbb Hba^{-1}=a\mathbb Ha^{-1}=\mathbb H$。
>
> - $\mathbb H\unlhd\text N(\mathbb H)$。直接用正规子群的定义即可。
## IV.商
<u>定理</u>：正规子群的所有陪集构成的集合关于陪集间的子群积成群。
> Proof：
>
> 设有正规子群 $\mathbb H$。则 $(a\mathbb H)(b\mathbb H)=a(\mathbb Hb)\mathbb H=a(b\mathbb H)\mathbb H=(ab)\mathbb H$。（子群积间存在结合律；一个群与其自身的子群积只会得到其自身）。
>
> 则可建立满射 $\varphi:a\mapsto a\mathbb H$。易证该满射是同态，即陪集构成的集合满同态于母群。因为满同态传递群结构，所以陪集构成的集合成群。
>
> 记住这个映射，它会多次出现。
<u>定义</u>：上述群被称作 $\mathbb G$ 关于 $\mathbb H$ 的**商群**，记作 $\mathbb G/\mathbb H$ 或 $\mathbb{\dfrac GH}$。在本文中一般用 $\mathbb G/\mathbb H$ 的场景比较多。按照我们上文的证明，存在满同态 $\varphi:\mathbb G\to\mathbb G/\mathbb H$。
<u>推论</u>：如 $\mathbb G$ 是有限群，则 $|\mathbb G/\mathbb H|=(\mathbb G:\mathbb H)=\dfrac{|\mathbb G|}{|\mathbb H|}$。
定理：如 $\mathbb G$ 是交换群，则 $\mathbb{G/H}$ 亦是交换群。
> 易证满同态传递交换律。
Cauchy 定理：若有有限交换群 $\mathbb G$，则对于所有 $|\mathbb G|$ 的质因子 $p$ 来说，$\mathbb G$ 中定有 $p$ 阶元素，进而定有 $p$ 阶子群。
> Proof：
>
> 设 $|\mathbb G|=pn$。现对每个 $p$ 来说，对于 $n$ 用归纳法。
>
> 显然当 $n=1$ 时 Cauchy 定理成立。
>
> 现设对于一切 $k<n$ 的 $k$ 来说 Cauchy 定理均成立，下证 Cauchy 定理在阶为 $pn$ 时亦成立。
>
> 取 $|\mathbb G|$ 中任一非单位元元素 $a$。
>
> - $|a|$ 是 $p$ 的倍数。设为 $s$ 倍，则 $|a^s|=\dfrac{|a|}{\gcd(s,|a|)}=p$。
>
> - $|a|$ 非 $p$ 的倍数，则设其为 $m$。显然应有 $\gcd(m,p)=1$。而由 Lagrange 定理的直接推论——群中元素的阶整除群的阶，则有 $m|pn$，进而 $m|n$。
>
> 现构造子群 $\mathbb H=\left<a\right>$，则显然 $|\mathbb H|=|a|=m$。因为 $\mathbb G$ 是交换群，所以 $\mathbb H$ 必是正规子群，进而存在商群 $\mathbb G/\mathbb H$，且 $|\mathbb G/\mathbb H|=\dfrac{pn}{m}$。因为 $a$ 非单位元，则 $m>2$，则 $\dfrac nm<n$，由归纳假设 $\mathbb G/\mathbb H$ 中存在 $p$ 阶元 $b\mathbb H$。令 $|b|=r$，则 $(b\mathbb H)^r=b^r\mathbb H=\mathbb H$。因为 $b\mathbb H$ 的阶是 $p$，所以理应有 $p|r$。则可令 $r=pt$，则 $|b^t|=p$。
推论：有限交换群是单群当且仅当其阶为素数。
> 是不是已经忘记单群是什么了？重申一遍，单群是只有平凡正规子群的群。
## V.群同态深入
<u>定义</u>：设群同态 $\varphi:\mathbb G\rightarrow\mathbb G'$。$\mathbb G'$ 的单位元在 $\varphi$ 下的所有原像的集合称为 $\varphi$ 的**核**，记作 $\ker\varphi$。
> 也有大写的 $\text{Ker}$ 记法。
<u>定理</u>：$\ker\varphi$ 是 $\mathbb G$ 的正规子群。
> $\ker\varphi$ 中元素关于交换律成立的哦。
<u>定义</u>：设群同态 $\varphi:\mathbb G\rightarrow\mathbb G'$。$\mathbb G$ 的所有元素在 $\varphi$ 下的所有像的集合称为 $\varphi$ 的**像集**，记作 $\Im\varphi$。
> 有没有发现这个定义有些熟悉？没错，它就是 $\varphi(\mathbb G)$。
<u>定理</u>：$\Im\varphi$ 是 $\mathbb G'$ 的子群。
> $\varphi':\mathbb G\rightarrow\Im\varphi$ 显然是满同态，依照我们之前证过的，满同态传递群形态。
<u>定义</u>：**自然同态**是群和商群间的同态。
> 这个同态具体是什么？它实际上在我们给出商群的定义的时候就一带给出了！假如 $\mathbb H\unlhd\mathbb G$，则同态 $\tau:\mathbb G\mapsto{\mathbb G/\mathbb H},a\mapsto a\mathbb H$ 就是自然同态。
<u>定理</u>：对于自然同态 $\tau:\mathbb G\mapsto{\mathbb G/\mathbb H},a\mapsto a\mathbb H$，有 $\ker\tau=\mathbb H$。
> $\mathbb{G/H}$ 的单位元显然是 $\mathbb H$，而映到 $\mathbb H$ 的所有元素即为所有 $\mathbb H$ 中元素。
接下来的定理的名称有亿点点不统一，暂按照 wiki 上的解释命名。
<u>第一同构定理</u>：对群同态 $\varphi:\mathbb G\to\mathbb G'$，$\mathbb G/\ker\varphi\cong\Im\varphi$。
> Proof：
>
> 可以构造映射 $\sigma:\mathbb G/\ker\varphi\to\mathbb \Im\varphi,a\ker\varphi\mapsto\varphi(a)$。
>
> - $\sigma$ 是同态。这很显然，因为 $\tau(a\ker\varphi)\tau(b\ker\varphi)=\varphi(a) \varphi(b)=\varphi(ab)=\tau(ab\ker\varphi)$。
> - $\sigma$ 是单射。$a\ker\varphi=b\ker\varphi\Leftrightarrow a^{-1}b\in\ker\varphi\Leftrightarrow\varphi(a^{-1}b)=\varphi(e)$。而显然 $\mathbb G/\ker\varphi$ 中所有的 $a\ker\varphi$ 都两两不同，故 $\varphi(e)$ 的原像只可能在 $a\ker\varphi=b\ker\varphi$ 即 $a^{-1}b=e$ 时产生，则 $\varphi(e)$ 的原像仅有 $e\ker\varphi$ 一个。我们之前证过，因为 $\varphi(e)$ 是 $\Im\varphi$ 上的单位元，所以其原像唯一即等价于 $\sigma$ 是单射。
> - $\sigma$ 是满射。 对于任何 $a'\in\Im\varphi$，显然必存在 $a$ 满足 $\varphi(a)=a'$。则在 $\sigma$ 中 $a\ker\varphi$ 必映射到 $a'$。
>
> 又单又满的同态就是同构。
推论：对于存在满同态的两个群 $\mathbb G\to\mathbb G'$，必有 $|\mathbb G'|$ 是 $|\mathbb G|$ 的因子。
定理：循环群的像也是循环群。
> 显然生成元的像亦为生成元。
<u>定理</u>：满同态 $\varphi:\mathbb G\to\mathbb G'$。若 $\ker\varphi\leq\mathbb H\unlhd\mathbb G$，且 $\varphi(\mathbb H)=\mathbb H'$，则 $\mathbb{G/H}\cong\mathbb{G'/H'}$。
> Proof：
>
> 依据正规子群在满同态上传递定理，有 $\mathbb H'$ 亦为正规子群。
>
> 定义 $\tau:\mathbb{G/H}\to\mathbb{G'/H'},a\mathbb H\mapsto\varphi(a)\mathbb H'$。
>
> - 是映射且是单射（即原像相同等价于像相同）。
>
> 下式中所有式从上到下依次等价。
> $$
> \begin{matrix}\tau(a\mathbb H)=\tau(b\mathbb H)\\\varphi(a)\mathbb H'=\varphi(b)\mathbb H'\\\varphi(a)\varphi(b)^{-1}\in\mathbb H'\\\varphi(ab^{-1})\in\mathbb H'\\\exists c\in\mathbb H\text{ s.t. }\varphi(c)=\varphi(ab^{-1})\\\varphi(ab^{-1}c^{-1})=\varphi(e)=e'\\ ab^{-1}c^{-1}\in\ker\varphi\leq\mathbb H\\ab^{-1}\in\mathbb H\\a\mathbb H=b\mathbb H\end{matrix}
> $$
>
> - 是同态。$\tau(a\mathbb Hb\mathbb H)=\tau(ab\mathbb H)=\varphi(ab)\mathbb H'=\varphi(a)\varphi(b)\mathbb H'=\varphi(a)\mathbb H'\varphi(b)\mathbb H'=\tau(a\mathbb H)\tau(b\mathbb H)$。
>
> - 是满射。显然因为 $\varphi$ 是满射，所以对于每个 $a'\in\mathbb G'$ 均可找到满足 $\varphi(a)=a'$ 的 $a$。则显然对于 $\mathbb{G'/H'}$ 中的每个元素亦可找到其原像。
第三同构定理：如 $\mathbb F\leq\mathbb H\unlhd\mathbb G$（我们证过此时 $\mathbb F$ 同时是 $\mathbb G$ 与 $\mathbb H$ 的正规子群），则 $\mathbb{G/H\cong(G/F)/(H/F)}$。
> Proof：
>
> 首先要证明 $\mathbb{H/F}$ 是 $\mathbb{G/F}$ 的正规子群，即 $\forall(g\mathbb F\in\mathbb{G/F},h\mathbb F\in\mathbb{H/F}),(g\mathbb F)(h\mathbb F)(g\mathbb F)^{-1}\in\mathbb{H/F}$。首先可以乱交换左右陪集得到要证式子 $ghg^{-1}\mathbb F\in\mathbb{H/F}$，即证 $ghg^{-1}\mathbb F\in\mathbb H$，而该条件等价于 $\mathbb H\unlhd\mathbb G$。
>
> 现可构造自然同态 $\tau:\mathbb G\to\mathbb{G/F}$。我们证过自然同态的核即为 $\mathbb F$，且有 $\tau(\mathbb H)=\mathbb{H/F}$。套用前一个定理即证。
第二同构定理：设 $\mathbb G$ 有子群 $\mathbb H$ 和正规子群 $\mathbb F$。则 $\mathbb{HF/F\cong H/(H\cap F)}$。
> 首先，$\mathbb F$ 定是 $\mathbb{HF}$ 的正规子群，因为 $\mathbb{HF}$ 是 $\mathbb G$ 的子群。
>
> 其次也定有 $\mathbb{H\cap F\unlhd H}$。
>
> 构造映射 $\varphi:\mathbb{H\to HF/F},h\mapsto h\mathbb F$。该映射是同态，因为其是自然同态消减定义域的结果。同时其也是满同态，因为对于 $hf\in\mathbb{HF}$，总有 $hf\mathbb F=h\mathbb F$，即消减定义域后值域并没有改变。
>
> 显然 $\ker\varphi$ 中的元素应是 $\mathbb F$ 中元素。而其又是 $\mathbb H$ 中元素，所以其为 $\mathbb{H\cup F}$ 中元素。
>
> 那么结构就和再前一个定理并无不同了。
<u>定理</u>：设有群同态 $\varphi:\mathbb G\to\mathbb G'$。如果有 $\ker\varphi\leq\mathbb H\leq\mathbb G$，则 $\varphi(\mathbb H)$ 的原像集合 $\varphi^{-1}(\varphi(\mathbb H))$ 即为 $\mathbb H$。（换句话说，没有 $\mathbb H$ 外元素映到 $\varphi(\mathbb H)$ 中）
> Proof：
>
> 显然 $\mathbb H\subseteq\varphi^{-1}(\varphi(\mathbb H))$。
>
> 显然 $\forall a\in\varphi^{-1}(\varphi(\mathbb H)),\varphi(a)\in\varphi(\mathbb H)$。
>
> 则 $\exists b\in\mathbb H,\varphi(a)=\varphi(b)$，则 $\varphi(ab^{-1})=\varphi(e)$，也即 $ab^{-1}\in\ker\varphi\leq\mathbb H$，也即 $a\in\mathbb H$。
>
> 这意味着 $\mathbb H\supseteq\varphi^{-1}(\varphi(\mathbb H))$。两者结合即为 $\mathbb H=\varphi^{-1}(\varphi(\mathbb H))$。
子群对应定理：设有满同态 $\varphi:\mathbb G\to\mathbb G'$。则集合 $\mathbb M=\{\mathbb H:\ker\varphi\leq\mathbb H\leq\mathbb G\}$ 与集合 $\mathbb M'=\{\mathbb H':\mathbb H'\leq\mathbb G'\}$ 间存在双射，且该双射保持包含关系。
> Proof：
>
> 构造 $\sigma:\mathbb H\mapsto\varphi(\mathbb H)$。由满同态传递群结构得知，$\varphi(\mathbb G)\leq\mathbb G'$。进而可有 $\sigma:\mathbb{M\to M'}$。
>
> 由前一条定理，$\sigma$ 是单射（像相同可推出原像相同）。
>
> 对于 $\mathbb M'$ 中所有元素 $\mathbb H'$，考虑其原像集合 $\varphi^{-1}(\mathbb H')$。显然其中必然包含 $\ker\varphi$（其是 $e'$ 的所有逆——显然 $e'$ 必在一切 $\mathbb H'$ 中），即其原像集合必然属于 $\mathbb M$。则 $\sigma$ 是满射。
>
> 则 $\sigma$ 是双射。
>
> 显然其亦保持包含关系。
第三/四同构定理/Correspondence theorem（wiki 词条）：设 $\mathbb{N\unlhd G}$，则集合 $\mathbb M=\{\mathbb H:\mathbb N\leq\mathbb H\leq\mathbb G\}$ 与集合 $\mathbb M':\{\mathbb H'\leq\mathbb{G/N}\}$ 间存在双射，且该双射保持包含关系。
> wiki 说该定理有时被叫做第三或第四同构定理。
>
> 在子群对应定理中令 $\varphi$ 为自然同态 $\tau:\mathbb G\to\mathbb{G/N}$ 即证。
Zassenhaus 引理/蝴蝶引理/第四同构定理：设 $\mathbb{A\unlhd A'\leq G,B\unlhd B'\leq G}$。则：
$$\mathbb{\dfrac{A(A'\cap B')}{A(A'\cap B)}\cong\dfrac{(A'\cap B')B}{(A\cap B')B}}$$
> wiki 说该定理有时被叫做第四同构定理。~~众所周知，四大同构定理有五个~~。
>
> 可以发现本定理具有特殊的韵律感。因而有人形象地把它称作“蝴蝶引理”。
>
> Proof：
>
> 首先 $\mathbb{(A'\cap B)\leq G}$（子群交是子群）。这样之后 $\mathbb{(A'\cap B)\leq A'}\leq\text N(\mathbb A)$。这就意味着 $\mathbb{(A'\cap B)A}=\sum\limits_{x\in\mathbb{(A'\cap B)}}x\mathbb A=\sum\limits_{x\in\mathbb{(A'\cap B)}}\mathbb Ax=\mathbb{A(A'\cap B)}$，即二者的子群积满足交换律。显然同样的交换律在该定理中出现的四个子群积中均成立。
>
> 满足交换律的子群积的结果仍是子群，因为我们在证明“正规子群与子群的积结果仍是子群”时，仅用到了两者间的交换律，可以回翻到该定理的证明处复习。
>
> 故我们证明了该定理中出现的四个子群积的结果都是子群。可喜可贺可喜可贺（
>
> 式子 $\mathbb{(A'\cap B)\unlhd(A'\cap B')}$ 是我们下一个证明的目标。由正规子群判定定理，即证 $\forall x\in\mathbb{(A'\cap B')},y\in\mathbb{(A'\cap B)}$，有 $xyx^{-1}\in\mathbb{(A'\cap B)}$。显然 $x,y\in\mathbb A'$，故 $xyx^{-1}\in\mathbb A'$；因为 $\mathbb{B\unlhd B'}$，而 $x\in\mathbb B',y\in\mathbb B$，则 $xyx^{-1}\in\mathbb B$；两者结合，上式成立。
>
> 式子 $\mathbb{A(A'\cap B)\unlhd A(A'\cap B')}$ 是我们再下一个证明的目标。即证 $\forall a,c\in\mathbb A,b\in(\mathbb{A'\cap B’}),d\in(\mathbb{A'\cap B})$，有 $abcd(ab)^{-1}\in\mathbb A(\mathbb{A'\cap B})$。上式写成 $abcdb^{-1}a^{-1}$ 没有问题。
>
> 一个比较棒的想法是将其转成 $a(bcb^{-1})(bdb^{-1})a^{-1}$ 的形式。然后因为 $\mathbb{A\unlhd A'}$ 且 $b\in(\mathbb{A'\cap B’})\leq\mathbb A'$ 且 $c\in\mathbb A$ 所以即可写成 $ac'(bdb^{-1})a^{-1}$，其中 $c'\in\mathbb A$；同理 $d$ 亦可被转成 $d'=bdb^{-1}$：因为 $\mathbb{B\unlhd B'}$ 且 $d\in(\mathbb{A'\cap B})\leq\mathbb B$ 且 $b\in(\mathbb{A'\cap B’})\leq\mathbb B'$ 则得 $d'\in\mathbb B$，因为 $b,d\in\mathbb A'$ 则得 $d'\in\mathbb A'$，所以 $d'\in(\mathbb{A'\cap B})$，式子为 $ac'd'a^{-1}$。
>
> 顺理成章地，写成 $(ac'a^{-1})(ad'a^{-1})$ 的形式。$a,c'\in\mathbb A$ 然后得到 $c''(ad'a^{-1})$。考虑式子 $d'a^{-1}d'^{-1}$，像上面一样地推即可简单转成 $a'\in\mathbb A$，然后知 $d'a^{-1}d'^{-1}=a'$，即 $d'a^{-1}=a'd'$，所以 $c''(ad'a^{-1})=c''aa'd'=c'''d'$，其中 $c'''\in\mathbb A$。显然 $c'''d'\in\mathbb{A(A'\cap B)}$。则 $\mathbb{A(A'\cap B)\unlhd A(A'\cap B')}$ 得证，同构式右边的式子类似可证。
>
> 我们终于证明出了本定理的式子没有出现定义错误，可喜可贺可喜可贺（
>
> 考虑在本定理的式子中间用 $\mathbb{\dfrac{A'\cap B'}{(A'\cap B)(A\cap B')}}$ 架起桥梁，即如 $\mathbb{\dfrac{A(A'\cap B')}{A(A'\cap B)}\cong\dfrac{A'\cap B'}{(A'\cap B)(A\cap B')}}$ 可证，同构式另一边的式子亦可类似证。
>
> 要想这个桥梁成立，必须先有 $\mathbb{(A'\cap B)(A\cap B')\unlhd(A'\cap B')}$ 成立。考虑设 $a\in(\mathbb{A'\cap B'}),b\in(\mathbb{A'\cap B}),c\in(\mathbb{A\cap B'})$，则证 $abca^{-1}\in\mathbb{(A'\cap B)(A\cap B')}$。
>
> 老套路啦。$abca^{-1}=(aba^{-1})(aca^{-1})=b'c'$，然后考虑证明 $b'=aba^{-1}$ 和 $c'=aca^{-1}$ 的性质：$a,b\in\mathbb A'$ 故 $aba^{-1}\in\mathbb A'$；$a\in\mathbb B',b\in\mathbb B$ 故 $b'\in\mathbb B$；则 $b'\in(\mathbb{A'\cap B})$，$c'$ 同理，然后知 $\mathbb{(A'\cap B)(A\cap B')\unlhd(A'\cap B')}$。
>
> 考虑建立映射 $\varphi:\mathbb{(A'\cap B')\to\dfrac{A(A'\cap B')}{A(A'\cap B)}},a\mapsto a\mathbb{A(A'\cap B)}$。
>
> 考虑 $x\in\mathbb{A'\cap B'}$。$x\in\ker\varphi\Leftrightarrow x\in\mathbb{A(A'\cap B)}=x\in\mathbb{(A'\cap B)A}=\mathbb{A'A\cap BA}=\mathbb{A'\cap BA}$（显然有 $\mathbb{AA'=A'}$；中间用了之前证过的交换律）。
>
> 则有 $x\in\mathbb{A'\cap B'\cap BA=(A'\cap B)(A\cap B')}$。显然这是充要条件，因为每条都可以逆推。则 $\ker\varphi=\mathbb{(A'\cap B)(A\cap B')}$。
>
> 如果 $\varphi$ 是满同态则直接应用第一同构定理即证。同态显然，现考虑证明 $\varphi$ 是满射。
>
> 考虑左陪集 $x\mathbb{A(A'\cap B)}$。如果对于任何 $x\in\mathbb{A(A'\cap B')=(A'\cap B')A}$ 都能在该集合中找到一个属于 $(\mathbb{A'\cap B'})$ 的元素，则 $\varphi$ 是满射。
>
> 设 $x=ab$，其中 $a\in(\mathbb{A'\cap B'}),b\in\mathbb A$。则 $x\mathbb{A(A'\cap B)}=ab\mathbb{A(A'\cap B)}=a\mathbb{A(A'\cap B)}$。显然 $a\in(\mathbb{A'\cap B'})$ 且 $a\in x\mathbb{A(A'\cap B)}$。则 $\varphi(a)=x\mathbb{A(A'\cap B)}$，即 $\varphi$ 是满射。
>
> 证毕（累死我了）。
## VI.自同构初步
本章的最后，我们来看一点轻松的东西，顺便再复习复习前面的几个定理。
<u>定义</u>：**自同态**是群到自身的同态，同理有**自同构**。
可以发现自同态/自同构是变换/置换的扩展：它还保证了变换前后运算的一致性。
与置换群类似，一个群的所有自同构亦成群。
<u>定义</u>：$\operatorname{Aut}\mathbb G$ 为 $\mathbb G$ 上全体自同构关于同构的复合（即置换的复合）构成的群，即**自同构群**。该群的单位元被称作**恒等自同构**，它将元素映射到本身，记作 $\epsilon$。
<u>定义</u>：群中元素 $h$ 关于元素 $g$ 的**共轭**为 $ghg^{-1}$，同理有子群 $\mathbb H$ 的共轭 $g\mathbb Hg^{-1}$。
> 这个定义莫名熟悉，实际上它在正规子群的定义与判定中频繁出现。
<u>定义</u>：群中元素 $a$ 的**中心化子** $\text C(a)$ 为全体满足 $ax=xa$ 的元素 $x$ 构成的集合。群 $\mathbb G$ 的**中心** $\text C(\mathbb G)$ 为全体满足中心化子等于 $\mathbb G$ 的元素 $a$ 构成的集合。易证中心化子和中心都是子群。
<u>定义</u>：$\tau_a:\mathbb G\to\mathbb G,x\mapsto axa^{-1}$ 是 $\mathbb G$ 的自同构，且被称作其关于 $a$ 的**内自同构**。
<u>定义</u>：全体 $\tau_a$ 构成一个群，被称作 $\mathbb G$ 的**内自同构群**，记作 $\operatorname{Inn}\mathbb G$。
定理：$\operatorname{Inn}\mathbb G\unlhd\operatorname{Aut}\mathbb G$。
> Proof：
>
> 只需证明 $\varphi\tau_a\varphi^{-1}\in\operatorname{Inn}\mathbb G$。
>
> 令 $\varphi(x)=y$，则 $\varphi^{-1}(y)=x$（因为 $\varphi$ 是双射）。
>
> 则 $\varphi\Big(\tau_a\big(\varphi^{-1}(y)\big)\Big)=\varphi\big(\tau_a(x)\big)=\varphi(axa^{-1})=\varphi(a)\varphi(x)\varphi(a^{-1})=\varphi(a)y\varphi(a)^{-1}=\tau_{\varphi(a)}(y)\in\operatorname{Inn}\mathbb G$。
定理：$\operatorname{Inn}\mathbb G\cong\mathbb G/\text C(\mathbb G)$。
> Proof：
>
> 首先可构造满射 $\varphi:\mathbb G\to\operatorname{Inn}\mathbb G,a\mapsto\tau_a$。易证其是满同态。
>
> 考虑恒等自同构 $\epsilon$。 $\tau_a=\epsilon\Leftrightarrow\forall x\in\mathbb G,axa^{-1}=x\Leftrightarrow\forall x\in\mathbb G,ax=xa\Leftrightarrow a\in\text C(\mathbb G)$。
>
> 则 $\text C(\mathbb G)=\ker\varphi$。用第一同构定理即证。
# V.群作用
本章的目标是证出几个重要的定理，如广义 Cauchy 定理和 Burnside 引理。
## I.群作用初步
Cayley 定理指出，任一群都同构于置换群。我们一开始也介绍过，群常常被看作是变换的集合。因此，我们便不由得想着要去在什么地方用用这些变换。
定义：对于群 $\mathbb G$ 与集合 $\mathbb S$，如果存在映射 $\varphi:\mathbb{G\times S\to S},(g,s)\mapsto gs$ 满足 $(ab)s=a(bs),es=s$，则称群 $\mathbb G$ **作用**于集合 $\mathbb S$。
但是个人觉得这个定义不太清晰，因此在接下来的讲解中会一直使用接下来的**等价定义**：
<u>定义</u>：对于群 $\mathbb G$ 与集合 $\mathbb S$，如 $\mathbb G$ 到 $\mathbb S$ 上的对称群 $\text S(\mathbb S)$ 存在群同态 $\varphi$，且该同态的运算在 $\mathbb G$ 中是乘法、在 $\text S(\mathbb S)$ 中是置换的复合，则称 $\mathbb G$ 对 $\mathbb S$ 有**作用** $\varphi$。如果该群同态是单射，则称其是**忠实作用**。
<u>定义</u>：在存在作用的 $\mathbb G$ 与 $\mathbb S$ 中，对于 $g\in\mathbb G,s\in\mathbb S$，可记 $\varphi(g)(s)$ 为 $g\circ s$，或更加简洁地记作 $gs$。但需要注意这**不是乘法！不是乘法！不是乘法！**
通过上述定义可以简单由同态传递结合律、单位元证明 $a,b\in\mathbb G,x\in\mathbb S$，有 $a(bx)=(ab)x,ex=x$。这证明等价定义推出原定义。
通过令 $\mathbb{S=G}$，我们可以得出一些常见的群作用：
- $a\circ x=ax$（这里的 $ax$ 就是普通的乘法）。这种群作用被称作**左平移作用**。
- $a\circ x=axa^{-1}$。我们之前说过，这是**共轭作用**。
## II.轨道与稳定子
<u>定义</u>：设群 $\mathbb G$ 作用于集合 $\mathbb S$ 上。定义 $\mathbb S$ 中元素 $x$ 在群 $\mathbb G$ 作用下的**轨道**为子集 $\text O(x)=\{ax|a\in\mathbb G\}$，简称过 $x$ 的轨道。如 $\mathbb S$ 中所有轨道全部相同，则称 $\mathbb G$ 在 $\mathbb M$ 上的作用是**传递**的。
> 在各种场合下，轨道可能有诸如 $\mathbb S_x$、$\text{Orb}(x)$ 等多种符号语言。这里选取了个人认为最简洁泛用的 $\text O(x)$ 写法。
<u>定理</u>：所有轨道的并为全集。
> 显然 $ex=x$，则 $x\in\mathbb S_x$。
<u>定理</u>：不相同轨道无交。
> Proof：
>
> 设 $\text O(x)\cap\text O(y)\neq\varnothing$。则取 $z\in\text O(x)\cap\text O(y)$，显然应满足存在 $a,b$ 使得 $ax=z=by$。
>
> 则有 $y=b^{-1}(ax)=(b^{-1}a)x\in\text O(x)$。
>
> $y\in\text O(x)$ 意味着 $y=cx$，进而 $dy=dcx$，进而 $\text O(y)\subseteq\text O(x)$。
>
> 交换 $x,y$，同理可得 $\text O(x)\subseteq\text O(x)$。则 $\text O(x)=\text O(y)$。
综合上述两定理，我们便得到推论：所有轨道等价类构成了 $\mathbb S$ 的一组**分解**。
<u>定义</u>：设群 $\mathbb G$ 作用于集合 $\mathbb S$ 上。定义 $\mathbb S$ 中元素 $x$ 在群 $\mathbb G$ 作用下的**稳定子**为子群 $\text{Stab}(x)=\{a\in\mathbb G|ax=x\}$。稳定子同态于对称群中所有保持 $x$ 元素不变的置换构成的群。
> 在其它文章中，稳定子可能有 $\mathbb G_x$ 等其它符号语言。这里仍选取符合本人喜好的表示方式。
<u>定理</u>：设 $\mathbb S$ 为 $\mathbb G$ 关于 $\text{Stab}(x)$ 的全体左陪集构成的集合。映射 $\varphi:\text O(x)\to\mathbb S,gx\mapsto g\text{Stab}(x)$ 是双射。
> Proof：
>
> - 是映射且是单射，即原像相同等价于像相同。
>
> $$ax=bx\Leftrightarrow b^{-1}ax=x\Leftrightarrow b^{-1}a\in\text{Stab}(x)\Leftrightarrow a\text{Stab}(x)=b\text{Stab}(x)$$
>
> - 显然是满射，因为全体 $g$ 显然取到了全体可能的左陪集。
<u>推论</u>：$|\text O(x)|=|\mathbb S|=(\mathbb G:\text{Stab}(x))$。
<u>轨道-稳定子定理</u>：$|\mathbb G|=|\text O(x)|\times|\text{Stab}(x)|$。
## III.群方程
<u>定义</u>：令群共轭作用于本身。现考虑其轨道 $\text O(x)=\{a\circ x|a\in\mathbb G\}=\{axa^{-1}\}$。称其为 $x$ 的**共轭类**，记作 $\text{Cl}(x)$。考虑其稳定子 $\text{Stab}(x)=\{a|a\in\mathbb G,a\circ x=x\}=\{a|a\in\mathbb G,ax=xa\}$，发现就是中心化子 $\text C(x)$。
> 同理，$\text{Cl}(x)$ 也只不过是众多表示方式中比较流行的一种。
定理：共轭类是等价类。
> 共轭类首先是轨道，而轨道是等价类。
定义：两个元素**共轭**当且仅当其位于同一个共轭类中（这意味着我们可以不使用一开始定义共轭时的“$g$ 是 $h$ 的共轭”这种单向关系的说法）。
定义：群 $\mathbb G$ 有子群 $\mathbb P$。令其共轭作用于全体 $a\mathbb Pb$ 构成的集合 $\mathbb S$，其中 $a,b\in\mathbb G$，即 $g\circ a\mathbb Pb=ga\mathbb Pbg^{-1}$。考虑该作用下的 $\text O(\mathbb P)$，显然为全体 $a\mathbb Pa^{-1}$，称其为 $\mathbb P$ 的共轭类，也记作 $\text{Cl}(\mathbb P)$。考虑其稳定子 $\text{Stab}(\mathbb P)$，则为 $a\mathbb Pa^{-1}=\mathbb P$ 的全体元素。发现就是正规化子 $\text N(\mathbb P)$。
定理：$|\text{Cl}(\mathbb P)|=(\mathbb G:\text N(\mathbb P))$。
> 依照轨道-稳定子定理简单证。
<u>群方程定理</u>：对于有限群 $\mathbb G$ 来说，$|\mathbb G|=|\text C(\mathbb G)|+\sum\limits_x(\mathbb G:\text C(x))$。其中 $x$ 取遍全体非中心的共轭类的代表元。
> Proof：
>
> 首先，因为共轭类首先是轨道，所以共轭等价类也构成了 $\mathbb G$ 的分解，即 $|\mathbb G|=\sum\limits_x|\text{Cl}(x)|$。
>
> 用轨道-稳定子定理，即得 $|\mathbb G|=\sum\limits_x(\mathbb G:\text C(x))$。
>
> 现考虑全体中心中元素。发现显然有中心中元素的共轭类中元素唯一（因为中心元素满足交换律），进而便可将其从 $\sum$ 中提出。
广义 Cauchy 定理：若有有限群 $\mathbb G$，则对于所有 $|\mathbb G|$ 的质因子 $p$ 来说，$\mathbb G$ 中定有 $p$ 阶元素，进而定有 $p$ 阶子群。
> 与狭义 Cauchy 定理的不同仅在于这里不要求是交换群。
>
> Proof：
>
> 仍归纳。显然在 $2$ 阶群中广义 Cauchy 定理成立。现设 $<n$ 阶群中广义 Cauchy 定理均成立。
>
> 现考虑群方程定理 $|\mathbb G|=|\text C(\mathbb G)|+\sum\limits_x(\mathbb G:\text C(x))$。
>
> - $p$ 是 $|\text C(\mathbb G)|$ 的因数。显然 $\text C(\mathbb G)$ 是交换群，那么在 $\text C(\mathbb G)$ 中用狭义 Cauchy 定理即可证得其存在 $p$ 阶元素。
>
> - $p$ 非 $|\text C(\mathbb G)|$ 因数。因为 $p$ 是 $|\mathbb G|$ 的因数，所以 $p$ 定非 $\sum\limits_x(\mathbb G:\text C(x))$ 的因数，进而定存在一个 $(\mathbb G:\text C(x))$ 不是 $p$ 的倍数。因为 $(\mathbb G:\text C(x))=|\mathbb G|/|\text C(x)|$，所以 $p$ 必是 $|\text C(x)|$ 的因数。
>
> 显然 $|\text C(x)|$ 是 $\mathbb G$ 的真子群。则由归纳假设，$\text C(x)$ 存在 $p$ 阶元素。
自此之后，我们便不再区分广义和狭义 Cauchy 定理，统称 Cauchy 定理。
# VI.群作用下计数问题
终于！本文中首次 OI 环节！
## I.Burnside 引理
定义：设群 $\mathbb G$ 作用于集合 $\mathbb S$。定义 $\mathbb G$ 中元素 $g$ 的**不动元素**为满足 $g\circ x=x$ 的 $\mathbb S$ 中元素 $x$。$g$ 的全体不动元素构成的集合为 $g$ 的**不动元素集**，记作 $\text F(g)$。$\mathbb G$ 中全体 $g$ 的不动元素集的交集为 $\mathbb G$ 的不动元素集，记作 $\text F(\mathbb G)$，其中元素亦被称作 $\mathbb G$ 的不动元素。
定理：设群 $\mathbb G$ 作用于集合 $\mathbb S$。设 $n$ 表示此时 $\mathbb S$ 上的本质不同轨道数。则有
$$n=\dfrac{\sum\limits_{g\in\mathbb{G}}|\text F(g)|}{|\mathbb G|}$$
> Proof：
> $$
> \sum\limits_{g\in\mathbb G}|\text F(g)|=\sum\limits_{g\in\mathbb G}\sum\limits_{x\in\mathbb S}[g\circ x=x]=\sum\limits_{x\in\mathbb S}\sum\limits_{g\in\mathbb G}[g\circ x=x]=\sum\limits_{x\in\mathbb S}|\text{Stab}(x)|=\sum\limits_{x\in\mathbb S}\dfrac{|\mathbb G|}{|\text O(x)|}
> $$
> 我们之前证过轨道间要么无交，要么等价。那么在上式求和式中每个不同的 $\text O(x)$ 共出现了 $|\text O(x)|$ 次，于是我们枚举每条本质不同轨道的代表元便得到了
> $$
> \sum\limits_{g\in\mathbb G}|\text F(g)|=\sum\limits_{x\in\mathbb S}\dfrac{|\mathbb G|}{|\text O(x)|}=\sum\limits_{i=1}^n\dfrac{|\mathbb G|}{|\text O(x_i)|}\times|\text O(x_i)|=n|\mathbb G|
> $$
### I.[【模板】Pólya 定理](https://www.luogu.com.cn/problem/P4980)
虽然打着我们接下来要讲的 Pólya 定理的名号，但是这题是实实在在的 Burnside 引理的模板。
我们来一个个为式子中的东西找上实际意义！
集合 $\mathbb S$ 可看作是所有可能的颜色序列构成的全集。
群 $\mathbb G$ 同构于的 $\mathbb S$ 上置换群是全体转 $i$ 次置换构成的子群。
转 $i$ 次的置换中有 $\gcd(i,n)$ 个循环子置换，共 $n^{\gcd(i,n)}$ 种方案；于是总式子就出来了：
$$\dfrac{\sum\limits_{i=1}^nn^{\gcd(i,n)}}n$$
下面就是欧反的常规操作了。
$\begin{aligned}\dfrac{\sum\limits_{i=1}^nn^{\gcd(i,n)}}n&=\dfrac{\sum\limits_{d|n}n^d\sum\limits_{i=1}^n\Big[\gcd(i,n)=d\Big]}{n}\\&=\dfrac{\sum\limits_{d|n}n^d\sum\limits_{i=1}^{n/d}\Big[\gcd(i,n/d)=1\Big]}{n}\\&=\dfrac{\sum\limits_{d|n}n^d\varphi(n/d)}{n}\end{aligned}
最后一个式子直接用了 \varphi(n/d) 的定义。
或许会想到杜教筛；但是杜教筛不好运用于 d|n 这样的求和。实际上，可以 O(\sqrt n) 地暴力枚举每个 d，然后暴力计算 \varphi，总时间复杂度为 \sum\limits_{d|n}\sqrt{d}\leq O(n^{3/4})。当然这个上界很松很松，因此跑得飞快。
代码：
#include<bits/stdc++.h>
using namespace std;
int T,n;
const int mod=1e9+7;
int ksm(int x,int y=mod-2){
int z=1;
for(;y;y>>=1,x=1ll*x*x%mod)if(y&1)z=1ll*z*x%mod;
return z;
}
int phi(int x){
// printf("%d:",x);
int ret=1;
for(int i=2;i*i<=x;i++){
if(x%i)continue;
ret=1ll*ret*(i-1)%mod;
int tms=-1;while(!(x%i))x/=i,tms++;
ret=1ll*ret*ksm(i,tms)%mod;
}
if(x!=1)ret=1ll*ret*(x-1)%mod;
// printf("%d\n",ret);
return ret;
}
int calc(){
int ret=0;
for(int i=1;i*i<=n;i++){
if(n%i)continue;
(ret+=1ll*ksm(n,i)*phi(n/i)%mod)%=mod;
if(i*i!=n)(ret+=1ll*ksm(n,n/i)*phi(i)%mod)%=mod;
}
return 1ll*ret*ksm(n)%mod;
}
int main(){
scanf("%d",&T);
while(T--)scanf("%d",&n),printf("%d\n",calc());
return 0;
}
II.[HNOI2008]Cards
首先，明显所有“洗牌”操作构成一个群。但是，需要注意的是，群中不能忘记还有 p_i=i 的这一组置换！
要计算某种置换下不动点，就发现置换中成的每个环上颜色必须都相同，可以一起处理。于是设 f_{i,j} 表示填了 i 个红的，j 个绿的的方案数，然后直接背包一下就出来了。
时间复杂度 O(mn^2)。
代码：
#include<bits/stdc++.h>
using namespace std;
int r,g,b,m,n,p,dsu[110],sz[110],f[30][30],res;
int find(int x){return dsu[x]==x?x:dsu[x]=find(dsu[x]);}
void merge(int x,int y){x=find(x),y=find(y);if(x!=y)dsu[y]=x,sz[x]+=sz[y];}
int ksm(int x,int y=p-2){
int z=1;
for(;y;y>>=1,x=x*x%p)if(y&1)z=z*x%p;
return z;
}
int main(){
scanf("%d%d%d%d%d",&r,&g,&b,&m,&p),n=r+b+g;
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++)dsu[j]=j,sz[j]=1;
for(int j=1,x;j<=n;j++)scanf("%d",&x),merge(j,x);
memset(f,0,sizeof(f)),f[0][0]=1;
for(int j=1;j<=n;j++){
if(dsu[j]!=j)continue;
// printf("%d\n",sz[j]);
for(int R=r;R>=0;R--)for(int G=g;G>=0;G--){
if(R+sz[j]<=r)(f[R+sz[j]][G]+=f[R][G])%=p;
if(G+sz[j]<=g)(f[R][G+sz[j]]+=f[R][G])%=p;
}
}
(res+=f[r][g])%=p;
}
memset(f,0,sizeof(f)),f[0][0]=1;
for(int j=1;j<=n;j++){
for(int R=r;R>=0;R--)for(int G=g;G>=0;G--){
if(R+1<=r)(f[R+1][G]+=f[R][G])%=p;
if(G+1<=g)(f[R][G+1]+=f[R][G])%=p;
}
}
(res+=f[r][g])%=p;
printf("%d\n",res*ksm(m+1)%p);
return 0;
}
III.TRANSP2 - Transposing is Even More Fun
题意非常迷惑，这里来翻译一下：
有一个 2^a\times2^b 的矩阵，在内存中按行存储，成为了一个 2^{a+b} 的数组。现在要将其转置，显然转置后的矩阵的存储方式仍是 2^{a+b} 的数组，只不过里面某些位置的值可能发生改变。若只支持交换数组中任意两个位置的值，求交换的最少次数。
首先，转置前后的位置肯定是一一对应的，其中位置 (x,y) 对应了置换后的 (y,x)。假设这对应关心形成了 k 个环，明显一个长度为 c 的环需要交换 c-1 次，则总交换次数应为 2^{a+b}-k。
考虑 (x,y) 在数组中的下标是 2^bx+y，其转成 (y,x) 就变成了 2^ay+x，相当于（循环）左移 a 位或右移 b 位。显然，通过左右移操作能得到的所有位置处于同一个环内。故我们所要求的就是在此操作下本质不同的位置数。
是不是有Burnside引理内味儿了？
左移 a 位与右移 b 位，结合起来最小循环节是 \gcd(a,b)。我们发现只需保留总下标范围（a+b）与循环节（\gcd(a,b)）即可，于是我们令 n=a+b,m=\gcd(a,b)。于是问题变为一个长度为 n 的环，每个位置可以填 0 或 1，求在循环 m 位意义下不同构的环数。
直接上Burnside，得到答案为
\dfrac{\sum\limits_{m|i}2^{\gcd(i,n)}}{n/\gcd{(m,n)}}
（总共只有 n/\gcd(m,n) 种置换）
我们重新令 n=(a+b)/m ，则稍微转换一下可得
\dfrac1n\sum\limits_{d|n}2^{md}\varphi(n/d)
介于数据范围，对于每个 n 都 \sqrt n 地处理是不现实的；但是如果是 O(\log n) 那就行了。于是我们离线下来处理即可。
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=1e6;
const int mod=1e6+3;
int ksm(int x,int y=mod-2){int z=1;for(;y;y>>=1,x=1ll*x*x%mod)if(y&1)z=1ll*z*x%mod;return z;}
int T,n[1001000],res[1001000],all[1001000],pri[1001000],phi[1001000],bit[1001000];
vector<pair<int,int> >v[1001000];
void sieve(){
phi[1]=1;for(int i=2;i<=N;i++){
if(!pri[i])pri[++pri[0]]=i,phi[i]=i-1;
for(int j=1;j<=pri[0]&&i*pri[j]<=N;j++){
pri[i*pri[j]]=true;
if(!(i%pri[j])){phi[i*pri[j]]=phi[i]*pri[j];break;}
phi[i*pri[j]]=phi[i]*phi[pri[j]];
}
}
}
int main(){
sieve();bit[0]=1;for(int i=1;i<=N;i++)bit[i]=(bit[i-1]<<1)%mod;
scanf("%d",&T);
for(int i=1,a,b;i<=T;i++){
scanf("%d%d",&a,&b);
if(!a||!b)continue;
all[i]=bit[a+b];
v[n[i]=(a+b)/__gcd(a,b)].push_back(make_pair(__gcd(a,b),i));
}
for(int i=1;i<=N;i++)for(int j=1;i*j<=N;j++)for(auto k:v[i*j])(res[k.second]+=1ll*bit[i*k.first]*phi[j]%mod)%=mod;
for(int i=1;i<=T;i++)printf("%d\n",(all[i]-1ll*res[i]*ksm(n[i])%mod+mod)%mod);
return 0;
}
IV.[SDOI2013]项链
Step 1.考虑计算符合条件的珠子数
由题意，其等于 \sum\limits_{i=1}^n\sum\limits_{j=i}^n\sum\limits_{k=j}^n[\gcd(i,j,k)=1]。
莫反一下就得到 \sum\limits_{d=1}^n\mu(d)\sum\limits_{i=1}^{n/d}\sum\limits_{j=i}^{n/d}\sum\limits_{k=j}^{n/d}。
后面的东西随便计个数算算得到 \sum\limits_{d=1}^n\mu(d)f(n/d)，其中 f(x)=\dfrac{x(x+1)(x+2)}{6}。
虽然 m 只有 10^7，但是我们仍然可以选择筛出 \mu 前缀和后整除分块做到单次 O(\sqrt m)。于是我们便算出了珠子数，设为 p。
Step 2.考虑计算符合条件的串数
直接上Burnside，得到 \dfrac{\sum\limits_{i=1}^nf\Big(\gcd(i,n)\Big)}{n}，其中 f(x) 表示长度为 x 的环，填入 p 种颜色的珠子，且两两不相邻的方案数。
随便欧拉反演后得到 \dfrac{\sum\limits_{d|n}^nf(d)\varphi(n/d)}{n}。
这里显然不能像之前III.I.【模板】Pólya 定理一样直接暴力，因为 n 较大。但是，发现 10^{14} 内因数最多的数的因子数仅有 6000 多，因此我们考虑预处理出来 n 的所有质因子，这样子就可以枚举所有质因子求出 n 的每个因数的 \varphi 值。复杂度 \sqrt n+6000\log n，可以接受。
Step 3.考虑计算 f
我们在位置 1 处断环成链。设 f(i,0/1) 表示当前填到第 i 个位置，且位置 i 的颜色不与/与位置 1 的颜色相同的方案数。
暴力DP可以做到 O(n) 计算单个 f 值；稍微聪明一点就可以选择用矩阵快速幂优化；懂得更多的，就可以计算出转移矩阵的特征值与特征向量，然后得出通项公式 f(n)=(p-1)^n+(p-1)(-1)^n。
似乎已经做完了？
Step 4.特判
首先，当 m=1 时，我们上述大部分结论都会失效，所以这时就要特判 n，若 n=1，答案为 1，否则为 0。
同时，我们发现，当 (10^9+7)|n 时，n 不存在逆元。于是这时就要更换全套系统，把所有东西从一个单独的 int，升级为一对 pair，表示其在 10^9+7 进制下末两位的值，这样子输出时就只需输出倒数第二位的值即可。
需要注意的是，这个系统一定要换完全，包括上文的 p 也要是这一形式。同时注意此系统实际上的模数是 (10^9+7)^2，因此求逆元时指数要对 \varphi\Big((10^9+7)^2\Big) 取模。
时间复杂度 O\Bigg(m+T\bigg(\sqrt m+\Big(\sqrt n+d(n)\log n\Big)\bigg)\Bigg)，其中 d(n) 表示 n 的因子数。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int inv6=166666668;
const int N=1e7;
int ksm(int x,int y=mod-2){int z=1;for(;y;y>>=1,x=1ll*x*x%mod)if(y&1)z=1ll*z*x%mod;return z;}
int T,m,p,mu[10010000],pri[10010000],inv[10010000];
ll n;
int calc(int x){return 1ll*x*(x+1)%mod*(x+2)%mod*inv6%mod;}
void sieve(){
mu[1]=1;for(int i=2;i<=N;i++){
if(!pri[i])pri[++pri[0]]=i,inv[pri[0]]=ksm(i),mu[i]=-1;
for(int j=1;j<=pri[0]&&i*pri[j]<=N;j++){
pri[i*pri[j]]=true;
if(i%pri[j])mu[i*pri[j]]=-mu[i];
else{mu[i*pri[j]]=0;break;}
}
}
for(int i=1;i<=N;i++)mu[i]+=mu[i-1];
}
int f(ll n){return (ksm(p-1,n%(mod-1))+(n&1?mod-(p-1):(p-1)))%mod;}
struct dat{
int a,b;
dat(int x){a=x/mod,b=x%mod;if(b<0)b+=mod,a--;if(a<0)a+=mod;}
dat(int x,int y){a=x,b=y;}
void operator*=(const int&v){a=(1ll*a*v+1ll*b*v/mod)%mod,b=1ll*b*v%mod;}
void operator*=(const dat&v){a=(1ll*a*v.b+1ll*b*v.a+1ll*b*v.b/mod)%mod,b=1ll*b*v.b%mod;}
dat operator*(const dat&v){return dat((1ll*a*v.b+1ll*b*v.a+1ll*b*v.b/mod)%mod,1ll*b*v.b%mod);}
void operator+=(const dat&v){a=(a+v.a+(b+v.b)/mod)%mod,b=(b+v.b)%mod;}
dat operator+(const dat&v){return dat((a+v.a+(b+v.b)/mod)%mod,b=(b+v.b)%mod);}
dat operator-(){return dat((mod-a)%mod,(mod-b)%mod);}
};
dat ksm(dat x,ll y=1ll*mod*(mod-1)-1){dat z(1);for(;y;y>>=1,x*=x)if(y&1)z*=x;return z;}
const dat INV6=ksm(dat(6));
dat CALC(int x){return dat(x)*dat(x+1)*dat(x+2)*INV6;}
dat P(0);
dat F(ll n){return ksm(P,n)+(n&1?(-P):P);}
int main(){
sieve();
scanf("%d",&T);
while(T--){
scanf("%lld%d",&n,&m);
if(m==1){printf("%d\n",n==1);continue;}
vector<int>v;ll tmpn=n;
for(int i=1;i<=pri[0];i++){
if(tmpn%pri[i])continue;
v.push_back(i);
while(!(tmpn%pri[i]))tmpn/=pri[i];
}
if(n%mod){
p=0;
for(int l=1,r;l<=m;l=r+1)r=m/(m/l),(p+=1ll*calc(m/l)*(0ll+mu[r]-mu[l-1]+mod)%mod)%=mod;
int invn=ksm(tmpn%mod);
int res=0;
for(int i=1;1ll*i*i<=n;i++){
if(n%i)continue;
int tmp=(n/i)%mod*f(i)%mod;
for(auto j:v)if(!((n/i)%pri[j]))tmp=1ll*tmp*(pri[j]-1)%mod*inv[j]%mod;
if(tmpn!=1&&!((n/i)%tmpn))tmp=(tmpn-1)%mod*tmp%mod*invn%mod;
(res+=tmp)%=mod;
if(1ll*i*i==n)break;
tmp=1ll*i*f(n/i)%mod;
for(auto j:v)if(!(i%pri[j]))tmp=1ll*tmp*(pri[j]-1)%mod*inv[j]%mod;
if(tmpn!=1&&!(i%tmpn))tmp=(tmpn-1)%mod*tmp%mod*invn%mod;
(res+=tmp)%=mod;
}
printf("%d\n",1ll*res*ksm(n%mod)%mod);
}else{
P=dat(0);
for(int l=1,r;l<=m;l=r+1)r=m/(m/l),P+=CALC(m/l)*dat(mu[r]-mu[l-1]);
P+=dat(-1);
dat res(0);
for(int i=1;1ll*i*i<=n;i++){
if(n%i)continue;
dat tmp=F(i);
if((n/i)%mod){
tmp*=(n/i)%mod;
for(auto j:v)if(!((n/i)%pri[j]))tmp*=1ll*(pri[j]-1)*inv[j]%mod;
}else{
tmp*=(mod-1);
for(auto j:v)if(!((n/i)%pri[j]))tmp*=1ll*(pri[j]-1)*inv[j]%mod;
}
res+=tmp;
if(1ll*i*i==n)break;
tmp=F(n/i),tmp*=i;
for(auto j:v)if(!(i%pri[j]))tmp*=1ll*(pri[j]-1)*inv[j]%mod;
res+=tmp;
}
printf("%d\n",1ll*res.a*ksm(n/mod)%mod);
}
}
return 0;
}
V.[MtOI2018]魔力环
上 Burnside 引理，则答案为 \dfrac 1n\sum\limits_{i=1}^nf(\gcd(i,n))=\dfrac1n\sum\limits_{d|n}f(d)\varphi(n/d)，其中 f(d) 表示环的循环节长为 d 时的答案。
只有当 n=m 时，环是全黑的，进而不同循环节间的黑段长度会拼接在一起。这个特判掉就行。然后每个循环节内部便必然存在白位置，进而不同循环节间的黑段不会拼接——除了循环节首尾的黑段事实上是相连的之外。
因为首尾相连即是成环，所以 f(d) 时的子问题就是一个长度为 d 的环中恰有 m/d 个黑位置时的答案。
考虑将模型转化为往一个白环中两两元素间插入不超过 K 个黑元素。然后在两个白元素间断环成链，枚举此二元素间黑元素的数量，然后对于剩下的部分计数。
问题转化为将某数量的黑元素分成某定值段，每段元素的数量属于区间 [0,K]。
钦定一些段不合法，然后二项式反演掉。问题转化为某数量的黑元素分成某定值段的方案数。
运用小学数学隔板法即可简单解决。
现在考虑分析复杂度。在求 f(d) 时，我们要 O(K) 枚举首段的长度，然后二项式反演。显然反演只用枚举到 \dfrac dK 即可。因而单次 O(d)。
考虑枚举不同的 d。而有意义的 d 显然只有 \gcd(n,m) 的所有因数（不然每段的黑白格数不是整数）。因而复杂度即为其所有因数之和。
考虑最粗糙的估计：O(\sqrt n) 个约数，每个按 n 算，也只不过是 O(n\sqrt n)。
代码：
#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
int n,m,K,fac[100100],inv[100100],res;
int ksm(int x,int y=mod-2){int z=1;for(;y;y>>=1,x=1ll*x*x%mod)if(y&1)z=1ll*z*x%mod;return z;}
int func(int x,int y){if(!y)return !x;return 1ll*fac[x+y-1]*inv[y-1]%mod*inv[x]%mod;}
int solve(int x,int y){
// printf("(%d,%d)\n",x,y);
int ret=0;
for(int i=0;i*(K+1)<=x&&i<=y;i++){
int tmp=1ll*func(x-i*(K+1),y)*fac[y]%mod*inv[i]%mod*inv[y-i]%mod;
// printf("__%d\n",tmp);
if(i&1)ret=(ret+mod-tmp)%mod;
else ret=(ret+tmp)%mod;
}
// printf("%d\n",ret);
return ret;
}
int calc(int d){
int ret=0;
for(int i=0;i<=min(m/d,K);i++)ret=(1ll*(i+1)*solve(m/d-i,(n-m)/d-1)+ret)%mod;
// printf("%d:%d\n",d,ret);
return ret;
}
int pri[100100],phi[100100];
void sieve(){
phi[1]=1;
for(int i=2;i<=n;i++){
if(!pri[i])pri[++pri[0]]=i,phi[i]=i-1;
for(int j=1;j<=pri[0]&&i*pri[j]<=n;j++){
pri[i*pri[j]]=true;
if(i%pri[j])phi[i*pri[j]]=phi[i]*phi[pri[j]];
else{phi[i*pri[j]]=phi[i]*pri[j];break;}
}
}
}
int main(){
scanf("%d%d%d",&n,&m,&K),K=min(K,n);
sieve();
// for(int i=1;i<=n;i++)printf("%d ",phi[i]);puts("");
if(n==m){puts(K==n?"1":"0");return 0;}
fac[0]=1;for(int i=1;i<=n;i++)fac[i]=1ll*fac[i-1]*i%mod;
inv[n]=ksm(fac[n]);for(int i=n;i;i--)inv[i-1]=1ll*inv[i]*i%mod;
for(int i=1;i<=n;i++)if(!(n%i)&&!(m%i))res=(1ll*phi[i]*calc(i)+res)%mod;
printf("%d\n",1ll*res*ksm(n)%mod);
return 0;
}
II.Pólya定理
Pólya定理：
该定理仅使用于染色模型，且颜色数量为 $|\mathbb B|$；$c(g)$ 表示 $g$ 的循环子置换数量。
这个定理可以直接由 Burnside 引理得到。
### I.[[SHOI2006] 有色图](https://www.luogu.com.cn/problem/P4128)
应该很容易想到的是，我们考虑对每一种点标号上的置换（共 $n!$ 种），都能够唯一生成一种边标号上的置换，而所有边标号上置换构成一个置换群。
于是我们考虑如何由点置换推出边置换的环数。
首先，我们要剔除点置换产生的一些无用消息。首先，我们把点置换写成环的形式。接着，我们发现只需储存每个环的大小即可，没必要管环上具体元素是什么。于是我们就把一组点置换写成了 $\{c_1,c_2,\dots\}$ 的形式，其中 $c_i$ 是环上点数量。
接着考虑边置换。明显，能与一条边 $(x,y)$ 在同一个环内的边，只有可能一端在点置换中与 $x$ 在同环内，另一端在点置换中与 $y$ 在同环内。
于是我们现在考虑对于两个环 $(c_i,c_j)$，会形成多少个环。发现，$i$ 中每 $c_i$ 次循环一次，$j$ 中每 $c_j$ 次循环一次，每个循环的大小是 $\operatorname{lcm}(c_i,c_j)$，则循环数即为 $\dfrac{c_ic_j}{\operatorname{lcm}(c_i,c_j)}=\gcd(c_i,c_j)$。
同时，不能忘记 $(x,y)$ 在同环内的情形。此时，所有长度相同的边成环，则此部分方案数为 $\left\lfloor\dfrac{c_i}{2}\right\rfloor$。
现在统计在一块，总环数为 $\sum\limits_i\left\lfloor\dfrac{c_i}{2}\right\rfloor\sum\limits_{i<j}\gcd(c_i,c_j)$。
现在考虑套上Pólya，得到式子为
$$\dfrac{\sum\limits_pm^{\sum\limits_i\left\lfloor\tfrac{c_i}{2}\right\rfloor\sum\limits_{i<j}\gcd(c_i,c_j)}}{n!}
然后我就开始莫反了，最后也没有反出什么结果出来
事实上，因为这个 n=53 很小，甚至可以考虑爆搜。我们考虑搜出所有的 \{c\}，则方案数可以简单计算，我们只需要计算有多少排列能生成该环大小集合即可。
首先，考虑我们给每个点分配到环上某个位置，是 n!；
接着，因为环上绕一圈是同构的，所以我们对于每个环要除掉环的长度，也即 \prod\limits_ic_i。
同时，我们上述操作中实际上是给环标号了的，但是实际上环上并无标号，任意两个 c 相等的环均是相同的。因此设 s_i 表示有多少个大小为 i 的环，则应该除去 s_i! 消去编号。
于是我们得出了总式子：
\dfrac{\sum\limits_{\{c\}}\dfrac{n!}{\prod c_i\prod s_i!}\times m^{\sum\limits_i\left\lfloor\tfrac{c_i}{2}\right\rfloor\sum\limits_{i<j}\gcd(c_i,c_j)}}{n!}
稍微约一约
\sum\limits_{\{c\}}\dfrac{m^{\sum\limits_i\left\lfloor\tfrac{c_i}{2}\right\rfloor\sum\limits_{i<j}\gcd(c_i,c_j)}}{\prod c_i\prod s_i!}
这就是答案。
代码：
#include<bits/stdc++.h>
using namespace std;
int n,m,mod,fac[110],inv[110],INV[110],res,sum[110];
int ksm(int x,int y=mod-2){
int z=1;
for(;y;y>>=1,x=1ll*x*x%mod)if(y&1)z=1ll*z*x%mod;
return z;
}
vector<int>v;
int calc(){
int ret=1,tot=0;
for(auto i:v)ret=1ll*ret*INV[i]%mod,tot+=i/2;
for(int i=1;i<=n;i++)if(sum[i])ret=1ll*ret*inv[sum[i]]%mod;
for(int i=0;i<v.size();i++)for(int j=i+1;j<v.size();j++)tot+=__gcd(v[i],v[j]);
return 1ll*ret*ksm(m,tot)%mod;
}
void dfs(int lef,int lim){
if(!lef){(res+=calc())%=mod;return;}
for(int i=min(lef,lim);i;i--)sum[i]++,v.push_back(i),dfs(lef-i,i),v.pop_back(),sum[i]--;
}
int main(){
scanf("%d%d%d",&n,&m,&mod);
fac[0]=1;for(int i=1;i<=n;i++)fac[i]=1ll*fac[i-1]*i%mod,INV[i]=ksm(i);
inv[n]=ksm(fac[n]);for(int i=n-1;i>=0;i--)inv[i]=1ll*inv[i+1]*(i+1)%mod;
dfs(n,n);
printf("%d\n",res);
return 0;
}
II.[HNOI2009]图的同构计数
双 倍 经 验
因为边的有无即可被看作是两种颜色。
于是直接贴上一题的代码就行了。
代码：
#include<bits/stdc++.h>
using namespace std;
const int mod=997;
int n,m,fac[110],inv[110],INV[110],res,sum[110];
int ksm(int x,int y=mod-2){
int z=1;
for(;y;y>>=1,x=x*x%mod)if(y&1)z=z*x%mod;
return z;
}
vector<int>v;
int calc(){
int ret=1,tot=0;
for(auto i:v)ret=ret*INV[i]%mod,tot+=i/2;
for(int i=1;i<=n;i++)if(sum[i])ret=ret*inv[sum[i]]%mod;
for(int i=0;i<v.size();i++)for(int j=i+1;j<v.size();j++)tot+=__gcd(v[i],v[j]);
return ret*ksm(2,tot)%mod;
}
void dfs(int lef,int lim){
if(!lef){(res+=calc())%=mod;return;}
for(int i=min(lef,lim);i;i--)sum[i]++,v.push_back(i),dfs(lef-i,i),v.pop_back(),sum[i]--;
}
int main(){
scanf("%d",&n);
fac[0]=1;for(int i=1;i<=n;i++)fac[i]=fac[i-1]*i%mod,INV[i]=ksm(i);
inv[n]=ksm(fac[n]);for(int i=n-1;i>=0;i--)inv[i]=inv[i+1]*(i+1)%mod;
dfs(n,n);
printf("%d\n",res);
return 0;
}
VII.某些特殊子群的存在性
本章直接依赖于群作用一章。
I.p-群初步
定义：一个群被称作 p-群，当其中所有元素的阶均为 p 的非负整数次幂，而 p-子群为是 p-群的子群。
定理：一个群是 p-群，当且仅当 |\mathbb G| 是 p 的非负整数次幂。
Proof：
由 Cauchy 定理，任何包含非 p 的质数作为因数的 |\mathbb G| 都必存在阶为该质数的元素，进而 p-群的阶必然只包含 p 作为质因数，进而就必是 p 的非负整数次幂。
定理：p-群 \mathbb G 作用于集合 \mathbb S 上时，|\mathbb S|\equiv|\text F(\mathbb G)|\pmod p。
Proof：
由轨道-稳定子定理，|\text O(x)| 必是 |\mathbb G| 的因子。
现 |\mathbb G| 为质数，则 |\text O(x)| 要么是 1，要么是 p 的正整数幂次。
因为轨道是分解，所以 $|\mathbb S|$ 等于 $|\text F(\mathbb G)|$ 个阶为 $1$ 的轨道再并上很多阶为 $p$ 的幂次的轨道。
那么显然两边同模 $p$ 便得到上式。
定理：如果 \mathbb H 是 \mathbb G 的 p-子群，则 (\text N(\mathbb H):\mathbb H)\equiv(\mathbb{G:H})\pmod p。
Proof：
令 \mathbb S 为 \mathbb H 关于 \mathbb G 的全体左陪集构成的集合，则 \text S(\mathbb S) 即为其上对称群。
定义 \tau_a:g\mathbb H\mapsto ag\mathbb H 为 \text S(\mathbb S) 中一个置换。
定义同态 \varphi:\mathbb H\to\text S(\mathbb S),a\mapsto\tau_a。则其是一个作用。
显然有 |\mathbb S|=(\mathbb{G:H})。则如果我们可以证明 \varphi 下的 \text F(\mathbb H)=\text N(\mathbb H)/\mathbb H，则应用前一个定理即证。
首先先考虑 \text F(a)，即全体在 \tau_a 下不变的元素。则应满足 ag\mathbb H=g\mathbb H。
对于 g\in\text N(\mathbb H)，有 ag\mathbb H=a\mathbb Hg。又 a 是 \mathbb H 中元素，所以 a\mathbb Hg=\mathbb Hg=g\mathbb H。
对于 g\notin\text N(\mathbb H)，必存在 x\in\mathbb H，满足 xg\notin g\mathbb H（即右偏集中必有某个元素不在左陪集中）即 xg\mathbb H\neq g\mathbb H。
则 \text F(\mathbb H)=\text N(\mathbb H)/\mathbb H ，证毕。
II.Sylow 定理
Sylow 第一定理：若 |\mathbb G|=p^\alpha m，其中 \alpha\in\mathbb N,p\nmid m。则其中必然含有阶为所有 p^\beta，其中 \beta\in\mathbb N,\beta\leq\alpha 的子群，且低阶子群必位于某个高阶子群的内部。
Proof：
现考虑归纳。现假设 $p^\beta$ 阶子群（$0\leq\beta<\alpha$）存在，下证 $p^{\beta+1}$ 阶子群存在。
现设 $p^\beta$ 阶子群是 $\mathbb H$。则，$(\mathbb{G:H})=\dfrac{|\mathbb G|}{|\mathbb H|}=\dfrac{p^\alpha m}{p^\beta}=p^{\alpha-\beta}m$。因为 $\beta<\alpha$，所以 $p|(\mathbb{G:H})$，进而运用我们之前证过的定理，$p|(\text N(\mathbb H):\mathbb H)$。
使用 Cauchy 定理在 $\text N(\mathbb H)/\mathbb H$ 中找到 $p$ 阶元 $a\mathbb H$。考虑循环群 $\left<a\mathbb H\right>$，其容显然为 $p$，且其中任意两个元素（即两个左陪集）无交。则考虑其中所有左陪集中的所有元素——共有 $p^{\beta+1}$ 个。如果它们构成 $\mathbb G$的子群，则显然就已经归纳成功了。
现考虑证明其是子群。应用子群判定定理，即证：对于任两个该循环群中左陪集 $b\mathbb H,c\mathbb H$ 中的任两个元素 $x,y$，存在一个左陪集满足 $xy^{-1}$ 是其中元素。
显然 $y^{-1}\in(c\mathbb H)^{-1}=c^{-1}\mathbb H$。显然 $xy^{-1}\in(b\mathbb H)(c^{-1}\mathbb H)=(bc^{-1})\mathbb H$。显然 $bc^{-1}\mathbb H$ 是该循环群中的元素。故证毕。
考虑我们构造的方式，就会发现这样构造可以为每个低阶子群构造一个包含其的高阶子群。
定义：在有限群 \mathbb G 中，设 |\mathbb G|=p^\alpha m，其中 \alpha\in\mathbb N,p\nmid m。则阶为 p^\alpha 的子群被称作 Sylow p-子群，所有 Sylow p-子群构成的集合被称作 Sylow p-子群集，记作 \text{Syl}_p(\mathbb G)。暂记 n_p(\mathbb G)=|\text{Syl}_p(\mathbb G)|。
Sylow 第二定理：\text{Syl}_p(\mathbb G) 中任两个群共轭。
Proof：设 \mathbb{P,Q}\in\text{Syl}_p(\mathbb G)。考虑 \mathbb P 所有左陪集构成的集合 \mathbb S，显然 |\mathbb S|=\dfrac{|\mathbb G|}{|\mathbb P|}=m（这里的 m 同上方定义）。
令群 \mathbb Q 左平移作用于 \mathbb S。（忘记左平移作用是什么了？Ctrl+F 找一下吧！）按照我们之前证过的定理，\mathbb S 的大小在模 p 意义下同余于不动元素数；而 |\mathbb S| 显然非 p 的倍数，故存在不动元素。则存在 a\in\mathbb P 满足对于一切 b\in\mathbb Q，ba\mathbb P=a\mathbb P，则 ba\mathbb Pa^{-1}=a\mathbb Pa^{-1}，即 b\in a\mathbb Pa^{-1}，即 \mathbb Q\subseteq a\mathbb Pa^{-1}。显然 a\mathbb Pa^{-1} 是 \mathbb P 的共轭，则 |a\mathbb Pa^{-1}|=|\mathbb P|=|\mathbb Q|，则 \mathbb Q=a\mathbb Pa^{-1}。
定理：若令 \mathbb P\in\text{Syl}_p(\mathbb G)，则 n_p(\mathbb G)=(\mathbb G:\text N(\mathbb P))。
Proof：
按照 Sylow 第二定理，\text{Syl}_p(\mathbb G) 中任两个群共轭；那么，是否有 \text{Syl}_p(\mathbb G) 中任意群的共轭群都属于 \text{Syl}_p(\mathbb G) 呢？（这等价于 \text{Syl} 是一个共轭类）
答案是肯定的，因为 Sylow 第二定理的证明中每一条的逆定理均成立。（自己可以尝试证一下哦）
则 n_p(\mathbb G)=|\text{Cl}(\mathbb P)|，因为共轭关系具有传递性。
我们证过 |\text{Cl}(\mathbb P)|=(\mathbb G:\text N(\mathbb P))，可以翻到“群方程”一节复习。
Sylow 第三定理：n_p(\mathbb G) 是 |\mathbb G| 的因数且模 p 的余数为 1。
Proof：
是因数我们已经在上一个定理中证过了。
考虑令 \mathbb P 共轭作用于 \text{Syl}_p(\mathbb G)。则 |\text{Syl}_p(\mathbb G)| 同余于该作用的不动元素数（我们在上一节证过该定理）。
考虑证明不动元素唯一。对于每个 \mathbb Q=a\mathbb Pa^{-1}\in\text{Syl}_p(\mathbb G) 且 \mathbb Q\neq\mathbb P，我们均可以将其作用上 a^{-1}（它一定存在，因为 \mathbb P 是群）以还原出 \mathbb P。这意味着它们都不是不动元素。而显然 \mathbb P 本身是不动元素。则不动元素唯一。
证毕。
INF.结语
这是群论中最基础的一些内容。
只写这么多不是因为群论只有这么多，而是因为 Typora 太垃圾，在编辑接近 100K 的文章时太卡了。
预告（放鸽子）：伽罗瓦理论 环/域理论。
update on 2022.2.15：大家似乎都很期待上面的文章啊。为了回应大家的期待，我将在 NOI2022 后 至少更新上述两种理论的一种。如果我有幸拿了 Au，那么 两篇文章都会更新。应该也会向日报投稿。假如不出意外的话，在明年的这个时候，大家应该就能在日报中见到上述续篇之一了。
感谢大家的支持！祝大家学习愉快，有所收获！也祝我自己在接下来的省选和 NOI 中 rp++
update on 2022.8.26：寄了。差 eps 分没拿到 Au。明年再战。
于是只有环论和域论了。
因为 NOI 延期导致更新必然会在开学后，但会更的。
不知道什么时候再见吧。
whk 我的 whk……
update on 2023.8.30
坑已经填完了，可以在 洛谷博客 阅读。
但是因为你谷逆天的 Latex 渲染，只能看到依托炸了的东西。
不准备投日报，除非你谷把渲染修好。
也可以选择渲染更友好的 cnblogs。
可能会随时 update。
再会！
借物处：
这份专栏
这篇文章
Visual Group Theory 这本书。
文章编排、定理证明、定理挑选有部分来自于上述材料。