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


Because when   then   ranges from   to   so   and when   then  .

Lemma 1 edit


as  .

To prove this we need two further lemmas.

Lemma 2 edit


where   is any polynomial and as  .


as   by assumption in the theorem.


by definition of slowly varying function.


Lemma 3 edit

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

  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.