The Music of the Primes: Why an unsolved problem in mathematics matters

, which on a conventional calculator stretches to over a hundred digits.

The Cambridge mathematician G. H. Hardy, author of A Mathematician’s Apology, used to describe the process of mathematical discovery and proof in terms of mapping out distant landscapes: ‘I have always thought of a mathematician as in the first instance an observer, a man who gazes at a distant range of mountains and notes down his observations.’ Once the mathematician has observed a distant mountain, the second task is then to describe to people how to get there.

You begin in a place where the landscape is familiar and there are no surprises. Within the boundaries of this familiar land are the axioms of mathematics, the self-evident truths about numbers, together with those propositions that have already been proved. A proof is like a pathway from this home territory leading across the mathematical landscape to distant peaks. Progress is bound by the rules of deduction, like the legitimate moves of a chess piece, prescribing the steps you are permitted to take through this world. At times you arrive at what looks like an impasse, and need to take that characteristic lateral step, moving sideways or even backwards to find a way around. Sometimes you need to wait for new tools, like Gauss’s clock calculators, to be invented, so that you can continue your ascent.

In Hardy’s words, the mathematical observer

sees A sharply, while of B he can obtain only transitory glimpses. At last he makes out a ridge which leads from A, and following it to its end he discovers that it culminates in B. If he wishes someone else to see it, he points to it, either directly or through the chain of summits which led him to recognise it himself. When his pupil also sees it, the research, the argument, the proof is finished.

The proof is the story of the trek and the map charting the coordinates of that journey – the mathematician’s log. Readers of the proof will experience the same dawning realisation as its author. Not only do they finally see the way to the peak, but also they understand that no new development will undermine the new route. Very often a proof will not seek to dot every i and cross every t. It is a description of the journey and not necessarily the re-enactment of every step. The arguments that mathematicians provide as proofs are designed to create a rush in the mind of the reader. Hardy used to describe the arguments we give as ‘gas, rhetorical flourishes designed to affect psychology, pictures on the board in the lecture, devices to stimulate the imagination of pupils’.

The mathematician is obsessed with proof, and will not be satisfied simply with experimental evidence for a mathematical guess. This attitude is often marvelled at and even ridiculed in other scientific disciplines. Goldbach’s Conjecture has been checked for all numbers up to 400,000,000,000,000 but has not been accepted as a theorem. Most other scientific disciplines would be happy to accept this overwhelming numerical data as a convincing enough argument, and move on to other things. If, at a later date, new evidence were to crop up which required a reassessment of the mathematical canon, then fine. If it is good enough for the other sciences, why is mathematics any different?

Most mathematicians would quiver at the thought of such heresy. As the French mathematician André Weil expressed it, ‘Rigour is to the mathematician what morality is to men.’ Part of the reason is that evidence is often quite hard to assess in mathematics. More than any other part of mathematics, the primes take a long time to reveal their true colours. Even Gauss was taken in by overwhelming data in support of a hunch he had about prime numbers, but theoretical analysis later revealed that he had been duped. This is why a proof is essential: first appearances can be deceptive. While the ethos of every other science is that experimental evidence is all that you can truly rely on, mathematicians have learnt never to trust numerical data without proof.

In some respects, the ethereal nature of mathematics as a subject of the mind makes the mathematician more reliant on providing proof to lend some feeling of reality to this world. Chemists can happily investigate the structure of a solid buckminsterfullerene molecule; sequencing the genome presents the geneticist with a concrete challenge; even the physicists can sense the reality of the tiniest subatomic particle or a distant black hole. But the mathematician is faced with trying to understand objects with no obvious physical reality such as shapes in eight dimensions, or prime numbers so large they exceed the number of atoms in the physical universe. Given a palette of such abstract concepts the mind can play strange tricks, and without proof there is a danger of creating a house of cards. In the other scientific disciplines, physical observation and experiment provide some reassurance of the reality of a subject. While other scientists can use their eyes to see this physical reality, mathematicians rely on mathematical proof, like a sixth sense, to negotiate their invisible subject.

