Prime-time mathematics

PRIME-TIME MATHEMATICS

Professor Robin Wilson

Introduction

In each of my two lectures this term I’ll tell you how you can earn a million dollars – but you’ll have to work hard for your money to solve the two problems I’ll be describing. Today is the Riemann hypothesis, a problem relating to prime numbers, and on 9 March you’ll see the P = NP? problem, about algorithms and how hard certain problems are to solve.

So where do the million dollars come in? In May 2000 in Paris an event took place that had great importance for the world of mathematics. The Clay Mathematics Institute, set up in the US in 1998 with the mission ‘to increase and disseminate mathematical knowledge’, hosted a meeting called A celebration of the universality of mathematical thought. The central theme of this meeting was the announcement of seven so-called ‘millennium problems’, with a prize of one million dollars for the solution to each – seven million dollars in all – in order to celebrate mathematics in the new millennium.

The meeting was held in Paris because one hundred years earlier, at the Second International Congress of Mathematicians in Paris, David Hilbert – one of the world’s most distinguished mathematicians – delivered a historic lecture in which he posed 23 unsolved problems. This lecture set the mathematical agenda for the next hundred years. One of Hilbert’s problems was the Riemann hypothesis – the only one of the 23 that still remains unsolved.

So what are these seven millennium problems? They’re the problems considered by the mathematical community to be the most difficult and important in the subject – the ‘mountains of mathematics’, with the Riemann hypothesis as Mount Everest. They’re all highly technical and some are extremely difficult to describe, but very roughly they’re as follows:

•      the Riemann hypothesis (relating to prime numbers);

•      the P = NP? problem (on the efficiency of algorithms for solving problems);

•      the Poincaré conjecture (a geometrical problem in four-dimensional space) – this is the only one of the seven that may be nearing a solution;

•      the Navier-Stokes equation (a type of differential equation arising from the motion of fluids);

•      Yang-Mills theory (relating to a mathematical problem from quantum physics);

•      the Birch-Swinnerton-Dyer conjecture (another problem from number theory);

•      and finally the Hodge conjecture (a highly technical problem named after the Cambridge geometer and topologist William Hodge).

All these problems are extremely difficult and definitely not for the amateur. A general description of them appears in Keith Devlin ’s popular book The Millennium Problems: the Seven Greatest Unsolved Mathematical Puzzles of our Time – but even he almost gave up trying to describe the Hodge conjecture.

So what is the Riemann hypothesis? It was introduced by the German mathematician Bernhard Riemann, who died at the age of 40 while a professor at Göttingen University where he followed in the footsteps of Gauss and Dirichlet. On being elected a member of the Berlin Academy in 1859 Riemann was required to contribute to the Academy’s proceedings; the result was his only paper in number theory which has since been regarded as one of the classics of mathematics: ‘On the number of primes less than a given magnitude’.

As you can see, it’s about prime numbers, and in very general terms it asks: do all the solutions of a certain equation have a particular form? So the answer to this very hard problem is simply ‘yes’ or ‘no’; but we don’t know which. The full statement is: do all the non-trivial zeros of the zeta function have real part ½? But what does that mean? and what’s its connection with prime numbers?

The rest of my talk divides into two halves – first I’ll talk about prime numbers, and then I’ll attempt to link them with this statement, hopefully without going overboard on the technicalities, although it’s a highly technical subject.

Incidentally, if you want to read more, three best-selling books have recently appeared– the simplest is Karl Sabbagh’s DrRiemann’s zeros, the most popular is Marcus du Sautoy’s Magic of the primes, while the best mathematically is John Darbyshire’s Prime obsessions.

Prime numbers

So let’s start with prime numbers. A prime number is a number, larger than 1, whose only factors are itself and 1: so 13, 17 and 19 are prime numbers, while 15 (= 3 × 5) and 18 (= 2 × 2 × 3) are not. The primes up to 100 are:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97.

Prime numbers are central to mathematics because they form the building blocks for numbers – every whole number can be built up from them: they’re the ‘atoms’ or ‘fundamental particles’ of mathematics. So, for example,

60 = 2 × 2 × 3 × 5 and 100 = 2 × 2 × 5 × 5,

and more generally every whole number splits into primes in only one way, apart from the order in which we write down the factors. This, incidentally, is why we don’t choose to regard 1 as a prime number – because if we did, we could then split a number like 6 into primes in many different ways: 6 = 2 × 3 = 2 × 3 × 1 = 2 × 3 × 1 × 1, and so on. It’s much more convenient to disallow 1 as a prime.

