Difference between revisions of "Chebyshev theta function"
m |
m (→Estimates of the function: I didn't know if the slight refinement was due to Chebyshev) |
||
| Line 16: | Line 16: | ||
'''Theorem (Chebyshev).''' If <math>x \ge 0</math>, then <math>\vartheta(x) \le | '''Theorem (Chebyshev).''' If <math>x \ge 0</math>, then <math>\vartheta(x) \le | ||
| − | 2x</math>. | + | 2x \log 2</math>. |
''Proof.'' We induct on <math>\lfloor x \rfloor</math>. For our base | ''Proof.'' We induct on <math>\lfloor x \rfloor</math>. For our base | ||
cases, we note that for <math>0 \le x < 2</math>, we have <math>\vartheta(x) = | cases, we note that for <math>0 \le x < 2</math>, we have <math>\vartheta(x) = | ||
| − | 0 \le | + | 0 \le 2x \log 2</math>. |
Now suppose that <math>x \ge 2</math>. Let <math>n = \lfloor x \rfloor</math>. Then | Now suppose that <math>x \ge 2</math>. Let <math>n = \lfloor x \rfloor</math>. Then | ||
| Line 26: | Line 26: | ||
\prod_{\lfloor n/2 \rfloor < p \le n} p , </cmath> | \prod_{\lfloor n/2 \rfloor < p \le n} p , </cmath> | ||
so | so | ||
| − | <cmath> | + | <cmath> x \log 2 \ge \sum_{\lfloor n/2 \rfloor < p \le n} \log p |
= \vartheta{x} - \vartheta{\lfloor n/2 \rfloor} | = \vartheta{x} - \vartheta{\lfloor n/2 \rfloor} | ||
| − | \ge \vartheta{x} - 2\lfloor n/2 \rfloor \ge \vartheta{x} - x , </cmath> | + | \ge \vartheta{x} - 2\lfloor n/2 \rfloor \log 2 \ge \vartheta{x} - x \log 2x , </cmath> |
by inductive hypothesis. Therefore | by inductive hypothesis. Therefore | ||
| − | <cmath> 2x \ge \vartheta(x), </cmath> | + | <cmath> 2x \log 2 \ge \vartheta(x), </cmath> |
as desired. <math>\blacksquare</math> | as desired. <math>\blacksquare</math> | ||
Revision as of 22:43, 29 March 2009
Chebyshev's theta function, denoted 
or sometimes
, is a function of use in analytic number theory.
It is defined thus, for real 
:
![\[\vartheta(x) = \sum_{p \le x} \log x ,\]](http://latex.artofproblemsolving.com/c/8/1/c81b371b6de7f02f4385bf81bb3d8535e35b7737.png)
where the sum ranges over all primes less than
.
Estimates of the function
The function 
is asymptotically equivalent to
(the prime counting function) and . This result
is the Prime Number Theorem, and all known proofs are rather
involved.
However, we can obtain a simpler bound on .
Theorem (Chebyshev). If 
, then 
.
Proof. We induct on 
. For our base
cases, we note that for 
, we have 
.
Now suppose that 
. Let 
. Then
![\[2^x \ge 2^n \ge \binom{n}{\lfloor n/2 \rfloor} \ge \prod_{\lfloor n/2 \rfloor < p \le n} p ,\]](http://latex.artofproblemsolving.com/4/c/0/4c02f1710b662c21347a8a98f0c1c9970e1e0983.png)
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} - 2\lfloor n/2 \rfloor \log 2 \ge \vartheta{x} - x \log 2x ,\]](http://latex.artofproblemsolving.com/c/6/5/c658c1920a1f12d77dec8fd1df2c51e009d67237.png)
by inductive hypothesis. Therefore
![\[2x \log 2 \ge \vartheta(x),\]](http://latex.artofproblemsolving.com/f/6/d/f6d7c8e8dc96d0c3d8487b3b068223986a0fcc31.png)
as desired. 
