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 http://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:

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

 1

Orderings

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.

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,

1. 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.16. 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.18. 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.19. Let and be quasi-ordered rings. Prove the following properties:

1. and ;

2. and ;

3. and ;

4. , but not always .

Exercise 1.21.

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.23. 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.24. 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.25.

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.26. 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.27. 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.28. Show that the nilpotent elements of a totally ordered ring are infinitesimal. Does the same thing hold for zero divisors?

Exercise 1.29. 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.30.

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.31. 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.33. 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.34. Show that any totally ordered -vector space is a Hahn space. Do there exist other totally ordered fields with this property?

Exercise 1.35. 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.36.

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

 2

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

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

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

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

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

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

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

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

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

Exercise 2.24. Generalize the results from this section to the case when we consider well-based series instead of grid-based series. In the definition of asymptotic scales, one should add the requirement that the natural inclusion mapping be well-based (i.e. well-based subsets of are mapped to well-based families).

Exercise 2.25.

1. Assume that is a perfect monomial group, i.e. , for all and . Prove that a series is invertible, if and only if is regular. Hint: show that for each dominant monomial of , there exists an extension of the ordering on , such that , for all .

2. Prove that the above characterization of invertible series does not hold for general monomial groups.

Exercise 2.26. Let be a field and be a monomial group with -powers. Assume that admits a finite basis .

1. Let be another asymptotic basis of . Show that and that there exists a square matrix

such that , that is, for all .

2. Show that .

3. If , then show that the matrix is diagonal, modulo a permutation of the elements of .

4. If , then show that the matrix is lower triangular.

 3

The Newton polygon method

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

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

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

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

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

## 3.1The method illustrated by examples

### 3.1.1The Newton polygon and its slopes

Consider the equation

 (3.1)

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

is the dominant exponent of and

 (3.2)

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

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

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

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

correspond to the starting exponents for (3.1).

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

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

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

 (3.3)

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

### 3.1.2Equations with asymptotic constraints and refinements

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

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

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

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

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

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

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

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

 (3.5)

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

 (3.6)

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

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

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

leads to a quasi-linear equation in . The case

leads to an equation of Newton degree (it will be shown later that the Newton degree of (3.6) coincides with the multiplicity of as a root of ). Therefore, the last case necessitates one more step of the Newton polygon method:

For both refinements, it can be checked that the asymptotic equation in is quasi-linear. Hence, after a finite number of steps, we have obtained a complete description of the set of solutions to (3.1). The first terms of these solutions are as follows:

### 3.1.3Almost double roots

Usually the Newton degrees rapidly decreases during refinements and we are quickly left with only quasi-linear equations. However, in the presence of almost multiple roots, the Newton degree may remain bigger than two for quite a while. Consider for instance the equation

 (3.7)

over , with and . This equation has Newton degree , and after steps of the ordinary Newton polygon method, we obtain the equation

which still has Newton degree . In order to enforce termination, an additional trick is applied: consider the first derivative

of the equation (3.7) w.r.t. . This derived equation is quasi-linear, so it admits a unique solution

Now, instead of performing the usual refinement in the original equation (3.7), we perform refinement

This yields the equation

Applying one more step of the Newton polygon method yields the admissible refinements

In both cases, we obtain a quasi-linear equation in :

In section 3.3.2, we will show that this trick applies in general, and that the resulting method always yields a complete description of the solution set after a finite number of steps.

Remark 3.2. The idea of using repeated differentiation in order to handle almost multiple solutions is old [Smi75] and has been used in computer algebra before [Chi86, Gri91]. Our contribution has been to incorporate it directly into the Newton polygon process, as will be shown in more detail in section 3.3.2.

## 3.2The implicit series theorem

In the previous section, we have stressed the particular importance of quasi-linear equations when solving asymptotic polynomial equations. In this section, we will prove an implicit series theorem for polynomial equations. In the next section, we will apply this theorem to show that quasi-linear equations admit unique solutions. The implicit series theorem admits several proofs (see the exercises). The proof we present here uses a powerful syntactic technique, which will be generalized in chapter 6.

Theorem 3.3. Let be a ring and a monomial monoid. Consider the polynomial equation

 (3.8)

with coefficients , such that and . Then (3.20) admits a unique solution in .

Proof. Since , the series is invertible in . Modulo division of (3.20) by , we may therefore assume without loss of generality that . Setting for all , we may then rewrite (3.20) as

 (3.9)

Now consider the set of trees with nodes of arities in and such that each node of arity is labeled by a monomial in . To each such tree

we recursively associate a coefficient and a monomial by

Now we observe that each of these monomials is infinitesimal, with

 (3.10)

Hence the mapping is strictly increasing, when is given the embeddability ordering from section 1.4. From Kruskal's theorem, it follows that the family is well-based and even grid-based, because of (3.10). We claim that is the unique solution to (3.9).

First of all, is indeed a solution to (3.9), since

In order to see that is the unique solution to (3.20), consider the polynomial . Since , we have for all , whence in particular . Furthermore, implies . Now assume that were another root of . Then would be a root of , so that

 (3.11)

since is invertible.

Exercise 3.1. Generalize theorem 3.3 to the case when (3.20) is replaced by

where is a grid-based family with and .

Exercise 3.2. Give an alternative proof of theorem 3.3, using the fact that (3.9) admits a unique power series solution in , when considered as an equation with coefficients in .

Exercise 3.3. Assuming that is totally ordered, give yet another alternative proof of theorem 3.3, by computing the terms of the unique solution by transfinite induction.

Exercise 3.4. Let denote the ring of non-commutative power series in over . Consider the equation

 (3.12)

with , and invertible . Prove that (3.12) admits a unique infinitesimal solution .

## 3.3The Newton polygon method

### 3.3.1Newton polynomials and Newton degree

Let be a constant field of characteristic zero and a totally ordered monomial group with -powers. Consider the asymptotic polynomial equation

 (3.13)

with coefficients in and . In order to capture ordinary polynomial equations, we will also allow , where is a formal monomial with . A starting monomial of relative to (3.13) is a monomial in , such that there exist and with and for all other . To such a starting monomial we associate the equation

 (3.14)

and is called the Newton polynomial associated to . A starting term of relative to (3.13) is a term , where is a starting monomial of relative to (3.13) and a non-zero root of . In that case, the multiplicity of is defined to be the multiplicity of as a root of . Notice that there are only a finite number of starting terms relative to (3.13).

Proposition 3.4.

Let be a non-zero solution to (3.13). Then is a starting term for (3.13).

The Newton degree of (3.13) is defined to be the largest degree of the Newton polynomial associated to a monomial . In particular, if there exists no starting monomial relative to (3.13), then the Newton degree equals the valuation of in . If , then we say that (3.13) is quasi-linear. The previous proposition implies that (3.13) does not admit any solution, if .

Lemma 3.5. If (3.13) is quasi-linear, then it admits a unique solution in .

Proof. If , then our statement follows from proposition 3.4, since there are no starting monomials. Otherwise, our statement follows from theorem 3.3, after substitution of for in (3.13), where is chosen -maximal such that for all , and after division of (3.13) by .

### 3.3.2Decrease of the Newton degree during refinements

A refinement is a change of variables together with the imposition of an asymptotic constraint:

 (3.15)

where and . Such a refinement transforms (3.13) into an asymptotic polynomial equation in :

 (3.16)

where

 (3.17)

for each . We say that the refinement (3.15) is admissible if the Newton degree of (3.16) is strictly positive.

Lemma 3.6. Consider the refinement (3.15) with . Then

1. The Newton degree of (3.16) coincides with the multiplicity of as a root of . In particular, (3.15) is admissible if and only if is a starting term for (3.13).

2. The Newton degree of (3.16) is bounded by the Newton degree of (3.13).

Proof. Let be maximal such that for all , and denote . Then is bounded by the Newton degree of (3.13) and

for all . In particular, denoting the multiplicity of as a root of by , we have . Moreover, for all , we have . Hence, for any and , we have . This shows that the Newton degree of (3.16) is at most .

Let us now show that the Newton degree of (3.16) is precisely . Choose large enough, so that

for all . Then .

If one step of the Newton polygon method does not suffice to decrease the Newton degree, then two steps do, when applying the trick from the next lemma:

Lemma 3.7. Let be the Newton degree of (3.13). If admits a unique starting monomial and a unique root of multiplicity , then

1. The equation

 (3.18)

is quasi-linear and its unique solution satisfies .

2. The Newton degree of any refinement

relative to (3.16) with is strictly inferior to .

Proof. Notice first that for all polynomials and monomials . Consequently, (3.18) is quasi-linear and is a single root of . This proves (a).

As to (b), we first observe that . Given , it follows that . In particular, there do not exist with . In other words, does not admit roots of multiplicity . We conclude by lemma 3.6.

### 3.3.3Resolution of asymptotic polynomial equations

Theorem 3.8. Let be an algebraically closed field of characteristic zero and a totally ordered monomial group with -powers. Then is algebraically closed.

Proof. Consider the following algorithm:

Algorithm polynomial_solve

Input: An asymptotic polynomial equation (3.13).

Output: The set of solutions to (3.13).

1. Compute the starting terms of relative to (3.13).

2. If and is a root of multiplicity of , then let be the unique solution to (3.18). Refine (3.15) and apply polynomial_solve to (3.16). Return the so obtained solutions to (3.13).

3. For each , refine

and apply polynomial_solve to the new equation in . Collect and return the so obtained solutions to (3.13), together with , if is divisible by .

The correctness of polynomial_solve is clear; its termination follows from lemmas 3.6(b) and 3.7(b). Since is algebraically closed, all Newton polynomials considered in the algorithm split over . Hence, polynomial_solve returns solutions to (3.13) in , when counting with multiplicities. In particular, when taking , we obtain solutions, so is algebraically closed.

Corollary 3.9. Let be a real closed field and a totally ordered monomial group with -powers. Then is real closed.

Proof. By the theorem, a polynomial equation of degree over admits solutions in , when counting with multiplicities. Moreover, each root is imaginary, because

for such . Therefore all real roots of are in .

Corollary 3.10.

The field of Puiseux series over an algebraically resp. real closed field is algebraically resp. real closed.

Exercise 3.5. Consider an asymptotic algebraic equation (3.13) of Newton degree . Let be the starting terms of (3.13), with multiplicities . Prove that

Also show that if is algebraically closed.

Exercise 3.6.

1. Show that the computation of all solutions to (3.13) can be represented by a finite tree, whose non-root nodes are labeled by refinements. Applied to (3.1), this would yields the following tree:

2. Show that the successors of each node may be ordered in a natural way, if is a real field, and if we restrict our attention to real algebraic solutions. Prove that the natural ordering on the leaves, which is induced by this ordering, corresponds to the usual ordering of the solutions.

Exercise 3.7.

1. Generalize the results of this chapter to asymptotic equations of infinite degree in , but of finite Newton degree.

2. Give an example of an asymptotic equation of infinite degree in , with infinitely many solutions.

Exercise 3.8. Consider an asymptotic polynomial equation

of Newton degree , with and . Consider the monomial monoid with

1. Show that there exists a unique invertible series such that is a monoic polynomial in .

2. Show that .

## 3.4Cartesian representations

In this section, we show that grid-based series may be represented by (finite sums of) multivariate Laurent series in which we substitute an infinitesimal monomial for each variable. Such representations are very useful for finer computations with grid-based series.

### 3.4.1Cartesian representations

Let be a grid-based algebra. A Cartesian representation for a series is a multivariate Laurent series , such that for some morphism of monomial monoids . Writing , with , we may also interpret as the product of a “series” in and the monomial .

More generally, a semi-Cartesian representation for is an expression of the form

where , and is a morphism of monomial monoids.

