# The inverse theorem for the nonlinear Roth configuration: an exposition

Sean Prendiville  Department of Mathematics and Statistics
Lancaster University
UK<EMAIL_ADDRESS>
###### Abstract.

We give an exposition of the inverse theorem for the cut-norm associated to
the nonlinear Roth configuration, established by Peluse and the author in [6].

###### Contents

  1. 1 Introduction
  2. 2 An outline of our argument
  3. 3 PET induction
  4. 4 An inverse theorem for the arithmetic box norm
  5. 5 Quantitative concatenation
  6. 6 Degree lowering
  7. 7 Proof of the cut norm inverse theorem
  8. A Basic theory of the Gowers norms

##  1\. Introduction

Peluse and the author recently obtained an effective bound on the density of
sets of integers lacking the configuration

$x,\ x+y,\ x+y^{2}\qquad(y\neq 0).$ (1.1)

We call this pattern the _nonlinear Roth configuration_ , after Bourgain and
Chang [1].

######  Theorem 1.1 (Peluse and Prendiville [6]).

There exists an absolute constant $c>0$ such that if
$A\subset\left\\{1,2,\dots,N\right\\}$ lacks the configuration (1.1), then

$|A|\ll N(\log\log N)^{-c}.$

We have since removed a logarithm from this bound.

######  Theorem 1.2 (Peluse and Prendiville [7]).

There exists an absolute constant $c>0$ such that if
$A\subset\left\\{1,2,\dots,N\right\\}$ lacks the configuration (1.1), then

$|A|\ll N(\log N)^{-c}.$

The main innovation behind both of these results is [6, Theorem 7.1], an
inverse theorem for the counting operator associated to this configuration. It
is the purpose of this note to give an exposition of this inverse theorem. The
approach is essentially the same as that in [6]. We hope that having two
distinct accounts is useful for those interested in utilising these ideas.

######  Definition 1.3 (Counting operator).

For positive integers $q\leq N$ write

$M:=\left\lfloor\sqrt{N/q}\right\rfloor.$ (1.2)

Given this, define the _counting operator_ on the functions
$f_{i}:\mathbb{Z}\to\mathbb{C}$ by

$\Lambda_{q,N}(f_{0},f_{1},f_{2}):=\mathbb{E}_{x\in[N]}\mathbb{E}_{y\in[M]}f_{0}(x)f_{1}(x+y)f_{2}(x+qy^{2}).$
(1.3)

When the $f_{i}$ all equal $f$ we simply write $\Lambda_{q,N}(f)$.

######  Definition 1.4 (Local function).

We call a function $\phi:\mathbb{Z}\to\mathbb{C}$ a _local function of
resolution $M$ and modulus $q$_ if there exists a partition of $\mathbb{R}$
into intervals of length $M$ such that $\phi$ is constant on the intersection
of every such interval with every congruence class mod $q$.

######  Definition 1.5 (Cut norm).

Define the _cut norm_ of $f:\mathbb{Z}\to\mathbb{C}$ by

$\left\|f\right\|_{q,N}:=\sup\\{|\Lambda_{q,N}(f,g_{1},g_{2})|,\
|\Lambda_{q,N}(g_{1},f,g_{2})|,\ |\Lambda_{q,N}(g_{1},g_{2},f)|\\},$ (1.4)

where the supremum is taken over all 1-bounded functions
$g_{i}:[N]\to\mathbb{C}$. We note that, in spite of our nomenclature, this is
not a norm but a seminorm. One could remedy this by summing over $y\geq 0$ in
the counting operator (1.3)

This seminorm is useful in [7]. However, it is too restrictive for the
approach developed in [6], where we (implicitly) only work with the following
quantities:

$\left\|f\right\|^{\sharp}_{q}:=\sup\\{|\Lambda_{q,N}(g_{0},g_{1},f)|:|g_{i}|\leq
1\ \text{ and }\ \mathrm{supp}(g_{i})\subset[N]\\}$ (1.5)

and

$\left\|f\right\|^{\flat}_{q}:=\sup\\{|\Lambda_{q,N}(f,g_{1},g_{2})|,\
|\Lambda_{q,N}(g_{1},f,g_{2})|\ :\ |g_{i}|\leq 1\ \text{ and }\
\mathrm{supp}(g_{i})\subset[N]\\}.$ (1.6)

Here then is a re-formulation and slight generalisation of [6, Theorem 7.1].

######  Theorem 1.6 (Partial cut norm inverse theorem).

Let $q\leq N$ be positive integers, $\delta>0$, and
$f:\mathbb{Z}\to\mathbb{C}$ be a $1$-bounded function with support in $[N]$.
Suppose that

$\left\|f\right\|^{\flat}_{q,N}\geq\delta.$

Then either $N\ll(q/\delta)^{O(1)}$ or there exists a 1-bounded local function
$\phi$ of resolution $\gg(\delta/q)^{O(1)}N^{1/2}$, modulus $qq^{\prime}$ for
some $q^{\prime}\ll\delta^{-O(1)}$, and such that

$\sum_{x\in[N]}f(x)\phi(x)\gg\delta^{2^{66}}N.$

This exposition is organised as follows. In §2, we give a more detailed
outline of the proof of Theorem 1.6. In §§3–5 we develop an effective approach
to a (special case of a) so-called _concatenation_ theorem of Tao and Ziegler
[10]. This allows us to show that if our counting operator is large, then the
function weighting the nonlinear term must have large Gowers uniformity norm.
The drawback is that the degree of the resulting Gowers norm is large (in our
approach it is the $U^{5}$-norm). In §6 we give a _degree-lowering_ procedure,
which utilises properties specific to our configuration to show that one may
replace the $U^{5}$-norm with the $U^{1}$-norm. In §7 we combine the results
of the previous sections in order to prove Theorem 1.6.

###  1.1. Notation

####  1.1.1. Standard conventions

We use $\mathbb{N}$ to denote the positive integers. For a real $X\geq 1$,
write $[X]=\\{1,2,\ldots,\left\lfloor X\right\rfloor\\}$. A complex-valued
function is _1-bounded_ if the modulus of the function does not exceed 1.

We use counting measure on $\mathbb{Z}$, so that for
$f,g:\mathbb{Z}\to\mathbb{C}$ we have

$\left\langle
f,g\right\rangle:=\sum_{x}f(x)\overline{g(x)}\qquad\text{and}\qquad\left\|f\right\|_{L^{p}}:=\biggl{(}\sum_{x}|f(x)|^{p}\biggr{)}^{\frac{1}{p}}.$

Any sum of the form $\sum_{x}$ is to be interpreted as a sum over
$\mathbb{Z}$. We use Haar probability measure on
$\mathbb{T}:=\mathbb{R}/\mathbb{Z}$, so that for measurable
$F:\mathbb{T}\to\mathbb{C}$ we have

$\left\|F\right\|_{L^{p}}:=\biggl{(}\int_{\mathbb{T}}|F(\alpha)|^{p}\mathrm{d}\alpha\biggr{)}^{\frac{1}{p}}=\biggl{(}\int_{0}^{1}|F(\alpha)|^{p}\mathrm{d}\alpha\biggr{)}^{\frac{1}{p}}$

For $\alpha\in\mathbb{T}$ we write $\left\|\alpha\right\|$ for the distance to
the nearest integer.

For a finite set $S$ and function $f:S\to\mathbb{C}$, denote the average of
$f$ over $S$ by

$\mathbb{E}_{s\in S}f(s):=\frac{1}{|S|}\sum_{s\in S}f(s).$

Given functions $f,g:G\to\mathbb{C}$ on an additive group with measure
$\mu_{G}$ we define their convolution by

$f*g(x):=\int_{G}f(x-y)g(y)\mathrm{d}\mu_{G},$ (1.7)

when this makes sense.

We define the Fourier transform of $f:\mathbb{Z}\to\mathbb{C}$ by

$\hat{f}(\alpha):=\sum_{x}f(x)e(\alpha x)\qquad(\alpha\in\mathbb{T}),$ (1.8)

again, when this makes sense. Here $e(\alpha)$ stands for $e^{2\pi i\alpha}$.

The difference function of $f:\mathbb{Z}\to\mathbb{C}$ is the function
$\Delta_{h}f:\mathbb{Z}\to\mathbb{C}$ given by

$\Delta_{h}f(x)=f(x)\overline{f(x+h)}.$

Iterating gives

$\Delta_{h_{1},\dots,h_{s}}f:=\Delta_{h_{1}}\dots\Delta_{h_{s}}f.$

This allows us to define the Gowers $U^{s}$-norm

$\left\|f\right\|_{U^{s}}:=\left(\sum_{x,h_{1},\dots,h_{s}}\Delta_{h_{1},\dots,h_{s}}f(x)\right)^{1/2^{s}}.$
(1.9)

If $\|\cdot\|$ is a seminorm on an inner product space, recall that its dual
seminorm $\|\cdot\|^{*}$ is defined by

$\|f\|^{*}:=\sup_{\|g\|\leq 1}|\langle f,g\rangle|.$

Hence

$\left|\left\langle
f,g\right\rangle\right|\leq\left\|f\right\|^{*}\left\|g\right\|.$ (1.10)

For a function $f$ and positive-valued function $g$, write $f\ll g$ or
$f=O(g)$ if there exists a constant $C$ such that $|f(x)|\leq Cg(x)$ for all
$x$. We write $f=\Omega(g)$ if $f\gg g$. We sometimes opt for a more explicit
approach, using $C$ to denote a large absolute constant, and $c$ to denote a
small positive absolute constant. The values of $C$ and $c$ may change from
line to line.

####  1.1.2. Local conventions

Up to normalisation, all of the above are well-used in the literature. Next we
list notation specific to our paper. We have tried to minimise this in order
to aid the casual reader.

For a real parameter $H\geq 1$, we use $\mu_{H}:\mathbb{Z}\to[0,1]$ to
represent the following normalised Fejér kernel

$\mu_{H}(h):=\frac{1}{\left\lfloor
H\right\rfloor}\left(1-\frac{|h|}{\left\lfloor
H\right\rfloor}\right)_{+}=\frac{(1_{[H]}*1_{[H]})(h)}{\left\lfloor
H\right\rfloor^{2}}.$ (1.11)

For a multidimensional vector $h\in\mathbb{Z}^{d}$ we write

$\mu_{H}(h):=\mu_{H}(h_{1})\dotsm\mu_{H}(h_{d}).$ (1.12)

We observe that this is a probability measure on $\mathbb{Z}^{d}$ with support
in the interval $(-H,H)^{d}$.

##  2\. An outline of our argument

In this section we describe the ideas behind Theorem 1.6. In the hope of
making the ideas clearer, we make the simplification that $q=1$ in our
counting operator (1.3). Hence, for finitely supported functions
$f_{0},f_{1},f_{2}:\mathbb{Z}\to\mathbb{C}$, write

$\Lambda(f_{0},f_{1},f_{2}):=\mathbb{E}_{x\in[N]}\mathbb{E}_{y\in[N^{1/2}]}f_{0}(x)f_{1}(x+y)f_{2}(x+y^{2}).$
(2.1)

For this operator, Theorem 1.6 can be deduced from the following.

######  Lemma 2.1.

Let $f_{0},f_{1},f_{2}:\mathbb{Z}\to\mathbb{C}$ be $1$-bounded functions
supported in the interval $[N]$ and $\delta>0$. Suppose that

$|\Lambda(f_{0},f_{1},f_{2})|\geq\delta.$

Then either $N\ll\delta^{-O(1)}$ or there exist positive integers
$q\ll\delta^{-O(1)}$ and $N^{\prime}\gg\delta^{O(1)}N^{1/2}$ such that

$\sum_{x}\left|\sum_{y\in[N^{\prime}]}f_{1}(x+qy)\right|\gg\delta^{O(1)}NN^{\prime}.$
(2.2)

Using the notation (1.9), notice that the left-hand side of (2.2) is equal to

$\sum_{x}\left\|f_{1}\right\|_{U^{1}(x+q\cdot[N^{\prime}])}.$

###  2.1. Quantitative concatenation

To prove Lemma 2.1, we first prove that our counting operator (2.1) is
controlled by the $U^{5}$-norm of $f_{2}$. The purpose of this subsection is
to sketch how we do this with polynomial bounds.

By applying the Cauchy–Schwarz and van der Corput inequalities a number of
times, we show in §3 that, when $f_{0},f_{1},f_{2}:\mathbb{Z}\to\mathbb{C}$
are $1$-bounded functions supported in the interval $[N]$, largeness of the
counting operator (2.1) implies largeness of the sum

$\sum_{a,b\in[N^{1/2}]}\sum_{h_{1},h_{2},h_{3}\in[N^{1/2}]}\sum_{x}\Delta_{ah_{1},bh_{2},(a+b)h_{3}}f_{2}(x).$
(2.3)

This deduction is made following the PET induction scheme of Bergelson and
Leibman [2]. The gain in working with the counting operator (2.3) over (2.1)
is that univariate polynomials such as $y^{2}$, whose image constitute a
sparse set, have been replaced by bilinear forms such as $ah_{1}$, whose image
is much denser

In §§4–5, we show that largeness of (2.3) implies largeness of
$\|f_{2}\|_{U^{5}}$. If there were no dependence between the coefficients of
the $h_{i}$ in (2.3), then we could in fact bound (2.3) in terms of
$\|f_{2}\|_{U^{3}}$. Since the argument is informative, we illustrate why this
is the case for the sum

$\sum_{a,b,c\in[N^{1/2}]}\sum_{h_{1},h_{2},h_{3}\in[N^{1/2}]}\sum_{x}\Delta_{ah_{1},bh_{2},ch_{3}}f_{2}(x).$
(2.4)

The following fact is key, the formal version of which is Lemma 5.3.

######  Claim 2.2.

If $\displaystyle\sum_{a,h\in[N^{1/2}]}\sum_{x}\Delta_{ah}f(x)$ is large then
so is $\displaystyle\sum_{k\in(-N,N)}\sum_{x}\Delta_{k}f(x)$.

###### Sketch proof.

Apply the Cauchy–Schwarz inequality to double the $a$ and $h$ variables,
yielding a bound in terms of

$\sum_{a,a^{\prime}\in[N^{1/2}]}\sum_{h,h^{\prime}\in[N^{1/2}]}\sum_{x}\Delta_{ah-a^{\prime}h^{\prime}}f(x).$
(2.5)

