Effective power series computations by Joris van der Hoeven CNRS, LIX, École polytechnique 91128 Palaiseau Cedex France Email: vdhoeven@lix.polytechnique.fr Final version of June 15, 2019

1Introduction

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 [4] or on relaxed power series evaluation [12].

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 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 4 that the tribe also satisfies an effective version of the Weierstrass preparation theorem [23], 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 [10].

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 a suitable condition [1] (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 [20] or Lazard's homogenization technique [17].

The main other example that motivated our work is the tribe of d-algebraic power series (see also [7, 8, 15]). The fact that the collection of all d-algebraic power series satisfies the Weierstrass preparation theorem was first proved in a more ad hoc way by van den Dries [9]. The notion of a tribe also shares some common properties with the notion of a Weierstrass system, as introduced by Denef and Lipshitz [6] and used in [9]. 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 grid-based 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 grid-based power series . For this reason, we briefly recall some basic facts about grid-based power series in section 3, 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 “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 for 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 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 5. 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 [1] furnishes a conditional algorithm for the computation of reduced standard bases.

Our paper uses several notations from the theory of grid-based power series [13] 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 [1]. 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 [3] for a more 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.

2Common operations on power series

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 that takes as input and that 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 that takes as input and produces the coefficient of on output. We will denote the set of computable power series by .

Basic operations on power series

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. We say that is a power series algebra if is a -algebra. From now on, we will always assume that this is the case. 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 power series 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 that takes as input and that computes . We say that is effectively stable under differentiation if there exists an algorithm that takes and as input and that computes .

Restricted division

For any ring , let . 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 that 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 an algorithm.

Composition

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

Implicit functions

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 the matrix formed by the first columns of 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 .

Restricted monomial transformations

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 non-negative integer coefficients, then we always have and is trivially stable under the monomial transformation whenever is stable under composition.

Examples

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 an -vector space of finite dimension. Using this criterion, one can prove that the set 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 can be effectively represented as an effective power series together with an annihilator . We claim that is an effective tribe for this representation.

Proposition 1. The -algebra forms an effective tribe.

Proof. Let , so that for certain monic polynomials of degrees and in . For , these relations allow us to rewrite both and as -linear combinations of with and . Since these span a vector space of dimension at most , this means that there exist monic polynomials of degree with , and we may compute and using linear algebra. This shows that forms an effective power series algebra that is clearly inhabited.

With the above notations, let and assume that . Then we notice that , so we can compute a polynomial with in a similar way as above. This shows that is effectively stable under restricted division by .

Assume now that with and let be a monic annihilator of of degree for . Assume first that the annihilator of belongs to . Given any , we may then rewrite as a linear combination of with , . In a similar way as above, this allows us to compute a non trivial annihilator of degree of . In general, the annihilator of belongs to for some denominator . In that case, the annihilator of belongs to , whence is algebraic, and so is . In other words, is effectively stable under composition. A similar argument shows the effective stability under restricted monomial transformations.

Let us finally assume that , but , and let and be such that . Let still be the annihilator of . Then yields a non trivial annihilator for . This shows that 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 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 . It then suffices to compute the coefficients of up to this valuation bound. For more details, we refer to [15], where we proved a stronger result in a more general setting.

A power series is said to be d-algebraic if it satisfies an algebraic differential equation for each , where is a non-zero polynomial in variables with coefficients in . This is the case if and only if the differential field generated by over admits a finite transcendence degree. We denote by the set of d-algebraic power series. Using the finite transcendence degree criterion, and similar techniques as in the proof of Proposition 1, it can be shown that forms a tribe.

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 [15], one may find more information on how to compute with d-algebraic power series, and a full proof of the fact that is actually an effective tribe (the proof being based on earlier techniques from [7, 8]). Notice that the most intricate part of this kind of computations is zero testing.

3Grid-based series

Monomial monoids

In what follows, we will only consider commutative monoids. A monomial monoid is a multiplicative monoid with a partial ordering that is compatible with the multiplication (i.e. and ). The notation generalizes Hardy's notation from asymptotic analysis, so we call an asymptotic ordering. 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.

Grid-based sets

A subset is said to be grid-based if there exist finite sets and such that

(1)

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 effective if the predicate is computable and if finite sets and with (1) are explicitly given.

Grid-based series

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 grid-based if its support is grid-based and we denote by the set of such series. A grid-based series is said to be infinitesimal or bounded if resp. , and we denote by resp. the sets of such series.

In [13, Chapter 2] elementary properties of grid-based 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 grid-based series , there is also a natural definition for the composition .

Given a grid-based 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 grid-based series in is regular. Given , this allows us to extend the relations and by defining and . By convention, we also define and for all .

Assume that and are effective. Then a grid-based 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 grid-based series forms an effective -algebra.

Examples

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 . Notice that is not 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 coincides with the set of power series , whereas coincides with the set of Laurent series that we denote by . If , then we notice that is a strict subring of the quotient field of .

Given monomial monoids , one may also form the set whose elements are ordered anti-lexicographically: if there exists an with and for all . The set should naturally be interpreted as (which is isomorphic to ). The set is a field that 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 ).