Proposition 3.11.

1. Any grid-based series admits a semi-Cartesian representation.

2. If is a monomial group, which is generated by its infinitesimal elements, then each grid-based series admits a Cartesian representation.

Proof.

Let and be such that

For each , let

Let

for all and let . Then

For certain and , we may write

for all . Let and

Then .

Cartesian or semi-Cartesian representations and are said to be compatible, if and belong to the same algebra of Laurent series, and if .

Proposition 3.12.

1. Any admit compatible semi-Cartesian representations.

2. If is a monomial group, which is generated by its infinitesimal elements, then any admit compatible Cartesian representations.

Proof. By the previous proposition, admit semi-Cartesian representations , where and for each . Now consider

Then for each , where is the image of under the natural inclusion of into . This proves (a); part (b) is proved in a similar way.

### 3.4.2Inserting new infinitesimal monomials

In proposition 3.12 we drastically increased the size of the Cartesian basis in order to obtain compatible Cartesian representations. The following lemma is often useful, if one wants to keep this size as low as possible.

Lemma 3.13. Let be infinitesimal elements of a totally ordered monomial group with -powers, such that . Then there exist infinitesimal with .

Proof. It suffices to prove the lemma for ; the general case follows by induction over . The case is proved by induction over . For , there is nothing to prove. So assume that and let with . Without loss of generality, we may assume that , modulo a permutation of variables. Putting , we now distinguish the following three cases:

1. If , then there exist infinitesimal , such that , by the induction hypothesis. Taking , we now have , since .

2. If , then , and we may take .

3. If , then there exists infinitesimal , such that . Taking , we again have .

When doing computations on grid-based series in , one often works with respect to a Cartesian basis of infinitesimal elements in . Each time one encounters a series which cannot be represented by a series in , one has to replace by a wider Cartesian basis with . The corresponding mapping is called a widening. Lemma 3.13 enables us to keep the Cartesian basis reasonably small during the computation.

## 3.5Local communities

Let be a ring and a monomial group which is generated by its infinitesimal elements. Given a set for each , we denote by the set of all grid-based series , which admit a Cartesian representation for some . In this section, we will show that if the satisfy appropriate conditions, then many types of computations which can be carried out in can also be carried out in .

### 3.5.1Cartesian communities

Let be a ring. A sequence with is said to be a Cartesian community over , if the following conditions are satisfied:

CC1
.

CC2
is a -algebra for each .

CC3
The are stable under strong monomial morphisms.

In CC3, a strong monomial morphism is strong -algebra morphism which maps monomials to monomials. In our case, a monomial preserving strong morphism from into is always of the form

where and for all . In particular, CA3 implies that the are stable under widenings.

Proposition 3.14. Let be a Cartesian community over and let be a monomial group. Then is a -algebra.

Proof. We clearly have . Let . Mimicking the proof of proposition 3.12, we observe that and admit compatible Cartesian representations . Then , and are Cartesian representations of , resp. .

### 3.5.2Local communities

A local community is a Cartesian community , which satisfies the following additional conditions:

LC1
For each with , we have .

LC2
Given and , we have .

LC3
Given with and , the unique series with belongs to .

In LC1 and LC3, the notation stands for the coefficient of in . The condition LC3 should be considered as an implicit function theorem for the local community. Notice that is stable under for all {}, since

 (3.19)

Remark 3.15. In [vdH97], the conditions LC2 and LC3 were replaced by a single, equivalent condition: given as in LC3, we required that , for the unique strong -algebra morphism , such that and . We also explicitly requested the stability under differentiation, although (3.19) shows that this is superfluous.

Example 3.16. Let be a subfield of and let be the set of convergent power series in variables over , for each . Then the form a local community. If is a monomial group, then will also be called the set of convergent grid-based series in over .

Example 3.17. For each , let be the set of power series in , which satisfy an algebraic equation over . Then the form a local community.

### 3.5.3Faithful Cartesian representations

In this and the next section, is a local community. A Cartesian representation is said to be faithful, if for each dominant monomial of , there exists a dominant monomial of , with .

Proposition 3.18. Let be a local community and . Then

1. For each and , we have .

2. For each initial segment , we have

Proof. For each , let . We will prove (a) by a weak induction over . If , then . If , then

By the weak induction hypothesis and LC1, we thus have .

In order to prove (b), let be the finite anti-chain of maximal elements of , so that . Let be the number of variables which effectively occur in , i.e. the number of , such that with for some . We prove (b) by weak induction over . If , then either and , or , and .

Assume now that and order the variables in such a way that effectively occurs in one of the . For each , let

We observe that

In particular, if is maximal with , then for all and

so that

Moreover, for each , at most variables effectively occur in the set of dominant monomials of . Therefore , by the induction hypothesis.

Proposition 3.19. Given a Cartesian representation

of a series , its truncation

is a faithful Cartesian representation of the same series .

### 3.5.4Applications of faithful Cartesian representations

Proposition 3.20. Let be series, which is either

1. infinitesimal,

2. bounded, or

3. regular.

Then admits a Cartesian representation in for some , which is also infinitesimal, bounded resp. regular.

Proof. Assume that is infinitesimal and let be a faithful Cartesian representation of , with dominant monomials . For each , let

with . Then and

is an infinitesimal Cartesian representation of in , when setting for each . This proves (a).

If is bounded, then let be an infinitesimal Cartesian representation of . Now is a bounded Cartesian representation of . This proves (b).

Assume finally that is regular, with dominant monomial . Let be a bounded Cartesian representation of . Since , the series is necessarily regular. Now take a Cartesian monomial which represents (e.g. among the dominant monomials of a faithful Cartesian representation of ). Then is a regular Cartesian representation of .

### 3.5.5The Newton polygon method revisited

Theorem 3.21. Let be a local community over a ring and let be a monomial monoid. Consider the polynomial equation

 (3.20)

with coefficients , such that and . Then (3.20) admits a unique solution in .

Proof. By proposition 3.20, there exist bounded Cartesian representations for certain . Now consider the series

We have and , so there exists a with

by LC3. We conclude that satisfies . The uniqueness of follows from theorem 3.3.

Theorem 3.22. Let be a local community over a (real) algebraically closed field and a totally ordered monomial group with -powers. Then is a (real) algebraically closed field.

Proof. The proof is analogous to the proof of theorem 3.8. In the present case, theorem 3.21 ensures that in step 2 of polynomial_solve.

Exercise 3.9. Let be a ring, a monomial monoid and a local community. We define to be the set of series in , which admit a semi-Cartesian representation

with for some , and . Which results from this section generalize to this more general setting?

Exercise 3.10. Let be a field. A series in is said to be differentially algebraic, if the field generated by its partial derivatives has finite transcendence degree over . Prove that the collection of such series forms a local community over .

Exercise 3.11. Assume that is an effective field, i.e. all field operations can be performed by algorithm. In what follows, we will measure the complexity of algorithms in terms of the number of such field operations.

1. A series is said to be effective, if there is an algorithm which takes on input, and which outputs . Show that the collection of effective series form a local community.

2. An effective series is said to be of polynomial time complexity, if there is an algorithm, which takes on input and which computes for all with in time . Show that the collection of such series forms a local community. What about even better time complexities?

Exercise 3.12. Let be a local community and let

be a Cartesian representation of an infinitesimal, bounded or regular grid-based series in . Show that, modulo widenings, there exists an infinitesimal, bounded resp. regular Cartesian representation of , with respect to a Cartesian basis with at most elements.

Exercise 3.13. Let be a local community over a field .

1. If and , then show that .

2. If is totally ordered, then prove that is a field.

Exercise 3.14. Let be a local community over a field and let be a totally ordered monomial group. Prove that for any , and

Exercise 3.15. Let be a Cartesian community. Given monomial groups and , let be the set of strong -algebra morphisms from into and the set of , such that for all .

1. Given and , where is a third monomial group, prove that .

2. Given and such that , prove that .

Exercise 3.16. Let be a subfield of and let and be monomial groups with . Prove that . Does this property generalize to other local communities?

Exercise 3.17. Let be the local community from example 3.17 and let be a totally ordered monomial group. Prove that is isomorphic to the algebraic closure of .

Exercise 3.18. Does theorem 3.22 still hold if we remove condition LC2 in the definition of local communities?

Exercise 3.19. Consider the resolution of , with and .

1. Given a starting term of multiplicity , let be minimal for such that for all . Show that there exist Cartesian coordinates with , in which admits a bounded Cartesian representations for all .

2. Consider a bounded Cartesian representation with and let . Given , let

Show that is a series in .

3. For each , let be initial segment generated by the such that , and its complement. We say that is the part of multiplicity of as a zero of . Show that can be determined effectively for all .

4. In polynomial_solve, show that refinements of the type

where is the unique solution to , may be replaced by refinements

 4

Transseries

Let be a totally ordered exp-log field. This means that is a totally ordered field with an exponential function and a partial logarithmic function which satisfies similar properties as those defined on the real numbers. Axioms for exp-log fields will be given in section 4.1. For the moment, the reader may assume that .

The aim of this chapter is the construction of the totally ordered exp-log field of grid-based transseries in over . This means that is a field of grid-based series with an additional exponential structure. Furthermore, contains as an infinitely large monomial. Actually, the field carries much more structure: in the next chapter, we will show how to differentiate, integrate, compose and invert transseries. From corollary 3.9, it also follows that is real closed. In chapter 9, this theorem will be generalized to algebraic differential equations.

As to the construction of , let us first consider the field . Given an infinitesimal series , we may naturally define

Using the exp-log structure of , these definitions may be extended to for and to for . However, nor the logarithm of , nor the exponential of any infinitely large series are defined. Consequently, we have to add new monomials to in order to obtain a field of grid-based series which is stable under exponentiation and logarithm.

Now it is easy to construct a field of grid-based series which is stable under logarithm (in the sense that is defined for all strictly positive ). Indeed, taking , we set

for monomials (here stands for the -th iterated logarithm). For general , we define

where as above.

In order to construct a field of grid-based series with an exponentiation, we first have to decide what monomial group to take. The idea is to always take exponentials of purely infinite series for the monomials in . For instance, is a monomial. On the other hand, is not a monomial and we may expand it in terms of using

More generally, as soon as each purely infinite series in admits an exponential, then is closed under exponentiation: for all we take

with as above.

In section 4.2, we first study abstract fields of transseries. These are totally ordered fields of grid-based series, with logarithmic functions that satisfy some natural compatibility conditions with the serial structures. Most of these conditions were briefly motivated above. In section 4.3 we construct the field of transseries in . We start with the construction of the field of logarithmic transseries. Next, we close this field under exponentiation by repeatedly inserting exponentials of purely infinite series as new monomials. In section 4.4, we prove the incomplete transbasis theorem, which provides a convenient way to represent and compute with grid-based transseries.

## 4.1Totally ordered exp-log fields

A partial exponential ring is a ring with a partial exponential function , such that

E1
.

E2
, for all .

The second condition stipulates in particular that , whenever . If , then we say that is an exponential ring. If is an exponential function, then we will also write for and for the -th iterate of (i.e. and for all ).

The field of real numbers is a classical example of an exponential field. Moreover, the real numbers carry an ordering and it is natural to search for axioms which model the compatibility of the exponential function with this ordering. Unfortunately, an explicit set of axioms which imply all relations satisfied by the exponential function on has not been found yet. Nevertheless, Dahn and Wolter have proposed a good candidate set of axioms [DW84].

We will now propose a similar system of axioms in the partial context. For each , we denote the Taylor expansion of at order by

We also denote

so that . An ordered partial exponential ring is a partially ordered ring , with a partial exponential function , which satisfies E1, E2 and

E3
, for all and .

If , then we say that is an ordered exponential ring.

