DEVIATION THEOREMS FOR SOLUTIONS OF LINEAR ORDINARY DIFFERENTIAL EQUATIONS AND APPLICATIONS TO PARALLEL COMPLEXITY OF SIGMOIDS

D. Yu. Grigoriev

Abstract. By a sigmoid with a depth d we mean a computational circuit with d layers in which rational operations are admitted at each layer, and to jump to the next layer the substitution of a function computed at the previous layer into an arbitrary real solution of a linear ordinary differential equation with the polynomial coefficients is admitted. Sigmoids appear as a computational model for neural networks. The deviation theorem is proved which states that for a (real) function 0 ≢ f computed by a sigmoid with a depth (or parallel complexity) d there exist c > 0 and an integer n such that the inequalities (exp(⋯ (exp(c|x|^{n}) ⋯)^{−1} ≤ |f(x)| ≤ exp(⋯ (exp(c|x|^{n}) ⋯)))) hold everywhere on the real line except for a finite measure set, where the iteration of the exponential function is taken d times. One can treat the deviation theorem as an analogue of Liouvillean theorem (on the bound of the difference of algebraic numbers) for solutions of ordinary differential equations. Also we estimate the numbers of zeroes of f in the intervals.

Introduction

Sigmoids (they appear as a computational model for neural networks, see [MSS] and

the references there, also the section 1 below) could be treated as the computational

circuits with the gate functions being not necessary rational functions as for the usual

circuits. In the so-called “standard sigmoid” one takes a function (1 + exp(−x))^{−1} as a

gate function. One of the most interesting questions in this area, how to approximate the

functions computed by sigmoids by means of the “simpler” functions?

We consider this question for the class of sigmoids in which as the gate functions could

occur arbitrary (real) functions being solutions of the linear ordinary differential equations

with the polynomial coefficients (see the section 1). For the question of approximation the

most important complexity parameter of a sigmoid appears to be its parallel complexity

or depth. By the depth we understand the number of layers of the sigmoid, at each

layer the applications of gate functions to the functions computed at the previous layers

Typeset by AMS-TEX

Subject classification. Primary 68C25

Key words and phrases: Sigmoid, parallel complexity, deviation theorems, bounds on Wronskian

are admitted and also rational operations are admitted. In the case of the threshold sigmoids (see [MSS] ) the functions at the next layer are taken as u(∑ w_{i}h_{i}) where h_{i} are the functions computed at the previous layers, w_{i} ∈ ℝ are some weights and u is a gate function; so linear functions are admitted. Observe also that the “standard” sigmoid can be simulated by the sigmoids considered in the present paper as (1 + exp(−x))^{−1} is a composition of a rational function and exp(−x) being a solution of a linear ordinary differential equation with const coefficients. Denote by exp^{(i)} = exp(⋯ (exp) ⋯) the iteration of the exponential function i times. This is an example of a function computed by a sigmoid with the depth i. We prove (see corollary 2 in the section 5) that any function computed by a sigmoid with a depth at most d cannot be approximated roughly speaking closer than (exp^{(d)})^{−1} by a (different) function also computed by a sigmoid with the depth at most d (this bound is sharp). The results of this kind we call deviation theorems, as we prove that two (different) functions computed by sigmoids of small parallel complexities deviate from each other. Also we prove that a function computed by a sigmoid, cannot grow too fast. One can also treat the deviation theorem as an extension of Liouvillean type theorems on algebraic numbers to the functions computed by sigmoids (cf. also [CC] ). A similar lower bound on an approximation of a function computed by a sigmoid by means of a Blum-Shub-Smale computations [BSS] (which admits rational operations and branching) is obtained in corollary 3 (see the section 5).

In the main theorem (see the section 5) we prove a stronger statement that the measure of all the points from a given interval in which the mentioned beforehand either deviation or the growth bound fails, is small. Whence we get (see the corollary) that the measure of all such points on a real line is finite. The theorem is proved by the induction on the depth and in the inductive step in order to get a lower bound on the function f computed at the next d-th layer of the sigmoid, we estimate by inductive hypothesis the coefficients a^{(0)}, …, a^{(m)} (being the functions computed by a sigmoid with the depth d − 1) of a certain linear ordinary differential equation Lf = ∑_{0≤i≤m} a^{(i)} f^{(i)} = 0 to which satisfies f.

The bound on the coefficients a^{(0)}, …, a^{(m)} implies an upper bound on |f| (see lemma 4 in the section 3), then we obtain a lower bound on the Wronskian (see [H], [K] ) of the equation Lf = 0 (see lemmas 5, 6 in the section 4) and finally, we get a lower bound on |f| (see lemma 7 in the section 5). In the section 2 we obtain some auxiliary bounds on the gate functions u, in other words on the solutions of the linear ordinary differential equations with polynomial coefficients, namely an upper bound (see lemma 1), a bound on the Wronskian (see lemma 3) and also a polynomial upper bound (being sharp) on the growth of the number of zeroes (in intervals) of u (see lemma 2), the latter was known as a consequence of Sturm theory for second-order equations (see [H] ). Moreover, we give an upper bound of the form exp^{(d−1)}(x^{0(1)}) (see the proposition in the section 5) on the number of zeroes in the interval [0, x] for arbitrary x, of a function computed by a sigmoid with the depth d (provided that we exclude a certain subset of ℝ with a finite measure such that its intersection with the interval [0, x] consist of at most exp^{(d−2)}(x^{0(1)}) intervals). In the section 1 we give necessary definitions and notations.

In the last section 6 we consider “elementary” sigmoids namely the ones with the gates exp, log and algebraic functions (in particular, containing “standard” sigmoids). As log has a singularity (at zero) one cannot directly apply the main theorem and the corollary, but it is still possible to extend the theorem and the corollary imposing a certain restriction on an elementary sigmoid (see the corollary 4).

1. \underline{Differential fields and sigmoids} Denote the ring K_{0} = ℝ[X], the field F_{0} = ℝ(X), differentiation D = d/dX, and by Γ

denote the set of real functions u : ℝ → ℝ (perhaps, with a finite number of singularities) being the solutions of linear ordinary differential equations of the kind

Lu = ( ∑_{0≤j≤n} a_{j}D^{j}) u = 0  (1)

where a_{j} ∈ K_{0}. Moreover, we impose a requirement that u could be obtained as the restriction on ℝ of some branch of a certain complex analytic function.

The elements of Γ will play the role of gate functions in the sigmoids. The operator L may have singularities only in the roots Δ = {δ_{1}, …, δ_{θ}} of the leading coefficient a_{n} ([H] ). Out of the points Δ ∩ ℝ the function u is analytic [H]. Now we define K_{i+1} and F_{i+1} by induction on i. Namely, K_{i+1} for i ≥ 0 is a differential ring ([K] ) generated by the functions of the form u(g), where u ∈ Γ, g ∈ F_{i}. Let F_{i+1} be a quotient field of K_{i+1} (so, F_{i+1} is a differential field). Thus, any element of F_{i+1} is a real function and could be obtained as the restriction on ℝ of some branch of a certain complex analytic function.

Under a sigmoid we’ll understand a circuit with a certain depth d in which any function w_{i+1}^{(j)} at (i + 1)-th layer (0 ≤ i < d) is computed as

w_{i+1}^{(j)} = u (\frac{f}{g} (w_{i}^{(1)}, w_{i}^{(2)}, …, X))  (2)

for some gate function u ∈ Γ and f, g ∈ ℝ[W_{i}^{(1)}, W_{i}^{(2)}, …, X] being polynomials in the functions w_{i}^{(1)}, w_{i}^{(2)}, … computed at the previous layers of the sigmoid, and in the variable X. One can show by induction on i that each function w_{i+1}^{(j)} is real and belongs to K_{i+1}, conversely, any element from K_{i+1} can be obtained as a rational function in functions computed at (i + 1)-th layer of a suitable sigmoid. Usually, u is taken from a certain subclass of Γ, for example, in the case of the “standard” sigmoid one takes u = exp(−X) (see [MSS] ).

Henceforth, we fix a sigmoid and by D_{i} ⊃ K_{i} denote a differential ring generated over ℝ by w_{i}^{(1)}, w_{i}^{(2)}, …; so as an algebraic ring D_{i} is generated by all the derivatives w_{i}^{(1)}, Dw_{i}^{(1)}, …, w_{i}^{(2)}, Dw_{i}^{(2)} . . ..

Consider a basis (over ℂ) \overline{u_{1}}, …, \overline{u_{n}} of the space of solution of the equation (1), where each of \overline{u_{1}}, …, \overline{u_{n}} could be considered as a branch of a complex analytic function [H], let u_{1} = u be the restriction of \overline{u}_{1} on ℝ, denote by u_{2}, …, u_{n} the restrictions of \overline{u}_{2}, …, \overline{u}_{n} on ℝ, respectively. Denote by \overline{D}_{i} ⊃ D_{i} a differential ring generated over ℂ by the functions of the form u_{ℓ}(\frac{f}{g} (w_{i}^{(1)}, w_{i}^{(2)}, …, X)), 1 ≤ ℓ ≤ n for all the functions w_{i+1}^{(j)} computed in the sigmoid at the steps of the kind (2) at (i + 1)-th layer. Again as above every element from \overline{D}_{i} could be considered as the restriction on ℝ of some branch of a certain complex analytic function.

