Читать книгу The Music of the Primes: Why an unsolved problem in mathematics matters - Marcus Sautoy du - Страница 14

If centuries of searching had failed to unearth some magic formula which would generate the list of prime numbers, perhaps it was time to adopt a different strategy. This was what the fifteen-year-old Gauss was thinking in 1792. He had been given a book of logarithms as a present the previous year. Until a few decades ago, tables of logarithms were familiar to every teenager doing calculations in the schoolroom. With the advent of pocket calculators, they lost their place as an essential tool in everyday life, but several hundred years ago every navigator, banker and merchant would have been exploiting these tables to turn difficult multiplication into simple addition. Included at the back of Gauss’s new book was a table of prime numbers. It was uncanny that primes and logarithms should appear together, because Gauss noticed after extensive calculations that there seemed to be a connection between these two seemingly unrelated topics.

The first table of logarithms was conceived in 1614 in an age when sorcery and science were bedfellows. Their creator, the Scottish Baron John Napier, was regarded by local residents as a magician who dealt in the dark arts. He skulked around his castle dressed in black, a jet-black cock perched on his shoulder, muttering that his apocalyptic algebra foretold that the Last Judgement would fall between 1688 and 1700. But as well as applying his mathematical skills to the practice of the occult, he also uncovered the magic of the logarithm function.

If you feed a number, say 100, into your calculator and then press the ‘log’ button, the calculator spits out a second number, the logarithm of 100. What your calculator has done is to solve a little puzzle: it has looked for the number x that makes the equation 10^x = 100 correct. In this case the calculator outputs the answer 2. If we input 1,000, a number ten times larger than 100, then the new answer output by your calculator is 3. The logarithm goes up by 1. Here is the essential character of the logarithm: it turns multiplication into addition. Each time we multiply the input by 10, we get the new output by adding 1 to the previous answer.

It was a fairly major step for mathematicians to realise that they could talk about logarithms of numbers which weren’t whole-number powers of 10. For example, Gauss would have been able to look up in his tables the logarithm of 128 and find that raising 10 to the power 2.107 21 would get him pretty close to 128. These calculations are what Napier had collected together in the tables that he had produced in 1614.

Tables of logarithms helped to accelerate the world of commerce and navigation that was blossoming in the seventeenth century. Because of the dialogue that logarithms created between multiplication and addition, the tables helped to convert a complicated problem of multiplying together two large numbers into the simpler task of adding their logarithms. To multiply together large numbers, merchants would add together the logarithms of the numbers and then use the log tables in reverse to find the result of the original multiplication. The increase in speed that the sailor or seller would gain via these tables might save the wrecking of a ship or the collapse of a deal.

But it was the supplementary table of prime numbers at the back of his book of logarithms that fascinated the young Gauss. In contrast to the logarithms, these tables of primes were nothing more than a curiosity to those interested in the practical application of mathematics. (Tables of primes constructed in 1776 by Antonio Felkel were considered so useless that they ended up being used for cartridges in Austria’s war with Turkey!) The logarithms were very predictable; the primes were completely random. There seemed no way to predict when to expect the first prime after 1,000, for example.

The important step Gauss took was to ask a different question. Rather than attempting to predict the precise location of the next prime, he tried instead to see whether he could at least predict how many primes there were in the first 100 numbers, the first 1,000 numbers, and so on. If one took any number N, was there a way to estimate how many primes one would expect to find amongst the numbers from 1 to N? For example, there are twenty-five prime numbers up to 100. So you have a one in four chance of getting a prime if you choose a number at random between 1 and 100. How does this proportion change if we look at the primes from 1 to 1000, or 1 to 1,000,000? Armed with his prime number tables, Gauss began his quest. As he looked at the proportion of numbers that were prime, he found that when he counted higher and higher a pattern started to emerge. Despite the randomness of these numbers, a stunning regularity seemed to be looming out of the mist.

If we look at the table overleaf of values of the number of primes up to various powers of ten, based on more modern calculations, this regularity becomes apparent.

This table, which contains much more information than was available to Gauss, shows us more clearly the regularity that Gauss discovered. It is in the last column that the pattern manifests itself. This column represents the proportion of prime numbers amongst all the numbers being considered. For example, 1 in 4 numbers are prime counting up to 100, so in that interval you will need to count, on average, 4 to get from one prime to the next. Of the numbers up to 10 million, 1 in 15 are prime. (So, for example, there is a 1 in 15 chance that a seven-digit telephone number is a prime.) For N greater than 10,000, this last column seems to be just increasing by about 2.3 each time.

So every time Gauss multiplied by 10, he had to add about 2.3 to the ratio of the primes to all the numbers. This link between multiplication and addition is precisely the relationship embodied in a logarithm. Gauss, with his book of logarithms, would have found this connection staring him in the face.

