additive_combinatorics.tex

\documentclass{article}

% preamble
\def\npart{III}
\def\nyear{2024}
\def\nterm{Lent}
\def\nlecturer{Prof Julia Wolf}
\def\ncourse{Introduction to Additive Combinatorics}
\def\draft{Incomplete}

\input{header}

% and here we go!
\begin{document}
\maketitle

\tableofcontents

\clearpage
\section{Fourier-analytic techniques}

\newlec

Let $G = \F_p^n$ where $p$ is a small fixed prime and $n$ is large.

\begin{notation}
  Given a finite set $B$ and any function $f : B \to \C$, write
  $$\E_{x \in B} f(x) = \frac 1{\abs B} \sum_{x \in B} f(x)$$
  Write $\omega = e^{\frac{\tau i}p}$. Note $\sum_{a \in \F_p} \omega^a = 0$.
\end{notation}

\begin{dfn}
  Given $f : \F_p^n \to \C$, define its {\bf Fourier transform} $\hat f : \F_p^n \to \C$ by
  $$\hat f(t) = \E_{x \in \F_p^n} f(x) \omega^{x \cdot t}$$
\end{dfn}

It is easy to verify the {\bf inversion formula}
$$f(x) = \sum_{t \in \F_p^n} \hat f(t)\omega^{-x \cdot t}$$
Indeed,
\begin{align*}
  \sum_{t \in \F_p^n} \hat f(t) \omega^{-x \cdot t}
  & = \sum_{t \in \F_p^n} \left(\E_y f(y)\omega^{y \cdot t}\right) \omega^{-x \cdot t} \\
  & = \E_y f(y) \sum_t \omega^{(y - x) \cdot t} \\
  & = \E_y f(y) 1_{y = x} p^n \\
  & = f(x)
\end{align*}

\begin{notation}
  Given a set $A$ of a finite group $G$, write
  \begin{itemize}
    \item $1_A$ the {\it characteristic function} of $A$, ie
    $$1_A(x) = \begin{cases}
      1 & \text{ if } x \in A \\
      0 & \text{ if } x \nin A
    \end{cases}$$
    \item $\mu_A$ the {\it characteristic measure} of $A$, ie
    $$\mu_A = \alpha^{-1} 1_A$$
    where $\alpha = \frac{\abs A}{\abs G}$.
    \item $f_A$ the {\it balanced function} of $A$, ie
    $$f_A(x) = 1_A(x) - \alpha$$
  \end{itemize}
\end{notation}

Note $\E_x f_A(x) = 0, \E_x \mu_A(x) = 1, \widehat{1_A}(0) = \E_x 1_A(x) = \alpha$. Writing $-A = \{-a | a \in A\}$, we have
\begin{align*}
  \widehat{1_{-A}}(t)
  & = \E_x 1_{-A}(x) \omega^{x \cdot t} \\
  & = \E_x 1_A(-x) \omega^{x \cdot t} \\
  & = \E_x 1_A(x) \omega^{-x \cdot t} \\
  & = \overline{\widehat{1_A}(t)}
\end{align*}

\begin{eg}\label{ex:dft-subspace}
  Let $V \le \F_p^n$. Then
  $$\widehat{1_V}(t) = \E_x 1_V(x) \omega^{x \cdot t} = \frac{\abs V}{\abs G} 1_{V^\perp}(t)$$
  So
  $$\widehat{\mu_V}(t) = 1_{V^\perp}(t)$$
\end{eg}

\begin{eg}\label{ex:dft-random-set}
  Let $R \subseteq \F_p^n$ be such that each $x$ is included with probability $\frac 12$ independently. Then with high probability
  $$\sup_{t \ne 0} \abs{\widehat{1_R}(t)} = O\left(\sqrt{\frac{\log(p^n)}{p^n}}\right)$$
  This is on Example Sheet 1 using a {\bf Chernoff-type bound}: Given $\C$-valued independent random variables $X_1, \dots, X_n$ with mean $0$ and $\theta \ge 0$, we have
  $$\P\left(\abs{\sum_i X_i} \ge \theta\sqrt{\sum_i \norm{X_i}^2_\infty}\right) \le 4\exp\left(-\frac{\theta^2}4\right)$$
\end{eg}

\begin{eg}
  Let $Q = \{x \in \F_p^n \mid x \cdot x = 0\}$. Then $\abs Q = \left(\frac 1p + O(p^{-n/2})\right)p^n$ and $\sup_{t \ne 0} \abs{\widehat{1_Q}(t)} = O(p^{-\frac n2})$. See Example Sheet 1.
\end{eg}

\begin{notation}
  Given $f, g : \F_p^n \to \C$, write
  \begin{align*}
    \inn f g & = \E_x f(x) \overline{g(x)} \\
    \inn{\hat f}{\hat g} & = \sum_t \hat f(t) \overline{\hat g(t)}
  \end{align*}
  Consequently,
  \begin{align*}
    \norm f_2^2 & = \E_x \abs{f(x)}^2 \\
    \norm{\hat f}_2^2 & = \sum_t \abs{\hat f(t)}^2
  \end{align*}
\end{notation}

\begin{lem}\label{lem:plancherel-parseval}
  For all $f, g : \F_p^n \to \C$,
  \begin{align*}
    \inn f g & = \inn{\hat f}{\hat g} & \text{ (Plancherel)} \\
    \norm f_2 & = \norm{\hat f}_2 & \text{ (Parseval)}
  \end{align*}
\end{lem}
\begin{proof}
  Exercise.
\end{proof}

\begin{dfn}\label{def:large-spec}
  Let $\rho > 0$ and $f : \F_p^n \to \C$. Define the $\rho$-large spectrum of $f$ to be
  $$\Spec_\rho(f) = \{t \mid |\hat f(t)| \ge \rho\norm f_1\}$$
\end{dfn}

\begin{eg}
  By Example \ref{ex:dft-subspace}, if $V \le \F_p^n$, then
  $\Spec_\rho(1_V) = V^\perp$ for all $\rho > 0$.
\end{eg}

\begin{lem}\label{lem:card-large-spec}
  For all $\rho > 0$, $\abs{\Spec_\rho(f)} \le \rho^{-2} \frac{\norm f_2^2}{\norm f_1^2}$.
\end{lem}
\begin{proof}
  $$\norm f_2^2 = \norm{\hat f}_2^2 \ge \sum_{t \in \Spec_\rho(f)} \abs{\hat f(t)}^2 \ge \abs{\Spec_\rho(f)}(\rho \norm f_1)^2$$
\end{proof}

\newlec

\begin{dfn}\label{def:convolution}
  Given $f, g : \F_p^n \to \C$, define their {\bf convolution} $f \ast g : \F_p^n \to \C$ by
  $$(f \ast g)(x) = \E_y f(y)g(x - y)$$
\end{dfn}

\begin{eg}\label{ex:convolution-indicators}
  Given $A, B \subseteq \F_p^n$,
  \begin{align*}
    (1_A \ast 1_B)(x)
    & = \E_y 1_A(y)1_B(x - y) \\
    & = \frac 1{p^n}\abs{A \inter (x - B)} \\
    & = \frac{\#\text{ ways to write } x = a + b, a \in A, b \in B}{p^n}
  \end{align*}
  In particular, the support of $1_A \ast 1_B$ is the {\bf sum set}
  $$A + B = \{a + b \mid a \in A, b \in B\}$$
\end{eg}

\begin{lem}\label{lem:dft-convolution}
  Given $f, g : \F_p^n \to \C$,
  $$\widehat{f \ast g}(t) = \hat f(t) \hat g(t)$$
\end{lem}
\begin{proof}
  \begin{align*}
    \widehat{f \ast g}(t)
    & = \E_x \left(\E_y f(y)g(x - y)\right)\omega^{x \cdot t} \\
    & = \E_y f(y) \E_u g(u)\omega^{(u + y) \cdot t} \\
    & = \hat f(t) \hat g(t)
  \end{align*}
\end{proof}

\begin{eg}
  $\norm{\hat f}_4^4 = \E_{x + y = z + w} f(x)f(y)\overline{f(z)f(w)}$. See Example Sheet 1.
\end{eg}

\begin{lem}[Bogolyubov]
  If $A \subseteq \F_p^n$ is of density $\alpha > 0$, then there exists a subspace $V$ of codimension at most $2\alpha^{-2}$ such that $V \subseteq (A + A) - (A + A)$.
\end{lem}
\begin{proof}
  Observe that $(A + A) - (A + A) = \supp (\underbrace{1_A \ast 1_A \ast 1_{-A} \ast 1_{-A}}_g)$, so we wish to find $V$ such that $g(x) > 0$ for all $x \in V$. Let $K = \Spec_\rho(1_A)$ for some $\rho > 0$ and define $V = \langle K\rangle^\perp$. By Lemma \ref{lem:card-large-spec}, $\codim V \le \abs K \le \rho^{-2}\alpha^{-1}$. We calculate
  \begin{align*}
    g(x)
    & = \sum_{t \in \F_p^n} \widehat{1_A \ast 1_A \ast 1_{-A} \ast 1_{-A}}(t)\omega^{-x \cdot t} \\
    & = \sum_{t \in \F_p^n} \abs{\widehat{1_A}(t)}^4 \omega^{-x \cdot t} \\
    & = \alpha^4 + \underbrace{\sum_{t \in K \setminus \{0\}} \abs{\widehat{1_A}(t)}^4 \omega^{-x \cdot t}}_{(1)} + \underbrace{\sum_{t \nin K} \abs{\widehat{1_A}(t)}^4 \omega^{-x \cdot t}}_{(2)}
  \end{align*}
  We now see that
  $$(1) = \sum_{t \in K \setminus \{0\}} \abs{\widehat{1_A}(t)}^4 \ge 0$$
  and
  $$\abs{(2)} \le \sum_{t \nin K} \abs{\widehat{1_A}(t)}^4 \le \sup_{t \nin K} \abs{\widehat{1_A}(t)}^2 \sum_{t \nin K} \abs{\widehat{1_A}(t)}^2 \le (\rho\alpha)^2\norm{1_A}_2^2 = \rho^2\alpha^3$$
  by Parseval. Picking $\rho = \sqrt{\frac\alpha 2}$, we thus get $\rho^2\alpha^3 \le \frac{\alpha^4}2$ and $g(x) > 0$ whenever $x \in V$.
\end{proof}

\begin{eg}
  The set $A = \{x \in \F_2^n \mid \abs x \ge \frac n2 + \frac{\sqrt n}2\}$ has density at least $\frac 14$ but there is no coset $C$ of any subspace of codimension $\sqrt n$ such that $C \subseteq A + A$. See Example Sheet 1.
\end{eg}

\begin{lem}\label{lem:density-increment}
  Let $A \subseteq \F_p^n$ of density $\alpha$ be such that $\Spec_\rho(1_A)$ contains some $t \ne 0$. Then there exist $V \le \F_p^n$ of codimension $1$ and $x \in \F_p^n$ such that
  $$\abs{A \inter (x + V)} \ge \alpha\left(1 + \frac\rho 2\right)\abs V$$
\end{lem}
\begin{proof}
  Let $t \ne 0$ be such that $\abs{\widehat{1_A}(t)} \ge \rho\alpha$ and let $V = \langle t\rangle^\perp$. For $j = 1, \dots, p$, write
  $$v_j + V = \{x \in \F_p^n \mid x \cdot t = j\}$$
  the cosets of $V$. Then
  \begin{align*}
    \widehat{1_A}(t)
    & = \widehat{f_A}(t) \\
    & = \E_{x \in \F_p^n}(1_A(x)) - \alpha)\omega^{x \cdot t} \\
    & = \E_j \omega^j \E_{x \in v_j + V} (1_A(x) - \alpha) \\
    & = \E_j a_j \omega^j
  \end{align*}
  where $a_j = \frac{\abs{A \inter (v_j + V)}}{\abs V} - \alpha$. Since $\sum_j a_j = 0$, we get
  $$\rho\alpha \le \abs{\widehat{1_A}(t)} \le \E_j \abs{a_j} = \E_j (\abs{a_j} + a_j)$$
  So there is some $j$ such that $\abs{a_j} + a_j \ge \rho\alpha$. In particular, this $a_j$ is positive, so
   $$\frac{\abs{A \inter (v_j + V)}}{\abs V} \ge \alpha + \frac{\rho\alpha}2$$
   as wanted.
