A new way of proving sumset estimates

A very important role in additive combinatorics is played by the following theorem. If is a finite subset of , or indeed of any Abelian group, and if , then for any non-negative integers and we have the estimate This is a theorem of Plünnecke that was rediscovered by Ruzsa. The proof had a structure of the following kind: define a type of graph, now known as a Plünnecke graph, and a notion of “magnification ratio”; formulate an inequality concerning Plünnecke graphs; using Menger’s theorem, prove the inequality for graphs with magnification ratio 1 (Menger’s theorem being used to find a collection of disjoint paths, the existence of which is a trivially sufficient condition for the inequality to hold in this case); using the tensor product trick and the construction of Plünnecke graphs that approximately have certain magnification ratios, deduce the result for all magnification ratios; construct a Plünnecke graph from a subset of an Abelian group; show, in a nice but not entirely obvious way, that the sumset estimates follow from the inequality about graphs.

The argument is an attractive one in the sense that it builds up to the result by means of clean and elementary steps (except perhaps that the approximations needed in the final step require one to get one’s hands slightly dirty). However, it is not an attractive argument if you have to give the proof in a lecture course: there are a lot of details to remember. I have this difficulty with other arguments too: there is a certain style of argument in combinatorics where one proves an amazing result after a long sequence of elementary observations. Reading such a proof can be easy, but remembering the precise sequence of elementary observations sometimes isn’t. Of course, if one feels this way about a proof, it is a good sign that one probably hasn’t fully understood the proof, as there is usually some story to tell about how the sequence of elementary observations was discovered. I freely admit to not fully understanding the proof of the sumset estimates in this deep way, and relying to some extent on memorization when I have lectured the result.

But now, I am glad to say, all that is a thing of the past. A research student of mine (about to be a former research student of mine), George Petridis, has come up with a ridiculously simple proof of the sumset estimates. Indeed, it is so ridiculously simple that my first reaction was that it could not be correct. Here’s the kind of reasoning I used: Terence Tao came up with a very nice argument, quite a bit simpler than the Plünnecke-Ruzsa proof, which gave a weaker bound that was still strong enough to be just as useful for applications in additive combinatorics. So it’s sort of obvious that getting the more exact bound must be irreducibly difficult. However, I should mention that George had previously come up with a new proof of Plünnecke’s graph inequality that had the same quality of “obvious wrongness”: it did not use Menger’s theorem, or anything like it, and did not use any kind of product trick.

Anyhow, the proof is so short that I can give it in full in this blog post, with George’s permission.

Polymath6: A is to B as C is to ???

The Polymath experiment is still very much in its infancy, with the result that we still have only a rather hazy idea of what the advantages and disadvantages are of open online multiple collaboration. It is easy to think of potential advantages and disadvantages, but the more actual experience we can draw on, the more we will get a feel for which of these plausible speculations are correct.

In my last post but one I outlined a few thoughts about the cap-set problem. Although this wasn’t meant as the beginning of a Polymath project (as I said in the post, it was modelled more on Gil Kalai’s notion of an “open discussion”), it had something in common with such projects, to the point where one of the worries people have about the Polymath approach actually occurred: I suggested a line of attack that was, unbeknownst to me, actively being pursued by somebody.

I do not know exactly what calculations went on in the minds of Michael Bateman and Nets Katz when they decided to go public with their ideas before they had fully worked them out, but my guess is that they wanted to establish that they had got there first. This they did by the very effective method of explaining that the simple observations that I had made were much weaker than what they already knew how to prove. As it happens, the story has had a happy ending for them, since they managed, soon after posting their comments, to push their ideas to the point where they have obtained the first improvement to the Roth/Meshulam bound, something that many people have wanted to do for a long time.