The reason why the proportion of primes was increasing by 2.3 rather than 1 every time Gauss multiplied by 10 is because primes favour logarithms based not on powers of 10 but on powers of a different number. Pressing the ‘log’ button on your calculator when you input 100 produced the answer 2, which is the solution to the equation 10^x = 100. But there is nothing that says we have to have 10 as the number to raise to the power x. It is our obsession with our ten fingers which makes 10 so appealing. The choice of the number 10 is called the base of the logarithm. We can talk about the logarithm of a number to a base other than 10. For example, the logarithm of 128 to base 2 rather than base 10 requires us to solve a different puzzle, to find a number x so that 2^x = 128. If we had a ‘log to base 2’ button on our calculator, we could press it and get the answer 7, because we need to raise 2 to the power of 7 to get up to 128: 2⁷ = 128.

What Gauss discovered is that primes can be counted using logarithms to the base of a special number, called e, which to twelve decimal places is 2.718 281 828459 … (like π, it has an infinite decimal expansion with no repeating patterns), e turns out to be as important in mathematics as the number π, and occurs all over the mathematical world. This is why logarithms to the base e are called ‘natural’ logarithms.

The table that Gauss had made at the age of fifteen led him to the following guess. For the numbers from 1 to N roughly 1 out of every log(N) numbers will be prime (where log(N) denotes the logarithm of N to the base e). He could then estimate the number of primes from 1 to N as roughly N/log(N). Gauss was not claiming that this magically gave him an exact formula for the number of primes up to N – it just seemed to provide a very good ballpark estimate.

It was a similar philosophy that he would later apply in his rediscovery of Ceres. His astronomical method made a good prediction for a small region of space to look at, given the data that had been recorded. Gauss had taken the same approach for the primes. Generations had become obsessed with trying to predict the precise location of the next prime, with producing formulas that would generate prime numbers. By not getting hung up on the minutiae of which number was prime or not, Gauss had hit on some sort of pattern. By stepping back and asking the broader question of how many primes there are up to a million rather than precisely which numbers are prime, a strong regularity seemed to emerge.

Gauss had made an important psychological shift in looking at the primes. It was as if previous generations had listened to the music of the primes note by note, unable to hear the whole composition. By concentrating instead on counting how many primes there were as one counted higher, Gauss found a new way to hear the dominant theme.

Following Gauss, it has become customary to denote the number of primes we find in the numbers from 1 to N by the symbol π(N) (this is just a name for this count and has nothing to do with the number π). It is perhaps unfortunate that Gauss used a symbol that makes one think of circles and the number 3.1415 … Think of this instead as a new button on your calculator. You input a number N and press the π(N) button, and the calculator outputs the number of primes up to N. So, for example, π(100) = 25, the number of primes up to 100, and π(1,000) = 168.

Notice that you can still use this new ‘count primes’ button to identify precisely when you get a prime. If you input the number 100 and press this button, counting primes between 1 and 100, you get the answer 25. If you now input the number 101, the answer will go up by 1 to 26 primes, and this means that 101 is a new prime number. So whenever there is a difference between π(N) and π(N +1), you know that N + 1 must be a new prime.

To reveal quite how stunning Gauss’s pattern was, we can look at a graph of the function π(N) counting the number of primes from 1 to N. Here’s a graph of π(N) for numbers N from 1 to 100:

The prime number staircase – the graph counts the cumulative number of primes up to 100.

On this small scale the result is a jumpy staircase, where it is hard to predict how long one has to wait for the next step to appear. We are still seeing at this scale the minutiae of the primes, the individual notes.

Now step back and look at the same function where N is taken over a much wider range of numbers, say counting the primes up to 100,000.

The prime number staircase counting primes up to 100,000.

The individual steps themselves become insignificant and we end up seeing the overarching trend of this function creeping up. This was the big theme that Gauss had heard and could imitate using the logarithm function.

The revelation that the graph appears to climb so smoothly, even though the primes themselves are so unpredictable, is one of the most miraculous in mathematics and represents one of the high points in the story of the primes. On the back page of his book of logarithms, Gauss recorded the discovery of his formula for the number of primes up to N in terms of the logarithm function. Yet despite the importance of the discovery, Gauss told no one what he had found. The most the world heard of his revelation were the cryptic words, ‘You have no idea how much poetry there is in a table of logarithms.’

Why Gauss was so reticent about something so momentous is a mystery. It is true that he had only found early evidence of some connection between primes and the logarithm function. He knew that he had absolutely no explanation or proof of why these two things should have anything to do with each other. It wasn’t clear that this pattern might not suddenly disappear as you counted higher. Gauss’s reluctance to announce unproved results marked a turning point in mathematical history. Although the Greeks had introduced the idea of proof as an important component of the mathematical process, mathematicians before Gauss’s time were much more interested in scientific speculation about mathematics. If the mathematics worked, they weren’t too concerned about a rigorous justification of why it worked. Mathematics was still the tool of the other sciences.

