Sturm–Tarski 符号查询

权重怎样进入过根的那一刻 ​

$A,B$ 互素，故负余式链的最后一项为非零常数。任何中间项过零时，左右邻项仍然相反，总变号数保持不变；这部分证明完全复用Sturm计数理路Sturm 多项式实根计数Sturm theorem for real polynomial roots · Sturm sequence · 多项式的 Sturm 定理用带负号的多项式余式链在区间两端数变号，证明其差恰为不同实根数，并明确零项、重根和根端点的处理。的局部三项分析。

设 $\alpha$ 是留下来的 $A$ 的根。因为 $p=dA$，有

而 $d(\alpha )\ne 0$，于是

在 $\alpha$ 附近，$A(x)$ 的符号是 $A^{\prime }(\alpha )(x-\alpha )$ 的符号，$B$ 保持 $B(\alpha )$ 的符号。

• 若 $q(\alpha )>0$，$B(\alpha )$ 与 $A^{\prime }(\alpha )$ 同号，链首从异号变为同号，$V$ 减一
• 若 $q(\alpha )<0$，二者异号，链首从同号变为异号，$V$ 增一
• 若 $q(\alpha )=0$，这个根已被 $d$ 删除，不产生变化

因此跨过一个根时，$V({\alpha }^{-})-V({\alpha }^{+})=\mathrm{sgn}q(\alpha )$。把区间内所有根的贡献相加，便得到公式。这也解释了为什么加权查询的 $V$ 不一定单调下降。

一个只用有理数的负号证书 ​

取

该区间只含一个 $p$ 的根 $\alpha$，所以查询应直接给出 $\mathrm{sgn}({\alpha }^2-2)$。

先算加权导数余式：

由 $x^3\equiv x+1(\mathrm{mod}p)$，得到

这对输入的GCD为一，负余式链为

中间两步可由以下等式核验：

端点表为

所以查询为 $1-2=-1$，从而 ${\alpha }^2-2<0$。变号数增加不是算法出错，恰好说明这个根带来一个负贡献。

边界：三种看似省事的改法会出错 ​

不能省去导数权重。 对 $p=x^2-1$、$q=1$，若从 $(p,1)$ 直接建链，两端变号之差为零，却有两个实根。正确第二项是 $p^{\prime }q=2x$。

不能把近零当零。 公共根的删除靠精确GCD完成。若将 $q$ 改成 $q+1/{10}^{20}$，曾经为零的贡献可能变成正或负；固定小数阈值会悄悄改变数学问题。

不能混用重数口径。 若原输入 $F=p^2$，本页仍对每个不同根计一次。需要按 $F$ 的重数统计时，应先做平方自由分解理路多项式平方自由分解Square-free factorization of polynomials · Square-free decomposition以形式导数、GCD 与正特征下的 Frobenius 开根分离不可约因子的重数。，对重数为 $k$ 的块查询后乘 $k$，再相加。

最后，余式项只可乘正数来简化符号。对普通子结式实现，也必须确认其输出有与本页一致的有符号恢复规则，不能只因为它也使用Euclidean算法就直接数变号。

三次查询恢复完整数量 ​

固定一个根集合，设 $n_{+},n_{-},n_0$ 分别为 $q$ 正、负、零的根数。计算

因为非零数的平方为正，零的平方仍为零，三式满足

解出

这些等式还能帮助检查结果：必须有 $0\le W\le N$、$|U|\le W$，而 $W$ 与 $U$ 同奇偶。若其中一条失败，输入条件、端点规则或符号链至少有一处处理不对。

例如令

在 $(-2,2)$ 内的三个根依次为 $-\sqrt{2},1,\sqrt{2}$。查询得到 $(N,U,W)=(3,0,2)$，于是 $(n_{+},n_{-},n_0)=(1,1,1)$。$U=0$ 来自一个正贡献与一个负贡献抵消，中间另有一个真正的零值；三种情形现在被分开了。

若要多个多项式的联合符号条件，可以对它们适当的乘积进行更多查询，再恢复各符号组合的计数。那需要新的线性恢复步骤，不能把单个 $q$ 的三个数量直接当成多个条件的交集数量。

区间选根与整轴统计是两个接口 ​

当 $(a,b)$ 隔离单根 $\alpha$ 时，$T(q;p)$ 只有一项，直接给出 $q(\alpha )$ 的符号。这使实代数数表示理路实代数数的精确表示Exact representation of real algebraic numbers · Isolating interval representation · 实代数数用整系数多项式和有理隔离区间指定一个实根，以GCD判等、区间细化比较大小，并为符号判断与精确算术保留正确根分支。有了精确求值接口，无需先构造 $q(\alpha )$ 的极小多项式。

当区间含多个根，输出则是这些根的符号总和。它不能告诉我们正根具体位于哪里；若需要逐根标注，就在每个隔离区间分别查询。

若要整个实轴的结果，可使用一个严格包含全部实根的有理区间。也可以直接计算 $\pm \mathrm{\infty }$ 的符号：非零多项式在 $+\mathrm{\infty }$ 的符号是首项系数符号，在 $-\mathrm{\infty }$ 还要乘 $(-1{)}^{\mathrm{deg}{S}_i}$。这只是在符号层读取首项，不需要真的把无穷代入多项式。

单元中的第二条证书路线 ​

对三次算例，查询给出了 ${\alpha }^2-2<0$ 的一份余式证书。Hermite迹型理路Hermite 迹型与实根符号Hermite trace form · Hermite matrix real root counting · Hermite criterion with sign conditions · Hermite 实根判据在多项式商代数上以乘法算子的迹构造对称形式，证明其签名等于实根上的符号查询，并用精确合同分解复核三次算例。会从同一多项式构造一个有理对称矩阵，以“正平方数减负平方数”重新得到 $-1$。两条计算读取同样的数学对象，却使用不同的中间数据，适合交叉核对。