FFT和FWT的群论本质

· · 算法·理论

定义同态映射 $\chi:G\to \mathbb C^\times \ s.t. \ \forall g,h\in G,\chi(g)\chi(h)=\chi(gh)$. (事实上 对于每个不可约的 $\rho:G\to \text{GL}(V)$ 有 $\chi_\rho: g\mapsto\text{Tr}(\rho(g)).$) 定义 $\hat G=\{\chi_i\}$ 为 $G$ 的对偶群, 其中的运算为 $\chi_1\chi_2(g)=\chi_1(g)\chi_2(g)$. --- $|\hat G|=|G|$. 证明: 对于循环群 $<a|a^n=1>$, 显然所有的 $n$ 个 $\chi$ 由 $\chi_k(a)=\varepsilon^k$ 生成, $\varepsilon=e^\frac{2\pi i}{n}$. 任意有限交换群均可分解为若干个循环群的直积, 对于 $G\cong G_1\times G_2$, $\chi_1\in\hat{G_1},\chi_2\in \hat{G_2}$ 有 $\chi(g)=\chi_1(g_1)\chi_2(g_2)\in \hat G\ (g=(g_1,g_2)\in G)$, 反之同理. --- 显然有自然同构 $\varphi:G\leftrightarrow \hat{\hat{G}},g\leftrightarrow (f:\chi\mapsto \chi(g))$. 记 $g(\chi)=\varphi(g)$. --- 定义内积 $\displaystyle\langle f,g\rangle=\dfrac 1n\sum_{x\in G} f(x)\overline{g(x)}$, 则 $\hat G$ 构成 $F(G,\mathbb C)$ 的单位正交基. 证明: $G$ 有限 $\Rightarrow |\chi(g)|=1\Rightarrow \overline{\chi(g)}=\dfrac{1}{\chi(g)}=\chi^{-1}(g)=\chi(g^{-1}). $\displaystyle \sum_{g\in G} \chi(g)=\sum_{g\in G} \chi(gh)=\chi(h)\sum_{g\in G} \chi(g)\Rightarrow$ 若 $\forall h\in G,\chi(h)=1$ 即 $\chi=e_{\hat G}$ 则 $\displaystyle \sum_{g\in G}\chi(g)=n$, 否则 $\text{LHS}=0$. $\Rightarrow\langle \chi_i,\chi_j\rangle=[\chi_i\chi_j^{-1}=e]=[i=j].

完整的 Fourier Transform: \displaystyle f:G\to\mathbb C,f=\sum_{i=1}^n \langle f,\chi_i\rangle\chi_i.

证明: \displaystyle\sum_{i=1}^n \langle f,\chi_i\rangle \chi_i(g)=\sum_{i=1}^n\sum_{h\in G} f(h)\overline{\chi_i(h)}\chi_i(g)=\sum_{h\in G}f(h)\sum_{i=1}^n\chi_i(g)\overline{\chi_i(h)}=\sum_{h\in G} f(h)\langle g,h\rangle=f(g). 注意此处的 \langle g,h\rangle 是 F(\hat G,\mathbb C) 上的内积.

对于 n-1 次多项式 F(x), 取 G=\mathbb Z/n\mathbb Z=(\{0,1,\cdots,n-1\},+), 则 \chi_k(g)=\varepsilon^{gk}.

$\displaystyle [x^{n-g}]F(x)=f(g)=\sum_{k=1}^n \langle f,\chi_k\rangle \chi_k(g)=\dfrac 1n\sum_{k=1}^n F(\varepsilon^k)\varepsilon^{gk}$, 即为多项式的DFT. 记 $\mathbb Z_n=\mathbb Z/n\mathbb Z$. 取 $n=2m$, 则 $2\mathbb Z_m=\{0,2,\cdots,2(m-1)\}$ 为 $\mathbb Z_n$ 的子群, $\mathbb Z_n=(2\mathbb Z_m)\cup(1+2\mathbb Z_m)$. $\displaystyle n\langle f,\chi\rangle=\sum_{g\in\mathbb Z_n} f(g)\overline{\chi(g)}=\sum_{g\in2\mathbb Z_m} (f(g)\overline{\chi(g)}+f(g+1)\overline{\chi(g)\chi(1)})=m\langle f_1,\chi'\rangle+\overline{\chi(1)}m\langle f_2,\chi'\rangle$. 其中 $f_1,f_2,\chi':2\mathbb Z_m\to \mathbb C,f_1(g)=f(g),f_2(g)=f(g+1),\chi'(g)=\chi(g)\Rightarrow \chi'$ 为 $2\mathbb Z_m$ 的同态. 这样转化到了一个更小的群上, 得到 FFT 的迭代形式. --- FWT 中下标的运算为各位独立的不进位加法, 则对应的群 $G=(\mathbb Z_2)^n,|G|=2^n$. $\mathbb Z_2$ 上有 $\chi_1(g)=1,\chi_2(g)=(-1)^g$. 从而 $G$ 上的 $\displaystyle\chi_k(g)=\prod_{i\in I}(-1)^{a_i}\cdot\prod_{i\not\in I} 1=(-1)^{|g\cap k|}$, 其中 $g=\overline{(a_n\cdots a_1)}_2,k$ 为集合 $I$ 的二进制表示. $k$ 取遍 $0\sim 2^n-1$ 时得到 FWT 的全部系数. $k-$ FWT 只需把 $\mathbb Z_2$ 换成 $\mathbb Z_k$.