AoPSWiki

Trying to get to the USAMO in 2010? Our AIME Problem Series can help you get there! Click here to enroll today!

Personal tools

Search

Toolbox

Chebyshev theta function

From AoPSWiki

Chebyshev's theta function, denoted $\vartheta$ or sometimes $\theta$ , is a function of use in analytic number theory. It is defined thus, for real $x$ : $\vartheta(x) = \sum_{p \le x} \log x ,$ where the sum ranges over all primes less than $x$ .

Estimates of the function

The function $\vartheta(x)$ is asymptotically equivalent to $\pi(x)$ (the prime counting function) and $x$ . This result is the Prime Number Theorem, and all known proofs are rather involved.

However, we can obtain a simpler bound on $\vartheta(x)$ .

Theorem (Chebyshev). If $x \ge 0$ , then $\vartheta(x) \le2x \log 2$ .

Proof. We induct on $\lfloor x \rfloor$ . For our base cases, we note that for $0 \le x < 2$ , we have $\vartheta(x) =0 \le 2x \log 2$ .

Now suppose that $x \ge 2$ . Let $n = \lfloor x \rfloor$ . Then $2^x \ge 2^n \ge \binom{n}{\lfloor n/2 \rfloor} \ge\prod_{\lfloor n/2 \rfloor < p \le n} p ,$ so $x \log 2 \ge \sum_{\lfloor n/2 \rfloor < p \le n} \log p= \vartheta{x} - \vartheta{\lfloor n/2 \rfloor}\ge \vartheta{x} - ...$ by inductive hypothesis. Therefore $2x \log 2 \ge \vartheta(x),$ as desired. $\blacksquare$

See also

Retrieved from "http://www.artofproblemsolving.com/Wiki/index.php/Chebyshev_theta_function"

Categories: Number theory | Analytic number theory

Try our innovative online adaptive learning system, Alcumus.
Over 1100 problems and 60+ video lessons. FREE!

© Copyright 2008 AoPS Incorporated. All Rights Reserved. • Foundation • Privacy • Contact Us