母関数とはFourier展開である
導入
以下のような問題と解法を見たことはあるでしょうか？
コインを$n$回投げて表が3の倍数回出る確率$p_n$を求めよ.
解答.
$f(x)=(\frac12 x+\frac12)^n$の, $x$の次数が3の倍数であるような項の係数の和が$p_n$なので, $\omega=\frac{-1+\sqrt{-3}}2$を1の原始3乗根として
$$ p_n=\frac{f(1)+f(\omega)+f(\omega^2)}3 $$
${}$
これがいわゆる母関数による解法です. 確率や場合の数の問題で, 事象を選ぶことを多項式をかけることに対応させ, 係数を求める問題に帰着させるという考え方です.
今回は, この方法を代数的に捉え直してみましょう.
${}$
群環
群$G$と環$R$に対して, $G$で添字付けられた基底をもつ自由$R$加群を考え, その元を$\sum_ga_g\, g$とかく. （$g\in G$による基底$e_g$を単に$g$とかき, その係数を$a_g\in R$とした.）
元$\sum_g a_g\,g$と$\sum_g b_g\,g$の積を
$$ \Big(\sum_{g\in G} a_g\,g\Big)\Big(\sum_{g\in G} b_g\,g\Big):=\sum_{g,h\in G}a_gb_h\,gh=\sum_{g\in G}\Big(\sum_{h\in G}a_hb_{gh^{-1}}\Big)g$$
と定めることで環構造が入る. この環を$R[G]$とかき, 群環という. これは$R$代数にもなっている.
群環は, 群の元を変数のように扱った形式和だと思うのがよい. 例えば$g,h\in G$として, $\Z[G]$において
$$ (g+2h)(3g^{-1}+h)= 3e+gh+6hg^{-1}+2h^2$$
のように計算ができる.
${}$
この概念を用いると, 先ほどの問題は次のように言い換えられます.
${}$
表の回数を3で割った余りを$\Z/3\Z$の元で表すと, コインを投げることは$\Z/3\Z$において$[1]$または$[0]$を確率$\frac12$で足すことに相当する
→群環$\C[\Z/3\Z]$での$(\frac12[1]+\frac12[0])^n$の$[0]$の係数が, 表が3の倍数回出る確率$p_n$である.
${}$
群環での計算問題に言い換えることができました. では, 群環の構造を詳しく調べてみましょう.
${}$
中国剰余定理
例1 において「群環は, 群の元を変数と思って...」と言いましたが, 群が可換な場合はまさに多項式とみなすことができます.
$\C[\Z/3\Z]$は, $[0]$を1, $[1]$を$X$, $[2]$を$X^2$に送ることにより
$$ \begin{array}{ccc} \C[\Z/3\Z]&\stackrel{\sim}{\longrightarrow}&\C[X]/(X^3-1)\\ \frac12[1]+\frac12[0] & \longmapsto &\frac12X+\frac12 \end{array}$$
さらに中国剰余定理より環として$\C[X]/(X^3-1)\cong \C^3 $となります.
${}$
$\C$の直積環と同型になることがわかりました. 直積環では$n$乗の計算はとても簡単です！
つまり$ \C[X]/(X^3-1) $において$(\frac12 X+\frac12)^n$の定数項を求めるには,
$$ \begin{array}{rcc} \C[X,Y]/(X^3-1) &\stackrel{f}{\longrightarrow}& \C^3 \\[5pt] \frac12 X+\frac12 & \longmapsto & (a,b,c)\\ & & \downarrow\\ p_n+\boxed{\phantom{t}}X+\boxed{\phantom{t}}Y+\boxed{\phantom{t}}XY & \longleftarrow& (a^n,b^n,c^n) \end{array}$$
のように, 同型$f$で$\frac12X+\frac12$を送り, $n$乗してから引き戻すことによって$p_n$を求められます.
${}$
同型を計算する
では, 同型$f:\C[X]/(X^3-1)\stackrel{\sim}{\longrightarrow}\C^3$を具体的に書き下しましょう.
先ほどの中国剰余定理を丁寧に書くと
$$ \begin{align*} \C[X]/(X^3-1)&\cong \C[X]/(X-1)\times\C[X]/(X-\omega)\times\C[X]/(X-\omega^2)\\[5pt] &\cong \C\times\C\times\C \end{align*}$$
ここで$\C[X]/(X-1)\stackrel{\sim}{\longrightarrow}\C$は, $X-1$で割った余り即ち$1$を代入するという写像なことに注意すれば,
$$ f:P(X)\longmapsto (P(1),P(\omega),P(\omega^2))$$
とわかります.
${}$
従って, $P(X)=\frac12X+\frac12$として, $p_n=\Big(f^{-1}(P(1)^n,P(\omega)^n,P(\omega^2)^n)\text{の定数項}\Big)$ となります.
中国剰余定理の逆写像は一般に綺麗にはかけませんが, 今回は計算してみると$f^{-1}(a,b,c)$の定数項は$\dfrac{a+b+c}3$であることがわかるので, 一番最初の結果と一致することが確かめられます.
${}$
Artin-Wedderburn
実は, 群環の構造を調べるには中国剰余定理ではなく, もっと一般的な以下の定理を用いる方が見通しが良いです.
$G$を有限群, $G$の$\C$係数既約表現の全体を$(\rho,V_\rho)_\rho$とし, $V_\rho$を自然に$\C[G]$加群とみることで$\phi_\rho:\C[G]\to\mathrm{End}\,V_\rho\cong\mathrm{M}_{d_\rho}(\C)$を定める. $\phi_\rho$を並べてできる
$$ \Phi:\ \C[G]\ \stackrel{\sim}{\longrightarrow}\ \prod_\rho \mathrm{M}_{d_\rho}(\C)$$
は, 環の同型である.
上の状況で, $(A_\rho)\in\prod_\rho\mathrm{M}_{d_\rho}(\C)$に対し$\Phi^{-1}((A_\rho))\in\C[G]$の$g$の係数は
$$ \frac{1}{|G|}\sum_\rho d_\rho \Tr(\phi_\rho(g^{-1})A_\rho)$$
${}$
特に$G$が有限Abel群の場合は, 既約表現は全て1次元指標ですから, 次のようになります.
$G$が有限Abel群ならば, その$|G|$個の指標全体を$(\chi_i)_i$として,
$$\begin{array}{rccc}
\rho:&\C[G]&\stackrel{\sim}{\longrightarrow}&\C^{|G|}\\[5pt]
& g & \longmapsto & (\chi_i(g))_i
\end{array}
$$
は環の同型である. 逆写像は
$$ \Phi^{-1}((c_i)_i)=\sum_g a_g\,g,\quad a_g=\frac1{|G|}\sum_i\chi_i(g^{-1})c_i$$
で与えられる.
前半は, 先ほど中国剰余定理を使った結果と同じことを言っています. しかし今度は逆写像が綺麗に表せているところがポイントです.
先ほどの問題に適用する. $G=\Z/3\Z$とすると, 指標は$[1]$を$1,\omega,\omega^2$に送る3つがある.
$\Phi(\frac12[1]+\frac12[0])=(1,\frac{1+\omega}2,\frac{1+\omega^2}2)$であり, これの$n$乗の引き戻しの$[0]$の係数は, 公式より
$$ p_n=\dfrac{1+(\frac{1+\omega}2)^n+(\frac{1+\omega^2}2)^n}{3}$$
である.
${}$
応用
$xy$平面の原点に点$\mathrm{P}$があり, 縦横斜めに隣り合う8つの格子点をランダムに選び移動することを毎秒繰り返す. $n$秒後に$\mathrm{P}$の$x,y$座標が共に奇数である確率$p_n$を求めよ.
解答.
$\mathrm{P}$の$x,y$座標の偶奇を$G=(\Z/2\Z)^2$の元で表すと, この操作は$a=\frac14(1,0)+\frac14(0,1)+\frac12(1,1)\in \C[G]$を掛けることに対応する. $a^n$の$(1,1)$の係数が$p_n$である.
$G$の指標は$(1,0),(0,1)\in G$を$\pm1$に送る4つであるから, $\Phi:\C[G]\stackrel{\sim}{\longrightarrow}\C^4$による$a$の像は$\Phi(a)=(1,-\frac12,-\frac12,0)$である. $\Phi^{-1}(\rho(a)^n)$の$(1,1)$の係数$p_n$は, 公式より
$$ p_n=\frac{1-2(-\frac12)^n}{4}$$
となる.
${}$
Artin-Wedderburnを使うと, 群が非可換な場合にも母関数を考えることができます. 詳しくは 私の過去の記事 の例などを参照してください.
${}$
Fourier変換
ところで, 上の定理2の式にはなぜFourier逆変換という名前がついているのでしょうか？
実は, 群環を$G$上の関数とみて, それを既約表現の和に分解していると捉えると, Fourier展開との類似性が見えてきます. 次のような一般化が存在します.
$G$をcompact位相群, $L^2(G)$をそのHaar測度に関する$L^2$空間とする.
$$ \Psi:\ \bigoplus_\rho \mathrm{End}\,V_\rho\longrightarrow L^2(G)$$
を, $\Psi(E_{ij}^{(\rho)})(g)=\rho(g)_{ij}$を線型に拡張して定める. （ここで$\rho$は$G$のunitary既約表現全体を動き, $V_\rho$は$\rho$の表現空間であり, $V_\rho$の標準基底を一つ取り$E_{ij}^{(\rho)} $を行列単位, $\rho(g)_{ij}$を$\rho(g)$の表現行列の$(i,j)$成分とした. また左辺はHilbert空間としての直和とする. ）
このとき, $L^2(G)$をleft translationにより$G$の表現とみると$\Psi$は表現の同型である. さらに, $d_\rho=\dim V_\rho$として, $\big\{\sqrt{d_\rho}\, \Psi(E_{ij}^{(\rho)})\big\}_{\rho,i,j}$は$L^2(G)$の正規直交基底である.
${}$
$G=S^1$のときが通常のFourier展開に相当します.
まず$S^1$のunitary既約表現は$\theta\mapsto e^{in\theta}$が全てである. 特に全て1次表現なので,
$$ \Psi^{-1}:L^2(S^1)\stackrel{\sim}{\longrightarrow}\bigoplus_n\C=\ell^2(\C)
$$
であり, $\{\theta\mapsto e^{in\theta}\}$が正規直交基底となる. これは通常のFourier展開の理論である.
次に, $G$が有限群のときに, 前述のArtin-WedderburnおよびFourier逆変換公式が導かれることを見ましょう.
$g\mapsto\mathbb{1}_g$（：特性関数）により$\C[G]$と$L^2(G)$を同一視する. Artin-WedderburnとPeter-Weylの2つの写像
$$
\begin{array}{rccc}
\Phi:& \C[G] &{\longrightarrow} & \prod _\rho\mathrm{End}\,V_\rho\\
\Psi^{-1}: & L^2(G) & {\longrightarrow} & \prod _\rho\mathrm{End}\,V_\rho
\end{array}
$$
の関係を調べる. まず$\Phi(g)=(\rho(g))_\rho$である.
次に$\Psi^{-1}(\mathbb{1}_g)=(A_\rho)_\rho$だとすると, $\ds\mathbb{1}_g=\sum_{\rho,i,j}(A_\rho)_{ij}\Psi(E_{ij}^{(\rho)})$となり, $\sqrt{d_\rho}\, \Psi(E_{ij}^{(\rho)})$が正規直交基底であったことから, 内積をとれば係数$(A_\rho)_{ij} $が求められる. 即ち,
$$ \begin{align*}
(A_\rho)_{ij} &=d_\rho\cdot\langle \mathbb{1}_g\,,\Psi(E_{ij}^{(\rho)})\rangle\\[5pt]
&=d_\rho\int_G \mathbb{1}_g(x)\,\overline{ \rho(x)_{ij}}\,dx\\[5pt]
&= \frac{d_\rho}{|G|}\rho(g^{-1})_{ji}
\end{align*}
$$
より, $\Psi^{-1}(g)=(\frac{d_\rho}{|G|}\rho(g^{-1})^T)_\rho$である. ここで最後に$\rho$がunitaryであることを使った.
この2つを見比べると以下の可換図式を得る.
$$
\xymatrix{
{\C[G]} \ar[rr]_{\Phi} \ar[d]_{g\mapsto g^{-1}} & {} & {\prod _\rho\mathrm{End}\,V_\rho} \ar[d]^{\times\frac{d_\rho}{|G|}\,(\bullet)^T}\\
{L^2(G)} \ar[rr]^{\sim}_{\Psi^{-1}} &{}& {\prod _\rho\mathrm{End}\,V_\rho}
}$$
これによりArtin-Wedderburnの$\Phi$が同型だと言えた.
${}$
最後に$\Phi^{-1}((A_\rho)_\rho)$の$g$の係数$a_g$を求めると,
$$ \begin{align*}
a_g&= \Psi\Big(\Big(\frac{d_\rho}{|G|}A_\rho^T\Big)_\rho\Big)(g^{-1})\\[5pt]
&=\frac1{|G|}\sum_{\rho,i,j}d_\rho\cdot (A_\rho)_{ji}\,\rho(g^{-1})_{ij}\\[5pt]
&=\frac1{|G|}\sum_{\rho}d_\rho\Tr(\rho(g^{-1})A_\rho)
\end{align*}$$
Fourier逆変換公式が従う.
${}$
このように $\ds\Psi^{-1}(f)=\Big(d_\rho\int_Gf(g)\rho(g^{-1})^T\,dg\Big)_\rho$であり, $G=S^1$のときこれはFourier展開係数を求める積分で, $G$が有限群のときほとんど$\Phi$だったので, Artin-WedderbunはFourier展開の類似であることが納得できました.
つまり, 母関数とはFourier展開なのです.
${}$
ここまで読んでくださった方, ありがとうございました.