\end{proof}

\newlec

\begin{lem}\label{lem:3AP-estimate}
  Let $p \ge 3$ and $A \subseteq \F_p^n$ of density $\alpha > 0$ be such that $\sup_{t \ne 0} \abs{\widehat{1_A}(t)} = o(1)$. Then $A$ contains $(\alpha^3 + o(1))\abs G^2$ three terms arithmetic progressions (aka 3AP).
\end{lem}

\begin{notation}
  Given $f, g, h : \F_p^n \to \C$, write
  $$T_3(f, g, h) = \E_x f(x) g(x + d) h(x + 2d)$$
  Given $A \subseteq \F_p^n$, write $2 \cdot A = \{2a \mid a \in A\}$. This is distinct from $2A = \{a + b \mid a, b \in A\}$.
\end{notation}

\begin{proof}
  The number of 3AP (including the trivial ones of the form $a, a, a$) in $A$ is $\abs G^2$ times
  \begin{align*}
    T_3(1_A, 1_A, 1_A)
    & = \E_{x, d} 1_A(x) 1_A(x + d) 1_A(x + 2d) \\
    & = \E_{x, y} 1_A(x) 1_A(y) 1_A(2y - x) \\
    & = \E_y (1_A \ast 1_A)(2y) 1_A(y) \\
    & = \inn{1_A \ast 1_A}{1_{2 \cdot A}} \\
    & = \inn{\widehat{1_A}^2}{\widehat{1_{2 \cdot A}}} \\
    & = \alpha^3 + \sum_{t \ne 0} \widehat{1_A}(t)^2 \overline{\widehat{1_{2 \cdot A}}(t)} \text{ by Plancherel}
  \end{align*}
  In absolute value, the error term is at most
  $$\sup_{t \ne 0} \abs{\widehat{1_{2 \cdot A}}(t)} \sum_t \abs{\widehat{1_A}(t)}^2 = \alpha \sup_{t \ne 0} \abs{\widehat{1_A}(t)}$$
\end{proof}

\begin{thm}[Meshulam]\label{thm:meshulam}
  Let $p \ge 3$ and $A \subseteq \F_p^n$ be a set containing only trivial 3APs. Then
  $$\abs A = O\left(\frac{p^n}{\log(p^n)}\right)$$
\end{thm}
\begin{proof}
  By assumption, $T_3(1_A, 1_A, 1_A) = \frac\alpha{p^n}$. But, as in Lemma \ref{lem:3AP-estimate},
  $$\abs{T_3(1_A, 1_A, 1_A) - \alpha^3} \le \alpha \sup_{t \ne 0} \abs{\widehat{1_A}(t)}$$
  Hence, provided that $2\alpha^{-2} \le p^n$, Lemma \ref{lem:density-increment} gives us a subspace $V \le \F_p^n$ of codimension $1$ and $x \in \F_p^n$ such that
  $$\abs{A \inter (x + V)} \ge \alpha\left(1 + \frac{\alpha^2}4\right)\abs V$$
  We iterate this observation. Let $A_0 = A, V_0 = \F_p^n$. At step $i$, we are given a set $A_i \subseteq V_i$ of density $\alpha_i$ with only trivial 3APs. Provided that $2\alpha_i^{-2} \le p^{\dim V_i}$, find $V_{i + 1} \le V_i$ of codimension $1$ and $x \in V_i$ such that $\abs{A_i \inter (x + V_i)} \ge \left(\alpha_i + \frac{\alpha_i^2}4\right)\abs{V_{i + 1}}$ and set $A_{i + 1} = (A_i - x) \inter V_i$. Note that $\alpha_{i + 1} \ge \alpha_i + \frac{\alpha_i^2}4$ and $A_{i + 1}$ only contains trivial 3APs (because, very importantly, 3AP are {\bf translation-invariant}). \\
  Through this iteration, the density of $A$ increases from $\alpha$ to $2\alpha$ in at most $\lceil 4\alpha^{-1}\rceil$ steps, from $2\alpha$ to $4\alpha$ in at most $\lceil 2\alpha^{-1}\rceil$ steps, etc... Since density can't increase past $1$, it takes at most
  $$\underbrace{\lceil 4\alpha^{-1}\rceil + \lceil 2\alpha^{-1}\rceil + \dots}_{\lceil \log \alpha^{-1}\rceil \text{ terms}} \le (4\alpha^{-1} + 1) + (2\alpha^{-1} + 1) + \dots \le 8\alpha^{-1} + \log \alpha^{-1} + 1 \le 9\alpha^{-1}$$
  steps to reach a point where the condition $2\alpha_i^{-2} \le p^{\dim V_i}$ is not respected anymore. Now either $\alpha \le \sqrt 2 p^{-\frac n4}$ (in which case the inequality is obvious) or $\alpha \ge \sqrt 2 p^{-\frac n4}$ and
  $$p^{n - 9\alpha^{-1}} \le p^{\dim V_i} \le 2\alpha_i^{-2} \le 2\alpha^{-2} \le p^{\frac n2}$$
  namely $\alpha \le \frac{18}n$, as wanted.
\end{proof}

\newlec

We have proved that if $A \subseteq \F_3^n$ only contains trivial 3APs then $\abs A = O(\frac{3^n}n)$. The largest known set in $\F_3^n$ with only trivial 3APs has size $\ge 2.218^n$ (Tyrrell, 2022). We will return to this later.

From now on, let $G$ be a finite abelian group. $G$ comes equipped with a set of {\bf characters}, ie group homomorphisms $\gamma : G \to \C^\times$. Characters themselves form a group denoted $\hat G$ and called the {\bf Pontryagin dual} (aka {\bf dual group}) of $G$. It turns out that if $G$ is finite abelian then $\hat G \cong G$ (but {\it non-canonically}). For instance,
\begin{itemize}
  \item If $G = \F_p^n$, then $\hat G = \{\gamma_t : x \mapsto \omega^{x \cdot t} \mid t \in G\}$
  \item If $G = \Z/n\Z$, then $\hat G = \{\gamma_t : x \mapsto \omega^{xt} \mid t \in G\}$
\end{itemize}
The latter is a special case of the former, but again $n$ should thought of as an asymptotic variable.

\begin{dfn}
  Given $f : G \to \C$, define its {\bf Fourier transform} $\hat f : \hat G \to \C$ by
  $$\hat f(\gamma) = \E_{x \in G} f(x)\gamma(x)$$
\end{dfn}
It is easy to verify that $f(x) = \sum_{\gamma \in \hat G} \hat f(\gamma) \overline{\gamma(x)}$. Similarly, Definitions \ref{def:large-spec}, \ref{def:convolution}, Examples \ref{ex:dft-random-set}, \ref{ex:convolution-indicators} and Lemmas \ref{lem:plancherel-parseval}, \ref{lem:card-large-spec}, \ref{lem:dft-convolution} go through in this more general context.

\begin{eg}
  Let $p$ be a prime, $L < p$ be even and $J = [-\frac L2, \frac L2] \subseteq \F_p$. Then for all $t \ne 0$ we have
  $$\widehat{1_J}(t) \le \min\left(\frac{L + 1}p, \frac 1{2\abs t}\right)$$
  See Example Sheet 1.
\end{eg}

\begin{thm}[Roth]
  Let $A \subseteq [N]$ be a set containing only trivial 3APs. Then $\abs A = O(\frac N{\log\log N})$.
\end{thm}

\begin{lem}
  Let $A \subseteq [N]$ of density $\alpha > 0$ containing only trivial 3APs and satisfying $N > 50\alpha^{-2}$. Let $p$ be a prime in $[\frac N3, \frac{2N}3]$ and write $A' = A \inter [p] \subseteq \F_p$. Then either
  \begin{enumerate}
    \item $\sup_{t \ne 0} \abs{\widehat{1_A}(t)} \ge \frac{\alpha^2}{10}$ (where the Fourier coefficients are computed in $\F_p$)
    \item or there exists an interval $J$ of length $\ge \frac N3$ such that
    $$\abs{A \inter J} \ge \alpha\left(1 + \frac\alpha{400}\right)\abs J$$
  \end{enumerate}
