Nota Bene: This was written for my good friend Martin Darke. Since Blogger really does not like formatting mathematics the essay appears here in excerpt form. If you would like to read the entire essay, a full pdf is available on scribd. It is also embedded at the bottom of this post.
THE NEVERENDING SIEVE OF ERATOSTHENES
You likely recall from your high school maths that prime numbers can be located by a simple sieving system. That is all the background needed for reading this and so I will cover what that sieve is next anyway just in case it evades the memory in the moment.
You can write out a very long list of the counting numbers starting from 1 going up to any desired maximum you like and then begin sieving by deleting 1, circling the number 2 and then deleting every other number on the list which is divisible by two. That means deleting every second number. This can mean deleting whole columns of numbers in a single go if you arrange to have an even number of columns in the first place.
The pattern is always the same though, you circle the next smallest number not already circled which is 3 and you now delete every third number on the list which removes every odd number also divisible by three. You keep going, circling the smallest uncircled number. Next is 5, then 7, then 11 and so on and deleting all multiples of a given number from your list and the problem naturally halts at some point when you have every number on your list either circled or deleted.
This is the sieve of Eratosthenes. You locate the primes by such a simple method, all the most obvious computer algorithms locating primes are based on it. It is mathematical gardening, a method of clearing out the factorable weeds and leaving only prime roses. This is not the fastest sieve possible but it is definitely the simplest and also the most ancient.
Imagine you are given the job of Prime Housing Officer and tasked with giving every one of the prime numbers sequential addresses on Prime Lane. You number the houses in ascending order starting at 1 and you find you need an infinite number of houses on Prime Lane to house the infinite number of primes.
There is a branch of mathematics which handles infinities and in that branch of mathematics, when doing your analysis, you always set up correspondences between two ordered sets of numbers and compare their two kinds of infinities by the ability to establish such correspondences or the impossibility of setting up such correspondences. We are doing the same kind of thing here by giving every prime an address on Prime Lane. Because we are dealing with primes and because there are infinitely many primes, we are going to find some rather weird properties apply to the primes.
Galileo was an early person to care about infinities. He noted that when you delete all the even numbers from the counting numbers you are still left with an infinite number of odd numbers. He was very close to hitting on Cantor’s method. What he was noticing is that you can write two or three lists of numbers and compare the length of the lists and match the entries.
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, …
2, 4, 6, 8, 10, 12, 14, 16, 18, 20, …
1, 3, 5, 7, 9, 11, 13, 15, 17, 19, …
Galileo was deeply boggled by this, that there are as many even numbers (or odd numbers) as there were counting numbers. You can subtract an infinite number of numbers from an infinite number of numbers and be left with an infinite number of numbers. Very weird indeed, and the weirder it gets the more it is contemplated.
There are also different kinds of infinities and these are analysed in this exact same way of comparing infinities to other infinities and not being able to produce correspondences between those lists. This program of research into infinities has been ongoing since Georg Cantor invented the first ever method to attack the problem in the early 20th century. By doing so he was able to prove that there really are, somehow, more Real numbers than there are ordinary counting numbers. Both are infinite but they are somehow also not infinities of the same kind, one of these infinities is definitely bigger than the other.
In more technical language, two different kinds of infinities which cannot be set up in a perfect correspondence have a different cardinality. The reason for mentioning this is that the primes are what is called countably infinite. That just means they have the same cardinality, same kind of infinity as the ordinary counting numbers. When you set up a correspondence between them you are forced to connect the primes with a counting number and the easiest way to do this is to number the primes, and that means giving the primes an address on Prime Lane and in ascending order of value.
TROUBLE AT PRIME LANE
So the number 2 lives at 1 Prime Lane being the first of the primes. The number 3 is the second prime and must live at 2 Prime lane. The number 5 lives at 3 Prime Lane and so on. Every prime has an address and every address contains one and only one prime. This is an exact correspondence. It is what mathematicians refer to as bijective. That only means if you give me a specific address on Prime Lane then there must exist a scheme by which I can locate the only possible prime that lives there. But also it means that if you give me a specific prime number then there must exist some scheme by which I can give you their unique address. This characteristic of uniqueness is called ‘one to one’, meaning there is a one to one correspondence between input and output. If you give me an address and the scheme instead gives you back two prime numbers then it is not ‘one on one’. Also, the process of being able to locate a unique prime given a unique address or vice versa to a scheme is called ‘onto’. So ‘onto’ means there’s a process which will always work. So onto implies an algorithm exists which is never wrong if applied correctly. So you will hear a mathematician say a function is ‘one on one and onto’, a phrase so awkward and unhelpfully opaque in meaning they mostly just say bijective.
Now a Prime Crime Inspector comes to Prime Lane one day and his only job as he has been instructed to do it, is to locate any address which is a prime number and he has been told to arrest and detain the occupant. Being a Prime Crime expert and in his prime, so to speak, he skips 1 Prime Lane since 1 is not prime and starts by arresting the occupant of 2 Prime Lane. Then he arrests the occupant of 3 Prime Lane. Then the occupant of 5 Prime Lane and then 7, 11, 13, 17 and so on until he’s arrested the infinitely many primes who have the misfortune of living in a house on Prime Lane which also has a prime numbered address. Call these the ‘prime numbered primes’ or say they are ‘at least doubly prime’. The phrase ‘at least’ will prove to be significant.
The Prime Crime Inspector now has an infinite jail to go to so as to drop off all the infinite number of prime numbers he has arrested. Note that he has also left an infinite number of primes behind, all of whom are utterly delighted to have turned out to live at a factorable address. Call these stay-behinds, ‘singularly primed primes’.
For the arrested primes, however, each one of them was already on Prime Lane and so by definition they were already a prime number, but they also lived at prime numbered addresses as well. So they are really being convicted of being ‘at least doubly prime’. For this reason, the Warden petitions the council to rename the prison Doubly Prime Jail and his petition is accepted and the motion carried.
Upon their arrival at Doubly Prime Jail each number is given their own unique cell and to keep things very simple for everyone they are incarcerated in ascending order of numerical value. The first number arrested was the occupant of 2 Prime Lane. That was the number 3 because 3 is the second prime. As the smallest prime arrested they now go into cell 1. In cell 2 goes the second smallest prime arrested, that is the occupant of 3 Prime Lane and that was the number 5 because 5 is the third prime. So, you can see that the occupants of Prime Lane have been sieved a second time now and the only numbers we are interested in tracking are now in neatly, consecutively numbered jail cells. Being found guilty of being the prime numbered addresses means being locked up in correspondence with the counting numbers a second time in terms of jail cells.
They must once again have the same cardinality since there really are infinite primes and we are deleting them to a genuinely simple scheme. So there have to be a countably infinite number of cells to house the countably infinite detainees.
Now a Prime Lawyer comes along and says there's been a breach of the law because the arrest warrant called for arrest of all only doubly primed primes while the arresting officer was asked to arrest all primes at prime numbered addresses and that means he has arrested an infinite number of primes which are also at least triply prime and are therefore not only doubly prime. And so, in order to sort out this miscarriage of mathematical justice, all of the prime numbers now living in prime numbered jail cells have their cell doors opened and are told to assemble in ascending numerical order for inspection and release. And so the sieve is applied again, a third time, this time note that it has been applied to the cell numbers of the various inmates. All the prime numbered cells contain prisoners who were at least triply prime, and thus are cleared of being only doubly prime.
All the singularly prime numbers still live in Prime Lane. All the doubly primed numbers are still locked in cells and all triply prime numbers or higher are due for release.
So, an infinite subset of the infinite inmates are released and, as recompense for false arrest, they are taken to a holding facility for higher order primes and will be given larger homes, all in the same infinitely long street and this bold new housing development, on prime real estate of course, is called Triply Prime Crescent.
Once again the obvious rule applies that we list these former inmates from smallest prime to ever larger primes and the smallest triply prime number lives at 1 Triply Prime Crescent. The next smallest prime to be released from Doubly Prime Jail lives at 2 Triply Prime Crescent and so on. Once again you set up a correspondence between the primes that are left after several sieves and street addresses and lo, you have another infinitely long crescent packed with the infinitely many primes that remain.
It is not remotely hard to prove that this repeated, looped sieving process must go on indefinitely. Sieving primes using the prime sieve recursively does not ever end because you can always set up another correspondence between 1) the primes that remain after the sieve has acted however many times you please and 2) the counting numbers in the form of a street addresses or numbered jail cells or what have you. There are always an infinite number of primes left after any sieve is the point, so you can apply the sieve infinitely many times.
It is quite a remarkable thing to think about subtracting infinities from infinities any finite number of times only to have an infinite number of objects left. That is what we are looking at.
I think of each application of a sieve as creating a new generation of primes. Here we have put each generation into a new street or a jail. So, Prime Lane contains only first generation primes, it also contains every first generation prime. The jail contains all second generation primes and only second generation primes. As we left things Triply Prime Crescent contains all third and higher generations of primes so that it will also contain fourth and fifth and ten billionth generation primes. If we sieved Triply Prime Lane by address it would remove all those unwelcome higher order primes and leave only third generation primes. Using my own preferred terminology, we have found that we will need an infinite number of generations to find a generation for every single prime. That is also to say, no matter how many times we repeatedly apply the sieve, we find we have to keep applying it because we don’t ever run out of primes to sieve.
After a trillion trillion trillion trillion applications of the sieve, we’re not even close to removing all of the primes. There will be as many primes left as there were after the first sieve because each generation has the same cardinality. It’s a very strange thought but this is what it means to have an infinite number of primes, it means an infinite number of generations would be needed to locate every possible prime at a specific address in this lane or that crescent, this road or that jail cell.
Note that a generation and the primes in a generation are not ‘one on one’. You give me a prime and I can locate its generation by simply sieving repeatedly until it gets deleted. You give me the generation of a prime though and you have only named the street that prime lives on so I have no idea which of infinitely many primes you might mean because giving me a street name is not a sufficiently complete addressing system. It is like saying I am thinking of a prime that lives in Doubly Prime Jail, which prime am I thinking of? It is not the same problem as saying, I am thinking of the number 17, where does 17 live these days? I can give you 17’s exact address by tracking its travel itinerary. Imagine sending 17 mail and every place it has lived it has a mail redirection service. 17 is the 7th prime so it lived at a prime numbered address on Prime Lane and we send mail there. It must be redirected because 17 really is the 7th prime and lived at 7 Prime Lane and was then arrested for that exact reason. So mail redirection applies and it goes to the Doubly Prime Jail. Here 17 was housed in cell 4, being the 4th smallest prime arrested. That is also where it stayed even when all the prime numbered cell doors were opened. 4 is certainly not a prime number. So, 17 is still prisoner number 4 at the Doubly Prime Jail and his mail finds him there.
Now for something curious which has the Wonderland kind of curiousness in the sense that it just gets curiouser and curiouser.
PRIME FAMILIES
One thing that is very revealing is to look at how primes are removed as the sieve is applied over and over. What emerges is a pattern of deletion of the primes and from this you can also consider what I have started to call families of primes. It is this idea that will enable us to get a ‘one on one and onto’ scheme such that you give me the generation of a prime and the family it belongs to and now I really can tell you what that prime is...
* * *
Primetime - Strange Pattern... by Bart Alder
