Transseries and Real Differential Algebra

 by Joris van der Hoeven

 Foreword XI
 Introduction 1
 The field with no escape 1
 Historical perspectives 3
 Outline of the contents 7
 Notations 10
 1Orderings 11
 1.1Quasi-orderings 12
 1.2Ordinal numbers 15
 1.3Well-quasi-orderings 17
 1.4Kruskal's theorem 19
 1.5Ordered structures 22
 1.6Asymptotic relations 25
 1.7Hahn spaces 29
 1.8Groups and rings with generalized powers 30
 2Grid-based series 33
 2.1Grid-based sets 34
 2.2Grid-based series 36
 2.3Asymptotic relations 40
 2.3.1Dominance and neglection relations 40
 2.3.2Flatness relations 42
 2.3.3Truncations 42
 2.4Strong linear algebra 44
 2.4.1Set-like notations for families 44
 2.4.2Infinitary operators 45
 2.4.3Strong abelian groups 46
 2.4.4Other strong structures 47
 2.5Grid-based summation 48
 2.5.1Ultra-strong grid-based algebras 48
 2.5.2Properties of grid-based summation 49
 2.5.3Extension by strong linearity 50
 2.6Asymptotic scales 53
 3The Newton polygon method 57
 3.1The method illustrated by examples 58
 3.1.1The Newton polygon and its slopes 58
 3.1.2Equations with asymptotic constraints and refinements 59
 3.1.3Almost double roots 62
 3.2The implicit series theorem 63
 3.3The Newton polygon method 65
 3.3.1Newton polynomials and Newton degree 65
 3.3.2Decrease of the Newton degree during refinements 66
 3.3.3Resolution of asymptotic polynomial equations 67
 3.4Cartesian representations 69
 3.4.1Cartesian representations 69
 3.4.2Inserting new infinitesimal monomials 71
 3.5Local communities 71
 3.5.1Cartesian communities 72
 3.5.2Local communities 72
 3.5.3Faithful Cartesian representations 73
 3.5.4Applications of faithful Cartesian representations 74
 3.5.5The Newton polygon method revisited 75
 4Transseries 79
 4.1Totally ordered exp-log fields 80
 4.2Fields of grid-based transseries 84
 4.3The field of grid-based transseries in 87
 4.3.1Logarithmic transseries in 88
 4.3.2Exponential extensions 88
 4.3.3Increasing unions 89
 4.3.4General transseries in 89
 4.3.5Upward and downward shifting 90
 4.4The incomplete transbasis theorem 92
 4.5Convergent transseries 94
 5Operations on transseries 97
 5.1Differentiation 98
 5.2Integration 103
 5.3Functional composition 106
 5.4Functional inversion 111
 5.4.1Existence of functional inverses 111
 5.4.2The Translagrange theorem 112
 6Grid-based operators 115
 6.1Multilinear grid-based operators 116
 6.1.1Multilinear grid-based operators 116
 6.1.2Operator supports 117
 6.2Strong tensor products 118
 6.3Grid-based operators 122
 6.3.1Definition and characterization 122
 6.3.2Multivariate grid-based operators and compositions 123
 6.4Atomic decompositions 124
 6.4.1The space of grid-based operators 124
 6.4.2Atomic decompositions 125
 6.4.3Combinatorial interpretation of atomic families 126
 6.5Implicit function theorems 127
 6.5.1The first implicit function theorem 128
 6.5.2The second implicit function theorem 130
 6.5.3The third implicit function theorem 130
 6.6Multilinear types 133
 7Linear differential equations 135
 7.1Linear differential operators 136
 7.1.1Linear differential operators as series 136
 7.1.2Multiplicative conjugation 137
 7.1.3Upward shifting 137
 7.2Differential Riccati polynomials 139
 7.2.1The differential Riccati polynomial 139
 7.2.2Properties of differential Riccati polynomials 140
 7.3The trace of a linear differential operator 141
 7.3.1The trace relative to plane transbases 141
 7.3.2Dependence of the trace on the transbasis 143
 7.3.3Remarkable properties of the trace 144
 7.4Distinguished solutions 146
 7.4.1Existence of distinguished right inverses 146
 7.4.2On the supports of distinguished solutions 148
 7.5The deformed Newton polygon method 151
 7.5.1Asymptotic Riccati equations modulo 151
 7.5.2Quasi-linear Riccati equations 152
 7.5.3Refinements 153
 7.5.4An algorithm for finding all solutions 155
 7.6Solving the homogeneous equation 156
 7.7Oscillating transseries 158
 7.7.1Complex and oscillating transseries 158
 7.7.2Oscillating solutions to linear differential equations 159
 7.8Factorization of differential operators 162
 7.8.1Existence of factorizations 162
 7.8.2Distinguished factorizations 163
 8Algebraic differential equations 165
 8.1Decomposing differential polynomials 166
 8.1.1Serial decomposition 166
 8.1.2Decomposition by degrees 167
 8.1.3Decomposition by orders 167
 8.1.4Logarithmic decomposition 168
 8.2Operations on differential polynomials 169
 8.2.2Multiplicative conjugation 170
 8.2.3Upward and downward shifting 170
 8.3The differential Newton polygon method 172
 8.3.1Differential Newton polynomials 172
 8.3.2Properties of differential Newton polynomials 173
 8.3.3Starting terms 174
 8.3.4Refinements 175
 8.4Finding the starting monomials 177
 8.4.1Algebraic starting monomials 177
 8.4.2Differential starting monomials 179
 8.4.3On the shape of the differential Newton polygon 180
 8.5Quasi-linear equations 182
 8.5.1Distinguished solutions 182
 8.5.2General solutions 183
 8.6Unravelling almost multiple solutions 186
 8.6.1Partial unravellings 186
 8.6.2Logarithmic slow-down of the unravelling process 188
 8.6.3On the stagnation of the depth 189
 8.6.4Bounding the depths of solutions 190
 8.7Algorithmic resolution 192
 8.7.1Computing starting terms 192
 8.7.2Solving the differential equation 194
 8.8Structure theorems 196
 8.8.1Distinguished unravellers 196
 8.8.2Distinguished solutions and their existence 197
 8.8.3On the intrusion of new exponentials 198
 9The intermediate value theorem 201
 9.1Compactification of total orderings 202
 9.1.1The interval topology on total orderings 202
 9.1.2Dedekind cuts 203
 9.1.3The compactness theorem 204
 9.2Compactification of totally ordered fields 206
 9.2.1Functorial properties of compactification 206
 9.2.2Compactification of totally ordered fields 207
 9.3Compactification of grid-based algebras 208
 9.3.1Monomial cuts 208
 9.3.2Width of a cut 209
 9.3.3Initializers 210
 9.3.4Serial cuts 210
 9.3.5Decomposition of non-serial cuts 211
 9.4Compactification of the transline 212
 9.4.1Exponentiation in 213
 9.4.2Classification of transseries cuts 213
 9.4.3Finite nested expansions 214
 9.4.4Infinite nested expansions 216
 9.5Integral neighbourhoods of cuts 219
 9.5.1Differentiation and integration of cuts 219
 9.5.2Integral nested expansions 219
 9.5.3Integral neighbourhoods 220
 9.5.4On the orientation of integral neighbourhoods 222
 9.6Differential polynomials near cuts 223
 9.6.1Differential polynomials near serial cuts 223
 9.6.2Differential polynomials near constants 224
 9.6.3Differential polynomials near nested cuts 225
 9.6.4Differential polynomials near arbitrary cuts 226
 9.6.5On the sign of a differential polynomial 227
 9.7The intermediate value theorem 229
 9.7.1The quasi-linear case 229
 9.7.2Preserving sign changes during refinements 230
 9.7.3Proof of the intermediate value theorem 232
 References 235
 Glossary 241
 Index 247

