Analytic Combinatorics/Tauberian Theorem

IntroductionEdit

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

TheoremEdit

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.

ProofEdit

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 1Edit

 [7]

as  .

To prove this we need two further lemmas.

Lemma 2Edit

 [8]

where   is any polynomial and as  .

 [9]
 

as   by assumption in the theorem.

 

by definition of slowly varying function.

 
 [9]

Lemma 3Edit

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

 [10]

Assume there are continuous functions   and   such that

 

Then

 [11]

and

 

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

 

If 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  

 

NotesEdit

  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. w:Gamma_function#Integral_representations

ReferencesEdit

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