A zero-test for D-algebraic transseries

Standard mathematical notation exists for many special functions such as

, etc. But how to decide whether an expression like

actually represents the zero function?

One popular approach is to rely on differential algebra [25, 20, 2], by defining

as a symbolic solution of the equation

. However, this only allows one to define

up to a multiplicative constant, which is insufficient to conclude that

Another approach is to define

as the unique solution of

with

. This can be made more precise by restricting our attention to D-algebraic power series. Let

be an effective field. We say that

is D-algebraic if it satisfies an equation

for some differential polynomial

. In that case,

is actually uniquely determined by

and a sufficient number of initial conditions. Given D-algebraic series

and a differential polynomial

, the zero-test problem now consists of deciding whether

. Many solutions have been proposed for this problem [24, 5, 6, 19, 26, 27, 22, 17, 15] and we refer to [12] for a brief overview of existing approaches.

However, one problem with ordinary power series is that they do not form a field. So-called transseries are a far reaching generalization of power series, by closing off

under exponentiation, logarithms, and infinite summation [4, 8, 7, 14]. An example of a transseries at infinity (

) is

The transseries with real coefficients form a field

that is closed under differentiation, composition and the resolution of many differential equations. A transseries

is again said to be D-algebraic if

for some

. For example, the transseries (1) is D-algebraic.

Given D-algebraic transseries

and a differential polynomial

, our main result is an algorithm for deciding whether

. In fact, we reduce this problem to the case

, but at the same time generalize it to the case where the coefficients of

and the differential polynomial

with

are taken in an effective differential subfield of

for which we already have a zero-test.

A substantial part of the paper is devoted to recalling required theoretical results about transseries from [14, 11, 1]. From an effective point of view, computations with transseries are most conveniently carried out with respect to a so-called transbasis

. This allows one to consider general transseries as power series in

with real exponents, and whose coefficients can recursively be expanded with respect to the transbasis

. For instance, for

, the transseries

is a series in

with coefficients in

. Along with our survey, we present a precise framework, much in the vein of [23, 10].

Having carried out the necessary preparations, our main algorithm turns out to be a natural extension of the zero-test from [15] for formal power series. Using a theorem from [11], we were also able to further sharpen the bound on the required expansion order. As an illustration of our algorithm, we will first define the Lambert function as the unique transseries solution to a suitable asymptotic differential equation and then verify that it satisfies the equation

2Generalized power series

Let

be a totally ordered abelian group. A subset

is said to be grid-based if there exist

and

with

Given a field

, consider a formal power series

with

and such that the support

is grid-based. Then we call

a grid-based power series (with coefficients in

and exponents in

) and we denote the set of such series by

or simply by

In [14, Section 2.2] it is shown that

forms a field. It actually forms a valued field for the valuation

defined by

(and

). If

is non-zero, then we call

the dominant monomial of

. If

is an ordered field, then so is

, by setting

. In that case, we will write

for the subset of strictly positive elements.

Example 2. If

is a “formal infinitely large variable”, then we define

and

and define the field of grid-based iterated series in

. We note that

and this inclusion is strict as soon as

: e.g.,

. Note also that

with

We will sometimes consider series

jointly with respect to all variables

and write

for its valuation. On other occasions, we expand

as a series in

with coefficients

and write

for its valuation in

For elements

in the value group (or infinity), we also write

for some integer

and

for all integers

. The following asymptotic relations will also be useful:

A field

is said to be effective if we have algorithms for the field operations and zero testing. An ordered field is effective if we also have an algorithm for the ordering. Assume that

is effective and that

is an effective ordered subfield of

We recursively define a lazy power series with coefficients in

and exponents in

as an algorithm

that takes no input and that either produces zero or a pair

with

and

, as well as another lazy power series

. The pair

actually represents a term

and we will use this latter notation in the sequel. Writing

, where the sequence stops whenever

produces zero, we allow coefficients

to be zero, but we require that

is a grid-based subset of

. We may thus regard

