additive_combinatorics_anki.tex

% To use these notes, you must copy anki_header.tex
% into the header of your card type in Anki

% layout in Anki:
\documentclass[10pt]{article}
\usepackage[a4paper]{geometry}
\geometry{paperwidth=.5\paperwidth,paperheight=100in,left=2em,right=2em,bottom=1em,top=2em}
\pagestyle{empty}
\setlength{\parindent}{0in}

% encoding:
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage{lmodern}

% packages:
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage{amssymb}
\usepackage{centernot}
\usepackage{parskip}

% Theorem-like environments
\theoremstyle{definition}
\newtheorem*{claim}{Claim}
\newtheorem*{conjecture}{Conjecture}

% Command redirections
\let\P\oldP
\let\oldemptyset\emptyset
\let\emptyset\varnothing

% Letter shorthands
\newcommand{\C}{\mathbb C}
\newcommand{\E}{\mathbb E}
\newcommand{\F}{\mathbb F}
\newcommand{\K}{\mathbb K}
\newcommand{\N}{\mathbb N}
\newcommand{\P}{\mathbb P}
\newcommand{\Q}{\mathbb Q}
\newcommand{\R}{\mathbb R}
\newcommand{\Z}{\mathbb Z}
\newcommand{\mcA}{\mathcal A}
\newcommand{\mcB}{\mathcal B}
\newcommand{\mcC}{\mathcal C}
\newcommand{\mcD}{\mathcal D}
\newcommand{\mcE}{\mathcal E}
\newcommand{\mcF}{\mathcal F}
\newcommand{\mcG}{\mathcal G}
\newcommand{\mcH}{\mathcal H}
\newcommand{\mcM}{\mathcal M}
\newcommand{\mcN}{\mathcal N}
\newcommand{\mcO}{\mathcal O}
\newcommand{\mcP}{\mathcal P}
\newcommand{\mcQ}{\mathcal Q}
\newcommand{\mcR}{\mathcal R}
\newcommand{\mcS}{\mathcal S}
\newcommand{\mcT}{\mathcal T}
\newcommand{\mcU}{\mathcal U}
\newcommand{\mcV}{\mathcal V}
\newcommand{\eps}{\varepsilon}
\newcommand{\Eps}{\mathcal E}

