Approximation and complexity: Liouvillean type theorems for linear differential equations

on an interval

Dima Grigoriev^{∗}

Abstract

Let u, v be solutions on an interval I of linear differential equations (LDE) P = 0, Q = 0, respectively. We obtain a lower bound on the approximation of v by u in terms of bounds on the coefficients of LDE S_{i} = 0 (for several i) satisfied by the i-th derivative of v and by the i-th derivatives of a basis of the LDE P = 0.

One could view this result as a differential analog of the Liouville’s theorem which states that two different algebraic numbers are well separated if they satisfy algebraic equations with small enough integer coefficients. Unlike the algebraic situation, in the differential setting, in order to bound from below the difference |u − v| we need to involve not only the coefficients of P, Q themselves, but also those of S_{i}.

Introduction

The well-known Liouville’s theorem states that if f(a) = g(b) = 0 where

f = ∑_{0≤i≤n} f_{i}X^{i}, g = ∑_{0≤i≤m} g_{i}X^{i} ∈ Z[X]

and a ≠ b then one can bound from below the difference |a − b|. For the sake of simplicity assume that f, g have no common roots. One possible approach to its proof is to consider the resultant

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

R = f_{n}^{m}g_{m}^{n} ∏(a_{i} − b_{j}) ∈ Z

where the product is taken over the roots a_{i} of f and b_{j} of g, respectively. Say, for definiteness a_{1} = a, b_{1} = b. Then

1 ≤ |R| = |f_{n}^{m}g_{m}^{n}(a_{1} − b_{1}) ∏_{(l,j)≠(1,1)}(a_{l} − b_{j})|

and from the upper bounds on the roots |a_{l}| ≤ max{1, |f_{i}/f_{n}|}, |b_{j}| ≤ max{1, |g_{i}/g_{m}|} one obtains a lower bound on |a_{1} − b_{1}|. Note that this argument provides a lower bound on |a_{l} − b_{j}| for any pair of the roots of f and g. We recall also that R = g_{m}^{n} ∏ f(b_{j}) and alternatively, one could obtain similar to above a lower bound on |f(b_{1})|. The proof of the Liouville’s theorem uses two basic ingredients: a lower bound on |R| and an upper bound on the roots |a_{i}|, |b_{j}|.

If one would try to transfer this argument to the solutions P (u) = Q(v) = 0 of linear ordinary differential operators

P = ∑_{0≤i≤n} p_{i} \frac{d^{i}}{dX^{i}} , Q = ∑_{0≤i≤m} q_{i} \frac{d^{i}}{dX^{i}}

one needs a replacement of the resultant.

Informally speaking, the approach can be viewed as follows. We have

∑_{0≤i≤n} p_{i} \frac{d^{i}}{dX^{i}} (u − v) = P (u − v) = −P (v).

In fact, P (v) plays a role of the resultant: it could be represented as the determinant of an appropriate (n + 1) × (n + 1) matrix with the last column formed by the derivatives \frac{d^{i}}{dX^{i}} (u − v), 0 ≤ i ≤ n and other entries being the derivatives of the elements of a basis u_{1}, …, u_{n} of the space of solutions of LDE P = 0. Assume that a certain lower bound on ||P (v)|| is given where ||, || denotes some norm, this replaces the first of the mentioned ingredients. We want to derive a contradiction from the supposition that ||u−v|| is small. For this purpose we have to guarantee that under the supposition the norms of the derivatives ||\frac{d^{i}}{dX^{i}} (u − v)||, 1 ≤ i ≤ n, should be small as well (it is an extra effort in comparison with the algebraic situation). Together with the upper bounds on the entries of the matrix which occur in the rate of approximation (this replaces the second of the mentioned ingredients), that leads to a contradiction by means of expanding P (v) with respect to its last column.

This plan is fulfilled in the theorem below which provides a lower bound on approximations max_{x∈I} |v − ∑_{1≤j≤n} λ_{j}u_{j}(x)| of a function v by means of any linear combination of the form ∑_{1≤j≤n} λ_{j}u_{j}, λ_{j} ∈ R, of functions u_{1}, …, u_{n} defined on a finite closed interval I ⊂ R. The bound depends on n which could be informally treated as a complexity measure of an approximation, having in mind that a function v is given and we try to minimize the number n of functions u_{1}, …, u_{n} taken from a fixed set of “basic” ones, for example, monomials, or trigonometric monomials sin(θX), or exponential monomials exp(θX) etc.

Let us underline that unlike the case of algebraic equations where the bound depends separately on both polynomials f and g, we consider approximations of a fixed solution of one operator by means of any solution of another operator, rather than the difference of any pair of solutions which could be arbitrary small on the interval, and the bound depends on suitable minors composed of the derivatives of v and of u_{1}, …, u_{n}.