# 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 https://www.texmacs.org.

Joris van der Hoeven
Chevreuse 1999–2006

# 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:

 (1) (2) (3) (4) (5) (6) (7) (8)

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 (18) 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 (15) are grid-based. For instance, for (2), we may take and . The examples (68) 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 (68) 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:

Given a differential polynomial and transseries with , there exists a transseries with and .

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

# 1Orderings

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.

Exercise 1.1. Let be a set.

1. A strict ordering on is a transitive and antireflexive relation on (i.e. for no elements ). Given a quasi-ordering show that the relation defined by is a strict ordering. Show also how to associate an ordering to a strict ordering.

2. Let be a quasi-ordering on . Show that the relation defined by is also a quasi-ordering on ; we call it the opposite quasi-ordering of .

3. Let be a quasi-ordering on . Show that defines an ordering on . Show that is the roughest ordering which is finer than .

Exercise 1.2. Two quasi-ordered sets and are said to be isomorphic, and we write , if there is an increasing bijection between and , whose inverse is also increasing. Prove the following:

1. and are commutative modulo (i.e. ), but not and .

2. and are associative modulo .

3. is distributive w.r.t. modulo .

4. is right (but not left) distributive w.r.t. modulo (in other words ).

Exercise 1.3. Let be a quasi-ordered set. We define an equivalence relation on , by taking two words to be equivalent if they are obtained one from another by a permutation of letters. We call the set of commutative words over . Show that:

