A new way of proving sumset estimates

A very important role in additive combinatorics is played by the following theorem. If $A$ is a finite subset of $\mathbb{Z}$ , or indeed of any Abelian group, and if $|A+A|\leq C|A|$ , then for any non-negative integers $k$ and $l$ we have the estimate $|kA-lA|\leq C^{k+l}|A|.$ 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 $A_0$ and $B$ be two sets (soon it will be clear why this generalization is important in the proof) and suppose that $|A_0+B|\leq K_0|A_0|.$ Now choose a non-empty subset $A$ of $A_0$ such that the ratio $|A+B|/|A|$ is minimized and call this ratio $K.$ Then we have the following two statements:

$|A+B|=K|A|;$
$|Z+B|\geq K|Z|$ for every $Z\subset A.$

To prove the sumset estimates it is sufficient to prove the following statement.

Lemma. Let $A$ and $B$ be as above. Then for every set $C$ we have the inequality $|A+B+C|\leq K|A+C|.$

Once we have this statement, then we can prove by induction that $|A+hB|\leq K^h|A|$ . Indeed, when $h=1$ we have equality, and for larger $h$ we can set $C=(h-1)B$ to deduce that $|A+hB|\leq K|A+(h-1)B|,$ which is clearly enough. Note also that since $K\leq K_0,$ it follows from this that

$|hB|\leq|A+hB|\leq K^h|A|\leq K^h|A_0|\leq K_0^h|A_0|.$

Therefore, (taking $A_0=B$ ) we already have the result that if $|B+B|\leq\alpha|B|,$ then $|hB|\leq\alpha^h|B|.$ 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 $C$ (or perhaps it is nicer to call it induction on $C$ itself). If $C$ is a singleton $\{x\}$ then the lemma claims that $|A+B+x|\leq K|A+x|,$ which is true because the left-hand side is $|A+B|$ and the right-hand side is $K|A|,$ and the inequality $|A+B|\leq K|A|$ is one of our starting assumptions.

Now let us suppose that we know that $|A+B+C|\leq K|A+C|$ and we want to prove the result for $C'=C\cup\{x\}.$ Obviously we know that

$A+B+C'=(A+B+C)\cup(A+B+x),$

from which it follows that

$|A+B+C'|\leq |A+B+C|+|A+B|\leq K|A+C|+K|A|.$

However, this is not good enough, as we do not know that $|A+C|+|A|\leq |A+C'|.$ Indeed, this will be the case only if $A+x$ is disjoint from $A+C.$ But there was a significant inefficiency in the above argument, since we can replace the first statement by

$A+B+C'=(A+B+C)\cup((A+B+x)\setminus(Z+B+x)),$

where $Z$ is the set of all $a\in A$ such that $a+B+x\subset A+B+C$ . And here we can use our second assumption, which tells us that $|Z+B|\geq K|Z|.$ Incorporating that information (and using the fact that $Z+B+x\subset A+B+x$ ) we find that

$|A+B+C'|\leq |A+B+C|+|A+B|-|Z+B|$
$\leq K(|A+C|+|A|-|Z|).$

It remains to prove that $|A+C|+|A|-|Z|\leq |A+C'|.$ But
$A+C'=(A+C)\cup((A+x)\setminus(W+x)),$
where $W$ is the set of all $a\in A$ such that $a+x\in A+C.$ Moreover, this is a disjoint union, and $W+x\subset A+x.$ It follows that
$|A+C'|=|A+C|+|A|-|W|.$
But if $a+x\in A+C,$ then $a+B+x\subset A+B+C,$ so $W\subset Z,$ so we can deduce that
$|A+C'|\geq|A+C|+|A|-|Z|,$
as required. $\square$

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:

$|U||V-W|\leq |U+V||U+W|.$

That holds for any three sets $U,V$ and $W.$ It is easily proved by defining a map $\phi:U\times(V-W)\to (U+V)\times(U+W)$ by taking $(u,x)$ to $(u+v(x),u+w(x)),$ where $v(x)$ and $w(x)$ are chosen such that $v(x)-w(x)=x.$ One then checks that this map is an injection.

Recall that so far we have proved that if $|A_0+B|\leq K_0|A_0|$ then there exists $A\subset A_0$ and $K\leq K_0$ such that $|A+hB|\leq K^h|B|$ for every $h.$ (Incidentally, the fact that $A$ does not depend on $h$ seems to be a novel feature of Petridis’s argument.) From Ruzsa’s triangle inequality it follows that

$|A||kB-lB|\leq|A+kB||A+lB|\leq K^{k+l}|A|^2,$

and from that we get that $|kB-lB|\leq K^{k+l}|A|.$ In particular, if $A_0=B$ then we can deduce that $|B+B|\leq K|B|$ implies that $|kB-lB|\leq K^{k+l}|B|.$

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.

59 Responses to “A new way of proving sumset estimates”

gowers Says:
February 10, 2011 at 12:13 pm | Reply
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 $|A+B|\leq K|A|$ and want to prove that $|A+hB|\leq K^h|A|.$ An obvious approach is induction on $h.$ And that leads very naturally to the following conjecture: if $|A+B|\leq K|A|$ then $|A+B+C|\leq K|A+C|$ for every $C,$ which we hope to apply with $C=(h-1)B.$

