 Subscribe!
My lastest posts can be found here: Previous blog posts:
Additionally, some earlier writings: |
Why are primes thought to be "random"? - 2011/10/28
To start with, let's suppose we want to generate all the Prime Numbers up to, say, 150. We can do this using a technique attributed to the ancient Greek mathematician Eratosthenes. We start by writing out the numbers from 2 up to 150 (or some other limit). We circle the first number that isn't crossed out (which is 2) and then cross out all the multiples of that.
So now we've circled 2 and crossed out all its multiple, which is all the even numbers. The next number that isn't crossed out is 3, so we circle that, and cross out all its multiples.
Next is 5, so we circle that, and cross out its multiples. Then 7, then 11.
Everything still not crossed out is prime.
So why am I telling you this? Well, let's do the same thing, but with a twist. We start the same way, and we write down the numbers from 2 up to 150 (or whatever our chosen limit might be). We again circle the first number that's not crossed out (and again that will be 2) but now we throw in a bit of randomness. Instead of crossing out every 2nd number, we randomly cross out every number with probability 1/2. The result will be about the same number of crossings out, but they won't be precisely the even numbers. In particular, I don't know what the next number might be - it might be 3, 4, or anything, really. But whatever the next number is, let's call it K. So we circle K, and then independently for each number after K, cross it out with probability 1/K. We'll call the circled numbers Random Eratosthenetic Pseudo-Primes (REPPs). We'll get different results each time we do this, but now we can look at the expected distribution of the REPPs. These have emerged from the random process, so in some sense they are randomly chosen, but there has been structure to the process that created them, so we would expect there to be structure in the chosen ones. We can ask about their expected density, and whether we expect there to be infinitely many. We can ask whether there will be long gaps, and whether there will be (in expectation) REPPs that are close together. In short, we can ask all the same sorts of questions about the REPPs that get asked about the primes, and since the process used to generate them is superficially similar, perhaps the behaviour and structure of these numbers will be similar to the behaviour and structure of the primes. I've heard that REPPs do have the same sort of structure as the true primes. I've heard that their density is indistinguishable from that of the true primes. I've also heard that major results for the true primes are also true (with probability 1) for the REPPs. None of this (assuming true - can anyone confirm?) is conclusive evidence for anything, but it does go some way to explaining why people think of the primes as being "somewhat random," and why some conjectures can be remarkably difficult to prove. Examples? Here are just two:
CommentsI've decided no longer to include comments directly via the Disqus (or any other) system. Instead, I'd be more than delighted to get emails from people who wish to make comments or engage in discussion. Comments will then be integrated into the page as and when they are appropriate. If the number of emails/comments gets too large to handle then I might return to a semi-automated system. We'll see.
|
Suggest a change ( <--
What does this mean?) /
Send me email