For a random choice of $a,a^{\prime}\in[N^{1/2}]$, the progression
$a\cdot[N^{1/2}]-a^{\prime}\cdot[N^{1/2}]$ covers a large portion of the
interval $(-N,N)$ relatively smoothly. One can make this intuition rigorous
and thus deduce largeness of the sum
$\sum_{k\in(-N,N)}\sum_{x}\Delta_{k}f(x).$∎

Applying Claim 2.2 three times allows us to replace each of $ah_{1}$, $bh_{2}$
and $ch_{3}$ in (2.4) with $k_{1},k_{2},k_{3}\in(-N,N)$, yielding largeness of
$\left\|f_{2}\right\|_{U^{3}}$.

Since the PET induction scheme outputs (2.3), and not (2.4), the problem
remains of how to handle the dependency between the differencing parameters in
(2.3). If we were not concerned with quantitative bounds, we could apply a
‘concatenation’ theorem of Tao and Ziegler [10, Theorem 1.24] to obtain
largeness of the $U^{9}$-norm of $f_{2}$. However, the qualitative nature of
this argument means that it cannot be used to obtain bounds in the nonlinear
Roth theorem. In its place we prove Theorem 5.6, which is a special case of
[10, Theorem 1.24], using a very different argument that gives polynomial
bounds. We spend the remainder of this subsection sketching the argument.

We begin by viewing (2.3) as the average

$\sum_{a,h_{1}\in[N^{1/2}]}\left\|\Delta_{ah_{1}}f_{2}\right\|_{a},$ (2.6)

where

$\|f\|_{a}^{4}:=\sum_{b\in[N^{1/2}]}\sum_{h_{2},h_{3}\in[N^{1/2}]}\sum_{x}\Delta_{bh_{2},(a+b)h_{3}}f(x)$
(2.7)

One can view this as an average of 2-dimensional Gowers box norms where, for
fixed $b$, the inner sum corresponds to a box norm in the ‘directions’ $b$ and
$a+b$. Note that if we could bound the quantity $\|\Delta_{ah_{1}}f_{2}\|_{a}$
in terms of the $U^{4}$-norm of $\Delta_{ah_{1}}f_{2}$ for many pairs
$(a,h_{1})$, then by Claim 2.2 we deduce largeness of the $U^{5}$-norm of
$f_{2}$. We show that, on average, one can indeed control $\|\cdot\|_{a}$ in
terms of $\|\cdot\|_{U^{4}}$, with polynomial bounds. The following can be
extracted from the proof of (the more general) Theorem 5.6.

######  Lemma 2.3.

For each $a\in[N^{1/2}]$ let $f_{a}:\mathbb{Z}\to\mathbb{C}$ be a $1$-bounded
function supported in the interval $[N]$. Suppose that

$\mathbb{E}_{a\in[N^{1/2}]}\|f_{a}\|_{a}^{4}\geq\delta\left\|1_{[N]}\right\|_{a}^{4}.$

Then

$\mathbb{E}_{a\in[N^{1/2}]}\|f_{a}\|_{U^{4}}^{16}\gg\delta^{O(1)}\left\|1_{[N]}\right\|_{U^{4}}^{16}.$

To finish this subsection, we briefly discuss the proof of this key lemma. For
most choices of $a,b\in[N^{1/2}]$, the ‘directions’ $a$ and $a+b$ of the box
norm

$\sum_{h_{2},h_{3}\in[N^{1/2}]}\sum_{x}\Delta_{bh_{2},(a+b)h_{3}}f_{a}(x)$
(2.8)

are close to ‘independent’, in the sense that at least one of the directions
$a$ and $a+b$ is large and together they have small greatest common divisor.
The proof of Lemma 2.3 thus begins by viewing $\|\cdot\|_{a}$ as an average of
box norms

$\|f\|_{\square(X,Y)}^{4}:=\sum_{x_{1},x_{2}\in X,y_{1},y_{2}\in
Y}f(x_{1},y_{1})\overline{f(x_{1},y_{2})f(x_{2},y_{1})}f(x_{2},y_{2}).$ (2.9)

It is easy to show that largeness of $\|f\|_{\square(X,Y)}$ implies that $f$
correlates with a function of the form $(x,y)\mapsto l(x)r(y)$. We show,
analogously, that provided $b$ and $a+b$ are not too small and have greatest
common divisor not too large, then largeness of the arithmetic box norm (2.8)
implies that $f_{a}$ correlates with a product $g_{b}h_{a+b}$ of 1-bounded
functions, where $g_{b}$ is $b$-periodic and $h_{a+b}$ is almost periodic
under shifts by integer multiples of $a+b$. As a consequence, for most
$a\in[N^{1/2}]$, largeness of $\|f_{a}\|_{a}$ implies largeness of

$\sum_{b\in[N^{1/2}]}\sum_{x}f_{a}(x)g_{b}(x)h_{a+b}(x).$ (2.10)

In fact, an application of Cauchy–Schwarz allows us give an explicit
description of $h_{a+b}$ in terms of $f_{a}$, namely we may take it to be of
the form

$h_{a+b}(x)=\mathbb{E}_{k\in[N^{1/2}]}f_{a}(x+(a+b)k)g_{b}(x+(a+b)k).$ (2.11)

This presentation makes apparent the almost periodicity of $h_{a+b}$.

######  Claim 2.4.

Largeness of (2.10) implies that $\mathbb{E}_{b\in[N^{1/2}]}h_{a+b}$ has large
$U^{3}$-norm.

Let us first show why Claim 2.4 in turn implies that $f_{a}$ has large
$U^{4}$-norm, completing our sketch proof of Lemma 2.3. The expression (2.11)
and the triangle inequality for Gowers norms together imply that largeness of
$\mathbb{E}_{b\in[N^{1/2}]}\left\|h_{a+b}\right\|_{U^{3}}$ implies largeness
of $\mathbb{E}_{b\in[N^{1/2}]}\left\|f_{a}g_{b}\right\|_{U^{3}}$. Utilising
the $b$-periodicity of $g_{b}$ we have

$\left\|f_{a}g_{b}\right\|_{U^{3}}=\mathbb{E}_{k\in[N^{1/2}]}\left\|f_{a}(\cdot)g_{b}(\cdot+bk)\right\|_{U^{3}}.$
(2.12)

The product $f_{a}(\cdot)g_{b}(\cdot+bk)$ resembles a difference function in
the direction $b$. Indeed the Gowers–Cauchy–Schwarz inequality (see [9,
Exercise 1.3.19]) shows that if (2.12) is large (on average over
$b\in[N^{1/2}]$) then so is

$\mathbb{E}_{b,k\in[N^{1/2}]}\left\|\Delta_{bk}f_{a}\right\|_{U^{3}}$

Largeness of $\left\|f_{a}\right\|_{U^{4}}$ then follows from Claim 2.2.

Finally we sketch the proof of Claim 2.4. The Cauchy–Schwarz inequality allows
us to remove the weight $f_{a}(x)$ from (2.10) and deduce largeness of

$\sum_{x}\sum_{b,b^{\prime}\in[N^{1/2}]}\overline{g_{b}(x)h_{a+b}(x)}g_{b^{\prime}}(x)h_{a+b^{\prime}}(x).$

Using the periodicity properties of $g_{b}$, $g_{b^{\prime}}$ and $h_{a+b}$,
this is approximately equal to

$\sum_{x}\sum_{\begin{subarray}{c}b,b^{\prime}\in[N^{1/2}]\\\
k_{1},k_{2},k_{3}\in[N^{1/2}]\end{subarray}}\overline{g_{b}(x-bk_{1})h_{a+b}(x-(a+b)k_{2})}g_{b^{\prime}}(x-b^{\prime}k_{3})h_{a+b^{\prime}}(x).$

Changing variables in $x$, we obtain largeness of the sum

$\sum_{x}\sum_{\begin{subarray}{c}b,b^{\prime}\in[N^{1/2}]\\\
k_{1},k_{2},k_{3}\in[N^{1/2}]\end{subarray}}\overline{g_{b}(x+(a+b)k_{2}+b^{\prime}k_{3})h_{a+b}(x+bk_{1}+b^{\prime}k_{3})}\\\
g_{b^{\prime}}(x+bk_{1}+(a+b)k_{2})h_{a+b^{\prime}}(x+bk_{1}+(a+b)k_{2}+b^{\prime}k_{3}).$

The point here is that all but the last function have arguments depending on
at most two of the bilinear forms $bk_{1}$, $(a+b)k_{2}$ and
$b^{\prime}k_{1}^{\prime}$. This enables us to employ the
Gowers–Cauchy–Schwarz inequality (in the form of Lemma A.4) to deduce
largeness of a sum similar to

$\sum_{x}\sum_{\begin{subarray}{c}b,b^{\prime}\in[N^{1/2}]\\\
k_{1},k_{2},k_{3}\in[N^{1/2}]\end{subarray}}\Delta_{bk_{1},\,(a+b)k_{2},\,b^{\prime}k_{3}}h_{a+b^{\prime}}(x).$

The utility of this expression is that the directions of the differencing
parameters are all ‘independent’ of the direction of periodicity of
$h_{a+b^{\prime}}$. Indeed the approximate $(a+b^{\prime})$-periodicity of
$h_{a+b^{\prime}}$ means that one can replace $\Delta_{y}h_{a+b^{\prime}}$
with $\mathbb{E}_{k}\Delta_{y+(a+b^{\prime})k}h_{a+b^{\prime}}$ at the cost of
a small error. We thereby obtain largeness of

$\sum_{x}\sum_{b,b^{\prime}\in[N^{1/2}]}\sum_{\begin{subarray}{c}k_{1},k_{2},k_{3}\in[N^{1/2}]\\\
k_{1}^{\prime},k_{2}^{\prime},k_{3}^{\prime}\in[N^{1/2}]\end{subarray}}\Delta_{bk_{1}+(a+b^{\prime})k_{1}^{\prime},\,(a+b)k_{2}+(a+b^{\prime})k_{2}^{\prime},\,b^{\prime}k_{3}+(a+b^{\prime})k_{3}^{\prime}}h_{a+b^{\prime}}(x).$
(2.13)

For a random triple $(a,b,b^{\prime})\in[N^{1/2}]$ the greatest common divisor
of the pairs $(b,a+b^{\prime})$, $(a+b,a+b^{\prime})$ and
$(b^{\prime},a+b^{\prime})$ are all small, and these are the pairs appearing
in the differencing parameters of (2.13). The argument used to treat (2.5) may
be therefore be employed to replace (2.13) with

$\sum_{x}\sum_{b^{\prime}\in[N^{1/2}]}\sum_{k_{1},k_{2},k_{3}\in[N]}\Delta_{k_{1},k_{2},k_{3}}h_{a+b^{\prime}}(x),$

and thereby yield Claim 2.4.

###  2.2. Degree lowering

After we have shown that $\Lambda(f_{0},f_{1},f_{2})$ is controlled by the
$U^{5}$-norm of $f_{2}$, we carry out a ‘degree lowering’ argument. This
technique originated in the work [5] in finite fields. The basic idea is that,
under certain conditions, one can combine $U^{s}$-control with understanding
of two-term progressions to deduce $U^{s-1}$-control. Repeating this gives a
sequence of implications

$U^{5}\text{-control}\implies U^{4}\text{-control}\implies
U^{3}\text{-control}\implies U^{2}\text{-control}\implies
U^{1}\text{-control}.$

Despite the appearance of the $U^{5}$-norm, $U^{4}$-norm, and $U^{3}$-norm,
the degree lowering argument, both in [5] and here, does not require the
$U^{s}$-inverse theorem for any $s\geq 3$. Instead it relies on Fourier
analysis in the place of these inverse theorems.

Adapting the degree lowering argument of [5] to the integer setting requires
several significant modifications. The first modification is that the
$U^{s}$-control described above is control in terms of the $U^{s}$-norm of the
dual function

$F(x):=\mathbb{E}_{y\in[N^{1/2}]}f_{0}(x-y^{2})f_{1}(x+y-y^{2}).$ (2.14)

Thus, to begin the degree lowering argument, we must show that largeness of
$\Lambda(f_{0},f_{1},f_{2})$ implies largeness of $\|F\|_{U^{5}}$. To do this,
we use a simple Hahn–Banach decomposition as described in [3, Proposition
3.6], for details see §7.

We conclude this section by sketching an instance of degree-lowering: how
$U^{3}$-control of the dual (2.14) implies $U^{2}$-control, starting from the
assumption that

$\|F\|_{U^{3}}^{8}\geq\delta\left\|1_{[N]}\right\|_{U^{3}}^{8}.$

Using the fact that $\|F\|_{U^{3}}^{8}=\sum_{h}\|\Delta_{h}F\|_{U^{2}}^{4}$
and applying the $U^{2}$-inverse theorem, we deduce the existence of a
function $\phi:\mathbb{Z}\to\mathbb{T}$ such that, for at least $\gg\delta N$
choices of differencing parameter $h$, we have

$\left|\sum_{x\in[N]}\Delta_{h}F(x)e(\phi(h)x)\right|\gg\delta N.$ (2.15)

Note that if, in the above inequality, we could replace the function $\phi(h)$
by a constant $\beta\in\mathbb{T}$ not depending on $h$, then we could easily
deduce largeness of $\|F\|_{U^{2}}$. Indeed, writing $g(h)$ for the phase of
the sum inside absolute values, this would give

$\sum_{x,h}\overline{g(h)}\overline{F(x+h)}F(x)e(\beta
x)\gg\delta^{O(1)}N^{3},$

and the usual argument111One can either use orthogonality and extraction of a
large Fourier coefficient, as in the proof of Lemma A.1, or use two
applications of Cauchy–Schwarz. showing $U^{2}$-control of the equation
$x+y=z$ implies that
$\|F\|_{U^{2}}^{4}\gg\delta^{O(1)}\left\|1_{[N]}\right\|_{U^{2}}$. It thus
remains to show that such a $\beta$ exists.

Expanding the definition of the difference and dual functions in (2.15), and
using the Cauchy–Schwarz inequality (as is done in greater generality in the
proof of Lemma 6.3), one can show that there exists $h^{\prime}$ such that for
many $h$ satisfying (2.15) we have

$\left|\sum_{x}\sum_{y\in[N^{1/2}]}\Delta_{h-h^{\prime}}f_{0}(x)\Delta_{h-h^{\prime}}f_{1}(x+y)e([\phi(h)-\phi(h^{\prime})][x+y^{2}])\right|\gg\delta^{O(1)}N^{3/2}$

