Mathematicians Team Up on Twin Primes Conjecture

https://www.simonsfoundation.org/quanta/20131119-together-and-alone-closing-the-prime-gap/

by digital55 • 13 years ago

288 94 13 years ago

simonsfoundation.org

Maven911• 13 years ago

Montreal..on the map, finally. There's a lot of talent here.

jrockway2• 13 years ago

Montreal was already on the map for Bixi. And probably other things.

possibilistic• 13 years ago

I'm not a mathematician, but this is an interesting subject to me.

Does this imply a certain density to prime numbers? And given this new information, does it mean that it could be less computationally hard to find or verify primes?

boyter• 13 years ago

I would be curious to know what impact this would have on primecoin which appears to have gained a lot of traction over the last few months.

gizmo6863• 13 years ago

Not directly. This says that at any point on the number line, if you go sufficiently farther down the number line, you can always find 2 primes whose difference is no more than 600. It is possible that the distance between such groups gets arbitrarily large (at an arbitrarily fast rate) as you go down the number line.

Having said that, the primes do have a known density, given by the Prime Number Theorem [1]. This theorem states that the number of primes less then x is x/ln(x), as x approaches infinity.

[1]http://en.wikipedia.org/wiki/Prime_number_theorem

iclelland• 13 years ago

The overall density of primes is known, and decreases continuously as the numbers get larger (See http://en.wikipedia.org/wiki/Prime_number_theorem)

What this theorem says is that no matter how large the numbers get, no matter how sparsely the primes are spread out, on average, there will always be pairs of primes that are relatively close (within 600 of each other)

ars• 13 years ago

"on average" is the wrong concept here. Just leave it out of your sentence and it's correct.

misiti3780• 13 years ago

I might be way off here ... but does this not have implications for RSA encryption .. isnt the whole concept resting on the fact that two prime numbers cant be factored ... (I don't know shit about encryption obviously)

kazagistar• 13 years ago

Yep, way off, sorry. This has basically nothing to do with factoring. This is just proving that there is never a point beyond which no two prime numbers are 600 or less apart.

gizmo6863• 13 years ago

It has not actually been proven that RSA is backed by the difficulty of factoring. That is to say, it may be possible to break RSA without an efficient way to factor numbers. However, an efficient way to factor numbers does break RSA.

Having said that, there is no obvious way that this result helps with factoring. Indeed, the Twin Prime Conjecture states that the gap is actually 2. Obviously, this has not been proven, but if there was a way to use a proof of this fact to efficiently factor numbers, then we would have used that method without the proof. If it ends up not working, then we would have disproven the Twin Prime Conjecture.

jrockway2• 13 years ago

isnt the whole concept resting on the fact that two prime numbers cant be factored

No. Prime numbers have no factors.

RSA uses two prime numbers multiplied together to create a number with only two prime factors; factoring that number is the hard part if it's large enough.

This discovery has nothing to do with factoring large numbers.

davidjohnstone• 13 years ago

To clarify, this result means that there are infinitely many pairs of primes separated by at most 600. This doesn't mean that the gap between subsequent primes must always be less than 600.

Lazare• 13 years ago

Thanks for the clarification. Reading back through the article I see where that's mentioned, but I totally missed it the first time through.

raz32dust• 13 years ago

Ah I had missed it too. Is there a bound on the gap between subsequent primes as well?

lmkg2• 13 years ago

Just the opposite. The frequency of primes is known to be logarithmic, and therefore asymptotically approaches zero. From this, there cannot be such a thing as the largest gap between primes, because that would put a lower bound on the frequency of primes.

prezjordan2• 13 years ago

Nope :) Consider the number 1000000! + 1 (one million factorial plus 1).

  1000000! + 2 is divisible by 2.  
  1000000! + 3 is divisible by 3.  
  ...  
  1000000! + 1000000 is divisible by 1000000.

Here we have a gap of 999999 numbers, none of which are prime.

xyzzyz2• 13 years ago

For any natural n, the n consecutive numbers (n+1)! + 2, (n+1)! + 3, ... (n+1)! + (n+1) are all composite -- the first one is divisible by 2, the second one by three and so on.

Thus there are arbitrarily long sequences of consecutive numbers that have no primes in them.

joe_the_user• 13 years ago

Ah, an earth-shaking discovery made by a man in his fifties who was barely within academia [1]. Guess he won't get a Fields Medal for that.

It seems like more and more of the really big discoveries are being made by people who go off and work really hard on their own.

I vaguely recall a claim that the greatest discoveries aren't being made by people in their twenties any more just because math is so huge you need ten years of study to get to the bleeding edge.

Anyway, it seems to say something about academia.

Edit: Just to be clear I neither deny that academia can achieve great things nor do I claim that young people can't do similarly. Certainly, anyone halfway near academia probably see many flaws but that's for another post.

[1] http://en.wikipedia.org/wiki/Yitang_Zhang

sillysaurus2• 13 years ago

It's easy to believe academia is fading when you categorically ignore all of its achievements.

cscheid2• 13 years ago

John Baez has had an interesting series of posts about this on G+, but IIRC the gist of it is that even though both Grigori Perelman and Yitang Zhang were somewhat outside the mainstream of academia, their work was not. Both of them built on well-known theories and methods to prove their groundbreaking theorems. Perelman's primary tool, for example, was Ricci flows, which had been used at least 25 years before his work. (I know even less about Zhang's work)

