Fourier-analytic techniques - Introduction to Additive Combinatorics

2 Fourier-analytic techniques

In this chapter we will assume that $G$ is finite abelian.

$G$ comes equipped with a group $Ĝ$ of characters, i.e. homomorphisms $γ : G \to ℂ$ . In fact, $Ĝ$ is isomorphic to $G$ .

See Representation Theory notes for more information about characters and proofs of this as well as some of the facts below.

Example 2.1.

(i) If $G = 𝔽_{p}^{n}$ , then for any $γ \in Ĝ = 𝔽_{p}^{n}$ , we have an associated character $γ (x) = e (γ \cdot x ∕ p)$ , where $e (y) = e^{2 π i y}$ .
(ii) If $G = ℤ ∕ N ℤ$ , then any $γ \in \hat{G} = ℤ ∕ N ℤ$ can be associated to a character $γ (x) = e (γ x ∕ N)$ .

Notation. Given $B \subseteq G$ nonempty, and any function $g : B \to ℂ$ , let

𝔼_{x \in B} g (x) = \frac{1}{| B |} \sum_{x \in B} g (x) .

Lemma 2.2. Assuming that:

$γ \in \hat{G}$

Then

𝔼_{x \in G} γ (x) = {\begin{matrix} 1 & if γ = 1 \\ 0 & otherwise \end{matrix},

and for all $x \in G$ ,

\sum_{γ \in \hat{G}} γ (x) = {\begin{matrix} | \hat{G} | & if x = 0 \\ 0 & otherwise \end{matrix} .

Proof. The first equality in eqch case is trivial. Suppose $γ \neq 1$ . Then there exists $y \in G$ with $γ (y) \neq 1$ . Then

\begin{array}{l} γ (y) 𝔼_{z \in G} γ (z) & = 𝔼_{z \in G} γ (y + z) \\ = 𝔼_{z^{'} \in G} γ (z^{'}) \end{array}

So $𝔼_{z \in G} γ (z) = 0$ .

For the second part, note that given $x \neq 0$ , there must by $γ \in \hat{G}$ such that $γ (x) \neq 1$ , for otherwise $\hat{G}$ would act trivially on $⟨ x ⟩$ , hence would also be the dual group for $G ∕ ⟨ x ⟩$ , a contradiction. □

Definition 2.3 (Fourier transform). Given $f : G \to ℂ$ , define its Fourier transform $\hat{f} : \hat{G} \to ℂ$ by

\hat{f} (γ) = 𝔼_{x \in G} f (x) \bar{γ (x)} .

It is easy to verify the inversion formula: for all $x \in G$ ,

f (x) = \sum_{γ \in \hat{G}} \hat{f} (γ) γ (x) .

Indeed,

\begin{array}{l} \sum_{γ \in \hat{G}} \hat{f} (γ) γ (x) & = \sum_{γ \in \hat{G}} 𝔼_{y \in G} f (y) \bar{γ (y)} γ (x) \\ = 𝔼_{y \in G} f (y) \underset{= | G | iff x = y}{\underset{⏟}{\sum_{γ \in \hat{G}} γ (x - y)}} \\ = f (x) & by Lemma 2.2 \end{array}

Given $A \subseteq G$ , the indicator or characteristic function of $A$ , $𝟙_{A} : G \to {0, 1}$ is defined as usual.

Note that

\hat{𝟙_{A}} (1) = 𝔼_{x \in G} 𝟙_{A} (x) 1 (x) = \frac{| A |}{| G |} .

The density of $A$ in $G$ (often denoted by $α$ ).

Definition (Characteristic measure). Given non-empty $A \subseteq G$ , the characteristic measure $μ_{A} : G \to [0, | G |]$ is defined by $μ_{A} (x) = α^{- 1} 𝟙_{A} (x)$ .

Note that $𝔼_{x \in G} μ_{A} (x) = 1 = \hat{μ_{A}} (1)$ .

Definition (Balanced function). The balanced function $f_{A} : G \to [- 1, 1]$ is given by $f_{A} (x) = 𝟙_{A} (x) - α$ . Note that $𝔼_{x \in G} f_{A} (x) = 0 = \hat{f_{A}} (1)$ .

Example 2.4. Let $V \leq 𝔽_{p}^{n}$ be a subspace. Then for $t \in \hat{𝔽_{p}^{n}}$ , we have

\begin{array}{l} \hat{𝟙_{V}} (t) & = 𝔼_{x \in 𝔽_{p}^{n}} 𝟙_{V} (x) e (- \frac{x \cdot t}{p}) \\ = \frac{| V |}{p^{n}} 𝟙_{V^{⊥}} (t) \end{array}

where $V^{⊥} = {t \in \hat{𝔽_{p}^{n}} : x \cdot t = 0 \forall x \in V}$ is the annihilator of $V$ . In other words, $\hat{𝟙_{V}} (t) = μ_{V^{⊥}} (t)$ .

Example 2.5. Let $R \subseteq G$ be such that each $x \in G$ lies in $R$ independently with probability $\frac{1}{2}$ . Then with high probability

\sup_{γ \neq 1} | \hat{𝟙_{R}} (γ) | = O (\sqrt{\frac{\log | G |}{| G |}}) .

This follows from Chernoff’s inequality: Given $ℂ$ -valued independent random variables $X_{1}, X_{2}, \dots, X_{n}$ with mean $0$ , then for all $𝜃 > 0$ , we have

ℙ (| \sum_{i = 1}^{n} X_{i} | \geq 𝜃 \sqrt{\sum_{i = 1}^{n} {∥ X_{i} ∥}_{L^{\infty} (ℙ)}^{2}}) \leq 4 \exp (- \frac{𝜃^{2}}{4}) .

Example 2.6. Let $Q = {x \in 𝔽_{p}^{n} : x \cdot x = 0} \subseteq 𝔽_{p}^{n}$ with $p > 2$ . Then

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

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

Given $f, g : G \to ℂ$ , we write

⟨ f, g ⟩ = 𝔼_{x \in G} f (x) \bar{g (x)} and ⟨ \hat{f}, \hat{g} ⟩ = \sum_{γ \in \hat{G}} \hat{f} (γ) \bar{\hat{g} (γ)} .

Consequently,

{∥ f ∥}_{L^{2} (G)}^{2} = 𝔼_{x \in G} | f (x) |^{2} and {∥ \hat{f} ∥}_{l^{2} (\hat{G})}^{2} = \sum_{γ \in \hat{G}} | \hat{f} (γ) |^{2} .

Lemma 2.7. Assuming that:

$f, g : G \to ℂ$

Then

(i) ${∥ f ∥}_{L^{2} (G)}^{2} = {∥ \hat{f} ∥}_{l^{2} (\hat{G})}^{2}$ (Parseval’s identity)
(ii) $⟨ f, g ⟩ = ⟨ \hat{f}, \hat{g} ⟩$ (Plancherel’s identity)

Proof. Exercise (hopefully easy). □

Definition 2.8 (Spectrum). Let $1 \geq ρ > 0$ and $f : G \to ℂ$ . Define the $ρ$ -large spectrum of $f$ to be

{Spec}_{ρ} (f) = {γ \in \hat{G} : | \hat{f} (γ) | \geq ρ {∥ f ∥}_{1}} .

Example 2.9. By Example 2.4, if $f = 𝟙_{V}$ with $V \leq 𝔽_{p}^{n}$ , then $\forall ρ > 0$ ,

{Spec}_{ρ} (𝟙_{V}) = {t \in \hat{𝔽_{p}^{n}} : | \hat{𝟙_{V}} (t) | \geq ρ \frac{| V |}{p^{n}}} = V^{⊥} .

Lemma 2.10. Assuming that:

$ρ > 0$

Then

| {Spec}_{ρ} (f) | \leq ρ^{- 2} \frac{{∥ f ∥}_{2}^{2}}{{∥ f ∥}_{1}^{2}} .

Proof. By Parseval’s identity,

\begin{array}{l} {∥ f ∥}_{2}^{2} & = {∥ \hat{f} ∥}_{2}^{2} \\ = \sum_{γ \in \hat{G}} | \hat{f} (γ) |^{2} \\ \geq \sum_{γ \in {Spec}_{ρ} (f)} | \hat{f} (γ) |^{2} \\ \geq | {Spec}_{ρ} (f) | {(ρ {∥ f ∥}_{1})}^{2} □ \end{array}

In particular, if $f = 𝟙_{A}$ for $A \subseteq G$ , then

{∥ f ∥}_{1} = α = \frac{| A |}{| G |} = {∥ f ∥}_{2}^{2},

so $| {Spec}_{ρ} (𝟙_{A}) | \leq ρ^{- 2} α^{- 1}$ .

Definition 2.11 (Convolution). Given $f, g : G \to ℂ$ , we define their convolution $f * g : G \to ℂ$ by

f * g (x) = 𝔼_{y \in G} f (y) g (x - y) \forall x \in G .

Example 2.12. Given $A, B \subseteq G$ ,

𝟙_{A} * 𝟙_{B} (x) = 𝔼_{y \in G} 𝟙_{A} (y) 𝟙_{B} (x - y) = 𝔼_{y \in G} 𝟙_{A} (y) 𝟙_{x - B} (y) = \frac{| A \cap (x - B) |}{| G |} = \frac{1}{| G |} r_{A + B} (x) .

In particular, $supp (𝟙_{A} * 𝟙_{B}) = A + B$ .

Lemma 2.13. Assuming that:

$f, g : G \to ℂ$

Then

\hat{f * g} (γ) = \hat{f} (γ) \hat{g} (γ) \forall γ \in \hat{G} .

Proof.

\begin{array}{l} \hat{f * g} (γ) & = 𝔼_{x \in G} f * g (x) \bar{γ (x)} \\ = 𝔼_{x \in G} 𝔼_{[\in y}] G f (y) g (\underset{u}{\underset{⏟}{x - y}}) \bar{γ (x)} \\ = 𝔼_{u \in G} 𝔼_{[\in y}] G f (y) g (u) \bar{γ (u + y)} \\ = \hat{f} (γ) \hat{g} (γ) □ \end{array}

Example 2.14.

𝔼_{x + y = z + w} f (x) f (y) \bar{f (z) f (w)} = ∥ \hat{f} ∥_{l^{4} (\hat{G})}^{4} .

In particular,

∥ \hat{𝟙_{A}} ∥_{l^{4} (\hat{G})}^{4} = \frac{E (A)}{| G |^{3}}

for any $A \subseteq G$ .

Theorem 2.15 (Bogolyubov’s lemma). Assuming that:

$A \subseteq 𝔽_{p}^{n}$ be a set of density $α$

Then there exists

V \leq 𝔽_{p}^{n}

of codimension

\leq 2 α^{- 2}

such that

V \subseteq A + A - A - A

Proof. Observe

2 A - 2 A = supp (\underset{= : g}{\underset{⏟}{𝟙_{A} * 𝟙_{A} * 𝟙_{- A} * 𝟙_{- A}}}),

so wish to find $V \leq 𝔽_{p}^{n}$ such that $g (x) > 0$ for all $x \in V$ . Let $S = {Spec}_{ρ} (𝟙_{A})$ with $ρ = \sqrt{\frac{α}{2}}$ and let $V = {⟨ S ⟩}^{⊥}$ . By Lemma 2.10, $codim (V) \leq | S | \leq ρ^{- 2} α^{- 1}$ . Fix $x \in V$ .

\begin{array}{l} g (x) & = \sum_{t \in \hat{𝔽_{p}^{n}}} \hat{g} (t) e (x \cdot t ∕ p) \\ = \sum_{t \in \hat{𝔽_{p}^{n}}} | \hat{𝟙_{A}} (t) |^{4} e (x \cdot t ∕ p) & by Lemma 2.13 \\ = α^{4} + \sum_{t \neq 0} | \hat{𝟙_{A}} (t) |^{4} e (x \cdot t ∕ p) \\ = α^{4} + \underset{(1)}{\underset{⏟}{\sum_{t \in S ∖ {0}} | \hat{𝟙_{A}} (t) |^{4} e (x \cdot t ∕ p)}} + \underset{(2)}{\underset{⏟}{\sum_{t \notin S} | \hat{𝟙_{A}} (t) |^{4} e (x \cdot t ∕ p)}} \end{array}

Note $(1) \geq {(ρ α)}^{4}$ since $x \cdot t = 0$ for all $t \in S$ and

\begin{array}{l} | (2) | & \leq \sup_{t \notin S} | \hat{𝟙_{A}} (t) |^{2} \sum_{t \notin S} | \hat{𝟙_{A}} |^{2} \\ \leq \sup_{t \in S} | \hat{𝟙_{A}} (t) |^{2} \sum_{t \notin S} | \hat{𝟙_{A}} |^{2} \\ \leq {(ρ α)}^{2} ∥ 𝟙_{A} ∥_{2}^{2} & by Parseval’s identity \\ = ρ^{2} α^{3} \end{array}

hence $g (x) > 0$ (in fact, $\geq \frac{α^{4}}{2}$ ) for all $x \in V$ and $codim (V) \leq 2 α^{- 2}$ . □

Example 2.16. The set $A = {x \in 𝔽_{2}^{n} : | x | \geq \frac{n}{2} + \frac{\sqrt{n}}{2}}$ (where $| x |$ counts the number of 1s in $x$ ) has density $\geq \frac{1}{8}$ , but there is no coset $C$ of any subspace of codimension $\sqrt{n}$ such that $C \subseteq A + A (= A - A)$ .

Lemma 2.17. Assuming that:

$A \subseteq 𝔽_{p}^{n}$ of density $α$
$ρ > 0$
$\sup_{t \neq 0} | \hat{𝟙_{A}} (t) | \geq ρ α$

Then there exists

V \leq 𝔽_{p}^{n}

of codimension

1

and

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

such that

| A \cap (x + V) | \geq α (1 + \frac{ρ}{2}) | V | .

Proof. Let $t \neq 0$ be such that $| \hat{𝟙_{A}} (t) | \geq ρ α$ , and let $V = {⟨ t ⟩}^{⊥}$ . Write $v_{j} + V$ for $j \in [p] = {1, 2, \dots, p}$ for the $p$ distinct cosets $v_{j} + V = {x \in 𝔽_{p}^{n} : x \cdot t = j}$ of $V$ . Then

\begin{array}{l} \hat{𝟙_{A}} (t) & = \hat{f_{A}} (t) \\ = 𝔼_{x \in 𝔽_{p}^{n}} (𝟙_{A} (x) - α) e (- x \cdot t ∕ p) \\ = 𝔼_{j \in [p]} 𝔼_{x \in v_{j} + V} (𝟙_{A} (x) - α) e (- j ∕ p) \\ = 𝔼_{j \in [p]} (\underset{= a_{j}}{\underset{⏟}{\frac{| A \cap (v_{j} + V) |}{| v_{j} + V |} - α}}) e (- j ∕ p) \end{array}

By triangle inequality, $𝔼_{j \in [p]} | a_{j} | \geq ρ α$ . But note that $𝔼_{j \in [p]} a_{j} = 0$ so $𝔼_{j \in [p]} a_{j} + | a_{j} | \geq ρ α$ , hence there exists $j \in [p]$ such that $a_{j} + | a_{j} | \geq ρ α$ . Then $a_{j} \geq \frac{ρ α}{2}$ . □

Notation. Given $f, g, h : G \to ℂ$ , write

T_{3} (f, g, h) = 𝔼_{x, d \in G} f (x) g (x + d) h (x + 2 d) .

Notation. Given $A \subseteq G$ , write

2 \cdot A = {2 a : a \in A},

to be distinguished from $2 A = A + A = {a + a^{'} : a, a^{'} \in A}$ .

Lemma 2.18. Assuming that:

$p \geq 3$ prime
$A \subseteq 𝔽_{p}^{n}$ of density $α > 0$
$\sup_{t \neq 0} | \hat{𝟙_{A}} (t) | \leq 𝜀$

Then the number of 3-term arithmetic progressions in

A

differs from

α^{3} {(p^{n})}^{2}

by at most

𝜀 {(p^{n})}^{2}

Proof. The number of 3-term arithmetic progressions in $A$ is ${(p^{n})}^{2}$ times

\begin{array}{l} T_{3} (𝟙_{A}, 𝟙_{A}, 𝟙_{A}) & = 𝔼_{x, d \in 𝔽_{p}^{n}} 𝟙_{A} (x) 𝟙_{(} x + d) 𝟙_{A} (x + 2 d) \\ = 𝔼_{x, y \in 𝔽_{p}^{n}} 𝟙_{A} (x) 𝟙_{A} (y) 𝟙_{A} (2 y - x) \\ = 𝔼_{y \in G} 𝟙_{A} (y) 𝔼_{x \in G} 𝟙_{A} (x) 𝟙_{A} (2 y - x) \\ = 𝔼_{y \in G} 𝟙_{A} (y) 𝟙_{A} * 𝟙_{A} (2 y) \\ = ⟨ 𝟙_{2 \cdot A}, 𝟙_{A} * 𝟙_{A} ⟩ \end{array}

By Plancherel’s identity and Lemma 2.13, we have

\begin{array}{l} = ⟨ \hat{𝟙_{2 \cdot A}}, {\hat{𝟙_{A}}}^{2} ⟩ \\ = \sum_{t} \hat{𝟙_{2 \cdot A}} (t) \bar{\hat{𝟙_{A}} {(t)}^{2}} \\ = α^{3} + \sum_{t \neq 0} \hat{𝟙_{2 \cdot A}} (t) \bar{\hat{𝟙_{A}} {(t)}^{2}} \end{array}

but

\begin{array}{l} | \sum_{t \neq 0} \hat{𝟙_{2 \cdot A}} (t) \hat{𝟙_{A}} {(t)}^{2} | & \leq \sup_{t \neq 0} | \hat{𝟙_{A}} (t) | \sum_{t \neq 0} | \hat{𝟙_{2 \cdot A}} (t) | | \hat{𝟙_{A}} (t) | \\ \overset{CS}{\leq} \sup_{t \neq 0} | \hat{𝟙_{A}} (t) | {(\sum_{t} | \hat{𝟙_{2 \cdot A}} (t) |^{2} \sum_{t} | \hat{𝟙_{A}} (t) |^{2})}^{\frac{1}{2}} \\ \leq 𝜀 ∥ \hat{𝟙_{2 \cdot A}} ∥_{2} ∥ \hat{𝟙_{A}} ∥_{2} \\ = 𝜀 \cdot α \end{array}

by Parseval’s identity. □

Theorem 2.19 (Meshulam’s Theorem). Assuming that:

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

Then

| A | = O (\frac{p^{n}}{\log p^{n}})

Proof. By assumption,

T_{3} (𝟙_{A}, 𝟙_{A}, 𝟙_{A}) = \frac{| A |}{{(p^{n})}^{2}} = \frac{α}{p^{n}} .

But as in (the proof of) Lemma 2.18,

| T_{3} (𝟙_{A}, 𝟙_{A}, 𝟙_{A}) - α^{3} | \leq \sup_{t \neq 0} | \hat{𝟙_{A}} (t) | \cdot α,

so provided $p^{n} \geq 2 α^{- 2}$ , i.e. $T_{3} (𝟙_{A}, 𝟙_{A}, 𝟙_{A}) \leq \frac{α^{3}}{2}$ we have $\sup_{t \neq 0} | \hat{𝟙_{A}} (t) | \geq \frac{α^{2}}{2}$ .

So by Lemma 2.17 with $ρ = \frac{α}{2}$ , there exists $V \leq 𝔽_{p}^{n}$ of codimension 1 and $x \in 𝔽_{p}^{n}$ such that $| A \cap (x + V) | \geq (α + \frac{α^{2}}{4}) | V |$ .

We iterate this observation: let $A_{0} = A$ , $V_{0} = 𝔽_{p}^{n}$ , $α_{0} = \frac{| A_{0} |}{| V_{0} |}$ . At the $i$ -th step, we are given a set $A_{i - 1} \subseteq V_{i - 1}$ of density $α_{i - 1}$ with no non-trivial 3 term arithmetic progressions. Provided that $p^{\dim (V_{i - 1})} \geq 2 α_{i - 1}^{- 2}$ , there exists $V_{i} \leq V_{i - 1}$ of codimension $1$ , $x_{i} \in V_{i - 1}$ such that

| (A - x_{i}) \cap V_{i} | \geq (α_{i - 1} + \frac{{(α_{i - 1})}^{2}}{4}) | V_{i} | .

Set $A_{i} = (A - x_{i}) \cap V_{i} \subseteq V_{i}$ , has density $\geq α_{i - 1} + \frac{{(α_{i - 1})}^{2}}{4}$ , and is free of non-trivial 3 term arithmetic progressions.

Through this iteration, the density increases from $α$ to $2 α$ in at most $\frac{α}{(\frac{α^{2}}{4})} = 4 \cdot α^{- 1}$ steps.

$2 α$ to $4 α$ in at most $\frac{2 α}{(\frac{{(2 α)}^{2}}{4})} = 2 α^{- 1}$ steps and so on.

So reaches $1$ in at most

4 α^{- 1} (1 + \frac{1}{2} + \frac{1}{4} + \frac{1}{8} + \dots) \leq 8 α^{- 1}

steps. The argument must end with $\dim (V_{i}) \geq n - 8 α^{- 1}$ , at which point we must have had $p^{\dim (V_{i})} < 2 α_{i - 1}^{2} \leq 2 α^{- 2}$ , or else we could have continued.

But we may assume that $α \geq \sqrt{2} p^{- \frac{n}{4}}$ (or $α^{- 2} < 2 p^{\frac{n}{2}}$ ) whence $p^{n - 8 α^{- 1}} \leq p^{\frac{n}{2}}$ , or $\frac{n}{2} \leq 2 α^{- 1}$ . □

At the time of writing, the largest known subset of $𝔽_{3}^{n}$ containing no non-trivial 3 term arithmetic progressions has size ${(2.2202)}^{n}$ .

We will prove an upper bound of the form ${(2.756)}^{n}$ .

Theorem 2.20 (Roth’s theorem). Assuming that:

$A \subseteq [N] = {1, \dots, N}$
$A$ contains no non-trivial 3 term arithmetic progressions

Then

| A | = O (\frac{N}{\log \log N})

Example 2.21 (Behrend’s example). There exists $A \subseteq [N]$ of size at least $| A | \geq \exp (- c \sqrt{\log N}) N$ containing no non-trivial 3 term arithmetic progressions.

Lemma 2.22. Assuming that:

$A \subseteq [N]$ of density $α > 0$
$N > 50 α^{- 2}$
$A$ contains no non-trivial 3 term arithmetic progressions
$p$ a prime in $[\frac{N}{3}, \frac{2 N}{3}]$
let $A^{'} = A \cap [p] \subseteq ℤ ∕ p ℤ$

Then one of the following holds:

(i) $\sup_{t \neq 0} | \hat{𝟙_{A^{'}}} (t) | \geq \frac{α^{2}}{10}$ (where the Fourier coefficient is computed in $ℤ ∕ p ℤ$ )
(ii) There exists an interval $J \subseteq [N]$ of length $\geq \frac{N}{3}$ such that $| A \cap J | \geq α (1 + \frac{α}{400}) | J |$

Proof. We may assume that $| A^{'} | = | A \cap [p] | \geq α (1 - \frac{α}{200}) p$ since otherwise

\begin{array}{l} | A \cap [p + 1, N] | & \geq α N - (α (1 - \frac{α}{200}) p) \\ = α (N - p) + \frac{α^{2}}{200} p \\ \geq (α + \frac{α^{2}}{400}) (N - p) \end{array}

so we would be in Case (ii) with $J = [p + 1, N]$ . Let $A^{″} = A^{'} \cap [\frac{p}{3}, \frac{2 p}{3}]$ . Note that all 3 term arithmetic progressions of the form $(x, x + d, x + 2 d) \in A^{'} \times A^{″} \times A^{″}$ are in fact arithmetic progressions in $[N]$ .

If $| A^{'} \cap [\frac{p}{3}] |$ or $| A^{'} \cap [\frac{2 p}{3}, p] |$ were at least $\frac{2}{5} | A^{'} |$ , we would again be in case (ii). So we may assume that $| A^{″} | \geq \frac{| A^{'} |}{5}$ .

Now as in Lemma 2.18 and Theorem 2.19,

\begin{array}{l} \frac{α^{″}}{p} & = \frac{| A^{″} |}{p^{2}} \\ T_{3} (𝟙_{A^{'}}, 𝟙_{A^{″}}, 𝟙_{A^{″}}) \\ = α^{'} {(α^{″})}^{2} + \sum_{t} \bar{\hat{𝟙_{A^{'}}} (t) \hat{𝟙_{A^{″}}} (t)} \hat{𝟙_{2 \cdot A^{″}}} (t) \end{array}

where $α^{'} = \frac{| A^{'} |}{p}$ and $α^{″} = \frac{| A^{″} |}{p}$ . So as before,

\frac{α^{'} α^{″}}{2} \leq \sup_{t \neq 0} | 𝟙_{A^{'}} (t) | \cdot α^{″},

provided that $\frac{α^{″}}{p} \leq \frac{1}{2} α^{'} {(α^{″})}^{2}$ , i.e. $\frac{2}{p} \leq α^{'} α^{″}$ . (Check this is satisfied).

Hence

\sup_{t \neq 0} | \hat{𝟙_{A^{'}}} (t) | \geq \frac{α^{'} α^{″}}{2} \geq \frac{1}{2} {(α (1 - \frac{α}{200}))}^{2} \cdot \frac{2}{5} \geq \frac{α^{2}}{10} . □

Lemma 2.23. Assuming that:

$m \in ℕ$
$φ : [m] \to ℤ ∕ p ℤ$ be given by $x \mapsto t x$ for some $t \neq 0$
$𝜀 > 0$

Then there exists a partition of

[m]

into progressions

P_{i}

of length

l_{i} \in [\frac{𝜀 \sqrt{m}}{2}, 𝜀 \sqrt{m}]

such that

diam (φ (P_{i})) = \max_{x, y \in P_{i}} | φ (x) - φ (y) | \leq 𝜀 p

for all $i$ .

Proof. Let $u = ⌊ \sqrt{m} ⌋$ and consider $0, t, 2 t, \dots, u t$ . By Pigeonhole, there exists $0 \leq v < w \leq u$ such that $| w t - v t | = | (w - v) t | \leq \frac{p}{u}$ . Set $s = w - v$ , so $| s t | \leq \frac{p}{u}$ . Divide $[m]$ into residue classes modulo $s$ , each of which has size at least $\frac{m}{s} \geq \frac{m}{4}$ . But each residue class can be divided into arithmetic progressions of the form $a, a + s, \dots, a + d s$ with $𝜀 \frac{u}{2} < d \leq 𝜀 u$ . The diameter of the image of each progression under $φ$ is $| d s t | \leq d \frac{p}{u} \leq 𝜀 u \frac{p}{u} = 𝜀 p$ . □

Lemma 2.24. Assuming that:

$A \subseteq [N]$ of density $α > 0$
$p$ a prime in $[\frac{N}{3}, \frac{2 N}{3}]$
let $A^{'} = A \cap [p] \subseteq ℤ ∕ p ℤ$
$| \hat{𝟙_{A^{'}}} (t) | \geq \frac{α^{2}}{20}$ for some $t \neq 0$

Then there exists a progression

P \subseteq [N]

of length at least

α^{2} \frac{\sqrt{N}}{500}

such that

| A \cap P | \geq α (1 + \frac{α}{80}) | P |

Proof. Let $𝜀 = \frac{α^{2}}{40 π}$ , and use Lemma 2.23 to partition $[p]$ into progressions $P_{i}$ of length

\geq 𝜀 \sqrt{\frac{p}{2}} \geq \frac{α^{2}}{40 π} \frac{\sqrt{\frac{N}{3}}}{2} \geq \frac{α^{2} \sqrt{N}}{500}

and $diam (φ (P_{i})) \leq 𝜀 p$ . Fix one $x_{i}$ from each of the $P_{i}$ . Then

\begin{array}{l} \frac{α^{2}}{20} & \leq | \hat{f_{A^{'}}} (t) | \\ = | \frac{1}{p} \sum_{i} \sum_{x \in P_{i}} f_{A^{'}} (x) e (- x t ∕ p) | \\ = \frac{1}{p} | \sum_{i} \sum_{x \in P_{i}} f_{A^{'}} (x) e (- x i t ∕ p) + \sum_{i} \sum_{x \in P_{i}} f_{A^{'}} (x) (e (- x t ∕ p) - e (- x i t ∕ p)) | \\ \leq \frac{1}{p} \sum_{i} | \sum_{x \in P_{i}} f_{A^{'}} (x) | + \frac{1}{p} \sum_{i} \sum_{x \in P_{i}} | f_{A^{'}} (x) | | \underset{\begin{array}{c} \leq 2 π 𝜀 \\ since | t (x - x_{i}) | \leq 𝜀 p \end{array}}{\underset{⏟}{e (- x t ∕ p) - e (- x i t ∕ p)}} | \end{array}

\sum_{i} | \sum_{x \in P_{i}} f_{A^{'}} (x) | \geq \frac{α^{2}}{40} p .

Since $f_{A^{'}}$ has mean zero,

\sum_{i} (| \sum_{x \in P_{i}} f_{A^{'}} (x) | + \sum_{x \in P_{i}} f_{A^{'}} (x)) \geq \frac{α^{2}}{40} p,

hence there exists $i$ such that

| \sum_{x \in P_{i}} f_{A^{'}} (x) | + \sum_{x \in P_{i}} f_{A^{'}} (x) \geq \frac{α^{2}}{80} | P_{i} |

and so

\sum_{x \in P_{i}} f_{A^{'}} (x) \geq \frac{α^{2}}{160} | P_{i} | . □

Definition 2.25 (Bohr set). Let $Γ \subseteq \hat{G}$ and $ρ > 0$ . By the Bohr set $B (Γ, ρ)$ we mean the set

B (Γ, ρ) = {x \in G : | γ (x) - 1 | < ρ \forall γ \in Γ} .

We call $| Γ |$ the rank of $B (Γ, ρ)$ , and $ρ$ its width or radius.

Example 2.26. When $G = 𝔽_{p}^{n}$ , then $B (Γ, ρ) = {⟨ Γ ⟩}^{⊥}$ for all sufficiently small $ρ$ .

Lemma 2.27. Assuming that:

$Γ \subseteq \hat{G}$ of size $d$
$ρ > 0$

Then

| B (Γ, ρ) | \geq {(\frac{ρ}{8})}^{d} | G | .

Proposition 2.28 (Bogolyubov in a general finite abelian group). Assuming that:

$A \subseteq G$ of density $α > 0$

Then there exists

Γ \subseteq \hat{G}

of size at most

2 α^{- 2}

such that

A + A - A - A \supseteq B (Γ, ρ)

Proof. Recall $𝟙_{A} * 𝟙_{A} * 𝟙_{- A} * 𝟙_{- A} (x) = \sum_{γ \in \hat{G}} | \hat{𝟙_{A}} (γ) |^{4} γ (x)$ .

Let $Γ \in {Spec}_{\sqrt{\frac{α}{2}}} (𝟙_{A})$ , and note that, for $x \in B (Γ, \frac{1}{2})$ and $γ \in Γ$ , $Re (γ (x)) > 0$ . Hence, for $x \in B (Γ, \frac{1}{2})$ ,

Re \sum_{γ \in \hat{G}} | \hat{𝟙_{A}} (γ) |^{4} γ (x) = \underset{\geq α^{4}}{\underset{⏟}{Re \sum_{γ \in Γ} | \hat{𝟙_{A}} (γ) |^{4} γ (x)}} + Re \sum_{γ \notin Γ} | \hat{𝟙_{A}} (γ) |^{4} γ (x)

and

| Re \sum_{γ \notin Γ} | \hat{𝟙_{A}} (γ) |^{4} γ (x) | \leq \sup_{γ \notin Γ} | \hat{𝟙_{A}} (γ) |^{2} \sum_{γ \notin Γ} | \hat{𝟙_{A}} (γ) |^{2} \leq {(\sqrt{\frac{α}{2}} \cdot α)}^{2} \cdot α = \frac{α^{4}}{2} . □