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

When things get too complicated, it sometimes makes sense to stop and wonder: Have I asked the right question? Enrico Bombieri, ‘Prime Territory’ in The Sciences

Two centuries before Bombieri’s April Fool had teased the mathematical world, equally exciting news was being trumpeted from Palermo by another Italian, Giuseppe Piazzi. From his observatory Piazzi had detected a new planet that orbited the Sun somewhere between the orbits of Mars and Jupiter. Christened Ceres, it was much smaller than the seven major planets then known, but its discovery on January 1, 1801, was regarded by everyone as a great omen for the future of science in the new century.

Excitement turned to despair a few weeks later as the small planet disappeared from view as its orbit took it around the other side of the Sun, where its feeble light was drowned out by the Sun’s glare. It was now lost to the night sky, hidden once again amongst the plethora of stars in the firmament. Nineteenth-century astronomers lacked the mathematical tools for calculating its complete path from the short trajectory they had been able to track during the first few weeks of the new century. It seemed that they had lost the planet and had no way of predicting where it would next appear.

However, nearly a year after Piazzi’s planet had vanished, a twenty-four-year-old German from Brunswick announced that he knew where astronomers should find the missing object. With no alternative prediction to hand, astronomers aimed their telescopes at the region of the night sky to which the young man had pointed. As if by magic, there it was. This unprecedented astronomical prediction was not, however, the mysterious magic of an astrologer. The path of Ceres had been worked out by a mathematician who had found patterns where others had only seen a tiny, unpredictable planet. Carl Friedrich Gauss had taken the minimal data that had been recorded for the planet’s path and applied a new method he had recently developed to estimate where Ceres could be found at any future date.

The discovery of Ceres’ path made Gauss an overnight star within the scientific community. His achievement was a symbol of the predictive power of mathematics in the burgeoning scientific age of the early nineteenth century. Whereas the astronomers had discovered the planet by chance, it was a mathematician who had brought to bear the necessary analytic skills to explain what was going to happen next.

Although Gauss’s name was new to the astronomical fraternity, he had already made his mark as a formidable new voice in the mathematical world. He had successfully plotted the trajectory of Ceres, but his real passion was for finding patterns in the world of numbers. For Gauss, the universe of numbers presented the ultimate challenge: to find structure and order where others could only see chaos. ‘Child prodigy’ and ‘mathematical genius’ are titles that are bandied about far too often, but there are few mathematicians who would argue with these labels being attached to Gauss. The sheer number of new ideas and discoveries that he produced before he was even twenty-five seems to defy explanation.

Gauss was born into a labourer’s family in Brunswick, Germany, in 1777. At the age of three he was correcting his father’s arithmetic. At the age of nineteen, his discovery of a beautiful geometric construction of a 17-sided shape convinced him that he should dedicate his life to mathematics. Before Gauss, the Greeks had shown how to use a compass and straight edge to construct a perfect pentagon. No one since had been able to show how to use this simple equipment to construct other perfect, so-called regular polygons with a prime number of sides. The excitement that Gauss experienced when he found a way to build this perfect 17-sided shape prompted him to start a mathematical diary which he would keep for the next eighteen years. This diary, which remained in the family’s hands until 1898, has become one of the most important documents in the history of mathematics, not least because it confirmed that Gauss had proved, but failed to publish, many results that it took other mathematicians well into the nineteenth century to rediscover.

One of Gauss’s greatest early contributions was the invention of the clock calculator. This was an idea, rather than a physical machine, that unleashed the possibility of doing arithmetic with numbers that had previously been considered too unwieldy. The clock calculator works on exactly the same principle as a conventional clock. If your clock says it’s 9 o’clock, and you add 4 hours, the hour hand moves round to 1 o’clock. Gauss’s clock calculator would therefore return the answer 1 rather than 13. If Gauss wants to do a more complicated calculation such as 7 × 7, the clock calculator would come up with the remainder that is left after dividing 49 = 7 × 7 by 12. The result would again be 1 o’clock.

It is when Gauss wants to calculate the value of 7 × 7 × 7 that the power and speed of the clock calculator begins to emerge. Instead of multiplying 49 by 7 again, Gauss can just multiply the last answer (which was 1) by 7 to get the answer 7. So without having to calculate what 7 × 7 × 7 was (which happens to be 343), he still knew with little effort that it gave remainder 7 on division by 12. The power of the calculator came into its own when Gauss started exploring big numbers that lay beyond his computational reach. Although he had no idea what 7

