群论基础

· · 算法·理论

第一节：群的基础定义

群的定义

群是一个集合和二元运算的二元组，例如 (G,\times)（也可以直接记为 G），其中 G=\{\dots,g_i,\dots\}，而 \times 是一个二元运算。它必须满足：

  1. 封闭性：\forall a,b\in G，必须满足 a\times b\in A。
  2. 结合律：\forall a,b,c\in G，必须满足 (a\times b)\times c=a\times (b\times c)。
  3. 有幺元（又称单位元）：恰好存在一个 e\in G 满足 \forall f\in G \Rightarrow f\times e=e\times f=f，其中 e 被称为群 G 的幺元。
  4. 有逆元：\forall a\in G，恰好存在一个 b\in G 使得 a\times b=b\times a=e。（当然，这里的 e 是群 G 的幺元）

这里，可以把 a\times b 简写成 ab；将 a 的逆元简写成 a^{-1}；用 a^n\ (n\in N) 表示 n 个 a 相乘，特别的，a^0=e。

理解：可以举一个例子。例如，对于三阶魔方的所有合法状态 g（合法状态指能被还原的状态）构成集合 G；同时，我们还可以认为每个状态对应一个操作，这个操作是先将魔方染一层色，让它看起来已被还原，然后将魔方拧成这个状态，然后把染的色擦掉，露出原本的颜色；然后，对于所有 a,b\in G，我们可以定义运算 a\times b 指（对还原的魔方）先做 a 操作，然后做 b 操作得到的状态。

接着，我们希望对群做定义，使得 (G,\times) 是一个群。首先，魔方处于合法状态时，不论如何转动，都将仍是合法状态，所以群应当有封闭性。其次，对于 a,b,c\in G，我们依次做操作 a,b,c 得到的结果，和先将 b,c 结合成一个“魔方公式” b\times c，然后依次做 a 及 b\times c 所得到的结果应该是一样的，所以群应当有结合律。对于一个魔方的状态，我们也可以对它什么都不做，这就是幺元 e\in G；如果将魔方变为其他状态，魔方的状态就一定会改变 （这不是废话吗），所以幺元是唯一的。对于魔方的一个状态 a，想把它还原，并且只能进行一个操作的话，这个操作应该是唯一的，如果记它为 a^{-1}，那应当有 a\times a^{-1}=a^{-1}{\times} a=e，所以，群应当有逆元。

关于逆元的小性质 (a\times b)^{-1}=b^{-1}\times a^{-1}

有群 G，若 a,b\in G，则 (a\times b)^{-1}=b^{-1}\times a^{-1}。

推导：

设 y=(a\times b)^{-1}，则：

\begin{aligned} & y=(a\times b)^{-1}\\ \Rightarrow & y^{-1}=a\times b\\ \Rightarrow & e=a\times b\times y\\ \Rightarrow & a^{-1}=b\times y\\ \Rightarrow & b^{-1}\times a^{-1}=y\\ \end{aligned}

证毕。

其实，很容易推广为

(a_1\times a_2\times\cdots\times a_n)^{-1}=a_n^{-1}\times a_{n-1}^{-1}\times\cdots\times a_1^{-1}

有限群和无限群的定义

如果群 G 的元素（也可称为群元）个数为 n\in\mathbb N，那么 G 为 n 阶群，还是有限群；如果 G 的元素个数有无穷个，那么它为无限群。

定义 |A| 表示群 A 的阶。

Abel 群的定义

Abel 群，还被称为阿贝尔群或交换群。群 G 是 Abel 群当且仅当 \forall a,b\in G\Rightarrow a\times b=b\times a；即运算满足交换律。

例如，魔方的上层的所有合法状态构成 Abel 群。

Abel：亚伯（《圣经》故事中亚当和夏娃的次子，被其兄该隐所杀）

重排定理

有群 G=\{\dots,g_i,\dots\}，则 \forall u\in G，当 g_i 取遍 G 的所有元素时，u\times g_i（或 g_i\times u）给出且仅仅一次给出 G 的所有元素。

简单证明：\forall g'\in G，如果希望 g' 被给出，那么必须 \exists g_i\in G 使得 u\times g_i=g'。显然，只能取 g_i=u^{-1}\times g' ，而 u^{-1} 是唯一的，所以 g_i 唯一。证毕。

子群的定义

设 H 是 G 的一个子集，并且满足，对于同样的运算 \times，H 也构成一个群，那么 H 被称为 G 的子群。（记作 H\leq G）

例如，\{e\} 和 G 就是 G 的子群，但他们太过显然，所以被称为平凡子群（或平庸子群）。而非平凡子群也被称为固有子群。

群元的阶

对于有限群 G，从中取一个元素 a，那么必然可以构造出一个子群 Z_k=\{a^1,a^2,\dots,a^k\}，还满足 a^k=e；则称 a 的阶是 k，还称 Z_k 是循环群。

简单证明：实际上，只需要证明 a^k=e 就很容易说明 Z_k 满足群的性质了。所以，来证 a^k=e。

因为 G 的元素个数有限，并且只要确定了一个群元 g，a\times g 也随之确定了，所以 Z_k 肯定是有循环的。但这种循环可能是混循环，即可能 a^{k+1}=a^t\ (1< t\leq k)，并且 k 处是第一个发生循环的地方，即 \forall 1\leq j<i\leq k\Rightarrow a^j\neq a^i。假设这种情况发生了，那么有 a\times a^k=a\times a^{t-1}，两边左乘 a^{-1} 得到 a^{k}=a^{t-1}，显然，此时 1\leq t-1<k\leq k，这与之前的不等式矛盾！证毕。

第二节：陪集相关

陪集的定义：大小相等

设 H 是 G 的子群，对于 g\in G，可以生成左陪集 gH=\{g\times h|h\in H\} 和右陪集 Hg=\{h\times g|h\in H\}。

实际上，可以证明，陪集 gH （或 Hg）的元素个数和 H 的元素个数相等的。因为 \forall t\in gH，只有唯一的 h\in H 满足 g\times h=t，否则假设 h_1,h_2\in H,\ h_1\neq h_2 都满足 g\times h_1=g\times h_2=t，可以推得 h_1=h_2，矛盾。

这也预示着函数 f(x)=u\times x 是可以双射的函数。

还有一件事，就是陪集之所以不叫“陪群”是因为它不一定是群。（很容易构造证明）

陪集定理：（不等则）交集为空

设群 H 是 G 的子群，则 H 的两个左（或右）陪集要么相等，要么没有公共元素。

简单证明：\forall g_1,g_2\in G，如果 g_1=g_2，那么命题显然成立，所以我们讨论 g_1\neq g_2 的情况。同时，右陪集的证明过程和左陪集的一样，所以这里只证左陪集的。

在朴素的思维中，g_1H 和 g_2H 有三种关系：

  1. g_1H=g_2H
  2. g_1H\neq g_2H$ 且 $g_1H\cap g_2H\neq \varnothing
  3. g_1H\cap g_2H= \varnothing

而需要证的命题说第 2 种情况不存在。那么假设 g_1H\neq g_2H 且 g_1H\cap g_2H\neq \varnothing，则至少存在一组 h_1,h_2\in H 满足 g_1h_1=g_2h_2。\forall g_1h_i\in g_1H，则必然仅存在一个 h_j\in H 满足 h_i=h_1h_j（因为 h_j 只能取 h_1^{-1}h_i），所以可以推导：

g_1h_i=g_1h_1h_j=g_2h_2h_j

其中，因为 h_i 能取遍 H，根据重排定理和 h_j=h_1^{-1}h_i 可得 h_j 可以（取遍 H），同理 h_2h_j 也可以，所以 g_1H=g_2H，矛盾！证毕。

Lagrange 定理（拉格朗日定理）：阶是因子

有限群 G 的子群 H 的阶，必为 G 的阶的因子。

简单证明：如果我们希望将 H 变成 G，那么可以不断向 H “加入” G 有但 H 没有的元素。不妨来仔细考察这个过程。

对于 g\in G,g\not\in H，设 g 是 k 阶群元，那么在把 g 加入 H 的同时，为了让 H'（H' 是 H 加入了 g 和一些其他元素）还是群，至少还要让

H'= H\cup g^1H\cup g^2H\cup\cdots\cup g^{k-1}H

现在，我们证明为什么是上面这个式子。

首先，e\in H，得到 g=g\times e\in H'，这说明我们的确把 g 加进去了。

其次，我们要证它仍是群。因为 H\subseteq H'，所以幺元 e\in H'。至于 \forall h_i'\in H' 的逆元，考虑到 h_i' 一定可以写成 h_i'=g^th_i\ (0\leq t< k,\ h_i\in H)，所以 h_i'^{-1} 可以是 g^{k-t}h_i^{-1}，显然，H'\subseteq G，所以 h_i'^{-1} 也是唯一的。

