Adversarial Wronskians: A proof of the Kung--Traub conjecture

Matthew J. Colbrook

AI summary · arXiv: 2610.40660v1 · math.NA

Adversarial Wronskians: A proof of the Kung--Traub conjecture

Matthew J. Colbrook

Original paper Submitted to arXiv on 20 Sep. 2026 Formal verification: https://github.com/MColbrook/Kung-Traub_conjecture License: NONEXCLUSIVE-DISTRIB 1.0 Also in: fr

How to read this summary? Illustrated guide

The essentials

The paper proves that deterministic stationary root-finding without memory, using at most n scalar evaluations per iteration, has universal local order at most 2^(n−1), and that this bound is sharp.

Question

Can arbitrary adaptive choices of function or derivative evaluations and unrestricted deterministic processing achieve local convergence order above the Kung–Traub bound? The paper addresses this for real analytic functions with simple zeros, and also treats grouped evaluations and complex observations.

Method

The authors model each iteration as at most n adaptive scalar observations and prove a fixed-scale lower bound using finite-dimensional polynomial perturbations and a localisation lemma for polynomial Wronskians. A diagonal construction preserves earlier observations while producing a single entire counterexample; the paper also establishes a grouped-evaluation bound and a complex analogue, and reports formal verification in Lean.

Findings

Result No deterministic stationary method without memory using at most n real scalar evaluations per iteration can have universal local order greater than 2^(n−1).
Result The counterexample can be an entire function whose real derivative stays between 3/4 and 5/4, with a unique real zero.
Authors’ interpretation The Kung–Traub methods attain the upper bound for every n≥2.
Result For prescribed groups of sizes ℓ₁,…,ℓₖ, the universal local order is at most ℓ₁∏ⱼ₌₂ᵏ(ℓⱼ+1).
See the passage in the paper
Then its universal local order is at most $$\ell_{1}\prod_{j=2}^{k}(\ell_{j}+1).$$
Result The corresponding complex-observation result rules out orders above 2^(n−1) on the stated holomorphic-function setting.

Limitations

The main real theorem concerns deterministic stationary methods without memory and real scalar observations; it does not establish the same bound for methods with memory.
See the passage in the paper
In particular, there is no information retained from earlier iterations other than the current starting point.
The complex theorem’s stated conclusion is restricted to a unit-disc derivative bound and a zero in the unit disc.

Why it matters

The result proves the Kung–Traub conjecture in a broad information model, allowing adaptive query locations and derivative orders and arbitrary deterministic processing. It establishes the optimal order for n≥2 by matching the upper bound with Kung–Traub methods, and extends the analysis to grouped and complex evaluations.

Written by AI from the paper. Passages are checked word for word against the text we analysed; the rest may contain errors.

AI-generated keywords: Kung–Traub conjecture root-finding methods convergence order scalar evaluations formal verification

Read further

Comprehensive Summary
Layman's Summary
Blog article
Original abstract

