杂谈计算机编程中的多项式算法

Galois_Field_1048576 · 2025-03-02 21:36:57 · 个人记录

本文中, 设 \omega 是矩阵乘法的复杂度.

本文将尝试从数学的角度, 谈论计算机编程中的多项式算法, 以理论为主. 多项式算法是维护有限元多项式环 R[\mathcal X] 或其商去特定理想 R[\mathcal X]/I 的算法. 多项式算法围绕快速 Fourier 变换, 这将是我们首先介绍的:

1. 快速 Fourier 变换

1.1 一般理论

快速 Fourier 变换来源于一个重要观察:

定理 (Maschke). 设 G 是有限群, \Bbbk 是域, |G| 在 \Bbbk 中的像非 0, 则 G 的任意 \Bbbk-表示半单.

证明. 注意到 \Bbbk 是域, 进而只需证其任意子表示都是其直和项. 设表示 V, 子表示 U, 作为空间的投影 \pi : V \to U. 我们给出调整 \pi 的一种方式, 使得得到的映射 \tau 满足 \ker \tau 是 V 的子表示: 取平均化

可以验证这个映射给出 \Bbbk-同态, 进而 \ker \tau 是 V 的子表示, 进而 U 是 V 的直和项.

推论. 设 G 是有限群, \Bbbk 是域, |G| 在 \Bbbk 中的像非 0, G 的所有不可约表示是 U_i, 则

证明. 注意到 \Bbbk[G] 有自然表示 G \to \operatorname{End} \Bbbk[G], 有所有的不可约表示都是 \Bbbk[G] 的子表示, 且由于是不可约表示, 它们直和起来可以得到自然表示, 进而

比较维度可得.

这意味着, 如果我们用在每个不可约表示处的值来替换原来群代数中的值 x \in \Bbbk[G], 我们计算群代数 \Bbbk[G] 中乘法的复杂度会从 \Theta(|G|^2) 下降到 \Theta(\sum (\dim U_i)^\omega). 这被称为 Fourier 变换, 记作 x \mapsto \hat x. 既然我们朴素地去做 Fourier 变换的复杂度是 \Theta(|G|^2) 的, 我们就考虑如何快速地做 Fourier 变换.

具体地, f : G \to \Bbbk 的 Fourier 变换定义为

而 \hat f \in \bigoplus_{\rho \in \mathcal R} \operatorname{End} V_\rho 的逆 Fourier 变换定义为

首先考虑 H \le G, 考虑其一组陪集分解 C = \{s_i\}. 自然我们可以得到

问题是, \rho|_H 不一定不可约, 所以它会是一些矩阵的直和. 我们只需要找到基 \mathfrak B, 将 \hat x_\rho 对应的矩阵转成 \hat x_{\rho|_H} 的分块对角矩阵即可. 对于具体的群, 我们会具体构造.

时间上, 我们有

进行一些简单的放缩可知:

注意到 G 的最大不可约表示的维度不能超过 \sqrt{|G|}, 所以

定理 (Lev). 如果 G 不是形如 \mathbb Z/ p \mathbb Z 的群, 则存在一个大小至少为 \sqrt{|G|} 的真子群.

证明. Lev 直接使用了有限单群分类定理, 逐一攻破. 故我们按下不表.

如果带入 |H| = \sqrt{|G|}, 定理会变为

即 T(n) \sim n^{3 \omega / 4}. 当 \omega \le \dfrac 83 时, 它才会更优. 当然, 实践上 |H| 取到 \sqrt{|G|} 时会很劣. 如果 G 的每一个子群 H 有 |H|^\theta 量级的真子群, 则

即 T(n) \sim n^{\omega(1-\theta/2)}. 当 \omega 取 3, \theta \ge \dfrac 23 时, 它会更优. 实践上这对于大多数群都是可行的.

1.2 一般快速 Fourier 变换

本节假设 \Bbbk 代数闭, 且 \Bbbk 的特征充分大或为 0.

群表示论的基本常识告诉我们, 在 G 能嵌入 \Bbbk^\times 时, G 的全部不可约表示都是 1 维表示. 事实上, 这在 G = \mathbb Z/n \mathbb Z 有着更初等的表达方式:

