# An inverse theorem for the Gowers $U^{3}(G)$ norm

Ben Green  Department of Mathematics, University of Bristol, University Walk,
Bristol BS8 1TW, England<EMAIL_ADDRESS>and  Terence Tao  Department
of Mathematics, UCLA, Los Angeles CA 90095-1555, USA<EMAIL_ADDRESS>
###### Abstract.

There has been much recent progress in the study of arithmetic progressions in
various sets, such as dense subsets of the integers or of the primes. One key
tool in these developments has been the sequence of _Gowers uniformity norms_
$U^{d}(G)$, $d=1,2,3,\ldots$ on a finite additive group $G$; in particular, to
detect arithmetic progressions of length $k$ in $G$ it is important to know
under what circumstances the $U^{k-1}(G)$ norm can be large.

The $U^{1}(G)$ norm is trivial, and the $U^{2}(G)$ norm can be easily
described in terms of the Fourier transform. In this paper we systematically
study the $U^{3}(G)$ norm, defined for any function $f:G\to\mathbb{C}$ on a
finite additive group $G$ by the formula

$\displaystyle\|f\|_{U^{3}(G)}$ $\displaystyle:=$
$\displaystyle|G|^{-4}\sum_{x,a,b,c\in
G}(f(x)\overline{f(x+a)f(x+b)f(x+c)}f(x+a+b)\times$
$\displaystyle\qquad\qquad\qquad\qquad\times
f(x+b+c)f(x+c+a)\overline{f(x+a+b+c)})^{1/8}.$

We give an inverse theorem for the $U^{3}(G)$ norm on a arbitrary group $G$.
In the finite field case $G=\mathbb{F}_{5}^{n}$ we show that a bounded
function $f:G\to\mathbb{C}$ has large $U^{3}(G)$ norm if and only if it has a
large inner product with a function $e(\phi)$, where $e(x):=e^{2\pi ix}$ and
$\phi:\mathbb{F}_{5}^{n}\to\mathbb{R}/\mathbb{Z}$ is a quadratic phase
function. In a general $G$ the statement is more complicated – the phase
$\phi$ is quadratic only locally on a Bohr neighbourhood in $G$.

As an application we extend Gowers proof [25] of Szemerédi’s theorem for
progressions of length 4 to arbitrary abelian $G$. More precisely, writing
$r_{4}(G)$ for the size of the largest $A\subseteq G$ which does not contain a
progression of length four, we prove that

$r_{4}(G)\ll|G|(\log\log|G|)^{-c},$

where $c$ is an absolute constant.

We also discuss links between our ideas and recent results of Host-Kra and
Ziegler in ergodic theory.

In future papers we will apply variants of our inverse theorems to obtain an
asymptotic for the number of quadruples $p_{1}<p_{2}<p_{3}<p_{4}\leqslant N$
of primes in arithmetic progression, and to obtain significantly stronger
bounds for $r_{4}(G)$.

The second author is supported by a grant from the Packard Foundation.

##  1\. Background and Motivation

A famous and deep theorem of Szemerédi asserts that any set of integers of
positive upper density contains arbitrarily long arithmetic progressions. More
precisely:

######  Theorem 1.1 (Szemerédi’s theorem, infinitary version).

[59] Let $A$ be a subset of the integers $\mathbb{Z}$ whose upper density
$\limsup_{N\to\infty}(2N+1)^{-1}|A\cap[-N,N]|$ is strictly positive. Then for
any $k\geqslant 1$, the set $A$ contains infinitely many arithmetic
progressions $\\{a,a+r,\ldots,a+(k-1)r\\}$, $r\neq 0$, of length $k$.

The first non-trivial case of this theorem is when $k=3$, which was treated by
Roth [54] using a Fourier-analytic argument. The case of higher $k$ was more
resistant to Fourier-analytic methods, and the first full proof of this
theorem was achieved by Szemerédi [59] using combinatorial methods. Later,
Furstenberg [18, 23] introduced an ergodic theoretic proof of this theorem.
More recently, Gowers [27] gave a proof which was both combinatorial and
Fourier-analytic in nature, and which is substantially closer in spirit to
Roth’s original argument than the other proofs. Even more recently there have
been a number of other proofs of this theorem by other methods, such as
hypergraph regularity [28, 47, 48, 51, 52, 53] or “discrete ergodic theory”
[61]. This theorem and its various proofs have in turn generated many other
mathematical developments. For instance, in [34], we were able to apply
Theorem 1.1 to demonstrate that the primes contain arbitrarily long arithmetic
progressions.

In this paper we shall be interested primarily in the Fourier-analytic
approach to this theorem, specifically in the $k=4$ case, which was treated
separately by Gowers in [25] and then again in [27]. This latter paper will be
our key reference. However as we shall see later there are some strong
connections between this approach and the ergodic one, especially after the
work on characteristic factors by Host and Kra [39, 41] and Ziegler [62, 63],
and on the connection to nilsequences by Bergelson, Host, and Kra [3]. Before
we give our main new results, however, we first give some further historical
background and motivation.

Gowers’ proof of the full Szemerédi theorem in [27] is quite lengthy and
involves many deep new ideas. However, it is possible to split it up into a
number of simpler steps, all but one of which are straightforward. Firstly, it
is easy to show that for any fixed $k$, Theorem 1.1 is equivalent to the
following finitary version.

######  Theorem 1.2 (Szemerédi’s theorem, finitary version [59]).

Let $\delta>0$ and $k\geqslant 1$. Then there exists an integer
$N_{0}=N_{0}(\delta,k)$ such that whenever $N\geqslant N_{0}$ and
$A\subseteq[1,N]$ is such that $|A|/|[1,N]|\geqslant\delta$, then $A$ contains
at least one proper arithmetic progression of length $k$.

The next observation, due to Roth, is that one can hope to prove this theorem
by downwardly inducting on the density parameter $\delta$ (the case
$\delta\geqslant 1$ being trivial or vacuous). In particular, for any fixed
$k$, Theorem 1.2 is equivalent to the following assertion.

######  Theorem 1.3 (Lack of progressions implies density increment).

Let $\delta>0$ and $k\geqslant 1$. Let $N\geqslant 1$, and let
$A\subseteq[1,N]$ be such that $|A|/|[1,N]|\geqslant\delta$, and such that $A$
contains no proper arithmetic progressions of length $k$. Then, if $N$ is
sufficiently large depending on $k$ and $\delta$, there exists an arithmetic
progression $P\subseteq[1,N]$ with $|P|\geqslant\omega(N,\delta)$ for some
function $\omega(N,\delta)$ of $N$ which goes to infinity as $N\to\infty$ for
each fixed $\delta$, such that we have the density increment $|A\cap
P|/|P|\geqslant\delta+c(\delta)$, where $c(\delta)>0$ is a function of
$\delta$ which is bounded away from zero whenever $\delta$ is bounded away
from zero.

The deduction of Theorem 1.2 from Theorem 1.3 is a straightforward induction
argument. For details of arguments of this type any of [25, 26, 27, 31, 54]
may be consulted, or indeed §7 or 11 of this paper. Of course, the final bound
$N_{0}(\delta,k)$ obtained in Theorem 1.2 will depend on the explicit bounds
$\omega(N,\delta)$, $c(\delta)$ obtained in Theorem 1.3. In Roth’s $k=3$
argument in [54], $c(\delta)$ was roughly $\delta^{2}$ and $\omega(N,\delta)$
was roughly $N^{1/2}$, which led to a final bound of the form
$N_{0}(\delta,3)\leqslant\exp(\exp(C/\delta))$. In Gowers’ extension of Roth’s
argument in [27], $c(\delta)$ was roughly $\delta^{C_{k}}$ and
$\omega(N,\delta)$ was roughly $N^{c_{k}}$ for some $C_{k},c_{k}>0$ depending
only on $k$, which led to a final bound of the form
$N_{0}(\delta,k)\leqslant\exp(\exp(C_{k}/\delta^{C_{k}}))$ (see [27] for a
more precise statement). These are the best known bounds for $N_{0}(\delta,k)$
except in the $k=3$ case, where the current record is
$N_{0}(\delta,3)\leqslant(C/\delta)^{C/\delta^{2}}$, due to Bourgain [10].

The next step is to pass from the interval $[1,N]$ to a cyclic group
$\mathbb{Z}/N\mathbb{Z}$ for some prime $N$. Indeed, by using Bertrand’s
postulate111that is, there is always a prime between $X$ and $2X$ and a simple
covering argument to split progressions in $\mathbb{Z}/N\mathbb{Z}$ into
progressions in $[1,N]$, one can show that Theorem 1.3 is in turn equivalent
for each fixed $k$ (up to minor changes in the bounds $\omega(N,\delta)$ and
$c(\delta)$) to the following statement.

######  Theorem 1.4 (Lack of progressions implies density increment).

Let $\delta>0$ and $k\geqslant 1$. Let $N\geqslant 1$ be a prime, and let $Q$
be a proper progression in $\mathbb{Z}/N\mathbb{Z}$ such that $|Q|\geqslant
c_{0}N$ for some $0<c_{0}\leqslant 1$. Let $A\subseteq Q$ be such that
$|A|\geqslant\delta N$, and such that $A$ contains no proper arithmetic
progressions of length $k$. Then, if $N$ is sufficiently large depending on
$k$ and $\delta$, there exists a proper arithmetic progression
$P\subseteq\mathbb{Z}/N\mathbb{Z}$ with $|P|\geqslant\omega(N,\delta,c_{0},k)$
for some function $\omega(N,\delta,c_{0},k)$ of $N$ which goes to infinity as
$N\to\infty$ for each fixed $\delta$, $c_{0}$, $k$, such that we have the
density increment

$\frac{|A\cap P|}{|P|}\geqslant\frac{|A\cap Q|}{|Q|}+c(\delta,c_{0},k),$

where $c(\delta,c_{0},k)>0$ is bounded away from zero whenever $\delta$,
$c_{0}$ are bounded away from zero and $k$ is fixed.

The deduction of Theorem 1.3 from Theorem 1.4 is not difficult, see [25, 27,
54]. Of course, it remains to prove Theorem 1.4. This was achieved in the
$k=3$ case by Roth using Fourier-analytic methods. To extend these arguments
to the case of higher $k$, Gowers introduced a collection of tools which form
a part of a theory which might be termed “higher-order Fourier analysis” for
reasons which will become clear later. In particular, to handle the $k=4$ case
required “quadratic Fourier analysis”.

While Gowers’ original argument takes place in a cyclic group
$\mathbb{Z}/N\mathbb{Z}$ of prime order, we will work in the more general
setting of an arbitrary finite additive group. This might seem unnecessary,
but is consistent with what we call the finite field philosophy. This is the
observation that many questions concerning the integers $\\{1,\dots,N\\}$ or
the cyclic group $\mathbb{Z}/N\mathbb{Z}$ may be asked very naturally for an
arbitrary finite abelian group $G$, and they may be answered there by
modifying the proof for $\mathbb{Z}/N\mathbb{Z}$ in a straightforward way.
Thus it is often the case that the passage

$\mathbb{Z}/N\mathbb{Z}\xrightarrow{\mbox{\scriptsize generalization}}G$

is rather straightforward.

However, it may be that the question is significantly easier to answer when
$G$ is some specific group, typically a vector space over a finite field such
as $\mathbb{F}_{2}^{n},\mathbb{F}_{3}^{n}$ or $\mathbb{F}_{5}^{n}$. This
observation was made in such papers as [44, 57]. In this paper we will take a
particular interest in $\mathbb{F}_{5}^{n}$ since this is the smallest
characteristic field for which arithmetic progressions of length 4 are a
sensible thing to discuss. Now the passage

$\mathbb{F}_{5}^{n}\xrightarrow{\mbox{\scriptsize generalization}}G$

might not be at all easy. However, in attempting such a route one has split
the problem into two presumably easier subproblems, and furthermore there is
now a library of tools available for effecting the generalization. This
started with the work of Bourgain [10] (though he did not phrase it this way),
and has continued with various works such as [30, 32]. The present paper,
particularly §8 and §9, is another example in this vein. For a longer
discussion of the finite field philosophy, see [31].

######  Definition 1.5 (Additive groups).

Define an _additive group_ to be a group $G=(G,+)$ with a commutative group
operation $+$; if $x\in G$ and $n\in\mathbb{Z}$ we can define the product
$nx\in G$ in the usual manner. If $f:G\to H$ is a function from one additive
group to another, and $h\in H$, we define the shift222This “ergodic” notation
corresponds to the backwards shift $T^{h}x:=x-h$ on the underlying group $G$.
We will discuss further connections with ergodic theory in §12. operator
$T^{h}$ applied to $f$ by the formula $T^{h}f(x):=f(x+h)$, and the difference
operator $h\cdot\nabla:=T^{h}-1$ applied to $f$ by the formula
$(h\cdot\nabla)f(x):=f(x+h)-f(x)$. We extend these definitions to functions of
several variables by subscripting the variable to which the operator is
applied, thus for instance if $f(x,y)$ is a function of two variables we
define $T^{h}_{x}f(x,y)=f(x+h,y)$ and $h\cdot\nabla_{x}f(x,y)=f(x+h,y)-f(x,y)$
if $x,h$ range inside an additive group $G$, and similarly for the $y$
variable.

Remark. Throughout the paper, we will write $N:=|G|$ for the cardinality of
$G$.

Remark. The notation above is of course designed to mimic that of several
variable calculus. We caution however that we do not assign any independent
meaning to the symbol $\nabla$, unless it is prepended with a shift $h$ to
create a difference operator $h\cdot\nabla$, which is of course a discrete
analogue of a directional derivative operator.

We now introduce a multilinear form $\Lambda_{k}(f_{1},\ldots,f_{k})$ which is
useful for counting arithmetic progressions. Here, and throughout the paper,
it is convenient to adopt the notation of conditional expectation, which
allows one to hide some distracting normalizing factors such as $1/N$ in our
arguments. Thus if $f:G\to\mathbb{C}$ is a complex-valued function on a finite
set $G$, and $B\subseteq G$ is a non-empty subset of $G$, we will use
$\mathbb{E}_{x\in B}f(x):=\frac{1}{|B|}\sum_{x\in B}f(x)$ to denote the
average of $f$ over $B$. We will abbreviate $\mathbb{E}_{x\in G}f(x)$ as
$\mathbb{E}(f)$ when the domain $G$ of $f$ is clear from context.

Now if $G$ is a finite additive group and
$f_{0},\ldots,f_{k-1}:G\to\mathbb{C}$ are complex-valued functions, we define
the $k$-linear form $\Lambda_{k}(f_{0},\ldots,f_{k-1})\in\mathbb{C}$ by

$\Lambda_{k}(f_{0},\ldots,f_{k-1}):=\mathbb{E}_{x,r\in
G}f_{0}(x)T^{r}f_{1}(x)\ldots T^{(k-1)r}f_{k-1}(x).$

Observe that if $A\subseteq G$ and $f_{0}=\ldots=f_{k-1}=1_{A}$, where
$1_{A}:G\to\\{0,1\\}$ denotes the indicator function of $A$, then
$\Lambda_{k}(1_{A},\ldots,1_{A})$ is just the number of progressions of length
$k$ (including those with common difference $0$), divided by the normalizing
factor of $N^{2}$. In particular, if $(N,(k-1)!)=1$ and $A$ contains no proper
progressions of length $k$ then we see that
$\Lambda_{k}(1_{A},\ldots,1_{A})=|A|/N^{2}$, which will be quite small when
$N$ is large.

It is thus of interest to determine under what conditions
$\Lambda_{k}(1_{A},\ldots,1_{A})$ is small or large. To this end, Gowers
introduced (what are now known as) the _Gowers uniformity norms_
$\|f\|_{U^{d}(G)}$ for any complex function $f:G\to\mathbb{C}$, whose
definition we now recall.

######  Definition 1.6 (Gowers uniformity norm).

Let $d\geqslant 0$, and let $f:G\to\mathbb{C}$ be a function. We define the
Gowers uniformity norm $\|f\|_{U^{d}(G)}\geqslant 0$ of $f$ to be the quantity

$\|f\|_{U^{d}(G)}:=\big{(}\mathbb{E}_{x\in G,h\in
G^{d}}\prod_{\omega\in\\{0,1\\}^{d}}{\mathcal{C}}^{|\omega|}T^{\omega\cdot
h}f(x)\big{)}^{1/2^{d}},$

where $\omega=(\omega_{1},\ldots,\omega_{d})$, $h\in(h_{1},\ldots,h_{d})$,
$\omega\cdot h:=\omega_{1}h_{1}+\ldots+\omega_{d}h_{d}$,
$|\omega|:=\omega_{1}+\ldots+\omega_{d}$, and ${\mathcal{C}}$ is the
conjugation operator ${\mathcal{C}}f(x):=\overline{f(x)}$.

Remark. An equivalent definition of the $U^{d}(G)$ norms is given by the
recursive formulae

$\|f\|_{U^{0}(G)}=\mathbb{E}(f);\quad\|f\|_{U^{1}(G)}=|\mathbb{E}(f)|;\quad\|f\|_{U^{d}}:=(\mathbb{E}_{h\in
G}\|T^{h}f\overline{f}\|_{U^{d-1}(G)}^{2^{d-1}})^{1/2^{d}}$ (1.1)

for all $d\geqslant 1$.

Remark. A configuration of the form $(x+\omega\cdot
h)_{\omega\in\\{0,1\\}^{d}}$ is called a _cube of dimension $d$_. Thus
$\|f\|_{U^{d}(G)}^{2^{d}}$ is a weighted average of $f$ over cubes; for
instance, $\|1_{A}\|_{U^{d}(G)}^{2^{d}}$ is equal to the number of cubes
contained in $A$, divided by the normalizing factor of $N^{d+1}$. The cases
$d=0,1$ are rather degenerate, and indeed $U^{d}(G)$ is not a norm in these
cases. However for $d>1$, one can show that $\|\cdot\|_{U^{d}(G)}$ is indeed a
norm, i.e. it is homogeneous, non-negative, non-degenerate, and obeys the
triangle inequality, see [27, Lemma 3.9]. These norms have also appeared
recently in ergodic theory, see for instance [41], and (together with the dual
norms $U^{d}(G)^{*}$) played a key role in [34]. It thus seems of interest to
study these norms more systematically; the results here can be viewed as a
step in that direction.

We will study these norms in detail later, but for now let us give an example
to illustrate what they are trying to capture. Suppose $f$ has the form
$f(x):=e(\phi(x))$ for some phase function $\phi:G\to\mathbb{R}/\mathbb{Z}$,
where $e:\mathbb{R}/\mathbb{Z}\to\mathbb{C}$ is the exponential map
$e(x):=e^{2\pi ix}$. Then a simple calculation shows that

$\|f\|_{U^{d}}^{2^{d}}=\mathbb{E}_{x,h_{1},\ldots,h_{d}\in
G}e((h_{1}\cdot\nabla_{x})\ldots(h_{d}\cdot\nabla_{x})\phi(x)).$

Thus the $U^{d}$ norm is in some sense measuring the oscillation present in
the $d^{th}$ “derivative” of the phase. In particular, we expect the $U^{d}$
norm to be large if the phase behaves like a “polynomial” of degree $d-1$ or
less, but small if the phase is behaving like a polynomial of degree $d$ or
higher.

We observe that as an immediate consequence of (1.1) and induction we have the
monotonicity property

$\|f\|_{U^{d}(G)}\leqslant\|f\|_{U^{d+1}(G)}\hbox{ for }d=0,1,2,\ldots.$ (1.2)

The relevance of the Gowers uniformity norms to arithmetic progressions lies
in the following result, which was stated explicitly in [27, Theorem 3.2] (in
the case of cyclic groups $G=\mathbb{Z}/N\mathbb{Z}$) but has been implicit in
the ergodic theory literature for some time. Write
$\mathcal{D}:=\\{z\in\mathbb{C}:|z|\leqslant 1\\}$ for the unit disk.

######  Proposition 1.7 (Generalized von Neumann Theorem).

Let $G$ be a finite abelian group with $(N,(k-1)!)=1$. Let
$f_{0},\dots,f_{k-1}:G\rightarrow\mathcal{D}$ be functions. Then we have

$|\Lambda_{k}(f_{0},\dots,f_{k-1})|\leqslant\min_{1\leqslant j\leqslant
k}\|f_{j}\|_{U^{k-1}(G)}.$

It is instructive to continue with the phase example given earlier. If
$f_{j}=e(\phi_{j})$, then

$\Lambda_{k}(f_{0},\ldots,f_{k-1})=\mathbb{E}_{x,r\in
G}e(\phi_{0}(x)+\phi_{1}(x+r)+\ldots+\phi_{k-1}(x+(k-1)r)).$

Thus $\Lambda_{k}(f_{0},\ldots,f_{k-1})$ is measuring the oscillation present
in the expression $\phi_{0}(x)+\phi_{1}(x+r)+\ldots+\phi_{k-1}(x+(k-1)r)$.
Proposition 1.7 can then be viewed as a statement that if this expression does
not oscillate, then neither do the expressions
$(h_{1}\cdot\nabla_{x})\ldots(h_{k-1}\cdot\nabla_{x})\phi_{j}(x)$ for any
$1\leqslant j\leqslant k$. Note that such a fact morally follows by
“differentiating” the expression
$\phi_{0}(x)+\phi_{1}(x+r)+\ldots+\phi_{k}(x+(k-1)r)$ in $k-1$ different
directions to eliminate all but one of the terms in this series. For
completeness we give a proof of this Proposition in Section 4.