The paper resolves the Kung–Traub conjecture, which asks how quickly a root-finding method can converge when it uses a fixed number of function or derivative evaluations per iteration and does not retain information from previous iterations. The authors study deterministic methods that may adaptively choose query locations and derivative orders, while otherwise processing the answers without restriction. They prove that no method using at most $n$ scalar evaluations can achieve local convergence order greater than $2^{n-1}$ for every real-analytic function with a simple zero. For $n\geq 2$, the multipoint methods of Kung and Traub attain this bound. The proof begins with a lower bound on the error at a fixed scale. The authors construct a finite-dimensional family of perturbations of a reference function by multiplying polynomials of degree at most $n$ by a fixed analytic weight. Each scalar observation imposes at most one linear constraint on the perturbation parameters. Thus, after $n$ observations, some inputs produce the same transcript but have different roots. The key challenge is to ensure that these roots are sufficiently far apart, rather than merely proving that a perturbation remains. To address this, the paper establishes a localisation result for polynomial Wronskians: if a polynomial subspace contains a nonzero polynomial with sufficiently many zeros in a small disc, its Wronskian must have a zero nearby. Combined with bounds on polynomial values in terms of their distances to their roots, this result controls how much the root can vary after successive observations. The resulting scale-dependent error lower bound has exponent $2^{n-1}$. A fixed-scale construction alone does not disprove a local-order guarantee, because the guarantee’s constants may depend on the function. The authors therefore construct a single entire function by adding a sequence of increasingly small analytic corrections. Each correction vanishes to sufficiently high order at every query point from earlier executions, preserving all previously recorded derivative values and outputs exactly. The corrections converge on every complex disc and remain small in the real $C^1$ norm. The limit is entire, real-valued on the real line, has a unique real zero, and has a derivative between $3/4$ and $5/4$ everywhere on the real line. Along a sequence of starting points approaching that zero, the error divided by the starting distance raised to any fixed power $p>2^{n-1}$ tends to infinity. This shows that the universal upper bound applies even to well-conditioned, strictly increasing functions. The paper also proves a sharper bound for evaluations arranged in prescribed groups. If the group sizes are $\ell_1,\ldots,\ell_k$, and queries within each group are chosen without access to answers from that group, the maximum universal order is at most $\ell_1\prod_{j=2}^{k}(\ell_j+1)$. A single group therefore gives a bound of $n$, while $n$ sequential groups of one evaluation each recover the bound $2^{n-1}$. The authors establish the same $2^{n-1}$ impossibility bound for complex-valued scalar observations on entire functions and report that the results are formally verified in Lean. These results concern deterministic, stationary methods without memory that use scalar evaluations. They do not rule out higher orders for methods that retain information across iterations or use a different information model. The paper provides a matching optimal construction in the real setting for $n\geq 2$; for one evaluation, the upper bound is $1$, and the stated sharpness construction applies specifically when $n\geq 2$.

How fast can a root-finding method really converge?

Root-finding algorithms aim to locate a value where a function equals zero. Newton’s method is a familiar example: it uses the function and its derivative to update an estimate, often converging very quickly near a simple root. But how much can any method gain from a fixed number of evaluations? In “Adversarial Wronskians: A proof of the Kung--Traub conjecture,” Matthew J. Colbrook answers this question for a broad class of deterministic methods.

The paper resolves the Kung–Traub conjecture, which concerns methods that make a fixed number of function or derivative evaluations in each iteration and do not carry information over from earlier iterations. Its central result is a sharp limit: with at most n scalar evaluations, no such method can guarantee local convergence order greater than 2n−1 for every real-analytic function with a simple zero. For n ≥ 2, the multipoint methods of Kung and Traub reach this bound.

Why evaluations limit what a method can know

A root-finding method can choose where to query a function, and it may choose the derivative order at each query. Later choices can depend on earlier answers. The method is otherwise allowed to process those answers however it likes. Still, every scalar observation reveals only a limited amount about the unknown function.

To turn that limitation into a proof, Colbrook considers a reference function and a family of nearby perturbations. Each perturbation is built by multiplying a polynomial of degree at most n by a fixed analytic weight. Since one scalar observation imposes at most one linear constraint on the polynomial’s parameters, n observations cannot distinguish every function in this family. Some different inputs therefore generate exactly the same sequence of queries and answers, even though their roots differ.

Showing that two roots differ is not enough, however. They might be so close that the method could still achieve a very high convergence order. The proof must quantify how far apart the roots can be after the observations. This is where the paper’s title points: Wronskians help control the geometry of the remaining polynomial perturbations.

Wronskians turn ambiguity into an error bound

The key technical ingredient is a localisation result for polynomial Wronskians. Roughly, if a polynomial subspace contains a nonzero polynomial with many zeros packed into a small disc, then its Wronskian must also have a zero nearby. Combined with estimates relating polynomial values to distances from their roots, this result tracks how much the unknown root can move as the method gathers information.

The analysis produces a scale-dependent lower bound on the error. In practical terms, after n evaluations, there are still indistinguishable functions whose roots are separated by an amount that prevents a universal convergence guarantee better than order 2n−1. This captures the central trade-off: sequential access to answers helps, but each scalar evaluation imposes a ceiling on what can be guaranteed across all eligible functions.