2. \underline{Bounds on the solutions and on the Wronskian of a linear ordinary} \underline{differential equations with polynomial coefficients}.

First, obtain upper bounds on the absolute values of a complex analytic function \overline{u} (and its derivatives D\overline{u}, D^{2}\overline{u}, …) satisfying (1).

¿From now on p_{0}, p_{1}, … will denote polynomials from K_{0} each having a form p_{i} = \overline{p_{i}}(X^{2}) where a polynomial \overline{p}_{i} ∈ K_{0} monotonically increases on ℝ^{+} and \overline{p_{i}}(0) ≥ 1. The class of all such polynomials denote by P.

For an operator L (see (1)) and x ∈ ℂ denote ∥x∥_{L} = max{ |x|, | x − δ_{1}|^{−1}, …, |x − δ_{θ}|^{−1}}.

Lemma 1. Let \overline{u} satisfy (1). One can find a suitable p_{0} ∈ P such that for any x ∈ ℂ |\overline{u}(x)|, |D\overline{u}(x)|, …, |D^{n}\overline{u}(x)| ≤ exp(p_{0}( ∥x∥_{L})).

Proof. Rewrite (1) as a system of linear first-order equations: DY = AY where the vector Y = (\overline{u}, D\overline{u}, …, D^{n−1}\overline{u}) and the matrix

A = ( \begin{matrix}0 & 1 \\ & 0 & 1 & ◯ \\ ◯ & & ... & 0 & 1 \\ −\frac{a_{0}}{a_{n}} & −\frac{a_{1}}{a_{n}} & … & & −\frac{a_{n−1}}{a_{n}} \end{matrix} )  (3)

Then Y (x) = Y (x_{0})+ ∫_{x_{0}}^{x} A(ξ)Y (ξ)dξ ([H] ), provided that the path along which we integrate with the endpoints x_{0}, x, does not pass through the singularities δ_{1}, …, δ_{θ}, hence ∥Y (x)∥ ≤ ∥Y (x_{0})∥ + ∫_{x_{0}}^{x} ∥A(ξ)∥ ∥Y (ξ)∥ dξ where ∥ ∥ denotes the euclidean norm for vectors and

matrices. Then Gronwall’s inequality [H] implies that ∥Y (x)∥ ≤ ∥Y (x_{0})∥ exp ∫_{x_{0}}^{x} ∥A(ξ)∥ dξ ≤ exp(p_{0}(∥x∥_{L})) for a suitably chosen path.

Corollary 1. For every j ≥ 0 there exists p_{0}^{(j)} ∈ P such that |D^{j}\overline{u}(x)| ≤ exp(p_{0}^{(j)}(∥x∥_{L})) for all x ∈ ℝ.

One can prove the corollary by induction on j taking into account that by applying

D^{j} to (1) one gets (a_{n}D^{n+j} + ∑_{0≤ℓ<n+j} a_{ℓ}^{(j)}D^{ℓ})\overline{u} = 0 for some a_{ℓ}^{(j)} ∈ K_{0}.

In the next lemma we bound from above the number N(x) of the roots of the real function u satisfying (1), in the interval [0, x], provided that Δ ∩ ℝ = ϕ, so when u has no (real) singularities. For second-order equations (n = 2) one can find a polynomial bound on N(x) in [H], being a consequence of Sturm theory.

Lemma 2. N(x) ≤ p_{1}^{(0)}(x) for a certain p_{1}^{(0)} ∈ P, provided that Δ ∩ ℝ = ϕ.

Proof. Let |a_{i}(y)| < p_{1}(x) for each y ∈ [0, x] for an appropriate polynomial p_{1} ∈ P. We show that each interval I = (y, y + (2p_{1}(x))^{−1}) ⊂ [0, x] contains at most (n − 1) roots of u. Suppose the contrary, then (by Rolle’s theorem) each derivative Du, … D^{n−1}u has at least one root in the interval I. Denote by M^{(j)} = max_{z∈I}|D^{j}u(z)|. Then M^{(j+1)} ≥ M^{(j)}2p_{1}(x) by the theorem of the mean of the derivative, 0 ≤ j < n. Let D^{n}u reach

M^{(n)} at a point x_{0} ∈ I. Then M^{(n)} = |D^{n}u(x_{0})| = | ∑_{0≤j≤n−1} a_{j}(x_{0})D^{j}u(x_{0})| ≤ p_{1}(x)

(\frac{1}{2p_{1}(x)} + (\frac{1}{2p_{1}(x)})^{2} + ⋯ + (\frac{1}{2p_{1}(x)})^{n}) M^{(n)} < p_{1}(x) · \frac{2}{(2p_{1}(x))}M^{(n)}. Obtained contradiction shows that I contains less that n roots of u, therefore N(x) ≤ 2xp_{1}(x)(n − 1), lemma is proved.

Remark. The bound in lemma 2 is sharp, take, for example, as u = sin(X^{n}). Consider Wronskian [H]

W = det ( \begin{matrix}\overline{u}_{1} & … & \overline{u}_{n} \\ D\overline{u}_{1} & … & D\overline{u}_{n} \\ ⋮ & & ⋮ \\ D^{n−1}\overline{u}_{1} & … & D^{n−1}\overline{u}_{n} \end{matrix} )

As DW = −\frac{a_{n−1}}{a_{n}} W, one gets W (x) = W (x_{0}) exp ∫_{x_{0}}^{x} −\frac{a_{n−1}}{a_{n}}, provided that the path along which we integrate, does not pass through the singularities δ_{1}, …, δ_{θ}. This formula entails the following lemma.

Lemma 3. There exists a polynomial p_{2} ∈ P such that (exp(p_{2}(∥x∥_{L})))^{−1} ≤ |W (x)| ≤ exp(p_{2}(∥x∥_{L})) hold for all x ∈ ℂ\Δ.

Remark. As below we will be interested in the functions on ℝ, we will apply lemmas 1, 3 to the functions u_{1}, …, u_{n}.

3. \underline{Upper bounds for the differential polynomials in the functions computed} by a sigmoid

Denote by exp^{(i)} = exp(⋯ (exp) ⋯) ∈ K_{i} the iteration of the exponential function i times.

By induction on i we’ll estimate (from above in the present section and from below in the section 5) differential polynomials G_{1}, …, G_{K} ∈ \overline{D_{i+1}} (see section 1). For this purpose we’ll produce a family of differential polynomials H^{(0)}, …, H^{(m)} ∈ D_{i} such that a lower bound on |H^{(0)}| and upper bounds on |H^{(0)}|, …, |H^{(m)}| would entail upper bounds on |G_{1}|, …, |G_{k}| (a similar statement for lower bounds one can find in the section 5). This will be used in the proof of the inductive step in the main theorem.

Lemma 4. For a family of differential polynomials G_{1}, …, G_{k} ∈ \overline{D_{i+1}} one can construct a family of differential polynomials 0 ≢ H^{(0)}, …, H^{(m)} ∈ D_{i} such that for every polynomials p_{7}, p̃ ∈ P there exists a polynomial \overline{p} ∈ P satisfying the following property: for arbitrary x ∈ ℝ if the inequalities |H^{(0)}| ≥ (exp^{(i)} p̃)^{−1}, |H^{(j)}| ≤ exp^{(i)} p̃, 0 ≤ j ≤ m hold everywhere on an interval I_{i} = (x − (exp^{(i)} p_{7}(x))^{−1}, x) then |G_{ℓ}| ≤ exp^{(i+1)} \overline{p}, 1 ≤ ℓ ≤ k hold everywhere on I_{i}.

Proof. For each function w = w_{i+1}^{(j)} computed by the sigmoid (see (2)) consider the following elements from D_{i}:

H_{w}^{(0)} = g(w_{1}^{(i)}, …, X) ⊓_{1≤ℓ≤θ,δ_{ℓ}∈ℝ} (f(w_{i}^{(1)}, …, X) − δ_{ℓ}g(w_{i}^{(1)}, …, X))

where the product is taken over the real δ_{ℓ} ∈ Δ ∩ ℝ, H_{w}^{(1)} = g(w_{1}^{(i)}, …, X), H_{w}^{(2)} = f(w_{i}^{(1)}, …, X). Observe that if |H_{w}^{(0)}| ≥ (exp^{(i)} p̃)^{−1}; |H_{w}^{(1)}|, |H_{w}^{(2)}| ≤ exp^{(i)} p̃ everywhere on I_{i} then |g(w_{1}^{(i)}, …, X)|, |f(w_{i}^{(1)}, …, X) − δ_{ℓ}g(w_{i}^{(1)}, …, X)| ≥ (exp^{(i)} p_{3})^{−1} everywhere on I_{i} for an appropriate polynomial p_{3} ∈ P. Hence ∥\frac{f}{g} (w_{i}^{(1)}, …, X)∥_{L} ≤ exp^{(i)} p_{4} everywhere on I_{i} for some p_{4} ∈ P.