\end{lem}
\begin{proof}
  If $\abs{A'} \le \alpha\left(1 - \frac\alpha{200}\right)p$, then
  $$\abs{A \inter [p + 1, N]} \ge \alpha(N - p) + \frac{\alpha^2p}{200} \ge \alpha\left(1 + \frac\alpha{400}\right)(N - p)$$
  and we are in Case 2 with $J = [p + 1, N]$. Let $A'' = A' \inter [\frac p3, \frac{2p}3]$. Note that all 3APs of the form $(x, x + d, x + 2d) \in A' \times A'' \times A''$ are in fact 3APs in $[N]$ (and in particular they are trivial). \\
  If $\abs{A' \inter [\frac p3]}$ or $\abs{A' \inter [\frac{2p}3, p]}$ were at least $\frac 25\abs{A'}$, then we would again be in Case 2. We may therefore assume that $\abs{A''} \ge \frac{\abs{A'}}5$. \\
  Now, as in Lemma \ref{lem:3AP-estimate} and Theorem \ref{thm:meshulam} with $\alpha' = \frac{\abs{A'}}p, \alpha'' = \frac{\abs{A''}}p$,
  $$\frac{\alpha''}p = T_3(1_{A'}, 1_{A''}, 1_{A''}) = \alpha'\alpha''^2 + \sum_{t \ne 0}\widehat{1_{A'}}(t)\widehat{1_{A''}}(t)\overline{\widehat{1_{2 \cdot A'}}(t)}$$
  So, as before, $\frac{\alpha'\alpha''}2 \le \alpha''\sup_{t \ne 0} \abs{\widehat{1_{A'}}(t)}$, provided $\frac{\alpha''}p \le \frac{\alpha'\alpha''^2}2$. This holds by assumption since $p \ge \frac N3, N \ge 50\alpha^{-2}, \alpha' \ge \frac{199}{200}\alpha, \alpha'' \ge \frac{\alpha'}5$.
\end{proof}

\newlec

We now want to convert the large Fourier coefficient into a density increment. This is harder now that the number of values of $xt$ grows as $n \to \infty$. Compare this to the finite field case where $x \cdot t$ only take $p$ different values regardless of $n$. If we can't find a single big coefficient, then we might instead be able to find an interval of coefficients whose total contribution is big.

TODO: Insert picture

\begin{lem}\label{lem:partition-progressions-small-diam}
  Let $m \in \N$ and $\phi : [m] \to \F_p$ be multiplication by some fixed $t \ne 0$. Given $\eps > 0$, there exists a partition of $[m]$ into progressions $P_i$ of length $\in [\frac{\eps\sqrt m}2, \eps\sqrt m]$ such that $\diam(\phi(P_i)) \le \eps p$.
\end{lem}
\begin{proof}
  Let $u = \floor{\sqrt m}$ and consider $0, t, \dots, ut$. By pigeonhole, find $0 \le v < w \le u$ such that $\abs{wt - vt} \le \frac pu$. Set $s = w - v \le u$ so that $\abs{st} \le \frac pu$. Divide $[m]$ into residue classes mod $s$. Each has size at least $\floor{\frac ms} \ge \floor{\frac mu}$ and can be divided into progressions of the form $a, a + s, \dots, a + ds$ with $\frac{\eps u}2 < d \le \eps u$. The diameter of each progression under $\phi$ is $\abs{dst} \le \eps p$.
\end{proof}

\begin{lem}
  Let $A \subseteq [N]$ be of density $\alpha > 0$. Let $p$ be a prime in $[\frac N3, \frac{2N}3]$ and write $A' = A \inter [p]$. Suppose there exists $t \ne 0$ such that $\abs{\widehat{1_A}(t)} \ge \frac{\alpha^2}{10}$. Then there exists a progression $P$ of length at least $\alpha^2 \frac{\sqrt N}{500}$ such that
  $$\abs{A \inter P} \ge \alpha\left(1 + \frac\alpha{50}\right)\abs P$$
\end{lem}
\begin{proof}
  Let $\eps = \frac{\alpha^2}{40\pi}$ and use Lemma \ref{lem:partition-progressions-small-diam} to partition $[p]$ into progressions $P_i$ of length at least $\frac{\eps \sqrt p}2 \ge \frac{\alpha^2}{80\pi}\sqrt{\frac N3} \ge \frac{\alpha^2\sqrt N}{500}$ and $\diam \phi(P_i) \le \eps p$. Fix one $x_i$ inside each $P_i$.
  \begin{align*}
    \frac{\alpha^2}{10}
    & \le \abs{\widehat{f_{A'}}(t)} \\
    & = \frac 1p\abs{\sum_i\sum_{x \in P_i} f_{A'}(x)\omega^{xt}} \\
    & = \frac 1p\abs{\sum_i\sum_{x \in P_i} f_{A'}(x)\omega^{x_it} + \sum_i\sum_{x \in P_i} f_{A'}(x)(\omega^{xt} - \omega^{x_it})} \\
    & \le \frac 1p\sum_i\abs{\sum_{x \in P_i} f_{A'}(x)\omega^{x_it}} + \frac 1p\sum_i\sum_{x \in P_i} \abs{f_{A'}(x)} 2\pi\eps \\
    & \le \frac 1p\sum_i\abs{\sum_{x \in P_i} f_{A'}(x)\omega^{x_it}} + \frac{\alpha^2}{20}
  \end{align*}
  So
  $$\sum_i \abs{\sum_{x \in P_i} f_{A'}(x)} \ge \frac{\alpha^2p}{20}$$
  Since $f_{A'}$ has mean zero, there exists $i$ such that $\sum_{x \in P_i} f_{A'}(x) \ge \frac{\alpha^2\abs{P_i}}{40}$.
\end{proof}

\begin{proof}[Proof of Roth's theorem]
  Put the ingredients together, Similarly to Meshulam. See Example Sheet 1 for details.
\end{proof}

\begin{eg}[Behrend's construction]
  There exists a set $A \subseteq [N]$ containing non nontrivial 3APs of size at least $e^{-O(\sqrt{\log n})}$. See Example Sheet 1.
\end{eg}

\begin{dfn}
  Let $\Gamma \subseteq \hat G$. The {\bf Bohr set} of {\bf frequencies} $\Gamma$ and width $\rho$ is
  $$B(\Gamma, \rho) = \{x \in G \mid \for \gamma \in \Gamma, \abs{\gamma(x) - 1} \le \rho\}$$
  $\abs\Gamma$ is the {\bf rank} of the Bohr set.
\end{dfn}

\begin{eg}
  When $G = \F_p^n$, $B(\Gamma, \rho) = \langle\Gamma\rangle^\perp$ for all small enough $\rho$ (depending only on $p$, not $n$).
\end{eg}

\begin{lem}
  Let $B$ be a Bohr set of rank $d$ and width $\rho$. Then $\abs B \ge \left(\frac\rho{2\pi}\right)^d\abs G$.
\end{lem}
\begin{proof}
  See Example Sheet 2.
\end{proof}

\newlec

\begin{lem}[Bogolyubov]
  Given $A \subseteq \F_p$ of density $\alpha > 0$, there exists $\Gamma \subseteq \widehat{\F_p}$ of size at most $2\alpha^{-2}$ such that $B(\Gamma, \frac 12) \subseteq (A + A) - (A + A)$.
\end{lem}
\begin{proof}
  Recall $(1_A \ast 1_A \ast 1_{-A} \ast 1_{-A})(x) = \sum_{t \in \widehat{\F_p}} \abs{\widehat{1_A}(t)}^4 \omega^{-xt}$. Let $\Gamma = \Spec_{\sqrt{\frac\alpha 2}}(1_A)$ and note that we have $\cos(\frac{2\pi xt}p) > 0$ for all $x \in B(\Gamma, \frac 12)$ and $t \in \Gamma$. Hence
  \begin{align*}
    \Re \sum_{t \in \widehat{\F_p}} \abs{\widehat{1_A}(t)}^4 \omega^{-xt}
    & = \sum_{t \in \Gamma} \abs{\widehat{1_A}(t)}^4 \cos\left(\frac{2\pi xt}p\right) + \sum_{t \notin \Gamma} \abs{\widehat{1_A}(t)}^4 \cos\left(\frac{2\pi xt}p\right) \\
    & \ge \alpha^4 - \frac{\alpha^4}2 > 0
  \end{align*}
\end{proof}

\clearpage
\section{Combinatorial methods}

For now, let $G$ be an abelian group. Given $A, B \subseteq G$, we defined
$$A \pm B = \{a \pm b \mid a \in A, b \in B\}$$
If $A$ and $B$ are finite and nonempty, then
$$\max(\abs A, \abs B) \le \abs{A \pm B} \le \abs A\abs B$$
Better bounds are available in certain settings.

\begin{eg}
  Let $V \le \F_p^n$ be a subspace. Then $V + V$, so $\abs{V + V} = \abs V$. In fact, if $A \subseteq \F_p^n$ is such that $\abs{A + A} = \abs A$, then $A$ is a coset of some subspace.
\end{eg}

\begin{eg}\label{ex:doubling-lt-three-halves}
  Let $A \subseteq \F_p^n$ be such that $\abs{A + A} < \frac 32 \abs A$. Then there exists $V \le \F_p^n$ such that $A$ is contained in a coset of $V$ and $\abs V < \frac 32\abs A$. See Example Sheet 2.
\end{eg}

\begin{eg}
  Let $A \subseteq \F_p^n$ be a set of linearly independent vectors. Then $\abs{A + A} = \binom{\abs A + 1}2$. This is big doubling, but $\abs A \le n$ is small! \\
  Let $A \subseteq \F_p^n$ be a set where each point is taken randomly with probability $p^{-\theta n} = N^{-\theta}$ where $\theta \in ]\frac 12, 1]$. Then with high probability $\abs{A + A} = (1 + o(1))\frac{\abs A^2}2$.
\end{eg}

\begin{dfn}
  Given finite sets $A, B \subseteq G$, we define the Ruzsa distance between $A$ and $B$ to be
  $$d(A, B) = \log \frac{\abs{A - B}}{\sqrt{\abs A\abs B}}$$
\end{dfn}

$d(A, B)$ is clearly nonnegative and symmetric. However, $d(A, A) \ne 0$ in general.

\begin{lem}[Ruzsa's triangle inequality]\label{lem:ruzsa-triangle}
  For $A, B, C \subseteq G$ finite,
  $$d(A, C) \le d(A, B) + d(B, C)$$
\end{lem}
\begin{proof}
  The inequality reduces to
  $$\abs B\abs{A - C} \le \abs{A - B}\abs{B - C}$$
  This is true because
  \begin{align*}
    \phi : B \times (A - C) & \to (A - B) \times (B - C) \\
    (b, d) & \mapsto (a_d - b, b - c_d)
  \end{align*}
  is injective, where for each $d \in A - C$ we have chosen $a_d \in A, c_d \in C$ such that $d = a_d - c_c$.
\end{proof}

\begin{dfn}
  Given a finite set $A \subseteq G$, we write $\sigma(A) = \frac{\abs{A + A}}{\abs A}$ the {\bf doubling constant} and $\delta(A) = \frac{\abs{A - A}}{\abs A}$ the {\bf difference constant} of $A$.
\end{dfn}

$d(A, A) = \log \sigma(A)$ and $d(A, -A) = \log \delta(A)$, so Lemma \ref{lem:ruzsa-triangle} for $A, -A, -A$ tells us that $\delta(A) \le \sigma(A)^2$.

\newlec

\begin{notation}
  Given $A \subseteq G$ and $\ell, m \in \N$, write $\ell A - m A$ for the set
  $$\underbrace{A + \dots + A}_{\ell \text{ times}} - \underbrace{A - \dots - A}_{m \text{ times}}$$
\end{notation}

\begin{thm}[Plünnecke's inequality]
  Let $A, B \subseteq G$ be finite such that $\abs{A + B} \le K\abs A$. Then for all $\ell, m$,
  $$\abs{\ell B - mB} \le K^{\ell + m}\abs A$$ww
\end{thm}
\begin{idea}
  $A$ should be thought of as being approximately a subspace. The assumption then says that $B$ is efficiently contained in (a translate of) $A$ and the conclusion now reads that $B$ must itself have small multiples. This makes sense, since we can use multiples of $A$ (which are not much bigger than $A$) to efficiently contain the multiples of $B$.
\end{idea}
\begin{proof}
  WLOG $\abs{A + B} = K\abs A$. Choose $A' \subseteq A$ nonempty such that the ratio $\frac{\abs{A' + B}}{\abs{A'}} = K'$ is minimised. Note $K' \le K$ and $\abs{A'' + B} \ge K'\abs{A''}$ for all $A'' \subseteq A$.
  \begin{claim}
    For all finite $C \subseteq G$, $\abs{A' + B + C} \le K'\abs{A' + C}$.
  \end{claim}
  From the claim, we show that $\abs{A' + mB} \le K'^m\abs{A'}$ for all $m$ by induction:
  That's true for $m = 0$. For $m + 1$, the claim with $C = mB$ gives
  $$\abs{A' + (m + 1)B} = \abs{A' + B + C} \le K'\abs{A' + C} \le K'^{m + 1}\abs{A'}$$
  Now, by the triangle inequality,
  $$\abs{A'}\abs{\ell B - mB} \le \abs{A' + \ell B}\abs{A' + mB} \le K'^\ell \abs{A'} K'^m \abs{A'}$$
  Namely, $\abs{\ell B - mB} \le K'^{\ell + m}\abs{A'} \le K^{\ell + m} \abs A$.
  \begin{proof}[Proof of the claim]
    Do induction on $C$. For $C = \emptyset$, it's true. For $C' = C \union \{x\}$ with x $\notin C$, observe that
    \begin{align*}
      A' + B + C'
      & = A' + B + C \union A' + B + x \\
      & = A' + B + C \union A' + B + x \setminus D + B + x
    \end{align*}
    where $D = \{a \in A' \mid a + B + x \subseteq A' + B + C\}$. By definition of $K'$, $\abs{D + B} \ge K'\abs D$, so
    \begin{align*}
      \abs{A' + B + C'}
      & \le \abs{A' + B + C} + \abs{A' + B + x \setminus D + B + x} \\
      & \le \abs{A' + B + C} + \abs{A' + B} - \abs{D + B} \\
      & \le K'\abs{A' + C} + K'\abs{A'} - K'\abs D \\
      & = K'(\abs{A' + C} + \abs{A'} - \abs D)
    \end{align*}
    We now apply the same argument again, writing
    $$A' + C' = A' + C \union A' + x \setminus E + x$$
    where $E = \{a \in A' \mid a + x \in A' + C\} \subseteq D$. This time, the union is disjoint, so
    $$\abs{A '+ C'} = \abs{A' + C} + \abs{A'} - \abs E \ge \abs{A' + C} + \abs A - \abs D$$
    Hence $\abs{A' + B + C'} \le K'\abs{A' + C'}$ which proves the claim.
  \end{proof}
\end{proof}

We are now in a position to generalise Example \ref{ex:doubling-lt-three-halves}.

\begin{thm}[Freiman-Ruzsa]\label{thm:freiman-ruzsa}
  Let $A \subseteq \F_p^n$ be such that $\abs{A + A} \le K\abs A$ for some $K > 0$. Then $A$ is contained in a subspace $H \le \F_p^n$ of size $\abs H \le K^2 p^{K^4} \abs A$.
\end{thm}
\begin{proof}
  Write $S = A - A$ and choose $X \subseteq A + S$ maximal such that the translates $x + A$ for $x \in X$ are disjoint. \\
  $X$ cannot be too large. Indeed, $\forall x \in X, x + A \subseteq 2A + S$. Hence $\Union_{x \in X} (x + A) \subseteq 2A + S$ and $\abs X\abs A = \abs{\Union_{x \in X} (x + A)} \le \abs{2A + S} \le K^4\abs A$ by Plünnecke, namely $\abs X \le K^4$. \\
  Now observe that $A + S \subseteq X + S$. Indeed, if $y \in A + S$, then either $y \in X \subseteq X + S$ (because $0 \in S$) or $y \notin X$, meaning that $x + A$ and $y + A$ are not disjoint ($X$ is maximal), namely $y \in x + A - A \subseteq X + S$. \\
  By induction, $\ell A + S \subseteq \ell X + S$ for all $\ell$. Hence, writing
  $$H = \langle A\rangle = \Union_\ell (\ell A + S) \subseteq \Union_\ell (\ell X + S) = \langle X\rangle + S$$
  the subgroup generated by $A$, we see that $A$ is contained in a subgroup of size
  $$\abs H \le \abs{\langle X\rangle}\abs S \le p^{\abs X}K^2\abs A \le K^2p^{K^4}\abs A$$
\end{proof}

\newlec

\begin{eg}
  Let $A = H \union R \subseteq \F_p^n$ where $H$ is a subspace of dimension $K \ll d \ll n - k$ and $R$ consists of $K - 1$ linearly independent vectors in $H^\perp$. Then $\abs A = \abs{H \union R} \sim \abs H$ and $\abs{A + A} = \abs{H \union H + R \union R + R} \sim K\abs H \sim K\abs A$ but any subspace $V \le \F_p^n$ containing $A$ must have size $\ge p^{d + (K - 1)} = p^{K - 1} \abs H \sim p^{K - 1}\abs A$ where the constant is exponential in $K$.
\end{eg}

\begin{conj}[Polynomial Freiman-Ruzsa]
  Let $A \subseteq \F_p^n$ be such that $\abs{A + A} \le K\abs A$. Then there is a subspace $H \le \F_p^n$ of size at most $C_1(K)\abs A$ and $x \in \F_p^n$ such that $\abs{A \inter (x + H)} \ge \frac{\abs A}{C_2(K)}$ where $C_1(K)$ and $C_2(K)$ are polynomials.
\end{conj}

For $p = 2$, this is now a theorem.

\begin{dfn}
  Given an abelian group $G$ and finite sets $A, B \subseteq G$, define {\bf additive quadruples} to be the tuples $(a, a', b, b') \in A^2 \times B^2$ such that $a + b = a' + b'$ and the {\bf additive energy between $A$ and $B$} to be
  $$E(A, B) = \frac{\#\{\text{additive quadruples}\}}{\abs A^{\frac 32}\abs B^{\frac 32}}$$
  Write $E(A) = E(A, A)$ the {\bf additive energy of $A$}.
\end{dfn}

Observe that, if $G$ is finite, then
\begin{align*}
  \abs A^3 E(A)
  & = \abs G^3 \E_{x + y = z + w} 1_A(x)1_A(y)1_A(z)1_A(w) \\
  & = \abs G^3 \norm{\widehat{1_A}}_4^4
\end{align*}

\begin{eg}
  When $H \le \F_p^n$, we have $E(H) = 1$.
\end{eg}

\begin{lem}\label{lem:energy-lower-bound}
  Let $G$ be abelian and $A, B \subseteq G$ be finite. Then $E(A, B) \ge \frac{\sqrt{\abs A\abs B}}{\abs{A \pm B}}$. 
\end{lem}
\begin{proof}
  Write $r(x) = \#\{(a, b) \in A \times B \mid a + b = x\}$ so that
  $$\abs A^{\frac 32}\abs B^{\frac 32}E(A, B) = \#\{\text{additive quadruples}\} = \sum_x r(x)^2$$
  Observe that $\sum_x r(x) = \abs A\abs B$, therefore
  \begin{align*}
    \abs A^{\frac 32}\abs B^{\frac 32} E(A, B)
    & = \sum_x r(x)^2 \\
    & \ge \frac{\sum_x r(x)1_{A + B}(x)}{\sum_x 1_{A + B}(x)^2} \text{ by Cauchy-Schwarz} \\
    & = \frac{(\abs A\abs B)^2}{\abs{A + B}}
  \end{align*}
  and similarly for $A - B$.
\end{proof}

In particular, if $\abs{A + A} \le K\abs A$ then $E(A) \ge \frac 1K$. The mantra is "Small doubling implies big energy". The converse is {\bf not} true.

\begin{eg}
  Let $G$ be your favorite family of abelian groups. Then there are constants $\eta, \theta > 0$ such that for all sufficiently large $n$ there exists $A \subseteq G$ with $\abs A = n$ satisfying $E(A) \gg \eta$ and $\abs{A + A} \ge \theta \abs A^2$. See Example Sheet 2.
\end{eg}

If we can't hope for a set to have small doubling when its energy is big, we might at least be able to find a big subset with big energy.

\begin{thm}[Balog-Szemerédi-Gowers]\label{thm:bsg}
  Let $G$ be an abelian group and let $A \subseteq G$ be finite such that $E(A) \ge \eta$ for some $\eta > 0$. Then there exists $A' \subseteq A$ of size at least $c(\eta)\abs A$ such that $\abs{A' + A'} \le C(\eta)\abs A$ where $c(\eta)$ and $C(\eta)$ are polynomials in $\eta$.
\end{thm}

We first prove a technical lemma using a method known as "dependent random choice".

\begin{lem}\label{lem:bsg-drc}
  Let $A_1, \dots, A_m \subseteq [n]$ and suppose that $\sum_{i, j} \abs{A_i \inter A_j} \ge \delta^2nm^2$. Then there exists $X \subseteq [m]$ of size at least $\frac{\delta^5m}{\sqrt 2}$ such that $\abs{A_i \inter A_j} \ge \frac{\delta^2n}2$ for at least 90\% of the pairs $(i, j) \in X^2$.
\end{lem}
\begin{proof}
  Let $x_1, \dots, x_5$ be taken uniformly at random from $[n]$ and let
  $$X = \{i \in [m] \mid \forall k, x_k \in A_i\}$$
  Observe that $\P(i, j \in X) = \left(\frac{\abs{A_i \inter A_j}}n\right)^5$. Hence
  $$\frac{\E \abs X^2}{m^2} = \E_{i, j} \P(i, j \in X) \ge \left(\frac{\E_{i, j} \abs{A_i \inter A_j}}n\right)^5 \ge \delta^{10}$$
  Call a pair {\bf bad} if $\abs{A_i \inter A_j} < \frac{\delta^2n}2$. Note that
  $$\P(i, j \in X \mid (i, j) \text{ bad}) = \P(x_1 \in A_i \inter A_j \mid (i, j) \text{ bad})^5 \le \frac{\delta^{10}}{2^5}$$
  Hence
  $$\E[\#\{\text{bad pairs in }X^2\}] \le \frac{\delta^{10}m^2}{2^5}$$
  meaning that
  $$\frac{\delta^{10}m^2}2 + 16\E[\#\{\text{bad pairs in }X^2\}] \le \E[\abs X^2]$$
  We can therefore find $x_1, \dots, x_5$ such that $\frac{\delta^{10}m^2}2 + 16\#\{\text{bad pairs in }X^2\} \le \abs X^2$. This both means that $\abs X \ge \frac{\delta^5m}{\sqrt 2}$ and that
  $$\#\{\text{bad pairs in }X^2\} \le \frac{\abs X^2}{16} \le 10\% \abs X^2$$
\end{proof}

\newlec

\begin{proof}[Proof of Balog-Szemerédi-Gowers]
  Call $d$ a {\bf popular difference} if we can write $d = x - y$ with $x, y \in A$ in at least $\frac{\eta\abs A}2$ ways, ie if $r_{A - A}(d) \ge \frac{\eta\abs A}2$.

  There must be at least $\frac{\eta\abs A}2$ popular differences for, if not,
  \begin{align*}
    \eta\abs A^3
    & \le \sum_d r_{A - A}(d)^2 \\
    & = \sum_{d\text{ popular}} r_{A - A}(d)^2 + \sum_{d\text{ unpopular}} r_{A - A}(d)^2 \\
    & < \frac{\eta\abs A}2 \abs A^2 + \frac{\eta\abs A}2\sum_d r_{A - A}(d) \\
    & = \eta\abs A^3 
  \end{align*}
  Define a graph with vertex set $A$ and with $x \sim y$ if $y - x$ is a popular difference. Since we have at least $\frac{\eta\abs A}2$ popular differences, our graph has at least $\frac{\eta^2\abs A^2}4$ (directed) edges. We have $\E_{x, y \in A} \abs{N(x) \inter N(y)} \ge \frac{\eta^4\abs A}{2^4}$. Indeed,
  \begin{align*}
    \E_{x, y \in A} \abs{N(x) \inter N(y)}
    & = \E_{x, y \in A} \sum_{z \in A} 1_{x \sim z} 1_{y \sim z} \\
    & = \sum_{z \in A} \left(\E_{x \in A} 1_{x \sim z}\right)^2 \\
    & \ge \frac 1{\abs A} \left(\sum_{z \in A} \E_{x \in A} 1_{x \sim z}\right)^2 \\
    & = \frac 1{\abs A} \left(\E_{x \in A} \abs{N(x)}\right)^2 \\
    & \ge \frac 1{\abs A} \left(\frac{\eta^2\abs A}4\right)^2 \\
    & = \frac{\eta^4\abs A}{2^4}
  \end{align*}
  We apply Lemma \ref{lem:bsg-drc} with $m = n = \abs A$ and $\delta = \frac{\eta^2}4$ to find a subset $B \subseteq A$ of size $\ge \frac{\eta^{10}\abs A}{2^{11}}$ with the property that $\abs{N(x) \inter N(y)} \ge \frac{\eta^4\abs A}{2^5}$ for at least 90\% of the $x, y \in B$. But then for at least 50\% of the $x \in B$ we have $\abs{N(x) \inter N(y)} \ge \frac{\eta^4\abs A}{2^5}$ for at least 80\% of the $y \in B$ (else $90\% \le \E_{x, y \in B} 1_{(x, y)\text{ good}} < 50\% * 100\% + 50\% * 80\% = 90\%$). Call $A' \subseteq B$ that set of such $x$. On one hand, $\abs{A'} \ge \frac{\abs B}2 \ge \frac{\eta^{10}\abs A}{2^{12}}$. On the other hand, if $x, y \in A'$ then at least 60\% of the $z \in B$, namely at least $\frac{\eta^{10}\abs A}{2^{12}}$ such $z$, are such that
  $$\abs{N(x) \inter N(z)}, \abs{N(y) \inter N(z)} \ge \frac{\eta^4\abs A}{2^5}$$
  We now prove an upper bound on $\abs{A' - A'}$ by showing that each element can be written as a linear combination of distinct octuples in $A$. For each such $z$, there are at least $\left(\frac{\eta^4\abs A}{2^5}\right)^2$ pairs $(u, v)$ with $u \in N(x) \inter N(z), v \in N(y) \inter N(z)$. For each such pair $(u, v)$, we have $x \sim u \sim z \sim v \sim y$, hence the elements $u - x, z - u, v - z, y - v$ are all popular differences and there are at least $\left(\frac{\eta\abs A}2\right)^4$ octuples $(a_1, \dots, a_8) \in A^8$ such that
  $$u - x = a_2 - a_1, z - u = a_4 - a_3, v - z = a_6 - a_5, y - v = a_8 - a_7$$
  In other words, there are at least
  $$\underbrace{\frac{\eta^{10}\abs A}{2^{12}}}_z
    \underbrace{\left(\frac{\eta^4\abs A}{2^5}\right)^2}_{(u, v)}
    \underbrace{\left(\frac{\eta\abs A}2\right)^4}_{(a_1, \dots, a_8)} = \frac{\eta^{22}\abs A^7}{2^{26}}$$
  octuples $(a_1, \dots, a_8) \in A^8$ such that
  $$y - x = (a_8 - a_7) + (a_6 - a_5) + (a_4 - a_3) + (a_2 - a_1)$$
  Since distinct $y - x$ give rise to distinct octuples,
  $$\frac{\eta^{22}\abs A^7}{2^{26}} \abs{A' - A'} \le \abs A^8$$
  namely
  $$\abs{A' - A'} \le \frac{2^{26}}{\eta^{22}}\abs A \le \frac{2^{38}}{\eta^{32}}\abs{A'}$$
\end{proof}

\clearpage
\section{Probabilistic tools}

\begin{prop}[Khintchine's inequality]
  Let $X_1, \dots, X_n$ be independent random variables taking values $\pm x_i$ with probability $\frac 12$. Then, for all $p \in [2, \infty[$,
  $$\norm{\sum_i X_i}_{L^p(\P)} = O\left(\sqrt p\left(\sum_i \norm{X_i}_{L^2(\P)}^2\right)^{\frac 12}\right)$$
\end{prop}

\newlec

\begin{proof}
  By nesting of norms, it's enough to prove it when $p = 2k$ for some integer $k$. Write $X = \sum_i X_i$ and WLOG assume that $\sum_i \norm{X_i}_{L^2(\P)}^2 = 1$. By Chernoff,
  $$\norm X_{L^{2k}(\P)}^{2k} = \int_0^\infty 2k t^{2k - 1} \P(\abs X \ge t)\ dt \le 8k \underbrace{\int_0^\infty t^{2k - 1} \exp\left(-\frac{t^2}4\right)\ dt}_{I(k)}$$
  Let's prove by induction on $k$ that $I(k) \le C^{2k}\frac{(2k)^k}{4k}$ for some constant $C > 0$. Indeed if $k = 1$ then
  $$\int_0^\infty t \exp\left(-\frac{t^2}4\right)\ dt = \left. -2\exp\left(-\frac{t^2}4\right)\right|_0^\infty = 2 \le C^2 \frac 24$$
  if $C \ge 2$. For $k > 1$,
  \begin{align*}
    I(k)
    & = \int_0^\infty t^{2k - 2} t \exp\left(-\frac{t^2}4\right)\ dt \\
    & = \left. t^{2k - 2} (-2)\exp\left(-\frac{t^2}4\right)\right|_0^\infty - \int_0^\infty (2k - 2)t^{2k - 3}(-2)\exp\left(-\frac{t^2}4\right)\ dt \\
    & = 4(k - 1)I(k - 1) \\
    & \le 4(k - 1)C^{2(k - 1)}\frac{(2(k - 1))^{k - 1}}{4(k - 1)} \\
    & \le C^{2k}\frac{(2k)^k}{4k}
  \end{align*}
  if $C \ge \sqrt 2$.
\end{proof}

\begin{cor}[Rudin's inequality]
  Let $\Lambda \subseteq \widehat{\F_2^n}$ be linearly independent and $f : \F_2^n \to \C$ be such that $\hat f$ is supported on $\Lambda$. Then, for all $p \in [2, \infty[$,
  $$\norm{\sum_{\gamma \in \Lambda} \hat f(\gamma)\gamma}_{L^p(\F_2^n)} = O\left(\sqrt p \norm f_{L^2(\Lambda)}\right)$$
\end{cor}
\begin{proof}
  See Example Sheet 2.
\end{proof}

\begin{cor}[Dual form of Rudin's inequality]\label{cor:dual-rudin}
  Let $\Lambda \subseteq \widehat{\F_2^n}$ be linearly independent and let $q \in ]1, 2]$ Then for all $f \in L^q(\F_2^n)$,
  $$\norm{\hat f}_{\ell^2(\Lambda)} = O\left(\sqrt{\frac q{q - 1}} \norm f_{L^q(\F_2^n)}\right)$$
\end{cor}
\begin{proof}
  Let $f \in L^q(\F_2^n)$ and write $g = \sum_{\gamma \in \Lambda} \hat f(\gamma)\gamma$. Then
  $$\hat g(\delta) = \E_x \delta(x) \sum_{\gamma \in \Lambda} \hat f(\gamma) \gamma(x) = \sum_{\gamma \in \Lambda} \hat f(\gamma) \E_x \gamma(x)\delta(x) = 1_\Lambda(\delta) \hat f(\delta)$$
  So $\hat g$ is supported on $\Lambda$ and
  $$\norm{\hat f}_{\ell^2(\Lambda)}^2 = \sum_{\gamma \in \Lambda} \abs{\hat f(\gamma)}^2 = \sum_{\gamma \in \Lambda} \hat f(\gamma)\overline{\hat g(\gamma)} = \langle\hat f, \hat g\rangle_{\ell_2(\F_2^n)} = \inn f g_{L^2(\F_2^n)}$$
  By Hölder,
  $$\inn f g_{L^2(\F_2^n)} \le \norm f_{L^q(\F_2^n)}\norm g_{L^p(\F_2^n)}$$
  where $\frac 1p + \frac 1q = 1$. By Rudin,
  $$\norm g_{L^p(\F_2^n)} = O(\sqrt p \norm{\hat g}_{\ell^2(\Lambda)}) = O\left(\sqrt{\frac q{q - 1}} \norm{\hat f}_{\ell^2(\Lambda)}\right)$$
  Putting all of this together, we get the result.
\end{proof}

Recall that, given $A \subseteq \F_2^n$ of density $\alpha > 0$, $\abs{\Spec_\rho(1_A)} \le \rho^{-2}\alpha^{-1}$. This is best possible, as the example of a subspace $H \le \F_2^n$ shows:
$$\abs{\Spec_1(1_H)} = \abs{H^\perp} = \left(\frac{\abs H}{2^n}\right)^{-1}$$
But here $H$ is very structured! And indeed in Bogolyubov we used the bound on the size of the spectrum only to bound the size of the subspace it generated. So maybe the {\it dimension} of the spectrum is what we should be looking at instead of its size.

\begin{thm}[Special case of Chang's lemma]
  Let $A \subseteq \F_2^n$ be of density $\alpha > 0$. Then for all $\rho > 0$ there exists a subspace $H \le \F_2^n$ of dimension $O(\rho^{-2}\log\alpha^{-1})$ such that $\Spec_\rho(1_A) \subseteq H$.
\end{thm}
\begin{proof}
  Let $\Lambda \subseteq \Spec_\rho(1_A)$ be a maximal linearly independent subset and let $H = \langle\Spec_\rho(1_A)\rangle$. Then $\dim H = \abs\Lambda$. By Corollary \ref{cor:dual-rudin}, if $q \in ]1, 2]$,
  $$(\rho\alpha)^2\abs\Lambda \le \sum_{\gamma \in \Lambda} \abs{\widehat{1_A}(\gamma)}^2 = \norm{\widehat{1_A}}_{\ell^2(\Lambda)}^2 = O\left(\frac q{q - 1}\norm{1_A}_{L^q(\F_2^n)}\right) = O\left(\frac q{q - 1} \alpha^{\frac 2q}\right)$$
  So $\abs\Lambda = O\left(\frac q{q - 1}\rho^{-2}\alpha^{\frac 2q - 2}\right)$. Choose $q = 1 + \log^{-1} \alpha^{-1}$ to get $\abs\Lambda = O(\rho^{-2}\log\alpha^{-1})$.
\end{proof}

We will prove Chang's lemma in greater generality on Example Sheet 3. The key definition for the generalisation is the following.

\begin{dfn}
  Let $G$ be a finite abelian group. We say $S \subseteq G$ is {\bf dissociated} if
  $$\sum_{s \in S} \eps_s s = 0 \implies \eps = 0$$
  for all $\eps \in \{-1, 0, 1\}^S$.
\end{dfn}

Note that if $G = \F_2^n$ then a set $S \subseteq G$ is dissociated iff it's linearly independent.

\newlec

\begin{thm}[Chang's lemma]
  Let $G$  be a finite abelian group and let $A \subseteq G$ be of density $\alpha > 0$. If $\Lambda \subseteq \Spec_\rho(1_A)$ is dissociated, then $\abs\Lambda = O(\rho^{-2}\log\alpha^{-1})$.
\end{thm}
\begin{proof}
  See Example Sheet 3.
\end{proof}

We may bootstrap Khintchine's inequality to get the following.

\begin{thm}[Marcinkiewicz-Zygmund inequality]
  Let $p \in [2, \infty[$ and $X_1, \dots, X_n \in L^p(\P)$ be independent random variables with $\E \sum_i X_i = 0$. Then
  $$\norm{\sum_i X_i}_{L^p(\P)} = O\left(\sqrt p \norm{\sum_i \abs{X_i}^2}_{L^{\frac p2}(\P)}^{\frac 12}\right)$$
\end{thm}
\begin{proof}
  We can derive the complex-valued case from the real-valued case by taking real and imaginary parts and apply the triangle inequality. \\
  Next assume that the distribution of the $X_i$ is symmetric, ie $\P(X_i = a) = \P(X_i = -a)$ for all $a$. Partition the probability space $\Omega$ into sets $\Omega_1, \dots, \Omega_M$, writing $\P_j$ for the induced probability measure on $\Omega_j$. Do it so that all $X_i$ are symmetric and take at most two values on each $\Omega_j$. Applying Khintchine for each $j \in [M]$,
  $$\norm{\sum_i X_i}_{L^p(\P_j)}^p = O\left(p^{\frac p2} \left(\sum_i \norm{X_i}_{L^2(\P_j)}^2\right)^{\frac p2}\right) = O\left(p^{\frac p2} \norm{\sum_i \abs{X_i}^2}_{L^{\frac p2}(\P_j)}^{\frac p2}\right)$$
  with the last inequality being Jensen on $x \mapsto x^{\frac p2}$. Summing over all $j \in [M]$ and taking $p$-th roots gives the symmetric case. \\
  Now suppose the $X_i$ are arbitrary. Let $Y_1, \dots, Y_n$ be such that $X_i \sim Y_i$ and $X_1, \dots, X_n$, $Y_1, \dots, Y_n$ are independent. Applying the symmetric result to $X_i - Y_i$,
  \begin{align*}
    \norm{\sum_i (X_i - Y_i)}_{L^p(\P \times \P)}
    & = O\left(\sqrt p \norm{\sum_i \abs{X_i - Y_i}^2}_{L^{\frac p2}(\P \times \P)}^{\frac 12}\right) \\
    & = O\left(\sqrt p \norm{\sum_i \abs{X_i}^2}_{L^{\frac p2}(\P)}^{\frac 12}\right)
  \end{align*}
  But also
  $$\norm{\sum_i X_i}_{L^p(\P)} = \norm{\sum_i X_i - \E \sum_i Y_i}_{L^p(\P)} \le \norm{\sum_i (X_i - Y_i)}_{L^p(\P \times \P)}$$
  by convexity.
\end{proof}

\begin{thm}[Croot-Sisask Almost Periodicity]
  Let $G$ be a finite abelian group, let $\eps > 0$ and let $p \in [2, \infty[$. Let $A, B \subseteq G$ be such that $\abs{A + B} \le K\abs A$ and let $f : G \to \C$. Then there exist $b \in B$ and a set $X \subseteq B - b$ such that $\abs X \ge (2K)^{-O(\eps^{-2}p)}\abs B$ and
  $$\norm{\tau_x(f \ast \mu_A) - f \ast \mu_A}_{L^p(G)} \le \eps \norm f_{L^p(G)}$$
\end{thm}
\begin{proof}
  The main idea is to approximate
  $$(f \ast \mu_A)(y) = \E_x \mu_A(x) f(y - x) = \E_{x \in A} f(y - x)$$
  by $\frac 1k \sum_{i = 1}^k f(y - z_i)$ with the $z_i$ sampled uniformly at random from $A$ for some $k$ to be chosen. For each $y \in G$, define $Z_i(y) = \tau_{-z_i}(f)(y) - (f \ast \mu_A)(y)$ which are independent with mean zero. So, by Marcinkiewicz-Zygmund,
  $$\norm{\sum_i Z_i(y)}_{L^p(\P)}^p = O\left(p^{\frac p2} \norm{\sum_i \abs{Z_i(y)}^2}_{L^{\frac p2}(\P)}^{\frac p2}\right) = O\left(p^{\frac p2} \E_{z_1, \dots, z_k} \abs{\sum_i \abs{Z_i(y)}^2}^{\frac p2}\right)$$

  \newlec
  
  By Hölder, picking $q$ such that $\frac 2p + \frac 1q = 1$,
  $$\mathrm{RHS} \le \left(\sum_i 1^q\right)^{\frac 1q\frac p2}\left(\sum_i \abs{Z_i(y)}^{2\frac p2}\right)^{\frac 2p\frac p2} = k^{\frac p2 - 1} \sum_i \abs{Z_i(y)}^p$$
  So, for each $y \in G$,
  $$\norm{\sum_i Z_i(y)}_{L^p(\P)}^p = O\left(p^{\frac p2}k^{\frac p2 - 1} \E_{z_1, \dots, z_k} \sum_i \abs{Z_i(y)}^p\right)$$
  Taking expectation over $y \in G$,
  $$\E_y \norm{\sum_i Z_i(y)}_{L^p(\P)}^p = O\left(p^{\frac p2}k^{\frac p2 - 1} \E_{z_1, \dots, z_k} \sum_i \norm{Z_i}_{L^p(G)}^p\right)$$
  Note that
  $$\norm{Z_i}_{L^p(G)} \le \norm{\tau_{-z_i}(f)}_{L^p(G)} + \norm{f \ast \mu_A}_{L^p(G)} \le 2\norm f_{L^p(G)}$$
  by Young's convolution inequality ($\norm{f \ast g}_{L^p} \le \norm f_{L^q}\norm g_{L^r}$ if $1 + \frac 1p = \frac 1q + \frac 1r$). It follows that
  $$\E_{z_1, \dots, z_k} \E_y \abs{\sum_i Z_i(y)}^p = O\left(p^{\frac p2} k^{\frac p2 - 1} \sum_i 2\norm f_{L^p(G)}^p\right) = O\left((pk \norm f_{L^p(G)}^2)^{\frac p2}\right)$$
  Dividing by $k$ on both sides,
  $$\E_{z_1, \dots, z_k} \underbrace{\E_y \abs{\E_i (\tau_{-z_i}(f)(y) - (f \ast \mu_A)(y))}^p}_{(*)} = O\left((pk^{-1} \norm f_{L^p(G)}^2)^{\frac p2}\right)$$
  Choose $k = O(\eps^{-2}p)$ such that the RHS is at most $(\frac\eps 4 \norm f_{L^p(G)})^p$. Write
  $$L = \left\{(z_1, \dots, z_k) \mid (*) \ge \left(\frac\eps 2 \norm f_{L^p(G)}\right)^p\right\}$$
  Observe that $\E (*) \le (\frac\eps 4 \norm f_{L^p(G)})^p = 2^{-p}(\frac\eps 2 \norm f_{L^p(G)})^p$. Hence Markov tells us that
  $$\frac{\abs{L^c}}{\abs A^k} = \P\left((*) \ge \left(\frac\eps 2 \norm f_{L^p(G)}\right)^p\right) \le 2^{-p} \le 1 - 2^{-k}$$
  Hence $\abs L \ge \frac 1{2^k} \abs A^k$. Let $D = \{(b, \dots, b) \mid b \in B\} \subseteq B^k$ the diagonal. Note that $L + D \subseteq (A + B)^k$, whence $\abs{L + D} \le \abs{(A + B)^k} \le K^k\abs A^k \le (2K)^k\abs L$. By Lemma \ref{lem:energy-lower-bound},
  $$\#\{\text{additive quadruples between $L$ and $D$}\} \ge \frac{\abs D^2\abs L}{(2K)^k}$$
  So there are at least $\frac{\abs D^2}{(2K)^k}$ pairs $(d_1, d_2) \in D \times D$ such that $r_{L - L}(d_1 - d_2) > 0$ (rewrite additive quadruples $\ell_1 + d_1 = \ell_2 + d_2$ as $d_1 - d_2 = \ell_2 - \ell_1$ and double-count). In particular, there exists $b \in B$ and $X \subseteq B - b$ of size $\abs X \ge \frac{\abs D}{(2K)^k}$ such that $\for i, \ell_1(x) - \ell_2(x) = x$. We are now done: By the triangle inequality, for each $x \in X$,
  \begin{align*}
    \norm{\tau_{-x}(f \ast \mu_A) - f \ast \mu_A}_{L^p(G)}
    \le & \norm{\tau_{-x}(f \ast \mu_A - \E_i \tau_{-\ell_2(x)}(f))}_{L^p(G)} \\
    & + \norm{\tau_{-x}\E_i \tau_{-\ell_2(x)}(f) - f \ast \mu_A}_{L^p(G)} \\
    \le & \norm{\tau_{-x}(f \ast \mu_A - \E_i \tau_{-\ell_2(x)}(f))}_{L^p(G)} \\
    & + \norm{\E_i \tau_{-\ell_1(x)}(f) - f \ast \mu_A}_{L^p(G)} \\
    \le & \eps \norm f_{L^p(G)} \text{ by definition of }L
  \end{align*}
\end{proof}

\begin{thm}[Polynomial Bogolyubov]\label{thm:polynomial-bogolyubov}
  Let $A \subseteq \F_p^n$ be a set of density $\alpha > 0$. Then there exists a subspace $V \le \F_p^n$ of codimension $O(\log^4\alpha^{-1})$ such that $V \subseteq A + A - (A + A)$.
\end{thm}
\begin{proof}
  See Example Sheet 3.
\end{proof}

\begin{thm}[Schoen, Shkredov]
  Let $p \ne 5$ and let $A \subseteq \F_p^n$ be a set containing no nontrivial solution to $x_1 + x_2 + x_3 + x_4 + x_5 = 5y$. Then $\abs A = \exp(-\Omega(n^{\frac 15}))\abs{\F_p^n}$.
\end{thm}
\begin{proof}
  Let $\alpha$ be the density of $A$. Partition $A$ into $A_1 \union A_2$ where $\abs{A_1} = \floor{\frac\alpha 2 p^n}, \abs{A_2} = \ceil{\frac\alpha 2 p^n}$. By averaging, find $z$ such that $\abs{A_1 \inter (z - A_2)} \ge \frac{\alpha^2}4 p^n$. Let $A' = A_1 \inter (z - A_2)$. By Theorem \ref{thm:polynomial-bogolyubov}, there exists $V \le \F_p^n$ of codimension $O(\log^4\alpha^{-1})$ such that $V \subseteq A' + A' - (A' + A')$. Hence
  $$2z + V \subseteq 2z + A' + A' - (A' + A') \subseteq A_1 + A_1 + A_2 + A_2$$
  Consequently, $(5 \cdot A - A) \inter (2z + V) = \emptyset$. Else there would be $x, y \in A, a_1, a_1' \in A_1, a_2, a_2' \in A_2$ such that $5y - x = a_1 + a_1' + a_2 + a_2'$ which would yield a nontrivial solution since $A_1, A_2$ are disjoint. If follows that for all $w \in \F_p^n$ at most one of $A \inter (w + V)$ and $(5 \cdot A) \inter (w + 2z + V)$ can be nonempty. Therefore
  $$2\abs A = \sum_{w \in V^\perp} \abs{A \inter (w + V)} + \abs{5 \cdot A \inter (w + 2z + V)} \le \abs{V^\perp} \sup_{w \in V^\perp} \abs{A \inter (w + V)}$$
  So there exists $w \in V^\perp$ such that $\abs{A \inter (w + V)} \ge \frac{2\abs A}{\abs{V^\perp}} = 2\alpha V$. The set $A \inter (w + V) \subseteq w + V$ has density at least $2\alpha$ and contains no nontrivial solution. \\
  After $t$ steps, we obtain a subspace $W$ of codimension $O(t\log^4\alpha^{-1})$ and $w$ such that $\abs{A \inter (w + W)} \ge 2^t\alpha \abs W$. Arguing as in the proof of Theorem \ref{thm:meshulam} yields the result.
\end{proof}

We get a similar bound in $\F_n$ where Behrend's construction offers a comparable lower bound.

\newpage

\section{Further topics}

In $\F_p^n$, we can do much better, even for 3APs.

\begin{thm}[Ellenberg-Gijswijt, based on Croot-Lev-Pach]
  Let $A \subseteq \F_3^n$ be a set containing no nontrivial 3AP. Then $\abs A = O(2.765^n)$.
\end{thm}

Let $M_n$ be the set of monomials in $X_1, \dots, X_n$ whose degree in each variable is at most $2$. Let $V_n$ be the $\F_3$-vector space generated by $M_n$. For any $d \in [0, 2n]$, write $M_n^d$ for the set of monomials in $M_n$ of total degree at most $d$, and write $V_n^d$ for the corresponding vector space. Set $m_d = \dim V_n^d = \abs{M_n^d}$.

\begin{lem}\label{lem:polynomial-diagonal}
  Let $A \subseteq \F_3^n$ and suppose $P \in V_n^d$ is such that $P(a + a') = 0$ for all $a, a' \in A$ distinct. Then
  $$\abs{\{a \in A \mid P(2a) \ne 0\}} \le 2m_{\frac d2}$$
\end{lem}
\begin{proof}
  Every $P \in V_n^d$ can be written as a linear combination of monomials from $M_n^d$. So
  $$P(x + y) = \sum_{\substack{m, m' \in M_n^d \\ \deg m + \deg m' \le d}} c_{m, m'} m(x)m'(y)$$
  for some coefficients $c_{m, m'}$. Since at least one of $m, m'$ has degree $\le \frac d2$, we can write
  $$P(x + y) = \sum_{m \in M_n^{\frac d2}} m(x) F_m(y) + \sum_{m' \in M_n^{\frac d2}} m'(y) G_{m'}(x)$$
  where $F_m, G_{m'}$ are polynomials. Viewing $P$ as an $\abs A \times \abs A$-matrix, we see that it can be written as a sum of at most $2m_{\frac d2}$ rank 1 matrices. Hence $\rank P \le 2m_{\frac d2}$. But $P$ is a diagonal matrix by assumption. Hence
  $$\abs{\{a \in A \mid P(2a) \ne 0\}} = \rank P \le 2m_{\frac d2}$$
\end{proof}

\begin{prop}
  Let $A \subseteq \F_3^n$ be a set containing no nontrivial 3AP. Then $\abs A \le 3m_{\frac{2n}3}$.
\end{prop}
\begin{proof}
  Let $d \in [1, 2n]$ be an integer to be chosen later. Let $W$ be the subspace of $V_n^d$ that vanish on $2 \cdot A^c$. Clearly,
  $$\dim W \ge \dim V_n^d - \abs{2 \cdot A^c} = m_d - (3^n - \abs A)$$
  We claim that there is $P \in W$ such that $\abs{\supp P} \ge \dim W$. Indeed, pick $P \in W$ with maximal support. If $\abs{\supp P} < \dim W$, then there is a nonzero $Q \in W$ vanishing on $\supp P$, in which case $P$ and $Q$ have disjoint support and
  $$\supp(P + Q) ) \supp P \union \supp Q \subsetneq \supp P$$
  contradicting the maximality of $P$. \\
  By assumption, $\{a + a' \mid a, a' \in A, a \ne a'\}$ and $2 \cdot A$ are disjoint. So any polynomial vanishing on $2 \cdot A^c$ also vanishes on $\{a + a' \mid a, a' \in A, a \ne a'\}$. By Lemma \ref{lem:polynomial-diagonal},
  $$\abs{\supp P} = \abs{\{x \mid P(x) \ne 0\}} = \abs{\{a \in A \mid P(2a) \ne 0\}} \le 2m_{\frac d2}$$
  Putting everything together,
  $$m_d - (3^n - \abs A) \le \dim W \le \abs{\supp P} \le 2m_{\frac d2}$$
  But monomials in $M_n \setminus M_n^d$ are in bijection with monomials of degree at most $2n - d$ (via $x_1^{\alpha_1} \dots x_n^{\alpha_n} \mapsto x_1^{2 - \alpha_1} \dots x_n^{2 - \alpha_n}$), whence $3^n - m_d = m_{2n - d}$. Thus setting $d = \frac{4n}3$ yields
  $$\abs A \le (3^n - m_d) + 2m_{\frac d2} = m_{2n - d} + 2m_{\frac d2} = 3m_{\frac{2n}3}$$
\end{proof}

We do {\bf not} know of a comparable bound for 4APs. Fourier-analytic techniques also fail.

\begin{eg}
  Recall from Lemma \ref{lem:3AP-estimate} that
  $$\abs{T_3(1_A, 1_A, 1_A) - \alpha^3} \le \sup_{t \ne 0} \abs{\widehat{1_A}(t)}$$
  But it is impossible to bound
  $$\abs{T_4(1_A, 1_A, 1_A, 1_A) - \alpha^4} = \abs{\E_{x, d} 1_A(x) 1_A(x + d) 1_A(x + 2d) 1_A(x + 3d) - \alpha^4}$$
  by $\sup_{t \ne 0} \abs{\widehat{1_A}(t)}$. Indeed, consider $Q = \{x \in \F_p^n \mid x \cdot x = 0\}$. By Question 2.ii on Example Sheet 1, $\frac{\abs Q}{p^n} = \frac 1p + O(p^{-\frac n2})$ and $\sup_{t \ne 0} \abs{\widehat{1_A}(t)} = O(p^{-\frac n2})$. But, given a 3AP $x, x + d, x + 2d \in Q$, we automatically have $x + 3d \in Q$ because of the following identity:
  $$x \cdot x - 3(x + d) \cdot (x + d) + 3(x + 2d) \cdot (x + 2d) - (x + 3d) \cdot (x + 3d)$$
  So $T_4(1_A, 1_A, 1_A, 1_A) = T_3(1_A, 1_A, 1_A) = \alpha^3 + o(1)$ by Lemma \ref{lem:3AP-estimate}.
\end{eg}

\begin{dfn}
  Given $g : G \to \C$ with $G$ finite abelian, define its {\bf $U^2$-norm} by the formula
  $$\norm f_{U^2}^4 = \E_{x, a, b} f(x) \overline{f(x + a) f(x + b)} f(x + a + b)$$
\end{dfn}

Question 3.i on Example Sheet 1 showed that $\norm f_{U^2} = \norm{\hat f}_{\ell^4}$, so this is indeed a norm. Question 3.ii asserted the following.

\begin{lem}\label{lem:t3-le-u2}
  Let $f_1, f_2, f_3 : G \to \C$. Then
  \begin{align*}
    \abs{T_3(f_1, f_2, f_3)} \le
    & \norm{f_1}_{L^2} \norm{f_2}_{U^2} \norm{f_3}_{U^2}, \\
    & \norm{f_1}_{U^2} \norm{f_2}_{L^2} \norm{f_3}_{U^2}, \\
    & \norm{f_1}_{U^2} \norm{f_2}_{U^2} \norm{f_3}_{L^2}
  \end{align*}
  In particular,
  \begin{align*}
    \abs{T_3(f_1, f_2, f_3)} \le
    & \norm{f_1}_{U^2} \norm{f_2}_\infty \norm{f_3}_\infty, \\
    & \norm{f_1}_\infty \norm{f_2}_{U^2} \norm{f_3}_\infty, \\
    & \norm{f_1}_\infty \norm{f_2}_\infty \norm{f_3}_{U^2}
  \end{align*}
\end{lem}

Note that
$$\sup_\gamma \abs{\hat f(\gamma)}^4 \le \sum_\gamma \abs{\hat f(\gamma)}^4 \le \sup_\gamma \abs{\hat f(\gamma)}^2 \sum_\gamma \abs{\hat f(\gamma)}^2$$
Thus, by Parseval,
$$\norm{\hat f}_\infty \le \norm f_{U^2} \le \norm{\hat f}_\infty^{\frac 12} \norm f_{L^2}^{\frac 12}$$
Moreover, if $f = f_A = 1_A - \alpha$, then
$$T_3(f, f, f) = T_3(1_A - \alpha, 1_A - \alpha, 1_A - \alpha) = T_3(1_A, 1_A, 1_A) - \alpha^3$$
We could therefore reformulate the first step in the proof of Meshulam's theorem (Theorem \ref{thm:meshulam}) as follows: \\
If $p^n \ge 2\alpha^{-2}$, then
$$\frac{\alpha^3}2 \le \abs{T_3(1_A, 1_A, 1_A) - \alpha} \le \norm{f_A}_{U^2}$$
by Lemma \ref{lem:t3-le-u2}.

\newlec 

It remains to show that if $\norm{f_A}_{U^2}$ is not too small then there exists a subspace $V \le \F_p^n$ of bounded codimension on which $A$ has increased density.

\begin{thm}[$U^2$ inverse theorem]
  Let $f : \F_p^n \to \C$ satisfy $\norm f_\infty \le 1$ and $\norm f_{U^2} \ge \delta$ for some $\delta > 0$. Then there exists $b$ such that $\abs{\E_x f(x) \omega^{x \cdot b}} \ge \delta^2$. \\
  In other words, $\abs{\inn f\phi} \ge \delta^2$ for $\phi(x) = \omega^{x \cdot b}$ and we say that "$f$ correlates with a linear function".
\end{thm}
\begin{proof}
  We have seen that $\norm f_{U^2}^2 \le \norm{\hat f}_\infty \norm f_2 \le \norm{\hat f}_\infty$. So $\delta^2 \le \norm{\hat f}_\infty = \abs{\E_x f(x) \omega^{x \cdot n}}$ for some $b$.
\end{proof}

\begin{dfn}
  Given $f : G \to \C$ with $G$ finite abelian, define its {\bf $U^3$-norm} by
  \begin{align*}
    \norm f_{U^3}^8
    = & \E_{x, a, b, c} f(x) \overline{f(x + a) f(x + b) f(x + c)} \\
    & f(x + a + b) f(x + a + c) f(x + b + c) \overline{f(x + a + b + c)} \\
    = & \E_{x, h_1, h_2, h_3} \prod_{\eps \in \{0, 1\}^3} \mathrm{conj}^{\abs\eps} f(x + \eps \cdot h)
  \end{align*}
\end{dfn}

It is easy to verify that $\norm f_{U^3}^8 = \E_h \norm{\Delta_h f}_{U^2}^4$ where $\Delta_h f(x) = f(x) \overline{f(x + h)}$.

\begin{dfn}
  Given functions $f_\eps : G \to \C$ for $\eps \in \{0, 1\}^3$, define the {\bf Gowers $U^3$-inner product} by
  $$\langle f\rangle_{U^3} = \E_h \norm{\Delta_h f}_{U^2}^4$$
\end{dfn}

Observe that $\langle f, \dots, f\rangle_{U^3} = \norm f_{U^3}^8$.

\begin{lem}[Gowers-Cauchy-Schwarz]
  Given $f_\eps : G \to \C$ for $\eps \in \{0, 1\}^3$,
  $$\abs{\langle f\rangle_{U^3}} \le \prod_\eps \norm{f_\eps}_{U^3}$$
\end{lem}
\begin{proof}
  See Example Sheet 3.
\end{proof}

Setting $f_\eps = \begin{cases}
  f & \text{ if } \eps_0 = 0 \\
  1 & \text{ if } \eps_0 = 1
\end{cases}$, the LHS equals $\norm f_{U^2}^4$. Hence $\norm f_{U^2} \le \norm f_{U^3}$.

\begin{prop}\label{prop:t4-le-u3}
  Let $f : G \to \C$ with $\norm f_\infty \le 1$. Then
  $$\abs{T_4(f, f, f, f)} \le \norm f_{U^3}$$
\end{prop}
\begin{proof}
  Reparametrising, we have
  \begin{align*}
    T_4(f, f, f, f)
    & = \E_{a, b, c, d}
    \underbrace{f(3a + 2b + c)}_{=: f_1(a, b, c)}
    \underbrace{f(2a + b - d)}_{=: f_2(a, b, d)}
    \underbrace{f(a - c - 2d)}_{=: f_3(a, c, d)}
    \underbrace{f(-b - 2c - 3d)}_{=: f_4(b, c, d)} \\
    & = \E_{a, b, c} f_1(a, b, c) \E_d f_2(a, b, d) f_3(a, c, d) f_4(b, c, d)
  \end{align*}
  So
  \begin{align*}
    \abs{T_4(f, f, f, f)}^2
    & \le \E_{a, b, c} \abs{\E_d f_2(a, b, d) f_3(a, c, d) f_4(b, c, d)}^2 \\
    & = \E_{d, d', a, b} f_2(a, b, d) \overline{f_2(a, b, d')} \E_c f_3(a, c, d) f_4(b, c, d) \overline{f_3(a, c, d') f_4(b, c, d')}
  \end{align*}
  Hence
  \begin{align*}
    \abs{T_4(f, f, f, f)}^4
    \le & \E_{d, d', a, b} \abs{\E_c f_3(a, c, d) f_4(b, c, d) \overline{f_3(a, c, d') f_4(b, c, d')}}^2 \\
    = & \E_{c, c', d, d', a} f_3(a, c, d) \overline{f_3(a, c, d') f_3(a, c', d)} f_3(a, c', d') \\
    & \E_b f_4(b, c, d) \overline{f_4(b, c, d'), f_4(b, c', d)} f_4(b, c', d')
  \end{align*}
  Finally,
  \begin{align*}
    \abs{T_4(f, f, f, f)}^8
    \le & \E_{c, c', d, d', a} \abs{\E_b f_4(b, c, d) \overline{f_4(b, c, d'), f_4(b, c', d)} f_4(b, c', d')}^2 \\
    = & \E_{b, b', c, c', d, d'} f_4(b, c, d) \overline{f_4(b, c, d'), f_4(b, c', d)} f_4(b, c', d') \\
    & \overline{f_4(b', c, d)} f_4(b', c, d'), f_4(b', c', d) \overline{f_4(b', c', d')} \\
    = & \norm f_{U^3}^8
  \end{align*}
\end{proof}

One might hope to generalise Meshulam's theorem (Theorem \ref{thm:meshulam}) as follows.

\begin{thm}[Szemerédi for 4APs]
  Let $A \subseteq \F_p^n$ be a set containing no nontrivial 4APs. Then $\abs A = o(p^n)$.
\end{thm}
\begin{idea}
  By Proposition \ref{prop:t4-le-u3} with $f = f_A = 1_A - \alpha$,
  $$T_4(1_A, 1_A, 1_A, 1_A) - \alpha^4 = T_4(f_A, f_A, f_A, f_A) + \underbrace{\dots + \dots + \dots}_{\text{controlled by } \norm{f_A}_{U^2}} + \underbrace{\dots + \dots + \dots}_{\text{explicit}}$$
  Hence, and since $\norm{f_A}_{U^2} \le \norm{f_A}_{U^3}$,
  $$\abs{T_4(1_A, 1_A, 1_A, 1_A) - \alpha^4} \le 14\norm{f_A}_{U^3}$$
  so if $A$ contains no nontrivial 4AP and $p^n \ge 2\alpha^{-3}$ then $\frac{\alpha^4}2 \le 14\norm{f_A}_{U^3}$.
\end{idea}

What can we say about functions whose $U^3$-norm is large?

\begin{eg}
  Let $M$ be a $n \times n$ matrix with entries in $\F_p$. Then $f(x) = \omega^{x^\perp M x}$ satisfies $\norm f_{U^3} = 1$.
\end{eg}

\begin{thm}[$U^3$ inverse theorem]
  Let $f : \F_p^n \to \C$ satisfying $\norm f_\infty \le 1$ and $\norm f_{U^3} \ge \delta$ for some $\delta > 0$. Then there exists a symmetric matrix $M$ with entries in $\F_p$ and $b \in \F_p^n$ such that
  $$\abs{\E_x f(x) \omega^{x^\perp M x + b^\perp x}} \ge c_p(\delta)$$
  where $c_p$ is a polynomial. \\
  In other words, $\abs{\langle f, \phi\rangle} \ge c_p(\delta)$ for $\phi(x) = \omega^{x^\perp M x + b^\perp x}$ and we say that "$f$ correlates with a quadratic phase function".
\end{thm}
\begin{proof}[Proof sketch]
  Suppose $\norm f_{U^3} \ge \delta$.

  {\bf Step 1: "Weak linearity"} \\
  If $\norm f_{U^3}^8 = \E_h \norm{\Delta_h f}_{U^2}^4 \ge \delta^8$, then for at least a $\frac{\delta^8}2$-proportion of $h \in \F_p^n$ we have $\norm{\Delta_h f}_{U^2}^4 \ge \frac{\delta^8}2$. For each such $f$, there exists $t_h$ such that $\abs{\widehat{\Delta_h}f(t_h)} \ge \frac{\delta^8}2$. Working a tiny bit harder, one can obtain the following.

  \begin{prop}\label{prop:weak-linearity}
    Let $f : \F_p^n \to \C$ satisfy $\norm f_\infty \le 1$ and $\norm f_{U^3} \ge \delta$ for some $\delta > 0$. Suppose that $\abs{\F_p^n} = \Omega_\delta(1)$. Then there exists $S \subseteq \F_p^n$ of density $\Omega_\delta(1)$ and a function $\phi : S \to \F_p^n$ such that
    \begin{enumerate}
      \item $\abs{\widehat{\Delta_h}f(\phi(h))} = \Omega_\delta(1)$
      \item There are at least $\Omega_\delta(\abs{\F_p^n}^2)$ additive quadruples $(s_1, s_2, s_3, s_4) \in S^4$ (namely $s_1 + s_2 = s_3 + s_4$) such that $\phi(s_1) + \phi(s_2) = \phi(s_3) + \phi(s_4)$.
    \end{enumerate}
  \end{prop}

  {\bf Step 2: "Strong linearity"} \\
  If $S$ and $\phi$ are as above, then there is an affine map $\psi : \F_p^n \to \widehat{\F_p^n}$ which coincides with $\phi$ for many elements of $S$. More precisely,
  \begin{prop}
    Let $S$ and $\phi$ be given by Proposition \ref{prop:weak-linearity}. Then there exists a $n \times n$ matrix with entries in $\F_p$ and $b \in \F_p^n$ such that the map $\psi : \F_p^n \to \widehat{\F_p^n}$ satisfies $\psi(x) = \phi(x)$ for $\Omega_\delta(\abs{\F_p^n})$ elements $x$ of $S$
  \end{prop}
  \begin{proof}
    Consider the graph $\Gamma = \{(h, \phi(h)) \mid h \in S\} \subseteq \F_p^n \times \widehat{\F_p^n}$. By Proposition \ref{prop:weak-linearity}, $\Gamma$ has $\Omega_\delta(\abs{\F_p^n})$ additive quadruples. By Balog-Szemerédi-Gowers (Theorem \ref{thm:bsg}), there exists $\Gamma' \subseteq \Gamma$ with $\abs{\Gamma'} = \Omega_\delta(\abs\Gamma) = \Omega_\delta(\abs{\F_p^n})$ and $\abs{\Gamma' + \Gamma'} = O_\delta(\abs{\Gamma'})$. Denote by $\pi : \F_p^n \times \widehat{\F_p^n} \to \F_p^n$ the projection onto the first factor. Define $S' = \pi(\Gamma')$ and note that $\abs{S'} = \abs{\Gamma'} = \Omega_\delta(\abs{\F_p^n})$. By Freiman-Ruzsa (Theorem \ref{thm:freiman-ruzsa}) applied to $\Gamma' \subseteq \F_p^n \times \widehat{\F_p^n}$, there exists a subspace $H \le \F_p^n \times \widehat{\F_p^n}$ with $\abs H = \Omega_\delta(\abs{\Gamma'}) = \Omega_\delta(\abs{\F_p^n})$ such that $\Gamma' \subseteq H$. By construction, $S' \subseteq \pi(H)$. Moreover,
    $$\abs{\ker \pi\restriction_H} = \frac{\abs H}{\abs{\pi(H)}} = \frac{O_\delta(\abs{\F_p^n})}{\abs{S'}} = O_\delta(1)$$
    We may pick $H^*$ a transversal of $\ker \pi\restriction_H$ and partition $H$ into cosets of $H^*$. $\pi$ is injective on each coset. By averaging, there exists $x + H^*$ such that
    $$\abs{\Gamma' \inter (x + H^*)} = \Omega_\delta(\abs{\Gamma'}) = \Omega_\delta(\abs{\F_p^n})$$
    Set $\Gamma'' = \Gamma' \inter (x + H^*)$ and define $S'' = \pi(\Gamma'')$. Now, $\pi\restriction_{x + H^*}$ is a bijection onto its image $V = \im \pi\restriction_{x + H^*}$. Thus we have an affine map $\psi : V \to \widehat{\F_p^n}$ such that $(h, \psi(h)) \in \Gamma''$ for all $h \in S''$.
  \end{proof}
  
  {\bf Step 3: Symmetry argument} \\
  Having obtained $\psi(x) = Mx + b$ for some matrix $M$ and vector $b$ such that $(h, Mh + b) \in \Gamma''$ for all $h \in S''$, we need to turn $M$ into a symmetric matrix in preparation of Step 4.

  {\bf Step 4: "Integrating"}
  \begin{prop}
    Suppose $f, M, b$ are as in Step 3 and $\E_h \abs{\widehat{\Delta_h}f(Mh + b)}^2 = \Omega_\delta(1)$. If $p > 2$, then there exists $b' \in \F_p^n$ such that $\E_x f(x) \omega^{x^T\frac{M + M^T}2 x + b'^T x} = \Omega_\delta(1)$.
  \end{prop}
  \begin{proof}
    See Example Sheet 3.
  \end{proof}
\end{proof}


\end{document}