Proposition 4.1. Let be an ordered ring in which . Given a partial exponential function on which satisfies E1, E1 and E1, we have

for all and .

Proof. Assume that . We cannot have , since otherwise

If , then

whence .

Proposition 4.2. is a totally ordered exponential field.

Proof. Let . For , we have

For , we have shown above that .

Proposition 4.3. Let be an ordered partial exponential ring. Then

1. is injective.

2. , for all .

3. If is a -module, then

Proof. Assume that , for some . Then

and similarly . Hence,

so that both and . This proves that , whence is injective.

Assume now that for some . Then

Consequently,

and , by the injectivity of . Inversely, assume that for some . Then

whence . We again conclude that , since . This proves (b).

If , then (c) follows from (b). If , then implies

for all .

Instead of axiomatizing partial exponential functions on a ring, it is also possible to axiomatize partial logarithmic functions. The natural counterparts of E1, E2 and E3 are

L1
.

L2
, for all .

L3
, for all and .

Notice that the second condition assumes the existence of a partial inversion , whose domain contains . The -th iterate of will be denoted by .

In a similar fashion, we define a partial logarithmic ring to be a ring with a partial logarithmic function which satisfies L1 and L2. An ordered partial logarithmic ring is an ordered ring with a partial logarithmic function which satisfies L1, L2 and L3. In the case when for such a ring, then we say that is an ordered logarithmic ring.

Proposition 4.4.

1. Let be a partial exponential ring, such that is injective. Then the partial inverse of satisfies L1 and L2.

2. If is an ordered partial exponential ring, then is injective, and its partial inverse satisfies L1, L2 and L3.

3. Let be a partial logarithmic ring, such that is injective. Then the partial inverse of satisfies E1 and E2.

4. If is an ordered partial logarithmic ring, then is injective, and its partial inverse satisfies E1, E2 and E3.

Proof. Let be a partial exponential ring, such that is injective. Then we clearly have L1. Now assume that . Then , whence . Furthermore, if , then , so that . Consequently, and . This proves L2 and (a). As to (b), if is an ordered partial exp-log ring, then is injective by proposition 4.3(a). The property L3 directly follows from E3.

Assume now that is a partial logarithmic ring, such that is injective. We clearly have E1. Given and in , we have and in particular . It follows that . This proves E2 and (c).

Assume finally that is an ordered partial logarithmic ring. Let be such that . Then

Hence , since . Similarly, and , which proves that is injective. The property E3 directly follows from L3.

If (a) and (c) (resp. (b) and (d)) are satisfied in the above proposition, then we say that is a partial exp-log ring (resp. an ordered partial exp-log ring). An ordered exp-log ring is an ordered partial exp-log ring , such that and . An ordered (partial) exponential, logarithmic resp. exp-log ring, which is also an ordered field is called an ordered (partial) exponential, logarithmic resp. exp-log field. In a partial exp-log ring, we extend the notations and to the case when , by setting and , if .

Assume now that is a ring with -powers, for some subring . An exponential resp. logarithmic function is said to be compatible with the -powers structure on if

E4
, for all and ; resp.

L4
, for all and .

Here we understand that in E4 and in L4. Notice that E4 and L4 are equivalent, if and are partial inverses. Notice also that any totally ordered exp-log field naturally has -powers: set for all and .

Exercise 4.1. Let be an exponential ring. Show that for all , we have .

Exercise 4.2. Show that the only exponential function on the totally ordered field of real numbers is the usual exponential function.

Exercise 4.3. Let be a totally ordered exponential field. Show that the exponential function on is continuous. That is, for all and in , there exists a , such that , for all with . Show also that the exponential function is equal to its own derivative.

Exercise 4.4. Let be an ordered partial exponential ring. Given and , prove that

1. , if .

2. , if .

## 4.2Fields of grid-based transseries

Let be a totally ordered exp-log field, a totally ordered monomial group with -powers. Assume that we have a partial logarithmic function on the totally ordered field with -powers. We say that is a field of grid-based transseries (or a field of transseries) if

T1
.

T2
, for all .

T3
, for all , where .

Intuitively speaking, the above conditions express a strong compatibility between the logarithmic and the serial structure of .

Example 4.5. Assume that is a field of transseries, such that , and such that is stable under exponentiation. Then is a monomial in . The series is not a monomial, since . We have

On the other hand, is a monomial, since

Proposition 4.6. Let be a field of transseries. Then

1. Given , the canonical decomposition of is given by

2. Given , we have

3. Given , we have

4. For all , we have , and .

Proof.

Follows from L1, L2, T2 and T3.

We have

The other relations are proved in a similar way.

We have

The other relations are proved similarly.

Let . Then , by (b), whence . Furthermore,

Consequently, , since . It follows that

Since is total on , we infer that . Therefore, . Finally, and (c) imply that by (c).

The following lemma, which is somehow the inverse of proposition 4.6(a) and (d), will be useful for the construction of fields of transseries.

Lemma 4.7. Let be a partial function on , which satisfies T1, T2 and

1. , for all and .

2. , for all .

3. , for all .

Then is a logarithmic function, which is compatible with the ordering and -powers on . Hence, is a field of grid-based transseries.

Proof. We clearly have L1. Given , we also have

Here

by proposition 2.18 and the fact that in . This proves L2.

Let us now show that

for all and . Assume first that . If , then we have

Otherwise, and

If , then . Consequently,

If , let us show that , for all , which clearly implies that . We first observe that for all , since and . Furthermore, , for all . Taking , we get . This proves L3.

Let us finally show that for any and . Denoting , we have

Indeed, proposition 2.18 implies that , since is a formal identity in .

Exercise 4.5. Let be a field of transseries.

1. Show that for all , where .

2. For each , show that

3. For each , show that , and .

Exercise 4.6. Let , and be as above. Prove the following formal identities:

1. ;

2. ;

3. ;

4. .

Hint: prove that the left and right hands sides satisfy the same (partial) differential equations and the same initial conditions.

Exercise 4.7. Let be a field of transseries and consider a flat subset of (i.e. ).

1. Show that there exists an initial segment of such that

2. Show that , where

We call the steep complement of .

## 4.3The field of grid-based transseries in

Let be a fixed totally ordered exp-log field, such as , and a formal infinitely large variable. In this section, we will construct the field of grid-based transseries in over . We proceed as follows:

• We first construct the field

of logarithmic transseries in .

• Given a field of transseries , we next show how to construct its exponential extension : this is the smallest field of transseries with and such that is defined in for all .

• We finally consider the sequence

of successive exponential extensions of . Their union

is the desired field of grid-based transseries in over .

### 4.3.1Logarithmic transseries in

Consider the field , where

Given a monomial , we define by

We extend this definition to , by setting

for each . Here we recall that .

Proposition 4.8. is a field of transseries.

Proof. Clearly, , for all and . Now let . Then , for certain with . Hence, , since and . Now the proposition follows from lemma 4.7.

### 4.3.2Exponential extensions

Let be a field of transseries and let

be the monomial group of formal exponentials with , which is isomorphic to the totally ordered -module : we define and for all and .

Now the mapping is an injective morphism of monomial groups, since for all . Therefore, we may identify with its image in and with the image of the strongly linear extension of in . We extend the logarithm on to by setting for monomials , and for general .

Proposition 4.9. is a field of transseries.

Proof. By construction, , for all and . Given , we have . Consequently, and are both in , and proposition 4.6(d) implies that . Hence, and . We conclude by lemma 4.7.

### 4.3.3Increasing unions

Proposition 4.10. Let be a totally ordered set and let be a family of fields of transseries of the form , such that and , whenever . Then is a field of transseries.

Proof. Clearly . Inversely, assume that

Since is grid-based, there exist , such that

For sufficiently large , we have , since is totally ordered. Hence, and . This proves that . Similarly, one verifies that is a field of transseries, using the fact that given , we actually have for some .

### 4.3.4General transseries in

Let be the sequence defined by and for all . By propositions 4.8, 4.9 and 4.10,

is a field of transseries. We call it the field of grid-based transseries in over . The exponential height of a transseries in is the smallest index , such that . A transseries of exponential height is called a logarithmic transseries.

Intuitively speaking, we have constructed by closing first under logarithm and next under exponentiation. It is also possible to construct the other way around: let be the smallest subfield of , which contains and which is stable under grid-based summation and exponentiation. We have of . The logarithmic depth of a transseries in is the smallest number , such that .

We will write for the field of transseries of exponential height and logarithmic depth . We will also write and .

Example 4.11. The divergent transseries

 (4.1)

is an example of a transseries of exponential height and logarithmic depth . The transseries and from example 4.5 have exponential height resp. and logarithmic depth .

For the purpose of differential calculus, it is convenient to introduce slight variations of the notions of exponential height and logarithmic depth. The level of a transseries is the smallest number for which . The field of transseries of level is called the field of exponential transseries. The depth of a transseries is the smallest number with .

Example 4.12. The transseries (4.1) has level and depth . Both transseries and have level and depth . The transseries has level and depth .

### 4.3.5Upward and downward shifting

In this section, we define the right compositions of transseries in with and . Given , we will also denote and by resp. and call them the upward and downward shifts of . The mappings are strong difference operators and will be constructed by induction over the exponential height.

For monomials , we define

Extending these definitions by strong linearity, we obtain mappings

Now assume that we have further extended these mappings into mappings

Then we define

for monomials . Extending these definitions by strong linearity, we obtain mappings

By induction over , we have thus defined and on . Notice that and are mutually inverse, since for all and , by induction over .

There is another way of interpreting right compositions of transseries in with and as formal substitutions and , considered as mappings from into resp. . Postulating that these mappings coincide with the upward and downward shiftings amounts to natural isomorphisms between and resp. .

Exercise 4.8. Let be any non-trivial field of grid-based transseries. Prove that there exists a strongly linear ring homomorphism .

Exercise 4.9. For all , prove that

1. ;

2. ;

3. ;

4. .

Exercise 4.10. Given , we call the contraction and the dilatation of . Determine and . Prove that for any , we have for some and all sufficiently large . Here denotes the -th iterate of .

Exercise 4.11. A field of well-based transseries is a field of well-based series of the form , which satisfies T1, T2, T3 and

T4
Let be a sequence of monomials in , such that , for each . Then there exists an index , such that for all and all , we have and .

Show that the results from sections 4.3.1, 4.3.2 and 4.3.3 generalize to the well-based context.

Exercise 4.12. Define a transfinite sequence of fields of well-based transseries as follows: we take , for each ordinal and , for each limit ordinal .

1. Prove that for all ordinals . Hint: one may consider the transfinite sequence of transseries defined by

2. If we restrict the supports of well-based transseries to be countable, then prove that the transfinite sequence stabilizes. Hint: find a suitable representation of transseries by labeled trees.

Exercise 4.13.

1. Prove that T1, T2 and T3 do not imply T4.

2. A transseries is said to be log-confluent, if there exists an index , such that for all , we have . Prove that T4 implies the log-confluence of all transseries in .

3. Prove that T1, T2, T3 and the log-confluence of all transseries in do not imply T4.

Exercise 4.14.

1. Prove that there exists a field of well-based transseries in the sense of exercise 4.11, which contains the transseries

2. Prove that the functional equation

## 4.4The incomplete transbasis theorem

A transbasis is a finite basis of an asymptotic scale, such that

TB1
and .

TB2
, for some .

TB3
for all .

The integer in TB2 is called the level of the transbasis . We say that is a transbasis for (or that can be expanded w.r.t. ), if .

Remark 4.13. Although the axiom TB3 is well-suited to the purpose of this book, there are several variants which are more efficient from a computational point of view: see exercise 4.15.

Example 4.14. The tuple is a transbasis for and so is . Neither nor is a transbasis.

