Analytic Combinatorics/Tauberian Theorem

Introduction

edit

'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

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

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
 [7]

as  .

To prove this we need two further lemmas.

Lemma 2

edit
 [8]

where   is any polynomial and as  .

 [9]
 

as   by assumption in the theorem.

 

by definition of slowly varying function.

 
 [9]

Lemma 3

edit

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
  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
  • 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.