Uniformization of multivariate power series Joris van der Hoeven Dépt. de Mathématiques (bât. 425) CNRS, Université Paris-Sud 91405 Orsay Cedex France June 4, 2009

1.Introduction

Let be a field and an extension field of . Given a polynomial , a natural question is to study the behaviour of as a function . In order to capture all relevant properties of , it is convenient to assume that is algebraically closed, or at least contains the algebraic closure of . Using quantifier elimination, we may always cut into a finite number of “regions” (which are constructible subsets of in this case), each on which has a “uniform behaviour”. For instance, outside a certain Zariski closed singular locus, the solutions to are given by a finite number of ramified non singular algebraic functions .

A similar challenge can be stated for many other theories. For instance, if is a real field, then we may also want to study the real geometric properties of the function , such as those regions where is positive. In this case, is rather taken to be the real closure of and cylindrical decomposition is a typical technique for studying the behaviour of the function .

In this paper, we will consider a power series over a field of characteristic zero, instead of a polynomial. We will see that can again be regarded as a function on a suitable space of grid-based series over a sufficiently large, non archimedean monomial group . At a first approximation, elements in the field might be taken to be series in with real exponents, and with a lexicographical ordering on . Series in and correspond to infinitesimal resp. bounded series in . We refer to section 2 for more precise definitions.

A suitable language for the study of power series functions is the usual language of fields, extended with an asymptotic neglection relation . In this language, should be interpreted as , should be interpreted as and corresponds to the case when . If and lie in a valued field, such as , then we also have , and . Even though is not a valued field, it does come with a partial neglection relation [vdH06, Chapter 1]. Furthermore, a relation such as naturally corresponds to a subset of .

From the asymptotic point of view, the simplest behaviour of a series on a subset of is when only depends on for points . If , this is the case if and only if is a uniform series in the sense that its support admits a unique -maximal element , called the dominant monomial of . In other words, we may write , where is a unit in . The series also satisfies on the region where . Again, it is possible to regard as a uniform series, but in a suitable ring of conical series, which corresponds precisely to the coordinate ring for the region on which .

Given an arbitrary series , our main objective is to present an algorithm which decomposes the space into a finite number of well-described regions , endowed with suitable local conical coordinates, such that becomes a uniform conical series on each of these regions, with respect to the local coordinates. Moreover, the necessary changes of coordinates will respect the elimination order on . More precisely, if are the local coordinates on any of the regions , then only depends on for each . In particular, at the end of the algorithm, it will be possible to read off the solutions to the equation from the answer.

Resolution of singularities [Hir64], which has recently been made effective [Vil89, Bod01, FKP06], is one means to solve our problem. However, the resolution process has to be carefully adapted in order to preserve the elimination ordering, which is non trivial. Moreover, resolution of singularities is really an overkill for our problem: for many practical applications, it is not necessary to glue the final regions together using birational maps. What is worse, insisting on global desingularization can be expected to artificially blow up the complexity, since the size of a description of the final non singular variety is usually huge.

In fact, our objective is closer to local uniformization in the sense of Zariski [Zar40]. In the future, we hope to provide a dictionary which will prove both approaches to be equivalent up to preservation of the elimination order. As we will see, one major advantage of our approach is that the general case is essentially reduced to the Newton-Puiseux method in dimension two.

An earlier version of our approach was first described in [vdH97, Chapter 10]. Apart from some minor changes (notational, terminological and the fact that we will not assume to be ordered), several improvements were made. First of all, section 4.2 contains a more geometric description of the uniform Newton degree, thereby simplifying our previous treatment of parallel descent of the Newton degree. We also corrected some errors concerning the use of so called pseudo-coefficients (see section 3.5). Finally, we adapted the method to series with coefficients in a -vector space instead of , where is typically of the form for . Although this last change is not mandatory, it simplifies the overall treatment and also prepares for the uniformization of local vector fields.

Let us briefly outline the contents of the paper. In section 2, we introduce conical varieties and their function rings, whose elements are conical series. In order to deal with regions where for certain , we will rewrite

for a new parameter over and . For this reason, the coefficients of our conical series will always live in an algebraic extension of with a finite number of parameters. It is also possible, but less convenient, to directly work with serial coordinates which are either infinitesimal or bounded . In section 2.4, we introduce refinements, which correspond to injective conical morphisms between conical varieties of the same dimension.

In section 3, we recall some general techniques for machine computations with conical series. First of all, we present a technique for computations with series with respect to changing coordinate systems. We next recall the formalism of non deterministic algorithms, which is suitable for modeling the situation in which a region has to be cut into several pieces. Finally, we briefly recall the notion of a local community. This concept aims at modeling certain subclasses of conical series, which are suitable for computations on a concrete computer. Of course, general power series are not even representable, since they may involve infinitely many coefficients. All effective computations assume that is an effective field. This means that there are algorithms for performing the field operations and the equality test in .

In section 4, we turn to algorithms for the uniformization of a conical series. We first recall the classical Newton polygon method in two dimensions, but for series whose coefficients lie in a more general field of generalized power series. We next consider uniform versions of this method, using evaluations of all but one variable. In particular, we will define an important invariant, the uniform Newton degree, which will strictly decrease every two refinements. We finally present our uniformization algorithm. Since a uniform series remains uniform under refinements, the algorithm can also be used for the simultaneous uniformization of several series.

Uniformization is a key ingredient for many computations with multivariate power series. Clearly, we need it in order to describe the asymptotic behaviour of such series. We typically also need it for the inversion of a power series, for expressing the zeros of as a function in the remaining variables, and for many other problems which can be stated in the first order theory of fields with a neglection relation . For instance, given two series , it allows us to determine the region of all for which .

2.Conical varieties

2.1.Grid-based series

In this section, we start by recalling some terminology and basic facts from [vdH06, Chapter 2]. Let be a field of characteristic zero and a monomial monoid, that is, a commutative multiplicative monoid with a compatible partial ordering . In this paper, we will always assume that is torsion free and a lattice for the ordering .

A subset is said to be grid-based if

for certain monomials with . Given a formal sum with , we call

the support of . We say that is a grid-based series if is grid-based. We denote by the set of all grid-based series.

Let . The finite set of -maximal elements in is called the set of dominant monomials of . If is a singleton, then is said to be uniform. In that case, the unique element of is called the dominant monomial of and the corresponding coefficient the dominant coefficient of . We say that is infinitesimal (and write ) if for all . Similarly, is said to be bounded (and we write ) if for all . We write if is uniform and ; this is the case if and only if with and .

The above definitions and results generalize to the case when the coefficient field is replaced by a -vector space . In fact, this may even be seen as a special case, when regarding as a subset of the quotient field of the tensor algebra of . When working with coefficients in , proposition 1 becomes:

A possibly infinite family is said to be grid-based if is grid-based and is finite for every . In that case, the sum with is a well-defined grid-based series in . It is possible to redevelop basic algebraic notions for this so called strong summation [vdH06, Chapters 2 and 6]. For instance, a strongly linear map is a linear map which preserves infinite summation in a suitable manner. Similarly, a morphism of strong algebras corresponds to the operator which substitutes for each .

2.2.Grid-based series with parameters

Let be an algebraic extension of which contains the algebraic closure of . A system of parametric coordinates is determined by a finite number of parameters , subject to a finite number of polynomial constraints and one polynomial inequality over :

We denote by the corresponding parametric variety of all points which satisfy these constraints. We also denote by

the corresponding parametric coordinate ring. Given a -vector space , we let . If is an effective field, then it is classical that the consistency of a finite system of polynomial constraints can be checked by algorithm, using Groebner basis techniques for instance.

It is classical that any point induces a unique morphism

with for all , and vice versa. Given , we will then write . Given a second system of parametric coordinates , a morphism

induces a morphism of parametric varieties by asking that for all . If is injective, then will be called a subregion of .

A grid-based series with parameters in is simply a grid-based series in (or in ). Given a point , we let (or with ) be its evaluation at this point. We say that is uniform if admits a unique dominant monomial and an invertible dominant coefficient. This is the case if and only if is uniform for all , since . More generally, we therefore say that is uniform if and only if is uniform for all . We say that is -uniform if there exists a finite set such that for all .

Proposition 3. Let . Then can be decomposed

into a finite number of subregions, such that for each , there exists a set , such that for each , we have .

Proof. Let be the set of monomials , such that is a dominant monomial of for some . Assume for contradiction that is infinite. Since is grid-based, there exists an infinite decreasing sequence of elements in . Since is Noetherian, the ideal generated by is generated by for some . Now choose such that is a dominant monomial of . Then , whence , a contradiction. This shows that and are finite. Given , the set is determined by the polynomial equations for all such that for all , and one polynomial inequation .

2.3.Conical power series

A system of serial coordinates consists of a finite number of serial coordinates , subject to a finite number of asymptotic constraints

These constraints can be encoded by the finite set , which is said to be consistent if

In that case, is a monomial group for the partial ordering given by

The set generates a monomial submonoid

which is said to be conical. Series in , , and are also said to be conical. For what follows, it will be convenient to always assume that

The theory of linear programming provides us with efficient algorithms for testing consistency and whether a given constraint is implied by the constraints in .

A system of conical coordinates consists of the combination of a system of parametric coordinates and a system of serial coordinates. In what follows, we will shortly call such an a coordinate system. We will denote the corresponding parameters by , the serial coordinates by , the asymptotic constraints by , and . If is clear from the context, then we will drop all subscripts . When working with respect to a coordinate system or , we will again drop subscripts and rather use tildas or primes for distinguishing from . For instance, the serial coordinates with respect to will be denoted by .

The coordinate ring of is given by

Let be a totally ordered monomial group such that any conical monomial group can be embedded in . Given any infinite dimensional totally ordered vector space over , one may take to be the multiplicative monomial group isomorphic to . A morphism of strong algebras

with is entirely determined by the -tuple and the -tuple . The pair is called a point and the set of all such points the conical variety associated to . As before, we will write for all .

Let and let the coordinate system obtained from by removing and keeping the same parameters (see remark 4 below), so that . A series is said to be ordinary in if . Then may also be regarded as a series in or as a series in . If is the only element in which depends on (so that ), then is called an ordinary coordinate of , and all series in are ordinary in .

Remark 4. A more precise construction of the coordinate system goes as follows. We take . The serial coordinates of are . We finally enforce

by taking to be the subset of monomials which admit only trivial factorizations in . This minimal set of generators is finite and can be computed as follows. Using linear programming, we first compute a minimal set of generators for the cone . For each , the minimal with yields a minimal generator for . Then , so we conclude by removing all elements which can be factored from .

2.4.Refinements

Consider two coordinate systems and . A conical morphism is a morphism of strong algebras

with . Notice that the image of a uniform series under is again uniform as soon as and zero otherwise. The morphism induces a mapping

on the associated varieties by

for all and . If is injective, then will be called an immersion. If is injective and the dimensions and of and coincide, then is called a refinement and

a subregion of . A refinement is said to be triangular, if only depends on and is ordinary in , for . A -refinement is a triangular refinement , such that for . A refinement is said to be strict in if is triangular and is ordinary in for all . A -refinement is said to be strict if it is strict in .

The composition of two triangular refinements is again triangular, the composition of two -refinements is again a -refinement, and the composition of a refinement which is strict in and a triangular refinement (or a triangular refinement and a refinement which is strict in ) is again strict in . We will sometimes say that the coordinate is refined, when applying a refinement which is strict in .

Example 5. Consider a conical morphism with and for all . Then is entirely determined by its restriction to . In particular, is a refinement if and only if consists of fractions of elements in . Such refinements correspond to the imposition of constraints on the parameters.

Example 6. Consider a conical morphism such that , and for all . Then and is an -refinement, which corresponds to the imposition of new asymptotic constraints on serial coordinates.

Example 7. The ramification of orders is the -refinement defined by and

More precisely, consists of , together with a constraint for every constraint .

Example 8. Given a coordinate system , we will denote by the -dimensional coordinate system formed by the parameters and the first serial coordinates of . We denote by the corresponding conical monomial group. Given a new invertible parameter and an infinitesimal monomial in which is incomparable to , let us show that the asymptotic change of variables

(1)

gives rise to a strict -refinement. Indeed, the parametric coordinate ring of the new coordinate system is given by . The new serial coordinates are for and a new coordinate . The monomial group is generated by and the monomials with . We take for and . Given a point , we have

so is indeed a -refinement. Since is an ordinary coordinate of , the refinement is strict in .

Example 9. Let be a uniform series with an invertible dominant coefficient and infinitesimal dominant monomial . If is incomparable to , then it can be shown as above that the asymptotic change of coordinates

(2)

gives rise to a strict -refinement .

3.Machine computations with conical series

3.1.Computations with respect to changing coordinates

One technical difficulty concerning the upcoming algorithms is that we frequently have to change our coordinates. From a notational point of view, it would be cumbersome to explicitly rewrite all our objects with respect to the new coordinates after every change. Instead, we will rather assume that our coordinate system with the corresponding constraints is stored in a global variable and that our objects are automatically rewritten with respect to the most recent coordinate system when necessary.

More precisely, starting with the coordinate ring , the execution of an algorithm up to a given “current execution point”, gives rise to a sequence of refinements:

The “current coordinates” at that point are encoded by the finite sets of parameters and serial coordinates, together with the constraints imposed upon them.

Now consider a series introduced between the -th and the -th refinement. We will encode such a series by the pair with . Whenever an operation needs to be performed on at the current execution point, we automatically replace this encoding by , where and . Similarly, a monomial will be encoded by the pair , where . When necessary, this encoding will be replaced by , where and is the dominant monomial of ; this will ensure that monomials remain monomials of the same asymptotic magnitude at any stage, even though their values as series may change.

Sometimes, we will also work with a system of “subcoordinates” of the current coordinate system . This means that the serial coordinates of are a subset of , with the constraints induced from . The parametric coordinates of and are assumed to be identical. When working with respect to such a system of subcoordinates, any change of coordinates for lifts to a change of coordinates for . In particular, all changes of coordinates can always be performed on , even when we need to work with respect to subcoordinates.

Remark 10. Various variants of the above strategy are possible. For instance, whenever an operation on two series takes place, then we may rewrite them with respect to the simplest common coordinate system. Instead of using a global variable for the current coordinate system, operations on the coordinate system (such as the imposition of constraints) may also be done on the series which are intended to use the new coordinates, thereby allowing for a more functional programming style.

3.2.Non deterministic algorithms

Another frequently occurring difficulty is that certain relations may not be satisfied uniformly on the current region . For instance, a polynomial relation for the parameters may be satisfied on a certain subregion, whereas the opposite relation is satisfied on another subregion. If, at a certain point during the execution of an algorithm, we need to decide whether or , we may thus have to decompose the current region into these two subregions and continue the execution on each of them.

A classical computer science approach to this situation is to allow for so called non deterministic algorithms. This non deterministic setting features an additional programming construct called case separation, which consists of selecting the way to continue the algorithm non deterministically, among a finite number of cases. For instance, when testing whether vanishes, one branch would correspond to the subregion of for which and the other branch would correspond to the subregion of for which .

It is classical that a non deterministic computation can be represented by a tree: each inner node of the tree corresponds to a non deterministic choice in the algorithm and the children of the node to the possible continuations of the algorithm. König's lemma implies that this computation tree is finite if and only it contains no infinite chains. In other words, if the non deterministic algorithm terminates for all possible sequences of choices, then we obtain a deterministic algorithm by running the non deterministic algorithm several times, for each possible sequence of choices.