as a grid-based series

. Conversely, a series

is said to be computable if it can be computed as a lazy power series. We write

for the set of such series.

In fact,

forms a field and the lazy approach allows us to implement the ring operations in an elegant way as follows: given

and non-zero

with

and

, we set

Since any non-zero

can be written as

with

, and

with

, we may thus compute

The lazy approach is very convenient as long as we only need a modest number of terms. For high order expansions, the relaxed (or online) approach is more efficient [13].

Assume now that

is an effective field and that

is an effective ordered subfield of

. In the case of iterated series in

, the lazy approach raises the problem of infinite cancellations: assume that we wish to subtract

using the lazy approach. Then the successive terms of the result are

. Due to this infinite cancellation, we never reach the first term

of the result.

In order to circumvent this difficulty, assume that we are given an effective subfield

such that

. We will call

an ambient field if for any

with

, when regarding

as a series in

, we have

for all

and

In the example (2) we may then take

, after which expansion with respect to

yields

and the coefficients

are all in

. In particular, we may detect the infinite cancellation in the first term using the zero test in

In this paper, we adopted the framework of grid-based series in order to use some of the results from [14]. However, the results from this book and the present paper can be adapted mutatis mutandis to so called steady series.

We say that a subset

is steady if

is either finite or

with

and

. It was shown by Levi-Civita [21] that the set

of series

with steady support forms a field. An example of such a steady series

that is not grid-based is

The field of iterated steady series is simply

. In fact, the framework of steady series would have been slightly better for the present paper, since it is the most natural setting for lazy power series expansions. Furthermore, we have seen that a series in

is not necessarily grid-based, so extra efforts are sometimes required to prove this, whenever this indeed is the case.

Even more generally, Hahn showed that the set

of series

with well-ordered support also forms a field. In this setting, we naturally have

. An example of a well-ordered series that is not steady is

, which is a natural solution of the equation

. However, this kind of series is more problematic from an algorithmic point of view, since the order type of the support of

. In particular, expressions like

give rise to infinite cancellations as in (2), but with no easy fix; see also [9].

3Transseries

Let

be a formal variable that we think of as being infinitely large. Given

, let

denote the

-fold iterated logarithm. A transbasis is a tuple

with the following properties:

In TB2, we understand that

consists of the multiplicative group of formal exponentials

with

and

. Accordingly, in TB3, we have written

for the series

with

We may always insert further iterated logarithms into

whenever needed. More precisely, the tuple

with

is again a transbasis. In the extension

, TB3 can be strengthened to

where

is a transbasis. If

is large, then the expression

becomes very large, which is not convenient. There are various other types of transbasis, for which

may directly be included in the transbasis instead of

. In this paper, we will ignore such “optimizations” and refer to [14, Section 4.4] for more details on alternative definitions.

A grid-based transseries is an element of

for some transbasis

. It turns out that the grid-based transseries form a field

(modulo natural identifications when varying

). This is not directly obvious from our “definition”, which depends on the underlying transbasis

. Usually, one first defines the field of transseries

in a more conceptual manner and then proves that any transseries can be expanded with respect to a transbasis: see [14, Chapter 4 and Section 4.4]. However, in this paper, we will always manipulate transseries via transbasis, so our more computational “definition” will be more direct and convenient.

Grid-based transseries were first considered by Écalle in [7]. For constructions of fields of transseries with well-ordered support, we refer to [1, Appendix A] or [4, 10].

Consider a transbasis

with

. Then we have the natural derivation

, with

for all

. This derivation extends by induction on

: assuming that we defined

, we can in particular compute

. Now given

, we take

, then it can be shown that

. This is due to the fact that, for a suitable notion of infinite summation, we have

Assuming that

all belong to

, it follows that

is also closed under the usual differentiation with respect to

. In addition, for

, we have the derivation

with

. Given

, it is shown in [14, Section 5.1] that

Given

, the formula (4) implies

, since

. For any

, it follows that

. If

has dominant monomial

