離散フーリエ変換と中国剰余定理

今日紹介するのは離散フーリエ変換は中国剰余定理としても理解できるというお話です。この見方をすると，合成積が離散フーリエ変換で積に化ける理由がよく分かります。

離散フーリエ変換

を正整数とし， を の原始乗根をします。

長さ の複素数列 に \begin{align}A_p= \sum_{k=0}^{N-1} a_k \cdot \zeta_N^{-kp}\end{align}を対応させるものを離散フーリエ変換と呼び， で表します。

また， を \begin{align}a_p= \frac{1}{N}\sum_{k=0}^{N-1} A_k \cdot \zeta_N^{kp}\end{align}に対応させるものを逆離散フーリエ変換と呼び， で表します。

は線形同型写像で， が逆写像になっていることが知られています。つまり， のとき が成り立ちます。

離散フーリエ変換 - Wikipedia

離散フーリエ変換はフーリエ変換の離散版として，解析的な文脈で語られるのが普通ですが，今日は代数的な視点から見てみようと思います。

多項式環での中国剰余定理

複素数体 上の1変数多項式環 を で生成されるイデアル で割った剰余環を で表すことにします。 における中国剰余定理は次の形になります。

中国剰余定理
が \begin{align}f(T)=f_0(T)\cdots f_{N-1}(T)\end{align}と因数分解できており， はどの２つを取っても互いに素なとき，自然な全射 をまとめた写像\begin{align}\frac{\mathbb{C}[T]}{\langle f(T)\rangle}\to
\prod_{k=0}^{N-1} \frac{\mathbb{C}[T]}{\langle f_k(T)\rangle}\end{align}は -代数としての同型となる。

特に が相異なる複素数で，\begin{align}f(T)=\prod_{k=0}^{N-1} (T-a_k)\end{align}のときを考えると， であり， なので，この場合の中国剰余定理の同型写像は \begin{eqnarray*}\frac{\mathbb{C}[T]}{\langle \prod_{k=0}^{N-1} (T-a_k)\rangle} &\to&\mathbb{C}^N \cong \prod_{k=0}^{N-1} \frac{\mathbb{C}[T]}{\langle T-a_k\rangle}, \\[2mm]
g(T) &\mapsto& (g(a_0),~g(a_2),~\dots,~g(a_{N-1}))\end{eqnarray*}となります。

この同型により，任意の に対し，次数が高々 の多項式 で が成り立つものが唯一存在することが分かります。これを利用したのが最近一部ネットで話題の月の日数を与える多項式です。

togetter.com
tsujimotter.hatenablog.com

離散フーリエ変換と中国剰余定理

離散フーリエ変換の代数的解釈

の場合を考えましょう。 の逆数 も の原始乗根なので\begin{align}T^N-1=\prod_{k=0}^{N-1}(T-\zeta_N^{-k})\end{align}と因数分解できます。よって中国剰余定理より\begin{eqnarray*}\varphi:\frac{\mathbb{C}[T]}{\langle T^N-1\rangle} &\to&\mathbb{C}^N \\[2mm]
g(T) &\mapsto& (g(1),~g(\zeta_N^{-1}),~\dots,~g(\zeta_N^{-p}),\dots,~g(\zeta_N^{-(N-1)}))\end{eqnarray*}は環同型となります。

この定義域である環 は，ベクトル空間としては を基底とする 次元 -ベクトル空間です。この基底を並べたベクトルを とおいて， を の元 \begin{align}\vec{a}\cdot \vec{T}=a_0+a_1T+a_2T^2+\dots a_{N-1}T^{N-1}\end{align}と同一視することができます ( は内積)。

離散フーリエ変換の定義を思い出すと，\begin{align}\varphi(\vec{a}\cdot \vec{T})=\mathcal{F}(\vec{a})\end{align}が成り立つことが分かります。つまり， という同一視を通し，環同型 は離散フーリエ変換 そのものと思うことができます。

逆離散フーリエ変換の代数的解釈

は同型なので逆写像 が存在します。 がどうなるのか見てみましょう。

の標準的な基底を とします。 は 番目の成分が でそれ以外の成分が のベクトルです。

に対し \begin{align}\varphi\left(\frac{1}{N}\sum_{k=0}^{N-1} \zeta_N^{kp} T^k\right)=e_p\end{align}となります。 は -代数の準同型なので に対し \begin{eqnarray*}\varphi^{-1}(\vec{A})&=&\varphi^{-1}\left(\sum_{p=0}^{N-1} A_p e_p\right)=\sum_{p=0}^{N-1} A_p \varphi^{-1}(e_p) =\sum_{p=0}^{N-1}A_p\cdot\frac{1}{N}\sum_{k=0}^{N-1} \zeta_N^{kp} T^k\\
&=&\sum_{k=0}^{N-1}\left( \frac{1}{N}\sum_{\ell=0}^{N-1}A_p \zeta_N^{kp}\right)T^k=\mathcal{F}^{-1}(\vec{A})\cdot \vec{T}\end{eqnarray*}となり， は逆離散フーリエ変換と本質的に同じものであることが分かります。

合成積

さて は単なるベクトル空間としての同型ではなくて環同型です。 と の演算を比較すると，足し算はどちらもベクトルの足し算と同じ構造で似たようなものですが，掛け算の方はかなり違って見えます。

は環の直積なので積の構造は単純です。 の積は成分ごとの積と定義され\begin{align}(A_0,\dots,A_{N-1})(B_0,\dots,B_{N-1})=(A_0B_0,\dots, A_{N-1}B_{N-1})\end{align}となります。

一方で と の での積は\begin{align}f(T)g(T)=\sum_{k=0}^{N-1}\left(\sum_{p+q \equiv k ~\mathrm{mod}~ N} a_pb_q\right)T^k \end{align}となります。

ここで， の添え字を と解釈します。つまり，任意の整数 に対して です (数列 を周期 の繰り返しになるように添え字を 全体に拡張したと解釈してもいいです)。すると，先ほどの積は \begin{align}f(T)g(T)=\sum_{k=0}^{N-1}\left(\sum_{p=0}^{N-1} a_pb_{k-p}\right)T^k \end{align}と書けます。

この係数を並べたベクトルは合成積と呼ばれます。

合成積
， に対し， \begin{align}c_k=\sum_{p=0}^{N-1} a_pb_{k-p}\end{align} を と の合成積と呼び， と書く。

はベクトルの和を加法，合成積を乗法とした可換環になります。一見変わった環のような感じがしますが を考えていることと同じです。

中国剰余定理の同型 を使うと，合成積の離散フーリエ変換がどうなるかすぐ分かります。

合成積の離散フーリエ変換\begin{align}\mathcal{F}(\vec{a}*\vec{b})=\mathcal{F}(\vec{a})\mathcal{F}(\vec{b})\end{align}

ここで は直積環 での積です (つまり成分ごとに積を取る)。以前と同じように で，黒点 は内積の記号とします。

証明
合成積の定義より が で成り立つ。 は環準同型だったので， となる。

だったので，これは を意味している。

証明終

数値的半群環のイデアルの生成元の数

を体とし，正整数で定まる の部分環 ，または の部分環 を数値的半群と呼びます。

MathPower にも出ていた可換環論botこと龍孫江さんの今日の記事で次の定理が示されていました。

定理
のあらゆるイデアルは，高々２個の要素で生成される.

blog.livedoor.jp
この「高々２個」の２はの生成元 の指数２と関係がありそうですよね。この定理を一般化した次の定理を示すことができます。

定理
を正整数とする。
と のあらゆるイデアルは，高々個の要素で生成される.

証明
まず， に対して示す。

はの部分環でPID。 を含む環 は階数 の自由 -加群になっている。のイデアルは の部分-加群で，ねじれ部分がないので，階数が高々の自由-加群になり，特に高々個の要素で生成されている。-加群としての生成系は当然，-加群としての生成系でもあるので，の任意のイデアルは高々個の要素で生成される。

に対しても， の部分環 を取って，全く同様に証明できる。
証明終

この証明は単に生成元の数がだけ以下ということだけを示していて，具体的にどのような元で生成されるかは教えてくれません。可換環論botこと龍孫江さんの証明はイデアルの生成元を具体的に生成元がどのようになるのかを与える構成的な証明です。

留数定理とリーマン・ゼータ関数

この記事は留数定理については学習済みであることを前提にしています。

今日はリーマン・ゼータ関数\begin{align}\displaystyle\zeta(s)=\sum_{n=1}^\infty \cfrac{1}{n^s}\end{align}の が正の偶数のときの値 を留数定理を使って計算します。

はベルヌーイ数というものを使って表すことができるのですが，留数定理を用いることによって，なぜベルヌーイ数が出てくるのか，その理由もはっきりします。

留数定理

留数定理を復習しておきましょう。 が でのローラン展開 \begin{align}\displaystyle f(z)=\sum_{n=-N}^\infty a_n (z-c)^n\end{align}を持つとき， を の における留数と呼びます。

留数定理
有界領域 内の単純閉曲線 が囲む領域 を考える。 が 内に孤立特異点 を持ち，それ以外の の点で正則であるならば\begin{align}\displaystyle \oint_C f(z) dz=2\pi i \sum_{j=1}^m \mathrm{Res}(f;c_j). \end{align}

ベルヌーイ数

ベルヌーイ数
は原点の近傍で正則で，そのテーラー展開 \begin{align}\cfrac{z}{e^z-1}=\sum_{n=0}^\infty \cfrac{B_n}{n!}z^n\end{align}で定まる をベルヌーイ数と呼ぶ。

であり， は有理数となります。また， は が 以上の奇数のとき になることが知られています。

の値

ベルヌーイ数を用いて，ゼータ関数 の正の偶数での値を表すことができます。

