子结式多项式余式序列

形式陈述

设 $D$ 为可执行精确运算与精确标量除法的整环， $A,B\in D[x]$ 非零， $m=\deg A\ge n=\deg B$ ， $b=\operatorname{lc}(B)$ 。当 $b$ 未必可逆时，伪除法在 $D[x]$ 内构造 $Q,R$ 使

b^{m-n+1}A=QB+R,\qquad \deg R<n.

$R=\operatorname{prem}(A,B)$ 称伪余式。一般多项式余式序列写成

R_0=A,\quad R_1=B,\qquad \alpha_iR_{i-1}=Q_iR_i+\beta_iR_{i+1},

其中 $\deg R_{i+1}<\deg R_i$ 。若简单地反复取带符号伪余式，先前首项的高次幂会作为可预测公因子留在新系数中，造成 coefficient swell。

下面固定一套 Brown–Traub 符号和下标，避免把不同约定的缩放因子混用。先处理边界：零输入的 GCD 由另一输入规范化得到；两个输入都为零时约定 GCD 为零。交换输入可使次数不增；常数除数的下一伪余式为零。对非零输入置

R_0=A,\quad R_1=B,\quad \delta_1=\deg R_0-\deg R_1,\quad \psi_1=-1,\quad \beta_1=(-1)^{\delta_1+1}.

第 $i\ge1$ 轮计算

R_{i+1}=\operatorname{prem}(R_{i-1},R_i)/\beta_i.

若它为零便停止，且不再对它取次数或首系数；否则令

\begin{aligned} \delta_{i+1}&=\deg R_i-\deg R_{i+1},\\ \psi_{i+1}&=(-\operatorname{lc}R_i)^{\delta_i}\psi_i^{\,1-\delta_i},\\ \beta_{i+1}&=-\operatorname{lc}(R_i)\psi_{i+1}^{\delta_{i+1}}, \end{aligned}

再进入下一轮。 $\delta_i>1$ 时， $\psi$ 的式子表示除以 $\psi_i^{\delta_i-1}$ ； $\delta_i=1$ 时直接取 $-\operatorname{lc}R_i$ ；初始次数相等而 $\delta_1=0$ 时取 $\psi_2=\psi_1=-1$ 。子结式定理保证这些标量除法和伪余式除法精确，所得系数仍在 $D$ 中。它们不是把每个余式任意首一化：保留规定缩放，才保留后续子结式信息。[2, §7；3, Theorems 2–3]

每个非零余式次数严格下降，故过程有限。在分式域中，所有 $\beta_i$ 和被乘的首项幂均非零，递推保持 $\gcd(R_{i-1},R_i)$ 的相伴随类；最后非零项首一化后就是分式域上的 GCD。若 $D$ 是可计算内容的 UFD，要恢复 $D[x]$ 中的GCD，还须乘回输入内容的 GCD：

\gcd_{D[x]}(A,B)\sim \gcd_D(\operatorname{cont}A,\operatorname{cont}B)\, \operatorname{pp}(R_{\mathrm{last}}).

这里 $\operatorname{pp}$ 是除去系数公因子的本原部分， $\sim$ 表示只差 $D$ 的单位。比如 $2x+2$ 与 $4x+4$ 的 GCD 是 $2x+2$ ，只取本原部分 $x+1$ 会丢掉公共内容 $2$ 。[2, §3]

算法以稠密系数向量做伪除、精确标量除法和内容规范化，并调用多项式乘法完成移位乘积。子结式的行列式解释控制系数大小：这些余式对应带规定下标的 Sylvester 子式。次数异常下降时，一个余式的实际次数可能小于其子结式下标，故还要区分“末项是常数”与“已得到零次子结式”。

直觉

域上的 Euclidean 算法随时可以除以除数首项，把余式重新首一化；整数环上这样做会引入分数。伪除法用首项的幂提前乘被除式，把所有步骤留在整数中，但代价是把许多“清分母用”的因子一起带进下一轮。primitive PRS 每轮计算全部系数的内容再除掉，系数很小，却反复做昂贵的整数 GCD。

子结式 PRS 位于两者之间。Sylvester 矩阵的特定子式预言了哪些首项因子必然出现，于是算法只做由次数下降可知的精确除法，不必逐项猜测公因子。可以把它理解为给 Euclidean 余式链安装一套代数上证明正确的消肿规则：不改变商域中的 GCD，却让中间式保持在输入行列式所允许的尺度。

UFD 上的非零本原输入且初始次数严格递减时，缩放余式链的最后非零项取本原部分后给出 GCD — 本原输入的缩放余式链

