基本概念和引理
- 代数系统：在一个集合上 $S$ 定义一个二元运算 $\times$，如果二元运算满足封闭性，则称 $(S,\times)$ 为一个代数系统。
- 半群：如果一个代数系统二元运算满足结合律，那么这个代数系统称为半群。
- 幺半群：如果一个半群里面有幺元（单位元），那么这个群为幺半群。
- 群：如果一个幺半群里面每个元素都有逆元，则这个幺半群是个群。
- Abel 群：如果一个群满足交换律，那么这个群是一个 Abel 群。
- 循环群：如果一个 Abel 群有一个生成元 $g$，也就是说，任意群内的元素可以被表示为 $g^k$，则这个群为一个循环群。
如图：
-
环：环是定义了两个运算 $+,\times$ 的集合 $S$，满足 $(S,+)$ 是阿贝尔群，且乘法关于加法有分配率，乘法具有结合律。
-
域：域是定义了两个运算 $+,\times$ 的集合 $S$ 满足 $(S,+)$ 和 $(S\backslash 0,\times)$ 都是阿贝尔群，其中 $0$ 是 $(S,+)$ 的单位元。
-
子群：设 $H$ 是 $G$ 的子集，若 $H$ 在 $G$ 的运算里构成群，则称 $H$ 为 $G$ 的子群。记作 $H\le G$
-
对于子群而言，以下三个定义等价：
-
- $H\le G$
-
- 对任意的 $a,b\in H$ 有 $ab\in H,a^{-1}\in H$
-
- 对任意的 $a,b\in H$ 有 $ab^{-1}\in H$
证明：互相推导是显然的，只需要注意因为 $H$ 中定义的二元运算就是 $G$ 中定义的，所以一定满足结合律。
-
陪集：设 $H\le G$ 则可以给出 $G$ 上的一个等价关系，$a\sim b \Leftrightarrow ∃ h,a=bh$，可以简单证明这个关系确实是等价关系，且 $a$ 的等价类是 $aH$，这个等价类是 $G$ 的一个左陪集，同时也可以由等价关系得到，$G$ 实际上是左陪集的无交并，任意一个元素一定属于一个等价类：$a\in aH$。
推论：任意有限群的子群大小一定是其大小的因数。
阶：设 $a$ 为群 $G$ 中的一个元素，则满足 $a^n=e$ 的最小的 $n$ 称为 $a$ 的阶。
推论：任意元素的阶一定是群大小的因数。因而若群大小是质数，则一定是循环群。
证明：对于一个元素 $a$，所有的 $a^n$ 组成一个群，所以阶数一定为群大小的因数。
-
正规子群：设 $H$ 为 $G$ 的子群，若对于任意 $g\in G,h\in H$ 都存在 $h'\in H$ 使得 $gh=h'g$，则称 $H$ 为 $G$ 的正规子群，记为 $H\trianglelefteq G$。
等价定义 $1$：若 $H$ 所有左陪集与右陪集相等，即 $\forall a,aH=Ha$，则 $H$ 是正规子群。
等价定义 $2$：若 $\forall g\in G,h\in H,ghg^{-1}\in H$，则 $H$ 是正规子群。
证明：显然。
-
商群：给定群 $G$，设 $H$ 是 $G$ 的正规子群，则 $H$ 的所有左陪集在群定义二元运算下满足群的性质，这个群称为 $G$ 关于 $H$ 的商群。记作 $L=G/H$，定义 $L$ 上的乘法为 $a_1H\times a_2H=(a_1\times a_2)H$
-
对于商群的定义来说，其良定义当且仅当 $H$ 是正规子群。
证明：充分性：若 $H$ 是正规子群，则 $\forall h_1,h_2\in H$ 都有 $a_1h_1H\times a_2h_2H=(a_1h_1a_2h_2)H=(a_1a_2h_1'h_2)H=(a_1a_2)H$。显然良定义。
必要性：$\forall g\in G,h_1,h_2\in H$，我们需要让 $(gh_1g^{-1}h_2)H=gh_1H\times g^{-1}h_2H=gH\times g^{-1}H=H$，因此必然要有 $gh_1h^{-1}$，这正是正规子群的定义。
-
推论：$|H||G/H|=|G|$
-
推论：对于一个 Abel 群，其任意子群都是正规子群。
-
同态：对于群 $G,H$，存在映射 $f:G\to H$，使得 $\forall a,b\in G,f(ab)=f(a)f(b)$，则 $G,H$ 同态。
同时定义 $\ker f={ g|f(g)=1_H,g\in G }$，即所有能被映射到 $H$ 单位元的 $G$ 中的值，这显然是一个群。同时，$\mathrm{im}\ f$ 定义为 $f(G)$，为 $f$ 的像。$\ker f$ 称为 $f$ 的核。若 $f$ 是双射，则称 $G,H$ 同构，成 $f$ 为 $G$ 和 $H$ 同构映射，并且记为 $G\cong H$。
-
群的直积：两个群的直积定义为 $H=G_1\times G_2={ (g_1,g_2)|g_1\in G_1,g_2\in G_2 }$，乘法定义为 $(g_1,g_2)\times (g_1',g_2')=(g_1\times_{G_1}g_1',g_2\times_{G_2}g_2')$。
显然的 $|H|=|G_1||G_2|$，并且 $G_1'={ (g_1,1_{G_2})|g_1\in G_1 }$ 和 $G_2'={ (1_{G_1},g_2)|g_2\in G_2 }$ 都是 $H$ 的 $H$ 正规子群。
同构基本定理与同构第二定理
- 同构基本定理：
设 $f:G\to H$ 为一个同态，则 $\ker f$ 是正规子群且 $G/\ker f\cong \mathrm{im}\ f$。
证明：首先证明 $\ker f$ 是一个正规子群，考虑 $f(gkg^{-1})$ 的值，其中 $k\in \ker f,g\in G$，根据定义，有：
$$
f(gkg^{-1}) =f(g)f(k)f(g{-1})=f(g)f(g)=f(1_G)=1_H
$$
所以 $\ker f$ 是一个正规子群。
接下来证明 $\mathrm{im}\ f$ 是一个子群，对于 $a_1,b_1\in \mathrm{im}\ f,∃ a,b,s.t.f(a)=a_1,f(b)=b_1$，于是 $a_1b_1{-1}=f(a)f(b)=f(ab^{-1})\in \mathrm{im}\ f$，故 $\mathrm{im}\ f\le H$。
以上证明了关于 $f$ 的像与核的一些简单性质。以下记 $H=\mathrm{im}\ f$
令 $\varphi : G/\ker f\to H$ 定义为 $\varphi(g\ker f)=f(g)$。要证明 $\varphi$ 良定义需要证明对于 $a,b$ 满足 $aH=bH\Rightarrow b\in aH$ 来说，$\varphi(aH)=\varphi(bH)$。实际上这确实是成立的：$\varphi(bH)=f(b)=f(ah)=f(a)f(h)=f(a)=\varphi(aH)$。
同时 $\varphi(g_1\ker f\times g_2\ker f)=\varphi(g_1g_2\ker f)=f(g_1g_2)=f(g_1)f(g_2)=\varphi(g_1\ker f)\varphi(g_2\ker f)$，所以 $\varphi$ 是同态映射。实际上，只需要说明 $\ker \varphi ={H}$ 即可，因为 $H$ 是 $G/H$ 的幺元，这个定理我们会在后面证明，这里先假设其成立。于是有 $\varphi(aH)=e_1\Rightarrow f(a)=e_1\Rightarrow a\in H\Rightarrow aH=H\Rightarrow\ker \varphi=H\Rightarrow$ $\varphi$ 是单射，而对于 $f(g)$ 来说，有 $\varphi(g\ker f)=f(g)$，所以又是满射。所以 $\varphi$ 是同构映射。
- 设 $\varphi:G\to H$ 是群同态，则 $\varphi$ 单 $\Leftrightarrow \ker \varphi ={ e_G }$
证明：$\varphi$ 不是单射 $\Leftrightarrow ∃ a,b\in G,s.t.a\not=b,\varphi(a)=\varphi(b)\Leftrightarrow \varphi(ab{-1})=\varphi(a)\varphi(b)=e_H\Leftrightarrow \ker \varphi \supseteq { ab^{-1},e }\Leftrightarrow \ker \varphi \not= { e }$。
- 推论：令 $H=G_1\times G_2$，则 $H/G'_1\cong G _2,H/G'_2\cong G_1$。
证明：这里只证明前者，后者类似。
构造 $f((g_1,g_2))=g_2$，这样的话 $\ker f={ (g_1,e) }$。由同构基本定理就可以得到推论。
- 推论：设 $\varphi:G\to H$ 为群的满同射，则 $G/\ker \varphi \cong G_1$。
- 同构第二定理：设 $H,K\trianglelefteq G,H\le K$ 则 $\frac{G/H}{K/H}=\frac{G}{K}$。即“除数”可约。
证明：首先有 $H\trianglelefteq K$，这是显然的，因为 $K\le G$，且对于 $g\in G$ 有 $gH=Hg$。
构造映射 $f:G/H\to G/K:f(gH)=gK$。
首先证明 $f$ 是良定义的，对于 $aH=bH$，有 $f(aH)=aK=aHK=bHK=bK=f(bH)$。
而 $f$ 是同态映射：$f(g_1H\times g_2H)=f(g_1g_2H)=g_1g_2K=g_1K\times g_2K=f(g_1H)f(g_2H)$。
显然，对于 $gK$，一定有 $gH$ 能映射到它，因此 $f$ 是满同态。由同态基本定理得：$\frac{G/H}{\ker f}=\frac{G}{K}$。现在只需要证明：$\ker f=K/H$。
有 $f(gH)=gK=K\Leftrightarrow g\in K\Leftrightarrow gH\in K/H$。于是 $K/H=\ker f$。
轨道稳定集定理
-
给定非空集合 $S$ 和置换群 $G$，这里 $G$ 中元素为置换，二元运算定义为 $f_1\times f_2=f_1\circ f_2$，即先做置换 $f_2$ 再做置换 $f_1$ 得到的置换。
-
设 $F_u={ f(u)|f\in G }$ 为 $u$ 的轨道，$P_u={ f|f(u)=u }$ 为 $u$ 的稳定集，则有 $|F_u||P_u|=G$
证明：值得一提的是 $F_u\subseteq S,P_u\le G$。
考虑 $G$ 的陪集分解：$f_1P_u\cup f_2P_u\cup\cdots f_kP_u$，显然 $f_iP_u$ 中所有的置换作用在 $u$ 上得到的结果相同。而实际上，不同陪集的置换作用在 $u$ 上得到的结果不同，这是因为如果作用的结果相同，不妨设两个置换为 $f_1,f_2$，那么 $f_2$ 肯定可以与若干个 $P_u$ 中的置换复合得到 $f_1$，这与 $f_1,f_2$ 属于不同陪集的前提不相符。
所以，陪集分解的数量应该就是 $|F_u|$，而每个陪集的大小都是 $P_u$，所以可知定理成立。
Bunside 引理
现在给定集合 $S$ 和置换群 $G$，现在定义如果两个 $S$ 中的元素可以通过置换得到，那么就认为它们相等。求本质不同的元素个数。
我们让每个轨道中的元素的贡献是轨道大小分之一即可。即：
$$
\sum\limits_{u\in S}\frac{1}{|F_u|}=\sum\limits_{u\in S}\frac{|P_u|}{|G|}=\frac{1}{|G|}\sum\limits_{p\in G}\sum\limits_{s\in S}[p(s)=s]
$$
后者就是 Burnside 引理的形式。
无标号无向图计数
阿贝尔群基本定理
-
阿贝尔群的任意子群都是正规子群。
-
阿贝尔群的商群也是阿贝尔群。
-
阿贝尔群基本定理内容：对于任意阿贝尔群 $A$，它一定可以唯一的写成：
$$
A\cong \mathbb{Z}{a_1}\times \mathbb{Z}\times \cdots \times \mathbb{Z}_{a_k}\times \mathbb{Z}^r
$$
其中 $a_1|a_2|\cdots |a_k$。$\mathbb{Z}_i$ 为 $\bmod i$ 意义下的加法群。若 $A$ 是有限群，则 $r=0$。
证明过于复杂，略过。
- 给定 $n$ 求 $n$ 阶阿贝尔群的个数，由于 $n$ 很大，以质因数分解的形式给出 $n=\sum\limits_{i=1}mp_i$。$1\le m\le 10^6$。
根据上面的定理内容，我们考虑 $a_1,a_2,\cdots,a_k$ 的值，实际上我们是需要对于每个质数 $p_i$，把它的指数 $a_i$ 拆成若干个数字的，也就是一个划分数，而答案就是若干划分数的乘积。
- 推论：若 $(p,q)=1$，则 $\mathbb{Z}{pq}=\mathbb{Z}\times\mathbb{Z}_q$
证明：只需要证明等号右边是循环群即可，实际上等号右边确实是循环群，生成元是 $(1,1)$。
- 推论：有限的阿贝尔群一定可以写成如下形式：
$$
\prod\mathbb{Z}{p_1}{\alpha_{1,i}}\prod\mathbb{Z}_{p_2}{\alpha{2,i}}\cdots\prod\mathbb{Z}{p_k}^{\alpha{k,i}}
$$
其中 $p_1,p_2,\cdots,p_k$ 是质数。
Lagrange 定理
- 域 $F$ 上的任意 $n$ 次多项式在 $F$ 内至多有 $n$ 个根。
证明：可以简单归纳证明。
- 推论：域 $F$ 上的阿贝尔乘法群 $F^\times$ 的任意有限子群都是循环群。
证明：$f^\times$ 即为 $F$ 域定义中的 $(S/0,\times)$。设子群 $G$，分解可得：
$$
G=\mathbb{Z}{a_1}\mathbb{Z}\cdots\mathbb{Z}_{a_k}
$$
因为 $a_1|a_2|\cdots|a_k$，所以 $G$ 是循环群当且仅当 $k=1$。若 $k>1$，显然 $G$ 中 $1^{F}$ 对应的元素应该是 $(0,0,\cdots,0)$，而对于 $G$ 中的一个元素对应的元素 $(b_1,b_2,\cdots,b_k)$ 来说，其 $a_k$ 次方一定是 $1^F$，所以对于 $F$ 域下的一个方程 $x{a_k}-1F=0^F$ 来说，按照 lagrange 定理，其应该只多有 $a_k$ 个根，但是 $G$ 中的每个元素都是这个方程的根，且一共有 $a_1a_2\cdots,a_k$ 个元素。矛盾。
Z 上的乘法群
令 $\mathbb{Z}_n^\times$ 为 $\bmod n$ 意义下的乘法群，显然 $|\mathbb{Z}_n^\times|=\varphi(n)$。因为群要求有逆元，而只有与 $n$ 互质的数有逆元。
- 欧拉定理：若 $(n,m)=1$ 则 $m^{\varphi(n)}=1\bmod n$。
证明：$m\in Z_n^\times$，设 $m$ 的阶是 $p$，则有 $m^p=1$，而根据 lagrange 定理，有 $p|\varphi(n)$，故成立。
- 定理：若 $(p,q)=1$，则 $\mathbb{Z}{pq}^\times\cong \mathbb{Z}^\times\times \mathbb{Z}_{q}^\times$。
证明：构造映射 $f:\mathbb{Z}{pq}^\times\to \mathbb{Z}^\times\times \mathbb{Z}_q^\times:f(n)=(n\bmod p,b\mod q)$。
证明是同态：$f(nm)=(nm\bmod p,nm\bmod q)=f(n)f(m)$。
证明是双射：根据中国剩余定理，对于右边任意一个 $(a,b)$，可以找出在 $\bmod\ pq$ 下的唯一解 $n$。而 $f(n)=(a,b)$。
所以定理成立。
威尔逊定理
- 设 $p$ 为质数，则 $(p-1)!\equiv -1\bmod p$
- 若 $p$ 为质数，则 $(p^q)!_p\equiv -1\bmod p$，其中 $(n!)_m$ 表示所有小于等于 $n$ 且与 $m$ 互质的正整数的乘积。
证明：若 $n$ 的原根存在，设为 $g$，则 $(n!)_n\equiv g^{\frac{\varphi(n)(\varphi(n)-1)}{2}}\bmod m$。
而 $g^{\varphi(n)(\varphi(n)-1)}\equiv 1$，所以 $(n!)_n$ 要么是 $-1$ 要么是 $1$，取决于 $\varphi(n)|\frac{\varphi(n)(\varphi(n)-1)}{2}$ 是否成立。
因此若 $\varphi(n)$ 是偶数，则乘积为 $-1$，否则乘积为 $1$。
于是两个定理都是显然的。