バーンサイドの補題

バーンサイドの補題の理解にかなり苦しんだので出来るだけ群論の基礎的な理解だけで分かるような備忘録を残す。

バーンサイドの補題：群$ Gとある集合$ Xに対して、ある演算$ f: G \times X = Xが存在して以下を満たすとする。

・$ Gの単位元を$ 1_Gと置くと、$ Xの要素$ xに対して$ f(1_G,x) = xである。

・$ Gの要素$ g,hと$ Xの要素$ xに対して$ f(g,f(h,x)) = f(gh,x)を満たす。

具体例を上げる。群$ Gを置換$ (1,2,3),(2,1,3)とその合成によって定義される群とし、$ Xを全ての要素が$ 0,1のいずれかの長さ$ 3の数列全てからなる集合とする。そして、$ f(g,x) = (x_{g_1},x_{g_2},x_{g_3})と定義しよう。$ 1_G = (1,2,3)であり、$ f(1_G,x) = xであること。また、$ f(g,f(h,x)) = f(gh,x)であることが確認できる。

$ Xの$ 2個の要素$ x,yを、$ f(g,x)=yを満たす$ gが存在するとき、またその時に限り同一視するとする。$ f(g^{-1},f(g,x)) = f(g^{-1},y)であり、左辺が$ xに等しいことからこの関係は交換しても成り立つ。このときの$ Xを$ X/Gと置く。また、$ Gの要素$ gに対して$ f(g,x)=xを満たす$ xの集合を$ X^gと

・$ |X/G| = \frac{1}{|G|}\sum_{g \in G}|X^g|

先程の具体例だと、例えば$ (0,1,0)と$ (1,0,0)は$ f((2,1,3),(0,1,0))=(1,0,0)であるため同一視される。$ |X/G|=6,|G|=2であることが確認できる。また、$ X^{(1,2,3)}は$ Xの要素全て、$ X^{(2,1,3)}は$ (0,0,0),(0,0,0),(1,1$ ,1),(1,1,1)であることが分かる。実際、$ 6 = \frac{8 + 4}{2}が成り立っている。

この定理の嬉しさは、$ Gを何かしらの置換の集合としたとき、その置換によって同じものを同じとみなして数え上げを行うことが出来る点にある。

例えば、https://atcoder.jp/contests/abc198/tasks/abc198_f を考える。ここで、$ Gを立方体を回転させる方法とそのマージによって定義される群、$ Xを立方体に正整数を書き込む方法のうち書かれた正整数の総和が$ Sになるもの全体の集合(ここでは回転での同一視を行わない)としよう。$ Gは立方体の$ 4本の対角線を考えるとこれらの入れ替えと捉えることが出来る。つまり長さ$ 4の置換全てを要素と持つ群となる。回転として同一視できるものは多く、$ Gの要素として見るべきは本質的には$ (1,2,3,4),(2,1,3,4),(2,1,4,3),(3,1,2,4),(4,1,2,3)の$ 5通りである。よってこれらの場合について答えを求めればよい。例えば$ (2,1,3,4)の場合は上下にひっくり返す(地面に置いた状態から右に倒すを$ 2回行った状態)を表している。つまり、$ 2x + 2y + 2z = Sの正整数解の個数を求めればよい。これは$ \frac{x^6}{(1-x^2)^3}の$ x^Sの係数である。

証明をする。予め用語を定義しておく。$ Xの要素$ xに対して$ f(g,x)=yを満たす$ gの集合を$ \mathrm{Stab}(x)と置く。また、同様に$ f(g,x)=yを満たす$ gが存在するような$ yの集合を$ \mathrm{Orb}(x)と置く。ここで、$ \mathrm{Orb}(x)の種類は$ |X/G|に等しくなる。

$ \begin{aligned} \frac{1}{|G|}\sum_{g \in G}|X^g| &= \frac{1}{|G|} \sum_{g \in G} |\{ x \in X : gx = x\}| \\ &= \frac{1}{|G|} \sum_{x \in G} |\{ x \in X : gx = x\}| \\ &= \frac{1}{|G|}\sum_{x \in X} |\mathrm{Stab(x)}|　\\ &= \frac{1}{|G|}\sum_{x \in X} \frac{|G|}{|\mathrm{Orb(x)}|} \\ &= \sum_{x \in X} \frac{1}{|\mathrm{Orb(x)}|} \\ &= \sum_{\mathrm{Orb}(x)} \sum_{y \in \mathrm{Orb}(x)} \frac{1}{\mathrm{Orb(y)}} \\ &= \sum_{\mathrm{Orb}(x)} 1 \\ &= |X/G| \end{aligned}

3 行目から 4 行目の間で $ |\mathrm{Stab(x)}| \times |\mathrm{Orb(x)}| = |G|を用いた。これは Orbit-Stabilizer Theorem と呼ばれる定理である。証明をする。$ \mathrm{Stab(x)}の要素の集合を$ P、$ \mathrm{Orb(x)}に含まれる$ yに対する$ f(g,x)=yを満たす代表 1 個の$ gの集合を$ Qをする。$ P,Qの要素$ p,qを用いて$ pqと表せない$ Gの要素がないことと、$ P,Qの要素$ p_1,p_2,q_1,q_2に対して$ p_1 \neq p_2 \lor q_1 \neq q_2 \to p_1q_1 \neq p_2q_2が示せればよい。

ここで、$ f(g,x) = yならば$ f(g^{-1},y) = xを示しておく。

$ f(g,x) = f(g,y)ならば$ f(g^{-1},f(g,x)) = f(g^{-1},f(g,y))より$ x=yである。

$ f(g,x) = y \iff f(g^{-1},f(g,x)) = f(g^{-1},y) \iff x = f(g^{-1},y)

よって示された。

前者については、もしそのような$ gが取れたとき、$ f(g,x)=yに対する代表となる$ Gの要素が$ Qに含まれているはずである。これを$ g'とする。ここで、$ f(gg'^{-1},x)= xが成り立つ。(証明：$ xを$ gで置換すると$ yになり、$ yを$ g'^{-1}で置換すると$ xになるため)

よって、$ Pに$ gg'^{-1}が含まれているはずである。すると、$ gg'^{-1} \times g' = gより矛盾する。

後者については、$ q_1 = q_2ならば$ p_1q_1 = p_2q_2とすると$ p_1q_1q_1^{-1} = p_2q_2q_1^{-1} \to p_1 = q_1となり矛盾する。

$ q_1 \neq q_2ならば、$ f(p_1q_1,x) \neq f(p_2q_2,x)より$ p_1q_1 \neq p_2q_2である。

よって示すことが出来た。より、バーンサイドの補題が証明出来た。