Chapter 7
Prime Mysteries
Mathematicians have tried in vain to this day to discover some order in the sequence of prime numbers, and we have reason to believe that it is a mystery into which the human mind will never penetrate.
– Leonhard Euler
The greatest problem for mathematicians now is probably the Riemann Hypothesis.
– Andrew Wiles
A prime number is just a natural number that can be divided, without a remainder, by only itself and 1. This might not seem like a particularly special quality, but prime numbers occupy a position of central importance in maths. It isn’t an exaggeration to say that some of the greatest unsolved mysteries in the subject involve primes and that, on a practical level, these numbers play an important part in our daily lives. Whenever you use a bank card, for instance, the bank’s computer checks you’re the owner by using an algorithm that cracks a very big number into a unique product of two known primes. Much of our financial security depends ultimately on these numerical oddballs.
The first few primes are 2, 3, 5, 7, 11, 13, 17, 19, 23, and 29. All numbers that aren’t prime are said to be composite. The number 1 itself isn’t considered to be a prime – although it could be – because if it were it would complicate some useful theorems, including one that’s so important it’s called the Fundamental Theorem of Arithmetic. This states that every number can be written in exactly one way (ignoring rearrangements) as a product of one or more primes. For instance, 10 = 2 × 5 and 12 = 2 × 2 × 3. If 1 were allowed to be prime then there’d be an infinite number of ways of writing such a product because it could include any number of 1’s multiplied together.
A cicada.
In nature, prime numbers crop up in a very unexpected and surprising way. One species of cicada, Magicicada septendecim, has a 17-year life cycle. All the individuals of this species remain in their larval phase for exactly 17 years before the whole mass of them emerge at once as adults to mate. Another species, Magicicada tredecim, is similar but has a 13-year life cycle. There are various theories about why these cicadas evolved specific prime-number life cycles. The most popular is that there existed a predator, which would also emerge in a regular number of years. If both cicadas and predators reached maturity in the same year, that brood of cicadas would very likely have been wiped out. Survival for the cicadas hinged upon evolving a life cycle that overlapped as little as possible with the predators’. If, for instance, a species had a 15-year life cycle, the predator could surface every 3 or 5 years and kill the cicadas every time they emerged, or surface every 6 or 10 years and kill the cicadas every second time the cicadas emerged, so that the species would rapidly become extinct. However, if a cicada has a 17-year life cycle then if the predator had a life cycle of less than 17 years (which is likely, as evidence suggests the hypothetical predator had a shorter life cycle than the cicadas) then the predator would emerge unsuccessfully 16 consecutive times and likely die, from starvation. These predators would have long since disappeared, leaving behind the cicadas we now see with their prime-numbered life cycles.
It’s known that there must be an infinite number of primes, or – what amounts to the same thing – that there’s no largest prime. Euclid proved this more than 2,000 years ago. A different but simple proof runs as follows: suppose that the number of primes is not infinite. Then we would be able to multiply them all together: 2 × 3 × 5 × 7 and so on, all the way up to the biggest one on the list. Let’s call the gigantic product that we’d get P and now add 1 to it. There are only two possibilities: either P + 1 is prime or it’s divisible by a smaller prime. But if we divide P + 1 by any prime on our list of what are supposedly all the primes there’d always be a 1 left over, forcing us to conclude that P + 1 must also be prime itself or have a prime factor not on the list. Starting from the assumption that there’s a largest prime number, we’re led to a contradiction. In logic and maths this is what’s called reductio ad absurdum, in other words, disproving an argument by showing it has absurd consequences. The starting assumption must be wrong and therefore its opposite must be true: there are infinitely many primes, a result known as Euclid’s theorem.
Mathematicians in ancient times had no easy way to calculate large primes. They would certainly have known in classical Greece that 127 was prime because it’s implied by a result in Euclid’s Elements, and perhaps they knew of others up to values of a few hundred or a few thousand. Significantly larger primes were found in the Renaissance era, including the number 524,287 found by Pietro Cataldi, a prominent prime hunter from Bologna. The search for new primes began to centre on numbers of the form 2n – 1, where n is an integer, which are now known as Mersenne numbers, after the seventeenth-century French monk Marin Mersenne, who devoted a lot of time to studying them. Mersenne numbers are useful ‘prime suspects’ because, selected at random, they’re much more likely to be prime than are randomly selected odd numbers of similar size (though not all Mersenne numbers are prime). The first few Mersenne primes (Mersenne numbers that are prime) are 3, 7, 31, and 127. Cataldi’s big prime is the 19th Mersenne number (M19) and the 7th Mersenne prime. It took almost a century and a half for a larger prime to be found, by the Swiss mathematician Leonhard Euler in 1732. Almost a century and a half after that, in 1876, the record-holder became Édouard Lucas, who showed that the 127th Mersenne number (M127), with a value of roughly 1.7 trillion trillion trillion, is also prime.
While many Mersenne numbers are indeed prime, Mersenne himself made a few errors in determining primality, such as believing that M67 was prime. The factors were first found in 1903 by Frank Nelson Cole. On October 31, he was invited to give an hour-long talk at the American Mathematical Society. He walked up to the blackboard, without saying a single word, calculated 267 – 1 by hand, and then calculated 139,707,721 × 761,838,257,287, showing they are the same, before returning to his seat to a standing ovation. He claimed that it had taken him ‘three years of Sundays’ to find the factors of 267 – 1.
Since 1951, the search for new prime numbers has exclusively involved computers and progressively faster algorithms for seeking out larger and larger Mersenne primes. At the time of writing, the largest known is M74207281, which has 22,338,618 digits. It was found on September 17, 2015, by Curtis Cooper at the University of Central Missouri as part of the Great Internet Mersenne Prime Search (GIMPS), a collaborative, distributed computing project of volunteers that has calculated the 15 largest Mersenne primes in the twenty-odd years it’s been running. As has become customary its discoverers marked the event by uncorking a celebratory bottle of champagne.
We know, then, what a prime number is and that the primes go on forever. We know that they can be useful to us in the modern world, and that they also crop up in nature. But there are many things we don’t know about primes, including whether certain well-known hypotheses are true or not. One of the more famous of these is the Goldbach conjecture, named after the German mathematician Christian Goldbach. This states that every even number greater than 2 can be written as the sum of two primes. For small even numbers: 4 = 2 + 2, 6 = 3 + 3, 8 = 3 + 5, 10 = 3 + 7, and so on, this is easy to verify. Much larger numbers have been checked using computers and the rule has never been found to fail. However, no one knows if it’s true in all cases.
Another unsolved conjecture has to do with pairs of prime numbers that differ by just 2, such as 3 and 5, and 11 and 13. These are called twin primes and the so-called twin prime conjecture is that there are infinitely many of them. To date, though, no one has been able to show that this is true beyond doubt.
Perhaps the greatest mystery of all to do with primes concerns their distribution. Among small natural numbers, primes are very common but they become sparser and sparser as the size of the numbers grows. Mathematicians are interested in the rate at which the thinning out happens, and how much we can know about the frequency of prime numbers. Their occurrence doesn’t follow any strict regular pattern but that isn’t to say they just spring up willy-nilly. In The Book of Prime Number Records, Paulo Ribenboim put it this way:
It [is] possible to predict with rather good accuracy the number of primes smaller than N (especially when N is large); on the other hand, the distribution of primes in short intervals shows a kind of built-in randomness. This combination of “randomness” and “predictability” yields at the same time an orderly arrangement and an element of surprise in the distribution of primes.
Countless mathematicians have commented on the enigmatic nature of prime numbers. They’re the simplest of things to describe – so simple that children in elementary school are taught what they are and are often asked to name the first few of them or say whether a number is prime or not. Agnijo himself became fascinated with primes at a very early age and with some of the unsolved problems that surround them. In time, this led to his fascination with other great mysteries of number theory.
Primes are also much like the atoms of the numerical universe, from which all other natural numbers are built. You’d think there’d be every reason to hope and suppose that they obeyed strict laws and that it should be easy to predict where the next one occurred along the number line. Yet, these most elemental of mathematical building blocks are shockingly unruly and capricious in their behaviour. It’s this tension between expectation and reality, and the strong suspicion that some organising principles of great importance lie just beyond our grasp, which has fascinated mathematicians since antiquity.
Looked at individually, or in small groups, the primes do indeed appear lawless. But viewed en masse, like shoals of fish or murmurations of starlings, a previously hidden level of organisation emerges. One of the most curious discoveries about them happened by accident. While sitting listening to a dull lecture in 1963, the Polish mathematician Stanislaw Ulam started doodling on a sheet of paper. He wrote down a square spiral of numbers, starting with 1 in the centre, and gradually working his way outward along a rectangular grid. He then circled all the primes and noticed something surprising. Along certain diagonals of the spiral, as well as some horizontal and vertical alignments, prime numbers were unusually dense. Larger Ulam spirals, produced using computers and containing tens of thousands of numbers, continue to show these patterns. In fact, it seems that they stretch out as far as we care to calculate.
The Ulam spiral.
Some of the prominent lines in the spiral correspond with certain formulae in algebra that are known to generate a lot of prime numbers. The best known of these was discovered by Leonhard Euler and is named after him. Euler’s ‘prime-generating polynomial’, n2 + n + 41, spits out primes for every single value of n from 0 up to 39. For instance, for n = 0, 1, 2, 3, 4, and 5, it outputs 41, 43, 47, 53, 61, and 71, respectively. For n = 40 it gives the (non-prime) square number 412, but continues to yield a very high frequency of primes as n gets larger. There are other, similar formulae that, for some reason that isn’t clear, have this peculiar ability to spawn primes at a great rate. Mathematicians continue to discuss the significance of the patterns in the Ulam spiral and their connection with unsolved problems such as Goldbach’s conjecture, the twin primes conjecture, and the hypothesis, known as Legendre’s conjecture, that there’s always at least one prime between consecutive perfect squares. What the spiral makes graphically clear, however, is that there are patterns and that despite appearing haphazard in their distribution, primes follow some overarching rules that govern their behaviour in large groups.
The best theorem we have about how the prime numbers are distributed is called, unsurprisingly, the prime number theorem and is widely regarded as one of the greatest achievements in number theory. In a nutshell, it says that for any number N that is large enough, the number of primes less than N is roughly equal to N divided by the natural logarithm of N. (The natural log of a number is just the power to which the number e, which is equal to 2.718 … , has to be raised to equal the number.) This formula doesn’t tell us where the next prime will lie but it does give a pretty accurate indication of how many primes there are within a given number interval, providing the interval is large enough.
Unlike Euclid’s theorem of the infinity of primes, which, as we’ve seen, can be explained in a few lines of plain English, the prime number theorem took a century of effort to prove. It was first mooted by the German Carl Gauss, as a teenager, in 1792 or 1793, and independently by the Frenchman Adrien-Marie Legendre a few years later. Of course, mathematicians had long recognised that the gaps between primes tend to get wider as the size of numbers increases, but it was the publication of extended tables of primes and of longer, more accurate tables of logarithms, in the second half of the eighteenth century, which helped spur efforts to find specific formulae to describe this thinning out. Gauss and Legendre spotted that a one-over-log type of function was at work. Further important progress towards refining the distribution formula was made by the Russian mathematician Pafnuty Chebyshev between 1848 and 1850. But the biggest breakthrough of all came through the efforts of the German Bernhard Riemann who, in 1859, published an eight-page memoir, his only writing on the subject, titled ‘On the Number of Primes Less Than a Given Magnitude’. In it he put forward a suggestion, subsequently called the Riemann Hypothesis, which has teased and tormented mathematicians ever since in their attempts to prove it. David Hilbert reputedly said that the first thing he would ask after waking from a sleep lasting a thousand years would be: ‘Is the Riemann Hypothesis established yet?’ In his book on the theory behind Riemann’s suggestion, the American mathematician H. M. Edwards wrote:
It is now unquestionably the most celebrated problem in mathematics and it continues to attract the attention of the best mathematicians, not only because it has gone unsolved for so long but also because it appears tantalizingly vulnerable and because its solution would probably bring to light new techniques of far-reaching importance.
To underscore how highly the Riemann Hypothesis is regarded it’s one of the seven Millennium Prize Problems identified by the Clay Mathematics Institute of Cambridge, Massachusetts, and for which a $1 million prize is on offer for the first verified solution. It’s one of the two that Agnijo would particularly like to solve, the other being the P vs NP conjecture (discussed in Chapter 5). The Riemann Hypothesis is also the only one of the Millennium Prize Problems that appears in a list of 23 major unsolved problems discussed by David Hilbert in an address he gave, on August 8, 1900, to the International Congress of Mathematicians in Paris.
To the question of how the primes are distributed, Riemann brought to bear the methods of a newly developed branch of maths known as complex analysis. As the name suggests, this has to do with all the different ways of working with complex numbers – numbers that contain a real part and an ‘imaginary’ part, such as 5 – 3i, where i is the square root of -1. At the core of complex analysis is the study of complex functions, which are just rules for turning one set of complex numbers into another. Back in 1732, the prodigious and astonishingly creative Swiss mathematician Leonhard Euler, whose collected works run to more than 31,000 pages, defined a previously unknown beast of the mathematical world called the zeta function. It’s a type of infinite series – an infinitely long sum of terms that may or may not converge to a finite value depending on what numbers are fed into it. Under certain circumstances, the zeta function reduces to a series similar to the harmonic series 1 + ½ + ⅓ + ¼ + … which has been studied since ancient Greek times when Pythagoras and his followers were obsessed with understanding the universe in terms of numbers and musical harmony. Riemann took Euler’s zeta function and extended it to include complex numbers, which is why the complex zeta function is also known as the Riemann zeta function.
In his famous memoir of 1859, Riemann put forward what he believed was a better formula for estimating how many primes there are up to a given number. However, this formula depends on knowing for which values the Riemann zeta function is zero. The Riemann zeta function is defined for all complex numbers of the form x + iy except those for which x = 1. The function goes to zero for all negative even integers (-2, -4, -6, etc.) but these aren’t of interest in tackling the problem of how prime numbers are distributed and so are referred to as ‘trivial’ zeros. Riemann realised that the function also has an infinite number of zeros in a critical strip between x = 0 and x = 1 and, further, that these ‘nontrivial’ zeros are symmetric with respect to the line x = ½. His famous hypothesis is that all of the nontrivial zeros of the complex zeta function lie, in fact, exactly on this line.
If true, the Riemann Hypothesis implies that prime numbers are distributed as regularly as they can possibly be within the ultimate limits imposed by the prime number theorem. In other words, granted that there’s a certain amount of ‘noise’ or ‘chaos’ that introduces uncertainty into where prime numbers spring up, the Riemann Hypothesis says that noise is extremely well controlled – that the apparent indiscipline of primes is, behind the scenes, highly choreographed. Another way to think of this is in terms of rolling a multisided die that has a probability of 1/log n of coming up prime. Suppose for each integer n that is greater than or equal to 2, you roll the die n times. In an ideal world, the expected number of primes would be n/log n. But the world not being ideal there’s always some variation – a margin of error – around the expected value. The size of this error is given by what’s commonly called the law of averages (or large numbers). What the Riemann Hypothesis claims is that the deviation of the distribution of primes from n/log n is no greater than what the law of averages predicts.
There’s plenty of strong evidence to suggest that the Riemann Hypothesis is true. Riemann checked the first few nontrivial zeros himself to make sure they obeyed his rule and, with one of the earliest computers, Alan Turing ran the calculation out to the first thousand. In 1986 came verification that the first billion and a half nontrivial zeros of the Riemann zeta function sit right on the critical line where the real part of the function equals ½. Much earlier, in 1915, G. H. Hardy proved that there’s an infinite number of nontrivial zeros (though not necessarily all of them) on this line. In 1989, the American mathematician Brian Conrey showed that the number of zeros on the line had to be more than two fifths of the entire population of zeros in the critical strip. Six years later, after several years of running ZetaGrid, a distributed computing project, the first 100 billion zeros of the Riemann function were found to fall precisely on the critical line, with no exceptions.
It would be perverse to suspect that the Riemann Hypothesis was wrong given every indication that it’s right. However, in mathematics belief and persuasive evidence are a world away from proof. Without proof any results, however useful, that take for granted the mere suggestion of a theoretician, even one as eminent as Bernhard Riemann, are like a house resting on sand. While there remains the possibility that a single nontrivial zero lies elsewhere in the critical strip other than on the line x = ½ this wonderful notion of Riemann’s really has no more weight than wishful thinking.
The importance of proving (or disproving) it, however, goes well beyond the bounds of number theory or of mathematics as a whole. The Riemann Hypothesis, it turns out, has a subtle but direct connection with the subatomic universe. One day in April 1972, at the Institute for Advanced Studies, in Princeton, New Jersey, mathematicians Hugh Montgomery and Atle Selberg were chatting about Montgomery’s recent discovery to do with the spacing of nontrivial zeros on the critical line. Later, in the cafeteria, Montgomery was introduced to Freeman Dyson, who was Professor in the School of Natural Sciences. As soon as Montgomery mentioned the subject of his work on the zeros, Dyson realised that the maths was identical to that of a theory he’d investigated in the 1960s. So-called random matrix theory can be used to carry out calculations on the energy levels of particles inside heavy atomic nuclei. Dyson recalled his surprise at seeing the same equations pop up in a field to do with the distribution of prime numbers:
His result was the same as mine. They were coming from completely different directions and you get the same answer. It shows that there is a lot there that we don’t understand, and when we do understand it, it will probably be obvious. But at the moment, it is just a miracle.
Often aspects of maths, such as the Riemann Hypothesis, seem completely abstract and of no interest except as some elaborate intellectual exercise. Yet here’s an example – and they’re not as uncommon as it may appear – of a direct connection between seemingly pure mathematics and the physical universe on a fundamental level.
More than 150 years have passed since Riemann announced his hypothesis to the world and the absence of a proof has become like a gaping hole at the heart of mathematics. Perhaps the ideas needed to solve it are so advanced or radical that they’re beyond the scope of our present understanding. If so, the very pursuit of a proof may help develop powerful new mathematical techniques. If a proof finally does come, its importance to maths will be hard to overstate because of the foundational role that prime numbers play in the number system and the relationship they have to hugely diverse areas of the subject. Hundreds of theorems will stand or fall depending on whether the Riemann Hypothesis is found to be true or false. If true, more questions will be asked, including why primes lie at such a delicate point of balance between randomness and order. If false, then all these theorems would collapse and a devastating earthquake would shake mathematics to its core.
No one is expecting the Riemann Hypothesis to be proved or disproved any time soon. Yet, sometimes, proofs appear in mathematics suddenly and without warning. This was the case with the magnificent vindication of Fermat’s Last Theorem by Andrew Wiles. It also happened more recently in connection with a discovery related to the twin primes conjecture – the idea, widely believed to be true, that there are infinitely many twin prime pairs. In 1849, the French mathematician Alphonse de Polignac went further and proposed that there were infinitely many prime pairs for any possible finite gap, not just 2. Little progress had been made in proving these suggestions until, out of the blue, in 2013, a middle-aged lecturer at the University of New Hampshire named Yitang Zhang, unknown in the wider mathematical community, published a paper with a startling result. Zhang had managed to show that there’s a number N, smaller than 70 million, such that there are infinitely many pairs of primes that differ by N. What this means is that no matter how far we wander into the remote lands of vast and ever vaster prime numbers, and no matter how sparse the primes in general become, we’ll always continue to find prime pairs that differ by less than 70 million. There’s every reason to believe that this number can be greatly reduced, and to hope, in a wider sense, that some remarkable breakthroughs in prime number research are on the horizon.
While prime numbers are quite simple to understand, they form mysterious patterns that we still haven’t properly explained. Is every even number the sum of two primes? Are there infinitely many pairs of primes differing by 2? No one knows for sure, although many think that we’re close to an answer. Prime numbers also seem to be fundamental to practically all of mathematics – and, perhaps, to the physical universe itself.