Let in the differential polynomials G_{1}, …, G_{k} occur the derivatives D^{s}u_{æ}((f/g)(w_{i}^{(1)}, w_{i}^{(2)}, …, X)) (see (2) and the section 1) up to orders s ≤ s_{0}. We have D^{s}u_{æ}((f/g)(w_{i}^{(1)}, w_{i}^{(2)}, …, X)) = \frac{1}{g^{s+1}} (u_{æ}(\frac{f}{g} (w_{i}^{(1)}, …))h_{0}^{(s)}+ \frac{∂u_{æ}}{∂z} (\frac{f}{g} (w_{i}^{(1)}, …))h_{1}^{(s)}+⋯+ \frac{∂^{s}u_{æ}}{∂z^{s}} (\frac{f}{g} (w_{i}^{(1)}, …)) h_{s}^{(s)}) for suitable differential polynomials h_{0}^{(s)}, ⋯, h_{s}^{(s)} ∈ D_{i}. As H^{(0)} take the product of H_{w}^{(0)} for all the functions w computed by the sigmoid, as H^{(1)}, …, H^{(m)} take the union of H_{w}^{(1)}, H_{w}^{(2)} for all w and in addition h_{0}^{(s)}, …, h_{s}^{(s)} for all s ≤ s_{0}, and all w. Then by the assumption of the lemma and by the proved above ∥\frac{f}{g} (w_{i}^{(1)}, …, X)∥_{L} ≤ exp^{(i)} p_{5} everywhere on I_{i} for a certain p_{5} ∈ P, therefore |\frac{∂^{t}u_{æ}}{∂z^{t}}(\frac{f}{g} (w_{i}^{(1)}, …)) | ≤ exp^{(i+1)}p_{6}, 0 ≤ t ≤ s_{0} everywhere on I_{i} for an appropriate p_{6} ∈ P because of lemma 1 and corollary 1. Hence |D^{s}u_{æ}((f/g)(w_{i}^{(1)}, …, X))| ≤ exp^{(i+1)} \overline{p}_{6} everywhere on I_{i} for a certain \overline{p}_{6} ∈ P by virtue of the construction of H^{(1)}, …, H^{(m)}.

Finally, each of G_{1}, …, G_{k} can be considered as an (algebraic) polynomial in D^{s}u_{æ} ((f/g)(w_{i}^{(1)}, …, X)), this completes the proof of the lemma.

Remark. Actually we did not utilize the particular form of an interval I_{i}, thus the lemma is valid for any interval, this form of I_{i} will be used later in the section 5 when we’ll deal with the lower bounds. The same remark concerns also lemmas 5, 6 below in the section 4.

4. \underline{Upper and lower bounds on Wronskians of the functions computed by} \underline{sigmoids}

Any function w = w_{i+1}^{(j)} computed by the sigmoid (see (2)) satisfies a linear ordinary differential equation with the coefficients from D_{i}. One can represent (cf. the proof of lemma 4) w, Dw, …, D^{n}w as linear combinations of u((f/g)(w_{i}^{(1)}, …)), \frac{∂u}{∂z}((f/g)(w_{i}^{(1)}, …)) , …, \frac{∂^{n−1}u}{∂z^{n−1}}((f/g)(w_{i}^{(1)}, …)) with the coefficients being differential polynomials in (f/g) (w_{i}^{(1)}, …). Therefore, w satisfies a certain n-order equation 0 = Lw = ( ∑_{0≤ℓ≤n} b_{ℓ}D^{ℓ})w where b_{0}, …, b_{n} are differential polynomials in (f/g)(w_{i}^{(1)}, …). By the same token u_{2}((f/g) (w_{i}^{(1)}, …)), …, u_{n}((f/g)(w_{i}^{(1)}, …)) also satisfy the same equation Lw = 0 (see the section 1). Let us prove that w = u_{1}((f/g)(w_{i}^{(1)}, …)), …, u_{n}((f/g)(w_{i}^{(1)}, …)) are linearly independent over ℂ and thereby these functions constitute a basis of the space of solutions of the equation Lw = 0, provided that (f/g)(w_{i}^{(1)}, …) ≢ const (if the latter is not the case then w ≡ const and we can omit computational step (2) in the sigmoid). Indeed, consider the Wronskian

W_{w} = det ( \begin{matrix}u_{1}(f/g)(w_{i}^{(1)}, …) & . . . . . . & u_{n}(f/g)(w_{i}^{(1)}, …) \\ D(u_{1}(f/g)(w_{i}^{(1)}, …)) & . . . . . . & D(u_{n}(f/g)(w_{i}^{(1)}, …)) \\ ⋮ & & ⋮ \\ D^{n−1}(u_{1}(f/g)(w_{i}^{(1)}, …)) & . . . . . . & D^{n−1}(u_{n}(f/g)(w_{i}^{(1)}, …)) \end{matrix} )

= W ((f/g)(w_{i}^{(1)}, …)) · (D((f/g)(w_{i}^{(1)}, …)))^{\frac{n(n−1)}{2}} ≢ 0

where W = det ( \begin{matrix}u_{1} & … & u_{n} \\ ⋮ & & ⋮ \\ D^{n−1}u_{1} & … & D^{n−1}u_{n} \end{matrix} ) is the Wronskian of the equation Lu = 0.

One can express D((f/g)(w_{i}^{(1)}, …,)) = \frac{h_{1}(w_{i}^{(1)},...,)}{g^{2}(w_{i}^{(1)},...,)} where h_{1}(w_{i}^{(1)}, …) ∈ D_{i} is a certain differential polynomial. Consider (cf. the proof of lemma 4) the following elements

from D_{i} : \overline{H}_{w}^{(0)} = h_{1}(w_{i}^{(1)}, …)g(w_{i}^{(1)}, …) ⊓_{1≤ℓ≤θ} (f(w_{i}^{(1)}, …) − δ_{ℓ}g(w_{i}^{(1)}, …)), \overline{H}_{w}^{(1)} =

g(w_{i}^{(1)}, …), \overline{H}_{w}^{(2)} = f(w_{i}^{(1)}, …), \overline{H}_{w}^{(3)} = h_{1}(w_{i}^{(1)}, …). Suppose that for a certain polynomial p_{8} ∈ P for arbitrary x ∈ ℝ the following inequalities |\overline{H}_{w}^{(0)}| ≥ (exp^{(i)} p_{8})^{−1}, |\overline{H}_{w}^{(j)}| ≤ exp^{(i)} p_{8}, 0 ≤ j ≤ 3 hold everywhere on an interval I_{i} = (x − (exp^{(i)} p_{7}(x))^{−1}, x). Then |\overline{H}_{w}^{(1)}|, |\overline{H}_{w}^{(3)}| ≥ (exp^{(i)} p_{8}^{2})^{−1} hold everywhere on I_{i}. Therefore, (exp^{(i)} p_{8}^{4})^{−1} ≤ |D((f/g)(w_{i}^{(1)}, …))| ≤ exp^{(i)} p_{8}^{5} is true everywhere on I_{i}. Since ∥(f/g)(w_{i}^{(1)}, …)∥_{L} ≤ exp^{(i)} p_{9} is valid everywhere on I_{i} for an appropriate p_{9} ∈ P, lemma 3 implies inequalities (exp^{(i+1)} \overline{p})^{−1} ≤ |W ((f/g)(w_{i}^{(1)}, …))| ≤ exp^{(i+1)} \overline{p} everywhere on I_{i} a suitable \overline{p} ∈ P, this gives similar bounds on |W_{w}|.

Thus, the following lemma is proved.

Lemma 5. For each function w = w_{i+1}^{(j)} (recall that we assume that w ≢ const without loss of generality) computed by a sigmoid (see (2)) one can construct differential polynomials \overline{H}_{w}^{(j)} ∈ D_{i}, 0 ≤ j ≤ 3, \overline{H}_{w}^{(0)} ≢ 0 such that for any polynomials p_{7}, p̃_{0} ∈ P there exists a polynomial \overline{p}_{0} ∈ P satisfying the following property: for arbitrary x ∈ ℝ if the inequalities |\overline{H}_{w}^{(0)}| ≥ (exp^{(i)} p̃_{0})^{−1}, |\overline{H}_{w}^{(j)}| ≤ exp^{(i)} p̃_{0}, 0 ≤ j ≤ 3 are valid everywhere on an interval I_{i} = (x − (exp^{(i)} p_{7}(x))^{−1}, x) (cf. lemma 4 and the remark just after it) then the Wronskian W_{w} = W (w_{i+1}^{(j)} = u_{1}((f/g)(w_{i}^{(1)}, …)), …, u_{n}((f/g)(w_{i}^{(1)}, …))) satisfies inequalities (exp^{(i+1)} \overline{p}_{0})^{−1} ≤ |W_{w}| ≤ exp^{(i+1)} \overline{p}_{0} everywhere on I_{i}.

