Burnside の補題と巡回指数：ネックレスと立方体の塗り分けを数える

$6$ 個のビーズを $2$ 色で塗り、回して重なるものを同じとみなします。塗り方は $2^6=64$ 通り、回転は $6$ 通り。$64$ を $6$ で割ると割り切れない。

回転で自分自身に戻る塗り方があるためです。その分を勘定に入れる式が、Burnside の補題と呼ばれるものです^[3]。

単純に割れない理由

赤白を交互に並べた $6$ ビーズは、$2$ 個ぶん回すと自分に戻る。この塗り方の軌道は $6$ 個ではなく $3$ 個。

すべて赤なら軌道は $1$ 個です。軌道の大きさがそろわないため、全体を群の位数で割る計算が合いません。

軌道の大きさは、その塗り方を固定する元の個数だけ小さくなる。だから固定するほうを数えれば勘定が合う、という発想になります。

軌道と安定化群

補題の証明で使う関係を先に示しておく。有限群 $G$ が集合 $X$ に作用し、$x\in X$ をとります。

$G_x=\{g\in G:g\cdot x=x\}$ を安定化群、$G\cdot x=\{g\cdot x:g\in G\}$ を軌道といいます^[1]。

写像 $G\to G\cdot x$、$g\mapsto g\cdot x$ を見ましょう。全射であることは軌道の定義そのもの。

$g\cdot x=h\cdot x$ は $h^{-1}g\in G_x$ と同値になる。だから同じ点へ送られる $g$ の全体は、左剰余類 $h{G}_x$ そのものです。

剰余類はどれも $|G_x|$ 個の元を持ち、たがいに交わりません。軌道の点 $1$ つに剰余類が $1$ つ対応するため、次が成り立つ^[1][4]。

$$|G|=|G_x|\cdot |G\cdot x|$$

軌道が大きいほど安定化群は小さい。積が $|G|$ で一定なので、片方を数えればもう片方が決まります。

補題

有限群 $G$ が有限集合 $X$ に作用し、軌道が $r$ 個あるとします。$\mathrm{Fix}(g)=\{x\in X:g\cdot x=x\}$ と置くと^[1]

$$r=\frac{1}{|G|}\sum _{g\in G}|\mathrm{Fix}(g)|$$

が成り立ちます^[3]。軌道の個数は、各元が止める点の個数の平均です。

証明は $\{(g,x)\in G\times X:g\cdot x=x\}$ を 2 通りに数えることでできる^[1]。

$g$ から先に数えると ${\sum }_g|\mathrm{Fix}(g)|$、$x$ から先に数えると ${\sum }_x|G_x|$ になる。ここで前の節の等式を使います。

$$\sum _{g\in G}|\mathrm{Fix}(g)|=\sum _{x\in X}|G_x|=\sum _{x\in X}\frac{|G|}{|G\cdot x|}$$

両辺を $|G|$ で割ると、右辺は ${\sum }_{x}1/|G\cdot x|$ になる。長さ $n$ の軌道の中の点は、それぞれ $1/n$ ずつ寄与します。$n$ 個あるので合わせて $1$ になり、軌道ごとに $1$ が立つ。合計は軌道の個数です^[1]。

名前について

この式は Burnside のものではありません^[3]。

Cauchy が 1845 年に知っていて、Frobenius が 1887 年に定理の形で発表しました^[3]。Burnside は 1897 年の教科書に、Frobenius への言及つきで載せています^[1]。

ところが 1911 年の第 2 版でその言及が落ちました^[3]。1960 年ごろから「Burnside の補題」という呼び名が定着し、いまに至ります。

Cauchy-Frobenius の定理、あるいは冗談まじりに「Burnside のものでない補題」とも呼ばれる^[3]。Conrad も、Burnside は自著で Frobenius に帰していると注意しています^[1]。

ネックレスを数える

$n$ 個のビーズを $a$ 色で塗り、回転で同一視する。$k$ 個ぶん回す置換を ${\sigma }_k$ と書きます。

ビーズの位置を $\mathbb{Z}/n$ と見ると、${\sigma }_k$ が生成する巡回群は $⟨k⟩$ で、その位数は $n/\gcd (k,n)$ です。${\sigma }_k$ の巡回は $⟨k⟩$ による剰余類にあたるため、個数は次のように決まる。

$$n÷\frac{n}{\gcd (k,n)}=\gcd (k,n)$$

同じ巡回に入るビーズは、同じ色でなければ固定されない。よって固定される塗り方は $a^{\gcd (k,n)}$ 通りです。

