LINEBURG


<< . .

 9
( 24)



. . >>

Brigham [58] has proved a general theorem about asymptotics of partition functions that
can be derived from Theorem 8.1. (For other results and references for partition asymptotics,
see [13, 23, 150].)

Theorem 8.2. Suppose that
∞ ∞
(1 ’ z k )’b(k) = a(n)z n ,
f (z) = (8.38)
n=0
k=1

where the b(k) ∈ Z, b(k) ≥ 0 for all k, and that for some C > 0, u > 0, we have

b(k) ∼ Cxu (log x)v as x’∞ . (8.39)
k¤x

Then
∼ u’1 {Cu“(u + 2)ζ(u + 1)}1/(u+1)
log n¤m a(n)
(8.40)
· (u + 1)(u’v)/(u+1) mu/(u+1) (log m)v/(u+1)
as m ’ ∞.

If b(k) = 1 for all k, a(n) is pn , the ordinary partition function. If b(k) = k for all k, a(n) is
the number of plane partitions of n. Thus Brigham™s theorem covers a wide class of interesting
partition functions. The cost of this generality is that we obtain only the asymptotics of the
logarithm of the summatory function of the partitions being enumerated. (For better estimates
of the number of plane partitions, for example, see [9, 170, 387]. For ordinary partitions, we
have the expansion (1.3).)
Brigham™s proof of Theorem 8.2 ¬rst shows that

f (e’w ) ∼ Cw’u (’ log w)v “(u + 1)ζ(u + 1) w ’ 0+
as (8.41)

and then invokes the Hardy-Ramanujan Tauberian theorem [328]. Instead, one can obtain a
proof from Theorem 8.1. The advantage of using Theorem 8.1 is that it is much easier to
generalize. Hardy and Ramanujan proved their Tauberian theorem only for functions whose

62
growth rates are of the form given by (8.41). Their approach can be extended to other functions,
but this is complicated to do. In contrast, Theorem 8.1 is easy to apply. The conditions of
Theorem 8.1 on the derivatives are not restrictive. For a function f (z) de¬ned by (8.38) we
have B ’ ∞ if b(k) = ∞, and the condition (8.33) can be shown to hold whenever there
are constants c1 and c2 such that for all w > 1, and all su¬ciently large m,

b(k) ¤ c1 wc2 b(k) , (8.42)
k¤mw k¤m

say. The main di¬culty in applying Theorem 8.1 to generalizations of Brigham™s theorem is
in accurately estimating the minimal value in Lemma 8.1.
There are many other applications of Lemma 8.1 and Theorem 8.1. For example, they can
be used to prove the results of [158] on volumes of spheres in the Lee metric.
Lemma 8.1 can be generalized in a straightforward way to multivariate generating functions.
If
am,n xm y n
f (x, y) = (8.43)
m,n≥0

and am,n ≥ 0 for all m and n, then for any x, y > 0 for which the sum in (8.43) converges we
have
am,n ¤ x’m y ’n f (x, y) . (8.44)

Generalizations of the lower bound of Theorem 8.1 to multivariate functions can also be derived,
but are again harder than the upper bound [289].

8.2. Tauberian theorems

The Brigham Tauberian theorem for partitions [58], based on the Hardy-Ramanujan
Tauberian theorem [328], was quoted already in Section 8.1. It applies to certain generat-
ing functions that have (in notation to be introduced in Section 10) a large singularity and
gives estimates only for the logarithm of the summatory function of the coe¬cients. Another
theorem that is often more precise, but is again designed to deal with rapidly growing par-
tition functions, is that of Ingham [212], and will be discussed at the end of this section.
Most of the Tauberian theorems in the literature apply to functions with small singularities
(i.e., ones that do not grow rapidly as the argument approaches the circle of convergence) and
give asymptotic relations for the sum of coe¬cients. References for Tauberian theorems are
[117, 154, 190, 212, 325]. Their main advantage is generality and ease of use, as is shown


