Table of Contents

Foreword

Transseries find their origin in at least three different areas of mathematics: analysis, model theory and computer algebra. They play a crucial role in Écalle's proof of Dulac's conjecture, which is closely related to Hilbert's 16-th problem.

I personally became interested in transseries because they provide an excellent framework for automating asymptotic calculus. While developing several algorithms for computing asymptotic expansions of solutions to non-linear differential equations, it turned out that still a lot of theoretical work on transseries had to be done. This led to part A of my thesis. The aim of the present book is to make this work accessible for non-specialists. The book is self-contained and many exercises have been included for further studies. I hope that it will be suitable for both graduate students and professional mathematicians. In the later chapters, a very elementary background in differential algebra may be helpful.

The book focuses on that part of the theory which should be of common interest for mathematicians working in analysis, model theory or computer algebra. In comparison with my thesis, the exposition has been restricted to the theory of grid-based transseries, which is sufficiently general for solving differential equations, but less general than the well-based setting. On the other hand, I included a more systematic theory of “strong linear algebra”, which formalizes computations with infinite summations. As an illustration of the different techniques in this book, I also added a proof of the “differential intermediate value theorem”.

I have chosen not to include any developments of specific interest to one of the areas mentioned above, even though the exercises occasionally provide some hints. People interested in the accelero-summation of divergent transseries are invited to read Écalle's work. Part B of my thesis contains effective counterparts of the theoretical algorithms in this book and work is in progress on the analytic counterparts. The model theoretical aspects are currently under development in a joint project with Matthias Aschenbrenner and Lou van den Dries.

The book in its present form would not have existed without the help of several people. First of all, I would like to thank Jean Écalle, for his support and many useful discussions. I am also indoubted to Lou van den Dries and Matthias Aschenbrenner for their careful reading of several chapters and their corrections. Last, but not least, I would like to thank Sylvie for her patience and aptitude to put up with an ever working mathematician.

We finally notice that the present book has been written and typeset using the GNU TeXmacs scientific text editor. This program can be freely downloaded from http://www.texmacs.org.

Introduction

The field with no escape

A transseries is a formal object, constructed from the real numbers and an infinitely large variable , using infinite summation, exponentiation and logarithm. Examples of transseries are:

As the examples suggest, transseries are naturally encountered as formal asymptotic solutions of differential or more general functional equations. The name “transseries” therefore has a double signification: transseries are generally transfinite and they can model the asymptotic behaviour of transcendental functions.

Whereas the transseries (1), (2), (3), (6) (7) and (8) are convergent, the other examples (4) and (5) are divergent. Convergent transseries have a clear analytic meaning and they naturally describe the asymptotic behaviour of their sums. These properties surprisingly hold in the divergent case as well. Roughly speaking, given a divergent series

like (4), one first applies the formal Borel transformation

If this Borel transform can be analytically continued on , then the inverse Laplace transform can be applied analytically:

The analytic function obtained admits as its asymptotic expansion. Moreover, the association preserves the ring operations and differentiation. In particular, both and satisfy the differential equation

Consequently, we may consider as an analytic realization of . Of course, the above example is very simple. Also, the success of the method is indirectly ensured by the fact that the formal series has a “natural origin” (in our case, satisfies a differential equation). The general theory of accelero-summation of transseries, as developed by Écalle [É92, É93], is far more complex, and beyond the scope of this book. Nevertheless, it is important to remember that such a theory exists: even though the transseries studied in this this book are purely formal, they generally correspond to genuine analytic functions.

The attentive reader may have noticed another interesting property which is satisfied by some of the transseries (1–8) above: we say that a transseries is grid-based, if

GB1

There exists a finite number of infinitesimal “transmonomials”, such that is a multivariate Laurent series in :

GB2

The property GB1 is recursively satisfied when replacing by the logarithm of one of the .

The examples (1–5) are grid-based. For instance, for (2), we may take and . The examples (6–8) are not grid-based, but only well-based. The last example even cannot be expanded w.r.t. a finitely generated asymptotic scale with powers in . As we will see in this book, transseries solutions to algebraic differential equations with grid-based coefficients are necessarily grid-based as well. This immediately implies that the examples (6–8) are differentially transcendental over (see also [GS91]). The fact that grid-based transseries may be considered as multivariate Laurent series also makes them particularly useful for effective computations. For these reasons, we will mainly study grid-based transseries in this book, although generalizations to the well-based setting will be indicated in the exercises.

The resolution of differential and more general equations using transseries presupposes that the set of transseries has a rich structure. Indeed, the transseries form a totally ordered field (chapter 4), which is real closed (chapter 3), and stable under differentiation, integration, composition and functional inversion (chapter 5). More remarkably, it also satisfies the differential intermediate value property:

In particular, any algebraic differential equation of odd degree over , like

admits a solution in . In other words, the field of transseries is the first concrete example of what one might call a “real differentially closed field”.

The above closure properties make the field of transseries ideal as a framework for many branches of mathematics. In a sense, it has a similar status as the field of real or complex numbers. In analysis, it has served in Écalle's proof of Dulac's conjecture — the best currently known result on Hilbert's 16-th problem. In model theory, it can be used as a natural model for many theories (reals with exponentiation, ordered differential fields, etc.). In computer algebra, it provides a sufficiently general formal framework for doing asymptotic computations. Furthermore, transseries admit a rich non-archimedean geometry and surprising connections exist with Conway's “field” of surreal numbers.

Historical perspectives

Historically speaking, transseries have their origin in several branches of mathematics, like analysis, model theory, computer algebra and non-archimedean geometry. Let us summarize some of the highlights of this interesting history.

1Resolution of differential equations by means of power series

It was already recognized by Newton that formal power series are a powerful tool for the resolution of differential equations [New71]. For the resolution of algebraic equations, he already introduced Puiseux series and the Newton polygon method, which will play an important role in this book. During the 18-th century, formal power series were used more and more systematically as a tool for the resolution of differential equations, especially by Euler.

However, the analytic meaning of a formal power series is not always clear. On the one hand side, convergent power series give rise to germs which can usually be continued analytically into multi-valued functions on a Riemann surface. Secondly, formal power series can be divergent and it is not clear a priori how to attach reasonable sums to them, even though several recipes for doing this were already known at the time of Euler [Har63, Chapter 1].

With the rigorous formalization of analysis in the 19-th century, criteria for convergence of power series were studied in a more systematic way. In particular, Cauchy and Kovalevskaya developed the well-known majorant method for proving the convergence of power series solutions to certain partial differential equations [vK75]. The analytic continuation of solutions to algebraic and differential equations were also studied in detail [Pui50, BB56] and the Newton polygon method was generalized to differential equations [Fin89].

However, as remarked by Stieltjes [Sti86] and Poincaré [Poi93, Chapître 8], even though divergent power series did not fit well in the spirit of “rigorous mathematics” of that time, they remained very useful from a practical point of view. This raised the problem of developing rigorous analytic methods to attach plausible sums to divergent series. The modern theory of resummation started with Stieltjes, Borel and Hardy [Sti94, Sti95, Bor28], who insisted on the development of summation methods which are stable under the common operations of analysis. Although the topic of divergent series was an active subject of research in the early 20-th century [Har63], it went out of fashion later on.

2Generalized asymptotic scales

Another approach to the problem of divergence is to attach only an asymptotic meaning to series expansions. The foundations of modern asymptotic calculus were laid by Dubois-Raymond, Poincaré and Hardy.

More general asymptotic scales than those of the form , or were introduced by Dubois-Raymond [dBR75, dBR77], who also used “Cantor's” diagonal argument in order to construct functions which cannot be expanded with respect to a given scale. Nevertheless, most asymptotic scales occurring in practice consist of so called -functions, which are constructed from algebraic functions, using the field operations, exponentiation and logarithm. The asymptotic properties of -functions were investigated in detail by Hardy [Har10, Har11] and form the start of the theory of Hardy fields [Bou61, Ros80, Ros83a, Ros83b, Ros87, Bos81, Bos82, Bos87].

Poincaré [Poi90] also established the equivalence between computations with formal power series and asymptotic expansions. Generalized power series with real exponents [LC93] or monomials in an abstract monomial group [Hah07] were introduced about the same time. However, except in the case of linear differential equations [Fab85, Poi86, Bir09], it seems that nobody had the idea to use such generalized power series in analysis, for instance by using a monomial group consisting of -functions.

