[number theory] prove that lim x->infinity pi(x)/x=0

[RossH]

Homework Statement

I am trying to prove that lim as x->infinity of pi(x)/x =0

Homework Equations

pi(x) is the counting function that describes the number of prime numbers equal to or less than x and greater than 1.

The Attempt at a Solution

I'm really stuck about where to start here. So far I have made tables and whatnot. I wrote a program that shows an approximation of this up to 10^9, so I am certain that this is accurate. Also I have looked at the theorems that I have: infinitude of primes, infinitude of 1 (mod 4) and 3 (mod 4) primes. pi(x)~~x/ln(x) (but I'm not allowed to use this in the proof). There really aren't any solid, proveable theorems that I can use here. Any advice?

 

[grey_earl]

I think you can prove it by contradiction: assume
\lim_{n \rightarrow \infty} \frac{\pi(n)}{n} = k > 0 (it obviously cannot be smaller than zero). This then assures you that (in the limit as n goes to infinity) of a continuous set of M natural numbers there must be k M primes, but since all multiples of primes are not prime, this gives you a contradiction. I know this isn't very precise, and I may be very wrong, but perhaps it helps you.

 

[RossH]

I think you can prove it by contradiction: assume
\lim_{n \rightarrow \infty} \frac{\pi(n)}{n} = k > 0 (it obviously cannot be smaller than zero). This then assures you that (in the limit as n goes to infinity) of a continuous set of M natural numbers there must be k M primes, but since all multiples of primes are not prime, this gives you a contradiction. I know this isn't very precise, and I may be very wrong, but perhaps it helps you.

I don't think that this works. All multiples of prime numbers are not prime, but I don't see where the contradiction is here. If you have a limited continuous set, then those multiples are outside of the set. If your set is unbounded, then you have an infinitude of numbers to choose from to get the rest of your primes. Unless I am misunderstanding what you are saying here?

 

[grey_earl]

Yes, but I mean the multiples of all the prime numbers starting from 2 and extending until your set. From any continuous set of 6 numbers, say, every second is a multiple of 2 and so falls out and every third is a multiple of 3 and falls out, so in every continuous set of 6 numbers (starting from 4) there is at most one prime. By going to sets which start with a number n which is larger and larger, from all the primes you passed there is a larger possibility that the remaining numbers in the set are a multiple of some prime you passed. That was my idea, it is clearer to you now?

 

[RossH]

Yes, but I mean the multiples of all the prime numbers starting from 2 and extending until your set. From any continuous set of 6 numbers, say, every second is a multiple of 2 and so falls out and every third is a multiple of 3 and falls out, so in every continuous set of 6 numbers (starting from 4) there is at most one prime. By going to sets which start with a number n which is larger and larger, from all the primes you passed there is a larger possibility that the remaining numbers in the set are a multiple of some prime you passed. That was my idea, it is clearer to you now?

I understand this, but it's not really a proof. It's more a conjecture. Also your statement:

in every continuous set of 6 numbers (starting from 4) there is at most one prime

is incorrect: There is a category of primes "twin primes" that are neighboring odd numbers that are prime. (11, 13), (17, 19), (29, 31) for example. I think that you failed to account for when a number is a multiple of 3 and a multiple of 2.

 

[grey_earl]

I understand this, but it's not really a proof. It's more a conjecture. Also your statement: is incorrect: There is a category of primes "twin primes" that are neighboring odd numbers that are prime. (11, 13), (17, 19), (29, 31) for example. I think that you failed to account for when a number is a multiple of 3 and a multiple of 2.

Both true. Sorry for the confusion! It was just an idea, I don't know if it will work out.

 

[RossH]

Both true. Sorry for the confusion! It was just an idea, I don't know if it will work out.

No problem. I'm definitely open to ideas.

 

[Hurkyl]

Also I have looked at the theorems that I have: infinitude of primes, infinitude of 1 (mod 4) and 3 (mod 4) primes
...
There really aren't any solid, proveable theorems that I can use here. Any advice?

Doesn't that theorem give you some information about how big pi(x)/x can be for large x?

 

[RossH]

Doesn't that theorem give you some information about how big pi(x)/x can be for large x?

Well, it has to be less than .5, if that's what you are going for.

 

[Hurkyl]

Well, it has to be less than .5, if that's what you are going for.

I was. (and technically "less than or equal to .5") Can the same technique be used for a better bound?

 

