Expansion, divisibility and parity: an explanation

Back in March, I put a paper (joint with Maks Radziwill) up in the arxiv. It was 101 pages long (unsurprisingly, given that it was the outcome of several years’ worth of work) and may be a little hard-going. In particular, some readers may have mistaken some minor points or technical innovations for the main point.

I’ve decided to write an informal exposition, aiming for clarity rather than for conceptual perfection. I am hosting it on my departmental webpage, since WordPress would seem to like to charge me a stiff fee for using mathjax (or any other plugin) to display mathematical notation.

Here is the first part: https://webusers.imj-prg.fr/~harald.helfgott/Expansion_1.html

Comments welcome!

Hiring postdocs at Göttingen

I will be hiring two 2-year postdocs to work with me at Göttingen in the coming academic years. Please inform anybody you know who may be interested in this possibility. Apply as indicated in the advertisement. The deadline is December 27, 2017.

Job advertisement: Postdocs in Göttingen

Graph Isomorphism in Quasipolynomial time

My Bourbaki article on Babai’s algorithm for solving graph isomorphism in quasipolynomial time is now online.

(Short story for those who have been following the matter in the last couple of weeks: Babai’s fix is both correct and elegant – and I spent last week going through other things to make sure that the overall procedure was correct as well. I gave a Bourbaki talk on all of this last Saturday; here is the video.)

Bourbaki talks, and the articles that accompany them, are expository. As many readers know, they are given by invitation; speakers are designated by N. Bourbaki (who does not exist) and assigned to work on a recent paper, or series of papers, by other people. The topic is typically close to one of the speaker’s specialties, but not quite within it.

A Bourbaki article has a target audience broader than that of specialists, though of course it is still aimed at people in maths and allied fields. It is often a step in the process by which a new proof is elucidated, polished, and in general assimilated into the general body of knowledge. I have tried to do my best for Babai’s remarkable work.

I also hope this will help lead to further improvements in the area, now that the correctness and precise strength of the result are clearer.

Bourbaki talk

This afternoon – Saturday, 4pm, Paris time – I will give a Bourbaki talk on the work of Babai on the graph isomorphism problem, going as well over previous work (Luks, Weisfeiler- Le(h)man, etc.) that prepared the way towards it. I’ve spent the last few weeks – and that includes the last few days – going through everything with great care.

From Wikipedia:

“The Séminaire Nicolas Bourbaki (Bourbaki Seminar) is a series of seminars (in fact public lectures with printed notes distributed) that has been held in Paris since 1948. It is one of the major institutions of contemporary mathematics, and a barometer of mathematical achievement, fashion, and reputation. It is named after Nicolas Bourbaki, a group of French and other mathematicians of variable membership.”

As you can see from the link, a Bourbaki talk is always given by a speaker about other people’s work. It is accompanied by an expository paper explaining difficult recent material.

It is an honor and a pleasure of me to give a Bourbaki talk on Babai’s major breakthrough. This has been an exciting story.

I understand that my talk will be streamed live: live video. The notes will be made available online in the very near future. I hope they will make it easier for all others to follow the proof themselves.

Graph isomorphism in subexponential time

In the course of preparing my Bourbaki talk on Babai’s work on the graph isomorphism problem, I found an error. It is serious. Babai has succeeded in recovering a result that, while weaker, is still remarkable.

Preparing a Bourbaki talk implies (a) going through somebody else’s work in great detail, and (b) preparing an expository paper on the subject. My exposition of Babai’s work is ready and will be publicly available in the next few days. It is a complete walkthrough of the proof, and should allow others to verify, as I did, that the modified version is correct.

Here is an excerpt from my introduction (in French in the original):

“Thm 1.1 (Babai) .- The string isomorphism problem can be solved in time exp(exp(O(sqrt(log n log log n)))) for strings of length n.

It is clear that the bound here is sub-exponential, but not quasipolynomial. In November 2015, Babai announced a solution in quasipolynomial time, with an explicit algorithm. The process of preparing this expository work confirmed that the algorithm was correct, or easily repairable, but it also made me realize that the time analysis was incorrect. The version announced here is correct.

Thm. 1.2 (Babai).- The graph isomorphism problem can be solved in time exp(exp(O(sqrt(log n log log n)))), where n is the number of vertices.

Our main references will be [Babai’s 2015 preprint and his extended abstract at STOC 2016]. We will attempt to examine the proof in as much detail as an expository work of this format allows, in part to help eliminate any doubt that may remain on the current form of the result. The error lay in a part of the proof that can be isolated and corrected, and might be later improved on its own (“Split or Johnson”). The rest of the work – rich in innovative ideas – is still valid.”

See also Laci Babai’s own announcement on the subject:

http://people.cs.uchicago.edu/~laci/update.html

