Adversarial Wronskians: A proof of the Kung--Traub conjecture
Abstract
We prove the Kung--Traub conjecture: a deterministic stationary root-finding method without memory, using at most n real scalar function or derivative evaluations per iteration, cannot have local order greater than 2n−1 on every real analytic function with a simple zero. For n≥2, the bound is attained by the methods of Kung and Traub. The local estimate is required at every sufficiently close starting point, with constants that may depend on the function. Evaluation points and derivative orders may be chosen adaptively, and the rules for choosing them and processing the data are unrestricted. The proof uses a localisation property of polynomial Wronskians to obtain a lower bound at each fixed scale. A diagonal construction then gives one entire function, with derivative bounded above and below on the real line, for which every larger order fails. We also obtain a sharper bound when evaluations are made in prescribed groups, and prove the corresponding result for complex scalar evaluations. The results of this paper are also formally verified in Lean.
Related
- The Sandier-Serfaty triangular-lattice conjecture: an independent reproduction of a claimed finite certificate, an adversarial audit of the claimed reduction, and a Lean statement (no proof of the conjecture is claimed)
- A proof of the Stanley-Stembridge conjecture
- A proof of Alexander’s Conjecture on an Inequality of Cassels
- A Proof of Ebenfelt's weak SOS Conjecture
- On the proof of the Kozma-Nitzan conjecture
BibTeX
@misc{colbrook2026adversarial,
title = {{Adversarial Wronskians: A proof of the Kung--Traub conjecture}},
author = {Matthew J. Colbrook},
howpublished = {HAL},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2610.40660},
eprint = {2610.40660},
archivePrefix = {arXiv},
url = {https://hal.science/hal-05755825v1},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Adversarial Wronskians: A proof of the Kung--Traub conjecture
AU - Matthew J. Colbrook
PY - 2026
DA - 2026/09/19
PB - HAL
DO - 10.48550/arxiv.2610.40660
UR - https://hal.science/hal-05755825v1
AB - We prove the Kung--Traub conjecture: a deterministic stationary root-finding method without memory, using at most n real scalar function or derivative evaluations per iteration, cannot have local order greater than 2^n−1 on every real analytic function with a simple zero. For n≥2, the bound is attained by the methods of Kung and Traub. The local estimate is required at every sufficiently close starting point, with constants that may depend on the function. Evaluation points and derivative orders may be chosen adaptively, and the rules for choosing them and processing the data are unrestricted. The proof uses a localisation property of polynomial Wronskians to obtain a lower bound at each fixed scale. A diagonal construction then gives one entire function, with derivative bounded above and below on the real line, for which every larger order fails. We also obtain a sharper bound when evaluations are made in prescribed groups, and prove the corresponding result for complex scalar evaluations. The results of this paper are also formally verified in Lean.
ER -