Transseries
and
Real Differential Algebra

by Joris van der Hoeven

Table of Contents

Foreword

XI

Introduction

1

The field with no escape

1

Historical perspectives

3

Outline of the contents

7

Notations

10

1Orderings

11

1.1Quasi-orderings

12

1.2Ordinal numbers

15

1.3Well-quasi-orderings

17

1.4Kruskal's theorem

19

1.5Ordered structures

22

1.6Asymptotic relations

25

1.7Hahn spaces

29

1.8Groups and rings with generalized powers

30

2Grid-based series

33

2.1Grid-based sets

34

2.2Grid-based series

36

2.3Asymptotic relations

40

2.3.1Dominance and neglection relations

40

2.3.2Flatness relations

42

2.3.3Truncations

42

2.4Strong linear algebra

44

2.4.1Set-like notations for families

44

2.4.2Infinitary operators

45

2.4.3Strong abelian groups

46

2.4.4Other strong structures

47

2.5Grid-based summation

48

2.5.1Ultra-strong grid-based algebras

48

2.5.2Properties of grid-based summation

49

2.5.3Extension by strong linearity

50

2.6Asymptotic scales

53

3The Newton polygon method

57

3.1The method illustrated by examples

58

3.1.1The Newton polygon and its slopes

58

3.1.2Equations with asymptotic constraints and refinements

59

3.1.3Almost double roots

62

3.2The implicit series theorem

63

3.3The Newton polygon method

65

3.3.1Newton polynomials and Newton degree

65

3.3.2Decrease of the Newton degree during refinements

66

3.3.3Resolution of asymptotic polynomial equations

67

3.4Cartesian representations

69

3.4.1Cartesian representations

69

3.4.2Inserting new infinitesimal monomials

71

3.5Local communities

71

3.5.1Cartesian communities

72

3.5.2Local communities

72

3.5.3Faithful Cartesian representations

73

3.5.4Applications of faithful Cartesian representations

74

3.5.5The Newton polygon method revisited

75

4Transseries

79

4.1Totally ordered exp-log fields

80

4.2Fields of grid-based transseries

84

4.3The field of grid-based transseries in

87

4.3.1Logarithmic transseries in

88

4.3.2Exponential extensions

88

4.3.3Increasing unions

89

4.3.4General transseries in

89

4.3.5Upward and downward shifting

90

4.4The incomplete transbasis theorem

92

4.5Convergent transseries

94

5Operations on transseries

97

5.1Differentiation

98

5.2Integration

103

5.3Functional composition

106

5.4Functional inversion

111

5.4.1Existence of functional inverses

111

5.4.2The Translagrange theorem

112

6Grid-based operators

115

6.1Multilinear grid-based operators

116

6.1.1Multilinear grid-based operators

116

6.1.2Operator supports

117

6.2Strong tensor products

118

6.3Grid-based operators

122

6.3.1Definition and characterization

122

6.3.2Multivariate grid-based operators and compositions

123

6.4Atomic decompositions

124

6.4.1The space of grid-based operators

124

6.4.2Atomic decompositions

125

6.4.3Combinatorial interpretation of atomic families

126

6.5Implicit function theorems

127

6.5.1The first implicit function theorem

128

6.5.2The second implicit function theorem

130

6.5.3The third implicit function theorem

130

6.6Multilinear types

133

7Linear differential equations

135

7.1Linear differential operators

136

7.1.1Linear differential operators as series

136

7.1.2Multiplicative conjugation

137

7.1.3Upward shifting

137

7.2Differential Riccati polynomials

139

7.2.1The differential Riccati polynomial

139

7.2.2Properties of differential Riccati polynomials

140

7.3The trace of a linear differential operator

141

7.3.1The trace relative to plane transbases

141

7.3.2Dependence of the trace on the transbasis

143

7.3.3Remarkable properties of the trace

144

7.4Distinguished solutions

146

7.4.1Existence of distinguished right inverses

146

7.4.2On the supports of distinguished solutions

148

7.5The deformed Newton polygon method

151

7.5.1Asymptotic Riccati equations modulo

151

7.5.2Quasi-linear Riccati equations

152

7.5.3Refinements

153

7.5.4An algorithm for finding all solutions

155

7.6Solving the homogeneous equation

156

7.7Oscillating transseries

158

7.7.1Complex and oscillating transseries

158

7.7.2Oscillating solutions to linear differential equations

159

7.8Factorization of differential operators

162

7.8.1Existence of factorizations

162

7.8.2Distinguished factorizations

163

8Algebraic differential equations

165

8.1Decomposing differential polynomials

166

8.1.1Serial decomposition

166

8.1.2Decomposition by degrees

167

8.1.3Decomposition by orders

167

8.1.4Logarithmic decomposition

168

8.2Operations on differential polynomials

169

8.2.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.5Quasi-linear equations

182

8.5.1Distinguished solutions

182

8.5.2General solutions

183

8.6Unravelling almost multiple solutions

186

8.6.1Partial unravellings

186

8.6.2Logarithmic slow-down of the unravelling process

188

8.6.3On the stagnation of the depth

189

8.6.4Bounding the depths of solutions

190

8.7Algorithmic resolution

192

8.7.1Computing starting terms

192

8.7.2Solving the differential equation

194

8.8Structure theorems

196

8.8.1Distinguished unravellers

196

8.8.2Distinguished solutions and their existence

197

8.8.3On the intrusion of new exponentials

198

9The intermediate value theorem

201

9.1Compactification of total orderings

202

9.1.1The interval topology on total orderings

202

9.1.2Dedekind cuts

203

9.1.3The compactness theorem

204

9.2Compactification of totally ordered fields

206

9.2.1Functorial properties of compactification

206

9.2.2Compactification of totally ordered fields

207

9.3Compactification of grid-based algebras

208

9.3.1Monomial cuts

208

9.3.2Width of a cut

209

9.3.3Initializers

210

9.3.4Serial cuts

210

9.3.5Decomposition of non-serial cuts

211

9.4Compactification of the transline

212

9.4.1Exponentiation in

213

9.4.2Classification of transseries cuts

213

9.4.3Finite nested expansions

214

9.4.4Infinite nested expansions

216

9.5Integral neighbourhoods of cuts

219

9.5.1Differentiation and integration of cuts

219

9.5.2Integral nested expansions

219

9.5.3Integral neighbourhoods

220

9.5.4On the orientation of integral neighbourhoods

222

9.6Differential polynomials near cuts

223

9.6.1Differential polynomials near serial cuts

223

9.6.2Differential polynomials near constants

224

9.6.3Differential polynomials near nested cuts

225

9.6.4Differential polynomials near arbitrary cuts

226

9.6.5On the sign of a differential polynomial

227

9.7The intermediate value theorem

229

9.7.1The quasi-linear case

229

9.7.2Preserving sign changes during refinements

230

9.7.3Proof of the intermediate value theorem

232

References

235

Glossary

241

Index

247

Foreword

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

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

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

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

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

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

Joris van der Hoeven
Chevreuse 1999–2006

Introduction

The field with no escape

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Historical perspectives

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

1Resolution of differential equations by means of power series

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

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

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

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

2Generalized asymptotic scales

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

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

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

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

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

3Model theory

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

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

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

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

4Computer algebra and automatic asymptotics

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

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

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

5Non-archimedean geometry

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

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

Outline of the contents

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Notations

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

  1. Given a mapping and , we write

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

  2. We systematically use the double index convention . Given a set of monomials, we also denote (this is an exception to the above notation).

  3. Given a set , we will denote by its subset of strictly positive elements, its subset of bounded elements, of negative infinitesimal elements, etc. If is a set of series, then we also denote , where , and similarly for , , etc. Notice that this is really a special case of notations 1 and 2.

  4. Intervals are denoted by , , or depending on whether the left and right sides are open or closed.

  5. We systematically denote monomials in the fraktur font and families using calligraphic characters.

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

There are also a few changes in terminology:

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

1Orderings

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

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

and

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

and denotes the set with the partial product ordering

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

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

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

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

1.1Quasi-orderings

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

O1
;

O2
.

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

O3
.

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

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

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

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

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

  3. The Cartesian product is naturally quasi-ordered by

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

    We write for the corresponding quasi-ordered set.

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

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

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

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

    and the canonical projection is increasing.

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

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

Then is finer than and the mapping admits a natural factorization

(1.1)

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

Exercise 1.1. Let be a set.

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

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

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

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

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

  2. and are associative modulo .

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

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

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

  1. We define a quasi-ordering on by .

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

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

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

  5. For all ordered sets , prove that .

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

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

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

  1. If , then .

  2. If , then .

  3. .

  4. .

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

1.2Ordinal numbers

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

Theorem 1.1. Every set can be well-ordered.

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

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

Fig. 1.2. Some examples of ordinal numbers.

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

Theorem 1.3. Each well-ordered set is isomorphic to a unique ordinal.

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

Table 1.1. Basic arithmetic on ordinal numbers.

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

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

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

Exercise 1.6. Prove the transfinite induction principle.

Exercise 1.7. For any two ordinals , show that

  1. ;

  2. .

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

Exercise 1.8. For all ordinals and , prove that

  1. ;

  2. .

Do we also have ?

1.3Well-quasi-orderings

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

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

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

the initial segment generated by .

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

  1. is well-quasi-ordered.

  2. Any final segment of is finitely generated.

  3. The ascending chain condition w.r.t. inclusion holds for final segments of .

  4. Each sequence admits an increasing subsequence.

  5. Any extension of the quasi-ordering on to a total quasi-ordering on yields a well-founded quasi-ordering.

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

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

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

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

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

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

  1. Any subset of with the induced ordering is well-quasi-ordered.

  2. Let be a morphism of ordered sets. Then is well-quasi-ordered.

  3. Any ordering on which extends is a well-quasi-ordering.

  4. is well-quasi-ordered, for any compatible equivalence relation on .

  5. and are well-quasi-ordered.

  6. and are well-quasi-ordered.

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

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

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

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

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

We say that is a minimal bad sequence.

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

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

which contradicts the badness of .

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

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

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

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

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

1.4Kruskal's theorem

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

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

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

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

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

(1.2)

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

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

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

The following theorem is known as Kruskal's theorem:

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

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

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

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

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

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

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

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

whenever there exists an increasing mapping with for all .

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

1.5Ordered structures

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

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

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

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

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

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

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

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

If and are ordered, then so are and .

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

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

  1. Show that , for all .

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

Exercise 1.16. Let be a totally ordered ring.

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

  2. Show that may contain nilpotent elements.

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

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

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

  1. and ;

  2. and ;

  3. and ;

  4. , but not always .

Exercise 1.18.

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

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

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

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

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

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

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

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

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

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

  1. Prove that is a quasi-ordering.

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

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

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

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

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

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

1.6Asymptotic relations

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

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

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

D1
;

D2
and .

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

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

N1
;

N2
and .

N3
.

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

Similarly,

whence

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

Proposition 1.17.

  1. Let be a dominance relation such that the strict ordering associated to satisfies N1 and N2. Then also satisfies N3.

  2. Let and be a dominance and a neglection relation. If and are associated, then they are compatible.

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

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

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

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

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

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

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

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

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

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

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

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

D3
.

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

N4
.

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

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

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

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

Exercise 1.21.

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

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

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

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

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

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

V1
for all .

V2
, for all with .

Show that the valuations on correspond to total dominance relations.

Exercise 1.26.

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

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

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

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

1.7Hahn spaces

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

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

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

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

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

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

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

Exercise 1.31.

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

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

1.8Groups and rings with generalized powers

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

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

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

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

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

from example 1.13.

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

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

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

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

In that case, we define

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

Proposition 1.26.

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

  2. If for all and we have

    (1.3)

    then and are associated.

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

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

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

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

We may also take , in which case we define

For instance, if , then , and for all .

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

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

  2. Show that and are characterized by

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

2Grid-based series

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

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

is the natural solution to the functional equation

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

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

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

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

2.1Grid-based sets

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

(2.1)

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

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

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

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

  1. Each finite set is grid-based.

  2. is grid-based.

  3. is grid-based.

  4. If , then is grid-based.

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

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

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

Then fulfills our requirements.

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

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

  1. Well-based subsets;

  2. Countable well-based subsets;

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

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

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

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

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

  1. The image is well-ordered.

  2. For every , the set is finite.

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

Exercise 2.5.

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

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

2.2Grid-based series

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

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

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

(2.2)

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

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

and

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

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

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

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

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

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

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

  1. is the ring of formal power series in .

  2. is the field of Laurent series in . Elements of are of the form with .

  3. is the field of Puiseux series in . Elements of are of the form with and .

  4. is the ring of multivariate power series, when is given the product ordering.

  5. is the ring of multivariate Laurent series, when is given the product ordering. We recall that a multivariate Laurent series is the product of a series in and a monomial . Given , let be the set of dominant monomials of . Then we may take for each .

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

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

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

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

Notice that , in general (see exercise 2.6).

Exercise 2.6. Show that, in general,

and

for non-trivial permutations of .

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

Now consider the monomial group

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

  1. ;

  2. ;

  3. ;

  4. ;

  5. ;

  6. ;

  7. .

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

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

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

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

and

Show that the embeddings and are strict, in general.

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

2.3Asymptotic relations

2.3.1Dominance and neglection relations

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

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

where we recall that .

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

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

For non-zero and , we have

Given , we define its canonical decomposition by

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

where

Similarly, we define and .

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

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

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

  1. is a totally ordered -algebra.

  2. The relations and coincide with those defined in proposition 1.20.

  3. If is a field, then is a Hahn space over .

  4. is the set of bounded elements in .

  5. is the set of infinitesimal elements in .

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

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

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

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

2.3.2Flatness relations

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

(2.3)

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

Indeed, for all and infinitesimal .

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

  1. ;

  2. .

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

2.3.3Truncations

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

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

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

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

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

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

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

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

  1. Show that is a perfect ordered -algebra.

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

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

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

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

Exercise 2.14.

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

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

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

Exercise 2.15.

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

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

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

  1. Show that is a flat subring of .

  2. Characterize the relations and .

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

2.4Strong linear algebra

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

2.4.1Set-like notations for families

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

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

Given an operation and families for , we define

(2.4)

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

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

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

2.4.2Infinitary operators

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

A partial infinitary operator on a set is a partial map

where is an infinite cardinal number and

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

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

2.4.3Strong abelian groups

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

SA1
is strongly commutative.

SA2
For all and , we have .

SA3
For all and , we have .

SA4
For all , we have .

SA5
For all and decompositions , we have

SA6
For all with , we have

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

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

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

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

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

2.4.4Other strong structures

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

SR
For all , we have

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

SM
For all and , we have

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

UM
For all and , we have .

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

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

SL
For all , we have .

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

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

Exercise 2.18. Let and . Prove that

Deduce that .

Exercise 2.19.

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

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

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

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

2.5Grid-based summation

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

2.5.1Ultra-strong grid-based algebras

Proposition 2.13. is an ultra-strong -algebra.

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

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

(2.5)

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

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

This proves SA5.

Now let and be two grid-based families. Then

is grid-based. Given , the couples

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

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

This proves SR.

2.5.2Properties of grid-based summation

Let be a grid-based algebra. Given , let

We have

(2.6)
(2.7)

Indeed,

and for every ,

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

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

Proposition 2.14. Given grid-based families , we have

  1. is grid-based.

  2. is grid-based.

  3. If , then is grid-based.

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

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

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

2.5.3Extension by strong linearity

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

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

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

is the unique strongly linear mapping which coincides with on .

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

is grid-based. Indeed,

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

This establishes the strong linearity of .

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

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

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

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

but also to

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

but also to

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

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

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

Now propositions 2.16 and 2.17 respectively imply that

and

for all . More generally, we have

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

Given , we define . Then

  1. For , we have

  2. For and infinitesimal , we have

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

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

RS
Let and be such that for all . Then .

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

2.6Asymptotic scales

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

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

Then

  1. and , for all and .

  2. If , then is injective.

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

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

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

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

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

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

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

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

Exercise 2.25.

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

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

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

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

    such that , that is, for all .

  2. Show that .

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

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

3The Newton polygon method

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

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

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

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

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

3.1The method illustrated by examples

3.1.1The Newton polygon and its slopes

Consider the equation

(3.1)

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

is the dominant exponent of and

(3.2)

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

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

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

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

(μ=2)
(μ=1)
(μ=0)
(μ=−
3
2
)

correspond to the starting exponents for (3.1).

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

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

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

(3.3)

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

3.1.2Equations with asymptotic constraints and refinements

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

(3.4)

Fig. 3.1. The left-hand side shows the Newton polygon associated to the equation (3.1). The slopes of the four edges correspond to the starting exponents , , and (from left to right). After the substitution

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

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

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

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

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

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

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

(3.5)

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

(3.6)

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

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

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

leads to a quasi-linear equation in . The case

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

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

3.1.3Almost double roots

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

(3.7)

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

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

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

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

This yields the equation

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

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

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

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

3.2The implicit series theorem

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

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

(3.8)

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

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

(3.9)

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

we recursively associate a coefficient and a monomial by

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

(3.10)

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

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

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

(3.11)

since is invertible.

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

where is a grid-based family with and .

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

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

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

(3.12)

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

3.3The Newton polygon method

3.3.1Newton polynomials and Newton degree

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

(3.13)

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

(3.14)

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

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

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

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

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

3.3.2Decrease of the Newton degree during refinements

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

(3.15)

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

(3.16)

where

(3.17)

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

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

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

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

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

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

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

for all . Then .

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

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

  1. The equation

    (3.18)

    is quasi-linear and its unique solution satisfies .

  2. The Newton degree of any refinement

    relative to (3.16) with is strictly inferior to .

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

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

3.3.3Resolution of asymptotic polynomial equations

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

Proof. Consider the following algorithm:

Algorithm polynomial_solve
Input: An asymptotic polynomial equation (3.13).
Output: The set of solutions to (3.13).

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

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

  3. For each , refine

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

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

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

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

for such . Therefore all real roots of are in .

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

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

Also show that if is algebraically closed.

Exercise 3.6.

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

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

Exercise 3.7.

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

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

Exercise 3.8. Consider an asymptotic polynomial equation

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

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

  2. Show that .

3.4Cartesian representations

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

3.4.1Cartesian representations

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

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

where , and is a morphism of monomial monoids.

Proposition 3.11.

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

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

Proof.

    Let and be such that

    For each , let

    Let

    for all and let . Then

    For certain and , we may write

    for all . Let and

    Then .

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

Proposition 3.12.

  1. Any admit compatible semi-Cartesian representations.

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

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

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

3.4.2Inserting new infinitesimal monomials

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

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

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

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

  2. If , then , and we may take .

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

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

3.5Local communities

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

3.5.1Cartesian communities

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

CC1
.

CC2
is a -algebra for each .

CC3
The are stable under strong monomial morphisms.

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

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

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

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

3.5.2Local communities

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

LC1
For each with , we have .

LC2
Given and , we have .

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

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

(3.19)

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

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

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

3.5.3Faithful Cartesian representations

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

Proposition 3.18. Let be a local community and . Then

  1. For each and , we have .

  2. For each initial segment , we have

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

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

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

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

We observe that

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

so that

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

Proposition 3.19. Given a Cartesian representation

of a series , its truncation

is a faithful Cartesian representation of the same series .

3.5.4Applications of faithful Cartesian representations

Proposition 3.20. Let be series, which is either

  1. infinitesimal,

  2. bounded, or

  3. regular.

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

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

with . Then and

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

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

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

3.5.5The Newton polygon method revisited

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

(3.20)

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

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

We have and , so there exists a with

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

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

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

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

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

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

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

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

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

Exercise 3.12. Let be a local community and let

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

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

  1. If and , then show that .

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

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

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

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

  2. Given and such that , prove that .

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

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

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

Exercise 3.19. Consider the resolution of , with and .

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

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

    Show that is a series in .

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

  4. In polynomial_solve, show that refinements of the type

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

4Transseries

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

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

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

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

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

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

where as above.

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

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

with as above.

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

4.1Totally ordered exp-log fields

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

E1
.

E2
, for all .

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

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

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

We also denote

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

E3
, for all and .

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

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

for all and .

Proof. Assume that . We cannot have , since otherwise

If , then

whence .

Proposition 4.2. is a totally ordered exponential field.

Proof. Let . For , we have

For , we have shown above that .

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

  1. is injective.

  2. , for all .

  3. If is a -module, then

Proof. Assume that , for some . Then

and similarly . Hence,

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

Assume now that for some . Then

Consequently,

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

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

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

for all .

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

L1
.

L2
, for all .

L3
, for all and .

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

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

Proposition 4.4.

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

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

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

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

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

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

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

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

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

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

E4
, for all and ; resp.

L4
, for all and .

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

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

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

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

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

  1. , if .

  2. , if .

4.2Fields of grid-based transseries

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

T1
.

T2
, for all .

T3
, for all , where .

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

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

On the other hand, is a monomial, since

Proposition 4.6. Let be a field of transseries. Then

  1. Given , the canonical decomposition of is given by

  2. Given , we have

  3. Given , we have

  4. For all , we have , and .

Proof.

    Follows from L1, L2, T2 and T3.

    We have

    The other relations are proved in a similar way.

    We have

    The other relations are proved similarly.

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

    Consequently, , since . It follows that

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

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

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

  1. , for all and .

  2. , for all .

  3. , for all .

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

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

Here

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

Let us now show that

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

Otherwise, and

If , then . Consequently,

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

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

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

Exercise 4.5. Let be a field of transseries.

  1. Show that for all , where .

  2. For each , show that

  3. For each , show that , and .

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

  1. ;

  2. ;

  3. ;

  4. .

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

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

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

  2. Show that , where

    We call the steep complement of .

4.3The field of grid-based transseries in

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

4.3.1Logarithmic transseries in

Consider the field , where

Given a monomial , we define by

We extend this definition to , by setting

for each . Here we recall that .

Proposition 4.8. is a field of transseries.

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

4.3.2Exponential extensions

Let be a field of transseries and let

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

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

Proposition 4.9. is a field of transseries.

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

4.3.3Increasing unions

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

Proof. Clearly . Inversely, assume that

Since is grid-based, there exist , such that

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

4.3.4General transseries in

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

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

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

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

Example 4.11. The divergent transseries

(4.1)

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

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

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

4.3.5Upward and downward shifting

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

For monomials , we define

Extending these definitions by strong linearity, we obtain mappings

Now assume that we have further extended these mappings into mappings

Then we define

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

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

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

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

Exercise 4.9. For all , prove that

  1. ;

  2. ;

  3. ;

  4. .

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

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

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

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

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

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

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

