Burnsideの補題 - 群作用による数え上げ

群 $G$ が集合 $X$ に作用しているとき、軌道の数を求める問題は組合せ論で頻繁に現れます。素朴に数えようとすると「回転して同じになるものを何度も数えてしまう」という困難にぶつかりますが、Burnside の補題はこの問題をきれいに解決します。

不動点と軌道

群 $G$ が有限集合 $X$ に作用しているとします。各群元 $g\in G$ に対して、$g$ で動かない元の集合を

$$X^g=\{x\in X\mid g\cdot x=x\}$$

と書き、これを $g$ の不動点集合と呼びます。一方、$x\in X$ の軌道とは

$$G\cdot x=\{g\cdot x\mid g\in G\}$$

のことで、群作用によって $x$ から到達できる元全体の集合です。軌道は $X$ の分割を与えるので、軌道の個数 $|X/G|$ は「本質的に異なる元が何種類あるか」を意味しています。

Burnside の補題の主張

Burnside の補題（Cauchy-Frobenius の補題とも呼ばれる）は次のように述べられます。

$$|X/G|=\frac{1}{|G|}\sum _{g\in G}|X^g|$$

つまり、軌道の数は「各群元の不動点の数の平均」に等しいという主張です。右辺はすべての群元について不動点を数えて合計し、群の位数で割るだけなので、計算が非常にしやすい形になっています。

証明

次の集合のペアを二通りに数えます。

$$S=\{(g,x)\in G\times X\mid g\cdot x=x\}$$

$g$ を固定して $x$ を動かすと、条件を満たす $x$ の個数は $|X^g|$ です。したがって

$$|S|=\sum _{g\in G}|X^g|$$

となります。逆に $x$ を固定して $g$ を動かすと、条件を満たす $g$ の集合は $x$ の安定化群 $G_x$ にほかなりません。したがって

$$|S|=\sum _{x\in X}|G_x|$$

とも書けます。軌道・安定化群定理 $|G|=|G\cdot x|\cdot |G_x|$ を使うと $|G_x|=|G|/|G\cdot x|$ なので

$$\sum _{x\in X}|G_x|=\sum _{x\in X}\frac{|G|}{|G\cdot x|}$$

が得られます。ここで、同じ軌道 $O$ に属する元はすべて $|G\cdot x|=|O|$ を満たすため、軌道 $O$ に属する元の寄与を合計すると

$$\sum _{x\in O}\frac{|G|}{|O|}=|O|\cdot \frac{|G|}{|O|}=|G|$$

です。軌道の個数を $|X/G|$ と書けば

$$|S|=|X/G|\cdot |G|$$

となり、2 つの表示を等しいとおくと

$$\sum _{g\in G}|X^g|=|X/G|\cdot |G|$$

が得られます。両辺を $|G|$ で割れば Burnside の補題が証明されます。

例 1：正方形の頂点の塗り分け

正方形の 4 つの頂点を白と黒の 2 色で塗る場合を考えます。回転で同じになるものは区別しないとすると、本質的に何通りの塗り方があるかを Burnside の補題で求めます。

正方形の回転群は $G=\{e,r,r^2,r^3\}$ で、$r$ は $90°$ 回転です。集合 $X$ は「4 頂点を 2 色で塗る方法全体」なので $|X|=2^4=16$ です。

各群元の不動点数を確認します。恒等変換 $e$ はすべての塗り方を固定するので $|X^e|=16$ です。$90°$ 回転 $r$ で不変な塗り方は、4 頂点がすべて同じ色でなければならないので $|X^r|=2$（全部白か全部黒）です。$180°$ 回転 $r^2$ は対角の頂点を入れ替えるので、対角同士が同じ色であればよく $|X^{r^2}|=2^2=4$ です。$270°$ 回転 $r^3$ は $90°$ 回転の逆なので $|X^{r^3}|=2$ です。

Burnside の補題を適用すると

$$|X/G|=\frac{1}{4}(16+2+4+2)=\frac{24}{4}=6$$

となり、回転で同一視したとき 6 通りの塗り方が存在することがわかります。

例 2：裏返しも許す場合

正方形は回転だけでなく裏返し（反転）もできます。裏返しも含めた対称群は位数 8 の二面体群 $D_4$ です。$D_4$ は 4 つの回転と 4 つの反転からなります。

反転の不動点数について補足します。縦軸で裏返す $s_1$ は左右の頂点を入れ替えるので、左右で同じ色であればよく $2^3$ ではなく、正確には上の頂点・下の頂点がそれぞれ自由で、左右のペアが 2 組あるので $|X^{s_1}|=2\times 2\times 2=8$——いえ、もう少し丁寧に見ます。縦軸反転は頂点 1, 3 を固定し頂点 2, 4 を入れ替えるので、頂点 1 は自由（2 通り）、頂点 3 は自由（2 通り）、頂点 2 と 4 は同色（2 通り）で $|X^{s_1}|=2^3=8$ です。横軸反転も同様に $|X^{s_2}|=8$ です。対角線反転はそれぞれ 2 頂点を固定して残り 2 頂点を入れ替えるので $|X^{s_3}|=|X^{s_4}|=2^3=4$——ここは頂点の番号付けによりますが、対角線反転では 1 頂点のみが固定され残り 3 頂点が 2 つの軌道に分かれるので $|X^{s_3}|=2^2=4$ です。

Burnside の補題を適用すると

$$|X/D_4|=\frac{1}{8}(16+2+4+2+8+8+4+4)=\frac{48}{8}=6$$

となります。この場合は回転のみの場合と同じ 6 通りになりますが、これは 2 色という選択肢が少ないためです。色数が増えると、回転のみの場合と裏返しも許す場合で結果が変わってきます。

例 3：3 色で正三角形を塗る

正三角形の 3 頂点を赤・青・緑の 3 色で塗る場合を考えます。回転群は $G=\{e,r,r^2\}$（$r$ は $120°$ 回転）で $|X|=3^3=27$ です。

恒等変換 $e$ はすべてを固定するので $|X^e|=27$ です。$120°$ 回転 $r$ で不変になるには 3 頂点が同色でなければならず $|X^r|=3$ です。$240°$ 回転 $r^2$ も同様に $|X^{r^2}|=3$ です。

$$|X/G|=\frac{1}{3}(27+3+3)=\frac{33}{3}=11$$

名称について

この補題は Burnside の名前で広く知られていますが、実際にはそれ以前に Cauchy や Frobenius が同じ結果を証明しています。Burnside 自身もこの結果が自分のオリジナルだとは主張しておらず、彼の教科書で紹介したことで広まったという経緯があります。数学ではこうした「名前の帰属が実際の発見者とずれる」現象がしばしば見られ、Stigler の法則（「科学的発見にはその発見者の名前がつかない」という経験則）の典型例とされています。

Burnside の補題は、群作用の理論の中でも特に応用範囲が広い結果です。次の記事で扱う Pólya の数え上げ定理は、Burnside の補題をさらに精密化したもので、「各色を何個使ったか」という情報まで追跡できるようになります。