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

as required.

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.

February 10, 2011 at 12:13 pm |

As an extra remark, let me point out that there is a story one can tell that makes the proof seem very natural. (It is not quite the same as the route by which George himself arrived at the proof.) You argue as follows. Suppose you know that and want to prove that An obvious approach is induction on And that leads very naturally to the following conjecture: if then for every which we hope to apply with

Now we have the idea of using induction on (which, as I said above, is not one that I myself would have had, but that was a silly problem of mine, since it is a perfectly reasonable thing to try). You consider what happens when you add an extra element, go through the reasoning that was contained in the proof of the lemma, all of which is basically the obvious thing to do, and then hit a brick wall because you don’t have any control over But then you realize you can obtain that control if you begin by passing to a subset of such that the ratio is minimized, and that doing that does not stop you being able to deduce what you want to deduce when you have finished the proof.

February 10, 2011 at 4:03 pm |

[…] Menger’s theorem is no longer needed fro the graph inequalities. Gowers has posted the nice proof in his blog, with links to Petridis’s papers on the ArXiv. 43.614000 […]

February 10, 2011 at 4:16 pm |

This is fantastic! I was just lecturing on Ruzsa-Plunnecke-type estimates, and planned to give the Menger Theorem and magnification ratio proof. But now I don’t have to (well, I suppose I will mention the tensor power trick, since it is so interesting and useful)!

I agree with you about how hard it is to lecture on some of these theorems (or rather, remember the precise sequence of elementary observations at the board), despite how easy it is to read about them and follow the proofs in the book.

February 10, 2011 at 10:25 pm |

This comment is prompted by an email from Antal Balog, who felt that I had made the argument unnecessarily complicated. Since his suggestion was closer to what Petridis himself actually did (which I very slightly modified), I now think I should definitely mention it, even though it is basically the same argument — just viewed from a different angle.

We start with the observation that

where as before, is the set of all such that As before, this is a disjoint union and Therefore

But so from which it follows that

and therefore that

The minimality of and the inductive hypothesis imply that this is at most

February 11, 2011 at 12:00 am |

This is indeed very nice! It reminds me a little of the Dyson e-transform machinery that can be used to prove the Cauchy-Davenport inequality or Kneser’s inequality.

The lemma can be abstracted a bit as a lattice-theoretic statement. Instead of looking at the expansion properties of the map , one can consider a more general map from finite sets to finite sets, which respects unions: (in particular, is monotone). As a corollary of this and inclusion-exclusion, one obtains the submodularity inequality

for any . In particular, if we set for any fixed K, we have

.

The abstract version of the lemma is then: if are a sequence of finite sets such that and for all and , then . Indeed, by construction, and for any , thus for any , and thus .

Indeed, now that I look at it, it seems that Petridis has managed to obtain the set-theoretic version of the argument used to prove the entropy Plunnecke-Ruzsa inequality, that I discuss in

http://terrytao.wordpress.com/2009/10/27/an-entropy-plunnecke-ruzsa-inequality/

I had been puzzled in the past as to why that simple entropy argument did not appear to have a known set-theoretic analogue, so Petridis’s argument is quite satisfying in that regard. It makes me wonder whether there is a more systematic dictionary between set addition and entropy addition that is worth exploring here.

Finally, I should point out that my inability to see simple arguments is by no means a demonstration that no such argument exists. (For instance, I had been working on the finite field Kakeya problem for years, and even put half of Dvir’s argument in a paper with Mockenhaupt without realising what we had got, before Dvir solved that problem with a beautifully simple argument.)

February 11, 2011 at 5:53 pm

On that last point, let me quickly say that what I was saying was slightly subtler than “If Terence Tao hasn’t found it then it doesn’t exist,” (though I would still contend that your not having found something decreases the probability that it exists, and in this case Imre Ruzsa hadn’t found it either). The background, as you know, is that Plünnecke found the graph theoretic proof that used Menger’s theorem and a product argument, and Ruzsa independently found the same proof. That is a very strong indication that there is something natural about that approach. Then you found a simpler proof that gave a weaker bound. At that point it is tempting to imagine an alternative world in which you made your discovery first, and indeed there is no particular reason that the proof you found should have been discovered after the proof that Plünnecke and Ruzsa found.

Had things indeed gone the other way round, then I think it would have been very natural to describe the state of affairs as follows: Tao found a nice argument that bounds the size of in terms of the size of Pl¨nnecke and, independently, Ruzsa, then used a more complicated argument to obtain a bound which has a sort of sharp feel about it (not for the actual bounds obtained for sumsets, but for more general statements that follow from their methods). From that it would be tempting to conclude that if you want a more exact result you have to work for it.

It was thoughts like that — not as detailed of course — that led me not even to consider the possibility that there could be such a simple proof of the sharper sumset estimates — I did think that there ought to be a way of circumventing the product trick but I thought that Menger’s theorem, or something like it, was playing a fundamental role.

February 12, 2011 at 11:23 am

Well, to be honest my primary objective was to obtain an elementary proof of a weak Plunnecke bound, as this would have been enough for the applications I had in mind; the sharp bound would have been nice, but as soon as I was able to get a weak bound, I declared victory and moved on.

