You're reading: Posts By Christian Lawson-Perfect

Happy Birthday to me

“Life moves very fast. It rushes from Heaven to Hell in a matter of seconds.”
― Paulo Coelho

This week, I was suddenly reminded of a fact I’d been meaning to keep track of, and I was disappointed to discover that even though I always endeavour to remember birthdays and holidays (mainly due to a system of elaborate reminders, notes and excessive list-making), I’d missed a hugely significant anniversary. Shortly after the clock struck midnight on New Year’s eve, I had passed one billion seconds old.

Hans Rosling and Raymond Smullyan have died

Why should I worry about dying? It’s not going to happen in my lifetime!

Raymond Smullyan, This Book Needs No Title (1986)

This week, the mathematical community has lost not one but two of its most beloved practitioners. Earlier this week, Swedish statistician Hans Rosling passed away aged 68, and today it’s been announced that author and logician Raymond Smullyan has also died, aged 97.

Mobile Numbers: Products of Twin Primes

In this series of posts, Katie investigates simple mathematical concepts using the Google Sheets spreadsheet app on her phone. If you have a simple maths trick, pattern or concept you’d like to see illustrated in this series, please get in touch.

Having spoken at the MathsJam annual conference in November 2016 about my previous phone spreadsheet on multiples of nine, I was contacted by a member of the audience with another interesting number fact they’d used a phone spreadsheet to investigate: my use of =MID() to pick out individual digits had inspired them, and I thought I’d share it here in another of these columns (LOL spreadsheet jokes).

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

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