Slashdot Mirror
Mathematicians Team Up To Close the Prime Gap
Hugh Pickens DOT Com writes "On May 13, an obscure mathematician garnered worldwide attention and accolades from the mathematics community for settling a long-standing open question about prime numbers. Yitang Zhang 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). Now Erica Klarreich reports at Quanta Magazine that other mathematicians quickly realized that it should be possible to push this separation bound quite a bit lower. By the end of May, mathematicians had uncovered simple tweaks to Zhang's argument that brought the bound below 60 million. Then Terence Tao, a winner of the Fields Medal, mathematics' highest honor, created a 'Polymath project,' an open, online collaboration to improve the bound that attracted dozens of participants. By July 27, the team had succeeded in reducing the proven bound on prime gaps from 70 million to 4,680. Now James Maynard has upped the ante by presenting 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. 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. 'It's important to have people who are willing to work in isolation and buck the conventional wisdom,' says Tao. Polymath, by contrast, is 'entirely groupthink.' Not every math problem would lend itself to such collaboration, but this one did."
'It's important to have people who are willing to work in isolation and buck the conventional wisdom,' says Tao. Polymath, by contrast, is 'entirely groupthink.' Not every math problem would lend itself to such collaboration, but this one did."
History is rife with examples of the lone genius making a leap forward, thereby allowing the crowd to take it even further. See The Structure of Scientific Revolutions by Thomas Kuhn.
Er...2 and 3. What do I win?
Factoring prime numbers is dead easy. Here's an implementation in Python:
It's the factoring of composite numbers that is difficult.
Actually, even factorizing composite numbers isn't really difficult. It's just difficult to do it in a way that finishes before you stop caring about the result. ;-)
That is, basically, the theory, yes. But if we can get that number down to "2" it proves a centuries-old conjecture that could lead to all sorts of interesting proofs of other things becoming true also.
In terms of computers:
You do realise that we use the difficulty of, in particular, finding large prime numbers as the basis for most modern security protocols implemented on computers? Precisely BECAUSE it's so hard to do?
We're not talking about 2, 3, 5, 7, etc. but we're talking about primes with MILLIONS of digits. Primes so large that even to prove they are prime can take a long time. Primes so enormous that multiplying two of them together makes a number that's almost impossible to factorise back to the correct original primes, so much so that we use it as the basis for things like SSL, TLS, etc.?
And, no, computers can't do mathematical proof. They can help as tools but they are dumb. You do not prove that every number to infinity has a prime within, say, 600 numbers by printing out every number. By definition you'll be there until infinity on even the fastest possible machine in the universe. You could prove that primes up to a number X that would hold true, but X would never be sufficient to prove it was always true. Just the fact that primes only have to be N numbers apart before you hit the next one could lead to mathematics that might well accelerate the discovery and manipulation of primes themselves.
But if you come up with a clever mathematical proof that GUARANTEES the answer, no matter what X is or how many billions of digits it has, without having to worry about ever finding a *particular* prime, then you have something that a mathematician can take as "fact" and incorporate into larger proofs about the universe. Imagine if we just assumed that every prime was like this, and applied it to a large scale engineering project, and then found out that actually - once you get past a few billion atoms - the premise doesn't hold? It'd be catastrophic.
The last "proof by computer" (i.e. by brute-force rather than as a tool) was the four-colour theorem. And even that was just because the problem could be reduced (by a mathematician, and using other proven theories, and logical inference) to a few thousand cases that the computer could iterate. It was used as a time-saver back in the days of manual calculation, not mathematical proof.
There's none. the number of primes smaller than n is équivalent to n/ln(n) when n goes to infinity (thanks to Hadamard and Vallee Poussin theorem). If there was a upper bound for two successive primes, it wouldn't be the case.
According to modern mathematics definition, 1 isn't a prime number because it is invertible. If you allowed invertibles among prime numbers then uniqueness of the factorization in primes wouldn't hold anymore as your example shows. We could have {p} {p, 1} {p 1 1}.
Does anyone happen to know what the greatest known lower bound is? (i.e. the largest known difference of two successive primes?)
There is none.
Proof: Select an arbitrarily large number N. The numbers between (N! + 2) and (N! + N) are all composite ((N! +2) is divisible by 2, (N! + 3) is divisible by 3, ..., and (N! + N) is divisible by N). Since you can find an arbitrarily large span of composite numbers, there is no upper bound on the gaps between primes.
QED.
No we don't.
Primality testing is easy - the problem is in P. Approximate methods for finding primes are very efficient. Exact checking is rarely used.
Modern security protocols rely on the problem of factoring a number into primes being difficult. Or on inverting exponentiation within a prime field.
Slashdot: where don knuth is an idiot because he cant grasp the awesome power of php
It looks like you don't understand what GP was asking (at best) or you don't understand the summary/primes.
I think the GP was asking if there are always less than 600 between primes. The answer to his question is "no". The higher you go the larger gaps can be between primes. There can be untold millions/billions/trillions etc. between two distinct primes. This proof shows not that there are never more than 600 between primes, but that there are an infinite number of pairs of primes that are separated by less than 600. The difference is small but important. There may be two primes separated by a vast number, yet the higher you go there will always be a pair of primes coming up that are separated by less than 600.
For example:
The numbers
2^57,885,161 - 1
and
2^43,112,609 - 1
are primes. They have 17,425,170 and 12,978,189 digits in them. They are the largest two primes we know of. They are separated by a bunch of numbers in between them, almost 5,000,000 DIGITS (note digits not numbers) and all the numbers between them are composites. HOWEVER, the next largest prime may simply be (2^57,885,161 1) + 600 because there will always be a chance that there is a prime coming up less than 600 away from the current highest prime.
This is getting closer and closer to proving the long held belief/hope that there are an infinite number of primes separated by only 2. NOT that EVERY prime is separated by 2 from every other prime. That would be obviously false. Simply that there are an infinite number of primes salted throughout all those impossibly high ones that are only 2 apart.
No, the maximum distance grows without bounds. What this proves is that you can always find two more primes that are less than 600 apart, so the minimum distance does not grow without bounds. It has absolutely nothing to do with the distance between one pair of primes and another pair.
Live today, because you never know what tomorrow brings
And, no, computers can't do mathematical proof. They can help as tools but they are dumb. You do not prove that every number to infinity has a prime within, say, 600 numbers by printing out every number. By definition you'll be there until infinity on even the fastest possible machine in the universe. You could prove that primes up to a number X that would hold true, but X would never be sufficient to prove it was always true. Just the fact that primes only have to be N numbers apart before you hit the next one could lead to mathematics that might well accelerate the discovery and manipulation of primes themselves.
But if you come up with a clever mathematical proof that GUARANTEES the answer, no matter what X is or how many billions of digits it has, without having to worry about ever finding a *particular* prime, then you have something that a mathematician can take as "fact" and incorporate into larger proofs about the universe. Imagine if we just assumed that every prime was like this, and applied it to a large scale engineering project, and then found out that actually - once you get past a few billion atoms - the premise doesn't hold? It'd be catastrophic.
What you say has nothing to do with computers. Why would anyone program a computer to work case-by-case like that? It's just as futile as going case-by-case by hand. Likewise, if one is inclined to generate higher-level, logical proofs by hand, then why not program a computer to generate higher-level, logical proofs? Oh wait, that's been done for decades (eg. AUTOMATH, or the entire field of Automated Theorem Proving).
The last "proof by computer" (i.e. by brute-force rather than as a tool) was the four-colour theorem. And even that was just because the problem could be reduced (by a mathematician, and using other proven theories, and logical inference) to a few thousand cases that the computer could iterate. It was used as a time-saver back in the days of manual calculation, not mathematical proof.
Erm, what lets you define "proof by computer" as "by brute-force"? Are you claiming that all computer programs are brute-force? That's clearly nonsense. Are you claiming that a computer running an efficient algorithm is just a 'tool' and that the Mathematical ability actually exists in the algorithm's programmer? If so, you must also claim that Deep Blue's programmers are much better chess players than Deep Blue. In that case, why weren't they the world champions?
Also, the brute-force 'proof' of the Four Color Theorem, from 1976, was unsatisfactory to many people. It only proved the Four Color Theorem under the assumption that the program is correct, but nobody could verify such an assumption. In 2005 a new proof-by-program was constructed, but this time the program was written and verified in Coq. Only a tiny bit of code needs to be verfied in order to trust this proof (Coq's implementation of the Calculus of Inductive Constructions), and since this code is shared by all Coq users it's already had many eyes on it since appearing in the mid 1980s.
No, that's not the theory at all. The theory does not say there is always a prime within 600 of another (that's simply not true).
The theory says for any number X, there is a pair of primes larger than X within 600 of each other. That pair may be 2 larger than X, 12 larger than X, or 21,515,359 larger than X.
Everything else you said is pretty much spot on though.
This is not a proof by induction it is a proof by contradiction, no induction step is needed.
It assumes there is a number N such that their must be at 2 primes between M and M + N, for any M, then the proof goes on to show how to pick a M for which this is not the case.
unless you are referring to the proof that the numbers between N! and N! + N are divisible not primes (clearly they are since you can write it as a*k+k = a*(N + 1) where a*k=N! for all values of k between 1 and N ). But you don't need induction to prove that either.
all the numbers between them are composites.
Ahem. Those are the two largest known primes (because primes of that form are particularly easy to search for using existing techniques), but there's nothing to say that there are not unknown primes between them. In fact, there almost certainly are many; the density of primes in that region should be on the order of 1 in every 100 million integers, so there are probably at least about 10^17425161 other primes in that span.