# Prime Gap Grows After Decades-Long Lull

Photo illustration by Olena Shmahalo / Quanta Magazine; original courtesy of Terence Tao

Paul Erdős, left, and Terence Tao discussing math in 1985. This past August, Tao and four other mathematicians proved an old Erdős conjecture, marking the first major advance in 76 years in understanding how far apart prime numbers can be.

21

In May 2013, the mathematician Yitang Zhang launched what has proven to be a banner year and a half for the study of prime numbers, those numbers that aren’t divisible by any smaller number except 1. Zhang, of the University of New Hampshire, showed for the first time that even though primes get increasingly rare as you go further out along the number line, you will never stop finding pairs of primes that are a bounded distance apart — within 70 million, he proved. Dozens of mathematicians then put their heads together to improve on Zhang’s 70 million bound, bringing it down to 246 — within striking range of the celebrated twin primes conjecture, which posits that there are infinitely many pairs of primes that differ by only 2.

Now, mathematicians have made the first substantial progress in 76 years on the reverse question: How far apart can consecutive primes be? The average spacing between primes approaches infinity as you travel up the number line, but in any finite list of numbers, the biggest prime gap could be much larger than the average. No one has been able to establish how large these gaps can be.

Olena Shmahalo / Quanta Magazine

“It’s a very obvious question, one of the first you might ever ask about primes,” said Andrew Granville, a number theorist at the University of Montreal. “But the answer has been more or less stuck for almost 80 years.”

This past August, two different groups of mathematicians released papers proving a long-standing conjecture by the mathematician Paul Erdős about how large prime gaps can get. The two teams have joined forces to strengthen their result on the spacing of primes still further, and expect to release a new paper later this month.

Erdős, who was one of the most prolific mathematicians of the 20th century, came up with hundreds of mathematics problems over his lifetime, and had a penchant for offering cash prizes for their solutions. Though these prizes were typically just $25, Erdős (“somewhat rashly,” as he later wrote) offered a$10,000 prize for the solution to his prime gaps conjecture — by far the largest prize he ever offered.

Erdős’ conjecture is based on a bizarre-looking bound for large prime gaps devised in 1938 by the Scottish mathematician Robert Alexander Rankin. For big enough numbers X, Rankin showed, the largest prime gap below X is at least

$${Large frac{1}{3} frac{log X loglog Xloglogloglog X}{(logloglog X)^2}}$$
Number theory formulas are notorious for having many “logs” (short for the natural logarithm), said Terence Tao of the University of California, Los Angeles, who wrote one of the two new papers along with Kevin Ford of the University of Illinois, Urbana-Champaign, Ben Green of the University of Oxford and Sergei Konyagin of the Steklov Mathematical Institute in Moscow. In fact, number theorists have a favorite joke, Tao said: What does a drowning number theorist say? “Log log log log … ”

UCLA

Terence Tao of the University of California, Los Angeles, said this is the first Erdős prize problem he has been able to solve.

Nevertheless, Rankin’s result is “a ridiculous formula, that you would never expect to show up naturally,” Tao said. “Everyone thought it would be improved on quickly, because it’s just so weird.” But Rankin’s formula resisted all but the most minor improvements for more than seven decades.

Many mathematicians believe that the true size of large prime gaps is probably considerably larger — more on the order of (log X)2, an idea first put forth by the Swedish mathematician Harald Cramér in 1936. Gaps of size (log X)2 are what would occur if the prime numbers behaved like a collection of random numbers, which in many respects they appear to do. But no one can come close to proving Cramér’s conjecture, Tao said. “We just don’t understand prime numbers very well.”

Erdős made a more modest conjecture: It should be possible, he said, to replace the 1/3 in Rankin’s formula by as large a number as you like, provided you go out far enough along the number line. That would mean that prime gaps can get much larger than in Rankin’s formula, though still smaller than in Cramér’s.

The two new proofs of Erdős’ conjecture are both based on a simple way to construct large prime gaps. A large prime gap is the same thing as a long list of non-prime, or “composite,” numbers between two prime numbers. Here’s one easy way to construct a list of, say, 100 composite numbers in a row: Start with the numbers 2, 3, 4, … , 101, and add to each of these the number 101 factorial (the product of the first 101 numbers, written 101!). The list then becomes 101! + 2, 101! + 3, 101! + 4, … , 101! + 101. Since 101! is divisible by all the numbers from 2 to 101, each of the numbers in the new list is composite: 101! + 2 is divisible by 2, 101! + 3 is divisible by 3, and so on. “All the proofs about large prime gaps use only slight variations on this high school construction,” said James Maynard of Oxford, who wrote the second of the two papers.