Exercise 4.13.

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

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

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

Exercise 4.14.

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

  2. Prove that the functional equation

    admits a solution in .

4.4The incomplete transbasis theorem

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

TB1
and .

TB2
, for some .

TB3
for all .

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

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

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

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

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

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

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

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

is bounded
We may take .

for each
is again a transbasis for some and

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

since .

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

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

This proves the theorem in the case when , with .

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

for all , we have

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

Exercise 4.15. Consider the following alternatives for TB3:

TB3-a
, for all ;

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

TB3-c
for all ;

TB3-d
for all .

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

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

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

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

  1. ;

  2. ;

  3. ;

  4. ;

  5. .

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

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

  1. for all .

  2. for all .

Exercise 4.18. Let be a local community.

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

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

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

  4. Given , show that .

4.5Convergent transseries

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

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

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

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

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

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

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

for , when choosing sufficiently small. Hence,

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

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

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

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

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

Exercise 4.19.

  1. Given , let

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

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

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

Exercise 4.20. Prove that

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

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

    CT1
    If , then and .

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

    Show that is a ring.

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

5Operations on transseries

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

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

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

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

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

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

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

5.1Differentiation

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

D1
, for all .

D2
is strongly linear.

D3
, for all .

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

D4
, for all .

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

D5
, for all with .

D6
, for all .

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

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

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

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

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

for certain monomials and in . For any , we have

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

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

by strong linearity. We conclude that

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

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

For , the derivative of a monomial must be given by

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

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

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

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

for all monomials .

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

Proposition 5.3. For all , we have

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

Proposition 5.4. Let be a transbasis.

  1. If or , then is stable under .

  2. If and , then is stable under .

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

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

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

Proposition 5.5. The derivation on is asymptotic and positive.

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

Given a monomial , we first observe that

belongs to . Moreover,

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

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

whence . If , then

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

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

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

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

Similarly, if is such that and , then

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

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

Exercise 5.1. For all , prove that

Exercise 5.2. For all with and , show that

Exercise 5.3. Let . Prove that

  1. .

  2. .

  3. .

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

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

D5
, for all with .

D6
, for all .

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

Exercise 5.5. Let . Characterize

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

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

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

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

  1. Show that is stable under differentiation.

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

  3. Show that

    for all .

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

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

5.2Integration

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

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

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

(5.1)

where

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

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

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

where

Then for all . Setting , we have

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

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

where the () are given by

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

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

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

(5.2)

Indeed, (5.2) defines a distinguished integral, since

and

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

Proposition 5.8. Let be a transbasis.

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

  2. If and , then is stable under .

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

with , we claim that

where are given by

Indeed, it is easily checked that . Furthermore,

whence , by the distinguished property of integration.

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

Exercise 5.10. Let .

  1. If and , then show that

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

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

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

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

5.3Functional composition

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

1
, for all .

2
is strongly linear.

3
, for all .

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

4
, for all .

We say that is asymptotic resp. increasing, if

5
, for all .

6
, for all .

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

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

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

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

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

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

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

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

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

For , the axioms 3 and 4 imply that

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

since

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

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

for all . Similarly,

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

Proposition 5.11.

  1. , for all and .

  2. , for all and .

  3. Let be such that and for all . Then

    (5.4)

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

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

and implies

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

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

since . We infer that

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

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

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

Then

Moreover, setting , we have

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

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

We have to show that coincides with

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

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

Exercise 5.13. Let and .

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

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

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

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

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

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

Exercise 5.17. Show that is stable under composition.

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

5.4Functional inversion

5.4.1Existence of functional inverses

Theorem 5.12. Any admits a functional inverse with

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

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

(5.5)

for any . In particular, for every , we have

Now the functional inverse of is given by

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

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

Now

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

5.4.2The Translagrange theorem

We define a scalar product on by

Given transseries and , let us denote

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

Theorem 5.13. Let be exponential transseries and . Then satisfies

Proof. Since for all , we have

Since and are exponential, we have

Using the rule , it follows that

Now integration by parts yields

But , since is exponential.

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

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

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

  1. Show that we do not always have .

  2. Give a necessary and sufficient condition for which

Exercise 5.20.

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

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

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

Exercise 5.21. Show that is stable under functional inversion.

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

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

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

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

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

6Grid-based operators

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

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

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

such that there exists a -linear grid-based operator

with

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

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

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

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

6.1Multilinear grid-based operators

6.1.1Multilinear grid-based operators

Let and be strong modules over a ring . A mapping

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

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

Example 6.1. Given monomial monoids and , all strongly linear mappings are multilinear grid-based operators. Denoting , we have in particular the following important types of linear grid-based operators:

  1. Left multiplication operators , with .

  2. Strong derivations . If admits -powers, then such derivations should also satisfy , whenever is well-defined for and .

  3. Strong integrations; these are partial, strongly linear right inverses of strong derivations , i.e. .

  4. Strong difference operators . If admits -powers, then such difference operators should also satisfy , whenever is well-defined for and ).

  5. Strong summation operators; these are partial, strongly linear right inverses of finite difference operators, i.e. , for some strong difference operator .

Example 6.2. Given a monomial monoid , the multiplication and the scalar product are strongly bilinear mappings.

Example 6.3. Compositions

of multilinear grid-based operators

are again multilinear grid-based operators.

Example 6.4. The -linear grid-based operators of the form form a -module. For instance, if is a strong derivation, where , then strong differential operators of the form

are linear grid-based operators. In section 6.4.1, we will see that we may actually define strong summations on spaces of grid-based operators.

6.1.2Operator supports

Let be an -linear grid-based operator, such that and are all subsets of a common monomial group . Then the operator support of is defined by

The operator support is the smallest subset of , such that

(6.1)

for all . Given , we also denote

Example 6.5. We have

for multilinear operators () and .

Exercise 6.1. Let be infinitesimal linear grid-based operators (i.e. for ).

  1. Show that is well-defined for non-commutative series .

  2. Determine the largest subspace of on which is a well-defined bijection.

Exercise 6.2.

  1. Is a multilinear grid-based operator necessarily a multilinear well-based operator?

  2. Show that for well-based series, if is totally ordered. Here denotes the strong dual of .

  3. Show that (b) does not hold for grid-based series. How to characterize ?

Exercise 6.3.

  1. Let be the set of transseries with for all and consider the space of operators

    (6.2)

    such that is a grid-based. Show that operates on and that is stable under composition.

  2. Let and consider the space of operators (6.2), such that is a grid-based family. Show that operates on and that is stable under composition.

6.2Strong tensor products

It is often useful to consider multilinear mappings

as linear mappings

A similar thing can be done in the strongly linear setting. We will restrict ourselves to the case when are grid-based modules, in which case the tensor product has a particularly nice form:

Proposition 6.6. Let be monomial sets and denote

Consider the mapping

This mapping is well-defined and strongly multilinear. Moreover, for every strongly multilinear mapping

into an arbitrary strong -module, there exists a unique strongly linear mapping

such that .

Lemma 6.7. Let be a grid-based family of monomials in . Then there exist grid-based families with .

Proof. Let be the projection of on , for . We have for certain and . Given , we will denote

Given , we define its multiplicity by

Given , let

Then for all , we have

Hence

for ().

Proof of proposition 6.6. Given grid-based subsets with the set is clearly a grid-based subset of . This implies that is well-defined. More generally, given grid-based families of terms , the family is again grid-based. Now consider arbitrary grid-based families and let , for . Then

This shows that is multilinear.

Inversely, if is a grid-based subset of , then its projections on for are again grid-based, and we have

Consequently, given a strongly multilinear mapping

the mapping

is well-defined. Moreover, if , then the above lemma implies that there exist with , whence

It follows that and are summable families in . Finally, using strong associativity, we have

We conclude that .

We call (together with the mapping ) the strong tensor product of . An immediate consequence of proposition 6.6 is the principle of extension by strong multilinearity:

Corollary 6.8. Let and be monomial monoids and assume that is a mapping, such that

is a grid-based family for any grid-based subsets . Then there exists a unique strongly multilinear mapping

with .

Proof. Using extension by strong linearity, there exists a unique strongly linear mapping , with . Then is the unique mapping we are looking for.

Exercise 6.4. When do we have , where denotes the space of strongly linear mappings from into ?

Exercise 6.5.

  1. Generalize proposition 6.6 to the case of well-based series.

  2. Show that a well-based family corresponds to an element of .

  3. Define a family to be super-grid-based with and . Show that is a strong -algebra for super-grid-based summation.

  4. Give an example of a grid-based family which is not super-grid-based.

Exercise 6.6. Show that tensor products exist in the general strongly linear setting (see also exercise 2.20). Hint:

  1. Let be strong modules. Consider the set of all mappings , whose support is contained in a set such that each is a summable subset of . Construct a natural embedding and give the structure of a strong -module.

  2. Let be the strong submodule of , which is generated by all elements of the form

    where the are mutually disjoint. Then the strong quotient

    with satisfies the universal property of the strong tensor product.

6.3Grid-based operators

6.3.1Definition and characterization

Let and be monomial sets. A mapping is said to be a grid-based operator if there exists a family of multilinear grid-based operators , such that for all , the family is grid-based, and

(6.3)

We call a multilinear family for . Considering the family of a single element , the formula (6.3) reduces to

(6.4)

Assuming that , each is uniquely determined and we call it the homogeneous part of degree of :

Proposition 6.9. Let be a grid-based operator and let be multilinear grid-based operators, such that (6.4) holds for all . If and , then for each .

Proof. We observe that it suffices to prove that for each , since the are symmetric and is torsion-free. Assume the contrary and let be such that for some . Choose

Since is a grid-based family, there exist only a finite number of indices , such that . Let be those indices.

Let for all . For any , we have , by multilinearity. On the other hand,

for each , so that

The matrix on the left hand side admits an inverse with rational coefficients (indeed, by the sign rule of Descartes, a real polynomial cannot have distinct positive zeros unless ). Since , it follows that . This contradiction completes the proof.

Proposition 6.10. Let be a grid-based operator and assume that . Then there exist a unique multilinear family for , such that each is symmetric.

Proof. Let be an arbitrary multilinear family for . Then the defined by

form a multilinear family of symmetric operators for . Moreover, each is determined uniquely in terms of by

We conclude by proposition 6.9.

Assume that and are subsets of a common monomial group . If we have and and are as in proposition 6.10, then we call

the operator support of . For all , we have

Notice also that for all .

6.3.2Multivariate grid-based operators and compositions

In a similar way that we have the natural isomorphism

for tensor products, we also have a natural isomorphism

for Cartesian products. This allows us to reinterpret mappings “in several series” as mappings “in one series” . In particular, any multilinear grid-based operator can be seen as a grid-based operator in from into . More generally, the natural isomorphism may be used in order to extend the notion of grid-based operators to mappings .

Let and be two grid-based operators. Then is again a grid-based operator. Indeed, let and be multilinear families for and . Then for all , we have

so that the defined by

form a multilinear family for .

Exercise 6.7. Assume that and let be a grid-based operator. Is it true that for any there exists an with ?

Exercise 6.8. Define the “derivative” of a grid-based operator .

Exercise 6.9.

  1. Characterize the intervals of the set of infinitesimal transmonomials (i.e. for all and , we have ), such that for all , the operator is a grid-based operator on .

  2. With as in (a), show that the operators and are grid-based.

6.4Atomic decompositions

6.4.1The space of grid-based operators

Let be the space of strongly multilinear operators . Then is clearly a -module. More generally, a family of elements in is said to be summable, if for all , we have

In that case, we define the sum by

This gives the structure of a strong -module.

Similarly, let denote the space of grid-based operators . This space is clearly a -module. A family is said to be summable, if for all , the family

is a grid-based family. In that case, the sum

is a grid-based operator and is a strong -module for this summation. In particular, we have

(6.5)

for all . We call (6.5) the decomposition of into homogeneous parts.

6.4.2Atomic decompositions

Let and be monomials sets. Given and , the operator

with

is an -linear grid-based operator. Operators of this form, which are said to be atomic, form a strong basis of , since any operator may be uniquely decomposed as

(6.6)

We call (6.6) the atomic decomposition of . More generally, an atomic family is a summable family , with and , where and .

Assume now that . Given a grid-based operator , let the be as in proposition 6.10. Then we have

(6.7)

and we call this formula the atomic decomposition of . More generally, a family , where and , is called an atomic family, if the family is summable in .

Since the in (6.7) are symmetric, the atomic decomposition is slightly redundant. Let be the equivalence relation on , such that if and only if and there exists a permutation of indices , such that for all . Given , and , we define

Clearly, does not depend on the choice of and operators of the form will be called symmetric atomic operators. Setting

for all , the decomposition

is unique. We call it the symmetric atomic decomposition of .

6.4.3Combinatorial interpretation of atomic families

Consider an atomic family with for each . We may interpret the as combinatorial boxes with inputs and output . We define a partial ordering on by . Given a subset of , we denote by the atomic family of all with . Finally, given a monomial set , we denote by the atomic family , so that is the identity operator on .

Remark 6.11. A convenient way to check whether a family is atomic is to prove that for each grid-based subset we have

  1. The set is grid-based.

  2. For each , there exist only a finite number of with .

Consider two atomic families and , where and for all and . We define their composition to be the family with formal index set

and

We may see the as combinatorial structures, such that the outputs of the coincide with the inputs of (see figure 6.1). A similar computation as at the end of section 6.3.2 yields:

Proposition 6.12. Let and be two atomic families as above. Then is again an atomic family and

Fig. 6.1. Combinatorial interpretation of the composition of atomic operators.

Exercise 6.10. Show that the mapping

from exercise 6.1 is a strong -algebra morphism.

Exercise 6.11. Show that and are naturally isomorphic as sets. Show that this natural isomorphism also preserves the strong -module structure.

Exercise 6.12. Show that an atomic family is summable, if and only if is grid-based for every grid-based subset .

Exercise 6.13. Generalize the theory from sections 6.3 and 6.4 to the well-based setting.

6.5Implicit function theorems

Let and be monomial sets which are contained in a common monomial monoid. Consider a grid-based operator

together with its atomic decomposition . We say that

If is strictly extensive in , then we have in particular

for all , and . Consequently, is also contracting in , since , whenever , and are such that for all .

Given a grid-based operator as above, the aim of the implicit function theorems is to construct a grid-based operator , such that

(6.8)

for all . In the well-based context, a sufficient condition for the existence (and uniqueness) of such an operator is the strict extensiveness of in . In the grid-based context we need additional conditions in order to preserve the grid-based property. In this section, we present three possible choices for these extra conditions, which lead each to a grid-based implicit function theorem.

6.5.1The first implicit function theorem

Theorem 6.13. Consider a grid-based operator

which is extensive in with multipliers in a grid-based set . Then for each , there exists a unique which satisfies (6.8) and the operator is grid-based. Furthermore, for all , we have

If , then we also have

Proof. Let be the atomic decomposition of . Consider the family , where the are recursively defined by

See figure 6.2 for the illustration of a member of . We claim that is an atomic family. Indeed, let be a grid-based set. Let us prove by induction over that

(6.9)

for all . This is clear if . If , then we may write , where for at least one . By the induction hypothesis, we have , so that . This shows that . Moreover, given , there are only a finite number of with . It follows that is an atomic family, by remark 6.11 and the fact that each is atomic.

Fig. 6.2. Illustration of a member of . The white dots correspond to elements of and the black dots to elements of . The light boxes belong to and the dark ones to .

Now consider the grid-based operator

Identifying and via the natural isomorphism, we have

for all . Similarly, for all , we have

Applying proposition 6.12, we conclude that

for all . As to the uniqueness of , assume that are such that and . Then we have

which is only possible if .

Let us finally prove the bounds on the supports. The first one follows directly from (6.9). The second one follows from the fact that the operator support of an element in is the product of the operator supports of all combinatorial boxes on the nodes of the corresponding tree.

6.5.2The second implicit function theorem

Theorem 6.14. Consider a grid-based operator

such that

is grid-based and infinitesimal for all . Then, for each , there exists a unique which satisfies (6.8) and the operator is grid-based.

Proof. Let , with support . There exist finite sets and , such that . Let

Then we have and

We now observe that maps into itself, so we may apply theorem 6.13 to this mapping with the same . This proves the existence and uniqueness of . With similar notations as in theorem 6.13, it also follows that is again a grid-based atomic family, so that is a grid-based operator.

6.5.3The third implicit function theorem

Theorem 6.15. Consider a grid-based operator

which is strictly extensive in . Assume that

is grid-based and . Then for each , there exists a unique which satisfies (6.8) and the operator is grid-based.

Proof. With the notations of the proof of theorem 6.13, let us first show that is a well-based family for every grid-based set . For each , let . To each , we associate a tree , by setting if , and

for . Since is strictly extensive in , this mapping is strictly increasing. Furthermore, the inverse image of each tree in is finite and is well-based by Higman's theorem. This together implies that is well-based.

Let us show that is actually a grid-based. For each tree , let , so that for all . Now consider

Let be the finite subset of -maximal elements of . Notice that we may naturally interpret elements

as trees

Given a grid-based set and , let us denote

Consider

We claim that satisfies the hypothesis of theorem 6.13.

Indeed, consider and let us show by induction over that for every with . Now

for some . In other words, there exists an embedding which fixes the root. Consider a factorization of this embedding through a tree with , such that for all with , and such that

is minimal. Assume for contradiction that . We distinguish three cases:

Case 1
for some .

Consider the tree with the same nodes as and if and . Then we may factor through with and .

Case 2
for some .

Let be a child of whose root is not in the image of . Then we may factor through a tree which is obtained by adding as a child to at the appropriate place, in such a way that . Moreover, since , the induction hypothesis implies that , so that .

Case 3
we are not in cases 1 and 2.

Since , there exists a with a successor . Let be the children of , so that is the root of for some . Consider the tree which is obtained by substituting the subtree of with root by

By the induction hypothesis, we have , so that . Furthermore, we may factor through in such a way that .

In each of these three cases, we have thus shown how to obtain a factorization through a tree with and . This contradiction of the minimality assumption completes the proof of our claim. We conclude the proof by applying theorem 6.13 and by noticing that is grid-based, so that is a grid-based operator.

Exercise 6.14. Give an example of a contracting mapping which is not strictly extensive.

Exercise 6.15. In the first implicit function theorem, show that the condition that has multipliers in a grid-based set cannot be omitted. Hint: consider the equation .

Exercise 6.16. Give an example where the second implicit function theorem may be applied, but not the first. Also give an example where the third theorem may be applied, but not the second.

Exercise 6.17. Prove the following implicit function theorem for well-based series:

Let be a well-based operator which is extensive in . Then for each , there exists a unique which satisfies (6.8) and the operator is well-based.

6.6Multilinear types

One obtains interesting subclasses of grid-based operators by restricting the homogeneous parts to be of a certain type. More precisely, let be a monomial monoid and let be a set of strongly multilinear mappings . We say that is a multilinear type if

MT1
The constant mapping is in , for each .

MT2
The projection mapping is in , for each .

MT3
The multiplication mapping is in .

MT4
If , then .

Given subsets of , we say that a strongly multilinear mapping

is an atom of type , if for , there exists a mapping in , such that coincides with the restriction of the domain and image of to resp. . We say that is of type , if is the sum of a grid-based family of atoms of type . A grid-based operator

is said to be of type , if is of type for all .

Example 6.16. For any set of grid-based operators , there exists a smallest multilinear type which contains . Taking to be the field of grid-based transseries, interesting special cases are obtained when taking or . Grid-based operators of type resp. are called differential resp. integral grid-based operators.

Exercise 6.18. Show that compositions of grid-based operators of type are again of type .

Exercise 6.19. State and prove the implicit function theorems from the previous section for grid-based operators of a given type .

Exercise 6.20. For which subfields of and do the grid-based operators of types and coincide?

7Linear differential equations

Let be a linear differential operator with transseries coefficients and . In this chapter, we study the linear differential equation

(7.1)

In our grid-based context, it is convenient to study the equation (7.1) in the particular case when and can be expanded w.r.t. a plane transbasis . In order to solve the equation , we necessarily need to consider solutions in . Therefore, we will regard as an operator on . Assuming that we understand how to solve (7.1) for and and assuming that we understand how this resolution depends on and upward shiftings, the incomplete transbasis theorem will enable us to solve (7.1) in the general case.

A first step towards the resolution of (7.1) is to find candidates for dominant terms of solutions . It turns out that the dominant monomial of only depends on the dominant term of , except if , where is a finite set of “irregular” monomials. The corresponding mapping is called the trace of , and its properties will be studied in section 7.3. In particular, we will show that is invertible.

In section 7.4 we will show that the invertibility of the trace implies the existence of a strong right inverse of . Moreover, the constructed right inverse is uniquely determined by the fact that for all (for which we call it “distinguished”). Furthermore, we may associate to each a solution to the homogeneous equation and these solutions form a “distinguished basis” of the space of all solutions.

Now finding all solutions to (7.1) it equivalent to finding one particular solution and the space of solutions to the homogeneous equation. Solving the homogeneous equation is equivalent to solving the Riccati equation

(7.2)

which is an algebraic differential equation in (see section 7.2). In section 7.5, we will show that (7.2) is really a “deformation” of the algebraic equation , so we apply a deformation of the Newton polygon method from chapter 3 to solve it. In fact, we will rather solve the equation “modulo ”, which corresponds to finding the dominant monomials in of solutions to the homogeneous equation (see section 7.6).

Of course, an equation like does not admit any non-trivial solutions in the transseries. In order to guarantee that the solution space of the homogeneous equation has dimension , we need to consider transseries solutions with complex coefficients and oscillating monomials. In section 7.7 we will briefly consider the resolution of (7.1) in this more general context. In section 7.8 we will also show that, as a consequence of the fact that , we may factor as a product of linear operators.

7.1Linear differential operators

7.1.1Linear differential operators as series

Let be the field of grid-based transseries in over a real-closed exp-log field of constants . In what follows, it will often be convenient to regard linear differential operators as elements of . In particular, each non-zero operator admits a dominant monomial

and a dominant coefficient

for which we will also use the alternative notation

Similarly, the asymptotic relations , , , , etc. extend to . In order to avoid confusion with the support of as an operator, the support of as a series will be denoted by .

Proposition 7.1. Given with , we have

Proof. Without loss of generality, one may assume that , modulo division of by . Then

Now each term in the big sum at the right hand side is infinitesimal.

7.1.2Multiplicative conjugation

Given a linear differential operator and a non-zero transseries , there exists a unique linear differential operator , such that