63
by the applications made to 0-1 laws in [77, 78, 79]. They can often be applied when the
information about generating functions is insu¬cient to use the methods of Sections 11 and
12. This is especially true when the circle inside which the generating function converges is a
natural boundary beyond which the function cannot be continued.
One Tauberian theorem that is often used in combinatorial enumeration is that of Hardy,
Littlewood, and Karamata. We say a function L(t) varies slowly at in¬nity if, for every u > 0,
L(ut) ∼ L(t) as t ’ ∞.

Theorem 8.3. Suppose that ak ≥ 0 for all k, and that

ak xk
f (x) =
k=0

converges for 0 ¤ x < r. If there is a ρ ≥ 0 and a function L(t) that varies slowly at in¬nity
such that
1
f (x) ∼ (r ’ x)’ρ L as x ’ r ’ , (8.45)
r’x
then
n
ak r k ∼ (n/r)ρ L(n)/“(ρ + 1) as n ’ ∞ . (8.46)
k=0



Example 8.4. Cycles of permutations ([33]). If S is a set of positive integers, and f n the
probability that a random permutation on n letters will have all cycle lengths in S (i.e.,
fn = an /n!, where an is the number of permutations with cycle length in S), then

fn z n = exp(z k /k) = (1 ’ z)’1 exp(’z k /k) .
f (z) = (8.47)
n=0 k∈S k∈S

+
If |¢ \ S| < ∞, then the methods of Sections 10.2 and 11 apply easily, and one ¬nds that
« 

fn ∼ exp ’ 1/k  as n’∞. (8.48)
k∈S

+ \ S|
This estimate can also be proved to apply for |¢ = ∞, provided |{1, . . . , m} \ S| does not
grow too rapidly when m ’ ∞. If |S| < ∞ (or when |{1, . . . , m} © S| does not grow rapidly),
the methods of Section 12 apply. When S = {1, 2}, one obtains, for example, the result of
Moser and Wyman [292] that the number of permutations of order 2 is

∼ (n/e)n/2 2’1/2 exp(n1/2 ’ 1/4) as n’∞. (8.49)


64
(For sharper and more general results, see [292, 376].) The methods used in these cases are
di¬erent from the ones we are considering in this section.
We now consider an intermediate case, with

|{1, . . . , m} © S| ∼ ρm as m’∞. (8.50)

for some ¬xed ρ, 0 ¤ ρ ¤ 1. This case can be handled by Tauberian techniques. To apply
Theorem 8.3, we need to show that L(t) = f (1 ’ t ’1 )t’ρ varies slowly at in¬nity. This is
equivalent to showing that for any u ∈ (0, 1),

f (1 ’ t’1 ) ∼ f (1 ’ t’1 u)uρ as t’∞. (8.51)

Because of (8.47), it su¬ces to prove that

k ’1 {(1 ’ t’1 )k ’ (1 ’ t’1 u)k } = ρ log u + o(1) as t’∞, (8.52)
k∈S

but this is easy to deduce from (8.50) using summation by parts (Section 5). Therefore we
¬nd from Theorem 8.3 that
m
fn ∼ f (1 ’ 1/n)“(ρ + 1)’1 as n’∞. (8.53)
n=0

(For additional results and references on this problem see [317].)
 




As the above example shows, Tauberian theorems yield estimates under weak assumptions.
These theorems do have some disadvantages. Not only do they usually estimate only the
summatory function of the coe¬cients, but they normally give no bounds for the error term.
(See [154] for some Tauberian theorems with remainder terms.) Furthermore, they usually
apply only to functions with nonnegative coe¬cients. Sometimes, as in the following theorem
of Hardy and Littlewood, one can relax the nonnegativity condition slightly.

Theorem 8.4. Suppose that ak ≥ ’c/k for some c > 0,

ak xk ,
f (z) = (8.54)
k=1

and that f (x) converges for 0 < x < 1, and that

lim f (x) = A . (8.55)
x’1’

