Monday, December 16, 2013

Sudden Progress on Prime Number Problem Has Mathematicians Buzzing




This is very much an article for those who care.  However actual progress on open questions on prime numbers is always unexpected because like all deeply researched problems in mathematics, you do not expect success going in.

Yet once Zhang broke the ice, we have had a rush to advance his line of inquiry and progress has been huge collapsing his original limit set arbitrarily high down to a number that is actually quite small.

This is all good for mathematics.

Sudden Progress on Prime Number Problem Has Mathematicians Buzzing

BY ERICA KLARREICH, QUANTA MAGAZINE
11.22.13


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.

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

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

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

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!’”

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

Original story reprinted with permission from Quanta Magazine, an editorially independent division ofSimonsFoundation.org whose mission is to enhance public understanding of science by covering research developments and trends in mathematics and the physical and life sciences.


No comments: