趣旨
競技プログラミングでは非常に多くの畳み込みとゲルファント変換が登場するのですが、ゲルファント変換という名称が競技プログラミング界隈ではあまり有名ではないようなので簡素な解説を書いてみます。どうせ$n$番煎じかもしれませんが、現状としてあまり有名でない以上はまだまだこういう記事が増えることで調べ物の助けになる人もいるかと思いますので、あまり気にせず書いてみることにします。毎回ネタを思いついてはどうせ$n$番煎じと思ってやめちゃうのですが、たまには許してもらえますよね。
まず競技プログラマーなら以下の用語に聞き覚えがある人も多いのではないでしょうか？
- 累積和
- 部分集合上のゼータ変換
- 約数ゼータ変換
- 倍数ゼータ変換
- 離散フーリエ変換（DFT）
- アダマール変換
これらは全部ゲルファント変換です。それぞれの原理を一々別個に勉強した覚えのある人も多いのではないでしょうか？ ゲルファント変換を知っても新たな問題が解けるようになるわけではないですが、個々のゲルファント変換に対して原理を勉強し直すコストを削減できるというメリットがあるので、今から色々な概念を勉強したいと思う人におすすめの内容です。
ただし共通化できるのはあくまで原理の理解だけです。それぞれ高速化の仕方が違うため、実装は個別に勉強しましょう。それを踏まえて、それぞれの高速化はゲルファント変換の高速化として原理を理解すると良いでしょう。
例えば
- 高速フーリエ変換（FFT／NTT）
- 高速ゼータ変換
- 高速アダマール変換
はゲルファント変換の高速化という見方をすることができるというわけです。
準備
まずは畳み込みとは何なのかを説明します。FFTとセットで出てきやすい用語なのでFFTを勉強する前はFFTやDFTのことと混同しているパターンがありがちだと思うので、混乱を根底から払拭するために用語をきちんと導入していきます。
可換環
例と反例の説明だけします。可換環を知っている人はこの章を飛ばしてください。
集合$R$とその上の二項演算$\oplus$と$\otimes$の組$(R,\oplus,\otimes)$であって適当な条件を満たすものを可換環と呼び、演算$\oplus$と$\otimes$に曖昧さのない文脈ではしばしば底集合$R$そのもので略されます。ここでは可換環と言ったら単位的なものだけを指します。以下は全て可換環です。
- 零環：要素数$1$の集合$O$と、その上の一意な二項演算$\oplus = \otimes$の組
- 整数環$\mathbb{Z}$：整数全体の集合$\mathbb{Z}$と、整数の通常の加法$+$と、整数の通常の乗算$\times$の組
- 実数体$\mathbb{R}$：実数全体の集合$\mathbb{R}$と、実数の通常の加法$+$と、実数の通常の乗算$\times$の組
- 整域（可換環の中で特別なもの）$R$に対する商体$\textrm{Frac}(R)$：$R$係数分数全体の集合$\textrm{Frac}(R)$と、$R$係数分数の通常の加法$+$と、$R$係数分数の通常の乗算$\times$の組
- 特に有理数体$\mathbb{Q} = \textrm{Frac}(\mathbb{Z})$：有理数全体の集合$\mathbb{Q}$と、有理数の通常の加法$+$と、有理数の通常の乗算$\times$の組
- 可換環$R$に対する$R$係数多項式環$R[X]$：$R$係数多項式全体の集合$R[X]$と、$R$係数多項式の通常の加法$+$と、$R$係数多項式の通常の乗算$\times$の組
- 特に$2$以上の整数$n$に対する$R$係数$n$変数多項式環$R[X_1,\ldots,X_n] = R[X_1,\ldots,X_{n-1}][X_n]$
- 可換環$R$に対する$R$係数形式冪級数環$R[[X]]$：$R$係数形式冪級数全体の集合$R[[X]$と、$R$係数形式冪級数の通常の加法$+$と、$R$係数形式冪級数の通常の乗算$\times$の組
- 特に$2$以上の整数$n$に対する$R$係数$n$変数形式冪級数環$R[X_1,\ldots,X_n] = R[X_1,\ldots,X_{n-1}][X_n]$
- 可換環$R$とそのイデアル$I$に対する剰余環$R/I$：法$I$剰余類全体の集合$R/I$と、法$I$剰余類の通常の加法$+$と、法$I$剰余類の通常の積$\times$の組
- 特に正整数$B$に対する剰余環$\mathbb{Z}/B \mathbb{Z}$：法$B$整数全体の集合$\mathbb{Z}/B \mathbb{Z}$と、法$B$整数の通常の加法$+$と、法$B$整数の通常の乗算$\times$の組
- 特に素数$p$に対する有限体$\mathbb{F}_p = \mathbb{Z}/p \mathbb{Z}$
- 特に可換環$R$と正整数$D$に対する$D$次打ち切りの$R$係数多項式環$R[X]/X^D R[X]$
- 特にガウス整数環$\mathbb{Z}[i] = \mathbb{Z}[X]/(X^2-1) \mathbb{Z}[X]$
- 特にガウス数体$\mathbb{Q}[i] = \mathbb{Q}[X]/(X^2-1) \mathbb{Q}[X]$
- 特に複素数体$\mathbb{C} = \mathbb{R}[X]/(X^2-1) \mathbb{R}[X]$
- 特に正整数$B$に対する剰余環$\mathbb{Z}/B \mathbb{Z}$：法$B$整数全体の集合$\mathbb{Z}/B \mathbb{Z}$と、法$B$整数の通常の加法$+$と、法$B$整数の通常の乗算$\times$の組
一方で以下は可換環ではありません。
- 空集合双マグマ$\emptyset$：空集合$\emptyset$と、その上の一意な二項演算$\oplus = \otimes$の組
- 自然数半環$\mathbb{N}$：非負整数全体の集合$\mathbb{N}$と、非負整数の通常の加法$+$と、非負整数の通常の乗法$\times$の組
- 零環でない可換環$R$と$2$以上の整数$n$に対する$R$係数$n$次行列環$\textrm{M}_n(R)$：$R$係数$n$次正方行列全体$\textrm{M}_n(R)$と、$R$係数$n$次正方行列の通常の加法$+$と、$R$係数$n$次正方行列の通常の乗法$\times$の組
これで可換環がどんなものか、定義はさておき競技プログラミングで現れる対象に対してはだいたい掴めてきましたね。畳み込みにおいて重要な登場人物は可換環ともう1人、モノイドです。
モノイド
例と反例の説明だけします。モノイドを知っている人はこの章を飛ばしてください。
集合$M$とその上の二項演算$\odot$の組$(M,\odot)$であって適当な条件を満たすものをモノイドと呼び、演算$\odot$に曖昧さのない文脈ではしばしば底集合$M$そのものに略されます。以下は全てモノイドです。
- 半環（可換環を一般化した概念）$(R,\oplus,\otimes)$に対する、加法モノイド$(R,\oplus)$と乗法モノイド$(R,\otimes)$
- 特に可換環$R$の加法群と乗法モノイド
- 特に正整数$B$に対する$\mathbb{Z}/B \mathbb{B}$の加法群と乗法モノイド
- 特に$\mathbb{F}_2$の加法群と乗法モノイド
- 特に$\{0,1\}$のXOR群とANDモノイド
- 特に$\{0,1\}$のNXOR（等号演算子）群とORモノイド
- 特に$\mathbb{F}_2$の加法群と乗法モノイド
- 特に正整数$B$に対する$\mathbb{Z}/B \mathbb{B}$の加法群と乗法モノイド
- 特に自然数半環$\mathbb{N}$の加法モノイドと乗法モノイド
- 特に最小元と引数$2$の$\max$が定義される半順序集合$(P,\leq)$に対する$\max$モノイド
- 特に$L \leq R$を満たす整数$L,R$に対する閉区間$\mathbb{Z} \cap [L,R]$の$\max$モノイドと$\min$モノイド
- 特に非負整数の$\textrm{gcd}$モノイドと$\textrm{lcm}$モノイド
- 特に集合$S$の部分集合の$\cup$モノイドと$\cap$モノイド
- 特に可換環$R$の加法群と乗法モノイド
- 集合$X$に対する自己写像モノイド$\textrm{End}(X)$：写像$X \to X$全体の集合$\textrm{End}(X)$と、その上の合成演算$\circ$の組
- モノイド$(M,\odot)$の逆モノイド$(M,\odot)^{\textrm{op}}$：$M$とその上の二項演算$m_0 \odot^{\textrm{op}} m_1 = m_1 \odot m_0$
- モノイド$M_1$と$M_2$に対する直積モノイド$M_1 \times M_2$：$M_1$の要素と$M_2$の要素の組全体の集合$M_1 \times M_2$と、その上の通常の二項演算の組
- 特にモノイド$M$と非負整数$n$に対する直積モノイド$M^n$
- 特に$\{0,1\}^{32}$や$\{0,1\}^{64}$の各点XOR群と各点ANDモノイド
- 特に$32$bit整数や$64$bit整数のbitwise XOR群とbitwise ANDモノイド
- 特に$\{0,1\}^{32}$や$\{0,1\}^{64}$の各点NXOR群と各点ORモノイド
- 特に$32$bit整数や$64$bit整数のbitwise NXOR群とbitwise ANDモノイド
- 特に$\{0,1\}^{32}$や$\{0,1\}^{64}$の各点XOR群と各点ANDモノイド
- 特にモノイド$M$と非負整数$n$に対する直積モノイド$M^n$
- 半群（モノイドを一般化した概念）$(M,\odot)$と$M$に属さない元$\ast$（例えば$M \notin M$なので$\ast = M$を考えれば良い）に対する、$\ast$による$(M,\odot)$の単位化：$M \cup \{\ast\}$と、その上の$\ast$を単位元とする$\odot$の一意な拡張の組
- 小圏（モノイドを一般化した概念）$C$と$\textrm{Ob}(C)$に属さない元$\ast$（例えば$\textrm{Ob}(C) \notin \textrm{Ob}(C)$なので$\ast = \textrm{Ob}(C)$を考えれば良い）に対する、$\ast$による$C$のMaybeモナド化：$\textrm{Ob}(C) \cup \{\ast\}$と、$C$の合成の定義域外の演算結果を$\ast$として一意に拡張したその上の二項演算の組
一方で以下はモノイドではありません。
- 空集合半群$\emptyset$：空集合$\emptyset$と、その上の一意な二項演算$\oplus$の組
- 要素数が$1$でない集合$X$に対する、左引数返しのマグマ$X$：$X$と、その上の二項演算$x_0 \triangleleft x_1 = x_0$の組
- 要素数$3$以上の集合$X$と$x \in X$に対する、$x$返しのマグマ$X$：$X$と、その上の二項演算$x_0 \odot x_1 = x$の組
従ってこれらはセグメント木（特に遅延セグメント木の作用される側）の要件に反するため、乗せた時の挙動は実装依存なので気をつけましょう。
これでモノイドがどんなものか、定義はさておき競技プログラミングで現れる対象に対してはだいたい掴めてきましたね。それでは畳み込みに移ります。
畳み込み
定義の説明だけします。群環を知っている人はこの章を飛ばしてください。
測度論を使うと無限和を伴う畳み込みを扱うこともできますが、ここでは話を簡単にするために有限和のみを伴う畳み込みについて説明します。
また$2$変数以上の畳み込みが隣接代数などの分野で現れますが、ここでは詳しく触れないことにします。後で$\max$畳み込みの章の最後に知っている人向けの説明だけします。
集合$N,R$と写像$a \colon N \to R$と$n \in N$に対し、$a(n)$をここでは$a_n$と書き表し、$a$の第$n$成分と呼びます。$a$を$(a_n)_{n \in N}$とも書き表します。こう書くと写像が配列の一般化であることが分かりやすいですね。写像$a \colon N \to R$全体の集合を$R^N$と書き表します。
$N$を集合とし、$(R,\oplus,\otimes)$を可換環とし、$R$の加法に関する単位元を$0$と書き表します。写像$a \colon N \to R$が$N$を添え字集合に持つ$R$係数形式的有限和であるとは、$a$の成分が有限個を除いて$0$であるということ、すなわち$\{n \in N \mid a_n \neq 0\}$が有限集合であるということです。$N$を添字集合に持つ$R$係数形式的有限和全体の集合を$R^{\oplus N}$と書き表します。あわわ記号が衝突しました。$R$の肩に乗っている$\oplus$は$R$の加法と関係がなく、代数学や圏論などの文脈で標準的に使われる記号です。
$R$が零環であるかまたは$N$が有限集合である時$R^{\oplus N} = R^N$であり、そうでない時$R^{\oplus N} \subsetneq R^N$です。$R^{\oplus N}$と$R^N$は各点和に関して可換群をなします。各点積に関しては可換モノイドをなし、$R^N$は各点和と各点積に関して可換環をなしますが、$R^{\oplus N} \subsetneq R^N$の時は$R^{\oplus N}$が単位的でないので可換環をなしません。
ここで$N$が特にモノイド$(M,\odot)$の底集合$M$である場合を考えます。この時、$R^{\oplus M}$には$\odot$を用いて次の二項演算が定義されます。
\[ \begin{array}{rcl} \displaystyle R^{\oplus M} \times R^{\oplus M} &\displaystyle \to &\displaystyle R^{\oplus M} \\
(a,b) &\displaystyle \mapsto &\displaystyle \left( \bigoplus_{i \odot j = k} a_i \otimes b_j \right)_{k \in M} \end{array} \]
ただし右辺の$\bigoplus_{i \odot j = k} a_i \otimes b_j$は$i \odot j = k$を満たす$(i,j) \in M^2$をわたる$a_i \otimes b_j$の$\oplus$に関する総和を表します。この総和は有限個を除く全ての$(i,j)$に対して$0$であり、本質的有限和と呼ばれます。本質的有限和は可換モノイド演算に対していつでも定義されるので、特に$\oplus$に対しても定義されます。競技プログラミングだと問題文に「総bitwise XORとは」みたいな注釈が入りがちですが、あれを一般化させたものが本質的有限和です。
ここで定義した新たな二項演算を、$R^{\oplus M}$上の（$\oplus,\otimes,\odot$に関する）畳み込み積と呼びます。
嬉しいことに、$R^{\oplus M}$は各点和と畳み込み積に関して可換とは限らない環の構造をなします。この構造を強調する際は、$R^{\oplus M}$を$R[M]$と表記して$M$の$R$上のモノイド環と呼びます。$M$が群の時は特に$M$の$R$上の群環と呼ばれます。
そして$(M,\odot)$が可換性を満たすならば、$R[M]$は可換環となります。この可換環は便利なので、その畳み込み積を計算したい気持ちになる人が多く観測されます。
$a,b \in R[M]$の畳み込み積の計算量は、定義通りに愚直に行うと何かしらの$2$乗のオーダーが掛かりがちで、競技プログラミングにおいては高速化が問われるところです。
演算の高速化の手法として競技プログラミングで頻出なのが、準同型による高速化です。準同型も頻出とはいえあまり用語そのものが競技プログラミング界隈で有名ではなさそうなので、こちらも解説しておきます。
ところで競技プログラミングって様々な数学概念が頻出ですが、解説では概念名に触れずにその問題そのものの具体的な説明だったり具体的な類題を引き合いに出したりが多いがちなので、writerさんたちが背景に念頭に置いてそうな抽象的な概念があまり共有知とされていなさそうな予感がしています。
準同型
定義と例だけ説明します。準同型を知っている人はこの章を飛ばしてください。
以下モノイドの演算と単位元は全部$\cdot$と$e$で書き表します。$M$と$N$をモノイドとします。モノイド準同型$M \to N$とは、写像$f \colon M \to N$であって以下を満たすもののことです。
- $f(e) = e$
- $\forall (i,j) \in M^2, f(i \cdot j) = f(i) \cdot f(j)$
ここで1の左辺の$e$は$M$の単位元、右辺の$e$は$N$の単位元であり、2の左辺の$\cdot$は$M$の演算、右辺の$\cdot$は$N$の演算であることに注意しましょう。代数学においてこのような記号の濫用（演算子のオーバーロード的なもの）は曖昧さの生じない範囲で（つまり記載された式から著者の意図した型が容易に推測できる範囲で）慣例的に行われます。
モノイド準同型の典型例は、行列式や置換の符号（転倒数が奇数なら$-1$、偶数なら$1$）です。どちらも便利ですね。
さて、2の左辺と右辺で考慮している演算が異なるということは、その計算量も異なるかもしれないということです。$M$の演算$i \cdot j$の計算が愚直には遅いけど高速に処理したいとして、もし
- $f(i) \cdot f(j)$の計算
- その計算結果と等しい値である$f(i \cdot j)$から$i \cdot j$の復元
が高速に可能であるならば、これで$i \cdot j$の計算の高速化が成功できたことになります。
見覚えありませんか？ 高速フーリエ変換、高速ゼータ変換、高速アダマール変換、全部これですね。他にも行列累乗の行列式を行列式の累乗に帰着させたり、置換の反復合成の符号を符号の累乗に帰着させたり。競技プログラミングにおける高速化の手法の様々なところに準同型が応用されています。
準同型はモノイドだけでなく可換環にも定義できます。以下可換環の加法と乗法と乗法的単位元は全部$+$と$\times$と$1$で書き表します。$R$と$A$を可換環とします。環準同型$R \to A$とは、写像$f \colon R \to A$であって以下を満たすもののことです。
- $f(1) = 1$
- $\forall (r_0,r_1) \in R^2, f(r_0 + r_1) = f(r_0) + f(r_1)$
- $\forall (r_0,r_1) \in R^2, f(r_0 \times r_1) = f(r_0) \times f(r_1)$
モノイドより可換環の方が構造が豊かである分、使える道具も増えます。実際、可換環には体という非常に性質の良い可換環たちの直積環への標準的な環準同型があり、体たちの直積環は各点で異なる体に値を持ちうる関数の空間でもあるので、可換環の演算と関数の演算を結ぶことが可能になります。この標準的な環準同型が、ゲルファント変換です。いよいよ本題に入ります。
本題
いよいよ本題です。ゲルファント変換について説明します。ゲルファント変換を知っている人はこの記事を飛ばしてください。
可換環の例で少し触れましたが、可換環にはイデアルという非負整数の一般化が定義されます。イデアルの中でも$0$と素数の一般化である素イデアルが重要で、可換環論や代数幾何、整数論や数論幾何で盛んに研究されています。
ゲルファント変換は素イデアルを使って定式化することのできる概念です。まずは素イデアルを使ってゲルファント変換を説明し、その後で素イデアルを知らない人向けにゲルファント変換を座標変換の言葉で説明し直します。
素イデアルとゲルファント変換
イデアルが何なのかはさておき、可換環$R$とそのイデアル$I$が与えられると、法$I$の剰余類の環$R/I$が定義されます。特に$I$が素イデアル$P$である時、この剰余環$R/P$は整域と呼ばれる特別な環であることが知られています。そして既に説明したように（？）整域には商体が定義され、整域$R/P$は商体$\textrm{Frac}(R/P)$の部分集合と自然に同一視できます。
というわけで、$R$の素イデアル$P$を１つ固定するごとに、環準同型$R \twoheadrightarrow R/P \hookrightarrow \textrm{Frac}(R/P)$が定義されます。これは$R$から体への環準同型です。$R$の素イデアル$P$全体の集合$\textrm{Spec}(R)$をわたる体$\textrm{Frac}(R/P)$の直積環$\prod_{P \in \textrm{Spec}(R)} \textrm{Frac}(R/P)$を$\Gamma(R)$と置くと、直積の普遍性という性質から環準同型$R \to \Gamma(R)$が得られます。これがゲルファント変換です。ゲルファント変換を明示的に書き下すと以下のような式になります。
\[ \begin{array}{rcl} \displaystyle R &\displaystyle \to &\displaystyle \Gamma(R) = \prod_{P \in \textrm{Spec}(R)} \textrm{Frac}(R/P) \\
f &\displaystyle \mapsto &\displaystyle \left( f(P) \right)_{P \in \textrm{Spec}(R)} \end{array} \]
ただし$f(P)$は$f$の法$P$剰余類$f + P \in R/P$の$\textrm{Frac}(R/P)$での像です。こう書くと$R$の要素がまるで関数のように見えるため、関数のように物事を見たい人たちに好まれます。
なお実際には素イデアル全体$\textrm{Spec}(R)$でなく目的に応じて十分多くの素イデアルを選んで考えたりします。例えば極大イデアル全体$\textrm{Max}(R)$に絞ったバージョンや、位相を考慮したバージョンをゲルファント変換と呼ぶこともあります。実際ゲルファント変換の大元にある$C^*$環論という分野では極大イデアル全体$\textrm{Max}(R)$に絞ったバージョンが使われていたので、そちらの方が由緒正しい用語法だと思います。
さて、ゲルファント変換を導入してみたものの、素イデアルが何者なのか分からないとこれではよく分かりませんね。次に素イデアル使わない説明をしていきましょう。
座標変換とゲルファント変換
実は可換環$R$の素イデアルというのは$R$から体への環準同型の核（$0$に写るもの全体）と等価な概念です。そこで、目的に応じて十分多くの$R$の素イデアル$P$に対する標準的な環準同型$R \to \textrm{Frac}(R/P)$を考える代わりに、目的に応じて十分多くの$R$から体への環準同型を考えると良いです。
競技プログラミングの文脈に特化させるため、$K$を体（例えば$\mathbb{Q},\mathbb{R},\mathbb{C},\mathbb{F}_p$）とし、$N$を正整数とし、長さ$N$の$K$係数配列全体の空間$K^N$を考えます。
$K^N$には各点和$+$と$K$上スカラー倍$\cdot$が定義されますが、その乗法構造は各点積だったり$N$元集合の何かしらのモノイド演算$\cdot$由来の畳み込みだったり、様々なものが考えられます。
各点積であれば、$N$回の$K$の乗法で処理できるので十分高速ですね。問題は畳み込みなどの、各点積とは異なる乗法$\times$が与えられている場合です。ここで仮定として、$(K^N,+,\times)$が可換環をなすことと、$\times$が$\cdot$と整合的であることを課します。
さて$K^N$から$K$への$K$線形写像を考えることと、何か１つ$K^N$の元$v$を固定して$v$と標準内積を取ることは等価です。つまり$K^N$は自身の双対線形空間と同型です。この翻訳のもとで、環$(K^N,+,\times)$から体$K$への$K$線形な環準同型を探すには、$K^N$の元$v$であって適切な関係式を満たすものを見つければ良いことになります。
そのような$v$を$K^N$の基底をなすように$N$個見つけられたとして、それぞれ$v_1,v_2,\ldots,v_N$と置きましょう。つまり$v_1,v_2,\ldots,v_N$は$K^N$の基底であって、$N$以下の任意の正整数$i$に対し$v_i$との内積$K^N \to K$が$K^N$の与えられた乗法$\times$に関して環準同型であるものということです。
$v_1,v_2,\ldots,v_N$が基底をなすということは、$v_1,v_2,\ldots,v_N$による内積が座標変換$K^N \to K^N$を与えるということで、この逆変換は行列$(v_1 \ v_2 \ \cdots \ v_N)$の転置の逆行列を左から掛けることで実現できます。つまり、$K^N$での非自明な乗法$a \times b$を計算するためには、それを内積で変換した
\[ ((a \times b)\cdot v_1,(a \times b)\cdot v_2,\ldots,(a \times b)\cdot v_N) \in K^N \]
を計算して、逆変換すればよいです。ここで$v_1,v_2,\ldots,v_N$との内積で得られる$N$個の$K$線形写像$K^N \to K$たちがいずれも環準同型であることを先程課したので、その条件から、
\[ ((a \times b)\cdot v_1,(a \times b)\cdot v_2,\ldots,(a \times b)\cdot v_N) = ((a \cdot v_1)(b \cdot v_1),(a \cdot v_2)(b \cdot v_2), \ldots, (a \cdot v_N)(b \cdot v_N)) \]
が成り立ちます。従ってこの左辺を求めるには、$a$と$b$を内積で変換したものの各点積である右辺を求めれば良いです。無事座標変換により$\times$を各点積に帰着できました。
というわけで、配列の空間の$K$線形空間構造と整合的な演算を考えている今回の状況では、$K^N$の乗法$\times$を計算するためにゲルファント変換をするということは単に、「$K^N$の基底$v_1,v_2,\ldots,v_N$であって、$N$以下の任意の正整数$i$に対し$v_i$との内積$K^N \to K$が環準同型であるもの」を探してこの基底との内積による座標変換と逆変換を考えるということに過ぎないというわけです。
では実際に、$K^N$の色々な乗法$\times$に対して上の意味でゲルファント変換に対応する座標変換を見てみましょう。
各点積の場合
$\times$が最初から各点積である場合、何もする必要がありません。つまり$v_1,v_2,\ldots,v_N$は標準基底として良く、それとの内積による座標変換は恒等変換です。
この場合の素イデアルは各成分（を取り出す射影の核）にそのまま対応するので、ゲルファント変換自体も$a \in K^N$を$(a_n)_{n=0}^{N-1}$に送る写像、すなわち恒等写像と同一視されます。
ちなみに$0$-indexedにした理由は、写像全体の集合を表す記法と直積の記法$K^N$の整合性を取るためです。集合論においては$N = \mathbb{N} \cap [0,N)$が成り立つように自然数概念が定式化されるため、$K^N$は写像$\mathbb{N} \cap [0,N) \to K$全体の集合として定式化されていることになります。この辺は好みで自由に定式化を変えてよいですが、整合的であればあるほど整合的である喜びを噛みしめることができます。
可換群演算に関する畳み込みの場合
$G$を要素数$N$の可換群として、$K^N$を群環$K[G]$と同一視した時の乗法、すなわち$G$の演算に関する畳み込み積を考えます。
畳み込み積に関して$v \in K^N$との内積$K^N \to K$が環準同型である必要十分条件は、$v$が$G$の指標であること、すなわち合成写像$G \hookrightarrow K[G] \cong K^N \to K$が$G$から$K$の乗法モノイドへのモノイド準同型であることです。
$K^N$の標準基底$(1,0,\ldots,0), \ldots, (0,\ldots,0,1)$を$\delta_0,\ldots,\delta_{N-1}$と置き、$K^N$と$K[G]$の同一視に用いた$G$の要素の番号付け$\mathbb{N} \cap [0,N) \cong G$によって$G$の可換群演算から定まる$\mathbb{N} \cap [0,N)$の可換群演算を$\odot$と置き、$\odot$に関する単位元を$e \in \mathbb{N} \cap [0,N)$と置くと、$v$が$G$の指標であるという条件は
- $\delta_e \cdot v = 1$
- $N$未満の任意の非負整数$i,j$に対し、$\delta_{i \odot j} \cdot v = (\delta_i \cdot v)(\delta_j \cdot v)$
の$2$条件を満たすことと同値です。非常に具体的な条件ですね。
さて$G$の指標たちは自動的に線形独立です。このことは$K = \mathbb{Q},\mathbb{R},\mathbb{C}$で$G$が有限群であればユニタリー指標の直交性をもとに理解している人も多いかと思いますが、一般の場合でもファンデルモンド行列式と同様の計算で確認できます。
$K$の標数が$0$であるかまたは$N$と互いに素な素数である場合、$K$が代数閉体などのある程度大きい体（より正確には$1$の冪根が十分多くある体）であれば、$G$の指標は$N$個存在してそれらは線形独立であるので$K^N$の基底をなします。そのような基底$v_1,v_2,\ldots,v_N$がとの内積による座標変換またはその非零定数倍こそが$G$上の離散フーリエ変換（DFT）です。
つまり、離散フーリエ変換はゲルファント変換の特別なものということです。DFTとかDFSとかDSUとかDSTとか似たようなのが多くて困っちゃいますね。
なお離散フーリエ変換は愚直に行うと$N^2$のオーダーが掛かってしまうので同じ要素を用いた演算を繰り返す（座標変換した結果を使い回せる）とかでない限り高速化には寄与しないのですが、離散フーリエ変換は高速化できることがあるため競技プログラミングで活躍しているというわけです。
離散フーリエ変換の高速化がどのような時にできるかを説明するにはポントリャーギン双対の話をすると良いのですが、その前に一旦具体例を２つ紹介します。
巡回畳み込みの場合
$K^N$を多項式環の剰余環$K[X]/(X^N-1) K[X]$と同一視した時の乗法を考えます。この乗法は$K$上の巡回群$\mathbb{Z}/N \mathbb{Z}$の群環$K[\mathbb{Z}/N \mathbb{Z}]$と自然に同一視できるので、巡回畳み込みと呼ばれています。
巡回畳み込みに関して$v \in K^N$との内積$K^N \to K$が環準同型である必要十分条件は$v$が巡回群$\mathbb{Z}/N \mathbb{Z}$の指標であること、すなわち
- $N$未満の任意の非負整数$i$に対し、$v_1^i = v_i$
- $v_1^N = 1$
の$2$条件を満たすということです。つまり$K$における$1$の$N$乗根ごとに$v$が取れます。$K$は体なのでそこにおける$1$の$N$乗根は高々$N$個ですが、ちょうど$N$個ある時に対応する基底$v_1,v_2,\ldots,v_N$が取れるというわけです。
例えば$K = \mathbb{C}$であれば$1$の$N$乗根がちょうど$N$個取れます。$K$が素数$p$を用いて$\mathbb{F}_p$と掛ける時、$1$の$N$乗根がちょうど$N$個取れる必要十分条件は$N \mid (p-1)$です。特に$N$が$2$冪である場合は、$p-1$が$2$でいっぱい割れる、つまり$p$がプロス素数であることが要求されるわけですね。
さて、$N$が$2$冪である場合の離散フーリエ変換は再帰によるその高速化が可能で、そのように実装したアルゴリズムを高速フーリエ変換（FFT）と呼びます。特に$K$がプロス素数$p$を用いて$\mathbb{F}_p$と書ける時の高速フーリエ変換は、数論的変換（NTT）とも呼び分けられることも多いです。
つまり、高速フーリエ変換も数論的変換もゲルファント変換の高速化であるということですね。
bitwise XOR畳み込みの場合
$N$が非負整数$D$を用いて$2^D$と表せるとし、$K^N = K^{2^D}$を群環$K[\mathbb{F}_2^{\oplus D}]$と同一視した時の乗法を考えます。この乗法は$D$ bitの非負整数を添え字に持つ配列のbitwise XOR畳み込みと自然に同一視されます。
bitwise XOR畳み込みに関して$v \in K^N$との内積$K^N \to K$が環準同型である必要十分条件は$v$が直和群$\mathbb{F}_2^{\oplus D}$の指標であること、すなわち$\mathbb{Z} \cap [0,D)$のある部分集合$U$が存在して
- 任意の$a \in \mathbb{F}_2^{\oplus D}$に対し、$v_a = (\# \{u \in U \mid a_u = 1\} \bmod 2 = 0) ? 1 \colon -1$
を満たすということです。つまり$K$の標数が$2$でなければ、$\mathbb{Z} \cap [0,D)$の部分集合ごとに$v$が取れます。$\mathbb{Z} \cap [0,D)$の部分集合は$2^D = N$個あり、対応する$v$たちは$K^N$の基底をなします。
この基底との内積による座標変換こそアダマール変換であり、その再帰的な計算による高速化が高速アダマール変換ですね。つまりアダマール変換はゲルファント変換の特別な例であり、高速アダマール変換はゲルファント変換の高速化というわけです。
一般の場合
巡回群や加法群$\mathbb{F}_2$の直和の指標の場合は、基底との内積による座標変換が再帰なりによって高速化できました。高速化の背景には指標のどんな性質が使われているでしょう？ そして一般の可換群演算に対しては、どのように高速化が検討できるでしょう？
$G$の指標を、$K$の乗法に関するモノイド準同型$G \to K$とみなします。すると$G$の指標全体の集合は$K^G$の部分集合とみなされるわけですが、これは$G$のポントリャーギン双対や$G$の指標群と呼ばれ、各点積に関して可換群をなします。
$G$のポントリャーギン双対は$\check{G}$と書き表され、$G$が可換有限群であるという仮定から有限アーベル群の基本定理により$G$と$\check{G}$が同型であることも従います。
従って$G$がシンプルであればあるほど$\check{G}$の構造もシンプルで、内積による座標変換に$\check{G}$の可換群構造を用いた良い再帰的計算方法が見つけやすくなります。
例えば$G$が巡回群であれば$\check{G}$も巡回群となりすなわち１つの要素からなる生成系を持つので、生成系による指数表示に関する再帰計算が、指数が$2$などの特定の素数の倍数であり続ける限り可能です。
例えば$G$が加法群$\mathbb{F}_2$の直和群であれば$\check{G}$も加法群$\mathbb{F}_2$の直和群となりすなわち$\mathbb{F}_2$線形基底を持つので基底による係数表示に関する再帰計算が、指数が$2$などの特定の素数の倍数であり続ける限り可能です。
裏を返せば$G$が巡回群であっても位数が$2 \times 3 \times 5 \times \cdots$のように無平方であれば高速フーリエ変換と同様の再帰が深度$1$で止まってしまいますし、$G$が加法群$\mathbb{F}_2$の直和群であっても次元が$2 \times 3 \times 5 \times \cdots$のように無平方であれば高速アダマール変換と同様の再帰が深度$1$で止まってしまいます（ただしこちらに関してはセグメント木を実装する時と同様に、次元を$2$冪まで広げればよいです）。
ポントリャーギン双対の生成系に、再帰と相性の良い構造を見つけられるか否かという問題なわけですね。次の多項式乗算の例で、高速フーリエ変換と高速アダマール変換以外にも実際に高速化できる離散フーリエ変換の例があることを説明いたします。
多項式乗算の場合
$K^N$を多項式環の剰余環$K[X]/X^N K[X]$と同一視した時の乗法を考えます。この乗法は多項式の乗法を$N$次以降打ち切ったものです。
残念ながら$K[X]/X^N K[X]$は素イデアルを１つしか持たない$0$次元環という環で、ゲルファント変換と相性が悪いです。そこで$N$次打ち切りの多項式乗算を別の乗算に帰着させる手法を考えましょう。
まず$D$を$2N-1$以上の正整数とします。この時$N$次未満の多項式の積は$D$次未満となるため、その計算結果は$K[X]/(X^D-1) K[X]$の乗算、つまり$D$次の巡回畳み込みから一意に復元されます。従って$N$次未満の多項式の積の$N$次以降を打ち切ったものを計算するには、$D$次の巡回畳み込みを計算して$D$次未満の多項式を復元してその$N$次以降を打ち切ればよいです。
これにより、直接のゲルファント変換が貧弱な$K[X]/X^N K[X]$でもゲルファント変換により乗法が処理できました。なお上記の議論は結果的に$N$次打ち切りをしない多項式乗算を計算した上で$N$次打ち切りをしているため、$N$次打ち切りをしない多項式乗算も同様にゲルファント変換で処理できます。
さて巡回畳み込みについて説明した際に触れたように、特に$p-1$が$2$でいっぱい割れる時、$D$が$2$冪の場合の基底が取れて離散フーリエ変換ができ、その高速化が高速フーリエ変換（FFT）でした。従って$N$次未満の多項式の乗算が$D$次巡回畳み込みの高速フーリエ変換を用いて高速化が可能というわけです。多項式乗算やその$N$次打ち切りそのものが高速フーリエ変換なわけではないので、用語の混乱をしないように気をつけていきましょう。
なお同様に$p-1$が$3$でいっぱい割れる時、つまり$p$がピアポン素数である時、$D$が$3$冪の場合の基底が取れて$D$次巡回畳み込みに対する離散フーリエ変換ができ、高速フーリエ変換と同様の再帰によるその高速化が（任意mod畳み込みなしで）可能です。
このように、高速フーリエ変換や高速アダマール変換以外にも、ポントリャーギン双対の生成系に再帰と相性の良い構造さえ見つけられれば実際に高速化が可能であるというわけです。多項式乗算の巡回畳み込みへの帰着によるゲルファント変換の活用をマスターしたら、上の問題にぜひ挑戦してみてください。
max畳み込みの場合
$P$を$N$元集合とし、$\leq$をその上の半順序とします。$(P,\leq)$は最小元と引数$2$の$\max$が定義されているとします。この時先述したように$(P,\max)$はモノイドをなし、しかも可換です。
$K^N$をモノイド環$K[P]$と同一視した時の乗法を考えます。この乗法は$\max$畳み込みと呼ばれ、
\[ a \times b = \left( \sum_{\max \{i,j\} = k} a_i b_j \right)_{k \in P} \]
と表されます。$\max$畳み込みに関して$v \in K^N$との内積$K^N \to K$が環準同型であるのは5日が気になるところですが、よく考えると始切片和が環準同型を定めます。つまりは各$k \in P$に対し、$\chi_k \in K^N$を$k$の始切片の特性関数$(i \leq k ? 1 \colon 0)_{i \in P} \in K[P]$に対応する元と定めると、$\chi_k$による内積は添字$k$以下の総和に他ならず、$\chi_k$との内積を取る写像$K^N \to K$が環準同型となります。
というわけで$K^N$の基底$(\chi_k)_{k \in P}$が取れたので、これにてゲルファント変換が計算できます。ここで各$k \in P$に対し$\chi_k$との内積が添字$k$以下の総和であったことを踏まえると、この基底との内積による座標変換は単に累積和を取っているだけですね。そして有限順序集合における累積和とはゼータ変換に他ならず、その逆変換はメビウス変換に他なりません。
つまり$\max$畳み込みの計算にはゼータ変換が有効で、このゼータ変換はゲルファント変換の特別な場合です。$(P,\leq)$を具体例にしてみると、見覚えのあるものがわんさか出てきます。
- 特に$P$が$\mathbb{Z} \cap [0,N)$で$\leq$が通常の大小関係の場合、$\max$畳み込みは通常の順序に関する$\max$畳み込み$\sum_{\max \{i,j\} = k}$に他ならず、この時のゼータ変換が累積和で、逆変換が階差数列（imos法で計算する数列）
- 特に$P$が$\mathbb{Z} \cap [0,N)$で$\leq$が通常の大小関係の逆の場合、$\max$畳み込みは通常の順序に関する$\min$畳み込み$\sum_{\min \{i,j\} = k}$に他ならず、この時のゼータ変換が右からの累積和で、逆変換が右からの階差数列
- 特に$P$が有限集合の冪集合で$\leq$が$\subset$の場合、$\max$畳み込みは$\cup$畳み込み$\sum_{S \cup T = U}$に他ならず、この時のゼータ変換の高速化が高速ゼータ変換で、逆変換の高速化が高速メビウス変換
- 特に$P$が有限集合の冪集合で$\leq$が$\supset$の場合、$\max$畳み込みは$\cap$畳み込み$\sum_{S \cap T = U}$に他ならない
- 特に$P$が$\mathbb{Z} \cap [1,N]$で$\leq$が約数関係の場合、$\max$畳み込みは$\textrm{lcm}$畳み込み$\sum_{\textrm{lcm}(i,j) = k}$に他ならず、この時のゼータ変換が約数ゼータ変換で、その逆変換が約数メビウス変換
- 特に$P$が$\mathbb{Z} \cap [0,N)$で$\leq$が倍数関係の場合、$\max$畳み込みは$\textrm{gcd}$畳み込み$\sum_{\textrm{gcd}(i,j) = k}$に他ならず、この時のゼータ変換が倍数ゼータ変換で、その逆変換が倍数メビウス変換
- 特に$N$が非負整数$D$を用いて$2^D$と表せ$P$が$\mathbb{Z} \cap [0,N)$で$\leq$が$2$進法の各桁の大小関係の積順序である場合、$\max$畳み込みはbitwise OR畳み込み$\sum_{i \textrm{ OR } j = k}$に他ならない
- 特に$N$が非負整数$D$を用いて$2^D$と表せ$P$が$\mathbb{Z} \cap [0,N)$で$\leq$が$2$進法の各桁の大小関係の逆の積順序である場合、$\max$畳み込みはbitwise AND畳み込み$\sum_{i \textrm{ AND } j = k}$に他ならない
競技プログラミングで出てくる色々なゼータ変換が$\max$畳み込みのゲルファント変換の具体例であることが分かりました。なおゼータ変換自体はゼータ関数の乗算として隣接代数に一般化され、隣接代数の乗法は$2$次元の畳み込みとなっており$\max$畳み込みより更に抽象的なものです。
論理演算の場合
$K = \mathbb{F}_2$とし、$N$が非負整数$D$を用いて$2^D$と表せるとし、$K^N = \mathbb{F}_2^{2^D}$を$D$個の命題変数$P_1,\ldots,P_D$が生成するブール代数
\[ \mathbb{F}_2[P_1,\ldots,P_D]/(P_1^2+P_1,\ldots,P_D^2+P_D) \]
と同一視した時の各種論理演算（$\land,\lor,\neg,\rightarrow$など）を考えます。
XORとANDの組のFunctional completenessより、全ての論理演算はブール代数の$+$と$\land$の合成で明示的に書き表せるため、$K^N$に定まった論理演算を計算するためには各点和と$\land$が計算できればよいです。ただしブール代数の加法$+$は
\[ P + Q = \neg(P \Leftrightarrow Q) \]
と定義される$2$項演算で、$+$と$\land$に関してブール代数は可換環をなします。
$\land$に関して$v \in K^N$との内積$K^N \to K$が環準同型である必要十分条件は$v$が真理関数であること、すなわちある$x \in \{0,1\}^D$が存在して
- 任意の$a \in \mathbb{F}_2[P_1,\ldots,P_D]/(P_1^2+P_1,\ldots,P_D^2+P_D)$に対し、$v_a = a(x)$
を満たすということです。ここで$a(x)$は$a$を代表する$\mathbb{F}_2$係数多項式に$x$を代入したもので、これはイデアルによる商の普遍性からwell-definedとなります。
つまり$x \in \{0,1\}^D$ごとに$v$が取れます。$x \in \{0,1\}^D$は$2^D = N$個あり、対応する$v$たちは命題論理の完全性（もしくは中国剰余定理）より$K^N$の基底をなします。
この基底との内積による座標変換こそ真理表への翻訳です。つまり論理演算の真理表への翻訳はゲルファント変換の特別な例というわけです。
論理演算は$2$項演算であったとしても必ずしもモノイド演算とならず、各種データ構造に乗らなかったりします。しかし$+$と$\land$はともに可換群演算と可換モノイド演算であり、データ構造と相性が良いですね。しかも真理表に翻訳するとbit演算による$64$並列が可能になるため、非常に高速に処理できるというわけです。
論理演算のゲルファント変換（真理表への変換）とデータ構造・$64$並列による高速化がマスターしたら、上の問題にぜひ挑戦してください。
ちなみに今回は$D$個の命題変数$P_1,\ldots,P_D$から作った具体的なブール代数を考えましたが、一般のブール代数でも同様の議論ができることがストーンの表現定理により保証されます。ストーン双対を知っている人向けに言うと、ブール代数に対するストーン双対もまた（極大イデアルに制限した、または位相を考慮した）ゲルファント変換とみなせるということです。
発展
$p$進解析を知っている人向けの発展的な内容も書いておきます。岩澤代数$\mathbb{Z}_p[[\mathbb{Z}_p]]$は岩澤同型により形式冪級数環$\mathbb{Z}_p[[X]]$と同一視できます。岩澤同型は位相可換群である加法群$\mathbb{Z}_p$の$p$進連続指標による座標変換なので、これもまた（位相を考慮した）ゲルファント変換としてみなせます。
更に完備群環と連続関数環の間の標準的なペアリングを通じて完備群環を$p$進測度の環とみなすと、岩澤同型の$p$進双対は$p$進連続関数のマーラー変換に他ならないことが分かります。この意味でマーラー変換もゲルファント変換の特別な例であるということです。
マーラー変換は、二項係数の和からその係数を復元する明示的な変換です。二項係数の和の係数計算は数え上げ問題などでよく扱われ、例えば要素数のみに依存する部分集合上の関数のゼータ変換から元の関数を復元する際にメビウス変換を避けて包除原理で高速化する時に考える必要がありますね。
上の問題はマーラー変換の知識なく実験で解くことが可能ですが、マーラー変換の知識があると実験せずとも式変形だけで解くことが可能です。詳しくは解説に載せてあるので、マーラー変換をマスターした人は是非挑戦してみましょう。
終わりに
高速フーリエ変換とか高速アダマール変換とか高速ゼータ変換の一見すると謎な係数操作も、体への環準同型を大量に取り出して各点積に帰着させるゲルファント変換の高速化として統一的に理解できるというお話でした。
ゲルファント変換の定義そのものは素イデアルの理解が必要でやや難解でしたが、競技プログラミングの文脈に合わせて配列空間の特殊な畳み込みの高速化目的に限定すると表面上は単なる座標変換に過ぎず、それこそ$45$度回転のちょっと難しい版程度の認識を持てるようになってくだされば幸いです。
自分用覚え書き
github pagesで数式を使う際は、inlineであってもなくても閉じカッコと半角アンダーバーの間に半角スラッシュを入れないとmarkdownからhtmlへの翻訳の仕様でバグるらしい。
数式環境をくくる大括弧と数式環境内の中括弧や半角空白は半角スラッシュ２つ、改行は半角スラッシュ５つ、その他は基本的に半角スラッシュ１つで良さそう。htmlとmathjaxの関係が難しい。
arrayとalignはどちらも使える。arrayが使えない気がしてしまったのは中括弧につける半角スラッシュの個数を間違えていたから。alignはアンパサンドを等号の右側につけて半角空白を２つ入れると幅がちょうど良さそう。arrayなしだとアンパサンドは使えない。