Differential Equations, Nested Forms and Star Products

John Shackell

University of Kent at Canterbury, U.K.

Algorithms Seminar

September 9, 1997

[summary by Frdric Chyzak]

A properly typeset version of this document is available in postscript and in pdf.

If some fonts do not look right on your screen, this might be fixed by configuring your browser (see the documentation here).

This presentation is in two parts. First, we recall the definition of two types of asymptotic expansions known as nested form and nested expansions. This theory makes it possible to adapt the asymptotic scale to the function under expansion and is based on the theory of Hardy fields [1]. Next, we suggest a reformulation of nested forms in terms of generalized products called star products, and a prospective theory of multivariate Hardy fields called partial Hardy fields.


1   Hardy fields

From the asymptotic viewpoint, C real-valued functions do not behave as nicely as holomorphic functions. In particular, asymptotic comparisons of functions that involve the symbols O, o and ~ cannot be termwise differentiated. A simple example is provided by f(x)=x+cos x~ x, whereas f'(x) is not asymptotic to 1. In rough terms, this defect is due to allowing the functions to oscillate. A remedy to this problem is the use of Hardy fields instead of rings of functions. A construction is as follows. In order to deal with fields of functions, one first considers the ring  G of germs of  C real-valued functions at +, where two functions are identified when they agree on a neighbourhood of +. Then, a Hardy field  H is a subring of  G which is also a differential field. An example is R(x) viewed as a ring of germs with the usual derivation.

Considering fields of germs has nice consequences. A non-zero function f of a Hardy field  H is invertible with  C inverse, so that asymptotically it never vanishes, and is therefore of asymptotically constant sign. This defines a total order on  H by f<g if and only if g-f has asymptotically positive sign. The derivative f' is also of asymptotically constant sign, so that f is monotonic and tends to a limit in R=R{-,+} when x goes to +. Applying this property to the ratio f/g of two functions in  H, we obtain that either f=o(g) or f~ cg for a non-zero real constant c or g=o(f).

For f in a Hardy field  H, an elementary result is that both differential ring extensions  H(exp f) and  H(ln f) are again Hardy fields. Let l0(x)=x and for n0, ln+1(x)=ln|ln(x)|. Similarly, let e0(x)=x and for n0, en+1(x)=exp en(x). For n<0, define en=l-n and ln=e-n. Then, for a Hardy field  H, there is a Hardy field extension containing each of the ln(f) and en(f). Again for a function f in a Hardy field  H, it follows from a theorem by Rosenlicht that there exists a smallest Hardy field containing R, f, and each gd for g>0 and dR. This field is denoted R f. A computationally interesting fact is that fD=(ln|f|)'=f'/fR f even when ln fR f.

2   Comparability classes

In view of various types of expansions, we need to extend asymptotic equivalence ~ to coarser and coarser equivalences. In particular, beside asymptotic equivalence (x is equivalent to x+ln x but not to 2x), we need to consider asymptotic equivalence up to a non-zero constant factor (x is equivalent to 2x but not to x2), asymptotic equivalence up to powers (x is equivalent to x2 but not to exp x). For two functions f and g in a Hardy field  H and with limiting values 0, - or +, we define fng to mean that there exists a non-zero constant cR such that ln(f)~ cln(g). Furthermore, we agree that fng when both functions tend to finite non-zero limits. For each n0, this defines an equivalence relation on  H\{0}. Call gn(f) the class of f0 and n( H) the set of equivalence classes.

Beside this, we need to measure the accuracy of an expansion (a series in ln x is finer than a series in x). This is done by defining an order between equivalence classes. Set gn(f)<gn(g) to mean ln(f)=o(ln(g)). For each n, this defines a total order on n( H): ln(f)/ln(g) is in a suitable Hardy field extension of  H, so that it has a limit a in R (independent of the extension). Either a=0 and gn(f)<gn(g); or a= and gn(g)<gn(f); or gn(f)=gn(g).

