Second Chebyshev Function is Theta of x

== Theorem ==
We have: 
:$\map \psi x = \map \Theta x$
where:
:$\Theta$ is $\Theta$ notation
:$\psi$ is the second Chebyshev function.
== Proof ==
We show that: 
:$\map \psi x = \map \OO x$
and:
:$x = \map \OO {\map \psi x}$
where $\OO$ denotes big-$\OO$ notation.
Note that: 
Note that: 
Clearly we have: 
:$\ds \sum_{n \mathop \le x} \map \psi {\frac x n} = \sum_{m \mathop \le x, \, \text {$m$ odd} } \map \psi {\frac x m} + \sum_{m \mathop \le x, \, \text {$m$ even} } \map \psi {\frac x m}$
So:
From Second Chebyshev Function is Increasing: 
:$\map \psi {\dfrac x n} - \map \psi {\dfrac x m} \ge 0$
when $n < m$. 
Suppose that $\floor x$ is an odd integer.
Then we have: 
Similarly, if $\floor x$ is a even integer, we have: 
We now show that: 
:$\ds \sum_{m \mathop \le x, \, m \text { odd} } \map \psi {\frac x m} - \sum_{m \mathop \le x, \, m \text { even} } \map \psi {\frac x m} = \map \OO x$
From the definition of big-$\OO$ notation, there exists some $x_1 \in \R$ and positive real number $C$ such that: 
:$\ds \sum_{m \mathop \le x, \, m \text { odd} } \map \psi {\frac x m} - \sum_{m \mathop \le x, \, m \text { even} } \map \psi {\frac x m} \le x \ln 2 + C \map \ln {x + 1}$
for $x \ge x_1$.
Then we have: 
As shown in Order of Natural Logarithm Function, for $x \ge 1$ we have: 
:$C \ln x \le C x$
Let:
:$x_0 = \max \set {x_1, 1}$
So for $x \ge x_0$, we have:
Let:
:$A = C + \paren {C + 1} \ln 2$
So, for $x \ge x_0$ we have: 
:$0 \le \map \psi x - \map \psi {x/2} \le A x$
So, for $x \ge 2^{k - 1} x_0$, we have: 
:$0 \le \map \psi {\dfrac x {2^{k - 1} } } - \map \psi {\dfrac x {2^k} } \le \dfrac {A x} {2^{k - 1} }$
Note that for $x < 2$, we have: 
:$\map \psi x = 0$
so for:
:$k \ge \dfrac {\ln x} {\ln 2}$
we have: 
:$\map \psi {\dfrac x {2^{k - 1} } } - \map \psi {\dfrac x {2^k} } = 0$
Set:
:$N = \floor {\dfrac {\ln x} {\ln 2} } + 1$
So we have, for $x \ge 2^{N - 1} x_0$:
So by the definition of big-O notation, we have: 
:$\map \psi x = \map \OO x$
Suppose that $\floor x$ is an odd integer.
Then:
Similarly if $\floor x$ is an even integer, we have: 
Since: 
:$\ds \sum_{m \mathop \le x, \, m \text { odd} } \map \psi {\frac x m} - \sum_{m \mathop \le x, \, m \text { even} } \map \psi {\frac x m} = x \ln 2 + \map \OO {\map \ln {x + 1} }$
From the definition of big-$\OO$ notation, there exists a positive real number $C$ and $x_2 \in \R$ such that: 
:$\ds \sum_{m \mathop \le x, \, m \text { odd} } \map \psi {\frac x m} - \sum_{m \mathop \le x, \, m \text { even} } \map \psi {\frac x m} \ge x \ln 2 - C \map \ln {x + 1}$
for $x \ge x_2$.
 assume that $C > 1$. 
We then have for $x \ge \max \set {x_2, 1}$: 
We show that for sufficiently large $x$ we have: 
:$x \ln 2 - x^{1/C} \ge \dfrac {\ln 2} 2 x$
This inequality holds : 
:$\dfrac {\ln 2} 2 \ge x^{\dfrac 1 C - 1}$
That is: 
:$x^{1 - \dfrac 1 C} \ge \dfrac 2 {\ln 2}$
Since $C > 1$, we have:
:$1 - \dfrac 1 C > 0$
and so: 
:$\paren {1 - \dfrac 1 C} \ln x \ge \map \ln {\dfrac 2 {\ln 2} }$
That is: 
:$x \ge \map \exp {\dfrac {\map \ln {\frac 2 {\ln 2} } } {1 - \frac 1 C} } = x_3$
Then for $x \ge \max \set {x_3, x_2, 1}$, we have: 
:$x \ln 2 - C \ln 2 - x^{1/C} \ge x \dfrac {\ln 2} 2 - C \ln 2$
If also $x \ge 4 C$, we have: 
:$x \dfrac {\ln 2} 2 - C \ln 2 \ge x \dfrac {\ln 2} 4$
Let:
:$x_4 = \max \set {x_3, x_2, 4 C}$
Then for $x \ge x_4$, we have: 
:$\ds \sum_{m \mathop \le x, \, m \text { odd} } \map \psi {\frac x m} - \sum_{m \mathop \le x, \, m \text { even} } \map \psi {\frac x m} \ge x \frac {\ln 2} 4$
So:
:$\map \psi x \ge x \dfrac {\ln 2} 4$
for $x \ge x_4$.
That is: 
:$\dfrac 4 {\ln 2} \map \psi x \ge x$ 
From the definition of big-$\OO$ notation, we have: 
:$x = \map \OO {\map \psi x}$
Since also: 
:$\map \psi x = \map \OO x$
we have: 
:$\map \psi x = \map \Theta x$
Category:Second Chebyshev Function
Category:Theta Notation