From a fixed-scale example to one difficult function

A subtle issue remains. A construction at one fixed scale does not by itself defeat a local convergence guarantee. Such a guarantee may use constants that depend on the particular function, so a different hard example at each scale would not settle the question.

The authors address this by building a single entire function through a sequence of increasingly small analytic corrections. Each new correction is chosen to vanish to sufficiently high order at all query points from earlier executions. That preserves the earlier derivative values and algorithm outputs exactly, while allowing the construction to create new difficult starting points at smaller scales.

The corrections converge on every complex disc and stay small in the real C1 norm. The resulting function is entire, real-valued on the real axis, and has a unique real zero. Its derivative remains between 3/4 and 5/4 everywhere on the real line, so the function is strictly increasing and well-conditioned. Yet, along starting points approaching the root, the error divided by the starting distance raised to any fixed power p > 2n−1 grows without bound. The limit therefore rules out higher universal orders even for functions with particularly well-behaved real roots.

Query timing matters

The paper also studies methods whose evaluations are arranged in groups. Within a group, query locations must be chosen without seeing that group’s answers. If the group sizes are ℓ1, …, ℓk, the maximum universal order is at most:

ℓ1 × (ℓ2 + 1) × … × (ℓk + 1).

This formula shows why adaptivity matters. If all n evaluations are in one group, the bound is n. If they are split into n sequential groups of one evaluation each, the bound becomes 2n−1. The paper also establishes the same impossibility bound for complex-valued scalar observations on entire functions, and reports that the results have been formally verified in Lean.

What the result does—and does not—say

For deterministic, stationary methods that use scalar evaluations and retain no information across iterations, the result gives a precise frontier: no method can universally beat order 2n−1, and the Kung–Traub multipoint methods attain that order in the real setting when n ≥ 2. With one evaluation, the upper bound is 1; the stated matching construction applies specifically for n ≥ 2.

This is not a claim that every root-finding algorithm is subject to the same limit. Methods that retain information from earlier iterations, or that use a different information model, fall outside the result. Within its scope, however, the paper gives a rigorous answer to a longstanding question—and explains how carefully designed analytic perturbations can expose the limits of even highly adaptive algorithms.

Created on 02 Nov. 2026

Was this synthesis useful?

Score: 0

Ask questions about this paper to our AI assistant

How to chat with this paper? Illustrated guide

Compare with the PDF

You can also chat with multiple papers at once here.

AI assistant instructions?

Tools for this paper

Explain it differently 3 free rewrites left today

Save to a collection Group papers in collections to compare them, chat with them and export them. Create a free account Log in

Export BibTeX · RIS (Zotero, Mendeley, EndNote) · Obsidian (Markdown) · Notion (Markdown)

Advanced tools Premium

For researchers who follow a field closely: citation alerts, journal-club slides, version comparison and Zotero export. Discover Premium

Zotero

Citation alerts Citation alerts guide

Who works on it? The people and institutions who publish on its topic

Weekly letter Presented in "Mathematics and statistics this week" of 2 November 2026. Mathematics and statistics this week: Testing the limits of familiar rules

Journal club Premium+ Slides to present it Propose for the journal club

Versions What changed between versions

Talk about it in public Premium+ Press kit: release, questions, hype check Press kit guide

Papers around this one

See them on a map

Ranked by how close their title and abstract are to this paper’s. Select some to read them together.

Closest papers

Related Broader context
An algebraic inverse theorem for the quadratic Littlewood-Offord problem, and an application to Ramsey graphs
Matthew Kwan, Lisa Sauermann · 2019 · Combinatorics · cited 7 times · AI summary available

The quadratic Littlewood-Offord paper studies concentration and algebraic structure of random quadratic polynomials, rather than limits on adaptive root-finding evaluations.

