Asymptotics of Implicit Functions and Computer Algebra

Asymptotics of Implicit Functions and Computer Algebra

Bruno Salvy

Inria Rocquencourt

Algorithms Seminar

September 9, 1996

[summary by Joris Van der Hoeven]

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

We describe several algorithms for the asymptotic inversion of functions, from the computer algebra viewpoint. We start with some classical results, such as the inversion theorem of Lagrange. We next consider functions which can only be expanded in more complicated asymptotic scales. Finally, we briefly discuss the problem of finding the asymptotic behaviour of implicit functions.

1 Introduction

Let f be a sufficiently regular function which admits a functional inverse f^inv in the neighbourhood of some point. One often encounters the problem of determining the asymptotic behaviour of f^inv in terms of the asymptotics of f. For instance, this problem arises systematically when computing integral transforms by the saddle-point method. If the function admits a power series expansion near the point of interest, then Lagrange's inversion theorem can be used, or Brent and Kung's fast algorithm for power series inversion (see section 2).

However, one often has to deal with logarithmic or exponential singularities, whence a more general device for asymptotic functional inversion is needed. A first approach would be to consider more general classes of singularities of a particular form. For instance, one may consider functions which admit an asymptotic expansion of the form

f= e^x x

-a

n ³ 0

d_n x^-n (x ® ¥);

see section 3. More generally, one might consider the class of exp-log functions, i.e. functions built up from Q and x by +, -, ×, /, exp and log. A first algorithm to obtain asymptotic information about functional inverses of such functions---in the form of a so-called nested expansion---was given by Salvy and Shackell [6]; see also section 4.

An interesting more general problem than the inversion problem is to find an algorithm to determine the asymptotic behaviour of implicit functions, say the solutions of exp-log functions in two variables. A partial algorithm to determine the potential nested expansions of such functions was proposed in [7] and will be discussed in section 5.

More generally, one might require complete asymptotic expansions of the inverses of exp-log functions and solutions of implicit equations. A nice algorithm to compute complete asymptotic expansions of exp-log functions themselves was given in [4]. Notice also that extending the techniques from [4], solutions for the inversion and implicit function problems for exp-log functions were given independently in [10] and [11].

2 Classical results

Let f(y)= f₀+ f₁ y+ f₂ y²+ ··· be a power series with f₀ ¹ 0 and assume that y(x) satisfies

y= x f(y).

Then Lagrange's inversion theorem gives a formula for [xⁿ] y:

[xⁿ] y=

[y^n-1] fⁿ.

The formula can be generalized to

[xⁿ] G=

[y^n-1] G' fⁿ,

for an arbitrary power series G. If f resp. G have an analytic meaning (i.e. the power series converge, or the power series are the asymptotic expansion of some functions), then the same holds for the above formulae.

Example 1 The generating function y of Cayley trees satisfies

y= x e^y.

Hence [xⁿ] y= 1/n [y^n-1] e^ny= n^n-1/n!. Other trees can be treated in a similar way.

Assume now that we do not merely want the n-th coefficient of the inverse of a power series x(y)= y+ a₂ y²+ a₃ y³+ ···= F(y), but the first N coefficients of y(x). This problem can be reduced to the problem of functional composition by the Newton method: define the sequence y_n(x) by y₀=x and

y_n+1= y_n-

F(y_n)-x

F'(y_n)

Brent and Kung have shown that the number of correct terms doubles at each step [1]. Suitably truncating the Newton iterations then yields an inversion algorithm for power series of the same complexity as functional composition, i.e. O(M(N) (N log N)^1/2)= O((N log N)^3/2) [1].

Example 2 How to find the n-th positive root x_n of tan x= x? Looking at the graph, we see that x_n= (2n+1) p/2- u_n with u_n ® 0. Applying tan we get

(2n+1)

- u_n= tan

æ
ç
ç
è

- u_n

ö
÷
÷
ø

whence

u_n+ tan (

- u_n)

(2n+1)p

= t_n,

with t_n ® 0. Inverting the above power series, we get

x_n= p n+

p n

2 p n²

æ
ç
ç
è

3p³

ö
÷
÷
ø

n³

+ ··· .

3 Inverses of more general functions

In this section we are interested in computing the asymptotic inverse of a function which admits

e^y y

-a

D(y^-1) (d_n ¹ 0, y ® ¥)

as an asymptotic expansion, where D(y^-1)= å_{n ³ 0} d_n y^-n. In other words, we want the asymptotic solution to

e^y y

-a

