Past exam of the mathematics course of the University of Cambridge / 2001 / iii / Paper 76 / 4 / i / Solution

One quantitative form of the Balog-Szemerédi-Gowers theorem is: if a nonempty finite set $A$ in an abelian group has $|A|=n$ and additive energy $E(A)\ge \eta n^3$, where $0<\eta \le 1$, then there is $B\subseteq A$ with $|B|\ge c_{\eta }n$ and both $|B-B|$ and $|B+B|$ bounded by $K_{\eta }|B|$. The constants depend only on $\eta$. We prove explicit, nonoptimal polynomial bounds, thereby proving the required Balog–Szemerédi statement.

Let $r(s)=|\{(a,a^{\prime })\in A^2:a+a^{\prime }=s\}|$. Then $E(A)={\sum }_{s}r(s{)}^2$. Declare $S=\{s:r(s)\ge \eta n/2\}$ to be the set of popular sums. The remaining sums contribute at most $(\eta n/2){\sum }_{s}r(s)=\eta n^3/2$. Since $r(s)\le n$, it follows that ${\sum }_{s\in S}r(s)\ge \eta n^2/2$. Also $|S|\le 2n/\eta$. Form a bipartite graph on two copies of $A$, joining $a$ to $a^{\prime }$ when $a+a^{\prime }\in S$. Its density is at least $\rho =\eta /2$.

We prove the needed four-step path lemma for a dense bipartite graph. Call an ordered pair of left vertices bad if its number of common right neighbors is less than $\tau n$, where $\tau ={\rho }^2/32$. For a uniformly chosen right vertex $y$, let $U=N(y)$ and let $b(U)$ count bad ordered pairs in $U^2$. ThenConsequently some $y$ satisfiesFor this $U$, $|U|\ge \rho n/2$ and $b(U)\le \rho n|U|/16\le |U{|}^2/8$. Delete vertices having more than $|U|/4$ bad partners in $U$. At most half are deleted; the retained set $B$ has $|B|\ge |U|/2\ge \rho n/4$. For any $a,b\in B$, at least $|U|/2$ middle vertices $u\in U$ are good partners of both. Each such $u$ supplies at least $(\tau n{)}^2$ walks $a,v,u,w,b$ of four edges. Hence every pair in $B$ has at leastsuch walks. Repetition of vertices is allowed; it does not affect the counting argument.

Each walk has edge labelsall in $S$, and $a-b=s_1-s_2+s_3-s_4$. For a fixed pair $a,b$, these four labels determine $v,u,w$, so distinct walks have distinct label quadruples. For each element of $B-B$, fix one representing pair $a,b$. Label quadruples for distinct differences cannot overlap. ThereforeUsing $\rho =\eta /2$ and $|S|\le 2n/\eta$ yieldsThis proves the small-difference-set form of the Balog-Szemerédi-Gowers theorem. To obtain a small sumset too, write $K=2^{24}{\eta }^{-10}$ and apply the already proved Plünnecke inequality to starting set $-B$ and summand set $B$. Some nonempty $X\subseteq -B$ has $|X+2B|\le K^2|X|$. For any fixed $x\in X$, $x+2B\subseteq X+2B$, whence $|B+B|\le K^2|B|$. Thus the conventional small-sumset conclusion also follows with constants depending only on $\eta$.