Theorem 4.15. Let be a transbasis and a transseries. Then can be expanded w.r.t. a super-transbasis of . Moreover, may be chosen so as to fulfill the following requirements:

1. The level of is the minimum of the levels of and .

2. If and belong to a flat subring of of the form , then so does .

Proof. Let be the level of . Without loss of generality, we may assume that . Indeed, there exists an with ; if , then we insert into . We will now prove the theorem by induction over the minimal , such that . If , then we clearly have nothing to prove. So assume that .

Let us consider the case when , with . We distinguish three cases:

is bounded
We may take .

for each
is again a transbasis for some and

can be expanded w.r.t. . Moreover, satisfies the extra requirements (a) and (b). Indeed, has level and

since .

for some
We rewrite , with . If is again equivalent to some , then , and we may rewrite , with . Repeating this procedure, we end up with an expression of the form

with and where is either bounded or infinitely large with , for all . By what precedes, and may be expanded w.r.t. a super-transbasis of which satisfies the additional requirements (a) and (b).

This proves the theorem in the case when , with .

Assume now that is a general grid-based transseries in . Then is contained in a set of the form , where and . Moreover, if , then we may choose . Indeed, setting

for all , we have

Using the induction hypothesis, and modulo an extension of , we may therefore assume without loss of generality that . By what precedes, it follows that there exists a super-transbasis of for which satisfies the requirements (a) and (b). By strong linearity, we conclude that is the required transbasis for .

Exercise 4.16. Consider the following alternatives for TB3:

TB3-a
, for all ;

TB3-b
, for all , where is such that ;

TB3-c
for all ;

TB3-d
for all .

We respectively say that is a heavy, normal, light or sloppy transbasis.

1. Show that TB3-a TB3-b TB3-c TB3-d.

2. Show that theorem 4.15 holds for any of the above types of transbases.

Exercise 4.17. Find heavy, normal, light and sloppy normal transbases with respect to which the following “exp-log transseries” can be expanded:

1. ;

2. ;

3. ;

4. ;

5. .

More precisely, an exp-log transseries (resp. function) is a transseries (resp. function) built up from and constants in , using the field operations , , , , exponentiation and logarithm.

Exercise 4.18. Let be a transbasis. Prove that there exists a unique transbasis , such that

1. for all .

2. for all .

Exercise 4.19. Let be a local community.

1. If and belong to in theorem 4.15, then show that may be chosen to belong to as well.

2. Show that (a) remains valid if LC3 is replaced by the weaker axiom that for all we have .

3. Given a transbasis , show that and that the coefficients of recursive expansions of are again in .

4. Given , show that .

## 4.5Convergent transseries

Assume now that and let us define the exp-log subfield of convergent transseries in . The field of convergent transseries of exponentiality is defined by induction over by taking and . Here we notice that , so that , by induction. Now we define . By exercises 3.13 and 3.14, the set is an exp-log subfield of .

Let be the ring of germs at infinity of real analytic functions at infinity. We claim that there exists a natural embedding , which preserves the ordered exp-log field structure. Our claim relies on the following lemma:

Lemma 4.16. Let be a totally ordered monomial group and an injection, which preserves multiplication and . Then for each ,

is a well-defined function in and the mapping is an injective morphism of totally ordered fields.

Proof. Let be a regular convergent Cartesian representation for , with . Let be such that is real analytic on . Consider the mapping

Since preserves , we have , for sufficiently large . Hence, is defined and real analytic for all sufficiently large .

Assume now that and write , where is a convergent series in with . Then

for , when choosing sufficiently small. Hence,

for all sufficiently large , i.e. . Consequently, is an injective, increasing mapping and it is clearly a ring homomorphism.

Let us now construct embeddings , by induction over . For , the elements in may naturally be interpreted as germs at infinity, which yields a natural embedding by lemma 4.16. Assume that we have constructed the embedding and consider the mapping

Clearly, is an injective multiplicative mapping. Given , we also have

Applying lemma 4.16 on , we obtain the desired embedding . Using induction over , we also observe that coincides with on for each . Therefore, we have a natural embedding of into , which coincides with on each .

Remark 4.17. In the case of well-based transseries, the notion of convergence is more complicated. In general, sums like only yield quasi-analytic functions and for a more detailed study we refer to [É92, É93]. For natural definitions of convergence like in exercise 4.21, it can be hard to show that convergence is preserved under simple operations, like differentiation.

Exercise 4.20.

1. Given , let

We say that is summable in , if is grid-based and . Show that this defines a strong ring structure on .

2. Let be a family of elements in . Define by , whenever there exists a neighbourhood of infinity, such that is defined on for each and such that is normally convergent on each compact subset of . Show that this defines a strong ring structure on .

3. Reformulate lemma 4.16 as a principle of “convergent extension by strong linearity”.

Exercise 4.21. Prove that

Exercise 4.22. Let be the field of well-based transseries of finite exponential and logarithmic depths. Given , let be the set of infinitely differentiable real germs at infinity and the set of infinitely differentiable real functions on .

1. Construct the smallest subset of , together with a mapping , such that

CT1
If , then and .

CT2
If is such that for all and is convergent on , then and .

Show that is a ring.

2. Show that for . Denoting , show that there exists a mapping , such that is the germ associated to for every with . Show also that is a field.

 5

Operations on transseries

One of the major features of the field of grid-based transseries in is its stability under the usual operations from calculus: differentiation, integration, composition and inversion.

What is more, besides the classical properties from calculus, these operations satisfy interesting additional properties, which express their compatibility with infinite summation, the ordering, and the asymptotic relations , , etc. Therefore, the field of transseries occurs as a natural model of “ordered or asymptotic differential algebra”, in addition to the more classical Hardy fields. It actually suggests the development of a whole new branch of model theory, which integrates the infinitary summation operators. Also, not much is known on the model theory of compositions.

In section 5.1, we start by defining the differentiation w.r.t. as the unique strongly linear -differentiation with and for all . This differentiation satisfies

In section 5.2, we show that the differentiation has a unique right inverse with the property that for all ; for this reason, we call the “distinguished integral” of . Moreover, the distinguished integration is strongly linear and we will see in the exercises that one often has .

In section 5.3, we proceed with the definition of a composition on . More precisely, given , we will show that there exists a unique strongly linear -difference operator with and for all . This difference operator satisfies

Moreover, the composition defined by is associative and compatible with the differentiation: for all and . Finally, the Taylor series expansion holds under mild hypotheses on and .

In section 5.4, we finally show that each admits a unique functional inverse with . We conclude this chapter with Écalle's “Translagrange theorem” [É03], which generalizes Lagrange's classical inversion formula.

## 5.1Differentiation

Let be a strong totally ordered partial exp-log -algebra. A strong derivation on is a mapping , which satisfies

D1
, for all .

D2
is strongly linear.

D3
, for all .

We say that is an exp-log derivation, if we also have

D4
, for all .

We say that is (strictly) asymptotic resp. positive, if

D5
, for all with .

D6
, for all .

In this section, we will show that there exists a unique strong exp-log derivation on , such that . This derivation turns out to be asymptotic and positive. In what follows, given a derivation on a field, we will denote by the logarithmic derivative of .

Lemma 5.1. Let be an arbitrary field of transseries and let be a mapping, which satisfies for all . Then

1. is a grid-based mapping, which extends uniquely to a strong derivation on .

2. If for all , then is an exp-log derivation on .

Proof. Let be a grid-based subset of , so that

for certain monomials and in . For any , we have

Hence for all , and a grid-based mapping. The strongly linear extension of is indeed a derivation, since and are both strongly bilinear mappings from into , which coincide on (a proof which does not use strong bilinearity can be given in a similar way as for proposition 2.16). This proves (a).

As to (b), assume that for all . Obviously, in order to prove that is a strong exp-log derivation, it suffices to prove that for all . Now each may be decomposed as , with , and . For each , we have . Hence,

by strong linearity. We conclude that

Proposition 5.2. There exists a unique strong exp-log derivation on with .

Proof. We will show by induction over that there exists a unique strong exp-log derivation on with . Since this mapping is required to be strongly linear, it is determined uniquely by its restriction to . Furthermore, will be a strong exp-log derivation, if its restriction to satisfies the requirements of lemma 5.9.

For , the derivative of a monomial must be given by

in view of axioms D3 and D4 and the requirements of lemma 5.9 are easily checked.

If , then the induction hypothesis states that there exists a unique strong exp-log derivation on with . In view of D4, any strong exp-log derivation on should therefore satisfy

for all . On the other hand, when defining in this way, we have

for all . Hence, there exists a unique strong derivation with on , by lemma 5.9. Moreover, is a strong exp-log derivation, since

for all monomials .

 Fig. 5.1. We will often adopt a geometric point of view for which the derivative is a function on the “transline” . Due to the highly non-archimedean character of , it is difficult to sketch the behaviour of this function. An attempt has been made in the left figure above. The two squares correspond to the regions where both coordinates are infinitesimal resp. bounded. Notice that is locally decreasing everywhere (the small curves), although its restriction to is increasing (the fat curve). At the right hand side, we also sketched the behaviour of the functions and for transmonomials (using logarithmic coordinates).

Proposition 5.3. For all , we have

Proof. The mappings and are both strong exp-log derivations with . We conclude by proposition 5.2.

Proposition 5.4. Let be a transbasis.

1. If or , then is stable under .

2. If and , then is stable under .

Proof. Let us prove (a) by induction over . Clearly, and are stable under differentiation. So assume that and that is stable under differentiation. Then . Hence

for all monomials . Consequently, is stable under differentiation, by strong linearity.

As to (b), we first observe that is also a transbasis, so is stable under differentiation. Given , we now have

Proposition 5.5. The derivation on is asymptotic and positive.

Proof. Let be a transbasis with . We will first prove by induction over , that is asymptotic and positive on , and , for all in . This is easy in the case when . So assume that .

Given a monomial , we first observe that

belongs to . Moreover,

for all , by the induction hypothesis. Actually, the induction hypothesis also implies that , since . Consequently, , if .

Secondly, let and be monomials with . If , then by the induction hypothesis. If , then

whence . If , then

Hence in all cases. Given with and , we thus get , for all , whence , by strong linearity.

Let us now prove that the induction hypothesis is satisfied at order . Given , with , we have

If , we still have , since and . Now let . By the induction hypothesis, we have , since . We conclude that

At this point, we have proved that is asymptotic and positive on . By theorem 4.15(a), this also proves that asymptotic and positive on . Now let be such that . Then

Similarly, if is such that and , then

Remark 5.6. A transbasis of level will also be called a plane transbasis. The two facts that is stable under differentiation for each and for all , make plane transbases particularly useful for differential calculus.

By theorem 4.15(a), we notice that any exponential transseries can be expanded with respect to a plane transbases. Computations which involve more general transseries can usually be reduced to the exponential case using the technique of upward and downward shifting.

Exercise 5.1. For all , prove that

Exercise 5.2. For all with and , show that

Exercise 5.3. Let . Prove that

1. .

2. .

3. .

In the case of (a), notice that we may for instance interpret as a relation in a field of well-based transseries in .

Exercise 5.4. Consider a derivation on a totally ordered -algebra , which is also a field. We say that is asymptotic resp. positive, but not necessarily strictly, if

D5
, for all with .

D6
, for all .

If is an asymptotic derivation, prove that is again an asymptotic derivation for any . Given positive derivations , prove that is again a positive derivation. Prove that neither the set of asymptotic, nor the set of positive derivations necessarily form a module.

Exercise 5.5. Let . Characterize

1. The strong -module of all strong exp-log derivations on .

2. The set of all (not necessarily strictly) asymptotic strong exp-log derivations on .

3. The set of all (not necessarily strictly) positive strong exp-log derivations on .

Exercise 5.6. Let be a flat subset of the set of transmonomials and let be its steep complement (see exercise 4.7).

1. Show that is stable under differentiation.

2. Considering as a strong -algebra, show that there exists a unique strongly -linear mapping with for all .

3. Show that

for all .

Exercise 5.7. Let be a convergent transseries. Prove that is convergent and that the germ at infinity associated to coincides with the derivative of the germ at infinity associated to . In other words, is a Hardy field.

Exercise 5.8. Construct a strong exp-log derivation on the field of well-based transseries of finite exponential and logarithmic depths. Show that there exists a unique such derivation with , and show that is asymptotic and positive. Hint: see [vdH97].

## 5.2Integration

In this section, we show that each transseries admits an integral in . Since the derivative of a transseries vanishes if and only if it is a constant, we infer that admits a unique, distinguished integral , whose constant term vanishes. The distinguished property immediately implies that mapping is linear. We will show that is actually strongly linear.

Proposition 5.7. There exists a unique right inverse of , such that the constant term of vanishes for all . This right inverse is strongly linear.

Proof. We will first consider the case when is exponential. Let be a plane transbasis for . Consider the double sum

 (5.1)

where

We will show that the family is grid-based, so that (5.1) defines an integral of .

Let us first study the for a monomial with . We observe that . Setting

we thus have and . Moreover, for any , we have . Now define families by

where

Then for all . Setting , we have

whence is grid-based by proposition 2.14(c) and (2.7). We conclude that is well-defined, and

Let us now show that the mapping is grid-based. Given a grid-based subset of , we may decompose

where the () are given by

By what precedes, is grid-based for each . Hence, is a grid-based mapping which extends uniquely to by strong linearity. Furthermore, given with , we have , so that

This implies that is a distinguished, strongly linear integral on .

Assume now that we have defined a distinguished, strongly linear integral on . We claim that we may extend to by

 (5.2)

Indeed, (5.2) defines a distinguished integral, since

and

for all . Its distinguished property implies that it extends the previous integral on . Its strong linearity follows from the fact that we may see as the composition of four strongly linear operations. Our proposition now follows by induction over .

Proposition 5.8. Let be a transbasis.

1. If or , then is stable under for all .

2. If and , then is stable under .

Proof. We will consider the case when and . The other cases follow by upward shifting. Now given

with , we claim that

where are given by

Indeed, it is easily checked that . Furthermore,

whence , by the distinguished property of integration.

Exercise 5.10. Let be a transmonomial. Show that there exists a unique transmonomial , so that is a transmonomial.

Exercise 5.12. Let .

1. If and , then show that

 (5.4)
2. Give a necessary and sufficient condition for (5.3) to hold.

3. Prove that there does not exist a strong integration on so that (5.3) holds for all .

Exercise 5.13. Show that is divergent. Deduce that is not an exp-log function.

Exercise 5.14. Let an embedding of a Hardy field into . The embedding is assumed to preserve the differential ring structure and the ordering. Given , show that can be extended into an embedding .

## 5.3Functional composition

Let and be strong totally ordered partial exp-log -algebras. A strong difference operator of into is an injection , which satisfies

1
, for all .

2
is strongly linear.

3
, for all .

If , then we say that is a strong difference operator on . We say that is an exp-log difference operator, if we also have

4
, for all .

We say that is asymptotic resp. increasing, if

5
, for all .

6
, for all .

In this section, we will show that for each , there exists a unique strong exp-log difference operator on , such that . This allows us to define a composition on by

We will show that this composition is associative, that it satisfies the chain rule, and that we can perform Taylor series expansion under certain conditions.

Lemma 5.9. Let be arbitrary fields of transseries and let be a mapping, which satisfies and for all . Then

1. is a grid-based mapping, which extends uniquely to a strong, asymptotic and increasing difference operator from into .

2. If for all , then the extension of to is an exp-log difference operator.

Proof. Let be a grid-based subset of with , for certain monomials and in . Then the family with is grid-based, by proposition 2.14(c). It follows that is grid-based, since . By proposition 2.16, the extension of to is a strong difference operator. If , then for all , whence . This proves that is asymptotic and, given , it also follows that . In particular, if , then . This completes the proof of (a).

Now assume that for all . In order to prove (b), it obviously suffices to show that for all . Now each may be decomposed as , with , and . For each , we have . Hence, , by strong linearity. We conclude that

Proposition 5.10. Let . Then there exists a unique strong exp-log difference operator on with . This difference operator is asymptotic and increasing.

Proof. We will show by induction over that there exists a unique strong exp-log difference operator from into with , and we will show that this difference operator is asymptotic and increasing.

For , the axioms 3 and 4 imply that

for all monomials . If , i.e. and for some , we also get

since

This completes the proof in the case when , by lemma 5.9.

If , then the induction hypothesis states that there exists a unique strong exp-log difference operator with , and is asymptotic and increasing. In view of 4, any extension of to should therefore satisfy for all . On the other hand, when defining in this way on , we have

for all . Similarly,

for all . This completes the proof in the general case, by lemma 5.9.

Proposition 5.11.

1. , for all and .

2. , for all and .

3. Let be such that and for all . Then

 (5.5)

Proof. Property (a) follows from proposition 5.10 and the fact that and are both strong exponential difference operators which map to .

Let be the set of , for which . We have and is stable under grid-based summation, since the mappings and are both strongly linear. is also stable under exponentiation and logarithm: if , then

and implies

This proves (b), since the smallest subset of which satisfies the above properties is itself.

As to (c), we first have to prove that the right hand side of (5.4) is well-defined. Let be a transseries in and denote by the set of transseries , such that for all . Given a transmonomial , we have

since . We infer that

Let us show that is stable under differentiation. By the strong linearity of the differentiation, it suffices to prove that , for all transmonomials with . If , then , for all . If , then for all , whence .

Now consider a transbasis , such that and . By theorem 4.15(b), any can be expanded with respect to such a transbasis. Let

so that , for all . Now let , , and consider the family of all terms

Then

Moreover, setting , we have

so is grid-based, by proposition 2.14(c). Since refines the family , it follows that the Taylor series in (5.4) is well-defined. For a similar reason, the mapping is grid-based, so the mapping is actually strongly linear.

Now let be the subset of of all , such that (5.4) holds. Clearly, and is stable under strongly linear combinations. We claim that is also stable under exponentiation and logarithm. Indeed, assume that and . Then , , , , since . Hence for all , which allows us to expand

We have to show that coincides with

But this follows from the fact that we may see as a formal identity in the ring . Indeed, and satisfy the same differential equation

and . Similarly, one may show that is stable under logarithm. This proves (c), since the smallest subset of , which contains and which is stable under strongly linear combinations, exponentiation and logarithm, is itself.

Exercise 5.15. Let and .

1. Prove that the exponentiality of equals the sum of the exponentialities of and .

2. Prove that the exponential height resp. logarithmic depth of is bounded by the sum of the exponential heights resp. logarithmic depths of and .

3. Improve the bound in (b) by taking into account the exponentialities of and .

Exercise 5.16. Let and be such that . Under which condition do we have

Exercise 5.17. Let and let a grid-based family of transseries, such that , for all and . prove that

Exercise 5.18. Let be a transmonomial in and a transseries, such that and for all . Prove that is a transmonomial.

Exercise 5.19. Show that is stable under composition.

Exercise 5.20. Let and be two transbases and consider two series and . Construct a transbasis for of size .

## 5.4Functional inversion

### 5.4.1Existence of functional inverses

Theorem 5.12. Any admits a functional inverse with

Proof. Without loss of generality, one may assume that , where is exponential. Indeed, it suffices to replace by for sufficiently large , where is the exponentiality of . Let be a plane transbasis for . We will prove that admits a functional inverse of the form , where can be expanded with respect to a plane transbasis which satisfies

Let us first assume that the constant coefficient of in vanishes. Then proposition 5.11(c) implies that

 (5.6)

for any . In particular, for every , we have

Now the functional inverse of is given by

Since and maps into itself, we conclude that , with .

The general case is proved by induction over . If , then we must have , so we are done. So assume that . By the induction hypothesis, there exists a functional inverse for , such that , where

Now

where , and . It follows that has a functional inverse of the form with and . We conclude that is a functional inverse of and we have

### 5.4.2The Translagrange theorem

We define a scalar product on by

Given transseries and , let us denote

When taking transmonomials for and , then the coefficients describe the post-composition operator with . More precisely, for all we have

Theorem 5.13. Let be exponential transseries and . Then satisfies

Proof. Since for all , we have

Since and are exponential, we have

Using the rule , it follows that

Now integration by parts yields

But , since is exponential.

The theorem generalizes to the case when and are no longer exponential, by applying the following rule a finite number of times:

Corollary 5.14. Let be transseries of depths and . Then satisfies

Exercise 5.21. Let where is exponential and let be as in (5.5).

1. Show that we do not always have .

2. Give a necessary and sufficient condition for which

Exercise 5.22.

1. A classical theorem of Liouville [Lio37, Lio38] states that is not an exp-log function. Show that there exists no exp-log function with (see [Har11] for a variant of this problem).

2. Show that there exists no exp-log function with . Hint: use exercise 5.11.

3. Assume that is not an exp-log function. Show that there exists an , such that there exists no exp-log function with .

Exercise 5.23. Show that is stable under functional inversion.

Exercise 5.24. Classify the convex subgroups of . Hint: is a convex subgroup of if and only if its contraction is a convex subgroup.

Exercise 5.25. Show that Lagrange's inversion formula is a special case of theorem 5.13.

Exercise 5.26. Show that theorem 5.13 still holds when and is exponential.

Exercise 5.27. Let be transseries and let be a transseries of level . Show that for all sufficiently large , the inverse satisfies

If one allows , then show that the formula holds for transseries of arbitrary levels.

 6

Grid-based operators

Besides multiplication and strong summation, we have introduced other interesting operations on the field of transseries in the previous chapter, like differentiation, integration, composition and functional inversion. In this chapter we will perform a theoretical study of an even larger class of operations on transseries, which contains the above elementary operations, but also many natural combinations of them.

This theoretical study is carried out best in the context of “grid-based modules”. Let be a ring. In chapter 2, we defined a grid-based algebra to be a strong -algebra of the form , where is a monomial monoid. An arbitrary subset of is called a monomial set and the set of strong linear combinations of elements in a grid-based module.

In section 6.1, we start by generalizing the notion of strongly linear mappings from chapter 2 to the multilinear case. Most natural elementary operations like multiplication, differentiation, right composition, etc. can then be seen as either linear or bilinear “grid-based operators”. In section 6.3, we next introduce the general concept of a grid-based operator. Roughly speaking, such an operator is a mapping which admits a “generalized Taylor series expansion”

such that there exists a -linear grid-based operator

with

for each . If , then such Taylor series expansions are unique and we will show that the may be chosen to be symmetric.

Multilinear grid-based operators may both be reinterpreted as general grid-based operators and linear grid-based operators using the “syntactic sugar isomorphisms”

The first isomorphism also provides a notion of grid-based operators in several variables.

As promised, many operations can be carried with grid-based operators: they can be composed and one may define a natural strong summation on the space of grid-based operators . An explicit strong basis of “symmetric atomic operators” for this space will be established in section 6.4.2. Last but not least, we will prove several implicit function theorems for grid-based operators in section 6.5. These theorems will be a key ingredient for the resolution of differential (and more general functional equations) in the next chapters.

## 6.1Multilinear grid-based operators

### 6.1.1Multilinear grid-based operators

Let and be strong modules over a ring . A mapping

is said to be strongly multilinear, if for all , we have and

If and are grid-based modules, then we also say that is a multilinear grid-based operator.

