03 陪集与正规子群

陪集(Coset)

对于$G$的一个子群$H$，每个$g\in G$我们都可以定义$H\to G$的映射$f_g(x)=g\circ x$，这一定是单射，因为消去律成立。对于给定的$H$，不同的$g$就给出了不同的单射，单射的像一定落在$G$中（封闭性），构成$G$的一个子集。因此对于每个$g$我们都可以给出一个像集，我们称之为由$g$生成的子群$H$的左陪集(left coset)：$gH=\{g\circ h\mid h\in H\}$。同样的，也可以定义右陪集$Hg$。从下面开始我们只讨论左陪集，因为右陪集的性质是完全相同的。

例如，令$G=(\Z,+)$，对于正整数$k$，$G$有子群$H=(k\Z,+)$。那么$\forall 0\leq i<k$都会生成互不相同的$H$的陪集$i+k\Z$，$i=k$时生成的陪集与$i=0$相同。因此$H$共有$k$个不同的陪集。

对于有限集，一定成立$|H|=|gH|$。有限子群的陪集大小一定与子群本身大小相等。无限子群的陪集大小与子群本身等势。

Lagrange定理

从整数加法群的例子中我们注意到这样一件看上去巧合的事实：每一个不同的陪集间都互不相交，并且所有陪集并起来恰好得到了$G$。换言之，$(\Z,+)$的陪集构成了$G$的一个partition。是不是所有群的陪集都满足这样的性质呢？

首先验证，不同的陪集之间是互不相交的。Pf. 对于$a\in G,H\preceq G$，设$b\in aH$，也即存在$h\in H$使得$ah=b$，那么对于所有的$h'\in H$都成立$bh'=(ah)h'=a(hh')\in aH$，这说明$bH\subseteq aH$；同时，对于所有的$h'\in H$都成立$ah'=(bh^{-1})h'=b(h^{-1}h')\in bH$，这说明$aH\subseteq bH$。因此$aH=bH$。也就是说，$aH$中的每个元素$b$生成的陪集都必定是$aH$本身。反之，假设对于$a,b\in G$已知$aH=bH$，那么由于$H$中有单位元，$b\in bH=aH$，对称的也有$a\in bH$。这说明$aH=bH$与$b\in aH$（或$a\in bH$）是当且仅当的，一个陪集中的任何一个元素都可以充当生成元而不改变任何事情。现在假设对于$a,b\in G$，$aH$与$bH$的交集是非空的，也即存在$c\in G$使得$c\in aH$且$c\in bH$。那么存在$h_1\in H$使得$c=ah_1$，存在$h_2\in H$使得$c=bh_2$。那么$ah_1=bh_2$，也即$a(h_1h_2^{-1})=b$。而$h_1h_2^{-1}\in H$，这说明$b\in aH$，等价于$aH=bH$。所以我们证明了，只要两个陪集有交，那么这两个陪集必须相等！取逆否命题得到，两个不同的陪集一定无交。Qed.

我们令$g$遍历$G$中的所有元素，由于每个$g$本身肯定包含在$gH$中，因此所有可能的$gH$并起来一定会得到全集$G$。而不同的$gH$间又互不相交。所以陪集的确构成了$G$上的一个partition！

$aH=bH\iff b\in aH\iff a^{-1}b\in H$

$Ha=Hb\iff b\in Ha\iff ba^{-1}\in H$

可以验证，左陪集的数量与右陪集的数量相等（如果是无穷则集合的势相等）。因为我们可以构造左陪集集合到右陪集集合的双射$\psi(aH)=Ha^{-1}$：因为$\forall b\in aH,Hb^{-1}=Ha^{-1}\iff a^{-1}b\in H$ $\iff aH=bH\iff b\in aH$，所以这是良定义的映射；$Ha^{-1}=Hb^{-1}\implies a\in bH$ $\iff aH=bH$，因此是单射。同时，$G\preceq G$，所以$G^{-1}=G$，因此$a^{-1}$取遍所有$G$中元素，因此是满射。

