
Foreword 
XI 
Introduction 
1 
The field with no escape 
1 
Historical perspectives 
3 
Outline of the contents 
7 
Notations 
10 
1Orderings 
11 
1.1Quasiorderings 
12 
1.2Ordinal numbers 
15 
1.3Wellquasiorderings 
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 
2Gridbased series 
33 
2.1Gridbased sets 
34 
2.2Gridbased 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.1Setlike notations for families 
44 
2.4.2Infinitary operators 
45 
2.4.3Strong abelian groups 
46 
2.4.4Other strong structures 
47 
2.5Gridbased summation 
48 
2.5.1Ultrastrong gridbased algebras 
48 
2.5.2Properties of gridbased 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 explog fields 
80 
4.2Fields of gridbased transseries 
84 
4.3The field of gridbased 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 
6Gridbased operators 
115 
6.1Multilinear gridbased operators 
116 
6.1.1Multilinear gridbased operators 
116 
6.1.2Operator supports 
117 
6.2Strong tensor products 
118 
6.3Gridbased operators 
122 
6.3.1Definition and characterization 
122 
6.3.2Multivariate gridbased operators and compositions 
123 
6.4Atomic decompositions 
124 
6.4.1The space of gridbased 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.2Quasilinear 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.1Additive conjugation 
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.5Quasilinear 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 slowdown 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 gridbased 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 nonserial 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 quasilinear 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 
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 16th 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 nonlinear 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 nonspecialists. The book is selfcontained 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 gridbased transseries, which is sufficiently general for solving differential equations, but less general than the wellbased 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 accelerosummation 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.
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 accelerosummation of transseries, as developed by Écalle [É92, É93], is far more complex, and beyond the scope of this book. Nevertheless, it is important to remember that such a theory exists: even though the transseries studied in this this book are purely formal, they generally correspond to genuine analytic functions.
The attentive reader may have noticed another interesting property which is satisfied by some of the transseries (1–8) above: we say that a transseries is gridbased, if
The examples (1–5) are gridbased. For instance, for (2), we may take and . The examples (6–8) are not gridbased, but only wellbased. 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 gridbased coefficients are necessarily gridbased as well. This immediately implies that the examples (6–8) are differentially transcendental over (see also [GS91]). The fact that gridbased transseries may be considered as multivariate Laurent series also makes them particularly useful for effective computations. For these reasons, we will mainly study gridbased transseries in this book, although generalizations to the wellbased 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
Historically speaking, transseries have their origin in several branches of mathematics, like analysis, model theory, computer algebra and nonarchimedean geometry. Let us summarize some of the highlights of this interesting history.
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 18th 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 multivalued 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 19th century, criteria for convergence of power series were studied in a more systematic way. In particular, Cauchy and Kovalevskaya developed the wellknown 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 20th century [Har63], it went out of fashion later on.
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 DuboisRaymond, Poincaré and Hardy.
More general asymptotic scales than those of the form , or were introduced by DuboisRaymond [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 20th century and Écalle's work on transseries and Dulac's conjecture [É85, É92, É93, Bra91, Bra92, CNP93].
His theory of accelerosummation 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 accelerosummable transseries seems to correspond to the “frameworkwithnoescape” about which Borel and Hardy may have dreamed.
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 20th century mathematics: proving the completeness and decidability of various mathematical theories.
Gödel's undecidability theorem and the undecidability of arithmetic are wellknown results in this direction. More encouraging were the results on the theory of the field of real numbers by ArtinSchreier and later TarskiSeidenberg [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 modeltheoretical introduction of the field of transseries as a good candidate of a nonstandard 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 ominimal 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 RittSeidenberg'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.
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 “explog” 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 accelerosummation 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.
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 nonstandard version of the real line. However, contrary to the real numbers, the transseries also come with a nontrivial 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 growthrate functions and numbers.
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 wellquasiorderings 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 gridbased series” , where is a so called monomial monoid with a partial quasiordering . Polynomials, ordinary power series, Laurent series, Puiseux series and multivariate power series are all special types of gridbased series. In general, gridbased 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”. Gridbased 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 gridbased sets. For this reason, it is convenient to develop the theory of gridbased 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 gridbased setting. Our exposition is based on the systematic consideration of “asymptotic equations”, which are equations with asymptotic sideconditions. 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 gridbased transseries in over an “ordered explog 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 explog 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 modeltheoretical 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 gridbased 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 modeltheoretical point of view. In section 5.4.2, we also prove the Translagrange theorem due to Écalle, which generalizes Lagrange's wellknown 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 gridbased series. In chapter 6, we develop a “functional analysis” for gridbased series, based on the concept of “gridbased operators”. Strongly multilinear operators are special cases of gridbased operators. In particular, multiplication, differentiation and integration of transseries are gridbased operators. General gridbased operators are of the form
where each is a strongly linear operator. The set of gridbased 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 wellknown 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 rightinverse , with the property that when is the dominant monomial of a solution to . Similarly, we will construct distinguished bases of solutions and distinguished factorizations.
Nonlinear 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 nonzero 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 signchange on . The main part of the chapter contains a detailed study of the nonarchimedean 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 signchange occurs is shrunk further and further until we hit a root of .
A few remarks about the notations used in this book will be appropriate. Notice that a glossary can be found at the end.
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.
We systematically use the double index convention . Given a set of monomials, we also denote (this is an exception to the above notation).
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.
Intervals are denoted by , , or depending on whether the left and right sides are open or closed.
We systematically denote monomials in the fraktur font and families using calligraphic characters.
Those readers who are familiar with my thesis should be aware of the following notational changes which occurred during the past years:
There are also a few changes in terminology:
Former  New 
normal basis  transbasis 
purely exponential transseries  exponential transseries 
potential dominant 
starting 
privileged refinement  unravelling 
In this chapter, we will introduce some ordertheoretical 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 antilexicographical 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 wellordered. 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 wellordered sets and ordinal numbers in section 1.2. In what follows, our treatment will be based on wellquasiorderings, which are the analogue of wellorderings in the context of partial quasiorderings. In sections 1.3 and 1.4, we will prove some classical results about wellquasiorderings.
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 nonzero 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 .
Let be a set. In all what follows, a quasiordering on is reflexive and transitive relation on ; in other words, for all we have
An ordering is a quasiordering which is also antisymmetric:
We sometimes write instead of in order to avoid confusion. A mapping between two quasiordered sets is said to be increasing (or a morphism of quasiordered sets), if , for all .
Given a quasiordering , we say that are comparable if or . If every two elements in are comparable, then the quasiordering 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 quasiordering 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 quasiorderings instead of orderings, but it is sometimes more convenient to deal with quasiorderings.
Some simple examples of totally ordered sets are and . Any set can be trivially quasiordered both by the finest ordering, for which , and by the roughest quasiordering, for which all satisfy . In general, a quasiordering on is said to be finer than a second quasiordering on if for all . Given quasiordered sets and , we can construct other quasiordered sets as follows:
The disjoint union is naturally quasiordered, by taking the quasiorderings on and on each summand, and by taking and mutually incomparable. In other words,
Alternatively, we can quasiorder , by postulating any element in to be strictly smaller than any element in . This quasiordered set is called the ordered union of and , and we denote it by . In other words,
The Cartesian product is naturally quasiordered by
Alternatively, we can quasiorder antilexicographically by
We write for the corresponding quasiordered 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 quasiordering on is defined by , if and only if there exists a strictly increasing mapping , such that for all . For instance,
An equivalence relation on is said to be compatible with the quasiordering if
for all . In that case, is naturally quasiordered by
and the canonical projection is increasing.
If and are ordered sets, then it can be verified that the quasiorderings defined in 1–6 above are actually orderings.
Let be an increasing mapping between quasiordered sets and . Consider the quasiordering 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.
A strict ordering on is a transitive and antireflexive relation on (i.e. for no elements ). Given a quasiordering show that the relation defined by is a strict ordering. Show also how to associate an ordering to a strict ordering.
Let be a quasiordering on . Show that the relation defined by is also a quasiordering on ; we call it the opposite quasiordering of .
Let be a quasiordering on . Show that defines an ordering on . Show that is the roughest ordering which is finer than .
Exercise
and are commutative modulo (i.e. ), but not and .
and are associative modulo .
is distributive w.r.t. modulo .
is right (but not left) distributive w.r.t. modulo (in other words ).
Exercise
We define a quasiordering on by .
For all , we have if and only if there exists an injection with for all .
The equivalence relation is compatible with , so that we may order by the quotient quasiordering induced by .
The quasiordering is finer than and we have a natural increasing surjection .
For all ordered sets , prove that .
For all ordered sets prove that there exists an increasing bijection , whose inverse is not increasing, in general.
Prove that defines an ordering on . Also prove the following properties:
If , then .
If , then .
.
.
Exercise
Let be a quasiordered set. The quasiordering on is said to be wellfounded, if there is no infinite strictly decreasing sequence in . A total wellfounded ordering is called a wellordering. A total ordering is a wellordering if and only if each of its nonempty subsets has a least element. The following classical theorems are implied by the axiom of choice [Bou70, Mal79]:
Theorem
Theorem
An ordinal number or ordinal is a set , such that the relation forms a strict wellordering 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.
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 nonempty set of ordinals admits a least element for . The following classification theorem is also classical [Mal79]:
Theorem
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:
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
Exercise
Exercise
;
.
In particular, and are associative and is right distributive w.r.t. , by exercise 1.2.
Exercise
;
.
Do we also have ?
Let be a quasiordered set. A chain in is a subset of which is totally ordered for the induced quasiordering. An antichain is a subset of of pairwise incomparable elements. A wellquasiordering is a wellfounded quasiordering without infinite antichains.
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
is wellquasiordered.
Any final segment of is finitely generated.
The ascending chain condition w.r.t. inclusion holds for final segments of .
Each sequence admits an increasing subsequence.
Any extension of the quasiordering on to a total quasiordering on yields a wellfounded quasiordering.
Proof. Assume (a) and let be a final segment of and the subset of minimal elements of . Then is an antichain, 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 antichain 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 wellquasiordering. 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.
The most elementary examples of wellquasiorderings are wellorderings and quasiorderings on finite sets. Other wellquasiorderings can be constructed as follows.
Proposition
Any subset of with the induced ordering is wellquasiordered.
Let be a morphism of ordered sets. Then is wellquasiordered.
Any ordering on which extends is a wellquasiordering.
is wellquasiordered, for any compatible equivalence relation on .
and are wellquasiordered.
and are wellquasiordered.
Corollary
Theorem
Proof. Our proof is due to NashWilliams [NW63]. If denotes any ordering, then we say that is a bad sequence, if there do not exist with . A quasiordering is a wellquasiordering, 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
Exercise
Exercise
Exercise
Exercise
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
If is a quasiordered set, then the embeddability quasiordering 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
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 quasiordering on is a wellquasiordering. Indeed, suppose the contrary, and let
be a bad sequence. Let be such that is minimal. Then the sequence
Remark
Exercise
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 wellquasiordered subset of and the ordering on is wellquasiordered, then prove that is wellquasiordered.
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
for all . If is rather an additive monoid (in which case is assumed to be abelian), then OM becomes
An ordered ring is a ring with an ordering with the following properties:
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
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
Example
Example
Example
Similarly, the antilexicographical direct sum of and is with the antilexicographical quasiordering
If and are ordered, then so are and .
Example
Exercise
Show that , for all .
If is a total ordering, then show that there exists a unique total ordering on , which extends , and for which is an ordered field.
Show that , for all . In particular, if contains no nilpotent elements, then is an integral domain.
Show that may contain nilpotent elements.
Show that may contain zero divisors which are not nilpotent.
Show that positive nonnilpotent elements are larger than any nilpotent element in .
Exercise
and ;
and ;
and ;
, but not always .
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, pullbacks, pushouts, direct and inverse limits and free objects (i.e. the forgetful functor to the category of sets admits a right adjoint).
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.
What can be said about the operations and introduced above?
Exercise
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.
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 .
Generalize b to the case when is an ordered ring, which may contain nilpotent elements.
Give conditions in the cases when is an ordered module or an ordered algebra without nilpotent elements.
Exercise
Prove that is a quasiordering.
Show that is an ordering, if and only if can be extended into a total ordering on .
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 .
is said to be perfect if is a bijection. Prove that the closure of is perfect.
Show that an ordered abelian group is perfect if and only if , for all and .
Show that an ordered ring without nilpotent elements is perfect, if and only if , for all and , for all .
Under which conditions is an ordered module perfect? And an ordered algebra without nilpotent elements?
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 nonzerodivisors in . A dominance relation is a quasiordering on , such that for all , and , we have
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 antireflexive, transitive relation), such that for all and and , we have
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 .
Let be a dominance relation such that
the strict ordering associated to satisfies
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 .
Proposition
Moreover, if is totally ordered, then is associated to .
Proof. Let us first show that is a quasiordering. 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 .
If is a totally ordered ring, then cannot have zerodivisors, so its ring of quotients is a totally ordered field. Moreover, for any ordered, torsionfree module, the natural map is an embedding. This allows us to generalize proposition 1.18 to the case of totally ordered rings.
Corollary
Assume now that is an algebra. A dominance relation on is defined to be a quasiordering , which satisfies D1, D2 and for all :
A neglection relation on is a strict ordering , which satisfies N1, N2, N3, and for all and :
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 nonzero 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
Example
Given a totally ordered vector space over a totally ordered field , show that
Given a totally ordered module over a totally ordered ring , show that
Exercise
Exercise
Exercise
Exercise
Show that the valuations on correspond to total dominance relations.
Exercise
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.
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
Exercise
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
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 .
Exercise
Exercise
Exercise
Prove that each Hahn space of countable dimension admits a basis which is totally ordered w.r.t. .
Prove that there exist infinite dimensional Hahn spaces, which do not admit bases of pairwise comparable elements for .
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
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
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
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
is an asymptotic ring with powers for and .
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 quasiordering 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 .
Example
We may also take , in which case we define
For instance, if , then , and for all .
Exercise
Show that has a natural asymptotic algebra structure with powers.
Show that and are characterized by
Exercise
2 
Let be a commutative ring, and a quasiordered 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 gridbased 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 wellbased and one of the strongest conditions is that the supports be gridbased. 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 gridbased, whence it does not satisfy any algebraic differential equation with power series coefficients (as will be seen in chapter 8).
Actually, the setting of gridbased 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 gridbased 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 gridbased “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 gridbased families and strong linear algebra (see sections 2.4, 2.5.3 and 2.6), which have a very “partiallyordered” 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.
Let be a commutative, multiplicative monoid of monomials, quasiordered by . A subset is said to be gridbased, 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, gridbased sets are wellquasiordered for the opposite quasiordering of (carefully notice the fact that this is true for the opposite quasiordering of and not for itself). Actually, a gridbased set is even wellquasiordered for the opposite ordering of (recall that ). More generally, a subset of which has this latter property is said to be wellbased.
Proposition
Each finite set is gridbased.
is gridbased.
is gridbased.
If , then is gridbased.
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
Exercise
Wellbased subsets;
finite subsets, when is an ordered group with powers. Here an finite subset of is a wellbased subset, which is contained in a finitely generated subgroup with powers of ;
Accumulationfree subsets, when is an ordered group with powers. Here an accumulationfree subset of is a subset , such that for all with , there exists an , such that
Exercise
Exercise
Exercise
The image is wellordered.
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 wellbased.
Exercise
For gridbased sets and , show that there exists a gridbased set with .
Given a gridbased set , does there exist a smallest gridbased set for inclusion, such that ? Hint: consider for a suitable ordering on .
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 gridbased, then we call a gridbased series. We denote the set of all gridbased 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 gridbased series in . We say that is a gridbased family, if is gridbased 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 gridbased series. In particular, given a gridbased series , the family is gridbased and we have .
Let us now give the structure of a algebra; we will say that is a gridbased algebra. and are clearly contained in via resp. . Let . We define
and
By propositions 1.6 and 2.1, and are welldefined as sums of gridbased 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 gridbased 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 gridbased 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
Example
is the field of Laurent series in . Elements of are of the form with .
is the field of Puiseux series in . Elements of are of the form with and .
is the ring of multivariate power series, when is given the product ordering.
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
If , where is clear from the context, then we simply write
Any series in may also be considered as a series in and we may recursively expand as follows:
Notice that , in general (see exercise 2.6).
and
for nontrivial permutations of .
Exercise
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):
;
;
;
;
;
;
.
Also determine the order types of the squares of these series.
Exercise
Exercise
Exercise
and
Show that the embeddings and are strict, in general.
Exercise
Let be a gridbased 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 gridbased 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 nonzero series in is regular. Then we define a dominance relation on , whose associated strict quasiordering is a neglection relation, by
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:
Example
Warning
Proposition
is a totally ordered algebra.
The relations and coincide with those defined in proposition 1.20.
If is a field, then is a Hahn space over .
is the set of bounded elements in .
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 .
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. .
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
;
.
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 nonempty 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
Exercise
Exercise
Show that is a perfect ordered algebra.
Let and be defined as in exercise 1.27. Show that in .
For and regular, show that , if and only if .
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
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 wellbased support has the natural structure of an ordered module. Show also that this ordering is total if the orderings on and are both total.
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 .
If in proposition 1.22, then show that admits a unique basis , such that and for all .
Exercise
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 .
Let be an extension of totally ordered fields. Given a Hahn space over , show that has the structure of a Hahn space over .
Show that is a flat subring of .
Characterize the relations and .
Exercise
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), “gridbased 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”.
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 gridbased 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 .
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.
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
We understand that , whenever we use the notation . For instance, SA2 should really be read: for all and , we have and .
Remark
Example
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
Let be a ring with a strong summation (which satisfies SA1–SA6). We say that is a strong ring if
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
Notice that SM is trivially satisfied when carries the trivial strong structure. We say that is an ultrastrong module, if we also have
A strong algebra (resp. an ultrastrong 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 ultrastrong module).
Let and be two strong modules. A linear mapping is said to be strong if it preserves the infinite summation symbols, i.e.
In the case of ultrastrong 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
Deduce that .
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).
Given a set , show how to construct the free strong module in .
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
Let be a gridbased algebra as in section 2.2. Given a countable family , we define to be summable if and only if is a gridbased 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 gridbased families coincide.
Proposition
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 gridbased family and a decomposition of . For each , let and , so that
(2.5) 
Now is a gridbased 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 gridbased and for all , we have
This proves SA5.
Now let and be two gridbased families. Then
is gridbased. Given , the couples
with form a finite antichain; let denote those couples. Then
is finite, whence is a gridbased family. Given , and using the above notations, we also have
Let be a gridbased algebra. Given , let
We have
Indeed,
and for every ,
Moreover, if is a gridbased, then refines .
It is convenient to generalize proposition 2.1 to gridbased families. Given , we denote
Proposition
is gridbased.
is gridbased.
If , then is gridbased.
Proof. Properties (a) and (b) follow from SA4 and SR. As to (c), let be the wellbased set of pairs with and , for the ordering
Now consider the family with for each word . This family is wellbased, since is wellbased and the mapping increasing. Moreover,
Let and be two gridbased algebras. A mapping is said to be gridbased if gridbased subsets are mapped to gridbased families .
Proposition
Proof. Let . Then is a gridbased 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 gridbased. Indeed,
is gridbased. Secondly, given , the set is finite, since is gridbased. 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 gridbased and
This establishes the strong linearity of .
Proposition
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
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 gridbased 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
For , we have
For and infinitesimal , we have
Exercise
Exercise
Exercise
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
, for all .
and , for all and .
The mapping is increasing.
Then
and , for all and .
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 gridbased). Hence, is in , and so are and . Therefore,
since is a group with powers. This proves (a).
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
Exercise
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 .
Prove that the above characterization of invertible series does not hold for general monomial groups.
Exercise
Let be another asymptotic basis of . Show that and that there exists a square matrix
such that , that is, for all .
Show that .
If , then show that the matrix is diagonal, modulo a permutation of the elements of .
If , then show that the matrix is lower triangular.
3 
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 gridbased 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 nonlinear 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 sideconditions, 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 gridbased 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 gridbased series. This calculus is based on the observation that any gridbased 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 gridbased series, such as convergent, algebraic or effective gridbased series. In section 3.5, we will show that the Newton polygon method can again be applied to these more special types of gridbased 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.
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 nontrivial polynomial equation in . We call and (3.2) the Newton polynomial resp. Newton equation associated to .
Let us now replace by a nonzero 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 nonzero 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.
First of all, since the new equation (3.3) comes with the asymptotic sidecondition , it is convenient to study polynomial equations with asymptotic sideconditions
(3.4) 
Fig. 3.1. The lefthand 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 righthand side. Each nonzero coefficient in the equation (3.1) for induces a “row” of (potentially) nonzero 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 leftmost 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
with a normalized asymptotic sidecondition (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.
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 quasilinear.
Returning to our example equation (3.1), it can be checked that each of the refinements
leads to a quasilinear 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 quasilinear. 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:
Usually the Newton degrees rapidly decreases during refinements and we are quickly left with only quasilinear 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 quasilinear, 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 quasilinear 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
In the previous section, we have stressed the particular importance of quasilinear 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 quasilinear 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.8) 
with coefficients , such that and . Then
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 wellbased and even gridbased, 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) 
where is a gridbased family with and .
Exercise
Exercise
Exercise
(3.12) 
with , and invertible . Prove that (3.12) admits a unique infinitesimal solution .
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 nonzero 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
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 quasilinear. The previous proposition implies that (3.13) does not admit any solution, if .
Lemma
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
The Newton degree of
The Newton degree of
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
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
The equation
(3.18) 
is quasilinear and its unique solution satisfies .
The Newton degree of any refinement
relative to
Proof. Notice first that for all polynomials and monomials . Consequently, (3.18) is quasilinear and is a single root of . This proves (a).
Theorem
Proof. Consider the following algorithm:
Algorithm polynomial_solve
Input:
An asymptotic polynomial equation (3.13).
Output:
The set of solutions to (3.13).
Compute the starting terms of relative to (3.13).
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).
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 .
Corollary
Proof. By the theorem, a polynomial equation of degree over admits solutions in , when counting with multiplicities. Moreover, each root is imaginary, because
Corollary
Exercise
Also show that if is algebraically closed.
Exercise
Show that the computation of all solutions to (3.13) can be represented by a finite tree, whose nonroot nodes are labeled by refinements. Applied to (3.1), this would yields the following tree:
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
Generalize the results of this chapter to asymptotic equations of infinite degree in , but of finite Newton degree.
Give an example of an asymptotic equation of infinite degree in , with infinitely many solutions.
Exercise
of Newton degree , with and . Consider the monomial monoid with
Show that there exists a unique invertible series such that is a monoic polynomial in .
Show that .
In this section, we show that gridbased 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 gridbased series.
Let be a gridbased 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 semiCartesian representation for is an expression of the form
where , and is a morphism of monomial monoids.
Any gridbased series admits a semiCartesian representation.
If is a monomial group, which is generated by its infinitesimal elements, then each gridbased 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 semiCartesian representations and are said to be compatible, if and belong to the same algebra of Laurent series, and if .
Any admit compatible semiCartesian representations.
If is a monomial group, which is generated by its infinitesimal elements, then any admit compatible Cartesian representations.
Proof. By the previous proposition, admit semiCartesian representations , where and for each . Now consider
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
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:
If , then there exist infinitesimal , such that , by the induction hypothesis. Taking , we now have , since .
If , then , and we may take .
If , then there exists infinitesimal , such that . Taking , we again have .
When doing computations on gridbased 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.
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 gridbased 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 .
Let be a ring. A sequence with is said to be a Cartesian community over , if the following conditions are satisfied:
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
A local community is a Cartesian community , which satisfies the following additional conditions:
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
Example
Example
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
For each and , we have .
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 antichain 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
Proposition
of a series , its truncation
Proposition
infinitesimal,
bounded, or
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).
Theorem
(3.20) 
with coefficients , such that and . Then
Proof. By proposition 3.20, there exist bounded Cartesian representations for certain . Now consider the series
We have and , so there exists a with
Theorem
Exercise
with for some , and . Which results from this section generalize to this more general setting?
Exercise
Exercise
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.
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
be a Cartesian representation of an infinitesimal, bounded or regular gridbased 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.
If and , then show that .
If is totally ordered, then prove that is a field.
Exercise
Exercise
Given and , where is a third monomial group, prove that .
Given and such that , prove that .
Exercise
Exercise
Exercise
Exercise
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 .
Consider a bounded Cartesian representation with and let . Given , let
Show that is a series in .
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 .
In polynomial_solve, show that refinements of the type
where is the unique solution to , may be replaced by refinements
Let be a totally ordered explog 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 explog 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 explog field of gridbased transseries in over . This means that is a field of gridbased 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 explog 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 gridbased series which is stable under exponentiation and logarithm.
Now it is easy to construct a field of gridbased 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 gridbased 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 gridbased 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 gridbased transseries.
A partial exponential ring is a ring with a partial exponential function , such that
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
If , then we say that is an ordered exponential ring.
Proposition
for all and .
Proof. Assume that . We cannot have , since otherwise
If , then
Proposition
Proof. Let . For , we have
Proposition
is injective.
, for all .
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
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
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
Let be a partial exponential ring, such
that is injective. Then the partial
inverse of
satisfies
If is an ordered partial exponential
ring, then is injective, and its partial
inverse satisfies
Let be a partial logarithmic ring, such
that is injective. Then the partial
inverse of
satisfies
If is an ordered partial logarithmic
ring, then is injective, and its partial
inverse satisfies
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 explog 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
If (a) and (c) (resp. (b) and (d)) are satisfied in the above proposition, then we say that is a partial explog ring (resp. an ordered partial explog ring). An ordered explog ring is an ordered partial explog ring , such that and . An ordered (partial) exponential, logarithmic resp. explog ring, which is also an ordered field is called an ordered (partial) exponential, logarithmic resp. explog field. In a partial explog 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
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 explog field naturally has powers: set for all and .
Exercise
Exercise
Exercise
Exercise
, if .
, if .
Let be a totally ordered explog 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 gridbased transseries (or a field of transseries) if
Intuitively speaking, the above conditions express a strong compatibility between the logarithmic and the serial structure of .
Example
On the other hand, is a monomial, since
Proposition
Given , the canonical decomposition of is given by
Given , we have
Given , we have
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
, for all and .
, for all .
, for all .
Then is a logarithmic function, which is compatible with the ordering and powers on . Hence, is a field of gridbased 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
Exercise
Show that for all , where .
For each , show that
For each , show that , and .
Exercise
;
;
;
.
Hint: prove that the left and right hands sides satisfy the same (partial) differential equations and the same initial conditions.
Let be a fixed totally ordered explog field, such as , and a formal infinitely large variable. In this section, we will construct the field of gridbased 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 gridbased transseries in over .
Given a monomial , we define by
We extend this definition to , by setting
for each . Here we recall that .
Proposition
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
Proposition
Proof. Clearly . Inversely, assume that
Since is gridbased, there exist , such that
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 gridbased 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 gridbased 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.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
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
Exercise
;
;
;
.
Exercise
Exercise
Exercise
Prove that for all ordinals . Hint: one may consider the transfinite sequence of transseries defined by
If we restrict the supports of wellbased transseries to be countable, then prove that the transfinite sequence stabilizes. Hint: find a suitable representation of transseries by labeled trees.
Exercise
Exercise
Prove that there exists a field of wellbased transseries in the sense of exercise 4.11, which contains the transseries
Prove that the functional equation
admits a solution in .
A transbasis is a finite basis of an asymptotic scale, such that
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
Example
Theorem
The level of is the minimum of the levels of and .
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:
can be expanded w.r.t. . Moreover, satisfies the extra requirements (a) and (b). Indeed, has level and
since .
with and where is either bounded or infinitely large with , for all . By what precedes, and may be expanded w.r.t. a supertransbasis of which satisfies the additional requirements (a) and (b).
This proves the theorem in the case when , with .
Assume now that is a general gridbased 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
We respectively say that is a heavy, normal, light or sloppy transbasis.
Show that TB3a TB3b TB3c TB3d.
Show that theorem 4.15 holds for any of the above types of transbases.
Exercise
;
;
;
;
.
More precisely, an explog transseries (resp. function) is a transseries (resp. function) built up from and constants in , using the field operations , , , , exponentiation and logarithm.
Exercise
for all .
for all .
Exercise
If and belong to in theorem 4.15, then show that may be chosen to belong to as well.
Show that (a) remains valid if LC3 is replaced by the weaker axiom that for all we have .
Given a transbasis , show that and that the coefficients of recursive expansions of are again in .
Given , show that .
Assume now that and let us define the explog 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 explog 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 explog field structure. Our claim relies on the following lemma:
Lemma
is a welldefined 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,
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
Exercise
Given , let
We say that is summable in , if is gridbased and . Show that this defines a strong ring structure on .
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 .
Reformulate lemma 4.16 as a principle of “convergent extension by strong linearity”.
Exercise
Exercise
Construct the smallest subset of , together with a mapping , such that
Show that is a ring.
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.
One of the major features of the field of gridbased 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.
Let be a strong totally ordered partial explog algebra. A strong derivation on is a mapping , which satisfies
We say that is an explog derivation, if we also have
We say that is (strictly) asymptotic resp. positive, if
In this section, we will show that there exists a unique strong explog 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
is a gridbased mapping, which extends uniquely to a strong derivation on .
If for all , then is an explog derivation on .
Proof. Let be a gridbased subset of , so that
for certain monomials and in . For any , we have
Hence for all , and a gridbased 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 explog 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
Proof. We will show by induction over that there exists a unique strong explog 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 explog 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 explog derivation on with . In view of D4, any strong explog 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 explog derivation, since
Proposition
Proposition
If or , then is stable under .
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
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
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
Exercise
.
.
.
In the case of (a), notice that we may for instance interpret as a relation in a field of wellbased transseries in .
Exercise
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
The strong module of all strong explog derivations on .
The set of all (not necessarily strictly) asymptotic strong explog derivations on .
The set of all (not necessarily strictly) positive strong explog derivations on .
Exercise
Show that is stable under differentiation.
Considering as a strong algebra, show that there exists a unique strongly linear mapping with for all .
Show that
for all .
Exercise
Exercise
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
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 gridbased, 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 gridbased by proposition 2.14(c) and (2.7). We conclude that is welldefined, and
Let us now show that the mapping is gridbased. Given a gridbased subset of , we may decompose
where the () are given by
By what precedes, is gridbased for each . Hence, is a gridbased 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
Proposition
If or , then is stable under for all .
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,
Exercise
Exercise
Exercise
Let and be strong totally ordered partial explog algebras. A strong difference operator of into is an injection , which satisfies
If , then we say that is a strong difference operator on . We say that is an explog difference operator, if we also have
We say that is asymptotic resp. increasing, if
In this section, we will show that for each , there exists a unique strong explog 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
is a gridbased mapping, which extends uniquely to a strong, asymptotic and increasing difference operator from into .
If for all , then the extension of to is an explog difference operator.
Proof. Let be a gridbased subset of with , for certain monomials and in . Then the family with is gridbased, by proposition 2.14(c). It follows that is gridbased, 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
Proof. We will show by induction over that there exists a unique strong explog 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 explog 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,
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 gridbased 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 welldefined. 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 gridbased, by proposition 2.14(c). Since refines the family , it follows that the Taylor series in (5.4) is welldefined. For a similar reason, the mapping is gridbased, 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
Exercise
Prove that the exponentiality of equals the sum of the exponentialities of and .
Prove that the exponential height resp. logarithmic depth of is bounded by the sum of the exponential heights resp. logarithmic depths of and .
Improve the bound in (b) by taking into account the exponentialities of and .
Exercise
Exercise
Exercise
Exercise
Exercise
Theorem
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
We define a scalar product on by
Given transseries and , let us denote
When taking transmonomials for and , then the coefficients describe the postcomposition operator with . More precisely, for all we have
Theorem
Proof. Since for all , we have
Since and are exponential, we have
Using the rule , it follows that
Now integration by parts yields
The theorem generalizes to the case when and are no longer exponential, by applying the following rule a finite number of times:
Corollary
Exercise
Show that we do not always have .
Give a necessary and sufficient condition for which
A classical theorem of Liouville [Lio37, Lio38] states that is not an explog function. Show that there exists no explog function with (see [Har11] for a variant of this problem).
Show that there exists no explog function with . Hint: use exercise 5.11.
Assume that is not an explog function. Show that there exists an , such that there exists no explog function with .
Exercise
Exercise
Exercise
Exercise
Exercise
If one allows , then show that the formula holds for transseries of arbitrary levels.
6 
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 “gridbased modules”. Let be a ring. In chapter 2, we defined a gridbased 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 gridbased 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 “gridbased operators”. In section 6.3, we next introduce the general concept of a gridbased operator. Roughly speaking, such an operator is a mapping which admits a “generalized Taylor series expansion”
such that there exists a linear gridbased 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 gridbased operators may both be reinterpreted as general gridbased operators and linear gridbased operators using the “syntactic sugar isomorphisms”
The first isomorphism also provides a notion of gridbased operators in several variables.
As promised, many operations can be carried with gridbased operators: they can be composed and one may define a natural strong summation on the space of gridbased 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 gridbased 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.
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 gridbased modules, then we also say that is a multilinear gridbased operator.
Example
Left multiplication operators , with .
Strong derivations . If admits powers, then such derivations should also satisfy , whenever is welldefined for and .
Strong integrations; these are partial, strongly linear right inverses of strong derivations , i.e. .
Strong difference operators . If admits powers, then such difference operators should also satisfy , whenever is welldefined for and ).
Strong summation operators; these are partial, strongly linear right inverses of finite difference operators, i.e. , for some strong difference operator .
Example
of multilinear gridbased operators
are again multilinear gridbased operators.
Example
are linear gridbased operators. In section 6.4.1, we will see that we may actually define strong summations on spaces of gridbased operators.
Let be an linear gridbased 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
for multilinear operators () and .
Show that is welldefined for noncommutative series .
Determine the largest subspace of on which is a welldefined bijection.
Exercise
Is a multilinear gridbased operator necessarily a multilinear wellbased operator?
Show that for wellbased series, if is totally ordered. Here denotes the strong dual of .
Show that (b) does not hold for gridbased series. How to characterize ?
Let be the set of transseries with for all and consider the space of operators
(6.2) 
such that is a gridbased. Show that operates on and that is stable under composition.
Let and consider the space of operators (6.2), such that is a gridbased family. Show that operates on and that is stable under composition.
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 gridbased modules, in which case the tensor product has a particularly nice form:
Proposition
Consider the mapping
This mapping is welldefined and strongly multilinear. Moreover, for every strongly multilinear mapping
into an arbitrary strong module, there exists a unique strongly linear mapping
such that .
Lemma
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
Proof of proposition 6.6. Given gridbased subsets with the set is clearly a gridbased subset of . This implies that is welldefined. More generally, given gridbased families of terms , the family is again gridbased. Now consider arbitrary gridbased families and let , for . Then
This shows that is multilinear.
Inversely, if is a gridbased subset of , then its projections on for are again gridbased, and we have
Consequently, given a strongly multilinear mapping
the mapping
is welldefined. 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 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
is a gridbased family for any gridbased subsets . Then there exists a unique strongly multilinear mapping
with .
Exercise
Exercise
Generalize proposition 6.6 to the case of wellbased series.
Show that a wellbased family corresponds to an element of .
Define a family to be supergridbased with and . Show that is a strong algebra for supergridbased summation.
Give an example of a gridbased family which is not supergridbased.
Exercise
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.
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.
Let and be monomial sets. A mapping is said to be a gridbased operator if there exists a family of multilinear gridbased operators , such that for all , the family is gridbased, 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
Proof. We observe that it suffices to prove that for each , since the are symmetric and is torsionfree. Assume the contrary and let be such that for some . Choose
Since is a gridbased 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
Proposition
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
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 .
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 gridbased operator can be seen as a gridbased operator in from into . More generally, the natural isomorphism may be used in order to extend the notion of gridbased operators to mappings .
Let and be two gridbased operators. Then is again a gridbased 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
Exercise
Exercise
Characterize the intervals of the set of infinitesimal transmonomials (i.e. for all and , we have ), such that for all , the operator is a gridbased operator on .
With as in (a), show that the operators and are gridbased.
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 gridbased operators . This space is clearly a module. A family is said to be summable, if for all , the family
is a gridbased family. In that case, the sum
is a gridbased 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.
Let and be monomials sets. Given and , the operator
with
is an linear gridbased 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 gridbased 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 .
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
The set is gridbased.
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
Fig. 6.1. Combinatorial interpretation of the composition of atomic operators. 
Exercise
from exercise 6.1 is a strong algebra morphism.
Exercise
Exercise
Let and be monomial sets which are contained in a common monomial monoid. Consider a gridbased operator
together with its atomic decomposition . We say that
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 gridbased operator as above, the aim of the implicit function theorems is to construct a gridbased operator , such that
(6.8) 
for all . In the wellbased context, a sufficient condition for the existence (and uniqueness) of such an operator is the strict extensiveness of in . In the gridbased context we need additional conditions in order to preserve the gridbased property. In this section, we present three possible choices for these extra conditions, which lead each to a gridbased implicit function theorem.
Theorem
which is extensive in with multipliers in a
gridbased set . Then for each , there exists a unique which
satisfies
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 gridbased 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 gridbased 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 .
Theorem
such that
is gridbased and infinitesimal for all .
Then, for each , there exists a unique which satisfies
Proof. Let , with support . There exist finite sets and , such that . Let
Then we have and
Theorem
which is strictly extensive in . Assume that
is gridbased and . Then for each , there exists a unique which
satisfies
Proof. With the notations of the proof of theorem 6.13, let us first show that is a wellbased family for every gridbased 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 wellbased by Higman's theorem. This together implies that is wellbased.
Let us show that is actually a gridbased. 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 gridbased 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:
Consider the tree with the same nodes as and if and . Then we may factor through with and .
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 .
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 .
Exercise
Exercise
Exercise
Exercise
Let be a wellbased operator which is extensive in . Then for each , there exists a unique which satisfies (6.8) and the operator is wellbased.
One obtains interesting subclasses of gridbased 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
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 gridbased family of atoms of type . A gridbased operator
is said to be of type , if is of type for all .
Example
Exercise
Exercise
Exercise
7 
Let be a linear differential operator with transseries coefficients and . In this chapter, we study the linear differential equation
(7.1) 
In our gridbased 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 nontrivial 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.
Let be the field of gridbased transseries in over a realclosed explog field of constants . In what follows, it will often be convenient to regard linear differential operators as elements of . In particular, each nonzero 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
Proof. Without loss of generality, one may assume that , modulo division of by . Then
Given a linear differential operator and a nonzero 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 .
Proof. From it follows that for all . Then (7.3) implies . Conversely, we have
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
Show that there exists a unique with
for all .
Give an explicit formula for for each .
Show that is a ring homomorphism.
Exercise
Show that each can be reinterpreted as an operator .
Given , let be the result of the substitution of for in . If , then show that .
Given (see exercise 6.3), let . Show that naturally operates on . Also show that the space of all such operators only depends on .
Same question, but for .
Under which condition on can the operator in either of the above questions be rewritten as an operator of the form ?
Exercise
Exercise
Determine so that .
Given , construct the th iterate of .
Determine the maximal flat subspace of such that .
where .
Show that and let be such that .
Assuming that , show that there exists a with .
Exercise
Given with and . Show that
are welldefined.
Let , , and . Show that
are welldefined.
Given a transmonomial with and , show that
is welldefined. Extend the definition of to and show that corresponds to the distinguished integration.
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 .
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.8) 
Proof. For all , we have
Given a linear differential operator , we call
Proposition
Proof. We claim that for all . Indeed, and, using induction,
Corollary
Exercise
Exercise
where and are defined in section 8.2.3.
Let be a linear gridbased 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.
Let be a linear differential operator, where is a plane transbasis. We will consider as a gridbased operator on , so that its trace is a mapping from into .
Proposition
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 .
Proposition
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
Proposition
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
Example
Given and , we have
Now the following cases may occur:
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
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
Proposition
Proof. Clearly, . Assume for contradiction that there exists an . Then there exists an with and . Let be a supertransbasis of for , of level , and which contains . Setting , proposition 7.10 now implies
Proposition
Assume again that , where is a plane transbasis.
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 .
Corollary
which extend and . Furthermore,
and .
Proposition
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 .
Exercise
Exercise
Exercise
Let and be monomial sets, such that is totally ordered. Given a linear gridbased 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
Theorem
Assume also that and are gridbased. Then
admits a distinguished and gridbased right inverse
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
Corollary
Corollary
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
Example
Let be a plane transbasis and let be a linear differential operator on of order .
Proposition
where
are gridbased sets and .
Proof. With the notations from the proof of theorem 7.17,
It follows that
Setting , we have
maps into .
maps into .
.
Proof. For all , we have
This shows (a). As to (b), let and consider
Exercise
Exercise
Exercise
Show that is the restriction of to , if is a supertransbasis of .
If , then show that if and only if .
If , then show that for all .
Exercise
Exhibit an operator in which maps to and relate and .
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 .
Given a plane transbasis , and , give a concrete algorithm to compute the recursive expansion of .
Exercise
Exercise
Here is the unique operator such that
for all .
Exercise
Show that for and .
Show that for and .
Do we always have ?
Exercise
Prove that each nonzero admits a distinguished rightinverse on .
Can be infinite?
Same questions for .
Exercise
For any , show that is an operator of the same kind.
Show that admits a distinguished rightinverse on .
Assuming that , show that admits a distinguished rightinverse on .
Given , show that admits a distinguished solution, which is not necessarily gridbased, but whose support is always wellbased and contained in a finitely generated group.
Show that (d) still holds if .
Given a general , show that admits a wellbased distinguished solution.
Give a bound for the cardinality of .
Exercise
Show that is a algebra under composition.
Show that each induces a unique operator in with .
Show that the skew fraction field of in consists of operators with and . Hint: show that for any with , there exist with and .
Exercise
If , then show that there exists a decomposition
with , and .
If and is sufficiently small, then show how to define .
Given , extend the definition of from exercise 7.7(c) to a definition of on a suitable strong subvector space of .
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.
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
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,
We say that () is quasilinear if its Newton degree is one (i.e. if (7.20) is quasilinear). We have the following analogue of lemma 3.5:
Proposition
Proof. Let and consider the wellbased operator
Since
(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
(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.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
Proposition
The equation
(7.32) 
is quasilinear and has a unique solution with .
Any refinement
(7.33) 
transforms
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
Putting together the results from the previous sections, we obtain the following analogue of