Number Theory

Together and Alone, Closing the Prime Gap

Comments (20)

print

On May 13, an obscure mathematician — one whose talents had gone so unrecognized that he had worked at a Subway restaurant to make ends meet — garnered worldwide attention and accolades from the mathematics community for settling a long-standing open question about prime numbers, those numbers divisible by only one and themselves. Yitang Zhang, a lecturer at the University of New Hampshire, showed that even though primes get increasingly rare as you go further out along the number line, you will never stop finding pairs of primes separated by at most 70 million. His finding was the first time anyone had managed to put a finite bound on the gaps between prime numbers, representing a major leap toward proving the centuries-old twin primes conjecture, which posits that there are infinitely many pairs of primes separated by only two (such as 11 and 13).

In the months that followed, Zhang found himself caught up in a whirlwind of activity and excitement: He has lectured on his work at many of the nation’s preeminent universities, has received offers of jobs from top institutions in China and Taiwan and a visiting position at the Institute for Advanced Study in Princeton, N.J., and has been told that he will be promoted to full professor at the University of New Hampshire.

Related Article: Unheralded Mathematician Bridges the Prime Gap

Meanwhile, Zhang’s work raised a question: Why 70 million? There is nothing magical about that number — it served Zhang’s purposes and simplified his proof. Other mathematicians quickly realized that it should be possible to push this separation bound quite a bit lower, although not all the way down to two.

By the end of May, mathematicians had uncovered simple tweaks to Zhang’s argument that brought the bound below 60 million. A May 30 blog post by Scott Morrison of the Australian National University in Canberra ignited a firestorm of activity, as mathematicians vied to improve on this number, setting one record after another. By June 4, Terence Tao of the University of California, Los Angeles, a winner of the Fields Medal, mathematics’ highest honor, had created a “Polymath project,” an open, online collaboration to improve the bound that attracted dozens of participants.

For weeks, the project moved forward at a breathless pace. “At times, the bound was going down every thirty minutes,” Tao recalled. By July 27, the team had succeeded in reducing the proven bound on prime gaps from 70 million to 4,680.

James Maynard.

Eleanor Grant

James Maynard, a postdoctoral researcher at the University of Montreal.

Now, a preprint posted to arXiv.org on November 19 by James Maynard, a postdoctoral researcher working on his own at the University of Montreal, has upped the ante. Just months after Zhang announced his result, Maynard has presented an independent proof that pushes the gap down to 600. A new Polymath project is in the planning stages, to try to combine the collaboration’s techniques with Maynard’s approach to push this bound even lower.

“The community is very excited by this new progress,” Tao said.

Maynard’s approach applies not just to pairs of primes, but to triples, quadruples and larger collections of primes. He has shown that you can find bounded clusters of any chosen number of primes infinitely often as you go out along the number line. (Tao said he independently arrived at this result at about the same time as Maynard.)

Zhang’s work and, to a lesser degree, Maynard’s fits the archetype of the solitary mathematical genius, working for years in the proverbial garret until he is ready to dazzle the world with a great discovery. The Polymath project couldn’t be more different — fast and furious, massively collaborative, fueled by the instant gratification of setting a new world record.

For Zhang, working alone and nearly obsessively on a single hard problem brought a huge payoff. Would he recommend that approach to other mathematicians? “It’s hard to say,” he said. “I choose my own way, but it’s only my way.”

Tao actively discourages young mathematicians from heading down such a path, which he has called “a particularly dangerous occupational hazard” that has seldom worked well, except for established mathematicians with a secure career and a proven track record. However, he said in an interview, the solitary and collaborative approaches each have something to offer mathematics.

“It’s important to have people who are willing to work in isolation and buck the conventional wisdom,” Tao said. Polymath, by contrast, is “entirely groupthink.” Not every math problem would lend itself to such collaboration, but this one did.

Combing the Number Line

Zhang proved his result by going fishing for prime numbers using a mathematical tool called a k-tuple, which you can visualize as a comb with some of its teeth snapped off. If you position such a comb along the number line starting at any chosen spot, the remaining teeth will point to some collection of numbers.

Zhang focused on snapped combs whose remaining teeth satisfy a divisibility property called “admissibility.” He showed that if you go fishing for primes using any admissible comb with at least 3,500,000 teeth, there are infinitely many positions along the number line where the comb will catch at least two prime numbers. Next, he showed how to make an admissible comb with at least 3,500,000 remaining teeth by starting with a 70-million-tooth comb and snapping off all but its prime teeth. Such a comb must catch two primes again and again, he concluded, and the primes it catches are separated by at most 70 million.

Admissible Combs

Roughly speaking, a comb is admissible if there is no obvious reason why its teeth couldn’t point entirely to primes infinitely often as you move it along the number line. If, for example, you take a five-tooth comb and snap off the second and fourth teeth, the resulting comb will not be admissible: it points to triples such as (2, 4, 6), or (5, 7, 9), or (11, 13, 15), and no matter where you place the comb, one of the three numbers in the collection will be divisible by 3. So once you get past the collection (3, 5, 7), you’ll never see another collection consisting entirely of primes.

But a three-tooth comb whose middle tooth gets snapped off has no such obstruction, so it is admissible. It points to pairs such as (2, 4), or (3, 5), or (11, 13), and there is no divisibility reason why it shouldn’t often point exclusively to primes. In fact, the twin primes conjecture is exactly the statement that this particular comb will point to prime pairs infinitely often.

A much more audacious conjecture called the prime k-tuple conjecture — a sort of twin primes conjecture on steroids — posits that any admissible comb will point entirely to primes infinitely often. In other words, the prime numbers display every plausible pattern, not just once but again and again. Plenty of computational evidence supports the prime k-tuple conjecture, but no one knows how to prove it.

The new work of Maynard and Tao gives very solid evidence for the conjecture, Granville said. “Will someone be able to build prime k-tuples in the near future? I doubt it,” he said. “But I’ve been wrong several times already.”

The finding is “a fantastic breakthrough,” said Andrew Granville, of the University of Montreal. “It’s a historic result.”

Zhang’s work involved three separate steps, each of which offered potential room for improvement on his 70 million bound. First, Zhang invoked some very deep mathematics to figure out where prime fish are likely to be hiding. Next, he used this result to figure out how many teeth his comb would need in order to guarantee that it would catch at least two prime fish infinitely often. Finally, he calculated how large a comb he had to start with so that enough teeth would be left after it had been snapped down to admissibility.

The fact that these three steps could be separated made improving Zhang’s bound an ideal project for a crowd-sourced collaboration, Tao said. “His proof is very modular, so we could parallelize the project, and people with different skills squeezed out what improvements they could.”

The Polymath project quickly attracted people with the right skills, perhaps more efficiently than if the project had been organized from the top down. “A Polymath project brings together people who wouldn’t have thought of coming together,” Tao said.

Prime Fishing Grounds

Of Zhang’s three steps, the first to admit improvement was the last one, in which he found an admissible comb with at least 3,500,000 teeth. Zhang had shown that a comb of length 70 million would do the trick, but he hadn’t tried particularly hard to make his comb as small as possible. There was plenty of room for improvement, and researchers who were good at computational mathematics soon started a friendly race to find small admissible combs with a given number of teeth.

Andrew Sutherland, of the Massachusetts Institute of Technology, quickly became a sort of de facto admissible-comb czar. Sutherland, who focuses on computational number theory, had been traveling during Zhang’s announcement and hadn’t paid particular attention to it. But when he checked in at a Chicago hotel and mentioned to the clerk that he was there for a mathematics conference, the clerk replied, “Wow, 70 million, huh?”

“I was floored that he knew about it,” Sutherland said. He soon discovered that there was plenty of scope for someone with his computational skills to help improve Zhang’s bound. “I had lots of plans for the summer, but they went by the wayside.”

For the mathematicians working on this step, the ground kept shifting underfoot. Their task changed every time the mathematicians working on the other two steps managed to reduce the number of teeth the comb would require. “The rules of the game were changing on a day-to-day basis,” Sutherland said. “While I was sleeping, people in Europe would post new bounds. Sometimes, I would run downstairs at 2 a.m. with an idea to post.”

The team eventually came up with the Polymath project’s record-holder — a 632-tooth comb whose width is 4,680 — using a genetic algorithm that “mates” admissible combs with each other to produce new, potentially better combs.

Maynard’s finding, which involves a 105-tooth comb whose width is 600, renders these giant computations obsolete. But the team’s effort was not a wasted one: Finding small admissible combs plays a part in many number theory problems, Sutherland said. In particular, the team’s computational tools will likely prove useful when it comes to refining Maynard’s results about triples, quadruples and larger collections of primes, Maynard said.

The Polymath researchers focusing on step two of Zhang’s proof looked for places to position the comb along the number line that had the greatest likelihood of catching pairs of primes, to figure out the number of teeth required. Prime numbers become very sparse as you go out along the number line, so if you just plunk your comb down somewhere randomly, you probably won’t catch any primes, let alone two. Finding the richest fishing grounds for prime numbers ended up being a problem in “calculus of variations,” a generalization of calculus.

Wrong in Public

The entire Polymath project is available online for anyone who wants to see “how the sausage is made,” Tao said. The blog discussion threads offer a unique glimpse into mathematics research, which usually happens behind closed doors.

In particular, Tao said, the online posts and comments make clear how much trial and error goes into developing mathematical ideas. Polished research papers often give the impression that their authors have never made a misstep. But in truth, Tao said, “great mathematicians make stupid mistakes, and this is a process that people often hide, because it is embarrassing.”

One of the bedrock principles of the Polymath approach is that participants should throw any idea out to the crowd immediately, without stopping to ponder whether it is any good. “There’s an explicit license to be wrong in public,” Morrison said. “It goes against a lot of people’s instincts, but it makes the project much more efficient when we’re more relaxed about saying stupid things.”

This step involved perhaps some of the least novel developments in the project, and the ones that were most directly superseded by Maynard’s work. At the time, though, this advance was one of the most fruitful ones. When the team filled in this piece of the puzzle on June 5, the bound on prime gaps dropped from about 4.6 million to 389,922.

The researchers focusing on step one of Zhang’s proof, which deals with how prime numbers are distributed, had perhaps the hardest job. Mathematicians have been familiar with a collection of distribution laws for primes for more than a century. One such law says that if you divide all prime numbers by the number three, half of the primes will produce a remainder of one and half will produce a remainder of two. This kind of law is exactly what’s needed to figure out whether an admissible comb is likely to find pairs of primes or miss them, since it suggests that “[prime] fish can’t all hide behind the same rock, but are spread out everywhere,” Sutherland said. But to use such distribution laws in his proof, Zhang — and, later, the Polymath project — had to grapple with some of the deepest mathematics around: a collection of theorems from the 1970s by Pierre Deligne, now an emeritus professor at the Institute for Advanced Study, concerning when certain error terms are likely to cancel each other out in gigantic sums. Morrison described Deligne’s work as “a big and terrifying piece of 20th-century mathematics.”

“We were very fortunate that several of the participants were well-versed in the difficult machinery that Deligne developed,” Tao said. “I myself did not know much about this area until this project.”

Terence Tao of the University of California, Los Angeles.

Kyle Alexander

Terence Tao of the University of California, Los Angeles.

The project didn’t just figure out how to refine this part of the proof to improve the bound. It also came up with an alternative approach that eliminates the need for Deligne’s theorems entirely, although at some cost to the bound: Without Deligne’s theorems, the best bound the project has come up with is 14,950.

This simplification of the proof is, if anything, more exciting to mathematicians than the final number the project came up with, since mathematicians care not only about whether a proof is correct but also about how much new insight it gives them.

“What we’re in the market for are ideas,” said Granville.

As the Polymath project progressed, Zhang himself was conspicuously, though perhaps not surprisingly, absent. He has not followed the project closely, he said. “I didn’t contact them at all. I prefer to keep quiet and alone. It gives me the opportunity to concentrate.”

Also absent, though less conspicuously, was Maynard. As the Polymath participants worked feverishly to improve the bound between prime pairs, Maynard was working on his own to develop a different approach — one foreshadowed by a forgotten paper that was written, and then retracted, ten years ago.

A Secret Weapon

Zhang’s work was grounded in a 2005 paper known as GPY, after its authors, Daniel Goldston of San Jose State University, János Pintz of the Alfréd Rényi Institute of Mathematics in Budapest, and Cem Yıldırım of Boğaziçi University in Istanbul. The GPY paper developed a scoring system to gauge how close a given number is to being prime. Even numbers get a very low score, odd numbers divisible by 3 are only slightly higher, and so on. Such scoring formulas, called sieves, can also be used to score the collection of numbers an admissible comb points to, and they are a crucial tool when it comes to figuring out where to place the comb on the number line so that it has a good chance of catching prime fish. Constructing an effective sieve is something of an art: The formula must provide good estimates of different numbers’ prime potential, but it must also be simple enough to analyze.

Two years before GPY was published, two of its authors, Goldston and Yıldırım, had circulated a paper describing what they asserted was a powerful scoring method. Within months, however, mathematicians discovered a flaw in that paper. Once Goldston, Yıldırım and Pintz adjusted the formula to repair this flaw, most mathematicians turned their focus to this adjusted scoring system, the GPY version, and didn’t consider whether there might be even better ways to tweak the original, flawed formula.