with

, this also yields

, whence

. For all

, we thus obtain

Let

be an effective ordered subfield of

and let

be an ambient field. We call

a differential ambient field if

and

is effectively closed under

. Differentiation can be implemented in a lazy manner: given a non-zero

with

(when regarded as a lazy series in

), we may take

We already noted that

is a transbasis for

. Moreover,

is again a differential ambient field for

. Indeed,

and the lazy algorithms for the field operations allow us to compute the iterated coefficients of any transseries in the field generated by

4Linear differential equations

For the rest of this paper, let

be an effective ordered subfield of

, let

be a transbasis, and let

be a differential ambient field. We denote by

the field of grid-based transseries.

Given

and

, we write

for the unique differential operator in

with

for all

, and we let

. We also denote by

the integer such that

and

Proof. The statements are rephrasings of [14, Theorem 7.17] and its corollaries.

In (d), the unique solution

is called the distinguished solution of

and we denote it by

. The operator

is linear and even preserves infinite summation [14, Section 7.4].

Given

, let

. We say that

is effectively linearly closed if

for every

and if we have an algorithm to compute

. In order to make

effectively linearly closed, we need to consider sequences of extensions

by distinguished solutions

of linear differential equations. The main difficulty concerns the design of a zero-test on such an extension

. In this subsection, we will start by showing how to expand distinguished solutions with respect to

, assuming that

is effectively linearly closed.

So consider a linear differential operator

with

. Note that we regard

as an operator in

instead of

, for convenience. We define

, where

stands for the valuation with respect to

Now let

. If

, then

, so assume that

and let

be the first term of its expansion in

. In order to compute the expansion of

, we may assume without loss of generality that

and decompose

with

and

with

. We may now expand

in a lazy manner as follows:

Here we note that

, whence

using our assumption that

is effectively linearly closed.

We extend the classical notion of indicial polynomials [18] to linear differential operators with transseries coefficients. Let

with

still be a linear differential operator in

. We define the indicial polynomial of

. (If

, then

, but this does not hold in general.)

Proposition 6. Let and with . If , then must be a root of the indicial polynomial .

Proof. First note that

can be obtained from

by substituting

for

. In particular,

. Then writing

, we have

. Applying (6) to

gives

for

. Therefore,

. Then rewrite

. Applying (6) to

yields

and thus

. Hence once

, we must have

Combining Theorem 5 and Proposition 6, if

and

are two distinct solutions to

, then

must be a root of the indicial polynomial

5Quasi-linear differential equations

Consider a differential polynomial

of order

and total degree

. We may also write

with

. We define

and

. We may also decompose

, where

regroups all homogeneous terms of total degree

, for

Given

, we write

and

for the unique differential polynomial in

with

and

for all

, respectively. From (7), we get

In other words, if

, then

, so in particular

. If

is homogeneous of degree

and

, then one also has

For details about these elementary definitions and properties, see [14, Sections 8.1, 8.2].

is said to be quasi-linear if

is quasi-linear [14, Section 8.5]. If

and (11) is quasi-linear, then so is the equation

, by (9). Consequently, if

and (12) is quasi-linear, then so is

Assume that (12) has a solution

and let

be such that

. Then the solution

is said to be distinguished if

for all

with

Theorem 8. Any quasi-linear differential equation (12) has a unique distinguished solution in , where . The uniqueness persists when replacing by an even larger transbasis.

Remark 9. With the above notation, given another solution

of (12) in

, the difference

satisfies the quasi-linear equation

. Then

since otherwise

. By Proposition 6, the valuation

must be a root of the indicial polynomial of

, when regarding

as an operator in

. This remark even goes through for complex solutions

of (12).

Consider a normalized quasi-linear differential equation (11), where

and

. Assume that

and

have been extended such that the distinguished solution

of (11) lies in

. The aim of this subsection is to compute the expansion

with respect to

We first decompose

, where

and

is such that

. It is readily checked that

is the distinguished solution of the equation

. We will assume that we already know how to compute this solution

and that

. As in Section 4.2, we will also assume that

is effectively linearly closed.

Now consider

and decompose it as

, where

with

and

with

and

. Note that we now write

and

with respect to

instead of

, which does not change their valuation with respect to

. We already saw in Section 4.2 how to compute

. This allows us to lazily compute

using the formula

The dependency of the right-hand side on

is legit in the lazy expansion paradigm, as long as the coefficient of

only depends on coefficients of

with

. By construction, this is the case here.

Example 10. Following from Example 7, let us compute the expansion of the distinguished solution

to the quasi-linear equation

. Decomposing

, we have

. The distinguished solution of

, so

and

. We now write

Then we compute

using

, where

. By (8), we have

. Combining

, we have

and

with

. Decompose

with

and

. Then we have

. Therefore,

6General algebraic differential equations

We first recall the basic notion of Newton degree and several related properties. Consider the extension

with derivations

with

for

. Then any

can be rewritten as an element

, which also corresponds to the

-fold upward shifting from [14, Section 8.2.3]; see also [1, page 293]. By [14, Theorem 8.6] and its subsequent remark, there exist a unique polynomial

and integer

such that

for all sufficiently large

. We call

the differential Newton polynomial for

. For a general monomial

, the Newton degree of the asymptotic differential equation

is defined to be the largest possible degree of

for all

such that

. In fact, the equation (13) is quasi-linear if and only if its Newton degree is one. The following theorem shows that Newton degree plays a crucial role in determining a lower bound on the number of the solutions to (13) in

Theorem 11. [11, Theorem 35] If the asymptotic algebraic differential equation (13) is of Newton degree , then (13) has at least solutions in when counting with multiplicities, provided that is sufficiently large.

Note that we can always assume that

in the equation (13) by replacing

with

In the sequel, we will therefore only consider the equation

Theorem 12. Let be such that . Then the asymptotic differential equation (14) has a solution in , provided that is sufficiently large.

Lemma 13. Let . Then if and only if the Newton degree of the equation (14) is non-zero.

Proof. If

, then (7) implies that (14) cannot have any solutions in

. Theorem 11 then implies that the Newton degree of (14) must vanish. Conversely, assume that

and let

-fold upward shifting of

as above. Let

and

stand for the dominant monomials of

and

, respectively. Since

for some invertible

with

, one may verify that

. Since

, we have

for some

. Consequently,

, whence

. Taking

sufficiently large such that

, it follows that

At first sight, it may seem that the mere resolution of quasi-linear differential equations is far off from solving general algebraic differential equations. But in fact, it is key the to the resolution of more general equations, due to the following consequence of [14, Section 8.7]:

Theorem 14. Let be a differential subfield of for the derivation , in which any equation or with has a non-zero solution in . Assume also that every quasi-linear differential equation with coefficients in has a solution in . Then any root in of a differential polynomial in must be in .

The equations

and

have

and

as their general solutions, so in order to apply the theorem, it is important that we know how to compute exponentials and logarithms of elements in

and

, respectively, while extending

if necessary. For this, we will use the same technique as in [23], but we actually only need to compute exponentials and logarithms up to constant factors. Moreover, due to the second condition in the theorem, we will assume that we know how to solve quasi-linear equations.

We have seen at the end of Section 3.4 how to extend

with

, after which

. If

, then this may require the extension of the constant field

with

, but we may always assume

if we just wish to integrate

. Finally, the function

is the distinguished (and actually unique) solution of the quasi-linear differential equation

Let

. As long as

for some

, we may write

and continue with

in the role of

. This leads to a decomposition

where

, and either

and

, or

and

, or

and

. If

, then similar arguments as in Section 3.4 show that

is again a transbasis and

a differential ambient field that contains

. After this extension (if necessary), we have

, then this may require the extension of the constant field

with

, but we may assume

if we just wish to compute a non-zero solution of

. We have

, where

is the distinguished (and actually unique) solution of the quasi-linear equation