Example 6.1. Given monomial monoids and , all strongly linear mappings are multilinear grid-based operators. Denoting , we have in particular the following important types of linear grid-based operators:

1. Left multiplication operators , with .

2. Strong derivations . If admits -powers, then such derivations should also satisfy , whenever is well-defined for and .

3. Strong integrations; these are partial, strongly linear right inverses of strong derivations , i.e. .

4. Strong difference operators . If admits -powers, then such difference operators should also satisfy , whenever is well-defined for and ).

5. Strong summation operators; these are partial, strongly linear right inverses of finite difference operators, i.e. , for some strong difference operator .

Example 6.2. Given a monomial monoid , the multiplication and the scalar product are strongly bilinear mappings.

Example 6.3. Compositions

of multilinear grid-based operators

are again multilinear grid-based operators.

Example 6.4. The -linear grid-based operators of the form form a -module. For instance, if is a strong derivation, where , then strong differential operators of the form

are linear grid-based operators. In section 6.4.1, we will see that we may actually define strong summations on spaces of grid-based operators.

### 6.1.2Operator supports

Let be an -linear grid-based operator, such that and are all subsets of a common monomial group . Then the operator support of is defined by

The operator support is the smallest subset of , such that

 (6.1)

for all . Given , we also denote

Example 6.5. We have

for multilinear operators () and .

Exercise 6.1. Let be infinitesimal linear grid-based operators (i.e. for ).

1. Show that is well-defined for non-commutative series .

2. Determine the largest subspace of on which is a well-defined bijection.

Exercise 6.2.

1. Is a multilinear grid-based operator necessarily a multilinear well-based operator?

2. Show that for well-based series, if is totally ordered. Here denotes the strong dual of .

3. Show that (b) does not hold for grid-based series. How to characterize ?

Exercise 6.3.

1. Let be the set of transseries with for all and consider the space of operators

 (6.2)

such that is a grid-based. Show that operates on and that is stable under composition.

2. Let and consider the space of operators (6.2), such that is a grid-based family. Show that operates on and that is stable under composition.

## 6.2Strong tensor products

It is often useful to consider multilinear mappings

as linear mappings

A similar thing can be done in the strongly linear setting. We will restrict ourselves to the case when are grid-based modules, in which case the tensor product has a particularly nice form:

Proposition 6.6. Let be monomial sets and denote

Consider the mapping

This mapping is well-defined and strongly multilinear. Moreover, for every strongly multilinear mapping

into an arbitrary strong -module, there exists a unique strongly linear mapping

such that .

Lemma 6.7. Let be a grid-based family of monomials in . Then there exist grid-based families with .

Proof. Let be the projection of on , for . We have for certain and . Given , we will denote

Given , we define its multiplicity by

Given , let

Then for all , we have

Hence

for ().

Proof of proposition 6.6. Given grid-based subsets with the set is clearly a grid-based subset of . This implies that is well-defined. More generally, given grid-based families of terms , the family is again grid-based. Now consider arbitrary grid-based families and let , for . Then

This shows that is multilinear.

Inversely, if is a grid-based subset of , then its projections on for are again grid-based, and we have

Consequently, given a strongly multilinear mapping

the mapping

is well-defined. Moreover, if , then the above lemma implies that there exist with , whence

It follows that and are summable families in . Finally, using strong associativity, we have

We conclude that .

We call (together with the mapping ) the strong tensor product of . An immediate consequence of proposition 6.6 is the principle of extension by strong multilinearity:

Corollary 6.8. Let and be monomial monoids and assume that is a mapping, such that

is a grid-based family for any grid-based subsets . Then there exists a unique strongly multilinear mapping

with .

Proof. Using extension by strong linearity, there exists a unique strongly linear mapping , with . Then is the unique mapping we are looking for.

Exercise 6.4. When do we have , where denotes the space of strongly linear mappings from into ?

Exercise 6.6.

1. Generalize proposition 6.6 to the case of well-based series.

2. Show that a well-based family corresponds to an element of .

3. Define a family to be super-grid-based with and . Show that is a strong -algebra for super-grid-based summation.

4. Give an example of a grid-based family which is not super-grid-based.

Exercise 6.7. Show that tensor products exist in the general strongly linear setting (see also exercise 2.20). Hint:

1. Let be strong modules. Consider the set of all mappings , whose support is contained in a set such that each is a summable subset of . Construct a natural embedding and give the structure of a strong -module.

2. Let be the strong submodule of , which is generated by all elements of the form

where the are mutually disjoint. Then the strong quotient

with satisfies the universal property of the strong tensor product.

## 6.3Grid-based operators

### 6.3.1Definition and characterization

Let and be monomial sets. A mapping is said to be a grid-based operator if there exists a family of multilinear grid-based operators , such that for all , the family is grid-based, and

 (6.3)

We call a multilinear family for . Considering the family of a single element , the formula (6.3) reduces to

Assuming that , each is uniquely determined and we call it the homogeneous part of degree of :

Proposition 6.9. Let be a grid-based operator and let be multilinear grid-based operators, such that (6.4) holds for all . If and , then for each .

Proof. We observe that it suffices to prove that for each , since the are symmetric and is torsion-free. Assume the contrary and let be such that for some . Choose

Since is a grid-based family, there exist only a finite number of indices , such that . Let be those indices.

Let for all . For any , we have , by multilinearity. On the other hand,

for each , so that

The matrix on the left hand side admits an inverse with rational coefficients (indeed, by the sign rule of Descartes, a real polynomial cannot have distinct positive zeros unless ). Since , it follows that . This contradiction completes the proof.

Proposition 6.10. Let be a grid-based operator and assume that . Then there exist a unique multilinear family for , such that each is symmetric.

Proof. Let be an arbitrary multilinear family for . Then the defined by

form a multilinear family of symmetric operators for . Moreover, each is determined uniquely in terms of by

We conclude by proposition 6.9.

Assume that and are subsets of a common monomial group . If we have and and are as in proposition 6.10, then we call

the operator support of . For all , we have

Notice also that for all .

### 6.3.2Multivariate grid-based operators and compositions

In a similar way that we have the natural isomorphism

for tensor products, we also have a natural isomorphism

for Cartesian products. This allows us to reinterpret mappings “in several series” as mappings “in one series” . In particular, any multilinear grid-based operator can be seen as a grid-based operator in from into . More generally, the natural isomorphism may be used in order to extend the notion of grid-based operators to mappings .

Let and be two grid-based operators. Then is again a grid-based operator. Indeed, let and be multilinear families for and . Then for all , we have

so that the defined by

form a multilinear family for .

Exercise 6.8. Assume that and let be a grid-based operator. Is it true that for any there exists an with ?

Exercise 6.9. Define the “derivative” of a grid-based operator .

Exercise 6.10.

1. Characterize the intervals of the set of infinitesimal transmonomials (i.e. for all and , we have ), such that for all , the operator is a grid-based operator on .

2. With as in (a), show that the operators and are grid-based.

## 6.4Atomic decompositions

### 6.4.1The space of grid-based operators

Let be the space of strongly multilinear operators . Then is clearly a -module. More generally, a family of elements in is said to be summable, if for all , we have

In that case, we define the sum by

This gives the structure of a strong -module.

Similarly, let denote the space of grid-based operators . This space is clearly a -module. A family is said to be summable, if for all , the family

is a grid-based family. In that case, the sum

is a grid-based operator and is a strong -module for this summation. In particular, we have

 (6.5)

for all . We call (6.5) the decomposition of into homogeneous parts.

### 6.4.2Atomic decompositions

Let and be monomials sets. Given and , the operator

with

is an -linear grid-based operator. Operators of this form, which are said to be atomic, form a strong basis of , since any operator may be uniquely decomposed as

 (6.6)

We call (6.6) the atomic decomposition of . More generally, an atomic family is a summable family , with and , where and .

Assume now that . Given a grid-based operator , let the be as in proposition 6.10. Then we have

 (6.7)

and we call this formula the atomic decomposition of . More generally, a family , where and , is called an atomic family, if the family is summable in .

Since the in (6.7) are symmetric, the atomic decomposition is slightly redundant. Let be the equivalence relation on , such that if and only if and there exists a permutation of indices , such that for all . Given , and , we define

Clearly, does not depend on the choice of and operators of the form will be called symmetric atomic operators. Setting

for all , the decomposition

is unique. We call it the symmetric atomic decomposition of .

### 6.4.3Combinatorial interpretation of atomic families

Consider an atomic family with for each . We may interpret the as combinatorial boxes with inputs and output . We define a partial ordering on by . Given a subset of , we denote by the atomic family of all with . Finally, given a monomial set , we denote by the atomic family , so that is the identity operator on .

Remark 6.11. A convenient way to check whether a family is atomic is to prove that for each grid-based subset we have

1. The set is grid-based.

2. For each , there exist only a finite number of with .

Consider two atomic families and , where and for all and . We define their composition to be the family with formal index set

and

We may see the as combinatorial structures, such that the outputs of the coincide with the inputs of (see figure 6.1). A similar computation as at the end of section 6.3.2 yields:

Proposition 6.12. Let and be two atomic families as above. Then is again an atomic family and

 Fig. 6.1. Combinatorial interpretation of the composition of atomic operators.

Exercise 6.11. Show that the mapping

from exercise 6.1 is a strong -algebra morphism.

Exercise 6.12. Show that and are naturally isomorphic as sets. Show that this natural isomorphism also preserves the strong -module structure.

Exercise 6.13. Show that an atomic family is summable, if and only if is grid-based for every grid-based subset .

Exercise 6.14. Generalize the theory from sections 6.3 and 6.4 to the well-based setting.

## 6.5Implicit function theorems

Let and be monomial sets which are contained in a common monomial monoid. Consider a grid-based operator

together with its atomic decomposition . We say that

• is strictly extensive in if whenever .

• is extensive in with multipliers in a set , if whenever .

• is contracting in if for all and . Here we write if for all , there exists an with .

If is strictly extensive in , then we have in particular

for all , and . Consequently, is also contracting in , since , whenever , and are such that for all .

Given a grid-based operator as above, the aim of the implicit function theorems is to construct a grid-based operator , such that

 (6.8)

for all . In the well-based context, a sufficient condition for the existence (and uniqueness) of such an operator is the strict extensiveness of in . In the grid-based context we need additional conditions in order to preserve the grid-based property. In this section, we present three possible choices for these extra conditions, which lead each to a grid-based implicit function theorem.

### 6.5.1The first implicit function theorem

Theorem 6.13. Consider a grid-based operator

which is extensive in with multipliers in a grid-based set . Then for each , there exists a unique which satisfies (6.8) and the operator is grid-based. Furthermore, for all , we have

If , then we also have

Proof. Let be the atomic decomposition of . Consider the family , where the are recursively defined by

See figure 6.2 for the illustration of a member of . We claim that is an atomic family. Indeed, let be a grid-based set. Let us prove by induction over that

 (6.9)

for all . This is clear if . If , then we may write , where for at least one . By the induction hypothesis, we have , so that . This shows that . Moreover, given , there are only a finite number of with . It follows that is an atomic family, by remark 6.11 and the fact that each is atomic.

 Fig. 6.2. Illustration of a member of . The white dots correspond to elements of and the black dots to elements of . The light boxes belong to and the dark ones to .

Now consider the grid-based operator

Identifying and via the natural isomorphism, we have

for all . Similarly, for all , we have

Applying proposition 6.12, we conclude that

for all . As to the uniqueness of , assume that are such that and . Then we have

which is only possible if .

Let us finally prove the bounds on the supports. The first one follows directly from (6.9). The second one follows from the fact that the operator support of an element in is the product of the operator supports of all combinatorial boxes on the nodes of the corresponding tree.

