Thursday, May 14, 2009

The Prime Number Theorem

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) (NOTE: Comments on this post have correctly refuted this comment about ``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.

8 comments:

  1. Do we even have an application that uses the rarity of primes? The weak version of the density lower bound given in the Chebyshev argument below (which is the argument you write without the frills) seems to be sufficient in almost all CS applications:

    Thm: pi(2n) ≥ n/(1+log_2 n).

    Proof: Calculate largest power of p dividing m! as
    floor (m/p) + floor(m/p^2) + ...,
    and from this write the largest power of p dividing (2n choose n) as
    floor (2n/p) -2 floor(n/p)
    + floor (2n/p^2) -2floor(n/p^2)
    +...,
    observe that each term in this sequence is <=1 and that if there are k non-zero terms then p^k < 2n.

    Finally, use the trivial property that
    (2n choose n) > 2^n to derive that
    pi(2n) > log (2^n)/log (2n) since each distinct prime contributes < 2n to (2n choose n).

    ReplyDelete
  2. P.S. If you don't care about constants, the proof that EQ has communication complexity O(log n) does not come close to requiring Bertrand's Postulate. The same proof that
    (2n choose n) is larger than 2^n and all its prime power factors are ≤ 2n is enough. Instead of using primes, use the prime power factors of (2n choose n).

    ReplyDelete
  3. I remember reading the following paper couple of years back. It has a cute application of PNT.

    Valerie King, Garry Sagert: A Fully Dynamic Algorithm for Maintaining the Transitive Closure. J. Comput. Syst. Sci. 65(1): 150-167 (2002)

    On a related note, I recently generalized Erdos's proof. It is an elementary proof and I believe the bounds in my paper can be tightened. But I don't think it will be anywhere near the best known bounds. The purpose of my paper is to test the limits of elementary techniques. By "elementary", I meant "combinatorial".

    ReplyDelete
  4. "Note that we did not say θ(n/ln(n)) or n/ln(n) + θ(1). We really said n/ln(n)"

    I donot know what you mean
    by this. A more precise
    estimation for \pi(n)
    is \int_2^n dt/ln t,
    which is
    n/ln n + n/(ln n)^2 + ..
    so the gap between
    \pi(n) and n/ln n is much larger than a constant.
    The gap between \pi(n)
    and \int_2^n dt/ln t
    was famously conjectured by
    Riemann to be
    \sqrt{n+\epsilon}.

    ReplyDelete
  5. 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) The error term is vastly larger than &theta(1), so I'm not sure what it means to say it is "really" n/ln(n) rather than n/ln(n) + &theta(1). All the prime number theorem says is that it is (n/ln(n))(1+o(1)). In fact, the error term is on the order of n/ln(n)^2. Replacing n/ln(n) with the integral from 2 to n of dx/log(x) gives a much better approximation (assuming the Riemann hypothesis, it's within n^(1/2+o(1))).

    Erdos and Selberg found elementary proofs that question the use of the word elementary since they were quite difficult. It is hard to pin down the term elementaryNo, it's not. In this context, it has nothing whatsoever to do with difficulty. Rather, it means avoiding complex analysis (and other similarly unexpected branches of mathematics).

    Erdos and Selberg (ind? not ind?- see this paper for the history)The linked paper is a good reference. Note however that nobody has ever claimed Erdos and Selberg did things independently (which is, I assume, what "ind?" refers to). The story is far more complicated than that.

    Is PNT, not Weak PNT, ever actually needed?Ever needed for what? If you never care about constant factors, then you are unlikely to start caring here. However, if you like Knuth-style asymptotic analysis of algorithms, where you actually care about constants, then occasionally you'll need the prime number theorem.

    ReplyDelete
  6. YES, correct that I am
    incorrect about
    ``really said n/ln(n)''
    Have edited the post to indicate this.

    ReplyDelete
  7. Some information about the history of Bertrand's Postulate is given in the following excerpt from "Proofs from THE BOOK", Chapter 2.

    "A famous bound states that "the gap to the next prime cannot be larger than the number we start our search at." This is known as Bertrand's postulate, since it was conjectured and verified empirically for n < 3 000 000 by Joseph Bertrand. It was first proved for all n by Pafnuty Chebyshev in 1850. A much simpler proof was given by the Indian genius Ramanujan. Our Book Proof is by Paul Erdos: it is taken from Erdos' first published paper, which appeared in 1932, when Erdos was 19."

    ReplyDelete
  8. I believe that Bertrand used it as an unproven assumption in some work and that is why it is called postulate.

    ReplyDelete