通过中国剩余定理.

由于有限 Abel 群时涉及的表示只有一维表示, 所以任何表示的限制仍然不可约, 也就是说我们无需考虑基 \mathfrak B. 因此, 我们可以直接利用

分解. 设 G = \mathbb Z/n \mathbb Z. 若 \rho 是 g + n \mathbb Z \in G 对应的特征标, 则 \rho(h + n \mathbb Z) = \exp(gh \mathrm i \tau / n) 是自然的构造. 带入得

其中, n \in m \mathbb Z. 这样的时间复杂度自然为

实践上, 计算一般的 \Bbbk[\mathbb Z/n \mathbb Z] 常常通过 \operatorname{mod} (X^n - 1) 的 \Bbbk[X] 来实现, 而 \Bbbk[X] 通过一个充分大的 \mathbb Z/N \mathbb Z 来实现 (N > 2n), 而取 N = 2^k 时一般是常见的, 此时

成为快速 Fourier 变换的一般实现. 下面将讨论高速实现之的一些办法: 设 N = 2^k, 二进制表示下 x \in \mathbb Z / N \mathbb Z 是 x_{k-1} x_{k-2} \dots x_1 x_0, 得到:

而 x_{k - 1} + 2 \mathbb Z 最先被处理, x_{k-2} + 2 (x_{k - 1} + 2 \mathbb Z) 次之, 所以处理顺序为:

这个值记作 \operatorname{rev}(x). 这样下去, 我们只需要将第 x 个值与第 \operatorname{rev}(x) 个值交换, 然后每个 0 \le j < k 进行相邻 2^j 的元素变换即可.

1.3 小特征有限域下的快速 Fourier 变换

当 p - 1 的因子充分小时, 可以通过上一节所讲的快速 Fourier 算法来计算, 因为我们只需要多项式 X^n - 1 在 \Bbbk 中分解成一次因式. 现在我们复述 David G. Cantor 与一些其他后来者在 p^{p^k} 元有限域上进行的加性 Fourier 变换. 本节, 记 \mathbb K = \mathbb F_{p^{p^k}}, \mathbb F = \mathbb F_p.

定义. \mathbb K \to \mathbb K 有一个典范的线性同态, 名为 Artin-Schrier 变换, 记作 \wp, 其定义为 \wp(x) = x^p - x. 其 i 次复合

命题. s_i = 0 的解的全体构成一个 \mathbb F-线性空间. 这个线性空间是 \mathbb K 的子域当且仅当 i = p^j.

证明. \wp 是线性同态导出 s_i 也是, 故第一个断言得证. 关于第二个: 当 i = p^j 时 s_i(x) = x^{p^i} - x , 同时 \mathbb K 只包含大小为 p^{p^j} 的子域.

定义. 子空间 W_i = \ker s_i. 此时我们定义 p^{i} 次多项式 p 的加性 Fourier 变换 \mathcal A(p) 为 p(\omega_i)~(\omega_i \in W_i) 的有序集合.

定义. \mathbb K 的一组 Cantor 生成元, 是满足

的 \{g_j\}, 其中 \deg f < i(p - 1), 且不存在 g_i 的 \ge p 次方项. 它诱导出了 \mathbb K 的 Cantor 基:

定理. 存在 \lambda \in \mathbb F, s_j(b_k) - \lambda b_{k-j} \in W_{k-j}, 特别地, 设 k = j 得 s_k(b_k) = 1. 也可以用简单的推理导出 W_k = \operatorname{span} \{ b_0, \dots, b_{k-1} \}.

这个定理的证明我们略去. Cantor 证明了满足条件 \wp(g_0) = 0, \wp(g_{k + 1}) = g_k^M, 其中

的 \{g_k\} 是 Cantor 生成元. 用这个序列可以导出 Cantor 基, 以及一个对应于之的 p^k 次不可约多项式.

