The Grub & Groove pub in Shanghai hosts a series of talks on Tuesday evenings called The Thinkery. Under the slogan of ‘everything is interesting’, they invite people to give a talk on the topic of their choice. Recently I gave a talk entitled **“Doing It With Twins: The Twin Primes Conjecture”**

Now, I want you to imagine for a moment that you live in the United States, to be exact: New Hampshire. You’re a recruiter at the University of New Hampshire and your job is to hire the best people to become professors and lecturers.

Now suppose one day you get an application from this guy, Zhang Yitang, a 50-something mathematician. Since getting his PhD from Purdue, he’s struggled to find an academic job, working as a motel clerk and a Subway sandwich maker. I wouldn’t blame you if you passed over him.

It turns out if you had skipped Zhang Yitang, you’d have been making a big mistake, because a few weeks ago this 57-year old Chinese mathematician made headlines around the world when he proved a result in number theory which has been challenging mathematicians for years.

For the rest of this talk I’m going to try to give you some context to understand what exactly Zhang Yitang proved. To do that, I’ll have to go back in time a little. In fact, back in time a lot…

… to Ancient Greece. Now, the Ancient Greeks were very interested in numbers, much like other ancient civilisations: the Babylonians, Chinese and Egyptians. What are the numbers which all ancient civilisations would study first?

These of course! The **natural** or **whole** or **counting** numbers. We call them counting numbers because we can use them to count things: and that’s something that’s useful for any civilisation, whether you’re counting sheep, or people, or rocks.

So, suppose I’m an Ancient Greek, and my master has given me a pile of 24 rocks.

My job is to organise these rocks neatly. So I organise them like this, into 6 columns of 4 rows making a nice rectangle.

If I multiply 6 and 4, of course I get 24. We call 6 and 4 **factors** of 24. Turns out there are other ways I could arrange my rocks, like 8 rows of 3 rocks. These are all factors of 24.

How about if I was given 13 rocks, and told to organise them into a rectangle. However I try to do it, there’s always some rocks sticking out the side.

In fact, the only way I can make my 13 rocks into a rectangle is to make a long thin line of 13 columns by 1 row: we could say that the only factors of 13 are itself (13) and 1.

The Ancient Greeks realised there was something inherently different about numbers like 24, and numbers like 13. Different things need different words.

We call numbers like 13 which only have two factors (themselves and 1) prime. All other numbers, like 24, are composite.

Let’s take a look at the small prime numbers, coloured here in red.

Why are mathematicians interested in prime numbers? One reason is that prime numbers can be thought of as the “atoms” which make up other counting numbers.

Just as water has two hydrogen atoms and one oxygen atom making up each H₂O molecule, it turns out all natural numbers can be made from prime numbers. How?

You remember earlier I showed you several factorisations of 24, like 6 × 4, 8 × 3, and 24 × 1. However, there’s only one way to make 24 by multiplying together prime numbers:

Here, “2”, and “2”, and “2”, and “3” can be thought of as “atoms” making up the number 24. Every counting number can be made by multiplying together prime factors in exactly one way - that’s called unique prime factorisation.

That’s one of the reasons we generally say that 1 isn’t prime. Why do we say that a prime must have two factors, itself and 1? Because if we allowed 1 as a prime, we’d lose this nice uniqueness property: 24 could be made from 2 × 2 × 2 × 3 × 1 or 2 × 2 × 2 × 3 × 1 × 1.

So, how do we figure out if a number is prime, say 1284741?

One simple way is trial division. First we try dividing the number by 2, and seeing if it divides exactly. Then we try dividing by 3. Then 5 (we can skip 4, as if the number was divisible by 4, it would also be divisible by 2). We continue dividing by each prime in turn.

This is rather slow.

A Greek named Eratosthenes, who you see above, devised a faster way of quickly finding all the prime numbers in a range. His method was called the Sieve of Eratosthenes. Let’s see how that works:

First start with a grid of numbers.