Abstract
Consider a quadratic polynomial $f\left(\xi_{1},\dots,\xi_{n}\right)$ of independent Bernoulli random variables. What can be said about the concentration of $f$ on any single value? This generalises the classical Littlewood--Offord problem, which asks the same question for linear polynomials. As in the linear case, it is known that the point probabilities of $f$ can be as large as about $1/\sqrt{n}$, but still poorly understood is the "inverse" question of characterising the algebraic and arithmetic features $f$ must have if it has point probabilities comparable to this bound. In this paper we prove some results of an algebraic flavour, showing that if $f$ has point probabilities much larger…
Related Broader context
Certified homotopy tracking using the Krawczyk method
Timothy Duff, Kisun Lee · 2024 · Numerical Analysis · cited 14 times · AI summary available

Certified homotopy tracking uses interval arithmetic to verify solution paths of polynomial systems, not to bound the convergence order of root-finding methods.

Abstract
We revisit the problem of certifying the correctness of approximate solution paths computed by numerical homotopy continuation methods. We propose a conceptually simple approach based on a parametric variant of the Krawczyk method from interval arithmetic. Unlike most previous methods for certified path-tracking, our approach is applicable in the general setting of parameter homotopies commonly used to solve polynomial systems of equations. We also describe a novel preconditioning strategy and give theoretical correctness and termination results. Experiments using a preliminary implementation of the method indicate that our approach is competitive with specialized methods appearing previousl…
Related Broader context
Weak Poincaré Inequalities via Approximate Stochastic Localization: Application to Sampling the Sherrington-Kirkpatrick Model
Ewan Davies, Holden Lee, Juspreet Singh Sandhu et al. · 2026 · Probability · cited 3 times · AI summary available

The stochastic-localization paper proves a weak Poincaré inequality for the Sherrington-Kirkpatrick model and applies it to sampling, not root finding.

Abstract
We develop a new method for proving a weak functional inequality by first proving it for a sufficiently regular sequence of distributions approximating the stochastic localization (SL) process, and then transferring it to the desired distribution via regularity of the SL process and conductance arguments. We use this strategy to prove a weak Poincaré inequality (WPI) holds for the Gibbs measure of the Sherrington-Kirkpatrick model when $β< \frac{1}{2}$. A prior result of the authors [arXiv:2605.03718, 2026] proves the ASL process for the Sherrington-Kirkpatrick model satisfies the required regularity conditions. A consequence of the WPI is that a much simpler algorithm -- Glauber dynamics wi…
Related Broader context
Oblivious Sketching of High-Degree Polynomial Kernels
Michael Kapralov, Rasmus Pagh, Ameya Velingker et al. · 2019 · Data Structures and Algorithms · AI summary available

The sketching paper develops algorithms for speeding up high-degree polynomial kernel computations, rather than studying root-finding convergence limits.

Abstract
Kernel methods are fundamental tools in machine learning that allow detection of non-linear dependencies between data without explicitly constructing feature vectors in high dimensional spaces. A major disadvantage of kernel methods is their poor scalability: primitives such as kernel PCA or kernel ridge regression generally take prohibitively large quadratic space and (at least) quadratic time, as kernel matrices are usually dense. Some methods for speeding up kernel linear algebra are known, but they all invariably take time exponential in either the dimension of the input point set (e.g., fast multipole methods suffer from the curse of dimensionality) or in the degree of the kernel functi…
Related Broader context
Potential Hessian Ascent: The Sherrington-Kirkpatrick Model
David Jekel, Juspreet Singh Sandhu, Jonathan Shi · 2024 · Probability · preprint, not peer reviewed · cited 8 times · AI summary available

Potential Hessian Ascent develops a spectral algorithm for optimizing random quadratic objectives on the hypercube, not for finding analytic function zeros.

Abstract
We provide the first iterative spectral algorithm to find near-optima of a random quadratic objective over the discrete hypercube. The algorithm is a randomized Hessian ascent in the solid cube, where we modify the objective by subtracting a specific instance-independent potential function [Chen et al., Communications on Pure and Applied Mathematics, 76(7), 2023]. This extends Subag's algorithmic program of Hessian ascent from the sphere [Subag, Communications on Pure and Applied Mathematics, 74(5), 2021] to the more complex geometry of the cube. Utilizing tools from free probability theory, we construct an approximate projector into the top-eigenspaces of the Hessian with well-behaved diago…
Related Broader context
The Hamel-Nadirashvili conjecture for the Fisher-KPP equation
Hongjun Guo, Kelei Wang, Maolin Zhou · 2026 · Analysis of PDEs · AI summary available

