群论基础补足

群的陪集和分拆

定义1：设群 $H<G$，对任意 $a \in G$ ，称
$aH=\{ax:x\in H\} \tag1$
为 $G$ 关于 $H$ 的左（右）陪集.

可以证明陪集构成群的一个分拆.先引入如下引理

引理1：设映射
$f:H\to aH \\ x \to ax$
该映射为满射.

证明：

只需证对任意 $x,y \in H$ 有 $x=y \iff f(x)=f(y)$.充分性显然.必要性根据群的消去律也是显然的.

同时可以有如下论断

论断1：对于群 $H<G$ ，不同元素 $a,b$ 生成的陪集 $aH,bH$ 要么相等，要么不交。

证明：

假设 $aH \cap bH \neq \empty$， $ah_1 = bh_2 \in aH \cap bH$，由对称性只需证 $aH \subset bH$. 任取 $ah \in aH$，就有 $ah = (bh_2h_1^{-1})h=b(h_2h_1^{-1}h) \in bH$（利用假设）.这就完成了证明.

因此，陪集构成了群的一个分拆.下面由陪集引入商集的概念

定义2：设群 $H<G$ ，将 $G$ 关于 $H$ 的所有左陪集构成的集合
$S:=\{aH:a\in G\} \tag2$
称作 $G$ 关于 $H$ 的商集，记作
$G/H$
同时称这个商集的大小为 $H$ 在 $G$ 中的指数，记作
$[G:H]=|G/H| \tag3$

综合上述引理及命题，我们就有

定理1（拉格朗日定理）：对于群 $H<G$，有
$|G|=[G:H]|H| \tag4$

证明：

$|G|=|\cup{a \in I}aH|=\sum{a \in I}|aH|=\sum_{a \in I}|H|=[G:H]|H|$，其中 $I$ 为陪集不交的元素集合，它的大小就是指数.

这就有了子群的阶整除群的阶的推论，这一点是显而易见的.

我们考察何时两个陪集会相等，有如下引理

引理2：对于 $G<H$，陪集 $aH=bH$ 的充要条件是 $b^{-1}a \in H$.

证明：

考虑等价转换，只需证陪集 $aH=H$ 的充要条件是 $a \in H$.

必要性：根据群的封闭性立得 $aH \subset H$.同理有 $a^{-1}H \subset H$.立得结论.

充分性： $a=ae \in aH$.

根据上面的定理，我们有关于子群的重要定理

定理2：对于群 $K<G<H$ 有
$[H:K]=[G:K][H:G] \tag5$

证明：

根据 $(4)$，这是显然的.

我们考察两个群 $H,K$ 的元素互相乘积所构成的集合

$HK=\{hk:h\in H,k\in K\}$

一般地，群的乘积不是一个群.关于群的乘积是否是群有如下命题

论断2：群的乘积是群当且仅当 $HK=KH$.

证明：

充分性：设 $h_1k_1h_2k_2=e$，显然有 $h_2k_2=k_1^{-1}h_1^{-1} \in KH$，根据对称性立得.

必要性：与群的定义一一对照立得.

我们考察乘积的大小，有如下定理

定理3：对于群 $K,H<G$，有
$|HK|=\frac{|H||K|}{|H\cap K|} \tag6$

证明：

微调至