was, his clock calculator told him that the number gave remainder 7 on division by 12.

Gauss saw that there was nothing special about clocks with 12 hours on their face. He introduced the idea of doing clock arithmetic, sometimes called modular arithmetic, with any number of hours on the clock face. So, for example, if you enter 11 into a clock calculator divided into 4 hours, the answer is 3 o’clock since 11 leaves remainder 3 on division by 4. Gauss’s account of this new sort of arithmetic revolutionised mathematics at the turn of the nineteenth century. Just as the telescope had allowed astronomers to see new worlds, the development of the clock calculator helped mathematicians to discover in the universe of numbers new patterns which had been hidden from view for generations. Even today, Gauss’s clocks are central to the security of the Internet, which utilises calculators whose clock faces bear more hours than there are atoms in the observable universe.

Gauss, the child of a poor family, was lucky to get the chance to capitalise on his mathematical talent. He was born into an age when mathematics was still a privileged pursuit funded by noble courts and patrons, or practised by amateurs such as Pierre de Fermat in their spare time. Gauss’s patron was the Duke of Brunswick, Carl Wilhelm Ferdinand. Ferdinand’s family had always supported the culture and economy of their dukedom. Indeed, his father had founded the Collegium Carolinum, one of the oldest technical universities in Germany. Ferdinand was imbued with his father’s ethos that education was the foundation of Brunswick’s commercial successes, and he was always on the lookout for talent deserving of support. Ferdinand first came across Gauss in 1791, and was so impressed with his abilities that he offered to finance the young man to attend the Collegium Carolinum so that he could realise his obvious potential.

It was with much gratitude that Gauss dedicated his first book to the duke in 1801. This book, entitled Disquisitiones Arithmeticae, collected together many of Gauss’s discoveries about the properties of numbers that he had recorded in his diaries. It is generally acknowledged as the book that heralded the birth of number theory as a subject in its own right, not just a ragbag collection of observations about numbers. Its publication is responsible for making the subject of number theory, as Gauss always liked to call it, ‘the Queen of Mathematics’. For Gauss, the jewels in the crown were the primes, numbers which had fascinated and teased generations of mathematicians.

The first tentative evidence that humankind knew about the special qualities of prime numbers is a bone that dates from 6500 BC. Called the Ishango bone, it was discovered in 1960 in the mountains of central equatorial Africa. Marked on it are three columns containing four groups of notches. In one of the columns we find 11, 13, 17 and 19 notches, a list of all the primes between 10 and 20. The other columns do seem to be of a mathematical nature. It is unclear whether this bone, housed in Belgium’s Royal Institute for Natural Sciences in Brussels, truly represents our ancestors’ first attempts to understand the primes or whether the carvings are a random selection of numbers which just happen to be prime. Nevertheless, this ancient bone is perhaps intriguing and tantalising evidence for the first foray into the theory of prime numbers.

Some believe that the Chinese were the first culture to hear the beating of the prime number drum. They attributed female characteristics to even numbers and male to odd numbers. In addition to this straight divide they also regarded those odd numbers that are not prime, such as 15, as effeminate numbers. There is evidence that by 1000 BC they had evolved a very physical way of understanding what it is, amongst all the numbers, that makes prime numbers special. If you take 15 beans, you can arrange them in a neat rectangular array made up of three rows of five beans. Take 17 beans, though, and the only rectangle you can make is one with a single row of 17 beans. For the Chinese, the primes were macho numbers which resisted any attempt to break them down into a product of smaller numbers.

The ancient Greeks also liked to attribute sexual qualities to numbers, but it was they who first discovered, in the 4th century BC, the primes’ true potency as the building blocks for all numbers. They saw that every number could be constructed by multiplying prime numbers together. Whilst the Greeks mistakenly believed fire, air, water and earth to be the building blocks of matter, they were spot on when it came to identifying the atoms of arithmetic. For many centuries, chemists strove to identify the basic constituents of their subject, and the Greeks’ intuition finally culminated in Dmitri Mendeleev’s Periodic Table, a complete description of the elements of chemistry. In contrast to the Greeks’ head start in identifying the building blocks of arithmetic, mathematicians are still floundering in their attempts to understand their own table of prime numbers.

