§E13.4Pólya の数え上げ

証明.$g$の巡回軌道は$\langle\rho(g)\rangle$の$X$への作用の軌道であるから、§E7.10 命題 3.2により互いに素であり、その合併は$X$に等しい。各巡回軌道の大きさは$1$以上$n$以下であるから、大きさは$1,\dots,n$のいずれかである。

巡回軌道の全体を大きさによって分類すると、大きさ$j$の類の要素数は定義 1.1により$c_j(g)$である。加法原理（§D2.2 定理 2.1）を巡回軌道の全体へ適用すると、巡回軌道の総数は$\sum_{j=1}^{n}c_j(g)$であり、これは$c(\rho(g))$にほかならない。

また、加法原理を$X$の分割へ適用すると$n=|X|=\sum_{B}|B|$である。ここで$B$は巡回軌道の全体を走る。この和を大きさによって分類すると、大きさ$j$の巡回軌道は$c_j(g)$個あり、それぞれが$j$を寄与するので$\sum_{B}|B|=\sum_{j=1}^{n}j\,c_j(g)$である。▨

証明.$g\cdot f=f$は、すべての$x\in X$について$f(\rho(g)^{-1}(x))=f(x)$が成り立つことを意味する。$\rho(g)$は全単射であるから、$x$を$\rho(g)(x)$で置き換えると、この条件はすべての$x$について$f(x)=f(\rho(g)(x))$が成り立つことと同値である。

この条件が成り立つとする。整数$m\ge0$についての帰納法により、すべての$x$と$m$について$f(\rho(g)^{m}(x))=f(x)$である。$x$の巡回軌道は$\{\rho(g)^{m}(x):m\in\mathbb Z\}$であり、$\rho(g)$の位数を$t$とすると$\rho(g)^{-1}=\rho(g)^{t-1}$であるから、この集合は$\{\rho(g)^{m}(x):m\ge0\}$に等しい。ゆえに$f$は$x$の巡回軌道の上で定数である。

逆に$f$が各巡回軌道の上で定数であるとする。$x$と$\rho(g)(x)$は同じ巡回軌道に属するので$f(\rho(g)(x))=f(x)$である。▨

証明.$g\cdot f=f\circ\rho(g)^{-1}$であるから

である。$\rho(g)^{-1}$は$X$から$X$への全単射であるから、$y=\rho(g)^{-1}(x)$と置くと、$x$が$X$を走るとき$y$も$X$を走る。$R$は可換環であるから積の順序を入れ替えてよく、右辺は$\prod_{y\in X}w(f(y))=W(f)$に等しい。

軌道$O$の二つの元は§E7.10 命題 3.2により$f_2=g\cdot f_1$の形で結ばれるので、上の等式から$W$は$O$の上で一定である。▨

証明.$Y$は有限集合であるから、$W$の値域$V=W(Y)\subseteq R$は有限集合である。$v\in V$に対し$Y_v=\{y\in Y:W(y)=v\}$と置く。$W$は各軌道の上で一定であるから、$y\in Y_v$ならば$g\cdot y\in Y_v$であり、$G$の作用は$Y_v$へ制限されて$Y_v$への左作用を定める。

$Y_v$たちは$Y$を互いに素に分割し、各軌道はただ一つの$Y_v$に含まれる。ゆえに$Y$の軌道の全体は、$Y_v$の軌道の全体を$v\in V$にわたって集めたものである。したがって

である。§E7.11 定理 3.1を$G$の$Y_v$への作用へ適用すると

であるから

となる。右辺は有限和であるから和の順序を入れ替えてよい。$g$を固定すると、$\operatorname{Fix}_{Y}(g)$は$\operatorname{Fix}_{Y_v}(g)$（$v\in V$）の互いに素な合併であり、$\operatorname{Fix}_{Y_v}(g)$の各元$y$は$W(y)=v$を満たす。ゆえに

であり、主張を得る。▨

証明.$C^{X}$は有限集合であり、$G$は$C^{X}$へ左から作用する（§E7.11 命題 1.5）。また命題 2.3により$W\colon C^{X}\to R$は各軌道の上で一定である。ゆえに命題 3.1を$Y=C^{X}$として適用することができ、示すべきことは各$g\in G$について

が成り立つことである。

