LINEBURG

0 < d(r) < 1 ,

(12.28)

r{1 + d(r)} < R ,

and such that f (z) = 0 for |z ’ r| < rd(r).

B) If we de¬ne, for k ≥ 1,

z k (k’1)

f (z) z

A(z) = , Bk (z) = A (z), B(z) = B1 (z) , (12.29)

f (z) k! 2

123

then we have

B(r) > 0 for R0 < r < R and B1 (r) ’ ∞ as r ’ R .

C) For su¬ciently large R1 and n, there is a unique solution r = u n to

B1 (r) = n + 1, R1 < r < R . (12.30)

Let

(’1)j

’1

Cj (z, r) = Bj+2 (z) + B1 (r) . (12.31)

B(r) j+2

There exist nonnegative Dn , En , and n0 such that for n ≥ n0 ,

j

|Cj (un , un )| ¤ En Dn , j = 1, 2, . . . . (12.32)

D) As n ’ ∞,

B(un )d(un )2 ’ ∞ ,

Dn En B(un )d(un )3 ’ 0 , (12.33)

Dn d(un ) ’ 0 .

For HS-admissible functions, Harris and Schoenfeld obtain complete asymptotic expansions.

Theorem 12.3. If f (z), de¬ned by (12.17), is HS-admissible, then for any N ≥ 0,

N

’1/2

f (un )u’n ’k

fn = 2(πβn ) 1+ Fk (n)βn + O(φN (n; d)) as n ’ ∞ , (12.34)

n

k=1

where

βn = B(un ) , (12.35)

2k

“(m + k + 1 )

(’1)k 2

√

Fk (n) = γj1 (n) · · · γjm (n) , (12.36)

m!

π m=1 j1 +···+jm =2k

j1 ,...,jm ≥1

γj (n) = Cj (un , un ) , (12.37)

and

φN (n; d) = max{µ(un , d), En (Dn En βn )2N +2 } ,

’1/2

124

with

En = min(1, En ), En = max(1, En ) , (12.38)

exp(’B(r)d(r)2 )

1/2

µ(r, d) = max »(r; d)B(r) , , (12.39)

d(r)B(r)1/2

where »(r; d) is the maximum value of |f (z)/f (z)| for z on the oriented path Q(r) consisting

of the line segment from r + ird(r) to (1 ’ d(r) 2 )1/2 + ird(r) and of the circular arc from the

last point to ir to ’r.

The conditions for HS-admissibility are often hard to verify. However, there is a theorem

[311] which guarantees that they do hold for a large class of interesting functions.

Theorem 12.4. If g(z) is H-admissible, then f (z) = exp(g(z)) is HS-admissible. Further-

’N

more, the error term φN (n; d) of Theorem 12.3 is then o(βn ) as n ’ ∞ for every ¬xed

N ≥ 0.

Example 12.6. Bell numbers and HS-admissibility. Since exp(x) ’ 1 is H-admissible, as we

saw in Example 12.5, we ¬nd that exp(exp(z) ’ 1) is HS-admissible, and Theorem 12.3 yields

a complete asymptotic expansion of the Bell numbers.

Theorem 12.4 does not apply when g(z) is a polynomial. As is pointed out by Schmutz

[339], for g(z) = z 4 ’ z 3 + z 2 the function f (z) = exp(g(z)) is HS-admissible, but Theo-

rem 12.3 does not give an asymptotic expansion because the error term φ N (n; d) is too large.

Schmutz [339] has obtained necessary and su¬cient conditions for Theorem 12.3 to give an

asymptotic expansion for the coe¬cients of f (z) = exp(g(z)) when g(z) is a polynomial.

12.3. Other saddle point applications

Section 12.1 presented the basic saddle point method and discussed its range of applicabil-

ity. Section 12.2 was devoted to results derived using this method that are general and yet can

be applied in a cook-book style, without a deep understanding of the saddle point technique.

Such a cook-book approach is satisfactory in many situations. However, often one encounters

asymptotic estimation problems that are not covered by any of general results mentioned in

Section 12.2, but can be solved using the saddle point method. This section mentions sev-

eral such results of this type that illustrate the range of problems to which this method is

applicable. Additional applications will be presented in Section 15, where other techniques are

combined with the saddle point method.

125

Example 12.7. Stirling numbers. The Stirling numbers of the ¬rst kind, s(n, k), satisfy (6.5)

as well as [81]

n

s(n, k)z k = z(z ’ 1) · · · (z ’ n + 1) . (12.40)