1. We define a quasi-ordering on by .

2. For all , we have if and only if there exists an injection with for all .

3. The equivalence relation is compatible with , so that we may order by the quotient quasi-ordering induced by .

4. The quasi-ordering is finer than and we have a natural increasing surjection .

5. For all ordered sets , prove that .

6. For all ordered sets prove that there exists an increasing bijection , whose inverse is not increasing, in general.

Exercise 1.4. Let and be ordered sets and denote by the set of mappings from into . For , we define

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

1. If , then .

2. If , then .

3. .

4. .

Exercise 1.5. Show that the category of quasi-ordered sets admits direct sums and products, pull-backs, push-outs, direct and inverse limits and free objects (i.e. the forgetful functor to the category of sets admits a right adjoint).

## 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. Every set can be well-ordered.

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. Each well-ordered set is isomorphic to a unique ordinal.

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

Exercise 1.6. Prove the transfinite induction principle.

Exercise 1.7. For any two ordinals , show that

1. ;

2. .

In particular, and are associative and is right distributive w.r.t. , by exercise 1.2.

Exercise 1.8. For all ordinals and , prove that

1. ;

2. .

Do we also have ?

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

Proof. Properties (a), (b), (e) and (f) follow from proposition 1.5(d). The properties (c) and (d) are special cases of (b).

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,

Exercise 1.9. Show that is a well-quasi-ordering if and only if the ordering on is a well-quasi-ordering.

Exercise 1.10. Prove the principle of Noetherian induction: let be a property for well-quasi-ordered sets, such that holds, whenever holds for all proper initial segments of . Then holds for all well-quasi-ordered sets.

Exercise 1.11. Let and be well-quasi-ordered sets. With as in exercise 1.4, when is also well-quasi-ordered?

Exercise 1.12. Let be a well-quasi-ordered set. The set of initial segments of is naturally ordered by inclusion. Show that is not necessarily well-quasi-ordered. We define to be a strongly well-quasi-ordered set if is also well-quasi-ordered. Which properties from proposition 1.6 generalize to strongly well-quasi-ordered sets?

Exercise 1.13. A limit well-quasi-ordered set is a well-quasi-ordered set , such that there are no final segments of cardinality 1. Given two well-quasi-ordered sets and , we define and to be equivalent if there exists an increasing injection from into and vice versa. Prove that a limit well-quasi-ordered set is equivalent to a unique limit ordinal.

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

Exercise 1.14. Let be a quasi-ordered set and let be an ordered set of operations on . That is, the elements of are mappings . We say that such an operation is extensive, if for all and , we have

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

whenever there exists an increasing mapping with for all .

Assume that these conditions are satisfied and let be a subset of . The smallest subset of which contains and which is stable under is said to be the subset of generated by w.r.t. , and will be denoted by . If is a well-quasi-ordered subset of and the ordering on is well-quasi-ordered, then prove that is well-quasi-ordered.

## 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

Exercise 1.15. Let be a totally ordered integral domain and let be its quotient field.

1. Show that , for all .

2. If is a total ordering, then show that there exists a unique total ordering on , which extends , and for which is an ordered field.

Exercise 1.16. Let be a totally ordered ring.

1. Show that , for all . In particular, if contains no nilpotent elements, then is an integral domain.

2. Show that may contain nilpotent elements.

3. Show that may contain zero divisors which are not nilpotent.

4. Show that positive non-nilpotent elements are larger than any nilpotent element in .

Exercise 1.17. Let and be quasi-ordered rings. Prove the following properties:

1. and ;

2. and ;

3. and ;

4. , but not always .

Exercise 1.18.

1. Show that the categories of ordered abelian groups, rings, -modules and -algebras (its morphisms are increasing morphisms of abelian groups, rings, etc.) admit direct sums and products, pull-backs, push-outs, direct and inverse limits and free objects (i.e. the forgetful functor to the category of sets admits a right adjoint).

2. Show that the same thing holds for the categories of ordered torsion free groups, rings without nilpotent elements, torsion free -modules and ordered -algebras without nilpotent elements, and such that the mapping is injective.

3. What can be said about the operations and introduced above?

Exercise 1.19. Let be an ordered abelian group, ring, -module or -algebra. We wish to investigate under which circumstances the ordering can be extended into a total ordering.

1. If is an ordered abelian monoid, prove that can be extended into a total ordering if and only if is torsion free (i.e. , for all and ). Hint: use Zorn's lemma.

2. If is an ordered ring without nilpotent elements, prove that can be extended into a total ordering if and only if is an integral domain, such that

for all , such that . Hint: first reduce the problem to the case when all squares in are positive. Next reduce the problem to the case when , for all .

3. Generalize b to the case when is an ordered ring, which may contain nilpotent elements.

4. Give conditions in the cases when is an ordered -module or an ordered -algebra without nilpotent elements.

Exercise 1.20. Let be an ordered group, ring, -module or -algebra. For each morphism of into a totally ordered structure of the same kind as , we define a relation on by . Let be the set of all such relations on .

1. Prove that is a quasi-ordering.

2. Show that is an ordering, if and only if can be extended into a total ordering on .

3. Let the equivalence relation associated to and let . Show that the ordered set can be given the same kind of ordered algebraic structure as , in such a way that the natural projection is a morphism. We call the closure of .

4. is said to be perfect if is a bijection. Prove that the closure of is perfect.

5. Show that an ordered abelian group is perfect if and only if , for all and .

6. Show that an ordered ring without nilpotent elements is perfect, if and only if , for all and , for all .

7. Under which conditions is an ordered -module perfect? And an ordered -algebra without nilpotent elements?

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

Exercise 1.21.

1. Given a totally ordered vector space over a totally ordered field , show that

2. Given a totally ordered module over a totally ordered ring , show that

Exercise 1.22. Let be a totally ordered ring. Is it true that the relations and are totally determined by the sets of infinitesimal resp. bounded elements of ?

Exercise 1.23. Prove that the sets of infinitesimal and bounded elements in a totally ordered ring are both convex (a subset of is convex if for all and , we have ). Prove that the set of archimedean elements has two “convex components”, provided that .

