upper bound on ϑ(n)


Let ϑ(n) be the Chebyshev functionMathworldPlanetmath


Then ϑ(n)nlog4 for all n1.


By inductionMathworldPlanetmath.

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 (2m+1m)=(2m+1m+1) and each term occurs exactly once, it follows that (2m+1m)4m. Each prime p with m+1<p2m+1 divides (2m+1m), implying that their productPlanetmathPlanetmath also divides (2m+1m). Hence


By the induction hypothesis, ϑ(m+1)(m+1)log4 and so ϑ(2m+1)(2m+1)log4. ∎


  • 1 G.H. Hardy, E.M. Wright, An Introduction to the Theory of Numbers, Oxford University Press, 1938.
Title upper bound on ϑ(n)
Canonical name UpperBoundOnvarthetan
Date of creation 2013-03-22 16:09:47
Last modified on 2013-03-22 16:09:47
Owner mps (409)
Last modified by mps (409)
Numerical id 5
Author mps (409)
Entry type TheoremMathworldPlanetmath
Classification msc 11A41