群论

前置知识：抽象代数基本概念、置换与排列

引入

群论（group theory）主要研究群这个 代数结构。

为了研究群的结构，需要掌握一些基本工具，这包括子群、群同态和群作用。算法竞赛中，主要涉及到的群是数论相关的群（比如整数模 $n$ 乘法群 $(\mathbf{Z}/n\mathbf{Z}{)}^{\times }$）以及置换群，本文将着重介绍相关的概念。本文未涉及的群论部分，比如有限群的结构理论和群的线性表示理论，有兴趣的读者应当参考专业书籍。

理解抽象代数不能够离开实例。作为理解下文概念的例子，这里讨论正三角形的空间对称群 $D_6$。

例子：正三角形的空间对称群 $D_6$

如图所示，对于给定正三角形，共计有六种不同的操作可以使得它与自身重合。

这里，使用 $r$ 表示顺时针旋转，使用 $s$ 表示沿顶点 $1$ 到三角形中心的连线翻转，操作自右向左复合，即 $sr$ 表示先旋转（$r$）再翻转（$s$）。两个操作不同，当且仅当某个三角形的顶点在两个操作之后所处位置不同。

记号	操作	阶	置换表示
$e$	恒等变换，即什么也不做	1	$(1)$
$r$	顺时针旋转 ${120}^{\circ }$	3	$(123)$
$r^2$	顺时针旋转 ${240}^{\circ }$	3	$(132)$
$s$	沿 $1$ 到中心连线翻转	2	$(23)$
$sr$	先旋转 ${120}^{\circ }$，再翻转	2	$(13)$
$s{r}^2$	先旋转 ${240}^{\circ }$，再翻转	2	$(12)$

容易验证，这些操作确实构成了群。比如说，该群的单位元是 $e$，而 $sr$ 的逆元是它自身。而且，群 $D_6$ 并不是交换群，比如可以直接验证 $rs=s{r}^{-1}$。

表中记录的操作并不是该记号对应的唯一的对称操作。比如，「沿 $2$ 到中心的连线翻转」也是三角形的对称操作，它不在表中，但它的结果和操作「先旋转 ${120}^{\circ }$，再翻转」相同。表中的「阶」和「置换表示」等概念下文会给予说明。

子群

要理解给定群的结构，可以首先分析其子结构。群的子结构就是那些在同一运算下仍然成为一个群的该群的子集。由此，有如下定义。

例子：正三角形的空间对称群 $D_6$（续）

在 $D_6$ 中，容易验证它的子群有 $\{e\}$，$\{e,s\}$，$\{e,sr\}$，$\{e,s{r}^2\}$，$\{e,r,r^2\}$ 和 $D_6$ 本身，共计六个。除群 $D_6$ 外，这些子群的结构都是更为简单，而且蕴含了关于原来群的部分信息。

要判断给定子集 $H\subseteq G$ 是不是子群，并不需要逐一验证群的定义：结合律自然成立；子集成为子群，只要保证它对二元运算封闭、有单位元且对取逆封闭就好了。事实上，这些条件可以总结在一起。

由子集生成的子群

一般地，给定群 $G$ 中的子集 $S$，从 $S$ 中的元素出发，重复进行乘法和取逆运算有限次，能够得到的所有结果的集合成为 $G$ 的一个子群。这称为由子集 $S$ 生成的子群。

可以证明，任给定这样的子集 $S$，总能找到这样的子群：$⟨S⟩$ 可以构造为所有包含 $S$ 的 $G$ 的子群的交。

例子：正三角形的空间对称群 $D_6$（续）

在群 $D_6$ 中选定旋转操作 $r$，重复应用它和它的逆操作，就得到子群 $\{e,r,r^2\}$。它可以记作 $⟨r⟩$。群 $D_6$ 中的所有非平凡子群都可以通过选定某个操作来生成。

有些子集生成的子群是群本身。这样的子集尤为特殊，称为群的生成子集。

群是自身平凡的生成子集。更为有趣的情形是，生成子集远小于群本身的规模。

例子：正三角形的空间对称群 $D_6$（续）

可以验证，$D_6=⟨s,r⟩$，这就是说，任何正三角形的对称操作都可以通过旋转和翻转的复合得到。

循环群

仅由一个元素生成的群的结构非常简单。这样的群称为循环群。

例子：正三角形的空间对称群 $D_6$（续）

所有 $D_6$ 的非平凡子群以及 $\{e\}$ 都是循环群。

