LINEBURG

minimum value, then f (z) is pathological, and the standard saddle point method will not be

applicable. For functions f (z) with nonnegative coe¬cients, it is easy to show uniqueness of

the minimizing r, as was already discussed in Section 8.1.) Cauchy™s formula (10.6) is then

applied with the contour |z| = r0 . The reason for this choice is that for many functions, on

this contour the integrand is large only near z = r 0 , the contributions from the region near

z = r0 do not cancel each other, and remaining regions contribute little. This is in contrast

to the behavior of the integrand on other contours. By Cauchy™s theorem, any simple closed

contour enclosing the origin gives the correct answer. However, on most of them the integrand

is large, and there is so much cancellation that it is hard to derive any estimates. The circle

going through the saddle point, on the other hand, yields an integral that can be controlled

well by techniques related to Laplace™s method and the method of stationary phase that were

mentioned in Section 5.5. We illustrate with an example, which is a totally self-contained

application of the saddle point method to an extremely simple situation.

Example 12.1. Stirling™s formula. We estimate (n!) ’1 = [z n ] exp(z). The saddle point,

+ that minimizes r ’n exp(r), which is clearly

according to our de¬nition above, is that r ∈ ¡

r = n. Consider the contour |z| = n, and set z = n exp(iθ), ’π ¤ θ ¤ π. Then

1 exp(z)

[z n ] exp(z) = dz

z n+1

2πi |z|=n

π

1 ’n

exp(neiθ ’ niθ)dθ .

= n (12.2)

2π ’π

Since | exp(z)| = exp(Re(z)), the absolute value of the integrand in (12.2) is n ’n exp(n cos θ),

which is maximized for θ = 0. Now

eiθ = cos θ + i sin θ = 1 ’ θ 2 /2 + iθ + O(|θ|3 ) ,

so for any θ0 ∈ (0, π),

θ0 θ0

’n iθ

n’n exp(n ’ nθ 2 /2 + O(n|θ|3 ))dθ .

n exp(ne ’ niθ)dθ = (12.3)

’θ0 ’θ0

116

(It is the cancellation of the niθ term coming from ne iθ and the ’niθ term that came from

change of variables in z ’n that is primarily responsible for the success of the saddle point

method.) The O(n|θ|3 ) term in (12.3) could cause problems if it became too large, so we will

select θ0 = n’2/5 , so that n|θ|3 ¤ n’1/5 for |θ| ¤ θ0 , and therefore

exp(n ’ nθ 2 /2 + O(n|θ|3 )) = exp(n ’ nθ 2 /2)(1 + O(n’1/5 )) . (12.4)

Hence

θ0 θ

’n iθ ’1/5 ’n n

exp(’nθ 2 /2)dθ .

n exp(ne ’ niθ)dθ = (1 + O(n ))n e

’θ0 ’θ0

But

θ0 ∞ ∞

2 2

exp(’nθ 2 /2)dθ

exp(’nθ /2)dθ = exp(’nθ /2)dθ ’ 2

’θ0 ’∞ θ0

= (2π/n)1/2 ’ O(exp(’n1/5 /2)) ,

so

θ0

n’n exp(neiθ ’ niθ)dθ = (1 + O(n’1/5 ))(2π/n)1/2 n’n en . (12.5)

’θ0

On the other hand, for θ0 < |θ| ¤ π,

2 4

cos θ ¤ cos θ0 = 1 ’ θ0 /2 + O(θ0 ) ,

so

n cos θ ¤ n ’ n1/5 /2 + O(n’3/5 ) ,

and therefore for large n

π

n’n exp(neiθ ’ niθ)dθ ¤ n’n exp(n ’ n1/5 /3) ,

θ0

and similarly for the integral from ’π to ’θ 0 . Combining all these estimates we therefore ¬nd

that

(n!)’1 = [z n ] exp(z) = (1 + O(n’1/5 ))(2πn)’1/2 n’n en , (12.6)

which is a weak form of Stirling™s formula (4.3). (The full formula can be derived by using

more precise expansions for the integrand.)

Suppose we try to push through a similar argument using the contour |z| = 2n. This time,

instead of Eq. (12.2), we ¬nd

π

1

n

