# 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.
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}$.

##### 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$.

## Notes

* ↑ Feller 1971, pp. 447.
* ↑ Feller 1971, pp. 445-447.
* ↑ Evertse 2024, pp. 152.
* ↑ Mimica 2015, pp. 19.
* ↑ Feller 1971, pp. 249.
* ↑ Feller 1971, pp. 249-250.
* ↑ Feller 1971, pp. 267.
* ↑ Feller 1971, pp. 267.
* ↑ Feller 1971, pp. 267.
* ↑ Feller 1971, pp. 267-268.
* ↑ Feller 1971, pp. 267.
* ↑ Feller 1971, pp. 267-268.
* ↑ Feller 1971, pp. 431-432.
* ↑ Feller 1971, pp. 430.
* ↑ Feller 1971, pp. 430.
* ↑ Feller 1971, pp. 431.
* ↑ Feller 1971, pp. 431.
* ↑ Feller 1971, pp. 433.
* ↑ Feller 1971, pp. 446.
* ↑ Feller 1971, pp. 446.

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