可以证明，循环群的结构由其大小唯一确定。如果循环群无限，则它必然和整数的加法群 $(\mathbf{Z},+)$ 具有相同的群结构，记作 $C_{\mathrm{\infty }}$ 或 $\mathbf{Z}$；否则，记群的元素个数为 $n\in {\mathbf{N}}_{+}$，则它必然和整数模 $n$ 的同余类的加法群 $(\mathbf{Z}/n\mathbf{Z},+)$ 具有相同的群结构，记作 $C_n$ 或 ${\mathbf{Z}}_n$。这一结论的严格叙述需要用到下文的 群同构 的概念，它严格描述了两个群结构相同这一事实。

所有循环群都是 Abel 群。本文的例子 $D_6$ 说明，即使群的所有非平凡子群都是循环群，群本身也可能不是 Abel 群。

阶

群的阶就是群的元素的个数。群内给定元素的阶就是该元素生成的循环子群的阶。由此，有如下定义：

元素的阶总是不大于群的阶，事实上，下文即证明，元素的阶总是整除群的阶。但是，群的阶并非总是元素的阶的最大值，比如 $D_6$ 是六阶群，但是元素的阶最大是 $3$。群的阶也并不是所有元素的阶的最小公倍数，比如 Klein 四元群¹ $V_4$ 的阶是 $4$，但是里面只有 $1$ 阶元和 $2$ 阶元。

定理

有限循环群 $C_n=⟨x⟩$ 中，元素 $x^k$ 的阶是

$$\frac{n}{gcd(k,n)}.$$

特别地，$C_n$ 的生成元的数目是 $\phi (n)$，这里，$\phi (\cdot )$ 是 欧拉函数。

作为上述讨论的应用，注意到模 $n$ 整数乘法群的阶是 $\phi (n)$，群中的任何元素 $a$ 的阶都整除它，故而必然有 $a^{\phi (n)}=1$。这就是 欧拉定理，因为该群中的元素就是所有与 $n$ 互质的元素。

陪集

子群以外的元素在群中的结构也并非杂乱无章。

例子：正三角形的空间对称群 $D_6$（续）

观察 $D_6$ 中的子群 $⟨r⟩$，剩余的元素 $\{s,sr,s{r}^2\}$ 结构和 $⟨r⟩$ 十分相似：它当中的每个操作都可以通过 $s$ 和 $⟨r⟩$ 中的操作复合得到。同理，考虑子群 $⟨s⟩$，则群中的剩余元素可以分为两类，$\{r,sr\}$ 和 $\{r^2,s{r}^2\}$，它们可以通过 $⟨s⟩$ 中的元素分别与 $r$ 和 $r^2$ 复合得到。这样的现象是普遍的。

给定子群，可以定义它的陪集。

陪集

设 $G$ 是群，$H\le G$ 是它的子群，则子群 $H$ 的包含 $g$ 的 左陪集（left coset）和 右陪集（right coset）分别定义为集合

陪集中的元素称为陪集的代表元（representative element）。

子群本身也是其陪集。给定子群，全体陪集构成群的一个分划，即群是全体陪集的不交并。分划总可以看作某个等价关系的等价类。对于左陪集的分划，这个等价关系就是 $g_1\sim g_2$ 当且仅当 $g_1^{-1}{g}_2\in H$；对于右陪集的分划，这个等价关系就是 $g_1\sim g_2$ 当且仅当 $g_1{g}_2^{-1}\in H$。

例子：正三角形的空间对称群 $D_6$（续）

按照陪集的语言，上面的例子中，$D_6$ 可以分别划分成 $⟨r⟩\cup s⟨r⟩$ 和 $⟨s⟩\cup ⟨s⟩r\cup ⟨s⟩r^2$。这里，前者将群划分为若干左陪集，后者将群划分为若干右陪集。应该注意，代表元的选取并无特殊，比如可以验证 $s⟨r⟩=sr⟨r⟩$。陪集中的任何元素都是该陪集的代表元。

同一子群的不同陪集大小都相同，都等于对应子群的大小。由于给定子群的全体陪集构成群的一个分划，有限群的阶必然是子群的阶的整数倍。这叫做 Lagrange 定理。

注意到，元素的阶就是元素生成的循环子群的阶，所以元素的阶也必然整除群的阶。

正规子群

一般情况下，给定子群的左右陪集并不相同。

例子：正三角形的空间对称群 $D_6$（续）

