Analytic Combinatorics/Tauberian Theorem

'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 originally to Hardy, Littlewood and Karamata, which is useful in analytic combinatorics.

Theorem from Feller.^[1]

If

${\displaystyle f(x)=\sum _{n=0}^{\infty }a_{n}x^{n}\sim {\frac {1}{(1-x)^{\rho }}}L\left({\frac {1}{1-x}}\right)\qquad (x\to 1^{-})}$

where the sequence ${\displaystyle \{a_{n}\}}$ is monotone (always non-decreasing or always non-increasing), ${\displaystyle 0<\rho <\infty }$ and ${\displaystyle \lim _{x\to \infty }{\frac {L(cx)}{L(x)}}=1}$ then

${\displaystyle a_{n}\sim {\frac {n^{\rho -1}}{\Gamma (\rho )}}L(n)\qquad (n\to \infty )}$

Proof from Feller.^[2]

• We express our theorem in terms of a measure ${\displaystyle U}$ with a density function ${\displaystyle u(x)=a_{n}\quad (n\leq x<n+1)}$ such that ${\displaystyle U(n)=\int _{0}^{n}u(x)dx=\sum _{i=0}^{n-1}a_{i}}$.
• The Laplace transform of ${\displaystyle U}$ is ${\displaystyle \omega (\lambda )=\int _{0}^{\infty }e^{-\lambda x}u(x)dx=\sum _{n=0}^{\infty }\int _{n}^{n+1}u(x)e^{-\lambda x}dx=\sum _{n=0}^{\infty }a_{n}\int _{n}^{n+1}e^{-\lambda x}dx=\sum _{n=0}^{\infty }a_{n}{\frac {1}{\lambda }}(e^{-n\lambda }-e^{-(n+1)\lambda })={\frac {1-e^{-\lambda }}{\lambda }}\sum _{n=0}^{\infty }a_{n}e^{-n\lambda }}$^[3]
• By the power series expansion of ${\displaystyle e}$, as ${\displaystyle \lambda \to 0}$, ${\displaystyle {\frac {1-e^{-\lambda }}{\lambda }}={\frac {\lambda +o(\lambda )}{\lambda }}\sim 1}$.
• Therefore, ${\displaystyle \omega (\lambda )\sim f(e^{-\lambda })\sim {\frac {1}{(1-e^{-\lambda })^{\rho }}}L\left({\frac {1}{1-e^{-\lambda }}}\right)\sim {\frac {1}{\lambda ^{\rho }}}L\left({\frac {1}{\lambda }}\right)}$ as ${\displaystyle \lambda \to 0}$.
• ${\displaystyle {\frac {\omega ({\frac {\lambda }{x}})}{\omega ({\frac {1}{x}})}}\sim {\frac {1}{\lambda ^{\rho }}}{\frac {L({\frac {x}{\lambda }})}{L(x)}}\sim {\frac {1}{\lambda ^{\rho }}}}$ as ${\displaystyle x\to \infty }$.^[4]
• ${\displaystyle {\frac {1}{\lambda ^{\rho }}}}$ is the Laplace transform of ${\displaystyle {\frac {y^{\rho -1}}{\Gamma (\rho )}}}$. To express this in terms of the measure ${\displaystyle {\frac {U(xy)}{\omega ({\frac {1}{x}})}}}$, we integrate the latter to get ${\displaystyle {\frac {y^{\rho }}{\rho \Gamma (\rho )}}={\frac {y^{\rho }}{\Gamma (\rho +1)}}}$.
• We use the continuity theorem to show that this implies ${\displaystyle {\frac {U(xy)}{\omega ({\frac {1}{x}})}}\sim {\frac {y^{\rho }}{\Gamma (\rho +1)}}}$, or (setting ${\displaystyle y=1}$) ${\displaystyle U(x)\sim {\frac {\omega ({\frac {1}{x}})}{\Gamma (\rho +1)}}\sim {\frac {x^{\rho }}{\Gamma (\rho +1)}}L(x)}$.
• We prove that this implies ${\displaystyle u(x)\sim {\frac {\rho U(x)}{x}}}$.
• Therefore, ${\displaystyle a_{n}=u(n)\sim {\frac {\rho U(n)}{n}}\sim {\frac {n^{\rho -1}}{\Gamma (\rho )}}L(n)}$.

