10 ms·
Mathematicians Team Up on Twin Primes Conjecture
- Maven911 13y agoMontreal..on the map, finally. There's a lot of talent here.
- jrockway 13y agoMontreal was already on the map for Bixi. And probably other things.
- possibilistic 13y agoI'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 13y agoI 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.
- gizmo686 13y agoNot 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 http://en.wikipedia.org/wiki/Prime_number_theorem
- iclelland 13y agoThe overall density of primes is known, and decreases continuously as the numbers get larger (See http://en.wikipedia.org/wiki/Prime_number_theorem 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)
- misiti3780 13y agoI 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)
- deleted 13y ago[deleted]
- kazagistar 13y agoYep, 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.
- gizmo686 13y agoIt 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.
- jrockway 13y 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 13y agoTo 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 13y agoThanks for the clarification. Reading back through the article I see where that's mentioned, but I totally missed it the first time through.
- raz32dust 13y agoAh I had missed it too. Is there a bound on the gap between subsequent primes as well?
- lmkg 13y agoJust 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.
- prezjordan 13y agoNope :) 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.
- undershirt 13y agoThat is a neat proof :D
- atmosx 13y agoWeird, I just read about this exact example yesterday in the "music of primes" by Markus De Sautoy. I'm not sure though if it was the German Siegel or the Norwegian guy (Sebel or something) who also end up to Princeton to figure it out, or maybe it was known already by Euler's time :-) Neat proof indeed.
- joe_the_user 13y agoAh, 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 http://en.wikipedia.org/wiki/Yitang_Zhang
- sillysaurus2 13y agoIt's easy to believe academia is fading when you categorically ignore all of its achievements.
- cscheid 13y agoJohn 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 13y agoI 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...
- whatgoodisaroad 13y agoMy 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?
- fspeech 13y agoThat may be where Zhang is heading.
- tzs 13y agoSpeaking 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/ http://xxx.lanl.gov/abs/math.NT/0008177/
- whatgoodisaroad 13y agoThat is surprising. It's pretty incredible to see a formulation that doesn't involve any advanced Number Theory.
- est 13y agoZhang revealed during an interview that he's already made "astonishing" progress on RH. http://www.changhai.org/community/article_load.php?aid=1383356678 http://www.changhai.org/community/article_load.php?aid=13833... > 這個黎曼猜想，我手上也有一些東西，如果拿出來，也會很轟動，我就是這種習慣，如果沒有完全結果，或者到最後，我覺得我不可能再做了，我也許會把它拿出來，但我現在是不想拿出來的。 He won't publish it until he finalized it.
- jtchang 13y agoSo 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)
- lmkg 13y agoYou 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.
- thedufer 13y 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.
- jychang 13y agoThere's no such thing as a "quadruple pair of primes". Assuming x is prime, one of x+2, x+4, and x+6 has to be nonprime. More specifically, one of them has to be dividable by 3... If x mod 3 is 1, then x+2 is divisible by 3; otherwise, if x mod 3 is 2, then x+4 is divisible by 3.
- tempestn 13y ago
- simonista 13y agoWow, 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 13y agoA 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 13y agoThat 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.
- ww2 13y agoMaynard 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 13y agoI knew about the Wiki http://michaelnielsen.org/polymath1/index.php?title=Bounded_gaps_between_primes http://michaelnielsen.org/polymath1/index.php?title=Bounded_... However, I did not know about the solo paper http://arxiv.org/abs/1311.4600 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-that-two-random-numbers-are-coprime http://math.stackexchange.com/questions/64498/probability-th... Here we are trying to count primes separated by certain small gaps.
- drakaal 13y agoThe 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_vel 13y agoWhat? 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.
- drakaal 13y agoWhat 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.