虚数单位（Imaginary unit）

虚数单位i定义为二次方程式x^2+1=0的两个解答中的一个解答。也就是说，虚数单位可以表达为i^2 = -1或i = \sqrt{-1}。

复数（Complex number）

复数为实数的延伸，它使任一多项式方程式都有根。
复数都可表达为x+yi，其中x及y皆为实数，分别称为复数的实部和虚部。

幅角（Argument）

设有非零复数z \in \mathbb{C} \backslash \{ 0 \}，记作z = x + yi，其中的x和y为实数，那么复数z的幅角\varphi指的是使下列等式：
z = x + yi = \sqrt{x^2 + y^2} (\cos \varphi + i \sin \varphi)
成立的任何实数\varphi。
几何意义参见：幅角 – 维基百科，自由的百科全书
只有非零复数有幅角。

欧拉公式（Euler’s formula）

对任意实数x，都存在e^{ix} = \cos x + i \sin x = \mathrm{cis} \ x。
还可以推导出\sin x = \frac{e^{ix} - e^{-ix}}{2i}及\cos x = \frac{e^{ix} + e^{-ix}}{2}。

欧拉恒等式（Euler’s identity）

cis函数

\mathrm{cis} \ \theta = \frac{z}{|z|} = \cos \theta + i \sin \theta
其中，z是幅角为\theta的复数。

棣莫弗公式（De Moivre’s formula）

对任意复数x和整数n，下列性质成立：
(\cos x + i \sin x)^n = \cos nx + i \sin nx
或者说
\mathrm{cis}^n \ x = \mathrm{cis} \ nx

单位根（Root of unity）

n次单位根是n次幂为1的复数，它们在复平面的单位圆上均匀分布，其中一个顶点是1。
单位的n次根有n个，分别为
\omega_n^k = e^{\frac{2 \pi ki}{n}} \ (k = 0, 1, 2, \ldots, n-1)
定义\omega_n = e^{\frac{2 \pi i}{n}}为主n次单位根，其他单位根为它的整数次幂。

消去引理

对任意整数n \geq 0, k \geq 0, d \geq 0，有：
\omega_{dn}^{dk} = \omega_n^k
证明：由定义

折半引理

如果n > 0为偶数，那么n个n次单位根的平方的集合就是\frac{n}{2}个\frac{n}{2}次单位根的集合。
证明：实际上就是在说对任意非负整数k，有 (\omega_n^k)^2 = \omega_{\frac{n}{2}}^k 。由消去引理

求和引理

对于任意整数n \geq 1与不能被n整除的非负整数k，有
\sum_{j=0}^{n-1}(\omega_n^k)^j = 0
证明：由几何级数的求和公式
\sum_{k=0}^n x^k = \frac{x^{n+1} - 1}{x - 1}

参考资料

• 虚数单位 – 维基百科，自由的百科全书
• 复数 (数学) – 维基百科，自由的百科全书
• 幅角 – 维基百科，自由的百科全书
• cis函数 – 维基百科，自由的百科全书
• 欧拉公式 – 维基百科，自由的百科全书
• 棣莫弗公式 – 维基百科，自由的百科全书
• 单位根 – 维基百科，自由的百科全书
• 算法导论（第3版），第30章，Thomax H. Cormen等著，机械工业出版社，9787111407010
• [学习笔记] 多项式与快速傅里叶变换(FFT)基础 – rvalue – 博客园