The Prime Number TheoremDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/