TOPICS
Search

Kung-Traub Conjecture


The Kung-Traub conjecture asserts that a deterministic stationary root-finding algorithm without memory using at most n scalar function or derivative evaluations in each iteration has universal local order at most 2^(n-1) at simple roots (Kung and Traub 1974). Each evaluation returns one scalar value of the function or of a derivative of any chosen nonnegative integer order. The evaluation points and derivative orders may depend on the answers already received in the current iteration.

Colbrook (2026) proves the bound for the class of real analytic functions. For every proposed order p>2^(n-1), a single entire function that is real on the real axis has a simple root and arbitrarily close starting points at which the local order-p estimate fails. The sharp order 2^(n-1) is attained for n>=2 by the methods of Kung and Traub (1974). Colbrook (2026) also proves a complex-observation version and reports a Lean formalization developed with ChatGPT assistance. The formal definitions and main theorem statements were inspected, but the development was not independently rebuilt here.


See also

Rate of Convergence, Root-Finding Algorithm

Explore with Wolfram|Alpha

References

Colbrook, M. J. "Adversarial Wronskians: A Proof of the Kung-Traub Conjecture." 20 Sep 2026. https://arxiv.org/abs/2610.40660v1.Kung, H. T. and Traub, J. F. "Optimal Order of One-Point and Multipoint Iteration." J. ACM 21, 643-651, 1974. https://doi.org/10.1145/321850.321860.

Cite this as:

Weisstein, Eric W. "Kung-Traub Conjecture." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/Kung-TraubConjecture.html

Subject classifications