DEVIATION THEOREMS FOR SOLUTIONS OF DIFFERENTIAL EQUATIONS AND APPLICATIONS TO LOWER BOUNDS ON PARALLEL COMPLEXITY OF SIGMOIDS (Extended abstract)

D. Yu. Grigoriev

Departments of Computer Science and Mathematics Pennsylvania State University University Park, PA 16802 USA e-mail: dima@cs.psu.edu

Under a sigmoid with a depth d we understand a circuit with d layers where each real function computed at (i+1)-th layer is obtained as G(q) where q is a rational expression in the functions computed at i-th layer and G is a gate operator from some admitted family. Two types of the families of gate operators are considered: first, we admit to substitute g(q) where g is a solution of a linear ordinary differential equation with the polynomial coefficients and second, as G(q) we take a solution of nonlinear first-order differential equation. The sigmoids of the first type compute any composition of the functions like exp, log, sin (thus, it includes, in particular, standard sigmoids corresponding to the gate g = (1 + exp(−x))^{−1}), the sigmoids of the second type compute Pfaffian functions. The main result states that if two different functions f_{1}, f_{2} are computed by means of the sigmoids with the parallel complexity d, then the difference |f_{1} − f_{2}| grows not slower than (exp^{(d)}(p))^{−1} (and not faster than exp^{(d)}(p)) where exp^{(d)} is d times iteration of the exponential function and p is a certain polynomial, thus one can not rather good approximate f_{1} with a precise parallel complexity d by means of a function f_{2} with a less parallel complexity. Also we estimate the number of zeroes in the intervals of a function computed by a sigmoid of the first type. All the obtained bounds are sharp.

Typeset by AMS-TEX

1. Deviation theorems for the functions computed by sigmoids.

Denote the ring K_{0} = ℝ[X], F_{0} = ℝ(X), D = d/dX. By Γ denote the set of real functions u : ℝ → ℝ being solutions of linear ordinary differential equations of the kind

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

where the coefficients a_{j} ∈ F_{0} are defined everywhere on ℝ, in other words, their denominators have no real roots. The elements of Γ will play the role of gate functions in the sigmoids. As the operator L has no real singularities ([H]), the function u is analytic on ℝ (actually, one could get rid of this requirement and consider gate functions with real singularities, but we shall not dwell on it for the sake of simplifying the exposition). Now we define K_{i} and F_{i} by induction on i, namely K_{i+1} for i ≥ 0 is a differential ring [K] generated by the functions of the form u(q) where u ∈ Γ and q ∈ F_{i}. Define F_{i+1} as a (differential) field of quotients of K_{i+1}.

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

w_{i+1}^{(j)} = u((g_{1}/g_{2})(w_{i}^{(1)}, w_{i}^{(2)}, …, X))  (2)

for a certain gate function u ∈ Γ and g_{1}, g_{2} ∈ ℝ[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.

Let u = u_{1}, …, u_{n} where u_{ℓ} : ℝ → ℝ, 1 ≤ ℓ ≤ n be a basis (over ℝ) of the space of solutions of the equation (1) [H]. Extend the sigmoid without changing its depth adding also the instructions u_{ℓ}((g_{1}/g_{2})(w_{i}^{(1)}, w_{i}^{(2)}, …, X)) at (i + 1)-th layer. One can show by induction on i that each function w_{i+1}^{(j)} belongs to K_{i+1} (and conversely, any element from K_{i+1} can be obtained as a polynomial in the functions computed at (i + 1)-th layer of a suitable sigmoid). Usually, u is taken from a certain subset 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 ℝ(X) 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)} . . .. Denote by exp^{(d)} ∈ K_{d} the iteration of the exponential function d times. Now we are able to formulate the first main result of the paper (deviation theorem for the functions computed by sigmoids).

Theorem 1. Let a function 0 ≢ f be computed by a sigmoid with a depth d. For any ρ_{1} there exist ρ_{0}, ρ_{2} where ρ_{0}, ρ_{1}, ρ_{2} ∈ K_{0} are univariate nonconstant polynomials, being positive everywhere on ℝ such that for any x ∈ ℝ the measure of the points y from an interval I = (x − (ρ_{1}(x))^{−1}, x) 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 1. 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 point y with |y| ≥ x_{0} for any x_{0} ≥ 0 is less than (exp ρ_{4}(x_{0}))^{−1} for suitable nonconstant polynomials ρ_{3}, ρ_{4} ∈ K_{0} being positive everywhere on ℝ.

Remark 1. The polynomials ρ_{0}, ρ_{2}, ρ_{3}, ρ_{4} could be calculated explicitly in terms of the size of the sigmoid and in the coefficients a_{j} of the differential operators L (see (1)) to which satisfy the gate functions u occuring in the sigmoid.