Searching for proofs of patterns that have already been spotted is also a great catalyst for further mathematical discovery. Many mathematicians feel that it may be better if these defining problems never get solved because of the wonderful new mathematics encountered along the way. The problems allow for exploration of a kind which forces mathematical pioneers to pass through lands they could never have envisaged at the outset of their journey.

But perhaps the most convincing argument for why the culture of mathematics places such stock in proving that a statement is true is that, unlike the other sciences, there is the luxury of being able to do so. In how many other disciplines is there anything that parallels the statement that Gauss’s formula for triangular numbers will never fail to give the right answer? Mathematics may be an ethereal subject confined to the mind, but its lack of tangible reality is more than compensated for by the certitude that proof provides.

Unlike the other sciences, in which models of the world can crumble between one generation and the next, proof in mathematics allows us to establish with 100 per cent certainty that facts about prime numbers will not change in the light of future discoveries. Mathematics is a pyramid where each generation builds on the achievements of the last without fear of any collapse. This durability is what is so addictive about being a mathematician. For no science other than mathematics can we say that what the ancient Greeks established in their subject holds true today. We may scoff now at the Greeks’ belief that matter was made from fire, air, water and earth. Will future generations look back on the list of 109 atoms that make up Mendeleev’s Periodic Table of elements with as much disdain as we view the Greek model of the chemical world? In contrast, all mathematicians begin their mathematical education by learning what the ancient Greeks proved about prime numbers.

The certainty that proof gives to the mathematician is something that is envied by members of other university departments as much as it is jeered at. The permanence created by mathematical proof leads to the genuine immortality to which Hardy referred. This is often why people surrounded by a world of uncertainty are drawn to the subject. Time after time has the mathematical world offered a refuge for young minds yearning to escape from a real world they cannot cope with.

Our faith in the durability of a proof is reflected in the rules governing the award of Clay’s Millennium Prizes. The prize money is released two years after publication of the proof and with the general acceptance of the mathematical community. Of course, this is no guarantee that there isn’t a subtle error, but it does recognise that we generally believe that errors can be spotted in proofs without waiting many years for new evidence. If there is an error, it must be there on the page in front of us.

Are mathematicians arrogant in believing that they have access to absolute proof? Can one argue that a proof that all numbers are built from primes is as likely to be overthrown as the theory of Newtonian physics or the theory of an indivisible atom? Most mathematicians believe that the axioms that are taken as self-evident truths about numbers will never crumble under future scrutiny. The laws of logic used to build upon these foundations, if applied correctly, will in their view produce proofs of statements about numbers that will never be overturned by new insights. Maybe this is philosophically naive, but it is certainly the central tenet of the sect of mathematics.

There is also the emotional buzz the mathematician experiences in charting new pathways across the mathematical landscape. There is an amazing feeling of exhilaration at discovering a way to reach the summit of some distant peak which has been visible for generations. It is like creating a wonderful story or a piece of music which truly transports the mind from the familiar to the unknown. It is great to make that first sighting of the possible existence of a far-off mountain like Fermat’s Last Theorem or the Riemann Hypothesis. But it doesn’t compare to the satisfaction of navigating the land in between. Even those who follow in the trail of that first pioneer will experience something of the sense of spiritual elevation that accompanied the first moment of epiphany at discovering a new proof. And this is why mathematicians continue to value the pursuit of proof even if they are utterly convinced that something like the Riemann Hypothesis is true. Because mathematics is as much about travelling as it is about arrival.

Is mathematics an act of creation or an act of discovery? Many mathematicians fluctuate between feeling they are being creative and a sense they are discovering absolute scientific truths. Mathematical ideas can often appear very personal and dependent on the creative mind that conceived them. Yet that is balanced by the belief that its logical character means that every mathematician is living in the same mathematical world that is full of immutable truths. These truths are simply waiting to be unearthed, and no amount of creative thinking will undermine their existence. Hardy encapsulates perfectly this tension between creation and discovery that every mathematician battles with: ‘I believe that mathematical reality lies outside us, that our function is to discover or observe it and that the theorems which we prove and which we describe grandiloquently as our “creations” are simply our notes of our observations.’ But at other times he favoured a more artistic description of the process of doing mathematics: ‘Mathematics is not a contemplative but a creative subject,’ he wrote in A Mathematician’s Apology, a book Graham Greene ranked with Henry James’s notebooks as the best account of what it is like to be a creative artist.

Although the primes, and other aspects of mathematics, transcend cultural barriers, much of mathematics is creative and a product of the human psyche. Proofs, the stories mathematicians tell about their subject, can often be narrated in different ways. It is likely that Wiles’s proof of Fermat’s Last Theorem would be as mysterious to aliens as listening to Wagner’s Ring cycle. Mathematics is a creative art under constraints – like writing poetry or playing the blues. Mathematicians are bound by the logical steps they must take in crafting their proofs. Yet within such constraints there is still a lot of freedom. Indeed, the beauty of creating under constraints is that you get pushed in new directions and find things you might never have expected to discover unaided. The primes are like notes in a scale, and each culture has chosen to play these notes in its own particular way, revealing more about historical and social influences than one might expect. The story of the primes is a social mirror as much as the discovery of timeless truths. The burgeoning love of machines in the seventeenth and eighteenth centuries is reflected in a very practical, experimental approach to the primes; in contrast, Revolutionary Europe created an atmosphere where new abstract and daring ideas were brought to bear on their analysis. The choice of how to narrate the journey through the mathematical world is something which is specific to each individual culture.

Euclid’s fables

The first to start telling these stories were the ancient Greeks. They realised the power of proof to forge permanent pathways to mountains in the mathematical world. Once they were reached, no longer was there the fear that these mountains were some distant mathematical mirage. For example, how can we be really sure that there aren’t some rogue numbers out there which can’t actually be built by multiplying together prime numbers? The Greeks were the first to come up with an argument that would leave no doubt in their minds or in the minds of future generations that no such rogue numbers could ever turn up.

Mathematicians often discover proofs by taking a particular instance of the general theory they are trying to prove, and begin by trying to understand why the theory is true for this example. They hope that the argument or recipe that was successful when applied to the example will work regardless of the particular case they chose to analyse. For instance, to prove that every number is a product of primes, start by considering the particular case of the number 140. Suppose you had checked that every number below 140 is either a prime number or the product of prime numbers multiplied together. What about the number 140 itself? Is it possible that this is a rogue number which is neither prime nor equal to a product of prime numbers? First, you would discover that the number is not prime. How would you do this? By showing it could be written as two smaller numbers multiplied together. For example, 140 is 4 × 35. Now we are ‘in’ because we have already confirmed that 4 and 35, numbers lower than our first candidate rogue, 140, can be written as primes multiplied together: 4 is 2 × 2 and 35 is 5 × 7. Piecing this information together, we see that 140 is in fact the product 2 × 2 × 5 × 7. So 140 is not a rogue after all.

The Greeks understood how they could translate this particular example into a general argument that would apply to all numbers. Curiously, their argument begins by asking us to imagine that there are such rogue numbers – ones that are neither prime nor can be written as prime numbers multiplied together. If there are such rogues, then, as we count through the sequence of all the numbers, we must eventually encounter the first of these rogue numbers. We shall call it N (it is sometimes referred to as the minimal criminal). Since this hypothetical number N isn’t a prime number, we must be able to write it as two smaller numbers, A and B, multiplied together. After all, if that weren’t possible, N would be prime.

Since A and B are smaller than N, our choice of N implies that A and B can be written as products of primes. So if we multiply together all the primes coming from A and all the primes coming from B, then we must get the original number, N. We have now shown that N can be written as prime numbers multiplied together, which contradicts our original choice of N. So our original assumption that there were rogue numbers can’t be tenable. Hence every number must be prime or built by multiplying primes.

When I tried this argument out on friends, they felt as if they had been cheated somewhere along the way. There is something slightly slippery about our opening gambit: assume the things you don’t want to exist do exist, and end up proving they don’t. This strategy of thinking the unthinkable became a powerful tool in the Greeks’ construction of proofs. It relies on the logical fact that a statement has to be either true or false. If we assume the statement is false and we get a contradiction, we can infer that our assumption was wrong and deduce that the statement must have been true after all.