Further application of Cauchy–Schwarz allows us to remove the difference
functions from the above inequality and deduce largeness of the exponential
sum

$\sum_{z\in[N^{1/2}]}\left|\sum_{y\in[N^{1/2}]}e(2\left[\phi(h)-\phi(h^{\prime})\right]yz)\right|.$

Summing the inner geometric progression and using a Vinogradov-type lemma then
shows that $\phi(h)-\phi(h^{\prime})$ is major arc. There are very few major
arcs, so the pigeonhole principle gives the existence of
$\beta_{0}\in\mathbb{T}$ such that $\phi(h)-\phi(h^{\prime})$ is very close to
$\beta_{0}$ for many $h\in(-N,N)$ that also satisfy (2.15). We may therefore
take $\beta=\beta_{0}+\phi(h^{\prime})$ in the argument following (2.15).

##  3\. PET induction

We prove Theorem 1.6 over the course of §§3–7. We begin in §§3–5 by showing
how our counting operator $\Lambda_{q,N}(f_{0},f_{1},f_{2})$, as defined in
(1.3), is controlled by the $U^{5}$-norm of $f_{2}$. This argument starts with
the PET induction scheme of Bergelson–Leibman [2], which in some sense
‘linearises’ a polynomial progression, replacing univariate polynomials such
as $y^{2}$ with bilinear forms $ah$. The outcome of this procedure is Lemma
3.3.

For the following, we recall our definition (1.11) of $\mu_{H}$.

######  Lemma 3.1 (van der Corput inequality).

Let $f:\mathbb{Z}\to\mathbb{C}$ be 1-bounded and $M,H\geq 1$. Then we have the
estimate

$\biggl{|}\mathbb{E}_{y\in[M]}f(y)\biggr{|}^{2}\leq\frac{M+H}{M}\sum_{h}\mu_{H}(h)\mathbb{E}_{y\in[M]}\Delta_{h}f(y).$

###### Proof.

This is standard, see for instance [8, Lemma 3.1].∎

######  Lemma 3.2 (Difference functions control linear configurations).

Let $f_{i}:\mathbb{Z}\to\mathbb{C}$ be $1$-bounded functions with support in
an interval $I_{i}$ of size $|I_{i}|=N$. Then for any $a,b\in\mathbb{Z}$ and
$1\leq H\leq M$ we have

$\biggl{|}\mathbb{E}_{x\in
I_{0}}\mathbb{E}_{y\in[M]}f_{0}(x)f_{1}(x+ay)f_{2}(x+by)f_{3}(x+(a+b)y)\biggr{|}^{8}\\\
\ll\sum_{h}\mu_{H}(h)\mathbb{E}_{x\in
I_{3}}\Delta_{ah_{1},bh_{2},(a+b)h_{3}}f_{3}(x).$ (3.1)

###### Proof.

Applying Cauchy-Schwarz in the $x$ variable gives

$\biggl{|}\mathbb{E}_{x\in
I_{0}}\mathbb{E}_{y\in[M]}f_{0}(x)f_{1}(x+ay)f_{2}(x+by)f_{3}(x+(a+b)y)\biggr{|}^{2}\\\
\leq\frac{1}{N}\sum_{x}\bigg{|}\mathbb{E}_{y\in[M]}f_{1}(x+ay)f_{2}(x+by)f_{3}(x+(a+b)y)\bigg{|}^{2}.$

Bounding the inner sum using van der Corput’s inequality (Lemma 3.1) and
making the change of variables $x\mapsto x-ay$ (valid since $x$ is ranging
over $\mathbb{Z}$), the latter is at most

$2\sum_{h_{1}}\mu_{H}(h_{1})\mathbb{E}_{x\in
I_{1}}\mathbb{E}_{y\in[M]}\Delta_{ah_{1}}f_{1}(x)\Delta_{bh_{1}}f_{2}(x+(b-a)y)\Delta_{(a+b)h_{1}}f_{3}(x+by).$

Here we may restrict $x$ to $I_{1}$ on observing that the support of
$\Delta_{ah_{1}}f_{1}$ is contained in the support of $f_{1}$. Making use of
the fact that $\mu_{H}$ is a probability measure, we repeat the procedure of
applying Cauchy–Schwarz, van der Corput then a change of variables, to deduce
that

$\biggl{|}\mathbb{E}_{x\in
I_{0}}\mathbb{E}_{y\in[M]}f_{0}(x)f_{1}(x+ay)f_{2}(x+by)f_{3}(x+(a+b)y)\biggr{|}^{4}\\\
\leq 8\sum_{h_{1},h_{2}}\mu_{H}(h_{1})\mu_{H}(h_{2})\mathbb{E}_{x\in
I_{2}}\mathbb{E}_{y\in[M]}\Delta_{bh_{1},(b-a)h_{2}}f_{2}(x)\Delta_{(a+b)h_{1},bh_{2}}f_{3}(x+ay).$

A final iteration of the same procedure then yields (3.1). ∎

Before embarking on the following, we remind the reader of our convention
(1.2) regarding $M$.

######  Lemma 3.3 (Linearisation).

Let $f_{i}:\mathbb{Z}\to\mathbb{C}$ be $1$-bounded functions, each with
support in the interval $[N]$. Then for any $1\leq H\leq M$ we have

$\left|\Lambda_{q,N}(f_{0},f_{1},f_{2})\right|^{32}\ll\sum_{a,b,h}\mu_{M}(a)\mu_{M}(b)\mu_{H}(h)\mathbb{E}_{x\in[N]}\Delta_{2q(a+b)h_{1},\,2qbh_{2},\,2qah_{3}}f_{2}(x).$
(3.2)

###### Proof.

We repeat the procedure given in the proof of Lemma 3.2, applying Cauchy-
Schwarz, followed by van der Corput’s inequality and a change of variables. A
first application gives

$\left|\Lambda_{q,N}(f_{0},f_{1},f_{2})\right|^{2}\leq\\\
2\sum_{a}\mu_{M}(a)\mathbb{E}_{x\in[N]}\mathbb{E}_{y\in[M]}\Delta_{a}f_{1}(x)f_{2}\bigl{(}x+qy^{2}-y\bigr{)}\overline{f_{2}\bigl{(}x+q(y+a)^{2}-y\bigr{)}}.$

A second application then gives

$\left|\Lambda_{q,N}(f_{0},f_{1},f_{2})\right|^{4}\ll\sum_{a,b}\mu_{M}(a)\mu_{M}(b)\mathbb{E}_{x\in[N]}\mathbb{E}_{y\in[M]}f_{2}(x)\overline{f_{2}\bigl{(}x+2qay+qa^{2}\bigr{)}}\\\
\overline{f_{2}\bigl{(}x+2qby+qb^{2}-b\bigr{)}}f_{2}\bigl{(}x+2q(a+b)y+q(a+b)^{2}-b\bigr{)}.$

Applying Lemma 3.2 to bound the inner sum over $x$ and $y$, we obtain (3.2)
after a final change of variables ∎

##  4\. An inverse theorem for the arithmetic box norm

The objective in this section is to characterise those 1-bounded functions
$f:\mathbb{Z}\to\mathbb{C}$ with support in $[N]$ for which the following
quantity is large

$\sum_{h,x}\mu_{H}(h)\Delta_{ah_{1},bh_{2}}f(x).$ (4.1)

One can think of this as an arithmetic analogue of the two-dimensional ‘box
norm’ (2.9). In our eventual application we are able to ensure that $a$ and
$b$ are a generic pair of integers from the interval $[N^{1/2}]$. In
particular, at least one of them has size proportional to $N^{1/2}$ and their
highest common factor is small. One may think of this as a proxy for linear
independence.

We begin by characterising largeness of (4.1) when the directions are coprime.

######  Lemma 4.1 (Inverse theorem for the arithmetic box norm).

Let $a,b$ be positive integers with $\gcd(a,b)=1$. Suppose that
$f:\mathbb{Z}\to\mathbb{C}$ is $1$-bounded with support in the interval $[N]$
and satisfies

$\sum_{h,x}\mu_{H}(h)\Delta_{ah_{1},bh_{2}}f(x)\geq\delta N.$ (4.2)

Then there exist 1-bounded functions $g,h:\mathbb{Z}\to\mathbb{C}$ such that

  * •

$g$ is $a$-periodic, in the sense that $g(x+a)=g(x)$ for all $x$;

  * •

$h$ is approximately $b$-periodic, in the sense that for any $\varepsilon>0$
we have

$\\#\left\\{x\in[N]:h(x+by)\neq h(x)\text{ for some }|y|\leq\varepsilon
N/b\right\\}\leq\left(1+\tfrac{2\varepsilon
N}{b}\right)\left(1+\tfrac{N}{a}\right);$

and furthermore

$\biggl{|}\sum_{x}f(x)g(x)h(x)\biggr{|}\geq\delta\left\lfloor
H\right\rfloor^{2}-2\left(\tfrac{H}{a}+\tfrac{Hb}{N}\right)\left\lfloor
H\right\rfloor^{2}.$ (4.3)

######  Remark.

In parsing the above inequalities, it may be helpful to keep in mind that in
our application $a$, $b$ and $H$ are of order $\sqrt{N}$, with $H$
considerably smaller than $a$, in which case the lower bound in (4.3) becomes
$\Omega(\delta H^{2})$.

###### Proof.

The majority of our proof is concerned with manipulating (4.2) until we can
interpret it as a genuine box norm (2.9), and thereby apply the box norm
inverse theorem. The essential observation is that, since $\gcd(a,b)=1$, every
integer $x$ can be uniquely represented in the form

$x=ay+bz\qquad(y\in\mathbb{Z},\ z\in[a]).$

We note that if $x\in[N]$ then the constraint on $z$ forces $y$ to lie in the
range $-b<y<N/a$.

Defining $F:\mathbb{Z}\times\mathbb{Z}\to\mathbb{C}$ by $F(y,z):=f(ay+bz)$,
the left-hand side of (4.2) becomes

$\sum_{y,y^{\prime}\in\mathbb{Z}}\sum_{\begin{subarray}{c}z\in[a]\\\
z^{\prime}\in\mathbb{Z}\end{subarray}}F(y,z)\overline{F(y^{\prime},z)}\overline{F(y,z^{\prime})}F(y^{\prime},z^{\prime})\mu_{H}(y^{\prime}-y)\mu_{H}(z^{\prime}-z).$

If $z^{\prime}$ and $z$ contribute to the above sum then $z^{\prime}\in
z+(-H,H)\subset(-H+1,a+H).$ Hence we can restrict the range of summation of
$z^{\prime}$ to $[a]$, at the cost of perturbing the sum by at most
$2\left\lfloor H\right\rfloor(\frac{N}{a}+b).$ It follows that

$\biggl{|}\sum_{y,y^{\prime}}\sum_{z,z^{\prime}\in[a]}F(y,z)\overline{F(y^{\prime},z)}\overline{F(y,z^{\prime})}F(y^{\prime},z^{\prime})\mu_{H}(y^{\prime}-y)\mu_{H}(z^{\prime}-z)\biggr{|}\\\
\geq\delta N-2\left\lfloor H\right\rfloor\left(\tfrac{N}{a}+b\right).$

We remove the Fejér kernels by Fourier expansion:

$\sum_{\begin{subarray}{c}y,y^{\prime}\\\
z,z^{\prime}\in[a]\end{subarray}}F(y,z)\overline{F(y^{\prime},z)F(y,z^{\prime})}F(y^{\prime},z^{\prime})\mu_{H}(y^{\prime}-y)\mu_{H}(z^{\prime}-z)=\\\
\int_{\mathbb{T}^{2}}\sum_{\begin{subarray}{c}y,y^{\prime}\\\
z,z^{\prime}\in[a]\end{subarray}}F(y,z)\overline{F(y^{\prime},z)F(y,z^{\prime})}F(y^{\prime},z^{\prime})\hat{\mu}_{H}(\alpha)\hat{\mu}_{H}(\beta)e(\alpha(y^{\prime}-y)+\beta(z^{\prime}-z))\mathrm{d}\alpha\mathrm{d}\beta\\\
\leq\left(\int_{\mathbb{T}}|\hat{\mu}_{H}(\alpha)|\mathrm{d}\alpha\right)^{2}\sup_{\alpha,\beta\in\mathbb{T}}\biggl{|}\sum_{\begin{subarray}{c}y,y^{\prime}\\\
z,z^{\prime}\in[a]\end{subarray}}F(y,z)F_{2}(y^{\prime},z)F_{3}(y,z^{\prime})F_{4}(y^{\prime},z^{\prime})\biggr{|},$

where $F_{2}(y^{\prime},z):=\overline{F(y^{\prime},z)}e(-\beta z)$,
$F_{3}(y,z^{\prime}):=\overline{F(y,z^{\prime})}e(-\alpha y)$, and
$F_{4}(y^{\prime},z^{\prime})$ $:=F(y^{\prime},z^{\prime})e(\alpha
y^{\prime}+\beta z^{\prime})$.

We observe that
$\hat{\mu}_{H}(\alpha)=|\hat{1}_{[H]}(\alpha)|^{2}/\left\lfloor
H\right\rfloor^{2}$, which implies that
$\int_{\mathbb{T}}|\hat{\mu}(\alpha)|d\alpha=\left\lfloor
H\right\rfloor^{-1}$. Therefore

$\biggl{|}\sum_{\begin{subarray}{c}y,y^{\prime}\\\
z,z^{\prime}\in[a]\end{subarray}}F(y,z)F_{2}(y^{\prime},z)F_{3}(y,z^{\prime})F_{4}(y^{\prime},z^{\prime})\biggr{|}\geq\delta\left\lfloor
H\right\rfloor^{2}N-2\left\lfloor
H\right\rfloor^{3}\left(\tfrac{N}{a}+b\right),$ (4.4)

for $1$-bounded functions $F_{i}:\mathbb{Z}\times[a]\to\mathbb{C}$ of the form
$F_{i}(y,z)=f(ay+bz)e(\alpha_{1}y+\alpha_{2}z)$. Since $f$ is supported on
$[N]$, there are exactly $N$ pairs
$(y^{\prime},z^{\prime})\in\mathbb{Z}\times[a]$ for which
$F(y^{\prime},z^{\prime})\neq 0$. Thus, by pigeonholing in $y^{\prime}$ and
$z^{\prime}$ in (4.4) and setting $L(y):=F_{3}(y,z^{\prime})$ and
$R(z):=F_{2}(y^{\prime},z)F_{4}(y^{\prime},z^{\prime})$, we get that

