LINEBURG

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

Copyright Design by: Sunlight webdesign