Introduction
The construction of high-order iterative methods is one of the central questions in solving nonlinear equations and systems. However, increasing the order of convergence does not depend solely on choosing a suitable correction formula. The information obtained from the function and its derivatives during each iteration also matters. A natural question then arises: what is the highest order of convergence that a method can guarantee when only a limited number of evaluations is available?
For scalar equations, Kung and Traub [3 ] studied the relationship between the number of evaluations and the order of convergence and formulated a bound for memoryless iterative methods. In 2010, Arroyo, Cordero, and Torregrosa [6 ] proposed an extension of this question to systems of nonlinear equations. Subsequently, in 2011, they published this conjecture in [4 ] . Its formulation, known as the Cordero–Torregrosa conjecture, distinguishes evaluations of the function from those of its Jacobian. If we denote their numbers by N F N_F N F N J N_J N J
p ≤ 2 N F + N J − 1 , (1) p \le2^{N_F+N_J-1}, \tag*{(1)} p ≤ 2 N F + N J − 1 , (1) under the condition N J ≤ N F N_J \le N_F N J ≤ N F
In this work, we prove the order barrier conjectured by Cordero–Torregrosa for the universal local order of one iteration, without needing to impose the condition N J ≤ N F N_J \le N_F N J ≤ N F
To obtain this generality, we retain three fundamental conditions: the method’s rules are fixed independently of the vector field, each decision uses only the information previously obtained, and no data from earlier iterations are received. Nor do we require the first queries to be evaluations of the function or its Jacobian at the initial point. In this way, we study the restrictions imposed by the available information without limiting the mathematical operations used to process it. The conditions of well-definedness and the evaluation budgets may be required only in neighborhoods of the roots.
The starting point of our proof is the scalar query theorem of Castro Marín [1 ] , which establishes an order barrier for memoryless methods with arbitrary rules. One of the contributions of this work is to prove that a vector execution on fields of the form
G f ( z 1 , … , z n ) = ( f ( z 1 ) , z 2 , … , z n ) T G_f(z_1,\ldots,z_n) = \left(f(z_1),z_2,\ldots,z_n\right)^T G f ( z 1 , … , z n ) = ( f ( z 1 ) , z 2 , … , z n ) T can be reproduced by a scalar procedure that exactly preserves query responses and the first component of the output. To this end, it suffices to make one scalar query for each vector query, without requiring the evaluation points to remain on the first coordinate axis. We also prove that the representation preserves the procedure’s decisions, the budgets, and the local conditions of well-definedness. Thus, taking d = N F + N J d = N_F + N_J d = N F + N J (1) .
Our second result shows that the distribution of evaluations can also impose stronger restrictions on the order of convergence. We say that a Jacobian evaluation is paired when the function has previously been evaluated at the same point. Under this condition, we prove that
p ≤ 2 N F − s + 1 3 s − 1 , s = min { N F , N J } , (2) p \le2^{N_F-s+1}3^{s-1}, \qquad s = \min\{N_F,N_J\}, \tag*{(2)} p ≤ 2 N F − s + 1 3 s − 1 , s = min { N F , N J } , (2) for N F , N J ≥ 1 N_F, N_J \ge1 N F , N J ≥ 1 1 ≤ N J ≤ N F 1 \le N_J \le N_F 1 ≤ N J ≤ N F
p ≤ 2 N F − N J + 1 3 N J − 1 , p \le2^{N_F-N_J+1}3^{N_J-1}, p ≤ 2 N F − N J + 1 3 N J − 1 , whereas, if N J > N F N_J > N_F N J > N F
p ≤ 2 ⋅ 3 N F − 1 . p \le2 \cdot3^{N_F-1}. p ≤ 2 ⋅ 3 N F − 1 . This improvement is strict relative to (1) when N J > 1 N_J > 1 N J > 1
A version of this refinement was previously studied for rational programs in [2 ] . In the present work, we prove that the bound remains valid for methods with arbitrary rules. To this end, we develop a construction independent of the scalar theorem used for the general barrier. Through polynomial perturbations, we preserve exactly the information obtained during the evaluations and control the separation between the root and the queried points. The argument admits adaptively chosen points, discontinuous decisions, and Jacobian evaluations performed long after the corresponding function evaluations.
An important property of this construction is that the obstruction does not depend on choosing a different function for each order we wish to rule out. Indeed, we prove that, for each method, there is a fixed entire function and a sequence of points approaching a simple root such that the error quotients diverge simultaneously for every exponent above the corresponding bound. Exact preservation of responses allows us to transfer this result to the limit without requiring continuity of the rules. Thus, impossibility is established by a fixed analytic field rather than by a family of problems that changes with the initial error.
The preceding construction also provides results for other distributions of information. In particular, when the procedure uses function evaluations only, we obtain an independent proof of the bound
p ≤ 2 N F − 1 . p \le2^{N_F-1}. p ≤ 2 N F − 1 . We also show that, on the diagonal fields used in the proof, the pairing condition can be recognized through equality of the first coordinates of the nodes. These results make it possible to specify which properties of the queries actually enter into the construction of the barriers.
Furthermore, the scalar representation allows us to distinguish between the number of queries made and the new information obtained by a procedure. Indeed, two vector queries made at different points may correspond to the same scalar query on the test fields. We prove that known responses can be reused without changing the decisions or the output of the method. Consequently, if d e f d_{\mathrm{ef}} d ef
p ≤ 2 d e f − 1 . p \le2^{d_{\mathrm{ef}}-1}. p ≤ 2 d ef − 1 . This estimate allows the general barrier to be improved when the procedure requests information that was already available. The improvement depends on the information acquired and not on the arithmetic cost of performing the internal operations.
The preceding results lead us to consider a more general question. So far, we have obtained restrictions on the order using the number of evaluations, their pairing, and the reuse of responses. However, for nonlinear systems it is also natural to ask whether the distribution of function evaluations among Jacobian evaluations can impose an additional restriction that depends on the vector structure of the problem.
In this direction, we return to the proposed product refinement considered in [2 ] and formulate the conjecture
p ≤ ( q + 2 ) N J − r ( q + 3 ) r , N F − 1 = q N J + r , 0 ≤ r < N J , (3) p \le(q+2)^{N_J-r}(q+3)^r,\qquad N_F-1=qN_J+r,\qquad0\le r<N_J, \tag*{(3)} p ≤ ( q + 2 ) N J − r ( q + 3 ) r , N F − 1 = q N J + r , 0 ≤ r < N J , (3) for N F , N J ≥ 1 N_F,N_J\ge1 N F , N J ≥ 1 n ≥ N F + N J − 1 n\ge N_F+N_J-1 n ≥ N F + N J − 1
Finally, we must specify that our barriers concern the universal local order of one iteration. This means that the error estimate must hold for every point sufficiently close to each simple root in the class considered. It is not a restriction on the order a method may attain for a particular problem. Nor should we confuse this order with the Q Q Q
In this work, we prove that a local one-cycle estimate yields convergence for iterations started sufficiently close to the root. However, we show by means of a polynomial vector example that the behavior of trajectories does not, by itself, determine the local order of the output map. We then establish sufficient conditions for relating both concepts, either through invariance of a test axis and regularity of the induced scalar operator, or through a nondegeneracy condition on the first homogeneous term of the vector map. These additional hypotheses do not enter into the general one-cycle barriers.
The article is organized as follows. First, we introduce the query model and prove the scalar representation of vector procedures. Next, we establish the general Cordero–Torregrosa barrier and develop the construction that allows it to be improved when Jacobian evaluations are paired. We then transfer these results to the vector case and study the bounds obtained through the reuse of information. We also examine the scope of the improvements and present the proposed product refinement. Finally, we study the relationship between universal local order and trajectory order and discuss the questions that remain open.
Problems, queries, and local order
Problems and function classes
We write N = { 1 , 2 , … } \mathbb{N}=\{1,2,\ldots\} N = { 1 , 2 , … } N 0 = N ∪ { 0 } \mathbb{N}_0=\mathbb{N}\cup\{0\} N 0 = N ∪ { 0 } R n \mathbb{R}^{n} R n α \alpha α F : Ω → R n F:\Omega\to\mathbb{R}^{n} F : Ω → R n Ω ⊂ R n \Omega\subset\mathbb{R}^{n} Ω ⊂ R n F ∈ C 1 ( Ω ) F\in C^{1}(\Omega) F ∈ C 1 ( Ω )
F ( α ) = 0 , det D F ( α ) ≠ 0. F(\alpha)=0,\qquad\det DF(\alpha)\ne0. F ( α ) = 0 , det D F ( α ) = 0. A problem is a triple ( Ω , F , α ) (\Omega,F,\alpha) ( Ω , F , α ) x x x α \alpha α F F F
We denote by E R \mathcal{E}_{\mathbb{R}} E R f : C → C f:\mathbb{C}\to\mathbb{C} f : C → C R \mathbb{R} R
E ∗ = { f ∈ E R : f ′ ( w ) > 1 2 ( − 1 ≤ u ≤ 1 ) , f has a root in ( − 1 2 , 1 2 ) } . \mathcal{E}_{*}=\left\{f\in\mathcal{E}_{\mathbb{R}}:f'(w)>\frac{1}{2}\ (-1\leq u\leq1),\quad f\text{ has a root in }\left(-\frac{1}{2},\frac{1}{2}\right)\right\}. E ∗ = { f ∈ E R : f ′ ( w ) > 2 1 ( − 1 ≤ u ≤ 1 ) , f has a root in ( − 2 1 , 2 1 ) } . The root of each f ∈ E ∗ f\in\mathcal{E}_{*} f ∈ E ∗ [ − 1 , 1 ] [-1,1] [ − 1 , 1 ] f f f α f \alpha_f α f
Fix I 0 = R I_0=\mathbb{R} I 0 = R I 0 = ( − 1 , 1 ) I_0=(-1,1) I 0 = ( − 1 , 1 ) Ω 0 = I 0 × R n − 1 \Omega_0=I_0\times\mathbb{R}^{n-1} Ω 0 = I 0 × R n − 1 H n ( I 0 ) \mathcal{H}_n(I_0) H n ( I 0 )
( Ω 0 , G f , α f ) , G f ( z ) = ( f ( z 1 ) , z 2 , … , z n ) T , α f = ( α f , 0 , … , 0 ) T , f ∈ E ∗ . (4) (\Omega_0,G_f,\alpha_f),\qquad G_f(z)=\left(f(z_1),z_2,\ldots,z_n\right)^{T},\quad\alpha_f=(\alpha_f,0,\ldots,0)^{T},\quad f\in\mathcal{E}_{*}. \tag*{(4)} ( Ω 0 , G f , α f ) , G f ( z ) = ( f ( z 1 ) , z 2 , … , z n ) T , α f = ( α f , 0 , … , 0 ) T , f ∈ E ∗ . (4) Each field is understood to be restricted to Ω 0 \Omega_0 Ω 0 C n \mathbb{C}^{n} C n n = 1 n=1 n = 1 R n − 1 \mathbb{R}^{n-1} R n − 1
Definition 2.1 (Admissible function class). A class F n \mathcal{F}_n F n H n ( I 0 ) \mathcal{H}_n(I_0) H n ( I 0 ) I 0 I_0 I 0
In particular, the class of all real-analytic vector fields on open sets, together with their simple roots, satisfies this condition. So does the class of all vector fields of class C r C^r C r r ≥ 1 r \ge1 r ≥ 1 C ∞ C^\infty C ∞
Data and rules
We define the set of queries
Q n = { 0 , 1 } × R n . Q_n = \{0,1\} \times\mathbb{R}^n. Q n = { 0 , 1 } × R n . Type 0 requests the value of the function; type 1 requests its full Jacobian. The response spaces are
R 0 = R n , R 1 = R n × n . \mathcal{R}_0 = \mathbb{R}^n, \qquad\mathcal{R}_1 = \mathbb{R}^{n \times n}. R 0 = R n , R 1 = R n × n . For a field F F F Ω \Omega Ω
E F ( 0 , y ) = F ( y ) , E F ( 1 , y ) = D F ( y ) , y ∈ Ω . E_F(0,y) = F(y), \qquad E_F(1,y) = DF(y), \qquad y \in\Omega. E F ( 0 , y ) = F ( y ) , E F ( 1 , y ) = D F ( y ) , y ∈ Ω. A query outside Ω \Omega Ω
A record of length k k k
R k = ( ( τ i , y i , A i ) ) i = 1 k , τ i ∈ { 0 , 1 } , y i ∈ R n , A i ∈ R τ i . R_k = \left((\tau_i,y_i,A_i)\right)_{i=1}^{k}, \qquad\tau_i \in\{0,1\}, \quad y_i \in\mathbb{R}^n, \quad A_i \in\mathcal{R}_{\tau_i}. R k = ( ( τ i , y i , A i ) ) i = 1 k , τ i ∈ { 0 , 1 } , y i ∈ R n , A i ∈ R τ i . We write R 0 = ( ) R_0 = () R 0 = ( ) k k k ( x , R k ) (x,R_k) ( x , R k ) H k \mathcal{H}_k H k
Let c and s be two distinct labels. A decision belongs to the disjoint union
A n = ( { c } × Q n ) ∪ ( { s } × R n ) . \mathcal{A}_n = (\{c\} \times Q_n) \cup(\{s\} \times\mathbb{R}^n). A n = ({ c } × Q n ) ∪ ({ s } × R n ) . The decision ( c , ( τ , y ) ) (c,(\tau,y)) ( c , ( τ , y )) ( s , v ) (s,v) ( s , v ) v v v
Definition 2.2 (Query method). A deterministic, causal, memoryless method is a family of partial rules
Φ k : D k ⟶ A n , D k ⊂ H k , k ∈ N 0 , \Phi_k : D_k \longrightarrow\mathcal{A}_n, \qquad D_k \subset\mathcal{H}_k, \qquad k \in\mathbb{N}_0, Φ k : D k ⟶ A n , D k ⊂ H k , k ∈ N 0 , fixed independently of the vector field and its root. No continuity, rationality, measurability, or computability is required of the rules or their domains.
We say that a method is total with budget d ≥ 1 d \ge1 d ≥ 1 0 , … , d 0,\ldots,d 0 , … , d d d d R n \mathbb{R}^n R n d d d
Determinism means that each history in the domain has a unique decision. Causality means that this decision depends only on the available history. Memorylessness means that each cycle begins only with x x x F F F
Definition 2.3 (Valid execution). A valid execution from x x x F F F R m R_m R m v v v 0 ≤ k < m 0 \le k < m 0 ≤ k < m
( x , R k ) ∈ D k , Φ k ( x , R k ) = ( c , ( τ k + 1 , y k + 1 ) ) , (x, R_k) \in D_k,\qquad\Phi_k(x, R_k) = (c,(\tau_{k+1}, y_{k+1})), ( x , R k ) ∈ D k , Φ k ( x , R k ) = ( c , ( τ k + 1 , y k + 1 )) , y k + 1 ∈ Ω , A k + 1 = E F ( τ k + 1 , y k + 1 ) , y_{k+1} \in\Omega,\qquad A_{k+1} = E_F(\tau_{k+1}, y_{k+1}), y k + 1 ∈ Ω , A k + 1 = E F ( τ k + 1 , y k + 1 ) , and, finally,
( x , R m ) ∈ D m , Φ m ( x , R m ) = ( s , v ) . (x, R_m) \in D_m,\qquad\Phi_m(x, R_m) = (s,v). ( x , R m ) ∈ D m , Φ m ( x , R m ) = ( s , v ) . We write M F ( x ) = v \mathcal{M}_F(x) = v M F ( x ) = v
The queries and decisions are unique whenever they exist: starting from the same x x x k k k
We define the counters
n F ( R m ) = # { i : τ i = 0 } , n J ( R m ) = # { i : τ i = 1 } . n_F(R_m) = \#\{i : \tau_i = 0\},\qquad n_J(R_m) = \#\{i : \tau_i = 1\}. n F ( R m ) = # { i : τ i = 0 } , n J ( R m ) = # { i : τ i = 1 } . Each request is counted once, even when it exactly repeats a previous one. Reusing a known response is not a new query. Arithmetic operations, factorizations, and internal comparisons are not counted here.
Definition 2.4 (Local budget). We say that M \mathcal{M} M ( N F , N J ) (N_F,N_J) ( N F , N J ) F n \mathcal{F}_n F n ( Ω , F , α ) ∈ F n (\Omega,F,\alpha) \in\mathcal{F}_n ( Ω , F , α ) ∈ F n δ F , α > 0 \delta_{F,\alpha} > 0 δ F , α > 0
0 < ∥ x − α ∥ ∞ < δ F , α , 0 < \lVert x-\alpha\rVert_\infty< \delta_{F,\alpha}, 0 < ∥ x − α ∥ ∞ < δ F , α , the execution is valid and satisfies n F ≤ N F n_F \le N_F n F ≤ N F n J ≤ N J n_J \le N_J n J ≤ N J
Definition 2.5 (Universal local order). The method has universal local order at least p > 1 p > 1 p > 1 F n \mathcal{F}_n F n C F , α , ρ F , α > 0 C_{F,\alpha},\rho_{F,\alpha} > 0 C F , α , ρ F , α > 0
∥ M F ( x ) − α ∥ ∞ ≤ C F , α ∥ x − α ∥ ∞ p ( 0 < ∥ x − α ∥ ∞ < ρ F , α ) . (5) \lVert\mathcal{M}_F(x)-\alpha\rVert_\infty\le C_{F,\alpha}\lVert x-\alpha\rVert_\infty^p \qquad(0 < \lVert x-\alpha\rVert_\infty< \rho_{F,\alpha}). \tag*{(5)} ∥ M F ( x ) − α ∥ ∞ ≤ C F , α ∥ x − α ∥ ∞ p ( 0 < ∥ x − α ∥ ∞ < ρ F , α ) . (5) The exponent is common to the class; the constants are not. By intersecting the neighborhoods in the two definitions, we can require well-definedness, budget, and error estimate simultaneously.
Preservation of responses and internal procedures
Lemma 2.6 (Indistinguishability). Suppose that an execution of M \mathcal{M} M F F F x x x F ~ \widetilde{F} F F ~ \widetilde{F} F x x x
Proof. The initial histories coincide. Suppose that they coincide after k k k Φ k \Phi_k Φ k k + 1 k+1 k + 1
Finite budgets and scalar representation
Extension of the rules with budget control
Lemma 3.1 (Truncation and total extension). Let N F , N J ∈ N 0 N_F, N_J \in\mathbb{N}_0 N F , N J ∈ N 0 d = N F + N J ≥ 1 d = N_F + N_J \ge1 d = N F + N J ≥ 1 M \mathcal{M} M M ^ \widehat{\mathcal{M}} M R n \mathbb{R}^n R n d d d M \mathcal{M} M
Proof. For k < d k < d k < d d d d
The rules so obtained are total maps and are fixed without knowledge of F F F d d d
Now consider a valid original execution with counters no greater than the budgets. At each of its prefixes, the original rule is defined. No query exceeds its counter, and the final output is reached at a level no greater than d d d
The extension also preserves a valid execution on a field defined on an open set if we compare it with an extension of the field that agrees at all its nodes. Only the responses at those nodes are used.
Reconstruction of a vector response
For s ∈ R s \in\mathbb{R} s ∈ R
ι ( s ) = ( s , 0 , … , 0 ) T . \iota(s) = (s, 0, \ldots, 0)^{T}. ι ( s ) = ( s , 0 , … , 0 ) T . Given Y ∈ R n Y \in\mathbb{R}^{n} Y ∈ R n η \eta η
R 0 ( Y , η ) = ( η , Y 2 , … , Y n ) T , R 1 ( Y , η ) = diag ( η , 1 , … , 1 ) . \mathcal{R}_0(Y,\eta) = (\eta, Y_2, \ldots, Y_n)^{T}, \qquad\mathcal{R}_1(Y,\eta) = \operatorname{diag}(\eta,1,\ldots,1). R 0 ( Y , η ) = ( η , Y 2 , … , Y n ) T , R 1 ( Y , η ) = diag ( η , 1 , … , 1 ) . Equation not extracted
(6) These maps do not depend on f f f
G f ( Y ) = R 0 ( Y , f ( Y 1 ) ) , D G f ( Y ) = R 1 ( Y , f ′ ( Y 1 ) ) . G_f(Y) = \mathcal{R}_0(Y,f(Y_1)), \qquad DG_f(Y) = \mathcal{R}_1(Y,f'(Y_1)). G f ( Y ) = R 0 ( Y , f ( Y 1 )) , D G f ( Y ) = R 1 ( Y , f ′ ( Y 1 )) . Theorem 3.2 (Exact simulation without additional queries). Let M \mathcal{M} M There exists a scalar method T T T f f f f ′ f' f ′ G f G_f G f ι ( s ) \iota(s) ι ( s )
T f ( s ) = ( M G f ( ι ( s ) ) ) 1 . (7) T_f(s) = \left(\mathcal{M}_{G_f}(\iota(s))\right)_1. \tag*{(7)} T f ( s ) = ( M G f ( ι ( s )) ) 1 . (7) Each vector function query corresponds to a query to f f f f ′ f' f ′ R n \mathbb{R}^n R n I × R n − 1 I \times\mathbb{R}^{n-1} I × R n − 1
Proof. The initial scalar datum is s s s ι ( s ) \iota(s) ι ( s ) v v v v 1 v_1 v 1 τ \tau τ Y Y Y f ( τ ) ( Y 1 ) f^{(\tau)}(Y_1) f ( τ ) ( Y 1 ) η \eta η
Suppose that, after k k k s s s k k k
This defines scalar rules that depend only on the initial datum and previous responses. The vector nodes, their coordinates, and their types can be reconstructed inductively; they are not supplied as external data. On numerical histories that do not correspond to a reconstruction, we may leave the rule undefined or, for an already truncated total method, return zero.
When applying these rules to a function f f f G f G_f G f
If f f f I I I Y Y Y I × R n − 1 I \times\mathbb{R}^{n-1} I × R n − 1 Y 1 ∈ I Y_1 \in I Y 1 ∈ I
Finally, every request is replaced by exactly one of the same type. We have not assumed that Y 2 = ⋯ = Y n = 0 Y_2 = \cdots= Y_n = 0 Y 2 = ⋯ = Y n = 0 □ \square □
Corollary 3.3 (Transfer of a local estimate). If M \mathcal{M} M α = ι ( a ) \alpha= \iota(a) α = ι ( a )
∣ T f ( s ) − a ∣ ≤ C G f , α ∣ s − a ∣ p |T_f(s)-a| \le C_{G_f,\alpha}|s-a|^p ∣ T f ( s ) − a ∣ ≤ C G f , α ∣ s − a ∣ p for s s s a a a
Proof. We have ∥ ι ( s ) − ι ( a ) ∥ ∞ = ∣ s − a ∣ \|\iota(s)-\iota(a)\|_\infty= |s-a| ∥ ι ( s ) − ι ( a ) ∥ ∞ = ∣ s − a ∣
∣ T f ( s ) − a ∣ ≤ ∥ M G f ( ι ( s ) ) − ι ( a ) ∥ ∞ . |T_f(s)-a| \le\left\|\mathcal{M}_{G_f}(\iota(s))-\iota(a)\right\|_\infty. ∣ T f ( s ) − a ∣ ≤ M G f ( ι ( s )) − ι ( a ) ∞ . We apply the vector estimate and shrink the neighborhood so that the budgets also hold. □ \square □
Scalar rules on response vectors
Lemma 3.4 (Compatibility with the scalar query model). Let M ^ \widehat{\mathcal{M}} M d d d d d d
Ψ k : R k + 1 ⟶ ( { c } × ( R × N 0 ) ) ⊔ ( { s } × R ) , 0 ≤ k ≤ d , \Psi_k : \mathbb{R}^{k+1} \longrightarrow\left(\{\mathsf{c}\} \times(\mathbb{R} \times\mathbb{N}_0)\right) \sqcup\left(\{\mathsf{s}\} \times\mathbb{R}\right), \qquad0 \le k \le d, Ψ k : R k + 1 ⟶ ( { c } × ( R × N 0 ) ) ⊔ ( { s } × R ) , 0 ≤ k ≤ d , with Ψ d \Psi_d Ψ d [1 Definition 2.4] . Only derivatives of orders zero and one are requested. For every real entire function f f f s ∈ R s \in\mathbb{R} s ∈ R M ^ \widehat{\mathcal{M}} M G f G_f G f ι ( s ) \iota(s) ι ( s ) M \mathcal{M} M d d d f f f
Proof. The level-k k k
h k = ( s , η 1 , … , η k ) ∈ R k + 1 . h_k = (s,\eta_1,\ldots,\eta_k) \in\mathbb{R}^{k+1}. h k = ( s , η 1 , … , η k ) ∈ R k + 1 . We must also define the rules on numerical vectors that occur in no execution. To this end, we add a label ⊥ \perp ⊥
S k = H k ⊔ ( { ⊥ } × R n ) . S_k = \mathcal{H}_k \sqcup(\{\perp\} \times\mathbb{R}^n). S k = H k ⊔ ({ ⊥ } × R n ) . An element of the second part indicates that reconstruction has already terminated with a vector output, which we shall preserve without using new responses.
We define total maps ρ k : R k + 1 → S k \rho_k:\mathbb{R}^{k+1} \to S_k ρ k : R k + 1 → S k
ρ 0 ( s ) = ( ι ( s ) , ( ) ) . \rho_0(s) = (\iota(s),()). ρ 0 ( s ) = ( ι ( s ) , ( )) . Suppose ρ k \rho_k ρ k k < d k<d k < d ρ k ( h k ) = ( ⊥ , v ) \rho_k(h_k)=(\perp,v) ρ k ( h k ) = ( ⊥ , v )
ρ k + 1 ( h k , η ) = ( ⊥ , v ) ( η ∈ R ) . \rho_{k+1}(h_k,\eta)=(\perp,v) \qquad(\eta\in\mathbb{R}). ρ k + 1 ( h k , η ) = ( ⊥ , v ) ( η ∈ R ) . If ρ k ( h k ) = ( ι ( s ) , R k ) ∈ H k \rho_k(h_k)=(\iota(s),R_k)\in\mathcal{H}_k ρ k ( h k ) = ( ι ( s ) , R k ) ∈ H k Φ ^ k \widehat{\Phi}_k Φ k ( s , v ) (s,v) ( s , v ) ρ k + 1 ( h k , η ) = ( ⊥ , v ) \rho_{k+1}(h_k,\eta)=(\perp,v) ρ k + 1 ( h k , η ) = ( ⊥ , v ) ( c , ( τ , Y ) ) (c,(\tau,Y)) ( c , ( τ , Y ))
ρ k + 1 ( h k , η ) = ( ι ( s ) , R k ∥ ( τ , Y , R τ ( Y , η ) ) ) , \rho_{k+1}(h_k,\eta)=\left(\iota(s),R_k\mathbin{\|}\left(\tau,Y,\mathcal{R}_{\tau}(Y,\eta)\right)\right), ρ k + 1 ( h k , η ) = ( ι ( s ) , R k ∥ ( τ , Y , R τ ( Y , η ) ) ) , where R k ∥ ( τ , Y , A ) R_k\mathbin{\|}(\tau,Y,A) R k ∥ ( τ , Y , A ) R k R_k R k R τ \mathcal{R}_{\tau} R τ (6) . Its value belongs to the response space of the corresponding type, regardless of η \eta η
Now define Ψ k \Psi_k Ψ k ρ k ( h k ) = ( ⊥ , v ) \rho_k(h_k)=(\perp,v) ρ k ( h k ) = ( ⊥ , v ) Ψ k ( h k ) = ( s , v 1 ) \Psi_k(h_k)=(s,v_1) Ψ k ( h k ) = ( s , v 1 ) Φ ^ k ( ρ k ( h k ) ) \widehat{\Phi}_k(\rho_k(h_k)) Φ k ( ρ k ( h k )) ( s , v ) (s,v) ( s , v ) ( s , v 1 ) (s,v_1) ( s , v 1 ) ( c , ( τ , Y ) ) (c,(\tau,Y)) ( c , ( τ , Y ))
Ψ k ( h k ) = ( c , ( Y 1 , τ ) ) . \Psi_k(h_k)=(c,(Y_1,\tau)). Ψ k ( h k ) = ( c , ( Y 1 , τ )) . In the last expression, we write the node first and then the derivative order, as in the model of [1 ] . The totality of ρ k \rho_k ρ k Φ ^ k \widehat{\Phi}_k Φ k Ψ k \Psi_k Ψ k d d d d d d
Now fix f ∈ E R f\in\mathcal{E}_{\mathbb{R}} f ∈ E R s ∈ R s\in\mathbb{R} s ∈ R ρ k ( h k ) \rho_k(h_k) ρ k ( h k ) k k k k = 0 k=0 k = 0 ( Y 1 , τ ) (Y_1,\tau) ( Y 1 , τ ) η = f ( τ ) ( Y 1 ) \eta=f^{(\tau)}(Y_1) η = f ( τ ) ( Y 1 ) (6) , the appended triple contains exactly the response of G f G_f G f D G f DG_f D G f Y Y Y
The states labeled ⊥ \perp ⊥
The general Cordero–Torregrosa barrier
The scalar result used
The following theorem is the query result that we shall use from [1 ] . Its complete analytic construction is developed there: the version for one exponent is Theorem 7.5 and the simultaneous choice is Proposition 7.7. We state precisely the form required for our transfer.
Theorem 4.1 (Scalar query barrier, Castro Marín). Let T T T d ≥ 1 d \ge1 d ≥ 1 f ∈ E ∗ f \in\mathcal{E}_* f ∈ E ∗ a a a s m > a s_m > a s m > a s m → a s_m \to a s m → a p > 2 d − 1 p > 2^{d-1} p > 2 d − 1
∣ T f ( s m ) − a ∣ ( s m − a ) p ⟶ + ∞ . (8) \frac{\lvert T_f(s_m)-a\rvert}{(s_m-a)^p} \longrightarrow+\infty. \tag*{(8)} ( s m − a ) p ∣ T f ( s m ) − a ∣ ⟶ + ∞. (8) In our case, the only derivative orders queried by the induced method will be zero and one. This restriction yields a subclass of the procedures admitted by the theorem. Lemma 3.4 explicitly identifies the induced rules with total maps on the response vectors of the scalar model.
Theorem 4.1 is used as a previous result from [1 Proposition 7.7] ; its analytic construction is not reproduced in this section. The following general barrier is a consequence of that result and exact simulation. In contrast, the paired barrier of Section 9 will be proved through the construction developed in the present work, without using Theorem 4.1.
A fixed analytic field for general methods
Theorem 4.2 (Vector barrier with arbitrary rules). Let n ≥ 1 n \ge1 n ≥ 1 N F , N J ∈ N 0 N_F, N_J \in\mathbb{N}_0 N F , N J ∈ N 0 d = N F + N J ≥ 1 d = N_F+N_J \ge1 d = N F + N J ≥ 1 M \mathcal{M} M ( N F , N J ) (N_F,N_J) ( N F , N J ) H n ( I 0 ) \mathcal{H}_n(I_0) H n ( I 0 ) f ∈ E ∗ f \in\mathcal{E}_* f ∈ E ∗ G f G_f G f α = ι ( a f ) \alpha= \iota(a_f) α = ι ( a f ) X m = ι ( s m ) X_m = \iota(s_m) X m = ι ( s m ) s m > a f s_m > a_f s m > a f s m → a f s_m \to a_f s m → a f m m m
∥ M G f ( X m ) − α ∥ ∞ ∥ X m − α ∥ ∞ p ⟶ + ∞ for every p > 2 N F + N J − 1 . (9) \frac{\lVert\mathcal{M}_{G_f}(X_m)-\alpha\rVert_\infty}{\lVert X_m-\alpha\rVert_\infty^p} \longrightarrow+\infty\qquad\text{for every } p > 2^{N_F+N_J-1}. \tag*{(9)} ∥ X m − α ∥ ∞ p ∥ M G f ( X m ) − α ∥ ∞ ⟶ + ∞ for every p > 2 N F + N J − 1 . (9) The field, root, and sequence are chosen before the final exponent p p p
Proof. We apply Lemma 3.1 to the rules of M \mathcal{M} M M ^ \widehat{\mathcal{M}} M I 0 I_0 I 0 f f f
By Theorem 3.2 and Lemma 3.4, the execution of M ^ \widehat{\mathcal{M}} M G f G_f G f R k + 1 \mathbb{R}^{k+1} R k + 1 0 ≤ k ≤ d 0 \le k \le d 0 ≤ k ≤ d d d d d d d f f f f f f a = a f a = a_f a = a f ( s m ) (s_m) ( s m )
Now consider the problem in (2.1), with the domain Ω 0 \Omega_0 Ω 0 m m m X m = ι ( s m ) X_m=\iota(s_m) X m = ι ( s m ) Ω 0 \Omega_0 Ω 0
M G f ( X m ) = M ^ G f ( X m ) \mathcal{M}_{G_f}(X_m)=\widehat{\mathcal{M}}_{G_f}(X_m) M G f ( X m ) = M G f ( X m ) for all these indices. On the right we use the global field, and on the left its restriction when I 0 = ( − 1 , 1 ) I_0=(-1,1) I 0 = ( − 1 , 1 )
The first component of the right-hand side is T f ( s m ) T_f(s_m) T f ( s m )
∥ X m − α ∥ ∞ = s m − a , ∥ M G f ( X m ) − α ∥ ∞ ≥ ∣ T f ( s m ) − a ∣ . \lVert X_m-\alpha\rVert_\infty=s_m-a,\qquad\lVert\mathcal{M}_{G_f}(X_m)-\alpha\rVert_\infty\geq\lvert T_f(s_m)-a\rvert. ∥ X m − α ∥ ∞ = s m − a , ∥ M G f ( X m ) − α ∥ ∞ ≥ ∣ T f ( s m ) − a ∣ . Dividing by ( s m − a ) p (s_m-a)^p ( s m − a ) p (8) , we obtain (9) . The index from which the executions coincide depends only on the problem and its budget neighborhood, not on p p p
Corollary 4.3 (Cordero–Torregrosa bound). Under the preceding hypotheses, if M \mathcal{M} M p > 1 p>1 p > 1 F n ⊃ H n ( I 0 ) \mathcal{F}_n\supset\mathcal{H}_n(I_0) F n ⊃ H n ( I 0 )
p ≤ 2 N F + N J − 1 . (10) p\leq2^{N_F+N_J-1}. \tag*{(10)} p ≤ 2 N F + N J − 1 . (10) Proof. If p p p
Remark 4.4 (Hypotheses not used). The proof does not prescribe the first node or the order of queries. It does not require starting with F ( x ) F(x) F ( x ) D F ( x ) DF(x) D F ( x )
Remark 4.5 (The function class cannot be arbitrarily small). The theorem uses entire test fields. With arbitrary rules, it does not establish a barrier on the class consisting only of polynomials of a fixed degree. Nor does a prohibition of high order hold on every subclass: for affine fields with invertible Jacobian, one Newton step solves the problem exactly. The generality of the rules and the breadth of the function class are distinct conditions.
Paired queries and construction integers
Pairing and repetition
Definition 5.1 (Causal pairing). A record is paired if, for every Jacobian query ( 1 , y ) (1,y) ( 1 , y ) ( 0 , y ) (0,y) ( 0 , y )
Repeating F ( y ) F(y) F ( y ) D F ( y ) DF(y) D F ( y )
Lemma 5.2 (Extension preserving pairing). If M \mathcal{M} M ( N F , N J ) (N_F,N_J) ( N F , N J )
Proof. We add a condition to Lemma 3.1 before preserving a type-1 query: the history must contain an earlier type-0 query at the same node. If it does not, we return zero instead of querying. This check uses only the record and equality of two known points. Every preserved execution satisfies the condition. By induction, the extension never makes an unpaired derivative query. In an original execution with the required property, the substitution is not activated and all its data are preserved.
The simulation in Theorem 3.2 preserves pairing. Indeed, if D F ( Y ) DF(Y) D F ( Y ) F ( Y ) F(Y) F ( Y ) f ′ ( Y 1 ) f'(Y_1) f ′ ( Y 1 ) f ( Y 1 ) f(Y_1) f ( Y 1 )
Integers associated with a record
Consider a paired scalar record. To each distinct function node u i u_i u i e i ≥ 1 e_i \ge1 e i ≥ 1 μ i ∈ { 1 , 2 } \mu_i \in\{1,2\} μ i ∈ { 1 , 2 } f ( u i ) f(u_i) f ( u i ) f ′ ( u i ) f'(u_i) f ′ ( u i )
We start with an empty list and E = 0 E=0 E = 0
e n e w = max { 1 , E } , μ n e w = 1 , E + = E + e n e w . (11) e_{\mathrm{new}}=\max\{1,E\},\qquad\mu_{\mathrm{new}}=1,\qquad E^+=E+e_{\mathrm{new}}. \tag*{(11)} e new = max { 1 , E } , μ new = 1 , E + = E + e new . (11) When first querying the derivative at a node of multiplicity 1, we put
μ i + = 2 , E + = E + e i . (12) \mu_i^+=2,\qquad E^+=E+e_i. \tag*{(12)} μ i + = 2 , E + = E + e i . (12) A repeated query does not change the list. At every stage,
E = ∑ i μ i e i . E=\sum_i \mu_i e_i. E = i ∑ μ i e i . These integers are used in the proof. We do not suppose that the nodes depend regularly on a parameter or have any prescribed asymptotic order.
For N F ≥ 1 N_F \ge1 N F ≥ 1 N J ≥ 0 N_J \ge0 N J ≥ 0 s = min { N F , N J } s=\min\{N_F,N_J\} s = min { N F , N J }
B ( N F , N J ) = { 2 N F − 1 , s = 0 , 2 N F − s + 1 3 s − 1 , s ≥ 1. (13) B(N_F,N_J)=
\begin{cases}
2^{N_F-1}, & s=0,\\
2^{N_F-s+1}3^{s-1}, & s\ge1.
\end{cases} \tag*{(13)} B ( N F , N J ) = { 2 N F − 1 , 2 N F − s + 1 3 s − 1 , s = 0 , s ≥ 1. (13) If 1 ≤ N J ≤ N F 1\le N_J\le N_F 1 ≤ N J ≤ N F (2) .
Lemma 5.3 (Growth of the construction integers). For every paired record with at most N F N_F N F N J N_J N J
max { 1 , E } ≤ B ( N F , N J ) . (14) \max\{1,E\}\le B(N_F,N_J). \tag*{(14)} max { 1 , E } ≤ B ( N F , N J ) . (14) Proof. If there are no nodes, E = 0 E=0 E = 0 v ≥ 1 v\ge1 v ≥ 1 r r r
v ≤ N F , r ≤ min { v , N J } . v\le N_F,\qquad r\le\min\{v,N_J\}. v ≤ N F , r ≤ min { v , N J } . The first node receives exponent e 1 = 1 e_1=1 e 1 = 1 E = 1 E=1 E = 1 E E E E E E
Consider a first derivative query at a node other than the first. Let e i e_i e i e i e_i e i 2 e i 2e_i 2 e i E ≥ 2 e i E\ge2e_i E ≥ 2 e i
E + = E + e i ≤ 3 2 E E^+=E+e_i\le\frac{3}{2}E E + = E + e i ≤ 2 3 E For the first node, we only need e 1 = 1 ≤ E e_1 = 1 \le E e 1 = 1 ≤ E E + ≤ 2 E E^+ \le2E E + ≤ 2 E
If r = 0 r = 0 r = 0 E ≤ 2 v − 1 E \le2^{v-1} E ≤ 2 v − 1 r ≥ 1 r \ge1 r ≥ 1
E ≤ 2 v − 1 2 ( 3 2 ) r − 1 = 2 v − r + 1 3 r − 1 . E \le2^{v-1} 2 \left(\frac{3}{2}\right)^{r-1} = 2^{v-r+1}3^{r-1}. E ≤ 2 v − 1 2 ( 2 3 ) r − 1 = 2 v − r + 1 3 r − 1 . If that derivative has not been queried, all r r r 3 / 2 3/2 3/2
E ≤ 2 v − 1 ( 3 2 ) r = 3 4 2 v − r + 1 3 r − 1 ≤ 2 v − r + 1 3 r − 1 . E \le2^{v-1}\left(\frac{3}{2}\right)^r = \frac{3}{4}2^{v-r+1}3^{r-1} \le2^{v-r+1}3^{r-1}. E ≤ 2 v − 1 ( 2 3 ) r = 4 3 2 v − r + 1 3 r − 1 ≤ 2 v − r + 1 3 r − 1 . Repetitions do not change these estimates.
The bound 2 v − 1 2^{v-1} 2 v − 1 v v v 3 / 2 3/2 3/2 v ≤ N F v \le N_F v ≤ N F r ≤ min { v , N J } r \le\min\{v,N_J\} r ≤ min { v , N J }
Remark 5.4. The maximum of the integer process is attained by starting with one function node, querying its derivative when s ≥ 1 s \ge1 s ≥ 1 s − 1 s - 1 s − 1 N F − s N_F - s N F − s
Polynomial tools for preserving responses
Norms on disks and normalized factors
For a real polynomial h h h R > 0 R > 0 R > 0
∥ h ∥ R = max ∣ z ∣ ≤ R ∣ h ( z ) ∣ . \|h\|_R = \max_{|z|\le R}|h(z)|. ∥ h ∥ R = ∣ z ∣ ≤ R max ∣ h ( z ) ∣. where its extension to the complex variable is used. If R ≥ 3 R \ge3 R ≥ 3 u ∈ [ − 1 , 1 ] u \in[-1,1] u ∈ [ − 1 , 1 ] ∣ z − u ∣ = 1 |z-u|=1 ∣ z − u ∣ = 1
∣ h ′ ( u ) ∣ ≤ ∥ h ∥ R . (15) |h'(u)| \le\|h\|_R. \tag*{(15)} ∣ h ′ ( u ) ∣ ≤ ∥ h ∥ R . (15) For any compact disk contained in the interior, bounds for each derivative of fixed order are obtained in the same way.
For a real node u u u
L u ( z ) = z − u 1 + ∣ u ∣ . (16) L_u(z) = \frac{z-u}{1+|u|}. \tag*{(16)} L u ( z ) = 1 + ∣ u ∣ z − u . (16) It has real coefficients and vanishes exactly at u u u R ≥ 1 R \ge1 R ≥ 1
∥ L u ∥ R ≤ R + 1 , ∣ L u ( b ) ∣ ≤ 1 if ∣ b ∣ ≤ 1 2 . (17) \|L_u\|_R \le R+1,\qquad|L_u(b)|\le1\quad\text{if }|b|\le\frac{1}{2}. \tag*{(17)} ∥ L u ∥ R ≤ R + 1 , ∣ L u ( b ) ∣ ≤ 1 if ∣ b ∣ ≤ 2 1 . (17) Indeed,
∣ L u ( z ) ∣ ≤ ∣ z ∣ + ∣ u ∣ 1 + ∣ u ∣ ≤ R + 1 , ∣ L u ( b ) ∣ ≤ 1 / 2 + ∣ u ∣ 1 + ∣ u ∣ ≤ 1. |L_u(z)| \le\frac{|z|+|u|}{1+|u|}\le R+1,\qquad|L_u(b)|\le\frac{1/2+|u|}{1+|u|}\le1. ∣ L u ( z ) ∣ ≤ 1 + ∣ u ∣ ∣ z ∣ + ∣ u ∣ ≤ R + 1 , ∣ L u ( b ) ∣ ≤ 1 + ∣ u ∣ 1/2 + ∣ u ∣ ≤ 1. These bounds are uniform with respect to u u u
Let P P P I ⊂ ( − 1 / 2 , 1 / 2 ) I \subset(-1/2,1/2) I ⊂ ( − 1/2 , 1/2 ) P P P
H ( z ) = P ( z ) ∏ i = 1 ν L u i ( z ) μ i , μ i ∈ { 1 , 2 } , ∑ i μ i ≤ d . (18) H(z)=P(z)\prod_{i=1}^{\nu}L_{u_i}(z)^{\mu_i},\qquad\mu_i\in\{1,2\},\qquad\sum_i\mu_i\le d. \tag*{(18)} H ( z ) = P ( z ) i = 1 ∏ ν L u i ( z ) μ i , μ i ∈ { 1 , 2 } , i ∑ μ i ≤ d . (18) We define
p − : = min I ∣ P ∣ > 0 , K 0 : = max { 1 , max I ∣ P ∣ } , K R : = max { 1 , ∥ P ∥ R ( R + 1 ) d } . p_-:=\min_I|P|>0,\qquad K_0:=\max\{1,\max_I|P|\},\qquad K_R:=\max\{1,\|P\|_R(R+1)^d\}. p − := I min ∣ P ∣ > 0 , K 0 := max { 1 , I max ∣ P ∣ } , K R := max { 1 , ∥ P ∥ R ( R + 1 ) d } . Then
∥ H ∥ R ≤ K R , ∣ H ( b ) ∣ ≤ K 0 ( b ∈ I ) . (19) \|H\|_R\le K_R,\qquad|H(b)|\le K_0\quad(b\in I). \tag*{(19)} ∥ H ∥ R ≤ K R , ∣ H ( b ) ∣ ≤ K 0 ( b ∈ I ) . (19) Moreover, for each node present and every b ∈ I b\in I b ∈ I
∣ H ( b ) ∣ ≤ K 0 ∣ b − u i ∣ . (20) |H(b)|\le K_0|b-u_i|. \tag*{(20)} ∣ H ( b ) ∣ ≤ K 0 ∣ b − u i ∣. (20) To verify the last inequality, we extract one copy of the factor L u i L_{u_i} L u i 1 / ( 1 + ∣ u i ∣ ) ≤ 1 1/(1+|u_i|)\le1 1/ ( 1 + ∣ u i ∣ ) ≤ 1
Lemma 6.1 (Preservation by simple and double factors). Suppose that a scalar record is paired. If each node at which only the function value is known has multiplicity 1, and each node at which the derivative is also known has multiplicity 2, the polynomial H H H
H ( u ) = 0 at every function query , H ′ ( v ) = 0 at every derivative query . H(u)=0\quad\text{at every function query},\qquad H'(v)=0\quad\text{at every derivative query}. H ( u ) = 0 at every function query , H ′ ( v ) = 0 at every derivative query . Therefore, adding a multiple of H H H
Proof. A simple factor imposes the first vanishing condition. At each derivative node there is a double factor, so both the product and its derivative vanish there. An additional factor P P P
Roots in a fixed interval
Lemma 6.2 (Uniform neighborhood of a polynomial). Let f , P ∈ R [ z ] f,P\in\mathbb{R}[z] f , P ∈ R [ z ] a ∈ ( − 1 / 2 , 1 / 2 ) a\in(-1/2,1/2) a ∈ ( − 1/2 , 1/2 ) f ( a ) = 0 f(a)=0 f ( a ) = 0 f ′ ( a ) > 0 f'(a)>0 f ′ ( a ) > 0 P ( a ) ≠ 0 P(a)\ne0 P ( a ) = 0 R ≥ 3 R\ge3 R ≥ 3 ε > 0 \varepsilon>0 ε > 0 r , δ , m , M > 0 r,\delta,m,M>0 r , δ , m , M > 0 I = [ a − r , a + r ] ⊂ ( − 1 / 2 , 1 / 2 ) I=[a-r,a+r]\subset(-1/2,1/2) I = [ a − r , a + r ] ⊂ ( − 1/2 , 1/2 ) P P P I I I δ ≤ ε \delta\le\varepsilon δ ≤ ε g g g ∥ g − f ∥ R < δ \|g-f\|_R<\delta ∥ g − f ∥ R < δ b ∈ I b\in I b ∈ I
0 < m ≤ g ′ ( u ) ≤ M ( u ∈ I ) . (21) 0<m\le g'(u)\le M\qquad(u\in I). \tag*{(21)} 0 < m ≤ g ′ ( u ) ≤ M ( u ∈ I ) . (21) Proof. By continuity, choose r > 0 r>0 r > 0 I ⊂ ( − 1 / 2 , 1 / 2 ) I\subset(-1/2,1/2) I ⊂ ( − 1/2 , 1/2 ) f ′ > 0 f'>0 f ′ > 0 P ≠ 0 P\ne0 P = 0 I I I
m = 1 2 min I f ′ > 0 , M = max I f ′ + 1. m=\frac{1}{2}\min_I f'>0,\qquad M=\max_I f'+1. m = 2 1 I min f ′ > 0 , M = I max f ′ + 1. Choose
0 < δ < min { ε , 1 , m , m r } . 0<\delta<\min\{\varepsilon,1,m,mr\}. 0 < δ < min { ε , 1 , m , m r } . By (6.1), ∣ g ′ − f ′ ∣ ≤ ∥ g − f ∥ R < δ |g'-f'|\le\|g-f\|_R<\delta ∣ g ′ − f ′ ∣ ≤ ∥ g − f ∥ R < δ I I I f ( a ) = 0 f(a)=0 f ( a ) = 0 f ′ ≥ 2 m f'\ge2m f ′ ≥ 2 m
f ( a + r ) ≥ 2 m r , f ( a − r ) ≤ − 2 m r . f(a+r)\ge2mr,\qquad f(a-r)\le-2mr. f ( a + r ) ≥ 2 m r , f ( a − r ) ≤ − 2 m r . The bound ∣ g − f ∣ < δ < m r |g-f|<\delta<mr ∣ g − f ∣ < δ < m r g ′ ≥ m g'\ge m g ′ ≥ m
Lemma 6.3 (Choice between two roots). Suppose that g g g g ± η H g \pm\eta H g ± η H η > 0 \eta> 0 η > 0 I I I b b b b + b_{+} b + b − b_{-} b − H ( b ) ≠ 0 H(b) \ne0 H ( b ) = 0 b + b_{+} b + b − b_{-} b − b b b
η ∣ H ( b ) ∣ M ≤ ∣ b ± − b ∣ ≤ η ∣ H ( b ) ∣ m . (22) \frac{\eta\lvert H(b)\rvert}{M} \le\lvert b_{\pm}-b\rvert\le\frac{\eta\lvert H(b)\rvert}{m}. \tag*{(22)} M η ∣ H ( b )∣ ≤ ∣ b ± − b ∣ ≤ m η ∣ H ( b )∣ . (22) For every y ∈ R y \in\mathbb{R} y ∈ R
∣ b ± − y ∣ ≥ η ∣ H ( b ) ∣ M . (23) \lvert b_{\pm}-y\rvert\ge\frac{\eta\lvert H(b)\rvert}{M}. \tag*{(23)} ∣ b ± − y ∣ ≥ M η ∣ H ( b )∣ . (23) Proof. We have ( g ± η H ) ( b ) = ± η H ( b ) (g \pm\eta H)(b) = \pm\eta H(b) ( g ± η H ) ( b ) = ± η H ( b ) b b b b ± b_{\pm} b ±
b ± − b = ∓ η H ( b ) ( g ± η H ) ′ ( ξ ± ) b_{\pm}-b = \frac{\mp\eta H(b)}{(g \pm\eta H)'(\xi_{\pm})} b ± − b = ( g ± η H ) ′ ( ξ ± ) ∓ η H ( b ) for intermediate points ξ ± ∈ I \xi_{\pm} \in I ξ ± ∈ I [ m , M ] [m,M] [ m , M ]
∣ b + − b − ∣ = ∣ b + − b ∣ + ∣ b − − b ∣ ≥ 2 η ∣ H ( b ) ∣ M . \lvert b_{+}-b_{-}\rvert= \lvert b_{+}-b\rvert+ \lvert b_{-}-b\rvert\ge\frac{2\eta\lvert H(b)\rvert}{M}. ∣ b + − b − ∣ = ∣ b + − b ∣ + ∣ b − − b ∣ ≥ M 2 η ∣ H ( b )∣ . The triangle inequality implies
max { ∣ b + − y ∣ , ∣ b − − y ∣ } ≥ 1 2 ∣ b + − b − ∣ , \max\{\lvert b_{+}-y\rvert,\lvert b_{-}-y\rvert\} \ge\frac{1}{2}\lvert b_{+}-b_{-}\rvert, max {∣ b + − y ∣ , ∣ b − − y ∣} ≥ 2 1 ∣ b + − b − ∣ , and we obtain (6.9).
An amplitude that controls the root without losing the exponent
Fix λ > 0 \lambda> 0 λ > 0 0 < t < 1 0 < t < 1 0 < t < 1 H ( b ) ≠ 0 H(b) \ne0 H ( b ) = 0
η = λ min { 1 , t ∣ H ( b ) ∣ } . (24) \eta= \lambda\min\left\{1,\frac{t}{\lvert H(b)\rvert}\right\}. \tag*{(24)} η = λ min { 1 , ∣ H ( b )∣ t } . (24) Then
η ∣ H ( b ) ∣ = λ min { ∣ H ( b ) ∣ , t } , 0 < η ≤ λ . (25) \eta\lvert H(b)\rvert= \lambda\min\{\lvert H(b)\rvert,t\}, \qquad0 < \eta\le\lambda. \tag*{(25)} η ∣ H ( b )∣ = λ min {∣ H ( b )∣ , t } , 0 < η ≤ λ . (25) The constant λ \lambda λ t t t η \eta η
Lemma 6.4 (Preservation of separations and a new node). Suppose that H H H b ∈ I b \in I b ∈ I η \eta η λ K 0 / m ≤ 1 / 2 \lambda K_{0}/m \le1/2 λ K 0 / m ≤ 1/2
For either root b ± b_{\pm} b ±
∣ b ± − u i ∣ 1 + ∣ u i ∣ ≥ 1 2 ∣ b − u i ∣ 1 + ∣ u i ∣ . (26) \frac{\lvert b_{\pm}-u_i\rvert}{1+\lvert u_i\rvert} \ge\frac{1}{2}\frac{\lvert b-u_i\rvert}{1+\lvert u_i\rvert}. \tag*{(26)} 1 + ∣ u i ∣ ∣ b ± − u i ∣ ≥ 2 1 1 + ∣ u i ∣ ∣ b − u i ∣ . (26) For every new node y y y
∣ b ± − y ∣ 1 + ∣ y ∣ ≥ κ min { ∣ H ( b ) ∣ , t } , κ = min { λ 3 M , 1 2 } . (27) \frac{\lvert b_{\pm}-y\rvert}{1+\lvert y\rvert} \ge\kappa\min\{\lvert H(b)\rvert,t\}, \qquad\kappa= \min\left\{\frac{\lambda}{3M},\frac{1}{2}\right\}. \tag*{(27)} 1 + ∣ y ∣ ∣ b ± − y ∣ ≥ κ min {∣ H ( b )∣ , t } , κ = min { 3 M λ , 2 1 } . (27) Moreover, ∣ b ± − b ∣ ≤ λ t / m \lvert b_{\pm}-b\rvert\le\lambda t/m ∣ b ± − b ∣ ≤ λ t / m
Proof. By (22) , (20) , and η ≤ λ \eta\le\lambda η ≤ λ
∣ b ± − b ∣ ≤ λ K 0 m ∣ b − u i ∣ ≤ 1 2 ∣ b − u i ∣ . |b_{\pm}-b| \le\frac{\lambda K_0}{m}|b-u_i| \le\frac{1}{2}|b-u_i|. ∣ b ± − b ∣ ≤ m λ K 0 ∣ b − u i ∣ ≤ 2 1 ∣ b − u i ∣. The reverse triangle inequality, followed by division by 1 + ∣ u i ∣ 1+|u_i| 1 + ∣ u i ∣ (26) .
We choose the sign in (23) for y y y ∣ y ∣ ≤ 2 |y|\le2 ∣ y ∣ ≤ 2 1 + ∣ y ∣ ≤ 3 1+|y|\le3 1 + ∣ y ∣ ≤ 3
∣ b ± − y ∣ 1 + ∣ y ∣ ≥ λ 3 M min { ∣ H ( b ) ∣ , t } . \frac{|b_{\pm}-y|}{1+|y|}\ge\frac{\lambda}{3M}\min\{|H(b)|,t\}. 1 + ∣ y ∣ ∣ b ± − y ∣ ≥ 3 M λ min { ∣ H ( b ) ∣ , t } . If ∣ y ∣ > 2 |y|>2 ∣ y ∣ > 2 ∣ b ± ∣ < 1 / 2 |b_{\pm}|<1/2 ∣ b ± ∣ < 1/2
∣ b ± − y ∣ 1 + ∣ y ∣ ≥ ∣ y ∣ − 1 / 2 1 + ∣ y ∣ > 1 2 . \frac{|b_{\pm}-y|}{1+|y|}\ge\frac{|y|-1/2}{1+|y|}>\frac{1}{2}. 1 + ∣ y ∣ ∣ b ± − y ∣ ≥ 1 + ∣ y ∣ ∣ y ∣ − 1/2 > 2 1 . The right-hand side is at least 1 2 min { ∣ H ( b ) ∣ , t } \frac{1}{2}\min\{|H(b)|,t\} 2 1 min { ∣ H ( b ) ∣ , t } t < 1 t<1 t < 1 (27) . The last assertion follows from (25) and the upper bound in (22) .
Lemma 6.5 (Lower bound for the product). Let 0 < c ≤ 1 0<c\le1 0 < c ≤ 1 0 < t < 1 0<t<1 0 < t < 1
∣ b − u i ∣ 1 + ∣ u i ∣ ≥ c t e i for all nodes present , \frac{|b-u_i|}{1+|u_i|}\ge ct^{e_i}\qquad\text{for all nodes present}, 1 + ∣ u i ∣ ∣ b − u i ∣ ≥ c t e i for all nodes present , and E = ∑ i μ i e i E=\sum_i\mu_i e_i E = ∑ i μ i e i
∣ H ( b ) ∣ ≥ p − c d t E , min { ∣ H ( b ) ∣ , t } ≥ min { p − c d , 1 } t max { 1 , E } . (28) |H(b)|\ge p^{-c^d t^E},\qquad\min\{|H(b)|,t\}\ge\min\{p^{-c^d},1\}t^{\max\{1,E\}}. \tag*{(28)} ∣ H ( b ) ∣ ≥ p − c d t E , min { ∣ H ( b ) ∣ , t } ≥ min { p − c d , 1 } t m a x { 1 , E } . (28) The assertion includes the empty list, for which E = 0 E=0 E = 0
Proof. By the product and ∑ i μ i ≤ d \sum_i\mu_i\le d ∑ i μ i ≤ d
∣ H ( b ) ∣ = ∣ P ( b ) ∣ ∏ i ( ∣ b − u i ∣ 1 + ∣ u i ∣ ) μ i ≥ p − c ∑ i μ i t E ≥ p − c d t E . |H(b)|=|P(b)|\prod_i\left(\frac{|b-u_i|}{1+|u_i|}\right)^{\mu_i}\ge p^{-c\sum_i\mu_i t^E}\ge p^{-c^d t^E}. ∣ H ( b ) ∣ = ∣ P ( b ) ∣ i ∏ ( 1 + ∣ u i ∣ ∣ b − u i ∣ ) μ i ≥ p − c ∑ i μ i t E ≥ p − c d t E . If E ≥ 1 E\ge1 E ≥ 1 p − c d t E p^{-c^d t^E} p − c d t E t t t min { p − c d , 1 } t E \min\{p^{-c^d},1\}t^E min { p − c d , 1 } t E E = 0 E=0 E = 0 p − c d p^{-c^d} p − c d t t t min { p − c d , 1 } t \min\{p^{-c^d},1\}t min { p − c d , 1 } t
Finite stage for arbitrary paired queries
Proposition 7.1 (Constants fixed before the scale). Let T T T f f f f ′ f' f ′ N F ≥ 1 N_F\ge1 N F ≥ 1 N J ≥ 0 N_J\ge0 N J ≥ 0 d = N F + N J d=N_F+N_J d = N F + N J B = B ( N F , N J ) B=B(N_F,N_J) B = B ( N F , N J ) f , P ∈ R [ z ] f,P\in\mathbb{R}[z] f , P ∈ R [ z ] a ∈ ( − 1 / 2 , 1 / 2 ) a\in(-1/2,1/2) a ∈ ( − 1/2 , 1/2 )
f ( a ) = 0 , f ′ ( a ) > 0 , P ( a ) ≠ 0. f(a)=0,\qquad f'(a)>0,\qquad P(a)\ne0. f ( a ) = 0 , f ′ ( a ) > 0 , P ( a ) = 0. For each R ≥ 3 R\ge3 R ≥ 3 ε > 0 \varepsilon>0 ε > 0 c , τ > 0 c,\tau>0 c , τ > 0 t t t 0 < t < τ 0<t<\tau 0 < t < τ x = a + t x=a+t x = a + t g g g b b b
∥ g − f ∥ R < ε , P ∣ ( g − f ) , deg ( g − f ) ≤ deg P + d , (29) \|g-f\|_R<\varepsilon,\qquad P\mid(g-f),\qquad\deg(g-f)\le\deg P+d, \tag*{(29)} ∥ g − f ∥ R < ε , P ∣ ( g − f ) , deg ( g − f ) ≤ deg P + d , (29) ∣ b − a ∣ < t / 8 , ∣ T g ( x ) − b ∣ ≥ c t B . (30) |b-a|<t/8,\qquad|T_g(x)-b|\ge ct^B. \tag*{(30)} ∣ b − a ∣ < t /8 , ∣ T g ( x ) − b ∣ ≥ c t B . (30) Moreover, P ( b ) ≠ 0 P(b)\ne0 P ( b ) = 0 b b b f f f P P P a a a R R R ε \varepsilon ε N F N_F N F N J N_J N J
Proof. We apply Lemma 6.2 and fix I , r , δ , m , M I,r,\delta,m,M I , r , δ , m , M p − , K 0 , K R p_{-},K_{0},K_{R} p − , K 0 , K R § 6 , with the integer d d d
0 < λ ≤ min { 1 , m 8 K 0 , m 32 ( d + 1 ) , δ 4 ( d + 1 ) K R } , 0 < τ < min { 1 / 4 , r / 2 } . (31) 0<\lambda\le\min\left\{1,\frac{m}{8K_{0}},\frac{m}{32(d+1)},\frac{\delta}{4(d+1)K_{R}}\right\},\qquad0<\tau<\min\{1/4,r/2\}. \tag*{(31)} 0 < λ ≤ min { 1 , 8 K 0 m , 32 ( d + 1 ) m , 4 ( d + 1 ) K R δ } , 0 < τ < min { 1/4 , r /2 } . (31) These choices precede t t t
Define κ = min { λ / ( 3 M ) , 1 / 2 } \kappa=\min\{\lambda/(3M),1/2\} κ = min { λ / ( 3 M ) , 1/2 } c 0 = 1 c_{0}=1 c 0 = 1 0 ≤ j ≤ d 0\le j\le d 0 ≤ j ≤ d
c j + 1 = min { c j 2 , κ min { p − c j d , 1 } } . (32) c_{j+1}=\min\left\{\frac{c_{j}}{2},\kappa\min\{p_{-}c_{j}^{d},1\}\right\}. \tag*{(32)} c j + 1 = min { 2 c j , κ min { p − c j d , 1 } } . (32) All these numbers are positive, no greater than one, and nonincreasing. Let c ∗ = c d + 1 c_{*}=c_{d+1} c ∗ = c d + 1
c = min { 1 8 , λ M min { p − c ∗ d , 1 } } > 0. (33) c=\min\left\{\frac{1}{8},\frac{\lambda}{M}\min\{p_{-}c_{*}^{d},1\}\right\}>0. \tag*{(33)} c = min { 8 1 , M λ min { p − c ∗ d , 1 } } > 0. (33) Now fix 0 < t < τ 0<t<\tau 0 < t < τ x = a + t x=a+t x = a + t f f f a a a T T T g 0 g_{0} g 0 b 0 b_{0} b 0 g , b g,b g , b
During the construction, we maintain the following properties. The current polynomial preserves all responses already provided. Its root belongs to I I I P P P j j j
∣ b − u i ∣ 1 + ∣ u i ∣ ≥ c j t ϵ i . (34) \frac{|b-u_{i}|}{1+|u_{i}|}\ge c_{j}t^{\epsilon_{i}}. \tag*{(34)} 1 + ∣ u i ∣ ∣ b − u i ∣ ≥ c j t ϵ i . (34) The multiplicities and integers are updated by (5.1) and (5.2).
Let us first see that all the perturbations we shall use are admissible in the neighborhood of Lemma 6.2. Each modification will have the form g ↦ g ± η H g\mapsto g\pm\eta H g ↦ g ± η H H H H η \eta η
∥ η H ∥ R ≤ λ K R ≤ δ 4 ( d + 1 ) . \lVert\eta H\rVert_{R}\le\lambda K_{R}\le\frac{\delta}{4(d+1)}. ∥ η H ∥ R ≤ λ K R ≤ 4 ( d + 1 ) δ . We shall make at most one modification per new function node and one final modification; thus no more than N F + 1 ≤ d + 1 N_{F}+1\le d+1 N F + 1 ≤ d + 1 δ / 4 < δ \delta/4<\delta δ /4 < δ f f f I I I m , M m,M m , M
Moreover, each root displacement is at most λ t / m \lambda t/m λ t / m
( d + 1 ) λ t m ≤ t 32 < t 8 . (35) (d+1)\frac{\lambda t}{m}\le\frac{t}{32}<\frac{t}{8}. \tag*{(35)} ( d + 1 ) m λ t ≤ 32 t < 8 t . (35) The existence of the candidates was established earlier from the norm bound, not from this estimate; there is no circular dependence.
Consider a method decision from the current history. If it asks for a function query at a node already in the list, we respond with the value of g g g
Suppose it asks for a function query at a new node y y y H H H P ( b ) ≠ 0 P(b)\ne0 P ( b ) = 0 b b b H ( b ) ≠ 0 H(b)\ne0 H ( b ) = 0 η \eta η g ± η H g\pm\eta H g ± η H
Both candidates preserve the history exactly, by Lemma 6.1. Therefore, the method requests the same node y y y
For previous nodes, (26) preserves at least half the separation. For the new node, Lemmas 6.4 and 6.5 give
∣ b n e w − y ∣ 1 + ∣ y ∣ ≥ κ min { p − c j d , 1 } t max { 1 , E } . \frac{\lvert b_{\mathrm{new}}-y\rvert}{1+\lvert y\rvert}\ge\kappa\min\{p-c_j^d,1\}t^{\max\{1,E\}}. 1 + ∣ y ∣ ∣ b new − y ∣ ≥ κ min { p − c j d , 1 } t m a x { 1 , E } . We assign e n e w = max { 1 , E } e_{\mathrm{new}}=\max\{1,E\} e new = max { 1 , E } (32) , (34) holds with j + 1 j+1 j + 1 y y y P P P I I I
Now suppose that the next query is a derivative query. By pairing, its node u i u_i u i g ′ ( u i ) g'(u_i) g ′ ( u i ) e i e_i e i E E E
The budget and totality ensure that this procedure reaches an output q ∈ R q\in\mathbb{R} q ∈ R d d d
We now form H H H g ± η H g\pm\eta H g ± η H q q q b b b
∣ q − b ∣ ≥ λ M min { ∣ H ( b p r e v i o u s ) ∣ , t } . \lvert q-b\rvert\ge\frac{\lambda}{M}\min\{\lvert H(b_{\mathrm{previous}})\rvert,t\}. ∣ q − b ∣ ≥ M λ min {∣ H ( b previous )∣ , t } . Before this modification, all nodes have separation at least c ∗ t e i c_\ast t^{e_i} c ∗ t e i d + 1 d+1 d + 1 c j c_j c j
∣ q − b ∣ ≥ λ M min { p − c ∗ d , 1 } t max { 1 , E } . \lvert q-b\rvert\ge\frac{\lambda}{M}\min\{p-c_\ast^d,1\}t^{\max\{1,E\}}. ∣ q − b ∣ ≥ M λ min { p − c ∗ d , 1 } t m a x { 1 , E } . By Lemma 5.3, max { 1 , E } ≤ B \max\{1,E\}\le B max { 1 , E } ≤ B 0 < t < 1 0<t<1 0 < t < 1 ∣ q − b ∣ ≥ c t B \lvert q-b\rvert\ge ct^B ∣ q − b ∣ ≥ c t B
The final polynomial preserves the output q = T g ( x ) q=T_g(x) q = T g ( x ) P P P deg P + d \deg P+d deg P + d δ ≤ ϵ \delta\le\epsilon δ ≤ ϵ (35) proves the control of the root. Finally, (26) preserves the separation of all nodes through the last modification, and P ( b ) ≠ 0 P(b)\ne0 P ( b ) = 0 b ∈ I b\in I b ∈ I
Remark 7.2 (Absence of regularity of the nodes). The record, its coincidences, and its decisions may vary discontinuously as t t t c , τ c,\tau c , τ e i e_i e i t t t
Remark 7.3 (Order of the choices). The effective amplitude η \eta η t t t 0 < η ≤ λ 0<\eta\le\lambda 0 < η ≤ λ (25) and the second inequality in (28) explicitly show that this reduction in amplitude does not lose the required exponent. The constants λ \lambda λ c j c_j c j c c c τ \tau τ t t t
A single entire function for the refinement
Proposition 7.1 provides a polynomial for each scale. This does not yet rule out a local estimate whose constants depend on the polynomial. We shall now construct a single limit that preserves the outputs of all stages. We use the strategy of exact preservation and successive approximations from [1 ] , with the paired stage just proved.
Successive choice of data
Theorem 8.1 (Paired scalar barrier with a fixed witness). Let T T T N F ≥ 1 N_F \ge1 N F ≥ 1 N J ≥ 0 N_J \ge0 N J ≥ 0 B = B ( N F , N J ) B = B(N_F,N_J) B = B ( N F , N J )
There exist f ∈ E ∗ f \in\mathcal{E}_* f ∈ E ∗ a a a x m > a x_m > a x m > a x m → a x_m \to a x m → a
∣ T f ( x m ) − a ∣ ( x m − a ) p ⟶ + ∞ for each p > B . (36) \frac{\lvert T_f(x_m)-a\rvert}{(x_m-a)^p} \longrightarrow+\infty\qquad\text{for each } p>B. \tag*{(36)} ( x m − a ) p ∣ T f ( x m ) − a ∣ ⟶ + ∞ for each p > B . (36) The function, root, and sequence do not depend on the final exponent.
Proof. We begin with
f 0 ( z ) = z , a 0 = 0 , S 0 = ∅ . f_0(z)=z,\qquad a_0=0,\qquad S_0=\varnothing. f 0 ( z ) = z , a 0 = 0 , S 0 = ∅ . The set S m S_m S m m m m dist ( a , ∅ ) = + ∞ \operatorname{dist}(a,\varnothing)=+\infty dist ( a , ∅ ) = + ∞
Suppose f 0 , … , f m − 1 f_0,\ldots,f_{m-1} f 0 , … , f m − 1 a i a_i a i S i S_i S i h 1 , … , h m − 1 h_1,\ldots,h_{m-1} h 1 , … , h m − 1
R m = m + 3 , ε m = 2 − m − 10 min { 1 , h 1 , … , h m − 1 } , (37) R_m=m+3,\qquad\varepsilon_m=2^{-m-10}\min\{1,h_1,\ldots,h_{m-1}\}, \tag*{(37)} R m = m + 3 , ε m = 2 − m − 10 min { 1 , h 1 , … , h m − 1 } , (37) where for m = 1 m=1 m = 1
P m − 1 ( z ) = ∏ u ∈ S m − 1 ( z − u ) 2 . (38) P_{m-1}(z)=\prod_{u\in S_{m-1}}(z-u)^2. \tag*{(38)} P m − 1 ( z ) = u ∈ S m − 1 ∏ ( z − u ) 2 . (38) We shall verify that P m − 1 ( a m − 1 ) ≠ 0 P_{m-1}(a_{m-1})\ne0 P m − 1 ( a m − 1 ) = 0 f m − 1 ′ ( a m − 1 ) > 0 f'_{m-1}(a_{m-1})>0 f m − 1 ′ ( a m − 1 ) > 0 m = 1 m=1 m = 1
We apply Proposition 7.1 to f m − 1 f_{m-1} f m − 1 P m − 1 P_{m-1} P m − 1 a m − 1 a_{m-1} a m − 1 R m R_m R m ε m \varepsilon_m ε m c m , τ m > 0 c_m,\tau_m>0 c m , τ m > 0 c m ≤ 1 / 8 c_m\le1/8 c m ≤ 1/8
p m = B + 1 m . p_m=B+\frac{1}{m}. p m = B + m 1 . Choose t m > 0 t_m>0 t m > 0
t m < min { τ m , 2 − m , 1 4 , ( c m 2 p m + 1 m ) 1 / ( p m − B ) } . (39) t_m<\min\left\{\tau_m,2^{-m},\frac{1}{4},\left(\frac{c_m}{2^{p_m+1}m}\right)^{1/(p_m-B)}\right\}. \tag*{(39)} t m < min { τ m , 2 − m , 4 1 , ( 2 p m + 1 m c m ) 1/ ( p m − B ) } . (39) The minimum is positive because p m − B = 1 / m > 0 p_m-B=1/m>0 p m − B = 1/ m > 0
c m t m B − p m > 2 p m + 1 m . (40) c_m t_m^{B-p_m}>2^{p_m+1}m. \tag*{(40)} c m t m B − p m > 2 p m + 1 m . (40) Put x m = a m − 1 + t m x_m=a_{m-1}+t_m x m = a m − 1 + t m f m f_m f m a m a_m a m
∥ f m − f m − 1 ∥ R m < ε m , P m − 1 ∣ ( f m − f m − 1 ) , (41) \lVert f_m-f_{m-1}\rVert_{R_m}<\varepsilon_m,\qquad P_{m-1}\mid(f_m-f_{m-1}), \tag*{(41)} ∥ f m − f m − 1 ∥ R m < ε m , P m − 1 ∣ ( f m − f m − 1 ) , (41) ∣ a m − a m − 1 ∣ < t m / 8 , ∣ T f m ( x m ) − a m ∣ ≥ A m , A m = c m t m B > 0. (42) \lvert a_m-a_{m-1}\rvert<t_m/8,\qquad\lvert T_{f_m}(x_m)-a_m\rvert\ge A_m,\qquad A_m=c_m t_m^B>0. \tag*{(42)} ∣ a m − a m − 1 ∣ < t m /8 , ∣ T f m ( x m ) − a m ∣ ≥ A m , A m = c m t m B > 0. (42) The root belongs neither to S m − 1 S_{m-1} S m − 1 S m S_m S m
h m = min { 1 , A m , t m , dist ( a m , S m ) } > 0. (43) h_m=\min\{1,A_m,t_m,\operatorname{dist}(a_m,S_m)\}>0. \tag*{(43)} h m = min { 1 , A m , t m , dist ( a m , S m )} > 0. (43) Let us see that the induction can continue. Since R j ≥ 3 R_j\ge3 R j ≥ 3 ε j ≤ 2 − j − 10 \varepsilon_j\le2^{-j-10} ε j ≤ 2 − j − 10
∥ f m − z ∥ 3 ≤ ∑ j = 1 m ∥ f j − f j − 1 ∥ 3 < ∑ j = 1 m 2 − j − 10 < 2 − 10 . (44) \lVert f_m-z\rVert_3\le\sum_{j=1}^{m}\lVert f_j-f_{j-1}\rVert_3<\sum_{j=1}^{m}2^{-j-10}<2^{-10}. \tag*{(44)} ∥ f m − z ∥ 3 ≤ j = 1 ∑ m ∥ f j − f j − 1 ∥ 3 < j = 1 ∑ m 2 − j − 10 < 2 − 10 . (44) By (15) ,
∣ f m ′ ( u ) − 1 ∣ < 2 − 10 ( − 1 ≤ u ≤ 1 ) . \lvert f_m'(u)-1\rvert< 2^{-10}\qquad(-1\le u\le1). ∣ f m ′ ( u ) − 1 ∣ < 2 − 10 ( − 1 ≤ u ≤ 1 ) . Hence f m ′ > 1 / 2 f_m'>1/2 f m ′ > 1/2 a m a_m a m ( − 1 / 2 , 1 / 2 ) (-1/2,1/2) ( − 1/2 , 1/2 ) f m ( a m ) = 0 f_m(a_m)=0 f m ( a m ) = 0
∣ a m ∣ = ∣ a m − f m ( a m ) ∣ ≤ ∥ f m − z ∥ 3 < 2 − 10 . \lvert a_m\rvert=\lvert a_m-f_m(a_m)\rvert\le\lVert f_m-z\rVert_3<2^{-10}. ∣ a m ∣ = ∣ a m − f m ( a m )∣ ≤ ∥ f m − z ∥ 3 < 2 − 10 . Moreover, a m ∉ S m a_m\notin S_m a m ∈ / S m P m ( a m ) ≠ 0 P_m(a_m)\ne0 P m ( a m ) = 0
Convergence of the polynomials and their roots
Fix a disk ∣ z ∣ ≤ R \lvert z\rvert\le R ∣ z ∣ ≤ R ℓ > m \ell>m ℓ > m R m + 1 ≥ R R_{m+1}\ge R R m + 1 ≥ R
∥ f ℓ − f m ∥ R ≤ ∑ j = m + 1 ℓ ε j ≤ ∑ j > m 2 − j − 10 ⟶ 0. \lVert f_\ell-f_m\rVert_R\le\sum_{j=m+1}^{\ell}\varepsilon_j\le\sum_{j>m}2^{-j-10}\longrightarrow0. ∥ f ℓ − f m ∥ R ≤ j = m + 1 ∑ ℓ ε j ≤ j > m ∑ 2 − j − 10 ⟶ 0. By completeness of the space of continuous functions on each disk, there is a uniform limit there. The limits are compatible when restricted to smaller disks and define a function f f f C \mathbb{C} C
To verify that f f f f m f_m f m f f f f m ( j ) → f ( j ) f_m^{(j)}\to f^{(j)} f m ( j ) → f ( j ) j j j f m f_m f m R \mathbb{R} R f f f f ∈ E R f\in\mathcal{E}_{\mathbb{R}} f ∈ E R
From (44) , we deduce
∥ f − z ∥ 3 ≤ 2 − 10 , f ′ ( u ) ≥ 1 − 2 − 10 > 1 2 ( − 1 ≤ u ≤ 1 ) . \lVert f-z\rVert_3\le2^{-10},\qquad f'(u)\ge1-2^{-10}>\frac{1}{2}\qquad(-1\le u\le1). ∥ f − z ∥ 3 ≤ 2 − 10 , f ′ ( u ) ≥ 1 − 2 − 10 > 2 1 ( − 1 ≤ u ≤ 1 ) . It remains to identify its root and control the distance to previous roots. By the mean value theorem applied to f j f_j f j a j − 1 a_{j-1} a j − 1 a j a_j a j
∣ a j − a j − 1 ∣ ≤ 2 ∣ f j ( a j − 1 ) ∣ = 2 ∣ ( f j − f j − 1 ) ( a j − 1 ) ∣ < 2 ε j . \lvert a_j-a_{j-1}\rvert\le2\lvert f_j(a_{j-1})\rvert=2\lvert(f_j-f_{j-1})(a_{j-1})\rvert<2\varepsilon_j. ∣ a j − a j − 1 ∣ ≤ 2 ∣ f j ( a j − 1 )∣ = 2 ∣( f j − f j − 1 ) ( a j − 1 )∣ < 2 ε j . The roots form a Cauchy sequence. Let a a a m ≥ 1 m\ge1 m ≥ 1
∣ a − a m ∣ ≤ 2 ∑ j > m ε j ≤ 2 ∑ j > m 2 − j − 10 h m = 2 − m − 9 h m < h m 4 . (45) \lvert a-a_m\rvert\le2\sum_{j>m}\varepsilon_j\le2\sum_{j>m}2^{-j-10}h_m=2^{-m-9}h_m<\frac{h_m}{4}. \tag*{(45)} ∣ a − a m ∣ ≤ 2 j > m ∑ ε j ≤ 2 j > m ∑ 2 − j − 10 h m = 2 − m − 9 h m < 4 h m . (45) The limit satisfies ∣ a ∣ ≤ 2 − 10 < 1 / 2 \lvert a\rvert\le2^{-10}<1/2 ∣ a ∣ ≤ 2 − 10 < 1/2 f f f f m f_m f m [ − 1 , 1 ] [-1,1] [ − 1 , 1 ] f ( a ) = 0 f(a)=0 f ( a ) = 0 f ′ > 1 / 2 f'>1/2 f ′ > 1/2 f ∈ E ∗ f\in\mathcal{E}_* f ∈ E ∗
Exact preservation of the records
Fix a stage m m m u u u j > m j>m j > m P j − 1 P_{j-1} P j − 1 ( z − u ) 2 (z-u)^2 ( z − u ) 2 (41) ,
f j ( u ) = f j − 1 ( u ) , f j ′ ( u ) = f j − 1 ′ ( u ) . f_j(u)=f_{j-1}(u),\qquad f_j'(u)=f_{j-1}'(u). f j ( u ) = f j − 1 ( u ) , f j ′ ( u ) = f j − 1 ′ ( u ) . Iterating and passing to the limit,
f ( u ) = f m ( u ) , f ′ ( u ) = f m ′ ( u ) . (46) f(u)=f_m(u),\qquad f'(u)=f_m'(u). \tag*{(46)} f ( u ) = f m ( u ) , f ′ ( u ) = f m ′ ( u ) . (46) For the passage to the limit, it suffices to choose a disk containing that fixed node, even if the nodes of different stages do not remain in a bounded set.
Lemma 2.6, applied to the finite record at stage m m m
T f ( x m ) = T f m ( x m ) . (47) T_f(x_m)=T_{f_m}(x_m). \tag*{(47)} T f ( x m ) = T f m ( x m ) . (47) This equality follows from (46) , not from continuity of the rules. The limiting root also belongs to none of the S m S_m S m (45) and (43) give
dist ( a , S m ) ≥ dist ( a m , S m ) − ∣ a − a m ∣ > 0. \operatorname{dist}(a,S_m)\ge\operatorname{dist}(a_m,S_m)-\lvert a-a_m\rvert>0. dist ( a , S m ) ≥ dist ( a m , S m ) − ∣ a − a m ∣ > 0. Error estimate and simultaneity of the exponents
By (42) , (45) , and (47) ,
∣ T f ( x m ) − a ∣ ≥ ∣ T f m ( x m ) − a m ∣ − ∣ a m − a ∣ > A m − A m 4 ≥ A m 2 . \lvert T_f(x_m)-a\rvert\ge\lvert T_{f_m}(x_m)-a_m\rvert-\lvert a_m-a\rvert>A_m-\frac{A_m}{4}\ge\frac{A_m}{2}. ∣ T f ( x m ) − a ∣ ≥ ∣ T f m ( x m ) − a m ∣ − ∣ a m − a ∣ > A m − 4 A m ≥ 2 A m . Moreover,
x m − a = t m + ( a m − 1 − a m ) + ( a m − a ) . x_m-a=t_m+(a_{m-1}-a_m)+(a_m-a). x m − a = t m + ( a m − 1 − a m ) + ( a m − a ) . The last two differences have absolute values smaller than t m / 8 t_m/8 t m /8 t m / 4 t_m/4 t m /4
5 8 t m < x m − a < 11 8 t m < 2 t m . (48) \frac{5}{8}t_m<x_m-a<\frac{11}{8}t_m<2t_m. \tag*{(48)} 8 5 t m < x m − a < 8 11 t m < 2 t m . (48) In particular, x m > a x_m>a x m > a x m → a x_m\to a x m → a
Applying (40) ,
∣ T f ( x m ) − a ∣ ( x m − a ) p m ≥ c m t m B 2 ( 2 t m ) p m = c m 2 p m + 1 t m B − p m > m . \frac{\lvert T_f(x_m)-a\rvert}{(x_m-a)^{p_m}}\ge\frac{c_m t_m^B}{2(2t_m)^{p_m}}=\frac{c_m}{2^{p_m+1}}t_m^{B-p_m}>m. ( x m − a ) p m ∣ T f ( x m ) − a ∣ ≥ 2 ( 2 t m ) p m c m t m B = 2 p m + 1 c m t m B − p m > m . Now fix any p > B p>B p > B m m m p m ≤ p p_m\le p p m ≤ p 0 < x m − a < 1 0<x_m-a<1 0 < x m − a < 1
∣ T f ( x m ) − a ∣ ( x m − a ) p ≥ ∣ T f ( x m ) − a ∣ ( x m − a ) p m > m . \frac{\lvert T_f(x_m)-a\rvert}{(x_m-a)^p}\ge\frac{\lvert T_f(x_m)-a\rvert}{(x_m-a)^{p_m}}>m. ( x m − a ) p ∣ T f ( x m ) − a ∣ ≥ ( x m − a ) p m ∣ T f ( x m ) − a ∣ > m . This proves (36) . All objects in the construction were chosen before fixing p p p
Remark 8.2 (Preserving more responses between stages). The factor (38) preserves both the value and the first derivative at every node from previous stages, even where only the value had been queried. This does not increase the method’s budget. It is an additional condition imposed on the perturbations between stages. Its degree may grow with m m m c m c_m c m τ m \tau_m τ m t m t_m t m B B B
Vector refinement without rationality assumptions
Theorem 9.1 (Paired barrier for arbitrary rules). Let n ≥ 1 n\ge1 n ≥ 1 N F ≥ 1 N_F\ge1 N F ≥ 1 N J ≥ 0 N_J\ge0 N J ≥ 0 M \mathcal{M} M ( N F , N J ) (N_F,N_J) ( N F , N J ) H n ( I 0 ) \mathcal{H}_n(I_0) H n ( I 0 )
Then there exist a fixed field G f G_f G f f ∈ E ∗ f\in\mathcal{E}_* f ∈ E ∗ α \alpha α X m → α X_m\to\alpha X m → α m m m
∥ M G f ( X m ) − α ∥ ∞ ∥ X m − α ∥ ∞ p ⟶ + ∞ for every p > B ( N F , N J ) . (49) \frac{\lVert\mathcal{M}_{G_f}(X_m)-\alpha\rVert_\infty}{\lVert X_m-\alpha\rVert_\infty^p}\longrightarrow+\infty
\qquad\text{for every }p>B(N_F,N_J). \tag*{(49)} ∥ X m − α ∥ ∞ p ∥ M G f ( X m ) − α ∥ ∞ ⟶ + ∞ for every p > B ( N F , N J ) . (49) In particular, if M \mathcal{M} M p > 1 p > 1 p > 1 H n ( I 0 ) \mathcal{H}_n(I_0) H n ( I 0 )
p ≤ B ( N F , N J ) . (50) p \le B(N_F,N_J). \tag*{(50)} p ≤ B ( N F , N J ) . (50) The first node is not prescribed; a start with F ( x ) F(x) F ( x ) D F ( x ) DF(x) D F ( x )
Proof. By Lemma 5.2 , the original rules admit a truncated total extension with paired records. Theorem 3.2 produces a total scalar method with the same counters. Each query to f ′ f' f ′ f f f
We apply Theorem 8.1 . We obtain f ∈ E ∗ f \in\mathcal{E}_* f ∈ E ∗ a = a f a = a_f a = a f x m > a x_m > a x m > a x m → a x_m \to a x m → a B ( N F , N J ) B(N_F,N_J) B ( N F , N J )
α = ι ( a ) , X m = ι ( x m ) . \alpha= \iota(a), \qquad X_m = \iota(x_m). α = ι ( a ) , X m = ι ( x m ) . For all sufficiently large m m m
( M G f ( X m ) ) 1 = T f ( x m ) . (\mathcal{M}_{G_f}(X_m))_1 = T_f(x_m). ( M G f ( X m ) ) 1 = T f ( x m ) . If I 0 = ( − 1 , 1 ) I_0 = (-1,1) I 0 = ( − 1 , 1 ) Theorem 4.2 : every node of the valid original execution is in the domain and the responses coincide there.
Finally,
∥ X m − α ∥ ∞ = x m − a , ∥ M G f ( X m ) − α ∥ ∞ ≥ ∣ T f ( x m ) − a ∣ . \lVert X_m-\alpha\rVert_\infty= x_m-a, \qquad\lVert\mathcal{M}_{G_f}(X_m)-\alpha\rVert_\infty\ge\lvert T_f(x_m)-a\rvert. ∥ X m − α ∥ ∞ = x m − a , ∥ M G f ( X m ) − α ∥ ∞ ≥ ∣ T f ( x m ) − a ∣ . Scalar divergence implies (49) . If a universal order greater than B B B
Corollary 9.2 (Refinement of the Cordero–Torregrosa bound). Under the hypotheses of Theorem 9.1 , if 1 ≤ N J ≤ N F 1 \le N_J \le N_F 1 ≤ N J ≤ N F
p ≤ 2 N F − N J + 1 3 N J − 1 = 2 N F + N J − 1 ( 3 4 ) N J − 1 . (51) p \le2^{N_F-N_J+1}3^{N_J-1}=2^{N_F+N_J-1}\left(\frac{3}{4}\right)^{N_J-1}. \tag*{(51)} p ≤ 2 N F − N J + 1 3 N J − 1 = 2 N F + N J − 1 ( 4 3 ) N J − 1 . (51) The improvement is strict when N J > 1 N_J > 1 N J > 1
Proof. In this range, s = min { N F , N J } = N J s = \min\{N_F,N_J\} = N_J s = min { N F , N J } = N J (13) and factor. If N J > 1 N_J > 1 N J > 1 ( 3 / 4 ) N J − 1 < 1 (3/4)^{N_J-1} < 1 ( 3/4 ) N J − 1 < 1
Corollary 9.3 (Budgets with repeated derivatives). If N J ≥ N F ≥ 1 N_J \ge N_F \ge1 N J ≥ N F ≥ 1
p ≤ 2 3 N F − 1 . p \le2\,3^{N_F-1}. p ≤ 2 3 N F − 1 . Proof. There are at most N F N_F N F s = N F s = N_F s = N F (13) , and the expression is 2 3 N F − 1 2\,3^{N_F-1} 2 3 N F − 1
Remark 9.4 (Analytic classes and larger differentiable classes). Theorems 4.2 and 9.1 produce fields that extend to entire fields. Hence their obstructions are valid for the class of all real-analytic fields with a simple root. If the same method claims a common order on a C r C^r C r C ∞ C^\infty C ∞
Remark 9.5 (An error exponent need not be an integer). The definition of order admits any real p > 1 p > 1 p > 1 e i e_i e i E E E t B − p → + ∞ t^{B-p} \to+\infty t B − p → + ∞ p > B p > B p > B p p p
Independent consequences without Jacobian queries
Corollary 9.6 (Methods that query function values only). Let N F ≥ 1 N_F \ge1 N F ≥ 1 T T T N F N_F N F E ∗ \mathcal{E}_* E ∗ I 0 I_0 I 0 f ∈ E ∗ f \in\mathcal{E}_* f ∈ E ∗ a a a x m > a x_m > a x m > a x m → a x_m \to a x m → a
∣ T f ( x m ) − a ∣ ( x m − a ) p ⟶ + ∞ for every p > 2 N F − 1 . \frac{|T_f(x_m)-a|}{(x_m-a)^p} \longrightarrow+\infty\qquad\text{for every } p > 2^{N_F-1}. ( x m − a ) p ∣ T f ( x m ) − a ∣ ⟶ + ∞ for every p > 2 N F − 1 . In particular, no universal local order greater than 2 N F − 1 2^{N_F-1} 2 N F − 1
Proof. Every record containing only values trivially satisfies the pairing condition. We take n = 1 n=1 n = 1 N J = 0 N_J=0 N J = 0 Theorem 9.1 . Since s = min { N F , 0 } = 0 s=\min\{N_F,0\}=0 s = min { N F , 0 } = 0 B ( N F , 0 ) = 2 N F − 1 B(N_F,0)=2^{N_F-1} B ( N F , 0 ) = 2 N F − 1 Theorem 4.1 : it follows from the finite stage and the entire-function construction in § 7 and § 8 . □
Corollary 9.7 (Vector barrier without Jacobian queries). Let N F ≥ 1 N_F \ge1 N F ≥ 1 M \mathcal{M} M ( N F , 0 ) (N_F,0) ( N F , 0 ) H n ( I 0 ) \mathcal{H}_n(I_0) H n ( I 0 ) 2 N F − 1 2^{N_F-1} 2 N F − 1 In particular, if the method guarantees universal local order p > 1 p>1 p > 1
p ≤ 2 N F − 1 . p \le2^{N_F-1}. p ≤ 2 N F − 1 . Proof. There are no Jacobian queries, so all records satisfy the pairing condition. We directly apply Theorem 9.1 with N J = 0 N_J=0 N J = 0 B ( N F , 0 ) = 2 N F − 1 B(N_F,0)=2^{N_F-1} B ( N F , 0 ) = 2 N F − 1 § 8 ; Theorem 4.1 is not required. □
The case N J = 0 N_J=0 N J = 0 3 N J − 1 3^{N_J-1} 3 N J − 1 (13) . On the other hand, when N J ≥ N F N_J \ge N_F N J ≥ N F
Pairing on the test fields
Definition 9.8 (Pairing in the first coordinate). We say that M \mathcal{M} M H n ( I 0 ) \mathcal{H}_n(I_0) H n ( I 0 ) ( 1 , Y ) (1,Y) ( 1 , Y ) ( 0 , Y ′ ) (0,Y') ( 0 , Y ′ ) Y 1 ′ = Y 1 Y'_1=Y_1 Y 1 ′ = Y 1
Proposition 9.9 (Refinement under projected pairing). Let N F ≥ 1 N_F \ge1 N F ≥ 1 N J ≥ 0 N_J \ge0 N J ≥ 0 M \mathcal{M} M ( N F , N J ) (N_F,N_J) ( N F , N J ) H n ( I 0 ) \mathcal{H}_n(I_0) H n ( I 0 ) Definition 9.8 holds, then the obstruction (9.1) and bound (9.2) of Theorem 9.1 remain valid.
Proof. We construct the truncated extension from Lemma 3.1. Before preserving a Jacobian query ( 1 , Y ) (1,Y) ( 1 , Y ) ( 0 , Y ′ ) (0,Y') ( 0 , Y ′ ) Y 1 ′ = Y 1 Y'_1=Y_1 Y 1 ′ = Y 1
Let us see that it preserves the original executions specified in the statement. At every prefix of such an execution, the original rule is defined, the next query respects the budget, and, if it is a Jacobian query, there is a preceding function value with the same first coordinate. Therefore, no substitution by the zero output is activated. Induction preserves all queries, their responses, and the output.
We now apply Theorem 3.2 to the extension. Each query of D G f ( Y ) DG_f(Y) D G f ( Y ) f ′ ( Y 1 ) f'(Y_1) f ′ ( Y 1 ) G f ( Y ′ ) G_f(Y') G f ( Y ′ ) Y 1 ′ = Y 1 Y'_1=Y_1 Y 1 ′ = Y 1 f ( Y 1 ) f(Y_1) f ( Y 1 ) f ∈ E ∗ f \in\mathcal{E}_* f ∈ E ∗ a a a s m > a s_m>a s m > a s m → a s_m\to a s m → a B ( N F , N J ) B(N_F,N_J) B ( N F , N J )
If I 0 = ( − 1 , 1 ) I_0=(-1,1) I 0 = ( − 1 , 1 )
For this fixed problem, the points ι ( s m ) \iota(s_m) ι ( s m ) T f ( s m ) T_f(s_m) T f ( s m )
∥ ι ( s m ) − ι ( a ) ∥ ∞ = s m − a , ∥ M G f ( ι ( s m ) ) − ι ( a ) ∥ ∞ ≥ ∣ T f ( s m ) − a ∣ \lVert\iota(s_m)-\iota(a)\rVert_\infty=s_m-a,\qquad
\lVert\mathcal{M}_{G_f}(\iota(s_m))-\iota(a)\rVert_\infty\geq\lvert T_f(s_m)-a\rvert ∥ ι ( s m ) − ι ( a ) ∥ ∞ = s m − a , ∥ M G f ( ι ( s m )) − ι ( a ) ∥ ∞ ≥ ∣ T f ( s m ) − a ∣ we obtain (9.1). A universal estimate with a higher exponent contradicts this divergence, proving (9.2).
Remark 9.10 (Difference between the two pairing conditions). Equality of complete vector nodes implies equality of their first coordinates, but the converse is false. For example, for n ≥ 2 n\geq2 n ≥ 2 Y Y Y Y + e 2 Y+e_2 Y + e 2 G f G_f G f G f ( Y ) G_f(Y) G f ( Y ) D G f ( Y + e 2 ) DG_f(Y+e_2) D G f ( Y + e 2 ) f ( Y 1 ) f(Y_1) f ( Y 1 ) f ′ ( Y 1 ) f'(Y_1) f ′ ( Y 1 )
The proposition concerns the projection and the diagonal family fixed for the proof. It does not assert that F ( Y ) F(Y) F ( Y ) F ( Y ′ ) F(Y') F ( Y ′ )
Effective budget and reuse of responses
The diagonal reduction also makes it possible to retain the distinction between requests made and information actually needed. This question is different from improving the barrier by pairing.
Proposition 10.1 (Simulation with exact reuse). Consider a vector method already truncated to a finite number d d d ( τ , Y 1 ) (\tau,Y_1) ( τ , Y 1 )
Proof. When a key appears for the first time, we request f ( τ ) ( Y 1 ) f^{(\tau)}(Y_1) f ( τ ) ( Y 1 )
Each reconstructed response is exactly the one that simulation without reuse would obtain. By induction, the same decisions are followed and the same output is reached. Between two new scalar queries, several already known vector requests may be replayed, but no more than d d d
Corollary 10.2 (Bound by number of distinct keys). Let M \mathcal{M} M ( N F , N J ) (N_{\mathrm{F}},N_{\mathrm{J}}) ( N F , N J ) H n ( I 0 ) \mathcal{H}_n(I_0) H n ( I 0 ) d = N F + N J ≥ 1 d=N_{\mathrm{F}}+N_{\mathrm{J}}\ge1 d = N F + N J ≥ 1 d e f ≥ 1 d_{\mathrm{ef}}\ge1 d ef ≥ 1 d e f d_{\mathrm{ef}} d ef ( τ , Y 1 ) (\tau,Y_1) ( τ , Y 1 ) p > 1 p>1 p > 1 H n ( I 0 ) \mathcal{H}_n(I_0) H n ( I 0 )
p ≤ 2 d e f − 1 . p \le2^{d_{\mathrm{ef}}-1}. p ≤ 2 d ef − 1 . Proof. We first apply Lemma 3.1 to the vector method and obtain M ^ \widehat{\mathcal{M}} M d d d
Let us see that the simulation with reuse in Proposition 10.1 defines rules on scalar data. Fix s s s k k k η 1 , … , η k \eta_1,\ldots,\eta_k η 1 , … , η k ι ( s ) \iota(s) ι ( s ) M ^ \widehat{\mathcal{M}} M (6) . When a key is repeated, we use its stored response without consuming a new scalar entry.
Once the k k k ( τ , u ) (\tau,u) ( τ , u ) f ( τ ) ( u ) f^{(\tau)}(u) f ( τ ) ( u ) k k k d d d ( s , η 1 , … , η k ) (s,\eta_1,\ldots,\eta_k) ( s , η 1 , … , η k ) f f f
Denote the scalar method so defined by T ′ T' T ′ Proposition 10.1 proves that its output coincides with the first component of the output of M ^ \widehat{\mathcal{M}} M I 0 I_0 I 0
Fix f ∈ E ∗ f\in\mathcal{E}_* f ∈ E ∗ T ′ T' T ′ d e f d_{\mathrm{ef}} d ef
We construct an extension T ^ \widehat{T} T k < d e f k<d_{\mathrm{ef}} k < d ef T ′ T' T ′ d e f d_{\mathrm{ef}} d ef Lemma 3.1 with a single total counter: we do not require all queries to be function queries or forbid derivatives. Induction on the record preserves the local executions of T ′ T' T ′ d e f d_{\mathrm{ef}} d ef
We apply Theorem 4.1 to T ^ \widehat{T} T f ∈ E ∗ f\in\mathcal{E}_* f ∈ E ∗ a a a s m > a s_m>a s m > a s m → a s_m\to a s m → a
∣ T ^ f ′ ( s m ) − a ∣ ( s m − a ) p ⟶ + ∞ \frac{\left|\widehat{T}'_f(s_m)-a\right|}{(s_m-a)^p}\longrightarrow+\infty ( s m − a ) p T f ′ ( s m ) − a ⟶ + ∞ for every p > 2 d e f − 1 p>2^{d_{\mathrm{ef}}-1} p > 2 d ef − 1
For this fixed problem, the points ι ( s m ) \iota(s_m) ι ( s m ) m m m
T ^ f ′ ( s m ) = T f ′ ( s m ) = ( M G f ( ι ( s m ) ) ) 1 . \widehat{T}'_f(s_m)=T'_f(s_m)=\left(\mathcal{M}G_f(\iota(s_m))\right)_1. T f ′ ( s m ) = T f ′ ( s m ) = ( M G f ( ι ( s m )) ) 1 . The universal local estimate would give
∣ T ^ f ( s m ) − a ∣ ≤ ∥ M G f ( ι ( s m ) ) − ι ( a ) ∥ ∞ ≤ C G f , a ( s m − a ) p \left|\widehat{T}_f(s_m)-a\right| \le\left\|M_{G_f}(\iota(s_m))-\iota(a)\right\|_\infty\le C_{G_f,a}(s_m-a)^p T f ( s m ) − a ≤ M G f ( ι ( s m )) − ι ( a ) ∞ ≤ C G f , a ( s m − a ) p for all these indices. If p > 2 d e f − 1 p>2^{d_{\mathrm{ef}}-1} p > 2 d ef − 1
Example 10.3. Consider a Newton cycle that requests F ( x ) F(x) F ( x ) D F ( x ) DF(x) D F ( x ) x − D F ( x ) − 1 F ( x ) x-DF(x)^{-1}F(x) x − D F ( x ) − 1 F ( x ) ( 2 , 1 ) (2,1) ( 2 , 1 )
Example 10.4 (Distinct nodes with the same projected information). Let n ≥ 2 n\ge2 n ≥ 2 e 2 e_2 e 2 x x x V = F ( x ) V=F(x) V = F ( x )
h = ∑ i = 1 n V i 2 , Y = x + h e 2 , h=\sum_{i=1}^{n}V_i^2,\qquad Y=x+he_2, h = i = 1 ∑ n V i 2 , Y = x + h e 2 , and query W = F ( Y ) W=F(Y) W = F ( Y ) A = D F ( x ) A=DF(x) A = D F ( x ) A A A
M F ( x ) = x − A − 1 V + W − V − h A e 2 . (52) \mathcal{M}_F(x)=x-A^{-1}V+W-V-hAe_2. \tag*{(52)} M F ( x ) = x − A − 1 V + W − V − h A e 2 . (52) The nominal budget is ( 2 , 1 ) (2,1) ( 2 , 1 ) x x x F ( x ) ≠ 0 F(x)\ne0 F ( x ) = 0 h > 0 h>0 h > 0 Y ≠ x Y\ne x Y = x
Suppose F F F C 2 C^2 C 2 α \alpha α V = O ( ∥ x − α ∥ ∞ ) V=O(\lVert x-\alpha\rVert_\infty) V = O (∥ x − α ∥ ∞ ) h = O ( ∥ x − α ∥ ∞ 2 ) h=O(\lVert x-\alpha\rVert_\infty^2) h = O (∥ x − α ∥ ∞ 2 ) Y Y Y x x x D F ( x ) DF(x) D F ( x )
W − V − h A e 2 = ∫ 0 1 ( D F ( x + s h e 2 ) − D F ( x ) ) h e 2 d s = O ( h 2 ) = O ( ∥ x − α ∥ ∞ 4 ) . W-V-hAe_2=\int_0^1\left(DF(x+she_2)-DF(x)\right)he_2\,\mathrm{d}s=O(h^2)=O(\lVert x-\alpha\rVert_\infty^4). W − V − h A e 2 = ∫ 0 1 ( D F ( x + s h e 2 ) − D F ( x ) ) h e 2 d s = O ( h 2 ) = O (∥ x − α ∥ ∞ 4 ) . Moreover, writing e = x − α e=x-\alpha e = x − α
F ( x ) − D F ( x ) e = ∫ 0 1 ( D F ( α + s e ) − D F ( x ) ) e d s = O ( ∥ e ∥ ∞ 2 ) . F(x)-DF(x)e=\int_0^1\left(DF(\alpha+se)-DF(x)\right)e\,\mathrm{d}s=O(\lVert e\rVert_\infty^2). F ( x ) − D F ( x ) e = ∫ 0 1 ( D F ( α + se ) − D F ( x ) ) e d s = O (∥ e ∥ ∞ 2 ) . Multiplying by D F ( x ) − 1 DF(x)^{-1} D F ( x ) − 1 x − D F ( x ) − 1 F ( x ) − α = O ( ∥ e ∥ ∞ 2 ) x-DF(x)^{-1}F(x)-\alpha=O(\lVert e\rVert_\infty^2) x − D F ( x ) − 1 F ( x ) − α = O (∥ e ∥ ∞ 2 ) (52) , the procedure has local order at least two on these problems.
Let us now see what information it requires on the diagonal family. Since Y 1 = x 1 Y_1=x_1 Y 1 = x 1
G f ( Y ) = G f ( x ) + h e 2 , D G f ( x ) e 2 = e 2 . G_f(Y)=G_f(x)+he_2,\qquad DG_f(x)e_2=e_2. G f ( Y ) = G f ( x ) + h e 2 , D G f ( x ) e 2 = e 2 . Therefore, the last correction term in (52) is zero and the output coincides with one Newton step. The three requests project to the keys
( 0 , x 1 ) , ( 0 , x 1 ) , ( 1 , x 1 ) . (0,x_1),\qquad(0,x_1),\qquad(1,x_1). ( 0 , x 1 ) , ( 0 , x 1 ) , ( 1 , x 1 ) . The second vector response is not equal to the first: its second component has increased by h h h Y Y Y H n ( I 0 ) \mathcal{H}_n(I_0) H n ( I 0 ) ( 2 , 1 ) (2,1) ( 2 , 1 )
For f ( s ) = s + s 2 f(s)=s+s^2 f ( s ) = s + s 2 x = ι ( t ) x=\iota(t) x = ι ( t ) t 2 / ( 1 + 2 t ) t^2/(1+2t) t 2 / ( 1 + 2 t )
A reduction in the budget must be justified uniformly over the local test class. Observing repeated queries in one particular execution does not permit replacing the common budget in a universal theorem.
Scope of the generalization and comparison of bounds
The class of rules is strictly larger
For this comparison, a finite rational program will be a finite instruction tree that forms sums, differences, products, and quotients of available data, makes queries to F F F D F DF D F
Example 11.1 (A discontinuous rule with order at least two). Let χ Q : R → { 0 , 1 } \chi_{\mathbb{Q}}:\mathbb{R}\to\{0,1\} χ Q : R → { 0 , 1 } F ( x ) F(x) F ( x ) D F ( x ) DF(x) D F ( x )
d = D F ( x ) − 1 F ( x ) d=DF(x)^{-1}F(x) d = D F ( x ) − 1 F ( x ) when the matrix is invertible, and returns
M F ( x ) = x − d + χ Q ( x 1 ) ∥ d ∥ 2 d . (53) \mathcal{M}_F(x)=x-d+\chi_{\mathbb{Q}}(x_1)\lVert d\rVert^2d. \tag*{(53)} M F ( x ) = x − d + χ Q ( x 1 ) ∥ d ∥ 2 d . (53) This rule is deterministic, causal, and memoryless. It has budget ( 1 , 1 ) (1,1) ( 1 , 1 ) x 1 x_1 x 1
Let F F F C 2 C^2 C 2 α \alpha α e = x − α e=x-\alpha e = x − α α \alpha α D F ( x ) − 1 DF(x)^{-1} D F ( x ) − 1 F ( x ) = O ( ∥ e ∥ ) F(x)=O(\lVert e\rVert) F ( x ) = O (∥ e ∥) d = O ( ∥ e ∥ ) d=O(\lVert e\rVert) d = O (∥ e ∥)
F ( x ) − D F ( x ) e = ∫ 0 1 ( D F ( α + s e ) − D F ( x ) ) e d s = O ( ∥ e ∥ 2 ) . F(x)-DF(x)e=\int_0^1\bigl(DF(\alpha+se)-DF(x)\bigr)e\,\mathrm{d}s=O(\lVert e\rVert^2). F ( x ) − D F ( x ) e = ∫ 0 1 ( D F ( α + se ) − D F ( x ) ) e d s = O (∥ e ∥ 2 ) . Multiplying by D F ( x ) − 1 DF(x)^{-1} D F ( x ) − 1 x − d − α = O ( ∥ e ∥ 2 ) x-d-\alpha=O(\lVert e\rVert^2) x − d − α = O (∥ e ∥ 2 ) O ( ∥ e ∥ 3 ) O(\lVert e\rVert^3) O (∥ e ∥ 3 ) 0 ≤ χ Q ≤ 1 0\leq\chi_{\mathbb{Q}}\leq1 0 ≤ χ Q ≤ 1
M F ( x ) − α = O ( ∥ x − α ∥ 2 ) . \mathcal{M}_F(x)-\alpha=O(\lVert x-\alpha\rVert^2). M F ( x ) − α = O (∥ x − α ∥ 2 ) . Let us see that this output map cannot be represented on all fields by a finite rational program of the class just defined. Take F ( x ) = x F(x)=x F ( x ) = x x = ι ( t ) x=\iota(t) x = ι ( t ) t > 0 t>0 t > 0 d = ι ( t ) d=\iota(t) d = ι ( t ) χ Q ( t ) t 3 \chi_{\mathbb{Q}}(t)t^3 χ Q ( t ) t 3 t 0 > 0 t_0>0 t 0 > 0 t 0 t_0 t 0 t 0 3 t_0^3 t 0 3
Suppose a finite rational representation exists. On the field F ( x ) = x F(x)=x F ( x ) = x t t t Z Z Z
On every component interval of ( 0 , + ∞ ) ∖ Z (0,+\infty)\setminus Z ( 0 , + ∞ ) ∖ Z
that a single branch is followed and its output is a continuous rational function on that interval. The purported representation is defined there because it must coincide with (11.1). Since there is a nonempty interval outside Z Z Z
Thus, the enlargement of the class of rules is effective. This example does not claim that a noncomputable rule is convenient for numerical computation; it shows that the proof need not exclude it.
Numerical comparison of the theoretical bounds
Table 1 shows several budgets. The numbers are upper bounds; we do not assert that they are attained by vector methods for every budget.
Table 1. General barrier and refinement under causal pairing.
Pairing is a condition on the acquisition of information, not on the reuse of a matrix. Two distinct Jacobian evaluations remain two queries even if an implementation reuses part of a factorization. On the other hand, an action D F ( y ) v DF(y)v D F ( y ) v
Product refinement: formulation and auxiliary results
The paired improvement depends on the information acquired at each node. A different question is to determine whether, for systems of sufficiently large dimension, the distribution of evaluations imposes an even lower barrier. We return to the proposal in [2 ] and specify both its formulation and the auxiliary results supporting it.
Let N F , N J ≥ 1 N_F,N_J \ge1 N F , N J ≥ 1
N F − 1 = q N J + r , q ∈ N 0 , 0 ≤ r < N J , N_F - 1 = qN_J + r,\qquad q \in\mathbb{N}_0,\qquad0 \le r < N_J, N F − 1 = q N J + r , q ∈ N 0 , 0 ≤ r < N J , and define
Π ( N F , N J ) = ( q + 2 ) N J − r ( q + 3 ) r . (54) \Pi(N_F,N_J) = (q+2)^{N_J-r}(q+3)^r. \tag*{(54)} Π ( N F , N J ) = ( q + 2 ) N J − r ( q + 3 ) r . (54) This notation is distinct from B ( N F , N J ) B(N_F,N_J) B ( N F , N J )
Distribution of an integer budget
Lemma 11.2 (Maximum of a product with fixed sum). Let m ∈ N 0 m \in\mathbb{N}_0 m ∈ N 0 j ∈ N j \in\mathbb{N} j ∈ N m = q j + r m=qj+r m = q j + r 0 ≤ r < j 0 \le r < j 0 ≤ r < j
max a 1 , … , a j ∈ N 0 a 1 + ⋯ + a j = m ∏ i = 1 j ( a i + 2 ) = ( q + 2 ) j − r ( q + 3 ) r . (55) \max_{\substack{a_1,\ldots,a_j\in\mathbb{N}_0\\a_1+\cdots+a_j=m}}\prod_{i=1}^{j}(a_i+2)=(q+2)^{j-r}(q+3)^r. \tag*{(55)} a 1 , … , a j ∈ N 0 a 1 + ⋯ + a j = m max i = 1 ∏ j ( a i + 2 ) = ( q + 2 ) j − r ( q + 3 ) r . (55) Moreover,
( q + 2 ) j − r ( q + 3 ) r ≤ 2 m + j , (56) (q+2)^{j-r}(q+3)^r \le2^{m+j}, \tag*{(56)} ( q + 2 ) j − r ( q + 3 ) r ≤ 2 m + j , (56) with equality if and only if m = 0 m=0 m = 0
Proof. The set of distributions is finite and nonempty. Therefore, there is a distribution ( a 1 , … , a j ) (a_1,\ldots,a_j) ( a 1 , … , a j ) a i ≥ a h + 2 a_i\ge a_h+2 a i ≥ a h + 2 ( a i − 1 , a h + 1 ) (a_i-1,a_h+1) ( a i − 1 , a h + 1 )
( a i + 1 ) ( a h + 3 ) − ( a i + 2 ) ( a h + 2 ) = a i − a h − 1 > 0. (a_i+1)(a_h+3)-(a_i+2)(a_h+2)=a_i-a_h-1>0. ( a i + 1 ) ( a h + 3 ) − ( a i + 2 ) ( a h + 2 ) = a i − a h − 1 > 0. The other factors are positive and remain the same. Hence the product increases, contradicting the choice of the distribution.
Let a a a a a a a + 1 a+1 a + 1 k k k a + 1 a+1 a + 1
m = j a + k , 0 ≤ k < j . m=ja+k,\qquad0\le k<j. m = j a + k , 0 ≤ k < j . Uniqueness of integer division gives a = q a=q a = q k = r k=r k = r j − r j-r j − r q q q r r r q + 1 q+1 q + 1 m m m
For every integer a ≥ 0 a\ge0 a ≥ 0 a + 2 ≤ 2 a + 1 a+2\le2^{a+1} a + 2 ≤ 2 a + 1 a = 0 a=0 a = 0 a = 0 a=0 a = 0 a = 1 a=1 a = 1 a ≥ 1 a\ge1 a ≥ 1
a + 3 < 2 ( a + 2 ) ≤ 2 a + 2 . a+3<2(a+2)\le2^{a+2}. a + 3 < 2 ( a + 2 ) ≤ 2 a + 2 . Induction completes the argument. Multiplying over all components of a distribution, we obtain
∏ i = 1 j ( a i + 2 ) ≤ 2 ∑ i = 1 j ( a i + 1 ) = 2 m + j . \prod_{i=1}^{j}(a_i+2)\le2^{\sum_{i=1}^{j}(a_i+1)}=2^{m+j}. i = 1 ∏ j ( a i + 2 ) ≤ 2 ∑ i = 1 j ( a i + 1 ) = 2 m + j . There is equality if and only if all components are zero, that is, if and only if m = 0 m=0 m = 0
Taking m = N F − 1 m=N_F-1 m = N F − 1 j = N J j=N_J j = N J
Π ( N F , N J ) ≤ 2 N F + N J − 1 . \Pi(N_F,N_J)\le2^{N_F+N_J-1}. Π ( N F , N J ) ≤ 2 N F + N J − 1 . with strict inequality for N F > 1 N_F>1 N F > 1
p ≤ ∏ i = 1 N J ( a i + 2 ) , a i ∈ N 0 , ∑ i = 1 N J a i = N F − 1. p\le\prod_{i=1}^{N_J}(a_i+2),\qquad a_i\in\mathbb{N}_0,\qquad\sum_{i=1}^{N_J}a_i=N_F-1. p ≤ i = 1 ∏ N J ( a i + 2 ) , a i ∈ N 0 , i = 1 ∑ N J a i = N F − 1. The lemma solves the maximization of the product, but does not provide this inequality. Assigning evaluations to groups does not, by itself, prove a restriction on the order.
The vector class in the conjecture
We denote by P n \mathcal{P}_n P n ( R n , F , α ) (\mathbb{R}^n,F,\alpha) ( R n , F , α ) F F F α \alpha α
Conjecture 11.3 (Vector product barrier). Let N F , N J ≥ 1 N_F,N_J \ge1 N F , N J ≥ 1 n ≥ N F + N J − 1 n \ge N_F+N_J-1 n ≥ N F + N J − 1 M \mathcal{M} M Definition 2.2 , with local budget ( N F , N J ) (N_F,N_J) ( N F , N J ) P n \mathcal{P}_n P n M \mathcal{M} M p > 1 p>1 p > 1
p ≤ Π ( N F , N J ) . p \le\Pi(N_F,N_J). p ≤ Π ( N F , N J ) . The rules may be arbitrary and pairing is not required. This formulation thus proposes an extension of the question posed for rational programs in [2 ] . The conjecture is not a consequence of the preceding barriers. Those barriers use entire test functions, which need not be polynomials. Furthermore, it has not been proved here that the dimensional condition is sufficient to construct the required perturbations.
For N J = 1 N_J=1 N J = 1 Π ( N F , 1 ) = N F + 1 \Pi(N_F,1)=N_F+1 Π ( N F , 1 ) = N F + 1 2 N F 2^{N_F} 2 N F N F = N J N_F=N_J N F = N J
Π ( N F , N F ) = 2 3 N F − 1 = B ( N F , N F ) . \Pi(N_F,N_F)=2^{3N_F-1}=B(N_F,N_F). Π ( N F , N F ) = 2 3 N F − 1 = B ( N F , N F ) . Numerical coincidence does not remove the differences between the function classes and pairing hypotheses. Nor is it true that Π \Pi Π B B B N J > N F N_J>N_F N J > N F Π ( 1 , 2 ) = 4 \Pi(1,2)=4 Π ( 1 , 2 ) = 4 B ( 1 , 2 ) = 2 B(1,2)=2 B ( 1 , 2 ) = 2
Why a dimensional condition is not enough
The following example develops the diagonal obstruction from [2 ] . It shows that the breadth of the function class is an essential part of the proposal.
Proposition 11.4 (Order four on a diagonal class). For every n ≥ 2 n \ge2 n ≥ 2 ( 2 , 1 ) (2,1) ( 2 , 1 )
G f ( z ) = ( f ( z 1 ) , z 2 , … , z n ) T G_f(z)=\left(f(z_1),z_2,\ldots,z_n\right)^{\mathsf{T}} G f ( z ) = ( f ( z 1 ) , z 2 , … , z n ) T is exactly four, when f f f H n ( I 0 ) \mathcal{H}_n(I_0) H n ( I 0 ) n ≥ 2 n \ge2 n ≥ 2 Π ( 2 , 1 ) = 3 \Pi(2,1)=3 Π ( 2 , 1 ) = 3
Proof. We query V = G f ( x ) V=G_f(x) V = G f ( x ) A = D G f ( x ) A=DG_f(x) A = D G f ( x ) A d = V Ad=V A d = V y = x − d y=x-d y = x − d V 1 = 0 V_1=0 V 1 = 0 y y y W = G f ( y ) W=G_f(y) W = G f ( y )
x 1 + = y 1 − V 1 W 1 A 11 ( V 1 − 2 W 1 ) , x i + = y i ( 2 ≤ i ≤ n ) . (57) x_1^+=y_1-\frac{V_1W_1}{A_{11}(V_1-2W_1)},\qquad x_i^+=y_i\quad(2\le i\le n). \tag*{(57)} x 1 + = y 1 − A 11 ( V 1 − 2 W 1 ) V 1 W 1 , x i + = y i ( 2 ≤ i ≤ n ) . (57) The rules receive neither the root nor the coefficients of f f f
Let a a a f f f A = diag ( f ′ ( x 1 ) , 1 , … , 1 ) A=\operatorname{diag}(f'(x_1),1,\ldots,1) A = diag ( f ′ ( x 1 ) , 1 , … , 1 ) y i = 0 y_i=0 y i = 0 i ≥ 2 i\ge2 i ≥ 2 e = x 1 − a e=x_1-a e = x 1 − a c = f ′ ( a ) ≠ 0 c=f'(a)\ne0 c = f ′ ( a ) = 0
c 2 = f ′ ′ ( a ) 2 c , c 3 = f ′ ′ ′ ( a ) 6 c . c_2=\frac{f''(a)}{2c},\qquad c_3=\frac{f'''(a)}{6c}. c 2 = 2 c f ′′ ( a ) , c 3 = 6 c f ′′′ ( a ) . Taylor expansion gives
f ( a + e ) c = e + c 2 e 2 + c 3 e 3 + O ( e 4 ) , f ′ ( a + e ) c = 1 + 2 c 2 e + 3 c 3 e 2 + O ( e 3 ) . \frac{f(a+e)}{c}=e+c_2e^2+c_3e^3+O(e^4),\qquad\frac{f'(a+e)}{c}=1+2c_2e+3c_3e^2+O(e^3). c f ( a + e ) = e + c 2 e 2 + c 3 e 3 + O ( e 4 ) , c f ′ ( a + e ) = 1 + 2 c 2 e + 3 c 3 e 2 + O ( e 3 ) . Inverting the second expression and multiplying by the first, we obtain
f ( a + e ) f ′ ( a + e ) = e − c 2 e 2 + ( 2 c 2 2 − 2 c 3 ) e 3 + O ( e 4 ) . \frac{f(a+e)}{f'(a+e)}=e-c_2e^2+(2c_2^2-2c_3)e^3+O(e^4). f ′ ( a + e ) f ( a + e ) = e − c 2 e 2 + ( 2 c 2 2 − 2 c 3 ) e 3 + O ( e 4 ) . Therefore,
y 1 − a = c 2 e 2 + ( 2 c 3 − 2 c 2 2 ) e 3 + O ( e 4 ) , y_1-a=c_2e^2+(2c_3-2c_2^2)e^3+O(e^4), y 1 − a = c 2 e 2 + ( 2 c 3 − 2 c 2 2 ) e 3 + O ( e 4 ) , f ( y 1 ) c = c 2 e 2 + ( 2 c 3 − 2 c 2 2 ) e 3 + O ( e 4 ) , \frac{f(y_1)}{c}=c_2e^2+(2c_3-2c_2^2)e^3+O(e^4), c f ( y 1 ) = c 2 e 2 + ( 2 c 3 − 2 c 2 2 ) e 3 + O ( e 4 ) , f ( y 1 ) f ′ ( a + e ) = c 2 e 2 + ( 2 c 3 − 4 c 2 2 ) e 3 + O ( e 4 ) . \frac{f(y_1)}{f'(a+e)}=c_2e^2+(2c_3-4c_2^2)e^3+O(e^4). f ′ ( a + e ) f ( y 1 ) = c 2 e 2 + ( 2 c 3 − 4 c 2 2 ) e 3 + O ( e 4 ) . Moreover, for e ≠ 0 e\ne0 e = 0
f ( a + e ) − 2 f ( y 1 ) = c e + O ( e 2 ) ≠ 0 , f(a+e)-2f(y_1)=ce+O(e^2)\ne0, f ( a + e ) − 2 f ( y 1 ) = ce + O ( e 2 ) = 0 , and
f ( a + e ) f ( a + e ) − 2 f ( y 1 ) = 1 + 2 c 2 e + O ( e 2 ) . \frac{f(a+e)}{f(a+e)-2f(y_1)}=1+2c_2e+O(e^2). f ( a + e ) − 2 f ( y 1 ) f ( a + e ) = 1 + 2 c 2 e + O ( e 2 ) . Thus the term subtracted from y 1 y_1 y 1
c 2 e 2 + ( 2 c 3 − 2 c 2 2 ) e 3 + O ( e 4 ) . c_2e^2+(2c_3-2c_2^2)e^3+O(e^4). c 2 e 2 + ( 2 c 3 − 2 c 2 2 ) e 3 + O ( e 4 ) . The terms of degrees two and three cancel, and we conclude that x 1 + − a = O ( e 4 ) x_1^+-a=O(e^4) x 1 + − a = O ( e 4 ) f ′ f' f ′ a a a f f f e = 0 e=0 e = 0 V 1 = 0 V_1=0 V 1 = 0 ( a , 0 , … , 0 ) T (a,0,\ldots,0)^T ( a , 0 , … , 0 ) T e ≠ 0 e\ne0 e = 0
∥ x + − ( a , 0 , … , 0 ) T ∥ ∞ ≤ C f ∣ x 1 − a ∣ 4 ≤ C f ∥ x − ( a , 0 , … , 0 ) T ∥ ∞ 4 . \left\|x^+-(a,0,\ldots,0)^T\right\|_\infty\le C_f|x_1-a|^4\le C_f\left\|x-(a,0,\ldots,0)^T\right\|_\infty^4. x + − ( a , 0 , … , 0 ) T ∞ ≤ C f ∣ x 1 − a ∣ 4 ≤ C f x − ( a , 0 , … , 0 ) T ∞ 4 . To verify that the universal order is not greater, take f ( s ) = s + s 2 f(s)=s+s^2 f ( s ) = s + s 2 x = ( t , 0 , … , 0 ) T x=(t,0,\ldots,0)^T x = ( t , 0 , … , 0 ) T
y 1 = t 2 1 + 2 t , x 1 + = t 4 ( 1 + 2 t ) ( 1 + 2 t + 2 t 2 ) = t 4 + O ( t 5 ) . y_1=\frac{t^2}{1+2t},\qquad x_1^+=\frac{t^4}{(1+2t)(1+2t+2t^2)}=t^4+O(t^5). y 1 = 1 + 2 t t 2 , x 1 + = ( 1 + 2 t ) ( 1 + 2 t + 2 t 2 ) t 4 = t 4 + O ( t 5 ) . The leading coefficient is nonzero. Therefore, no estimate with exponent greater than four holds over the entire class. Finally, Π ( 2 , 1 ) = 3 \Pi(2,1)=3 Π ( 2 , 1 ) = 3 n ≥ 2 n\ge2 n ≥ 2
The proposition does not refute Conjecture 11.3: the constructed method does not guarantee order four on all fields in P n \mathcal{P}_n P n
A sufficient criterion for vector perturbations
The proposal in [2 ] uses perturbations that preserve information and displace the root. To separate that construction from the regularity of the rules, we give a criterion in which the required uniformity appears as an explicit hypothesis.
Let D > 1 D > 1 D > 1 β = ( β 1 , … , β n ) ∈ N 0 n \beta= (\beta_1,\ldots,\beta_n) \in\mathbb{N}_0^n β = ( β 1 , … , β n ) ∈ N 0 n ∣ β ∣ = ∑ i β i |\beta| = \sum_i \beta_i ∣ β ∣ = ∑ i β i β ! = ∏ i β i ! \beta! = \prod_i \beta_i! β ! = ∏ i β i ! z β = ∏ i z i β i z^\beta= \prod_i z_i^{\beta_i} z β = ∏ i z i β i
F θ ( z ) = A ( z − a ) + ∑ 2 ≤ ∣ β ∣ ≤ D c β ( z − a ) β , det A ≠ 0 , (58) F_\theta(z) = A(z-a) + \sum_{2 \leq|\beta| \leq D} c_\beta(z-a)^\beta,\qquad\det A \ne0, \tag*{(58)} F θ ( z ) = A ( z − a ) + 2 ≤ ∣ β ∣ ≤ D ∑ c β ( z − a ) β , det A = 0 , (58) where θ = ( a , A , ( c β ) ) \theta= (a,A,(c_\beta)) θ = ( a , A , ( c β )) a , c β ∈ R n a,c_\beta\in\mathbb{R}^n a , c β ∈ R n A ∈ R n × n A \in\mathbb{R}^{n \times n} A ∈ R n × n D = 1 D = 1 D = 1 Θ n , D \Theta_{n,D} Θ n , D a θ = a a_\theta= a a θ = a D F θ ( a ) = A DF_\theta(a) = A D F θ ( a ) = A
Definition 11.5 (Uniform estimate in the parameters). Let K ⊂ Θ n , D K \subset\Theta_{n,D} K ⊂ Θ n , D W ⊂ R n ∖ { 0 } W \subset\mathbb{R}^n \setminus\{0\} W ⊂ R n ∖ { 0 } M \mathcal{M} M p p p K × W K \times W K × W C , t 0 > 0 C,t_0 > 0 C , t 0 > 0
∥ M F θ ( a θ + t v ) − a θ ∥ ∞ ≤ C t p ( θ ∈ K , v ∈ W , 0 < t < t 0 ) . (59) \|\mathcal{M}_{F_\theta}(a_\theta+ tv)-a_\theta\|_\infty\leq Ct^p \qquad(\theta\in K,\ v \in W,\ 0 < t < t_0). \tag*{(59)} ∥ M F θ ( a θ + t v ) − a θ ∥ ∞ ≤ C t p ( θ ∈ K , v ∈ W , 0 < t < t 0 ) . (59) The definition requires the same constant and the same interval of scales. It is stronger than having, for each field, the constants in Definition 2.5. We do not suppose that a universal local estimate for arbitrary rules automatically yields (11.7).
Lemma 11.6 (Vector root displacement and parameter control). Let F = F θ 0 F = F_{\theta_0} F = F θ 0 a a a A = D F ( a ) A = DF(a) A = D F ( a ) H t : R n → R n H_t:\mathbb{R}^n \to\mathbb{R}^n H t : R n → R n 0 < t < t 1 0 < t < t_1 0 < t < t 1 D D D
H t ( a ) = t σ w + o ( t σ ) , σ > 1 , w ≠ 0. H_t(a) = t^\sigma w + o(t^\sigma),\qquad\sigma> 1,\qquad w \ne0. H t ( a ) = t σ w + o ( t σ ) , σ > 1 , w = 0. There exist ρ , η 0 , t 2 , C 0 , C 1 , C 2 > 0 \rho,\eta_0,t_2,C_0,C_1,C_2 > 0 ρ , η 0 , t 2 , C 0 , C 1 , C 2 > 0 ∣ η ∣ ≤ η 0 |\eta| \leq\eta_0 ∣ η ∣ ≤ η 0 0 < t < t 2 0 < t < t_2 0 < t < t 2 F + η H t F+\eta H_t F + η H t a η ( t ) a_\eta(t) a η ( t ) a a a ρ \rho ρ
C 1 ∣ η ∣ ∥ H t ( a ) ∥ ∞ ≤ ∥ a η ( t ) − a ∥ ∞ ≤ C 2 ∣ η ∣ ∥ H t ( a ) ∥ ∞ . (60) C_1|\eta|\|H_t(a)\|_\infty\leq\|a_\eta(t)-a\|_\infty\leq C_2|\eta|\|H_t(a)\|_\infty. \tag*{(60)} C 1 ∣ η ∣∥ H t ( a ) ∥ ∞ ≤ ∥ a η ( t ) − a ∥ ∞ ≤ C 2 ∣ η ∣∥ H t ( a ) ∥ ∞ . (60) Moreover, the perturbed field admits an exact representation F ~ θ ~ ( t , η ) \widetilde{F}_{\widetilde{\theta}(t,\eta)} F θ ( t , η )
∥ θ ~ ( t , η ) − θ 0 ∥ ∞ ≤ C 0 ∣ η ∣ . (61) \|\widetilde{\theta}(t,\eta)-\theta_0\|_\infty\leq C_0|\eta|. \tag*{(61)} ∥ θ ( t , η ) − θ 0 ∥ ∞ ≤ C 0 ∣ η ∣. (61) In particular, for each fixed sufficiently small η ≠ 0 \eta\ne0 η = 0 Θ ( t σ ) \Theta(t^\sigma) Θ ( t σ )
Proof. Choose ρ > 0 \rho> 0 ρ > 0
∥ I − A − 1 D F ( z ) ∥ ∞ ≤ 1 4 ( ∥ z − a ∥ ∞ ≤ ρ ) . \|I-A^{-1}DF(z)\|_\infty\leq\frac{1}{4}\qquad(\|z-a\|_\infty\leq\rho). ∥ I − A − 1 D F ( z ) ∥ ∞ ≤ 4 1 ( ∥ z − a ∥ ∞ ≤ ρ ) . Boundedness of the coefficients and degree of H t H_t H t H t H_t H t L 1 ≥ 0 L_1 \geq0 L 1 ≥ 0 ∥ D H t ( z ) ∥ ∞ \|DH_t(z)\|_\infty ∥ D H t ( z ) ∥ ∞ η 0 > 0 \eta_0 > 0 η 0 > 0
η 0 ∥ A − 1 ∥ ∞ L 1 ≤ 1 4 . \eta_0\|A^{-1}\|_\infty L_1 \leq\frac{1}{4}. η 0 ∥ A − 1 ∥ ∞ L 1 ≤ 4 1 . For G = F + η H t G = F+\eta H_t G = F + η H t
Φ ( z ) = z − A − 1 G ( z ) (62) \Phi(z)=z-A^{-1}G(z) \tag*{(62)} Φ ( z ) = z − A − 1 G ( z ) (62) has Lipschitz constant no greater than 1 / 2 1/2 1/2 H t ( a ) → 0 H_t(a) \to0 H t ( a ) → 0 t 2 t_2 t 2
∥ Φ ( a ) − a ∥ ∞ = ∣ η ∣ ∥ A − 1 H t ( a ) ∥ ∞ < ρ / 2 \|\Phi(a)-a\|_\infty=|\eta|\|A^{-1}H_t(a)\|_\infty<\rho/2 ∥Φ ( a ) − a ∥ ∞ = ∣ η ∣∥ A − 1 H t ( a ) ∥ ∞ < ρ /2 uniformly for ∣ η ∣ ≤ η 0 |\eta|\le\eta_0 ∣ η ∣ ≤ η 0 Φ \Phi Φ a η ( t ) a_\eta(t) a η ( t ) G G G
Write Δ = a η ( t ) − a \Delta=a_\eta(t)-a Δ = a η ( t ) − a
∥ Δ ∥ ∞ ≤ 1 2 ∥ Δ ∥ ∞ + ∣ η ∣ ∥ A − 1 ∥ ∞ ∥ H t ( a ) ∥ ∞ . \|\Delta\|_\infty\le\frac{1}{2}\|\Delta\|_\infty+|\eta|\|A^{-1}\|_\infty\|H_t(a)\|_\infty. ∥Δ ∥ ∞ ≤ 2 1 ∥Δ ∥ ∞ + ∣ η ∣∥ A − 1 ∥ ∞ ∥ H t ( a ) ∥ ∞ . This proves the upper bound with C 2 = 2 ∥ A − 1 ∥ ∞ C_2=2\|A^{-1}\|_\infty C 2 = 2∥ A − 1 ∥ ∞ D G DG D G L > 0 L>0 L > 0
− η H t ( a ) = G ( a + Δ ) − G ( a ) = ∫ 0 1 D G ( a + s Δ ) Δ d s . -\eta H_t(a)=G(a+\Delta)-G(a)=\int_0^1 DG(a+s\Delta)\Delta\,\mathrm{d}s. − η H t ( a ) = G ( a + Δ ) − G ( a ) = ∫ 0 1 D G ( a + s Δ ) Δ d s . Therefore, ∣ η ∣ ∥ H t ( a ) ∥ ∞ ≤ L ∥ Δ ∥ ∞ |\eta|\|H_t(a)\|_\infty\le L\|\Delta\|_\infty ∣ η ∣∥ H t ( a ) ∥ ∞ ≤ L ∥Δ ∥ ∞ C 1 = 1 / L C_1=1/L C 1 = 1/ L
∥ I − A − 1 D G ( a η ( t ) ) ∥ ∞ ≤ 1 2 < 1 , \left\|I-A^{-1}DG(a_\eta(t))\right\|_\infty\le\frac{1}{2}<1, I − A − 1 D G ( a η ( t )) ∞ ≤ 2 1 < 1 , so D G ( a η ( t ) ) DG(a_\eta(t)) D G ( a η ( t ))
To obtain the parameters, we expand the polynomial G G G a η ( t ) a_\eta(t) a η ( t )
a ~ = a η ( t ) , A ~ = D G ( a η ( t ) ) , c ~ β = ∂ β G ( a η ( t ) ) β ! ( 2 ≤ ∣ β ∣ ≤ D ) . \widetilde{a}=a_\eta(t),\qquad\widetilde{A}=DG(a_\eta(t)),\qquad\widetilde{c}_\beta=\frac{\partial^\beta G(a_\eta(t))}{\beta!}\qquad(2\le|\beta|\le D). a = a η ( t ) , A = D G ( a η ( t )) , c β = β ! ∂ β G ( a η ( t )) ( 2 ≤ ∣ β ∣ ≤ D ) . Taylor’s formula is exact because the degree does not exceed D D D G = F θ ~ G=F_{\widetilde{\theta}} G = F θ θ ~ ∈ Θ n , D \widetilde{\theta}\in\Theta_{n,D} θ ∈ Θ n , D F F F H t H_t H t a a a ∥ Δ ∥ ∞ + ∣ η ∣ \|\Delta\|_\infty+|\eta| ∥Δ ∥ ∞ + ∣ η ∣ H t ( a ) H_t(a) H t ( a ) ∥ Δ ∥ ∞ ≤ C ∣ η ∣ \|\Delta\|_\infty\le C|\eta| ∥Δ ∥ ∞ ≤ C ∣ η ∣
Finally, ∥ H t ( a ) ∥ ∞ / t σ → ∥ w ∥ ∞ > 0 \|H_t(a)\|_\infty/t^\sigma\to\|w\|_\infty>0 ∥ H t ( a ) ∥ ∞ / t σ → ∥ w ∥ ∞ > 0 η ≠ 0 \eta\ne0 η = 0
Proposition 11.7 (Sufficient criterion under explicit uniformity). Let b ≥ 2 b\ge2 b ≥ 2 M \mathcal{M} M D ≥ 1 D\ge1 D ≥ 1 ( θ 0 , v 0 ) ∈ Θ n , D × ( R n ∖ { 0 } ) (\theta_0,v_0)\in\Theta_{n,D}\times(\mathbb{R}^n\setminus\{0\}) ( θ 0 , v 0 ) ∈ Θ n , D × ( R n ∖ { 0 }) K , W K,W K , W θ 0 , v 0 \theta_0,v_0 θ 0 , v 0 p > 1 p>1 p > 1
Write F = F θ 0 F=F_{\theta_0} F = F θ 0 a = a θ 0 a=a_{\theta_0} a = a θ 0 t > 0 t>0 t > 0 H t H_t H t D D D
H t ( Y ) = 0 at each function query , D H t ( Z ) = 0 at each Jacobian query , (63) H_t(Y)=0\ \text{at each function query},\qquad DH_t(Z)=0\ \text{at each Jacobian query}, \tag*{(63)} H t ( Y ) = 0 at each function query , D H t ( Z ) = 0 at each Jacobian query , (63) of the record of M F ( a + t v 0 ) \mathcal{M}_F(a+tv_0) M F ( a + t v 0 )
H t ( a ) = t σ w + o ( t σ ) , 1 < σ ≤ b , w ≠ 0. H_t(a)=t^\sigma w+o(t^\sigma),\qquad1<\sigma\le b,\qquad w\ne0. H t ( a ) = t σ w + o ( t σ ) , 1 < σ ≤ b , w = 0. Then p ≤ b p\le b p ≤ b b = Π ( N F , N J ) b=\Pi(N_F,N_J) b = Π ( N F , N J )
Proof. Suppose p > b p>b p > b Lemma 11.6 . Since θ 0 \theta_0 θ 0 K K K η ≠ 0 \eta\ne0 η = 0
θ ~ ( t , η ) ∈ K \widetilde{\theta}(t,\eta)\in K θ ( t , η ) ∈ K for all sufficiently small t t t a t = a η ( t ) a_t=a_\eta(t) a t = a η ( t )
v t = v 0 − a t − a t . v_t=v_0-\frac{a_t-a}{t}. v t = v 0 − t a t − a . The lemma gives ∥ a t − a ∥ ∞ = Θ ( t σ ) \lVert a_t-a\rVert_\infty=\Theta(t^\sigma) ∥ a t − a ∥ ∞ = Θ ( t σ ) σ > 1 \sigma>1 σ > 1 v t → v 0 v_t\to v_0 v t → v 0 v t ∈ W v_t\in W v t ∈ W t t t
a t + t v t = a + t v 0 . a_t+tv_t=a+tv_0. a t + t v t = a + t v 0 . Thus the two executions start at exactly the same initial point.
Conditions (11.10) preserve the complete function vectors and Jacobian matrices. By Lemma 2.6 ,
M F ~ θ ~ ( t , η ) ( a + t v 0 ) = M F ( a + t v 0 ) . \mathcal{M}_{\widetilde{F}_{\widetilde{\theta}(t,\eta)}}(a+tv_0)=\mathcal{M}_F(a+tv_0). M F θ ( t , η ) ( a + t v 0 ) = M F ( a + t v 0 ) . We apply (59) to ( θ 0 , v 0 ) (\theta_0,v_0) ( θ 0 , v 0 ) ( θ ~ ( t , η ) , v t ) (\widetilde{\theta}(t,\eta),v_t) ( θ ( t , η ) , v t )
∥ a t − a ∥ ∞ ≤ ∥ M F ( a + t v 0 ) − a ∥ ∞ + ∥ M F ~ θ ~ ( t , η ) ( a t + t v t ) − a t ∥ ∞ ≤ 2 C t p . \begin{aligned}
\lVert a_t-a\rVert_\infty
&\le\lVert\mathcal{M}_F(a+tv_0)-a\rVert_\infty\\
&\quad+\left\lVert\mathcal{M}_{\widetilde{F}_{\widetilde{\theta}(t,\eta)}}(a_t+tv_t)-a_t\right\rVert_\infty
\le2Ct^p.
\end{aligned} ∥ a t − a ∥ ∞ ≤ ∥ M F ( a + t v 0 ) − a ∥ ∞ + M F θ ( t , η ) ( a t + t v t ) − a t ∞ ≤ 2 C t p . This contradicts the lower bound of magnitude t σ t^\sigma t σ p > b ≥ σ p>b\ge\sigma p > b ≥ σ p ≤ b p\le b p ≤ b
Remark 11.8 (What the criterion requires). The proposition proves an implication, not that every method in Conjecture 11.3 satisfies its hypotheses. In the rational framework of [2 ] , uniformity is obtained on suitable parameter regions from rational dependence and control of decisions. That justification does not automatically carry over to arbitrary rules. In the present criterion, uniformity is explicitly required, and the perturbation family with exponent σ ≤ Π ( N F , N J ) \sigma\le\Pi(N_F,N_J) σ ≤ Π ( N F , N J )
The vanishing condition D H t ( Z ) = 0 DH_t(Z)=0 D H t ( Z ) = 0 H t H_t H t
ℓ t ( 1 , 0 ) = 1 , ℓ t ( 1 , t m ) = 0 \ell_t(1,0)=1,\qquad\ell_t(1,t^m)=0 ℓ t ( 1 , 0 ) = 1 , ℓ t ( 1 , t m ) = 0 on a linear form in R 2 \mathbb{R}^2 R 2 m ≥ 1 m\ge1 m ≥ 1
ℓ t ( z 1 , z 2 ) = z 1 − t − m z 2 . \ell_t(z_1,z_2)=z_1-t^{-m}z_2. ℓ t ( z 1 , z 2 ) = z 1 − t − m z 2 . The system has full rank for every t > 0 t>0 t > 0
Orders observed on a coupled vector field
Consider the polynomial field
Ψ ( u , v ) = ( u + u 2 + u v v + u 2 + u v + v 2 ) . (64) \Psi(u,v)=
\begin{pmatrix}
u+u^2+uv\\
v+u^2+uv+v^2
\end{pmatrix}. \tag*{(64)} Ψ ( u , v ) = ( u + u 2 + uv v + u 2 + uv + v 2 ) . (64) Its root α = ( 0 , 0 ) T \alpha=(0,0)^{T} α = ( 0 , 0 ) T D Ψ ( 0 , 0 ) = I D\Psi(0,0)=I D Ψ ( 0 , 0 ) = I x ( t ) = t ( 1 , 2 ) T x(t)=t(1,2)^{T} x ( t ) = t ( 1 , 2 ) T t = 10 − k t=10^{-k} t = 1 0 − k 6 ≤ k ≤ 13 6\le k\le13 6 ≤ k ≤ 13 ∥ M Ψ ( x ( t ) ) ∥ ∞ \lVert M_{\Psi}(x(t))\rVert_{\infty} ∥ M Ψ ( x ( t )) ∥ ∞ Table 2 presents the orders claimed for systems and the observed exponents, rounded to the integer they approach.
Table 2. Claimed order and observed order on (11.11).
For M 7 , 1 M_{7,1} M 7 , 1 H ( μ ) = I + μ + μ 2 H(\mu) = I + \mu+ \mu^{2} H ( μ ) = I + μ + μ 2 G ( μ , ν ) = I + μ ν + ( 13 / 6 ) μ ν 2 G(\mu,\nu) = I + \mu\nu+ (13/6)\mu\nu^{2} G ( μ , ν ) = I + μν + ( 13/6 ) μ ν 2 [10 ] , we take the polynomial expressions in (26) and (46), without higher-order remainders. For WFM1–WFM5, we use the choices in Table 1 of the May 26, 2026 version of [12 ] . M5 and the Sharma–Guha scheme in the first row are algebraically equal; likewise, WFM1 reproduces CTT8. These coincidences are not counted as independent constructions.
The results show orders lower than those claimed in this coupled test. The observed-order column describes only what was observed along x ( t ) x(t) x ( t ) Q Q Q Conjecture 11.3 . The comparison concerns the local behavior of the formulas; it does not presume that all use the same query model, since some employ divided differences or higher-order derivatives.
Local order and trajectories
Our results concern (2.2). The sequence X m X_m X m X m + 1 = M F ( X m ) X_{m+1} = M_F(X_m) X m + 1 = M F ( X m ) Q Q Q
§ 12 proves the implication from a local estimate to convergence of the trajectories, exhibits obstructions to the converse, and establishes sufficient conditions for transferring both barriers to Q Q Q Theorems 4.2 and 9.1 .
Dependencies of the proofs
The general barrier in § 4 uses Theorem 4.1, namely Proposition 7.7 of [1 ] , as a previous result. The simulation, its expression through rules on response vectors, preservation of the counters, treatment of domains, and transfer of the obstruction are proved here. The effective-budget bound in Corollary 10.2 uses the same scalar antecedent.
That antecedent controls the total number of queries without distinguishing whether a first derivative is accompanied by an earlier function value. Thus, substituting d = N F + N J d = N_F + N_J d = N F + N J H ′ ( v ) = 0 H'(v) = 0 H ′ ( v ) = 0 H ( v ) = 0 H(v) = 0 H ( v ) = 0 § 6 –§ 8 .
The paired barrier follows from Proposition 7.1 and the complete construction in § 8 . It is not deduced from a purported improvement of the general scalar theorem or from rationality of the nodes. Its analytic dependence is limited to the elementary results used explicitly: continuity, the mean value theorem, Cauchy estimates, and uniform convergence on compact disks.
Order of one cycle and order of trajectories
The preceding barriers concern estimate (5) , which must hold at all points of a punctured neighborhood of each root. In this section, we specify its relationship with the order of convergence of sequences generated by the method. We do not assume that regularity of the field carries over to the rules or the output map.
Local estimates and error equations
Fix a problem ( Ω , F , α ) (\Omega,F,\alpha) ( Ω , F , α )
E ( e ) = M F ( α + e ) − α ( 0 < ∥ e ∥ ∞ < ρ ) E(e) = \mathcal{M}_F(\alpha+ e) - \alpha\qquad(0 < \lVert e\rVert_\infty< \rho) E ( e ) = M F ( α + e ) − α ( 0 < ∥ e ∥ ∞ < ρ ) and, when iteration from the root is necessary, define E ( 0 ) = 0 E(0) = 0 E ( 0 ) = 0
Proposition 12.1 (Consequences of a one-cycle estimate). Let p > 1 p > 1 p > 1
(i) If
lim sup e → 0 , e ≠ 0 ∥ E ( e ) ∥ ∞ ∥ e ∥ ∞ p < + ∞ , \limsup_{\substack{e \to0,\\ e \ne0}} \frac{\lVert E(e)\rVert_\infty}{\lVert e\rVert_\infty^p} < +\infty, e → 0 , e = 0 lim sup ∥ e ∥ ∞ p ∥ E ( e ) ∥ ∞ < + ∞ , then there exist C , δ > 0 C,\delta> 0 C , δ > 0 ∥ E ( e ) ∥ ∞ ≤ C ∥ e ∥ ∞ p \lVert E(e)\rVert_\infty\le C\lVert e\rVert_\infty^p ∥ E ( e ) ∥ ∞ ≤ C ∥ e ∥ ∞ p 0 < ∥ e ∥ ∞ < δ 0 < \lVert e\rVert_\infty< \delta 0 < ∥ e ∥ ∞ < δ
(ii) Let m ≥ 2 m \ge2 m ≥ 2 P m : R n → R n P_m:\mathbb{R}^n \to\mathbb{R}^n P m : R n → R n m m m
E ( e ) = P m ( e ) + o ( ∥ e ∥ ∞ m ) ( e → 0 ) , (65) E(e) = P_m(e) + o(\lVert e\rVert_\infty^m) \qquad(e \to0), \tag*{(65)} E ( e ) = P m ( e ) + o (∥ e ∥ ∞ m ) ( e → 0 ) , (65) then a local estimate with exponent m m m P m ≢ 0 P_m \not\equiv0 P m ≡ 0 m m m
(iii) If ∥ E ( e ) ∥ ∞ ≤ C ∥ e ∥ ∞ p \lVert E(e)\rVert_\infty\le C\lVert e\rVert_\infty^p ∥ E ( e ) ∥ ∞ ≤ C ∥ e ∥ ∞ p
lim sup k → ∞ ∥ e k + 1 ∥ ∞ ∥ e k ∥ ∞ p ≤ C , ∥ e k + 1 ∥ ∞ ∥ e k ∥ ∞ ⟶ 0. \limsup_{k\to\infty}\frac{\lVert e_{k+1}\rVert_\infty}{\lVert e_k\rVert_\infty^p} \le C,\qquad\frac{\lVert e_{k+1}\rVert_\infty}{\lVert e_k\rVert_\infty} \longrightarrow0. k → ∞ lim sup ∥ e k ∥ ∞ p ∥ e k + 1 ∥ ∞ ≤ C , ∥ e k ∥ ∞ ∥ e k + 1 ∥ ∞ ⟶ 0. Proof. For the first statement, let L L L δ > 0 \delta> 0 δ > 0 L + 1 L + 1 L + 1 δ \delta δ C = L + 1 C = L + 1 C = L + 1 P m P_m P m ∥ v ∥ ∞ = 1 \|v\|_\infty= 1 ∥ v ∥ ∞ = 1
A = max ∥ v ∥ ∞ = 1 ∥ P m ( v ) ∥ ∞ < + ∞ . A = \max_{\|v\|_\infty=1} \|P_m(v)\|_\infty< +\infty. A = ∥ v ∥ ∞ = 1 max ∥ P m ( v ) ∥ ∞ < + ∞. By homogeneity, ∥ P m ( e ) ∥ ∞ ≤ A ∥ e ∥ ∞ m \|P_m(e)\|_\infty\le A\|e\|_\infty^m ∥ P m ( e ) ∥ ∞ ≤ A ∥ e ∥ ∞ m (65) has norm at most ∥ e ∥ ∞ m \|e\|_\infty^m ∥ e ∥ ∞ m ∥ E ( e ) ∥ ∞ ≤ ( A + 1 ) ∥ e ∥ ∞ m \|E(e)\|_\infty\le(A+1)\|e\|_\infty^m ∥ E ( e ) ∥ ∞ ≤ ( A + 1 ) ∥ e ∥ ∞ m P m ≢ 0 P_m \not\equiv0 P m ≡ 0 v v v ∥ v ∥ ∞ = 1 \|v\|_\infty= 1 ∥ v ∥ ∞ = 1 P m ( v ) ≠ 0 P_m(v) \ne0 P m ( v ) = 0 t > 0 t > 0 t > 0
E ( t v ) = t m P m ( v ) + o ( t m ) , ∥ E ( t v ) ∥ ∞ t m ⟶ ∥ P m ( v ) ∥ ∞ > 0. E(tv) = t^mP_m(v) + o(t^m), \qquad\frac{\|E(tv)\|_\infty}{t^m} \longrightarrow\|P_m(v)\|_\infty> 0. E ( t v ) = t m P m ( v ) + o ( t m ) , t m ∥ E ( t v ) ∥ ∞ ⟶ ∥ P m ( v ) ∥ ∞ > 0. For any r > m r > m r > m ∥ E ( t v ) ∥ ∞ / t r \|E(tv)\|_\infty/t^r ∥ E ( t v ) ∥ ∞ / t r + ∞ +\infty + ∞ r r r
Finally, choose 0 < δ 1 < δ 0 < \delta_1 < \delta 0 < δ 1 < δ C δ 1 p − 1 ≤ 1 / 2 C\delta_1^{p-1} \le1/2 C δ 1 p − 1 ≤ 1/2 ∥ e 0 ∥ ∞ < δ 1 \|e_0\|_\infty< \delta_1 ∥ e 0 ∥ ∞ < δ 1 e k ≠ 0 e_k \ne0 e k = 0
∥ e k + 1 ∥ ∞ ≤ C ∥ e k ∥ ∞ p − 1 ∥ e k ∥ ∞ ≤ 1 2 ∥ e k ∥ ∞ . \|e_{k+1}\|_\infty\le C\|e_k\|_\infty^{p-1}\|e_k\|_\infty\le\frac{1}{2}\|e_k\|_\infty. ∥ e k + 1 ∥ ∞ ≤ C ∥ e k ∥ ∞ p − 1 ∥ e k ∥ ∞ ≤ 2 1 ∥ e k ∥ ∞ . Induction shows that all iterates remain in the neighborhood and that ∥ e k ∥ ∞ ≤ 2 − k ∥ e 0 ∥ ∞ \|e_k\|_\infty\le2^{-k}\|e_0\|_\infty ∥ e k ∥ ∞ ≤ 2 − k ∥ e 0 ∥ ∞
∥ e k + 1 ∥ ∞ ∥ e k ∥ ∞ ≤ C ∥ e k ∥ ∞ p − 1 ⟶ 0. \frac{\|e_{k+1}\|_\infty}{\|e_k\|_\infty} \le C\|e_k\|_\infty^{p-1} \longrightarrow0. ∥ e k ∥ ∞ ∥ e k + 1 ∥ ∞ ≤ C ∥ e k ∥ ∞ p − 1 ⟶ 0. This proves all three statements.
Remark 12.2 (One-cycle limits and historical formulations). In [3 Section 2, p. 644] , order is formulated through a limit as the input x x x (65) , valid as e → 0 e \to0 e → 0
This remark does not by itself identify all historical classes of methods with our model. Causality, memorylessness, information accounting, and functional universality must be preserved. Nor does it replace an equation verified only along a particular sequence with a neighborhood limit.
Trajectories and limits of the converse implication
Definition 12.3 (Trajectory and exact Q Q Q E E E E ( 0 ) = 0 E(0) = 0 E ( 0 ) = 0 e k + 1 = E ( e k ) e_{k+1} = E(e_k) e k + 1 = E ( e k ) e k ≠ 0 e_k \ne0 e k = 0 k k k exact Q Q Q r > 1 r > 1 r > 1 ℓ ∈ ( 0 , + ∞ ) \ell\in(0,+\infty) ℓ ∈ ( 0 , + ∞ )
∥ e k + 1 ∥ ∞ ∥ e k ∥ ∞ r ⟶ ℓ . \frac{\|e_{k+1}\|_\infty}{\|e_k\|_\infty^r} \longrightarrow\ell. ∥ e k ∥ ∞ r ∥ e k + 1 ∥ ∞ ⟶ ℓ . We say it satisfies a trajectory estimate with exponent r r r C > 0 C > 0 C > 0 k 0 k_0 k 0 ∥ e k + 1 ∥ ∞ ≤ C ∥ e k ∥ ∞ r \|e_{k+1}\|_\infty\le C\|e_k\|_\infty^r ∥ e k + 1 ∥ ∞ ≤ C ∥ e k ∥ ∞ r k ≥ k 0 k \ge k_0 k ≥ k 0 Q Q Q
The constant in a trajectory estimate may depend on the initial point. It must not be confused with a constant valid for every input in a neighborhood. Nor do we assign infinite exact Q Q Q
Example 12.4 (C 1 C^1 C 1 [1 Example 10.7] ,
ψ ( e ) = { − e 2 , e ≥ 0 , − e 4 , e < 0. \psi(e) =
\begin{cases}
-e^2, & e \ge0, \\
-e^4, & e < 0.
\end{cases} ψ ( e ) = { − e 2 , − e 4 , e ≥ 0 , e < 0. The function is of class C 1 C^1 C 1 − 2 e -2e − 2 e − 4 e 3 -4e^3 − 4 e 3 0 < ∣ e 0 ∣ < 1 0 < |e_0| < 1 0 < ∣ e 0 ∣ < 1
e k + 1 = − e k 4 , ∣ e k + 1 ∣ = ∣ e k ∣ 4 . e_{k+1}=-e_k^4,\qquad|e_{k+1}|=|e_k|^4. e k + 1 = − e k 4 , ∣ e k + 1 ∣ = ∣ e k ∣ 4 . All these trajectories converge to zero and have exact Q Q Q e > 0 e>0 e > 0
∣ ψ ( e ) ∣ ∣ e ∣ 4 = e − 2 ⟶ + ∞ . \frac{|\psi(e)|}{|e|^4}=e^{-2}\longrightarrow+\infty. ∣ e ∣ 4 ∣ ψ ( e ) ∣ = e − 2 ⟶ + ∞. The neighborhood estimate of order four does not hold. The exact local order of this map is two: ∣ ψ ( e ) ∣ ≤ ∣ e ∣ 2 |\psi(e)|\le|e|^2 ∣ ψ ( e ) ∣ ≤ ∣ e ∣ 2 ∣ e ∣ < 1 |e|<1 ∣ e ∣ < 1
Example 12.5 (Vector analyticity is not enough). Consider the polynomial map
E : R 2 ⟶ R 2 , E ( u , v ) = ( v 2 , v 3 ) . E:\mathbb{R}^2\longrightarrow\mathbb{R}^2,\qquad E(u,v)=(v^2,v^3). E : R 2 ⟶ R 2 , E ( u , v ) = ( v 2 , v 3 ) . For ∥ ( u , v ) ∥ ∞ < 1 \|(u,v)\|_\infty<1 ∥ ( u , v ) ∥ ∞ < 1 ∥ E ( u , v ) ∥ ∞ = ∣ v ∣ 2 ≤ ∥ ( u , v ) ∥ ∞ 2 \|E(u,v)\|_\infty=|v|^2\le\|(u,v)\|_\infty^2 ∥ E ( u , v ) ∥ ∞ = ∣ v ∣ 2 ≤ ∥ ( u , v ) ∥ ∞ 2 ( u , v ) = ( 0 , t ) (u,v)=(0,t) ( u , v ) = ( 0 , t ) 0 < t < 1 0<t<1 0 < t < 1 t 2 t^2 t 2 E E E
On the other hand, if 0 < ∣ v 0 ∣ < 1 0<|v_0|<1 0 < ∣ v 0 ∣ < 1 ( u 0 , v 0 ) (u_0,v_0) ( u 0 , v 0 ) k ≥ 1 k\ge1 k ≥ 1
v k = v 0 3 k , u k = v 0 2 ⋅ 3 k − 1 , ∥ ( u k , v k ) ∥ ∞ = ∣ v 0 ∣ 2 ⋅ 3 k − 1 . v_k=v_0^{3^k},\qquad u_k=v_0^{2\cdot3^{k-1}},\qquad\|(u_k,v_k)\|_\infty=|v_0|^{2\cdot3^{k-1}}. v k = v 0 3 k , u k = v 0 2 ⋅ 3 k − 1 , ∥ ( u k , v k ) ∥ ∞ = ∣ v 0 ∣ 2 ⋅ 3 k − 1 . These identities hold for k = 1 k=1 k = 1 E E E
∥ ( u k + 1 , v k + 1 ) ∥ ∞ = ∥ ( u k , v k ) ∥ ∞ 3 ( k ≥ 1 ) . \|(u_{k+1},v_{k+1})\|_\infty=\|(u_k,v_k)\|_\infty^3\qquad(k\ge1). ∥ ( u k + 1 , v k + 1 ) ∥ ∞ = ∥ ( u k , v k ) ∥ ∞ 3 ( k ≥ 1 ) . Every nonterminating trajectory sufficiently close to the origin has exact Q Q Q v 0 = 0 v_0=0 v 0 = 0
Thus, even for an analytic output map, the order of all nonterminating trajectories does not automatically determine the local order of the vector map. The lowest-degree homogeneous term, ( v 2 , 0 ) (v^2,0) ( v 2 , 0 )
A scalar bridge under regularity of the operator
The following argument develops the implication in [1 Lemma 10.5] . We use a trajectory estimate, which is a weaker hypothesis than the existence of exact Q Q Q
Lemma 12.6 (Vanishing of lower-degree terms). Let b ∈ N b\in\mathbb{N} b ∈ N ψ \psi ψ C b + 1 C^{b+1} C b + 1 ψ ( 0 ) = 0 \psi(0)=0 ψ ( 0 ) = 0 e k → 0 e_k\to0 e k → 0 r > b r>b r > b C > 0 C>0 C > 0 k 0 ∈ N 0 k_0\in\mathbb{N}_0 k 0 ∈ N 0
∣ e k + 1 ∣ = ∣ ψ ( e k ) ∣ ≤ C ∣ e k ∣ r ( k ≥ k 0 ) . |e_{k+1}|=|\psi(e_k)|\le C|e_k|^r\qquad(k\ge k_0). ∣ e k + 1 ∣ = ∣ ψ ( e k ) ∣ ≤ C ∣ e k ∣ r ( k ≥ k 0 ) . :::`
Then ψ ( j ) ( 0 ) = 0 \psi^{(j)}(0)=0 ψ ( j ) ( 0 ) = 0 1 ≤ j ≤ b 1\le j\le b 1 ≤ j ≤ b C 1 , δ > 0 C_1,\delta>0 C 1 , δ > 0
∣ ψ ( e ) ∣ ≤ C 1 ∣ e ∣ b + 1 ( ∣ e ∣ < δ ) . |\psi(e)|\le C_1|e|^{b+1}\qquad(|e|<\delta). ∣ ψ ( e ) ∣ ≤ C 1 ∣ e ∣ b + 1 ( ∣ e ∣ < δ ) . Proof. Suppose some derivative of order between one and b b b m m m
ψ ( e ) = c m e m + o ( ∣ e ∣ m ) , c m = ψ ( m ) ( 0 ) m ! ≠ 0. \psi(e)=c_m e^m+o(|e|^m),\qquad c_m=\frac{\psi^{(m)}(0)}{m!}\ne0. ψ ( e ) = c m e m + o ( ∣ e ∣ m ) , c m = m ! ψ ( m ) ( 0 ) = 0. Since e k ≠ 0 e_k\ne0 e k = 0 e k → 0 e_k\to0 e k → 0
∣ ψ ( e k ) ∣ ∣ e k ∣ m ⟶ ∣ c m ∣ > 0. \frac{|\psi(e_k)|}{|e_k|^m}\longrightarrow|c_m|>0. ∣ e k ∣ m ∣ ψ ( e k ) ∣ ⟶ ∣ c m ∣ > 0. Consequently, for all sufficiently large k k k
∣ ψ ( e k ) ∣ ∣ e k ∣ r ≥ ∣ c m ∣ 2 ∣ e k ∣ m − r ⟶ + ∞ , \frac{|\psi(e_k)|}{|e_k|^r}\ge\frac{|c_m|}{2}|e_k|^{m-r}\longrightarrow+\infty, ∣ e k ∣ r ∣ ψ ( e k ) ∣ ≥ 2 ∣ c m ∣ ∣ e k ∣ m − r ⟶ + ∞ , since m ≤ b < r m\le b<r m ≤ b < r
Choose δ > 0 \delta>0 δ > 0 ψ \psi ψ C b + 1 C^{b+1} C b + 1 [ − δ , δ ] [-\delta,\delta] [ − δ , δ ]
M = max ∣ u ∣ ≤ δ ∣ ψ ( b + 1 ) ( u ) ∣ . M=\max_{|u|\le\delta}|\psi^{(b+1)}(u)|. M = ∣ u ∣ ≤ δ max ∣ ψ ( b + 1 ) ( u ) ∣. Taylor’s formula with integral remainder, valid for both signs of e e e
ψ ( e ) = e b + 1 b ! ∫ 0 1 ( 1 − s ) b ψ ( b + 1 ) ( s e ) d s . \psi(e)=\frac{e^{b+1}}{b!}\int_0^1(1-s)^b\psi^{(b+1)}(se)\,\mathrm{d}s. ψ ( e ) = b ! e b + 1 ∫ 0 1 ( 1 − s ) b ψ ( b + 1 ) ( se ) d s . Thus, ∣ ψ ( e ) ∣ ≤ M ∣ e ∣ b + 1 / ( b + 1 ) ! |\psi(e)|\le M|e|^{b+1}/(b+1)! ∣ ψ ( e ) ∣ ≤ M ∣ e ∣ b + 1 / ( b + 1 )! C 1 = 1 + M / ( b + 1 ) ! C_1=1+M/(b+1)! C 1 = 1 + M / ( b + 1 )!
Transfer of trajectory order on an invariant axis
The simulation of Theorem 3.2 reproduces the first component of one cycle. If its output does not belong to the first axis, iterating the scalar method amounts to resetting the other coordinates to zero. Therefore, this simulation does not automatically reproduce the vector trajectories. The following hypothesis avoids this difficulty.
Theorem 12.7 (Q Q Q M \mathcal{M} M ( N F , N J ) (N_F,N_J) ( N F , N J ) H n ( I 0 ) \mathcal{H}_n(I_0) H n ( I 0 ) d = N F + N J ≥ 1 d=N_F+N_J\ge1 d = N F + N J ≥ 1 b = 2 d − 1 b=2^{d-1} b = 2 d − 1 N F ≥ 1 N_F\ge1 N F ≥ 1 b = B ( N F , N J ) b=B(N_F,N_J) b = B ( N F , N J )
For each f ∈ E ∗ f\in\mathcal{E}_* f ∈ E ∗ a = a f a=a_f a = a f T f T_f T f f f f
(i) The test axis is invariant for the outputs:
M G f ( ι ( s ) ) = ι ( T f ( s ) ) for 0 < ∣ s − a ∣ sufficiently small . \mathcal{M}G_f(\iota(s))=\iota(T_f(s))\qquad\text{for }0<|s-a|\text{ sufficiently small}. M G f ( ι ( s )) = ι ( T f ( s )) for 0 < ∣ s − a ∣ sufficiently small . (ii) The operator ψ f ( e ) = T f ( a + e ) − a \psi_f(e)=T_f(a+e)-a ψ f ( e ) = T f ( a + e ) − a C b + 1 C^{b+1} C b + 1 ψ f ( 0 ) = 0 \psi_f(0)=0 ψ f ( 0 ) = 0
(iii) There is a common number p > 1 p>1 p > 1 f f f T f ( s ) = a T_f(s)=a T f ( s ) = a a a a ι ( a ) \iota(a) ι ( a ) Q Q Q p f ≥ p p_f\ge p p f ≥ p
Then p ≤ b p \le b p ≤ b
Proof. Suppose p > b p > b p > b f ∈ E ∗ f \in\mathcal{E}_* f ∈ E ∗ T f ( s ) = a T_f(s) = a T f ( s ) = a ∣ T f ( a + e ) − a ∣ ≤ ∣ e ∣ b + 1 \lvert T_f(a+e)-a\rvert\le\lvert e\rvert^{b+1} ∣ T f ( a + e ) − a ∣ ≤ ∣ e ∣ b + 1 X k = ι ( a + e k ) X_k=\iota(a+e_k) X k = ι ( a + e k )
e k + 1 = ψ f ( e k ) , ∥ X k − ι ( a ) ∥ ∞ = ∣ e k ∣ . e_{k+1}=\psi_f(e_k), \qquad\lVert X_k-\iota(a)\rVert_\infty=\lvert e_k\rvert. e k + 1 = ψ f ( e k ) , ∥ X k − ι ( a ) ∥ ∞ = ∣ e k ∣ . The exact Q Q Q p f p_f p f p f ≥ p > b p_f \ge p > b p f ≥ p > b
∣ T f ( a + e ) − a ∣ ≤ C f ∣ e ∣ b + 1 \lvert T_f(a+e)-a\rvert\le C_f\lvert e\rvert^{b+1} ∣ T f ( a + e ) − a ∣ ≤ C f ∣ e ∣ b + 1 in a neighborhood of zero. Thus this estimate holds for every f f f f f f
We apply Theorem 4.2, or Theorem 9.1 in the paired case. We obtain a fixed field G f ∗ G_{f_*} G f ∗ α ∗ = ι ( a ∗ ) \alpha_*=\iota(a_*) α ∗ = ι ( a ∗ ) X m = ι ( s m ) X_m=\iota(s_m) X m = ι ( s m ) b + 1 b+1 b + 1 m m m
∥ M G f ∗ ( X m ) − α ∗ ∥ ∞ = ∣ T f ∗ ( s m ) − a ∗ ∣ ≤ C f ∗ ∣ s m − a ∗ ∣ b + 1 = C f ∗ ∥ X m − α ∗ ∥ ∞ b + 1 . \left\lVert\mathcal{M}_{G_{f_*}}(X_m)-\alpha_*\right\rVert_\infty
=\lvert T_{f_*}(s_m)-a_*\rvert
\le C_{f_*}\lvert s_m-a_*\rvert^{b+1}
=C_{f_*}\lVert X_m-\alpha_*\rVert_\infty^{b+1}. M G f ∗ ( X m ) − α ∗ ∞ = ∣ T f ∗ ( s m ) − a ∗ ∣ ≤ C f ∗ ∣ s m − a ∗ ∣ b + 1 = C f ∗ ∥ X m − α ∗ ∥ ∞ b + 1 . The contradiction proves p ≤ b p \le b p ≤ b
Remark 12.8. The invariance hypothesis concerns only the outputs on the test family. It does not require that internal nodes remain on the axis. For n = 1 n=1 n = 1 Q Q Q n > 1 n>1 n > 1 G f G_f G f G f G_f G f ψ f \psi_f ψ f
The alternative T f ( s ) = a T_f(s)=a T f ( s ) = a
A sufficient vector condition without axis invariance
Let E E E C b + 1 C^{b+1} C b + 1 E ( 0 ) = 0 E(0)=0 E ( 0 ) = 0 1 ≤ j ≤ b 1 \le j \le b 1 ≤ j ≤ b
P j ( e ) = 1 j ! D j E ( 0 ) [ e , … , e ] . P_j(e)=\frac{1}{j!}D^jE(0)[e,\ldots,e]. P j ( e ) = j ! 1 D j E ( 0 ) [ e , … , e ] . Here D j E ( 0 ) D^jE(0) D j E ( 0 ) j j j b b b nondegenerate in directions if, for the smallest m ≤ b m \le b m ≤ b P m ≢ 0 P_m \not\equiv0 P m ≡ 0
P m ( v ) ≠ 0 for every v ≠ 0. P_m(v)\ne0 \qquad\text{for every }v\ne0. P m ( v ) = 0 for every v = 0. If all P j P_j P j
Lemma 12.9 (A trajectory and a nondegenerate leading term). Let b ∈ N b \in\mathbb{N} b ∈ N E E E e k → 0 e_k \to0 e k → 0 r > b r>b r > b P j P_j P j 1 ≤ j ≤ b 1 \le j \le b 1 ≤ j ≤ b
∥ E ( e ) ∥ ∞ = O ( ∥ e ∥ ∞ b + 1 ) ( e → 0 ) . \lVert E(e)\rVert_\infty=O\left(\lVert e\rVert_\infty^{b+1}\right)
\qquad(e\to0). ∥ E ( e ) ∥ ∞ = O ( ∥ e ∥ ∞ b + 1 ) ( e → 0 ) . Proof. If there is a first nonzero P m P_m P m
c = min ∥ v ∥ ∞ = 1 ∥ P m ( v ) ∥ ∞ > 0. c=\min_{\lVert v\rVert_\infty=1}\lVert P_m(v)\rVert_\infty>0. c = ∥ v ∥ ∞ = 1 min ∥ P m ( v ) ∥ ∞ > 0. By Taylor’s formula and homogeneity,
E ( e ) = P m ( e ) + o ( ∥ e ∥ ∞ m ) , ∥ P m ( e ) ∥ ∞ ≥ c ∥ e ∥ ∞ m . E(e)=P_m(e)+o(\lVert e\rVert_\infty^m),\qquad\lVert P_m(e)\rVert_\infty\ge c\lVert e\rVert_\infty^m. E ( e ) = P m ( e ) + o (∥ e ∥ ∞ m ) , ∥ P m ( e ) ∥ ∞ ≥ c ∥ e ∥ ∞ m . Thus ∥ E ( e ) ∥ ∞ ≥ ( c / 2 ) ∥ e ∥ ∞ m \lVert E(e)\rVert_\infty\ge(c/2)\lVert e\rVert_\infty^m ∥ E ( e ) ∥ ∞ ≥ ( c /2 ) ∥ e ∥ ∞ m e ≠ 0 e\ne0 e = 0
∥ e k + 1 ∥ ∞ ∥ e k ∥ ∞ r ≥ c 2 ∥ e k ∥ ∞ m − r ⟶ + ∞ , \frac{\lVert e_{k+1}\rVert_\infty}{\lVert e_k\rVert_\infty^r}\ge\frac{c}{2}\lVert e_k\rVert_\infty^{m-r}\longrightarrow+\infty, ∥ e k ∥ ∞ r ∥ e k + 1 ∥ ∞ ≥ 2 c ∥ e k ∥ ∞ m − r ⟶ + ∞ , which contradicts the trajectory estimate. Therefore all homogeneous polynomials up to degree b b b
For each small e e e s ↦ E ( s e ) s\mapsto E(se) s ↦ E ( se ) [ 0 , 1 ] [0,1] [ 0 , 1 ]
E ( e ) = 1 b ! ∫ 0 1 ( 1 − s ) b D b + 1 E ( s e ) [ e , … , e ] d s . E(e)=\frac{1}{b!}\int_0^1(1-s)^bD^{b+1}E(se)[e,\ldots,e]\,\mathrm{d}s. E ( e ) = b ! 1 ∫ 0 1 ( 1 − s ) b D b + 1 E ( se ) [ e , … , e ] d s . On a sufficiently small closed ball, continuity provides a bound M M M D b + 1 E D^{b+1}E D b + 1 E
∥ E ( e ) ∥ ∞ ≤ M ( b + 1 ) ! ∥ e ∥ ∞ b + 1 . \lVert E(e)\rVert_\infty\le\frac{M}{(b+1)!}\lVert e\rVert_\infty^{b+1}. ∥ E ( e ) ∥ ∞ ≤ ( b + 1 )! M ∥ e ∥ ∞ b + 1 . This proves the assertion.
Corollary 12.10 (Q Q Q b b b Theorem 12.7 , without requiring axis invariance. Suppose that, for every problem in H n ( I 0 ) \mathcal{H}_n(I_0) H n ( I 0 ) C b + 1 C^{b+1} C b + 1 b b b
Suppose moreover that there exists p > 1 p>1 p > 1 Q Q Q p F ≥ p p_F\ge p p F ≥ p p ≤ b p\le b p ≤ b
Proof. If p > b p>b p > b Lemma 12.9 , with r = p F r=p_F r = p F b + 1 b+1 b + 1 b + 1 b+1 b + 1 H n ( I 0 ) \mathcal{H}_n(I_0) H n ( I 0 ) Corollary 4.3 or Theorem 9.1 , according to the choice of b b b
Conclusions
We have proved the bound conjectured by Cordero–Torregrosa for the universal local order of iterative methods applied to systems of nonlinear equations. Our result establishes that
p ≤ 2 N F + N J − 1 , p \leq2^{N_F+N_J-1}, p ≤ 2 N F + N J − 1 , without needing to suppose that the number of Jacobian evaluations is less than or equal to the number of function evaluations. In particular, the inequality is also valid when N J > N F N_J > N_F N J > N F
We have also proved that the distribution of evaluations can impose a stronger restriction on the order of convergence. When every Jacobian evaluation is performed at a point where the function has previously been evaluated, we obtain
p ≤ 2 N F − s + 1 3 s − 1 , s = min { N F , N J } . p \leq2^{N_F-s+1}3^{s-1}, \qquad s = \min\{N_F,N_J\}. p ≤ 2 N F − s + 1 3 s − 1 , s = min { N F , N J } . This inequality strictly improves the general bound when N J > 1 N_J > 1 N J > 1
The preceding results show that limitations on the order of convergence depend not only on the total number of evaluations, but also on how the information is obtained. This leads us to propose a new conjecture relating the order to a more precise distribution of function and Jacobian evaluations. In particular, we propose the product bound
p ≤ ( q + 2 ) N J − r ( q + 3 ) r , N F − 1 = q N J + r , 0 ≤ r < N J , p \leq(q+2)^{N_J-r}(q+3)^r, \qquad N_F-1=qN_J+r,\quad0\leq r<N_J, p ≤ ( q + 2 ) N J − r ( q + 3 ) r , N F − 1 = q N J + r , 0 ≤ r < N J , for sufficiently broad vector classes and under the dimensional condition n ≥ N F + N J − 1 n \geq N_F+N_J-1 n ≥ N F + N J − 1
Finally, we must recall that the barriers obtained concern the universal local order of one iteration, not the order that a method may attain on a particular system. We have also studied the relationship between this order and the Q Q Q
References 