> <\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. > be an effective field of characteristic zero. An effective tribe is a subset of ,z,\|]>|]>=K\K|]>|]>\K,z|]>|]>\\> that is effectively stable under the algebra operations, restricted division, composition, the implicit function theorem, as well as restricted monomial transformations with arbitrary rational exponents. Given an effective tribe with an effective zero test, we will prove that an effective version of the Weierstrass division theorem holds inside the tribe, and that this can be used for the computation of standard bases.>|algebraic power series|tribe>|> There are two main aspects about effective 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 undecidable in general, since we need to check the cancellation of an infinite number of coefficients. Therefore, arelated subject is the isolation of sufficiently large classes of power series such that most of the common operations on power series can be carried out inside the class, but such that the class remains sufficiently restricted such that we can design effective zero tests. The abstract description of a suitable framework for power series computations is the subject of section. We first recall the most common operations on formal power series over afield of characteristic zero: the -algebra operations, restricted division, composition, the resolution of implicit equations, and so called restricted monomial transformations with arbitrary rational exponents. A subset of ,z,\|]>|]>=K\K|]>|]>\K,z|]>|]>\\> that is stable under each of these operations will be called a tribe. We will also specify effective counterparts of these notions. The main results of this paper are as follows. Given an effective tribe with an effective zero test, we show in section that the tribe also satisfies an effective version of the Weierstrass preparation theorem, and we give an algorithm for performing Weierstrass division with remainder. In section, we also introduce \PWeierstrass bases\Q and a recursive version of Weierstrass division that works for ideals. For Archimedean monomial orderings, this can in turn be used for the computation of standard bases of ideals generated by series in the tribe in the sense of Hironaka. Our results can for instance be applied to the tribe of algebraic power series. In that particular case, various alternative algorithms have been developed. An algorithm for Weierstrass division was given in. This algorithm has recently been extended to the computation of reduced standard bases of ideals that satisfy a suitable condition (namely Hironaka's box condition). In the case that the ideals are generated by polynomials instead of power series, one may compute (non-reduced) standard bases using Mora's tangent cone algorithm or Lazard's homogenization technique. The main other example that motivated our work is the tribe of dalgebraic power series(see also). The fact that the collection of all d-algebraic power series satisfies the Weierstrass preparation theorem was first proved in a more way by van den Dries. The notion of a tribe also shares some common properties with the notion of aWeierstrass system, as introduced by Denef and Lipshitz and used in. Our approach can be regarded as a simpler, effective and more systematic way to prove that certain types of power series form Weierstrass systems. Moreover, we show how to compute more general standard bases in this context. The idea behind our main algorithm for the computation of Weierstrass polynomials is very simple: given a series L\K,\,z|]>|]>> of Weierstrass degree in >, we just compute the solutions ,\,\> of the equation ,\,z|)>=0> in> inside asufficiently large field of grid-based power series. This allows us to compute the polynomial -\|)>*\*-\|)>> which we to be the Weierstrass polynomial associated to . Using the stability of the tribe under restricted monomial transformations, we will be able to compute as an element of . The algorithms rely on our ability to compute with the auxiliary grid-based power series ,\,\>. For this reason, we briefly recall some basic facts about grid-based power series in section, as well as the basic techniques that are needed in order to compute with them. Weierstrass division is a precursor of the more general notion of Hironaka division in the particular case of a principal ideal in general position. For arbitrary ideals in general position (or, more precisely, in \PWeierstrass position\Q), we introduce a recursive version of Weierstrass division in section. Assuming that such an ideal is finitely generated by elements in the tribe , this allows us to compute a \PWeierstrass basis\Q for and to decide ideal membership for other elements of . Another application is the computation of the Hilbert function of . The main ingredients in section are the possibility to put ideals in Weierstrass position modulo a suitable linear change of variables and ordinary Weierstrass division in the principal ideal case. For tribes in which we have alternative algorithms for the Weierstrass preparation theorem, the techniques of section can use these algorithms instead of the ones from section. In the last section, we show how to compute more traditional standard bases of ideals that are finitely generated by elements of . The main difficulty with standard bases in the power series setting (in contrast to Gröbner bases in the polynomial setting) is termination. This difficulty is overcome by using the fact that we may compute the Hilbert function of the ideal using the techniques from section. During the construction of a standard basis, this essentially allows us to decide whether the S-series of two basis elements reduces to zero or whether it reduces to a series of high valuation. In general, our algorithm does not compute a reduced standard basis: it is actually known that such a reduced standard basis does not necessarily exist. An interesting open question is under which conditions our algorithm still does compute one. In the algebraic setting, we already mentioned above that furnishes aconditional algorithm for the computation of reduced standard bases. Our paper uses several notations from the theory of grid-based power series that are uncommon in the area of standard bases. For instance, admissible orderings are replaced by monomial orderings, initial monomials by dominant monomials, and Weierstrass position is reminiscent of Hironaka's box condition that is essential in. The general motivation behind our notations is their natural asymptotic meaning. They have been very useful for the development of asymptotic differential algebra and we refer the reader to for amore extensive background and dictionary. <\acknowledgments*> The author wishes to express his gratitude to the two referees for their careful reading and helpful comments, as well as to Alin Bostan and Lou van den Dries for historical references. Let be a field of characteristic zero and denote <\eqnarray*> ,z,\|]>|]>>||K|]>|]>\K,z|]>|]>\\,>>>> where we understand that ,\,z|]>|]>> is naturally included in ,\,z|]>|]>> for each. So each element K,z,\|]>|]>> is a power series in a finite number of variables. We say that is if its elements can be represented by concrete data structures and if all field operations can be carried out by algorithms. We say that if we also have an algorithm that takes K> as input and that returns if and otherwise. If is effective, then a power series K,z,\|]>|]>> is said to be if we have an effective bound for its dimension (so that K,\,z|]>|]>>), together with an algorithm that takes \> as input and produces the coefficient \K> of =z>*\*z>> on output. We will denote the set of computable power series by ,z,\|]>|]>>. Let be a subset of ,z,\|]>|]>>. We will denote =L\K,\,z|]>|]>> for each and say that is if K,z,\|]>|]>>. In this section, we will give definitions of several operations on power series and the corresponding closure properties that may satisfy. We say that is a if is a -algebra. From now on, we will always assume that this is the case. It is also useful to assume that is in the sense that \L> for all . For each , we will denote =\/\ z> and =z*\>. We say that is if L\L> for all(whence L\L>). The above closure properties admit natural effective analogues. We say that is an if is an effective field, if the elements of can be represented by concrete data structures and the -algebra operations can be carried out by algorithms. We say that is if there is an algorithm that takes \> as input and that computes \L>. We say that is if there exists an algorithm that takes L> and \> as input and that computes f\L>. For any ring , let >=R\>. We say that is if L> whenever L> and L>> are such that K,z,\|]>|]>>. If is effective, then we say that is if we also have an algorithm that computes as afunction of L>, whenever K,z,\|]>|]>>. Here we do assume the existence of a test whether K,z,\|]>|]>> (the behaviour of the algorithm being unspecified if K,z,\|]>|]>>). More generally, given L>>, we say that is > if L> whenever K,z,\|]>|]>>, and that is > if this division can be carried out by analgorithm. Given K|]>=K,\,z|]>|]>>, 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|)>\L> for any L> and ,\,g\L> with =\=g=0>. If we also have an algorithm for the computation of ,\,g|)>>, then we say that is . We notice that stability under composition implies stability under permutations of the>. In particular, it suffices that \L> for to be inhabited. Stability under composition also implies stability under the projections > with <\equation*> f|)>,\,z|)>=f,\,z,0,z,\,z|)>. If is also stable under restricted division by > (whence under restricted division by any>), then this means that we may compute the coefficients |]> f> of the power series expansion of with respect to > by induction over : <\equation*> |]> f=\ |]> f-\-|]> f|)>*z|z>. Similarly, we obtain stability under the differentiation: for any L> and n>, we have <\eqnarray*> f|)>,\,z|)>>|| ,\,z,z+z,z,\,z|)>-f,\,z|)>|z>.>>>> 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,\|]>|]>>> (for implicit functions) if ,\,\>\L> for the above solution of \\=0>, whenever ,\,\\L>. We say that if we also have an algorithm to compute ,\,\> as a function of ,\,\>. We claim that satisfies the implicit function theorem for implicit functions as soon as satisfies the implicit function theorem for one implicit function and is stable under restricted division and composition. We prove this by induction over . For the statement is clear, so assume that 1>. Since the matrix formed by the first columns of \/\ z|)>> is invertible, at least one of the \/\ z|)>> must be non-zero. Modulo a permutation of rows we may assume that \/\ z|)>\0>. Applying the implicit function theorem to > only, we obtain a function \L> with \,z,\,z|)>=0>. Differentiating this relation, we also obtain <\eqnarray*> \|\ z>>|| \/\ z|\ \/\ z>\,z,\,z|)>,>>>> for each . Setting \1/ \/\ z|)>>, this yields in particular <\eqnarray*> \|\ z>>||* \|\ z>.>>>> Now consider the series =\\,z,\,z|)>\L>. For each m-1>, we have <\eqnarray*> \|\ z>>|| \|\ z>* \|\ z>+ \|\ z>>>||| \|\ z>-\* \|\ z>* \|\ z>.>>>> In particular, <\eqnarray*> \|\ z>>|>| \|\ z>>>|>||>>| \|\ z>>|>| \|\ z>>>>>>>||* \|\ z>>|>| \|\ z>>>|>||>>| \|\ z>>|>| \|\ z>>>>>>\0.>>>> By the induction hypothesis, we may thus compute series ,\,\\L> such that \,\,\,z,\,z|)>=0> for all . Setting =\\,\,\,z,\,z|)>\L>, we conclude that \,\,\,z,\,z|)>=\\,z,\,z|)>\,\,\,z,\,z|)>=0> and <\eqnarray*> \,\,\,z,\,z|)>>||\,z,\,z|)>\,\,\,z,\,z|)>>>|||\,\,\,z,\,z|)>>>|||>>> for all m-1>. Consider an invertible n> matrix \n>> with rational coefficients. Then the transformation <\eqnarray*> \z:z>*\*z>>|>|>*\*z>>>|>|>|i>>>>> is called a monomial transformation, where \> is considered 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>.>>>> We say that is if for any L> and invertible matrix \n>> with supp f\\>, we have z\L>. 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 atest whether supp f\\> in this case (the behaviour of the algorithm being unspecified whenever supp f\\>). If \n>> has non-negative integer coefficients, then we always have supp f\\> and is trivially stable under the monomial transformation f\z> whenever is stable under composition. We say that the -algebra with \L> is a if is stable under composition, the resolution of implicit equations, and restricted division by >. We say that is a if is also stable under restricted division and restricted monomial transformations. Effective local communities and tribes are defined similarly. A power series K,z,\|]>|]>> is said to be if it satisfies a non-trivial algebraic equation over the polynomial ring ,z,\|]>=K\K|]>\K,z|]>\\>. Setting ,z,\|)>=K\K|)>\K,z|)>\\>, this is the case if and only if the module > is an -vector space of finite dimension. Using this criterion, one can prove that the set ,z,\|]>|]>> of algebraic power series is a tribe (and actually the smallest tribe for inclusion). For convenience of the reader, let us state and prove an effective version of this result. Assume that is an effective field. Then an effective algebraic power series K,z,\|]>|]>> can be effectively represented as an effective power series together with an annihilator H>. We claim that ,z,\|]>|]>> is an effective tribe for this representation. <\proposition> The -algebra ,z,\|]>|]>> forms an effective tribe. <\proof> Let K,z,\|]>|]>>, so that =Q=0> for certain monic polynomials K,\,z|)>> of degrees and in . For ,d*e>, these relations allow us to rewrite both > and > as ,\,z|)>>-linear combinations of *g> with k\d> and l\e>. Since these *g> span a vector space of dimension at most , this means that there exist monic polynomials K,\,z|)>> of degree d*e> with =S=0>, and we may compute and using linear algebra. This shows that ,z,\|]>|]>> forms an effective power series algebra that is clearly inhabited. With the above notations, let =Q+Q*u+\+Q*u+Q*u> and assume that 0>. Then we notice that =0\=0>, so we can compute a polynomial K,\,z|)>> with =0> in a similar way as above. This shows that ,z,\|]>|]>> is effectively stable under restricted division by . Assume now that ,\,g\K,z,\|]>|]>> with =\=g=0> and let \K,\,z|)>> be a monic annihilator of > of degree > for ,n>. Assume first that the annihilator of belongs to ,\,z,u|]>>. Given any \>, we may then rewrite g|)>> as a linear combination of \g|)>*g>*\*g>> with d>, \e,\,k\e>. In a similar way as above, this allows us to compute a non trivial annihilator of degree d*e*\*e> of g>. In general, the annihilator of belongs to *K,\,z,u|]>> for some denominator K,\,z|]>>. In that case, the annihilator of belongs to ,\,z,u|]>>, whence \g> is algebraic, and so is g=g|)>*\g>. In other words, ,z,\|]>|]>> is effectively stable under composition. A similar argument shows the effective stability under restricted monomial transformations. Let us finally assume that =0>, but f/\ z|)>\0>, and let \K,\,z|]>|]>> and =z,\,\=z> be such that \=0>. Let ,\,z,u|)>> still be the annihilator of. Then \\=P,z,\,z,f\\|)>=P,z,\,z,0|)>=0> yields a non trivial annihilator for >. This shows that ,z,\|]>|]>> is effectively stable under the implicit function theorem. In order to conclude, we still need to prove the existence of an effective zero test for (given by its annihilator and an algorithm to compute its coefficients). Now the polynomial equation =0> admits at most solutions. Using the Newton polygon method for a suitable valuation, it is possible to derive a bound for the maximal valuation of in the case when 0>. It then suffices to compute the coefficients of up to this valuation bound. For more details, we refer to, where we proved a stronger result in a more generalsetting. A power series K,\,z|]>|]>> is said to be if it satisfies an algebraic differential equation ,\> f|)>=0> for each ,n|}>>, where > is a non-zero polynomial in +1> variables with coefficients in . This is the case if and only if the differential field |f|\>> generated by over ,z,\|)>> admits afinite transcendence degree. We denote by ,z,\|]>|]>> the set of d-algebraic power series. Using the finite transcendence degree criterion, and similar techniques as in the proof of Proposition, it can be shown that ,z,\|]>|]>> forms atribe. If is an effective field, then effective d-algebraic power series may again be represented through an effective power series and differential annihilators > of the above form. In, one may find more information on how to compute with dalgebraic power series, and afull proof of the fact that ,z,\|]>|]>> is actually an effective tribe (the proof being based on earlier techniques from). Notice that the most intricate part of this kind of computations is zero testing. In what follows, we will only consider commutative monoids. A is amultiplicative monoid > with a partial ordering> that is compatible with the multiplication ( \\\\\\\\*\\\*\> and *\\\*\\\\\>). The notation> generalizes Hardy's notation from asymptotic analysis, so we call > an . We denote by >=\\\\\1|}>> the set of elements in > and by >=\\\\\1|}>> the set of elements in >. We say that > has >-powers if we also have a powering operation |)>\\\\\\\\> such that *\|)>=\*\> and |)>=\> for all \> and ,\\\>. A monomial monoid > is said to be if its elements can be represented by effective data structures and if we have algorithms for the multiplication and the asymptotic ordering >. Since =\\\\\\\\\> this implies the existence of an effective equality test. A monomial group > is said to be if it is an effective monomial monoid with an algorithm for the group inverse. We say that > is an >powers> if we also have a computable powering operation. A subset \\> is said to be if there exist finite sets ,\,\|}>\\>> and ,\,\|}>\\> such that <\eqnarray*> >|>|>*\*\>*\\i,\,i\\,1\j\n|}>.>>>> If > is actually a monomial group that is generated (as a group) by its infinitesimal elements, then we may always take . If > is an effective monomial monoid, then a grid-based subset \\> is said to be if the predicate \\\\\\> is computable and if finite sets ,\,\|}>\\>> and ,\,\|}>\\> with() are explicitly given. Let be a field of characteristic zero. Given a formal series \\>f>*\> with >\K>, the set \\\f>\0|}>> will be called the of . We say that the formal series is if its support is grid-based and we denote by >> the set of such series. A grid-based series K>> is said to be or if \>> \>>, and we denote by >>> >>> the sets of such series. In2> elementary properties of grid-based series are studied at length. We prove there that >> forms a ring in which all series with supp f\\>> are invertible. In particular, if > is a totally ordered group, then >> forms a field. Given a power series K,\,z|]>|]>> and grid-based series ,\,g\K>>>, there is also anatural definition for the composition =f\g=f,\,g|)>=f\,\,g|)>>. Given a grid-based series K>> the maximal elements of for > are called for . If has a unique dominant monomial, then we say that is , we write > for the dominant monomial of , and call >> the of . If > is totally ordered, then any non-zero grid-based series in >> is regular. Given K>>>, this allows us to extend the relations > and > by defining g\\\\> and g\\\\>. By convention, we also define g> and g\g\0> for all K>>. Assume that and > are effective. Then a grid-based series K>> is said to be if its support is effective and if the map \\\f>> is computable. It can be shown that the set >> of computable grid-based series forms an effective -algebra. Given an \Pinfinitesimal\Q indeterminate , the set >=\i\\|}>> is a monomial monoid for the asymptotic ordering \z\i\j>, and >>> coincides with |]>>. Similarly, >>> coincides with the field of Laurent series |)>>. Notice that \>z> is an element of >>>, since its support >> admits no largest element for >, whence it cannot be grid-based. Beyond Laurent series, it is easily verified that >>> coincides with the field of Puiseux series in over . If is algebraically closed, then so is >>>. Given monomial monoids ,\,\>, one may form the product monomial monoid \\\\> with *\*\\\*\*\\\\\\\\\\\> for all |\,\|\>\\,\,,\>\\>. Then >\\\z>>> coincides with the set of power series ,\,z|]>|]>>>, whereas >\\\z>>> coincides with the set of Laurent series that we denote by ,\,z|)>|)>>. If 2>, then we notice that ,\,z|)>|)>> is a strict subring of the quotient field of ,\,z|]>|]>>. Given monomial monoids ,\,\>, one may also form the set \\\\> whose elements *\*\> are ordered anti-lexicographically: *\*\\\*\*\> if there exists an with \\> and =\> for all i>. The set >\\\z>>> should naturally be interpreted as |]>|]>\|]>|]>> (which is isomorphic to ,\,z|]>|]>>). The set >\\\z>>> is a field that contains ,\,z|)>|)>>, and this inclusion is strict if 1> (notice also that >\\\z>>\K|)>|)> \ |)>|)>>). If is algebraically closed, then >\\\z>>> is again an algebraically closed field (and again, we have >\\\z>>\K>> \ >>>). Let > be a totally ordered group. Given K,\,z|]>|]>> and ,\,g\K>>, we have already observed that g\K>> whenever \1,\,g\1>. This means that we may regard ,\,z|]>|]>> as a space of \Plocal functions\Q >>|)>\K>>. Similarly, K,\,z|)>|)>> can be regarded as a function >>\|)>\K>> and K>\\\z>>> as a function K>> where ,\,g|)>\>>\|)>\\i\j,\k,g\g|}>>. More generally, for any monomial group > with underlying group >*\*z>>, the algebra >> can be regarded as a local function space on a subset of>>\|)>>. From now on, we will assume that > is a monomial group that is generated as a group by its infinitesimal elements. Given a series K>>, a for is a Laurent series >\K,\,z|)>|)>> together with monomials ,\,\\\>> such that >,\,\|)>>. Given several series ,\,f\K>>, and Cartesian representations for each of the >, we say that these Cartesian representations are if they are of the form =>,\,\|)>> for >\K,\,z|)>|)>> and ,\,\\\>>. In3.12> we show that such compatible Cartesian representations always exist. In3>, we gave constructive proofs of several basic facts about Cartesian representations and -based series to be introduced below. These constructive proofs can easily be transformed into algorithms, so we will only state the effective counterparts of the main results. First of all, in order to keep the number of variables in Cartesian representations as low as possible, we may use the following effective variant of3.13>: Let ,\,\,\,\,\> be infinitesimal elements of an effective totally ordered monomial group> with >-powers, such that we have explicit expressions for ,\,\>\\>*\*\>> as power products. Then we may effectively compute infinitesimal ,\,\>\\>*\*\>> with ,\,\,\,\,\\|)>>*\*|)>>>.> -based power series> Let be a local community. We will say that K>> is if admits a Cartesian representation of the form >,\,\|)>> with >=\*z>*\*z>>, \L> and ,\,i\\>. The set >> of all such series forms a -algebra3.14>. If , and> are effective, then any grid-based series in >> is computable. Moreover, we may effectively represent series in >> by Cartesian representations, and >> is an effective -algebra for this representation. A Cartesian representation >,\,\|)>> of K>> is said to be if for each dominant monomial |\>=z>*\*z>> of , there exists a dominant monomial > of with |\>,\,\|)>\\>. We have the following effective counterpart of3.19>: <\proposition> Assume that , and > are effective. Then there exists an algorithm that takes a series in >> as input and computes a faithful Cartesian representation >,\,\|)>> with >=\*z>*\*z>>, \L> and ,\,i\\>. Faithful Cartesian representations are a useful technical tool for various computations. They occur for instance in the proof of the following effective counterpart of3.20>: <\proposition> Assume that , and > are effective. There exists an algorithm that takes an infinitesimal (or bounded, or regular) series K>> as input and that computes a Cartesian representation >,\,\|)>> such that >> is again infinitesimal (or bounded, or regular, respectively). <\subsubsection*> Solving power series equations Assume now that is an effective field with an effective zero test and an algorithm for determining the roots in of polynomials in >, where is a new indeterminate. Let be an effective local community over and > an effective totally ordered monomial group. We notice that agrid-based series in \F>>> can also be regarded as an ordinary power series in >|]>>. We are interested in finding all infinitesimal solutions of apower series equation <\equation*> P+P*f+P*f+\=0, where +P*F+P*F+\\K\F>>>. The Newton polygon method from3> can be generalized in a straightforward way to power series equations instead of polynomial equations and the effective counterpart of 3.21> becomes: <\theorem> There exists an algorithm that takes K\F>>\K>|]>> with 0> as input and that computes all solutions of the equation =0> with K>>>. Given K\F>>> with 0>, we may also consider as an element of >\\>\K|]>>>. Let \K|]>> be the dominant coefficient of for this latter representation. The valuation of > in is called the of . If is algebraically closed, then it can be shown that the number of solutions to the equation in Theorem coincides with the Weierstrass degree, when counting with multiplicities. <\subsubsection*> Scalar extensions Let be a tribe over and let ,\,\> be indeterminates. Then there exists asmallest tribe over |)>> that extends . We will denote this tribe by |)>\L>. Setting <\equation*> \=\>\\\\>\>\z>\\|)>, we notice that |)>\K>\\\\>>\K>> and K>>. This shows that any element in |)>\L> can be represented by an element of >>. In particular, if is effective, then so is |)>\L>. Let be an effective field with an effective zero test. We may consider its algebraic closure > as an effective field with an effective zero test, when computing non-deterministically (we refer to for more details about this technique, which is also called dynamic ). Let be an effective tribe over with an effective zero test. It is convenient to represent elements of \L> by evaluations of polynomials L> at \K>. The algebraic number > is effectively represented using an annihilator K> and we may always take such that deg A>. We say that is if \L> forms again an effective tribe for this representation. This is the case for the tribes of algebraic and dalgebraic power series, but not for arbitrary tribes: if > and is the smallest tribe that contains the exponential power series >, then it follows from Wilkie's theorem that does not contain >; on the other hand, any tribe that contains \L> must contain >. Assume that is algebraically stable. Consider a series \L|)>\K,z,\|]>|]>>, represented as |)>=P+\+P*\>, where \K> is given by an annihilator of degree , and ,\,P\L>. Then we notice that we can compute a representation for as a element of . Indeed, whenever \0> for some 0>, then this means that there exists a monomial \z>*z>*\> such that the coefficient |]> P\K|]>> of > in is a polynomial of non-zero degree in >. On the other hand, |]> P\K>, which means that we can compute an annihilator for > of degree k>. Repeating this reduction a finite number of times, we thus reach the situation in which =\=P=0>, so that \L>. Let still be an effective algebraically stable tribe over with an effective zero test. Given L>, we recall that is said to have in > if = f/\ z|)>=\= f/\ z|)>=0>, but f/\ z|)>\0>. In that case, the Weierstrass preparation theorem states that there exists a unit K,\,z|]>|]>> and amonic polynomial +P*z+\+P\K,\,z|]>|]>|]>> of degree such that . The polynomial is called the associated to (with respect to >). We claim that L> and that there exists an algorithm to compute (and therefore the corresponding unit , since > is effectively stable under restricted division): <\theorem> There exists an algorithm that takes a power series L> of Weierstrass degree in > as input and computes its Weierstrass polynomial as an element of >. <\proof> Consider the effective totally ordered monomial group =z>\\\z>> with >powers. We have a natural inclusion \K\z>>\L>>. Now consider K\z>>\L>\K>|]>|]>>. By theorem, we may compute all infinitesimal solutions ,\,\>\K>\L>> to the equation |)>=0> in > (we recall that there are such solutions, when counting with multiplicities, since > is algebraically closed). Now consider <\eqnarray*> ||-\|)>*\*-\|)>\K\z>>\L>>>>> and let >\K,\,z|]>|]>> be the Weierstrass polynomial associated to . Since >> also admits the infinitesimal roots ,\,\> when considered as an element of >|]>|]>>, we have >> when considering >> as an element of \z>>>. It follows that <\eqnarray*> |>|\z>>\L>\K,\,z|]>|]>.>>>> Now consider a Cartesian representation >,\,\|)>> for with >\L>. By Proposition, we may take >> to be infinitesimal. Since ,\,\> are infinitesimal and ,\,\\z>*\*z>>, Lemma also shows that we may assume without loss of generality that n>. Completing the ,\,\> with additional elements if necessary, this means that we may compute an invertible matrix \n>> such that =z\z> for all . In other words, >\z> with >\L>. Since K,\,z|]>|]>> and is effectively closed under restricted monomial transformations, we conclude that L>. Recall that is an effective algebraically stable tribe over with an effective zero test. Assume that L> has Weierstrass degree in > and let L>. The Weierstrass division theorem states that there exist unique K,\,z|]>|]>> and K,\,z|]>|]>|]>> with <\eqnarray*> ||>>> and > R\d>. We claim that the and of this division once again belong to > and that there exists an algorithm to compute them: <\theorem> There exists an algorithm that takes a power series L> of Weierstrass degree in > and L> as input and computes the quotient and remainder of the Weierstrass division of by as elements of >. <\proof> Let =z>\\\z>> be as in the proof of Theorem. Let ,\,\> be the distinct solutions of |)>=0> when considered as an equation in >, and let > be the multiplicity of each >, so that +\+\=d>. For each , we compute the multiplicity > and the polynomials <\eqnarray*> >||-1>* g|\ z>\,z,\,z|)>*z\K>\L>|]>>>|>||-\|)>>\K>\L>|]>.>>>> Using Chinese remaindering, we next compute the unique K>\L>|]>> such that A mod B> for each and > R\d>. It is easily verified that coincides with the remainder of the Weierstrass division of by . In particular, K,\,z|]>|]>> and we may obtain as an element of > in the same way as in the proof of Theorem. We obtain the quotient of the Weierstrass division by performing the restricted division of by . Often, it is possible to regard or represent elements of the tribe as functions. For instance, we may regard +exp z> as a function |]>|)>\K|]>> that sends ,z|)>> to +exp z>. This point of view is very useful for heuristic zero testing: in order to test whether K,\,z|]>|]>> vanishes, just pick random infinitesimal univariate series ,\,z\t*K|]>> and check whether the first terms of ,\,z|)>> vanish for some suitable large number . In this evaluation approach, we notice that Weierstrass preparation becomes far less expensive: instead of explicitly computing ,\,\\K>\L>> as above, it suffices to show how to ,\,\> (in terms of the evaluations of ,\,z>). For instance, if we evaluate ,\,z> at infinitesimal ordinary power series in |]>>, then the evaluations of ,\,\> will be Puiseux series in >>> that can be computed fast using the Newton polygon method. In the special case of algebraic power series, we recall from the introduction that an alternative approach to Weierstrass division was proposed in. In this approach, algebraic functions are represented in terms of unique power series solutions to certain systems of polynomial equations. Given an algebraic series K,\,z|]>|]>> of Weierstrass degree in >, the idea is then to represent the Weierstrass polynomial associated to as +u*z+\+u> for certain undetermined coefficients. Next, it suffices to form anew system of equations in ,\,u> for which the unique solution yields the actual Weierstrass polynomial. For instance, if is a polynomial, then the relation > P=0> essentially provides us with such asystem, where > P> stands for the remainder of the Euclidean division of by as polynomials in >. The efficiency of this approach from highly depends on the way how the systems of equations that are satisfied by algebraic power series are represented. For instance, completely writing out the remainder > P> as a polynomial in ,\,u,,z,\,z>|]>> typically leads to very large expressions. On the other hand, we expect the approach to be efficient in combination with the evaluation approach mentioned above. If we replace the variables ,\,z> by infinitesimal power series in |]>>, then one may solve the evaluated system of equations in ,\,u> using the relaxed technique from. One attractive way to represent d-algebraic power series in ,\,z> is as elements of asuitable type of finitely generated algebras K,\,z|]>|]>> over that are stable under the derivations ,\,\> with respect to ,\,z>. For instance, we might have ,z,\*z>,erf*z|)>|]>>. In order to compute with implicit functions, there are essentially two approaches. The traditional one procedes by the elimination of one or more coordinates, which may lead to expensive rewritings. An alternative strategy is to represent restrictions of functions in to subvarieties by the same functions in , and rather focus on the computation of the derivations that leave the subvariety invariant. Consider for instance the sphere +1|)>+z+z=1>. We keep representing functions on the sphere using all three coordinates >, >, and >. On the other hand, for differential calculus, we only work with derivations that annihilate the equation of the sphere. In particular, the local coordinates > and > give rise to derivations |~>=\-z*|)>*\> and |~>=\-z*|)>*\> that do not commute. We refer to5> for more details on how to compute with respect to such curved coordinates and how to derive an implicit function theorem in this way. The second, more geometric approach can be generalized to Weierstrass division, by regarding the implicit function theorem as division with respect to a series of Weierstrass degree one. For a d-algebraic series A\K,\,z|]>|]>> of higher Weierstrass degree 1>, we may again consider the restriction of the ambient space to the zero-set of (recall that we may regard as a local function >>|)>\K>>> for any totally ordered monomial group >). Remainders of Weierstrass divisions by then correspond to functions on this zero-set. It is likely that an alternative effective Weierstrass preparation theorem can be obtained by pursuing this line of thought. Throughout this section, we assume that is an effective field with an effective zero test and that is an effective algebraically stable tribe over with an effective zero test. We will write =K,\,z|]>|]>=K>> with =z>*\*z>> and assume that > is endowed with the asymptotic ordering > that corresponds on the standard lexicographical ordering on the exponent vectors: <\eqnarray*> \z>|>|k,i=j\\\i=j\i\j|)>.>>>> For each ,n|}>>, we also define =z>*\*z>> and =K,\,z|]>|]>=K>>. Given an arbitrary subset \\>, we finally define >\\\supp f\\|}>>. Consider a subset \\>> together with a mapping :\\\;b\\>> with >\0> for each \> (intuitively speaking, > should be interpreted as a \Pleading monomial\Q of ; it will play a similar role as the \Pdominant monomial\Q > of from before). Setting =z>*\*z>> with \0> (or =0> and ), we call > the for and > the corresponding . We also denote =k>, =d>, and <\eqnarray*> >||*\>>|>||\\>>|>||>*\*z>>>|>||\\\\\\|}>.>>>> Given any \>, we define <\eqnarray*> >||\\>f*\>*\.>>>> We say that > is a if \>, if > has valuation > ( ,\,z>) for each \> and if \\>=\> for all b> in >. In that case, the elements of> are totally ordered by b\\\>\=\>\k\k>|)>|)>>. <\example> The set =,b|}>> with <\eqnarray*> >||-z*|)>>>|>||-z+z*z*z>>>> forms a Weierstrass system with \b> and <\equation*> ||||>>||>|>|>>||>>|>>||>*z>*z>>||>>||>*z>>>|>>||>*z>\z*z>*z>>||>>||>\z*z>\z>*z>*z>>>|>>||||>>||>|>>||>*z>*z>>||>>||>*z>*z>.>>>>> Let > be a Weierstrass system and >. Given \>, Weierstrass division of > by > yields a unique series a unique \> such that <\eqnarray*> -u*\>|>|,d-1|}>>*\>.>>>> It follows that K>>. Moreover, if K>>, then K>>. We call f\f-u*b> the of with respect to . If \>, then f\\> and we may compute f> as described in Section. We notice that :\\K>>> is an >-linear mapping. The mapping actually preserves in the following sense: a family |)>I>\\> is said to be if the set I\\\supp f|}>> is finite for each \\>. In that case, the sum I>f> is well defined by taking >=I>|)>>> for each \\>. Linear mappings that preserve infinite summation are said to be . Now consider a Weierstrass system =,\,b|}>> with \\\b>. Given \>, we define its with respect to > by <\eqnarray*> > f>||>\\\red>|)>.>>>> By induction over , it can be checked that >:\\K>>> is a strongly linear mapping, where >=\>\\\\>>. If \>, then we also have >\K>>>, and we may compute >> using(). <\example> Let us show how to reduce <\equation*> f=z*b=z*z*z+-z|)>*z with respect to the Weierstrass system > from Example. We start with the computation of <\eqnarray*> > f>||*z*b=z*z*|)>+-z|)>*z.>>>> Now >> f|)>=z*z*|)>> and >|)>=z-z>. Abbreviating \\>|)>>, it follows that *z*|)>> satisfies > \>> f|)>=red> f-u*b>. Consequently, <\eqnarray*> > f>||> f-u*b>>|||*z*|)>+-z-z*z*|)>|)>*z.>>>> We indeed have > f\\>=z>\z*z>\z*z>*z>>. <\remark> Weierstrass reduction is somewhat different in flavour than reduction with respect to a Gröbner basis in the sense that the variables ,\,z> do not play a symmetric role. In particular, the notion of S-polynomials has no direct counterpart in our context. Despite these differences, Weierstrass reduction admits similar applications, such as the computation of Hilbert functions, checking ideal membership, etc. The set >> also plays asimilar role as the set of \Pboxes below a Gröbner staircase\Q. <\remark> Rather than regarding Weierstrass bases as a power series analogue of Gröbner bases, it is actually more appropriate to consider them as a natural counterpart of so-called \PJanet bases\Q. The theory of Janet bases was originally developed in the context of differential equations. Nevertheless, the theory in particular applies to linear partial differential equations in ,\,\> with constant coefficients in , in which case we are really working with polynomials in indeterminates ,\,\> over . A Weierstrass system > is itself said to be if for each \>, we have \K>>>. Two Weierstrass systems > and > are said to be if >> and >> coincide. Let > be an arbitrary Weierstrass system and consider \> with > and >. We claim that there exists a unique \\> with \K>>. Indeed, the Weierstrass preparation theorem implies the existence of a series \>> with \z+\*z+\+\>. It follows that \K>>. If \>, then Theorem shows how to compute . Replacing by *b> for each \>, we obtain an equivalent Weierstrass system such that \K>> for each \>. Let =,\,b|}>> with \\\b>. Replacing > by >\\\red>|)>|)>> for ,1>, we obtain an equivalent reduced Weierstrass system|~>>. If \\>, then this procedure is completely effective, and |~>\\>. Let be an ideal of >. In this subsection, we will define when is in . We proceed by induction over . The ideals and > are always in Weierstrass position, which deals in particular with the case when . Assume that 0> and 0>, and let be the minimal valuation of a non-zero element of. Given a power series \>, let +g*z+g*z+\> be its power series expansion with respect to >. For each \>, the sets i>\I\\\val> g\i|}>> and >\\g\Ii>|}>> are ideals of > and >. We say that is in Weierstrass position if there exists an element I> with >\0> and such that the ideals >,\,I>> of > are in Weierstrass position. Since we assumed to be of charactersitic zero, it contains infinitely many elements. Given a finite number of ideals ,\,I> of >, let us show by induction over that there exists a linear change of coordinates for which ,\,I> are simultaneously in Weierstrass position. A linear change of coordinates is a mapping \\;f\f\\> with \\\+\+K*z|)>> For , we have nothing to do, so assume that 0>. For each ,p|}>>, let \I> be a non-zero element of minimal valuation >. Since is infinite, there exist ,\,\\K> such that \\|)>>>\0>, where =,z+\*z,\,z+\*z|)>>. By the induction hypothesis, there exists a vector \|)>=+\+K*x|)>> of linear series such that \\|)>>\\> are simultaneously in Weierstrass position for ,p|}>> and d>. Setting =,\,\,\|)>\\>, we notice that \\\\|)>>>\0> and \\|)>>\\=\\\\|)>>> for all ,p|}>> and d>. Consequently, the ideals \\\\> are all in Weierstrass position. From a practical point of view, a random linear change of variables puts an ideal into Weierstrass position with probability one. From a theoretical standpoint, it suffices to extend > with > formal parameters and to perform a generic triangular linear change of coordinates. The adjunction of new formal parameters can be done effectively using the technique from the end of Section. Let be an ideal of >. A Weierstrass system > is said to be a for if \\red> f=0|}>>. Assuming that is in Weierstrass position, an abstract way to construct a Weierstrass basis goes as follows. If >, then we take =\>. Otherwise, let be an element of of minimal valuation with >\0>. For each ,d-1|}>>, the induction hypothesis yields aWeierstrass basis>> for the ideal >>. For each \>>, there exists an element =b*z+b*z+\+b*z\Ii>>. Let >> be the set of all such elements > with \>>. Then the disjoint union \\>\\\\>> is a Weierstrass basis for . Our next aim is to provide a more effective criterion for checking whether a reduced Weierstrass system > is in fact a Weierstrass basis of an ideal. Given ,n|}>> we will denote <\eqnarray*> >>||\\k\k|}>>>|>>||\\k=k|}>>>|>>||\\k\k|}>.>>>> The Weierstrass system > is said to be if for all ,n-1|}>> and \>, we have <\eqnarray*> > *b|)>>||>>> Notice that this relation automatically holds for \>>, so it suffices to prove the relation for all ,n-1|}>> and \>>. The main goal of this subsection is to prove the following theorem: <\theorem> Any stable reduced Weierstrass system > is a Weierstrass basis. <\proof> Let ,n-1|}>> and notice that \K>>>> is an >-module. Now consider <\eqnarray*> >||\\red> f=0|}>>>|||\\red>> f=0|}>>>|>||\\>>\*b.>>>> We claim that =N> for all . We clearly have \N>. For the inverse inclusion, it suffices to show that > is an >-module. We will use induction over . For , we have =N=0>. Assuming that =N>, let us now show that =N>. Notice that <\eqnarray*> >||\\>>|>||\>>\*b>>>> and >>:\\\> is an >-linear projection. Now > can be regarded as an >module by letting multiplication by \\> act as <\eqnarray*> \f>|>|>> *f|)>=red>> *f|)>.>>>> Since > is stable, we have \b\M> for all \>>. Since >> generates the >-module =M>, it follows that > is an |]>>-submodule of >. Using the fact that >> is strongly linear, > is actually an >-submodule of >. In other words, *M\M+\>. Using that =M\\>, we conclude that *M=\*\\|)>\M\\*\=M>, whence > is an >-module. Having proved our claim, we finally observe that > is a Weierstrass basis for =M>. Let > be a finite subset of >. Assuming \Pgeneral position\Q, we will show in this section how to compute a Weierstrass basis \\> for the ideal |)>>. The algorithm will proceed by the repeated replacement of elements of> by linear combinations of elements in >. Consequently, along with the computations, we may calculate amatrix \\\>> with =M*\> (in the sense that \>M*f> for all \>). The algorithm raises an error if the general position hypothesis is violated. As usual, we proceed by induction over . If \>, then we may take =\> and we have nothing to do. Otherwise, let \\> be of minimal valuation . If >=0>, then we raise an error. Assuming that >\0>, we first replace by , where \> is such that \K>>. We next replace each other element \\> by g>, so that \\K>>. For each ,d-1|}>>, let >=\\val> g=i|}>>. The recursive application of the algorithm to >|)>> yields a matrix > such that *>|)>> is aWeierstrass basis of >|)>|)>>. Consequently, >=M*\>> yields a Weierstrass system such that >|)>> is a Weierstrass basis. The disjoint union =\\>\\\\>> is also aWeierstrass system and we may reduce it using the algorithm described above. At this point, we have a reduced Weierstrass system with the property that >|)>> is aWeierstrass basis for each . We next compute => *b|)>\||1\k\n|\>,|b\\|\>|\>|}>>. If =>, then> is a Weierstrass basis by Theorem. Otherwise, we replace > by \\\> and recompute> in the same way above, while keeping the same . During each iteration of this loop, the ideals >|)>|)>> of > can only increase, and one of them must increase strictly. Since > is Noetherian, the loop therefore terminates. Sufficiently \Pgeneral position\Q for avoiding any errors can be forced in a similar way as described in the subsection about Weierstrass position. In that case, we systematically work with collections > such that each \\> is a finite subset of >. Modulo a common linear change of coordinates \\> we then compute a Weierstrass basis for each ideal\\|)>> with \\>. Let be an ideal of >. For each \>, let > be the ideal generated by all monomials >*\*z>> with +\+d=d>. Setting =dim /|)>|)>> and =HF=D-D>, the function > is called the of . It is well known that there exists a degree \\> and a polynomial \\> such that =H> for all \>. This polynomial is called the of . Moreover, the > of is the minimal \\> such that =H> for all \>. Now let > be a Weierstrass basis for and denote <\eqnarray*> ,\d>>||>\\d>>>|d>>||>*\*z>\d+\+d\d|}>.>>>> Given \>, let d>=\\d>>f>*\>, so that d>> is a natural representative of modulo>. For some |)>\>\\>>, we have \>Q*b+red>>, whence d>=\>*b|)>d>+red>d>>. It follows that |)>=red> mod |)>>, whence <\eqnarray*> /|)>>|>|,\d>>.>>>> This simply means that <\equation*> D=,\d>|\|>=d>\\>|\|>=d>|\|>-\>\\d>|\|>. Now given \> with =z>*\*z>>, we have <\equation*> \\d>|\|>=>*\*x>\\d-d-\-d>|\|>=-\-d|n-k+1> for all d+\+d>. These formulas allow us to explicitly compute the Hilbert polynomial of and the corresponding regularity. Using a fairly standard technique, let us briefly show how the results of this section generalize to finitely generated >-modules instead of ideals. Let \\> be the free >-module with canonical basis ,\,e>. We may embed this module in the >-submodule =\*z\\\\*z> of |^>\\,\,z>,,\,z>|]>|]>> the mapping :\\\> defined by <\equation*> \*e+\+a*e|)>=a*z+\+a*z. Now consider an >-submodule of > and let > be the ideal of |^>> generated by \\> and >, where ,\,z|)>>. Then <\eqnarray*> >||\\>>>> and we have a natural isomorphism of >-modules <\eqnarray*> |^>/I>|>|/M\|^>/Z\\/M\\.>>>> This latter identity makes it possible to carry over the constructions from this section to the case of >-modules. In particular, one may define and compute the Hilbert function of using the formula <\eqnarray*> >||>-HF,>>>> and it can be checked that =dim /*e+\+J*e|)>|)>>. The corresponding Hilbert polynomial and Hilbert regularity satisfy <\eqnarray*> >||>-H>>|>|>|>,\|)>+1.>>>> Let , =K,\,z|]>|]>=K>> and be as in the previous section, but the reader may forget about the other notations defined there. Let > be an arbitrary total monomial ordering on > with \1,\,z\1>. Given a series \> and a monomial \\>, we denote \>=\\>f>*\>. Given a subset \\>, we also denote \>=\>\f\\|}>>. The notations \>>, \>>, \>>, are defined likewise. In this section, we first very briefly recall the notions of Hironaka reduction and standard bases; for more details, we refer to. Given a finite subset > of >, we next show how to compute a (not necessarily reduced) standard base for |)>>, using the techniques from the previous section. Let > be a finite subset of >>. We define <\eqnarray*> >>||\>\*\>>>|>>||\\>.>>>> Given \>, we say that is with respect to > if \>>. There exists a|)>> such that is reduced with respect to >. Writing =,\,b|}>> with \\\b>, there actually exist unique ,\,q\\> such that *b-\-q*b> is reduced with respect to> and \supp q\\>\\*\>> for all j\i\r>. We define >\f-q*b-\-q*b> to be the of with respect to > and simply write =red>> if => is asingleton. If \> and \\>, then we do not necessarily have >\\>. Nevertheless, for any \\> such that \>> is finite, we may compute >\>> from\>> and \>> using a similar recursion (over \>>) as in the case of Euclidean division. We say that > is if is reduced with respect \> for all \>. <\example> Let be the tribe of algebraic power series. If <\eqnarray*> ||*z>>|||-z|)>*-z|)>,>>>> then it can be shown75> that <\eqnarray*> >||0>*2>+z2>|)>.>>>> Since the power series \0>*z>> is lacunary, it cannot be algebraic, whence > is transcendental. This means that \>, but \\>. <\example> For those readers who are familiar with differential algebra, it is not hard to see that the series > from the previous example is even d-transcendental (this fact was first proved using different techniques in): assume the contrary and consider a d-algebraic equation |)>=0> over >|)>> of minimal Ritt rank. We have =z-\|)>>, so |)>|)>=0> also yields an equation of the same Ritt rank for |)>>. But the change of variables =z> then gives a second, different, d-algebraic equation for |)>> of the same Ritt rank as . Applying Ritt reduction with respect to , this yields a new equation of smaller Ritt rank, which contradicts the minimality hypothesis. In other words, if we replace by the tribe of d-algebraic power series in the above example, then we still have \>, but \\>. Given an ideal \>, let <\eqnarray*> >||\f\I\|}>>>|>||\\.>>>> We say that a finite subset > of >> is a for if |)>\>> is a set of generators of |)>>. We say that > is if > is autoreduced and \K>> for all \>. Any ideal \> admits a unique reduced standard basis. Let \>> be such that =z=z>*\*z>> and =z=z>*\*z>>. Let >=,j|)>,\,max,j|)>|)>>. We define the S-series \\> of and to be <\eqnarray*> >||>*z*f-f>*z*g.>>>> In a similar way as in the case of Gröbner bases, it can be shown that a finite autoreduced subset > of >> is a standard basis if and only if >|)>|)>=0> for all \\>. For any pair |)>\\>, the relation >|)>|)>=0> gives rise to an >-linear relation between the elements of >. Using standard Gröbner basis techniques it can be shown that the space of all >-linear relations between elements of > (the module of syzygies) is generated by the relations of this special form. Given afinite set \\> and |)>>, this characterization theoretically allows us to compute the reduced standard basis > for using a suitable local adaptation of Buchberger's algorithm. However, such an \Palgorithm\Q relies on our ability to compute reductions and Examples and show that we do not have any general algorithm for doing so. Nevertheless, we will show next that it is still possible to compute suitable truncations of >. Given an ideal \> and a monomial \\>, we have \>\I\>>, where \>=I\\\>> is again an ideal. Let> be the reduced standard basis for and assume that is generated by afinite subset > of>. If \>> is finite, then for any \\>> and \\\>> we have an algorithm to compute the >>\red>\>\\\>>. Similarly, for \\>>>, we can compute the >\S\>\\\>>. When using these truncated variants of reduction and S-polynomials, the local analogue of Buchberger's algorithm terminates, since all computations take place in a finite dimensional vector space. This provides us with an algorithm to compute =\\>\>, together with a matrix \\\>> such that =|)>\>>. Let > be a standard basis of an ideal of >, let \>, and let ,\d>> be defined as in(). In a similar way as at the end of section, one can show that <\eqnarray*> /|)>>|>|,\d>>.>>>> Moreover, >=\\b\\|}>>> and the dimension of \b\\|}>,\d>>> can be computed by the familiar technique of counting boxes below a Gröbner staircase. In other words, if we know a standard basis \\> of an ideal of >, then we can compute the Hilbert function of . In this subsection we show that the Hilbert function of also provides us with information about the possible shapes of standard bases for . We will assume that the monomial ordering > on > is in the sense that for any ,\\\\>, there exists a\> with \\>. In particular, the set \>> is finite for any \\>. <\theorem> Let > be a finite subset of > and assume that the monomial ordering>> on> is Archimedean. Then there exists an algorithm to compute a standard basis |~>> for|)>>>, together with a matrix \|~>\\>> with |~>=M*\>. <\proof> Using the techniques from Section, we can compute the Hilbert function > of. Let > be the reduced standard basis of and \\>. Since > is Archimedean, the set \>> is finite. We have shown above that this allows us to compute =\\>\>, as well as amatrix \\\>> with =|)>\>>. Let |~>=M*\>. Given \|~>>, there exists a \> with \>=b\>\0> and =\\>>=\\>>=\>>. Consequently, |~>>\\>>. Now we may also compute the Hilbert function >> of the ideal =|~>>|)>>. We claim that |~>> is a standard basis for if and only if =HF>>. Indeed, we have >=\|~>>\\>=\>, so =HF>> if and only if |~>>=\>>. By definition, a subset \I> is a standard basis of if and only >=\=\>>. In order to compute a standard basis, we pick smaller and smaller elements \\> for>, and perform the above computations until we have =HF>>. Since > is Archimedean, >eventually becomes sufficiently small so that \\> for all \>. At that point, we necessarily have |~>>=\>> and =HF>>. This proves the termination of our algorithm. Let =\>, |^>=K,\,z|]>|]>> be as at the end of section, as well as the further notations , > and >. Assume also that the monomial ordering on > has been extended to |^>\z>*\*z>> in such a way that \1,\,z\1>. Given an >-submodule of >, a subset > of> is defined to be a for if \\|)>\*z\|n+1\i\j\n+r|\>|}>> is a standard basis for the ideal > of |^>>. Given such a standard basis, we may compute the Hilbert function of using =HF>-HF>, by counting boxes below the standard bases> and,\,z|}>> of > and . Given a subset \\> and a monomial \\>, we denote \>=|)>\>*e+\+|)>\>*e\f*e+\+f*e\\|}>>, and we define \>>, likewise. We again have \>\M\>>, where \>=M\\\>> is an >-module. The notions of truncated reduction and truncated S-\Ppolynomials\Q readily generalize to modules (the S-polynomial of > and > with j> being zero, by definition) and it can be shown that the same holds for Theorem. In fact, we are up to proving something even better. Modulo a permutation of variables, we may assume without loss of generality that \\\z>>. The of > is defined to be the number of indices ,n|}>>> such that or n> and \z> for all \>. Given a finite subset > of \\*e\\\\*e>, we also denote by *\> the >-module generated by >. <\theorem> Let > be a finite subset of >. Then there exists an algorithm to compute a standard basis |~>> for*\>>, together with a matrix \|~>\\>> with |~>=T*\>. <\proof> We proceed by induction over the Archimedean rank > of >. If =0>, then the result is obvious. So assume that \0> and let n> be maximal such that >=z>*\*z>> has Archimedean rank one. We denote >=K,\,z|]>|]>> and notice that >=z>*\*z>> has Archimedean rank -1>. Given \\>>, we notice that the truncation \>> is a free finite dimensional >>module. By the induction hypothesis, it follows that we can compute a standard basis for the >>submodule generated by any finite subset > of \>>. Given \\>>, we can also check whether \>*\>: it suffices to decide whether the Hilbert functions of >*\> and >*\|)>> coincide. Given a finite subset > of \>> as above, we say that > is if for all ,r|}>>, \>>, and ,\\\>>> with \\> and \\>, we have <\enumerate> If *e\\> and \\*\>>, then *e|)>\>\\>*\>. If *e,g*\*e\\> and \\>, then ,g*\|)>\>*e\\>*\>. By what precedes, we have an algorithm to check whether > is stable. If not, then we may keep enlarging > with elements of the form *e|)>\>> or ,g*\|)>\>*e> until stabilization takes place. Due to the Noetherianity of \>>, this happens after a finite number of steps. In other words, given \\>>, the above procedure allows us to compute a stable standard basis > for the >>-module *\|)>\>> together with the matrix \\\>> for which =|)>\>>. Let |~>=T*\>. Since >> is Archimedean, a similar reasoning as in the proof of Theorem shows that the Hilbert functions of *|~>> and coincide for a sufficiently small \\>>. At that point, |~>=T*\> contains the desired standard basis of . <\bibliography|bib|plain|all.bib> <\bib-list|10> M.E. Alonso, F.J. Castro-Jiménez, and H.Hauser. Encoding algebraic power series. Technical report, ArXiv, 2014. . M.E. Alonso, T.Mora, and R.Raimondo. A computational model for algebraic power series. , 77:1\U38, 1992. M.Aschenbrenner, L.vanden Dries, and J.vander Hoeven. . Number 195 in Annals of Mathematics studies. Princeton University Press, 2017. 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. Ultraproducts and approximation in local rings. , 253:1\U28, 1980. 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. L.vanden Dries. On the elementary theory of restricted elementary functions. , 53(3):796\U808, 1988. H.Hironaka. Resolution of singularities of an algebraic variety over a field of characteristic zero. , 79:109\U326, 1964. H.Hironaka. Idealistic exponents of singularity. In . John Hopkins University Press, 1975. J.vander Hoeven. Relax, but don't be too lazy. , 34:479\U542, 2002. J.vander Hoeven. , volume 1888 of . Springer-Verlag, 2006. J.vander Hoeven. From implicit to recursive equations. Technical report, HAL, 2011. . J.vander Hoeven. Computing with D-algebraic power series. Technical report, HAL, 2014. . M.Janet. . PhD thesis, Faculté des sciences de Paris, 1920. Thèses françaises de l'entre-deux-guerres. Gauthiers-Villars. D.Lazard. Gröbner bases, gaussian elimination and resolution of systems of algebraic equations. In J.A. van Hulzen, editor, , number 162 in Lect. Notes in Computer Sc., pages 146\U156. Springer Berlin Heidelberg, 1983. A.J. Macintyre and A.J. Wilkie. On the decidability of the real exponential field. Technical report, Oxford University, 1994. K.Mahler. Arithmetische Eigenschaften einer Klasse transzendental-transzendenter Funktionen. , 32:545\U585, 1930. F.Mora. An algorithm to compute the equations of tangent cones. In , number 144 in Lect. Notes in Computer Sc., pages 158\U165. Springer Berlin Heidelberg, 1982. J.F. Ritt. . Amer. Math. Soc., New York, 1950. D.Robertz. , volume 2121 of . Springer, Cham, 2014. K.Weierstrass. , pages 135\U142. Mayer und Müller, 1895. Reprinted by Johnson, New York, 1967. <\initial> <\collection> <\attachments> <\collection> <\associate|bib-bibliography> <\db-entry|+63PGfIkmrfTq8e|article|BK78> <|db-entry> H. T. > <\db-entry|+Li3PZLCHp1NMmM|article|vdH:relax> <|db-entry> > <\db-entry|+Li3PZLCHp1NMlU|inbook|Wei1895> <|db-entry> > <\db-entry|+Li3PZLCHp1NMeN|article|Hir64> <|db-entry> > <\db-entry|+63PGfIkmrfTq8O|article|AMR92> <|db-entry> T. R. > <\db-entry|+63PGfIkmrfTq8M|techreport|ACH14> <|db-entry> F. J. H. > > <\db-entry|+UxLEI9PJlFl3HA|inproceedings|Mora82> <|db-entry> > <\db-entry|+UxLEI9PJlFl3H9|inproceedings|Laz83> <|db-entry> > > <\db-entry|+Li3PZLCHp1NMby|article|DL84> <|db-entry> L. > <\db-entry|+Li3PZLCHp1NMbz|article|DL89> <|db-entry> L. > <\db-entry|+Li3PZLCHp1NMoD|techreport|vdH:dalg> <|db-entry> > > <\db-entry|+Li3PZLCHp1NMl6|article|vdD88> <|db-entry> > <\db-entry|+Li3PZLCHp1NMbx|article|DL80> <|db-entry> L. > <\db-entry|+Li3PZLCHp1NMmr|book|vdH:ln> <|db-entry> > <\db-entry|+PXBVIVv9LqhEls|book|vdH:mt> <|db-entry> L. van den J. van der > <\db-entry|+Li3PZLCHp1NMbh|inproceedings|DDD85> <|db-entry> C. D. > J. > <\db-entry|+63PGfIkmrfTqAE|techreport|MW94> <|db-entry> A. J. > <\db-entry|+Li3PZLCHp1NMnk|techreport|vdH:newimpl> <|db-entry> > > <\db-entry|+E96SXMnMy13sau|phdthesis|Jan20> <|db-entry> > <\db-entry|+E96SXMnMy13saw|book|Rob14> <|db-entry> > <\db-entry|+RqsSWY3usuEwzp|incollection|Hir75> <|db-entry> > <\db-entry|+63PGfIkmrfTqAT|book|Ritt50> <|db-entry> > <\db-entry|+E96SXMnMy13sav|article|Mah30> <|db-entry> > <\references> <\collection> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > <\auxiliary> <\collection> <\associate|bib> BK78 vdH:relax Wei1895 Hir64 AMR92 ACH14 Mora82 Laz83 DL84 DL89 vdH:dalg vdD88 DL80 vdD88 ACH14 vdH:ln ACH14 vdH:mt vdH:dalg vdH:dalg DL84 DL89 vdH:ln vdH:ln vdH:ln vdH:ln vdH:ln vdH:ln vdH:ln vdH:ln vdH:ln DDD85 MW94 AMR92 AMR92 vdH:newimpl vdH:dalg Jan20 Rob14 Hir64 Hir75 Hir75 Ritt50 Mah30 <\associate|toc> |math-font-series||1Introduction> |.>>>>|> |math-font-series||2Common operations on power series> |.>>>>|> |Basic operations on power series |.>>>>|> > |Restricted division |.>>>>|> > |Composition |.>>>>|> > |Implicit functions |.>>>>|> > |Restricted monomial transformations |.>>>>|> > |Examples |.>>>>|> > |math-font-series||3Grid-based series> |.>>>>|> |Monomial monoids |.>>>>|> > |Grid-based sets |.>>>>|> > |Grid-based series |.>>>>|> > |Examples |.>>>>|> > |Asymptotic interpretation |.>>>>|> > |Cartesian representations |.>>>>|> > ||L>-based power series |.>>>>|> > |Solving power series equations |.>>>>|> > |Scalar extensions |.>>>>|> > |math-font-series||4Effective Weierstrass preparation> |.>>>>|> |Effective algebraic closures |.>>>>|> > |Effective Weierstrass preparation |.>>>>|> > |Effective Weierstrass division |.>>>>|> > |The evaluation approach |.>>>>|> > |Algebraic power series |.>>>>|> > |D-algebraic power series |.>>>>|> > |math-font-series||5Effective power series elimination> |.>>>>|> |Weierstrass systems |.>>>>|> > |Weierstrass reduction |.>>>>|> > |Reduced Weierstrass systems |.>>>>|> > |Weierstrass position |.>>>>|> > |Weierstrass bases |.>>>>|> > |Stable Weierstrass systems |.>>>>|> > |Computing Weierstrass bases |.>>>>|> > |Hilbert functions |.>>>>|> > |Generalization to modules |.>>>>|> > |math-font-series||6Standard bases> |.>>>>|> |Hironaka reduction |.>>>>|> > |Standard bases |.>>>>|> > |Truncated standard bases |.>>>>|> > |Hilbert functions |.>>>>|> > |Computing standard bases in the Archimedean case |.>>>>|> > |Standard bases for modules |.>>>>|> > |Computing standard bases in the general case |.>>>>|> > |math-font-series||Bibliography> |.>>>>|> <\links> <\collection> > >