2’n n’n exp(2neiθ ’ niθ)dθ .

[z ] exp(z) = (12.7)

2π ’π

117

At θ = 0, the integrand is 2’n n’n exp(2n), which is exp(n) times as large as the value of the

integrand in (12.2). Since the two integrals do produce the same answer, and from the analysis

above we see that this answer is close to n ’n exp(n) in value, the integral in (12.7) must involve

tremendous cancellation. That is indeed what we see in the neighborhood of θ = 0. We ¬nd

that

exp(2neiθ ’ niθ) = exp(2n ’ nθ 2 + niθ + O(n|θ|3 )) , (12.8)

and the exp(niθ) term produces wild oscillations of the integrand even over small ranges of

θ. Trying to work with the integral (12.7) and proving that it equals something exponentially

smaller than the maximal value of its integrand is not a promising approach. By contrast, the

saddle point contour used to produce Eq. (12.2) gives nice behavior of the integrand, so that

it can be evaluated.

The estimates for n! obtained in Example 10.1 came from a simple application of the

saddle point method. The motivation for the choice of the contour |z| = n is provided by the

discussion at the end of the example; other choices lead to oscillating integrands that cannot

be approximated by a Gaussian, nor by any other nice function. The example above treated

only the exponential function, but it is easy to see that this phenomenon is general; a rapidly

oscillating term exp(ni±) for ± = 0 is present unless the contour passes through the saddle

point. When we do use this contour, and the Gaussian approximation is valid, we ¬nd that

for functions f (z) satisfying our assumptions we have the following estimate.

Saddle point approximation

’n

[z n ]f (z) ∼ (2πb(r0 ))’1/2 f (r0 )r0 as n ’ ∞ , (12.9)

where r0 is the saddle point (where r ’n f (r) is minimized, so that r0 f (r0 )/f (r0 ) = n)

and

2

f (r) f (r) f (r) f (r)

+ r2 ’ r2

b(r) = r =r r . (12.10)

f (r) f (r) f (r) f (r)

Example 12.2. Bell numbers. Example 5.4 showed how to estimate the Bell number B n

by elementary methods, starting with the representation (5.38). The exponential generating

function

∞

zn

B(z) = Bn (12.11)

n!

n=0

118

satis¬es

B(z) = exp(exp(z) ’ 1) ,

as can be seen from (5.38) or by other methods (cf. [81]). The saddle point occurs at that

r0 > 0 that satis¬es

r0 exp(r0 ) = n , (12.12)

and

b(r0 ) = r0 (1 + r0 ) exp(r0 ) , (12.13)

so the saddle point approximation says that as n ’ ∞,

Bn ∼ n!(2πr0 exp(r0 ))’1/2 exp(exp(r0 ) ’ 1)r0 .

2 ’n

(12.14)

The saddle point approximation can be justi¬ed even more easily than for the Stirling estimate

of n!.

The above approximation is widely applicable and extremely useful, but care has to be

exercised is applying it. This is shown by the next example.

Example 12.3. Invalid application of the saddle point method. Consider the trivial example

f (z) = (1 ’ z)’1 , so that [z n ]f (z) = 1 for all n ≥ 0. Then f (r)/f (r) = (1 ’ r)’1 , and so

the saddle point is r0 = n/(n + 1), and b(r0 ) = r0 /(1 ’ r0 )2 = n(n + 1). Therefore if the

approximation (12.9) were valid, it would give

n

1

n ’1/2

[z ]f (z) ∼ (2πn(n + 1)) (n + 1) 1 +

n

∼ (2π)’1/2 e as n’∞. (12.15)

Since (2π)’1/2 e = 1.0844 . . . = 1 = [z n ]f (z), something is wrong, and the estimate (12.9) does

not apply to this function.

The estimate (12.9) gave the wrong result in Example 12.3 because the Gaussian approxi-

mation on the saddle point method contour used so e¬ectively in Example 12.1 (and in almost

all cases where the saddle point method applies) does not hold over a su¬ciently large re-

gion for f (z) = (1 ’ z)’1 . In Example 12.1 we used without detailed explanation the choice

θ0 = n’2/5 , which gave the approximation (12.5) for |θ| ¤ θ 0 , and yet led to an estimate for the