k=0

Since (’1)n+k s(n, k) > 0, (which is re¬‚ected in the behavior of the generating function (12.40),

which grows faster along the negative real axis than along the positive one), we rewrite it as

n

(’1)n+k s(n, k)z k = z(z + 1) · · · (z + n ’ 1) . (12.41)

k=0

The function on the right-hand side behaves like a good candidate for an application of the

saddle point method. For details, see [295, 296].

The estimates mentioned in Example 12.7 are far from best possible in either the size of

the error term or (more important) in the range of validity. References for the best currently

known results about Stirling numbers of both the ¬rst and second kind are given in [363].

Some of the results in the literature are not rigorous. For example, [363] presents elegant and

uniform estimates based on an application of the saddle point method. They are likely to

be correct, but the necessary rigorous error analysis has not been performed yet, although it

seems that this should be doable. Other results, like those of [232] are obtained by methods

that there does not seem to be any hope of making rigorous in the near future. Some of the

results, though, such as the original ones of Moser and Wyman [295, 296], and the more recent

one of Wilf [378], are fully proved.

The saddle point method can be used to obtain full asymptotic expansions. These expan-

sions are usually in powers of n’1/2 when estimating [z n ]f (z), and they hardly ever converge,

but are asymptotic expansions as de¬ned by Poincar´ (as in Eq. (2.2)). The usual forms of the

e

saddle point method are incapable of providing expansions similar to the Hardy-Ramanujan-

Rademacher convergent series for the partition function p(n) (Eq. (3.1)). However, the saddle

point method can be applied to estimate p(n). There are technical di¬culties, since the gen-

erating function

∞ ∞

n

(1 ’ z k )’1

f (z) = p(n)z = (12.42)

n=0 k=1

has a large singularity at z = 1, but in addition has singularities at all other roots of

unity. The contribution of the integral for z away from 1 can be crudely estimated to be

O(n’1 exp(Cn1/2 /2)) (the last term in Eq. (1.5)). A simple estimate of the integral near z = 1

yields the asymptotic expansion of Eq. (1.6). A more careful treatment of the integral, but

126

one that follows the conventional saddle point technique, replaces the 1 + O(n ’1/2 ) term in

ck n’k/2 . To

Eq. (1.6) by an asymptotic (in the sense of Poincare, so nonconvergent) series

obtain Eq. (1.5), one needs to choose the contour of integration near z = 1 carefully and use

precise estimates of f (z) near z = 1.

De Bruijn [63] also discusses applications of the saddle point method when the saddle point

is not on the real axis, and especially when there are several saddle points that contribute

comparable amounts. This usually occurs when there are oscillations in the coe¬cients. When

the oscillations are irregular, the tricks mentioned in Section 10 of changing variables do not

work, and the contributions of the multiple saddle points have to be evaluated.

Example 12.8. Oscillating sequence. Consider the sequence a n of Examples 9.4 and 10.1.

As is shown in Example 9.4, its ordinary generating function is given by (9.39). It has an

essential singularity at z = 1, but is analytic every place else. This function is not covered by

our earlier discussion. For example, its maximal value is in general not taken on the positive

real axis. It can be shown that the Cauchy integral has two saddle points, at approximately

z = 1’(2n)’1 ±in’1/2 (1’(4n)’1 )1/2 . Evaluating [z n ]f (z) by using Cauchy™s theorem with the

contour chosen to pass through the two points in the correct way yields the estimate (9.38).

In applying the saddle point method, a general principle is that multiplying a generating

function f (z) with dominant singularity at R by another function g(z) which is analytic in

|z| < R and has much lower growth rate near z = R yields a function f (z)g(z) whose saddle

point is close to that of f (z). Usually one can obtain a relation of the form

[z n ](f (z)g(z)) ∼ g(r0 )([z n ]f (z)) , (12.43)

where r0 is the saddle point for f (z). This principle (which is related to the one behind

Theorem 7.1) is useful, but has to be applied with caution, and proofs have to be provided for

each case. For fuller exposition of this principle and general results, see [157]. The advantage

of this approach is that often f (z) is easy to manipulate, so the determination of a saddle point

for it is easy, whereas multiplying it by g(z) produces a messy function, and the exact saddle

point for f (z)g(z) is di¬cult to determine.

Example 12.9. Boolean lattice of subsets of {1, . . . , n}. The number a n of Boolean sublattices

of the Boolean lattice of subsets of {1, . . . , n} has the exponential generating function [162]