Now we have the idea of using induction on $C$ (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 $|Z+B|.$ But then you realize you can obtain that control if you begin by passing to a subset of $A$ such that the ratio $|A+B|/|A|$ 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.
507- Plünnecke inequalities and sumset estimates « Teaching blog Says:
February 10, 2011 at 4:03 pm | Reply
[…] 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 […]
Ernie Croot Says:
February 10, 2011 at 4:16 pm | Reply
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.
gowers Says:
February 10, 2011 at 10:25 pm | Reply
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
$A+C'=(A+C)\cup((A+x)\setminus(W+x)),$
where $W,$ as before, is the set of all $a\in A$ such that $a+x\in A+C.$ As before, this is a disjoint union and $W\subset A.$ Therefore
$|A+C'|=|A+C|+|A|-|W|.$
But $W+x\subset A+C,$ so $W+B+x\subset A+B+C,$ from which it follows that
$A+B+C'\subset (A+B+C)\cup((A+B+x)\setminus(W+B+x))$
and therefore that
$|A+B+C'|\leq|A+B+C|+|A+B|-|W+B|.$
The minimality of $|A+B|/|A|$ and the inductive hypothesis imply that this is at most $K(|A+C|+|A|-|W|)=K|A+C'|.$
Terence Tao Says:
February 11, 2011 at 12:00 am | Reply
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 $A \mapsto A+B$ , one can consider a more general map $A \mapsto \phi(A)$ from finite sets to finite sets, which respects unions: $\phi(A \cup A') = \phi(A) \cup \phi(A')$ (in particular, $\phi$ is monotone). As a corollary of this and inclusion-exclusion, one obtains the submodularity inequality

$|\phi(A \cup A')| + |\phi(A \cap A')| \leq |\phi(A)| + |\phi(A')|$

for any $A,A'$ . In particular, if we set $c(A) := |\phi(A)|-K|A|$ for any fixed K, we have

$c(A \cup A') + c(A \cap A') \leq c(A) + c(A')$ .

The abstract version of the lemma is then: if $A_1,\ldots,A_n$ are a sequence of finite sets such that $|\phi(A_i)| = K |A_i|$ and $|\phi(Z_i)| \geq K|Z_i|$ for all $i=1,\ldots,n$ and $Z_i \subset A_i$ , then $|\phi(\bigcup_{i=1}^n A_i)| \leq K |\bigcup_{i=1}^n A_i|$ . Indeed, by construction, $c(A_i)=0$ and $c(Z_i) \leq 0$ for any $Z_i \subset A_i$ , thus $c(A_i \cup B) \leq c(B)$ for any $B$ , and thus $c(\bigcup_{i=1}^n A_i) \leq 0$ .

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.)
- gowers Says:
  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 $|kA-lA|/|A|$ in terms of the size of $|A+A|/|A|.$ 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.
- Terence Tao Says:
  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.))
valuevar Says:
February 11, 2011 at 12:51 pm | Reply
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)?
- Breuillard Says:
  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).
Todd Cochrane Says:
February 14, 2011 at 8:03 pm | Reply
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.
Seva Says:
February 20, 2011 at 9:03 pm | Reply
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 $A,B_1,...,B_n$ of an abelian group with $|A+B_i|\le K_i|A|$ , there exists a non-empty subset $A_0\subseteq A$ such that

$|A_0+B_1+...+B_n| \le K_1...K_n |A_0|.$

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?
- gowers Says:
  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 $h<k$ and $|A+kB|\leq C^k|A|$ then there exists $A'\subset A$ such that $|A'+hB|\leq C^h|A'|.$ 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.
- Seva Says:
  February 21, 2011 at 8:23 am
  Exactly — this inequality with $|A'+hB|<C^h|A'|$ pointed out by Balog was another thing I also had in mind!
- Petridis Says:
  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 $C$ . 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 $A+B$ 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 $A$ appropriately. Nor is any graph theory. In fact, Tim’s first comment is a much more natural path to choosing $A$ . 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.
Sumset Estimates « Blame It On The Analyst Says:
February 21, 2011 at 4:02 pm | Reply
[…] 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 […]
Christian Says:
February 22, 2011 at 1:34 pm | Reply
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 $A$ is excellent for $B$ if it minimizes the ratio $|A+B|/|A|$ , i.e. if for every $Z\subseteq A$ one has $|Z+B|\cdot |A|\geqslant |Z|\cdot |A+B|$ .

Now it is not hard to observe that “ $A$ is excellent for $B$ ” is equivalent to the existence of a bijection $\varphi$ from $A\times (A+B)$ to itself such that if $\varphi(r, s)=(x, y)$ then $y-r\in B$ .

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

The main Lemma, asserting that if $A$ is excellent for $B$ , then for each $C$ one has $|A|\cdot |A+B+C|\leqslant |A+B|\cdot |A+C|$ can now be proved by exhibiting an injective map from $A\times (A+B+C)$ to $(A+B)\times (A+C)$ , as follows: Impose an arbitrary linear oreder on $C$ and fix any bijection $\varphi$ as above. Now given an arbitray element $(a, s)$ from $A\times (A+B+C)$ , write $s=t+c$ with $t\in A+B$ and $c\in C$ such that $c$ is minimal in the sense of the linear order we have chosen for $C$ . Let $\varphi^{-1}(a, t)=(x, y)$ and let $(y, x+c)$ be the image of $(a, s)$ in $(A+B)\times (A+C)$ . Let us check that this map is indeed injective, as we need it to be. For this purpose, let $(a', s')$ be another element of $A\times (A+B+C)$ , define $t'$ , $c'$ , $x'$ and $y'$ in the expected way and suppose that $y=y'$ as well as $x+c=x'+c'$ . We have to show that $a=a'$ and $s=s'$ . Assume that we had $c\ne c'$ . Then without loss of generality $c$ is smaller than $c'$ in the linear order on $C$ . Note that $s’=t’+c’=t’-x’+x’+c’=x+(t’-x’)+c$. Note that $x\in A$ , $t'-x'\in B$ (since $\varphi(x', y')=(a', t')$ ), and $c\in C$ . Thus in decomposing $s'$ in order to carry the above definition out, we could have chosen $c$ instead of $c'$ , and in fact we should have done so as $c$ is smaller than $c'$ . This contradiction establishes $c=c'$ , so by the hypothesis $x+c=x'+c'$ also get $x=x'$ . Applying $\varphi$ to the equality $(x, y)=(x', y')$ we infer $(a, t)=(a', t')$ . For this reason we have $a=a'$ and $s=t+c=t'+c'=s'$ , as claimed.
- Christian Says:
  February 23, 2011 at 7:01 pm
  Another perhaps interesting problem is this: Recall that if $A$ is excellent for either $B$ or $C$ , then $|A|\cdot |A+B+C|\leqslant |A+B|\cdot |A+C|$ . But now suppose that $A$ is excellent for $B+C$ . Prove in a way that is as interesting as possible that then we also have $|A|\cdot |A+B+C|\leqslant |A+B|\cdot |A+C|$ . (I’m not satisfied with my own proof, so I’m not mentioning it here.)