Thus, we’ve bounded Wronskian of the functions w = w_{i+1}^{(j)} computed by the sigmoid (see (2)). Now we proceed to estimating Wronskian of the differential polynomials in the functions w, i.e. the elements from D_{i+1}, more precisely, by the latter we mean Wronskian of some linear ordinary differential equation with the coefficients from D_{i} to which satisfies this differential polynomial under consideration. Arguing by induction on the construction of the differential polynomial, we estimate Wronskian in three cases: for the derivative (see 4.1 below), for the sum of the functions (see 4.2 below) and for the product (see 4.3 below). Lemma 5 plays the role of the base of induction.

So, we assume that two function w, v ∈ D_{i+1} satisfy linear ordinary differential equa-

tions 0 = Q_{1}w = Q_{2}v, where Q_{1} = ∑_{0≤ℓ≤k} α^{(ℓ)}D^{ℓ}, Q_{2} = ∑_{0≤ℓ≤m} β^{(ℓ)}D^{ℓ} and the coeffi-

cients α^{(ℓ)}, β^{(ℓ)} ∈ D_{i}. We assume also that by induction some differential polynomials 0 ≢ H_{w}^{(0)}, …, H_{w}^{(æ_{w})}, 0 ≢ H_{v}^{(0)}, …, H_{v}^{(æ_{v})} ∈ D_{i} are produced such that for any polynomials p_{7}, p_{10} ∈ P there exists p_{11} ∈ P satisfying the following property: if

|H_{w}^{(0)}|, |H_{v}^{(0)}| ≥ (exp^{(i)}(p_{10}))^{−1}; |H_{w}^{(j)}|, |H_{v}^{(j)}| ≤ exp^{(i)}(p_{10})  (4)

for all j ≥ 0 everywhere on an interval I_{i} = (x − (exp^{(i)} p_{7}(x))^{−1}, x), then

(exp^{(i+1)}(p_{11}))^{−1} ≤ |W_{w}|, |W_{v}| ≤ exp^{(i+1)}(p_{11})  (5)

everywhere on I_{i}; here W_{w}, W_{v} denote the Wronskians of the operators Q_{1}, Q_{2}, resp. Recall (see the section 1) that u = u_{1}, …, u_{n} is a basis of the equation (1) and w_{i+1}^{(j)} = u((f/g)(w_{i}^{(1)}, …)) (see (2)). Finally, we assume that the equation Q_{1}w = 0(Q_{2}v = 0 resp.) has a basis (over ℂ) w = w^{(1)}, …, w^{(k)}(v = v^{(1)}, …, v^{(m)} resp.) where w^{(1)}, …, w^{(k)}, v^{(1)}, …, v^{(m)} ∈ \overline{D_{i+1}}.

Thus, we’ve formulated an inductive hypothesis of the induction on the construction of w ∈ D_{i+1} (the base was proved in lemma 5).

4.1. \underline{Estimating Wronskian for the derivative Dw}.

Consider 2 cases. In the first one α^{(0)} ≠ 0. Then Dw, D^{2}w, …, D^{k+1}w can be expressed as the linear combinations of w, Dw, …, D^{k−1}w with the coefficients being the differential polynomials in α^{(0)}, …, α^{(k)} and thereby, being the elements from D_{i}. Therefore, we get a required equation for Dw, namely, 0 = \overline{Q}_{1}Dw = ( ∑_{0≤ℓ≤k} \overline{α}^{(ℓ)}D^{ℓ})Dw. The functions Dw^{(1)}, …, Dw^{(k)} constitute a basis of the space of its solutions since

W_{Dw} = det ( Dw^{(1)} … Dw^{(k)} ; ⋮ ; D^{k}w^{(1)} … D^{k}w^{(k)} ) = (−1)^{k+1} \frac{α^{(0)}}{α^{(k)}} W_{w} ≢ 0

Set H_{Dw}^{(0)} = H_{w}^{(0)} · α^{(0)}α^{(k)}, H_{Dw}^{(1)} = H_{w}^{(1)}, …, H_{Dw}^{(æ_{w})} = H_{w}^{(æ_{w})}, H_{Dw}^{(æ_{w}+1)} = H_{w}^{(0)}, H_{Dw}^{(æ_{w}+2)} = α^{(0)}, H_{Dw}^{(æ_{w}+3)} = α^{(k)} (see (4)), this gives the desired bounds on the Wronskian W_{Dw} (see (5)).

In the second case α^{(0)} = 0. Then 0 = \overline{Q}_{1}(Dw) = ( ∑_{0≤ℓ≤k−1} α^{(ℓ+1)}D^{ℓ})Dw provides the required equation for Dw. Since 0 = Q_{1} 1 we can take as a basis of the space of solutions of the equation 0 = Q_{1}w the functions 1, w, \overline{w}^{(2)}, …, \overline{w}^{(k−1)} for some \overline{w}^{(2)}, …, \overline{w}^{(k−1)} ∈ \overline{D}_{i+1}. Then the Wronskian W_{w} of the equation Q_{1}w = 0

det ( 1  w  \overline{w}^{(2)}  …  \overline{w}^{(k+1)} ; 0 Dw  D\overline{w}^{(2)} … D\overline{w}^{(k+1)} ; ⋮ ; 0 D^{k−1}w D^{k−1}\overline{w}^{(2)} … D^{k−1}\overline{w}^{(k+1)} ) equals to

the Wronskian of the basis Dw, D\overline{w}^{(2)}, …, D\overline{w}^{(k−1)} of the space of solutions of the equation 0 = \overline{Q}_{1} (Dw). This proves the inductive hypothesis for W_{Dw} (taking H_{Dw}^{(0)} = H_{w}^{(0)}, …,H_{Dw}^{(æ_{w})} = H_{w}^{(æ_{w})}).

4.2. \underline{Estimating Wronskian for the sum w + v}.

All the functions \overline{w} + \overline{v} where \overline{w}, \overline{v} are solutions of the equations 0 = Q_{1}\overline{w} = Q_{2}\overline{v}, satisfy a linear ordinary differential equation ( ∑_{0≤p≤s} γ^{(ℓ)}D^{ℓ})(\overline{w} + \overline{v}) = Q_{+}(\overline{w} + \overline{v}) = 0 of the minimal order s ≤ m + k because one can express \overline{w} + \overline{v}, D(\overline{w} + \overline{v}), ⋯, D^{k+m}(\overline{w} + \overline{v}) as the linear combinations of \overline{w}, D\overline{w}, …, D^{k−1}\overline{w}, \overline{v}, D\overline{v}, …, D^{m−1}\overline{v} with the coefficients being the quotients of differential polynomials in α^{(0)}, …, α^{(k)}, β^{(0)}, …, β^{(m)}. Hence γ^{(ℓ)} can be taken as differential polynomials in α^{(0)}, …, α^{(k)}, β^{(0)}, …, β^{(m)} and thereby one can assume γ^{(ℓ)} ∈ D_{i}. As a basis of the space of solutions of the equation Q_{+}z = 0 one can take a subset of w^{(1)}, …, w^{(k)}, v^{(1)}, …, v^{(m)} and s equals to the maximal number of linearly independent (over ℂ) functions among w^{(1)}, …, w^{(k)}, v^{(1)}, …, v^{(m)} (see [S81] ). Denote by W_{w+v} the Wronskian of the equation Q_{+}z = 0 (with respect to the chosen basis). Therefore, relying on lemma 4 one can construct H̃_{w+v}^{(0)}, …, H̃_{w+v}^{(æ̃_{w+v})} ∈ D_{i} such that if |H̃_{w+v}^{(0)}| ≥ (exp^{(i)}(p_{12}))^{−1}, |H̃_{w+v}^{(j)}| ≤ exp^{(i)}(p_{13}) everywhere on I_{i} then |W_{w+v}| ≤ exp^{(i+1)}(p_{14}) everywhere on I_{i}.

Proceed to a lower bound on |W_{w+v}|. Rewrite the equations 0 = Q_{1}w = Q_{2}v as first-order linear systems DY_{1} = B_{1}Y_{1}, DY_{2} = B_{2}Y_{2} where (cf. (3))

B_{1} = ( \begin{matrix}0 & 1 & & ◯ \\ & 0 \\ ◯ & & ... & 1 \\ −\frac{α^{(0)}}{α^{(k)}} & −\frac{α^{(1)}}{α^{(k)}} & … & −\frac{α^{(k−1)}}{α^{(k)}} \end{matrix} ) , B_{2} = ( \begin{matrix}0 & 1 & & ◯ \\ & 0 \\ ◯ & & ... & 1 \\ −\frac{β^{(0)}}{β^{(m)}} & −\frac{β^{(1)}}{β^{(m)}} & … & −\frac{β^{(m−1)}}{β^{(m)}} \end{matrix} )

Consider a direct sum of the latter 2 systems: DU = (B_{1} ⊕ B_{2})U where B_{1} ⊕ B_{2} = \binom{B_{1} 0}{0 B_{2}}. Denote by T_{1} (resp T_{2}) k-dimensional (resp. m-dimensional) space of solutions of the system DY_{1} = B_{1}Y_{1} (resp DY_{2} = B_{2}Y_{2}), a certain basis of T_{1} (resp. T_{2}) consists of the vectors {(w^{(j)}, Dw^{(j)}, …, D^{k−1}w^{(j)})}_{1≤j≤k} (resp. {(v^{(j)}, Dv^{(j)}, …, D^{m−1}v^{(j)})}_{1≤j≤m}). The space of solutions of the system DU = (B_{1} ⊕ B_{2})U is the direct sum T_{1} ⊕ T_{2}. Therefore, the Wronskian W_{B_{1}⊕B_{2}} of the system DU = (B_{1} ⊕B_{2})U equals to W_{B_{1}⊕B_{2}} = W_{B_{1}} ·W_{B_{2}} = W_{w} · W_{v}.

