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

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

so
from which it follows that


and the inductive hypothesis imply that this is at most 
where
But
and therefore that
The minimality of
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.
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.)
Say, to my knowledge, no progress has been made on my ~10-year-old conjecture that if
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
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
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 constants
and 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 […]
June 12, 2019 at 7:55 am |
Reblogged.