群在集合上的作用

在上一部分中，我们由群\(G\)中某个元素\(g\)的左乘引发的单射讨论了陪集、同态等内容。现在，我们把这种左乘推广到任意的一个集合\(X\)上。给定一个群\((G,\cdot)\)和一个非空集合\(X\)，如果我们能够定义一个\(G\)中元素和\(X\)中元素的运算\(\circ\)满足以下三条性质，就称群\(G\)作用在\(X\)上：① \(\forall g\in G,f_g:x\to g\circ x\)是一个\(X\)到\(X\)的映射；② \(\forall g,h\in G,\forall x\in X,\)\(h\circ(g\circ x)=(h\cdot g)\circ x\)；③ 对于\(G\)中的单位元\(e\)，\(\forall x\in X,e\circ x=x\)。

我们发现，这样的作用\(f_g\)始终是\(X\to X\)的双射：先证单射，如果\(g\circ x_1=g\circ x_2\)，那么两边同时作用\(g^{-1}\)，得到\(g^{-1}\circ (g\circ x_1)=g^{-1}\circ (g\circ x_2)\)，根据性质二得到\((g^{-1}\cdot g)\circ x_1=(g^{-1}\cdot g)\circ x_2\)，也即\(x_1=x_2\)；再证满射，对于任意的\(y\in X\)，由于\(f_{g^{-1}}\)也是\(X\to X\)的映射，因此\(g^{-1}\circ y\in X\)，于是一定有\(f_g(g^{-1}\circ y)=g\circ (g^{-1}\circ y)=(g\cdot g^{-1})\circ y=y\)。

而基于集合\(X\)，我们有\(X\)的对称群\(S_X\)，其中的元素是所有\(X\to X\)的双射。如果我们定义\(\phi(g):g\to f_g\)，这就是一个\(X\)到\(S_X\)的映射。而根据定义，\(\phi(g\cdot h)=f_{g\cdot h}\)。\(\forall x\in X\)，\(f_{g\cdot h}(x)=(g\cdot h)\circ x=g\circ (h\circ x)=f_g(f_h(x))\)，而映射的复合恰好是对称群上的运算法则，因此\(\phi\)是一个保运算的映射。也即\(\phi\)是\(X\)到\(S_X\)的群同态！根据同态的左子群右子群性质，我们也知道了所有映射\(f_g\)也构成了一个对称群的子群，如果取\(X\)等于\(G\)那么实际上我们得到了一个同构映射，这正是Cayley定理描述的事实。

轨道与稳定子(Orbits and Stabilizers)

对于\(X\)中的任意一个元素\(x\)，我们用所有可能的群中元素作用在它身上得到的元素集合称为\(x\)的轨道(orbit)，记为\(B(x)=\{g\circ x\mid g\in G\}\)。我们发现，轨道实际上把\(X\)分划为了若干等价类。\(\forall x,y\in X\)，定义\(x\sim y\)当且仅当\(y\in B(x)\)。我们证明这是一个等价关系：自反性，\(x\in B(x)\)显然成立；对称性，如果\(y\in B(x)\)，那么存在\(g\in G\)使得\(y=g\circ x\)，因此\(x=g^{-1}\circ y\)，所以\(x\in B(y)\)；传递性，如果\(x\in B(y),y\in B(z)\)，那么存在\(g_1\)使得\(x=g_1\circ y\)，存在\(g_2\)使得\(y=g_2\circ z\)，于是\(x=g_1\circ (g_2\circ z)=(g_1\cdot g_2)\circ z\)，因此\(x\in B(z)\)。

在生成\(x\)的轨道\(B(x)\)的所有\(g\)当中，有一些（例如单位元）会把\(x\)映射到\(x\)本身，我们把这些\(x\)收集进集合\(G(x)=\{g\mid g\circ x=x\}\)，称为\(x\)的稳定子(Stabilizer)。我们发现对于任意\(x\)，稳定子\(G(x)\)都形成了\(G\)的一个子群：只需证明\(\forall g,h\in G(x),g^{-1}\cdot h\in G(x)\)，其中\(g\circ x=x\)，因此\(x=g^{-1}\circ x\)，而\(h\circ x=x\)，因此\(g^{-1}\circ (h\circ x)=x\)，也即\((g^{-1}\cdot h)\circ x=x\)。