A measure ${\displaystyle U}$ assigns a positive number to a set. It is a generalisation of concepts such as length, area or volume.

In our case, our measure is the area under the curve of the step function that takes the values of our coefficients, ${\displaystyle u(x)=a_{n}\quad (n\leq x<n+1)}$. Therefore, ${\displaystyle U(x)=\int _{0}^{x}u(y)dy}$. If ${\displaystyle n}$ is an integer, ${\displaystyle U(n)=\sum _{i=0}^{n-1}a_{i}}$. We define ${\displaystyle U\{I\}}$ to be the area under the curve confined to the interval ${\displaystyle I}$. If the interval ${\displaystyle I}$ is contained in the interval ${\displaystyle (n,n+1)}$ for some ${\displaystyle n}$ and ${\displaystyle l}$ is the length of ${\displaystyle I}$, then ${\displaystyle U\{I\}=u(n)l}$.

A measure can be converted to a probability distribution ${\displaystyle F(x)={\frac {U(x)}{U(+\infty )}}}$ with density ${\displaystyle f(x)=u(x)}$, assigning a probability to how likely a random variable will take on a value less than or equal to ${\displaystyle x}$. We do this because probability distributions have two properties which we make use of in our proof.

We define ${\displaystyle F\{A\}}$ to be the probability that a random variable will take on a value in the set ${\displaystyle A}$.

The expectation or mean of a probability distribution ${\displaystyle F}$ with density ${\displaystyle f}$ is calculated as ${\displaystyle E(X)=\int _{-\infty }^{\infty }xf(x)dx}$.

We also define ${\displaystyle E(u)=\int _{-\infty }^{\infty }u(x)f(x)dx}$.

Theorem 1

Let ${\displaystyle \{F_{n}\}}$ be a sequence of probability distributions with expectations ${\displaystyle E_{n}}$, if ${\displaystyle F_{n}\to F}$ then ${\displaystyle E_{n}(u)\to E(u)}$ for ${\displaystyle u\in C_{0}(-\infty ,\infty )}$.^[5]

Proof

Assume ${\displaystyle F_{n}\to F}$. Let ${\displaystyle u}$ be a continuous function such that ${\displaystyle |u(x)|<M}$ for all ${\displaystyle x}$. Let A be an interval such that ${\displaystyle F\{A\}>1-\epsilon }$, and therefore, for the complement ${\displaystyle A'}$, ${\displaystyle F\{A'\}<2\epsilon }$ for ${\displaystyle n}$ sufficiently large.

Because ${\displaystyle u}$ is continuous it is possible to partition ${\displaystyle A}$ into intervals ${\displaystyle I_{1},I_{2},\cdots }$ so small that ${\displaystyle u}$ oscillates by less than ${\displaystyle \epsilon }$.

We can then estimate ${\displaystyle u}$ in ${\displaystyle A}$ by a step function ${\displaystyle \sigma }$ which assumes constant values within each ${\displaystyle I_{k}}$ and such that ${\displaystyle |u(x)-\sigma (x)|<\epsilon }$ for all ${\displaystyle x\in A}$. We define ${\displaystyle \sigma (x)=0}$ for ${\displaystyle x\in A'}$, so that ${\displaystyle |u(x)-\sigma (x)|<M}$ for ${\displaystyle x\in A'}$.

