Jump to content

Analytic Combinatorics/Tauberian Theorem

From Wikibooks, open books for an open world

Introduction

[edit | edit source]

'Tauberian' refers to a class of theorems with many applications. The full scope of Tauberian theorems is too large to cover here.

We prove here only a particular Tauberian theorem due to Hardy, Littlewood and Karamata, which is useful in analytic combinatorics.

Theorem

[edit | edit source]

Theorem due to Hardy[1].

If as , where and is a slowly varying function, then when .

Bear in mind that if we can convert it to a General Dirichlet series (without changing the value of the coefficients we are interested in) by the substitution such that

as [2].

This gives us

which is the form it is given in Flajolet and Sedgewick 2009, pp. 435.

Proof

[edit | edit source]

Proof due to Hardy[3].

If then this method actually finds the asymptotic estimate of after which we can find by or by finding in .

Let be a step function where , and [4].

Using integration by parts[5]:

Because .

If then

[6]

Because when then ranges from to so and when then .

Lemma 1

[edit | edit source]
[7]

as .

To prove this we need two further lemmas.

Lemma 2

[edit | edit source]
[8]

where is any polynomial and as .

[9]

as by assumption in the theorem.

by definition of slowly varying function.

[9]

Lemma 3

[edit | edit source]

If is real-valued and Riemann integrable in the open interval and then there exist polynomials and such that and

[10]

Construct continuous functions and [11] such that

Then

[12]

and

By the Weierstrass approximation theorem there are polynomials and such that and . If and then as required by the lemma and

By virtue of being Riemann-integrable, we can find finite step functions and such that and

Then, we have proven above there are polynomials and such that and

Combining these we can complete the proof of lemma 3:

Going back to the proof of lemma 1

by lemma 2.

Lemma 3 implies that

so that

and

and finally

By a similar argument, one can prove

Combining both these results we conclude the proof of lemma 1

Putting it all together:

or

.

As . Then, if

Notes

[edit | edit source]
  1. Hardy 1949, pp. 166.
  2. Because as which is equivalent to as . See De Bruijn 1981, pp. 10 and Hardy 1949, pp. 155.
  3. Hardy 1949, pp. 166-168.
  4. Hardy 1949, pp. 158.
  5. w:Riemann–Stieltjes_integral#Properties
  6. Hardy 1949, pp. 158.
  7. Hardy 1949, pp. 166.
  8. Hardy 1949, pp. 168.
  9. a b Due to the sum rule of integration?
  10. Hardy 1949, pp. 166.
  11. For example, you could construct piecewise continuous functions by partitioning into , putting and and then "joining the dots" between these values. Refine the partition until the conditions are met.
  12. w:Gamma_function#Integral_representations

References

[edit | edit source]
  • Hardy, G.H. (1949). Divergent Series (1st ed.). Oxford University Press.
  • Flajolet, Philippe; Sedgewick, Robert (2009). Analytic Combinatorics (PDF). Cambridge University Press.
  • De Bruijn, N.G. (1981). Asymptotic Methods in Analysis. Dover Publications.