Differential Equations, Nested Forms and Star Products

Differential Equations, Nested Forms and Star Products

John Shackell

University of Kent at Canterbury, U.K.

Algorithms Seminar

September 9, 1997

[summary by Frédéric 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).

Abstract

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.

PART I: ASYMPTOTIC NESTED EXPANSIONS

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 l₀(x)=x and for n³0, l_n+1(x)=ln|l_n(x)|. Similarly, let e₀(x)=x and for n³0, e_n+1(x)=exp e_n(x). For n<0, define e_n=l_-n and l_n=e_-n. Then, for a Hardy field H, there is a Hardy field extension containing each of the l_n(f) and e_n(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 g^d for g>0 and dÎR. This field is denoted Ráá fññ. A computationally interesting fact is that f^D=(ln|f|)'=f'/fÎRáá fññ even when ln fÏRáá 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 x²), asymptotic equivalence up to powers (x is equivalent to x² but not to exp x). For two functions f and g in a Hardy field H and with limiting values 0, -¥ or +¥, we define f»_ng to mean that there exists a non-zero constant cÎR such that l_n(f)~ cl_n(g). Furthermore, we agree that f»_ng when both functions tend to finite non-zero limits. For each n³0, this defines an equivalence relation on H\{0}. Call g_n(f) the class of f¹0 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 g_n(f)<g_n(g) to mean l_n(f)=o(l_n(g)). For each n, this defines a total order on ¡_n( H): l_n(f)/l_n(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 g_n(f)<g_n(g); or a=±¥ and g_n(g)<g_n(f); or g_n(f)=g_n(g).

Here are a few examples:

g₀(ln x)<g₀

(

exp

(

l₂(x)²

)

<g₀(x)=g₀(x+ln x)<g₀

(

x²

)

<g₀

(

exp

(

ln(x)²

)

<g₀(exp(x)),

g₁(ln x)<g₁

(

exp

(

l₂(x)²

)

<g₁(x)=g₁(x+ln x)=g₁

(

x²

)

<g₁

(

exp

(

ln(x)²

)

<g₁(exp(x)),

g₂(ln x)=g₂

(

exp

(

l₂(x)²

)

<g₂(x)=g₂(x+ln x)=g₂

(

x²

)

=g₁

(

exp

(

ln(x)²

)

<g₂(exp(x)).

The previous equivalence relations extend known cases: g₀ is the valuation map with the usual ordering reversed; the elements of ¡₁( H) are Rosenlicht's comparability classes.

3 From g_n to g_n+1

In view of the examples above, one proves that the ~_n are coarser and coarser relations: if g_n(f)=g_n(g), then g_n+1(f)=g_n+1(g). Thus for n³0, the map g_n+1 factors through ¡_n( H): g_n+1=h_n°g_n for a surjection h_n from ¡_n( H) to ¡_n+1( H). Taking the direct limit, we get ¡_¥( H) and g_¥ such that for any k³0 and any non-zero dÎR,

(ln

x)<g

(x)=g

(

x^d

)

(

e_k

(

l_k^d(x)

)

(exp x).

On the contrary, inequalities are not always preserved by the h_n's: when g_n(f)<g_n(g), i.e., l_n(f)=o(l_n(g)), it is not always true that g_n+1(f)£g_n+1(g). For instance,

g₀

(

x^-1

)

<g₀(ln x)<g₀(x) but g₁(ln x)<g₁(x)=g₁

(

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 g₂(f) to g₂(l_p-1(x)) yields information on g₁(L_p(x)f^D(x)) where L_p(x)=1/l_p'(x)=xl₁(x)···l_p-1(x). The key idea is to restrict to functions f with infinite or zero limit at +¥ and to use L'Hôpital's rule: if f,g®0 or ±¥, f(x)/g(x)~f'(x)/g'(x). Applying this rule to l₂(f) and l_p+1(x), we obtain

l₂(f)

l_p+1(x)

ln|f|

l_p

l_p'

, and hence

L_p(x)f

(x) ~

l_p(x)l_p+1(x)

ln|f|

ln|ln|f||

Taking logarithms whenever appropriate, we then get:

if g₂(f)>g₂(l_p-1(x)) then g₁(L_pf^D)=g₁(ln f);
if g₂(f)<g₂(l_p-1(x)) then ln(L_pf^D)~-l_p+1(x);
if g₂(f)=g₂(l_p-1(x)) and l₂(f)¬ ~l_p+1(x) then g₁(L_pf^D)=g₁(l_p(x));
if l₂(f)~l_p+1(x) then g₁(L_pf^D)<g₁(l_p(x))=g₁(ln f).

4 Nested forms

For an integer m³0, reals d³0 and e>0 and a function f such that g₁(f)<g₁(l_m(x)), consider f=l_m^d(x)f(x) and g=l_m^d+e(x). Then ln(f/g)=lnf(x)-el_m+1(x) =-el_m+1(x)+o(l_m+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=e_s

(

l_m^d(x)f

)

where s,m³0, dÎR⁺ and g₁(f)<g₁(l_m(x)).

Not every function f in a Hardy field admits a nested form. In fact, if f®+¥, then either g₂(f)>g₂(e_s(x)) for all s³0; or for all m³0, there exists f_mÎRáá fññ such that f_m~l_m(x); or else f admits a partial nested form f=e_s(l_m^d(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 f_i's which either stops on a f_i for which the second case above holds, or is an infinite sequence with decreasing g₁, or contains a f_i 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 f_i's, i=0,...,n, with f₀=f, such that each f_i+1 is the function f which appears in a partial nested form of f_i and f_n=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:

e₁

(

l₂²(x)e₂

(

l₅^1/3(x)(2+o(1))

)

, and -e₁^-1

æ
ç
ç
è

l₁(x)e₂

æ
ç
ç
è

(2)^1/2

(x)(13+o(1))

ö
÷
÷
ø

As a consequence to the previous results, if f belongs to a Hardy field and ¡₁(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 ¡₁(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.

PART II: PROSPECTIVE RESULTS

6 Star products

In view of the identities ab=exp(ln a+ln b) and ab=ln(e^ae^b), we define the star products *_k by

a*_kb=e_k(l_k(a)+l_k(b))=e_k-1(l_k-1(a)l_k-1(b)), for kÎZ.

We have a*₀b=a+b, a*₁b=ab. For rÎR, we also define a^*_^k^{^r}=e_k(rl_k(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 e_k+1(0) as a neutral element and e_k(0) as a zero.

Sample expressions that involve star products are:

x*₂l₁(x)=exp(l₁(x)l₂(x)), (exp

*₂²

=exp

(

x²

)

, e^x*_-1x=ln

(

e₂(x)+e^x

)

*_-1²

=ln

(

2e^x

)

=x+ln 2, (exp

*₃²

*₂l₁(x)=e₂

(

l₁³(x)

)

*₂l₁(x) =e₁

(

e₁

(

l₁³(x)

)

l(2(x)

)

Of course, any exp-ln function can be written as an expression in the real constants and the functions e_n for nÎZ using star products *_k for kÎZ only.

The advantage of star products is their nice behaviour with the g_k's: if a and b have infinite limit at +¥, then g_k-1(a*_kb)>max{g_k-1(a),g_k-1(b)} and g_k(a*_kb)=max{g_k(a),g_k(b)}. Furthermore, taking *_k powers does not affect asymptotic relations between e_s(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

for sufficiently large y₀, {f(x,y₀)| fÎ H} is a Hardy field;
for sufficiently large x₀, {f(x₀,y)| fÎ H} is a Hardy field;
for fÎ H, lim_y®+¥f(x,y) is either identically ±¥ or else an element of a Hardy field;
for fÎ H, lim_x®+¥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 f_i(x) obtained by taking the nested expansion of f(x,y₀) for fixed y=y₀ becomes independent of y₀ for sufficiently large y₀. Thus with an assumption of well-orderedness, we obtain a first nested expansion,

f(x,y)x® +¥

~ e

s₀

æ
ç
ç
è

d₀

m₀

(x)e

±1

s₁

æ
ç
ç
è

··· e

±1

s_n

æ
ç
ç
è

d_n

m_n

(x)(f(y)+o(1))

ö
÷
÷
ø

···

ö
÷
÷
ø

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.

References

[1]: Bourbaki (N.). -- Éléments de Mathématiques, Chapter V: Fonctions d'une variable réelle (appendice), pp. 36--55. -- Hermann, Paris, 1961, second edition.

This document was translated from L^AT_EX by H^EV^EA.

PART I: ASYMPTOTIC NESTED EXPANSIONS

1 Hardy fields

2 Comparability classes

3 From gn to gn+1

4 Nested forms

5 Further expansions

PART II: PROSPECTIVE RESULTS

6 Star products

7 Partial Hardy fields

References

3 From g_n to g_n+1