Rewrite also the equation Q_{+}(w + v) = 0 as a first-order linear differential system:

DT = CT where C = ( \begin{matrix}0 & 1 & & ◯ \\ & 0 \\ ◯ & & ... & 1 \\ \frac{−γ^{(0)}}{γ^{(s)}} & & ... & \frac{−γ^{(s−1)}}{γ^{(s)}} \end{matrix} ). Denote by T (s-dimensional) space of

solutions of the system DT = C T. Consider a mapping L : T_{1} ⊕ T_{2} → T which maps

\begin{matrix}(w^{(j_{1})}, Dw^{(j_{1})}, …, D^{k−1}w^{(j_{1})}) ⊕ (v^{(j_{2})}, Dv^{(j_{2})}, …, D^{m−1}v^{(j_{2})}) → \\ (w^{(j_{1})} + v^{(j_{2})}, D(w^{(j_{1})} + v^{(j_{2})}), …, D^{s−1}(w^{(j_{1})} + v^{(j_{2})})) \end{matrix}

Obviously, L is surjective.

Recall (see [K], also [Si 90] ) that a subspace (over ℂ) U_{1} ⊂ T_{1} ⊕ T_{2} is called invariant (with repsect to the system DU = (B_{1} ⊕ B_{2})U) if U_{1} is invariant under the action of the (differential) Galois group. Then the kernel U = ker L ⊂ T_{1} ⊕ T_{2} is invariant (see e.g. [BBH], [G90b] ), hence any nonsingular linear transformation of the space T_{1} ⊕ T_{2} being of the form \overline{L} = \binom{∗}{L}, where ∗ is (k + m − s) × (k + m) matrix over ℝ, reduces (see e.g.

[BBH] ) the system DU = (B_{1} ⊕ B_{2})U to the block-triangular form D\overline{U} = \binom{C_{1} 0}{C_{2} C_{3}}\overline{U} where \overline{U} = \overline{L}U, \binom{C_{1} 0}{C_{2} C_{3}} = (D\overline{L}) · (\overline{L})^{−1} + \overline{L}\binom{B_{1} O}{O B_{2}}(\overline{L})^{−1} and the space of solutions of the system DU_{3} = C_{3}U_{3} equals to U (in [G90b], see also [G90a] one can find the complexity bounds on reducing a system to the block-triangular form). The space of solutions of the system DU_{1} = C_{1}U_{1} equals to T , hence the Wronskian W_{C_{1}} of this system equals to W_{w+v}.

It is known (see [H] ) that the Wronskian W_{C_{1}}= exp ∫ tr C_{1}, therefore, W_{C_{1}}W_{C_{3}}W\binom{C_{1} 0}{C_{2} C_{3}} = (det \overline{L}) · W\binom{B_{1} 0}{0 B_{2}} = (det \overline{L}) · W_{w} · W_{v}. As each coefficient of any vector in the space U ⊂ T_{1} ⊕ T_{2} belongs to \overline{D_{i+1}} one can construct by lemma 4 the differential polynomials \overline{H}_{U,...,}^{(0)}\overline{H}_{U}^{(æ_{U})} ∈ D_{i} such that if |\overline{H}_{U}^{(0)}| ≥ (exp^{(i)}(p_{15}))^{−1}, |\overline{H}_{U}^{(j)}| ≤ exp^{(i)}(p_{16}), 0 ≤ j ≤ æ_{U} everywhere on an interval I_{i} = (x − (exp^{(i)}(p_{7}(x)))^{−1}, x) then |W_{C_{3}}| ≤ exp^{(i+1)}(p_{17}) everywhere on I_{i}. As each entry of the matrix \overline{L} belongs to a quotient field of the ring D_{i}, one can represent det(\overline{L}) = \overline{H}^{(0)} / \overline{H}^{(1)} where \overline{H}^{(0)}, \overline{H}^{(1)} ∈ D_{i}.

Finally, taking H_{w+v}^{(0)} = H_{w}^{(0)} H_{v}^{(0)} H̃_{w+v}^{(0)} \overline{H}_{U}^{(0)} \overline{H}^{(0)} (see (4)) and as a family H_{w+v}^{(1)}, …, H_{w+v}^{(æ_{w+v})} taking the union of H_{w}^{(j)}, H_{v}^{(j)}, H̃_{w+v}^{(j)}, \overline{H}_{U}^{(j)}, \overline{H}^{(0)}, \overline{H}^{(1)} for all j ≥ 0, we obtain (using (5)) that if |H_{w+v}^{(0)}| ≥ (exp^{(i)}(p_{18}))^{−1}, |H_{w+v}^{(j)}| ≤ exp^{(i)}(p_{19}) for all j ≥ 0 everywhere on I_{i} then (exp^{(i+1)}(p_{20}))^{−1} ≤ |W_{C_{1}}| = |W_{w+v}| ≤ exp^{(i+1)}(p_{14}) everywhere on I_{i}, which completes the proof of the inductive hypothesis for the sum w + v ∈ D_{i+1}.

4.3. \underline{Estimating Wronskian for the product wv}.

All the functions \overline{w} \overline{v} where \overline{w}, \overline{v} are the solutions of the equations 0 = Q_{1}\overline{w} = Q_{2}\overline{v}, satisfy a linear ordinary differential equation 0 = Q_{×}(\overline{w} \overline{v}) = ( ∑_{0≤j≤t} ρ^{(j)}D^{j})(\overline{w} \overline{v}) of the (minimal) order t ≤ mk because one can express \overline{w} \overline{v}, D(\overline{w} \overline{v}), …, D^{mk}(\overline{w} \overline{v}) as the linear combinations of D^{j_{1}} \overline{w} D^{j_{2}} \overline{v} for 0 ≤ j_{1} ≤ k − 1, 0 ≤ j_{2} ≤ m − 1 with the coefficients being quotients of differential polynomials in α^{(0)}, …, α^{(k)}, β^{(0)}, …, β^{(m)}. Hence ρ^{(j)} can be taken as differential polynomials in α^{(0)}, …, α^{(k)}, β^{(0)}, …, β^{(m)} and thereby one can assume that ρ^{(j)} ∈ D_{i}. As a basis of the space of solutions of the equation Q_{×}z = 0 one can take a maximal linearly independent (over ℂ) subset of the elements w^{(j_{1})}v^{(j_{2})}, 1 ≤ j_{1} ≤ k, 1 ≤ j_{2} ≤ m (see [S81] ). Denote by W_{wv} the Wronskian of the equation Q_{×}z = 0 (with respect to the chosen basis). Therefore, relying on lemma 4 one can construct differential polynomials H̃_{wv,...,}^{(0)}H̃_{wv}^{(æ̃_{wv})} ∈ D_{i} such that if |H̃_{wv}^{(0)}| ≥ (exp^{(i)}(p_{21}))^{−1}, |H̃_{wv}^{(j)}| ≤ exp^{(i)}(p_{22}), for all j ≥ 0 everywhere on an interval I_{i} (see above the subsection 4.2) then |W_{wv}| ≤ exp^{(i+1)}(p_{23}) everywhere on I_{i}.

Thus, similar to the case of the sume w + v, it remains to prove the lower bound on |W_{wv}|. Consider a tensor product of the systems DY_{1} = B_{1}Y_{1}, DY_{2} = B_{2}Y_{2} (see above): DU = (B_{1} ⊗E_{m} +E_{k} ⊗B_{2})U where E_{m}, E_{k} denote the unit matrices of the corresponding sizes. Then the space of solutions of the latter system coincides with the tensor product T_{1} ⊗_{ℝ} T_{2} (cf. e.g. [BBH] ). Hence Wronskian W_{B_{1}⊗E_{m}+E_{k}⊗B_{2}} of this system equals to W_{B_{1}}^{m} W_{B_{2}}^{k} = W_{w}^{m} W_{v}^{k}.

Rewrite (cf. (3)) also the equation Q_{×}z = 0 as a first-order differential system:

DR = J R where J = ( \begin{matrix}0 & 1 & & ◯ \\ & 0 \\ ◯ & & ... & 1 \\ − \frac{ρ^{(0)}}{ρ^{(t)}} & & & − \frac{ρ^{(t−1)}}{ρ^{(t)}} \end{matrix} ). Denote by R (t-dimensional) space of

solutions of the system DR = J R. Consider a mapping Y : T_{1} ⊗ T_{2} → R which maps (…, (D^{ℓ_{1}}w^{(j_{1})})(D^{ℓ_{2}}v^{(j_{2})}), …)_{0≤ℓ_{1}<k, 0≤ℓ_{2}<m} → (…, D^{ℓ}(w^{(j_{1})}v^{(j_{2})}), …)_{0≤ℓ<t}. Obviously, Y is surjective.