Update (Jan 14): As many of you know, Babai posted last Monday that he had fixed the problem. This is just to tell you that (a) his fix is correct (and elegant), (b) I have spent the last five days checking other things in the proof and making some bits explicit. I can now state with assurance that the proof is correct: Babai is now giving an algorithm that works in quasipolynomial time. See the video of my Bourbaki talk at https://www.youtube.com/watch?v=7NR975OM2G8&list=PL9kd4mpdvWcCN64K5VhaYFH_gBa-WlIr3&index=1

I will put up the corresponding expository article soon.

 

 

Hangul and stinky tofu

It has been a while since I last wrote here. I might as well restart matters with a brief update.

Summer was full of activities and travel. After giving a course at the summer school on analytic number theory at IHES, I went to Korea for most of August (ANTS and of course the ICM). Then I went back to Paris and got the keys to my new office at IMJ (Paris VI/VII), where I will be from now on as a CNRS Directeur de recherche. The office is in the Paris VII campus, close to the Bibliothèque Nationale and, most importantly, the Cinémathèque.

… and then I left for Saint Petersburg, to spend a trimester there as a Lamé Chair. During that time, I was offered a Humboldt Professorship (at Göttingen) , which I am now considering.

I have been back in Paris since late December, after relatively brief trips to Perú and the Czech Republic. I also managed to lose the keys to my office in the interval. It took a very long time to get another set of keys.

On a different note – my survey paper on growth in groups got accepted; it is about to appear. I also spent a great deal of time rewriting my proof of the Ternary Goldbach Conjecture – it is now in an essentially self-contained monograph. Besides adding expository material, I simplified some parts of the proof – notably the part on parabolic cylinder functions.

I have some partial drafts of planned blog posts from the last few months. Let me include here a brief set of impressions from my Korea trip. I did this in French, just to keep my chops up.

Conference in Петербург

It is high time I told about my adventures in Korea at ICM (Hangul, stinky tofu, old and new friends) and about the very pleasant time I’ve been having in Saint Petersburg (maths, opera). But not yet!

Let me first announce the following conference, which will take place in St Petersburg at the end of November:

I hope it will turn out rather well. Please tell us if you want to attend – though, as we have limited funds, you would essentially have to fund your trip through your own grant (or your advisor’s, if you are a student, but we might be able to help with lodging in that case.) Things may be easier if you are in Russia. All are welcome!

Math people moving around

In the June 2014 issue of the Newsletter of the European Mathematical Society,there is
an article (by Martin Andler, from Versailles) on the invited speakers at this year’s ICM, and, in particular, on geographical shifts in their career.

Besides offering some tables, the article briefly enumerates a few perspectives on the movement of mathematicians between countries, without really endeavouring to resolve the tensions between them. My aim here will be to give a summary of the situation and what I see as a second step in the analysis of these issues, in part with the hope that readers of this blog will discuss them further.

AGRA II

I am now able to make this public: the second AGRA school (Aritmética, Grupos, Análisis) will be happening in Cusco in August 2015.

Here is the website.

We are still putting together funding, but we have already managed to ensure quite a bit, and so we will be able to fund quite a few graduate students and young researchers (and perhaps some that are not quite so young). Our aim is to cover the expenses of admitted applicants in South America fully, and to cover the local expenses of people from elsewhere as well.



I’m not calling it a “summer” or “winter” school, since climate at a moderate-high altitude (3400 meters over sea level) relatively close to the equatorial line simply does not follow that categorization. “Dry-season school” would have sounded a little odd, even though it would have been accurate.

(Implications: sunny, cool at night and in the early morning, no mud, no rain, and unfortunately, no mushrooms either.)

As I said: people of all genders are encouraged to apply – or, in Spanish, tod@s están invitad@s a postular, which is a rather nice way to put it, since it explicitly includes cyborgs.

I hope the speakers will find they have been fairly depicted by their photograph:



This depicts the use of the Monte Carlo method to approximate an area. Many thanks to Martín Chambi!

Meta- and Galois

First, some extradiegetic comments. I did not post much last year. The main reason is obvious – for the first half of the year, I was very busy finishing the proof of the ternary Goldbach conjecture; then, during the summer, I had many speaking engagements – and I also spent a non-trivial amount of time writing a popular account of the proof for this blog. I spent the October-December rewriting the second, longer half of the proof – so that the proof is now in three papers, each of them a little over 70 pages in length. (I was also looking for new topics, doing some more travelling and lecturing, and retaking Russian and Classical Greek, among other things.)

At the same time, even though I had many reasons for staying away for blogging, it is a bit of a pity that I did not have time to blog precisely at a time when there started to be many more potential readers for it. Of course, some of them (you) are probably still around.

So far, I have written here mostly on mathematics, cinema and my travels. I would also like to touch a bit more frequently on a few serious subjects, not strictly mathematical, though sometimes related to mathematics and academia.