(There is an interesting interplay in analytic combinatorics between the “extremal” branch, which focuses on obtaining extremely sharp bounds, and the “asymptotic” branch, which allows losses in various constants and exponents. As a general rule, the asymptotic results, being weaker, are easier to prove, but here we see a counterexample. (And thanks to tricks such as the tensor product trick (in one direction), or careful induction (in the other), it is sometimes possible to derive a non-asymptotic result from an asymptotic result or vice versa.))

February 11, 2011 at 12:51 pm |

This is remarkable. I had been skipping Rusza-Plunnecke (giving only estimates for |k A|, k>=3, instead) in expository lectures because of how long the proofs used to be.

Does this by any chance give anything for sets A\subset G, G a non-abelian group, A of small doubling (|AA|<=c|A|, c small) but large tripling (|AAA| large)?

February 26, 2011 at 6:34 pm

Yes, actually Petridis’s paper contains an answer to this, in particular another proof of Tao’s result that a set A of small doubling has small tripling if and only if AaA is small for all a in A.

Another consequence of Petridis’s beautiful argument is the fact (also due to Tao) that a set of small doubling always contains a large subset of small tripling (namely the subset of A realizing the minimal expansion as in Petridis’s proof).

Similarly, it shows that a set of small doubling is always controlled by an approximate group (see Tao’s paper on non-commutative product set estimates).

February 14, 2011 at 8:03 pm |

This is a stunning proof of the Plunnecke-Ruzsa inequality!

Another nice consequence of Petridis’s main lemma is a simple proof of the additive version of Ruzsa’s triangle inequality [*, Corollary 6.2]. Perhaps this has already been noted. As far as I know, there is no elementary proof of this inequality along the lines of the proof of the standard triangle inequality.

For any nonempty finite subsets B, C, X of an additive group G we have

|B+C| |X| ≤ |B+X| |C+X|.

Proof. Let A be a subset of X such that the ratio |A+B| / |A| is minimal and let K be this minimal ratio. Then, by Petridis’s lemma (applied with A_0=X), we have

|A+B+C| ≤ K |A+C|.

Since K ≤ |X+B| / |X| we obtain

|X| |B+C| ≤ |X| |A+B+C| ≤ K |X| |A+C| ≤ |X+B| |A+C| ≤ |X+B||X+C|.

* I.Z. Ruzsa, An application of graph theory to additive number theory, Scientia, Series A. Official journal of Universidad Tecnica Federico Santa Maria, 3:97-109, 1989.

February 20, 2011 at 9:03 pm |

Being truly excited and fascinated, I am still a bit cautious as to whether one should now forget the Plunnecke-Ruzsa method forever. Say, using this method Ruzsa proved the very useful fact that for any finite, non-empty subsets of an abelian group with , there exists a non-empty subset such that

I would not be surprised if this were deducible from Petridis’ lemma, but there does not seem to be an immediate deduction around — or does it?

February 20, 2011 at 11:43 pm

I haven’t thought properly about that, or about a question Antal Balog asked me, which is whether Petridis’s methods give the result that if and then there exists such that It may indeed be the case that there are some things that require the more difficult argument. However, Petridis’s graph theory paper contains a simpler proof of the graph theoretic inequality of Plünnecke, so I’m not sure that the full strength of the original argument is needed. Petridis would be better able to answer these questions than I am.

February 21, 2011 at 8:23 am

Exactly — this inequality with pointed out by Balog was another thing I also had in mind!

February 22, 2011 at 11:48 am

I have pondered about Seva’s question myself and definitely believe there are enough reasons to not forget about the graph theoretic method. Naturally it depends on the context. Some years ago I attended a graduate course in additive combinatorics lectured by Tim. Only one, admittedly large, part of the course was devoted to his proof of Szemeredi’s theorem for progressions of length four. Only one of the essential ingredients is Freiman’s theorem. Only one of the many interesting results needed in Ruzsa’s proof of Freiman’s theorem is Plunnecke’s inequality. In this context I am sure that Tim, and even the keenest members of the audience, would rather not have to dwell on directed layered graphs. (Though, as Ernie Croot pointed out, in this case one should find a different excuse to demonstrate the mighty tensor product trick. I will offer a standard example in the next reply.)

Someone doing research on the subject has different needs. Intuition and experience, for example, are hard to define and measure, but are essential and in my opinion one’s intuition is sharpened by having experience of the graph theoretic side. While talking about intuition and experience is tricky and I am not even sure others should take my advice on how to conduct research seriously, I will try to quantify the statement above.

It goes beyond the fact that thinking of sumsets as layers of a graph joined by edges that represent elements helps lesser minds like myself visualise what is going on. Compared to dealing with sumsets one has fewer options in graphs. This can sometimes be a good thing. Tim has offered an example by bringing up induction on the size of . This type of induction may not be as common in additive combinatorics, but is one of the options in one’s disposal when dealing with Plunnecke graphs. It is furthermore effective. For example it helped answer two graph-theoretic questions that interested me and so I have considered induction a natural tool for quite some time. The same holds for attempting to partition, rather than simply cover, sumsets. By this I mean taking a little care when thinking of as the union of translates of $A$.