$g$を固定し、$g$の巡回軌道を$B_1,\dots,B_r$（$r=c(\rho(g))$）とする。これらは$X$の分割である（§E7.10 命題 3.2）。補題 2.1により、$f\in\operatorname{Fix}_{C^{X}}(g)$であることと、$f$が各$B_i$の上で定数であることは同値である。$f$に対し$\gamma_i\in C$を$B_i$上の共通の値と定めると、対応$f\mapsto(\gamma_1,\dots,\gamma_r)$は$\operatorname{Fix}_{C^{X}}(g)$から$C^{r}$への全単射である。実際、逆向きの対応は、与えられた$(\gamma_1,\dots,\gamma_r)$に対し$x\in B_i$で$f(x)=\gamma_i$と定めるものであり、$B_i$が$X$の分割であるからこれは$X$上の写像を一意に定める。

$f$の重みを計算する。$X=\bigsqcup_{i=1}^{r}B_i$であり$R$は可換であるから

である。したがって

となる。最後の等号は、可換環における有限個の因子への分配法則である。実際、右辺の積を展開すると、各因子から色を一つずつ選ぶ選び方$(\gamma_1,\dots,\gamma_r)$ごとに項$\prod_i w(\gamma_i)^{|B_i|}$が現れ、その総和になる。

最後に、$i$を$|B_i|$の値で分類する。$|B_i|=j$となる$i$は定義 1.1により$c_j(g)$個であるから

である。$g$について$1/|G|$を付けて足し合わせると、定義 1.3の定義により右辺は$Z_G$へ$s_j=\sum_{c}w(c)^{j}$を代入した値である。▨

証明.$R=\mathbb Q$とし、すべての$c\in C$について$w(c)=1$と定める。このとき$W(f)=1$であるから、定理 3.2の左辺は軌道の個数に等しい。また$\sum_{c\in C}w(c)^{j}=k$であるから右辺は$Z_G(k,\dots,k)$である。最後に、命題 1.2により$\prod_{j}k^{c_j(g)}=k^{\sum_j c_j(g)}=k^{c(\rho(g))}$である。これは§E7.11 命題 2.2が与える不動点数と一致する。▨

証明.$\pi_j$は$\pi_{-j}$を逆写像にもつので全単射であり、$\tau_b$は$\tau_b\circ\tau_b=\mathrm{id}$を満たすので全単射である。合成を計算すると

である。たとえば第三の式は$(\tau_b\circ\pi_j)(a)=b-(a+j)=(b-j)-a$による。ゆえに$C_n$と$D_{2n}$はいずれも合成について閉じ、恒等写像$\pi_0$を含み、$\pi_j^{-1}=\pi_{-j}$、$\tau_b^{-1}=\tau_b$であるから部分群である。

