Further Topics - Introduction to Additive Combinatorics

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

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

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

Problem 1(i) on Sheet 2 showed that

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

, so this is indeed a norm.

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,

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) | . □

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)}

Observe that

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

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)}

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}

where

\dots

consists of

14

other terms in which between one and three of the inputs are equal to

f_{A}

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}

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

4 Further Topics