Remark 2. The bounds in the theorem 1 and in the corollary 1 are sharp. As an example consider a function f = sin ·(exp^{(d)})^{−1} with the parallel sigmoidal complexity equal to d: the set of the points y at which |f(y)| ≤ (exp^{(d)} ρ_{5}(y))^{−1} consists of a union of intervals where n-th interval (n = 0, 1, …) has a length (exp^{(d)} ρ_{6}(n))^{−1} and contains the point πn (for appropriate polynomials ρ_{5}, ρ_{6} ∈ K_{0}).

One can treat the theorem 1 and the corollary 1 as the impossibility of “rather good” approximation of a function with the parallel sigmoidal complexity d by means of a function with less parallel complexity (in particular, by a rational function), thus if such an approximation does exist, it gives a lower bound on the parallel sigmoidal complexity.

The corollary 1 could be easily extended to the sigmoids with branching instructions as the resulting function would be piecewise and one could apply the corollary to each piece. In particular, when we consider only rational computations, it gives a lower bound (the similar as in the corollary 1) on the approximation by means of Blum-Shub-Smale computation ([BSS]).

Finally, we estimate the number of zeroes of a function computed by a sigmoid.

In the next proposition let us adopt a convention that exp^{(−1)} ≡ const.

Proposition. Let a function f be computed by a sigmoid with a depth d ≥ 1. There exists a set J ⊂ ℝ with a finite measure such that for any x ∈ ℝ the number of zeroes of f in the set [0, x] ∖ J does not exceed exp^{(d−1)} ρ_{7}(x) for a suitable polynomial ρ_{7} ∈ K_{0}, moreover the intersection [0, x] ∩ J is a union of at most exp^{(d−2)} ρ_{7}(x) intervals.

2. Upper bounds on the functions computed by sigmoids.

¿From now on p_{1}, p_{2}, … will denote polynomials from K_{0} each having a form p_{j} = \overline{p_{j}}(X^{2}) where a polynomial \overline{p_{j}} monotonically increases on ℝ^{+} and \overline{p_{j}}(0) ≥ 1. The proof of the following lemma is based on the Gronwall’s inequality [H]. Let u satisfy (1).

Lemma 1. For each j ≥ 0 there exists a polynomial p_{j}^{(0)} such that |D^{j}u| ≤ exp(p_{j}^{(0)}).

The proof of the theorem 1 is conducted by induction on d. The next lemma serves to get upper bounds in the inductive step, its proof relies on (2) and lemma 1.

Lemma 2. Let 0 ≤ i < d. For a family of differential polynomials G_{1}, …, G_{k} ∈ D_{i+1} one can produce a family of differential polynomials 0 ≢ H_{0}, …, H_{m} ∈ D_{i} such that for every p_{1}, p_{2} there exists p_{3} satisfying the following property: for arbitrary x ∈ ℝ if the inequalities |H_{0}| ≥ (exp^{(i)}(p_{2}))^{−1}, |H_{j}| ≤ exp^{(i)}(p_{2}), 0 ≤ j ≤ m hold everywhere on an interval I_{i} = (x − (exp^{(i)} p_{1}(x))^{−1}, x) then |G_{ℓ}| ≤ exp^{(i+1)}(p_{3}), 1 ≤ ℓ ≤ k everywhere on I_{i}.

3. Upper and lower bounds on Wronskians of the functions computed by sigmoids.

Denote by W_{u} the Wronskian of (1) (see [H])

W_{u} = det ( \begin{matrix}u_{1} & … & u_{n} \\ Du_{1} & … & Du_{n} \\ ⋮ & & ⋮ \\ D^{n−1}u_{1} & … & D^{n−1}u_{n} \end{matrix} )

As W_{u}(x) = W_{u}(x_{0}) exp ∫_{x_{0}}^{x}(−a_{n−1}) ([H]) we get the following lemma.

Lemma 3. For a suitable p_{4} (exp p_{4})^{−1} ≤ |W_{u}| ≤ exp p_{4}.

A function w = w_{i+1}^{(j)} (see (2)) computed by the sigmoid, satisfies a linear ordinary dif-

ferential equation 0 = ( ∑_{0≤ℓ≤n}b_{ℓ}D^{ℓ}) w with the coefficients b_{ℓ} ∈ D_{i}. Without loss of gen-

erality we can assume that w ≢ const, then u_{1}((g_{1}/g_{2})(w_{i}^{(1)}, w_{i}^{(2)}, …, X)), …, u_{n}((g_{1}/g_{2}) (w_{i}^{(1)}, w_{i}^{(2)}, …, X)) ∈ D_{i+1} (see (2)) constitute a basis (over ℝ) of the space of solutions of this equation. Denote by W_{w} the Wronskian of this equation. One can prove the following lemma using lemma 3 and the identity

W_{w} = W_{u}((g_{1}/g_{2})(w_{i}^{(1)}, w_{i}^{(2)}, …, X)) · (D((g_{1}/g_{2})(w_{i}^{(1)}, w_{i}^{(2)}, …, X)))^{n(n−1)/2}

