Proof. Let $A=\{a_1,a_2,\dots ,a_n\}$ with $a_1<a_2<\cdots <a_n$. Then

$$a_1+a_1<a_1+a_2<a_1+a_2<\cdots <a_1+a_n<a_2+a_n<\cdots <a_n+a_n,$$

so $|A+A|\ge 2|A|-1$. But we could also have written

$$a_1+a_1<a_1+a_2<a_2+a_2<a_2+a_3<a_2+a_4<\cdots <a_2+a_n<a_3+a_n<\cdots <a_n+a_n.$$

When $|A+A|=2|A|-1$, these two orderings must be the same. So $a_2+a_i=a_1+a_{i+1}$ for all $i=2,\dots ,n-1$. □

Proof. Assume $|A|+|B|\le p+1$. Without loss of generality assume that $1\le |A|\le |B|$ and that $0\in A$. Apply induction on $|A|$. The case $|A|=1$ is trivial. Suppose $|A|\ge 2$, and let $0\ne a\in A$.

Since $\{a,2a,3a,\dots ,(p-1)a,pa\}=\mathbb{Z}∕p\mathbb{Z}$ and $|A|+|B|\le p+1$, there must exist $m\ge 0$ such that $ma\in B$ but $(m+1)a\notin B$. Let $B^{\prime }=B-ma$, so $0\in B^{\prime }$, $a\notin B^{\prime }$, $|B^{\prime }|=|B|$.

But $1\le |A\cap B^{\prime }|<|A|$, so the inductive hypothesis applies to $A\cap B^{\prime }$ and $A\cup B^{\prime }$. Since

$$(A\cap B^{\prime })+(A\cup B^{\prime })\subseteq A+B^{\prime },$$

we have

$$|A+B|=|A+B^{\prime }|\ge |(A\cap B^{\prime })+(A\cup B^{\prime })|\ge |A\cap B^{\prime }|+|A\cup B^{\prime }|+1=|A|+|B|+1.\square$$

Proof. Observe that

$$|B|\cdot |A-C|\le |A-B|\cdot |B-C|.$$

Indeed, writing each $d\in A-C$ as $d=a_d-c_d$ with $a_d\in A$, $c_d\in C$, the map

$$\begin{array}{llll}\hfill \varphi :B\times (A-C)& \to (A-B)\times (B-C)& \hfill & \\ \hfill (b,d)& \mapsto (a_d-b,b-c_d)& \hfill & \end{array}$$

is injective. The triangle inequality now follows from the definition. □

Proof. Choose a non-empty subset $A^{\prime }\subseteq A$ such that the ratio $\frac{|A^{\prime }+B|}{|A^{\prime }|}$ is minimised, and call this ratio $K^{\prime }$. Then $|A^{\prime }+B|=K^{\prime }|A^{\prime }|$, $K^{\prime }\le K$, and $\forall A^{″}\subseteq A$, $|A^{″}+B|\ge K^{\prime }|A^{″}|$.

Claim: For every finite $C\subseteq G$, $|A^{\prime }+B+C|\le K^{\prime }|A^{\prime }+C|$.

Let’s complete the proof of the theorem assuming the claim. We first show that $\forall m\in {\mathbb{N}}_0$, $|A^{\prime }+mB|\le {K{}^{\prime }}^m|A^{\prime }|$. Indeed, the case $m=0$ is trivial, and $m=1$ is true by assumption. Suppose $m>1$ and the inequality holds for $m-1$. By the claim with $C=(m-1)B$, we get

$$|A^{\prime }+mB|=|A^{\prime }+B+(m-1)B|\le K^{\prime }|A^{\prime }+(m-1)B|\le {K{}^{\prime }}^m|A^{\prime }|.$$

But as in the proof of Ruzsa’s triangle inequality, $\forall l,m\in {\mathbb{N}}_0$, we can show

$$|A^{\prime }||lB-mB|\le |A^{\prime }+lB||A^{\prime }+mB|\le {K{}^{\prime }}^l|A^{\prime }|{K{}^{\prime }}^m|A^{\prime }|={K{}^{\prime }}^{l+m}|A^{\prime }{|}^2.$$

Hence $|lB-mB|\le {K{}^{\prime }}^{l+m}|A^{\prime }|\le {K{}^{\prime }}^{l+m}|A|$, which completes the proof (assuming the claim).

We now prove the claim by induction on $|C|$. When $|C|=1$ the statement follows from the assumptions. Suppose the claim is true for $C$, and consider $C^{\prime }=C\cup \{x\}$ for some $x\notin C$. Observe that

