Order of Sum of Von Mangoldt Function of n over n

== Theorem ==
We have:
:$\ds \sum_{n \le x} \frac {\map \Lambda n} n = \ln x + \map \OO 1$ 
where:
:$\Lambda$ is the Von Mangoldt function
:$\OO$ is big-$\OO$ notation.
== Proof ==
Consider the sum: 
:$\ds \sum_{t \le x} \sum_{m \divides t} \map \Lambda m$
We are summing over the pairs of natural numbers $\tuple {t, m}$ such that $t \le x$ and $m$ divides $t$. 
Since $m$ divides $t$ and $t \le x$, we must have $m \le x$. 
So we can equivalently sum over the pairs of natural numbers $\tuple {m, t}$ such that $m \le x$ and $m$ divides $t \le x$. 
Hence: 
:$\ds \sum_{t \le x} \sum_{m \divides t} \map \Lambda m = \sum_{m \le x} \sum_{m \divides t, \, t \le x} \map \Lambda m$
We can then write: 
:$\ds \sum_{m \le x} \sum_{m \divides t, \, t \le x} \map \Lambda m = \sum_{m \le x} \paren {\map \Lambda m \paren {\sum_{m \divides t, \, t \le x} 1} }$
From Quantity of Positive Integers Divisible by Particular Integer:
:$\ds \sum_{m \divides t, \, t \le x} 1 = \floor {\frac x m}$
From Order of Floor Function, there exists a real function $R_1 : \hointr 1 \infty \to \R$ such that: 
:$\ds \sum_{m \divides t, \, t \le x} 1 = \frac x m + \map {R_1} x$
with:
:$\map {R_1} x = \map \OO 1$
So that: 
:$\ds \sum_{m \le x} \sum_{m \divides t, \, t \le x} \map \Lambda m = \sum_{m \le x} \map \Lambda m \frac x m + \map {R_1} x \sum_{m \le x} \map \Lambda m$
Then, we have, dividing through $x$: 
:$\ds \frac 1 x \sum_{m \le x} \sum_{m \divides t, \, t \le x} \map \Lambda m = \sum_{m \le x} \frac {\map \Lambda m} m + \frac {\map {R_1} x} x \map \psi x$ 
From Arithmetic Average of Second Chebyshev Function, we have: 
:$\ds \frac 1 x \sum_{t \le x} \sum_{m \divides t} \map \Lambda m = \frac 1 x \paren {x \ln x - x + \map {R_2} x}$
for some real function $R_2 : \hointr 1 \infty \to \R$ with: 
:$\map {R_2} x = \map \OO {\map \ln {x + 1} }$
So, we have: 
:$\ds \sum_{m \le x} \frac {\map \Lambda m} m + \frac {\map {R_1} x} x \map \psi x = \ln x - 1 + \frac {\map {R_2} x} x$
We can therefore write: 
:$\ds \sum_{m \le x} \frac {\map \Lambda m} m = \ln x + \paren {\frac {\map {R_2} x} x - 1 - \frac {\map {R_1} x} x \map \psi x}$ 
It now remains to show the bracketed term is $\map \OO 1$. 
From Product of Big-O Estimates, we have: 
:$\ds \frac {\map {R_2} x} x = \map \OO {\frac {\map \ln {x + 1} } x}$ 
From Order of Natural Logarithm Function, we have: 
:$\ln x \le x$
for $x \ge 1$. 
So: 
:$\ds \frac {\map \ln {x + 1} } x \le \frac {x + 1} x$
Then we have: 
:$\ds \frac {x + 1} x = 1 + \frac 1 x \le 2$ 
So, for $x \ge 1$ we have:
:$\ds \frac {\map \ln {x + 1} } x \le 2$ 
so:
:$\ds \frac {\map \ln {x + 1} } x = \map \OO 1$
So we have, from Transitivity of Big-O Estimates: 
:$\ds \frac {\map {R_2} x} x = \map \OO 1$ 
From Second Chebyshev Function is $\map \Theta x$, we have: 
:$\ds \map \psi x = \map \OO x$ 
Combining this with: 
:$\map {R_1} x = \map \OO 1$
we have, from Product of Big-O Estimates: 
:$\ds \frac {\map {R_1} x} x \map \psi x = \map \OO 1$ 
So, from Sum of Big-O Estimates, we have: 
:$\ds \frac {\map {R_2} x} x - 1 - \frac {\map {R_1} x} x \map \psi x = \map \OO 1$
We therefore obtain: 
:$\ds \sum_{m \le x} \frac {\map \Lambda m} m = \ln x + \map \OO 1$
Category:Von Mangoldt Function