Lemma 4. For each function const ≢ w = w_{i+1}^{(j)} computed by the sigmoid (see (2)) one can produce differential polynomials 0 ≢ H_{0}^{(w)}, …, H_{s}^{(w)} ∈ D_{i} such that for every p_{1}, p_{5} there exists p_{6} satisfying the following property: for arbitary x ∈ ℝ if the inequalities |H_{0}^{(w)}| ≥ (exp^{(i)} p_{5})^{−1}, |H_{j}^{(w)}| ≤ exp^{(i)}(p_{5}), 0 ≤ j ≤ s hold everywhere on an interval I_{i} = (x − (exp^{(i)} p_{1}(x))^{−1}, x) then the Wronskian W_{w} satisfies inequalities

(exp^{(i+1)}(p_{6}))^{−1} ≤ |W_{w}| ≤ exp^{(i+1)}(p_{6}) everywhere on I_{i}.

Let a differential polynomial G ∈ D_{i+1}. Then G satisfies a certain linear ordinary

differential equation 0 = LG = ( ∑_{0≤j≤m}h_{j}D^{j}) G with the coefficients h_{j} ∈ D_{i} and with a

basis (over ℝ) of the space of solutions from D_{i+1} (one could produce the operator L by induction on the construction of G, see [S]). Denote by W_{G} the Wronskian of the operator L. The main purpose of this section is to establish the bounds on W_{G}. An upper bound is provided by applying lemma 2 to W_{G} and getting a family H̃_{0}, …, H̃_{m_{1}} ∈ D_{i}, a lower bound is proved by induction on the construction of G (so, on the number of operations of differentiating, adding and multiplying), lemma 4 gives the base of this induction.

To prove the inductive step we assume that two functions v_{1}, v_{2} ∈ D_{i+1} satisfy linear ordinary differential equations 0 = Q_{1}v_{1} = Q_{2}v_{2}, where Q_{1} = ∑_{0≤ℓ≤k_{1}}α^{(ℓ)}D^{ℓ}, Q_{2} =

∑_{0≤ℓ≤k_{1}}β^{(ℓ)}D^{ℓ} and the coefficients α^{(ℓ)}, β^{(ℓ)} ∈ D_{i}. We assume also that by induction some

differential polynomials 0 ≢ H_{0}^{(v_{1})}, …, H_{æ_{1}}^{(v_{1})}, 0 ≢ H_{0}^{(v_{2})}, …, H_{æ_{2}}^{(v_{2})} ∈ D_{i} are produced such that for every p_{7} there exists p_{8} satisfying the following property for any x ∈ ℝ: if

|H_{0}^{(v_{1})}|, |H_{0}^{(v_{2})}| ≥ (exp^{(i)} p_{7})^{−1}; |H_{j}^{(v_{1})}|, |H_{j}^{(v_{2})}| ≤ exp^{(i)} p_{7}  (3)

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

(exp^{(i+1)} p_{8})^{−1} ≤ |W_{v_{1}}|, |W_{v_{2}}| ≤ exp^{(i+1)} p_{8}  (4)

everywhere on I_{i}, here W_{v_{1}}, W_{v_{2}} denote the Wronskians of the operators Q_{1}, Q_{2}, resp.

One can produce (cf. [S]) the linear ordinary differential operators Q_{D}, Q_{+}, Q_{×} of the minimal orders with the coefficients from D_{i}, namely, being differential polynomials in α^{(ℓ)}, β^{(ℓ)} and with basis of the spaces of solutions from D_{i+1} such that 0 = Q_{D}(D\overline{v}_{1}) = Q_{+}(\overline{v}_{1} +\overline{v}_{2}) = Q_{×}(\overline{v}_{1}\overline{v}_{2}) for all the solutions of the equations 0 = Q_{1}\overline{v}_{1} = Q_{2}\overline{v}_{2}. The main task is to estimate their Wronskians W_{Dv_{1}}, W_{v_{1}+v_{2}}, W_{v_{1}v_{2}}, that would prove bounds (4) for the inductive step. As estimating W_{Dv_{1}} is comparatively easy and on the other hand considering W_{v_{1}+v_{2}} and W_{v_{1}v_{2}} are similar, let us dwell on estimating W_{v_{1}+v_{2}}.

Replace the equations 0 = Q_{1}\overline{v}_{1} = Q_{2}\overline{v}_{2} = Q_{+}(\overline{v}_{1}+\overline{v}_{2}) by the corresponding first-order linear systems DV_{1} = A_{1}V_{1}, DV_{2} = A_{2}V_{2}, DV_{+} = A_{+}V_{+}, resp. where the matrix

A_{1} = ( \begin{matrix}0 & 1 & & ◯ \\ & 0 & ... \\ & ◯ & & 1 \\ −\frac{α^{(0)}}{α^{(k_{1})}} & −\frac{α^{(1)}}{α^{(k_{1})}} & ⋯ & −\frac{α^{(k_{1}−1)}}{α^{(k_{1})}} \end{matrix}  )

