.
This work has been supported by the ANR10BLAN 0109 LEDA project.

Abstract
Let be an effective field of characteristic zero. An effective tribe is a subset of 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, and that this can be used for the computation of standard bases.
Keywords: Power series, algorithm, Weierstrass preparation, standard basis, Dalgebraic 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 [3] or on relaxed power series evaluation [11].
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, a related 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 2. We first recall the most common operations on formal power series over a field 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 which 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 4 that the tribe also satisfies an effective version of the Weierstrass preparation theorem [17], and we give an algorithm for performing Weierstrass division with remainder. In section 5, we also introduce “Weierstrass bases” 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 [9].
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 [2]. This algorithm has recently been extended to the computation of reduced standard bases of ideals that satisfy Hironaka's box condition [1]. 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 [16] or Lazard's homogenization technique [15].
The main other example that motivated our work is the tribe of Dalgebraic power series (see also [6, 7, 14]). The fact that the collection of all Dalgebraic power series satisfies the Weierstrass preparation theorem was first proved in a more ad hoc way by van den Dries [8]. The notion of a tribe also shares some common properties with the notion of a Weierstrass system, as introduced by Denef and Lipshitz [5] and used in [8]. 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 of Weierstrass degree in , we just compute the solutions of the equation in inside a sufficiently large field of gridbased power series. This allows us to compute the polynomial which we know 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 gridbased power series . For this reason, we briefly recall some basic facts about gridbased power series in section 3, as well as the basic techniques which 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 “Weierstrass position”), we introduce a recursive version of Weierstrass division in section 5. Assuming that such an ideal is finitely generated by elements in the tribe , this allows us to compute a “Weierstrass basis” 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 5 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 the Weierstrass preparation theorem, the techniques of section 5 can use these algorithms instead of the ones from section 4.
In the last section 6, 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 constrast 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 idea using the techniques from section 5. During the construction of a standard basis, this essentially allows us to decide whether the Sseries of two basis elements reduces to zero or whether it reduces to a series of high valuation. In order to avoid certain technical difficulties, we prove our main result only for archimedean monomial orderings. It is plausible that our results can be extended to the general case and we will outline some ideas in this direction.
Our paper uses several notations from the theory of gridbased power series [12] 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 [1]. Nevertheless, the dictionary is rather straightforward and we hope that the reader will appreciate some of the benefits of our notations.
Let be a field of characteristic zero and denote
where we understand that is naturally included in for each . So each element is a power series in a finite number of variables.
We say that is effective if its elements can be represented by concrete data structures and if all field operations can be carried out by algorithms. We say that admits an effective zero test if we also have an algorithm which takes on input and which returns true if and false otherwise.
If is effective, then a power series is said to be computable if we have an effective bound for its dimension (so that ), together with an algorithm which takes on input and produces the coefficient of on output. We will denote the set of computable power series by .
Let be a subset of . We will denote for each and say that is effective if . 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 inhabited in the sense that for all . For each , we will denote and . We say that is stable under differentiation if for all (whence ).
The above closure properties admit natural effective analogues. We say that is an effective 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 effectively inhabited if there is an algorithm which takes on input and which computes . We say that is effectively stable under differentiation if there exists an algorithm which takes and on input and which computes .
We say that is stable under restricted division if whenever and are such that . If is effective, then we say that is effectively stable under restricted division if we also have an algorithm which computes as a function of , whenever . Here we do not assume the existence of a test whether (the behaviour of the algorithm being unspecified if ). More generally, given , we say that is stable under restricted division by if whenever , and that is effectively stable under restricted division by if this division can be carried out by algorithm.
Given , we let denote the evaluation of at . Given and with , we define the composition of and to be the unique power series with
We say that a power series domain is stable under composition if for any and with . If we also have an algorithm for the computation of , then we say that is effectively stable under composition.
We notice that stability under composition implies stability under permutations of the . In particular, it suffices that for to be inhabited. Stability under composition also implies stability under the projections with
If is also stable under restricted division by (whence under restricted division by any ), then this means that we may compute the coefficients of the power series expansion of with respect to by induction over :
Similarly, we obtain stability under the differentiation: for any and , we have
Let with and . Assume that the matrix formed by the first columns of the scalar matrix
is invertible. Then the implicit function theorem implies that there exist unique power series , such that the completed vector with satisfies . We say that a power series domain satisfies the implicit function theorem (for implicit functions) if for the above solution of , whenever . We say that effectively satisfies the implicit function theorem 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 . Since is invertible at least one of the must be non zero. Modulo a permutation of rows we may assume that . Applying the implicit function theorem to only, we obtain a function with . Differentiating this relation, we also obtain
for each . Setting , this yields in particular
Now consider the series . For each , we have
In particular,
By the induction hypothesis, we may thus compute series such that for all . Setting , we conclude that and
for all .
Consider an invertible matrix with rational coefficients. Then the transformation
is called a monomial transformation, where is considered as a column vector. For a power series whose support satisfies , we may apply the monomial transformation to as well:
We say that is stable under restricted monomial transformations if for any and invertible matrix with , we have . We say that is effectively stable under restricted monomial transformations if we also have an algorithm to compute as a function of and . Notice that we do not require the existence of a test whether in this case (the behaviour of the algorithm being unspecified whenever ).
If has positive integer coefficients, then we always have and is trivially stable under the monomial transformation whenever is stable under composition.
We say that the algebra with is a local community if is stable under composition, the resolution of implicit equations, and restricted division by . We say that is a tribe if is also stable under restricted division and restricted monomial transformations. Effective local communities and tribes are defined similarly.
A power series is said to be algebraic if it satisfies a non trivial algebraic equation over the polynomial ring . Setting , 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 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 can be effectively represented as an effective power series together with an annihilator . It can be shown that is an effective tribe for this representation.
A power series is said to be Dalgebraic if it satisfies a non trivial algebraic differential equation for each , where is a non zero polynomial in variables with coefficients in . We denote by the set of Dalgebraic power series. If is an effective field, then effective Dalgebraic power series may again be represented through an effective power series and differential annihilators of the above form. In [14], one may find more information on how to compute with Dalgebraic power series, and a full proof of the fact that is an effective tribe (the proof being based on earlier techniques from [6, 7]).
In what follows, we will only consider commutative monoids. A monomial monoid is a multiplicative monoid with an asymptotic partial ordering which is compatible with the multiplication (i.e. and ). We denote by the set of infinitesimal elements in and by the set of bounded 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 effective 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 effective if it is an effective monomial monoid with an algorithm for the group inverse. We say that is an effective monomial group with powers if we also have a computable powering operation.
A subset is said to be gridbased if there exist finite sets and such that
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 gridbased subset is said to be effective if the predicate is computable and if finite sets and with (1) are explicitly given.
Let be a field of characteristic zero. Given a formal series with , the set will be called the support of . We say that the formal series is gridbased if its support is gridbased and we denote by the set of such series. A gridbased series is said to be infinitesimal or bounded if resp. , and we denote by resp. the sets of such series.
In [12, Chapter 2] elementary properties of gridbased series are studied at length. We prove there that forms a ring in which all series with are invertible. In particular, if is a totally ordered group, then forms a field. Given a power series and gridbased series , there is also a natural definition for the composition .
Given a gridbased series the maximal elements of for are called dominant monomials for . If has a unique dominant monomial, then we say that is regular, we write for the dominant monomial of , and call the dominant coefficient of . If is totally ordered, then any non zero gridbased series in is regular.
Assume that and are effective. Then a gridbased series is said to be effective if its support is effective and if the map is computable. It can be shown that the set of computable gridbased series forms an effective algebra.
Given an “infinitesimal” indeterminate , the set is a monomial monoid for the asymptotic ordering , 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 coincides with the set of power series , whereas coincides with the set of Laurent series .
Given monomial monoids , one may also form the set whose elements are ordered antilexicographically: if there exists an with and for all . The set should naturally be interpreted as (which it is isomorphic to ). The set is a field which contains , and this inclusion is strict if (notice also that ). If is algebraically closed, then is again an algebraically closed field (and again, we have ).
From now on, we will assume that is a monomial group which is generated as a group by its infinitesimal elements. Given a series , a Cartesian representation for is a Laurent series together with monomials such that . Given several series , and Cartesian representations for each of the , we say that these Cartesian representations are compatible if they are of the form for and . In [12, Proposition 3.12] we show that such compatible Cartesian representations always exist.
In [12, Chapter 3], 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 of [12, Lemma 3.13]:
Lemma
Let be a local community. We will say that is Lbased if admits a Cartesian representation of the form with , and . The set of all such series forms a algebra [12, Proposition 3.14]. If , and are effective, then any gridbased 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 is said to be faithful if for each dominant monomial of , there exists a dominant monomial of with . We have the following effective counterpart of [12, Proposition 3.19]:
Proposition
Faithful Cartesian representations are a useful technical tool for various computations. They occur for instance in the proof of the following effective counterpart of [12, Proposition 3.20]:
Proposition
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 a gridbased series in can also be regarded as an ordinary power series in . We are interested in finding all infinitesimal solution of a power series equation
where . The Newton polygon method from [12, Chapter 3] can be generalized in a straightforward way to power series equations instead of polynomial equations and the effective counterpart of [12, Theorem 3.21] becomes:
Theorem
Given with , we may also consider as an element of . Let be the dominant of for this latter representation. The valuation of in is called the Weierstrass degree of . If is algebraically closed, then it can be shown that the number of solutions to the equation in Theorem 4 coincides with the Weierstrass degree, when counting with multiplicities.
Scalar extensions
Let be a tribe over and let be formal indeterminates. Then there exists a smallest tribe over that extends . We will denote this tribe by . Setting
we notice that and . This shows that any element in can be represented by an element of . In particular, if is effective, then so is .
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 [4] for more details about this technique, which is also called dynamic evaluation).
Let be an effective tribe over with an effective zero test. It is convenient to represent elements of by polynomials , where . The algebraic number is effectively represented using an annihilator and we may always take such that . It is a routine verification that forms again an effective tribe for this representation.
Consider a series , represented as , where is given by an annihilator of degree . Then we notice that we can compute a representation for as a element of . Indeed, whenever for some , then this means that there exists a monomial such that the coefficient of in is a polynomial of non zero degree in . On the other hand, , which means that we can compute an annihilator for of degree . Repeating this reduction a finite number of times, we thus reach the situation in which , so that .
Let still be an effective tribe over with an effective zero test. Given , we recall that is said to have Weierstrass degree in if , but . In that case, the Weierstrass preparation theorem states that there exists unit and a monic polynomial of degree such that . The polynomial is called the Weierstrass polynomial associated to . We claim that and that there exists an algorithm to compute (and therefore the corresponding unit , since is effectively stable under restricted division):
Theorem
Proof. Consider the effective totally ordered monomial group with powers. We have a natural inclusion . Now consider . By theorem 4, we may compute all infinitesimal solutions to the equation in (we recall that there are such solutions, when counting with multiplicities, since is algebraically closed). Now consider
and let 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 . It follows that
Assume that has Weierstrass degree in and let . The Weierstrass division theorem states that there exists a quotient and a remainder in with
and . We claim that and once again belong to and that there exists an algorithm to compute them:
Theorem
Proof. Let be the distinct solutions of when considered as an equation in , and let be the multiplicity of each , so that . For each , we compute the polynomials
Often, it is possible to regard or represent elements of the tribe as functions. For instance, we may regard as a function that sends to . This point of view is very useful for heuristic zero testing: in order to test whether vanishes, just pick random infinitesimal univariate series and check whether the first terms of vanish for some suitable large number .
In this evaluation approach, we notice that Weierstrass preparation becomes far less expensive: instead of explicitly computing as above, it suffices to show how to evaluate (in terms of the evaluations of ). For instance, if we evaluate 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 [2]. In this approach, algebraic functions are represented in terms of unique power series solutions to certain systems of polynomial equations. Given an algebraic series of Weierstrass degree in , the idea is then to represent the Weierstrass polynomial associated to as for certain undetermined coefficients. Next, it suffices to form a new system of equations in for which the unique solution yields the actual Weierstrass polynomial. For instance, if is a polynomial, then the relation essentially provides us with such a system (here we understand to be the remainder of the euclidean division of by as polynomials in ).
The efficiency of this approach from [2] 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 as a polynomial in 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 by infinitesimal power series in , then one may solve the evaluated system of equations in using the relaxed technique from [13].
One attractive way to represent Dalgebraic power series in is as elements of a suitable type of finitely generated algebras over that are stable under the derivations with respect to . For instance, we might have . We refer to [14, Section 5.3] for a precise and fully general definition.
Now consider a Dalgebraic series of Weierstrass degree . Then Weierstrass division with respect to can be regarded as restricting Dalgebraic series defined on the dimensional ambient space in to the dimensional subspace in with branches on which vanishes. Restrictions of functions in can again be represented by the same elements in , but the derivations on need to be replaced by new derivations with . We refer to [14, section 5.5] for an implicit function theorem that is based on this line of thought. We expect it to be possible to generalize these ideas and obtain an alternative effective Weierstrass preparation theorem.
Throughout this section, we assume that is an effective field with an effective zero test and that is an effective tribe over with an effective zero test. We will write with and assume that is endowed with the asymptotic ordering such that
For each , we also define and . Given an arbitrary subset , we finally define .
Consider a subset together with a leading monomial with for each . Setting with (or and ), we call the Weierstrass variable for and the corresponding Weierstrass degree. We also denote , , and
Given any , we define
We say that is a Weierstrass system if , if has valuation (w.r.t. ) for each and if for all in . In that case, the elements of are totally ordered by .
Let be a Weierstrass system and . Given , Weierstrass division of by yields a unique series a unique such that
It follows that . Moreover, if , then . We call the Weierstrass reduction of with respect to . If , then and we may compute as described in Section 4.
We notice that is an linear mapping. The mapping actually preserves infinite summation in the following sense: a family is said to be summable if the set is finite for each . In that case, the sum is well defined by taking for each . Linear mappings that preserve infinite summation are said to be strongly linear.
Now consider a Weierstrass system with . Given , we define its Weierstrass reduction with respect to by
By induction over , it can be checked that is a strongly linear mapping, where . If , then we also have , and we may compute using (2).
A Weierstrass system is itself said to be reduced if for each , we have . Two Weierstrass systems and are said to be equivalent if and coincide.
Let be an arbitrary Weierstrass system and consider with and . We claim that there exists a unique with . Indeed, the Weierstrass preparation theorem implies the existence of a series with . It follows that . If , then Theorem 5 shows how to compute .
Replacing by for each , we obtain an equivalent Weierstrass system such that for each . Let with . Replacing by for , 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 Weierstrass position. We proceed by induction over . The ideals and are always in Weierstrass position, which deals in particular with the case when .
Assume that and , and let be the minimal valuation of a non zero element of . Given a power series , let be its power series expansion with respect to . For each , the sets and are ideals of and . We say that is in Weierstrass position if there exists an element with and such that the ideals of are in Weierstrass position.
Assume that is infinite. Given a finite number of ideals of , let us show by induction over that there exists a linear change of coordinates for which are simultaneously in Weierstrass position. A linear change of coordinates is a mapping with
For , we have nothing to do, so assume that . For each , let be a non zero element of minimal order . Since is infinite, there exist such that , where . By the induction hypothesis, there exists a vector of linear series such that are simultaneously in Weierstrass position for and . Notice that we still have for all . 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 3.
Let be an ideal of . A Weierstrass system is said to be a Weierstrass basis for if . 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 . For each , the induction hypothesis yields a Weierstrass basis for the ideal . For each , the exists an element . Let be the set of all such elements with . Then 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 we will denote
The Weierstrass system is said to be stable if for all and , we have
Notice that this relation automatically holds for , so it suffices to prove the relation for all and . The main goal of this subsection is to prove the following theorem:
Theorem
Proof. Let and notice that is an module. Now consider
We claim that for all . We clearly have . For the inverse inclusion, it suffices to show that is an module. We will use induction over . For , we have .
Assuming that , let us now show that . Notice that
and is an linear projection. Now can be regarded as an module by letting multiplication by act as
Since is stable, we have for all . Since generates the module , it follows that is an submodule of . Using the fact that is strongly linear, is actually an submodule of . In other words, . Using that , we conclude that , whence is an module.
Let be a finite subset of . Assuming “general position”, 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 a matrix with (in the sense that 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 , then we raise an error. Assuming that , we first replace by , where is such that . We next replace each other element by , so that . For each , let . The recursive application of the algorithm to yields a matrix such that is a Weierstrass basis of . Consequently, yields a Weierstrass system such that is a Weierstrass basis. The union is also a Weierstrass 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 a Weierstrass basis for each . We next compute . If , then is a Weierstrass basis by Theorem 7. 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 “general position” 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 with . Setting and , the function is called the Hilbert function of . It is well know that there exists a degree and a polynomial such that for all . This polynomial is called the Hilbert polynomial of and the corresponding regularity of .
Now let be a Weierstrass basis for and denote
Given , let , so that is a natural representative of modulo . For some , we have , whence . It follows that , whence
This simply means that
Now given with , we have
for all . These formulas allow us to explicitly compute the Hilbert polynomial of and the corresponding regularity.
Let , and be as in the previous section, but forget about the other notations defined there. Let be an arbitrary total monomial ordering on with . Given a series monomial , we denote . Given a subset , we also denote . The notations , , , etc. are defined likewise.
Let be a finite subset of . We define
Given , we say that is reduced with respect to if . There exists a unique such that is reduced with respect to and we define to be the Hironaka reduction of with respect to . 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 autoreduced if is reduced with respect for all .
Example
then it can be shown [10, p. 75] that
In particular, , but .
Given an ideal , let
We say that a finite subset of is a standard basis for if is a set of generators of . We say that is reduced if is autoreduced and for all . Any ideal admits a unique reduced standard basis.
Let be such that and . Let . We define the Sseries of and to be
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 for all . For any pair , the relation 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 a finite 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 “algorithm” relies on our ability to compute reductions and Example 8 shows that we do not have any algorithm for doing so. Nevertheless, we will show next that it is still possible to compute suitable truncations of .
Given an ideal , we have , where is again an ideal. Let be the reduced standard basis for and assume that is generated by a finite subset of .
If is finite, then for any and we have an algorithm to compute the truncated reduction . Similarly, for , we can compute the truncated Spolynomial . When using these truncated variants of reduction and Spolynomials, 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 be defined as in (3). In a similar way as at the end of section 5, one can show that
Moreover, and the dimension of 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 archimedean in the sense that for any , the exists a with . In particular, the set is finite for any .
Theorem
Proof. Using the techniques from Section 5, 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 a matrix with . Let . Given , there exists a with 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 . Indeed, we have , so if and only if . By definition, a subset is a standard basis of if and only .
Remark
We expect Theorem 9 to generalize to arbitrary monomial orderings, but various technical difficulties have to be worked out with care. We will content ourselves with outlining an approach that we believe should work.
First of all, it is fairly standard that elimination techniques can be generalized to work over finite dimensional modules instead of rings. In particular, the results from section 5 should generalize to finitely generated submodules of , as well as Theorem 9 in the case of archimedean monomial orderings.
Now given a non archimedean monomial ordering , we may assume without loss of generality that we ordered the coordinates such that . Let be maximal such that the restriction of to is archimedean. The idea is now to regard elements of as series in , where . It then suffices to generalize the theory from the previous subsections to the case when is replaced by . Moreover, using induction over , we may assume that we know how to compute standard bases for submodules of . But for each , the truncation is precisely a free finite dimensional module. This should allow us to first compute a standard basis for as an module and next turn this into the truncation of an actual (not necessarily reduced) standard basis.
[1] M.E. Alonso, F.J. CastroJiménez, and H. Hauser. Encoding algebraic power series. Technical report, ArXiv, 2014. http://arxiv.org/abs/1403.4104.
[2] M.E. Alonso, T. Mora, and R. Raimondo. A computational model for algebraic power series. J. Pure and Appl. Alg., 77:1–38, 1992.
[3] R.P. Brent and H.T. Kung. Fast algorithms for manipulating formal power series. Journal of the ACM, 25:581–595, 1978.
[4] J. Della Dora, C. Dicrescenzo, and D. Duval. A new method for computing in algebraic number fields. In G. Goos and J. Hartmanis, editors, Eurocal'85 (2), volume 174 of Lect. Notes in Comp. Science, pages 321–326. Springer, 1985.
[5] J. Denef and L. Lipshitz. Ultraproducts and approximation in local rings. Math. Ann., 253:1–28, 1980.
[6] J. Denef and L. Lipshitz. Power series solutions of algebraic differential equations. Math. Ann., 267:213–238, 1984.
[7] J. Denef and L. Lipshitz. Decision problems for differential equations. The Journ. of Symb. Logic, 54(3):941–950, 1989.
[8] L. van den Dries. On the elementary theory of restricted elementary functions. J. Symb. Logic, 53(3):796–808, 1988.
[9] H. Hironaka. Resolution of singularities of an algebraic variety over a field of characteristic zero. Annals of Math., 79:109–326, 1964.
[10] H. Hironaka. Idealistic exponents of singularity. In Algebraic geometry, The Johns Hopkins Centennial Lectures. John Hopkins University Press, 1975.
[11] J. van der Hoeven. Relax, but don't be too lazy. JSC, 34:479–542, 2002.
[12] J. van der Hoeven. Transseries and real differential algebra, volume 1888 of Lecture Notes in Mathematics. SpringerVerlag, 2006.
[13] J. van der Hoeven. From implicit to recursive equations. Technical report, HAL, 2011. http://hal.archivesouvertes.fr/hal00583125.
[14] J. van der Hoeven. Computing with Dalgebraic power series. Technical report, HAL, 2014. http://hal.archivesouvertes.fr/hal00979367.
[15] D. Lazard. Gröbner bases, gaussian elimination and resolution of systems of algebraic equations. In J. A. van Hulzen, editor, Proc. EUROCAL'83, number 162 in Lect. Notes in Computer Sc., pages 146–156. Springer Berlin Heidelberg, 1983.
[16] F. Mora. An algorithm to compute the equations of tangent cones. In Proc. EUROCAM '82, number 144 in Lect. Notes in Computer Sc., pages 158–165. Springer Berlin Heidelberg, 1982.
[17] K. Weierstrass. Mathematische Werke II, Abhandlungen 2, pages 135–142. Mayer und Müller, 1895. Reprinted by Johnson, New York, 1967.