for all . We call a multiplicative conjugate of . Its coefficients are given by

(7.3)

Notice that for all .

Proposition 7.2. If , then

Proof. From it follows that for all . Then (7.3) implies . Conversely, we have

7.1.3Upward shifting

In order to reduce the study of a general linear differential equation over the transseries to the case when the coefficients are exponential, we define the upward shifting and downward shifting of to be the unique operators with

for all . In other words, the resolution of is equivalent to the resolution of . The coefficients of and are explicitly given by

(7.4)
(7.5)

where the are Stirling numbers of the first resp. kind, which are determined by

Upward and downward shifting are compatible with multiplicative conjugation in the sense that

for all . We will denote by resp. the -th iterates of and .

Exercise 7.1. Let and .

  1. Show that there exists a unique with

    for all .

  2. Give an explicit formula for for each .

  3. Show that is a ring homomorphism.

Exercise 7.2. Let and . Denote by the field with differentiation .

  1. Show that each can be reinterpreted as an operator .

  2. Given , let be the result of the substitution of for in . If , then show that .

Exercise 7.3. Let and , so that .

  1. Given (see exercise 6.3), let . Show that naturally operates on . Also show that the space of all such operators only depends on .

  2. Same question, but for .

  3. Under which condition on can the operator in either of the above questions be rewritten as an operator of the form ?

Exercise 7.4. Let be a flat subspace of .

  1. Extend the definition of in exercises 6.3 and 7.3 to the present case.

  2. Let be two flat subspaces of of the above type. Characterize .

Exercise 7.5. Let .

  1. Determine so that .

  2. Given , construct the -th iterate of .

  3. Determine the maximal flat subspace of such that .

Exercise 7.6. Let . Consider an operator

where .

  1. Show that and let be such that .

  2. Assuming that , show that there exists a with .

Exercise 7.7. Let be as in exercise 7.3(a) or (b), and .

  1. Given with and . Show that

    are well-defined.

  2. Let , , and . Show that

    are well-defined.

  3. Given a transmonomial with and , show that

    is well-defined. Extend the definition of to and show that corresponds to the distinguished integration.

7.2Differential Riccati polynomials

7.2.1The differential Riccati polynomial

Given a transseries , we may rewrite the successive derivatives of as

(7.6)

where the are universal differential polynomials given by

For instance:

In particular, for each linear differential operator , there exists a unique differential polynomial such that

(7.7)

for all . We call the differential Riccati polynomial associated to . Notice that is uniquely determined by the polynomial

which is called the algebraic part of .

7.2.2Properties of differential Riccati polynomials

Let be a differential polynomial with transseries coefficients. Like in the case of differential operators, we may consider as a series in , where denotes the set of transmonomials. Given we also define to be the unique differential polynomial in , such that

for all . We call an additive conjugate of . Additive conjugates of the differential Riccati polynomials correspond to multiplicative conjugates of the corresponding linear differential operators:

Proposition 7.3. For all and , we have

(7.8)

Proof. For all , we have

so (7.8) follows from the uniqueness property of differential Riccati polynomials.

Given a linear differential operator , we call

the derivative of .

Proposition 7.4. For all , we have

(7.9)
(7.10)

Proof. We claim that for all . Indeed, and, using induction,

for all . Our claim immediately implies (7.9) and (7.10).

Corollary 7.5. For all and , we have

(7.11)
(7.12)

Exercise 7.8. Prove that

Exercise 7.9. Show that

where and are defined in section 8.2.3.

7.3The trace of a linear differential operator

Let be a linear grid-based operator. A term is said to be regular for , if is regular for all with and if does not depend on the choice of such an . In particular, a monomial in is said to be regular for if it is regular as a term. We will denote by the set of all regular monomials for and by the set of irregular monomials. The mapping

is called the trace of . For all , we have

(7.13)

Given a linear differential equation over the transseries with , finding a term with corresponds to finding a good candidate for the first term of a solution. In the next section we will show that this first term may indeed be completed into a full solution.

7.3.1The trace relative to plane transbases

Let be a linear differential operator, where is a plane transbasis. We will consider as a grid-based operator on , so that its trace is a mapping from into .

Proposition 7.6. Given , we have

Proof. Modulo replacing by , we may assume without loss of generality that and . Let be minimal with , so that if and only if .

Now implies . Furthermore, for all but the finite number of such that . It follows that for a sufficiently small , whence .

If , then . Given with , we have either or with . In the first case, . In the second case, we have either and or and . So we always have . Hence , by strong linearity.

Proposition 7.7. For every there exists a unique with .

Proof. Let and consider . We will prove the proposition by induction over the maximal such that . If such an does not exist, then we have nothing to prove. Otherwise, proposition 7.2 implies

It follows that for certain . By the induction hypothesis, there exists an with . Hence for . Furthermore, given , we have . This proves the uniqueness of .

Proposition 7.8. The trace of is invertible.

Proof. Let . By the previous proposition, there exists a unique with . Modulo the replacement of by we may assume without loss of generality that . Let be minimal with . Then

Setting

we thus have . Notice that proposition 7.6 implies .

Example 7.9. Let and consider the operator

Given and , we have

Now the following cases may occur:

7.3.2Dependence of the trace on the transbasis

Let , where is a plane transbasis and let us study the dependence of the trace of on . Given a plane supertransbasis of , proposition 7.6 implies that and clearly coincides with on . Similarly, if is a second transbasis such that and coincide as subsets of , then and , where denotes the “identification mapping”.

Proposition 7.10. Let . Then and for all .

Proof. We clearly have

for all . Given

let us show that . Modulo replacing by , we may assume without loss of generality that and .

Assume that , so that , and . Then implies and . Hence . Since , we also observe that , whence . But this means in particular that

In other words, .

Assume now that and let be minimal with . Then so

On the other hand, , whence . This is only possible if and . In other words, .

Proposition 7.11. Let be a transbasis of level containing and denote . Let and let be the set of singular monomials of as an operator on . Then

Proof. Clearly, . Assume for contradiction that there exists an . Then there exists an with and . Let be a super-transbasis of for , of level , and which contains . Setting , proposition 7.10 now implies

Hence, so that . This contradiction completes the proof.

Proposition 7.12. Let be a linear differential operator on . Then the trace of is invertible.

Proof. Given , the incomplete transbasis theorem implies that there exists a transbasis for like in proposition 7.11. By proposition 7.8, there exists an with . By proposition 7.11, we have and .

7.3.3Remarkable properties of the trace

Assume again that , where is a plane transbasis.

Proposition 7.13. The set

is finite.

Proof. Considering as indeterminates, the successive derivatives of satisfy

where the are as in (7.6). Consequently, we may see

as an element of for each .

Assume for contradiction that is infinite. Since , there exists an infinite sequence of elements in . For each , let be such that . Now each induces an ideal of , generated by all coefficients of with . We have and each is a zero of , but not of . It follows that , which contradicts the Noetherianity of .

Corollary 7.14. There exist unique strongly linear mappings

which extend and . Furthermore,

  1. and .

  2. and .

Proposition 7.15. Given , we have

and

Proof. Let . Then for all , we have and . By strong linearity, it follows that for all with . This shows that and .

Conversely, let and assume that . Then for all with . If , then proposition 7.6 implies and for all . Hence and we may choose so that . But then and . If satisfies , then we clearly have .

Similarly, let and denote . Then for all with . Moreover, we may choose such that and for all . This ensures that . Denoting , we conclude that , whence .

As to second identity, let . Then and implies . Hence .

Exercise 7.10. Prove the propositions of section 7.3.3 for operators .

Exercise 7.11. Generalize the results from this section to the well-based setting.

Exercise 7.12. Let . Determine .

7.4Distinguished solutions

Let and be monomial sets, such that is totally ordered. Given a linear grid-based operator and , we say that is a distinguished solution to the equation

(7.14)

if for any other solution , we have . Clearly, if a distinguished solution exists, then it is unique. A mapping is said to be a distinguished right inverse of , if and is a distinguished solution solution to (7.14) for each . A distinguished solution to the homogeneous equation

(7.15)

is a series with and for all other solutions with . A distinguished basis of the solution space of (7.15) is a strong basis which consists exclusively of distinguished solutions. If it exists, then the distinguished basis is unique.

Remark 7.16. Distinguished solutions can sometimes be used for the renormalization of “divergent” solutions to differential equations; see [vdH01b] for details.

7.4.1Existence of distinguished right inverses

Theorem 7.17. Assume that the trace is invertible and both and extend to strongly linear mappings

Assume also that and are grid-based. Then

  1. admits a distinguished and grid-based right inverse

  2. The elements with form a distinguished basis for .

Proof. Let . Then the operator is strictly extensive, and the operator coincides with on . Now consider the functional

By theorem 6.14, there exists a strongly linear operator

such that for all . Consequently,

is a strongly linear right inverse for . Given , we also observe that ; otherwise, . Consequently, is the distinguished solution of (7.14) for all . This proves (a).

As to (b), we first observe that

for all . The solution is actually distinguished, since

and for all . In fact, we claim that

(7.16)

Indeed, if , then we would have , so

which is impossible. Now let be an arbitrary solution to (7.15) and consider

Then we have for all , by the distinguished property of the and (7.16). Consequently, . This proves (b).

Corollary 7.18. Let be a plane transbasis and let be a linear differential operator on . Then admits a distinguished right inverse and admits a finite distinguished basis.

Proof. In view of proposition 7.8 and corollary 7.14, we may apply theorem 7.17. By general differential algebra, we know that is finite dimensional.

Corollary 7.19. Let be a linear differential operator on . Then admits a distinguished right inverse and admits a finite distinguished basis.

Proof. Given , let us first prove that admits a distinguished solution. Let be a transbasis for as in proposition 7.11 and consider . Then

From proposition 7.11, it follows that

for all

Hence is the distinguished solution to . In particular, the construction of is independent of the choice of . The operator is strongly linear, since each grid-based family in is also a family in for some as above, and is strongly linear on .

Example 7.20. With as in example 7.9, we have

7.4.2On the supports of distinguished solutions

Let be a plane transbasis and let be a linear differential operator on of order .

Proposition 7.21. The operator support of is bounded by

where

are grid-based sets and .

Proof. With the notations from the proof of theorem 7.17,

It follows that

Recall that is finite, by proposition 7.13. This also implies that is grid-based.

Proposition 7.22. Given , let

Setting , we have

  1. maps into .

  2. maps into .

  3. .

Proof. For all , we have

This shows (a). As to (b), let and consider

Then is a bijection between and and maps into . By theorem 7.17, it follows that the restriction of to admits a distinguished right inverse, which necessarily coincides with the restriction of to . This proves (b), since and . Moreover, for each element of the distinguished basis of , we have . This proves (c).

Exercise 7.13. Show that .

Exercise 7.14. Show that we actually have in proposition 7.22(c).

Exercise 7.15. Let and be plane transbases in the extended sense of exercise 4.15. Given , let denote the distinguished right inverse of as an operator on .

  1. Show that is the restriction of to , if is a supertransbasis of .

  2. If , then show that if and only if .

  3. If , then show that for all .

Exercise 7.16. Let be a flat subspace of and the steep complement of , so that . Consider as a strong operator on (notice that is not -linear). Let be the set of monomials such that does not depend on and such that the mapping is invertible.

  1. Exhibit an operator in which maps to and relate and .

  2. Generalize theorem 7.17 to the setting of strongly additive operators and relate the distinguished right inverses of as an operator on and as an operator on .

  3. Given a plane transbasis , and , give a concrete algorithm to compute the recursive expansion of .

Exercise 7.17. Let and let be a transmonomial. Prove that

Exercise 7.18. Let and . When do we have

Here is the unique operator such that

for all .

Exercise 7.19.

  1. Show that for and .

  2. Show that for and .

  3. Do we always have ?

Exercise 7.20.

  1. Prove that each non-zero admits a distinguished right-inverse on .

  2. Can be infinite?

  3. Same questions for .

Exercise 7.21. Consider an operator as in exercise 7.6.

  1. For any , show that is an operator of the same kind.

  2. Show that admits a distinguished right-inverse on .

  3. Assuming that , show that admits a distinguished right-inverse on .

  4. Given , show that admits a distinguished solution, which is not necessarily grid-based, but whose support is always well-based and contained in a finitely generated group.

  5. Show that (d) still holds if .

  6. Given a general , show that admits a well-based distinguished solution.

  7. Give a bound for the cardinality of .

Exercise 7.22. Let be the space of partial grid-based operators , such that is a space of finite codimension over in . Two such operators are understood to be equal if they coincide on a space of finite codimension in .

  1. Show that is a -algebra under composition.

  2. Show that each induces a unique operator in with .

  3. Show that the skew fraction field of in consists of operators with and . Hint: show that for any with , there exist with and .

Exercise 7.23. Let , where denotes the field of exponential transseries.

  1. If , then show that there exists a decomposition

    with , and .

  2. If and is sufficiently small, then show how to define .

  3. Given , extend the definition of from exercise 7.7(c) to a definition of on a suitable strong subvector space of .

7.5The deformed Newton polygon method

Let be a linear differential operator and consider the problem of finding the solutions to the homogeneous equation . Modulo upward shiftings it suffices to consider the case when the coefficients of can all be expanded w.r.t. a plane transbasis . Furthermore, theorem 7.17 and its corollaries imply that it actually suffices to find the elements of .

Now solving the equation is equivalent to solving the equation for . As we will see in the next section, finding the dominant monomials of solutions is equivalent to solving the “Riccati equation modulo

(7.17)

for . It turns out that this equation is really a “deformation” of the algebraic equation

(7.18)

In this section, we will therefore show how to solve (7.17) using a deformed version of the Newton polygon method from chapter 3.

7.5.1Asymptotic Riccati equations modulo

Let is a plane transbasis and . We regard as a linear differential operator on . Given , consider the asymptotic versions

(7.19)

and

(7.20)

of (7.17) resp. (7.18). We call (7.19) an asymptotic Riccati equation modulo . A solution of (7.19) is said to have multiplicity , if for all and .

Given , we notice that for all ,

(7.21)

We say that is a starting monomial of relative to (), if is a starting monomial of relative to (7.20). Starting terms of solutions and their multiplicities are defined similarly. The Newton degree of () is defined to be the Newton degree of (7.20). The formula (7.21) yields the following analogue of proposition 3.4:

Proposition 7.23. If is a solution to (7.19), then is a starting term of relative to (7.19).

Proof. Assume the contrary, so that there exists an index with for all . But then

for all . Hence

and similarly

for all . In other words,

and .

7.5.2Quasi-linear Riccati equations

We say that () is quasi-linear if its Newton degree is one (i.e. if (7.20) is quasi-linear). We have the following analogue of lemma 3.5:

Proposition 7.24. If () is quasi-linear, then it admits a unique solution .

Proof. Let and consider the well-based operator

Since () is quasi-linear, we have

(7.22)

for all and . Moreover, on we have . Since is a differential polynomial of degree , we thus have

(7.23)

when considering as an operator on . Combining (7.22) and (7.23), we conclude that

for all with . By theorem 6.14, it follows that the equation

(7.24)

admits a unique fixed point in . We claim that this is also the unique solution to ().

Let us first show that is indeed a solution. From (7.24), we get

(7.25)

On the other hand, we have for :

(7.26)
(7.27)

In other words, and . Assume finally that is such that . Then (7.25), (7.26) and (7.27) also imply that

In other words, .

7.5.3Refinements

Given a refinement

(7.28)

where and , the equation (7.19) becomes

(7.29)

where satisfies . We recall that the coefficients of the corresponding algebraic equation

(7.30)

are given by

Let us show that the analogues of lemmas 3.6 and 3.7 hold.

Proposition 7.25. Let . Then the Newton degree of

(7.31)

equals the multiplicity of as a starting term of relative to ().

Proof. For a certain transmonomial , the Newton polynomial relative to is given by

Then, similarly as in the proof of lemma 3.6, we have

for all , and we conclude in the same way.

Proposition 7.26. Let be the Newton degree of (). If admits a unique starting term of multiplicity , then

  1. The equation

    (7.32)

    is quasi-linear and has a unique solution with .

  2. Any refinement

    (7.33)

    transforms (7.32) into an equation of Newton degree .

Proof. Part (a) follows immediately from lemma 3.7(a) and the fact that . Now consider a refinement (7.33). As to (b), let be such that the the Newton polynomial associated to is given by

By the choice of , we have

It follows that the term of degree in vanishes, so cannot admit a root of multiplicity . We conclude by proposition 7.25.

7.5.4An algorithm for finding all solutions

Putting together the results from the previous sections, we obtain the following analogue of polynomial_solve:

Algorithm riccati_solve
Input: An asymptotic Riccati equation (7.19) modulo .
Output: The set of solutions to (7.19) in .

  1. Compute the starting terms of relative to (7.20).

  2. If and is a root of multiplicity of , then let be the unique solution to (7.32). Refine (7.28) and apply riccati_solve to (7.29). Return the so obtained solutions to (7.19).

  3. For each , refine and apply riccati_solve to the new equation in . Collect and return the so obtained solutions to (7.19), together with , if .

Proposition 7.27. The algorithm riccati_solve terminates and returns all solutions to (7.19) in .

Since is only real closed, the equation (7.19) does not necessarily admit starting terms when counting with multiplicities. Consequently, the equation may admit less than solutions. Nevertheless, we do have:

Proposition 7.28. If the Newton degree of (7.19) is odd, then (7.19) admits at least one solution in .

Proof. If , then we apply the proposition 7.24. Otherwise, there always exists a starting monomial , such that is odd as well. Since is real closed, it follows that their exists at least one starting term of the form of odd multiplicity . Modulo one application of proposition 7.26, we may assume that , and the result follows by proposition 7.25 and induction over .

Example 7.29. Consider the linear differential operator

with

The starting terms for are and (of multiplicity ). The refinement leads to

so is a solution to (7.17). The other starting term leads to

and admits two starting terms . After one further refinement, we obtain the following two additional solutions to (7.17):

7.6Solving the homogeneous equation

Let be a linear differential operator on , where is a plane transbasis. Let be the solutions to (7.17), as computed by riccati_solve, and their multiplicities. We will denote

The following proposition shows how to find the elements of when we consider as an operator on :

Proposition 7.30. We have

Proof. Let and consider the operator . Then

But is precisely the multiplicity of as a solution of (7.17).

In order to find the elements of when we consider as an operator on , we have to study the dependence of under extensions of and upward shifting. Now riccati_solve clearly returns the same solutions if we enlarge . The proposition below ensures that we do not find essentially new solutions when shifting upwards. In the more general context of oscillating transseries, which will be developed in the next section, this proposition becomes superfluous (see remark 7.38).

Proposition 7.31. Assume that

Then

Proof. Assume that is a solution to

(7.34)

of multiplicity . Let , and let be the multiplicity of as a solution of (7.17). We have to prove that

Let be -maximal in and set . If such an does not exist, then set . Then, modulo replacing by , we may assume without generality that either or .

Let us first consider the case when . Since all starting monomials for are necessarily in , there exists an with for all . It follows from (7.4) that

In other words, is not a starting monomial for , so neither (7.17) nor (7.34) holds.

Let us now consider the case when and observe that is minimal with . If , then , so we neither have (7.17) nor (7.34). If , then

so does not satisfy (7.34). Similarly, if , then , which implies (7.34). Moreover, setting , we have

In other words, , whence .

Theorem 7.32. Let be a linear differential operator on of order , whose coefficients can be expanded w.r.t. a plane transbasis . Assume that are the solutions to (7.17), with multiplicities . Then

(7.35)
(7.36)

Proof. Let denote the set of exponential transmonomials and let us first assume that . Then there exists a supertransbasis of , with and . Now riccati_solve returns the same solutions with respect to and . Therefore, proposition 7.30 yields

In general, we have for some . So applying the above argument to , combined with proposition 7.31, we again have (7.35). As to (7.36), assume that and let . Then

The result now follows from the fact that the form a basis of .

Since the equation (7.17) may admit less than solutions (see remark 7.27), we may have . Nevertheless, proposition 7.28 implies:

Corollary 7.33. If is a linear differential operator of odd order, then the equation admits at least one non-trivial solution in .

7.7Oscillating transseries

Let be a linear differential operator of order . Since is only real closed, the dimension of the solution space of can be strictly less than . In order to obtain a full solution space of dimension , we have both to consider transseries with complex coefficients and the adjunction of oscillating transmonomials. In this section we will sketch how to do this.

7.7.1Complex and oscillating transseries

Let be the set of transmonomials and consider the field

of transseries with complex coefficients. Then most results from the previous sections can be generalized in a straightforward way to linear differential operators . We leave it as an exercise for the reader to prove the following particular statements:

Proposition 7.34. Let be a linear differential operator on . Then admits a distinguished right inverse and admits a finite distinguished basis.

Proposition 7.35. Let be a linear differential operator, where is a plane transbasis, and . If the Newton degree of (7.19) is , then (7.19) admits solutions, when counted with multiplicities.

An oscillating transseries is an expression of the form

(7.37)

where and . Such transseries can be differentiated in a natural way

We denote by

the differential ring of all oscillating transseries. Given an oscillating transseries , we call (7.37) the spectral decomposition of . Notice that

where if and only if and .

7.7.2Oscillating solutions to linear differential equations

Consider a linear differential operator . We have

where

since for all . In other words, “acts by spectral components” and its trace is determined by

Now let and consider the differential equation

(7.38)

This equation is equivalent to the system of all equations of the form

(7.39)

By proposition 7.34, the operators all admit distinguished right inverses. We call

the distinguished solution of (7.38). The operator , which is strongly linear, is called the distinguished right inverse of . The solutions to the homogeneous equation may be found as follows:

Theorem 7.36. Let be a linear differential operator on of order , whose coefficients can be expanded w.r.t. a plane transbasis . Assume that are the solutions to (7.17), with multiplicities . Then

(7.40)
(7.41)

Proof. Let , where , and . Then , considered as an operator on , satisfies

Hence , and . Furthermore,

is an element of with dominant monomial . By proposition 7.35, there are such solutions and they are linearly independent, since they have distinct dominant monomials. Consequently, they form a basis of , since . This proves (7.41). Since each element induces an element with dominant monomial in , we also have (7.40).

Corollary 7.37. Let be a linear differential operator on of order . Then .

Remark 7.38. Due to the fact that the dimension of is maximal in theorem 7.36, its proof is significantly shorter than the proof of theorem 7.32. In particular, we do not need the equivalent of proposition 7.31, which was essentially used to check that upward shifting does not introduce essentially new solutions.

