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.
George’s starting point is (I think) fairly standard: it is a reduction that I haven’t seen explicitly stated, but it can probably be read out of the usual proofs and may have been explicitly stated somewhere. Let and be two sets (soon it will be clear why this generalization is important in the proof) and suppose that Now choose a non-empty subset of such that the ratio is minimized and call this ratio Then we have the following two statements:
- for every
To prove the sumset estimates it is sufficient to prove the following statement.
Lemma. Let and be as above. Then for every set we have the inequality
Once we have this statement, then we can prove by induction that . Indeed, when we have equality, and for larger we can set to deduce that which is clearly enough. Note also that since it follows from this that
Therefore, (taking ) we already have the result that if then The full result with sums and differences follows from a standard use of Ruzsa’s triangle inequality — I’ll come to that later.
But for now let us see how Petridis’s main lemma is proved. This is the part of the argument that is new, and it is the part that is far simpler than I thought any such argument could possibly be.
Proof of lemma. I used to have a slightly dogmatic attitude that extremal combinatorics (including additive combinatorics) was too “global” for induction on the size of a set to play any serious role. Recent results of Tomasz Schoen and Jacob Fox have made me realize that I have been disadvantaging myself by taking that attitude. Nevertheless, I cannot help being surprised that it works here: Petridis proves the lemma by induction on the size of (or perhaps it is nicer to call it induction on itself). If is a singleton then the lemma claims that which is true because the left-hand side is and the right-hand side is and the inequality is one of our starting assumptions.
Now let us suppose that we know that and we want to prove the result for Obviously we know that
from which it follows that
However, this is not good enough, as we do not know that Indeed, this will be the case only if is disjoint from But there was a significant inefficiency in the above argument, since we can replace the first statement by
where is the set of all such that . And here we can use our second assumption, which tells us that Incorporating that information (and using the fact that ) we find that
It remains to prove that But
where is the set of all such that Moreover, this is a disjoint union, and It follows that
But if then so so we can deduce that
I would like to draw attention to the fact that only the second half of the above write-up of the proof was the proof itself. So it really is a ridiculously short and simple argument.
To complete the proof of the statement with differences as well as sums one follows the same argument that Ruzsa used at this stage. Ruzsa first proved a lemma (the “triangle inequality” mentioned above), which is the following statement:
That holds for any three sets and It is easily proved by defining a map by taking to where and are chosen such that One then checks that this map is an injection.
Recall that so far we have proved that if then there exists and such that for every (Incidentally, the fact that does not depend on seems to be a novel feature of Petridis’s argument.) From Ruzsa’s triangle inequality it follows that
and from that we get that In particular, if then we can deduce that implies that
A preprint containing a similar argument for non-Abelian groups, out of which this argument can be read, is on the arXiv here. I actually understood the argument from a private email George sent me when he first did the Abelian case, and also from a beautiful talk that he gave yesterday. The Menger-free proof of the graph inequality can be found here.