Mind the gap

13/05/2003

Mathematicians are holding their breath. Can Dan Goldston and Cem Yalcin Yildrim repair the hole in their proof to make the biggest breakthrough in prime number theory for 80 years?

Goldston, of San Jose State University, and Cem Yalcin Yildrim, of Bogazici University, Istanbul, thought they had proved a result about the spacing of the prime numbers, which in turn could have led to a proof of the elusive Twin Prime conjecture. Their work, presented to colleagues in March, generated enormous excitement in the mathematical community. Unfortunately, on April 23, after closer examination, mathematicians spotted an error in the proof and now an effort is under way to resurrect their result.

Prime numbers are the fundamental building blocks of number theory, with every integer being expressed in exactly one way as a product of primes. Mathematicians have known there are infinitely many primes since Euclid's proof over 2,000 years ago, but they have struggled for centuries to understand how the primes are spread among the integers. Prime numbers become sparser as you look further up the number line, but they are also clumpy, sometimes bunching together in groups. Goldston and Yildrim may still have brought mathematicians much closer to proving the Twin Prime Conjecture, by using a new method to attack the question of just how bunched together the prime numbers can be.

The Twin Prime Conjecture states that there are infinitely many pairs of prime numbers which are separated by just two, like 3 and 5, and 29 and 31. "The Twin Prime Conjecture is one of those annoying unsolved problems in number theory: so simple and elegant to state, but a solution continues to evade the most complex methods and sharpest minds," said Brian Murphy, a number theorist involved in breaking the RSA-155 factoring challenge.

Imagine you are walking along the integers, one step per number, and you are interested in the distance between primes. If you are standing at a prime number p, then, as a consequence of the Prime Number Theorem, you will expect to walk ln p (the natural logarithm of p) steps on average before getting to the next prime number. But this is just on average, and sometimes you will have to walk much further, and sometimes much less far. If the Twin Prime Conjecture is true, then there are infinitely many primes such that the next one is just two steps away.

As a step towards proving the conjecture, mathematicians have been trying to find the smallest gap, in terms of this average spacing, that exists for infinitely many prime numbers. The best they had been able to do, after several incremental improvements, was to show that there were infinitely many pairs of primes that were separated by less than a quarter of the average gap.

Goldston and Yildrim thought they had easily broken this record, by showing that for any fraction, no matter how small, there are infinitely many consecutive pairs of primes within this fraction of the average distance of each other. But, deep within the proof, Andrew Granville of the Université de Montreal and K. Soundararajan of the University of Michigan found a problem. Some quantities, which were believed to be small error terms, are actually as big the values being calculated. Mathematicians are trying to correct the error, but so far the problem remains unresolved. However, many are confident that Goldston and Yildrim's approach will still break the current record of a quarter of the average gap.

Even if they had been able to prove their original result, they would not have proved the Twin Prime Conjecture. Their result would still have been in terms of the average distance ln p, which gets very large as p does, but it would have been the biggest step forward in this direction for 80 years. What is promising, error or no error, is the new approach Goldston and Yildrim used to prove their result.

Instead of just asking about the gap between two consecutive primes, they asked about the gaps between any number of consecutive primes. In 1977 Maier proved that the results concerning the largest distances between two consecutive primes could be proved for each of the gaps between any number of consecutive primes. According to the American Institute of Mathematics, Goldston and Yildrim would have, in a similar way, proved their result for any number of consecutive small gaps, at the same time as they demolished all previous records for one small gap.

Despite initial disappointment, Goldston and Yildrim's colleagues in number theory are still excited by their work, and are waiting to see what can be done with this approach. Can their proof be repaired to break the record for the smallest gaps between primes or, better still, to prove their original result? Could the Twin Prime Conjecture itself be next? And could their method be used to tackle the Riemann Hypothesis, one of the Clay Institute's seven Millennium Prize Problems, which is deeply connected to the distribution of prime numbers?

Whatever happens, Goldston and Yildrim have taken mathematicians further in their understanding of the prime numbers. "This is how science progresses, by having clever new ideas," Harold Boas, editor of Notices of the American Mathematical Society, told the San Jose Mercury. "The new idea is still there, and people are still trying to work out what the consequences are."