is in the Frobenius form (see [H]), the similar for A_{2}, A_{+}. Denote by V_{1}, V_{2}, V_{+} the corresponding spaces (over ℝ) of solutions of the linear systems. Consider a natural epimorphism σ : V_{1} ⊕ V_{2} → V_{+} mapping σ((v_{1}^{(j_{1})}, Dv_{1}^{(j_{1})}, …, D^{k_{1}−1}v_{1}^{(j_{1})}) ⊕ (v_{2}^{(j_{2})}, Dv_{2}^{(j_{2})}, …, D^{k_{2}−1}v_{2}^{(j_{2})})) → (v_{1}^{(j_{1})}+v_{2}^{(j_{2})}, D(v_{1}^{(j_{1})}+v_{2}^{(j_{2})}), D^{2}(v_{1}^{(j_{1})}+v_{2}^{(j_{2})}), …). The direct sum V_{1}⊕V_{2}

is the space of solutions of the system DV = ( \begin{matrix}A_{1} & 0 \\ 0 & A_{2} \end{matrix} ) V. The subspace Ker(σ) ⊂ V_{1}⊕V_{2} is invariant under the differential Galois group of the latter system (see [K], also [BBH], [G90b]). Therefore, any nonsingular linear transformation of the space V_{1} ⊕ V_{2} being of

the form \overline{σ} = ( \begin{matrix}∗ \\ σ \end{matrix} ) where ∗ is a matrix with the entries from ℝ reduces (see e.g. [BBH])

the system DV = ( \begin{matrix}A_{1} & 0 \\ 0 & A_{2} \end{matrix} ) V to the block-triangular form D\overline{V} = ( \begin{matrix}C_{1} & 0 \\ C_{2} & C_{3} \end{matrix} ) \overline{V}, where

\overline{V} = \overline{σ}V. The space of solutions of the system DV_{3} = C_{3}V_{3} coincides with Ker(σ) and the space of solutions of the system D\overline{V}_{1} = C_{1}\overline{V}_{1} equals to V_{+} (in [G90a], [G90b] one can find the complexity bounds on reducing a system to the block-triangular form).

Using the formula for the Wronskian W_{C_{1}} = exp ∫ trC_{1} ([H]), we obtain equalities

W_{C_{1}}W_{C_{3}} = W( \begin{matrix}C_{1} & 0 \\ C_{2} & C_{3} \end{matrix} ) = (det \overline{σ}) · W( \begin{matrix}B_{1} & 0 \\ 0 & B_{2} \end{matrix} ) = (det \overline{σ})W_{v_{1}}W_{v_{2}}.

As the coefficients of the vectors from Ker(σ) ⊂ V_{1} ⊕ V_{2} belong to D_{i+1} one can apply to them lemma 2 and get a family H_{0}^{(σ)}, …, H_{m_{2}}^{(σ)} ∈ D_{i}. Also det(\overline{σ}) = \overline{H}_{0}/\overline{H}_{1} for suitable \overline{H}_{0}, \overline{H}_{1} ∈ D_{i}. Finally, using (3) we take H_{0}^{(v_{1}+v_{2})} = H_{0}^{(v_{1})} · H_{0}^{(v_{2})} · H̃_{0} · H_{0}^{(σ)} · \overline{H}_{0} and as H_{1}^{(v_{1}+v_{2})}, … we take the union of H_{j}^{(v_{1})}, H_{j}^{(v_{2})}, H̃_{j}, H_{j}^{(σ)}, \overline{H}_{0}, \overline{H}_{1} for all j ≥ 0 and using (4) prove the inductive step for v_{1} + v_{2}. Namely, for every p_{9} there exists p_{10} satisfying the following property: for any x ∈ ℝ (cf. (3), (4)) if |H_{0}^{(v_{1}+v_{2})}| ≥ (exp^{(i)}(p_{9}))^{−1}, |H_{j}^{(v_{1}+v_{2})}| ≤ exp^{(i)}(p_{9}) for all j ≥ 0 everywhere on an interval I_{i} then (exp^{(i+1)}(p_{10}))^{−1} ≤ |W_{v_{1}+v_{2}}| ≤ exp^{(i+1)}(p_{10}) everywhere on I_{i}.

This completes the consideration of the inductive step for the sum v_{1} + v_{2}. The bound on W_{v_{1}v_{2}} is proved in a similar way, the role of the direct sum V_{1} ⊕ V_{2} is being

replaced by the tensor product V_{1} ⊗_{ℝ} V_{2} and the role of the matrix ( \begin{matrix}A_{1} & 0 \\ 0 & A_{2} \end{matrix} ) is played

by A_{1} ⊗ E_{k_{2}} + E_{k_{1}} ⊗ A_{2} where E_{k_{1}} denotes the unit k_{1} × k_{1} matrix.Thus, by induction on the construction of the differential polynomial G ∈ D_{i+1} we get the following lemma.

