upper bound on $\vartheta(n)$

Theorem.

Let $\vartheta(n)$ be the Chebyshev function  $\vartheta(n)=\sum_{\begin{subarray}{c}p\leq n\\ p{\>\mathrm{prime}}\end{subarray}}\log p.$

Then $\vartheta(n)\leq n\log 4$ for all $n\geq 1$.

Proof.

The cases for $n=1$ and $n=2$ follow by inspection.

For even $n>2$, the case follows immediately from the case for $n-1$ since $n$ is not prime.

So let $n=2m+1$ with $m>0$ and consider $(1+1)^{2m+1}$ and its binomial expansion (http://planetmath.org/BinomialTheorem). Since $\displaystyle{{2m+1}\choose m}={{2m+1}\choose{m+1}}$ and each term occurs exactly once, it follows that $\displaystyle{{2m+1}\choose m}\leq 4^{m}$. Each prime $p$ with $m+1 divides ${2m+1}\choose m$, implying that their product  also divides $\displaystyle{{2m+1}\choose m}$. Hence

 $\vartheta(2m+1)-\vartheta(m+1)\leq\log{{2m+1}\choose m}\leq m\log 4.$

By the induction hypothesis, $\vartheta(m+1)\leq(m+1)\log 4$ and so $\vartheta(2m+1)\leq(2m+1)\log 4$. ∎

References

• 1 G.H. Hardy, E.M. Wright, An Introduction to the Theory of Numbers, Oxford University Press, 1938.
Title upper bound on $\vartheta(n)$ UpperBoundOnvarthetan 2013-03-22 16:09:47 2013-03-22 16:09:47 mps (409) mps (409) 5 mps (409) Theorem  msc 11A41