競技プログラミングにおいて (高速) フーリエ変換は中～上級者の間でよく使われるテクニックです。AtCoder による解説も存在します。
また、有志による解説も数多く紹介します。ここでは一部を紹介します。
この記事の目標は、表現論の立場からフーリエ変換を理解することです。表現論については最初になるべく解説しますが、線形代数と群論の用語は説明なく用いることがあります。記法は Steinberg (参考文献を参照) に基づいています。
表現
#
群論のキーワードの 1 つに「対称性 」があります。例えば正六角形は 60° 回転させたり、反転させたりしても形が変わりません。このような形を保つ変換は、合成しても形を保つ変換なので群をなします。正六角形の場合は位数 12 の二面体群と呼ばれるものになります。このように対称性を調べるのに群は大いに役立ちます。
ところで、群の定義を思い出してみましょう。
群とは、集合 G G G ⋅ : G × G → G \cdot : G\times G \to G ⋅ : G × G → G
任意の x , y , z ∈ G x,y,z\in G x , y , z ∈ G x ⋅ ( y ⋅ z ) = ( x ⋅ y ) ⋅ z x\cdot (y\cdot z)=(x\cdot y)\cdot z x ⋅ ( y ⋅ z ) = ( x ⋅ y ) ⋅ z
ある e ∈ G e\in G e ∈ G g ∈ G g\in G g ∈ G g ⋅ e = e ⋅ g = g g\cdot e=e\cdot g=g g ⋅ e = e ⋅ g = g
任意の g ∈ G g\in G g ∈ G g − 1 ∈ G g^{-1}\in G g − 1 ∈ G g ⋅ g − 1 = g − 1 ⋅ g = e g\cdot g^{-1}=g^{-1}\cdot g=e g ⋅ g − 1 = g − 1 ⋅ g = e
どこにも対称性という言葉が出てきません。このような抽象的な定義では、対称性とどのような関係があるかわかりません。そこで、抽象的に定義された群がどのような対称性をもつのかを考えていきます。
G G G X X X X X X X X X S X S_X S X G G G S X S_X S X G G G X X X 作用 と呼びます。G G G X X X
考えることが多いのが X X X V V V n n n n n n X X X X X X V V V V V V G L ( V ) GL(V) G L ( V ) G G G G L ( V ) GL(V) G L ( V ) G G G V V V 表現 と呼びます。φ \varphi φ g ∈ G g\in G g ∈ G φ ( g ) \varphi(g) φ ( g ) V V V φ ( g ) \varphi(g) φ ( g ) φ g \varphi_g φ g V V V n n n 次元 といいます。例えば、位数 12 の二面体群が正六角形の対称性を表すということは 2 次元の表現であるとみることができます。
線形変換は基底を 1 つとることで行列表示することが可能です。そのため、表現とは G G G n n n G L n ( C ) GL_n(\mathbb{C}) G L n ( C )
V , W V,W V , W G G G φ : G → G L ( V ) , ψ : G → G L ( W ) \varphi\colon G\to GL(V), \psi\colon G\to GL(W) φ : G → G L ( V ) , ψ : G → G L ( W ) V ⊕ W V\oplus W V ⊕ W ρ : G → G L ( V ⊕ W ) \rho\colon G\to GL(V\oplus W) ρ : G → G L ( V ⊕ W ) ρ g ( v , w ) = ( φ g ( v ) , ψ g ( w ) ) ( g ∈ G , v ∈ V , w ∈ W ) \rho_g(v,w)=(\varphi_g(v),\psi_g(w)) \ (g\in G, v\in V, w\in W) ρ g ( v , w ) = ( φ g ( v ) , ψ g ( w )) ( g ∈ G , v ∈ V , w ∈ W ) 直和 といい、ρ = φ ⊕ ψ \rho=\varphi\oplus\psi ρ = φ ⊕ ψ
G G G φ : G → G L ( V ) , ψ : G → G L ( W ) \varphi\colon G\to GL(V), \psi\colon G\to GL(W) φ : G → G L ( V ) , ψ : G → G L ( W ) 同値 であるとは、線形同型 T : V → W T\colon V\to W T : V → W g ∈ G g\in G g ∈ G T ∘ φ g = ψ g ∘ T T\circ\varphi_g=\psi_g\circ T T ∘ φ g = ψ g ∘ T
φ : G → G L ( V ) \varphi\colon G\to GL(V) φ : G → G L ( V ) W W W V V V g ∈ G , w ∈ W g\in G, w\in W g ∈ G , w ∈ W φ g ( w ) ∈ W \varphi_g(w)\in W φ g ( w ) ∈ W W W W G G G φ : G → G L ( V ) \varphi\colon G\to GL(V) φ : G → G L ( V ) 既約 であるとは、G G G { 0 } \{0\} { 0 } V V V
既約表現は素数と似ていると思った人もいるかもしれません。実際、素因数分解の表現バージョンともいえる以下の定理が知られています。
マシュケの定理 : 有限群の表現は、いくつかの既約表現の直和と同値である。
既約表現への分解は本質的に一意であることも知られています。
指標
#
正方行列 A A A ∑ i = 1 n A i i \sum_{i=1}^nA_{ii} ∑ i = 1 n A ii T r ( A ) \mathrm{Tr}(A) Tr ( A ) T r ( A B ) = T r ( B A ) \mathrm{Tr}(AB)=\mathrm{Tr}(BA) Tr ( A B ) = Tr ( B A )
V V V V V V A , B A,B A , B P P P A = P − 1 B P A=P^{-1}BP A = P − 1 BP T r ( A ) = T r ( P − 1 B P ) = T r ( B P P − 1 ) = T r ( B ) \mathrm{Tr}(A)=\mathrm{Tr}(P^{-1}BP)=\mathrm{Tr}(BPP^{-1})=\mathrm{Tr}(B) Tr ( A ) = Tr ( P − 1 BP ) = Tr ( BP P − 1 ) = Tr ( B )
よって、表現 φ : G → G L ( V ) \varphi\colon G\to GL(V) φ : G → G L ( V ) χ φ : G → C \chi_{\varphi}\colon G\to \mathbb{C} χ φ : G → C χ φ ( g ) = T r ( φ ( g ) ) \chi_{\varphi}(g)=\mathrm{Tr}(\varphi(g)) χ φ ( g ) = Tr ( φ ( g )) χ φ \chi_{\varphi} χ φ 指標 と呼びます。既約表現の指標を既約指標 と呼びます。
G G G C \mathbb{C} C L ( G ) L(G) L ( G ) L ( G ) L(G) L ( G ) L ( G ) L(G) L ( G )
まず f 1 , f 2 ∈ L ( G ) f_1,f_2\in L(G) f 1 , f 2 ∈ L ( G ) f 1 + f 2 f_1+f_2 f 1 + f 2 ( f 1 + f 2 ) ( x ) : = f 1 ( x ) + f 2 ( x ) (f_1+f_2)(x):=f_1(x)+f_2(x) ( f 1 + f 2 ) ( x ) := f 1 ( x ) + f 2 ( x ) ( c f ) ( x ) : = c f ( x ) (cf)(x):=cf(x) ( c f ) ( x ) := c f ( x ) L ( G ) L(G) L ( G )
⟨ f 1 , f 2 ⟩ : = 1 ∣ G ∣ ∑ g ∈ G f 1 ( g ) ‾ f 2 ( g )
\langle f_1,f_2\rangle:=\frac{1}{|G|}\sum_{g\in G}\overline{f_1(g)}f_2(g)
⟨ f 1 , f 2 ⟩ := ∣ G ∣ 1 g ∈ G ∑ f 1 ( g ) f 2 ( g ) と定めることができます。
積は 2 種類あります。1 つは各点積 ( f 1 ⋅ f 2 ) ( g ) : = f 1 ( g ) f 2 ( g ) (f_1\cdot f_2)(g):=f_1(g)f_2(g) ( f 1 ⋅ f 2 ) ( g ) := f 1 ( g ) f 2 ( g )
( f 1 ∗ f 2 ) ( g ) : = ∑ h ∈ G f 1 ( g h − 1 ) f 2 ( h )
(f_1*f_2)(g):=\sum_{h\in G}f_1(gh^{-1})f_2(h)
( f 1 ∗ f 2 ) ( g ) := h ∈ G ∑ f 1 ( g h − 1 ) f 2 ( h ) です。L ( G ) L(G) L ( G ) C ∣ G ∣ \mathbb{C}^{|G|} C ∣ G ∣
有限アーベル群上のフーリエ変換
#
G G G
既約表現は 1 次元である。ゆえに既約表現がそのまま既約指標になる。
既約指標は ∣ G ∣ |G| ∣ G ∣
既約指標は L ( G ) L(G) L ( G )
G G G フーリエ変換 を考えていきます。G = { g 1 , g 2 , … , g n } G=\{g_1,g_2,\ldots,g_n\} G = { g 1 , g 2 , … , g n } n n n χ 1 , χ 2 , … , χ n \chi_1,\chi_2,\ldots,\chi_n χ 1 , χ 2 , … , χ n f ∈ L ( G ) f\in L(G) f ∈ L ( G ) f ^ ∈ L ( G ) \widehat{f}\in L(G) f ∈ L ( G )
f ^ ( g i ) = n ⟨ χ i , f ⟩ = ∑ g ∈ G χ i ( g ) ‾ f ( g )
\widehat{f}(g_i)=n\langle \chi_i,f\rangle=\sum_{g\in G}\overline{\chi_i(g)}f(g)
f ( g i ) = n ⟨ χ i , f ⟩ = g ∈ G ∑ χ i ( g ) f ( g ) により定めます。この定義は g i , χ i g_i,\chi_i g i , χ i
χ 1 , χ 2 , … , χ n \chi_1,\chi_2,\ldots,\chi_n χ 1 , χ 2 , … , χ n L ( G ) L(G) L ( G ) f ∈ L ( G ) f\in L(G) f ∈ L ( G )
f = ∑ i = 1 n ⟨ χ i , f ⟩ χ i
f=\sum_{i=1}^n\langle \chi_i,f\rangle\chi_i
f = i = 1 ∑ n ⟨ χ i , f ⟩ χ i と表せます。上の定義から
f = 1 n ∑ i = 1 n f ^ ( g i ) χ i
f=\frac{1}{n}\sum_{i=1}^n\widehat{f}(g_i)\chi_i
f = n 1 i = 1 ∑ n f ( g i ) χ i が成り立ちます。これをフーリエ逆変換 と呼びます。
逆変換の公式より、f ^ = 0 \widehat{f}=0 f = 0 f = 0 f=0 f = 0 T : L ( G ) → L ( G ) T\colon L(G)\to L(G) T : L ( G ) → L ( G ) T f = f ^ Tf=\widehat{f} T f = f T T T L ( G ) L(G) L ( G ) T T T
a ∗ b ^ ( g i ) = n ⟨ χ i , a ∗ b ⟩ = ∑ g ∈ G χ i ( g ) ‾ ( a ∗ b ) ( g ) = ∑ g ∈ G ∑ h ∈ G χ i ( g ) ‾ a ( g h − 1 ) b ( h ) = ∑ h ∈ G b ( h ) ∑ g ∈ G χ i ( g ) ‾ a ( g h − 1 ) = ∑ h ∈ G b ( h ) ∑ x ∈ G χ i ( x h ) ‾ a ( x ) ( x = g h − 1 ) = ∑ h ∈ G χ i ( h ) ‾ b ( h ) ∑ x ∈ G χ i ( x ) ‾ a ( x ) = n ⟨ χ i , b ⟩ ⋅ n ⟨ χ i , a ⟩ = b ^ ( g i ) ⋅ a ^ ( g i ) = ( a ^ ⋅ b ^ ) ( g i )
\begin{align*}
\widehat{a* b}(g_i) &= n\langle\chi_i,a* b\rangle \\
&= \sum_{g\in G}\overline{\chi_i(g)}(a* b)(g) \\
&= \sum_{g\in G}\sum_{h\in G}\overline{\chi_i(g)}a(gh^{-1})b(h) \\
&= \sum_{h\in G}b(h)\sum_{g\in G}\overline{\chi_i(g)}a(gh^{-1}) \\
&= \sum_{h\in G}b(h)\sum_{x\in G}\overline{\chi_i(xh)}a(x) \quad (x=gh^{-1}) \\
&= \sum_{h\in G}\overline{\chi_i(h)}b(h)\sum_{x\in G}\overline{\chi_i(x)}a(x) \\
&= n\langle \chi_i,b\rangle\cdot n\langle \chi_i,a\rangle \\
&= \widehat{b}(g_i)\cdot\widehat{a}(g_i) \\
&= (\widehat{a}\cdot\widehat{b})(g_i)
\end{align*}
a ∗ b ( g i ) = n ⟨ χ i , a ∗ b ⟩ = g ∈ G ∑ χ i ( g ) ( a ∗ b ) ( g ) = g ∈ G ∑ h ∈ G ∑ χ i ( g ) a ( g h − 1 ) b ( h ) = h ∈ G ∑ b ( h ) g ∈ G ∑ χ i ( g ) a ( g h − 1 ) = h ∈ G ∑ b ( h ) x ∈ G ∑ χ i ( x h ) a ( x ) ( x = g h − 1 ) = h ∈ G ∑ χ i ( h ) b ( h ) x ∈ G ∑ χ i ( x ) a ( x ) = n ⟨ χ i , b ⟩ ⋅ n ⟨ χ i , a ⟩ = b ( g i ) ⋅ a ( g i ) = ( a ⋅ b ) ( g i ) より、T ( a ∗ b ) = T a ⋅ T b T(a* b)=Ta\cdot Tb T ( a ∗ b ) = T a ⋅ T b L ( G ) L(G) L ( G ) ⋅ \cdot ⋅ ∗ * ∗
離散フーリエ変換
#
G = Z / N Z G=\mathbb{Z}/N\mathbb{Z} G = Z / N Z N N N χ \chi χ Z / N Z \mathbb{Z}/N\mathbb{Z} Z / N Z χ ( 1 ) = z \chi(1)=z χ ( 1 ) = z χ ( N ) = z N \chi(N)=z^N χ ( N ) = z N χ ( N ) = χ ( 0 ) = 1 \chi(N)=\chi(0)=1 χ ( N ) = χ ( 0 ) = 1 z N = 1 z^N=1 z N = 1 z z z N N N N N N N N N k = 0 , 1 , … , N − 1 k=0,1,\ldots,N-1 k = 0 , 1 , … , N − 1 e 2 π i k / N e^{2\pi ik/N} e 2 πik / N
実際、k = 0 , 1 , … , N − 1 k=0,1,\ldots,N-1 k = 0 , 1 , … , N − 1 χ k ( m ) = e 2 π i k m / N \chi_k(m)=e^{2\pi ikm/N} χ k ( m ) = e 2 πikm / N χ k \chi_k χ k ∣ G ∣ = N |G|=N ∣ G ∣ = N
フーリエ変換は上の式に従って書くと、f : Z / N Z → C f\colon \mathbb{Z}/N\mathbb{Z}\to\mathbb{C} f : Z / N Z → C
f ^ ( k ) = ∑ m = 0 N − 1 χ k ( m ) ‾ f ( m ) = ∑ m = 0 N − 1 e − 2 π i k m / N f ( m )
\widehat{f}(k)=\sum_{m=0}^{N-1}\overline{\chi_k(m)}f(m)=\sum_{m=0}^{N-1}e^{-2\pi ikm/N}f(m)
f ( k ) = m = 0 ∑ N − 1 χ k ( m ) f ( m ) = m = 0 ∑ N − 1 e − 2 πikm / N f ( m ) となります。フーリエ逆変換は
f ( k ) = 1 N ∑ m = 0 N − 1 e 2 π i k m / N f ^ ( m )
f(k)=\frac{1}{N}\sum_{m=0}^{N-1}e^{2\pi ikm/N}\widehat{f}(m)
f ( k ) = N 1 m = 0 ∑ N − 1 e 2 πikm / N f ( m ) です。
多項式の積
#
2 つの多項式 f ( x ) , g ( x ) f(x),g(x) f ( x ) , g ( x ) O ( deg f deg g ) O(\deg f\deg g) O ( deg f deg g )
まず N > deg f + deg g N>\deg f+\deg g N > deg f + deg g N N N G = Z / N Z G=\mathbb{Z}/N\mathbb{Z} G = Z / N Z f ( x ) = ∑ a m x m f(x)=\sum a_mx^m f ( x ) = ∑ a m x m m ↦ a m m\mapsto a_m m ↦ a m f f f L ( G ) L(G) L ( G ) g g g L ( G ) L(G) L ( G ) f ∗ g ∈ L ( G ) f*g\in L(G) f ∗ g ∈ L ( G )
( f ∗ g ) ( m ) = ∑ k = 0 N − 1 a m − k b k
(f* g)(m)=\sum_{k=0}^{N-1}a_{m-k}b_k
( f ∗ g ) ( m ) = k = 0 ∑ N − 1 a m − k b k 0 ≤ m ≤ deg f + deg g 0\le m\le \deg f+\deg g 0 ≤ m ≤ deg f + deg g ( f ∗ g ) ( m ) (f * g)(m) ( f ∗ g ) ( m ) m m m f ( x ) g ( x ) f(x)g(x) f ( x ) g ( x ) f g fg f g f ∗ g f*g f ∗ g
ここでフーリエ変換が f ∗ g ^ = f ^ ⋅ g ^ \widehat{f*g}=\widehat{f}\cdot \widehat{g} f ∗ g = f ⋅ g O ( N ) O(N) O ( N )
f , g f,g f , g f ^ , g ^ \widehat{f},\widehat{g} f , g 各点積 f ^ ⋅ g ^ \widehat{f}\cdot\widehat{g} f ⋅ g
これは f ∗ g ^ \widehat{f * g} f ∗ g f ∗ g f*g f ∗ g
ここで問題となるのが、フーリエ係数 ( f ^ ( 0 ) , … , f ^ ( N − 1 ) ) (\widehat{f}(0),\ldots,\widehat{f}(N-1)) ( f ( 0 ) , … , f ( N − 1 )) O ( N 2 ) O(N^2) O ( N 2 )
高速フーリエ変換
#
一般の有限アーベル群 G = { g 1 , g 2 , … , g n } G=\{g_1,g_2,\ldots,g_n\} G = { g 1 , g 2 , … , g n }
f ^ ( g i ) = n ⟨ χ i , f ⟩ = ∑ g ∈ G χ i ( g ) ‾ f ( g )
\widehat{f}(g_i)=n\langle \chi_i,f\rangle=\sum_{g\in G}\overline{\chi_i(g)}f(g)
f ( g i ) = n ⟨ χ i , f ⟩ = g ∈ G ∑ χ i ( g ) f ( g ) を考えます。ここで、H H H G G G G = t 1 H ∪ t 2 H ∪ ⋯ ∪ t m H G=t_1H\cup t_2H\cup\cdots\cup t_mH G = t 1 H ∪ t 2 H ∪ ⋯ ∪ t m H G G G g = t j h ( 1 ≤ j ≤ m , h ∈ H ) g=t_jh \ (1\le j\le m, h\in H) g = t j h ( 1 ≤ j ≤ m , h ∈ H )
f ^ ( g i ) = ∑ j = 1 m ∑ h ∈ H χ i ( t j h ) ‾ f ( t j h ) = ∑ j = 1 m χ i ( t j ) ‾ ∑ h ∈ H χ i ( h ) ‾ f ( t j h )
\widehat{f}(g_i)=\sum_{j=1}^m\sum_{h\in H}\overline{\chi_i(t_jh)}f(t_jh)=\sum_{j=1}^m\overline{\chi_i(t_j)}\sum_{h\in H}\overline{\chi_i(h)}f(t_jh)
f ( g i ) = j = 1 ∑ m h ∈ H ∑ χ i ( t j h ) f ( t j h ) = j = 1 ∑ m χ i ( t j ) h ∈ H ∑ χ i ( h ) f ( t j h ) この式の内側の総和は、H H H G G G H H H H H H
部分群 H H H
剰余類について総和を求める。
H H H G ≥ G 1 ≥ G 2 ≥ ⋯ ≥ { 1 } G\ge G_1\ge G_2\ge\cdots\ge \{1\} G ≥ G 1 ≥ G 2 ≥ ⋯ ≥ { 1 }
離散フーリエ変換で考えましょう。特に 2 べきの場合を考えます。G = Z / 2 N Z G=\mathbb{Z}/2N\mathbb{Z} G = Z /2 N Z N N N H H H 2 Z / 2 N Z ≅ Z / N Z 2\mathbb{Z}/2N\mathbb{Z}\cong \mathbb{Z}/N\mathbb{Z} 2 Z /2 N Z ≅ Z / N Z G / H G/H G / H 2 2 2 0 0 0 2 N − 1 2N-1 2 N − 1 m m m m = 2 a + r ( 0 ≤ a ≤ N − 1 , 0 ≤ r ≤ 1 ) m=2a+r \ (0\le a\le N-1, 0\le r\le 1) m = 2 a + r ( 0 ≤ a ≤ N − 1 , 0 ≤ r ≤ 1 )
f ^ ( k ) = ∑ m = 0 2 N − 1 e − 2 π i k m / 2 N f ( m ) = ∑ r = 0 1 e − 2 π i k r / 2 N ∑ a = 0 N − 1 e − 2 π i k 2 a / 2 N f ( 2 a + r ) = ∑ a = 0 N − 1 e − 2 π i k a / N f ( 2 a ) + e − 2 π i k / 2 N ∑ a = 0 N − 1 e − 2 π i k a / N f ( 2 a + 1 )
\begin{align*}
\widehat{f}(k) &= \sum_{m=0}^{2N-1}e^{-2\pi ikm/2N}f(m) \\
&= \sum_{r=0}^1e^{-2\pi ikr/2N}\sum_{a=0}^{N-1}e^{-2\pi ik2a/2N}f(2a+r) \\
&= \sum_{a=0}^{N-1}e^{-2\pi ika/N}f(2a)+e^{-2\pi ik/2N}\sum_{a=0}^{N-1}e^{-2\pi ika/N}f(2a+1)
\end{align*}
f ( k ) = m = 0 ∑ 2 N − 1 e − 2 πikm /2 N f ( m ) = r = 0 ∑ 1 e − 2 πik r /2 N a = 0 ∑ N − 1 e − 2 πik 2 a /2 N f ( 2 a + r ) = a = 0 ∑ N − 1 e − 2 πika / N f ( 2 a ) + e − 2 πik /2 N a = 0 ∑ N − 1 e − 2 πika / N f ( 2 a + 1 ) となります。G = Z / 2 N Z G=\mathbb{Z}/2N\mathbb{Z} G = Z /2 N Z H ≅ Z / N Z H\cong\mathbb{Z}/N\mathbb{Z} H ≅ Z / N Z H H H
この方法により、Z / N Z \mathbb{Z}/N\mathbb{Z} Z / N Z O ( N log N ) O(N\log N) O ( N log N ) N = ∏ p i N=\prod p_i N = ∏ p i Z / N Z \mathbb{Z}/N\mathbb{Z} Z / N Z O ( N ∑ p i ) O(N\sum p_i) O ( N ∑ p i )
改めて多項式の積の求め方を書きます。f = ∑ a m x m , g = ∑ b m x m f=\sum a_mx^m, g=\sum b_mx^m f = ∑ a m x m , g = ∑ b m x m N > deg f + deg g N>\deg f+\deg g N > deg f + deg g N N N a , b a,b a , b a ^ , b ^ \widehat{a},\widehat{b} a , b a ^ ⋅ b ^ \widehat{a}\cdot \widehat{b} a ⋅ b a ∗ b ^ \widehat{a * b} a ∗ b a ∗ b a*b a ∗ b f g fg f g
実装したものがこちらになります。(Kotlin 言語)
https://atcoder.jp/contests/atc001/submissions/24183589
高速フーリエ変換の工夫の部分
#
上のコードは再帰で実装していますが、非再帰で実装することもでき、(検証していませんが) 速くなるようです。高速フーリエ変換のアルゴリズムにはいくつかの種類があり、AtCoder の解説でも触れられています。
おまけ
#
非アーベル群上のフーリエ変換
#
アーベル群とは限らない有限群 G G G φ ( 1 ) , … , φ ( s ) \varphi^{(1)},\ldots,\varphi^{(s)} φ ( 1 ) , … , φ ( s ) G G G φ g ( k ) \varphi_g^{(k)} φ g ( k ) φ g ( k ) = ( φ i j ( k ) ( g ) ) \varphi_g^{(k)}=(\varphi_{ij}^{(k)}(g)) φ g ( k ) = ( φ ij ( k ) ( g )) φ i j ( k ) : G → C \varphi_{ij}^{(k)}\colon G\to\mathbb{C} φ ij ( k ) : G → C φ ( k ) \varphi^{(k)} φ ( k ) d k d_k d k d k φ i j ( k ) \sqrt{d_k}\varphi_{ij}^{(k)} d k φ ij ( k ) L ( G ) L(G) L ( G )
M d ( C ) M_d(\mathbb{C}) M d ( C ) d d d d d d φ \varphi φ f ∈ L ( G ) f\in L(G) f ∈ L ( G ) f ^ ( φ ) ∈ M d ( C ) \widehat{f}(\varphi)\in M_{d}(\mathbb{C}) f ( φ ) ∈ M d ( C )
f ^ ( φ ) = ∑ g ∈ G φ ( g ) ‾ f ( g )
\widehat{f}(\varphi)=\sum_{g\in G}\overline{\varphi(g)}f(g)
f ( φ ) = g ∈ G ∑ φ ( g ) f ( g ) により定め、写像 T : L ( G ) → M d 1 ( C ) × ⋯ × M d s ( C ) T\colon L(G)\to M_{d_1}(\mathbb{C})\times\cdots\times M_{d_s}(\mathbb{C}) T : L ( G ) → M d 1 ( C ) × ⋯ × M d s ( C ) T f = ( f ^ ( φ ( 1 ) ) , … , f ^ ( φ ( s ) ) ) Tf=(\widehat{f}(\varphi^{(1)}),\ldots,\widehat{f}(\varphi^{(s)})) T f = ( f ( φ ( 1 ) ) , … , f ( φ ( s ) ))
f = 1 n ∑ i , j , k d k f ^ ( φ ( k ) ) i j φ i j ( k )
f=\frac{1}{n}\sum_{i,j,k}d_k\widehat{f}(\varphi^{(k)}) _ {ij}\varphi_{ij}^{(k)}
f = n 1 i , j , k ∑ d k f ( φ ( k ) ) ij φ ij ( k ) となります。アーベル群の場合には畳み込み積は各点積と対応していましたが、一般には次の定理のようになります。
定理 (Wedderburn) : T : L ( G ) → M d 1 ( C ) × ⋯ × M d s ( C ) T\colon L(G)\to M_{d_1}(\mathbb{C})\times\cdots\times M_{d_s}(\mathbb{C}) T : L ( G ) → M d 1 ( C ) × ⋯ × M d s ( C ) L ( G ) L(G) L ( G )
R \mathbb{R} R
#
無限群のフーリエ変換を考えるには、有限和だった部分を無限和にしなければなりません。R \mathbb{R} R
関数 f , g : R → C f,g\colon \mathbb{R}\to\mathbb{C} f , g : R → C
( f ∗ g ) ( x ) = ∫ − ∞ ∞ f ( x − y ) g ( y ) d y
(f * g)(x)=\int_{-\infty}^{\infty}f(x-y)g(y)dy
( f ∗ g ) ( x ) = ∫ − ∞ ∞ f ( x − y ) g ( y ) d y フーリエ変換は
f ^ ( x ) = ∫ − ∞ ∞ e − 2 π i x t f ( t ) d t
\widehat{f}(x)=\int_{-\infty}^{\infty}e^{-2\pi ixt}f(t)dt
f ( x ) = ∫ − ∞ ∞ e − 2 πi x t f ( t ) d t となります。フーリエ逆変換は
f ( x ) = ∫ − ∞ ∞ e 2 π i x t f ^ ( t ) d t
f(x)=\int_{-\infty}^{\infty}e^{2\pi ixt}\widehat{f}(t)dt
f ( x ) = ∫ − ∞ ∞ e 2 πi x t f ( t ) d t となります。この場合にも、f ∗ g ^ = f ^ ⋅ g ^ \widehat{f*g}=\widehat{f}\cdot\widehat{g} f ∗ g = f ⋅ g
元々は R \mathbb{R} R
高速フーリエ変換
#
Cooley-Tukey のアルゴリズムは有限群に一般化することができます。これは Diaconis, Rockmore の論文で述べられています。
有限アーベル群の場合と同様に、部分群に関するフーリエ変換と剰余類に関する和に分解することができますが、1 つ注意しなければならないことがあります。φ \varphi φ G G G H H H H H H H H H
G G G H H H G = t 1 H ∪ ⋯ ∪ t m H G=t_1H\cup\cdots\cup t_mH G = t 1 H ∪ ⋯ ∪ t m H 各 t j t_j t j H H H
行列をかけて j = 1 , 2 , … , m j=1,2,\ldots,m j = 1 , 2 , … , m
任意の有限群 G G G c c c O ( ∣ G ∣ log c ∣ G ∣ ) O(|G|\log^c |G|) O ( ∣ G ∣ log c ∣ G ∣ )
参考文献・おすすめの本など
#
表現論やフーリエ変換に関係する本を紹介します。すべての本を知っているわけではないのでご了承ください。
Steinberg, Benjamin. Representation theory of finite groups: an introductory approach. Springer Science & Business Media, 2011.
有限群の表現論の基礎がまとまっています。英語の本ですが、表現論が初めてという人にもおすすめできると思います。ただし線形代数と群論はある程度知っている必要があります。この記事のうち高速フーリエ変換以外の部分について大いに参考にしました。
平井武, 線型代数と群の表現 I, II. すうがくぶっくす 20, 21, 朝倉書店.
日本語の本で初心者におすすめできそうなのはこの本だと思っています (持っていないので大声でおすすめできませんが……)。線形代数・群論・表現論を扱っているようです。
河添健, 群上の調和解析, すうがくの風景1, 朝倉書店, 2000.
表現論とフーリエ変換を扱っています。元気な高校生なら十分チャレンジできる！とありますが本当でしょうか。
エリアス・M. スタイン ラミ・シャカルチ, フーリエ解析入門, 日本評論社, 2007
プリンストン解析学講義シリーズの最初の巻で、主に R \mathbb{R} R
Cooley, James W., and John W. Tukey. “An algorithm for the machine calculation of complex Fourier series.” Mathematics of computation 19.90 (1965): 297-301.
Diaconis, Persi, and Daniel Rockmore. “Efficient computation of the Fourier transform on finite groups.” Journal of the American Mathematical Society 3.2 (1990): 297-332.
Cooley-Tukey のアルゴリズムを一般の有限群に拡張した論文です。
