Here the pdf version: link.
In the following, I shall use to denote both the Lebesgue measure of , when a subset of , or the cardinality of set . This shouldn’t cause any confusion, and help highlight the parallel with the continuous case.
For the sake of completeness, we remind the reader that the Minkowski sum of two sets is defined as
I’ve been shamefully sketchy in the previous post about Christ’s work on near extremizers, and in particular I haven’t addressed properly one of the most important ideas in his work: exploiting the hidden additive structure of the inequalities. I plan to do that in this post and a following one, in which I’ll sketch his proof of the sharpened Riesz-Sobolev inequality.
In that paper, one is interested in proving that triplets of sets that nearly realize equality in Riesz-Sobolev inequality
must be close to the extremizers of the inequality, which are ellipsoids (check this previous post for details and notation). In case , ellipsoids are just intervals, and one wants to prove there exist intervals s.t. are very small.
Christ devised a tool that can be used to prove that a set on the line must nearly coincide with an interval. It’s the following
Proposition 1 (Christ, [ChRS2]) , (continuum Freiman’s theorem) Let be a measurable set with finite measure . If
then there exists an interval s.t.  and
Thus if one can exploit the near equality to spot some additive structure, one has a chance to prove the sets must nearly coincide with intervals. It turns out that there actually is additive structure concealed in the Riesz-Sobolev inequality: consider the superlevel sets
then one can prove that
If one can control the measure of the set on the right by for some specific value of , then Proposition 1 can be applied, and will nearly coincide with an interval. Then one has to prove this fact extends to , but that’s what the proof in [ChRS] is about and I will address it in the following post, as said.
Anyway, the result in Prop. 1, despite being stated in a continuum setting, is purely combinatoric. It follows – by a limiting argument – from a big result in additive combinatorics: Freiman’s theorem.
The aim of this post is to show how Prop. 1 follows from Freiman’s theorem, and to prove Freiman’s theorem with additive combinatorial techniques. It isn’t necessary at all in order to appreciate the results in [ChRS], but I though it was nice anyway. I haven’t stated the theorem yet though, so here it is:
Then there exists an arithmetic progression s.t. , whose length is .
The proof isn’t extremely hard but neither it’s trivial. It relies on a few lemmas, and it is fully contained in section 2. Section 1 contains instead the limiting procedure mentioned above that allows to deduce Proposition 1 from Freiman’s theorem.
Remark 1 Notice that Proposition 1 is essentially a result for the near-extremizers of Brunn-Minkowski’s inequality in , which states that . Indeed the extremizers for B-M are convex sets, which in dimension 1 means the intervals. Thus Prop 1 is saying that if isn’t much larger than , then is close to being an extremizer, i.e. an interval. One can actually prove that for two sets , if one has
then . A proof can be found in [ChRS]. It is in this sense that the result in [ChBM] for Brunn-Minkowski was used to prove the result in [ChRS] for Riesz-Sobolev, which was then used for Young’s and thus for Hausdorff-Young, as mentioned in the previous post.
1. Proof of continuum Freiman’s theorem
In this section I shall prove Proposition 1 assuming Freiman’s theorem. The proof is taken from [ChRS2]. Discrete sets are indicated in calligraphic letters like , and thus is the cardinality of . Subsets of are indicated in latin letters like , and therefore is the Lebesgue measure of .
Assume , and therefore fix small enough s.t. as well. The idea is that for small enough we can find a set of points on s.t. these points have high density in , and thus approximates . But then the bound on the measure of implies that , and therefore one can apply Freiman’s theorem and conclude is nearly an arithmetic progression. Finally, it is proven that in this context the common difference of the arithmetic progression must be and thus the approximating set is indeed an interval.
Define the approximating discrete set as follows: let denote the interval centered in of width , i.e. ; then
Then we see the set approximates in measure. Indeed, by Lebesgue differentiation theorem,
as . Since , it also follows as , and therefore for every we can find small enough s.t.
Assume and notice the following: if then . This is because the sets have large density. Indeed, if are s.t. then their intersection must have positive measure (in particular it’s non empty), and therefore ; applying this observation to we get that , which means there exist s.t. .
It’s now easy to estimate
For small enough then we can make it so and eventually taking them even smaller we can make it so , since as . Therefore we have, for such , , and we can apply Freiman’s discrete theorem, which yields us an arithmetic progression s.t. and .
Now, remember we want to prove that is contained in some interval: this interval will be . Notice that
and we can make as small as we want. Thus if we can prove and that is an interval, we’re done. The first one is easy: namely, intersect all the intervals you get for . Again, by Lebesgue differentiation theorem, at most a set of null measure is left outside of . As for the second, it’s obvious that for to be an interval we must have that the step of is . We can assume that (by translating in the positive real line); assume by contradiction that . Then for any s.t. we must have . In other words, integers in must be separated by at least 2. This implies that has measure too large. Indeed, observe that , and therefore if it must be
where the second to last inequality is simply Brunn-Minkowski. Now, by our assumption, as runs through , all the sets are disjoint (except for at most a point), since implies . Then we have a lower bound for :
and by inequality (1) (see below)
For small enough the last can be made , thus producing a contradiction. This concludes the proof.
2. Proof of discrete Freiman’s theorem
All of the following is taken from [TaoVu].
We’re gonna need a few facts here. Although our set will be in i.e. arbitrarily large, we want to prove an upper bound on its cardinality, and we’ll do so by reducing it to a set in some , where . The statement of Freiman’s theorem can be recast as saying that , and we’ll prove this by contradiction. In doing so we’ll therefore need some lower bounds on quantities where are subsets of . Here the group structure must enter in some way, and indeed one has the following (which we’ll use)
where is the group of symmetries of set , i.e. translations w.r.t. which is invariant.
Remark 2 Notice that since , the statement can be trivially tightened to
Let’s look at a couple of particular cases: if then for finite sets , and thus we have 
Anyway, we’ll need Kneser’s theorem for the case of a general quotient of . Before we can prove it though, we’re gonna need a few more facts.
2.1. Case of in a general additive group
We have an important structural property:
- is contained in a coset of : s.t. ;
- is a union of cosets of : s.t. .
Proof: Assume . We can translate so that it contains , and therefore , but then the hypothesis forces . Therefore , and we’ll choose . Notice we have translated at the beginning, so our original is actually contained in a translation of , i.e. a coset. The fact that is a union of cosets of is immediate from the fact that is the group of symmetries of itself.
As for the other implication, it’s evident that is a translation of and thus has the same cardinality.
Remark 3 From the second characterization it follows that , and in general that , which is equivalent to . Here , where the Minkowski sum has terms.
The following device will prove very useful in the proof of Kneser’s theorem.
Definition 5 Let be subsets of an additive group . Choose . Then the -transform of is the pair defined by
This definition seems pretty arbitrary but I hope I can clarify it a little bit. First of all notice that we can write and , and now notice that is the set of all with s.t.
while is the set of all s.t.
and thus . This means we can interpret the -transform as the following algorithm:
- translate by , thus obtaining ;
- remove the elements of that are not contained in (these are ): what’s left is ;
- take the elements removed at the previous step, translate them back by , thus obtaining ;
- join this set to (notice they are disjoint) and call the resulting set .
The reason why these transforms are gonna be useful in proving lower bounds for sums is contained in the following proposition
Proposition 6 Let be sets in additive group, and let denote the -transform of . Then we have the following:
- and .
As you can see, the transform can reduce the size of the Minkowski sum while keeping constant: it is thus a perfect tool to prove lowerbounds of the kind we’re interested in!
As for the properties above, (2.) and (3.) are evident from the discussion preceding the statement of the proposition: we’ve removed a set from , translated it, and attached to . It is therefore clear that the sum of the elements hasn’t changed. As for property (1.), contains either elements of the form or : in the first case, since ,
while in the second, since an element of must be of the form for some
2.3. Proof of Kneser’s theorem
We’re now ready for the proof of Kneser’s theorem. It consists of a rather involved induction. The relevant parameters here are and (or , it’s up to you). Notice that besides the trivial bound we have another bound, , since for obvious reasons. Thus one arranges the induction procedure as follows:
- upward on : assume the thm has been proved for all lower values of , and for all admissible values of and ; then we prove it holds for ;
- downward on : assume the thm has been proved for a fixed and for all higher values and all admissible values of ; then we prove it holds for and ;
- upward on : assume the thm has been proved for a fixed , a fixed and for all lower values of ; then we prove it holds for , and .
To convince you that this way we get the inequality for all admissible values, notice that the base case is true by Lemma 4: since , it follows that , and then is contained in a coset of and in particular ; we also get that is a translate of , therefore . Then .
Proof: The proof branches into multiple cases. A checkmark symbol indicates the leaf is terminal, without further branching (under the specific hypothesis of the branch the leaf is in).
Case 1: suppose . In this case we can reduce to a smaller by quotienting out the symmetries: let , then consider sets in : their Minkowski sum is
which has cardinality strictly smaller than ; then by induction hypothesis (1.) it is
and we recover what we want upon multiplying by .
Case 2: suppose . We hav:= to prove then that . We split in further cases.
Case 2.1: Suppose that for all we have that . This means that or equivalently for all and therefore ; by lemma 4 then is in a coset of some subgroup and is a union of cosets of . Then it is evident that : for any , since for some , . But since we are in case 2, then , and therefore , and then and we’re done. \checkmark
Case 2.2: Suppose then that there exists s.t. , and amongst all such ‘s choose one that maximizes . By translating we can assume without loss of generality that and therefore work with
Case 2.2.1: Suppose that . Then , and therefore
Case 2.2.2: Suppose then that . Define . Then we have
it follows that
and therefore we can replace and with and without altering , but at most increasing .
Case 22.214.171.124: Suppose . Then by induction hypothesis (2.)
Case 126.96.36.199: Suppose , which implies that and , and in particular . But this means and therefore . This means that is a union of cosets of .
Now, consider the pairs s.t. , and let be the set of all that appear in , which is non-empty by assumption. Fix one of these and notice the following: , otherwise
and for the same reason the whole coset is disjoint from , as otherwise
(in particular, is disjoint from ). If is s.t. , then is disjoint from : indeed, if then so would , since is the symmetry group of . Then we’ve found an entire coset inside , and we can tighten the inequality to
and what is ? It’s the set of elements of the form or that are not contained in either or , but are contained in – equivalently, it’s the set of elements of the form that are not contained in . It’s clear has elements, and since there is no double counting and we can write
Summing up, we have the inequalities
Then, by (2) and the fact that ,
We split into further cases.
Case 188.8.131.52.1: Suppose there exists s.t. . Then we’re done.
Case 184.108.40.206.2: Suppose then for all . We must show we reach a contradiction. Define
Now we want to consider sums of the form . We split again.
Case 220.127.116.11.2.1: Suppose we can find s.t.
First notice that since both elements of and are of the form with , it follows that
this means we can find an s.t. , which in turn implies : indeed, if this were the case, we’d have for all and in particular for those , but then . On the other hand, too, thus we can take the -transform of . Consider : since , it is strictly contained in . Moreover, since , : indeed, if then too, and then . Finally, strictly contains , since it contains , and is disjoint from as seen above. Notice is non-empty, since for some and , and thus . Thus we’ve reached a contradiction, because was assumed to have maximal cardinality.
Case 18.104.22.168.2.2: Suppose then that
for all . Then , by interchanging and we get that for all . This means that
which by Lemma 4, when implies that is contained in a coset of . We show that all ‘s are contained in cosets of this , and that are all unions of cosets of this same . Indeed, the above for implies (by Lemma 4 again) that is contained in a coset of , but then must be contained in a coset of as well: let , coset for some , an element of , then for some and thus , which proves that belongs to a coset of .
Since are contained in cosets of , is a translate of , and therefore for some it is , but they have the same cardinality and must therefore coincide – all ‘s are translates of each other. Since is a union of cosets of , so are its translates and therefore the ‘s. Notice that : indeed, is contained in a coset of , which then contains at least one coset of . Thus is a union of cosets of for every , and therefore so is , which contains by definition of ; moreover, by definition of , is a union of cosets of and thus a union of cosets of . Therefore
is the union of cosets of , and therefore .
On the other hand, by assumption for all , which implies , and then we’ve reached a contradiction.
That was some tour de force.
2.4. Another lowerbound on
We need one further lemma to conclude the proof.
Notice that by linearity.
Proof: One can write
If , it is by linearity , and therefore if we let take all possible values we see that we can write
we use as a lower bound of the sum the supremum of its terms, and thus
and by (1) the inner term is bounded from below by . Thus the last sum is bounded from below by
notice that for , and it is iff , so that the last sum is bound from below by
Since , by expanding the sums and then collecting the terms we have what we want (notice since , and thus ).
2.5. Finally, the proof
Remember the statement of Freiman’s theorem: we assume isn’t much larger than , in particular , and want to prove there exists an arithmetic progression containing and of controlled length (at most : observe that , so that if is an arithmetic progression then the bound is tight).
Proof: Translate so that . Fix , and suppose without loss of generality that (otherwise, factor out the common divisor of the elements of – which would be the step of the arithmetic progression). We claim that the arithmetic progression that we’re looking for is exactly in this case. It certainly contains , and it suffices to prove the bound on the size . We argue by contradiction, assuming that .
Let be the quotient map . Notice that . You might guess what we’re gonna do now: we want to prove that , thus reaching a contradiction, and we want to do so using the lowerbounds we’ve introduced above. In particular, by Lemma 7, since (only and have the same remainder modulus ) and (since all the other elements of are mapped -to-)
from which it follows that , by the hypothesis of Freiman’s theorem.  In particular, by the assumption we have .
Moreover, by Kneser’s theorem 3,
where . By rearranging (4) we can say
Thus we have and in particular can’t be trivial, because we have too. This means there exists a number s.t. , and in particular it must be . We want to apply Lemma 7 with in place of to conclude, i.e. with quotient map : this way we factor out the symmetry group of the projection of , and basically reduce to the case . But we have to find bounds for the quantities first.
Observe that , since otherwise the elements of would have greatest common divisor at least , which we have ruled out. Therefore has elements in different cosets of and in particular (which is made of cosets of ) contains at least two entire cosets (and ). It follows that, for some non-trivial coset intersecting ,
since has multeplicity w.r.t. , we have
Now we can start applying Lemma 7 with . Thus
since , we can bound by (5), and therefore the above is bounded from below by
Since , the last expression is equal to
where the last inequality is again. Thus we’ve proved , thus reaching a contradiction.
 To be precise, is essentially contained in , in the sense that .
 one doesn’t need Kneser’s thm to prove this, it follows from the ordering of the integers.
 i.e. there exists s.t.
 Notice however we don’t strictly need the lemma for this, because can’t have more than elements, being a projection, and elements of the form and have the same remainder modulus .
[ChBM] M. Christ, Near equality in the Brunn-Minkowski inequality, arXiv:1207.5062 [math.CA], 2012.
[ChRS2] M. Christ, An Approximate Inverse Riesz-Sobolev Inequality, arXiv:1112.3715 [math.CA], 2011.
[ChRS] M. Christ, Near equality in the Riesz-Sobolev inequality, arXiv:1309.5856 [math.CA], 2013.
[TaoVu] Terence Tao & Van H. Vu, Additive combinatorics, Cambridge Studies in Advanced Mathematics, vol. 105, 2006.