$$r=\frac{1}{n}\sum _{k=1}^n{a}^{\gcd (k,n)}$$

約数でまとめ直します。$g$ を $n$ の約数とし、$\gcd (k,n)=g$ となる $k$ を数えましょう。

$k=g{k}^{\prime }$ と書くと $1\le k^{\prime }\le n/g$ で、条件は $\gcd (k^{\prime },n/g)=1$ に読み替わる。この $k^{\prime }$ の個数がオイラー関数 $\phi (n/g)$ です。

$$r=\frac{1}{n}\sum _{d\mid n}\phi (d)a^{n/d}$$

$n=6$、$a=2$ で計算します。$\phi (1)=1$、$\phi (2)=1$、$\phi (3)=2$、$\phi (6)=2$。

$$r=\frac{1}{6}\left(2^6+2^3+2\cdot 2^2+2\cdot 2^1\right)=\frac{64+8+8+4}{6}=\frac{84}{6}=14$$

$14$ 通りになる。冒頭の $64÷6$ が割り切れなかったぶんを、固定される塗り方が埋めました。

裏返しも許すと

ネックレスをひっくり返してよいことにすると、群が二面体群になります。位数は $2n$。

$n=6$ では鏡映が $6$ 本あります。向かい合う頂点を通る軸が $3$ 本で、$2$ 個を固定し残りを $2$ 個ずつ組にするため巡回は $4$ 個、固定される塗り方は $2^4=16$ 通り。

辺の中点を通る軸が $3$ 本あり、$3$ 組の入れ替えになって $2^3=8$ 通りです。

$$r=\frac{84+3\cdot 16+3\cdot 8}{12}=\frac{84+72}{12}=\frac{156}{12}=13$$

回転だけなら $14$、裏返しも許すと $13$ になる。差の $1$ は、鏡映で初めて重なる 2 つが 1 つにまとまったぶんです。

立方体の頂点と辺

同じ補題を立方体で使います。まず回転群の位数を、軌道と安定化群の関係から出しましょう。

面を 1 枚とると、その面をそれ自身へ送る回転は、面に垂直な軸まわりの $4$ 通りです。面の軌道は $6$ 枚の面全体なため、位数は $4\times 6=24$ になる^[2]。

内訳は 5 種類です^[2]。

頂点 8 個を 2 色で塗る場合を数えます。恒等変換は $2^8=256$。面まわりの 90 度は頂点を 4 個ずつ 2 組の巡回にするので $2^2=4$。面まわりの 180 度は 2 個ずつ 4 組で $2^4=16$。

対角線まわりは 2 個を固定して 3 個ずつ 2 組なので $2^4=16$。辺まわりは 2 個ずつ 4 組で $2^4=16$ です。

$$r=\frac{256+6\cdot 4+3\cdot 16+8\cdot 16+6\cdot 16}{24}=\frac{552}{24}=23$$

辺 12 本でも同じ手順です。$4096$、$8$、$64$、$16$、$128$ と並び、合計は $5232$。$24$ で割って $218$ 通りになる。

巡回指数

数え上げの型を式にまとめます^[2]。置換 $\pi$ が長さ $1$ の巡回を $b_1$ 個、長さ $2$ を $b_2$ 個、と持つとき、$\pi$ に $x_1^{b_1}{x}_2^{b_2}\cdots$ を対応させる。

群 $G$ 全体で平均をとったものが巡回指数です^[2][4]。

$$P_G(x_1,x_2,\dots )=\frac{1}{|G|}\sum _{\pi \in G}{x}_1^{b_1(\pi )}{x}_2^{b_2(\pi )}\cdots$$

立方体の面への作用では、5 種類がそれぞれ $x_1^6$、$x_1^2{x}_4$、$x_1^2{x}_2^2$、$x_3^2$、$x_2^3$ に対応します^[2]。

$$P_G=\frac{1}{24}\left(x_1^6+6x_1^2{x}_4+3x_1^2{x}_2^2+8x_3^2+6x_2^3\right)$$

すべての変数に色の数 $c$ を入れると、補題の式に戻る。$c=2$ なら次のようになる。

$$P_G(2,2,2,2)=\frac{64+48+48+32+48}{24}=\frac{240}{24}=10$$

Pólya の定理

代入する相手を数から多項式に替えると、内訳まで数えられます。定理の形に書きましょう^[4][5]。

$X$ を塗る場所の集合、$Y$ を色の集合とします。色 $c$ に重み $\mu (c)$ を与え、塗り方 $f:X\to Y$ の重みを積で定めます。

