Freiman’s theorem and compact subsets of the real line with additive structure

Here the pdf version: link.

In the following, I shall use {|A|} to denote both the Lebesgue measure of {A}, when a subset of {\mathbb{R}}, or the cardinality of set {A}. 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 {A,B} is defined as

\displaystyle A+B:=\{a+b \,:\, a\in A, b\in B\}.

 

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 {A,B,C \subset \mathbb{R}^d} that nearly realize equality in Riesz-Sobolev inequality

\displaystyle \left\langle \chi_{A} \ast \chi_{B}, \chi_{C}\right\rangle \leq \left\langle \chi_{A^\ast} \ast \chi_{B^\ast}, \chi_{C^\ast}\right\rangle

must be close to the extremizers of the inequality, which are ellipsoids (check this previous post for details and notation). In case {d=1}, ellipsoids are just intervals, and one wants to prove there exist intervals {I,J,K} s.t. {A \Delta I, B\Delta J, C\Delta K} 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 {A\subset \mathbb{R}} be a measurable set with finite measure {>0}. If

\displaystyle |A+A|< 3|A|,

then there exists an interval {I} s.t. {A\subset I} [1] and

\displaystyle |I| \leq |A+A|-|A|.

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

\displaystyle S_{A,B}(t):=\{x \in \mathbb{R} \,:\, \chi_A \ast \chi_B (x) > t\};

then one can prove that

\displaystyle S_{A,B} (t) - S_{A,B} (t') \subset S_{A,-A}(t+t' - |B|).

If one can control the measure of the set on the right by {|S_{A,B} (t)|} for some specific value of {t=t'}, then Proposition 1 can be applied, and {S_{A,B}(t)} will nearly coincide with an interval. Then one has to prove this fact extends to {A,B,C}, 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:

Theorem 2 (Freiman’s {3k-3} theorem) Let {A\subset \mathbb{Z}} be finite and such that

\displaystyle |A+A| < 3|A|-3.

Then there exists an arithmetic progression {P} s.t. {A\subseteq P}, whose length is {|P|\leq |A+A|-|A|+1}.

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 {\mathbb{R}^1}, which states that {|A+A|\geq |A|+|A|}. Indeed the extremizers for B-M are convex sets, which in dimension 1 means the intervals. Thus Prop 1 is saying that if {|A+A|} isn’t much larger than {2|A|}, then {A} is close to being an extremizer, i.e. an interval. One can actually prove that for two sets {A,B}, if one has

\displaystyle |A+B| \leq |A|+|B|+\min(|A|,|B|)

then {\mathrm{diam}(A) \leq |A+B|-|B|}. 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 {\mathcal{A}}, and thus {|\mathcal{A}|} is the cardinality of {\mathcal{A}}. Subsets of {\mathbb{R}} are indicated in latin letters like {A}, and {|A|} therefore is the Lebesgue measure of {A}.

Assume {|A+A|< 3|A|}, and therefore fix {\rho > 0} small enough s.t. {|A+A|<(3-\rho)|A|} as well. The idea is that for {\varepsilon>0} small enough we can find a set of points {\mathcal{A}} on {\varepsilon \mathbb{Z}} s.t. these points have high density in {A}, and thus {\mathcal{A}+[-\varepsilon/2, \varepsilon/2]} approximates {A}. But then the bound on the measure of {A+A} implies that {|\mathcal{A}+\mathcal{A}| \leq 3 |\mathcal{A}| - 3}, and therefore one can apply Freiman’s theorem and conclude {\mathcal{A}} is nearly an arithmetic progression. Finally, it is proven that in this context the common difference of the arithmetic progression must be {1} and thus the approximating set is indeed an interval.

Define the approximating discrete set {\mathcal{A}} as follows: let {I_{n,\varepsilon}} denote the interval centered in {\varepsilon n} of width {\varepsilon}, i.e. {I_{n, \varepsilon} = [\varepsilon n - \varepsilon/2,\varepsilon n + \varepsilon/2]}; then

\displaystyle \mathcal{A}=\mathcal{A}_{\varepsilon, \delta} := \{ n \in \mathbb{Z} \,:\, |A\cap I_{n, \varepsilon}| > (1-\delta) \varepsilon\}.

Then we see the set {\tilde{A}_{\varepsilon,\delta} := \bigcup_{n \in \mathcal{A}_{\varepsilon,\delta}}{I_{n,\varepsilon}}} approximates {A} in measure. Indeed, by Lebesgue differentiation theorem,

\displaystyle \left|\tilde{A}_{\varepsilon,\delta} \; \Delta \; A\right| \rightarrow 0

as {\max(\varepsilon, \delta) \rightarrow 0}. Since {|\tilde{A}_{\varepsilon,\delta} | = \varepsilon |\mathcal{A}_{\varepsilon,\delta}|}, it also follows {\varepsilon |\mathcal{A}_{\varepsilon,\delta}| \rightarrow |A|} as {\max(\varepsilon, \delta) \rightarrow 0}, and therefore for every {1\gg \eta>0 } we can find {\varepsilon, \delta} small enough s.t.

\displaystyle (1-\eta) |A| \leq \varepsilon |\mathcal{A}|\leq (1+\eta) |A|.

Assume {\delta < 1/2} and notice the following: if {m+n \in \mathcal{A}+\mathcal{A}} then {\varepsilon n + \varepsilon m \in A+A}. This is because the sets {A\cap I_{n,\varepsilon}, A\cap I_{m,\varepsilon}} have large density. Indeed, if {S,T \subset [-1/2,1/2]} are s.t. {|S|,|T|>1/2} then their intersection must have positive measure (in particular it’s non empty), and therefore {0 \in S-T}; applying this observation to {S= A\cap I_{n,\varepsilon}-\varepsilon n, T=-(A\cap I_{m,\varepsilon})+\varepsilon m} we get that {0 \in (A\cap I_{n,\varepsilon}-\varepsilon n)\cap (-(A\cap I_{m,\varepsilon})+\varepsilon m)}, which means there exist {a,b \in A} s.t. {a - \varepsilon n = -b + \varepsilon m} {\Rightarrow } {\varepsilon n + \varepsilon m = a + b \in A+A}.

It’s now easy to estimate

\displaystyle |\mathcal{A} + \mathcal{A}| \leq \frac{|A+A|}{\varepsilon} \leq \frac{(3-\rho)|A|}{\varepsilon} \leq \frac{(3-\rho) |\mathcal{A}|}{1-\eta}

\displaystyle = 3 |\mathcal{A}| - \frac{\rho - 3\eta}{1-\eta}|\mathcal{A}|.

For {\max(\varepsilon, \delta)} small enough then we can make it so {\frac{\rho - 3\eta}{1-\eta} > \rho/2} and eventually taking them even smaller we can make it so {\rho/2 |\mathcal{A}|> 3}, since {|\mathcal{A}|\rightarrow \infty} as {\max(\varepsilon, \delta) \rightarrow 0}. Therefore we have, for such {\varepsilon, \delta}, {|\mathcal{A} + \mathcal{A}| \leq 3 |\mathcal{A}| - 3}, and we can apply Freiman’s discrete theorem, which yields us an arithmetic progression {\mathcal{P}} s.t. {\mathcal{A}\subset \mathcal{P}} and {|\mathcal{P}| \leq |\mathcal{A}+ \mathcal{A}| - |\mathcal{A}|+1}.

Now, remember we want to prove that {A} is contained in some interval: this interval will be {I := \bigcup_{n \in \mathcal{P}}{I_{n,\varepsilon}}}. Notice that

\displaystyle |I| = \varepsilon |\mathcal{P}| \leq \varepsilon|\mathcal{A}+ \mathcal{A}| - \varepsilon|\mathcal{A}|+\varepsilon \leq |A+A| - (1-\eta)|A| + \varepsilon = |A+A|-|A| +(\eta |A| + \varepsilon),

and we can make {\eta |A| + \varepsilon} as small as we want. Thus if we can prove {A \subset I} and that {I} is an interval, we’re done. The first one is easy: namely, intersect all the intervals you get for {\varepsilon, \delta \rightarrow 0}. Again, by Lebesgue differentiation theorem, at most a set of null measure is left outside of {I}. As for the second, it’s obvious that for {I} to be an interval we must have that the step {d} of {\mathcal{P}} is {1}. We can assume that {\mathcal{P} \subset \mathbb{Z}^{+}} (by translating {A} in the positive real line); assume by contradiction that {d>1}. Then for any {m,n,m',n' \in \mathcal{A}} s.t. {m+n \neq m' + n'} we must have {|(m+n)-(m'+n')|\geq 2}. In other words, integers in {\mathcal{A}+\mathcal{A}} must be separated by at least 2. This implies that {A+A} has measure too large. Indeed, observe that {I_{n, \varepsilon}+I_{m \varepsilon} = [\varepsilon(m+n) - \varepsilon, \varepsilon(m+n) + \varepsilon]}, and therefore if {m+n \in \mathcal{A}+\mathcal{A}} it must be

\displaystyle |(A+A) \cap [\varepsilon (m+n) - \varepsilon,\varepsilon (m+n) + \varepsilon ]|\geq |(A\cap I_{n, \varepsilon}) + (A \cap I_{m, \varepsilon})|\geq |A\cap I_{n, \varepsilon}| + |A \cap I_{m, \varepsilon}| \geq 2 (1-\delta) \varepsilon,

where the second to last inequality is simply Brunn-Minkowski. Now, by our assumption, as {k} runs through {\mathcal{A}+\mathcal{A}}, all the sets {[\varepsilon k - \varepsilon, \varepsilon k + \varepsilon]} are disjoint (except for at most a point), since {k' - k \geq 2} implies {\varepsilon k + \varepsilon \leq \varepsilon k' - \varepsilon}. Then we have a lower bound for {|A+A|}:

\displaystyle |A+A| \geq 2 (1- \delta) \varepsilon |\mathcal{A}+\mathcal{A}|,

and by inequality (1) (see below)

\displaystyle 2 (1- \delta) \varepsilon |\mathcal{A}+\mathcal{A}| \geq 2 (1- \delta) \varepsilon (2|\mathcal{A}|-1) \geq 2 (1- \delta) (2(1-\eta)|A|-\varepsilon)

\displaystyle = (4 - 4(\delta +\eta + \delta\eta)) |A| - (2-2\delta)\varepsilon = 4 |A| - o(1)|A| -o(1).

For {\varepsilon, \delta} small enough the last can be made {> (3+1/2)|A|}, 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 {A} will be in {\mathbb{Z}} 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 {(\mathbb{Z}/N\mathbb{Z}, +)}, where {N = \max(A) - \min(A)}. The statement of Freiman’s theorem can be recast as saying that {N \leq |A+A|-|A| + 1}, and we’ll prove this by contradiction. In doing so we’ll therefore need some lower bounds on quantities {|A+B|} where {A,B} are subsets of {\mathbb{Z}/N\mathbb{Z}}. Here the group structure must enter in some way, and indeed one has the following (which we’ll use)

Theorem 3 (Kneser’s theorem) Let {A,B} be subsets in an additive group {G}. Then

\displaystyle |A+B| \geq |A|+|B| - |\mathrm{Sym}_G (A+B)|,

where {\mathrm{Sym}_G (E) = \{g \in G \,:\, E+g = E\}} is the group of symmetries of set {E}, i.e. translations w.r.t. which {E} is invariant.

Remark 2 Notice that since {(A+\mathrm{Sym}_G (A+B))+(B+\mathrm{Sym}_G (A+B)) = A+ B + \mathrm{Sym}_G (A+B) = A+B}, the statement can be trivially tightened to

\displaystyle |A+B| \geq |A+\mathrm{Sym}_G (A+B)|+|B+\mathrm{Sym}_G (A+B)| - |\mathrm{Sym}_G (A+B)|.

Let’s look at a couple of particular cases: if {G = \mathbb{Z}} then for finite sets {\mathrm{Sym}_\mathbb{Z} (E) = \{0\}}, and thus we have [2]

\displaystyle |A+B| \geq |A|+ |B|-1 \qquad \text{ in } \mathbb{Z} \ \ \ \ \ (1)

if {G = \mathbb{Z}/p\mathbb{Z}} with {p} prime then there are no non trivial subgroups and therefore {\mathrm{Sym}_{\mathbb{Z}/p\mathbb{Z}}(E) = \{0\}} or {\mathbb{Z}/p\mathbb{Z}}, and the latter can only happen iff {E} is all of the group, and thus Kneser’s theorem implies the Cauchy-Davenport inequality

\displaystyle |A+B| \geq \min(|A|+ |B|-1, p).

Anyway, we’ll need Kneser’s theorem for the case of a general quotient of {\mathbb{Z}}. Before we can prove it though, we’re gonna need a few more facts.

2.1. Case of {|A+B|=|A|} in a general additive group

We have an important structural property:

Lemma 4 Let {A,B} be subsets in an additive group {G}. Then {|A+B|=|A|} if and only if there exists a subgroup {H \leq G} s.t.

  • {B} is contained in a coset of {H}: {\exists \tilde{g} \in G} s.t. { B \subseteq \tilde{g}+H};
  • {A} is a union of cosets of {H}: {\exists F \subseteq G } s.t. {A = \bigcup_{g \in F}{(g + H)}}.

Proof: Assume {|A+B|=|A|}. We can translate {B} so that it contains {0}, and therefore {A+B\supseteq A}, but then the hypothesis forces {A+B = A}. Therefore {B \subseteq \mathrm{Sym}_G (A)}, and we’ll choose {H = \mathrm{Sym}_G (A)}. Notice we have translated {B} at the beginning, so our original {B} is actually contained in a translation of {H}, i.e. a coset. The fact that {A} is a union of cosets of {H} is immediate from the fact that {H} is the group of symmetries of {A} itself.

As for the other implication, it’s evident that {A+B} is a translation of {A} and thus has the same cardinality. \Box

Remark 3 From the second characterization it follows that {|A+B-B|=|A|}, and in general that {|A+nB-mB|=|A|}, which is equivalent to {|A+B|=|A|}. Here {nB= B + \ldots + B}, where the Minkowski sum has {n} terms.

2.2. {e}-transforms

The following device will prove very useful in the proof of Kneser’s theorem.

Definition 5 Let {A,B} be subsets of an additive group {G}. Choose {e \in A-B}. Then the {e}-transform of {(A,B)} is the pair {(A_e, B_e)} defined by

\displaystyle A_e := A \cup (B+e),

\displaystyle B_e := B \cap (A-e).

This definition seems pretty arbitrary but I hope I can clarify it a little bit. First of all notice that we can write {A_e = A \cup ((B+e)\backslash A)} and {B_e = B \backslash (B \backslash (A-e))}, and now notice that {(B+e)\backslash A} is the set of all {b+e} with {b\in B} s.t.

\displaystyle b + e \neq a \qquad \forall a\in A,

while {B \backslash (A-e)} is the set of all {b\in B} s.t.

\displaystyle b \neq a-e \qquad \forall a\in A,

and thus {(B+e)\backslash A = [B \backslash (A-e)]+e}. This means we can interpret the {e}-transform as the following algorithm:

  • translate {A} by {-e}, thus obtaining {A-e};
  • remove the elements of {B} that are not contained in {A-e} (these are {B \backslash (A-e)}): what’s left is {B_e};
  • take the elements removed at the previous step, translate them back by {+e}, thus obtaining {(B+e) \backslash A};
  • join this set to {A} (notice they are disjoint) and call the resulting set {A_e}.

The reason why these transforms are gonna be useful in proving lower bounds for sums is contained in the following proposition

Proposition 6 Let {A,B} be sets in {G} additive group, {e \in A-B} and let {A_e, B_e} denote the {e}-transform of {A,B}. Then we have the following:

  1. {A_e + B_e \subseteq A+B};
  2. {|A_e|+|B_e| = |A|+|B|;}
  3. {|A_e|\geq |A|} and {|B_e| \leq |B|}.

 

As you can see, the transform can reduce the size of the Minkowski sum while keeping {|A|+|B|} 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 {B}, translated it, and attached to {A}. It is therefore clear that the sum of the elements hasn’t changed. As for property (1.), {A_e} contains either elements of the form {a \in A} or {b+e}: in the first case, since {B_e \subseteq B},

\displaystyle a+B_e \subset A+B,

while in the second, since an element of {B_e} must be of the form {a'-e} for some {a'\in A}

\displaystyle b+e+a'-e = b+a \in A+B.

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 {|A+B|, |A|+|B|} and {|B|} (or {|A|}, it’s up to you). Notice that besides the trivial bound {|B|\leq |A|+|B|} we have another bound, {|A|+|B| \leq 2|A+B|}, since {\max(|A|,|B|)\leq |A+B|} for obvious reasons. Thus one arranges the induction procedure as follows:

  1. upward {\nearrow} on {|A+B|}: assume the thm has been proved for all lower values of {|A+B|<n}, and for all admissible values of {|A|+|B|} and {|B|}; then we prove it holds for {|A+B|=n};
  2. downward {\searrow} on {|A|+|B|}: assume the thm has been proved for a fixed {|A+B|=n} and for all higher values {|A|+|B|>m} and all admissible values of {|B|}; then we prove it holds for {|A+B|=n} and {|A|+|B|=m};
  3. upward {\nearrow} on {|B|}: assume the thm has been proved for a fixed {|A+B|=n}, a fixed {|A|+|B|=m} and for all lower values of {|B|<\ell}; then we prove it holds for {|A+B|=n}, {|A|+|B|=m} and {|B|=\ell}.

To convince you that this way we get the inequality for all admissible values, notice that the base case {|A|+|B| = 2 |A+B|} is true by Lemma 4: since {\max(|A|,|B|) \leq |A+B|}, it follows that {|A|=|B|=|A+B|}, and then {B} is contained in a coset of {\mathrm{Sym}_G (A)} and in particular {|B|\leq |\mathrm{Sym}_G (A)|}; we also get that {A+B} is a translate of {A}, therefore {\mathrm{Sym}_G (A) = \mathrm{Sym}_G (A+B)}. Then {|A+B|=|A| \geq |A|+|B|-|\mathrm{Sym}_G (A+B)|}.
Proof: The proof branches into multiple cases. A checkmark symbol {\checkmark} indicates the leaf is terminal, without further branching (under the specific hypothesis of the branch the leaf is in).

Case 1: suppose {\mathrm{Sym}_G (A+B) \neq \{0\}}. In this case we can reduce to a smaller {|A+B|} by quotienting out the symmetries: let {F :=\mathrm{Sym}_G (A+B)}, then consider sets {(A+F) / F, (G+F)/F} in {G/F}: their Minkowski sum is

\displaystyle (A+F)/F + (B+F)/F = (A+B+F)/F = (A+B)/F,

which has cardinality strictly smaller than {|A+B|}; then by induction hypothesis (1.) it is

\displaystyle \left|(A+B)/F\right|\geq \left|(A+F)/F\right|+\left|(B+F)/F\right| -1,

and we recover what we want upon multiplying by {|F|}. {\checkmark}

Case 2: suppose {\mathrm{Sym}_G (A+B) = \{0\}}. We hav:= to prove then that {|A+B|\geq |A|+|B|-1}. We split in further cases.

Case 2.1: Suppose that for all {e \in A-B} we have that {B_e = B}. This means that {B \subset A-e} or equivalently {B+e \subset A} for all {e} and therefore {A+B-B \subseteq A}; by lemma 4 then {B} is in a coset of some subgroup {H \leq G} and {A} is a union of cosets of {H}. Then it is evident that {H \leq \mathrm{Sym}_G (A+B)}: for any {h\in H}, since {a = g + h'} for some {g}, {a+b+h = (g+h+h')+b \in A+B}. But since we are in case 2, then {H= \{0\}}, and therefore {|B|=1}, and then {|A+B|=|A|=|A|+|B|-1} and we’re done. \checkmark

