Riemann-Stieltjes Integration and Asymptotics

Cover image
πŸ› A Project Cauchy Op-ed

Named after French mathematician Augustin-Louis Cauchy, Project Cauchy column is where I invite some of the HFI Programming club members to provide neat proofs or explanations about some number theory puzzles. I highly suggest that you read these articles with a pencil and paper so you can sketch things out and scribble solutions to exercises as you come across them. This time, Travor presented me one of the neatest proofs to the prime number theorem.

As the title suggests, today we are going to do some integral calculus. First, let's recall the definition of Riemann integral:

Riemann Integral and Its Formal Definition

Traditionally, an integral of some function f(x)f(x) over some interval [a,b][a,b] is defined as the signed area of f(x)f(x) over the curve:

∫abf(x)dxβ‰œSignedΒ areaΒ underΒ f(x)Β whereΒ x∈[a,b]\int_a^bf(x)\mathrm dx\triangleq\text{Signed area under $f(x)$ where $x\in[a,b]$}

and Riemann integral is one way to define it rigorously. Particularly, we define it as the sum of the areas of tiny rectangles:

∫abf(x)dxβ‰ˆβˆ‘k=1Nf(ΞΎk)(xkβˆ’xkβˆ’1)\int_a^bf(x)\mathrm dx\approx\sum_{k=1}^Nf(\xi_k)(x_k-x_{k-1})

where ΞΎk\xi_k are sampled in [xkβˆ’1,xk][x_{k-1},x_k] and the increasing sequence {xk}\{x_k\} is called a partition of the interval [a,b][a,b]:

a=x0≀x1≀x2≀⋯≀xN=ba=x_0\le x_1\le x_2\le\cdots\le x_N=b

To formalize Riemann integral, let's define the mesh⁑{xn}\operatorname{mesh}\{x_n\} as the length of the maximum of interval in a partition {xn}\{x_n\}:

mesh⁑{xn}β‰œmax⁑1≀n≀N(xnβˆ’xnβˆ’1)\operatorname{mesh}\{x_n\}\triangleq\max_{1\le n\le N}(x_n-x_{n-1})

Then we say that some function f(x)f(x) is Riemann integrable if for all Ξ΅>0\varepsilon>0, there exists Ξ΄>0\delta>0 such that when mesh⁑{xn}≀δ\operatorname{mesh}\{x_n\}\le\delta we always have

βˆ£βˆ‘k=1Nf(ΞΎk)(xkβˆ’xkβˆ’1)βˆ’βˆ«abf(x)dx∣<Ξ΅\left|\sum_{k=1}^Nf(\xi_k)(x_k-x_{k-1})-\int_a^bf(x)\mathrm dx\right|<\varepsilon

Alternatively, if some function f(x)f(x) is Riemann-integrable on [a,b][a,b], then the limit

lim⁑mesh⁑{xn}β†’0βˆ‘k=1Nf(ΞΎk)(xkβˆ’xkβˆ’1)\lim_{\operatorname{mesh}\{x_n\}\to0}\sum_{k=1}^Nf(\xi_k)(x_k-x_{k-1})

exists and converges to ∫abf(x)dx\int_a^bf(x)\mathrm dx.

From Riemann Integral to Riemann-Stieltjes Integral

Although Riemann integral appears to be sufficient to integrate functions, it is not friendly to integrate piecewise continuous functions. Let's first look at its definition:

∫abf(x)dg(x)=lim⁑mesh⁑{xn}β†’0I(xn,ΞΎn)β‰œlim⁑mesh⁑{xn}β†’0βˆ‘k=1Nf(ΞΎk)[g(xk)βˆ’g(xkβˆ’1)]\int_a^bf(x)\mathrm dg(x) =\lim_{\operatorname{mesh}\{x_n\}\to0}I(x_n,\xi_n)\triangleq\lim_{\operatorname{mesh}\{x_n\}\to0}\sum_{k=1}^Nf(\xi_k)[g(x_k)-g(x_{k-1})]

