高速フーリエ変換 その2 (+少し量子力学)

高速フーリエ変換に関することを書きます。前回の記事（「高速フーリエ変換 その1」）では基本的な考え方・アルゴリズムのことを書きました。本記事では群の表現論と高速フーリエ変換との関係を書こうと思います。

参考文献は記事最後に挙げたRef.[1-7]です。本記事の重要な部分（「剰余類分解と高速フーリエ変換」の前半部分）はkoboshiさんの記事「フーリエ変換と表現論」（Ref.[1]）を参考にさせて頂きました。もちろん文責は全て私puremoruにあります。

以下$${{\mathbb N, \mathbb Z, \mathbb C}}$$をそれぞれ自然数、整数、複素数の集合とします。$${:=}$$は左辺を右辺で定義する、$${=:}$$は右辺を左辺で定義する記号です。中括弧$${\{\}}$$は集合を表します。

前回の復習

まず「高速フーリエ変換 その1」の復習です。超短縮版です。

離散フーリエ変換

離散フーリエ変換(Discrete Fourier Transform, DFT)は以下のような変換：$${\{x_i\}\mapsto \{y_i\} \ (i=0 \text{ -- } N-1)}$$です:

$$
\begin{aligned}
y_j = \sum_{k=0}^{N-1} \exp(-2\pi i j k/N)x_k
\end{aligned}
\\
(i\text{は虚数単位})
$$

これは例えば時間の関数を周波数成分に分解するような変換です。「音をドレミで表す」ような操作に対応します。DFTは実に様々な分野の情報処理において使用されています。身近な音楽、写真、動画だけでなく、CTスキャンや超音波エコー等の医学における情報処理にも使われています。

高速フーリエ変換

前出のDFTをそのまま計算するより高速な計算方法があります。以下$${N=2^n \ \ (n\in {\mathbb N})}$$とします。DFTの和の中を$${x_k}$$の$${k}$$に関して偶奇に分けます：

$$
\begin{aligned}
y_j=\sum_{r=0}^{N/2-1}W^{jr}_{N/2}x_{2r}+W^j_N \sum_{r=0}^{N/2-1}W_{N/2}^{jr}x_{2r+1}, \ \ \ (0\le j \le N/2-1)
\end{aligned}
$$

ここで$${W_N:=\exp(-2\pi i/N)}$$です。

初項と第２項は、それぞれ要素数$${N/2}$$の独立なDFTです。それぞれの項において、更に同様の分解を実行することができます。これを再帰的に繰り返すと、最終的に要素数$${1}$$のDFTに帰着します。このように、偶奇わけの操作を繰り返すとDFTが実行できるのですが、これはナイーブなDFTと比較し計算量が本質的に減っています。これが高速フーリエ変換(Fast Fourier Transform, FFT)です。

群の表現論における高速フーリエ変換

以下高速フーリエ変換を有限アーベル群の表現論の観点から議論します。

有限アーベル群上のフーリエ変換は、群論・表現論的な立場では、以下のように定義されます:

$$
\begin{aligned}
&Gを有限アーベル群、g\in Gに対し\chi(g)をその指標とする。\\
&このときf\in L(G) \ \ (L(G)はGから{\mathbb C}への関
数全体のなす集合)\\
&に対し、\hat f\in L(G)を\\
&{}\\
&
\displaystyle
\hspace{2cm}\hat f(\chi)=|G|\langle f,\chi\rangle = \sum_{g\in G}f(g)\overline{\chi(g)}\\
&{}\\
&で定める。これをGのフーリエ変換とよぶ。\\
& 但し |G|はGの位数, \langle f_1,f_2\rangle:=\frac{1}{|G|}\sum_{g\in G}\overline{f_1(g)}f_2(g), 上部の線は複素\\&共役を表す。
\end{aligned}
$$

上記の定義を理解するため、用語の説明を以下に示します：