Asymptotic interpretation

Let be a totally ordered group. Given and , we have already observed that whenever . This means that we may regard as a space of “local functions” . Similarly, can be regarded as a function and as a function where . More generally, for any monomial group with underlying group , the algebra can be regarded as a local function space on a subset of .

Cartesian representations

From now on, we will assume that is a monomial group that 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 [13, Proposition 3.12] we show that such compatible Cartesian representations always exist.

In [13, Chapter 3], 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 of [13, Lemma 3.13]:

Lemma 2.

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 is L-based if admits a Cartesian representation of the form with , and . The set of all such series forms a -algebra [13, Proposition 3.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 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 [13, Proposition 3.19]:

Proposition 3.

Assume that , and are effective. Then there exists an algorithm that takes a series in as input and computes a faithful Cartesian representation with , and .

Faithful Cartesian representations are a useful technical tool for various computations. They occur for instance in the proof of the following effective counterpart of [13, Proposition 3.20]:

Proposition 4.

Assume that , and are effective. There exists an algorithm that takes an infinitesimal (or bounded, or regular) series as input and that computes a Cartesian representation such that is again infinitesimal (or bounded, or regular, respectively).

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 a grid-based series in can also be regarded as an ordinary power series in . We are interested in finding all infinitesimal solutions of a power series equation

where . The Newton polygon method from [13, Chapter 3] can be generalized in a straightforward way to power series equations instead of polynomial equations and the effective counterpart of [13, Theorem 3.21] becomes:

Theorem 5.

There exists an algorithm that takes with as input and that computes all solutions of the equation with .

Given with , we may also consider as an element of . Let be the dominant coefficient 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 5 coincides with the Weierstrass degree, when counting with multiplicities.

Scalar extensions

Let be a tribe over and let be 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 .

4Effective Weierstrass preparation

Effective algebraic closures

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 [5] 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 evaluations of polynomials at . The algebraic number is effectively represented using an annihilator and we may always take such that . We say that is algebraically stable if forms again an effective tribe for this representation. This is the case for the tribes of algebraic and d-algebraic 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 [18] that does not contain ; on the other hand, any tribe that contains must contain .

Assume that is algebraically stable. Consider a series , represented as , where is given by an annihilator of degree , and . 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 .

Effective Weierstrass preparation

Let still be an effective algebraically stable 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 a unit and a monic polynomial of degree such that . The polynomial is called the Weierstrass polynomial associated to (with respect 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 6. There exists an algorithm that takes a power series of Weierstrass degree in as input and computes its Weierstrass polynomial as an element of .

Proof. Consider the effective totally ordered monomial group with -powers. We have a natural inclusion . Now consider . By theorem 5, 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

Now consider a Cartesian representation for with . By Proposition 4, we may take to be infinitesimal. Since are infinitesimal and , Lemma 2 also shows that we may assume without loss of generality that . Completing the with additional elements if necessary, this means that we may compute an invertible matrix such that for all . In other words, with . Since and is effectively closed under restricted monomial transformations, we conclude that .

Effective Weierstrass division

Recall that is an effective algebraically stable tribe over with an effective zero test. Assume that has Weierstrass degree in and let . The Weierstrass division theorem states that there exist unique and with

and . We claim that the quotient and remainder of this division once again belong to and that there exists an algorithm to compute them:

Theorem 7. There exists an algorithm that takes a power series of Weierstrass degree in and as input and computes the quotient and remainder of the Weierstrass division of by as elements of .

Proof. Let be as in the proof of Theorem 6. 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 multiplicity and the polynomials

Using Chinese remaindering, we next compute the unique such that for each and . It is easily verified that coincides with the remainder of the Weierstrass division of by . In particular, and we may obtain as an element of in the same way as in the proof of Theorem 6. We obtain the quotient of the Weierstrass division by performing the restricted division of by .

The evaluation approach

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.

Algebraic power series

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, where stands for 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 [14].

D-algebraic power series

One attractive way to represent d-algebraic 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 .

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 . 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 and that do not commute. We refer to [15, Section 5] 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 of higher Weierstrass degree , we may again consider the restriction of the ambient space to the zero-set of (recall that we may regard as a local function 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.

5Effective power series elimination

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 with and assume that is endowed with the asymptotic ordering that corresponds on the standard lexicographical ordering on the exponent vectors:

For each , we also define and . Given an arbitrary subset , we finally define .

Weierstrass systems

Consider a subset together with a mapping with for each (intuitively speaking, should be interpreted as a “leading monomial” of ; it will play a similar role as the “dominant monomial” of from before). 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 .

Example 8. The set with

forms a Weierstrass system with and

Weierstrass reduction

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

(2)

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).

Example 9. Let us show how to reduce

with respect to the Weierstrass system from Example 8. We start with the computation of

Now and . Abbreviating , it follows that satisfies . Consequently,

We indeed have .

Remark 10. Weierstrass reduction is somewhat different in flavour than reduction with respect to a Gröbner basis in the sense that the variables 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 a similar role as the set of “boxes below a Gröbner staircase”.

Remark 11. 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 “Janet bases” [16, 22]. 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 .

Reduced Weierstrass systems

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 6 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 .

Weierstrass position

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.

Since we assumed to be of charactersitic zero, it contains infinitely many elements. 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 valuation . 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 . Setting , we notice that and for all and . 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.

Weierstrass bases

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 , there exists an element . Let be the set of all such elements with . Then the disjoint union is a Weierstrass basis for .

Stable Weierstrass systems

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 12. Any stable reduced Weierstrass system is a Weierstrass basis.

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.

Having proved our claim, we finally observe that is a Weierstrass basis for .

Computing Weierstrass bases

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 disjoint 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 12. 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 .

Hilbert functions

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 known that there exists a degree and a polynomial such that for all . This polynomial is called the Hilbert polynomial of . Moreover, the regularity of is the minimal such that for all .

Now let be a Weierstrass basis for and denote

			(3)
			(4)

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.

Generalization to modules

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 . We may embed this module in the -submodule of via the mapping defined by

Now consider an -submodule of and let be the ideal of generated by and , where . Then

and we have a natural isomorphism of -modules

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

and it can be checked that . The corresponding Hilbert polynomial and Hilbert regularity satisfy

6Standard bases

Let , 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 . Given a series and a monomial , we denote . Given a subset , we also denote . The notations , , , etc. 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 [10, 11]. 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.

Hironaka reduction

Let be a finite subset of . We define

Given , we say that is reduced with respect to if . There exists a such that is reduced with respect to . Writing with , there actually exist unique such that is reduced with respect to and for all . We define to be the Hironaka reduction of with respect to and simply write if is a singleton. 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 13. Let be the tribe of algebraic power series. If

then it can be shown [11, p. 75] that

Since the power series is lacunary, it cannot be algebraic, whence is transcendental. This means that , but .

Example 14. For those readers who are familiar with differential algebra [21], 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 [19]): assume the contrary and consider a d-algebraic equation over of minimal Ritt rank. We have , so also yields an equation of the same Ritt rank for . But the change of variables 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 .

Standard bases

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 S-series 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 Examples 13 and 14 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 .

Truncated standard bases

Given an ideal and a monomial , 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 S-polynomial . 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 .

Hilbert functions

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 .

Computing standard bases in the Archimedean case

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 , there exists a with . In particular, the set is finite for any .

Theorem 15. 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 .

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 .

In order to compute a standard basis, we pick smaller and smaller elements for , and perform the above computations until we have . Since is Archimedean, eventually becomes sufficiently small so that for all . At that point, we necessarily have and . This proves the termination of our algorithm.

Standard bases for modules

Let , be as at the end of section 5, as well as the further notations , and . Assume also that the monomial ordering on has been extended to in such a way that .

Given an -submodule of , a subset of is defined to be a standard basis for if is a standard basis for the ideal of . Given such a standard basis, we may compute the Hilbert function of using , by counting boxes below the standard bases and of and .

Given a subset and a monomial , we denote , and we define , etc. likewise. We again have , where is an -module. The notions of truncated reduction and truncated S-“polynomials” readily generalize to modules (the S-polynomial of and with being zero, by definition) and it can be shown that the same holds for Theorem 15. In fact, we are up to proving something even better.

Computing standard bases in the general case

Modulo a permutation of variables, we may assume without loss of generality that . The Archimedean rank of is defined to be the number of indices such that or and for all . Given a finite subset of , we also denote by the -module generated by .

Theorem 16. Let be a finite subset of . Then there exists an algorithm to compute a standard basis for , together with a matrix with .

Proof. We proceed by induction over the Archimedean rank of . If , then the result is obvious. So assume that and let be maximal such that has Archimedean rank one. We denote and notice that has Archimedean rank .

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 stable if for all , , and with and , we have

1. If and , then .

2. If and , then .

By what precedes, we have an algorithm to check whether is stable. If not, then we may keep enlarging with elements of the form or 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 . Since is Archimedean, a similar reasoning as in the proof of Theorem 15 shows that the Hilbert functions of and coincide for a sufficiently small . At that point, contains the desired standard basis of .

Bibliography