Exercise 1.24. Show that the nilpotent elements of a totally ordered ring are infinitesimal. Does the same thing hold for zero divisors?

Exercise 1.25. Let be a field. We recall that a valuation on is a mapping of into a totally ordered additive group, such that

V1
for all .

V2
, for all with .

Show that the valuations on correspond to total dominance relations.

Exercise 1.26.

1. Let be any ring and define , if and only if , for all . Show that is a domination relation, for which is the set of bounded elements, and the set of archimedean elements.

2. Assume that is a ring with a compatible dominance relation and neglection relation. Show that we may generalize the theory of this section, by replacing all quantifications over resp. by quantifications over resp. . For instance, the condition D2 becomes for all , and .

Exercise 1.27. Let be a perfect totally ordered ring and a perfect ordered -module. Given , we define resp. , if resp. for all morphisms of into a totally ordered -module . Prove that and compatible domination and neglection relations. Prove that the same thing holds, if we take a perfect ordered -algebra instead of .

Exercise 1.28. Let be an -module with a dominance relation . Let be the set of total dominance relations on , with . Prove that .

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

Exercise 1.29. Show that any totally ordered -vector space is a Hahn space. Do there exist other totally ordered fields with this property?

Exercise 1.30. Let be a totally ordered field and a finite dimensional Hahn space over . Assume that and are both bases of and denote by resp. the column matrices with entries resp. . Show that for some lower triangular matrix .

Exercise 1.31.

1. Prove that each Hahn space of countable dimension admits a basis which is totally ordered w.r.t. .

2. Prove that there exist infinite dimensional Hahn spaces, which do not admit bases of pairwise comparable elements for .

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

Exercise 1.32. Let be a totally ordered field with -powers and let be its smallest subfield with -powers.

1. Show that has a natural asymptotic -algebra structure with -powers.

2. Show that and are characterized by

Exercise 1.33. Consider as a “quasi-ordered vector space” for and the -power operation. Show that we may quotient this vector space by and that and correspond to the natural dominance and neglection relations on this quotient.

# 2Grid-based series

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 .

Exercise 2.1. Show that proposition 2.1 also holds for the following types of subsets of :

1. Well-based subsets;

2. Countable well-based subsets;

3. -finite subsets, when is an ordered group with -powers. Here an -finite subset of is a well-based subset, which is contained in a finitely generated subgroup with -powers of ;

4. Accumulation-free subsets, when is an ordered group with -powers. Here an accumulation-free subset of is a subset , such that for all with , there exists an , such that

Exercise 2.2. Assume that is a group. Show that -finite subsets of are not necessarily grid-based.

Exercise 2.3. If , with , then accumulation-free subsets of are also called Levi-Civitian subsets. Show that infinite Levi-Civitian subsets of are of the form , with .

Exercise 2.4. Assume that is a partially ordered monomial group with -powers. A subset of is said to be weakly based, if for each injective morphism of into a totally ordered monomial group with -powers we have:

1. The image is well-ordered.

2. For every , the set is finite.

Show that proposition 2.1 also holds for weakly based subsets and give an example of a weakly based subset which is not well-based.

Exercise 2.5.

1. For grid-based sets and , show that there exists a grid-based set with .

2. Given a grid-based set , does there exist a smallest grid-based set for inclusion, such that ? Hint: consider for a suitable ordering on .

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

Exercise 2.6. Show that, in general,

and

for non-trivial permutations of .

Exercise 2.7. Show that the definitions of this section generalize to the case when, instead of considering grid-based subsets of , we consider subsets of one of the types from exercise 2.1 or 2.4. Accordingly, we have the notions of well-based families, well-based series, accumulation-free series, etc. The -algebra of well-based series in over will be denoted by .

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

Also determine the order types of the squares of these series.

Exercise 2.8. Let be a Noetherian ring and let be a well-based monomial monoid. Show that is a Noetherian ring.

