【学习笔记】群论入门

前言

群除我会，来学一波。

本学习笔记基本参考【IOI2020 论文集】虞皓翔，浅谈群论在信息学竞赛中的简单应用

置换

懂得都懂，需要注意几点：

置换复合： $(f\circ g)(i)=f(g(i))$。

置换的循环分解、循环指标

循环分解实际上就是看这个置换拆成多少环。形如：

$$ g=(a_{1,1},a_{1,2}\cdots a_{1,L_1})(a_{2,1},\cdots,a_{2,L_2})\cdots(a_{k,1},\cdots,a_{k,L_k}) $$

循环指标就是把上面的 $\{L_k\}$ 拿出来，设 $c_i$ 表示 $L_k=i$ 的有多少个，则 $g$ 的循环指标是 $t_1^{c_1}t_2^{c_2}\cdots t_{n}^{c_n}$。其中的 $t_i$ 一般认为没有实际意义，和形式幂级数里的 $x$ 差不多。

群

定义非空集合 $G$ 和定义在该集合上的一个二元运算 $\circ$ 的二元组 $(G,\circ)$ 是一个群，需要满足：

• $\forall x,y\in G,x\circ y\in G$（封闭性）
• $\forall x,y,z\in G,(x\circ y)\circ z=x\circ(y\circ z)$（结合律）
• $\exists g\in G, \forall x\in G, x\circ e=e\circ x = x$（单位元/幺元）
• $\forall x\in G,\exists y\in G,x\circ y=y\circ x=e$，称 $y$ 为 $x^{-1}$（逆元）

群不一定要满足交换律。

交换群：$(G,\circ)$ 满足交换律时，称其为交换群。

陪集和 $\text{Lagrange}$ 定理

陪集：群 $G$ 和其子群 $H$，对于元素 $g\in G$，设 $gH=\{g\circ h|h\in H\}$ 是 $H$ 在 $G$ 中导出的左陪集；类似地定义右陪集。

易于证明，对于一个 $H$，导出的所有陪集大小相等。还有结论：

对于 $H$ 导出的两个陪集 $H_1,H_2$，要么 $H_1=H_2$，要么 $H_1\cap H_2=\varnothing$。

反证法：若 $a,b\in G$，$h_1,h_2\in H$，$a\circ h_1=b\circ h_2$，则 $a=b\circ(h_2\circ h_1^{-1})\in bH$，因此 $aH\subseteq bH$，同样可以证明 $bH\subseteq aH$，所以 $aH=bH$。

$\text{Lagrange}$ 定理：对于 $G$ 与其子群 $H$，有 $|G|=|H||G:H|$，其中 $|G:H|$ 是 $H$ 导出的不同陪集个数。

根据上面两个结论，显然可得。

置换群、$\text{Polya}$ 定理与 $\text{Burnside}$ 引理

染色：$n$ 元染色表示给集合中的每个元素分配一个颜色（物品）的方案。

设 $\mathbf{c}$ 表示一个染色，$\mathbf{c}_i$ 表示元素 $i$ 的染色。$C$ 是所有染色的集合。

显然可以将一个置换作用于一个染色。

轨道和稳定子群

轨道：对于置换群 $G$ 和染色 $\mathbf{c}$，定义轨道 $G\cdot\mathbf c$ 为：

$$ G\cdot \mathbf{c}=\{g\circ \mathbf{c}|g\in G\} $$

也就是把置换群中的每一种置换都作用于 $\mathbf{c}$ 所能得到的染色集合。

可以这样理解“轨道”：可以认为是一个染色 $\mathbf{c}$ 随便选择一个置换作用于自己，总会落到这样一个集合（轨道）中。但是这个符号和稳定子群的符号真的好难记

因此 $G\circ \mathbf{c}$ 是置换群 $G$ 中任意置换作用于 $\mathbf{c}$ 所能得到的所有染色的集合。

而稳定子群，和轨道差不多是一种“相反”或者说“对立”的概念。

稳定子群：对于置换群 $G$ 和染色集合 $\mathbf{c}$，置换群中满足 $g\circ \mathbf{c}=\mathbf{c}$ 的所有 $g$ 构成一个群 $G_{\mathbf{c}}$，称作 $\mathbf{c}$ 的稳定子群。

可以理解为：当固定的染色 $\mathbf{c}$ 在稳定子群中任意选择一个置换，作用于自己，所得还是自己，所以叫“稳定子群”。也可以记成：因为只有 G 是个群所以稳定子群里面的元素肯定是置换

可以认为轨道是对染色的筛选，稳定子群是对置换的筛选。

轨道—稳定子群定理

给出上面两个东西的定义，不难“感觉”到，对于一个特定的轨道 $G\cdot \mathbf{c}$，其中所有 $\mathbf{c}'\in G\cdot \mathbf{c}$，他们的稳定子群大小加起来可能有一些特殊的性质。

我们直接给出定理：

轨道—稳定子群定理：对于置换群 $G$ 与染色 $\mathbf{c}$，有 $|G\cdot \mathbf{c}||G_{\mathbf{c}}|=|G|$。