$$A^{\prime }+B+C^{\prime }=(A^{\prime }+B+C)+((A^{\prime }+B+x)\setminus (D+B+x))$$

with $D=\{a\in A^{\prime }:a+B+x\subseteq A^{\prime }+B+X\}$.

By definition of $K^{\prime }$, $|D+B|\ge K^{\prime }|D|$, so

$$\begin{array}{llll}\hfill |A^{\prime }+B+C^{\prime }|& \le |A^{\prime }+B+C|+|A^{\prime }+B+x|-|D+B+x|& \hfill & \\ \hfill & \stackrel{\text{IH}}{\le }{K}^{\prime }|A^{\prime }+C|+K^{\prime }|A^{\prime }|-K^{\prime }|D|& \hfill & \\ \hfill & =K^{\prime }(|A^{\prime }+C|+|A^{\prime }|-|D|)& \hfill & \end{array}$$

We apply this argument a second time, writing

$$A^{\prime }+C^{\prime }=(A^{\prime }+C)\bigsqcup ((A^{\prime }+x)\setminus (E+x))$$

where $E=\{a\in A^{\prime }:a+x\in A^{\prime }+C\}\subseteq D$. We conclude that

$$|A^{\prime }+C^{\prime }|=|A^{\prime }+C|+|A^{\prime }+x|-|E+x|\ge |A^{\prime }+C|+|A^{\prime }|-|D|$$

so

$$|A^{\prime }+B+C^{\prime }|\le K^{\prime }(|A^{\prime }+C|+|A^{\prime }|-|D|)\le K^{\prime }|A^{\prime }+C^{\prime }|,$$

proving the claim. □

Proof. Choose $X\subseteq 2A-A$ maximal such that the translates $x+A$ with $x\in X$ are disjoint. Such a set $X$ cannot be too large: $\forall x\in X$, $x+A\subseteq 3A-A$, so by Plunnecke’s Inequality, since $|3A-A|\le K^4|A|$,

$$|X||A|=\left|\bigcup _{x\in X}(x+A)\right|\le |3A-A|.$$

So $|X|\le K^4$. We next show

$$2A-A\subseteq X+A-A.\text{(∗)}$$

Indeed, if $y\in 2A-A$ and $y\notin X$, then by maximality of $X$, $y+A\cap x+A\ne \varnothing$ for some $x\in X$ (and if $y\in X$, then clearly $y\in X+A-A$).

It follows from ($\ast$) by induction that $\forall l\ge 2$,

$$lA-A\subseteq (l-1)X+A-A,\text{(∗∗)}$$

since

$$lA-A=A+\underset{\subseteq (l-2)X+A-A}{\underbrace{(l-1)A-A}}\subseteq (l-2)X+\underbrace{2A-A}\subseteq X+A-A\subseteq (l-1)X+A-A.$$

Now let $H\le {𝔽}_p^n$ be the subgroup generated by $A$, which we can write as

$$H=\bigcup _{l\ge 1}(lA-A)\stackrel{\mathrm{\text{(}}\ast \ast \text{)}}{\subseteq }Y+A-A$$

where $Y\le {𝔽}_p^n$ is the subgroup generated by $X$.

But every element of $Y$ can be written as a sum of $|X|$ elements of $X$ with coefficients amongst $0,1,\dots ,p-1$, hence $|Y|\le p^{|X|}\le p^{K^4}$. To conclude, note that

$$|U|\le |Y||A-A|\le p^{K^4}\le p^{K^4}{K}^2|A|,$$

where we use Plunnecke’s Inequality or even Ruzsa’s triangle inequality. □

Proof. Omitted, because the techniques are not relevant to other parts of the course. See Entropy Methods in Combinatorics next term. □

Proof. Define $r_{A+B}(x)=|\{(a,b)\in A\times B:a+b=x\}|$ (and notice that this is the same as $|A\cap (x-B)|$). Observe that

$$\begin{array}{llllll}\hfill E(A,B)& =|\{(a,a^{\prime },b,b^{\prime })\in A^2\times B^2:a+b=a^{\prime }+b^{\prime }\}& \hfill & & \hfill & \\ \hfill & =\sum _{x\in G}{r}_{A+B}{(x)}^2& \hfill & & \hfill & \\ \hfill & =\sum _{x\in A+B}{r}_{A+B}{(x)}^2& \hfill & & \hfill & \\ \hfill & \ge \frac{{\left(\sum _{x\in A+B}{r}_{A+B}(x)\right)}^2}{|A+B|}& \hfill & \text{by Cauchy-Schwarz}& \hfill & & \hfill & \end{array}$$