D(y^-1)= x

in y. A first method [2] is to do this is to take logarithms

y= log x+ a log y- log D(y^-1), (1)

and to replace y by the right hand side in an iterative manner. This yields an expansion of the form

y » log

n ³ 0

P_n(log log x)

logⁿ x

where the P_n are polynomials.

A faster method to compute the P_n was proposed in [5]. Setting z= log log x and t= (log x)^-1, we set

y- log

x= P(z, t)=

n ³ 0

P_n(z) tⁿ.

Taking logarithms, this yields

log y= log (log x+ P)= z+ log (1+ tP).

From (1), we get

P= a z+ a log (1+ tP)- log D

æ
ç
ç
è

1+tP

ö
÷
÷
ø

In this equation z and t are decoupled. We get

P(0,t)= a log (1+ tP(0,t))- log D

æ
ç
ç
è

1+tP(0,t)

ö
÷
÷
ø

and

æ
ç
ç
è

- t

ö
÷
÷
ø

¶ P

¶ z

+ t²

¶ P

¶ t

= 1.

These two relations enable us to compute the coefficients of P efficiently.

Example 3 The number of prime numbers p(x) smaller than x satisfies

p(x) »

log x

æ
ç
ç
è

log x

log² x

+ ···

ö
÷
÷
ø

Using the above method we find the asymptotic expansion

p(n) » n log n

æ
ç
ç
è

log log n-1

log n

log log n-2

log² n

+ ···

ö
÷
÷
ø

for the n-th prime number p(n).

The above result can be extended to get asymptotic expansions for log y and e^{b y} y^gG(y^-1) [5].

4 Inversion of exp-log functions

Let f be an exp-log function (i.e. a function built up from Q and x by +, -, ×, /, exp and log), which tends to infinity for x ® ¥. We denote by exp_i resp. log_i the i-th iterate of exp resp. log. We write f <<< g, if f is of a smaller comparability class than g, i.e. (log |f|)/(log |g|) tends to 0.

In this section, we present an algorithm to compute a ``nested expansion'' for the asymptotic functional inverse of f. Such a nested expansion often (although not always) yields an asymptotic expansion of the function. In any case, the limit behaviour of a function can be determined from its nested expansion.

One first defines a nested form as being a finite sequence { (s_i, e_i, m_i, d_i, f_i) } for 1 £ i £ n. Here s_i, m_i Î N, d_i Î R, e_i= ± 1, f_i lies in a Hardy field and

f_i-1(x)= exp

e_i

s_i

(log

d_i

m_i

(x) f_i(x)),

with f_i <<< log_m_{_i} for 2 £ i £ n. We also require that

f_n has a finite limit l;
d_n ¹ 1 unless s_n=0 or m_n=0;
d_i>0 unless s_i=0.

Continuing the process of taking nested forms with f_n-l (if possible), we obtain a nested expansion.

Example 4 exp [log² x exp [(log log x)^1/2 (7+ f(x))]] is a nested form, if f(x) tends to 0.

John Shackell was the first to prove in [8] that any exp-log function admits a nested form, and even a nested expansion. Nested forms and expansions are particularly well suited to the purpose of functional inversion. The algorithm proceeds as follows:

Algorithm

An exp-log function f tending to infinity is given at input, and we compute a nested expansion of its functional inverse at infinity.

Rewrite f as a NF
f(y)= exp_s (log_m^d (y) f₁(y))= x.
Invert
y= exp_m (log_s^1/D x g₁(x)). (E)
Iterate
- Compute NF(g_i)= exp_s_{_i}^e_ⁱ (log_m_{_i}^d_ⁱ y G_i(y)),
- Substitute (E) in log_m_{_i}^d_ⁱ y,
- Rewrite to get g_i+1,
until NF(g_i)= c+ e (y), with e(y) ® 0, yielding NF(y(x)).
Repeat the above procedure for e(y), whence NE(y(x)).

Example 5

f(y)= y e

log

² y e

(log log y)^1/2

= x.

Step 1: rewrite f as NF

exp

[

log² y exp [ (log₂ y)^1/2 (1+ W)]

]

with