同时，我们可以证明如果存在\(a\in G\)使得\(y=a\circ x\)，那么\(G(y)=aG(x)a^{-1}\)。先证\(G(y)\subseteq aG(x)a^{-1}\)，\(\forall g\in G(y)\)，\(g\circ y=y\)，那么\((a^{-1}ga)\circ x=(a^{-1}g)\circ y=a^{-1}\circ y=x\)，因此\(a^{-1}ga\in G(x)\)，也即\(g\in aG(x)a^{-1}\)；再证\(aG(x)a^{-1}\subseteq G(y)\)，\(\forall h\in G(x)\)，\(h\circ x=x\)，那么\(aha^{-1}\circ y=(ah)\circ x=a\circ x=y\)，因此\(aha^{-1}\in G(y)\)。我们知道左乘或右乘一个群中元素一定是单射，因此\(G(y)\)与\(G(x)\)的大小一定相同——同一个轨道上的元素的稳定子大小都相同。

The Orbit-Stablizer Theorem

我们可以这样理解\(x\)的轨道：以它为中心，每个\(g\)中的元素都对应着一条有向边从\(x\)出发指向\(g\circ x\)，\(x\)的轨道就是从\(x\)出发可达的点集；一部分有向边是从\(x\)出发指向自身的，这些边就是稳定子。稳定子可能不止一条，同样地对于某个\(y\in B(x)\)，边\(x\to y\)也可能不止一条。对于某个\(y\in B(x)\)，假设既有\(g_1\circ x=y\)，又有\(g_2\circ x=y\)，那么\(x=(g_1^{-1}g_2)\circ x\)，因此\(g_1^{-1}g_2\)是稳定子。我们发现，\(g_1\circ x=g_2\circ x\iff g_1^{-1}g_2\in G(x)\)——这是陪集的性质！对于子群\(G(x)\)，陪集\(g_1G(x)=g_2G(x)\)当且仅当\(g_1^{-1}g_2\in G(x)\)。轨道图上指向相同终点的边一定构成稳定子的一个陪集。根据Lagrange定理，所有的陪集都有相同的大小。换言之，轨道图上任意两点之间边的条数总是相等的，且等于\(|G(x)|\)。轨道的大小就是陪集的个数，\(|B(x)|=[G:G(x)]\)。

The Orbit-Counting Theorem

如何计算\(X\)中有多少个不同的轨道呢？我们可以用一种double counting的方法来得到计算轨道大小的一个简单方法。设群\(G\)作用在集合\(X\)上，把所有满足\(g\circ x=x\)的有序对收集进集合\(T\)，\(T=\{(g,x)\mid g\circ x=x,g\in G,x\in X\}\)。固定\(x\)计数，设\(T_x=\{(g,x)\mid g\circ x=x,g\in G\}\)，所有的\(g\)其实就是稳定子，\(|T_x|=|G(x)|\)。于是\(|T|=\sum\limits_{x}|T_x|=\sum\limits_{x}|G(x)|\)。另一方面，固定\(g\)，设\(T_g=\{(g,x)\mid g\circ x=x,x\in X\}\)，于是\(\sum\limits_{x}|G(x)|=\sum\limits_{g}|T_g|\)。两边同时除以\(|G|\)，那么\(\sum\limits_{x}\dfrac{|G(x)|}{|G|}=\dfrac{\sum\limits_{g}|T_g|}{|G|}\)。其中，\(|G|/|G(x)|=[G:G(x)]=|B(x)|\)，因此\(\sum\limits_{x}\dfrac{|G(x)|}{|G|}=\sum\limits_{x}\dfrac{1}{|B(x)|}\)，而由于同一个轨道中的\(x\)的\(B(x)\)都取相同值，因此\(\sum\limits_{x}\dfrac{1}{|B(x)|}\)就是轨道数。综上，轨道数就等于\(\dfrac{1}{|G|}\sum\limits_{g}|T_g|\)。而\(|T_g|\)就是函数\(f_g\)的“不动点”个数。

