Approximation and complexity II: iterated integration

Dima Grigoriev^{∗}

Abstract

We introduce two classes of real analytic functions W ⊂ U on an interval. Starting with rational functions, for constructing functions from W we allow applying two types of operations: integrating and multiplying by a polynomial with rational coefficients. In a similar way, for constructing functions from U we allow integrating and additions and multiplications of already constructed functions from U and multiplications by rational numbers. Thus, U is a subring of the ring of Pfaffian functions [Kh].

Two lower bounds are proved on a function f from W (or from U, respectively) in terms of the complexity of constructing of f.

Introduction

The well-known Liouvillean theorem states that if

p(a) = 0, a ≠ 0, p = ∑_{0≤i≤m} p_{i}X^{i}, p_{i} ∈ Z then one can bound from below the absolute value |a| of the algebraic number a in terms of the complexity of the determining polynomial p.

The question arises whether this phenomenon could be extended to solutions v of (ordinary) differential equations Q(v) = 0? It is known [B] that in general one can’t bound v if to consider non-linear second-order (or higher) equations Q(v) = 0. Thus, one ought to allow to solve either linear or first-order equations.

∗IRMAR, Université de Rennes, Campus de Beaulieu, 35042 Rennes, cedex France

In the present paper we introduce two classes of real analytic functions W ⊂ U on a finite interval I. In both cases we start with rational functions with rational coefficients. To construct functions from W we allow to apply two types of operations: integration and multiplication by a polynomial from Q[X]. Thereby, W is a differential Q[X]-module. While for constructing functions from U we allow to apply integration and substitute already constructed functions from U into a (multivariate) polynomial with rational coefficients. Thereby, U is a differential Q[X]-algebra. Clearly, U is a subring of the ring of Pfaffian functions [Kh].

Thus, each function f from W (or from U, respectively) is constructed by means of a chain of operations (which involve arithmetic and integrating) and one can define the “complexity” of f as the complexity of a corresponding chain.

In section 1 below we prove (theorem 1) a lower bound on the norm max_{x∈I} |f(x)| for f ∈ W in terms of I and of the complexity of the corresponding chain for f. Moreover, we provide an upper bound on the number of roots of f (lemma 1) being better than the bound from [Kh] established for the wider class of Pfaffian functions.

In section 2 we prove (theorem 2) a lower bound on max_{x∈I} |f(x)| for f ∈ U again in terms of I and of the complexity of the chain for f under the assumption that in the chain each application of the integration introduces a function being transcendental with respect to the previously constructed functions in the chain. This assumption of purely transcendental chains allows one to avoid introducing in a chain arbitrarily small constants (otherwise, no lower bound would be possible).

Thus, in constructing of U (and of W) we allow to integrate. It seems that if we allowed to solve more general types of first-order differential equations (as e.g., in case of Pfaffian functions [Kh]) then the results of a similar sort to ones in the present paper would fail, again because solving such equations would allow to introduce arbitrarily small constants in a chain.

In [G01] the similar results were established for solutions of linear differential equations on an interval.

The picture becomes somewhat easier if instead of approximating on an interval to study asymptotic approximations on the real line (at infinity) since then introducing small constants does not disturb. In this setting a lower bound on approximations in terms of the complexity for a wider than in the present paper class of Pfaffian functions was obtained in [G93]. Besides, a lower bound for a wider than in [G01] class of compositions of solutions of linear differential equations was established in [G92].

One could also view the results of the paper as a trade-off between approximations and the complexity. It would be interesting to understand more on this trade-off. We mention that in this direction a lower bound was proved in [CG] on the complexity of approximating algebraic computation trees.

It is worthwhile also to mention that in [K] a version of a differential analog of the Liouville’s theorem was proposed in terms of bounds on valuations, while we study approximations in L_{∞}-norm.

1 Functions of linear-iterated integration

Denote by I ⊂ R a finite interval of the length |I| such that

I ⊂ [−b, b], b ≥ 1  (1)

and for a function g on I consider the norm ||g||_{I} = max_{x∈I} |g(x)|.

Let q_{0}, …, q_{t} be real analytic functions on I, moreover q_{0} ∈ R(X).We say that q_{0}, …, q_{t} constitute (t, d)-chain of linear-iterated integration if for each 0 ≤ i ≤ t − 1 for appropriate polynomials p_{0,i}, …, p_{i,i} ∈ R[X] of degrees deg(p_{0,i}), …, deg(p_{i,i}) ≤ d, we have for the derivative

qi+1^{′} = p_{0,i}q_{0} + ⋯ + p_{i,i}q_{i}  (2)

In such a case we say sometimes simply that q_{t} satisfies (t, d)-chain. Clearly, a (t, d)-chain is a particular case of a Pfaffian chain [Kh] and thereby, q_{t} is a Pfaffian function.

First we prove an upper bound on the number #(g) of the roots of g in I (in fact, this would give the same bound on the number of the roots on the whole real line, provided that the functions {q_{i}}_{0≤i≤t}, g were analytic on the whole real line as well). We note that this bound is stronger (being polynomial rather than exponential) than the bound [Kh] which is valid for the wider class of Pfaffian functions.

Lemma 1 Let

g = ∑_{0≤j≤t} v_{j,1}q_{j,1} + ⋯ + ∑_{0≤j≤t} v_{j,N}q_{j,N}  (3)

where for every 1 ≤ l ≤ N the functions q_{0,l}, …, q_{t,l} form (t, d)-chain, here the polynomials v_{j,l} ∈ R[X], deg(v_{j,l}) ≤ d. Then #(g) ≤ O(Nt^{2}d^{2}), provided that g ≢ 0.

Proof. We express the rational function q_{0,l} = q̂_{0,l}/\overline{q_{0,l}} where the numerator and the denominator q̂_{0,l}, \overline{q_{0,l}} have the degrees deg(q̂_{0,l}), deg(\overline{q_{0,l}}) ≤ d.

By induction on s = 1, …, t denoting S = (d+1)+(2d+1)+⋯+(sd+1) one can represent the derivative

g^{(S)} = ∑_{1≤j≤t−s} v_{j,1,s}q_{j,1} + q_{0,1,s} + ⋯ + ∑_{1≤j≤t−s} v_{j,N,s}q_{j,N} + q_{0,N,s}

for suitable v_{j,l,s} ∈ R[X], q_{0,l,s} = q̃_{l,s}/(\overline{q_{0,l}})^{S} where

deg(v_{j,l,s}) ≤ min{Sd, (t − j + 1)d}, deg(q̃_{l,s}) ≤ O((sd)^{2}),

see (2).

Finally, putting s = t, T = (d + 1) + (2d + 1) + ⋯ + (td + 1) we get that g^{(T)} ∈ R(X) and taking into account the Rolle’s theorem #(g) ≤ #(g^{(T)})+T when g^{(T)} ≢ 0 or otherwise we have #(g) ≤ T − 1, we conclude with the lemma. □.

From now on we assume that the functions q_{0} ∈ Q(X), p_{0,i}, …, p_{i,i} ∈ Q[X] determining a chain, have rational coefficients. When q_{0} = q̂_{0}/\overline{q_{0}} where q̂_{0}, \overline{q_{0}} ∈ Z[X] one says that the height h(q_{0}) ≤ h if the absolute values of all the integer coefficients of q̂_{0}, \overline{q_{0}} do not exceed h. Thus, we say that a (t, d)-chain q_{0}, …, q_{t} is (t, d, h)-chain if

h(q_{0}), h(p_{j,i}) ≤ h, 0 ≤ i ≤ t − 1, 0 ≤ j ≤ i  (4)

Denote by W_{t} the Q[X]-module generated by functions satisfying (t, \overline{d}, \overline{h})- chains for all possible \overline{d}, \overline{h} ≥ 0. Evidently, W_{0} = Q(X).

Using (2), (4) one can by induction on s estimate

h(v_{j,l,s}), h(q_{0,l,s}) ≤ (hsd)^{O((s^{2}+t)d^{2})}

Therefore, at the end of induction one gets

g^{(T)} ∈ Q(X), h(g^{(T)}) ≤ (htd)^{O(t^{2}d^{2}N)}

.

Let us suppose that g^{(T)} ≢ 0. Due to lemma 1 there exists a subinterval

I_{0} ⊂ I, |I_{0}| = \frac{|I|}{O(Nt^{2}d^{2})}  (5)

which contains no roots of the derivatives g, g^{(1)}, …, g^{(T +1)} (in case when g^{(T +1)} ≡ 0 we require instead that g, g^{(1)}, …, g^{(T)} have no roots in I_{0}).

Let us recall lemma 2 from [G01].

Lemma 2 Assume that the derivatives g, g^{(1)}, …, g^{(T +1)} have no roots in I_{0} (in case when g^{(T +1)} ≡ 0 we require that g, g^{(1)}, …, g^{(T)} have no roots in I_{0}). Then there exists a subinterval I_{T} ⊂ I_{0} of the length |I_{T} | = \frac{|I_{0}|}{T +1} such that