Exercise 7.24. Assume that is a subfield of and consider a strongly linear operator . Show that extends by strong linearity into a strongly linear operator . If admits a strongly linear right inverse , then show that the same holds for and .

Exercise 7.25. Let .

  1. Let be a starting term for (7.19) and assume that is a solution of (7.20) with . Consider the refinement and let . Prove that .

  2. Prove that any sequence of refinements like in (a) is necessarily finite.

  3. Design an alternative algorithm for solving (7.19).

  4. Given a solution to (7.19), prove that there exists a in the algebraic closure of , such that .

Exercise 7.26. Let be an matrix with coefficients in and consider the equation

(7.42)

for .

  1. Show that the equation can be reduced to an equation of the form (7.42) and vice versa.

  2. If , then show that

    is a solution to (7.42).

  3. Assume that is a block matrix of the form

    where and is invertible with . Consider the change of variables

    which transforms into

    Show that

    admits a unique infinitesimal solution . Also show that the coefficient can be cleared in a similar way.

  4. Show that the equation (7.42) can be put in the form from (c) modulo a constant change of variables with .

  5. Give an algorithm for solving (7.42) when there exist different dominant monomials of eigenvalues of . What about the general case?

  6. Check the analogue of exercise 7.25(d) in the present setting.

Exercise 7.27. Take and let be as in exercise 7.6, but with coefficients in .

  1. Determine the maximal flat subspace of on which is defined.

  2. Show that admits a distinguished right-inverse on . Can be infinite?

  3. Same question for instead of .

7.8Factorization of differential operators

7.8.1Existence of factorizations

One important consequence of corollary 7.37, i.e. the existence a full basis of solutions of dimension of , is the possibility to factor the as a product of linear operators:

Theorem 7.39. Any linear differential operator of order admits a factorization

with .

Proof. We prove the theorem by induction over the order . For we have nothing to prove. If , then there exists a non-trivial solution to the equation , by corollary 7.37. Now the division of by in the ring yields a relation

for some , and implies . The theorem therefore follows by induction over .

Theorem 7.40. Any linear differential operator admits a factorization as a product of a transseries in and operators

with , or

with .

Proof. We prove the theorem by induction over the order of . If then we have nothing to do. If there exists a solution to , then we conclude in a similar way as in theorem 7.39. Otherwise, there exists a solution to the Riccati equation , such that with and . Now division of by in the ring yields

for some differential operator of order . Moreover, is both a multiple of and , when considered as an operator in . But this is only possible if . We conclude by induction.

7.8.2Distinguished factorizations

We have seen in section 7.4 that the total ordering on the transmonomials allows us to isolate a distinguished basis of solutions to the equation . A natural question is whether such special bases of solutions induce special factorizations of and vice versa.

We will call a series monic, if is regular and . Similarly, a differential operator of order is said to be monic if . A tuple of elements is said to be monic if each element is monic. Given a regular series , the series is monic. In what follows we will consider bases of as tuples . We will also represent factorizations of monic differential operators by tuples .

Proposition 7.41. Let be a monic linear differential operator on of order . Then

  1. To any monic basis of , we may associate a factorization

    and we write .

  2. To any factorization

    we may associate a monic basis of by

    We have for all .

  3. For any factorization represented by we have

  4. If is a monic basis of such that for all , then

Proof. Assume that is a monic basis of and let us prove by induction that is a right factor of for all . This is clear for . Assume that

for some . Then

implies that is a right factor of , in a similar way as in the proof of theorem 7.39. Hence (a) follows by induction.

As to (b), the are clearly monic solutions of , and, more generally,

for . The distinguished property of therefore implies that for all . This also guarantees the linear independence of the . Indeed, assume that we have a relation

Then

and, repeating the argument, . This proves (b).

Now consider a factorization and let

Given with , we get

where is the dominant coefficient of

Applying the above argument for , we obtain (c).

Let us finally consider a monic basis of such that for all . Let

Assume that for some and let

Then both and form monic bases for and for all . It follows that for all , whence . Applying the argument for , we obtain (d).

The distinguished basis of is the unique monic basis such that for all and . The corresponding factorization of is called the distinguished factorization.

Exercise 7.28. Assume that admits a factorization

with . Then

  1. Prove that there exists a unique such factorization with .

  2. Prove that this unique factorization is the distinguished factorization.

8Algebraic differential equations

Let be the field of grid-based transseries in over a real closed field and let be a differential polynomial of order . In this chapter, we show how to determine the transseries solutions of the equation

More generally, given an initial segment of transmonomials, so that

we will study the asymptotic algebraic differential equation

(E)

Usually, we have or for some .

In order to solve (E), we will generalize the Newton polygon method from chapter 3 to the differential setting. This program gives rise to several difficulties. First of all, the starting monomials for differential equations cannot be read off directly from the Newton polygon. For instance, the equation admits a starting monomial whereas the Newton polygon would suggest instead. Also, it is no longer true that cancellations are necessarily due to terms of different degrees, as is seen for the equation , which admits as a starting monomial.

In order to overcome this first difficulty, the idea is to find a criterion which tells us when a monomial is a starting monomial for the equation (E). The criterion we will use is the requirement that the differential Newton polynomial associated to admits a non-zero solution in the algebraic closure of . Differential Newton polynomials are defined in section 8.3.1; modulo multiplicative conjugations, it will actually suffice to define them in the case when . In section 8.3.3, we will show how to compute starting monomials and terms. Actually, the starting monomials which correspond to cancellations between terms of different degrees can almost be read off from the Newton polygon. The other ones are computed using Riccati equations.

A second important difficulty with the differential Newton polygon method is that almost multiple solutions are harder to “unravel” using the differentiation technique from section 3.1.3. One obvious reason is that the quasi-linear equation obtained after differentiation is a differential equation with potentially multiple solutions. Another more pathological reason is illustrated by the example

(8.1)

Although the coefficient of in this equation vanishes, the equation admits as a starting term of multiplicity . Indeed, setting , we get

Differentiation yield the quasi-linear equation

but after the refinement and upward shifting, we obtain an equation

which has the same form as (8.1). This makes it hard to unravel almost multiple solutions in a constructive way. Nevertheless, as we will see in section 8.6, the strong finiteness properties of the supports of grid-based transseries will ensure the existence of a brute-force unravelling algorithm.

In section 8.7 we put all techniques of the chapter together in order to state an explicit (although theoretical) algorithm for the resolution of (E). In this algorithm, we will consider the computation of the distinguished solution to a quasi-linear equation as a basic operation. Quasi-linear equations are studied in detail in section 8.5.

In the last section, we prove a few structural results about the solutions of (E). We start by generalizing the notion of distinguished solutions to equations of Newton degree . We next prove that (E) admits at least one solution if is odd. We will also prove a bound for the number of “new exponentials” which may occur in solutions to (E).

8.1Decomposing differential polynomials

8.1.1Serial decomposition

Let be a differential polynomial over of order . In the previous chapter, we have already observed that we may interpret as a series

(8.2)

where the coefficients are differential polynomials in . We call (8.2) the serial decomposition of . As before, the embedding induces definitions for the asymptotic relations , , etc. and dominant monomials and coefficients of differential polynomials. We will denote by the dominant coefficient of .

8.1.2Decomposition by degrees

The most natural decomposition of is given by

(8.3)

Here we use vector notation for tuples

of integers:

We call (8.3) the decomposition of by degrees. The -th homogeneous part of is defined by

so that

(8.4)

We call (8.4) the decomposition of into homogeneous parts. If , then the largest with is called the degree of and the smallest with the differential valuation of .

8.1.3Decomposition by orders

Another useful decomposition of is its decomposition by orders:

(8.5)

In this notation, runs through tuples of integers in of length , and for all permutations of integers. We again use vector notation for such tuples

For the last two definitions, we assume that . We call the weight of . The -th isobaric part of is defined by

so that

(8.6)

We call (8.6) the decomposition of into isobaric parts. If , then the largest with is called the weight of and the smallest with the weighted differential valuation of .

8.1.4Logarithmic decomposition

It is convenient to denote the successive logarithmic derivatives of by

Then each can be rewritten as a polynomial in :

We define the logarithmic decomposition of by

(8.7)

where

Now consider the total lexicographical ordering on , defined by

Assuming that , let be maximal for with . Then

(8.8)

for or .

8.2Operations on differential polynomials

8.2.1Additive conjugation

Given a differential polynomial and a transseries , the additive conjugation of with is the unique differential polynomial , such that

for all . The coefficients of are explicitly given by

(8.9)

Notice that for all , we have

Proposition 8.1. If with and , then

Proof. The relation (8.9) both yields and

so . Furthermore,

for all , whence the second relation.

8.2.2Multiplicative conjugation

The multiplicative conjugation of a differential polynomial with a transseries is the unique differential polynomial , such that

for all . The coefficients of are given by

(8.10)

Proposition 8.2.

  1. If , then for all ,

  2. If , then

  3. If and are exponential, then

Proof. If , then the equation (8.10) implies and , whence (a). Part (b) follows directly from (a), and (c) is proved in a similar way.

8.2.3Upward and downward shifting

The upward and downward shiftings of a differential polynomial are the unique differential polynomials resp. in such that

for all . The non-linear generalizations of the formulas (7.4) and (7.5) for the coefficients of and are

(8.11)
(8.12)

where the are generalized Stirling numbers of the first kind

and the are generalized Stirling numbers of the second kind

Proposition 8.3. We have

Proof. We get from (8.11) and from (8.12).

Proposition 8.4. If is exponential, then

Proof. Since , the equation (8.11) yields

and . This clearly implies the relation.

Exercise 8.1. Let and .

  1. Show that there exists a unique with

    for all .

  2. Give an explicit formula for for all .

  3. Show that is a differential ring homomorphism:

Exercise 8.2. Let and .

  1. Let be the result of the substitution of for each in . Show that is a morphism of differential rings.

  2. Reinterpret additive and multiplicative conjugation using composition like above.

  3. Show that is isomorphic to , where

Exercise 8.3. Let .

  1. If forms a grid-based family, then show that is well-defined for all .

  2. For two operators and like in (a), with , show that is well-defined.

  3. Generalize (b) to operators in several variables and to more general subspaces of the form of .

8.3The differential Newton polygon method

8.3.1Differential Newton polynomials

Recall from the introduction that, in order to generalize the Newton polygon method to the differential setting, it is convenient to first define the differential Newton polynomial associated to a monomial . We will start with the case when and rely on the following key observations:

Lemma 8.5. Let be isobaric, of weight and assume that . Then .

Proof. For all isobaric of weight , let us denote

Then satisfies and . Furthermore, (8.11) yields

Consequently, if for some , then

Since implies , it follows by induction that for any iterated exponential of . From (8.8), we conclude that and .

Theorem 8.6. Let be a differential polynomial with exponential coefficients. Then there exists a polynomial and an integer , such that for all , we have .

Proof. By formula (8.11), we have and

(8.13)

Consequently,

Hence, for some , we have . Now (8.13) applied on instead of yields . Proposition 8.4 therefore gives

We conclude by applying lemma 8.5 with for .

Given an arbitrary differential polynomial , the above theorem implies that there exists a polynomial and an integer , such that for all sufficiently large . We call

the differential Newton polynomial for . More generally, if is an arbitrary monomial, then we call the differential Newton polynomial for associated to . If is exponential and , then we say that is transparent. Notice that a transseries is transparent if and only if it is exponential.

8.3.2Properties of differential Newton polynomials

Proposition 8.7.

  1. for all .

  2. If and , then .

  3. If , then .

Proof. Assertion (a) is trivial, by construction.

In (b), modulo a sufficient number of upward shiftings, we may assume without loss of generality that , and are transparent. Dividing by , we may also assume that . Then (8.9) implies

so that .

As to (c), it clearly suffices to consider the case when and . After a finite number of upward shiftings, we may also assume that and are transparent and . Let . Then for all we have , whence

by proposition 8.2(a). This implies , as desired.

Proposition 8.8. Let , and . Then we have for all .

Proof. Since , we first notice that

Hence, modulo division by and a sufficient number of upward shiftings, we may assume without loss of generality that , that and are exponential, that , and . Then

and , whence . We conclude that .

8.3.3Starting terms

We call a starting monomial, if admits a non-zero root in the algebraic closure of . This is the case if and only if . We say that is algebraic if is non-homogeneous, and differential if . A starting monomial, which is both algebraic and differential, is said to be mixed.

Example 8.9. Let be a starting monomials for , where and . Then for all sufficiently large . By proposition 7.6, it follows that for all sufficiently large , whence . Similarly, if is not a starting monomial, then for all sufficiently large , and .

Assuming that we have determined a starting monomial for (E), let be a non-zero root of . If , then we call a starting term for (E). If with and , then is said to be an algebraic starting term. If , then we say that is a differential starting term. The multiplicity of (and of ) is the differential valuation of . Notice that the definition of the multiplicity extends to the case when .

Proposition 8.10. Assume that is a non-zero transseries solution to (E). Then is a starting term.

Proof. Assume that is not a starting term. Modulo normalization, we may assume without loss of generality that is transparent and . Then

since .

The Newton degree of (E) is defined to be the maximum of and the largest possible degree of for monomials . The above proposition shows that equations of Newton degree zero do not admit solutions.

Proposition 8.11. If , then

Proof. Consider a monomial with . Modulo a multiplicative conjugation with we may assume without loss of generality that , so that with and . Modulo upward shifting, we may also assume that , and are transparent. Then , by proposition 8.7(b).

Geometrically speaking, we may consider the Newton degree as “the multiplicity of zero as a root of modulo ”. More generally, given an initial segment , we say that is a solution to (E) modulo , if the Newton degree of

(8.14)

is strictly positive. The multiplicity of such a solution is defined to be the Newton degree of (8.14). If , then the multiplicities of and as solutions of (E) modulo coincide, by proposition 8.11. In particular, if is a solution of (E) modulo , then so is . We call a normalized solution, because it is the unique solution in such that for all .

8.3.4Refinements

Given a starting term for (E), we will generalize the technique of refinements in order to compute the remaining terms. In its most general form, a refinement for (E) is a change of variables together with an asymptotic constraint

(R)

where and is an initial segment of transmonomials. Such a refinement transforms (E) into

(RE)

Usually, we take , in which case (RE) becomes

(8.15)

In particular, we may take , but, as in section 3.3.2, it is useful to allow for more general in presence of almost multiple solutions.

Consider a refinement (R) and a second refinement

(RR)

with and . Then we may compose (R) and (RR) so as to yield another refinement

(8.16)

Refinements of the form (8.16) are said to be finer as (R).

Proposition 8.12. Consider a refinement (R) with . Then the Newton degree of (RE) is bounded by the Newton degree of (E).

Proof. By the definition of Newton degree, the result is clear if . In general, we may decompose the refinement in a refinement with and a refinement with . We conclude by proposition 8.11.

Proposition 8.13. Let and . Then the Newton degree of

is equal to the multiplicity of as a root of .

Proof. Let us first show that for any monomial . Modulo multiplicative conjugation and upward shifting, we may assume without loss of generality that and that , , and are transparent. The differential valuation of being , we have in particular . Hence,

for all . We infer that .

At a second stage, we have to show that . Without loss of generality, we may again assume that , and that and are transparent. The differential valuation of being , we have for all . Taking , we thus get

for all . We conclude that .

Exercise 8.4. If , then show that

  1. .

  2. .

Exercise 8.5. If , with and , then show that is the unique algebraic starting term for .

Exercise 8.6.

  1. Give a definition for the composition

    of an infinite sequence of refinements

  2. What can be said about the Newton degree of (RE)?

Exercise 8.7. Let and let be an initial segment.

  1. Show that .

  2. What can be said about ?

  3. If and , then show that

    Hint: first reduce to the case when . Next, considering as algebraic equations in , show that there exists a common solution with for all (i.e. we do not require that for ).

Exercise 8.8. Improve the bound in theorem 8.6 for of degree .

Exercise 8.9. Show that upward shiftings may indeed be needed in theorem 8.6.

Exercise 8.10. Let and let be such that

  1. Show that

    with .

  2. Let be the subset of of homogeneous and isobaric polynomials of degree and weight . For , show that

    and .

  3. If is such that , then show that

  4. Show that if and only if .

8.4Finding the starting monomials

8.4.1Algebraic starting monomials

The algebraic starting monomials correspond to the slopes of the Newton polygon in the non-differential setting. However, they can not be determined directly from the dominant monomials of the , because of the introductory example and because there may be some cancellation of terms in the different homogeneous parts during multiplicative conjugations. Instead, the algebraic starting monomials are determined by successive approximation:

Proposition 8.14. Let be such that and .

  1. If is exponential, then there exists a unique exponential monomial , such that .

  2. Denoting by the monomial in (a), there exists an integer , such that for all we have .

  3. There exists a unique monomial , such that is non-homogeneous.

Proof. In (a), let be a plane transbasis for the coefficients of . We prove the existence of by induction over the least , such that for some . If , then we have . Otherwise, let with . Then

so that for some and . By the induction hypothesis, there exists a exponential monomial , such that . Hence we may take . As to the uniqueness of , assume that with . Then

This proves (a).

The above argument also shows that for some , since

Now, with the notations from theorem 8.6, we have shown that and that equality occurs if and only if . Because of (8.10), we also notice that for all . It follows that

and similarly for instead of . We finally observe that and imply that , since

whenever and . Consequently, and stabilize for with . For this , we have (b).

With the notations from (b), is actually the unique monomial such that

is non-homogeneous for all sufficiently large . Now for sufficiently large . This proves (c) for exponential differential polynomials , and also for general differential polynomials, after sufficiently many upward shiftings.

The unique monomial from part (c) of the above proposition is called the -equalizer for . An algebraic starting monomial is necessarily an equalizer. Consequently, there are only a finite number of algebraic starting monomials and they can be found as described in the proof of proposition 8.14.

Remark 8.15. From the proof of proposition 8.14, it follows that if can be expanded w.r.t. a plane transbasis , then all equalizers for belong to .

8.4.2Differential starting monomials

In order to find the differential starting monomials, it suffices to consider the homogeneous parts of , since , if and . Now, using (7.6), we may rewrite

where is a differential polynomial of order in . We call the differential Riccati polynomial associated to .

For a linear differential operator with exponential coefficients, we have seen in the previous chapter that finding the starting terms for the equation is equivalent to solving modulo . Let us now show that finding the starting monomials for the equation is equivalent to solving modulo . In the exponential case, this is equivalent to solving the equation modulo .

Proposition 8.16. The monomial is a starting monomial of w.r.t.

(8.17)

if and only if the equation

(8.18)

has strictly positive Newton degree.

Proof. We first notice that for all and . We claim that the equivalence of the proposition holds for and if and only if it holds for and . Indeed, is starting monomial w.r.t. (8.17), if and only if is a starting monomial w.r.t.

(8.19)

and (8.18) has strictly positive Newton degree if and only if

(8.20)

has strictly positive Newton degree. Now the latter is the case if and only if

has strictly positive Newton degree. But

This proves our claim.

Now assume that is a starting monomial w.r.t. (8.17). In view of our claim, we may assume without loss of generality that and are transparent. Since is homogeneous, we have for some and , and

Since is exponential, it follows that has degree , so that the Newton degree of (8.18) is at least . Similarly, if is not a starting monomial w.r.t. (8.17), then and

for some . Consequently, for any infinitesimal monomial , and the Newton degree of (8.18) vanishes.

8.4.3On the shape of the differential Newton polygon

Proposition 8.17. Let be the Newton degree of (E). Then the algebraic starting monomials are equalizers of the form

where .

Proof. Let us prove the proposition by induction over . If , then there is nothing to prove, so assume that . Let be such that is maximal for . Modulo a multiplicative conjugation with and upward shifting, we may assume without loss of generality that and that is transparent.

We claim that is a starting monomial for (E). Indeed, let be such that . By proposition 8.7(c), we already have , since otherwise

Now assume for contradiction that is not a starting monomial for (E), so that , and let be such that . We must have , since proposition 8.7(c) implies

Now consider the equalizer . After sufficiently many upward shiftings, we may assume without loss of generality that and are transparent. But then

which contradicts the fact that .

Having proved our claim, let and . Since is exponential, we have , whence

In other words, . It follows that the equation

has Newton degree . We conclude by applying the induction hypothesis to this equation.

Proposition 8.18. Assume that is a non-algebraic starting monomial for (E). Then, with the notations from proposition 8.17, there exists a unique such that

Moreover, and .

Proof. By proposition 8.7(c),

fulfills the requirements.

Exercise 8.11. Compute the starting terms for

Exercise 8.12. Let be a differential polynomial with exponential coefficients and assume that with is a starting monomial for . Then prove that . Hint: if is homogeneous, then show that

Exercise 8.13. Let be a differential field and , . If , then show that there exists a homogeneous of degree , such that .

Exercise 8.14. Prove that there are exactly algebraic starting terms in for an equation (E) of Newton degree .

Exercise 8.15. Let denote the space of homogeneous of degree . Given , let be the result of substituting in the logarithmic decomposition of .

  1. Show that , when rewriting .

  2. Show that is an isomorphism.

  3. What about higher degrees?

8.5Quasi-linear equations

8.5.1Distinguished solutions

The equation (E) is said to be quasi-linear if its Newton degree is one. A solution to a quasi-linear equation is said to be distinguished if we have for all other solutions to (E). Distinguished solutions are unique: if and are distinct distinguished solutions, then we would have , whence , which is absurd.

Lemma 8.19. Assume that the equation (E) is quasi-linear and that the coefficients of can be expanded w.r.t. a plane transbasis . Assume also that , , and let

Then, considering and as operators on , the equation (E) admits a distinguished solution given by

(8.21)

Proof. Since is stable under and for each , the operator is strictly extensive on and is grid-based. By theorem 6.15, the operator therefore admits an inverse

This shows that is well-defined. In order to show that is the distinguished solution, assume that is another solution and let . If , then we clearly have , since . If , then let

Since , we have , so that is the dominant monomial of a solution to the equation . Hence , since .

Lemma 8.20. Consider a quasi-linear equation (E) whose coefficients can be expanded w.r.t. a plane transbasis . Assume that and . Then (E) admits a distinguished solution

Proof. Modulo division of the equation by , we may assume without loss of generality that . We prove the result by induction over . If , then

for some and . Hence is the distinguished solution to . Assume now that . By the induction hypothesis, there exists a distinguished solution to the quasi-linear equation

(8.22)

with . By lemma 8.19, the equation

admits a distinguished solution

with . Then the distinguished properties of and imply that is the distinguished solution to (E).