I am treading in dangerous waters as having read Plunnecke’s original paper is definitely not necessary to come up with the simple ideas that help one choose appropriately. Nor is any graph theory. In fact, Tim’s first comment is a much more natural path to choosing . All I can say for certain is that having experimented with Plunnecke graphs helped me and I suspect it might help somebody else in another instance.

There are more objective reasons to not let the graph theoretic result slip into oblivion and have to do with its flexibility. This is related to the questions asked above. To keep the reply short I will address them separately.

February 21, 2011 at 4:02 pm |

[…] post is just to link Tim Gowers’s recent blog post on Plünnecke-type sumset estimates in groups because he discusses the recent work of his […]

February 22, 2011 at 1:34 pm |

Here is a slighly different perspective on the inductive argument establishing the main Lemma. Before giving it, I should say that I didn’t read Petridis’ papers yet, so maybe everything I say is already stated explicitly there, and in any case it occurs at least implicitly in Tim’s post above.

Throughout, I use capital letters to denote non empty finite sets living in some commutative ambient group. Let us say that is excellent for if it minimizes the ratio , i.e. if for every one has .

Now it is not hard to observe that “ is excellent for ” is equivalent to the existence of a bijection from to itself such that if then .

[Why? — The reverse direction follows from the fact that for every the map provides an injection from to . To see the forward direction, consider a society whose set of men is , whose set of women is and in which a man knows all women of the form , where and . Now every set $Z$ of men knows women, and hence at least women, which means that we can arrange each man to marry exactly women according to the marriage theorem. Now define in such a way that for each man the set of women he marries is .]

The main Lemma, asserting that if is excellent for , then for each $C$ one has can now be proved by exhibiting an injective map from to , as follows: Impose an arbitrary linear oreder on and fix any bijection as above. Now given an arbitray element from , write $s=t+c$ with and $c\in C$ such that $c$ is minimal in the sense of the linear order we have chosen for . Let and let be the image of in . Let us check that this map is indeed injective, as we need it to be. For this purpose, let be another element of , define , , and in the expected way and suppose that as well as . We have to show that and . Assume that we had . Then without loss of generality is smaller than in the linear order on . Note that $s’=t’+c’=t’-x’+x’+c’=x+(t’-x’)+c$. Note that , (since ), and . Thus in decomposing in order to carry the above definition out, we could have chosen instead of , and in fact we should have done so as is smaller than . This contradiction establishes , so by the hypothesis also get . Applying to the equality we infer . For this reason we have and , as claimed.

February 23, 2011 at 7:01 pm

Another perhaps interesting problem is this: Recall that if is excellent for either or , then . But now suppose that is excellent for . Prove in a way that is as interesting as possible that then we also have . (I’m not satisfied with my own proof, so I’m not mentioning it here.)

February 22, 2011 at 4:34 pm |

In this reply, like in the previous, I assume knowledge of the standard proof of Plunneke’s graph theoretic inequality. I thought about introducing the terminology and facts I am using so that the readers not familiar could follow. I decided against this as it would have take a while and the replies to the post indicate that interested readers know about the standard proof. Apologies if this doesn’t include everybody.

