Sturm 多项式实根计数

辅助项过零时，为什么计数不变 ​

先证明相邻两项不能同时为零。若 $S_{i-1}(t)=S_i(t)=0$，除法恒等式迫使 $S_{i+1}(t)=0$，一路传到最后的非零常数，矛盾。

现在设中间项 $S_i(t)=0$，其中 $0<i<m$。同一恒等式给出

所以左右邻居符号相反。在 $t$ 附近，邻居保持各自符号。中间项无论是正、负，还是正好为零，这一小段总共都贡献一次变号：

都是一次；把所有符号反转也一样。辅助项因此不会凭空增加或消去计数。

如果几个不相邻的辅助项在同一点为零，可以分别处理这些局部三项段；它们不共享任何会过零的邻项，变号总和仍然不动。这里只用了连续多项式的非零值在足够小邻域内保持符号。

原多项式过根时，为什么恰好减一 ​

设 $f(\alpha )=0$。平方自由性使 $f^{\prime }(\alpha )\ne 0$，写

在足够小的邻域，$h(x)$ 与 $f^{\prime }(x)$ 同号。因此在根左侧，$f(x)$ 与 $f^{\prime }(x)$ 异号；在根右侧，它们同号。链首两项从“一次变号”变成“零次变号”。

其余位置的总变号数按上一节保持不变，所以 $V$ 跨过 $\alpha$ 恰好减一。有限区间内只有有限多个多项式零点，把区间按这些点分段，所有辅助点贡献零、每个 $f$ 的根贡献一；相加就是 $V(a)-V(b)$。

图中 $-3/2$ 是 $S_2$ 的根，$\pm 1/\sqrt{3}$ 是 $S_1$ 的根；它们都不是 $f$ 的根。虚线标出这些位置时，蓝色阶梯保持水平。红色根只用有理区间 $(5/4,4/3)$ 标定，绘图位置不承担精确证书。

重根、端点与缩放各有一条规则 ​

先去重再计数。 对任意非零非常数 $F\in \mathbb{Q}[x]$，令

这个平方自由部分与 $F$ 有相同的不同根。用 $f$ 的链计数，输出的是不同根数；若还要各自重数，调用平方自由分解理路多项式平方自由分解Square-free factorization of polynomials · Square-free decomposition以形式导数、GCD 与正特征下的 Frobenius 开根分离不可约因子的重数。保存的重数块。例如 $(x-1{)}^2$ 在 $(0,2)$ 有一个不同根、按重数计有两个，两个口径不能混写。

根端点要单独处理。 本页公式使用开区间且要求端点非根。若 $f=x$，链为 $(x,1)$，则 $V(-1)-V(0)=1$，但 $(-1,0)$ 里没有根。这说明直接把根端点的零删去，会把右端点算进去。需要开区间时可改选非根有理端点，或明确使用单侧值 $V(a^{+})-V(b^{-})$。

只允许不改符号的简化。 把链中的任意一项乘以正数不会改变 $V$，所以可用正分母清掉分数。把最后的 $-23/4$ 首一化为 $1$ 却乘了负数，会毁掉证书。“每项都化为首一”适合某些GCD接口，不适合直接拿来数Sturm变号。若继续递推，应同时保存实际的除法恒等式，而不是把旧商硬套到缩放后的项上。

把数量保证变成下一步工具 ​

一条有理余式链可以反复在不同端点求值，不必为每个区间重算。所有端点值都是有理数，符号可以精确判断；复杂性仍取决于分子分母的位长度，不能把任意大有理数运算当成固定耗时。

现在对任何候选区间都能回答零个、一个或多个根。实根隔离理路有理多项式的实根隔离Real root isolation of rational polynomials · Sturm bisection isolation · 实根隔离以精确根计数驱动区间细分，为每个不同实根给出互不相交的有理隔离区间，证明终止、完整性和重数恢复。据此丢弃零根区间、保留单根区间、继续分割多根区间。若需要在这些根上统计另一个多项式的正负，Sturm–Tarski 查询理路Sturm–Tarski 符号查询Sturm–Tarski query · Tarski query · Sturm–Tarski theorem · 加权实根符号查询将实根计数推广为根上符号之和，以导数加权负余式链计算查询，并用三次查询恢复正、负、零根数。保留同样的余式机制，把“每个根贡献一”推广为“按所查询的符号贡献 $-1,0,1$”。