\newcommand{\curlybrack}[1]{\left\{ #1\right\}}
\newcommand{\abs}[1]{\left\lvert #1\right\rvert}
\newcommand{\norm}[1]{\left\lVert #1\right\rVert}
\newcommand{\inn}[2]{\left\langle #1, #2\right\rangle}
\newcommand{\floor}[1]{\left\lfloor #1\right\rfloor}
\newcommand{\ceil}[1]{\left\lceil #1\right\rceil}
\newcommand{\doublesqbrack}[1]{[\![#1]\!]}

\newcommand{\imp}{\implies}
\newcommand{\for}{\forall}
\newcommand{\nin}{\notin}
\newcommand{\comp}{\circ}
\newcommand{\union}{\cup}
\newcommand{\inter}{\cap}
\newcommand{\Union}{\bigcup}
\newcommand{\Inter}{\bigcap}
\newcommand{\hatplus}{\mathbin{\widehat{+}}}
\newcommand{\symdif}{\mathbin\varbigtriangleup}
\newcommand{\aeeq}{\overset{\text{ae}}=}
\newcommand{\lexlt}{\overset{\text{lex}}<}
\newcommand{\colexlt}{\overset{\text{colex}}<}
\newcommand{\wto}{\overset w\to}
\newcommand{\wstarto}{\overset{w*}\to}
\renewcommand{\vec}[1]{\boldsymbol{\mathbf{#1}}}
\renewcommand{\bar}[1]{\overline{#1}}

\let\Im\relax
\let\Re\relax

\DeclareMathOperator{\Ber}{Ber}
\DeclareMathOperator{\conv}{conv}
\DeclareMathOperator{\diam}{diam}
\DeclareMathOperator{\codim}{codim}
\DeclareMathOperator{\esssup}{ess sup}
\DeclareMathOperator{\Ext}{Ext}
\DeclareMathOperator{\id}{id}
\DeclareMathOperator{\Im}{Im}
\DeclareMathOperator{\interior}{int}
\DeclareMathOperator{\lhs}{LHS}
\DeclareMathOperator{\rank}{rank}
\DeclareMathOperator{\Re}{Re}
\DeclareMathOperator{\rhs}{RHS}
\DeclareMathOperator{\Span}{Span}
\DeclareMathOperator{\Spec}{Spec}
\DeclareMathOperator{\supp}{supp}
\DeclareMathOperator{\Var}{Var}

%  pdf layout:
\geometry{paperheight=74.25mm}
\usepackage{pgfpages}
\pagestyle{empty}
\pgfpagesuselayout{8 on 1}[a4paper,border shrink=0cm]
\makeatletter
\@tempcnta=1\relax
\loop\ifnum\@tempcnta<9\relax
\pgf@pset{\the\@tempcnta}{bordercode}{\pgfusepath{stroke}}
\advance\@tempcnta by 1\relax
\repeat
\makeatother

%  notes, fields, tags:
\def \ifempty#1{\def\temp{#1} \ifx\temp\empty }
\newcommand{\xfield}[1]{
        #1\par
        \vfill
        {\tiny\texttt{\parbox[t]{\textwidth}{\localtag\hfill\\\globaltag\hfill\uuid}}}
        \newpage}
\newenvironment{field}{}{\newpage}
\newif\ifnote
\newenvironment{note}{\notetrue}{\notefalse}
\newcommand{\localtag}{}
\newcommand{\globaltag}{}
\newcommand{\uuid}{}
\newcommand{\tags}[1]{
    \ifnote
        \renewcommand{\localtag}{#1}
    \else
        \renewcommand{\globaltag}{#1}
    \fi
    }
\newcommand{\xplain}[1]{
  \label{#1} % make sure there's no duplicate label
  \renewcommand{\uuid}{#1} % update the UUID for display and Anki disambiguation
  }

\begin{document}

% Lecture 1

\tags{fourier-analysis}

\begin{note}
  \tags{fourier-transform}
  \xplain{dft-def}
  \xfield{Discrete Fourier transform}
  \begin{field}
    If $f : \F_p^n \to \C$, then
    $$\hat f(t) = \E_{x \in \F_p^n} f(x) \omega^{x \cdot t}$$
    where $\omega = e^{\frac{\tau i}p}$.

    More generally, if $f : G \to \C$, then $\hat f : \hat G \to \C$ is defined by
    $$\hat f(\gamma) = \E_{x \in G} f(x)\gamma(x)$$
  \end{field}
\end{note}

\begin{note}
  \tags{fourier-transform}
  \xplain{dft-inversion}
  \xfield{Inversion formula for the discrete Fourier transform}
  \begin{field}
    $$f(x) = \sum_{t \in \F_p^n} \hat f(t) \omega^{- x \cdot t}$$
    \begin{proof}
      \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*}
    \end{proof}
  \end{field}
\end{note}

\begin{note}
  \xplain{indicator-mu-balance-def}
  \xfield{Ways to turn a set $A \subseteq \F_p^n$ into a function}
  \begin{field}
    \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}$$
      Normalised in the $\infty$ norm.
      \item $\mu_A$ the {\it characteristic measure} of $A$, ie
      $$\mu_A = \alpha^{-1} 1_A$$
      where $\alpha = \frac{\abs A}{\abs G}$. Normalised in the $L^1$ norm.
      \item $f_A$ the {\it balanced function} of $A$, ie
      $$f_A(x) = 1_A(x) - \alpha$$
      Normalised to have sum $0$.
    \end{itemize}
  \end{field}
\end{note}

\begin{note}
  \tags{fourier-transform}
  \xplain{dft-neg}
  \xfield{Fourier transform of $-A$}
  \begin{field}
    $$\widehat{1_{-A}} = \overline{1_A}$$
    \begin{proof}
      \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*}
    \end{proof}
  \end{field}
\end{note}

\begin{note}
  \tags{fourier-transform}
  \xplain{dft-subspace}
  \xfield{Fourier transform of a subspace}
  \begin{field}
    If $V \le \F_p^n$, then
    $$\widehat{\mu_V}(t) = 1_{V^\perp}(t)$$
    \begin{proof}
      $$\widehat{1_V}(t) = \E_x 1_V(x) \omega^{x \cdot t} = \frac{\abs V}{\abs G} 1_{V^\perp}(t)$$
    \end{proof}
  \end{field}
\end{note}

\begin{note}
  \tags{fourier-transform}
  \xplain{dft-random-set}
  \xfield{Fourier transform of a random set}
  \begin{field}
    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)$$
    \begin{proof}
      Chernoff
    \end{proof}
  \end{field}
\end{note}

\begin{note}
  \xplain{discrete-lp-norm-def}
  \xfield{Inner product, $L^p$ norm}
  \begin{field}
    If $f, g : \F_p^n \to \C$, then
    \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)} \\
      \norm f_p^p & = \E_x \abs{f(x)}^p \\
      \norm{\hat f}_p^p & = \sum_t \abs{\hat f(t)}^p
  \end{align*}
  \end{field}
\end{note}

\begin{note}
  \tags{fourier-transform}
  \xplain{discrete-plancherel-parseval}
  \xfield{Plancherel and Parseval's identities}
  \begin{field}
    \begin{align*}
      \inn f g & = \inn{\hat f}{\hat g} & \text{ (Plancherel)} \\
      \norm f_2 & = \norm{\hat f}_2 & \text{ (Parseval)}
    \end{align*}
    \begin{proof}
      \begin{align*}
        \inn{\hat f}{\hat g}
        & = \sum_t \hat f(t) \overline{\hat g(t)} = \sum_{t, x, y} f(x) \overline{g(y)} \omega^{(x - y) \cdot t} \\
        & = \sum_{x, y} f(x) \overline{g(y)} 1_{x = y} = \inn f g
      \end{align*}
    \end{proof}
  \end{field}
\end{note}

\begin{note}
  \tags{large-spectrum}
  \xplain{large-spectrum-def}
  \xfield{Large spectrum}
  \begin{field}
    The $\rho$-large spectrum of $f$ is
    $$\Spec_\rho(f) = \{t \mid |\hat f(t)| \ge \rho\norm f_1\}$$
  \end{field}
\end{note}

\begin{note}
  \tags{large-spectrum}
  \xplain{large-spectrum-subspace}
  \xfield{Large spectrum of a subspace}
  \begin{field}
    If $V \le \F_p^n$ and $\rho > 0$, then
    $$\Spec_\rho(1_V) = V^\perp$$
  \end{field}
\end{note}

\begin{note}
  \tags{large-spectrum}
  \xplain{card-large-spectrum-le}
  \xfield{Upper bound on the size of the large spectrum}
  \begin{field}
    For all $\rho > 0$,
    $$\abs{\Spec_\rho(f)} \le \rho^{-2} \frac{\norm f_2^2}{\norm f_1^2}$$
    \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}
  \end{field}
\end{note}

% Lecture 2

\begin{note}
  \tags{convolution}
  \xplain{convolution-def}
  \xfield{Convolution of functions}
  \begin{field}
    Given $f, g : \F_p^n \to \C$, their convolution $f \ast g : \F_p^n \to \C$ is given by
    $$(f \ast g)(x) = \E_y f(y)g(x - y)$$
  \end{field}
\end{note}

\begin{note}
  \tags{convolution}
  \xplain{convolution-indicators}
  \xfield{Meaning of $1_A \ast 1_B$}
  \begin{field}
    \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{field}
\end{note}

\begin{note}
  \tags{convolution fourier-transform}
  \xplain{dft-convolution}
  \xfield{Relationship between convolution and Fourier transform}
  \begin{field}
    Given $f, g : \F_p^n \to \C$,
    $$\widehat{f \ast g}(t) = \hat f(t) \hat g(t)$$
    \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}
  \end{field}
\end{note}

\begin{note}
  \tags{fourier-transform}
  \xplain{l4-norm-fourier-transform}
  \xfield{Meaning of the $L^4$ norm of the Fourier transform}
  \begin{field}
    $$\norm{\hat f}_4^4 = \E_{x + y = z + w} f(x)f(y)\overline{f(z)f(w)}$$
    \begin{proof}
      \begin{align*}
        \norm{\hat f}_4^4
        & = \norm{\hat f^2}_2^2 = \norm{\widehat{f \ast f}}_2^2 = \norm{f \ast f}_2^2 \\
        & = \E_a (f \ast f)(a)\overline{(f \ast f)(a)} \\
        & = \E_{a, x, y, z, w} f(x)f(y)1_{x + y = a}\overline{f(z)f(w)1_{z + w = a}} \\
        & = \E_{x + y = z + w} f(x)f(y)\overline{f(z)f(w)}
      \end{align*}
    \end{proof}
  \end{field}
\end{note}

\begin{note}
  \tags{finite-field-model}
  \xplain{bogolyubov-ff}
  \xfield{Bogolyubov's lemma in $\F_p^n$}
  \begin{field}
    If $A \subseteq \F_p^n$ has density $\alpha > 0$, then there exists a subspace $V$ of codimension at most $2\alpha^{-2}$ such that $V \subseteq (A + A) - (A + A)$.
    \begin{proof}
      Write $(A + A) - (A + A) = \supp (\underbrace{1_A \ast 1_A \ast 1_{-A} \ast 1_{-A}}_g)$, set $K = \Spec_\rho(1_A)$ for $\rho = \sqrt{\frac\alpha 2} > 0$ and define $V = \langle K\rangle^\perp$. We have $\codim V \le \abs K \le \rho^{-2}\alpha^{-1} = 2\alpha^{-2}$ and
      $$g(x) = \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)}$$
      Now prove $(1) \ge 0$ and $\abs{(2)} \le \rho^2\alpha^3 = \frac{\alpha^4}2$ so that $g(x) > 0$ whenever $x \in V$.
    \end{proof}
  \end{field}
\end{note}

\begin{note}
  \xplain{sumset-no-subspace, finite-field-model}
  \xfield{Example of a set $A \subseteq \F_2^n$ of fixed density such that $A + A$ does not contain any subspace of bounded codimension}
  \begin{field}
    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$.
  \end{field}
\end{note}

\begin{note}
  \tags{large-spectrum finite-field-model}
  \xplain{density-increment-ff}
  \xfield{Density increment in $\F_p^n$}
  \begin{field}
    Let $A \subseteq \F_p^n$ of density $\alpha$. If $t \ne 0$ is in $\Spec_\rho(1_A)$, then there exists $x$ such that
    $$\abs{A \inter (x + V)} \ge \alpha\left(1 + \frac\rho 2\right)\abs V$$
    where $V = \langle t\rangle^\perp$.
    \begin{proof}
      For $j = 1, \dots, p$, write $v_j + V$ the cosets of $V$, $a_j = \frac{\abs{A \inter (v_j + V)}}{\abs V} - \alpha$ the density increment within each $V_j$. Calculate $\sum_j a_j = 0$ and $\widehat{1_A}(t) = \E_j a_j \omega^j$, so that
      $$\rho\alpha \le \abs{\widehat{1_A}(t)} \le \E_j \abs{a_j} = \E_j (\abs{a_j} + a_j)$$
      and find $j$ such that $\abs{a_j} + a_j \ge \rho\alpha$. Take $x = v_j$.
    \end{proof}
  \end{field}
\end{note}

% Lecture 3

\begin{note}
  \tags{convolution}
  \xplain{t3-def}
  \xfield{Definition of $T_3$}
  \begin{field}
    If $f, g, h : \F_p^n \to \C$, then
    $$T_3(f, g, h) = \E_x f(x) g(x + d) h(x + 2d) = \inn{f \ast h}{\bar g (2^{-1} \cdot)}$$
  \end{field}
\end{note}

\begin{note}
  \tags{3AP finite-field-model}
  \xplain{3AP-uniform}
  \xfield{Number of 3APs in a uniform set $A \subseteq \F_p^n$}
  \begin{field}
    If $\sup_{t \ne 0} \abs{\widehat{1_A}(t)} = o(1)$, then $A$ contains $(\alpha^3 + o(1))\abs G^2$ 3APs.
    \begin{proof}
      The number of 3APs in $A$ is $\abs G^2$ times
      \begin{align*}
        T_3(1_A, 1_A, 1_A)
        & = \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}
  \end{field}
\end{note}

\begin{note}
  \tags{3AP}
  \xplain{meshulam, finite-field-model}
  \xfield{Meshulam's theorem}
  \begin{field}
    IF $p \ge 3$ and $A \subseteq \F_p^n$ only contains trivial 3APs, then the density of $A$ is $O(n^{-1})$.
    \begin{proof}
      By assumption, $T_3(1_A, 1_A, 1_A) = \frac\alpha{p^n}$. But
      $$\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$, we find 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$$
      Iteratively increase $\alpha$ like this until $2\alpha^{-2} \le p^n$. Since $\alpha \le 1$, this takes at most $9\alpha^{-1}$ steps. So $p^{n - 9\alpha^{-1}}\le 2\alpha^{-2}$ which implies $\alpha \le \frac{18}n$, as wanted.
    \end{proof}
  \end{field}
\end{note}

% Lecture 4

\begin{note}
  \tags{character}
  \xplain{character-def}
  \xfield{Characters, dual group}
  \begin{field}
    Characters of the group $G$ are group homomorphisms $\gamma : G \to \C^\times$. They form a group called the Pontryagin dual or dual group of $G$.
  \end{field}
\end{note}

\begin{note}
  \tags{character}
  \xplain{dual-ff}
  \xfield{Duals of $\F_p^n, \Z/n\Z$}
  \begin{field}
    \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}
  \end{field}
\end{note}

\begin{note}
  \tags{fourier-transform integer-model}
  \xplain{dft-interval}
  \xfield{Fourier transform of an interval in $\Z/p\Z$}
  \begin{field}
    Write $J = [-\frac L2, \frac L2] \subseteq \Z/p\Z$ with $L < p$ even. For all $t$,
    $$\widehat{1_J}(t) \le \min\left(\frac{L + 1}p, \frac 1{2\abs t}\right)$$
    \begin{proof}
      If $t = 0$, then $\widehat{1_J}(t) = \frac{\abs J}p = \frac{L + 1}p$. If $t \ne 0$, then
      $$\widehat{1_J}(t) = \E_x 1_J(x)\omega^{xt} = \E_{x = -\frac L2}^{\frac L2} \omega^{xt} = \frac{\omega^{(L + 1)\frac t2} - \omega^{-(L + 1)\frac t2}}{p(\omega^{\frac t2} - \omega^{-\frac t2})}$$
      Noting that for all $x \in [-\pi, \pi]$ we have $\abs{e^{ix} - 1} \ge \frac{2\abs x}\pi$,
      $$\abs{\widehat{1_J}(t)} \le \frac 2p \abs{\omega^t - 1}^{-1} \le \frac 2p\left(\frac 2\pi\frac{2\pi t}p\right)^{-1} = \frac 1{2\abs t}$$
    \end{proof}
  \end{field}
\end{note}

\begin{note}
  \tags{3AP integer-model}
  \xplain{large-fourier-coeff-int}
  \xfield{Density increment or large Fourier coefficient for 3APs in an interval}
  \begin{field}
    Let $A \subseteq [N]$ be of density $\alpha > 0$ with $N > 50\alpha^{-2}$ and containing only trivial 3APs. Let $p$ be a prime in $[\frac N3, \frac{2N}3]$ and write $A' = A \inter [p] \subseteq \Z/p\Z$. Then either
    \begin{enumerate}
      \item $\sup_{t \ne 0} \abs{\widehat{1_A}(t)} \ge \frac{\alpha^2}{10}$
      \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}
    \begin{proof}
      There's no non-trivial 3AP with terms in $A', A'', A''$ where $A''$ is the middle third of $A'$. If $A'$ and $A''$ are both dense enough, then we're in Case 1 by computing $T_3(1_{A'}, 1_{A''}, 1_{A''})$. Else we're in Case 2 by looking at the appropriate complement.
    \end{proof}
  \end{field}
\end{note}

% Lecture 5

\begin{note}
  \tags{integer-model}
  \xplain{partition-progressions-small-diam}
  \xfield{For $t \ne 0, \eps > 0$ and $\phi : [m] \to \Z/p\Z$ multiplication by $t$, how to partition $[m]$ into progressions of length roughly $\eps\sqrt m$ such that $\diam(\phi(P_i)) \le \eps p$?}
  \begin{field}
    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{field}
\end{note}

\begin{note}
  \tags{3AP integer-model}
  \xplain{density-increment-int}
  \xfield{Density increment from a large Fourier coefficient for 3APs in an interval}
  \begin{field}
    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$$
    \begin{proof}
      Let $\eps = \frac{\alpha^2}{40\pi}$ and partition $[p]$ into progressions $P_i$ of length at least $\frac{\eps \sqrt p}2 \ge \frac{\alpha^2\sqrt N}{500}$ and $\diam \phi(P_i) \le \eps p$. Fix one $x_i$ inside each $P_i$. Write $\abs{\widehat{f_{A'}}(t)} = \frac 1p\abs{\sum_i\sum_{x \in P_i} f_{A'}(x)\omega^{xt}}$ and use the fact that $\omega^{xt} \approx \omega^{x_it}$ whenever $x \in P_i$ to find some $i$ such that $\sum_{x \in P_i} f_{A'}(x) \ge \frac{\alpha^2\abs{P_i}}{40}$.
    \end{proof}
  \end{field}
\end{note}

\begin{note}
  \tags{3AP integer-model}
  \xplain{roth}
  \xfield{Roth's theorem}
  \begin{field}
    Let $A \subseteq [N]$ be a set containing only trivial 3APs. Then $\abs A = O(\frac N{\log\log N})$.
    \begin{proof}
      Iterate the density increment.
    \end{proof}
  \end{field}
\end{note}

\begin{note}
  \tags{3AP integer-model}
  \xplain{behrend}
  \xfield{Behrend's construction}
  \begin{field}
    There exists a set $A \subseteq [N]$ containing non nontrivial 3APs of size at least $e^{-O(\sqrt{\log N})}$. See Example Sheet 1.
    \begin{proof}
      $[m]^d$ contains $m^d$ points which all lie on some sphere of radius squared $\le md^2$. Hence one of the spheres contains at least $\frac{m^{d - 2}}d$ integer points. Send those to $\Z$ via the map
      \begin{align*}
        [m]^d & \to [(2m)^d] \\
        x & \mapsto \sum_i (2m - 1)^i x_i
      \end{align*}
      Density is at least $\frac 1{2^d m^2 d}$, which we optimise by taking $d = \sqrt{\log N}$.
    \end{proof}
  \end{field}
\end{note}

\begin{note}
  \tags{bohr-set}
  \xplain{bohr-set-def}
  \xfield{Bohr set}
  \begin{field}
    Let $\Gamma \subseteq \hat G$. The Bohr set of 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 rank of the Bohr set.
  \end{field}
\end{note}

\begin{note}
  \tags{bohr-set finite-field-model}
  \xplain{bohr-set-ff}
  \xfield{Bohr set in $\F_p^n$}
  \begin{field}
    When $G = \F_p^n$, $B(\Gamma, \rho) = \langle\Gamma\rangle^\perp$ for all small enough $\rho$ (depending only on $p$, not $n$).
  \end{field}
\end{note}

\begin{note}
  \tags{bohr-set}
  \xplain{bohr-set-card-ge}
  \xfield{Lower bound on the size of a Bohr set}
  \begin{field}
    If $B$ is a Bohr set of rank $d$ and width $\rho$, then $\abs B \ge \left(\frac\rho{2\pi}\right)^d \abs G$.
  \end{field}
\end{note}

% Lecture 6

\begin{note}
  \tags{bohr-set}
  \xplain{bogolyubov-int}
  \xfield{Bogolyubov's lemma in $\Z/p\Z$}
  \begin{field}
    If $A \subseteq \Z/p\Z$ has density $\alpha > 0$, then there exists $\Gamma \subseteq \widehat{\Z/p\Z}$ of size at most $2\alpha^{-2}$ such that $B(\Gamma, \frac 12) \subseteq (A + A) - (A + A)$.
    \begin{proof}
      Pick $\Gamma = \Spec_{\sqrt{\frac\alpha 2}}(1_A)$ and lower bound
      $$\Re (1_A \ast 1_A \ast 1_{-A} \ast 1_{-A})(x) = \Re \sum_{t \in \widehat{\F_p}} \abs{\widehat{1_A}(t)}^4 \omega^{-xt}$$
      by splitting the sum over $\Gamma$ and $\Gamma^c$.
    \end{proof}
  \end{field}
\end{note}

\begin{note}
  \xplain{balanced-function-fourier-analysis-relevance}
  \xfield{Why is the balanced function important in Fourier-analytic arguments?}
  \begin{field}
    Passing from a function to its balanced function kills the $0$-th Fourier coefficient, which otherwise has to be special-cased everywhere.
  \end{field}
\end{note}

\tags{combinatorial-methods}

\begin{note}
  \tags{doubling-constant}
  \xplain{doubling-constant-def}
  \xfield{Doubling constant, difference constant}
  \begin{field}
    For a finite nonempty set $A \subseteq G$, its doubling and difference constants are
    $$\sigma(A) = \frac{\abs{A + A}}{\abs A}, \delta(A) = \frac{\abs{A - A}}{\abs A}$$
  \end{field}
\end{note}

\begin{note}
  \tags{doubling-constant}
  \xplain{doubling-constant-one}
  \xfield{When is the doubling constant $1$?}
  \begin{field}
    When the set is a subspace
  \end{field}
\end{note}

\begin{note}
  \tags{doubling-constant}
  \xplain{doubling-constant-lt-three-halves}
  \xfield{If $A$ has very small doubling constant then $A$ lies in a small coset.}
  \begin{field}
    If $A$ is 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$.
  \end{field}
\end{note}

\begin{note}
  \tags{doubling-constant}
  \xplain{big-doubling-random}
  \xfield{Example of a set with big doubling}
  \begin{field}
    Let $A \subseteq \F_p^n$ be a set where each point is taken randomly with probability $p^{-\theta n}$ where $\theta \in ]\frac 12, 1]$. Then with high probability $\abs{A + A} = (1 + o(1))\frac{\abs A^2}2$.
  \end{field}
\end{note}

\begin{note}
  \tags{ruzsa-distance}
  \xplain{ruzsa-distance-def}
  \xfield{Ruzsa distance}
  \begin{field}
    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{field}
\end{note}

\begin{note}
  \tags{ruzsa-distance}
  \xplain{ruzsa-triangle-inequality}
  \xfield{Ruzsa's triangle inequality}
  \begin{field}
    For $A, B, C \subseteq G$ finite,
    $$d(A, C) \le d(A, B) + d(B, C)$$
    \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 - c$.
    \end{proof}
  \end{field}
\end{note}

\begin{note}
  \tags{doubling-constant}
  \xplain{pluennecke-inequality}
  \xfield{Plünnecke's inequality}
  \begin{field}
    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 B$$
  \begin{proof}
    WLOG $\abs{A + B} = K\abs A$. Find $A' \subseteq A$ nonempty minimising $K' = \frac{\abs{A' + B}}{\abs{A'}}$.
    \begin{claim}
      For all finite $C \subseteq G$, $\abs{A' + B + C} \le K'\abs{A' + C}$
    \end{claim}
    From the claim, prove that $\abs{A' + mB} \le K'^m\abs{A'}$ for all $m$ by induction. 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$.
  \end{proof}
  \end{field}
\end{note}

\begin{note}
  \xplain{pluennecke-inequality-claim}
  \xfield{Key claim within the proof of Plünnecke's inequality}
  \begin{field}
    WLOG $\abs{A + B} = K\abs A$. $A' \subseteq A$ is nonempty minimising $K' = \frac{\abs{A' + B}}{\abs{A'}}$.
    \begin{claim}
      For all finite $C \subseteq G$, $\abs{A' + B + C} \le K'\abs{A' + C}$
    \end{claim}
    \begin{proof}[Proof of claim]
      Induct on $C$. obvious if $C = \emptyset$. For $C' = C \union \{x\}, x \notin C$, write
      \begin{align*}
        A' + B + C' & = A' + B + C \union A' + B + x \setminus D + B + x \\
        A' + C' & = A' + C \union A' + x \setminus E + x
      \end{align*}
      where $D = \{a \in A' \mid a + B + x \subseteq A' + B + C\}, E = \{a \in A' \mid a + x \in A' + C\} \subseteq D$. Note that the second union is disjoint. Use the induction hypothesis and the minimality assumption for $K'$ to deduce the claim.
    \end{proof}
  \end{field}
\end{note}

\begin{note}
  \tags{doubling-constant}
  \xplain{doubling-difference-constants-relation}
  \xfield{Relationship between the doubling and difference constant}
  \begin{field}
    If $\abs{A - A} \le K\abs A$, then
    $$\abs A\abs{A + A} \le \abs{A - A}\abs{A - A} \le K^2\abs A^2$$
    by Ruzsa's triangle inequality. So $\sigma(A) \le \delta(A)^2$.
    
    If $\abs{A + A} \le K\abs A$, then
    $$\abs{A - A} \le K^{1 + 1}\abs A$$
    by Plünnecke's inequality. So $\delta(A) \le \sigma(A)^2$.
  \end{field}
\end{note}

\begin{note}
  \xplain{freiman-ruzsa}
  \xfield{The Freiman-Ruzsa theorem}
  \begin{field}
    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$.
    \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. Use that $X + A \subseteq 2A + S$ to prove $\abs X \le K^4$ by Plünnecke. Now $A + S \subseteq X + S$ because $y \in A + S$ is either in $X \subseteq X + S$ or $x + A$ and $y + A$ are not disjoint by maximality of $X$, namely $y \in x + A - A \subseteq X + S$. By induction, $\ell A + S \subseteq X + S$ for all $\ell$. Hence, the subgroup generated by $A$ is contained in $\langle X\rangle + S$ and size at most
      $$\abs{\langle X\rangle}\abs S \le p^{\abs X}K^2\abs A \le K^2p^{K^4}\abs A$$
    \end{proof}
  \end{field}
\end{note}

\begin{note}
  \tags{doubling-constant}
  \xplain{subgroup-exponential-size-doubling-constant}
  \xfield{Example of a set which generates a subgroup of size exponential in its doubling constant}
  \begin{field}
    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{field}
\end{note}

\begin{note}
  \xplain{polynomial-freiman-ruzsa}
  \xfield{Polynomial Freiman-Ruzsa conjecture}
  \begin{field}
    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{field}
\end{note}

\begin{note}
  \tags{additive-energy}
  \xplain{additive-energy-def}
  \xfield{Additive energy}
  \begin{field}
    Given an abelian group $G$ and finite sets $A, B \subseteq G$, define additive quadruples to be the tuples $(a, a', b, b') \in A^2 \times B^2$ such that $a + b = a' + b'$ and the additive energy between $A$ and $B$ to be
    $$E(A, B) = \frac{\#\{\text{additive quadruples}\}}{\abs A^{\frac 32}\abs B^{\frac 32}}$$
  \end{field}
\end{note}

\begin{note}
  \tags{additive-energy fourier-transform}
  \xplain{additive-energy-fourier-transform}
  \xfield{Relation between the additive energy and the Fourier transform}
  \begin{field}
    If $G$ is finite and $A \subseteq G$, 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*}
    namely
    $$\norm{\widehat{1_A}}_4^4 = \alpha^3 E(A)$$
  \end{field}
\end{note}

\begin{note}
  \tags{additive-energy}
  \xplain{additive-energy-subgroup}
  \xfield{Additive energy of a subgroup}
  \begin{field}
    When $H \le G$, we have $E(H) = 1$.
  \end{field}
\end{note}

\begin{note}
  \tags{doubling-constant additive-energy}
  \xplain{small-doubling-constant-implies-big-additive-energy}
  \xfield{Small doubling implies big energy}
  \begin{field}
    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}}$. In particular, if $\abs{A \pm A} \le K\abs A$ then $E(A) \ge \frac 1K$.
    \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$$
      Also note that $\sum_x r(x) = \abs A\abs B$ so that
      \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} = \frac{(\abs A\abs B)^2}{\abs{A + B}}
      \end{align*}
      by Cauchy-Schwarz. Do similarly for $A - B$.
    \end{proof}
  \end{field}
\end{note}

\begin{note}
  \tags{doubling-constant additive-energy}
  \xplain{big-additive-energy-not-implies-small-doubling-constant}
  \xfield{Big energy does not imply small doubling}
  \begin{field}
    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$.
  \end{field}
\end{note}

\begin{note}
  \tags{additive-energy}
  \xplain{balog-szemeredi-gowers}
  \xfield{Balog-Szemerédi-Gowers}
  \begin{field}
    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)$ such that $\abs{A' + A'} \le C(\eta)\abs A$ where $c(\eta)$ and $C(\eta)$ are polynomials in $\eta$.
  \end{field}
\end{note}

\begin{note}
  \xplain{balog-szemeredi-gowers-dependent-random-choice}
  \xfield{Dependent random choice step within the proof of Balog-Szemerédi-Gowers}
  \begin{field}
    Let $A_1, \dots, A_m \subseteq [n]$ and suppose that $\E_{i, j} \abs{A_i \inter A_j} \ge \delta^2n$. 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$.
    \begin{proof}
      Let $x_1, \dots, x_5$ be uniform random in $[n]$ and let $X = \{i \in [m] \mid \forall k, x_k \in A_i\}$. Call a pair {\bf bad} if $\abs{A_i \inter A_j} < \frac{\delta^2n}2$. Prove that
      $$\frac{\delta^{10}m^2}2 + 16\E[\#\{\text{bad pairs in }X^2\}] \le \E[\abs X^2]$$
      so that $\frac{\delta^{10}m^2}2 + 16\#\{\text{bad pairs in }X^2\} \le \abs X^2$ for some $x_1, \dots, x_5$. This gives $\abs X \ge \frac{\delta^5m}{\sqrt 2}$ and $\#\{\text{bad pairs in }X^2\} \le \frac{\abs X^2}{16} \le 10\% \abs X^2$
    \end{proof}
  \end{field}
\end{note}

\end{document}