hyperbovine• 13 years ago

I think the mathematical edifice is sound, but I can certainly see how being as divorced as possible from typical faculty responsibilities makes it easier to do original / groundbreaking research. Too many professors I know spend the bulk of their time attending to e-mail, grant writing, and traveling to give talks about work others have done. What little remaining time they have is often devoted to teaching. Some of them openly complain about how little time they have to actually think about things, while others seems to roll with it (being famous in your field is not a bad gig). Worse, the more successful you become the more these tertiary responsibilities encroach on your time. It's an open secret that the best-known professors in certain fields basically sign their names on the papers their postdocs and grad students write and that is more or less the extent of their research contribution. Cutting all this out, even if it means moving in with your mom in Moscow, could indeed be a viable option...

icambron3• 13 years ago

I don't get it. The article talks not just about Zhang, but also about James Maynard, who is a postdoc and looks young, and is part of what you might call standard academia. His result is independent of Zhang's and is orders of magnitude stronger and is much easier to understand. Comes off pretty good for academia, really.

Also, remember that most people on Earth aren't in academia, but most people still think. So the null hypothesis is that most innovations won't come from academia. But a huge amount of them do anyway, including even your counterexample, who--despite his economic struggles--was still a lecturer at a university. You could make a similar argument for young people.

Our university system and our cultural obsession with youth deserve plenty of criticism, but the accusation that they're not making important discoveries isn't one of them, and it's totally unwarranted from this article.

fspeech4• 13 years ago

Are you saying that Maynard independently tackled P(2) or that he independently came up with a better sieve? My take from reading the article is the latter.

azakai• 13 years ago

The article talks not just about Zhang, but also about James Maynard, who is a postdoc and looks young, and is part of what you might call standard academia. His result is independent of Zhang's and is orders of magnitude stronger and is much easier to understand.

Maynard has done some stellar work to be sure, but he built off of Zhang's breakthrough. Maynard's result is one of a sequence of very quick findings all happening in just months after Zhang's work became public, all make possible by that work, and relatively easy, as can be seen from their number and rapid pace.

I have not read all the papers here, but my guess is that Zhang's result is hugely more impressive.

Pitarou4• 13 years ago

... but most people still think.

I take issue with that.

People think, but they don't think far beyond what is directly accessible to experience, so I wouldn't call it academic thinking.

fspeech4• 13 years ago

Okay it appears that you and several others have not read the preprint paper. The article's wording is a bit confusing but if you think carefully you'd realize that a later work can not be independent of an earlier well known result.

The article does have a link to Maynard's preprint: http://arxiv.org/pdf/1311.4600v1.pdf

Here is an expert overview of the situation: http://www.dms.umontreal.ca/~andrew/CEBBrochureFinal.pdf

