单位根筛选与复数三角恒等式

单位根能把多项式的某些系数选出来。这里只使用有限等比和、二项式定理和复数乘法，不建立傅里叶分析理论。

正交求和及适用条件

设 $N\ge1$ 为整数， $\omega=\cos(2\pi/N)+i\sin(2\pi/N)$ 。对任意整数 $m$ ，

\sum_{j=0}^{N-1}\omega^{jm}=\begin{cases}N,&N\mid m,\\0,&N\nmid m.\end{cases}

若 $N\mid m$ ，每项为 $1$ ；否则公比不为 $1$ ，等比求和的分子 $1-\omega^{Nm}=0$ 。

若改用 $\omega^k$ ，非零和的条件变为 $N\mid km$ ，不能只检查 $N\mid m$ 。例如 $N=4,k=2,m=2$ 时每项仍为 $1$ ，和为 $4$ ，虽然 $4$ 不整除 $2$ 。

有限系数筛选

设 $N\ge1$ 为整数， $\omega=\cos(2\pi/N)+i\sin(2\pi/N)$ 。设 $P(z)=\sum_{k=0}^d c_kz^k$ ， $r\in\{0,\ldots,N-1\}$ 。交换两个有限求和，得

\frac1N\sum_{j=0}^{N-1}\omega^{-rj}P(\omega^j)=\sum_{\substack{0\le k\le d\\k\equiv r\ (\mathrm{mod}\ N)}}c_k.

具体地，展开左侧后， $c_k$ 的系数为

\frac1N\sum_{j=0}^{N-1}\omega^{(k-r)j}.

由本页“正交求和及适用条件”中的结论，这个系数在 $N\mid(k-r)$ 时等于 $1$ ，其余情形等于 $0$ 。下标条件只表示按除以 $N$ 的余数分类。

例如 $P(z)=(1+z)^6,N=3,r=0$ ，选出的系数和为 $\binom60+\binom63+\binom66=22$ 。也可从 $[2^6+(1+\omega)^6+(1+\omega^2)^6]/3=(64+1+1)/3$ 得到。

棣莫弗公式生成多倍角

把 $(\cos x+i\sin x)^3=\cos3x+i\sin3x$ 展开并比较实部、虚部，得到

\cos3x=4\cos^3x-3\cos x,\qquad\sin3x=3\sin x-4\sin^3x.

对一般正整数幂展开也能产生相应恒等式。比较实虚部的依据是复数相等当且仅当实部虚部分别相等；不能仅比较模长就认定复数相同。

对等差角求和，也可对 $\sum_{k=0}^{n-1}(\cos(a+kd)+i\sin(a+kd))$ 使用复数等比和，再分别取实虚部；公比为 $1$ 时须单独直接求和。

有限复数列的离散傅里叶变换

这里的对象只有 $n$ 个复数，所用工具是有限求和与单位根。设整数 $n\ge1$ ，

\omega=\cos\frac{2\pi}{n}+i\sin\frac{2\pi}{n},\qquad a_0,\ldots,a_{n-1}\in\mathbb C.

下标按除以 $n$ 的余数理解，如 $a_{k+n}=a_k$ 。定义另一组复数

\widehat a_t=\frac1{\sqrt n}\sum_{k=0}^{n-1}a_k\omega^{-kt}\quad(0\le t<n),

称为原复数列的离散傅里叶变换。它将原数列改写为 $n$ 个单位根模式的系数。不同教材的正负号和归一化因子可能不同，后面公式均依照本定义。

反演公式及证明

a_k=\frac1{\sqrt n}\sum_{t=0}^{n-1}\widehat a_t\omega^{kt}.

代入定义并交换两个有限和，右侧为

\frac1n\sum_{j=0}^{n-1}a_j\sum_{t=0}^{n-1}\omega^{(k-j)t}.

由单位根求和，内层在 $j=k$ 时为 $n$ ，在其余 $j$ 时为零，所以结果恰为 $a_k$ 。这也证明变换保留全部信息，且每组变换系数唯一对应原数列。

线性与平移

对固定复数 $\lambda,\mu$ ，逐项代入定义得到

\widehat{\lambda a+\mu b}_t=\lambda\widehat a_t+\mu\widehat b_t.

若 $b_k=a_{k+h}$ ，令 $j=k+h$ ； $j$ 仍遍历所有余数，于是

\widehat b_t=\frac1{\sqrt n}\sum_j a_j\omega^{-(j-h)t}=\omega^{ht}\widehat a_t.

这里 $h$ 是整数，描述循环平移，不是向数列两端补零后的平移。

Parseval 恒等式与循环卷积

沿用本页归一化的离散傅里叶变换。任意两组长度为 $n$ 的复数列 $a,x$ 满足

\sum_{t=0}^{n-1}\overline{\widehat a_t}\,\widehat x_t =\sum_{k=0}^{n-1}\overline{a_k}x_k.

证明。 利用 $\overline\omega=\omega^{-1}$ 展开左侧：

\begin{aligned} \sum_t\overline{\widehat a_t}\widehat x_t &=\frac1n\sum_{j,k}\overline{a_j}x_k\sum_t\omega^{(j-k)t}\\ &=\sum_k\overline{a_k}x_k. \end{aligned}

内层求和只保留 $j=k$ 。取 $x=a$ ，得到模长平方和不变：

\sum_t|\widehat a_t|^2=\sum_k|a_k|^2.

再定义循环卷积 $f_k=\sum_{j=0}^{n-1}a_jx_{k-j}$ ，下标均按余数理解。它满足

\widehat f_t=\sqrt n\,\widehat a_t\widehat x_t.

证明。 在定义中令 $r=k-j$ ，得到

\begin{aligned} \widehat f_t&=\frac1{\sqrt n}\sum_{k,j}a_jx_{k-j}\omega^{-kt}\\ &=\frac1{\sqrt n}\left(\sum_j a_j\omega^{-jt}\right) \left(\sum_r x_r\omega^{-rt}\right) =\sqrt n\widehat a_t\widehat x_t. \end{aligned}

该公式将循环卷积化为逐项乘法。它与普通多项式乘积的系数卷积不同：这里超出长度的下标会绕回开头，使用前须确认问题采用的是哪一种边界约定。

关联阅读