Lemma 5. For every differential polynomials G_{0} = G, G_{1}, …, G_{æ} ∈ D_{i+1} one can produce differential polynomials 0 ≢ H_{0}, …, H_{η} ∈ D_{i} such that for any polynomials p_{1}, p_{11} there exists a polynomial p_{12} satisfying the following property: for arbitrary x ∈ ℝ if |H_{0}| ≥ (exp^{(i)} p_{11})^{−1}, |H_{ℓ}| ≤ exp^{(i)} p_{11}, 0 ≤ ℓ ≤ η hold everywhere on an interval I_{i} = (x − (exp^{(i)} p_{1}(x))^{−1}, x) (cf. lemmas 2,4) then |G_{ℓ}| ≤ exp^{(i+1)}(p_{12}), 0 ≤ ℓ ≤ æ and |W_{G}| ≥ (exp^{(i+1)} p_{12})^{−1} everywhere on I_{i}, where W_{G} denotes the Wronskian of a certain linear

ordinary differential equation 0 = ( ∑_{0≤j≤m}γ^{(j)}D^{j}) G with the coefficients γ^{(j)} ∈ D_{i} and

with a basis (over ℝ) of the space of solutions G_{0,0,...,}G_{0,m−1} ∈ D_{i+1}.

4. Lower bounds on functions computed by a sigmoid.

Relying on a lower bound on the Wronskian W_{G} (see lemma 5) one can obtain a lower bound on a differential polynomial 0 ≢ G ∈ D_{i+1} Lemma 6. For every differential polynomials 0 ≢ G_{0} = G, G_{1}, …, G_{æ} ∈ D_{i+1} one can produce differential polynomials 0 ≢ H_{0}, …, H_{ν} ∈ D_{i} such that for any polynomials p_{1}, p_{13} there exist polynomials p_{14}, p_{15}, p_{16} satisfying the following property: for arbitrary x ∈ ℝ if |H_{0}| ≥ (exp^{(i)} p_{13})^{−1}, |H_{ℓ}| ≤ exp^{(i)} p_{13}, 0 ≤ ℓ ≤ ν hold everywhere on an interval I_{i} = (x − (exp^{(i)} p_{1}(x))^{−1}, x), then |G_{ℓ}| ≤ exp^{(i+1)} p_{14} 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_{15}(x))^{−1}, moreover the lower bound |G| ≥ (exp^{(i+1)} p_{14}(x))^{−1} holds everywhere on I_{i+1}^{(α)} for each α and finally ∑_{α}|I_{i+1}^{(α)}| ≥ |I_{i}|(1 − (exp^{(i+1)} p_{16}(x))^{−1}). In

addition, the complement I_{i} ∖ ∪_{α}I_{i+1}^{(α)} consists of at most exp^{(i)} p_{15}(x) intervals and G has at most exp^{(i)} p_{15}(x) zeroes in I_{i}.

The latter inequality informally means that the desired lower bound on |G| holds “almost everywhere” on I_{i}.

To prove lemma 6 first apply lemma 5 to G_{0}, …, G_{æ} and produce H_{0}, …, H_{η}. Then taking an equation 0 = ( ∑_{0≤j≤m}γ^{(j)}D^{j})G from lemma 5 produce an equation 0 = ( ∑_{0≤j≤m}

σ^{(j)}D^{j})DG with the coefficients σ^{(j)} ∈ D_{i}, γ^{(m)} = σ^{(m)} ≢ 0. Apply lemma 2 to a family \{D^{j}G_{0,ℓ}\}_{0≤j,ℓ≤m−1} (see lemma 5) and get a family \overline{H}_{0}, …, \overline{H}_{μ} ∈ D_{i}. As the required in the lemma differential polynomials take H_{0} = H_{0}\overline{H}_{0}σ^{(m)} and as H_{1}, …, H_{ν} take the union of H_{0}, …, H_{η}, \overline{H}_{0}, …, \overline{H}_{μ}, σ^{(0)}, …, σ^{(m)}. Hence lemmas 2, 5 imply the existence of polynomials p_{17}, p_{18}, p_{19}, p_{20} such that inequalities |σ^{(m)}| ≥ (exp^{(i)} p_{17})^{−1}, |W_{G}| ≥ (exp^{(i+1)} p_{18})^{−1}, |G_{ℓ}| ≤ exp^{(i+1)} p_{19}, |D^{j}G_{0,ℓ}| ≤ exp^{(i+1)} p_{20}, |β^{(ℓ)}| ≤ exp^{(i)} p_{17} hold everywhere on I_{i}. When G ≡ const, these inequalities give the lemma, so assume that G ≢ const.