$\biggl{|}\sum_{y}\sum_{z\in[a]}F(y,z)L(y)R(z)\biggr{|}\geq\delta\left\lfloor
H\right\rfloor^{2}-2\left\lfloor
H\right\rfloor^{3}\left(\tfrac{1}{a}+\tfrac{b}{N}\right).$

For each $x\in\mathbb{Z}$, define $l(x)\in\mathbb{Z}$ and $r(x)\in[a]$ by
$x=al(x)+br(x)$, and set $g(x):=R\circ r(x)$ and $h(x):=L\circ l(x)$. Then it
remains to check the invariance properties of $g$ and $h$. To see that
$g(x)=g(x+ay)$ for all $x,y\in\mathbb{Z}$, just note that $r(x)=r(x+ay)$ for
every $x,y\in\mathbb{Z}$.

Finally we establish that, for most $x\in[N]$, we have $h(x)=h(x+bz)$ for all
$|z|\leq\varepsilon N/b$. First note that $l(x)=l(x+bz)$ whenever $\varepsilon
N/b<r(x)\leq a-\varepsilon N/b$. Hence for this to fail, $x$ must lie in one
of at most $1+2\varepsilon N/b$ congruence classes modulo $a$. The number of
such $x$ lying in the interval $[N]$ is at most

$\left(1+\frac{2\varepsilon N}{b}\right)\left(1+\frac{N}{a}\right).$

∎

The lemma also yields a result in the situation in which $\gcd(a,b)>1$. In
proving this we take the opportunity to smooth out the $b$-invariance of $h$
slightly, whilst also giving an explicit description of $h$ in terms of $f$.
More concretely, we replace $h$ with a projection of $fg$ onto cosets of
$b\cdot\mathbb{Z}$.

######  Lemma 4.2.

There exists an absolute constant $c>0$ such that on assuming $1\leq H\leq
c\delta^{3}N^{1/2}$ and $1\leq K\leq c\delta^{2}H^{2}N^{-1/2}$ the following
holds. Let $a,b\in[N^{1/2}]$ with $\gcd(a,b)\leq\delta^{-1}$ and
$a,b\geq\delta N^{1/2}$. Suppose that $f:\mathbb{Z}\to\mathbb{C}$ is
$1$-bounded, supported on the interval $[N]$, and satisfies

$\biggl{|}\sum_{h,x}\mu_{H}(h)\Delta_{ah_{1},bh_{2}}f(x)\biggr{|}\geq\delta
N.$

Then there exists a 1-bounded $a$-periodic function $g$ such that

$\sum_{x}f(x)g(x)\sum_{k}\mu_{K}(k)\overline{f(x+bk)g(x+bk)}\gg\delta^{2}H^{4}/N.$
(4.5)

###### Proof.

Set $q:=\gcd(a,b)\leq\delta^{-1}$. For each $u\in[q]$, define a $1$-bounded
function $f_{u}:\mathbb{Z}\to\mathbb{C}$ by $f_{u}(x):=f(u+qx)$, and let
$I_{u}:=\left\\{x:u+qx\in[N]\right\\}$ denote the interval on which $f_{u}$ is
supported. By the pigeon-hole principle, for some $u$ we have

$\sum_{x,h_{1},h_{2}}\mu_{H}(h_{1})\mu_{H}(h_{2})\Delta_{\frac{a}{q}h_{1},\frac{b}{q}h_{2}}f_{u}(x)\geq\delta|I_{u}|.$

Note that $\gcd(a/q,b/q)=1$, so by the previous lemma, there exist 1-bounded
functions $g_{u},h_{u}:\mathbb{Z}\to\mathbb{C}$ such that

$\biggl{|}\sum_{x}f_{u}(x)g_{u}(x)h_{u}(x)\biggr{|}\geq\delta\left\lfloor
H\right\rfloor^{2}-2\left(\tfrac{Hq}{a}+\tfrac{Hb}{q|I_{u}|}\right)\left\lfloor
H\right\rfloor^{2}\gg\delta H^{2}.$

Furthermore, $g_{u}$ is $(a/q)$-periodic and

$\\#\left\\{x\in I_{u}:h_{u}(x)\neq h_{u}(x+yb/q)\text{ for some
}|y|\leq\varepsilon|I_{u}|q/b\right\\}\\\
\leq\left(1+\tfrac{2q\varepsilon|I_{u}|}{b}\right)\left(1+\tfrac{q|I_{u}|}{a}\right)\ll\tfrac{N}{a}+\tfrac{\varepsilon
N^{2}}{ab}.$

Defining $g_{u^{\prime}}$ and $h_{u^{\prime}}$ to be identically zero when
$u^{\prime}\neq u$, we set $g(u^{\prime}+qx):=g_{u^{\prime}}(x)$ and
$h(u^{\prime}+qx):=h_{u^{\prime}}(x)$. One can then check that $g$ is
$a$-invariant, that

$\biggl{|}\sum_{x}f(x)g(x)h(x)\biggr{|}\gg\delta H^{2},$

and that

$\\#\left\\{x\in[N]:h(x)\neq h(x+by)\text{ for some }|y|\leq\varepsilon
N/b\right\\}\ll\tfrac{N}{a}+\tfrac{\varepsilon N^{2}}{ab}.$

We may use the latter property to show that, provided $K\geq 1$, we have

$\biggl{|}\sum_{x}f(x)g(x)h(x)-\sum_{x}h(x)\mathbb{E}_{y\in[K]}g(x+by)f(x+by)\biggr{|}\ll\tfrac{NK}{a}.$

Provided that $K\leq c\delta^{2}H^{2}N^{-1/2}$ we deduce that

$\biggl{|}\sum_{x}h(x)\mathbb{E}_{y\in[K]}g(x+bk)f(x+bk)\biggr{|}\gg\delta
H^{2}.$

One can check that, as a function of $x$, the inner expectation is 1-bounded
with support in $[-2N,2N]$. Applying the Cauchy–Schwarz inequality and
changing variables then gives (4.5). ∎

Finally we observe that a function of the form

$h(x):=\sum_{k}\mu_{K}(k)f(x+by)$ (4.6)

has nice $b$-periodicity properties.

######  Lemma 4.3.

If $h$ is defined as in (4.6) for some 1-bounded $f$, then $h$ is
$O(K^{-1})$-Lipschitz along $b\cdot\mathbb{Z}$, in that for any
$x,y\in\mathbb{Z}$ we have $h(x+by)=h(x)+O(|y|/K)$.

###### Proof.

Recalling the definition (1.11), note that $\mu_{K}$ is $(2/\left\lfloor
K\right\rfloor)$-Lipschitz, in that $|\mu_{K}(k+y)-\mu_{K}(k)|\leq
2|y|/\left\lfloor K\right\rfloor$ for all $k,y\in\mathbb{Z}$. Hence, for
$|y|\leq K$, a change of variables gives

$|h(x+by)-h(x)|\leq\sum_{k}|\mu_{K}(k-y)-\mu_{K}(k)|\ll\frac{|y|}{K}\sum_{|k|<2K}1.$

∎

##  5\. Quantitative concatenation

The endpoint of this section is to show how our counting operator (1.3) is
controlled by the $U^{5}$-norm. We begin with four technical lemmas. The first
says that convolving Fejér kernels along progressions of coprime common
difference covers a substantial portion of an interval in a somewhat regular
manner, a fact that can be interpreted Fourier analytically in the following.

######  Lemma 5.1.

Let $K,L\geq 1$ and let $a,b$ be integers satisfying $a\geq\delta L$,
$b\geq\delta K$ and $\gcd(a,b)\leq\delta^{-1}$. Then

$\int_{\mathbb{T}}\bigl{|}\widehat{\mu}_{K}(a\beta)\bigr{|}\bigl{|}\widehat{\mu}_{L}(b\beta)\bigr{|}\mathrm{d}\beta\ll\frac{\delta^{-4}}{\left\lfloor
K\right\rfloor\left\lfloor L\right\rfloor}.$

###### Proof.

Expanding Fourier transforms, one can check that

$\int_{\mathbb{T}}\bigl{|}\widehat{\mu}_{H}(a\beta)\bigr{|}\bigl{|}\widehat{\mu}_{K}(b\beta)\bigr{|}\mathrm{d}\beta\\\
=\left\lfloor K\right\rfloor^{-2}\left\lfloor
L\right\rfloor^{-2}\\#\biggl{\\{}(x,y)\in[K]^{2}\times[L]^{2}:a(x_{1}-x_{2})=b(y_{1}-y_{2})\biggr{\\}}.$

Writing $d:=\gcd(a,b)$, the number of solutions to the equation is at most

$\left\lfloor K\right\rfloor\left\lfloor
L\right\rfloor\left(\tfrac{\left\lfloor
K\right\rfloor}{b/d}+1\right)\left(\tfrac{\left\lfloor
L\right\rfloor}{a/d}+1\right).$

∎

Our next lemma allows us to discard pairs of integers $a,b$ which are not
sufficiently coprime. We exploit this repeatedly.

######  Lemma 5.2.

For fixed integers $0\leq a_{1},a_{2}\leq M$. The number of pairs $(b,c)$ of
integers $0\leq b,c\leq M$ such that $\gcd(a_{1}+b,a_{2}+c)>\delta^{-1}$ is
$\ll\delta M^{2}$.

###### Proof.

Notice that if $d=\gcd(a_{1}+b,a_{2}+c)$ then $d\leq 2M$. Hence

$\displaystyle\sum_{\begin{subarray}{c}0\leq b,c\leq M\\\
\gcd(a_{1}+b,a_{2}+c)>\delta^{-1}\end{subarray}}1\leq\sum_{\delta^{-1}<d\leq
2M}\ \biggl{(}\ \sum_{0\leq m\leq 2M,\ d\mid m}1\biggr{)}^{2}$
$\displaystyle\leq\sum_{\delta^{-1}<d\leq 2M}\left(\frac{2M}{d}+1\right)^{2}$
$\displaystyle\ll M^{2}\sum_{d>\delta^{-1}}\frac{1}{d^{2}}\ll\delta M^{2}.$

∎

The following lemma says that, as $a$ and $h$ range over $[N^{1/2}]$, the
difference function $\Delta_{ah}f$ behaves like $\Delta_{k}f$ with $k\in[N]$,
at least on average.

######  Lemma 5.3.

Let $f:\mathbb{Z}\to\mathbb{C}$ be a 1-bounded function with support in $[N]$.
Suppose that $\delta N^{1/2}\leq H\leq N^{1/2}$ and

$\mathbb{E}_{a\in[N^{1/2}]}\sum_{h}\mu_{H}(h)\left\|\Delta_{ah}f\right\|_{U^{s}}^{2^{s}}\geq\delta\left\|1_{[N]}\right\|_{U^{s}}^{2^{s}}.$

Then

$\left\|f\right\|_{U^{s+1}}^{2^{s+1}}\gg\delta^{12}\left\|1_{[N]}\right\|_{U^{s+1}}^{2^{s+1}}$

###### Proof.

Expanding the definition of the $U^{s}$-norm

$\mathbb{E}_{a\in[N^{1/2}]}\sum_{h}\mu_{H}(h)\left\|\Delta_{ah}f\right\|_{U^{s}}^{2^{s}}\\\
=\sum_{h_{1},\dots,h_{s},x}\overline{\Delta_{h_{1},\dots,h_{s}}f(x)}\mathbb{E}_{a\in[N^{1/2}]}\sum_{h}\mu_{H}(h)\Delta_{h_{1},\dots,h_{s}}f(x+ah).$

Employing the Cauchy–Schwarz inequality to double the $a$ and $h$ variables
gives

$\mathbb{E}_{a,a^{\prime}\in[N^{1/2}]}\sum_{h_{i}}\sum_{x}\sum_{h,h^{\prime}}\mu_{H}(h)\mu_{H}(h^{\prime})\Delta_{h_{1},\dots,h_{s},ah-a^{\prime}h^{\prime}}f(x)\gg\delta^{2}N^{s+1}.$

By Lemma 5.2 and the pigeon-hole principle, we deduce the existence of
$a,a^{\prime}\gg\delta^{2}N^{1/2}$ with $\gcd(a,a^{\prime})\ll\delta^{-2}$
such that

$\sum_{h_{i}}\sum_{x}\sum_{h,h^{\prime}}\mu_{H}(h)\mu_{H}(h^{\prime})\Delta_{h_{1},\dots,h_{s},ah-a^{\prime}h^{\prime}}f(x)\gg\delta^{2}N^{s+1}.$

By Fourier inversion and extraction of a large Fourier coefficient, there
exists $\alpha\in\mathbb{T}$ such that the right-hand side above is at most

$\int_{\mathbb{T}}\left|\widehat{\mu}_{H}(a\beta)\right|\left|\widehat{\mu}_{H}(a^{\prime}\beta)\right|\mathrm{d}\beta\biggl{|}\sum_{h_{i}}\sum_{x}\Delta_{h_{1},\dots,h_{s},h_{s+1}}f(x)e(\alpha
h_{s+1})\biggr{|}.$

The result follows on employing Lemma 5.1 and Lemma A.3. ∎

We now prove a similar lemma, but with $\Delta_{ah}f$ replaced by $fg_{a}$
where $g_{a}$ is $a$-periodic. The moral is that these are similar quantities
(on average).

######  Lemma 5.4.

Let $f,g_{a}:\mathbb{Z}\to\mathbb{C}$ be 1-bounded functions such that $g_{a}$
is $a$-periodic and $\mathrm{supp}(f)\subset[N]$. Suppose that

$\mathbb{E}_{a\in[N^{1/2}]}\left\|fg_{a}\right\|_{U^{s}}^{2^{s}}\geq\delta\left\|1_{[N]}\right\|_{U^{s}}^{2^{s}}.$

Then

$\left\|f\right\|_{U^{s+1}}^{2^{s+1}}\gg\delta^{24}\left\|1_{[N]}\right\|_{U^{s+1}}^{2^{s+1}}$

###### Proof.

Fix $a\in[N^{1/2}]$. By the periodicity of $g_{a}$ and a change of variables,
we have

$\sum_{h_{i}}\sum_{x}\Delta_{h_{1},\dots,h_{s}}g_{a}(x)\Delta_{h_{1},\dots,h_{s}}f(x)=\sum_{h_{i}}\sum_{x}\Delta_{h_{1},\dots,h_{s}}g_{a}(x)\mathbb{E}_{y\in[N^{1/2}]}\Delta_{h_{1},\dots,h_{s}}f(x+ay).$