Example 15. Following Example 10, we will expand

with

. First decompose

, where

and

. Then extend the transbasis

. For

, consider the distinguished solution

of the quasi-linear equation

, where

7The new algorithm for zero testing

Consider the admissible ranking

with

whenever

. The leader of a differential polynomial

is the highest variable

occurring in

when regarding

as a polynomial in

. We will denote it by

. Considering

as a polynomial in

, the leading coefficient

is called the initial of

and

its separant; we also define

. If

has degree

, then the pair

is called the Ritt rank of

and such pairs are ordered lexicographically. We understand that

for polynomials

Given

, we say that

is reducible with respect to

if there exists an

such that

and

. The process of Ritt reduction provides us with a relation of the form

Assume that we are given a grid-based transseries

such that

and a differential polynomial

. Let

be such that

. Note that we have

. We first present a criterion for the existence of a root of

that is sufficiently close to

Now assume that

is quasi-linear and let

be a solution of it. Let

be the indicial polynomial of

, considered as an operator with respect to

. We define

to be the largest root of

. If no such root exists, then we set

Let us show now that there always exists a threshold

such that for any

and any

with

and

, we have

. The smallest such

will be denoted by

and we call it the root separation of

Proposition 17. Let such that is quasi-linear. Assume that is a solution of this equation. Then

Proof. Consider a root

with

and

. Then Remark 9 implies that

is a root of

. Consequently

Consider a quasi-linear differential equation

with

and assume that its distinguished solution

belongs to

. Given

, we will now present an algorithm to check whether

simultaneously vanish at

. By induction, we suppose that a zero test on

has been given. In particular, one can test whether the coefficients of

with respect to

are zero and thus compute the valuation of

Algorithm ZeroTest

Input: , ordered by non-decreasing Ritt rank

Output: true if and false otherwise

1	If then return false
2	If then return
3	If then return
4	If then return
5	Let
6	Return the result of the test

Proof. In steps 2, 3, and 4, the Ritt rank of the first argument of

always strictly decreases; this proves the termination of the algorithm. Furthermore, if one of the tests in steps 2, 3, or 4 succeeds, then the algorithm is clearly correct. In step 1, note that we assumed that

as an element of

. So if

, then

Assume now that we reach step 5. By construction, this means that

and

for all

. In particular, Ritt reduction of

yields a relation

where

and

. If

, then we clearly have

, so assume that

. Applying Proposition 16, we obtain a grid-based transseries

such that

and

, for some

. Using (7), it follows that

Now (16) implies

and thus

. From (17), we in particular get

and

. Hence evaluating (15) at

yields

. Applying Proposition 17 to

, we obtain

. Since

, we conclude that

. From

, Ritt reduction of

also yields

for all

Theorem 18. Let be a differential ambient field (which comes with a zero test, by assumption). Let be a differential polynomial. If is a quasi-linear equation with a distinguished solution , then is again a differential ambient field.

Proof. Our zero test on

trivially extends to the quotient field

since a fraction vanishes if and only if its numerator does. We may use the algorithms from Sections 2.4, 3.4, and 5.3 to compute expansions of elements in

Following from Examples 7, 10 and 15, consider the distinguished transseries solution

and let

i.e.,

is a real branch of the Lambert function at infinity [3]. To this end, it is enough to verify that

Now we apply ZeroTest algorithm to

and

over

. Since

, we have

and thus the algorithm proceeds to step 4. Ritt reduction yields

Since

is a root of

, we obtain

, leading the algorithm to step 5. Writing

, we have

, and thus

. Hence, we take

. Since

, we only need to test whether

in the final step 6:

As a result, we finally obtain that

is a root of

and thus show that

is a real branch of the Lambert

function.

Bibliography