We claim that G takes every value ϵ in the interval I_{i} at most max{m + 1, 2(m + 1)|I_{i}| exp^{(i)} p_{17}^{2}(x)} times. Suppose the contrary. Then there exists a subinterval I ⊂ I_{i} of a length λ = min{|I_{i}|, (2 exp^{(i)} p_{17}^{2}(x))^{−1}} in which G takes value ϵ at least m + 1 times. Therefore, each derivative DG, …, D^{m}G has a least one root in the interval I. Denote M^{(j)} = max_{y∈I} |D^{j}G(y)|. Then λM^{(j+1)} ≥ M^{(j)}, 1 ≤ j ≤ m. Let D^{m+1}G reach

M^{(m+1)} at a point y_{0} ∈ I. Then M^{(m+1)} = |(σ^{(m)}(y_{0}))^{−1} ( ∑_{0≤j≤m−1}σ^{(j)}D^{j+1}G(y_{0}))| ≤

(exp^{(i)} p_{17}(x))^{2}M^{(m+1)} (λ + λ^{2} + ⋯ + λ^{m}) < M^{(m+1)}, the contradiction proves the claim.

Construct a sequence of polynomials r_{0}, …, r_{m−1} ∈ K_{0} by (inverse) induction: set r_{m−1} = p_{18} + (m − 1)p_{20} + m^{2}, and r_{j} = 2r_{j+1} + p_{20} + 2, 0 ≤ j < m − 1, then r_{0} ≥ r_{1} ≥ ⋯ ≥ r_{m−1} everywhere on ℝ. First, assume that at some point x_{1} ∈ I_{i} inequalities |D^{j}G(x_{1})| ≤ (exp^{(i+1)} r_{j}(x))^{−1} ≤ (exp^{(i+1)} r_{m−1}(x))^{−1} hold for all 0 ≤ j ≤ m − 1. Then expanding Wronskian W_{G} with respect to the column consisting of G, DG, …, D^{m−1}G (as G ≢ 0 we can take G as one of the elements of a basis of the space of solutions of 0 = ( ∑_{0≤j≤m}γ^{(j)}D^{j})G we obtain inequalities (exp^{(i+1)} p_{18}(x))^{−1} ≤ |W_{G}(x_{1})| ≤ (exp^{(i+1)} r_{m−1}(x))^{−1}m!(exp^{(i+1)} p_{20}(x))^{m−1}, that contradicts to the choice of r_{m−1}.

Consider a subinterval I^{(0)} ⊂ I_{i} on which |G| ≤ (exp^{(i+1)} r_{0}(x))^{−1} everywhere. Take the minimal 1 ≤ j_{0} ≤ m−1 such that there exists a point x_{0} ∈ I^{(0)} for which |D^{j_{0}}G(x_{0})| ≥ (exp^{(i+1)} r_{j_{0}}(x))^{−1}. Since |D^{j_{0}+1}G| ≤ exp^{(i+1)} p_{20}(x) everywhere on I_{i} we get for arbitrary x_{2} ∈ I_{i} inequalities |D^{j_{0}}G(x_{2})| ≥ |D^{j_{0}}G(x_{0})| − |x_{2} − x_{0}| exp^{(i+1)} p_{20}(x) ≥ (exp^{(i+1)} r_{j_{0}}(x))^{−1} − |x_{2} − x_{0}| exp^{(i+1)} p_{20}(x). Assume that at least one of two points x_{3} = x_{0} ± (exp^{(i+1)}(r_{j_{0}} +p_{20})(x))^{−1} belong to I^{(0)}, then |D^{j_{0}−1}G(x_{0})−D^{j_{0}−1}G(x_{3})| = | ∫_{x_{0}}^{x_{3}} D^{j_{0}}G| ≥ (2 exp^{(i+1)}(r_{j_{0}} + p_{20})(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}. Thus, neither of two considered points belong to I^{(0)}, therefore, |I^{(0)}| ≤ 2(exp^{(i+1)}(r_{j_{0}} + p_{20})(x))^{−1}.

Partition the interval I_{i} on the subintervals with the endpoints in which G takes the values ±(exp^{(i+1)} r_{0}(x))^{−1}. By the proved above there are at most 2 max{m + 1, 2(m + 1)|I_{i}| exp^{(i)} p_{17}^{2}(x)} such subintervals. Also we have proved that the length of any subinterval on which |G| ≤ (exp^{(i+1)} r_{0}(x))^{−1} everywhere, is less than 2(exp^{(i+1)}(r_{j_{0}} + p_{20})(x))^{−1} (this is used in the proof of the proposition from the section 1), partitioning all the other subintervals into disjoint subintervals I_{i+1}^{(α)} completes the proof of lemma 6.

Finally, one can prove theorem 1 (and as well the proposition). First, apply lemma 6 to i = d − 1 and a family of differential polynomials consisting of a single element f ∈ D_{d}, then to the obtained family from D_{d−1} and i = d − 2 again apply lemma 6 and so on decreasing i until we get a family of the rational functions from D_{0} = ℝ(X). Then we ascertain the necessary bounds by induction on (increasing i) again using lemma 6 for the inductive step.

5. Deviation theorems for the functions computed by Pfaffian sigmoids. Consider another class of sigmoids which are called Pfaffian and which also contain, in

particular, “standard” sigmoids. Denote the field P_{0} = ℝ(X), then by induction on i the field P_{i+1} is generated over P_{i} by all the functions v_{i+1}^{(j)} : ℝ → ℝ (possibly having a finite number of singularities) satisfying first-order nonlinear differential equations of the form

D v_{i+1}^{(j)} = q(v_{i+1}^{(j)})  (5)

where a polynomial q(Z) ∈ P_{i}[Z]. Obviously exp^{(i)} ∈ P_{i}.

According to [Kh] any function f ∈ P_{i}, being Pfaffian, has a finite number of singularities and roots. Hence for every two functions f_{1}, f_{2} ∈ P_{i}, f_{1} ≢ f_{2}, the difference (f_{1}−f_{2})(x) is either positive or negative everywhere on an interval x ∈ [x_{0}, ∞) for a certain x_{0} ∈ ℝ, we write f_{1} ≻ f_{2} or f_{1} ≺ f_{2}, respectively. Now we can formulate the deviation theorem for Pfaffian sigmoids.

Theorem 2. For any function 0 ≢ f ∈ P_{i} there exists a polynomial p_{21} such that

(exp^{(i)} p_{21})^{−1} ≺ |f| ≺ exp^{(i)} p_{21}

The bounds are obviously sharp. For Pfaffian sigmoids the necessary bounds are valid starting with some point x_{0} unlike corollary 1 where the bounds were valid out of a finitemeasure set. Analogues of the remark 1 and the remark concerning Blum-Shub-Smale model are true also for Pfaffian sigmoids.

The theorem is proved by induction on i and firstly we prove an upper bound (for i = 0 one can find its proof in [B]).

Lemma 7. Assume that the statement of the theorem 2 is proved for P_{i} and v_{i+1}^{(j)} satisfies (5) where deg(q) = n. Then for an appropriate polynomial p_{22}

a) if n = 0 or n ≥ 2 then |v_{i+1}^{(j)}| ≺ exp^{(i)} p_{22}

b) if n = 1 then |v_{i+1}^{(j)}| ≺ exp^{(i+1)} p_{22}