几类特殊的作用

选取\(X=G\)，运算定义为群的运算\(f_g:x\to gx\)。根据封闭性，这是\(X\to X\)的映射；根据群运算的结合律和单位元的性质，我们验证了这的确是一种群在集合上的作用，这里\(G\)作用于自身，称为正则作用(The Regular Action)。此时\(f_g\)是\(G\to G\)的双射，因此任意一个元素的轨道都覆盖了所有点，稳定子大小为1。也即轨道图上不存在重边。

对于\(G\)和\(X\)，定义\(f_g:x\to x\)。这确实是映射，结合律和单位元都成立。这称为平凡作用(The Trivial Action)。此时，所有\(G\)中元素都是任何\(x\)的稳定子，\(\forall x,G(x)=G\)。每个\(x\)自成一个轨道，共有\(|X|\)个不同轨道。

选取\(X=G\)，定义\(f_g:x\to gxg^{-1}\)。根据群的封闭性这是\(X\to X\)的映射，结合律成立（\(h\circ (g\circ x)=h(gxg^{-1})h^{-1}=(hg)x(hg)^{-1}=(hg)\circ x\)），单位元\(exe^{-1}=x\)。这称为元素共轭作用(Conjugation on Elements)。此时，所有\(G\)中元素都是任何\(x\)的稳定子，\(\forall x,G(x)=G\)。每个\(x\)自成一个轨道，共有\(|X|\)个不同轨道。这是保运算的映射，\(f_g(xy)=gxyg^{-1}=gxg^{-1}gyg^{-1}=f_g(x)f_g(y)\)，因此\(f_g\)构成了\(G\to G\)的自同态。\(x\)的稳定子写作\(G(x)=\{g\mid gxg^{-1}=x\}\)，也即\(\{g\mid gx=xg\}\)，这些是所有与\(x\)相乘满足交换律的元素集合，称为\(x\)的中心化子(Centralizer)，记为\(C_G(x)\)。对所有的\(C_G(x)\)取交，得到的是与所有\(x\)满足交换律的元素，这些元素称为群\(G\)的中心元(Central Element)。由于每个\(G(x)\)都是\(G\)的子群，中心元构成的集合也是子群，称为中心元群。中心元群中的每个元素的稳定子都是\(G\)，它们都各自自成一个轨道。\(f_g\)不一定是满射，因此可能不止一个轨道。我们把这些轨道划分的等价类称为共轭类(Conjugacy Class)。

取\(X=\{H\mid H\preceq G\}\)，定义\(f_g:H\to gHg^{-1}\)。\(gHg^{-1}\)是子群，因为\((gHg^{-1})(gHg^{-1})=gHHg^{-1}=gHg^{-1}\)，\((gHg^{-1})^{-1}=gHg^{-1}\)；结合律\(h(gHg^{-1})h^{-1}=(hg)H(hg)^{-1}\)；单位元\(eHe^{-1}=H\)。这称为子群共轭作用(Conjugation on Subgroups)。\(H\)的稳定子\(G(H)=\{g\mid gHg^{-1}=H\}\)\(=\{g\mid gH=Hg\}\)。可见如果\(G(H)\subseteq K\)就有\(H\)是\(K\)的正规子群，因此\(G(H)\)又称为\(H\)的正规化子(Normalizer)，记为\(N_G(H)\)。换言之，\(N_G(H)\)是\(G\)中最大的使得\(H\)在其中是正规子群的子集。

取\(X=\{S\mid S\subseteq G\}\)，定义\(f_g:S\to gSg^{-1}\)。根据封闭性，\(gSg^{-1}\subseteq G\)；结合律\(h(gSg^{-1})h^{-1}=(hg)S(hg)^{-1}\)；单位元\(eSe^{-1}=S\)。这称为子集共轭作用(Conjugation on Subsets)。\(S\)的稳定子\(G(S)=\{g\mid gS=Sg\}\)同样称为\(S\)的正规化子(Normalizer)，记为\(N_G(S)\)。子集共轭显然满足\(|S|=|gSg^{-1}|\)（子群共轭自然也满足）。