Gauss broke from the past by stressing the value of proof. For him, presenting proofs was the primary goal of the mathematician, an ethos which has remained fundamental to this day. Without a proof of the connection between logarithms and primes, Gauss’s discovery was worthless to him. The freedom that the patronage of the Duke of Brunswick permitted him meant he could be quite choosy, almost indulgent about the mathematics he produced. His prime motivation was not fame and recognition but a personal understanding of the subject he loved. His seal bore the motto Pauca sed matura (‘Few but ripe’). Unless a result had reached full maturity it remained an entry in his diary or a doodle at the back of his table of logarithms.

For Gauss, mathematics was a private pursuit. He even encrypted entries in his diary using his own secret language. Some of them are easy to unravel. For example, on July 10, 1796, Gauss wrote Archimedes’ famous declaration ‘Eureka!’ followed by the equation

num = Δ + Δ + Δ

which represents his discovery that every number can be written as the sum of three numbers from the list of triangular numbers, 1, 3, 6, 10, 15, 21, 28, …, those numbers for which Gauss had produced his schoolroom formula. For example, 50 = 1 + 21 + 28. But other entries remain a complete mystery. No one has been able to unravel what Gauss meant when he wrote on October 11, 1796, ‘Vicimus GEGAN’. Some have blamed Gauss’s failure to disseminate his discoveries for holding back the development of mathematics by half a century. If he had bothered to explain half of what he had discovered and not been so cryptic in the explanations he did offer, mathematics might have advanced at a quicker pace.

Some people believe that Gauss kept his results to himself because the Paris Academy had rejected his great treatise on number theory, Disquisitiones Arithmeticae, as obscure and dense. Having been stung by rejection, to protect himself from any further humiliation he insisted that every last piece of the mathematical jigsaw be in place before he would consider publishing anything. Disquisitiones Arithmeticae did not receive immediate acclaim partly because Gauss continued to be cryptic even in the work he did expose to public view. He always claimed that mathematics was like a piece of architecture. An architect never leaves the scaffolding for people to see how the building was constructed. This was not a philosophy that helped mathematicians to penetrate Gauss’s mathematics.

But there were other reasons why Paris was not as receptive to Gauss’s ideas as he had hoped. By the end of the eighteenth century, mathematics in Paris was becoming ever more dedicated to serving the demands of an increasingly industrialised state. The Revolution of 1789 had shown Napoleon the need for a more centralised teaching of military engineering, and he responded by founding the École Polytechnique to further his war aims. ‘The advancement and perfection of mathematics are intimately connected with the prosperity of the State,’ Napoleon declared. French mathematics was dedicated to solving problems of ballistics and hydraulics. But despite this emphasis on the practical needs of the state, Paris still boasted some of the leading pure mathematicians in Europe.

One of the great authorities in Paris was Adrien-Marie Legendre, who was born twenty-five years before Gauss. Portraits of Legendre depict a rather puffed-up gentleman with a round, chubby face. In contrast to Gauss, Legendre came from a wealthy family but he had lost his fortune during the Revolution and been forced to rely instead on his mathematical talents for his livelihood. He too was interested in the primes and number theory, and in 1798, six years after Gauss’s childhood calculations, he announced his discovery of the experimental connection between primes and logarithms.

Although it would later be proved that Gauss had indeed beaten Legendre to the discovery, Legendre did nonetheless improve on the estimate for the number of primes up to N. Gauss had guessed that there were roughly N/log(N) primes up to N. Although this was close, it was found to gradually drift away from the true number of primes as N got larger and larger. Here is a comparison of Gauss’s childhood guess, shown as the lower plot, with the true number of primes, the upper plot:

A comparison between Gauss’s guess and the true number of primes.

This graph reveals that although Gauss was on to something, there still seemed to be room for improvement.

Legendre’s improvement was to replace the approximation N/log(N) by

thus introducing a small correction which had the effect of shifting Gauss’s curve up towards the true number of primes. As far as the values of these functions that were then within computational reach, it was impossible to distinguish the two graphs of π(N) and Legendre’s estimate. Legendre, steeped in the prevailing preoccupation with the practical application of mathematics, was much less reluctant to stick his neck out and make some prediction about the connection between primes and logarithms. He was not a man scared to circulate unproven ideas, or even proofs with gaps in them. In 1808 he published his guess at the number of primes in a book about 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 in the observatory he would continue to expand his table of primes. Gauss had heard the first big theme in the music of the primes. But it was one of his few students, Riemann, who would truly unleash the full force of the hidden harmonies that lay behind the cacophony of the primes.