"In April 2013, Yitang Zhang proved the existence of a nite bound B such that there are innitely many pairs of distinct primes which dier by no more than B. This is a massive breakthrough, makes the twin prime conjecture look highly plausible (which can be re-interpreted as the conjecture that one can take B 2) and his work helps us to better understand other delicate questions about prime numbers that had previously seemed intractable. The original purpose of this talk was to discuss Zhang's extraordinary work, putting it in its context in analytic number theory, and to sketch a proof of his theorem. Zhang had even proved the result with B 70 000 000. Moreover, a co-operative team, polymath8, collaborating only on-line, had been able to lower the value of B to 4680. Not only had they been more careful in several dicult arguments in Zhang's original paper, they had also developed Zhang's techniques to be both more powerful and to allow a much simpler proof. Indeed the proof of Zhang's Theorem, that will be given in the write-up of this talk, is based on these developments. In November, inspired by Zhang's extraordinary breakthrough, James Maynard dramatically slashed this bound to 600, by a substantially easier method. Both Maynard, and Terry Tao who had independently developed the same idea, were able to extend their proofs to show that for any given integer m ¥ 1 there exists a bound Bm such that there are innitely many intervals of length Bm containing at least m distinct primes. We will also prove this much stronger result herein, even showing that one can take Bm e8m􀀀5. If these techniques could be pushed to their limit then we would obtain B( B2) 12, so new ideas are still needed to have a feasible plan for proving the twin prime conjecture. The article will be split into two parts. The rst half, which appears here, we will introduce the work of Zhang, Polymath8, Maynard and Tao, and explain their arguments that allow them to prove their spectacular results. As we will discuss, Zhang's main novel contribution is an estimate for primes in relatively short arithmetic progressions. The second half of this article sketches a proof of this result; the Bulletin article will contain full details of this extraordinary work."

EDIT: it appears that copying and pasting from the PDF is problematic and please read the linked PDF if interested.

rrrrtttt• 13 years ago

Established scientists stop producing groundbreaking results because of tenure. Once you have tenure, the biggest incentive to work hard goes away; it's simple economics. (Hence "mathematics is a young man's game".)

adiM• 13 years ago

For most people in academia, the incentive to work hard is not the fear to get fired, but the intrinsic satisfaction of working on a certain class of problems. Tenure does not take that intrinsic value away.

XorNot• 13 years ago

You might want to look into what "groundbreaking" entails because excited news articles lead nowhere all the damn time.

Tenure exists to escape people from the "3 papers a year" BS which means you get a neverending stream of minor refinements and very little thorough investigation.

GigabyteCoin• 13 years ago

an earth-shaking discovery made by a man in his fifties who was barely within academia

It's stories like these that make me jump with joy inside every time I think about the wonder that is the internet and the possibilities that creates for us as a human race.

