LINEBURG


<< . .

 17
( 24)



. . >>

A) There is an R0 , 0 < R0 < R and a function d(r) de¬ned for r ∈ (R 0 , R) such that

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

<< . .

 17
( 24)



. . >>

Copyright Design by: Sunlight webdesign