群 $D_6$ 中，$⟨s⟩r=\{r,sr\}$，但是 $r⟨s⟩=\{r,s{r}^2\}$。但是如果考虑子群 $⟨r⟩$，那么左右陪集又总是相同的，因为此时群只有两个陪集，而子群作为一个陪集又必然重合。

左右陪集是否相同，反映了相应的子群的性质。

这个定义中的条件正等价于 $gN=Ng$ 永远成立。群 $G$ 总有平凡的正规子群，即 $⟨e⟩$ 和 $G$ 自身。

例子：正三角形的空间对称群 $D_6$（续）

在群 $D_6$ 中，$⟨s⟩$ 不是正规子群，而 $⟨r⟩$ 是正规子群。

商群

正规子群是非常重要的一类子群，原因之一就是基于正规子群可以定义商群。

对于群 $G$ 和它的正规子群 $N⊴G$，考虑全体陪集的集合

$$G/N=\{gN:g\in G\}.$$

此时，左右陪集相同，不必区分。可以从群 $G$ 的运算出发，定义 $G/N$ 上的二元运算 $\circ$，它满足

$$g_{1}N\circ g_{2}N=(g_1{g}_2)N.$$

可以证明，运算的结果与代表元的选取无关²。此时，$(G/N,\circ )$ 确实具有群的结构，它称为 $G$ 模 $N$ 的 商群（quotient group）。商群 $G/N$ 并不是群 $G$ 的子群，它的每个元素都是群 $G$ 的一个子集。

例子：正三角形的空间对称群 $D_6$（续）

在群 $D_6$ 中，商群 $G/⟨r⟩$ 的意义非常显然。它相当于在所有这些对称操作中，忽视操作中将三角形旋转的角度，而只关注它是否将三角形翻转。两个将三角形翻转的操作的复合相当于没有翻转原三角形；但是，如果两个操作一个翻转了三角形而另一个没有，那么复合也必然翻转了三角形。翻转与否也具有群的结构。从群 $D_6$ 中忽视旋转的细节而只考虑翻转的有无，在代数上就是将复杂的群 $D_6$ 模掉 $⟨r⟩$ 而得到商群 $D_6/⟨r⟩$。这些论述对子群 $⟨s⟩$ 是无效的，因为如果忽视翻转的有无，那么旋转的度数没有办法明确判断的，这也是为什么 $G/⟨s⟩$ 不具有商群的结构。

群的商群可以将复杂的群简化，允许观察群的部分结构来了解原来群的结构。这也是商群也称为 因子群（factor group）的原因。除平凡正规子群外，再不含其他正规子群的群称为 单群（simple group），这些群没有办法简化为更小的群。如同素数一样，它们是组成更复杂的群结构的基石。

群同态

理解给定群结构的第二种方法，是将两个群的结构相互比较。

对于两个群，要比较它们的结构，就是要构造两个群之间的映射。但是，这样的映射并不能是任意的，它们要保持群的结构，也就是要保持群的运算在映射前后一致。这样的映射称为群的同态。

群同态必然将单位元映射到单位元，也必然将逆元映射到逆元。

群同构

对于自群 $G$ 到群 $H$ 的同态 $\phi :G\to H$，一个自然的问题是，这一同态在多大程度上反映了群 $G$ 和群 $H$ 的结构是一致的。为此，考察群 $G$ 在同态 $\phi$ 下的像 $\phi (G)$，它将群 $G$ 的结构映射到群 $H$ 中。一方面，$\phi (G)$ 是群 $H$ 的一个子群；但若同态 $\phi$ 不是满射，$\phi (G)$ 与群 $H$ 并不相同。另一方面，同态 $\phi$ 也未必是单射；如果 $\phi$ 不是单射，那么 $\phi (G)$ 只反映了群 $G$ 的部分结构。只有当同态 $\phi$ 是双射时，群 $G$ 和群 $H$ 的结构才是完全一致的。这种特殊的群同态叫做群同构。

同构的两个群结构完全一致。如果只关心群的结构，两个同构的群没有必要区分。前文关于循环群的分类定理就是在同构的意义下给出的。

例子：正三角形的空间对称群 $D_6$（续）

回到前文的例子，正三角形的每个对称操作都唯一对应了顶点集合上的置换操作。顶点集合上的全体置换也构成群，即 $S_3$。容易验证，这样得到的映射 $\phi :D_6\to S_3$ 是群同态；进一步地，它也是群同构。所以，$D_6\cong S_3$。事实上，六阶群要么同构于 $C_6$，要么同构于 $S_3$（证明见下文）。