The composite numbers in the above list are enormous, since 101! has 160 digits. To improve on Rankin’s formula, mathematicians had to show that lists of composite numbers appear much earlier in the number line — that it’s possible to add a much smaller number to a list such as 2, 3, … , 101 and again get only composite numbers. Both teams did this by exploiting recent results — different ones in each case — about patterns in the spacing of prime numbers. In a nice twist, Maynard’s paper used tools that he developed last year to understand small gaps between primes.

The five researchers have now joined together to refine their new bound, and plan to release a preprint within a week or two which, Tao feels, pushes Rankin’s basic method as far as possible using currently available techniques.

The new work has no immediate applications, although understanding large prime gaps could ultimately have implications for cryptography algorithms. If there turn out to be longer prime-free stretches of numbers than even Cramér’s conjecture predicts, that could, in principle, spell trouble for cryptography algorithms that depend on finding large prime numbers, Maynard said. “If they got unlucky and started testing for primes at the beginning of a huge gap, the algorithm would take a very long time to run.”

Eleanor Grant

James Maynard of the University of Oxford wrote the second paper proving Erdős’ conjecture on large prime gaps.

Tao has a more personal motivation for studying prime gaps. “After a while, these things taunt you,” he said. “You’re supposed to be an expert on prime numbers, but there are these basic questions you can’t answer, even though people have thought about them for centuries.”

Erdős died in 1996, but Ronald Graham, a mathematician at the University of California, San Diego, who collaborated extensively with Erdős, has offered to make good on the \$10,000 prize. Tao is toying with the idea of creating a new prize for anyone who makes a big enough improvement on the latest result, he said.

In 1985, Tao, then a 10-year-old prodigy, met Erdős at a math event. “He treated me as an equal,” recalled Tao, who in 2006 won a Fields Medal, widely seen as the highest honor in mathematics. “He talked very serious mathematics to me.” This is the first Erdős prize problem Tao has been able to solve, he said. “So that’s kind of cool.”

The recent progress in understanding both small and large prime gaps has spawned a generation of number theorists who feel that anything is possible, Granville said. “Back when I was growing up mathematically, we thought there were these eternal questions that we wouldn’t see answered until another era,” he said. “But I think attitudes have changed in the last year or two. There are a lot of young people who are much more ambitious than in the past, because they’ve seen that you can make massive breakthroughs.”

• Michael Hardy says:

Someone needs to work on LaTeX or MathJax skills. If you write \frac{\log X \log\log X\log\log\log\log X}{(\log\log\log X)^2}, then “log” will appear un-italicized and there will be proper spacing between each “log” and whatever precedes and follows it.

• @Michael: Thanks for the LaTeX tip. As you can tell, we’re quite rusty!

• Lyubo says:

Just a small correction log is not shot for natural logarithm, “ln” is. And log is for logarithm basis 10 .

• Erica Klarreich says:

@Lyubo: Thanks so much for your comment. You’re quite right, among physicists and engineers “ln” is the notation commonly used for the natural logarithm, and that’s what is typically taught in school. Among mathematicians, however, it’s more common to use “log” to denote the natural logarithm, and “log_10” to denote the logarithm base 10. So I used the latter convention, which is also what the authors used in their two papers.

• gustavo sarmiento says:

Every single article published here on no !matter what subject always ends with something like “that anything is possible”.
In hererer words all the time you spent reading was wasted.
Please put your “that anything is possible,” at the beginning so we don’t waste our time

• Tomguglielmo says:

Wonderful article, Erica, and beautifully written. Thank you!
One more point: I can not understand why some of us comment on trivia and not on the importance of this major result.

• @Erica: In the standard university calculus sequence, ln is still very much the notation of choice. For instance, the most successful [so I’ve been told] calculus textbook, by James Stewart, uses ln. It has the following marginal note:

“Most textbooks in calculus and the sciences, as well as calculators, use the notation ln x for the natural logarithm and log x for the “common logarithm,” log_10 x. In the more advanced mathematical and scientific literature and in computer languages, however, the notation log x usually denotes the natural logarithm.” [Calculus, 5th edition, page 64]

I do not know where the “advanced mathematical and scientific literature” begins. In our undergraduate real analysis course, our textbook uses ln, introducing it as log_e after having defined e using infinite sequences.

Peter Nyikos
Professor, Dept. of Mathematics
University of South Carolina
http://people.math.sc.edu/nyikos/
nyikos @ math.sc.edu

• john o says:

On your easy way to construct a list of composite numbers, it would be better to use the product of only the prime numbers that will still give the same length string of composites but will do so at a much reduce starting number. For example the pruduct of all the primes below 101 is only a 38 digit number not 160 like 101 factorial.