接着，在考察 g^tH\ (0\leq t<k) 们之间的关系，根据陪集定理，她们之间两两要么相等，要么没有公共元素，而 |g^tH|=|H|，所以 |H| 是 |H'| 的因子。

那么，经过一系列对 H 的“添加”后，它终于变成了 G，但是每个“添加”都使得它的阶扩大到了它的自然数倍，所以 |H| 是 |G| 的因数。证毕。

第三节：群在单个元素上的作用

请先了解前置知识，循环群 C_n、置换群 S_n、二面体群 D_n。详见常见群简介。（可能也不够“详”）

置换群的介绍

群作用（元素）的定义

首先了解群 G 对元素 x（不一定满足 x\in G）的作用。首先，我们可能需要扩展 \times 的定义，让 \forall g\in G，g\times x 被定义。不过，定义时需要满足以下两个性质：

作用的结果称为 G 的 x 轨道，记作 \operatorname{Orb}(x) （真的有人会这么记吗） ，而 \operatorname{Orb}(x) 是一个集合，可以认为：

\operatorname{Orb}(x)=\{g\times x|g\in G\}

理解：例如，我们有一个 S_3 群，其中每个元素都是一个置换操作，但是总是置换有序序列 (1,2,3) 未免有些乏味，不妨来置换一下元素 x=(1,2,2)，那么置换的结果就是 S_3 的 x 轨道，枚举发现：

\operatorname{Orb}(x)=\{(1,2,2),(2,1,2),(2,2,1)\}

这让我们知道，|\operatorname{Orb}(x)|=3。

在这一过程中，我们允许 x 也参与乘法运算，但令人伤心的是，\times 不再保证有封闭性和唯一的逆元了，还好单位元还存在，结合律也满足。

稳定子群的定义

有群 G 和集合 X，定义，关于 x\in X，G 的稳定子群 \operatorname{Stab}(x)=\{g|g\times x=x,\ g\in G\}。

理解：还是刚刚 S_3 作用 x=(1,2,2) 的例子，我们发现有的群元 s\in S_3 作用在 x 身上像没作用一样，即 s\times x=x，所以，我们让她们构成一个集合 \operatorname{Stab}(x)，枚举发现，她们分别是：

\operatorname{Stab}(x)=\left\{ \left(\begin{matrix} 1&2&3\\ 1&2&3 \end{matrix}\right) , \left(\begin{matrix} 1&2&3\\ 1&3&2 \end{matrix}\right) \right\}

于是，我们得知 |\operatorname{Stab}(x)|=2。

然后我们发现，\operatorname{Stab}(x) 好像也是一个群！接着，我们将证明”稳定子集“都是群。

简单证明：（稳定子“集“都是群）

考虑封闭性，\forall a,b\in \operatorname{Stab}(x)\Rightarrow a\times b\times x=x，\therefore (a\times b)\times x=x，\therefore a\times b\in \operatorname{Stab}(x)；考虑结合律，x\not\in \operatorname{Stab}(x)，所以 \times 还是群 G 的那个“旧”乘号（没有经过扩展），自然满足结合律；考虑单位元，设 e\in G 是 G 的单位元，\because e\times x=x，\therefore e\in \operatorname{Stab}(x)，所以 \operatorname{Stab}(x) 有单位元，又 \because x\not\in \operatorname{Stab}(x)，所以单位元是唯一的；考虑逆元，设 a\in \operatorname{Stab}(x)，则 a\times x=x，不妨设 a^{-1}\times x=y，则移项得 x=a\times y，假设 x\neq y，则 x=a\times y\neq a\times x，矛盾，所以只能有 x=y，所以 a^{-1}\in \operatorname{Stab}(x)，而 \operatorname{Stab}(x)\subseteq G，所以 a^{-1} 唯一。证毕。

轨道稳定子群定理 |G|=|\operatorname{Orb}(x)|\cdot|\operatorname{Stab}(x)|

对于群 G （有限群）作用在元素 x 上，有：

|G|=|\operatorname{Orb}(x)|\cdot|\operatorname{Stab}(x)|

简单证明：不妨设群 S=\operatorname{Stab}(x)，集合 O=\operatorname{Orb}(x)。因为 S\leq G，所以根据拉格朗日定理，一定存在 k\ (k\geq 1) 个元素 g_1,g_2,\dots,g_k\in G（其中 g_k=e，e 是 G 的单位元），可将 G 划分为 k 个不交的陪集：

G=\bigcup_{i=1}^k g_iS

（其中 \forall g_i\neq g_j,1\leq i,j\leq k\Rightarrow g_iS\cap g_jS=\varnothing）