Newton, Borel and Hardy were all aware of the systematic aspects of their theories and they consciously tried to complete their framework so as to capture as much of analysis as possible. The great unifying theory nevertheless had to wait until the late 20-th century and Écalle's work on transseries and Dulac's conjecture [É85, É92, É93, Bra91, Bra92, CNP93].

His theory of accelero-summation filled the last remaining source of instability in Borel's theory. Similarly, the “closure” of Hardy's theory of -functions under infinite summation removes its instability under functional inversion (see exercise 5.20) and the resolution of differential equations. In other words, the field of accelero-summable transseries seems to correspond to the “framework-with-no-escape” about which Borel and Hardy may have dreamed.

3Model theory

Despite the importance of transseries in analysis, the first introduction of the formal field of transseries appeared in model theory [Dah84, DG86]. Its roots go back to another major challenge of 20-th century mathematics: proving the completeness and decidability of various mathematical theories.

Gödel's undecidability theorem and the undecidability of arithmetic are well-known results in this direction. More encouraging were the results on the theory of the field of real numbers by Artin-Schreier and later Tarski-Seidenberg [AS26, Tar31, Tar51, Sei54]. Indeed, this theory is complete, decidable and quantifier elimination can be carried out effectively. Tarski also raised the question how to axiomatize the theory of the real numbers with exponentiation and to determine its decidability. This motivated the model-theoretical introduction of the field of transseries as a good candidate of a non-standard model of this theory, and new remarkable properties of the real exponential function were stated.

The model theory of the field of real numbers with the exponential function has been developed a lot in the nineties. An important highlight is Wilkie's theorem [Wil96], which states that the real numbers with exponentiation form an o-minimal structure [vdD98, vdD99]. In these further developments, the field of transseries proved to be interesting for understanding the singularities of real functions which involve exponentiation.

After the encouraging results about the exponential function, it is tempting to generalize the results to more general solutions of differential equations. Several results are known for Pfaffian functions [Kho91, Spe99], but the thing we are really after is a real and/or asymptotic analogue of Ritt-Seidenberg's elimination theory for differential algebra [Rit50, Sei56, Kol73]. Again, it can be expected that a better understanding of differential fields of transseries will lead to results in that direction; see [AvdD02, AvdD01, AvdD04, AvdDvdH05, AvdDvdH] for ongoing work.

4Computer algebra and automatic asymptotics

We personally became interested in transseries during our work on automatic asymptotics. The aim of this subject is to effectively compute asymptotic expansions for certain explicit functions (such as “exp-log” function) or solutions to algebraic, differential, or more general equations.

In early work on the subject [GG88, Sha90, GG92, Sal91, Gru96, Sha04], considerable effort was needed in order to establish an appropriate framework and to prove the asymptotic relevance of results. Using formal transseries as the privileged framework leads to considerable simplifications: henceforth, with Écalle's accelero-summation theory in the background, one can concentrate on the computationally relevant aspects of the problem. Moreover, the consideration of transfinite expansions allows for the development of a formally exact calculus. This is not possible when asymptotic expansions are restricted to have at most terms and difficult in the framework of nested expansions [Sha04].

However, while developing algorithms for the computation of asymptotic expansions, it turned out that the mathematical theory of transseries still had to be further developed. Our results in this direction were finally regrouped in part A of our thesis, which has served as a basis for this book. Even though this book targets a wider public than the computer algebra community, its effective origins remain present at several places: Cartesian representations, the incomplete transbasis theorem, the Newton polygon method, etc.

5Non-archimedean geometry

Last but not least, the theory of transseries has a strong geometric appeal. Since the field of transseries is a model for the theory of real numbers with exponentiation, it is natural to regard it as a non-standard version of the real line. However, contrary to the real numbers, the transseries also come with a non-trivial derivation and composition. Therefore, it is an interesting challenge to study the geometric properties of differential polynomials, or more general “functions” constructed using the derivation and composition. The differential intermediate value theorem can be thought of as one of the first results in this direction.

An even deeper subject for further study is the analogy with Conway's construction of the “field” of surreal numbers [Con76]. Whereas the surreal numbers come with the important notion of “earliness”, transseries can be differentiated and composed. We expect that it is actually possible to construct isomorphisms between the class of surreal numbers and the class of generalized transseries of the reals with so called transfinite iterators of the exponential function and nested transseries. A start of this project has been carried out in collaboration with my former student M. Schmeling [Sch01]. If this project could be completed, this would lead to a remarkable correspondence between growth-rate functions and numbers.

Outline of the contents

Orderings occur in at least two ways in the theory of transseries. On the one hand, the terms in the expansion of a transseries are naturally ordered by their asymptotic magnitude. On the other hand, we have a natural ordering on the field of transseries, which extends the ordering on . In chapter 1, we recall some basic facts about well-quasi-orderings and ordered fields. We also introduce the concept of “asymptotic dominance relations” , which can be considered as generalizations of valuations. In analysis, and are alternative notations for and .

In chapter 2, we introduce the “strong -algebra of grid-based series” , where is a so called monomial monoid with a partial quasi-ordering . Polynomials, ordinary power series, Laurent series, Puiseux series and multivariate power series are all special types of grid-based series. In general, grid-based series carry a transfinite number of terms (even though the order is always bounded by ) and we study the asymptotic properties of .

We also lay the foundations for linear algebra with an infinitary summation operator, called “strong linear algebra”. Grid-based algebras of the form , Banach algebras and completions with respect to a valuation are all examples of strong algebras, but we notice that not all strong “serial” algebras are of a topological nature. One important technique in the area of strong linear algebra is to make the infinite sums as large as possible while preserving summability. Different regroupings of terms in such “large sums” can then be used in order to prove identities, using the axiom of “strong associativity”. The terms in “large sums” are often indexed by partially ordered grid-based sets. For this reason, it is convenient to develop the theory of grid-based series in the partially ordered setting, even though the ordering on transmonomials will be total.

The Newton polygon method is a classical technique for the resolution of algebraic equations with power series coefficients. In chapter 3, we will give a presentation of this method in the grid-based setting. Our exposition is based on the systematic consideration of “asymptotic equations”, which are equations with asymptotic side-conditions. This has the advantage that we may associate invariants to the equation like the Newton degree, which simplifies the method from a technical point of view. We also systematically consider derivatives of the equation, so as to quickly separate almost multiple roots.

Chapter 3 also contains a digression on Cartesian representations, which are both useful from a computational point of view and for the definition of convergence. However, they will rarely be used in the sequel, so this part may be skipped at a first reading.

In chapter 4, we construct the field of grid-based transseries in over an “ordered exp-log field” of constants . Axioms for such constant fields and elementary properties are given in section 4.1. In practice, one usually takes . In computer algebra, one often takes the countable subfield of all “real elementary constants” [Ric97]. It will be shown that is again an ordered exp-log field, so it is also possible to take and construct fields like . Notice that our formalism allows for partially defined exponential functions. This is both useful during the construction of and for generalizations to the multivariate case.

The construction of proceeds by the successive closure of under logarithm and exponentiation. Alternatively, one may first close under exponentiation and next under logarithm, following Dahn and Göring or Écalle [DG86, É92]. However, from a model-theoretical point of view, it is more convenient to first close under logarithm, so as to facilitate generalizations of the construction [Sch01]. A consequence of the finiteness properties which underlie grid-based transseries is that they can always be expanded with respect to finite “transbases”. Such representations, which will be studied in section 4.4, are very useful from a computational point of view.

In chapter 5, we will define the operations and on and prove that they satisfy the usual rules from calculus. In addition, they satisfy several compatibility properties with the ordering, the asymptotic relations and infinite summation, which are interesting from a model-theoretical point of view. In section 5.4.2, we also prove the Translagrange theorem due to Écalle, which generalizes Lagrange's well-known inversion formula for power series.

Before going on with the study of differential equations, it is convenient to extend the theory from chapter 2 and temporarily return to the general setting of grid-based series. In chapter 6, we develop a “functional analysis” for grid-based series, based on the concept of “grid-based operators”. Strongly multilinear operators are special cases of grid-based operators. In particular, multiplication, differentiation and integration of transseries are grid-based operators. General grid-based operators are of the form

where each is a strongly -linear operator. The set of grid-based operators from into forms a strong -vector space, which admits a natural basis of so called “atomic operators”. At the end of chapter 6, we prove several implicit function theorems, which will be useful for the resolution of differential equations.

In chapter 7, we study linear differential equations with transseries coefficients. A well-known theorem [Fab85] states that any linear differential equation over admits a basis of formal solutions of the form