Let each of the functions v_{i+1}^{(j_{1})}, …, v_{i+1}^{(j_{m})} ∈ P_{i+1} satisfy an equation similar to (5), namely Dv_{i+1}^{(j_{ℓ})} = q_{ℓ}(v_{i+1}^{(j_{ℓ})}). Then for any polynomial 0 ≢ h ∈ P_{i}[Z_{1}, …, Z_{m}] the bound |h(v_{i+1}^{(j_{1})}, …, v_{i+1}^{(j_{m})})| ≺ exp^{(i+1)} p_{23} holds for a suitable polynomial p_{23} because of lemma 7. Thus, to prove theorem 2 it remains to prove a lower bound on h(v_{i+1}^{(j_{1})}, …, v_{i+1}^{(j_{m})}) ∈ P_{i+1}.

Firstly, we consider the case when v_{i+1}^{(j_{1})}, …, v_{i+1}^{(j_{m})} are algebraically independent over P_{i}. Suppose that |h(v_{i+1}^{(j_{1})}, …, v_{i+1}^{(j_{m})})| ≺ (exp^{(i+1)} p)^{−1} for all the polynomials p. Then we say that h(v_{i+1}^{(j_{1})}, …, v_{i+1}^{(j_{m})}) is small. Also we suppose that m is the least possible with this property. Finally, without loss of generality, one can suppose that the polynomial h is irreducible over P_{i}.

Since the derivative D(h(v_{i+1}^{(j_{1})}, …, v_{i+1}^{(j_{m})})) = ∑_{1≤ℓ≤m}_{\frac{∂h}{∂v_{i+1}^{(j_{ℓ})}}} q_{ℓ}(v_{i+1}^{(j_{ℓ})}) = g(v_{i+1}^{(j_{1})}, …, v_{i+1}^{(j_{m})})

∈ P_{i+1} for a certain polynomial g ∈ P_{i}[Z_{1}, …, Z_{m}], the derivative should be also small (as being also a Pfaffian function). If h ∤ g in the ring P_{i}[Z_{1}, …, Z_{m}] then there exist polynomials h_{1}, g_{1} ∈ P_{i}[Z_{1}, …, Z_{m}] such that 0 ≢ hh_{1} +gg_{1} ∈ P_{i}[Z_{1}, …, Z_{m−1}]. But then the function (hh_{1} + gg_{1})(v_{i+1}^{(j_{1})}, …, v_{i+1}^{(j_{m})}) is small by virtue of lemma 7, this contradicts to the choice of m.

Now let g = h g_{0} for some g_{0} ∈ P_{i}[Z_{1}, …, Z_{m}]. Consider any 1 ≤ ℓ ≤ m for which deg_{Z}(q_{ℓ}) ≤ 1, then for each 1 ≤ s ≤ m