In order for this it to exist, we need to set up constraints on f(x)f(x) and g(x)g(x):

Theorem 1: The Riemann-Stieltjes integral ∫abfdg\int_a^bf\mathrm dg exists if ff is continuous on [a,b][a,b] and gg is of bounded variation on [a,b][a,b]

When we say gg is of bounded variation, we mean that the following quantity exists:

Var⁑[a,b](g)β‰œsupβ‘βˆ‘k∣g(xk)βˆ’g(xkβˆ’1)∣\displaystyle{\operatorname{Var}_{[a,b]}}(g)\triangleq\sup\sum_k|g(x_k)-g(x_{k-1})|

Proof. Let's define {yn}={y1,y2,…,yM}\{y_n\}=\{y_1,y_2,\dots,y_M\} as another partition of [a,b][a,b] such that {xn}\{x_n\} is its subsequence and Ξ·k\eta_k be the sampled abscissa in [yk,ykβˆ’1][y_k,y_{k-1}], so if we designate PkP_k to be the set of mm such that ymy_m's are contained in interval (xkβˆ’1,xk](x_{k-1},x_k]:

Pk={m∣xkβˆ’1<ym≀xk}P_k=\{m|x_{k-1}<y_m\le x_k\}

then we have

βˆ‘m∈Pk[g(ym)βˆ’g(ymβˆ’1)]=g(xk)βˆ’g(xkβˆ’1)\sum_{m\in P_k}[g(y_m)-g(y_{m-1})]=g(x_k)-g(x_{k-1})

which implies

I(xn,ΞΎn)=βˆ‘k=1Nβˆ‘m∈Pkf(ΞΎk)[g(ym)βˆ’g(ymβˆ’1)](1)I(x_n,\xi_n)=\sum_{k=1}^N\sum_{m\in P_k}f(\xi_k)[g(y_m)-g(y_{m-1})]\tag1 I(yn,Ξ·n)=βˆ‘k=1Nβˆ‘m∈Pkf(Ξ·m)[g(ym)βˆ’g(ymβˆ’1)](2)I(y_n,\eta_n)=\sum_{k=1}^N\sum_{m\in P_k}f(\eta_m)[g(y_m)-g(y_{m-1})]\tag2

Because f(x)f(x) is uniformly continuous within [a,b][a,b], we know that for every Ξ΅>0\varepsilon>0 there exists Ξ΄>0\delta>0 such that when s,t∈[a,b]s,t\in[a,b] satisfy ∣sβˆ’tβˆ£β‰€mesh⁑{xn}≀δ|s-t|\le\operatorname{mesh}\{x_n\}\le\delta then ∣f(s)βˆ’f(t)∣<Ξ΅|f(s)-f(t)|<\varepsilon. Accordingly, if we were to take the absolute values of (1) and (2), then

∣I(xn,ΞΎn)βˆ’I(yn,Ξ·n)∣=βˆ‘n=1Nβˆ‘m∈Pk∣f(Ξ·m)βˆ’f(ΞΎk)∣∣g(ym)βˆ’g(ymβˆ’1)βˆ£β‰€Ξ΅βˆ‘m=1M∣g(ym)βˆ’g(ymβˆ’1)βˆ£β‰€Ξ΅Var⁑[a,b](g)\begin{aligned} |I(x_n,\xi_n)-I(y_n,\eta_ n)| &=\sum_{n=1}^N\sum_{m\in P_k}|f(\eta_m)-f(\xi_k)||g(y_m)-g(y_{m-1})| \\ &\le\varepsilon\sum_{m=1}^M|g(y_m)-g(y_{m-1})| \le\varepsilon\operatorname{Var}_{[a,b]}(g) \end{aligned}