对给定阶的有限群的结构进行分类，是群论的重要研究内容，但超出了本文的范畴。

同态的核

对于一般的同态，可以进一步讨论有多少关于群的结构的信息损失在了同态中。延续上文的记号。已知 $\phi (G)$ 是群 $H$ 的子群，现在问题的关键在于 $\phi (G)$ 和群 $G$ 之间的关系。

例子：正三角形的空间对称群 $D_6$（续）

考虑如下定义的映射 $\phi :D_6\to C_2=⟨x⟩$：

$$\phi (e)=\phi (r)=\phi (r^2)=e,\phi (s)=\phi (sr)=\phi (s{r}^2)=x.$$

容易验证，$\phi$ 是群同态；它是满射，但不是单射。它的意义很明显，就是在群的每一个对称操作映射到其翻转的有无。这样的同态压缩的群 $D_6$ 中的信息，就是有关它旋转角度的信息。比如说，如果没有翻转，任何角度的旋转都映射到了群 $C_2$ 中的单位元。

这个例子启发使用 $\{e\}$ 的原像衡量同态中损失的结构信息。为此，有如下定义。

同态基本定理

同态的核 $\ker \phi$ 的确刻画了群同态中损失的结构信息。这一结论的精确表述就是 同态基本定理（亦称 第一同构定理）（fundamental theorem of group homomorphism, a.k.a., first isomorphism theorem）。

也就是说，同态 $\phi$ 的核是群 $G$ 的正规子群，而模 $\ker \phi$ 得到的商群 $G/\ker \phi$ 同构于同态的像 $\phi (G)$，而这一同态的像正是群 $H$ 的子群。

例子：正三角形的空间对称群 $D_6$（续）

上文给出的群同态 $\phi :D_6\to C_2$ 的核是 $⟨r⟩$，前文讨论正规子群时也已经说明 $D_6/⟨r⟩$ 的确同构于 $C_2$。

自然同态

得到这样的结论并不为奇。这是因为在构造同态 $\phi :D_6\to C_2$ 时，利用的正是商群 $D_6/⟨r⟩$ 的几何意义。这样的现象并不罕见。事实上，对每个商群，都可以构造出群同态，使得同态的像同构于给定的商群。

这一结论也说明，对于任何给定群的正规子群，都能够找到对应的群同态，使得这一同态的核就是给定的正规子群。前文同态基本定理则说明，任何同态的核都是正规子群。故而，正规子群和同态的核是一体两面。

利用自然映射的概念，群的同态基本定理其实是在说如下的 交换图（commutative diagram）成立。

这里，所有箭头都是群同态，且 $N=\ker \phi$ 是同态 $\phi$ 的核，$\phi (G)$ 是同态 $\phi$ 的像。这些映射依次是，$\pi :g\mapsto gN$ 为群 $G$ 到商群 $G/N$ 的自然映射（满同态），$\mathrm{\Phi }:gN\mapsto \phi (g)$ 是同构映射，$\iota$ 则是嵌入映射（单同态）。交换图意味着，图中从 $G$ 出发到 $H$ 结束的两条不同路径上的映射的复合得到的结果是一致的，即 $\phi =\iota \circ \mathrm{\Phi }\circ \pi$。交换图清晰地说明，同态 $\phi$ 损失的信息就反映在 $\pi$ 和 $\iota$ 中。

群的同构定理

用于理解群的结构的有力工具，是群的同构定理。前文已经给出第一同构定理。为了内容完整，这里再给出其他常见的同构定理。

第二同构定理涉及到子群的乘积的概念。

子群的乘积并不总是子群。比如，群 $D_6$ 的子群 $A=⟨s⟩$ 和子群 $B=⟨sr⟩$ 的乘积等于 $AB=\{e,s,r,sr\}$，这并不是 $G$ 的子群，因为 $(sr)s=r^2\notin AB$。其实，这种 $a\in A$，$b\in B$，但 $ba\notin AB$ 形式的反例正是乘积不是子群的根本原因。对此，有如下定理。

第二同构定理（second isomorphism theorem, a.k.a., diamond isomorphism theorem）则给出了子群乘积仍是子群的更为简单的充分条件，并且进一步确定了其结构。

第三同构定理（third isomorphism theorem）则给出了商群的正规子群和商群与原来群的正规子群和商群之间的对应关系。它解释了将商群进一步分解这一想法的合理性。

