Order barriers under query budgets: the Kung–Traub conjecture as a corollary

We study the restrictions imposed by the number of evaluations of a function and its derivatives on the local order of approximation of simple roots. To this end, we develop an operational query model that extends the class of procedures considered in the Kung–Traub formulation of 1974 and allows us to establish the same barrier under more general hypotheses. In our model, the nodes and the orders of differentiation queried may depend on the previous responses, without requiring these orders to be uniformly bounded. Moreover, we allow different evaluation profiles and budgets imposed only in local neighborhoods of the roots. Unlike the class of iterations considered by Kung and Traub, our operational barrier does not require convergence of the trajectories from both sides of the root, but rather a one-sided error estimate. Nor do we require continuity or computability of the rules. The main analytical contribution consists of a construction by means of polynomial perturbations that preserve exactly the responses to previous queries. We prove that, for every total method T with budget d ≥ 1, there exist an entire function F, real on R, a simple root α, and a sequence xₘ > α, with xₘ → α, such that |T_F(xₘ) − α| / (xₘ − α)^p → +∞ for every p > 2^(d−1). The function, the root, and the sequence can be chosen independently of the final exponent p. We show by examples that these extensions are effective. We construct a locally convergent method with a fixed number of queries and differentiation orders that are not uniformly bounded, whose records cannot be reproduced by schemes with maximum orders fixed at each stage. We also construct a local realization that satisfies a one-sided quadratic estimate, but whose iteration does not belong to the Kung–Traub class because it lacks two-sided local convergence. Moreover, since the obstruction is constructed within an analytic class, we prove that the same barrier rules out guarantees of higher order over strictly larger function classes containing it, including classes of smooth functions that need not be analytic. Thus, the additional generality encompasses both the admitted procedures and the approximation hypotheses, as well as the classes over which an order guarantee is required. By means of exact representations that preserve the outputs, records, and costs of the evaluations, we obtain as a corollary the inequality of the Kung–Traub conjecture in the real formulation considered. Finally, we study minimum costs and information reductions, which allow sharper bounds to be obtained when a map admits lower-cost realizations. The intermediate estimates in our construction retain information on the ranks of the query functionals and the degrees of the perturbations. This structure provides a basis for investigating sharper barriers for particular families of methods.