LINEBURG


<< . .

 13
( 24)



. . >>

provides enough of an extra boost to push through the necessary technical details of the
estimates.
Most generating functions f (z) have their coe¬cients a n = [z n ]f (z) real. If f (z) is analytic
at 0, and has real coe¬cients, then f (z) satis¬es the re¬‚ection principle,

f (z) = f (z) . (10.12)

This implies that zeros and singularities of f (z) come in complex conjugate pairs.
The success of analytic methods in asymptotics comes largely from the use of Cauchy™s
formula (10.6) to estimate accurately the coe¬cients a n . At a more basic level, this success
comes because the behavior of an analytic function f (z) re¬‚ects precisely the behavior of the
coe¬cients an . In the discussion of elementary methods in Section 8, we pointed out that the
behavior of a generating function for real arguments does not distinguish between functions
with di¬erent coe¬cients. For example, the functions f 1 (z) and f3 (z) de¬ned by (8.1) and (8.4)
are almost indistinguishable for z ∈ . However, they di¬er substantially in their behavior for
¡




complex z. The function f1 (z) has only a ¬rst order pole at z = 1 and no other singularities,
while f3 (z) has poles at z = 1, exp(2πi/3), and exp(4πi/3). The three poles at the three cubic
roots of unity re¬‚ect the modulo 3 periodicity of the coe¬cients of f 3 (z). This is a general
phenomenon, and in the next section we sketch the general principle that underlies it. (The
degree to which coe¬cients of an analytic function determine the behavior at the singularities
is the subject of Abelian theorems. We will not need to delve into this subject to its full depth.
For references, see [190, 364].)
Analytic methods are extremely powerful, and when they apply, they often yield estimates
of unparalleled precision. However, there are tricky situations where analytic methods seem
as if they ought to apply, but don™t (at least not easily), whereas simpler approaches work.




93
Example 10.2. Set partitions with distinct block sizes. Let a n be the number of partitions of
a set of n elements into blocks of distinct sizes. Then a n = bn · n!, where bn = [z n ]f (z), with

zk
f (z) = 1+ . (10.13)
k!
k=1
The function f (z) is entire and has nonnegative coe¬cients, so it might appear as an ideal
candidate for an application of some of the methods for dealing with large singularities (such as
the saddle point technique) that will be presented later. However, on circles |z| = (n + 1/2)/e,
+,
n∈ f (z) does not vary much, so there are technical problems in applying these analytic
¢




methods. On the other hand, combinatorial estimates can be used to show [233] that the b n
behave in a “regularly irregular” way, so that, for example,

bm(m+1)/2’1 ∼ bm(m+1)/2 as m’∞, (10.14)

bm(m+1)/2 ∼ mbm(m+1)/2+1 as m’∞. (10.15)

These estimates are obtained by expanding the product in Eq. (10.13) and noting that
1
bn = . (10.16)
r
ki !
r
1¤k1 <···<kr
i=1
ki =n

Since factorials grow rapidly, the only terms in the sum in (10.16) that are signi¬cant are those
with small ki . The term bn z n for n = m(m + 1)/2 for example, comes almost entirely from
the product of z k /k!, 1 ¤ k ¤ m, all other products contributing an asymptotically negligible
amount.
 




10.2. Subtraction of singularities

An important basic tool in asymptotics of coe¬cients of analytic functions is that of
subtraction of singularities. If we wish to estimate [z n ]f (z), and we know [z n ]g(z), and the
singularities of f (z) ’ g(z) are smaller than those of f (z), then we can usually conclude that
[z n ]f (z) ∼ [z n ]g(z) as n ’ ∞. In practice, given a function f (z), we ¬nd the dominant singu-
larities of f (z) (usually poles), and construct a simple function g(z) with those singularities.
We illustrate this approach with several examples. The basic theme will recur in other sections.



Example 10.3. Bernoulli numbers. The Euler-Maclaurin summation formula, introduced in
Section 5.3, involves the Bernoulli numbers B n with exponential generating function

zn z
f (z) = Bn =z . (10.17)
n! e ’1
n=0


