Balog-Szemerédi-Gowers theorem

If a finite set $A$ has at least $\eta |A{|}^3$ additive quadruples, then it contains $A^{\prime }$ with $|A^{\prime }|\ge {\eta }^C|A|$ and $|A^{\prime }+A^{\prime }|\le {\eta }^{-C}|A^{\prime }|$ for an absolute constant $C$.

There are absolute $c,C>0$ such that finite sets $A,B$ of size $n$, a bipartite graph of density at least $\delta$, and a restricted sumset of size at most $Kn$ yield subsets $A^{\prime },B^{\prime }$ with $|A^{\prime }|,|B^{\prime }|\ge c{\delta }^{C}n$ and $|A^{\prime }+B^{\prime }|\le C{\delta }^{-C}{K}^{C}n$. A graph formed by popular representations of sums turns this into the usual large-additive energy form of the Balog-Szemerédi-Gowers theorem.

Let a bipartite graph have $n$ vertices in each class and at least $\rho n^2$ edges. There is a subset $B$ of one class with $|B|\ge \rho n/4$ such that every pair of its vertices has at least ${\rho }^5{n}^3/4096$ four-edge walks between them. Declare a pair of left vertices bad if it has fewer than $\tau n$ common neighbours, with $\tau ={\rho }^2/32$. For a random right vertex $y$, put $U=N(y)$ and let $b(U)$ count ordered bad pairs inside $U$. Then $\mathbb{E}|U|\ge \rho n$ and $\mathbb{E}b(U)\le \tau n^2$. Some $y$ has $|U|-16b(U)/(\rho n)\ge \rho n/2$, so $|U|\ge \rho n/2$ and $b(U)\le |U{|}^2/8$. Remove vertices with more than $|U|/4$ bad partners. At least half remain. For any two remaining vertices, at least $|U|/2$ middle vertices are good partners of both. Each supplies at least $(\tau n{)}^2$ walks, giving the bound.

If $E(A)\ge \theta |A{|}^3$, a subset $B\subseteq A$ satisfies $|B|\ge c_{\theta }|A|$ and $|B-B|\le K_{\theta }|B|$. A dependent random choice argument in the popular sum graph finds many four-edge paths representing each member of the difference set. The Petridis minimal-growth lemma then bounds all higher iterated sumsets and difference sets.