バーンサイドの補題

ウィキペディア

バーンサイドの補題

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2023/02/20 21:17 UTC 版)

バーンサイドの補題（英: Burnside's lemma）、あるいはバーンサイドの数え上げ補題、コーシー・フロベニウスの補題、軌道の数え上げ補題とは、対称性を考慮して数学的な対象を数え上げるときに有用な群論の結果である。

以下では G は有限群で集合 X に作用しているとする。群 G の各元 g に対して X^g で元 g によって固定されるすべての X の元からなる集合を表す。バーンサイドの補題は軌道の数 |X/G| は次の式で表せることを主張している。

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

彩色された立方体

単位元

3⁶個の元すべてを固定する

面の90度回転（6つ）

3³個の元（回転軸の通る2面と側面の彩色分）を固定する

面の180度回転（3つ）

3⁴個の元（回転軸の通る2面と側面の2対面の彩色分）を固定する

頂点の120度回転（8つ）

3²個の元（回転軸に対して上下の彩色分）を固定する

辺の180度回転（6つ）

3³個の元（回転軸の通る辺に接する面の2組と側面の彩色分）を固定する

よって各元が固定する集合の大きさの平均は次の通り。

${\frac {1}{24}}\left(3^{6}+6\cdot 3^{3}+3\cdot 3^{4}+8\cdot 3^{2}+6\cdot 3^{3}\right)=57$

したがって立方体の面を3色で塗り分ける方法は57通りある。一般に立方体の面を n 色で塗り分ける方法は次の通り。

${\frac {1}{24}}\left(n^{6}+3n^{4}+12n^{3}+8n^{2}\right)$

証明

証明の第一歩は群 G の元 g に関する和を集合 X の元 x に関する和に書き直すことである（二重数え上げ）。

$\sum _{g\in G}\vert X^{g}\vert =\vert \{\,(g,x)\in G\times X\mid gx=x\,\}\vert =\sum _{x\in X}\vert G_{x}\vert$

（ここで X^g = { x ∈ X | gx = x } は群 G の元 g で固定される X のすべての元からなる集合で G_x = { g ∈ G | gx = x } は集合 X の元 x を固定する G のすべての元からなる固定群である。）

軌道・固定群定理により集合 X の各元 x の軌道 Gx = { gx ∈ X | g ∈ G } と固定群 G_x による左剰余類 G/G_x の間には自然な全単射がある。ラグランジュの定理と合わせると次を得る。

$\vert Gx\vert =[G:G_{x}]=\vert G\vert /\vert G_{x}\vert$

したがって最初の等式の右辺にある集合 X の元に関する和を次のように書き換えることができる。

$\sum _{x\in X}\vert G_{x}\vert =\sum _{x\in X}{\frac {\vert G\vert }{\vert Gx\vert }}=\vert G\vert \sum _{x\in X}{\frac {1}{\vert Gx\vert }}$

最後に集合 X は軌道の直和であることに注意すれば直前の X に関する和は各軌道に関する和へ分解できる。

$\sum _{x\in X}{\frac {1}{\vert Gx\vert }}=\sum _{A\in X/G}\sum _{x\in A}{\frac {1}{\vert A\vert }}=\sum _{A\in X/G}1=\vert X/G\vert$

すべてをまとめれば目的の結果を得る。

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

歴史

ウィリアム・バーンサイドは『有限群論』（1897年）でFrobenius (1887)に拠るものとしてこの補題を述べ、証明した。しかしフロベニウス以前にもこの式はコーシーによって1845年には知られていた。実際にはこの補題はよく知られていたのでバーンサイドが単にコーシーへ帰するのを省いたようである。結果としてこの補題はしばしばバーンサイドのでない補題とも呼ばれる。バーンサイドはこの分野において多くの貢献をしているのでこれは一見感じられるほど曖昧ではない。

参考文献

• Burnside, William (1897), Theory of Groups of Finite Order, Cambridge University Press , at Project Gutenberg and here at Archive.org. （これは第一版である。第二版の序文ではバーンサイドの有名な表現論の有用性に関する方針転換が述べられている。）
• Frobenius, Ferdinand Georg (1887), “Ueber die Congruenz nach einem aus zwei endlichen Gruppen gebildeten Doppelmodul”, Crelle CI: 288, doi:10.1515/crll.1887.101.273 .
• Neumann, Peter M. (1979), “A lemma that is not Burnside's”, The Mathematical Scientist 4 (2): 133–141, ISSN 0312-3685, MR 562002, Zbl 0409.20001 .
• Rotman, Joseph (1995), An introduction to the theory of groups, Springer-Verlag, ISBN 0-387-94285-8 .

関連項目

• ポーヤの計数定理

外部リンク

• Weisstein, Eric W. "Cauchy-Frobenius Lemma". MathWorld (英語).
• Neumann, Peter M. (2001), "Burnside Lemma", in Hazewinkel, Michiel (ed.), Encyclopaedia of Mathematics, Springer, ISBN 978-1-55608-010-4。