I would like to first draw further attention to an important fact. The lemma, as Tim pointed out, is a slightly stronger version of the Plunnecke-Ruzsa inequality. A set is found such that holds for all . There is an equivalent stronger statement for Plunnecke graphs. Suppose that the vertex set of the graph is and that is such that the (“directed”) neighborhood of has size . Then the image of in has size at most . This can be deduced from the traditional form of Plunnecke’s inequality by induction on [c.f. Theorem 2.3 of http://arxiv.org/pdf/1101.5001%5D. Note however that using the lemma allows one to reverse the order of proof for sumsets: instead of deducing the stronger form from the traditional, one (if so inclined) can deduce the traditional form from the stronger.

More importantly, most statements about sumsets have a stronger formulation. Proving them directly and in an elementary manner is another matter. Tim is triumphantly and typically proven to be right as it is the induction that fails in all interesting cases. To be precise I cannot see how to even start the induction, though this shouldn’t discourage anyone from trying. Christian’s comment may be useful in this direction.

The response turned out to be too long. I will therefore break it down in three posts. First I will address the question of Antal Balog and then that of Seva. In the end I will also talk about restricted sumsets that appear in Ruzsa’s papers.

February 22, 2011 at 4:42 pm |

Balog’s question has a special case that is interesting in its own right. Suppose that is a singleton. Then has the same size as . The question then becomes: is there an elementary proof that is decreasing? I know that Ruzsa had worked on this and that the statement follows from Plunnecke’s inequality, but not much more. If my cross-referencing is correct I suspect that Seva knows more. An affirmative answer to Balog’s question that is based on induction probably has to answer this simpler question. I should also say here that an affirmative answer to Balog’s question would follow if we prove the lemma for restricted sumsets. More on them later.

February 23, 2011 at 11:52 am

This particular case, i.e. monotonicity of seems to have a rather easy elementary proof, which is as follows. Recall that Gyarmati, Matolcsi and Ruzsa have shown that if are additive sets and if one sets

as well as

for , then

.

(See Theorem 1.2. of their paper “A superadditivity and submultiplicativity property for cardinalities of iterated sumsets”, which recently appeared in Combinatorica 30 (2010), 163-174.)

The proof is short, elementary and beautiful.

Now if we just look at the particular case of that theorem where for all , then we get

,

which means that we have indeed

.

February 23, 2011 at 5:34 pm

This is indeed very nice.

February 22, 2011 at 5:28 pm |

Seva’s question (or to be precise what I interpreted it to mean) is a little easier to answer. There is a graph-theoretic proof of Plunnecke’s inequality for different summands. It is similar to a theorem of Ruzsa that can be found in pages 19-20 of http://www.renyi.hu/conferences/sze70/Talks/ruzsa.pdf .

There is however another simple argument that needs only the Plunnecke-Ruzsa inequality and does not require general Plunnecke graphs. I have seen it in Plunnecke’s Inequality for Different Summands, by Gyarmati, Matolcsi and Ruzsa. http://arxiv.org/abs/0810.1488 It is very standard, but I include it here in case that is what Seva wanted.

For notational convenience take and . We let and . Consider the Cartesian product of the underlying group with cyclic groups and of size respectively and . Then let , , and . Observe that . So by the Plunnecke-Ruzsa inequality there exists such that . Now simply observe that . The size of the left hand side is and we have therefore proved . The factor of four can be removed via the tensor product trick.

I should state the obvious: using the lemma hardly changes anything, though strictly speaking the bound on can be derived from it. The above proof suggests that the we want to choose is one that minimizes the ratio over all . I don’t know how to use this effectively, but am happy to share the little intuition I have.

February 23, 2011 at 6:54 pm

It still seems an interesting problem to me to try to find a more elementary proof that does not use the tensor power trick, basically for the following two reasons:

First, if one fully writes out the tensor power argument, one initially only gets a set living in some , and then one has to argue that may actually be taken to be of the form for some appropriate . As far as I know, this latter argument seems to require one to redo the “harder direction” of the proof of the statement that magnification ratios of Plünnecke graphs behave nicely under taking products in a sumset setting (which takes a few lines) or otherwise to construct the Plünnecke graph itself and refer to that theorem. Both alternatives seem, at least to me, to be less elegant than George’s recently discovered arguments.

Secondly, a general feature of “elementary” arguments (as opposed to abstract ones) seems to be that they do not require much more “mathematical space” than the question they intend to answer. E.g. a proof of a number theoretic statement that only mentions natural numbers themselves is usually more elementary than a proof using complex analysis in an essential way, a proof of Hindmans theorem that just mentions properties of sets of natural numbers (as Baumgartner’s) is more elementary than the more usual one taking about compact sets of ultrafilters, i.e. sets of sets of sets of natural numbers, and so on. Thus I think that a truly elementary proof of the result referred to by Seva should not appeal to our ability to form very large tensorpowers; instead it should never leave the ambient group and instead proceed by making clever extremal choices, exhibiting clever injective (or surjective) maps, and so on.

February 22, 2011 at 5:56 pm |

Time to define Ruzsa’s restricted sumsets. These are useful when one tries to find good bounds on for two general sets and . A good way to bound is to partition in sets and bound b the sum of the . This is an overly generous approach and it is better to proceed like in the proof of the lemma. Start with . Then consider . Then and so on.

Building on this let , be sets and . We are interested in the following question: Suppose that we know and . What can be said about ? The graph with vertex set is a Plunnecke graph and so we can apply Plunnecke’s graph theoretic inequality and get a nice bound on .

An interesting question is whether an elementary proof can be found. That is suppose that the ratio is minimal when . Can we prove in an elementary way that ? I can’t even start the induction. There is simply no reason to assume that for some the entire set is mapped into .

Take for example to be a basis for a free Abelian group and . Then for all , but for any $S\subseteq A$ . Finding a way round this would be nice, but I have been busy with other things.

February 24, 2011 at 12:24 pm

Dear George,

this comment is meant to be a reply to your last question, i.e. proving

for all additive sets , and such that every satisfies

.

Maybe you will not count the argument as being strictly “elementary”, and quite possibly you are already knowing about it, but I thought posting it might nevertheless be helpful to others who are seeking to find another proof which is closer in spirit to your argument described in Tim’s initial post.

So here comes the argument itself. First, construct a bijection from to itself such that whenever one has . This may be done using the minimality assumption on as well as the marriage theorem in more or less the same way as in a previous comment. Next we fix an arbitrary linear order on . Now we propose to construct an injective map from

into

.

For this purpose, take an arbitrary from , and write with , and such that is minimal with respect to our linear order imposed on . Note that is impossible, for then we had . Thus , whence we can look at . Observe that , which means that cannot hold as it implied $s=(t+b)=(t-x)+(x+b)\in B+E$, contrary to our assumption on . Therefore both of and belong to , wherefore we may define . To complete the proof we just have to check that is indeed injective, which is quite similar to the corresponding argument in a previous post. (It is here that one has to exploit the minimality of $b$ on which we have insisted on in our definition of .)

February 24, 2011 at 3:22 pm

This is very nice. I didn’t know about it. It seems that having the bijection you described does make a difference. I am not too surprised as your proof of

is different enough to the simple inductive argument. I am also not too surprised that Hall’s marriage theorem came up.

February 24, 2011 at 3:42 pm

Here is a slightly more general statement that more or less also comes out of the above proof but that might be more susceptible to a purely inductive treatment: Let , and be as above, and let be another additive set. Then we have

,

where

.

Have fun!

February 24, 2011 at 7:22 pm

Actually there is a quite easy inductive proof of the statement apperaing in George’s comment, the basic idea of which just occured to me while cooking. So let us once again suppose that , and are additive sets such that for all one has

.

Now I claim that for every the inequality

holds. Looking at the particular case answers George’s question, but we seem to need some parameter like in order to have something to which induction may be applied. To see the above statement, we argue by induction on .

Let us start with the case , say for simplicity. [Note that everything we do is invariant under translations.] Clearly

Applying the minimality of to in place of we obtain

.

Multiplying the first inequality by and using the second we infer

Subtracting the second term occuring at the left hand side, we arrive at

which is what we wanted to show.

Having thus disposed of the base case, we suppose now that the claim has already been shown for some and that we now seek to establish it for as well, where, again without loss of generality, . Setting it is not hard to see that

.

We multiply by and apply the minimality property of in order to conclude

.

Adding the induction hypothesis and subtracting the second term from the left hand side, we conclude

,

i.e.

,

which is what we wanted to prove.

February 24, 2011 at 7:32 pm

Basically the same idea should also work for the statement involving from two comments earlier, which might turn out to be useful for “iterations”.

February 25, 2011 at 1:33 am

More explicitely, if , and are as usual (by now), is arbitrary and is defined as above, then one can show by the induction on that every satisfies

In the particular case we may exploit so that we just have

Note that if we specialize this to , then

which means that in this case we get

$|A|\cdot |(A+nB)\setminus (E+(n-1)B)|\leqslant |(A+B)\setminus E|\cdot |(A+(n-1)B)\setminus ((n-2)B+E)|$.

Thus using induction on we finally arrive at a Petridis-style proof of

,

where .

February 25, 2011 at 8:52 am

Very nice Christian! Having an elementary proof of the statement is satisfying. I will need some extra time to digest your clever set operation manipulations and time is in premium right now. My impression is that proof is natural, which is an added bonus. By natural I mean one where each step is easily motivated.

February 25, 2011 at 9:22 pm

Guys,

Not sure whether I will ever have enough energy to read what you wrote on restricted sumsets (and, honestly, I may not feel truly motivated about them), but I certainly enjoyed Christian’s post with the elementary proof that is decreasing, and Georges’ proof that there exists

with . It is my understanding, however, that we still do not have a complete "elementary"

proof of either of the two inequalities that Antal and me mentioned; is this correct?

On this occasion, a minor linguistical remark. The term "restricted sumset" is usually meant to denote the set of all sums where , , and the pair satisfies some restriction, like . These sumsets are notoriously difficult to deal with.

Say, to my knowledge, no progress has been made on my ~10-year-old conjecture that if and are finite subsets of an abelian group with , then the restricted sumset of and , as defined above, contains at least elements. (This, I believe, is the restricted addition counterpart of the famous Kneser's theorem.)

February 25, 2011 at 10:23 pm

Ruzsa talks about restricted sums or restricted addition graphs. Mixing up the terminology is on me. Apologies.

No elementary proofs so far. I was too optimistic in one of my earlier replies!

What I find intriguing is that for distinct summands one knows what a good choice for is. Yet I can’t see how to make good use of this.

February 26, 2011 at 11:12 am |

Dear Seva,

it’s perfectly understandable that you don’t feel like reading those comments of mine, given that progress there evolves like a spiral. I just added ideas as I had them. Maybe I should rewrite the whole proof on estimating , putting some emphasis on its “naturality” in the sense George mentioned.

Regarding optimism: I still remain strongly convinced that it is both possible and worth while to “petridify” the whole area, i.e. both your as well as Balog’s question should have interesting answers. One should take into account that the approach involving Plünnecke graphs probably needed some time to develope too, so we shouldn’t be discouraged if it takes more than a few days from George’s brilliant discovery until more elementary proofs of more advanced results are found.

Finally I’d like to thank you for mentioning this highly interesting conjecture on what you call “restricted sumsets”. Among those questions that may be categorified as “Problems that arise since we don’t have a Combinatorial Nullstellensatz for general Abelian groups” it’s perhaps the most innocent looking one that I’ve ever seen.

February 26, 2011 at 8:06 pm

Right – I am not sure it is known even in this case! I actually have a paper on this conjecture (well, I exaggerate a little): http://math.haifa.ac.il/~seva/Papers/restcnj.dvi

February 26, 2011 at 5:56 pm |

Sorry, I think I have to take the last paragraph back, as now it seem to me that Seva’s problem is difficult even in the case where the ambient group is of the form .

February 26, 2011 at 8:07 pm

(My reply above was actually meant to be a reply to *this* post — sorry for the mess!)

March 3, 2011 at 12:49 pm |

In this comment, I am attempting to say more transparently how the restricted sum set estimate mentioned by George may be generalized and then be proved inductively. What we are attempting to do is the following: Suppose that and are additive sets and that is arbitrary. We may allow to be empty as well, in which special case the main argument to be found below reduces in an obvious way to George’s original proof of

for all under some appropriate assumption on and , as it is explained in Tim’s post. Having this extremal case in mind might to some extent be helpful in digesting what follows. Let us start to think about proving the existence of some such that

holds. In the spirit of George’s original argument, we may actually specify a set doing that, namely any non empty that minimizes the ratio . Our task is then to show that this minimality property of already entails the inequality we are just discussing. In order to save parameters, it is quite natural to suppose that itself minimizes this ratio, i.e. that every satisfies

It is under this assumption that we want to show

If we agree to write , this may restated as saying

.

In the long run, of course, we want to know considerably more, namely that for every positive integer we have

As in the original unrestricted case, we would like to show this by an easy induction on , where the induction step relies on the still more general estimate

that should be valid for all integers . In the case , George did this by introducing a new variable standing for there and then using induction on . If we attempt to do the same thing here, then it’s at first not clear what expression should replace the term . The perhaps most straightforward way around this difficulty is to let stand only for , so that we might start thinking about how to prove

.

The trouble we have to face then is that this inequality is not even easy in the case , for then it is just equivalent to the inequality we started our discussion with, whereas the whole point of introducing a new parameter has been to write something down that is utterly trivial whenever but that starts to get interesting if becomes larger. Thus we might wish to reconsider our option to take meaning . Then we need a sensible statement of the form

A+C$}|$,

that is allegedly valid for all additive sets . We will continue this line of thought in the next comment.

March 3, 2011 at 12:54 pm

Oups, the non-parsing formula is this:

,

where is supposed to denote some “useful” subset of that still remains to be specified, which we shall do next.

March 3, 2011 at 1:26 pm |

Now in order to proceed any further, we need to specify a sense of useful for which we obtain a statement that is at the same time true, inductively provable and implying what we want to know. It seems conceivable to me that there might be more than one way in which this can be done, so that there could in fact be several estimates of perhaps even incomparable strengthes awaiting to be discovered here. But at the time of writing this I can offer only one suggestion for replacing the estimate at the end of the previous comment by something precise, which may be motivated as follows: Recall that if should happen to be of the form for some additive set , then we want to remove from the set appearing at the right hand side at least all elements from . (As long as the statement we are about to formulate is still true, it is not problematic to remove even more elements from , for then we just end up getting a technically stronger result.) Now we cannot talk about in general, for which reason we should try to describe a property that applies to all elements of that can be understood without mentioning itself. If we think of as being something to which may be added in order to obtain , we may accomplish this by observing that every has the property . This thought leads us to defining

,

so that we might hope to prove

for any additive set . At this point I have to admit that all my attempts to prove this estimate by means of an induction on ended unsuccessfully, but I still cannot tell with certainty whether the reason for this has more to do with stupidity on my part or the very nature of the assertion itself. (The case is doable, but problems seem to arise at the induction step.) So the reader who has followed the discussion up to this point is encouraged to make an independent attempt of proving the above by induction on before he continues reading. Thinking about this problem for just a few minutes might in any case be helpful in order to find the next step we make a plausible one.

Let me try to describe what in my view makes the above estimate difficult to prove. The reason is that we do not have just two occurrences of , as in the situation that we could handle, but actually four. (Notice that the definition of involves the letter twice.) Moreover, whereas previously all occurrences of were increasing in the sense that the quantities which involved them became larger if was replaced by some $C\cup\{r\}$ in the induction step, we now have two increasing and two decreasing occurrences of . That is, if gets larger, then so does the term appearing on the left hand side, but at the same time grows and to describe the interaction between those to processes and the cancelations that are going on seems to be somewhat complicated. The very same phenomenon also takes place at the right hand side.

One way to deal with this problem is to regard the decreasing occurrences of as being fixed once and for all at the beginning and then to use induction only on the increasing occurrences of . That is, we fix our additive set from now on, take a new variable and hope to prove

for all ; one might expect that this can be done by induction on in a more or less straightforward way, and so it turns out to be.

March 3, 2011 at 6:03 pm

The difficulties I encountered when trying to prove the restricted sumset estimates were related with what you call increasing and decreasing occurrences of . So it is satisfying to have read the post.

March 3, 2011 at 2:24 pm |

We now come to the final comment in this series of three, in which we just record the proof of our claim made at the end of the previous one. Note that so far nothing beyond motivation has happened, which means that the actual argument we perform is much shorter than one might guess by just looking on the total length of these comments. To make the statement we prove entirely clear we would like restate it once more:

Suppose that additive sets and as well as a set are chosen in such a way that minimizes the ratio , which is intended to mean that every satisfies

Take an arbitrary additive set and stipulate

.

Then one has

,

More generally, every (possibly empty) subset of satisfies

.

In order to prove the latter statement, which we just regard as a technical strengthening of the former, we proceed by induction on . The case is obvious. For the induction step, we consider any about which we already know

,

take any , set and endeavour to show

.

For this purpose, we set

.

Let us consider any . Writing with and , we either have , in which case [Observe that this argument relies on belonging to ], so that in particular , or we have , in which case . Therefore

.

Further, if satisfies , then certainly . Using all this, we get

.

Multiplying by and adding the induction hypothesis, we infer

.

In view of the minimality condition imposed on , this may be weakened to

.

By our definition of , if some belongs to then the sum belongs to but not to . For this reason, we may rewrite the above estimate as

,

which completes the induction step.

March 3, 2011 at 4:22 pm

Let me add another little thought: The assumption is actually never used throughout this proof, so we should delete it. Observe that if we are just interested in George’s original version of his question, the distinction seems to be somewhat immaterial, but for the general--version stated above it does seem to make a difference. (Adding points outside to may cause both sides of the inequality we stated to decrease in a somewhat unforeseeable manner.) At the moment I believe that the extra generality we may gain in this manner could be important for applications.

March 3, 2011 at 4:44 pm |

Here’s a modest example of what I mean by this. Let , , and be additive sets and let be a further set (that may be assumed to be disjoint to ). Suppose that minimizes the ratio , i.e. that every satisfies

Then we have

.

Why? Setting , we already know a related estimate, where the second factor of the right hand side is replaced by , where

.

Now is clearly disjoint from , wherefore

,

so that our claim follows.

March 3, 2011 at 6:21 pm

Another thing that I want to point out – with some application in mind – is that under the same assumption on , , and we have

an estimate that more or less already appeared at the end of the first comment I wrote today, namely

.

The reason for this is simply that is disjoint to . (Once again it is not required that is a subset of .)

March 3, 2011 at 6:26 pm

That’s a nice result. I should also say that the restricted results may look technical, but are also very useful. Instead of an example I will point out that they generalise (or in some cases follow from) a very useful property of Plunnecke graphs. Suppose be a Plunnecke graph with vertex set and take and . The subgraph that consists of all paths that start in and finish in is also a Plunnecke graph.

March 4, 2011 at 1:48 am

Dear George,

something I failed to understand so far is whether results such as e.g. the estimate

$|A+2B+C|\leqslant \gamma|A+B+C|$

appearing in the next comment can also be shown by means of Plünnecke graphs. Or are the only known proofs of such results those that rely on your method?

March 4, 2011 at 9:30 am

I would need to think further about this. My initial reaction is that Plunnecke graphs are not strong enough to prove such statements. The fact that is arbitrary makes me say this. I could be wrong.

In any case I find your posts very interesting! The results seem powerful. Well done!

March 3, 2011 at 7:06 pm |

Let us now start to think about Balog’s problem, the easiest instance of which is this: Suppose that two additive sets and satisfy for some positive real number . Then there is some non empty such that

In accordance with George’s general approach one might hope to be able to take for this purpose any that minimizes the ratio . In other words, we add the hypothesis that for each we have

,

and then we hope to prove

.

Note that this then entails

for all integers .

[Why? By George’s theorem we have for all non negative integers , so we may apply induction on .]

An estimate that is still more general may be obtained by taking a further additive set . In perfect analogy with George’s line of thought we claim that

.

(Note that taking we obtain what we want.) Now I admittedly have been unable to verify this claim by induction on , but maybe someone else will succeed. (The case is not difficult, but the induction step seems to be hard.)

To convince ourselves of the truth of the above claim, we may instead argue like this: Take a maximal subset of that satisfies

.

(Such subsets do exist, e.g. has this property.) What we seek to prove is then , so assume that this was not the case. Setting

,

we then get , which means that cannot be empty.

Subclaim 1: .

Proof: Notice that our definition of entails

.

Thus if our subclaim failed, then taking a non empty subset of for which

is minimal, we had . Then the restricted sumset estimate, or rather the version of it that appears in the first reply to my previous comment, reveals

.

Adding this to

and taking the distributive law

into account, we infer that the set , which is strictly larger than by and , contradicts the maximality property of . This establishes our first subclaim.

Subclaim 2: . Adding these two inequalities, we get

,

which contradicts our definition of . Therefore our assumption must have been wrong, or in other words we have indeed

.

It seems conceivable that this may be generalized further.

March 3, 2011 at 7:17 pm

Apparently wordpress has swallowed large portions of the proof of the second subclaim for reasons I don’t quite understand, so here is the end of this comment again:

Subclaim 2: . Adding these two inequalities, we get

,

which contradicts our definition of . Therefore our assumption must have been wrong, or in other words we have indeed

.

March 3, 2011 at 7:27 pm

The improvement has been less impressive that I had hoped for, so here is a final attempt for today, which is TeX-nically somewhat simpler:

Subclaim 2: is less than .

Proof: Quite similarly, setting

we have

,

so if our subclaim failed, we could take some non empty for which the ratio

is minimal and then we had . Using the result from my previous comment with and here in place of and there, we obtain

.

Adding this to

we see that contradicts the maximality of . This proves the second subclaim.

Now note that by definition of , which tells us that . Thus our hypothesis on gives . Moreover, combining our two subclaims, we learn that is larger than . Adding these two inequalities, we infer that

is larger than $\gamma^2(|X|+|Y|)=\gamma^2|A|$,

which contradicts our definition of . Therefore our assumption must have been wrong, or in other words we have indeed

.

March 4, 2011 at 1:35 am |

In this comment, I attempt to answer Balog’s question.

Proposition. Let $n$ denote some positive integer, let , and be additive sets, and let be a further (possibly empty) set that is disjoint to . Choose a positive real number such that

and suppose that the inequality

holds for all . Then

.

Proof: We argue by induction on . The base case, , has already been considered in a previous comment. So suppose now that and that the statement under discussion is already known for in place of . Notice that if we would set , then

,

just for the simple reason that both sides vanished. Thus we can select some set with

that satisfies

,

and that is maximal with respect to that property. Set

and . Note that if , then and we are done, so assume from now on that this was not the case.

Subclaim 1: is less than .

Proof: By definition of we have

.

Now we choose some non empty such that

attains its minimal value, and observe that if our subclaim failed, then we had . Using the estimate from the first reply to the comment that appeared just before the previous one (is there any reasonable way for making such references?) with and here in place of and there, we infer

.

We would like to add this to

.

For this purpose, we observe that generally if , then

.

This principle may be applied here, as by construction. Thus setting , we get

,

which tells us that violates the maximality of . This contradiction proves our first subclaim.

Subclaim 2: is less than .

Proof: Set . This set may be supposed to be non empty, for otherwise the demand on entails what we want to know. Now if our subclaim failed, then in view of

,

the minimal value

that arises as varies through all non empty subsets of satisfies . Applying the induction hypothesis (recall that our proof is by induction on ) with and here in place of and there, we infer

.

Adding this to

we deduce in the same way as before that contradicts the maximality of . This completes the proof of our second subclaim.

Now everything is as before:

,

the first of these two terms is larger than by our two subclaims and the second one is at least by extremality of and . So altogether is larger than , and this contradiction proves our proposition.

Corollary 1. Let and be two additive sets such that and suppose that every satisfies

. Then one has for each additive set .

Proof: Just set in the proposition just obtained.

Corollary 2. If and are as above, then for all integers .

Proof: The case is clear, now use induction on . For the induction step observe that if , then substituting into the previous corollary, we get

.

Corollary 3. If and are additive sets and , then there is some non empty such that for every integer we have .

Proof: Take in such a way that is minimal and use the previous corollary.

March 12, 2011 at 5:44 pm |

I was going over a recent paper of Hamidoune (who, sadly, died unexpectedly last week) at

http://arxiv.org/abs/1006.5074

on non-commutative Freiman theorems in small characteristic and was struck by some similarities in his approach and those discussed here. The approach is based on isoperimetric inequalities for the

connectivity constantsand is based on an analysis of minimisers to those constants. Apart from dealing with minimising rather than , this looks quite similar. It may be worth looking into whether there is any deeper connection here…

March 12, 2011 at 6:05 pm

A correction: in the definition of , there is an additional constraint on Z needed to avoid degeneracy: one also needs ZB to not equal the entire group. (If the ambient group is infinite, then this additional condition is of course superfluous).

The key lemma is that after right-shifting B to contain the identity, then and have the same connectivity constant, and for at least one of these two sets, the connectivity is minimised by a subgroup H. (In most cases, is expected to be |B| and H is expected to be trivial, but when the doubling constant is strictly less than 2, dips below |B| and H becomes non-trivial.)

March 13, 2011 at 8:48 am

This is an interesting suggestion that merits a careful look.

By the way one suspects that Plunnecke’s inequality is not sharp unless and is a subgroup. For the time being I am getting used to the fact that `atoms’ play a role in group theory and not just physics or philosophy and so I can’t say whether Hamidoune’s approach can help in this regard. Probably not, but it is worth a try.

March 13, 2011 at 9:22 am

I should add that I am a 20th century creature and only now noticed the blogpost advertised below. The Freiman type result discussed there is presented in a very straightforward way.

March 12, 2011 at 10:17 pm |

[…] with the recent simple proof of the Ruzsa-Plünnecke inequality by Petridis (as discussed by Tim Gowers here), and this is what I would like to do below the fold. I also include (with permission) […]

March 30, 2011 at 10:49 pm |

A typo? Near the end, “such that |A+hB|\le K^h|B| for every…”

Shouldn’t it be \le K^h|A|?

August 26, 2012 at 9:23 pm |

[…] Menger’s theorem is no longer needed fro the graph inequalities. Gowers has posted the nice proof in his blog, with links to Petridis’s papers on the ArXiv. 43.614000 -116.202000 Like […]