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.

Continue reading