Here are a few examples:
g0(ln x)<g0 ( exp ( l2(x)2 ) ) <g0(x)=g0(x+ln x)<g0 ( x2 ) <g0 ( exp ( ln(x)2 ) ) <g0(exp(x)),
g1(ln x)<g1 ( exp ( l2(x)2 ) ) <g1(x)=g1(x+ln x)=g1 ( x2 ) <g1 ( exp ( ln(x)2 ) ) <g1(exp(x)),
g2(ln x)=g2 ( exp ( l2(x)2 ) ) <g2(x)=g2(x+ln x)=g2 ( x2 ) =g1 ( exp ( ln(x)2 ) ) <g2(exp(x)).
The previous equivalence relations extend known cases: g0 is the valuation map with the usual ordering reversed; the elements of 1( H) are Rosenlicht's comparability classes.

3   From gn to gn+1

In view of the examples above, one proves that the ~n are coarser and coarser relations: if gn(f)=gn(g), then gn+1(f)=gn+1(g). Thus for n0, the map gn+1 factors through n( H): gn+1=hngn for a surjection hn from n( H) to n+1( H). Taking the direct limit, we get ( H) and g such that for any k0 and any non-zero dR,
(ln x)<g
( xd ) =g
( ek ( lkd(x) ) ) <g
(exp x).

On the contrary, inequalities are not always preserved by the hn's: when gn(f)<gn(g), i.e., ln(f)=o(ln(g)), it is not always true that gn+1(f)gn+1(g). For instance,
g0 ( x-1 ) <g0(ln x)<g0(x)    but     g1(ln x)<g1(x)=g1 ( x-1 ) .
However, the property is valid when comparing functions that are infinite at +, as shown by the examples of the previous section.

On the other hand, comparing g2(f) to g2(lp-1(x)) yields information on g1(Lp(x)fD(x)) where Lp(x)=1/lp'(x)=xl1(x)lp-1(x). The key idea is to restrict to functions f with infinite or zero limit at + and to use L'Hpital's rule: if f,g0 or , f(x)/g(x)~f'(x)/g'(x). Applying this rule to l2(f) and lp+1(x), we obtain
,     and hence      Lp(x)f
(x) ~
Taking logarithms whenever appropriate, we then get:
  1. if g2(f)>g2(lp-1(x)) then g1(LpfD)=g1(ln f);
  2. if g2(f)<g2(lp-1(x)) then ln(LpfD)~-lp+1(x);
  3. if g2(f)=g2(lp-1(x)) and l2(f) ~lp+1(x) then g1(LpfD)=g1(lp(x));
  4. if l2(f)~lp+1(x) then g1(LpfD)<g1(lp(x))=g1(ln f).

4   Nested forms

For an integer m0, reals d0 and e>0 and a function f such that g1(f)<g1(lm(x)), consider f=lmd(x)f(x) and g=lmd+e(x). Then ln(f/g)=lnf(x)-elm+1(x) =-elm+1(x)+o(lm+1(x)) is negative infinite at +. Thus f=o(g). If similarly e<0, g=o(f). In view of the previous relations, we define a partial nested form for a function f that is infinite at + as an expression of the form
f=es ( lmd(x)f )     where s,m0, dR+ and g1(f)<g1(lm(x)).

Not every function f in a Hardy field admits a nested form. In fact, if f+, then either g2(f)>g2(es(x)) for all s0; or for all m0, there exists fmR f such that fm~lm(x); or else f admits a partial nested form f=es(lmd(x)f). The first two cases are strange situations in which, for example, f cannot satisfy an algebraic differential equation over R. In the third case, R f contains an element asymptotic to f. So the previous result applies to one of f and the function f may in turn admit a partial nested form. Continuing in this way, we produce a sequence of fi's which either stops on a fi for which the second case above holds, or is an infinite sequence with decreasing g1, or contains a fi asymptotic to a non-zero constant A.

This gives a recursive definition of a nested form: a function f has a nested form if there exists a finite sequence of fi's, i=0,...,n, with f0=f, such that each fi+1 is the function f which appears in a partial nested form of fi and fn=A+o(1) for a non-zero real A. (A few other technical constraints are added to ensure the uniqueness of the nested form of a function, in the case of existence.) For example, the following are two nested forms:
e1 ( l22(x)e2 ( l51/3(x)(2+o(1)) ) ) ,     and     -e1-1