这一结论可以推广到第四同构定理，或称 对应定理（correspondence theorem），它进一步给出了群的子群格和商群的子群格之间的对应关系。

群作用

理解给定群结构的第三种方法，是考察群在集合上的作用。

比如说，本文考察的正三角形的空间对称群就是通过群的元素（即对称操作）在三角形上的作用来定义的。再比如说，对称群 $S_M$ 的定义可以通过它的元素在集合 $M$ 上的作用给出。这里所谓的作用，指的是每个群的元素都对应一个集合上的置换。

对于满足上述定义的群作用，自然有如下构造

这一映射，将每个群 $G$ 中的元素 $g$ 都对应到集合 $X$ 上的一个置换 ${\phi }_g$，且置换 ${\phi }_g$ 将元素 $x$ 映射到 $g\cdot x$。

根据定义，群中的单位元 $e$ 对应的双射 ${\phi }_e$ 是 $X$ 上的恒等映射，而群中元素 $g$ 对应的映射 ${\phi }_g$ 和其逆元 $g^{-1}$ 对应的映射 ${\phi }_{g^{-1}}$ 互为逆映射（这也说明为什么 ${\phi }_g$ 总是双射）。可以验证，${\phi }_{g_1{g}_2}={\phi }_{g_1}{\phi }_{g_2}$，即 $\phi$ 是群 $G$ 到群 $S_X$ 的群同态。

这一群同态 $\phi$ 称为该群作用的 置换表示（permutation representation），它将群 $G$ 映射到了某个置换群上。

该群同态的核也称为该群作用的核。如果这一群同态的核是平凡的，即这个同态是单射，则称该群作用是 忠实的（faithful），即该作用的置换表示忠实地反映了群结构的信息。此时，群 $G$ 与置换表示得到的的置换群同构。

轨道

群作用是二元映射。固定群中的元素 $g$，则可以得到集合上的置换 ${\phi }_g$。而如果固定集合上的元素 $x$，则可以得到群对该元素作用的所有可能的结果。

例子：正三角形的空间对称群 $D_6$（续）

比如说，如果考虑群 $⟨s⟩\le D_6$ 在正三角形顶点集合上的作用，则顶点 $1$ 的轨道是 $\{1\}$，而顶点 $2$ 和 $3$ 的轨道是 $\{2,3\}$。但是，群 $⟨r⟩\le D_6$ 在顶点集合上的作用只有一个轨道，即全体顶点集。

容易证明，群 $G$ 的作用下，集合 $X$ 的全体轨道构成了该集合的一个分划，记作 $X/G$。但是和陪集不同，这些轨道并不一定是等长的。

稳定化子

群作用下，集合中的一个元素的轨道长度取决于有多少群里的元素对应的置换以它为不动点。

例子：正三角形的空间对称群 $D_6$（续）

比如说，之所以在群 $⟨s⟩\le D_6$ 的作用下，顶点 $1$ 的轨道长是一，是因为所有群里的元素都将顶点 $1$ 映到其自身；而顶点 $2$ 的轨道长是二，是因为只有单位元 $e$ 将顶点 $2$ 映射到其自身。

这启发了如下的定义。

群作用的核就是集合中所有元素的稳定化子的交。

例子：正三角形的空间对称群 $D_6$（续）

考虑群 $D_6$ 在顶点集合上的群作用，则顶点 $1$ 的稳定化子是 $\{e,s\}=⟨s⟩$。这是 $D_6$ 的子群。因为 $D_6$ 可以划分成左陪集 $⟨s⟩$，$r⟨s⟩$ 和 $r^2⟨s⟩$，容易发现，每个左陪集对顶点 $1$ 作用的结果是一样的。

这一例子说明，轨道上的元素，都和稳定化子的左陪集一一对应。这说明如下结果。

利用 Lagrange 定理，可以将轨道长和稳定化子的陪集数目联系起来。这就是 轨道稳定子定理（orbit-stabilizer theorem）。

可以在上面的例子中验证这一结论。

Burnside 引理

这一引理给出了群作用的轨道个数公式。

Burnside 引理

对于群 $G$ 在集合 $X$ 上的作用，轨道的个数等于群中每个元素对应置换的不动点的平均个数，即

$$|X/G|=\frac{1}{|G|}\sum _{g\in G}|X^g|.$$

这里，$X^g=\{x\in X:gx=x\}$ 是元素 $g\in G$ 对应置换的不动点集合。

证明