Case 2.2: Suppose then that there exists {e \in A-B} s.t. {B_e \subsetneq B}, and amongst all such {e}‘s choose one that maximizes {|B_e|}. By translating we can assume without loss of generality that {e=0} and therefore work with

\displaystyle A_0 = A\cup B,

\displaystyle B_0 = A \cap B.

Since {|B_0|<|B|} and {|A_0+B_0|\leq |A+B|}, by induction hypothesis (3.) we have that

\displaystyle |A_0+B_0|\geq |A_0+H|+|B_0+H|-|H| \ \ \ \ \ (2)

 

where {H:=\mathrm{Sym}_G (A_0+B_0)}. We keep splitting in cases.

Case 2.2.1: Suppose that {A_0+B_0 = A+B}. Then {H=\{0\}}, and therefore

\displaystyle |A+B|\geq |A_0+B_0|\geq |A_0+H|+|B_0+H|-|H|=|A_0|+|B_0|-1=|A|+|B|-1. \quad \checkmark

Case 2.2.2: Suppose then that {A_0+B_0 \subsetneq A+B}. Define {C:=B_0+H}. Then we have

\displaystyle C+C = B_0 + B_0 + H \subset A_0 + B_0 + H = A_0 + B_0,

\displaystyle A+C = A + B_0 + H \subset A_0 + B_0+ H = A_0 + B_0,