$$W(f)=\prod _{x\in X}\mu (f(x))$$

同じ軌道に入る 2 つの塗り方は、同じ重みを持つ。$f_2=f_1\circ \pi$ なら、積の順が変わるだけだからです^[4]。よって軌道にも重みが定まる。

主張は、軌道の重みの総和が巡回指数への代入で書けることです^[4][5]。

$$\sum _{\text{軌道}}W=P_G\left(\sum _{c\in Y}\mu (c),\sum _{c\in Y}\mu (c{)}^2,\dots \right)$$

証明は補題の重み付き版です。重みは軌道の上で一定だから、重み $\omega$ を持つ軌道だけを集めた集合に補題を当てられます^[4]。

$$|\{\omega \text{の軌道}\}|=\frac{1}{|G|}\sum _{\pi \in G}|\{f\in \mathrm{Fix}(\pi ):W(f)=\omega \}|$$

両辺に $\omega$ をかけ、$\omega$ について足し合わせます。左辺は軌道の重みの総和になり、右辺は $\frac{1}{|G|}{\sum }_{\pi }{\sum }_{f\in \mathrm{Fix}(\pi )}W(f)$ です。

内側の和を計算しましょう。$\pi$ が固定する塗り方は、各巡回の上で色が一定のものに限られます。

長さ $i$ の巡回を色 $c$ で塗ると、その巡回は場所を $i$ 個持つので重みに $\mu (c{)}^i$ を出す。巡回ごとの色の選び方は独立で、和が積に分かれます^[5]。

$$\sum _{f\in \mathrm{Fix}(\pi )}W(f)=\prod _i{\left(\sum _{c\in Y}\mu (c{)}^i\right)}^{b_i(\pi )}$$

右辺は、$x_i$ に ${\sum }_c\mu (c{)}^i$ を入れた単項式そのものです。$\pi$ について平均をとると巡回指数への代入になり、主張が示せました。

$\mu$ をすべて $1$ にすると重みが全部 $1$ になり、軌道の個数を数える式に戻ります。補題は、この定理で重みを落とした場合にあたる。

色ごとに数える

立方体の面で定理を使います。黒に $b$、白に $w$ を重みとして割り当てると、$x_i$ に入るのは $b^i+w^i$ です。

できあがる多項式の $b^k{w}^{6-k}$ の係数が、黒を $k$ 枚使う塗り分けの個数になる。

黒 $3$ 枚のところを計算しましょう。$x_1^6$ からは $(b+w{)}^6$ の $b^3{w}^3$ の係数で $20$。$x_1^2{x}_2^2$ からは $4$ になり、$3$ 倍して $12$。$x_3^2$ からは $(b^3+w^3{)}^2$ の中央の項で $2$、$8$ 倍して $16$。

$x_1^2{x}_4$ と $x_2^3$ からは $b^3{w}^3$ が現れません。指数の偶奇が合わないためです。

$$\frac{20+12+16}{24}=\frac{48}{24}=2$$

黒 $3$ 枚の塗り分けは $2$ 通り。1 つの頂点に集まる 3 枚を黒くする形と、帯のように 3 枚を並べる形です。

合同式が副産物になる

補題からは整数の合同式も手に入ります^[1]。

ネックレスの個数は整数だから、$\frac{1}{m}{\sum }_{k=1}^m{a}^{\gcd (k,m)}$ も整数になる。分母を払うと次の形になる。

$$\sum _{k=1}^m{a}^{\gcd (k,m)}\equiv 0(\mathrm{mod}m)$$

これが任意の整数 $a$ と正整数 $m$ で成り立ちます^[1]。

$m$ が素数 $p$ のときを見ましょう。$\gcd (k,p)$ は $k=p$ でだけ $p$、ほかは $1$ です。

$$(p-1)a+a^p=(a^p-a)+pa\equiv 0(\mathrm{mod}p)$$

$pa$ は $p$ で割り切れるため $a^p\equiv a(\mathrm{mod}p)$。Fermat の小定理でした^[1]。

ビーズの並べ方を数えただけで、数論の定理まで届きます。軌道の個数が整数だという当たり前の事実が効いている。

軌道の個数そのものを数えるかわりに、各元が止める点を数える。補題はその 2 つを等式で結んでいます。

巡回指数まで進めると、変数を残したまま同じ計算が通ります。数のかわりに多項式を代入するだけで、内訳が係数として並ぶ。

出典