## [Computational Complexity] The Prime Number Theorem

Expand Messages
• Recall the Prime Number Theorem (PNT). Let &pi(n) be the number of primes that are &le n. As n goes to infinity &pi(n) approaches n/ln(n). Note that we did not
Message 1 of 1 , May 14, 2009
• 0 Attachment
Recall the Prime Number Theorem (PNT).
Let &pi(n) be the number of primes that are &le n. As n goes to infinity &pi(n) approaches n/ln(n).
Note that we did not say &theta(n/ln(n)) or n/ln(n) + &theta(1). We really said n/ln(n) However, I will have need to refer to a Weak PNT:
Let &pi(n) be the number of primes that are &le n. There exists constants A and B such that As n goes to infinity An/ln(n) &le &pi(n) &le Bn/ln(n).

In Hardy and Wright's treatement of PNT (and others) they prove the very badly named Bertrand's Postulate (BP) on the way to proving PNT.
(BP) for all n&ge 3 there is a prime between n and 2n.
1. The first proofs of PNT used Complex Analysis and were considered to be not elementary. Erdos and Selberg (ind? not ind?- see this paper for the history) found elementary proofs that question the use of the word elemenatary since they were quite difficult. It is hard to pin down the term elementary since, Oliver Sudac (TCS, The Prime Number Theorem is PRA Provable, Vol 257, NOT Online) showed there is a proof in Primitive Recurive Arithmetic which is weaker than Peano Arithmetic. An interesting article on this which IS online is by Jeremy Avigad on all of this is at Number Theory and Elementary Arithmetic.
2. Applications of PNT. Are there any? The Tao-Greene theorem (there are arb long arithmetic progressions of primes) uses it, though I suspect Weak PNT would suffice. QUESTION: Is PNT, not Weak PNT, ever actually needed?
3. WEAK PNT has a much easier proof. Here are my notes on it. The constants in this presentation are reasonable.
4. From the proof I present of the Weak PNT you can obtain that for large n there is a prime between and 3n.
5. Bertrands Postulate is used in Computer Science sometimes to show that you can get hold of a prime. (E.g., the proof that EQ has Comm Complexity O(log n).) QUESTION Is full BP ever actually needed?
6. Better results are known: Baker, Harmon, Pintz showed that, for large n, there is always a prime between n and n+n{0.525}. See their paper.
7. I have not been able to find why Bertrand's Postulate is called that. History: Conjectured by Joseph Bertrand in 1845, proven by Chebyshev in 1850.

--
Posted By GASARCH to Computational Complexity at 5/14/2009 11:13:00 AM
Your message has been successfully submitted and would be delivered to recipients shortly.