位数を数える。$j\ne j'$ならば$\pi_j(0)=j\ne j'=\pi_{j'}(0)$であるから、$\pi_j$たちは相異なる$n$個の元である。同様に$\tau_b(0)=b$により$\tau_b$たちも相異なる。回転と鏡映が一致しないことを示す。$\pi_j=\tau_b$とすると、$a=0$から$j=b$を得、$a=1$から$1+j=b-1$を得るので$1+j=j-1$、すなわち$2\equiv0\pmod n$となる。$n\ge3$に反する。ゆえに$|D_{2n}|=2n$である。▨

証明.$H=\langle\pi_j\rangle$と置く。$H$の$X$への作用の安定化群を調べる。$\pi_j^{m}(a)=a+mj$であるから、$\pi_j^{m}$が$a$を固定することと$mj\equiv0\pmod n$であることは同値であり、この条件は$a$に依存しない。ゆえに$\pi_j^{m}$が或る点を固定すればすべての点を固定し、$\pi_j^{m}=\mathrm{id}$である。したがって各$a$の安定化群$H_a$は単位元だけからなる。§E7.10 定理 3.4により、すべての軌道の大きさは$|H|$に等しい。

次に$|H|$を求める。以下、$j$は代表として取った整数$0\le j\le n-1$を表す。前段で見たとおり$\pi_j^{m}=\mathrm{id}$であることと$n\mid mj$であることは同値であり、$m=n$はこれを満たすので、$n\mid mj$を満たす正整数が存在する。その最小のものを$t$と置く。

このとき$|H|=t$である。実際、任意の整数$m$を$m=qt+s$（$0\le s<t$）と書くと$\pi_j^{m}=(\pi_j^{t})^{q}\circ\pi_j^{s}=\pi_j^{s}$であるから$H=\{\pi_j^{0},\pi_j^{1},\dots,\pi_j^{t-1}\}$である。また$0\le s'<s\le t-1$について$\pi_j^{s}=\pi_j^{s'}$とすると$\pi_j^{s-s'}=\mathrm{id}$となり、$0<s-s'<t$が$t$の最小性に反する。ゆえにこれら$t$個の元は相異なる。

$t\le n/d$である。実際、$d$は$n$と$j$の公約数であるから（$j=0$のときは$d=n$という約束により$d\mid n$かつ$d\mid j$が成り立つ）、$n/d$は正の整数であり$j/d$は非負整数である。$(n/d)\,j=n\,(j/d)$であるから$n\mid(n/d)\,j$が成り立ち、$t$の最小性により$t\le n/d$を得る。

$t\mid n$である。実際、$n=qt+s$（$q$は整数、$0\le s<t$）と書くと、$n\mid nj$と$n\mid tj$から$n\mid(n-qt)\,j=sj$が従う。$s>0$とすると$t$の最小性に反するので$s=0$であり、$t$は$n$を割り切る。

そこで$u=n/t$と置く。$u$は正整数であり、$n\mid tj$は$tu\mid tj$と書き直すことができるので、$t>0$より$u\mid j$である。また$u\mid n$である。ゆえに$u$は$n$と$j$の正の公約数であり、$u\le d$である（$j=0$のときは、$d=n$という約束と$u\mid n$により$u\le n=d$が成り立つ）。したがって$t=n/u\ge n/d$である。

以上の二つの不等式から$t=n/d$、すなわち$|H|=n/d$である。ゆえに各巡回軌道の大きさは$n/d$である。巡回軌道は$X$を分割するので、加法原理（§D2.2 定理 2.1）により（軌道の個数）$\times\,(n/d)=n$であり、軌道の個数は$d$である。

ゆえに$\pi_j$の巡回型は$c_{n/d}(\pi_j)=d$、他の$c_i(\pi_j)=0$であり、定義 1.3の定義から主張の等式を得る。▨

証明.$\tau_b\circ\tau_b=\mathrm{id}$であるから$\langle\tau_b\rangle=\{\mathrm{id},\tau_b\}$であり、$a$の巡回軌道は$\{a,b-a\}$である。この軌道の大きさは、$a=b-a$すなわち$2a=b$のとき$1$、そうでないとき$2$である。

(1)を示す。$n$が奇数のとき、$2\cdot\frac{n+1}{2}=n+1\equiv1\pmod n$であるから$2$は$\mathbb Z/n\mathbb Z$の可逆元であり、その逆元は$(n+1)/2$の剰余類である。ゆえに$2a=b$はただ一つの解$a=\frac{n+1}{2}b$をもつ。不動点は$1$個であり、残る$n-1$個の点は大きさ$2$の軌道へ分かれるので、その軌道は$(n-1)/2$個である。

(2)を示す。$n$が偶数とする。任意の$a$に対し$2a$は偶数の剰余類であるから、$b$が奇数の剰余類ならば$2a=b$は解をもたず、不動点は存在しない。このとき$n$個の点はすべて大きさ$2$の軌道へ分かれるので、その軌道は$n/2$個である。$b$が偶数の剰余類ならば$b=2c$と書くことができ、$a=c$は解である。他の解を求めると、$2a=2c$は$n\mid2(a-c)$と同値であり、$n=2\cdot(n/2)$であるからこれは$(n/2)\mid(a-c)$と同値である。$\mathbb Z/n\mathbb Z$の中でこれを満たす$a$は$c$と$c+n/2$の二つである。不動点は$2$個であり、残る$n-2$個の点は$(n-2)/2$個の大きさ$2$の軌道へ分かれる。▨

証明.命題 4.2により$|D_{2n}|=2n$であり、$D_{2n}$の元は$n$個の回転と$n$個の鏡映である。回転の寄与は命題 4.3の証明で求めた巡回型による。鏡映の寄与は命題 4.4による。$n$が偶数のとき、偶数の剰余類$b$は$n/2$個、奇数の剰余類$b$は$n/2$個であるから、二種類の鏡映がそれぞれ$n/2$個ずつある。定義 1.3の定義に代入すると主張の等式を得る。▨