$\frac{|HK|}{|K|}=\frac{|H|}{|H\cap K|} \tag{6'}$

等号右端可依照陪集分割 $H$ 构成一个指标集 $I$ ，使得其中元素陪集不交并为 $H$.

$H=\bigsqcup_{h\in I}h(H \cap K)\tag7$

等式左端同样可以写成类似形式：

$HK=\bigsqcup_{h\in I'} hK\tag8$

注意，此时不需要关心 $HK$ 是否构成一个群.我们考虑证明 $|I|=|I’|$.尝试构造映射

$f:h(K)\to h(H \cap K)\tag9$

只需证对任意 $xK,yK：x,y\in H$ 有 $xK=yK \iff f(xK)=f(yK)$.

设 $xK=yK$，根据引理2，我们有 $y^{-1}x \in K$，因此有 $y^{-1}x \in H \cap K$.再次根据引理2即可得证.

正规子群和商群

本节的最终目标是为陪集赋予群的结构.

首先定义左（右）陪集的乘法

$(aH)(bH)=(abH) \tag{10}$

考察这个定义是否是良定义的，就需要有 $a’H=aH,b’H=bH$ 推出 $a’b’H=abH$ .一般而言这个条件是不成立的，我们需要额外添加条件以达成目的.下面给出正规子群

定义3：若 $N<G$，$\forall a\in G$
$aN=Na \tag{11}$
称 $N$ 是 $G$ 的正规子群，记作
$N \lhd G$

下面我们会看到正规子群的性质是非常良好的.它为陪集的乘法赋予了良定义.

论断2：对于 $G$ 的正规子群 $N$，形如 $(10)$ 的定义是良定义的.

证明：这里直接将 $(10)$ 看作群的乘法，有 $aNbN=abNN=abN$，其中最后一步可以根据封闭性和单位元分别推出左包含和右包含.这就由 $G$ 的乘法的良定义推出了 $(10)$ 的良定义.

这样，我们就可以构造出陪集的群：商群

定理4：设 $N \lhd G$，则 $G/N$ 在由 $(10)$ 定义的乘法下构成群 $(G/N,\times)$，我们称为商群.

证明：我们一一验证

单位元：$N$ 是单位元，显然由 $\forall a \in G,(aN)(eN)=aN$.反向同理.

逆元：$\forall a\in G,(aN)(a^{-1}N)=(aa^{-1})N=N$

封闭性：根据陪集的分拆性质即得.

结合律：不难由 $G$ 的结合律推出.

为了更好地判别正规子群，我们给出如下引理

引理3：以下论断等价
$H \lhd G$ $\forall a\in G,aNa^{-1}\subset N \tag{12}$ $\forall a\in G,\forall n \in N,ana^{-1} \in N \tag{13}$

证明：$(12)$ 与 $(13)$ 等价在集合上是显然的，现在只证 $(12)$ 和 $(11)$ 等价.

充分性：根据定义立得 $aNa^{-1}=N \subset N$.

必要性：根据定义立得 $aN \sub Na^{-1}$，$(12)$ 中将 $a$ 替换为 $a^{-1}$ 立得 $a^{-1}N(a^{-1})^{-1}=a^{-1}Na\subset N$，那么结论就是显然的了.

一般而言， $(12),(13)$ 在实践中能更好地利用正规子群的性质.

利用上面的铺垫，我们有几个简单的论断

论断3：任意个正规子群的交还是正规子群.

利用 $(13)$ 就能简洁地证明，这里略去证明.

论断4：对于群 $G$，有 ${e} \lhd G,G \lhd G$.

论断5：交换群的子群都是正规子群.

这些论断的证明都是平凡的，略去.

群的同构定理

接下来是目前为止最重要的成果

定理5（第一同构定理）：设 $f:G \rightarrow H$ 是群 $G$ 到 $H$ 的同态，则有
$\operatorname{ker}(G) \lhd G$
且
$G/\operatorname{ker}(G) \simeq \operatorname{im}(f) \tag{14}$

证明：

首先，需要证明 $\operatorname{ker}(G) \lhd G$，设 $a\in G,n \in \operatorname{ker}(G)$，有

$f(ana^{-1})=f(a)e'f(a)^{-1}=e'$

根据引理3，结论得证.设 $N= \operatorname{ker}(G)$，我们构造映射

$F:G/N \rightarrow \operatorname{im}(f)$

定义为

$F(aN)=f(a),a\in G \tag{15}$

验证是否良定义，即对于 $aN=a’N$，是否有 $f(a)=f(a’)$。我们立刻有 $aa’^{-1} \in N$，$f(aa’^{-1})=e’$，从而 $f(a)f(a’^{-1})=e’,a^{-1}=a’^{-1},a=a’$.这就是良定义的.

下面验证 $F$ 的同态、单射、满射.

同态：

$F(aN)F(bN)=f(a)f(b)=f(ab)=F(abN)=F(aNbN)$

单射：只需验证 $\operatorname{ker}(aN) = {N}$.设 $F(aN)=e’$，即 $f(a)=e’$，从而 $a\in N$，因此 $aN=N$.

满射：设 $a’\in H$，取 $a:f(a)=a’$，即得 $F(aN)=f(a)=a’$.

综上，$F$ 是一个群同构，因此定理得证.

定理表明了从任意的群同态，可以构造出群同构.这是非常良好的性质.

下面的例子表明了定理（可能）在算法竞赛中的应用.

设有群同态 $f:C7 \rightarrow C{16}$，$f$ 必然是平凡的.这是因为根据定理，必然有 $|\operatorname{im}(f)| \mid|C{16}|$（子群）和 $|\operatorname{im}(f)| \mid|C{7}|$.第二点是因为根据定理，

$|G|=|\operatorname{im}(f)||\operatorname{ker}(G)| \tag{16}$

从而 $\operatorname{im}(f) \mid \gcd(16,9)$，这就说明了平凡性.

从第一同构定理可以推出第二、第三同构定理.

定理6（第二同构定理）：设 $H<G,N \lhd G$，则 $H\cap N \lhd H，N\lhd HN$，且
$H/(H \cap N)\simeq HN/N \tag{17}$

证明：

首先需要证明前两条.

首先令 $h \in H,x\in H\cap N$，有 $hxh^{-1}\in H$，同时根据 $N$ 的正规性， $hxh^{-1} \in N$.这就证明了第一条.

其次，需要证明 $HN$ 是个群，根据论断2和 $N$ 的正规性就可以得出.

再令 $hn \in HN,n’\in N$，则 $hnn’(hn)^{-1}=hnn’n^{-1}h^{-1}$，$nn’n^{-1}\in N$，这就证明了第二条.

于是可以构造映射

$H \rightarrow HN/N : f(h)=hN \tag{18}$

良定义性由引理2保证，同态性由 $H$ 的子群性质保证，下面证明 $\operatorname{ker}(f)= H\cap N$.这是因为 $\forall h \in H,hN=N \Rightarrow h\in N,h \in H \cap N$.根据第一同构定理，这就完成了证明.

这就是定理3有了正规性的更强形式.

定理7（第三同构定理）：设 $N\lhd G,M \lhd G,M<N$,则 $N/M \lhd G/M$，且
$(G/M)/(N/M) \simeq G/N \tag{19}$

证明：

先证明第一条.首先，我们要证明 $N/M$ 是一个群，也就是证明 $M$ 关于 $N$ 的正规性.这完全可以由 $M$ 关于 $G$ 的正规性保证.

其次，我们取 $nM \in N/M,gM \in G/M$，则

$nMgM(nM)^{-1}=ngn^{-1}M=g'M\in G/M,g'\in G \tag{20}$

这就完成了正规性的证明.

下面证明 $(19)$，我们构造映射

$G/M \rightarrow G/N:f(gM)=gN \tag{21}$

良定义性由引理2保证，同态性由 $G$ 的运算保持，只需证明 $\operatorname{ker}(f)=N/M$.我们设 $f(nM)=N$，根据商集的定义，自然有 $nM \in N/M$.从而根据第一同构定理，这就完成了证明.

这就是定理2有了正规性的更强形式.

群作用

先回顾置换群的概念

论断4：对于集合 $S$，所有双射 $f_i:S\to S$ 构成的集合 $\operatorname{Perm}(S)$ 与复合运算 $ \circ$ 构成群，记为 $(\operatorname{Perm}(S),\circ)$.

略去证明.

我们现在从一个最简单的双射引出群作用的概念.设

$f_x:G\to G \tag{22}$

是一族群 $G$ 到自身的映射，定义为

$f_x(y)=xy \tag{23}$

显然对于固定的 $x$ 这是一个双射.也就是说，固定一个 $x$ 我们可以得到一个 $\operatorname{Perm}(G)$ 的元素 $f_x$，这启发我们枚举所有 $G$ 的元素，它们都可以对应上（或者说是映射到） $\operatorname{Perm}(G)$ 的一个元素（这个元素的类型是映射）.形式化地，

$g(x):=f_x:G\to G \tag{24}$

同时注意到这样的映射是群到群的映射，我们自然而然地猜测这个映射是个群同态.即证

$g(xy)=g(x)\circ g(y) \tag{25}$

注意，等号两端都是映射.为了证明映射相同，我们即需证

$\forall z \in G,g(xy)|_z=(g(x)\circ g(y))|_z \tag{26}$

而根据定义显然有

$g(xy)|_z=(xy)z=x(yz)=g(x)|_{g(y)|_z}=(g(x) \circ g(y))|_z \tag{27}$

这就完成了证明.

我们希望研究更多类似于这样的双射 $f_x$，能找到到一个置换群的同态 $\phi$ ，于是我们引入了以下定义

定义4：我们称 $\phi(x)$ 是群 $G$ 在集合 $S$ 上的群作用，若它满足存在一族双射 $f_i$
$\phi(x):G\to \operatorname{Perm}(S),\phi(x):=f_x(G\to S) \tag{28}$
是一个 $G$ 到 $\operatorname{Perm}(S)$ 的群同态.在不引起混淆的情况下，我们将 $\phi(x)|_s$ 简记为 $x \cdot s$ 或 $xs$.

定义可能有些抽象，理解时可以先抛开映射的具体内涵，把它理解成一个众多数据类型中的一种，就非常好理解了.群作用的定义包括 $f_x$ 和 $\phi$ 两个映射.

必须注意上面指的映射族必须是双射.

上述的左乘作用就是一个 $G \to G$ 的群作用.我们再举一个更加重要的例子.

论断5：定义
$f_x:G \to G,f_x(y):=xyx^{-1}\\ \phi(x):=f_x(G \to G) \tag{29}$
是共轭作用.它是一个 $G \to G$ 的群作用.

证明：

双射是显然的，因为

$f_x\circ f_{x^{-1}}(y)=y \tag{30}$

也就是说任意的 $f_x$ 都存在逆映射.并且显然地有

$\forall z\in G,\phi(x)\circ \phi(y)|_z=xyzy^{-1}x^{-1}=xyz(xy)^{-1}=\phi(xy)|_z \tag{31}$

这就证明了论断.

并且共轭作用还有一个很好的性质

论断6：上述 $f_x$ 是一个自同构.

熟读上面证明就会发现这是显然的，略去证明.

定义5：形如上述 $f_x$ 的自同构称为内自同构，其余的同构称为外自同构.

回到群作用.我们有下述引理

引理4：$\phi$ 是一个群作用与同时满足下述条件等价

$\forall s\in S,e\cdot s=s \tag{32.1}$

$\forall x,y \in G,s\in S,x\cdot (y \cdot s)=(xy) \cdot s \tag{32.2}$

证明：

正推是非常显然的.反推的同态性由第二式保证，我们只需证明所有的 $\phi(x)$ 都存在逆映射，也就是它是双射.不难发现

$x\cdot( x^1 \cdot s)=(xx^{-1})\cdot s=e \cdot s=s\tag{33}$

这就完成了证明.（注意第一条是不可或缺的）

轨道-稳定化子定理

我们从一个数数的例子来引出轨道-稳定化子定理.

考虑一个正 $n$ 边形，它的每个顶点互不相同，定义为 $A,B,C,\dots$ .定义状态 $P=(S_1,S_2,\dots,S_n)$ 为从某个固定的位置点开始顺时针数的顶点顺序.再定义翻转操作为沿着对称轴翻转的操作 $f(P)=P’$，旋转操作为将图形顺时针旋转使得每个顶点转到下一个顶点的操作 $g(P)=P’$ .说人话就是每次操作都要保证与上一个形状相比形状不变，变的只有顶点的顺序.我们的任务是找出有多少种这样的操作.

我们枚举可以知道 $n=3,4,5$ 时答案是 $6,8,10$，于是我们猜测答案就是 $2n$ .其实答案就是 $2n$，因为由轴对称和中心对称，旋转和翻转操作各有 $n$ 种.

我们尝试用群论的语言解释对称性.我们首先注意到所有操作构成的集合关于操作复合关系构成群，这是显然的，那么我们任取一个顶点 $s$，定义群作用为操作 $f$ 导致状态 $s$ 变到 $s’$ 的映射.我们发现有两个变换很特殊，它们把 $s$ 映回了自身，也就是旋转一周和绕过 $s$ 的轴的翻转.同时，$s$ 总共能被映射到 $n$ 个顶点.于是我们惊奇地发现答案就是这两个结果的乘积.

这是否是偶然？不是.这是由群作用的对称性得到的自然而然的结果.于是我们抽象出上述讨论种特殊的集合

定义6：设 $\phi:(G,\times)\to (\operatorname{Perm}(S),\circ)$ 是一个 $G$ 在 $S$ 上的群作用.取 $s\in S$，则定义
$\operatorname{Orb}(s)=\{x \cdot s|x\in G \} \tag{33}$
为 $s$ 的轨道，
$\operatorname{Stab}(s)=\{x |x \cdot s=s,x\in G\} \tag{34}$
为 $s$ 的稳定化子.（注意，上述点乘都是群作用）

也就是说，上面关于正 $n$ 边形的讨论中，映射回自身的操作就是 $s$ 的稳定化子，所有 $n$ 个点就是 $s$ 的轨道.既然定义为“轨道”了，我们自然猜想它们互不相交

论断7：设 $\phi:(G,\times)\to (\operatorname{Perm}(S),\circ)$ 是一个 $G$ 在 $S$ 上的群作用，且 $s,s’\in S$，我们有 $s$ 和 $s’$ 的轨道要么相等要么不交，也就是 $S$ 所有元素的轨道构成集合 $S$ 的一个分拆.

证明：

设 $s’’ \in \operatorname{Orb}(s)\cap\operatorname{Orb}(s’)$，对应的群作用分别为 $x,x’$，且有 $xs=x’s’=s’’$，再取 $ys\in \operatorname{Orb}(s)$ 即有

$ys=(yx^{-1})xs=(yx^{-1})s''\in \operatorname{Orb}(s') \tag{35}$

根据对称性就可以得到证明.至于分拆，只需注意到每个元素至少属于它自身的轨道即可.

注意到稳定化子中的元素都是 $G$ 中的元素，我们自然想去证明它是 $G$ 的子群

论断8：设 $\phi:(G,\times)\to (\operatorname{Perm}(S),\circ)$ 是一个 $G$ 在 $S$ 上的群作用，$s\in S$，则 $s$ 的稳定化子是 $G$ 的子群.

证明：

单位元：$es=s$ （引理4）

再任取 $x,y\in \operatorname{Stab}(s)$，我们要证 $xy^{-1}s \in \operatorname{Stab}(s)$.考虑群作用的同态性质，我们有

$y^{-1}(ys)=y^{-1}s=es=s \tag{36}$

从而 $y^{-1}\in \operatorname{Stab}(s)$，再根据引理4，于是引理得证.

引理6：设 $\phi:(G,\times)\to (\operatorname{Perm}(S),\circ)$ 是一个 $G$ 在 $S$ 上的群作用，则 $xs=ys$ 当且仅当 $x^{-1}y \in \operatorname{Orb}(s)$

证明：

同时左乘 $x^{-1}$ 即可得知.

于是我们就有了开头猜到的结论

定理8（轨道-稳定化子定理）：设 $\phi:(G,\times)\to (\operatorname{Perm}(S),\circ)$ 是一个 $G$ 在 $S$ 上的群作用，$s\in S$，则存在 $G/\operatorname{Stab(s)}$ 到 $\operatorname{Orb}(s)$ 的双射.

特别地，若 $G$ 是有限群，则
$|G|=|\operatorname{Stab}(s)||\operatorname{Orb}(s)| \tag{37}$

证明：

定义 $f:G/\operatorname{Stab(s)} \to \operatorname{Orb}(s)$ 为 $f(x \operatorname{Stab(s)}) = xs$.

首先证明 $f$ 是良定义的.根据引理6，$x\operatorname{Orb}(s)=y\operatorname{Orb}(s) \iff x^{-1}y \in \operatorname{Orb}(s) \iff xs=ys$ .同时根据充要性可以得出单射性.

满射根据稳定化子的定义是显然的.从而 $f$ 是个双射.再根据l拉格朗日定理就能得到证明.

这样，我们就可以回到开头提出的问题，$|D_n|=|\operatorname{Stab(s)}| |\operatorname{Orb}(s)| = 2n $ 就是显然的了.

轨道-稳定化子定理可以为数论提供非常好的数数方法，就像正 $n$ 边形的例子，只要知道被作用的元素的轨道大小和稳定化子大小就可以算出原群的大小.