> <\body> ||<\author-affiliation> CNRS, LIX, École polytechnique 91128 Palaiseau Cedex France |>>||<\doc-note> This work has been supported by the ANR-10-BLAN 0109 LEDA project. > ||> Let be a field of characteristic zero. A power series K|]>> is said to be if it satisfies a non-trivial differential equation ,f,\,f>|)>=0>, where is apolynomial with coefficients in . The set of D-algebraic power series contains many classical transcendental functions, such as , , >, , and it is closed under the ring operations, restricted division, differentiation and composition. This makes the differential ring of D-algebraic power series suitable as a framework for exact computations with mathematical expressions that involve transcendental functions. The notion of D-algebraic power series admits a straightforward generalization to the multivariate context. In this case, we require the satisfaction of a non-trivial algebraic differential equation with respect to each of the partial derivatives. The multivariate context allows for some additional operations, such as the resolution of implicit power series equations and general monomial transformations with rational powers. Again, the set of D-algebraic power series is stable under such operations. There are two main aspects about computations with formal power series. On the one hand, we need fast algorithms for the computation of coefficients. There is an important literature on this subject and the asymptotically fastest methods either rely on Newton's method or on relaxed power series evaluation. On the other hand, there is the problem of deciding whether a given power series is zero. This problem is hard in the sense that we need to check the cancellation of an infinite number of coefficients. Therefore, arelated question is how to represent power series in such a way that we can design such zero tests. We also notice the asymmetric aspect of the problem: given a non-zero series, it is usually easy to prove that 0>: it suffices to compute a non-zero coefficient. However, if vanishes, then it is potentially difficult to establish aformal proof of this fact. In this paper, we will focus on the second aspect. We will consider various representations for D-algebraic power series, show how to perform common operations on power series when using these representations, and also present several zero tests. All representations are based on a combination of differential equations satisfied by the power series and initial conditions. However, depending on additional properties of these equations, some representations are more suitable for performing common operations and zero testing. For global computations with algebraic differential equations, it is convenient to use the classical framework of differential algebra. In addition, we need some technology in order to deal with initial conditions. One key ingredient is the determination of the number of initial conditions which are needed in order to guarantee that a power series solution of a system of differential equations is unique. For this, we will use a similar technique as the one introduced by Denef and Lipshitz in, and develop this technique in further detail. Apart from a first section with some reminders from differential algebra, the paper is subdivided into three main parts. In section, we first focus on the univariate case and the representation of a D-algebraic series by a single differential polynomial that annihilates together with a sufficient number of initial conditions. In section, we remain in the univariate setting, but switch to more flexible representations of D-algebraic series as solutions to systems of algebraic differential equations with sufficiently many initial conditions. In section, we generalize our results to the multivariate setting and also consider the additional operations of solving implicit equations, composition, and monomial transformations. In section, we effectively represent D-algebraic power series by a pair >, where K|]>> is a computable power series (meaning that the function f> is computable) and a non-zero differential polynomial K> such that =0>. Specializing a more general result from, we will show how to compute a number \\> (called a root separation bound for at ) with the property that the equation =0> admits no other solutions with \\> (where denotes the usual valuation in ). Moreover, if is a \Pnon-degenerate root\Q of (in the sense that \0>, where > is a simpler non-zero differential polynomial, called the separant of ), then we actually obtain an explicit recurrence relation for > in terms of ,\,f> for \>. In section, we will exploit the existence of such a recurrence relation in the non-degenerate case, by giving a first zero test for series in the differential field |f|\>> generated by . We will next strengthen the root separation bound by not only looking for other solutions of =0> in |]>>, but also in |]>>. In section, this allows us to simplify the zero test (along similar lines as in) and also widen its scope to power series that depend on a finite number of parameters(Remark). We finally consider the case when is ill specified as a degenerate root of . In sections and, we give algorithms for computing root separation bounds in this case, as well as non-degenerate annihilators. In principle, annihilators of complex D-algebraic series (such as large expressions in other D-algebraic series) can be computed using brute force (Proposition). However, this technique is, in general, very inefficient. For this reason, we introduce the more flexible framework of D-domains in section. In this framework, we express D-algebraic series as rational functions in a finite number of D-algebraic series that satisfy a special kind of system of algebraic differential equations with initial conditions. We show how to adopt the major results from section to this setting. In section, we turn our attention to multivariate D-algebraic series. We will start by showing how to interpret a multivariate D-algebraic series in ,\,z|]>|]>> as a Dalgebraic series in > whose coefficients are D-algebraic series in ,\,z|]>|]>>>. We next generalize the notion of a D-domain and show that the above reduction to the univariate case can be done at the level of D-domains. We conclude by giving some algorithms for some typical multivariate operations: the resolution of implicit equations, composition, and monomial transformations. In each of these cases, we will show how to avoid the computation of differential annihilators as much as possible, by remaining in the framework of multivariate D-domains. There are several approaches to the zero test problem for D-algebraic power series and we refer to for a brief discussion. From a logical point of view, the most important decision problems for power series solutions to algebraic differential equations with initial conditions were settled in. One essential tool in this paper is the computation of a generalization of root separation bounds for more general decision problems. In a sense, this paper merely consists of specializations of these results to more specific problems. Nevertheless, we think that we introduced some noteworthy improvements that we will point out now. It should first be emphasized that the papers are based on a more general decision procedure for testing whether systems of differential equations and inequations with initial conditions admit solutions. Efficiency is not the major concern here. The authors also do not attempt to state their results in terms of classical differential algebra, even though they are aware of this possibility. From our point of view, one main contribution of this paper is to isolate the part of the problem that can be dealt with using classical differential algebra techniques from the part where initial conditions and root separation bounds come in(notice that provides an interesting alternative way to achieve this goal). This allows us to explicitly state our zero test algorithms, which we also believe to be more efficient than the ones from. Our approach also contains a few theoretical improvements. First of all, we mainly work over a so called \Peffective power series domain\Q K|]>> instead of the constant field. For instance, we may take |\|\>\K|]>>, where <\equation*> \=2>*B|n*>*z is the differentially transcendental power series involved in the Euler-Maclaurin formula for the >-function. Similarly, the conditions on the constant field are slightly weaker: we merely require an effective constant field with an algorithm for the computation of all positive integer roots of univariate polynomials with coefficients in . The improved zero test from section also allows for power series that depend on parameters. These theoretical improvements were actually introduced in, but the current presentation is simpler and more systematic. In particular, we only need to consider logarithmic power series instead of logarithmic transseries in the correctness proof of the improved zero test from section. Furthermore, we included algorithms for the computation of non-degenerate annihilators and root separation bounds in the degenerate case. Section contains no theoretical improvements, but we expect the more flexible framework of Ddomains to be most suitable for practical computations. It is interesting to see that the root separation bounds and both zero tests from section can be generalized to this setting. In particular, for the computation of root separation bounds, we introduce the dominant Hermite normal form, which seems interesting in its own right. As we show in section, a multivariate D-algebraic series in ,\,z|]>|]>> can always be regarded as a D-algebraic series in > whose coefficients are D-algebraic series in ,\,z|]>|]>>>. From the logical point of view, decision problems for such series therefore reduce to their univariate counterparts. However, there are a few additional operations, such as solving implicit equations, extraction of coefficients and monomial transformations. Not only do we present algorithms for carrying out such operations, but we also discuss ways to make this efficient, in the framework of multivariate D-domains. Let us recall some standard notations from differential algebra. Let be a field of characteristic zero and let be a differential -algebra that is also an integral domain. We will mainly work with respect to a single derivation >. Given a finite number of indeterminates ,\,F>, we will denote by ,\,F|}>> or simply by > the differential ring of differential polynomials in ,\,F> and by |F,\,F|\>> or |F|\>> its fraction field. We will assume an admissible ranking > on the set = F:i\,k|}>,j\\|}>>. For instance, we may take F\\> F>> whenever j> or > and i>. Given such aranking, the of a differential polynomial A\A> is the highest variable F> occurring in when is considered as a polynomial in >. We will denote by > the leader of . Considering as a polynomial in >, the leading coefficient > is called the of , =\ P/\ \> the , and we will denote =I*S>. If has degree in >, then the pair ,d|)>> is called the of and such pairs are ordered lexicographically. We will also denote >=\> in that case. Given ,\,Q\A\A>, we say that is with respect to ,\,Q>> if there exists an such that \\\> \>> or =\=\>> and > P\deg> Q>. The process of provides us with a relation of the form <\eqnarray*> >>*\*I>>*S>>*\*S>>*P>|| Q+\+\*Q+R,>>>> where ,\,\,\,\,\\\>, ,\,\\A|]>>, A> and where is reduced with respect to ,\,Q>. We will denote ,\,Q|)>>. Given ,\,Q\A>, we recall that =,\,Q|]>=A|]> Q+\+A|]> Q> stands for the differential ideal generated by ,\,Q>. If ,\,Q\A\A>, then we also denote =H>*\*H>> and recall that <\eqnarray*> :H>>||A:\n\\,H*P\|}>>>>> forms a differential ideal. We say that ,\,Q> forms an if > Ritt reduces to itself with respect to ,\,Q,Q,\,Q> for each . In that case the set of differential polynomials that reduce to zero with respect to ,\,Q> coincides with the differential ideal :H>>. In section, we will also consider differential rings and differential polynomials with respect to a finite number of pairwise commuting derivations ,\,\>. In that case, > has to be replaced with the set of all expressions >*\*\> F> with ,k|}>> and ,\,j\\>. The notion of admissible rankings and Ritt reduction can be extended to this setting and we refer to classical textbooks on differential algebra for more details. In order to explicitly write down a differential polynomial A>, it is convenient to use vector notation. We will index differential monomials by vectors =,\,i|)>> where each> is itself a finite sequence =,\,i>|)>> that may be padded with zeros whenever necessary. We denote <\eqnarray*> > F>|| F|)>>,>>>> after which we may write <\eqnarray*> ||>P>*\> F,>>>> with >\A>. For a fixed degree \>, it will be convenient to denote by > the homogeneous component of of degree : <\eqnarray*> >|||\|>=d>P>*\> F>>||\|>>||i.>>>> The largest with \0> will be called the of and we will denote it by . The smallest with \0> will be called the of and we denote it by . It will also be convenient to denote d>=P+\+P> and d>=P+\+P>. Given a differential polynomial A> and a \Ppoint\Q ,\,f|)>\A>, it is often convenient to consider the of by , which is defined to be the unique differential polynomial \A> with <\equation*> P|)>=P|)> for all \A>. The coefficients >=|)>>> of > can be expressed directly by using aTaylor series expansion: <\eqnarray*> >>||!>*P|)>>>>||)>>>|||\|>> P| F|)>|)>>>>>|!>||i!.>>>> In particular, we get >=\!*P|)>>>. Assume now that K|]>> and =z*\/\ z>. Given A>, we will denote by \\\|}>> its valuation in . This valuation naturally extends to differential polynomials in > the inclusion |]>\K|]>>. Notice that should not be confused with . Assume now that and let A,\ F|]>\> be a homogeneous differential polynomial in a single variable of degree . Then we will denote by \K> the polynomial with <\eqnarray*> >||>>|)>>*n|\|\<\|\|\>>>>>||\|\<\|\|\>>>||+2*i+\+r*i.>>>> For any series K|]>>, we then have <\eqnarray*> +d*v>>|||)>*f>.>>>> We will also denote by > the largest root of in >, while taking =-1> if no such root exists. For some purposes, we will occasionally consider logarithmic power series K|]>>. Such series can still be considered as power series +f*z+\> in and we will still denote by > the valuation of in . The coefficients > are polynomials in >, and we will write =f>*>+\+f>. Notice that > maps *z> into itself for each . <\proposition> Consider a non-zero linear differential operator K|]>> and write *\+\+L*\> with \0> and \0>. Then there exists a unique :K\K*>> with g=g> for every K>. <\proof> Let us first prove the existence of >. If , then we may write > with K|]>*\>, and the equation admits the solution <\eqnarray*> ||+\|)> >,>>>> since \deg h> for every K>. For general , we may write *\> with \0> and take g=\ > g> with <\eqnarray*> h*|)>>|||*\*>*.>>>> This proves the existence of >. For any K> of degree s> in , we also notice that =d*\*|)>*L*f\0>. This implies the uniqueness of >. Let be a field. Let K|]>> be a differential subalgebra of |]>> for > with the property that for all A> and A\> such that K|]>>, we have A>. We will also call a . A series K|]>> is said to be over if it satisfies a non-trivial differential equation =0> with A\A>. In positive characteristic 0>, any series K|]>> satisfies the linear differential equation <\eqnarray*> *-1|)>*\*-|)>|]>>||>>> whence any series is D-algebraic (indeed, -i> annihilates all series in *K|]>|]>>). From now on, we will therefore assume that has characteristic zero. <\proposition> The series K|]>> is D-algebraic if and only if > admits finite transcendence degree over . <\proof> Assuming that K|]>> is D-algebraic over , pick A\A> of minimal Ritt rank F,d|)>> with =0>. Then \0> and ,\ f,S|]>> is stable under the derivation >, whence \B> and A\r+1>. Conversely, assume that A=r>. Then ,\> f> satisfy a non-trivial algebraic relation, whence is D-algebraic. <\proposition> The set > of D-algebraic series over forms a power series domain. <\proof> Let A>. Then \A+A>, whence A\trdeg A+trdeg A\\> and A>. Similarly, \A*A>, whence A\trdeg A+trdeg A\\> and A>. Clearly, f|}>\A>, so A f|}>\trdeg A> and f\A>. Assume finally that K|]>>. Then \*A|)>|]>>, whence A\trdeg A+trdeg A+1\\>, so that A>. Assume now that is an effective power series domain. The most obvious way to effectively represent a D-algebraic power series in> is to represent it by a pair > where is a computable series and A\A> a non-trivial annihilator with =0>. We define the of as an annihilator of to be >. We also say that the annihilator is if \0>, and notice that the multiplicity of a non-degenerate annihilator is one. In order to make Proposition effective, we will need a way to compute a non-degenerate annihilator as a function of an arbitrary annihilator. This is not completely immediate, and we will postpone the presentation of an algorithm for doing so to the end of this section. Let K|]>> be D-algebraic over with annihilator A\A>. Assume that there exists a number \\> such that for any \K|]>\> with |)>=0> and -f|)>\\>, we have \f>. Then the smallest such number > will be denoted by > and we call it the of at . It corresponds to the number of initial conditions that should be known in order to determine in a unique way as a root of . In fact > always exists and, as we will see in the next section, we can give an algorithm to compute it under suitable assumptions. <\proposition> Assume that is D-algebraic over with annihilator A\A>. Then the following root separation bound holds: <\equation> \\max>|)>,Z>>|)>+1. <\proof> Let > and =v|)>>. Given =f+\\K|]>> with |)>\\>, we have <\eqnarray*> |)>|]>+d*n>>||>*\.>>>> Now assume that max,Z>|)>+1>. Then <\eqnarray*> d>|)>|)>>|>|*n\\+d*n,>>>> whence <\eqnarray*> |)>|]>+d*n>>||>*\.>>>> Since Z>>, we get >\0>, which entails |)>\0>. The following proposition also provides us with a partial converse. <\proposition> Let A\A> and K|]>>. Assume that \0> and that |)>\2*\>, with \max|)>,Z>|)>+1>. Then there exists a unique root \K|]>> of with -f|)>\\>. <\proof> Notice that \0> implies that \0>, so that |)>,Z>|)>> is finite. Let =v|)>\\>. We have to show the existence of a unique series \K|]>> with |)>\\> and |)>=0>. We may decompose <\eqnarray*> >||-\,>>|>|||)>>*z>.>>>> Extracting the coefficient of +n>> in the relation |)>=\|)>> now yields <\eqnarray*> >*\>|||)>+n>.>>>> For all \>, we have >\0> and |)>+n>> only depends on ,\,\>. In other words, the relation() actually provides us with a recurrence relation for the computation of >. We say that is if its elements can be represented effectively and if all field operations can be carried out by algorithms. We will call an if all positive integer roots of polynomials over can be determined by algorithm. In particular, this means that admits an effective zero test, there exists an algorithm which takes an element of on input and which returns if and otherwise. A power series K|]>> is said to be , if there exists an algorithm for computing > as a function of \>. The power series domain will said to be , if its elements are all effective power series and if the differential -algebra operations can be carried out by algorithms. We notice that the differential -algebra |]>> of all computable series is effective, although it does not admit an effective zero test. Assume now that we are given an effective power series domain with an effective zero test over an effective diophantine field . Assume also that we are given an effective Dalgebraic power series K|]>> and an annihilator A\A> for . Assume finally that the annihilator has multiplicity one, so that we may compute |)>> and >> by expanding the power series coefficients of >. In other words, the bound() from Proposition provides us with an effective upper bound for >. Given a polynomial A>, we will now give an algorithm (or > when we want to make the dependency on and explicit) for testing whether =0>. In particular, this shows that the -algebra |f|\>\K|]>> is again an effective power series domain. <\named-specified-algorithm|ZeroTest>> : A> the result of the test >>0> <|named-specified-algorithm> <\listing> If A> then return the result of the test If |)>> then return *\>|)>> If |)>> then return |)>> If 0> then return > Let \max|)>,Z>,v|)>,v|)>,v|)>,Z>|)>+1> Return the result of the test |)>\2*\> <\proof> We first notice that recursive calls only occur for differential polynomials of astrictly smaller Ritt rank. This guarantees termination of the algorithm. As to its correctness, we clearly have =0\*\>|)>=0> at line 2 whenever =0>. Assume now that we reach line 3 with =0>. Then the degree of in its leader cannot be one, since this would imply =S>, and we know that \0>. Consequently, >> is aconstant multiple of >, whence *Q=T*S+Q rem S> for some \> and A>, and =0\|)>=0>. Assume now that we reach line 4. We have *S*P=U*Q+\+U*\ Q+P rem Q> for some \> and ,\,U\A>. Since \0> and \0>, it follows that =0\=0>. Assume finally that we reach step 5. If |)>\2*\>, then we clearly have \0>, so assume that |)>\2*\>. Applying Proposition, we obtain a unique power series \K|]>> with |)>=0> and -f|)>\\>. It follows that ,1>|)>=v|)>\\>, ,1>>=Z>\\>, |)>|)>=v|)>\\> and |)>|)>=v|)>\\>. The relation *S*P=U*Q+\+U*\ Q> therefore implies |)>=0>. Applying Proposition to >, we obtain the bound >\\>. Since -f|)>\\>, we conclude that =f>. <\remark> As a variant to the algorithm, we can also check whether =\=Q=0> for more than one ,\,Q\A> at the same time. In that case, we keep reducing until we find a A> with *S|)>\0> and such that for all ,\,Q,P|}>>. <\remark> One drawback of the above zero test is that it does not apply to power series that depend on a finite number of parameters ,\,\> in . Indeed, this would require aroot separation bound that is uniform in these parameters. Unfortunately, the largest integer root of a simple polynomial such as > can become arbitrarily large, so the best uniform root separation bounds are usually >. In practical applications, the series is often the solution of a classical initial value problem, in which case >=-1>. One disadvantage of the zero test from section is that >> still depends on in quite an unpredictable way. In particular, even for simple , this quantity might become arbitrarily large. In this section, we will give an improved version of our algorithm that does not have this drawback. The idea is to not only consider ordinary power series solutions to our differential equations, but also logarithmic power series solutions in |]>>, as introduced in section. Let K|]>> be D-algebraic over with annihilator A\A>. Assume that there exists a number \\> such that for any \K|]>\> with -f|)>\\>, we have \f>. Then the smallest such number > will be denoted by >> and we call it the of at . Proposition naturally strengthens to this setting: <\proposition> Assume that is D-algebraic over with annihilator A\A>. Then the following strong root separation bound holds: <\equation> \>\max>|)>,Z>>|)>+1. <\proof> The proof is similar to the proof of Proposition with the following change. Writing =\*+\+\> with \0>, we now have <\eqnarray*> |)>|]>+d*n>>||>*\*+\|)>>>>> instead of(), and where |)>> stands for a polynomial of degree at most in >. The consideration of logarithmic solutions leads to a better bound for the existence part of Proposition. <\proposition> Let A\A> and K|]>>. Assume that \0> and that |)>\2*\>, with \v|)>+1>. Then there exists a root \K|]>> of with -f|)>\\>. <\proof> The proof is analogous to the proof of Proposition, with the exception that() should be replaced by <\eqnarray*> >+n|)>*\>|||)>+n>.>>>> For all \>, the right hand side |)>+n>> again only depends on ,\,\>, but the constant term > of the differential operator *\+\+L\J>+n|)>\K|]>> may vanish if =0>. Yet, Proposition still implies that the equation =g> admits asolution in > for any K>, which is sufficient for the existence of a solution> to the equation |)>=0>. In the proof of the algorithm , we only needed the existence of the solution \K|]>> with |)>=0> and -f|)>\\>. In view of what precedes, we may thus improve the algorithm as follows: <\named-specified-algorithm|ZeroTest>>> : A> the result of the test >>0> <|named-specified-algorithm> <\listing> If A> then return the result of the test If >|)>> then return >*\>|)>> If >|)>> then return >|)>> If 0> then return >> Let \max|)>,Z>,v|)>,v|)>,v|)>|)>+1> Return the result of the test |)>\2*\> <\remark> Recall from Remark that the zero test from the previous section does not work if or depends on a finite number of parameters ,\,\> in . One interesting aspect of the improved zero test is that we no longer require any root separation bounds which depend on , so the zero test still works if depends on parameters (when using the technique of dynamic evaluation for examining the finite number of branches that can occur depending on algebraic conditions on the parameters). In fact, the original equation may also depend on parameters, as long as we have a uniform bound for >>. Assume that we are given an effective power series domain with an effective zero test over an effective diophantine field . Assume also that we are given an effective Dalgebraic power series \|]>> and an annihilator A\A> for . Let us show how the zero test algorithm from the previous section can be used in order to compute >, thereby providing an effective bound for > Proposition. <\named-specified-algorithm|RootSeparationBound>> : a computable D-algebraic series and A\A> with =0> an upper bound > for >. <|named-specified-algorithm> <\listing> Let > is an index with |)>>|)>|)>>\0> Repeat the following Let |\|>> and \max|)>,Z>|)>+1> If then return > Let > and > be indices with =\+\>, |\|>=d-1>, |\|>=1>, and set P|)>>> Let \max|)>,Z>|)>+1> If |)>\2*max,\|)>> then Let \K|]>> be such that |)>=0> and -f|)>\max,\|)>> If >>|)>>|)>> for all > with |\|>\d> and |)>>\0>, then return > Let > be an index with d>|)>>|)>d,+f>|)>>\0> <\proof> We first notice that strictly decreases at every iteration of the main loop, which implies the termination of our algorithm. As a loop invariant, we also notice that |)>>\0>> (whence \0>>) whenever we are at line 3, which means that we indeed have an algorithm for the computation of \\>. If , then the correctness of line4 follows from Proposition. Otherwise, we construct such that |)>>=P|)>>\0>> and \0>>, whence the computability of > at line 6. If |)>\2*max,\|)>> at line 7, then Proposition implies the existence and uniqueness of > at line 8, and the relation() actually provides us with an algorithm to compute the coefficients of>. Moreover and > satisfy the assumptions for applying the algorithm >>> to and its derivatives at line 9. Now if =d>, then in particular =0> and =f> by the uniqueness of>. Consequently, the zerotests >>|)>>|)>> will indeed all succeed at line 9 and we will return a correct bound > by Proposition. Conversely, if >>|)>>|)>> holds for all > with |\|>\d> and |)>>\0>, then in particular |)>=0>. Since |)>\\>, we also have >,d>|)>=v|)>> and >,d>>=Z>>, whence > by Proposition and =val P>>=d>. If \d>, then this means that we will reach line 10 and find an index > with |\|>\d> and |)>>\0>. <\remark> In practice, it is better to replace line 9 by a simultaneous zero test as outlined in Remark. <\proposition> There exists an algorithm which, given a computable D-algebraic series and A> with =0>, computes an annihilator \A> for of multiplicity one. <\proof> We may use a variant of the algorithm . Indeed, it suffices to return instead of > in step 4, and instead of > in step 9. <\proposition> There exists an algorithm which, given a computable D-algebraic series and A> with =0>, computes a non-degenerate annihilator \A> for . <\proof> Using the previous proposition, we may assume without loss of generality that has multiplicity one. In particular, we have a zero test for elements in >. Now let P> and keep replacing S> as long as =0>. Then we will end up with a such that =0> and \0>. We are now in a position to make Proposition effective. We first need a general algorithm for computing algebraic dependencies. <\proposition> Let be an effective integral domain with an effective zero test. There exists an algorithm which takes polynomials ,\,P\A,\,G|]>> on input, and which produces a relation \A,\,F|]>> with ,\,P|)>=0>. <\proof> Let deg P>. Given \>, the set of power products =:i\\|}>> with =\:i+\+i\n|}>> and =P>*\*P>> contains at most \n> elements. The degree of any polynomial in > is bounded by , and the space of polynomials in ,\,G|]>> of degreed*r> has rank \n> as a free -module. Taking \> minimal such that \>, it follows that the set > contains a non-trivial linear dependency \>\*P=0>, which we may compute using linear algebra. If is a D-algebraic power series with non-degenerate annihilator A> of order, then the -algebra > is contained in the -algebra ,\ f,S|]>>,which is stable under >. <\proposition> The set > of D-algebraic series over forms an effective power series domain. <\proof> Let ,f\A> be represented by pairs ,P|)>> and ,P|)>>> with |)>=|)>=0>>. Applying Proposition, we may assume without loss of generality that the annihilators > and > are non-degenerate, of orders > and >. Then <\eqnarray*> ||,\,\-1> f,S>|)>,f,\,\-1> f,S>|)>|]>>>>> is an effective -algebra which is stable under >. For +f,f*f,\ f|}>\B>, we may use Proposition in order to compute an -algebraic relation between g,\,\+r+2> g>. Similarly, assuming that /f\B> with \0>, the algebra |]>> is stable under >, so we may compute an -algebraic relation between g,\,\+r+3> g>. Of course, the algorithm from the proof of Proposition uses brute force for for finding algebraic relations, so any algorithm that relies on this method is deemed to be quite inefficient. In the section below, we will discuss algorithms that avoid relying on Proposition for the computation with D-algebraic series. In the algorithms from the previous sections, we essentially represent D-algebraic power series by elements of |f|\>\K|]>>, where K|]>> is a computable root of a differential polynomial A\A>. Since |f|\>\K|]>> is itself an effective power series domain with an effective zero test, we may also form towers |f|\>\|f|\>> and represent D-algebraic power series by elements of such towers. This generalization is useful for representing expressions involving , the algebra operations, and other D-algebraic operations such as , , etc. Indeed, differential polynomials that annihilate such expression can quickly become quite large. In this section, we will introduce an even more convenient representation based on differential algebra, which generalizes the construction of towers and provides more flexibility for representing solutions to implicit equations at the end of section. An over is a differential algebra over of finite transcendence degree over together with a differential -algebra morphism :B\K|]>> which we will call the . A second abstract D-domain > with evaluation mapping|~>> is said to be to if |~>> admits the same image as >. Assuming that is an effective power series domain with an effective zero test over an effective diophantine field, we say that > is if > is computable and > is computable for each ; in that case, we also say that is an effective D-domain. A is an abstract D-domain of the form <\eqnarray*> ||,\,F|}>/I>>|||,\,P|]>:>*\*H>|)>>,>>>> where ,\,P\A,\,F|}>> are such that <\eqnarray*> >*\*H>+I|)>>|>|>>> and where the leaders of ,\,P> are > F,\,\> F> for certain ,\,r\\>. It will be convenient to lift the evaluation mapping > to ,\,F|}>> using =\>. Then > becomes simply the evaluation mapping at |)>,\,\|)>|)>>. In particular, > is effective as soon as is a tuple of computable power series. We will call the D-domain if \A|}>> for each . We will call the D-domain if > is of the form =S*\ F-R> with ,R\A,\,F|]>> for all . <\proposition> <\enumerate-alpha> Given any D-domain over and B>, the series > is D-algebraic over . If is effective, then we may effectively compute an annihilator for >. Any D-algebraic series over is represented by an element of an unmixed Ddomain over . If is effective and A>, then we may effectively compute such a . <\proof> Given a D-algebraic domain over and B>, the sequence P,\ P,\> contains non-trivial algebraic dependencies which can be computed using Proposition. This proves ). Inversely, given A>, we may compute a non-degenerate annihilator A> for using Proposition. Then /:H>|)>> with =f> defines an unmixed D-domain in which represents . <\proposition> Any D-domain is equivalent to an unmixed D-domain. If is effective, then this reduction is effective. <\proof> Let ,\,f\B> be generators of the -algebra and let be the transcendence degree of over . For each >, we may compute a non-degenerate annihilator > for > using Proposition. Then =A,\,F|}>/,\,P|]>:>*\*H>|)>>|)>> with |)>=f> defines an unmixed D-domain that is equivalent to . <\proposition> Any D-domain is equivalent to a Pfaffian D-domain. If is effective, then this reduction is effective. <\proof> Let us first show that is equivalent to a D-domain with orders =1>. Modulo the replacement of > by P>, we may assume without loss of generality that \1> and > F> P=1> for all . Now consider formal variables > with i\k> and j\r>. Let = F:i\k,j\r|}>>, |~>=:i\k,j\r|}>\ F-1>:i\k|}>> and consider the algebra morphism :A|]>\A|~>|]>>, with F|)>=F> for r> and > F|)>=\ F-1>>. Consider the set > of all polynomials \A|~>|]>> with =\ F-F> if r> and >=\|)>>. Let > be the ranking on = F:i\k,j\\|}>>. We define a ranking on = F:i\k,j\r,k\\|}>> by setting F\\>*F,j>> whenever F\\+k> F>> or F=\+k> F>> and k>. Then the D-domain =A|~>|}>/> with =|]>:H>>> is equivalent to . Assuming that =1> and > F> P=1> for all , let us now show that is equivalent to aPfaffian Ddomain. We may assume that we ordered the variables > such that \\\F>>. In particular, this implies that =S*\ F-R> with ,R\A,\,F|]>>. Let us prove by induction over that we may replace > by a differential polynomial of the form =S*\ F-R> with ,R\A,\,F|]>>. So assume that the induction hypothesis is satisfied for all smaller. We have =D*\ F-N> with A,\,F,\ F,\,\ F|]>>. Let be the maximum of the degrees of and , and i>=S*\*S>. Then substitution of /S> for each F> with i> in i>*D> and i>*N> yields two polynomials > and > in ,\,F|]>> such that i> P-*\ F-R|)>\,\,P|]>>. This means that we may replace > by *\ F-R>. Before we generalize the zero test algorithms from section, we will need a way to asymptotically normalize systems of linear differential equations with power series coefficients. The normalization that we will use is an asymptotic variant of the Hermite normal form. Let us first consider a square k> matrix K|]>k>>. We say that is in if is upper triangular and there exist integers p\\\p\k> such that <\itemize> =0> whenever l> or p>. ,p>\deg M>> for all \i\l>. If has maximal rank , then we must have =i> for each . It can be shown that there exists a unique unimodular matrix K|]>k>> such that is in Hermite normal form. Moreover, \K|]>k>> and there is an algorithm for the computation of if is an effective field. Let us now consider a matrix K|]>|]>k>> of rank . Recall that K|]>> commutes with > following the law |)>*z=z*P+i|)>>. For each we will denote by \K|]>> the -th row of and by <\equation*> D|)>=*M|)>,\,*M|)>|)>\K its \Pskew dominant coefficient\Q, where <\equation*> v\v|)>\min|)>,\,v|)>|)>. If =0>, then we understand that |)>=0>. The matrix > with rows |)>,\,D|)>> will be called the row dominant matrix of . We say that is in if > is in Hermite normal form. Any matrix |]>|]>>k>> with an inverse in |]>|]>k>> and such that is in dominant Hermite normal form will be called a . We claim that such a matrix always exists. What is more, if the entries of are computable power series, then we may use the following algorithm to compute . <\named-specified-algorithm|NormalizationMatrix>> : a matrix K|]>|]>k>> with computable coefficients and rank a normalization matrix in |]>|]>> for <|named-specified-algorithm> <\listing> Let D> Let K|]>k>> be such that is in Hermite normal form Let K|]>|]>k>> be such that =z|)>>*T*z|)>>> If has rank then return Otherwise return *U> <\proof> If , then is a normalization matrix of by construction. If k>, and assuming that > is a normalization matrix of , then *U> is a normalization matrix of , since is always invertible. This proves the correctness of the algorithm. As to its termination, let and let \\\i> be minimal such that the matrix with rows >,\,D>> has rank for each r>. We claim that can only increase and that the -tuple ,\,i|)>> can only decrease for the lexicographical ordering, once stabilizes. Indeed, let =U*M>, =D|)>>, =rank M> and let \\\i>> be minimal such that the matrix with rows >,\,D>> has rank for each r>. Then the rows >,\,D>> are precisely the first rows of the Hermite normal form , and therefore form a matrix of rank . This shows that \r> and \i> for each . Having proved our claims, we may assume without loss of generality that and ,\,i|)>> have stabilized. Since the degrees of the polynomials entries of >,\,D>> can only decrease, we may also assume that >,\,D>> whence >,\,M>> have stabilized. Furthermore, we may assume that our rows were ordered in such a way that =j> for all . Modulo division of ,\,M> by powers of , we may finally assume that |)>=\=v|)>=0>. Then K|]>> and |)>\v|)>> for all r>. This is repeatedly possible only if > lies in the |]>|]>> module spanned by ,\,M> for each r>. Since has rank , this means that we must have , which completes the termination proof. Given an abstract D-domain , we claim that there exists a number \\> such that for any alternative evaluation mapping |~>> on , we have |~>=\> whenever |~>-\|)>\\> for all B>. The minimal such number will be called the for and we denote it by >. Our claim clearly holds when /:H>|)>> is an unmixed Ddomain. Indeed, in this case, we have <\equation*> \\max,\|)>>,\,\,\|)>>|)>, with the notations from above. The general case reduces to this particular case by applying Proposition. However, since the computation of univariate differential polynomials that annihilate given elements of may be quite expensive, we would like to have a more direct bound. We first need a few preliminaries. Consider linear differential polynomials ,\,P\K|]>,\,F|}>>. Any such polynomial can formally be viewed as an element of |]>|]>*F\\\K|]>|]>*F>. Let K|]>|]>k>> be the matrix with =M F+\+M*F>. Assuming that this matrix has rank over |]>|]>>, we may use the method from section to compute anormalization matrix K|]>|]>k>> for . We will call such a a normalization matrix for ,\,P>. Applying to the column vector with entries ,\,P> we obtain a new column vector with \Pdominant reduced\Q entries ,\,>>. By construction, the dominant coefficient >|)>>> of >> is apolynomial of the form <\equation*> >|)>>=\ F+\+\ F with ,\,\\K|]>>. We will denote by >>\K> the polynomial with >>|)> F=\>. We also denote by >>> the largest root of >>> in >, or if no such root exists. Now consider a D-domain /:H>|)>> with evaluation mapping >. Let ,\,f|)>=\=|)>,\,\|)>|)>>. Since \0>, each > is non-zero and has the same leader > F> as>. In particular, the polynomials > are linearly independent over |)>|]>>. Consequently, there exists a normalization matrix for >, whence >> and >> are well defined for all . <\proposition> Let /:H>|)>> be a D-domain with evaluation mapping > and >. Let be a normalization matrix for > and =T*P>. Then <\eqnarray*> >|>|>|)>,\,v>|)>,Z>>,\,Z>>|)>+1.>>>> <\proof> Let \v>|)>> for each . Given =f+\\K|]>> with |)>\\>, there exists a largest index with |)>=n>. We have <\eqnarray*> >|)>|]>+n>>||>>*|)>.>>>> Assuming that max,\,\,Z>>,\,Z>>|)>+1>, we also have <\eqnarray*> >1>|)>|)>>|>|\\+n,>>>> whence <\eqnarray*> >|)>|]>+n>>||>>*|)>.>>>> Since Z>>>, we get >>\0>, which entails |)>\0>, |)>\0> and |)>\0>. In order to generalize the zero test from section to the setting of D-domains, we first need a suitable counterpart of Proposition in addition to Proposition. Assume that we are given a differential ring /:H>|)>> where ,\,P\A\A> are such that >=\> F> for certain ,\,r\\>. Given \|]>> and \>, we would like to solve the system of equations |)>=0> for \K|]>> with |)>\n>. Assuming that >|)>\0> for each , we may define and > as in the previous section. Since is a normalization matrix, there also exists a matrix K|]>|]>k>> with >. Then we have |)>=0\|)>=T*P|)>=0> and |)>=0\P|)>=U |)>=0>. Now consider <\equation*> \,\,P;f,\,f>\max>|)>,\,v>|)>,Z>>,\,Z>>|)>+1. We have the following analogue of Proposition for solving the equation |)>=0> for sufficiently small >. <\proposition> With the above notations, if \\,\,P;f,\,f>> and |)>\2*\>, then there exists a unique \K|]>> with |)>=0> and -f|)>\\>. <\proof> By what precedes, it suffices to show that the equation |)>=0> admits a unique solution with |)>\\>. Let \v>|)>\\> for each . Recall that we may write <\eqnarray*> |)>>>|| F+\+\ F>>>> for each , with \K|]>>. We now decompose each > as <\eqnarray*> >||-\,>>|>|| F*z>.>>>> Extracting the coefficient of +n>> in the relation |)>=\|)>> now yields <\eqnarray*> >*|)>>|||)>+n>.>>>> For all \>, we have >\0> and |)>+n>> only depends on coefficients |)>> with n> and coefficients |)>> with i>. Hence() provides us with a recurrence relation for the computation of >. <\named-specified-algorithm|ZeroTest>> : A> the result of the test >>0> <|named-specified-algorithm> <\listing> If A> then return the result of the test If |)>> then return *\>|)>> If |)>> then return |)>> If rem Q\0> for some then return rem Q|)>> Let \\> be an upper bound for > Let be such that =\> F> for some \\> Let \\,\,P,Q,P,\,P;f,\,f>> Return the result of the test |)>\2*max,\|)>> <\proof> The proof is analogous to the proof of the zero test algorithm from section. The zero test from the previous section may be further improved along similar lines as what we did in section. Given an abstract D-domain , the for is the smallest number =\>> such that for any alternative \Pevaluation\Q mapping |~>:B\K|]>>>, we have |~>=\> whenever |~>-\|)>\\> for all B>. The existence of such a number is shown in the same way as before and for D-domains we have the usual explicit bound: <\proposition> Let /:H>|)>> be a D-domain with evaluation mapping > and >. Let be a normalization matrix for > and =T*P>. Then <\eqnarray*> >>|>|>|)>,\,v>|)>,Z>>,\,Z>>|)>+1.>>>> <\proof> The proof is similar to the proof of Proposition. This time, \K|]>>, we again pick to be the largest index with |)>=n>, so that we may write |)>=\>*log> z+\+\> with >\0>. In the same way as before, we now get <\eqnarray*> >|)>|]>+n>>||>>*\>*log> z+\-1> z|)>.>>>> For Z>>>, we again get >>\0>, |)>\0>, |)>\0> and |)>\0>. For the analogue of Proposition, we define <\eqnarray*> ,\,P;f,\,f>>>|>|>|)>,\,v>|)>|)>+1.>>>> <\proposition> With the above notations, if \\,\,P;f,\,f>>> and |)>\2*\>, then there exists an \K|]>> with |)>=0> and -f|)>\\>. <\proof> The proof is similar to the proof of Proposition, except that() should be replaced by <\eqnarray*> |)>>||>+n|)> \|)>+n>,>>>> where >+n|)>> is the operator inverse of >+n|)>> from Proposition. In the algorithm from the previous section, it is now possible to replace ,\,P;f,\,f>> by ,\,P;f,\,f>>> in the definition of >. Given a subring K|]>=K,\,z|]>|]>>, we will denote by > the intersection of |]>> with the fraction field of . We say that K|]>> is a if is adifferential ring with respect to the derivations =z*\/\ z> such that =A> and is stable under the substitutions :z\0>. A power series domain is said to be , if the differential -algebra operations can be carried out by algorithms and for each ,n|}>> we have a computable mapping which takes A> on input and returns as a computable power series in |]>|]>>. In particular, this means that every A> can be regarded as an power series in the sense that there exists an algorithm which takes \> on input and returns the coefficient > of =z>*\*z>> in on output. We also notice that the quotient field of aneffective power series domain is an effective differential field, when representing fractions in the usual way. In particular, > is an effective differential -algebra. The above definitions can be generalized to countable dimension as follows. We let ,z,\|]>|]>=K\K|]>|]>\K,z|]>|]>\\>, where we regard each ,\,z|]>|]>> as being naturally included into ,\,z|]>|]>>. A subset K,z,\|]>|]>> is said to be a if \A\K,\,z|]>|]>> is a power series domain for each . We say that is if each > is and if we have an algorithm for computing an upper bound for the dimension of any given series A>. Given K|]>>, we let \K> denote the evaluation of at ,0|)>>. Given K|]>> and |g,\,g|\>\K|]>=K,\,u|]>|]>> with =\=g=0>>, we define the composition g=f\,\,g|)>> of and to be the unique power series g\K,\,u|]>|]>> with <\equation*> g|)>,\,u|)>=f,\,u|)>,\,g,\,u|)>|)>. We say that a power series domain K,z,\|]>|]>> is if ,\,g|)>\A> for any A> and ,\,g\A> with =\=g>. If we also have an algorithm for the computation of ,\,g|)>>, then we say that is . Let ,\,\\K,\,z|]>|]>> with 0> and =\=\=0>. Assume that the matrix formed by the first columns of the scalar matrix <\eqnarray*> \|\ z>>|| \|\ z>>|>| \|\ z>>>|>||>>| \|\ z>>|>| \|\ z>>>>>>>>>> is invertible. Then the implicit function theorem implies that there exist unique power series ,\,\\K,\,z|]>|]>>, such that the completed vector =,\,\|)>> with =z,\,\=z> satisfies \\=0>. We say that a power series domain K,z,\|]>|]>>> if ,\,\\A> for the above solution of \\=0>, whenever ,\,\\A>. We say that if we also have an algorithm to compute ,\,\> as a function of ,\,\>. Consider an invertible n> matrix \n>> with rational coefficients. Then the transformation <\eqnarray*> \z:z>*\*z>>|>|>*\*z>>>|>|>|i>>>>> is called a monomial transformation, where we consider \> as a column vector. For apower series K,\,z|]>|]>> whose support \:f\0|}>> satisfies supp f\\>, we may apply the monomial transformation to as well: <\eqnarray*> z>||\>f*zi>.>>>> A power series domain K,\,z|]>|]>> is said to be if for any A> and invertible matrix \n>> with supp f\\>, we have z\A>. We say that is if we also have an algorithm to compute z> as a function of and . Notice that we do require the existence of a test whether supp f\\> in this case (the behaviour of the algorithm being unspecified whenever supp f\\>). Given an effective power series domain that effectively satisfies each of the above closure properties (composition, implicit functions, and monomial transformations), it can be shown that an effective version of the Weierstrass preparation theorem holds. We refer to for details. Let K|]>=K,\,z|]>|]>> be a multivariate power series domain. Given a power series K|]>=K,\,z|]>|]>> and ,n|}>>, we may consider as a power series <\eqnarray*> |||]> f+|]> f|)>*z+|]> f|)>*z+\>>>> in > with coefficients in |]>|)>>, and also as a power series in > with coefficients in the fraction field of |]>|)>>. If is D-algebraic over for this latter interpretation of , then we say that is D-algebraic in > (or with respect to>). We say that is D-algebraic over if is D-algebraic in each of the variables ,\,z>>. <\proposition> Given K|]>> is D-algebraic over and ,n|}>>, each coefficient |]> f> of the power series expansion of in > is D-algebraic over >. <\proof> Given i>, let =0> be a non-trivial differential equation satisfied by in>. Let |)>> denote the valuation of > in >. Modulo division of > by |)>>>, we may assume without loss of generality that |)>=0>. Now > satisfies the non-trivial equation |)>|)>=0>. This shows that |]> f> is D-algebraic over >. For 0>, we will prove by induction that |]> f> is D-algebraic over >. So assume that |]> f,\,|]> f> are D-algebraic over >, whence over . Given i>, the series <\equation*> g=|]> f-\-|]> f|)>*z|z> is D-algebraic in > over , by Proposition. By what precedes, it follows that |]> f=\> is D-algebraic in >. <\proposition> The set > of D-algebraic power series over forms a multivariate power series domain. <\proof> The stability of > under the differential ring operations and division (when defined) directly follows from Proposition. The stability under the projections > follows from Proposition. From now on, > denotes the set of differential polynomials with respect to the pairwise commuting derivations ,\,\>. Proposition also admits a natural generalization: <\proposition> The series K|]>> is D-algebraic if and only if > admits finite transcendence degree over . <\proof> Assuming that K|]>> is D-algebraic over , let \A F,\ F,\|]>\A> be of minimal Ritt rank F,d|)>> with =0>, for each . Let =>*\*\> f:i\r,\,i\r|}>>. Then >\0> for each and ,S>,\,S>|]>> is stable under the derivations ,\,\>. Consequently, \B> and A\r*\*r+n>. Conversely, assume that A=r>. Then ,\ f> satisfy a non-trivial algebraic relation for each , whence is D-algebraic. Assume now that is an effective multivariate power series domain. We may effectively represent a D-algebraic series \A> over by a tuple ,\,P|)>> where is acomputable power series in |]>> and > an annihilator for with respect to >, for each . <\proposition> Assume that K|]>=K,\,z|]>|]>> is an effective multivariate power series domain over an effective diophantine field with an effective zero test. Then > is an effective multivariate power series domain with an effective zero test. Moreover, for any ,n|}>>, there exists an algorithm for computing the coefficients |]> f> of the power series expansion of a given A> with respect to >. <\proof> We prove the proposition by induction over . For , the result is trivial, so assume that 0> and that we proved the result for all smaller . Given ,n|}>>, let us first show how to compute the coefficients |]> f> of the power series expansion of a given A> with respect to >. The induction hypothesis provides us with a zero test in |)>=\>. In the proof of Proposition, we thus have an algorithm for the computation of the valuation |)>>, and the remainder of this proof isconstructive. Let denote the quotient field of |)>=\>. We claim that is an effective diophantine field. Indeed, given a polynomial L|]>>, an integer \\> is a root of if and only if > is a root of multiplied by the denominators of its coefficients. Without loss of generality, we may therefore assume that \|)>|]>>. After this reduction, \\> is a root of if and only if > is a root of the coefficient >*\*z>|]> P\K|]>> of >*\*z>> in for all ,\,i\\>. Let ,\,i\\> be such that this coefficient is non-zero and let > be its largest root in > (or if no such root exists). We may now check whether =0> for ,\> and compute the largest root of in >. Any series in > may be regarded as a univariate series in > with coefficients in. By what precedes, is an effective diophantine field and we have an algorithm for the computation of the coefficients of . The zero tests from section can therefore be used as zero tests for . Let K|]>=K,\,z|]>|]>> be a multivariate power series domain. An abstract multivariate D-domain over is a differential -algebra for ,\,\> together with adifferential -algebra morphism :B\K|]>>. A over is an abstract multivariate D-domain over of theform <\eqnarray*> ||,\,F|}>/I>>|||,\,P,\,P,\,P|]>:>*\*H>*\*H>*\*H>|)>>,>>>> where ,\,P,\,P,\,P\A,\,F|}>> are such that <\eqnarray*> >*\*H>*\*H>*\*H>+I|)>>|>|>>> and where each > only involves derivations of the form > and admits a leader of the form > F> for certain \\>. We will denote by > those elements of the fraction field of such that \\/\\K|]>>. We will also write =\> for A,\,F|}>>. We say that is if is an effective power series domain and > is computable for each B>. We say that is if \A,\ F,\ F,\|]>> for all and . We say that is if > is of the form =S*\ F-R> with ,R\A,\,F|]>> for all . The proof of the following proposition is analogous to the proof of Proposition: <\proposition> <\enumerate-alpha> Given any multivariate D-domain over and any B>, the series > is Dalgebraic over . If is effective, then we may effectively compute \A>. Any multivariate D-algebraic series over is the element of a multivariate Ddomain over . If is effective and A>, then we may effectively compute . <\corollary> Let be an effective multivariate D-domain over K,\,z|]>|]>>. Then there exists an algorithm for testing whether =0>, for given B>. <\proof> This follows from Proposition and the existence of a zero test in > (Proposition). The proofs of the following propositions are analogous to the proofs of Propositions and: <\proposition> Any multivariate D-domain is equivalent to an unmixed D-domain. If is effective, then this reduction is effective. <\proposition> Any multivariate D-domain is equivalent to a Pfaffian D-domain. If is effective, then this reduction is effective. Consider A,\,F|}>> with =\ F> and =\ F>. Let \> be such that =max,q|)>> for all ,n|}>> and assume that >. Then we recall from differential algebra> that the >-polynomial > of and is defined by <\eqnarray*> >||*\ P-S*\ Q.>>>> Given a D-domain as above, we say that is if ,P,j>>\I> for all ,j>. Given an arbitrary effective D-domain , we may compute an equivalent effective coherent D-domain using the algorithm below, where we make use of the effective zero test from Corollary: <\named-specified-algorithm|MakeCoherent>> : An effective multivariate D-domain A coherent effective multivariate D-domain that is equivalent to <|named-specified-algorithm> <\listing> Let \:|1\i\n,j\1\k|\>|}>> Repeat the following Let >\\:\\0,\|)>\0|}>> If there exists \> with >\=0>, then set \\\> Else if > \> with P rem \>\\P> and \>, then set \\> Else if > \> with \ rem \>\0> and \>, then set \\\> Else if > \> with |)>=0> and \\>, then set \\\|}>> Else if > \> with |)>=0> and \\>, then set \\\|}>> Else return ,\,F|}>/|]>:H>>|)>> with the evaluation induced by > <\proof> The main loop invariant states that > only contains annihilators for the point =|)>,\,\|)>|)>>, and each of the original differential polynomials > Ritt reduces to zero with respect to >>. The termination follows from the fact that we only add new elements of smaller and smaller Ritt ranks to >. At the end, the set > is necessarily coherent and autoreduced, and such that >|)>\0>. Since each original polynomial > reduces to zero modulo >=\>, there must exist a corresponding polynomial \\> with leader > F> and \r>. This shows that ,\,F|}>/|]>:H>>|)>> is indeed a D-domain. By Proposition, there exists an algorithm for extracting the coefficients of multivariate Dalgebraic power series with respect to a single variable >. In the case of power series that are represented by elements of a D-domain, it would be nice to have a more efficient and systematic algorithm. In particular, given ,n|}>> and \>, we would like to effectively construct aD-domain l>> such that for any B> and any l>, we can produce a |]> P\Bl>> with |]> \=\>. For this, it suffices that l>> contains all coefficients of the form |]> F> with ,k|}>> and l>. Theoretically speaking, we may construct l>> using Proposition. As a first optimization, we claim that there exists a computable finite set \\> such that we can take l>=Bl>\Bl-1>> whenever \>. Indeed, for any \>, we may regard as apower series in> with coefficients in the quotient field of |]>|)>>. For sufficiently large , the coefficients of this power series are determined by a recurrence relation of type(). As a second optimization, assume that is Pfaffian and >>, meaning that the valuations >|)>|)>> of the >|)>> in > all vanish. We will take <\equation*> Bl>=Bl>|]> F,\,|]> F|}>/I, with |]> F|)>=|]> \|)>> for all , and where the differential ideal > is constructed as follows. Given \i> and ,k|}>>, let <\equation*> \,j,l>=|]> F>:m\l,1\j\k|}>\>|]> F|)>:m\l|}>. Since ,j>|)>|)>=0>, extracting the coefficient of > in the equation <\eqnarray*> ,j>|)>*\> F|)>>||,j>|)>>>>> yields a relation <\eqnarray*> |]> \,j>|)>|)>*|]> \> F|)>|)>>||,j,l>,>>>> for some ,j,l>\A,j,l>|]>>. Now let > be the set of all differential polynomials of the form ,j,l>=|]> S,j>|)>*\>|]> F|)>-R,j,l>>. Then we may take =A|}>/|]>:H>>|)>>. Notice that l>> is again Pfaffian if l>> is Pfaffian. However, regularity in the other variables >> is not necessarily preserved. Nevertheless, if >|)>\0> for all , then the recursive extraction of coefficients only yields regular Pfaffian D-domains. <\remark> Given a regular D-domain in >, it can be shown that the reduction to an equivalent Pfaffian D-domain used in the proof of Proposition actually yields a regular Pfaffian D-domain in >. From what precedes, it follows in particular that there exists a constant \> such that we may take l>=BL>> for all L>. Hence for any B> and any \>, we have |]> P\BL>>. We may then reinterpret the D-domain as a univariate D-domain by only retaining the relations ,\,P> and using coefficients of the form \\|)>> withBL>>. This allows us to replace the theoretical zero test from Corollary by one of the more efficient zero tests from section. Let |\,\,\|\>\K|]>=K,\,z|]>|]>> with n> and denote <\eqnarray*> = \|\ z>>|| \|\ z>>|>| \|\ z>>>|>||>>| \|\ z>>|>| \|\ z>>>>>>.>>>> Let > be the submatrix spanned by the first columns of > and > the submatrix spanned by the last columns. Assume that \Km>> is invertible. Then the implicit function theorem implies that there exist unique power series ,\,\\K,\,u|]>|]>>, such that the completed vector =,\,\|)>> with =u,\,\=u> satisfies <\equation> \\\=0. Forming the Jacobian matrix =\ \/\ u> of >, we let > and > denote the submatrices spanned by the first last rows. Differentiating the relation(), we obtain <\eqnarray*> \\|)>*\+\\|)>*\>||>>> Since =Id>, this yields <\eqnarray*> >||*\|)>\\.>>>> Given any K|]>>, consider the row matrices = f/\ z,\,\ f/\ z|)>> and = f/\ z,\,\ f/\ z|)>>. Then <\eqnarray*> f\\|\ u>>||\\|)>*\+\\|)>>>|||-F*\*\|)>\\.>>>> Let =,\,\|)>>, =,\,\|)>> and =*\/\ u,\,u*\/\ u|)>>. Let > and > diagonal matrices with entries ,\,z> ,\,z>. Denoting by |~>=|~>,\,|~>|)>> the row vector of derivations with <\eqnarray*> |~> f>|| f-\ f*Z*\*\*Z,>>>> the above relation implies <\eqnarray*> \|)>>|||~> f|)>\\.>>>> Notice that *\*z*det \*|~>> maps power series to row vectors of power series. Assume now that ,\,\\B> for some effective multivariate D-domain of dimension over with <\eqnarray*> ||,\,F|}>/I>>|||:i,j|]>:H>>|)>>.>>>> Assume also that the coordinate functions ,\,z> are among the >. We will make the additional assumption that \\\0> for all ,m|}>>. In particular, setting *\*z*det \>, we have \\0>. We introduce a new evaluation mapping |~>> on by taking <\eqnarray*> |~>|)>>|||)>\\.>>>> We may formally extend |~>> into an evaluation from |]>> into |]>\|)>|]>>. This evaluation is not compatible with the original derivations ,\,\>, but we do have <\eqnarray*> * |~>|\ u>>|||~>|~> P|)>>>>> for all B|]>>, and for each of the derivations |~>>. Since |]>> is finite dimensional as a -algebra, Proposition implies that ,|~> F,|~>|)> F,\> satisfy acomputable non-trivial -algebraic relation > for each and. Using Proposition, we may assume without loss of generality that these relations are non-degenerate. We now define a new multivariate Ddomain > for the derivations |~>,\,|~>>, by taking <\eqnarray*> >||,\,F|}>/>>|>||:i,j|]>:H>>|)>>,>>>> and taking the evaluation mapping|~>> as in(). By construction, |~>|)>=\> for each ,m|}>>, so > is D-algebraic. The additional assumption that =z\\\0> for all ,m|}>> is quite benign. Indeed, for any index with =0>, postcomposition of K|]>> with > means in particular sending > to . This can also be achieved by extracting the coefficient of > in. Consequently, modulo a finite number of extraction of coefficients, we may assume without loss of generality that \0> for all ,m|}>>. We have proved: <\proposition> The set of D-algebraic power series over an effective diophantine field is effectively satisfies the implicit function theorem. <\proposition> The set of D-algebraic power series over an effective diophantine field is effectively stable under composition. <\proof> Given K,\,z|]>|]>> and ,\,g\K,\,u|]>|]>> with =\=g=0>, consider the power series =z-g\K,\,z,u,\,u|]>|]>>. The above algorithm allows us to compute ,\,\\K,\,u|]>|]>> with =u> and \\=0>, as well as the result of the composition \> (when considering as an element of ,\,z,u,\,u|]>|]>>>), which coincides with g>. The construction of > is somewhat unsatisfactory since the computation of individual algebraic relations > using Proposition is usually quite expensive. In the frequent situation that >\\\0> for all , we may use the following more efficient technique. Using Proposition, we may assume without loss of generality that the original relations > are of the form =S*\ F-R> with ,R\K,\,F|]>>. By assumption, we have |)>\\\0> for all . With the above notations, let> denote the horizontal concatenation of the matrices > and *\*\*Z>, so that |~> f= f|)>*\> for all and > has coefficients in . Modulo the relations >, we may then write <\equation*> |~> F=>> F|)>*\,i>=>\,i>*|S>. For each and , this means that there exists a power product > of the ,j>> and apolynomial \K,\,F|]>> with <\eqnarray*> *|~> F>||.>>>> This allows us to take =U**|~> F-> in the construction of the multivariate Ddomain > instead of the relation found using Proposition. <\proposition> Let K,\,z|]>|]>> be an effective power series domain over an effective diophantine field . Then > is effectively stable under monomial transformations. <\proof> Let be an effective D-domain over , let B> and >. Given an invertible matrix \n>> with supp f\\>, we have to show how to compute z>. Given a row vector \\>, we will denote \\=\*\+\+\*\>. Then for any power series \K|]>> and any \\>, we notice that <\eqnarray*> \\|)>\z|)>>||*M|)>\\|)>|)>\z.>>>> Since B\s\r*\*r+n>, the elements *M|)>\\|)>,\,*M|)>\\|)>> satisfy an -algebraic dependency which can be computed using Proposition. Applying this result for all > of the form =e=|\>,0,1,0,\,0|)>>, we obtain D-algebraic relations over for \z> in the individual derivations >. The above proposition could in principle be used for computing with monomial transforms of elements in an effective D-domain . However, in a similar way as it is more efficient to keep fractions in their symbolic forms when computing with fractions in >, it is often more efficient to keep monomial transforms in their symbolic form z> when computing with them. More precisely, we first notice that monomial transformations f\z> with \> are somewhat easier, since they can be computed using our algorithms for composition. Now two monomial transformations f\z>> and f\z>> are said to be if there exist invertible matrices ,N\\n>> with *N=M*N>. Given ,f\\> with \supp f\\> and \supp f\\>, let =f\z>>, =f\z>> and *N>. Since > and > have coefficients in >, we may construct a D-domain > with ,g\\|)>>. Now \z>=g\z> and \z>=g\z>. In particular, any \K,f|}>> can be represented by =\\z> for some \\|)>>. From the geometrical point of view, the notion of compatibility can be interpreted as follows. Let > be an open subset of \>|)>\:|\|>=1|}>> and =\>*\>. Let ,\,z|]>|]>>> be the subset of ,\,z|]>|]>> of series with \>. Given a monomial transformation f\z>, we call \M*>|)>|)>\>|)>> its associated cone. Given two monomial transformations f\z>> and f\z>> with associated cones > and>, it is not hard to check that these transformations are compatible if and only if \\\>. It should be emphasized that zero testing of power series is a quite asymmetric problem in the sense that it is usually easy to prove that a non-zero series is indeed non-zero (it suffices to find a non-zero coefficient), whereas it is often hard to prove vanishing series to be zero. Since exact zero tests are so slow, it is often preferable to use heuristic zero tests instead. In fact, heuristic zero tests can be combined with genuine zero tests: for a complex computation that involves many zero tests, we first perform all zero tests heuristically. At the end of the computation, we collect all series that were heuristically assumed to be zero in order to compute the result, and we apply an exact zero test to these series. The most obvious heuristic zero test for a univariate D-algebraic series is to compute all coefficients up to a fixed order. Even for large orders, these coefficients can be computed efficiently using Newton's method or relaxed power series evaluation. In the case of multivariate D-algebraic series K,\,z|]>|]>>, one simple idea is to generate arandom scalar vector =,\,\|)>\K> and to test whether the univariate power series *z|)>> vanishes. The composition *z|)>> can be computed efficiently using the algorithm(s) from section. Here we notice the remarkable fact that the derivation <\eqnarray*> |^>>||+\+\>>>> for which <\eqnarray*> *z|)>|)>>|||^> f|)>\*z|)>>>>> does not depend on >. This makes it actually possible to design another exact zero test for multivariate D-algebraic series: compute a univariate D-domain capable of representing *z|)>> where > is treated as a formal parameter, and test whether *z|)>=0>. <\bibliography|bib|plain|all.bib> <\bib-list|10> A.Bostan, F.Chyzak, F.Ollivier, B.Salvy, É. Schost, and A.Sedoglavic. Fast computation of power series solutions of systems of differential equations. In , pages 1012\U1021, New Orleans, Louisiana, U.S.A., January 2007. R.P. Brent and H.T. Kung. Fast algorithms for manipulating formal power series. , 25:581\U595, 1978. J.Della Dora, C.Dicrescenzo, and D.Duval. A new method for computing in algebraic number fields. In G.Goos and J.Hartmanis, editors, , volume 174 of , pages 321\U326. Springer, 1985. J.Denef and L.Lipshitz. Power series solutions of algebraic differential equations. , 267:213\U238, 1984. J.Denef and L.Lipshitz. Decision problems for differential equations. , 54(3):941\U950, 1989. M.J. Fischer and L.J. Stockmeyer. Fast on-line integer multiplication. , 9:67\U72, 1974. J.vander Hoeven. A new zero-test for formal power series. In Teo Mora, editor, , pages 117\U122, Lille, France, July 2002. J.vander Hoeven. Relax, but don't be too lazy. , 34:479\U542, 2002. J.vander Hoeven. Newton's method and FFT trading. , 45(8):857\U878, 2010. J.vander Hoeven. Faster relaxed multiplication. Technical report, HAL, 2012. . J.vander Hoeven. Effective power series computations. Technical report, HAL, 2014. . J.vander Hoeven and J.R. Shackell. Complexity bounds for zero-test algorithms. , 41:1004\U1020, 2006. A.G. Khovanskii. , volume88 of . A.M.S., Providence RI, 1991. E.R. Kolchin. . Academic Press, New York, 1973. A.Péladan-Germa. . PhD thesis, Gage, École Polytechnique, Palaiseau, France, 1997. R.H. Risch. Algebraic properties of elementary functions in analysis. , 4(101):743\U759, 1975. J.F. Ritt. . Amer. Math. Soc., New York, 1950. J.Shackell. A differential-equations approach to functional equivalence. In , pages 7\U10, Portland, Oregon, A.C.M., New York, 1989. ACM Press. J.Shackell. Zero equivalence in function fields defined by differential equations. , 336(1):151\U172, 1993. <\initial> <\collection> <\references> <\collection> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > <\auxiliary> <\collection> <\associate|bib> BK78 BCOSSS07 vdH:fnewton vdH:relax FS74 vdH:fastrelax Ritt50 Kol73 DL84 DL89 DL84 DL89 vdH:issac02 Ris75 DL84 DL89 Khov91 Sh89 Sh93 Pel:phd vdH:zerotest vdH:issac02 DL84 DL89 DL84 DL89 Pel:phd vdH:issac02 Ritt50 Kol73 DDD85 vdH:powser Ritt50 Kol73 BK78 vdH:relax BCOSSS07 vdH:fnewton FS74 vdH:fastrelax <\associate|toc> |math-font-series||1Introduction> |.>>>>|> |General introduction |.>>>>|> > |Structure of the paper and main results |.>>>>|> > |Comparison with previous work |.>>>>|> > |math-font-series||2Reminders from differential algebra> |.>>>>|> |2.1Ritt reduction |.>>>>|> > |2.2Decompositions of differential polynomials |.>>>>|> > |2.3Additive conjugation |.>>>>|> > |2.4Differential polynomials with power series coefficients |.>>>>|> > |2.5Logarithmic power series |.>>>>|> > |math-font-series||3D-algebraic power series> |.>>>>|> |3.1Univariate D-algebraic power series |.>>>>|> > |3.2Root separation bounds |.>>>>|> > |3.3A first effective zero test |.>>>>|> > |3.4An improved zero test |.>>>>|> > |3.5Effective root separation bounds |.>>>>|> > |3.6Non degenerate annihilators |.>>>>|> > |math-font-series||4D-domains> |.>>>>|> |4.1Definition of a D-domain |.>>>>|> > |4.2Dominant Hermite normal forms |.>>>>|> > |4.3Root separation bounds for D-domains |.>>>>|> > |4.4An effective zero test for D-domains |.>>>>|> > |4.5An improved zero test for D-domains |.>>>>|> > |math-font-series||5Multivariate D-algebraic series> |.>>>>|> |5.1Multivariate power series domains and closure properties |.>>>>|> > |5.2Multivariate D-algebraic power series |.>>>>|> > |5.3Multivariate D-domains |.>>>>|> > |5.4Extraction of coefficients and application to zero testing |.>>>>|> > |5.5An effective implicit function theorem |.>>>>|> > |5.6Effective monomial transformations |.>>>>|> > |5.7Heuristic zero testing |.>>>>|> > |math-font-series||Bibliography> |.>>>>|>