Just over two years ago, Plus reported on one of those times when the mathematical community held its breath (see Mind the gap in issue 25): Dan Goldston, of San José State University, USA, and Cem Yalcin Yildrim, of Bogazici University, Istanbul, had announced a major step towards a proof of the twin prime conjecture - only to be told by fellow mathematicians Andrew Granville and Kannan Soundararajan that their proof contained a flaw. Could the mistake be repaired? Were we back to square one? There was no easy fix for the problem and it was back to the blackboard for Goldston and Yildrim.

Now, two years later, it looks as though the two mathematicians can finally breathe a sigh of relief. Having joined forces with Janos Pintz of the Hungarian Academy of Sciences, they managed to re-prove their result, and, according to Granville, this time the proof seems to bear up under scrutiny.

The twin prime conjecture is one of those tantalising problems in number theory that are easy to state but fiendishly difficult to prove. It says that there are infinitely many pairs of primes - twin primes - whose difference is 2. The pairs $(3,5)$, $(5,7)$ and $(11,13)$ are examples. Mathematicians have known since the 18th century that prime numbers are more common among the smaller numbers, and get increasingly rare as you look at larger and larger numbers. Twin primes are even more rare than ordinary primes and finding them is no easy feat.

Nevertheless there is overwhelming evidence, most of it statistical, that there are infinitely many twin primes. In the 1920s, G. H. Hardy and J. E. Littlewood found what they believed was the probability distribution of twin prime numbers. This distribution says that the average number of twin primes less than a given number $n$ grows with $n$. So, if Hardy and Littlewood were correct - and most people believe that they were - then there are indeed infinitely many twin primes.

More support for the twin prime conjecture came in 1966 when Chen Jingrun proved that there are infinitely many pairs of numbers $(p,q)$ with $p$ prime and $q$ either prime or a product of two primes. Even though this seems promisingly close to a proof of the twin prime conjecture, there is a major problem: there is no way of checking which of the infinitely many $q$'s are in fact prime. To date, the only way of checking how many of them are prime, is to look at them one by one, which is of course impossible in a finite amount of time. This decision problem, referred to as the "parity problem", turns up in various areas of mathematics and is responsible for many a mathematician's headache.

Goldston, Pintz and Yildrim attacked the problem from a different angle. Rather than considering the primes themselves they looked at the gaps between them. By the prime number theorem, we know that, on average, the gap between a prime $p$ and the next prime along is $ln(p)$ (the natural logarithm of $p$). This is only an average - in reality, particular consecutive primes can be very far apart or very close together. Building on Hardy and Littlewood's work, Goldston, Pintz and Yildrim set out to compare the actual length of the gaps with the average length. Their result states that given any fraction, no matter how small - 1/1,000, say -, there is a pair of consecutive primes $(p,q)$ (probably very large) so that the actual gap $q - p$ is less than that fraction times the average gap $ln(p)$, so less than $1/1,000 \times ln(p)$ in our example.

Their result does not, however, show that there are infinitely many primes which are a definite distance apart, be it 2 (as conjectured), 20 or 20,000. Since the size $ln(p)$ of the average gap grows with $p$, the actual gap might grow as well. In our example, $ln(p)$ might be 100,000, so that $1,000 \times ln(p) = 100$ is still large.

Even though this might seem miles away from a full proof of the twin prime conjecture, the result represents a major breakthrough. Brian Conrey, the Executive Director of the American Institute of Mathematics said: "Goldston, Pintz, and Yildrim have discovered a remarkable new proof in prime number theory. By amazingly elementary techniques they have found one of the deepest insights into the mysterious behavior of the primes ... we have every confidence that indeed a real gem has been unearthed."

As often happens in mathematics, the methods used, rather than the theorem itself, pave the way for the future. Goldston, Pintz and Yildrim's methods are surprisingly simple. Their approach is based on what is known to experts as a "Selberg sieve". Sieves have been used in prime number theory since ancient times. The basic idea is that in order to find a certain set of numbers, for example primes or twin primes, you starts with a larger set and methodically eliminate unwanted numbers, until a smaller set of candidate numbers is left in the sieve. The simplest and most famous sieve is that named after Eratosthenes, which finds all primes less than a given number.

Andrew Granville, who found the flaw in the first proof, said in an email to the Mathematical Association of America:" ... there is no obvious reason that the method cannot be modified to prove the twin prime conjecture. It is an exciting breakthrough and seems to open the gates for many other developments."

The short paper entitled "Small Gaps between Primes Exist" was published on the Mathematics arXiv on the 14th of May 2005.

Further Reading

• Plus explored the twin prime conjecture in Mathematical mysteries: twin primes.
• Read the Mathematical Association of America's news article on the advance on the twin prime conjecture.
• Wikipedia has an entry on the twin prime conjecture.
• The homepage of the mathematician Chris Caldwell features just about everything you could want to know about primes.
• Check out the Largest known primes website to see the largest twin primes found so far.
• The mathematician Jill Britton has made a Java applet illustrating the sieve of Eratosthenes.