Analytic Combinatorics/Tauberian Theorem

Introduction

'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

Theorem from Feller.

If

$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 $\{a_{n}\}$ is monotone (always non-decreasing or always non-increasing), $0<\rho <\infty$ and $\lim _{x\to \infty }{\frac {L(cx)}{L(x)}}=1$ then

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

Proof

Proof from Feller.

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

Measure and probability distributions

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

Graph of u(x) shown as a step-function in blue. There are two examples of the measure U: U(1.5) is the area under the curve in orange, U{[2.4, 2.6]} is the area under the curve in green.

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

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

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

Property 1: Expectation or mean

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

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

Theorem 1

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

Proof

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

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

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

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

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

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

Putting it all together,

$|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 $E_{n}(u)\to E(u)$.

Property 2: Convergence

Lemma 1

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

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

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

Proof

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

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

Theorem 2

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

Proof

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

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

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

Theorem 3

If $F_{n}\to F$ then the limit of every subsequence equals $F$.

Proof

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

Laplace transform

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

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

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

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

Theorem 4

Distinct probability distributions have distinct Laplace transforms.

Continuity theorem

Theorem 5

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

Proof

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

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

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

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

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

Asymptotics of the density function

Theorem 6

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

Proof

For $0<a<b$,

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

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

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

Therefore

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

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

$u(x)\sim {\frac {\psi (x)U(x)}{x}}={\frac {\rho U(x)}{x}}$ as $x\to \infty$.

Dense

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

References

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