Sunday, February 07, 2010


JSH: Random distributions and prime numbers

It's important to highlight the debate about randomness and prime numbers as for years now the side which claims that random cannot be found with primes has been winning, when all the evidence actually says that they can.

And it's not a minor issue. If primes can give random distributions then random may possibly defined through prime numbers. Random in our reality may BE about prime numbers.

It's an opportunity to answer one of the biggest questions in our reality: what exactly is random?

So I presented a rather simple mathematical axiom:

Prime residue axiom: Given differing primes p_1 and p_2, there is no preference for any particular residue of p_2 for p_1 mod p_2 over any other. (And I'll note that I don't consider 0 to be a residue. )

The axiom indicates then that by residue, there should be random behavior. Here is an example mod 3.

Here is what you get with the first 23 primes greater than 3:

5 mod 3 = 2, 7 mod 3 = 1, 11 mod 3 = 2, 13 mod 3 = 1, 17 mod 3 = 2, 19 mod 3 = 1, 23 mod 3 = 2, 29 mod 3 = 2, 31 mod 3 = 1, 37 mod 3 = 1, 41 mod 3 = 2, 43 mod 3 = 1, 47 mod 3 = 2, 53 mod 3 = 2, 59 mod 3 = 2, 61 mod 3 = 1, 67 mod 3 = 1, 71 mod 3 = 2, 73 mod 3 = 1, 79 mod 3 = 1, 83 mod 3 = 2, 89 mod 3 = 2, 97 mod 3 = 1

There are some mathematical details which have to be handled though before you rush to higher primes, as the maximum gap between primes is roughly p+1, where p^2 is the smallest integer. So to look mod 101, for instance, you'd need to start at 101^2, before you use primes, so you'd take the residue modulo primes greater than p^2.

So I need to clip the first two and start at 11 mod 3.

So the sequence is

2, 1, 2, 1, 2, 2, 1, 1, 2, 1, 2, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1

and by the prime residue axiom, it is random.

Primes could be used to label random sequences. As imagine the sequence above were to be labeled, then it could be, residues mod 3, from 11 through 23. For different random sequences, you could just look for them in prime residues, and use the primes themselves to label in the same way.

The max gap isn't a complicated thing to handle. So if you wish to test this idea out, you can program it easily enough, and just look at the distribution with the standard methods to determine randomness.

But notice, if you did not know about the max gap issue, and did so, you could convince yourself that the sequence is not random as you'd have a tendency towards smaller residues until you broke through the barrier.

For those still skeptical consider now twin primes. The prime residue axiom would indicate that for twin primes—two primes in a row separated only by 2, for instance 11, 13, or 17, 19—the probability calculation for their occurrence is actually very easy.

For example, between 5^2 and 7^2, there are 6 primes. The probability then is given by:

prob = ((5-2)/(5-1))*((3-2)/(3-1) = (3/4)*(1/2) = 0.375

(That calculation is fairly straightforward probability.)

And 6*0.375 = 2.25 so you expect 2 twin primes in that interval.

The primes are 29, 31, 37, 41, 43, 47 and you'll notice, two twin primes as predicted: 29,31 and 41, 43.

However, there is an issue which shifts the probability slightly.

If you go into the actual residues it jumps out at you:

29, 31, 37, 41, 43, 47

mod 3: 2, 1, 1, 2, 1, 2
mod 5: 4, 1, 2, 1, 3, 2

Here all the residues for 5 were in evidence so the count came out right, but for random it should have been possible for ALL the residues mod 5 to be 4, but it's not because with 6 primes there isn't enough space in the interval—4*5 = 20, but 49-25=24, where only 12 are odd and only 6 are primes. So the probability is actually off! A scenario where all residues are 4 is precluded by the size of the interval for the larger prime.

Which is an issue like the max gap problem.

That will tend to over-count because the higher residues are less likely to occur because they cannot fit. Easy explanation that jumps out at you with even a small example. Easy.

For the smaller primes it's not an issue as if the prime is greater than interval/(prime count in interval) then that prime isn't affected and its residues can have purely random behavior. For instance, for 3 between 25 and 49, you have 24/(6) = 4, and as that is greater than 3, there is no clipping for 3.

And that's it.

You have all the information needed to see randomness with prime numbers.

For the residue of one prime relative to another, you have to go beyond the max gap. I've hypothesized that's just a matter of going to primes greater than p^2, to get a random sequence of numbers using that prime's residues. For instance, again for p = 101, you'd use primes greater than 101^2.

I've also shown how you can see the count of twin primes following the predictions from random, with a slight over in the expectation value given by difficulty in fitting in higher residues of the larger primes.

Physicists who are curious who are good with their probability and statistics can test out distributions to see if they now look random, and should consider why they believed before that primes did not give us random.

Primes may have been the key all along. The answer to random. By using them fully we may be able to greatly enhance our understanding of random in our own world.

Who knows? Random in our everyday lives may just be about prime behavior.

<< Home

This page is powered by Blogger. Isn't yours?