Then
n
lim ak = A . (8.56)
n’∞
k=1


65
Some condition such as ak ≥ ’c/k on the ak is necessary, or otherwise the theorem would
not hold. For example, the function

1’x
= 1 ’ 2x + 2x2 · · ·
f (x) = (8.57)
1+x

satis¬es (8.55) with A = 0, but (8.56) fails.
We next present an example that shows an application of the above results in combination
with other asymptotic methods that were presented before.

Example 8.5. Permutations with distinct cycle lengths. The probability that a random per-
mutation on n letters will have cycles of distinct lengths is [z n ]f (z), where

zk
f (z) = 1+ . (8.58)
k
k=1

Greene and Knuth [177] note that this is also the limit as p ’ ∞ of the probability that a
polynomial of degree n factors into irreducible polynomials of distinct degrees modulo a prime
p. It is shown in [177] that

[z n ]f (z) = e’γ (1 + n’1 ) + O(n’2 log n) as n’∞, (8.59)

where γ = 0.577 . . . is Euler™s constant. A simpli¬ed version of the argument of [177] will be
presented that shows that
[z n ]f (z) ∼ e’γ as n’∞. (8.60)

Methods for obtaining better expansions, even more precise than that of (8.59), are discussed
in Section 11.2. For related results obtained by probabilistic methods, see [20].

We have, for |z| < 1,

log(1 + z k /k)
f (z) = (1 + z) exp
k=2


(8.61)
k
= (1 + z) exp z /k + g(z)
k=2


= (1 + z)(1 ’ z)’1 exp(g(z)) ,

where
∞ ∞
(’1)m’1 z mk
g(z) = ’z + . (8.62)
km
m
m=2 k=2


66
Since the coe¬cients of g(z) are small, the double sum in (8.62) converges for z = 1, and we
have
∞ ∞
(’1)m’1 ’m
g(1) = lim g(z) = ’1 + k
m
z’1’
k=2 m=2


(8.63)
{log(1 + k ’1 ) ’ k ’1 }
= ’1 +
k=2


= ’ log 2 + lim (log(n + 1) ’ Hn ) = ’ log 2 ’ γ ,
n’∞

where Hn = 1 + 1/2 + 1/3 + · · · + 1/n is the n-th harmonic number. Therefore, by (8.61), we
¬nd from Theorem 8.4 that if fn = [z n ]f (z), then

f0 + f1 + · · · + fn ∼ ne’γ as n’∞. (8.64)

To obtain asymptotics of fn , we note that if hn = [z n ] exp(g(z)), then by (8.61),

fn = 2h0 + 2h1 + · · · + 2hn’1 + hn . (8.65)

We next obtain an upper bound for |hn |. There are several ways to proceed. The method used
below gives the best possible result |h n | = O(n’2 ).
Since g(z) has the power series expansion (8.62), and h n = [z n ] exp(g(z)), comparison of
terms in the full expansion of exp(g(z)) and exp(v(z)) shows that |h n | ¤ [z n ] exp(v(z)), where
v(z) is any power series such that |[z n ]g(z)| ¤ [z n ]v(z). For n ≥ 2,

(’1)m’1 m m
n
[z ]g(z) = . (8.66)
m n
m|n
m≥2
m<n

The term (m/n)m is monotone decreasing for 1 ¤ m ¤ n/e, since its derivative with respect
to m is ¤ 0 in that range. Therefore
2 3
1 2 1 3 2 ’n/2
n
¤ 10n’2 ,
|[z ]g(z)| ¤ + + 2 (8.67)
2 n m n n
3¤m¤n/3

say. Hence we can take

n’2 z n ,
v(z) = 10 (8.68)
n=1

and then we need to estimate
wn = [z n ] exp(v(z)) . (8.69)


67
We let w(z) = exp(v(z)), and note that

w (z) = v (z)w(z) , (8.70)

so for n ≥ 1,
n’1
wk (n ’ k)’1 .
nwn = 10 (8.71)
k=0