but

$$\begin{array}{llll}\hfill \sum _{x\in G}|A\cup (x-B)|& =\sum _{x\in G}\sum _{y\in G}{𝟙}_A(y){𝟙}_{x-B}(y)& \hfill & \\ \hfill & =\sum _{x\in G}\sum _{y\in G}{𝟙}_A(y){𝟙}_B(x-y)& \hfill & \\ \hfill & =|A||B|& \hfill & \end{array}$$

(As usual, ${𝟙}_A$ here means the indicator function). □

Proof. Let $U=\{x\in G:|A\cap (x+A)|\le \frac{1}{2}\eta |A|\}$. Then

$$\begin{array}{llll}\hfill \sum _{x\in U}|A\cap (x+A){|}^2& =\frac{1}{2}\eta |A|\sum _x|A\cap (x+A)|& \hfill & \\ \hfill & =\frac{1}{2}\eta |A{|}^3& \hfill & \\ \hfill & =\frac{1}{2}E(A)& \hfill & \end{array}$$

For $0\le i\le \lceil {\log }_2{\eta }^{-1}\rceil$, let

$$Q_i=\left\{x\in G:\frac{|A|}{2^{i+1}}<|A\cap (x+A)|\le \frac{|A|}{2^i}\right\},$$

and set ${\delta }_i={\eta }^{-1}{2}^{-2i}$. Then

$$\begin{array}{llllll}\hfill \sum _i{\delta }_i|Q_i|& =\sum _i\frac{|Q_i|}{{\eta }^{2^{2i}}}& \hfill & & \hfill & \\ \hfill & =\frac{1}{\eta |A{|}^2}\sum _i\frac{|A{|}^2}{2^{2i}}|Q_i|& \hfill & & \hfill & \\ \hfill & =\frac{1}{\eta |A{|}^2}\sum _i\frac{|A{|}^2}{2^{2i}}\sum _{x\notin U}{𝟙}_{\left\{\frac{|A|}{2^{i+1}}<|A\cap (x+A)|\le \frac{|A|}{2^i}\right\}}& \hfill & & \hfill & \\ \hfill & \ge \frac{1}{\eta |A{|}^2}\sum _{x\notin U}|A\cap (x+A){|}^2& \hfill & & \hfill & \\ \hfill & \ge \frac{1}{\eta |A{|}^2}\cdot \frac{1}{2}E(A)& \hfill & \left(\sum _{x\in U}|A\cap (x+A){|}^2\le \frac{1}{2}E(A)\right)& \hfill & & \hfill & \\ \hfill & =\frac{1}{2}|A|& \hfill & & \hfill \text{(}\ast \text{)}\end{array}$$

Let $S=\{(a,b)\in A^2:a-b\notin P_{c\eta }\}$. Then

$$\begin{array}{llll}\hfill \sum _i\sum _{(a,b)\in S}|(A-a)\cap (A-b)\cap Q_i|& \le \sum _{(a,b)\in S}\underset{=\underset{\text{by definition of }S}{\underbrace{|A\cap (a-b+A)|\le c\eta |A|}}}{\underbrace{|(A-a)\cap (A-b)|}}& \hfill & \\ \hfill & \le |S|\cdot c\eta |A|& \hfill & \\ \hfill & \le c\eta |A{|}^3& \hfill & \\ \hfill & \le 2c\eta |A{|}^2\cdot \frac{1}{2}|A|& \hfill & \\ \hfill & \stackrel{\mathrm{\text{(}}\ast \text{)}}{\le }2c\eta |A{|}^2\sum _i{\delta }_i|Q_i|& \hfill & \end{array}$$

Hence there exists $i_0$ such that

$$\sum _{(a,b)\in S}|(A-a)\cap (A-b)\cap Q_{i_0}|\le 2c\eta |A{|}^2{\delta }_{i_0}|Q_{i_0}|.$$

Let $Q=Q_{i_0}$, $\delta ={\delta }_{i_0}$, $\lambda =2^{-i_0}$. So

$$\sum _{(a,b)\in S}|(A-a)\cap (A-b)\cap Q|\le 2c\eta \delta |A{|}^2|Q|.\text{(∗∗)}$$

Find $x$ such that $X=|A\cap (A+x)|$ is large.

Given $x\in G$, let $X(x)=A\cap (x+A)$. Then

