On an almost all version of the Balog-Szemeredi-Gowers theorem

On an almost all version of the Balog-Szemeredi-Gowers theorem, Discrete Analysis 2019:12, 18 pp.

A central theorem in additive combinatorics, Freiman’s theorem, sometimes known as the Freiman-Ruzsa theorem since a very influential second proof was given by Imre Ruzsa, states that a set $A$ of integers with the property that the sumset $A+A$ has size at most $C$ times the size of $A$ is necessarily a large subset of a low-dimensional arithmetic progression. To give an indication of what this means, a normal arithmetic progression is one-dimensional, a two-dimensional progression is a “progression of progressions” (such as 1, 11, 21, 31, 41, 5, 15, 25, 35, 45, 9, 19, 29, 39, 49, 13, 23, 33, 43, 53), a three-dimensional progression is a progression of progressions of progressions, and so on, and the claim is that for every $C$ there exist $c>0$ and $k$ depending on $C$ only such that if $|A+A|\leq C|A|$, then $A$ is contained in a progression $P$ of dimension at most $k$ such that $|A|\geq c|P|$, where $c$ and $k$ depend on $C$ only.

Freiman’s theorem has many uses, but it often happens that one is not handed the hypothesis $|A+A|\leq C|A|$ on a plate. In particular, one often obtains a “statistical” version of the hypothesis, which says that there is a set $S$ of size at most $C|A|$ such that for at least $\eta|A|^2$ pairs $(a,b)\in A^2$ the sum $a+b$ belongs to $S$. (It is an exercise to show that this is equivalent, up to the values of the parameters, to the assertion that there are at least $\theta|A|^3$ quadruples $(a,b,c,d)\in A^4$ such that $a+b=c+d$.) Fortunately, there is a theorem of Balog and Szemerédi that states that if $A$ satisfies this weaker hypothesis, then there is a large subset of $A$ that has a small sumset, so we can at least conclude that $A$ has a large structured subset (and in fact cannot conclude any more, since the union of an arithmetic progression and an arbitrary set of comparable size will satisfy the weaker hypothesis). A second proof of the Balog-Szemerédi theorem, which avoided a use of Szemerédi’s regularity lemma and yielded power-type bounds, was given by Gowers.

This paper examines the following rather natural question: what happens if the parameter $\eta$ above is very close to 1? That is, what can we say about $A$ if only a few sums lie outside a set of size at most $C|A|$? We might hope that in such a case, the subset of $A$ we find with a small sumset can be taken to be almost all of $A$. In slogan form, “If $A$ almost has a small sumset, then almost all of $A$ has a small sumset.”

This turns out to be true. That is, for every $\epsilon>0$ and every $C$ there exists $\delta>0$ such that if there is a set of pairs of size at least $(1-\delta)|A|^2$ that give rise to at most $C|A|$ sums, then there is a subset $A'\subset A$ of size at least $(1-\epsilon)|A|$ such that $|A'+A'|\leq (C+\epsilon)|A|$.

The proof of this result is harder than one might expect. In particular, it relies on the arithmetic removal lemma of Ben Green, which itself is based on an important variant of Szemerédi’s regularity lemma that he formulated and proved. However, it seems that this difficulty is at least to some extent necessary. Although there may perhaps be some way of avoiding regularity, a truly simple proof would be likely to give a power dependence of $\delta$ on $\epsilon$ and $C$, but the author gives an example (inspired by Behrend’s construction of a large AP-free set, but not directly derived from it) that demonstrates that the dependence is worse than a power.