The Greek proof appeals to the lazy side of most mathematicians. Instead of being faced with the impossible task of doing an infinite number of explicit calculations to prove that all numbers can be built from primes, the abstract argument captures the essence of every such computation. It’s like knowing how to climb an infinite ladder without physically having to perform the task.

More than any other Greek mathematician, Euclid is regarded as the father of the art of proof. He was part of the research institute that the Greek leader Ptolemy I established in Alexandria around 300 BC. There, Euclid wrote one of the most influential textbooks in all of recorded history: The Elements. In the first part of this book he set down axioms for geometry describing the relationship between points and lines. These axioms were put forward as self-evident truths about the objects of geometry, so that geometry would then act as a mathematical description of the physical world. He went on to use the rules of deduction to produce five hundred theorems of geometry.

The middle part of Euclid’s Elements deals with the properties of numbers, and it is here that we find what many regard as the first truly brilliant piece of mathematical reasoning. In Proposition 20, Euclid explains a simple but fundamental truth about prime numbers: there are infinitely many of them. He begins with the fact that every number can be built by multiplying prime numbers together. On top of this he constructs his next proof. If these prime numbers are the building blocks of all numbers, is it possible, he asks himself, for there to be only a finite number of these building blocks? The Periodic Table of the chemical elements was constructed by Mendeleev, and in its present form it classifies 109 different atoms from which we can build all matter. Could the same be true for prime numbers? What if a mathematical Mendeleev presented Euclid with a list of 109 primes and challenged Euclid to prove that some primes were missing from the list?

Why, for example, can’t all numbers be built simply by multiplying together different combinations of the primes 2, 3, 5 and 7? Euclid thought about how you might look for numbers that aren’t built from any of these primes. You might say, ‘Well that’s easy – just take the next prime, 11.’ This certainly can’t be built from 2, 3, 5 and 7. But sooner or later this strategy is going to fail precisely because, even today, we have no clue about how to guarantee finding where the next prime will be. And because of this unpredictability, Euclid had to try a different tack in his search for a method that would work, regardless of how long the list of primes was.

Whether it was truly Euclid’s own idea or whether he was simply recording ideas that others had dreamt up in Alexandria, we have no way of knowing. Whichever it was, he was able to show how to build a number that couldn’t be built from any finite list of primes that he might be given. Take the primes 2, 3, 5 and 7. Euclid multiplied them together to get 2 × 3 × 5 × 7 = 210, then – and this is his act of genius – he added 1 to this product to get 211. Euclid had constructed this number, 211, in such a way that none of the primes in the list, 2, 3, 5 and 7, would divide into it exactly. By adding 1 to the product, he could guarantee that dividing by a prime on the list would always leave remainder 1.

Now, Euclid knew that all numbers were built by multiplying together primes. So what about 211? Since it can’t be divided by 2, 3, 5 or 7, there had to be some other primes not on the list that built the number 211. In this particular example, 211 is itself a prime. Euclid was not claiming that the number he built would always be prime – only that it was a number that was built out of primes that were not on the list that our mathematical Mendeleev was offering us.

For example, what if one claimed that all numbers could be built from the finite list of primes 2, 3, 5, 7, 11 and 13. Euclid’s number built from these primes is 2 × 3 × 5 × 7 × 11 × 13 + 1 = 30,031. This number is not a prime. All Euclid was saying was that, given any list containing finitely many primes, he could produce a number that had to be built out of primes that were not on the list. In this particular case the primes you need are 59 and 509. But in general, Euclid had no way of knowing how to find the precise value of these new primes. He knew only that they must exist.

It was a wonderful argument. Euclid had no idea how to produce primes explicitly, but he could prove why they would never run dry. It is striking that we do not know whether infinitely many of Euclid’s numbers themselves are prime, even though they are sufficient to prove that there must be an infinite number of primes. With Euclid’s proof, gone was the chance of fitting together a Periodic Table listing all the primes or of discovering some prime number genome coding billions of them. No simple butterfly collecting would ever allow us to understand these numbers. Here, then, was the ultimate challenge: the mathematician, armed with a limited weaponry, pitched against the infinite expanse of prime numbers. How could we possibly chart a path through such an infinite chaotic jumble and find some pattern which might predict their behaviour?

Hunting for primes