Theorem 8.21. Assume that the equation (E) is quasi-linear. Then it admits a distinguished transseries solution . Moreover, if the coefficients of can be expanded w.r.t. a plane transbasis , then

Proof. If , then is the trivial distinguished solution of (E). Assume therefore that . Modulo some upward shiftings we may assume without loss of generality that the coefficients of and the transbasis are exponential. Modulo a multiplicative conjugation and using proposition 8.14(a), we may also assume that . Now consider the -equalizer for , which is also the only algebraic starting monomial. If

with , then and

In other words, after one more upward shifting and a multiplicative conjugation with , we may also assume that . We conclude by lemma 8.20.

8.5.2General solutions

Lemma 8.22. Consider a quasi-linear equation (E) with exponential coefficients and a solution which is not exponential. Let be the largest monomial in which is not exponential. Then for some and an exponential monomial .

Proof. Consider the exponential transseries . Then

admits as a solution, so it is quasi-linear and is a starting monomial. Consequently, is also a starting monomial for the equation , where . It follows that for some exponential monomial .

Let us show that , where . Modulo an additive conjugation with , a multiplicative conjugation with , and division of the equation by , we may assume without loss of generality that , and . Since the equation is quasi-linear, we have

It follows that

whence

In other words, is a starting monomial for the equation

We conclude that and .

Theorem 8.23. Let be a solution to a quasi-linear equation (E). If the depths of the coefficients of are bounded by , then the depth of is bounded by .

Proof. For each , such that the depth of is , let be the minimal element in the support of of depth . By the previous lemma, we have , whence . Therefore, , where denotes the set of exponential transmonomials. The result now follows from the fact that .

Corollary 8.24. If the coefficients of can be expanded w.r.t. a plane transbasis , then the distinguished solution to (E) belongs to .

Theorem 8.25. Let be a solution to a quasi-linear equation (E). Then may be written in a unique way as

where is the distinguished solution to (E), , and

are such that each is the distinguished solution to the equation

Proof. Consider the sequence with for all , where

and is the distinguished solution to

Since the equation

is quasi-linear (it admits as a solution), is also the distinguished solution to this latter equation, whence . By induction, it follows that .

Let us now prove that the sequence has length at most . Assume the contrary and consider

Then

for all , so are starting monomials for

Since this equation is quasi-linear and , it follows that are also starting monomials for the linear differential equation

In other words, . But then

Exercise 8.16. If is the distinguished solution to a quasi-linear equation (E) and a truncation of , then show that is the distinguished solution to

Exercise 8.17. Assume that (E) is quasi-linear, with distinguished solution . Show that the equation is also quasi-linear, with distinguished solution . And if is replaced by a transseries?

Exercise 8.18. Show that in theorem 8.21.

Exercise 8.19. Show that the dependence of on is polynomial in theorem 8.23.

Exercise 8.20. Give an example of a quasi-linear equation (E) such that the set

is infinite.

Exercise 8.21. Can you give an example for which

in corollary 8.24?

8.6Unravelling almost multiple solutions

As pointed out in the introduction, “unravelling” almost multiple solutions is a more difficult task than in the algebraic setting. As our ultimate goal, a total unravelling is a refinement

(8.23)

such that and . Unfortunately, total unravellings can not be read off immediately from the equation or its derivatives. Nevertheless, we will show how to “approximate” total unravellings by so called partial unravellings which are constructed by repeatedly solving suitable quasi-linear equations.

8.6.1Partial unravellings

In order to effectively construct a total unravelling, consider a starting monomial such that admits a root of multiplicity . Assume that is sufficiently large so that is exponential and

for some and . Let

(8.24)

and consider a refinement (R) such that

AU1
The Newton degree of ( RE ) equals .

AU2
and .

AU3
We have for or some starting monomial for

Then we call (R) an atomic unravelling.

Proposition 8.26. Let be a set of atomic unravellings for (E). Then admits a finest element.

Proof. Assume for contradiction that there exists an infinite sequence

of finer and finer atomic unravellings in , so that

for all . Setting

it follows for all that

Consequently, is a starting monomial for and . But this is impossible, since .

Given an atomic unravelling (R) followed by a second refinement (RR) such that the Newton degree of

equals , we say that (RR) is compatible with (R) if , and is not a starting monomial for

(8.25)

If the second refinement (RR) is not compatible with (R), then we may construct a finer atomic unravelling

such that . Indeed, it suffices to take , where is the distinguished solution to the equation

In other words, during the construction of solutions of (E) we “follow” the solutions to as long as possible whenever the Newton degree remains .

A partial unravelling is the composition of a finite number of compatible atomic unravellings. We call the length of the partial unravelling. By convention, the identity refinement

is a partial unravelling of length . We have shown the following:

Proposition 8.27. Assume that (E) has Newton degree . Given a partial unravelling (R) and a starting term for (RE) of multiplicity , there exists a finer partial unravelling

with .

8.6.2Logarithmic slow-down of the unravelling process

The introductory example (8.1) shows that an atomic unravelling does not necessarily yield a total unravelling. Nevertheless, when applying a succession of compatible atomic unravellings, the following proposition shows that the corresponding monomials change by factors which decrease logarithmically.

Theorem 8.28. Consider an atomic unravelling (R), followed by a compatible refinement (RR). Then, denoting , there exists an with

Proof. Modulo some upward or downward shiftings, we may assume without loss of generality that in (8.24), so that is exponential. Modulo a multiplicative conjugation with and division of by , we may also assume that and that . By proposition 8.1 it follows that .

Let us first show that . Assuming the contrary, we have either or , where . In the first case, is a starting monomial for

and . Since is exponential, it follows that , as well as , by proposition 8.8. So is also a starting monomial for the equation . But this is impossible, since . In the second case, is a starting monomial for

Again is exponential and , so we obtain a contradiction in a similar way as above.

Since is not a starting monomial for (8.25), we have

for a sufficiently large such that , and are exponential and . Using proposition 8.3 and the fact that , it follows that

On the other hand,

whence

We conclude that

since is the coefficient of in for some .

Now let be a monomial with , so that and . Then, proposition 8.2 implies

From propositions 8.3 and 8.8, it therefore follows that the degree of cannot exceed . We conclude that there exists an with

since (8.26) has Newton degree .

8.6.3On the stagnation of the depth

This section deals with two important consequences of proposition 8.28. Roughly speaking, after one atomic unravelling, the terms of degree do no longer play a role in the unravelling process. If is exponential, and modulo the hypothesis that only admits exponential starting monomials, it will follow that the process only involves monomials in , where denotes the set of exponential transmonomials.

Lemma 8.29. Consider an equation (E) of Newton degree and assume that and . Then any non-differential starting term of multiplicity is in .

Proof. Let be a non-differential starting term of multiplicity , so that for some . Then is the -equalizer for all . In particular, is a starting term for the linear equation . Hence, , by proposition 7.8 and the incomplete transbasis theorem.

Theorem 8.30. Consider an atomic unravelling (R) for an equation (E) of Newton degree , followed by a compatible refinement (RR) such that . Assume that and are exponential and that admits only exponential starting monomials. Then .

Proof. If , then we have nothing to prove, so assume that . By U1 and lemma 8.29, it follows that . Modulo a multiplicative conjugation with an element in and the division of by , we may therefore assume without loss of generality that and . Notice that since and is exponential.

By theorem 8.28, our assumption implies

for all . Since is exponential, this relation simplifies to

Now assume that , let be maximal with , and let . Since is a starting term for (E) of multiplicity , we have for all . It follows that , and for all . Now consider

By what precedes, we have . Furthermore, and . By proposition 8.8, is a starting monomial for

Moreover, is a differential starting monomial, by lemma 8.29. Since

proposition 8.8 also implies that is a starting monomial for . Our assumptions thus result in the contradiction that .

8.6.4Bounding the depths of solutions

If we can bound the number of upward shiftings which are necessary for satisfying the conditions of proposition 8.30, then the combination of propositions 8.28 and 8.30 implies that any sequence of compatible atomic unravellings is necessarily finite. Now the problem of finding such a bound is a problem of order , by proposition 8.16. Using induction, we obtain the following theorem:

Theorem 8.31. Consider an equation (E) of Newton degree and weight , with exponential coefficients. If is a normalized solution to (E) modulo an initial segment , then has depth , where and if .

Proof. We prove the theorem by a double recursion over and . If , then the theorem follows from corollary 3.9. In the case when we also have nothing to prove, since there are no solutions. So assume that , and that we have proved the theorem for all strictly smaller or for the same and all strictly smaller . We may also assume that , since the theorem is clearly satisfied when .

Let be the dominant monomial of . If is algebraic, then proposition 8.14 implies that its depth is bounded by . If is differential, then and is a root of modulo for some . Hence, its depth is bounded by , because of the induction hypothesis. Modulo upward shiftings and a multiplicative conjugation with , we may thus reduce the general case to the case when and . It remains to be shown that has depth .

If is a root of multiplicity of , then the Newton degree of

is by proposition 8.13 and is a root of this equation modulo . The induction hypothesis now implies that has depth .

Assume now that is a root of multiplicity of . Consider a finest atomic unraveling (R) for which . Then and are exponential, by theorem 8.23. Let be the longest truncation of , such that the Newton degree of

is equal to . By the induction hypothesis, only admits exponential solutions. Now theorem 8.30 implies that has depth . If , then we are done. Otherwise, is a starting term of multiplicity for , by the definition of . By what precedes, we conclude that has depth .

Corollary 8.32. Consider an equation (E) of Newton degree and a non-empty set of partial unravellings for (E). Then admits a finest element.

Proof. Let us first assume for contradiction that there exists an infinite sequence of compatible atomic unravellings

Modulo a finite number of upward shiftings, it follows from theorem 8.31 that we may assume without loss of generality that the coefficients of are exponential and that only admits exponential solutions. Then theorem 8.30 implies that for all . From theorem 8.28 it also follows that for all . But this is impossible.

Now pick a partial unravelling (R) in of maximal length. Then any finer partial unravelling in is obtained by replacing the last atomic unravelling which composes (R) by a finer one. The result now follows from proposition 8.26.

Exercise 8.22. In theorem 8.30, show that whenever is a starting monomial for of the form with and , then .

Exercise 8.23. Improve the bound in theorem 8.31 in the case when .

Exercise 8.24. Show how to obtain a total unravelling (8.23) a posteriori, by computing w.r.t. the monomial instead of .

8.7Algorithmic resolution

In this section, we will give explicit, but theoretical algorithms for solving (E). In order to deal with integration constants, we will allow for computations with infinite sets of transseries. In practice, one rather needs to compute with finite sets of “parameterized transseries”. However, the development of such a theory (see [vdH97, vdH01a]) falls outside the scope of the present book.

8.7.1Computing starting terms

Theorem 8.6 implies that we may compute the Newton polynomial of a differential polynomial using the algorithm below. Recall that a monomial is a starting monomial if and only if .

Algorithm

Input: .

Output: The differential Newton polynomial of .

  1. If is not exponential or , then return .

  2. Return .

The algebraic starting monomials can be found by computing all equalizers and keeping only those which are starting monomials. The equalizers are computed using the method from the proof of proposition 8.14.

Algorithm

Input: and integers with and .

Output: The -equalizer for .

  1. If is not exponential or , then return .

  2. If then return .

  3. Let and return .

Algorithm alg_st_mon

Input: and an initial segment .

Output: The set of algebraic starting monomials for (E).

  1. Compute .

  2. Return .

In fact, using proposition 8.17, it is possible to optimize the algorithm so that only a linear number of equalizers needs to be computed. This proposition also provides us with an efficient way to compute the Newton degree.

Algorithm Newton_degree

Input: and an initial segment .

Output: The Newton degree of (E).

  1. Compute .

  2. Return .

The algorithm for finding the differential starting terms is based on proposition 8.16 and a recursive application of the algorithm ade_solve (which will be specified below) in order to solve the Riccati equations modulo .

Algorithm diff_st_mon

Input: and an initial segment .

Output: The set of differential starting monomials for (E).

  1. If is homogeneous, then

    Let

    Return .

  2. Let for each with .

  3. Return .

Having computed the sets of algebraic and differential starting monomials, it suffices to compute the roots of the corresponding Newton polynomials in order to find the starting terms.

Algorithm st_term

Input: and an initial segment .

Output: The set of starting terms for (E).

  1. Let .

  2. Return .

8.7.2Solving the differential equation

Let us now show how to find all solutions to (E) and, more generally, all normalized solutions of (E) modulo an initial segment . First of all, is a solution if and only if the Newton degree of is . In order to find the other solutions, we first compute all starting terms in . For each such , we next apply the subalgorithm ade_solve_sub in order to find the set of solutions which starting term .

Algorithm ade_solve

Input: and initial segments .

Output: The set of normalized solutions to (E) modulo .

  1. Compute .

  2. Let .

  3. If Newton_degree then .

  4. Return .

Let be the Newton degree of (E). In order to find the normalized solutions with starting terms of multiplicity , we may simply use the refinement

and recursively solve

The other starting terms require the unravelling theory from section 8.6: we start by computing the quasi-linear differentiated equation

(8.26)

with as in (8.24) and we will “follow” solutions to this equation as long as possible using the subalgorithm unravel.

Algorithm ade_solve_sub

Input: , initial segments and a starting term for (E).

Output: The set of normalized solutions to (E) modulo with dominant term .

  1. Let and .

  2. If , then return .

  3. Compute using (8.24), with minimal , and let , where is the distinguished solution to

    (8.27)
  4. Return .

The algorithm unravel is analogous to ade_solve, except that we now compute the solutions with a given starting term using the subalgorithm unravel_sub instead of ade_solve_sub.

Algorithm unravel

Input: and initial segments .

Output: The set of normalized solutions to (E) modulo with dominant term .

  1. Compute .

  2. Let .

  3. If Newton_degree, then .

  4. Return .

In unravel_sub, we follow the solutions to (8.26) as far as possible. More precisely, let be as in (8.24). Then the successive values of for calls to unravel and unravel_sub are of the form , where satisfy for each . At the end, the refinement

(8.28)

is an atomic unravelling for the original equation. Moreover, at the recursive call of ade_solve_sub, the next refinement will be compatible with (8.28).

Algorithm unravel_sub

Input: , initial segments and a starting term for (E).

Output: The set of normalized solutions to (E) modulo with dominant term .

  1. If , then return ade_solve_sub.

  2. Let , where is the distinguished solution to (8.27).

  3. Return .

The termination of our algorithms are verified by considering the three possible loops. In successive calls of solve and solve_sub we are clearly done, since the Newton degree strictly decreases. As to successive calls of unravel and unravel_sub, we have in (8.28), by theorem 8.25. Finally, any global loop via solve_sub and unravel, during which the Newton degree remains constant, corresponds to a sequence of compatible atomic unravellings. But such sequences are necessarily finite, by theorems 8.25, 8.30 and 8.31.

Exercise 8.25. Assume that and that we search for zeros of (E) in the set of well-based transseries of finite exponential and logarithmic depths .

  1. Given , show there exists an with . Give a definition for the differential Newton polynomial of . Generalize proposition 8.10.

  2. Given with and , prove that there is at most one well-based transmonomial such that is non-homogeneous.

  3. Show that proposition 8.16 still holds for well-based transmonomials.

  4. Show that the set of solutions to (E) in as computed by ade_solve coincides with the set of solutions to (E) in .

  5. Show that ,

    and

    do not satisfy an algebraic differential equation with coefficients in .

  6. Does satisfy an algebraic differential equation with coefficients in ? And does satisfy an algebraic differential equation with coefficients in ?

8.8Structure theorems

8.8.1Distinguished unravellers

Theorem 8.33. Let (E) be an equation of Newton degree . Then there exists a unique which is longest for with the properties that

  1. , for .

  2. For any , the term is an algebraic starting term for

    (8.29)

Proof. Consider the set of all partial unravellings

(8.30)

such that satisfies (a) and (b). Since contains the identity refinement, we may choose (8.30) to be finest in , by corollary 8.32. We claim that is maximal for , such that (a) and (b) are satisfied.

Indeed, assume for contradiction that some also satisfies (a) and (b). Then is the unique algebraic starting term for (8.29) and it has multiplicity . By proposition 8.27, there exists a partial unravelling

which is finer than (8.30), and such that . By what precedes, satisfies (a). Moreover, satisfies (b), since does. This contradicts the maximality of (8.30).

Let us now prove the uniqueness of . Assume for contradiction that with and also satisfies (a) and (b). Let and . Then

admits both and as algebraic starting terms of multiplicity . But this is impossible.

The transseries from the theorem is called the distinguished unraveller for (E). It has the property that for any algebraic starting term for

(8.31)

the refinement

is a total unravelling.

Remark 8.34. It is easily checked that theorem 8.33 also holds for , and that coincides with the distinguished solution of (E) in this case.

Recall that stands for the group of logarithmic monomials.

Proposition 8.35. Let be as in theorem 8.33 and assume that for a plane transbasis . Then .

Proof. Assume the contrary, let be maximal, such that , and let . Modulo a finite number of upward shiftings, we may assume without loss of generality that and are exponential. But then is an algebraic starting monomial for

By remark 8.15, we conclude that .

8.8.2Distinguished solutions and their existence

A solution to (E) is said to be distinguished, if for all , the term is an algebraic starting term for the equation

If is odd, then there exists at least one distinguished solution.

Theorem 8.36. Any equation (E) of odd Newton degree admits at least one distinguished solution in . Moreover, if the coefficients of can be expanded w.r.t. a plane transbasis , then any such solution is in .

Proof. We prove the theorem by induction over . For , the result follows from corollary 8.24. So let and assume that the theorem holds for all smaller .

Now proposition 8.17 implies that there exists at least one starting monomial and equalizer such that is odd. It follows that for some of odd degree. Since is real closed, it follows that admits a root of odd multiplicity .

If , then proposition 8.13 and the induction hypothesis imply that

(8.32)

admits a distinguished solution , whence

is a distinguished solution to (E). Inversely, if is a distinguished solution to (E) whose dominant term has multiplicity , then is necessarily an equalizer, and

a distinguished solution to (8.32), whence .

If , then let be the distinguished unraveller for (E), so that the equation

(8.33)

does not admit an algebraic starting term of multiplicity . Modulo some upward shiftings and by what precedes, it follows that (8.33) admits a distinguished solution . We conclude that

is a distinguished solution to (E). Inversely, we have for any distinguished solution of (E), and is a distinguished solution to (8.33), whence .

8.8.3On the intrusion of new exponentials

In this chapter, we have shown how to solve (E) directly as an equation in . A more advanced method for solving (E) is to use integral refinements

in addition to usual refinements. This gives a better control over the number of exponentials and integration constants introduced in the resolution process, because is often “strongly transcendental” over the field generated by the coefficients of , so that the equation rewritten in has lower order. A full exposition of these techniques is outside the scope of this book, but the proof of the following theorem will illustrate some of the involved ideas to the reader.

Theorem 8.37. Consider of order for some plane transbasis . Then for each exponential solution to (E), there exists a transbasis for with .

Proof. Let us construct sequences , and such that

  1. is totally ordered for .

  2. for each (where we understand that ).

We take . Given , let be the longest truncation of , such that . If , then the sequence is complete. Otherwise, we let

If is an arbitrary transbasis for , then

so that the construction finishes for . Setting , we also observe that for all . It follows that is a transbasis for .

Let us now consider another sequence with

so that

Denoting for all , we notice that is isomorphic to . Now for all , we have

By strong linearity, it follows that for all and , we have . Moreover, if

then the above formula also yields

In particular,

for all .

Now assume for contradiction that and let with . Then substitution of for in for all and for yields a non-zero polynomial , which admits as a root. But this contradicts the fact that is real closed. We conclude that , whence is a transbasis for with .

Corollary 8.38. Consider of order for some transbasis . Then for each solution to (E), there exists a transbasis for with .

Exercise 8.26. Give an alternative algorithm for the resolution of (E), where, after the computation of a starting term , we perform the refinement

where is the distinguished unraveller for .

Exercise 8.27. If, in the algorithms of section 8.7, we let st_term only return the algebraic starting terms, then show that the algorithm ade_solve will return the set of all distinguished solutions.

Exercise 8.28. Show that there exist at most distinguished solutions to (E).

Exercise 8.29. If is a distinguished solution to (E) and , then show that is a distinguished solution to .

Exercise 8.30. Improve theorem 8.31 and show that we can take . Hint: use exercise 8.22 in combination with the proof technique from theorem 8.37.

9The intermediate value theorem

The main aim of this chapter is to prove the intermediate value theorem: given a differential polynomial over the transseries and with , there exists an with and . In particular, any differential polynomial of odd degree admits a zero in .

The intermediate value theorem is interesting from several points of view. First of all, it gives a simple sufficient condition for the existence of zeros of differential polynomials. This is complementary to the theory from the previous section, in which we gave a theoretical algorithm to compute all solutions, but no simple criterion for the existence of a solution (except for theorem 8.33).

Secondly, the intermediate value theorem has a strong geometric appeal. When considering differential polynomials as functions on , a natural question is to determine their geometric behaviour and in particular to localize their zeros. Another question would be to find the extremal and inflexion points. It is already known that extremal values are not necessarily attained. For instance, the differential polynomial

admits its minimal “value”

“in”

In the future, we plan to classify all such non-standard “cuts” which occur as local extrema of differential polynomials. In particular, we expect that a cut occurs as a local minimum if and only of it occurs as a local maximum for another differential polynomial.

Finally, the intermediate value theorem is a starting point for the further development of the model theory for ordered differential algebra. Indeed, the field of transseries is a good candidate for an existentially closed model of this theory, i.e. a “real differentially algebraically closed field”. Such fields are necessarily closed under the resolution of first order linear differential equations and they satisfy the intermediate value theorem. It remains to be investigated which additional properties should be satisfied and the geometric aspects of real differential polynomials may serve as a source of inspiration.

In order to prove the intermediate value theorem, the bulk of this chapter is devoted to a detailed geometric study of the “transline” and differentially polynomial functions on it. Since the field of transseries is highly non-archimedean, it contains lots of cuts. Such cuts may have several origins: incompleteness of the constant field (if ), the grid-based serial nature of , and exponentiation. In sections 9.1, 9.2, 9.3 and 9.4 we study these different types of cuts and prove a classification theorem.

Although the classification of cuts gives us a better insight in the geometry of the transline, the representation we use is not very convenient with respect to differentiation. In section 9.5, we therefore introduce another way to represent cuts using integral nested sequences of the form