||g^{(j)}||_{I_{T}} ≤ ||g||_{I_{0}} (\frac{T + 1}{|I_{0}|})^{j} , 0 ≤ j ≤ T

We represent g^{(T)} = f_{1}/f_{2} for f_{1}, f_{2} ∈ Z[X] such that h(f_{1}), h(f_{2}) ≤ h(g^{(T)}). There exists a rational point a = a_{1}/a_{2} ∈ I_{T} , a_{2} > 0, a_{1}, a_{2} ∈ Z such that

a_{2} ≤ max\{1, |I_{T} |^{−1}\} ≤ max\{1, \frac{O(T Nt^{2}d^{2})}{|I|}\}

(due to (5) and lemma 2). Then

|f_{2}(a)| ≤ ||f_{2}||_{I_{T}} ≤ (htdb)^{O(Nt^{2}d^{2})}

(see (1), (2), (3), (4)) and

|f_{1}(a)| ≥ min{1, a_{2}^{−O(Nt^{2}d^{2})}}

(see (2), (3)). Lemma 2 implies that

||g||_{I_{T}} max\{1, (\frac{O(T Nt^{2}d^{2})}{|I|})^{T} \} ≥ ||g^{(T)}||_{I_{T}} ≥ |g^{(T)}(a)| ≥

(hNtdb)^{−O(Nt^{2}d^{2})} min\{1, (\frac{|I|}{O(T Nt^{2}d^{2})})^{O(Nt^{2}d^{2})}\}

This entails the following theorem.

Theorem 1 Assume that g satisfies (t, d, h)-chain on an interval I ⊂ [−b, b], the conditions (1), (2), (3), (4) and g^{(T)} ≢ 0. Then

||g||_{I} ≥ (hNtdb)^{−O(Nt^{2}d^{2})} min{1, |I|^{O(Nt^{2}d^{2})}}

We note that without any condition on the derivatives of g the lower bound in theorem 1 would fail since e.g., when t = 1, g = g_{1} and an equation g1^{′} = 0 as a chain, one could take as g an arbitrarily small constant.

2 Functions of iterated integration

Now we consider an extension of the class of functions W_{t} from the previous section. We define a sequence of analytic on I real functions {g_{i}}_{1≤i≤t}, g of iterated integration by recursion on i. Namely,

gi^{′} = p_{i}(X, g_{1}, …, g_{i−1}), g = p_{t+1}(X, g_{1}, …, g_{t})  (6)

where the rational functions p_{i} ∈ Q(X)[Y_{1}, …, Y_{i−1}], 1 ≤ i ≤ t + 1. In other words, one is allowed, in particular, to integrate at a current step the product of functions produced at previous steps. Clearly, the produced ring U_{t} of all functions of the form g contains W_{t}, and on the other hand being a subring of the ring of Pfaffian function [Kh].

Any rational function p ∈ Q(X)[Y_{1}, …, Y_{t}] we write in a form p̂/\overline{p} where the polynomials p̂ ∈ Z[X, Y_{1}, …, Y_{t}], \overline{p} ∈ Z[X] are reciprocately prime. We assume that

deg(p_{i}) = max\{deg(p̂_{i}), deg(\overline{p_{i}})\} ≤ d, h(p_{i}) = max\{h(p̂_{i}), h(\overline{p_{i}})\} ≤ h, (7)

1 ≤ i ≤ t + 1.

Also we suppose that

||g_{i}||_{I} ≤ M, 1 ≤ i ≤ t, M ≥ 1  (8)

and that each complex root of the denominator \overline{p_{i}} lies on a distance at least 1 from the interval I, 1 ≤ i ≤ t + 1, hence

|\overline{p_{i}}| is greater or equal to 1 everywhere on I  (9)

We observe that the latter conditions provide the upper bounds on the functions involved in the computations with the sequence, and one could interpret the theorem in this section as a lower bound on the functions of iterated integration by means of their upper bounds.

We make an assumption that the sequence {g_{i}}_{1≤i≤t} (see (6)) is purely transcendental, i.e. g_{i+1} is algebraically independent over the field F_{i} = R(X, g_{1}, …, g_{i}) for all 0 ≤ i < t. We note that F_{i} is a differential field. The condition of {g_{i}}_{1≤i≤t} being purely transcendental is similar to the condition in the algorithm due to Risch [R] and allows one to avoid introducing in a sequence (6) functions being arbitrarily small constants which would prevent from lower bounds on the functions of iterated integration on I.

The following lemma enables us to eliminate a transcendental integral.

