群(II)

陪集

在Cayley定理的证明中，以及在证明对称群中奇置换与偶置换数量相等时，我们都用到了群的这样一个性质：如果以群\(G\)中的任意一个特定元素\(g\in G\)来产生一个映射\(G\to G:f(x)=g\circ x\)，则\(f\)一定是单射。这本质上缘于群具有“消去律”的性质。如果\(G\)是有限的，我们进一步得知\(f\)是双射，也即“左乘\(g\)”实际上给出了一个permutation。这个性质是如此重要，以至于我们要从它出发更深入地讨论群的性质。

陪集的定义

对于\(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,+)\)。那么\(0,1,2,\cdots,k-1\)都会生成互不相同的\(H\)的陪集（由于是阿贝尔群，左陪集等于右陪集），\(k\)生成的陪集与\(0\)相同。因此我们说\(H\)有\(k\)个不同的陪集。

我们已经知道，对于有限集\(f\)是双射。因此如果\(H\)是有限群，一定成立\(|H|=|gH|\)。有限子群的陪集大小一定与子群本身大小相等。

Lagrange定理

从整数加法群的例子中我们注意到这样一件巧合的事实：每一个不同的陪集间都互不相交，并且所有陪集并起来恰好得到了\(G\)。换言之，陪集构成了\(G\)的一个partition。是不是所有群的陪集都满足这样的性质呢？我们来证明的确是这样的。首先我们来验证，不同的陪集之间是互不相交的。设\(a,b\in G\)，\(b\in aH\)，也即存在\(h\in H\)使得\(ah=b\)，那么对于所有的\(h'\in H\)都成立\(bh'=ahh'\in aH\)，这说明\(bH\subseteq aH\)；同时，对于所有的\(h'\in H\)都成立\(ah'=bh^{-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\)。所以我们证明了，只要两个陪集有交，那么这两个陪集必须相等！现在我们令\(g\)遍历\(G\)中的所有元素，由于每个\(g\)本身肯定包含在\(gH\)中，因此所有可能的\(gH\)并起来一定会得到全集\(G\)。而不同的\(gH\)间又互不相交。所以陪集的确构成了\(G\)上的一个partition！

可以验证（并且根据对称性显然），左陪集的数量（如果是无穷则考虑集合的势）与右陪集的数量相等。因为我们可以构造左陪集集合到右陪集集合的双射\(\psi(aH)=Ha^{-1}\)：如果\(Ha^{-1}=Hb^{-1}\)，那么\(b^{-1}\in Ha^{-1}\)，也即存在\(h\in H\)使得\(b^{-1}=ha^{-1}\)，也即\(a=bh\)，那么\(a\in bH\)，等价于\(aH=bH\)，因此是单射。同时，\(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]\)，称为\(H\)在\(G\)中的index(指数)，则\(|G|=[G:H]\cdot |H|\)。在\(G/H\)中，“除号”形象地体现出了这种如同整数除法一样的对集合的划分，我们通常把\(G/H\)称为商集(Quotient Set)。

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

在循环群上的应用

现在我们知道对于有限群\(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^*\)中的一个元素对应（如果不能则说明\(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\and H^{-1}\subseteq H\)\(\iff H\circ H=H\and H^{-1}=H\)。我们看到，陪集只是单个元素构成的集合的乘积。为了讨论商群，我们要更深入地研究一下这种集合间的乘积运算。

首先，这种乘积运算是有结合律的。对于集合\(A,B,C\)，始终满足\((AB)C=A(BC)\)。这实际上正是群的运算\(\circ\)的结合律的直接结果。

另一个问题是乘积运算能否保子群的性质？如果\(H\preceq G,K\preceq G\)，是否成立\(HK\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\)是\(H\cup K\)生成的子群。）

现在我们开始讨论陪集与陪集的乘积。对于\(H\preceq G\)，要能得到商群，我们希望陪集与陪集的乘积依然是陪集。然而这并不是对任意\(H\)都能满足的。对于\(a,b\in G\)，一定有\(ab \in (aH)(bH)\)。如果\((aH)(bH)\)是陪集，那陪集作为等价类意味着它一定只能是\((ab)H\)。下面我们证明，如果要能使得对于任意的\(a,b\in G\)都满足\((aH)(bH)=abH\)， 当且仅当\(\forall c \in G,cH=Hc\)：右推左，\((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\)。

换言之，要使得\(H\)的陪集在乘积作用下保持陪集性质，它必须是一个不区分左右陪集的子群。只有具有这样良好的性质，我们才可能定义商群\(G/H\)。我们特别把这类特殊的子群\(H\)称为\(G\)的正规子群(Normal Subgroup)。\(H\)是\(G\)的正规子群当且仅当\(\forall c\in G,cH=Hc\)。