The Prime Number Theorem

Date: 05/26/2008 at 21:20:54
From: Benjamin
Subject: the prime number theorem

Which one of the following formulas is true?  They are both given, one
after the other, in the book "Gamma" by Julian Havill.  Obviously both
cannot be true.

Let pi(x) be the number of primes below x.  Then

1. pi(x) - pi(sqrt(x)) + 1 = [prod over primes p, p<=x of (1-1/p)]x

or 

2. pi(x) = same right hand side as above.

The second formula is used to derive a form of the prime number
theorem, i.e. 

pi(x) = 2x e^gamma/ln(x)

Does it simply neglect pi(sqrt(x)) compared to pi(x)?

Date: 05/27/2008 at 00:27:56
From: Doctor Jordan
Subject: Re: the prime number theorem

Hi Benjamin,

We will use f(x) ~ g(x) to mean f(x)/g(x) goes to 1 as x goes to
infinity.  For example,

  x^2 + x ~ x^2

since

  x^2    x         1
  --- + --- = 1 + ---
  x^2   x^2        x

goes to 1 as x goes to infinity.

In particular this example shows us that two functions being
asymptotic (that is how we say ~) does not mean they are equal, since
of course x^2 + x is not equal to x^2.

The prime number theorem tells us that pi(x) ~ x/ln(x).

I will show that pi(x) - pi(sqrt(x)) also is asymptotic to x/ln(x).

  pi(x) - pi(sqrt(x))    pi(x)    pi(sqrt(x)) * ln(x)
  ------------------- = ------- - -------------------
        x/ln(x)         x/ln(x)            x

But pi(sqrt(x)) is certainly <= sqrt(x), since the number of primes <=
x is upper bounded by x itself.

Thus 

  pi(sqrt(x)) * ln(x)    sqrt(x) * ln(x)
  ------------------- <= ---------------
           x                    x

Multiplying the right side by sqrt(x)/sqrt(x) gives

   ln(x)
  ------
  sqrt(x)

which goes to 0 as x goes to infinity, by L'Hospital's rule.

Therefore

  pi(x) - pi(sqrt(x))
  -------------------
        x/ln(x)

goes to 1 as x goes to infinity, which shows that pi(x) - pi(sqrt(x))
is asymptotic to x/ln(x).

Therefore pi(x) is asymptotic to x/ln(x) and so is 
pi(x) - pi(sqrt(x)).

Does this answer your question?

- Doctor Jordan, The Math Forum
  http://mathforum.org/dr.math/