\displaystyle B+ C = B + B_0 + H \subset A_0 + B_0+ H = A_0 + B_0;

it follows that

\displaystyle (A\cup C)+(B\cup C) = A+B,

and therefore we can replace {A} and {B} with {A\cup C} and {B\cup C} without altering {|A+B|}, but at most increasing {|A|+|B|}.

Case 2.2.2.1: Suppose {|A\cup C|+|B\cup C |>|A|+|B|}. Then by induction hypothesis (2.)

\displaystyle |A+B|\geq |A\cup C|+|B\cup C |-1>|A|+|B|-1. \quad \checkmark

Case 2.2.2.2: Suppose {|A\cup C|+|B\cup C |=|A|+|B|}, which implies that {C\subset A} and {C\subset B}, and in particular {C\subset A \cap B = B_0}. But this means {B_0 \subset B_0 + H \subset B_0} and therefore {C = B_0}. This means that {B_0} is a union of cosets of {H}.

Now, consider the pairs {(a,b) \in A\times B} s.t. {a+b \in (A+B)\backslash (A_0+B_0)}, and let {A'} be the set of all {a \in A} that appear in { (A+B)\backslash (A_0+B_0)} [3], which is non-empty by assumption. Fix one of these {\tilde{a} \in A'} and notice the following: {\tilde{a}\not\in B_0}, otherwise