The kernel K = ker Y ⊂ T_{1} ⊗ T_{2} is invariant (cf. above and [BBH], [G90b] ), hence any nonsingular linear transformation of the space T_{1} ⊗ T_{2} being of the form \overline{Y} = \binom{∗}{Y}, where ∗ is (km − t) × km matrix over ℝ, reduces (cf. above and [BBH] ) the system DU = (B_{1} ⊗ E_{m} + E_{k} ⊗ B_{2})U to D\overline{U} = \binom{J_{1} 0}{J_{2} J_{3}}\overline{U} where \overline{U} = \overline{Y}U, \binom{J_{1} 0}{J_{2} J_{3}} = (D\overline{Y})(\overline{Y})^{−1} + \overline{Y}(B_{1} ⊗ E_{m} + E_{k} ⊗ B_{2})(\overline{Y})^{−1} and the space of solutions of the system DU_{3} = J_{3}U_{3} coincides with K. The space of solutions of the system DU_{1} = J_{1}U_{1} equals to R, whence W_{J_{1}} = W_{wv}. Therefore, (see the subsection 4.2 above and [H] ) W_{J_{1}} W_{J_{3}} = W\binom{J_{1} 0}{J_{2} J_{3}} = (det \overline{Y}) · W_{B_{1}⊗E_{m}+E_{k}⊗B_{2}} = (det \overline{Y}) · W_{w}^{m} · W_{v}^{k}.

As each coefficient of any vector in the space K ⊂ T_{1} ⊗ T_{2} belongs to \overline{D_{i+1}}, one can construct by lemma 4 the differential polynomials \overline{H}_{K,...,}^{(0)} \overline{H}_{K}^{(æ_{K})} ∈ D_{i} such that if |\overline{H}_{K}^{(0)}| ≥ (exp^{(i)}(p_{24}))^{−1}, |\overline{H}_{K}^{(j)}| ≤ exp^{(i)}(p_{25}) for all j ≥ 0 everywhere on an interval I_{i} (see above), then |W_{J_{3}}| ≤ exp^{(i+1)}(p_{26}) everywhere on I_{i}. As each entry of the matrix \overline{Y} belongs to a quotient field of the ring D_{i}, one can represent det(\overline{Y}) = H̃^{(0)}/H̃^{(1)} where H̃^{(0)}, H̃^{(1)} ∈ D_{i}. Finally, taking H_{wv}^{(0)} = H_{w}^{(0)} H_{v}^{(0)} H̃_{wv}^{(0)} \overline{H}_{K}^{(0)} H̃^{(0)} (see (4)) and as a family H_{wv}^{(1)}, …, H_{wv}^{(æ_{wv})} taking the union of H_{w}^{(j)}, H_{v}^{(j)}, H̃_{wv}^{(j)}, \overline{H}_{K}^{(j)}, H̃^{(0)}, H̃^{(1)} for all j ≥ 0, we obtain (using (5)) that if |H_{wv}^{(0)}| ≥ (exp^{(i)}(p_{27}))^{−1}, |H_{wv}^{(j)}| ≤ exp^{(i)}(p_{28}) for all j ≥ 0 everywhere on I_{i} then

(exp^{(i+1)}(p_{29}))^{−1} ≤ |W_{J_{1}}| = |W_{wv}| ≤ exp^{(i+1)}(p_{23})

everywhere on I_{i}, which completes the proof of the inductive hypothesis for the product wv.

Let us summarize what was proved above in the present section in the following lemma.

Lemma 6. For any differential polynomials G_{0} ∈ D_{i+1}, G_{1}, …, G_{æ} ∈ \overline{D_{i+1}} one can construct differential polynomials 0 ≢ H_{0}, H_{1}, …, H_{η} ∈ D_{i} such that for any polynomials p_{7}, p̃_{i} ∈ P there exists a polynomial p̃_{i+1} ∈ P satisfying the following property: for any x ∈ ℝ if |H_{0}| ≥ (exp^{(i)}(p̃_{i}))^{−1}, |H_{ℓ}| ≤ exp^{(i)}(p̃_{i}), 0 ≤ ℓ ≤ η hold everywhere on an interval I_{i} = (x − (exp^{(i)}(p_{7}(x)))^{−1}, x) (cf. lemma 4 and the remark after it) then |G_{ℓ}| ≤ exp^{(i+1)}(p̃_{i+1}), 0 ≤ ℓ ≤ æ and |W_{G_{0}}| ≥ (exp^{(i+1)}(p̃_{i+1}))^{−1} everywhere on I_{i} where W_{G_{0}} denotes the Wronskian of a certain linear ordinary differential equation ( ∑_{0≤j≤m} \overline{β}^{(j)}D^{j})G_{0} = 0 with the coefficients \overline{β}^{(j)} ∈ D_{i} and with the space of solutions containing G_{0} and having a basis consisting of the elements from \overline{D_{i+1}}.

The proof is conducted by induction on the construction of G_{0} (using lemma 5 for the base of induction), so obtain a family H_{0}^{(0)}, H_{1}^{(0)}, ⋯ ∈ D_{i}, then apply lemma 4 to G_{0}, …, G_{æ}, obtain as a result a family H_{0}^{(1)}, H_{1}^{(1)}, ⋯ ∈ D_{i} and finally combine H_{0} = H_{0}^{(0)} H_{0}^{(1)} and as a family H_{1}, H_{2}, … take the union of both families H_{0}^{(0)} H_{1}^{(0)}, … and H_{0}^{(1)}, H_{1}^{(1)}, . . ..

5. \underline{Lower bound on a differential polynomial in the functions computed by a} \underline{sigmoid}

Lemma 7. Let i ≥ 0. For any differential polynomials 0 ≢ G_{0} ∈ D_{i+1}, G_{1}, …, G_{æ} ∈ \overline{D_{i+1}} one can construct differential polynomials 0 ≢ H_{0}, …, H_{ν} ∈ D_{i} such that for any polynomials p_{7}, p̃_{i} ∈ P there exist polynomials \overline{p_{i+1}}, p_{i+1}^{(0)}, p_{i+1}^{(1)} ∈ P satisfying the following property: for any x ∈ ℝ if |H_{0}| ≥ (exp^{(i)}(p̃_{i}))^{−1}, |H_{e}| ≤ exp^{(i)}(p̃_{i}), 0 ≤ e ≤ ν hold everywhere on an interval I_{i} = (x − (exp^{(i)}(p_{7}(x)))^{−1}, x), then |G_{ℓ}| ≤ exp^{(i+1)}(\overline{p_{i+1}}), 0 ≤ ℓ ≤ æ are valid everywhere on I_{i} and there exists a disjoint family of subintervals {I_{i+1}^{(α)}}_{α} of the interval I_{i} each with the length |I_{i+1}^{(α)}| = (exp^{(i+1)}(p_{i+1}^{(0)}(x)))^{−1}, moreover the lower bound |G_{0}| ≥ (exp^{(i+1)}(\overline{p_{i+1}}))^{−1} holds everywhere on I_{i+1}^{(α)} for each α and finally ∑_{α} |I_{i+1}^{(α)}| ≥ |I_{i}|(1 − (exp^{(i+1)}(p_{i+1}^{(1)}(x)))^{−1}). Moreover, the complement I_{i}\ ∪_{α} I_{i+1}^{(α)} consists of at most exp^{(i)}(p_{i+1}^{(0)}(x)) intervals and G_{0} has at most exp^{(i)}(p_{i+1}^{(0)}(x)) zeros in I_{i}.

Remark 1. One can interpret the lemma 7 informally that the desired lower bound on |G_{0}| holds “almost” everywhere on I_{i}.

Remark 2. Observe that the construction of H_{0}, …, H_{ν} from G_{0}, …, G_{æ} is independent from the intervals and bounds, the similar remark concerns as well the previous lemmas 4, 5, 6.

Proof of lemma 7. Apply lemma 6 to G_{0}, …, G_{æ} and produce H_{0}, …, H_{η}. Then consider an equation 0 = \overline{L}G_{0} = ( ∑_{0≤j≤m} \overline{β}^{(j)}D^{j})G_{0} yielded in lemma 6, where \overline{β}^{(0)}, …, \overline{β}^{(m)} ∈ D_{i}, then DG_{0} satisfies equation 0 = L(DG_{0}) = ( ∑_{0≤j≤m} β^{(j)}D^{j})DG_{0} for suitable differential polynomials β^{(0)}, …, β^{(m)} ∈ D_{i}, β^{(m)} = \overline{β}^{(m)} ≢ 0. Consider any basis G_{0} = G_{0,1}, …, G_{0,m} ∈ \overline{D_{i+1}} of the space of solutions of the equation 0 = \overline{L}G_{0} and apply lemma 4 to a family \{D^{j}G_{0,ℓ}\}_{0≤j≤m−1, 1≤ℓ≤m}. As a result we get a family \overline{H}_{0}, …, \overline{H}_{μ} ∈ D_{i}, set H_{0} = H_{0}\overline{H}_{0}β^{(m)} and as a family H_{1}, …, H_{ν} take the union of H_{0}, …, H_{η}, \overline{H}_{0}, …, \overline{H}_{μ}, β^{(0)} , …, β^{(m)}. Thus by lemmas 4, 6 |β^{(m)}| ≥ (exp^{(i)}(p_{30}))^{−1}, |W_{G_{0}}| ≥ (exp^{(i+1)}(p_{31}))^{−1}, |G_{j}| ≤ exp^{(i+1)}(p_{32}), |D^{j}G_{0,ℓ}| ≤ exp^{(i+1)}(p_{33}), |β^{(ℓ)}| ≤ exp^{(i)}(p_{34}) everywhere on I_{i}. When G_{0} ≡ const, these inequalities give the lemma immediately, so furthermore assume that G_{0} ≢ const.

