Burnside の補題に関するノート。

概要

Burnside の補題は、有限群の軌道の個数を求める式を決定する定理だ。

定理

定理： 有限群 $G$ が空でない集合 $X$ に作用しているとする。 このとき $G$ 軌道の個数 $N$ は次で与えられる：

\[\tag*{$\spadesuit0$} N = \frac{1}{\lvert G \rvert} \sum_{g \in G}\lvert X^g \rvert.\]

ただし $X^g \coloneqq \lbrace x \in X \,\mid\, g \cdot x = x\rbrace$ とする。

証明の検討：

軌道の個数 $N$ は「$G$ の要素によって固定される点の数」の平均値に等しいと主張している。 右辺の和はカギ括弧部分を表現している。

$g \in G$ と $x \in X$ と二つ不確定要素があるので、二通りの数え方が考えられる。 その過程で固定部分群 $G_x$ の性質を利用できるだろう。

参考資料 (Wikipedia) の証明中の $X/G$ は $G$ 軌道の集合を意味するようだ。 つまり $\lvert X/G \rvert = N.$

証明：

まず $\spadesuit$ の右辺の和を書き直すために

\[S = \{(g, x) \in G \times X\,|\, g \cdot x = x\}\]

とおくと、次の等式が成り立つ：

\[\tag*{$\spadesuit1$} \sum_{g \in G}\lvert X^g \rvert = \sum_{x \in X} \lvert G_x\rvert.\]

軌道・固定部分群定理によると、各 $x \in X$ に対して軌道 $O(x) = \lbrace g \cdot x\,\mid\, g \in G\rbrace \subset X$ と剰余群 $G/G_x$ の間に全単射写像が存在する。Lagrange の定理により次が成り立つ：

\[\lvert G \rvert = \lvert O(x) \rvert \lvert G_x \rvert.\]

これを使って $\spadesuit1$ 右辺の和を書き換えると：

\[\tag*{$\spadesuit2$} \begin{aligned} \sum_{x \in X} \lvert G_x\rvert &= \sum_{x \in X} \frac{\lvert G \rvert}{\lvert O(x) \rvert}\\ &= \lvert G \rvert \sum_{x \in X} \frac{1}{\lvert O(x) \rvert}. \end{aligned}\]

集合 $X$ が $N$ 個の軌道による軌道分解を持つという仮定から、 $x \in X$ にわたる和は各軌道についての和にバラバラにできる。 軌道分解を $\displaystyle X = \bigsqcup_{i = 1}^n O(x_i)$ とおくと：

\[\tag*{$\spadesuit3$} \begin{aligned} \sum_{x \in X} \frac{1}{\lvert O(x) \rvert} &= \sum_{i = 1}^N \sum_{x \in O(x_i)}\frac{1}{\lvert O(x) \rvert}\\ &= \sum_{i = 1}^N 1\\ &= N. \end{aligned}\]

$\spadesuit1, \spadesuit2, \spadesuit3$ を合わせて次の結果を得る：

\[\therefore \sum_{g \in G}\lvert X^g\rvert = \lvert S \rvert = \sum_{x \in X}\lvert G_x\rvert = \lvert G \rvert N.\]

したがって $\spadesuit0$ が成り立つ。 $\blacksquare$

応用

本補題をうまく利用することで対称的な図形に何かをするときの方法数を決定できる。 適用例：

  • $k$ 色の塗料を $1 \times n$ マスの細長い盤に塗り分けるやり方は何通りか。
  • $k$ 種類のじゅうぶんな量の宝石から 6 個選んで首飾りを作るやり方は何通りあるか。
    • $k$ 種類の 2 個ずつ相当の量の宝石ではどうか。
  • 立方体は 3 色で何通りに塗り分けられるか。

決定手順は：

  • 補題の $X$ として色や宝石などの組の集合をとる。塗料問題の例では長さ 6 の色からなる組の集合になる。
  • $X$ に作用する群 $G$ およびその作用は図形の対称性により決定する。
    • 塗料問題で作用している群は次のようなものだ： $\lbrace e, g \rbrace.$ ただし $g = (1, n)(2, n - 1)\dotsb(n - 1, 2)(n, 1) \in S_n.$
    • 首飾り問題では二面体群 $D_{12}$ が作用している。
    • 立方体問題では立方体の回転群が作用している。これは対称群 $S_4$ と同型の群だ。
  • $G$ 軌道の個数が求める値だ。
    • 塗料問題
      • $\lvert X^e \rvert = \lvert X \rvert = k^n.$
      • $\lvert X^g \rvert$ は $n$ が偶数か奇数かで異なるが、偶数の場合は $k^{n/2},$ 奇数の場合は $k^{(n+1)/2}$ となる。

      • これらの平均値が求める塗り方数だ：

        \[N = \lvert X/G \rvert = \begin{cases} \dfrac{1}{2}(k^n + k^{n/2}), & \text{k : even number,}\\ \dfrac{1}{2}(k^n + k^{(n+1)/2}) & \text{k : odd number.}\\ \end{cases}\]
    • 首飾り問題
      • まず $D_{12} = \lbrace e, r, r^2, \dotsc, r^5, s_1, s_2, \dotsc, s_6\rbrace$ と置く。 $r$ は 60 度の回転変換、$s_i$ はある軸に関する鏡映変換を意味する。
      • 次に各 $\lvert X^g\rvert$ を決定する。
        • $\lvert X^e \rvert = k^6.$
        • $\lvert X^r \rvert = k.$ なぜなら $r\cdot x = x$ となるには石がすべて同じであることが必要だから。
        • $\lvert X^{r^2} \rvert = k^2.$ なぜなら $0, 120, 240$ 度の石と $60, 180, 300$ 度の石がそれぞれ同じであることが必要だから。
        • 残りの回転変換についてもこのように決定する。
        • 鏡映変換については軸が頂点を共有するものとそうでないものとで場合分けする。 $k^3$ の場合と $k^4$ の場合がある。
      • 以上の平均値をとる（つまり 12 で割る）。
    • 立方体問題は Wikipedia からの引用だ。

参考文献