首先感性的认知一下：$|G\cdot \mathbf{c}|$ 是置换群 $G$ 中任意元素作用于 $\mathbf{c}$ 所能得到的不同染色个数。而 $|G_\mathbf{c}|$ 是作用于 $\mathbf{c}$ 而使得 $\mathbf{c}$ 不变的置换个数。

再来证明：

任意取一个 $g\in G$，考虑左陪集 $gG_\mathbf{c}=\{g\circ h|h\in G_{\mathbf{c}}\}$，又对于任意 $h\in G_{\mathbf{c}}$，有 $h\circ \mathbf{c}=\mathbf{c}$，所以对于 $gG_\mathbf{c}$ 中任意置换 $f$，有 $f\circ \mathbf{c}=g\circ h_0\circ \mathbf{c}=g\circ \mathbf{c}$。因此 $gG_{\mathbf{c}}$ 中所有元素作用于 $\mathbf{c}$ 产生相同的染色。

再考虑证明两个不同左陪集不存在相同元素。对于左陪集 $g_1G_{\mathbf{c}}$ 和 $g_2G_{\mathbf{c}}$，若有：$g_1\circ \mathbf{c}=g_2\circ \mathbf{c}$，则 $g_1^{-1}\circ (g_2\circ \mathbf{c})=g_1^{-1}\circ g_1\circ \mathbf{c}=\mathbf{c}$，所以 $g_1^{-1}\circ g_2\in G_{\mathbf{c}}$，因此 $g_2\in g_1G_{\mathbf{c}}$。与假设不符。

再根据上面的 $\text{Lagrange}$ 定理：$|G|=|G:H||H|$，有 $|H|=|G_{\mathbf{c}}|$，$|G:H|$ 是 $H$ 导出的陪集个数，这恰好是 $|G\cdot \mathbf{c}|$。于是就证完了。

$\text{Burnside}$ 引理

正片开始

再来一个和上面定义看起来很像的定义

不动点：对于 $g\in G$ 和一个染色集合 $X\subseteq C$，定义不动点 $X^g$ 为使得 $g\circ \mathbf{c}=\mathbf{c}$ 的 $\mathbf{c}$ 所组成的集合。

这就是稳定子群中反过来一样，对一个固定的置换，筛选染色。

染色的等价：称两个染色 $\mathbf{c_1},\mathbf{c_2}$ 等价，当且仅当下面条件之一成立：

• $\mathbf{c_1}\sim \mathbf{c_2}$。
• $\exists g\in G$ 使得 $g\circ \mathbf{c_1}=\mathbf{c_2}$。
• $\mathbf{c_2}$ 在 $\mathbf{c_1}$ 的轨道中。
• $\mathbf{c_1},\mathbf{c_2}$ 所在的轨道相同。

实际上都是一个意思

因此，$X$ 中不等价的染色个数，可以看作是其中所有染色在 $G$ 上形成的轨道个数。

设 $X/G$ 是 $X$ 中所有染色在 $G$ 上形成的轨道的集合，$|X/G|$ 是该集合的大小，也就是形成的轨道个数，则：

$\text{Burnside}$ 引理：对于置换群 $G$ 与染色集合 $X$，有：

$$ |X/G||G|=\sum_{g\in G}|X^{g}| $$

也就是不同轨道个数=所有置换的不动点个数的平均值。

证明：

考虑计算 $s=\{(g,\mathbf{c})|g\circ \mathbf{c}=\mathbf{c},g\in G,\mathbf{c}\in X\}$ 的大小。也就是 $g$ 在 $\mathbf{c}$ 的稳定子群中，$\mathbf{c}$ 是 $g$ 的不动点。考虑从 $\mathbf{c}$ 的角度枚举，则就是所有染色的稳定子群大小之和：

$$ s=\sum_{\mathbf{c}\in X} G_{\mathbf{c}} $$

再考虑从 $g$ 的角度枚举，则就是所有置换的不动点个数之和：

$$ s=\sum_{g\in G}|X^g| $$

因此：

$$ \sum_{\mathbf{c}\in X} G_{\mathbf{c}}=\sum_{g\in G}|X^g| $$

右侧已经是我们想要的形式了，但是左侧还不太像。考虑轨道—稳定子群定理 $|G|=|G_{\mathbf{c}}||G\cdot \mathbf{c}|$，则 $|G_\mathbf{c}|=\dfrac{|G|}{|G\cdot \mathbf{c}|}$，带入可得：

$$ |G|\sum_{\mathbf{c}\in X}\dfrac{1}{|G\cdot \mathbf{c}|}=\sum_{g\in G}|X^g| $$

考虑 $\sum_{\mathbf{c}\in X}\dfrac{1}{|G\cdot \mathbf{c}|}$ 是什么，对于一个轨道 $G\cdot \mathbf{c}$ 中的每一个元素，都会贡献 $\dfrac{1}{|G\cdot \mathbf{c}|}$ 的权值，那么一整个轨道贡献 $1$。则权值之和恰好就是不同的轨道个数 $|X/G|$。

这样，我们就证明了 $\text{Burnside}$ 引理：

$$ |G||X/G|=\sum_{g\in G} |X^g| $$

正片结束

好的接下来的部分鸽了