• $${\underline{群}}$$
  何らかの2項演算が定義されている集合$${G}$$が以下の条件を満たす時、群と呼ばれます（以下$${ab \ \ (a,b\in G)}$$と書いたらその間に2項演算子が存在するものとします）：
    ・結合法則を満たす: $${a(bc)=(ab)c, \ \ (a,b,c\in G)}$$
    ・単位元$${\mathbf 1}$$をもつ: $${a{\mathbf 1}={\mathbf 1}a=a, \ \ {\mathbf 1}, a\in G}$$
    ・逆元$${a^{-1}}$$をもつ: $${aa^{-1}=a^{-1}a={\mathbf 1}, \ \ a^{-1}\in G}$$
  群は数学のみならず物理学でも非常に重要な概念です。物理系が何らかの対称性をもつとき、対称性変換を集めると群になります。特に量子力学では、群論およびその表現論を用いると、シュレーディンガー方程式を実際に解く事なしに量子状態の性質を（ある程度）決定することができるので、大変便利でありまた不可欠です。

• $${\underline{位数}}$$
  群の元げんの数 

• $${\underline{部分群、正規部分群}}$$
  部分群は群の部分集合でそれ自身群をなすものです。正規部分群は$${G}$$の部分群$${H}$$であり、$${h\in H}$$が$${G}$$の元$${g\in G}$$による以下の変換に対して不変なものです:
  
  $${\hspace{1cm}\forall h\in H, \forall g\in G, \ \ g^{-1}hg\in H}$$
  
  $${g^{-1}hg}$$の形の変換を共役変換と呼びます。

• $${\underline{有限アーベル群}}$$
  群$${G}$$の元が可換（$${ab=ba, \ \ a,b\in G}$$）であり、かつ元の個数が有限のものです。

• $${\underline{剰余類、剰余群}}$$
  群$${G}$$及びその部分群$${H}$$が存在する時、集合
  
  $${gH=\{gh| h\in H, g\in G\}, \ \ \ Hg=\{hg| h\in H, g\in G\},}$$
  
  はそれぞれ左剰余類・右剰余類と呼ばれます。アーベル群の場合左右の区別は無く、単に剰余類と呼ぶことにします。部分群が正規部分群のとき、剰余類の集合$${G/H:=\{gH|g\in G\}}$$は演算
  
  $${(g_1H)(g_2H)=g_1g_2H\in G/H}$$
  
  により群をなします。$${G/H}$$は剰余群や商群と呼ばれます。

• $${\underline{剰余類分解}}$$
  同じ剰余類に属する元は同値と呼ばれます。同値関係を$${\sim}$$で表せば
  
  $${a\sim b\leftrightarrow \exist h, b=ah \ \ \ (h\in H)}$$
  
  です。$${G}$$の元で、同値ではない$${a_1,a_2,\ldots,a_m}$$のそれぞれの剰余類を$${a_1H,a_2H,\ldots,a_mH}$$と置くと、$${G}$$は次のように類別されます:
  
  $${G=H+ a_1H+ a_2H+ \ldots+ a_mH}$$
  
  上式の$${+}$$は、$${G}$$の元が$${a_i H}$$のどれかに属し、かつ異なる$${a_iH}$$は共通部分を持たないことを示します。この式は、$${G}$$の元の中で$${H}$$に含まれないものは$${H}$$と$${G}$$の元を使って表せることを示しています。