94
The denominator exp(z) ’ 1 has zeros at 0, ±2πi, ±4πi, . . . . The zero at 0 is canceled by the
zero of z, so f (z) is analytic for |z| < 2π, but has ¬rst order poles at z = ±2πi, ±4πi, . . . .
Consider
1 1
g(z) = 2πi ’ . (10.18)
z ’ 2πi z + 2πi
Then f (z) ’ g(z) is analytic for |z| < 4π, so

|[z n ](f (z) ’ g(z))| = O((4π ’ )’n ) as n’∞ (10.19)

for every > 0. On the other hand,

0 n odd ,
[z n ]g(z) = (10.20)
2(2π)’n n even .

This gives the leading term asymptotics of B n . By taking more complicated g(z), we can
subtract more of the singularities of f (z) and obtain more accurate expansions for B n . It is
even possible to obtain an exponentially rapidly convergent series for B n .
 




Example 10.4. Rational function asymptotics. As another example of the subtraction of
singularities principle, we sketch a proof of Theorem 9.1. Suppose that the hypotheses of that
theorem are satis¬ed. Let
k
’g(ρj )
u(z) = . (10.21)
ρj h (ρj )(1 ’ z/ρj )
j=1

Then f (z) ’ u(z) has no singularities in |z| ¤ R, and for |z| = R,
k
’1
|f (z) ’ u(z)| ¤ |f (z)| + |u(z)| ¤ W + δ |g(ρj )/h (ρj )| . (10.22)
j=1

Hence, by Theorem 10.2,
k
n ’n ’1 ’n
[z ](f (z) ’ u(z)) ¤ W R +δ R |g(ρj )/h (ρj )| . (10.23)
j=1

On the other hand,
k
ρ’n’1 g(ρj )/h (ρj ) .
[z n ]u(z) = ’ (10.24)
j
j=1

The last two estimates yield Theorem 9.1.
 




The reader may have noticed that the proof of Theorem 9.1 presented above does not
depend on f (z) being rational. We have proved the following more general result.



95
Theorem 10.4. Suppose that f (z) is meromorphic in an open set containing |z| ¤ R, that it
is analytic at z = 0 and on |z| = R, and that the only poles of f (z) in |z| < R are at ρ 1 , . . . , ρk ,
each of multiplicity 1. Suppose further that

max |f (z)| ¤ W (10.25)
|z|=R

and that R ’ |ρj | ≥ δ for some δ > 0 and 1 ¤ j ¤ k. Then

k k
rj ρ’n’1
n ’n ’1 ’n
[z ]f (z) + ¤ WR +δ R |rj | , (10.26)
j
j=1 j=1

where rj is the residue of f (z) at ρj .

In the examples above, the dominant singularities were separated from other ones, so their
contributions were larger than those of lower order terms by an exponential factor. Sometimes
the singularity that remains after subtraction of the dominant one is on the same circle, and
only slightly smaller. Section 11 presents methods that deal with some cases of this type, at
least when the singularity is not large. What makes those methods work is the subtraction
of singularities principle. Next we illustrate another application of this principle where the
singularity is large. (The generating function is entire, and so the singularity is at in¬nity.)

Example 10.5. Permutations without long increasing subsequences. Let u k (n) be the number
of permutations of {1, 2, . . . , n} that have no increasing subsequence of length > k. Logan and
Shepp [257] and Vershik and Kerov [370] established by calculus of variations and combina-
torics that the average value of the longest increasing subsequence in a random permutation is
asymptotic to 2n1/2 . Frieze [149] has proved recently, using probabilistic methods, a stronger
result, namely that almost all permutations have longest increasing subsequences of length
close to 2n1/2 . Here we consider asymptotics of uk (n) for k ¬xed and n ’ ∞. The Schensted
correspondence and the hook formula express u k (n) in terms of Young diagrams with ¤ k
columns. For k ¬xed, there are few diagrams and their in¬‚uence can be estimated explicitly
using Stirling™s formula, although Selberg-type integrals are involved and the analysis is com-
plicated. This analysis was done by Regev [329], who proved more general results. Here we
sketch another approach to the asymptotics of u k (n) for k ¬xed. It is based on a result of
Gessel [161]. If

uk (n)z 2n
Uk (z) = , (10.27)
(n!)2
n=0


