FFT和FWT的群论本质

$G$ 为有限交换群, $|G|=n$. $F(G,\mathbb C)=\{f:G\to \mathbb C\}$ 为 $\mathbb C-$ 线性空间, $\dim F=n$.

定义同态映射 $\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\langle \chi_i,\chi_j\rangle=\dfrac 1n\sum_{g\in G}\chi_i(g)\overline{\chi_j(g)}=\dfrac 1n\sum_{g\in G} (\chi_i\chi_j^{-1})(g)$.

$\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 f:k\mapsto [x^{n-k}]F(x)\Rightarrow n\langle f,\chi_k\rangle=\sum_{g=0}^{n-1} f(g)\overline{\chi_k(g)}=\sum_{g=0}^{n-1} [x^{n-g}]F(x)\varepsilon^{k(n-g)}=F(\varepsilon^k)$.

$\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$.