这一定理的证明十分简明。注意到，轨道个数可以写作

$$|X/G|=\sum _{o\in X/G}1=\sum _{x\in X}\frac{1}{|Gx|}=\frac{1}{|G|}\sum _{x\in X}|G_x|.$$

最后一个等号就是上面的推论；而右式和所要求证的只差一个 Fubini 定理，因为它们中的求和式都是对集合 $\{(g,x)\in G\times X:gx=x\}$ 的计数，只不过右式先对 $g$ 求和，而所求证的式子先对 $x$ 求和。

这一定理在组合数学中有很多用处，可以用于统计「本质不同」的对象的数目。更多例子和讨论可以参考 Pólya 计数。

Cayley 定理

利用群作用研究群的结构，需要选取合适的集合。事实上，群自身就是这样一个集合。因此，接下来考虑群对自身的两类常见的群作用，并借此分析群的结构。

第一个这样的群作用是群对自身的 左乘作用（left multiplication）。它的置换表示如下。

群的左乘作用必然是忠实的，因为群满足消去律。所以，由同态基本定理，$G$ 可以嵌入对称群 $S_G$ 中。这意味着，每个群都同构于某个置换群⁴。

这个群作用只有一个轨道，而且，每个元素的稳定化子都是 $\{e\}$。

共轭作用

第二个群到自身的作用叫做 共轭作用（conjugation）。它的置换表示如下。

在群的共轭作用下，轨道和稳定化子都有特别的名字。

群的中心，是与群中所有元素都交换的元素的集合；因为它是群作用的核，它必然是正规子群。群的中心的大小，表明了它和交换群之间的差距。给定元素的中心化子，是与该元素交换的所有元素的集合；也是所有中心包括它的子群中最大的，这也就是它的名字来源；同时，因为它是共轭作用下某元素的稳定化子，所以它是子群。共轭类一般不是子群。

例子：正三角形的空间对称群 $D_6$（续）

回到群 $D_6$，它的中心是 $\{e\}\ne G$，这说明它不是交换群。元素 $r$ 的中心化子 $C_G(r)$ 是 $⟨r⟩$，元素 $s$ 的中心化子 $C_G(s)$ 为 $⟨s⟩$。一般地，对所有 $g\in G$，总成立 $⟨g⟩\le C_G(g)$。群 $D_6$ 的共轭类共三个，即 $\{e\},\{r,r^2\},\{s,sr,s{r}^2\}$。容易发现，共轭的元素都是同阶的⁵。

群在共轭作用下划分成若干个共轭类。所以，可以写出 类方程（class equation）。

类方程

对于群 $G$，设 $\{{\mathcal{K}}_i{\}}_{i=1}^r$ 为全体长度大于一的共轭类，且 $g_i$ 是 ${\mathcal{K}}_i$ 的代表元，成立

$$|G|=|Z(G)|+\sum _{i=1}^r[G:C_G(g_i)].$$

它可以用于分析群的结构，比如用于证明下文的 Sylow 定理。

正规化子和中心化子

事实上，群的幂集也可以是群作用的对象。这里着重讨论群在它的全体子集 $X=\mathcal{P}(G)$ 上的共轭作用。它的置换表示如下。

在这一共轭作用下，同样可以定义群的子集的共轭类。它的核依然是群的中心。它的稳定化子则称为正规化子。

正规化子是共轭作用下 $S$ 的稳定化子，必然是 $G$ 的子群；$S$ 的正规化子是能够使得 $S$ 包含在其正规子群中的子群中最大的，这也是正规化子的名字来源。特别地，对于单元素集合 $\{a\}$，$N_G(\{a\})=C_G(a)$。

中心化子也可以类似地推广到子集的情形。

中心化子实际上是群 $N_G(S)$ 在 $S$ 的共轭作用的核。所以，必然有 $C_G(S)⊴N_G(S)\le G$，所以由子群的传递性，中心化子也是子群。特别地，群的中心 $Z(G)=C_G(G)⊴N_G(G)=G$ 必然是正规子群。

Sylow 定理

进一步地，对有限群的共轭作用进行分析，可以得到 Sylow 定理。它是处理有限群的结构的有力工具，可以迅速地得到大量小阶群的结构。

$p$‑群

对于群 $G$，如果存在素数 $p$ 和正整数 $\alpha$ 使得 $|G|=p^{\alpha }$，则称它为 $p$‑群（$p$-group）。

关于 $p$‑群的定义