Notice that the sum over $x$ is non-zero only if $|x|,|h_{i}|<N$, hence by
Cauchy–Schwarz and a change of variables

$\displaystyle\biggl{(}\mathbb{E}_{a\in[N^{1/2}]}\left\|fg_{a}\right\|_{U^{s}}^{2^{s}}\biggr{)}^{2}$
$\displaystyle\ll
N^{s+1}\mathbb{E}_{a\in[N^{1/2}]}\sum_{h_{i}}\sum_{x}\sum_{y}\mu_{N^{1/2}}(y)\Delta_{h_{1},\dots,h_{s},ay}f(x)$
$\displaystyle=N^{s+1}\mathbb{E}_{a\in[N^{1/2}]}\sum_{y}\mu_{N^{1/2}}(y)\left\|\Delta_{ay}f\right\|_{U^{s}}^{2^{s}}$

The result follows on employing Lemma 5.3. ∎

We are now ready to give the technical heart of this section. The (somewhat
lengthy) assumptions come from our eventual application of Lemma 4.2.

######  Lemma 5.5.

Fix $a\in\mathbb{N}$ and let $\delta N^{1/2}\leq K\leq N^{1/2}$. For each
$b\in[N^{1/2}]$ let $f,g_{b},h_{b}:\mathbb{Z}\to\mathbb{C}$ be 1-bounded
functions such that $\mathrm{supp}(f),\mathrm{supp}(h_{b})\subset[N]$ and
where $g_{b}$ is $b$-periodic. Set

$\tilde{h}_{b}(x):=\sum_{k}\mu_{K}(k)h_{b}(x+(a+b)k)$

and suppose that

$\sum_{\begin{subarray}{c}\delta\sqrt{N}\leq b\leq\sqrt{N}\\\
\gcd(a,b)\leq\delta^{-1}\end{subarray}}\sum_{x}f(x)g_{b}(x)\tilde{h}_{b}(x)\geq\delta
N^{3/2}.$

Then

$\mathbb{E}_{b\in[N^{1/2}]}\big{\|}h_{b}\big{\|}_{U^{3}}^{8}\gg\delta^{208}\left\|1_{[N]}\right\|_{U^{3}}^{8}.$

###### Proof.

To ease notation, write

$\tilde{h}_{b}(x):=\sum_{k}\mu_{K}(k)h_{b}(x+(a+b)k)$

We apply Cauchy–Schwarz to remove the weight $f(x)$ and double the $b$
variable, yielding

$\sum_{\begin{subarray}{c}\delta\sqrt{N}\leq b,b^{\prime}\leq\sqrt{N}\\\
\gcd(a,b)\leq\delta^{-1}\end{subarray}}\sum_{x}g_{b}(x)\tilde{h}_{b}(x)\overline{g_{b^{\prime}}(x)\tilde{h}_{b^{\prime}}(x)}\geq\delta^{2}N^{2}.$

Employing Lemma 5.2, we may discard those $b,{b^{\prime}}$ for which one of
$\gcd(b^{\prime},a+{b})$ or $\gcd(a+b^{\prime},a+{b})$ is greater than
$C\delta^{-2}$. On combining this with the popularity principle, we deduce the
existence of $\mathcal{B}\subset[\delta N^{1/2},N^{1/2}]$ of size
$|\mathcal{B}|\gg\delta^{2}N^{1/2}$ such that for each $b\in\mathcal{B}$ there
exists $b^{\prime}\in[N^{1/2}]$ with all of $\gcd(b,a+{b})$,
$\gcd({b^{\prime}},a+{b})$, $\gcd(a+b^{\prime},a+{b})$ at most
$O(\delta^{-2})$ and satisfying

$\sum_{x}g_{b}(x)\overline{\tilde{h}_{b^{\prime}}(x)g_{b^{\prime}}(x)}\tilde{h}_{b}(x)\gg\delta^{2}N.$
(5.1)

Expanding the definition of $\tilde{h}_{b^{\prime}}$, using the invariance of
$g_{b}$ and changing variables gives

$\sum_{x}\mathbb{E}_{k_{1},k_{3}\in[K]}\sum_{k_{2}}\mu_{K}(k_{2})g_{b}(x+(a+b^{\prime})k_{2}+{b^{\prime}}k_{3})\overline{h_{b^{\prime}}(x+bk_{1}+{b^{\prime}}k_{3})}\\\
\overline{g_{b^{\prime}}(x+bk_{1}+(a+b^{\prime})k_{2})}\
\tilde{h}_{b}(x+bk_{1}+(a+b^{\prime})k_{2}+{b^{\prime}}k_{3})\gg\delta^{2}N.$

Since $h_{b^{\prime}}$ is supported on $[N]$ and $b,{b^{\prime}},K\leq
N^{1/2}$, there are at most $O(N)$ values of $x$ which contribute to the above
sum. Applying Hölder’s inequality then gives

$\sum_{x}\biggl{(}\mathbb{E}_{k_{1},k_{3}\in[K]}\sum_{k_{2}}\mu_{K}(k_{2})g_{b}(x+(a+b^{\prime})k_{2}+{b^{\prime}}k_{3})\overline{h_{b^{\prime}}(x+bk_{1}+{b^{\prime}}k_{3})}\\\
\overline{g_{b^{\prime}}(x+bk_{1}+(a+b^{\prime})k_{2})}\
\tilde{h}_{b}(x+bk_{1}+(a+b^{\prime})k_{2}+{b^{\prime}}k_{3})\biggr{)}^{8}\gg\delta^{16}N.$

The sum inside the 8th power corresponds to an integral with respect to three
probability measures on $\mathbb{Z}$, with integrand amenable to Lemma A.4.
Combining this with a change of variables gives

$\sum_{x}\sum_{k_{1},k_{2},k_{3}}\mu_{K}(k_{1})\nu_{K}(k_{2})\mu_{K}(k_{3})\Delta_{bk_{1},(a+b^{\prime})k_{2},{b^{\prime}}k_{3}}\
\tilde{h}_{b}(x)\gg\delta^{16}N,$

where we set

$\nu_{K}(k):=\sum_{k_{1}-k_{2}=k}\mu_{K}(k_{1})\mu_{K}(k_{2}).$

By Lemma 4.3, each $\tilde{h}_{b}$ is $O(K^{-1})$-Lipschitz along
$(a+b)\cdot\mathbb{Z}$. Hence, if $l_{i}\in[L]$, a telescoping identity shows
that

$|\Delta_{h_{1}+(a+{b})l_{1},h_{2}+(a+{b})l_{2},h_{3}+(a+{b})l_{3}}\tilde{h}_{b}(x)-\Delta_{h_{1},h_{2},h_{3}}\tilde{h}_{b}(x)|\ll
L/K.$

Taking $L:=c\delta^{16}K$ we obtain

$\sum_{x}\sum_{k_{1},k_{2},k_{3}}\mu_{K}(k_{1})\nu_{K}(k_{2})\mu_{K}(k_{3})\mathbb{E}_{l_{1},l_{2},l_{3}\in[L]}\\\
\Delta_{bk_{1}+(a+{b})l_{1},\,(a+b^{\prime})k_{2}+(a+{b})l_{2},\,{b^{\prime}}k_{3}+(a+{b})l_{3}}\
\tilde{h}_{b}(x)\gg\delta^{16}N.$

We may replace the uniform measure on the $l_{i}$ by Fejér kernels at the cost
of three applications of Cauchy–Schwarz; this gives

$\sum_{x}\sum_{\begin{subarray}{c}k_{1},k_{2},k_{3}\\\
l_{1},l_{2},l_{3}\end{subarray}}\mu_{K}(k_{1})\nu_{K}(k_{2})\mu_{K}(k_{3})\mu_{L}(l_{1})\mu_{L}(l_{2})\mu_{L}(l_{3})\\\
\Delta_{bk_{1}+(a+{b})l_{1},\,(a+b^{\prime})k_{2}+(a+{b})l_{2},\,{b^{\prime}}k_{3}+(a+{b})l_{3}}\
\tilde{h}_{b}(x)\gg\delta^{128}N.$

Write

$\displaystyle\lambda_{1}(h):=\sum_{bk+(a+{b})l=h}$
$\displaystyle\mu_{K}(k)\mu_{L}(l),\qquad\lambda_{2}(h):=\sum_{(a+b^{\prime})k+(a+{b})l=h}\nu_{K}(k)\mu_{L}(l),$
$\displaystyle\lambda_{3}(h):=\sum_{{b^{\prime}}k+(a+{b})l=h}\mu_{K}(k)\mu_{L}(l).$

Then

$\sum_{x}\sum_{h_{1},h_{2},h_{3}}\lambda_{1}(h_{1})\lambda_{2}(h_{2})\lambda_{3}(h_{3})\\\
\Delta_{h_{1},h_{2},h_{3}}\ \tilde{h}_{b}(x)\gg\delta^{128}N.$

By Fourier inversion and extraction of a large Fourier coefficient, there
exist $\alpha_{i}\in\mathbb{T}$ such that

$\biggl{|}\sum_{x}\sum_{h_{1},h_{2},h_{3}}\Delta_{h_{1},h_{2},h_{3}}\
\tilde{h}_{b}(x)e(\underline{\alpha}\cdot\underline{h})\biggr{|}\prod_{i=1}^{3}\int_{\mathbb{T}}\bigl{|}\widehat{\lambda}_{i}(\beta)\bigr{|}\mathrm{d}\beta\gg\delta^{128}N.$

By our choice of $b$, $b^{\prime}$ (see the paragraph preceding (5.1)),
together with Lemma 5.1, for each $i$ we have

$\int_{\mathbb{T}}\bigl{|}\widehat{\lambda}_{i}(\alpha)\bigr{|}\mathrm{d}\alpha\ll\frac{\delta^{-8}}{KL}\ll\frac{\delta^{-26}}{N},$
(5.2)

the latter following from the fact that $L\gg c\delta^{16}K$ and $K\geq\delta
N^{1/2}$. On combining this with Lemma A.3 we obtain

$\big{\|}\tilde{h}_{b}\big{\|}_{U^{3}}^{8}\gg\delta^{206}N^{4}.$

Since $\tilde{h}_{b}$ is an average of translates of $h_{b}$, we may apply the
triangle inequality for the $U^{3}$-norm, together with the fact that Gowers
norms are translation invariant, and conclude that
$\left\|h_{b}\right\|_{U^{3}}^{8}\gg\delta^{206}N^{4}$. Summing over
$b\in\mathcal{B}$ gives our final bound. ∎

Finally we synthesise Lemmas 3.3, 4.2 and 5.5.

######  Theorem 5.6 (Global $U^{5}$-control).

Let $g_{0},g_{1},f:\mathbb{Z}\to\mathbb{C}$ be 1-bounded functions, each with
support in $[N]$. Suppose that

$\left|\Lambda_{q,N}(g_{0},g_{1},f)\right|\geq\delta\Lambda_{q,N}(1_{[N]}).$

Then

$\sum_{u\in[q]}\left\|f\right\|_{U^{5}(u+q\mathbb{Z})}^{2^{5}}\gg\delta^{2^{25}}\sum_{u\in[q]}\left\|1_{[N]}\right\|_{U^{5}(u+q\mathbb{Z})}^{2^{5}}.$

###### Proof.

We recall our convention (1.2) regarding $M$. We begin by applying the
linearisation procedure (Lemma 3.3) to deduce that

$\sum_{a,b\in(-2M,2M)}\
\biggl{|}\sum_{h}\mu_{H}(h)\sum_{x}\Delta_{q(a+b)h_{1},qbh_{2},qah_{3}}f(x)\biggr{|}\\\
\gg\delta^{32}NM^{2}.$

We note that the sum inside the absolute value is invariant under
$a\mapsto-a$. Hence we may restrict to $a,b\in[0,2M]$ at the cost of changing
the absolute constant. Applying Lemma 5.2 we may discard those $a,b$ for which
either $\gcd(a,b)>C\delta^{-32}$ or $b<c\delta^{32}M$. Partitioning the sum
over $x$ into congruence classes $u\bmod q$, the popularity principle gives:

  * •

at least $\Omega(\delta^{32}q)$ residues $u\in[q]$;

  * •

for each of which there is a subset of $h_{3}\in(-H,H)$ of
$\mu_{H}$-measure222i.e.
$\sum_{h_{3}\in\mathcal{H}}\mu_{H}(h_{3})\gg\delta^{32}$. at least
$\Omega(\delta^{32})$;

  * •

for each of which there exist $\Omega(\delta^{32}M)$ values of $a\in[2M]$;

  * •

for each of which there are $\Omega(\delta^{32}M)$ values of $b\in[2M]$
satisfying $\gcd(a,b)\ll\delta^{-32}$ and $b\gg\delta^{32}M$;

and together these satisfy

$\biggl{|}\sum_{h_{1},h_{2}}\mu_{H}(h_{1},h_{2})\sum_{x}\Delta_{(a+b)h_{1},bh_{2},ah_{3}}f(qx-u)\biggr{|}\\\
\gg\delta^{32}M^{2}.$

For fixed $u,h_{3},a$ write $\tilde{f}(x):=\Delta_{ah_{3}}f(qx-u),$ so that
$\tilde{f}$ has support in the interval $[(2M)^{2}]$ and

$\biggl{|}\sum_{h_{1},h_{2}}\mu_{H}(h_{1},h_{2})\sum_{x}\Delta_{(a+b)h_{1},bh_{2}}\tilde{f}(x)\biggr{|}\\\
\gg\delta^{32}M^{2}.$

Set

$H:=c\delta^{96}M\qquad\text{and}\qquad K:=c^{3}\delta^{160}M,$ (5.3)

with $c$ sufficiently small to ensure that we may apply Lemma 4.2. This gives
the existence of a 1-bounded $b$-periodic function $g_{b}$ such that on
setting

$\tilde{h}_{b}(x):=\sum_{k}\mu_{K}(k)\overline{\tilde{f}(x+(a+b)k)g_{b}(x+(a+b)k)}$
(5.4)

we have

$\sum_{x}\tilde{f}(x)g_{b}(x)\tilde{h}_{b}(x)\gg\delta^{448}M^{2}.$

Setting $\eta:=c\delta^{480}$ for some small absolute constant $c>0$, we may
sum over our set of permissible $b$ to deduce that

$\sum_{\begin{subarray}{c}\eta M\leq b\leq 2M\\\
\gcd(a,b)\leq\eta^{-1}\end{subarray}}\sum_{x}\tilde{f}(x)g_{b}(x)h_{b}(x)\geq\eta
M^{3}.$

The hypotheses of Lemma 5.5 having been met, we conclude that

$\mathbb{E}_{b\in[2M]}\big{\|}\tilde{f}g_{b}\big{\|}_{U^{3}}^{8}\gg\delta^{99,840}\left\|1_{[M^{2}]}\right\|_{U^{3}}^{8}.$

Applying Lemma 5.4 then gives

$\big{\|}\tilde{f}\big{\|}_{U^{4}}^{16}\gg\delta^{2,396,160}\left\|1_{[M^{2}]}\right\|_{U^{4}}^{16}.$

Recalling that $\tilde{f}(x)=\Delta_{ah_{3}}f_{u}(x)$ where
$f_{u}(x):=f(qx-u)$, we may integrate over the set of permissible $h_{3}$ and
$a$, utilising positivity to extend the range of summation, and deduce that

$\mathbb{E}_{a\in[2M]}\sum_{h}\mu_{H}(h_{3})\big{\|}\Delta_{ah_{3}}f_{u}\big{\|}_{U^{4}}^{16}\gg\delta^{2,396,224}\left\|1_{[M^{2}]}\right\|_{U^{4}}^{16}$

Using Lemma 5.3 and summing over the permissible range of $u$ we get that

$\mathbb{E}_{u\in[q]}\left\|f_{u}\right\|_{U^{5}}^{32}\gg\delta^{28,754,720}\left\|1_{[M^{2}]}\right\|_{U^{5}}^{32},$

and the result follows. ∎

##  6\. Degree lowering

So far, we have shown that $\Lambda_{q,N}(f_{0},f_{1},f_{2})$ is controlled by
$\mathbb{E}_{u\in[q]}\|f_{2}\|_{U^{5}(u+q\mathbb{Z})}^{2^{5}}$ whenever
$f_{0},f_{1},$ and $f_{2}$ are $1$-bounded complex-valued functions supported
on the interval $[N]$. The next step in our argument is to bound
$\Lambda_{q,N}(f_{0},f_{1},f_{2})$ in terms of the $U^{5}(u+q\mathbb{Z})$-norm
of the dual function

$F(x):=\mathbb{E}_{y\in[M]}f_{0}(x-qy^{2})f_{1}(x+y-qy^{2}).$ (6.1)

We postpone this deduction until §7. In this section we show how
$U^{5}$-control of the dual implies $U^{2}$-control.

Our argument combines three simple lemmas: Weyl’s inequality; what we call
‘dual–difference interchange’, which allows us to replace the difference
function of the dual by the dual of the difference functions; and the fact
that a function whose difference functions correlate with ‘low rank’ Fourier
coefficients must have a large uniformity norm of lower degree.

The following log-free variant of Weyl’s inequality can be found in [4, Lemma
A.11].

######  Lemma 6.1 (Weyl’s inequality).

There exists an absolute constant $C$ such that the following holds. Let
$\alpha,\beta\in\mathbb{T}$, $\delta\in(0,1)$ and let $I\subset\mathbb{Z}$ be
an interval with $|I|\geq C\delta^{-6}$ and

$\big{|}\mathbb{E}_{y\in I}e(\alpha y^{2}+\beta y)\big{|}\geq\delta.$

Then there exists a positive integer $q\ll\delta^{-4}$ such that

$\|q\alpha\|\ll\delta^{-14}|I|^{-2}.$

This has the following consequence, which uses our convention (1.2) regarding
$M$.

######  Lemma 6.2.

There exist an absolute constant $C$ such that for $N\geq C(q/\delta)^{C}$ the
following holds. Suppose that for $\alpha\in\mathbb{T}$ there are $1$-bounded
functions $g_{0},g_{1}:\mathbb{Z}\to\mathbb{C}$ supported on the interval
$[N]$ such that

$\left|\sum_{x}\sum_{y\in[M]}g_{0}(qx)g_{1}(qx+y)e(\alpha(x+y^{2}))\right|\geq\delta
MN/q.$

Then there exists a positive integer $q^{\prime}\ll\delta^{-4}$ such that
$\|q^{\prime}q^{2}\alpha\|\ll\delta^{-14}q^{3}/N$.

###### Proof.

We split the sum over $y\in[M]$ into arithmetic progressions modulo $q$ and
split the sum over $x$ into intervals of length $M/q$. Hence, by the pigeon-
hole principle, there exists $u\in[q]$ and an integer $m$ such that on
rounding the sum over $y$ we have

$\left|\sum_{x,y\in[M/q]}g_{0}(q(m+x))g_{1}(u+q(m+x+y))e\left(\alpha\left(x+(u+qy)^{2}\right)\right)\right|\\\
\gg\delta(M/q)^{2}.$

Define the functions

$\displaystyle h_{0}(x):=g_{0}(q(m+x))$ $\displaystyle e(\alpha
x)1_{[M/q]}(x),\qquad h_{1}(x):=g_{1}(u+q(m+x))1_{[2M/q]},$ $\displaystyle
h_{2}(x):=e\left(\alpha(u+qx)^{2}\right)1_{[M/q]}(x)$

Then by orthogonality, extraction of a large Fourier coefficient and Parseval
we have

$\displaystyle\delta
M^{2}/q^{2}\ll\left|\int_{\mathbb{T}}\hat{h}_{0}(\beta)\hat{h}_{1}(-\beta)\hat{h}_{2}(\beta)\mathrm{d}\alpha\right|\ll\big{\|}\hat{h}_{2}\big{\|}_{\infty}\big{\|}\hat{h}_{0}\big{\|}_{L^{2}}\big{\|}\hat{h}_{1}\big{\|}_{L^{2}}\ll\big{\|}\hat{h}_{2}\big{\|}_{\infty}M/q.$

It follows that there exists $\beta\in\mathbb{T}$ such that

$\left|\sum_{x\in[M/q]}e\left(\alpha(u+qx)^{2}+\beta x\right)\right|\gg\delta
M/q.$

Applying Weyl’s inequality, we deduce the existence of
$q^{\prime}\ll\delta^{-4}$ such that
$\left\|q^{\prime}q^{2}\alpha\right\|\ll\delta^{-14}(q/M)^{2}$. ∎

######  Lemma 6.3 (Dual–difference interchange).

For each $y\in[M]$, let $F_{y}:\mathbb{Z}\to\mathbb{C}$ be a 1-bounded
function with support in an interval of length $N$. Set

$F(x):=\mathbb{E}_{y\in[M]}F_{y}(x).$

Then for any function $\phi:\mathbb{Z}^{s}\to\mathbb{T}$ and finite set
$\mathcal{H}\subset\mathbb{Z}^{s}$ we have

$\left(N^{-s-1}\sum_{\underline{h}\in\mathcal{H}}\left|\sum_{x}\Delta_{\underline{h}}F(x)e\bigl{(}\phi(\underline{h})x\bigr{)}\right|\right)^{2^{s}}\ll_{s}\\\
N^{-2s-1}\sum_{\underline{h}^{0},\underline{h}^{1}\in\mathcal{H}}\left|\sum_{x}\mathbb{E}_{y\in[M]}\Delta_{\underline{h}^{0}-\underline{h}^{1}}F_{y}(x)e\bigl{(}\phi(\underline{h}^{0};\underline{h}^{1})x\bigr{)}\right|,$

where

$\phi(\underline{h}^{0};\underline{h}^{1}):=\sum_{\omega\in\left\\{0,1\right\\}^{s}}(-1)^{|\omega|}\phi(\underline{h}^{\omega})\qquad\text{and}\qquad\underline{h}^{\omega}:=(h_{1}^{\omega_{1}},\dots,h_{s}^{\omega_{s}}).$

###### Proof.

We proceed by induction on $s\geq 0$, the base case being an identity. Suppose
then that $s\geq 1$. For $\underline{h}\in\mathbb{Z}^{s-1}$ and
$h\in\mathbb{Z}$, we note that

$\Delta_{(\underline{h},h)}F(x)=\Delta_{\underline{h}}\left(\mathbb{E}_{y,y^{\prime}\in[M]}F_{y}(x)\overline{F_{y^{\prime}}(x+h)}\right)$

Hence by the induction hypothesis

$\left(N^{-s-1}\sum_{h}\sum_{\begin{subarray}{c}\underline{h}\\\
(\underline{h},h)\in\mathcal{H}\end{subarray}}\left|\sum_{x}\Delta_{(\underline{h},h)}F(x)e\bigl{(}\phi(\underline{h})x\bigr{)}\right|\right)^{2^{s}}\ll_{s}\\\
\left(N^{-2s}\sum_{h}\sum_{\begin{subarray}{c}\underline{h}^{0},\underline{h}^{1}\\\
(\underline{h}^{i},h)\in\mathcal{H}\end{subarray}}\left|\sum_{x}\mathbb{E}_{y,y^{\prime}\in[M]}\Delta_{\underline{h}^{0}-\underline{h}^{1}}F_{y}(x)\overline{F_{y^{\prime}}(x+h)}e\bigl{(}\phi(\underline{h}^{0};\underline{h}^{1};h)x\bigr{)}\right|\right)^{2},$

where

$\phi(\underline{h}^{0};\underline{h}^{1};h):=\sum_{\omega\in\left\\{0,1\right\\}^{s-1}}(-1)^{|\omega|}\phi(\underline{h}^{\omega},h).$

Letting $e(\psi(\underline{h}^{0};\underline{h}^{1};h))$ denote the phase of
the inner absolute, we take the sum over $h$ inside and apply Cauchy–Schwarz
to obtain

$\left(\sum_{\underline{h}^{0},\underline{h}^{1},x}\mathbb{E}_{y,y^{\prime}\in[M]}\sum_{\begin{subarray}{c}h\\\
(\underline{h}^{i},h)\in\mathcal{H}\end{subarray}}\Delta_{\underline{h}^{0}-\underline{h}^{1}}F_{y}(x)\overline{F_{y^{\prime}}(x+h)}e\bigl{(}\phi(\underline{h}^{0};\underline{h}^{1};h)x+\psi(\underline{h}^{0};\underline{h}^{1};h)\bigr{)}\right)^{2}\\\
\leq
N^{2s-1}\sum_{\underline{h}^{0},\underline{h}^{1}}\sum_{\begin{subarray}{c}h^{0},h^{1}\\\
(\underline{h}^{i},h^{j})\in\mathcal{H}\end{subarray}}\\\
\left|\sum_{x}\mathbb{E}_{y\in[M]}\Delta_{\underline{h}^{0}-\underline{h}^{1}}F_{y}(x)\overline{F_{y}(x+h^{0}-h^{1})}e\Bigl{(}\bigl{(}\phi(\underline{h}^{0};\underline{h}^{1};h^{0})-\phi(\underline{h}^{0};\underline{h}^{1};h^{1})\bigr{)}x\Bigr{)}\right|.$

The result follows. ∎

If $\phi(h_{1},\dots,h_{s-1})$ is a function of $s-1$ variables we write
$\phi(h_{1},\dots,\hat{h}_{i},\dots,h_{s}):=\phi(h_{1},\dots,h_{i-1},h_{i+1},\dots,h_{s}).$
We say that $\phi(h_{1},\dots,h_{s})$ is _low rank_ if there exist functions
$\phi_{i}(h_{1},\dots,h_{s-1})$ such that

$\phi(h_{1},\dots,h_{s})=\sum_{i=1}^{s}\phi_{i}(h_{1},\dots,\hat{h}_{i},\dots,h_{s}).$

From the definition of the Gowers norm together with the $U^{2}$-inverse
theorem (Lemma A.1), one can show that largeness of the $U^{s+2}$-norm is
equivalent to the existence of $\phi:\mathbb{Z}^{s}\to\mathbb{T}$ such that

$\sum_{h_{1},\dots,h_{s}}\left|\sum_{x}\Delta_{h}f(x)e(\phi(h)x)\right|\gg
N^{s+1}.$

The following lemma says that if $\phi$ is low-rank, then the $U^{s+1}$-norm
must also be large.

######  Lemma 6.4 (Low rank correlation implies lower degree).

Let $f:\mathbb{Z}\to\mathbb{C}$ be a 1-bounded function with support in $[N]$.
Then for $\phi_{1},\dots,\phi_{m}:\mathbb{Z}^{s-1}\to\mathbb{T}$ with $m\leq
s$ we have

$\frac{1}{N^{s+1}}\sum_{h_{1},\dots,h_{s}}\left|\sum_{x}\Delta_{h}f(x)e\left(\sum_{i=1}^{m}\phi_{i}(h_{1},\dots,\hat{h}_{i},\dots,h_{s})x\right)\right|\\\
\ll_{m}\left(\frac{\left\|f\right\|_{U^{s+1}}^{2^{s+1}}}{N^{s+2}}\right)^{2^{-m-1}}.$
(6.2)

###### Proof.

We proceed by induction on $m\geq 0$, the base case corresponding to the
Cauchy–Schwarz inequality. Suppose then that $m\geq 1$ and the result is true
for smaller values of $m$. Letting $e(\psi(h))$ denote the phase of the inner-
most sum, the left-hand side of (6.2) is equal to

$\frac{1}{N^{s+1}}\sum_{h_{2},\dots,h_{s},x}\Delta_{h_{2},\dots,h_{s}}f(x)e\left(\phi_{1}(h_{2},\dots,h_{s})\right)\sum_{h_{1}}\Delta_{h_{2},\dots,h_{s}}\overline{f}(x+h_{1})\\\
e\left(\sum_{i=2}^{m}\phi_{i}(h_{1},\dots,\hat{h}_{i},\dots,h_{s})x+\psi(h_{1},\dots,h_{s})\right).$

By Cauchy–Schwarz, the square of this is at most

$\frac{1}{N^{s+2}}\sum_{h_{2},\dots,h_{s}}\
\sum_{h_{1},h_{1}^{\prime}\in(-N,N)}\\\
\left|\sum_{x}\Delta_{h_{1}-h_{1}^{\prime},h_{2},\dots,h_{s}}f(x)e\left(\sum_{i=2}^{m}\left(\phi_{i}(h_{1},\dots,\hat{h}_{i},\dots,h_{s})-\phi_{i}(h_{1}^{\prime},\dots,\hat{h}_{i},\dots,h_{s})\right)x\right)\right|.$

Taking a maximum over $h_{1}^{\prime}\in(-N,N)$ and changing variables in
$h_{1}$, the latter is at most an absolute constant times

