\section{Introduction}\label{sec1}
Gowers~\cite[Problem 11.4]{Go2} has posed the problem of obtaining quantitative bounds in the polynomial Szemer\'edi theorem of Bergelson and Leibman~\cite{BL}, which states that if $P_1,\dots,P_m\in\Z[y]$ all have zero constant term, then any subset $A$ of $[N]:=[1,N]\cap\N$ containing no nontrivial polynomial progression
\begin{equation}\label{eq1.1}
x,x+P_1(y),\dots,x+P_m(y)
\end{equation}
satisfies $|A|=o(N)$. In this paper, we prove the first such bound over the integers for the non-linear Roth configuration $x,x+y,x+y^2$.

\begin{theorem}\label{thm1.1}
If $A\subset[N]$ contains no nontrivial progression of the form
\begin{equation}\label{eq1.2}
x,x+y,x+y^2,
\end{equation}
then
\[
|A|\ll\f{N}{(\log\log{N})^{2^{-157}}}.
\]
\end{theorem}
\begin{remark}\label{rmk1.2}
We did not try to optimize the exponent of $\log\log{N}$ in Theorem~\ref{thm1.1}, preferring instead to keep explicit quantities appearing in the proof as simple as possible.
\end{remark}

Proving a quantitative version of the polynomial Szemer\'edi theorem is a difficult generalization of the problem of proving bounds in Szemer\'edi's theorem, and very little is known outside of a few special cases. Indeed, Theorem~\ref{thm1.1} is the first effective bound obtained in the integers for sets lacking a polynomial progression~\eqref{eq1.1} involving polynomials $P_1,\dots,P_m$ of differing degrees. Prior to our work, quantitative bounds were only known for two-term progressions $x,x+P(y)$, due to S\'ark\"ozy~\cite{Sa1,Sa2}, Balog, Pelik\'an, Pintz, and Szemer\'edi \cite{BPPS}, Slijep\v{c}evi\'{c} \cite{Sl}, and Lucier \cite{L}, for arithmetic progressions $x,x+y,\dots,x+(k-1)y$, due to Gowers~\cite{Go1,Go3}, and for arithmetic progressions with common difference equal to a perfect $d^{th}$ power $x,x+y^d,\dots,x+(k-1)y^d$, due to the second author~\cite{Pr}.

The finite field analogue of Gowers's problem, where one seeks to bound the size of subsets of finite fields lacking nontrivial polynomial progressions, has very recently received much attention, and more is known than in the integer setting. Bourgain and Chang~\cite{BC} studied the non-linear Roth configuration in finite fields, proving a power-saving bound for sets lacking $x,x+y,x+y^2$. Following this, the first author~\cite{Pe1} proved power-saving bounds for sets lacking more general three-term progressions $x,x+P_1(y),x+P_2(y)$ whenever $P_1$ and $P_2$ are affine-linearly independent. Dong, Li, and Sawin~\cite{DLS} shortly after obtained an improved power-saving exponent for these three-term progressions. The first author~\cite{Pe2} then proved power-saving bounds for sets lacking arbitrarily long polynomial progressions $x,x+P_1(y),\dots,x+P_m(y)$ whenever $P_1,\dots,P_m$ are affine-linearly independent.

We now briefly discuss on the proof of Theorem~\ref{thm1.1}. Our strategy is to adapt the argument of~\cite{Pe2} in finite fields to the integer setting. There are multiple issues with applying the arguments of~\cite{Pe2} in the integers, however, so the proof of Theorem~\ref{thm1.1} requires several significant modifications and additions. The key idea of~\cite{Pe2} is that if one can control the count of certain polynomial progressions in a set by the Gowers $U^s$-norm, then one can use this and understanding of shorter progressions to prove control of the count by the $U^{s-1}$-norm. Thus, if one understands shorter progressions and can show control by any $U^s$-norm, then one can deduce control by the $U^1$-seminorm. As the $U^1$-seminorm is simply the absolute value of the average (or sum, depending on the choice of normalization) of a function over its domain, this is very powerful information. In the proof of Theorem~\ref{thm1.1}, we use it to prove that sets lacking the non-linear Roth configuration have a density increment on a progression with very small common difference.

A variety of perspectives, both ergodic and combinatorial, can be used to establish that the count of non-linear Roth configurations is controlled by a $U^1$-seminorm, in a qualitative sense. The novelty of~\cite{Pe2} and the proof of Theorem~\ref{thm1.1} is that they demonstrate this in a quantitatively effective manner, with polynomial bounds, by avoiding standard tools of higher order Fourier analysis that give either no quantitative bounds or poor ones. Indeed, while Gowers norms of high degree such as the $U^5$-norm play a role in our argument, we completely avoid using the inverse theorems for these norms, the equidistribution theory of nilsequences, or any version of the arithmetic regularity lemma, requiring only Fourier analysis and numerous applications of the Cauchy--Schwarz inequality in their place.

Perhaps the biggest difficulty in adapting the argument of~\cite{Pe2} to the integer setting is in first showing that the count of non-linear Roth configurations is controlled by some $U^s$-norm. While this is not too difficult to accomplish in finite fields by using Bergelson and Leibman's PET induction scheme~\cite{BL}, such an argument instead yields control in terms of an average of certain Gowers box norms in the integer setting. We must then show, with quantitative bounds, that this average of Gowers box norms is controlled by a $U^s$-norm. We do this by proving an explicit, quantitative version of a special case of a concatenation theorem of Tao and Ziegler~\cite{TZ}, with polynomial bounds.

This paper is organized as follows. In Section~\ref{sec2}, we set notation and recall some basic facts about Gowers norms. In Section~\ref{sec3}, we give a more detailed outline of the proof of Theorem~\ref{thm1.1}. In Section~\ref{sec4}, we show that the non-linear Roth configuration is controlled by an average of three-dimensional Gowers box norms. We show that this average is controlled by an average of $U^5$-norms localized to certain arithmetic progressions in Section~\ref{sec5} by proving a quantitative concatenation result. In Section~\ref{sec6}, we prove that $U^s$-control of the non-linear Roth configuration implies $U^{s-1}$-control, which we combine with the results of Section~\ref{sec5} in Section~\ref{sec7} to deduce a density increment lemma and thus prove Theorem~\ref{thm1.1}.

\section{Notation and preliminaries}\label{sec2}
We say that a function $f:\Z\to\C$ is \textit{$1$-bounded} if $\|f\|_{L^\infty}\leq 1$, and for any finite subset $S\subset\Z$, we denote the average of $f$ over $S$ by $\E_{x\in S}f(x):=\f{1}{|S|}\sum_{x\in S}f(x)$. When $f$ is finitely supported, we define its \textit{Fourier transform} $\hat{f}:\T\to\C$ by
\[
\hat{f}(\gamma):= \sum_x f(x) e(\gamma x)
\]
and the convolution of $f$ with another finitely supported function $g:\Z\to\C$ by
\[
(f*g)(x):=\sum_{y}f(y)g(x-y).
\]
We normalize the $\ell^p$-norms on the space of complex-valued functions on $\Z$ by setting $\|f\|_{\ell^p}^p:=\sum_x|f(x)|^p$. If $\|\cdot\|$ is any norm on an inner product space, recall that its dual norm $\|\cdot\|^*$ is defined by
\[
\|f\|^{*}:=\sup_{\|g\|=1}|\langle f,g\rangle|.
\]
In the proof of Theorem~\ref{thm1.1}, we will use the standard inner product on the space of complex-valued functions supported on $[N]$, defined by
\[
\langle f,g\rangle:=\sum_{x\in[N]}f(x)\overline{g(x)}.
\]

