Burnsideの補題

同義語：バーンサイドの補題Burnside's lemmaCauchy–Frobeniusの補題Cauchy–Frobenius lemma

概要

前提知識: 群の作用, 置換, 巡回置換

正方形の 4 つの頂点を赤と白で塗る方法は $2^4=16$ 通りあるが、回して重なるものを同じとみなすと 6 通りになる。この「対称性で移り合うものを同一視した個数」は、群の作用の軌道の個数である。Burnside の補題（Burnside's lemma）は、有限群 $G$ が有限集合 $X$ に作用するとき、軌道の個数が「$G$ の元が動かさない点の個数の平均」に等しいことを述べる。軌道を 1 つずつ調べる代わりに、群の元ごとに動かない点を数えればよく、塗り分けの数え上げでは動かない点の個数が巡回の個数だけで決まるので、計算が機械的になる。
この補題は Cauchy–Frobenius の補題とも呼ばれる（節「補足」）。同じ Burnside の名をもつ Burnsideのp^a q^b定理（位数 $p^aq^b$ の群は可解）とは別の主張である。色の使われ方ごとの個数を母関数にまとめる Pólyaの数え上げ定理は、この補題の重みつき版から導かれる。

定義

以下、$G$ を有限群、$X$ を有限集合とし、$G$ は $X$ に左から作用しているとする（群の作用の記事の定義「群の作用」）。$g\in G$ による $x\in X$ の行き先を $gx$ と書く。

固定点集合と軌道の集合

$x\in X$ の軌道を $Gx:=\{gx\mid g\in G\}$、安定化群を $G_x:=\{g\in G\mid gx=x\}$ とする。軌道全体の集合を $X/G$ と書く。
$g\in G$ の固定点集合を $X^g:=\{x\in X\mid gx=x\}$ とする。

軌道は $X$ を交わりのない部分集合に分ける（群の作用の記事の命題「軌道による分割と安定化群」）。$\lvert X/G\rvert$ は、$G$ の元で移り合う点を同一視したときの点の個数である。

主定理

Burnsideの補題

有限群 $G$ が有限集合 $X$ に作用しているとき、
$$ \lvert X/G\rvert=\frac1{\lvert G\rvert}\sum_{g\in G}\lvert X^g\rvert $$
が成り立つ。すなわち、軌道の個数は、$G$ の元が動かさない点の個数の平均に等しい。

組の集合 $\Omega:=\{(g,x)\in G\times X\mid gx=x\}$ の元の個数を 2 通りに数える。$g$ を先に決めると、$x$ は $X^g$ の元なので $\lvert\Omega\rvert=\sum_{g\in G}\lvert X^g\rvert$ である。$x$ を先に決めると、$g$ は $G_x$ の元なので $\lvert\Omega\rvert=\sum_{x\in X}\lvert G_x\rvert$ である。
群の作用の記事の定理「軌道・安定化群定理」により $\lvert G\rvert=\lvert Gx\rvert\cdot\lvert G_x\rvert$、すなわち $\lvert G_x\rvert=\lvert G\rvert/\lvert Gx\rvert$ である。$X$ を軌道ごとに分けて和をとる。1 つの軌道 $O$ に属する点 $x$ はどれも $Gx=O$ を満たすので、
$$ \sum_{x\in O}\lvert G_x\rvert=\lvert O\rvert\cdot\frac{\lvert G\rvert}{\lvert O\rvert}=\lvert G\rvert $$
である。軌道は $\lvert X/G\rvert$ 個あるので $\sum_{x\in X}\lvert G_x\rvert=\lvert G\rvert\cdot\lvert X/G\rvert$ である。2 つの数え方を比べて $\lvert G\rvert$ で割ればよい。$\square$

線形代数による別の証明もある。

平均をとる写像による証明

$V:=\mathbb{Q}^X$ を $X$ の元 $x$ に対応する基底 $e_x$ をもつベクトル空間とし、$\rho(g)e_x:=e_{gx}$ で $G$ を線形に作用させる。

証明を開く