图示选择本原输入与严格递减的初始次数。一般输入的公共内容需按前面的公式单独乘回。

例子与边界

在 $\mathbb Z[x]$ 中取

A=2x^2+3x+1,\qquad B=3x+1.

普通域除法的余式是 $2/9$ 。伪除法因 $m-n+1=2$ 先乘 $3^2$ ：

9A=(6x+7)B+2.

于是 PRS 为 $A,B,2,0$ ，全程没有分数；primitive part 的最后非零常数为 $1$ ，说明 $A,B$ 在 $\mathbb Q[x]$ 中互素，而常数 $2$ 还记录了结式信息。这个小例子只有一轮，子结式缩放尚不显眼；在多轮高次数输入中，若把每个伪余式原样传下去，首项幂会层层累积，正是它要消去的部分。

整环假设不能随意削弱。若系数环有零因子，乘首项可能把非零多项式消成零，次数下降和“最后非零项给出 GCD”的论证都失效。伪除法本身可在整环中定义，但用内容与 primitive part 规范化通常要求 UFD；若只在商域里求 GCD，则还要追踪分母并把答案拉回 $D[x]$ 。

次数异常下降也需要正确递推。若某一步从次数 $d$ 直接掉到 $d-k$ ，不能套用“每次恰降一”的简化缩放，否则精确除法可能失败。零输入、常数除数以及首项为单位的情形应由边界分支处理。子结式 PRS 控制的是代数冗余因子，不保证机器整数永不变大；真实 bit complexity 仍受输入系数高度和快速整数运算影响。

推论与应用

序列中的零与非零主子结式刻画 GCD 次数，零次子结式 $S_0$ 才是结式。例如 $A=x^2+1$ 、 $B=x^2-1$ 的本页 PRS 为 $A,B,-2,0$ ，而 $\operatorname{Res}(A,B)=4$ ；从二次直接降到常数时，不能把末项 $-2$ 当成结式。要恢复 $S_0$ ，应保留标量子结式递推，或使用结式页的带首项幂和符号的递推。因此带完整缩放记录的余式链可同时回答“是否有公共因子”“公共因子的次数是多少”以及“结式值是什么”，避免另行构造完整 Sylvester 行列式。

多项式平方自由分解需要计算 $\gcd(f,f')$ ，在整数系数或把多元多项式视为某个主变量的一元多项式时，子结式 PRS 是经典的精确 GCD 引擎。它也用于实根计数的 Sturm–Habicht 序列、符号消元和参数化系统的次数判定。GCD 在未选定规范代表时只确定到单位倍数；子结式的具体系数则还固定了行列式次序与缩放。比较不同实现的输出时，应先统一这些约定。

对非零输入令 $N=\max\{1,\deg A,\deg B\}$ 。至多 $O(N)$ 个余式阶段配合普通稠密伪除法，给出保守的 $O(N^3)$ 次系数加法、乘法及 $O(N^2)$ 次精确标量除法上界；内容计算与 GCD oracle 的成本、系数位长度及相应位运算另计。滚动保存余式并复用工作向量需 $O(N)$ 个系数槽；若保留全部余式多项式，则需 $O(N^2)$ 个系数槽。

用于Sturm实根计数时，还要保留正确的符号，而不只是GCD或零检测信息。本页Brown–Traub缩放约定不能未经转换就逐项拿来数变号；普通Sturm链使用负余式，若简化各项，只能乘正数保持端点符号。Sturm–Tarski查询进一步从导数加权的输入建立符号链，计算根上正、负、零贡献。

参考资料

[1] George E. Collins, “Subresultants and Reduced Polynomial Remainder Sequences,” Journal of the ACM 14(1), 1967, pp. 128–142, doi:10.1145/321371.321381.
[2] W. S. Brown and J. F. Traub, “On Euclid’s Algorithm and the Theory of Subresultants”, Journal of the ACM 18(4), 1971, pp. 505–514，§3 的内容分离与 §7 的缩放递推。
[3] W. S. Brown, “The Subresultant PRS Algorithm,” ACM Transactions on Mathematical Software 4(3), 1978, pp. 237–249，Theorems 2–3；精确缩放及辅助标量的整性。可对照 SymPy 的多项式算法实现说明中子结式 PRS 的同一约定。
Keith O. Geddes, Stephen R. Czapor, and George Labahn, Algorithms for Computer Algebra, Kluwer, 1992, Ch. 7.

形式陈述 ​

反向链接

形式陈述