HN Explorer

36 comments

[ 4.5 ms ] story [ 110 ms ] thread
raverbashing
It's the retraction of the retraction, basically
oh_sigh
Not exactly - Helfgott's initial analysis pointing out the flaw was(and still is) correct - it's just that Babai found a way to work around it.
jwtadvice
I remember the same thing originally happened with Wile's proof of FLT. It's heartwarming to know that scholars continue to skeptically check each other's work for factual correctness.
williamstein
Even better -- this situation is much more public and open than the situation with Andrew's FLT proof. I remember when Wiles proof was announced, when there was a gap, etc. only a select few got to actually look at the proof. It was only published after it had been very carefully checked. I started studying number theory exactly during this strange period of secrecy in 1993. Incidentally, exactly at that time, I used to play around writing computer games with Harald Helfgott, who is the guy who just found the mistake with Graph Isomorphism a few days ago... (He's a fantastic mathematician.)
saalweachter
I can't help but wonder if the qualitative difference in the problems -- graph isomorphism is an important, active area of applied mathematical research in search of a better algorithm, FLT was a multi-century abstract mathematical puzzler -- makes for a difference in the groups of people working on the problems and their attitudes.
Jweb_Guru
Graph isomorphism isn't that important practically (subgraph isomorphism is, but it's NP-complete and, IIRC, APX-hard as well) and the hard graph cases don't come up much in practice (despite being a relatively large percentage of random graphs, AFAIK). I think it reflects a difference in how mathematics is done; the quasipolynomial result was first presented at a conference, not in a paper, which definitely wouldn't have been the case 20 years ago.
mafribe
Wiles' original FLT result was first presented at a workshop in Cambridge, although he didn't explicitly state that he had succeeded (sans the gap) in proving FLT, he left that for the audience to infer.
tacomonstrous
And that doesn't even make it unusual. Most mathematical results are first presented at conferences or workshops, sometimes long before publication.
moomin
I was around at the time. I remember the buzz after day one of his two day workshop. Everyone knew where he was going.
JCzynski
Wiles was weird at the time. Math is done in public, he just really wanted to be the one to have the final valid proof of Fermat's Last Theorem.
jacobolus
Saying you’re working on FLT in the late 20th century is a good way to make everyone think you’ve gone nuts and are wasting your time. It makes some sense to make sure you have something solid before you mention it.
bonzini
Technically he was working on the Taniyama conjecture (now known as the modularity theorem), not on Fermat's last theorem.
digler999
or conversely, if they believe you, they could try to sniff your approach and take the credit for it. given the fame of FLT I dont blame him for doing it undercover.
cromwellian
If only the ABC conjecture proof was handled as transparently.
aalireza
What you're saying implies that a situation is -even- theoretically possible such that a radically new mathematical theory with near-completely novel underlying frameworks that's essentially developed by a single guy over the span of almost a decade that necessarily resulted in a deviation from the route focused by the majority of researchers, could be `quickly` understood/vetted by other mathematicians via traditional methods of un-automated peer-review process.

I guess if that was true, we would have been a significantly smarter species, or at a the very least, had god-like context-switching or learning abilities.

cromwellian
What I meant is, the author of the theory for a long time refused to travel and present his theory in person to walk others through it.

Things might have gone faster if the author had taken the time to teach others and help them understand it.

stablemap
I want to point out two more differences: in Wiles's case it took about a year of work with Richard Taylor to patch things up.
tacomonstrous
On the other hand, Wiles's work was quite a bit more complex conceptually just in terms of the sheer number of moving pieces involved, though the level of cleverness required is probably comparable in the two cases.
CJefferson
I don't think this is finished yet. The paper is very complex, and not completely checked yet. Other issues will possibly arise. That's part of any large maths proof.
tomrod
I don't know this work, about I appreciate the candor and honesty this academic presents. Thanks for posting.
WhitneyLand
This is so cool, the guy (among other things) beat an important algorithm that had stood as the fastest for decades.
wolfgke
Luks worked together with Babai on the previous fastest algorithm. Babai is just very modest when he only mentions Luks when reffering to it.
masalax
Great news!

>I am working on an updated arXiv posting.

I sure hope this isn't the new "I have discovered a truly marvelous proof of this, which this margin is too narrow to contain"!

cvoss
Babai commented that the new work-around requires a 2-page proof and makes 10 existing pages obsolete. So, a net savings of 8 pages, in theory! We'll see how it turns out.
pmiller2
Makes me wish it was possible to write a -8 page paper. :)
SixSigma
I would have written a shorter letter, but I did not have the time. - Blaise Pascal, Provincial Letters: Letter XVI (4 December 1656)
wolfgke
Just write an 8 page paper on antimatter [pun intended].
xiphias
Does this also mean that Bitcoin mining time is quasipolynomial with the difficulty parameter?
drdeca
I don't think bitcoin's work function is based on graph isomorphism?
xiphias
Yeah, I read more about it, only subgraph isomorphism is known to be NP-complete...of course the complexity of that will remain a mystery for a long time.
wolfgke
And finding a nonce that makes the block have a SHA256 with many leading zeroes is probably not an NP-hard problem.
xiphias
It is, some people also tried SAT solvers for mining:

http://jheusser.github.io/2013/02/03/satcoin.html

wolfgke
Please look up the definition of NP-hardness again. If the problem

(#) := "finding a nonce that makes the block have a SHA256 with many leading zeroes"

was NP-hard, it would be an interesting idea to use a solver for (#) to solve e.g. SAT (not the other way round!).

TLDR: You talked about the wrong inclusion.

ajkjk
Not even related.
[deleted]
(comment deleted)