Now, let {zn}\{z_n\} be another partition of [a,b][a,b], ΞΆn\zeta_n be its correponding samples abscissa and {yn}\{y_n\} be the union of both partitions, then

∣I(xn,ΞΎn)βˆ’I(zn,ΞΆn)∣=∣I(xn,ΞΎn)βˆ’I(yn,Ξ·n)βˆ’[I(zn,ΞΆn)βˆ’I(yn,Ξ·n)]βˆ£β‰€βˆ£I(xn,ΞΎn)βˆ’I(yn,Ξ·n)∣+∣I(zn,ΞΆn)βˆ’I(yn,Ξ·n)βˆ£β‰€2Ξ΅Var⁑[a,b](g)\begin{aligned} |I(x_n,\xi_n)-I(z_n,\zeta_n)| &=|I(x_n,\xi_n)-I(y_n,\eta_n)-[I(z_n,\zeta_n)-I(y_n,\eta_n)]| \\ &\le|I(x_n,\xi_n)-I(y_n,\eta_n)|+|I(z_n,\zeta_n)-I(y_n,\eta_n)| \\ &\le2\varepsilon\operatorname{Var}_{[a,b]}(g) \end{aligned}

which indicates the validness of this theorem. β–‘\square

Properties of Riemann-Stieltjes Integral

In addition to the constraint for the Riemann-Stieltjes integral to exist, we can also transform it into a Riemann integral at specific occasions:

Theorem 2: If gβ€²(x)g'(x) exists and is continuous on [a,b][a,b] then

∫abf(x)dg(x)=∫abf(x)gβ€²(x)dx(3)\int_a^bf(x)\mathrm dg(x)=\int_a^bf(x)g'(x)\mathrm dx\tag3

Proof. Since g(x)g(x) is differentiable, we can use mean value theorem to guarantee the existence of ΞΎk∈[xkβˆ’1,xk]\xi_k\in[x_{k-1},x_k] such that g(xk)βˆ’g(xkβˆ’1)=gβ€²(Ξ·k)(xkβˆ’xkβˆ’1)g(x_k)-g(x_{k-1})=g'(\eta_k)(x_k-x_{k-1}), so

βˆ‘k=1N∣g(xk)βˆ’g(xkβˆ’1)∣=βˆ‘k=1N∣gβ€²(Ξ·k)∣(xkβˆ’xkβˆ’1)β†’βˆ«ab∣gβ€²(x)∣dx(mesh⁑{xn}β†’0)\begin{aligned} \sum_{k=1}^N|g(x_k)-g(x_{k-1})| &=\sum_{k=1}^N|g'(\eta_k)|(x_k-x_{k-1}) \\ &\to\int_a^b|g'(x)|\mathrm dx\quad(\operatorname{mesh}\{x_n\}\to0) \end{aligned}

As a result, g(x)g(x) is of bounded variation, implying the existence of the left hand side of (3).

S(xn,ΞΎn)=βˆ‘k=1Nf(ΞΎk)gβ€²(Ξ·k)(xkβˆ’xkβˆ’1)=βˆ‘k=1Nf(ΞΎk)gβ€²(ΞΎk)(xkβˆ’xkβˆ’1)⏟T1+βˆ‘k=1Nf(ΞΎk)[gβ€²(Ξ·k)βˆ’gβ€²(ΞΎk)](xkβˆ’xkβˆ’1)⏟T2\begin{aligned} S(x_n,\xi_n) &=\sum_{k=1}^Nf(\xi_k)g'(\eta_k)(x_k-x_{k-1}) \\ &=\underbrace{\sum_{k=1}^Nf(\xi_k)g'(\xi_k)(x_k-x_{k-1})}_{T_1} +\underbrace{\sum_{k=1}^Nf(\xi_k)[g'(\eta_k)-g'(\xi_k)](x_k-x_{k-1})}_{T_2} \\ \end{aligned}

By the uniform continuity of gβ€²(x)g'(x), we know that for all Ξ΅>0\varepsilon>0 there exists Ξ΄>0\delta>0 such that ∣gβ€²(s)βˆ’gβ€²(t)∣<Ξ΅|g'(s)-g'(t)|<\varepsilon whenever ∣sβˆ’t∣<Ξ΄|s-t|<\delta, indicating T1β†’βˆ«abfgβ€²T_1\to\int_a^bfg' and T2β†’0T_2\to0 as mesh⁑{xn}β†’0\operatorname{mesh}\{x_n\}\to0. Accordingly, we arrive at the conclusion that

∫abf(x)dg(x)=∫abf(x)gβ€²(x)dx\int_a^bf(x)\mathrm dg(x)=\int_a^bf(x)g'(x)\mathrm dx

thus completing the proof. β–‘\square

In addition, we can also apply integration by parts on Riemann-Stieltjes integrals. Particularly, if we assume ff has a continuous derivative and gg is of bounded variation on [a,b][a,b], then

∫abf(x)dg(x)=f(x)g(x)∣qbβˆ’βˆ«abg(x)fβ€²(x)dx\int_a^bf(x)\mathrm dg(x)=f(x)g(x)|_q^b-\int_a^bg(x)f'(x)\mathrm dx

Riemann-Stieltjes Integral and Partial Summation

Let h(n)h(n) be some arithmetic function and H(x)H(x) be its summatory function

R(x)=βˆ‘n≀xr(n)(4)R(x)=\sum_{n\le x}r(n)\tag4

Let f(t)f(t) have continuous derivative on [0,∞)[0,\infty) and b>a>0b>a>0 then we have

∫abf(x)dR(x)=βˆ‘k=1Nf(ΞΎk)[R(xk)βˆ’R(xkβˆ’1)]\int_a^bf(x)\mathrm dR(x)=\sum_{k=1}^Nf(\xi_k)[R(x_k)-R(x_{k-1})]

where we require that mesh{xn}<1\mathrm{mesh}\{x_n\}<1. Recall (4), we observe that R(x)R(x) is a step function that only jumps at integer values, so we only need to sum over knk_n's such that n∈(xknβˆ’1,xkn]n\in(x_{k_n-1},x_{k_n}]. Hence, this integral becomes a summation that sums over integers values in (a,b](a,b]:

∫abf(x)dR(x)=βˆ‘a<n≀bf(ΞΎkn)r(n)=βˆ‘a<n≀bf(n)r(n)+βˆ‘a<n≀b[f(ΞΎkn)βˆ’f(n)]r(n)\begin{aligned} \int_a^bf(x)\mathrm dR(x) &=\sum_{a<n\le b}f(\xi_{k_n})r(n) \\ &=\sum_{a<n\le b}f(n)r(n)+\sum_{a<n\le b}[f(\xi_{k_n})-f(n)]r(n) \\ \end{aligned}

Since ff is uniformly continuous on [a,b][a,b], we have that ∣f(x)βˆ’f(y)∣<Ξ΄|f(x)-f(y)|<\delta when ever ∣xβˆ’y∣<Ξ΅|x-y|<\varepsilon, thus the second summation is of O(Ξ΄)\mathcal O(\delta), leaving us

∫abf(x)dR(x)=βˆ‘a<n≀bf(n)r(n)(5)\int_a^bf(x)\mathrm dR(x)=\sum_{a<n\le b}f(n)r(n)\tag5

Employing (5) in different situations can give us plentiful brilliant results. Let's have a look at some of them:

Asymptotic Expansions

It was well-known that the harmonic series 1+12+13+β‹―1+\frac12+\frac13+\cdots diverges, and we can provide a formal proof using Riemann-Stieltjes integral:

