バーンサイドの補題

バーンサイドの補題は、バーンサイドの数え上げ定理、コーシー・フロベニウスの補題、あるいは軌道数え上げ定理とも呼ばれ、数学的対象を数えるときに対称性を考慮するのに役立つことが多い群論の結果である。これはオーギュスタン・ルイ・コーシーとフェルディナント・ゲオルク・フロベニウスによって発見され、ウィリアム・バーンサイドが引用して有名になった。^[1]この結果は、いくつかの対象に作用する対称群の軌道を列挙するものである。つまり、対称な対象を同じものとして数え、異なる対象を対称同値関係まで数えるか、標準形にある対象だけを数えるかである。たとえば、ある種類の有機化合物の可能性があるものを記述する場合、空間的な回転対称性まで考慮する。つまり、特定の分子の異なる回転図は化学的には同一である。(ただし、鏡映しでは異なる化合物になる可能性がある。)

形式的には、G を集合Xに作用する有限 群とする。 Gの各gに対して、X ^{g は}gによって固定される（gによって左不変である） Xの要素の集合を表すものとする。つまり、X ^g = { x ∈ X | g . x = x } である。バーンサイドの補題は、軌道の数について次の式を主張し、| X / G | と表記する。^[2]

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

したがって、軌道の数（自然数または+∞ ）は、 Gの元によって固定された点の平均数に等しくなります。無限群G の場合、依然として一対一が存在します。

$${\displaystyle G\times X/G\ \longleftrightarrow \ \coprod _{g\in G}X^{g}.}$$

長さ 3 のビット文字列は 8 種類ありますが、文字列の端を結び付けると、長さ 3 の 2 色のネックレスが4 つだけでき、標準形式は 000、001、011、111 になります。他の文字列 100 と 010 は回転すると 001 に相当し、110 と 101 は 011 に相当します。つまり、回転の等価性により、文字列のセットXが 4 つの軌道に分割されます。

${\displaystyle X=\{{\texttt {000}}\}\cup \{{\texttt {001}},{\texttt {010}},{\texttt {100}}\}\cup \{{\texttt {011}},{\texttt {101}},{\texttt {110}}\}\cup \{{\texttt {111}}\}.}$

バーンサイドの公式では、回転数（ヌル回転を含めて 3）と、各回転で変更されないビット文字列の数を使用します。8 ビット ベクトルはすべてヌル回転では変更されず、2 つ（000 と 111）は他の 2 つの回転では変更されません。したがって、軌道の数は次のようになります。

$${\displaystyle 4={\frac {1}{3}}(8+2+2).}$$

長さ 4 の場合、16 個のビット文字列、4 種類の回転、ヌル回転では 16 個の文字列すべてが変更されません。1 回転と 3 回転ではそれぞれ 2 つの文字列 (0000 と 1111) が変更されません。2 回転では 4 つのビット文字列 (0000、0101、1010、1111) が変更されません。したがって、異なるネックレスの数は次のようになります。これは、標準形式 0000、0001、0011、0101、0111、1111 で表されます。 ${\displaystyle 6={\tfrac {1}{4}}(16+2+4+2)}$

nビットおよびk色の一般的なケースは、ネックレス多項式によって与えられます。

バーンサイドの補題は、3 つの色を使用して、立方体の面の回転方向に異なる色の数を計算できます。

X を、固定された立方体に適用できる3 ⁶通りの可能な面の色の組み合わせの集合とし、立方体の回転群G を、色の面を移動することによってXに作用させるとします。Xの 2 つの色は、一方が他方の回転であるとき、まさに同じ軌道に属します。回転によって異なる色は群軌道に対応し、 Gの 24 個の要素の固定集合のサイズを数えることで見つけることができます。色は各回転で変更されません。

• 恒等元は36^色すべてを固定する
• 6回の90度回転でそれぞれ3^つの色彩が固定される
• 3回の180度顔回転でそれぞれ3 ⁴色を固定
• 8つの120度頂点回転はそれぞれ3 ²色を固定する
• 6 回の 180 度エッジ回転で、それぞれ 3 つのカラーリングが固定され^ます。