Further, since v(1) < ∞, and wn ≥ 0 for all n, we have wn ¤ A = w(1) = exp(v(1)) for all
n. Let B = 106 A and note that wn ¤ Bn’2 for 1 ¤ n ¤ 103 . Suppose now that wm ¤ Bm’2
for 1 ¤ m < n for some n ≥ 103 . We will prove that wn ¤ Bn’2 , and then by induction this
inequality will hold for all n ≥ 1. We apply Eq. (8.70). For 0 ¤ k ¤ 100, we use w k ¤ A,
(n ’ k)’1 ¤ 2n’1 . For 100 < k ¤ n/2,

wk (n ’ k)’1 ¤ Bk ’2 (n ’ k)’1 ¤ 2Bk ’2 n’1 , (8.72)

and so
wk (n ’ k)’1 ¤ B(40n)’1 . (8.73)
100¤k¤n/2

Finally,
wk (n ’ k)’1 ¤ 4Bn’2 (n ’ k)’1 ¤ 4Bn’2 Hn . (8.74)
n/2<k¤n’1 n/2<k¤n’1

Therefore, by (8.71),

nwn ¤ 2000An’1 + B(4n)’1 + 4BHn n’2 ¤ Bn’1 , (8.75)

which completes the induction step and proves that w n ¤ Bn’2 for all n ≥ 1.
 




There are Tauberian theorems that apply to generating functions with rapidly growing
coe¬cients but are more precise than Brigham™s theorem or the estimates obtainable with the
methods of Section 8.1. One of the most useful is Ingham™s Tauberian theorem for partitions
[212]. The following result is a corollary of the more general Theorem 2 of [212].

Theorem 8.5. Let 1 ¤ u1 < u2 < . . . be positive integers such that

|{uj : uj ¤ x}| = Bxβ + R(x) , (8.76)

where B > 0, β > 0, and
y
x’1 R(x)dx = b log y + c + o(1) as y’∞. (8.77)
1


68
Let
∞ ∞
n
(1 ’ z uj )’1 ,
a(z) = an z = (8.78)
n=1 j=1
∞ ∞
a— (z) = a— z n = (1 + z uj ) . (8.79)
n
n=1 j=1

Then, as m ’ ∞,
m
an ∼ (2π)’1/2 (1 ’ ±)1/2 ec V ’±(b+1/2) m(b+1/2)(1’±)’1/2 exp(±’1 (V m)± ) , (8.80)
n=1
m
a— ∼ (2π)’1/2 (1 ’ ±)1/2 2b (V — m)’±/2 exp(±’1 (V — m)± ) , (8.81)
n
n=1

where

± = β(β + 1)’1 , V = {Bβ“(β + 1)ζ(β + 1)}1/β , V — = (1 ’ 2’β )1/β V . (8.82)

If u1 = 1, then as n ’ ∞

an ∼ (2π)’1/2 (1 ’ ±)1/2 ec V ’±(b’1/2) n(b’1/2)(1’±)’1/2 exp(±’1 (V n)± ) , (8.83)

and if 1, 2, 4, 8, . . . all belong to {uj }, then

a— ∼ (2π)’1/2 (1 ’ ±)1/2 2b (V — )±/2 n±/2’1 exp(±’1 (V — n)± ) . (8.84)
n


Theorem 8.5 provides more precise information than Brigham™s Theorem 8.2, but under
more restrictive conditions. It is derived from Ingham™s main result, Theorem 1 of [212],
which can be applied to wider classes of functions. However, that theorem cannot be used to
derive Theorem 8.2. The disadvantage of Ingham™s main theorem is that it requires knowledge
of the behavior of the generating function in the complex plane, not just on the real axis.
On the other hand, the region where this behavior has to be known is much smaller than
it is for the analytic methods that give more accurate answers, and which are presented in

<< . .

 9
( 24)



. . >>

Copyright Design by: Sunlight webdesign