Take the first prime number, that’s 2. Now start colouring in all the multiples of 2, the 2-times table.

When you’ve finished, the grid looks like this.

The next white number is prime: that’s 3. Now colour in all of 3’s multiples - the 3-times table.

The next white number is prime, that’s 5. Now colour in all of 5’s multiples.

Keep going, colouring in the multiples of the primes. The white numbers left uncoloured are the primes.

So, you can see there are quite a lot of small primes. In the first 100 numbers, there are 25 primes. But as we go higher up the number line, there are fewer primes. From 1000 to 1100, there are only 16 primes. What if we take a much bigger number: the population of China is about 1.3 billion. The next 100 numbers after that only have 5 primes.

So, if the primes are getting rarer and rarer, maybe they run out completely? Do we get to a point where there are no more primes? Or, can we always find more primes? The Greeks asked this question:

And, the Greeks were also able to answer this question:

This is Euclid, a famous Greek mathematician. He was able to prove that yes - there are an infinite number of primes. How?

Let’s assume that the answer is no: there are only a **finite** number of primes. That means we could write them down:

2, 3, 5, 7, …, B

where B is the biggest prime.

Now I’m going to write down a clever number, by multiplying together all the prime numbers: 2 times 3 times 5 times …. all the way up to B. Then add 1.

Now, let’s think about this number. Is it **prime**, or **composite**?

If it’s **prime** then, hey! Looks like we just found a prime number that’s not on our list. It’s clearly much bigger than B. That can’t be right!

If it’s **composite**… we know 2 × 3 × 5 × … × B is divisible by 2, and also by 3, and also by 5, and in fact by all the prime numbers. If we add 1 to make the red number, it isn’t divisible by **any** of the primes. But remember every number can be made by multiplying together a unique set of prime factors. The red number has no prime factors? That can’t be right!

We seem to have boxed ourselves into a corner. What’s gone wrong? The only thing that can have happened is that our original assumption “there are only a finite number of primes” is **wrong**. In fact, there are an infinite number of primes!

As promised, on to the twins!

Twin primes are simply two primes which are close together: just two apart. Like 3 and 5, or 41 and 43. Both of the pair are prime.

We could ask the question:

This is the twin prime conjecture.

And it turns out it’s a much, much harder question to answer than “are there an infinite number of primes?”. One which the Greeks weren’t able to answer. One which has been troubling mathematicians right up to the present day.

Now, we have one advantage over the Ancient Greeks: computers. We can use computers to search for large twin primes. The numbers in the largest known twin prime each have over 200700 digits. If I printed them out on A4 paper, each number would take up 50 sheets. And the only difference would be on the last digit of the final page of each printout!

Twin primes interest mathematicians because they say something about the size of the gaps between the primes. Even as the primes in general get further and further apart, we still might expect to be able to find pairs of primes very close together.

If it’s hard to prove the twin prime conjecture, maybe we could relax the condition a little. Rather than looking for primes 2 apart, can we find infinite pairs of primes which are no more than 4 apart? Or even, pairs of primes which are no more than 1000 apart?

Actually, **no**, mathematicians hadn’t been able to prove this result for any size of gap.

Some big progress was finally made in 2005 with the publication of a paper by these three men: Daniel Goldston of the University of San Jose; János Pintz from Budapest; and Cem Yıldırım from Istanbul.

Their initials spelt out GPY, so that’s how the paper became popularly known. They showed that there are inﬁnitely many primes where the gap

to the next prime is as small as we want compared to the average gap between

primes. That’s not the twin prime conjecture, but it’s a step in the right direction.

Now their techniques use some pretty deep mathematics, but in general their strategy actually used a similar technique to the Sieve of Eratosthenes. They combined a sieving technique to find primes, together with a function, which has a parameter called a “level of distribution” .

Now Goldston, Pintz and Yıldırım were able to devise a function with a level of distribution of 0.5, but it turns out that you need a function with a level of distribution above 0.5 to prove the twin prime conjecture. Any amount would do: 0.5000001 would do.

