Chebyshev's Estimates

brownkenny · 2009-01-22, 00:06

I've been working through Tenenbaum's book "Introduction to Analytic and Probabilistic Number Theory" and I'm stuck on the proof of an upper bound for $\pi(x)$ .

For reference, it's Theorem 3 on page 11. The desired upper bound is

$\pi(x) \leq \{ \log 4 + \frac{8 \log \log n}{\log n} \} \frac{n}{\log n}$

Using the bound

$\prod_{p \leq n} p \leq 4^n$

it's easy to show that for $1 < t \leq n$ we have

$\pi(n) \leq \frac{n \log 4}{\log t} + \pi(t)$

Tenenbaum then gives the bound

$\pi(n) \leq \frac{n \log 4}{\log t} + t$

So far, so good. At this point in the proof, Tenenbaum says "The stated result follows by choosing $t = n / (\log n)^2$ " and leaves the details to the reader. As much as I've looked at it, I still can't figure out how he arrives at the desired result. Any tips/suggestions? Thanks in advance.

R.D. Silverman · 2009-01-22, 12:48

Quote:

Originally Posted by brownkenny

I've been working through Tenenbaum's book "Introduction to Analytic and Probabilistic Number Theory" and I'm stuck on the proof of an upper bound for $\pi(x)$ .

For reference, it's Theorem 3 on page 11. The desired upper bound is

$\pi(x) \leq \{ \log 4 + \frac{8 \log \log n}{\log n} \} \frac{n}{\log n}$

Using the bound

$\prod_{p \leq n} p \leq 4^n$

it's easy to show that for $1 < t \leq n$ we have

$\pi(n) \leq \frac{n \log 4}{\log t} + \pi(t)$

Tenenbaum then gives the bound

$\pi(n) \leq \frac{n \log 4}{\log t} + t$

So far, so good. At this point in the proof, Tenenbaum says "The stated result follows by choosing $t = n / (\log n)^2$ " and leaves the details to the reader. As much as I've looked at it, I still can't figure out how he arrives at the desired result. Any tips/suggestions? Thanks in advance.

After the substitution factor out n/log(n) and then use partial fractions....?
This shouldn't be too bad.

brownkenny · 2009-01-22, 17:21

Thanks for the suggestion, Dr. Silverman. When I made the substitution I wound up with a log(log(n)) term in the denominator that I'm not sure how to get rid of.

I tried estimating some more, but I still can't figure out where the factor of 8 in the term

$<br /> \frac{8 \log \log n}{\log n}<br />$

comes from.

Thanks again, Dr. Silverman.

2009-01-22, 00:06	#1
brownkenny Jan 2009 6₁₆ Posts	Chebyshev's Estimates I've been working through Tenenbaum's book "Introduction to Analytic and Probabilistic Number Theory" and I'm stuck on the proof of an upper bound for $\pi(x)$ . For reference, it's Theorem 3 on page 11. The desired upper bound is $\pi(x) \leq \{ \log 4 + \frac{8 \log \log n}{\log n} \} \frac{n}{\log n}$ Using the bound $\prod_{p \leq n} p \leq 4^n$ it's easy to show that for $1 < t \leq n$ we have $\pi(n) \leq \frac{n \log 4}{\log t} + \pi(t)$ Tenenbaum then gives the bound $\pi(n) \leq \frac{n \log 4}{\log t} + t$ So far, so good. At this point in the proof, Tenenbaum says "The stated result follows by choosing $t = n / (\log n)^2$ " and leaves the details to the reader. As much as I've looked at it, I still can't figure out how he arrives at the desired result. Any tips/suggestions? Thanks in advance.

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
The Fibonacci-Chebyshev connection	Dr Sardonicus	Number Theory Discussion Group	6	2022-01-15 12:13
Requestion for fast chebyshev theta function	danaj	Computer Science & Computational Number Theory	9	2018-03-31 14:59
P-1 B2 time estimates	henryzz	GMP-ECM	8	2009-12-31 17:51
GNFS estimates	10metreh	Factoring	48	2009-04-08 01:54
Msieve QS estimates	henryzz	Msieve	27	2009-01-21 18:37

2009-01-22, 17:21	#3
brownkenny Jan 2009 6₈ Posts	Thanks for the suggestion, Dr. Silverman. When I made the substitution I wound up with a log(log(n)) term in the denominator that I'm not sure how to get rid of. I tried estimating some more, but I still can't figure out where the factor of 8 in the term $<br /> \frac{8 \log \log n}{\log n}<br />$ comes from. Thanks again, Dr. Silverman.