βˆ‘n≀N1n=∫1βˆ’Ξ΅Nd⌊xβŒ‹x=⌊xβŒ‹x∣1βˆ’Ξ΅N+∫1βˆ’Ξ΅N⌊xβŒ‹x2dx=∫1βˆ’Ξ΅Ndxx+1βˆ’βˆ«1βˆ’Ξ΅N{x}x2dx=∫1Ndxx+1βˆ’βˆ«1N{x}x2dx=log⁑N+1βˆ’βˆ«1∞{x}x2dx+∫N∞{x}x2dx=log⁑N+Ξ³+O(1N)\begin{aligned} \sum_{n\le N}\frac1n &=\int_{1-\varepsilon}^N{\mathrm d\lfloor x\rfloor\over x} \\ &=\left.\lfloor x\rfloor\over x\right|_{1-\varepsilon}^N+\int_{1-\varepsilon}^N{\lfloor x\rfloor\over x^2}\mathrm dx \\ &=\int_{1-\varepsilon}^N{\mathrm dx\over x}+1-\int_{1-\varepsilon}^N{\{x\}\over x^2}\mathrm dx \\ &=\int_1^N{\mathrm dx\over x}+1-\int_1^N{\{x\}\over x^2}\mathrm dx \\ &=\log N+1-\int_1^\infty{\{x\}\over x^2}\mathrm dx+\int_N^\infty{\{x\}\over x^2}\mathrm dx \\ &=\log N+\gamma+\mathcal O\left(\frac1N\right) \end{aligned}

Since log⁑Nβ†’βˆž\log N\to\infty as Nβ†’βˆžN\to\infty, we conclude that the harmonic series diverges.

Evaluation of an Interesting Series

βˆ‘n=1∞(βˆ’1)nlog⁑nn\sum_{n=1}^\infty{(-1)^n\log n\over n}

Now, let's first consider the finite case:

βˆ‘n=1N(βˆ’1)nlog⁑nn=2βˆ‘n≀N/2log⁑(2n)2nβˆ’βˆ‘n≀Nlog⁑nn+O(log⁑NN)=βˆ‘n≀N/2log⁑2+log⁑nnβˆ’βˆ‘n≀Nlog⁑nn+O(log⁑NN)=log⁑2βˆ‘n≀N/21nβˆ’βˆ‘N/2<n≀Nlog⁑nn+O(log⁑NN)\begin{aligned} \sum_{n=1}^N{(-1)^n\log n\over n} &=2\sum_{n\le N/2}{\log(2n)\over2n}-\sum_{n\le N}{\log n\over n}+\mathcal O\left(\log N\over N\right) \\ &=\sum_{n\le N/2}{\log2+\log n\over n}-\sum_{n\le N}{\log n\over n}+\mathcal O\left(\log N\over N\right) \\ &=\log2\sum_{n\le N/2}\frac1n-\sum_{N/2<n\le N}{\log n\over n}+\mathcal O\left(\log N\over N\right) \\ \end{aligned}

In fact, using Riemann-Stieltjes integral, we can show

βˆ‘N/2<n≀Nlog⁑nn=∫N/2Nlog⁑xxd⌊xβŒ‹=Nlog⁑(N)βˆ’Nlog⁑(N/2)Nβˆ’βˆ«N/2N[xβˆ’{x}]d(log⁑xx)+O(1n)=log⁑2βˆ’βˆ«N/2N(1βˆ’log⁑xx)dx+O(log⁑NN)=∫N/2Nlog⁑xxdx+O(log⁑NN)=12[log⁑2Nβˆ’log⁑2(N/2)]+O(log⁑NN)=12[log⁑N+log⁑(N/2)][log⁑Nβˆ’log⁑(N/2)]+O(log⁑NN)=12log⁑2[2log⁑Nβˆ’log⁑2]+O(log⁑NN)=log⁑2log⁑Nβˆ’12log⁑22+O(log⁑NN)\begin{aligned} \sum_{N/2<n\le N}{\log n\over n} &=\int_{N/2}^N{\log x\over x}\mathrm d\lfloor x\rfloor \\ &={N\log(N)-N\log(N/2)\over N}-\int_{N/2}^N[x-\{x\}]\mathrm d\left(\log x\over x\right)+\mathcal O\left(\frac1n\right) \\ &=\log2-\int_{N/2}^N\left({1-\log x\over x}\right)\mathrm dx+\mathcal O\left(\log N\over N\right) \\ &=\int_{N/2}^N{\log x\over x}\mathrm dx+\mathcal O\left(\log N\over N\right) \\ &=\frac12[\log^2N-\log^2(N/2)]+\mathcal O\left(\log N\over N\right) \\ &=\frac12[\log N+\log(N/2)][\log N-\log(N/2)]+\mathcal O\left(\log N\over N\right) \\ &=\frac12\log2[2\log N-\log2]+\mathcal O\left(\log N\over N\right) \\ &=\log2\log N-\frac12\log^22+\mathcal O\left(\log N\over N\right) \end{aligned}