∞

zn

A(z) = an = exp(2z + exp(z) ’ 1) . (12.44)

n!

n=0

127

We can write A(z) = exp(2z)B(z), where B(z) is the exponential generating function for the

Bell numbers (Example 12.2). Since B(z) grows much faster than exp(2z), it is easy to show

that (12.43) applies, and so

an ∼ exp(2r0 )Bn as n’∞, (12.45)

where r0 is the saddle point for B(z). Using the approximation (12.12) of Example 12.2, we

¬nd that

an ∼ (n/ log n)2 Bn as n’∞. (12.46)

The insensitivity of the saddle point approximation to slight perturbations is re¬‚ected in

slightly di¬erent de¬nitions of a saddle point that are used. The saddle point approximation

(12.9) for [z n ]f (z) is stated in terms of r0 , the point that minimizes f (r)r ’n . The discussion

of the saddle point emphasized minimization of the peak value of the integrand in Cauchy™s

formula, which is the same as minimizing f (r)r ’n’1 , since the contour integral (10.6) involves

f (z)z ’n’1 . Some sources call the point minimizing f (r)r ’n’1 the saddle point. It is not

important which de¬nition is adopted. The asymptotic series coe¬cients look slightly di¬er-

ently in the two cases, but the ¬nal asymptotic series, when expressed in terms of n, are the

same. The reason for slightly preferring the de¬nition that minimizes f (r)r ’n is that when

the change of variable z = r exp(iθ) is made in Cauchy™s integral, there is no linear term in θ,

and the integrand involves exp(’cnθ 2 + O(|θ|3 )). If we minimized f (r)r ’n’1 , we would have

to deal with exp(’c iθ ’ c nθ 2 + O(|θ|3 )), which is not much more di¬cult to handle but is

less elegant.

The same principle can be applied when the exact saddle point is hard to determine, and

it is awkward to work with an implicit de¬nition of this point. When that happens, there

is often a point near the saddle point that is easy to handle, and for which the saddle point

approximation holds. We refer to [157] for examples and discussion of this phenomenon.

12.4. The circle method and other techniques

As we mentioned in Section 12.3, the saddle point method is a powerful method that

estimates the contribution of the neighborhood of only a single point, or at most a few points.

The convergent series of Eq. (1.3) for the partition function p(n) (as well as the earlier non-

convergent but asymptotic and very accurate expansion of Hardy and Ramanujan) is obtained

128

by evaluating the contribution of the other singularities of f (z) to the integral. The m-th term

in Eq. (1.3) comes from the primitive m-th roots of unity. To obtain this expansion one needs

to use a special contour of integration and detailed knowledge of the behavior of f (z). The

details of this technique, called the circle method, can be found in [13, 23].

Convergent series can be obtained from the circle method only when the generating function

is of a special form. For results and references, see [8, 10].

Nonconvergent but accurate asymptotic expansions can be derived from the circle method

in a much wider variety of applications. It is especially useful when there is no single dominant

singularity. For the partition function p(n), all the singularities away from z = 1 contribute

little, and it is z = 1 that creates the dominant term and yields Eq. (1.6). For other functions

this is often false. For example, when dealing with additive problems of Waring™s type, where

one studies Nk,m (n), the number of representations of a nonnegative integer n as

m

xk , +

n= xj ∈ ∪ {0} for all j, (12.47)

j ¢

j=1

the natural generating function to study is

∞

Nk,m (n)z n = g(z)m , (12.48)

n=0

where

∞

k

zh .

g(z) = (12.49)

h=0

The function g(z) has a natural boundary at |z| = 1, but it again grows fastest as z approaches

a root of unity from within |z| < 1, so it is natural to speak of g(z) having singularities at

the roots of unity. The singularity at z = 1 is still the largest, but not by much, as other

roots of unity contribute comparable amounts, with the contribution of other roots of unity ζ

diminishing as the order of ζ increases. All the contributions can be estimated, and one can

obtain solutions to Waring™s problem (which was to show that for every k, there is an integer

m such that Nk,m (n) > 0 for all n) and other additive problems. For details of this method see

[23]. We mention here that for technical reasons, one normally works with generating functions

of the form Gn (z)m , where

n1/k

k

zh ,

Gn (z) = (12.50)

h=0

(so that the generating function depends on n), and analyzes them for |z| = 1 (since they are

now polynomials), but the basic explanation above of why this process works still applies.

129

13. Multivariate generating functions

A major di¬culty in estimating the coe¬cients of multivariate generating functions is

