实代数数的精确表示

两份记录什么时候相等 ​

设 $(p,a,b)$ 表示 $\alpha$，$(q,c,d)$ 表示 $\beta$。如果两个开区间不相交，它们当然不同。否则令

$\alpha =\beta$ 当且仅当 $g$ 在 $J$ 中有一个实根。

证明分两步。若 $\alpha =\beta$，它是 $p,q$ 的共同根，因而是 $g$ 的根，也在交集内。反过来，若 $\gamma \in J$ 是 $g$ 的根，它同时是 $p,q$ 的根；两个原区间都只含自己的一个根，所以 $\gamma =\alpha =\beta$。

交集端点不会是 $g$ 的根，因为每个端点至少是一个原隔离区间的非根端点。因此可以直接在 $J$ 中用Sturm计数。若 $g$ 是非零常数，判等立即返回否，不需要将两个近似值算到许多小数位。

例如比较 $(x^2-2,1,3/2)$ 与 $((x^2-2)(x-5),11/8,3/2)$，GCD为 $x^2-2$，交集计数为一，故相等。若改成 $(x^2-3,3/2,2)$，区间已经分离，立即得到 $\sqrt{2}<\sqrt{3}$。

比大小为何一定能结束 ​

先执行上面的精确判等。如果两数相同，返回等号；否则不断细化各自的隔离区间，直到两区间分离，再看谁在左边。

终止依据是 $|\alpha -\beta |>0$。让两个区间都足够窄，它们就不可能继续重叠。这个正距离不用事先知道，但“不同”必须先有证据。若跳过判等，两份相同实数的不同记录可能永远细化而永不分离。

取 $\alpha$ 为 $x^3-x-1$ 的实根，$\beta =\sqrt{2}$。现有证书为

因为 $4/3<11/8$（交叉相乘为 $32<33$），直接得到 $\alpha <\beta$。这里不曾把任何无理数舍入成小数。

一个容易混淆的求逆边界 ​

在商环里，用Bézout等式求 $h$ 的逆通常要求 $gcd(p,h)=1$。可是对我们选中的单个根，$h(\alpha )\ne 0$ 已足以取倒数，即使 $h$ 在 $p$ 的另一个根上为零。

例如用

表示 $\sqrt{2}$，并取 $h=x-1$。显然 $h(\alpha )\ne 0$，但 $gcd(p,h)=x-1$，所以 $h$ 在整个 $\mathbb{Q}[x]/(p)$ 中不是单位。

可以先去掉 $g=gcd(p,h)$，用 $p_1=p/g=x^2-2$ 保留目标根。现在

故在目标根处

一般情况下，$p$ 平方自由且 $h(\alpha )\ne 0$ 保证除去公共因子后仍保留 $\alpha$，而 $gcd(p/g,h)=1$。再做扩展Euclidean运算才得到合法逆元。这说明“指定根处非零”与“整个可约商代数里可逆”不是同一条件。

在一个根上判断另一个多项式的符号 ​

给定 $h\in \mathbb{Q}[x]$，想知道 $h(\alpha )$ 是负、零还是正。第一步仍然是先查零：求 $g=gcd(p,h)$，检查它是否在 $(a,b)$ 中有根。若有，便有 $h(\alpha )=0$；若没有，$h(\alpha )\ne 0$。

非零以后，可以细化 $\alpha$ 的隔离区间，直到其中没有 $h$ 的实根。为避免端点问题，同时要求 $h$ 在两端非零。然后取任意内部有理数 $t$，计算 $h(t)$ 的符号；由介值定理，$h$ 在整个区间不能改变符号，所以这正是 $h(\alpha )$ 的符号。

为什么这一步也会停？$h$ 非零时只有有限多个实根，而已经知道 $\alpha$ 不是其中任何一个，故存在一个围绕 $\alpha$ 且不含这些根的小区间。若 $h$ 是非零常数，直接返回常数符号；若 $h=0$，直接返回零。

在本例中，$\alpha \in (5/4,4/3)$ 全为正数，且

所以 ${\alpha }^2-2<0$。对 $h=x^3-x-1$，则GCD检测立即返回零。后一种等号不能靠“数值绝对值已经很小”认证。

Sturm–Tarski查询理路Sturm–Tarski 符号查询Sturm–Tarski query · Tarski query · Sturm–Tarski theorem · 加权实根符号查询将实根计数推广为根上符号之和，以导数加权负余式链计算查询，并用三次查询恢复正、负、零根数。提供另一条路径：直接对隔离区间计算加权变号数，通常不必先把区间缩到能看出 $h$ 的符号。两种办法输出相同的精确三值结果。

算术运算需要重新选根 ​

代数数的和、积仍是代数数。但得到一个结果多项式之后，还要确定选中了哪个实根。

最简单的例子是 $\gamma =\alpha +1$。代入 $\alpha =\gamma -1$ 得

所以

以 $\gamma$ 为根。原区间平移一单位给出 $(9/4,7/3)$；平移在两方程根之间建立一一对应，故这个区间恰含一个 $g$ 的根。这就得到结果的精确表示。

对一般两数之和，若 $p(\alpha )=0,q(\beta )=0$，可计算消元多项式

因为 $t=\alpha +\beta$ 时两式有共同根 $x=\alpha$，所以 $R(\alpha +\beta )=0$。但它通常还包含其他共轭根之和；因此去重后，要结合两个输入区间的和区间继续隔离，直到只含目标根。非零消元多项式只有有限多个不同根，输入区间宽度可以趋于零，故最终能选中目标。结果多项式有重根时，先取平方自由部分。

这一点与结式页理路多项式结式计算Polynomial resultant computation · Sylvester resultant algorithm由 Sylvester 行列式或子结式余式链计算两个一元多项式是否具有公共根的消元量。的接口一致：结式给必要代数关系，隔离区间负责实际的实根分支。仅返回结式不能宣称已经算出了用户指定的那个和。

自测：四类证据各做什么 ​

对同一根 $\alpha$，交付以下结果：

• $(x^3-x-1,5/4,4/3)$ 是有效表示：用Sturm计数为一认证
• $\alpha <\sqrt{2}$：用有理区间分离认证
• ${\alpha }^3-\alpha -1=0$：用共同因子认证
• ${\alpha }^2-2<0$：用隔离区间上的正数平方界认证

这四项分别回答存在唯一性、顺序、等号和严格符号。把它们合在一起，精确实代数数才不仅是“一个带很多小数位的数”。