Burnside引理

書接上回，繼續深入研究在群作用下集合的軌道與穩定子群的相關性質

現在我們想要研究這樣一個問題：
$$有限群G在有限集合S上面有一個作用，那么S的G?軌道條數是多少$$
也就是在有限群$G$作用下集合$S$的等價類的數量

不妨設$S$有$r$條$G$-軌道條數，那么就有
$$S=\underset{i=1}{\overset{r}{?}}Orb(x_i)$$
其中$x_i$就是每一條軌道的代表元。注意到任意兩條軌道交集為空，所以
$$|S|=\underset{i=1}{\overset{r}{?}}|Orb(x_i)|=\underset{i=1}{\overset{r}{?}}\frac{|G|}{|Stab(x_i)|}$$
這里有點怪，它似乎暗示我們同一個軌道的元素的不變子群的階都是一樣的。我們再仔細研究一下

$?x,y\in S$,且$x$,$y$在同一條軌道里面，$?a\in G,a?x=y$。則
$$\begin{gathered} h\in Stab(y)?h?y=y \\ ?h?(a?x)=a?x \\ ?(ha)?x=a?x \\ ?a^{?1}?((ha)?x)=(a^{?1}?(a?x)) \\ ?(a^{?1}ha)?x=x \\ ?a^{?1}ha\in Stab(x) \\ ?h\in a^{?1}Stab(x)a \end{gathered}$$

注意到上述過程都是等價的，所以我們很快得到
$$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|(1)$$
這啟發我們用另一種方法來計算$r$.只要能夠得到${\sum }_{x\in S}|Stab(x)|$,再除以$|G|$，就能得到$r$

---

我們考慮$G?S$的一個子集$K=\{(a,x)|a?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 ? x = x } F_a=\{x|a\cdot x=x\} Fa?={x∣a?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 } B=\{b_1,b_2,...b_n\} B={b1?,b2?,...bn?},染色方案集合為 C = { c 1 , c 2 , . . . c m } C=\{c_1,c_2,...c_m\} C={c1?,c2?,...cm?},考慮集合
S = B C = { X i } , 其中 X i = < c i 1 , c i 2 , . . . c i n > , 1 ≤ i j ≤ m S=B^C=\{X_i\},其中X_i=<c_{i_1},c_{i_2},...c_{i_n}>,1\leq i_j\leq m S=BC={Xi?},其中Xi?=<ci1??,ci2??,...cin??>,1≤ij?≤m
$S$的實際含義就是所有給$B$中元素染色的方案的集合,每一個方案用一個n元排列表示,顯然$|S|=m^n$

現在考慮在集合$B$上的置換群$Perm(B)$的子群 G = { ( 1 2 . . . n ? 1 n 2 3 . . . n 1 ) , ( 1 2 3 . . . n ? 1 n 3 4 . . . n 1 2 ) , . . . , ( 1 ) } 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={(12?23?......?n?1n?n1?),(13?24?3...?...n?n?11?n2?),...,(1)},其中$G_i=\left(\begin{array}{ccccccc}1& 2& 3& 4& ...& n?1& n\\ i+1& i+2& ...& n& 1& ...& i\end{array}\right)$。顯然$|G|=n$。此外不難證明$G$確實是一個群，這里就不證了。

至于為什么要這樣定義，是因為$G$中元素實際上代表的就是一個環的旋轉（這一點不難發現）與題目給出的本質不同的定義相吻合。整個$G$就恰好代表了環上的所有旋轉操作，如果我們能證明有限群$G$在集合$S$上有一個作用,那么本質不同的環的數量不就是$S$的$G$-軌道條數了嗎，從而可以用$Burnside$引理求解

我們來證明有限群$G$確實在集合$S$上有一個作用

證明：

考慮
$$\begin{gathered} ?:G?S\to S \\ (a,x)?a?x \end{gathered}$$
這里$a$是一個置換，$x$是一個大小為$n$的排列，那么此時$a?x$就是一個普通的 置換在排列上的作用了，這樣定義顯然是合理的。

要證明$G$在$S$上有群作用，我們只需要證明
$$\begin{gathered} e?x=x,?x\in S \\ (a°b)?x=a?(b?x) \end{gathered}$$
第一點非常顯然，$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=\left(\begin{array}{cccc}1& 2& 3& 4\\ 2& 3& 4& 1\end{array}\right)$,?此時顯然需要$x_i$內所有$c_{i_j}$都相等，從而$|F_{a_1}|=m$
• $a_2=\left(\begin{array}{cccc}1& 2& 3& 4\\ 3& 4& 1& 2\end{array}\right)$,$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,°)$是一個$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}{?}_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?n$,每次走$i$步，回到原點需要$lcm(n,i)$次，從而每一個輪換的階為$lcm(n,i)/i$,那么$|F_{G_i}|=n/(lcm(n,i)/i)=ni/lcm(n,i)=(n,i)$

$\square$

未完待續（肝不動了，下周回來補…）