96
then
Uk (z) = det(I|i’j| (2z))1¤i,j¤k , (10.28)

where the Im (x) are Bessel functions (Chapter 9 of [297]). H. Wilf and the author have noted
that one can obtain the asymptotics of the u k (n) by using known asymptotic results about the
+,
Im (x). Eq. (9.7.1) of [297] states that for every H ∈ ¢




H’1
’1/2 z
c(m, h)z ’h + O(|z|’H )
Im (z) = (2πz) e , (10.29)
h=0

where this expansion is valid for |z| ’ ∞ with |Arg(z)| ¤ 3π/8, say. The c(m, h) are explicit
constants with c(m, 0) = 1. Let us consider k = 4 to be concrete. Then, taking H = 7 in
(10.29) (higher values of H are needed for larger k) we ¬nd from (10.28) that

U4 (z) = e8z (3(256π 2 z 8 )’1 + O(|z|’9 )) for |z| ≥ 1 . (10.30)

It is also known that Im (’z) = (’1)m Im (z) and Im (z) is relatively small in the angular region
|π/2 ’ Arg(z)| < π/8. Therefore U4 (’z) = U4 (z), and one can show that

|U4 (z)| = O(|z|’1 U4 (|z|)) (10.31)

for z away from the real axis.
To apply the subtraction of singularities principle, we need an entire function f (z) that is
even, is large only near the real axis, and such that for x ∈ , x ’ ∞,
¡




f (x) ∼ 3(256π 2 x8 )’1 exp(8x) . (10.32)

The function
f — (z) = 3(128π 2 z 8 )’1 cosh(8z)

is even and has the desired asymptotic growth, but is not entire. We correct this defect by
subtracting the contribution of the pole at z = 0, and let

f (z) = 3(128π 2 z 8 )’1 (cosh(8z) ’ 1 ’ 32z 2 ’ 512z 4 /3 ’ 16384z 6 /45 ’ 131072z 8 /315) . (10.33)

(It is not necessary to know explicitly the ¬rst 8 terms in the Taylor expansion of cosh(8z)
that we wrote down above, as they do not a¬ect the ¬nal answer.) With this de¬nition

|U4 (z) ’ f (z)| = O(|z|’1 f (|z|)) (10.34)


97
uniformly for all z with |z| ≥ 1, say, and so if we apply Cauchy™s theorem on the circle |z| = n/4,
say, we ¬nd that
[z 2n ](U4 (z) ’ f (z)) = O(n’2n e2n 16n n’9 ) . (10.35)

(The choice of |z| = n/4 is made to minimize the resulting estimate.) On the other hand, by
Stirling™s formula,

[z 2n ]f (z) = 3(128π 2 )’1 · ([z 2n+8 ]cosh(8z))

= 3(128π 2 )’1 82n+8 /(2n + 8)!

∼ 1536π ’5/2 n’2n 16n e2n n’17/2 as n’∞. (10.36)

Comparing (10.35) and (10.36), we see that

u4 (n) = (n!)2 [z 2n ]U4 (z) ∼ (n!)2 1536π ’5/2 n’2n 16n e2n n’17/2

∼ 1536π ’3/2 n’15/2 16n as n’∞. (10.37)
 




Other methods can be applied to Gessel™s generating function to obtain asymptotics of
uk (n) for wider ranges of k ([306]).
The above example obtains a good estimate because the remainder term in (10.30) is smaller
than the main term by a factor of |z|’1 . Had it been smaller only by a factor of |z| ’1/2 , the
resulting estimate would have been worthless, and it would have been necessary to obtain a
fuller asymptotic expansion of U4 (z) or else use smoothness properties of the remainder term.
This is due to the phenomenon, mentioned before, that crude absolute value estimates in either
Cauchy™s theorem, or the elementary approaches of Section 8, usually lose a factor of n 1/2 when
estimating the n-th coe¬cient.
The subtraction of singularities principle can be applied even when the generating functions
seem to be more complicated than those of Example 10.5. If we consider the problem of that
example, but with k = 5, then we ¬nd that

U5 (z) = 3 exp(10z)(5 · 213 · π 5/2 z 25/2 )’1 (1 + O(|z|’1 )) (10.38)