考虑其中的一个陪集 g_iS\ (1\leq i\leq k)，\forall s\in S\Rightarrow s\times x=x，所以 \forall g_is\in g_iS\Rightarrow (g_is)x=g_ix，因为 g_ix\in O，所以我们可以认为，从每个陪集 g_iS 到 O 的元素有某种对应关系；现在，我们想证明这种对应是一一对应关系，这样就能说明 k=|O|，再根据 \forall g_i\Rightarrow |g_iS|=|S| 说明 |G|=|O|\times |S| 了。

考虑证明一一对应关系。\forall g_i\neq g_j,1\leq i,j\leq k，我们发现 \forall g_is\in g_iS\Rightarrow (g_is)x=g_ix，同理 \forall g_js\in g_jS\Rightarrow (g_js)x=g_jx，现在，我们想证明 g_ix\neq g_jx；假设 g_ix=g_jx，那么移项得 g_j^{-1}g_ix=x，所以 g_j^{-1}g_i\in S，所以 g_i=g_j(g_j^{-1}g_i)\in g_jS，但是 e\in S，所以 g_i\in g_iS，这说明 g_iS\cap g_jS\neq\varnothing，矛盾！所以，g_ix\neq g_jx。这告诉我们不同的 g_iS 所对应的 O 中的元素是不同的，这就能说明一一对应性了，证毕。

第四节：群在集合上的作用

群作用（集合）的定义

现在，我们定义群 G 作用在集合 X 上相当于群 G 分别作用在 X 的每个元素上，所以，作用的结果为：

\{g\times x\mid g\in G,x\in X\}

等价类的定义

然后，我们发现，如果满足 \forall g\in G,x\in X\Rightarrow g\times x\in X，那么 G 在 X 上的轨道还会满足某种“封闭性”。所以，我们可以定义一个类似于 \operatorname{Orb}(x) 的东西：（记作 [x]）

[x]=\{y\mid y\in X,y\in \operatorname{Orb}(x)\}

我们称之为 x 等价类。注意，我们判断两个等价类是否相同并非看中括号中的元素是否相同，而是用集合的“等于”关系判断。

实际上，她还有一个等价定义：

[x] = \{ y \in X \mid \exists g \in G \Rightarrow g \cdot x = y \}

容易发现，x\in[x]，因为 x\in \operatorname{Orb}(x)。受到配集划分群的启发，我们希望把集合 X 划分为一些等价类。不妨定义轨道空间 X/G（读作 X mod G）为所有等价类的集合，则有：

\begin{aligned} & X/G=\{[x]\mid x\in X\}&①\\ & X=\bigcup_{[x]\in X/G} [x]&② \end{aligned}

其中，① 是定义，但是 ② 只是我们的一个“美好愿望”；那么，能否证明 ② 成立呢？实际上，等价类有如下一些性质，它们可以说明 ② 的正确性。

不动的元素集合的定义

模仿稳定子群的定义，我们可以定义集合 X 在群元 g 作用下的不动的元素集合 X^g：

X^g=\{x\mid g\times x=x,\ x\in X\}

Burnside 引理

对于群 G 和集合 X，满足 \forall g\in G,x\in X\Rightarrow g\times x\in X，则有：

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

推导：

\begin{aligned} |X/G| &= \sum_{[x]\in X/G}1\\ &= \sum_{[x]\in X/G}\sum_{y\in [x]}\frac{1}{\big|[x]\big|}\\ &= \sum_{[x]\in X/G}\sum_{y\in X}\frac{1}{\big|[x]\big|}\cdot \big[y\in [x]\big]\\ &= \sum_{y\in X}\sum_{[x]\in X/G}\frac{1}{\big|[x]\big|}\cdot \big[y\in [x]\big]\\ &= \sum_{y\in X}\frac{1}{\big|[y]\big|}\\ &= \sum_{y\in X}\frac{1}{|\operatorname{Orb}(y)|}\\ &= \sum_{y\in X}\frac{|\operatorname{Stab}(y)|}{|G|}\\ &= \frac{1}{|G|}\sum_{x\in X}|\operatorname{Stab}(x)|\\ &= \frac{1}{|G|}\sum_{x\in X}\sum_{g\in G}[g\times x=x]\\ &= \frac{1}{|G|}\sum_{g\in G}\sum_{x\in X}[g\times x=x]\\ &= \frac{1}{|G|}\sum_{g\in G}|X^g| \end{aligned}

推导完毕。