> <\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|]>|]>\\> which 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.>||> 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. In 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|]>|]>\\> which is stable under each of these operations will be called a tribe. We will also specify effective counterparts of these notions. The main result of this note is presented in section: given an effective tribe with an effective zero test, we show that the tribe also satisfies an effective version of the Weierstrass preparation theorem, and we give an algorithm for performing Weierstrass division with remainder. Our result can for instance be applied to the tribes of algebraic power series and D-algebraic 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 a Weierstrass system, as introduced by Denef and Lipshitz and used in. Our main theorem can be regarded as a simpler, effective and more systematic way to prove that certain types of power series form Weierstrass systems. The idea behind our main algorithm 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 a sufficiently 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 which are needed in order to compute with them. 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 which takes K> on input and which 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 which takes \> on 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. From now on, we will always assume that is at least a algebra. 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 -algebra> 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 which takes \> on input and which computes \L>. We say that is if there exists an algorithm which takes L> and \> on input and which computes f\L>. 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 which 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 \,z,\|]>|]>>). More generally, given K,z,\|]>|]>\>, we say that is > if L> whenever K,z,\|]>|]>>, and that is > if this division can be carried out byalgorithm. 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 \/\ 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 positive 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 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 a -vector space of finite dimension. Using this criterion, it is not hard to prove that the set ,z,\|]>|]>> of algebraic power series is a tribe (and actually the smallest tribe for inclusion). 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 K,z,\|]>>. It can be shown that ,z,\|]>|]>> is an effective tribe for this representation. A power series K,\,z|]>|]>> is said to be if it satisfies a non trivial algebraic differential equation ,\> f|)>=0> for each ,n|}>>, where > is a non zero polynomial in +1> variables with coefficients in . We denote by ,z,\|]>|]>> the set of D-algebraic power series. 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 a full proof of the fact that ,z,\|]>|]>> is an effective tribe (the proof being based on earlier techniques from). In what follows, we will only consider commutative monoids. A is amultiplicative monoid > with an asymptotic partial ordering> which is compatible with the multiplication ( \\\\\\\\*\\\*\> and *\\\*\\\\\>). 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 group which 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. 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 ``infinitesimal'' 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 |)>> and >>> 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 ,\,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 it is isomorphic to ,\,z|]>|]>>). The set >\\\z>>> is a field which 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>> \ >>>). From now on, we will assume that > is a monomial group which 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 give 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 which takes a series in >> on 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 which takes an infinitesimal (or bounded, or regular) series K>> on input and which 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 >. 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 solution of a power 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 which takes K\F>>\K>|]>> with 0> on input and which 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 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. 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 polynomials L|]>>, where \K>. The algebraic number > is effectively represented using an annihilator L> and we may always take such that deg A>. It is aroutine verification that \L> forms again an effective tribe for this representation. Consider a series K\L\K,z,\|]>|]>>, represented as |)>=P+\+P*\>, where \K> is given by an annihilator of degree . 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 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 unit K,\,z|]>|]>> and amonic polynomial +P*z+\+P\K,\,z|]>|]>|]>> of degree such that . The polynomial is called the associated 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 which takes a power series L> of Weierstrass degree on 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>. Assume that L> has Weierstrass degree in > and let L>. The Weierstrass division theorem states that there exists a quotient and a remainder in ,\,z|]>|]>|]>> with <\eqnarray*> ||>>> and > R\d>. We claim that and once again belong to > and that there exists an algorithm to compute them: <\theorem> There exists an algorithm which takes a power series L> of Weierstrass degree and L> on input and computes the quotient and remainder of the Weierstrass division of by as elements of >. <\proof> 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 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 . <\bibliography|bib|plain|all.bib> <\bib-list|10> R.P. Brent and H.T. Kung. Fast algorithms for manipulating formal power series. , 25:581--595, 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--326. Springer, 1985. J.Denef and L.Lipshitz. Ultraproducts and approximation in local rings. , 253:1--28, 1980. J.Denef and L.Lipshitz. Power series solutions of algebraic differential equations. , 267:213--238, 1984. J.Denef and L.Lipshitz. Decision problems for differential equations. , 54(3):941--950, 1989. L.vanden Dries. On the elementary theory of restricted elementary functions. , 53(3):796--808, 1988. J.vander Hoeven. Relax, but don't be too lazy. , 34:479--542, 2002. J.vander Hoeven. , volume 1888 of . Springer-Verlag, 2006. J.vander Hoeven. Computing with D-algebraic power series. Technical report, HAL, 2014. . K.Weierstrass. , pages 135--142. Mayer und Müller, 1895. Reprinted by Johnson, New York, 1967. <\initial> <\collection> <\references> <\collection> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > |\>|?|../zerotests/powser2.tm>> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > <\auxiliary> <\collection> <\associate|bib> BK78 vdH:relax Wei1895 DL84 DL89 vdH:dalg vdD88 DL80 vdD88 vdH:dalg DL84 DL89 vdH:ln vdH:ln vdH:ln vdH:ln vdH:ln vdH:ln vdH:ln vdH:ln vdH:ln DDD85 <\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 |.>>>>|> > |Cartesian representations |.>>>>|> > ||L>-based power series |.>>>>|> > |Solving power series equations |.>>>>|> > |math-font-series||4Effective Weierstrass preparation> |.>>>>|> |Effective algebraic closures |.>>>>|> > |Effective Weierstrass preparation |.>>>>|> > |Effective Weierstrass division |.>>>>|> > |math-font-series||Bibliography> |.>>>>|> <\links> <\collection> > >