$${𝔼}_{x\in Q}|X(x)|=\frac{1}{|Q|}\sum _{x\in Q}|A\cap (x+A)|\ge \frac{1}{2}\lambda |A|.$$

Let $T(x)=\{(a,b)\in X{(x)}^2:a-b\notin P_{c\eta }\}$. Then

$$\begin{array}{llll}\hfill {𝔼}_{X\in Q}|T(x)|& ={𝔼}_{x\in Q}|\{(a,b)\in {(A\cap (\underset{x\in A-a\cap A-b}{\underbrace{x}}+A))}^2:a-b\notin P_{c\eta }\}|& \hfill & \\ \hfill & =\frac{1}{|Q|}\sum _{x\in Q}|\{(a,b)\in S:x\in A-a\cap A-b\}|& \hfill & \\ \hfill & =\frac{1}{|Q|}\sum _{(a,b)\in S}|(A-a)\cap (A-b)\cap Q|& \hfill & \\ \hfill & \le \frac{1}{|Q|}2c\eta |A{|}^2\delta |Q|& \hfill & \\ \hfill & =2c\eta \delta |A{|}^2& \hfill & \\ \hfill & =2c{\lambda }^2|A{|}^2& \hfill & \end{array}$$

Therefore,

$$\begin{array}{llll}\hfill {𝔼}_{x\in Q}|X(x){|}^2-{(16c)}^{-1}|T(x)|& \stackrel{\text{C-S}}{\le }{\left({𝔼}_{x\in Q}|X(x)|\right)}^2-{(16c)}^{-1}{𝔼}_{x\in Q}|T(x)|& \hfill & \\ \hfill & \le {\left(\frac{\lambda }{2}\right)}^2|A{|}^2-{(16c)}^{-1}2c{\lambda }^2|A{|}^2& \hfill & \\ \hfill & =\left(\frac{{\lambda }^2}{4}-\frac{{\lambda }^2}{8}\right)|A{|}^2& \hfill & \\ \hfill & =\frac{{\lambda }^2}{8}|A|& \hfill & \end{array}$$

So there exists $x\in Q$ such that $|X(x){|}^2\ge \frac{{\lambda }^2}{8}|A{|}^2$, in which case we have

$$|X|\ge \frac{\lambda }{\sqrt{8}}|A|\ge \frac{\eta }{3}|A|$$

and $|T(x)|\le 16c|X{|}^2$. □

Proof of Theorem 1.19. Given $A\subseteq G$ with $E(A)\ge \eta |A{|}^3$, apply Lemma 1.21 with $c=2^{-7}$ to otain $X\subseteq A$ of size $|X|\ge \frac{\eta }{3}|A|$ such that for all but $\frac{1}{8}$ of pairs $(a,b)\in X^2$, $a-b\in P_{\eta ∕2^7}$. In particular, the bipartite graph

$$G=(X\dot{\cup }X,\{(x,y)\in X\times X:x-y\in P_{\eta ∕2^7}\})$$

has at least $\frac{7}{8}|X{|}^2$ edges. Let $A^{\prime }=\left\{x\in X:\mathrm{deg}(x)\ge \frac{3}{4}|X|\right\}$.

Clearly, $|A^{\prime }|\ge \frac{|X|}{8}$. For any $a,b\in A^{\prime }$, there are at least $\frac{|X|}{2}$ elements $y\in X$ such that $(a,y),(b,y)\in E(G)$ ($a-y,b-y\in P_{\eta ∕2^7}$).

Thus $a-b=(a-y)-(b-y)$ has at least

$$\underset{\text{choices for }y}{\underbrace{\frac{\eta }{6}|A|}}\cdot \frac{\eta }{2^7}|A|\cdot \frac{\eta }{2^7}|A|\ge \frac{{\eta }^3}{2^{17}}|A{|}^3$$

representations of the form $a_1-a_2-(a_3-a_4)$ with $a_i\in A$.

It follows that

$$\begin{array}{llll}\hfill \frac{{\eta }^3}{2^{17}}|A{|}^3|A^{\prime }-A^{\prime }|& \le |A{|}^4& \hfill & \\ \hfill ⟹|A^{\prime }-A^{\prime }|& \le 2^{17}{\eta }^{-3}|A|& \hfill & \\ \hfill & \le 2^{22}{\eta }^{-4}|A^{\prime }|& \hfill & \end{array}$$

Thus $|A^{\prime }+A^{\prime }|\le 2^{44}{\eta }^{-8}|A^{\prime }|$. □