Now, employing this obtained identity and the asymptotic formula for harmonic series yields:

βˆ‘n≀N(βˆ’1)nlog⁑nn=log⁑2(log⁑N+Ξ³)βˆ’log⁑2log⁑N+12log⁑22+O(log⁑NN)=Ξ³log⁑2+12log⁑22+O(log⁑NN)\begin{aligned} \sum_{n\le N}{(-1)^n\log n\over n} &=\log2(\log N+\gamma)-\log2\log N+\frac12\log^22+\mathcal O\left(\log N\over N\right) \\ &=\gamma\log2+\frac12\log^22+\mathcal O\left(\log N\over N\right) \end{aligned}

Now, take the limit nβ†’βˆžn\to\infty on both side gives

βˆ‘nβ‰₯1(βˆ’1)nlog⁑nn=Ξ³log⁑2+12log⁑22\sum_{n\ge1}{(-1)^n\log n\over n}=\gamma\log2+\frac12\log^22

The Prime Number Theorem

If we were to define the prime indicator function

1p(n)={1nΒ isΒ aΒ prime0otherwise\mathbf1_p(n)= \begin{cases} 1 & \text{$n$ is a prime} \\ 0 & \text{otherwise} \end{cases}

Then the prime counting function can be defined as

Ο€(x)=βˆ‘p≀x1=βˆ‘n≀x1p(n)\pi(x)=\sum_{p\le x}1=\sum_{n\le x}\mathbf1_p(n)

Now, let's also define Chebyshev's function Ο‘(x)\vartheta(x):

Ο‘(x)=βˆ‘p≀xlog⁑p=βˆ‘n≀x1p(n)log⁑n\vartheta(x)=\sum_{p\le x}\log p=\sum_{n\le x}\mathbf1_p(n)\log n

Hence, we have

Ο€(x)=βˆ‘n≀x1log⁑nβ‹…1p(n)log⁑n=∫2βˆ’Ξ΅xdΟ‘(t)log⁑t=Ο‘(x)log⁑x+∫2xΟ‘(t)tlog⁑2t\begin{aligned} \pi(x) &=\sum_{n\le x}{1\over\log n}\cdot\mathbf1_p(n)\log n\\ &=\int_{2-\varepsilon}^x{\mathrm d\vartheta(t)\over\log t} \\ &={\vartheta(x)\over\log x}+\int_2^x{\vartheta(t)\over t\log^2t} \end{aligned}

It is known that Ο‘(x)∼x\vartheta(x)\sim x, so plugging it into the above equation gives

Ο€(x)∼xlog⁑x\pi(x)\sim{x\over\log x}

which is the prime number theorem.

Conclusion

To sum up, in this blog, we first define and explore the Riemann-Stieltjes integral, then use this integration technique to solve problems via asymptotic expansion. Lastly, we provide a proof for the prime number theorem.

β—€ Adversarial CamouflagePerceptual Similarity β–Ά