The possibility that exists by having things like free 2,000 book encylcopedias (see http://en.wikipedia.org/wiki/Wikipedia%3ASize_of_Wikipedia#H...) at the fingertips of nearly every human on earth is just mind boggling.

I won't be surprised if Joe Average discovers the cure for Cancer tomorrow. Or AIDS. Or our fossil fuel addiction.

In fact, I expect those things to happen sooner than most of us might think.

Ar-Curunir• 13 years ago

Nah, I don't think the average person will discover the cure to cancer.

While access to freely available knowledge is increasing, this knowledge is mostly broad, not deep. So we can have information on a lot of topics, but these topics aren't covered in very much depth.

Also keep in mind that Zhang was very much within the fold of academia when he discovered the 70 million upper bound on the separation of primes.

crassus• 13 years ago

Precisely the reason to push for free and open academic journals that anybody can read.

rimantas• 13 years ago

I expect nothing like this will ever happen. You underestimate effort and amount of work (and training) needed for such breakthroughs. Also the cost of the research. I am afraid most of the low hanging fruits are already gone. You don't find cure for cancer just by reading a scientific journal over the evening tea and then dreaming up the formula.

velis_vel2• 13 years ago

I don't think that you can really call a professor with a PhD 'Joe Average'.

thaumasiotes4• 13 years ago

I vaguely recall a claim that the greatest discoveries aren't being made by people in their twenties any more just because math is so huge you need ten years of study to get to the bleeding edge.

This depends heavily on what you mean. Of course there are areas of math requiring ten (or more) years of study before you can work in them. However...

- In theory, all high school graduates have studied math for at least twelve years.

- There are many, many problems on "the bleeding edge" of mathematics, in the sense that no one can solve them, but which can be stated in terms an algebra student would have no trouble understanding. Further, there are many mathematical techniques which are "advanced" in the sense that they are never taught in school, but are "simple" in the sense that the algebra student I mentioned earlier would have no trouble following a proof using them. If you're interested, try reading through the archives of Tanya Khovanova's blog; she has plenty of examples of IMO problems and special Soviet math exam problems for Jews.

gizmo6863• 13 years ago

The difficulty with proving bleeding edge results in mathematics is normally not that the question is particularly advanced or difficult to understand, but rather that if it had an easy solution, then it would likely have been solved by now.

The only times I can think of where this is not the case is after a major, yet easy to understand, discovery makes a lot of formerly hard problem easy, or a field of mathematics that is either young enough, or uninteresting enough that it has not yet had significant time devoted to it.

atmosx2• 13 years ago

Being barely within academia today means having access to all the papers released along with many blog posts by PhD's who analyze the results and repercussions of a paper or a discovery.

The only example of out-of-academia, in the real sense, was Ramanujan[1] who was a sort of pure genius out of nowhere and was able to pull out formulas like this [2]. He wasn't constrict by the rigorous need for proof that Europeans were looking in order to accept any discovery for being true.

De Sautoy[3] states that Ramanujan non-formal (western-style) education kept him away from European mathematical achievements and but also away from European fears of inability to attack specific problems (i.e. like Riemann's Hypothesis for example[4]) and that was a good thing.

[1] http://en.wikipedia.org/wiki/Srinivasa_Ramanujan [2] http://bit.ly/1dh0E5w (Google image) [3] http://plus.maths.org/content/music-primes [4] http://en.wikipedia.org/wiki/Riemann_hypothesis

dominotw• 13 years ago

Ah yes. Andrew wiles preferred to work on his own and he 'disappeared' for years before he came up with his proof.

whatgoodisaroad2• 13 years ago

My understanding of the Riemann Hypothesis is that it can be reformulated as a statement about prime density. If this result is a concrete outer bound on density, does it have implications on RH?

fspeech4• 13 years ago

That may be where Zhang is heading.

tzs• 13 years ago

Speaking of reformulations of the Riemann Hypothesis, there is a surprisingly elementary statement that is equivalent to the RH.

Let H(1) = 1.

Let H(2) = 1 + 1/2.

Let H(3) = 1 + 1/2 + 1/3.

...and so on.

These are called the harmonic numbers.

Let S(1) = 1.

Let S(2) = 1 + 2.

Let S(3) = 1 + 3.

Let S(4) = 1 + 2 + 4.

Let S(5) = 1 + 5.

Let S(6) = 1 + 2 + 3 + 6.

The pattern here is harder to spot than the pattern for the harmonic numbers. S(n) for a positive integer n is the sum of the divisors of n. For instance, 6 is divisible be 1, 2, 3, and 6, so S(6) = 1 + 2 + 3 + 6.

Conjecture: for any positive integer n, S(n) <= H(n) + exp(H(n)) log(H(n)), with equality only when n = 1.

Believe it or not, this conjecture is equivalent to the Riemann Hypothesis!

Proof here: http://xxx.lanl.gov/abs/math.NT/0008177/

whatgoodisaroad2• 13 years ago

That is surprising. It's pretty incredible to see a formulation that doesn't involve any advanced Number Theory.

est• 13 years ago

Zhang revealed during an interview that he's already made "astonishing" progress on RH.

http://www.changhai.org/community/article_load.php?aid=13833...

這個黎曼猜想，我手上也有一些東西，如果拿出來，也會很轟動，我就是這種習慣，如果沒有完全結果，或者到最後，我覺得我不可能再做了，我也許會把它拿出來，但我現在是不想拿出來的。

He won't publish it until he finalized it.

jtchang• 13 years ago

So if I understand this right...it means that no matter how far along the number line I go (and I can go a long ways out) I will always be able to eventually find a pair of primes that are separated by no more than 600?

The crazy thing to me is that primes get less and less dense as you get further and further out. It would seem to me that once you reach a certain threshold you won't be able to find two primes "close" to each other anymore because primes will be so far apart from each other. But this says I will always be able to find a pair pretty close together? (I may be looking a long time though)

lmkg2• 13 years ago

You will always be able to find a pair of primes that are "close" to each other. However, the theorem makes no claim how far such pairs are from each other ;). To your point, primes get progressively less dense, which must also mean that these pairs get sparser still. It's probably quite vast distances between them, but infinity is a long ways, so it's not entirely surprisingly you find such improbably events with regularity.

thedufer4• 13 years ago

Maynard’s approach applies not just to pairs of primes, but to triples, quadruples and larger collections of primes.

Quadruples implies that it does, in fact, make a claim how far such pairs are from each other. In fact, it sounds like it could be used to make a claim about any finite grouping of primes. It would be interesting to see what kind of pattern those follow.

abuzzooz• 13 years ago

It would seem to me that once you reach a certain threshold you won't be able to find two primes "close" to each other anymore because primes will be so far apart from each other. ]

That is not quite correct. The average gap between primes gets larger as you move further along the number line. But, you will still get the occasional consecutive odd numbers that are close to one another. In fact, there is an old conjecture (Twin Prime Conjecture[1]) that claims that there are an infinite number of pairs of consecutive primes separated by 2.

PS. I'm not a mathematician (engineer with some decent math background), so I might very well be wrong.

[1] http://en.wikipedia.org/wiki/Twin_prime

fragsworth• 13 years ago

Yeah, this result is effectively getting a little bit closer to proving the Twin Prime Conjecture.

It would be interesting to see the proof get progressively closer to 2, but more and more difficult each time.

thatthatis• 13 years ago

In understanding how small prime gaps can occur so far out, it helps to think of primes as gaps in the projection of all prior prime numbers (i.e. the shadow of all prior primes).

It is then fairly easy to intuit that every so often there'd be gaps in the shadows right next to each other.

simonista• 13 years ago

Wow, this is a great story. First of all, props to the writer for weaving a bunch of different threads together in a way that made sense and was understandable to non-mathematicians without dumbing it down too much. And this is why I love math. There are so many great characters and themes in this story.

I love problems that can be stated so simply and yet are so fiendishly difficult to prove.

I love the idea that there is room for everybody in mathematics, from the lone genius outside of academia, to the young post-doc, to the unlikely collaborators.

Most of all, I love the idea that it's okay to fail, to throw out dumb ideas along with brilliant ones and that everyone makes mistakes, even Ph.D.'s in mathematics. We need more of that in education and academia generally.

sushirain• 13 years ago

A mathematician once told me that he doesn't appreciate research which leads to small improvement of a bound, but only research that leads to a conceptual novelty (like possibility). I guess this story shows that there is room for both.

adamfeldman• 13 years ago

That is the most beautifully well-written article about mathematics that I have read in my life.

The explanations made it completely accessible as a CS student with nothing more than calculus experience and familiarity with the concept of the search for primes.

ww22• 13 years ago

Maynard is too eager. He talked too much that is a coincidence. But the fact is that he is a member of the polymath project and all the works are consequences rather than coincidence.

mrcactu5• 13 years ago

I knew about the Wiki http://michaelnielsen.org/polymath1/index.php?title=Bounded_...

However, I did not know about the solo paper http://arxiv.org/abs/1311.4600

  In their celebrated paper [5], Goldston,
  Pintz and Yıldırım introduced a new method for counting   
  tuples of primes, and this allowed
  them to show that [eq 1.1]

  The recent breakthrough of Zhang [9] managed 
  to extend this work to prove [eq 1.2]

"Sieve methods" say integer properties like divisibility are essentially random. This is how we can show two integer randomly chosen are relativley prime with probabilty pi²/6= 0.608...

http://math.stackexchange.com/questions/64498/probability-th...

Here we are trying to count primes separated by certain small gaps.

drakaal2• 13 years ago

The bigger implication is that if you know the frequency of prime numbers and have a way to calculate when to expect them the difficulty in calculating new large primes is greatly reduced. In effect the strength of all encryption based on Primes is greatly reduced.

BitCoin, PGP, HTTPS, Certs, all just got orders of magnitude easier to crack. Well not just... It will take a little bit for time to use this information to create optimizations for beating each of these. But soon.

velis_vel2• 13 years ago

What? No. RSA doesn't depend on finding prime numbers, it depends on factoring large numbers, which is a completely separate problem. Elliptic curve cryptography doesn't depend on prime factorization at all.

Even if they did, I don't think this really helps you; knowing that there exist arbitrarily many primes within N doesn't help you find primes any faster.

drakaal2• 13 years ago

What do you think Factors are? Do you know what a Prime is? Do you know what a Factor Is?

I am skipping the rest of your arguments since. "What, Yes" is more correct.

Mathematicians Team Up on Twin Primes Conjecture

Related Stories