### 6.5.2The second implicit function theorem

Theorem 6.14. Consider a grid-based operator

such that

is grid-based and infinitesimal for all . Then, for each , there exists a unique which satisfies (6.8) and the operator is grid-based.

Proof. Let , with support . There exist finite sets and , such that . Let

Then we have and

We now observe that maps into itself, so we may apply theorem 6.13 to this mapping with the same . This proves the existence and uniqueness of . With similar notations as in theorem 6.13, it also follows that is again a grid-based atomic family, so that is a grid-based operator.

### 6.5.3The third implicit function theorem

Theorem 6.15. Consider a grid-based operator

which is strictly extensive in . Assume that

is grid-based and . Then for each , there exists a unique which satisfies (6.8) and the operator is grid-based.

Proof. With the notations of the proof of theorem 6.13, let us first show that is a well-based family for every grid-based set . For each , let . To each , we associate a tree , by setting if , and

for . Since is strictly extensive in , this mapping is strictly increasing. Furthermore, the inverse image of each tree in is finite and is well-based by Higman's theorem. This together implies that is well-based.

Let us show that is actually a grid-based. For each tree , let , so that for all . Now consider

Let be the finite subset of -maximal elements of . Notice that we may naturally interpret elements

as trees

Given a grid-based set and , let us denote

Consider

We claim that satisfies the hypothesis of theorem 6.13.

Indeed, consider and let us show by induction over that for every with . Now

for some . In other words, there exists an embedding which fixes the root. Consider a factorization of this embedding through a tree with , such that for all with , and such that

is minimal. Assume for contradiction that . We distinguish three cases:

Case 1
for some .

Consider the tree with the same nodes as and if and . Then we may factor through with and .

Case 2
for some .

Let be a child of whose root is not in the image of . Then we may factor through a tree which is obtained by adding as a child to at the appropriate place, in such a way that . Moreover, since , the induction hypothesis implies that , so that .

Case 3
we are not in cases 1 and 2.

Since , there exists a with a successor . Let be the children of , so that is the root of for some . Consider the tree which is obtained by substituting the subtree of with root by

By the induction hypothesis, we have , so that . Furthermore, we may factor through in such a way that .

In each of these three cases, we have thus shown how to obtain a factorization through a tree with and . This contradiction of the minimality assumption completes the proof of our claim. We conclude the proof by applying theorem 6.13 and by noticing that is grid-based, so that is a grid-based operator.

Exercise 6.15. Give an example of a contracting mapping which is not strictly extensive.

Exercise 6.16. In the first implicit function theorem, show that the condition that has multipliers in a grid-based set cannot be omitted. Hint: consider the equation .

Exercise 6.17. Give an example where the second implicit function theorem may be applied, but not the first. Also give an example where the third theorem may be applied, but not the second.

Exercise 6.18. Prove the following implicit function theorem for well-based series:

Let be a well-based operator which is extensive in . Then for each , there exists a unique which satisfies (6.8) and the operator is well-based.

## 6.6Multilinear types

One obtains interesting subclasses of grid-based operators by restricting the homogeneous parts to be of a certain type. More precisely, let be a monomial monoid and let be a set of strongly multilinear mappings . We say that is a multilinear type if

MT1
The constant mapping is in , for each .

MT2
The projection mapping is in , for each .

MT3
The multiplication mapping is in .

MT4
If , then .

Given subsets of , we say that a strongly multilinear mapping

is an atom of type , if for , there exists a mapping in , such that coincides with the restriction of the domain and image of to resp. . We say that is of type , if is the sum of a grid-based family of atoms of type . A grid-based operator

is said to be of type , if is of type for all .

Example 6.16. For any set of grid-based operators , there exists a smallest multilinear type which contains . Taking to be the field of grid-based transseries, interesting special cases are obtained when taking or . Grid-based operators of type resp. are called differential resp. integral grid-based operators.

Exercise 6.19. Show that compositions of grid-based operators of type are again of type .

Exercise 6.20. State and prove the implicit function theorems from the previous section for grid-based operators of a given type .

Exercise 6.21. For which subfields of and do the grid-based operators of types and coincide?

 7

Linear differential equations

Let be a linear differential operator with transseries coefficients and . In this chapter, we study the linear differential equation

 (7.1)

In our grid-based context, it is convenient to study the equation (7.1) in the particular case when and can be expanded w.r.t. a plane transbasis . In order to solve the equation , we necessarily need to consider solutions in . Therefore, we will regard as an operator on . Assuming that we understand how to solve (7.1) for and and assuming that we understand how this resolution depends on and upward shiftings, the incomplete transbasis theorem will enable us to solve (7.1) in the general case.

A first step towards the resolution of (7.1) is to find candidates for dominant terms of solutions . It turns out that the dominant monomial of only depends on the dominant term of , except if , where is a finite set of “irregular” monomials. The corresponding mapping is called the trace of , and its properties will be studied in section 7.3. In particular, we will show that is invertible.

In section 7.4 we will show that the invertibility of the trace implies the existence of a strong right inverse of . Moreover, the constructed right inverse is uniquely determined by the fact that for all (for which we call it “distinguished”). Furthermore, we may associate to each a solution to the homogeneous equation and these solutions form a “distinguished basis” of the space of all solutions.

Now finding all solutions to (7.1) it equivalent to finding one particular solution and the space of solutions to the homogeneous equation. Solving the homogeneous equation is equivalent to solving the Riccati equation

 (7.2)

which is an algebraic differential equation in (see section 7.2). In section 7.5, we will show that (7.2) is really a “deformation” of the algebraic equation , so we apply a deformation of the Newton polygon method from chapter 3 to solve it. In fact, we will rather solve the equation “modulo ”, which corresponds to finding the dominant monomials in of solutions to the homogeneous equation (see section 7.6).

Of course, an equation like does not admit any non-trivial solutions in the transseries. In order to guarantee that the solution space of the homogeneous equation has dimension , we need to consider transseries solutions with complex coefficients and oscillating monomials. In section 7.7 we will briefly consider the resolution of (7.1) in this more general context. In section 7.8 we will also show that, as a consequence of the fact that , we may factor as a product of linear operators.

## 7.1Linear differential operators

### 7.1.1Linear differential operators as series

Let be the field of grid-based transseries in over a real-closed exp-log field of constants . In what follows, it will often be convenient to regard linear differential operators as elements of . In particular, each non-zero operator admits a dominant monomial

and a dominant coefficient

for which we will also use the alternative notation

Similarly, the asymptotic relations , , , , etc. extend to . In order to avoid confusion with the support of as an operator, the support of as a series will be denoted by .

Proposition 7.1. Given with , we have

Proof. Without loss of generality, one may assume that , modulo division of by . Then

Now each term in the big sum at the right hand side is infinitesimal.

### 7.1.2Multiplicative conjugation

Given a linear differential operator and a non-zero transseries , there exists a unique linear differential operator , such that

for all . We call a multiplicative conjugate of . Its coefficients are given by

 (7.3)

Notice that for all .

Proposition 7.2. If , then

Proof. From it follows that for all . Then (7.3) implies . Conversely, we have

### 7.1.3Upward shifting

In order to reduce the study of a general linear differential equation over the transseries to the case when the coefficients are exponential, we define the upward shifting and downward shifting of to be the unique operators with

for all . In other words, the resolution of is equivalent to the resolution of . The coefficients of and are explicitly given by

where the are Stirling numbers of the first resp. kind, which are determined by

Upward and downward shifting are compatible with multiplicative conjugation in the sense that

for all . We will denote by resp. the -th iterates of and .

Exercise 7.1. Let and .

1. Show that there exists a unique with

for all .

2. Give an explicit formula for for each .

3. Show that is a ring homomorphism.

Exercise 7.3. Let and . Denote by the field with differentiation .

1. Show that each can be reinterpreted as an operator .

2. Given , let be the result of the substitution of for in . If , then show that .

Exercise 7.4. Let and , so that .

1. Given (see exercise 6.3), let . Show that naturally operates on . Also show that the space of all such operators only depends on .

2. Same question, but for .

3. Under which condition on can the operator in either of the above questions be rewritten as an operator of the form ?

Exercise 7.5. Let be a flat subspace of .

1. Extend the definition of in exercises 6.3 and 7.3 to the present case.

2. Let be two flat subspaces of of the above type. Characterize .

Exercise 7.6. Let .

1. Determine so that .

2. Given , construct the -th iterate of .

3. Determine the maximal flat subspace of such that .

Exercise 7.7. Let . Consider an operator

where .

1. Show that and let be such that .

2. Assuming that , show that there exists a with .

Exercise 7.8. Let be as in exercise 7.3(a) or (b), and .

1. Given with and . Show that

are well-defined.

2. Let , , and . Show that

are well-defined.

3. Given a transmonomial with and , show that

is well-defined. Extend the definition of to and show that corresponds to the distinguished integration.

## 7.2Differential Riccati polynomials

### 7.2.1The differential Riccati polynomial

Given a transseries , we may rewrite the successive derivatives of as

 (7.6)

where the are universal differential polynomials given by

For instance:

In particular, for each linear differential operator , there exists a unique differential polynomial such that

 (7.7)

for all . We call the differential Riccati polynomial associated to . Notice that is uniquely determined by the polynomial

which is called the algebraic part of .

### 7.2.2Properties of differential Riccati polynomials

Let be a differential polynomial with transseries coefficients. Like in the case of differential operators, we may consider as a series in , where denotes the set of transmonomials. Given we also define to be the unique differential polynomial in , such that

for all . We call an additive conjugate of . Additive conjugates of the differential Riccati polynomials correspond to multiplicative conjugates of the corresponding linear differential operators:

Proposition 7.3. For all and , we have

 (7.8)

Proof. For all , we have

so (7.8) follows from the uniqueness property of differential Riccati polynomials.

Given a linear differential operator , we call

the derivative of .

Proposition 7.4. For all , we have

Proof. We claim that for all . Indeed, and, using induction,

for all . Our claim immediately implies (7.9) and (7.10).

Corollary 7.5. For all and , we have

Exercise 7.9. Prove that

Exercise 7.10. Show that

where and are defined in section 8.2.3.

## 7.3The trace of a linear differential operator

Let be a linear grid-based operator. A term is said to be regular for , if is regular for all with and if does not depend on the choice of such an . In particular, a monomial in is said to be regular for if it is regular as a term. We will denote by the set of all regular monomials for and by the set of irregular monomials. The mapping

is called the trace of . For all , we have

 (7.13)

Given a linear differential equation over the transseries with , finding a term with corresponds to finding a good candidate for the first term of a solution. In the next section we will show that this first term may indeed be completed into a full solution.

### 7.3.1The trace relative to plane transbases

Let be a linear differential operator, where is a plane transbasis. We will consider as a grid-based operator on , so that its trace is a mapping from into .

Proposition 7.6. Given , we have

Proof. Modulo replacing by , we may assume without loss of generality that and . Let be minimal with , so that if and only if .

Now implies . Furthermore, for all but the finite number of such that . It follows that for a sufficiently small , whence .

If , then . Given with , we have either or with . In the first case, . In the second case, we have either and or and . So we always have . Hence , by strong linearity.

Proposition 7.7. For every there exists a unique with .

Proof. Let and consider . We will prove the proposition by induction over the maximal such that . If such an does not exist, then we have nothing to prove. Otherwise, proposition 7.2 implies

It follows that for certain . By the induction hypothesis, there exists an with . Hence for . Furthermore, given , we have . This proves the uniqueness of .

Proposition 7.8. The trace of is invertible.

Proof. Let . By the previous proposition, there exists a unique with . Modulo the replacement of by we may assume without loss of generality that . Let be minimal with . Then

Setting

