I personally know Brian Conrad (quoted in article). He has an encyclopedic knowledge of algebraic number theory and algebraic geometry, I would say that he's in the top ten people worldwide who could reasonably assess whether Mochizuki's proof is correct. And he has a great nose for bullshit, and little patience for it.
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.
Right, because "experience in algebra, established reputation in field, and familiarity with communication of math" can be acquired by anyone with only a modicum of smarts.
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.
Unless I misread, I don't believe I saw anything that implied that the poster was claiming that anyone with a modicum of smarts could contribute significantly to the study of elliptic curves as relates to Diophantine equations. That being said, there are a mind-boggling number of extremely specific sub-specialties in mathematics, each of which would demand a significant investment of time from even a very intelligent person to reach a deep understanding of the state of the art. The fact that only a handful of folks are sufficiently versed in a particular sub-specialty to evaluate a long, involved and presumably brilliant proof attempt that draws significantly upon the state of the art of that sub-specialty does not imply that only a handful of folks are sufficiently intelligent to evaluate the proof. This reminds me of the recent attempt on the P/NP problem by Vinay Deolalikar - plenty of extremely talented mathematicians watched from the sidelines because they did not have sufficient specialized knowledge to properly evaluate the proof; though, that did not imply that the proof was particularly brilliant or even correct (http://michaelnielsen.org/polymath1/index.php?title=Deolalik...).
Reputation in the field is not a proxy for general intelligence. That there are only 10 people with the reputation to make it worth them assessing the proof does not mean those are the only 10 people with the smarts to understand it.
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.
I do not assert that reputation is a proxy for general intelligence. However, reputation is a cornerstone of becoming a peer reviewer, and it takes peer review for an assertion to become science. Therefore, my assertion is more so that having reputable academics backing the paper will decrease the equivocacy of its assertions and aid its adoption rather than assert that reputation functions as a proxy for intelligence.
It is not unreasonable to assert that it takes intelligence to understand this area of mathematics. However, it is wholly inane to assert that one is intelligent if and only if one understands the intricacies of this proof.
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.
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.
Yes, sqp(abc)^r/c is greater than 0. But what we are saying here is that it is _bounded_.
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:
Thanks, after reading that through a couple of times, I think I understand what it means.
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."
this is for the abc conjecture[1] (I was thinking maybe they were being headline-y about the Riemann hypothesis before I clicked through), which, if proved, would be extremely interesting due to the number of conjectures and other theorems that have been shown to be equivalent to it or direct consequences of it.
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.
> 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
The way I see it Mochizuki's work could turn out to be like Maxwell's theory of electromagnetism. It could give us a definitive theory on the nature of prime numbers, but first someone needs to come and understand and solve it. A 'solution' of a differential equation system would be a formula, a 'solution' of Mochizuki's system would be an algorithm. Many new algorithms could come out of this, and one of them could be an algorithm for prime factorization.
But: I'm not a mathematician, so maybe I'm just fantasizing right now.
Warning: This article is mangled by the flattening of all the superscripts in it. Given that it's about powers, the math is all but unreadable. You have been warned. :-)
> 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.
I found the formulation of the theorem difficult to digest, but the wikipedia version was much clearer:
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?
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.
Those familiar with LaTeX may find the following tool useful: http://www.unicodeit.net/ It takes LaTeX symbols as input and outputs the unicode for them. There is a mac app available too, which will convert it in-place for you too.
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.
also, most platforms I have used have some kind of software to look up characters, e.g. on OSX you have something like "character map" where you can search by name/category
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
This link was already posted in this thread. And as I mentioned there, it wasn't Gowers but Martin Weissman who wrote the first answer. http://news.ycombinator.com/item?id=4503359
I don't expect the new maths to cause a delay from learning so much as from verifying.
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.
Here's a presentation of the mathematician the article is about. It's on the nature of "Inter-universal Teichmuller Theory"[1] which apparently was the work leading up to the proof.
That explanation was not written by Gowers at all (his name appears on it now that the answer was marked community wiki, becuase he is the most recent person to edit it, to fix a typo), and indeed although Gowers is certainly brilliant, this is far from his domain of expertise. That answer was written by Martin Weissman (username: Marty), the author information is at the bottom right corner of any answer and here says "Marty 98%".
Can anyone explain in lag terms what the implications of this may be.
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?
abc conjecture is asymptotic. That is, its statement is of the form "for every positive epsilon there exists a constant". A proof can be constructive, that is, an algorithm that can calculate a constant from an epsilon, or it can be nonconstructive. For any practical application it would seem a constructive proof is needed.
I am not at all qualified to talk about the claimed proof, but I think it would be nonconstructive.
His answer was that he thinks there will be no practical applications from this proof, since it merely states that something exists without giving us an idea of how to find that thing.
Yeah. For the most part non-constructive proofs are only good for proving things about existing algorithms - their convergence properties, their correctness, their running time etc. Formal proof often isn't necessary in practice, though - "seems to work well enough" is ok in many domains.
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.
> cryptographic algorithms are largely implemented relying on primes
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.)
There's even more at work here. In the context of RSA and DHMW there are bad primes and good primes. A prime p is potentially bad if p-1 has no large factors. The algebraic structures associated with pq are then combinations of small algebraic structures, and that can (sometimes) make pq easier to factor.
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.
There is little point in concerning oneself with smooth p-1, p+1, Φ_i(p) values. Randomly-chosen primes will have a negligible chance of having such properties.
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.
Right, so what you're saying is that when the primes are smaller, as they used to be able to be, strong (and safe) primes were a good idea because the earlier methods of factoring could exploit their potential weaknesses. However, it's now the case that with ECM and GNFS methods of factoring we've had to move to much, much larger primes, so the weaknesses are no longer relevant.
> two unrelated, unassociated people use the same software to generate "good" primes, sometimes they will coincide
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.)
yes, prime factorization is the predominant method for making cryptography "hard" to brute force. Earlier in it's history, discrete logarithms were also used to make brute force un-palatable, but factorization based cyrptography rules the roost right now.
This guy's thesis has an approachable explanation of the conjecture, as well as some of the interesting theorems that it implies (including an asymptotic version of Fermat's Last Theorem):
there's an apostrophe before the "s" in "Masters" that is stripped out by the HN code for some reason. either add that or go to http://jeffreypaulwheeler.com/ and select the link "The abc Conjecture" near the start of "Papers Section".
At this stage, yes, it's naive. The ideas and techniques here are pretty much completely new, and it will take years, if not decades, for people to understand them deeply enough to find the essential core of what's happening.
No, they are not overly long. It's likely that papers explaining them will effectively be an order of magnitude (base 10) longer.
> If there is some kind of connection between prime numbers, wouldn't a lot of the current work in encryption be thrown out?
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.
Ok, off topic, sorry, but... Are you saying that if/when quantum computing comes around, existing encryption systems would be suddenly ineffective? So if the NSA gets their hands on a quantum computer, they'd be able to brute force a 1024bit RSA encrypted file in far quicker time than their other super computers?
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":
[...] 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.
Yes. The naive algorithm for factorization runs in O(2^N) (where N is the number of bits in the number you want to factorize), which is impractical for any sufficiently large N (2^64 > 10^19, 2^1024 > 10^328 which is BIG). There are better known algorithms, but none of them are polynomial, so a bruteforce is highly impractical.
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.
Ok, thanks. But when I start hearing conspiracy theories that the NSA (or anyone) has already developed one, I should basically look for an encryption algorithm that isn't based on prime factorization?
Encryption algorithms exist and are being developed which are not based on prime factorization and for which no known quantum algorithm exists which can break them in polynomial time.
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.
> Are you saying that if/when quantum computing comes around, existing encryption systems would be suddenly ineffective?
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.
I think that's the wrong attitude to take. If you look at the mathematics there is really nothing so weird or magical about quantum mechanics or using it to perform factorization; you just take a set of qbits initially in an equal superposition of all possible factors, manipulate them through quantum operations such that the amplitudes of all the factors that don't divide the number go to zero, and then measure the state to force a collapse/entangle yourself with it, and the number you measure will necessarily be a factor. QM in general is really pretty simple and even obvious if you ignore the silly mythology and just follow the math.
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.
> If you look at the mathematics there is really nothing so weird or magical about quantum mechanics or using it to perform factorization ...
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.
It is funny, but AFAIK there is no established lower bound on the complexity of factoring problem. Even in the realm of classic computation. Anecdotally - Ron Rivest estimated in 1977 that factoring a 125-digit number would require 40 quadrillion years. RSA-129 was solved in 1994. RSA-768 in 2009.
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.