As a consequence to the previous results, if f belongs to a Hardy field and 1(R f) is well ordered, then f has a nested form. In particular, when f satisfies an algebraic differential equation over R and belongs to a Hardy field, then 1(R f) is finite, with cardinality bounded by the order of the differential equation. It follows that only finitely many nested forms are possible for such solutions, and that those possible forms can be listed.

5   Further expansions

Nested forms only give a certain amount of asymptotic information. In particular, nothing is known about the o(1). In certain cases, a possibility is to give a nested form representation for this o(1), and continue recursively. We then get nested expansions, which extend asymptotic expansions, with no presumption of convergence. Nested expansions are guaranteed to exist for solutions of algebraic differential equations in a Hardy field and yield a unique representation. In particular, nested expansions can be calculated for exp-ln functions (modulo an oracle for constants); and for Liouvillian functions, although there is difficulty specifying which integral or algebraic function is under consideration. There are also known algorithms to add and multiply nested expansions, but this may be awkward. On the other hand the functional inverse of a nested expansion can be easily computed by an algorithm due to Salvy and Shackell.


6   Star products

In view of the identities ab=exp(ln a+ln b) and ab=ln(eaeb), we define the star products *k by
a*kb=ek(lk(a)+lk(b))=ek-1(lk-1(a)lk-1(b)),     for kZ.
We have a*0b=a+b, a*1b=ab. For rR, we also define a*kr=ek(rlk(a)). These definitions yield properties which give star products their name: each *k is commutative and associative; *k+1 is left and right distributive over *k; *k+1 admits ek+1(0) as a neutral element and ek(0) as a zero.

Sample expressions that involve star products are:
x*2l1(x)=exp(l1(x)l2(x)),     (exp x)
=exp ( x2 ) ,     ex*-1x=ln ( e2(x)+ex ) ,
=ln ( 2ex ) =x+ln 2,     (exp x)
*2l1(x)=e2 ( l13(x) ) *2l1(x) =e1 ( e1 ( l13(x) ) l(2(x) ) .
Of course, any exp-ln function can be written as an expression in the real constants and the functions en for nZ using star products *k for kZ only.

The advantage of star products is their nice behaviour with the gk's: if a and b have infinite limit at +, then gk-1(a*kb)>max{gk-1(a),gk-1(b)} and gk(a*kb)=max{gk(a),gk(b)}. Furthermore, taking *k powers does not affect asymptotic relations between es(x)'s. In view of these results, we expect to find a better presentation of nested expansions in terms of star products and hope for simpler algorithms to deal with nested expansions.

7   Partial Hardy fields

We say that a ring  H of functions of two variables x and y is a partial Hardy field if
  1. for sufficiently large y0, {f(x,y0)| f H} is a Hardy field;
  2. for sufficiently large x0, {f(x0,y)| f H} is a Hardy field;
  3. for f H, limy+f(x,y) is either identically  or else an element of a Hardy field;
  4. for f H, limx+f(x,y) is either identically  or else an element of a Hardy field.
The point of this definition is to allow for multivariate nested expansions.

Let f(x,y) be a function in a partial Hardy field. Provided R f is a partial Hardy field, the sequence of fi(x) obtained by taking the nested expansion of f(x,y0) for fixed y=y0 becomes independent of y0 for sufficiently large y0. Thus with an assumption of well-orderedness, we obtain a first nested expansion,
f(x,y)x + ~ e




where by point (4) of the definition, f belongs to a Hardy field. Now, with reasonable assumptions, f admits a nested form.

Once again, if f satisfies an algebraic partial differential equation, there is a limitation on the nested forms allowed to occur. However, a complication is that solutions of PDE's contain arbitrary functions, which can be set by specifying the limiting behaviour of f in one direction.


Bourbaki (N.). -- lments de Mathmatiques, Chapter V: Fonctions d'une variable relle (appendice), pp. 36--55. -- Hermann, Paris, 1961, second edition.

This document was translated from LATEX by HEVEA.