The Greeks were fascinated by prime numbers – from the Pythagoreans onwards. In the 3rd century BC Eratosthenes, who’s also remembered for estimating the circumference of the Earth, introduced his ‘sieve’ for finding all primes up to a given number. So, for example, to find all the primes up to 100, we first list all the numbers and delete 1. We then leave 2, but sift out all its multiples. We do the same for 3, and 5, and 7. It seems as though this would all take a long time, but notice that the multiples of 11 have already been crossed out, as have all the multiples of higher primes. In fact, we don’t need to look at primes above 10, because if a number has a prime factor greater than 10, then it also has one less than 10 – and in general, we need only divide by primes up to the square root of the total number.

Before we continue, we should point out that we cannot write out a complete list of primes – they go on for ever. This was a celebrated result of Euclid, and appears in his Elements, Book IX, Proposition 20. It’s one of the most concise and attractive proofs in mathematics.

We argue by contradiction – assuming that the only primes are p 1, p 2, …, p n, and let us consider the number

N = (p 1 × p 2 × … × p n) + 1.

Then none of the primes p 1, p 2, …, p n divides exactly into N – so N must either be a prime not in the list, or be made up from primes not in the list. In either case, there is a prime number other than p 1, p 2,…, p n, and this gives us the required contradiction.

To see that both situations in the proof can arise, suppose first that the only primes known were 2, 3, 5 and 7 – then the number N would be (2 × 3 × 5 × 7) + 1, which is 211, a new prime. But if the only primes known were 2, 3, 5, 7, 11 and 13, then the number N would be 30,031, which is not a prime – it’s 59 × 509, but both of these are new primes.

Are there any general ways of generating primes? Many people have tried. In the 18th century, Leonhard Euler suggested the formula n 2 + n + 41, which yields primes for all n up to 39, but fails for n = 40 and obviously fails also for n = 41.

Pierre de Fermat also made a celebrated claim: that all numbers of the form (2 raised to the power 2 n) + 1 are prime. For example, taking n = 0, 1, 2, 3 and 4, we get 3, 5, 17, 257 and 65,537, which are all prime. Incidentally, as Gauss later observed, these numbers are interesting in geometry, since we can construct regular polygons with these numbers of sides using only straight-edge and compass: we learnt how to construct equilateral triangles at school, the Greeks showed how to construct pentagons, Gauss himself showed how to construct a 17-gon, and someone apparently once spent many years of their life describing a detailed construction for a regular 257-gon.

How about the next Fermat number F 5? This is (2 to the power 2 5) + 1, or 2 32 + 1, which is 4,274,967,297? Fermat didn’t have a computer to check this number, but a century later, Euler showed that it’s not prime – it has a prime factor of 641.

Sadly, Fermat’s conjecture has been proved wrong in spectacular fashion – no other Fermat number has ever been found that’s prime: F 6 = 2 64 + 1 has a factor of 274,177; F 9448 has a factor of 19 × 2 9450 + 1; and the largest known Fermat number, F 23,471 (a number with more than 10 7000 digits), has a factor of 5 × 2 23,473 + 1.

More successful for producing primes are the Mersenne primes, named after the 16th-century Minimite friar Marin Mersenne. These all have the form 2 n – 1: that’s one less than a power of 2. When n = 2, 3 and 5, we get the primes 3, 7 and 31, but when n = 4 or 6 we get non-primes. In fact, whenever the exponent n is not prime, the Mersenne number won’t be either – but is it true that whenever pis a prime, so then so is 2 p – 1?

As Mersenne himself noticed, this is true for many primes, but not for all – for example, taking p = 11, we get 2 11 – 1 = 2047, which is 23 × 89. Mersenne claimed that we get primes when p = 13, 17, 17, 19, 31, 67, 127 and 257 – he was wrong about 67 and 257, and he omitted 61, 89 and 107, but it was still a remarkable achievement for those days, especially given how large these numbers are.

Mersenne primes have received some notoriety in that all the recent records for the largest known prime have this form. In 2001, it was announced that the Mersenne number 2 13,466,917 – 1 (which is a 4-million-digit number) is prime, and I believe that this record has been recently broken by an even larger Mersenne prime.