[1]: M. Aschenbrenner, L. van den Dries, and J. van der Hoeven. Asymptotic Differential Algebra and Model Theory of Transseries. Number 195 in Annals of Mathematics studies. Princeton University Press, 2017.
[2]: F. Boulier. Étude et implantation de quelques algorithmes en algèbre différentielle. PhD thesis, University of Lille I, 1994.
[3]: R. M. Corless, G. H. Gonnet, D. E. G. Hare, D. J. Jeffrey, and D. E. Knuth. On the Lambert function. Adv. Comput. Math., 5(4):329–359, 1996.
[4]: B. I. Dahn and P. Göring. Notes on exponential-logarithmic terms. Fundamenta Mathematicae, 127:45–50, 1986.
[5]: J. Denef and L. Lipshitz. Power series solutions of algebraic differential equations. Math. Ann., 267:213–238, 1984.
[6]: J. Denef and L. Lipshitz. Decision problems for differential equations. The Journ. of Symb. Logic, 54(3):941–950, 1989.
[7]: J. Écalle. Introduction aux fonctions analysables et preuve constructive de la conjecture de Dulac. Hermann, collection: Actualités mathématiques, 1992.
[8]: 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.
[9]: J. van der Hoeven. Outils effectifs en asymptotique et applications. Technical Report LIX/RR/94/09, LIX, École polytechnique, France, 1994.
[10]: J. van der Hoeven. Automatic asymptotics. PhD thesis, École polytechnique, Palaiseau, France, 1997.
[11]: J. van der Hoeven. Complex transseries solutions to algebraic differential equations. Technical Report 2001-34, Univ. d'Orsay, 2001.
[12]: J. van der Hoeven. A new zero-test for formal power series. In Teo Mora, editor, Proc. ISSAC '02, pages 117–122. Lille, France, July 2002.
[13]: J. van der Hoeven. Relax, but don't be too lazy. JSC, 34:479–542, 2002.
[14]: J. van der Hoeven. Transseries and real differential algebra, volume 1888 of Lecture Notes in Mathematics. Springer-Verlag, 2006.
[15]: J. van der Hoeven. Computing with D-algebraic power series. AAECC, 30(1):17–49, 2019.
[16]: J. van der Hoeven. The Jolly Writer. Your Guide to GNU TeXmacs. Scypress, 2020.
[17]: J. van der Hoeven and J. R. Shackell. Complexity bounds for zero-test algorithms. JSC, 41:1004–1020, 2006.
[18]: E. L. Ince. Ordinary differential equations. Longmans, Green and Co., 1926. Reprinted by Dover in 1944 and 1956.
[19]: A. G. Khovanskii. Fewnomials, volume 88 of Translations of Mathematical Monographs. AMS, Providence RI, 1991.
[20]: E. R. Kolchin. Differential algebra and algebraic groups. Academic Press, New York, 1973.
[21]: T. Levi-Civita. Sugli infiniti ed infinitesimi attuali quali elimenti analitici. Atti ist. Ven., 7:1765–1815, 1893.
[22]: A. Péladan-Germa. Tests effectifs de nullité dans des extensions d'anneaux différentiels. PhD thesis, Gage, École Polytechnique, Palaiseau, France, 1997.
[23]: D. Richardson, B. Salvy, J. Shackell, and J. van der Hoeven. Expansions of exp-log functions. In Proc. ISSAC '96, pages 309–313. Zürich, Switzerland, July 1996.
[24]: R. H. Risch. Algebraic properties of elementary functions in analysis. Amer. Journ. of Math., 4(101):743–759, 1975.
[25]: J. F. Ritt. Differential algebra. Amer. Math. Soc., New York, 1950.
[26]: J. Shackell. A differential-equations approach to functional equivalence. In Proc. ISSAC '89, pages 7–10. Portland, Oregon, ACM, New York, 1989. ACM Press.
[27]: J. Shackell. Zero equivalence in function fields defined by differential equations. Proc. of the AMS, 336(1):151–172, 1993.

1Introduction

2Generalized power series

3Transseries

4Linear differential equations

5Quasi-linear differential equations

6General algebraic differential equations

7The new algorithm for zero testing

Bibliography