as |z| ’ ∞, with |Arg(z)| ¤ 3π/8, U5 (’z) = U5 (z), and U5 (z) is entire. We now need an
entire function with known coe¬cients that grows as exp(10z)z ’25/2 . This is not di¬cult to
obtain, as
12
’12
cj z ’j
I0 (10z)z ’ (10.39)
j=1


98
for suitable coe¬cients cj has the desired properties.

10.3. The residue theorem and sums as integrals

Sometimes sums that are not easily handled by other methods can be converted to integrals
that can be evaluated explicitly or estimated by the residue theorem. If t(z) is a meromorphic
function that has ¬rst order poles at z = a, a + 1, . . . , b, with a ∈ Z, each with residue 1, then
b
1
f (n) = f (z)t(z)dz , (10.40)
2πi “
n=a

where “ is a simple closed contour enclosing a, a + 1, . . . , b, provided f (z) is analytic inside “
and t(z) has no singularities inside “ aside from the ¬rst order poles at a, a + 1, . . . , b. If t(z)
is chosen to have residue (’1)n at z = n, then we obtain
b
1
(’1)n f (n) = f (z)t(z)dz . (10.41)
2πi “
n=a
A useful example is given by the formula
n
(’1)n n!
n f (z)dz
k
(’1) f (k) = . (10.42)
k 2πi z(z ’ 1) · · · (z ’ n)

k=0

The advantage of (10.40) and (10.41) is that the integrals can often be manipulated to give
good estimates. This is especially valuable for alternating sums such as (10.41). An analytic
function f (z) is extremely regular, so a sum such as that in (10.40) can often be estimated by
methods such as the Euler-Maclaurin summation formula (Section 5.3). However, that formula
cannot always be applied to alternating sums such as that of (10.41), because the sign change
destroys the regularity of f (n). (However, as is noted in Section 5.3, there are generalizations
of the Euler-Maclaurin formula that are sometimes useful.) It is hard to write down general
rules for applying this method, as most situations require appropriate choice of t(z) and careful
handling of the integral. For a detailed discussion of this method, often referred to as Rice™s
method, see Section 4.9 of [205]. A pair of popular functions to use as t(z) are

t1 (z) = π/(sin πz), t2 (z) = π/(tan πz) . (10.43)

One can show (Theorem 4.9a of [205]) that if r(z) = p(z)/q(z) with p(z) and q(z) polynomials
such that deg q(z) ≥ deg p(z) + 2, and q(n) = 0 for any n ∈ Z, then

r(n) = ’ Res(r(z)t1 (z)) , (10.44)
n=’∞

(’1)n r(n) = ’ Res(r(z)t2 (z)) , (10.45)
n=’∞


99
where the sums on the right-hand sides above are over the zeros of q(z).
Examples of applications of these methods to asymptotics of data structures are given in
[141] and [360].

10.4. Location of singularities, Rouch´™s theorem, and unimodality
e

A recurrent but only implicit theme throughout the discussion in this section is that of
isolation of zeros. For example, to apply Theorem 9.1 we need to know that the polynomial
h(z) has only k zeros, each of multiplicity one, in |z| < R. Proofs of such results can often be
obtained with the help of Rouch´™s theorem [205, 364].
e

Theorem 10.5. Suppose that f1 (z) and f2 (z) are functions that are analytic inside and on
the boundary of a simple closed contour “. If

|f2 (z)| < |f1 (z)| for all z∈“ , (10.46)

then f1 (z) and f1 (z) + f2 (z) have the same number of zeros (counted with multiplicity) inside
“.


Example 10.6. Sequences with forbidden subblocks. We consider again the topic of Exam-
ples 6.4, 6.8, and 9.2, and prove the results that were already used in Example 9.2. We again
set
h(z) = z k + (1 ’ 2z)CA (z) , (10.47)

where the only fact about CA (z) we will use is that it is a polynomial of degree < k and
coe¬cients 0 and 1, and CA (0) = 1. We wish to show that h(z) has only one zero in |z| ¤ 0.6
if k is large. Write
∞ ∞
1 1
j j

<< . .

 13
( 24)



. . >>

Copyright Design by: Sunlight webdesign