Newton 多边形与根的赋值

设想 $\alpha$ 的赋值为 $t$。在求和 $f(\alpha )$ 中，第 $i$ 项的赋值是 $v_p(a_i)+it$。若其中只有一个严格最小的值，该项就不可能被其余项抵消，因而 $f(\alpha )\ne 0$。能成为根的 $t$，至少要让两个系数项在最低位置相遇。

把直线写成 $y=-tx+c$，最高仍不超过所有系数点的那一条恰有截距 $c=w_t(f)$。当它只碰到一个顶点时，最低项唯一；当它沿着一条边时，最左和最右接触点相距 $r_t(f)-{\ell }_t(f)$。所以根赋值是边斜率的负数，长度则记录多少个一次因子能在这里贡献同样的赋值。

为什么最低系数不会在乘法中全部消失 ​

写 $g=\sum _j{b}_j{X}^j$，令 $A=w_t(f)$、$B=w_t(g)$。乘积的第 $k$ 个系数为 $c_k=\sum _{i+j=k}{a}_i{b}_j$，故强三角不等式给出

这个不等式还不够：若每个最低项都发生抵消，就可能永远取不到等号。为排除这种情形，选择 $k={\ell }_t(f)+{\ell }_t(g)$。项 $a_{{\ell }_t(f)}{b}_{{\ell }_t(g)}$ 的带权赋值正好为 $A+B$。任何另一组 $i+j=k$，必有 $i<{\ell }_t(f)$ 或 $j<{\ell }_t(g)$，因而至少一侧严格大于自己的最小值。于是选中的项是这一系数里唯一最低的项，无法抵消，式(3)在此取等号。

若 $k<{\ell }_t(f)+{\ell }_t(g)$，每一对指标都至少有一侧低于相应最小达到指标，所以该系数严格高于 $A+B$。这同时证明式(2)的第一、第二行。改取两个最大达到指标，完全相同的端点论证得到第三行。这里没有假设系数符号一致，也没有假设乘积的每个中间系数都不抵消。

从支持线到全部边 ​

对固定 $t$，直线斜率为 $-t$。它接触一条边时，该边长度就是 $r_t-{\ell }_t$；只接触一个顶点时这个差为零。式(2)使这个差在乘法下相加，因此逐个 $t$ 得到全部斜率的并集规律。

一次因子 $X-\alpha$ 的两个点是 $(0,v(\alpha ))$ 与 $(1,0)$，唯一斜率为 $-v(\alpha )$、长度一。若在已给赋值的域中写成 $a_n\prod _j(X-{\alpha }_j)$，重复使用乘法定律即得带重数的根结论。常数 $a_n$ 只把整张图上下平移，不改变斜率。

三次式中，只有一条边允许基域根 ​

在 $p=3$ 时取

四个系数点依次为

下边界连接 $(0,1)\to (2,0)\to (3,0)$，斜率分别为 $-1/2$ 和 $0$，长度分别为 $2$ 和 $1$。点 $(1,1)$ 在第一条边上方，不是顶点。

这意味着任何 ${\mathbb{Q}}_3$ 根必须赋值为 $0$，因为非零基域元素的赋值只能是整数，不能是 $1/2$。然而“允许赋值为零”还不是存在证明。模3有 $\overline{f}=X^2(X-1)$，余数1是简单根；Hensel 引理理路Hensel 引理：简单根的唯一提升Hensel's lemma · 亨泽尔引理模素数的简单根在指定余类内唯一提升为 p-adic 根，并以逐位递推计算 11-adic 的三的平方根。才提供该单位根。互素因子提升理路Hensel 互素因子提升Hensel factor lifting · Coprime polynomial Hensel lifting · 亨泽尔因子提升从互素首一模素数因子出发，逐位求解唯一系数修正，构造完整p-adic因子并交付有限精度乘积证书。进一步恢复一次与二次因子，并确认二次因子在 ${\mathbb{Q}}_3$ 上不可约。