[RossH]

I was. (and technically "less than or equal to .5") Can the same technique be used for a better bound?

I suppose I could use a larger modulus, say 8, but I don't have the tools yet to prove for all odd values of the modulus that there are infinite primes. (I've been shown the proof for 3 (mod 4) but only told to accept for 1 (mod 4)) Also, I have been told that 1,3,5,7 (mod 8) all have an infinite number of primes, so that would still be bounded at .5 anyway. Am I missing your point?

 

[Hurkyl]

I suppose I could use a larger modulus, say 8, but I don't have the tools yet to prove for all odd values of the modulus that there are infinite primes. (I've been shown the proof for 3 (mod 4) but only told to accept for 1 (mod 4)) Also, I have been told that 1,3,5,7 (mod 8) all have an infinite number of primes, so that would still be bounded at .5 anyway. Am I missing your point?

You didn't use the fact there were infinitely many, did you? You just need the fact that, except for 2, all primes are odd.

Powers of 2 were my first thought, but they don't help. However, there are other moduli...


(For the record, the line of attack I'm hinting at requires knowledge that \sum_p 1/p = +\infty, where p ranges over primes)

 

[RossH]

You didn't use the fact there were infinitely many, did you? You just need the fact that, except for 2, all primes are odd.

Powers of 2 were my first thought, but they don't help. However, there are other moduli...(For the record, the line of attack I'm hinting at requires knowledge that \sum_p 1/p = +\infty, where p ranges over primes)

Okay, this makes sense because there are infinitely many primes and the series 1/x increases without bound.

I guess that mod 3 will give a better bound because a prime number can only take the form of 2 (mod 3), which would imply that
<br /> \lim_{n \rightarrow \infty} \frac{\pi(n)}{n} = .33<br />

But I don't see that going anywhere productive with higher odd numbers. I'm also having trouble seeing where your series fits in here. Unless you want me to factor out the pi(x) or something like that?

 

[Hurkyl]

I guess that mod 3 will give a better bound because a prime number can only take the form of 2 (mod 3),

Actually, primes can be 1 (mod 3) also -- 7, for example.

 

[RossH]

Actually, primes can be 1 (mod 3) also -- 7, for example.

D'oh. In that case I'm stumped. Do you have another hint? I don't see where your summation comes into play.

 

[Hurkyl]

My summation won't come into play until you figure out how to use modular information to upper bound primes. The only reason I mentioned it was in case you wanted to ignore this line of attack because you weren't allowed to use the fact the sum is known to diverge.

 

[RossH]

My summation won't come into play until you figure out how to use modular information to upper bound primes.

Does this have something to do with proving that some of the modulus that are possible for a prime number may have a finite number of primes? I doubt it, because it seems like everything has an infinite number, but just a thought.