“Those of us looking at GPY thought we had the bases covered, and it didn’t cross our mind to go back and redo the earlier analysis,” said Granville, who is Maynard’s postdoctoral adviser.

About a year ago, however, Maynard decided to go back and take a second look at the earlier paper. A newly minted Ph.D. who had studied sieving theory, he spotted a new way to adjust the paper’s scoring system. GPY’s approach to scoring an admissible comb had been to multiply together all the numbers the comb pointed to and then score the product in one fell swoop. Maynard figured out a way to score each number separately, thereby deriving much more nuanced information from the scoring system.

Maynard’s sieving method “turns out to be surprisingly easy,” Granville said. “It’s the sort of thing where people like me slap their foreheads and say, ‘We could have done this seven years ago if we hadn’t been so sure we couldn’t do it!’”

Yitang Zhang

University of New Hampshire

Yitang Zhang of the University of New Hampshire.

With this refined scoring system, Maynard was able to bring the prime gap down to 600 and also prove a corresponding result about bounded gaps between larger collections of primes.

The fact that Zhang and Maynard managed, within months of each other, to prove that prime gaps are bounded is “a complete coincidence,” Maynard said. “I found Zhang’s result very exciting when I heard about it.”

Tao has been similarly philosophical about Maynard’s scoop of the Polymath project’s headline number.  “You expect the record to be beaten — that’s progress,” he said.

It is likely, Tao and Maynard said, that Maynard’s sieve can be combined with the deep technical work by Zhang and the Polymath project about the distribution of primes to bring the prime gap even lower.

The Polymath project has focused lately on writing up its findings in a paper, already over 150 pages, which it has been invited to submit to the journal Algebra & Number Theory. However, Tao predicted that the project’s participants will not be able to resist immediately sinking their teeth into Maynard’s new preprint. “It’s like red meat,” he said.

This time, Maynard plans to join in. “I’m looking forward to trying to get the bound as small as possible,” he said.

It remains to be seen how much more can be wrung out of Zhang’s and Maynard’s methods. Prior to Maynard’s work, the best-case scenario seemed to be that the bound on prime gaps could be pushed down to 16, the theoretical limit of the GPY approach. Maynard’s refinements push this theoretical limit down to 12. Conceivably, Maynard said, someone with a clever sieve idea could push this limit as low as 6. But it’s unlikely, he said, that anyone could use these ideas to get all the way down to a prime gap of 2 to prove the twin primes conjecture.

“I feel that we still need some very large conceptual breakthrough to handle the twin primes case,” Maynard said.

Tao, Maynard and the Polymath participants may eventually get an influx of new ideas from Zhang himself. It has taken the jet-setting mathematician a while to master the art of thinking about mathematics on airplanes, but he has now started working on a new problem, about which he declined to say more than that it is “important.” While he isn’t currently working on the twin primes problem, he said, he has a “secret weapon” in reserve — a technique to reduce the bound that he developed before his result went public. He omitted this technique from his paper because it is so technical and difficult, he said, adding that he may publish it next year.

“It’s my own original idea,” he said. “It should be a completely new thing.”

This article was reprinted on Wired.com.

Add a Comment

View Comments (20)

