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

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

離散フーリエ変換

$N$ を正整数とし， $\zeta_N=e^{\frac{2\pi i}{N}}$ を $1$ の原始 $N$ 乗根をします。

長さ $N$ の複素数列 $\vec{a}=(a_0,\dots,a_{N-1})$ に $\vec{A}=(A_0,\dots,A_{N-1})$ \begin{align}A_p= \sum_{k=0}^{N-1} a_k \cdot \zeta_N^{-kp}\end{align}を対応させるものを離散フーリエ変換と呼び， $\mathcal{F}:\mathbb{C}^N \to \mathbb{C}^N$ で表します。

また， $\vec{A}=(A_1,\dots,A_{N-1})$ を $\vec{a}=(a_0,\dots,a_{N-1})$ \begin{align}a_p= \frac{1}{N}\sum_{k=0}^{N-1} A_k \cdot \zeta_N^{kp}\end{align}に対応させるものを逆離散フーリエ変換と呼び， $\mathcal{F}^{-1}:\mathbb{C}^N \to \mathbb{C}^N$ で表します。

$\mathcal{F}$ は線形同型写像で， $\mathcal{F}^{-1}$ が逆写像になっていることが知られています。つまり， $\vec{A}=\mathcal{F}(\vec{a})$ のとき $\vec{a}=\mathcal{F}^{-1}(\vec{A})$ が成り立ちます。

離散フーリエ変換 - Wikipedia

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

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

複素数体 $\mathbb{C}$ 上の1変数多項式環 $\mathbb{C}[T]$ を $f(T) \in \mathbb{C}[T]$ で生成されるイデアル $\langle f(T)\rangle$ で割った剰余環を $\cfrac{\mathbb{C}[T]}{\langle f(T)\rangle}$ で表すことにします。 $\mathbb{C}[T]$ における中国剰余定理は次の形になります。

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

特に $a_0,\dots,a_{N-1} \in\mathbb{C}$ が相異なる複素数で，\begin{align}f(T)=\prod_{k=0}^{N-1} (T-a_k)\end{align}のときを考えると， $\cfrac{\mathbb{C}[T]}{\langle T-a_k\rangle} \cong \mathbb{C}$ であり， $g(T) \equiv g(a_k) \mod \langle T-a_k\rangle$ なので，この場合の中国剰余定理の同型写像は \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*}となります。

この同型により，任意の $(b_0,\dots, b_{N-1})\in \mathbb{C}^N$ に対し，次数が高々 $N-1$ の多項式 $g(T)$ で $g(a_k)=b_k~~(0\le k \le N-1)$ が成り立つものが唯一存在することが分かります。これを利用したのが最近一部ネットで話題の月の日数を与える多項式です。

togetter.com
tsujimotter.hatenablog.com

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

$f(T)=T^N-1$ の場合を考えましょう。 $\zeta_N=e^{\frac{2\pi i}{N}}$ の逆数 $\zeta_N^{-1}$ も $1$ の原始 $N$ 乗根なので\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*}は環同型となります。

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

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

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

$\varphi$ は同型なので逆写像 $\varphi^{-1}$ が存在します。 $\varphi^{-1}$ がどうなるのか見てみましょう。

$\mathbb{C}^N$ の標準的な基底を $e_0,\dots,e_{N-1}$ とします。 $e_p$ は $p$ 番目の成分が $1$ でそれ以外の成分が $0$ のベクトルです。

$0\le p\le N-1$ に対し \begin{align}\varphi\left(\frac{1}{N}\sum_{k=0}^{N-1} \zeta_N^{kp} T^k\right)=e_p\end{align}となります。 $\varphi^{-1}$ は $\mathbb{C}$ -代数の準同型なので $\vec{A}=(A_1,\dots, A_{N-1})$ に対し \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*}となり， $\varphi^{-1}$ は逆離散フーリエ変換と本質的に同じものであることが分かります。

合成積

さて $\varphi:\frac{\mathbb{C}[T]}{\langle T^N-1\rangle} \to\mathbb{C}^N$ は単なるベクトル空間としての同型ではなくて環同型です。 $\frac{\mathbb{C}[T]}{\langle T^N-1\rangle}$ と $\mathbb{C}^N$ の演算を比較すると，足し算はどちらもベクトルの足し算と同じ構造で似たようなものですが，掛け算の方はかなり違って見えます。

$\mathbb{C}^N$ は環の直積なので積の構造は単純です。 $(A_0,\dots,A_{N-1}), (B_0,\dots,B_{N-1}) \in \mathbb{C}^N$ の積は成分ごとの積と定義され\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}となります。

一方で $\displaystyle f(T)=\vec{a}\cdot \vec{T}=\sum_{p=0}^{N-1} a_pT^p$ と $\displaystyle g(T)=\vec{b}\cdot \vec{T}=\sum_{q=0}^{N-1} b_qT^q$ の $\frac{\mathbb{C}[T]}{\langle T^N-1\rangle}$ での積は\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}となります。

ここで， $\vec{b}=(b_0,b_1,\dots,b_{N-1})$ の添え字を $\mathbb{Z}/N\mathbb{Z}=\{0,1,\dots,N-1\}$ と解釈します。つまり，任意の整数 $m$ に対して $b_{p+mN}=b_p$ です (数列 $b_p$ を周期 $N$ の繰り返しになるように添え字を $\mathbb{Z}$ 全体に拡張したと解釈してもいいです)。すると，先ほどの積は \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}と書けます。

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

合成積
$\vec{a}=(a_0,\dots,a_{N-1})$ ， $\vec{b}=(b_0,\dots,b_{N-1})$ に対し， $\vec{c}=(c_0,\dots,c_{N-1})$ \begin{align}c_k=\sum_{p=0}^{N-1} a_pb_{k-p}\end{align} を $\vec{a}$ と $\vec{b}$ の合成積と呼び， $\vec{a}*\vec{b}$ と書く。

$\mathbb{C}^N$ はベクトルの和を加法，合成積を乗法とした可換環になります。一見変わった環のような感じがしますが $\frac{\mathbb{C}[T]}{\langle T^N-1\rangle}$ を考えていることと同じです。

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

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

ここで $\mathcal{F}(\vec{a})\mathcal{F}(\vec{b})$ は直積環 $\mathbb{C}^N$ での積です (つまり成分ごとに積を取る)。以前と同じように $\vec{T}=(1,T,T^2,\dots,T^{N-1})$ で，黒点 $\cdot$ は内積の記号とします。

証明
合成積の定義より $(\vec{a}*\vec{b})\cdot\vec{T}=(\vec{a}\cdot\vec{T})(\vec{b}\cdot\vec{T})$ が $\frac{\mathbb{C}[T]}{\langle T^N-1\rangle}$ で成り立つ。 $\varphi$ は環準同型だったので， $\varphi((\vec{a}*\vec{b})\cdot\vec{T})=\varphi(\vec{a}\cdot\vec{T})\varphi(\vec{b}\cdot\vec{T})$ となる。

$\varphi(\vec{a}\cdot\vec{T})=\mathcal{F}(\vec{a})$ だったので，これは $\mathcal{F}(\vec{a}*\vec{b})=\mathcal{F}(\vec{a})\mathcal{F}(\vec{b})$ を意味している。

証明終