Cyclotomic polynomial

前置知识

在复数域 $\mathbb{C}$ 中，多项式 $x^n-1$ 有 $n$ 个根： $\cos \frac{2 \pi k}{n}+\mathrm{i} \sin \frac{2 \pi k}{n}, k=0,1, \cdots, n-1$ 。由 Euler 公式，可以写作 $\mathrm{e}^{2 \pi i k / n}=\exp \frac{2 \pi \mathrm{i} k}{n}$ 。
以下为了方便，记 $\omega_n=\exp \frac{2 \pi i}{n}$ ，则 $\omega_n^k=\left(\omega_n\right)^k=\exp \frac{2 \pi i k}{n}$ 。在上下文已知的情况下，可以用 $\omega$ 代替 $\omega_n$ （在某些文献中，用 $\varepsilon$ 表达相同的含义）。

根据上述记号， $x^n-1$ 的 $n$ 个根可以记作 $1, \omega, \omega^2, \cdots, \omega^{n-1}$
因此, 由 Vieta 定理（根与系数的关系），可以得到
性质 1.1: $x^n-1=(x-1)(x-\omega)\left(x-\omega^2\right) \cdots\left(x-\omega^{n-1}\right)$
由初中的因式分解技巧，有 $x^n-1=(x-1)\left(x^{n-1}+x^{n-2}+\cdots+x+1\right)$ ，于是就有
推论 1.1: $x^{n-1}+x^{n-2}+\cdots+x+1=(x-\omega)\left(x-\omega^2\right) \cdots\left(x-\omega^{n-1}\right)$
在上式中代入任何一个 $\omega_n^i$, 即可得到：
推论 1.2:

$$1 + \omega_n^k + \omega_n^{2k} + \cdots + \omega_n^{(n-1)k} = \begin{cases} 0 & \text{if } n \nmid k \\ n & \text{if } n \mid k \end{cases}$$

单位根群

由公式 $\omega_n^k=\exp\frac{2\pi\mathrm{i}k}{n}$ 得知，$1, \omega_n, \omega_n^2, \cdots, \omega_n^{n-1}$ 关于乘法运算$\cdot$构成了一个 $n$ 阶循环群 $\omega_n$ 被称为单位根群 (Group of root or unity)，其中 $\omega_n$ 是 $\omega_n$ 的一个生成元。
从而有 $\omega_n^a \cdot \omega_n^b=\omega_n^{a+b},\left(\omega_n^a\right)^b=\omega_n^{a b}, \omega_n^k=\omega_{\lambda n}^{\lambda k}$ ，以及特殊地 $\overline{\omega_n^k}=\omega_n^{-k}$
提到群，自然就会想到它的生成元。那哪些元素会成为它的生成元呢？
如果一个单位根, 比如 $\omega_6^2=\frac{-1+\sqrt{3} \mathrm{i}}{2}$, 它其实也是一个 3 次的单位根, 因此它所生成的所有单位根都是 3 次的, 而不会生成 $\omega_6=\frac{1+\sqrt{3} \mathrm{i}}{2} 。$
由有限循环群的结论， $\omega_n^k$ 是 $\omega_n$ 的生成元，当且仅当 $n \perp k$ ，即 $(n, k)=1$ 。因此，这些满足 $n \perp k$ 的单位根 $\omega_n^k$ 有着特殊的性质，这就是我们即将讨论的重点。
辨析：
单位根: $n$ 阶单位根是满足 $x^n = 1$ 的复数根，这些根在复平面上均匀分布在单位圆上。单位根的一般形式为 $\omega_n^k$，其中 $\omega_n = e^{2\pi i / n}$ 是一个主 $n$ 阶单位根，而 $k$ 是从 $0$ 到 $n-1$ 的整数。
本原单位根: 一个 $n$ 阶本原单位根是一种特殊的单位根，它的任意次幂（除了 $n$ 的倍数次）都不等于 $1$。具体地，如果 $\omega_n^k$ 是一个 $n$ 阶的本原单位根，那么对于任意非零整数 $m < n$ ，都有 $(\omega_n^k)^m \neq 1$。

