Burnside引理
Burnside引理,Pólya定理及其应用
Burnside引理
书接上回，继续深入研究在群作用下集合的轨道与稳定子群的相关性质
现在我们想要研究这样一个问题： \[ 有限群G在有限集合S上面有一个作用，那么S的G-轨道条数是多少 \] 也就是在有限群\(G\)作用下集合\(S\)的等价类的数量
不妨设\(S\)有\(r\)条\(G\)-轨道条数，那么就有 \[ S=\bigcup_{i=1}^{r}Orb(x_i) \] 其中\(x_i\)就是每一条轨道的代表元。注意到任意两条轨道交集为空，所以 \[ |S|=\bigcup_{i=1}^{r}|Orb(x_i)|=\bigcup_{i=1}^{r}\frac{|G|}{|Stab(x_i)|} \] 这里有点怪，它似乎暗示我们同一个轨道的元素的不变子群的阶都是一样的。我们再仔细研究一下
\(\forall x,y\in S\),且\(x\),\(y\)在同一条轨道里面，\(\exist a\in G,a\cdot x=y\)。则 \[ \begin{flalign} &h\in Stab(y)\Leftrightarrow h\cdot y=y \\ &\Leftrightarrow h\cdot(a\cdot x)=a\cdot x \\ &\Leftrightarrow (ha)\cdot x=a\cdot x \\ &\Leftrightarrow a^{-1}\cdot ((ha)\cdot x)=(a^{-1}\cdot (a\cdot x)) \\ &\Leftrightarrow (a^{-1}ha)\cdot x=x \\ &\Leftrightarrow a^{-1}ha\in Stab(x) \\ &\Leftrightarrow h\in a^{-1}Stab(x)a \end{flalign} \]
注意到上述过程都是等价的，所以我们很快得到 \[ Stab(y)=a^{-1}Stab(x)a \] 于是我们得到如下命题
设有限群\(G\)在有限集合\(S\)上面有一个作用，那么同一个\(G\)-轨道的点的稳定子群彼此共轭，从而它们彼此同构
同构的群之间显然阶数相等，这也解答了我们刚刚的疑惑。
现在再来重新审视一个轨道\(Orb(x_i)\),其内部所有元素的稳定子群的阶是相同的，那么内部所有元素的稳定子群的阶数之和就会等于 \[ \sum |Stab(x_i)|=|Stab(x_i)||Orb(x_i|=|G| \] 那么集合内部所有元素的稳定子群的阶之和就会等于 \[ \sum_{x\in S}|Stab(x)|=\sum_{i=1}^{r} |G|=r|G|\quad\quad\quad\quad\quad\quad(1) \] 这启发我们用另一种方法来计算\(r\).只要能够得到\(\sum_{x\in S}|Stab(x)|\),再除以\(|G|\)，就能得到\(r\)
我们考虑\(G\cross S\)的一个子集\(K=\{(a,x)|a\cdot x=x\}\),
对于一个给定的\(x\in S\),以\(x\)作为第二个值的有序对\((a,x)\)的数量显然就是\(|Stab(x)|\),所以 \[ |K|=\sum_{x\in S}|Stab(x)| \] 问题又转化成了求\(|K|\),不过我们离成功已经很近了。
事实上将问题转化成求\(|K|\)是很有好处的，因为我们可以以\(x\)为关键字来看待它，当然也可以以\(a\)为关键字来看。如此，对于一个给定的\(a\in G\),所有以\(a\)为第一个值的有序对对应的x组成一个集合\(F_a=\{x|a\cdot x=x\}\),我们记其为\(a\)的不动点集
那么 \[ \sum_{x\in S}|Stab(x)|=|K|=\sum_{a\in G}|F_a| \] 从而由\((1)\)式可知 \[ r=\frac{\sum_{x\in S}|Stab(x)|}{|G|}=\frac{1}{|G|}\sum_{a\in G}|F_a| \] 于是我们得到\(Burnside\)引理如下：
设有限群\(G\)在有限集合\(S\)上有一个群作用，那么\(S\)的\(G\)-轨道条数\(r\)为 \[ r=\frac{1}{|G|}\sum_{a\in G}|F_a| \]
这个引理的意义在于，原本单纯只跟集合\(S\)有关的问题，我们可以借用群\(G\)来解决了，而群\(G\)在一些特定情况下有良好的性质能够帮助我们快速计算\(\sum_{a\in G}|F_a|\)
应用
来个具体的例子
给定一个大小为n的环，环上每一个点有m种染色方案。问总共可以染出多少个本质不同的环。这里环本质不同定义为无法通过旋转得到
不妨记环上点的集合为\(B=\{b_1,b_2,...b_n\}\),染色方案集合为\(C=\{c_1,c_2,...c_m\}\),考虑集合 \[ S=B^C=\{X_i\},其中X_i=<c_{i_1},c_{i_2},...c_{i_n}>,1\leq i_j\leq m \] \(S\)的实际含义就是所有给\(B\)中元素染色的方案的集合,每一个方案用一个n元排列表示,显然\(|S|=m^n\)
现在考虑在集合\(B\)上的置换群\(Perm(B)\)的子群\(G=\{\bigl(\begin{smallmatrix} 1 & 2 & ... & n-1 & n\\ 2 & 3 & ...& n & 1 \end{smallmatrix}\bigr),\bigl(\begin{smallmatrix} 1& 2 & 3 & ... & n-1 & n\\ 3 & 4& ...& n & 1 & 2 \end{smallmatrix}\bigr),...,(1)\}\),其中\(G_i=\bigl(\begin{smallmatrix} 1&2 & 3&4&... & n-1 & n\\ i+1& i+2 & ... & n & 1 &...&i \end{smallmatrix}\bigr)\)。显然\(|G|=n\)。此外不难证明\(G\)确实是一个群，这里就不证了。
至于为什么要这样定义，是因为\(G\)中元素实际上代表的就是一个环的旋转（这一点不难发现）与题目给出的本质不同的定义相吻合。整个\(G\)就恰好代表了环上的所有旋转操作，如果我们能证明有限群\(G\)在集合\(S\)上有一个作用,那么本质不同的环的数量不就是\(S\)的\(G\)-轨道条数了吗，从而可以用\(Burnside\)引理求解
我们来证明有限群\(G\)确实在集合\(S\)上有一个作用
证明：
考虑 \[ \phi:G\cross S\rightarrow S \\ (a,x)\mapsto a\cdot x \] 这里\(a\)是一个置换，\(x\)是一个大小为\(n\)的排列，那么此时\(a\cdot x\)就是一个普通的 置换在排列上的作用了，这样定义显然是合理的。
要证明\(G\)在\(S\)上有群作用，我们只需要证明 \[ e\cdot x=x,\forall x\in S \\ (a\circ b)\cdot x=a\cdot (b\cdot x) \] 第一点非常显然，\(G\)中的\(e\)就是恒等变换，它作用在一个排列上显然保持不变
第二点其实就是置换的复合性质的描述，我们当然知道它是成立的
从而\(G\)确实在\(S\)上有一个群作用，那么我们就可以用\(Burnside\)引理来处理这个问题了。 \(\square\)
我们要求本质不同的环的数量，也就是求\(S\)的\(G\)-轨道条数\(r\),从而 \[ r=\frac{1}{|G|}\sum_{a\in G}|F_a|=\frac{1}{n}\sum_{a\in G}|F_a| \] 此时问题变成对于\(G\)内的每一个置换，求其不动点集的阶
不妨来看个简单版本，我们就令\(n=4\)。此时总共有4个置换，
- \(a_1=\bigl(\begin{smallmatrix} 1 & 2 & 3 & 4 \\ 2 & 3 &4 & 1 \end{smallmatrix}\bigr)\),此时显然需要\(x_i\)内所有\(c_{i_j}\)都相等，从而\(|F_{a_1}|=m\)
- \(a_2=\bigl(\begin{smallmatrix} 1 & 2 & 3 & 4 \\ 3 & 4 & 1 & 2 \end{smallmatrix}\bigr)\),\(1,3\)是一组，\(2,4\)是一组，所以\(|F_{a_2}|=m^2\)
- 同理可得\(|F_{a_3}|=m\)
- \(a_4=(1)\),每一个排列在\(a_4\)作用下都保持不变，元素对应的颜色自然也不变，从而\(|F_{a_4}|=|S|=m^n\)
从而\(r=\frac{1}{n}(m^n+2m+m^2)\)
但是当\(n\)逐渐变大的时候,这种暴力枚举的方法将会变的寸步难行。这里再引入一个概念
置换群的轮换指标
置换型：如果\(n\)元置换\(g\)中有\(b_i\)个长度为\(i\)的轮换，那么\(g\)的置换型为\({x_1}^{b_1}{x_2}^{b_2}...{x_n}^{b_n}\)，其中\(\sum i*b_i=n\)显然成立。这里\(x_i\)只是一个形式
设\((G,\circ)\)是一个\(n\)元置换群，那么它的轮换指标定义为 \[ P_G(x_1,x_2,...x_n)=\frac{1}{|G|}\sum_{g\in G}x_1^{b_1}x_2^{b_2}...x_{n}^{b_n} \]
\({x_i}^{b_i}\)就表示在一个置换\(g\)内有\(b_i\)个\(i\)-轮换，而对于一个轮换，其内所有点都是可以互相到达的，所以轮换内部的点的颜色一定得相同，从而这个轮换的染色方案就是\(m\),从而,对于置换\(g\),\(|F_g|=m^{b_1}m^{b_2}...m^{b_n}\)
从而 \[ r=\frac{1}{|G|}\sum_{a\in G}|F_a|=\frac{1}{|G|}\sum_{a\in G}x_1^{b_1}x_2^{b_2}...x_{n}^{b_n}=P_G(x_1,x_2,...x_n) \] 现在问题就变成了求置换群\(G\)的轮换指标
这里给出一些结论
正n边形的旋转群的轮换指标
\[ P_G=\frac{1}{n}\sum_{d|n}\phi_d{x_d}^{\frac{n}{d}} \]
这其实就是我们刚刚在研究的问题
注意到正n边形的旋转群\(G\)中，\(G_i\)就表示旋转步长为\(i\)的置换组成，我们有如下结论： \[ |F_{G_i}|=(n,i) \] 证明：
- \(i|n\),每次走i步，\(n/i\)次后回到原点，所以该置换可以拆成i个轮换，每一个轮换的阶为\(n/i\)。显然有\(|F_{G_i}|=i=(n,i)\)
- \(i\nmid n\),每次走\(i\)步，回到原点需要\(lcm(n,i)\)次，从而每一个轮换的阶为\(lcm(n,i)/i\),那么\(|F_{G_i}|=n/(lcm(n,i)/i)=ni/lcm(n,i)=(n,i)\)
\(\square\)
未完待续