对于\(H\preceq G\)，取\(X=G/H=\{aH\mid a\in G\}\)，定义\(f_g:aH\to gaH\)。显然这是映射，满足结合律和单位元。这称为陪集左乘的作用(Multiplication on cosets)。作为一个应用，我们考虑如下例子：群的第二同构定理陈述了如果\(H\preceq G,K\unlhd G\)，那么\(H/(H\cap K)\cong HK/K\)。现在我们证明如果把\(K\unlhd G\)放弱为\(K\preceq G\)，成立\(\dfrac{|H|}{|H\cap K|}=\dfrac{|HK|}{|K|}\)。取\(X=G/K\)，让\(H\)以陪集左乘的方式作用在\(X\)上（\(G\)可以作用，子群\(H\)当然也可以作用）。那么对于\(K\in X\)，轨道\(B(K)=\{hK\mid h\in H\}=HK/K\)，稳定子\(G(K)=\{h\in H\mid hK=K\}=H\cap K\)。所以\(|B(K)|=|H|/|G(K)|\)，也即\(|HK|/|K|=|H|/|H\cap K|\)。

取\(X=\{S\mid S\subseteq G\}\)，同样可以验证\(f_g:S\to gS\)是作用，称为子集左乘的作用(Multiplication on Subsets)。

串珠染色问题

有\(6\)颗珠子串成一个环，要给它们用\(n\)种颜色染色，问有多少种不同的染色方案？其中，经过旋转和翻折后相同的方案算同一种方案。这就是串珠染色问题。

可以证明，串珠（正六边形）的运动只有\(12\)种，分别是依次旋转\(0^\circ,60^\circ,120^\circ,180^\circ,240^\circ,300^\circ\)以及沿六条不同的对称轴翻折。每一种运动对应着一个\(6\)阶permutation，所有的运动构成一个\(6\)阶置换群，也即\([6]\)的对称群的一个子群。列举如下：\(\tau_1=(1)(2)(3)(4)(5)(6)\)，\(\tau_2=(1,2,3,4,5,6)\)，\(\tau_3=(1,3,5)(2,4,6)\)，\(\tau_4=(1,4)(2,5)(3,6)\)，\(\tau_5=(1,5,3)(2,6,4)\)，\(\tau_6=(1,6,5,4,3,2)\)，\(\tau_7=(1,6)(2,5)(3,4)\)，\(\tau_8=(1,5)(2,4)(3)(6)\)，\(\tau_9=(1,4)(2,3)(5,6)\)，\(\tau_{10}=(1,3)(2)(4,6)(5)\)，\(\tau_{11}=(1,2)(3,6)(4,5)\)，\(\tau_{12}=(1)(2,6)(3,5)(4)\)。把这个置换群记为\(D_{12}\)。

现在不考虑重复地做出\(n^6\)中染色方案，每个染色方案是一个长度为\(6\)的数字串，它们构成集合\(X\)。令\(D_{12}\)作用在\(X\)上，作用的方式是以\(\tau_i\)的方式进行顺序的重排。可见，映射、结合律、单位元都满足，因此这是群在集合上的作用。而串珠染色问题就是要问\(X\)的不同轨道个数，因为同一个轨道意味着同一种本质相同的染色方案。根据Orbit-Counting定理，我们只需计算每一个置换\(\tau_i\)在\(X\)上的不动点个数。假设总共可以染\(n\)种颜色，那么\(\tau_1\)的不动点是全部（\(n^6\)）；\(\tau_2\)产生不动点当且仅当旋转\(60^\circ\)以后不变，意味着只要有两个相邻颜色不同就不合法，因此只有所有颜色相同的方案，共\(n\)个。更一般地，我们发现进行不相交的轮换分解以后，不动点上每个轮换中的颜色必须相同，不同轮换可以是不同颜色。因此\(\tau_i\)的不动点个数就是\(n^k\)，其中\(k\)是轮换个数。这样我们就给出了串珠染色问题的多项式表达式：\(\dfrac{n^6+n+n^2+n^3+n^2+n+n^3+n^4+n^3+n^4+n^3+n^4}{12}\)。