Similar to the proof of lemma 2 we prove that G_{0} takes each value ε on the interval I_{i} at most max{m + 1, 2 exp^{(i)}((p_{30}p_{34})(x))(m + 1)|I_{i}|} times. Suppose the contrary. Then there is a subinterval I ⊂ I_{i} of the length λ = min\{|I_{i}|, \frac{1}{2}(exp^{(i)}(p_{30}p_{34}(x)))^{−1}\}, in which G_{0} takes value ε at least (m + 1) times. Therefore, each derivative DG_{0}, …, D^{m}G_{0} has at least one root in the interval I. Denote M^{(j)} = max_{y∈I}|D^{j}G_{0}(y)|. Then M^{(j+1)} ≥ \frac{M^{(j)}}{λ} , 1 ≤ j ≤ m. Let |D^{m+1}G_{0}| reach M^{(m+1)} at a point x_{0} ∈ I. Then M^{(m+1)} =

|\frac{1}{β^{(m)}(x_{0})} ( ∑_{0≤j≤m−1} β^{(j)}D^{j+1}G_{0}(x_{0})) | ≤ exp^{(i)}(p_{30}(x_{0}))M^{(m+1)} exp^{(i)}(p_{34}(x_{0}))(λ + λ^{2} +

⋯ + λ^{m}) < M^{(m+1)}. The obtained contradiction proves that G_{0} takes each value ε in the interval I_{i} at most max{m + 1, 2 exp^{(i)}((p_{30}p_{34})(x))(m + 1)|I_{i}|} ≤ exp^{(i)}(p_{35})(x) times for a certain p_{35}.

Construct a sequence of polynomials r_{0}, …, r_{m−1} ∈ K_{0} by (inverse) induction: set r_{m−1} = p_{31} + (m − 1)p_{33} + m^{2} and r_{j} = 2r_{j+1} + p_{33} + 2, 0 ≤ j < m − 1, then r_{0} ≥ r_{1} ≥ ⋯ ≥ r_{m−1} everywhere on ℝ.

Firstly, assume that at some point x_{1} ∈ I_{i} hold inequalities |D^{j}G_{0}(x_{1})| ≤ (exp^{(i+1)}(r_{j} · (x)))^{−1} ≤ (exp^{(i+1)}(r_{m−1}(x)))^{−1} for all 0 ≤ j ≤ m − 1. Then expanding W_{G_{0}} with respect to the column consisting of G_{0}, DG_{0}, …, D^{m−1}G_{0} (as G_{0} ≢ 0 we can assume that G_{0} is one of the elements of a basis of the space of solutions of \overline{L}G = 0) we obtain (exp^{(i+1)}(p_{31}(x)))^{−1} ≤ |W_{G_{0}}(x_{1})| ≤ (exp^{(i+1)}(r_{m−1}(x)))^{−1}m!(exp^{(i+1)}(p_{33}(x)))^{m−1} that contradicts to the choice of r_{m−1}.

Consider a subinterval I^{(0)} ⊂ I_{i} on which |G_{0}| ≤ (exp^{(i+1)}(r_{0}(x)))^{−1} everywhere. Take a minimal 1 ≤ j_{0} ≤ m − 1 (it does exist, see above) such that there exists a point x_{0} ∈ I^{(0)} for which |D^{j_{0}}G_{0}(x_{0})| ≥ (exp^{(i+1)}(r_{j_{0}}(x)))^{−1}. As |D^{j_{0}+1}G_{0}| ≤ exp^{(i+1)}(p_{33}(x)) everywhere on I_{i} we get for each x_{1} ∈ I_{i} |D^{j_{0}}(x_{1})| ≥ |D^{j_{0}}G_{0}(x_{0})| − |x_{1} − x_{0}| exp^{(i+1)}(p_{33}(x)) ≥ (exp^{(i+1)}(r_{j_{0}}(x)))^{−1} − |x_{1} − x_{0}| exp^{(i+1)}(p_{33}(x)). Assume that at least one of two points x_{2} = x_{0} ± (exp^{(i+1)}(r_{j_{0}} + p_{33})(x))^{−1} belongs to I^{(0)}, then |D^{j_{0}−1}G_{0}(x_{0}) − D^{j_{0}−1}G_{0}(x_{2})| =

| ∫_{x_{0}}^{x_{2}} D^{j_{0}}G_{0}| ≥ 1/2(exp^{(i+1)}(r_{j_{0}} + p_{33})(x))^{−1}(exp^{(i+1)}(r_{j_{0}}(x)))^{−1} ≥ 2(exp^{(i+1)}(r_{j_{0}−1}(x)))^{−1}

that leads to a contradiction with the minimality of j_{0}. Hence, neither of two considered points x_{3} belong to I^{(0)}, therefore, the length |I^{(0)}| ≤ 2(exp^{(i+1)}(r_{j_{0}} + p_{33})(x))^{−1} ≤ 2(exp^{(i+1)}(r_{m−1} + p_{33})(x))^{−1} ≤ (exp^{(i+1)}(p_{36}(x)))^{−1} for a certain p_{36}.

Partition the interval I_{i} on the subintervals with the endpoints in which G_{0} takes the values ±(exp^{(i+1)}(r_{0}(x)))^{−1}. By the proved above there are at most 2 exp^{(i)}(p_{35}(x)) such subintervals. Also we’ve proved that the length of any subinterval on which |G_{0}| ≤ (exp^{(i+1)}(r_{0}(x)))^{−1} everywhere, is less than (exp^{(i+1)} p_{36}(x))^{−1}, partitioning all the other subintervals into disjoint subintervals I_{i+1}^{(α)} completes the proof of lemma 7. Now we can formulate the main result of the paper.

Theorem. Let a function 0 ≢ f be computed by a sigmoid of the depth d. For any ρ_{1} there exist ρ_{0}, ρ_{2}, where ρ_{0}, ρ_{1}, ρ_{2} are univariate nonconstant polynomials, being positive everywhere on ℝ such that for any x ∈ ℝ the measure of the points y ∈ (x−(ρ_{1}(x))^{−1}, x) = I at which |f(y)| ≥ exp^{(d)}(ρ_{0}(x)) or |f(y)| ≤ (exp^{(d)} ρ_{0}(x))^{−1}, is less than \frac{(ρ_{1}(x))^{−1}}{exp(ρ_{2}(x))} = \frac{|I|}{exp(ρ_{2}(x))}.

Corollary. The measure of the points y ∈ ℝ for which |f(y)| ≥ exp^{(d)}(ρ_{3}(y)) or |f(y)| ≤ (exp^{(d)} ρ_{3}(y))^{−1} is finite, moreover the measure of such points y with |y| ≥ x_{0} for any x_{0} > 0 is less than exp(−ρ_{4}(x_{0})) for suitable nonconstant polynomials ρ_{3}, ρ_{4} positive everywhere on ℝ.

Remark. Note that all the polynomials occurring in the theorem and the corollary could be calculated explicitly in terms of the size of the sigmoid and in the parameters of the differential equations defining occurring in the sigmoid functions from Γ (see the section 1).

Proof of the theorem. Apply lemma 7 (taking also into account remark 2 just after it) to f, it will produce a family H_{0}^{(d−1)}, …, H_{æ_{d−1}}^{(d−1)} ∈ D_{d−1}, next apply lemma 7 to H_{0}^{(d−1)}, …, H_{æ_{d−1}}^{(d−1)} and obtain as a result a family H_{0}^{(d−2)}, …, H_{æ_{d−2}}^{(d−2)} ∈ D_{d−2} and so on, until we get a family H_{0}^{(0)}, …, H_{æ_{0}}^{(0)} ∈ K_{0} of polynomials.

Let x_{0} > 0 be larger than the absolute values of all the roots of the polynomial H_{0}^{(0)}. Take any polynomial p_{37} ∈ P. We’ll prove by induction on i ≥ 1 that there exist polynomials p̃_{4}^{(i)}, p̃_{5}^{(i)}, p̃_{6}^{(i)} ∈ P such that for any |x| > x_{0} + 1 the subset of the points y ∈ (x − (p_{37}(x))^{−1}, x) = I at which |H_{0}^{(i)}(y)| ≥ (exp^{(i)} p̃_{4}^{(i)}(x))^{−1} and |H_{j}^{(i)}(y)| ≤ (exp^{(i)} p̃_{4}^{(i)}(x)), 0 ≤ j ≤ æ_{i} contains a certain disjoint union of Q^{(i)}(x) ⊂ I of the intervals I_{α}^{(i)} each of the length I_{α}^{(i)}| = (exp^{(i)} p̃_{5}^{(i)}(x))^{−1} and the measure mes (Q^{(i)}(x)) ≥ mes (I) · (1 − (exp p̃_{6}^{(i)}(x))^{−1}).

