Past exam of the mathematics course of the University of Cambridge / 2024 / iii / Paper 129 / 1

The Plünnecke-Ruzsa inequality says that if $A,B$ are finite nonempty subsets of an abelian group andthen for all nonnegative integers $m,n$,

Choose a nonempty $X\subseteq A$ minimizingthen $K^{\prime }\le K$. We first prove the Petridis minimal-growth lemmafor every finite $C$, by induction on $|C|$. Remove $c\in C$, write $C^{\prime }=C\setminus \{c\}$, and letThe new points contributed to $X+C$ by $X+c$ are exactly $|X\setminus X^{\prime }|$. Moreover, $X^{\prime }+B+c\subseteq (X+B+c)\cap (X+B+C^{\prime })$, soThe induction hypothesis, the identity $|X+B|=K^{\prime }|X|$, and minimality, which gives $|X^{\prime }+B|\ge K^{\prime }|X^{\prime }|$, yieldIteration with $C=(r-1)B$ gives

Finally, the Ruzsa triangle inequality givesas required.

Construct $X\subseteq B$ greedily. Begin with one element of $B$. While some $b\in B$ satisfiesadjoin $b$ to $X$. The first translate contributes $|A|$ points to $A+X$, and each later translate contributes at least $|A|/2$ new points. Thereforeand hence

When the process stops, every $b\in B$ satisfies $|(A+b)\cap (A+X)|>|A|/2$. Each point in this intersection has the formand therefore gives a triple $(x,a,a^{\prime })\in X\times A\times A$ with $b=a-a^{\prime }+x$. Distinct intersection points give distinct $a^{\prime }$, so there are more than $|A|/2$ such triples.

For $b,b^{\prime }\in B$, the corresponding sets of possible $a^{\prime }\in A$ both have size greater than $|A|/2$ and hence intersect. Using a common $a^{\prime }$ givesso $b-b^{\prime }=a-c+x-y$. Thus

Assume $|A+A|\le K|A|$ and putThis set is symmetric, contains zero, and the Plünnecke-Ruzsa inequality givesIt also contains $A-A$, so for every $x\in A$,

To control $H+H=4A-4A$, observe again by Plünnecke-Ruzsa thatApply the Ruzsa covering lemma with $S=H+H$ and $T=A$. There is a set $Y$ with $|Y|\le K^9$ such thatConsequently $H$ is a $K^9$-approximate group. Taking a sufficiently large absolute constant $C$ gives