The Kung–Traub Conjecture for Memoryless Real Scalar Methods: Proof and Formalization of Computational Procedures
Rodrigo Alberto Castro Marín
Abstract
The Kung–Traub conjecture states that the convergence order of a memoryless scalar iterative method using n evaluations of a function and its derivatives per iteration cannot exceed 2^(n−1). We prove this bound for real scalar, deterministic, causal methods with adaptive queries and partially defined rules, without requiring continuity or computability of those rules.
For every total method T with budget n and every p > 2^(n−1), we construct an entire function F, real on the real axis, a simple root α, and a sequence x_m → α such that
|T_F(x_m) − α| / |x_m − α|^p → +∞.
The construction uses properties of Wronskians of polynomial spaces, concentration of zeros, and quantitative perturbations that preserve exactly the responses to previous queries. We also develop two formalizations of computation: a fixed-budget query model and a model of procedures with internal states and performed evaluations. We prove exact representations that preserve, within the budget under consideration, the domains of valid computations, outputs, records, and evaluation counts by derivative order. From this correspondence, we obtain the order barrier for local realizations and the real formulation of the Kung–Traub bound with the specified operational cost. The results are established for real functions and real nodes.