$\rho(g)$ の行列は置換行列で、対角成分は $gx=x$ となる $x$ の所だけ $1$ なので、跡は $\operatorname{tr}\rho(g)=\lvert X^g\rvert$ である。$P:=\frac1{\lvert G\rvert}\sum_{g\in G}\rho(g)$ とおく。$h\in G$ について $g\mapsto hg$ は $G$ の全単射なので $\rho(h)P=P$ であり、これを平均して $P^2=P$ を得る。$P$ の像は $G$ で動かないベクトル全体 $V^G$ に一致する（$\rho(h)P=P$ から像は $V^G$ に含まれ、$v\in V^G$ なら $Pv=v$）。$v=\sum_xc_xe_x$ が $V^G$ に属することは、$c$ が各軌道の上で一定であることと同値なので、$\dim V^G=\lvert X/G\rvert$ である。$P^2=P$ なので $V=\operatorname{Im}P\oplus\operatorname{Ker}P$ と分かれ、$P$ はそれぞれの上で恒等写像と $0$ なので、$\operatorname{tr}P=\dim\operatorname{Im}P$ である。よって $\frac1{\lvert G\rvert}\sum_g\lvert X^g\rvert=\operatorname{tr}P=\dim V^G=\lvert X/G\rvert$ である。$\square$

この証明を複素数体の上の表現で書き直すと、軌道の個数は置換表現の指標と自明な指標の内積になる（指標(表現論) の記事の命題「軌道の個数と 2 重可移性」）。
固定点の個数は共役な元どうしで等しい。

共役な元の固定点

$g,h\in G$ について、$x\mapsto hx$ は $X^g$ から $X^{hgh^{-1}}$ への全単射である。したがって $\lvert X^g\rvert$ は $g$ の共役類だけで決まり、$G$ の共役類を $K_1,\dots,K_r$、その代表元を $g_i\in K_i$ とすると
$$ \lvert X/G\rvert=\frac1{\lvert G\rvert}\sum_{i=1}^{r}\lvert K_i\rvert\,\lvert X^{g_i}\rvert $$
である。

$gx=x$ なら $(hgh^{-1})(hx)=hgx=hx$ なので $hx\in X^{hgh^{-1}}$ である。同じ理由で $y\mapsto h^{-1}y$ は $X^{hgh^{-1}}$ を $X^{h^{-1}(hgh^{-1})h}=X^g$ に写し、2 つの写像は互いに逆である。後半は thm-bl-main の和を共役類ごとにまとめたものである。$\square$

塗り分けの数え上げ

$C$ を $m$ 個の元からなる集合（色の集合）とし、写像 $f\colon X\to C$ を $X$ の塗り分けという。その全体を $C^X$ と書く（$\lvert C^X\rvert=m^{\lvert X\rvert}$）。$g\in G$ と $f\in C^X$ について $(gf)(x):=f(g^{-1}x)$ と定めると、これは $G$ の $C^X$ への作用である（$(g(hf))(x)=(hf)(g^{-1}x)=f(h^{-1}g^{-1}x)=((gh)f)(x)$）。$gf$ は場所 $x$ の色を場所 $gx$ に運んだ塗り分けであり、この作用の軌道が「$G$ の元で移り合うものを同一視した塗り分け」である。
$g$ の作用で定まる $X$ の置換を互いに素な巡回置換の積に分解し（置換の記事の定理「互いに素な巡回置換の積への分解」）、不動点も長さ $1$ の巡回と数えた巡回の個数を $c(g)$ と書く。巡回は、$g$ が生成する部分群 $\langle g\rangle$ の $X$ への作用の軌道 $\{x,gx,g^2x,\dots\}$ のことである。

動かない塗り分けの個数

$g\in G$ について、$gf=f$ であることと、$f$ が $g$ の各巡回の上で一定であることは同値である。したがって $g$ で動かない塗り分けは $m^{c(g)}$ 個ある。

$gf=f$ は、すべての $x$ で $f(g^{-1}x)=f(x)$ となることであり、$x$ を $gx$ に置き換えると、すべての $x$ で $f(x)=f(gx)$ となることと同値である。これを繰り返すと $f(x)=f(g^kx)$（$k\ge0$）なので $f$ は各巡回の上で一定であり、逆に各巡回の上で一定なら $f(gx)=f(x)$ である。よって動かない塗り分けは、$c(g)$ 個の巡回のそれぞれに色を 1 つずつ選ぶことと一対一に対応し、$m^{c(g)}$ 個ある。$\square$

塗り分けの模様の個数

$G$ の元で移り合うものを同一視した $m$ 色の塗り分けの個数は
$$ \lvert C^X/G\rvert=\frac1{\lvert G\rvert}\sum_{g\in G}m^{c(g)} $$
である。

thm-bl-main を $C^X$ への作用に当て、prop-bl-fixed-colorings を代入すればよい。$\square$

色に重みを付け、軌道ごとの重みの和を数えるように thm-bl-main を拡げたものが、Pólyaの数え上げ定理の記事の補題「重みつきの Burnside の補題」であり、重みをすべて $1$ にすると thm-bl-main に戻る。同じ記事の定理「Pólya の数え上げ定理」は、その補題と prop-bl-fixed-colorings の重みつき版から、色の使われ方ごとの個数を巡回指数で表す。cor-bl-colorings は、その定理で重みをすべて $1$ にしたもの（同じ記事の系「模様の総数」）と一致する。

首飾り

円周上に等間隔に並んだ $n$ 個の玉の位置を $\mathbb{Z}/n\mathbb{Z}=\{0,1,\dots,n-1\}$ とし、回転 $\rho(i)=i+1$ が生成する位数 $n$ の巡回群 $C_n=\{\rho^0,\dots,\rho^{n-1}\}$ を考える。$C_n$ の軌道として数えた $m$ 色の塗り分けを 首飾り（ネックレス、necklace）という。$\varphi$ は Euler関数、$\sum_{d\mid n}$ は $n$ の正の約数 $d$ にわたる和である。

回転の巡回

$0\le k< n$ とし、$e:=\gcd(k,n)$ とする（$k=0$ では $e=n$）。$\rho^k$ は $\mathbb{Z}/n\mathbb{Z}$ を、長さ $n/e$ の巡回 $e$ 個に分ける。

$i$ を含む巡回は $\{i+jk\bmod n\mid j\in\mathbb{Z}\}$ である。整数 $jk+ln$（$j,l\in\mathbb{Z}$）の全体は $e$ の倍数全体に等しい（Bézout の等式）ので、この巡回は $\{i+je\bmod n\mid j\in\mathbb{Z}\}$ であり、$e\mid n$ から元の個数は $n/e$ である。巡回はどれも同じ長さで $\mathbb{Z}/n\mathbb{Z}$ を分けるので、個数は $n/(n/e)=e$ である。$\square$

首飾りの個数

$m$ 色の玉で作る長さ $n$ の首飾りの個数は
$$ N(n,m)=\frac1n\sum_{d\mid n}\varphi(d)\,m^{n/d} $$
である。

cor-bl-colorings と lem-bl-rotation により $N(n,m)=\frac1n\sum_{k=0}^{n-1}m^{\gcd(k,n)}$ である。$d\mid n$ を固定し、$\gcd(k,n)=n/d$ となる $0\le k< n$ を数える。そのような $k$ は $n/d$ の倍数なので $k=\frac ndj$（$0\le j< d$）と書け、$\gcd(\frac ndj,n)=\frac nd\gcd(j,d)$ なので、条件は $\gcd(j,d)=1$ と同値である。よって個数は $\varphi(d)$ で、各 $k$ は $m^{n/d}$ を与える。$d$ が $n$ の約数全体を動くと $n/d$ も約数全体を動くので、和は主張の形になる。$\square$

首飾りの個数の整除性

すべての正の整数 $n,m$ について $\sum_{d\mid n}\varphi(d)\,m^{n/d}$ は $n$ で割り切れる。とくに $n=p$ が素数なら $m^p\equiv m\pmod p$（Fermatの小定理）である。

$N(n,m)$ は個数なので整数であり、thm-bl-necklace から前半を得る。$n=p$ のとき約数は $1,p$ で $\varphi(1)=1$、$\varphi(p)=p-1$ なので、$m^p+(p-1)m=(m^p-m)+pm$ が $p$ で割り切れ、$m^p\equiv m\pmod p$ である。$\square$

2 色の首飾りと腕輪

$n=6$、$m=2$ では、約数 $d=1,2,3,6$ について $\varphi(d)=1,1,2,2$ なので、$N(6,2)=\frac16(2^6+2^3+2\cdot2^2+2\cdot2)=\frac{84}6=14$ である。
裏返しも同一視すると、群は回転と鏡映 $\sigma(i)=-i$ が生成する群（$n\ge3$ では位数 $2n$ の二面体群）になり、その軌道を腕輪（bracelet）という。$n\le2$ では鏡映が回転と一致するので、腕輪の個数は首飾りと同じである。$n=6$ の 6 つの鏡映は、向かい合う 2 つの玉を通る軸についての 3 つが巡回 $4$ 個（不動点 2 個と互換 2 個）、向かい合う 2 つの隙間を通る軸についての 3 つが巡回 $3$ 個（互換 3 個）を与える。よって 2 色の腕輪は $\frac1{12}(84+3\cdot2^4+3\cdot2^3)=\frac{156}{12}=13$ 個である。