Lemma 3 Let F be a differential field and u being algebraically independent over F such that its derivative u′ ∈ F, provided that F (u) has the same subfield of constants as F has. Consider g = p(u) ∈ F [u], deg_{u}(p) = n and denote the polynomials p_{i}(u) ∈ F [u] to be such that the derivative g^{(i)} = p_{i}(u) for i ≥ 0. Then gcd(p, p_{1}, …, p_{n}) ∈ F.

Proof. We argue by induction on n. The base of induction is evident. For the inductive step consider the leading term of p = wu^{n} + ⋯ where w ∈ F. First, f ≡ w′g − wg′ ≠ 0 since otherwise g = cw for a certain constant c and thereby, u is algebraic over F. Denote the derivatives f^{(i)} = r_{i}(u) ∈ F [u], i ≥ 0. Obviously, deg_{u}(r_{0}) < deg(p_{0}) = n and deg(r_{i}) ≤ deg(r_{0}), i ≥ 0. On the other hand,

f^{(i)} = ∑_{0≤j≤i} \binom{i}{j}(w^{(i+1)}g^{(i−j)} − w^{(i−j)}g^{(j+1)}), i ≥ 0,

therefore gcd(p_{0}, …, p_{n}) divides gcd(r_{0}, …, r_{n−1}) in the polynomial ring F [u]. This implies the inductive step since gcd(r_{0}, …, r_{n−1}) ∈ F by the inductive hypothesis. □.

Observe that the condition of conserving the subfield of constants will be fulfilled in our situation because we consider the functions on the interval I and the subfield coincides just with R.

In course of the procedure described below a certain family Δ ⊂ U_{t} of functions is constructed. Later on we bound from above the total number N_{0} of the roots of the functions from Δ and now we fix a subinterval J ⊂ I of the length |J| = |I|/(N_{0} + 1) which does not contain any such root.

At the first step we represent the function g = q(g_{t}) where the coefficients of the (univariate) polynomial q belong to the (differential) ring K_{t−1} = Q(X)[g_{1}, …, g_{t−1}] ⊂ F_{t−1}. Then g^{(i)} = q_{i}(g_{t}) for suitable polynomials q_{i}(g_{t}) ∈ K_{t} = K_{t−1}[g_{t}], 0 ≤ i ≤ d. Consider G = gcd(q, q_{1}, …, q_{d}) in the ring Q(X, g_{1}, …, g_{t−1})[g_{t}] being defined up to a factor from Q_{t−1} = Q(X, g_{1}, …, g_{t−1}). Then G belongs to F_{t−1} = R(Q_{t−1}) according to lemma 3, in other words, deg_{g_{t}}(G) = 0, therefore, G ∈ Q_{t−1} since gcd does not change when the field of the coefficients being extended Q_{t−1} ⊂ F_{t−1}.

The subresultant theorem (see e.g., [L]) states that one can choose G in such a way that

G = A_{0}q + A_{1}q_{1} + … + A_{d}q_{d} ∈ K_{t−1}  (10)

where the coefficients of the (univariate) polynomials A_{0}, …, A_{d} ∈ K_{t−1}[g_{t}] are appropriate subminors of the Sylvester matrix A of the family of the (univariate) polynomials q, q_{1}, …, q_{d}. More precisely, the usual Sylvester matrix is atributed to a pair of polynomials, but one can directly extend it to a family of polynomials (see [G90]).

The size of the matrix A is bounded by O(deg(q) + deg(q_{1}) + … + deg(q_{d})) ≤ O(d^{2}) (see [L], [G90]). Each entry of A written as a certain function r(X, g_{1}, …, g_{t−1}) ∈ K_{t−1} can be bounded as follows: deg(r) ≤ O(d^{2}), h(r) ≤ (hd)^{O(d)} (see (7)). Therefore,

deg(A_{i}) ≤ O(d^{4}), h(A_{i}) ≤ d^{O(d^{4}+t)}h^{O(d^{3})}, ||A_{i}||_{I} ≤ d^{O(d^{4}+t)}h^{O(d^{3})}M^{O(d^{4})}

(the latter inequality invokes (8), (9)). Hence deg(G) ≤ O(d^{4}), h(G) ≤ d^{O(d^{4}+t)}h^{O(d^{3})}.

Lemma 2 implies that there exists a subinterval J_{1} ⊂ J, |J_{1}| = |J|/(d + 1) such that

||g^{(j)}||_{J_{1}} ≤ ||g||_{J} (\frac{d + 1}{|J|})^{j} , 0 ≤ j ≤ d