对于已有延拓赋值的分裂域，另一条边表示两个赋值为 $1/2$ 的根。这与完全分歧二次域理路局部域与分歧Local field · 局部域由有限余数与完备性证明 p-adic 整数紧致，并直接构造 Q₃(√2)、Q₃(√3) 的赋值、整数环和剩余域，区分非分歧与完全分歧。中出现半整数赋值的现象一致；不能把“三个扩域根”改读成“三个三进数根”。

图中灰点不是顶点。蓝边的负斜率要求半整数根赋值，绿色水平边允许单位根；绿色根的存在仍由前面的简单根检验提供。

一条整数斜率边并不保证有根 ​

在 ${\mathbb{Q}}_3$ 上，$X^2-1$ 与 $X^2+1$ 的多边形都是从 $(0,0)$ 到 $(2,0)$ 的水平边。前者有根 $\pm 1$，后者没有根：若平方为 $-1$，赋值先迫使这个数为单位，降模3后便要求某个非零平方等于2，矛盾。多边形记录赋值，不能恢复剩余单位的全部信息。

相反，$X^2-3$ 的唯一斜率为 $-1/2$，仅用基域赋值为整数便能排除所有 ${\mathbb{Q}}_3$ 根。二次多项式因此不可约；在更高次数时，“没有根”通常不足以证明不可约，下面需要真正约束全部因子次数。

有限精度不能自动辨认所有系数 ​

若只知道某系数模 $p^N$ 为零，得到的是 $v_p(a_i)\ge N$，并不知道它真为零。若其他已知顶点已经给出一条在该横坐标处严格低于 $N$ 的下边界，这个下界足以证明未知点不会改变多边形；否则需要提高精度。

尤其不能把输入中显示的零截断无条件当成无限赋值。实际有限证书应列出每个顶点的精确赋值，以及其余系数高于相应支持线的可核下界。本页的整数算例则可直接求出非零系数的精确赋值。

单边斜率分母给出不可约证书 ​

假设 $f$ 的多边形只有一条边，其斜率化为最简分数 $a/b$，其中 $b>0$。若 $f=gh$ 且两个因子的常数项均非零，乘法定律迫使 $g,h$ 的所有边也具有同一个斜率。设 $\mathrm{deg}g=d$，则它的端点高度差为

左边是整数，$gcd(a,b)=1$，所以 $b\mid d$。这条整除约束对任意基域因子成立，无须先添入全部根。

特别地，若横向总长度为 $n$、两端高度差与 $n$ 互素，则 $b=n$，不存在次数介于1与 $n-1$ 的因子，$f$ 在 ${\mathbb{Q}}_p$ 上不可约。例如 $X^5+p^{2}X+p^2$ 的三个有限点是 $(0,2),(1,2),(5,0)$，中间点高于连线，斜率为 $-2/5$，因此对每个素数 $p$ 都得到五次不可约多项式。

互素条件有实际作用。$(X^2-p{)}^2=X^4-2p{X}^2+p^2$ 也只有一条斜率 $-1/2$ 的边，但明显可约；它的每个二次因子次数确实都被分母2整除。单边本身不足以推出不可约。

有理斜率的有限构造 ​

对于给定精确赋值的系数，从左到右将非零点放入栈。每加入一个新点，若栈尾连续三点的前一段斜率大于或等于后一段，就删掉中点，再检查新的末尾三点。两段斜率用整数交叉相乘比较，无须浮点除法；等号时删点正好合并共线边。

为什么可删除？在上述斜率条件下，中点位于连接两端的直线上方或线上，不能成为严格下凸边界的顶点。每个点至多入栈、出栈一次，所以在赋值已经给定后需 $O(n+1)$ 次精确整数比较和 $O(n+1)$ 个槽位。提取系数赋值、表示有理数以及大整数交叉乘法的位成本另计。

最终交付的证书很短：顶点列表、约分后的斜率及长度、所有其他点在边上方的检查。若要进一步交付具体因子，则使用互素剩余块提升；若对象变成无限级数，则需要闭球零点界理路Strassmann 定理与闭球零点界Strassmann's theorem · Strassmann theorem · 斯特拉斯曼定理对系数趋零的p-adic幂级数，以最后一个最大绝对值系数的指标界定闭单位球中的零点数，并给除根、缩放与尾界证书。同时处理无限尾部，不能只把有限折线无限延长。