定理 (オイラー 1748)
を正整数とする。
\begin{align}\zeta(2k)=\cfrac{1}{2}\cdot \cfrac{ ( - 1 )^{k - 1 } (2\pi)^{2k} B_{2k} }{(2k)!}\end{align}

証明
とし，\begin{align}g(z)=\cfrac{f(2\pi i z)}{z^{2k+1}}=\cfrac{2\pi i}{z^{2k}}\cdot\cfrac{1}{e^{2\pi i z}-1}\end{align}とおく。 を正整数とし， を図のような，1辺が である正方形の積分経路とする。

の に囲まれる領域における特異点は となる整数 で， は位数 の極で， は位数 の極になっている。 における留数は，\begin{align}g(z)=\cfrac{1}{z^{2k+1}} \sum_{n=0}^\infty \cfrac{B_n}{n!}(2\pi i z)^n=\sum_{n=0}^\infty \cfrac{(2\pi i)^nB_n}{n!}z^{n-2k-1}\end{align}なので，\begin{align}\mathrm{Res}(g(z); 0) = \cfrac{(2\pi i)^{2k}B_{2k}}{(2k)!}=\cfrac{(-1)^k(2\pi)^{2k}B_{2k}}{(2k)!} \end{align}となる。また，その他の留数は とすると
\begin{eqnarray*}
\mathrm{Res}(g(z); n) &=& \lim_{z\to n} g(z)(z-n)=\lim_{z\to n} \cfrac{2\pi i}{z^{2k}}\cdot\cfrac{z-n}{e^{2\pi i z}-1}=\cfrac{2\pi i}{(n^{2k})}
\left( \cfrac{d e^{2\pi i z}}{dz}\bigg|_{z=n}\right)^{-1}=\cfrac{1}{n^{2k}}\\
\mathrm{Res}(g(z); -n) &=& \lim_{z\to -n} g(z)(z+n)=\lim_{z\to -n} \cfrac{2\pi i}{z^{2k}}\cdot\cfrac{z+n}{e^{2\pi i z}-1}=\cfrac{2\pi i}{(n^{2k})}
\left( \cfrac{d e^{2\pi i z}}{dz}\bigg|_{z=-n}\right)^{-1}=\cfrac{1}{n^{2k}}\\
\end{eqnarray*}となる。よって留数定理より\begin{align}\cfrac{1}{2\pi i}\oint_{\Gamma_N} g(z)dz=\sum_{n=-N}^N \mathrm{Res}(g;n) =\cfrac{(-1)^k(2\pi)^{2k}B_{2k}}{(2k)!}+2\sum_{n=1}^N \cfrac{1}{n^{2k}}\end{align}となる。

ここで が示されれば，上式で として目的の等式 \begin{align}\sum_{n=1}^\infty \cfrac{1}{n^{2k}}=\cfrac{1}{2}\cdot \cfrac{( - 1 )^{k - 1 } (2\pi)^{2k}B_{2k} }{(2k)!}\end{align}が得られる。

以下で を示す。

上の点 に対し，\begin{align}|g(z)|=\cfrac{2\pi}{|z|^{2k}}\cdot\cfrac{1}{|e^{-2\pi y\pm(N+1/2)\cdot 2\pi i }-1|}
=\cfrac{2\pi}{|z|^{2k}}\cdot\cfrac{1}{e^{-2\pi y}+1}< \cfrac{2\pi}{N^{2k}}\end{align} 上の点 に対し，\begin{align}|g(z)|=\cfrac{2\pi}{|z|^{2k}}\cdot\cfrac{1}{|e^{-2\pi(N+1/2) + 2\pi i x }-1|}<\cfrac{2\pi}{N^{2k}} \cdot\cfrac{1}{1 - e^{ - 2\pi(N+1/2)}} \le \cfrac{2\pi}{N^{2k}} \cdot\cfrac{1}{1 - e^{ - \pi}}\end{align} 上の点 に対し，\begin{align}|g(z)|=\cfrac{2\pi}{|z|^{2k}}\cdot\cfrac{1}{|e^{2\pi(N+1/2) + 2\pi i x }-1|}
\cfrac{2\pi}{N^{2k}} \cdot\cfrac{1}{e^{2\pi(N+1/2)-1}} \le \cfrac{2\pi}{N^{2k}} \cdot\cfrac{1}{e^{\pi}-1} \end{align}以上より， に依存しないある定数 を用いて， 上で と上から評価できる。よって \begin{align}\left| \cfrac{1}{2\pi i}\oint_{\Gamma_N} g(z)dz\right| \le \cfrac{1}{2\pi}\cdot |g(z)|\cdot \mathrm{length} (\Gamma_N) <\cfrac{ 4M(2N+1)}{2\pi N^{2k}}\to 0 ~(N\to\infty)\end{align}となるので である。

証明終

他にもいろいろな証明方法があるようですが，ベルヌーイ数が出てくる理由が分かりやすいので，お気に入りの証明です。