$p$‑群还有另外一种定义，即所有元素的阶都是素数的幂的群。这两种定义对于有限群是等价的；但是，第二种定义同样适用于无限群的情形。另外，关于 $p$‑群的定义，不同的文献可能对于是否将 $\{e\}$ 算作 $p$‑群存在分歧，读者在阅读时应当加以分辨。

$p$‑子群

对于群 $G$ 和它的子群 $P\le G$，如果 $P$ 本身是一个 $p$‑群，则称 $P$ 为 $p$‑子群（$p$-subgroup）。

Cauchy 定理保证了 $p$‑子群的存在性。其实，通过更为细致的分析，能够得到更强的结论，即 Sylow $p$‑子群的存在性。

Sylow $p$‑子群

对于群 $G$ 和它的子群 $P\le G$，如果 $|G|=p^{\alpha }m$，$p⟂m$ 且 $|P|=p^{\alpha }$，则称 $P$ 为 Sylow $p$‑子群（Sylow $p$-subgroup）。

也就是说，Sylow $p$‑子群是极大的 $p$‑子群。Sylow 定理断言了 Sylow $p$‑子群的存在性，这提供了 Lagrange 定理的一定程度的逆命题。

证明

为证明第一部分，对 $|G|$ 进行归纳。考虑类方程

$$|G|=|Z(G)|+\sum _{i=1}^r[G:C_G(g_i)].$$

如果 $p\mid |Z(G)|$，那么可以任取中心的 $p$ 阶子群 $N\le Z(G)$，则必然有 $N⊴Z(G)⊴G$，因而，$G/N$ 是更小的群。根据归纳假设，它有 Sylow $p$‑子群 $P/N$，则自然同态下相应的原像 $P$ 就是原来的群 $G$ 的 Sylow $p$‑子群。于是，只要考虑 $p$ 不能整除 $|Z(G)|$ 的情形。此时，可以取 $g_i\in G$，使得 $p$ 不能整除 $[G:C_G(g_i)]$，因而，$|G|$ 中 $p$ 的全部幂次都出现在 $|C_G(g_i)|$ 中。再次根据归纳假设，$|C_G(g_i)|$ 有 Sylow $p$‑子群 $P$，它正是原来的群 $G$ 的 Sylow $p$‑子群。

为证明第二部分和第三部分，设群 $G$ 的 Sylow $p$‑子群 $P$ 的共轭类为 $\mathcal{S}=\{gP{g}^{-1}:g\in G\}$，并考察群 $G$ 在 $\mathcal{S}$ 上的共轭作用限制在某一 $p$‑子群 $Q$ 上的结果。集合 $\mathcal{S}$ 可以在该作用下可以划分成若干轨道。设总共有 $r$ 个轨道，每个轨道的代表元为 $P_i$，则有恒等式

$$|\mathcal{S}|=\sum _{i=1}^r[Q:Q\cap N_G(P_i)].$$

这里，$Q\cap N_G(P_i)$ 是 $P_i$ 在上述群作用下的稳定化子。设 $H=Q\cap N_G(P_i)$，则显然 $H\le N_G(P_i)$，故而根据群的第二同构定理，有 $P_{i}H/P_i\cong H/(P_i\cap H)$。所以，$|P_{i}H|=|P_i||H|/|P_i\cap H|$，而右侧是 $p$ 的幂，左侧必然也是 $p$ 的幂，而且需要成立 $|P_i|\le |P_{i}H|$。但是，$P_i$ 已经是 $G$ 的子群中 $p$ 的幂次最大的，所以 $P_i=P_{i}H$。代入前文的同构关系中，就有 $H=P_i\cap H=Q\cap P_i$。这里用到了显然的关系 $P_i\le N_G(P_i)$。这样，就知道稳定化子 $Q\cap N_G(P_i)$ 实际上就是 $Q\cap P_i$。所以，上式可以写作

$$|\mathcal{S}|=\sum _{i=1}^r[Q:Q\cap P_i].$$

这一等式对于所有 $p$‑子群 $Q$ 都成立。

