Doing It With Twins: the Twin Prime Conjecture

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”

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.

University of New Hampshire

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.

Zhang Yitang CV

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.

Headlines about Twin Primes Conjecture

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…

Ancient Greece

… 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?

Natural numbers

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.

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.

6 times 4 rocks

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.

Factorisations 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.

13 rocks

13 rocks again

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.

13 rocks in a line

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

13 is prime, 24 is composite

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.

Small prime numbers

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.

Water

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:

Prime factorisation of 24

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?

Is this prime?

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.

Trial division

This is rather slow.

Too 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.

Sieve

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

Sieve
Sieve
Sieve

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

Sieve

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

Sieve

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

Sieve

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

Sieve

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.

Density of 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:

Are there are infinite number of primes?

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

Yup

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

Mathematical proof ahead

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.

Clever number

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!

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.

Twin primes

We could ask the question:

Are there an infinite number of twin primes?

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!

Lots of numbers

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.

Gap 2

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?

Gap 4
Gap 1000

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.

GPY

Their initials spelt out GPY, so that’s how the paper became popularly known. They showed that there are infinitely 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” .

GPY explained

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:

Hairs breadth

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.

That sentence impressed me so much

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 years passed

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.

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.

70 million

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.

70 million

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

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.

So, why should we care?

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:

G.H. Hardy

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.

Secure website

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.

Eratosthenes

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.

Prime

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

Quotation

Matt Mayer

Matt Mayer is a founder at ReignDesign. Matt is from the UK and was based in Shanghai for ten years. He is now living in Bangkok, Thailand.

6 comments

  1. 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!

  2. 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!!

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

Leave a Reply

Your email address will not be published. Required fields are marked *