A 1974 SPEED LIMIT FOR SOLVING EQUATIONS, FINALLY PROVED

To find where a function f crosses zero, a computer often runs an iteration: start from a guess x, ask the function a few questions, compute a better guess, and repeat. The questions are evaluations: the value of f at some point, or of its slope (the derivative), or of a higher derivative.

Digits that double

The speed of such a method is measured by its order. If the current error is ε, an iteration of order p leaves an error of roughly ε to the power p. Order 2 means that, close to the answer, the number of correct digits doubles at each step; order 4, that it quadruples.

Newton’s method spends two evaluations per step — f(x) and its slope f′(x) — and moves to x − f(x)/f′(x). It has order 2. Asking more questions per step can buy more speed. The question is how much.

A conjecture from 1974

In 1974, H. T. Kung and J. F. Traub proposed an answer, as “Conjecture 8.1” of a paper in the Journal of the ACM: an iteration without memory that uses n evaluations per step has order at most 2ⁿ⁻¹. “Without memory” means that the method keeps nothing from previous steps except its current guess.

The bound could not be lowered: Kung and Traub had themselves built “multipoint” methods reaching 2ⁿ⁻¹ for every n ≥ 2 — order 4 with three evaluations, 8 with four, 16 with five. What was missing was the other half: a proof that no method can do better. Partial results came with the conjecture and after it. The bound was proved for interpolation-based methods, for rational methods with two evaluations, and under various extra conditions; for methods using only function values, a weaker bound, 2ⁿ, was established. The general case stayed open.

Fooling the algorithm

Matthew Colbrook, at the Department of Applied Mathematics and Theoretical Physics of the University of Cambridge, now proves it in full. The model is deliberately generous to the algorithm. It may choose where to evaluate, and which derivatives to take, as it goes along. It may process the answers in any deterministic way it likes, with no smoothness required of its rules.

The proof turns the algorithm’s own determinism against it. Build two functions that give exactly the same answers to all its questions but have different zeros. The algorithm must return the same guess for both, so on one of them it misses by at least half the distance between the two zeros.

To find such pairs, Colbrook nudges a reference function by a small polynomial of degree at most n, which has n + 1 adjustable coefficients. Each evaluation pins down at most one combination of them, so after n questions some nudges remain invisible to the algorithm. That count alone is not enough: an invisible nudge might barely move the zero.

The key tool is the Wronskian — a determinant built from a family of polynomials and their derivatives. A new lemma says that if a polynomial of the family has many zeros packed into a small disc, the family’s Wronskian must vanish nearby. A Wronskian has only a limited number of zeros. By always answering the algorithm with a function whose zero stays clear of them, the proof keeps the zero free to move.

The bookkeeping produces the exponent. Starting at a distance ε from the zero, the possible zeros remain spread over a range of at least a constant times a power of ε. In the author’s words, “the exponent remains one after the first observation and then doubles, giving 2ⁿ⁻¹ after n observations.” Since the algorithm cannot tell these zeros apart, its error cannot always fall below a constant times ε to the power 2ⁿ⁻¹: no order above 2ⁿ⁻¹.

One function for every scale

One difficulty remained. The definition of order only asks that the error stay below some constant times ε to the power p, and that constant may depend on the function, so a different bad function at each scale proves nothing. Colbrook therefore builds a single function, adding corrections one after another, each vanishing at every point the algorithm has already queried, so that all past answers stay exactly the same.

The limit is an entire function — smooth everywhere, even over the complex numbers — whose slope stays between 3/4 and 5/4 on the real line: a steadily rising curve with one well-behaved zero. For any p above 2ⁿ⁻¹, the method fails to reach order p on it. The optimal order without memory is therefore exactly 2ⁿ⁻¹ for n ≥ 2. The paper proves the same bound when the evaluations are complex numbers.

The price of asking all at once

A sharper statement covers evaluations made in groups, where every question of a group is chosen before any of its answers arrives — the situation of parallel methods. With groups of sizes ℓ₁, …, ℓₖ, the order is at most ℓ₁ × (ℓ₂ + 1) × … × (ℓₖ + 1). Asking all n questions at once caps the order at n; asking them one at a time allows 2ⁿ⁻¹. With five evaluations, that is 5 against 16.

Checked by machine

The results are formally verified in Lean, a proof assistant that checks every logical step. The code is public and registered in a public registry of formal proofs (Palomar). The author states that the Lean formalisation was carried out with the help of ChatGPT 6, then checked with the Lean 4 Comparator against the theorems of the paper, and that every argument was reviewed by the author, who takes full responsibility for the content.

The limit concerns methods that forget. Methods allowed to reuse their earlier steps obey other bounds, which this paper leaves aside. And the bound is a worst case: on some particular functions, a method can still go faster.