The Music of the Primes: Why an unsolved problem in mathematics matters. Marcus Sautoy du

number theory entitled Théorie des Nombres.

      The controversy over who first discovered the connection between primes and logarithms led to a bitter dispute between Legendre and Gauss. It was not limited to the argument about primes – Legendre even claimed that he had been the first to discover Gauss’s method for establishing the motion of Ceres. Time and again, Legendre’s assertion that he had uncovered some mathematical truth would be countered by an announcement by Gauss that he had already plundered that particular treasure. Gauss commented in a letter of July 30, 1806, written to an astronomical colleague named Schumacher, ‘It seems to be my fate to concur in nearly all my theoretical works with Legendre.’

      In his lifetime, Gauss was too proud to get involved in open battles of priority. When Gauss’s papers and correspondence were examined after his death, it became clear that due credit invariably went to Gauss. It wasn’t until 1849 that the world learnt that Gauss had beaten Legendre to the connection between primes and logarithms, which Gauss disclosed in a letter to a fellow mathematician and astronomer, Johann Encke, written on Christmas Eve of that year.

      Given the data available at the start of the nineteenth century, Legendre’s function was much better than Gauss’s formula as an approximation to the number of primes up to some number N. But the appearance of the rather ugly correction term 1.083 66 made mathematicians believe that something better and more natural must exist to capture the behaviour of the prime numbers.

      Such ugly numbers may be commonplace in other sciences, but it is remarkable how often the mathematical world favours the most aesthetic possible construction. As we shall see, Riemann’s Hypothesis can be interpreted as an example of a general philosophy among mathematicians that, given a choice between an ugly world and an aesthetic one. Nature always chooses the latter. It is a constant source of amazement for most mathematicians that mathematics should be like this, and explains why they so often get wound up about the beauty of their subject.

      It is perhaps not surprising that in later life Gauss further refined his guess and arrived at an even more accurate function, one which was also much more beautiful. In the same Christmas Eve letter that Gauss wrote to Encke, he explains how he subsequently discovered how to go one better than Legendre’s improvement. What Gauss did was to go back to his very first investigations as a child. He had calculated that amongst the first 100 numbers, 1 in 4 are prime. When he considered the first 1,000 numbers the chance that a number is prime went down to 1 in 6. Gauss realised that the higher you count, the smaller the chance that a number will be prime.

      So Gauss formed a picture in his mind of how Nature might have decided which numbers were going to be prime and which were not. Since their distribution looked so random, might tossing a coin not be a good model for choosing primes? Did Nature toss a coin – heads it’s prime, tails it’s not? Now, thought Gauss, the coin could be weighted so that instead of landing heads half the time, it lands heads with probability 1/log(N). So the probability that the number 1,000,000 is prime should be interpreted as l/log(1,000,000), which is about 1/15. The chances that each number N is a prime gets smaller as N gets bigger because the probability 1/log(N) of coming up heads is getting smaller.

      This is just a heuristic argument because 1,000,000 or any other particular number is either prime or it isn’t. No toss of a coin can alter that. Although Gauss’s mental model was useless at predicting whether a number is prime, he found it very powerful at making predictions about the less specific question of how many primes one might expect to encounter as one counted higher. He used it to estimate the number of primes you should get after tossing the prime number coin N times. With a normal coin which lands heads with probability ½, the number of heads should be ½N. But the probability with the prime number coin is getting smaller with each toss. In Gauss’s model the number of primes is predicted to be

      Gauss actually went one step further to produce a function which he called the logarithmic integral, denoted by Li(N). The construction of this new function was based on a slight variation of the above sum of probabilities, and it turned out to be stunningly accurate.

      By the time Gauss, in his seventies, wrote to Encke, he had constructed tables of primes up to 3,000,000. ‘I very often used an idle quarter of an hour to count through another chiliad [an interval of 1,000 numbers] here and there’ in his search for prime numbers. His estimate for primes less than 3,000,000 using his logarithmic integral is a mere seven hundredths of 1 per cent off the mark. Legendre had managed to massage his ugly formula to match π(N) for small N, so with the data available at the time it looked as if Legendre’s formula was superior. As more extensive tables began to be drawn up, they revealed that Legendre’s estimate grew far less accurate for primes beyond 10,000,000. A professor at the University of Prague, Jakub Kulik, spent twenty years single-handedly constructing tables of primes for numbers up to 100,000,000. The eight volumes of this gargantuan effort, completed in 1863, were never published but were deposited in the archives of the Academy of Sciences in Vienna. Although the second volume has gone astray, the tables already revealed that Gauss’s method, based on his Li(N) function, was once again outstripping Legendre’s. Modern tables show just how much better Gauss’s intuition was. For example, his estimate for the number of primes up to 10¹⁶ (i.e. 10,000,000,000,000,000) deviates from the correct value by just one ten-millionth of 1 per cent, whilst Legendre’s is now off by one-tenth of 1 per cent. Gauss’s theoretical analysis had triumphed over Legendre’s attempts to manipulate his formula to match the available data.

      Gauss noticed a curious feature about his method. Based on what he knew about the primes up to 3,000,000, he could see that his formula Li(N always appeared to overestimate the number of primes. He conjectured that this would always be the case. And who wouldn’t back Gauss’s hunch, now that modern numerical evidence confirms Gauss’s conjecture up to 10¹⁶? Certainly any experiment that produced the same result 10¹⁶ times would be regarded as pretty convincing evidence in most laboratories – but not in the mathematician’s. For once, one of Gauss’s intuitive guesses turned out to be wrong. But although mathematicians have now proved that eventually π(N) must sometimes overtake Li(N), no one has ever seen it happen because we can’t count far enough yet.

      A comparison of the graphs of π(N) and Li(N) shows such a good match that over a large range it is barely possible to distinguish the two. I should stress that a magnifying glass applied to any portion of such a picture will show that the functions are different. The graph of π(N) looks like a staircase, whilst Li(N) is a smooth graph with no sharp jumps.

      Gauss had uncovered evidence of the coin that Nature had tossed to choose the primes. The coin was weighted so that a number N has a chance of 1 in log(N) of being prime. But he was still missing a method of predicting precisely the tosses of the coin. That would take the insight of a new generation.

      By shifting his perspective, Gauss had perceived a pattern in the primes. His guess became known as the Prime Number Conjecture. To claim Gauss’s prize, mathematicians had to prove that the percentage error between Gauss’s logarithmic integral and the real number of primes gets smaller and smaller the further you count. Gauss had seen this far-off mountain peak, but it was left to future generations to provide a proof, to reveal the pathway to the summit, or to unmask the connection as an illusion.

      Many blame the appearance of Ceres for distracting Gauss from proving the Prime Number Conjecture himself. The overnight fame he received at the age of twenty-four steered him towards astronomy, and mathematics no longer had pride of place. When his patron, Duke Ferdinand, was killed by Napoleon in 1806, Gauss was forced to find other employment to support his family. Despite overtures from the Academy in St Petersburg, which was seeking a successor to Euler, he chose instead to accept a position as director of the Observatory in Göttingen, a small university town in Lower Saxony. He spent his time tracking more asteroids through the night sky and completing surveys of the land for the Hanoverian and Danish governments. But he was always thinking about mathematics. Whilst charting the mountains of Hanover he would ponder Euclid’s axiom of parallel lines, and back