The Aperiodical 

You're reading: Posts Tagged: Harald Helfgott

Graph Isomorphism panto: oh no it isn’t; oh yes it is!

By Katie Steckles. Posted January 21, 2017

As we reported back in November 2015, László Babai came up with an algorithm to decide if two graphs are isomorphic in quasipolynomial time. At the time, this proof still needed peer review, and in the last week or so, two big developments have occurred on that front.

On Wednesday 4th January, an error was discovered in the proof. Harald Helfgott (of the University of Göttingen in Germany and France’s National Center for Scientific Research), who studied the paper for several months, discovered that the algorithm was not quasipolynomial ($\displaystyle{ 2^{\mathrm{O}((\log n)^{c})} }$ for some fixed $c>0$) as claimed, but merely subexponenential: growing faster than a polynomial but still significantly slower than exponential growth).

Adorably, Babai posted this message on his website:

I apologize to those who were drawn to my lectures on this subject solely because of the quasipolynomial claim, prematurely magnified on the internet in spite of my disclaimers. I believe those looking for an interesting combination of group theory, combinatorics, and algorithms need not feel disappointed.

But maths is all about the drama, so on Monday 9th January Babai announced a fix for the error, and it’s now back on the quasipolynomial table. This has now been confirmed (as of 14th Jan) by Harald Helfgott himself at the Bourbaki seminar in Paris. Amusingly, Helfgott had only been studying the paper in such detail in order to give the seminar, and it was this close scrutiny which allowed him to discover the mistake.

More information

Announcement on Babai’s website

Fixing the UPCC Case of Split-or-Johnson – Babai’s paper detailing the fix (PDF)

Graph Isomorphism Vanquished — Again, at Quanta Magazine

Bourbaki Seminar – Harald Helfgott, on YouTube

On equivalent forms of the weak Goldbach conjecture

By Peter Rowlett. Posted May 17, 2013

Harald Helfgott has announced a proof of the odd Goldbach conjecture (also known as the ternary or weak Goldbach conjecture). This is big news. Like a good maths newshound, Christian Perfect promptly wrote this up for The Aperiodical as “All odd integers greater than 7 are the sum of three odd primes!”

Wait, though, there’s a problem. As Relinde Jurrius pointed out on Twitter, the formulation used in the paper abstract was not quite the same.

The ternary Goldbach conjecture, or three-primes problem, asserts that every odd integer $N$ greater than $5$ is the sum of three primes. The present paper proves this conjecture.

The version Christian used makes the assertion using odd primes, whereas the paper abstract only claims “the sum of three primes”. The latter version includes $7$ because $7$ can be written as the sum of three primes, but not odd ones ($7 = 3+2+2$). Certainly, you can see both statements of the weak Goldbach conjecture used (for example, here’s the $\gt 5$ version and here’s the $\gt 7$ version). Are they equivalent?

All odd integers greater than 7 are the sum of three odd primes!

By Christian Lawson-Perfect. Posted May 14, 2013

It seems that big mathematical advances are like buses – you wait ages for one, and then two come along at once. Also revealed yesterday was a proof of the odd Goldbach conjecture: that all odd numbers greater than 7 can be written as the sum of exactly three odd primes. The proof is contained in Major arcs for Goldbach’s theorem, a paper submitted to the arXiv by Harald Helfgott, who’s a mathematician at the École Normale Supérieure in Paris. This new paper completes the work started in Helfgott’s previous paper, Minor arcs for Golbach’s problem, published last year.

The strong Goldbach conjecture states that every even number can be written as the sum of two primes. This is still unproven, and remains one of the long-standing unproven results in number theory. Sadly, it’s the opinion of Terence Tao, among others, that the method used to prove the weak conjecture probably won’t work on the strong conjecture.

The paper: Major arcs for Goldbach’s theorem by Harald Helfgott

via Terry Tao on Google+