The librarian of the great ancient Greek research institute in Alexandria was the first person we know of to have produced tables of primes. Like some ancient mathematical Mendeleev, Eratosthenes in the third century BC discovered a reasonably painless procedure for determining which numbers are prime in a list of, say, the first 1,000 numbers. He began by writing out all the numbers from 1 to 1,000. He then took the first prime, 2, and struck off every second number in the list. Since all these numbers were divisible by 2, they weren’t prime. He then moved to the next number that hadn’t been struck off, namely 3. He then stuck off every third number after 3. Since these were all divisible by 3, they weren’t prime either. He kept doing this, just picking up the next number which hadn’t already been struck from the list and striking off all the numbers divisible by the new prime. By this systematic process he produced tables of primes. The procedure was later christened the sieve of Eratosthenes. Each new prime creates a ‘sieve’ which Eratosthenes uses to eliminate non-primes. The size of the sieve changes at each stage, but by the time he reaches 1,000 the only numbers to have made it through all the sieves are prime numbers.

When Gauss was a young boy he was given a present – a book containing a list of the first several thousand prime numbers which had probably been constructed using these ancient number sieves. To Gauss, these numbers just tumbled around randomly. Predicting the elliptical path of Ceres would be difficult enough. But the challenge posed by the primes had more in common with the near-impossible task of analysing the rotation of bodies such as Hyperion, one of Saturn’s satellites, which is shaped like a hamburger. In contrast to the Earth’s Moon, Hyperion is far from gravitationally stable and spins chaotically. Even though the spinning of Hyperion and the orbits of some asteroids are chaotic, at least it is known that their behaviour is determined by the gravitational pull of the Sun and the planets. But for the primes, no one had the faintest idea what was pulling and pushing these numbers around. As he gazed at his table of numbers, Gauss could see no rule that told him how far to jump to find the next prime. Were mathematicians just going to have to accept these numbers as determined by Nature, set like stars in the night sky with no rhyme or reason? Such a position was unacceptable to Gauss. The primary drive for the mathematician’s existence is to find patterns, to discover and explain the rules underlying Nature, to predict what will happen next.

The search for patterns

The mathematician’s quest for primes is captured perfectly by one of the tasks we have all faced at school. Given a list of numbers, find the next number. For example, here are three challenges:

1, 3, 6, 10, 15, …

1, 1, 2, 3, 5, 8, 13, …

1, 2, 3, 5, 7, 11, 15, 22, 30, …

Numerous questions spring to the mathematical mind when faced with such lists. What is the rule behind the creation of each list? Can you predict the next number on the list? Can you find a formula that will produce the 100th number on the list without having to calculate the first 99 numbers?

The first sequence of numbers above consists of what are called the triangular numbers. The tenth number on the list is the number of beans required to build a triangle with ten rows, starting with one bean in the first row and ending with ten beans in the last row. So the Nth triangular number is got by simply adding the first N numbers: 1 + 2 + 3 + … + N. If you want to find the 100th triangular number, there is a long laborious method in which you attack the problem head on and add up the first 100 numbers.

Indeed, Gauss’s schoolteacher liked to set this problem for his class, knowing that it always took his students so long that he could take forty winks. As each student finished the task they were expected to come and place their slate tablets with their answer written on it in a pile in front of the teacher. While the other students began labouring away, within seconds the ten-year-old Gauss had laid his tablet on the table. Furious, the teacher thought that the young Gauss was being cheeky. But when he looked at Gauss’s slate, there was the answer – 5,050 – with no steps in the calculation. The teacher thought that Gauss must have cheated somehow, but the pupil explained that all you needed to do was put N = 100 into the formula

and you will get the 100th number in the list without having to calculate any other numbers on the list on the way.

Rather than tackling the problem head on, Gauss had thought laterally. He argued that the best way to discover how many beans there were in a triangle with 100 rows was to take a second similar triangle of beans which could be placed upside down on top of the first triangle. Now Gauss had a rectangle with 101 rows each containing 100 beans. Calculating the total number of beans in this rectangle built from the two triangles was easy: there are in total 101 × 100 = 10,100 beans. So one triangle must contain half this number, namely

. There is nothing special here about 100. Replace it by N and you get the formula

.

The picture overleaf illustrates the argument for the triangle with 10 rows instead of 100.

Instead of directly attacking his teacher’s problem, Gauss had found a different angle from which to view the calculation. Lateral thinking, turning the problem upside down or inside out to see it from a new perspective, is an immensely important theme in mathematical discovery and is one reason why people who can think like the young Gauss make good mathematicians.