Otherwise, so far I know that prime numbers can only be (if greater than k for p (mod k):
1 (mod 2)
1,2 (mod 3)
1,3 (mod 4)
1,2,3,4 (mod 5)
1,5 (mod 6) => upper bound of pi(x)/x=.33 < .5
1,2,3,4,5,6 (mod 7)
1,3,5,7 (mod 8)
1,2,4,5,7,8 (mod 9)

I think I might have made a discovery here. The number of possible moduli decreases because 3 and 6 are divisible by 3, a factor of 9. So the number of moduli is sharply smaller if the number if k for p (mod k) is a composite number, similar to none of the modulus of 2|number working for the even moduli. Or 3, for p (mod 6). Am I on the right track?

 

[Hurkyl]

I think so.

 

[RossH]

But this would seem to be self-referential. Because I would have to prove that composite numbers have more unique factors as x->inf, which would require proving that primes are less common, which is what I am trying to prove in the first place.

 

[Hurkyl]

I don't really follow your objection. Maybe I didn't understand your post before that.


(I'm going to continue as if I understood it)

You don't have to prove anything as k -> inf. You picked a particular k, and you used it to get a useful result. When you picked 2, that told you the limit was less than or equal to 1/2. When you picked 6, that told you the limit was less than or equal to 1/3. When you picked 9, that told you the limit was less than or equal to 2/3. 9 wasn't useful; you could have ignored it if you wanted to. You could ignore 6 too if you found a better k to consider.

 

[RossH]

I don't really follow your objection. Maybe I didn't understand your post before that.(I'm going to continue as if I understood it)

You don't have to prove anything as k -> inf. You picked a particular k, and you used it to get a useful result. When you picked 2, that told you the limit was less than or equal to 1/2. When you picked 6, that told you the limit was less than or equal to 1/3. When you picked 9, that told you the limit was less than or equal to 2/3. 9 wasn't useful; you could have ignored it if you wanted to. You could ignore 6 too if you found a better k to consider.

I'm not quite sure why I am able to look at only one value for k. I'm trying to prove that the limit is 0 so any value of k that has any modulus that is congruent to any prime number will say that the limit must be >0. Unless there is a value of k that has no congruencies with 0 (unlikely). That's why I was thinking that I should look at it as k-> inf.

Unless I define k in terms of x? What if I look for a function in X that will have more and more prime factors as X grows larger, which means that the fraction of primes in terms of the modulus will get smaller. For example, F(X_i)=p1*p2*p3<X_i and F(X_j)=p1*p2*p3*p4. The more prime factors, the smaller the possibilities, as long as F(X)<X.

 

[RossH]

bump.

 

[atomthick]

Maybe you should think more about what pi(N)/N means. For example you can think of it as: If I have N numbers and I pick one of them at random what is the probability that the number is prime?

Choose the following number sequence:

n! + 2, n! + 3, ..., n! + n in this sequence there is no prime number. If you let n -> infinity you will have an infinite sequence with no prime numbers in it meaning that the probability to pick a prime number from the sequence is 0.

Maybe you can workout a proof from the above example.

 

[RossH]

Maybe you should think more about what pi(N)/N means. For example you can think of it as: If I have N numbers and I pick one of them at random what is the probability that the number is prime?

Choose the following number sequence:

n! + 2, n! + 3, ..., n! + n in this sequence there is no prime number. If you let n -> infinity you will have an infinite sequence with no prime numbers in it meaning that the probability to pick a prime number from the sequence is 0.

Maybe you can workout a proof from the above example.

I've been working with this for a couple days. My professor says that this reasoning doesn't work because there are also always primes with distance n for an arbitrary n above any given prime p. Does anybody have any other ideas?

 

[RossH]

I think I'm close. I have condensed our previous conversation into the following:

Any number prime p (mod k) can only have a remainders that are relatively prime to k, as a number would not be prime if it could be expressed as a composite plus a factor of that composite. And I know that these possible remainders demonstrate a fraction of the possible numbers that can be prime, given that in any range of numbers there must be at least one that satisfies each possible remainder (mod k). ...

But I'm not sure what I can conclude from this. I think that I need to find a way to express a number N with respect to a prime p such that p (mod N) has a constant number of possible values, K. Then as N increases, K/N -> 0. But otherwise I'm really stumped where to go.

I have considered the following: multiplying all prime numbers less than an arbitrary value and modding by that, so there are no relative primes less than a certain value except 1. But the problem with this is once you reach a certain value there can be a multiple of this as 2*p1*p2*...*pn. So I dong't think that works.

 

[atomthick]

Let's try something else.

If a number from 0 .. N is not prime it will have a factor (not necessary a prime number) lower than \sqrt{}N.

If we take the numbers from 1 to \sqrt{}N and multiply them with numbers from 2 to \sqrt{}N we will get \sqrt{}N * (\sqrt{}N - 1) = N - \sqrt{}N numbers which have a factor lower than \sqrt{}N.

So the probability to pick a number which has a factor lower than \sqrt{}N is somehow greater than (N - \sqrt{}N)/N, but we are looking for numbers that are prime and don't have a factor lower than \sqrt{}N. Our probability will be therefore lower than 1 - (N - \sqrt{}N)/N = \sqrt{}N/N which becomes 0 as N -> infinity.

Maybe you can turn this argument into a proof.

 

[Hurkyl]

I think I'm close. I have condensed our previous conversation into the following:

Any number prime p (mod k) can only have a remainders that are relatively prime to k, as a number would not be prime if it could be expressed as a composite plus a factor of that composite. And I know that these possible remainders demonstrate a fraction of the possible numbers that can be prime, given that in any range of numbers there must be at least one that satisfies each possible remainder (mod k). ...

And you even have a formula for that fraction. (invoking number-theoretic functions)

But I'm not sure what I can conclude from this.

You can conclude that the limit is no bigger than every possible fraction that can appear in the analysis above.

(Note that you can compute the limit of interest if you can show the limit is less than or equal to every positive number)