分圆多项式

如果一个 $n$ 阶单位根 $\omega_n^k$, 满足对于任意的 $i=1,2, \cdots, n-1, \omega_n^{k-i} \neq 1$ (即 $\omega_n^k$ 是群 $\omega_n$ 的生成元), 则称 $n$ 阶单位根 $\omega_n^k$ 是本原的 (Primitive), $\omega_n^k$ 称为本原单位根 (Primitive root of unity), 简称原根。
定理 3.1: $\omega_n^k$ 是 $n$ 阶本原单位根的充要条件是 $n \perp k$ 。
由定理3.1，可知 $n$ 阶本原单位根恰有 $\phi(n)$ 个
上面提到过, 以所有 $n$ 阶单位根为根的多项式为 $x^n-1$， 那么以所有 $\phi(n)$ 个 $n$ 阶本原单位根为根的多项式又有什么样的性质呢？这就是我们接下来要提到的分圆多项式。
定义分圆多项式 (Cyclotomic polynomial) 所有以 $n$ 阶本原单位根为单根的首一多项式, 记作 $\Phi_n(x)$, 即

$$\Phi_n(x)=\prod_{\substack{1 \leq k \leq n,(k, n)=1}}\left(x-\omega_n^{\star}\right)$$

注意到 $n$ 个单位根将复平面上的单位圆 $|z|=1$ 等分成了 $n$ 等分, 因此得名为分圆多项式 (Cyclotomic)。
由于 $n$ 阶本原单位根一共有 $\phi(n)$ 个, 因此 $n$ 阶分圆多项式的次数 $\operatorname{deg} \Phi_n(x)=\phi(n)$, 这解释了为什么分圆多项式用 $\Phi_n(x)$ 表示。
分圆多项式的一个最基础最重要的定理由下面的定理 3.2 给出。
定理 3.2: $\prod_{d|n} \Phi_d(x)=x^n-1 。$
证明：
证明这个定理之前，我们比较两边的次数，可以发现一个有趣的事实：$\sum_{d|n}\phi(d)=n$，这个的理解笔者刚学抽代的时候就有点迷糊，先给出该定理的证明（记录一下），之后再给出定理3.2的证明

1. 如果 $n=1$，$\phi(n)=\phi(1)=1=n$
2. 如果 $n$ 是质数，$\phi(n) = n-1$，因此有 $\phi(n)+\phi(1)=n$
3. 如果 $n$ 是一个质数的幂，即$n=p^k$，则有$\sum_{d \mid n} \phi(d)=\sum_{i=0}^k \phi\left(p^i\right)=\sum_{i=1}^k p^{i-1}(p-1)+1=p^k$
4. 如果 $n$ 是任意整数，则由整数环是唯一分解整环可得 $n=p_1^{k_1} p_2^{k_2} p_3^{k_3}\dots p_n^{k_n}$，有$\sum_{d|n}\phi(d)=\sum_{i_1=0}^{k_1}\sum_{i_2=0}^{k_2}\dots\sum_{i_n=0}^{k_n}\phi(p_1^{i_1} p_2^{i_2} p_3^{i_3}\dots p_n^{i_n})=n(相互独立互质，利用欧拉函数的积性)$