• $${\underline{準同型写像、同型}}$$
  準同型写像とは群$${G}$$から群$${G'}$$への写像であり
  
  $${f(uv)=f(u)f(v), \ \ \ u,v\in G}$$
  
  を満たすものをいいます。これは、群$${G}$$の構造が群$${G'}$$の構造において保たれることを意味します。$${f}$$が全単射なら$${f}$$は群の同型と呼ばれ、$${G\simeq G'}$$で表します。この場合$${G}$$と$${G'}$$は群として等しいです。

• $${\underline{指標}}$$
  $${G}$$を有限アーベル群とします。群$${G}$$から$${\mathbb C^\times:={\mathbb C}-\{0\}}$$への準同型写像を$${G}$$の指標と呼び、その全体を$${\hat G}$$と書きます。すなわち
  
  $${\hat G=\{\chi: G\rightarrow {\mathbb C^\times,\chi(ab)=\chi(a)\chi(b), \ \ \ a,b\in G}\}}$$
  
  です。

• $${\underline{{\mathbb Z}/n{\mathbb Z}}}$$
  $${{\mathbb Z}/n{\mathbb Z}}$$は$${n{\mathbb Z}:=\{0,\pm n,\pm 2n,\ldots\}}$$による$${\mathbb Z}$$の剰余群です。具体的には
  
  $${{\mathbb Z}/n{\mathbb Z}=\{[0],[1],\ldots,[n-1]\}}$$
  
  です。ここで
  
  $${[m]:=m+n{\mathbb Z}=\{m+nk, \ \ 0\le m\le n-1, \ \ k\in {\mathbb Z}\}}$$
  
  としました。$${\mathbb Z}$$は剰余類分解
  
  $${{\mathbb Z}=[0] + [1] + \ldots + [n-1]}$$
  
  を持ちます。

• $${\underline{表現}}$$
  表現とは、$${g\in G}$$を具体的な「表現・表示」に写す、以下のような写像$${\rho}$$です:
  
  $${\rho: G\rightarrow GL(V),\ \ \rho(gh)=\rho(g)\rho(h)}$$
  
  ここで$${V}$$は$${n}$$次元複素線型空間、$${GL(V)}$$は$${V\rightarrow V}$$の可逆線形写像のなす群です。つまりは表現とは、$${G}$$から$${GL(V)}$$への準同型写像です。これは$${G}$$の世界の関係が$${GL(V)}$$の世界でも同じように成立することを保証します。ベクトル空間$${V}$$に基底を導入すれば行列になります。表現行列とはこのようにして$${g}$$と対応する行列のことです。
  
  例えばある$${g\in G}$$に対し、適当に基底をとれば、表現行列により
  
  $${D(g)=\begin{pmatrix} D_{11}(g) & D_{12}(g) & \ldots & D_{1n}(g) \\ D_{21}(g) & D_{22}(g) & \ldots & D_{2n}(g) \\ \vdots & \vdots & \ddots & \vdots \\ D_{n1}(g) & D_{n2}(g) & \ldots & D_{nn}(g)\end{pmatrix}}$$
  
  と書けます。これは例えば2次元平面においてデカルト座標を採用し、$${x,y}$$方向の単位ベクトルを基底にとると、回転角$${\theta}$$の回転行列が
  
  $${\begin{pmatrix} \cos\theta & -\sin\theta\\ \sin\theta & \cos\theta \end{pmatrix}}$$
  
  とかけるようなことに対応します。
  
  指標の定義は表現のそれと大変似ています。実際、指標は表現行列の対角成分の和です：
  
  $${\displaystyle\chi(g)=\sum_i D_{ii}(g)}$$
  
  本記事では有限アーベル群のみ扱っており、必ず1次元表現（1行1列の複素"行列"による表現）になるので、表現行列と指標に区別はないです。表現に関する理論である表現論は、群論と不可分であり、数学・物理学において大切な分野です。

• $${\underline{可約表現、既約表現}}$$
  重要ですが本記事では必要ないので、Appendixに少しだけ書きます。

• $${\underline{巡回群}}$$
  唯１つの元で生成される群です。その元を$${g}$$とすると
  
  $${G=\{g^n|n\in {\mathbb Z}\}}$$
  
  と書けます。これが有限群であり、その位数が$${n}$$なら
  
  $${G=\{g^0,g^1,g^2,\ldots,g^{n-1}\}}$$
  
  です。巡回群はアーベル群なので、位数$${n}$$が有限なら、有限アーベル群です。これは$${{\mathbb Z}/n{\mathbb Z}}$$と同型です。$${g^n={\bf 1}}$$および$${\chi(g^2)=\chi(g)^2}$$より、有限巡回群の指標は以下を満たします：
  
  $${\chi(g)^n=1}$$
  
  つまり、$${\chi(g)}$$は1の$${n}$$乗根です：$${\chi(g)=e^{2\pi i/n}}$$

• $${\underline{\hat Gの双対性}}$$
  指数の積を$${(\chi_1\cdot \chi_2)(g):=\chi_1(g)\chi_2(g) \ \ \ (g\in G)}$$で定義すれば$${\hat G}$$は群になります。そして以下の双対性
  
  $${G\simeq \hat G}$$
  
  を満たします。$${G}$$が巡回群の場合、$${\hat G}$$は
  
  $${\hat G=\{\chi_0,\chi_1,\ldots,\chi_{n-1}\}=\{e^{2\pi m i/n}, \ 0\le m \le n-1\}}$$
  
  です。

剰余類分解と高速フーリエ変換

以上で高速フーリエ変換を説明する準備が整いました。

$${G}$$の部分群$${H^{(1)}}$$をひとつとってきます。これに関する剰余類分解

$${G=H^{(1)}+ a_1H^{(1)}+ a_2H^{(1)}+ \ldots+ a_mH^{(1)}}$$

を考えます。$${G}$$の任意の元は$${g=a_j h \ \ \ (0\le j\le m, \ h\in H^{(1)})}$$と一意的に表せます（$${a_0 h}$$は右辺第１項の元を表すものとする）。すると、前章冒頭に示したフーリエ変換は以下のように分解できます：

$$
\displaystyle
\hat f(\chi)=\sum_{j=1}^m\sum_{h\in H^{(1)}}f(a_j h)\overline{\chi(a_j h)}
=\sum_{j=1}^m\overline{\chi(a_j)}\sum_{h\in H^{(1)}}f(a_j h)\overline{\chi(h)}
$$

$${\chi(ab)=\chi(a)\chi(b) \ \ (a,b\in G)}$$が成立することに注意してください。この式の内側の総和は、$${{H}^{(1)}}$$に関するフーリエ変換です。よってフーリエ変換が

• 部分群$${H^{(1)}}$$についてフーリエ変換を計算する

• 剰余類について総和を求める

の２つの作業に分解されました。さらに$${H^{(1)}}$$についてフーリエ変換を計算する際も同様に計算を行うことができます。これを繰り返し、部分群の列$${G\supseteq H^{(1)}\supseteq H^{(2)} \supseteq\ldots\supseteq \{\mathbf 1\}}$$に対して分解を行うことで、$${G}$$のフーリエ変換を得ます。これは高速フーリエ変換に対応します。

具体的に$${N}$$が2のべきの場合を考えます。有限アーベル群

$$
G=\{e^{2\pi k i/N}, \ \ 0\le k\le N-1\}
$$

を考え、正規部分群

$$
\begin{aligned}
H^{(1)}&=\{e^{2\pi i\cdot 2k'/N}, \ \ 0\le k'\le N/2-1\}\\
&=\{e^{2\pi i\cdot k'/(N/2)}, \ \ 0\le k'\le N/2-1\}
\end{aligned}
$$

とすると、$${H^{(1)}}$$に関する剰余群分解は

$$
G=H^{(1)}+e^{2\pi i /N}H^{(1)}
$$

となります。実際

$$
\begin{aligned}
H^{(1)}&=\{e^{2\pi i\cdot 0/N},e^{2\pi i\cdot 2/N},e^{2\pi i\cdot 4/N},\ldots\},\\
e^{2\pi i/N}H^{(1)}&=\{e^{2\pi i\cdot 1/N},e^{2\pi i\cdot 3/N},e^{2\pi i\cdot 5/N},\ldots\}
\end{aligned}
$$

であり、$${G}$$を尽くします。同様に、$${H^{(1)}}$$の正規部分群

$$
\begin{aligned}
H^{(2)}&=\{e^{2\pi i\cdot 2k''/(N/2)}, \ \ 0\le k''\le N/2^2-1\}\\
&=\{e^{2\pi i\cdot k''/(N/2^2)}, \ \ 0\le k''\le N/2^2-1\}
\end{aligned}
$$

に関して

$$
H^{(1)}=H^{(2)}+e^{2\pi i /(N/2)}H^{(2)}
$$

が成立します。これを$${\log_2 N}$$回繰り返せば、フーリエ変換が完了します。$${N}$$が2のべき以外でも、同様の分解が可能なことはわかるのではないかと思います。

量子力学における「フーリエ変換」

本章・次の章はおまけです。話が大雑把になります。

量子力学では、一般化されたフーリエ変換は重要です。ある量子状態$${|\psi\rangle}$$を正規直交基底$${|\alpha\rangle}$$で展開すると

$$
\begin{aligned}
|\psi\rangle=\sum_\alpha |\alpha\rangle\langle\alpha|\psi\rangle
\end{aligned}
$$

とかけます。$${\alpha}$$が連続量の場合は、和を積分に読み替えてください。この$${\langle\alpha|\psi\rangle}$$は一般化された"フーリエ係数"です。$${|\alpha\rangle}$$がエルミート演算子である物理量$${\hat A}$$の固有状態、すなわち$${\hat A|\alpha\rangle=\alpha|\alpha\rangle}$$とすれば、$${|\psi\rangle}$$を$${\hat A}$$に関して観測すると、$${|\langle\alpha|\psi\rangle|^2}$$に比例した確率で固有値$${\alpha}$$を得ます。$${\langle\alpha|\psi\rangle}$$は$${\alpha}$$表示の波動関数と呼ばれます。

上記の$${|\alpha\rangle}$$を位置の固有状態$${|x\rangle}$$とし、左から運動量の固有状態$${\langle p|}$$を作用させれば

$$
\displaystyle 
\langle p|\psi\rangle=\sum_x \langle p|x\rangle \langle x |\psi\rangle
$$

となります。Ref.[7]に示したように、$${\langle p|x\rangle}$$は

$$
\langle p|x\rangle\propto e^{-ipx/\hbar}
$$

です。よって

$$
\langle p|\psi\rangle=\sum_x e^{-ipx/\hbar} \langle x |\psi\rangle
$$

を得ます。これは、位置表示の波動関数$${\langle x |\psi\rangle}$$を、ふつうの意味でフーリエ変換すると、運動量表示の波動関数$${\langle p |\psi\rangle}$$を得ることを意味します。$${\langle x |\psi\rangle}$$が狭義のいわゆる波動関数です。境界条件を課せば、一般に、取りうる$${p}$$の値が離散的になります。

フーリエ変換との対応で言えば、波動関数はフーリエ係数に対応します。変換前と変換後の基底の内積が指標に対応します。

上記の例は1次元表現です。一方、例えば、3次元空間において中心力ポテンシャルの下での波動関数を角運動量の基底で展開することを考えれば、角運動量代数の非可換性により多次元表現が顔を出します。

量子力学における群論・表現論の重要性

量子力学では波動関数$${\langle\alpha|\psi\rangle}$$（＝"フーリエ係数"）を求めることがひとつの目標です。そのためには具体的に基底$${|\alpha\rangle}$$を設定し、その表示のもとでシュレーディンガー方程式を解く必要があります。しかし微分方程式を解くのは（簡単な方程式以外）発見法的であるように感じますし、系統的に解くなら展開を用いるしかないように思います。例えばシュレーディンガー方程式を解いて水素原子の波動関数を求めるには、岩波の公式集でも見ない限りは解を多項式等の基底で展開して係数を求めるしかありません（あとは試行錯誤とひらめきによる発見的方法）。そして、解を求めてもその意味するところはわかりにくいです。

ところで、系の回転不変性より角運動量演算子とハミルトニアンが可換であることから、角運動量演算子の固有状態は同時にハミルトニアンの固有状態です。よって、角運動量演算子の固有状態の性質を知ることが、系の性質（＝ハミルトニアンの固有状態の性質）を調べる際には重要であることがわかります。ゆえに、回転変換のなす群（＝角運動量演算子を生成子とする群）の表現に関する性質を調べることが、水素原子の性質を知るためには大切です。微分方程式を解かなくとも、群論・表現論による議論により、系のかなりの情報を得ることが可能です。

そして現代物理学では、水素原子だけではなく、また量子力学だけではなく、系の対称性を群論・表現論さらにはトポロジーにより考察することが不可欠です。

おしまい。$${{}_\blacksquare}$$

References

[1] koboshi「フーリエ変換と表現論」：
　https://hackmd.io/@koboshi/rJpHiXa-O
[2] Steinberg, B. "Representation Theory of Finite Groups." (Springer New York, 2012).
[3] 河添 健「群上の調和解析」すうがくの風景1 （朝倉書店）
[4] Wikipedia 「群」「表現」等、群論・表現論に関連する項目
[5] 小野寺喜孝 「物性物理 物性化学のための群論入門」（裳華房）
[6] 物理のかぎしっぽ「剰余類」：
　https://hooktail.sub.jp/algebra/Remainder/
[7] puremoru「【量子力学】運動量固有状態の位置表示」：
　https://note.com/puremoru/n/n04606d42b348

Appendix: 可約表現、既約表現

群には可約・可約表現、既約・既約表現という概念があります。表現行列は、その基底をうまくとりかえると、変換が混ざらない組に組分けできることがあります。大雑把にいうと、可約表現とは変換が混ざらない組に組分けできる表現のこと、既約とはそうではない表現のことです。

Wikipedia「既約表現」の項目から、既約、可約の定義を引用します：

$${V}$$の線型部分空間$${W}$$が$${G}$$-不変であるとは、任意の$${g\in G}$$および$${w\in W}$$に対して$${gw\in W}$$が成立することを言う。表現$${\rho}$$を$${G}$$-不変部分空間$${W}$$へ制限したものは部分表現と呼ばれる。表現$${\rho: G\rightarrow GL(V)}$$が既約であるとは、それが自明でない部分表現を持たないことを言う（任意の表現は自明な$${G}$$-不変部分空間、つまり全体空間$${V}$$と$${\{0\}}$$を部分表現として必ず含むことに注意）。真の非自明な不変部分空間を持つ表現$${\rho}$$は、可約(reducible)であると言う。

Wikipedia「既約表現」の項目より

上記文章はなんだか難しいですが、表現行列で説明すれば難しくないです。いま、ある群の元の表現行列が

$${D(g)=\begin{pmatrix} D_{11}(g) & D_{12}(g) & \ldots & D_{1n}(g) \\ D_{21}(g) & D_{22}(g) & \ldots & D_{2n}(g) \\ \vdots & \vdots & \ddots & \vdots \\ D_{n1}(g) & D_{n2}(g) & \ldots & D_{nn}(g)\end{pmatrix}}$$

であったとします。ある変換行列$${P}$$が存在し、 相似変換$${D(g)\rightarrow P^{-1}D(g)P}$$に対し

$${\begin{aligned} D(g)&=\begin{pmatrix} D^{(1)}(g) & 0 & \ldots & 0 \\ 0 & D^{(2)}(g)  & \ldots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \ldots & D^{k}(g)\end{pmatrix} \\ &{}\\ &=: D^{(1)}(g)\oplus D^{(2)}(g)\oplus \ldots\oplus D^{(k)}(g)\end{aligned}}$$

のように、前記の表現行列がブロック対角に変換できることがあります。ここで$${D^{(i)}}$$や$${0}$$は一般には行列であることに注意してください。これが可能な場合を可約表現、できない場合を既約表現と言います。このようにブロック対角にできる場合、それぞれの$${D^{(i)}}$$が作用する世界が異なり、独立になることを意味します。