注意到 p^D 次多项式的基有其对应的生成元 g_k = \wp^k = s_k, 即按照二进制可以从 g_k 导出 p^D 次多项式全体的线性空间的基. 这组基我们记作 X_i. 我们首先给出 < p^D 次多项式和 (X_i) 的基线性表示的快速双射 (朴素做法为 \Theta(D^2 p^D \operatorname{poly}(p)), 而快速算法为 \Theta(D p^D \log D \operatorname{poly}(p))): 我们首先考虑 p^{D-1} 次多项式 s_{D-1}. 那么对于 < p^D 次多项式 f, 我们可以写

这个基的变换可以 p^D \operatorname{poly}(p) 地暴力去做. 然后对每一个 f_i 的变换进行拼接, 并利用 s_is_j = X_{2^i+2^j} 即可.

现在我们专注于如何计算一个陪集上的加性 Fourier 变换. 在理论推导上:

这就得到了和原版 FFT 类似的形式, 因此可以直接依此式分治.

例如 \mathbb F_{2^{64}} 的 Nim 乘积构成的域的 Fourier 变换常常使用 Cantor 算法进行.

1.4 Frobenius 变换优化的 Fourier 变换

我们称 m 次 Frobenius 变换为 \sigma : \alpha \to \alpha^{p^m}.

称 \alpha, \beta \in \mathbb K 共轭, 若存在 \sigma \in \operatorname{Aut}(\mathbb K) = \operatorname{Gal}(\mathbb K|\mathbb F) 使得 \sigma(\alpha) = \beta. 则我们有如下的命题:

命题. 考虑 \alpha \in W_k \setminus W_{k - 1}, 则 \alpha 的共轭元个数为

证明. 考虑其对应的 Cantor 生成元. 显然有

因此 \alpha 的稳定化子是由 p^{\lceil \log_p k \rceil} 次 Frobenius 变换生成的群, 根据轨道-稳定化子定理, 轨道大小为 p^{\lceil \log_p k \rceil}.

进一步, 这 p^{\lceil \log_p k \rceil} 个元素受到 \lceil \log_p k \rceil 个 Frobenius 变换的影响, 它们的次数分别为:

其中次数为 p^i 的 Frobenius 变换可以修改 \alpha 在 Cantor 基下的第 k - 1 - p^i 个坐标. 这是因为, 如果把 \alpha 和 \alpha^{p^{p^i}} 加起来, 则相当于 s_{p^i}(\alpha). 由于 \alpha 的 k - 1 个坐标不为 0 (\alpha \in W_k \setminus W_{k - 1}), 所以 s_{p^i}(\alpha) 的 k-1-p^i 号坐标不是 0, 可见 \alpha 和 \alpha^{p^{p^i}} 在 k-1-p^i 号坐标下不同. 可以说明, 如果重复应用这个 Frobenius 变换, k-1-p^i 位将会取遍 \mathbb F. 所以应用这些 Frobenius 变换后可以确定地修改第 k-1-p^i 号坐标, 注意到这些坐标的组合就已经共有 |\mathbb F|^{\lceil \log_p k \rceil} = p^{\lceil \log_p k \rceil} 个了, 因此 Frobenius 变换可以直接被这些坐标的变换分类.

现在考虑

注意到在 Frobenius 变换的同一个同构类下的元素, 得知其中一个的加性 Fourier 变换的前提下, 得知其它的是简单的. 而我们知道 Frobenius 变换可以直接被特定位置坐标的变换分类, 所以可以考虑一个商集代表元的刻画:

这样, 不难验证 \Sigma 中的一个元素经过 Frobenius 变换可以得到整个 W_m. 因此, 在计算加性 Fourier 变换时, 如果遇到坐标为 p^k, 我们可以直接递归单侧, 可以将时间变为原来的 \dfrac pd, 其中 d = \lceil \log_p n \rceil.

介绍了梗概后, 更详细的讨论可见 这里 的论文与 这里 的代码.

事实上, 本节介绍的加性 Frobenius Fourier 变换源于 Frobenius Fourier 变换, 其原始论文为 这里.

对于算法竞赛中常见的 Nim 积域 \mathbb F_{2^{64}}, Cantor 基的形式是简单的: 1, 2, 4, 8, \dots. 因此, 这两个算法可以给出 Nim 积多项式乘法的一个简易方法.

1.5 任意环