In our setting, each node of the computation tree also corresponds to a coordinate system and the case separation induces a partition

In particular, the root of the tree corresponds to the original coordinates and the leafs of the tree correspond to the final coordinates for which the algorithm provides uniform results. At the end, it will then be guaranteed that

Throughout our algorithms, we will assume that branches which correspond to empty regions are automatically eliminated. In other words, a non deterministic process is killed as soon as contradictory constraints are imposed.

Remark 11. The approach of non deterministic algorithms is known under various other names, depending on the area. In computer algebra, it is sometimes referred to as dynamic evaluation. In basic programming languages, non deterministic algorithms are best implemented simply by rerunning the algorithm several times from its start and exhausting all sequences of non deterministic choices. In high order programming which support so called continuations, this rerunning can be avoided.

3.3.Local communities

Assume now that is an effective field. Since power series in and more general grid-based power series in may contain infinitely many coefficients, we need to restrict our attention to suitable subclasses of series in order to compute with them. In this section, we recall the concept of a “local community”, which axiomatizes such computationally interesting classes of series. In fact, it also models other interesting classes of series, such as the class of convergent multivariate power series over .

We will only recall the main definitions and facts about local communities and similarly for Cartesian representations in the next subsection. More details can be found in [vdH06, Sections 3.4 and 3.5] and [vdH97].

A local community over an effective -algebra is a family of -subalgebras , which satisfies the following properties:

LC1

For all , we have .

LC2

Given and , such that is divisible by , we have .

LC3

Given a strong algebra morphism with , we have .

LC4

Given and , such that and , let be the unique power series such that the substitution of for in vanishes. Then .

Given and , we notice that

since computing the limit for reduces to substituting by zero. In particular, when expanding as a series in , then each of its coefficients is again in .

Example 12. Let be the set of all algebraic power series in over for each . Then is a local community over , which is actually the smallest local community over .

Example 13. Assuming or , let be the set of all convergent power series in over . Then is a local community.

The local community is said to be effective if there are algorithms for carrying out the -algebra operations in , for performing the division by in LC2, for the substitution in LC3, and for computing as a function of in LC4. For instance, the local community of all algebraic power series over is effective.

Given a local community over and a system of parametric coordinates over , we denote by the smallest local community over which contains . Given another system of parametric coordinates, any morphism induces a natural componentwise morphism . We say that is parametrically effective if is effective for each system of parametric coordinates over and if is computable whenever is computable. The local community of all algebraic power series over is parametrically effective.

Remark 14. It can be shown that is parametrically effective as soon as is effective. The idea is first to represent elements in by algebraic series in after substitutions for a suitable point and transcendence basis of . Then elements in can be regarded as elements in .

3.4.Cartesian representations

A multivariate Laurent series in over is an element with the componentwise partial ordering on . We may always rewrite with and .

Let be an arbitrary monomial monoid and consider a grid-based series . A Cartesian representation for is a series with for some strong algebra morphism with for all . A family of Cartesian representations is said to be compatible if the strong morphism is the same for all its components . It can be shown that any finite family of grid-based series admits a family of compatible Cartesian representations.

Let be a local community over . A Cartesian representation of is called an -representation of . The set of all series with an -representation is clearly an -subalgebra of . A Cartesian representation of is said to be faithful if for every dominant monomial of , there exists a dominant monomial of with . Any can be shown to admit a faithful -representation. Every uniform also admits a uniform -representation. Moreover, if is effective, then there are algorithms for computing faithful and uniform -representations.

The above definitions and properties extend to the case when we take our coefficients in a strong -module of the form . In that case, a Cartesian representation can be rewritten as an -tuple of series

Under the identifications , we then say that is an -representation if for all . The corresponding subspace of is an -module and the results about faithful and uniform representations extend.

