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:
Post a Comment