自然，Sylow $p$‑子群 $P$ 也是 $p$‑子群。将 $P$ 代入上式中的 $Q$，则右侧有且仅有一项的大小是 $1$，其余都是 $p$ 的倍数。因此，Sylow $p$‑子群 $P$ 的共轭类的大小 $|\mathcal{S}|$ 必然模 $p$ 余 $1$。同时，因为这一式子对于任何 $p$‑子群 $Q$ 都成立，就自然存在 $g\in G$，使得 $Q\le gP{g}^{-1}$；否则，对所有上述等式中的 $P_i$ 都有 ，就与 $|\mathcal{S}|\equiv 1(\mathrm{mod}p)$ 矛盾。如果此时再考虑 $Q$ 是某个不同于 $P$ 的 Sylow $p$‑子群，则必然有 $Q=gP{g}^{-1}$ 对某个 $g\in G$ 成立，即所有 Sylow $p$‑子群都共轭。因而，Sylow $p$‑子群的数目 $n_p$ 就是 $|\mathcal{S}|$，它必然满足 $n_p\equiv 1(\mathrm{mod}p)$。最后，注意到 $n_p=|\mathcal{S}|=[G:N_G(P)]$，且 $P\le N_G(P)$，就成立 $n_p\mid m$。这样就完整地证明了定理的第二部分和第三部分。

应用：同构意义下，六阶群只有 $C_6$ 和 $S_3$

设 $G$ 的阶是 $6$。那么，根据 Sylow 定理，它有 Sylow $2$‑子群，且它的数目满足 $n_2\equiv 1(\mathrm{mod}2)$ 和 $n_2\mid 3$，所以，只有两个情形：$n_2=1$ 或 $n_2=3$。同理，可以证明群 $G$ 有且只有一个 Sylow $3$‑子群，即 $n_3=1$。

对于 $n_2=1$ 的情形，可以发现群 $G$ 中有一个 Sylow $2$‑子群，故而有一个 $2$ 阶元；又有一个 Sylow $3$‑子群，故而有两个 $3$ 阶元。群 $G$ 还有一个单位元，而剩下的元素，根据 Lagrange 定理，它的阶数必须整除 $6$。又不能是新的 $2$ 阶或 $3$ 阶元，否则会出现与前文不同的新的 Sylow $p$‑子群；所以，剩下的元素只能是 $6$ 阶元。存在和群的阶数相同的元素，这意味着群 $G$ 是循环群，所以 $G\cong C_6$。

对于 $n_2=3$ 的情形，群 $G$ 有三个共轭的 Sylow $3$‑子群。考虑群 $G$ 在这三个 Sylow $3$‑子群上的共轭作用。对于任何一个 Sylow $3$‑子群 $P$，根据 Sylow 定理，有 $|N_G(P)|=2$；但又有 $P\le N_G(P)$，所以 $P=N_G(P)$。因此，这三个 Sylow $3$‑子群的正规化子的交集，即这个共轭作用的核，是平凡的。所以，这个作用是忠实的，它将 $G$ 嵌入到了这三个 Sylow $3$‑子群上的置换群 $S_3$。但是，因为 $|G|=|S_3|$，必然有 $G\cong S_3$。

有限生成 Abel 群

在掌握分析群结构的基本工具后，现在重点讨论一类群的结构。

在概述中提到，Abel 群因为元素可以交换，结构相较于其它群更为简单。其中尤为简单的是那些可以通过有限多个元素生成的 Abel 群。

本节的分类定理说明，有限生成的 Abel 群可以看作是有限多个的循环群的简单组合。算法竞赛中涉及的群多为有限群。有限 Abel 群必然是有限生成的，因此总是适用这一结论。

直积

前文对群的分析主要集中在如何将群分解为更小的群；相反地，自然可以讨论如何将两个群组合成更大的群。在所有可能的组合方式中，群的直积是最为简单的一种。

群的直积的基本想法是，给定两个群 $G$ 和 $H$，考虑其笛卡尔积 $G\times H$，二元对 $(g,h)$ 的运算定义为对两分量分别运算，分量之间互不影响。这样得到的结果显然是更大的群，且原来的两个群可以平凡地嵌入新的群中。

对于直积 $G\times H$，平凡地有嵌入映射 $g\mapsto (g,e_H)$ 和 $h\mapsto (e_G,h)$。反过来，映射 $(g,h)\mapsto g$ 和映射 $(g,h)\mapsto h$ 是群同态，同态的核分别是 $\{e_G\}\times H$ 和 $G\times \{e_H\}$。这两个核恰好是上述嵌入映射的像，且它们的交集是平凡的，即 $\{(e_G,e_H)\}$。所以，群的直积 $G\times H$ 中有两个子群，都是正规子群，交集是平凡的，且它们的乘积就是直积 $G\times H$ 本身。

这样的分析其实给出了一个群能够写成它的两个子群的直积的充分必要条件。