As an application of the theorem we provide a lower bound for approximations by means of linear combinations of functions of the forms sin(θX), cos(θX).

Observe that it is more difficult to prove analogs of Liouvillean type theorems for solutions of linear differential equations on an interval than on the whole real line. Moreover, one can obtain lower bounds on approximations on R not only for solutions of LDE, but for their compositions [G 92] making use of a more general approach involving the Wronskian.

It is an interesting question whether one can prove Liouvillean type theorems for approximations on an interval for two classes of functions studied in [G 92], [G 93], respectively, namely, compositions of solutions of linear differential equations and Pfaffian functions [Kh] (or in other terms, for nested solutions of first-order non-linear differential equations). We mention also that beyond these two classes of functions one could hardly expect any Liouvillean type theorem due to the example (see [B]) of a second-order non-linear differential equation with arbitrarily closeness to zero.

One could also view the result of the paper as a trade-off between approximations and 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.

Another motivation for this trade-off arises from neural networks (see [MSS] and the references there) where one considers sigmoids (circuits with certain transcendental functions as gates), and the problem of approximating a sigmoid by another of small complexity.

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 consider approximations in L_{∞}-norm.

The author would like to take this opportunity to thank Georg Schnitger for stimulating discussions. Also the author is indebted to the anonymous referees whose remarks have conduced to improve the exposition.

Approximations of solutions of linear differential equations

Let I ⊂ R be a finite interval of length |I| and u_{1}, …, u_{n}, v be 2n + 2differentiable functions on I. We study the question of how well linear combinations of the form ∑_{1≤j≤n} λ_{j}u_{j} for λ_{j} ∈ R can approximate v, i.e. the problem of bounding from below the norm

||v − ∑_{1≤j≤n} λ_{j}u_{j}||_{I} = max |(v − ∑_{1≤j≤n} λ_{j}u_{j})(x)|

where the maximum of absolute values is taken over the points x from the closure of the interval I.

Consider (2n+3)×(n+1) matrix \overline{Δ} with the rows (respectively, columns) numbered from 0 to 2n + 2 (respectively, from 1 to n + 1) defined as follows. For 1 ≤ k ≤ n its k-th column is formed by the derivatives u_{k}, uk^{′}, …, u_{k}^{(2n+2)} and (n + 1)-th column is formed by the derivatives v, v′, …, v^{(2n+2)}. For 0 ≤ i ≤ n + 1, i ≤ j ≤ i + n + 1 let \overline{Δ}(i, ĵ) denote the (n + 1) × (n + 1) subdeterminant of \overline{Δ} formed by the rows i, i+1, …, j −1, j +1, …, i+n, i+ n + 1.

We assume the following bounds for any point x ∈ I:

|\overline{Δ}(i, ĵ)(x)| ≤ M, |\overline{Δ}(i, î + n + 1)(x)| ≥ δ > 0  (1)

for all 0 ≤ i ≤ n + 1, i ≤ j ≤ i + n + 1 and for certain fixed M, δ. Then the space of solutions of the LDE S_{i} = 0 where

S_{i} = ∑_{0≤j≤n+1}(−1)^{j}\overline{Δ}(i, ĵ + i)\frac{d^{j}}{dX^{j}} , 0 ≤ i ≤ n + 1

has a basis u_{1}^{(i)}, …, u_{n}^{(i)}, v^{(i)} due to the condition on δ in (1).

For 0 ≤ j ≤ n let Δ(ĵ) be the n×n subdeterminant of the first n columns of \overline{Δ} and the rows 0, 1, …, j − 1, j + 1, …, n. Then u_{1}, …, u_{n} is a basis of the space of solutions of the LDE S = 0 where

S = ∑_{0≤j≤n}(−1)^{j}Δ(ĵ)\frac{d^{j}}{dX^{j}} .

Assume that for any point x ∈ I we have

|Δ(ĵ)(x)| ≤ M_{0}, 0 ≤ j ≤ n  (2)

Theorem

||v − ∑_{1≤j≤n} λ_{j}u_{j}||_{I} ≥ \frac{δ}{(n + 1)M_{0}} (\frac{min\{|I|, δ/2M\}}{(n + 1)^{3}})^{n}  (3)

Remark. There exists a closed subinterval I_{n} ⊂ I (which depends on λ_{1}, …, λ_{n}) of length

|I_{n}| ≥ \frac{min\{|I|, δ/2M\}}{(n + 1)^{3}}

such that |(v − ∑_{1≤j≤n} λ_{j}u_{j})(x)| is greater than the right-hand side of (3) for any point x ∈ I_{n}.

