Proof Claimed for Deep Connection between Prime Numbers
nature.com
nature.com
He is taking this claim seriously. He doesn't necessarily believe it's correct (presumably he's a bit careful in what he says to the press), but he seems to think it has a shot, and is worth paying attention to.
Presumably, it is experience in algebra, established reputation in field, and familiarity with communication of math that allow this subset of people to reasonably assess the papers. It is not to say that the theorem is so advanced that only 10 people on earth possess the aptitude to understand it - it is that only 10 people have the foundation on which to understand the theorem due to its specificity.
I think you are underestimating just how intricate and challenging understanding a proof can be. Especially one of this length and by someone of this standing.
And yes, a large part of being able to work in a specialized field like this really is about having the specialized knowledge and vocabulary, rather than general intelligence. If this is anything like most proofs in mathematics, most reasonably intelligent people would be able to understand it given ten years of studying the field. It's not about being smart enough, there's just so much existing knowledge that you need a lot of specialization to be able to really contribute to any given area.
Obviously I'm reading this wrong -- because as stated (and assuming that a, b, and c are positive integers) this seems trivially true -- sqp(abc) cannot be zero, r cannot be negative, and c is finite, so therefore sqp(abc)^r/c is greater than zero, QED.
Does Nature mean that the quantity does not approach zero as r tends to infinity (or some such)? Their example sure doesn't seem to indicate such.
The formulation in the article is a little confusing/non-intuitive. A perhaps more 'layman' explanation is that for every r > 1, there are only finitely many coprime tuples (a,b,c) such that a+b = c and c > sqp(abc)^r In other words, in "most" cases, sqp(abc) is greater than c!
This is equivalent to the definition in the article. Why? Well, given a fixed r, there are finitely many tuples that satisfy c > sqp(abc)^r. Since there are finitely many, we can pick a constant K > 0 st c < K*sqp(abc)^r for ALL tuples (a,b,c). Thus:
sqp(abc)^r/c > 1/K > 0, as the article mentions.
Looking back at the article, this is the critical bit:
> the ratio of sqp(abc)^r/c always has some minimum value greater than zero for any value of r greater than 1
That looks like it's just saying sqp(abc)^r/c > 0. But from what you're saying, the bit about the minimum value (1/K) is important. For each value of r, it should be possible to define a minimum value greater than 0 which sqp(abc)^r/c can never be smaller than. Right?
Are those minima interesting in themselves, or just as part of the whole conjecture? Is there a method for finding the minimum for a given value of r?
"It almost looks as if the method doesn't (as presently written) produce explicit constants. Hopefully as the ideas become more widely understood, effective constants will be able to be extracted."
The proof will be well beyond me, but the conjecture itself is pretty accessible, as are many of its connections.
This line from the article was confusing:
> Fifteen and 17 are square free-numbers, but 16 and 18 — being divisible by 42 and 32, respectively — are not.
but that's supposed to be 4^2 and 3^2, respectively.
I didn't understand that the ratio of import was sqp(abc)^r / c until I clicked through to the original story.
[0]: http://www.nature.com/news/proof-claimed-for-deep-connection...
> It states that for integers a+b=c, the ratio of sqp(abc)r/c always has some minimum value greater than zero for any value of r greater than 1. For example, if a=3 and b=125, so that c=128, then sqp(abc)=30 and sqp(abc)2/c = 900/128. In this case, in which r=2, sqp(abc)r/c is nearly always greater than 1, and always greater than zero
should be:
It states that for integers a+b=c, the ratio of sqp(abc)^r/c always has some minimum value greater than zero for any value of r greater than 1. For example, if a=3 and b=125, so that c=128, then sqp(abc)=30 and sqp(abc)^2/c = 900/128. In this case, in which r=2, sqp(abc)^r/c is nearly always greater than 1, and always greater than zero
http://www.nature.com/news/proof-claimed-for-deep-connection...
But: I'm not a mathematician, so maybe I'm just fantasizing right now.
> Mochizuki entered Princeton University at age 16 and received a Ph.D. under the supervision of Gerd Faltings at age 22. In 2002, he became a professor at the Research Institute for Mathematical Sciences in the Kyoto University.
Very impressive.
For every ε > 0, are there only finitely many triples of coprime positive integers a + b = c such that c > d (1+ε), where d denotes the product of the distinct prime factors of abc?
Unicode, of course: ε
When I need a Unicode character, I find it with my Unicode search page:
Then I copy the character into the document I'm working on. Others have more efficient ways to enter Unicode from their keyboards, like having a list of codes and a keyboard layout that allows the codes to be entered efficiently.
a⋅x² + b⋅x + c
are given by
x = (-b ± √(b² - 4⋅a⋅c)) / (2⋅a)
φ ∩ (ψ ∪ ρ) ↔ (φ ∩ ψ) ∪ (φ ∩ ρ)
Thanks! I can't even begin to describe how useful this will be!
If I could upvote this more than once, I would!
This is a technique John Horton Conway uses a lot, expressing conjectures as games, where two (or more) people try to do something in turns to make, or not make, something happen.
Useful idea.
http://mathoverflow.net/questions/106560/philosophy-behind-m...
Such a great answer proves that the question was worth asking. – Olivier 2 days ago
@Olivier: while I agree with your comment regarding the answer, I woould like to add that your inference regarding this particular question to me comes close to saying: the great and heroic work of the fire-fighters prove that it was worth setting the house on fire. – quid 2 days ago
On MathOverflow, though, it is possible to edit the original house so that it is no longer inflammatory, while still recording the work of the firefighter. – Terry Tao 2 days ago
[edit: formatting]
That means that if someone wants to check if the proof is right, he'll first have to learn how to use all these objects.
I'll guess we won't have a tested proof for some years.
[1] [SPA] http://gaussianos.com/posible-demostracion-de-la-veracidad-d...
In some sense, proof-checking is a trivial linear-time operation: you check that each step follows from the last, and if they all do, the proof is correct. Proof checking is something that computers do well, except that describing a proof to a computer is usually non-trivial.
Where proof-checkers -- human and otherwise -- will get hung up, especially with the new maths, is that it may not be obvious how each step follows from the last.
What will happen is something a bit interactive: if the proof checker cannot intuitively see the logic in one step of the proof, he may first try to prove the lemma himself. If he can't, he'll go back to the original author of the proof and say, "Hey, I don't see how you go from step 518 to step 519. Can you prove it?" Sometimes the author easily can; he just didn't elaborate on that step in the proof because it was so obvious to him. Sometimes he can't; either in trying to prove that lemma he finds a contradiction, in which case the proof is incorrect, or maybe he just can't prove it, and the proof is ... incomplete.
It's this last situation which causes these grand proofs to drag out for so many years. At some point in the 500 pages, there is a jump which the author didn't notice, and it takes him another few years to prove that jump. The checkers have a much easier job, because they just have to try to follow the logic; if they fail, the burden is on the author to make the point at which they stick more clear.
[1] http://www.kurims.kyoto-u.ac.jp/~motizuki/Inter-universal%20...
http://mathoverflow.net/questions/106560/what-is-the-underly...
[edit: Oops. Fixed attribution.]
Also, take a look at Minhyong Kim's answer.
Just the phrase "deep connection between prime numbers" sounds really interesting, so, if this were true would there be any practical application of this in the next (N) years that would not be possible without this proof?
I am not at all qualified to talk about the claimed proof, but I think it would be nonconstructive.
I dont really get how your response answers my question.
Can you really dumb it down for me; explain like I am 5 how this will result in practical applications in the next (N) years.
thanks
Of course, this isn't to say that new mathematics based on the result and on the techniques used to prove it won't lead to new algorithms.
This is fascinating.
One of the steps in generating an RSA key is, "Randomly generate two large prime numbers p and q. Multiply p and q, and save the product pq = p*q as part of your public key."
If anyone can figure out p and q from pq, then they can figure out your private key.
A while ago there was an article on HN about using the Euclidean algorithm to break SSL.
If you have two keys pq and rs, and one of the factors is the same (like p = r), then there's a well-known algorithm dating back thousands of years which you can use to quickly figure out the common factor's value.
So what the authors of a paper did was gather a couple million public keys from SSL websites, then run the Euclidean algorithm on each pair of keys, and many of them had common factors. Why? As noted above, the prime numbers are supposed to be picked "randomly," but they weren't picked randomly enough. (Getting a computer to produce random numbers is an interesting problem. The usual approaches are "faking it" -- technically called pseudorandom numbers -- and using input from hardware that interfaces with the outside world, like the system clock, keyboard, mouse, network, etc.)
So not just any old primes will work, and if two unrelated, unassociated people use the same software to generate "good" primes, sometimes they will coincide, leading to the potential for finding their factorizations with GCD on pairs.
Additionally, the more powerful ECM algorithm can be parametrized to generate about p different elliptic curves E_{a,b}(p), where p is found whenever E_{a,b}(p) has a smooth order. Once again, the chance of finding a pair (a,b) that results in such a smooth order is negligible. This is, in a nutshell, the result of Rivest and Silverman [1] dispelling the need to jump through many hoops to generate strong primes.
[1] http://people.csail.mit.edu/rivest/RivestSilverman-AreStrong...
Thank you.
I thought the GCD attack's success was more due to the lack of good entropy (randomness) in the random number generation, than due to a lack of eligible primes of the requested length.
This makes much sense -- some people might run the random-number generation on server systems, which often don't have any sources for human input (mouse movements and keystrokes can be a great source of randomness).
Or maybe it's simply a case of people using /dev/urandom instead of /dev/random because it's faster. (Which it is, but it's also not something you want to use for something as important as generating a key for long-term use.)
There are probably implications for mathematics.
No, they are not overly long. It's likely that papers explaining them will effectively be an order of magnitude (base 10) longer.
[edit - linked the wrong discussion]
Unlikely. The recent work doesn't improve our ability to factor large integers, the key to modern cryptography. If someone created a function that instantly produced the prime factors for large integers without the present difficult process, that would change everything, but that's not a likely outcome.
The next real challenge to modern cryptography isn't this work, but quantum computing. If quantum computing came to full flower with no obstacles sometime in the future, that would represent a basic change because it would perform an end run around the present computational difficulties that assure the security and reliability of our present methods.
I found some info here, but I didn't get enough out of it to answer my question directly. I think the answer is "Well theoretically, but it's complicated":
http://stackoverflow.com/questions/2768807/quantum-computing...
http://en.wikipedia.org/wiki/Quantum_computer#Potential
http://en.wikipedia.org/wiki/Shor%27s_algorithm
http://en.wikipedia.org/wiki/Post-quantum_cryptography
[...] most currently popular public-key cryptosystems
rely on the integer factorization problem or discrete
logarithm problem, both of which would be easily solvable
on large enough quantum computers using Shor's algorithm.
Even though current publicly known experimental quantum
computing is nowhere near powerful enough to attack real
cryptosystems, many cryptographers are researching new
algorithms, in case quantum computing becomes a threat in
the future.Shor's algorithm, on the other hand, runs in O((logN)^3). For an idea of the difference, log(64)^3 = 216, log(1024)^3 = 1000.
So Shor's algorithm could be used to very quickly factorize large numbers and would effectively break RSA. We just need a quantum computer, which as far as we know nobody has yet.
There will probably be significant warning before quantum computers exist which can break RSA. In that time it will probably become the norm to no longer use algorithms which are rendered obsolete by quantum computers.
Yes, but it's a big "if". There are many obstacles that stand in the way of quantum computing on a large scale, in fact some believe it will never be possible to maintain the delicate conditions required to perform quantum computation on a large scale.
The reason quantum computing could outperform conventional computation is because a quantum computer would, in a manner of speaking, process all possible problem statements at once, in parallel, and arrive at the best solution just as though only one problem statement had been processed. I know that may be difficult to imagine, but so is quantum. About quantum theory, John Wheeler said, "If you are not completely confused by quantum mechanics, you do not understand it."
Suffice it to say that quantum computing on a scale sufficient to pose a threat to public-key cryptosystems is not just around the corner.
As for the specifics, I believe we have working 4-qbit quantum computers, and shor's algorithm has been successfully applied to calculate that 15=3x5. But current approaches do indeed seem unlikely to scale up to 1024 qbits.
Yes, if you examine the mathematics that's true, but if you examine the physics it's not true. The problem doesn't lie with algorithm design, the problem lies with putting them into practice in actual physical computers.
> QM in general is really pretty simple and even obvious if you ignore the silly mythology and just follow the math.
On the contrary, not at all simple if one must try create an actual physical realization.
This is not to suggest that the problems won't be overcome, only that they're more formidable than describing how easy it is in principle.