虚数单位（Imaginary unit）

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

复数（Complex number）

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

幅角（Argument）

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

欧拉公式（Euler’s formula）

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

欧拉恒等式（Euler’s identity）

[latex display=”true”]e^{i \pi} + 1 = 0[/latex]

cis函数

[latex display=”true”]\mathrm{cis} \ \theta = \frac{z}{|z|} = \cos \theta + i \sin \theta[/latex]
其中，[latex]z[/latex]是幅角为[latex]\theta[/latex]的复数。

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

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

单位根（Root of unity）

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

消去引理

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

折半引理

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

求和引理

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

参考资料

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