The second challenge sequence, 1, 1, 2, 3, 5, 8, 13, …, consists of the so-called Fibonacci numbers. The rule behind this sequence is that each new number is calculated by adding the two previous ones, for example, 13 = 5 + 8. Fibonacci, a mathematician in the thirteenth-century court in Pisa, had struck upon the sequence in relation to the mating habits of rabbits. He had tried to bring European mathematics out of the Dark Ages by proselytising the discoveries of Arabic mathematicians. He failed. Instead, it was the rabbits that immortalised him in the mathematical world. His model of the propagation of rabbits predicted that each new season would see the number of pairs of rabbits grow in a certain pattern. This pattern was based on two rules: each mature pair of rabbits will produce a new pair of rabbits each season, and each new pair will take one season to reach sexual maturity.

An illustration of Gauss’s proof of his formula for the triangular numbers.

But it is not only in the rabbit world that these numbers prevail. This sequence of numbers crops up in all manner of natural ways. The number of petals on a flower invariably is a Fibonacci number, as is the number of spirals in a fir cone. The growth of a seashell over time reflects the progression of the Fibonacci numbers.

Is there a fast formula like Gauss’s formula for the triangular numbers that will produce the 100th Fibonacci number? Again, at first sight it looks as though we might have to calculate all the previous 99 numbers since the way to get the 100th number is to add together the two previous ones. Is it possible that there is a formula that could give us this 100th number just by plugging the number 100 into the formula? This turns out be much trickier, despite the simplicity of the rule for generating these numbers.

The formula for generating the Fibonacci numbers is based upon a special number called the golden ratio, a number which begins 1.618 03… Like the number π, the golden ratio is a number whose decimal expansion continues without end, demonstrating no patterns. Yet it encapsulates what many people down the centuries have regarded as perfect proportions. If you examine the canvases in the Louvre or the Tate Gallery, you’ll find that very often the artist will have chosen a rectangle whose sides are in a ratio of 1 to 1.618 03 … Experiment reveals that a person’s height when compared to the distance from their feet to their belly button favours the same ratio. The golden ratio is a number which appears in Nature in an uncanny fashion. Despite its chaotic decimal expansion, this number also holds the key to generating the Fibonacci numbers. The Nth Fibonacci number can be expressed by a formula built from the Nth power of the golden ratio.

I will leave the third sequence of numbers, 1, 2, 3, 5, 7, 11, 15, 22, 30, …, as a teasing challenge which I will return to later. Its properties helped cement the fame of one of the most intriguing mathematicians of the twentieth century, Srinivasa Ramanujan, who had an extraordinary ability to discover new patterns and formulas in areas of mathematics where others had tried and failed.

It is not just Fibonacci numbers that one finds in Nature. The animal kingdom also knows about prime numbers. There are two species of cicada called Magicicada septendecim and Magicicada tredecim which often live in the same environment. They have a life cycle of exactly 17 and 13 years, respectively. For all but their last year they remain in the ground feeding on the sap of tree roots. Then, in their last year, they metamorphose from nymphs into fully formed adults and emerge en masse from the ground. It is an extraordinary event as, every 17 years, Magicicada septendecim takes over the forest in a single night. They sing loudly, mate, eat, lay eggs, then die six weeks later. The forest goes quiet for another 17 years. But why has each species chosen a prime number of years as the length of their life cycle?

There are several possible explanations. Since both species have evolved prime number life cycles, they will be synchronised to emerge in the same year very rarely. In fact they will have to share the forest only every 221 = 17 × 13 years. Imagine if they had chosen cycles which weren’t prime, for example 18 and 12. Over the same period they would have been in synch 6 times, namely in years 36, 72, 108, 144, 180 and 216. These are the years which share the prime building blocks of both 18 and 12. The prime numbers 13 and 17, on the other hand, allow the two species of cicada to avoid too much competition.

Another explanation is that a fungus developed which emerged simultaneously with the cicadas. The fungus was deadly for the cicadas, so they evolved a life cycle which would avoid the fungus. By changing to a prime number cycle of 17 or 13 years, the cicadas ensured that they emerged in the same years as the fungus less frequently than if they had a non-prime life cycle. For the cicadas, the primes weren’t just some abstract curiosity but the key to their survival.

