<\body> >>>>>>||<\expand|make-title> >> and Joris van der Hoeven\>>> |>>>||>|\>>>| de Mathématiques (bât. 425)>>|||||>|||||>|||>\ ||>||>|||>>>>>>> > > Zero equivalence is a major issue on the analysis side of symbolic computation. Standard mathematical notation provides a way of representing many transcendental functions. However, trivial cases apart, this notation gives rise to the following problems: Expressions may not be defined: consider , or -e*e)>. Expressions may be ambiguous: what values should we take for )> or |>>? Expressions may be redundant: x+cos x> and are different expressions > Often, one is interested in expressions which represent functions in a ring. In that case, the third problem reduces to deciding when a given expression represents the zero function. As to the first two problems, one has to decide where and how we want our functions to be defined. In this paper, we will mainly be concerned with expressions that represent multivariate power series. The expressions will then be formed from the constants and the indeterminates using the ring operations and power series solutions to first-order differential equations. The correctness and non-ambiguity of expressions may then be ensured by structural induction. This may involve zero-testing for the series represented by subexpressions. As a first step, one would like to be able to solve zero-equivalence for the elementary constants, that is to say the smallest field of constants closed under the application of the exponential, trigonometric and (for non-zero argument) logarithmic functions. Alas no such algorithm is known and it is clear that some formidable problems in transcendental number theory would need to be solved before one was found. In the face of this dilemma implementers have used heuristic methods generally involving floating-point computations. Theoreticians have often resorted to the use of an oracle; in other words they pre-supposed a solution to the problem for constants. They have then gone on to develop other algorithms, for example to decide zero equivalence of functions, on this basis. However for elementary constants one can do better than merely invoke an oracle. , algorithms for deciding the signs of elementary constants based on the Schanuel Conjecture have been given by Caviness and Prelle, and Richardson, . The conjecture has been shown to imply the decidability of the real exponential field, .|<\expand|quote> Let ,\,\> be complex numbers which are linearly independent over the rational numbers . Then the transcendence degree of (\,\,\,exp(\),\,exp(\)):<\ with|math font|Bbb*|Q>> is at least . > There are definite advantages in using a conjecture from number theory rather than heuristic methods, in that it is clear what is being assumed and any counter example found would be of considerable mathematical interest. However in a practical situation, a zero equivalence method for constants is generally needed very often, and here the algorithms based on the Schanuel Conjecture are really rather slow. Another limitation of the above approach is that it is very hard to see how to generalize the Schanuel Conjecture to cover constants given by Liouvillian or Pfaffian functions. For the substance of the conjecture is that the relations between exponentials and logarithms of numbers are just the ones we already know about, but it seems impossible to even formulate such a claim when integrals and solutions of differential equations are involved. <\expand|quote> In , the following witness conjecture was made. Let 3> and consider the set > of real exp-log expressions such that for each subexpression of the form or , we have \|\N> resp.> \\|\|\N>, where > denotes the value of as a real constant. Then there exists a of the form (n)=C*\ n> such that for any > of size (f)>, it suffices to evaluate > up to (\(f))> digits in order to determine whether it vanishes. Earlier versions and variants of witness conjectures appeared in . Also, Dan Richardson has accumulated numerical evidence and worked out some number-theoretic consequences. It should be noticed that these conjectures are independent of the Schanuel conjecture. Indeed, there might exist non zero elementary constants, which yet evaluate to extremely small numbers. On the other hand, there might exist counterexamples to the Schanuel conjecture which can be ``detected'' to be zero by evaluating a reasonable number of digits. The interest of witness conjectures is that they potentially provide us with fast zero tests, if they can be proved to to hold for reasonably small witness functions >. Although zero-test algorithms for constants are extremely hard to design, more progress has been made on zero-tests for functions , , . Unfortunately, no reasonable complexity bounds (i.e. less that the Ackermann function) for these algorithms were known up till now. In this paper, we both generalize the algorithm from to the multivariate setting and provide complexity bounds. Now it is interesting to study the significance of such bounds for the exp-log constant conjecture. Indeed, since number theoretical questions about transcendence or Diophantine approximation are usually very hard, a first step usually consists of formulating analogue questions in the setting of function fields. A deep and well-known theorem of Ax states that the power series part of Schanuel's conjecture does hold. The exp-log conjecture also admits a natural power series analogue. Given a field >, consider the set > of multivariate power series expressions constructed from > and ,\,z> using ,,>> and left composition of infinitesimal series by , and . Now let > be such an expression of size (f)> and let (f)\[[z,\,z]]> be the power series represented by . Then we expect that there exists a constant >, such that (f)=0> if and only if the coefficient of >*\*z>> in (f)> vanishes for all ,\,\\{0,\,C*\(f)}>. As a side effect of our complexity bounds, we will be able to prove a weaker result: with the above notation, there exists a constant , such that (f)> vanishes if and only if the coefficient of \ >*\*z>> in (f)> vanishes for all ,\,\\{0,\,k(f)>>}>. Just as the Ax theorem gives theoretical evidence that for the numerical Schanuel conjecture, our result thereby gives evidence that the numerical witness conjecture might be true. In section , we describe our setup of for doing computations on power series. Such computations may either be effective zero-tests or the extraction of coefficients. We will next consider the extension of effective local domains by solutions to first order partial differential equations. In section , we will show that such extensions are again effective local domains. In section 3, we recall the Bareiss method for Gaussian elimination of matrices with coefficients in an integral domain. This method has the advantage of limiting the expression swell. More precisely, we give bounds in terms of on integral domains. In the sequel, the Bareiss method is applied to the efficient g.c.d.> computation of several polynomials. This is an essential improvement with respect to , which allows us to obtain ``reasonable'' complexity bounds for our zero test. In section 4, we prove four key lemmas which ensure the correctness of our zero test. We also corrected a small mistake in the original correctness proof in . In section we present the actual algorithm and complexity bounds. In the case of power series over the real numbers, it is possible to obtain better theoretical bounds using techniques from . Nevertheless, we think that the results of this paper are interesting from several point of views: <\itemize> The framework is more general, because we show how to obtain complexity bounds in a relative way for extensions of effective local domains. We presented an improved version of an actual zero-test algorithm, which might have a better average complexity than Khovanskii's complexity bounds, although we have not yet proved a better bound for the worst case. Our methods are likely to generalize to higher order differential equations, by adapting the algorithm from . We plan to improve our complexity bounds in a forthcoming paper, with the hope of obtaining bounds closer to those in . Let > be an effective field of constants, which means that all field operations can be performed algorithmically and that we have an effective zero test. The ring [[z,\,z]]> is a differential ring for the partial differentiations ,\,\> w.r.t. ,\,z> on [[z,\,z]]>. We will frequently consider multivariate power series in [[z,\,z]]> as recursive power series in [[z]]\[[z]\ ]>. For this reason, it is convenient to introduce the partial evaluation mappings :[[z,\,z]]>|>|[[z,\,z]];>>|,\,z<\ rsub|j>)>|>|,\,z,0,\,0)>>>>> for all i\j\k>. We re-obtain the total evaluation mappings =\> as special cases. Notice that \(f)=\(\ f),> for every [[z,\,z]]\ > and i\j\k>. > of [[z,\,z]]> is called an , if we have algorithms for ,\,\,\,\> and an algorithm to test whether (f)=0> for each i\k> and >.> \[[z,\,z]]>, we observe that ()\[[z,\,z]]> may be considered as an effective power series domain for each i\k>. Indeed, this follows from the fact that > commutes with ,\,\,\,\,\,\>.> Let > be an effective power series domain and let be a power series in [[z,\,z]]>, which satisfies partial differential equations f=(f)|B(f)>>>|\ >>| f=(f)|B(f)>>>>>>> where ,B\[F]> are such that (B(f))\0> for each . Then the ring =f,(f)>,\,(f)>> is a differential subring of [[z,\\ ,z]]>, which is called a of >. The main aim of this paper is to show that > is also an effective power series domain and to give complexity bounds for the corresponding algorithms. >> Elements in [f]> are naturally represented by polynomials [F]> in a formal variable , via the unique >-algebra morphism :[F]\[f]> with (F)=f>. This mapping > naturally extends to a mapping :|\>\>, where |\>=F,(F)>,\,(F)>\(F)\ > The structure of > may be transported to |\>> in a natural way. The partial differentiations ,\,\<\ rsub|k>> on > extend uniquely to |\>> by setting F=A(F)/B(F)> for each (so that \\=\\\>). Each partial evaluation mapping :\> induces a natural evaluation mapping \ \\> on |\>>, which we will also denote by >. Since > is an effective local domain, the operations ,,>,\,\,\,\> can clearly be performed algorithmically on >. Our main problem will therefore be to design a zero-test for >, which amounts to deciding whether (P/Q)=0> for a given rational function >>. Actually, it is more convenient to work with polynomials in [F]> instead of rational functions in |\>>. Our main problem will then be to decide whether (P)=0> for [F]>, since a rational function |\>> represents zero if and only if does. Unfortunately, the ring [F]> is not necessarily stable under the derivations ,\,\>. For this reason, we introduce the derivations =B(F)*\,> which do map [F]> into itself. In order to determine whether (P)=0> for polynomials [F]>, we will consider the roots of such polynomials in the algebraic closure > of >. Now it is classical that the algebraic closure of the ring of univariate power series over a field is the field \z\> of Puiseux series over the algebraic closure > of . Interpreting multivariate power series in [[z,\,z]]> as recursive power series in [[z]]\[[z]\ ]>, we may thus view elements in > as recursive Puiseux series in \z\ \\\z\>. We define the anti-lexicographical ordering > on > by >\>>|>|=\\\\\=\)\>>|||\ \\\\=\\\\\=\)\>>|||>>|||\<\ less\>\),>>>>> for >=(\,\,\),>=(\,\,\)\>. Consider a Puiseux series \\z\\\z\>. We will write =>\>*z>> for the power series expansion of > w.r.t. >. Each coefficient may recursively be expanded in a similar way w.r.t. ,\,z>. Alternatively, we may expand > at once w.r.t. all variables using the anti-lexicographical ordering: =>>\>>*z>>,> where >>=z>*\*z>>. If 0>, then the minimal > with >>\0> is called the valuation of > and we denote it by (\)>. If (\)\>, then may we define (\)> to be the coefficient of *\*z> in >, for each {0,\,k}>. As usual, we denote (\)=\(\)>. If [F]> is a non zero polynomial, then we define the valuation (P)> of to be the minimum of the valuations of its non zero coefficients. If has degree , then we also define >>(\)=P>>*\+\+P>>\[\],> for each >\>. It should be noticed that the recursive extraction of coefficients can be done effectively in an effective power series domain >, because ,\,\>=!*\*\!>*\(\>*\*\> \)> for all \> and ,\,\\>. More generally, if |\>>, then we may formally represent the coefficient ,\,\>> of =\(P)> by polynomials in (|\>)>. Such representations are best derived through relaxed evaluation of formal power series , by using the partial differential equations satisfied by . > computations> Let > be an effective integral domain. In what follows, we will describe algorithms to triangulate matrices with entries in > and compute g.c.d.s of polynomials with coefficients in >. In order to state complexity bounds, it is convenient to measure the ``sizes'' of constants in > in terms of a , which is a function :\> with the following properties: <\description> (\+\)\m\ ax{\(\),\(\)}>. (\*\)\\\ (\)+\(\)>. If > is actually a differential ring with derivations ,\,\>, then we also assume the existence of a constant >\> with (\ \)\\(\)+K>>.> =[z,\,z]>, then we may take (P)> to be the maximum of the degrees of in ,\,z> and >=0>.> <\example> Assume that > and > are as in section and assume that we have a pseudo-norm > on >. Then we define a pseudo-norm on |\>> by (P)=max deg P,deg(F)> P,\,deg(F)> P,max>P>\(P>).> This pseudo-norm induces a pseudo-norm on > by (\)=min\(P)P\<\ wide||\>,\=\(P).> Notice that we may take >=K|\>>=ma\ x K>,2,max {\(A),\,\(A)}+max \ B|\ F>>,\,\ B|\ F>>.> Let > still be an effective integral domain with a pseudo-norm > and quotient field >. Consider an n> matrix with entries in > (i.e.> a matrix with rows and columns). For all indices i\\\i\m> and j\\\j\n>, we will also write ,\,i],[j<\ rsub|1>,\,j]>> for the l> minor of when we only keep the rows ,\,i> and columns ,\,j>. It is classical that we may upper triangulate using Gaussian elimination. This leads to a formula where is a matrix with determinant one and an upper triangular matrix. Unfortunately, this process usually leads to a fast coefficient growth for the numerators of the entries of the successive matrices. In order to remove this drawback, we will rather do all computations over > instead of >. This approach is due to . So let us now be given an n> matrix with entries in >. For simplicity, we will first assume that the usual triangulation of as a matrix with entries in > does not involve row permutations. This usual triangulation of gives rise to a sequence of identities >=>*M,> with {0,\,m}>, where >> is the matrix obtained from >> after steps. More precisely, >> is obtained from >> by leaving the first rows invariant and by adding multiples of the -th row to the others (in particular, the >> will be lower triangular throughout the process). If there exists a with >)\0>, then let > be the minimal such , so that >)=0> for all k> and p>. Each >> may be rewritten as a product >=D*T,> of an invertible diagonal matrix > and another matrix > with entries in >. Our aim is to show that we may choose the > and > of small pseudo-norms. In fact, we claim that we may take =Diag (1,\,\,\,\,\,\,\)> for each , where =(T\ )>>. In order to see this, let 1>, k-1> and p>. Then we first observe that >),k-1,i],[p,\,p,j]>=>,k-1,i]\ ,[1,\,k-1,i]>*M,k-1,i],[p,\,p,j]>.> Since >,k-1,i],[1,\,k-1,i]>> is a lower triangular matrix with ones on its diagonal, we obtain >),k-1,i],[\ p,\,p,j]>=det M,k-1,i],[p,\,p,j]>> Since >),k-1,i],[\ p,\,p,j]>> is upper triangular, we also have >),k-1,i],[\ p,\,p,j]>=(>)>*\*(>)>*(>).> By our choice of >, we finally have >)>*\*(<\ wide|T|\>)>*(>)=)>*\*(T)>*(T)|1*\*\*\\ >=(T).> Putting this together, we see that each coefficient of > (whence in particular >) may be written as the determinant of a minor of : (T)=det M,k-1,i],[p,\,p,j]>.> Hence, we have not only shown that the > and > have coefficients in >, but even that they may be written explicitly as determinants of minors of . This result remains so (up to a factor 1>) if row permutations were needed in the triangulation process, since we may always permute the rows of , so that no further row permutations are necessary during the triangulations. This proves the following theorem: <\theorem> There exists an algorithm, which takes an n> matrix with entries in > on input, and which computes an invertible m> diagonal matrix and an n> upper triangular matrix with entries in >, such that there exists a matrix >> with entries in >, of determinant one, and so that *T=>*M>. Moreover, (D)\min(m,n)*\(M)> and (T)\min(m,n)*\(M)>. Here (M)=max \(M)>. The actual computation of involves elementary operations. If we do have an algorithm for exact division in , then this is also the time complexity of the algorithm in terms of operations in >. Otherwise, it may be necessary to compute the entries of the intermediate matrices > by formula (), which yields an overall complexity of )>. Let > still be an effective integral domain with a pseudo-norm > and quotient field >. Consider a finite number ,\,P> of polynomials in [F]>. In this section, we address the question of computing a g.c.d.> [F]> of ,\,P> and a corresponding Bezout relation. Since we are only computing over an integral domain, we call g.c.d., if is a scalar multiple of g.c.d.> of ,\,P>, when considered as polynomials over the quotient field >. Accordingly, a Bezout relation for ,\,P> has the form Q*P+\+Q*P=c\ *G,> where ,\,Q\[F]> and >>. From the computational point of view, we are interested in minimizing the pseudo-norms of ,\,Q,c> and . As to the degrees, such ``small Bezout relations'' always exist: ,\,P\[F]> be more than one non-zero polynomial. Then there exists a Bezout relation )>, such that *P}\max {deg P+deg P\|i\j}>.> <\proof> Assume the contrary and choose a Bezout relation () of minimal degree {deg Q*P}> and such that the number of indices \\\i> with >*P>=d> is minimal. Since deg G>, we must have 1>, and modulo a permutation of indices, we may assume that =k> for each . Let > be the leading coefficient of > and > the leading coefficient of >. Then for =d-deg P-deg P\0>, we have *Q-\*x>*P)*P+(\*Q+\*x>*P)*P<\ rsub|2>+\*Q*P+\+\*Q*P=\\ *c*G,> is again a Bezout relation, which contradicts our minimality hypothesis. Let +deg P\|i\j}>. In order to actually find a Bezout relation of degree d>, we now consider the matrix with -\-deg P> rows and columns, which is the vertical superposition of all matrices of the form >>|>|>|||\ |>||>>|>|>|||>|||||<\ cell|>||>|||>||>||>||||||<\ cell|>|>||||>>|>|>|>|||||>>|>|>>>>>,> where =deg P>. Now triangulate as in the section above D*T=>*M> and let be the number of non-zero rows in . The -th row of corresponds to a polynomial linear combination of ,\,P> of minimal degree. In other words, it contains the coefficients of a g.c.d.> of ,\,P>. Moreover, we may obtain a Bezout relation when considering the matrix with an m> identity matrix glued at its right hand side. When triangulating this matrix, we obtain a relation of the form *T\|T=>*M\|Id=(<\ wide|U|\>*M\|>\ ),> such that the additional part > of the triangulated matrix gives us the transformation matrix >> in () up to the diagonal matrix : =D*>.> The finite sum which leads to the -th row in the product *M> now yields the desired Bezout relation. Notice that in this Bezout relation. From the complexity point of view, we also notice that at most rows in may actually have contributed to the first d> rows of . When replacing with its restriction to these rows, the above triangulations will therefore yield the same g.c.d.> and the same Bezout relation. We have proved <\theorem> Let ,\,P\[F]> be more than one non-zero polynomials. Then there exists an algorithm to compute a g.c.d.> of ,\,P> as well as a Bezout relation )> with , such that (G),\(Q),\,\(Q)}\2*(max {\(P),\,\(P)})\ .> Let > be an effective integral domain and let [F]> be polynomials over > with V\deg U>. If > were actually an effective field, then we might have used the Euclidean division algorithm to obtain the unique expression for of the form with [F]> and deg V>. However, this algorithm involves divisions and can no longer be used if > is an integral domain. Nevertheless, pseudo-division may always be used to obtain the unique expression for of the form *U=Q*V+R,> where > is the or of and [F]> are such that R\deg V>. We also call the and the of the division of by . <\algorithm|pdiv> \; [F]> with deg V>. the pseudo-quotient resp. pseudo-remainder of the division of by . <\body> Set 0> and U> For deg R,\,deg V> do <\indent> I*Q+R*Fi-deg V>> I*R-R*Fi-deg V>*V> Return In particular, we may use pseudo-division to make a polynomial square-free. Namely, we take the square-free part of to be >(P)=>(P,>(P,P))>. The following complexity bound follows from theorem : Let >>(P)> of as above. Then (S)\2*\(P)>.> We recall that derivations on integral domains extend uniquely to their algebraic closures. <\lemma> Let [F]> be a square-free polynomial and (P,d P,\,d P).> Consider the factorization )*\*(F-h),> with ,\,h\>. Then each of the > satisfies the partial differential equations )>. <\proof> Consider one of the factors > of and write )*Q.> For each {1,\,k}>, we have P=(A(F)-B(F)*\ h)*Q+(F-h)*d Q> Since > both divides *P> and )*d Q>, it also divides (F)-B(F)*\ h)*Q>. Now is square-free, so that > does not divide . Therefore > divides (F)-B(F)*\ h>. Consequently, (h)-B(h)*\\ h=0> for each , i.e. > satisfies (). Let \\z\\\z\> be a Puiseux series with (\)\>. Assume that > satisfies the same equations )> as and the same initial condition (\)=\(f)>. Then =f>.> <\proof> Let us prove by induction over that (\)=\\ (f)> for all {0,\,k}>. We have (\)=\\ (f)> by assumption. Assume therefore that 0> and (\)=\(f)>. Then =\(\)\ > is a Puiseux series in \z\\\z\> of the form \=\(f)+\0>\>*z>.> Since > and > commute, > satisfies the partial differential equation \ \=(A)(\)|\(B)(\)>.> In particular, extraction of the coefficient in -1>> yields \*\>=(A)(\)|\(B)(\)>-1>> for every \0>. Now (B)(\))=\<\ varepsilon\>(B)(\)=\(B(f))\0,> since (\(B(f\ )))=\(B(f))\0>. Consequently, we may see () as a recurrence relation which uniquely determines >> as a function of other >> with \\>. Hence =\(f)> is the unique solution to () of the form (). The lemma now follows by induction. <\lemma> Let be a polynomial in [F]>. Given \> with P(P)>(\)=0,> there exists a root \\<\ llangle\>z\\\z\> of with (\)\> and (\)=\>. <\proof> Intuitively speaking, this lemma follows from the Newton polygon method: the existence of a solution \0> to () implies that the Newton polygon associated to the equation )=0> admits a horizontal slope and that > is a solution to the associated Newton polynomial. Therefore, > is the first term of a solution to )=0>, the full solution being obtained using the Newton polygon method. If =0>, then the Newton polygon admits a ``strictly positive slope'' and a similar argument applies. More precisely, we may apply the results from chapter 3 in . We first notice that \z\\\z\=[>z>;\;z>]>> is a field of grid-based power series. Now setting =\+\>, the Newton degree of P>(\)=P(\+\)=0\ ((\)\)> is strictly positive. Indeed, this is clear if =0>, and this follows from lemma 3.2 in if \0>. Now our lemma follows from the fact that the algorithm returns solutions to (). <\lemma> With the notation from lemma , we have (P)=0\G(G)> (\(f))=0.> (G)> (\(f))=0>. Lemma implies that admits a root \\z\\\z\> with (\)\> and (\)=\\ (f)>. This root > satisfies the equations (), by lemma . Hence =f>, by lemma . We conclude that and (P)=P(f)=0>.> The lemmas from the previous section yield the following zero-test algorithm: <\algorithm|zero_test> \; [F]>. result of the test (P)=0>. <\body> then return .> computations]> <\indent> Replace (P)>. Let (P,d P,\,d P)>. ]> <\indent> Denote *Fq>+\+\ G>. For ,1> do <\indent> Expand ,\,\>,\,G,\,\>> in a relaxed way w.r.t. >. Stop at the least >, such that there exists a with ,\,\>\0>. >> (\(f))=0>.> In order to derive complexity bounds, we will to assume that we have a pseudo-norm > on > and that there exists a function >:\>, such that for each \\\{0}>, we have (\)\|\\\ >(\(\))>. Here we understand that ,\,\)\|=max {\,\,\},> for each >\>. It is also reasonable to also assume that >> is increasing and that it grows sufficiently fast such that >(c)\c>, >(c+d)\\>(c)+\>(d)> and >\ (c*d)\\>(c)*\>(d)> for all >>. Notice that we may take >(c)=1> for all > when =>. <\theorem> Let >+max {\(B),\,\(B)},max {\(A),\,\(A)},1}.> Then for any \\\{0}>, we have (\)\|\\>((2*k*C*\(\))).> <\proof> Assume first that \\\{0}> can be represented by a square-free polynomial [F]>. Then does not change in step 2 of and for {1,\,k}>, we have (d P)\\(P)+C,> Then theorem yields (G)\2*(\(P)+C).> Since (G)\|\\>(\(G))> for each non-zero coefficient > of , it follows that >\|\\\ >(2*(\(P)+C))> in step 3 of . Since we assumed \0>, we must have >>(\(f))\0> in the last step of . Considering the Taylor series expansion ||(f))+G(\(f))*\+>*G(\(f))*\\ +\>>|||>>(\(f))*z>*\*z>+o(z>*\*z>)>>>>> in the infinitesimal power series =f-\(f)>, we observe that (\(G))=>>. By theorem , also satisfies a Bezout relation of the form *d P+\+Q*d P,> Now (\(d P))\|=\|(\(B)*\ \(P))\|=\|(\ \(P))\|\\|(\(P))\|-1> for all (recall that (B)\0)>, so that (\(S*P+Q*\ d P+\+Q*d P))\|\\|(\(P))\|-1.> We conclude that (\(P))\|\\>(2*(\(P)+C)+1).> This gives a bound for (\)> in the case when is square-free. Let us now turn to the more general situation in which > is represented by a polynomial [F]> which is no longer square-free. Setting >\(P,(P,\ P/\ F))>, the above discussion yields the bound (\(P\ >))\|\\>(2*(2*\(P)+C)\ +1),> since (P>)\2*\(P)> by proposition . Now divides >> when we understand these polynomials to have coefficients in the quotient field of >. If is the leading coefficient of , we thus have >*P>> in [F]>, as is seen by pseudo-dividing >> by . It follows that (\(P))\|>|>|(P)*\|(\(P>))\|+\(P)*\\ |(c)\|>>||>|<\ cell|\(P)*\>(2*(2*\(P)+C)+1\ )+\(P)*\>(\(P))>>||>|>(2*\(P)*(2*\(P)+C+1)),>>>>> since (c)\|\\>(\(P))>. Let us finally consider the case when > is represented by a general element |\\ >>. Then we may rewrite as a fraction /\> with \[F]> and =B(P)>*\*B(P)>>, and we have (\)\\(P)+k*\(P)*max {\(B),\,\(B)}\k*C*\(P).\ > Since (\(\))=>, we thus get (\(P))\|>|>|>(2*\(\)*(2*\(\)+C+1))>>||>|>(2*k**C*\(P)*\ (2*(k*C*\(P))+C+1))>>||>|>(32*(k*C*\(P)),>>>>> since (P)=0> or 2*(k*C*\(P))>. As a consequence of the above bound for the valuations of non-zero series \>, we have a straightforward zero-test algorithm for series \> which consists of testing whether all coefficients of > up to the bound vanish using relaxed evaluation . This algorithm satisfies the following complexity bound: >>. With the notation from theorem , we may test whether represents zero in time >((2*k*C*\(\))\ )*log \>((2*k*C*\(\)))*k)>.> is very pessimistic, since it reflects the theoretical worst case bounds for the valuations. In practice, we recommend using , which we expect to be much faster in average.> Consider a tower of regular D-algebraic ring extensions \\\\ \> starting with =[z,\,z]>\ . We have natural representations :|\>=|\>F,(F)>,\,>(F)>\> for all {1,\,k}>. The repeated application of theorem yields , such that for all |\>>, we have either (P)=0> or (\(P))\|\K**\(P)>>.> , we have a polynomial time algorithm zero-test in >. Theoretically speaking, we already knew this, because \|\>/I> for a certain ideal of |\>>. Hence, it would suffice to reduce a polynomial in |\\ >> with respect to a Groebner basis for in order to know whether it represents zero. Unfortunately, we do not know of any algorithm to compute such a Groebner basis for . Nevertheless, even without such a Groebner basis the above corollary tells us that we still have a polynomial time zero-test.> Let us now return to exp-log series in the ring > considered in the introduction. \ Repeated application of theorem yields >, which can be represented by an expression of size >. Then either or (f)\|\(4*k*\)>>.>> <\proof> Let >> be an expression which represents and let >,\,>>> be its subexpressions listed in the order of a postfix traversal. We construct a tower \\\> with representations |\>\\\|\>>, such that >\>> for all and \\\p>=h>. We construct the tower by induction over . For we have nothing to show, so suppose 0> and that we have performed the construction up to stage . If >\> or >\{z,\,z}>, then we clearly have >\\ |\>=[z,\,z]>. If >=\ >>+>>>, >=>>->>>, >=>>->>> or >=>>*>>> with \>\i>, then >\|\>>>. Assume finally that >=\\>> with i>, where \{1/(1+z),exp z,log (1+z)}>. Then we take |\>>=|\>>[>]> if =exp z> or |\>>=|\>>[>,1/(1+>)]> otherwise, and one the relations f>|| f)*f;>>| f>|| f)*f;>>| f>|| f|1+f>>>>>> holds for all \{\,\,\}>. Notice that the pseudo-norm of >> is bounded by (whence by >) for all . Consequently, the from theorem is bounded by > at each stage. By induction over , it therefore follows that >(s)\(4*k*\\ )-1|8>>*s>> for all 1>. If 0>, we conclude that (f)\|\\>>(\)\(4*k*\)>>=k>>>. <\bibliography|bib|alpha|zerotest.bib> J. Ax. On Schanuel's conjecture. , 93:252--268, 1971. E.H. Bareiss. Sylvester's identity and multistep integer-preserving Gaussian elimination. , 22:565--578, 1968. B.F. Caviness and M.J. Prelle. A note on algebraic independence of logarithmic and exponential constants. , 12/2:18--20, 1978. A. G. Khovanskii. . American Mathematical Society, Providence, RI, 1991. S. Lang. Transcendental numbers and diophantine approximation. , 77/5:635--677, 1971. A.J. Macintyre and A.J. Wilkie. On the decidability of the real exponential field. In P.G. Odifreddi, editor, , CLSI. 1995. Ariane Péladan-Germa. Testing identities of series defined by algebraic partial differential equations. In Gérard Cohen, Marc Giusti, and Teo Mora, editors, , pages 393--407. Springer-Verlag, 1995. Proceedings of the 11th International Symposium, AAECC-11, Paris, France, July 1995. D. Richardson. How to recognise zero. , 24(6):627--646, 1994. D. Richardson. The uniformity conjecture. In , volume 2064, pages 253--272. Springer Verlag, 2001. J.R. Shackell. A differential-equations approach to functional equivalence. In G. Gonnet, editor, , pages 7--10, Portland, Oregon, 1989. A.C.M. Press. J.R. Shackell. Zero-equivalence in function fields defined by algebraic differential equations. , 336/1:151--172, 1993. J. van der Hoeven. . PhD thesis, École Polytechnique, Laboratoire d'Informatique, École Polytechnique, Paris, France, 1997. J. van der Hoeven. Relax, but don't be too lazy. Technical Report 78, Prépublications d'Orsay, 1999. Submitted to JSC. J. van der Hoeven. Fast evaluation of holonomic functions near and in singularities. , 31:717--743, 2001. J. van der Hoeven. Zero-testing, witness conjectures and differential diophantine approximation. Technical Report 2001-62, Prépublications d'Orsay, 2001. <\initial> <\collection> <\references> <\collection> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > <\auxiliary> <\collection> <\associate|bib> Lang71 C/P Richardson94a MW95 vdH:witness vdHoeven97 vdH:singhol Rich01 vdH:witness Sh3 Sh4 Peladan95 Sh3 Ax71 Sh3 Sh3 Khov91 Sh4 Khov91 VdH:relax Bar68 vdHoeven97 vdHoeven97 VdH:relax VdH:relax <\associate|toc> |1Introduction><\ value|toc-dots> 1.1Zero-tests for constants 1.2Zero-tests for functions 1.3Overview |2The main setup> 2.1Effective local domains 2.2Computations in ||S>> 2.3Extraction of coefficients |3The Bareiss method and g.c.d.> computations> 3.1Pseudo-norms 3.2The Bareiss method 3.3Computing greatest common divisors of several polynomials 3.4Making polynomials square-free using pseudo-division |4Four key lemmas> |5The algorithm> 5.1Statement of the algorithm 5.2Complexity bounds 5.3Consequences of the complexity bounds |Bibliography>