Comments for this entry

  • Withdrawn, I understand now… there are infinitely many pairs of primes that are separated by something less than 600, which is pretty different. Rather than every pair of primes being separated by at most 600, it simply means we’ll never stop finding pairs that are separated by something less than 600, despite most pairs being separated by increasing amounts.

  • When there are possibly a million approaches towards solving a problem, and the feasibility of each approach is verifiable in polynomial time, this problem is called NP-HARD. When a prophet tells you that one particular approach is doable, then everybody can solve this problem in polynomial time.

    When there are a million conjectures, and the provability of each conjecture requires indefinite time to know, this family of conjectures is called UNDECIDABLE. When a prophet tells you that one particular conjecture (e.g. bounded gaps between primes) is doable with contemporary techniques (modification of GPY), then a lot mathematicians, Tao for instance, would stop their current work and prove the conjecture “within months of each other”. I think you shouldn’t call this “a complete coincidence”.

  • In 2004 I read a book “The Music of the Primes” by Marcus du Sautoy and for a short time thereafter I became obsessed with pondering a solution. (I am a amateur with limited limited exposure to advanced mathematics, however, I love the art of the science and I am as likely to read a book on mathematics a any other. Why? I don’t know why.) My approach to solve the problem was a sieve solution. When I found the flaw and the sieve failed, I had exceeded my mental capabilities and finally, gave up. My point here is that I was very pleased with my work then and I am pleased that, I was on the correct path to a ‘aha’ moment even if ti is others that will finally achieve the goal. Thank you so much for the article, you made my day! By the by, I have always kept that spreadsheet of my sieve, so far it is my best mathematics work ever.

  • This is a beautiful, well-written and incredibly timely article. It is the best piece in Quanta (and therefore, the best popular science/mathematics anywhere) since the report on Ian Agol’s three-manifold breakthroughs, also by Erica Klarreich.

    I should also praise Maynard. It is unbelievable that he manage to get a stronger result (bounded gaps for any number of primes, improved bounds in the two prime case) while simplifying the proof (no need to mess with distribution of primes in arithmetic progressions, Bombieri-Vinogradov or less does it). This is nothing short of spectacular.

  • 70 million, 4,680, 600 and so on. The only special thing about these numbers is that it demonstrates that the way we look at numbers may be completely wrong.

  • This is a good reading, lots of information, well balanced materials.

    But one question pops up after reading this article:

    It’s just a bit over 6 months after Zhang’s breakthrough work was announced. Let’s suppose Zhang’s work were not announced back then. Can we assume Maynard’s findings by now (suppose no input from Zhang’s insight at all) can incur a even BIGGER twin primes breakthrough as well just by now? Is it really “a complete coincidence”?

    Although it’s still far away from the finish line (from now 600 to 2), the impression is that the pole was moved somehow after the tipping point.

  • There is a huge difference between “you know this method (or methods of this kind) is gonna prove something” and “you don’t even know something is even true”.

  • The most exciting sentence in this excellent article is the last one , especially if that ‘important ‘ problem is the GRH

  • I don’t think we are talking about ‘coincidence’ that the findings of a brilliant young mathematician, who only presented his DPhil in Oxford this summer, has just now come up with something that leaves the rest standing. He was busy doing his DPhil before!!! I think he has done all this since then. Well done James. Nice photo too.

  • Thank you for another very nice piece of popular writing on number theory.

    There was another superb recent advance in the field: Peter Scholze’s construction of Galois representations attached to torsion classes in the cohomology of locally symmeteric spaces for GL_n.

    Since it doesn’t deal with elementary mathematics, it of course, recieved absolutely no press. Can one hope that someone at Quanta will take up the challenge to write a popular piece on it?

  • One relatively easy way to drastically reduce the sieving field for twin primes (to 6/30 or 20% of natural numbers) is to start with numbers congruent to {1, 11, 13, 17, 19, 29} mod 30 (OEIS Sequence A230462).

    Outstanding article, btw.

  • It is a very exciting project. I would like also to say that the team technology is needed if near completion. However, if they keep doing the same thing by bringing down the gap number piece-by-piece, it may kill the beauty of mathematics.

    We are not only looking at the completion of the problem, to be frank, it does not have much application even in mathematics. We are looking at how we create new mathematics to solve this problem. That is the key!

    I can offer you another problem to think: (I am not a specialist of number theory, if someone had the similar suggestion, I would like to support his/hers) Now there are infinitive numbers of prime pairs, the length of the pair is at most 600. We want to get 600 to be 2. We knew that
    if p is a prime, then between p and 2p, there will be another prime (Bertrand’s postulate) . Question I would like to ask is: Can we prove that if p and p+2 are two primes, from p to p * (p+2) [or to (p*(p+2))^k], we can find a pair , q and q+2 , that are primes.

    In general if p and p+c are two primes, from p to p * (p+c) or to (p*(p+c))^k, we can find a q and q+c’ that are primes where c and k are constant and c’<=c. (p*q means p\times q.)

  • Just in case people follow this (excellent) article all the way down to the bottom of the comments: the most recent progress by Terence Tao and his distributed approach has seen their best bound fall to 272, which beats Maynard’s spectacular solo bound (my time of writing is January 4 2013–check Tao’s blog for updates after that).

  • The separation between primes is always equal to an even number , PS(prime separation) =E(even) , they co-exist you cannot have one without the other

  • I have been following the twin prime story since Zhang became a instant star last year. I know math at the Chinese High School level. I saw the “world record” being set almost every day. I can feel the vibe in the community that is contagious to an outsider like me. I ask my self, solitary or groups, or both. In my bio field, we do everything in groups. A lot of times, you feel you want to be alone to think, but it is very hard, since it is too noisy and too much stuffs is useless. Zhang and Maynard probably are tied up now, please free them from these chores, then we may have a chance to get the ultimate prize, the twin prime thing itself.

Leave a Comment

Your email address will not be published. Your name will appear near your comment. Required *