In their paper, GPY wrote that they:

Back to our hero Zhang Yitang. In 2008 he read a copy of GPY, and read about how close the researchers seemed to be to the twin primes conjecture.

So, without consulting with G, P or Y, or anyone else in the field, Zhang Yitang set to work, trying to improve on the GPY result.

3 long years passed. Many mathematicians across the world were also trying to improve on the GPY result, trying out different functions, and better and better sieves in an attempt to increase the level of distribution. But 0.5 seemed be be an impossible barrier to overcome.

Last year, Zhang Yitang took a break and visited a friend in Colorado. While at a barbecue, he had a brainwave. What if instead he used a **worse** sieve.

The new sieve skipped some numbers with large prime factors. It was a counter-intuitive thing to do, but it actually provided Zhang Yitang with the flexibility to make his argument work.

Zhang Yitang wrote up his results and submitted to the *Annals of Mathematics*, a mathematical journal. The editors were surprised to receive the manuscript out of the blue, from an unknown mathematician, but the maths checked out and it was published.

So what exactly did Zhang Yitang manage to prove? Not the twin prime conjecture. He did prove that there are an infinite number of pairs of prime numbers no more than 70 million apart.

Now, you might be thinking: that doesn’t seem so impressive, 70 million is a pretty huge number. But, to mathematicians it’s actually a pretty small number! The gap between 70 million and 2 is a lot less than the gap between infinity and 70 million.

And already other mathematicians have managed to improve on this bound, getting the limit down to 4 million.

There’s hope that refining the arguments in Zhang Yitang’s paper could get the bound down to 16. And this, or other techniques may some day let us reach the goal of proving it for gaps of 2.

Number theory can seem very arcane, not very relevant or useful. There are two schools of thought. Many pure mathematicians indeed revel in the “uselessness” of the results. A famous British mathematician, G.H. Hardy, once said:

And yet, much to G.H. Hardy’s chagrin, it turns out pure mathematics does have uses. If you’ve ever used a secure website, that’s one starting https://, for something like online banking or online shopping, you were actually using a cryptography system called RSA.

RSA relies on facts about prime numbers. In fact, it relies on the fact that factorizing numbers is hard, even for computers. There are no significantly faster ways of finding factors today than the sieving techniques that Eratosthenes used.

Secure communication online wouldn’t have been possible without this knowledge.

But even if it turns out that some of this knowledge doesn’t have “real world” applications, I believe that it is important to explore these concepts. Because they are truly **universal**. Even an alien living in another galaxy, maybe with a different number of fingers on each hand, maybe completely unimaginable to us: if he has this many objects, he won’t be able to arrange them in a rectangle.

I’ll leave you with a quote from Zhang Yitang, shortly after his proof.

this is cool I love it thank you

Best intro about Zhang YiTang’s paper!

This post is really good!! It explains hard things in a easier way to make me (a math layman) understand!! Thank you the author of this post!

This is most excellent, Matt. I do believe, however, that your presentation contains one misstatement: “There are no significantly faster ways of finding factors today than the sieving techniques that Eratosthenes used.” The Prime Spiral Sieve (aka Croft Spiral Sieve) has been benchmarked against the Sieve of Eratosthenes using an M.I.T. approved Python algorithm (pyprimes 0.1.1a). In a 420 second test the Prime Spiral Sieve proved to be faster than the Sieve of Eratosthenes. The Prime Spiral Sieve generated 12856761 primes or 29944 per second compared to the Sieve of Eratosthenes generating 9380437 primes or 22334 per second. I believe this qualifies as ‘significant,’ especially with regard to very large numbers. The results of the benchmarking test can be found here: https://mail.python.org/pipermail/tutor/2011-December/087209.html … Thank you!!

Thanks Gary! I guess by ‘significantly faster’ I was really meaning ‘orders of magnitude faster’. Interesting read anyway, thanks!