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

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|, 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)|.

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