理論計算機科学におけるフーリエ解析 (定義)

フーリエ変換とは関数の良い基底を使って線形和で表すことを指します. 競技プログラミングの文脈などでは畳み込みのフーリエ変換と積の関係が非常に有名だと思いますが, それ以外にも様々な応用があります. 基本的にフーリエ変換と聞くと$\sin$や$\cos$が混じった積分がでてくるというイメージだと思いますが, 理論計算機科学では離散的なものを扱う都合上そういったものは(文脈によるが)登場せず, 全てが初等的に定義されるのでより親しみやすいと個人的に思います. 

本記事では定義と基本的な事実だけ紹介します. 将来的にフーリエ変換を使った証明等を書く時にこの記事を参照していきます.

$n\in\mathbb{N}$に対し$[n]=\{1,\dots,n\}$と略記します. 有限集合$S$上で一様ランダムに$x$が選ばれることを$x\sim S$で表します.

$\mathbb{F}_q$を素体とし, $\omega=\mathrm{e}^{\frac{2\pi i}{q}}$とします. 二つの関数$f,g\colon\mathbb{F}_q^n\to\mathbb{C}$に対し, その内積を

$$\langle f,g\rangle := \mathbb{E}_{x\sim\mathbb{F}_q^n}[f(x)\overline{g(x)}] = \frac{1}{|\mathbb{F}_q^n|}\sum_{x\in\mathbb{F}_q^n}f(x)\overline{g(x)}$$

とします. この内積が誘導するノルム$\|f\|=\sqrt{\langle f,f\rangle}$を考えます.

$v\in\mathbb{F}_q^n$に対し$\chi_v\colon\mathbb{F}_q^n\to\mathbb{C}$を $$\chi_v(x)=\omega^{\sum_{i=1}^n v_ix_i}$$ とし, 

$$\widehat{f}(v)=\langle f,\chi_v\rangle$$

で定義される関数$\widehat{f}$を$f$のフーリエ変換といいます.

関数族$(\chi_v)_{v\in\mathbb{F}_q^n}$は基底をなしていることが知られており, 任意の関数$f\colon\mathbb{F}_q^n\to\mathbb{C}$は一意に $f=\sum_{v\in \mathbb{F}_q^n}\widehat{f}(v) \chi_v$ と表せることが知られています. このような$f$の表現を$f$のフーリエ逆変換といいます.

また, $\|f\|^2 = \sum_{v\in\mathbb{F}_q^n}|\widehat{f}(v)|^2$が成り立ちます (Parsevalの等式). これはフーリエ変換がノルムを保つ変換(ユニタリ変換)であると解釈できます.

二つの関数$f,g\colon\mathbb{F}_q^n\to\mathbb{C}$に対し, その畳み込み$f\ast g$を

$$(f\ast g)(x) = \mathbf{E}_{a\sim\mathbb{F}_q^n}[f(a)g(x-a)]$$

とします. よく知られる事実として, $\widehat{f\ast g}(v) = \widehat{f}(v) \widehat{g}(v)$が成り立ちます.

最後に, $f\colon\mathbb{F}_q^n\to\mathbb{C}$と$1\leq p\leq\infty$に対して$f$の$\ell_p$ノルムを $$\|f\|_p=\left(\mathbb{E}_{x\sim\mathbb{F}_q^n}[|f(x)|^p]\right)^{1/p}$$ で定めます.

本記事では$\mathbb{F}_q^n$上の関数を対象にしていましたが, より一般にアーベル群上の関数に対して群の表現を考えることで似たような枠組みを考えることができます.