mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2009-01-22, 00:06   #1
brownkenny
 
brownkenny's Avatar
 
Jan 2009

2×3 Posts
Default 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.
brownkenny is offline   Reply With Quote
Old 2009-01-22, 12:48   #2
R.D. Silverman
 
R.D. Silverman's Avatar
 
"Bob Silverman"
Nov 2003
North of Boston

22×5×373 Posts
Default

Quote:
Originally Posted by brownkenny View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2009-01-22, 17:21   #3
brownkenny
 
brownkenny's Avatar
 
Jan 2009

2×3 Posts
Default

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.
brownkenny is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 07:29.


Sat Jul 2 07:29:26 UTC 2022 up 79 days, 5:30, 0 users, load averages: 0.94, 1.20, 1.31

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