Exercise 2.9. For all constant rings and monomial groups, let either denote the ring of well-based, countably well-based, -finite or accumulation-free series over in . In which cases do we have for all and ?

Exercise 2.10. Let be a monomial group and let be the equivalence relation associated to as in exercise 1.1(c) Let and let be a right inverse for the projection . Show that we have natural embeddings

and

Show that the embeddings and are strict, in general.

Exercise 2.11. Let be a quasi-ordered monomial group and an “ideal” of in the sense that , for all and . Define a ring structure on , such that in , for all with .

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

Exercise 2.12. Let be an ordered ring and a monomial group. Given and series , determine the sets of dominant monomials of , and . Show that is an ordered -algebra.

Exercise 2.13. Assume that is a perfect ordered ring and a perfect ordered monoid.

1. Show that is a perfect ordered -algebra.

2. Let and be defined as in exercise 1.27. Show that in .

3. For and regular, show that , if and only if .

4. For and regular, show that , if and only if .

In other words, there is no satisfactory way to define the relations and purely formally, except in the case when the second argument is regular.

Exercise 2.14.

1. Let be an ordered ring and let be a monomial set, i.e. a set which is ordered by . Show that the set of series with well-based support has the natural structure of an ordered -module. Show also that this ordering is total if the orderings on and are both total.

2. Prove Hahn's embedding theorem [Hah07]: let be a Hahn space over a totally ordered field . Then is a totally ordered set for and may be embedded into .

3. If in proposition 1.22, then show that admits a unique basis , such that and for all .

Exercise 2.15.

1. Let be a field extension and a monomial set. Given a -subvector space of , show that is isomorphic to the -subvector space of , which is generated by .

2. Let be an extension of totally ordered fields. Given a Hahn space over , show that has the structure of a Hahn space over .

Exercise 2.16. Let be a totally ordered monomial group and let be a flat subset (i.e. ).

1. Show that is a flat subring of .

2. Characterize the relations and .

Exercise 2.17. Generalize the notion of truncation to the well-based setting. A directed index set is an ordered set , such that for any , there exist a with and . Let be a -increasing family of series in , i.e. whenever . If is Noetherian or totally ordered, then show that there exists a least common extension of the . Show that this property does not hold in the grid-based setting.

## 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

 (2.4)

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.

Exercise 2.18. Let and . Prove that

Deduce that .

Exercise 2.19.

1. Let , or a more general Banach algebra. Consider the infinite summation operator on , which associates to each absolutely summable family . Show that is a strong ring for this operator (and the usual finite summation operators).

2. Given a set , show how to construct the free strong -module in .

3. Let be a -algebra on a set . We define to be the free strong -module in , quotiented by all relations for at most countable families , whose members are mutually disjoint. Show that finite measures can then be interpreted as strongly linear mappings from into .

Exercise 2.20. Strong abelian groups, rings, modules and algebras form categories, whose morphisms are strongly linear mappings. Show that these categories admit direct sums and products, direct and inverse limits, pull-backs, push-outs and free objects (i.e. the forgetful functor to the category of sets admits a left adjoint).

## 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

This proves SR.

### 2.5.2Properties of grid-based summation

Let be a grid-based algebra. Given , let

We have

 (2.6) (2.7)

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

Exercise 2.21. Assume that is a strong ring and a monomial monoid. A family is said to be grid-based, if is grid-based and , for each . Show that this definition generalizes the usual definition of grid-based families and generalize proposition 2.13.

Exercise 2.22. Give the strong field structure from exercise 2.19(a) and the strong ring structure from exercise 2.21. Show that the strong summation on does not necessarily satisfy US. Prove that it does satisfy the following axiom:

RS
Let and be such that for all . Then .

Exercise 2.23. Generalize the results from this section to the case when we consider well-based (or -finite, accumulation-free series, etc.) series instead of grid-based series.

## 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