The following lemma was proved as lemma 2 [G 92].

Lemma 1 For each 0 ≤ i ≤ n + 1 the number of roots on I of the derivative w^{(i)} = v^{(i)} − ∑_{1≤j≤n} λ_{j}u_{j}^{(i)}, does not exceed ⌈2M|I|/δ⌉n; moreover any subinterval of I of length less or equal to δ/2M contains at most n roots of w^{(i)}.

Proof. Suppose that a certain closed subinterval I′ ⊂ I of length |I′| ≤ δ/2M contains more than n roots of w^{(i)}. Then each of the derivatives w^{(i)}, w^{(i+1)}, …, w^{(i+n)} has a root in I′. Let M^{(j)} = ||w^{(i+j)}||_{I′}, 0 ≤ j ≤ n + 1. Then

M^{(j+1)} ≥ M^{(j)}/|I′| ≥ 2MM^{(j)}/δ, 0 ≤ j ≤ n

by the Mean Value Theorem.

On the other hand according to the Cramer’s rule we have the identity

w^{(i+n+1)}\overline{Δ}(i, î + n + 1) = ∑_{i≤j≤i+n}(−1)^{j−i−n}w^{(j)}\overline{Δ}(i, ĵ)

taking into the account that the minors \overline{Δ}(i, ĵ) do not change if to replace the (n + 1)-th column of the matrix \overline{Δ} by the derivatives w, w^{(1)}, …, w^{(2n+2)}, that corresponds to a linear elementary transformation of the columns of \overline{Δ}. Substituting in this identity a point x ∈ I′ at which the derivative |w^{(i+n+1)}| attains its maximum M^{(n+1)}, we bound from below the absolute value of the left-hand side by M^{(n+1)}δ, and on the other hand, bound from above the absolute value of the right-hand side by M(M^{(0)} + ⋯ + M^{(n)}) due to (1), i.e. M^{(n+1)} ≤ M(M^{(n)} + ⋯ + M^{(0)})/δ . Hence

M^{(n+1)} ≤ \frac{M}{δ} M^{(n+1)}((\frac{δ}{2M}) + (\frac{δ}{2M})^{2} + ⋯ + (\frac{δ}{2M})^{n+1}) <

\frac{M}{δ} M^{(n+1)} \frac{δ}{2M} \frac{2M}{2M − δ} ≤ M^{(n+1)},

this contradiction proving the lemma. □

In view of lemma 1, there exists a closed subinterval I_{0} ⊂ I of length

|I_{0}| ≥ \frac{min\{|I|, δ/2M\}}{(n + 1)^{2}}

without roots of any w^{(i)}, 0 ≤ i ≤ n + 1. Under these conditions on I_{0} we estimate the norms of the derivatives ||w^{(1)}||_{I_{n}}, …, ||w^{(n)}||_{I_{n}} via the norm ||w||_{I_{n}} for a suitable closed subinterval I_{n} ⊂ I_{0}.

Lemma 2 Assume that the derivatives w^{(0)}, …, w^{(n+1)} have no roots in an interval I_{0}. Then there exists a closed subinterval I_{n} ⊂ I_{0} of length |I_{n}| = \frac{|I_{0}|}{n+1} such that

||w^{(j)}||_{I_{n}} ≤ ||w||_{I_{0}}(\frac{n + 1}{|I_{0}|})^{j}, 0 ≤ j ≤ n.

Proof. Assume that one has already produced (by recursion on j) closed subintervals I_{0} ⊃ I_{1} ⊃ ⋯ ⊃ I_{j} with the lengths |I_{l}| = |I_{0}|\frac{n+1−l}{n+1} such that

||w^{(l)}||_{I_{l}} ≤ ||w||_{I_{0}}(\frac{n+1}{|I_{0}|})^{l}, 0 ≤ l ≤ j < n.

Denote by a_{1} = |w^{(j+1)}(x_{1})|, a_{2} = |w^{(j+1)}(x_{2})| the values of the function |w^{(j+1)}| at the endpoints of the interval I_{j} = [x_{1}, x_{2}]. If a_{1} < a_{2} then set x_{0} = x_{2} − \frac{|I_{0}|}{n+1} and the subinterval I_{j+1} = [x_{1}, x_{0}]. Otherwise, if a_{1} > a_{2} then x_{0} = x_{1}+ \frac{|I_{0}|}{n+1} and the subinterval I_{j+1} = [x_{0}, x_{2}] . Then ||w^{(j+1)}||_{I_{j+1}} = |w^{(j+1)}(x_{0})| and |w^{(j+1)}(x)| ≥ ||w^{(j+1)}||_{I_{j+1}} for any point x from the subinterval I_{j} − I_{j+1} since w^{(j+1)} is monotone and has no roots in the subinterval I_{j} ⊂ I_{0} (whence |w^{(j+1)}| is also monotone on the same interval). Observe that a_{1} ≠ a_{2}, indeed, otherwise w^{(j+2)} would vanish identically on the interval I_{j}. Hence