. We include the functions g, g^{(1)}, …, g^{(d)} into the family Δ and thereby, impose the condition that g, g^{(1)}, …, g^{(d)} have no roots in J (cf. the discussion on Δ, J above). Due to that and to (10) we get

||G||_{J_{1}} ≤ ||g||_{J} max\{1, (\frac{d + 1}{|J|})^{d}\}d^{O(d^{4}+t)}h^{O(d^{3})}M^{O(d^{4})}  (11)

Thus, we have carried out one step of the procedure, constructed G and thereby, eliminated g_{t}.

After t such steps we achieve by recursion a rational function L ∈ Q(X) and nested subintervals J ⊃ J_{1} ⊃ … ⊃ J_{t} such that

deg(L) ≤ d^{4^{t}}, h(L) ≤ h^{d^{5^{t}}}, |J_{t}| ≥ \frac{|J|}{d^{5^{t}}}, ||L||_{J_{t}} ≤ ||g||_{J}(Mh)^{d^{6^{t}}} max\{1, |J|^{−d^{5^{t}}}\}

(because of (11)).

The family Δ consists of O(d^{4^{t}}) functions each having at most d^{O(4^{t})} roots (on I) due to [Kh] since one can view (6) as a Pfaffian chain, therefore, the total number N_{0} of roots of the functions from Δ does not exceed d^{O(4^{t})}, hence

|J| ≥ \frac{|I|}{d^{O(4^{t})}} ,

finally

||L||_{J_{t}} ≤ ||g||_{I}(Mh)^{O(d^{6^{t}})} max{1, |I|^{−d^{5^{t}}}}

(see (11)).

Similar to the end of section 1 there exists a rational point

a = a_{1}/a_{2} ∈ J_{t}, a_{1}, a_{2} ∈ Z, 0 < a_{2} ≤ max{1, |J_{t}|^{−1}}.

In a similar way we represent L = L_{1}/L_{2}, L_{1}, L_{2} ∈ Z[X] and we get

|L_{1}(a)| ≥ a_{2}^{− deg(L_{1})} ≥ min\{1, (\frac{|I|}{d^{5^{t}}} )^{O(d^{4^{t}})}\},

|L_{2}(a)| ≤ h(L_{2}) deg(L_{2})b^{deg(L_{2})} ≤ h^{d^{5^{t}}}b^{d^{4^{t}}}

(see (1), (7)). As |L_{1}(a)/L_{2}(a)| ≤ ||L||_{J_{t}} we conclude that

||g||_{I} ≥ (Mh)^{−d^{6^{t}}}b^{−d^{4^{t}}} min{1, |I|^{d^{5^{t}}}}

taking into account (11). Thus, the following theorem is proved.

Theorem 2 If g satisfies a purely transcendental iterated integration sequence (6) and the bounds (1), (7), (8), (9), then

||g||_{I} ≥ (Mhb)^{−O(d^{6^{t}})} min{1, |I|^{d^{5^{t}}}}

In conclusion let us formulate a conjecture that an upper bound on the number of roots of a function from the class U_{t} should be better than the one from [Kh].

References

[B] R.Bellman. Stability theory of differential equations, McGraw-Hill, 1953.

[CG] F.Cucker, D.Grigoriev. Complexity lower bounds for approximation algebraic computation trees, J. Complexity, 1999, 15, 4, p. 499–512.

[G90] D.Grigoriev. Complexity of factoring and GCD calculating of ordinary linear differential operators, J.Symbolic Comput., 1990, 10, p. 7–37.

[G 92] D.Grigoriev. Deviation theorems for solutions of linear ordinary differential equations and applications to parallel complexity of sigmoids, St.Petersburg Math. J., 1995, 6, 1, p. 89–106.

[G 93] D.Grigoriev, Deviation theorems for Pfaffian sigmoids, St.Petersburg Math. J., 1995, 6, 1, p. 107–112.

[G01] D.Grigoriev. Approximation and complexity: Liouvillean type theorems for linear differential equations on an interval, Foundations of Computational Mathematics, 2001, 1, p. 289–295.

[Kh] A.Khovanskii. Fewnomials. AMS Transl. Math. Monogr., 1991, 88.

[K] E.Kolchin. Rational approximations to solutions of algebraic differential equations. Proc. AMS, 1959, 10, p. 238–244.

[L] R.Loos. Generalized polynomial remainder sequences, in Computer Algebra, Springer, 1983, p. 115–138.

[R] R.Risch. The problem of integration in finite terms, Trans. AMS, 1970, 139.