######  Corollary 1.8 (Lack of progressions implies large uniformity norm
[27]).

Let $k\geqslant 3$, let $G$ be a finite additive group with $(N,(k-1)!)=1$,
and let $A\subseteq G$, $|A|=\alpha N$, be a non-empty set such that $A$ has
no proper arithmetic progressions of length $k$. If $N\geqslant
2/\alpha^{k-1}$, then we have $\|1_{A}-\alpha\|_{U^{k-1}(G)}\geqslant
2^{-k-1}\alpha^{k-1}$.

More generally, let $P$ be a proper arithmetic progression in $G$ such that
$|P|\geqslant c_{0}N$. Let $A\subseteq P$, $|A|=\alpha|P|$, be a non-empty set
which contains no proper arithmetic progressions. If $N>N_{0}(c_{0},k,\alpha)$
then we have $\|1_{A}-\alpha 1_{P}\|_{U^{k-1}(G)}\geqslant
c(c_{0},\alpha,k)>0$, where the quantity $c(c_{0},\alpha,k)$ stays bounded
away from zero when $c_{0},\alpha$ are bounded away from zero and $k$ is
fixed.

Proof.  We begin with the first claim. Since $1_{A}=\alpha+(1_{A}-\alpha)$, we
can split the expression $\Lambda_{k}(1_{A},\ldots,1_{A})$ as the sum of
$2^{k}$ expressions, one of which is $\Lambda_{k}(\alpha,\ldots,\alpha)$, and
the other $2^{k-1}$ of which can be bounded in magnitude by
$\|1_{A}-\alpha\|_{U^{k-1}(G)}$ thanks to Proposition 1.7. In particular we
conclude that

$|\Lambda_{k}(\alpha,\ldots,\alpha)-\Lambda_{k}(1_{A},\ldots,1_{A})|\leqslant
2^{k}\|1_{A}-\alpha\|_{U^{k-1}(G)}.$

But clearly $\Lambda_{k}(\alpha,\ldots,\alpha)=\alpha^{k}$, while since $A$
has no proper arithmetic progressions we have
$\Lambda_{k}(1_{A},\ldots,1_{A})=|A|/N^{2}=\alpha/N\leqslant\alpha^{k}/2$. The
first claim follows.

The second claim proceeds similarly but is based upon the decomposition
$1_{A}=\alpha 1_{P}+(1_{A}-\alpha 1_{P})$, and the observation that
$\Lambda_{k}(1_{P},\ldots,1_{P})\geqslant c(c_{0},k)>0$ for some positive
quantity $c(c_{0},k)$ depending on $c_{0}$ and $k$; we leave the details to
the reader.

Comparing this Proposition with Theorem 1.4, we thus see that in order to
prove Szemerédi’s theorem for a fixed $k$, it suffices to prove the following:

######  Theorem 1.9 (Large uniformity norm implies density increment [27]).

Let $\eta>0$ and $k\geqslant 3$. Let $G=\mathbb{Z}/N\mathbb{Z}$ be a cyclic
group of prime order, and let $f:G\to\mathcal{D}$ be a real-valued bounded
function such that $\mathbb{E}(f)=0$ and $\|f\|_{U^{k-1}(G)}\geqslant\eta$.
Then, if $N>N_{0}(k,\eta)$, there exists a proper arithmetic progression
$P\subseteq G$ with $|P|\geqslant\omega(N,\eta,k)$ such that $\mathbb{E}_{x\in
P}f(x)\geqslant c(\eta,k)$, where

  * •

$\omega(N,\eta)\rightarrow\infty$ as $N\rightarrow\infty$ for fixed $\eta$;

  * •

$c(\eta,k)>0$ is bounded away from zero when $\eta$ is bounded away from zero
and $k$ is fixed.

Indeed, Theorem 1.4 then follows by applying Corollary 1.8 and then invoking
Theorem 1.9 with $f:=1_{A}-(\mathbb{E}_{x\in Q}1_{A}(x))1_{Q}$. Theorem 1.9 is
in fact deduced in [27] from the following stronger theorem:

######  Theorem 1.10 (Weak inverse theorem for
$U^{k-1}(\mathbb{Z}/N\mathbb{Z})$ [27]).

Let $\eta>0$ and $k\geqslant 3$. Let $G=\mathbb{Z}/N\mathbb{Z}$ be a cyclic
group of prime order, and let $f:G\to\mathcal{D}$ be a bounded function such
that $\|f\|_{U^{k-1}(G)}\geqslant\eta$. Then, if
$N\geqslant\exp(C_{k}\eta^{-C_{k}})$ for some sufficiently large $C_{k}>0$,
one can partition $\mathbb{Z}/N\mathbb{Z}$ into arithmetic progressions
$(P_{j})_{j\in J}$, each of size $|P_{j}|\geqslant
c_{k}\eta^{-C_{k}}N^{c_{k}\eta^{-C_{k}}}$ for some $c_{k},C_{k}>0$, such that

$\sum_{j\in J}|\mathbb{E}(f1_{P_{j}})|\geqslant c_{k}\eta^{C_{k}}$

for some $c_{k},C_{k}>0$.

Theorem 1.9 (and hence Theorem 1.1) follows quickly from this and the mean
zero hypothesis $\sum_{j\in J}\mathbb{E}(f1_{P_{j}})=\mathbb{E}(f)=0$. Indeed
one gets a fairly good quantitative result for Theorem 1.2, with
$N_{0}=\exp(\exp(C_{k}\delta^{-C_{k}}))$ for some explicit $C_{k}>0$; see
[27].

We refer to Theorem 1.10 as a weak inverse theorem because it gives a
necessary criterion in order for a bounded function $f$ to have large
$U^{k-1}(G)$ norm, and hence a sufficient condition for the $U^{k-1}(G)$ norm
to be small. As discussed above, this theorem is strong enough to imply
Szemerédi’s theorem. Also, Theorem 1.10 could potentially be useful, when
combined with such tools as Theorem 1.7, for not only demonstrating the
existence of progressions of length $k$ in a given set $A$, but in fact
providing an accurate count as to _how many_ such progressions there are. For
instance, one might hope to count the number of progressions of length $k$ in
the primes less than $N$ by using Theorem 1.10 to show that a certain counting
function $f$ associated to the primes has small
$U^{k-1}(\mathbb{Z}/N\mathbb{Z})$ norm and hence its contribution to the count
of progressions in the primes could be controlled using Theorem 1.7. However,
the sufficient condition for smallness of $U^{k-1}(\mathbb{Z}/N\mathbb{Z})$
given by Theorem 1.10 is very difficult to verify for sets such as the primes
(being at least as difficult as the Elliott-Halberstam conjecture, which is
not known to be implied even by the GRH).

It is thus of interest to obtain a better inverse theorem for the
$U^{k-1}(\mathbb{Z}/N\mathbb{Z})$ norm, which gives a more easily checkable
condition for when this norm is small. Ideally we would like this condition to
be both necessary and sufficient, at least up to constant losses. In this
paper we shall achieve these objectives for $k=4$.

In subsequent work we will give various applications of the results and
methods of this paper. In [35] we obtain a new bound on the size of the
largest subset of the vector space $\mathbb{F}_{5}^{n}$ with no 4-term
arithmetic progression, and we hope to generalize that result to arbitrary
abelian groups $G$. In another series of papers, we will obtain an asymptotic
formula for the number of quadruples $p_{1}<p_{2}<p_{3}<p_{4}\leqslant N$ of
primes in arithmetic progression.

##  2\. Inverse theorems for $U^{k-1}$ norms

We have now motivated why we are interested in an inverse theorem for the
$U^{k-1}$ norms. Before we state our main theorems, let us give some other
examples and results which will illustrate what the inverse theorem should be.
Recall that the $U^{d}$ norm of a function $e(\phi)$ measures the oscillation
in the $d^{th}$ derivative of the phase $\phi$. Also recall that a polynomial
of degree at most $d-1$ is a function whose $d^{th}$ derivative vanishes. We
generalize this concept as follows.

######  Definition 2.1 (Locally polynomial phase functions).

If $B$ is any non-empty subset of a finite additive group $G$ and $d\geqslant
1$, we say that a function $\phi:B\to\mathbb{R}/\mathbb{Z}$ is a _polynomial
phase function of order at most $d-1$ locally on $B$_ if we have

$(h_{1}\cdot\nabla_{x})\ldots(h_{d+1}\cdot\nabla_{x})\phi(x)=0$

whenever the cube
$(x+\omega_{1}h_{1}+\ldots+\omega_{d}h_{d})_{\omega_{1},\ldots,\omega_{d}\in\\{0,1\\}}$
is contained in $B$. If $f:B\to\mathbb{C}$ is a function, we define the _local
polynomial bias of order $d$ on $B$_ $\|f\|_{u^{d}(B)}$ to be the quantity

$\|f\|_{u^{d}(B)}:=\sup|\mathbb{E}_{x\in B}(f(x)e(-\phi(x)))|$

where $\phi$ ranges over all local polynomial phase functions of order at most
$d-1$ on $B$.

To begin with we will work in the global setting $B=G$, but as will become
clear later we will need to also work in the local setting. We will refer to
polynomial phase functions of degree at most 1 as _linear phase functions_ ,
and of degree at most 2 as _quadratic phase functions_ , with the modifiers
“local” or “global” as appropriate.

The quantity $\|\|_{u^{d}(B)}$ is clearly a seminorm. It shares several
features in common with the $U^{d}(G)$ norm. First of all, like the $U^{d}(G)$
norm, we have the monotonicity $\|f\|_{u^{d}(B)}\leqslant\|f\|_{u^{d+1}(B)}$,
and when $B=G$ we also have the shift invariance
$\|T^{h}f\|_{u^{d}(G)}=\|f\|_{u^{d}(G)}$. We also have the conjugation
symmetry $\|\overline{f}\|_{u^{d}(B)}=\|f\|_{u^{d}(B)}$, and the phase
invariance $\|fe(\phi)\|_{u^{d}(B)}=\|f\|_{u^{d}(B)}$ whenever $\phi$ is a
locally polynomial phase of degree at most $d-1$ on $B$. The latter invariance
also extends to the $U^{d}(G)$ norm, thus

$\|fe(\phi)\|_{U^{d}(G)}=\|f\|_{U^{d}(G)}$ (2.1)

whenever $\phi:G\to\mathbb{R}/\mathbb{Z}$ is a global polynomial phase
function of degree at most $d-1$. Indeed, this invariance333This polynomial
phase invariance also indicates why Fourier analysis - which is essentially
invariant under modulation by linear phase functions but not by quadratic or
higher phases - is only able to effectively deal with the $U^{2}(G)$ norm and
not with higher norms. To deal with the $U^{3}(G)$ norm thus requires some
sort of “quadratic Fourier analysis” which is insensitive to phase modulations
by quadratic phases. The results here can be viewed as some preliminary steps
towards establishing such a quadratic Fourier analysis theory. can easily be
seen from (1.1) and induction, using the fact that the derivative of a
polynomial of degree at most $d-1$ is a polynomial of degree $d-2$.

From this invariance and (1.1), (1.2) we conclude that

$\|f\|_{U^{d}(G)}=\|fe(-\phi)\|_{U^{d}(G)}\geqslant\|fe(-\phi)\|_{U^{1}(G)}=|\mathbb{E}_{x\in
G}(f(x)e(-\phi(x)))|$

whenever $\phi$ is a global polynomial phase of degree at most $d-1$. Taking
suprema over all $\phi$, we obtain the inequality

$\|f\|_{U^{d}(G)}\geqslant\|f\|_{u^{d}(G)}$ (2.2)

for all $d\geqslant 1$, all additive groups $G$, and all $f:G\to\mathbb{C}$.

It is now natural to ask whether the inequality (2.2) can be reversed. When
$d=1$ it is easy to verify (using (1.1) and the fact that polynomials of
degree at most 0 are constant) that we in fact have equality:

$\|f\|_{U^{1}(G)}=\|f\|_{u^{1}(G)}.$

Consider next the case $d=2$. For this we need the Fourier transform. Let
$\widehat{G}$ be the Pontryagin dual of $G$, in other words the space of
homomorphisms $\xi:x\mapsto\xi\cdot x$ from $G$ to $\mathbb{R}/\mathbb{Z}$. As
is well known, $\widehat{G}$ is an additive group which is isomorphic to $G$.
If $\xi\in\widehat{G}$, we define the _Fourier coefficient_ $\widehat{f}(\xi)$
of $f$ at the frequency $\xi$ by the formula

$\widehat{f}(\xi)=\mathbb{E}_{x}f(x)e(-\xi\cdot x).$

As is well known, we have the _Fourier inversion formula_

$f(x)=\sum_{\xi\in\widehat{G}}\widehat{f}(\xi)e(\xi\cdot x)$

and the _Plancherel identity_

$\mathbb{E}(|f|^{2})=\sum_{\xi\in\widehat{G}}|\widehat{f}(\xi)|^{2}.$ (2.3)

One can then easily verify the pleasant identity

$\|f\|_{U^{2}(G)}^{4}=\sum_{\xi\in\widehat{G}}|\widehat{f}(\xi)|^{4}.$ (2.4)

For instance, this can be achieved by first establishing the identity
$\|f\|_{U^{2}}^{4}=\mathbb{E}(|f*f|^{2})^{2}$, where
$f*f(x):=\mathbb{E}_{y}f(y)f(x-y)$ is the convolution of $f$ with itself, and
then using (2.3). Next, we make the easy observation that if
$\phi:G\to\mathbb{R}/\mathbb{Z}$ is a global polynomial phase function of
degree at most 1, then $x\mapsto\phi(x)-\phi(0)$ is a homomorphism from $G$ to
$\mathbb{R}/\mathbb{Z}$, and hence there exists $\xi\in\widehat{G}$ such that
$\phi(x)=\xi\cdot x+\phi(0)$. From this it is easy to see that

$\|f\|_{u^{2}(G)}=\sup_{\xi\in\widehat{G}}|\widehat{f}(\xi)|.$ (2.5)

Combining (2.3), (2.4), (2.5) we readily conclude

######  Proposition 2.2 (Inverse theorem for $U^{2}(G)$ norm).

Let $f:G\to\mathcal{D}$ be a bounded function. Then

$\|f\|_{u^{2}(G)}\leqslant\|f\|_{U^{2}(G)}\leqslant\|f\|_{u^{2}(G)}^{1/2}.$

We remark that this Proposition easily implies the $k=3$ case of Theorem 1.10
(using Dirichlet’s theorem on approximation by rationals to cover $G$ by
progressions on which $\phi$ is close to constant), and hence also implies
Szemerédi’s theorem for $k=3$. Indeed this is essentially Roth’s original
argument [54], albeit phrased in very modern language.

Based on evidence such as Proposition 2.2, one is tempted to conjecture that
the $U^{d}(G)$ and $u^{d}(G)$ norms are also related for higher $d$, in the
sense that if $f$ is bounded and one of the two norms $\|f\|_{U^{d}(G)}$,
$\|f\|_{u^{d}(G)}$ is small, then the other is also. From (2.2) we already
know that one direction is true: smallness of the $U^{d}(G)$ norm implies the
smallness of the $u^{d}(G)$ norm. Our first main result establishes a converse
to this in the $d=3$ case when $G=\mathbb{F}_{5}^{n}$, though with only
partially satisfactory control on the constants.

######  Theorem 2.3 (Inverse theorem for $U^{3}(\mathbb{F}_{5}^{n})$).

Let $f:\mathbb{F}_{5}^{n}\to\mathcal{D}$ be a bounded function and let
$0<\eta\leqslant 1$.

  1. (i)

If $\|f\|_{U^{3}(\mathbb{F}_{5}^{n})}\geqslant\eta$, then there exists a
subspace $W\leqslant\mathbb{F}_{5}^{n}$ of codimension at most $(2/\eta)^{C}$
such that

$\mathbb{E}_{y\in\mathbb{F}_{5}^{n}}\|f\|_{u^{3}(y+W)}\geqslant(\eta/2)^{C},$
(2.6)

where we can take $C=2^{16}$. In particular, there exists $y\in G$ such that
$\|f\|_{u^{3}(y+W)}\geqslant(\eta/2)^{C}$.

  2. (ii)

Conversely, given any subspace $W\leqslant\mathbb{F}_{5}^{n}$ and any function
$f:\mathbb{F}_{5}^{n}\to\mathbb{C}$ we have
$\|f\|_{U^{3}(\mathbb{F}_{5}^{n})}\geqslant\|f\|_{u^{3}(\mathbb{F}_{5}^{n})}\geqslant
5^{-n}|W|\|f\|_{u^{3}(y+W)}$ for any $y\in\mathbb{F}_{5}^{n}$.

Combining the two parts of the theorem together we see that

$\|f\|_{u^{3}(\mathbb{F}_{5}^{n})}\leqslant\|f\|_{U^{3}(\mathbb{F}_{5}^{n})}\leqslant\frac{C}{\log^{c}(1+1/\|f\|_{u^{3}(\mathbb{F}_{5}^{n})})}$
(2.7)

for some absolute constants $c,C>0$. Thus this does give a result which
asserts that the smallness of the $U^{3}(\mathbb{F}_{5}^{n})$ norm implies the
smallness of the $u^{3}(\mathbb{F}_{5}^{n})$ norm and vice versa, although the
dependence of constants is poor444We conjecture that one can improve the upper
bound in (2.7) to a polynomial dependence (bringing this estimate in line with
Proposition 2.2; see §13 for further discussion.. Note however that the
control is much better if one localizes the quadratic bias norm
$u^{3}(\mathbb{F}_{5}^{n})$ to cosets $y+W$ of $W$. We remark that there is
nothing particularly special about the finite field $\mathbb{F}_{5}^{n}$, and
one has similar results for any other finite field of odd characteristic,
though the constants depend of course on the field.

We shall prove Theorem 2.3 (i) in §6 ((ii) is easier, and we will prove it in
§3); it contains many of the main ideas of this paper, which combine the
Fourier and combinatorial analysis of Gowers in [25] with an additional
“symmetry argument” which is necessary to obtain a strong inverse theorem
instead of a weak inverse theorem. As a consequence we obtain, in §7, a
Szemerédi theorem for progressions of length 4 in $\mathbb{F}_{5}^{n}$.

Let us now discuss finite abelian groups $G$ in general, particular importance
being attached to $\mathbb{Z}/N\mathbb{Z}$ on account of potential
applications. It is tempting to conjecture, in light of the preceding results,
that in such groups, any bounded function with small $u^{d}(G)$ norm must
necessarily have small $U^{d}(G)$ norm. Unfortunately, such a statement is
false, even for $G=\mathbb{Z}/N\mathbb{Z}$. This fact was essentially
discovered by Furstenberg and Weiss [24], in the closely related context of
determining characteristic factors for multiple recurrence in ergodic theory;
a similar observation was also made in page 487 of [27]. See §12 for some
further discussion of this connection. We give one instance of the
Furstenberg-Weiss example as follows:

######  Example 2.4.

Let $N$ be a large prime number, and let $M$ be the largest integer less than
$\sqrt{N}$. Let $G:=\mathbb{Z}/N\mathbb{Z}$, and let $f:G\to\mathbb{C}$ be the
bounded function defined by setting $f(yM+z):=e(yz/M)\psi(y/M)\psi(z/M)$
whenever $-M/10\leqslant y,z\leqslant M/10$, and $f=0$ otherwise; here
$\psi:\mathbb{R}\to\mathbb{R}_{\geqslant 0}$ is a non-negative smooth cutoff
function which equals one on the interval $[-1/20,1/20]$ and vanishes outside
of $[-1/10,1/10]$. Then a direct calculation shows that
$\|f\|_{U^{3}(G)}\geqslant c_{0}$ for some absolute constant $c_{0}>0$,
basically because all the phases in the expression for $\|f\|_{U^{3}(G)}^{8}$
cancel out leaving only the non-negative cutoffs $\psi$, whereas a Weyl sum
computation reveals that $\mathbb{E}(fe(-\phi))=O(N^{-c})$ for any quadratic
phase function $\phi$ and some explicit constant $c>0$. (Note that when $N$ is
prime, the only quadratic phase functions $\phi$ are those of the form
$\phi(x)=ax^{2}+bx+c$ where $a,b,c\in\mathbb{R}/\mathbb{Z}$ with $Na=Nb=0$;
see Lemma 3.1). We omit the details.

The heart of the difficulty here is that the function $yM+z\mapsto yz/M$ is
locally quadratic on the set $B:=\\{yM+z:-M/10\leqslant y,z\leqslant M/10\\}$,
which is a fairly large subset of $G$, but does not extend (even
approximately) to a _globally_ quadratic phase function on all of $G$. These
locally quadratic phase functions are thus a genuinely new class of
obstructions to having small $U^{d}(G)$ norm which must now also be accounted
for in order to produce a genuine inverse theorem for the $U^{3}(G)$ norm.
Similar considerations also apply, of course, to the $U^{d}(G)$ norms for
$d>3$.

We must therefore understand the proper generalization of sets such as
$B=\\{yM+z:-M/10\leqslant y,z\leqslant M/10\\}$. It turns out that there are
two ways to obtain such a generalization, which are in a sense dual to one
another, namely that of _generalized arithmetic progressions_ and that of
_Bohr sets_. For technical reasons it is convenient to work in the first
instance with the latter notion, but we will discuss generalized arithmetic
progressions later in the paper.

######  Definition 2.5 (Bohr sets).

Let $G$ be a finite additive group, and let $S\subseteq\widehat{G}$, $|S|=d$
be a subset of the dual group. We define a sub-additive quantity $\|\|_{S}$ on
$G$ by setting

$\|x\|_{S}:=\sup_{\xi\in S}\|\xi\cdot x\|_{\mathbb{R}/\mathbb{Z}},$

where $\|x\|_{\mathbb{R}/\mathbb{Z}}$ denotes the distance to the nearest
integer, and define the _Bohr set_ $B(S,\rho)\subseteq G$ for any $\rho>0$ to
be the set

$B(S,\rho):=\\{x\in G:\|x\|_{S}<\rho\;\;\mbox{for all }\xi\in S\\}.$

Note that the dependence of the Bohr set $B(S,\rho)$ on $\rho$ can be rather
discontinuous , as can be seen rather dramatically in finite field geometries
such as $\mathbb{F}_{3}^{n}$. This is inconvenient in applications, but
fortunately it was noted by Bourgain555In fact rather earlier Gowers [27,
Lemma 10.10] employed an argument which establishes that all Bohr sets in
$\mathbb{Z}/N\mathbb{Z}$, $N$ prime, are regular in a very weak sense. [10]
that one may restrict attention to “regular” Bohr sets which enjoy some
limited continuity properties in $\rho$.

######  Definition 2.6 (Regular Bohr sets [10]).

Let $S\subseteq\widehat{G}$, $|S|=d$, be a set of characters, and suppose that
$\rho\in(0,1)$. A Bohr set $B(S,\rho)$ is said to be _regular_ if one has

$(1-100d|\kappa|)|B(S,\rho)|\leqslant|B(S,(1+\kappa)\rho)|\leqslant(1+100d|\kappa|)|B(S,\rho)|$

whenever $|\kappa|\leqslant 1/100d$.

Lemma 8.2 gives a plentiful supply of regular Bohr sets. The constant 100 can
be lowered but this will not concern us here. With this definition in place,
we can now give the generalization of Theorem 2.3 to arbitrary groups.

######  Theorem 2.7 (Inverse theorem for $U^{3}(G)$).

Let $G$ be an finite additive group of odd order, let $f:G\to\mathcal{D}$ be a
bounded function and let $0<\eta\leqslant 1$.

  1. (i)

If $\|f\|_{U^{3}(G)}\geqslant\eta$, then there exists a regular Bohr set
$B:=B(S,\rho)$ in $G$ with $|S|\leqslant(2/\eta)^{C}$ and
$\rho\geqslant(\eta/2)^{C}$ such that

$\mathbb{E}_{y\in G}\|f\|_{u^{3}(y+B)}\geqslant(\eta/2)^{C},$ (2.8)

where it is permissible to take $C=2^{24}$. In particular, there exists $y\in
G$ such that $\|f\|_{u^{3}(y+B)}\geqslant(\eta/2)^{C}$.

  2. (ii)

Conversely, $B=B(S,\rho)$ is a regular Bohr set, if $f:G\to\mathcal{D}$ is a
bounded function and if $\|f\|_{u^{3}(y+B)}\geqslant\eta$, then we have

$\|f\|_{U^{3}(G)}\geqslant(\eta^{3}\rho^{2}/C^{\prime}d^{3})^{d}$

for some absolute constant $C^{\prime}$.

Note that the $u^{3}(G)$ norm is no longer involved in this inverse theorem;
this is necessary as demonstrated by Example 2.4, and has to do with the lack
of extendibility of some local quadratic phases to global ones. In later
sections we will prove other, related, inverse theorems for the $U^{3}(G)$
norm. In §10 we will obtain a result in which the quadratic phases are given
quite explicitly when $G=\mathbb{Z}/N\mathbb{Z}$. Then, in Theorem 12.8, we
will provide a link to recent ergodic-theoretic work of Host-Kra and Ziegler .

In a future series of papers we will prove an enhanced version of Theorem 2.7,
and use it to establish an asymptotic for the number of quadruples
$p_{1}<p_{2}<p_{3}<p_{4}\leqslant N$ of primes in arithmetic progression. The
enhancement required is that we must be able to deal with functions
$f:\mathbb{Z}/N\mathbb{Z}\rightarrow\mathbb{C}$ which are not necessarily
bounded, in particular functions such as $f=\Lambda-1$, where $\Lambda$ is the
von Mangoldt function. Once this is done, one may analyse the $u^{3}$ norm of
$f$ using what are, in essence, rather classical methods of analytic number
theory such as Vaughan’s decomposition of $\Lambda$.

A word of reassurance is perhaps in order for the reader interested in this
result concerning primes. Although the present paper is long, only a few
sections of it, namely sections §4, 5, 8 and 9, are relevant to that work. In
fact it is hoped that the subsequent papers on primes will be readable largely
independently of the present work.

Let us briefly mention the connection between the results here and those in
[61]. In that paper the second author introduced the concept of a _uniformly
almost periodic function of order $k-2$_, which generalized the concept of a
polynomial phase of order at most $k-2$ (and which incorporates the “locally
polynomial phases” discussed above. One also obtained (by very elementary
means) an inverse theorem for the $U^{k-1}$ norms involving these uniformly
almost periodic functions, see [61, Lemma 5.11]. However, because the
uniformly almost periodic functions are a larger class than the locally
polynomial phases, those results are weaker than the inverse theorems
presented here. Nevertheless, with substantial additional effort (involving
for instance the van der Waerden theorem) it is possible to use the inverse
theorem for uniformly almost periodic functions to obtain another proof of
Szemerédi’s theorem. See [61] for more details. We also remark that very
similar objects (the _anti-uniform functions_) were also utilized in [34] in
order to reduce the task of establishing arbitrarily long progressions in the
primes to Szemerédi’s theorem.

Finally, let us offer a word of explanation for our policy concerning
constants. For many of the arguments of this paper we have supplied exact
constants, eschewing excessive use of the $O$-notation. This perhaps allows
one to better see how bounds from different lemmas combine with one another to
influence later bounds. Some readers may, however, prefer to replace such
quantities as $2^{90}\eta^{-384}$ with $C\eta^{-C}$ when reading the paper.

##  3\. A model problem: global quadratic phase functions

We now present a simple result, namely the classification of globally
quadratic phase functions on an arbitrary additive group $G$ of odd order,
which we will need later, and which will serve to illustrate our strategy for
the more advanced results we give below.

Let us call a homomorphism $M:G\mapsto\widehat{G}$ _self-adjoint_ if we have

$Mx\cdot y-My\cdot x=0\hbox{ for all }x,y\in G.$

######  Lemma 3.1 (Inverse theorem for globally quadratic phase functions).

Let $G$ be a finite additive group of odd order, and let
$\phi:G\to\mathbb{R}/\mathbb{Z}$ be a globally quadratic phase function. Then
there exists $c\in\mathbb{R}/\mathbb{Z}$, $\xi\in\widehat{G}$, and a self-
adjoint homomorphism $M:G\to\widehat{G}$ such that $\phi(x)=Mx\cdot x+\xi\cdot
x+c$. Conversely, all such functions $x\mapsto Mx\cdot x+\xi\cdot x+c$ are
globally quadratic phase functions.

Proof.  The converse is easy, so we focus on the forward direction. It is
convenient to adopt the notation ${\mathbf{p}}(x_{1},\ldots,x_{n})$ to denote
an arbitrary function of variables $x_{1},\ldots,x_{n}$ which takes values in
$\mathbb{R}/\mathbb{Z}$, where ${\mathbf{p}}$ can vary from line to line or
even within the same line. This is useful for handling expressions whose exact
value is not important for the argument, but whose functional dependencies on
other variables needs to be recorded.

We shall give an argument which may seem a bit cumbersome (and is certainly
not the shortest proof of this lemma), but it will serve to motivate the proof
of Theorems 2.3 and 2.7. Indeed, this lemma can be thought of in some sense as
the $\eta=1$ case of those theorems. First observe that if $\phi$ is a
quadratic phase function, then $(h\cdot\nabla_{x})\phi$ is a linear phase
function for each $h$. Thus for each $h\in G$ there exists
$\xi_{h}\in\widehat{G}$ such that

$(h\cdot\nabla_{x})\phi(x)=\phi(x+h)-\phi(x)=\xi_{h}\cdot
x+{\mathbf{p}}(h)\hbox{ for all }x,h\in G.$ (3.1)

The next step is to obtain some linearity on the map $h\mapsto\xi_{h}$, by
using difference operators to eliminate various terms. Let $k\in G$ be
arbitrary. If we apply the difference operator $(k\cdot\nabla_{x})$ to (3.1)
we can eliminate the ${\mathbf{p}}(h)$ term to obtain

$(k\cdot\nabla)\phi(x+h)-(k\cdot\nabla)\phi(x)=\xi_{h}\cdot k\hbox{ for all
}x,h,k\in G.$ (3.2)

If we then apply the difference operator $(h_{1}\cdot\nabla_{h})$ some
$h_{1}\in G$ to eliminate the $(k\cdot\nabla)\phi(x)$ term, we obtain

$(h_{1}\cdot\nabla)(k\cdot\nabla)\phi(x+h)=(h_{1}\cdot\nabla_{h})\xi_{h}\cdot
k\hbox{ for all }x,h,k,h_{1}\in G.$ (3.3)

Making the substitution $y=x+h$ we obtain

$(h_{1}\cdot\nabla)(k\cdot\nabla)\phi(y)=(h_{1}\cdot\nabla_{h})\xi_{h}\cdot
k\hbox{ for all }y,h,k,h_{1}\in G.$ (3.4)

If we then apply the difference operator $(h_{2}\cdot\nabla_{h})$ for some
$h_{2}\in G$ to eliminate the remaining $\phi$ term, we conclude

$0=(h_{2}\cdot\nabla_{h})(h_{1}\cdot\nabla_{h})\xi_{h}\cdot k\hbox{ for all
}y,h,k,h_{1}\in G.$ (3.5)

Since $k$ is arbitrary, we conclude that

$(h_{2}\cdot\nabla_{h})(h_{1}\cdot\nabla_{h})\xi_{h}=0\hbox{ for all
}h_{1},h_{2}\in G.$ (3.6)

Thus if we write

$\xi_{h}=2Mh+\xi_{0}$ (3.7)

then we see that $M:G\mapsto\widehat{G}$ is a group homomorphism. Note that we
can insert the $2$ in front of $M$ because $|G|$ is odd; this factor of 2 will
be convenient later. Inserting this back into (3.1) we obtain

$(h\cdot\nabla_{x})\phi(x)=2Mh\cdot x+\xi_{0}\cdot x+{\mathbf{p}}(h)\hbox{ for
all }x,h\in G.$ (3.8)

This is almost what we want, but we must somehow “integrate” the partial
derivative $h\cdot\nabla_{x}$. To do this we must first establish that $M$ is
self-adjoint. Informally, this self-adjointness reflects the symmetry
$(h^{\prime}\cdot\nabla)(h\cdot\nabla)\phi=(h\cdot\nabla)(h^{\prime}\cdot\nabla)\phi$
of the second derivative. To make this rigorous (and in a manner which will
extend suitably to more general situations) we shall use the following
“symmetry argument”. In order to focus on the $Mh\cdot x$ term, we shall write
(3.8) as

${\mathbf{p}}(x+h)+{\mathbf{p}}(x)+{\mathbf{p}}(h)-2Mh\cdot x=0\hbox{ for all
}x,h\in G.$ (3.9)

Substituting $x$ by $y$ and subtracting to eliminate ${\mathbf{p}}(h)$, we
obtain

${\mathbf{p}}(y+h)+{\mathbf{p}}(y)+{\mathbf{p}}(x+h)+{\mathbf{p}}(x)-2Mh\cdot(y-x)=0\hbox{
for all }x,y,h\in G.$ (3.10)

Making the substitution $z=x+y+h$, we conclude

${\mathbf{p}}(x,z)+{\mathbf{p}}(y,z)-2M(z-x-y)\cdot(y-x)=0\hbox{ for all
}x,y,z\in G.$ (3.11)

Absorbing as many terms as possible into the unspecified functions
${\mathbf{p}}$, we conclude that

${\mathbf{p}}(x,z)+{\mathbf{p}}(y,z)+2\\{x,y\\}=0\hbox{ for all }x,y,z\in G,$
(3.12)

where $\\{x,y\\}$ is the anti-symmetric form

$\\{x,y\\}:=Mx\cdot y-My\cdot x.$ (3.13)

Freezing the value of $z$, we conclude that

${\mathbf{p}}(x)+{\mathbf{p}}(y)+2\\{x,y\\}=0\hbox{ for all }x,y\in G.$ (3.14)

Replacing $y$ by $y^{\prime}$ and subtracting to eliminate the
${\mathbf{p}}(x)$ factor, we conclude

${\mathbf{p}}(y)+{\mathbf{p}}(y^{\prime})+2\\{x,y^{\prime}-y\\}=0\hbox{ for
all }x,y,y^{\prime}\in G.$ (3.15)

Thus for each $y,y^{\prime}$, the linear function
$x\mapsto\\{x,y^{\prime}-y\\}$ is independent of $x$ and is hence always
zero666There appear to be some intriguing parallels with symplectic geometry
here. Roughly speaking, the vanishing (3.16) is an assertion that the graph
$\\{(h,Mh):h\in G\\}$ is a “Lagrangian manifold” on the “phase space”
$G\times\widehat{G}$. This graph can also be interpreted (essentially) as the
“wave front set” $\\{(x,\nabla\phi(x)):x\in G\\}$ of the original function
$e(\phi)$. A similar interpretation persists in the proofs of Theorem 2.3 and
2.7 below. Thus we see hints of some kind of “combinatorial symplectic
geometry” emerging, though we do not see how to develop these possible
connections further.:

$\\{x,y^{\prime}-y\\}=0\hbox{ for all }x,y,y^{\prime}\in G.$ (3.16)

Thus $M$ is self-adjoint.

We return now to (3.8), which we write as

${\mathbf{p}}(h)+{\mathbf{p}}(x+h)-\phi(x)-2Mh\cdot x=0\hbox{ for all }x,h\in
G.$ (3.17)

From the self-adjointness of $M$ we have

$2Mh\cdot x=M(x+h)\cdot(x+h)-Mx\cdot x-Mh\cdot h$ (3.18)

and hence

${\mathbf{p}}(h)+{\mathbf{p}}(x+h)-\phi(x)+Mx\cdot x=0\hbox{ for all }x,h\in
G.$ (3.19)

In particular, if we apply difference operators in the $h$ and $x+h$ variables
we see that the phase function $-\phi(x)+Mx\cdot x$ is linear:

$(h_{1}\cdot\nabla_{x})(h_{2}\cdot\nabla_{x})(-\phi(x)+Mx\cdot x)=0\hbox{ for
all }x,h_{1},h_{2}\in G.$ (3.20)

Hence there exists $\xi\in\widehat{G}$ and a $c\in\mathbb{R}/\mathbb{Z}$ such
that

$\phi(x)-Mx\cdot x=\xi\cdot x+c.$ (3.21)

The claim follows.

As one corollary of this classification, we obtain the following “quadratic
extension theorem”.

######  Proposition 3.2 (Quadratic Extension Theorem).

Let $G$ be an additive group, let $H\leqslant G$ be a subgroup, and suppose
that $y\in G$. Then any quadratic phase function
$\phi:y+H\rightarrow\mathbb{R}/\mathbb{Z}$ can be extended (non-uniquely in
general) to a globally quadratic phase function on $G$.

Remark. An important theme of this paper is that this behaviour is specific to
cosets $y+H$, and breaks down for other sets such as Bohr sets.

As a consequence of Proposition 3.2, let us now establish the (easy) second
part of Theorem 2.3. The first inequality
$\|f\|_{U^{3}(G)}\geqslant\|f\|_{u^{3}(G)}$ follows from (2.2), so we focus on
the second inequality
$\|f\|_{u^{3}(G)}\geqslant\frac{|W|}{|G|}\|f\|_{u^{3}(y+W)}$. It suffices to
show that

$\|f\|_{u^{3}(G)}\geqslant\frac{|W|}{|G|}\big{|}\mathbb{E}_{x\in
y+W}f(x)e(-\phi(x))\big{|}$

whenever $\phi$ is a locally quadratic function on $y+W$. But by the preceding
discussion, we can extend $\phi$ to all of $G$, and write

$\frac{|W|}{|G|}\big{|}\mathbb{E}_{x\in
y+W}f(x)e(-\phi(x))\big{|}=\big{|}\mathbb{E}_{x\in
G}f(x)1_{W}(x-y)e(-\phi(x))\big{|}.$

But by Fourier inversion we may write

$1_{W}(x-y)=\mathbb{E}_{\xi\in W^{\perp}}e(\xi\cdot(x-y))$

where $W^{\perp}:=\\{\xi\in\widehat{G}:\xi\cdot x=0\hbox{ for all }x\in W\\}$.
Thus we have

$\mathbb{E}_{x\in G}f(x)1_{W}(x-y)e(-\phi(x))=\mathbb{E}_{\xi\in
W^{\perp}}\mathbb{E}_{x\in G}f(x)e(\xi\cdot(x-y)-\phi(x)).$

But since $\xi\cdot(x-y)-\phi(x)$ is globally quadratic in $x$, we have

$|\mathbb{E}_{x\in G}f(x)e(\xi\cdot(x-y)-\phi(x))|\leqslant\|f\|_{u^{3}(G)}$

and the claim follows from the triangle inequality. Note that this argument in
fact works for arbitrary groups $G$ (with $W$ now being a subgroup of $G$
rather than a subspace).

##  4\. Averaging lemmas

In this section we collect some very simple averaging estimates which we shall
rely frequently on in the sequel.

######  Lemma 4.1 (Averaging on a subgroup).

Let $G$ be an additive group, let $H$ be a finite subgroup of $G$, and let
$A\subseteq H$ be non-empty. Let $f:H\to\mathbb{C}$ be a function. Then

$\mathbb{E}_{x\in H}\mathbb{E}_{y\in x+A}f(y)=\mathbb{E}_{y\in H}f(y).$

In particular, by the pigeonhole principle there exists $x\in H$ such that

$|\mathbb{E}_{y\in x+A}f(y)|\geqslant|\mathbb{E}_{y\in H}f(y)|.$

Proof.  Since $H+h=H$ for all $h\in A$ we have

$\mathbb{E}_{x\in H}f(x+h)=\mathbb{E}_{y\in H}f(y)\hbox{ for all }h\in A.$

Averaging this over all $h\in A$ we obtain the first claim, and the second
claim then follows from the pigeonhole principle.

This Lemma will be adequate for our purposes when we are in the finite field
geometry case, because we will have plenty of subgroups available. In the
general group case, however, we will also need a more general type of
averaging principle. The next lemma contains several rather similar
formulations of such a result; all of them will be useful later on.

######  Lemma 4.2 (Averaging on a Bohr set).

Let $S\subseteq\widehat{G}$ be a set of $d$ characters and let $0<\rho<1$ and
$\varepsilon\leqslant 1/200d$ be parameters. Suppose that the Bohr set
$B:=B(S,\rho)$ is regular, and let $A\subseteq B(S,\varepsilon\rho)$ be any
set. Finally, let $f:G\rightarrow\mathcal{D}$ be any function. Then

  1. (i)

$\big{|}\mathbb{E}_{x\in B}f(x)-\mathbb{E}_{x\in B}f(x)\big{|}\leqslant
200d\varepsilon$ if $y\in A$;

  2. (ii)

$\big{|}\mathbb{E}_{x\in B}f(x)-\mathbb{E}_{x\in B}\mathbb{E}_{y\in
x+A}f(x)\big{|}\leqslant 200d\varepsilon$;

  3. (iii)

There is some $x\in B$ for which $\mathbb{E}_{y\in
x+A}f(y)\geqslant\mathbb{E}_{y\in B}f(y)-200d\varepsilon$;

  4. (iv)

There is some $x\in B(S,(1-\varepsilon)\rho)$ such that $\mathbb{E}_{y\in
x+A}f(y)\geqslant\mathbb{E}_{y\in B}f(y)-500d\varepsilon$.

Proof.  To prove (i) we must check that

$\big{|}\sum_{x\in B+y}f(x)-\sum_{x\in B}f(x)\big{|}\leqslant
200d\varepsilon|B|.$

This follows from the fact that $B(S,\rho)$ and $y+B(S,\rho)$ differ in at
most $200d\varepsilon$ elements. Indeed it is easy to see that

$B(S,\rho)\triangle(y+B(S,\rho))\subseteq B(S,(1+\varepsilon)\rho)\setminus
B(S,(1-\varepsilon)\rho)$

($\triangle$ denotes symmetric difference), and this latter set has size no
more than $200d\varepsilon$ by regularity.
(ii) follows from (i) and the triangle inequality. Indeed $|\mathbb{E}_{x\in
B}f(x+y)-\mathbb{E}_{x\in B}f(x)|\leqslant 200d\varepsilon$, whence

$\big{|}\mathbb{E}_{x\in B}\mathbb{E}_{y\in A}f(x+y)-\mathbb{E}_{x\in
B}f(x)\big{|}\leqslant 200d\varepsilon,$

which is (ii).
(iii) is immediate from (ii) and the pigeonhole principle.
(iv) follows from the pigeonhole principle and the fact that

$\mathbb{E}_{x\in B}f(x)-\mathbb{E}_{x\in
B(S,(1-\varepsilon)\rho)}\mathbb{E}_{y\in x+A}f(y)\big{|}\leqslant
500d\varepsilon,$

which is in turn implied by (ii) and the bound

$\big{|}\mathbb{E}_{x\in B}F(x)-\mathbb{E}_{x\in
B(S,(1-\varepsilon)\rho)}F(x)\big{|}\leqslant 300\epsilon d,$

valid for any $F:G\rightarrow\mathcal{D}$. To confirm this, note that

$\big{|}\sum_{x\in B}F(x)-\sum_{x\in
B(S,(1-\varepsilon)\rho)}F(x)\big{|}\leqslant|B\setminus
B(S,(1-\varepsilon)\rho)|\leqslant 100\varepsilon d|B|.$

Therefore

$\displaystyle\big{|}\mathbb{E}_{x\in B}F(x)-\mathbb{E}_{x\in
B(S,(1-\varepsilon)\rho)}F(x)\big{|}$ $\displaystyle\leqslant$
$\displaystyle\frac{1}{|B|}\bigg{|}\sum_{x\in B}F(x)-\sum_{x\in
B(S,(1-\varepsilon)\rho)}F(x)\bigg{|}$
$\displaystyle\quad+\bigg{|}\frac{1}{|B|}-\frac{1}{|B(S,(1-\varepsilon)\rho)|}\bigg{|}\cdot\bigg{|}\sum_{x\in
B(S,(1-\varepsilon)\rho)}F(x)\bigg{|}$ $\displaystyle\leqslant$ $\displaystyle
100\varepsilon d+\bigg{|}\frac{|B|}{|B(S,(1-\varepsilon)\rho)|}-1\bigg{|}$
$\displaystyle\leqslant$ $\displaystyle 100\varepsilon
d+\frac{1}{1-100\varepsilon d}-1\leqslant 300\varepsilon d.$

This completes the proof of Lemma 4.2.

We adopt the following useful notation, analogous to the ${\mathbf{p}}$
notation used in proving Lemma 3.1. When $g(x_{1},\ldots,x_{n})$ is a complex-
valued function of certain variables $x_{1},\ldots,x_{n}$ with
$\|g\|_{\infty}\leqslant 1$, we shall refer to $g(x_{1},\ldots,x_{n})$ instead
as ${\mathbf{b}}(x_{1},\ldots,x_{n})$. The notation ${\mathbf{b}}$ thus
denotes a function with $\|{\mathbf{b}}\|_{\infty}\leqslant 1$, but the
notation may refer to different functions from line to line, or even on the
same line (similar to the $O$ notation, or the use of the unspecified
constants $C$).

We now record a basic application of the Cauchy-Schwarz inequality, whose
proof is immediate.

######  Lemma 4.3 (Cauchy-Schwarz).

Let $X,Y$ be finite sets, and let $f:X\times Y\to\mathbb{C}$ be a function.
Then for any bounded function ${\mathbf{b}}(x)$ of $X$, we have

$|\mathbb{E}_{x,y}f(x,y){\mathbf{b}}(x)|\leqslant\mathbb{E}_{x}|\mathbb{E}_{y}f(x,y)|\leqslant(\mathbb{E}_{x}|\mathbb{E}_{y}f(x,y)|^{2})^{1/2}=(\mathbb{E}_{x,y,y^{\prime}}f(x,y^{\prime})\overline{f(x,y)})^{1/2}.$

In the special case when $Y=G$ is a group, we conclude in particular the _Van
der Corput inequality_

$|\mathbb{E}_{x\in X,y\in G}f(x,y){\mathbf{b}}(x)|\leqslant|\mathbb{E}_{x\in
X,y,h\in G}T^{h}_{y}f(x,y)\overline{f(x,y)}|^{1/2}$ (4.1)

whenever $f:X\times G\to\mathbb{C}$ is a function, which follows by using the
substitution $y^{\prime}=y+h$. This inequality is very useful for eliminating
unknown bounded functions ${\mathbf{b}}(x)$ in an expression to be estimated.
Using the van der Corput inequality, we can now prove Proposition 1.7.

Proof of Proposition 1.7. It suffices to prove the more general
statement777Indeed, the $U^{d}(G)$ norms are capable of controlling even more
general expressions, for instance when the linear shifts $a_{j}h$ are replaced
by polynomial shifts with no constant coefficient; this is implicitly in [4].

$|\mathbb{E}_{x,h}\prod_{j\in
J}T^{a_{j}h}f_{j}(x)|\leqslant\|f_{j_{0}}\|_{U^{|J|-1}(G)}$ (4.2)

for all finite sets $J$ with $|J|\geqslant 1$, all $j_{0}\in J$, all bounded
functions $(f_{j})_{j\in J}$, and all distinct integers $(a_{j})_{j\in J}$
such that $a_{j}-a_{j^{\prime}}$ is coprime to $|G|$ for all distinct
$j,j^{\prime}\in J$.

We induct on $|J|$. When $|J|=1$ the claim is trivial from (1.1), so suppose
$|J|\geqslant 2$ and the claim has already been proven for smaller values of
$J$. Let $j_{1}$ be an element in $J\backslash\\{j_{0}\\}$. By making the
change of variables $x\to x+a_{j_{1}}h$ if necessary we may assume that
$a_{j_{1}}=0$. Since $f_{j_{1}}$ is bounded, we can then express the left-hand
side of (4.2) as

$\big{|}\mathbb{E}_{x,h\in G}\big{(}{\mathbf{b}}(x)\prod_{j\in
J\backslash\\{j_{1}\\}}T^{a_{j}h}f_{j}(x)\big{)}\big{|},$

which by (4.1) can be bounded by

$\mathbb{E}_{k\in G}\big{(}\mathbb{E}_{x,h\in G}\big{(}\prod_{j\in
J\backslash\\{j_{1}\\}}T^{a_{j}h}(T^{a_{j}k}f_{j}\overline{f_{j}})(x)\big{)}\big{)}^{1/2}.$

Applying the inductive hypothesis (4.2) to the inner expectation, we can bound
this in turn by

$\mathbb{E}_{k\in
G}(\|T^{a_{j}k}f_{j}\overline{f_{j}}\|_{U^{|J|-2}(G)})^{1/2},$

which by Hölder’s inequality and the substitution $h:=a_{j}k$ (noting that
$(N,a_{j}-a_{j_{1}})=(N,a_{j})=1$) is bounded by

$\mathbb{E}_{h\in
G}\big{(}\|T^{h}f_{j}\overline{f_{j}}\|_{U^{|J|-2}(G)}^{2^{|J|-2}}|\big{)}^{1/2^{|J|-1}}.$

The claim then follows from (1.1).

Let us now consider averages of the form

$\mathbb{E}_{z\in B^{\prime},x\in B}(f(z){\mathbf{b}}(x){\mathbf{b}}(z+x))$

where $B,B^{\prime}$ are non-empty subsets of an additive group $G$, and
$f,g,h$ are bounded functions. If $B=B^{\prime}=G$, then a variant of
Proposition 1.7 shows that this quantity is bounded by $\|f\|_{U^{2}(G)}$, and
hence (by Proposition 2.2) if the above average is large, then $f$ must
correlate with a linear phase function. It turns out that a similar statement
is true for arbitrary $B,B^{\prime}$, provided that $B+B^{\prime}$ is only a
little bit larger than $B$.

######  Lemma 4.4 (Large trilinear form implies correlation with linear
phase).

Let $B$, $B^{\prime}$ be two non-empty subsets of an additive group $G$. Then
we have

$\|f\|_{u^{2}(B^{\prime})}\geqslant\frac{\mathbb{E}(1_{B})}{\mathbb{E}(1_{B+B^{\prime}})}|\mathbb{E}_{z\in
B^{\prime},x\in B}(f(z){\mathbf{b}}_{1}(x){\mathbf{b}}_{2}(z+x))|$

for any $f:G\to\mathbb{C}$ and any two bounded functions ${\mathbf{b}}_{1}$,
${\mathbf{b}}_{2}$.

Proof.  Without loss of generality we may assume that
$f,{\mathbf{b}}_{1},{\mathbf{b}}_{2}$ vanish outside of $B^{\prime}$, $B$,
$B+B^{\prime}$ respectively. From Fourier expansion we have

$\displaystyle\mathbb{E}_{z\in B^{\prime},x\in
B}(f(z){\mathbf{b}}_{1}(x){\mathbf{b}}_{2}(z+x))$
$\displaystyle=\frac{1}{\mathbb{E}(1_{B^{\prime}})\mathbb{E}(1_{B})}\mathbb{E}_{y\in
G}(f*{\mathbf{b}}_{1}(y){\mathbf{b}}_{2}(y))$
$\displaystyle=\frac{1}{\mathbb{E}(1_{B^{\prime}})\mathbb{E}(1_{B})}\sum_{\xi\in\widehat{G}}\widehat{f}(\xi)\widehat{\mathbf{b}}_{1}(\xi)\widehat{\mathbf{b}}_{2}(-\xi).$

On the other hand, from Plancherel we have
$\sum_{\xi\in\widehat{G}}|\widehat{\mathbf{b}}_{1}(\xi)|^{2}\leqslant\mathbb{E}(1_{B})$
and
$\sum_{\xi\in\widehat{G}}|\widehat{\mathbf{b}}_{2}(-\xi)|^{2}\leqslant\mathbb{E}(1_{B+B^{\prime}})$.
From Hölder’s inequality we thus conclude that

$|\mathbb{E}_{z\in B^{\prime},x\in
B}(f(z){\mathbf{b}}_{1}(x){\mathbf{b}}_{2}(z+x))|\leqslant\frac{\mathbb{E}(1_{B+B^{\prime}})}{\mathbb{E}(1_{B^{\prime}})\mathbb{E}(1_{B})}\sup_{\xi\in\widehat{G}}|\widehat{f}(\xi)|,$

and hence there exists $\xi\in\widehat{G}$ such that

$|\mathbb{E}_{z\in B^{\prime}}(f(z)e(-\xi\cdot z))|\geqslant|\mathbb{E}_{z\in
B^{\prime},x\in
B}(f(z){\mathbf{b}}_{1}(x){\mathbf{b}}_{2}(z+x))|\frac{\mathbb{E}(1_{B})}{\mathbb{E}(1_{B+B^{\prime}})}.$

The claim follows.

##  5\. An argument of Gowers

We now begin the proofs of the inverse theorems in Theorem 2.3 and Theorem
2.7. As we shall see, the arguments shall be analogous to those used to prove
Lemma 3.1, and closely follow the treatment in Gowers [25]. The first part of
the argument is to establish a “phase derivative” $h\to\xi_{h}$ for the
function $f$ and to establish some additivity properties on this phase
derivative. These arguments apply to arbitrary finite additive groups $G$;
later on we shall treat the finite field case separately.

######  Proposition 5.1 (Large $U^{3}$ norm gives many additive quadruples
[25]).

Let $G$ be an arbitrary finite additive group, and let $f:G\to\mathcal{D}$ be
a bounded function such that $\|f\|_{U^{3}(G)}\geqslant\eta$ for some
$\eta>0$. Then there exists a set $H\subseteq G$, and a function
$\xi:H\to\widehat{G}$ whose graph $\Gamma:=\\{(h,\xi_{h}):h\in H\\}\subseteq
G\times\widehat{G}$ obeys the estimate

$|\\{(z_{1},z_{2},z_{3},z_{4})\in\Gamma:z_{1}+z_{2}=z_{3}+z_{4}\\}|\geqslant
2^{-8}\eta^{64}N^{3}.$ (5.1)

Furthermore for each $(h,\xi_{h})\in\Gamma$ we have

$|\mathbb{E}_{x}T^{h}f(x)\overline{f}(x)e(-\xi_{h}\cdot
x)|\geqslant\eta^{4}/2^{1/2}.$

Proof.  As we shall see, this proposition corresponds fairly closely with the
first part of the proof of Lemma 3.1 (up to (3.6)). From (1.1) we have

$\mathbb{E}_{h\in G}\|T^{h}f\overline{f}\|_{U^{2}(G)}^{4}\geqslant\eta^{8}.$

Applying Proposition 2.2 we conclude that

$\mathbb{E}_{h\in G}\|T^{h}f\overline{f}\|_{u^{2}(G)}^{2}\geqslant\eta^{8}.$

Thus if we let

$H:=\\{h\in G:\|T^{h}f\overline{f}\|_{u^{2}(G)}^{2}\geqslant\eta^{8}/2\\}$

then we have

$\mathbb{E}_{h\in G}\|T^{h}f\overline{f}\|_{u^{2}(G)}^{2}1_{G\backslash
H}(h)\geqslant\eta^{8}/2$

and hence

$\mathbb{E}_{h\in
G}\|T^{h}f\overline{f}\|_{u^{2}(G)}^{2}1_{H}(h)\geqslant\eta^{8}/2.$

In particular we have

$\mathbb{E}(1_{H})\geqslant\eta^{8}/2.$ (5.2)

By (2.5) and definition of $H$, we can find a map $h\mapsto\xi_{h}$ from $H$
to $\widehat{G}$ such that

$|\mathbb{E}_{x}T^{h}f(x)\overline{f}(x)e(-\xi_{h}\cdot
x)|\geqslant\eta^{4}/2^{1/2}\hbox{ for all }h\in H.$ (5.3)

Let us fix this map $h\mapsto\xi_{h}$. We square sum the above expression in
$h$ and use (5.2) to conclude

$\mathbb{E}_{h}|\mathbb{E}_{x}T^{h}f(x)\overline{f}(x)e(-\xi_{h}\cdot
x)|^{2}1_{H}(h)\geqslant\eta^{16}/4.$

But from the identity

$|\mathbb{E}_{x}T^{h}f(x)\overline{f}(x)e(-\xi_{h}\cdot
x)|^{2}=\mathbb{E}_{x,k}T^{k}(T^{h}f)(x)\overline{T^{h}f}(x)\overline{T^{k}f(x)}f(x)e(\xi_{h}\cdot
k)$

we conclude

$|\mathbb{E}_{x,h,k}T^{k}(T^{h}f)(x)\overline{T^{h}f}(x)e(\xi_{h}\cdot
k)1_{H}(h)\overline{T^{k}f(x)}f(x)|\geqslant\eta^{16}/4.$ (5.4)

At this point we suppress the explicit mention of the functions $f$ and write
this simply as

$|\mathbb{E}_{x,h,k\in G}({\mathbf{b}}(x+h,k)1_{H}(h)e(\xi_{h}\cdot
k){\mathbf{b}}(x,k))|\geqslant\eta^{16}/4.$

Applying (4.1) to eliminate the ${\mathbf{b}}(x,k)$ factor, we conclude

$\mathbb{E}_{h,h_{1},x,k}{\mathbf{b}}(x+h+h_{1},k){\mathbf{b}}(x+h,k)e((h_{1}\cdot\nabla_{h})\xi_{h}\cdot
k)1_{H}(h+h_{1})1_{H}(h)\geqslant\eta^{32}/16.$ (5.5)

Making the substitution $y=x+h$, we obtain

$\mathbb{E}_{h,y,h_{1},k}e((h_{1}\cdot\nabla_{h})\xi_{h}\cdot
k)1_{H}(h+h_{1})1_{H}(h){\mathbf{b}}(y,h_{1},k)\geqslant\eta^{32}/16.$ (5.6)

Applying (4.1) again we conclude

$\mathbb{E}_{h,h_{1},h_{2},y,k}e((h_{2}\cdot\nabla_{h})(h_{1}\cdot\nabla_{h})\xi_{h}\cdot
k)1_{H}(h+h_{1}+h_{2})1_{H}(h+h_{2})1_{H}(h+h_{1})1_{H}(h)\geqslant
2^{-28}\eta^{64}.$ (5.7)

Summing this in $k$ using the Fourier inversion formula, and discarding the
irrelevant $y$ averaging, we infer

$\mathbb{E}_{h,h_{1},h_{2}}1_{(h_{2}\cdot\nabla_{h})(h_{1}\cdot\nabla_{h})\xi_{h}=0}1_{H}(h+h_{1}+h_{2})1_{H}(h+h_{2})1_{H}(h+h_{1})1_{H}(h)\geqslant\eta^{64}/256.$
(5.8)

The claim now follows by substituting $z_{1}:=(h,\xi_{h})$,
$z_{2}:=(h+h_{1},\xi_{h+h_{1}})$, $z_{3}:=(h+h_{2},\xi_{h+h_{2}})$, and
$z_{4}:=(h+h_{1}+h_{2},\xi_{h+h_{1}+h_{2}})$.

As remarked, the analogy between this argument and the first part of the proof
of Lemma 3.1 is very close. In particular equations (5.3), (5.4), (5.5),
(5.6), (5.7) and (5.8) are analogues of (3.1), (3.2), (3.3), (3.4), (3.5) and
(3.6) respectively.

In order to exploit the conclusion (5.1), we require two very useful results
from additive combinatorics. The first result asserts that a set
$\Gamma^{\prime}$ with some partial additive structure (in the sense that it
contains many additive quadruples) can be refined to have a more complete
additive structure (in the sense that its sum set is small). This type of
result was first obtained by Balog and Szemerédi [1], but with very weak
constants. A version of the theorem with polynomial dependencies between the
constants was obtained by Gowers [25]. The version we quote below, with rather
good powers in those polynomials, may be proved by a careful working of the
argument in Chang [13]. Of course for the purposes of this paper the precise
values of the constants are somewhat unimportant.

Write
$\Gamma^{\prime}-\Gamma^{\prime}:=\\{z-z^{\prime}:z,z^{\prime}\in\Gamma^{\prime}\\}$
for the difference set of $\Gamma^{\prime}$.

######  Theorem 5.2 (Balog-Szemerédi-Gowers theorem [13]).

Let $G$ be an additive group, and let $\Gamma$ be a finite non-empty subset of
$G$ such that

$|\\{(z_{1},z_{2},z_{3},z_{4})\in\Gamma:z_{1}+z_{2}=z_{3}+z_{4}\\}|\geqslant|\Gamma|^{3}/K$

for some $K\geqslant 1$. Then there exists a subset
$\Gamma^{\prime}\subseteq\Gamma$ such that

$|\Gamma^{\prime}|\geqslant 2^{-6}K^{-1}|\Gamma|\hbox{ and
}|\Gamma^{\prime}-\Gamma^{\prime}|\leqslant 2^{42}K^{6}|\Gamma^{\prime}|.$

The other tool we need is the Plünnecke inequality, a simple proof888Actually,
since we only need this theorem for bounded $k,l$, and would not be concerned
if the bound of $K^{k+l}$ were worsened to $K^{C(k+l)}$ for some absolute
constant $C$, it is possible to modify the proof of Theorem 5.2 in order to
gain control on $|k\Gamma^{\prime}-l\Gamma^{\prime}|$ directly, without
needing the Plünnecke inequalities. However this would not simplify the
remainder of the argument and so we do not give the details of this alternate
approach here. of which can be found in [55].

######  Theorem 5.3 (Plünnecke inequalities [50, 55]).

Let $G$ be an arbitrary additive group, and let $\Gamma^{\prime}$ be a finite
non-empty subset of $G$ such that $|\Gamma^{\prime}-\Gamma^{\prime}|\leqslant
K|\Gamma^{\prime}|$ for some $K\geqslant 1$. Then we have
$|k\Gamma^{\prime}-l\Gamma^{\prime}|\leqslant K^{k+l}|\Gamma^{\prime}|$ for
all $k,l\geqslant 1$, where $k\Gamma^{\prime}$ denotes the $k$-fold sumset of
$\Gamma^{\prime}$.

In our applications the integers $k,l$ will be quite small, in fact they will
not exceed 9. Combining Proposition 5.1 with Theorem 5.2 and Theorem 5.3, we
conclude

######  Proposition 5.4 ($h\mapsto\xi_{h}$ is nearly affine-linear).

Let $G$ be an arbitrary finite additive group, and let $f:G\to\mathcal{D}$ be
a bounded function such that $\|f\|_{U^{3}(G)}\geqslant\eta$ for some
$\eta>0$. Then there exists a set $H^{\prime}\subseteq G$ a function
$\xi:H^{\prime}\to\widehat{G}$ whose graph
$\Gamma^{\prime}:=\\{(h,\xi_{h}):h\in H^{\prime}\\}\subseteq
G\times\widehat{G}$ obeys the estimates

$|\Gamma^{\prime}|\geqslant 2^{-14}\eta^{64}N$ (5.9)

and

$|k\Gamma^{\prime}-l\Gamma^{\prime}|\leqslant(2^{90}\eta^{-384})^{k+l}|\Gamma^{\prime}|\hbox{
for all }k,l\geqslant 1.$

Furthermore for each $(h,\xi_{h})\in\Gamma^{\prime}$ we have

$|\mathbb{E}_{x\in G}(T^{h}f(x)\overline{f(x)}e(-\xi_{h}\cdot
x))|\geqslant\eta^{4}/2.$ (5.10)

Thus far we have not used anything about the underlying group $G$ other than
it is finite and abelian. We could continue doing this, proving Theorem 2.7
and extracting Theorem 2.3 as a corollary. However for expository reasons we
will now restrict to the finite field geometry case $G=\mathbb{F}_{5}^{n}$ and
give a complete proof of Theorem 2.3. The arguments there serve as a
simplified model which will help motivate the general case.

##  6\. The finite field case

We now restrict attention to a finite field geometry setting
$G=\mathbb{F}_{5}^{n}$, and prove Theorem 2.3 (i). In this section, then,
$N=5^{n}$. Thanks to Proposition 5.4, we have already isolated a phase
derivative $h\mapsto\xi_{h}$ which exhibits some linear behavior. The first
step (following Gowers [25, 27]) is to show that $\xi$ in fact matches up with
a linear phase function on a large subspace; then we shall show that in fact
$\xi$ matches up with a _self-adjoint_ linear phase function on a large
subspace (this is the substantially new part of the argument). Finally, we
shall again follow Gowers [25] and conjugate $f$ by a quadratic phase to
eliminate this linear phase derivative and conclude the argument.

Step 1: Linearization of phase derivative. In this subsection we establish

######  Proposition 6.1 (Graphs have large linear component [25, 27]).

Let $H^{\prime}\subseteq\mathbb{F}_{5}^{n}$, and let
$\xi:H^{\prime}\to(\mathbb{F}_{5}^{n})^{*}$ be a function whose graph
$\Gamma^{\prime}:=\\{(h,\xi_{h}):h\in
H^{\prime}\\}\subseteq\mathbb{F}_{5}^{n}\times(\mathbb{F}_{5}^{n})^{*}$ obeys
the estimates

$K^{-1}N\leqslant|\Gamma^{\prime}|\leqslant|9\Gamma^{\prime}-8\Gamma^{\prime}|\leqslant
KN$ (6.1)

for some $K\geqslant 1$. Then there exists a linear subspace
$V\leqslant\mathbb{F}_{5}^{n}$ with the codimension bound

$n-\dim(V)\leqslant(2K)^{6}$

and a translate $x_{0}+V$ of this subspace, together with a linear
transformation $M:V\to(\mathbb{F}_{5}^{n})^{*}$ and an element
$\xi_{0}\in(\mathbb{F}_{5}^{n})^{*}$ such that

$\mathbb{E}_{h\in
V}(1_{H}(x_{0}+h)1_{\xi_{x_{0}+h}=2Mh+\xi_{0}})\geqslant(2K)^{-4}.$ (6.2)

Proof.  Note that while $\Gamma^{\prime}$ is a graph, the slightly larger sets
$k\Gamma^{\prime}-l\Gamma^{\prime}$ need not be a graph. The next lemma shows
that this can be rectified by passing to an appropriate subset
$\Gamma^{\prime\prime}\subseteq\Gamma^{\prime}$.

######  Lemma 6.2.

There exists a subset $\Gamma^{\prime\prime}$ of $\Gamma^{\prime}$ with

$|\Gamma^{\prime\prime}|\geqslant N/5K^{3}$ (6.3)

such that $4\Gamma^{\prime\prime}-4\Gamma^{\prime\prime}$ is a graph.

Remarks. When $G=\mathbb{Z}/N\mathbb{Z}$ is a cyclic group of prime order,
this lemma is essentially [27, Lemma 7.5], and our arguments both here and in
§9 are in a similar spirit. Curiously, the argument of [27] uses the fact that
$\mathbb{Z}/N\mathbb{Z}$ is a field, and so this is a rare instance of the
cyclic group case being somewhat easier than the general group case. The
conclusion can also be rephrased as an assertion that the map
$h\mapsto\xi_{h}$ is a _Freiman $8$-homomorphism_ on $H^{\prime\prime}$.

Proof.  Let $A\subseteq(\mathbb{F}_{5}^{n})^{*}$ be the set of all $\xi$ such
that $(0,\xi)\in 8\Gamma^{\prime}-8\Gamma^{\prime}$. Observe that since
$\Gamma^{\prime}$ is a graph, we have
$|\Gamma^{\prime}+A|=|\Gamma^{\prime}||A|$. On the other hand,
$\Gamma^{\prime}+A$ is contained in $9\Gamma^{\prime}-8\Gamma^{\prime}$.
Applying (6.1), we conclude that $|A|\leqslant K^{2}$. Now let
$m=\lceil\log_{5}|A|\rceil$, and let
$\Psi:(\mathbb{F}_{5}^{n})^{*}\to\mathbb{F}_{5}^{m}$ be a randomly chosen
linear transformation from $(\mathbb{F}_{5}^{n})^{*}$ to $\mathbb{F}^{m}$.
Observe that for each non-zero $\xi\in A$, we have $\Psi(\xi)\neq 0$ with
probability at least $1-5^{-m}$. Thus we see that with non-zero probability
$\Psi$ is non-zero on all of $A\backslash\\{0\\}$.

Fix $\Psi$ with the above properties, and let $c$ be a randomly selected point
in $\mathbb{F}^{m}$, and define
$\Gamma^{\prime\prime}:=\\{(h,\xi_{h})\in\Gamma^{\prime}:\Psi(\xi_{h})=c\\}$.
Then the expected size of $|\Gamma^{\prime\prime}|$ is at least
$|\Gamma^{\prime}|/5^{m}\geqslant N/5K^{2}$. Also, observe that if $(0,\xi)$
lies in $8\Gamma^{\prime\prime}-8\Gamma^{\prime\prime}$ then $\xi$ lies in $A$
and (by linearity of $\Psi$) $\Psi(\xi)=0$, hence $\xi=0$. Since
$8\Gamma^{\prime\prime}-8\Gamma^{\prime\prime}$ is the difference set of
$4\Gamma^{\prime\prime}-4\Gamma^{\prime\prime}$, this implies that
$4\Gamma^{\prime\prime}-4\Gamma^{\prime\prime}$ is a graph. The claim follows.

Define $H^{\prime\prime}$ by $\Gamma^{\prime\prime}:=\\{(h,\xi_{h}):h\in
H^{\prime\prime}\\}$. Now we use a result of Bogolyubov [7] (which we shall
also utilize later in this paper) to obtain some control on the set
$2H^{\prime\prime}-2H^{\prime\prime}$.

######  Lemma 6.3 (Bogolyubov lemma [7]).

Let $A$ be a subset of a finite additive group $G$ such that
$|A|\geqslant\delta|G|$. Then there exists a set $S\subseteq\widehat{G}$ with
$|S|\leqslant 2\delta^{-2}$ such that $B(S,\frac{1}{4})\subseteq 2A-2A$.

Remark. Somewhat sharper versions of this lemma are known, see [12], but we
will not need these here.

Proof.  From Fourier inversion we have

$1_{A}(x)=\sum_{\xi\in\widehat{G}}\widehat{1}_{A}(\xi)e(\xi\cdot x).$

Convolving this with itself four times, we obtain

$1_{A}*1_{A}*1_{-A}*1_{-A}(x)=\sum_{\xi\in
G}|\widehat{1}_{A}(\xi)|^{4}e(\xi\cdot x)$

where $f*g(x):=\mathbb{E}_{y}f(y)g(x-y)$ is the normalized convolution
operation. Since the left-hand side is only non-zero on $2A-2A$, we conclude
that

$\\{x\in G:\Re\sum_{\xi\in G}|\widehat{1}_{A}(\xi)|^{4}e(\xi\cdot
x)>0\\}\subseteq 2A-2A.$

Let us now study the sum on the left-hand side. Let $0<\alpha<\delta$ be a
parameter to be chosen later, and let $S:=\\{\xi\in
G:|\widehat{1}_{A}(\xi)|\geqslant\alpha\\}$ denote the large Fourier
coefficients of $A$. Since $\alpha<\mathbb{E}(1_{A})$, we have $0\in S$. Also,
from the Plancherel identity

$\sum_{\xi\in G}|\widehat{1}_{A}(\xi)|^{2}=\mathbb{E}(1_{A})\geqslant\delta$

and Chebyshev’s inequality we have an upper bound on the cardinality of $S$:

$|S|\leqslant\delta/\alpha^{2}.$

Now suppose that $x\in B(S,\frac{1}{4})$. Then we have $\cos(2\pi\xi\cdot
x)\geqslant 0$ for all $\xi\in S$. Thus

$\displaystyle\Re\sum_{\xi\in G}|\widehat{1}_{A}(\xi)|^{4}e(\xi\cdot x)$
$\displaystyle=\sum_{\xi\in S}|\widehat{1}_{A}(\xi)|^{4}\cos(2\pi\xi\cdot
x)+\sum_{\xi\not\in S}|\widehat{1}_{A}(\xi)|^{4}\cos(2\pi i\xi\cdot x)$
$\displaystyle\geqslant|\widehat{1}_{A}(0)|^{4}-\sum_{\xi\not\in
S}|\widehat{1}_{A}(\xi)|^{4}$ $\displaystyle\geqslant\delta^{4}-\sum_{\xi\in
G}\alpha^{2}|\widehat{1}_{A}(\xi)|^{2}$
$\displaystyle\geqslant\delta^{4}-\alpha^{2}\delta$

by another application of Plancherel’s theorem. Thus if we set
$\alpha:=\delta^{3/2}/\sqrt{2}$ (for instance), the claim follows.

We apply Lemma 6.3 with $G=\mathbb{F}_{5}^{n}$ and $A=H^{\prime\prime}$, the
set coming from Lemma 6.2. The set $S$ we produce satisfies $|S|\leqslant
50K^{6}$. Let $V\subseteq\mathbb{F}_{5}^{n}$ be the subspace
$V:=\\{x\in\mathbb{F}_{5}^{n+m}:x\cdot\xi=0\hbox{ for all }\xi\in S\\}$. Then
by linear algebra we have

$\dim(V)\geqslant n-|S|\geqslant n-50K^{6}$ (6.4)

and, since clearly $V\subseteq B(S,\frac{1}{4})$, we have

$V\subseteq 2H^{\prime\prime}-2H^{\prime\prime}.$

Thus there exists a map $M:V\to\widehat{G}$ such that

$Z:=\\{(h,2Mh):h\in V\\}$

is a subset of $2\Gamma^{\prime\prime}-2\Gamma^{\prime\prime}$; since
$2\Gamma^{\prime\prime}-2\Gamma^{\prime\prime}$ is a graph and contains the
origin, we have $M0=0$. Also, since
$4\Gamma^{\prime\prime}-4\Gamma^{\prime\prime}$ is a graph and $V$ is closed
under addition, we see that $M(h+h^{\prime})=Mh+Mh^{\prime}$ for all
$h,h^{\prime}\in V$, thus $M$ is linear.

Consider the set $Z+\Gamma^{\prime\prime}$. On one hand, this set can be
foliated into (say) $L$ disjoint cosets of the linear space $Z$. On the other
hand, it is contained in $3\Gamma^{\prime\prime}-2\Gamma^{\prime\prime}$, and

$|3\Gamma^{\prime\prime}-2\Gamma^{\prime\prime}|\leqslant|9\Gamma^{\prime}-8\Gamma^{\prime}|\leqslant
KN.$

This gives the bound $|Z|\leqslant KN/L$. Since $Z+\Gamma^{\prime\prime}$ also
contains $\Gamma^{\prime\prime}$, we thus see from the pigeonhole principle
and (6.3) that there exists a coset $(x_{0},\xi_{0})+Z$ of $Z$ such that

$|\Gamma^{\prime\prime}\cap((x_{0},\xi_{0})+Z)|\geqslant|Z|/5K^{4}.$

Since $\dim(Z)=\dim(V)\geqslant n-50K^{6}$, the claim (6.2) follows.

Combining Proposition 6.1 with Proposition 5.4, we quickly conclude the
following proposition.

######  Proposition 6.4 (Large $U^{3}(\mathbb{F}_{5}^{n})$ gives linear phase
derivative).

Let $G=\mathbb{F}_{5}^{n}$, and let $f:G\to\mathcal{D}$ be a bounded function
such that $\|f\|_{U^{3}(G)}\geqslant\eta$ for some $\eta>0$. Then there exists
a linear subspace $V$ of $G$ with the codimension bound

$n-\dim(V)\leqslant 2^{C_{1}}\eta^{-C_{1}^{\prime}}$ (6.5)

and a translate $x_{0}+V$ of this subspace, together with a linear
transformation $M:V\to\widehat{G}$ and an element $\xi_{0}\in\widehat{G}$ such
that

$\mathbb{E}_{h\in V}|\mathbb{E}_{x\in
G}T^{x_{0}+h}f(x)\overline{f(x)}e(-(2Mh+\xi_{0})\cdot x)|\geqslant
2^{-C_{2}}\eta^{C^{\prime}_{2}}.$ (6.6)

It is permissible to take $C_{i},C^{\prime}_{i}=2^{16}$ for $i=1,2$.

Step 2: The symmetry argument. We now establish some symmetry properties on
$M$, closely following the argument in Lemma 3.1. As we shall be focusing more
on $M$ than on $f$ in this step, we shall suppress the terms involving $f$
(and $\xi_{0}$ and $x_{0}$) using the ${\mathbf{b}}$ notation. Indeed from
(6.6) we have

$|\mathbb{E}_{x\in G,h\in
V}{\mathbf{b}}(x+h){\mathbf{b}}(x){\mathbf{b}}(h)e(-2Mh\cdot x)|\geqslant
2^{-C_{2}}\eta^{C^{\prime}_{2}}$ (6.7)

Once again we use Cauchy-Schwarz and similar tools to eliminate all the
bounded functions. By Lemma 4.1 there exists $x_{1}\in G$ such that

$|\mathbb{E}_{x,h\in
V}{\mathbf{b}}(x+x_{1}+h){\mathbf{b}}(x+x_{1}){\mathbf{b}}(h)e(-2Mh\cdot(x+x_{1}))|\geqslant
2^{-C_{2}}\eta^{C^{\prime}_{2}},$ (6.8)

which after redefining the bounded functions to absorb the $x_{1}$ terms
implies that

$|\mathbb{E}_{x,h\in
V}{\mathbf{b}}(x+h){\mathbf{b}}(x){\mathbf{b}}(h)e(-2Mh\cdot x)|\geqslant
2^{-C_{2}}\eta^{C^{\prime}_{2}}.$ (6.9)

Applying Cauchy-Schwarz (Lemma 4.3) to eliminate ${\mathbf{b}}(h)$, we see
that

$|\mathbb{E}_{x,y,h\in
V}{\mathbf{b}}(y+h){\mathbf{b}}(y+h){\mathbf{b}}(x+h){\mathbf{b}}(x)e(-2Mh\cdot(y-x))|\geqslant
2^{-2C_{2}}\eta^{2C^{\prime}_{2}};$ (6.10)

Making the substitution $z=x+y+h$, this becomes

$|\mathbb{E}_{x,y,z\in
V}{\mathbf{b}}(z,y){\mathbf{b}}(z,x)e(-2M(z-x-y)\cdot(y-x))|\geqslant
2^{-2C_{2}}\eta^{2C^{\prime}_{2}};$ (6.11)

Absorbing as many phase terms into the functions ${\mathbf{b}}$ as we can, we
infer

$|\mathbb{E}_{x,y,z\in
V}{\mathbf{b}}(z,y){\mathbf{b}}(z,x)e(2\\{x,y\\})|\geqslant
2^{-2C_{2}}\eta^{2C^{\prime}_{2}},$ (6.12)

where $\\{x,y\\}$ is the anti-symmetric form defined in (3.13), that is to say
$\\{x,y\\}=Mx\cdot y-My\cdot x$. By the pigeonhole principle in $z$ we
conclude that

$|\mathbb{E}_{x,y\in V}{\mathbf{b}}(y){\mathbf{b}}(x)e(2\\{x,y\\})|\geqslant
2^{-2C_{2}}\eta^{2C^{\prime}_{2}}$ (6.13)

for some bounded functions ${\mathbf{b}}(y)$, ${\mathbf{b}}(x)$. Applying
Cauchy-Schwarz again to eliminate the ${\mathbf{b}}(x)$ factor, we deduce that

$|\mathbb{E}_{x,y,y^{\prime}\in
V}{\mathbf{b}}(y){\mathbf{b}}(y^{\prime})e(2\\{x,y^{\prime}-y\\})|\geqslant
2^{-4C_{2}}\eta^{4C^{\prime}_{2}}.$ (6.14)

By the triangle inequality we obtain

$\mathbb{E}_{y,y^{\prime}\in V}|\mathbb{E}_{x\in
V}e(2\\{x,y^{\prime}-y\\})|\geqslant 2^{-4C_{2}}\eta^{4C^{\prime}_{2}};$
(6.15)

Making the substitution $h=y^{\prime}-y$ we conclude

$\mathbb{E}_{h\in V}|\mathbb{E}_{x\in V}e(2\\{x,h\\})|\geqslant
2^{-4C_{2}}\eta^{4C^{\prime}_{2}}.$ (6.16)

The map $x\mapsto 2\\{x,h\\}$ is a homomorphism from $V$ to
$\mathbb{R}/\mathbb{Z}$. Thus if we write

$W:=\\{h\in V:\\{x,h\\}=0\hbox{ for all }x\in V\\}$

then $W$ is a linear subspace of $V$ and

$\mathbb{E}_{x\in V}e(2\\{x,h\\})=1_{W}(h).$

Thus, in view of (6.16), we see that $W$ is extremely large relative to $V$:

$|W|/|V|=\mathbb{E}_{y,h\in V}1_{W}(h)\geqslant
2^{-4C_{2}}\eta^{4C^{\prime}_{2}}.$

In particular, from (6.5) we have

$n-\dim(W)\leqslant
2^{C_{1}}\eta^{-C^{\prime}_{1}}+4C^{\prime}_{2}\log_{5}(2/\eta)+4C_{2}\log_{5}2\leqslant
2^{C_{1}+1}\eta^{-C^{\prime}_{1}}.$

By construction of $W$ we see that $M$ is self-adjoint on $W$, that is to say

$Mw\cdot w^{\prime}=Mw^{\prime}\cdot w\hbox{ for all }w,w^{\prime}\in W.$
(6.17)

Let us remark that the analogy between this argument and that of §3 is
exceptionally close. The seven equations (3.9), (3.10), (3.11), (3.12),
(3.14), (3.15) and (3.16) are analogues of (6.9), (6.10), (6.11), (6.12),
(6.13), (6.14) and (6.15) respectively.

Step 3: Eliminating the quadratic phase component. We now give the final part
of the proof of Theorem 2.3, which also follows the proof of Lemma 3.1
closely. We return to (6.6), which we write as

$|\mathbb{E}_{x\in G;h\in
V}{\mathbf{b}}(h){\mathbf{b}}(x+h)\overline{f(x)}e(-2Mh\cdot x)|\geqslant
2^{-C_{2}}\eta^{C^{\prime}_{2}},$

where we have distributed the phase factor $e(-\xi_{0}\cdot
x)=e(-\xi_{0}\cdot(x+h))e(\xi_{0}\cdot h)$ among the functions ${\mathbf{b}}$.
Here the focus will be on the $\overline{f(x)}$ factor, the aim being to
demonstrate that this function exhibits some quadratic bias. We first observe
that the simple averaging argument of Lemma 4.1 allows us to find
$h^{\prime}\in V$ such that

$|\mathbb{E}_{x\in G;h\in
W}{\mathbf{b}}(h+h^{\prime}){\mathbf{b}}(x+h+h^{\prime})\overline{f(x)}e(-2M(h+h^{\prime})\cdot
x)|\geqslant 2^{-C_{2}}\eta^{C^{\prime}_{2}}.$

Once again we can absorb $e(-2Mh^{\prime}\cdot x)$ into the functions
${\mathbf{b}}$, and conclude that

$|\mathbb{E}_{x\in G;h\in
W}{\mathbf{b}}(h){\mathbf{b}}(x+h)\overline{f(x)}e(-2Mh\cdot x)|\geqslant
2^{C_{2}}\eta^{C^{\prime}_{2}},$

which implies that

$|\mathbb{E}_{y\in G;x,h\in
W}{\mathbf{b}}(h){\mathbf{b}}(x+h+y)\overline{f(x+y)}e(-2Mh\cdot(x+y))|\geqslant
2^{C_{2}}\eta^{-C^{\prime}_{2}}.;$

Using the triangle inequality we deduce

$\mathbb{E}_{y\in G}|\mathbb{E}_{x,h\in
W}{\mathbf{b}}(h,y){\mathbf{b}}(x+h,y)\overline{f(x+y)}e(-2Mh\cdot
x)|\geqslant 2^{C_{2}}\eta^{-C^{\prime}_{2}}.$ (6.18)

Now we observe from (6.17) that we have the identity

$2Mh\cdot x=M(x+h)\cdot(x+h)-Mx\cdot x-Mh\cdot h,$

and hence

$e(-2Mh\cdot x)={\mathbf{b}}(x+h){\mathbf{b}}(h)e(Mx\cdot x).$

Therefore (6.18) implies that

$\mathbb{E}_{y\in G}|\mathbb{E}_{x,h\in
W}{\mathbf{b}}(h,y){\mathbf{b}}(x+h,y)\overline{f(x+y)}e(-Mx\cdot x)|\geqslant
2^{-C_{2}}\eta^{C^{\prime}_{2}}.$

Applying Lemma 4.4 for each $y\in G$ separately and with $B=B^{\prime}=W$, we
conclude that

$\mathbb{E}_{y\in G}\|\overline{f(x+y)}e(Mx\cdot x)\|_{u^{2}(W)}\geqslant
2^{-C_{2}}\eta^{C^{\prime}_{2}},$

and hence of course

$\mathbb{E}_{y\in G}\|\overline{f(x+y)}e(Mx\cdot x)\|_{u^{3}(W)}\geqslant
2^{-C_{2}}\eta^{C^{\prime}_{2}}.$

But the $u^{3}(W)$ norm is invariant under quadratic phase modulations,
conjugation, and translation, and so we have

$\mathbb{E}_{y\in G}\|f\|_{u^{3}(y+W)}\geqslant
2^{-C_{2}}\eta^{C^{\prime}_{2}}$

which gives (2.6).

##  7\. Application: Szemerédi’s theorem in finite field geometries

As a sample application of Theorem 2.3, we can now prove a quantitative
Szemerédi theorem for progressions of length four in $\mathbb{F}_{5}^{n}$. If
$G$ is any finite abelian group of order $N$, where $(6,N)=1$, we define
$r_{4}(G)$ to be the cardinality of the largest set $A\subseteq G$ which does
not contain four distinct elements in arithmetic progression.

######  Theorem 7.1 (Szemerédi theorem for $r_{4}(\mathbb{F}_{5}^{n})$).

Write $N=5^{n}$. Then we have the bound

$r_{4}(\mathbb{F}_{5}^{n})\ll N(\log\log N)^{-2^{-21}}.$

Remark. In §11 below we will prove a similar result for an arbitrary $G$.
Although that result will supersede the present one, the proof is quite a bit
more complicated, and so we give the finite field argument separately now. In
[35] we improve the bound to $r_{4}(\mathbb{F}_{5}^{n})\ll N(\log N)^{-c}$
using substantially lengthier arguments.

As with all analytic arguments for proving Szemerédi type theorems, the key
step is the establishment of the following “density increment” result.

######  Proposition 7.2.

Let $\delta>0$, suppose that

$n>6(2/\delta)^{2^{20}},$ (7.1)

and let $A\subseteq\mathbb{F}_{5}^{n}$ be a set with size at least $\delta N$.
Suppose that $A$ contains no four-term arithmetic progressions. Then we can
find an affine subspace $x_{0}+V$ of $\mathbb{F}_{5}^{n}$ with dimension
$\dim(V)\geqslant n/3$ such that we have the density increment

$\mathbb{E}_{x\in
x_{0}+V}1_{A}(x)\geqslant\mathbb{E}_{x\in\mathbb{F}_{5}^{n}}1_{A}(x)+(\delta/2)^{2^{20}}.$

Proof.  Write

$\alpha:=\mathbb{E}_{x\in\mathbb{F}_{5}^{n}}1_{A}(x)=|A|/N.$

By Corollary 1.8 and the lower bound $N\geqslant 2/\delta^{3}$ (which is very
much a consequence of (7.1)!) we conclude that

$\|1_{A}-\alpha\|_{U^{3}(\mathbb{F}_{5}^{n})}\geqslant\delta^{3}/8.$

Applying Theorem 2.3, we can thus find a subspace
$W\leqslant\mathbb{F}_{5}^{n}$ with codimension at most $(2/\delta)^{4C}$ and
quadratic phase functions $\phi_{y}$ for each $y\in\mathbb{F}_{5}^{n}$ such
that

$\mathbb{E}_{y\in\mathbb{F}_{5}^{n}}\big{|}\mathbb{E}_{x\in
y+W}(1_{A}(x)-\alpha)e(-\phi_{y}(x))\big{|}\geqslant(\delta/2)^{4C}.$ (7.2)

On the other hand, we may assume that

$\mathbb{E}_{x\in
y+W}(1_{A}(x)-\alpha)<\textstyle\frac{1}{4}\displaystyle(\delta/2)^{4C}$

for all $y\in\mathbb{F}_{5}^{n}$, since the proposition is immediate
otherwise. Now since $\mathbb{E}_{x\in y+W}(1_{A}(x)-\alpha)$ has mean zero,
we thus conclude that

$\mathbb{E}_{y\in\mathbb{F}_{5}^{n}}\big{|}\mathbb{E}_{x\in
y+W}(1_{A}(x)-\alpha)\big{|}<\textstyle\frac{1}{2}\displaystyle(\delta/2)^{4C}.$

Subtracting this from (7.2) and using the pigeonhole principle, we infer that
there exists $y\in\mathbb{F}_{5}^{n}$ such that

$\big{|}\mathbb{E}_{x\in
y+W}(1_{A}(x)-\alpha)e(-\phi_{y}(x))\big{|}>\textstyle\frac{1}{2}\displaystyle(\delta/2)^{4C}+\big{|}\mathbb{E}_{x\in
y+W}(1_{A}(x)-\alpha)\big{|}.$

Now observe (using Lemma 3.1) that $\phi_{y}$ takes values in the set
$T=\\{0,\frac{1}{5},\frac{2}{5},\frac{3}{5},\frac{4}{5}\\}$. For each $t\in T$
let $S_{t}$ be the quadratic surface $S_{t}:=\\{x\in y+W:\phi_{y}(x)=t\\}$.
Then by the triangle inequality we have

$\big{|}\mathbb{E}_{x\in
y+W}(1_{A}(x)-\alpha)e(-\phi_{y}(x))\big{|}\leqslant\sum_{t\in
T}\big{|}\mathbb{E}_{x\in y+W}(1_{A}(x)-\alpha)1_{S_{t}}(x)\big{|}$

whilst

$\big{|}\mathbb{E}_{x\in
y+W}(1_{A}(x)-\alpha)\big{|}\geqslant-\mathbb{E}_{x\in
y+W}(1_{A}(x)-\alpha)=-\sum_{t\in T}\mathbb{E}_{x\in
y+W}(1_{A}(x)-\alpha)1_{S_{t}}(x).$

Combining these estimates, and using the pigeonhole principle, we deduce that
there exists $t\in T$ such that

$\big{|}\mathbb{E}_{x\in
y+W}(1_{A}(x)-\alpha)1_{S_{t}}(x)\big{|}>\textstyle\frac{1}{2}\displaystyle(\delta/2)^{4C}\mathbb{E}_{x\in
y+W}1_{S_{t}}(x)-\mathbb{E}_{x\in y+W}(1_{A}(x)-\alpha)1_{S_{t}}(x),$

and hence

$\mathbb{E}_{x\in
y+W}(1_{A}(x)-\alpha)1_{S_{t}}(x)\geqslant\textstyle\frac{1}{4}\displaystyle(\delta/2)^{4C}\mathbb{E}_{x\in
y+W}1_{S_{t}}(x).$ (7.3)

This gives a density increment on a quite large quadratic hypersurface
$S_{t}\cap(y+W)$. Our job is now to convert this into a density increment on a
subspace. Observe from Lemma 3.1 that we can write $S_{t}\cap(y+W)$ in the
form

$S_{t}\cap(y+W)=y+\\{x\in W:\textstyle\frac{1}{2}\displaystyle x\cdot
Mx+v\cdot x=c\\}$

for some self-adjoint linear transformation $M:W\to\widehat{W}$, some $v\in
W^{*}$, and some $c\in F$. We now locate a large subspace on which $M$ is
degenerate. To this end we need a simple lemma999One could also proceed here
using the theory of Witt groups, but that would be far more advanced
technology than what is actually needed here.. For future reference we shall
phrase this lemma for more general finite fields than $\mathbb{F}_{5}$.

######  Lemma 7.3 (Gauss sum lemma).

Let $F$ be a finite field of odd characteristic, let $W$ be a vector space
over $F$, and let $M:W\to\widehat{W}$ be a self-adjoint linear transformation.
If $\dim(W)\geqslant 3$, then there exists a non-zero $x\in W$ such that
$x\cdot Mx=0$.

Proof.  If $M$ has a non-trivial kernel then the claim is easy, so assume $M$
has no kernel. Then a standard Gauss sum computation (using (4.1), for
instance) shows that $|\mathbb{E}_{x\in W}e(a(x\cdot Mx))|^{2}=|F|^{-\dim(W)}$
for all $a\in|F|\setminus\\{0\\}$. But by Fourier inversion we have

$\mathbb{E}_{x\in W}1_{x\cdot
Mx=0}=\textstyle\frac{1}{|F|}\displaystyle\sum_{a\in F}\mathbb{E}_{x\in
W}e(a(x\cdot
Mx))\geqslant\textstyle\frac{1}{|F|}\displaystyle(1-(|F|-1)\cdot|F|^{-\dim(W)/2}).$

Since $\dim(W)\geqslant 3$ we thus see that $\\{x\in W:x\cdot Mx=0\\}$ must
contain at least one non-zero element, and we are done.

In our situation, the space $W$ has dimension substantially larger than 3 – in
fact $\dim(W)\geqslant n-(2/\delta)^{4C}$. Let $U$ be a subspace of $W$ which
is degenerate in the sense that $x\cdot My=0$ for all $x,y\in U$, and which is
maximal with respect to this property. We claim that $\dim(U)\geqslant
n/2-(2/\delta)^{4C}$. Indeed if this were not the case the space
$U^{\perp}:=\\{x\in W:x\cdot My=0\hbox{ for all }y\in U\\}$ would have at
least three more dimensions than $U$ (in fact, vastly more than this), and one
could apply the previous lemma to $U^{\perp}/U$ to contradict the maximality
of $U$.

Let $U$ be as above. By splitting (7.3) into cosets of $U$ and applying the
pigeonhole principle, we may find a coset $z+U$ of $U$ in $y+W$ such that

$\mathbb{E}_{x\in
z+U}(1_{A}(x)-\alpha)1_{S_{t}}(x)\geqslant\textstyle\frac{1}{4}\displaystyle(\delta/2)^{4C}\mathbb{E}_{x\in
z+U}1_{S_{t}}(x).$

Note that on this space $z+U$, the form $x\cdot Mx$ becomes linear, which
means that $S_{t}\cap(z+U)$ is an affine subspace of $z+U$ of codimension at
most $1$. Letting $x_{0}+V$ denote this subspace, and recalling that the
constant $C$ in Theorem 2.3 could certainly be taken to be $2^{17}$,
Proposition 7.2 follows. Note that (7.1) suffices to guarantee the stated
bound $\dim(V)\geqslant n/3$.

Proof of Theorem 7.1. Suppose that $A\subseteq\mathbb{F}_{5}^{n}$ has
cardinality $\delta N$ yet contains no four-term arithmetic progression. Then
by repeated application of Proposition 7.2 we may construct a sequence

$\mathbb{F}_{5}^{n}\geqslant x_{1}+V_{1}\geqslant x_{2}+V_{2}\geqslant\dots$

of affine subspaces such that $\dim(V_{j})\geqslant n/3^{j}$ and

$\mathbb{E}_{x\in x_{j}+V_{j}}1_{A}(x)\geqslant\delta+j(\delta/2)^{2^{20}},$
(7.4)

provided only that at all stages the condition (7.1) is satisfied, that is to
say

$\dim(V_{j})>6(2/\delta)^{2^{20}}.$ (7.5)

Equation (7.4) is impossible if $j\geqslant j_{0}=(2/\delta)^{2^{20}}$, and so
(7.5) must be violated by some $j\leqslant j_{0}$. This means that

$n>6\times(2/\delta)^{2^{20}}\times 3^{(2/\delta)^{2^{20}}},$

which certainly implies that $\delta\ll(\log\log N)^{-2^{-21}}$.

Remark. A more-or-less identical argument shows that

$r_{4}(\mathbb{F}_{p}^{n})\ll N(\log\log N/p)^{-c},$

uniformly for all primes $p\geqslant 5$, for some absolute constant $c>0$. In
combination with Gowers’ result that $r_{4}(\mathbb{Z}/N\mathbb{Z})\ll
N(\log\log N)^{-c}$, this may be used to give a fairly cheap proof that
$r_{4}(G)=o(N)$ for all finite abelian $G$, a result which was first obtained
by Frankl and Rödl [17] by rather different means. The key to the argument is
that $G$ contains either a large subgroup of the form $\mathbb{F}_{p}^{n}$, or
else a large cyclic subgroup. The bound obtained is of the form

$r_{4}(G)\ll N(\log\log\log\log N)^{-c};$

we suppress the details since a far superior bound will be obtained in §11.

##  8\. Some results on Bohr sets

Let $G$ be an arbitrary finite abelian group with $|G|=N$, let
$S\subseteq\widehat{G}$ will be a set of $d$ characters, and suppose that
$\rho\in(0,1)$ is a positive parameter. We will collect some basic facts about
Bohr sets $B(S,\rho)$ which we will need to prove Theorem 2.7. These Bohr sets
play the role that subspaces did in the finite geometry setting, with the
quantity $d$ corresponding, roughly speaking, to the codimension of the
subspace.

Note that a Bohr set always contains 0, and is symmetric around the origin. In
fact we have the following easy bounds on the size of Bohr sets:

######  Lemma 8.1 (Bounds for size of Bohr sets).

We have

$|B(S,\rho)|\geqslant\rho^{d}N$

and

$|B(S,2\rho)|\leqslant 5^{d}|B(S,\rho)|.$

Proof.  By the triangle inequality, we see that for any $y=(y_{\xi})_{\xi\in
S}$ in the torus $(\mathbb{R}/\mathbb{Z})^{S}$, we have

$\displaystyle\sum_{x\in G}\prod_{\xi\in S}1_{\|\xi\cdot
x-y_{\xi}\|_{\mathbb{R}/\mathbb{Z}}<\rho/2}$ $\displaystyle=|\\{x\in
G:\sup_{\xi\in S}\|\xi\cdot x-y_{\xi}\|_{\mathbb{R}/\mathbb{Z}}<\rho/2\\}|$
$\displaystyle\leqslant|\\{x\in G:\sup_{\xi\in S}\|\xi\cdot
x\|_{\mathbb{R}/\mathbb{Z}}<\rho\\}|$ $\displaystyle=|B(S,\rho)|.$

Integrating this over all $y\in(\mathbb{R}/\mathbb{Z})^{S}$, we conclude that

$\sum_{x\in G}\rho^{d}\leqslant|B(S,\rho)|$

which gives the first bound.

To establish the second bound, we integrate the same expression but only over
the cube $\\{y:\sup_{\xi\in S}\|y_{\xi}\|\leqslant\frac{5}{2}\rho\\}$. Note
from the triangle inequality that this does not affect the components of the
integral for which $x\in B(S,2\rho)$. Thus we have

$\sum_{x\in B(S,2\rho)}\rho^{d}\leqslant|B(S,\rho)|(5\rho)^{d}$

which gives the second bound.

Next, we establish, following Bourgain, that regular Bohr sets (as defined in
Definition 2.6) exist in abundance.

######  Lemma 8.2 (Regular Bohr sets are ubiquitious [10]).

Let $0<\varepsilon<1$. Then there exists $\rho\in[\varepsilon,2\varepsilon]$
such that $B(S,\rho)$ is regular.

Proof.  We may assume $S$ is non-empty since the claim is trivial otherwise.
Let $f:[0,1]\to\mathbb{R}$ be the function
$f(a):=\frac{1}{d}\log_{2}|B(S,2^{a}\varepsilon)|$. Observe that $f$ is non-
decreasing in $a$, and from Lemma 8.1 we have $f(1)-f(0)\leqslant\log_{2}5$.

Suppose we could find $0.1\leqslant a\leqslant 0.9$ is such that
$|f(a^{\prime})-f(a)|\leqslant 20|a-a^{\prime}|$ for all $|a|\leqslant 0.1$.
Then it is easy to see that the Bohr set $B(S,2^{a}\varepsilon)$ is regular.
Thus, it suffices to obtain an $a$ with this property. This can be done
directly from the Hardy-Littlewood maximal inequality (applied to the
Lebesgue-Stieltjes measure $df$), or as follows. If no such $a$ exists, then
for every $a\in[0.1,0.9]$ there exists an interval $I$ of length at most $0.1$
and with one endpoint equal to $a$, such that $\int_{I}df>\int_{I}20\ dx$.
These intervals cover $[0.1,0.9]$, which has measure $0.8$. By the Vitali
covering lemma101010One can also use the Besicovitch covering lemma at this
point, which would in fact give slightly better bounds. Indeed, one can
improve the constant $1/5$ to $1/2$, see for instance [15]., one can find thus
find a finite subcollection of disjoint intervals $I_{1},\ldots,I_{n}$ of
total length $|I_{1}|+\ldots|I_{n}|\geqslant 0.8/5$ (say). But then we have

$\log_{2}5\geqslant\int_{0}^{1}df\geqslant\sum_{i=1}^{n}\int_{I_{i}}df\geqslant\sum_{i=1}^{n}\int_{I_{i}}20dx\geqslant\frac{0.8}{5}\times
20,$

a contradiction.

Next, we show that given any small set of points in $G$, one can find a large
Bohr set which avoids all of them except possibly for zero. We will need this
to develop the analogue of Lemma 6.2 (see Lemma 9.2 below).

######  Lemma 8.3 (Separation lemma).

Let $G$ be a finite additive group, and let $A\subseteq G$ be a set of
elements containing zero. Then there exists a set $S\subseteq\widehat{G}$ with
$|S|\leqslant 1+\log_{2}|A|$ such that $A\cap B(S,\frac{1}{4})=\\{0\\}$.

Proof.  We induct on $|A|$. When $|A|=1$ the claim is trivial (set
$S=\emptyset$). Now suppose that $|A|\geqslant 2$ and the claim has already
been proven for smaller sets $A$. Suppose that $2^{n}<|A|\leqslant 2^{n+1}$.
Let $\xi\in\widehat{G}$ be chosen randomly. Observe that for each $x\in
A\backslash\\{0\\}$, the map $\xi\mapsto\xi\cdot x$ is a non-trivial group
homomorphism from $\widehat{G}$ to $\mathbb{R}/\mathbb{Z}$, thus the random
variable $\xi\cdot x$ is uniformly distributed over a cyclic subgroup of
$\mathbb{R}/\mathbb{Z}$. In particular, we have

$\mathbb{P}(x\in
B(\xi,\textstyle\frac{1}{4}\displaystyle))=\mathbb{P}(\|\xi\cdot
x\|_{\mathbb{R}/\mathbb{Z}}<\textstyle\frac{1}{4}\displaystyle)\leqslant\textstyle\frac{1}{2}\displaystyle.$

Summing this over all non-zero $A$, we conclude

$\mathbb{E}|(A\backslash\\{0\\})\cap
B(\xi,\textstyle\frac{1}{4}\displaystyle)|\leqslant(|A|-1)/2.$

In particular, we can find $\xi\in\widehat{G}$ such that

$|A\cap
B(\xi,\textstyle\frac{1}{4}\displaystyle)|\leqslant\lfloor\frac{|A|+1}{2}\rfloor\leqslant
2^{n}.$

By induction hypothesis we conclude that there exists a set $S^{\prime}$ of
cardinality at most $n$ such that

$A\cap B(\xi,\textstyle\frac{1}{4}\displaystyle)\cap
B(S^{\prime},\textstyle\frac{1}{4}\displaystyle)=\\{0\\},$

and the claim follows by setting $S:=S^{\prime}\cup\\{\xi\\}$.

Our next task is to investigate the Fourier-analytic behavior of Bohr sets. In
the first instance we deal with a concept somewhat more general that that of a
Fourier coefficient, replacing a linear phase function by a locally linear
phase function.

######  Lemma 8.4 (Generalized Fourier decay).

Let $S\subseteq\widehat{G}$, $|S|=d$, be a set of characters. Let
$B:=B(S,\rho)$ be a regular Bohr set, and let
$\phi:B(S,2\rho)\to\mathbb{R}/\mathbb{Z}$ be a function which is locally
linear in the sense that that $\phi(x+y)=\phi(x)+\phi(y)$ whenever $x,y\in
B(S,\rho)$. Suppose that

$|\mathbb{E}_{x\in B}(e(\phi(x)))|\geqslant\eta$

for some $0<\eta\leqslant 1$ (large generalized Fourier coefficient). Then
$\phi$ is close to constant in the sense that for every $y\in B$ we have

$\|\phi(y)\|_{\mathbb{R}/\mathbb{Z}}\leqslant\frac{2^{12}d\|y\|_{S}}{\rho\eta^{2}}.$

Proof.  Let $y\in B$, and let $M\geqslant 0$ be the largest integer such that
$M\|y\|_{S}\leqslant\eta\rho/400d$. If $M=0$ then we have
$\|y\|_{S}\geqslant\eta\rho/400d$, and the claim is trivial. By Lemma 4.2 (ii)
we have

$|\mathbb{E}_{x\in B}(e(\phi(x)))-\mathbb{E}_{x\in B}\mathbb{E}_{-M\leqslant
n\leqslant M}e(\phi(x+ny)))|\leqslant\eta/2$

and hence by the triangle inequality

$|\mathbb{E}_{x\in B}\mathbb{E}_{-M\leqslant n\leqslant
M}e(\phi(x+ny))|\geqslant\eta/2.$

On the other hand, by the local linearity of $\phi$ we have
$\phi(x+ny)=\phi(x)+n\phi(y)$ for all $|n|\leqslant M$ and hence
$e(\phi(x+ny))={\mathbf{b}}(x)e(n\phi(y))$. By the triangle inequality we
conclude that

$|\mathbb{E}_{-M\leqslant n\leqslant M}e(n\phi(y))|\geqslant\eta/2.$

But by the geometric series formula, the left-hand side is bounded by
$2/M\|\phi(y)\|_{\mathbb{R}/\mathbb{Z}}$. This implies that

$\|\phi(y)\|_{\mathbb{R}/\mathbb{Z}}\leqslant\frac{4}{M\eta}\leqslant\frac{3200d}{\rho\eta^{2}}\|y\|_{S},$

which implies the result.

As a corollary we see that the normalized Fourier transform of a Bohr set
decays away from the “polar body” of that Bohr set111111One could obtain much
better Fourier localization properties by replacing the Bohr sets by smoother
weight functions; see for instance [30, 60] for examples of this approach.
This also conveys the slight advantage that all weight functions can
automatically be made regular. However these functions have the disadvantage
of being spread out in physical space, and we found it more convenient to use
Bourgain’s machinery of regular Bohr sets from [10] instead.. If
$\xi\in\widehat{G}$ then define

$\|\xi\|_{B(S,\rho)}:=\sup_{y\in B(S,\rho)}\|\xi\cdot
y\|_{\mathbb{R}/\mathbb{Z}}.$

Note that if $\xi\in S$ then $\|\xi\|_{B(S,\rho)}\leqslant\rho$.

######  Corollary 8.5 (Fourier decay).

Let $S\subseteq\widehat{G}$ be a set of $d$ characters, let $B:=B(S,\rho)$ be
a regular Bohr set, and let $0<\theta\leqslant 1$. Then for any
$\xi\in\widehat{G}$, we have

$|\mathbb{E}_{x\in B}e(\xi\cdot x)|\leqslant 64\big{(}\frac{\theta
d}{\|\xi\|_{B(S,\theta\rho)}}\big{)}^{1/2}$

where

Proof.  Apply Lemma 8.4 with $\phi(x):=\xi\cdot x$, with
$\eta:=|\mathbb{E}_{x\in B}e(\xi\cdot x)|$ and with $y$ being an arbitrary
element of $B(S,\theta r)$.

We can exploit this decay via a Tomas-Stein almost-orthogonality type argument
(also used by Bombieri [9] in the context of the large sieve; see also [45])
to conclude

######  Corollary 8.6 (Local Bessel inequality).

Let $S\subseteq\widehat{G}$ be a set of $d$ characters, let $B:=B(S,\rho)$ be
a regular Bohr set, let $0<\theta\leqslant 1$, and let
$\xi_{1},\ldots,\xi_{k}\in\widehat{G}$ be frequencies such that
$\|\xi_{i}-\xi_{j}\|_{B(S,\theta\rho)}\geqslant\delta$ for all $1\leqslant
i<j\leqslant k$ and some $\delta>0$. Then

$\mathbb{E}_{x\in B}|\sum_{j=1}^{k}{\mathbf{b}}(j)e(\xi_{j}(x))|^{2}\leqslant
k+2^{7}k^{2}(\theta d/\delta)^{1/2}$

for any bounded complex numbers ${\mathbf{b}}(j)$.

Proof.  We have

$\displaystyle\mathbb{E}_{x\in
B}|\sum_{j=1}^{k}{\mathbf{b}}(j)e(\xi_{j}(x))|^{2}$
$\displaystyle=\sum_{1\leqslant i,j\leqslant
k}{\mathbf{b}}(i,j)\mathbb{E}_{x\in B}e((\xi_{i}-\xi_{j})\cdot x)$
$\displaystyle\leqslant k+2\sum_{1\leqslant i<j\leqslant k}|\mathbb{E}_{x\in
B}e(\xi_{i}-\xi_{j})\cdot x)|$ $\displaystyle\leqslant k+2^{7}k^{2}(\theta
d/\delta)^{1/2},$

thanks to Corollary 8.5. The claim follows.

We can dualize the above corollary to give the following result. This allows
us to generalize, to the relative setting, a frequently-used consequence of
Parseval’s identity: a large set $A\subseteq G$ cannot have too many large
Fourier coefficients.

######  Corollary 8.7 (Local Bessel inequality, dual version).

Let $S\subseteq\widehat{G}$ be a set of $d$ characters, let $B:=B(S,\rho)$ be
a regular Bohr set, let $0<\theta,\eta\leqslant 1$, and suppose that
$A\subseteq B$. Let

$\Gamma:=\\{\xi\in\widehat{G}:|\widehat{1_{A}}(\xi)|\geqslant\eta\mathbb{E}(1_{B})\\}.$

Then there exist frequencies $\xi_{1},\ldots,\xi_{k}\in\widehat{G}$ with
$k\leqslant 2/\eta^{2}$ such that any $\xi\in\Gamma$ is close to some
$\xi_{i}$ in the $\|\cdot\|_{B(S,\theta\rho)}$ norm:

$\Gamma\subseteq\\{\xi\in\widehat{G}:\|\xi-\xi_{j}\|_{B(S,\theta\rho)}\leqslant
2^{16}\theta d/\eta^{4}\hbox{ for some }1\leqslant j\leqslant k\\}.$ (8.1)

Proof.  Let $\delta:=2^{16}\theta d/\eta^{4}$, and let
$\xi_{1},\ldots,\xi_{k}$ be frequencies in $\Gamma$ such that
$\|\xi_{i}-\xi_{j}\|_{B(S,\theta\rho)}\geqslant\delta$, and which is maximal
with respect to set inclusion. Then it is clear that (8.1) holds. For each
$1\leqslant j\leqslant k$, we have $\xi_{j}\in\Gamma$. Hence there exists a
bounded complex number ${\mathbf{b}}(j)$ such that

$\Re\mathbb{E}_{x\in B}{\mathbf{b}}(j)e(\xi_{j}(x))1_{A}(x)\geqslant\eta.$

Summing this in $j$ and applying Cauchy-Schwarz, we conclude that

$\mathbb{E}_{x\in
B}|\sum_{j=1}^{k}{\mathbf{b}}(j)e(\xi_{j}(x))|^{2}\geqslant\eta^{2}k^{2}.$

Applying Corollary 8.6, we conclude that $\eta^{2}k^{2}\leqslant
k+\frac{1}{2}\eta^{2}k^{2}$, and hence $k\leqslant 2/\eta^{2}$. The claim
follows.

As a consequence, we can now generalize Bogolyubov’s argument (Lemma 6.3) to
subsets of Bohr sets.

######  Lemma 8.8 (Local Bogolyubov lemma).

Let $S\subseteq\widehat{G}$ be a set of $d$ characters, and let
$B:=B(S,\rho)$. Let $A\subseteq B$ be a set with $|A|=\delta|B|$. Then there
exists a set $S^{\prime}\subseteq\widehat{G}$ with $|S^{\prime}|\leqslant
2^{7}\delta^{-3}$ such that $B(S\cup
S^{\prime},2^{-33}\delta^{6}\rho/d)\subseteq 2A-2A$.

Proof.  It is convenient to replace $2A-2A$ by the slightly smaller set
$A+A^{\prime}-A-A^{\prime}$. Let $\varepsilon=\delta/400d$. By Lemma 8.2,
there exists $\rho^{\prime}\in[\varepsilon\rho,2\varepsilon,\rho]$ such that
the Bohr set $B^{\prime}:=B(S,\rho^{\prime})$ is regular. By Lemma 4.2 (iii)
we can find $x\in B$ such that

$\mathbb{E}_{y\in x+B^{\prime}}1_{A}(y)\geqslant\mathbb{E}_{y\in
B}1_{A}(y)-200d\varepsilon\geqslant\delta/2.$

Let $A^{\prime}:=A\cap(x+B^{\prime})$. From the Fourier inversion formulae

$1_{A}(x)=\sum_{\xi\in\widehat{G}}\widehat{1}_{A}(\xi)e(\xi\cdot x);\quad
1_{A^{\prime}}(x)=\sum_{\xi\in\widehat{G}}\widehat{1}_{A^{\prime}}(\xi)e(\xi\cdot
x)$

we conclude that

$1_{A}*1_{A^{\prime}}*1_{-A}*1_{-A^{\prime}}(x)=\sum_{\xi\in\widehat{G}}|\widehat{1}_{A}(\xi)|^{2}|\widehat{1}_{A^{\prime}}(\xi)|^{2}e(\xi\cdot
x).$ (8.2)

In particular, applying (8.2) with $x=0$ we conclude that

$\mathbb{E}_{x\in
G}|1_{A}*1_{A^{\prime}}(x)|^{2}=\sum_{\xi\in\widehat{G}}|\widehat{1}_{A}(\xi)|^{2}|\widehat{1}_{A^{\prime}}(\xi)|^{2}.$

The function $1_{A}*1_{A^{\prime}}$ is supported on $B(S,\rho+\rho^{\prime})$,
which has cardinality at most $2|B|$ since $B$ is regular and
$\varepsilon<1/200d$. Thus by Cauchy-Schwarz

$\displaystyle\mathbb{E}_{x\in G}|1_{A}*1_{A^{\prime}}(x)|^{2}$
$\displaystyle\geqslant$ $\displaystyle(\mathbb{E}_{x\in
G}1_{A}*1_{A^{\prime}}(x))^{2}/2\mathbb{E}(1_{B})$ $\displaystyle=$
$\displaystyle\mathbb{E}(1_{A})^{2}\mathbb{E}(1_{A^{\prime}})^{2}/2\mathbb{E}(1_{B})$
$\displaystyle=$
$\displaystyle\textstyle\frac{1}{2}\displaystyle\big{(}\mathbb{E}_{y\in
B}1_{A}(y)\big{)}^{2}\big{(}\mathbb{E}_{y\in
x+B^{\prime}}1_{A}(y)\big{)}^{2}\mathbb{E}(1_{B})\mathbb{E}(1_{B^{\prime}})^{2}$
$\displaystyle\geqslant$
$\displaystyle\delta^{4}K^{-4}\mathbb{E}(1_{B})\mathbb{E}(1_{B^{\prime}})^{2}/8.$

Thus we have

$\sum_{\xi\in\widehat{G}}|\widehat{1}_{A}(\xi)|^{2}|\widehat{1}_{A^{\prime}}(\xi)|^{2}\geqslant\textstyle\frac{1}{8}\displaystyle\delta^{4}\mathbb{E}(1_{B})\mathbb{E}(1_{B^{\prime}})^{2}.$
(8.3)

Now let

$R:=\\{\xi\in
G:|\widehat{1}_{A^{\prime}}(\xi)|\geqslant\textstyle\frac{1}{8}\displaystyle\delta^{3/2}\mathbb{E}(1_{B^{\prime}})\\},$

and let $x\in B(R,\frac{1}{10})$. Then by taking real parts of both sides of
(8.2), we conclude

$\displaystyle 1_{A}*1_{A^{\prime}}*1_{-A}*1_{-A^{\prime}}(x)$
$\displaystyle=$
$\displaystyle\sum_{\xi\in\widehat{G}}|\widehat{1}_{A}(\xi)|^{2}|\widehat{1}_{A^{\prime}}(\xi)|^{2}\cos(2\pi\xi\cdot
x)$ $\displaystyle\geqslant$ $\displaystyle\sum_{\xi\in
R}|\widehat{1}_{A}(\xi)|^{2}|\widehat{1}_{A^{\prime}}(\xi)|^{2}\cos(2\pi/10)-\sum_{\xi\not\in
R}|\widehat{1}_{A}(\xi)|^{2}|\widehat{1}_{A^{\prime}}(\xi)|^{2}$
$\displaystyle=$
$\displaystyle\sum_{\xi\in\widehat{G}}|\widehat{1}_{A}(\xi)|^{2}|\widehat{1}_{A^{\prime}}(\xi)|^{2}\cos(2\pi/10)$
$\displaystyle\qquad-(\cos(2\pi/10)+1)\sum_{\xi\notin
R}|\widehat{1}_{A}(\xi)|^{2}|\widehat{1}_{A^{\prime}}(\xi)|^{2}$
$\displaystyle\geqslant$
$\displaystyle\textstyle\frac{1}{2}\displaystyle(\sum_{\xi\in\widehat{G}}|\widehat{1}_{A}(\xi)|^{2}|\widehat{1}_{A^{\prime}}(\xi)|^{2})-2\sum_{\xi\not\in
R}|\widehat{1}_{A}(\xi)|^{2}|\widehat{1}_{A^{\prime}}(\xi)|^{2}$
$\displaystyle\geqslant$
$\displaystyle\textstyle\frac{1}{16}\displaystyle\delta^{4}\mathbb{E}(1_{B})\mathbb{E}(1_{B^{\prime}})^{2}-\textstyle\frac{1}{32}\displaystyle\delta^{3}\mathbb{E}(1_{B^{\prime}})^{2}\sum_{\xi\in
G}|\widehat{1}_{A}(\xi)|^{2}$

using (8.3) and the definition of $R$. On the other hand, from Plancherel’s
identity we have

$\sum_{\xi\in
G}|\widehat{1}_{A}(\xi)|^{2}=\mathbb{E}(1_{A})\leqslant\delta\mathbb{E}(1_{B}),$

and hence

$1_{A}*1_{A^{\prime}}*1_{-A}*1_{-A^{\prime}}(x)\geqslant\big{(}\frac{\delta^{4}}{16}-\frac{\delta^{4}}{32}\big{)}\mathbb{E}(1_{B})\mathbb{E}(1_{B^{\prime}})^{2}>0,$

which implies that $x$ is contained in $A+A^{\prime}-A-A^{\prime}$ and hence
in $2A-2A$. Hence we have

$B(R,\textstyle\frac{1}{10}\displaystyle)\subseteq 2A-2A.$

We are not done yet, because we do not have good bounds for $|R|$. Let
$\theta>0$ be a small parameter to be chosen later. Invoking Corollary 8.7, we
conclude the existence of frequencies $\xi_{1},\ldots,\xi_{k}\in\widehat{G}$
with $k\leqslant 128\delta^{3}$ such that

$R\subseteq\\{\xi\in\widehat{G}:\|\xi-\xi_{j}\|_{B(S,\theta\rho)}\leqslant
2^{28}\delta^{-6}\theta d\hbox{ for some }1\leqslant j\leqslant k\\}.$

Let $S^{\prime}:=\\{\xi_{1},\ldots,\xi_{k}\\}$. If $x\in B(S\cup
S^{\prime},\theta\rho)$ then in particular $x\in B(S,\theta\rho)$. Thus if
$\xi\in R$, then by the preceding inclusion we have

$\|\xi\cdot x-\xi_{j}\cdot x\|_{\mathbb{R}/\mathbb{Z}}\leqslant
2^{28}\delta^{-6}\theta d\hbox{ for some }j.$

Also, since $x\in B(S^{\prime},\theta\rho)$, we get

$\|\xi_{j}\cdot
x\|_{\mathbb{R}/\mathbb{Z}}\leqslant\theta\rho\leqslant\theta;$

by the triangle inequality we then obtain

$\|\xi\cdot x\|_{\mathbb{R}/\mathbb{Z}}\leqslant 2^{29}\delta^{-6}\theta d.$

We thus conclude that

$B(S\cup S^{\prime},\theta\rho)\subseteq B(R,2^{29}\delta^{-6}\theta d).$

Thus if we choose $\theta:=2^{-33}\delta^{6}/d$, we have $B(S\cup
S^{\prime},\theta\rho)\subseteq B(R,\frac{1}{10})$, and since
$B(R,\frac{1}{10})\subseteq 2A-2A$ the claim follows.

##  9\. The general group case

We now prove Theorem 2.7, which generalizes Theorem 2.3 to the case of
arbitrary finite additive groups $G$. We begin by disposing of part (ii) of
the theorem, which is rather easier to establish than (i).

Recall that in order to establish Theorem 2.7 (ii) we are to prove that if
$S\subseteq\widehat{G}$ is a set of $d$ characters, if $B=B(S,\rho)$ is a
regular Bohr set, if $f:G\rightarrow\mathcal{D}$ is a bounded function and if
$\|f\|_{u^{3}(y+B)}\geqslant\eta$ then we have

$\|f\|_{U^{3}(G)}\geqslant(\eta^{3}\rho^{2}/Cd^{3})^{d}$

for some absolute constant $C$. By translation invariance we may take $y=0$.
Let $\phi:B\to\mathbb{R}/\mathbb{Z}$ be a locally quadratic phase function on
$B$, and suppose that

$|\mathbb{E}_{x\in B}(f(x)e(-\phi(x)))|=\eta.$

It turns out to be convenient to have $\phi$ defined, and to be a quadratic
form, on a slightly larger Bohr set than $B$. This is not in general possible,
but the same effect can be achieved by first passing to a smaller Bohr set. In
fact, in the argument which follows we will have two smaller Bohr sets
$B^{\prime}=B(S,\rho^{\prime})$ and
$B^{\prime\prime}=B(S,\rho^{\prime\prime})$. Set $\varepsilon=c\eta/d$, where
$c$ is a small constant to be specified later. We will take
$\rho^{\prime}\in[\varepsilon\rho/2,\varepsilon\rho]$ so that $B^{\prime}$ is
regular (this is possible by Lemma 8.2) and
$\rho^{\prime\prime}=\varepsilon\rho^{\prime}$ (we will not require
$B^{\prime\prime}$ to be regular). It will be convenient to write
$\beta^{\prime}:=\mathbb{E}1_{B^{\prime}}$ and
$\beta^{\prime\prime}:=\mathbb{E}1_{B^{\prime\prime}}$. By Lemma 4.2 we have

$\eta=\mathbb{E}_{z\in B}\mathbb{E}_{x\in
z+B^{\prime}}(f(x)e(-\phi(x)))+O(\varepsilon d).$

Observe that the contribution from $z\in B\backslash
B(S,(1-10\varepsilon)\rho)$ is at most $O(\varepsilon d)$, thanks to the
regularity of $B$, Thus we in fact have

$\mathbb{E}_{x\in B}(f(x)e(-\phi(x)))=\mathbb{E}_{z\in
B}1_{B(S,(1-10\varepsilon)\rho)}(z)\mathbb{E}_{x\in
z+B^{\prime}}(f(x)e(-\phi(x)))+O(\varepsilon d),$

and hence by the pigeonhole principle there exists $z\in
B(S,(1-10\varepsilon)\rho)$ such that

$|\mathbb{E}_{x\in z+B^{\prime}}(f(x)e(-\phi(x)))|\geqslant 2\eta/3$ (9.1)

provided that $c$ is chosen sufficiently small.

We are going to compare $1_{z+B^{\prime}}$, which is relevant to (9.1), with
the function

$F(x):=\frac{1}{\beta^{\prime\prime}}\mathbb{E}_{h}1_{z+B^{\prime\prime}}(x+h)1_{z+B^{\prime}}(x+2h).$

Write $B^{\prime}_{-}=B(S,(1-2\epsilon)\rho^{\prime})$ and
$B^{\prime}_{+}=B(S,(1+2\epsilon)\rho^{\prime})$. Note that if $x\in
z+B^{\prime}_{-}$ and $x+h\in z+B^{\prime\prime}$ then $x+2h=2(x+h)-x$ is
contained in $z+B^{\prime}$. For such $x$, then, we have $F(x)=1$. Also, if
$F(x)\neq 0$ then there is some $h$ such that $x+h\in z+B^{\prime\prime}$ and
$x+2h\in z+B^{\prime}$, which means that $x=2(x+h)-(x+2h)$ lies in
$z+B^{\prime}_{+}$. We have, then,

$|F(x)-1_{z+B^{\prime}}(x)|\leqslant 21_{B^{\prime}_{+}\setminus
B^{\prime}_{-}}(x).$ (9.2)

Now note further that if $x+h\in z+B^{\prime\prime}$ and $x+2h\in
z+B^{\prime}$ then

$x\in z+B^{\prime}+2B^{\prime\prime}\subseteq B,$

and also

$x+3h=2(x+2h)-(x+h)\in z+2B^{\prime}+B^{\prime\prime}\subseteq B.$

Both of these are consequences of the fact that $z\in
B(S,(1-10\varepsilon)\rho)$. In such an eventuality, then, all four of the
elements $x,x+h,x+2h,x+3h$ lie in $B$ and, since $\phi$ is quadratic, we have
$(h\cdot\nabla_{x})^{3}\phi(x)=0$, or in other words

$\phi(x)-3\phi(x+h)+3\phi(x+2h)-\phi(x+3h)=0.$ (9.3)

Therefore

$\displaystyle F(x)e(-\phi(x))$ $\displaystyle=$
$\displaystyle\frac{1}{\beta^{\prime\prime}}\mathbb{E}_{h}1_{z+B^{\prime\prime}}(x+h)e(3\phi(x+h))1_{z+B^{\prime}}(x+2h)\times$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\times\;e(-3\phi(x+2h))e(\phi(x+3h))$
$\displaystyle=:$
$\displaystyle\frac{1}{\beta^{\prime\prime}}\mathbb{E}_{h}g_{1}(x+h)g_{2}(x+2h)g_{3}(x+3h),$

say, where the functions $g_{1},g_{2},g_{3}$ are all bounded by 1. It is
immediate from (9.2) that

$|F(x)e(-\phi(x))-1_{z+B^{\prime}}(x)e(-\phi(x))|\leqslant
21_{B^{\prime}_{+}\setminus B^{\prime}_{-}}(x).$

From (9.1) we infer, then, that

$\displaystyle\frac{1}{\beta^{\prime\prime}}\mathbb{E}_{x,h}f(x)g_{1}(x+h)g_{2}(x+2h)g_{3}(x+3h)$
$\displaystyle=$ $\displaystyle\mathbb{E}_{x}f(x)F(x)e(-\phi(x))$
$\displaystyle=$
$\displaystyle\mathbb{E}_{x}f(x)1_{z+B^{\prime}}(x)e(-\phi(x))+O(\mathbb{E}1_{B^{\prime}_{+}\setminus
B^{\prime}_{-}})$ $\displaystyle=$
$\displaystyle\mathbb{E}_{x}f(x)1_{z+B^{\prime}}(x)e(-\phi(x))+O(\epsilon
d\beta^{\prime}),$

the penultimate step being a consequence of the regularity of $B^{\prime}$. If
$c$ is chosen small enough, this means in view of (9.1) that

$\mathbb{E}_{x,h}f(x)g_{1}(x+h)g_{2}(x+2h)g_{3}(x+3h)\geqslant\beta^{\prime}\beta^{\prime\prime}\eta/3.$
(9.4)

However Proposition 1.7 implies that we have

$\big{|}\mathbb{E}_{x,h}f(x)g_{1}(x+h)g_{2}(x+2h)g_{3}(x+3h)\big{|}\leqslant\|f\|_{U^{3}(G)},$

and hence from (9.4) we have

$\|f\|_{U^{3}(G)}\geqslant\beta^{\prime}\beta^{\prime\prime}\eta/3\geqslant(\varepsilon^{3}\rho^{2}/4)^{d}\eta/3\geqslant(\eta^{3}\rho^{2}/Cd^{3})^{d}$

for some absolute constant $C$.

Now we turn to the proof of Theorem 2.7 (i). As in §6 our starting point is
Proposition 5.4, which the reader may care to recall now. The argument is
closely analogous to that in §6, and hence in turn to that in §3.

Step 1: Linearization of phase derivative. We begin by carrying out the first
major step, which is to show that the function $h\mapsto\xi_{h}$, which
roughly speaking captures the derivative of the phase of $f$, matches up with
a locally linear function.

######  Proposition 9.1.

Let $H^{\prime}\subseteq G$, and suppose that
$\xi:H^{\prime}\rightarrow\widehat{G}$ is a function whose graph

$\Gamma^{\prime}:=\\{(h,\xi_{h}):h\in H^{\prime}\\}\subseteq
G\times\widehat{G}$

obeys the estimates

$K^{-1}N\leqslant|\Gamma^{\prime}|\leqslant|9\Gamma^{\prime}-8\Gamma|\leqslant
KN$

for some $K\geqslant 1$. Then there is a set $S\subseteq\widehat{G}$,

$d_{1}:=|S|\leqslant 2^{13}K^{26},$

a regular Bohr set $B_{1}:=B(S,\rho)$, where
$\rho\in[\frac{1}{16},\frac{1}{8}]$, elements $x_{0}\in G,\xi\in\widehat{G}$
and a function $M:B(S,\frac{1}{4})\rightarrow\widehat{G}$ satisfying the local
linearity condition121212recall that $\|h\|_{S}:=\sup_{\xi\in
S}\|\xi_{h}\|_{\mathbb{R}/\mathbb{Z}}$

$M(h\pm h^{\prime})=Mh\pm Mh^{\prime}\hbox{ whenever
}\|h\|_{S},\|h^{\prime}\|_{S}\leqslant\textstyle\frac{1}{8}\displaystyle,$
(9.5)

and such that

$\mathbb{E}\big{(}1_{H^{\prime}}(x_{0}+h)1_{\xi_{x_{0}+h}=2Mh+\xi_{0}}|h\in
B_{1}\big{)}\geqslant 2^{-6}K^{-13}.$

Proof. As in the finite field case, the first step is to refine the graph
$\Gamma^{\prime}$ so that certain of the iterated sum-difference sets
$k\Gamma^{\prime}-l\Gamma^{\prime}$ are also graphs. To do this we use the
following generalization of Lemma 6.2:

######  Lemma 9.2.

There exists a subset $\Gamma^{\prime\prime}=\\{(h,\xi_{h}):h\in
H^{\prime\prime}\\}$ of $\Gamma^{\prime}$ with

$|\Gamma^{\prime\prime}|\geqslant 2^{-6}K^{-13}N$

such that $4\Gamma^{\prime\prime}-4\Gamma^{\prime\prime}$ is a graph.

Proof.  Let $A\subseteq\widehat{G}$ be the set of all $\xi$ such that
$(0,\xi)\in 8\Gamma^{\prime}-8\Gamma^{\prime}$. Arguing as in the proof of
Lemma 6.2 we conclude that $|A|\leqslant K^{2}$. Applying Lemma 8.3, we can
find a set $S\in\widehat{\widehat{G}\,}$ with $|S|\leqslant 1+2\log_{2}K$ such
that $A\cap B(S,\frac{1}{4})=\\{0\\}$.

Let $\Psi:\widehat{G}\to(\mathbb{R}/\mathbb{Z})^{S}$ be the homomorphism
$\Psi(\xi):=(s(\xi))_{s\in S}$. Now let us cover the torus
$(\mathbb{R}/\mathbb{Z})^{S}$ by $2^{6|S|}\leqslant 2^{6}K^{12}$ cubes of
side-length $\frac{1}{64}$. Since $|\Gamma^{\prime}|\geqslant N/K$, the
pigeonhole principle implies that there exists one of these cubes $Q$ for
which the set

$\Gamma^{\prime\prime}:=\\{(h,\xi_{h})\in\Gamma^{\prime}:\Psi(\xi_{h})\in
Q\\}$

has cardinality at least $2^{-6}K^{-13}N$. Now observe from the linearity of
$s$ that if $(0,\xi)\in 8\Gamma^{\prime\prime}-8\Gamma^{\prime\prime}$ then
$\|s(\xi)\|_{\mathbb{R}/\mathbb{Z}}\leqslant\frac{16}{64}$ for all $s\in S$.
In other words, $\xi\in B(S,\frac{1}{4})$. But $\xi$ also lies in $A$, and
hence $\xi=0$ by construction. Since
$8\Gamma^{\prime\prime}-8\Gamma^{\prime\prime}$ is the difference set of
$4\Gamma^{\prime\prime}-4\Gamma^{\prime\prime}$, we conclude that
$4\Gamma^{\prime\prime}-4\Gamma^{\prime\prime}$ is a graph as desired.

Define $H^{\prime\prime}$ so that $\Gamma^{\prime\prime}=\\{(h,\xi_{h}):h\in
H^{\prime\prime}\\}$. Applying Lemma 6.3 with $A:=H^{\prime\prime}$, we obtain
a set $S\subseteq\widehat{G}$ with $|S|\leqslant 2^{13}K^{26}$ such that the
Bohr set $B_{0}:=B(S,\frac{1}{4})$ is completely contained inside
$2H^{\prime\prime}-2H^{\prime\prime}$. We will now work inside this Bohr set
$B_{0}$ and pass to progressively narrower Bohr sets $B_{1},B_{2},\ldots$ when
necessary. We will eventually end up at $B_{5}$; the dimension of $B_{j}$ will
be denoted $d_{j}$, and so in particular $d_{0}=|S|$. It will turn out that
$d_{0}=d_{1}=d_{2}<d_{3}=d_{4}=d_{5}$, that is to say it is only in passing
from $B_{2}$ to $B_{3}$ that we shall increment the dimension of $B_{j}$. This
is because that passage will involve Lemma 8.8.

Since $2\Gamma^{\prime\prime}-2\Gamma^{\prime\prime}$ is a graph, we can find
a (unique) function $M:B_{0}\to\widehat{G}$ such that

$\\{(h,2M(h)):h\in B_{0}\\}\subseteq 2H^{\prime\prime}-2H^{\prime\prime}.$

Since $2\Gamma^{\prime\prime}-2\Gamma^{\prime\prime}$ contains 0, we conclude
that $\phi(0)=0$. Also, since $8\Gamma^{\prime\prime}-8\Gamma^{\prime\prime}$
is a graph we see that

$M(h_{1})+M(h_{2})=M(h^{\prime}_{1})+M(h^{\prime}_{2})$ (9.6)

whenever $h_{1},h_{2},h^{\prime}_{1},h^{\prime}_{2}\in B_{0}$ is such that
$h_{1}+h_{2}=h^{\prime}_{1}+h^{\prime}_{2}$; in other words, $M$ is a _Freiman
homomorphism_ of order 2. In particular, since $M0=0$, we have the local
linearity relationship (9.5).

By Lemma 8.2 there is $\rho\in[\frac{1}{16},\frac{1}{8}]$ such that the Bohr
set $B_{1}:=B(S,\rho_{1})$ is regular. By Lemma 4.1 there exists $x_{0}\in G$
such that

$\mathbb{E}_{h\in B_{1}}1_{H^{\prime\prime}}(x_{0}+h)\geqslant 2^{-6}K^{-13}.$

Let us fix this $x_{0}$, and set $A:=\\{h\in B_{1}:x_{0}+h\in
H^{\prime\prime}\\}$, so that we have

$|A|\geqslant 2^{-6}K^{-13}|B_{1}|.$

Observe that if $h,h^{\prime}\in A$, then
$(h-h^{\prime},\xi_{x_{0}+h}-\xi_{x_{0}+h^{\prime}})$ lies in
$\Gamma^{\prime\prime}-\Gamma^{\prime\prime}$, which is a subgraph of
$2\Gamma^{\prime\prime}-2\Gamma^{\prime\prime}$. Thus we have
$\xi_{x_{0}+h}-\xi_{x_{0}+h^{\prime}}=2M(h-h^{\prime})$. Combining this with
(9.5), we conclude that there exists $\xi_{0}\in\widehat{G}$ such that

$\xi_{x_{0}+h}=\xi_{0}+2Mh\hbox{ for all }h\in A.$

This concludes the proof of Proposition 9.1.

Combining Proposition 9.1 with Proposition 5.4 leads immediately to the
following, which generalizes Proposition 6.4 to arbitrary $G$.

######  Proposition 9.3 (Large $U^{3}(G)$-norm implies locally linear phase
derivative).

Let $G$ be an arbitrary finite additive group, and let $f:G\to\mathcal{D}$ be
a bounded function such that $\|f\|_{U^{3}(G)}\geqslant\eta$ for some
$\eta>0$. Then there exists a set $S\subseteq\widehat{G}$ with

$d_{1}:=|S|\leqslant 2^{C_{3}}\eta^{-C^{\prime}_{3}},$

a regular Bohr set $B_{1}:=B(S,\rho)\subseteq B(S,\frac{1}{4})=B_{0}$ with
$\rho\in[\frac{1}{16},\frac{1}{8}]$, elements $x_{0}\in G$ and
$\xi_{0}\in\widehat{G}$, and a function $M:B_{0}\to\widehat{G}$ obeying the
local linearity property (9.5), such that

$\mathbb{E}_{h\in B_{1}}|\mathbb{E}_{x\in
G}T^{x_{0}+h}f(x)\overline{f(x)}e(-(\xi_{0}+2Mh)\cdot x)|\geqslant
2^{-C_{4}}\eta^{C^{\prime}_{4}}.$ (9.7)

We could take $C_{i},C^{\prime}_{i}=2^{18}$, $i=3,4$.

Step 2: The symmetry argument. Let $S,B_{1},x_{0},\xi_{0},M$ be as in
Proposition 9.3. Using the proof of Theorem 2.3 as a model, the next step
would be to establish some symmetry property on $M:B_{0}\to\widehat{G}$, in
the sense that the form $\\{x,y\\}:=M(x)\cdot y-M(y)\cdot x$ is small. More
precisely, we shall establish

######  Lemma 9.4 (Symmetry of derivative).

Let the notation be as in Proposition 9.3. For any $x,y\in B_{0}$, let
$\\{x,y\\}$ denote the anti-symmetric form

$\\{x,y\\}:=M(x)\cdot y-M(y)\cdot x.$

Then there exists a set $S_{3}$ of frequencies with
$S_{3}\supseteq\frac{1}{2}\cdot S$ and $d_{3}:=|S_{3}|\leqslant
2^{C_{5}}\eta^{-C^{\prime}_{5}}$, and a Bohr set
$B_{3}=B(S_{3},2^{-C_{6}}\eta^{C^{\prime}_{6}})\subseteq B_{1}$, such that

$\|\\{x,z\\}\|_{\mathbb{R}/\mathbb{Z}}\leqslant
2^{C_{7}}\eta^{-C^{\prime}_{7}}\|x\|_{S_{3}}\hbox{ for all }x,z\in B_{3}.$
(9.8)

It is permissible to take all of the $C_{i},C^{\prime}_{i}$, $i=5,6,7$, equal
to $2^{23}$.

Proof.  Let
$\varepsilon_{2}=2^{-C_{3}-2C_{4}-10}\eta^{C^{\prime}_{3}+2C^{\prime}_{4}}$.
By Lemma 8.2, we can find $\rho_{2}\in[\varepsilon_{2},2\varepsilon_{2}]$ such
that $B_{2}:=B(S,\rho_{2})\subseteq B_{1}$ is a regular Bohr set. Of course we
have

$d_{2}=d_{1}\leqslant 2^{C_{3}}\eta^{-C_{3}}.$

We write (9.7) as

$|\mathbb{E}_{h\in B_{1};x\in
G}{\mathbf{b}}(x+h){\mathbf{b}}(x){\mathbf{b}}(h)e(-2Mh\cdot x)|\geqslant
2^{-C_{4}}\eta^{C^{\prime}_{4}},$ (9.9)

absorbing all the phase terms into the functions ${\mathbf{b}}$. Applying
Lemma 4.1 we can find $x_{1}\in G$ such that

$|\mathbb{E}_{h\in B_{1};x\in
B_{2}}{\mathbf{b}}(x+x_{1}+h){\mathbf{b}}(x+x_{1}){\mathbf{b}}(h)e(-2Mh\cdot(x+x_{1}))|\geqslant
2^{-C_{4}}\eta^{C^{\prime}_{4}}.$ (9.10)

Absorbing the $x_{1}$ terms into the functions ${\mathbf{b}}$ we conclude that

$|\mathbb{E}_{h\in B_{1};x\in
B_{2}}{\mathbf{b}}(h){\mathbf{b}}(x+h){\mathbf{b}}(x)e(-2Mh\cdot x)|\geqslant
2^{-C_{4}}\eta^{C^{\prime}_{4}}.$ (9.11)

Applying the Cauchy-Schwarz inequality (Lemma 4.3) to eliminate
${\mathbf{b}}(h)$, we then deduce

$\mathbb{E}_{h\in B_{1};x,y\in
B_{2}}{\mathbf{b}}(x+h){\mathbf{b}}(x){\mathbf{b}}(y+h){\mathbf{b}}(y)e(-2Mh\cdot(y-x))\geqslant
2^{-2C_{4}}\eta^{2C^{\prime}_{4}}.$ (9.12)

Making the substitution $z:=x+y+h$, this becomes

$\mathbb{E}_{x,y\in B_{2}}\mathbb{E}_{z\in
x+y+B_{2}}{\mathbf{b}}(z,x){\mathbf{b}}(z,y)e(-2M(z-x-y)\cdot(y-x))\geqslant
2^{-2C_{4}}\eta^{2C^{\prime}_{4}}.$ (9.13)

Absorbing as many phase terms into the functions ${\mathbf{b}}(z,x)$ and
${\mathbf{b}}(z,y)$ as we can, we conclude

$\mathbb{E}_{x,y\in B_{2}}\mathbb{E}_{z\in
x+y+B_{1}}{\mathbf{b}}(z,x){\mathbf{b}}(z,y)e(2\\{x,y\\})\geqslant
2^{-2C_{4}}\eta^{2C^{\prime}_{4}}.$

Next, by the regularity of $B_{1}$ and Lemma 4.2 (i), we observe that

$\displaystyle\big{|}\mathbb{E}_{x,y\in B_{2}}\mathbb{E}_{z\in
x+y+B_{1}}{\mathbf{b}}(z,x){\mathbf{b}}(z,y)e(2\\{x,y\\})$
$\displaystyle\qquad\qquad\qquad\qquad\qquad-\mathbb{E}_{x,y\in
B_{2}}\mathbb{E}_{z\in
B_{1}}{\mathbf{b}}(z,x){\mathbf{b}}(z,y)e(2\\{x,y\\})\big{|}\leqslant
2^{9}\varepsilon_{2}d$

which, due to the choice of $\varepsilon_{2}$ and the bound $d\leqslant
2^{C_{3}}\eta^{-C^{\prime}_{3}}$, implies that

$\mathbb{E}_{x,y\in B_{2}}\mathbb{E}_{z\in
B_{1}}{\mathbf{b}}(z,x){\mathbf{b}}(z,y)e(2\\{x,y\\})\geqslant
2^{-2C_{4}-1}\eta^{2C^{\prime}_{4}}.$ (9.14)

In particular, by the pigeonhole principle in $z$ we have

$|\mathbb{E}_{x,y\in
B_{2}}{\mathbf{b}}(x){\mathbf{b}}(y)e(2\\{x,y\\})|\geqslant
2^{-2C_{4}-1}\eta^{2C^{\prime}_{4}}$ (9.15)

for some bounded functions ${\mathbf{b}}(x),{\mathbf{b}}(y)$. At this point we
observe the local bilinearity relationships

$\\{x+x^{\prime},y\\}=\\{x,y\\}+\\{x^{\prime},y\\};\quad\\{x,y+y^{\prime}\\}=\\{x,y\\}+\\{x,y^{\prime}\\},$
(9.16)

which hold whenever all four of
$\|x\|_{S},\|x^{\prime}\|_{S},\|y\|_{S},\|y^{\prime}\|_{S}$ are at most
$\frac{1}{8}$. We can then apply Cauchy-Schwarz (Lemma 4.3) to eliminate
${\mathbf{b}}(x)$ and conclude that

$|\mathbb{E}_{x,y,y^{\prime}\in
B_{2}}{\mathbf{b}}(y,y^{\prime})e(2\\{x,y^{\prime}-y\\})|\geqslant
2^{-4C_{4}-2}\eta^{4C^{\prime}_{4}},$

and hence by the triangle inequality

$\mathbb{E}_{y,y^{\prime}\in B_{2}}|\mathbb{E}_{x\in
B_{2}}e(2\\{x,y^{\prime}-y\\})|\geqslant 2^{-4C_{4}-2}\eta^{4C^{\prime}_{4}}.$

By the pigeonhole principle, there exists $y^{\prime}\in B_{2}$ such that

$\mathbb{E}_{y\in B_{2}}|\mathbb{E}_{x\in
B_{2}}e(2\\{x,y^{\prime}-y\\})|\geqslant 2^{-4C_{4}-2}\eta^{4C^{\prime}_{4}}.$
(9.17)

Fix this $y^{\prime}$. Since $|\mathbb{E}_{x\in
B_{2}}e(2\\{x,y^{\prime}-y\\})|$ is bounded above by 1, we conclude that there
exists a set $A\subseteq B_{2}$ with $|A|\geqslant
2^{-4C_{4}-3}\eta^{4C^{\prime}_{4}}|B_{2}|$ such that

$|\mathbb{E}_{x\in B_{2}}e(2\\{x,y^{\prime}-y\\})|\geqslant
2^{-4C_{4}-3}\eta^{4C^{\prime}_{4}}\hbox{ for all }y\in A.$

Applying Lemma 8.4 (and recalling that $d_{2}\leqslant
2^{C_{3}}\eta^{-C^{\prime}_{3}}$ and
$\rho_{2}\geqslant\varepsilon_{2}=2^{-C_{3}-2C_{4}-10}\eta^{C^{\prime}_{3}+2C^{\prime}_{4}}$)
we conclude that

$\|2\\{x,y^{\prime}-y\\}\|_{\mathbb{R}/\mathbb{Z}}\leqslant
2^{24+2C_{3}+8C^{\prime}_{4}}\eta^{-2C^{\prime}_{3}-10C^{\prime}_{4}}\|x\|_{S}\hbox{
for all }x\in B_{2},y\in A.$

Applying (9.16) (and recalling that $\rho_{2}\leqslant
2\varepsilon\leqslant\frac{1}{32}$), we conclude that

$\|2\\{x,z\\}\|_{\mathbb{R}/\mathbb{Z}}\leqslant
2^{26+2C_{3}+8C^{\prime}_{4}}\eta^{-2C^{\prime}_{3}-10C^{\prime}_{4}}\|x\|_{S}\hbox{
for all }x\in B_{2},z\in 2A-2A.$

On the other hand, by applying Lemma 8.8, we can find
$S^{\prime}\subseteq\widehat{G}$ with $|S\cup S^{\prime}|\leqslant
2^{12C_{4}+16}\eta^{-12C^{\prime}_{4}}$ and a Bohr set
$B^{\prime}_{3}:=B(S\cup
S^{\prime},2^{-61-2C_{3}-26C_{4}}\eta^{2C^{\prime}_{3}+26C^{\prime}_{4}})$
which is completely contained in $2A-2A$ and inside $B_{2}$. Thus we have

$\|2\\{x,z\\}\|_{\mathbb{R}/\mathbb{Z}}\leqslant
2^{26+2C_{3}+8C^{\prime}_{4}}\eta^{-2C^{\prime}_{3}-10C^{\prime}_{4}}\|x\|_{S}\hbox{
for all }x,z\in B^{\prime}_{3}.$

Let us now eliminate the factor $2$. Observe that $B_{3}:=\\{2x:x\in
B^{\prime}_{3}\\}$ is also a Bohr set (with the frequency set $S\cup
S^{\prime}$ replaced by $S_{3}:=\frac{1}{2}\cdot(S\cup S^{\prime})$). Since
$\|x\|_{S}\leqslant 2\|x\|_{S_{3}}$, we also observe that $B_{3}\subseteq
B(S,2\rho_{2})\subseteq B_{1}$. By (9.16), which implies that
$\\{2x,z\\}=2\\{x,z\\}$, we conclude (9.8) as desired.

There are extremely close analogies between the above argument and that of §6.
Equations (9.9), (9.10), (9.11), (9.12), (9.13), (9.14), (9.15) and (9.17) are
analogous to (6.7), (6.8), (6.9), (6.10), (6.11), (6.12), (6.13) and (6.16)
respectively.

Step 3: Eliminating the quadratic phase component. We now return to the
conclusion of Proposition 9.3 and localize the $x$ and $h$ variables to a
small Bohr set. Let