Therefore, ${\displaystyle |E(u)-E(\sigma )|\leq \epsilon F\{A\}+MF\{A'\}\leq \epsilon +M\epsilon }$.

For sufficiently large ${\displaystyle n}$, ${\displaystyle |E_{n}(u)-E_{n}(\sigma )|\leq \epsilon F_{n}\{A\}+MF_{n}\{A'\}\leq \epsilon +M\epsilon }$

Because ${\displaystyle E_{n}(\sigma )\to E(\sigma )}$ then for sufficiently large ${\displaystyle n}$, ${\displaystyle |E(\sigma )-E_{n}(\sigma )|<\epsilon }$.

Putting it all together,

${\displaystyle |E(u)-E_{n}(u)|\leq |E(u)-E(\sigma )|+|E(\sigma )-E_{n}(\sigma )|+|E_{n}(\sigma )-E_{n}(u)|<3(M+1)\epsilon }$

which implies ${\displaystyle E_{n}(u)\to E(u)}$.^[6]

Lemma 1

Let ${\displaystyle a_{1},a_{2},\cdots }$ be an arbitrary sequence of points. Every sequence of numerical functions contains a subsequence that converges for all ${\displaystyle a_{i}}$.^[7]

Row 4, ${\displaystyle u_{n}^{4}}$, (in blue) is contained in the previous 3 rows, contains all the subsequent rows and converges at ${\displaystyle a_{4}}$. All ${\displaystyle u_{4}^{4},u_{5}^{5},\cdots }$ (in green) are contained in ${\displaystyle u_{n}^{4}}$ and therefore converge for ${\displaystyle a_{4}}$. This argument can be repeated for all ${\displaystyle a_{k}}$.

${\displaystyle u_{1}^{1}}$	${\displaystyle u_{2}^{1}}$	${\displaystyle u_{3}^{1}}$	${\displaystyle u_{4}^{1}}$	${\displaystyle u_{5}^{1}}$	${\displaystyle \cdots }$
${\displaystyle u_{1}^{2}}$	${\displaystyle u_{2}^{2}}$	${\displaystyle u_{3}^{2}}$	${\displaystyle u_{4}^{2}}$	${\displaystyle u_{5}^{2}}$	${\displaystyle \cdots }$
${\displaystyle u_{1}^{3}}$	${\displaystyle u_{2}^{3}}$	${\displaystyle u_{3}^{3}}$	${\displaystyle u_{4}^{3}}$	${\displaystyle u_{5}^{3}}$	${\displaystyle \cdots }$
${\displaystyle \color {blue}u_{1}^{4}}$	${\displaystyle \color {blue}u_{2}^{4}}$	${\displaystyle \color {blue}u_{3}^{4}}$	${\displaystyle \color {green}u_{4}^{4}}$	${\displaystyle \color {blue}u_{5}^{4}}$	${\displaystyle \cdots }$
${\displaystyle u_{1}^{5}}$	${\displaystyle u_{2}^{5}}$	${\displaystyle u_{3}^{5}}$	${\displaystyle u_{4}^{5}}$	${\displaystyle \color {green}u_{5}^{5}}$	${\displaystyle \cdots }$
${\displaystyle \vdots }$	${\displaystyle \vdots }$	${\displaystyle \vdots }$	${\displaystyle \vdots }$	${\displaystyle \vdots }$	${\displaystyle \ddots }$

Proof

For a sequence of functions ${\displaystyle \{u_{n}\}}$ we can find a subsequence ${\displaystyle u_{1}^{1},u_{2}^{1},\cdots }$ that converges at ${\displaystyle a_{1}}$. Out of the subsequence ${\displaystyle u_{1}^{1},u_{2}^{1},\cdots }$ we find a subsequence ${\displaystyle u_{1}^{2},u_{2}^{2},\cdots }$ that converges at ${\displaystyle a_{2}}$. Continue in this way to find sequences ${\displaystyle \{u_{n}^{k}\}}$ that converge for the point ${\displaystyle a_{k}}$, but not necessarily any of the previous points.

Construct a diagonal sequence ${\displaystyle u_{1}^{1},u_{2}^{2},u_{3}^{3},\cdots }$. This sequence converges for all ${\displaystyle a_{k}}$ because all but the first ${\displaystyle k-1}$ terms are contained in ${\displaystyle \{u_{n}^{k}\}}$. This is true for all ${\displaystyle k}$.^[8]

Theorem 2

Every sequence ${\displaystyle \{F_{n}\}}$ of probability distributions possesses a subsequence ${\displaystyle F_{n_{1}},F_{n_{2}},\cdots }$ that converges to a probability distribution ${\displaystyle F}$.^[9]

Proof

By lemma 1, we can find a subsequence ${\displaystyle \{F_{n_{k}}\}}$ that converges for all points ${\displaystyle a_{i}}$of a dense sequence. Denote the limit the sequence converges for each ${\displaystyle a_{i}}$ by ${\displaystyle G(a_{i})}$. For ${\displaystyle x}$ that are not one of ${\displaystyle a_{i}}$, ${\displaystyle G(x)}$ is the greatest lower bound of all ${\displaystyle G(a_{i})}$ for ${\displaystyle a_{i}>x}$.

${\displaystyle G}$ is increasing between 0 and 1. If we define ${\displaystyle F}$ to be equal to ${\displaystyle G}$ at all points of continuity and ${\displaystyle F(x)=G(x+)}$ if ${\displaystyle x}$ is a point of discontinuity. For a point of continuity ${\displaystyle x}$, we can find two points such that ${\displaystyle a_{i}<x<a_{j}}$, ${\displaystyle G(a_{j})-G(a_{i})<\epsilon }$ and ${\displaystyle G(a_{i})\leq F(x)\leq G(a_{j})}$.

${\displaystyle F_{n}}$ are monotone, therefore ${\displaystyle F_{n_{k}}(a_{i})\leq F_{n_{k}}(x)\leq F_{n_{k}}(a_{j})}$. The limit of ${\displaystyle \{F_{n_{k}}\}}$ differs from ${\displaystyle F(x)}$ by no more than ${\displaystyle \epsilon }$, so ${\displaystyle F_{n_{k}}\to F(x)}$ as ${\displaystyle k\to \infty }$ for all points of continuity.^[10]

Theorem 3

If ${\displaystyle F_{n}\to F}$ then the limit of every subsequence equals ${\displaystyle F}$.^[11]

Proof

By the definition of limits, ${\displaystyle |F_{n}-F|<\epsilon }$ for ${\displaystyle n>N}$. Therefore, for any subsequence ${\displaystyle \{F_{n_{k}}\}}$, ${\displaystyle |F_{n_{k}}-F|<\epsilon }$ when ${\displaystyle n_{k}\geq n>N}$.^[12]

The Laplace Transform can be seen as the continuous analogue of the power series, where ${\displaystyle \sum _{n=0}^{\infty }a_{n}x^{n}}$ becomes ${\displaystyle \int _{0}^{\infty }a(x)e^{-\lambda x}dx}$. ${\displaystyle x^{n}}$ is replaced by ${\displaystyle e^{-\lambda x}}$ because it is easier to integrate.

We define the Laplace transform of a probability distribution ${\displaystyle F}$ as ${\displaystyle \phi (\lambda )=\int _{0}^{\infty }e^{-\lambda x}F\{dx\}}$.

If ${\displaystyle F}$ has the density ${\displaystyle f}$ then we can also define the Laplace tranform of ${\displaystyle F}$ as ${\displaystyle \phi (\lambda )=\int _{0}^{\infty }e^{-\lambda x}f(x)dx}$.^[13]

If our density ${\displaystyle f}$ is zero for ${\displaystyle x<0}$, we can also see that the Laplace transform is equivalent to the expectation ${\displaystyle E(e^{-\lambda X})=\int _{0}^{\infty }e^{-\lambda x}f(x)dx}$.^[14]

Theorem 4

Distinct probability distributions have distinct Laplace transforms.^[15]

Theorem 5

Let ${\displaystyle \{F_{n}\}}$ be a sequence of probability distributions with Laplace transforms ${\displaystyle \phi _{n}}$, then ${\displaystyle \phi _{n}\to \phi }$ implies ${\displaystyle F_{n}\to F}$.^[16]

Proof

Because the Laplace transforms ${\displaystyle \phi _{n},\phi }$ are equivalent to expectations, we can use theorem 1 with ${\displaystyle u(x)=e^{-\lambda x}}$ to prove that ${\displaystyle F_{n}\to F}$ implies ${\displaystyle \phi _{n}\to \phi }$.

By theorem 2, if ${\displaystyle \{F_{n_{k}}\}}$ is a subsequence that converges to ${\displaystyle F'}$, then the Laplace transforms of ${\displaystyle F_{n_{k}}}$ converge to the Laplace transform ${\displaystyle \phi '}$ of ${\displaystyle F'}$.

By assumption in the theorem, the Laplace transforms ${\displaystyle \phi _{n}}$ converge to ${\displaystyle \phi }$, then by theorem 3 all its subsequences also converge to ${\displaystyle \phi }$ so that ${\displaystyle \phi =\phi '}$.

Because Laplace transforms are unique, ${\displaystyle F'=F}$. But this will be true for every subsequence so by theorem 3 ${\displaystyle F_{n}\to F}$.^[17]

This proof can be extended more generally to measure by defining our probability distribution in terms of the measure ${\displaystyle U_{n}}$, ${\displaystyle F_{n}={\frac {1}{\phi _{n}(\lambda )}}e^{-\lambda x}U_{n}\{dx\}}$.^[18]

Theorem 6

If ${\displaystyle U}$ has a monotone density ${\displaystyle u}$ and ${\displaystyle \rho >0}$ then ${\displaystyle u(x)\sim {\frac {\rho U(x)}{x}}}$ as ${\displaystyle x\to \infty }$.^[19]

Proof

For ${\displaystyle 0<a<b}$,

${\displaystyle \int _{a}^{b}{\frac {u(ty)t}{U(t)}}dy={\frac {U(tb)-U(ta)}{U(t)}}}$.

As ${\displaystyle t\to \infty }$ the right side tends to ${\displaystyle b^{\rho }-a^{\rho }}$. By theorem 2, there exists a sequence ${\displaystyle \{t_{k}\}\to \infty }$ such that

${\displaystyle {\frac {u(ty)t}{U(t)}}\to \psi (y)}$

Therefore

${\displaystyle \int _{a}^{b}\psi (x)dx=b^{\rho }-a^{\rho }}$

which implies ${\displaystyle \psi (y)=\rho y^{\rho -1}}$. This limit is independent of the chosen sequence ${\displaystyle \{t_{k}\}}$ therefore is true for any sequence. For ${\displaystyle y=1}$

${\displaystyle u(x)\sim {\frac {\psi (x)U(x)}{x}}={\frac {\rho U(x)}{x}}}$ as ${\displaystyle x\to \infty }$.^[20]

A subset ${\displaystyle A}$ of a set ${\displaystyle X}$ is called dense if the closure of ${\displaystyle A}$ is equivalent to ${\displaystyle X}$, i.e. ${\displaystyle {\overline {A}}=X}$. This means that if ${\displaystyle x\in X}$ then ${\displaystyle x}$ is either in the subset ${\displaystyle A}$ or is on the boundary of that subset. If it is on the boundary then we can select elements of ${\displaystyle A}$ which are arbitrarily close to ${\displaystyle x}$.

• Evertse, Jan-Hendrik (2024). Analytic Number Theory (Mastermath) Part I: Prime Number Theory. Chapter 5: Tauberian theorems (PDF).
• Feller, William (1971). An Introduction to Probability Theory and Its Applications. Volume II (2nd ed.). John Wiley & Sons.
• Mimica, Ante (2015). Laplace Transform (PDF).