For any $\delta,M>0$, we define the weight $\mu_{\delta,M} : \Z \to [0,\infty)$ by
\[
\mu_{\delta,M}(h):=\f{\#\{(h_1, h_2) \in [\delta M]^2 : h_1 - h_2 = h\}}{\delta^2M}.
\]
Note that $\supp\mu_{\delta,M}\subset(-\delta M,\delta M)$, $\|\mu_{\delta,M}\|_{\ell^1}=M$, and $\|\mu_{\delta,M}\|_{\ell^2}^2\leq M/\delta$.

For any $f:\Z\to\C$ and $h\in\Z$, define the function $\Delta_hf:\Z\to\C$ by $\Delta_hf(x):=f(x+h)\overline{f(x)}$. Also define, for every $h_1,\dots,h_s\in\Z$, the function $\Delta_{h_1,\dots,h_s}f:\Z\to\C$ by
$\Delta_{h_1,\dots,h_s}f(x):=(\Delta_{h_1}\cdots\Delta_{h_s}f)(x).$ In Section~\ref{sec6}, we will use the notation $\Delta_{\ul{h}}f$ where $\ul{h}=(h_1,\dots,h_k)$ is a $k$-tuple of integers to denote the function $\Delta_{h_1,\dots,h_k}f$. We similarly define, for $(h_1,h_1')\in\Z^2$, the function $\Delta'_{(h_1,h_1')}f:\Z\to\C$ by $\Delta'_{(h_1,h_1')}f(x):=f(x+h_1)\overline{f(x+h_1')}.$

We now recall the definitions of the Gowers uniformity and box norms.
\begin{definition}[$U^s$-norm]\label{def2.1}
Let $f:\Z\to\C$ be a function with finite support. We define the $U^s$-norm of $f$ by
\[
\|f\|_{U^s}^{2^s}:=\sum_{x,h_1,\dots,h_s}\Delta_{h_1,\dots,h_s}f(x).
\]

We also define the $U^s$-norm of $f$ localized to a subset $T\subset\Z$ by
\[
\|f\|_{U^s(T)}:=\|f1_T\|_{U^s}.
\]
\end{definition}
\begin{definition}[Gowers box norms]\label{def2.2}
Let $Q_1,\dots,Q_d\subset\Z$ be finite subsets and $f:\Z\to\C$ be a function with finite support. We define
\[
\|f\|_{\square_{Q_1,\dots,Q_d}^d}^{2^d}:=\sum_x\sum_{\substack{h_i,h_i'\in Q_i \\ i=1,\dots, d}}\Delta'_{(h_1,h_1')}\cdots\Delta'_{(h_d,h_d')}f(x).
\]
\end{definition}

We will occasionally need the Gowers--Cauchy--Schwarz inequality. To state it, we first define the $U^s$-inner product.
\begin{definition}[$U^s$-inner product]\label{def2.3}
Let $s\in\N$ and, for each $\omega\in\{0,1\}^s$, let $f_\omega:\Z\to\C$ be a function with finite support. We define the $U^s$-inner product of the $f_\omega$'s by
\[
[f_\omega]_{U^s}:=\sum_{x,h_1,\dots,h_s}\prod_{\omega\in\{0,1\}^s}\mathcal{C}^{|\omega|}f_\omega(x+\omega\cdot (h_1,\dots,h_s)),
\]
where $\mathcal{C}$ denotes the complex conjugation operator.
\end{definition}
\begin{lemma}[Gowers--Cauchy--Schwarz inequality]\label{lem2.4}
Let $s\in\N$ and, for each $\omega\in\{0,1\}^s$, let $f_\omega:\Z\to\C$ be a function with finite support. We have
\[
|[f_\omega]_{U^s}|\leq \prod_{\omega\in\{0,1\}^s}\|f_\omega\|_{U^s}.
\]
\end{lemma}

Finally, we will need the following result, which is an easy consequence of basic Fourier analysis.
\begin{lemma}[Inverse theorem for the $U^2$-norm]\label{def2.5}
Let $f:\Z\to\C$ be a $1$-bounded function supported on $[N]$ and $\delta>0$. If
\[
\|f\|_{U^2}^4\geq \delta N^3,
\]
then there exists a $\beta\in\T$ such that
\[
\left|\sum_{x}f(x)e(\beta x)\right|\geq \delta^{1/2} N.
\]
\end{lemma}
\begin{proof}
Using the definition of the Fourier transform, together with the orthogonality of additive characters and Parseval's identity, we have
\[
\|f\|_{U^2}^4 = \int_{\T} |\hat{f}(\gamma)|^4d\gamma \leq \|\hat{f}\|_{L^\infty}^2 \int_{\T} |\hat{f}(\gamma)|^2d\gamma \leq \|\hat{f}\|_{L^\infty}^2 N,
\]
so that $\|\widehat{f}\|_{L^\infty}\geq\delta^{1/2}N$.
\end{proof}

\section{An outline of the argument}\label{sec3}

\subsection{The density increment}\label{ss3.1}

Our proof proceeds via a density increment argument. This is the same method of proof used by Roth~\cite{R} to bound the size of sets lacking three-term arithmetic progressions and by Gowers~\cite{Go1,Go3} to bound the size of sets lacking longer arithmetic progressions. Roth and Gowers show that if a set $A\subset[N]$ of density $\alpha:=|A|/N$ contains no nontrivial $k$-term arithmetic progressions, then there exists a progression $P=a+q\cdot[N']$ of length $N'\asymp N^{\Omega_k(1)}$ on which $A$ has increased density $|A\cap P|/|P|\gg \alpha+\alpha^{O_k(1)}$, provided $N\gg\alpha^{-O_k(1)}$. Consider the rescaled version $A'\subset[N']$ of $A\cap P$ defined by
\begin{equation}\label{3.??}
A':=\{n\in[N']:a+qn\in A\cap P\},
\end{equation}
and note that if $A$ has no $k$-term arithmetic progressions, then neither does $A'$. One can then repeat this with $A'$ and $N'$ in place of $A$ and $N$, respectively.

The success of the above argument crucially relies on the fact that $k$-term arithmetic progressions are preserved under translation and scaling, and similarly the argument in~\cite{Pr} relies on the fact that $k$-term arithmetic progressions with common difference equal to a perfect $d^{th}$ power are preserved under translation and scaling by a perfect $d^{th}$ power. These are very special properties that the vast majority of polynomial progressions, including the non-linear Roth configuration~\eqref{eq1.2}, lack.

Indeed, if $A\subset[N]$ has no nontrivial configurations of the form~\eqref{eq1.2}, then the rescaled set $A'\subset[N']$ defined as in~\eqref{3.??} has no nontrivial configurations of the form $x,x+y,x+qy^2$. But if $q>N'$, then every subset of $[N']$ has this property because $x$ and $x+qy^2$ cannot both lie in $[N]$ when $y\neq 0$, and thus there is no hope of continuing the density increment argument in this case. In contrast, the inequality $q>N'$ can (and does) occur in the arguments of~\cite{R},~\cite{Go1,Go3}, and~\cite{Pr} because these papers consider progressions that are preserved under scaling.

To deal with the poor behavior of the non-linear Roth configuration under scaling, we prove a stronger density increment lemma that ensures that the arithmetic progression on which we find a density increment has very small step size. We show that if $A\subset[N]$ has density $\alpha:=|A|/N$ and lacks nontrivial configurations of the form~\eqref{eq1.2}, then there exists a progression $P=a+q\cdot[N']$ with common difference $q\ll\alpha^{-O(1)}$ and length $N'\gg\alpha^{O(1)}N^{1/2}$ such that we have the density increment
\begin{equation}\label{eq3.1}
|A\cap P|/|P|\gg\alpha+\alpha^{O(1)},
\end{equation}
provided $N\gg\alpha^{-O(1)}$. Defining $A'\subset[N']$ to be the rescaled set as in~\eqref{3.??}, we thus see that $A'$ has increased density $\alpha+\alpha^{O(1)}$ in $[N']$ and lacks nontrivial configurations of the form
\begin{equation}\label{eq3.2}
x,x+y,x+qy^2.
\end{equation}
The coefficient $q$ is sufficiently small that the methods employed to treat our original configuration~\eqref{eq1.2} still apply to the new configuration~\eqref{eq3.2}, allowing us to prove a similar density increment result for sets lacking~\eqref{eq3.2}. We can thus continue the density increment iteration, which terminates in at most $O(\alpha^{-O(1)})$ steps and yields the density bound appearing in Theorem~\ref{thm1.1}. This general density increment result is Lemma~\ref{lem7.2}.

For notational simplicity, we restrict to the case $q=1$ for the remainder of this section. We deduce our density increment result by proving that any weighted count of the non-linear Roth configuration is controlled by a sum of local $U^1$-seminorms of one of the weights, in a sense to be made precise shortly in Lemma~\ref{lem3.1} below. For any finitely supported functions $f_0,f_1,f_2:\Z\to\C$, define the counting operator
\begin{equation}\label{eq3.3}
\Lambda(f_0,f_1,f_2):=\sum_x\sum_{y\in[N^{1/2}]}f_0(x)f_1(x+y)f_2(x+y^2).
\end{equation}

The following is our key lemma used to deduce a density increment in the $q=1$ case. The more general version that is needed for the proof of Theorem~\ref{thm1.1} is Theorem~\ref{thm7.1}.
\begin{lemma}\label{lem3.1}
Let $f_0,f_1,f_2:\Z\to\C$ be $1$-bounded functions supported in the interval $[N]$ and $\delta>0$. Suppose that
\[
|\Lambda(f_0,f_1,f_2)|\geq\delta N^{3/2}.
\]
Then there exist positive integers $q\ll\delta^{-O(1)}$ and $\delta^{O(1)}N^{1/2}\ll N'\leq N^{1/2}$ such that
\begin{equation}\label{eq3.4}
\sum_x\left|\sum_{y\in[N']}f_1(x+qy)\right|\gg\delta^{O(1)}NN',
\end{equation}
provided $N\gg\delta^{-O(1)}$.
\end{lemma}

It is then a routine matter to use the large local average~\eqref{eq3.4} to show that sets lacking the non-linear Roth configuration~\eqref{eq1.2} satisfy the density increment~\eqref{eq3.1} when $N\gg\alpha^{-O(1)}$. This is carried out, in greater generality, in the proof of Lemma~\ref{lem7.2}.

\subsection{van der Corput differencing and quantitative concatenation}\label{ss3.2}

To prove Lemma~\ref{lem3.1}, we first prove that our counting operator~\eqref{eq3.3} 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 many times, we show in Section~\ref{sec4} that, when $f_0,f_1,f_2:\Z\to\C$ are $1$-bounded functions supported in the interval $[N]$, largeness of the counting operator~\eqref{eq3.3} implies largeness of an average of (weighted versions of) sums of the form
\begin{equation}\label{eq3.5}
\E_{a,b\in[N^{1/2}]}\sum_x\sum_{h_1,h_2,h_3\in[N^{1/2}]}\Delta_{ah_1,(a+b)h_2,bh_3}f_2(x).
\end{equation}
\begin{remark}The weighted version of the above that we actually encounter is an average of normalized three-dimensional Gowers box norms of $f_2$.\end{remark} In Section~\ref{sec5}, we show that largeness of~\eqref{eq3.5} implies largeness of $\|f_2\|_{U^5}$.

If there were no dependence between the coefficients of the $h_i$ in~\eqref{eq3.5}, then it would be easy to bound~\eqref{eq3.5} in terms of $\|f_2\|_{U^3}$. We illustrate why this is the case for the following simpler average of sums:
\begin{equation}\label{eq3.6}
\E_{a\in [N^{1/2}]}\sum_{h_3\in[N^{1/2}]}\|\Delta_{ah_3}f\|_{U^2}^4=\E_{a\in[N^{1/2}]}\sum_{x,h_1,h_2}\sum_{h_3\in[N^{1/2}]}\Delta_{h_1,h_2,ah_3}f(x).
\end{equation}
Swapping the order of summation in~\eqref{eq3.6}, we apply the Cauchy--Schwarz inequality to double the $a$ and $h_3$ variables, yielding a bound for~\eqref{eq3.6} in terms of
\begin{equation}\label{eq3.7}
\E_{a,c\in[N^{1/2}]}\sum_{h_3,h_3'\in[N^{1/2}]}\|\Delta_{ah_3-ch_3'}f\|_{U^2}^4.
\end{equation}
For a random choice of $a,c\in[N^{1/2}]$, the progression $a\cdot[N^{1/2}]-c\cdot[N^{1/2}]$ covers a large portion of the interval $(-N,N)$ relatively smoothly. One can easily make this intuition rigorous and thus deduce that largeness of~\eqref{eq3.7} implies largeness of $\|f\|_{U^3}$.

The problem remains of how to handle~\eqref{eq3.5}. If we did not care about getting quantitative bounds, we could apply the following `concatenation' theorem of Tao and Ziegler~\cite{TZ}.
\begin{theorem}[{Tao and Ziegler~\cite[rank $1$ case of Theorem 1.24]{TZ}}]\label{thm3.2}
Let $I$ be a finite indexing set and $d$ be a positive integer. For each $j=1,\dots,d$, let $(Q_{i,j})_{i\in I}$ be a family of finite-length arithmetic progressions in $\Z$. There exists a function $c:(0,\infty)\to(0,\infty)$ depending only on $d$ and satisfying $c(\ve)\to 0$ as $\ve\to 0$ such that the following holds.

Suppose that $f:\Z\to\C$ is $1$-bounded and that
\[
\E_{i,i'\in I}\|f\|_{\square^{d^2}_{(\ve Q_{i,j}+\ve Q_{i',j'})_{1\leq j,j'\leq d}}}\leq\ve
\]
for some $\ve>0$. Then
\[
\E_{i\in I}\|f\|_{\square^d_{(Q_{i,j})_{1\leq j\leq d}}}\leq c(\ve).
\]
\end{theorem}
By three applications of the Cauchy--Schwarz inequality, one can bound~\eqref{eq3.5} by a sum of $8^{th}$ powers of Gowers box norms of the form $\|f_2\|_{\square^3_{a[N^{1/2}],(a+b)[N^{1/2}],b[N^{1/2}]}}$, so that if we were only seeking a qualitative result, we could apply the above theorem with $I=[N^{1/2}]^2$, $d=3$, and $Q_{(a,b),1},Q_{(a,b),2},$ and $Q_{(a,b),3}$ equaling $a[N^{1/2}],(a+b)[N^{1/2}]$, and $b[N^{1/2}]$, respectively. However, because Tao and Ziegler's argument does not yield quantitative bounds, we cannot use Theorem~\ref{thm3.2} to prove our bound for the non-linear Roth theorem. In its place, we instead prove a quantitative version of a special case of Theorem~\ref{thm3.2} in Theorem~\ref{thm5.1}, using a very different argument that gives polynomial bounds. We spend the remainder of this subsection sketching this argument.

Our argument begins by viewing (a weighted version of) the quantity~\eqref{eq3.5} as a (weighted) average and sum over $b$ and $h_3$ of the following average of Gowers box norms
\begin{equation}\label{eq3.8}
\|g\|_b^4:=\E_{a\in[N^{1/2}]}\|g\|^4_{\square_{a[N^{1/2}],(a+b)[N^{1/2}]}^2},
\end{equation}
so that it suffices to bound
\begin{equation}\label{eq3.9}
\sum_{b,h_3\in[N^{1/2}]}\|\Delta_{bh_3}f_2\|_b^4.
\end{equation}
Note that if we could bound the quantity $\|\Delta_{b h_3}f_2\|_b$ in the sum~\eqref{eq3.9} in terms of the $U^4$-norm of $\Delta_{b h_3}f_2$ for many pairs $(b,h_3)$, then by following the argument used to treat~\eqref{eq3.6} we can obtain a bound in terms of the $U^5$-norm. We show that, on average, one can control $\|\cdot\|_b$ in terms of $\|\cdot\|_{U^4}$, with polynomial bounds. We prove a more general (weighted) version of the following lemma as Corollary~\ref{cor5.6}.
\begin{lemma}\label{lem3.4}
For each $b\in[N^{1/2}]$ let $f_b:\Z\to\C$ be a $1$-bounded function supported in the interval $[N]$ and $\delta>0$. Suppose that
\[
\E_{b\in[N^{1/2}]}\|f_b\|_b^4\geq \delta N^3.
\]
Then
\[
\E_{b\in[N^{1/2}]}\|f_b\|_{U^4}^{16}\gg \delta^{O(1)}N^5.
\]
\end{lemma}

To finish this subsection, we will briefly discuss the proof of this important lemma. For most choices of $b\in[N^{1/2}]$, the `directions' $a$ and $a+b$ of the box norm $\|\cdot\|_{\square^2_{a[N^{1/2}],(a+b)[N^{1/2}]}}$ are usually close to `independent' for most choices of $a\in[N^{1/2}]$, in the sense that $a$ and $a+b$ have small greatest common divisor. The proof of Lemma~\ref{lem3.4} thus begins by viewing such $\|\cdot\|_b$ 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).
\]
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 largeness of $\|g\|_{\square_{d_1[N^{1/2}],d_2[N^{1/2}]}^2}$ when $d_1$ and $d_2$ have small greatest common divisor implies that $g$ correlates with a product of two functions $l(x)$ and $r(x)$ that are almost-invariant (in a sense to be made precise in Section~\ref{sec5}) under shifts by integer multiples of $d_2$ and $d_1$, respectively. As a consequence of this, for most $b\in[N^{1/2}]$, largeness of $\|f\|_{b}$ implies largeness of
\begin{equation}\label{eq3.10}
\E_{a\in[N^{1/2}]}\left|\sum_xf(x)l_{a+b}(x)r_{a}(x)\right|,
\end{equation}
where $l_{a+b}$ and $r_a$ are almost-invariant under shifts by integer multiples of $a+b$ and $a$, respectively. We then show that largeness of~\eqref{eq3.10} implies largeness of
\[
\sum_{x}l_{a+b}(x)l_{c+b}(x)r'_a(x)r'_c(x)
\]
for many pairs $a,c\in[N^{1/2}]$ such that $\gcd(a,c)$, $\gcd(a,a+b)$, and $\gcd(a,c+b)$ are all small, where $r'_a(x)$ and $r_c'(x)$ are again almost-invariant under shifts by multiples of $a$ and $c$, respectively, and are of the form $r'_a(x)=\sum_{w\in[N^{1/2}]}f(x+aw)l_{a+b}(x+aw).$ From this, we deduce largeness of (a weighted version of)
\begin{align*}
\sum_x\sum_{\substack{w_1,w_2,w_3,h_1,\dots,h_8\in[N^{1/2}]}}[&(fl_{a+b})(x+ah_1)(fl_{a+b})(x+cw_3+ah_2) \\
&(fl_{a+b})(x+(c+b)w_2+ah_3)(fl_{a+b})(x+(c+b)w_2+cw_3+ah_4)\\
&(fl_{a+b})(x+(a+b)w_1+ah_5)(fl_{a+b})(x+(a+b)w_1+cw_3+ah_6) \\
&(fl_{a+b})(x+(a+b)w_1+(c+b)w_2+ah_7)\\
&(fl_{a+b})(x+(a+b)w_1+(c+b)w_2+cw_3+ah_8)].
\end{align*}
Leveraging the fact that $\gcd(a,c)$, $\gcd(a,a+b)$, and $\gcd(a,c+b)$ are all small, we then bound the above in terms of the $U^3$-norm of $(fl_{a+b})(x)$ using Fourier analysis and the Gowers--Cauchy--Schwarz inequality. Taking advantage of the almost-invariance of $l_{a+b}$ under shifts by multiples of $a+b$, one can then apply the Cauchy--Schwarz inequality and argue in the same manner used to handle~\eqref{eq3.6} to deduce a bound in terms of $\|f\|_{U^4}$.

Putting everything together proves the following theorem, which we prove a more general version of as Theorem~\ref{thm5.2}.
\begin{theorem}\label{thm3.3}
Let $f_0,f_1,f_2:\Z\to\C$ be $1$-bounded functions supported in the interval $[N]$ and $\delta>0$. Suppose that
\[
|\Lambda(f_0,f_1,f_2)|\geq\delta N^{3/2}
\]
and $N\gg\delta^{-O(1)}$. Then
\[
\|f_2\|_{U^5}\gg\delta^{O(1)}N^6.
\]
\end{theorem}

\subsection{Degree lowering}\label{ss3.3}

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~\cite{Pe2} 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~\cite{Pe2} and here, does not require the $U^s$-inverse theorem for any $s\geq 3$. It instead uses Fourier analysis the place of these inverse theorems, as we will illustrate at the end of this subsection.

As was mentioned in the Introduction, adapting the degree lowering argument of~\cite{Pe2} 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):=\E_{y\in[N^{1/2}]}f_0(x-y^2)f_1(x+y-y^2).
\]

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 begin by decomposing the function $f_2$ into three parts using what is essentially Proposition~2.6 of~\cite{Pe2}, which is based on Gowers's Hahn--Banach decomposition method~\cite{Go4}. This yields
\[
f_2=g_{str}+g_{sml}+g_{unf},
\]
where $g_{str}$ has $U^5$-dual norm not too large, $g_{sml}$ has small $\ell^1$-norm, and $g_{unf}$ has bounded $L^\infty$-norm and small $U^5$-norm. Theorem~\ref{thm3.3} tells us that $g_{unf}$ makes negligible contribution to our counting operator $\Lambda(f_0,f_1,f_2)$, and a simple application of the triangle inequality shows that the same is true for $g_{sml}$. Thus, we can disregard the contributions of $g_{unf}$ and $g_{sml}$ and conclude that if $|\Lambda(f_0,f_1,f_2)|\geq\delta N^{3/2}$, then
\[
|\Lambda(f_0,f_1,g_{str})|\gg\delta^{O(1)}N^{3/2}.
\]
We can rewrite $\Lambda(f_0,f_1,g_{str})$ as $N^{1/2}$ times the inner product of $F$ and $g_{str}$,
\[
\Lambda(f_0,f_1,g_{str})=N^{1/2}\sum_{x}F(x)g_{str}(x),
\]
and use the defining property of the $U^5$-dual norm to conclude that $\|F\|_{U^5}^{2^5}\gg\delta^{O(1)}N^6$.

To finish this section, We will sketch the degree lowering argument for the non-linear Roth configuration in the $U^3$-control $\implies$ $U^2$-control case, starting from the assumption that
\[
\|F\|_{U^3}^8\geq\delta N^4.
\]
Using the fact that $\|F\|_{U^3}^8=\sum_h\|\Delta_hF\|_{U^2}^4$ and applying the $U^2$-inverse theorem, we deduce the existence of a function $\phi:\Z\to\T$ such that, for at least $\gg\delta N$ choices of differencing parameter $h$, we have
\begin{equation}\label{eq3.11}
\left|\sum_{x\in[N]}\Delta_hF(x)e(\phi(h)x)\right|\gg\delta N,
\end{equation}
so that by positivity,
\[
\sum_{h}\left|\sum_{x}\Delta_hF(x)e(\phi(h)x)\right|^2\gg\delta^{2}N^3.
\]

Note that if we could replace the function $\phi(h)$ by a constant $\beta\in\T$ not depending on $h$ in the above inequality (possibly worsening the exponent of $\delta$), then we could easily deduce largeness of $\|F\|_{U^2}$. Indeed, this would give
\[
\sum_x\sum_{h,h'}F(x)\overline{F(x+h)F(x+h')}F(x+h+h')e(-\beta h')\gg\delta^{O(1)}N^3,
\]
so that, after applying the Cauchy--Schwarz inequality in the $x$ and $h'$ variables, we deduce that $\|F\|_{U^2}^4\gg\delta^{O(1)}N^3$. It thus remains to show that such a $\beta$ exists.

By using the Cauchy--Schwarz inequality (as is done in greater generality in the proof of Lemma~\ref{lem6.3}), one can show that
\[
\left|\sum_x\sum_{y\in[N^{1/2}]}\Delta_{h-h'}f_0(x)\Delta_{h-h'}f_1(x+y)e([\phi(h)-\phi(h')][x+y^2])\right|\gg \delta^{O(1)}N^{3/2}
\]
for many pairs $(h,h')$ for which~\eqref{eq3.11} holds for both $h$ and $h'$. Using two applications of the Cauchy--Schwarz inequality, we can remove the weights $\Delta_{h-h'}f_0$ and $\Delta_{h-h'}f_1$ from the above inequality and deduce that the exponential sum
\[
\sum_{m\in[N^{1/2}]}\left|\sum_{\ell\in[N^{1/2}]}e(2\beta m\ell)\right|^2
\]
is large, from which we conclude that $\phi(h)-\phi(h')$ is major arc. There are very few major arcs, so the pigeonhole principle shows that there exists a $\beta_0\in\T$ such that $\phi(h)-\phi(h')$ is very close to $\beta_0$ for many $h,h'\in(-N,N)$ that also satisfy~\eqref{eq3.11}. Now, applying the pigeonhole principle again to fix $h'$, we see that we can take $\beta=\beta_0+\phi(h')$.

\section{Control by an average of Gowers box norms}\label{sec4}
In this section, we show that the weighted count of configurations $x,x+y,x+qy^2$ is controlled by an average of certain normalized Gowers box norms. To do this, we first define, for $q\in\N$ and $f_0,f_1,f_2:\Z\to\C$, the following counting operator
\begin{equation}\label{eq4.1}
\Lambda_q(f_0,f_1,f_2):=\sum_x\sum_{y\in[(N/q)^{1/2}]}f_0(x)f_1(x+y)f_2(x+qy^2).
\end{equation}
We write $\Lambda_q(f)$ for $\Lambda_q(f_0,f_1,f_2)$ when the $f_i$ are all equal to the same function $f$.
\begin{lemma}\label{lem4.1}
There exists an absolute constant $C>0$ such that the following holds. Let $f_0,f_1,f_2:\Z\to\C$ be $1$-bounded functions supported in the interval $[N]$, $q$ be a positive integer, and $\delta_1,\delta_2,\delta_3>0$. Set $M:=(N/q)^{1/2}$, and suppose that
\begin{equation}\label{eq4.2}
\left|\Lambda_q(f_0,f_1,f_2)\right|\geq \delta_1 NM.
\end{equation}
Then, if $0<\delta_2<C\delta_1^4$ and $0<\delta_3<C\delta_1^{32}$, we have
\[
\E_{a,b\in[\delta_2M]}\sum_{x,h_1,h_2,h_3}\mu_{\delta_3,M}(h_1)\mu_{\delta_3,M}(h_2)\mu_{\delta_3,M}(h_3)\Delta_{2q(a+b)h_1,2qbh_2,2qah_3}f_2(x)\gg\delta_1^{32}NM^3,
\]
provided $N\geq \f{1}{C}q\delta_2^{-2}\delta_1^{-64}$.
\end{lemma}

We prove Lemma~\ref{lem4.1} by using repeated applications of the Cauchy--Schwarz and van der Corput inequalities to control $\Lambda_q(f_0,f_1,f_2)$ by an average of weighted counts over varying linear progressions, and then bounding each of these weighted counts by a normalized Gowers box norm using three more applications of the Cauchy--Schwarz and van der Corput inequalities. Before beginning the proof, we recall van der Corput's inequality (see, for example, Section 2.1 of~\cite{M}).
\begin{lemma}[van der Corput's inequality]\label{lem4.2}
Let $g:\Z\to\C$ and $0<H<M$. Then we have the estimate
\[
\left|\sum_{y\in[M]}g(y)\right|^2\leq\f{M+H}{H^2}\sum_hr_{[H]}(h)\sum_{y\in [M]\cap([M]-h)}g(y+h)\overline{g(y)},
\]
where $r_{[H]}(h)$ denotes the number of pairs $(h_1,h_2)\in [H]^2$ such that $h_1-h_2=h$.
\end{lemma}
Now we can prove Lemma~\ref{lem4.1}.
\begin{proof}[Proof of Lemma~\ref{lem4.1}]
Applying the Cauchy--Schwarz inequality in the $x$ variable to the left-hand side of~\eqref{eq4.2} yields the bound
\[
\sum_x\left|\sum_{y\in[M]}f_1(x+y)f_2(x+qy^2)\right|^2\geq \delta_1^2 NM^2,
\]
and using van der Corput's inequality with $H=\delta_2 M$ and $g(y)=f_1(x+y)f_2(x+qy^2)$ bounds the left-hand side of the above by
\[
\ll\left|\sum_{x,a}\mu_{\delta_2,M}(a)\sum_{y\in[M]\cap([M]-a)}f_1(x+y)f_2(x+qy^2)\overline{f_1(x+y+a)f_2(x+q(y+a)^2)}\right|,
\]
since $\f{M+H}{H^2}\ll \f{1}{\delta_2^2M}$. Note that $\mu_{\delta_2,M}$ is supported on $(-\delta_2M,\delta_2 M)$, so we may extend the sum over $y\in[M]\cap([M]-a)$ to a sum over $y\in[M]$ at the cost of an error of size
\[
\ll \delta_2 M\sum_{x,a}\mu_{\delta_2,M}(a)=\delta_2NM^2.
\]
Thus,
\[
\left|\sum_{x,a}\mu_{\delta_2,M}(a)\sum_{y\in[M]}f_1(x+y)f_2(x+qy^2)\overline{f_1(x+y+a)f_2(x+q(y+a)^2)}\right|\gg\delta_1^2 NM^2
\]
by the bound $\delta_2<C\delta_1^4$, taking the $C$ in the statement of the lemma sufficiently small. Making the change of variables $x\mapsto x-y$, this means that
\[
\left|\sum_{x,a}\mu_{\delta_2,M}(a)\Delta_af_1(x)\sum_{y\in[M]}f_2(x+qy^2-y)\overline{f_2(x+q(y+a)^2-y)}\right|\gg\delta_1^2 NM^2.
\]

We next apply the Cauchy--Schwarz inequality in the $x$ and $a$ variables to the left-hand side above to deduce that
\[
\|\mu_{\delta_2,M}\|_{\ell^2}^2\left(\sum_{x}\sum_{|a|<\delta_2M}\left|\sum_{y\in[M]}f_2(x+qy^2-y)\overline{f_2(x+q(y+a)^2-y)}\right|^2\right)\gg\delta_1^4 N M^4.
\]
Note that $\|\mu_{\delta_2,M}\|_{\ell^2}^2\leq H^3/(\delta_2^4M^2)=M/\delta_2$, so that by dividing both sides of the above inequality by $M^2$ and using van der Corput's inequality with $H=\delta_2 M$ again and arguing in the same manner as before, we get
\begin{align*}
\delta_1^4 NM^2\ll\big|\E_{|a|<\delta_2 M}\sum_{x,b}\mu_{\delta_2,M}(b)f_2(x)\sum_{y\in[M]}[&\overline{f_2(x+q[2ay+a^2])}\overline{f_2(x+q[2by+b^2]-b)}\\
&f_2(x+q[2(a+b)y+(a+b)^2]-b)]\big|,
\end{align*}
after making the change of variables $x\mapsto x-qy^2+y$.

Applying the Cauchy--Schwarz inequality again in the $x,a,$ and $b$ variables, using van der Corput's inequality with $H=\delta_3M$, and making the change of variables $x\mapsto x-q[2ay+a^2]+qa^2+b$, we similarly deduce that
\begin{align*}
\delta_1^8 NM^2\ll\big|\E_{|a|,|b|<\delta_2M}\sum_{x,h_1}\mu_{\delta_3,M}(h_1)\sum_{y\in[M]}[&\overline{\Delta_{2qah_1}f_2(x+qa^2+b)}\overline{f_2(x+q[2(b-a)y+b^2])}\\
&f_2(x+q[2by+(a+b)^2])\\
&f_2(x+q[2(b-a)y+2bh_1+b^2])\\
&\overline{f_2(x+q[2by+2(a+b)h_1+(a+b)^2])}]\big|.
\end{align*}

Now, before applying the Cauchy--Schwarz inequality yet again in the $x,a,b,$ and $h_1$ variables, we split $\mu_{\delta_3,M}(h_1)$ by writing $\mu_{\delta_3,M}(h_1)=\sqrt{\mu_{\delta_3,M}(h_1)}^2$ and use the fact that $\|\mu_{\delta_3,M}(h_1)\|_{\ell^1}=M$ to deduce that
\begin{align*}
\delta_1^{16} NM^3\ll\big|\E_{|a|,|b|<\delta_2M}\sum_{x,h_1,h_2}\mu_{\delta_3,M}(h_1)\mu_{\delta_3,M}(h_2)\sum_{y\in[M]}[&\overline{\Delta_{2qbh_1,2q(b-a)h_2}f_2(x+q[b^2-(a+b)^2])}\\
&\Delta_{2q(a+b)h_1,2qbh_2}f_2(x+2qay)]\big|,
\end{align*}
assuming $C>0$ is small enough, by using van der Corput's inequality with $H=\delta_3M$ and making the change of variables $x\mapsto x-q[2(b-a)y-(a+b)^2]$.

We apply the Cauchy--Schwarz inequality once more in the $x,a,b,h_1,$ and $h_2$ variables and then van der Corput's inequality with $H=\delta_3M$ in the same manner as above and make the change of variables $x\mapsto x-2qay$ to deduce that
\[
\delta_1^{32}NM^3\ll\E_{|a|,|b|<\delta_2M}\sum_{x,h_1,h_2,h_3}\mu_{\delta_3,M}(h_1)\mu_{\delta_3,M}(h_2)\mu_{\delta_3,M}(h_3)\Delta_{2q(a+b)h_1,2qbh_2,2qah_3}f_2(x),
\]
assuming $C>0$ is small enough.

Finally, observe that the expression inside the average above is symmetric under the transformations $a \mapsto -a$ and $b \mapsto -b$ since $\mu_{\delta_3,M}(h)$ is symmetric under $h\mapsto -h$. In addition, the contribution when $a=0$ or $b=0$ is $\ll NM^2/\delta_2$. Thus, we can restrict our sum to $1\leq a, b\leq \delta_2M$, at the cost of a factor of $8$, provided that $N\geq \f{1}{C}q\delta_2^{-2}\delta_1^{-64}$ for $C$ sufficiently small.
\end{proof}

\section{Quantitative concatenation}\label{sec5}

The goal of this section is to control the average of normalized Gowers box norms appearing in the conclusion of Lemma~\ref{lem4.1} by an average of $U^5$-norms localized to progressions modulo $q$:
\begin{theorem}\label{thm5.1}
There exists an absolute constant $C>0$ such that the following holds. Let $f:\Z\to\C$ be a $1$-bounded function supported in the interval $[N]$, $q$ be a positive integer, and $\delta_1,\delta_2,\delta_3>0$. Set $M:=(N/q)^{1/2}$, and suppose that
\[
\E_{a,b\in[\delta_1 M]}\sum_{x,h_1,h_2,h_3}\mu_{\delta_2,M}(h_1)\mu_{\delta_2,M}(h_2)\mu_{\delta_2,M}(h_3)\Delta_{2q(a+b)h_1,2qbh_2,2qah_3}f(x)\geq\delta_3NM^3.
\]
Then, if $0<\delta_2<C\delta_1^3\delta_3^4$, we have
\[
\E_{u\in[q]}\|f\|_{U^5(u+q\Z)}^{2^5}\gg(\delta_2\delta_3)^{2^{25}}(N/q)^6.
\]
\end{theorem}

Combining this with Lemma~\ref{lem4.1}, we will be able to conclude that the count of configurations $x,x+y,x+qy^2$ in subsets of $[N]$ is controlled by an average of $U^5(u+q\Z)$-norms. Precisely, these two results yield the following theorem.
\begin{theorem}[$U^5$-control]\label{thm5.2}
Let $f_0,f_1,f_2:\Z\to\C$ be $1$-bounded functions supported in the interval $[N]$, $q$ be a positive integer, and $\delta>0$. Set $M:=(N/q)^{1/2}$, and suppose that
\[
|\Lambda_q(f_0,f_1,f_2)|\geq\delta NM.
\]
Then we have
\[
\E_{u\in[q]}\|f_2\|_{U^5(u+q\Z)}^{2^5}\gg\delta^{2^{33}}(N/q)^6,
\]
provided $N\gg q\delta^{-72}$.
\end{theorem}
As mentioned in Section~\ref{sec3}, the proof of Theorem~\ref{thm5.1} proceeds by studying, for $M:=(N/q)^{1/2}$ and each fixed $b\in[\delta_1M]$, the quantity
\begin{equation}\label{eq5.1}
\|f\|_{b}^4:=\E_{a\in[\delta_1 M]}\sum_{x,h_1,h_2}\mu_{\delta_2,M}(h_1)\mu_{\delta_2,M}(h_2)\Delta_{2q(a+b)h_1,2qah_2}f(x)
\end{equation}
when $f:\Z\to\C$ is $1$-bounded and supported on the interval $[N]$. Most pairs $a,b\in[\delta_1 M]$ have small greatest common divisor, and thus the Gowers box norm appearing inside of the average over $a\in[\delta_1 M]$ in~\eqref{eq5.1} can be analyzed in a similar manner to the two-dimensional box norm defined on functions on product sets. We carry this out in Subsection~\ref{ss5.1} by proving an inverse theorem for such Gowers box norms. Then, in Subsection~\ref{ss5.2}, which is the heart of this section, we use this inverse theorem to show that the norm $\|\cdot\|_b$ can be controlled by an average of $U^4$-norms localized to progressions modulo $q$ on average over $b\in[\delta_1 M]$. Finally, in Subsection~\ref{ss5.3}, we combine this fact with one more application of the Cauchy--Schwarz and van der Corput inequalities to prove Theorem~\ref{thm5.1}, and then deduce Theorem~\ref{thm5.2}.

\subsection{An inverse theorem for certain Gowers box norms}\label{ss5.1}
The majority of the proof of the following lemma is concerned with controlling the Gowers box norm by a genuine two-dimensional box norm inner product.

\begin{lemma}[Arithmetic box norm inverse theorem]\label{lem5.3}
Let $\delta_1,\delta_2,\delta_3>0$ and suppose that $c,d\in\N$ with $\gcd(c,d)=1$ and $c>\delta_1M$. Let $f:\Z\to\C$ be a $1$-bounded function supported on the interval $[N]$ satisfying
\begin{equation}\label{eq5.2}
\sum_{x,h_1,h_2}\mu_{\delta_2,M}(h_1)\mu_{\delta_2,M}(h_2)\Delta_{ch_1,dh_2}f(x)\geq\delta_3 NM^2.
\end{equation}
Then there exist $1$-bounded  functions $l,r:\Z\to\C$ such that
\[
\left|\sum_xf(x)l(x)r(x)\right|\geq(\delta_2^2\delta_3-O(\delta_2^3/\delta_1))M^2,
\]
$r(x)=r(x+cy)$ for all $x,y\in\Z$, and
\[
\#\{x\in[N]:l(x)\neq l(x+dz)\text{ for some }z\in[\ve M]\}\ll \f{\ve}{\delta_1}N
\]
for every $\ve>0$.
\end{lemma}
\begin{proof}
First note that, since $\gcd(c,d)=1$, every integer $x$ can be uniquely represented in the form
\[
x=cy+dz\qquad (y\in\Z,z\in[c]).
\]
We therefore define $F:\Z\times[c]\to\C$ by $F(y,z):=f(cy+dz)$.

Unraveling the definition of $\mu_{\delta_2,M}$, we write the left-hand side of~\eqref{eq5.2} as $M^2$ times the quantity
\[
\sum_{x}\E_{h_1,h_1',h_2,h_2'\in[\delta_2 M]}f(x)\overline{f(x+c(h_1'-h_1))f(x+d(h_2'-h_2))}f(x+c(h_1'-h_1)+d(h_2'-h_2)),
\]
which, making the change of variables $x\mapsto x+ch_1+dh_2$ and then replacing the sum over $x\in\Z$ with a sum over $y\in\Z$ and $z\in[c]$, equals
\begin{align*}
\E_{h_1,h_1',h_2,h_2'\in[\delta_2 M]}\sum_{\substack{z\in[c]}}\sum_y[&f(c(y+h_1)+d(z+h_2))\overline{f(c(y+h_1')+d(z+h_2))} \\
&\overline{f(c(y+h_1)+d(z+h_2'))}f(c(y+h_1')+d(z+h_2'))].
\end{align*}

Now, for each fixed pair of $h_2,h_2'\in[\delta_2 M]$, the contribution of all $z\in[c]$ such that at least one of $z+h_2$ or $z+h_2'$ is not in $[c]$ to the interior sum in the above quantity is
\begin{equation}\label{eq5.3}
\ll\sum_{c-\delta_2 M<z\leq c}\sum_y1_{[N]}(c(y+h_1)+d(z+h_2)),
\end{equation}
since $f$ is $1$-bounded and supported on the interval $[N]$. Making the change of variables $y\mapsto y-h_1$, we see that for each fixed $z$ and $h_2$, the inner sum in~\eqref{eq5.3} counts the number of $n\in[N]$ that are congruent to $d(z+h_2)$ modulo $c$. This quantity is bounded above by $\lceil N/c\rceil$. The number of congruence classes modulo $c$ covered by $d(z+h_2)$ is certainly bounded above by $\delta_2 M$, since this is the number of possible choices for $z$. Thus,~\eqref{eq5.3} is $\ll \delta_2 NM/c\ll \delta_2/\delta_1 N$, since $c>\delta_1 M$ by hypothesis.

By a similar argument, the contribution of $z\in\Z\sm[c]$ such that $z+h_2$ and $z+h_2'$ lie in $[c]$ for some $h_2,h_2'\in[\delta_2M]$ to the quantity
\begin{align*}
\E_{h_1,h_1',h_2,h_2'\in[\delta_2 M]}\sum_{\substack{y,z\\ z+h_2,z+h_2'\in[c]}}[&f(c(y+h_1)+d(z+h_2))\overline{f(c(y+h_1')+d(z+h_2))} \\
&\overline{f(c(y+h_1)+d(z+h_2'))}f(c(y+h_1')+d(z+h_2'))]
\end{align*}
is also $\ll\delta_2/\delta_1N$. As a consequence, we get
\[
(\delta_3-O(\delta_2/\delta_1))NM^2\leq\sum_{\substack{y,y' \\ z,z'\in[c]}}F(y,z)\overline{F(y',z)F(y,z')}F(y',z')\mu_{\delta_2,M}(y'-y)\mu_{\delta_2,M}(z'-z).
\]

By Fourier inversion, we have
\begin{align*}
&\sum_{\substack{y,y' \\ z,z'\in[c]}}F(y,z)\overline{F(y',z)F(y,z')}F(y',z')\mu_{\delta_2,M}(y'-y)\mu_{\delta_2,M}(z'-z) \\
&=\int_{\T^2}\sum_{\substack{y,y' \\ z,z'\in[c]}}F(y,z)\overline{F(y',z)F(y,z')}F(y',z')\widehat{\mu_{\delta_2,M}}(\gamma)\widehat{\mu_{\delta_2,M}}(\gamma')e(\gamma(y'-y)+\gamma'(z'-z))d\gamma d\gamma' \\
&\leq\left(\int_{\T}|\widehat{\mu_{\delta_2,M}}(\gamma)|d\gamma\right)^2\sup_{\gamma,\gamma'\in\T}\left|\sum_{\substack{y,y' \\ z,z'\in[c]}}F(y,z)F_2(y',z)F_3(y,z')F_4(y',z')\right|,
\end{align*}
where $F_2(y',z):=\overline{F(y',z)}e(-\gamma' z)$, $F_3(y,z'):=\overline{F(y,z')}e(-\gamma y)$, and $F_4(y',z'):=F(y',z')e(\gamma y'+\gamma'z')$.

We observe that $\widehat{\mu_{\delta_2,M}}(\gamma)=|\widehat{1_{[\delta_2 M]}}(\gamma)|^2/(\delta_2^2 M)$, which implies that $\int_\T|\widehat{\mu_{\delta_2,M}}(\gamma)|d\gamma=1/\delta_2$. Hence,
\begin{equation}\label{eq5.4}
(\delta_2^2\delta_3-O(\delta_2^3/\delta_1))NM^2\leq \left|\sum_{\substack{y,y' \\ z,z'\in[c]}}F(y,z)F_2(y',z)F_3(y,z')F_4(y',z')\right|
\end{equation}
for $1$-bounded functions $F_i:\Z\times[c]\to\C$ of the form $F_i(y,z)=f(cy+dz)e(\gamma_{1,i}y+\gamma_{2,i}z)$. Since $f$ is supported on $[N]$, there are exactly $N$ pairs $(y',z')\in\Z\times[c]$ for which $F(y',z')\neq 0$. Thus, by pigeonholing in $y'$ and $z'$ in~\eqref{eq5.4} and setting $L(y):=F_3(y,z')$ and $R(z):=F_2(y',z)F_4(y',z')$, we get that
\[
\left|\sum_{y}\sum_{z\in[c]}F(y,z)L(y)R(z)\right|\geq (\delta_2^2\delta_3-O(\delta_2^3/\delta_1))M^2.
\]

Now, for each $x\in\Z$, define $g(x)\in\Z$ and $h(x)\in[c]$ by $x=cg(x)+dh(x)$, and set $l(x):=L\circ g$ and $r(x):=R\circ h$. Then
\[
\left|\sum_xf(x)l(x)r(x)\right|\geq(\delta_2^2\delta_3-O(\delta_2^3/\delta_1))M^2.
\]

It remains to check the invariance properties of $l$ and $r$. To see that $r(x)=r(x+cy)$ for all $x,y\in\Z$, just note that $h(x)=h(x+cy)$ for every $x,y\in\Z$. To see that, for most $x\in[N]$, we have $l(x)=l(x+dz)$ for all $z\in[\ve M]$, note that $g(x)=g(x+dz)$ whenever $h(x)<c-\ve M$. But for $h(x)<c-\ve M$ to hold, $x$ must lie in one of $\ve M$ congruence classes modulo $c$. This implies that
\[
\#\{x\in[N]:l(x)\neq l(x+dz)\text{ for some }z\in[\ve M]\}\ll \f{\ve MN}{c}<\f{\ve}{\delta_1}N
\]
for every $\ve>0$.
\end{proof}
Lemma~\ref{lem5.3} yields a result in the $\gcd(c,d)>1$ situation, which we easily deduce by passing to subprogressions modulo $\gcd(c,d)$ and applying the lemma.
\begin{corollary}\label{cor5.4}
There exists an absolute constant $C>0$ such that the following holds. Let $\delta_1,\delta_2,\delta_3>0$ and $m\in\N$ and suppose that $c,d\in\N$ with $m:=\gcd(c,d)$ and $c>\delta_1mM$. Let $f:\Z\to\C$ be a $1$-bounded function supported on the interval $[N]$ and satisfying
\[
\sum_{x,h_1,h_2}\mu_{\delta_2,M}(h_1)\mu_{\delta_2,M}(h_2)\Delta_{ch_1,dh_2}f(x)\geq\delta_3 NM^2.
\]
Then, if $0<\delta_2<C\delta_1\delta_3/m$, there exist $1$-bounded functions $l,r:\Z\to\C$ such that
\[
\left|\sum_xf(x)l(x)r(x)\right|\gg\delta_2^2\delta_3 M^2,
\]
$r(x)=r(x+cy)$ for all $x,y\in\Z$, and
\[
\#\{x\in[N]:l(x)\neq l(x+dz)\text{ for some }z\in[\ve M]\}\ll \f{\ve}{\delta_1}N
\]
for every $\ve>0$.
\end{corollary}
\begin{proof}
Define, for each $k=0,\dots,m-1$, a $1$-bounded function $f_k:\Z\to\C$ by $f_k(x):=f(mx-k)$. Then each $f_k$ is supported on $[\lceil N/m\rceil]$ and there exist $\delta_{3,0},\dots,\delta_{3,m-1}\geq 0$ satisfying $\delta_{3,0}+\dots+\delta_{3,m-1}=\delta_3$ such that
\[
\sum_{x,h_1,h_2}\mu_{\delta_2,M}(h_1)\mu_{\delta_2,M}(h_2)\Delta_{\f{c}{m}h_1,\f{d}{m}h_2}f_k(x)\geq\delta_{3,k} \f{NM^2}{m}.
\]
Note that $\gcd(c/m,d/m)=1$ and $c/m>\delta_1M$, so by Lemma~\ref{lem5.3}, there exist $l_k,r_k:\Z\to\C$ such that
\[
\sum_xf_k(x)l_k(x)r_k(x)\geq (\delta_2^2\delta_{3,k}-O(\delta_2^3/\delta_1))M^2,
\]
$r_k(x)=r_k(x+cy/m)$ for all $x,y\in\Z$, and
\[
\#\{x\in[\lceil N/m\rceil]:l_k(x)\neq l_k(x+dz/m)\text{ for some }z\in[\ve M]\}\ll\f{\ve}{\delta_1}\f{N}{m}.
\]
Defining $r(mx-k):=r_{k}(x)$ and $l(mx-k):=l_{k}(x)$ for $k=0,\dots,m-1$, we thus get that
\[
\sum_xf(x)l(x)r(x)\geq (\delta_2^2\delta_{3}-O(\delta_2^3m/\delta_1))M^2,
\]
$r(x)=r(x+cy)$ for all $x,y\in\Z$, and
\[
\#\{x\in[N]:l(x)\neq l(x+dz)\text{ for some }z\in[\ve M]\}\ll\f{\ve}{\delta_1}N.
\]
Assuming that $C>0$ is small enough yields
\[
\sum_xf(x)l(x)r(x)\gg\delta_2^2\delta_{3}M^2.
\]
\end{proof}

\subsection{$U^4$-control on average}\label{ss5.2}
In this subsection, we show that, on average over $b$, the norm $\|\cdot\|_b$ is controlled by an average of $U^4$-norms localized to arithmetic progressions modulo $q$. This will be an immediate consequence of the following lemma.
\begin{lemma}\label{lem5.5}
There exists an absolute constant $C>0$ such that the following holds. Set $M:=N^{1/2}$ and let $\delta_1,\delta_2,\delta_3,\delta_4>0$. For all but $O(\delta_1 \delta_2M)$ of the $b\in [\delta_2 M]$, if $f:\Z\to\C$ is a $1$-bounded function supported in the interval $[N]$ satisfying
\begin{equation}\label{eq5.?}
\E_{a\in[\delta_2M]}\sum_{x,h_1,h_2}\mu_{\delta_3,M}(h_1)\mu_{\delta_3,M}(h_2)\Delta_{2(a+b)h_1,2ah_2}f(x)\geq\delta_4 NM^2,
\end{equation}
then
\[
\|f\|_{U^4}^{2^4}\gg(\delta_3\delta_4)^{2^{20}}N^5,
\]
provided $0<\delta_1/\delta_2<C\delta_4$ and $0<\delta_3<C\delta_1^3\delta_4$.
\end{lemma}
Note that the only differences between~\eqref{eq5.?} and the definition of $\|\cdot\|_b^4$ in~\eqref{eq5.1} (besides the different indices for various $\delta_i$'s) are the presence of $q$ in the delta operator $\Delta_{2q(a+b)h_1,2qah_2}$ applied to $f$ in~\eqref{eq5.1} and the lack of one in the delta operator $\Delta_{2(a+b)h_1,2ah_2}$ applied to $f$ in~\eqref{eq5.?} and that $M=(N/q)^{1/2}$ in~\eqref{eq5.1} and $M=N^{1/2}$ in~\eqref{eq5.?}. We thus deduce the following corollary from Lemma~\ref{lem5.5} by splitting the domain of $f$ up modulo $q$ and choosing $\delta_1$ appropriately in Lemma~\ref{lem5.5}.
\begin{corollary}\label{cor5.6}
There exists an absolute constant $C>0$ such that the following holds. Set $M:=(N/q)^{1/2}$ and let $\delta_2,\delta_3,\delta_4>0$, $f_b:\Z\to\C$ be $1$-bounded functions supported in the interval $[N]$ for each $b\in[\delta_2 M]$, and $q$ be a positive integer. If
\[
\E_{b\in[\delta_2 M]}\|f_b\|_{b}^4\geq \delta_4 NM^2
\]
for $0<\delta_3<C\delta_2^3\delta_4^4$, then we have
\[
\E_{u\in[q]}\E_{b\in[\delta_2 M]}\|f_b\|_{U^4(u+q\Z)}^{2^4}\gg (\delta_3\delta_4)^{2^{21}}(N/q)^5.
\]
\end{corollary}
In this Corollary, $\delta_2$ and $\delta_3$ play the role of $\delta_1$ and $\delta_2$, respectively, in the definition~\eqref{eq5.1} of $\|\cdot\|_b$.
\begin{proof}[Proof of Corollary~\ref{cor5.6} assuming Lemma~\ref{lem5.5}]
For any function $g:\Z\to\C$ and $h\in\Z$, let $T_hg:\Z\to\C$ denote the function $T_hg(x):=g(x+h)$. We split $\Z$ up into arithmetic progressions modulo $q$ and note that, since
\[
\left|\E_{a,b\in[\delta_2M]}\sum_{x,h_1,h_2}\mu_{\delta_3,M}(h_1)\mu_{\delta_3,M}(h_2)\Delta_{2(a+b)h_1,2ah_2}T_uf_b(qx)\right|\leq\f{N}{q}M^2
\]
for all $u\in[q]$, for at least a $\gg\delta_4$-proportion of $u\in[q]$ we must have
\[
\E_{a,b\in[\delta_2M]}\sum_{x,h_1,h_2}\mu_{\delta_3,M}(h_1)\mu_{\delta_3,M}(h_2)\Delta_{2(a+b)h_1,2ah_2}T_uf_b(qx)\gg\delta_4\f{N}{q}M^2.
\]
For the same reason, we also have that
\[
\E_{a\in[\delta_2M]}\sum_{x,h_1,h_2}\mu_{\delta_3,M}(h_1)\mu_{\delta_3,M}(h_2)\Delta_{2(a+b)h_1,2ah_2}T_uf_b(qx)\gg\delta_4\f{N}{q}M^2
\]
holds for at least a $\gg\delta_4$-proportion of the $b\in[\delta_2 M]$ for such $u$. Applying Lemma~\ref{lem5.5} with $N/q$ in place of $N$, $T_uf_b(q\cdot)$ in place of $f$, and $\delta_1=\f{C'}{2}\delta_2\delta_4$ for $C'>0$ sufficiently small, we get that
\[
\|f_b\|_{U^4(u+q\Z)}^{2^4}\gg(\delta_3\delta_4)^{2^{20}}(N/q)^5
\]
for at least a $\gg C'\delta_4^2$-proportion of $b\in[\delta_2 M]$ and $u\in[q]$. We thus deduce by positivity that
\[
\E_{u\in[q]}\E_{b\in[\delta_2 M]}\|f_b\|_{U^4(u+q\Z)}^{2^4}\gg(\delta_3\delta_4)^{2^{21}}(N/q)^5.
\]
\end{proof}
At the end of the above proof we used the very crude bound $2^{20}+2\leq 2^{21}$. This is the sort of estimate referred to in Remark~\ref{rmk1.2}, and there will be many more like it in the remainder of the paper.

Before proving Lemma~\ref{lem5.5}, we record two well-known lemmas for ease of exposition. The first is the fact that most pairs of integers have small greatest common divisor.
\begin{lemma}\label{lem5.7}
The proportion of integers $1\leq a,b\leq X$ with $\gcd(a,b)>Y$ is $\ll Y\1$.
\end{lemma}
\begin{proof}
Recall (see, for example, Chapter 3 of~\cite{A}) that the proportion of pairs $(a,b)$ of positive integers below $X$ such that $\gcd(a,b)\leq Y$ is asymptotically
\[
\sim\f{1}{\zeta(2)}\sum_{n=1}^Y\f{1}{n^2}.
\]
Thus, the proportion of pairs with $\gcd(a,b)>Y$ is $\ll Y\1$.
\end{proof}

The second is that a function of three variables that correlates with functions depending on only two of these variables has large three-dimensional box norm. The proof, which is standard, is just three applications of the Cauchy--Schwarz inequality.
\begin{lemma}\label{lem5.8}
Let $X_1,X_2,$ and $X_3,$ be finite sets and $f,g_1,g_2,g_3:X_1\times X_2\times X_3\to\C$ be $1$-bounded functions such that the value of $g_i(x_1,x_2,x_3)$ does not depend on $x_i$. If
\[
\left|\E_{\substack{x_i\in X_i \\ i=1,2,3}}f(x_1,x_2,x_3)\prod_{i=1}^3g_i(x_1,x_2,x_3)\right|\geq \delta,
\]
then
\[
\|f\|_{\square(X_1,X_2,X_3)}\geq\delta.
\]
\end{lemma}
\begin{proof}
Apply the Cauchy--Schwarz inequality three times: once in all but the $x_1$ variable, once in all but the $x_2$ variable, and once in all but the $x_3$ variable.
\end{proof}
Now we can prove Lemma~\ref{lem5.5}. For an outline of this argument, see Subsection~\ref{ss3.2} starting after Lemma~\ref{lem3.4}.
\begin{proof}[Proof of Lemma~\ref{lem5.5}]
Let $S$ denote the set of integers $b\in[\delta_2 M]$ such that $\gcd(a,b)\ll \delta_1\1$ for all but a proportion of $\delta_1$ of the integers $a\in[\delta_2 M]$. For fixed $b\in S$, let $U_{b}$ denote the set of all such $a\in[\delta_2 M]$ satisfying $\gcd(a,b)\ll\delta_1\1$ and also $a>\delta_1M$.

Let $b\in S$, and note that $[\delta_2 M]\sm S$ has size $O(\delta_1 \delta_2 M)$ by Lemma~\ref{lem5.7}. We restrict the average over $a\in[\delta_2 M]$ in~\eqref{eq5.?} to an average over $U_{b}$ so that we can apply Corollary~\ref{cor5.4}. By Lemma~\ref{lem5.7} again, we have $|U_{b}|\geq (1-O(\delta_1))\delta_2M-\delta_1M=(\delta_2-O(\delta_1))M$, so that
\begin{align*}
\E_{a\in U_{b}}\left|\sum_{x,h_1,h_2}\mu_{\delta_3,M}(h_1)\mu_{\delta_3,M}(h_2)\Delta_{(a+b)h_1,ah_2}f(x)\right| &\gg (\delta_4-O(\delta_1\delta_2\1))NM^2 \\
&\gg\delta_4 NM^2
\end{align*}
by the bound $\delta_1/\delta_2<C\delta_4$, assuming that $C>0$ is small enough.

Now, since $\left|\sum_{x,h_1,h_2}\mu_{\delta_3,M}(h_1)\mu_{\delta_3,M}(h_2)\Delta_{(a+b)h_1,ah_2}f(x)\right|\ll NM^2$ for all $a\in U_b$, there are $\gg\delta_4|U_b|$ many $a$'s in $U_b$ such that
\[
\left|\sum_{x,h_1,h_2}\mu_{\delta_3,M}(h_1)\mu_{\delta_3,M}(h_2)\Delta_{(a+b)h_1,ah_2}f(x)\right|\gg\delta_4NM^2.
\]
We have $m:=\gcd(a,a+b)=\gcd(a,b)\leq\delta_1\1$ and $a>\delta_1 M=\delta_1^2 mM$ by definition for these $a$'s, in addition to the inequality $0<\delta_3<C\delta_1^2\delta_4/\delta_1\1\leq C\delta_1^2\delta_4/m$. Thus, by taking $C$ sufficiently small, it follows from Corollary~\ref{cor5.4} (using $m,\delta_1^2,\delta_3,$ and $\delta_4$ in the roles of $m,\delta_1,\delta_2,$ and $\delta_3$ in the corollary, respectively) that there exist $1$-bounded functions $l_{a+b},r_a:\Z\to\C$ satisfying
\begin{align*}
\sum_xf(x)l_{a+b}(x)r_a(x)&\gg\delta_3^2\delta_4M^2,
\end{align*}
$r_a(x)=r_a(x+ay)$ for all $x,y\in\Z$, and
\[
\#\{x\in[N]:l_{a+b}(x)\neq l_{a+b}(x+(a+b)z)\text{ for some }z\in[\ve M]\}\ll \f{\ve}{\delta_1^2}N
\]
for every $\ve>0$. Note that, by replacing $l_{a+b}$ by $l_{a+b}1_{[N]}$, we may assume that $l_{a+b}$ is supported on $[N]$, since $f$ is. Set $r_a,l_{a+b}:\Z\to\C$ to be identically zero for all other $a$'s in $U_b$, so that
\[
\E_{a\in U_b}\sum_xf(x)l_{a+b}(x)r_a(x)\gg\delta_3^2\delta_4^2M^2.
\]

We now work on controlling the left-hand side of the above by $\|f\|_{U^4}$. To do this, we first insert extra averaging in $x$ by shifting by multiples of $a$ and using the invariance of $r_a$, so that
\[
\E_{a\in U_b}\sum_{x}\sum_{w\in[\delta_1M]}f(x+aw)l_{a+b}(x+aw)r_a(x)\gg\delta_1\delta_3^2\delta_4^2M^3.
\]
Applying the Cauchy--Schwarz inequality in the $a$ and $x$ variables, this implies that
\[
\E_{a\in U_b}\sum_{x}f(x)l_{a+b}(x)\left(\sum_{w,w'\in[\delta_1 M]}f(x+a(w-w'))l_{a+b}(x+a(w-w'))\right)\gg \delta_1^2\delta_3^4\delta_4^4M^4
\]
or, setting
\[
r'_a(x):=\sum_{w}\mu_{\delta_1,M}(w)f(x+aw)l_{a+b}(x+aw),
\]
that
\begin{equation}\label{eq5.5}
\E_{a\in U_b}\sum_{x}f(x)l_{a+b}(x)r'_a(x)\gg \delta_3^4\delta_4^4M^3.
\end{equation}
For future reference, note that $\|r_a'\|_{L^\infty}\leq M$ and $r_a'$ is supported in $[-N,2N]$, since $\mu_{\delta_1,M}$ is bounded by $\delta_1\1$ and supported in $[-\delta_1 M,\delta_1 M]$, $f$ is $1$-bounded and supported in $[N]$, and $a\leq \delta_2 M\leq M$.

We apply the Cauchy--Schwarz inequality again in the $x$ variable to~\eqref{eq5.5} to deduce that
\[
\E_{a,c\in U_b}\sum_{x}l_{a+b}(x)l_{c+b}(x)r'_a(x)r'_c(x)\gg \delta_3^8\delta_4^8M^4.
\]
Let $0<\delta_5<C'\delta_3^8\delta_4^8\delta_1^2$ for $C'>0$ sufficiently small. Inserting extra averaging in $x$ by shifting by multiples of $(a+b)$ gives
\[
\E_{a,c\in U_g}\sum_{\substack{x \\ w_1\in[\delta_5M]}}l_{a+b}(x+(a+b)w_1)l_{c+b}(x+(a+b)w_1)r'_a(x+(a+b)w_1)r'_c(x+(a+b)w_1)\gg \delta_3^8\delta_4^8\delta_5M^5.
\]
Recall that
\[
\#\{x\in[N]:l_{a+b}(x)\neq l_{a+b}(x+(a+b)z)\text{ for some }z\in[\delta_5 M]\}\ll \delta_5/\delta_1^2N,
\]
so
\[
\sum_{x}\sum_{w_1\in[\delta_5 M]}\left|l_{a+b}(x+(a+b)w_1)-l_{a+b}(x)\right|\ll \delta_{5}^2/\delta_1^2 M^3+\delta_2\delta_5^2M^3\ll\delta_5^2/\delta_1^2 M^3,
\]
because $a,b\leq \delta_2M$ and $l_{a+b}$ is $1$-bounded. Since $\|r_a'\|_{L^\infty},\|r_c'\|_{L^\infty}\leq M$ and $l_{c+b}$ is $1$-bounded, it thus follows that
\[
\E_{a,c\in U_b}\sum_{\substack{x \\ w_1\in[\delta_5M]}}l_{a+b}(x)l_{c+b}(x+(a+b)w_1)r'_a(x+(a+b)w_1)r'_c(x+(a+b)w_1)\gg \delta_3^8\delta_4^8\delta_5M^5.
\]
By a similar argument using the almost-invariance of $l_{c+b}$ under shifts by $(c+b)$, we have
\begin{align*}
\E_{a,c\in U_b}\sum_{\substack{x \\ w_1,w_2\in[\delta_5M]}}[&l_{a+b}(x+(c+b)w_2)r'_a(x+(a+b)w_1+(c+b)w_2)\\
&l_{c+b}(x+(a+b)w_1)r'_c(x+(a+b)w_1+(c+b)w_2)]\gg \delta_3^8\delta_4^8\delta_5^2M^6.
\end{align*}

Now, we insert extra averaging yet again by shifting by multiples of $c$, so that
\begin{align*}
\delta_3^8\delta_4^8\delta_5^3M^7\ll\E_{a,c\in U_b}\sum_{\substack{x \\ w_1,w_2,w_3\in[\delta_5M]}}[&l_{a+b}(x+(c+b)w_2+cw_3)r'_a(x+(a+b)w_1+(c+b)w_2+cw_3)\\
&l_{c+b}(x+(a+b)w_1+cw_3)r'_c(x+(a+b)w_1+(c+b)w_2+cw_3)].
\end{align*}
As a consequence,
\begin{align*}
\delta_3^8\delta_4^8\delta_5^3M^7\ll E+\E_{a,c\in U_b}\sum_{\substack{x \\ w_1,w_2,w_3\in[\delta_5 M]}}[&l_{a+b}(x+(c+b)w_2+cw_3)r'_a(x+(a+b)w_1+(c+b)w_2+cw_3)\\
&l_{c+b}(x+(a+b)w_1+cw_3)r'_c(x+(a+b)w_1+(c+b)w_2)],
\end{align*}
where
\[
E \ll \delta_5^{2}M^3\max_{a,c\in U_b}\sum_x\sum_{\substack{w_3\in[\delta_5M]}}\left|r'_c(x+cw_3)-r'_c(x)\right|,
\]
since $\|r_a'\|_{L^\infty}\leq M$.

Recalling the definition of $r_c'$ and using the fact that $f$ and $l_{c+b}$ are $1$-bounded and supported on intervals of length $\ll N$, we see that for each choice of $a$ and $c$ the double sum on the right-hand side of the above is
\begin{equation}\label{eq5.6}
\ll M^2\sum_{\substack{w_3\in[\delta_5M]}}\sum_{w}|\mu_{\delta_1,M}(w+w_3)-\mu_{\delta_1,M}(w)|.
\end{equation}
Since
\[
\mu_{\delta_1,M}(w)=\f{\#\{z,z'\in[\delta_1M]:z-z'=w\}}{\delta_1^{2}M}=\f{\lfloor\delta_1M\rfloor-|w|}{\delta_1^2M},
\]
we can thus use the reverse triangle inequality to bound~\eqref{eq5.6} by
\begin{align*}
\ll M^2\delta_1M\sum_{\substack{w_3\in[\delta_5M]}}\f{|w_3|}{\delta_1^2M}\ll M^2\delta_1M \delta_5^2M^2\f{1}{\delta_1^2M}\ll \delta_5^2/\delta_1 M^4.
\end{align*}
This shows that $E\ll\delta_5^4/\delta_1 M^7$, which by taking $C'>0$ small enough implies that
\begin{align*}
\delta_3^8\delta_4^8\delta_5^3M^7\ll\E_{a,c\in U_b}\sum_x\sum_{\substack{w_1,w_2,w_3\in[\delta_5M]}}[&l_{a+b}(x+(c+b)w_2+cw_3)r'_a(x+(a+b)w_1+(c+b)w_2+cw_3)\\
&l_{c+b}(x+(a+b)w_1+cw_3)r'_c(x+(a+b)w_1+(c+b)w_2)],
\end{align*}
by the bound $\delta_5<C'\delta_3^8\delta_4^8\delta_1^2$.

Note that, for each fixed $x$, the functions $(w_1,w_2,w_3)\mapsto l_{a+b}(x+(c+b)w_2+cw_3)$, $(w_1,w_2,w_3)\mapsto l_{c+b}(x+(a+b)w_1+cw_3)$, and $(w_1,w_2,w_3)\mapsto r'_c(x+(a+b)w_1+(c+b)w_2)$ do not depend on $w_1$, $w_2$, and $w_3$, respectively. Thus, we can apply Lemma~\ref{lem5.8} to deduce that
\begin{align*}
\delta_3^{2^6}\delta_4^{2^6}\delta_5^{6}M^{16}\ll\E_{a,c\in U_b}\sum_x\sum_{\substack{w_i,w_i'\in[\delta_5M]; i=1,2,3}}[&r'_a(x+(a+b)w_1+(c+b)w_2+cw_3)\\
&r'_a(x+(a+b)w_1+(c+b)w_2+cw_3')\\
&r'_a(x+(a+b)w_1+(c+b)w_2'+cw_3)\\
&r'_a(x+(a+b)w_1+(c+b)w_2'+cw_3')\\
&r'_a(x+(a+b)w_1'+(c+b)w_2+cw_3)\\
&r'_a(x+(a+b)w_1'+(c+b)w_2+cw_3')\\
&r'_a(x+(a+b)w_1'+(c+b)w_2'+cw_3)\\
&r'_a(x+(a+b)w_1'+(c+b)w_2'+cw_3')]
\end{align*}
since $l_{a+b},l_{c+b},r_a',r_c'$ are all supported in intervals of length $\ll N$ and $\|r_c'\|_{L^\infty}\leq M$. Recalling the definition of $r_a'$ and making the change of variables $x\mapsto x-(a+b)w_1-(c+b)w_2-cw_3$, the right-hand side above equals $(\delta_5^2M)^3$ times
\begin{align*}
\E_{a,c\in U_b}\sum_{\substack{x,w_1,w_2,w_3 \\ h_1,\dots,h_8}}\prod_{i=1}^3\mu_{\delta_5,M}(w_i)\prod_{j=1}^8\mu_{\delta_1,M}(h_j)[&(fl_{a+b})(x+ah_1)\\
&(fl_{a+b})(x+cw_3+ah_2)\\
&(fl_{a+b})(x+(c+b)w_2+ah_3)\\
&(fl_{a+b})(x+(c+b)w_2+cw_3+ah_4)\\
&(fl_{a+b})(x+(a+b)w_1+ah_5)\\
&(fl_{a+b})(x+(a+b)w_1+cw_3+ah_6)\\
&(fl_{a+b})(x+(a+b)w_1+(c+b)w_2+ah_7)\\
&(fl_{a+b})(x+(a+b)w_1+(c+b)w_2+cw_3+ah_8)].
\end{align*}
After making the change of variables $h_1=h_1'$, $h_4=h_2+h_3+h_4'$, $h_6=h_2+h_5+h_6'$, $h_7=h_3+h_5+h_7'$, and $h_8=h_2+h_3+h_5+h_8'$ and pigeonholing in $h_1',h_4',h_6',h_7'$, and $h_8'$ using that $\supp\mu_{\delta_1,M}\subset(-\delta_1M,\delta_1M)$, we thus deduce that there exist $h_i'\in\Z$ satisfying $|h_i|\ll\delta_1M$ for $i=1,4,6,7,8$ such that
\begin{align*}
\f{\delta_3^{2^6}\delta_4^{2^6}}{\delta_1^{4}}M^{8}\ll\E_{a,c\in U_b}\sum_{\substack{x,w_1,w_2,w_3\\h_2,h_3,h_5}}[&\mu_{\delta_5,M}(w_1)\mu_{\delta_5,M}(w_2)\mu_{\delta_5,M}(w_3) \\
&\mu_{\delta_1,M}(h_2)\mu_{\delta_1,M}(h_3)\mu_{\delta_1,M}(h_5) \\
&\mu_{\delta_1,M}(h_2+h_3+h_4') \\
&\mu_{\delta_1,M}(h_2+h_5+h_6')\\
&\mu_{\delta_1,M}(h_3+h_5+h_7')\\
&\mu_{\delta_1,M}(h_2+h_3+h_5+h_8') \\
&T_{ah_1'}(fl_{a+b})(x) \\
&(fl_{a+b})(x+cw_3+ah_2) \\
&(fl_{a+b})(x+(c+b)w_2+ah_3)\\
&T_{ah_4'}(fl_{a+b})(x+(c+b)w_2+cw_3+a[h_2+h_3])\\
&(fl_{a+b})(x+(a+b)w_1+ah_5)\\
&T_{ah_6'}(fl_{a+b})(x+(a+b)w_1+cw_3+a[h_2+h_5])\\
&T_{ah_7'}(fl_{a+b})(x+(a+b)w_1+(c+b)w_2+a[h_3+h_5])\\
&T_{ah_8'}(fl_{a+b})(x+(a+b)w_1+(c+b)w_2+cw_3+a[h_2+h_3+h_5])].
\end{align*}
Next, we argue using Fourier inversion, as in the proof of Lemma~\ref{lem5.3}, to remove the weights $\mu_{\delta_1,M}(h_2+h_3+h_4'),\mu_{\delta_1,M}(h_2+h_5+h_6'),\mu_{\delta_1,M}(h_3+h_5+h_7'),$ and $\mu_{\delta_1,M}(h_2+h_3+h_5+h_8')$ in the above. Indeed, recalling that $\int_{\T}|\widehat{\mu_{\delta_1,M}}(\gamma)|d\gamma=1/\delta_1$, we get that
\begin{align*}
\delta_3^{2^6}\delta_4^{2^6}M^{8}\ll\E_{a,c\in U_b}\sup_{\gamma_1,\gamma_2,\gamma_3\in\T}\big|\sum_{\substack{x,w_1,w_2,w_3\\h_1,h_2,h_3}}[&\mu_{\delta_5,M}(w_1)\mu_{\delta_5,M}(w_2)\mu_{\delta_5,M}(w_3) \\
&\mu_{\delta_1,\gamma_1}(h_1)\mu_{\delta_1,\gamma_2}(h_2)\mu_{\delta_1,\gamma_3}(h_3) \\
&T_{ah_1'}(fl_{a+b})(x)\\
&(fl_{a+b})(x+cw_3+ah_1)\\
&(fl_{a+b})(x+(c+b)w_2+ah_2)\\
&T_{ah_4'}(fl_{a+b})(x+(c+b)w_2+cw_3+a[h_1+h_2])\\
&(fl_{a+b})(x+(a+b)w_1+ah_3)\\
&T_{ah_6'}(fl_{a+b})(x+(a+b)w_1+cw_3+a[h_1+h_3])\\
&T_{ah_7'}(fl_{a+b})(x+(a+b)w_1+(c+b)w_2+a[h_2+h_3])\\
&T_{ah_8'}(fl_{a+b})(x+(a+b)w_1+(c+b)w_2+cw_3+a[h_1+h_2+h_3])]\big|,
\end{align*}
where $\mu_{\delta_1,\gamma_i}(x):=\mu_{\delta_1,M}(x)e(\gamma_i x)$. (Here we have renamed $h_2,h_3,$ and $h_5$ in the previous displayed equation as $h_1,h_2,$ and $h_3$, respectively.)

Now, for each $a,c\in U_b$ and $\gamma_1,\gamma_2,\gamma_3\in\T$, define
\[
\nu_{a,c,\gamma_1}^{(1)}(k):=\sum_{\substack{w_3,h_1 \\ cw_3+ah_1=k}}\mu_{\delta_5,M}(w_3)\mu_{\delta_1,\gamma_1}(h_1)=\sum_{\substack{w_3,h_1 \\ cw_3+ah_1=k}}\mu_{\delta_5,M}(w_3)\mu_{\delta_1,M}(h_1)e(\gamma_1h_1),
\]
\[
\nu_{a,c,\gamma_2}^{(2)}(k):=\sum_{\substack{w_2,h_2 \\ (c+b)w_2+ah_2=k}}\mu_{\delta_5,M}(w_2)\mu_{\delta_1,\gamma_2}(h_2)=\sum_{\substack{w_2,h_2 \\ (c+b)w_2+ah_2=k}}\mu_{\delta_5,M}(w_2)\mu_{\delta_1,M}(h_2)e(\gamma_2 h_2),
\]
and
\[
\nu_{a,c,\gamma_3}^{(3)}(k):=\sum_{\substack{w_1,h_3 \\ (a+b)w_1+ah_3=k}}\mu_{\delta_5,M}(w_1)\mu_{\delta_1,\gamma_3}(h_3)=\sum_{\substack{w_1,h_3 \\ (a+b)w_1+ah_3=k}}\mu_{\delta_5,M}(w_1)\mu_{\delta_1,M}(h_3)e(\gamma_3 h_3),
\]
so
\begin{align*}
\delta_3^{2^6}\delta_4^{2^6}M^{8}\ll\E_{a,c\in U_b}\sup_{\gamma_1,\gamma_2,\gamma_3\in\T}\big|\sum_{x,k_1,k_2,k_3}[&\nu_{a,c,\gamma_1}^{(1)}(k_1)\nu_{a,c,\gamma_2}^{(2)}(k_2)\nu_{a,c,\gamma_3}^{(3)}(k_3)\\
&T_{ah_1'}(fl_{a+b})(x)(fl_{a+b})(x+k_1)\\
&(fl_{a+b})(x+k_2)T_{ah_4'}(fl_{a+b})(x+k_1+k_2)\\
&(fl_{a+b})(x+k_3)T_{ah_6'}(fl_{a+b})(x+k_1+k_3)\\
&T_{ah_7'}(fl_{a+b})(x+k_2+k_3)T_{ah_8'}(fl_{a+b})(x+k_1+k_2+k_3)]\big|.
\end{align*}
By arguing as in the proof of Lemma~\ref{lem5.3} again using Fourier inversion, for each $a,c\in U_b$ we can bound the quantity inside of the average on the right-hand side above by
\begin{equation}\label{eq5.7}
\sup_{\substack{\gamma_i,\gamma_i'\in\T \\ i=1,2,3}}\left(\int_{\T}|\widehat{\nu_{a,c,\gamma_1}^{(1)}}(\gamma_1')|d\gamma_1'\right)\left(\int_{\T}|\widehat{\nu_{a,c,\gamma_2}^{(2)}}(\gamma_2')|d\gamma_2'\right)\left(\int_{\T}|\widehat{\nu_{a,c,\gamma_3}^{(3)}}(\gamma_3')|d\gamma_3'\right)
\end{equation}
times
\begin{align*}
\sup_{\gamma_1',\gamma_2',\gamma_3'\in\T}\big|\sum_{x,k_1,k_2,k_3}[&T_{ah_1'}(fl_{a+b})(x)e(-(\gamma_1'+\gamma_2'+\gamma_3') x)(fl_{a+b})(x+k_1)e(\gamma_1'(x+k_1))\\
&(fl_{a+b})(x+k_2)e(\gamma_2'(x+k_2))T_{ah_4'}(fl_{a+b})(x+k_1+k_2)\\
&(fl_{a+b})(x+k_3)e(\gamma_3'(x+k_3))T_{ah_6'}(fl_{a+b})(x+k_1+k_3)\\
&T_{ah_7'}(fl_{a+b})(x+k_2+k_3)T_{ah_8'}(fl_{a+b})(x+k_1+k_2+k_3)]\big|.
\end{align*}
For each $\gamma_1',\gamma_2',$ and $\gamma_3'$, this second quantity can be easily bounded above in terms of $\|fl_{a+b}\|_{U^3}$ by the Gowers--Cauchy--Schwarz inequality. So, we bound~\eqref{eq5.7}.

Note that for any $\gamma_1\in\T$, we have
\[
\nu_{a,c,\gamma_1}^{(1)}(k)=\f{1}{\delta_1^2\delta_5^2M^2}(1_{c[\delta_5M]}*1_{-c[\delta_5M]}*[1_{a[\delta_1M]}e(\gamma_1\cdot/a)]*[1_{-a[\delta_1M]}e(\gamma_1\cdot/a)])(k),
\]
so that
\begin{align*}
|\widehat{\nu_{a,c,\gamma_1}^{(1)}}(\gamma_1')|&=\f{1}{\delta_1^2\delta_5^2M^2}\left|(1_{c[\delta_5M]}*[1_{a[\delta_1M]}e(\gamma_1\cdot/a)])^{\wedge}(\gamma_1')\right|^2
\end{align*}
and, by Parseval's identity and the triangle inequality, that
\[
\int_{\T}|\widehat{\nu_{a,c,\gamma_1}^{(1)}}(\gamma_1')|d\gamma_1' =\f{1}{\delta_1^2\delta_5^2M^2}\|1_{c[\delta_5M]}*1_{a[\delta_1M]}e(\gamma_1\cdot/a)\|^2_{\ell^2}\leq\f{1}{\delta_1^2\delta_5^2M^2}\|1_{c[\delta_5M]}*1_{a[\delta_1M]}\|^2_{\ell^2}.
\]
Similarly, for any $\gamma_2,\gamma_3\in \T$, we have
\[
\int_{\T}|\widehat{\nu_{a,c,\gamma_2}^{(2)}}(\gamma_2')|d\gamma_2'\leq\f{1}{\delta_1^2\delta_5^2M^2}\|1_{(c+b)[\delta_5M]}*1_{a[\delta_1M]}\|^2_{\ell^2}
\]
and
\[
\int_{\T}|\widehat{\nu_{a,c,\gamma_3}^{(3)}}(\gamma_3')|d\gamma_3'\leq\f{1}{\delta_1^2\delta_5^2M^2}\|1_{(a+b)[\delta_5M]}*1_{a[\delta_1M]}\|_{\ell^2}^2.
\]
For most $a,c\in U_b$, both $\gcd(a,c)$ and $\gcd(a,c+b)$ are small. Indeed, by two applications of Lemma~\ref{lem5.7}, for all but a $\ll C\delta_3^{2^6}\delta_4^{2^6}$ fraction of the pairs $(a,c)\in[\delta_2 M]^2$, we have that $\gcd(a,c),\gcd(a,c+b)\leq\f{1}{C}\delta_3^{-2^6}\delta_4^{-2^6}$. For such pairs $(a,c)$, we have
\begin{align*}
\|1_{c[\delta_5M]}*1_{a[\delta_1M]}\|_{\ell^2}^2 &= \#\{x_1,x_2\in[\delta_5M],y_1,y_2\in[\delta_1M] : c[x_1-x_2]=a[y_1-y_2]\} \\
&\ll \delta_5\delta_1M^2\cdot\f{\delta_5M}{\delta_1M/(\delta_3^{-2^6}\delta_4^{-2^6}/C)}\f{\delta_1M}{\delta_1M/(\delta_3^{-2^6}\delta_4^{-2^6}/C)} \\
&= \f{1}{C^2}\delta_5^{2}\delta_3^{-2^7}\delta_4^{-2^7}M^2,
\end{align*}
since $\gcd(a,c)\leq\f{1}{C}\delta_3^{-2^6}\delta_4^{-2^6}$ and $a,c>\delta_1M$. Similarly,
\[
\|1_{(c+b)[\delta_5M]}*1_{a[\delta_1M]}\|_{\ell^2}^2\ll\f{1}{C^2}\delta_5^{2}\delta_3^{-2^7}\delta_4^{-2^7}M^2
\]
and
\[
\|1_{(a+b)[\delta_5M]}*1_{a[\delta_1M]}\|_{\ell^2}^2\ll\delta_5^2\delta_1^{-2}M^2,
\]
since $\gcd(a,b)\leq\delta_1\1$.

As a consequence, by taking $C>0$ sufficiently small, we thus have
\begin{align*}
\delta_3^{2^9}\delta_4^{2^9}M^8\ll\E_{a,c\in U_b}\sup_{\gamma_1',\gamma_2',\gamma_3'\in\T}\big|\sum_{x,k_1,k_2,k_3}[&T_{ah_1'}(fl_{a+b})(x)e(-(\gamma_1'+\gamma_2'+\gamma_3') x)(fl_{a+b})(x+k_1)e(\gamma_1'(x+k_1))\\
&(fl_{a+b})(x+k_2)e(\gamma_2'(x+k_2))T_{ah_4'}(fl_{a+b})(x+k_1+k_2)\\
&(fl_{a+b})(x+k_3)e(\gamma_3'(x+k_3))T_{ah_6'}(fl_{a+b})(x+k_1+k_3)\\
&T_{ah_7'}(fl_{a+b})(x+k_2+k_3)T_{ah_8'}(fl_{a+b})(x+k_1+k_2+k_3)]\big|,
\end{align*}
by recalling the assumption $\delta_1<C\delta_4\delta_2\leq C\delta_4$. The sum inside of the supremum is the $U^3$-inner product of eight $1$-bounded functions that are supported on intervals of length $\ll N$. Thus, by the Gowers--Cauchy--Schwarz inequality, we have
\[
\delta_3^{2^{12}}\delta_4^{2^{12}}M^8\ll\E_{a\in U_b}\sum_{x,k_1,k_2,k_3}\Delta_{k_1,k_2,k_3}(fl_{a+b})(x).
\]

Finally, inserting extra averaging in $x$ by shifting by multiples of $(a+b)$, for any $0<\delta_6<C'\delta_3^{2^{12}}\delta_4^{2^{12}}\delta_1^2$ when $C'>0$ is sufficiently small, we have by the almost-invariance of $l_{a+b}$ that
\[
\delta_3^{2^{12}}\delta_4^{2^{12}}\delta_6M^9\ll\E_{a\in U_b}\sum_{x,k_1,k_2,k_3}\sum_{m\in[\delta_6M]}\Delta_{k_1,k_2,k_3}f(x+(a+b)m)\Delta_{k_1,k_2,k_3}l_{a+b}(x).
\]
Applying the Cauchy--Schwarz inequality once in the $a,x,k_1,k_2,$ and $k_3$ variables, we get
\[
\delta_3^{2^{13}}\delta_4^{2^{13}}M^9\ll\E_{a\in U_b}\sum_{x,k_1,k_2,k_3}\sum_{m}\mu_{\delta_6,M}(m)\Delta_{k_1,k_2,k_3}f(x)\Delta_{k_1,k_2,k_3}f(x+(a+b)m),
\]
and applying it in the $x,k_1,k_2,$ and $k_3$ variables and using Lemma~\ref{lem5.7} and the pigeonhole principle again, we get that there exist $a,c\in U_b$ with $\gcd(a+b,c+b)\ll\delta_3^{-2^{14}}\delta_4^{-2^{14}}$ such that
\[
\delta_3^{2^{14}}\delta_4^{2^{14}}M^{10}\ll\sum_{\substack{x,k_1,k_2,k_3 \\ m,m'}}\mu_{\delta_6,M}(m)\mu_{\delta_6,M}(m')\Delta_{k_1,k_2,k_3}f(x)\Delta_{k_1,k_2,k_3}f(x+(a+b)m-(c+b)m').
\]
Hence by Fourier inversion and the Gowers--Cauchy--Schwarz inequality, we conclude in a similar manner as previously that
\[
\delta_3^{2^{20}}\delta_4^{2^{20}}M^{10}\ll\sum_{x,k_1,k_2,k_3,k_4}\Delta_{k_1,k_2,k_3,k_4}f(x)=\|f\|_{U^4}^{2^4}.
\]
Recalling that $M=N^{1/2}$, this completes the proof of the lemma.
\end{proof}
\subsection{Proof of Theorem~\ref{thm5.2}}\label{ss5.3}
We can now prove Theorem~\ref{thm5.1}, which will then immediately imply Theorem~\ref{thm5.2} when combined with the results of Section~\ref{sec4}.

\begin{proof}[Proof of Theorem~\ref{thm5.1}]
Note that, for all $h_2$, we have the bound
\[
\left|\E_{a,b\in[\delta_1 M]}\sum_{x,h_1,h_3}\mu_{\delta_2,M}(h_1)\mu_{\delta_2,M}(h_3)\Delta_{2q(a+b)h_1,2qah_3}(\Delta_{2qbh_2}f)(x)\right|\ll NM^2.
\]
As a consequence, for at least a $\gg\delta_3$-proportion of the $\mu_{\delta_2,M}$-mass of the $h_2$'s, we have that
\[
\E_{a,b\in[\delta_1 M]}\sum_{x,h_1,h_3}\mu_{\delta_2,M}(h_1)\mu_{\delta_2,M}(h_3)\Delta_{2q(a+b)h_1,2qah_3}(\Delta_{2qbh_2}f)(x)\gg\delta_3NM^2.
\]
For each of these $h_2$, we apply Corollary~\ref{cor5.6} with $f_b:=\Delta_{2qbh_2}f$ to deduce that
\[
\E_{u\in[q]}\E_{b\in[\delta_1M]}\|\Delta_{2qbh_2}f\|_{U^4(u+q\Z)}^{2^4}\gg(\delta_2\delta_3)^{2^{21}}(N/q)^5.
\]
Thus, by positivity, we have
\[
\E_{u\in[q]}\E_{b\in[\delta_1M]}\sum_{h_2}\mu_{\delta_2,M}(h_2)\|\Delta_{2qbh_2}f\|_{U^4(u+q\Z)}^{2^4}\gg \delta_3 M(\delta_2\delta_3)^{2^{21}}(N/q)^5.
\]
Expanding the definition of $\|\cdot\|_{U^4(u+q\Z)}$, this means that
\[
\E_{u\in[q]}\E_{b\in[\delta_1 M]}\sum_{\substack{x,h_2 \\ k_1,k_2,k_3,k_4}}\mu_{\delta_2,M}(h_2)\Delta_{k_1,k_2,k_3,k_4}T_{u}f(qx)\Delta_{k_1,k_2,k_3,k_4}T_{u}f(qx+2qbh_2)\gg(\delta_2\delta_3)^{2^{21}}\delta_3(N/q)^5M.
\]
Applying Cauchy--Schwarz in the $u,x,k_1,k_2,k_3,$ and $k_4$ variables, we thus deduce that
\[
\E_{u\in[q]}\E_{b,d\in[\delta_1 M]}\sum_{\substack{x,h_2,h_2' \\ k_1,k_2,k_3,k_4}}\mu_{\delta_2,M}(h_2)\mu_{\delta_2,M}(h_2')\Delta_{k_1,k_2,k_3,k_4,2[bh_2-dh_2']}T_{u}f(qx)\gg(\delta_2\delta_3)^{2^{23}}(N/q)^{6},
\]
recalling that $M^2=N/q$. By using Lemma~\ref{lem5.7}, the pigeonhole principle, Fourier inversion, and the Gowers--Cauchy--Schwarz inequality again as in the proof of Lemma~\ref{lem5.5}, we conclude that
\[
\E_{u\in[q]}\|f\|_{U^5(u+q\Z)}^{2^5}\gg(\delta_2\delta_3)^{2^{25}}(N/q)^6.
\]
\end{proof}
Now we can prove Theorem~\ref{thm5.2}.
\begin{proof}[Proof of Theorem~\ref{thm5.2}]
We apply Lemma~\ref{lem4.1} with $\delta_1=\delta$, $\delta_2=C\delta^4$, and $\delta_3=C\delta^{140}$ for $C$ sufficiently small to deduce that
\[
\E_{a,b\in[\delta_2M]}\sum_{x,h_1,h_2,h_3}\mu_{\delta_3,M}(h_1)\mu_{\delta_3,M}(h_2)\mu_{\delta_3,M}(h_3)\Delta_{2q(a+b)h_1,2qbh_2,2qah_3}f_2(x)\gg\delta^{32}NM^3,
\]
provided $N\geq\f{1}{C}q\delta^{-72}$. Noting that $\delta_3<C'\delta^{12}\delta^{128}$ for $C'>0$ going to zero with $C$, we can thus apply Theorem~\ref{thm5.1} to deduce that
\[
\E_{u\in[q]}\|f_2\|_{U^5(u+q\Z)}^{2^5}\gg(\delta^{140+32})^{2^{25}}(N/q)^{6}\gg\delta^{2^{33}}(N/q)^6
\]
if $C$ is small enough.
\end{proof}

\section{Degree lowering}\label{sec6}
So far, we have shown that $\Lambda_q(f_0,f_1,f_2)$ is controlled by $\E_{u\in[q]}\|f_2\|_{U^5(u+q\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 of the argument is to bound $\Lambda_q(f_0,f_1,f_2)$ in terms of an average of $U^5(u+q\Z)$-norms of the dual function
\begin{equation}\label{eq6.1}
F(x):=\E_{y\in[M]}f_0(x-qy^2)f_1(x+y-qy^2).
\end{equation}
For future reference, note that $F$ is $1$-bounded and supported on $[N+q,2N]$.

To do this, we will use the following consequence of the Hahn-Banach Theorem. This lemma is essentially the same as Proposition~2.6 in ~\cite{Pe2}, except that powers of $1/q$ have been replaced with appropriate powers of $\ve$, $\F_q$ has been replaced by $[N]$, and we phrase things in terms of $\ell^p$-norms instead of $L^p$-norms. We give the proof of Lemma~\ref{lem6.1} in Appendix~\ref{appA} for completeness.
\begin{lemma}\label{lem6.1}
Let $f:\Z\to\C$ be function supported on the interval $[N]$ satisfying $\|f\|_{\ell^2}^2\leq N$, $\|\cdot\|$ be any norm on the space of complex-valued functions supported on $[N]$, and $\ve_1,\ve_2,\ve_3,\ve_4>0$. There exists a decomposition $f=g_{str}+g_{sml}+g_{unf}$ such that
\begin{enumerate}
\item $\|g_{str}\|^*\leq\ve_1\1 N$,
\item $\|g_{sml}\|_{\ell^1}\leq\ve_2 N$,
\item $\|g_{unf}\|_{L^\infty}\leq\ve_3\1$, and $\|g_{unf}\|\leq\ve_4$,
\end{enumerate}
provided $\ve_2\1\ve_3+\ve_1\ve_4\1\leq 1/2$.
\end{lemma}
Note that, when $f_2$ is $1$-bounded and supported on the interval $[N]$, we have that
\[
\E_{u\in[q]}\f{1}{(N/q)^6}\|f_2\|_{U^5(u+q\Z)}^{2^5}\leq \E_{u\in[q]}\f{1}{(N/q)^{6/2^5}}\|f_2\|_{U^5(u+q\Z)},
\]
since for such $f_2$ we have $\|f_2\|_{U^5}^{2^5}/(N/q)^6\leq 1$. We thus apply Lemma~\ref{lem6.1} with the norm $\|f\|:=\E_{u\in[q]}\f{1}{(N/q)^{6/2^5}}\|f\|_{U^5(u+q\Z)}$ (which is a norm on the space of functions supported on $[2N]$ because it is an average of such norms (see Appendix~B of~\cite{GT})), $\ve_1=C\delta^{2^{35}}/100$, $\ve_2=\delta/2$, $\ve_3=\delta/100$, and $\ve_4=C\delta^{2^{35}}$ for $C$ sufficiently small to get a decomposition
\[
f_2=g_{str}+g_{sml}+g_{unf}
\]
satisfying $\|g_{str}\|^*\leq\ve_1\1 N$, $\|g_{sml}\|_{\ell^1}\leq\ve_2 N$, $\|g_{unf}\|_{L^\infty}\leq\ve_3\1$, and $\|g_{unf}\|\leq\ve_4$. Suppose that $|\Lambda_q(f_0,f_1,f_2)|\geq\delta NM$. Then by the trilinearity of $\Lambda_q$, we have
\[
\Lambda_q(f_0,f_1,f_2)=\Lambda_q(f_0,f_1,g_{str})+\Lambda_q(f_0,f_1,g_{sml})+\Lambda_q(f_0,f_1,g_{unf}).
\]
By the triangle inequality, we have $\Lambda_q(f_0,f_1,g_{sml})\leq \delta NM/2$ because $f_0$ and $f_1$ are $1$-bounded. Thus,
\[
|\Lambda_q(f_0,f_1,g_{str})|+|\Lambda_q(f_0,f_1,g_{unf})|\geq \delta NM/2.
\]
If $|\Lambda_q(f_0,f_1,g_{unf})|$ had size at least $\delta NM/4$, then, since $g_{unf}/\ve_3\1$ is $1$-bounded and supported on $[N]$, Theorem~\ref{thm5.2} tells us that
\[
(\delta\ve_3)^{2^{33}}(N/q)^6\ll \E_{u\in[q]}\|g_{unf}/\ve_3\1\|_{U^5(u+q\Z)}^{2^5},
\]
so that, certainly,
\[
(\delta\ve_3)^{2^{33}}\ll \E_{u\in[q]}\f{1}{(N/q)^{6/2^5}}\|g_{unf}/\ve_3\1\|_{U^5(u+q\Z)}=\|g_{unf}/\ve_3\|\leq \ve_4/\ve_3,
\]
since $g_{unf}/\ve_3\1$ is $1$-bounded and supported on the interval $[N]$. But this implies that $\delta^{2^{34}+1}\ll C\delta^{2^{35}}$, which is false for every $\delta\leq 1$ when $C$ is small enough. Thus,
\[
|\Lambda_q(f_0,f_1,g_{str})|\geq\delta NM/4.
\]
We can write $\Lambda_q(f_0,f_1,g_{str})$ as the inner product $M\sum_{x}g_{str}(x)\overline{\overline{F(x)}}$, which combined with the bound $\|g_{str}\|^*\leq \ve_1\1 N$ implies that $\delta/4\leq \ve_1\1 \|F\|$. Thus, by H\"older's inequality, we have
\[
\delta^{2^5}\ve_1^{2^5}\ll(\E_{u\in[q]}\f{1}{(N/q)^{6/2^5}}\|F\|_{U^5(u+q\Z)})^{2^5}\ll \E_{u\in[q]}\f{1}{(N/q)^{6}}\|F\|_{U^5(u+q\Z)}^{2^5}.
\]
We conclude that
\begin{equation}\label{eq6.?}
\delta^{2^{41}}(N/q)^{6}\ll \E_{u\in[q]}\|F\|_{U^5(u+q\Z)}^{2^5}.
\end{equation}

In this section, we will show that, for every $s\geq 3$, the lower bound $\|F\|_{U^s(u+q\Z)}^{2^s}\geq\gamma (N/q)^{s+1}$ implies that $\|F\|_{U^{s-1}(u+q\Z)}^{2^{s-1}}\gg\gamma^{2^{9s}}(N/q)^{s}$, so that
\[
\|F\|_{U^{s-1}(u+q\Z)}^{2^{s-1}}\gg \left(\f{\|F\|_{U^{s}(u+q\Z)}^{2^s}}{(N/q)^{s+1}}\right)^{2^{9s}} (N/q)^s.
\]
We can thus deduce from~\eqref{eq6.?} that $\E_{u\in[q]}\|F\|^4_{U^2(u+q\Z)}\gg\delta^{2^{149}}(N/q)^3$ by applying the above with $s=5,4,$ and $3$.

Before beginning the degree lowering argument, we prove the following lemma, which is the ``understanding of two-term progressions'' input mentioned in Subsection~\ref{ss3.3}. Note that if the $y^2$ term in the hypothesis were replaced by a linear polynomial in $y$ (and the range $[M]$ were correspondingly extended to $[N]$), then the lemma would fail to hold. This is where it is crucial that the terms of the progression $x,x+y,x+qy^2$ satisfy no linear relations.
\begin{lemma}\label{lem6.2}
Let $\alpha\in\T$, $q\in\N$, and $\gamma>0$, and set $M:=(N/q)^{1/2}$. If there exist $1$-bounded functions $g_0,g_1:\Z\to\C$ supported on the interval $[N]$ such that
\[
\left|\sum_x\sum_{y\in[M]}g_0(qx-qy^2)g_1(qx+y-qy^2)e(\alpha x)\right|\geq\gamma\f{NM}{q},
\]
then there exists a positive integer $t\ll\gamma^{-4}$ such that $\|q^2t\alpha\|\ll\gamma^{-5}/(N/q^3)$.
\end{lemma}
\begin{proof}
We first split the sum over $y\in[M]$ up into arithmetic progressions modulo $q$ by writing $y=qz-h$ for $h\in[q]$, and use the pigeonhole principle to find an $h\in[q]$ for which
\[
\left|\sum_x\sum_{z\in[M/q]}g_0(qx-q(qz-h)^2)g_1(qx+(qz-h)-q(qz-h)^2)e(\alpha x)\right|\geq\gamma\f{NM}{q^2}.
\]
Making the change of variables $x\mapsto x+q(qz^2-2hz)$, this means that
\[
\left|\sum_xg_0(qx-qh^2)\sum_{z\in[M/q]}g_1(qx+qz-h-qh^2)e(\alpha [x+q(qz^2-2hz)])\right|\geq\gamma\f{NM}{q^2}.
\]
We apply the Cauchy--Schwarz inequality in the $x$ variable to the above to get that
\[
\sum_x\left|\sum_{z\in[M/q]}g_1(qx+qz-h-qh^2)e(\alpha [x+q(qz^2-2hz)])\right|^2\geq\gamma^2\f{NM^2}{q^3},
\]
so that, by applying van der Corput's inequality with $H=\gamma^3 M/q$ and making the change of variables $x\mapsto x-z$, we have
\[
\sum_{x,a}\mu_{\gamma^3,M/q}(a)\overline{\Delta_{qa}g_1(qx-h-qh^2)}e(\alpha q[-2ha+qa^2])\sum_{z\in[M/q]}e(2\alpha q^2az)\geq\gamma^2\f{NM^2}{q^3},
\]
Applying the Cauchy--Schwarz inequality again in the $x$ and $a$ variables and using the fact that $\|\mu_{\gamma^3,M/q}\|_{\ell^2}^2\leq\gamma^{-3}M/q$ and $\mu_{\gamma^3,M/q}$ is supported on $(-\gamma^3M/q,\gamma^3M/q)$, we get that
\[
\sum_{0\leq a\leq \gamma^3 M/q}\left|\sum_{z\in[M/q]}e(2\alpha q^2az)\right|^2\gg\gamma^7\f{M^3}{q^3}.
\]

Suppose now that $|2\alpha q^2-b/d|\leq d^{-2}$ for some relatively prime integers $b$ and $d$. Then
\begin{align*}
\sum_{0\leq a\leq \gamma^3 M/q}\left|\sum_{z\in[M/q]}e(2\alpha q^2az)\right|^2 &\ll\sum_{0\leq a\leq \gamma^3 M/q}\min((M/q)^2,1/\|2\alpha q^2a\|^2) \\
&\ll\f{\gamma^3 M}{dq}\left(\f{M^2}{q^2}+d^2\right).
\end{align*}
Hence,
\[
\f{1}{d}+\f{d}{(M/q)^2}\gg\gamma^4.
\]
Now, by the pigeonhole principle, there exists a $d\ll\gamma^5 (M/q)^2$ such that $\|2\alpha q^2 d\|\ll\gamma^{-5}/(M/q)^2$. This means that there exists a $b\in\Z$ relatively prime to $d$ for which $|2\alpha q^2-b/d|\leq d^{-2}$, and thus $1/d+d/(M/q)^2\gg\gamma^4$. In this case, $1/d\gg\gamma^4$ since $d/(M/q)^2\ll\gamma^5$, which forces $d\ll\gamma^{-4}$. We conclude by taking $t:=2d$ and recalling that $M^2=N/q$.
\end{proof}
The main argument of this section will be carried out in the proof of Proposition~\ref{prop6.6}. For this, we will need three lemmas. The first, Lemma~\ref{lem6.3}, says that if many multiplicative derivatives $\Delta_{h}T_uF(x)$ of a dual function correlate with linear phases depending on $h$, then many related dual functions correlate with linear phases of a special form.

Before stating the lemma, we introduce some useful notation. For any $m\in\N$ and subset $H\subset\Z^m$, let $\square_m(H)$ denote the set of $2m$-tuples of integers
\[
\ul{k}=(k_{10},\dots,k_{m0},k_{11},\dots,k_{m1})\in\Z^{2m}
\]
satisfying $(k_{1i_1},\dots,k_{mi_m})\in H$ for all $(i_1,\dots,i_m)\in\{0,1\}^m$. For example,
\[
\square_2(H)=\{(k_{10},k_{20},k_{11},k_{21})\in\Z^4:(k_{10},k_{20}),(k_{10},k_{21}),(k_{11},k_{20}),(k_{11},k_{21})\in H\}.
\]
\begin{lemma}\label{lem6.3}
Let $q\in\N$, $\gamma>0$, $H\subset[N/q]^m$ with $H\geq\gamma (N/q)^m$, and $f_0,f_1:\Z\to\C$ be $1$-bounded functions supported in the interval $[N]$. Suppose that the dual function $F$ is defined as in~\eqref{eq6.1}. If
\begin{equation}\label{eq6.2}
\sum_{\ul{h}\in H}\left|\sum_x\Delta_{q\ul{h}}T_uF(qx)e(\phi(\ul{h})x)\right|^2\geq\gamma |H| \f{N^2}{q^2}
\end{equation}
for $u\in[q]$ and some function $\phi:H\to\T$, then
\[
\E_{\ul{k}\in\square_m(H)}\left|\sum_{x}\E_{y\in[M]}\Delta_{q(k_{i1}-k_{i0})}T_uf_0(qx-qy^2)\Delta_{q(k_{i1}-k_{i0})}T_uf_1(qx+y-qy^2)e(\psi(\ul{k})x)\right|^2\geq\gamma^{m+2^m}\f{N^2}{q^2},
\]
where
\[
\psi(\ul{k}):=\sum_{\omega\in\{0,1\}^m}(-1)^{|\omega|}\phi(k_{1\omega_1},\dots,k_{m\omega_m}).
\]
\end{lemma}
For example, when $m=2$ we have
\[
\psi(k_{10},k_{20},k_{11},k_{21})=\phi(k_{10},k_{20})-\phi(k_{10},k_{21})-\phi(k_{11},k_{20})+\phi(k_{11},k_{21}).
\]
\begin{proof}
By expanding the definition of the dual function $F$~\eqref{eq6.1} and setting
\[
F_{y}(x):=T_uf_0(qx-qy^2)T_uf_1(qx+y-qy^2)
\]
so that $T_uF(qx)=\E_{y\in[M]}F_y(x)$, we can write the left-hand side of~\eqref{eq6.2} as
\[
\E_{\substack{y_{\omega 0},y_{\omega 1}\in[M] \\ \omega\in\{0,1\}^m}}\sum_{\ul{h}\in[N/q]^m}\sum_{x,z}1_H(\ul{h})\prod_{\omega\in\{0,1\}^m}F_{y_{\omega 0}}(x+\ul{h}\cdot\omega)\overline{F_{y_{\omega 1}}(z+\ul{h}\cdot\omega)}e(\phi(\ul{h})[x-z]).
\]
We will now apply the Cauchy--Schwarz inequality $m$ times, first in all but the $h_1$ variable to get that
\begin{align*}
\gamma^2\f{|H|^2(N/q)^2}{(N/q)^{m-1}}\ll&\E_{\substack{y_{\omega 0},y_{\omega 1}\in[M] \\ \omega\in\{0,1\}^m}}\sum_{h_1,\dots,h_m,h_1'\in[N/q]}1_H(h_1,\dots,h_m)1_H(h_1',h_2,\dots,h_m) \\
&\sum_{x,z}\prod_{\substack{\omega\in\{0,1\}^m \\ \omega_1=0}}\Delta_{h_1'-h_1}F_{y_{\omega 0}}(x+\ul{h}\cdot\omega)\overline{\Delta_{h_1'-h_1}F_{y_{\omega 1}}(z+\ul{h}\cdot\omega)} \\
&e([\phi(h_1,\dots,h_m)-\phi(h_1',h_2,\dots,h_m)][x-z])
\end{align*}
after making the change of variables $x\mapsto x-h_1$ and $z\mapsto z-h_1$. We similarly apply the Cauchy--Schwarz inequality in all but the $h_i$ variable for $i=2,\dots,m$ to get that
\[
\gamma^{2^m}\f{|H|^{2^m}(N/q)^2}{(N/q)^{m2^m-2m}}\ll\E_{y_0,y_1\in[M]}\sum_{\ul{h}\in\square_m(H)}\sum_{x,z}\Delta_{(h_i'-h_i)}F_{y_0}(x)\overline{\Delta_{(h_i'-h_i)}F_{y_1}(z)}e(\psi(\ul{h})[x-z]).
\]
Note that the right-hand side of the above can be written as
\[
\sum_{\ul{h}\in\square_m(H)}\left|\sum_x\E_{y\in[M]}\Delta_{(h_i'-h_i)}F_y(x)e(\psi(\ul{h})x)\right|^2.
\]

Now, by the lower bound $|H|\geq\gamma (N/q)^m$, we have
\[
\f{|H|^{2^m}}{(N/q)^{m2^m-2m}}\geq\gamma^m\f{(N/q)^{m2^m}}{(N/q)^{m2^m-2m}}=\gamma^m (N/q)^{2m},
\]
and since $|\square_m(H)|\leq (N/q)^{2m}$ trivially, we deduce that
\[
\gamma^{m+2^m}(N/q)^2M^2\leq\E_{\ul{h}\in\square_m(H)}\left|\sum_x\sum_{y\in[M]}\Delta_{(h_i'-h_i)}F_y(x)e(\psi(\ul{h})x)\right|^2.
\]
Since the quantity inside of the absolute value equals
\[
\sum_{x}\E_{y\in[M]}\Delta_{q(h_i'-h_i)}T_uf_0(qx-qy^2)\Delta_{q(h_i'-h_i)}T_uf_1(qx+y-qy^2)e(\psi(\ul{h})x),
\]
this completes the proof of the lemma.
\end{proof}
The next lemma, Lemma~\ref{lem6.4}, is similar to Lemma~\ref{lem5.8} in that it essentially says that a function of $k$ variables that correlates with functions all depending on at most $k-1$ of those variables has large box norm. For the particular function considered in Lemma~\ref{lem6.4}, this box norm translates into a $U^s$-norm.
\begin{lemma}\label{lem6.4}
Let $q,m\in\N$, $\gamma>0$, and $\phi_i:[N/q]^{m-1}\to\C$ for $1\leq i\leq m$. Then for every $1$-bounded function $f:\Z\to\C$ supported on $[N/q]$, we have
\[
\sum_{\ul{h}\in\Z^m}\left|\sum_x\Delta_{q\ul{h}}f(qx)e\left(\sum_{i=1}^m\phi_i(h_1,\dots,\widehat{h_i},\dots,h_m)x\right)\right|^2\leq (N/q)^{m(1-2^{-m})}\|f\|_{U^{m+1}(q\Z)}^{2}.
\]
\end{lemma}
\begin{proof}
Expanding, the left-hand side of the above equals
\begin{equation}\label{eq6.3}
\sum_{\ul{h}\in\Z^m}\sum_{x,h_{m+1}}\Delta_{qh_1,\dots,qh_{m+1}}f(qx)e\left(\sum_{i=1}^m\phi_i(h_1,\dots,\widehat{h_i},\dots,h_m)h_{m+1}\right).
\end{equation}
We now apply the Cauchy--Schwarz inequality $m$ times, once in all but the $h_i$ variable for each $i=1,\dots,m$. Applying the Cauchy--Schwarz inequality in all but the $h_1$ variable, for example, bounds the above by the square root of
\[
(N/q)^{m+2}\sum_{\ul{h}\in\Z^m}\sum_{x,h_{m+1}}\Delta_{qh_1,\dots,qh_{m+1}}f(qx)e\left(\sum_{i=2}^m\phi_i(h_1,\dots,\widehat{h_i},\dots,h_m)h_{m+1}\right).
\]
Similarly, applying the Cauchy--Schwarz inequality in all but the $h_i$ variable for $i=2,\dots,m$, we get that~\eqref{eq6.3} is bounded above by the $2^{m}$-th root of
\[
(N/q)^{(m+2)(2^m-1)}\sum_{\ul{h}\in\Z^m}\sum_{x,h_{m+1}}\Delta_{qh_1,\dots,qh_{m+1}}f(qx),
\]
which equals $(N/q)^{m(2^m-1)}\|f\|_{U^{m+1}(q\Z)}^{2^{m+1}}$.
\end{proof}
The final lemma records an easy fact about rational approximation for convenience in the proof of Proposition~\ref{prop6.6}.
\begin{lemma}\label{lem6.5}
Let $\alpha\in\T$ and suppose that $a,b\in\Z$ with
\[
\left|\alpha-\f{a}{b}\right|\leq \gamma.
\]
For any $C\geq 1$, there exists an integer $k$ with $|k|\leq C$ and $\theta\in[-1,1]$ such that
\[
\alpha=\f{a}{b}+k\f{\gamma}{C}+\theta\f{\gamma}{C}.
\]
\end{lemma}
\begin{proof}
Take $k=\lfloor\beta/\gamma\rfloor$ and $\theta=(\beta-k\gamma)/\gamma$.
\end{proof}

Now we can prove the main result of this section.
\begin{proposition}[$U^s$-control implies $U^{s-1}$-control]\label{prop6.6}
Let $s\geq 3$, $q\in\N$, $\gamma>0$, and $f_0,f_1:\Z\to\C$ be $1$-bounded functions supported in the interval $[N]$. Set $M:=(N/q)^{1/2}$. Suppose that the dual function $F$ is defined as in~\eqref{eq6.1}. If
\[
\|F\|_{U^s(u+q\Z)}^{2^s}\geq\gamma(N/q)^{s+1},
\]
then
\[
\|F\|_{U^{s-1}(u+q\Z)}^{2^{s-1}}\geq\gamma^{2^{9s}}(N/q)^{s}.
\]
\end{proposition}
\begin{proof}
Since $\|F\|_{U^s(u+q\Z)}^{2^s}=\sum_{h_1,\dots,h_{s-2}}\|\Delta_{qh_1,\dots,qh_{s-2}}F\|_{U^2(u+q\Z)}^4$, the inverse theorem for the $U^2(u+q\Z)$-norm tells us that
\[
\sum_{h_1,\dots,h_{s-2}\in\Z}\left|\sum_x\Delta_{qh_1,\dots,qh_{s-2}}T_uF(qx)e(\phi(h_1,\dots,h_{s-2})x)\right|^2\gg\gamma^{2^s}(N/q)^{s}
\]
for some $\phi(h_1,\dots,h_{s-2})\in\T$ for each $(h_1,\dots,h_{s-2})\in [N/q]^{s-2}$. By the pigeonhole principle, there exists an $H\subset [N/q]^{s-2}$ with $|H|\gg\gamma^{2^s}(N/q)^{s-2}$ such that
\[
\left|\sum_{x}\Delta_{qh_1,\dots,qh_{s-2}}T_uF(qx)e(\phi(h_1,\dots,h_{s-2})x)\right|^2\gg\gamma^{2^s}(N/q)^2
\]
for each $(h_1,\dots,h_{s-2})\in H$.

Now we apply Lemma~\ref{lem6.3}, which, since $|H|\gg\gamma^{2^s}(N/q)^{s-2}$, tells us that
\[
\E_{\ul{k}\in\square_{s-2}(H)}\left|\sum_{x}\E_{y\in[M]}\Delta_{q(k_{i1}-k_{i0})}T_uf_0(qx-qy^2)\Delta_{q(k_{i1}-k_{i0})}T_uf_1(qx+y-qy^2)e(\psi(\ul{k})x)\right|^2\geq\gamma^{2^{2s}}\f{N^2}{q^2},
\]
where
\[
\psi(\ul{k}):=\sum_{\omega\in\{0,1\}^{s-2}}(-1)^{|\omega|}\phi(k_{1\omega_1},\dots,k_{(s-2)\omega_{s-2}}).
\]
By the Cauchy--Schwarz inequality and the lower bound $|H|\gg\gamma^{2^s}(N/q)^{s-2}$, the number of elements in $\square_{s-2}(H)$ is at least $\gamma^{2^{2s}} (N/q)^{2(s-2)}$. Thus, by the pigeonhole principle, there exists a set of $2(s-2)$-tuples $H'\subset\square_{s-2}(H)$ with $|H'|\gg\gamma^{2^{2s}}(N/q)^{2(s-2)}$ such that
\[
\left|\sum_{x}\sum_{y\in[M]}\Delta_{q(k_{i1}-k_{i0})}T_uf_0(qx-qy^2)\Delta_{q(k_{i1}-k_{i0})}T_uf_1(qx+y-qy^2)e(\psi(\ul{k})x)\right|\geq\gamma^{2^{2s-1}}\f{NM}{q}
\]
for every $\ul{k}\in H'$.

By Lemma~\ref{lem6.2}, for each $\ul{k}\in H'$ there exists a $t\ll\gamma^{-2^{4s}}$ such that $\|q^2t\psi(\ul{k})\|\leq \gamma^{-2^{5s}}/(N/q^3)$. By applying Lemma~\ref{lem6.5} with $C=\gamma^{-2^{7s}+2^{5s+1}}$, it follows that for each $\ul{k}\in H'$, there exist integers $a(\ul{k}),t(\ul{k})\ll \gamma^{-2^{4s}}$, $|m(\ul{k})|\leq \gamma^{-2^{7s}+2^{5s+1}}$, and $|\theta(\ul{k})|\leq 1$ such that
\[
q^2\psi(\ul{k})=\f{a(\ul{k})}{t(\ul{k})}+\f{m(\ul{k})\gamma^{-2^{5s}}}{\gamma^{-2^{7s}+2^{5s+1}}N/q^3}+\f{\theta(\ul{k})\gamma^{-2^{5s}}}{\gamma^{-2^{7s}+2^{5s+1}}N/q^3}.
\]
By the pigeonhole principle yet again, we can refine $H'$ to a subset $H''$ of $H'$ of size $|H''|\gg\gamma^{2^{7s}}(N/q)^{2(s-2)}$ for which there exist $a,t\ll\gamma^{-2^{4s}}$ and $|m|\leq \gamma^{-2^{7s}+2^{5s+1}}$ such that for any $\ul{k}\in H''$, we have
\[
\psi(\ul{k})=\f{a}{q^2t}+\f{m\gamma^{-2^{5s}}}{\gamma^{-2^{7s}+2^{5s+1}} N/q}+\f{\theta(\ul{k})\gamma^{-2^{5s}}}{\gamma^{-2^{7s}+2^{5s+1}}N/q},
\]
or, using the definition of $\psi$,
\[
(-1)^{s}\phi(k_{11},\dots,k_{(s-2)1}):=\sum_{\omega\in\{0,1\}^{s-2}\sm\{0\dots 0\}}(-1)^{|\omega|}\phi(k_{1\omega_1},\dots,k_{(s-2)\omega_{s-2}})+\f{a}{q^2t}+\f{(m+\theta(\ul{k}))\gamma^{-2^{5s}} }{\gamma^{-2^{7s}+2^{5s+1}}N/q}.
\]

Set
\[
\psi_{1}(\ul{k}):=(-1)^s\sum_{\substack{\omega\in\{0,1\}^{s-2}\sm\{0\dots 0\} \\ \omega_1=0}}(-1)^{|\omega|}\phi(k_{1\omega_1},\dots,k_{(s-2)\omega_{s-2}})+\f{a}{q^2t}+\f{m\gamma^{-2^{5s}}}{\gamma^{-2^{7s}+2^{5s+1}} N/q},
\]
and, for $i=2,\dots,s-2$, set
\[
\psi_{i}(\ul{k}):=(-1)^s\sum_{\substack{\omega\in\{0,1\}^{s-2}\sm\{0\dots 0\} \\ \omega_1=\dots=\omega_{s-3}=1 \\ \omega_m=0}}(-1)^{|\omega|}\phi(k_{1\omega_1},\dots,k_{(s-2)\omega_{s-2}}).
\]
These functions are defined so that $\psi_i$ does not depend on $k_{i1}$, and so that
\[
\phi(k_{11},\dots,k_{(s-2)1})=\sum_{i=1}^{s-2}\psi_i(\ul{k})\pm\f{\theta(\ul{k})\gamma^{-2^{5s}}}{\gamma^{-2^{7s}+2^{5s+1}}N/q}.
\]
For any $\ul{k}\in H''$, we thus have
\[
\left|\phi(k_{11},\dots,k_{(s-2)1})-\sum_{i=1}^{s-2}\psi_i(\ul{k})\right|\leq\f{\gamma^{2^{-5s}}}{\gamma^{-2^{7s}+2^{5s+1}}N/q}.
\]

By the pigeonhole principle again, there exist $h_1,\dots,h_{s-2}\in [N/q]$ such that the fiber
\[
H''':=\{(h_1',\dots,h_{s-2}')\in H:(h_1,\dots,h_{s-2},h_1',\dots,h_{s-2}')\in\square_{s-2}(H)\}
\]
has size $\gg\gamma^{2^{7s}}(N/q)^{s-2}$. Fix such $h_1,\dots,h_{s-2}$. Since
\[
\gamma^{2^{8s}}<\gamma^{2^{7s}}\cdot \left(\f{\gamma^{-2^{5s}}}{\gamma^{-2^{7s}+2^{5s+1}}}\right)^2=\gamma^{3\cdot 2^{7s}-3\cdot 2^{5s+1}}
\]
as $s\geq 3$, it follows that
\[
\sum_{(h_1',\dots,h_{s-2}')\in H'''}\left|\sum_{x}\Delta_{qh_1',\dots,qh_{s-2}'}T_uF(qx)e\left(\sum_{i=1}^m\phi_i(h_1',\dots,h_{s-2}')x\right)\right|^2\gg\gamma^{2^{8s}}(N/q)^{s},
\]
where, for each $i=1,\dots,s-2$, we have
\[
\phi_i(h_1',\dots,h_{s-2}'):=\psi_i(h_1,\dots,h_{s-2},h_1',\dots,h_{s-2}'),
\]
which does not depend on $h_i'$ by our definition of $\psi_i$. By positivity, we can extend the sum over $H'''$ to one over all of $[N/q]^{s-2}$. This yields
\[
\sum_{h_1',\dots,h_{s-2}'\in [N/q]}\left|\sum_{x}\Delta_{qh_1',\dots,qh_{s-2}'}T_uF(qx)e\left(\sum_{i=1}^{s-2}\phi_i(h_1',\dots,h_{s-2}')x\right)\right|^2\gg \gamma^{2^{8s}}(N/q)^{s}.
\]
Using Lemma~\ref{lem6.4}, we conclude that
\[
\|F\|_{U^{s-1}(u+q\Z)}^{2^{s-1}}\gg\gamma^{2^{9s}}(N/q)^{s}.
\]
\end{proof}
Note that the proof of Proposition~\ref{prop6.6} does not go through for $s=2$ because of the use of Lemma~\ref{lem6.4}, which only works for positive $m$.
\section{Local $U^1$-control and the density increment}\label{sec7}

In this section, we deduce a density increment from our general $U^1$-control result, Theorem~\ref{thm7.1}, which is the generalization of Lemma~\ref{lem3.1} needed to handle the progression $x,x+y,x+qy^2$ for arbitrary $q$. We then carry out the density increment argument, proving Theorem~\ref{thm1.1}.

\begin{theorem}[$U^1$-control]\label{thm7.1}
Let $f_0,f_1,f_2:\Z\to\C$ be $1$-bounded functions supported in the interval $[N]$, $q$ be a positive integer, and $\delta>0$. Set $M:=(N/q)^{1/2}$ and suppose that
\[
\left|\Lambda_q(f_0,f_1,f_2)\right|\geq\delta NM.
\]
Then there exist positive integers $q'\ll\delta^{-2^{151}}$ and $\delta^{2^{153}}M/q\ll N'\leq M$ such that
\[
\sum_{x}\left|\sum_{y\in[N']}f_1(x+qq'y)\right|\gg \delta^{2^{155}}NN',
\]
provided $N\gg q\delta^{-72}$.
\end{theorem}
\begin{proof}
Assume that $N\gg q\delta^{-72}$. Applying Theorem~\ref{thm5.2} and then Proposition~\ref{prop6.6} three times (for $s=5,4,$ and $3$), we deduce using the $U^2(u+q\Z)$-inverse theorem that, for at least a $\gg\delta^{2^{149}}$-proportion of $u\in[q]$, we have
\[
\left|\sum_{x}\sum_{y\in[M]}T_uf_0(qx)T_uf_1(qx+y)e(\beta_u [x+y^2])\right|\gg \delta^{2^{149}}\f{N}{q}M
\]
for some $\beta_u\in\T$. Then by applying Lemma~\ref{lem6.2} with $\gamma=\delta^{2^{149}}$ for each such $u\in[q]$, we get that there exists a positive integer $q'_u\ll \delta^{-2^{151}}$ such that $\|q^2q'_u\beta\|\ll\delta^{-2^{152}}/(N/q^3)$, and by applying Lemma~\ref{lem6.5} with $C=\delta^{-2^{153}}/C'$ and $C'>0$ sufficiently small, we have
\[
\beta_u=\f{a_u}{q^2q'_u}+k_u\f{\delta^{2^{152}}C'}{N/q}+\theta_u\f{\delta^{2^{152}}C'}{N/q}
\]
for some integer $|k_u|\leq \delta^{-2^{153}}/C'$ and $|\theta_u|\leq 1$. Pigeonholing in $a_u,q_u',$ and $k_u$, we deduce that there exist $a,q'\ll \delta^{-2^{151}}$ and $|k|\ll \delta^{-2^{153}}/C'$ such that for a $\gg C'\delta^{2^{154}}$ proportion of $u\in[q]$, we have
\[
\left|\sum_{x}\sum_{y\in[M]}T_uf_0(qx)T_uf_1(qx+y)e(\beta [x+y^2])\right|\gg \delta^{2^{149}}\f{N}{q}M
\]
for some $\beta\in\T$ satisfying $\left|\beta-\f{a}{q^2q'}-k\f{\delta^{2^{152}}C'}{N/q}\right|\leq\f{\delta^{2^{152}}C'}{N/q}$. As a consequence, by taking $C'$ sufficiently small, we get for such $u\in[q]$ that
\[
\left|\sum_{x}\sum_{y\in[M]}T_uf_0(qx)T_uf_1(qx+y)e(\beta x+[a/q^2q'+k\delta^{2^{152}}/(N/q)]y^2)\right|\gg \delta^{2^{149}}\f{N}{q}M.
\]
By splitting the sum over $y\in[M]$ in the above up into progressions modulo $qq'$ of length $N'\asymp \delta^{2^{153}}M/qq'$ and pigeonholing, we get that there exists a $b_u\in\Z$ such that
\[
\left|\sum_{x}\sum_{y\in[N']+b_u}T_uf_0(qx)e(\beta x)T_uf_1(qx+qq'y)\right|\gg \delta^{2^{153}}\f{N}{q}N',
\]
which, making the change of variables $x\mapsto x-q'b_u$ and using the triangle inequality, yields
\[
\sum_{x}\left|\sum_{y\in[N']}T_uf_1(qx+qq'y)\right|\gg \delta^{2^{153}}\f{N}{q}N'
\]
for a $\gg C'\delta^{2^{154}}$ proportion of $u\in[q]$. We conclude by positivity that
\[
\sum_{x}\left|\sum_{y\in[N']}f_1(x+qq'y)\right|\gg \delta^{2^{155}}NN'.
\]
\end{proof}
Theorem~\ref{thm7.1} has the following consequence, which is the main ingredient in the proof of Theorem~\ref{thm1.1}.
\begin{lemma}[Density increment]\label{lem7.2}
Let $q$ be a positive integer and set $M:=(N/q)^{1/2}$. Let $A\subset[N]$ have density $\alpha:=|A|/N$. If $A\subset [N]$ lacks nontrivial progressions of the form $x,x+y,x+qy^2$ and $N\gg q^2\alpha^{-2^{158}}$, then there exists $q'\ll\alpha^{-2^{153}}$ and $\alpha^{2^{155}}M/q\ll N'\leq M$ such that
\[
|A\cap(a+qq'\cdot[N'])|\geq\left(\alpha+\Omega(\alpha^{157})\right)N'
\]
for some $a\in[N]$.
\end{lemma}
\begin{proof}
Set $f_A:=1_A-\alpha 1_{[N]}$. Then $\Lambda_q(1_A)=0$, since the only progressions $x,x+y,x+qy^2$ in $A$ are the trivial ones. On the other hand, using the trilinearity of $\Lambda_q$ and the decomposition $1_A=f_A+\alpha 1_{[N]}$, the quantity $\Lambda_q(1_A)$ is equal to
\begin{equation}\label{eq7.1}
\alpha^3\Lambda_q(1_{[N]})+\alpha^2\Lambda_q(f_A,1_{[N]},1_{[N]})+\alpha\Lambda_q(1_A,1_{[N]},f_A)+\Lambda_q(1_A,f_A,1_A).
\end{equation}

Now assume that $N\gg q^2\alpha^{-2^{158}}$. One can easily verify that $\Lambda_q(1_{[N]})\geq\f{1}{8}NM$ when the implied constant in the lower bound for $N$ is large enough, so that, since~\eqref{eq7.1} equals zero, one of the following must hold:
\begin{enumerate}
\item $|\Lambda_q(f_A,1_{[N]},1_{[N]})|\gg\alpha NM$,
\item $|\Lambda_q(1_A,1_{[N]}, f_A)|\gg\alpha^2 NM$, or
\item $|\Lambda_q(1_A,f_A,1_A)|\gg\alpha^3 NM$.
\end{enumerate}
We claim that each of these possibilities leads to the conclusion of the lemma.

In the second case, when $|\Lambda_q(1_A,1_{[N]},f_A)|\gg\alpha^2 NM$, this follows from the Fourier-analytic proof of S\'ark\"ozy's theorem (with better bounds on $q'$ and $N'$). See, for instance,~\cite{LM}. The first case, when $|\Lambda_q(f_A,1_{[N]},1_{[N]})|\gg\alpha NM$, is even simpler.

In the third case, when $|\Lambda_q(1_A,f_A,1_A)|\gg\alpha^3 NM$, we apply Theorem~\ref{thm7.1} to deduce that there exist positive integers $q'\ll\alpha^{-2^{153}}$ and $\alpha^{2^{155}}M/q\ll N'\leq M$ such that
\[
\sum_{x}\left|\sum_{y\in[N']}f_A(x+qq'y)\right|\gg\alpha^{2^{157}}NN',
\]
as $1_A$ and $f_A$ are $1$-bounded and supported on $[N]$. Since $f_A$ has mean zero, we may add $0=\sum_x\sum_{y\in[N']}f_A(x+qq'y)$ to both sides of the above inequality to get that
\[
\sum_x\max\big(0,\sum_{y\in[N']}f_A(x+qq'y)\big)\gg\alpha^{2^{157}} NN'.
\]
Let $X$ consist of those $x$ for which $x+qq'[N']\subset [N]$. The number of $x\notin X$ for which $(x+qq'[N'])\cap[N]\neq\emptyset$ is at most $2qq'N'$. Hence,
\[
\sum_x\max\big(0,\sum_{y\in[N']}f_A(x+qq'y)\big)\gg\alpha^{2^{157}} NN'-O(qq'(N')^2).
\]
The right-hand side of the above is $\gg \alpha^{2^{157}} NN'-O(q'N)$ by the upper bound $N'\leq M$, and thus by assuming that $N\gg q^2\alpha^{-2^{158}}$ we may ensure that $\alpha^{2^{157}} NN'-O(q'N)\gg\alpha^{2^{157}}NN'$. Hence, by the pigeonhole principle, there exists an $a\in X\subset[N]$ such that
\[
\sum_{y\in[N']}f_A(a+qq'y)\gg\alpha^{2^{157}}N'.
\]
Recalling that $f_A=1_A-\alpha 1_{[N]}$, this gives the conclusion of the lemma.
\end{proof}

We can now carry out the density increment argument.

\begin{proof}[Proof of Theorem~\ref{thm1.1}]
Note first that if $B\subset[N]$ lacks nontrivial progressions of the form $x,x+y,x+qy^2$, then the set $\{n\in[N']:a+qq'n\in B\}$ lacks nontrivial progressions of the form $x,x+y,x+q^2q'y^2$.

Now suppose that $A\subset[N]$ has density $\alpha$ and lacks nontrivial progressions of the form~\eqref{eq1.2}. Setting $A_0:= A$, $N_0:= N$, $\alpha_0:=\alpha$, and $q_0:=1$, if each $N_i$ is large enough then we can repeatedly apply Lemma~\ref{lem7.2} to obtain a sequence of four-tuples $(A_i,N_i,\alpha_i,q_i)$ satisfying the following for some absolute constants $c,C>0$:
\begin{enumerate}
\item $A_i\subset[N_i]$ with $|A_i|\geq(\alpha_{i-1}+\Omega(\alpha_{i-1}^{2^{157}}))N_i$,
\item $N_i\geq c\alpha^{2^{155}}(N_{i-1}/q_{i-1})^{1/2}/q_{i-1}$,
\item $q_i\leq C\alpha^{-2^{153}}$,
\item and $A_i$ lacks nontrivial configurations of the form
\[
x,x+y,x+q_0^{2^i}q_1^{2^{i-1}}\cdots q_{i-1}^2q_iy^2.
\]
\end{enumerate}
This iteration must terminate at some $i\ll\alpha^{-2^{157}}$, for otherwise we obtain a density exceeding $1$. Hence, at this point the largeness assumption on $N_i$ in Lemma~\ref{lem7.2} must fail, so that
\[
N_i\ll\alpha^{-2^{158}}(q_0^{2^i}q_1^{2^{i-1}}\cdots q_{i-1}^2q_i)^{2}\ll (C\alpha^{-2^{158}})^{2^{i+1}}.
\]
On the other hand, we also have the lower bound
\begin{align*}
N_i & \gg\alpha^{2^{155}}(N_{i-1}/q_{i-1})^{1/2}/q_{i-1} \\
& \gg(c\alpha^{2^{155}})^{1+1/2+\dots+1/2^{i-1}}q_{i-1}^{-3/2}q_{i-2}^{-1/2(3/2)}\cdots q_0^{-1/2^{i-1}(3/2)}N^{1/2^i} \\
&\gg \alpha^{2^{157}}N^{1/2^i},
\end{align*}
by the upper bound on the $q_i$'s. Comparing our upper and lower bounds for $N_i$ thus gives $N\ll (C\alpha^{-2^{158}})^{2^{2i+2}}$ for some $i\ll \alpha^{-2^{157}}$. Taking a double logarithm then gives the bound in Theorem~\ref{thm1.1}.
\end{proof}