• Carey says:

This is probably the first time in years I’ve bothered to write in the comments section of anything in the webosphere, but many of these comments are so annoyingly and pointlessly pedantic.

Erica, thank you for the article. I’ve been out of the game for years but understood exactly the log-convention you are referring to despite the etymology of notation being non-central to the article.

Things have gotten so specialized or abstruse – perhaps more so in fundamental physics – that it is really nice to hear about progress on old romantic problems or highly abstract / generalized problems.

• Erica Klarreich says:

@john o: You’re quite right, and thanks for your comment. I chose to explain things in terms of factorials because I thought that would be easier to understand, but you’re correct that you could instead use the product of all the primes less than 101, to get a list of composite numbers at a smaller starting place. That modification to the argument isn’t enough to improve on Rankin’s formula, however; to achieve that, the mathematicians involved had to figure out how to produce lists of composite numbers even earlier in the number line.

• Lelio says:

Primorial is the word we use to refer to the product of all primes up to a limit, and n# is the notation, so the product of all the primes less/equal to 101 can be written as 101#

• John H says:

@Peter N, Erica,etc
I am not a mathematician (or engineer), but as I have noticed in many areas: The wonderful thing about standards is that there are so many to choose from!

• Tom Anderson says:

“prime numbers, those numbers that aren’t divisible by any smaller number except 1”

This is a poor definition because negative numbers are numbers. Thus, if we ask “is 2 divisible by -2” (http://www.wolframalpha.com/input/?i=Divisible%5B2%2C+-2%5D) we get the result “True” because 2 divided by -2 = -1 which is an integer. Wikipedia says, “Divisors can be negative as well as positive, although sometimes the term is restricted to positive divisors.” (http://en.wikipedia.org/wiki/Divisor)

Sometimes the definition of “divisible by” is restricted to whole numbers (positive integers). If this was a standard definition that is being used, it would be a sufficient definition.

Also, why bother with the term “smaller than”? No number is divisible by a number that is bigger than itself.

Therefore, I believe it would be better to say something like:

“prime numbers, those counting numbers that are only divisible by 1 or themselves”

• Jared says:

@Tom Are we correcting a proof here? Hahaha

• Douglas J. Bender says:

I have a new class of mathematical numbers I’d like to propose and define. That is, all those composite numbers less than a given prime number. I call these the “sub-prime numbers”. Very handy in calculating mortgage loans.

• Douglas J. Bender says:

Actually, calculating the average of all the “sub-prime numbers” for a given prime might be interesting and helpful (or not). And the same might (or might not) be so for another class of mathematical numbers I’d also like to propose and define: The “sub-prime prime numbers”; which would be, of course, just the primes less than a given prime. It might be interesting and helpful (or not) to find their averages. What happens as the given prime gets larger and larger, and so on? But maybe I should just get to sleep now, before I get myself in trouble.

(My original comment was just a joke, attempting to use “sub-prime” in a new and nonsense [sort of] way.)

• Sid Hollander says:

“prime numbers, those counting numbers that are only divisible by 1 or themselves”

would that make ‘1’ a prime (exclusively)?

• Edward Fung says:

Professor Zhang in April 2013 has proved that there are infinite pairs of consecutive primes with a gap N as long as N < 70 million (now proved to be N < 300). So if I have chosen gap N = 4, then one pair of consecutive primes is 13 and 17, and another pair is 19 and 23. Is Professor Zhang proof saying that there are infinite pairs of consecutive primes that has gap N=4, in additon to the two pairs I shown here ? If yes, does it also means that there are infinite pairs of consecutive primes with gap N=2. If yes, does it mean the Twin Prime conjecture is proven ?

• Edward Fung says:

I think I found the answer to my question. No, Professor Zhang’s 2013 proof does not prove the Twin Prime conjecture which said there are infinitive pairs of twin primes.

Instead, the proof said that there are infinite pairs of consecutive primes that have a gap 70 millions, then there may only be a limited supply in the infinite number system. There may be a lot but will not be unlimit supply. But if you want to find a pair of consecutive prime with gap N< 70 millions (which Terrence Tao's group narrow it down to gap N < 300), there are infinitive number of pairs. Now if someone can narrow the gap N<3, then the Twin Prime conjecture will be proven.

• Jeff Skates says:

Given that Qanta moderates comments perhaps Qanta can categorize all comments, so readers can filter out those of no interest. Categories could knid

• Jeff Skates says:

Comment categories could include:
Notation
Definition
Query
Response
Joke
Extension
Related work
Others?