W= log₂^-1/2 y log (1+ log

^-1 y e

-(log₂ y)^1/2

Step 2: Invert

y= exp

é
ê
ê
ë

(log x)^1/2 exp

æ
ç
ç
è

(log₂ y)^1/2 (1+W)

ö
÷
÷
ø

ù
ú
ú
û

Step 3: Iterate

(log₂ y)^1/2=

(2)^1/2

(log₂ x)^1/2

æ
ç
ç
è

1+W

2 (log₂ y)^1/2

ö
÷
÷
ø

-1/2

whence the nested form for y:

y= exp

é
ê
ê
ë

(log x)^1/2 exp

æ
ç
ç
è

2(2)^1/2

(log₂ x)^1/2 (1+ e (x))

ö
÷
÷
ø

ù
ú
ú
û

Step 4: Repeat

y= exp

é
ê
ê
ê
ê
ê
ê
ë

(log x)^1/2

2(2)^1/2

log₂ x

· e^1/8 ·

æ
ç
ç
è

32(2)^1/2

log₂^-1/2 x+

4096

log₂^-1 x+

383

393216 (2)^1/2

log₂^-3/2 x+ ···

ö
÷
÷
ø

ù
ú
ú
û

5 Asymptotic expansion of implicit functions

Assume now that H is an exp-log function in two variables x and y. By theorems of Khovanskii and van den Dries [3, 9], if y(x) is a real solution of H(x,y)=0 (for x ® ¥), then (the germ of) y(x) belongs to a Hardy field. In particular, y(x) does not present any oscillatory phenomena at infinity. As a corollary [7], y(x) has a nested form and even a nested expansion. A question is how to compute all possible nested expansions of such solutions.

The idea from the algorithm in [7] is to compute the asymptotic behaviour for H(x,y) for all possible asymptotic behaviours of x and y. In order to do so, one often has to distinguish several number of cases, but always finitely many, depending on the values of x and y. The strategy is best illustrated on an example.

Example 6

H(x,y)=

exp (x²+ 2 x log² x+ y)

exp (x²+x log² x+y)

-1.

Three cases are distinguished:

H ~

ì
í
î

1,	if y ® -¥ and x <<< y;
?,	if log \|y\| ~ 2 log x;
exp (x log² x),	otherwise.

Since H=0, we find that log |y| ~ 2 log x, whence y ~ -x². Continuing the process, we find

y= -x²- 2xlog² x+

-xlog² x

x²

-2xlog² x

2x²

+ ··· .

We remark that it is not claimed that the obtained nested expansions are indeed nested expansions of actual solutions. For a solution to this problem, we refer to [11].

References

[1]: Brent (R. P.) and Kung (H. T.). -- Fast algorithms for manipulating formal power series. Journal of the ACM, vol. 25, 1978, pp. 581--595.
[2]: De Bruijn (N. G.). -- Asymptotic Methods in Analysis. -- Dover, 1981. A reprint of the third North Holland edition, 1970 (first edition, 1958).
[3]: Khovanskii (A. G.). -- Fewnomials and Pfaff manifolds. In Proceedings of the International Congress of Mathematicians, pp. 549--564. -- 1983.
[4]: Richardson (Dan), Salvy (Bruno), Shackell (John), and Van der Hoeven (Joris). -- Asymptotic expansions of exp-log functions. In Lakshman (Y. N.) (editor), Symbolic and Algebraic Computation. pp. 309--313. -- New York, 1996. Proceedings ISSAC'96. Zürich.
[5]: Salvy (Bruno). -- Fast computation of some asymptotic functional inverses. Journal of Symbolic Computation, vol. 17, 1994, pp. 227--236.
[6]: Salvy (Bruno) and Shackell (John). -- Asymptotic expansions of functional inverses. In Wang (Paul S.) (editor), Symbolic and Algebraic Computation. pp. 130--137. -- New York, 1992. Proceedings of ISSAC'92, Berkeley.
[7]: Salvy (Bruno) and Shackell (John). -- Symbolic Asymptotics: Functions of Two Variables, Implicit Functions. -- Research Report n°2883, Institut National de Recherche en Informatique et en Automatique, 1996. Submitted to the Journal of Symbolic Computation.
[8]: Shackell (John). -- Growth estimates for exp-log functions. Journal of Symbolic Computation, vol. 10, n°6, December 1990, pp. 611--632.
[9]: Van den Dries (Lou). -- Analytic Hardy fields and exponential curves in the real plane. American Journal of Mathematics, vol. 106, 1984, pp. 149--167.
[10]: van der Hoeven (J.). -- General algorithms in asymptotics II: Common operations. -- Technical Report n°LIX/RR/94/10, LIX, École polytechnique, France, 1994.
[11]: Van der Hoeven (Joris). -- Asymptotique Automatique. -- PhD thesis, École polytechnique, Palaiseau, France, 1997.

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