deg_{v_{i+1}^{(j_{ℓ})}} (\frac{∂h}{∂v_{i+1}^{(j_{s})}} q_{s}(v_{i+1}^{(j_{s})})) ≤ deg_{v_{i+1}^{(j_{ℓ})}}(h(v_{i+1}^{(j_{1})}, …, v_{i+1}^{(j_{m})}))

and therefore, Z_{ℓ} does not occur in the polynomial g_{0}. If for some 1 ≤ ℓ ≤ m deg_{Z}(q_{ℓ}) ≥ 2 then lemma 7 entails that |v_{i+1}^{(j_{ℓ})}| ≺ exp^{(i)} p_{23} for a suitable polynomial p_{23}. Hence |g_{0}(v_{i+1}^{(j_{1})}, …, v_{i+1}^{(j_{m})})| ≺ exp^{(i)} p_{24} for a certain p_{24}. Thus |D(h(v_{i+1}^{(j_{1})}, …, v_{i+1}^{(j_{m})}))/ h(v_{i+1}^{(j_{1})}, …, v_{i+1}^{(j_{m})})| ≺ exp^{(i)} p_{24}, therefore | log |h(v_{i+1}^{(j_{1})}, …, v_{i+1}^{(j_{m})})| | ≺ exp^{(i)} p_{25} for an appropriate p_{25} and finally |h(v_{i+1}^{(j_{1})}, …, v_{i+1}^{(j_{m})})| ≻ (exp^{(i+1)} p_{25})^{−1}, this contradicts to the supposition that h(v_{i+1}^{(j_{1})}, …, v_{i+1}^{(j_{m})}) is small.

In the general case choose some transcendental over P_{i} basis (let it be v_{i+1}^{(j_{1})}, …, v_{i+1}^{(j_{s})})

among v_{i+1}^{(j_{1})}, …, v_{i+1}^{(j_{m})}. Then there exists a polynomial t(Y) = ∑_{0≤ℓ≤k}t^{(ℓ)}Y^{ℓ} ∈

P_{i}[v_{i+1}^{(j_{1})}, …, v_{i+1}^{(j_{s})}][Y] with the coefficients t^{(ℓ)} ∈ P_{i}[v_{i+1}^{(j_{1})}, …, v_{i+1}^{(j_{s})}], 0 ≤ ℓ ≤ k and t^{(0)} ≢ 0 such that t(h(v_{i+1}^{(j_{1})}, …, v_{i+1}^{(j_{m})})) ≡ 0. Since we have proved that |t^{(0)}| ≻ (exp^{(i+1)} p_{26})^{−1} and by lemma 7 |t^{(ℓ)}| ≺ exp^{(i+1)} p_{26}, 0 ≤ ℓ ≤ k for a suitable p_{26}, we obtain that |h(v_{i+1}^{(j_{1})}, …, v_{i+1}^{(j_{m})})| ≻ (1/2)(exp^{(i+1)} p_{26})^{−2} and complete the proof of theorem 2 taking into account that any element of the field P_{i+1} can be represented as a quotient h^{(1)}(v_{i+1}^{(j_{1})}, …, v_{i+1}^{(j_{m})})/h^{(2)}(v_{i+1}^{(j_{1})}, …, v_{i+1}^{(j_{m})}) for some elements v_{i+1}^{(j_{1})}, …, v_{i+1}^{(j_{m})} ∈ P_{i+1} each satisfying an equation of the type (1) and polynomials h^{(1)}, h^{(2)} ∈ P_{i}[Z_{1}, …, Z_{m}].

6. Deviation theorems for elementary sigmoids.

By an elementary sigmoid with a depth d we mean a sigmoid like in the section 1 where at the computational step (2) the gate function is either u = exp or u = log, in the latter case we impose a requirement that (g_{1}/g_{2})(w_{i}^{(1)}, …, X) is positive everywhere. Then the function w_{i+1}^{(j)} satisfies an equation of the form (5) and therefore w_{i+1}^{(j)} ∈ P_{i+1}. A function computed by an elementary sigmoid is elementary (cf. [S]). A “standard” sigmoid ([MSS]) is a particular case of an elementary one. Theorem 2 implies the following.

Corollary 2. Let a function 0 ≢ f be computed by an elementary sigmoid with a depth d. Then for a certain polynomial p_{27} we have (exp^{(d)} p_{27})^{−1} ≺ |f| ≺ exp^{(d)} p_{27}.

The remarks similar to remarks 1, 2 and the remark about Blum-Shub-Smale model from the section 1 are true also for the elementary sigmoids.

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

REFERENCES

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

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

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

[Kh] Khovansky, A., Fewnomials, Transl. Math. Monogr., AMS, 88 (1991).

[S] Singer, M., Liouvillian solutions of nth order linear differential equations, Amer. J. Math, 103 (1981), pp. 661–682.