> <\body> <\expand|make-title> <\address> de Mathématiques ( 425) Université Paris-Sud 91405 Orsay Cedex France Email:

> <\abstract> In this paper, we present a new zero-test for expressions which are constructed from formal power solutions to algebraic differential equations using the ring operations and differentiation. We also provide a survey of all existing methods that we know of and a detailed comparison of these methods with our approach. >>\ >> Zero-testing is an important 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: <\itemize> 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, but they represent the same function. 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 be concerned with expressions that represent formal power series (in fact, this approach covers most elementary calculus on special functions, using analytic continuation if necessary). The expressions will then be formed from the constants and the indeterminates using the ring operations and power series solutions to algebraic differential equations. The correctness and non-ambiguity of expressions may be ensured by structural induction. This may involve zero-testing for the series represented by subexpressions. Several classical approaches for zero-testing exist and we provide a quick survey of them in section . Our new zero-test, which is described in section , is based on a similar approach as . We believe the algorithm to be interesting for five main reasons: <\itemize> We treat differential equations of arbitrary order. Our method accommodates divergent power series solutions. It reformulates previous work from in the more standard setting of differential algebra. We believe it to be more efficient. With some more work, it might be possible to give complexity bounds for the algorithm (or a modified version of it) along the same lines as . Such bounds are also interesting in relation to ``witness conjectures'' . On the longer run, the algorithm might generalize to the multivariate setting of partial differential equations with initial conditions on a subspace of dimension 0>. Throughout the paper, we will assume that the reader is familiar with differential algebra and the notations used in this field; see section and for a nice introduction. The proof of our algorithm also uses a result from the preprint , which is too complicated to be presented here, although we do provide a sketch of the proof in section . We plan to provide some examples and more explanations in a forthcoming journal paper. We are also writing a lecture note about the subject of section 4. No implementations are available yet. A is a power series which satisfies a non-trivial algebraic differential equation . Consider a power series expression constructed from and the constants in some field > like >, using > and left composition of infinitesimal power series by differentially algebraic power series ,\,\>. Then it is a classical problem to test whether such an expression represents zero. There are many approaches for this problem. If the differentially algebraic power series are particularly simple, then it is sometimes possible to characterize all possible relations between the power series under consideration. This is clearly the case if we restrict the differentially algebraic power series to be algebraic. A more interesting example is obtained when we also allow left composition with and z>. In this case, the Ax theorem and the Risch structure theorem may be used to design a fast zero-test. The structural approach may yield very efficient algorithms when it works. However, it requires the characterization of all possible relations in a given context, where we merely asked for a test whether a particular one holds. Consequently, the approach usually only applies in very specific situations. An obvious way to test whether an expression represents the zero power series is to obtain a bound for its valuation in terms of its size if the expression does represent zero. Khovanskii has given reasonably good uniform bounds (of the form >)>, where denotes the input size) for the number of zeros for systems of real Pfaffian functions . These bounds may be adapted to the power series context. This approach is interesting because it only requires fast power series expansions for implementing a zero-test. However, such a zero-test might be slow for expressions which can be quickly rewritten to zero (like , where is a complicated expression). Also, if we want the approach to be efficient, good bounds (such as the ones predicted by witness conjectures ) would be necessary. At the moment, we only have Khovanskii-type bounds in the case of Pfaffian functions. A new strategy for obtaining bounds, which might generalize to higher order equations by adapting the algorithm in this paper, has been proposed in . However, the obtained bounds are still doubly exponential. From a theoretical point, it is also interesting to ask whether zero-tests always exist. This question has been answered very precisely and in a very general context by Denef and Lipschitz . In the present setting of power series expressions, their approach uses the well-known fact that the set of differentially algebraic power series is closed under the ring operations and composition. However, the equations one obtains for sums, products, may be very complicated, so that that approaches which essentially use this fact are deemed to be very inefficient. Another simple approach was proposed by Shackell in (see the first algorithm). The idea is to keep all algebraic relations which hold between a finite number of power series in a Groebner basis . If we want to test a new relation, then we include it in and look whether we obtain a contradiction. If not, then we keep on adding the derivatives of all relations in into . Under certain hypotheses, this process always ends up in a contradiction or a proof that the added relations all hold. However, the approach does not seem to provide any reasonable complexity bounds. Yet another interesting approach to the zero-test problem is to change our point of view. The differentially algebraic power series > at the top of this section are usually specified by a finite number of algebraic differential equations and initial conditions. Now instead of asking whether a given expression represents zero, we may ask for which initial conditions for ,\,\> the expression represents zero. It turns out that the set of such initial conditions is a closed algebraic set . The ``difficult'' cases in the zero-test correspond to the situation in which the original initial conditions are in the closure of an open subset of where the answer is ``easier''. It would be interesting to investigate whether this approach of varying the initial conditions may yield a better power series analogue for Khovanskii's results. A present disadvantage of the method is that it only applies in the convergent case and that it is not yet clear how to obtain complexity bounds. The approach in this paper is similar to the algorithm in . A better understanding (and a complexity analysis) of this algorithm were obtained in . In order to explain the underlying idea behind the present algorithm, let us assume for simplicity that and that > satisfies the algebraic differential equation . Now suppose that we want to test whether for a second algebraic differential polynomial . Then we first use differential algebra to determine a third equation 0> which is equivalent to and under certain non-degeneracy conditions. Now we consider as an indeterminate and try to solve 0> in a suitable differential overfield > of [[z]]>. This field > consists of so called logarithmic transseries and has the nice property that 0> still has a unique solution in > for the initial conditions of . Hence, if and only if 0> admits a solution > in >, in which case we have =f>. The approach has the advantages that it accommodates divergent differentially algebraic power series ,\<\ ldots\>,\> and that the degeneracy of the initial conditions is not amplified during the resolution process. We also have a good hope to obtain complexity bounds along the same lines as in and some hope to generalize the approach to the multivariate setting. We finally expect the approach to be one of the most efficient ones in practice, although no implementations are available yet. Let > be an of characteristic . This means that all elements of > can be represented effectively and that there are algorithms for performing the field operations and testing equality (or, equivalently, for zero-testing). Let > be an ( the differentiation is effective too). We assume that the elements of > are formal power series in [[z]]>, that \\ C[z]>, and that the differentiation > on > corresponds to the differentiation =z*\/\ z> on [[z]]>. Moreover, we will assume that > is an , there exists an algorithm which takes > and \> on input and which computes the coefficient \> of > in . Notice that this implies the existence of an algorithm to compute the valuation of >. Now consider a non zero differential polynomial [F,\,F]\{F}> of order (recall that =\ F>) and a power series solution [[z]]> to . We will assume that is not a multiple solution, Q|\ F> (f)\0> for some {0,\,r}> (if is a multiple solution, then we may always replace by a non-zero Q|\ F>> and continue doing this until is no longer a multiple solution). Choose such that the valuation of Q|\ F> (f)> is minimal, say . Then modulo a transformation of the form <\expand|equation*> f\f+\+f*z+*z and division of the equation by a suitable power of , we may also assume that <\equation> Q=L F+z*M, where [\]> and {F}>. Let \[k]> be the polynomial we get from when reinterpreting > as an indeterminate . Then () yields a recurrence relation for all but a finite number of coefficients of : <\equation> f=-(k)>*(M(f)). Indeed, the only for which this relation does not hold are roots of >. There are at most such and they correspond to the initial conditions for . Let be the largest root of > in > (or 1> if such a root does not exist). Then we notice in particular that is the unique solution to whose first coefficients are ,\,f>. In what follows, we will show that the differential ring {f}> is again an effective power series domain. Now elements in {f}> can naturally be represented as the images of differential polynomials in {F}> under the substitution f>. It therefore suffices to design an algorithm to test whether for a given differential polynomial {F}>. Our algorithm is based on Ritt reduction and the resolution of algebraic equation in more general rings of formal power series. We will use standard notations from differential algebra: <\itemize> > denotes the and > denotes the of a differential polynomial . The of {F}> is given by P=(r,d)\\\ >, where is the order of and > P> the degree of in >. Notice that the set > of possible ranks is well-ordered the lexicographical ordering. We will write > for )>. Given {F}>, we denote by the of with respect to . We thus have a relation <\expand|equation*> I>*H>*A=X*B+(A rem B), where ,\\\>, {F}> and rank B>. <\remark> At a first glance, our setting may seem less general than the one in the beginning of section . However, since we will prove that {f}> is again an effective power series domain, we may repeat the construction after replacing > by {f}>, and add as many other functions ,\,f> as we like. In fact, it suffices to add one > for each new subexpression of the form \g\ >. It is well known that any non-trivial algebraic equation with coefficients in [[z]]> has a solution in the field

>>> of Puiseux series over the algebraic closure > of >. We will sketch the proof of an analogous result in the case of algebraic differential equations. For a full proof (of a more general result) we refer to . In order to solve equations of the form f=1>, it is clear that solutions to such equations might involve logarithms. In fact, they may even involve iterated logarithms. Let > be the totally ordered group of with powers in >. More precisely, the elements of > are monomials <\equation> \=z>*(log z)>*\*(log z)>, where ,\,\\\<\ bbb-Q\>> and > stands for the -th iterated logarithm. Given such a monomial, we write \1> if and only if \0>, where denotes the least with \0> in (). This defines a total ordering >> on >. The asymptotic relation \\> corresponds to writing =o(\)> as 0> in analysis. A subset \\> is said to be , if there exist monomials \1,\,\\1> and > in

>, such that \\

>*\<\ cdots\>*\

>*\>. A is a mapping \> with grid-based support. We will usually write such series using the infinite sum notation

\ \\>f>*\> and we denote the set of all logarithmic transseries by =>>. Since the support of each non-zero \> is grid-based (whence well-ordered), this support admits a >>-maximal element > which is called the of . It can be shown that

>> is a field for the operations <\expand|eqnarray*> |