$\frac{1}{N^{s+1}}\sum_{h_{1},h_{2},\dots,h_{s}}\Bigg{|}\sum_{x}\Delta_{h_{1},h_{2},\dots,h_{s}}f(x)\\\
e\left(\sum_{i=2}^{m}\left(\phi_{i}(h_{1}+h_{1}^{\prime},h_{2}\dots,\hat{h}_{i},\dots,h_{s})-\phi_{i}(h_{1}^{\prime},h_{2}\dots,\hat{h}_{i},\dots,h_{s})\right)x\right)\Bigg{|}.$

This phase has lower rank than the original, hence we may apply the induction
hypothesis to yield the lemma. ∎

######  Lemma 6.5 (Degree lowering).

There exists an absolute constant such that for $N\geq C(q/\delta)^{C}$ the
following holds. Let $f_{0},f_{1}:\mathbb{Z}\to\mathbb{C}$ be 1-bounded
functions with support in $[N]$ and define the dual

$F(x):=\mathbb{E}_{y\in[M]}f_{0}(x-qy^{2})f_{1}(x+y-qy^{2}).$

If, for $s\geq 3$, we have

$\sum_{u\in[q]}\left\|F\right\|_{U^{s}(u+q\cdot\mathbb{Z})}^{2^{s}}\geq\delta\sum_{u\in[q]}\left\|1_{[N]}\right\|_{U^{s}(u+q\cdot\mathbb{Z})}^{2^{s}},$

then

$\sum_{u\in[q]}\left\|F\right\|_{U^{s-1}(u+q\cdot\mathbb{Z})}^{2^{s-1}}\gg_{s}\delta^{4^{s+2}}\sum_{u\in[q]}\left\|1_{[N]}\right\|_{U^{s-1}(u+q\cdot\mathbb{Z})}^{2^{s-1}},$

###### Proof.

Write $M:=\left\lfloor(N/q)^{1/2}\right\rfloor$. Given $u\in[q]$ let
$F_{u}(x):=F(u+qx)$, a function with support in the interval $[2N/q]$.
Applying the popularity principle, there exists a set of $\Omega(\delta q)$
residues $u\in[q]$ for which
$\left\|F_{u}\right\|_{U^{s}}^{2^{s}}\gg\delta(N/q)^{s+1}$. Expanding the
definition of the $U^{s}$-norm (1.9) we have

$\sum_{h_{1},\dots,h_{s-2}}\left\|\Delta_{h_{1},\dots,h_{s-2}}F_{u}\right\|_{U^{2}}^{4}\gg\delta(N/q)^{s+1}.$

Applying the $U^{2}$-inverse theorem (Lemma A.1), there exists
$\mathcal{H}\subset(-2N/q,2N/q)^{s-2}$ of size
$|\mathcal{H}|\gg\delta(N/q)^{s-2}$ and a function
$\phi:\mathbb{Z}^{s-2}\to\mathbb{T}$ such that for every
$\underline{h}\in\mathcal{H}$ we have

$\left|\sum_{x}\Delta_{\underline{h}}F_{u}(x)e\bigl{(}\phi(\underline{h})x\bigr{)}\right|\gg\delta
N/q.$ (6.3)

Set $T:=\left\lceil C\delta^{-1}N/q\right\rceil$, with $C$ an absolute
constant taken sufficiently large to ensure that, on rounding
$\phi(\underline{h})$ to the nearest fraction of the form $t/T$, the validity
of (6.3) remains. Summing over $\underline{h}\in\mathcal{H}$ and applying
Lemma 6.3, we deduce that

$\sum_{\underline{h}^{0},\underline{h}^{1}\in\mathcal{H}}\left|\sum_{x}\mathbb{E}_{y\in[M]}\Delta_{\underline{h}^{0}-\underline{h}^{1}}f_{0}(u+qx-
qy^{2})\Delta_{\underline{h}^{0}-\underline{h}^{1}}f_{1}(u+qx+y-qy^{2})\right|\\\
e\bigl{(}\phi(\underline{h}^{0};\underline{h}^{1})x\bigr{)}\gg_{s}\delta^{2^{s-1}}(N/q)^{2s-1}.$

Applying the pigeon-hole and popularity principle, there exists
$\mathcal{H}^{\prime}\subset\mathcal{H}$ of size
$\Omega_{s}(\delta^{2^{s-1}}(N/q)^{s-2})$ and
$\underline{h}^{1}\in\mathcal{H}$ such that for every
$\underline{h}^{0}\in\mathcal{H}^{\prime}$ we have

$\left|\sum_{x}\sum_{y\in[M]}\Delta_{\underline{h}^{0}-\underline{h}^{1}}f_{0}(u+qx-
qy^{2})\Delta_{\underline{h}^{0}-\underline{h}^{1}}f_{1}(u+qx+y-qy^{2})e\bigl{(}\phi(\underline{h}^{0},\underline{h}^{1})x\bigr{)}\right|\\\
\gg\delta^{2^{s-1}}MN/q.$

By Lemma 6.2, for each $\underline{h}^{0}\in\mathcal{H}^{\prime}$ there exists
$q^{\prime}\ll\delta^{-2^{s+1}}$ such that

$\left\|q^{\prime}q^{2}\phi(\underline{h}^{0},\underline{h}^{1})\right\|\ll\delta^{-2^{s}\times
7}q^{3}/N$

Notice that $\phi(\underline{h}^{0},\underline{h}^{1})$ is an element of the
additive group $\left\\{t/T:t\in[T]\right\\}\subset\mathbb{T}$. Moreover, for
any $Q_{i}$ we have the inclusion

$\left\\{\alpha\in\mathbb{T}:\exists q^{\prime}\leq Q_{1}\text{ with
}\left\|q^{\prime}q^{2}\alpha\right\|\leq
Q_{2}q^{3}/N\right\\}\subset\bigcup_{\begin{subarray}{c}1\leq a\leq q\leq
Q_{1}\\\
\mathrm{hcf}(a,q)=1\end{subarray}}\left[\frac{a}{q^{\prime}q^{2}}-\frac{Q_{2}}{N},\frac{a}{q^{\prime}q^{2}}+\frac{Q_{2}}{N}\right].$

By a volume packing argument, the number of $t/T$ lying in this union of
intervals is at most $O\left(Q_{1}^{2}(1+\tfrac{Q_{2}T}{N})\right)$. It
therefore follows from the pigeon-hole principle that there exists
$\mathcal{H}^{\prime\prime}\subset\mathcal{H}^{\prime}$ of size
$\Omega\left(\delta^{2^{s+3}+1-2^{s}}(N/q)^{s-2}\right)$ and $t_{0}\in[T]$
such that for any $\underline{h}^{0}\in\mathcal{H}^{\prime\prime}$ we have
$\phi(\underline{h}^{0},\underline{h}^{1})=t_{0}/T$. In particular, when
restricted to the set $\mathcal{H}^{\prime\prime}$, the function $\phi$
satisfies

$\phi(\underline{h}^{0})=t_{0}/T-\sum_{\omega\in\left\\{0,1\right\\}^{s}\setminus\left\\{0\right\\}}(-1)^{|\omega|}\phi(\underline{h}^{\omega}).$

The right-hand side of this identity is clearly _low rank_ according to the
terminology preceding Lemma 6.4.

Summing over $\underline{h}\in\mathcal{H}^{\prime\prime}$ in (6.3), we deduce
the existence of a low rank function $\psi:\mathbb{Z}^{s-2}\to\mathbb{T}$ such
that

$\sum_{\underline{h}}\left|\sum_{x}F_{u}(x)e\bigl{(}\psi(\underline{h})x\bigr{)}\right|\gg\delta^{2^{s+3}+1-2^{s}}(N/q)^{s-1}.$

Employing Lemma 6.4 then gives

$\left\|F_{u}\right\|_{U^{s-1}}^{2^{s-1}}\gg\delta^{(2^{s+3}+1-2^{s})2^{s+1}}(N/q)^{s}.$

Summing over permissible $u$, then extending to the full sum over $u\in[q]$ by
positivity, we obtain the bound claimed in the lemma. ∎

##  7\. Proof of the cut norm inverse theorem

In this section we complete our proof of Theorem 1.6. We first show how the
dual function is controlled by the $U^{5}$-norm, and hence by the degree
lowering of §6, the dual is controlled by the $U^{1}$-norm.

The following can be found in the discussion following [3, Proposition 3.6].
Although the statement therein is for norms, and not seminorms, one can check
that the (simple) argument remains valid in this greater generality333On
occasion the relevant results in [3] appear to assume that unit balls are
_bounded_ (if we take the definition of _convex body_ to be a compact convex
set with non-empty interior), which may not be true for the unit ball of a
seminorm. However, the boundedness assumption is not necessary in the
pertinent proofs. Moreover, one could quotient by the norm zero set to obtain
a genuine norm..

######  Lemma 7.1.

Let $\|\cdot\|$ be a seminorm on the space of complex-valued functions
supported on $[N]$. For any such function $f$ and $\varepsilon>0$ there exists
a decomposition $f=f_{str}+f_{unf}$ such that

$\left\|f_{str}\right\|^{*}\leq\varepsilon^{-1}\left\|f\right\|_{2}\quad\text{and}\quad\left\|f_{unf}\right\|\leq\varepsilon\left\|f\right\|_{2}.$

######  Lemma 7.2 ($U^{5}$-control of the dual).

There exists an absolute constant $C$ such that for $N\geq Cq\delta^{-C}$ the
following holds. Let $g_{0},g_{1},f:\mathbb{Z}\to\mathbb{C}$ be 1-bounded
functions, each with support in $[N]$. Suppose that

$\left|\Lambda_{q,N}(g_{0},g_{1},f)\right|\geq\delta\Lambda_{q,N}(1_{[N]}).$

Then, on defining the dual

$G(x):=\mathbb{E}_{y\in[M]}g_{0}(x-qy^{2})g_{1}(x+y-qy^{2}),$ (7.1)

we have

$\sum_{u\in[q]}\left\|G\right\|_{U^{5}(u+q\cdot\mathbb{Z})}^{2^{5}}\gg\delta^{2^{26}}\sum_{u\in[q]}\left\|1_{[N]}\right\|_{U^{5}(u+q\cdot\mathbb{Z})}^{2^{5}}.$

###### Proof.

Applying Lemma 7.1 to $f$ with
$\left\|\cdot\right\|:=\left\|\cdot\right\|^{\sharp}_{q}$ as defined in (1.5)
and $\varepsilon:=\tfrac{1}{2}\delta\Lambda_{q,N}(1_{[N]})N^{-1/2}$, we deduce
that

$|\Lambda_{q,N}(g_{0},g_{1},f_{str})|\geq\delta\Lambda_{q,N}(1_{[N]})-|\Lambda_{q,N}(g_{0},g_{1},f_{unf})|\\\
\geq\delta\Lambda_{q,N}(1_{[N]})-\left\|f_{unf}\right\|_{q,N}^{\sharp}\geq\tfrac{1}{2}\delta\Lambda_{q,N}(1_{[N]}).$

We note that our lower bound assumption on $N$ implies that
$\Lambda_{q,N}\left(1_{[N]}\right)\gg 1$. Hence the dual inequality (1.10)
gives

$\delta\ll N^{-1}|\left\langle
f_{str},G\right\rangle|\ll\delta^{-1}\left\|G\right\|^{\sharp}_{q}.$

Invoking Theorem 5.6 yields the result. ∎

Taken together, the work in §§3–6 gives the following.

###### Proof of Theorem 1.6.

Applying Lemma 7.2, we deduce that

$\sum_{u\in[q]}\left\|G\right\|_{U^{5}(u+q\cdot\mathbb{Z})}^{2^{5}}\gg\delta^{2^{26}}\sum_{u\in[q]}\left\|1_{[N]}\right\|_{U^{5}(u+q\cdot\mathbb{Z})}^{2^{5}},$

where $G$ is defined as in (7.1).

We now apply Lemma 6.5 three times. The first application gives

$\sum_{u\in[q]}\left\|G\right\|_{U^{4}(u+q\cdot\mathbb{Z})}^{2^{4}}\gg\delta^{2^{40}}\sum_{u\in[q]}\left\|1_{[N]}\right\|_{U^{4}(u+q\cdot\mathbb{Z})}^{2^{4}},$

a second replaces $U^{4}$ with $U^{3}$ at the cost of replacing
$\delta^{2^{40}}$ with $\delta^{2^{52}}$. With a final application, we obtain

$\sum_{u\in[q]}\left\|G\right\|_{U^{2}(u+q\cdot\mathbb{Z})}^{4}\gg\delta^{2^{62}}\sum_{u\in[q]}\left\|1_{[N]}\right\|_{U^{2}(u+q\cdot\mathbb{Z})}^{4}.$

Let $\eta:=\delta^{2^{62}}$. By the popularity principle, there are at least
$\Omega(\eta q)$ values of $u\in[q]$ for which
$\left\|G\right\|_{U^{2}(u+q\cdot\mathbb{Z})}^{4}\gg\eta\left\|1_{[N]}\right\|_{U^{2}(u+q\cdot\mathbb{Z})}^{4}$.
The inverse theorem for the $U^{2}$-norm then gives the existence of
$\phi(u)\in\mathbb{T}$ for which

$\left|\sum_{x}G(u+qx)e(\phi(u)x)\right|\gg\eta^{1/2}N/q.$ (7.2)

Set $T:=\left\lceil C\eta^{-1/2}N/q\right\rceil$, with $C$ an absolute
constant taken sufficiently large to ensure that, on rounding $\phi(u)$ to the
nearest fraction of the form $t/T$, the inequality (7.2) remains valid.

By Lemma 6.2, for each $u$ satisfying (7.2), there exists a positive integer
$q^{\prime}\ll\eta^{2}$ such that
$\|q^{\prime}q^{2}\phi(h)\|\ll\eta^{-7}q^{3}/N$. By a volume packing argument
similar to that given in the proof of Lemma 6.5, the function $\phi$ is
constant on a proportion of at least $\Omega\bigl{(}\eta^{11}\bigr{)}$ of the
residues $u\in[q]$ satisfying (7.2). Summing over these $u$, then extending
the sum to all of $[q]$, we deduce the existence of $\alpha\in\mathbb{T}$ and
$q^{\prime}\ll\eta^{-2}$ such that
$\|q^{\prime}q^{2}\alpha\|\ll\eta^{-7}q^{3}/N$ and