The weirdest formulas for generating primes that I’ve come across are these. First, there’s a number x, which is about 1.3064, with the property that if you raise it to the powers 3, 9, 27, 81 (the powers of 3), and then drop the fractional bits, you always get a prime number.

And even more remarkable is this polynomial expression in no fewer than 26 variables a, b,…, z. As these variables range over all the positive integers, the expression yields both positive and negative numbers – and the positive ones are all prime – in fact, we get every single prime by this means.

Primes are things that were designed to be multiplied, and we get into real trouble if we try to add or subtract them: in fact, some of the most intriguing puzzles in mathematics arise in this way.

For example, if we add two primes other than 2 we always get an even number: 6 = 3 + 3, 10 = 7 + 3 (or 5 + 5), 20 = 13 + 7 (or 17 + 3), and so on. But can we get all even numbers in this way? The belief that we can is called the Goldbach conjecture, but no-one knows for sure. It’s been checked for all even numbers up to 4 trillion – but this isn’t good enough for mathematicians who need absolute proof, true in all cases. The best knowledge we have is a celebrated result of Chen Jin-run who proved in 1966 that every large enough even number is the sum of a prime and another number which has at most two prime factors.

We can also subtract primes – we won’t find two that are 1 apart (except for 2 and 3), since beyond 2 all primes are odd, but how about primes differing by 2? – twin primes, such as 3 and 5, 11 and 13, 41 and 43, 107 and 109 or 1,000,037 and 1,000,039.

Here are the pairs of twin primes up to 100 – and they’re not scarce: up to 10 11 there are 224 million such pairs. But, like the primes, do they go on for ever? No-one knows. So there’s another problem, easy to state yet no-one knows how to solve it.

So the belief is that, like buses, primes can come in pairs. But unlike buses they don’t come in threes – the only pair of triple primes – of the form n, n + 2, n + 4 – is 3, 5, 7; in any other triple of numbers like this, one of the numbers must have a factor of 3 and so can’t be prime.

We’ve seen that twin primes seem to occur forever, yet we can find arbitrarily large gaps between primes. For example, from 90 to 96 is a string of seven non-primes, and if we want a string of 99 non-primes, we consider the number 100!, which is 100 × 99 × … 2 × 1, and add 2 (giving a number divisible by 2), 3 (that’s divisible by 3), and so on, up to 100! + 100 which is divisible by 100.

This leads us to one of the main questions of this lecture – how are the primes distributed? They don’t seem to be well distributed, as we can see if we look at the numbers just below and just above 10 million. The hundred just below contain nine primes (that’s quite a lot), while the hundred just above contain just two.

In his inaugural lecture at the University of Bonn, the number-theorist Don Zagier said: There are two facts of which I hope to convince you so overwhelmingly that they will permanently be engraved in your hearts. The first is that the prime numbers belong to the most arbitrary objects studied by mathematicians: they grow like weeds, seeming to obey no other law than that of chance, and nobody can predict where the next one will sprout. The second fact is even more astonishing, for it states just the opposite: that the prime numbers exhibit stunning regularity, that there are laws governing their behaviour, and that they obey these laws with almost military precision.

To see what he meant by this, we’ll introduce the prime-counting function π(x), which counts the number of primes up to any number x – it’s nothing at all to do with the circle number π. So π(10) = 4, because there are exactly four primes (2, 3, 5, 7) up to 10; and π(20) = 8, because there are now a further four (11, 13, 17, 19). Continuing, we find that π(100) = 25; π(1000) = 168; π(10,000) = 1229; and so on. If we plot the values up to 100 on a graph we get a jagged pattern – each new prime creates a jump. But if we stand further away and plot the primes up to 100,000, we get a lovely smooth curve – the primes do indeed seem to increase very regularly.

We can describe this more precisely by comparing the values of x and π(x) as x increases. We get the following table which lists x, π(x) and their ratio x / π(x):

                 x                                             π( x)                                   x / π(x)                               

                10                                            4                                     2.5

                100                                          25                                   4.0

                1000                                        168                                  6.0

                10,000                                     1229                                 8.1

                100,000                                   9592                                 10.4

                1,000,000                                78,498                              12.7

                10,000,000                              664,579                             15.0

                100,000,000                            5,761,455                           17.4

                1,000,000,000                         50,847,534                         19.7

So up to 100 one-fourth of the numbers are prime, up to 1000 one-sixth of them are prime, and so on. They’re gradually thinning out. But can we express this more precisely?

