 Solution

For a finite nonempty set $A$, its additive energy iswhere $r_{A+A}(s)$ counts ordered representations. Since ${\sum }_s{r}_{A+A}(s)=|A{|}^2$, Cauchy-Schwarz givesThus $|A+A|\le K|A|$ implies $E(A,A)\ge |A{|}^3/K$: a small doubling constant forces many additive quadruples.

A polynomial form of the Balog-Szemerédi-Gowers theorem gives the converse after passing to a subset. There are absolute constants $c,C>0$ such that if $E(A,A)\ge \eta |A{|}^3$, $0<\eta \le 1$, then some $A^{\prime }\subseteq A$ satisfiesThe exponent and constants here need not be optimal.

Precisely, a graph form of the Balog-Szemerédi-Gowers theorem states the following. If $A,B$ are finite sets of size $n$ in an abelian group, $\Gamma \subseteq A\times B$ has at least $\delta n^2$ edges, and its restricted sumsethas size at most $Kn$, then there are $A^{\prime }\subseteq A$, $B^{\prime }\subseteq B$ with $|A^{\prime }|,|B^{\prime }|\ge c{\delta }^{C}n$ andThese are uniform absolute constants, valid for $0<\delta \le 1$ and $K\ge 1$.

To apply this theorem to additive energy, let $n=|A|$ and retain the sums with $r_{A+A}(s)\ge \eta n/2$. The discarded sums contribute at most $(\eta n/2){\sum }_{s}r(s)=\eta n^3/2$ to the additive energy. Since $r(s)\le n$, the retained pairs number at least $\eta n^2/2$. There are at most $2n/\eta$ retained sums. They therefore define a bipartite graph of density at least $\eta /2$ with restricted sumset size at most $2n/\eta$. The graph theorem supplies large subsets $A^{\prime },B^{\prime }$ with polynomially bounded $|A^{\prime }+B^{\prime }|$.

For completeness, turn this cross-sumset bound into a doubling constant bound. The Ruzsa triangle inequality gives $|A^{\prime }-A^{\prime }|\le |A^{\prime }+B^{\prime }{|}^2/|B^{\prime }|$. If $D=|A^{\prime }-A^{\prime }|/|A^{\prime }|$, the Plünnecke inequality, applied to the pair $A^{\prime },-A^{\prime }$, gives $|A^{\prime }+A^{\prime }|\le D^2|A^{\prime }|$. The minimal-growth proof below in Question 5 applies to arbitrary finite pairs and proves this particular expansion estimate as well. All losses are fixed powers of ${\eta }^{-1}$, proving the displayed converse after increasing $C$.

The requested dense bipartite common-neighbour lemma is a dependent random choice assertion. Call an ordered pair in $V^2$ bad when it has fewer than $ϵn$ common neighbours. Choose $w\in W$ uniformly, and put $S=N(w)\subseteq V$. ThenFor each bad pair, the probability that both endpoints lie in $S$ is its number of common neighbours divided by $n$, which is less than $ϵ$. Thus the expected number $b(S)$ of bad ordered pairs in $S^2$ is at most $ϵm^2$. ConsequentlyChoose a neighbourhood $V^{\prime }=S$ attaining at least this expectation. It has $|V^{\prime }|\ge \delta m/\sqrt{2}\ge \delta m/2$, andHence at least the proportion $1-2ϵ/{\delta }^2$ of its ordered pairs have at least $ϵn$ two-edge connections. As usual these connections are counted by common neighbours, including a return walk for a diagonal ordered pair; assume $\delta >0$, as the formula requires.

The relevance to the graph theorem is that many two-edge connections turn a sparse collection of permitted sums into additive control on a large vertex subset. On a connection $a\to b\to a^{\prime }$, $a-a^{\prime }=(a+b)-(a^{\prime }+b)$ expresses a difference using two elements of the restricted sumset. The abundance of connections, followed by standard cleaning and further path counting, bounds the number of differences without throwing away most vertices. This is the role of dependent random choice in obtaining polynomial losses in the graph form of the Balog-Szemerédi-Gowers theorem.