This representation makes it possible to characterize the behaviour of differential polynomials in so called “integral neighbourhoods” of cuts, as we will see in section 9.6. In the last section, we combine the local properties of differential polynomials near cuts with the Newton polygon method from chapter 8, and prove the intermediate value theorem. We essentially use a generalization of the well-known dichotomic method for finding roots.

9.1Compactification of total orderings

9.1.1The interval topology on total orderings

Any totally ordered set has a natural topology, called the interval topology, whose open sets are arbitrary unions of open intervals. We recall that an interval is a subset of , such that for each with , we have . An interval is said to be open, if for each we have: is minimal resp. maximal in , if and only if is minimal resp. maximal in .

A set is open if every point in is contained in an open interval . Arbitrary unions of open sets are clearly open. The intersection of two open intervals and is again open: if is minimal or maximal in , then it is in particular minimal resp. maximal in or , whence is minimal resp. maximal in . It follows that the intersection of two open sets is also open, so the open sets of form a topology.

We observe that an increasing union of open intervals is again an open interval. Hence, given an open set and , there exists a maximal open interval with . It follows that each open set admits a unique decomposition

(9.1)

as the disjoint union of its maximal open subintervals.

Proposition 9.1. A totally ordered set with the interval topology is Hausdorff if and only if for each there exists a , with .

Proof. Assume that is Hausdorff and let . There exist open subsets and with . Without loss of generality, we may assume that we have replaced and by subintervals which contain resp. . Since is not maximal in and is open, there exists an with . We must also have : otherwise whence , since is an interval.

Conversely, assume that for all there exists a , with . Then given , and assuming by symmetry that , there exists a , with . Then and are disjoint intervals with and . Moreover, for any there exists a with , and is minimal in if and only if it is minimal in . Hence is open, and similarly for .

Example 9.2. Any totally ordered field is Hausdorff.

9.1.2Dedekind cuts

Given a totally ordered set , let denote the set of its open initial segments without maximal elements, ordered by inclusion. We have a natural increasing mapping

Elements in are called cuts. If is Hausdorff, then we have already seen that is open for all , so yields a natural inclusion of into .

The elements and are minimal and maximal in . If admits no maximal element, then . More generally, any non-empty subset of admits an infimum and a supremum:

Proposition 9.3. Any non-empty subset of admits a supremum and an infimum in .

Proof. Let be a subset of and consider the open initial segment without a maximal element

We claim that . By construction, for all . Conversely, if satisfies , then we may pick . Now let be such that . Then , whence . In a similar way, it can be shown that the interior of equals the infimum of .

Proposition 9.4. Let be an interval of a Hausdorff total ordering . Then there exists unique such that has one and only one of the following forms:

  1. .

  2. and .

  3. and .

  4. and .

Proof. Let and . Then clearly

and . Consequently,

Depending on whether and are in or not, we are therefore in one of the four cases (a), (b), (c) or (d).

9.1.3The compactness theorem

Theorem 9.5. Let be a Hausdorff totally ordered set. Then

  1. is Hausdorff.

  2. .

  3. is connected.

  4. is compact.

Proof. In order to show that is Hausdorff, let be in . Choose . Since has no maximal element, there exist with . It follows that , which proves (a).

From (a) it follows that the natural mapping is injective. In order to see that is also surjective, consider an open initial segment without a maximal element, and consider . We claim that . Indeed, if , so that , then there exists a with , by the definition of . Hence , since is an initial segment. Conversely, if , then there exists a with , since has no maximal element. We have , so . This proves our claim and (b).

Let us now show that is connected. Assume the contrary. Then is the disjoint union of two open sets. By (9.1), it follows that

where is a set of at least two open intervals. Let be non-maximal. Then we also have a decomposition of as the disjoint union of two non-empty open intervals

Now consider . We have either or . In the first case, would be a maximal element of . In the second case, would be a minimal element of . This gives us the desired contradiction which proves (c).

Let us finally show that is compact. In view of (9.1), it suffices to show that from any covering of with open intervals we can extract a finite subcovering. Consider the sequence which is inductively defined by and

for all . If is such that then we notice that either or , since is an open interval.

We claim that for all sufficiently large . Assuming the contrary, consider . There exists an with . Since is open, there exists an in . Now take with . Then and are both in , which contradicts the fact that or . This proves the claim.

Denoting by the minimal number with , let us now show how to choose with (), and (). This is clear for . Having constructed , pick an element . Then there exists an with and for some . Since is an interval, it follows that , whence . This completes our construction.

We contend that . Indeed, given , we either have , or there exists there exists a unique with . In the second case, let . Then we have either and , or and .

Exercise 9.1. Let be a totally ordered set. Given , show that contains infinitely many elements.

Exercise 9.2.

  1. Determine for all ordinals .

  2. Determine for all ordinals .

9.2Compactification of totally ordered fields

Let be a totally ordered field. A natural question is to see whether the algebraic structure on can be extended to its compactification and which algebraic properties are preserved under this extension. In section 9.2.1, we first show that increasing and decreasing mappings naturally extend when compactifying. After that, we will show how this applies to the field operations on . We will denote .

9.2.1Functorial properties of compactification

Proposition 9.6. Let and be Hausdorff total orderings and .

  1. Any increasing mapping extends to an increasing mapping , given by

  2. Any decreasing mapping extends to a decreasing mapping , given by

Moreover, in both cases, the mapping is injective resp. surjective if and only if is. Also, if is surjective, then is its unique extension to a monotonic mapping from into .

Proof. Assume that is increasing (the decreasing case is proved similarly). The mapping defined in (a) is clearly increasing. Assume that is injective and let . Choosing with , we have

so is injective.

Assume from now on that is surjective and let . Then is an open initial segment without a maximal element. Indeed, if were maximal, then we may choose with and there would exist a with and necessarily . This shows that . By construction, we have . Given , so that , there exists an with . Consequently, and . This proves that .

Now let be another increasing mapping which extends on . Assume for contradiction that for some (the case is treated similarly) and let . Since is surjective, there exists a with . But if , then and if , then . This contradiction shows that is the unique increasing extension of to a mapping from into .

Corollary 9.7. Let be a Hausdorff ordering and the set ordered by the opposite ordering of . Then there exists a natural bijection

The following proposition is proved in a similar way as proposition 9.6: see exercise 9.3.

Proposition 9.8. Let be a Hausdorff ordering and an interval. Then there exists a natural inclusion

This inclusion is unique with the property that is an interval.

9.2.2Compactification of totally ordered fields

1Opposites and inverses

By proposition 9.6(b), the mapping

extends to unique decreasing bijection , which we also denote by and the inversion

extends to a unique decreasing bijection . Notice that and . For , we may also set , so that is bijective on .

2Addition

The addition on may be extended to an increasing mapping by applying proposition 9.6(a) twice: first to mappings of the form with and next to mappings of the form with . This is equivalent to setting

Notice that the mapping is an isomorphism for each . Subtraction on is defined as usual by . Since the definition of the addition is symmetric in and , the addition is commutative. Clearly, we also have for all , and

for all . However, cannot be an additive group, because . Nevertheless,

for all and . Indeed, given , we have .

3Multiplication

The multiplication extends first to by

and next to by

for all . This definition is coherent if or , since for all . We define division on as usual by . The multiplication is clearly commutative, associative and with neutral element . We also have distributivity whenever . However, .

Exercise 9.3. Prove proposition 9.8.

Exercise 9.4. Show that for all .

9.3Compactification of grid-based algebras

Let be a totally ordered field and a totally ordered monomial group and consider the algebra of grid-based series. In this section we study the different types of cuts which may occur in . We will denote , , . We will also denote .

9.3.1Monomial cuts

Let be a totally ordered field and a totally ordered monomial group. An element is said to be a monomial if and for all . We denote by the union of the set of such monomials and the set of usual monomials. The ordering on naturally extends to , by letting it coincide with the usual ordering .

Given , we define the dominant monomial of as follows. If for no , so that , then we take . If for some , then there exists a with . Moreover, does not depend on the choice of and we set . Thanks to the notion of dominant monomials, we may extend the asymptotic relations , , and to by , , and .

Proposition 9.9. For any , we have

(9.2)
(9.3)

Proof. The first relation is clear from the definition of dominant monomials. As to the second one, we first observe that and for sufficiently large . Hence,

Since we also have for a sufficiently small , it follows that .

9.3.2Width of a cut

Let . We define the width of by

Notice that .

Proposition 9.10. For any , we have

(9.4)
(9.5)

Proof. We have

which proves (9.4). Similarly, we have

Conversely, given with , let be such that , and . Then and , whence

The case is treated in a similar way.

9.3.3Initializers

Let . Given with , there exists a with . Moreover, does not depend on the choice of , and we set . We define the initializer of by

We claim that , where we recall that stands for the set of well-based series in over . Indeed, consider . Then there exists a with and we have . In particular, there exists no infinite sequence in with .

Proposition 9.11. For any , we have

(9.6)
(9.7)

Proof. In order to prove (9.6), let be such that , and let be such that . Then , and .

Similarly, given with , let be such that and . Then we have

and

This proves (9.7).

9.3.4Serial cuts

Let be a cut with . Then for any and , there exists a with and we have . In other words, we always have , where

A cut is said to be serial, if there exists a with

(9.8)

From the proposition below it follows that we may always replace by and obtain the same serial cut. For this reason, we will identify the set of serial cuts with .

Proposition 9.12. Given a serial cut , we have

  1. .

  2. .

Proof. The equation (9.8) implies for . Now, given , let and be such that . Then and , so that . This proves (a).

Given , we have , since otherwise for some , whence . We even have , since would imply and . Consequently, so that .

9.3.5Decomposition of non-serial cuts

Proposition 9.13. For any , we have either

  1. and for some we have

  2. and

Proof. Modulo substitution of for , we may assume without loss of generality that , since .

Suppose that and consider

We must have , since otherwise . We also cannot have , since otherwise . Hence . If , then there exists a with . If , then for some with . If , then , which is again impossible. This proves that . Applying the same argument for , we also obtain , whence .

Assume now that and let us show that . Replacing by in the case when , we may assume without loss of generality that . For we now have

The above proposition allows us to extend the notions of dominant coefficients and terms to . Indeed, given , we have either , in which case we set , or , in which case for some , and we set and . By convention, we also set .

Exercise 9.5. Show that for all we have

Exercise 9.6. Show that is stable under and show that one may extend the flatness relation to .

Exercise 9.7. Given , what can be said about and ?

Exercise 9.8. If , then show that .

Exercise 9.9. Given , compute .

Exercise 9.10. Given , show that

Exercise 9.11. Generalize the theory of section 9.3.4 to other types of supports, like those from exercise 2.1. Show that there exist no serial cuts in the well-based setting.

Exercise 9.12. Characterize the embeddings of into .

Exercise 9.13. Given and , we may define the coefficient of in as follows. If , then . If , then we have already defined if and we set if . If and with , then . Show that we may see as a subset of . Also give a characterization of the elements in .

Exercise 9.14. If , then define a “symmetric addition” on by if , likewise if , if but , and for equal signs. Show that this addition is commutative and that for all . Show also that the symmetric addition is not necessarily associative.

9.4Compactification of the transline

Let us now consider the field of grid-based transseries. Given a transseries cut , the aim of this section is to find an explicit expression for in terms of cuts in , the field operations, seriation and exponentiation. We will denote for all .

9.4.1Exponentiation in

By proposition 9.6(a), the functions and uniquely extend to increasing bijections and , which are necessarily each others inverses.

Proposition 9.14.

  1. For all , we have

  2. For all , we have

  3. For any , we have

Proof. Let . If , then . Assume that . Then it follows from that and similarly . For any with , we have . It follows that . Conversely, for any with , there exists a with , so that . This shows that we also have .

Now consider . We have

This proves (b).

Let . If , then assume for contradiction that there exists a with , and take . Then there exists a with . But then and , which contradicts our assumption. We conclude that . Similarly, if , then let and be such that . Then , so that . This completes the proof of (c).

9.4.2Classification of transseries cuts

Let . The nested sequence for is the possibly finite sequence defined as follows. We take . Given , we distinguish two cases for the construction of :

NS1
If , then the construction has been completed.

NS2
Otherwise, we let , and , so that

(9.9)

We will denote by the number such that is the last term of the nested sequence; if no such term exists, then we let .

For any , repeated application of (9.9) entails

(9.10)

In particular, if , then we call

(9.11)

the nested expansion of . If , then the nested expansion of is defined to be

(9.12)

In this latter case, the nested expansion of each is given by

The following proposition is a direct consequence of our construction:

Proposition 9.15. Each admits a unique nested expansion of one and only one of the following forms:

(9.13)
(9.14)
(9.15)
(9.16)
(9.17)
(9.18)

In order to completely classify the elements in , we still need to determine under which conditions on the , , , and , the expressions (9.15), (9.16), (9.17) and (9.18) are the nested expansion of a cut . This problem will be addressed in the next sections.

9.4.3Finite nested expansions

Proposition 9.16. Assume that admits a finite nested expansion. Then

  1. and .

  2. and

    .

  3. for all .

  4. .

  5. .

Proof. Given , proposition 9.13 implies that either or for some and . In the first case, proposition 9.14(c) implies whence and . In the second case, we obtain with . We cannot have , since otherwise . Therefore, , , and . This proves (a). Similarly, if 1, then either or . In the second case, and yield either , or . This proves (e).

Now let . By what precedes, we necessarily have and . If , then it follows that , since . This proves the first part of (b). Assume that . We cannot have , since otherwise . Similarly, would imply and would imply . If and , then , whence and . We cannot have and , since this would imply . Finally, if , then we have shown above that , so that . This completes the proof of (b) and also proves (d).

In order to prove (c), let and , so that . We conclude that .

Proposition 9.17. Let be as in (9.11), where , and are such that the conditions (ae) of proposition 9.16 are satisfied. Then, admits (9.11) as its nested expansion.

Proof. Let us prove by induction over that

(9.19)

satisfies

  1. .

  2. .

  3. .

  4. .

  5. admits (9.19) as its nested expansion.

These properties are is trivially satisfied for . So assume that they hold for and let us show that they again hold for .

From (A) at order , we get . Since , we have . This proves (A) at order . For , we have either , in which case implies , or , in which case and imply . This proves (B).

As to (C), if and , then . If and , then and imply . If and , then and .

Now let . In order to prove (D), it suffices to show that . Assume first that , so that . If , then and . If or , then and . Hence , by proposition 9.14(c). Assume now that . Then either and , or for some and , or and , since . This proves (D). The last property (E) follows from (D) and (E) at stage .

9.4.4Infinite nested expansions

To any , we may associate a natural interval

where and . Given a sequence with and , we denote

for all and for all . We also denote

for all and . Given , we finally define by

Proposition 9.18. Assume that admits an infinite nested expansion. Then

  1. and .

  2. We have for infinitely many , and for all .

  3. For every , we have .

Proof. Property (a) is proved in a similar way as in proposition 9.16, as well as the fact that for all . Property (c) is obvious, since for all .

Let us prove that for infinitely many . It suffices to prove that for one , modulo repetition of the same argument for instead of . Considering instead of , we may also assume without loss of generality that and . Since , there exist with and . For a sufficiently large , we now have and . But then so that for some . This completes the proof of (b).

Proposition 9.19. Consider and , which satisfy conditions (a–c) of proposition 9.18. Then .

Proof. Let and define , and so on. We claim that for all . Indeed, let be such that but . Then , whence .

Given , we have to prove that . Let us construct a sequence of elements in as follows. Assuming that we have constructed , we deduce from that, so, taking

we indeed have as well as

(9.20)

Now and imply . By induction over , the formula (9.20) therefore yields for all . In other words, for all and in particular for .

Proposition 9.20. Consider and , which satisfy conditions (a–c) of proposition 9.18. Then for some with nested expansion (9.18).

Proof. Since is a decreasing intersection of compact non-empty intervals, contains at least one element. If contains more than one element, then it contains in particular an element . Assume for contradiction that . Then we may choose and such that is minimal.

Let and . From , it follows that and . Since , we also have , by proposition 9.19. Hence and , by the minimality of the counterexample . Now is impossible, since otherwise . It follows that , since , whence . We cannot have , since otherwise , and . Therefore, there exists an with , and . Repeating the same argument, we conclude that , which is impossible.

Now that we have proved that for some , let us show that admits (9.18) as its nested expansion. Indeed, we also have for and proposition 9.19 implies . Consequently, , since . This shows that . Using the same argument, it follows by induction that for all .

Proposition 9.21. Assume that admits an infinite nested expansion. Then for every and , there exists a with .

Proof. Let be the set of monomials , such that for all there exists a with . Let be the union of all , for nested expansions of the form (9.12). If , then we are clearly done, since we would in particular have for each . So let us assume for contradiction that is non-empty and choose and such that is minimal. Let be minimal such that . If or , then let . Otherwise, let . Setting and (whenever ), we distinguish the following four cases:

Case
We first observe that . Now let be minimal such that . Then and for all . This contradicts the fact that .

Case
For all , we have , so the sign of does not depend on the choice of . Since , we may choose such that . But then .

Case
Let be such that for all . Given , it follows that , so the sign on does not depend on the choice of . We obtain a contraction as in the previous case.

Case
The minimality hypothesis entails . By the construction of , we thus must have . Since implies and , it follows that for some and . Since is a singleton, we also must have . Now if , then we would have , which is impossible. If , then for all , which contradicts the fact that .

In all cases, we thus obtain a contradiction, so we conclude that .

Exercise 9.15. Prove that and . In the case when , show that (modulo suitable adjustments of the theory) the “halting condition” NS1 may be replaced by the alternative condition that

Exercise 9.16. Show that the condition (d) is needed in proposition 9.20.

Exercise 9.17. Show that the conclusion of proposition 9.21 may be replaced by the stronger statement that for all , there exists a with . Does this still hold in the case of well-based transseries?

9.5Integral neighbourhoods of cuts

9.5.1Differentiation and integration of cuts

Let be an interval of . Any cut (where is an open initial segment without maximal element) naturally induces an element in . Identifying with , this yields a natural inclusion of into , which extends the inclusion of into . For any with , there exists a with so that . In other words, is a cut in whose width lies in . From proposition 9.13 it now follows that either or for some and . In other words,

In particular, each element admits a canonical decomposition

(9.21)

with , and .

Denote and consider the differential operator on . The restrictions of to and respectively yield increasing and decreasing bijections

By proposition 9.6, we may extend and to the compactifications of and . This allows us to extend to by setting for all . Notice that and . The logarithmic derivative of is defined by .

Similarly, the inverses of and , which coincide with restrictions of the distinguished integration, extend to the compactifications of and . By additivity, the distinguished integration therefore extends to . The distinguished integrals of and are undetermined, since can be chosen among and .

9.5.2Integral nested expansions

Let be a cut. We say that has integral height , if either

The integral height of is defined to be , if none of the above conditions holds for a finite .

We say that is right-oriented (resp. left-oriented) if

An oriented cut is a cut which is either left- or right-oriented. A cut is said to be pathological if for some and , or , where is a pathological cut. If , then there are no pathological cuts. If is neither an oriented nor a pathological cut, then is said to be regular.

For each , we recursively define , and by taking (starting with ), and . The sequence is called the integral nested sequence of and the sequence its integral guiding sequence. For each with , we call

the integral nested expansion of at height . If is an irregular cut of height , so that for certain and , then we also define and . In that case, we call the extended integral height of and the extended integral guiding sequence. If is a regular cut, then the extended integral height and guiding sequence are defined to be same as the usual ones.

9.5.3Integral neighbourhoods

Let be a cut of integral height and with extended integral guiding sequence . Let be transseries in , where and are formal symbols with . Then the set

is called a basic integral neighbourhood of extended height , if either one of the following conditions holds:

The height of is the minimum of and . An integral neighbourhood of is a superset of a finite intersection of basic integral neighbourhoods. The (extended) height of such a neighbourhood is the maximal (extended) height of the components in the intersection.

Let be an integral neighbourhood of of height and consider a transseries close to . We define the integral coordinates of by

If is an integral neighbourhood of , then we notice that is an integral neighbourhood of , and it is convenient to denote the integral coordinates of by .

Example 9.22. Let and consider a basic integral neighbourhood of of height .

If , then , with . In particular, there exists an with and . For any with and , it follows that , whence . For any with , we also have , whence . By distinguishing the cases , and , it follows that for certain with .

If , then , where is an integral neighbourhood of both and . Hence,

so there exists an with

and

It follows that for any with , we have

and

so that . Similarly, if with and , then

whence

and .

9.5.4On the orientation of integral neighbourhoods

Let be a cut. A one-sided neighbourhood of is either a superset of an interval with and (and we say that is a right neighbourhood of ) or a superset of an interval with and (and we say that is a left neighbourhood of ). A neighbourhood of is a set which is both a left neighbourhood of (unless ) and a right neighbourhood of (unless ).

Proposition 9.23. Let be a non-pathological cut and let be an integral neighbourhood of .

  1. If is regular, then there exists a neighbourhood of with .

  2. If is right-oriented, then admits a right neighbourhood with .

  3. If is left-oriented, then admits a left neighbourhood with .

Proof. We prove the proposition by induction over the height of . If , or and is regular, then we may take . If and is oriented, then the result follows from what has been said in example 9.22. Assume therefore that and let be the integral expansion of at height .

We have , where each is a basic integral neighbourhood of of height . Modulo a final adjustment of , we may assume without loss of generality that . We have for all , where each is a basic integral neighbourhood of . Let .

  1. If is regular, then so is , hence the induction hypothesis implies that there exist with and . We conclude that either and or and .

  2. If is right-oriented, then either and is right-oriented, or and is left-oriented. In the first case, the induction hypothesis implies that there exists a with and , so that . In the second case, there exists a with and , so that .

  3. The case when is left-oriented is treated in a similar way as (b).

Proposition 9.24. Let be a cut and an integral neighbourhood of , of height . Then there exists an integral neighbourhood of of height , such that and have constant sign for .

Proof. We prove the proposition by induction over . If , then we may take . So assume that and write . We have , where is a basic integral neighbourhood of height of and an intersection of basic integral neighbourhoods of heights . By the induction hypothesis, there exists an integral neighbourhood of , such that and have constant sign for all . Now take

Exercise 9.18. Show that .

Exercise 9.19. Show that maps into .

Exercise 9.20. If , then show that either and , or , and , or .

Exercise 9.21. Show that the extension of to is not additive.

Exercise 9.22.

  1. Show that the operators and naturally extend to resp. .

  2. Give an explicit formula for , where .

  3. Does the post-composition operator with preserve addition and/or multiplication?