\displaystyle \tilde{a} + B \subset B_0 + A_0,

and for the same reason the whole coset {\tilde{a}+H} is disjoint from {B_0}, as otherwise

\displaystyle \tilde{a}+H+B \subset B_0+H+A_0 = A_0+B_0

(in particular, {A'+H} is disjoint from {B_0}). If {\tilde{b} \in B} is s.t. {\tilde{a}+\tilde{b} \in (A+B)\backslash (A_0+B_0)}, then {\tilde{a}+\tilde{b}+H} is disjoint from {A_0+B_0}: indeed, if {\tilde{a}+\tilde{b}+h \in A_0 + B_0} then so would {\tilde{a}+\tilde{b}}, since {H} is the symmetry group of {A_0+B_0}. Then we’ve found an entire coset inside { (A+B)\backslash (A_0+B_0)}, and we can tighten the inequality { |A+B|> |A_0+B_0|} to

\displaystyle |A+B|\geq |A_0+B_0| + |(\tilde{a}+H)+\tilde{b}|\geq |A_0+B_0| + |((\tilde{a}+H)\cap A)+\tilde{b}| =|A_0+B_0| + |(\tilde{a}+H)\cap A|.

Moreover,

\displaystyle |A_0 + H| = |A_0| + |(A_0 + H)\backslash A_0| \geq |A_0| + |((A_0 + H)\backslash A_0)\cap (\tilde{a}+H)|,

and what is {((A_0 + H)\backslash A_0)\cap (\tilde{a}+H)}? It’s the set of elements of the form {a+h} or {b+h} that are not contained in either {A} or {B}, but are contained in {\tilde{a}+H} – equivalently, it’s the set of elements of the form {\tilde{a}+h} that are not contained in {A\cup B}. It’s clear {\tilde{a}+H} has {|H|} elements, and since {(\tilde{a}+H) \cap (A\cap B) = \emptyset} there is no double counting and we can write

\displaystyle |((A_0 + H)\backslash A_0)\cap (\tilde{a}+H)| = |H| - |(\tilde{a}+H)\cap A| - |(\tilde{a}+H)\cap B|.

Summing up, we have the inequalities

\displaystyle |A+B|\geq |A_0+B_0| + |(\tilde{a}+H)\cap A|,

\displaystyle |A_0 + H| \geq |A_0| + |H| - |(\tilde{a}+H)\cap A| - |(\tilde{a}+H)\cap B|.

Then, by (2) and the fact that {B_0 + H = B_0},

\displaystyle |A+B|\geq |A_0+B_0| + |(\tilde{a}+H)\cap A| \geq |A_0+H|+|B_0+H|-|H|+ |(\tilde{a}+H)\cap A|

\displaystyle \geq |A_0| + |H| - |(\tilde{a}+H)\cap A| - |(\tilde{a}+H)\cap B| + |B_0|-|H|+ |(\tilde{a}+H)\cap A|

\displaystyle = |A_0| + |B_0| - |(\tilde{a}+H)\cap B| = |A| + |B| - |(\tilde{a}+H)\cap B| .

We split into further cases.

Case 2.2.2.2.1: Suppose there exists {\tilde{a} \in A'} s.t. {|(\tilde{a}+H)\cap B|=1}. Then we’re done. {\checkmark}

Case 2.2.2.2.2: Suppose then {|(a+H)\cap B|>1} for all {a \in A'}. We must show we reach a contradiction. Define

\displaystyle A^a := (a+H) \cap A,

\displaystyle B^a := (a+H)\cap B.

Now we want to consider sums of the form {A^a - B^a + B^{a'}}. We split again.

Case 2.2.2.2.2.1: Suppose we can find {a,a' \in A'} s.t.

\displaystyle A^a - B^a + B^{a'} \not\subset A^{a'}.

First notice that since both elements of {A^a} and {B^a} are of the form {a+h} with {h\in H}, it follows that

\displaystyle A^a - B^a \subset H;

this means we can find an {\tilde{h} \in H } s.t. {B^{a'} + \tilde{h} \not\subset A^{a'}}, which in turn implies {B\not\subset A-\tilde{h}}: indeed, if this were the case, we’d have {b+\tilde{h} \in A} for all {b\in B} and in particular for those {b = a'+h}, but then {b+ \tilde{h} = a' + (h+\tilde{h}) \in (a'+H) \cap A = A^{a'}}. On the other hand, {A^{a} - B^{a} \subset A-B} too, thus we can take the {\tilde{h}}-transform of {A,B}. Consider {B_{\tilde{h}}}: since {B\not\subset A-\tilde{h}}, it is strictly contained in {B}. Moreover, since {A\cap B + H = A \cap B}, {A\cap B = B_0 \subset B_{\tilde{h}}}: indeed, if {x \in A\cap B} then {x + \tilde{h} \in A\cap B} too, and then {x = (x+\tilde{h})-\tilde{h} \in B \cap (A-\tilde{h}) = B_{\tilde{h}}}. Finally, {B_{\tilde{h}}} strictly contains {B_0}, since it contains {B \cap (a + H) \cap (((a+H)\cap A) - \tilde{h}) = B^a \cap (A^a - \tilde{h})\subset a+H}, and {a+H} is disjoint from {B_0} as seen above. Notice {B^a \cap (A^a - \tilde{h})} is non-empty, since {\tilde{h} = \tilde{a}-\tilde{b}} for some {\tilde{a} \in A^a} and {\tilde{b} \in B^a}, and thus {\tilde{b} = \tilde{a} - \tilde{h} \in B^a \cap (A^a - \tilde{h})}. Thus we’ve reached a contradiction, because {B_0} was assumed to have maximal cardinality. {\checkmark}

Case 2.2.2.2.2.2: Suppose then that

\displaystyle A^a - B^a + B^{a'} \subset A^{a'}

for all {a,a' \in A'}. Then {|A^a|\leq |A^{a'}|}, by interchanging {a} and {a'} we get that {|A^a| = |A^{a'}|} for all {a,a' \in A'}. This means that

\displaystyle |A^a - B^a + B^{a'}| = |A^{a}|,

which by Lemma 4, when {a=a'} implies that {B^a} is contained in a coset of {K:=\mathrm{Sym}_G (A^a)}. We show that all {B^a}‘s are contained in cosets of this {K}, and that {A^a} are all unions of cosets of this same {K}. Indeed, the above for {a \neq a'} implies (by Lemma 4 again) that {B^{a'}-B^a} is contained in a coset of {K}, but then {B^{a'}} must be contained in a coset of {K} as well: let {x \in B^{a'}}, {B^a \subset g + K} coset for some {g}, {g+k} an element of {B^a}, then {x-(g+k) = g' +k'} for some {k' \in K, g' \in G} and thus {x = (g'+g) + (k'+k)}, which proves that {x} belongs to a coset of {K}.

Since {B^a, B^{a'}} are contained in cosets of {K}, {A^a - B^a + B^{a'}} is a translate of {A^a}, and therefore for some {g\in G} it is {g+A^a \subset A^{a'}}, but they have the same cardinality and must therefore coincide – all {A^a}‘s are translates of each other. Since {A^a} is a union of cosets of {K}, so are its translates and therefore the {A^{a'}}‘s. Notice that {K \leq H}: indeed, {A^a = A \cap (a+H)} is contained in a coset of {H}, which then contains at least one coset of {K}. Thus {A^a + B} is a union of cosets of {K} for every {a \in A'}, and therefore so is {\bigcup_{a \in A'}{(A^a + B)}}, which contains {(A+B) \backslash (A_0 + B_0)} by definition of {A'}; moreover, by definition of {H}, {A_0 + B_0} is a union of cosets of {H} and thus a union of cosets of {K}. Therefore

\displaystyle A+B = \bigcup_{a \in A'}{(A^a + B)} \cup (A_0 + B_0)

is the union of cosets of {K}, and therefore {K \leq \mathrm{Sym}_G (A+B) = \{0\}}.

On the other hand, by assumption {|B^a| > 1} for all {a}, which implies {|K|>1}, and then we’ve reached a contradiction. {\checkmark} \Box

That was some tour de force.

2.4. Another lowerbound on {|A+A|}

We need one further lemma to conclude the proof.

Lemma 7 Let {\phi \, : \, \mathbb{Z} \rightarrow \mathbb{Z} / {N\mathbb{Z}}} be the quotient map, {A\subset \mathbb{Z}} be a finite set containing {0}. Define {\mu(x) := |A \cap \phi^{-1} (x)|}, where {x \in \mathbb{Z} / {N\mathbb{Z}}} (it’s the multiplicity of {x}). The minimum multiplicity is defined as {m:= \min_{x \in \phi(A)\backslash \{0\}}{\mu(x)}}. Then

\displaystyle |A+A| \geq |A| + |\phi(A)|(\mu (0) - 2 m) + |\phi(A+A)|(2m -1).

Notice that {\phi(A+A) = \phi(A) + \phi(A)} by linearity.

Proof: One can write

\displaystyle |A+A| = \sum_{n \in \mathbb{Z} / {N\mathbb{Z}}}{|\{a+b\, : \, a,b \in A, (a+b) \mod N = n\}|}

\displaystyle = \sum_{x \in \phi(A+A)}{|(A+A) \cap \phi^{-1}(x)|}.

If {\phi(a+b) = x}, it is by linearity {\phi(a) + \phi(b) = x}, and therefore if we let {\phi(a), \phi(b)} take all possible values we see that we can write

\displaystyle |(A+A) \cap \phi^{-1}(x)| = \sum_{y,z \in \phi(A) : y+z = x}{|(A \cap \phi^{-1}(y) )+ (A \cap \phi^{-1}(z))|};

we use as a lower bound of the sum the supremum of its terms, and thus

\displaystyle |A+A| = \sum_{x \in \phi(A+A)}{|(A+A) \cap \phi^{-1}(x)|} \geq \sum_{x \in \phi(A+A)}{\sup_{y,z \in \phi(A) : y+z = x}{|(A \cap \phi^{-1}(y) )+ (A \cap \phi^{-1}(z))|}},

and by (1) the inner term is bounded from below by {|A \cap \phi^{-1}(y) |+ |A \cap \phi^{-1}(z)|-1 = \mu(y) + \mu(z) - 1}. Thus the last sum is bounded from below by

\displaystyle \sum_{x \in \phi(A+A)}{\sup_{y,z \in \phi(A) : y+z = x}{\mu(y) + \mu(z) - 1}} = \sum_{x \in \phi(A+A)}{\left(\sup_{y,z \in \phi(A) : y+z = x}{\mu(y) + \mu(z) }\right)} - |\phi(A+A)|;

notice that {\mu(y) + \mu(z) \geq 2 m} for {y,z \neq 0}, and it is {y=0} iff {z = x \in \phi (A)}, so that the last sum is bound from below by

\displaystyle \sum_{x \in \phi(A)}{(\mu(0) + \mu(x))} + \sum_{x \in \phi (A+A) \backslash \phi(A)}{2m} - |\phi(A+A)|.

Since {\sum_{x \in \phi(A)}{\mu(x)} = |A|}, by expanding the sums and then collecting the terms we have what we want (notice {\phi(A+A) \supset \phi(A)} since {0 \in A}, and thus {| \phi (A+A) \backslash \phi(A)| = |\phi (A+A)| - |\phi(A)|}). \Box

2.5. Finally, the proof

Remember the statement of Freiman’s theorem: we assume {A+A} isn’t much larger than {A}, in particular {|A+A|< 3|A|-3}, and want to prove there exists an arithmetic progression {P} containing {A} and of controlled length (at most {|A+A|-|A|+1}: observe that {|P+P| = 2|P|-1}, so that if {A} is an arithmetic progression then the bound is tight).
Proof: Translate {A} so that {\min(A) = 0}. Fix {N:=\max(A)}, and suppose without loss of generality that {gcd(A) = 1} (otherwise, factor out the common divisor of the elements of {A} – which would be the step of the arithmetic progression). We claim that the arithmetic progression {P} that we’re looking for is exactly {P=\{0,1,\ldots, N\}} in this case. It certainly contains {A}, and it suffices to prove the bound {|P| \leq |A+A|-|A|+1} on the size {|P|=N+1}. We argue by contradiction, assuming that {N > |A+A|-|A|}.

Let {\phi} be the quotient map {\mathbb{Z} \rightarrow \mathbb{Z} / {N\mathbb{Z}}}. Notice that {|\phi(A)|=|A|-1}. You might guess what we’re gonna do now: we want to prove that {|A+A|\geq 3|A|-3}, thus reaching a contradiction, and we want to do so using the lowerbounds we’ve introduced above. In particular, by Lemma 7, since {\mu(0) = 2} (only {\max(A)=N} and {\min(A)=0} have the same remainder modulus {N}) and {m=1} (since all the other elements of {A} are mapped {1}-to-{1})

\displaystyle |A+A| \geq |A| + |\phi(A+A)|, \ \ \ \ \ (3)

 

from which it follows that {|\phi(A+A)| \leq |A+A|-|A| \leq 2|A|-4}, by the hypothesis of Freiman’s theorem. [4] In particular, by the assumption we have {|\phi(A+A)|<N}.

Moreover, by Kneser’s theorem 3,

\displaystyle |\phi(A+A)|\geq 2|\phi(A) + H | - |H|, \ \ \ \ \ (4)

 

where {H:= \mathrm{Sym}_{ \mathbb{Z} / {N\mathbb{Z}}}(\phi(A+A))}. By rearranging (4) we can say

\displaystyle |H| \geq 2 (|\phi(A) + H| - |A|)+4 = 2(|\phi(A)+H| - |\phi(A)|)+2. \ \ \ \ \ (5)

 

Thus we have {|H|\geq 2} and in particular {H} can’t be trivial, because we have {|\phi(A+A)|<N} too. This means there exists a number {N>h>1} s.t. {H = {h \mathbb{Z}}/{N \mathbb{Z}}}, and in particular it must be {h | N}. We want to apply Lemma 7 with {h} in place of {N} to conclude, i.e. with {\phi_h} quotient map {\mathbb{Z} \rightarrow \mathbb{Z} / {h\mathbb{Z}}}: this way we factor out the symmetry group of the projection of {A+A}, and basically reduce to the case {H=\{0\}}. But we have to find bounds for the quantities {\mu_h, m_h} first.

Observe that {\phi(A)\not\subset H}, since otherwise the elements of {A} would have greatest common divisor at least {h}, which we have ruled out. Therefore {\phi(A)} has elements in different cosets of {H} and in particular {\phi(A)+H} (which is made of cosets of {H}) contains at least two entire cosets (and {\phi_h (A)\geq 2}). It follows that, for {x+H} some non-trivial coset intersecting {\phi(A)},

\displaystyle |(H \cup (x+H))\cap \phi(A)|= |[H \cup (x+H)]\cap [(\phi(A)+H)\backslash ((\phi(A)+H)\backslash \phi(A))|

\displaystyle = |[H \cup (x+H)]\cap (\phi(A)+H)| - |[H \cup (x+H)]\cap [(\phi(A)+H)\backslash \phi(A)]|

\displaystyle \geq 2|H| - |(\phi(A)+H)\backslash \phi(A)|= 2|H| - |\phi(A)+H| + |\phi(A)|;

since {0} has multeplicity {2} w.r.t. {\phi}, we have

\displaystyle |\phi^{-1}(H \cup (x+H))\cap A| \geq 2|H| - |\phi(A)+H| + |\phi(A)| + 1,

which is

\displaystyle \mu_h (0) + m_h > 2|H| - t + 1, \ \ \ \ \ (6)

 

where {t:= |\phi(A)+H| - |\phi(A)|}. If you repeat the reasoning with only {x+H} in place of {H \cup (x+H)}, you get instead

\displaystyle m_h > |H| - t. \ \ \ \ \ (7)

 

By Kneser’s theorem we also have

\displaystyle |\phi_h (A+A)|\geq 2|\phi_h (A)| -1, \ \ \ \ \ (8)

 

because now {\phi_h (A+A)} has trivial symmetry group, as mentioned before.

Now we can start applying Lemma 7 with {\phi_h}. Thus

\displaystyle |A+A| \geq |A|+|\phi_h (A)|(\mu_h(0) - 2m_h) + |\phi_h(A+A)|(2m_h - 1)

\displaystyle \stackrel{(6)}{\geq} |A|+|\phi_h (A)|(2|H| - t + 1 - 3 m_h) + |\phi_h(A+A)|(2m_h - 1)

\displaystyle \stackrel{(8)}{\geq} |A|+|\phi_h (A)|(2|H| - t + 1 - 3 m_h) + 2|\phi_h (A)|(2m_h - 1) - (2m_h - 1)

\displaystyle = |A|+|\phi_h (A)|(2|H| - t - 1) - (|\phi_h (A)|-2) m_h + 1

\displaystyle \stackrel{(7)}{\geq} |A|+|\phi_h (A)|(2|H| - t - 1) + (|\phi_h (A)|-2) (|H|-t) + 1;

since {\phi_h (A) - 2 \geq 0}, we can bound {|H|-t \geq t +2} by (5), and therefore the above is bounded from below by

\displaystyle |A|+|\phi_h (A)|(2|H| - t - 1) + (|\phi_h (A)|-2) (t+2) + 1

\displaystyle = |A|+ 2|\phi_h (A)||H| -t |\phi_h (A)| - |\phi_h (A)| + t |\phi_h (A)| + 2|\phi_h (A)| - 2t - 3

\displaystyle = |A| + 2|\phi_h (A)||H| +|\phi_h (A)| - 2t - 3.

Since {|\phi_h (A)||H|= |\phi(A)+H| = |A|+t -1}, the last expression is equal to

\displaystyle = |A| + 2(|A|+t -1) +|\phi_h (A)| - 2t - 3

\displaystyle = 3|A| + 2t -2 + |\phi_h (A)| - 2t -3 \geq 3|A|-3,

where the last inequality is {|\phi_h (A)|\geq 2} again. Thus we’ve proved {|A+A|\geq 3|A|-3}, thus reaching a contradiction. \Box

Footnotes:

[1] To be precise, {A} is essentially contained in {I}, in the sense that {|A\backslash I|=0}.
[2] one doesn’t need Kneser’s thm to prove this, it follows from the ordering of the integers.
[3] i.e. there exists {b\in B} s.t. {a+b\not\in A_0 + B_0}
[4] Notice however we don’t strictly need the lemma for this, because {\phi(A+A)} can’t have more than {|A+A|} elements, being a projection, and elements of the form {\min(A)+b} and {\max(A)+b} have the same remainder modulus {N}.

Refereces:

[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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s