we thus have . Notice that proposition 7.6 implies .

Example 7.9. Let and consider the operator

Given and , we have

Now the following cases may occur:

### 7.3.2Dependence of the trace on the transbasis

Let , where is a plane transbasis and let us study the dependence of the trace of on . Given a plane supertransbasis of , proposition 7.6 implies that and clearly coincides with on . Similarly, if is a second transbasis such that and coincide as subsets of , then and , where denotes the “identification mapping”.

Proposition 7.10. Let . Then and for all .

Proof. We clearly have

for all . Given

let us show that . Modulo replacing by , we may assume without loss of generality that and .

Assume that , so that , and . Then implies and . Hence . Since , we also observe that , whence . But this means in particular that

In other words, .

Assume now that and let be minimal with . Then so

On the other hand, , whence . This is only possible if and . In other words, .

Proposition 7.11. Let be a transbasis of level containing and denote . Let and let be the set of singular monomials of as an operator on . Then

Proof. Clearly, . Assume for contradiction that there exists an . Then there exists an with and . Let be a super-transbasis of for , of level , and which contains . Setting , proposition 7.10 now implies

Hence, so that . This contradiction completes the proof.

Proposition 7.12. Let be a linear differential operator on . Then the trace of is invertible.

Proof. Given , the incomplete transbasis theorem implies that there exists a transbasis for like in proposition 7.11. By proposition 7.8, there exists an with . By proposition 7.11, we have and .

### 7.3.3Remarkable properties of the trace

Assume again that , where is a plane transbasis.

Proposition 7.13. The set

is finite.

Proof. Considering as indeterminates, the successive derivatives of satisfy

where the are as in (7.6). Consequently, we may see

as an element of for each .

Assume for contradiction that is infinite. Since , there exists an infinite sequence of elements in . For each , let be such that . Now each induces an ideal of , generated by all coefficients of with . We have and each is a zero of , but not of . It follows that , which contradicts the Noetherianity of .

Corollary 7.14. There exist unique strongly linear mappings

which extend and . Furthermore,

1. and .

2. and .

Proposition 7.15. Given , we have

and

Proof. Let . Then for all , we have and . By strong linearity, it follows that for all with . This shows that and .

Conversely, let and assume that . Then for all with . If , then proposition 7.6 implies and for all . Hence and we may choose so that . But then and . If satisfies , then we clearly have .

Similarly, let and denote . Then for all with . Moreover, we may choose such that and for all . This ensures that . Denoting , we conclude that , whence .

As to second identity, let . Then and implies . Hence .

Exercise 7.11. Prove the propositions of section 7.3.3 for operators .

Exercise 7.12. Generalize the results from this section to the well-based setting.

Exercise 7.13. Let . Determine .

## 7.4Distinguished solutions

Let and be monomial sets, such that is totally ordered. Given a linear grid-based operator and , we say that is a distinguished solution to the equation

 (7.14)

if for any other solution , we have . Clearly, if a distinguished solution exists, then it is unique. A mapping is said to be a distinguished right inverse of , if and is a distinguished solution solution to (7.14) for each . A distinguished solution to the homogeneous equation

 (7.15)

is a series with and for all other solutions with . A distinguished basis of the solution space of (7.15) is a strong basis which consists exclusively of distinguished solutions. If it exists, then the distinguished basis is unique.

Remark 7.16. Distinguished solutions can sometimes be used for the renormalization of “divergent” solutions to differential equations; see [vdH01b] for details.

### 7.4.1Existence of distinguished right inverses

Theorem 7.17. Assume that the trace is invertible and both and extend to strongly linear mappings

Assume also that and are grid-based. Then

1. admits a distinguished and grid-based right inverse

2. The elements with form a distinguished basis for .

Proof. Let . Then the operator is strictly extensive, and the operator coincides with on . Now consider the functional

By theorem 6.14, there exists a strongly linear operator

such that for all . Consequently,

is a strongly linear right inverse for . Given , we also observe that ; otherwise, . Consequently, is the distinguished solution of (7.14) for all . This proves (a).

As to (b), we first observe that

for all . The solution is actually distinguished, since

and for all . In fact, we claim that

 (7.16)

Indeed, if , then we would have , so

which is impossible. Now let be an arbitrary solution to (7.15) and consider

Then we have for all , by the distinguished property of the and (7.16). Consequently, . This proves (b).

Corollary 7.18. Let be a plane transbasis and let be a linear differential operator on . Then admits a distinguished right inverse and admits a finite distinguished basis.

Proof. In view of proposition 7.8 and corollary 7.14, we may apply theorem 7.17. By general differential algebra, we know that is finite dimensional.

Corollary 7.19. Let be a linear differential operator on . Then admits a distinguished right inverse and admits a finite distinguished basis.

Proof. Given , let us first prove that admits a distinguished solution. Let be a transbasis for as in proposition 7.11 and consider . Then

From proposition 7.11, it follows that

for all

Hence is the distinguished solution to . In particular, the construction of is independent of the choice of . The operator is strongly linear, since each grid-based family in is also a family in for some as above, and is strongly linear on .

Example 7.20. With as in example 7.9, we have

### 7.4.2On the supports of distinguished solutions

Let be a plane transbasis and let be a linear differential operator on of order .

Proposition 7.21. The operator support of is bounded by

where

are grid-based sets and .

Proof. With the notations from the proof of theorem 7.17,

It follows that

Recall that is finite, by proposition 7.13. This also implies that is grid-based.

Proposition 7.22. Given , let

Setting , we have

1. maps into .

2. maps into .

3. .

Proof. For all , we have

This shows (a). As to (b), let and consider

Then is a bijection between and and maps into . By theorem 7.17, it follows that the restriction of to admits a distinguished right inverse, which necessarily coincides with the restriction of to . This proves (b), since and . Moreover, for each element of the distinguished basis of , we have . This proves (c).

Exercise 7.14. Show that .

Exercise 7.15. Show that we actually have in proposition 7.22(c).

Exercise 7.17. Let and be plane transbases in the extended sense of exercise 4.15. Given , let denote the distinguished right inverse of as an operator on .

1. Show that is the restriction of to , if is a supertransbasis of .

2. If , then show that if and only if .

3. If , then show that for all .

Exercise 7.18. Let be a flat subspace of and the steep complement of , so that . Consider as a strong operator on (notice that is not -linear). Let be the set of monomials such that does not depend on and such that the mapping is invertible.

1. Exhibit an operator in which maps to and relate and .

2. Generalize theorem 7.17 to the setting of strongly additive operators and relate the distinguished right inverses of as an operator on and as an operator on .

3. Given a plane transbasis , and , give a concrete algorithm to compute the recursive expansion of .

Exercise 7.19. Let and let be a transmonomial. Prove that

Exercise 7.20. Let and . When do we have

Here is the unique operator such that

for all .

Exercise 7.22.

1. Show that for and .

2. Show that for and .

3. Do we always have ?

Exercise 7.23.

1. Prove that each non-zero admits a distinguished right-inverse on .

2. Can be infinite?

3. Same questions for .

Exercise 7.24. Consider an operator as in exercise 7.6.

1. For any , show that is an operator of the same kind.

2. Show that admits a distinguished right-inverse on .

3. Assuming that , show that admits a distinguished right-inverse on .

4. Given , show that admits a distinguished solution, which is not necessarily grid-based, but whose support is always well-based and contained in a finitely generated group.

5. Show that (d) still holds if .

6. Given a general , show that admits a well-based distinguished solution.

7. Give a bound for the cardinality of .

Exercise 7.25. Let be the space of partial grid-based operators , such that is a space of finite codimension over in . Two such operators are understood to be equal if they coincide on a space of finite codimension in .

1. Show that is a -algebra under composition.

2. Show that each induces a unique operator in with .

3. Show that the skew fraction field of in consists of operators with and . Hint: show that for any with , there exist with and .

Exercise 7.26. Let , where denotes the field of exponential transseries.

1. If , then show that there exists a decomposition

with , and .

2. If and is sufficiently small, then show how to define .

3. Given , extend the definition of from exercise 7.7(c) to a definition of on a suitable strong subvector space of .

## 7.5The deformed Newton polygon method

Let be a linear differential operator and consider the problem of finding the solutions to the homogeneous equation . Modulo upward shiftings it suffices to consider the case when the coefficients of can all be expanded w.r.t. a plane transbasis . Furthermore, theorem 7.17 and its corollaries imply that it actually suffices to find the elements of .

Now solving the equation is equivalent to solving the equation for . As we will see in the next section, finding the dominant monomials of solutions is equivalent to solving the “Riccati equation modulo

 (7.17)

for . It turns out that this equation is really a “deformation” of the algebraic equation

 (7.18)

In this section, we will therefore show how to solve (7.17) using a deformed version of the Newton polygon method from chapter 3.

### 7.5.1Asymptotic Riccati equations modulo

Let is a plane transbasis and . We regard as a linear differential operator on . Given , consider the asymptotic versions

 (7.19)

and

 (7.20)

of (7.17) resp. (7.18). We call (7.19) an asymptotic Riccati equation modulo . A solution of (7.19) is said to have multiplicity , if for all and .

Given , we notice that for all ,

 (7.21)

We say that is a starting monomial of relative to (), if is a starting monomial of relative to (7.20). Starting terms of solutions and their multiplicities are defined similarly. The Newton degree of () is defined to be the Newton degree of (7.20). The formula (7.21) yields the following analogue of proposition 3.4:

Proposition 7.23. If is a solution to (7.19), then is a starting term of relative to (7.19).

Proof. Assume the contrary, so that there exists an index with for all . But then

for all . Hence

and similarly

for all . In other words,

and .

### 7.5.2Quasi-linear Riccati equations

We say that () is quasi-linear if its Newton degree is one (i.e. if (7.20) is quasi-linear). We have the following analogue of lemma 3.5:

Proposition 7.24. If () is quasi-linear, then it admits a unique solution .

Proof. Let and consider the well-based operator

Since () is quasi-linear, we have

 (7.22)

for all and . Moreover, on we have . Since is a differential polynomial of degree , we thus have

 (7.23)

when considering as an operator on . Combining (7.22) and (7.23), we conclude that

for all with . By theorem 6.14, it follows that the equation

 (7.24)

admits a unique fixed point in . We claim that this is also the unique solution to ().

Let us first show that is indeed a solution. From (7.24), we get

 (7.25)

On the other hand, we have for :

In other words, and . Assume finally that is such that . Then (7.25), (7.26) and (7.27) also imply that

In other words, .

### 7.5.3Refinements

Given a refinement

 (7.28)

where and , the equation (7.19) becomes

 (7.29)

where satisfies . We recall that the coefficients of the corresponding algebraic equation

 (7.30)

are given by

Let us show that the analogues of lemmas 3.6 and 3.7 hold.

Proposition 7.25. Let . Then the Newton degree of

 (7.31)

equals the multiplicity of as a starting term of relative to ().

Proof. For a certain transmonomial , the Newton polynomial relative to is given by

Then, similarly as in the proof of lemma 3.6, we have

for all , and we conclude in the same way.

Proposition 7.26. Let be the Newton degree of (). If admits a unique starting term of multiplicity , then

1. The equation

 (7.32)

is quasi-linear and has a unique solution with .

2. Any refinement

 (7.33)

transforms (7.32) into an equation of Newton degree .

Proof. Part (a) follows immediately from lemma 3.7(a) and the fact that . Now consider a refinement (7.33). As to (b), let be such that the the Newton polynomial associated to is given by

By the choice of , we have

It follows that the term of degree in vanishes, so cannot admit a root of multiplicity . We conclude by proposition 7.25.

### 7.5.4An algorithm for finding all solutions

Putting together the results from the previous sections, we obtain the following analogue of