Later On

A blog written for those whose interests more or less match mine.

Crowd-sourcing shrinking the prime gap

leave a comment »

I blogged earlier about the initial discovery, but lots has happened since, reported in Quanta magazine by Erica Klarreich:

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 ArticleUnheralded 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.

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, whichhe 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.

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: . .

Continue reading. And a very important point is made in a sidebar:

Wrong in Public

The entire Polymath project is available onlinefor 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.”

Written by LeisureGuy

30 November 2013 at 10:54 am

Posted in Math

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 1,347 other followers