Evolution might be uncovering primes for the cicadas, but mathematicians wanted a more systematic way to find these numbers. Of all the number challenges it was the list of primes above all others for which mathematicians sought some secret formula. One has to be careful, though, about expecting patterns and order to be everywhere in the mathematical world. Many people throughout history have got lost in the vain attempt to find structure hidden in the decimal expansion of π, one of the most important numbers in mathematics. But its importance has fuelled desperate attempts to discover messages buried in its chaotic decimal expansion. Whilst alien life had used the primes to catch Ellie Arroway’s attention at the beginning of Carl Sagan’s book Contact, the ultimate message of the book is buried deep in the expansion of π, in which a series of O’s and l’s suddenly appears, mapping out a pattern that is meant to reveal ‘there is an intelligence that antedates the universe’. Darren Aronofsky’s film ‘π’ also plays on this popular cultural image.

As a warning to those captivated by the idea of uncovering hidden messages in numbers such as π, mathematicians have been able to prove that most decimal numbers have hidden somewhere in their infinite expansions any sequence of numbers you might be looking for. So there is a good chance that π will contain the computer code for the book of Genesis if you search for long enough. One has to find the right viewpoint from which to look for patterns. π is an important number not because its decimal expansion contains hidden messages. Its importance becomes apparent when it is examined from a different perspective. The same was true of the primes. Armed with his table of primes and his knack for lateral thinking, Gauss was on the lookout for the right angle and viewpoint from which to stare at the primes so that some previously hidden order might emerge from behind the façade of chaos.

Proof, the mathematician’s travelogue

Although finding patterns and structure in the mathematical world is one part of what a mathematician does, the other part is proving that a pattern will persist. The concept of proof perhaps marks the true beginning of mathematics as the art of deduction rather than just numerological observation, the point at which mathematical alchemy gave way to mathematical chemistry. The ancient Greeks were the first to understand that it was possible to prove that certain facts would remain true however far you counted, however many instances you examined.

The mathematical creative process starts with a guess. Often, the guess emerges from the intuition that the mathematician develops after years of exploring the mathematical world, cultivating a feel for its many twists and turns. Sometimes simple numerical experiments reveal a pattern which one might guess will persist for ever. Mathematicians during the seventeenth century, for example, discovered what they believed might be a fail-safe method to test if a number N was prime: calculate 2 to the power N and divide by N – if the remainder is 2 then the number N is a prime. In terms of Gauss’s clock calculator, these mathematicians were trying to calculate 2

on a clock with N hours. The challenge then is to prove whether this guess is right or wrong. It is these mathematical guesses or predictions that the mathematician calls a ‘conjecture’ or ‘hypothesis’.

A mathematical guess only earns the name of ‘theorem’ once a proof has been provided. It is this movement from ‘conjecture’ or ‘hypothesis’ to ‘theorem’ that marks the mathematical maturity of a subject. Fermat left mathematics with a whole slew of predictions. Subsequent generations of mathematicians have made their mark by proving Fermat right or wrong. Admittedly, Fermat’s Last Theorem was always called a theorem and never a conjecture. But that is unusual, and probably came about because Fermat claimed in notes that he scribbled in his copy of Diophantus’s Arithmetica that he had a marvellous proof that was unfortunately too large to write in the margin of the page. Fermat never recorded his supposed proof anywhere, and his marginal comments became the biggest mathematical tease in the history of the subject. Until Andrew Wiles provided an argument, a proof of why Fermat’s equations really had no interesting solutions, it actually remained a hypothesis – merely wishful thinking.

Gauss’s schoolroom episode encapsulates the movement from guess via proof to theorem. Gauss had produced a formula which he predicted would produce any number you wanted on the list of triangular numbers. How could he guarantee that it would work every time? He certainly couldn’t test every number on the list to see whether his formula gave the correct answer, since the list is infinitely long. Instead, he resorted to the powerful weapon of mathematical proof. His method of combining two triangles to make a rectangle guaranteed, without the need for an infinite number of calculations, that the formula would always work. In contrast, the seventeenth-century prime number test based on 2

was finally thrown out of the mathematical court in 1819. The test works correctly for all numbers up to 340, but then declares that 341 is prime. This is where the test fails, since 341 = 11 × 31. This exception wasn’t discovered until Gauss’s clock calculator with 341 hours on the clock face could be used to simplify the analysis of a number like 2