Meandering of trajectories of polynomial vector fields in the affine n-space

Publicacions Matem`atiques, Vol 41 (1997), 223–242. MEANDERING OF TRAJECTORIES OF POLYNOMIAL VECTOR FIELDS IN THE AFFINE n-SPACE D. Novikov and S. Yakovenko Abstract We give an explicit upper bound for the number of isolated intersections between an integral curve of a polynomial vector field in Rnand an affine hyperplane. The problem turns out to be closely related to finding an explicit upper bound for the length of ascending chains of polynomial ideals spanned by consecutive derivatives. This exposition constitutes an extended abstract of a forthcoming paper: only the basic steps are outlined here, with all technical details being either completely omitted or at best indicated. Contents 1. Geometry: Trajectories of polynomial vector fields and their meandering 224 1.1. Formulation of the main result 1.2. Remarks 1.3. Related problems 1.4. Ramifications 2. Analysis: Construction of a quasilinear equation 229 2.1. Linear nth order equation 2.2. The nonlinear multidimensional case: the construction 2.3. Integrality via universality 3. Algebra: Chains of ideals and chains of varieties 233 3.1. Basic definitions 3.2. Strict monotonicity and convexity 3.3. General finiteness result 3.4. Decreasing chains of algebraic varieties 3.5. Dimension-preserving iterations 3.6. Chains of ideals spanned by consecutive derivatives References 240 224 D. Novikov, S. Yakovenko 1. Geometry: Trajectories of polynomial vector fields and their meandering An algebraic curve defined by simple formulas in Rncannot be strongly meandering in the following sense: each (affine) hyperplane in Rneither entirely contains this curve, or intersects it by no more than a finite number of isolated points, and this number can be easily bounded in terms of the algebraic complexity of the curve (the degree of polynomial equations determining it). For example, if the curve is explicitly parameterized as t→ (x1(t),... ,x n(t)), where xj(t) are polynomials of degree ⩽din one variable, then the number of isolated intersections with a hyperplane is at most d. More generally, if a nonsingular curve is defined as a common zero locus for any finite number of polynomials in nvariables of degree ⩽d, then the number of isolated intersections cannot be greater than dn−1(a variation on the theme of B´ezout theorem). It would be natural to expect that an integral curve of a polynomial vector field of degree ⩽d, though almost never algebraic, would exhibit a similar property: the number of isolated intersections with any hyperplane can be explicitly majorized in terms depending only on the differential equations determining the curve. Note that if a solution would be explicitly known, then one might try to use a result from [15] claiming that the number of isolated intersections with any affine hyperplane is no greater than a weighted sum of integral Frenet curvatures. But even for the rare case of integrable equations the answer in terms of integral curvatures may well happen to be not uniformly bounded over all integral curves. Easy examples show that it is insufficient to know only the degree of the polynomials defining the vector field; the magnitude of the coefficients affects the possible number of intersections already in the linear case. The “size” of the curve also must be taken into account. Besides, there seems to be no more relevant parameters, and the question arises: is it possible to place an explicit upper bound on the number of intersections between an integral curve and a hyperplane, in terms of the dimension of the space, the degree of the vector field, the magnitude of its coefficients and the size of the curve? An affirmative answer to this question constitutes the main result of this paper. 1.1. Formulation of the main result. Consider a system of n polynomial nonautonomous ordinary differential equations ˙x=v(t, x) or, more explicitly, Meandering of polynomial vector fields 225 (1.1) ˙xi=vi(t, x1,... ,x n),v i∈R[t, x1,... ,x n],i=1,... ,n, t∈R,x=(x1,... ,x n)∈Rn,deg v:= max i=1,... ,n deg vi⩽d, with the polynomial right hand sides viof some known degree d. Recall that the height h(p) of a multivariate polynomial pis the maximal absolute value of its coefficients. We assume that the height of the right hand side of the system (1.1) is known and bounded by a certain constant r: (1.2) vi=vi(t, x)=j+|α|⩽dvijα tjxα,α=(α1,... ,α n)∈Zn +, h(v) = max ih(vi) = max imax j,α |vijα|⩽r. Let Γbe a solution to this system, a parameterized curve, whose geometric dimensions are also known: we assume that in the space-time the graph of Γis contained in the ball of some radius rcentered at the origin (the minimal such rwill be called the height of the curve and denoted by h(Γ) for aesthetical reasons), (1.3) Γ:I→Rn,It→ x(t)∈Rn, I⊆[−r,r],x(t):= max j=1,... ,n |xj(t)|⩽r∀t∈I. Our principal goal is to place an explicit upper bound on the number of isolated intersections between Γand an arbitrary affine hyperplane in Rn, knowing only the degree and the height of the determining equation (1.1) and the height of the trajectory Γ. Obviously, it would be sufficient to estimate in the above terms the number of isolated intersections with the hyperplane {x1=0}. Moreover, in order to reduce the number of initial data, we assume (and it turns out to be rather natural) that r=r. To abbreviate the formulations, we introduce the following notation. Definition 1. Let n, d be two natural numbers and r>0 a real number. The meandering index Ω(r, n, d) is the supremum of the possible number of isolated intersections with hyperplanes, taken over all polynomial equations of dimension n, degree dand height rand over all their integral curves of (the same) height r. One may show, using some general results on real analytic sets [3], that Ω(r, n, d) is always finite, but the methods used in [3] give absolutely no 226 D. Novikov, S. Yakovenko information on the nature of Ωas a function of its arguments. Our main result claims computability of Ωin a certain very strong sense and places an explicit upper bound on it. Definition 2. A primitive recursive function is a function from Zm + to Z+that can be obtained from the basic functions (identity and the constant 1) by a finite number of compositions (substitutions), juxtaposition (concatenation) and recursion in one variable. The latter rule allows to construct a function using the recursive construction f(1,ν)=g(ν),ν=(ν1,... ,ν a)∈Zm +, f(k+1,ν)=G(k,f(k,ν),ν),k=1,2,... , provided that the functions g(·) and G(·,·,·) are already constructed. Despite the seemingly all-embracing appearance of the class of primitive recursive functions, this class does not include all functions that are computable in the algorithmic sense of this word. As a counterexample, one could mention the Ackermann generalized exponential described in section 3.3. This function grows more rapidly than any primitive recursive function, and in a strange way appears in connection with the problem of bounding Ω, as explained in sections 3.3 and 3.4. Now the principal result of this paper can be formulated. Theorem 1 (main). Ω(r, n, d)⩽(2 + r)B(n,d), where Bis a finite number depending only on nand d. Moreover, B(n, d)as a function of two natural arguments is explicitly computable, admits a primitive recursive majorant and for large n, d grows not more rapidly than the tower of four exponents, exp[4]n+d)≡ exp exp exp exp(n+d). 1.2. Remarks. This formulation deserves, to our opinion, several comments. The finiteness of Ω(r, n, d) is, as already mentioned, a corollary to a very basic property of real analytic sets. The analytic section 2 provides information sufficient to conclude that for any particular choice of nand d, the meandering index Ω(r, n, d)as a function of rgrows at most polynomially. In other words, the value B(n, d) is proved to exist and be always finite. Meandering of polynomial vector fields 227 In the beginning of section 3 we explain why B(n, d) can be explicitly majorized using some finite deterministic algorithms, and therefore admits a recursive, but not (yet) necessarily primitive recursive majorant. The problem is in estimating the maximal length of certain ascending chains of polynomial ideals, the subject that received substantial attention since the paper by G. Hermann [8] and later works by A. Seidenberg [18], [19]. Five years ago one might hope that upgrading recursiveness to the primitive recursiveness is a matter of technical skill. However, the recent results by G. Moreno Soc´ıas [14] show that the best result one can get without additional information is the upper bound in the form of the Ackermann generalized exponential, see below in section 3.3. The growth of this function is faster than any closed expression (elementary function, e.g. the tower of one million exponents) or even any primitive recursive function. However, one can obtain much better estimate for the length, using the algebraic fact that the ideals in the chain are obtained by adding consecutive derivatives, resulting in a certain “convexity” of the “monotonous” chain of ideals. In section 3 we discuss without going into technical details, how this “convexity” makes ascending chains infinitely shorter, resulting in the tower of only three exponents. This implies that the bound for the original problem on the number of intersections can be achieved as the tower of 4 exponents. Concluding this informal discussion, we would like to stress that the function B(n, d) can be written in an explicit closed form. Moreover, the asymptotic upper bound given in Theorem 1 is certainly excessive (the price for its relatively compact form). Yet we were unable to reduce it to the tower of two exponents (see section 1.3 below), not saying about polynomial expressions. 1.3. Related problems. A local counterpart of the problem on counting isolated intersections is the problem on estimating the maximal multiplicity of contact, known as Risler problem [17]. An explicit answer in the Risler problem was relatively recently obtained first by A. Gabrielov, J.-M. Lion and R. Moussu for planar (n= 2) curves [4], and then by Gabrielov in [2] for the general case: the multiplicity of isolated contact between an integral curve of a polynomial system (1.1) and a hyperplane does not exceed (d+1) 2n, which makes a tower of two exponents. Note that the bound does not depend on the height(s). Another problem that leads to similar considerations, appears when one replaces the differential equation (1.1) by a polynomial discrete time dynamical system of the form 228 D. Novikov, S. Yakovenko Rnx(t)→ x(t+1)=P(t, x(t)) ∈Rn,t=0,1,2,... , where P:R×Rn→Rnis a polynomial map of some known degree d. For such systems the order of contact between an (infinite) orbit {x(0),x(1),x(2),...}and an algebraic hypersurface (say, a hyperplane X0⊆Rn), is the length of the initial segment of the sequence {x(t)} t=0 that belongs to X0, provided that the infinite orbit leaves X0at a certain moment (otherwise the “contact” between the orbit and the hypersurface is “nonisolated”). The problem that will be referred to as the discrete Risler problem, is to estimate the maximal possible order of an isolated contact, knowning only the dimension nand the degree d. Besides the natural analogy, the discrete Risler problem naturally appears when one tries to solve the (original) Risler problem by expanding solutions in Taylor series, at least in the linear case. On the other hand, the method of proving Theorem 1 is more easy to explain in slightly different settings provided by the analysis of the discrete Risler problem. 1.4. Ramifications. Besides the principal result of Theorem 1, we solve also the discrete Risler problem for sufficiently generic polynomial maps that are dimension-preserving in the sense described below in section 3.5. The solution of the discrete Risler problem, after additional considerations similar to that of section 2 and using some very recent results by M. Briskin and Y. Yomdin [1], [20], would allow to estimate the number of isolated intersections with hyperplanes for analytic curves, whose vector Taylor coefficients can be obtained by polynomial recurrent procedures (as in the case of solutions of linear polynomial systems of first order differential equations). We would also remark that being originally totally real, the question about the number of intersections makes sense also for holomorphic integral curves of polynomial differential equations. Our proof works without any change in the complex settings as well, and the final bound remains the same. The only difference is that the reference to Lemma 1 below should be replaced by that to its complex analog from [16]. Acknowledgements. This work would never be done without help and support of our friends and colleagues who patiently explained us some basics and fine points of commutative algebra. We are grateful to Alexander Braverman, Maria Gorelik, Vladimir Hinich, Anna Melnikov, Andr´e Reznikov, Victor Vinnikov, Amnon Yekutieli. Yosef Yomdin, Vladimir Golubyatnikov, Marie-Fran¸coise Coste-Roy and Andrei Gabri´elov were among the first who discussed this problem Meandering of polynomial vector fields 229 with us and by showing constant and strong interest provided us with additional stimuli. However, our special and cordial gratitude goes primarily to Joos Heintz: he introduced us into the beautiful realm of effective commutative algebra and taught us many fundamental results. In particular, he supplied us with the explicit estimate of the complexity of primary decomposition that we otherwise would be unable to produce. 2. Analysis: Construction of a quasilinear equation Let t→ (x1(t),... ,x n(t)) be the parametric representation of the curve, x0(t)≡1 and λ0,λ 1,... ,λ na tuple of real constants. To majorize the meandering, one has to estimate the number of isolated zeros of an arbitrary linear combination λ0(t)x0+λ1x1(t)+···+λnxn(t). Typically such linear families of functions appear as solutions to higher order linear differential equations (with variable coefficients). Thus we start with our principal example that will also serve as a principal tool in further investigations. 2.1. Linear nth order equation. Suppose that a real analytic function f:I→Ris known to satisfy on this interval some linear ordinary differential equation of order νwith real analytic coefficients, (2.1) y(ν)+aν−1(t)y(ν−1) +···+a1(t)y+a0(t)y=0, and the coefficients aj(t) extend analytically into some open neighborhood Uof the real interval IR⊆Cin the complex plane. Then the upper bound for the absolute value of the coefficients in Uis naturally referred to as the height of the equation (2.1). It turns out that any solution to an equation of bounded height may have only a bounded number of isolated zeros. The precise formulation follows. Lemma 1 (see [9, Theorem 1]).If |aj(t)|⩽rin UI, then any real solution of the equation (2.1) may have no more than γ·(ν+r)isolated zeros on I, where γ=γ(I,U)<+∞is an explicit “geometric” constant determined by the relative position of Iinside U. Note that one should not assume that the coefficients ajare polynomial or rational, though in many cases they turned to be: only their height r is essential. The asymptotic behavior of the geometric constant γ(I,U) is studied in [9, section 1.2]. The idea behind the proof of Lemma 1 is rather simple: the number of isolated zeros of an analytic function is related via the Jensen inequality 230 D. Novikov, S. Yakovenko to the growth of this function in the gap between Iand U. On the other hand, solutions of linear equations cannot grow too rapidly if the coefficients of the equations are explicitly bounded. 2.2. The nonlinear multidimensional case: the construction. The problem of estimating Ω(r, n, d) is equivalent to estimating the number of zeros of x1-coordinate along an arbitrary solution of the system (1.1). In this section we construct explicitly a linear equation of the form (2.1) satisfied by the function y(t)=x1(t). Let R=C[t, x]=C[t, x1,... ,x n] be the ring of polynomials in tand x; denote by D:R→Rthe derivation along the system (1.1): D= ∂t+n i=1 vi(t, x)∂i,∂i=∂/∂xi,i=1,... ,n. Consider the sequence of polynomials {pk}∞ k=0 ⊆Rdefined by the initial condition p0(x)=x1∈R and the recursive rule (2.2) p0=x1, pk=Dpk−1,k=1,2,3,... . The ring Ris Noetherian, therefore the ascending chain of ideals (2.3) (0) ⊆(p0)⊆(p0,p 1)⊆(p0,p 1,p 2)⊆··· ···⊆(p0,p 1,... ,p k)⊆(p0,p 1,...,p k,p k+1)⊆··· must stabilize at a certain moment !so that p∈(p0,... ,p −1) and hence (2.4) p=h−1p−1+···+h1p1+h0p0,h j∈R. Consider now any trajectory Γ:t→ x(t) of the nonlinear system (1.1). By construction, the polynomial pk=pk(t, x) restricted on this curve, is the kth derivative dk dtkx1(t), while the restriction of hkbecomes an analytic function that we denote by −aj(t). Altogether, the identity (2.4) would mean then that the function y(t)=x1(t) along Γsatisfies the linear equation (2.1) of order !. By Lemma 1, to estimate the number of zeros it would be sufficient to know the height of the coefficients on some complex neighborhood of the real segment Iand the order of the equation !. The problem on estimating !is a rather difficult problem that will be treated separately in section 3 and in particular in section 3.6. But even knowing !is in general not sufficient to estimate the heights of the polynomials hjin (2.4). Indeed, the identity (2.4) means a system of linear equations for the coefficients of the polynomials hj. This system Meandering of polynomial vector fields 231 is known to admit at least one solution, but nobody can guarantee that this system is sufficiently well-posed so that in an attempt to solve it one never divides by numbers too close to zero. One case when such guarantee can be given is when all polynomials pj are with integral coefficients. Then all nonzero denominators will be at least equal to 1 in the absolute value, and the division will be well-posed. These arguments are in more details exposed below. 2.3. Integrality via universality. The key idea behind the second step is to ensure that all polynomials pkhave integral coefficients. This would allow to find a representation (2.4) of some bounded height. The required integrality is achieved by adjoining formally all coefficients of the polynomials vjto the list of independent variables. More precisely, we consider the full collection of coefficients {vijα}of all polynomials vi(t, x) as described in (1.2) as new independent variables, and denote by Λ = {λ1,... ,λ n}={t, x1,... ,x n,... ,v ijα,...}, the combined list of all variables of length n=1+n+n·n+d n. Denote by R∗the extended polynomial ring, R∗=C[Λ] = C[t, xj,v ijα]. Then the derivation Dextends (by the same formula) to the derivation D∗:R∗→R∗and the sequence of polynomials arises as in (2.2). Actually, the polynomials will be the same, only their dependence on the coefficients of the vector field vwill now be explicit. In other words, we consider (1.1)-(1.2) as a vector field in the space with coordinates (t, xj,v ijα), on understanding that the remaining coordinates are governed by the trivial equations ˙ t=1,˙vijα =0 1⩽i⩽n, 0⩽j+|α|⩽d. Notice that with respect to the new set of independent variables: (1) the extended derivation D∗is integral, i.e. all right hand sides v∗ iof the corresponding system of equations are integral polynomials from the subring Z[Λ] = Z[t, xj,v ijα]⊂R∗(actually, the coefficients are only 0’s or 1’s), (2) the degrees of these polynomials do not exceed d+ 1 and their height is 1, (3) the polynomials pkare also integral, with their degrees growing linearly in kand heights roughly exponential in k. The chain (2.3) understood now as a chain of ideals in R∗, is determined by the numbers nand donly, therefore one has one and the same bound !=!(n, d) for the length of this chain, uniform over all problems of the given dimension and degree. This already implies the existential upper 238 D. Novikov, S. Yakovenko (3.4) X0⊃X1⊃···⊃Xkn−1    dim XkXk+1=n−1 ⊃Xkn−1+1 ⊃···⊃Xkn−2    dim XkXk+1=n−2 ⊃··· ···⊃Xks+1 ⊃···⊃Xks−1    dim XkXk+1=s ⊃···⊃Xk1+1 ⊃···⊃Xk0    dim XkXk+1=0 such that along sth segment the differences XkXk+1 are exactly sdimensional semialgebraic varieties. The length of each such segment does not exceed the number of sdimensional irreducible components in the starting set Xks+1 of this segment. This is almost obvious: the dimensions dim XkXk+1 must be nonincreasing, hence the chain can be partitioned into segments as required. Along each segment one has to monitor only s-dimensional irreducible components, and moreover, their number must strictly decrease on each step inside the segment. Indeed, inside the sth segment all components of dimension >smust be preserved, otherwise the difference will be more than s-dimensional. On the other hand, if all s-dimensional components are preserved on some step, this means that the difference XkXk+1 is at most (s−1)-dimensional, and one starts the next segment. It remains only to observe that the number of irreducible components can be estimated by the B´ezout theorem, and hence for the lengths ks−ks−1we have a recurrent inequality, (3.5) ks−1−ks⩽dksn−1=(dn−1)ks,s=n−1,... ,1,0,k n=0. As a result, we obtain a simple upper bound that is infinitely better than the Ackermann generalized exponential: the above inequality can be transformed into ks−1⩽(1 + dn−1)ks, which obviously gives a tower of nexponents after niterations. In terms of the discrete Risler problem this result looks as follows. Theorem 2. If P:Cn→Cnis a dimension-preserving polynomial map of degree ⩽dthen for any algebraic hypersurface X0of degree ⩽d and any point x∈X0the P-orbit {Pk(x)}∞ k=0 either leaves X0no later than on the Nth step, where N⩽AA···A    n−1 times ,A=1+dn−1, Meandering of polynomial vector fields 239 or remains on X0forever. In other words, the answer is given by the Ackermann function of rank 4, and this is related to the exponential growth of degrees of pk:if the degrees were growing linearly with k, then the result would be given by the Ackermann function of rank 3, or, more exactly, by a double exponential in nestimate, as in [2]. In this sense all towers of exponents of some universal height (2, 3 or 1000) all occupy an intermediate place between the Ackermann functions of ranks 3 and 4, “closer” to the former one. Thus the difference between the tower of height 4 that occurs in Theorem 1 and that of height 2 typical for the (continuous) Risler problem, is “negligeable”. 3.6. Chains of ideals spanned by consecutive derivatives. Now we briefly describe how the constructions of section 3.5 should be modified for working with chains of ideals. As before, the main tool is the irreducible decomposition of polynomial ideals [21]: any polynomial ideal I⊆Radmits an irredundant representation I=Q1∩···∩Qk, where Qj⊆Rare primary ideals with pairwise different associated prime ideals. Additional problems arising when replacing varieties by ideals, are of two kinds. First, the primary decomposition is in general non-unique, except for primary components of maximal dimension [21]. Second, one has to take multiplicities into account, since there may occur a strictly ascending chain of primary ideals with the same associated prime, and one has to look for a numeric indicator of its ascent. The problem with defining multiplicities is rather delicate: in particular, we tried to avoid defining and using the multiplicity for embedded primary components, i.e. those whose associated prime contains the associated prime(s) of some other primary components. This difficulty was circumvented by constructing an arbitrary (not canonically defined) primary decomposition and deleting out of it all primary components of larger dimensions. The following proposition is an algebraic analog of Lemma 5. Lemma 6. If Dis a derivation and {Ik}is a strictly ascending chain constructed as in (2.2), then this chain can be subdivided into ⩽nsegments of finite length, (3.6) I0⊂I1⊂···⊂Ikn−1    dim Ik:Ik+1=n−1 ⊂Ikn−1+1 ⊂···⊂Ikn−2    dim Ik:Ik+1=n−2 ⊂··· ···⊂Iks+1 ⊂···⊂Iks−1    dim Ik:Ik+1=s ⊂···⊂Ik1+1 ⊂···⊂Ik0    dim Ik:Ik+1=0 240 D. Novikov, S. Yakovenko such that along sth segment the colon ratios Ik:Ik+1 are exactly sdimensional. Consider any primary decomposition of Iks+1 and collect the terms in such a way that Iks+1 =Q s∩Q s, where Q sis the intersection of primary components of dimension >sand Q sis the intersection of primary components of dimensions ⩽s. Then s-dimensional components of Q s are well defined together with their multiplicities by the choice of Q s, and the length of the sth segment does not exceed the number of s-dimensional primary components of Q s, counted with their multiplicities. Note that the decomposition Iks+1 =Q s∩Q sis not uniquely defined, however, any such representation can be used to estimate the length of the sth segment. Moreover, one has no simple formulas as in B´ezout theorem, for the number of irreducible components. Therefore we had to use an algorithm for the effective primary decomposition of a polynomial ideal, and analyze its complexity. This subject, covered in a range of recent publications [5], [6], [10], [11], is still too technical to be included here. What we need from this highly developed theory is an explicit upper bound for the degrees of generators and the number of irreducible primary components of an ideal given by a system of generators of known degrees. After this the problem of majorizing multiplicities becomes relatively simple, and we can write a system of recurrent inequalities majorizing the length of segments in (3.6). References 1. M. Briskin and Y. Yomdin, Algebraic families of analytic functions I, Preprint, Weizmann Institute of Science (1995). 2. A. Gabrielov, Multiplicities of zeros of polynomials on trajectories of polynomial vector fields and bounds on degree of nonholonomy, Math. Res. Lett. 2(1996), 437–451. 3. A. Gabrielov, Projections of semianalytic sets, Funktsional. Anal. i Prilozhen. 2(4) (1968), 18–30 (Russian), English transl. in Functional Anal. Appl. 2(1968), 282–291. 4. A. Gabrielov, J.-M. Lion and R. Moussu, Ordre de contact de courbes int´egrales du plan, C.R. Acad. Sci. Paris S´er. I Math. 319(3) (1994), 219–221. 5. P. Gianni, B. Trager and G. Zacharias, Gr¨obner bases and primary decomposition of polynomial ideals. Computational aspects Meandering of polynomial vector fields 241 of commutative algebra, J. Symbolic Comput. 6(2-3) (1988), 149– 167. 6. M. Giusti,“Some effectivity problems in polynomial ideal theory,” EUROSAM 84 (Cambridge, 1984), Lecture Notes in Comput. Sci. 174, Springer, Berlin-New York, 1984, pp. 159–171. 7. J. Heintz, Definability and fast quantifier elimination in algebraically closed fields, Theoret. Comput. Sci. 24(3) (1983), 239–277. 8. G. Hermann, Die Frage der endlich vielen Schritte in der Theorie der Polynomialideale, Math. Ann. 95 (1926), 736–788. 9. Yu. Il’yashenko and S. Yakovenko, Counting real zeros of analytic functions satisfying linear ordinary differential equations, J. Differential Equations 126(1) (1996), 87–105. 10. T. Krick and A. Logar, An algorithm for the computation of the radical of an ideal in the ring of polynomials, in “Applied algebra, algebraic algorithms and error-correcting codes,” (New Orleans, LA, 1991), Lecture Notes in Comput. Sci. 539, Springer, Berlin, 1991, pp. 195–205. 11. D. Lazard, A note on upper bounds for ideal-theoretic problems, J. Symbolic Comput. 13(3) (1992), 231–233. 12. S. Lojasiewicz,“Introduction to Complex Analytic Geometry,” Birkh¨auser, Basel-Boston-Berlin, 1991. 13. E. W. Mayr and A. R. Meyer, The complexity of the word problems for commutative semigroups and polynomial ideals, Adv. Math. 46 (1982), 305–329. 14. G. Moreno Soc´ ıas, Length of polynomial ascending chains and primitive recursiveness, Math. Scand. 71(2) (1992), 181–205. Autour de la fonction de Hilbert-Samuel (escaliers d’id´eaux polynomiaux), Ph.D. Thesis, Centre de Math´ematiques de l’´ Ecole Polytechnique, 1991. 15. D. Novikov and S. Yakovenko, Integral Frenet curvatures and oscillation of spatial curves around affine subspaces of a Euclidean space, J. of Dynamical and Control Systems 2(2) (1996), 157–191. 16. D. Novikov and S. Yakovenko, A complex analog of Rolle theorem and polynomial envelopes of irreducible differential equations in the complex domain, J. London Math. Soc. (1996) (to appear). 17. J.-J. Risler, A bound for the degree of nonholonomy in the plane, Algorithmic complexity of algebraic and geometric models (Creteil, 1994), Theoret. Comput. Sci. 157(1) (1996), 129–136. 18. A. Seidenberg, Constructions in algebra, Trans. Amer. Math. Soc. 197 (1974), 273–313. 242 D. Novikov, S. Yakovenko 19. A. Seidenberg, Constructive proof of Hilbert’s theorem on ascending chains, Trans. Amer. Math. Soc. 174 (1972), 305–312; On the length of a Hilbert ascending chain, Proc. Amer. Math. Soc. 29 (1971), 443–450. 20. Y. Yomdin, Oscillation of analytic curves, Preprint, Weizmann Institute of Science (1995). 21. O. Zariski and P. Samuel,“Commutative Algebra,” vol. 1, Springer-Verlag, N. Y. et al., 1975, corrected reprinting of the 1958 edition.. Keywords. Oscillation, Ascending chains, Polynomial ideals, Zeros of analytic functions. 1991 Mathematics subject classifications: 14Q05, 30C15, 34C20, 13E05, 13P10. Department of Theoretical Mathematics The Weizmann Institute of Science Rehovot 76100 ISRAEL e-mail: [email protected]eizmann.ac.il e-mail: yako[email protected]eizmann.ac.il WWW Home Page: http://www.wisdom.weizmann.ac.il/˜yakov/index.html Rebut el 30 de Novembre de 1996