Exercise 9.23.

  1. Compute the nested integral sequences for , and .

  2. Prove analogues of the results from section 9.4 for nested integral sequences.

9.6Differential polynomials near cuts

Let and . In this section, we study the asymptotic behaviour of for close to . In particular, we study the sign of for close to .

9.6.1Differential polynomials near serial cuts

Lemma 9.25. Let . Then there exist with and , such that for all . Moreover, if , then and may be chosen such that for all .

Proof. If there exists a with , then the lemma follows for and any with and . Assume for contradiction that .

If , then each with induces a solution to , by letting be the distinguished solution to the equation . Now pick such that

for all . This is possible, since would be a subset of the grid-based set , if for some and all . Now are pairwise distinct starting monomials for the linear differential equation , which is impossible.

Assume now that and choose with . Consider the set of all partial unravellings

(9.22)

relative to the equation , such that and . Since contains the identity refinement, we may choose (9.22) to be finest in , by corollary 8.32. We claim that is maximal for , such that .

Indeed, assume for contradiction that some also satisfies

and let . By proposition 8.27, there exists a partial unravelling

which is finer than (9.22), and such that . But then and , which contradicts the maximality of (9.22).

Our claim implies that for any with . This contradicts the definition of .

9.6.2Differential polynomials near constants

Lemma 9.26. Let and . Then there exist an integral neighbourhood of and , such that

and for all .

Proof. Let be such that is exponential, and . Let and be such that .

Take and let . If , then , so and . If , then , whence , and . This proves that either and , or and .

If , then , where is the leading coefficient of and . Since , it follows that , whence for . Moreover, is not a starting monomial for , since . Consequently .

Similarly, if , then , where and are such that . Again, we have , and . Furthermore, , so is not a starting monomial for . Therefore, .

Corollary 9.27. Let be an irregular cut of height . Then there exist an integral neighbourhood of , , and , such that for all , we have

Moreover, if , then we may take such that for all .

9.6.3Differential polynomials near nested cuts

Lemma 9.28. Let be a cut of integral height . Then there exist with and , such that for all , so that is not a starting monomial for , we have

Moreover, if , then and may be chosen such that for all as above.

Proof. Let . By proposition 8.17, there exists a unique integer such that for each equalizer for , we have either and or and . Now let be such that is not a starting monomial for , and if and if for all equalizers for . Then for some and for some sufficiently large and . Consequently,

which proves the first statement of the lemma. Moreover, since is not a starting monomial for , we have . If , it follows that whenever is chosen such that .

9.6.4Differential polynomials near arbitrary cuts

Theorem 9.29. Let and let be a cut of height with integral guiding sequence . Then there exists an integral neighbourhood of of height , such that one of the following holds:

Moreover, if , then may be chosen such that for all .

Proof. We prove the theorem by induction over . So assume that we proved the theorem for all smaller (for , there is nothing to prove). If , then the result follows from lemma 9.25. If with and , then we are done by corollary 9.27.

In the last case, we have for some . By lemma 9.28, there exists an and an integral neighbourhood of of height , such that for all so that is not a starting monomial for , we have

(9.25)

By the induction hypothesis, there exists an integral neighbourhood of of height , such that and one of the following holds:

Moreover, for , the induction hypothesis and proposition 8.16 also imply that is not a starting monomial for , since .

Now take . Then the relations (9.25) and (9.26) resp. (9.27) entail (9.23) resp. (9.24) for all . Moreover, if , then may be chosen such that for all , by lemma 9.28.

9.6.5On the sign of a differential polynomial

Let be a differential polynomial. We denote by the sign function associated to :

We say that is constant at the right of , if there exist and such that for all . In that case, we denote . We say that is constant at the left of , if there exist and such that for all , and we denote . If is constant at the left and at the right of , then we say that is constant at both sides of .

Proposition 9.30. Let with and . Then

(9.28)
(9.29)
(9.30)
(9.31)

Proof. For , we have

and . That proves (9.28). The other properties follow by considering and instead of .

Theorem 9.31. Let and . Then

  1. If is regular, then is constant on both sides of , and .

  2. If is left-oriented, then is constant at the left of .

  3. If is right-oriented, then is constant at the right of .

  4. If , then is constant at both sides of .

Proof. Propositions 9.24, 9.30 and theorem 9.29 imply (a), (b) and (c). Property (d) follows by considering instead of .

Proposition 9.32. Let , and denote . Then

Proof. From (9.28), it follows that . Consequently, for all sufficiently small , so that . Similarly, we obtain . Since

for all , we also have

Let be an initial segment of . The sign of modulo at a point is defined as follows. If , then we set . Recall that is the multiplicity of as a zero of modulo in this case. If , then for all , we have , and we set . Given and , we write if for all . Given , we denote

We say that is constant at the right of , if there exist and such that for all . In that case, we denote . Constance at the left is defined similarly. If is of the form , then we also write , and .

Exercise 9.24. Let be a Hardy field. Consider a cut and an element , such that for . If is defined, then show that there exists a with and for all .

Exercise 9.25. Show that ,

and

do not satisfy an algebraic differential equation with coefficients in . Compare with the technique from exercise 8.25.

Exercise 9.26. Let be a real analytic solution to (for a construction of such a solution, see [Kne50]). Show that is a Hardy field.

9.7The intermediate value theorem

In this section, we assume that is a real closed field. Our main aim is to prove the following intermediate value theorem:

Theorem 9.33. Let and be such that and . Then there exists a with .

In fact, we will prove the following stronger version of the theorem:

Theorem 9.34. Let and let be an initial segment of . Assume that are such that and . Then there exists a such that is odd.

In both theorems, the interval may actually be replaced by a more general interval with . More precisely, we say that changes sign on modulo , if and exist and . Notice that changes sign on modulo if and only if changes sign on . We say that changes sign at modulo if is odd. Now if changes sign on , then it also changes sign on for some with , and . Consequently, if theorem 9.34 holds for all intervals with , then it also holds for all intervals with .

Remark 9.35. The fact that changes sign at modulo does not necessarily imply . Indeed, changes sign modulo at , but and are not defined.

9.7.1The quasi-linear case

Lemma 9.36. Let be of order and let be an initial segment of . Assume that the theorem 9.34 holds for all differential polynomials of order . Let be such that the equation

(9.32)

is quasi-linear and assume that changes sign on . Then there exists a with .

Proof. Modulo an additive conjugation by a sufficiently small , we may assume without loss of generality that . Since (9.32) is quasi-linear, it admits only a finite number of starting monomials. Let be the largest such monomial. Modulo a multiplicative conjugation with , we may assume without loss of generality that . We must have , since otherwise . Furthermore, since , we either have with , or with .

If , then the distinguished solution to (9.32) satisfies . Moreover, from proposition 9.32, it follows that

We claim that . Otherwise, theorem 9.34 applied to implies the existence of a with

Taking such that (whence ) , it follows that would be a starting monomial for (9.32). Our claim implies that , so that . Furthermore, , so

If , then for any . Let , where is the distinguished solution to . Then and again implies .

9.7.2Preserving sign changes during refinements

Lemma 9.37. Let and let be of one of the following forms:

  1. with .

  2. with .

  3. .

If changes sign on , then there exists a with

Proof. In cases (b) and (c), we may replace (and ) by a sufficiently large (resp. small ). Therefore, it suffices to deal with intervals of the form (a). From lemma 9.26, it follows that , for all . Without loss of generality, we may therefore assume that with and .

If is odd, then we choose with , and obtain

If is even, then changes sign on . Since is real closed, it follows that there exists a where admits a root of odd multiplicity , and

Lemma 9.38. Let be of order and let be an initial segment of . Assume that the theorem 9.34 holds for all differential polynomials of order . Let be such that . Then there exists and with and .

Proof. Modulo an additive conjugation with a sufficiently small , we may assume without loss of generality that

We prove the lemma by induction over . If , then the assumptions cannot be met, so we have nothing to prove. So assume that . Since , there exists an equalizer of the form for the equation . We distinguish the following cases:

Since , we are done by the induction hypothesis.

and
The result follows immediately when applying lemma 9.37 to and the interval .

or
If , then let be such that for all . Then for any with , we have . So both if and if , there exists an with , and .

Since , we must have . From proposition 9.32, it follows that

Applying theorem 9.34 to , we infer that there exists a with . Taking such that (whence ), it follows that is a starting monomial for . Moreover, is of the form with , since . Furthermore, since , we have

whence is odd. For any , we conclude that

9.7.3Proof of the intermediate value theorem

We will prove the following variant of theorem 9.34:

Theorem 9.39. Let and let be an initial segment of . Given , consider an interval of one of the following forms:

  1. with and with .

  2. with .

  3. with .

  4. with .

If changes sign on , then there exists a point such that is odd.

Proof. We prove the theorem by a double induction over the order of and the Newton degree of

The case when is contrary to our assumptions. So assume that and that the hypothesis holds for all smaller orders, as well as for the same order and smaller . Notice that we must have , since changes sign modulo on .

Let us first show that cases (a), (c) and (d) can all be reduced to case (b). This is clear for (c) by considering instead of . In case (d), there exists a such that for all with . For any such , it follows that changes sign on . As to (a), we observe that changes sign either on , on , or on . The first to cases have already been dealt with. The last case reduces to (d) when applying lemma 9.37 to the polynomial and the interval .

Let us now show how to prove (b). Modulo an additive conjugation, we may assume without loss of generality that . If , then we are done by lemma 9.36. So assume that . Consider the set of all partial unravellings

(9.33)

with either and , or and

By corollary 8.32, we may choose a finest partial unravelling (9.33) in .

Take if and such that otherwise. By lemma 9.38, applied to , there exists a term with , and such that

We claim that we cannot have . Indeed, by proposition 8.27, this would imply the existence of a partial unravelling

with , which is finer than (9.33). But then

contradicts the maximality of (9.33). Consequently, we have

and the theorem follows by applying the induction hypothesis for on the interval .

Exercise 9.27.

  1. Prove that if .

  2. Prove that if .

  3. Other similar properties.

References

AS26
E. Artin and O. Schreier. Algebraische Konstruction reeller Körper. Hamb. Abh. , pages 85–99, 1926.

AvdD01
M. Aschenbrenner and L. van den Dries. Liouville closed -fields. J. Pure Appl. Algebra , 2001. to appear.

AvdD02
M. Aschenbrenner and L. van den Dries. -fields and their Liouville extensions. Math. Z. , 242:543–588, 2002.

AvdD04
M. Aschenbrenner and L. van den Dries. Asymptotic differential algebra. In Contemporary Mathematics . Amer. Math. Soc., Providence, RI, 2004. To appear.

AvdDvdH
M. Aschenbrenner, L. van den Dries, and J. van der Hoeven. Linear differential equations over H-fields. In preparation.

AvdDvdH05
Matthias Aschenbrenner, Lou van den Dries, and J. van der Hoeven. Differentially algebraic gaps. Selecta Mathematica , 11(2):247–280, 2005.

BB56
C.A. Briot and J.C. Bouquet. Propriétés des fonctions définies par des équations différentielles. Journal de l'École Polytechnique , 36:133–198, 1856.

BCR87
J. Bochnak, M. Coste, and M.-F. Roy. Géométrie algébrique réelle . Ergebnisse der Mathematik und ihrer Grenzgebiete. Springer, Berlin-Heidelberg, 1987. 3. Folge, Band 12.

Bir09
G.D. Birkhoff. Singular points of ordinary differential equations. Trans. Am. Math. Soc. , 10:436–470, 1909.

Bor28
É. Borel. Leçons sur les séries divergentes . Gauthiers Villards, 2-nd edition, 1928. Reprinted by Jacques Gabay.

Bos81
M. Boshernitzan. An extension of Hardy's class l of 'orders of infinity'. J. Analyse Math. , 39:235–255, 1981.

Bos82
M. Boshernitzan. New 'orders of infinity'. J. Analyse Math. , 41:130–167, 1982.

Bos87
M. Boshernitzan. Second-order differential equations over hardy fields. J. London Math. Soc. , 35:109–120, 1987.

Bou61
N. Bourbaki. Fonctions d'une variable réelle . Éléments de Mathématiques (Chap. 5. Hermann, 2-nd edition, 1961.

Bou70
N. Bourbaki. Théorie des ensembles . Hermann, 1970.

Bra91
B.L.J. Braaksma. Multisummability and Stokes multipliers of linear meromorphic differential equations. J. Diff. Eq , 92:45–75, 1991.

Bra92
B.L.J. Braaksma. Multisummability of formal power series solutions to nonlinear meromorphic differential equations. Ann. Inst. Fourier de Grenoble , 42:517–540, 1992.

Can99
G. Cantor. Sur les fondements de la théorie des ensembles transfinis . Jacques Gabay, 1899. Reprint from les Mémoires de la Société des Sciences physiques et naturelles de Bordeaux.

Can93
J. Cano. An extension of the Newton-Puiseux polygon construction to give solutions of Pfaffian forms. Ann. Institut Fourier de Grenoble , 43(1):125–142, 1993.

Chi86
A.L. Chistov. Polynomial complexity of the newton-puiseux algorithm. In Proc. Symp. Math. Found. Comp. Sc. , pages 247–255, Bratislava, 1986. Springer Lect. Notes in Comp. Sc. 233.

CNP93
B. Candelberger, J.C. Nosmas, and F. Pham. Approche de la résurgence . Actualités mathématiques. Hermann, 1993.

Con76
J.H. Conway. On numbers and games . Academic Press, 1976.

Dah84
B.I. Dahn. The limiting behaviour of exponential terms. Fund. Math. , 124:169–186, 1984.

dBR75
P. du Bois-Reymond. Über asymptotische Werte, infinitäre Approximationen und infinitäre Auflösung von Gleichungen. Math. Ann. , 8:363–414, 1875.

dBR77
P. du Bois-Reymond. Über die Paradoxen des Infinitärscalcüls. Math. Ann. , 11:149–167, 1877.

DG86
B. I. Dahn and P. Göring. Notes on exponential-logarithmic terms. Fundamenta Mathematicae , 127:45–50, 1986.

DW84
Bernd I. Dahn and Helmut Wolter. Ordered fields with several exponential functions. Z. Math. Logik Grundlag. Math. , 30(4):341–348, 1984.

É03
J. Écalle. Recent advances in the analysis of divergence and singularities. In Yu.S. Ilyashenko C. Rousseau, editor, Proc. of the July 2003 Montreal Summer School on Singularities and Normal Forms . Kluwer, 1903. To appear.

É85
J. Écalle. Les fonctions résurgentes I–III . Publ. Math. d'Orsay 1981 and 1985, 1985.

É92
J. Écalle. Introduction aux fonctions analysables et preuve constructive de la conjecture de Dulac . Hermann, collection: Actualités mathématiques, 1992.

É93
J. Écalle. Six lectures on transseries, analysable functions and the constructive proof of Dulac's conjecture. In D. Schlomiuk, editor, Bifurcations and periodic orbits of vector fields , pages 75–184. Kluwer, 1993.

Fab85
E. Fabry. Sur les intégrales des équations différentielles linéaires à coefficients rationnels . PhD thesis, Paris, 1885.

Fin89
H.B. Fine. On the functions defined by differential equations, with an extension of the Newton-Puiseux polygon construction to these equations. Amer. Jour. of Math. , 12:295–322, 1889.

GG88
K.O. Geddes and G.H. Gonnet. A new algorithm for computing symbolic limits using hierarchical series. In Proc. ISSAC '88 , volume 358 of Lect. Notes in Comp. Science , pages 490–495. Springer, 1988.

GG92
G.H. Gonnet and D. Gruntz. Limit computation in computer algebra. Technical Report 187, ETH, Zürich, 1992.

Gri91
D.Y. Grigoriev. Complexity of factoring and calculating the gcd of linear ordinary differential operators. J. Symb. Comp , 10:7–37, 1991.

Gru96
D. Gruntz. On computing limits in a symbolic manipulation system . PhD thesis, E.T.H. Zürich, Switzerland, 1996.

GS91
D. Grigoriev and M. Singer. Solving ordinary differential equations in terms of series with real exponents. Trans. of the AMS , 327(1):329–351, 1991.

Hah07
H. Hahn. Über die nichtarchimedischen Größensysteme. Sitz. Akad. Wiss. Wien , 116:601–655, 1907.

Har10
G.H. Hardy. Orders of infinity . Cambridge Univ. Press, 1910.

Har11
G.H. Hardy. Properties of logarithmico-exponential functions. Proceedings of the London Mathematical Society , 10(2):54–90, 1911.

Har63
G.H. Hardy. Divergent series . Clarendon Press, Oxford, 3rd edition, 1963.

Hau08
F. Hausdorff. Grundzüge einer Theorie der geordneten Mengen. Math. Ann. , 65:435–505, 1908.

Hig52
G. Higman. Ordering by divisibility in abstract algebras. Proc. London Math. Soc. , 2:326–336, 1952.

Kho91
A.G. Khovanskii. Fewnomials , volume 88 of Translations of Mathematical Monographs . A.M.S., Providence RI, 1991.

Kne50
H. Kneser. Reelle analytische Lösungen der Gleichung und verwandter Funktionalgleichungen. Jour. f. d. reine und angewandte Math. , 187(1/2):56–67, 1950.

Kol73
E.R. Kolchin. Differential algebra and algebraic groups . Academic Press, New York, 1973.

Kru60
J.B. Kruskal. Well-quasi-ordering, the tree theorem and Vázsoni's conjecture. Trans. Am. Math. Soc. , 95:210–225, 1960.

Kuh00
S. Kuhlmann. Ordered exponential fields . Fields Institute Monographs. Am. Math. Soc., 2000.

LC93
T. Levi-Civita. Sugli infiniti ed infinitesimi attuali quali elimenti analitici. Atti ist. Ven. , 7:1765–1815, 1893.

Lio37
J. Liouville. Mémoire sur la classification des transcendantes, et sur les racines de certaines équations en fonction finie explicite des coefficients. J. Math. Pures et Appl. , 2:56–104, 1837.

Lio38
J. Liouville. Suite du mémoire sur la classification des transcendantes, et sur les racines de certaines équations en fonction finie explicite des coefficients. J. Math. Pures et Appl. , 3:523–546, 1838.

Mal79
J. Malitz. Introduction to mathematical logic . Undergraduate texts in Mathematics. Springer-Verlag, New York, 1979.

New71
I. Newton. De methodis serierum et Fluxionum . Manuscript, 1671.

NW63
C. St. J. A. Nash-Williams. On well-quasi-ordering finite trees. Proc. Cambridge Philos. Soc. , 59:833–835, 1963.

Poi86
H. Poincaré. Sur les intégrales irrégulières des équations linéaires. Acta Math. , 8:295–344, 1886.

Poi90
H. Poincaré. Sur le problème des trois corps et les équations de la dynamique. Acta Math. , 13:1–270, 1890.

Poi93
H. Poincaré. Les méthodes nouvelles de la mécanique céleste , volume Tôme II. Gauthier-Villars, Paris, 1893.

Pui50
M.V. Puiseux. Recherches sur les fonctions algébriques. J. Math. Pures et Appliquées , 15:365–480, 1850.

Rib64
P. Ribenboim. Théorie des valuations . Les Presses de l'Université de Montréal, 1964. 2-nd Ed. 1968.

Ric97
D. Richardson. How to recognise zero. JSC , 24:627–645, 1997.

Rit50
J.F. Ritt. Differential algebra . Amer. Math. Soc., New York, 1950.

Ros80
M. Rosenlicht. Differential valuations. Pacific J. Math. , 86:301–319, 1980.

Ros83a
M. Rosenlicht. Hardy fields. Journal of Math. Analysis and Appl. , 93:297–311, 1983.

Ros83b
M. Rosenlicht. The rank of a Hardy field. Trans. Amer. Math. Soc. , 280(2):659–671, 1983.

Ros87
M. Rosenlicht. Growth properties of functions in Hardy fields. Trans. Amer. Math. Soc. , 299(1):261–272, 1987.

RSSvdH96
D. Richardson, B. Salvy, J. Shackell, and J. van der Hoeven. Expansions of exp-log functions. In Y.N. Lakhsman, editor, Proc. ISSAC '96 , pages 309–313, Zürich, Switzerland, July 1996.

Sal91
B. Salvy. Asymptotique automatique et fonctions génératrices . PhD thesis, École Polytechnique, France, 1991.

Sch01
M.C. Schmeling. Corps de transséries . PhD thesis, Université Paris-VII, 2001.

Sei54
A. Seidenberg. A new decision method for elementary algebra. An. of Math. , 60:365–374, 1954.

Sei56
A. Seidenberg. An elimination theorem for differential algebra. Univ. California Publ. Math. (N.S.) , pages 31–38, 1956.

Sei68
A. Seidenberg. Reduction of singularities of the differentiable equation . Amer. J. of Math. , 90:248–269, 1968.

Sha90
J. Shackell. Growth estimates for exp-log functions. Journal of Symbolic Computation , 10:611–632, 1990.

Sha04
J. Shackell. Symbolic asymptotics , volume 12 of Algorithms and computation in Mathematics . Springer-Verlag, 2004.

Smi75
S. Smith. On the higher singularities of plane curves. Prod. London Math. Soc. , 6:153–182, 1875.

Spe99
P. Speissegger. The Pfaffian closure on an o-minimal structure. Jour. f. d. reine und angewandte Math. , 508:189–211, 1999.

Sti86
T.J. Stieltjes. Recherches sur quelques séries semi-convergentes. Ann. Sc. Éc. Norm. Sup. de Paris , 3:201–258, 1886.

Sti94
T.J. Stieltjes. Recherches sur les fractions continues. Ann. Fac. Sci. Toulouse , 8:J1–J122, 1894.

Sti95
T.J. Stieltjes. Recherches sur les fractions continues. Ann. Fac. Sci. Toulouse , 9:A1–A47, 1895.

Str77
W. Strodt. A differential algebraic study of the intrusion of logarithms into asymptotic expansions. In H. Bass, P.J. Cassidy, and J. Kovacic, editors, Contributions to algebra , pages 355–375. Academic Press, 1977.

SW71
W. Strodt and R.K. Wright. Asymptotic behaviour of solutions and adjunction fields for nonlinear first order differential equations , volume 109. Mem. Amer. Math. Soc., 1971.

Tar31
A. Tarski. Sur les ensembles définissables de nombres réels. Fund. Math. , 17:210–239, 1931.

Tar51
A. Tarski. A decision method for elementary algebra and geometry . Rand coorporation, Berkeley and Los Angelos, 2 edition, 1951.