接下来我们证明定理3.2
给定一个 $n$ 阶单位根 $\omega_n^k$, 我们定义 $d=\operatorname{gcd}(n, k)$ 。这意味着我们可以将 $n$ 和 $k$ 分别写为 $n=n_1d$ 和 $k=k_1 d$, 其中 $\operatorname{gcd}\left(n_1, k_1\right)=1$ 。因此, $\omega_n^k=\omega_{n_1 d}^{k_1 d}=\left(\omega_{n_1 d}^d\right)^{k_1}=\omega_{n}^{k_1}$ 。这里 $\omega_{n_1}^{k_1}$ 是一个 $n_1$ 阶单位根
由于 $n_1$ 和 $k_1$ 互质, 所以 $\omega_{n_1}^{k_1}$ 实际上是一个 $n_1$ 阶的本原单位根。这表明, 从任意 $n$ 阶单位根出发, 通过适当的因子分解和简化, 总能找到一个相对 “更原始” 的单位根, 即某个较小阶数的本原单位根
互斥性：对于 $n$ 的不同因数 $d$ 和 $d^{\prime}$, 其中 $d \neq d^{\prime}, d$ 阶的本原单位根和 $d^{\prime}$ 阶的本原单位根是不同的。本原单位根的定义保证了它不能通过较小的幂次得到 $1$ , 这意味着两个不同阶数的本原单位根不可能相等。
对于 $n$ 的每一个因数 $d$，一个 $d$ 阶的本原单位根 $\omega_d^e$ (其中 $e$ 是小于 $d$ 并与 $d$ 互质的整数), 也是一个 $n$ 阶单位根, 因为 $\omega_d^e=\omega_{d /(n / d)}^{e(n / d)}=\omega_n^{e(n / d)}$
从以上分析可知，所有 $n$ 的因数 $d$ 对应的 $d$ 阶本原单位根的乘积实际上构成了多项式 $x^n-1$ 的根（性质1.1）。因为 $x^n-1$ 的根包括了所有 $n$ 阶单位根, 而这些单位根又可以通过本原单位根表示。

在定理 3.2 的等式两端代入 $n=p$ ( $p$ 是素数), 由于 $p$ 的因子只有 1 和 $p$, 就有 $\Phi_1(x) \Phi_p(x)=x^p-1$, 由于 $\Phi_1(x)=x-1$, 因此我们得到了

$$\Phi_p(x)=\frac{x^p-1}{x-1}=x^{p-1}+x^{p-2}+\cdots+1$$

当 $n$ 比较小时, $\Phi_n(x)$ 的性状如下:

$$\begin{aligned} & \Phi_1(x)=x-1 \\ & \Phi_2(x)=x+1 \\ & \Phi_3(x)=x^2+x+1 \\ & \Phi_4(x)=x^2+1 \\ & \Phi_5(x)=x^4+x^3+x^2+x+1 \\ & \Phi_6(x)=x^2-x+1 \\ & \Phi_7(x)=x^6+x^5+x^4+x^3+x^2+x+1 \\ & \Phi_8(x)=x^4+1 \\ & \Phi_9(x)=x^6+x^3+1 \\ & \Phi_{10}(x)=x^4-x^3+x^2-x+1 \\ & \Phi_{11}(x)=x^{10}+x^9+x^8+x^7+x^6+x^5+x^4+x^3+x^2+x+1 \\ & \Phi_{12}(x)=x^4-x^2+1 \\ & \Phi_{13}(x)=x^{12}+x^{11}+x^{10}+x^9+x^8+x^7+x^6+x^5+x^4+x^3+x^2+x+1 \\ & \Phi_{14}(x)=x^6-x^5+x^4-x^3+x^2-x+1 \\ & \Phi_{15}(x)=x^8-x^7+x^5-x^4+x^3-x+1 \\ & \Phi_{16}(x)=x^8+1 \\ & \Phi_{17}(x)=x^{16}+x^{15}+x^{14}+x^{13}+x^{12}+x^{11}+x^{10}+x^9+x^8+x^7+x^6+x^5+x^4+x^3+x^2+x+1 \\ & \Phi_{18}(x)=x^6-x^3+1 \\ & \Phi_{19}(x)=x^{18}+x^{17}+x^{16}+x^{15}+x^{14}+x^{13}+x^{12}+x^{11}+x^{10}+x^9+x^8+x^7+x^6+x^5+x^4+x^3+x^2+x+1 \\ & \Phi_{20}(x)=x^8-x^6+x^4-x^2+1 \\ & \Phi_{21}(x)=x^{12}-x^{11}+x^9-x^8+x^6-x^4+x^3-x+1 \\ & \Phi_{22}(x)=x^{10}-x^9+x^8-x^7+x^6-x^5+x^4-x^3+x^2-x+1 \\ & \Phi_{23}(x)=x^{22}+x^{21}+x^{20}+x^{19}+x^{18}+x^{17}+x^{16}+x^{15}+x^{14}+x^{13}+x^{12}+x^{11} \\ & \quad+x^{10}+x^9+x^8+x^7+x^6+x^5+x^4+x^3+x^2+x+1 \\ & \Phi_{24}(x)=x^8-x^4+1 \\ & \Phi_{25}(x)=x^{20}+x^{15}+x^{10}+x^5+1 \\ & \Phi_{26}(x)=x^{12}-x^{11}+x^{10}-x^9+x^8-x^7+x^6-x^5+x^4-x^3+x^2-x+1 \\ & \Phi_{27}(x)=x^{18}+x^9+1 \\ & \Phi_{28}(x)=x^{12}-x^{10}+x^8-x^6+x^4-x^2+1 \\ & \Phi_{29}(x)=x^{28}+x^{27}+x^{26}+x^{25}+x^{24}+x^{23}+x^{22}+x^{21}+x^{20}+x^{19}+x^{18}+x^{17}+x^{16}+x^{15}+x^{14} \\ & \quad+x^{13}+x^{12}+x^{11}+x^{10}+x^9+x^8+x^7+x^6+x^5+x^4+x^3+x^2+x+1 \\ & \Phi_{30}(x)=x^8+x^7-x^5-x^4-x^3+x+1 \end{aligned}$$

