The Kung–Traub Barrier: Sharp Polynomial Information Bounds for Complex Root-Finding

We study the polynomial order of the information available for approximating a simple root of a complex-valued function using n evaluations of the function or its derivatives. Nodes and derivative orders may be chosen from previous responses, without requiring continuity or computability of the rules. We work with a uniform class of entire functions sufficiently close to the identity and consider their unique distinguished roots in the unit disk. Polynomial order is defined using families of functions that yield the same information and differ from a base function by polynomials of degree at most n. We prove that, among all causal information procedures using exactly n ≥ 1 evaluations and locally valid on this class, the maximal polynomial information order is 2^(n−1). For the upper bound, we construct a fixed entire function and polynomial perturbations of degree at most n, whose coefficients tend to zero, that preserve all query responses exactly while separating the roots sufficiently to exclude every larger exponent. The construction uses two systems of polynomial kernels, concentration of Wronskian zeros, and diagonalization. For the reverse inequality, we construct an explicit information procedure based on inverse Hermite interpolation and establish a uniform bound on the separation of the roots of any two functions in the class yielding identical information, without requiring their difference to be polynomial. Consequently, the Kung–Traub barrier is attained for the polynomial information order and the mathematical model considered here.

Authors

Institutions

Publication Details

Journal
Zenodo (CERN European Organization for Nuclear Research)
Published
2026-11-18
DOI
https://doi.org/10.5281/zenodo.24338405
Primary Topic
Polynomial and algebraic computation
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

The Kung–Traub Barrier: Sharp Polynomial Information Bounds for Complex Root-Finding

Rodrigo Castro
1 links
Zenodo (CERN European Organization for Nuclear Research)
Polynomial and algebraic computation
preprint

The Kung–Traub Barrier: Sharp Polynomial Information Bounds for Complex Root-Finding

Rodrigo Castro
preprint en

Abstract

We study the polynomial order of the information available for approximating a simple root of a complex-valued function using n evaluations of the function or its derivatives. Nodes and derivative orders may be chosen from previous responses, without requiring continuity or computability of the rules. We work with a uniform class of entire functions sufficiently close to the identity and consider their unique distinguished roots in the unit disk. Polynomial order is defined using families of functions that yield the same information and differ from a base function by polynomials of degree at most n. We prove that, among all causal information procedures using exactly n ≥ 1 evaluations and locally valid on this class, the maximal polynomial information order is 2^(n−1). For the upper bound, we construct a fixed entire function and polynomial perturbations of degree at most n, whose coefficients tend to zero, that preserve all query responses exactly while separating the roots sufficiently to exclude every larger exponent. The construction uses two systems of polynomial kernels, concentration of Wronskian zeros, and diagonalization. For the reverse inequality, we construct an explicit information procedure based on inverse Hermite interpolation and establish a uniform bound on the separation of the roots of any two functions in the class yielding identical information, without requiring their difference to be polynomial. Consequently, the Kung–Traub barrier is attained for the polynomial information order and the mathematical model considered here.

Zenodo (CERN European Organization for Nuclear Research)
University of Valparaíso (CL)
Polynomial and algebraic computation
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon