“MATHEMATICS, more than any other art or science, is a young man’s game,” mused Godfrey Harold Hardy ruefully, in his 1940 memoir A Mathematician’s Apology. As if to prove him right, two mathematicians in their twenties have now solved a famous problem that Hardy himself struggled with.
Hardy’s great love was number theory, and one thing number theorists have always wanted to understand is the distribution of prime numbers – those whose only divisors are 1 and themselves. They seem to pop up randomly in the sequence of numbers, and yet paradoxically they also show hints of patterns. One type of pattern is called an arithmetic progression: start at any prime number, such as 5, and advance in constant jumps of, say, 12. In this case, the first five numbers of the progression are all prime: 5, 17, 29, 41, 53. However, the next number in the sequence is the non-prime 65, which is 5 × 13.
How many consecutive prime terms can an arithmetic progression have before hitting a non-prime? Hardy believed that there was no upper limit. With his long-time collaborator, John Littlewood, he published a very specific guess about the frequency of prime runs of length k, for any number k. But until this year, mathematicians had taken only small steps towards proving Hardy right. In 1939, Johannes van der Corput proved that there are infinitely many arithmetic progressions of primes containing only three numbers, known as three-term progressions. But the longest known is a 22-term sequence, beginning at 11,410,337,850,553 and proceeding in steps of 4,609,098,694,200.
Advertisement
Now Ben Green of the University of British Columbia and Terence Tao of the University of California at Los Angeles have announced a proof that prime progressions of any length exist. They cannot yet prove Hardy’s frequency estimate, but they do know that it is in the right ballpark.
Green says they initially set out only to improve slightly upon van der Corput’s result by showing that there are infinitely many four-term progressions. But once they had proved this result, they realised their methods were more general. “It was just one of those things where one idea leads to another,” says Green.
If primes occurred truly at random, the process of determining whether a number is prime or not could be compared with flipping a coin weighted in favour of non-primes, where primes are heads. In 1975 Endre Szemerédi proved that any set of integers selected in this way would contain progressions of all lengths. Unfortunately, in this model, the primes behave as if the coin becomes more heavily weighted toward tails the more you flip it, so Szemerédi’s theorem fell short of proving Hardy’s belief.
Tao and Green overcame this problem with an ingenious two-step approach. First they found a set of “almost-primes” (which includes primes, but also numbers with fewer than a specified number of divisors) that contained progressions of any length. Next, they showed that within this set there are always enough primes to ensure that the probability of “heads” stays above a finite value. That means the set will contain an arithmetic progression of any length made up of primes.