周期数列の母関数と離散フーリエ変換について

この記事はまだあまり整理されていません．

周期 $N$ の複素数列全体を $C^{Z / N} = {x ∣ x_{n} = x_{n + N} for every n \in Z}$ とする．
$C^{Z / N}$ 上のラグ作用素 $L$ を $L x = (x_{n - 1})_{n \in Z}$ で定義する．

$C^{Z / N}$ は加法 $x + y = (x_{n} + y_{n})_{n \in Z}$ ，スカラー乗法 $λ x = (λ x_{n})_{n \in Z}$ に関する $N$ 次元ベクトル空間である．

$\dim C^{Z / N} = N$ のみ示す． $δ \in C^{Z / N}$ を $N Z$ の指示関数，すなわち
$δ_{n} = {\begin{cases} 1 & (n \equiv 0 (\mod N)), \\ 0 & (otherwise) \end{cases}$
とする．このとき，集合 $S = {L^{m} δ ∣ 0 \leq m < N}$ は $C^{Z / N}$ の基底である．実際
$L^{m} δ_{n} = δ_{n - m} = {\begin{cases} 1 & (n \equiv m (\mod N)), \\ 0 & (otherwise) \end{cases}$
なので， $S$ の各元は1次独立であり，任意の $x \in C^{Z / N}$ は $x = \sum_{m = 0}^{N - 1} x_{m} L^{m} δ$ と書ける．

要するに， $S$ は $C^{N}$ の標準基底を周期的に拡張した集合である．

ここで
$x = \sum_{m = 0}^{N - 1} x_{m} L^{m} δ = (\sum_{m = 0}^{N - 1} x_{m} L^{m}) δ$
だから，写像 $Z : C^{Z / N} \to C [L]$ を $x \mapsto \sum_{m = 0}^{N - 1} x_{m} L^{m}$ で定義すれば， $(Z x) δ = x$ が成立する．ただし $C [L] = {P (L) ∣ P (z) \in C [z]}$ である．

環 $C [z] / ⟨ z^{N} - 1 ⟩$ は写像 $z + ⟨ z^{N} - 1 ⟩ \mapsto L$ によって $C [L]$ と同型である．

写像 $ϕ : C [z] \to C [L]$ を $P (z) \mapsto P (L)$ で定義する． $\ker ϕ = ⟨ z^{N} - 1 ⟩$ が示せれば，準同型定理より $C [z] / ⟨ z^{N} - 1 ⟩ ≅ C [L]$ がしたがう．また，この同型は $z + ⟨ z^{N} - 1 ⟩ \mapsto L$ を満たす．

$P (z) \in \ker ϕ$ を任意にとり， $P (z)$ を $z^{N} - 1$ で割った商を $Q (z)$ ，あまりを $R (z)$ とする．このとき $P (z) = Q (z) (z^{N} - 1) + R (z)$ ， $L^{N} = 1$ より $ϕ (P (z)) = R (L) = 0$ である．また， $\deg R (z) < N$ なので $R (z) = \sum_{m = 0}^{N - 1} r_{m} z^{m}$ とおける．すると
$ϕ (R (z)) δ = (\sum_{m = 0}^{N - 1} r_{m} L^{m}) δ = \sum_{m = 0}^{N - 1} r_{m} (L^{m} δ) = 0$
であり， $S$ は $C^{Z / N}$ の基底だから $r_{m} = 0$ である．つまり， $P (z) \in \ker ϕ$ なら $R (z) = 0$ ， $P (z) \in ⟨ z^{N} - 1 ⟩$ である．明らかに $⟨ z^{N} - 1 ⟩ \subset \ker ϕ$ も成り立つので， $\ker ϕ = ⟨ z^{N} - 1 ⟩$ である．

$Z$ は全単射である．

$\overset{ˇ}{Z} : C [L] \to C^{Z / N}$ を $P (L) \mapsto P (L) δ$ で定義する． $\overset{ˇ}{Z} (Z x) = (Z x) δ = x$ はすでに示したので， $Z (\overset{ˇ}{Z} P (L)) = P (L)$ が示せれば $\overset{ˇ}{Z} = Z^{- 1}$ といえる．

上の同型から $\deg P (z) < N$ を仮定してよい． $P (z) = \sum_{m = 0}^{N - 1} p_{m} z^{m}$ とし， $m$ を $N$ で割ったあまりを $m % N$ と書く，すると
$\overset{ˇ}{Z} P (L) = \sum_{m = 0}^{N - 1} p_{m} L^{m} δ = (p_{m % N})_{m \in Z}, Z (\overset{ˇ}{Z} P (L)) = \sum_{m = 0}^{N - 1} p_{m % N} L^{m} = P (L)$
である．

以上により， $Z$ は（加法を保つ）全単射である．よって， $C^{Z / N}$ の乗法を $x * y = Z^{- 1} ((Z x) (Z y))$ で定めれば，3つ組 $(C^{Z / N}, +, *)$ は $C [L]$ と同型な環になる．

$x * y$ を $x$ と $y$ の一般項を用いて表そう．
$(Z x) (Z y) = (\sum_{m = 0}^{N - 1} x_{m} L^{m}) (\sum_{n = 0}^{N - 1} y_{n} L^{n}) = \sum_{m = 0}^{N - 1} \sum_{n = 0}^{N - 1} x_{m} y_{n} L^{m + n}$
であり， $k = m + n$ とおくと
$(Z x) (Z y) = \sum_{m = 0}^{N - 1} \sum_{k = m}^{N - 1 + m} x_{m} y_{k - m} L^{k}$
となる． $\sum_{k = m}^{N - 1 + m}$ は1周期にわたる和なので，範囲を $\sum_{k = 0}^{N - 1}$ に変えてよい．よって
$(Z x) (Z y) = \sum_{m = 0}^{N - 1} \sum_{k = 0}^{N - 1} x_{m} y_{k - m} L^{k} = \sum_{k = 0}^{N - 1} (\sum_{m = 0}^{N - 1} x_{m} y_{k - m}) L^{k}$
であり， $z = x * y$ とおくと
$z = \sum_{k = 0}^{N - 1} (\sum_{m = 0}^{N - 1} x_{m} y_{k - m}) L^{k} δ, z_{k} = \sum_{m = 0}^{N - 1} x_{m} y_{k - m}$
となる．

$x, y \in C^{Z / N}$ とする．次式で定義される $x * y \in C^{Z / N}$ を， $x$ と $y$ の巡回畳み込みという．また， $x * y$ は $Z (x * y) = (Z x) (Z y)$ を満たす．
$x * y = z, z_{k} = \sum_{m = 0}^{N - 1} x_{m} y_{k - m}$

$\bar{z} = z + ⟨ z^{N} - 1 ⟩$ とする．同型写像 $ψ : C [z] / ⟨ z^{N} - 1 ⟩ \to C [L]$ ， $P (\bar{z}) \mapsto P (L)$ を用いて， $im Z$ を $C [z] / ⟨ z^{N} - 1 ⟩$ へと変えた写像 $ψ^{- 1} \circ Z$ を $\tilde{Z}$ とおく．つまり
$\tilde{Z} : C^{Z / N} \to C [z] / ⟨ z^{N} - 1 ⟩, (x_{n})_{n \in Z} \mapsto \sum_{n = 0}^{N - 1} x_{n} {\bar{z}}^{n}$
である．

写像 $f : C [z] \to C^{N}$ を $P (z) \mapsto (P (ζ^{k}))_{k = 0}^{N - 1}$ （ $ζ = e^{2 π i / N}$ ）で定義する．明らかに， $f$ は環準同型である．

$\ker f = ⟨ z^{N} - 1 ⟩$ である．

$P (z) \in ⟨ z^{N} - 1 ⟩$ なら， $P (z) = Q (z) (z^{N} - 1)$ とおくと $f (P (z)) = (Q (ζ^{k}) (ζ^{k N} - 1))_{k = 0}^{N - 1} = 0$ である．また $P (z) \in \ker f$ なら，因数定理より $P (z)$ は $\prod_{k = 0}^{N - 1} (z - ζ^{k}) = z^{N} - 1$ で割り切れる．

上の命題から，写像 $\bar{f} : C [z] / ⟨ z^{N} - 1 ⟩ \to C^{N}$ ， $P (\bar{z}) \mapsto (P (ζ^{k}))_{k = 0}^{N - 1}$ はwell-definedな環同型である．よって，写像 $F$ を $\bar{f} \circ \tilde{Z}$ で定義すると， $F$ は $(C^{Z / N}, +, *)$ から $C^{N}$ への環同型である．実際に $\hat{x} = F x$ を計算すると
$F x = f (\sum_{n = 0}^{N - 1} x_{n} {\bar{z}}^{n}), {\hat{x}}_{k} = \sum_{n = 0}^{N - 1} x_{n} ζ^{k n}$
となる．これは（符号の違いを除いて） $x$ の離散フーリエ変換である．

投稿日：2022年12月29日

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

投稿者

cuttlefish_math

10300

数学、特に応用数学が好きです。Mathlogでは主に、数学とプログラミングを絡めたようなことを書けたらいいなと思っています。

他の人のコメント

コメントはありません。

読み込み中

cuttlefish_math

周期数列の母関数と離散フーリエ変換について