陪集构成partition这一事实可以理解为，我们用陪集给出了$G$上的一个等价类，一个陪集$gH$中的所有元素就被看为“等价的”，因为我们确实容易验证元素的这种关系是自反、传递、对称的。更具体的，由陪集给出的等价类定义了一个自然映射$\pi:G\to G/H$，其中$G/H$定义为$\{gH\mid g \in G\}$，它是所有不同陪集构成的集合。$\pi(g)=gH$。（右陪集集合则记为$G\backslash H$）。现在，对于有限群$G$，每个陪集的大小都相等且为$|H|$，所以我们直接得到不同的陪集个数必定为$\dfrac{|G|}{|H|}$。这称为Lagrange定理：记有限群$G$中子群$H$的不同陪集个数为$[G:H]$，则$|G|=[G:H]\cdot |H|$。在$G/H$中，“除号”形象地体现出了这种如同整数除法一样的对集合的划分，我们通常把$G/H$称为商集(quotient set)。

Lagrange定理向我们揭示了有限群的很重要的一个性质：任何子群的大小都必须是$G$的大小的约数！这为我们理解子群的性质提供了大量的便利。

Lagrange定理的应用

现在我们知道对于有限群$G$，其元素$a\in G$生成的循环群$\lang a\rang$既然是$G$的一个子群，其大小就一定是$|G|$的约数。假如$|G|$是素数，那么其约数只有$1$或$|G|$本身。取$G$中任何一个非单位元作为生成元生成一个循环群，这个群一定是不止一阶的，那么它只能是$|G|$阶的。那么，这个循环群就是$G$本身了！也就是说，$G$是一个循环群，并且除了单位元以外所有元素都可以作为生成元。我们证明了，任何素阶群都一定是循环群！

Lagrange定理的另一个重要的推论就是数论上的Euler定理，它的本质就是作为子群的循环群。我们验证过$(\Z_n^*,\cdot)$是群（$\Z_n^*$中的元素是$1$到$n-1$中所有与$n$互质的数，共$\varphi(n)$个）。那么取任意一个与$n$互质的数$a$，$a$在模$n$意义下一定与$\Z_n^*$中的一个元素相等（如果不能则说明存在某个$k\in \Z$使得$a-kn$有$n$的因子，与$gcd(a,n)=1$矛盾）。所以我们不妨假设$1\leq a<n$。那么$\lang a\rang$构成了$\Z_n^*$的一个子群，根据Lagrange定理其大小一定是$\varphi(n)$的约数。那么此时必定成立$a^{\varphi(n)}\equiv 1\pmod n$。这就是Euler定理。取$n$为素数$p$，此时$\varphi(p)=p-1$。那么得到推论$a^{p-1}\equiv 1\pmod p$，这就是Fermat小定理。

Euler定理是密码学中RSA算法的核心。见大一下的算法内容数的算法。

正规子群(Normal Groups)

我们已经看到通过陪集，我们把全集$G$分成了若干个等价类。这些等价类构成了商集$G/H$。我们现在要追问，$G/H$本身能否构成一个群呢？也就是说，何时我们能由子群$H$得到商群(quotient subgroup)$G/H$？要能构成群，我们首先要定义一个陪集与陪集间的代数运算。这里，我们回忆起在给出子群的等价定义时，我们定义过在群的代数运算$\circ$下集合的乘积与逆，并证明了$H\preceq G$ $\iff H\circ H \subseteq H\land H^{-1}\subseteq H$ $\iff H\circ H=H\land H^{-1}=H$。我们看到，陪集只是单个元素构成的集合与子群的乘积，因此可以继承集合乘积的性质。（集合的乘积是满足结合律的，这实际上正是群的运算$\circ$的结合律的直接结果）。我们将会用这个集合间的乘积运算作为商集中陪集与陪集的运算。

