Wednesday, August 09, 2006

Prime gap equation

My last few posts have been about what results from primes not having a preference with regard to their residue modulo another prime, which may sound complicated but it's not, as for instance, 3 has 3 residues: 0, 1, 2. And the residue of 5 modulo 3 is 2, as 5-3 = 2, whereas 7 mod 3 = 1, since 7-6=1, and I'm simply noting that if you check primes modulo 3, you will find no preference for a particular residue beyond not being 0.

An approach which can be proven rigorously to be absolutely true as I've shown in an earlier post where I related the probability that x is prime directly to the exact prime count.

But that result is not a surprise as the naturals have a rather simple ordering, which is they advance by 1, so you have 5,6,7, where you see all the possible residues, and repeat, so 8, 9, 10, shows the same ordering and, of course, that goes out to infinity. So primes modulo 3 can't prefer, say, 1 as the residue, as then the composites would have to tend towards 1 as well, when in fact, naturals split by thirds.

That simple idea leads to methods for figuring out how many primes should be in a particular interval using probability methods, as, for instance with 3, 1/2 of the primes will have 1 as a residue modulo 3, so you can say that there is a 50% chance any given prime has 1 as a residue modulo 3. Moving up to the other primes you can get a probability based on its number of non-zero residues, so like with 5, there is a 25% chance that a prime will have a residue modulo 5 of 1, and so forth.

In my previous posts I worked through some equations that you can quickly derive using this simple idea, and now I'd like to talk about yet one more, which is the equation for the odds of a particular prime gap g. A prime gap is just a situation where you have a run of composites between primes, like between 13 and 17, you have 3 composites, 14, 15, 16, but it's called a prime gap of 4, because 17-13=4.

Based on my simple idea the equation for prime gaps is as follows.

The prime gap equation given a natural number x and even gap g greater than 2 is

probPrimeGap = ((pj - 2)/(pj - 1)*...*(1/2))*(1 - ((pj - 2)/(pj-1)*...*(1/2))n*Corr

where n equals (g/2)- floor(g/4) - 1, j is the number of primes up to sqrt(x), pj is the jth prime, and Corr corrects for any odd primes that are factors of g, if there are any, and if there are none Corr=1, otherwise it adjusts to (p-1)/p for that prime versus (p-2)/(p-1).

When g=4 is a special case because if x is prime and x-4 is prime then x-2 cannot be, unless x=7. So for the g=4 case you have the same probability as for twin primes:

probTwinPrime = ((pj - 2)/(pj - 1)*...*(1/2))

So let's try it out with g=6.

For a 6 gap, n = 6/2 - floor(6/4) - 1 = 1, and instead of figuring out the value for Corr it's easier to just note that instead of using 1/2 you use 2/3. So you have:

probPrimeGap = ((5 - 2)/(5 - 1))*2/3*(1 - ((5 - 2)/(5 - 1))*2/3) = (3/4)(2/3)(1 - (3/4)(2/3)) = 0.5*0.5 = 0.25

And 6*0.25 = 1.5, so 1 case is expected and one occurs at 31, 37.

Now reiterating the idea.

First as shown in my post on twin primes if you have x a prime, then you have the probability that x-2 does NOT have a prime p that is less than or equal to sqrt(x) as a factor, is (p-2)/(p-1), but if x may not be prime, you need the probability that it is prime.

You just multiply all the odds of something not happening together to get the odds that none of them happen. So for the first piece of my prime gap equation I just multiplied the probability (p-2)/(p-1) for each prime less than or equal to sqrt(x), where for any primes that are factors of g you just have (p-1)/p as there is 0 probability that p can add to another prime and give a number divisible by itself.

For the second piece I simply consider the probability if x is prime that x-2 is NOT prime or x-4 is not prime, and then that x-6 is NOT prime, and so forth up until before the gap, like with g=10, that goes up to x-8, so n=4, as it turns out each probability is roughly the same, and that's how I get the equation, as I just subtract the probability that x-g is prime from 1.

So can it be wrong?

Well, what is the idea based upon?

It's based upon the primes not having a preference modulo the residue of another prime, so like, if they did, with 3, then it'd have to be the case that numbers leaned towards a particular residue modulo 3, but they don't as they go lockstep in a simple pattern 1, 2, 3, and then 4, 5, 6, and then 7, 8, 9 and so forth, where in each case the residues modulo 3 are the same in a perfect pattern that goes out to infinity. Each prime produces a similar pattern.

So that part of the idea cannot be wrong.

But it is probability.

The expectation value is just the most likely result, but the actual results follow the gaussian distribution also called the normal distribution, so for instance, there is a 50% probability of flipping a coin heads, so given 10 flips the expected number of heads is 5.

But you can sit and flip a coin 10 times and get 10 heads or none.

Oh, one other thing is the question of how big of a gap is possible at various levels, like, of course, you can't have a gap of 10 starting at 11, so what determines it? My guess is that the maximum gap size is p+1 where p is the largest prime less than the sqrt(x), where x is the start of the interval.

But that only matters at smaller values. As you look at bigger gaps the prime gap equation dominates, so that the gap is likely to occur much further down than when it is first allowed.

James Harris


James said...

Corrected today changing 1/3 to 1/2, as I think that was just a typo. Wow, complicated formula. No wonder I don't like to think about it too much. Kind of just threw it up on the blog and wandered off, which I'm going to do again now...

James said...

Had to make more corrections. Removed PrimeProb(x), and corrected (p-2)/p to (p-2)/(p-1).

James said...

Added a demonstration example.