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

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$.

For $k\ge 2$, the following precise cardinality-controlled cyclic Freiman model suffices. If $A\subseteq \mathbb{Z}$ is nonempty, $|A|=n$ and $D=kA-kA$ has $|D|\le Cn$, there is $A^{\prime }\subseteq A$ withHere ${\cong }_k$ means a bijection preserving and reflecting all equalities of $k$-term sums, a Freiman s-isomorphism of order $s=k$. The same construction works for $k=1$ if only injectivity is needed.

Choose an auxiliary prime $P$ larger than $N$ and every nonzero absolute value in $D$, and large enough to embed the finite set $A$ injectively modulo $P$. Multiply its residues by a uniformly chosen nonzero residue $u$. For a fixed $d\in D\setminus \{0\}$, $ud$ is uniform among the $P-1$ nonzero residues. The forbidden residues areof number at most $2(P-1)/N$. The union bound says that the probability some nonzero $d\in D$ enters $\mathcal{F}$ is at most $2(|D|-1)/N<1$. Fix a multiplier avoiding every forbidden event.

Let $\tilde{a}\in \{0,\dots ,P-1\}$ represent $ua(\mathrm{mod}P)$. Partition that range into $k+1$ half-open intervals of length $P/(k+1)$ and retain the most populated interval; it supplies $A^{\prime }$ with $|A^{\prime }|\ge n/(k+1)$. Define the model map by $\theta (a)=\tilde{a}(\mathrm{mod}N)$. For two $k$-term sums of retained representatives, their difference $T$ has $|T|<P$. If the original sums are equal, then $T\equiv 0(\mathrm{mod}P)$, hence $T=0$, so the model preserves the equality.

Conversely, if the model sums are equal, then $T$ is a multiple of $N$. If their original difference $d\in D$ were nonzero, it would satisfy $ud\equiv T(\mathrm{mod}P)$ with $0<|T|<P$, contradicting the forbidden-event choice. If $T=0$ directly, $ud\equiv 0$ implies $d=0$ too by the choice of $P$. Thus the equality is reflected. Padding equal one-term images with $k-1$ copies of a fixed retained element shows that the map is injective. This proves the Freiman s-isomorphism and the claimed bound on the cyclic modulus, independently of the diameter of $A$.

Let $T_3(A)$ count ordered solutions $a+c=2b$ in $A^3$, including the trivial ones. The hypothesis gives $T_3(A)\ge c{n}^2$. Its relation to additive energy is the promised easy Fourier step. Translate $A$ into $[0,M]$ and embed it in an odd prime cyclic group of order $P>4M$. No relevant integer equality wraps modulo $P$. With the unnormalized Fourier transform $\hat{f}(r)={\sum }_x{1}_A(x)e(-rx/P)$, character orthogonality givesSince multiplication by $2$ permutes the characters, Cauchy-Schwarz and Parseval identity on a finite group implyThus $E(A)\ge c^2{n}^3$. Equivalently, one can apply Cauchy-Schwarz directly to $T_3(A)={\sum }_{b\in A}{r}_{A+A}(2b)$.

By part (i), some $B\subseteq A$ has $|B|\ge c_1(c)n$ and $|B+B|\le K(c)|B|$. Part 3(ii) then bounds $|2B-2B|\le K(c{)}^4|B|$. Apply part (ii) with $k=2$: there is $B^{\prime }\subseteq B$, $|B^{\prime }|\ge |B|/3$, Freiman 2-isomorphic to a subset $C\subseteq {\mathbb{Z}}_N$ with $N\le 4K(c{)}^4|B|+1$. Consequently $C$ has a positive subset density depending only on $c$, and $N$ tends to infinity with $n$ because $N\ge |B^{\prime }|$.

View the representatives of $C$ as a subset of $\{0,\dots ,N-1\}$. The assumed four-term case of Szemerédi's theorem gives four distinct integer representatives in arithmetic progression once $n$ is sufficiently large in terms of $c$. If their preimages are $b_0,b_1,b_2,b_3$, the two model equalitieslift through the Freiman 2-isomorphism to the same equalities in $\mathbb{Z}$. Hence their consecutive differences agree; injectivity makes the common difference nonzero. Therefore $A$ contains a nonconstant four-term arithmetic progression. This proves dense three-term progressions force four-term progressions without an assumption that $A$ initially lies in a short interval.