Notice that whenever x is multiplied by a factor of 10, the ratio x/π(x) seems to increase by a constant amount, around 2.3. Now the mathematical device that turns multiplication into addition is the logarithm (co-discovered by Henry Briggs in Gresham College around 1615) and this number 2.3 is one that mathematicians recognise as the logarithm of 10. Indeed, we can summarise this phenomenon by saying that as x increases, π(x) behaves like x / log x, in the sense that the ratio between them approaches 1 as x gets larger and larger. This is a celebrated result in mathematics known as the prime number theorem. It was guessed at by the German mathematician Gauss when he was playing around with prime numbers at the age of 15 – but Riemann couldn’t prove it, and it wasn’t proved until after Riemann’s death. In 1896 the mathematicians Hadamard (from Belgium) and de la Vallée Poussin (from France) independently justified it, using sophisticated ideas from calculus.

Now, if we compare the graphs of π(x) and x / log x, they see that they agree fairly well, but the agreement isn’t perfect and various mathematicians have tried to improve on it. Legendre suggested introducing a fudge factor of about 1.08, so that π(x) behaves like x / (log x – 1.8), while Gauss proposed an excellent estimate which amounts to saying that the chance of a given number N being prime is about log N – so in order to test whether N is prime, roll a dice with log N sides. For those of you familiar with calculus, Gauss also recast his improved estimate for π(x) in terms of an integral, called the logarithmic integral, or li (x).

Getting down to series business

Let’s now leave prime numbers for a while and see how the Riemann hypothesis arises.

I’d first like to look at some series, where we add lots of terms together. The series

1 + ½ + ¼ + 1/ 8 + 1/ 16 + …

goes on for ever (that’s what the dots indicate), but they have an actual sum, which is 2. This means that if we add up the terms one by one, we get 1, then 1 1/ 2, then 1 3/ 4, then 1 7/ 8, and so on – indeed, by adding up enough terms we can get as close as we like to 2.

In the same way, the sum of

1 + 1/ 3 + 1/ 9 + 1/ 27 + …,

with each term one-third the previous one, is 1½. In fact, for any number p, the sum

1 + 1/ p + 1/p 2 + 1/p 3 + … = p / (p – 1).

Not all series can be summed. Here’s one that can’t:

1 + ½ + 1/ 3 + 1/ 4 + ….

It’s called the harmonic series, since the Greeks thought that it has links with the harmonic series of music. To see why it has no sum, we can bracket it as

1 + ½ + ( 1/ 3 + ¼) + ( 1/ 5 + 1/ 6 + 1/ 7 + 1/ 8) + ….

But this is greater than 1 + ½ + ½ + ½ + … which increases without limit, so the harmonic series doesn’t converge to any fixed number. And amazingly, even if we throw away most of the terms and leave only those that correspond to primes

1 + ½ + 1/ 3 + 1/ 5 + 1/ 7 + 1/ 11 + …,

then there is still no sum.

In the 18th-century one of the big challenges was to add up all the reciprocals of the squares – namely, to find the sum of the series:

1 + ¼ + 1/ 9 + 1/ 16 + 1/ 25 + ….

This was eventually solved by the Swiss mathematician Leonhard Euler, who found (by somewhat dubious means) that the sum is the number π 2/ 6, a remarkable result – why does π come in? In the same way, he found that the sum of the reciprocals of the fourth powers is π 4/ 90, for the sixth powers it’s π 6/ 945, and so on up to the 26th powers. He called the sum of the kth powers ζ(k), naming it the zeta function: so,

ζ(1) (the harmonic series)is not defined; ζ(2) = π 2/ 6; ζ(4) = π 2/ 90; and so on.

It turns out that, ζ(k) is defined for each number k larger than 1.

What have these series and the zeta function to do with prime numbers? Seemingly nothing – but Euler spotted a crucial link. It can be used to give another proof that there are infinitely many primes.

We can write the series for ζ(1) as follows:

1 + ½ + 1/ 3 + ¼ + … = (1 + ½ + ¼ + … ) × (1 + 1/ 3 + 1/ 9 + … ) × (1 + 1/ 5 + 1/ 25 + …) × …,

where each bracket involves the powers of just one prime. Summing the separate series gives

2/ (2 – 1) × 3/ (3 – 1) × 5/ (5 – 1) × … = 2 × 1½ × 1¼ × ….

