Balog–Szemerédi–Gowers theorem

Remarks

The converse direction is easy: if $\abs{A + B} \le Kn$, then Cauchy–Schwarz gives $E(A, B) \ge n^4 / (Kn) = n^3/K$. Large energy alone does not give a small sumset for the whole sets. For example, let $A$ be the union of an arithmetic progression of length $n/2$ and $n/2$ random-looking integers. Then $E(A, A)$ is at least of order $n^3$, but $\abs{A + A}$ is of order $n^2$; the theorem finds the progression part. The proof is graph-theoretic. One forms the bipartite graph on $A \cup B$ with an edge $ab$ when $a + b$ is a popular sum. A dependent-random-choice argument then finds $A'$ and $B'$ joined by many paths of length three, which bounds $\abs{A' + B'}$. Balog and Szemerédi proved the theorem first, and Gowers obtained polynomial dependence on $K$.

Going deeper

For a student

The theorem lets one pass from a statistical statement, large energy, to a combinatorial one, a small sumset for large subsets. After that, Freiman's theorem gives structure. Gowers used this chain in his quantitative proof of Szemerédi's theorem.