$n$	1	2	3	4	5	6	7	8
2 色の首飾り $N(n,2)$	2	3	4	6	8	14	20	36
2 色の腕輪	2	3	4	6	8	13	18	30

首飾り $RRWRWW$ と $RRWWRW$ は回転では移り合わないが、裏返すと移り合う。2 色の腕輪が首飾りより初めて少なくなるのは $n=6$ である。

立方体の面

立方体の面の塗り分け

立方体 $[-1,1]^3$ を自分自身に移す回転は 24 個ある。実際、回転は原点を動かさない等長変換なので、立方体の表面で原点に最も近い 6 点（面の中心 $\pm e_1,\pm e_2,\pm e_3$）を入れ替え、その行列は符号付き置換行列である。逆に、符号付き置換行列で行列式が $1$ のものは 24 個あり、どれも立方体を自分自身に移す回転である（特殊直交群の記事の例「立方体を自分自身に移す回転」）。これらは回転軸で次の 5 種類に分かれる。6 つの面の置換としての巡回の個数 $c(g)$ は、各回転の行列を書き出して確かめられる。

回転	個数	面の巡回の長さ	$c(g)$
恒等写像	1	$1,1,1,1,1,1$	6
向かい合う面の中心を通る軸のまわりの $\pm90^\circ$	6	$1,1,4$	3
同じ軸のまわりの $180^\circ$	3	$1,1,2,2$	4
対角線のまわりの $\pm120^\circ$	8	$3,3$	2
向かい合う辺の中点を通る軸のまわりの $180^\circ$	6	$2,2,2$	3

個数の和は $1+6+3+8+6=24$ である。cor-bl-colorings により、$m$ 色で塗る模様は
$$ \frac1{24}\bigl(m^6+6m^3+3m^4+8m^2+6m^3\bigr)=\frac1{24}\bigl(m^6+3m^4+12m^3+8m^2\bigr) $$
通りであり、$m=2$ で $10$ 通り、$m=3$ で $57$ 通りである。
6 つの面を 6 色で 1 色ずつ塗る $6!=720$ 通りの塗り分けの集合を考える。恒等写像以外の回転はどれも 2 つ以上の面を入れ替えるので、この集合のどの塗り分けも動かす。よって thm-bl-main により模様は $720/24=30$ 通りである。

最後の計算のように、恒等元以外のどの元も固定点をもたない（作用が自由な）ときは、どの軌道も $\lvert G\rvert$ 個の点からなり、thm-bl-main は割り算 $\lvert X\rvert/\lvert G\rvert$ になる。この仮定がないと割り算は使えない（節「反例」）。

応用

推移的な作用では平均が $1$ であることから、固定点のない元の存在が出る。

推移的な作用と固定点のない元

有限群 $G$ が、2 個以上の元をもつ有限集合 $X$ に推移的に作用しているとする。このとき、$X$ のすべての点を動かす元 $g\in G$（$X^g=\emptyset$ となる元）が存在する。

推移的なので軌道は 1 つであり、thm-bl-main により $\frac1{\lvert G\rvert}\sum_g\lvert X^g\rvert=1$ である。恒等元 $e$ は $\lvert X^e\rvert=\lvert X\rvert\ge2$ を与えるので、すべての $g$ で $\lvert X^g\rvert\ge1$ なら平均は $1$ より大きくなる。よって $\lvert X^g\rvert=0$ となる $g$ がある。$\square$

真部分群の共役の和

有限群 $G$ の部分群 $H\neq G$ について、$\bigcup_{x\in G}xHx^{-1}\neq G$ である。

$G$ を左剰余類の集合 $G/H$ に $g(xH):=gxH$ で作用させる。これは推移的で、$H\ne G$ なので $\lvert G/H\rvert\ge2$ である。$gxH=xH$ は $x^{-1}gx\in H$、すなわち $g\in xHx^{-1}$ と同値なので、$g$ が $G/H$ のすべての点を動かすことは、$g$ がどの $xHx^{-1}$ にも属さないことと同値である。thm-bl-jordan によりそのような $g$ がある。$\square$

固定点の個数の 2 乗の平均も、軌道の個数で表せる。

2 点の組の軌道

$G$ を $X\times X$ に $g(x,y):=(gx,gy)$ で作用させると、
$$ \frac1{\lvert G\rvert}\sum_{g\in G}\lvert X^g\rvert^2=\lvert(X\times X)/G\rvert $$
である。$G$ の $X$ への作用が推移的で $\lvert X\rvert\ge2$ なら右辺は $2$ 以上であり、右辺が $2$ であることと、$G$ が相異なる 2 点の組 $(x,y)$（$x\ne y$）の全体に推移的に作用すること（2 重可移）は同値である。