如果$H\preceq G,K\preceq G$，是否成立$HK\preceq G$？下面我们证明，这是需要额外条件的：如果$H\preceq G,K\preceq G$，那么$HK\preceq G\iff HK=KH$。左推右，因为$HK$是子群，根据等价定义得到$(HK)^{-1}=HK$，而$(HK)^{-1}=K^{-1}H^{-1}$，而$H,K$都是子群，因此等于$KH$；右推左，$(HK)^{-1}=K^{-1}H^{-1}=KH=HK$，同时$(HK)(HK)=H(KH)K$ $=H(HK)K=(HH)(KK)=HK$，因此$HK\preceq G$。（我们注意到，如果$G$本身就是阿贝尔群，那么$HK=KH$是显然成立的，在这种情形下$HK$总是$G$的子群。但反过来$HK=KH$并不能推出$G$是阿贝尔群。另外我们还注意到，任何一个包含$H$中所有元素且包含$K$中所有元素的子群都必须包含$HK$中的所有元素，因此如果$HK\preceq G$，那么$HK$就是包含$H$和$K$的最小子群了，也即此时$HK=\lang H\cup K\rang$。）

对于$H\preceq G$，要能得到商群，我们希望陪集与陪集的乘积依然是陪集。对于$a,b\in G$，一定有$ab \in (aH)(bH)$。如果$(aH)(bH)$是陪集，那陪集作为等价类意味着它一定等于$abH$。然而这并不是对任意$H$都能成立的。下面我们证明，如果要能使得对于任意的$a,b\in G$都满足$(aH)(bH)=abH$， 当且仅当$\forall c \in G,cH=Hc$。Pf. 右推左，$(aH)(bH)=$ $a(Hb)H=a(bH)H=$ $ab(HH)=abH$；左推右，$\forall c$，$(cH)(c^{-1}H)=(cc^{-1})H=H$。而$\forall c,cHc^{-1}\subseteq cHc^{-1}H=H$，因为$H$里含有单位元。$cHc^{-1}\subseteq H$展开，等价于$\forall h\in H,\exists h'\in H$使得$chc^{-1}=h'$，这等价于$h=c^{-1}h'c$，也即$\forall h \in H,h\in c^{-1}Hc$。也即$H\subseteq c^{-1}Hc,\forall c$。对于任意固定的$c$，$cHc^{-1}\subseteq H$，取$c'=c^{-1}$，有$H\subseteq c'^{-1}Hc'=cHc^{-1}$，因此$H=cHc^{-1},\forall c$。两个相等的集合有相同的关于$c$的右陪集，因此$Hc=cH,\forall c$。Qed.

换言之，要使得$H$的陪集在乘积作用下保持陪集性质，它必须是一个不区分左右陪集的子群。只有具有这样良好的性质，我们才可能定义商群$G/H$。我们把这类特殊的子群$H$称为$G$的正规子群(normal subgroup)，记为$H\unlhd G$。如果$H$是$G$的正规真子群，则记为$H\lhd G$。$H$是$G$的正规子群当且仅当$\forall c\in G,cH=Hc$。这一条件有很多等价的表达方式，我们可以验证$cH=Hc,\forall c$ $\iff cHc^{-1}=H,\forall c$ $\iff cHc^{-1}\subseteq H,\forall c\iff H$的每个左陪集都是某个$H$的右陪集$\iff H$的每个右陪集都是某个$H$的左陪集。其中，前三条我们在刚才的证明中实际上已经证明了，第四条证明如下：由第一条推第四条显然；反过来，已知$\forall c,\exists c'$使得$cH=Hc'$，那么$\forall \hat c \in cH$，则$cH=\hat c H$。而$\hat c \in Hc'$，因此$Hc'=H\hat c$。那么$\hat cH=H\hat c$。由于$c$可以取任意元素，因此$\hat c$一定也可以取遍任意元素，证毕。第五条同理。

那么我们就可以验证对于正规子群$N\unlhd G$，$G/N=\{gN\mid g \in G\}$关于集合的乘积运算是群。根据正规子群的定义，封闭性成立；结合律：$(aNbN)cN=abcN=aN(bNcN)$；商群中陪集的单位元就是$G$的单位元的陪集$e_GN=N$；陪集的逆就是生成元的逆的陪集。综上，正规子群的商集的确构成了群（商群）。作为一个例子，我们可以取$G$为$n$阶可逆方阵构成的集合，$N$取$n$阶的行列式为1的矩阵的集合。容易验证$N$是子群，而我们可以进一步验证$N$是正规子群：$\forall A\in N,P\in G$，$\det(PAP^{-1})=\det(P)\det(A)\det(P^{-1})=\det(A)=1$，因此$PNP^{-1}\subseteq N,\forall P$，所以是正规子群。