||w^{(j)}||_{I_{j}−I_{j+1}} ≥ ||w^{(j+1)}||_{I_{j+1}}(|I_{j}| − |I_{j+1}|)

because w^{(j)} has no roots in the subinterval I_{j} ⊂ I_{0}. Thus,

||w^{(j)}||_{I_{j}} ≥ ||w^{(j+1)}||_{I_{j+1}} \frac{|I_{0}|}{n + 1}

which proves the recursion hypothesis. Taking j = n and l = j, and noting that I_{n} ⊂ I_{j}, we get lemma 2. □

To complete the proof of the theorem consider the (n+1)×(n+1) subdeterminant formed by the first n + 1 derivatives of the functions u_{1}, …, u_{n}, w. Since this subdeterminant is equal to \overline{Δ}(0, n̂ + 1), we get (using lemma 2) from its expansion with respect to the last column (taking into account (2) and the bound on the length |I_{0}| following lemma 1) that

δ ≤ ||\overline{Δ}(0, n̂ + 1)||_{I_{n}} ≤ (n + 1)M_{0}||w||_{I_{0}}(\frac{n + 1}{|I_{0}|})^{n}.

The theorem is proved. □

Now we give an application of the theorem in the case of the functions u_{2j−1} = sin(θ_{j}X), u_{2j} = cos(θ_{j}X) for pairwise distinct squares θ_{j}^{2}. Since we deal with 2n functions u_{1}, …, u_{2n} the role of n in the bounds from theorem 1 will be played by 2n. About the function v we assume that the derivatives v^{(0)}, v^{(2)}, v^{(4)}, …, v^{(4n+2)} of even orders all have the same sign at each point of I, the same holds for all odd order derivatives v^{(1)}, v^{(3)}, …, v^{(4n+1)}, furthermore the derivatives are bounded above, and away from zero, with A ≥ |v^{(l)}(x)| ≥ a > 0 for x ∈ I, 0 ≤ l ≤ 4n + 2. In particular, one one could take v = exp.

Denote by σ_{i} the i-th elementary symmetric function of θ_{1}^{2}, …, θ_{n}^{2}, 0 ≤ i ≤ n, in particular, σ_{0} = 1. Denote by B_{0}, B_{1}, … the rows of the matrix \overline{Δ}, respectively. Then B_{2n+j} = ∑_{0≤i≤n−1}(−1)^{n−i+1}σ_{n−i}B_{2i+j} for j ≥ 0 (in fact, this holds for every j ≥ 0, but j ≤ 2n + 2 in the matrix \overline{Δ}). Therefore, |Δ(0, ĵ)| equals |σ_{n−j/2}Δ(0, ˆ2n)| when j is even, and equals zero when j is odd. Hence M_{0} ≤ max_{0≤l≤n}{σ_{l}}.

Furthermore, δ ≥ a ∑_{0≤j≤n} σ_{j}|Δ(0, ˆ2n)| and

M ≤ A max_{0≤l≤n}{σ_{l}} ∑_{0≤l≤n} |Δ(0, ˆ2n)|.

Let R = max{1, θ_{j}^{2}}, then max_{0≤l≤n}{σ_{l}} ≤ (2R)^{n}. The theorem implies that

||v− ∑_{1≤j≤2n} λ_{j}u_{j}||_{I} ≥ \frac{δ}{(n + 2)^{n+1}M_{0}} |I_{0}|^{n} = \frac{δ}{n^{n}(n + 2)^{2n+1}M_{0}} min\{|I|^{n}, (\frac{δ}{2M})^{n}\}

Thus, we obtain the following corollary.

Corollary.

||v − ∑_{1≤j≤n}(λ_{j} sin(θ_{j}X) + λ_{j+n} cos(θ_{j}X))||_{I} ≥ min\{\frac{|I|^{n}a}{n^{O(n)}A}, \frac{a^{n+1}}{A^{n}2^{O(n^{2})}R^{n^{2}}} \}

.

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.

[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.

[H] P.Hartman. Ordinary differential equations, Birkhauser, 1982.

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

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

[MSS] W.Maass, G.Schnitger, E.Sontag. On the computational power of sigmoid versus boolean threshold circuits. Proc. IEEE FOCS, 1991, p. 767– 776.