The base of induction for i = 0 (it is convenient to start with i = 0 although the inductive hypothesis is true for i ≥ 1). In this case for a suitable polynomial p̃_{4}^{(0)} ∈ P the required inequalities |H_{0}^{(0)}(y)| ≥ (p̃_{4}^{(0)}(x))^{−1}, |H_{j}^{(0)}(y)| ≤ p̃_{4}^{(0)}(x) hold everywhere on I, so Q^{(0)} = I and mesQ^{(0)} = mes(I).

For the inductive step take any of the intervals I_{α}^{(i)} and apply to it (and to the family H_{0}^{(i+1)}, …, H_{æ_{i+1}}^{(i+1)}, see above) lemma 7, this will provide polynomials p̃_{4}^{(i+1)}, p̃_{5}^{(i+1)} ∈ P and the necessary intervals which we denote by I_{β}^{(i+1)} (taking the union over all α). By lemma 7 and the inductive hypothesis one gets for i ≥ 1 ∑_{β} |I_{β}^{(i+1)}| ≥ (1 − (exp^{(i+1)}(p_{i+1}^{(1)}(x)))^{−1}) ∑_{α} |I_{α}^{(i)}| ≥ (1 − (exp^{(i+1)}(p_{i+1}^{(1)}(x)))^{−1})(1 − (exp p̃_{6}^{(i)}(x))^{−1})|I| ≥ (1 − (exp p̃_{6}^{(i+1)}(x))^{−1})|I| for a relevant polynomial p̃_{6}^{(i+1)} ∈ P (when i = 0 put p̃_{6}^{(1)} = p̃_{1}^{(1)}), that completes the proof of the theorem.

Following the proofs of lemma 7 (see the end of its proof) and the theorem one can bound the number of zeroes of a function computed by a sigmoid (cf. lemma 2). In the next proposition we agree that exp^{(−1)} ≡ const.

Proposition. Let a function f be computed by a sigmoid of the depth d ≥ 1.

a) For any polynomial ρ_{1} there exist polynomials ρ_{2}, ρ_{5}, where ρ_{2}, ρ_{2}, ρ_{5} are nonconst positive everywhere on ℝ, such that for arbitrary x ∈ ℝ there exists a subset J ⊂ I = (x − (ρ_{1}(x))^{−1}, x) being a union of exp^{(d−2)} ρ_{5}(x) intervals, with the measure less than \frac{|I|}{exp(ρ_{2}(x))} and the number of zeroes of the function f in the set I\J does not exceed exp^{(d−1)} ρ_{5}(x);

b) There exists a set J_{0} ⊂ ℝ with a finite measure such that for arbitrary x ∈ ℝ the number of zeroes of f in the set [0, x]\J_{0} is less than exp^{(d−1)} ρ_{6}(x) for a suitable polynomial ρ_{6}, moreover the intersection [0, x] ∩ J_{0} is a union of at most exp^{(d−2)} ρ_{6}(x) intervals.

Let us demonstrate the sharpness of the bound in the corollary to the theorem. Namely, consider a function f = sin(x) · (exp^{(i)}(x))^{−1}, which can be computed by a sigmoid of the depth i. Then the set of the points y at which |f(y)| ≤ (exp^{(i)} p_{39}(y))^{−1} consists of a union of intervals where n-th interval (n = 0, 1, …) has a length (exp^{(i)} p_{38}(n))^{−1} and contains the point πn (for appropriate polynomials p_{39}, p_{38} ∈ P).

Let us give two applications of the theorem and of the corollary to the questions of approximation of the functions computed by sigmoids. One can treat corollary 2 below as an analogue of Liouvillean theorem (on the algebraic numbers) for the functions computed by sigmoids. Here we consider the growth of the difference of two functions as a measure of their deviation, in particular for the solutions of the linear ordinary differential equations with polynomial coefficients. In the latter case another analogue of Liouvillean theorem for another measure of deviation, namely for the order of the power-series expansions, was ascertained in [CC].

Corollary 2. If different functions f, g are computed by sigmoids with the depths at most d then exp^{(d)}(p_{40}(x)) ≥ |(f − g)(x)| ≥ (exp^{(d)} p_{40}(x))^{−1} for a suitable nonconst polynomial p_{40} positive everywhere on ℝ for all x ∈ ℝ, except for a set with a finite measure.

Another application concerns Blum-Shub-Smale model [BSS]. If one tries to approximate f by BSS-computation, that means the f is approximated by a piecewise rational function. Applying the corollary to the theorem to each piece, we get

Corollary 3. If an irrational function f is computed by a sigmoid with a depth d and a function h is computed by some Blum-Shub-Smale computation then exp^{(d)}(p_{41}(x)) ≥ |(f− h)(x)| ≥ (exp^{(d)} p_{41}(x))^{−1} for an appropriate nonconst polynomial p_{41} positive everywhere on ℝ for all x ∈ ℝ, except for a set with a finite measure.

Actually, both corollaries 2, 3 could be formulated in the stronger ways using the theorem rather than the corollary. One could consider corollary 2 as a lower bound on the parallel complexity (i.e. the depth) of a function, computed by a sigmoid, approximating a given one. Corollary 3 could be treated as a lower bound on the approximation of a function computed by a sigmoid by means of a piecewise rational function. Note also that the bounds in the corollaries 2, 3 are sharp: take f = (exp^{(d)})^{−1} and g = h = 0.

6. \underline{Deviation theorems for elementary sigmoids} Recall (see the section 1) that the considered gate (real) functions u from Γ were defined

everywhere on ℝ (out of a finite number of singular points), and moreover we required that u was the restriction on ℝ of some branch of an analytic complex function.

One can weaken this requirement and consider a function u such that for a certain finite union of (possibly infinite) intervals N ⊂ ℝ the function u is real on N, i.e. u : N → ℝ and u is the restriction on ℝ of some branch of an analytic complex function. We require that at every computational step (2) of the sigmoid the values of the function (f/g)(w_{i}^{(1)}, …, X) should belong to N everywhere on ℝ (out of singularities), thus w_{i+1}^{(j)} : ℝ → ℝ. One can easily (almost literally) extend the proof of the theorem (and the corollary) to this situation.

Under elementary sigmoid we understand a sigmoid in which the role of the gate functions can play exp, log and algebraic functions (in particular, they contain “standard” sigmoids with the gate function (exp(−x) + 1)^{−1}). Each of these gate functions satisfy a certain linear ordinary differential equation with polynomial coefficients. The above requirement when, for example, u = log means that (f/g)(w_{i}^{(1)}, …, X) is positive everywhere on ℝ. Thus, the corollary implies

Corollary 4. Let a function f be computed by an elementary sigmoid with a depth d with the gate functions exp, log and algebraic functions with the requirement that at each computational step of the sigmoid (see (2)) the function u((f/g)(w_{i}^{(1)}, …, X)) takes only real values on ℝ. Then there exists a polynomial p_{42} such that the measure of the points x for which one of the inequalities (exp^{(d)} p_{42}(x))^{−1} ≤ |f(x)| ≤ exp^{(d)} p_{42}(x) fails, is finite.

The statements similar to the remark just after the corollary and to corollaries 2, 3 are true also for the elementary sigmoids.

Acknowledgements The author would like to thank M. Singer for valuable remarks used in the proofs of lemma 1, 6 and G. Schnitger for interesting discussions.

REFERENCES

[BBH] Beukers, F., Brownawell, D., Heckman G., Siegel normality, Ann. Math., 127 (1988), pp. 279–308.

[BSS] Blum, L., Shub, M., Smale, S., On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines, Bull. AMS, 21, 1 (1989), pp. 1–46.

[CC] Chudnovsky, D., Chudnovsky, G., The Wronskian formalism for linear differential equations and

Pade approximations, Adv. Math., 53 (1984), pp. 28–54.

[G90a] Grigoriev, D., Complexity of factoring and GCD calculating of ordinary linear differential operators, J. Symb. Comput., 10 (1990), pp. 7–37.

[G90b] Grigoriev, D., Complexity of irreducibility testing for a system of linear ordinary differential

equations, Proc. Int. Symp. Symb. Alg. Comput., ACM, Tokyo (1990), pp. 225–230.

[H] Hartman, P., Ordinary differential equations, Birkhäuser, 1982.

[K] Kaplansky, I., An introduction to differential algebra, Hermann, 1957.

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

[S81] Singer, M., Liouvillean solutions of n-th order linear differential equations, Amer. J. Math, 103 (1981), pp. 661–682.

[S90] Singer, M., Formal solutions of differential equations, J. Symb. Comput., 10 (1990), pp. 59–94.

Departments of Computer Science and Mathematics Penn State University State College, PA 16802 USA

on leave from Mathematical Institute Fontanka 27 St. Petersburg 191011 RUSSIA