直觉告诉你, 分圆多项式的系数一定在 $\{-1,0,1\}$ 的范围中 !
然而这却是假的。当 $n=105$ 时,

$$\begin{aligned} \Phi_{105}(x) & =x^{48}+x^{47}+x^{46}-x^{43}-x^{42}-2 x^{41}-x^{40}-x^{39}+x^{36}+x^{35}+x^{34}+x^{33}+x^{32}+x^{31}-x^{28}-x^{26}-x^{24}-x^{22}-x^{20} \\ & +x^{17}+x^{16}+x^{15}+x^{14}+x^{13}+x^{12}-x^9-x^8-2 x^7-x^6-x^5+x^2+x+1 \end{aligned}$$

进一步, 当 $n=463505=5 \times 7 \times 17 \times 19 \times 41$ 时, $\Phi_n(x)$ 的绝对值最大的系数竟有 $-17310!$ 这也可以说明分圆多项式在 $n$ 较大时的增长速度是非常迅猛的。
不过，虽然分圆多项式的系数很大，但是我们还是可以非常容易地求出它的值。因为如果对定理 3.2 的等式两端取对数，我们就能得到

$$\log \left(x^n-1\right)=\sum_{d, n} \log \Phi_d(x)$$

可以看出，这是一个 Möbius 变换 (Dirichlet 前缀和) 的形式。因此，我们尝试使用 Möbius 反转变换，即

$$\log \Phi_n(x)=\sum_{d \mid n} \mu\left(\frac{n}{d}\right) \cdot \log \left(x^d-1\right)$$

两边再取指数, 就有

$$\Phi_n(x)=\prod_{d \mid n}\left(x^d-1\right)^{\mu(n / d)}$$

于是我们就得到了一个计算 $\Phi_n(x)$ 的表达式。
而定理 3.2 中的式子是一个分解式，所有的分圆多项式都是在 $\mathbb{Z}$ 中不可约 (irreducible) 的。

参考

[1] https://yhx-12243.github.io/OI-transit/memos/17.html#mjx-eqn-2
[2] https://blog.csdn.net/ADjky/article/details/61198817