Petridis Says:
February 22, 2011 at 4:34 pm | Reply
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 $A^\prime$ is found such that $|A^\prime +hB|\leq K^h|A^\prime|$ holds for all $h$ . There is an equivalent stronger statement for Plunnecke graphs. Suppose that the vertex set of the graph is $V_0,\dots ,V_h$ and that $X\subseteq V_0$ is such that the (“directed”) neighborhood of $X$ has size $D_1 |X|$ . Then the image of $X$ in $V_h$ has size at most $D_1^h |X|$ . This can be deduced from the traditional form of Plunnecke’s inequality by induction on $|V_0|$ [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.
Petridis Says:
February 22, 2011 at 4:42 pm | Reply
Balog’s question has a special case that is interesting in its own right. Suppose that $A$ is a singleton. Then $A+hB$ has the same size as $hB$ . The question then becomes: is there an elementary proof that $|hA|^{1/h}$ 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.
- Christian Says:
  February 23, 2011 at 11:52 am
  This particular case, i.e. monotonicity of $|hB|^{1/h}$ seems to have a rather easy elementary proof, which is as follows. Recall that Gyarmati, Matolcsi and Ruzsa have shown that if $B_1, B_2, \ldots, B_n$ are additive sets and if one sets
  
  $S=B_1+B_2+\ldots+B_n$
  
  as well as
  
  $S_i=B_1+\ldots+B_{i-1}+B_{i+1}+\ldots+B_n$
  
  for $i=1, 2, \ldots, n$ , then
  
  $|S|^{n-1}\leqslant |S_1|\cdot|S_2|\cdot\ldots\cdot|S_n$ .
  
  (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 $B_i=B$ for all $i=1, 2, \ldots, n$ , then we get
  
  $|nB|^{n-1}\leqslant |(n-1)B|^n$ ,
  
  which means that we have indeed
  
  $|nB|^{1/n}\leqslant |(n-1)B|^{1/(n-1)}$ .
- Petridis Says:
  February 23, 2011 at 5:34 pm
  This is indeed very nice.
Petridis Says:
February 22, 2011 at 5:28 pm | Reply
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 $h=2$ and $K_1, K_2 \in \mathbb{Z}$ . We let $B=B_1\cup B_2$ and $K=K_1 K_2$ . Consider the Cartesian product of the underlying group with cyclic groups $C_1$ and $C_2$ of size respectively $K_2$ and $K_1$ . Then let $A^\prime = A\times\{0\}\times\{0\}$ , $B_1^\prime = B_1\times C_1 \times \{0\}$ , $B_2^\prime \{0\}\times C_2$ and $B^\prime= B_1^\prime \cup B_2^\prime$ . Observe that $|A^\prime + B^\prime|\leq K_2 |A+B_1| + K_1 |A+B_2|= 2 K |A^\prime|$ . So by the Plunnecke-Ruzsa inequality there exists $A_0^\prime \subseteq A^\prime$ such that $|A_0^\prime + 2B^\prime|\leq 4 K^2 |A_0^\prime|= 4 K^2 |A_0|$ . Now simply observe that $(A_0+B_1+B_2)\times C_1\times C_2 \subseteq A_0^\prime+2B^\prime$ . The size of the left hand side is $K|A_0+B_1+B_2|$ and we have therefore proved $|A_0+B_1+B_2|\leq 4K|A_0|$ . 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 $|A_0+B_1+B_2|$ can be derived from it. The above proof suggests that the $A_0$ we want to choose is one that minimizes the ratio $(K_1 |Z+B_2| + K_2 |Z+B_1|)/|Z|$ over all $Z\subseteq A$ . I don’t know how to use this effectively, but am happy to share the little intuition I have.
- Christian Says:
  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 $X'$ living in some $A^k$ , and then one has to argue that $X'$ may actually be taken to be of the form $X^k$ for some appropriate $X\subseteq A$ . 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.
Petridis Says:
February 22, 2011 at 5:56 pm | Reply
Time to define Ruzsa’s restricted sumsets. These are useful when one tries to find good bounds on $|A+hB|$ for two general sets $A$ and $B$ . A good way to bound $|A+hB|$ is to partition $A+B$ in sets $E_1,\dots,E_k$ and bound $|A+hB|$ b the sum of the $|E_i+(h-1)B|$ . This is an overly generous approach and it is better to proceed like in the proof of the lemma. Start with $E_1+(h-1)B$ . Then consider $(E_2+(h-1)B)\backslash (E_1+(h-1)B)$ . Then $(E_3+(h-1)B)\backslash ((E_1\cup E_2)+(h-1)B)$ and so on.

Building on this let $A$ , $B$ be sets and $E \subset A+B$ . We are interested in the following question: Suppose that we know $|A|$ and $|(A+B)\backslash E|$ . What can be said about $|(A+hB)\backslash (E+(h-1)B)|$ ? The graph with vertex set $(A+iB)\backslash (E+(i-1)B)$ is a Plunnecke graph and so we can apply Plunnecke’s graph theoretic inequality and get a nice bound on $|A+hB|$ .

An interesting question is whether an elementary proof can be found. That is suppose that the ratio $|(Z+B)\backslash E|/|Z|$ is minimal when $Z=A$ . Can we prove in an elementary way that $|A| \,|(A+2B)\backslash(E+B)|\leq |(A+B)\backslash E|^2$ ? I can’t even start the induction. There is simply no reason to assume that for some $b\in B$ the entire set $A$ is mapped into $(A+B)\backslash E$ .

Take for example $A=B=\{\gamma_1,\dots,\gamma_n\}$ to be a basis for a free Abelian group and $E=\{2\gamma_i : 1\leq i \leq n\}$ . Then $|(\gamma_i+A)\backslash E|<|A|$ for all $i$ , but for any $S\subseteq A$ $|(S+A)\backslash E| /|S| = |A|-(|S|+1)/2$ . Finding a way round this would be nice, but I have been busy with other things.
- Christian Says:
  February 24, 2011 at 12:24 pm
  Dear George,
  this comment is meant to be a reply to your last question, i.e. proving
  
  $|A|\cdot |(A+2B)\setminus (E+B)|\leqslant |(A+B)\setminus E|^2$
  
  for all additive sets $A$ , $B$ and $E\subseteq A+B$ such that every $Z\subseteq A$ satisfies
  $|Z|\cdot |(A+B)\setminus E|\leqslant |A|\cdot |(Z+B)\setminus E|$ .
  
  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 $\varphi$ from $A\times ((A+B)\setminus E)$ to itself such that whenever $\varphi(a, s)=(x, y)$ one has $(y-a)\in B$ . This may be done using the minimality assumption on $A$ 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 $B$ . Now we propose to construct an injective map $\psi$ from
  
  $|A\times ((A+2B)\setminus (E+B))|$
  
  into
  
  $((A+B)\setminus E)\times ((A+B)\setminus E)$ .
  
  For this purpose, take an arbitrary $(a, s)$ from $|A\times ((A+2B)\setminus (E+B))|$ , and write $s=t+b$ with $t\in A+B$ , $b\in B$ and such that $b$ is minimal with respect to our linear order imposed on $B$ . Note that $t\in E$ is impossible, for then we had $s\in E+B$ . Thus $t\in (A+B)\setminus E$ , whence we can look at $\varphi^{-1}(a, t)=(x, y)$ . Observe that $t-x\in B$ , which means that $(x+b)\in E$ cannot hold as it implied $s=(t+b)=(t-x)+(x+b)\in B+E$, contrary to our assumption on $s$ . Therefore both of $y$ and $x+b$ belong to $(A+B)\setminus E$ , wherefore we may define $\psi(a, s)=(y, x+b)$ . To complete the proof we just have to check that $\psi$ 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 $\psi$ .)
- Petridis Says:
  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
  $|A| |A+B+C| \leq |A+B| |A+C|$
  is different enough to the simple inductive argument. I am also not too surprised that Hall’s marriage theorem came up.
- Christian Says:
  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 $A$ , $B$ and $E$ be as above, and let $C$ be another additive set. Then we have
  
  $|A|\cdot |(A+B+C)\setminus (C+E)|\leqslant |(A+B)\setminus E|\cdot |Q|$ ,
  
  where
  
  $Q=\{q\in A+C\,|\, q+B\not\subseteq C+E\}$ .
  
  Have fun!
- Christian Says:
  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 $A$ , $B$ and $E\subseteq A+B$ are additive sets such that for all $Z\subseteq A$ one has
  
  $|Z|\cdot |(A+B)\setminus E|\leqslant |A|\cdot |(Z+B)\setminus E|$ .
  
  Now I claim that for every $C\subset B$ the inequality
  
  $|A|\cdot |(A+B+C)\setminus (B+E)|\leqslant |(A+B)\setminus E|\cdot |(A+C)\setminus E|$
  
  holds. Looking at the particular case $B=C$ answers George’s question, but we seem to need some parameter like $C$ in order to have something to which induction may be applied. To see the above statement, we argue by induction on $C$ .
  
  Let us start with the case $|C|=1$ , say $C=\{0\}$ for simplicity. [Note that everything we do is invariant under translations.] Clearly
  
  $|(A+B)\setminus (B+E)|+|((A\cap E)+B)\setminus E|\leqslant |(A+B)\setminus E|.$
  
  Applying the minimality of $A$ to $A\cap E$ in place of $Z$ we obtain
  
  $|A\cup E|\cdot |(A+B)\setminus E|\leqslant |A|\cdot |(A\cup E)+B)\setminus E|$ .
  
  Multiplying the first inequality by $|A|$ and using the second we infer
  
  $|A|\cdot |(A+B)\setminus (B+E)|+ |A\cup E|\cdot |(A+B)\setminus E|\leqslant |A|\cdot |(A+B)\setminus E|.$
  
  Subtracting the second term occuring at the left hand side, we arrive at
  
  $|A|\cdot |(A+B)\setminus (B+E)|\leqslant |A\setminus E|\cdot |(A+B)\setminus E|,$
  
  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 $C\subsetneqq B$ and that we now seek to establish it for $C'=C\cup \{0\}$ as well, where, again without loss of generality, $0\in B\setminus C$ . Setting $Z=A\cap ((A+C)\cup E)$ it is not hard to see that
  
  $|(A+B)\setminus ((A+B+C)\cup (B+E))|+|(Z+B)\setminus E|\leqslant |(A+B)\setminus E|$ .
  
  We multiply by $|A|$ and apply the minimality property of $A$ in order to conclude
  
  $|A|\cdot |(A+B)\setminus ((A+B+C)\cup (B+E))|+latex |Z|\cdot |(A+B)\setminus E|\leqslant |A|\cdot |(A+B)\setminus E|$ .
  
  Adding the induction hypothesis and subtracting the second term from the left hand side, we conclude
  
  $|A|\cdot |(A+B+C)\setminus (B+E)|\leqslant |(A+B)\setminus E|\cdot(|A|-|Z|+|(A+C)\setminus E|)$ ,
  
  i.e.
  
  $|A|\cdot |(A+B+C)\setminus (B+E)|\leqslant |(A+B)\setminus E|\cdot |(A+C')\setminus E|$ ,
  
  which is what we wanted to prove.
- Christian Says:
  February 24, 2011 at 7:32 pm
  Basically the same idea should also work for the statement involving $Q$ from two comments earlier, which might turn out to be useful for “iterations”.
- Christian Says:
  February 25, 2011 at 1:33 am
  More explicitely, if $A$ , $B$ and $E$ are as usual (by now), $C$ is arbitrary and $Q$ is defined as above, then one can show by the induction on $D$ that every $D\subseteq C$ satisfies
  
  $|A|\cdot |(A+B+D)\setminus (C+E)|\leqslant |(A+B)\setminus E|\cdot |(A+D)\cap Q|.$
  
  In the particular case $C=D$ we may exploit $Q\subseteq A+C$ so that we just have
  
  $|A|\cdot |(A+B+C)\setminus (C+E)|\leqslant |(A+B)\setminus E|\cdot |Q|.$
  
  Note that if we specialize this to $C=(n-1)B$ , then
  
  $Q\subseteq (A+(n-1)B)\setminus ((n-2)B+E),$
  
  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 $n$ we finally arrive at a Petridis-style proof of
  
  $|(A+nB)\setminus (E+(n-1)B)|\leqslant K^n\cdot |A|$ ,
  
  where $K=|(A+B)\setminus E|/|A|$ .
- Petridis Says:
  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.
- Seva Says:
  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 $|hA|^{1/h}$ is decreasing, and Georges’ proof that there exists
  $A_0\subset A$ with $|A_0+B_1+B_2|<4K_1K_2|A_0|$ . 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 $a+b$ where $a\in A$ , $b\in B$ , and the pair $(a,b)$ satisfies some restriction, like $a\ne b$ . 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 $A$ and $B$ are finite subsets of an abelian group with $A\cap(-B)=\{0\}$ , then the restricted sumset of $A$ and $B$ , as defined above, contains at least $|A|+|B|-3$ elements. (This, I believe, is the restricted addition counterpart of the famous Kneser's theorem.)
- Petridis Says:
  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 $A_0$ is. Yet I can’t see how to make good use of this.
Christian Says:
February 26, 2011 at 11:12 am | Reply
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 $(A+nB)\setminus (E+(n-1)B)$ , 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.
- Seva Says:
  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
Christian Says:
February 26, 2011 at 5:56 pm | Reply
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 $\mathbb{F}_p^n$ .
- Seva Says:
  February 26, 2011 at 8:07 pm
  (My reply above was actually meant to be a reply to *this* post — sorry for the mess!)
Christian Says:
March 3, 2011 at 12:49 pm | Reply
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 $A$ and $B$ are additive sets and that $E\subseteq A+B$ is arbitrary. We may allow $E$ 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

$|A|^{n-1}\cdot |A+nB|\leqslant |A+B|^n$

for all $n$ under some appropriate assumption on $A$ and $B$ , 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 $X\subseteq A$ such that

$|X|\cdot |(X+2B)\setminus (E+B)|\leqslant |(X+B)\setminus E|^2$

holds. In the spirit of George’s original argument, we may actually specify a set $X$ doing that, namely any non empty $X$ that minimizes the ratio $|(X+B)\setminus E|/|X|$ . Our task is then to show that this minimality property of $X$ already entails the inequality we are just discussing. In order to save parameters, it is quite natural to suppose that $A$ itself minimizes this ratio, i.e. that every $Z\subseteq A$ satisfies

$|Z|\cdot |(A+B)\setminus E|\leqslant |A|\cdot |(Z+B)\setminus E|.$

It is under this assumption that we want to show

$|A|\cdot |(A+2B)\setminus (E+B)|\leqslant |(A+B)\setminus E|^2.$

If we agree to write $\kappa=|(A+B)\setminus E|/|A|$ , this may restated as saying

$|(A+2B)\setminus (E+B)|\leqslant\kappa^2|A|$ .

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

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

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

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

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

$|(A+2B+C)\setminus(E+B+C)|\leqslant\kappa |(A+B+C)\setminus (E+C)|$ .

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

$|(A+B+C)\setminus(E+C)|\leqslant\kappa\cdot |\textnormal{Some "useful" subset of$ A+C$}|$,

that is allegedly valid for all additive sets $C$ . We will continue this line of thought in the next comment.
- Christian Says:
  March 3, 2011 at 12:54 pm
  Oups, the non-parsing formula is this:
  
  $|(A+B+C)\setminus(E+C)|\leqslant\kappa\cdot |Q(C)|$ ,
  
  where $Q(C)$ is supposed to denote some “useful” subset of $A+C$ that still remains to be specified, which we shall do next.
Christian Says:
March 3, 2011 at 1:26 pm | Reply
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 $C$ should happen to be of the form $T+B$ for some additive set $T$ , then we want to remove from the set $A+C=A+B+T$ appearing at the right hand side at least all elements from $E+T$ . (As long as the statement we are about to formulate is still true, it is not problematic to remove even more elements from $A+C$ , for then we just end up getting a technically stronger result.) Now we cannot talk about $T$ in general, for which reason we should try to describe a property that applies to all elements of $E+T$ that can be understood without mentioning $T$ itself. If we think of $T$ as being something to which $B$ may be added in order to obtain $C$ , we may accomplish this by observing that every $q\in E+T$ has the property $q+B\subseteq E+C$ . This thought leads us to defining

$Q(C)=\{q\in A+C\,|\, q+B\nsubseteq E+C\}$ ,

so that we might hope to prove

$|(A+B+C)\setminus(E+C)|\leqslant\kappa\cdot |Q(C)|$

for any additive set $C$ . At this point I have to admit that all my attempts to prove this estimate by means of an induction on $C$ 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 $|C|=1$ 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 $C$ 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 $C$ , as in the situation $E=\varnothing$ that we could handle, but actually four. (Notice that the definition of $Q(C)$ involves the letter $C$ twice.) Moreover, whereas previously all occurrences of $C$ were increasing in the sense that the quantities which involved them became larger if $C$ was replaced by some $C\cup\{r\}$ in the induction step, we now have two increasing and two decreasing occurrences of $C$ . That is, if $C$ gets larger, then so does the term $A+B+C$ appearing on the left hand side, but at the same time $E+C$ 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 $C$ as being fixed once and for all at the beginning and then to use induction only on the increasing occurrences of $C$ . That is, we fix our additive set $C$ from now on, take a new variable $D$ and hope to prove

$|(A+B+D)\setminus(E+C)|\leqslant\kappa\cdot |(A+D)\cap Q(C)|$

for all $D\subseteq C$ ; one might expect that this can be done by induction on $D$ in a more or less straightforward way, and so it turns out to be.
- Petridis Says:
  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 $C$ . So it is satisfying to have read the post.
Christian Says:
March 3, 2011 at 2:24 pm | Reply
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 $A$ and $B$ as well as a set $E\subseteq A+B$ are chosen in such a way that $A$ minimizes the ratio $|(A+B)\setminus E|/|A|$ , which is intended to mean that every $Z\subseteq A$ satisfies

$|Z|\cdot |(A+B)\setminus E|\leqslant |A|\cdot |(Z+B)\setminus E|.$

Take an arbitrary additive set $C$ and stipulate

$Q(C)=\{q\in A+C\,|\, q+B\nsubseteq E+C\}$ .

Then one has

$|A|\cdot |(A+B+C)\setminus(E+C)|\leqslant |(A+B)\setminus E|\cdot |Q(C)|$ ,

More generally, every (possibly empty) subset $D$ of $C$ satisfies

$|A|\cdot |(A+B+D)\setminus(E+C)|\leqslant |(A+B)\setminus E|\cdot |(A+D)\cap Q(C)|$ .

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

$|A|\cdot |(A+B+D)\setminus(E+C)|\leqslant |(A+B)\setminus E|\cdot |(A+D)\cap Q(C)|$ ,

take any $r\in C\setminus D$ , set $D'=D\cup\{r\}$ and endeavour to show

$|A|\cdot |(A+B+D')\setminus(E+C)|\leqslant |(A+B)\setminus E|\cdot |(A+D')\cap Q(C)|$ .

For this purpose, we set

$Z=\{a\in A\,|\, a+r\not\in Q(C)\vee a+r\in A+D\}$ .

Let us consider any $s\in Z+B$ . Writing $s=a+b$ with $a\in Z$ and $b\in B$ , we either have $a+r\not\in Q(C)$ , in which case $a+B+r\subseteq E+C$ [Observe that this argument relies on $r$ belonging to $C$ ], so that in particular $s+r\in E+C$ , or we have $a+r\in A+D$ , in which case $s+r\in A+B+D$ . Therefore

$Z+B\subseteq \{s\in A+B\,|\, s+r\in (E+C)\cup (A+B+D)\}$ .

Further, if $s\in A+B$ satisfies $s+r\not\in E+C$ , then certainly $s\not\in E$ . Using all this, we get

$|(A+B+D')\setminus((A+B+D)\cup (E+C))|+|(Z+B)\setminus E|\leqslant |(A+B)\setminus E|$ .

Multiplying by $|A|$ and adding the induction hypothesis, we infer

$|A|\cdot |(A+B+D')\setminus(E+C)|+|A|\cdot |(Z+B)\setminus E|\leqslant |(A+B)\setminus E|\cdot (|A|+|(A+D)\cap Q(C)|)$ .

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

$|A|\cdot |(A+B+D')\setminus(E+C)|\leqslant |(A+B)\setminus E|\cdot (|A|-|Z|+|(A+D)\cap Q(C)|)$ .

By our definition of $Z$ , if some $a$ belongs to $A\setminus Z$ then the sum $a+r$ belongs to $Q(C)$ but not to $A+D$ . For this reason, we may rewrite the above estimate as

$|A|\cdot |(A+B+D')\setminus(E+C)|\leqslant |(A+B)\setminus E|\cdot (|(A+D')\cap Q(C)|)$ ,

which completes the induction step.
- Christian Says:
  March 3, 2011 at 4:22 pm
  Let me add another little thought: The assumption $E\subseteq A+B$ 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- $C$ -version stated above it does seem to make a difference. (Adding points outside $A+B$ to $E$ 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.
Christian Says:
March 3, 2011 at 4:44 pm | Reply
Here’s a modest example of what I mean by this. Let $A$ , $B$ , and $C$ be additive sets and let $J$ be a further set (that may be assumed to be disjoint to $A$ ). Suppose that $A$ minimizes the ratio $|(A+B)\setminus (J+B)|/|A|$ , i.e. that every $Z\subseteq A$ satisfies

$|Z|\cdot |(A+B)\setminus (J+B)|\leqslant |A|\cdot |(Z+B)\setminus (J+B)|.$

Then we have

$|A|\cdot |(A+B+C)\setminus (J+B+C)|\leqslant |(A+B)\setminus (J+B)|\cdot |(A+C)\setminus(J+C)|$ .

Why? Setting $E=J+B$ , we already know a related estimate, where the second factor of the right hand side is replaced by $|Q(C)|$ , where

$Q(C)=\{q\in A+C\,|\, q+B\nsubseteq J+B+C\}$ .

Now $Q(C)$ is clearly disjoint from $J+C$ , wherefore

$Q(C)\subseteq (A+C)\setminus(J+C)$ ,

so that our claim follows.
- Christian Says:
  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 $A$ , $B$ , $C$ and $E$ we have
  an estimate that more or less already appeared at the end of the first comment I wrote today, namely
  $|A|\cdot |(A+2B+C)\setminus(E+B+C)|\leqslant|(A+B)\setminus E|\cdot|(A+B+C)\setminus (E+C)|$ .
  
  The reason for this is simply that $Q(B+C)$ is disjoint to $E+C$ . (Once again it is not required that $E$ is a subset of $A+B$ .)
- Petridis Says:
  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 $G$ be a Plunnecke graph with vertex set $V_0\cup\dots\cup V_h$ and take $X\subseteq V_0$ and $Y\subseteq V_h$ . The subgraph that consists of all paths that start in $X$ and finish in $Y$ is also a Plunnecke graph.
- Christian Says:
  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?
- Petridis Says:
  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 $C$ 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!
Christian Says:
March 3, 2011 at 7:06 pm | Reply
Let us now start to think about Balog’s problem, the easiest instance of which is this: Suppose that two additive sets $A$ and $B$ satisfy $|A+2B|=\gamma^2|A|$ for some positive real number $\gamma$ . Then there is some non empty $X\subseteq A$ such that

$|X+3B|\leqslant \gamma^3|X|.$

In accordance with George’s general approach one might hope to be able to take for this purpose any $X$ that minimizes the ratio $|X+2B|/|X|$ . In other words, we add the hypothesis that for each $Z\subseteq A$ we have

$|Z+2B|\geqslant \gamma^2|Z|$ ,

and then we hope to prove

$|A+3B|\leqslant \gamma^3|A|$ .

Note that this then entails

$|A+nB|\leqslant \gamma^n|A|$

for all integers $n\geqslant 2$ .

[Why? By George’s theorem we have $|A+(m+2)B|\leqslant\gamma^2|A+mB|$ for all non negative integers $m$ , so we may apply induction on $n$ .]

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

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

(Note that taking $C=B$ we obtain what we want.) Now I admittedly have been unable to verify this claim by induction on $C$ , but maybe someone else will succeed. (The case $|C|=1$ 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 $E$ of $A+B$ that satisfies

$|E+B+C|\leqslant \gamma|E+C|$ .

(Such subsets do exist, e.g. $E=\varnothing$ has this property.) What we seek to prove is then $E=A+B$ , so assume that this was not the case. Setting
$X=\{a\in A\,|\,a+B\subseteq E\}$ ,

we then get $X\ne A$ , which means that $Y=A\setminus X$ cannot be empty.

Subclaim 1: $\gamma\cdot |Y|<|(A+B)\setminus E|$ .

Proof: Notice that our definition of $Y$ entails

$(A+B)\setminus E=(Y+B)\setminus E$ .

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

$\kappa=|(Z+B)\setminus E|/|Z|$

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

$|(Z+2B+C)\setminus (E+B+C)|\leqslant\kappa|(Z+B+C)\setminus(E+C)|$ .

Adding this to

$|E+B+C|\leqslant \gamma|E+C|$

and taking the distributive law

$(R\cup S)+T=(R+T)\cup(S+T)$

into account, we infer that the set $E\cup(Z+B)$ , which is strictly larger than $E$ by $Z\ne\varnothing$ and $X\cap Z=\varnothing$ , contradicts the maximality property of $E$ . This establishes our first subclaim.

Subclaim 2: $\gamma\cdot|(A+B)\setminus E|\gamma^2|Y|$ . Adding these two inequalities, we get

$|A+2B|>\gamma^2(|X|+|Y|)=\gamma^2|A|$ ,

which contradicts our definition of $\gamma$ . Therefore our assumption $E\ne A+B$ must have been wrong, or in other words we have indeed

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

It seems conceivable that this may be generalized further.
- Christian Says:
  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: $\gamma\cdot|(A+B)\setminus E|\gamma^2|Y|$ . Adding these two inequalities, we get
  
  $|A+2B|>\gamma^2(|X|+|Y|)=\gamma^2|A|$ ,
  
  which contradicts our definition of $\gamma$ . Therefore our assumption $E\ne A+B$ must have been wrong, or in other words we have indeed
  
  $|A+2B+C|\leqslant \gamma|A+B+C|$ .
- Christian Says:
  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: $\gamma\cdot|(A+B)\setminus E|$ is less than $|(A+2B)\setminus (E+B)|$ .
  
  Proof: Quite similarly, setting
  
  $E'=(A+B)\setminus E$
  
  we have
  
  $(A+2B)\setminus (E+B)=(E'+B)\setminus (E+B)$ ,
  
  so if our subclaim failed, we could take some non empty $F\subseteq E'$ for which the ratio
  
  $\lambda=|(F+B)\setminus (E+B)|/|F|$
  
  is minimal and then we had $\lambda\leqslant\gamma$ . Using the result from my previous comment with $F$ and $E$ here in place of $A$ and $J$ there, we obtain
  
  $|(F+B+C)\setminus (E+B+C)|\leqslant\lambda|(F+C)\setminus(E+C)|$ .
  
  Adding this to
  
  $|E+B+C|\leqslant\gamma|E+C|$
  
  we see that $E\cup F$ contradicts the maximality of $E$ . This proves the second subclaim.
  
  Now note that $X+B\subseteq E$ by definition of $X$ , which tells us that $X+2B\subseteq E+B$ . Thus our hypothesis on $|A|$ gives $|E+B|\geqslant\gamma^2|X|$ . Moreover, combining our two subclaims, we learn that $|(A+2B)\setminus(E+B)|$ is larger than $\gamma^2|Y|$ . Adding these two inequalities, we infer that
  
  $|A+2B|$ is larger than $\gamma^2(|X|+|Y|)=\gamma^2|A|$,
  
  which contradicts our definition of $\gamma$ . Therefore our assumption $E\ne A+B$ must have been wrong, or in other words we have indeed
  
  $|A+2B+C|\leqslant \gamma|A+B+C|$ .
Christian Says:
March 4, 2011 at 1:35 am | Reply
In this comment, I attempt to answer Balog’s question.

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

$|(A+nB)\setminus (J+nB)|=\gamma^n\cdot|A|$

and suppose that the inequality

$|(Z+nB)\setminus (J+nB)|\geqslant\gamma^n\cdot|Z|$

holds for all $Z\subseteq A$ . Then

$|(A+nB+C)\setminus (J+nB+C)|\leqslant \gamma\cdot|(A+(n-1)B+C)\setminus (J+(n-1)B+C)|$ .

Proof: We argue by induction on $n$ . The base case, $n=1$ , has already been considered in a previous comment. So suppose now that $n\geqslant 2$ and that the statement under discussion is already known for $n-1$ in place of $n$ . Notice that if we would set $E=J+B$ , then

$|(E+(n-1)B+C)\setminus (J+nB+C)|\leqslant \gamma\cdot |(E+(n-2)B+C)\setminus (J+(n-1)B+C)|$ ,

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

$J+B\subseteq E\subseteq (A\cup J)+B$

that satisfies

$|(E+(n-1)B+C)\setminus (J+nB+C)|\leqslant \gamma\cdot |(E+(n-2)B+C)\setminus (J+(n-1)B+C)|$ ,

and that is maximal with respect to that property. Set

$X=\{a\in A\,|\, a+B\subseteq E\}$

and $Y=A\setminus X$ . Note that if $X=A$ , then $A+B\subseteq E$ and we are done, so assume from now on that this was not the case.

Subclaim 1: $\gamma\cdot |Y|$ is less than $|(A+B)\setminus E|$ .

Proof: By definition of $X$ we have

$(A+B)\setminus E=(Y+B)\setminus E$ .

Now we choose some non empty $Z\subseteq Y$ such that

$\kappa=|(Z+B)\setminus E|/|Z|$

attains its minimal value, and observe that if our subclaim failed, then we had $\kappa\leqslant\gamma$ . 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 $Z$ and $(n-2)B+C$ here in place of $A$ and $C$ there, we infer

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

We would like to add this to

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

For this purpose, we observe that generally if $T\subseteq S$ , then

$|R\setminus S|+|S\setminus T|=|(R\cup S)\setminus T|$ .

This principle may be applied here, as $J+B\subseteq E$ by construction. Thus setting $E^*=E\cup(Z+B)$ , we get

$|(E^*+(n-1)B+C)\setminus (J+nB+C)|\leqslant \gamma\cdot |(E^*+(n-2)B+C)\setminus (J+(n-1)B+C)|$ ,

which tells us that $E^*$ violates the maximality of $E$ . This contradiction proves our first subclaim.

Subclaim 2: $\gamma^{n-1}\cdot |(A+B)\setminus E|$ is less than $|(A+nB)\setminus (E+(n-1)B)|$ .

Proof: Set $E'=(A+B)\setminus E$ . This set may be supposed to be non empty, for otherwise the demand on $E$ entails what we want to know. Now if our subclaim failed, then in view of

$(A+nB)\setminus (E+(n-1)B)=(E'+(n-1)B)\setminus (E+(n-1)B)$ ,

the minimal value

$\lambda^{n-1}=|(F+(n-1)B)\setminus (E+(n-1)B)|/|F|$

that arises as $F$ varies through all non empty subsets of $E'$ satisfies $\lambda\leqslant\gamma$ . Applying the induction hypothesis (recall that our proof is by induction on $n$ ) with $F$ and $E$ here in place of $A$ and $J$ there, we infer

$|(F+(n-1)B+C)\setminus (E+(n-1)B+C)|\leqslant\gamma |(F+(n-2)B+C)\setminus (E+(n-2)B+C)|$ .

Adding this to

$|(E+(n-1)B+C)\setminus (J+nB+C)|\leqslant \gamma\cdot |(E+(n-2)B+C)\setminus (J+(n-1)B+C)|$

we deduce in the same way as before that $E\cup F$ contradicts the maximality of $E$ . This completes the proof of our second subclaim.

Now everything is as before:

$|(A+nB)\setminus (J+nB)|=|(A+nB)\setminus (E+(n-1)B)|+|(E+(n-1)B)\setminus (J+nB)|$ ,

the first of these two terms is larger than $\gamma^n\cdot |Y|$ by our two subclaims and the second one is at least $\gamma^n\cdot |X|$ by extremality of $A$ and $X+B\subseteq E$ . So altogether $|(A+nB)\setminus (J+nB)|$ is larger than $\gamma^n\cdot |A|$ , and this contradiction proves our proposition.

Corollary 1. Let $A$ and $B$ be two additive sets such that $|A+nB|=\gamma^n\cdot|A|$ and suppose that every $Z\subseteq A$ satisfies
$|Z+nB|\geqslant\gamma^n\cdot|Z|$ . Then one has $|A+nB+C|\leqslant \gamma\cdot|A+(n-1)B+C|$ for each additive set $C$ .

Proof: Just set $J=\varnothing$ in the proposition just obtained.

Corollary 2. If $A$ and $B$ are as above, then $|A+mB|\leqslant \gamma^m|A|$ for all integers $m\geqslant n$ .

Proof: The case $m=n$ is clear, now use induction on $m$ . For the induction step observe that if $m>n$ , then substituting $C=(m-n)B$ into the previous corollary, we get

$|A+mB|\leqslant \gamma\cdot|A+(m-1)B|$ .

Corollary 3. If $A$ and $B$ are additive sets and $|A+nB|=\gamma^n\cdot|A|$ , then there is some non empty $X\subseteq A$ such that for every integer $m\geqslant n$ we have $|X+mB|\leqslant |X|$ .

Proof: Take $X$ in such a way that $|X+nB|/|X|$ is minimal and use the previous corollary.
Terence Tao Says:
March 12, 2011 at 5:44 pm | Reply
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 constants

$\kappa(B) := \min \{ |ZB|-|Z|: Z \hbox{ finite nonempty} \}$

and is based on an analysis of minimisers to those constants. Apart from dealing with minimising $|ZB|-|Z|$ rather than $|Z+B|/|Z|$ , this looks quite similar. It may be worth looking into whether there is any deeper connection here…
- Terence Tao Says:
  March 12, 2011 at 6:05 pm
  A correction: in the definition of $\kappa$ , 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 $B$ and $B^{-1}$ 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, $\kappa(B)$ is expected to be |B| and H is expected to be trivial, but when the doubling constant is strictly less than 2, $\kappa(B)$ dips below |B| and H becomes non-trivial.)
- Petridis Says:
  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 $K=1$ and $A=B$ 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.
- Petridis Says:
  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.
Hamidoune’s Freiman-Kneser theorem for nonabelian groups « What’s new Says:
March 12, 2011 at 10:17 pm | Reply
[…] 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) […]
Gadi Aleksandrowicz Says:
March 30, 2011 at 10:49 pm | Reply
A typo? Near the end, “such that |A+hB|\le K^h|B| for every…”

Shouldn’t it be \le K^h|A|?
507- Plünnecke inequalities and sumset estimates « A kind of library Says:
August 26, 2012 at 9:23 pm | Reply
[…] 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 […]