Exciting real-time developments about prime numbers

Just a short post to note a way in which you can watch mathematical progress as it happens. Last month, Yitang Zhang announced a proof of a result that says that there are an infinite number of prime pairs no more than 70,000,000 apart. That may sound unimpressive, but it was the first time that anyone had proved anything about “bounded gaps” between primes. (It was, however, a natural outgrowth of other work on the size of prime gaps.) In his paper, he noted that he thought that the 70,000,000 number could fairly easily be reduced somewhat. (Note that if you reduced it to 2, you would prove the famous Twin Prime Conjecture, but the word is that that would be very unlikely to come out of just modifying or improving Zhang’s method.)

So a number of people, particularly the inimitable Terry Tao, took up the challenge. Tao is part of a group that supports the “Polymath” projects, which are a sort of crowdsourced way of doing mathematics (with “crowd” interpreted as “a few very smart, expert volunteers”). They took on the reduction of the 70,000,000 figure as their 8th project. Over the past few days the number (which they call H) has been decreasing quite a bit: look at the 4th column of the table on this page. Right now I see H = 252,804 as the best so far, which is far from 2, but still better than 70,000,000, and not bad for a couple week’s work.

Again, the main achievement was Zhang’s, to get any finite bound at all. It likely won’t be earth-shattering to reduce H, even if they get it down to 1,000 or so. (I would guess that H = 10 or so would be amazing, but I’m not an expert.) To put the 252,804 in perspective (but not to diminish the good work), I should note that it’s actually rather hard to find a specific prime gap that big. (They are mostly much, much smaller—it’s just that nobody could prove that it always stayed that way forever, even for huge numbers.) You can easily create such a gap (see below) by using numbers on the order of e^(250,000), but if you, say, want to find the smallest prime pair that has a gap that big, that’s very hard, and way beyond what is explicitly known. In fact, poking around on the Online Encyclopedia of Integer Sequences (oeis.org), I found a link to this page that lists all the known gaps that set a record for being the biggest gap for a given size prime—and the biggest such gap found is only 1476. So it seems that it would be especially interesting if the polymath folks could get H under 1476, since then you’re really starting to prove something about “small” prime gaps, as opposed to “not ridiculously huge” prime gaps…no idea if that’s remotely possible.

If you want to know how to create a prime gap of a specific size (using a really huge number, way more than is likely to be necessary), here it is. Suppose we want to create a sequence of m-1 numbers that are all composite. If you take m! + 2, m! + 3, m! + 4,…, m! + m, then these numbers are divisible by 2,3,4,5,…,m respectively, so that creates a prime gap of at least m-1. The trouble is, it starts beyond m!, which is really big.

You can do a bit better by only multiplying primes together, what’s called a primorial. Denote 2*3*5*7*…*p by p#. Then p# + 2,p# + 3,…, p# + p are all composite, and p# is rather less than p! (it’s around e^p). But e^250,000 is still really huge, so for the value of H that polymath8 is down to now, it’s not like it’s easy to create such a prime gap without using ginormous numbers.

There’s a conjecture that one should find a prime gap of 250,000 at around e^500, which is still really big (about a googol squared), but not so ridiculous (and in fact in the range of numbers that are used for high-security cryptography).

Update: I asked about this at Terry Tao’s blog, and he indicated that H = 10,000 would be a reasonable target for the polymath8 project. And in fact, as of today (21 June) the lowest claimed H at polymath8 is 12,042. That’s less than one order of magnitude bigger than 1467, which is cool. One would also expect, conjecturally (see page 5 of the linked paper), to see a gap of that size at around e^{\sqrt{12042/1.1}} \approx e^{105} \approx 10^{46}, well within the range of numbers used for modern cryptography.

This entry was posted in Uncategorized and tagged , , , , , . Bookmark the permalink.

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