Since ζ(1) is not defined, the right-hand side must go on for ever, and so there must be infinitely many primes.

Euler further extended these ideas to prove that, for any number k, larger than 1:

ζ(k) = 2 k/ (2 k–1) × 3 k/ (3 k–1) × 5 k/ (5 k–1) × 7 k/ (7 k–1) × ….

So Euler spotted an unexpected link between the zeta function, which involves adding reciprocals of powers of numbers and which seems to have nothing to do with primes, and a product that intimately involves the prime numbers. This was a stunning result and a major breakthrough.

The Riemann hypothesis

We’ve now set the scene for the Riemann hypothesis. As we’ve seen, the zeta function ζ(k) is defined for any number k larger than 1. But can we extend the definition to other numbers?

By way of analogy, we’ve seen that

1 + x + x 2 + x 3 + … is equal to 1 / (1 – x).

But the left-hand side makes sense only when x lies between –1 and 1, whereas the right-hand side makes sense for any x, apart from 1. So we can extend the formula on the left-hand side to all values of x (other than 1) by redefining it using the formula on the right-hand side.

In the same way, we can extend the definition of the zeta function to almost all of the complex plane. This consists of all symbols of the form a + bi, where a and b are the x- and y-coordinates and i represents the ‘square root of –1’. There’s nothing particularly mystical about this – all it means is that in calculations, whenever you come across i 2 you replace it by –1.

Using something called contour integration, we can extend our definition of the zeta function to the whole plane, apart from the point 1: this makes sense, since we know that ζ(k) is not defined when k = 1. When k is a number larger than 1, we get the same value as before – for example, ζ(2) = π 2/ 6. For all other values of k, including the complex ones (involving i, the square root of –1), we get a value of the zeta function.

We’ve seen how Gauss attempted to explain why the primes thin out, by proposing the estimate x / log x for the number of primes up to x. Riemann’s great achievement was to obtain an exact formula for the number of primes up to x, and his formula involved in a crucial way the so-called zerosof the zeta function – the solutions of the equation ζ(z) = 0.

It turns out that there are zeros of the zeta function at –2, –4, –6, –8, … (these are called the trivial zeros), and that all the other zeros (the non-trivial ones) lie within a vertical strip between 0 and 1 (the so-called critical strip), beginning at the following points:

½ ± 14.1i, ½ ± 21.01i, ½ ± 25.01i; ½ ± 30.4i; ….

But these all have the form ½ + (something times i). Do all the zeros in the critical strip have this form? Do they all lie on the central vertical line?

That’s the big question that we now call the Riemann hypothesis. We know that the zeros in the critical strip are symmetrically placed, both horizontally and vertically, and that as we progress vertically up and down the line, the first few zeros do lie on this central line ½. In fact, the first billion and a half zeros lie on this line. Moreover, the English mathematician G. H. Hardy proved that there are infinitely many zeros inside the critical strip, and in fact at least 40% of the zeros lie on the central line. But do they all lie on this line? Or are the first billion and a half just a coincidence?

It is generally believed that all the non-trivial zeros do lie on the central line. Indeed, the appearance of just one of these zeros off the central line would cause major havoc in number theory and throughout mathematics. But no-one has been able to prove it, even after a century and a half.

So you now know what the Riemann hypothesis states. If its statement seems an anti-climax after the big build-up, its consequences are substantial. In mathematics the truth of the Riemann hypothesis would give us much better results about prime numbers, with major consequences throughout mathematics. In modern cryptography, where factorising large numbers into their prime factors plays a crucial role in modern security systems (such as the internet and our bank accounts), a proof of the Riemann hypothesis would tell us that there is no fast algorithm for factoring a given large number – so our bank accounts would be safe.

I’d like to end with an unexpected development. The American number-theorist Hugh Montgomery was visiting the tea-room at Princeton and found himself sitting opposite the Nobel prize-winning physicist Freeman Dyson (incidentally, a former Cambridge pupil of Hardy). Montgomery had been exploring the spacings between the zeros in the critical strip, and Dyson said “But those are just the spacings between the energy levels of a quantum chaotic system.” If this analogy does indeed hold, as many think it does, then the Riemann hypothesis may well have consequences in quantum physics. And conversely, through their knowledge of these energy levels, quantum physicists rather than mathematicians may be the ones to prove the Riemann hypothesis. Now there’s an intriguing thought …

© Robin Wilson, Gresham College, 2 February 2005