$(X\times X)^g=X^g\times X^g$ なので、前半は thm-bl-main を $X\times X$ に当てたものである。対角 $\Delta:=\{(x,x)\mid x\in X\}$ と補集合 $(X\times X)\setminus\Delta$ はどちらも $G$ で保たれる。推移的なら $\Delta$ は 1 つの軌道であり、$\lvert X\rvert\ge2$ なら補集合は空でないので少なくとも 1 つの軌道を含む。よって右辺は $2$ 以上で、$2$ であることは補集合が 1 つの軌道であること、すなわち 2 重可移であることと同値である。$\square$

置換の不動点の個数の平均

$n\ge2$ とし、対称群 $S_n$ を $\{1,\dots,n\}$ に自然に作用させる。この作用は 2 重可移なので、thm-bl-main と prop-bl-pairs により、$n$ 文字の置換の不動点の個数を $F(\sigma)$ とすると
$$ \frac1{n!}\sum_{\sigma\in S_n}F(\sigma)=1,\qquad\frac1{n!}\sum_{\sigma\in S_n}F(\sigma)^2=2 $$
である。置換を等確率で選ぶと、不動点の個数の期待値は $1$、分散は $2-1^2=1$ であり、どちらも $n$ によらない。同じ値は、期待値の線形性と数え上げの記事の例「置換の不動点の個数」で、事象の指示関数の和として別の方法で計算されている。

反例

外す条件	反例	成り立たなくなること
平均をとる元の集合が群である	$X=\{1,2,3\}$ で、集合 $\{e,(1\,2),(2\,3)\}$ について固定点の個数を平均する	平均 $(3+1+1)/3=5/3$ が、この集合が生成する $S_3$ の軌道の個数 $1$ に等しい
作用が自由である	立方体の面の 2 色の塗り分け（全部同じ色の塗り分けはどの回転でも動かない）	割り算 $\lvert X\rvert/\lvert G\rvert=64/24$ が模様の個数 $10$ に等しい（整数でもない）
作用が推移的である	位数 $2$ の群 $\{e,(1\,2)\}$ を $\{1,2,3\}$ に作用させる	すべての点を動かす元が存在する（どの元も $3$ を動かさない）
群が有限である	複素数を成分とする可逆な $2\times2$ 行列の群 $\mathrm{GL}_2(\mathbb{C})$ と、上三角行列の部分群 $B$	$\bigcup_xxBx^{-1}\neq\mathrm{GL}_2(\mathbb{C})$（実際は等号が成り立つ）

1 行目は thm-bl-main、2 行目は ex-bl-cube の後の割り算、3 行目は thm-bl-jordan、4 行目は cor-bl-conjugates の条件を外したものである。1 行目で、平均をとる集合は $S_3$ を生成するが群ではない（$(1\,2)(2\,3)$ を含まない）。平均が整数でないことからも、何かの個数ではないことが分かる。4 行目では、複素行列 $A$ は固有値をもち、その固有ベクトル $v$ を第 1 列、$v$ と 1 次独立なベクトルを第 2 列とする可逆行列 $x$ をとると $x^{-1}Ax$ の $(2,1)$ 成分が $0$ になる。すなわち $A\in xBx^{-1}$ であり、$B$ の共役の和が群全体になる。cor-bl-conjugates の証明は、平均を有限個の和として扱えることに依存している。

補足

名前：この補題は Burnside の名で呼ばれるが、推移的な場合を Cauchy が、一般の場合を Frobenius が証明していて、Cauchy–Frobenius の補題とも呼ばれる（Sta13 p. 105）。Burnside の名は、彼の群論の本に載ったことによる（KT17 §15.3 の脚注, p. 297）。
証明の型：prf-bl-main は、組 $(g,x)$ を 2 通りに数える二重数え上げである。同じ数え方で、Pólyaの数え上げ定理の記事の補題「重みつきの Burnside の補題」が得られる。
表現論との関係：rem-bl-linear の写像 $P$ は、群の元の平均をとって不変なベクトルへ射影する写像で、群の表現の理論で繰り返し使われる。prop-bl-pairs の 2 重可移性の条件は、推移的な作用の複素数体上の置換表現から自明な表現を除いた部分が既約になる条件でもある（指標(表現論) の記事の命題「軌道の個数と 2 重可移性」）。