vdD98
L. van den Dries. Tame topology and o-minimal structures , volume 248 of London Math. Soc. Lect. Note . Cambridge university press, 1998.

vdD99
L. van den Dries. O-minimal structures and real analytic geometry. In B. Mazur et al., editor, Current Developments in Mathematics , pages 105–152. Int. Press, Somerville, MA, 1999.

vdH95
J. van der Hoeven. Automatic numerical expansions. In J.-C. Bajard, D. Michelucci, J.-M. Moreau, and J.-M. Müller, editors, Proc. of the conference "Real numbers and computers", Saint-Étienne, France , pages 261–274, 1995.

vdH96
J. van der Hoeven. On the computation of limsups. Journal of Pure and Applied Algebra , 117/118:381–394, 1996.

vdH97
J. van der Hoeven. Automatic asymptotics . PhD thesis, École polytechnique, France, 1997.

vdH98
J. van der Hoeven. Generic asymptotic expansions. AAECC , 9(1):25–44, 1998.

vdH00
J. van der Hoeven. A differential intermediate value theorem. Technical Report 2000-50, Univ. d'Orsay, 2000.

vdH01a
J. van der Hoeven. Complex transseries solutions to algebraic differential equations. Technical Report 2001-34, Univ. d'Orsay, 2001.

vdH01b
J. van der Hoeven. Fast evaluation of holonomic functions near and in singularities. JSC , 31:717–743, 2001.

vdH01c
J. van der Hoeven. Formal asymptotics of solutions to certain linear differential equations involving oscillation. Technical Report 2001-60, Prépublications d'Orsay, 2001.

vdH01d
J. van der Hoeven. Operators on generalized power series. Journal of the Univ. of Illinois , 45(4):1161–1190, 2001.

vdH02a
J. van der Hoeven. A differential intermediate value theorem. In B. L. J. Braaksma, G. K. Immink, M. van der Put, and J. Top, editors, Differential equations and the Stokes phenomenon , pages 147–170. World Scientific, 2002.

vdH02b
J. van der Hoeven. Relax, but don't be too lazy. JSC , 34:479–542, 2002.

vK75
S. von Kowalevsky. Zur Theorie der partiellen Differentialgleichungen. J. Reine und Angew. Math. , 80:1–32, 1875.

Wil96
A. Wilkie. Model completeness results for expansions of the real field by restricted Pfaffian functions and the exponential function. J. A.M.S. , 9:1051–1094, 1996.

Glossary

Chapter 1. Orderings

quasi-ordering

12

equivalent elements w.r.t. quasi-ordering

12

disjoint union of and

12

ordered union of and

13

Cartesian product of and

13

anti-lexicographic product of and

13

set of words over

13

set of non-empty words over

13

ordering defined by

14

set of commutative words over

15

the ordinal number

16

final segment generated by

17

initial segment generated by

17

root of

19

set of finite -labeled trees

20

subset of positive or zero elements in

22

subset of strictly positive elements in

22

subset of non-zero elements in

22

subset of negative or zero elements in

22

subset of strictly negative elements in

22

absolute value of

22

subset of non-zero-divisors in

25

is dominated by

25

Landau's notation for

25

is asymptotic to

25

is negligible w.r.t.

25

Landau's notation for

25

is equivalent to

25

elements of which can be raised to a power

30

if and otherwise

30

is flatter than or as flat as

30

is flatter than

30

is as flat as

30

and are similar modulo flatness

30

flat subring of

31

modulo flatness

31

modulo flatness

31

modulo elements flatter than

31

modulo elements flatter than

31

modulo elements flatter than or as flat as

31

modulo elements flatter than or as flat as

31

Chapter 2. Grid-based series

quasi-ordered monomial monoid

34

monomials

34

ring of coefficients

36

support of a series

36

ring of grid-based series in with coefficients in

36

coefficient of in

36

natural multivariate series in

38

recursive multivariate series in

38

dominant monomial of

40

dominant coefficient of

40

dominant term of

40

series with

40

purely infinite part of

41

constant part of

41

infinitesimal part of

41

bounded part of

41

set of purely infinite elements in

41

set of infinitesimal elements in

41

set of bounded elements in

41

the series

42

restriction of to

42

is a truncation of

43

collection of families with values in

44

families

44

alternative notation for family

44

disjoint union of two families and

44

Cartesian product of families and

44

application of a function on families

45

and coincide modulo renaming indexes

45

is contained in modulo renaming indexes

45

collection of strongly summable families over

46

strong sum of

46

family of terms occurring in

49

family of monomials occurring in

49

family of power products of elements in

50

extension of by strong linearity

50

composition of with

53

Chapter 3. The Newton polygon method

Newton polynomial associated to

65

series in with Cartesian representations in

71

subset of convergent grid-based series in

73

Chapter 4. Transseries

the -th iterate of with

80

the -th iterate of with

80

field of grid-based transseries

84

flat subset of

87

steep complement of

87

field of grid-based transseries in

87

field of logarithmic transseries in

88

exponential extension of

88

transseries of exp. height and log. depth

89

field of exponential transseries

90

upward shifting of

90

downward shifting of

90

contraction of

91

dilatation of

91

field of convergent transseries

94

Chapter 5. Operations on transseries

derivative of

98

logarithmic derivative of

98

distinguished integral of

103

right composition with

106

composition of and

106

functional inverse of

111

scalar product of and

112

Chapter 6. Grid-based operators

composition of multilinear grid-based operators

117

operator support of

117

sets of operators on resp.

118

homogeneous part of degree of

122

composition of grid-based operators and

124

set of strongly multilinear

124

set of grid-based operators from

125

atomic -linear grid-based operator

125

arity of an atomic operator

126

inputs of an atomic operator

126

output of an atomic operator

126

atomic decomposition of

126

composition of atomic families and

126

Chapter 7. Linear differential equations

alternative notation for dominant coefficient

136

serial support of

136

multiplicative conjugate of by

137

upward and downward shiftings of

137

Stirling numbers of the first kind

137

Stirling numbers of the second kind

137

-th iterates of and

138

space of operators of the form on

138

differential polynomial with

139

differential Riccati polynomial associated to

139

algebraic part of

140

additive conjugate of by

140

derivative of differential operator

140

set of regular monomials for

141

set of irregular monomials for

141

trace of

141

trace of w.r.t.

141

distinguished right inverse of

146

set of solutions to

146

complexification of

158

field of oscillating transseries

159

spectral part of associated to

159

action of on the spectral component

159

Chapter 8. Algebraic differential equations

coefficient of in differential polynomial

166

dominant coefficient of

167

shorthand for

167

coefficient of in

167

-th homogeneous part of

167

(total) degree of

167

differential valuation of

167

shorthand for

168

(normalized) coefficient of in

168

-th isobaric part of

168

weight of

168

weighted differential valuation of

168

-th iterated logarithmic derivative

168

shorthand for

168

coefficient of in

168

additive conjugation of with

169

multiplicative conjugation of with

170

upward and downward shiftings of

170

generalized Stirling number of the first kind

170

generalized Stirling number of the second kind

171

differential Newton polynomial for

173

Newton degree of

174

-equalizer for

178

differential Riccati polynomial associated to

179

set of exponential transmonomials

184

set of logarithmic transmonomials

197

Chapter 9. The intermediate value theorem

maximal open interval containing

203

the interval

203

the interval

203

compactification of a total ordering

203

a typical element of

203

minimal element of

203

maximal element of

203

shorthand for

206

totally ordered grid-based algebra

208

shorthand for

208

shorthand for

208

set of finite cuts in

208

set of monomials and monomial cuts

208

dominant monomial of

209

width of

209

initializer of

210

serial completion of

210

typical serial cut

210

shorthand for

212

the cut

219

basic integral neighbourhood

220

integral coordinates of

221

sign of

227

sign of at the right of a point

227

sign of at the left of a point

227

sign of modulo

228

sign of at the right of a point modulo

228

sign of at the left of a point modulo

228

Index

absolute value, 22

accumulation-free set, 35

additive conjugate, 140, 169

ade_solve, 194

ade_solve_sub, 194

admissible refinement, 61, 66

alg_st_mon, 193

algebraic

starting monomial, 174

starting term, 174

antichain, 17

anti-lexicographical

direct sum, 23

tensor product, 23

archimedean, 27

ring, 27

arity

maximal of operator, 45

tree, 20

associated

dominance relation, 26

neglection relation, 26

asymptotic, 25

-algebra, 27

basis, 54

derivation, 98, 102

difference operator, 106

differential equation, 165

solution modulo , 175

equation, 65

-module, 26

Riccati equation, 152

ring with -powers, 30

scale, 54

atomic

decomposition, 126

symmetric, 126

family, 126

operator, 125

input, 126

output, 126

symmetric, 126

unravelling, 186

bad sequence, 18

minimal, 19

basic integral neighbourhood, 220

basis

asymptotic, 54

asymptotic scale, 54

Cartesian, 71

distinguished, 146

bounded, 27

series, 42

bounded part, 41

canonical decomposition, 40

canonical decomposition, 219

Cantor's theorem, 16

Cartesian

basis, 71

community, 72

representation, 69

compatible, 70

faithful, 73

chain, 17

child, 20

coefficient, 36

dominant, 40

compactification of total ordering, 204

compactness theorem, 204

comparability class, 30

comparable, 12

compatible

Cartesian representations, 70

dominance relation, 26

neglection relation, 26

refinement, 187

composition

grid-based operator, 124

multilinear grid-based operator, 117

conjugate

additive, 140, 169

multiplicative, 60, 137, 170

constant

at both sides, 227

at the left, 227

at the right, 227

constant part, 41

contracting operator, 128

contraction of transseries, 91

convergent

grid-based series, 73

transseries, 94

well-based, 96

convex, 28

cut, 203

initializer, 210

integral height, 219

left-oriented, 220

monomial, 208

oriented, 220

pathological, 220

regular, 220

right-oriented, 220

serial, 211

width, 209

decomposition

atomic, 126

symmetric, 126

by degrees, 167

by orders, 167

canonical, 219

into homogeneous parts, 125, 167

into isobaric parts, 168

logarithmic, 168

serial, 167

degree

differential polynomial, 167

Newton, 65, 152, 174

depth

logarithmic, 89

transseries, 90

derivation

asymptotic, 98, 102

exp-log, 98

strong, 98, 116

derivative

differential operator, 140

logarithmic, 98

iterated, 168

Dickson's lemma, 18

diff_st_mon, 193

difference operator

asymptotic, 106

exp-log, 106

increasing, 106

strong, 106, 117

differential

algebraic equation, 165

asymptotic, 165

grid-based operator, 133

operator

additive conjugate, 140

derivative, 140

distinguished right inverse, 146

downward shifting, 137

monic, 163

multiplicative conjugate, 137

trace, 141

upward shifting, 137

polynomial

additive conjugate, 169

decomposition

by degrees, 167

by orders, 167

into homogeneous parts, 167

into isobaric parts, 168

logarithmic, 168

serial, 167

degree, 167

downward shifting, 170

homogeneous part, 167

isobaric part, 168

multiplicative conjugate, 170

Newton, 173

transparent, 173

upward shifting, 170

valuation, 167

weight, 168

weighted valuation, 168

Riccati polynomial, 179

starting monomial, 174

starting term, 174

strong operator, 117

dilatation of transseries, 91

direct sum, 23

anti-lexicographical, 23

distinguished

basis, 146

factorization, 164

integral, 103

right inverse, 146, 160

solution, 146, 160, 182, 197

unraveller, 197

dominance relation, 25

associated, 26

compatible, 26

flattened, 31

total, 25

dominant

coefficient, 40

exponent, 58

monomial, 40, 209

term, 40

dominated, 25

downward shifting, 90, 137, 170

equalizer, 178

equation

asymptotic, 65

Newton, 58

quasi-linear, 61, 65, 182

equivalent, 12, 25

family, 45

expansion

nested, 214

integral, 220

exp-log

derivation, 98

difference operator, 106

function, 94

ordered field, 83

ordered ring, 83

partial ring, 83

transseries, 94

exponential

function, 80

height, 89

-module, 30

partial ring, 80

ordered, 81

ring, 80

ordered, 81

transseries, 90

extended

integral guiding sequence, 220

integral height, 220

extension

by strong linearity, 50

least common, 43

extensive

grid-based operator, 128

operation, 21

strictly operator, 128

factorization

distinguished, 164

faithful Cartesian representation, 73

family

atomic, 126

equivalent, 45

grid-based, 36

refines, 46

well-based, 39

field

grid-based transseries, 84

ordered – with -powers, 30

ordered exp-log , 83

final segment, 17

generated by , 17

finer refinement, 175

-finite set, 35

flat

as – as, 30

subring, 31

subset, 44

flatter, 30

greatest common truncation, 43

grid-based

algebra, 37, 115

family, 36

field of transseries, 84, 89

mapping, 50

module, 115

operator, 122

composition, 124

contracting, 128

decomposition

atomic, 126

homogeneous parts, 125

symmetric atomic, 126

differential, 133

extensive, 128

homogeneous part, 122

integral, 133

multilinear, 116

multilinear family for , 122

of type , 133

strictly extensive, 128

with multipliers in , 128

series, 36

convergent, 73

set, 34

summation, 48

group

ordered – with -powers, 30

with -powers, 30

Hahn space, 29

Hardy field, 23

Hausdorff interval topology, 203

height

exponential, 89

extended integral , 220

integral cut, 219

Higman's theorem, 18

homogeneous

part, 122

decomposition into s, 125

differential polynomial, 167

grid-based operator, 122, 125

incomplete transbasis theorem, 92

increasing

difference operator, 106

mapping, 12

induction

Noetherian, 19

transfinite, 16

infimum, 19

infinitary operator, 45

infinitesimal, 27

series, 42

infinitesimal part, 41

initial segment, 17

generated by , 17

initializer of cut, 210

integral

coordinates, 221

distinguished, 103

grid-based operator, 133

guiding sequence, 220

height

cut, 219

extended, 220

neighbourhood, 221

basic, 220

nested expansion, 220

nested sequence, 220

refinement, 198

integration

strong, 116

intermediate value theorem, 229

interval, 202

open, 202

topology, 202

Hausdorff, 203

inverse of transseries, 111

irregular monomial for , 141

isobaric part, 168

Kruskal's theorem, 21

Laurent series, 38

multivariate, 38

leaf, 19

least common extension, 43

left neighbourhood, 222

left-oriented cut, 220

level

transbasis, 92

transseries, 90

Levi-Civitian set, 36

local community, 72

logarithmic

depth, 89

derivative, 98

iterated, 168

function, 82

transseries, 89

log-confluent transseries, 92

mixed starting monomial, 174

monic

differential operator, 163

series, 163

monoid

monomial, 115

monomial, 34, 36

cut, 208

dominant, 40, 209

monoid, 115

set, 115

starting, 65, 152, 174

algebraic, 174

differential, 174

mixed, 174

strong morphism, 72

multilinear

family for grid-based operator, 122

grid-based operator, 116

composition, 117

summable family, 124

strongly, 116

type, 133

multiplicative conjugate, 60, 137, 170

multiplicity

solution modulo , 175

starting term, 65, 152, 174

multipliers

grid-based operator with in , 128

multivariate

Laurent series, 38

series, 38

neglection relation, 25

associated, 26

compatible, 26

flattened, 31

negligible, 25

neighbourhood, 222

integral, 221

basic, 220

left, 222

one-sided, 222

right, 222

nested

expansion, 214

integral, 220

sequence, 213

integral, 220

Newton

degree, 65, 152, 174

equation, 58

polygon, 58

differential, 180

polynomial, 58, 65

Newton_degree, 193

node, 19

leaf, 19

predecessor, 19

successor, 19

Noetherian induction, 19

normalized solution modulo , 175

one-sided neighbourhood, 222

open interval, 202

operator

atomic, 125

input, 126

output, 126

symmetric, 126

differential

monic, 163

grid-based, 122

composition, 124

contracting, 128

decomposition

atomic, 126

homogeneous parts, 125

symmetric atomic, 126

differential, 133

extensive, 128

homogeneous part, 122

integral, 133

multilinear family for , 122

of type , 133

strictly extensive, 128

with multipliers in , 128

infinitary, 45

strong differential, 117

support, 117, 123

ordered

-algebra, 22

exp-log field, 83

exp-log ring, 83

exponential ring, 81

field, 22

with -powers, 30

group with -powers, 30

-module, 22

monoid, 22

partial exponential ring, 81

ring, 22

with -powers, 30

ordering, 12

anti-lexicographic, 13

Cartesian product, 13

commutative words, 15

disjoint union, 12

embeddability, 13, 20

finest, 12

opposite, 14

ordered union, 13

strict, 14

total, 12

compactification, 204

well-founded, 15

words, 13

ordinal, 16

countable, 16

limit, 16

successor, 16

oriented cut, 220

oscillating transseries, 159

spectral decomposition, 159

part

bounded, 41

constant, 41

homogeneous, 122

decomposition into s, 125

differential polynomial, 167

infinitesimal, 41

purely infinite, 41

partial

exponential ring, 80

ordered, 81

unravelling, 187

pathological cut, 220

perfect ordered structure, 25

plane transbasis, 102

polynomial

differential

decomposition

by degrees, 167

by orders, 167

into homogeneous parts, 167

into isobaric parts, 168

logarithmic, 168

serial, 167

degree, 167

homogeneous part, 167

isobaric part, 168

Newton, 173

transparent, 173

valuation, 167

weight, 168

weighted valuation, 168

differential Riccati , 179

Newton, 58, 65

differential, 173

polynomial_solve, 67

positive derivation, 98, 102

power series, 38

predecessor, 19

Puiseux series, 38

purely infinite part, 41

quasi-analytic function, 96

quasi-linear

asymptotic Riccati equation, 152

equation, 61, 65, 182

quasi-ordering, 12

anti-lexicographic, 13

Cartesian product, 13

commutative words, 15

compatible equivalence relation, 14

disjoint union, 12

embeddability, 13, 20

finer, 12

finest, 12

opposite, 14

ordered union, 13

roughest, 12

total, 12

well, 17

well-founded, 15

words, 13

recursive

expansion, 38

multivariate series, 38

refinement, 61, 66, 153, 175

admissible, 61, 66

compatible, 187

finer, 175

integral, 198

regular

cut, 220

monomial for , 141

series, 40

term for , 141

relation

antisymmetric, 12

asymptotic, 25

dominance, 25

neglection, 25

reflexive, 12

transitive, 12

representation

Cartesian, 69

faithful, 73

semi-Cartesian, 69

restriction of series, 42

Riccati

differential polynomial, 140, 179

algebraic part, 140

equation modulo , 151

asymptotic, 152

riccati_solve, 155

right neighbourhood, 222

right-oriented cut, 220

ring

archimedean, 27

asymptotic with -powers, 30

exponential, 80

ordered, 81

ordered – with -powers, 30

ordered exp-log , 83

partial exp-log , 83, 83

partial exponential , 80

ordered, 81

with -powers, 30

root

almost multiple, 62

scalar product of transseries, 112

scale

asymptotic, 54

change, 54

semi-Cartesian representation, 69

sequence

integral guiding , 220

nested, 213

integral, 220

serial

cut, 211

decomposition, 167

series

bounded, 42

differentially algebraic, 75

dominant exponent, 58

effective, 76

grid-based, 36

convergent, 73

infinitesimal, 42

Laurent, 38

multivariate, 38

monic, 163

multivariate, 38

natural, 38

recursive, 38

order type, 39

power, 38

Puiseux, 38

regular, 40

restriction, 42

Taylor, 108, 122, 125

valuation, 58

well-based, 39

set

accumulation-free, 35

-finite, 35

grid-based, 34

Levi-Civitian, 36

monomial, 115

weakly based, 36

well-based, 34

countable, 35

shifting

downward, 90, 137, 170

upward, 90, 137, 170

sign change, 229

similar modulo flatness, 30

solution

distinguished, 146, 160, 182, 197

modulo , 175

multiplicity, 175

normalized, 175

st_term, 194

starting

coefficient, 59

exponent, 58

monomial, 58, 65, 152, 174

algebraic, 174

differential, 174

mixed, 174

term, 59, 65, 152, 174

algebraic, 174

differential, 174

multiplicity, 65, 152, 174

steep complement, 87

Stirling number, 137, 170

strong

Abelian group, 46

-algebra, 47

associativity, 46

commutativity, 45

derivation, 98, 116

difference operator, 106, 117

differential operator, 117

integration, 116

linear mapping, 47

-module, 47

monomial morphism, 72

multilinear mapping, 116

repetition, 46

ring, 47

summation operator, 117

tensor product, 120

trivial structure, 46

subtree, 19

successor, 19

support, 36

operator, 117, 123

Taylor series, 108, 122, 125

tensor product, 23

anti-lexicographical, 23

strong, 120

term, 36

dominant, 40

regular for , 141

starting, 65, 152, 174

algebraic, 174

differential, 174

multiplicity, 65, 152, 174

theorem

Cantor, 16

compactness, 204

Higman, 18

incomplete transbasis, 92

intermediate value, 229

Kruskal, 21

Newton-Puiseux, 68

Translagrange, 112

trace of differential operator, 141

transbasis, 92

incomplete theorem, 92

level, 92

plane, 102

transfinite induction, 16

Translagrange theorem, 112

transparent

differential polynomial, 173

transseries, 173

transseries

complex coefficients, 158

contraction, 91

convergent, 94

depth, 90

dilatation, 91

downward shift, 90

exp-log, 94

exponential, 90

exponential height, 89

field of grid-based , 84

in , 89

inverse, 111

level, 90

logarithmic, 89

logarithmic depth, 89

log-confluent, 92

oscillating, 159

spectral decomposition, 159

scalar product, 112

upward shift, 90

well-based, 91

convergent, 96

tree, 20, 20

arity, 20

-labeled, 20

leaf, 19

node, 19

root, 19

unoriented, 19

truncation, 43

greatest common, 43

ultra-strong

-algebra, 47

-module, 47

unbounded, 27

unravel, 195

unravel_sub, 195

unraveller

distinguished, 197

unravelling

atomic, 186

partial, 187

total, 186

upward shifting, 90, 137, 170

valuation, 28, 58

differential polynomial, 167

weighted, 168

weakly based set, 36

weight

differential polynomial, 168

vector, 168

weighted valuation, 168

well-based

family, 39

series, 39

set, 34

countable, 35

transseries, 91

convergent, 96

well-ordering, 15

well-quasi-ordering, 17

widening, 71

wider Cartesian basis, 71

width of cut, 209

word, 13

commutative, 15

Zorn's lemma, 15