with , , and . We will present a natural generalization of this theorem to the transseries case. Our method is based on a deformation of the algebraic Newton polygon method from chapter 3.

Since the only transseries solution to is , the solution space of an equation of order does not necessarily have dimension . Nevertheless, as will be shown in section 7.7, one does obtain a solution space of dimension by considering an oscillatory extension of the field of transseries. A remarkable consequence is that linear differential operators can be factored into first order operators in this extension. It will also be shown that operators in can be factored into first and second order operators.

It should also be noticed that the theory from chapter 7 is compatible with the strong summation and asymptotic relations on . First of all, the trace of a linear differential operator , which describes the dominant asymptotic behaviour of , satisfies several remarkable properties (see section 7.3.3). Secondly, any operator admits a so called distinguished strong right-inverse , with the property that when is the dominant monomial of a solution to . Similarly, we will construct distinguished bases of solutions and distinguished factorizations.

Non-linear differential equations are studied in chapter 8. For simplicity, we restrict our attention to asymptotic algebraic differential equations like

with , but similar techniques apply in more general cases. The generalization of the Newton polygon method to the differential setting contains two major difficulties. First, the “slopes” which lead to the first terms of solutions cannot directly be read off from the Newton polygon. Moreover, such slopes may be due to cancellations of terms of different degrees (like in the usual case) or terms of the same degree. Secondly, it is much harder to “unravel” almost multiple solutions.

In order to circumvent the first problem, we first define the differential Newton polynomial associated to the “horizontal slope” (it actually turns out that is always of the form with ). Then the slope which corresponds to solutions of the form is “admissible” if and only if admits a non-zero root in . Here is the unique differential polynomial with for all . In section 8.4, we next give a procedure for determining the admissible slopes. The second problem is more pathological, because one has to ensure the absence of iterated logarithms with arbitrarily high in the expansions of solutions. This problem is treated in detail in section 8.6.

The suitably adapted Newton polygon methods allows us to prove several structure theorems about the occurrence of exponentials and logarithms into solutions of algebraic differential equation. We also give a theoretical algorithm for the determination of all solutions.

The last chapter of this book is devoted to the proof the intermediate value theorem for differential polynomials . This theorem ensures the existence of a solution to on an interval under the simple hypothesis that admits a sign-change on . The main part of the chapter contains a detailed study of the non-archimedean geometry of . This comprises a classification of its “cuts” and a description of the behaviour of differential polynomials in cuts. In the last section, this theory is combined with the results of chapter 8, and the interval on which a sign-change occurs is shrunk further and further until we hit a root of .

Notations

A few remarks about the notations used in this book will be appropriate. Notice that a glossary can be found at the end.

1. Given a mapping and , we write

   

   Similarly, given a set , we will write or if resp. for all . These and other classical notations for sets are extended to families in section 2.4.1.

2. We systematically use the double index convention . Given a set of monomials, we also denote (this is an exception to the above notation).
3. Given a set , we will denote by its subset of strictly positive elements, its subset of bounded elements, of negative infinitesimal elements, etc. If is a set of series, then we also denote , where , and similarly for , , etc. Notice that this is really a special case of notations 1 and 2.
4. Intervals are denoted by , , or depending on whether the left and right sides are open or closed.
5. We systematically denote monomials in the fraktur font and families using calligraphic characters.

Those readers who are familiar with my thesis should be aware of the following notational changes which occurred during the past years:

There are also a few changes in terminology:

Former	New
normal basis	transbasis
purely exponential transseries	exponential transseries
potential dominant —	starting —
privileged refinement	unravelling

In this chapter, we will introduce some order-theoretical concepts, which prepare the study of generalized power series in the next chapter. Orderings occur in at least two important ways in this study.

First, the terms of a series are naturally ordered according to their asymptotic magnitudes. For instance, the support of , considered as an ordered set, is isomorphic to . More interesting examples are

and

whose supports are isomorphic to and respectively. Here denotes the set with the total anti-lexicographical ordering

and denotes the set with the partial product ordering

In general, when the support is totally ordered, it is natural to require the support to be well-ordered. If we want to be able to multiply series, this condition is also necessary, as shown by the example

For convenience, we recall some classical results about well-ordered sets and ordinal numbers in section 1.2. In what follows, our treatment will be based on well-quasi-orderings, which are the analogue of well-orderings in the context of partial quasi-orderings. In sections 1.3 and 1.4, we will prove some classical results about well-quasi-orderings.

A second important occurrence of orderings is when we consider an algebra of generalized power series as an ordered structure. For instance is naturally ordered by declaring a non-zero series with to be positive if and only if . This gives the structure of a so called totally ordered -algebra.

In section 1.5, we recall the definitions of several types of ordered algebraic structures. In section 1.6, we will then show how a certain number of typical asymptotic relations, like , , and , can be introduced in a purely algebraic way. In section 1.8, we define groups and fields with generalized exponentiations, and the asymptotic relations , and . Roughly speaking, for infinitely large and , we have , if for all . For instance, , but , for .

1.1Quasi-orderings

Let be a set. In all what follows, a quasi-ordering on is reflexive and transitive relation on ; in other words, for all we have

O1

;

O2

.

An ordering is a quasi-ordering which is also antisymmetric:

O3

.

We sometimes write instead of in order to avoid confusion. A mapping between two quasi-ordered sets is said to be increasing (or a morphism of quasi-ordered sets), if , for all .

Given a quasi-ordering , we say that are comparable if or . If every two elements in are comparable, then the quasi-ordering is said to be total. Two elements are said to be equivalent, and we write , if and . If and , then we write (see also exercise 1.1(a) below). The quasi-ordering on induces a natural ordering on the quotient set by and the corresponding projection is increasing. In other words, we do not really gain in generality by considering quasi-orderings instead of orderings, but it is sometimes more convenient to deal with quasi-orderings.

Some simple examples of totally ordered sets are and . Any set can be trivially quasi-ordered both by the finest ordering, for which , and by the roughest quasi-ordering, for which all satisfy . In general, a quasi-ordering on is said to be finer than a second quasi-ordering on if for all . Given quasi-ordered sets and , we can construct other quasi-ordered sets as follows:

1. The disjoint union is naturally quasi-ordered, by taking the quasi-orderings on and on each summand, and by taking and mutually incomparable. In other words,

   

2. Alternatively, we can quasi-order , by postulating any element in to be strictly smaller than any element in . This quasi-ordered set is called the ordered union of and , and we denote it by . In other words,

   

3. The Cartesian product is naturally quasi-ordered by

   

4. Alternatively, we can quasi-order anti-lexicographically by

   

   We write for the corresponding quasi-ordered set.

Fig. 1.1. Examples of some basic constructions on ordered sets.

1. Let be the set of words over . Such words are denoted by sequences (with ) or if confusion may arise. The empty word is denoted by and we define . The embeddability quasi-ordering on is defined by , if and only if there exists a strictly increasing mapping , such that for all . For instance,

   

2. An equivalence relation on is said to be compatible with the quasi-ordering if

   

   for all . In that case, is naturally quasi-ordered by

   

   and the canonical projection is increasing.

If and are ordered sets, then it can be verified that the quasi-orderings defined in 1–6 above are actually orderings.

Let be an increasing mapping between quasi-ordered sets and . Consider the quasi-ordering on defined by

Then is finer than and the mapping admits a natural factorization

(1.1)

Here is the identity on composed with the natural projection from on , is the natural inclusion of into and is an isomorphism.

Prove that defines an ordering on . Also prove the following properties:

1.2Ordinal numbers

Let be a quasi-ordered set. The quasi-ordering on is said to be well-founded, if there is no infinite strictly decreasing sequence in . A total well-founded ordering is called a well-ordering. A total ordering is a well-ordering if and only if each of its non-empty subsets has a least element. The following classical theorems are implied by the axiom of choice [Bou70, Mal79]:

Theorem 1.1.

Theorem 1.2.

