§E7.11Burnside の補題

証明. 逆写像を用いる理由は、左作用の積の順序と写像の合成の順序を一致させるためである。実際、$\rho(gh)=\rho(g)\circ\rho(h)$であるから、

また$e\cdot f=f$である。したがって、上の式は左作用を定める。▨

証明. 塗り分け$f_2$が$f_1$に対称変換$g$を施して得られることは、定義により$f_2=g\cdot f_1$と表される。等式$f_2=g\cdot f_1$がある$g\in G$について成り立つことは、$f_2\in G\cdot f_1$と同値である。▨

証明.§E7.10 定理 3.4 (軌道安定化群定理)により、$G\cdot x$と左剰余類集合$G/G_x$の間に全単射がある。 Lagrange の定理を用いると

である。▨

証明.$\sigma\cdot f=f$であることは、

が成り立つことと同値である。この等式を繰り返し用いると、$f$は各巡回軌道上で一定である。逆に、各巡回軌道上で一定な塗り分けは$\sigma$によって固定される。各巡回軌道には$k$通りの色を独立に選ぶことができるから、不動点数は$k^{c(\sigma)}$である。▨

証明. 組の集合

を考える。第一成分$g$を先に固定して数えると、

である。

第二成分$x$を先に固定して数えると、

である。軌道$\mathcal O\subseteq X$を一つ固定する。$y=h\cdot x$ならば

である。実際、$g\cdot y=y$と$(h^{-1}gh)\cdot x=x$は同値である。したがって、安定化群の位数は軌道上で一定である。$x\in\mathcal O$を一つ取ると、軌道安定化群定理により

である。したがって、すべての軌道について和を取ると

となる。二つの計数結果を等置し、$|G|$で割れば主張を得る。▨

証明.定理 3.1 (Burnside の補題)を$X=C^V$に適用し、命題 2.2を用いればよい。▨

証明.$d=\gcd(n,j)$と置き、

と置く。$m=n$は$n\mid nj$を満たすから、$A$は空でない。$A$の最小元を$t$とする。

第一に、$t\leq n/d$を示す。$d$は$n$と$j$の公約数であるから、$n/d$は正の整数であり、$j/d$は整数である。等式$(n/d)j=n(j/d)$から$n\mid(n/d)j$が従うので、$n/d\in A$である。$t$の最小性により$t\leq n/d$である。

第二に、$t\mid n$を示す。整数の除法によって$n=qt+s$、$0\leq s<t$と書く。$n\mid nj$と$n\mid tj$から

が従う。$s>0$ならば$s\in A$となり、$t$の最小性に反する。したがって$s=0$であり、$t$は$n$を割り切る。

第三に、$t\geq n/d$を示す。$u=n/t$と置くと、$u$は正の整数である。$n\mid tj$は$tu\mid tj$と書き直すことができ、$t>0$であるから$u\mid j$である。また$u\mid n$である。したがって$u$は$n$と$j$の公約数であり、$d$が最大公約数であることから$u\leq d$である。ゆえに$t=n/u\geq n/d$である。

第一と第三の不等式から$t=n/d$を得る。▨

証明.$t=n/\gcd(n,j)$と置く。整数$m$に対し、$(r^j)^m$は$a\in\mathbb Z/n\mathbb Z$を$a+mj$へ写す。したがって、次の三つの条件は同値である。

1. ある$a\in\mathbb Z/n\mathbb Z$が存在して$(r^j)^m(a)=a$が成り立つ。
2. $n\mid mj$が成り立つ。
3. すべての$a\in\mathbb Z/n\mathbb Z$について$(r^j)^m(a)=a$が成り立つ。すなわち$(r^j)^m$は恒等写像である。

実際、$\mathbb Z/n\mathbb Z$において$a+mj=a$が成り立つことは$n\mid mj$と同値であり、条件$n\mid mj$は$a$に依存しない。

第一に、$\left|\langle r^j\rangle\right|=t$を示す。補題 4.1により$n\mid tj$であるから、上の同値によって$(r^j)^t$は恒等写像である。整数$m$を$m=qt+s$、$0\leq s<t$と書くと$(r^j)^m=(r^j)^s$であるから、

である。$0\leq s'<s<t$について$(r^j)^s=(r^j)^{s'}$が成り立つと仮定すると、$(r^j)^{s-s'}$は恒等写像であり、$n\mid(s-s')j$かつ$0<s-s'<t$となる。これは補題 4.1が与える最小性に反する。したがって上の$t$個の元は相異なり、$\left|\langle r^j\rangle\right|=t$である。

第二に、各$a\in\mathbb Z/n\mathbb Z$の安定化群が単位元だけからなることを示す。$\langle r^j\rangle$の元$(r^j)^m$が$a$を固定するならば、上の同値によって$(r^j)^m$は恒等写像である。したがって$a$の安定化群は単位元だけからなる。定理 1.8により、$\langle r^j\rangle$の作用による$a$の軌道の要素数は

である。$a$は任意に取ったから、$r^j$の巡回軌道はいずれも$t$個の頂点からなる。▨

証明.$t=n/\gcd(n,j)$と置く。補題 4.2により、$r^j$の巡回軌道はいずれもちょうど$t$個の頂点からなる。§E7.10 命題 3.2により、巡回軌道の全体は$\mathbb Z/n\mathbb Z$を互いに素な部分集合へ分割する。したがって§D2.2 定理 2.1により

であり、

である。▨

証明. 回転群$C_n=\langle r\rangle$に定理 3.2 (塗り分けに対する Burnside の補題)を適用する。命題 4.4により、$r^j$の不動点数は$k^{\gcd(n,j)}$である。この不動点数を Burnside の補題の式へ代入すると、第一の等式を得る。

第二の等式を示す。$d$を$n$の正の約数とし、$e=n/d$と置く。$0\leq j<n$を満たす整数$j$について、

が成り立つことを示す。

はじめに、$j$が$j=ea$、$0\leq a<d$の形に書けている場合を扱う。正の整数$m$に対し、$n\mid mj$は$ed\mid mea$と書き直すことができ、$e>0$であるから、この条件は$d\mid ma$と同値である。補題 4.1により、$n\mid mj$を満たす最小の正の整数は$n/\gcd(n,j)$であり、$d\mid ma$を満たす最小の正の整数は$d/\gcd(d,a)$である。二つの条件が同値であることから

を得る。したがって、$\gcd(n,j)=e$と$\gcd(a,d)=1$とは同値である。次に$\gcd(n,j)=e$とすると、$e$は$j$を割り切るから$j=ea$と書くことができ、$0\leq j<n=ed$から$0\leq a<d$である。以上により上の同値が成り立つ。

$1$以上$d$以下で$d$と互いに素な整数の個数は$\varphi(d)$である。$d\geq2$の場合、$0\leq a<d$で$d$と互いに素な整数$a$の個数はこれに等しく、$d=1$の場合はどちらの個数も$1$である。したがって、$\gcd(n,j)=n/d$を満たす$j$（$0\leq j<n$）はちょうど$\varphi(d)$個あり、命題 4.4により、そのような回転$r^j$の巡回軌道数は$n/d$である。$\gcd(n,j)$は$n$の正の約数であるから、$d=n/\gcd(n,j)$もまた$n$の正の約数であり、各$j$（$0\leq j<n$）はこの$d$に対してちょうど一度数えられる。したがって$d$を$n$の正の約数全体にわたって動かせば、

を得る。▨

証明. 回転による不動点数の和は定理 4.5の証明から

である。鏡映による不動点数の和を求める。

$n$が奇数ならば、各鏡映軸は一つの頂点とその対辺の中点を通る。この鏡映は一つの頂点を固定し、残りの$n-1$個の頂点を$(n-1)/2$個の二点軌道に分ける。したがって巡回軌道数は$(n+1)/2$であり、一つの鏡映の不動塗り分け数は$k^{(n+1)/2}$である。鏡映は$n$個あるから、

である。

$n$が偶数ならば、鏡映は二種類ある。向かい合う二頂点を通る軸に関する鏡映は$n/2$個あり、二頂点を固定して残りを二点ずつ交換する。巡回軌道数は

である。向かい合う二辺の中点を通る軸に関する鏡映も$n/2$個あり、頂点を固定せず、頂点を$n/2$個の二点軌道に分ける。したがって、鏡映による不動点数の和は

である。最後に、位数$2n$の$D_{2n}$に Burnside の補題を適用すれば主張を得る。▨