Analytic Combinatorics/Tauberian Theorem

From Wikibooks, open books for an open world
Jump to navigation Jump to search

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


Because when then ranges from to so and when then .

Lemma 1[edit | edit source]


as .

To prove this we need two further lemmas.

Lemma 2[edit | edit source]


where is any polynomial and as .


as by assumption in the theorem.

by definition of slowly varying function.


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


Construct continuous functions and [11] such that




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 finally

By a similar argument, one can prove

Combining both these results we conclude the proof of lemma 1

Putting it all together:



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.