Given a faithful Cartesian representation of a conical series , the dominant monomials of can be read off from the dominant monomials of . In particular, if is effective, then we have an algorithm for the computation of . In general, is not -uniform, so case separations may be necessary in order to enforce this property. As long as is not uniform, it suffices to pick a non uniform dominant coefficient of , distinguish the two cases when and , and keep computing the dominant monomials of in both cases. In a similar way as in proposition 3, it can be shown that this algorithm terminates.

Given a finite subset of monomials, the associated Newton polytope is the subset of all monomials for which there exists a strong morphism such that for all . The computation of as a function of is classical and corresponds to the computation of a convex hull. If , then we call the Newton polytope of . If is -uniform, then we call the -uniform Newton polytope of . By what precedes, and modulo case separations, we have an algorithm for the computation of the -uniform Newton polytope of . In the sequel, this algorithm will be called .

3.5.Diagonal communities and how to avoid them

Let us consider a conical series in which admits an -representation with respect to a fixed local community . Given , it is natural to ask for an -representation of the coefficient of in . Unfortunately, such an -representation does not always exist. For instance, assume that admits an -representation of the form

where , and . Then the coefficient admits a Cartesian representation

(3)

However, there is no reason for this diagonal to be in . A local community is said to be a diagonal community if it satisfies

DC

For any , the set is closed under taking diagonals

The ring of conical series with -representations in a diagonal community is closed under the extraction of coefficients with respect to .

Many classical local communities, such as the communities of algebraic or convergent power series, are actually diagonal. However, local communities are not always diagonal, and even if they are, then proving this fact may be non trivial. Fortunately, for our purpose of uniformization, we can do with a suitable approximate version of the extraction of coefficients with respect to : given , we say that is a pseudo-coefficient of in , if the set of dominant monomials of contains no monomial of the form with . In [vdH97, Section 9.4.4], we have given an algorithm for the computation of such a pseudo-coefficient .

Remark 15. The main idea behind the computation of is to hack the algorithm for the computation of a faithful -representation of by replacing all zero tests by so called diagonal tests. This idea is based on the observation that, even though we cannot compute in (3), we can check whether :

In general, denoting by the genuine coefficient of in , a similar trick may be used to test whether [vdH06, Section 9.4.2]. Using such diagonal tests for and truncations of , it then becomes possible to compute the set of dominant monomials of . The truncation yields the desired pseudo-coefficient.

4.Uniformization of conical series

In this section, we will assume that we have fixed a local community and that all conical series to be considered admit -representations. In particular, the set will correspond to instead of . All our algorithms on conical series will only rely on operations that can be performed from within the local community . Therefore, if is parametrically effective, then our algorithms also become fully effective.

The only -vector spaces over which we will work are strong vector spaces of the form . If is the canonical basis of such a vector space over , then the vectors with form a strong basis for . Given such a basis element and a vector , we denote by the coefficient of in . Similarly, if is a grid-based series, then we denote .

4.1.The Newton polygon method in dimension two

Let be a totally ordered monomial group with -powers (i.e. for any and , there exists an with ). Given a series , the solutions in to the equation

(4)

can be computed using the Newton polygon method. This method is explained in detail in [vdH06, Chapter 3] in the case when is a polynomial in and readily adapts to the case when is a power series (see [vdH06, Exercises 3.1 and 3.7]). Let us briefly recall the main definitions and results.

The series may also be regarded as a series in and its dominant coefficient in this representation is called the Newton series of . If is a polynomial, then we rather call it the Newton polynomial of . The valuation of in is called the Newton degree and we denote it by . If is infinitesimal, then the additive and multiplicative conjugates are defined by

For , this allows us to define the Newton degree associated to the “slope” by . The following properties are easy or proved in [vdH06, Chapter 3]:

Proposition 16. Given , with , with and , we have

Proposition 18. Let , , , and . Then

Moreover, if and is the unique solution to the equation

(5)

then for any non zero with dominant monomial , we have