Generations have striven without success to improve on Euclid’s understanding of the primes, and there have been many intriguing speculations. But as Cambridge don Hardy liked to say, ‘Every fool can ask questions about prime numbers that the wisest man cannot answer.’ The Twin Primes Conjecture, for example, asks whether there are infinitely many primes p such that the number p + 2 is also prime. An example of such a pair is 1,000,037 and 1,000,039. (Note that this is the closest that two primes numbers can be, since N and N + 1 cannot both be prime – except when N = 2 – because at least one of these numbers is divisible by 2.) Might Sacks’s autistic-savant twins have had an extra facility for finding these twin primes? Euclid proved two millennia ago that there are infinitely many primes, but no one knows whether there might be some number beyond which there are no longer such close primes. We believe that there are infinitely many twin primes. Guesses are one thing, but proof remains the ultimate goal.

Mathematicians tried, with varying degrees of success, to come up with formulas that, even if they don’t generate all prime numbers, do produce a list of primes. Fermat thought he had one. He guessed that if you raise 2 to the power 2

and add 1, the resulting number

is a prime. This number is called the Nth Fermat number. For example, taking N = 2 and raising 2 to the power 2

= 4, you get 16. Add 1 and you get the prime number 17, the second Fermat number. Fermat thought that his formula would always give him a prime number, but it turned out to be one of the few guesses that he got wrong. The Fermat numbers get very large very quickly. Even the fifth Fermat number has 10 digits, and was out of Fermat’s computational reach. It is the first Fermat number which is not prime, being divisible by 641.

Fermat’s numbers were very dear to Gauss’s heart. The fact that 17 is one of Fermat’s primes is the key to why Gauss could construct his perfect 17-sided shape. In his great treatise Disquisitiones Arithmeticae, Gauss shows why it is that, if the Nth Fermat number is a prime, you can make a geometric construction of an N-sided shape only using a straight edge and compass. The fourth Fermat number, 65,537, is prime, so with these very basic instruments it is possible to construct a perfect 65,537-sided figure.

Fermat’s numbers have failed to throw up more than four primes to date, but he had more success in uncovering some of the very special properties that prime numbers have. Fermat discovered a curious fact about those prime numbers that leave remainder 1 on division by 4 – examples are 5, 13, 17 and 29. Such prime numbers can always be written as the sum of two squares – for example, 29 = 2

+ 5

. This was another of Fermat’s teases. Although he claimed to have a proof, he failed to record much of the details.

On Christmas Day, 1640, Fermat wrote of his discovery – that certain primes could be expressed as the sum of two squares – in a letter to a French monk called Marin Mersenne. Mersenne’s interests were not confined to liturgical matters. He loved music and was the first to develop a coherent theory of harmonics. He also loved numbers. Mersenne and Fermat corresponded regularly about their mathematical discoveries, and Mersenne broadcast many of Fermat’s claims to a wider audience. Mersenne became renowned for his role as an international scientific clearing house through which mathematicians could disseminate their ideas.

Just as generations had been captivated by the search for order in the primes, Mersenne too had caught the bug. Although he couldn’t see a way to find a formula that would produce all the primes, he did come across a formula that in the long run has proved far more successful at finding primes than Fermat’s formula has. Like Fermat, he started by considering powers of 2. But instead of adding 1, as Fermat had, Mersenne decided to subtract 1 from the answer. So, for example, 2

− 1 = 8 − 1 = 7, a prime number. Maybe Mersenne’s musical intuition was coming to his aid. Doubling the frequency of a note takes the note up an octave, so powers of 2 produce harmonic notes. You might expect a shift of 1 to sound a very dissonant note, not compatible with any previous frequency – a ‘prime note’.

Mersenne quickly discovered that his formula wasn’t going to yield a prime every time. For example, 2

− 1 = 15. Mersenne realised that if n was not prime then there was no chance that 2

− 1 was going to be prime. But now he boldly claimed that, for n up to 257, 2

− 1 would be prime precisely if n was one of the following numbers: 2, 3, 5, 7, 13, 19, 31, 67, 127, 257. He had discovered that even if n was prime, it still annoyingly didn’t guarantee that his number 2

− 1 would be prime. He could calculate 2