What is the Limit of Prime Number Frequency?

[rede96]

As I understand it, the proof that there are an infinite number of prime numbers is that if you take the factorial of the largest prime you can think of, say P!, it will be divisible by every number up to P!, as P! is equal to the product of all those numbers.

As all numbers are divisible by prime numbers, if you have P! + 1, that number can not be divisible by the previous set of number so it must be either a prime number or divisible by a higher prime number than P.

I was also told that the larger the numbers get the fewer prime numbers you seem to get or the frequency of prime numbers seems to diminish.

That got me thinking, the frequency of prime numbers can’t continue to decrease otherwise the frequency or distance between two primes would have to reach infinity at some point. Then there would be an infinite amount of composite numbers after the last prime, which obviously can’t be the case if there are an infinite number of primes.

So that would suggest that there must be a limit to the distance between any two prime numbers as it can’t be infinity or one would never get to the next prime.

However it is possible to prove that one can have an infinite sequence of composite numbers. For example 100! + 2 is divisible by 100!, 1 and 2 thus it is a composite. And 100! + 3 is divisible by 100!, 1 and 3 and so on. I could replace the 100 with 1,000,000 and have 1,000,000 sequential composite numbers (or 999,999 I think it would be). Thus I could replace the 100 with an infinite amount of numbers.

Thus one can have an infinite number of sequential composite numbers, which would mean no more primes!

So what don’t I understand! ‘cos that’s doing my head in!

 

[CRGreathouse]

As I understand it, the proof that there are an infinite number of prime numbers is that if you take the factorial of the largest prime you can think of, say P!, it will be divisible by every number up to P!, as P! is equal to the product of all those numbers.

As all numbers are divisible by prime numbers, if you have P! + 1, that number can not be divisible by the previous set of number so it must be either a prime number or divisible by a higher prime number than P.

Yes, that's one proof.

I was also told that the larger the numbers get the fewer prime numbers you seem to get or the frequency of prime numbers seems to diminish.

Also true. The average gap between primes increases as the range you consider gets large.

That got me thinking, the frequency of prime numbers can’t continue to decrease otherwise the frequency or distance between two primes would have to reach infinity at some point.

Nope. The average gap increases without bound (the frequency decreases) but the gap between primes is never infinite. Bertrand's Postulate gives a weak upper bound on the gap.

So that would suggest that there must be a limit to the distance between any two prime numbers as it can’t be infinity or one would never get to the next prime.

If there was a fixed limit to the prime gap, then primes would have positive density in the natural numbers. But they don't: almost all natural numbers are composite.

However it is possible to prove that one can have an infinite sequence of composite numbers. For example 100! + 2 is divisible by 100!, 1 and 2 thus it is a composite. And 100! + 3 is divisible by 100!, 1 and 3 and so on. I could replace the 100 with 1,000,000 and have 1,000,000 sequential composite numbers (or 999,999 I think it would be). Thus I could replace the 100 with an infinite amount of numbers.

This shows that the gap between primes is unbounded, not that it's infinite.

Compare this to the powers of two (1, 2, 4, 8, 16, ...) which are even less dense. The gap between teo powers of two also grows unboundedly, but there are still infinitely many powers of two.

 

[rede96]

Yes, that's one proof.

The average gap increases without bound (the frequency decreases) but the gap between primes is never infinite. Bertrand's Postulate gives a weak upper bound on the gap.

If there was a fixed limit to the prime gap, then primes would have positive density in the natural numbers. But they don't: almost all natural numbers are composite.


This shows that the gap between primes is unbounded, not that it's infinite.

Compare this to the powers of two (1, 2, 4, 8, 16, ...) which are even less dense. The gap between teo powers of two also grows unboundedly, but there are still infinitely many powers of two.

Thanks for the reply CRGreathouse. The power of two example helped me to understand it a little.

So just to test that I’ve understood it, using the original factorial example, I can increase the number of sequential composites by increasing the value of P!, but each time I increase P! by one, there must be a prime number between the two factorials.

E.g. 100! gives me 99 sequential composites, 101! gives me 100 sequential composites. But there must be a prime between 100! and 101!

Therefore I can increase P! infinitely but there will always be at least one prime between the current and last values of P!

Being a Math novice my terminology is crap, but does that makes sense?

 

[signerror]

As I understand it, the proof that there are an infinite number of prime numbers is that if you take the factorial of the largest prime you can think of, say P!, it will be divisible by every number up to P![/color], as P! is equal to the product of all those numbers.

You probably mean "up to P". It's not true for "up to P!": e.g. it's not true that 5 | 3!.

As all numbers are divisible by prime numbers, if you have P! + 1, that number can not be divisible by the previous set of number so it must be either a prime number or divisible by a higher prime number than P.

Yes, this is Euclid's theorem.

http://mathworld.wolfram.com/EuclidsTheorems.html

That got me thinking, the frequency of prime numbers can’t continue to decrease otherwise the frequency or distance between two primes would have to reach infinity at some point. Then there would be an infinite amount of composite numbers after the last prime, which obviously can’t be the case if there are an infinite number of primes.

No, this is a misconception. Here's a simple example: consider the sequence

1,2,4,7,11,16,22...

where the difference between terms increases by one each term (2-1=1, 4-2=2, 7-4=3...)

Clearly, the differences increase without bound: for any integer N, no matter how large, there is a pair of terms whose gap is N (specifically, the Nth and (N+1)th terms). The gap sizes "go off to infinity". Of course they never "reach infinity" after any finite number of terms. And there are always more terms left. So as you see: there are infinitely many terms, yet the gaps keep growing without bound.

Likewise, there are both infinitely many primes and infinitely many composites. And although the ratio between #primes and #composites goes off to zero, there are always more primes.

 

[CRGreathouse]

So just to test that I’ve understood it, using the original factorial example, I can increase the number of sequential composites by increasing the value of P!, but each time I increase P! by one, there must be a prime number between the two factorials.

Yes. For any n >= 2, there is a prime between n! and (n+1)!.

In fact for any number n >= 2 there is a prime between n and 2n: this is Bertrand's Postulate.

 

[ThirstyDog]

I know this is slightly off topic but I remember an interesting talk in which it was stated that there an infinite number of primes, p, such that the is a prime, q, with the property
p < q < p + 16.
They proved this in an attempt to prove the twin prime conjecture.

 

[CRGreathouse]

I know this is slightly off topic but I remember an interesting talk in which it was stated that there an infinite number of primes, p, such that the is a prime, q, with the property
p < q < p + 16.
They proved this in an attempt to prove the twin prime conjecture.

Hmm. I remember that Goldston, Pintz and Yıldırım (copy/paste for the dotless i's!) showed that with the constant 21 in place of 16, under Elliott-Halberstam. That was fairly recent.