(Zorn's lemma) Let be a non-empty ordered set, such that each non-empty totally ordered subset of has an upper bound. Then admits a maximal element.

An ordinal number or ordinal is a set , such that the relation forms a strict well-ordering on . In particular, the natural numbers can “be defined to be” ordinal numbers: . The set of natural numbers is also an ordinal. More generally, if is an ordinal, then so is . For all ordinals , its elements are also ordinals.

Fig. 1.2. Some examples of ordinal numbers.

It is classical [Mal79] that the class of all ordinal numbers has all the properties of an ordinal number: if and are ordinal numbers, then and each non-empty set of ordinals admits a least element for . The following classification theorem is also classical [Mal79]:

Theorem 1.3.

The usual induction process for natural numbers admits an analogue for ordinal numbers. For this purpose, we distinguish between successor ordinals and limit ordinals: an ordinal is called a successor ordinal if for some ordinal (and we write ) and a limit ordinal if not (in which case ). For example, the inductive definitions for addition, multiplication and exponentiation can now be extended to ordinal numbers as follows:

Table 1.1. Basic arithmetic on ordinal numbers.

Similarly, one has the transfinite induction principle: assume that a property for ordinals satisfies for all and for all limit ordinals . Then holds for all ordinals .

The following theorem classifies all countable ordinals smaller than , and is due to Cantor [Can99]:

Theorem 1.4. Let be a countable ordinal. Then there exists a unique sequence of natural numbers (with if ), such that

1.3Well-quasi-orderings

Let be a quasi-ordered set. A chain in is a subset of which is totally ordered for the induced quasi-ordering. An anti-chain is a subset of of pairwise incomparable elements. A well-quasi-ordering is a well-founded quasi-ordering without infinite anti-chains.

A final segment is a subset of , such that , for all . Given an arbitrary subset of , we denote by

the final segment generated by . Dually, an initial segment is a subset of , such that , for all . We denote by

the initial segment generated by .

Proposition 1.5. Let be a quasi-ordered set. Then the following are equivalent:

1. is well-quasi-ordered.
2. Any final segment of is finitely generated.
3. The ascending chain condition w.r.t. inclusion holds for final segments of .
4. Each sequence admits an increasing subsequence.
5. Any extension of the quasi-ordering on to a total quasi-ordering on yields a well-founded quasi-ordering.

Proof. Assume (a) and let be a final segment of and the subset of minimal elements of . Then is an anti-chain, whence finite. We claim that generates . Indeed, in the contrary case, let . Since is not minimal in , there exists an with . Repeating this argument, we obtain an infinite decreasing sequence . This proves (b). Conversely, if is an infinite anti-chain or an infinite strictly decreasing sequence, then the final segment generated by is not finitely generated. This proves (a)(b).

Now let be an ascending chain of final segments. If the final segment is finitely generated, say by , then we must have , for some . This shows that (b)(c). Conversely, let be the set of minimal elements of a final segment . If ,... are pairwise distinct elements of , then forms an infinite strictly ascending chain of final segments.

Now consider a sequence of elements in , and assume that is a well-quasi-ordering. We extract an increasing sequence from it by the following procedure: Let be the final segment generated by the , with and ( by convention) and assume by induction that the sequence contains infinitely many terms in . Since is finitely generated by (b), we can select a generator , with and such that the sequence contains infinitely many terms in . This implies (d). On the other hand, it is clear that it is not possible to extract an increasing sequence from an infinite strictly decreasing sequence or from a sequence of pairwise incomparable elements.

Let us finally prove (a)(e). An ordering containing an infinite anti-chain or an infinite strictly decreasing sequence can always be extended to a total quasi-ordering which contains a copy of , by a straightforward application of Zorn's lemma. Inversely, any extension of a well-quasi-ordering is a well-quasi-ordering.

The most elementary examples of well-quasi-orderings are well-orderings and quasi-orderings on finite sets. Other well-quasi-orderings can be constructed as follows.

Proposition 1.6. Assume that and are well-quasi-ordered sets. Then

1. Any subset of with the induced ordering is well-quasi-ordered.
2. Let be a morphism of ordered sets. Then is well-quasi-ordered.
3. Any ordering on which extends is a well-quasi-ordering.
4. is well-quasi-ordered, for any compatible equivalence relation on .
5. and are well-quasi-ordered.
6. and are well-quasi-ordered.

Corollary 1.7.

(Dickson's lemma) For each , the set with the partial, componentwise ordering is a well-quasi-ordering.

Theorem 1.8. (Higman) Let is be a well-quasi-ordered set. Then is a well-quasi-ordered set.

Proof. Our proof is due to Nash-Williams [NW63]. If denotes any ordering, then we say that is a bad sequence, if there do not exist with . A quasi-ordering is a well-quasi-ordering, if and only if there are no bad sequences.

Now assume for contradiction that is a bad sequence for . Without loss of generality, we may assume that each was chosen such that the length (as a word) of were minimal, under the condition that

We say that is a minimal bad sequence.

Now for all , we must have , so we can factor , where is the first letter of . By proposition 1.5(d), we can extract an increasing sequence from . Now consider the sequence

By the minimality of , this sequence is good. Hence, there exist with . But then,

which contradicts the badness of .

1.4Kruskal's theorem

An unoriented tree is a finite set of nodes with a partial ordering , such that admits a minimal element , called the root of , and such that each other node admits a predecessor. Given , we recall that is a predecessor of (and a successor of ) if and for any with . A node without successors is called a leaf. Any node naturally induces a subtree with root . Since is finite, an easy induction shows that any two nodes of admit an infimum w.r.t. , for which , and for all with and .

An oriented tree (or simply tree) is an unoriented tree , together with a total ordering which extends and which satisfies the condition

It is not hard to see that such a total ordering is uniquely determined by its restrictions to the sets of -successors for each node .

Two unoriented or oriented trees and will be understood to be equal if there exists a bijection which preserves resp. and . In particular, under this identification, the sets of unoriented and oriented trees are countable.

Given a set , an -labeled tree is a tree together with a labeling . We denote by the set of such trees. An -labeled tree may be represented graphically by

(1.2)

where and are the subtrees associated to the successors of . We call the children of the root and its arity. Notice that we may have .

Example 1.9. We may see usual trees as -labeled trees, where is the set with one symbolic element . The difference between unoriented and oriented trees is that the ordering on the branches is important. For instance, the two trees below are different as oriented trees, but the same as unoriented trees:

If is a quasi-ordered set, then the embeddability quasi-ordering on is defined by , if and only if there exists a strictly increasing mapping for , such that , and , for all . An example of a tree which embeds into another tree is given by

The following theorem is known as Kruskal's theorem:

Theorem 1.10. If is a well-quasi-ordered set, then so is .

Proof. Assume that there exists a bad sequence . We may assume that we have chosen each

of minimal cardinality (assuming that have already been fixed), i.e. is a “minimal bad sequence”. We claim that the induced quasi-ordering on is a well-quasi-ordering. Indeed, suppose the contrary, and let

be a bad sequence. Let be such that is minimal. Then the sequence

is also bad, which contradicts the minimality of . Hence, is well-quasi-ordered, and so is , by Higman's theorem and proposition 1.6(f). But each tree can be interpreted as an element of . Hence, is a well-quasi-ordered subset of , which contradicts our assumption that is a bad sequence.

Remark 1.11. In the case when we restrict ourselves to trees of bounded arity, the above theorem was already due to Higman. The general theorem was first conjectured by Vázsonyi. The proof we have given here is due to Nash-Williams.

We say that the orderings of and are compatible, if for all , and , we have

whenever there exists an increasing mapping with for all .

1.5Ordered structures

In what follows, all monoids, groups and rings will be commutative and all rings unitary. The following ordered structures will be encountered frequently throughout this book. Recall that we systematically understand all orderings to be partial (contrary to what is customary for certain structures).

• An ordered monoid is a monoid with an ordering such that

  OM

  

  for all . If is rather an additive monoid (in which case is assumed to be abelian), then OM becomes

  OA

  .

• An ordered ring is a ring with an ordering with the following properties:

  OR1

  ;

  OR2

  ;

  OR3

  ,

  for all .

• An ordered field is a field with an ordering which makes an ordered ring and such that for all . Notice that this latter condition is automatically satisfied if is total.

• An ordered -module over an ordered ring is an -module with an ordering which satisfies

  OM1

  ;

  OM2

  ,

  for all and . Any abelian group is trivially an ordered -module.

• An ordered -algebra is a morphism of ordered rings, i.e. an increasing ring morphism of an ordered ring into an ordered ring . As usual, we denote , for and . Notice that is in particular an ordered -module. Any ordered ring is trivially an ordered -algebra.

Let be an ordered abelian group, ring, -module or -algebra. We denote

We observe that the ordering is characterized by . If is totally ordered, then we define the absolute value of by if and , if .

Example 1.12. and are the most common examples of totally ordered fields. and are respectively a totally ordered monoid and a totally ordered group. The complex numbers form an ordered abelian group when setting . However, this ordering is partial and not compatible with the multiplication. Notice that and are incomparable for and .

Example 1.13. The ring of germs at of infinitely differentiable real valued functions on intervals with can be ordered by , if there exists an , such that for all . A totally ordered subfield of this ring is called a Hardy field.

Example 1.14. The above definitions naturally generalize to the case of quasi-orderings instead of orderings. If is a quasi-ordered abelian group, then is an ordered abelian group, and similarly for quasi-ordered rings, -modules, etc.

Example 1.15. Let and be two quasi-ordered abelian groups, rings, -modules or -algebras. Their direct sum is naturally quasi-ordered by the product quasi-ordering

Similarly, the anti-lexicographical direct sum of and is with the anti-lexicographical quasi-ordering

If and are ordered, then so are and .

Example 1.16. Let and be two quasi-ordered abelian groups, rings, -modules or -algebras. Their tensor product is naturally quasi-ordered, by declaring an element of to be positive if it is a sum of elements of the form with and . Similarly, we define the anti-lexicographical tensor product : its set of positive elements is additively generated by elements in of the form , with and . If and are ordered, then the same does not necessarily hold for

1.6Asymptotic relations

Let and be two germs of real valued functions at infinity. Then we have the following classical definitions of the domination and neglection relations resp. :

Considered as relations on the -algebra of germs of real valued functions at infinity, and satisfy a certain number of easy to prove algebraic properties. In this section, we will take these properties as the axioms of abstract domination and neglection relations on more general modules and algebras.

Let be a ring and an -module. In all what follows, we denote by the set of non-zero-divisors in . A dominance relation is a quasi-ordering on , such that for all , and , we have

D1

;

D2

and .

Notice that D1 and D2 imply that is a submodule of for each . If , then we say that is dominated by , and we also write . If and , then we say that and are asymptotic, and we also write . We say that is total, if or for all .

A neglection relation is a strict ordering on (i.e. an anti-reflexive, transitive relation), such that for all and and , we have

N1

;

N2

and .

N3

.

Notice that is a submodule of if . However, this is not always the case, since . If , then we say that can be neglected w.r.t. , and we also write . If , then we also say that and are equivalent, and we write . Indeed, is an equivalence relation:

Similarly,

whence

We say that is compatible with a dominance relation , if and , for all . In that case, we call an asymptotic -module. We say that and are associated, if is the strict ordering associated to , i.e. for all .

Proposition 1.17.

1. Let be a dominance relation such that the strict ordering associated to satisfies N1 and N2. Then also satisfies N3.
2. Let and be a dominance and a neglection relation. If and are associated, then they are compatible.

Proof. Assume that satisfies the condition in (a), and let be such that and . If , then implies and : contradiction. Hence, we have and .

As to (b), assume that and are associated. Then we clearly have . Furthermore, . Similarly, . Hence, .

Proposition 1.18. Let be a totally ordered field and an ordered -vector space. Then is an asymptotic -vector space for the relations and defined by

Moreover, if is totally ordered, then is associated to .

Proof. Let us first show that is a quasi-ordering. We clearly have for all , since for all . If and , then there exists a with and a with . Let us next prove D1. Assume that and and let . Then there exist with and , whence . As to D2, let , and . Then for all , we have and .

In order to prove the remaining relations, we first notice that

Indeed, if , then there exists a with for all . In particular, , whence either (if ) or (if ). Furthermore, for all , we have , whence . Let us show that is a strict ordering. We cannot have , since . If , then we have for all .

Let us now prove N1. If , and , then and , whence . As to N2, let , and . If , then , whence . If , then and , whence . Let us finally prove N3. Assume that , and . Then implies . From it thus follows that .

Assuming that is totally ordered, the relation is associated to , since . In general, we clearly have . Furthermore, if , then both and , whence . Similarly, , so that .

If is a totally ordered ring, then cannot have zero-divisors, so its ring of quotients is a totally ordered field. Moreover, for any ordered, torsion-free -module, the natural map is an embedding. This allows us to generalize proposition 1.18 to the case of totally ordered rings.

Corollary 1.19.

Let be a totally ordered ring and an ordered, torsion-free -module. Then is an asymptotic -module for the restrictions to of the relations and on . Moreover, if is totally ordered, then is associated to .

Assume now that is an -algebra. A dominance relation on is defined to be a quasi-ordering , which satisfies D1, D2 and for all :

D3

.

A neglection relation on is a strict ordering , which satisfies N1, N2, N3, and for all and :

N4

.

An element is said to be infinitesimal, if . We say that is bounded, if (and unbounded if not). Elements with are called archimedean. If all non-zero elements of are archimedean, then is said to be archimedean itself. In particular, a totally ordered ring said to be archimedean, if it is archimedean as an ordered -algebra. If and are compatible, then we call an asymptotic -algebra.

Proposition 1.20. Let be a totally ordered ring and a non-trivial totally ordered -algebra. Define the relations and on as in corollary 1.19. Then is an asymptotic -algebra and is associated to .

Proof. Let be such that , and let . Then there exists a with . If , then we infer that , whence . If , then we obtain , whence again , by D2. This proves D3. As to N4, let be such that . Then for all , we have , whence .

Example 1.21. Let be a totally ordered -algebra. We may totally order the polynomial extension of by an infinitesimal element by setting , if and only if there exists an index with . This algebra is non-archimedean, since . Similarly, one may construct an extension with an infinitely large element , in which .

V1

for all .

V2

, for all with .

1.7Hahn spaces

Let be a totally ordered field and a totally ordered -vector space. We say that is a Hahn space, if for each with , there exists a , with .

Proposition 1.22. Let be a totally ordered field and a finite dimensional Hahn space over . Then admits a basis with .

Proof. We prove the proposition by induction over the dimension of . If , then we have nothing to prove. So assume that , and let be a hyperplane in of dimension . By the induction hypothesis, admits a basis .

We claim that there exists an , such that is asymptotic to none of the . Indeed, if not, let be minimal such that there exists an with . Since is saturated, there exists a with . Then , whence with , since . This contradicts the minimality of .

So let be such that is asymptotic to none of the . Since for all , the set is totally ordered w.r.t. .

1.8Groups and rings with generalized powers

Let be a multiplicative group. For any and , we can take the -th power of in . We say that is a group with -powers. More generally, given a ring , a group with -powers is an -module , such that acts on through exponentiation. We also say that is an exponential -module. If and are ordered, then we say that is an ordered group with -powers if , for all and .

Example 1.23. Let be any group with -powers and let be an -algebra. Then we may form the group with -powers, by tensoring the -modules and . However, there is no canonical way to order , if and are ordered.

A ring with -powers is a ring , such that a certain multiplicative subgroup of carries the structure of a group with -powers. Any ring is a ring with -powers by taking the group of units of for . If is an ordered ring, then we say that the ordering is compatible with the -power structure if

An ordered field with -powers is an ordered field , such that the ordered group of strictly positive elements in has -powers.

Example 1.24. The field is a field with -powers by taking . The field is a totally ordered field with -powers for the ordering

from example 1.13.

Let be an asymptotic ring with -powers, i.e. is both an asymptotic ring and a ring with -powers, and or for all . Given , we denote if and otherwise. Then, given , we define

and we say that is flatter than resp. flatter than or as flat as . If , then we say that is as flat as and we write . Given , the set of with is also called the comparability class of . Finally, if , then we say that and are similar modulo flatness, and we write .

Example 1.25. Consider the totally ordered field with -powers and the natural asymptotic relations and for . Then we have , and .

Let be an asymptotic ring with -powers and consider a subring with -powers such that . The subring is said to be flat if

In that case, we define

for . In virtue of the next proposition, we call a flattened dominance relation and a flattened neglection relation.

Proposition 1.26.

1. is an asymptotic ring with -powers for and .

2. If for all and we have

   (1.3)

   then and are associated.

Proof. Assume that and so that and for certain . We also have or , so, by symmetry, we may assume that . Now , whence , which proves D1. We trivially have D2, since for all . The properties D3, N1, N2, N3, N4 and the quasi-ordering properties directly follow from the corresponding properties for and .

Assume now that . Then in particular , whence and . Furthermore, if we had , then we would both have and for some , which is impossible. This proves that .

Conversely, assume that we have and , together with (1.3). Then for some and for all . Given , we then have , since otherwise . Applying (1.3) to , and , we conclude that and .

Example 1.27. Given an element , we may take to be the ring generated by all with . Then we define

We may also take , in which case we define

For instance, if , then , and for all .

Let be a commutative ring, and a quasi-ordered monomial monoid. In this chapter, we will introduce the ring of generalized power series in over . For the purpose of this book, we have chosen to limit ourselves to the study of grid-based series, whose supports satisfy a strong finiteness property. On the other hand, we allow to be partially ordered, so that multivariate power series naturally fit into our context. Let us briefly discuss these choices.

In order to define a multiplication on , we have already noticed in the previous chapter that the supports of generalized power series have to satisfy an ordering condition. One of the weakest possible conditions is that the supports be well-based and one of the strongest conditions is that the supports be grid-based. But there is a wide range of alternative conditions, which correspond to the natural origins of the series we want to consider (see exercises 2.1 and 2.7). For instance, a series like

is the natural solution to the functional equation

However, is not grid-based, whence it does not satisfy any algebraic differential equation with power series coefficients (as will be seen in chapter 8).

Actually, the setting of grid-based power series suffices for the resolution of differential equations and that is the main reason why we have restricted ourselves to this setting. Furthermore, the loss of generality is compensated by the additional structure of grid-based series. For example, they are very similar to multivariate Laurent series (as we will see in the next chapter) and therefore particularly suitable for effective purposes [vdH97]. In chapter 4, we will also show that grid-based “transseries” satisfy a useful structure theorem.

Although we might have proved most results in this book for series with totally ordered supports only, we have chosen to develop theory in a partially ordered setting, whenever this does not require much additional effort. First of all, this lays the basis for further generalizations of our results to multivariate and oscillating transseries [vdH97, vdH01a]. Secondly, we will frequently have to “fully expand” expressions for generalized series. This naturally leads to the concepts of grid-based families and strong linear algebra (see sections 2.4, 2.5.3 and 2.6), which have a very “partially-ordered” flavour. Actually, certain proofs greatly simplify when we allow ourselves to use series with partially ordered supports.

Let us illustrate the last point with a simple but characteristic example. Given a classical power series and an “infinitesimal” generalized power series , we will define their composition . In particular, when taking !, this yields a definition for the exponential of . Now given two infinitesimal series and , the proof of the equality is quite long in the totally ordered context. In the partially ordered context, on the contrary, this identity trivially follows from the fact that in the ring of multivariate power series.

2.1Grid-based sets

Let be a commutative, multiplicative monoid of monomials, quasi-ordered by . A subset is said to be grid-based, if there exist , with , and such that

(2.1)

In other words, for each monomial , there exist and with

Notice that we can always take if the ordering on is total.

By Dickson's lemma, grid-based sets are well-quasi-ordered for the opposite quasi-ordering of (carefully notice the fact that this is true for the opposite quasi-ordering of and not for itself). Actually, a grid-based set is even well-quasi-ordered for the opposite ordering of (recall that ). More generally, a subset of which has this latter property is said to be well-based.

Proposition 2.1. Let and be grid-based subsets of . Then

1. Each finite set is grid-based.
2. is grid-based.
3. is grid-based.
4. If , then is grid-based.

Proof. The first three assertions are trivial. As to the last one, we will prove that implies that there exist elements in , with

This clearly implies the last assertion. So assume that we have and (2.1). For each , the set

is a final segment of . Let be a finite set of generators of this final segment and let

Then fulfills our requirements.

Fig. 2.1. Illustration of a grid-based set with three base points , , and two infinitesimal generators and . Notice that we used “logarithmic paper” in the sense that multiplication by or corresponds to a translation via one of the vectors in the picture. Alternatively, one may write , where is a formal variable and is a formal ordered additive “value group” which is “anti-isomorphic” to . Instead of representing monomials , one may then represent their values in .

2.2Grid-based series

Let be a commutative, unitary ring of coefficients and a commutative, multiplicative monoid of monomials. The support of a mapping is defined by

If is grid-based, then we call a grid-based series. We denote the set of all grid-based series with coefficients in and monomials in by . We also write for the coefficient of in such a series and for . Each with is called a term occurring in .

Let be a family of grid-based series in . We say that is a grid-based family, if is grid-based and for each there exist only a finite number of with . In that case, we define its sum by

(2.2)

This sum is again a grid-based series. In particular, given a grid-based series , the family is grid-based and we have .

Let us now give the structure of a -algebra; we will say that is a grid-based algebra. and are clearly contained in via resp. . Let . We define

and

By propositions 1.6 and 2.1, and are well-defined as sums of grid-based families. It is not hard to show that is indeed a -algebra. For instance, let us prove the associativity of the multiplication. For each , we have

The right hand side of this equation is symmetric in , and and a similar expression is obtained for .

Let be a power series and an infinitesimal grid-based series, i.e. for all . Then we define

where the sum ranges over all words over the alphabet . The right hand side is indeed the sum of a grid-based family, by Higman's theorem and proposition 2.1. In section 2.5.3, we will consider more general substitutions and we will prove that and for all .

In particular, we have for all with . This yields an inverse for all elements of the form with . Assume now that is a field and that is a totally ordered group. Then we claim that is a field. Indeed, let be a series in and let be its dominant term (i.e. is maximal for in ). Then we have

Example 2.2. Let be any multiplicative monoid with the finest ordering for which no two distinct elements are comparable. Then is the polynomial ring .

Example 2.3. Let be any ordered abelian monoid and a formal, infinitely small variable. We will denote by the formal ordered multiplicative monoid of powers with , where (i.e. and are anti-isomorphic). We call the ring of grid-based series in over and along . If is clear from the context, then we also write . The following special cases are classical:

1. is the ring of formal power series in .
2. is the field of Laurent series in . Elements of are of the form with .
3. is the field of Puiseux series in . Elements of are of the form with and .
4. is the ring of multivariate power series, when is given the product ordering.
5. is the ring of multivariate Laurent series, when is given the product ordering. We recall that a multivariate Laurent series is the product of a series in and a monomial . Given , let be the set of dominant monomials of . Then we may take for each .

Often, we rather assume that is an infinitely large variable. In that case, is given the opposite ordering .

Example 2.4. There are two ways of explicitly forming rings of multivariate grid-based series: let be formal variables and ordered additive monoids. Then we define the rings of natural grid-based power series resp. recursive grid-based power series in over and along by

If , where is clear from the context, then we simply write

Any series in may also be considered as a series in and we may recursively expand as follows:

Notice that , in general (see exercise 2.6).

and

Now consider the monomial group

where . The order type of a series is the unique ordinal number which is isomorphic to the support of the series, considered as an ordered set. Determine the order types of the following series in , as well as their origins (like an equation which is satisfied by the series):

1. ;
2. ;
3. ;
4. ;
5. ;
6. ;
7. .

and

2.3Asymptotic relations

2.3.1Dominance and neglection relations

Let be a grid-based power series. The set of maximal elements for in the support of is called its set of dominant monomials. If this set is a singleton, then we say that is regular, we denote by or its unique dominant monomial, by its dominant coefficient, and by its dominant term. If is invertible, then we also denote , so that .

Notice that any grid-based series can be written as a finite sum of regular series. Indeed, let be the dominant monomials of . Then we have

where we recall that .

Assume that is an ordered ring. We give the structure of an ordered -algebra by setting , if and only if for each dominant monomial of , we have (see exercise 2.12).

Assume now that and are totally ordered, so that each non-zero series in is regular. Then we define a dominance relation on , whose associated strict quasi-ordering is a neglection relation, by

For non-zero and , we have

Given , we define its canonical decomposition by

where , and are respectively the purely infinite, constant and infinitesimal parts of . We also define , and ; we call the bounded part of . The canonical decomposition of itself is given by:

where

Similarly, we define and .

Example 2.5. Let with . Then the canonical decomposition of with is given by

Warning 2.6. One should not confuse with , since is strictly contained in , in general. We always do have and .

Proposition 2.7. Assume that is a totally ordered integral domain and a totally ordered monomial group. Then

1. is a totally ordered -algebra.
2. The relations and coincide with those defined in proposition 1.20.
3. If is a field, then is a Hahn space over .
4. is the set of bounded elements in .
5. is the set of infinitesimal elements in .

Proof. Given in , we have either , or (and thus ), or (and thus ). This proves (a).

Assume that , i.e. or . If , then clearly . If , then either and implies , or and implies . Inversely, assume that , i.e. and either or . If , then clearly , for all and . Otherwise, and or for all and , so that and again . We conclude that the above definition of coincides with the definition in proposition 1.20, using exercise 1.21(b). This proves (b), since for both definitions of we have .

If is a field, then for , we have . This shows (c). If is bounded, then either and clearly , or and for all , whence again . If is unbounded, then , whence . This proves (d), and (e) is proved similarly.

In the case when is not necessarily totally ordered, we may still define the constant and infinitesimal parts of a series by and . We say that is bounded resp. infinitesimal, if resp. . In other words, is bounded resp. infinitesimal, if for all , we have , resp. .

2.3.2Flatness relations

Assume now that is both a totally ordered -module and a totally ordered field with -powers, for some totally ordered ring , and assume that is a totally ordered group with -powers. Let and write with . Given , let . Then we define

(2.3)

In this way, we give the field the structure of a -algebra with -powers, by taking

Indeed, for all and infinitesimal .

Proposition 2.8. Let and be as above and let and be defined as in section 1.8. For , denote if and otherwise. Then, given , we have

1. ;
2. .

Proof. The characterizations of and immediately follow from the fact that for all .

2.3.3Truncations

Let be an arbitrary monomial monoid and . Given a subset , we define the restriction of to by

For instance, , , and . By our general notations, we recall that , for sets . Notice that , , etc.

Given two series , we say that is a truncation of (and we write ), if there exists a final segment of , such that . The truncation is a partial ordering on .

Let be a non-empty family of series. A common truncation of the is a series , such that for all . A greatest common truncation of the is a common truncation, which is greatest for . Similarly, a common extension of the is a series , such that for all . A least common extension of the is a common extension, which is least for . Greatest common truncations always exist:

Proposition 2.9. Any non-empty family admits a greatest common truncation.

Proof. Fix some and consider the set of initial segments of , such that for all . We observe that arbitrary unions of initial segments of a given ordering are again initial segments. Hence is an initial segment of each . Furthermore, for each , there exists an with for all . Hence for all . This proves that is a common truncation of the . It is also greatest for , since any common truncation is of the form for some initial segment of with .

2.4Strong linear algebra

Just as “absolutely summable series” provide a useful setting for doing analysis on infinite sums (for instance, they provide a context for changing the order of two summations), “grid-based families” provide an analogue setting for formal asymptotics. Actually, there exists an abstract theory for capturing the relevant properties of infinite summation symbols, which can be applied in both cases. In this section, we briefly outline this theory, which we call “strong linear algebra”.

2.4.1Set-like notations for families

It will be convenient to generalize several notations for sets to families. We will denote families by calligraphic characters and write for the collection of all families with values in . Explicit families will sometimes be denoted by . Consider two families and , where , and are arbitrary sets. Then we define

More generally, if , and for all , then we denote

Given an operation and families for , we define

It is also convenient to allow bounded variables to run over families. This allows us to rewrite (2.4) as

Similarly, sums of grid-based families may be denoted by

We say that and are equivalent, and we write , if there exists a bijection with for all . If is only injective, then we write . If and is the natural inclusion, then we simply write .

2.4.2Infinitary operators

The main idea behind strong linear algebra is to consider classical algebraic structures with additional infinitary summation operators . These summation symbols are usually only partially defined and they satisfy natural axioms, which will be specified below for a few structures. Most abstract nonsense properties for classical algebraic structures admit natural strong analogues (see exercise 2.20).

A partial infinitary operator on a set is a partial map

where is an infinite cardinal number and

We call the maximal arity of the operator . For our purposes, we may usually take , although higher arities can be considered [vdH97]. The operator is said to be strongly commutative, if for all equivalent families and in , we have and .

It is convenient to extend commutative operators to arbitrary families of cardinality . This is done by taking a bijection with and setting , whenever . When extending in this way, we notice that the domain of really becomes a class (instead of a set) and that is not really a map anymore.

2.4.3Strong abelian groups

Let be an abelian group with a partial infinitary operator . We will denote by the domain of . We say that is a strong abelian group, if

SA1

is strongly commutative.

SA2

For all and , we have .

SA3

For all and , we have .

SA4

For all , we have .

SA5

For all and decompositions , we have

SA6

For all with , we have

We understand that , whenever we use the notation . For instance, SA2 should really be read: for all and , we have and .

Remark 2.10. Given a strong abelian group , it is convenient to extend the summation operator to arbitrary families : we define to be summable in the extended sense if and only if is summable in the usual sense; if this is the case, then we set .

Example 2.11. Any abelian group carries a trivial strong structure, for which if only if is a finite family of elements in .

We call SA5 the axiom of strong associativity. It should be noticed that this axiom can only be applied in one direction: given a large summable family , we may cut it into pieces , which are all summable and whose sums are summable. On the other hand, given summable families such that is again summable, the sum is not necessarily defined: consider . The axiom SA6 of strong repetition aims at providing a partial inverse for SA5, in the case when each piece consists of a finite number of repetitions of an element.

Remark 2.12. In SA5, we say that the family refines the family . In order to prove identities of the form , a common technique is to construct a large summable family , which refines both and .

2.4.4Other strong structures

Let be a ring with a strong summation (which satisfies SA1–SA6). We say that is a strong ring if

SR

For all , we have

Let be a module over such a strong ring and assume that we also have a strong summation on . Then is said to be a strong -module if

SM

For all and , we have

Notice that SM is trivially satisfied when carries the trivial strong structure. We say that is an ultra-strong -module, if we also have

UM

For all and , we have .

A strong -algebra (resp. an ultra-strong -algebra) is an -algebra , together with a strong summation, for which carries both the structures of a strong ring and a strong -module (resp. an ultra-strong -module).

Let and be two strong -modules. A linear mapping is said to be strong if it preserves the infinite summation symbols, i.e.

SL

For all , we have .

In the case of ultra-strong modules, this condition implies

whenever and . Notice that strong abelian groups and rings can be considered as strong -modules resp. -algebras, so the definition of strongly linear mappings also applies in these cases.

2.5Grid-based summation

Let be a grid-based algebra as in section 2.2. Given a countable family , we define to be summable if and only if is a grid-based family, in which case its sum is given by formula (2.2). After extension of the strong summation operator to arbitrary families using remark 2.10, it can be checked that the notions of strong summation and summation of grid-based families coincide.

2.5.1Ultra-strong grid-based algebras

Proposition 2.13. is an ultra-strong -algebra.

Proof. The proof does not present any real difficulties. In order to familiarize the reader with strong summability, we will prove SA5 and SR in detail. The proofs of the other properties are left as exercises.

Let be a countable grid-based family and a decomposition of . For each , let and , so that

(2.5)

Now is a grid-based family for all , since and is finite for all . Furthermore,

and the set is finite for all , because of (2.5). Hence, the family is grid-based and for all , we have

This proves SA5.

Now let and be two grid-based families. Then

is grid-based. Given , the couples

with form a finite anti-chain; let denote those couples. Then

is finite, whence is a grid-based family. Given , and using the above notations, we also have

2.5.2Properties of grid-based summation

Let be a grid-based algebra. Given , let

We have

Indeed,

and for every ,

Moreover, if is a grid-based, then refines .

It is convenient to generalize proposition 2.1 to grid-based families. Given , we denote

Proposition 2.14. Given grid-based families , we have

1. is grid-based.
2. is grid-based.
3. If , then is grid-based.

Proof. Properties (a) and (b) follow from SA4 and SR. As to (c), let be the well-based set of pairs with and , for the ordering

Now consider the family with for each word . This family is well-based, since is well-based and the mapping increasing. Moreover,

so is a grid-based. Hence is grid-based, since refines .

2.5.3Extension by strong linearity

Let and be two grid-based algebras. A mapping is said to be grid-based if grid-based subsets are mapped to grid-based families .

Proposition 2.15. Let be a grid-based mapping. Then extends uniquely to a strongly linear mapping .

Proof. Let . Then is a grid-based family, by definition, and so is . We will prove that

is the unique strongly linear mapping which coincides with on .

Given and we clearly have , by SM. Now let and . We claim that

is grid-based. Indeed,

is grid-based. Secondly, given , the set is finite, since is grid-based. Finally, for each with , the family is finite. Hence, the family is finite, which proves our claim. Now our claim, together with SA5, proves that is grid-based and

This establishes the strong linearity of .

In order to see that is unique with the desired properties, it suffices to observe that for each , we must have by linearity and by strong linearity.

Proposition 2.16. Assume, with the notations from the previous proposition that preserves multiplication. Then so does .

Proof. This follows directly from the fact that the mappings and are both strongly bilinear mappings from into , which coincide on .

Strong bilinearity will be treated in more detail in section 6.2. Translated into terms of strong linearity, the proof runs as follows. Given , we first consider the mapping . Its extension by strong linearity maps to

but also to

We next consider the mapping . Its extension by strong linearity maps to

but also to

Proposition 2.17. Let and be two grid-based mappings. Then

Proof. This follows directly from the uniqueness of extension by strong linearity, since and coincide on .

In section 2.2, we defined the composition for and infinitesimal . We now have a new interpretation of this definition as follows. Consider the mapping , which maps to . By proposition 2.1 and Higman's theorem, is a grid-based family, whence we may extend by strong linearity. Given , we have

Now propositions 2.16 and 2.17 respectively imply that

and

for all . More generally, we have

Proposition 2.18. Let be infinitesimal grid-based series in and consider the mapping

Given , we define . Then

1. For , we have

   

2. For and infinitesimal , we have

   

RS

Let and be such that for all . Then .

2.6Asymptotic scales

Let both be an -module and a field with -powers, for some ring , and let be an ordered monomial group with -powers. The the definition of in (2.3) generalizes to the case when is a regular series with . As before, the group of such has -powers.

Proposition 2.19. Let be another ordered monomial group with -powers and let be a grid-based mapping such that

• , for all .
• and , for all and .
• The mapping is increasing.

Then

1. and , for all and .
2. If , then is injective.

Proof. By proposition 2.16, preserves multiplication. Let be a regular series and . Then

by the propositions of the previous section. Furthermore, is strictly increasing (otherwise, let be such that , but . Then is not grid-based). Hence, is in , and so are and . Therefore,

since is a group with -powers. This proves (a).

Assume now that . Then is injective and strictly increasing. Given with dominant monomials , the monomials are pairwise distinct. Consequently, the dominant monomials of are precisely the maximal elements for among the . In particular, if , then there exists at least one such maximal element, so that . This proves (b).

An asymptotic scale in is a subgroup of with -powers, such that is injective. Then is naturally ordered by , for all . The previous proposition now shows that we may identify with a subset of via the strongly linear extension of the inclusion . This identification is coherent in the sense that , for any asymptotic scale in , by proposition 2.17.

A basis of an asymptotic scale is a basis of , when considering as an exponential -module. If is such a basis, then is a basis of . In particular, if , then is a basis of . In this case, the bijection is called a scale change and its restriction to a base change. We also say that is an asymptotic basis for in this case.

When dealing with finite bases, it will often be convenient to consider them as ordered -tuples instead of sets without any ordering.

Almost all techniques for solving asymptotic systems of equations are explicitly or implicitly based on the Newton polygon method. In this section we explain this technique in the elementary case of algebraic equations over grid-based algebras , where is a constant field of characteristic zero and a totally ordered monomial group with -powers. In later chapters of this book, the method will be generalized to linear and non-linear differential equations.

In section 3.1, we first illustrate the Newton polygon method by some examples. One important feature of our exposition is that we systematically work with “asymptotic algebraic equations”, which are polynomial equations over together with asymptotic side-conditions, like . Asymptotic algebraic equations admit natural invariants, like the “Newton degree”, which are useful in the termination proof of the method. Another important ingredient is the consideration of equations , , etc. in the case when admits almost multiple roots.

In section 3.2, we prove a version of the implicit function theorem for grid-based series. Our proof uses a syntactic technique which will be further generalized in chapter 6. The implicit function theorem corresponds to the resolution of asymptotic algebraic equations of Newton degree one. In section 3.3, we show how to compute the solutions to an asymptotic algebraic equation using the Newton polygon method. We also prove that is algebraically closed or real closed, if this is the case for .

The end of this chapter contains a digression on “Cartesian representations”, which allow for a finer calculus on grid-based series. This calculus is based on the observation that any grid-based series can be represented by a multivariate Laurent series. By restricting these Laurent series to be of a special form, it is possible to define special types of grid-based series, such as convergent, algebraic or effective grid-based series. In section 3.5, we will show that the Newton polygon method can again be applied to these more special types of grid-based series.

Cartesian representations are essential for the development of effective asymptotics [vdH97], but they will only rarely occur later in this book (the main exceptions being section 4.5 and some of the exercises). Therefore, sections 3.4 and 3.5 may be skipped in a first reading.

3.1The method illustrated by examples

3.1.1The Newton polygon and its slopes

Consider the equation

(3.1)

and a Puiseux series , where is a formal parameter. We call the dominant exponent or valuation of . Then

is the dominant exponent of and

(3.2)

is a non-trivial polynomial equation in . We call and (3.2) the Newton polynomial resp. Newton equation associated to .

Let us now replace by a non-zero value in , so that . If is a solution to (3.1), then we have in particular . Consequently, must contain at least two terms, so that occurs at least twice among the numbers . It follows that

We call and the starting exponents for (3.1). The corresponding monomials , , and are called starting monomials for (3.1).

The starting exponents may be determined graphically from the Newton polygon associated to (3.1), which is defined to be the convex hull of all points with . Here points really encode points (recall the explanations below figure 2.1). The Newton polygon associated to (3.1) is drawn at the left hand side of figure 3.1. The diagonal slopes

correspond to the starting exponents for (3.1).

Given a starting exponent for (3.1), a non-zero solution of the corresponding Newton equation is called a starting coefficient and a starting term. Below, we listed the starting coefficients as a function of in the case of equation (3.2):

Notice that the Newton polynomials can again be read off from the Newton polygon. Indeed, when labeling each point by the coefficient of in , the coefficients of are precisely the coefficients on the edge with slope .

Given a starting term , we can now consider the equation which is obtained from (3.1), by substituting for , and where satisfies the asymptotic constraint . For instance, if , then we obtain:

(3.3)

The Newton polygon associated to (3.3) is illustrated at the right hand side of figure 3.1. It remains to be shown that we may solve (3.3) by using the same method in a recursive way.

3.1.2Equations with asymptotic constraints and refinements

First of all, since the new equation (3.3) comes with the asymptotic side-condition , it is convenient to study polynomial equations with asymptotic side-conditions

(3.4)

Fig. 3.1. The left-hand side shows the Newton polygon associated to the equation (3.1). The slopes of the four edges correspond to the starting exponents , , and (from left to right). After the substitution we obtain the equation (3.3), whose Newton polygon is shown at the right-hand side. Each non-zero coefficient in the equation (3.1) for induces a “row” of (potentially) non-zero coefficients in the equation for , in the direction of the arrows. The horizontal direction of the arrows corresponds to the slope of the starting exponent . Moreover, the fact that is a starting term corresponds to the fact that the coefficient of the lowest left-most induced point vanishes.

in a systematic way. The case of usual polynomial equations is recovered by allowing . In order to solve (3.4), we now only keep those starting monomials for which satisfy the asymptotic side condition , i.e. .

The highest degree of for a monomial is called the Newton degree of (3.4). If , then is either divisible by (and is a solution to (3.4)), or (3.4) admits a starting monomial (and we can carry out one step of the above resolution procedure). If , then (3.4) admits no solutions.

Remark 3.1. Graphically speaking, the starting exponents for (3.4) correspond to sufficiently steep slopes in the Newton polygon (see figure 3.2). Using a substitution , the equation (3.4) may always be transformed into an equation

with a normalized asymptotic side-condition (the case has to be handled with some additional care). Such transformations, called multiplicative conjugations, will be useful in chapter 8, and their effect on the Newton polygon is illustrated in figure 3.2.

Fig. 3.2. At the left-hand side, we have illustrated the Newton polygon for the asymptotic equation . The dashed line corresponds to the slope and the edges of the Newton polygon with slope have been highlighted. Notice that the Newton degree corresponds to the first coordinate of the rightmost point on an edge with slope . At the right-hand side, we have shown the “pivoting” effect around the origin of the substitution on the Newton polygon.

Given a starting term or a more general series , we next consider the transformation

(3.5)

with , which transforms (3.4) into a new asymptotic polynomial equation

(3.6)

Transformations like (3.5) are called refinements. A refinement is said to be admissible, if the Newton degree of (3.6) does not vanish.

Now the process of computing starting terms and their corresponding refinements is generally infinite and even transfinite. A priori, the process therefore only generates an infinite number of necessary conditions for Puiseux series to satisfy (3.4). In order to really solve (3.4), we have to prove that, after a finite number of steps of the Newton polygon method, and whatever starting terms we chose (when we have a choice), we obtain an asymptotic polynomial equation with a unique solution. In the next section, we will prove an implicit function theorem which guarantees the existence of such a unique solution for equations of Newton degree one. Such equations will be said to be quasi-linear.

Returning to our example equation (3.1), it can be checked that each of the refinements

leads to a quasi-linear equation in . The case