π 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:
Traditionally, an integral of some function f ( x ) f(x) f ( x ) over some interval [ a , b ] [a,b] [ a , b ] is defined as the signed area of f ( x ) f(x) f ( x ) over the curve:
β« a b f ( x ) d x β 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]$} β« a b β f ( x ) d x β SignedΒ areaΒ underΒ f ( x ) Β whereΒ x β [ 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:
β« a b f ( x ) d x β β k = 1 N f ( ΞΎ k ) ( x k β x k β 1 ) \int_a^bf(x)\mathrm dx\approx\sum_{k=1}^Nf(\xi_k)(x_k-x_{k-1}) β« a b β f ( x ) d x β k = 1 β N β f ( ΞΎ k β ) ( x k β β x k β 1 β )
where ΞΎ k \xi_k ΞΎ k β are sampled in [ x k β 1 , x k ] [x_{k-1},x_k] [ x k β 1 β , x k β ] and the increasing sequence { x k } \{x_k\} { x k β } is called a partition of the interval [ a , b ] [a,b] [ a , b ] :
a = x 0 β€ x 1 β€ x 2 β€ β― β€ x N = b a=x_0\le x_1\le x_2\le\cdots\le x_N=b a = x 0 β β€ x 1 β β€ x 2 β β€ β― β€ x N β = b
To formalize Riemann integral, let's define the mesh β‘ { x n } \operatorname{mesh}\{x_n\} m e s h { x n β } as the length of the maximum of interval in a partition { x n } \{x_n\} { x n β } :
mesh β‘ { x n } β max β‘ 1 β€ n β€ N ( x n β x n β 1 ) \operatorname{mesh}\{x_n\}\triangleq\max_{1\le n\le N}(x_n-x_{n-1}) m e s h { x n β } β 1 β€ n β€ N max β ( x n β β x n β 1 β )
Then we say that some function f ( x ) f(x) f ( x ) is Riemann integrable if for all Ξ΅ > 0 \varepsilon>0 Ξ΅ > 0 , there exists Ξ΄ > 0 \delta>0 Ξ΄ > 0 such that when mesh β‘ { x n } β€ Ξ΄ \operatorname{mesh}\{x_n\}\le\delta m e s h { x n β } β€ Ξ΄ we always have
β£ β k = 1 N f ( ΞΎ k ) ( x k β x k β 1 ) β β« a b f ( x ) d x β£ < Ξ΅ \left|\sum_{k=1}^Nf(\xi_k)(x_k-x_{k-1})-\int_a^bf(x)\mathrm dx\right|<\varepsilon β£ β£ β£ β£ β£ β£ β k = 1 β N β f ( ΞΎ k β ) ( x k β β x k β 1 β ) β β« a b β f ( x ) d x β£ β£ β£ β£ β£ β£ β < Ξ΅
Alternatively, if some function f ( x ) f(x) f ( x ) is Riemann-integrable on [ a , b ] [a,b] [ a , b ] , then the limit
lim β‘ mesh β‘ { x n } β 0 β k = 1 N f ( ΞΎ k ) ( x k β x k β 1 ) \lim_{\operatorname{mesh}\{x_n\}\to0}\sum_{k=1}^Nf(\xi_k)(x_k-x_{k-1}) m e s h { x n β } β 0 lim β k = 1 β N β f ( ΞΎ k β ) ( x k β β x k β 1 β )
exists and converges to β« a b f ( x ) d x \int_a^bf(x)\mathrm dx β« a b β f ( x ) d x .
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:
β« a b f ( x ) d g ( x ) = lim β‘ mesh β‘ { x n } β 0 I ( x n , ΞΎ n ) β lim β‘ mesh β‘ { x n } β 0 β k = 1 N f ( ΞΎ k ) [ g ( x k ) β g ( x k β 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})] β« a b β f ( x ) d g ( x ) = m e s h { x n β } β 0 lim β I ( x n β , ΞΎ n β ) β m e s h { x n β } β 0 lim β k = 1 β N β f ( ΞΎ 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) f ( x ) and g ( x ) g(x) g ( x ) :
Theorem 1 : The Riemann-Stieltjes integral β« a b f d g \int_a^bf\mathrm dg β« a b β f d g exists if f f f is continuous on [ a , b ] [a,b] [ a , b ] and g g g is of bounded variation on [ a , b ] [a,b] [ a , b ]
When we say g g g is of bounded variation, we mean that the following quantity exists:
Var β‘ [ a , b ] ( g ) β sup β‘ β k β£ g ( x k ) β g ( x k β 1 ) β£ \displaystyle{\operatorname{Var}_{[a,b]}}(g)\triangleq\sup\sum_k|g(x_k)-g(x_{k-1})| V a r [ a , b ] β ( g ) β sup k β β β£ g ( x k β ) β g ( x k β 1 β ) β£
Proof. Let's define { y n } = { y 1 , y 2 , β¦ , y M } \{y_n\}=\{y_1,y_2,\dots,y_M\} { y n β } = { y 1 β , y 2 β , β¦ , y M β } as another partition of [ a , b ] [a,b] [ a , b ] such that { x n } \{x_n\} { x n β } is its subsequence and Ξ· k \eta_k Ξ· k β be the sampled abscissa in [ y k , y k β 1 ] [y_k,y_{k-1}] [ y k β , y k β 1 β ] , so if we designate P k P_k P k β to be the set of m m m such that y m y_m y m β 's are contained in interval ( x k β 1 , x k ] (x_{k-1},x_k] ( x k β 1 β , x k β ] :
P k = { m β£ x k β 1 < y m β€ x k } P_k=\{m|x_{k-1}<y_m\le x_k\} P k β = { m β£ x k β 1 β < y m β β€ x k β }
then we have
β m β P k [ g ( y m ) β g ( y m β 1 ) ] = g ( x k ) β g ( x k β 1 ) \sum_{m\in P_k}[g(y_m)-g(y_{m-1})]=g(x_k)-g(x_{k-1}) m β P k β β β [ g ( y m β ) β g ( y m β 1 β ) ] = g ( x k β ) β g ( x k β 1 β )
which implies
I ( x n , ΞΎ n ) = β k = 1 N β m β P k f ( ΞΎ k ) [ g ( y m ) β g ( y m β 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 ( x n β , ΞΎ n β ) = k = 1 β N β m β P k β β β f ( ΞΎ k β ) [ g ( y m β ) β g ( y m β 1 β ) ] ( 1 )
I ( y n , Ξ· n ) = β k = 1 N β m β P k f ( Ξ· m ) [ g ( y m ) β g ( y m β 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 I ( y n β , Ξ· n β ) = k = 1 β N β m β P k β β β f ( Ξ· m β ) [ g ( y m β ) β g ( y m β 1 β ) ] ( 2 )
Because f ( x ) f(x) f ( x ) is uniformly continuous within [ a , b ] [a,b] [ a , b ] , we know that for every Ξ΅ > 0 \varepsilon>0 Ξ΅ > 0 there exists Ξ΄ > 0 \delta>0 Ξ΄ > 0 such that when s , t β [ a , b ] s,t\in[a,b] s , t β [ a , b ] satisfy β£ s β t β£ β€ mesh β‘ { x n } β€ Ξ΄ |s-t|\le\operatorname{mesh}\{x_n\}\le\delta β£ s β t β£ β€ m e s h { x n β } β€ Ξ΄ then β£ f ( s ) β f ( t ) β£ < Ξ΅ |f(s)-f(t)|<\varepsilon β£ f ( s ) β f ( t ) β£ < Ξ΅ . Accordingly, if we were to take the absolute values of (1) and (2), then
β£ I ( x n , ΞΎ n ) β I ( y n , Ξ· n ) β£ = β n = 1 N β m β P k β£ f ( Ξ· m ) β f ( ΞΎ k ) β£ β£ g ( y m ) β g ( y m β 1 ) β£ β€ Ξ΅ β m = 1 M β£ g ( y m ) β g ( y m β 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} β£ I ( x n β , ΞΎ n β ) β I ( y n β , Ξ· n β ) β£ β = n = 1 β N β m β P k β β β β£ f ( Ξ· m β ) β f ( ΞΎ k β ) β£ β£ g ( y m β ) β g ( y m β 1 β ) β£ β€ Ξ΅ m = 1 β M β β£ g ( y m β ) β g ( y m β 1 β ) β£ β€ Ξ΅ V a r [ a , b ] β ( g ) β
Now, let { z n } \{z_n\} { z n β } be another partition of [ a , b ] [a,b] [ a , b ] , ΞΆ n \zeta_n ΞΆ n β be its correponding samples abscissa and { y n } \{y_n\} { y n β } be the union of both partitions, then
β£ I ( x n , ΞΎ n ) β I ( z n , ΞΆ n ) β£ = β£ I ( x n , ΞΎ n ) β I ( y n , Ξ· n ) β [ I ( z n , ΞΆ n ) β I ( y n , Ξ· n ) ] β£ β€ β£ I ( x n , ΞΎ n ) β I ( y n , Ξ· n ) β£ + β£ I ( z n , ΞΆ n ) β I ( y n , Ξ· 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} β£ I ( x n β , ΞΎ n β ) β I ( z n β , ΞΆ n β ) β£ β = β£ I ( x n β , ΞΎ n β ) β I ( y n β , Ξ· n β ) β [ I ( z n β , ΞΆ n β ) β I ( y n β , Ξ· n β ) ] β£ β€ β£ I ( x n β , ΞΎ n β ) β I ( y n β , Ξ· n β ) β£ + β£ I ( z n β , ΞΆ n β ) β I ( y n β , Ξ· n β ) β£ β€ 2 Ξ΅ V a r [ a , b ] β ( g ) β
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) g β² ( x ) exists and is continuous on [ a , b ] [a,b] [ a , b ] then
β« a b f ( x ) d g ( x ) = β« a b f ( x ) g β² ( x ) d x (3) \int_a^bf(x)\mathrm dg(x)=\int_a^bf(x)g'(x)\mathrm dx\tag3 β« a b β f ( x ) d g ( x ) = β« a b β f ( x ) g β² ( x ) d x ( 3 )
Proof. Since g ( x ) g(x) g ( x ) is differentiable, we can use mean value theorem to guarantee the existence of ΞΎ k β [ x k β 1 , x k ] \xi_k\in[x_{k-1},x_k] ΞΎ k β β [ x k β 1 β , x k β ] such that g ( x k ) β g ( x k β 1 ) = g β² ( Ξ· k ) ( x k β x k β 1 ) g(x_k)-g(x_{k-1})=g'(\eta_k)(x_k-x_{k-1}) g ( x k β ) β g ( x k β 1 β ) = g β² ( Ξ· k β ) ( x k β β x k β 1 β ) , so
β k = 1 N β£ g ( x k ) β g ( x k β 1 ) β£ = β k = 1 N β£ g β² ( Ξ· k ) β£ ( x k β x k β 1 ) β β« a b β£ g β² ( x ) β£ d x ( mesh β‘ { x n } β 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} k = 1 β N β β£ g ( x k β ) β g ( x k β 1 β ) β£ β = k = 1 β N β β£ g β² ( Ξ· k β ) β£ ( x k β β x k β 1 β ) β β« a b β β£ g β² ( x ) β£ d x ( m e s h { x n β } β 0 ) β
As a result, g ( x ) g(x) g ( x ) is of bounded variation, implying the existence of the left hand side of (3).
S ( x n , ΞΎ n ) = β k = 1 N f ( ΞΎ k ) g β² ( Ξ· k ) ( x k β x k β 1 ) = β k = 1 N f ( ΞΎ k ) g β² ( ΞΎ k ) ( x k β x k β 1 ) β T 1 + β k = 1 N f ( ΞΎ k ) [ g β² ( Ξ· k ) β g β² ( ΞΎ k ) ] ( x k β x k β 1 ) β T 2 \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} S ( x n β , ΞΎ n β ) β = k = 1 β N β f ( ΞΎ k β ) g β² ( Ξ· k β ) ( x k β β x k β 1 β ) = T 1 β k = 1 β N β f ( ΞΎ k β ) g β² ( ΞΎ k β ) ( x k β β x k β 1 β ) β β + T 2 β k = 1 β N β f ( ΞΎ k β ) [ g β² ( Ξ· k β ) β g β² ( ΞΎ k β ) ] ( x k β β x k β 1 β ) β β β
By the uniform continuity of g β² ( x ) g'(x) g β² ( x ) , we know that for all Ξ΅ > 0 \varepsilon>0 Ξ΅ > 0 there exists Ξ΄ > 0 \delta>0 Ξ΄ > 0 such that β£ g β² ( s ) β g β² ( t ) β£ < Ξ΅ |g'(s)-g'(t)|<\varepsilon β£ g β² ( s ) β g β² ( t ) β£ < Ξ΅ whenever β£ s β t β£ < Ξ΄ |s-t|<\delta β£ s β t β£ < Ξ΄ , indicating T 1 β β« a b f g β² T_1\to\int_a^bfg' T 1 β β β« a b β f g β² and T 2 β 0 T_2\to0 T 2 β β 0 as mesh β‘ { x n } β 0 \operatorname{mesh}\{x_n\}\to0 m e s h { x n β } β 0 . Accordingly, we arrive at the conclusion that
β« a b f ( x ) d g ( x ) = β« a b f ( x ) g β² ( x ) d x \int_a^bf(x)\mathrm dg(x)=\int_a^bf(x)g'(x)\mathrm dx β« a b β f ( x ) d g ( x ) = β« a b β f ( x ) g β² ( x ) d x
thus completing the proof. β‘ \square β‘
In addition, we can also apply integration by parts on Riemann-Stieltjes integrals. Particularly, if we assume f f f has a continuous derivative and g g g is of bounded variation on [ a , b ] [a,b] [ a , b ] , then
β« a b f ( x ) d g ( x ) = f ( x ) g ( x ) β£ q b β β« a b g ( x ) f β² ( x ) d x \int_a^bf(x)\mathrm dg(x)=f(x)g(x)|_q^b-\int_a^bg(x)f'(x)\mathrm dx β« a b β f ( x ) d g ( x ) = f ( x ) g ( x ) β£ q b β β β« a b β g ( x ) f β² ( x ) d x
Riemann-Stieltjes Integral and Partial Summation
Let h ( n ) h(n) h ( n ) be some arithmetic function and H ( x ) H(x) H ( x ) be its summatory function
R ( x ) = β n β€ x r ( n ) (4) R(x)=\sum_{n\le x}r(n)\tag4 R ( x ) = n β€ x β β r ( n ) ( 4 )
Let f ( t ) f(t) f ( t ) have continuous derivative on [ 0 , β ) [0,\infty) [ 0 , β ) and b > a > 0 b>a>0 b > a > 0 then we have
β« a b f ( x ) d R ( x ) = β k = 1 N f ( ΞΎ k ) [ R ( x k ) β R ( x k β 1 ) ] \int_a^bf(x)\mathrm dR(x)=\sum_{k=1}^Nf(\xi_k)[R(x_k)-R(x_{k-1})] β« a b β f ( x ) d R ( x ) = k = 1 β N β f ( ΞΎ k β ) [ R ( x k β ) β R ( x k β 1 β ) ]
where we require that m e s h { x n } < 1 \mathrm{mesh}\{x_n\}<1 m e s h { x n β } < 1 . Recall (4), we observe that R ( x ) R(x) R ( x ) is a step function that only jumps at integer values, so we only need to sum over k n k_n k n β 's such that n β ( x k n β 1 , x k n ] n\in(x_{k_n-1},x_{k_n}] n β ( x k n β β 1 β , x k n β β ] . Hence, this integral becomes a summation that sums over integers values in ( a , b ] (a,b] ( a , b ] :
β« a b f ( x ) d R ( x ) = β a < n β€ b f ( ΞΎ k n ) r ( n ) = β a < n β€ b f ( n ) r ( n ) + β a < n β€ b [ f ( ΞΎ k n ) β 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} β« a b β f ( x ) d R ( x ) β = a < n β€ b β β f ( ΞΎ k n β β ) r ( n ) = a < n β€ b β β f ( n ) r ( n ) + a < n β€ b β β [ f ( ΞΎ k n β β ) β f ( n ) ] r ( n ) β
Since f f f is uniformly continuous on [ a , b ] [a,b] [ a , b ] , we have that β£ f ( x ) β f ( y ) β£ < Ξ΄ |f(x)-f(y)|<\delta β£ f ( x ) β f ( y ) β£ < Ξ΄ when ever β£ x β y β£ < Ξ΅ |x-y|<\varepsilon β£ x β y β£ < Ξ΅ , thus the second summation is of O ( Ξ΄ ) \mathcal O(\delta) O ( Ξ΄ ) , leaving us
β« a b f ( x ) d R ( x ) = β a < n β€ b f ( n ) r ( n ) (5) \int_a^bf(x)\mathrm dR(x)=\sum_{a<n\le b}f(n)r(n)\tag5 β« a b β f ( x ) d R ( x ) = a < n β€ b β β f ( n ) r ( n ) ( 5 )
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 + 1 2 + 1 3 + β― 1+\frac12+\frac13+\cdots 1 + 2 1 β + 3 1 β + β― diverges, and we can provide a formal proof using Riemann-Stieltjes integral:
β n β€ N 1 n = β« 1 β Ξ΅ N d β x β x = β x β x β£ 1 β Ξ΅ N + β« 1 β Ξ΅ N β x β x 2 d x = β« 1 β Ξ΅ N d x x + 1 β β« 1 β Ξ΅ N { x } x 2 d x = β« 1 N d x x + 1 β β« 1 N { x } x 2 d x = log β‘ N + 1 β β« 1 β { x } x 2 d x + β« N β { x } x 2 d x = log β‘ N + Ξ³ + O ( 1 N ) \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} n β€ N β β n 1 β β = β« 1 β Ξ΅ N β x d β x β β = x β x β β β£ β£ β£ β£ β£ β 1 β Ξ΅ N β + β« 1 β Ξ΅ N β x 2 β x β β d x = β« 1 β Ξ΅ N β x d x β + 1 β β« 1 β Ξ΅ N β x 2 { x } β d x = β« 1 N β x d x β + 1 β β« 1 N β x 2 { x } β d x = log N + 1 β β« 1 β β x 2 { x } β d x + β« N β β x 2 { x } β d x = log N + Ξ³ + O ( N 1 β ) β
Since log β‘ N β β \log N\to\infty log N β β as N β β N\to\infty N β β , we conclude that the harmonic series diverges.
Evaluation of an Interesting Series
β n = 1 β ( β 1 ) n log β‘ n n \sum_{n=1}^\infty{(-1)^n\log n\over n} n = 1 β β β n ( β 1 ) n log n β
Now, let's first consider the finite case:
β n = 1 N ( β 1 ) n log β‘ n n = 2 β n β€ N / 2 log β‘ ( 2 n ) 2 n β β n β€ N log β‘ n n + O ( log β‘ N N ) = β n β€ N / 2 log β‘ 2 + log β‘ n n β β n β€ N log β‘ n n + O ( log β‘ N N ) = log β‘ 2 β n β€ N / 2 1 n β β N / 2 < n β€ N log β‘ n n + O ( log β‘ N N ) \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} n = 1 β N β n ( β 1 ) n log n β β = 2 n β€ N / 2 β β 2 n log ( 2 n ) β β n β€ N β β n log n β + O ( N log N β ) = n β€ N / 2 β β n log 2 + log n β β n β€ N β β n log n β + O ( N log N β ) = log 2 n β€ N / 2 β β n 1 β β N / 2 < n β€ N β β n log n β + O ( N log N β ) β
In fact, using Riemann-Stieltjes integral, we can show
β N / 2 < n β€ N log β‘ n n = β« N / 2 N log β‘ x x d β x β = N log β‘ ( N ) β N log β‘ ( N / 2 ) N β β« N / 2 N [ x β { x } ] d ( log β‘ x x ) + O ( 1 n ) = log β‘ 2 β β« N / 2 N ( 1 β log β‘ x x ) d x + O ( log β‘ N N ) = β« N / 2 N log β‘ x x d x + O ( log β‘ N N ) = 1 2 [ log β‘ 2 N β log β‘ 2 ( N / 2 ) ] + O ( log β‘ N N ) = 1 2 [ log β‘ N + log β‘ ( N / 2 ) ] [ log β‘ N β log β‘ ( N / 2 ) ] + O ( log β‘ N N ) = 1 2 log β‘ 2 [ 2 log β‘ N β log β‘ 2 ] + O ( log β‘ N N ) = log β‘ 2 log β‘ N β 1 2 log β‘ 2 2 + O ( log β‘ N N ) \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} N / 2 < n β€ N β β n log n β β = β« N / 2 N β x log x β d β x β = N N log ( N ) β N log ( N / 2 ) β β β« N / 2 N β [ x β { x } ] d ( x log x β ) + O ( n 1 β ) = log 2 β β« N / 2 N β ( x 1 β log x β ) d x + O ( N log N β ) = β« N / 2 N β x log x β d x + O ( N log N β ) = 2 1 β [ log 2 N β log 2 ( N / 2 ) ] + O ( N log N β ) = 2 1 β [ log N + log ( N / 2 ) ] [ log N β log ( N / 2 ) ] + O ( N log N β ) = 2 1 β log 2 [ 2 log N β log 2 ] + O ( N log N β ) = log 2 log N β 2 1 β log 2 2 + O ( N log N β ) β
Now, employing this obtained identity and the asymptotic formula for harmonic series yields:
β n β€ N ( β 1 ) n log β‘ n n = log β‘ 2 ( log β‘ N + Ξ³ ) β log β‘ 2 log β‘ N + 1 2 log β‘ 2 2 + O ( log β‘ N N ) = Ξ³ log β‘ 2 + 1 2 log β‘ 2 2 + O ( log β‘ N N ) \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} n β€ N β β n ( β 1 ) n log n β β = log 2 ( log N + Ξ³ ) β log 2 log N + 2 1 β log 2 2 + O ( N log N β ) = Ξ³ log 2 + 2 1 β log 2 2 + O ( N log N β ) β
Now, take the limit n β β n\to\infty n β β on both side gives
β n β₯ 1 ( β 1 ) n log β‘ n n = Ξ³ log β‘ 2 + 1 2 log β‘ 2 2 \sum_{n\ge1}{(-1)^n\log n\over n}=\gamma\log2+\frac12\log^22 n β₯ 1 β β n ( β 1 ) n log n β = Ξ³ log 2 + 2 1 β log 2 2
The Prime Number Theorem
If we were to define the prime indicator function
1 p ( n ) = { 1 n Β isΒ aΒ prime 0 otherwise \mathbf1_p(n)=
\begin{cases}
1 & \text{$n$ is a prime} \\
0 & \text{otherwise}
\end{cases} 1 p β ( n ) = { 1 0 β n Β isΒ aΒ prime otherwise β
Then the prime counting function can be defined as
Ο ( x ) = β p β€ x 1 = β n β€ x 1 p ( n ) \pi(x)=\sum_{p\le x}1=\sum_{n\le x}\mathbf1_p(n) Ο ( x ) = p β€ x β β 1 = n β€ x β β 1 p β ( n )
Now, let's also define Chebyshev's function Ο ( x ) \vartheta(x) Ο ( x ) :
Ο ( x ) = β p β€ x log β‘ p = β n β€ x 1 p ( n ) log β‘ n \vartheta(x)=\sum_{p\le x}\log p=\sum_{n\le x}\mathbf1_p(n)\log n Ο ( x ) = p β€ x β β log p = n β€ x β β 1 p β ( n ) log n
Hence, we have
Ο ( x ) = β n β€ x 1 log β‘ n β
1 p ( n ) log β‘ n = β« 2 β Ξ΅ x d Ο ( t ) log β‘ t = Ο ( x ) log β‘ x + β« 2 x Ο ( t ) t log β‘ 2 t \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} Ο ( x ) β = n β€ x β β log n 1 β β
1 p β ( n ) log n = β« 2 β Ξ΅ x β log t d Ο ( t ) β = log x Ο ( x ) β + β« 2 x β t log 2 t Ο ( t ) β β
It is known that Ο ( x ) βΌ x \vartheta(x)\sim x Ο ( x ) βΌ x , so plugging it into the above equation gives
Ο ( x ) βΌ x log β‘ x \pi(x)\sim{x\over\log x} Ο ( x ) βΌ log x 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.