$\sum_{u\in[q]}\left|\sum_{x}G(u+qx)e(\alpha x)\right|\gg\eta^{12}N.$ (7.3)

Expanding the dual function, there is a 1-bounded function $\psi(u\bmod q)$
such that the left-hand side of the above is equal to

$\sum_{u\in[q]}\psi(u\bmod q)\sum_{x\equiv
u(q)}\mathbb{E}_{y\in[M]}g_{0}(x-qy^{2})g_{1}(x+y-qy^{2})e(\alpha x/q)\\\
=\sum_{x}g_{0}(x)\psi(x\bmod q)e(\alpha
x/q)\mathbb{E}_{y\in[M]}g_{1}(x+y)e(\alpha y^{2}).$ (7.4)

Let us first suppose that $f=g_{0}$, we deal with the case $f=g_{1}$ shortly.
Setting

$\phi(x):=\psi(x\bmod q)e(\alpha x/q)\mathbb{E}_{y\in[M]}g_{1}(x+y)e(\alpha
y^{2}),$

we have $\left\langle f,\overline{\phi}\right\rangle\gg\eta^{12}N$. Our aim is
to show that $\phi$ can be approximated by a local function of the type
claimed in the lemma.

We begin by removing the phase from the expectation over $[M]$, at the cost of
passing to shorter progressions. Let $M^{\prime}\leq M/q^{\prime}q^{2}$ be a
quantity to be determined. If $y\in[M^{\prime}]$ then for any
$m\in[-M,M]\cap\mathbb{Z}$ we have

$\left|e(\alpha(m+q^{\prime}q^{2}y)^{2})-e(\alpha
m^{2})\right|\ll\left\|\alpha\left(2mq^{\prime}q^{2}y+(q^{\prime}q^{2}y)^{2}\right)\right\|\ll
q^{\prime}q^{4}\eta^{-7}M^{\prime}/M.$ (7.5)

Hence, partitioning $\mathbb{Z}$ into progressions $P$ of common difference
$q^{\prime}q^{2}$ and length $M^{\prime}$, there exist phases $\omega_{P}$
such that for any $x\in\mathbb{Z}$ we have

$\left|\mathbb{E}_{y\in[M]}g_{1}(x+y)e(\alpha
y^{2})-M^{-1}\sum_{P}\omega_{P}\sum_{y\in[M]\cap P}g_{1}(x+y)\right|\ll
q^{\prime}q^{4}\eta^{-7}M^{\prime}/M.$ (7.6)

Notice that there are at most $O(M/M^{\prime})$ progressions $P$ such that
$P\cap[M]\neq\emptyset$ (since we are assuming $M^{\prime}\leq
M/q^{\prime}q^{2}$).

Next we show how the phase $e(\alpha x/q)$ is approximately periodic. Suppose
that $z\in[M^{\prime\prime}]$, with $M^{\prime\prime}\leq M^{\prime}/q$ to be
determined. Then for any $x\in\mathbb{Z}$ we have

$\left|e\left(\alpha(x+q^{\prime}q^{3}z)/q\right)-e\left(\alpha
x\right)\right|\ll\left\|\alpha
q^{\prime}q^{2}\right\|M^{\prime\prime}\ll\eta^{-7}q^{3}M^{\prime\prime}/N$

and by a boundary estimate

$\left|\sum_{y\in[M]\cap P}g_{1}(x+q^{\prime}q^{3}z+y)-\sum_{y\in[M]\cap
P}g_{1}(x+y)\right|\ll qM^{\prime\prime}.$

It then follows from a telescoping identity that for all $x\in\mathbb{Z}$ and
$z\in[M^{\prime\prime}]$ we have

$\displaystyle\left|\phi(x+q^{\prime}q^{3}z)-\phi(x)\right|$
$\displaystyle\ll\frac{\eta^{-7}q^{3}M^{\prime\prime}}{N}+\frac{\eta^{-7}q^{\prime}q^{4}M^{\prime}}{M}+\frac{qM^{\prime\prime}}{M}\sum_{\begin{subarray}{c}P\\\
P\cap[M]\neq\emptyset\end{subarray}}1$
$\displaystyle\ll\frac{\eta^{-7}q^{\prime}q^{4}M^{\prime}}{M}+\frac{qM^{\prime\prime}}{M^{\prime}}.$

Taking $M^{\prime}:=c\eta^{19}M/q^{\prime}q^{4}$ and
$M^{\prime\prime}:=c\eta^{12}M^{\prime}/q$ for a sufficiently small absolute
constant $c>0$ we have

$\left|\phi(x+q^{\prime}q^{3}z)-\phi(x)\right|\leq\eta^{12}/C\quad\text{for
all }x\in\mathbb{Z}\text{ and }z\in[M^{\prime\prime}].$ (7.7)

Partitioning $\mathbb{Z}$ into translates $T$ of
$q^{\prime}q^{3}\cdot[M^{\prime\prime}]$ we deduce that

$\sum_{T}\biggl{|}\sum_{x\in T}f(x)\biggr{|}\gg\eta^{12}N.$

Write $\chi(x)$ for the phase of the inner sum when $x\in T$. Then $\chi$ is a
1-bounded local function of modulus $q^{\prime}q^{3}$ and resolution
$\Omega\left((\delta/q)^{O(1)}M\right)$ satisfying

$\sum_{x}f(x)\overline{\chi(x)}\gg\delta^{2^{66}}N,$

as required.

Next we give the argument for when $f=g_{1}$. Returning to (7.4) we have

$\sum_{x}\left|\mathbb{E}_{y\in[M]}f(x+y)e(\alpha y^{2})\right|\gg\eta^{12}N.$

Utilising (7.5) and (7.6), we may partition $\mathbb{Z}$ into progressions $P$
of common difference $q^{\prime}q^{2}$ and length
$M^{\prime}:=c\eta^{19}M/q^{\prime}q^{4}$ such that

$\sum_{x}\sum_{P}\left|\mathbb{E}_{y\in[M]\cap P}f(x+y)\right|\gg\eta^{12}N.$

Since $O(M/M^{\prime})$ of the $P$ intersect $[M]$, the pigeon-hole principle
gives $P^{\prime}:=P\cap[M]$ such that

$\sum_{x}\left|\sum_{y\in P^{\prime}}f(x+y)\right|\gg\eta^{12}NM^{\prime}.$

In particular $|P^{\prime}|\gg\eta^{12}M^{\prime}\gg(q/\delta)^{C}M$.

Partitioning $\mathbb{Z}$ into translates of $P^{\prime}$ of the form

$\mathbb{Z}=\bigsqcup_{i}(a_{i}+P^{\prime}),$

the pigeon-hole principle gives $z\in P^{\prime}$ such that

$\sum_{i}\left|\sum_{y\in P^{\prime}}f(a_{i}+y+z)\right|\gg\eta^{12}N.$

Writing $\chi(x)$ for the phase of the inner sum when $x\in a_{i}+P$ one sees
that $\chi$ is a local function of resolution $\gg(q/\delta)^{C}M$ and modulus
$q^{\prime}q^{2}$ which satisfies $\left\langle
f,\chi\right\rangle\gg\eta^{12}N$. The proof is complete on noting that a
local function of modulus $q^{\prime}q^{2}$ is also a local function of
modulus $q^{\prime}q^{3}$. ∎

##  Appendix A Basic theory of the Gowers norms

######  Lemma A.1 (Inverse theorem for the $U^{2}$-norm).

Let $f:\mathbb{Z}\to\mathbb{C}$ be a $1$-bounded function with support in
$[N]$. Then there exists $\alpha\in\mathbb{T}$ such that

$\|f\|_{U^{2}}^{4}\leq N\left|\sum_{x}f(x)e(\alpha x)\right|^{2}.$

###### Proof.

Using the definition of the Fourier transform (1.8), together with
orthogonality of additive characters, we have

$\left\|f\right\|_{U^{2}}^{4}=\int_{\mathbb{T}}\bigl{|}\hat{f}(\alpha)\bigr{|}^{4}\mathrm{d}\alpha\leq\big{\|}\hat{f}\big{\|}_{\infty}^{2}\int_{\mathbb{T}}\bigl{|}\hat{f}(\alpha)\bigr{|}^{2}\mathrm{d}\alpha\leq\big{\|}\hat{f}\big{\|}_{\infty}^{2}N.$

∎

For each $\omega\in\\{0,1\\}^{s}$, let $f_{\omega}:\mathbb{Z}\to\mathbb{C}$ be
a function with finite support. Then we define the _Gowers inner product_ by

$[f_{\omega}]_{U^{s}}:=\sum_{x,h_{1},\dots,h_{s}}\prod_{\omega\in\left\\{0,1\right\\}^{s}}\mathcal{C}^{|\omega|}f_{\omega}(x+\omega\cdot
h).$

Here $\mathcal{C}$ denotes the operation of complex conjugation. Notice that
$[f]_{U^{s}}=\left\|f\right\|_{U^{s}}^{2^{s}}$.

######  Lemma A.2 (Gowers–Cauchy–Schwarz).

For each $\omega\in\\{0,1\\}^{s}$, let $f_{\omega}:\mathbb{Z}\to\mathbb{C}$ be
a function with finite support. Then we have

$[f_{\omega}]_{U^{s}}\leq\prod_{\omega\in\\{0,1\\}^{s}}\|f_{\omega}\|_{U^{s}}.$

###### Proof.

See [9, Exercise 1.3.19]. ∎

######  Lemma A.3 (Phase invariance for $s\geq 2$).

Let $L\in\mathbb{R}[x,h_{1},\dots,h_{s}]$ be a linear form, with $s\geq 2$ and
let $f:\mathbb{Z}\to\mathbb{C}$. Then

$\biggl{|}\sum_{x,h_{1},\dots,h_{s}}\Delta_{h_{1},\dots,h_{s}}f(x)e(L(x,h_{1},\dots,h_{s}))\biggr{|}\leq\left\|f\right\|_{U^{s}}^{2^{s}}.$

###### Proof.

The linear form may be written as

$L(x,h_{1},\dots,h_{s})=\alpha x+\beta_{1}(x+h_{1})+\dots+\beta_{s}(x+h_{s}),$

for some real $\alpha$ and $\beta_{i}$. Write $f_{0}(x):=f(x)e(\alpha x)$,
$f_{e_{i}}(x):=f(x)e(-\beta_{i}x)$ for $i=1,\dots,s$, and for
$\omega\in\left\\{0,1\right\\}^{s}\setminus\left\\{0,e_{1},\dots,e_{s}\right\\}$
set $f_{\omega}:=f$. Then by Gowers–Cauchy–Schwarz we have

$\biggl{|}\sum_{x,h_{1},\dots,h_{s}}\Delta_{h_{1},\dots,h_{s}}f(x)e(L(x,h_{1},\dots,h_{s}))\biggr{|}\leq\prod_{\omega}\left\|f_{\omega}\right\|.$

It therefore suffice to prove that for a phase function $e_{\alpha}:x\mapsto
e(\alpha x)$ $\left\|fe_{\alpha}\right\|_{U^{s}}=\left\|f\right\|_{U^{s}}.$
The latter follows on observing that

$\Delta_{h_{1},\dots,h_{s}}(fe_{\alpha})=\left(\Delta_{h_{1},\dots,h_{s}}f\right)\left(\Delta_{h_{1},\dots,h_{s}}e_{\alpha}\right),$

and for any $x,h_{1},\dots,h_{s}$ with $s\geq 2$ we have
$\Delta_{h_{1},\dots,h_{s}}e_{\alpha}(x)=1.$ ∎

######  Lemma A.4 (Box Cauchy–Schwarz).

Let $\mu_{1},\mu_{2},\mu_{3}$ be probability measures on $\mathbb{Z}$ with the
discrete sigma algebra. If $F_{1},F_{2},F_{3}$ are 1-bounded function on
$\mathbb{Z}^{2}$ and $F$ is a 1-bounded function on $\mathbb{Z}^{3}$ then

$\left|\sum_{x\in\mathbb{Z}^{3}}F_{1}(x_{2},x_{3})F_{2}(x_{1},x_{3})F_{3}(x_{1},x_{2})F(x)\underline{\mu}(x)\right|^{8}\\\
\leq\sum_{x^{0},x^{1}\in\mathbb{Z}^{3}}\prod_{\omega\in\left\\{0,1\right\\}^{3}}\mathcal{C}^{|\omega|}F(x_{1}^{\omega_{1}},x_{2}^{\omega_{2}},x_{3}^{\omega_{3}})\mu_{1}(x_{1}^{0})\mu_{1}(x_{1}^{1})\mu_{2}(x_{2}^{0})\mu_{2}(x_{2}^{1})\mu_{3}(x_{3}^{0})\mu_{3}(x_{3}^{1}).$

## References

  * BC [17] J. Bourgain and M.-C. Chang.  Nonlinear Roth type theorems in finite fields.  Israel J. Math., 221(2):853–867, 2017.
  * BL [96] V. Bergelson and A. Leibman.  Polynomial extensions of van der Waerden’s and Szemerédi’s theorems.  J. Amer. Math. Soc., 9(3):725–753, 1996.
  * Gow [10] W. T. Gowers.  Decompositions, approximate structure, transference, and the Hahn-Banach theorem.  Bull. Lond. Math. Soc., 42(4):573–606, 2010.
  * GT [08] B. Green and T. Tao.  Quadratic uniformity of the Möbius function.  Ann. Inst. Fourier (Grenoble), 58(6):1863–1935, 2008.
  * Pel [19] S. Peluse.  On the polynomial szemerédi theorem in finite fields.  Duke Math. J., 168(5):749–774, 04 2019.
  * PP [19] S. Peluse and S. Prendiville.  Quantitative bounds in the non-linear Roth theorem.  ArXiv e-prints, 2019.
  * PP [20] S. Peluse and S. Prendiville.  A polylogarithmic bound in the nonlinear Roth theorem.  ArXiv e-prints, 2020.
  * Pre [17] S. Prendiville.  Quantitative bounds in the polynomial Szemerédi theorem: the homogeneous case.  Discrete Anal., pages 34, Paper No. 5, 2017.
  * Tao [12] T. Tao.  Higher order Fourier analysis, volume 142 of Graduate Studies in Mathematics.  American Mathematical Society, Providence, RI, 2012.
  * TZ [16] T. Tao and T. Ziegler.  Concatenation theorems for anti-Gowers-uniform functions and Host-Kra characteristic factors.  Discrete Anal., pages 60, Paper No. 13, 2016.