The Fisher-KPP paper classifies entire solutions of a reaction-diffusion equation, rather than analyzing evaluation limits in root-finding methods.

In short
The paper proves that all bounded entire Fisher–KPP solutions with concave reaction terms are local limits of finite mixtures of planar fronts, optionally including a homogeneous solution.
Related Broader context
Matrix anti-concentration inequalities with applications
Zipei Nie · 2021 · Probability · cited 22 times · AI summary available

The matrix anti-concentration paper bounds minimum singular values of random matrices, not the convergence order of deterministic root-finding methods.

Abstract
We provide a polynomial lower bound on the minimum singular value of an $m\times m$ random matrix $M$ with jointly Gaussian entries, under a polynomial bound on the matrix norm and a global small-ball probability bound $$\inf_{x,y\in S^{m-1}}\mathbb{P}\left(\left|x^* M y\right|>m^{-O(1)}\right)\ge \frac{1}{2}.$$ With the additional assumption that $M$ is self-adjoint, the global small-ball probability bound can be replaced with a weaker version. We establish two matrix anti-concentration inequalities, which lower bound the minimum singular values of the sum of independent positive semidefinite self-adjoint matrices and the linear combination of independent random matrices with independent Ga…
Related Broader context
Fast Multivariate Multipoint Evaluation Over All Finite Fields
Vishwas Bhargava, Sumanta Ghosh, Zeyu Guo et al. · 2022 · Data Structures and Algorithms · cited 21 times · AI summary available

Fast Multivariate Multipoint Evaluation develops algorithms to evaluate polynomials at many finite-field points, rather than to find analytic function zeros.

Abstract
Multivariate multipoint evaluation is the problem of evaluating a multivariate polynomial, given as a coefficient vector, simultaneously at multiple evaluation points. In this work, we show that there exists a deterministic algorithm for multivariate multipoint evaluation over any finite field $\mathbb{F}$ that outputs the evaluations of an $m$-variate polynomial of degree less than $d$ in each variable at $N$ points in time \[ (d^m+N)^{1+o(1)}\cdot\poly(m,d,\log|\mathbb{F}|) \] for all $m\in\N$ and all sufficiently large $d\in\mathbb{N}$. A previous work of Kedlaya and Umans (FOCS 2008, SICOMP 2011) achieved the same time complexity when the number of variables $m$ is at most $d^{o(1)}$ and…

Go further

How are these papers found?

We compare the title and abstract of this paper with those of every paper summarized on this site, and with the papers Semantic Scholar recommends, those it cites and those citing it (for a much-cited paper, its most recent citations and, from OpenAlex, the most cited ones). Among the prior work and the follow-ups, the papers that use each other in depth, a method it uses and the much-cited follow-ups come a little higher. The levels (very close, close, related) come from the similarity of the texts, not from a judgment of quality; * marks a paper without an abstract, compared by its title. The sentence under a paper is written by an AI from the two abstracts: check it in the papers. A paper marked not relevant by three readers leaves the list.

Updated on 2 November 2026.

Disclaimer: The AI-based summarization tool and virtual assistant provided on this website may not always provide accurate and complete summaries or responses. We encourage you to carefully review and evaluate the generated content to ensure its quality and relevance to your needs.

Adversarial Wronskians: A proof of the Kung--Traub conjecture

The essentials

Question

Method

Findings

Limitations

Why it matters

Read further

Definitions

How fast can a root-finding method really converge?

Why evaluations limit what a method can know

Wronskians turn ambiguity into an error bound

From a fixed-scale example to one difficult function

Query timing matters

What the result does—and does not—say

Ask questions about this paper to our AI assistant

Tools for this paper

Advanced tools Premium

Papers around this one

Closest papers

Go further

Cite this paper (BibTeX)