Further Topics - Introduction to Additive Combinatorics

4 Further Topics

In $𝔽_{p}^{n}$ , we can do much better.

Theorem 4.1 (Ellenberg-Gijswijt, following Croot-Lev-Pach). Assuming that:

$A \subseteq 𝔽_{3}^{n}$ contains no non-trivial 3 term arithmetic progressions

Then

| A | = o {(2.756)}^{n}

Notation. Let $M_{n}$ be the set of monomials in $x_{1}, \dots, x_{2}$ whose degree in each variable is at most $2$ . Let $V_{n}$ be the vector space over $𝔽_{3}$ whose basis is $M_{n}$ . For any $d \in [0, 2 n]$ , write $M_{n}^{d}$ for the set of monomials in $M_{n}$ of (total) degree at most $d$ , and $V_{n}^{d}$ for the corresponding vector space. Set $m_{d} = \dim (V_{n}^{d}) = | M_{n}^{d} |$ .

Lemma 4.2. Assuming that:

$A \subseteq 𝔽_{3}^{n}$
$P \in V_{n}^{d}$ is a polynomial
$P (a + a^{'}) = 0$ for all $a \neq a^{'} \in A$

Then

| {a \in A : P (2 a) \neq 0} | \leq 2 m_{d ∕ 2} .

Proof. Every $P \in V_{n}^{d}$ can be written as a linear combination of monomials in $M_{n}^{d}$ , so

P (x + y) = \sum_{\begin{array}{c} m, m^{'} \in M_{n}^{d} \\ \deg (m m^{'}) \leq d \end{array}} c_{m, m^{'}} m (x) m^{'} (y)

for some coefficients $c_{m, m^{'}}$ . Clearly at least one of $m, m^{'}$ must have degree $\leq \frac{d}{2}$ , whence

P (x + y) = \sum_{m \in M_{n}^{d ∕ 2}} m (x) F_{m} (y) + \sum_{m^{'} \in M_{n}^{d ∕ 2}} m^{'} (y) G_{m^{'}} (x),

for some families of polynomials ${(F_{m})}_{m \in M_{n}^{d ∕ 2}}$ , ${(G_{m^{'}})}_{m^{'} \in M_{n}^{d ∕ 2}}$ .

Viewing ${(P (x + y))}_{x, y \in A}$ as a $| A | \times | A |$ -matrix $C$ , we see that $C$ can be written as the sum of at most $2 m_{d ∕ 2}$ matrices, each of which has rank $1$ . Thus $rank (C) \leq 2 m_{d ∕ 2}$ . But by assumption, $C$ is a diagonal matrix whose rank equals $| {a \in A : P (a + a) \neq 0} |$ . □

Proposition 4.3. Assuming that:

$A \subseteq 𝔽_{3}^{n}$ a set containing no non-trivial 3 term arithmetic progressions

Then

| A | \leq 3 m_{2 n ∕ 3}

Proof. Let $d \in [0, 2 n]$ be an integer to be determined later. Let $W$ be the space of polynomials in $V_{n}^{d}$ that vanish on ${(2 \cdot A)}^{c}$ . We have

\dim (W) \geq \dim (V_{n}^{d}) - | {(2 \cdot A)}^{c} | = m_{d} - (3^{n} - | A |) .

We claim that there exists $P \in W$ such that $| supp (P) | \geq \dim (W)$ . Indeed, pick $P \in W$ with maximal support. If $| supp (P) | < \dim (W)$ , then there would be a non-zero polynomial $Q \in W$ vanishing on $supp (P)$ , in which case $supp (P + Q) ⊋ supp (P)$ , contradicting the choice of $P$ .

Now by assumption,

{a + a^{'} : a \neq a^{'} \in A} \cap 2 \cdot A = \emptyset .

So any polynomial that vanishes on ${(2 \cdot A)}^{c}$ vanishes on ${a + a^{'} : a \neq a^{'} \in A}$ . By Lemma 4.2 we now have that,

\begin{array}{l} | A | - (3^{n} - m_{d}) & = m_{d} - (3^{n} - | A |) \\ \leq \dim (W) \\ \leq | supp (P) | \\ = | {x \in 𝔽_{3}^{n} : P (x) \neq 0} | \\ = | {a \in A : P (2 a) \neq 0} | \\ \leq 2 m_{d ∕ 2} \end{array}

Hence $| A | \geq 3^{n} - m_{d} + 2 m_{d ∕ 2}$ . But the monomials in $M_{n} ∖ M_{n}^{d}$ are in bijection with the ones in $M_{2 n - d}$ via $x_{1}^{α_{1}} \dots x_{n}^{α_{n}} \mapsto x_{1}^{2 - α_{1}} \dots x_{n}^{2 - α_{n}}$ , whence $3^{n} - m_{d} = m_{2 n - d}$ . Thus setting $d = \frac{4 n}{3}$ , we have $| A | \leq m_{2 n ∕ 3} + 2 m_{2 n ∕ 3} = 3 m_{2 n ∕ 3}$ . □

You will prove Theorem 4.1 on Example Sheet 3.

We do not have at present a comparable bound for 4 term arithmetic progressions. Fourier techniques also fail.

Example 4.4. Recall from Lemma 2.18 that given $A \subseteq G$ ,

| T_{3} (𝟙_{A}, 𝟙_{A}, 𝟙_{A}) - α^{3} | \geq \sup_{γ \neq 1} | \hat{𝟙_{A}} (γ) | .

But it is impossible to bound

T_{4} (𝟙_{A}, 𝟙_{A}, 𝟙_{A}, 𝟙_{A}) - α^{4} = 𝔼_{x \in d} 𝟙_{A} (x) 𝟙_{A} (x + d) 𝟙_{A} (x + 2 d) 𝟙_{A} (x + 3 d) - α^{4}

by $\sup_{γ \neq 1} | \hat{𝟙_{A}} (γ) |$ . Indeed, consider $Q = {x \in 𝔽_{p}^{n} : x \cdot x = 0}$ . By Problem 11(ii) on Sheet 1,

\frac{| Q |}{p^{n}} = \frac{1}{p} + O (p^{- n ∕ 2})

and

\sup_{t \neq 0} | \hat{𝟙_{Q}} (t) | = O (p^{- n ∕ 2}) .

But given a 3 term arithmetic progression $x, x + d, x + 2 d \in Q$ , by the identity

x^{2} - 3 {(x + d)}^{2} + 3 {(x + 2 d)}^{2} - {(x + 3 d)}^{2} = 0 \forall x, d,

$x + 3 d$ automatically lies in $Q$ , so

T_{4} (𝟙_{A}, 𝟙_{A}, 𝟙_{A}, 𝟙_{A}) = T_{3} (𝟙_{A}, 𝟙_{A}, 𝟙_{A}) = {(\frac{1}{p})}^{3} + O (p^{- n ∕ 2})

which is not close to ${(\frac{1}{p})}^{4}$ .

Definition 4.5 ( $U^{2}$ -norm). Given $f : G \to ℂ$ , define its $U^{2}$ -norm by the formula

∥ f ∥_{U^{2} (G)}^{4} = 𝔼_{x, a, b \in G} f (x) \bar{f (x + a) f (x + b)} f (x + a + b) .

Problem 1(i) on Sheet 2 showed that $∥ f ∥_{U^{2} (G)} = ∥ \hat{f} ∥_{l^{4} (\hat{G})}$ , so this is indeed a norm.

Problem 1(ii) asserted the following:

Lemma 4.6. Assuming that:

$f_{1}, f_{2}, f_{3} : G \to ℂ$

Then

| T_{3} (f_{1}, f_{2}, f_{3}) | \leq \min_{i \in [3]} ∥ f_{i} ∥_{U^{2} (G)} \cdot \prod_{j \neq i} ∥ f_{j} ∥_{L^{\infty} (G)} .

Note that

\sup_{γ \in \hat{G}} | \hat{f} (γ) |^{4} \leq \sum_{γ \in \hat{G}} | \hat{f} (γ) |^{4} \leq \sup_{γ \in \hat{G}} | \hat{f} (γ) |^{2} \sum_{γ \in \hat{G}} | \hat{f} (γ) |^{2}

and thus by Parseval’s identity,

∥ f ∥_{U^{2} (G)}^{4} = ∥ \hat{f} ∥_{l^{\infty} (\hat{G})}^{4} \leq ∥ \hat{f} ∥_{l^{\infty} (\hat{G})}^{2} ∥ f ∥_{L^{2} (G)}^{2} .

Hence

∥ \hat{f} ∥_{l^{\infty} (\hat{G})} \leq ∥ \hat{f} ∥_{l^{4} (\hat{G})} = ∥ f ∥_{U^{2} (G)} \leq ∥ \hat{f} ∥_{l^{\infty} (\hat{G})}^{\frac{1}{2}} ∥ f ∥_{L^{2} (G)}^{\frac{1}{2}} .

Moreover, if $f = f_{A} A = 𝟙_{A} - α$ , then

T_{3} (f, f, f) = T_{3} (𝟙_{A} - α, 𝟙_{A} - α, 𝟙_{A} - α) = T_{3} (𝟙_{A}, 𝟙_{A}, 𝟙_{A}) - α^{3} .

We may therefore reformulate the first step in the proof of Meshulam’s Theorem as follows: if $p^{n} \geq 2 α^{- 2}$ , then by Lemma 4.6,

\frac{α^{3}}{2} \leq | \frac{α}{p^{n}} - α^{3} | = | T_{3} (f_{A} A, f_{A} A, f_{A} A) | \leq ∥ f_{A} A ∥_{U^{2} (𝔽_{p}^{n})} .

It remains to show that if $∥ f_{A} A ∥_{U^{2} (𝔽_{p}^{n})}$ is non-trivial, then there exists a subspace $V \leq 𝔽_{p}^{n}$ of bounded codimension on which $A$ has increased density.

Theorem 4.7 ( $U^{2}$ Inverse Theorem). Assuming that:

$f : 𝔽_{p}^{n} \to ℂ$
$∥ f ∥_{L^{\infty} (𝔽_{p}^{n})} \leq 1$
$δ > 1$
$∥ f ∥_{U^{2} (𝔽_{p}^{n})} \geq δ$

Then there exists

b \in 𝔽_{p}^{n}

such that

| 𝔼_{x \in 𝔽_{p}^{n}} f (x) e (- x \cdot b ∕ p) | \geq δ^{2} .

In other words, $| ⟨ f, ϕ ⟩ | \geq δ^{2}$ for $ϕ (x) = e (- x \cdot b ∕ p)$ and we say “ $f$ correlates with a linear phase function”.

Proof. We have seen that

∥ f ∥_{U^{2} (𝔽_{p}^{n})}^{2} \leq ∥ \hat{f} ∥_{l^{\infty} (\hat{𝔽_{p}^{n}})} ∥ f ∥_{L^{2} (𝔽_{p}^{n})} \leq ∥ \hat{f} ∥_{l^{\infty} (\hat{𝔽_{p}^{n}})},

δ^{2} \leq ∥ \hat{f} ∥_{l^{\infty} (\hat{𝔽_{p}^{n}})} = \sup_{t \in \hat{𝔽_{p}^{n}}} | 𝔼_{x} f (x) e (- x \cdot t ∕ p) | . □

Definition 4.8 ( $U^{3}$ norm). Given $f : G \to ℂ$ , define its $U^{3}$ norm by

\begin{array}{l} ∥ f ∥_{U^{3} (G)}^{8} & : = 𝔼_{_{\in} x, a, b, c} f (x) \bar{f (x + a) f (x + b) f (x + c)} \\ f (x + a + b) f (x + b + c) f (x + a + c) \bar{f (x + a + b + c)} \\ = 𝔼_{x, h_{1}, h_{2}, h_{3} \in G} \prod_{𝜀 \in {0, 1}^{3}} C^{| 𝜀 |} f (x + 𝜀 \cdot h) \end{array}

where $C g (x) = \bar{g (x)}$ and $| 𝜀 |$ denotes the number of ones in $𝜀$ .

It is easy to verify that $𝔼_{c \in G} ∥ Δ_{c} f ∥_{U^{2} (G)}^{4}$ where $Δ_{c} g (x) = g (x) \bar{g (x + c)}$ .

Definition 4.9 ( $U^{3}$ inner product). Given functions $f_{𝜀} : G \to ℂ$ for $𝜀 \in {0, 1}^{3}$ , define their $U^{3}$ inner product by

{⟨ {(f_{𝜀})}_{𝜀 \in {0, 1}^{3}} ⟩}_{U^{3} (G)} = 𝔼_{x, h_{1}, h_{2}, h_{3} \in G} \prod_{𝜀 \in {0, 1}^{3}} C^{| 𝜀 |} f_{𝜀} (x + 𝜀 \cdot h) .

Observe that ${⟨ f, f, f, f, f, f, f, f ⟩}_{U^{3} (G)} = {∥ f ∥_{U^{3} (G)}}^{8}$ .

Lemma 4.10 (Gowers–Cauchy–Schwarz Inequality). Assuming that:

$f_{𝜀} : G \to ℂ$ , $𝜀 \in {0, 1}^{3}$

Then

| {⟨ {(f_{𝜀})}_{𝜀 \in {0, 1}^{3}} ⟩}_{U^{3} (G)} \leq \prod_{𝜀 \in {0, 1}^{3}} ∥ f_{𝜀} ∥_{U^{3} (G)} .

Setting $f_{𝜀} = f$ for $𝜀 \in {0, 1}^{2} \times {0}$ and $f_{𝜀} = 1$ otherwise, it follows that $∥ f ∥_{U^{2} (G)}^{4} \leq {∥ f ∥_{U^{3} (G)}}^{4}$ hence $∥ f ∥_{U^{2} (G)} \leq ∥ f ∥_{U^{3} (G)}$ .

Proposition 4.11. Assuming that:

$f_{1}, f_{2}, f_{3}, f_{4} : 𝔽_{5}^{n} \to ℂ$

Then

T_{4} (f_{1}, f_{2}, f_{3}, f_{4}) \leq \min_{i \in [4]} ∥ f_{i} ∥_{U^{3} (G)} \prod_{j \neq i} ∥ f_{j} ∥_{L^{\infty} (𝔽_{5}^{n})} .

Proof. We additionally assume $f = f_{1} = f_{2} = f_{3} = f_{4}$ to make the proof easier to follow, but the same ideas are used for the general case. We additionally assume $∥ f ∥_{L^{\infty} (𝔽_{5}^{n})} \leq 1$ , by rescaling, since the inequality is homogeneous.

Reparametrising, we have

\begin{array}{l} T_{4} (f, f, f, f) & = 𝔼_{a, b, c, d \in 𝔽_{5}^{n}} f (3 a + 2 b + c) f (2 a + b - d) f (a - c - 2 d) f (- b - 2 c - 3 d) \\ | T_{4} (f, f, f, f) |^{8} & \leq (𝔼_{a, b, c} | 𝔼_{d} f (2 a + b - d) f (a - c - 2 d) f (- b - 2 c - 3 d) |^{2})^{4} \\ = (𝔼_{d, d^{'}} 𝔼_{a, b} f (2 a + b + d) \bar{f (2 a + b - d^{'})} \\ 𝔼_{c} f (a - c - 2 d) \bar{f (a - c - 2 d^{'})} f (- b - 2 c - 3 d) \bar{f (- b - 2 c - 3 d^{'})})^{4} \\ \leq (𝔼_{d, d^{'}} 𝔼_{a, b} | 𝔼_{c} f (a - c - 2 d) \bar{f (a - c - 2 d^{'})} f (- b - 2 c - 3 d) \bar{f (- b - 2 c - 3 d^{'})} |^{2})^{2} \\ = (𝔼_{c, c^{'}, d, d^{'}} 𝔼_{a} f (a - c - 2 d) \bar{f (a - c^{'} - 2 d)} \bar{f (a - c - 2 d^{'})} f (a - c^{'} - 2 d^{'}) \\ 𝔼_{b} f (- b - 2 c - 3 d) \bar{f (- b - 2 c^{'} - 3 d)} \bar{f (- b - 2 c - 3 d^{'})} f (- b - 2 c^{'} - 3 d^{'}))^{2} \\ \leq 𝔼_{c, c^{'}, d, d^{'}, a} | 𝔼_{b} f (- b - 2 c - 3 d) \bar{f (- b - 2 c^{'} - 3 d)} \bar{f (- b - 2 c - 3 d^{'})} f (- b - 2 c^{'} - 3 d^{'}) |^{2} \\ = 𝔼_{b, b^{'}, c, c^{'}, d, d^{'}} f (- b - 2 c - 3 d) \bar{f (- b^{'} - 2 c - 3 d)} \bar{f (- b - 2 c^{'} - 3 d)} f (- b^{'} - 2 c^{'} - 3 d) \\ \bar{f (- b - 2 c - 3 d^{'})} f (- b^{'} - 2 c - 3 d^{'}) f (- b - 2 c^{'} - 3 d^{'}) \bar{f (- b^{'} - 2 c^{'} - 3 d^{'})} □ \end{array}

Theorem 4.12 (Szemeredi’s Theorem for 4-APs). Assuming that:

$A \subseteq 𝔽_{5}^{n}$ a set containing no non-trivial 4 term arithmetic progressions

Then

| A | = o (5^{n})

Idea: By Proposition 4.11 with $f = f_{A} = 𝟙_{A} - α$ ,

T_{4} (\underset{f_{A} + α}{\underset{⏟}{𝟙_{A}}}, \underset{f_{A} + α}{\underset{⏟}{𝟙_{A}}}, \underset{f_{A} + α}{\underset{⏟}{𝟙_{A}}}, \underset{f_{A} + α}{\underset{⏟}{𝟙_{A}}}) - α^{4} = T_{4} (f_{A}, f_{A}, f_{A}, f_{A}) + \dots

where $\dots$ consists of $14$ other terms in which between one and three of the inputs are equal to $f_{A}$ .

These are controlled by

∥ f_{A} ∥_{U^{2} (𝔽_{5}^{n})} \leq ∥ f_{A} ∥_{U^{3} (G)},

whence

| T_{4} (𝟙_{A}, 𝟙_{A}, 𝟙_{A}, 𝟙_{A}) - α^{4} | \leq 15 ∥ f_{A} ∥_{U^{3} (G)} .

So if $A$ contains no non-trivial 4 term arithmetic progressions and $5^{n} > 2 α^{- 3}$ , then $∥ f_{A} ∥_{U^{3} (G)} \geq \frac{α^{4}}{30}$ .

What can we say about functions with large $U^{3}$ norm?

Example 4.13. Let $M$ be an $n \times n$ symmetric matrix with entries in $𝔽_{5}$ . Then $f (x) = e (x^{⊤} M x ∕ 5)$ satisfies $∥ f ∥_{U^{3} (G)} = 1$ .

Theorem 4.14 ( $U^{3}$ inverse theorem). Assuming that:

$f : 𝔽_{5}^{n} \to ℂ$
$∥ f ∥_{L^{\infty} (𝔽_{5}^{n})} \leq 1$
$∥ f ∥_{U^{3} (G)} \geq δ$ for some $δ > 0$

Then there exists a symmetric

n \times n

matrix

M

with entries in

𝔽_{5}

and

b \in 𝔽_{5}^{n}

such that

| 𝔼_{x} f (x) e ((x^{⊤} M x + b^{⊤} x) ∕ p) | \geq c (δ)

where $c (δ)$ is a polynomial in $δ$ . In other words, $| ⟨ f, ϕ ⟩ | \geq c (δ)$ for $ϕ (x) = e ((x^{⊤} M x + b^{⊤} x) ∕ p)$ and we say “ $f$ correlates with a quadratic phase function”.

Proof (sketch). Let $Δ_{h} f (x)$ denote $f (x) \bar{f (x + h)}$ .

$∥ f ∥_{U^{3} (G)} = {(𝔼_{h} ∥ Δ_{h} f ∥_{U^{2}}^{4})}^{\frac{1}{8}}$ .

STEP 1: Weak linearity. See reference.
STEP 2: Strong linearity. We will spend the rest of the lecture discussing this in detail.
STEP 3: Symmetry argument. Problem 8 on Sheet 3.
STEP 4: Integration step. Problem 9 on Sheet 3.

STEP 1: If ${∥ f ∥_{U^{3} (G)}}^{8} = 𝔼_{h} ∥ Δ_{h} ∥_{U^{2}}^{4} \geq δ^{8}$ , then for at least a $\frac{δ^{8}}{2}$ -proportion of $h \in 𝔽_{5}^{n}$ , $\frac{δ^{8}}{2} \leq ∥ Δ_{h} f ∥_{U^{2}}^{4} \leq ∥ \hat{Δ_{h} f} ∥_{l^{\infty}}^{2}$ . So for each such $h \in 𝔽_{5}^{n}$ , there exists $t_{h}$ such that $| \hat{Δ_{h} f} (t_{h}) |^{2} \geq \frac{δ^{8}}{2}$ .

Proposition 4.15. Assuming that:

$f : 𝔽_{5}^{n} \to ℂ$
$∥ f ∥_{\infty} \leq 1$
$∥ f ∥_{U^{3} (G)} \geq δ$
$| 𝔽_{5}^{n} | = Ω_{δ} (1)$

Then there exists

S \subseteq 𝔽_{5}^{n}

with

| S | = Ω_{δ} (| 𝔽_{5}^{n} |)

and a function

ϕ : S \to \hat{𝔽_{5}^{n}}

such that

(i) $| \hat{Δ_{h} f} (ϕ (h)) | = Ω_{δ} (1)$ ;
(ii) There are at least $Ω_{δ} (| 𝔽_{5}^{n} |^{3})$ quadruples $(s_{1}, s_{2}, s_{3}, s_{4}) \in S^{4}$ such that $s_{1} + s_{2} = s_{3} + s_{4}$ and $ϕ (s_{1}) + ϕ (s_{2}) + ϕ (s_{4})$ .

STEP 2: If $S$ and $ϕ$ are as above, then there is a linear function $ψ : 𝔽_{5}^{n} \to \hat{𝔽_{5}^{n}}$ which coincides with $ϕ$ for many elements of $S$ .

Proposition 4.16. Assuming that:

$S$ and $ϕ$ given as in Proposition 4.15

Then there exists

n \times n

matrix

M

with entries in

𝔽_{5}

and

b \in 𝔽_{5}^{n}

such that

ψ (x) = M x + b

(

ψ : 𝔽_{5}^{n} \to \hat{𝔽_{5}^{n}}

) satisfies

ψ (x) = ϕ (x)

for

Ω_{δ} (| 𝔽_{5}^{n} |)

elements

x \in S

Proof. Consider the graph of $ϕ$ , $Γ = {(h, ϕ (h)) : h \in S} \subseteq 𝔽_{5}^{n} \times \hat{𝔽_{5}^{n}}$ . By Proposition 4.15, $Γ$ has $Ω_{δ} (| 𝔽_{5}^{n} |^{3})$ additive quadruples.

By Balog–Szemeredi–Gowers, Schoen, there exists $Γ^{'} \subseteq Γ$ with $| Γ^{'} | = Ω_{δ} (| Γ |) = Ω_{δ} (| 𝔽_{5}^{n} |)$ and $| Γ^{'} + Γ^{'} | = O_{δ} (| Γ^{'} |)$ . udefine $S^{'} \subseteq S$ by $Γ^{'} = {(h, ϕ (h)) : h \in S^{'}}$ and note $| S^{'} | = Ω_{δ} (| 𝔽_{5}^{n} |)$ .

By Freiman-Ruzsa applied to $Γ^{'} \subseteq 𝔽_{5}^{n} \times \hat{𝔽_{5}^{n}}$ , there exists a subspace $H \leq 𝔽_{5}^{n} \times \hat{𝔽_{5}^{n}}$ with $| H | = O_{δ} (| Γ^{'} |) = O_{δ} (| 𝔽_{5}^{n} |)$ such that $Γ^{'} \subseteq H$ .

Denote by $π : 𝔽_{5}^{n} \times \hat{𝔽_{5}^{n}} \to 𝔽_{5}^{n}$ the projection onto the first $n$ coordinates. By construction, $π (H) \supseteq S^{'}$ . Moreover, since $| S^{'} | = Ω_{δ} (| 𝔽_{5}^{n} |)$ ,

| \ker (π |_{H}) | = \frac{| H |}{| Im (π |_{H}) |} = \frac{O_{δ} (| 𝔽_{5}^{n} |)}{| S^{'} |} = O_{δ} (1) .

We may thus partition $H$ into $O_{δ} (1)$ cosets of some subspace $H^{*}$ such that $π |_{H}$ is injective on each coset. By averaging, there exists a coset $x + H^{*}$ such that

| Γ^{'} \cap (x + H^{*}) | = Ω_{δ} (| Γ^{'} |) = Ω_{δ} (| 𝔽_{5}^{n} |) .

Set $Γ^{″} = Γ^{'} \cap (x + H^{*})$ , and define $S^{″}$ accordingly.

Now $π |_{x +^{*}}$ is injective and surjective onto $V : = Im (π |_{x + H^{*}})$ . This means there is an affine linear map $ψ : V \to \hat{𝔽_{5}^{n}}$ such that $(h, ψ (h)) \in Γ^{″}$ for all $h \in S^{″}$ . □

Then do steps 3 and 4. □

What to do if you have lots of additive quadruples?

Balog-Szemeredi-Gowers

What to do if you have small doubling constant?

Freiman-Ruzsa (or Polynomial-Freiman-Ruzsa)