The theory adapts with minor modifications to the case when admits its coefficients in a -vector space . In that case, we are still looking for solutions of (4) in . However, in proposition 17 it is only guaranteed that (4) admits at most solution. In particular, the equation (5) cannot necessarily be solved in proposition 18. Nevertheless, there exists a strong basis element of such that the coefficient of in has Newton degree . Then proposition 18 still holds if we take to be the solution of . Indeed, if and , then has the property that . Consequently, does not admit a root of multiplicity and neither does .

4.2.Uniform aspects of the Newton polygon method

Let us now return to the case of a multivariate series . We will assume that is an ordinary coordinate in and let be the coordinates in except . In particular, and . Considering as a power series in , we may then evaluate at a point using

Now the uniform Newton degree of in is defined by

This definition extends to the case when the coordinate is just ordinary in : it suffices to replace by and an infinitesimal coordinate which satisfies no constraints. The non trivial fact that is actually finite will follow later from the possibility to uniformize . Nevertheless, the finiteness is trivially guaranteed in one particular case:

Proposition 19. Let and assume that is uniform as a series in . Denoting by the dominant coefficient of , we have

In fact, and for all with .

The properties stated in proposition 16 admit natural uniform analogues:

Proposition 20. Given , with , with and , we have

where .

For the remaining propositions 17 and 18, it is useful to define an additional concept: we say that is Newton prepared if there exist two monomials , such that admits a -uniform Newton polytope , which is contained in . If contains at least two elements, then there exist unique , and with . We will call the principal coordinate for and its associated slope. If, moreover, we have , then we say that is -Newton prepared, with associated Newton polynomial . Notice that proposition 19 applies as soon as .

Proof. This is a direct application of [vdH06, Theorem 3.3 and Exercise 3.1].

Proposition 21 is not good enough though, since the unique solution may depend on . Consequently, we will have to replace by the coefficient of in . Unless is a diagonal community, we have no means to compute this coefficient. In practice, we therefore rather compute a pseudo-coefficient in , which we will denote by .

Proposition 22. Assume that is -Newton prepared, with slope and Newton polynomial . Let be uniform with dominant term . Then

Moreover, in the case when , let be a strong basis element for such that , and assume that , where satisfies

Assume that is -Newton prepared, with slope , and let be uniform, with dominant monomial . If is -Newton prepared, then

Proof. The first assertion follows directly from the first assertion of proposition 18. As to the second assertion, let be the monomial, such that the dominant monomials of are with . Then the dominant monomials of are with . Writing , the definition of pseudo-coefficients states that each dominant monomial of depends on at least one of the coordinates . Now

Since

it follows that the unique dominant monomial of is a dominant monomial of . In other words, must be a dominant monomial of , even though is free from . This contradiction completes the proof.

4.3.Polarization

A first useful subalgorithm which we will need is polarization. Given an arbitrary monomial , we will frequently have to decide whether , or . In general, it may happen that none of these conditions are satisfied globally on . In such cases, we will use polarization in order to decompose into at most three subregions, such that on each subregion we have either , or .

Now the subregions where and simply correspond to the imposition of the corresponding asymptotic constraints. In the remaining case, we write with and . For a new invertible parameter , and modulo a suitable ramification, it then suffices to perform the refinement with .

4.4.Newton preparation

In section 4.2, we have seen the usefulness of Newton prepared series. Assuming that we have an algorithm for the uniformization of series in at most variables, we will now present an algorithm for the Newton preparation of a series. Our algorithm assumes given an ordinary coordinate and will only use refinements in the remaining coordinates . Hence, the refinements never involve , although they may involve . If does not become uniform after the preparation, then it should be noticed that the principal coordinate of may satisfy .

The algorithm for performing the Newton preparation is quite straightforward. We first uniformize as a series in and let . Writing as a series in , the tail will then be uniform. After uniformizing the remaining coefficients , it follows that the Newton polytope of has the form , with and . Now a sufficient condition for to be Newton prepared is that all the slopes are pairwise comparable for . This is forced using polarization, where we notice that only refinements which do not involve are needed.