詳しい検査については、こちらをご覧ください 。

平均的な固定セットのサイズは次のようになります。

${\displaystyle |X/G|={\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色の立方体の面の回転方向に異なる色の数は次のとおりです。

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

バーンサイドの補題の証明では、最初のステップは、群元g  ∈  Gの合計を、元の集合x  ∈  Xの合計として再表現することです。

${\displaystyle \sum _{g\in G}|X^{g}|=\#\{(g,x)\in G\times X\mid g\cdot x=x\}=\sum _{x\in X}|G_{x}|.}$

ここで、X ^g  = { x  ∈  X  |  gx  =  x } はg  ∈  Gによって固定されたXの点の集合であり、G _x  = { g  ∈  G  |  gx  =  x } はG の安定化部分群、つまり点x  ∈  Xを固定する対称性です。

軌道安定定理は、各x  ∈  Xに対して、軌道G·x  = { g·x  |  g  ∈  G } と左剰余類の集合G/G _xの間に自然な一対一関係が存在することを述べています。 ラグランジュの定理は以下を意味します。

${\displaystyle |G\cdot x|=[G\,:\,G_{x}]=|G|/|G_{x}|.}$

したがって、合計は次のように書き直すことができます。

${\displaystyle \sum _{x\in X}|G_{x}|=\sum _{x\in X}{\frac {|G|}{|G\cdot x|}}=|G|\sum _{x\in X}{\frac {1}{|G\cdot x|}}.}$

X をX/G の軌道の非結合和として書きます。

${\displaystyle |G|\,\sum _{x\in X}{\frac {1}{|G\cdot x|}}\ =\ |G|\!\sum _{A\in X/G}\,\sum _{x\in A}{\frac {1}{|A|}}\ =\ |G|\!\sum _{A\in X/G}1\ =\ |G|\,|X/G|.}$

すべてをまとめると、望ましい結果が得られます。

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

これは共役類方程式の証明に似ており、 Gの自身への共役作用、すなわちX = Gおよびg . x = gxg ⁻¹を考慮するため、xの安定化子は中心化子、すなわち G _x = Z _G ( x ) になります。

バーンサイドの補題は、異なるオブジェクトを数えますが、構築はしません。一般に、同型排除による組み合わせ生成では、オブジェクトx上のgの対称性が考慮されます。しかし、gx = xを確認する代わりに、gx がまだ生成されていないことを確認します。これを実現する1つの方法は、各同値類の辞書式最小のメンバーをクラスの標準形として使用して、gx が辞書式でxより小さくないことをチェックすることです。 ^[3]このような手法で生成されたオブジェクトを数えると、バーンサイドの補題が正しく適用されたことを確認できます。

ウィリアム・バーンサイドは1897年の有限群に関する著書でこの補題を述べて証明し、これをフロベニウス1887に帰した。しかしフロベニウスより以前、 1845年にコーシーがこの公式を知っていました。そのため、この補題はバーンサイドの補題ではない補題と呼ばれることもあります。^{[4]科学的発見に誤った名前を付けることは}スティグラーの名詞法則と呼ばれています。

• ポリア列挙定理
• サイクル指数

• バーンサイド、ウィリアム (1897)。有限順序群の理論。ケンブリッジ大学出版局–プロジェクト・グーテンベルク経由。Archive.orgでも入手可能です。(これは第 1 版です。第 2 版の序文には、表現理論の有用性に関するバーンサイドの有名な一転が含まれています。)
• Frobenius、Ferdinand Georg (1887)、「Ueber die Congruenz nach einem aus zwei endlichen Gruppen gebildeten Doppelmodul」、Crelle's Journal、101 (4): 273–299、doi :10.3931/e-rara-18804。
• Cheng, Yuanyou (1986)。「Burnside の補題の推移群の乗算への一般化」。湖北工科大学ジャーナル。ISSN 1003-4684  。。
• ロトマン、ジョセフ（1995）、群論入門、シュプリンガー・フェアラーク、ISBN 0-387-94285-8。