1974年提出的解方程速度极限，终于被证明

为了找到函数f穿过零的位置，计算机常常运行一种迭代：从一个猜测值x出发，向函数提几个问题，算出一个更好的猜测值，然后重复。这些问题就是求值（evaluation）：f在某一点的值，或者它的斜率（导数）的值，或者更高阶导数的值。

位数翻番

这类方法的速度用它的阶（order）来衡量。如果当前误差为ε，那么一个p阶的迭代留下的误差大约是ε的p次方。2阶意味着在接近答案时，正确的位数每一步翻一番；4阶则意味着变为原来的四倍。

牛顿法每一步花费两次求值——f(x)及其斜率f′(x)——然后移动到x − f(x)/f′(x)。它是2阶的。每一步多问几个问题，就能换来更快的速度。问题在于能快多少。

一个来自1974年的猜想

1974年，孔祥重（H. T. Kung）和特劳布（J. F. Traub）在《ACM期刊》（Journal of the ACM）的一篇论文中，以“猜想8.1”的形式提出了一个答案：每一步使用n次求值的无记忆迭代，阶数至多为2ⁿ⁻¹。“无记忆”是指，该方法除了当前的猜测值之外，不保留之前各步的任何信息。

这个上界不可能再降低：孔祥重和特劳布本人就已经构造出了“多点”方法，对每个n ≥ 2都能达到2ⁿ⁻¹——三次求值达到4阶，四次达到8阶，五次达到16阶。缺少的是另一半：证明没有任何方法能做得更好。在这一猜想提出时及其之后，都出现了一些部分结果。这个上界已经针对基于插值的方法、使用两次求值的有理方法，以及在各种附加条件下得到证明；对于只使用函数值的方法，人们证明了一个较弱的上界2ⁿ。一般情形一直悬而未决。

骗过算法

剑桥大学应用数学与理论物理系的Matthew Colbrook，如今完整地证明了它。这个模型有意对算法十分宽容。算法可以边走边选择在哪里求值、取哪些阶的导数。它可以用任何自己喜欢的确定性方式处理得到的回答，对其规则不要求任何光滑性。

证明利用算法自身的确定性来对付它。构造两个函数，它们对算法提出的所有问题都给出完全相同的回答，却有不同的零点。算法对这两个函数必须返回同一个猜测值，因此在其中一个函数上，它的偏差至少是两个零点间距离的一半。

为了找到这样的函数对，Colbrook用一个次数至多为n的小多项式去微调一个参考函数，这个多项式有n + 1个可调系数。每次求值至多锁定这些系数的一种组合，因此在提出n个问题之后，仍有一些微调是算法看不见的。但仅靠这个计数还不够：一个看不见的微调，可能几乎不会移动零点。

关键工具是朗斯基行列式（Wronskian）——由一族多项式及其导数构成的行列式。一条新引理指出：如果这族多项式中的某一个有许多零点挤在一个小圆盘里，那么这族多项式的朗斯基行列式必定在附近为零。通过始终用一个零点远离这几个点的函数来回答算法，证明让零点保持可以自由移动。

指数正是从这番细致的计算中得出的。从距零点ε的地方出发，可能的零点始终分布在一个范围内，这个范围至少是常数乘以ε的某个幂次。用作者的话说：“指数在第一次观测之后仍为1，此后每次翻倍，在n次观测之后得到2ⁿ⁻¹。”

一个函数应对所有尺度

还剩下一个难点。阶的定义允许前面的常数依赖于函数，所以在每个尺度上换一个不同的坏函数，什么也证明不了。因此，Colbrook构造了单一一个函数，逐一加入修正项，每个修正项都在算法已经查询过的每一个点上为零，从而让所有过去的回答保持完全不变。

其极限是一个整函数（entire function）——处处光滑，即使在复数范围内也是如此——它在实轴上的斜率始终介于3/4和5/4之间：一条稳定上升、只有一个性质良好的零点的曲线。对于任何大于2ⁿ⁻¹的p，该方法在这个函数上都达不到p阶。因此，对于n ≥ 2，无记忆方法的最优阶恰好是2ⁿ⁻¹。论文还证明，当求值结果为复数时，同样的上界也成立。

一次全问的代价

一个更强的命题涵盖了分组进行的求值：同一组中的每个问题，都要在该组任何回答到来之前选定——这正是并行方法所处的情形。若各组的大小为ℓ₁, …, ℓₖ，则阶数至多为ℓ₁ × (ℓ₂ + 1) × … × (ℓₖ + 1)。一次提出全部n个问题，阶数的上限就是n；逐个提问，则可达到2ⁿ⁻¹。对于五次求值，就是5对16。

由机器核查

这些结果在Lean中得到了形式化验证。Lean是一种证明助手，会检查每一个逻辑步骤。代码已经公开，并登记在Palomar注册库中。作者表示，Lean形式化是在ChatGPT 6的帮助下完成的，随后用Lean 4 Comparator对照论文中的定理进行了核查；每一个论证都经过作者本人审阅，作者对内容承担全部责任。

这一极限针对的是会遗忘的方法。允许重复利用之前各步的方法遵循其他的上界，本文对此未作讨论。