作为我们之前说的 David G. Cantor 的同一人, 他还给出了在一般环 R (甚至可以除去结合性) 上进行的快速多项式乘法算法. 取定基数 s \in \Theta(1). 我们现在的问题在于, 首先我们需要除法, 然后我们需要单位根. 对于除法我们尝试规避, 对于单位根我们尝试扩环.

注意到 Fourier 反演公式中, 除了一个 \dfrac 1n\ (n = s^r) 的系数以外不需要除法. 因此考虑多项式 A, B \in R[X]/(X^n-1), 我们其实可以得到 n [X^k] (AB), 即设前 n 项中的 k 次多项式系数为 c, 进位超过 n 项中的 k+n 次多项式系数为 c', 那么我们可以得到 n(c+c') 的值. 另外, 我们可以依照同样的算法流程考虑 A'(X) = A(X \omega_{ns}), B'(X) = B(X \omega_{ns}), 我们可以知道 n(c+\omega_s c') 的值. 解二元一次方程组, 我们可以在只使用环运算的前提下得到 n(1-\omega_s) c 和 n(1-\omega_s) c' 的值. 我们现在断言: 存在 \chi \in R 使得 (1-\omega_s) \chi \in \mathbb Z \setminus \{0\}. 断言的证明是:

现在我们可以求得 ac 和 bc, 其中 a \perp b, 所以通过 Bézout 引理可以求得 c.

现在尝试采用扩环解决单位根问题. 考虑扩环 \overline R = R[\omega_n] = R[X]/(\Phi_n). 注意到 DFT 的过程只需要加减法和乘以单位根, 而乘以单位根在扩环的意义下是循环移位. 考虑 R[X]/(X^{pq}-1) \simeq R[X, Y]/(X^q-Y, Y^p-1), 观察到商 Y^p-1 的一个根是扩 \omega_p. 我们首先把它当做一个 (R[X]/(\Phi_p))[Y], 而根据我们刚才的 DFT 算法, 不难发现复杂度其实是 \Theta(\mathrm{polylog}(pq)) 地计算的 DFT. 现在我们唯一需要的就是计算两个扩张 \omega_n 的整数的乘积, 而这可以进行递归.

关于一般环上的算法, 还有一个很有趣的实例: Toom--Cook 算法. 二者均共享了一个基本的思路: 将 R[X] 的 X^n = Y 提出来, 然后尝试带入 Y 的点值以得到一个结果. 如果我们固定多项式 p 对于 Y 的系数是 k 次, 那么我们需要 2k+1 个点值以恢复乘积多项式的信息 (这里我们直接得到乘积多项式而不是其 \bmod (X^n-1) 的结果), 那么这个算法的时间复杂度为

EI 在其 blog 中给出了 T(n) \sim n 2^{\mathrm O(\sqrt{\log n})} 的上界.

1.6 对称群

我们不予证明对称群的不可约表示结构定理. 这里, 我们认为 Young 图是 r_1 \ge \dots \ge r_n 的数列, 而 Young 表是其中填上数的结果. 我们设一个 Young 表中 c(i) 表示 i 的位置的纵坐标减去横坐标的结果.

定理. 设 Young 图 \lambda, 其对应的不可约表示 \rho_\lambda 在 \sigma = (k\ k+1) 这一对换上的矩阵表示为: 这个方阵的维度是 \lambda 的标准 Young 表数, 因此我们用这样的 Young 表来标记行列. 如果按照 \sigma 的办法将 \lambda 中的数重排, 得到的表是标准 Young 表, 则记 R = 1, 否则 R = 0, 那么 \rho_\lambda(\sigma) 的矩阵表示 A 满足:

Clausen 对对称群 Fourier 变换给出了一套算法, 他构造了这样一个映射: \mathfrak S_n \to \mathfrak S_{n - 1}, \sigma 映射到把 n 从 \sigma 中抽离得到的置换, 例如 2\ 5\ 4\ 3\ 1 \to 2\ 4\ 3\ 1. 我们可以用轮换

来表示这一点. 我们在 1.1 讨论的一般群上的算法中, 我们要找到基, 使得 \mathfrak S_n 到 \mathfrak S_{n - 1} 把不可约表示转成不可约表示的分块对角矩阵. Clausen 发现, 这个基是遗传的, 也就是说, 在矩阵表示下, 如果我们要找到 A = P D P^{-1} (表示基变换), 那么 P 恰好为 I!

简要证明. 注意到 Young 图中一个位置 n 是可能位置的充要条件是其右和下均无方块. 按照这样的位置, 我们可以将 \lambda 对应的所有 Young 表分类. 现设 \sigma \in \mathfrak S_{n-1}, 这样 \sigma(\lambda) 的 n 位置和 \lambda 相同, 因此它们所归属的类相同. 因此 \rho_\lambda(\sigma) 这个矩阵是分块的, 并且不难验证这每一块对应一个 \mathfrak S_{n-1} 的不可约表示 (带入 \sigma 的结果).

对于较为稀疏的 f 值输入, 我们会尝试使用例如

的双陪集把 f 缩小大小, 这样我们可以有更高的自由度对于无需 Fourier 变换的群进行操作. \mathbb S_n \mathtt{ob} 是对称群卷积库的经典.

一篇名为 \mathbb S_n \mathtt{FFT} 的论文认为这种卷积在机器学习中有应用: 我们将喜好排序表示为 \mathfrak S_n 中的置换, 则对于置换 \sigma, 置换 \tau 的接纳度为

并且设 f_\sigma 为这样的 \mathbb R^{n!} 向量. 聚类问题是将这 m 个喜好划分为 k 类的问题, 使得

最小.

然后我们应用有限群的 Parseval 定理:

定理. 设 f : G \to \mathbb C, 取一组 unitary 表示 \mathcal R, 则:

其中下标 HS 的范数为 Hilbert--Schmidt 范数, 表示矩阵元的平方和.

证明. 首先 Peter--Weyl 定理, L^2(G) 有一组正交直和分解为 \sqrt{d_\pi} \pi. 例如我们取 e(\pi, i, j) 为 \pi(g) 的矩阵表示的 (i, j) 矩阵元, 则 f 可以分解为 \langle f, e(\pi, i, j) \rangle e(\pi, i, j), 对这个系数进行计算得

这样, 计算其 L^2-范数, 等于诸系数的平方和, 即

得证.

因此, 聚类问题等价于

一般而言, 我们只需要少量的 \pi 的结果就能得到较准确的近似结果, 因此我们认为这个方法可以优化计算时间.

2. 多项式 Newton 迭代

本部分的前三节担任了赋值域论入门的责任.

2.1 赋值域的基本操作

一个域 \mathbb K 的一个赋值是衡量这个域中的元素 \mathbb K 有在某一视角下多么可忽略. 直觉上, 当 \nu(x) \to \infty 时 x \to 0. 它将一个元素 x \in \mathbb K 带到一个有序的 Abel 群 (加入无穷大元素) \nu(x) \in \Gamma \sqcup \{ \infty \} (具体地, 通过规定一个加法封闭且有三岐性的正锥). 这个赋值应当满足这样的性质:

这样对 \mathbb K 有一个拓扑 \lim a = \lambda \iff \nu(a_n - \lambda) \to \infty, 对此极限封闭的集合成为此集合中的闭集. 它有许多等价定义方案, 比如由非 Archimedes 范数 |x| = -\exp(\nu(x)) (当 \Gamma \hookrightarrow \mathbb R 时) 定义的度量空间极限, 以及用 \alpha + \nu^{-1}(\Gamma_{> x}) 为拓扑基的直接构造拓扑. 当然, 一般而言 \mathbb K 没有我们想要的分析学性质, 比如 \mathbb K 是全不连通空间, 以及当 \mathbb K 完备 (Cauchy 列收敛) 时, 有无穷级数 \sum a 收敛 \iff a \to 0.

对于 \mathbb K, 我们可以定义其整数环 \mathcal O_{\mathbb K} = \nu^{-1}(\Gamma_{\ge 0}), 它有唯一的极大理想 \mathfrak m = \nu^{-1}(\Gamma_{> 0}), 并且有剩余类域 \kappa = \mathcal O_{\mathbb K} / \mathfrak m. 对于 Cauchy 拓扑的完备化, 我们存在自然的同构 \mathcal O_{\widehat{\mathbb K}} \simeq \widehat{\mathcal O_{\mathbb K}}, 这是通过证明合成 \mathcal O_{\mathbb K} \to \mathbb K \to \widehat{\mathbb K} 是完备化完成的.

自然, 我们要谈赋值就离不开绝对值, 它是诸如 |x| = 0 \iff x = 0 且满足三角不等式的乘法同态. Ostrowski 给出了两个重要的分类定理: 其一分类了 \mathbb Q 上的绝对值, 只有 p-进绝对值 |x|_p = \sup \{ r : x \in p^r \mathbb Z \}\ (p \in \mathbb P), 和 \infty-进绝对值, 即通常的绝对值. 其证明为: 对于非 Archimedes 绝对值, 单位闭圆盘 \{n \in \mathbb Z : |n| < 1\} 是 \mathbb Z 的素理想. 这个素理想诱导了等价于 |\cdot|_p 的绝对值; 对于 Archimedes 绝对值, 常用的技巧是通过乘性良定义一个 c = \dfrac{\log |x|}{\log x}\ (x \in \mathbb Z_{> 1}), 然后通过一个严谨的极限论证 |x| = |x|_\infty^c 永远成立. 其二分类了所有的 Archimedes 完备域 \mathbb K, 认为有且仅有 \mathbb R, \mathbb C. 这个证明的思路与代数基本定理的一个分析证明很相似. 为了证明所有的 \mathbb K 均是实二次方程的根, 通过构造一个待定系数的二次方程 X^2 - (z + \overline z) X + |z|^2 = 0\ (z \in \mathbb C) 并带入 X \in \mathbb K 得到一个关于 z 的函数 f(z). 其最小值须为 0, 否则可以通过调整法得到一个更小的值, 然后即可视 \mathbb K 为 \mathbb R-代数.

当我们进行扩域时, 一定存在赋值的延拓. 设 \mathbb K|\mathbb F. 考虑 \mathcal O_{\mathbb F}[(\mathfrak m^\complement)^{-1}] \subseteq A \subseteq \mathbb K, 并且给出一个 \mathfrak m \mathcal O_{\mathbb F}[(\mathfrak m^\complement)^{-1}] \subseteq \mathfrak a \subseteq A 的理想. 利用 Zorn 引理易知其中存在极大元, 设为 (\mathcal O, \mathfrak n), 则 \mathfrak n 自然是极大理想. 则 \mathfrak n^\complement = \mathcal O^\times, 这是因为如果 y \notin \mathcal O^\times, 则由于 \mathfrak m[y^{-1}] y^{\text{充分大}} \subseteq \mathfrak m, 所以 1 \notin \mathfrak m[y^{-1}]; 这样 (\mathcal O[y^{-1}], \mathfrak m[y^{-1}]) 与原来的二元组的极大性矛盾. 然后考虑 \alpha \in \mathbb K^\times, 换元后乘以 \alpha^{\text{充分大}} 可知一旦 \alpha^{\pm 1} \notin \mathcal O, \mathfrak n \cdot \mathcal O[\alpha^{\pm 1}] \ne \mathcal O[\alpha^{\pm 1}], 然后因为极大性可构造对应扩张, 这样我们可以得到一个分式域为 \mathbb K 的环 \mathcal O, 它满足条件 \mathcal O \cup \mathcal O^{-1} = \mathbb K. 让我们考虑乘法商群 \Gamma = \mathbb K^\times / \mathcal O^\times, 然后定义 x \preceq y \iff \dfrac yx \in \mathcal O, 这样给出 \Gamma 的一个序结构. 自然的商映射给出了我们所欲的赋值.

我们给出一个例子: 对于域 \mathbb Q 和 \mathbb Z 的素理想 \mathfrak p, 我们定义过 \nu_{\mathfrak p}. 对于这个赋值的完备化为所谓的 \mathfrak p-进有理数域 \mathbb Q_{\mathfrak p}. 对于 \mathfrak p-进有理数域, 在科普视频中最为常见的解释为: 小数点前存在无限位的类似于实数的数. 一个典型的例子为:

关于例子的计算, 是暴力的进行逐项累和的结果. Python 源码如下:

def exp4(prec):
    mod, S, fact, n = 2**prec, 0, 1, 0
    while True:
        if n == 0: term = 1
        else:
            fact *= n
            fact_v2 = v_fact(n)
            u, v = fact >> fact_v2, 2 * n - fact_v2
            if v >= prec: term = 0
            else:
                inv_u = modinv(u, 2 ** (prec - v))
                term = (pow(2, v, mod) * inv_u) % mod
        S = (S + term) % mod
        if term == 0 and n > 5 or n > prec + 20: break
        n += 1
    return S

提到 \mathfrak p-进数我们将提到 Witt 环的概念. 这是我们提升 \mathbb Z/{\mathfrak p} 到 \mathbb Z_{\mathfrak p} 的工具. 我们直接从 A \subset \mathbb Z_{\ge 1} 对整除封闭时考虑. Witt 向量的定义为 R^{\mathbb Z_{\ge 1}}, 其在 A 上的限制我们称为截断, 但我们对 Witt 向量构成的环不会使用逐点乘, 而是赋予一个不同的乘法, 我们对其的勾勒为:

我们规定其性质为使得幽灵分量

并要求环结构使得幽灵分量为同态. 香蕉空间的 Witt 环页面给出了这两个多项式的构造.

本小节的最后, 我们给出 p-进数出人意料的一个应用:

定理. \sqrt 2 是无理数.

证明. 请在 Hippasus 容量充足的前提下阅读这个证明. 注意到 \mathbb Q \hookrightarrow \mathbb Q_3, 所以只需证 X^2 - 2 = 0 在 \mathbb Q_3 中无解. 设其解为 \alpha, 则 \nu_3(\alpha^2) = \nu_3(2) = 0, 即 \nu_3(\alpha) = 0 \implies \alpha \in \mathbb Z_3, 而其 3^0 分量 c 满足 c^2 \equiv 2 \pmod 3, 这与可以一一列举的事实矛盾.

这个证明完全是抽象废话. 读者可以尝试剥离其抽象废话部分, 给出其内核的证明.

2.2 Hensel 引理

本节取定 \Gamma = (\mathbb R, +). 本节的主要内容是给出 Hensel 域的大量刻画.

我们在这里给出 Hensel 域的第一个等价定义:

定义 0. 称 \mathbb K 是 Hensel 域, 如果对于一个首一多项式 f \in \mathcal O_{\mathbb K}[X], 如果存在首一分拆 f = \overline g \overline h \bmod \mathfrak m, 其中 \overline g \perp \overline h, 则存在 f = gh, 使得 \bmod \mathfrak m 意义下 g \equiv \overline g, h \equiv \overline h, \deg g = \deg \overline g.

等价定义 1. \mathbb K 是 Hensel 域当且仅当每个有限生成 \mathcal O_{\mathbb K}-模 A, 如果 A 是代数, 则它是有限个局部 \mathcal O_{\mathbb K}-代数之积.

等价定义 2. \mathbb K 是 Hensel 域当且仅当对任意整同态 \mathcal O_{\mathbb K} \to A, A/\mathfrak mA 的幂等元都能提升到 A.

证明. 后文, 取定剩余类域 \mathbb k = \mathcal O_{\mathbb K} / \mathfrak m.

我们首先证明 0 \implies 2. 考虑幂等元 e \in A / \mathfrak mA, 以及原象 f \equiv e \pmod{\mathfrak m}. 设多项式 p \in \mathcal O_{\mathbb K}[X] 使得 p(f) = 0, 这样我们有同态 \mathcal O_{\mathbb K}[X]/(p) \to A, 进而基变换给出 \phi : \Bbbk[X]/(\overline p) \to A / \mathfrak m A, 考虑 e 对应的开闭集在 \operatorname{Spec} \phi 下的像, 它也会是一个开闭集, 对应于一个幂等元 x \in \Bbbk[X]/(\overline p). 这样, 我们现在将 e 的提升问题转化为 x 的提升问题. 此时当 x 幂等时, x(x-1) \equiv 0 \pmod \overline p, 这是域上的多项式, 所以我们得到首一互质分解 q_1q_2 = \overline p. 根据定义 0 知提升为 p_1p_2 = p, 因此存在同态 O_{\mathbb K}[X]/(p) \to O_{\mathbb K}[X]/(p_1) \times O_{\mathbb K}[X]/(p_2), 两侧均平坦, 而利用中山引理得模 \mathfrak m 同构给出本身同构. 递归下去即可.

然后我们证明 2 \implies 1. 设 A 是有限生成 \mathcal O_{\mathbb K}-模, 同时是 A-代数. 则 A/\mathfrak mA 是 \Bbbk-代数, 进而 Artin, 记作 \prod L_i, 其中每一个 L_i 局部. 设仅在第 i 个分量为 1 的元素 e, 则 \sum e = 1 给出了积分解, 根据等价定义 2, 这些元素根据其幂等性可以提升到 A 上, 这样我们可以得到 \sum E = 1, 进而给出积分解. 只需验证这个积分解为局部代数的积分解: 整同态素理想上行, 每一个 A 的积分解项的极大理想都包含 A/\mathfrak mA 的积分解项的极大理想, 遂给出唯一的极大理想.

最后证明 1 \implies 0 以完成证明. 取定首一多项式 f \in \mathcal O_{\mathbb K}[X], 对 \mathcal O_{\mathbb K}[X]/(f) 进行局部分解 (等价定义 1) 得到 \prod L_i. 将积分解 \bmod \mathfrak m 得每一个 L_i 对应于 \operatorname{Spec} \Bbbk[X]/\overline f 的一个点, 进而整个环对应于有限个点 E. 那么 f = \overline g \overline h \bmod \mathfrak m 给出 E 的一个分划, 进而给出积分解 \mathcal O_{\mathbb K}[X]/(f) = A_1 \times A_2, 其中 A_1 / \mathfrak m A_1 = \Bbbk[X]/ \overline g, A_2 / \mathfrak m A_2 = \Bbbk[X]/\overline h. 根据 \mathcal O_{\mathbb K}[X]/(f) 的构造知它作为模有限秩自由, 因此 A_1, A_2 也. 按照 X 在 A_1, A_2 上投影的 0, 1, \dots, n-1 次得他们是 A_i / \mathfrak m A_i 的基, 进而根据中山引理是 A_i 的基. 按照 x^n 的坐标即可得到提升 f = gh.

等价定义 3. 设 f \in 1+X+X^2 \mathfrak m[X], 则 f 存在一个根 \alpha 使得 \alpha \bmod \mathfrak m = -1.

等价定义 4. 对于每一个首一多项式 f \in \mathcal O_{\mathbb K}[X], 对 b \in \mathcal O_{\mathbb K} 使得 \nu(f(b)) > 2 \nu(f'(b)), 那么 f 存在一个根 x \in \mathcal O_{\mathbb K}, 使得 \nu(x - b) > \nu(f'(b)).

等价定义 4 弱化. 对于每一个首一多项式 f \in \mathcal O_{\mathbb K}[X], 对 b \in \mathcal O_{\mathbb K} 使得 \nu(f(b)) > 0, \nu(f'(b)) = 0 (换句话说, \overline b 是 \overline f 在 \Bbbk 中的单重根), 那么 f 存在一个根 x \in \mathcal O_{\mathbb K}, 使得 x 与 b 在 \bmod \mathfrak m 意义下相等.

证明. 0 \implies 3 来自要求 \overline g = 1+X, 而 \deg g = \deg \overline g = 1 遂得 g 的一个根 r 延拓到 f 上, 而显然的验证知 r \equiv -1 \pmod{\mathfrak m}.

我们来证明 3 \implies 4. 考虑利用代数方法得到的类似 Taylor 展开的等式

我们尝试换元 Y = \dfrac{f'(b) \varepsilon}{f(b)}, 同时带入 X = b, 得

而条件给出 \dfrac{f(b)}{f'(b)^2} \in \mathfrak m, 即

至此, 我们将 h(Y) = \dfrac{f(b + \varepsilon)}{f(b)} 写成了 1 + Y + Y^2 \mathfrak m[Y] 的形式, 它有一个根 r, 而我们所断言的 f 的根是其对应的 b + \varepsilon. 不难验证它满足条件.