Wikimore

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.^[1]

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.^[2]

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 }$ ^[3]
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$ .^[4]
${\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 )$ .^[5]
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)

.^[6]

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}$ .^[7]

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

.^[8]

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$ .^[9]
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.^[10]

Theorem 3: If $F_{n}\to F$ then the limit of every subsequence equals $F$ .^[11]
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$ .^[12]

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$ .^[13]

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$ .^[14]

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

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$ .^[16]
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

.^[17]

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\}$ .^[18]

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$ .^[19]
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

.^[20]

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

Category:Book:Analytic Combinatorics#Tauberian%20Theorem%20

[1] Feller 1971, pp. 447.

[2] Feller 1971, pp. 445-447.

[3] Evertse 2024, pp. 152.

[4] Mimica 2015, pp. 19.

[5] Feller 1971, pp. 249.

[6] Feller 1971, pp. 249-250.

[7] Feller 1971, pp. 267.

[8] Feller 1971, pp. 267.

[9] Feller 1971, pp. 267.

[10] Feller 1971, pp. 267-268.

[11] Feller 1971, pp. 267.

[12] Feller 1971, pp. 267-268.

[13] Feller 1971, pp. 431-432.

[14] Feller 1971, pp. 430.

[15] Feller 1971, pp. 430.

[16] Feller 1971, pp. 431.

[17] Feller 1971, pp. 431.

[18] Feller 1971, pp. 433.

[19] Feller 1971, pp. 446.

[20] Feller 1971, pp. 446.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]