4.5.Blowing up edges

Assume now that is Newton prepared, but not uniform, and let be its principal coordinate with slope . At this point, we might in principle proceed by polarizing . However, in order to force a strict decrease of the Newton degree (using proposition 22), we have to slightly modify the procedure for polarization and introduce a new case for handling the situation when the Newton polynomial has non zero roots of maximal multiplicity . In this new case, which will only be needed if is an ordinary coordinate in (see also remark 23 below), we apply a Tschirnhausen transformation.

In the last step of 4, the subalgorithm computes a pseudo-coefficient of in . In addition, modulo additional refinements and recursive calls of , we enforce the difference to be uniform. This will ensure that the keeps its status of being a pseudo-coefficient, even after subsequent refinements of . In the exceptional case that one of the coordinates is refined during the uniformization of , we do not require to be uniform on exit. Let us finally notice that, in the case when is an effective diagonal community, we may simply take to be the genuine coefficient of in .

4.6.Uniformization

We are now in a position to state the main algorithm for the uniformization of . As long as is not uniform, we keep Newton preparing and blowing up the resulting edge until becomes uniform. If no ordinary coordinate exists, then we perform a sequence of suitable polarizations which will either make uniform or induce a refinement which makes one of the coordinates ordinary.

Remark 23. We do not know of any effective test whether a given coordinate is ordinary in . For this reason, we will use a slightly weaker test. For every series , we maintain a set of coordinates which are ensured to be ordinary for , and simply check whether is in this set. Whenever is refined, we add to . The coordinate is removed from , whenever an -refinement or occurs, where and or is not ordinary in . Our slightly weaker test is still sufficient for making the termination proof below work.

Proof. The algorithm is clearly correct. Let us first prove the termination modulo the termination of the subalgorithm . Assume for contradiction that it does not terminate on a given input , but that each of its recursive invocations for lower dimensional series terminates.

We observe that all coordinates cannot indefinitely remain non ordinary. Indeed, the polarizations in the second part either strictly reduce the number of elements in or end up by refining one of the coordinates, thereby making it ordinary in .

Let be maximal such that the coordinate is refined infinitely many times. Modulo picking up the computation at a later point, we may assume without loss of generality that the coordinates are never refined (although new asymptotic constraints may be imposed upon them). After one refinement of , the coordinate will then remain ordinary in .

Consider the series expansion of in after a call of . Then each of the coefficients for which is uniform. In particular, if is not uniform, then contains at least two elements whose exponents in differ. Consequently, the principal coordinate for satisfies . We claim that we cannot have . Otherwise, necessarily falls in a case which results in the uniformization of , since the coordinate is never refined. After return, the main algorithm then terminates.

Consequently, we are infinitely often in the situation that is called with as the principal coordinate of . By proposition 22, the Newton degree at least decreases by one for every two such calls. Since , this cannot happen infinitely many times. This contradiction proves the termination of modulo the termination of .

To complete the proof, let us consider one of the recursive calls and prove its termination. Without loss of generality, we may assume that none of the coordinates is refined during the recursive calls of . Intuitively speaking, the termination of is equivalent to the termination of , interspersed with a sequence of additional refinements.

More precisely, assume that the loop does not terminate. In a similar way as above, let be maximal such that is refined infinitely many times. Without loss of generality, we may assume that remains ordinary in . At each recursive call of , each of the dominant monomials of involves one of the coordinates . At the first subsequent call of , it follows that the dominant edge of is actually a dominant edge of . Now in a similar way as above, it occurs infinitely often that is the principal coordinate of (and thus of ) for this call. But then decreases every two such calls, which leads to the desired contradiction.

Acknowledgment. We are grateful to Jean-Philippe Rolin, for his careful reading of successive versions of this manuscript and many useful discussions on the subject.

Bibliography