integral over θ0 < |θ| ¤ π that was negligible. This was possible because the third order term

119

(i.e., n|θ|3 ) in Eq. (12.5) was small. When we try to imitate this approach for f (z) = (1 ’ z) ’1 ,

we fail, because the third order term is too large. Instead of ne iθ ’ niθ, we now have

1 i

’ log(1 ’ r0 eiθ ) ’ niθ = ’ log(1 ’ r0 ) ’ n(n + 1)θ 2 ’ n2 (n + 1)θ 3 + · · · . (12.16)

2 6

More fundamentally, the saddle point method fails here because the function f (z) = (1 ’ z) ’1

does not have a large enough singularity at z = 1, so that when one traverses the saddle point

contour |z| = r0 , the integrand does not drop o¬ rapidly enough for a small region near the

real axis to provide the dominant contribution.

When can one apply the saddle point approximation (12.9)? Perhaps the simplest, yet still

general, set of su¬cient conditions for the validity of (12.9) is provided by requiring that the

function f (z) be Hayman-admissible. Hayman admissibility is described in De¬nition 12.1, in

the following subsection. Generally speaking, though, for the saddle point method to apply we

need the function f (z) to have a large dominant singularity at R, so that f (r) grows at least

as fast as exp((log(R ’ r))2 ) as r ’ R’ for R < ∞, and as fast as exp((log r)2 ) as r ’ ∞

for R = ∞. The faster the growth rate, the easier it usually is to apply the method, so that

exp(1/(1 ’ z)) or exp(exp(1/(1 ’ z))) can be treated easily.

In our application of the saddle point method to exp(z) in Example 12.1 we were content

to obtain a poor error term, 1 + O(n’1/5 ), in Stirling™s formula for n!. This was done to

simplify the presentation and concentrate only on the main factors that make the saddle point

method successful. With more care devoted to the integral one can obtain the full asymptotic

expansion of n!. (Only the range |θ| ¤ θ 0 has to be considered carefully.) This is usually true

when the saddle point method is applicable.

This section provided a sketchy introduction to the saddle point method. For a much more

thorough presentation, including a discussion of the topographical view of the integrand and

the “hill-climbing” interpretation of the contour of integration, see [63].

12.2. Admissible functions

The saddle point method is a powerful and ¬‚exible tool, but in its full generality it is often

cumbersome to apply. In many situations it is possible to apply general theorems derived

using the saddle point method that give asymptotic approximations that are not the sharpest

possible, but which allow one to avoid the drudgery of applying the method step by step. The

general theorems that we present were proved by Hayman [204] and by Harris and Schoenfeld

120

[198]. We next describe the classes of functions to which these theorems apply, and then present

the estimates one obtains for them. It is not always easy to verify that these de¬nitions hold,

but it is almost always easier to do this than to apply the saddle point method from scratch.

It is worth mentioning, furthermore, that for many generating functions, there are conditions

that guarantee that they satisfy the hypotheses of the Hayman and the Harris-Schoenfeld

theorems. These conditions are discussed later in this section.

The de¬nition below is stated somewhat di¬erently than the original one in [204], but can

be shown to be equivalent to it.

De¬nition 12.1. A function

∞

fn z n

f (z) = (12.17)

n=0

is admissible in the sense of Hayman (or H-admissible) if

i) f (z) is analytic in |z| < R for some 0 < R ¤ ∞,

ii) f (z) is real for z real, |z| < R,

iii) for R0 < r < R,

max |f (z)| = f (r) , (12.18)

|z|=r

iv) for

f (r)

a(r) = r , (12.19)

f (r)

2

f (r) f (r) f (r)

+ r2 ’ r2

b(r) = ra (r) = r , (12.20)

f (r) f (r) f (r)

and for some function δ(r), de¬ned in the range R 0 < r < R to satisfy 0 < δ(r) < π, the

following three conditions hold:

f (reiθ ) ∼ f (r) exp(iθa(r) ’ θ 2 b(r)/2)

a)

as r ’ R uniformly for |θ| < δ(r), (12.21)

f (reiθ ) = o(f (r)b(r)’1/2 )

b)

as r ’ R uniformly for |θ| < δ(r), (12.22)

c) b(r) ’ ∞ as r ’ R. (12.23)

