Past exam of the mathematics course of the University of Cambridge / 2021 / iii / Paper 129 / 4

A bijection $\varphi :A\to B$ is a Freiman s-isomorphism when, for every $a_1,\dots ,a_s,a_1^{\prime },\dots ,a_s^{\prime }\in A$,holds if and only if

Because $A\subseteq {\mathbb{Z}}^2$ is finite, choose $R$ with $A\subseteq [-R,R{]}^2$ and an integer $M>2sR$. DefineAn equality of $s$-term sums in ${\mathbb{Z}}^2$ plainly gives equality after applying this linear map. Conversely, equality of the images giveswhere $|{\Delta }_x|\le 2sR<M$. Therefore ${\Delta }_x=0$, and then ${\Delta }_y=0$. The same estimate with one term on each side shows that $\varphi$ is injective on $A$. Hence $\varphi$ is a Freiman s-isomorphism from $A$ to the subset $\varphi (A)\subseteq \mathbb{Z}$.

The Dense Bogolyubov-Ruzsa lemma says that, for every $\alpha >0$, if $S$ has density at least $\alpha$ in a cyclic group of prime order, then $2S-2S$ contains a proper generalized arithmetic progression of rank $O_{\alpha }(1)$ and size ${\Omega }_{\alpha }(|G|)$.

Now suppose $A\subseteq \mathbb{Z}$ and $|A+A|\le K|A|$. The Ruzsa modelling lemma, taken at a sufficiently high fixed Freiman order, supplies $A^{\prime }\subseteq A$ with $|A^{\prime }|\ge |A|/2$ and a Freiman isomorphism from $A^{\prime }$ to a subset $S\subseteq \mathbb{Z}/q\mathbb{Z}$, where $q$ is prime, $q=O_K(|A|)$, and $|S|/q{\gg }_{K}1$. Apply the dense Bogolyubov-Ruzsa lemma to $S$ and transfer the resulting progression back through the Freiman model. We obtain a proper progressionof rank $O_K(1)$ and size $|P_0|{\gg }_K|A|$.

The Plünnecke-Ruzsa inequality givesThere are $|A||P_0|$ pairs $(a,p)$ with $a\in A$ and $p\in P_0$, distributed among the sums in $A+P_0$. Some $x$ therefore has at least $K^{-5}|P_0|{\gg }_K|A|$ representations $x=a+p$. Equivalently,Set $P=x-P_0$. Translation and negation preserve properness and rank. Moreover $P_0\subseteq 2A-2A$ and another use of Plünnecke gives $|P|\le K^4|A|$. Thusas required.

The Balog-Szemerédi-Gowers theorem states that if a finite set $A$ has at least $\delta |A{|}^3$ additive quadruples, then it has a subset $A^{\prime }\subseteq A$ such thatwhere $C$ is an absolute constant.

Consider the graphThe hypothesis says exactly that $\Gamma$ has at least $\delta N^3$ additive quadruples. By the Balog-Szemerédi-Gowers theorem, it contains ${\Gamma }^{\prime }$ with $|{\Gamma }^{\prime }|{\gg }_{\delta }N$ and $|{\Gamma }^{\prime }+{\Gamma }^{\prime }|{\ll }_{\delta }|{\Gamma }^{\prime }|$.

Part b gives a Freiman s-isomorphism from ${\Gamma }^{\prime }$ to a set $D\subseteq \mathbb{Z}$, where it is enough to take any fixed $s\ge 2$. The set $D$ has bounded doubling, with a bound depending only on $\delta$. Part c therefore provides a proper generalized arithmetic progression $Q$ of rank $O_{\delta }(1)$ such that

Write $Q$ as a proper parameter box. Since $|Q|{\gg }_{\delta }N$, one of its $O_{\delta }(1)$ side lengths tends to infinity with $N$. Averaging over all lines parallel to that side gives a line on which $D\cap Q$ has density bounded below in terms of $\delta$. The Szemerédi theorem quoted in the question then gives, once $N$ is sufficiently large in terms of $k$ and $\delta$, a nonconstant $k$-term arithmetic progression in $D$.

The inverse Freiman isomorphism sends it to a $k$-term arithmetic progression in ${\Gamma }^{\prime }\subseteq \Gamma$, because each relation between three consecutive terms is an additive-quadruple relation. Write this progression asIts first-coordinate difference cannot be zero: the graph of a function has only one point above each $x$. Hence $d\ne 0$. On the nonconstant progressionwe haveTaking $a=e/d$ and $b=y_0-(e/d)x_0$, both in $\mathbb{Q}$, proves the claim.