that the geometry of the problem is far more di¬cult. It is harder to see what are the critical

regions where the behavior of the function determines the asymptotics of the coe¬cients, and

those regions are more complicated. Singularities and zeros are no longer isolated, as in the

one-dimensional case, but instead form (k ’ 1)-dimensional manifolds in k variables. Even

rational multivariate functions are not easy to deal with.

One basic tool in one-dimensional complex analysis is the residue theorem, which allows

one to move a contour of integration past a pole of the integrand. (We derived a form of the

residue theorem in Section 10, in the discussion of poles of generating functions.) There is an

impressive generalization by Leray [4, 250] of this theory to several dimensions. Unfortunately,

it is complicated, and with few exceptions (such as that of [252], see also [49]) so far it has not

been applied successfully to enumeration problems. On the other hand, there are some much

simpler tools that can frequently be used to good e¬ect.

An important tool in asymptotics of multivariate generating functions is the multidimen-

sional saddle point method.

Example 13.1. Alternating sums of powers of binomial coe¬cients. Consider

2n s

2n

k+n

S(s, n) = (’1) , (13.1)

k

k=0

where s and n are positive integers. It has been known for a long time that S(1, n) = 0,

S(2, n) = (2n)!(n!)’2 , S(3, n) = (3n)!(n!)’3 . However, no formula of this type has been known

for s > 3. De Bruijn (see Chapter 4 of [63]) showed that S(s, n) for integer s > 3 cannot

be expressed as a ratio of products of factorials. Although his proof is not presented as an

application of the multidimensional saddle point method, it is easy to translate it into those

terms. S(s, n) is easily seen to equal the constant term in

F (z1 , . . . , zs’1 ) = (’1)n (1 + z1 )2n . . . (1 + zs’1 )2n (1 ’ (z1 . . . zs’1 )’1 )2n , (13.2)

and so

’1 ’1

S(s, n) = (2πi)’s+1 ··· F (z1 , . . . , zs’1 )z1 . . . zs’1 dz1 . . . dzs’1 , (13.3)

where the integral is taken with each z j traversing a circle, say. De Bruijn™s proof in e¬ect

shows that for s ¬xed and n ’ ∞, there are two saddle points at z 1 = · · · = zs’1 = exp(2i±),

130

with ± = ±(2s)’1 , and this leads to the estimate

π 2ns+s’1

22’s (πn)(1’s)/2 s’1/2 as n ’ ∞ ,

S(s, n) ∼ 2 cos (13.4)

2s

valid for any ¬xed integer s ≥ 2. Since cos(π(2s) ’1 ) is algebraic but irrational for s ≥ 4, the

asymptotic estimate (13.4) shows that S(s, n) cannot be expressed as a ratio of ¬nite products

of (aj n)! for any ¬xed ¬nite set of integers a j .

In Chapter 6 of [63], de Bruijn derives the asymptotics of S(s, n) as n ’ ∞ for general real s.

The approach sketched above no longer applies, and de Bruijn uses the integral representation

s

“(2n + 1) dz

S(s, n) = ,

“(n + z + 1)“(n ’ z + 1) 2i sin πz

C

where C is a simple closed curve that contains the points ’n, ’n + 1, . . . , ’1, 0, 1, . . . , n in

its interior and has no other integer points on the real axis in its closure. A complicated

combination of analytic techniques, including the one-dimensional saddle point method, then

leads to the ¬nal asymptotic estimate of S(s, n).

The multidimensional saddle point method works best when applied to large singularities.

Just as for the basic one-dimensional method, it does not work when applied to small singu-

larities, such as those of rational functions. Fortunately, there is a trick that often succeeds

in converting a small singularity in n dimensions into a large one in n ’ 1 dimensions. The

main idea is to expand the generating function with respect to one of the variables through

partial fraction expansions or other methods. It is hard to write down a general theorem, but

the next example illustrates this technique.

Example 13.2. Alignments of k sequences. Let f (k, n) denote the number of k — m matrices

of 0™s and 1™s such that each column sum is ≥ 1 and each row sum is exactly n. (The number

of columns, m, can vary, although obviously k ¤ m ¤ kn.) We consider k ¬xed, n ’ ∞ [178].

If we let N (r1 , . . . , rk ) denote the number of 0, 1 matrices with k rows, no columns of all 0™s,

and row sums r1 , . . . , rk , then it is easy to see [178] that

’1

«

k

Copyright Design by: Sunlight webdesign