121

For H-admissible functions, Hayman [204] proved a basic result that gives the asymptotics

of the coe¬cients.

Theorem 12.1. If f (z), de¬ned by Eq. (12.17), is H-admissible in |z| < R, then

(a(r) ’ n)2

’1/2 ’n

fn = (2πb(r)) f (r)r exp ’ + o(1) (12.24)

b(r)

as r ’ R, with the o(1) term uniform in n.

If we choose r = rn to be a solution to a(rn ) = n, then we obtain from Theorem 12.1 a

simpler result. (The uniqueness of r n follows from a result of Hayman [204] which shows that

a(r) is positive increasing in some range R 1 < r < R, R1 > R0 .)

Corollary 12.1. If f (z), de¬ned by Eq. (12.17), is H-admissible in |z| < R, then

fn ∼ (2πb(rn ))’1/2 f (rn )rn as n ’ ∞ ,

’n

(12.25)

where rn is de¬ned uniquely for large n by a(r n ) = n, R0 < rn < R.

Corollary 12.1 is adequate for most situations. The advantage of Theorem 12.1 is that

b(r) 1/2 . (Note that the

it gives a uniform estimate over the approximate range |a(r) ’ n| ¤

estimate (12.24) is vacuous for |a(r) ’ n| b(r) ’1/2 ’ ∞.) Theorem 12.1 shows that the fn r n

are approximately Gaussian in the central region.

There are many direct applications of the above results.

Example 12.4. Stirling™s formula. Let f (z) = exp(z). Then f (z) is H-admissible for R = ∞;

conditions i)“iii) of De¬nition 12.1 are trivially satis¬ed, while a(r) = r, b(r) = r, so iv) also

holds for R0 = 0, δ(r) = r ’1/3 , say. Corollary 12.1 then shows that

1

∼ (2πn)’1/2 en n’n as n ’ ∞ ,

fn = (12.26)

n!

since rn = n, which gives a weak form of Stirling™s approximation to n!.

In many situations the conditions of H-admissibility are much harder to verify than for

f (z) = exp(z), and even in that case there is a little work to be done to verify that condition

iv) holds. However, many of the generating functions one encounters are built up from other,

simpler generating functions, and Hayman [204] has shown that often the resulting functions

are guaranteed to be H-admissible. We summarize some of Hayman™s results in the following

theorem.

122

Theorem 12.2. Let f (z) and g(z) be H-admissible for |z| < R ¤ ∞. Let h(z) be analytic in

|z| < R and real for real z. Let p(z) be a polynomial with real coe¬cients.

i) If the coe¬cients an of the Taylor series of exp(p(z)) are positive for all su¬ciently large

n, then exp(p(z))) is H-admissible in |z| < ∞.

ii) exp(f (z)) and f (z)g(z) are H-admissible in |z| < R.

iii) If, for some · > 0, and R1 < r < R,

max |h(z)| = O(f (r)1’· ) , (12.27)

|z|=r

then f (z) + h(z) is H-admissible in |z| < R. In particular, f (z) + p(z) is H-admissible

in |z| < R and, if the leading coe¬cient of p(z) is positive, p(f (z)) is H-admissible in

|z| < R.

Example 12.5. H-admissible functions. a) By i) Theorem 12.2, exp(z) is H-admissible, so

we immediately obtain the estimate (12.26), which yields Stirling™s formula. b) Since exp(z)

is H-admissible, part iii) of Theorem 12.2 shows that exp(z) ’ 1 is H-admissible. c) Applying

part ii) of Theorem 12.2, we next ¬nd that exp(exp(z) ’ 1) is H-admissible, which yields the

asymptotics of the Bell numbers.

Hayman™s results give only ¬rst order approximations for the coe¬cients of H-admissible

functions. In some circumstances it is desirable to obtain full asymptotic expansions. This is

possible if we impose additional restrictions on the generating function. We next state some

results of Harris and Schoenfeld [198].

De¬nition 12.2. A function f (z) de¬ned by Eq. (12.17) is HS-admissible provided it is ana-

lytic in |z| < R, 0 < R ¤ ∞, is real for real x, and satis¬es the following conditions:

Copyright Design by: Sunlight webdesign