# Corners with polynomial side length

Noah Kravitz, Borys Kuca, James Leng  Department of Mathematics, Princeton
University, Princeton, NJ 08540, USA<EMAIL_ADDRESS>Faculty of
Mathematics and Computer Science, Jagiellonian University, 30-348 Kraków,
Poland<EMAIL_ADDRESS>Department of Mathematics, UCLA, Los Angeles, CA
90095, USA<EMAIL_ADDRESS>
###### Abstract.

A _$P$ -polynomial corner_, for $P\in\mathbb{Z}[z]$ a polynomial, is a triple
of points $(x,y),\;(x+P(z),y),\;(x,y+P(z))$ for $x,y,z\in\mathbb{Z}$. In the
case where $P$ has an integer root of multiplicity $1$, we show that if
$A\subseteq[N]^{2}$ does not contain any nontrivial $P$-polynomial corners,
then

$|A|\ll_{P}\frac{N^{2}}{(\log\log\log N)^{c}}$

for some absolute constant $c>0$. This simultaneously generalizes a result of
Shkredov about corner-free sets and a recent result of Peluse, Sah, and
Sawhney about sets without $3$-term arithmetic progressions of common
difference $z^{2}-1$. The main ingredients in our proof are a multidimensional
quantitative concatenation result from our companion paper [16] and a novel
degree-lowering argument for box norms.

##  1\. Introduction

In recent years, there has been a surge of interest in obtaining “reasonable”
upper bounds for the Polynomial Szemerédi Theorem of Bergelson and Leibman
[2]. This theorem asserts that if
$\mathbf{P}_{1},\ldots,\mathbf{P}_{\ell}\in{\mathbb{Z}}^{D}[z]$ are
polynomials satisfying some mild local conditions, then every subset of
${\mathbb{Z}}^{D}$ with upper positive Banach density must contain a
(nontrivial) occurrence of the polynomial progression

${\textbf{x}},\;{\textbf{x}}+\mathbf{P}_{1}(z),\;\ldots,\;{\textbf{x}}+\mathbf{P}_{\ell}(z).$

This result provided a unified proof for several earlier results in arithmetic
Ramsey theory over ${\mathbb{Z}}$, including Roth’s pioneering theorem [36] on
sets avoiding $3$-term arithmetic progressions, Szemerédi’s later
generalization [42] to sets avoiding $\ell$-term arithmetic progressions for
arbitrary fixed $\ell\geq 3$, and work of Sárközy [37, 38] and Furstenberg [6]
(independently) on sets avoiding length-$2$ polynomial progressions.

The Polynomial Szemerédi Theorem, despite its useful generality, comes with a
drawback: Because the proof uses methods from ergodic theory, the result is
ineffective and provides no bounds on sets avoiding polynomial progressions.
Roth and Sárközy proved their theorems with fairly good bounds. Szemerédi
provided bounds of tower-type which, although strictly-speaking “effective”,
are not particularly “reasonable”. The work of Gowers on obtaining improved
bounds for Szemerédi’s Theorem [7, 8] gave birth to the field of higher-order
Fourier analysis, and since then there has been substantial work on obtaining
quantitative versions of various instances of the Polynomial Szemerédi
Theorem.

Of particular interest is an early result due to Shkredov [39, 40], who
obtained reasonable bounds for subsets of $[N]^{2}$ avoiding the “corner”
configuration

$(x,y),\;(x+z,y),\;(x,y+z).$

His argument involved a suitable notion of “pseudorandom sets” with which one
can run a modification of Roth’s original density-increment strategy.
Shkredov’s approach was later simplified by Green [9, 10] for corner-free
subsets of $\mathbb{F}_{p}^{D}\times\mathbb{F}_{p}^{D}$; see also the work of
Lacey and McClain [20] for an improvement in
$\mathbb{F}_{2}^{D}\times\mathbb{F}_{2}^{D}$. Peluse’s recent work on subsets
of ${\mathbb{F}}_{p}^{D}\times{\mathbb{F}}_{p}^{D}$ avoiding the “$L$-shaped
configuration” $(x,y),\;(x+z,y),\;(x,y+z),\;(x,y+2z)$ is an extension of
Shkredov’s approach.

Until recently, Shkredov’s work on corners was the only instance of a
“reasonable bound” for a multidimensional configuration over the integers. Our
main result is a polynomial extension of Shkredov’s theorem.

######  Theorem 1.1.

Let $P\in\mathbb{Z}[z]$ be a polynomial with an integer root of multiplicity
$1$. If $A\subseteq[N]^{2}$ does not contain a configuration of the form
$(x,y),\;(x+P(z),y),\;(x,y+P(z))$ with $P(z)\neq 0$, then

$|A|\ll_{P}\frac{N^{2}}{(\log\log\log N)^{c}}$

for some absolute constant $c>0$.

Theorem 1.1 and the concurrently released work of Peluse, Prendiville and Shao
[33] on the configuration $(x,y),\;(x+z,\;y),\;(x,\;y+z^{2})$ provide the
first examples of reasonable bounds for multidimensional polynomial (i.e.,
non-linear) progressions over the integers.

Using a calculation of Shkredov [39], we can take any $c<1/73$. The reader may
notice that our statement has an artificial-looking constraint on the
polynomial $P$. This constraint, which is slightly stronger than
intersectivity, arises from a technical point related to the use of the
$W$-trick, as discussed later.

A key analytic step in our argument is the following inverse theorem for
polynomial corners, which may be of independent interest.

######  Theorem 1.2 (Inverse theorem for polynomial corners).

Let $d\in{\mathbb{N}}$, let $P\in{\mathbb{Z}}[z]$ be a degree-$d$ polynomial
with leading coefficient $\beta_{d}$, let $\delta\in(0,1/10)$, and let
$f_{0},f_{1},f_{2}:{\mathbb{Z}}^{2}\to\mathbb{C}$ be $1$-bounded functions
supported on $[N]^{2}$ for some integer
$N\geq\exp(\log(1/\delta)^{\Omega_{P}(1)})$. If

$\mathopen{}\left|\sum_{x,y}\operatorname*{\mathbb{E}}_{z\in[(N/\beta_{d})^{1/d}]}f_{0}(x,y)f_{1}(x+P(z),y)f_{2}(x,y+P(z))\mathclose{}\right|\geq\delta
N^{2},$

then

$\displaystyle\sum_{x,y}f_{0}(x,y)b_{1}(x)b_{2}(y)\geq\exp(-\log(1/\delta)^{O_{P}(1)})N^{2},\quad\text{for
some $1$-bounded $b_{1},b_{2}:{\mathbb{Z}}\to{\mathbb{C}}$},$
$\displaystyle\sum_{x,y}f_{1}(x,y)b_{1}(x+y)b_{2}(y)\geq\exp(-\log(1/\delta)^{O_{P}(1)})N^{2}\quad\text{for
some $1$-bounded $b_{1},b_{2}:{\mathbb{Z}}\to{\mathbb{C}}$},$
$\displaystyle\sum_{x,y}f_{2}(x,y)b_{1}(x)b_{2}(x+y)\geq\exp(-\log(1/\delta)^{O_{P}(1)})N^{2}\quad\text{for
some $1$-bounded $b_{1},b_{2}:{\mathbb{Z}}\to{\mathbb{C}}$}.$

In the proof of Theorem 1.1, we will end up using a slightly different version
of this inverse theorem that is better suited to $W$-tricks (Theorem 4.1); the
proof simplifies in several ways for the $W$-trick-free version stated here.
Theorem 4.1 leads to a “comparison theorem” with a “model” counting operator
(Theorem 7.2), which in Section 7 we will use to deduce the following
improvement on the result of Peluse, Sah, and Sawhney [34].

######  Corollary 1.3.

Let $P\in\mathbb{Z}[z]$ be a polynomial with an integer root of multiplicity
$1$. If $A\subseteq[N]$ does not contain a configuration of the form
$x,\;x+P(z),\;x+2P(z)$ with $P(z)\neq 0$, then

$|A|\ll\frac{N}{\exp((\log\log N)^{c_{P}})}$

for some constant $c_{P}>0$.

Before we say more about our main theorem, let us briefly survey related
results. Previous work has focused on $1$-dimensional polynomial progressions
over the integers and both $1$-dimensional and multidimensional polynomial
progressions in finite-field settings. One of the many important differences
between the integers and finite fields is that for a fixed polynomial
$P\in{\mathbb{Z}}[z]$ of degree at least $2$, the image of $P$ is an
equidistributed set of positive density in (a sequence of) finite fields,
while in the integers it is a sparse set with local biases; since there are
more “opportunities” to find polynomial progressions in finite fields
$\mathbb{F}_{p}$, it is generally easier to prove bounds on the sizes of sets
avoiding polynomial progressions in finite-field settings, and much more is
known here than over the integers.

Early results for $1$-dimensional polynomial progressions in $\mathbb{F}_{p}$
($p$ a prime) are due to Bourgain and Chang [3], Dong, Li, and Sawin [5], and
Peluse [28]. In a major breakthrough, Peluse [29] proved power-saving upper
bounds for subsets of $\mathbb{F}_{p}$ avoiding the polynomial progression

$x,\;x+P_{1}(z),\;\ldots,\;x+P_{\ell}(z)$

for any given linearly independent polynomials
$P_{1},\ldots,P_{m}\in{\mathbb{Z}}[z]$ with constant coefficients all zero.
Her proof introduced the now-well-used technique of degree-lowering for Gowers
norms. Peluse’s work has been generalized in several ways. For instance, the
second author [17] proved reasonable upper bounds for subsets of
$\mathbb{F}_{p}$ avoiding a given progression of the form

$(x,\;x+z,\;\dots,\;x+(\ell-1)z,\;x+z^{\ell},\;\dots,\;x+z^{\ell+k-1}).$

In [23], the third author used a $U^{3}$-version of degree-lowering to obtain
reasonable upper bounds for a large family of so-called “complexity-$1$”
polynomial configurations. Lastly, Bergelson and Best [1] generalized Peluse’s
result to general finite commutative rings.

Less is known about multidimensional progressions in finite fields. Regarding
linear configurations, we have already mentioned results on corners and
L-shaped configurations. In the higher-degree case, the second author [18, 19]
proved a general Szemerédi-type theorem for patterns of the form

${\textbf{x}},\;{\textbf{x}}+{\textbf{v}}_{1}P_{1}(z),\;\dots,\;{\textbf{x}}+{\textbf{v}}_{\ell}P_{\ell}(z),$

where $P_{1},\dots,P_{\ell}$ are linearly independent polynomials with
constant coefficients all zero and
${\textbf{v}}_{1},\ldots,{\textbf{v}}_{\ell}$ are arbitrary vectors in
$\mathbb{F}_{p}^{D}$. When $\ell=2$, special cases of this result had been
established earlier by Han, Lacey, and Yang [13].

Let us now turn to polynomial progressions in ${\mathbb{Z}}$. In a sequence of
papers [29, 31, 32], Peluse and Prendiville adapted Peluse’s original degree-
lowering argument for progressions of the form
$x,\;x+P_{1}(z),\;\ldots,\;x+P_{m}(z)$ where the polynomials $P_{i}$ have
distinct degrees. Prendiville [35] also proved reasonable bounds for sets
avoiding arithmetic progressions with common difference of the form $z^{d}$
for fixed $d$; the homogeneity of the polynomial $z^{d}$ allowed him to use a
density-increment argument. Peluse, Sah, and Sawhney [34], adapting a
$U^{3}$-degree-lowering argument developed in [23], addressed the case of
three-term arithmetic progressions with common difference $z^{2}-1$. They
proved a “transference” result relating the number of $3$-term arithmetic
progressions to the number of $3$-term arithmetic progressions with common
difference $z^{2}-1$.

By a simple projection argument (see the proof of Corollary 1.3 below),
Theorem 1.1 contains the setting studied by Peluse, Sah, and Sawhney as a
special case. Hence, our main theorem can be understood as a common
generalization of Shkredov’s corners theorem and the result of Peluse, Sah,
and Sawhney. To prove Theorem 1.1, we will establish a transference result for
corners, in the style of [34], and then use Shkredov’s work as a black box.
The starting point for our argument is a PET and quantitative concatenation
result carried out in our companion paper [16]. The bulk of the present paper
is devoted to obtaining degree-lowering for the polynomial corners
configuration. Our degree-lowering argument is the first to use box norms
instead of Gowers norms, and its success attests to the robustness of degree-
lowering as a tool in arithmetic combinatorics.

###  1.1. Future directions

Our results and methods suggest several avenues for future inquiry. The most
natural open problem is extending Theorem 1.1 to a larger class of polynomials
$P$. A particularly appealing example, recently highlighted by Peluse [27,
Problem 3.17], is $P(z)=z^{2}$. (Theorem 1.1 fails to cover $P(z)=z^{2}$
because $0$, the only integer root, has multiplicity $2>1$.) One strategy,
which we attempted initially before turning to transference arguments, is
obtaining $U^{1}\times U^{1}$-control for the $P$-polynomial corner counting
operator and then running Shkredov’s original density-increment argument for
corners. Our degree-lowering argument goes through with $\widetilde{P}$
replaced by an arbitrary (non-$W$-tricked) polynomial $P\in\mathbb{Z}[z]$,
which gives the norm-control necessary for starting Shkredov’s iterative
argument. The pitfall of this approach, however, is that in later stages of
the iteration one must deal with subsets of pseudorandom sets rather than
subsets of $[N]^{2}$, and this creates complications in both the arguments of
this paper and the PET and concatenation results of our companion paper [16].
It seems possible that one could generalize our arguments to the setting of
pseudorandom sets as in [39, 40], but we have not pursued this.

The polynomial progressions investigated in this paper belong to the class of
linear patterns (in our case, corners) with polynomial differences. Other
works on obtaining bounds for such configurations have proceeded either by
modifying arguments for the corresponding linear patterns (as in, e.g., [35])
or by using transference results to relate the counts of linear and polynomial
patterns (as in the present work and [17, 34]). Reasonable bounds are known
for $L$-shaped configurations and arithmetic progressions of length $\ell\geq
4$, but their polynomial analogues are currently unknown, so it would be
interesting to extend our methods to establish transference results for these
two particular configurations. It would also be interesting to use this
machinery to obtain more general transference principles, even for cases where
there are not currently reasonable bounds for linear configurations.

###  1.2. Acknowledgments

NK was supported in part by the NSF Graduate Research Fellowship Program under
grant DGE–203965. BK is supported by the NCN Polonez Bis 3 grant No.
2022/47/P/ST1/00854 (H2020 MSCA GA No. 945339). For the initial stages of the
project, BK was supported by the ELIDEK grant No: 1684. JL is suppored by the
NSF Graduate Research Fellowship Grant No. DGE-2034835.

We would like to thank Terry Tao, Sarah Peluse, and Mehtaab Sawhney for
helpful discussions and for comments on a draft of this paper.

##  2\. Proof strategy

We now give an overview of the proof of Theorem 1.1. Our overarching goal is
to relate the number of polynomial corners to the number of ordinary corners;
once this is accomplished, we can “transfer” Shkredov’s result (in a standard
supersaturation version) from ordinary corners to polynomial corners.

Let $A\subseteq[N]^{2}$ be a set of density $\delta$, and let
$P\in\mathbb{Z}[z]$ be a polynomial of degree $d$ with an integer root $\rho$
of multiplicity $1$. Then

$P(z-\rho)=\beta_{d}z^{d}+\cdots+\beta_{1}z$

for some $\beta_{1},\ldots,\;\beta_{d}\in{\mathbb{Z}}$ with
$\beta_{1},\;\beta_{d}\neq 0$; without loss of generality we may assume that
$\beta_{d}>0$. The number of corners in $A$ is
$N\Lambda^{\operatorname{Corners}}(1_{A},1_{A},1_{A})$, where
$\Lambda^{\operatorname{Corners}}$ is the normalized corner-counting operator
at scale $N$ given by

$\Lambda^{\operatorname{Corners}}(f_{0},f_{1},f_{2}):=\sum_{x,y\in{\mathbb{Z}}}\operatorname*{\mathbb{E}}_{z\in[N]}f_{0}(x,y)f_{1}(x+z,y),f_{2}(x,y+z).$

The number of $P$-polynomial corners in $A$ is

$(N/\beta_{d})^{1/d}\Lambda(1_{A},1_{A},1_{A}),$

where $\Lambda$ is the normalized $P$-polynomial corner-counting operator at
scale $N$ given by

$\Lambda(f_{0},f_{1},f_{2}):=\sum_{x,y\in\mathbb{Z}}\operatorname*{\mathbb{E}}_{z\in[(N/\beta_{d})^{1/d}]}f_{0}(x,y)f_{1}(x+P(z),y)f_{2}(x,y+P(z)).$

In order to show that $|\Lambda^{\operatorname{Corners}}-\Lambda|$ is small,
we must make both an Archimedean and a non-Archimedean modification.

First, since the set $\\{P(z):z\in{\mathbb{N}}\\}$ becomes sparser at larger
scales, we introduce a similarly-decaying weight

$\nu(z):=d^{-1}1_{[N]}(z)(N/(z+1))^{(d-1)/d}.$

into $\Lambda^{\operatorname{Corners}}$ to obtain the model corner-counting
operator

$\Lambda^{{\mathrm{Model}}}(f_{0},f_{1},f_{2}):=\sum_{x,y\in\mathbb{Z}}\operatorname*{\mathbb{E}}_{z\in[N]}f_{0}(x,y)f_{1}(x+z,y)f_{2}(x,y+z)\nu(z).$

Second, since the set $\\{P(z):z\in{\mathbb{N}}\\}$ may be biased with respect
to small moduli, we “pre-sieve” the set $A$ before attempting to compare the
counts of corners and of $P$-polynomial corners. More precisely, for $W$ a
very slowly-growing function of $N$, we restrict our attention to the elements
of $A$ lying in a single coset of $(\beta_{1}^{2}W{\mathbb{Z}})^{2}$; by the
pigeonhole principle, there is some such coset
$(b_{1}+\beta_{1}^{2}W{\mathbb{Z}})\times(b_{2}+\beta_{1}^{2}W{\mathbb{Z}})$
in which $A$ has relative density at least $\delta$ (at scale $N$). Let

$A^{\prime}:=\\{(x^{\prime},y^{\prime})\in{\mathbb{Z}}^{2}:(\beta_{1}^{2}Wx^{\prime}+b_{1},\;\beta_{1}^{2}Wy^{\prime}+b_{2})\in
A\\}\subseteq[N/(\beta_{1}^{2}W)]^{2}$

be this “slice” of $A$. We claim that in order to find a $P$-polynomial corner
in $A$, it suffices to find a $\widetilde{P}$-polynomial corner in
$A^{\prime}$, where $\widetilde{P}$ is the _$W$ -tricked_ auxiliary polynomial

(1)
$\displaystyle\widetilde{P}(z):=\frac{P(\beta_{1}Wz-\rho)}{\beta_{1}^{2}W}=\beta_{d}\beta_{1}^{d-2}W^{d-1}z^{d}+\beta_{d-1}\beta_{1}^{d-3}W^{d-2}z^{d-1}+\cdots+z\in\mathbb{Z}[z].$

(The linear coefficient $1$ of $\widetilde{P}$ will be convenient later for
technical reasons.) Indeed, if

$(x^{\prime},y^{\prime}),\;(x^{\prime}+\widetilde{P}(z^{\prime}),y^{\prime}),\;(x^{\prime},y^{\prime}+\widetilde{P}(z^{\prime}))$

form a $\widetilde{P}$-polynomial corner in $A^{\prime}$, then $A$ contains
the $P$-polynomial corner

$(x,y),\;(x+P(z),y),\;(x,y+P(z))$

with

$x:=\beta_{1}^{2}Wx^{\prime}+b_{1},\quad
y:=\beta_{1}^{2}Wy^{\prime}+b_{2},\quad\text{and}\quad
z:=\beta_{1}Wz^{\prime}-\rho.$

Hence, we replace $\Lambda$ with the _$W$ -tricked counting operator_

$\displaystyle\Lambda^{W}(f_{0},f_{1},f_{2}):=\sum_{x,y}\operatorname*{\mathbb{E}}_{z\in[(N/W_{d})^{1/d}]}f_{0}(x,y)f_{1}(x+\widetilde{P}(z),y)f_{2}(x,y+\widetilde{P}(z)),$

where $W_{d}:=\beta_{d}\beta_{1}^{d-2}W^{d-1}$ is the leading coefficient of
$\widetilde{P}$. The main work of this paper is showing that, with these
modifications made, the counting operators $\Lambda^{{\mathrm{Model}}}$ and
$\Lambda^{W}$ are very close (Proposition 7.2).

This comparison theorem boils down to showing that both
$\Lambda^{{\mathrm{Model}}}$ and $\Lambda^{W}$ are “controlled” by appropriate
$U^{1}\times U^{1}$-box norms of their arguments. The control for
$\Lambda^{{\mathrm{Model}}}$ (Proposition 7.1) is fairly straightforward and
follows from an argument similar to the proof of [34, Lemma 4.1], so we will
focus on the control for $\Lambda^{W}$. We wish to show that for all
$1$-bounded functions $f_{0},f_{1},f_{2}$ supported on $[N]^{2}$, the
largeness of $|\Lambda^{W}(f_{0},f_{1},f_{2})|$ implies (with quantitative
control) the largeness of a box norm of $f_{0}$ in the directions
${\mathbf{e}}_{1}:=(1,0)$ and ${\mathbf{e}}_{2}:=(0,1)$. The control in terms
of $f_{1}$ (with the directions
${\mathbf{e}}_{1},\;{\mathbf{e}}_{1}-{\mathbf{e}}_{2}$) and $f_{2}$ (with the
directions ${\mathbf{e}}_{2},\;{\mathbf{e}}_{2}-{\mathbf{e}}_{1}$) is
completely symmetrical. The precise statement of this result is in Theorem
4.1, which constitutes a $W$-tricked version of Theorem 1.2.

The starting point of this endeavor is the PET induction scheme and a
quantitative concatenation result, as carried out in our companion paper [16].
The output of these arguments is the existence of a natural number
$t=O_{d}(1)$ such that the lower bound
$|\Lambda^{W}(f_{0},f_{1},f_{2})|\geq\delta N^{2}$ implies that

(2) $\|f_{0}\|_{({\mathbf{e}}_{1}W_{d}\cdot[\pm
N/W_{d}])^{t},\;({\mathbf{e}}_{2}W_{d}\cdot[\pm
N/W_{d}])^{t}}^{2^{2t}}\gg_{d}\delta^{O_{d}(1)}N^{2},$

and likewise for $f_{1},f_{2}$ (cf. Proposition 4.2). For simplicity of
exposition, we will temporarily pretend that $W=1$; at the end of this sketch,
we will mention how to deal with the additional technical complications
arising from the presence of $W$. For notational simplicity, we will also make
the unimportant assumption that $\beta_{d}=\beta_{1}=1$ (so that $W_{d}=1$ and
the $z$-variable ranges over $[N^{1/d}]$ in the definition of $\Lambda^{W}$).

In order to replace $t$ with $1$, we will carry out an iterative degree-
lowering procedure (see Proposition 4.3 below): We will show that if the
largeness of $|\Lambda^{W}(f_{0},f_{1},f_{2})|$ is already known to imply the
largeness of $\|f_{0}\|_{({\mathbf{e}}_{1}\cdot[\pm
N])^{k},\;({\mathbf{e}}_{2}\cdot[\pm N])^{\ell}}^{2^{k+\ell}}$ for some
$k,\ell$ with $k\geq 2$, then it also implies the largeness of
$\|f_{0}\|_{({\mathbf{e}}_{1}\cdot[\pm N])^{k-1},\;({\mathbf{e}}_{2}\cdot[\pm
N])^{\ell}}^{2^{k+\ell-1}}$ (and likewise with the roles of $k,\ell$
reversed). We will arrive at our goal after $2t-2$ iterations of this degree-
lowering procedure. This is the first time that degree-lowering has been
carried out using box norms; all previous degree-lowering arguments in the
literature aim at lowering degrees of Gowers norms. Our argument thus
testifies to the versatility of the degree-lowering approach pioneered by
Peluse [29].

By the dual–difference interchange (a consequence of the Cauchy–Schwarz
inequality; see Lemma 3.6), it suffices to obtain our degree-lowering result
when $k=2$ and $\ell=1$. Suppose that
$|\Lambda^{W}(f_{0},f_{1},f_{2})|\geq\delta N^{2}$. We begin by applying the
“stashing”111The name for this trick is due to Manners [25]. trick: Since
$f_{0}$ is supported on $[N]^{2}$, using the Cauchy–Schwarz inequality to
eliminate $f_{0}$ from $\Lambda^{W}$ gives

$\delta^{2}N^{4}\leq\mathopen{}\left|\Lambda^{W}(f_{0},f_{1},f_{2})\mathclose{}\right|^{2}\leq
N^{2}\Lambda^{W}(\mathcal{D}_{0}(f_{1},f_{2}),f_{1},f_{2}),$

where $\mathcal{D}_{0}(f_{1},f_{2}):\mathbb{Z}^{2}\to\mathbb{C}$, the _dual
function_ of the first argument of $\Lambda^{W}$, is given by

$\mathcal{D}_{0}(f_{1},f_{2})(x,y):=\operatorname*{\mathbb{E}}_{z\in[N^{1/d}]}f_{1}(x+\widetilde{P}(z),y)f_{2}(x,y+\widetilde{P}(z)).$

The hypothesis of the degree-lowering statement tells us that

$\left\|\mathcal{D}_{0}(f_{1},f_{2})\right\|_{{\mathbf{e}}_{1}\cdot[\pm
N],\;{\mathbf{e}}_{1}\cdot[\pm N],\;{\mathbf{e}}_{2}\cdot[\pm N]}^{8}$

is large (i.e., at least $c(\delta)N^{2}$ for some explicit $c(\delta)>0$).
Then the inverse theorem for the $U^{2}\times U^{1}$-norm (see Lemma A.8
below) implies that $\mathcal{D}_{0}(f_{1},f_{2})$ correlates with a
“$U^{2}\times U^{1}$-obstruction” of the form $g(x)e(a(y)x+b(y))$, where
$g:{\mathbb{Z}}\to{\mathbb{C}}$ is a $1$-bounded function,
$a:{\mathbb{Z}}\to{\mathbb{R}}/{\mathbb{Z}}$ is a phase, and
$b:{\mathbb{Z}}\to{\mathbb{R}}/{\mathbb{Z}}$ is a shift.222To understand where
this inverse theorem comes from, notice that differentiating once in the
$y$-direction removes the $g(x)$ term and differentiating twice in the
$x$-direction removes the $e(a(y)x+b(y))$ term. Unraveling the definition of
$\mathcal{D}_{0}(f_{1},f_{2})$ and ignoring the terms $g(x),b(y)$ (which are
of secondary importance), we find that

$\Lambda^{\prime}(a,f_{1},f_{2}):=\sum_{x,y}\operatorname*{\mathbb{E}}_{z\in[N^{1/d}]}e(a(y)x)f_{1}(x+\widetilde{P}(z),y)f_{2}(x,y+\widetilde{P}(z))$

is large in absolute value.

We now aim to show that the phase $a$ is close to some constant $\alpha$ for
many values of $y$ (see Proposition 4.4 below); this step “lowers” the
degree-$2$ obstruction $e(a(y)x)$ to the degree-$1$ obstruction $e(\alpha x)$.
Before sketching the proof of this structural result for $a$, let us see how
to use it to complete the degree-lowering procedure. Substituting $\alpha$ for
$a(y)$ and shifting $x\mapsto x-\widetilde{P}(z)$ in the expression for
$\Lambda^{\prime}(a,f_{1},f_{2})$, we find that

$\sum_{x,y}\operatorname*{\mathbb{E}}_{z\in[N^{1/d}]}e(\alpha(x-\widetilde{P}(z))f_{1}(x,y)f_{2}(x-\widetilde{P}(z),y+\widetilde{P}(z))$

is large. Grouping the exponential with $f_{2}$, we recognize this expression
as an instance of the counting operator for the $2$-point configuration
$(x,y),\;(x-\widetilde{P}(z),y+\widetilde{P}(z))$. Adapting a classical
Fourier-analytic argument of Sárközy [37, 38] for $2$-point polynomial
configurations, we conclude that

$\left\|f_{1}\right\|_{({\mathbf{e}}_{2}-{\mathbf{e}}_{1})\cdot[\pm
N],\;{\mathbf{e}}_{2}\cdot[\pm N]}^{4}$

is large. A further sequence of manipulations in the flavor of stashing let us
transfer this “degree-$2$ control” from $f_{1}$ back to $f_{0}$.

It remains to analyze the phase function $a$. It turns out that it suffices to
understand the case where $f_{2}$ is a “$U^{1}\times U^{1}$-obstruction” of
the form $b_{1}(y)b_{2}(x+y)$ for some $1$-bounded functions
$b_{1},b_{2}:{\mathbb{Z}}\to{\mathbb{C}}$, in which case we are dealing with
the expression

$\displaystyle\sum_{x,y}\operatorname*{\mathbb{E}}_{z\in[N^{1/d}]}e(a(y)x)f_{1}(x+\widetilde{P}(z),y)b_{1}(y+\widetilde{P}(z))b_{2}(x+y+\widetilde{P}(z)).$

Shifting $x\mapsto x-\widetilde{P}(z)$, we reach an expression in which the
functions $f_{1}$ and $b_{2}$ are independent of $z$. Then, by applying the
triangle inequality in $x,y$ and pigeonholing in $x$, we deduce that

$\displaystyle\sum_{y\in[N]}\mathopen{}\left|\operatorname*{\mathbb{E}}_{z\in[N^{1/d}]}e(-a(y)\widetilde{P}(z))b_{1}(y+\widetilde{P}(z))\mathclose{}\right|$

is large. A variant of the PET argument from our companion paper [16] lets us
control this expression by a Gowers norm of $b_{1}$, and the inverse theorem
for the Gowers norms produces a nilsequence $\varphi$ of bounded degree,
dimension, and complexity such that

(3)
$\sum_{y\in[N]}\mathopen{}\left|\operatorname*{\mathbb{E}}_{z\in[N^{1/d}]}e(a(y)\widetilde{P}(z))\varphi(y+\widetilde{P}(z))\mathclose{}\right|$

is large. To analyze (3), we require input from the theory of nilsequences.

We use an iterative process, itself a microcosm of degree-lowering, to show
that the nilsequence in (3) can be replaced by nilsequences of progressively
smaller step (see Proposition 6.2). This argument makes use of recent
quantitative equidistribution results for polynomial sequences on nilmanifolds
due to the third author [21]. At the end of this iteration, we have replaced
$\varphi(y)$ by a step-$1$ nilsequence, namely, a function of the form
$e(p(y))$ for some polynomial $p$. We then use Weyl’s inequality to reduce to
the case where $p(y)=\alpha_{1}y+\alpha_{0}$ is linear. Another application of
Weyl’s inequality shows that there are many values of $y$ such that
$a(y)-\alpha_{1}$ is major-arc, i.e., close to a rational of small height;
pigeonholing in these rational shifts finally gives that $a(y)$ is nearly
constant for many $y$’s.

Figure 1 provides a visual overview of the main steps of our argument.

Our degree-lowering arguments must be modified in several ways to account for
the parameter $W$. Recall that the initial norm-control in (2) involves
differencing with respect to boxes with common difference $W$ (rather than
$1$). In order to manipulate such expressions and use inverse theorems for box
norms, we must split all of the parameters in sight (e.g., $x,y,z$) into
arithmetic progressions with common difference $W$. This maneuver, which often
requires introducing iterated $W$-tricks, is quite a nuisance but does not
change the essential nature of our arguments.

More importantly, the miniature PET induction in the lead-up to (3) yields
Gowers-norm control where the differencing parameters are boxes with side
lengths equal to the leading coefficient of $\widetilde{P}$. Since this
leading coefficient is a constant multiple of a fixed positive integer power
of $W$, this step of the argument requires us to replace $W$ with some
$W^{O(1)}$, and we must keep track of the accumulation of these exponents in
all of the iterations of the degree-lowering. (We also have to perform
$W^{O(1)}$-tricks instead of $W$-tricks.)

We conclude with a short discussion of the shape of bounds in Theorem 1.1. Of
the three logarithms in the bound in Theorem 1.1, two come from the
supersaturation version of Shkredov’s result [40, 39], and the third arises in
the transference step of our argument. That we lose only one logarithm in
comparing the counts of polynomial and linear corners is reliant on a recent
equidistribution result for nilsequences due to the third author [21] and the
quasipolynomial inverse theorem of Gowers norms [24] (which is itself reliant
on [21]). If we instead used bounds for equidistribution of nilsequences
provided by Tao and Teräväinen [44] (who quantified earlier equidistribution
results of Green and Tao [11]), we would end up with a large number of
iterated logarithms bounded in terms of the degree of the polynomial $P$.

###  2.1. Organization of the paper

Nilsequence input (Proposition 6.2) Inverse theorem for $\Lambda^{\prime}$
(Proposition 4.5) Degree-lowering for $\Lambda^{W}$ (Proposition 4.3) PET and
quantitative concatenation (Proposition 4.2) Inverse theorem for $\Lambda^{W}$
(Theorem 4.1) Inverse theorem for $\Lambda^{\mathrm{Model}}$ (Proposition 7.1)
Comparison theorem (Theorem 7.2) Supersaturation for corners (Proposition F.2)
Bound for polynomial corners (Theorem 1.1) Section 5Sections 4.3, 4.4 Figure
1. The main steps and logical implications in the proof of Theorem 1.1.

After recalling definitions and preliminaries in Section 3, we embark on the
proof of the main technical result of the paper, Theorem 4.1, which asserts
that the counting operator $\Lambda^{W}$ is controlled by suitable degree-$2$
box norms. In Section 4, we show how to use our degree-lowering result,
Proposition 4.3, to deduce Theorem 4.1 from the PET and quantitative
concatenation results of the companion paper [16]. We also reduce Proposition
4.3 to Proposition 4.4, an inverse theorem for the auxiliary operator
$\Lambda^{\prime}$. The lion’s share of the proof of Proposition 4.4 is then
carried out in Section 5. The key input in this argument is Proposition 6.2, a
structural result on (3), which we prove in Section 6 using nilsequence
machinery.

The arguments in Sections 4–6 make use of several standard results which we
collect in the appendices: inverse theorems for various box norms in Appendix
A; a summary of nilsequence theory in Appendix B; a fraction comparison
argument in Appendix C; and a Sárközy-style inverse theorem for a $2$-point
polynomial progressions (derived with circle-method techniques) in Appendix D.

We conclude the main body of the paper with Section 7, where we finally
complete the proof of Theorem 1.1. Proposition 7.1 establishes the desired
box-norm control for $\Lambda^{\mathrm{Model}}$, and we compare $\Lambda^{W}$
and $\Lambda^{\mathrm{Model}}$ in Proposition 7.2. The latter proposition
requires two more ingredients from the appendices: a Fourier-uniformity result
for certain polynomial weights from Appendix E; and a supersaturation version
of Shkredov’s corners theorem from Appendix F.

##  3\. Definitions and preliminaries

###  3.1. Basic notation

We write ${\mathbb{N}},{\mathbb{Z}},{\mathbb{R}},{\mathbb{C}}$ for the sets of
positive integers, integers, real numbers, and complex numbers (respectively).
For reals $a<b$, we set $[a,b]:=\\{\left\lceil
a\right\rceil,a+1,\ldots,\left\lfloor b\right\rfloor\\}$, and we abbreviate
$[0,N-1]$ as $[N]$ and $[-N+1,N-1]$ as $[\pm N]$. We remark that our somewhat
unusual convention for $[N]$ (the norm would be $[N]=[1,N]$) behaves well
under passing to arithmetic progressions: For $q|N$, we have the partition
$[N]=\bigcup_{j\in[q]}(q\cdot[N/q]+j)$.

We write ${\textbf{x}}=(x_{1},...,x_{D})$ for an element of ${\mathbb{Z}}^{D}$
(for fixed $D\in{\mathbb{N}}$) and $x$ for an element of ${\mathbb{Z}}$. When
the context is clear, we often write a sum over ${\mathbb{Z}}^{D}$ or
${\mathbb{Z}}$ as $\sum_{{\textbf{x}}}$ or $\sum_{x}$ instead of
$\sum_{{\textbf{x}}\in{\mathbb{Z}}^{D}}$ or $\sum_{x\in{\mathbb{Z}}}$. We also
write ${\underline{h}}=(h_{1},\ldots,h_{s})$ for a tuple of $s$ integers, and
we denote its $\ell^{1}$-norm by $|{\underline{h}}|:=|h_{1}|+\cdots+|h_{s}|$.
We will often combine these two pieces of notation; we use
${\underline{h}}{\textbf{v}}$ to indicate the tuple
$(h_{1}{\textbf{v}},\ldots,h_{s}{\textbf{v}})$.

We denote the indicator function of a set $X$ by $1_{X}$. If $X$ is finite and
nonempty, we let $\operatorname*{\mathbb{E}}_{x\in X}:=\frac{1}{|X|}\sum_{x\in
X}$ be the average over $X$.

We call a function $f:X\to{\mathbb{C}}$ $1$-bounded if $\sup\limits_{x\in
X}|f(x)|\leq 1$.

We use the following standard asymptotic notation. Let $f,g:X\to{\mathbb{C}}$,
with $g$ taking positive real values. We write $f=O(g)$, $f\ll g$, $g\gg f$,
or $g=\Omega(f)$ if there exists $C>0$ such that $|f(x)|\leq Cg(x)$ for all
$x\in X$, and we write $f\asymp g$ or $f=\Theta(g)$ if $f\ll g$ and $f\gg g$.
If the constant $C$ depends on a parameter, we record this dependence with a
subscript, e.g., $f=O_{P}(g)$, $f\ll_{P}g$.

We let ${\mathcal{C}}:{\mathbb{C}}\to{\mathbb{C}}$ denote the complex
conjugation operator ${\mathcal{C}}z=\overline{z}$.

###  3.2. $W$-trick notation

Throughout the paper, we let $w=w(N)>10$ be a (fixed) slowly-growing function
of $N$; we will later take $w(N)=\exp((\log\log\log\log N)^{C_{P}})$ for some
$C_{P}>0$. Let

$W=W(N):=\prod_{\begin{subarray}{c}p<w\\\ p\text{ prime}\end{subarray}}p$

be the product of the primes up to $w$. Standard results on the growth rate of
Chebyshev’s function give $\log W\asymp w$.

It will often be useful to restrict functions to arithmetic progressions,
which we capture in the following definition.

######  Definition 3.1 ($V$-tricked function).

For $V\in\mathbb{N}$ and $r\in\mathbb{Z}$, we can parameterize the arithmetic
progression $V\mathbb{Z}+r\subseteq\mathbb{Z}$ by $\\{Vx+r:x\in\mathbb{Z}\\}$.
If $f$ is a function on $\mathbb{Z}$, then its restriction to $V\mathbb{Z}+r$,
with this parametrization, is

$f_{(r,V)}(x):=f(Vx+r).$

Likewise, for $r_{1},r_{2}\in\mathbb{Z}$ and $f$ a function on
$\mathbb{Z}^{2}$, the restriction of $f$ to
$(V\mathbb{Z}+r_{1})\times(V\mathbb{Z}+r_{2})$ can be parameterized as

$f_{(r_{1},r_{2},V)}(x,y):=f(Vx+r_{1},Vy+r_{2}).$

We refer to the operation of passing to such a subprogression as a _$V$
-trick_, and we say that the resulting functions are _$V$ -tricked_.

In this paper, we will usually take $V$ to be a small (nonnegative integer)
power of $W$ and $r,r_{1},r_{2}$ to be elements of $[V]$. We remark that a
composition of two such $V$-tricks is itself a $V$-trick. To see this
symbolically for $f:\mathbb{Z}\to\mathbb{C}$, one can calculate that

$\displaystyle(f_{(r_{1},V_{1})})_{(r_{2},V_{2})}(x)$
$\displaystyle=f_{(r_{1},V_{1})}(V_{2}x+r_{2})$
$\displaystyle=f(V_{1}(V_{2}x+r_{2})+r_{1})$
$\displaystyle=f_{(V_{1}r_{2}+r_{1},V_{1}V_{2})}(x),$

where $V_{1}V_{2}$ is a power of $W$ if $V_{1},V_{2}$ are. The case of
functions on $\mathbb{Z}^{2}$ is analogous.

######  Definition 3.2 ($V$-tricked polynomial).

For $V$-tricks of polynomials, we will use slightly different notation that
will turn out to be helpful for keeping track of divisibility properties of
various coefficients. Let $Q\in\mathbb{Z}[z]$ be a polynomial. For
$V\in\mathbb{N}$ and $r\in{\mathbb{Z}}$, define the _$V$ -tricked_ polynomial
of $Q$ to be

$Q_{[r,V]}(z):=\frac{Q(Vz+r)-Q(r)}{V}\in\mathbb{Z}[z].$

That $Q_{[r,V]}$ has integer coefficients can be easily verified using the
Binomial Theorem.

As in the case of $V$-tricks for functions, the composition of two $V$-tricks
for a polynomial is again a $V$-trick. In particular, we have

$\displaystyle(Q_{[r_{1},V_{1}]})_{[r_{2},V_{2}]}(z)$
$\displaystyle=\frac{Q_{[r_{1},V_{1}]}(V_{2}z+r_{2})-Q_{[r_{1},V_{1}]}(r_{2})}{V_{2}}$
$\displaystyle=\frac{Q(V_{1}(V_{2}z+r_{2})+r_{1})-Q(r_{1})-Q(V_{1}r_{2}+r_{1})+Q(r_{1})}{V_{1}V_{2}}$
$\displaystyle=Q_{[V_{1}r_{2}+r_{1},V_{1}V_{2}]}(z).$

Note that iterated $V$-tricks (in both the function setting and the polynomial
setting) do not in general commute.

###  3.3. Van der Corput Inequalities

If $E\subseteq{\mathbb{Z}}^{D}$ is finite and nonempty, we define the Fejér
kernel

$\displaystyle\mu_{E}({\mathbf{h}}):=\operatorname*{\mathbb{E}}_{{\mathbf{h}}_{1},{\mathbf{h}}_{2}\in
E}1_{{\mathbf{h}}_{1}-{\mathbf{h}}_{2}}({\mathbf{h}}).$

Note that $\sum_{\mathbf{h}}\mu_{E}({\mathbf{h}})=1$ and that
$0\leq\mu_{E}({\mathbf{h}})\leq\frac{1_{E-E}({\mathbf{h}})}{|E|}$ pointwise.
If $E=[\pm H]$, we set

$\displaystyle\mu_{H}(h):=\mu_{[\pm
H]}(h)=\operatorname*{\mathbb{E}}_{h_{1},h_{2}\in[\pm
H]}1_{h_{1}-h_{2}}(h)=\frac{1}{2H-1}\mathopen{}\left(1-\frac{|h|}{2H-1}\mathclose{}\right)_{+}.$

This definition differs slightly from those in [30, 31, 32, 35] in that we
take the ranges of $h_{1},h_{2}$ to be $[\pm H]$ rather than $[H]$. Making the
range of $h_{1},h_{2}$ symmetric around the origin will be convenient for us
later.

We will use the following form of the standard van der Corput inequality. For
a more thorough discussion, see [16, Section 3] (which follows from, e.g.,
[35, Lemma 3.2]).

######  Lemma 3.3 (The van der Corput inequality).

Let $\delta\in(0,1]$, and let $H,N\in{\mathbb{N}}$ with
$H\leq\frac{\delta^{2}}{4}N$. If $f:{\mathbb{Z}}\to{\mathbb{C}}$ is a
$1$-bounded function satisfying

(4)
$\displaystyle\mathopen{}\left|\operatorname*{\mathbb{E}}_{x\in[N]}f(x)\mathclose{}\right|\geq\delta,$

then

$\displaystyle\operatorname*{\mathbb{E}}_{h,h^{\prime}\in[\pm
H]}\operatorname*{\mathbb{E}}_{x\in[N]}f(x+h)\overline{f(x+h^{\prime})}\geq\frac{\delta^{2}}{4}$

and

$\displaystyle{\sum_{h}\mu_{H}(h)\operatorname*{\mathbb{E}}_{x\in[N]}f(x)\overline{f(x+h)}}\geq\frac{\delta^{2}}{4}.$

###  3.4. Box norms

We now briefly review the theory of box norms on ${\mathbb{Z}}^{D}$; we will
later work with the groups ${\mathbb{Z}}$ and ${\mathbb{Z}}^{2}$. Given
${\mathbf{h}},{\mathbf{h}}^{\prime}\in{\mathbb{Z}}^{D}$ and a finitely
supported function $f:{\mathbb{Z}}^{D}\to{\mathbb{C}}$, we define the
(multiplicative) discrete derivatives
$\Delta_{\mathbf{h}}f({\textbf{x}}):=f({\textbf{x}})\overline{f({\textbf{x}}+{\mathbf{h}})}$
and
$\Delta^{\prime}_{({\mathbf{h}},{\mathbf{h}}^{\prime})}f({\textbf{x}}):=f({\textbf{x}}+{\mathbf{h}})\overline{f({\textbf{x}}+{\mathbf{h}}^{\prime})}$.
Similarly, compositions of such discrete derivatives are given by

$\displaystyle\Delta_{{\mathbf{h}}_{1},\ldots,{\mathbf{h}}_{s}}f({\textbf{x}})$
$\displaystyle=\Delta_{{\mathbf{h}}_{1}}\cdots\Delta_{{\mathbf{h}}_{s}}f({\textbf{x}})=\prod_{{\underline{\epsilon}}\in\\{0,1\\}^{s}}{\mathcal{C}}^{|{\underline{\epsilon}}|}f({\textbf{x}}+{\underline{\epsilon}}\cdot{\underline{\textbf{h}}}),$
$\displaystyle\Delta^{\prime}_{({\mathbf{h}}_{1},{\mathbf{h}}_{1}^{\prime}),\ldots,\;({\mathbf{h}}_{s},{\mathbf{h}}_{s}^{\prime})}f({\textbf{x}})$
$\displaystyle=\Delta^{\prime}_{({\mathbf{h}}_{1},{\mathbf{h}}_{1}^{\prime})}\cdots\Delta^{\prime}_{({\mathbf{h}}_{s},{\mathbf{h}}_{s}^{\prime})}f({\textbf{x}})=\prod_{{\underline{\epsilon}}\in\\{0,1\\}^{s}}{\mathcal{C}}^{|{\underline{\epsilon}}|}f({\textbf{x}}+(\underline{1}-{\underline{\epsilon}})\cdot{\underline{\textbf{h}}}+{\underline{\epsilon}}\cdot{\underline{\textbf{h}}}^{\prime}),$

where ${\underline{\textbf{h}}}=({\mathbf{h}}_{1},\ldots,{\mathbf{h}}_{s})$
and again ${\mathcal{C}}z=\overline{z}$ for $z\in{\mathbb{C}}$.

For finite sets $E_{1},\ldots,E_{s}\subseteq{\mathbb{Z}}^{D}$, we define the
box norm of $f$ along $E_{1},\ldots,E_{s}$ to be

$\displaystyle\left\|f\right\|_{E_{1},\ldots,E_{s}}:=\mathopen{}\left(\operatorname*{\mathbb{E}}_{{\mathbf{h}}_{1},{\mathbf{h}}_{1}^{\prime}\in
E_{1}}\cdots\operatorname*{\mathbb{E}}_{{\mathbf{h}}_{s},{\mathbf{h}}_{s}^{\prime}\in
E_{s}}\sum_{\textbf{x}}\Delta^{\prime}_{({\mathbf{h}}_{1},{\mathbf{h}}_{1}^{\prime}),\ldots,\;({\mathbf{h}}_{s},{\mathbf{h}}_{s}^{\prime})}f({\textbf{x}})\mathclose{}\right)^{1/2^{s}}.$

We can equivalently express this as

(5)
$\displaystyle\left\|f\right\|_{E_{1},\ldots,E_{s}}=\mathopen{}\left(\sum_{{\textbf{x}},{\mathbf{h}}_{1},\ldots,{\mathbf{h}}_{s}}\mu_{E_{1}}({\mathbf{h}}_{1})\cdots\mu_{E_{s}}({\mathbf{h}}_{s})\Delta_{{\mathbf{h}}_{1},\ldots,{\mathbf{h}}_{s}}f({\textbf{x}})\mathclose{}\right)^{1/2^{s}}$

after shifting
${\textbf{x}}\mapsto{\textbf{x}}-{\mathbf{h}}^{\prime}_{1}-\cdots-{\mathbf{h}}_{s}^{\prime}$
and removing the extraneous averages over
${\mathbf{h}}^{\prime}_{1},\ldots,{\mathbf{h}}^{\prime}_{s}$. For the sake of
completeness, we also define
$\left\|f\right\|_{\emptyset}:=\sum_{\textbf{x}}f({\textbf{x}})$ (but note
that this is not a seminorm). If a set $E$ repeats $t$ times, we often write
$E^{t}$ instead of $E,\ldots,E$. We also write
$\left\|f\right\|_{U^{s}(E)}:=\left\|f\right\|_{E^{s}}$ for the degree-$s$
Gowers norm of $f$ along $E$. Box norms satisfy a number of well known
properties, listed in the following lemma.

######  Lemma 3.4 (Properties of box norms, [16, Lemma 3.5]).

Let $\delta\in(0,1)$, let $d,D,N,s\in{\mathbb{N}}$, and let
$E_{1},\ldots,E_{s}\subseteq{\mathbb{Z}}^{D}$ be finite and nonempty sets. Let
$f:{\mathbb{Z}}^{D}\to{\mathbb{C}}$ be a $1$-bounded function supported on
$[N]^{D}$. Then the following properties hold:

  1. (i)

(Inductive formula) For any $i\in\\{1,\ldots,s\\}$, we have

$\displaystyle\left\|f\right\|_{E_{1},\ldots,E_{s}}^{2^{s}}=\operatorname*{\mathbb{E}}_{{\mathbf{h}}_{1},{\mathbf{h}}_{1}^{\prime}\in
E_{1}}\cdots\operatorname*{\mathbb{E}}_{{\mathbf{h}}_{i},{\mathbf{h}}_{i}^{\prime}\in
E_{i}}\left\|\Delta^{\prime}_{({\mathbf{h}}_{1},{\mathbf{h}}_{1}^{\prime}),\ldots,\;({\mathbf{h}}_{i},{\mathbf{h}}_{i}^{\prime})}f\right\|_{E_{i+1},\ldots,E_{s}}^{2^{s-i}}.$

  2. (ii)

(Permutation invariance) For any permutation $\sigma$ on $\\{1,\ldots,s\\}$,
we have

$\displaystyle\left\|f\right\|_{E_{1},\ldots,E_{s}}=\left\|f\right\|_{E_{\sigma(1)},\ldots,E_{\sigma(s)}}.$

  3. (iii)

(Monotonicity) If $f$ is $1$-bounded and $|[N]^{D}-E_{s}|\leq CN^{D}$ for some
$C>0$, then

(6) $\displaystyle\left\|f\right\|_{E_{1},\ldots,E_{s-1}}^{2^{s-1}}\geq\delta
N^{D}\quad\Longrightarrow\quad\left\|f\right\|_{E_{1},\ldots,E_{s}}^{2^{s}}\geq\delta^{2}N^{D}/C.$

  4. (iv)

(Enlarging the sets) If $s\geq 2$ and
$E^{\prime}_{i}\subseteq{\mathbb{Z}}^{D}$ is a finite set satisfying
$E^{\prime}_{i}\supseteq E_{i}$ for each $i\in\\{1,\ldots,s\\}$, then

$\displaystyle\left\|f\right\|_{E_{1},\ldots,E_{s}}\leq\mathopen{}\left(\frac{|E_{1}^{\prime}|\cdots|E_{s}^{\prime}|}{|E_{1}|\cdots|E_{s}|}\mathclose{}\right)^{1/2^{s-1}}\left\|f\right\|_{E_{1}^{\prime},\ldots,E_{s}^{\prime}}.$

  5. (v)

(Trimming the lengths of boxes) Let

$\displaystyle E_{i}={\boldsymbol{\beta}}_{i}\cdot[\pm
H_{i}]\quad\textrm{and}\quad
E_{i}^{\prime}={\boldsymbol{\beta}}_{i}\cdot[\pm\kappa_{i}H_{i}]$

for some ${\boldsymbol{\beta}}_{i}\in{\mathbb{Z}}^{D}$, $\kappa_{i}>0$, and
$H_{i}\in{\mathbb{N}}$. If $f$ is $1$-bounded, then

$\displaystyle\left\|f\right\|_{E_{1},\ldots,E_{s}}^{2^{s}}\geq\delta
N^{D}\quad\Longrightarrow\quad\left\|f\right\|_{E_{1}^{\prime},\ldots,E_{s}^{\prime}}^{2^{s}}\gg_{s}\delta^{2^{s}}\min(1,\delta^{2^{s}}/\kappa)^{2s}N^{D}$

for $\kappa=\max_{i}\kappa_{i}.$

  6. (vi)

(Passing to sub-arithmetic progressions) Suppose that $f$ is $1$-bounded and

$\displaystyle E_{i}={\boldsymbol{\beta}}_{i}\cdot[\pm
H_{i}]\quad\textrm{and}\quad
E_{i}^{\prime}=q_{i}{\boldsymbol{\beta}}_{i}\cdot[\pm H_{i}/q_{i}]$

for some ${\boldsymbol{\beta}}_{i}\in{\mathbb{Z}}^{D}$ and
$q_{i},H_{i}\in{\mathbb{N}}$ satisfying $q_{i}\leq C\delta^{2^{s}}H_{i}$ for
all $i$ and some constant $C>0$. Then

$\displaystyle\left\|f\right\|_{E_{1},\ldots,E_{s}}^{2^{s}}\geq\delta
N^{D}\quad\Longrightarrow\quad\left\|f\right\|_{E_{1}^{\prime},\ldots,E_{s}^{\prime}}^{2^{s}}\gg_{s,C}\delta
N^{D}.$

###  3.5. Dual-difference interchange

On several occasions, we apply a standard dual-difference interchange trick
which has been a linchpin in all previous degree-lowering arguments. Its proof
rests on the following observation.

######  Lemma 3.5.

Let $D,t\in{\mathbb{N}}$, let $C>0$, let $E\subseteq{\mathbb{Z}}^{D}$ be
finite and nonempty, and for each $i\in\\{1,\ldots,t\\}$, let
$F_{i}({\textbf{x}})=\operatorname*{\mathbb{E}}_{z_{i}\in
Z_{i}}f_{i}({\textbf{x}},z_{i})$ be a function from ${\mathbb{Z}}^{D}$ to
${\mathbb{C}}$ supported on a set of size at most $CN^{D}$, where $Z_{i}$ is a
nonempty finite set and $f_{i}:{\mathbb{Z}}^{D}\times Z_{i}\to\mathbb{C}$ is
$1$-bounded. If

$\mathopen{}\left|\sum_{{\textbf{x}},{\mathbf{h}}}\mu_{E}({\mathbf{h}})\Delta_{({\mathbf{h}},0)}\prod_{i=1}^{t}\operatorname*{\mathbb{E}}_{z_{i}\in
Z_{i}}f_{i}({\textbf{x}},z_{i})\mathclose{}\right|\geq\delta N^{D},$

then

${\sum_{{\textbf{x}},{\mathbf{h}}}\mu_{E}({\mathbf{h}})\prod_{i=1}^{t}\operatorname*{\mathbb{E}}_{z_{i}\in
Z_{i}}\Delta_{({\mathbf{h}},0)}f_{i}({\textbf{x}},z_{i})}\geq(\delta^{2}/C)N^{D}.$

###### Proof.

Expanding and applying the Cauchy–Schwarz inequality gives

$\displaystyle\delta^{2}N^{2D}$
$\displaystyle\leq\mathopen{}\left|\sum_{\textbf{x}}\operatorname*{\mathbb{E}}_{{\mathbf{h}}\in
E}\prod_{i=1}^{t}\operatorname*{\mathbb{E}}_{z_{i}\in
Z_{i}}f_{i}({\textbf{x}}+{\mathbf{h}},z_{i})\cdot\operatorname*{\mathbb{E}}_{{\mathbf{h}}^{\prime}\in
E}\prod_{i=1}^{t}\operatorname*{\mathbb{E}}_{z^{\prime}_{i}\in
Z_{i}}f_{i}({\textbf{x}}+{\mathbf{h}}^{\prime},z^{\prime}_{i})\mathclose{}\right|^{2}$
$\displaystyle\leq
CN^{D}\cdot\sum_{\textbf{x}}\operatorname*{\mathbb{E}}_{z_{i}\in
Z_{i}}\Bigl{|}\operatorname*{\mathbb{E}}_{{\mathbf{h}}\in
E}\prod_{i=1}^{t}f_{i}({\textbf{x}}+{\mathbf{h}},z_{i})\Bigr{|}^{2}$
$\displaystyle=CN^{D}\cdot\sum_{{\textbf{x}},{\mathbf{h}}}\mu_{E}({\mathbf{h}})\prod_{i=1}^{t}\operatorname*{\mathbb{E}}_{z_{i}\in
Z_{i}}\Delta_{({\mathbf{h}},0)}f_{i}({\textbf{x}},z_{i}),$

as desired. ∎

Iterating Lemma 3.5, we obtain the following.

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

Let $C>0$, let $D,r,s\in{\mathbb{N}}$ with $1\leq r\leq s$, let
$E_{1},\ldots,E_{s}\subseteq[\pm CN^{D}]$ be nonempty sets, and let
$F({\textbf{x}})=\operatorname*{\mathbb{E}}_{z\in Z}f({\textbf{x}},z)$ be a
function from ${\mathbb{Z}}^{D}$ to ${\mathbb{C}}$, where $Z$ is a nonempty
finite set and $f:{\mathbb{Z}}^{D}\times Z\to\mathbb{C}$ is a $1$-bounded
function supported on $[\pm CN^{D}]\times Z$. If

$\displaystyle\left\|F\right\|_{E_{1},\ldots,E_{s}}^{2^{s}}\geq\delta N^{D},$

then

$\displaystyle\sum_{{\mathbf{h}}_{1},\ldots,{\mathbf{h}}_{r}}\mu_{E_{1}}({\mathbf{h}}_{1})\cdots\mu_{E_{r}}({\mathbf{h}}_{r})\left\|F^{{\mathbf{h}}_{1},\ldots{\mathbf{h}}_{r}}\right\|^{2^{s-r}}_{E_{r+1},\ldots,E_{s}}\gg_{C,r}\delta^{2^{r}}N^{D},$

where

$\displaystyle
F^{{\mathbf{h}}_{1},\ldots,{\mathbf{h}}_{r}}({\textbf{x}}):=\operatorname*{\mathbb{E}}_{z\in
Z}\Delta_{({\mathbf{h}}_{1},0),\ldots,\;({\mathbf{h}}_{r},0)}f({\textbf{x}},z).$

###### Proof.

Expanding the definition of the box norm, we get that

$\displaystyle\sum_{{\mathbf{h}}_{2},\ldots,{\mathbf{h}}_{s}}\mu_{E_{2}}({\mathbf{h}}_{2})\cdots\mu_{E_{s}}({\mathbf{h}}_{s})\cdot\sum_{{\textbf{x}},{\mathbf{h}}_{1}}\mu_{E_{1}}({\mathbf{h}}_{1})\Delta_{({\mathbf{h}}_{1},0),\ldots,\;({\mathbf{h}}_{s},0)}\operatorname*{\mathbb{E}}_{z\in
Z}f({\textbf{x}},z)\geq\delta N^{D}.$

We apply Lemma 3.5 for a fixed tuple
$({\mathbf{h}}_{2},\ldots,{\mathbf{h}}_{s})\in E_{2}\times E_{s}$ with the
role of the product over $i\in\\{1,\ldots,t\\}$ played by the iterated
multiplicative derivative
$\Delta_{({\mathbf{h}}_{2},0),\ldots,\;({\mathbf{h}}_{s},0)}$. This lets us
move the differencing over ${\mathbf{h}}_{1}$ inside the expectation, which
gives

$\displaystyle\sum_{{\mathbf{h}}_{1},\ldots,{\mathbf{h}}_{s}}\mu_{E_{1}}({\mathbf{h}}_{1})\cdots\mu_{E_{s}}({\mathbf{h}}_{s})\cdot\sum_{{\textbf{x}}}\Delta_{({\mathbf{h}}_{2},0),\ldots,\;({\mathbf{h}}_{s},0)}\operatorname*{\mathbb{E}}_{z\in
Z}\Delta_{({\mathbf{h}}_{1},0)}f({\textbf{x}},z)\gg_{C}\delta^{2}N^{D}.$

We continue in the same fashion to move the differencings over
${\mathbf{h}}_{2},\ldots,{\mathbf{h}}_{r}$ inside the expectation; here we are
implicitly using the fact that the functions
$\Delta_{({\mathbf{h}}_{1},0),\ldots,\;({\mathbf{h}}_{j},0)}f$ for
${\mathbf{h}}_{i}\in E_{i}$, $1\leq i\leq j\leq r$ are supported on $[\pm
CN^{D}]\times Z$. ∎

###  3.6. Fourier analysis

We conclude the preliminaries section with a brief summary of Fourier analysis
on ${\mathbb{Z}}$, which we shall use on occasion. For a finitely supported
function $f:{\mathbb{Z}}\to{\mathbb{C}}$ and
$\xi\in{\mathbb{R}}/{\mathbb{Z}}$, we define the _Fourier transform_
$\hat{f}:{\mathbb{R}}/{\mathbb{Z}}\to{\mathbb{C}}$ via

$\displaystyle\hat{f}(\xi):=\sum_{x}f(x)e(\xi x).$

The Fourier inversion formula gives
$f(\xi)=\int_{{\mathbb{R}}/{\mathbb{Z}}}\hat{f}(\xi)e(-\xi x)\,d\xi$, and the
Parseval Identity gives $\left\|f\right\|_{2}=\left\|\hat{f}\right\|_{2}$.
Here the $L^{p}$-norm of a function $f:{\mathbb{Z}}\to{\mathbb{C}}$ is defined
by $\left\|f\right\|_{p}:=\Bigl{(}\sum_{x}|f(x)|^{p}\Bigr{)}^{1/p}$ for $1\leq
p<\infty$ and $\left\|f\right\|_{\infty}:=\sup_{x\in{\mathbb{Z}}}f(x)$, the
$L^{p}$-norm of a (Lebesgue-measurable) function
$F:{\mathbb{R}}/{\mathbb{Z}}\to{\mathbb{C}}$ is defined by
$\left\|F\right\|_{p}:=\Bigl{(}\int_{{\mathbb{R}}/{\mathbb{Z}}}|F(\xi)|^{p}\,d\xi\Bigr{)}^{1/p}$
for $1\leq p<\infty$ and $\left\|F\right\|_{\infty}:=\sup\\{r\geq
0:\;\mathrm{Leb}(|F|^{-1}(r,\infty))>0\\}$.

##  4\. Degree-lowering

For the remainder of the paper, we fix the integer polynomial $P$ together
with its degree $d$ and the auxiliary $W$-tricked polynomial $\widetilde{P}$
defined in (1). Recall that for $1$-bounded functions
$f_{0},f_{1},f_{2}:{\mathbb{Z}}^{2}\to\mathbb{C}$ supported on $[N]^{2}$, we
have the counting operator

$\Lambda^{W}(f_{0},f_{1},f_{2})=\sum_{x,y\in\mathbb{Z}}\operatorname*{\mathbb{E}}_{z\in[(N/W_{d})^{1/d}]}f_{0}(x,y)f_{1}(x+\widetilde{P}(z),y)f_{2}(x,y+\widetilde{P}(z)),$

where $W_{d}$ is the leading coefficient of $\widetilde{P}$. Recall also that
${\mathbf{e}}_{1}:=(1,0)$ and ${\mathbf{e}}_{2}:=(0,1)$ denote the usual basis
vectors in $\mathbb{Z}^{2}$. As described in the proof outline above, the main
work of this paper is showing that $\Lambda^{W}$ is “controlled” by
appropriate degree-$2$ box norms of its arguments.

######  Theorem 4.1 (Inverse theorem for $\Lambda^{W}$).

There is a constant $C=C_{P}>0$ such that the following holds. Let
$\delta\in(0,1/10)$, and let $f_{0},f_{1},f_{2}:{\mathbb{Z}}^{2}\to\mathbb{C}$
be $1$-bounded functions supported on $[N]^{2}$ for some integer $N\geq
CW^{C}\exp(\log(1/\delta)^{C})$. If

$|\Lambda^{W}(f_{0},f_{1},f_{2})|\geq\delta N^{2},$

then there exists some positive integer power $V=W^{O_{P}(1)}$ such that

$\displaystyle\|f_{0}\|_{{\mathbf{e}}_{1}V\cdot[N/V],\;{\mathbf{e}}_{2}V\cdot[N/V]}^{4}\geq\exp(-\log(1/\delta)^{O_{P}(1)})N^{2},$
$\displaystyle\|f_{1}\|_{{\mathbf{e}}_{1}V\cdot[N/V],\;({\mathbf{e}}_{2}-{\mathbf{e}}_{1})V\cdot[N/V]}^{4}\geq\exp(-\log(1/\delta)^{O_{P}(1)})N^{2},$
and
$\displaystyle\|f_{2}\|_{{\mathbf{e}}_{2}V\cdot[N/V],\;({\mathbf{e}}_{2}-{\mathbf{e}}_{1})V\cdot[N/V]}^{4}\geq\exp(-\log(1/\delta)^{O_{P}(1)})N^{2}.$

Theorem 4.1 is a $W$-tricked version of Theorem 1.2 from the introduction.
While we prove only the former, the latter follows from a simplified version
of the proof of Theorem 4.1 in which we take $W=V=1$ in all places and replace
$\widetilde{P}$ with $P$. We remark that while Theorem 4.1 has the same
restriction on $P$ as Theorem 1.1, no such restriction is present in the
statement of Theorem 1.2. This is because the fraction-comparison argument
Lemma C.3, whose proof in the $W$-tricked setting uses the special structure
of ${P}$, holds trivially for all non-$W$-tricked polynomials.

To prove Theorem 4.1, we will use a degree-lowering argument. The starting
point for the argument is the following special case of [16, Theorem 1.2].

######  Proposition 4.2.

There exist a constant $C=C_{d}>0$ and a positive integer $t=O_{d}(1)$ such
that for all $\delta\in(0,1/10)$ and $1$-bounded functions
$f_{0},f_{1},f_{2}:{\mathbb{Z}}^{2}\to\mathbb{C}$ supported on $[N]^{2}$ for
some integer $N\geq CW_{d}\delta^{-C}$, the bound

$|\Lambda^{W}(f_{0},f_{1},f_{2})|\geq\delta N^{2}$

implies that

$\displaystyle\|f_{0}\|_{({\mathbf{e}}_{1}W_{d}\cdot[\pm
N/W_{d}])^{t},\;({\mathbf{e}}_{2}W_{d}\cdot[\pm
N/W_{d}])^{t}}^{2^{2t}}\gg_{d}\delta^{O_{d}(1)}N^{2}$
$\displaystyle\|f_{1}\|_{({\mathbf{e}}_{1}W_{d}\cdot[\pm
N/W_{d}])^{t},\;(({\mathbf{e}}_{2}-{\mathbf{e}}_{1})W_{d}\cdot[\pm
N/W_{d}])^{t}}^{2^{2t}}\gg_{d}\delta^{O_{d}(1)}N^{2}$ and
$\displaystyle\|f_{2}\|_{({\mathbf{e}}_{2}W_{d}\cdot[\pm
N/W_{d}])^{t},\;(({\mathbf{e}}_{2}-{\mathbf{e}}_{1})W_{d}\cdot[\pm
N/W_{d}])^{t}}^{2^{2t}}\gg_{d}\delta^{O_{d}(1)}N^{2}.$

Our goal in the next few sections is to reduce $t$ to $2$ in the box norms
appearing in Proposition 4.2. The following proposition captures the main
iterative step of this process.

######  Proposition 4.3 (Degree-lowering).

Let $k,\ell\in\mathbb{N}$ with $\max(k,\ell)\geq 2$. For every $C_{1}>0$ there
exists $C_{2}=C_{2}(C_{1},P,k,\ell)>0$ such that the following holds. Let
$V\leq W^{C_{1}}$ be a nonnegative integer power of $W$, and suppose that for
all $\delta\in(0,1/10)$, all positive integers $N\geq
C_{2}W^{C_{2}}\exp(\log(1/\delta)^{C_{2}})$, and all $1$-bounded functions
$f_{0},f_{1},f_{2}:{\mathbb{Z}}^{2}\to\mathbb{C}$ supported on $[N]^{2}$, the
lower bound

$|\Lambda^{W}(f_{0},f_{1},f_{2})|\geq\delta N^{2}$

implies that

$\|f_{0}\|_{({\mathbf{e}}_{1}V\cdot[\pm
N/V])^{k},\;({\mathbf{e}}_{2}V\cdot[\pm
N/V])^{\ell}}^{2^{k+\ell}}\geq\exp(-\log(1/\delta)^{C_{1}})N^{2}.$

Then there exists some positive integer power
$\tilde{V}=V^{O_{C_{1},P,k,\ell}(1)}$ such that

$\|f_{0}\|_{({\mathbf{e}}_{1}\tilde{V}\cdot[N/\tilde{V}])^{k-1},\;({\mathbf{e}}_{2}\tilde{V}\cdot[\pm
N/\tilde{V}])^{\ell}}^{2^{k+\ell-1}}\geq\exp(-\log(1/\delta)^{O_{C_{1},P,k,\ell}(1)})N^{2}$

if $k\geq 2$ and

$\|f_{0}\|_{({\mathbf{e}}_{1}\tilde{V}\cdot[N/\tilde{V}])^{k},\;({\mathbf{e}}_{2}\tilde{V}\cdot[\pm
N/\tilde{V}])^{\ell-1}}^{2^{k+\ell-1}}\geq\exp(-\log(1/\delta)^{O_{C_{1},P,k,\ell}(1)})N^{2}$

if $\ell\geq 2$.

Before proving Proposition 4.3, we show how it implies Theorem 4.1.

###### Proof of Theorem 4.1 assuming Propositions 4.2 and 4.3..

By Proposition 4.2, there exists a positive integer $t=O_{d}(1)$ such that

$\|f_{0}\|_{({\mathbf{e}}_{1}W_{d}\cdot[\pm
N/W_{d}])^{t},\;({\mathbf{e}}_{2}W_{d}\cdot[\pm
N/W_{d}])^{t}}^{2^{2t}}\gg_{d}\delta^{O_{d}(1)}N^{2}.$

Using Lemma 3.4(iv), we can replace $W_{d}$ by $W^{d-1}$ at the cost of a
factor of $O_{P}(1)$ in the lower bound. We now apply Proposition 4.3 $2t-2$
times. Since $N$ is chosen sufficiently large, we end up with a positive
integer power $V=W^{O_{d}(1)}$ such that

$\|f_{0}\|_{{\mathbf{e}}_{1}V\cdot[\pm N/V],\;{\mathbf{e}}_{2}V\cdot[\pm
N/V]}^{4}\geq\exp(-\log(1/\delta)^{O_{P}(1)})N^{2}.$

This gives the claimed control in terms of $f_{0}$.

The control in terms of $f_{1},f_{2}$ follows by symmetry. To see this, notice
that the affine linear map $(x,y)\mapsto(2N-1-(x+y),y)$ sends $[N]^{2}$ into
$[2N]^{2}$ and preserves the set of corners with each given side length, with
the caveat that the two points on the horizontal side of each corner have been
“exchanged”. More precisely, for each $i$, define the function
$\widetilde{f}_{i}:[2N]^{2}\to{\mathbb{C}}$ by
$\widetilde{f}_{i}(x,y):=f_{i}(2N-1-(x+y),y)$. Then the change of variables
$x\mapsto 2N-1-x-y-\widetilde{P}(z)$ gives the identity

$\Lambda^{W}(f_{0},f_{1},f_{2})=\Lambda^{W}(\widetilde{f_{1}},\widetilde{f_{0}},\widetilde{f_{2}}).$

The previous paragraph (with $N,\delta$ replaced by $2N,\delta/4$) tells us
that

$\|\widetilde{f}_{1}\|_{{\mathbf{e}}_{1}V\cdot[\pm
2N/V],\;{\mathbf{e}}_{2}V\cdot[\pm
2N/V]}^{4}\geq\exp(-\log(1/\delta)^{O_{P}(1)})N^{2}.$

Using Lemma 3.4(v) to replace $[\pm 2N/V]$ by $[\pm N/V]$ and unwinding the
definition of $\widetilde{f}_{1}$, we conclude that

$\|f_{1}\|_{{\mathbf{e}}_{1}V\cdot[N/V],\;({\mathbf{e}}_{2}-{\mathbf{e}}_{1})V\cdot[N/V]}^{4}\geq\exp(-\log(1/\delta)^{O_{P}(1)})N^{2}.\\\
$

The control for $f_{2}$ follows from an analogous change of variables. ∎

###  4.1. Proof of Proposition 4.3: preliminary maneuvers

We now begin the proof of Proposition 4.3. All implicit constants are allowed
to depend on $P,k,l$. The initial assumption

$\displaystyle|\Lambda^{W}(f_{0},f_{1},f_{2})|\geq\delta N^{2}$

implies that

(7) $\displaystyle\|f_{0}\|_{({\mathbf{e}}_{1}V\cdot[\pm
N/V])^{k},\;({\mathbf{e}}_{2}V\cdot[\pm
N/V])^{\ell}}^{2^{k+\ell}}\geq\exp(-\log(1/\delta)^{O(1)})N^{2}$

for all $1$-bounded functions
$f_{0},f_{1},f_{2}:{\mathbb{Z}}^{2}\to{\mathbb{C}}$ supported on $[N]^{2}$.
Our proof strategy is as follows. Applying several standard maneuvers such as
stashing, the dual-difference interchange and an inverse theorem for the
$U^{2}\times U^{1}$ box norm, we reduce the problem to the study of the
auxiliary operator

$\Lambda^{\prime}(a,\widetilde{f_{1}},\widetilde{f_{2}}):=\sum_{x,y}\operatorname*{\mathbb{E}}_{z\in[(N/W_{d})^{1/d}V^{-1}]}e(a(y)x)\widetilde{f_{1}}(x+\widetilde{P}_{[r,V]}(z),y)\widetilde{f_{2}}(x,y+\widetilde{P}_{[r,V]}(z)).$

The phase $e(a(y)x)$ is the “main term” that arises from the $U^{2}\times
U^{1}$ inverse theorem. Our main technical advancement is a structural result
on $\Lambda^{\prime}$: We show that if
$\Lambda^{\prime}(a,\widetilde{f_{1}},\widetilde{f_{2}})$ is large, then $a$
is “approximately constant” in the sense that there are many arithmetic
progressions of difference $V^{\prime}=V^{O(1)}$ on each of which $a$ is
constant a positive proportion of the time. Morally speaking, this means that
$\Lambda^{\prime}(a,\widetilde{f_{1}},\widetilde{f_{2}})$ can be large only
when $e(a(y)x)$ is actually a $U^{1}\times U^{1}$ obstruction. We use this
information to obtain the auxiliary norm control

$\displaystyle\|f_{1}\|^{4}_{({\mathbf{e}}_{1}VV^{\prime}\cdot[\pm
N/\tilde{V}])^{k-1},\;({\mathbf{e}}_{2}-{\mathbf{e}}_{1})\tilde{V}\cdot[\pm
N/\tilde{V}],\;({\mathbf{e}}_{2}\tilde{V}\cdot[\pm
N/\tilde{V}])^{\ell-1}}\geq\exp(-\log(1/\delta)^{O(1)})N^{2},$

where $\tilde{V}=VV^{\prime}$. We then transfer this norm-control from $f_{1}$
to $f_{0}$.

Let us fill in some more details of this strategy. In doing so, we will also
highlight several techniques used in various guises throughout the paper.

We define the _dual function_

$\displaystyle{\mathcal{D}}_{0}(f_{1},f_{2})(x,y):=\operatorname*{\mathbb{E}}_{z\in[(N/W_{d})^{1/d}]}f_{1}(x+\widetilde{P}(z),y)f_{2}(x,y+\widetilde{P}(z))$

with respect to the first argument of $\Lambda^{W}$. The Cauchy–Schwarz
inequality gives

$\displaystyle|\Lambda^{W}(f_{0},f_{1},f_{2})|^{2}$
$\displaystyle=\mathopen{}\left|\sum_{x,y}f_{0}(x,y){\mathcal{D}}_{0}(f_{1},f_{2})(x,y)\mathclose{}\right|^{2}$
$\displaystyle\leq
N^{2}\cdot\sum_{x,y}|{\mathcal{D}}_{0}(f_{1},f_{2})(x,y)|^{2}$
$\displaystyle=N^{2}\cdot\Lambda^{W}({\mathcal{D}}_{0}(f_{1},f_{2}),\overline{f_{1}},\overline{f_{2}}),$

for all $1$-bounded functions $f_{0}$ supported on $[N]^{2}$. It follows that
if $\Lambda^{W}(f_{0},f_{1},f_{2})\geq\delta N^{2}$, then we also have

$\displaystyle\Lambda^{W}({\mathcal{D}}_{0}(f_{1},f_{2}),\overline{f_{1}},\overline{f_{2}})\geq\delta^{2}N^{2}.$

This trick whereby we replace an arbitrary function $f_{0}$ by the structured
function ${\mathcal{D}}_{0}(f_{1},f_{2})$ is often called stashing, and it
will be the bread and butter of our arguments. In particular, once we know
that $\Lambda^{W}$ is controlled by some norm $\left\|\cdot\right\|$ of its
first argument, we see that the largeness of $\Lambda^{W}(f_{0},f_{1},f_{2})$
implies not only the largeness of $\left\|f_{0}\right\|$ but also the
largeness of $\left\|{\mathcal{D}}_{0}(f_{1},f_{2})\right\|$. In this
particular case, stashing and (7) together give

(8)
$\displaystyle\|{\mathcal{D}}_{0}(f_{1},f_{2})\|_{({\mathbf{e}}_{1}V\cdot[\pm
N/V])^{k},\;({\mathbf{e}}_{2}V\cdot[\pm
N/V])^{\ell}}^{2^{k+\ell}}\geq\exp(-\log(1/\delta)^{O(1)})N^{2}.$

The next step is to apply the dual–difference interchange to (8) in order to
arrive at an average of $U^{2}\times U^{1}$-box norms to which we can apply an
inverse theorem. To begin, applying Lemma 3.6 to (8) gives

$\sum_{\begin{subarray}{c}{\underline{h}}_{1}\in\mathbb{Z}^{k-2},\\\
{\underline{h}}_{2}\in\mathbb{Z}^{\ell-1}\end{subarray}}\mu_{N/V}({\underline{h}}_{1},{\underline{h}}_{2})\|\mathcal{D}_{0}^{{\underline{h}}_{1},{\underline{h}}_{2}}(f_{1},f_{2})\|_{({\mathbf{e}}_{1}V\cdot[\pm
N/V])^{2},\;{\mathbf{e}}_{2}V\cdot[\pm
N/V]}^{8}\geq\exp(-\log(1/\delta)^{O(1)})N^{2},$

where

$\mathcal{D}_{0}^{{\underline{h}}_{1},{\underline{h}}_{2}}(f_{1},f_{2})(x,y):=\operatorname*{\mathbb{E}}_{z\in[(N/W_{d})^{1/d}]}\Delta_{{\underline{h}}_{1}V{\mathbf{e}}_{1},{\underline{h}}_{2}V{\mathbf{e}}_{2}}(f_{1}(x+\widetilde{P}(z),y)f_{2}(x,y+\widetilde{P}(z)))$

for ${\underline{h}}_{1}\in\mathbb{Z}^{k-2}$ and
${\underline{h}}_{2}\in\mathbb{Z}^{\ell-1}$. (We recall here that
${\underline{h}}_{1}V{\mathbf{e}}_{1}=(h_{11}V{\mathbf{e}}_{1},\ldots,h_{1(k-2)}V{\mathbf{e}}_{1})$,
and similarly for ${\underline{h}}_{2}V{\mathbf{e}}_{2}$.) Since
$\mu_{N/V}({\underline{h}}_{1},{\underline{h}}_{2})\ll(N/V)^{-k-\ell+3}$
pointwise, the popularity principle provides at least
$\exp(-\log(1/\delta)^{O(1)})(N/V)^{k+\ell-3}$ choices of
$({\underline{h}}_{1},{\underline{h}}_{2})$ such that

(9)
$\|\mathcal{D}_{0}^{{\underline{h}}_{1},{\underline{h}}_{2}}(f_{1},f_{2})\|_{({\mathbf{e}}_{1}V\cdot[\pm
N/V])^{2},\;{\mathbf{e}}_{2}V\cdot[\pm
N/V]}^{8}\geq\exp(-\log(1/\delta)^{O(1)})N^{2}.$

For the next several steps, fix such a choice of
${\underline{h}}_{1},{\underline{h}}_{2}$. (The reader can now see why all of
the main ideas appear in the case $k=2$, $\ell=1$ described in the proof
sketch.)

The box norm in (9) is not yet ripe for an application of an inverse theorem
for the $U^{2}\times U^{1}$ box norms because of the multiplicative factor $V$
in the boxes ${\mathbf{e}}_{1}V\cdot[\pm N/V]$ and ${\mathbf{e}}_{2}V\cdot[\pm
N/V]$. To bring the box norm into a form amenable to an application of the
inverse theorem, we split the ranges of $x,y$ into arithmetic progressions of
common difference $V$ and observe the identity

(10) $\displaystyle\left\|g\right\|_{({\mathbf{e}}_{1}V\cdot[\pm
N/V])^{2},\;{\mathbf{e}}_{2}V\cdot[\pm
N/V]}^{8}=\sum_{j_{1},j_{2}\in[V]}\left\|g_{(j_{1},j_{2},V)}\right\|_{({\mathbf{e}}_{1}\cdot[\pm
N/V])^{2},\;{\mathbf{e}}_{2}\cdot[\pm N/V]}^{8}.$

for any compactly supported $g:{\mathbb{Z}}\to{\mathbb{C}}$; we recall the
$V$-tricked function $g_{(j_{1},j_{2},V)}(x,y)=g(Vx+j_{1},Vy+j_{2})$ from
Definition 3.1. Notice that after this change of variables, the boxes in the
box norm have side length $[N/V]$ instead of $V\cdot[N/V]$.

We will of course apply the identity (10) to the functions
$\mathcal{D}^{{\underline{h}}_{1},{\underline{h}}_{2}}_{0}(f_{1},f_{2})$. This
maneuver requires us to adapt the range of $z$ accordingly: Recalling the
definition of the $V$-trick for polynomials, we replace $\widetilde{P}(z)$ by
$\widetilde{P}_{[r,V]}(z)=\frac{\widetilde{P}(Vz+r)-\widetilde{P}(r)}{V}$. On
changing variables $z\mapsto Vz+r$, we can express the dual function as

$\displaystyle\mathcal{D}_{0}^{{\underline{h}}_{1},{\underline{h}}_{2}}(f_{1},f_{2})(Vx+j_{1},Vy+j_{2})$
$\displaystyle=\operatorname*{\mathbb{E}}_{z\in[(N/W_{d})^{1/d}]}\Delta_{V{\underline{h}}_{1}{\mathbf{e}}_{1},V{\underline{h}}_{2}{\mathbf{e}}_{2}}(f_{1}(Vx+j_{1}+\widetilde{P}(z),Vy+j_{2})f_{2}(Vx+j_{1},Vy+j_{2}+\widetilde{P}(z)))$
$\displaystyle=\operatorname*{\mathbb{E}}_{r\in[V]}\operatorname*{\mathbb{E}}_{z\in[(N/W_{d})^{1/d}V^{-1}]}\Delta_{V{\underline{h}}_{1}{\mathbf{e}}_{1},V{\underline{h}}_{2}{\mathbf{e}}_{2}}(f_{1}(V(x+\widetilde{P}_{[r,V]}(z))+j_{1}+\widetilde{P}(r),Vy+j_{2})$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\times
f_{2}(Vx+j_{1},V(y+\widetilde{P}_{[r,V]}(z))+j_{2}+\widetilde{P}(r)))$
$\displaystyle=\operatorname*{\mathbb{E}}_{r\in[V]}\operatorname*{\mathbb{E}}_{z\in[(N/W_{d})^{1/d}V^{-1}]}\Delta_{{\underline{h}}_{1}{\mathbf{e}}_{1},{\underline{h}}_{2}{\mathbf{e}}_{2}}(f_{1,j_{1}+\widetilde{P}(r),j_{2}}(x+\widetilde{P}_{[r,V]}(z),y)f_{2,j_{1},j_{2}+\widetilde{P}(r)}(x,y+\widetilde{P}_{[r,V]}(z))),$

where we also set

$f_{l,j_{1},j_{2}}(x,y):=(f_{l})_{(j_{1},j_{2},V)}(x,y)=f_{l}(Vx+j_{1},Vy+j_{2})$

for brevity. We observe that these $V$-tricked functions are supported on an
interval of length $N/V$. In the formula above (and in similar expressions in
the future), we assume without loss of generality that
$(N/W_{d})^{1/d}V^{-1}\in{\mathbb{N}}$ (as we may since $N$ is large compared
to $V$), so that splitting the range of $z$ into arithmetic progressions
incurs no error.

Invoking (10) with
$g=\mathcal{D}_{0}^{{\underline{h}}_{1},{\underline{h}}_{2}}(f_{1},f_{2})$ and
applying the triangle inequality to (9) gives

$\operatorname*{\mathbb{E}}_{j_{1},j_{2},r\in[V]}\left|\\!\left|\operatorname*{\mathbb{E}}_{z\in[(N/W_{d})^{1/d}V^{-1}]}\Delta_{{\underline{h}}_{1}{\mathbf{e}}_{1},{\underline{h}}_{2}{\mathbf{e}}_{2}}f_{1,j_{1}+\widetilde{P}(r),j_{2}}(\cdot+\widetilde{P}_{[r,V]}(z),\cdot)\right.\right.\\\
\left.\left.\Delta_{{\underline{h}}_{1}{\mathbf{e}}_{1},{\underline{h}}_{2}{\mathbf{e}}_{2}}f_{2,j_{1},j_{2}+\widetilde{P}(r)}(\cdot,\cdot+\widetilde{P}_{[r,V]}(z))\vphantom{\operatorname*{\mathbb{E}}_{z\in[(N/W_{d})^{1/d}V^{-1}]}}\right|\\!\right|_{({\mathbf{e}}_{1}\cdot[\pm
N/V])^{2},\;{\mathbf{e}}_{2}\cdot[\pm N/V]}^{8}\\\
\geq\exp(-\log(1/\delta)^{O(1)})(N/V)^{2}.$

Since each summand contributes at most $(N/V)^{2}$, the popularity principle
provides at least $\exp(-\log(1/\delta)^{O(1)})V^{3}$ choices of
$(j_{1},j_{2},r)\in[V]^{3}$ such that

$\left|\\!\left|\operatorname*{\mathbb{E}}_{z\in[(N/W_{d})^{1/d}V^{-1}]}\Delta_{{\underline{h}}_{1}{\mathbf{e}}_{1},{\underline{h}}_{2}{\mathbf{e}}_{2}}f_{1,j_{1}+\widetilde{P}(r),j_{2}}(\cdot+\widetilde{P}_{[r,V]}(z),\cdot)\right.\right.\\\
\left.\left.\Delta_{{\underline{h}}_{1}{\mathbf{e}}_{1},{\underline{h}}_{2}{\mathbf{e}}_{2}}f_{2,j_{1},j_{2}+\widetilde{P}(r)}(\cdot,\cdot+\widetilde{P}_{[r,V]}(z))\vphantom{\operatorname*{\mathbb{E}}_{z\in[(N/W_{d})^{1/d}V^{-1}]}}\right|\\!\right|_{({\mathbf{e}}_{1}\cdot[\pm
N/V])^{2},\;{\mathbf{e}}_{2}\cdot[\pm N/V]}^{8}\\\
\geq\exp(-\log(1/\delta)^{O(1)})(N/V)^{2}.$

For the next several steps, fix such a choice of $j_{1},j_{2},r$. For each
“good” choice of $j_{1},j_{2},r$ from the previous step, the $U^{2}\times
U^{1}$-inverse theorem (Lemma A.8) tells us that there exist a $1$-bounded
function $g:\mathbb{Z}\to\mathbb{C}$ supported on $[N]$ and phase functions
$a,b:{\mathbb{Z}}\to\mathbb{R}/\mathbb{Z}$ (all depending on
${\underline{h}}_{1},{\underline{h}}_{2},j_{1},j_{2},r$) such that

$\sum_{x,y}\operatorname*{\mathbb{E}}_{z\in[(N/W_{d})^{1/d}V^{-1}]}\Delta_{{\underline{h}}_{1}{\mathbf{e}}_{1},{\underline{h}}_{2}{\mathbf{e}}_{2}}f_{1,j_{1}+\widetilde{P}(r),j_{2}}(x+\widetilde{P}_{[r,V]}(z),y)\\\
\Delta_{{\underline{h}}_{1}{\mathbf{e}}_{1},{\underline{h}}_{2}{\mathbf{e}}_{2}}f_{2,j_{1},j_{2}+\widetilde{P}(r)}(x,y+\widetilde{P}_{[r,V]}(z))g(x)e(a(y)x+b(y))\geq\exp(-\log(1/\delta)^{O(1)})(N/V)^{2}.$

Hiding the dependence on
${\underline{h}}_{1},{\underline{h}}_{2},j_{1},j_{2},r$, we define

$\displaystyle\widetilde{f}_{1}(x,y):=e(b(y))\Delta_{{\underline{h}}_{1}{\mathbf{e}}_{1},{\underline{h}}_{2}{\mathbf{e}}_{2}}f_{1,j_{1}+\widetilde{P}(r),j_{2}}(x,y)$
and
$\displaystyle\widetilde{f}_{2}(x,y):=g(x)\Delta_{{\underline{h}}_{1}{\mathbf{e}}_{1},{\underline{h}}_{2}{\mathbf{e}}_{2}}f_{2,j_{1},j_{2}+\widetilde{P}(r)}(x,y);$

then the previous inequality can be rewritten as

$\sum_{x,y}\operatorname*{\mathbb{E}}_{z\in[(N/W_{d})^{1/d}V^{-1}]}e(a(y)x)\widetilde{f}_{1}(x+\widetilde{P}_{[r,V]}(z),y)\widetilde{f}_{2}(x,y+\widetilde{P}_{[r,V]}(z))\\\
\geq\exp(-\log(1/\delta)^{O(1)})(N/V)^{2}.$

###  4.2. Examining the structure of $a$

The main task is showing that the phase function $a$ possesses some extra
structure; specifically, we will show that $a(y)$ is approximately constant
much of the time. For future reference, define the counting operator

$\Lambda^{\prime}(a,\widetilde{f_{1}},\widetilde{f_{2}}):=\sum_{x,y}\operatorname*{\mathbb{E}}_{z\in[(N/W_{d})^{1/d}V^{-1}]}e(a(y)x)\widetilde{f_{1}}(x+\widetilde{P}_{[r,V]}(z),y)\widetilde{f_{2}}(x,y+\widetilde{P}_{[r,V]}(z)).$

The key structural result for the function $a$ is the following proposition.

######  Proposition 4.4.

For every $C_{1}>0$ there exists $C_{2}=C_{2}(C_{1},P)>0$ such that the
following holds. Let $\delta\in(0,1/10)$, let $V\leq W^{C_{1}}$ be a
nonnegative integer power of $W$, and let $r\in[V]$. Let
$\widetilde{f_{1}},\widetilde{f_{2}}:{\mathbb{Z}}^{2}\to\mathbb{C}$ be
$1$-bounded functions supported on $[N/V]^{2}$, for some integer $N\geq
C_{2}V^{C_{2}}\exp(\log(1/\delta)^{C_{2}})$ , and let
$a:{\mathbb{Z}}\to\mathbb{R}/\mathbb{Z}$ be a phase function. If

$|\Lambda^{\prime}(a,\widetilde{f_{1}},\widetilde{f_{2}})|\geq\delta(N/V)^{2},$

then there exist a positive integer power $V^{\prime}=V^{O_{C_{1},P}(1)}$ and
phases $\alpha_{0},\ldots,\alpha_{V^{\prime}-1}\in{\mathbb{R}}/{\mathbb{Z}}$
such that for at least $\exp(-\log(1/\delta)^{O_{C_{1},P}(1)})V^{\prime}$
values of $j\in[V^{\prime}]$, the bound

$\|V^{\prime}a_{(j,V^{\prime})}(y)-\alpha_{j}\|_{\mathbb{R}/\mathbb{Z}}\leq\exp(\log(1/\delta)^{O_{C_{1},P}(1)})VV^{\prime}/N$

holds for at least $\exp(-\log(1/\delta)^{O_{C_{1},P}(1)})N/(VV^{\prime})$
choices of $y\in[N/(VV^{\prime})]$.

Unfortunately, this set of $y$’s where the phase can be well-approximated by
constants may contribute little to the value of
$\Lambda^{\prime}(a,\widetilde{f_{1}},\widetilde{f_{2}})$. To obtain a
consequence better suited to our purposes, we bootstrap Proposition 4.4 and
produce some such set of $y$’s that does make a significant contribution to
$\Lambda^{\prime}(a,\widetilde{f_{1}},\widetilde{f_{2}})$. The exact statement
is as follows.

######  Proposition 4.5.

For every $C_{1}>0$ there exists $C_{2}=C_{2}(C_{1},P)>0$ such that the
following holds. Let $\delta\in(0,1/10)$, let $V\leq W^{C_{1}}$ be a
nonnegative integer power of $W$, and let $r\in[V]$. Let
$\widetilde{f_{1}},\widetilde{f_{2}}:{\mathbb{Z}}^{2}\to\mathbb{C}$ be
$1$-bounded functions supported on $[N/V]^{2}$, for some integer $N\geq
C_{2}V^{C_{2}}\exp(\log(1/\delta)^{C_{2}})$, and let
$a:{\mathbb{Z}}\to\mathbb{R}/\mathbb{Z}$ be any function. If

$|\Lambda^{\prime}(a,\widetilde{f_{1}},\widetilde{f_{2}})|\geq\delta(N/V)^{2},$

then there exist a positive integer power $V^{\prime}=V^{O_{C_{1},P}(1)}$, an
integer

$\exp(-\log(1/\delta)^{O_{C_{1},P}(1)}))N\leq N^{\prime}\leq N,$

and phases
$\alpha_{0},\ldots,\alpha_{V^{\prime}-1}\in{\mathbb{R}}/{\mathbb{Z}}$ such
that

$\sum_{j\in[V^{\prime}]}\sum_{i\in[N/N^{\prime}]}\sum_{y}\left|\sum_{x\in[N^{\prime}/(VV^{\prime})]}\operatorname*{\mathbb{E}}_{z\in[(N/W_{d})^{1/d}V^{-1}]}e(\alpha_{y\\!\\!\\!\\!\pmod{V^{\prime}}}x)\right.\\\
\widetilde{f_{1}}(V^{\prime}x+j+\frac{N^{\prime}}{V}i+\widetilde{P}_{[r,V]}(z),y)\left.\widetilde{f_{2}}(V^{\prime}x+j+\frac{N^{\prime}}{V}i,y+\widetilde{P}_{[r,V]}(z))\vphantom{\sum_{x}}\right|\\\
\geq\exp(-\log(1/\delta)^{O_{C_{1},P}(1)})(N/V)^{2}.$

Proposition 4.5 essentially says that we can replace $a(y)$ by a phase
function $y\mapsto\alpha_{y\pmod{V^{\prime}}}$ that is constant on arithmetic
progressions of difference $V^{\prime}$. The summation over
$i\in[N/N^{\prime}]$ is a technical annoyance, necessitated by the proof, that
will be easily removed in our later application of Proposition 4.5.

###### Proof.

Fix $C_{1}>0$. Proposition 4.4 applied with $\delta/2$ in place of $\delta$
tells us that the inequality

(11)
$\displaystyle|\Lambda^{\prime}({a},\widetilde{f_{1}},\widetilde{f_{2}})|\geq(\delta/2)(N/V)^{2}$

(for $a,\widetilde{f_{1}},\widetilde{f_{2}}$ satisfying the conditions of
Proposition 4.4) implies that there exist $C:=C_{2}=C_{2}(C_{1},P)>0$ and
$V^{\prime}=V^{O_{P}(1)}$ such that, on setting $\tilde{V}=VV^{\prime}$, we
obtain a set ${\mathcal{V}}\subset[V^{\prime}]$ of size
$|{\mathcal{V}}|\geq\exp(-\log(1/\delta)^{C})V^{\prime}$, and for each
$j^{\prime}\in{\mathcal{V}}$ we get a phase
$\alpha_{j^{\prime}}\in\mathbb{R}/\mathbb{Z}$ and a set
$S_{j^{\prime}}\subseteq[N/\tilde{V}]$ of size
$|S_{j^{\prime}}|\geq\exp(-\log(1/\delta)^{C})N/\tilde{V}$ satisfying

(12)
$\displaystyle\|V^{\prime}a_{({j^{\prime}},V^{\prime})}(y^{\prime})-\alpha_{j^{\prime}}\|_{{\mathbb{R}}/{\mathbb{Z}}}\leq\exp(\log(1/\delta)^{C})\tilde{V}/N$

for all $y^{\prime}\in S_{j^{\prime}}$. (Note that if this conclusion holds
for $V^{\prime}$, then it also holds with $V^{\prime}$ replaced by a larger
power of $V$, so we may assume that $V^{\prime}$ is independent of the
particular choice of $a,\widetilde{f}_{1},\widetilde{f}_{2}$.) For any
constant $C^{\prime}>C$, we can set
$N^{\prime}\sim(C^{\prime})^{-1}\exp(-2\log(1/\delta)^{2C^{\prime}})N$ and
split the $x$-variable into progressions as

$V^{\prime}x+j+\frac{N^{\prime}}{V}i\quad\textrm{for}\quad
x\in[N^{\prime}/\tilde{V}],\;\;j\in[V^{\prime}],\;\;i\in[N/N^{\prime}].$

Then for each $j^{\prime}\in{\mathcal{V}}$ and $y^{\prime}\in S_{j^{\prime}}$,
we can approximate

(13)
$\mathopen{}\left|e\mathopen{}\left(a_{({j^{\prime}},V^{\prime})}(y^{\prime})\mathopen{}\left(V^{\prime}x+j+\frac{N^{\prime}}{V}i\mathclose{}\right)\mathclose{}\right)-e\mathopen{}\left(\alpha_{j^{\prime}}x+a_{({j^{\prime}},V^{\prime})}(y^{\prime})\mathopen{}\left(j+\frac{N^{\prime}}{V}i\mathclose{}\right)\mathclose{}\right)\mathclose{}\right|\\\
\leq\exp(\log(1/\delta)^{C})\frac{N^{\prime}}{N}\leq\exp(-\log(1/\delta)^{2C^{\prime}})/2.$

Define the set

$\displaystyle\tilde{S}:=\\{y\in[N/V]:\;y=V^{\prime}y^{\prime}+j^{\prime},\;j^{\prime}\in{\mathcal{V}},\;y^{\prime}\in
S_{j^{\prime}}\\},$

which has size $|\tilde{S}|\geq\exp(-2\log(1/\delta)^{C})N/V$. Now the
approximation (13) gives

$\displaystyle\left|\sum_{x}\operatorname*{\mathbb{E}}_{z\in[(N/W_{d})^{1/d}V^{-1}]}e(a(y)x)\widetilde{f_{1}}(x+\widetilde{P}_{[r,V]}(z),y)\widetilde{f_{2}}(x,y+\widetilde{P}_{[r,V]}(z))\right.$
$\displaystyle\qquad-\sum_{j\in[V^{\prime}]}\sum_{i\in[N/N^{\prime}]}\sum_{x\in[N^{\prime}/\tilde{V}]}\operatorname*{\mathbb{E}}_{z\in[(N/W_{d})^{1/d}V^{-1}]}e\mathopen{}\left(\alpha_{y\\!\\!\\!\\!\pmod{V^{\prime}}}x+a(y)\mathopen{}\left(j+\frac{N^{\prime}}{V}i\mathclose{}\right)\mathclose{}\right)$
$\displaystyle\qquad\qquad\qquad\left.\widetilde{f_{1}}(V^{\prime}x+j+\frac{N^{\prime}}{V}i+\widetilde{P}_{[r,V]}(z),y)\widetilde{f_{2}}(V^{\prime}x+j+\frac{N^{\prime}}{V}i,y+\widetilde{P}_{[r,V]}(z))\vphantom{\sum_{x}}\right|$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\leq(\exp(-\log(1/\delta)^{2C^{\prime}})/2)N/V$

for each $y\in\tilde{S}$, and hence

$\displaystyle\sum_{y\in\tilde{S}}$
$\displaystyle\left|\sum_{x}\operatorname*{\mathbb{E}}_{z\in[(N/W_{d})^{1/d}V^{-1}]}e(a(y)x)\widetilde{f_{1}}(x+\widetilde{P}_{[r,V]}(z),y)\widetilde{f_{2}}(x,y+\widetilde{P}_{[r,V]}(z))\right.$
$\displaystyle\qquad-\sum_{j\in[V^{\prime}]}\sum_{i\in[N/N^{\prime}]}\sum_{x\in[N^{\prime}/\tilde{V}]}\operatorname*{\mathbb{E}}_{z\in[(N/W_{d})^{1/d}V^{-1}]}e\mathopen{}\left(\alpha_{y\\!\\!\\!\\!\pmod{V^{\prime}}}x+a(y)\mathopen{}\left(j+\frac{N^{\prime}}{V}i\mathclose{}\right)\mathclose{}\right)$
$\displaystyle\qquad\qquad\qquad\left.\widetilde{f_{1}}(V^{\prime}x+j+\frac{N^{\prime}}{V}i+\widetilde{P}_{[r,V]}(z),y)\widetilde{f_{2}}(V^{\prime}x+j+\frac{N^{\prime}}{V}i,y+\widetilde{P}_{[r,V]}(z))\vphantom{\sum_{x}}\right|$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\leq(\exp(-\log(1/\delta)^{2C^{\prime}})/2)(N/V)^{2}.$

The upshot is that if
$\Lambda^{\prime}(a,\widetilde{f}_{1},\widetilde{f}_{2})$ is large, then we
can use the approximation (12) provided by Proposition 4.4 to approximate

$\displaystyle\Lambda^{\prime}_{\tilde{S}}(a,\widetilde{f}_{1},\widetilde{f}_{2}):=\sum_{y\in\tilde{S}}\mathopen{}\left|\sum_{x}\operatorname*{\mathbb{E}}_{z\in[(N/W_{d})^{1/d}V^{-1}]}e(a(y)x)\widetilde{f_{1}}(x+\widetilde{P}_{[r,V]}(z),y)\widetilde{f_{2}}(x,y+\widetilde{P}_{[r,V]}(z))\mathclose{}\right|$

by a sum closer to what we are seeking. Indeed, if

(14)
$\displaystyle\Lambda^{\prime}_{\tilde{S}}(a,\widetilde{f}_{1},\widetilde{f}_{2})\geq\exp(-\log(1/\delta)^{2C^{\prime}})(N/V)^{2}$

for $C^{\prime}>C$ as above, then the triangle inequality and the long
inequality above imply that

$\sum_{y}\sum_{j\in[V^{\prime}]}\sum_{i\in[N/N^{\prime}]}\left|\sum_{x\in[N^{\prime}/\tilde{V}]}\operatorname*{\mathbb{E}}_{z\in[(N/W_{d})^{1/d}V^{-1}]}e(\alpha_{y\\!\\!\\!\\!\pmod{V^{\prime}}}x)\widetilde{f_{1}}(V^{\prime}x+j+\frac{N^{\prime}}{V}i+\widetilde{P}_{[r,V]}(z),y)\right.\\\
\left.\widetilde{f_{2}}(V^{\prime}x+j+\frac{N^{\prime}}{V}i,y+\widetilde{P}_{[r,V]}(z))\vphantom{\sum_{x}}\right|\geq(\exp(-\log(1/\delta)^{2C^{\prime}})/2)(N/V)^{2},$

which establishes the conclusion of the proposition.

The lower bound (14) does not always hold, however. We will show that in this
case, we can “throw out” the $y$-values in $\widetilde{S}$ and repeat the
argument from the previous paragraph to obtain a new set $\widetilde{S}$ which
is mostly disjoint from the set that we threw out; we can then iterate this
procedure, which is guaranteed to terminate after a bounded number of steps
because of the disjointness of the sets $\widetilde{S}$. The details are as
follows.

We first note that if $S\subseteq[N/\widetilde{V}]$ and
$a^{\prime}:S\to\mathbb{R}/\mathbb{Z}$ is a function such that
$V^{\prime}a^{\prime}(y)$ assumes each integer multiple of $1/|S|$ exactly
once as $y$ ranges over $S$, then, for any interval
$I\subseteq\mathbb{R}/\mathbb{Z}$, we have the bound

(15) $|\\{y\in S:V^{\prime}a^{\prime}(y)\in I\\}|\leq 1+|S|\cdot|I|\leq
1+(N/\widetilde{V})|I|.$

In this case, we will say that $a^{\prime}$ is _uniformly distributed_ on $S$.

We also note that if $S\subseteq[N/V]$ and
$a^{\prime\prime}:[N/V]\to\mathbb{R}/\mathbb{Z}$ is any function that agrees
with $a$ on $[N/V]\setminus S$, then

(16) $\displaystyle\Lambda^{\prime}(a^{\prime\prime},1_{[N/V]\setminus
S}\widetilde{f}_{1},\widetilde{f}_{2})=\Lambda^{\prime}(a,1_{[N/V]\setminus
S}\widetilde{f}_{1},\widetilde{f}_{2})$

(here we write $(1_{[N/V]\setminus S}\widetilde{f}_{1})(x,y)$ for
$1_{[N/V]\setminus S}(y)\widetilde{f}_{1}(x,y)$). Indeed, there is no
contribution from the values of $y$ where $a(y)\neq a^{\prime\prime}(y)$
because for such $y$ we have $(1_{[N/V]\setminus
S}\widetilde{f}_{1})(x+\widetilde{P}_{[r,V]}(z),y)=0$.

To begin our iterative procedure, set $\widetilde{S}_{0}=\emptyset$ and
$a_{0}=a$. For $\ell=1,2,\ldots$, we will construct phases
$\alpha_{\ell,j^{\prime}}$ (for $j^{\prime}\in[V^{\prime}]$), a set
$\widetilde{S}_{\ell}$, and a phase function $a_{\ell}$ that agrees with $a$
on the complement of
$\widetilde{S}_{\leq\ell}:=\cup_{\ell^{\prime}\leq\ell}\widetilde{S}_{\ell^{\prime}}$
and is uniformly distributed on the intersection of $\widetilde{S}_{\leq\ell}$
with each arithmetic progression of common difference $V^{\prime}$. The
$\ell$-th stage of the iteration begins with the inequality

$\Lambda^{\prime}(a,1_{[N/V]\setminus\tilde{S}_{\leq\ell-1}}\widetilde{f}_{1},\widetilde{f}_{2})\geq(\delta/2)(N/V)^{2}$

(which certainly holds for $\ell=1$). Then, by (16), we also have

$\Lambda^{\prime}(a_{\ell-1},1_{[N/V]\setminus\tilde{S}_{\leq\ell-1}}\widetilde{f}_{1},\widetilde{f}_{2})\geq(\delta/2)(N/V)^{2}.$

Arguing as in the first paragraph of the proof, with $a_{\ell-1}$ instead of
$a$ and $1_{[N/V]\setminus\tilde{S}_{\leq\ell-1}}\widetilde{f}_{1}$ instead of
$\widetilde{f}_{1}$, we obtain phases $\alpha_{\ell,j^{\prime}}$ (for
$j^{\prime}\in[V^{\prime}]$) and a set $\widetilde{S}_{\ell}$. If (14) holds,
then we obtain the conclusion of the proposition and our iterative procedure
terminates. If not, then, by induction on $\ell$ and the triangle inequality,
we have

(17)
$\Lambda^{\prime}(a,1_{[N/V]\setminus\widetilde{S}_{\leq\ell}}\widetilde{f}_{1},\widetilde{f}_{2})\geq(\delta-\ell\exp(-\log(1/\delta)^{C^{\prime}}))(N/V)^{2}>(\delta/2)(N/V)^{2}$

as long as $\ell<(\delta/2)\exp(\log(1/\delta)^{C^{\prime}})$. Now let
$a_{\ell}$ be a function that agrees with $a$ on
$[N/V]\setminus\widetilde{S}_{\leq\ell}$ and that is uniformly distributed on
the intersection of $\widetilde{S}_{\leq\ell}$ with each arithmetic
progression of common difference $V^{\prime}$. This completes the $\ell$-th
step of the iteration and puts us in a position to perform the $(\ell+1)$-th
step.

It remains to analyze the sizes of the sets $\widetilde{S}_{\leq\ell}$ and
argue that the procedure terminates after a bounded number of steps. By (15)
applied to each of the sets $S_{\ell,j^{\prime}}$ (for
$j^{\prime}\in[V^{\prime}]$), we have

$|\widetilde{S}_{\ell}\cap\widetilde{S}_{\leq\ell-1}|\leq
V^{\prime}(1+2(N/\widetilde{V})\exp(\log(1/\delta)^{C})\widetilde{V}/N)<3V^{\prime}\exp(\log(1/\delta)^{C}).$

Hence

$\displaystyle|\widetilde{S}_{\leq\ell}|$
$\displaystyle>|\widetilde{S}_{\leq\ell-1}|+|\widetilde{S}_{\ell}|-3V^{\prime}\exp(\log(1/\delta)^{C})$
$\displaystyle\geq|\widetilde{S}_{\leq\ell-1}|+\exp(-2\log(1/\delta)^{C})N/V-3V^{\prime}\exp(\log(1/\delta)^{C})$
$\displaystyle\geq|\widetilde{S}_{\leq\ell-1}|+(1/2)\exp(-2\log(1/\delta)^{C})N/V$

(using the assumption that $N$ is large), and by induction we obtain

$|\widetilde{S}_{\leq\ell}|>(\ell/2)\exp(-2\log(1/\delta)^{C})N/V.$

Since $\widetilde{S}_{\leq\ell}$ is a subset of $[N/V]$, we conclude that the
iterative procedure must terminate in at most $2\exp(-2\log(1/\delta)^{C})$
steps, and, in particular, a suitable choice of $C^{\prime}$ guarantees that
the estimate in (17) holds for all $\ell$ in the iterative procedure. ∎

###  4.3. Auxiliary norm control on $f_{1}$.

Recall from before that we have the lower bound

$\sum_{x,y}\operatorname*{\mathbb{E}}_{z\in[(N/W_{d})^{1/d}V^{-1}]}\Delta_{{\underline{h}}_{1}{\mathbf{e}}_{1},{\underline{h}}_{2}{\mathbf{e}}_{2}}f_{1,j_{1}+\widetilde{P}(r),j_{2}}(x+\widetilde{P}_{[r,V]}(z),y)\\\
\Delta_{{\underline{h}}_{1}{\mathbf{e}}_{1},{\underline{h}}_{2}{\mathbf{e}}_{2}}f_{2,j_{1},j_{2}+\widetilde{P}(r)}(x,y+\widetilde{P}_{[r,V]}(z))g(x)e(a(y)x+b(y))\geq\exp(-\log(1/\delta)^{O(1)})(N/V)^{2}$

for at least

$\exp(-\log(1/\delta)^{O(1)})(N/V)^{k+\ell-3}$

tuples $({\underline{h}}_{1},{\underline{h}}_{2})\in{\mathbb{Z}}^{k+\ell-3}$
and at least $\exp(-\log(1/\delta)^{O(1)})V^{3}$ values
$(j_{1},j_{2},r)\in[V]^{3}$, where $g,a,b$ depend on
${\underline{h}}_{1},{\underline{h}}_{2},j_{1},j_{2},r$. Proposition 4.5 gives
an integer

$\exp(-\log(1/\delta)^{O(1)})N\leq N^{\prime}\leq N,$

a positive integer power $V^{\prime}=V^{O(1)}$, and $1$-bounded functions
$b_{1,j,j^{\prime},i},b_{2,j,j^{\prime},i}:{\mathbb{Z}}\to{\mathbb{C}}$ (the
latter dependent on ${\underline{h}}_{1},{\underline{h}}_{2},j_{1},j_{2},r$)
such that

$\sum_{i\in[N/N^{\prime}]}\sum_{j,j^{\prime}\in[V^{\prime}]}\sum_{y}\sum_{x\in[N^{\prime}/(VV^{\prime})]}\operatorname*{\mathbb{E}}_{z\in[(N/W_{d})^{1/d}V^{-1}]}b_{1,j,j^{\prime},i}(x)b_{2,j,j^{\prime},i}(y)\\\
\Delta_{{\underline{h}}_{1}{\mathbf{e}}_{1},{\underline{h}}_{2}{\mathbf{e}}_{2}}f_{1,j_{1}+\widetilde{P}(r),j_{2}}(V^{\prime}x+j+\frac{N^{\prime}}{V}i+\widetilde{P}_{[r,V]}(z),V^{\prime}y+j^{\prime})\\\
\Delta_{{\underline{h}}_{1}{\mathbf{e}}_{1},{\underline{h}}_{2}{\mathbf{e}}_{2}}f_{1,j_{1},j_{2}+\widetilde{P}(r)}(V^{\prime}x+j+\frac{N^{\prime}}{V}i,V^{\prime}y+j^{\prime}+\widetilde{P}_{[r,V]}(z))\\\
\geq\exp(-\log(1/\delta)^{O(1)})(N/V)^{2}$

for at least $\exp(-\log(1/\delta)^{O(1)})V^{3}$ values
$(j_{1},j_{2},r)\in[V]^{3}$. By the pigeonhole principle, we can choose a
single $i\in[N/N^{\prime}]$ for which the sum over $j,j^{\prime},y,x,z$
satisfies the lower bound, at the cost of losing an extra factor of
$\exp(-\log(1/\delta)^{O(1)})$, modifying $b_{1,j,j^{\prime},i}$ by a phase if
necessary, and dropping the index $i$ from $b_{1,j,j^{\prime},i}$,
$b_{2,j,j^{\prime},i}$. We then $V^{\prime}$-trick the polynomial
$\widetilde{P}_{[r,V]}$, simplify the notation by setting

(18)
$\begin{split}f^{l}_{j_{1},j_{2},j,j^{\prime}}(x,y)&:=\Delta_{{\underline{h}}_{1}{\mathbf{e}}_{1},{\underline{h}}_{2}{\mathbf{e}}_{2}}f_{l,j_{1},j_{2}}(V^{\prime}x+j+\frac{N^{\prime}}{V}i,V^{\prime}y+j^{\prime})\\\
&=\Delta_{V{\underline{h}}_{1}{\mathbf{e}}_{1},V{\underline{h}}_{2}{\mathbf{e}}_{2}}f_{l}(VV^{\prime}x+Vj+j_{1}+N^{\prime}i,VV^{\prime}y+Vj^{\prime}+j_{2})\end{split}$

for $l=1,2$, and shift $y\mapsto
y-\widetilde{P}_{[Vr^{\prime}+r,VV^{\prime}]}(z)$, obtaining

$\sum_{j,j^{\prime},r^{\prime}\in[V^{\prime}]}\sum_{y}\sum_{x\in[N^{\prime}/(VV^{\prime})]}\operatorname*{\mathbb{E}}_{z\in[(N/W_{d})^{1/d}(VV^{\prime})^{-1}]}b_{1,j,j^{\prime}}(x)b_{2,j,j^{\prime}}(y-\widetilde{P}_{[Vr^{\prime}+r,VV^{\prime}]}(z))\\\
f^{1}_{j_{1}+\widetilde{P}(r),j_{2},j+\widetilde{P}_{[r,V]}(r^{\prime}),j^{\prime}}(x+\widetilde{P}_{[Vr^{\prime}+r,VV^{\prime}]}(z),y-\widetilde{P}_{[Vr^{\prime}+r,VV^{\prime}]}(z))\\\
f^{2}_{j_{1},j_{2}+\widetilde{P}(r),j,j^{\prime}+\widetilde{P}_{[r,V]}(r^{\prime})}(x,y)\geq\exp(-\log(1/\delta)^{O(1)})(N/V)^{2}$

for the aforementioned values $(j_{1},j_{2},r)\in[V]^{3}$. Importantly, this
new expression is amenable to an application of a Sárközy-type estimate. By
Corollary D.10 applied with

$b_{1,j,j^{\prime}}(x)1_{[N^{\prime}/(VV^{\prime})]}(x)f^{2}_{j_{1},j_{2}+\widetilde{P}(r),j,j^{\prime}+\widetilde{P}_{[r,V]}(r^{\prime})}(x,y),\;\;b_{2,j,j^{\prime}}(y)f^{1}_{j_{1}+\widetilde{P}(r),j_{2},j+\widetilde{P}_{[r,V]}(r^{\prime}),j^{\prime}}(x,y)$

in place of $f_{0},f_{1}$ and with
${\textbf{v}}={\mathbf{e}}_{1}-{\mathbf{e}}_{2}$, we obtain the lower bound

$\sum_{j,j^{\prime},r^{\prime}\in[V^{\prime}]}\sum_{x,y}\mathopen{}\left|\sum_{z\in[\pm
N^{\prime\prime}/(VV^{\prime})]}b_{2,j,j^{\prime}}(y-qz)f^{1}_{j_{1}+\widetilde{P}(r),j_{2},j+\widetilde{P}_{[r,V]}(r^{\prime}),j^{\prime}}(x+qz,y-qz)\mathclose{}\right|\\\
\geq\exp(-\log(1/\delta)^{O(1)})(N/V)^{3}$

for some positive integers $q\leq\exp(\log(1/\delta)^{O(1)})$ and
$\exp(-\log(1/\delta)^{O(1)})N\leq N^{\prime\prime}\leq N$. We apply the
Cauchy–Schwarz inequality to remove the absolute value and then change
variables $(x,y)\mapsto(x-qz,y+qz)$ and $z\mapsto-z$, so that

$\sum_{j,j^{\prime},r^{\prime}\in[V^{\prime}]}\sum_{x,y,z}\mu_{N^{\prime\prime}/(VV^{\prime})}(z)\Delta_{qz}b_{2,j,j^{\prime}}(y)\Delta_{qz({\mathbf{e}}_{2}-{\mathbf{e}}_{1})}f^{1}_{j_{1}+\widetilde{P}(r),j_{2},j+\widetilde{P}_{[r,V]}(r^{\prime}),j^{\prime}}(x,y)\\\
\geq\exp(-\log(1/\delta)^{O(1)})V^{\prime}(N/V)^{2}.$

In order to get rid of $b_{2,j,j^{\prime}}$, we introduce an additional
averaging over $[\pm N/(VV^{\prime})]$ in the $x$-direction and then apply the
Cauchy–Schwarz inequality to double this new variable. Using Lemma 3.4(iv) to
remove $q$, and summing over the admissible values of $j_{1},j_{2},r\in[V]$,
we thus obtain

$\sum_{\begin{subarray}{c}j_{1},j_{2},r\in[V],\\\
j,j^{\prime},r^{\prime}\in[V^{\prime}]\end{subarray}}\|f^{1}_{j_{1}+\widetilde{P}(r),j_{2},j+\widetilde{P}_{[r,V]}(r^{\prime}),j^{\prime}}\|_{({\mathbf{e}}_{2}-{\mathbf{e}}_{1})\cdot[\pm
N/(VV^{\prime})],\;{\mathbf{e}}_{1}\cdot[\pm N/(VV^{\prime})]}^{4}\\\
\geq\exp(-\log(1/\delta)^{O(1)})VV^{\prime}N^{2}.$

We now want to remove the shifts by $\widetilde{P}(r)$ and
$\widetilde{P}_{[r,V]}(r^{\prime})$ from the indices $j_{1},j^{\prime}$.
Notice first that the function
$f^{1}_{j_{1},j_{2},j+s_{3}V^{\prime},j^{\prime}+s_{4}V^{\prime}}$ is a
translate of the function $f^{1}_{j_{1},j_{2},j,j^{\prime}}$ and hence
$\left\|f^{1}_{j_{1},j_{2},j,j^{\prime}}\right\|_{({\mathbf{e}}_{2}-{\mathbf{e}}_{1})\cdot[\pm
N/(VV^{\prime})],\;{\mathbf{e}}_{1}\cdot[\pm N/(VV^{\prime})]}$ depends only
on the residue classes of $j,j^{\prime}$ modulo $V^{\prime}$. We can therefore
replace the summation over $j,j^{\prime}\in[V^{\prime}]$ by a summation over
$j,j^{\prime}\in{\mathbb{Z}}/V^{\prime}{\mathbb{Z}}$ and then shift $j\mapsto
j-\widetilde{P}_{[r,V]}(r^{\prime})$ to obtain

$\sum_{\begin{subarray}{c}j_{1},j_{2},r\in[V]\end{subarray}}\sum_{j,j^{\prime}\in{\mathbb{Z}}/V^{\prime}{\mathbb{Z}}}\|f^{1}_{j_{1}+\widetilde{P}(r),j_{2},j,j^{\prime}}\|_{({\mathbf{e}}_{2}-{\mathbf{e}}_{1})\cdot[\pm
N/(VV^{\prime})],\;{\mathbf{e}}_{1}\cdot[\pm N/(VV^{\prime})]}^{4}\\\
\geq\exp(-\log(1/\delta)^{O(1)})VN^{2}.$

Similarly, the identity

$\displaystyle
f^{1}_{j_{1}+s_{1}V,j_{2}+s_{2}V,j,j^{\prime}}=f^{1}_{j_{1},j_{2},j+s_{1},j^{\prime}+s_{2}},$

makes
$\sum_{j,j^{\prime}\in{\mathbb{Z}}/V^{\prime}{\mathbb{Z}}}\|f^{1}_{j_{1}+\widetilde{P}(r),j_{2},j,j^{\prime}}\|_{({\mathbf{e}}_{2}-{\mathbf{e}}_{1})\cdot[\pm
N/(VV^{\prime})],\;{\mathbf{e}}_{1}\cdot[\pm N/(VV^{\prime})]}^{4}$ depend
only on the residue class of $j_{1},j_{2}$ modulo $V$, and so we can replace
the sum over $j_{1},j_{2}\in[V]$ by the sum over
$j_{1},j_{2}\in{\mathbb{Z}}/V{\mathbb{Z}}$. Shifting $j_{1}\mapsto
j_{1}-\tilde{P}(r)$, we then get

$\sum_{\begin{subarray}{c}j_{1},j_{2}\in{\mathbb{Z}}/V{\mathbb{Z}}\end{subarray}}\sum_{j,j^{\prime}\in{\mathbb{Z}}/V^{\prime}{\mathbb{Z}}}\|f^{1}_{j_{1},j_{2},j,j^{\prime}}\|_{({\mathbf{e}}_{2}-{\mathbf{e}}_{1})\cdot[\pm
N/(VV^{\prime})],\;{\mathbf{e}}_{1}\cdot[\pm N/(VV^{\prime})]}^{4}\\\
\geq\exp(-\log(1/\delta)^{O(1)})N^{2},$

and so

$\|\Delta_{V{\underline{h}}_{1}{\mathbf{e}}_{1},V{\underline{h}}_{2}{\mathbf{e}}_{2}}f_{1}\|_{({\mathbf{e}}_{2}-{\mathbf{e}}_{1})VV^{\prime}\cdot[\pm
N/(VV^{\prime})],\;{\mathbf{e}}_{1}VV^{\prime}\cdot[\pm
N/(VV^{\prime})]}^{4}\geq\exp(-\log(1/\delta)^{O(1)})N^{2}.$

Since this holds for at least $\exp(-\log(1/\delta)^{O(1)})(N/V)^{k+\ell-3}$
choices of
$({\underline{h}}_{1},{\underline{h}}_{2})\in{\mathbb{Z}}^{k+\ell-3}$, we get
from properties (i) and (vi) of Lemma 3.4 that

(19) $\|f_{1}\|^{2^{k+\ell-1}}_{({\mathbf{e}}_{1}VV^{\prime}\cdot[\pm
N/(VV^{\prime})])^{k-1},\;({\mathbf{e}}_{2}-{\mathbf{e}}_{1})VV^{\prime}\cdot[\pm
N/(VV^{\prime})],\;({\mathbf{e}}_{2}VV^{\prime}\cdot[\pm
N/(VV^{\prime})])^{\ell-1}}\\\ \geq\exp(-\log(1/\delta)^{O(1)})N^{2}.$

###  4.4. Completing the proof of Proposition 4.3

So far, we have proved that if

$|\Lambda^{W}(f_{0},f_{1},f_{2})|\geq\delta N^{2}$

implies that

$\|f_{0}\|_{({\mathbf{e}}_{1}V\cdot[\pm
N/V])^{k},\;({\mathbf{e}}_{2}V\cdot[\pm
N/V])^{\ell}}^{2^{k+\ell}}\geq\exp(-\log(1/\delta)^{O(1)})N^{2},$

then the norm-control (19) also follows. This lower bound is not particularly
useful in itself, but we will use it as an intermediate step towards the
desired norm-control on $f_{0}$. To this end, we first use stashing to replace
$f_{1}$ in $\Lambda^{W}$ with the dual function

$\displaystyle{\mathcal{D}}_{1}(f_{0},f_{2})(x,y):=\operatorname*{\mathbb{E}}_{z\in[(N/W_{d})^{1/d}}f_{0}(x-\widetilde{P}(z),y)f_{2}(x-\widetilde{P}(z),y+\widetilde{P}(z)),$

so that (19) holds with ${\mathcal{D}}_{1}(f_{0},f_{2})$ in place of $f_{1}$.
We then apply the dual–difference interchange (Lemma 3.6) to this expression,
so that

$\sum_{\begin{subarray}{c}{\underline{h}}_{1}\in\mathbb{Z}^{k-1},\\\
{\underline{h}}_{2}\in\mathbb{Z}^{\ell-1}\end{subarray}}\mu_{N/(VV^{\prime})}({\underline{h}}_{1},{\underline{h}}_{2})\cdot\|\mathcal{D}_{1}^{{\underline{h}}_{1},{\underline{h}}_{2}}(f_{0},f_{2})\|_{({\mathbf{e}}_{2}-{\mathbf{e}}_{1})VV^{\prime}\cdot[\pm
N/(VV^{\prime})]}^{2}\\\ \geq\exp(-\log(1/\delta)^{O(1)})N^{2},$

where

$\mathcal{D}_{1}^{{\underline{h}}_{1},{\underline{h}}_{2}}(f_{0},f_{2})(x,y):=\operatorname*{\mathbb{E}}_{z\in[(N/W_{d})^{1/d}}\Delta_{VV^{\prime}{\underline{h}}_{1}{\mathbf{e}}_{1},VV^{\prime}{\underline{h}}_{2}{\mathbf{e}}_{2}}(f_{0}(x-\widetilde{P}(z),y)f_{2}(x-\widetilde{P}(z),y+\widetilde{P}(z))).$

Thus for at least $\exp(-\log(1/\delta)^{O(1)})(N/(VV^{\prime}))^{k+\ell-2}$
values of
$({\underline{h}}_{1},{\underline{h}}_{2})\in{\mathbb{Z}}^{k+\ell-2}$, we have
the lower bound

$\|\mathcal{D}_{1}^{{\underline{h}}_{1},{\underline{h}}_{2}}(f_{0},f_{2})\|_{({\mathbf{e}}_{2}-{\mathbf{e}}_{1})VV^{\prime}\cdot[\pm
N/(VV^{\prime})]}^{2}\geq\exp(-\log(1/\delta)^{O(1)})N^{2}.$

We temporarily fix such a choice of
$({\underline{h}}_{1},{\underline{h}}_{2})\in{\mathbb{Z}}^{k+\ell-2}$ and
repeat the above procedure of splitting the domains of $x,y$ into arithmetic
progressions of difference $VV^{\prime}$. This yields

$\displaystyle\mathcal{D}_{1}^{{\underline{h}}_{1},{\underline{h}}_{2}}(f_{0},f_{2})(VV^{\prime}x+j_{1},VV^{\prime}y+j_{2})$
$\displaystyle\qquad\qquad=\operatorname*{\mathbb{E}}_{z\in[(N/W_{d})^{1/d}]}\Delta_{VV^{\prime}{\underline{h}}_{1}{\mathbf{e}}_{1},VV^{\prime}{\underline{h}}_{2}{\mathbf{e}}_{2}}(f_{0}(VV^{\prime}x+j_{1}-\widetilde{P}(z),VV^{\prime}y+j_{2})$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad\times
f_{2}(VV^{\prime}x+j_{1}-\widetilde{P}(z),VV^{\prime}y+j_{2}+\widetilde{P}(z)))$
$\displaystyle\qquad\qquad=\operatorname*{\mathbb{E}}_{r\in[VV^{\prime}]}\operatorname*{\mathbb{E}}_{z\in[(N/W_{d})^{1/d}(VV^{\prime})^{-1}]}\Delta_{{\underline{h}}_{1}{\mathbf{e}}_{1},{\underline{h}}_{2}{\mathbf{e}}_{2}}(f_{0,j_{1}-\widetilde{P}(r),j_{2}}(x-\widetilde{P}_{[r,VV^{\prime}]}(z),y)$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad\times
f_{2,j_{1}-\widetilde{P}(r),j_{2}+\widetilde{P}(r)}(x-\widetilde{P}_{[r,VV^{\prime}]}(z),y+\widetilde{P}_{[r,VV^{\prime}]}(z))),$

where
$f_{l,j_{1},j_{2}}(x,y)=(f_{l})_{(j_{1},j_{2},VV^{\prime})}(x,y)=f_{l}(VV^{\prime}x+j_{1},VV^{\prime}y+j_{2})$
for $l=0,2$. Hence

$\operatorname*{\mathbb{E}}_{j_{1},j_{2},r\in[VV^{\prime}]}\left|\\!\left|\operatorname*{\mathbb{E}}_{z\in[(N/W_{d})^{1/d}(VV^{\prime})^{-1}]}\Delta_{{\underline{h}}_{1}{\mathbf{e}}_{1},{\underline{h}}_{2}{\mathbf{e}}_{2}}f_{0,j_{1}-\widetilde{P}(r),j_{2}}(\cdot-\widetilde{P}_{[r,VV^{\prime}]}(z),\cdot)\right.\right.\\\
\left.\left.\Delta_{{\underline{h}}_{1}{\mathbf{e}}_{1},{\underline{h}}_{2}{\mathbf{e}}_{2}}f_{2,j_{1}-\widetilde{P}(r),j_{2}+\widetilde{P}(r)}(\cdot-\widetilde{P}_{[r,VV^{\prime}]}(z),\cdot+\widetilde{P}_{[r,VV^{\prime}]}(z)))\vphantom{\operatorname*{\mathbb{E}}_{z\in[(N/W_{d})^{1/d}(VV^{\prime})^{-1}]}}\right|\\!\right|_{({\mathbf{e}}_{2}-{\mathbf{e}}_{1})\cdot[\pm
N/(VV^{\prime})]}^{2}\\\
\geq\exp(-\log(1/\delta)^{O(1)})(N/(VV^{\prime}))^{2}.$

Applying the inverse theorem for the $U^{1}$ norm (Lemma A.2)333Technically,
to apply this result, the length of the boxes should be larger by a factor
$\exp(\log(1/\delta)^{O(1)})$ than the support of the function whose norm we
are evaluating. This can be ensured by replacing the box
$({\mathbf{e}}_{2}-{\mathbf{e}}_{1})VV^{\prime}\cdot[\pm N/(VV^{\prime})]$ by
$({\mathbf{e}}_{2}-{\mathbf{e}}_{1})VV^{\prime}\cdot[\pm
N^{\prime}/(VV^{\prime})]$ (with $N^{\prime}\asymp\exp(\log(1/\delta)^{C})N$
for an appropriate $C>0$) before performing the Dual-Difference Interchange
using Lemma 3.4(iv). for the values $(j_{1},j_{2},r)\in[VV^{\prime}]^{3}$
where the above norm is at least
$\exp(-\log(1/\delta)^{O(1)})(N/(VV^{\prime}))^{2}$, we obtain a $1$-bounded
function $b:\mathbb{Z}\to\mathbb{C}$ (depending on
${\underline{h}}_{1},{\underline{h}}_{2},j_{1},j_{2},r$) such that

$\sum_{x,y}\operatorname*{\mathbb{E}}_{z\in[(N/W_{d})^{1/d}(VV^{\prime})^{-1}]}b(x+y)\Delta_{{\underline{h}}_{1}{\mathbf{e}}_{1},{\underline{h}}_{2}{\mathbf{e}}_{2}}f_{0,j_{1}-\widetilde{P}(r),j_{2}}(x-\widetilde{P}_{[r,VV^{\prime}]}(z),y)\\\
\Delta_{{\underline{h}}_{1}{\mathbf{e}}_{1},{\underline{h}}_{2}{\mathbf{e}}_{2}}f_{2,j_{1}-\widetilde{P}(r),j_{2}+\widetilde{P}(r)}(x-\widetilde{P}_{[r,VV^{\prime}]}(z),y+\widetilde{P}_{[r,VV^{\prime}]}(z))\\\
\geq\exp(-\log(1/\delta)^{O(1)})(N/(VV^{\prime}))^{2}.$

Changing variables
$(x,y)\mapsto(x+\widetilde{P}_{[r,VV^{\prime}]}(z),y-\widetilde{P}_{[r,VV^{\prime}]}(z))$
simplifies this expression to

$\sum_{x,y}\operatorname*{\mathbb{E}}_{z\in[(N/W_{d})^{1/d}(VV^{\prime})^{-1}]}b(x+y)\Delta_{{\underline{h}}_{1}{\mathbf{e}}_{1},{\underline{h}}_{2}{\mathbf{e}}_{2}}f_{0,j_{1}-\widetilde{P}(r),j_{2}}(x,y-\widetilde{P}_{[r,VV^{\prime}]}(z))\\\
\Delta_{{\underline{h}}_{1}{\mathbf{e}}_{1},{\underline{h}}_{2}{\mathbf{e}}_{2}}f_{2,j_{1}-\widetilde{P}(r),j_{2}+\widetilde{P}(r)}(x,y)\\\
\geq\exp(-\log(1/\delta)^{O(1)})(N/(VV^{\prime}))^{2}.$

After an application of Corollary D.10, with

$\displaystyle
b(x+y)\Delta_{{\underline{h}}_{1}{\mathbf{e}}_{1},{\underline{h}}_{2}{\mathbf{e}}_{2}}f_{2,j_{1}-\widetilde{P}(r),j_{2}+\widetilde{P}(r)}(x,y)\quad\textrm{and}\quad\Delta_{{\underline{h}}_{1}{\mathbf{e}}_{1},{\underline{h}}_{2}{\mathbf{e}}_{2}}f_{0,j_{1}-\widetilde{P}(r),j_{2}}(x,y)$

in place of $f_{0}(x,y),f_{1}(x,y)$ and with ${\textbf{v}}={\mathbf{e}}_{2}$),
maneuvers similar to those in the proof of Theorem 4.1 give

$\|f_{0}\|_{({\mathbf{e}}_{1}\tilde{V}\cdot[N/\tilde{V}])^{k-1},\;({\mathbf{e}}_{2}\tilde{V}\cdot[N/\tilde{V}])^{\ell}}^{2^{k+\ell-1}}\geq\exp(-\log(1/\delta)^{O(1)})N^{2}$

with $\tilde{V}=VV^{\prime}.$ Exchanging the roles of $x$ and $y$ gives the
last assertion of the proposition.

##  5\. Reducing Proposition 4.4 to a nilsequence problem

The next two sections are devoted to the proof of Proposition 4.4; this will
complete the degree-lowering argument from the previous section. Recall the
counting operator

$\Lambda^{\prime}(a,\widetilde{f_{1}},\widetilde{f_{2}})=\sum_{x,y}\operatorname*{\mathbb{E}}_{z\in[(N/W_{d})^{1/d}V^{-1}]}e(a(y)x)\widetilde{f_{1}}(x+\widetilde{P}_{[r,V]}(z),y)\widetilde{f_{2}}(x,y+\widetilde{P}_{[r,V]}(z));$

our goal is to show that if
$\Lambda^{\prime}(a,\widetilde{f_{1}},\widetilde{f_{2}})$ is large for some
$1$-bounded functions $\widetilde{f_{1}},\widetilde{f_{2}}$, then there are
many arithmetic progressions of difference $V^{\prime}=V^{O_{P}(1)}$ on each
of which the phase $a$ is approximately constant. In this section we will use
higher-order Fourier analysis manipulations to replace the functions
$\widetilde{f}_{1},\widetilde{f}_{2}$ with nilsequences; in the next section
we will use sophisticated machinery from the theory of nilsequences to
complete the proof of Proposition 4.4. Our starting point is the following
norm-control.

######  Proposition 5.1.

For every $C_{1}>0$ there exists $C_{2}=C_{2}(C_{1},P)>0$ such that the
following holds. Let $\delta\in(0,1/10)$, let $V\leq W^{C_{1}}$ be a
nonnegative integer power of $W$, and let $r\in[V]$. Let
$\widetilde{f_{1}},\widetilde{f_{2}}:{\mathbb{Z}}^{2}\to\mathbb{C}$ be
$1$-bounded functions supported on $[N/V]^{2}$, for some integer $N\geq
C_{2}V^{C_{2}}\delta^{-C_{2}}$, and let $a:\mathbb{Z}\to\mathbb{R}/\mathbb{Z}$
be a phase function. If

$|\Lambda^{\prime}(a,\widetilde{f_{1}},\widetilde{f_{2}})|\geq\delta(N/V)^{2},$

then we have the norm-control

$\displaystyle\|\widetilde{f_{2}}\|_{({\mathbf{e}}_{2}-{\mathbf{e}}_{1})\cdot[\pm
N/V],\;{\mathbf{e}}_{1}\cdot[\pm
N/V]}^{4}\gg_{C_{1},P}\delta^{O_{C_{1},P}(1)}(N/V)^{2}.$

Naïvely, one would expect to have
$\\{{\mathbf{e}}_{2}-{\mathbf{e}}_{1},\;{\mathbf{e}}_{2}\\}$-control on
$\widetilde{f_{2}}$. Our norm-control looks slightly different because, as
will become clear in the proof, taking discrete derivatives in the
${\mathbf{e}}_{1}$-direction is very convenient for dealing with the
$e(a(y)x)$ term in $\Lambda^{\prime}$. The argument would give the same
conclusion with
$\|\widetilde{f_{1}}\|_{({\mathbf{e}}_{2}-{\mathbf{e}}_{1})\cdot[\pm
N/V],\;({\mathbf{e}}_{1}\cdot[\pm N/V])^{2}}$, but we do not need this.

###### Proof.

We fix $C_{1}>0$ and let all the constants depend on $C_{1},P$. We introduce
an extra averaging over $[N/V]$ in the $x$-direction444If we did not want the
range of the new variable $h$ to be restricted, then we could apply the
Cauchy–Schwarz inequality directly. and apply the Cauchy–Schwarz inequality in
order to double the variable $x$; this gives

(20)
$\sum_{x,y,h}\mu_{N/V}(h)\operatorname*{\mathbb{E}}_{z\in[(N/W_{d})^{1/d}V^{-1}]}e(a(y)h)\\\
\Delta_{h{\mathbf{e}}_{1}}\widetilde{f_{1}}(x+\widetilde{P}_{[r,V]}(z),y)\Delta_{h{\mathbf{e}}_{1}}\widetilde{f_{2}}(x,y+\widetilde{P}_{[r,V]}(z))\geq\delta^{2}(N/V)^{2}.$

Shifting $x\mapsto x-\widetilde{P}_{[r,V]}(z)$ gives

$\sum_{x,y,h}\mu_{N/V}(h)\operatorname*{\mathbb{E}}_{z\in[(N/W_{d})^{1/d}V^{-1}]}e(a(y)h)\\\
\Delta_{h{\mathbf{e}}_{1}}\widetilde{f_{1}}(x,y)\Delta_{h{\mathbf{e}}_{1}}\widetilde{f_{2}}(x-\widetilde{P}_{[r,V]}(z),y+\widetilde{P}_{[r,V]}(z))\geq\delta^{2}(N/V)^{2}.$

The crucial point is that now only $\widetilde{f}_{2}$ has
$\widetilde{P}_{[r,V]}(z)$ in its argument and so we can apply the Sárközy-
type estimate (Corollary D.10) (after using the popularity principle to find
many $h$’s for which the inner expression is large in absolute value). Hence
there exist positive integers555A direct application of Corollary D.10 gives
$q_{h}$ that depends on $h$; however, $q$ can be chosen uniformly by the
pigeonhole principle since there are only $O(\delta^{-O(1)})$ possibilities
for $q_{h}$. $q\ll\delta^{-O(1)}$ and $\delta^{O(1)}N\ll N^{\prime}\leq N$
such that

$\displaystyle\sum_{x,y,h}\mu_{N/V}(h)\mathopen{}\left|\operatorname*{\mathbb{E}}_{z\in[N^{\prime}/V]}\Delta_{h{\mathbf{e}}_{1}}\widetilde{f_{2}}(x-qz,y+qz)\mathclose{}\right|\gg\delta^{O(1)}(N/V)^{2}.$

Applying the Cauchy–Schwarz inequality and then using Lemma 3.4(iv) to replace
$N^{\prime}$ with $N$ and drop $q$, we get the desired bound on
$\widetilde{f}_{2}$. ∎

The next result shows that the largeness of
$\Lambda^{\prime}(a,\widetilde{f_{1}},\widetilde{f_{2}})$ for some functions
$\widetilde{f_{1}},\widetilde{f_{2}}$ implies some correlation of the phase
$a$ with nilsequences on arithmetic progressions. We refer the reader to
Definition B.9 for definition of a nilsequence.

######  Proposition 5.2.

For every $C_{1}>0$ there exists $C_{2}=C_{2}(C_{1},P)>0$ such that the
following holds. Let $\delta\in(0,1/10)$, let $V\leq W^{C_{1}}$ be a positive
integer power of $W$, and let $r\in[V]$. Let
$a:{\mathbb{Z}}\to{\mathbb{R}}/{\mathbb{Z}}$ be a phase function, and let
$\widetilde{f_{1}},\widetilde{f_{2}}:{\mathbb{Z}}^{2}\to\mathbb{C}$ be
$1$-bounded functions supported on $[N/V]^{2}$, for some integer $N\geq
C_{2}V^{C_{2}}\exp(\log(1/\delta)^{C_{2}})$. If

$|\Lambda^{\prime}(a,\widetilde{f_{1}},\widetilde{f_{2}})|\geq\delta(N/V)^{2},$

then there exist a positive integer $k=O_{P}(1)$, a positive integer power
$V^{\prime}=V^{O_{C_{1},P}(1)}$, and a function
$\varphi:{\mathbb{Z}}\to{\mathbb{C}}$ such that

$\operatorname*{\mathbb{E}}_{j,r^{\prime}\in[V^{\prime}]}\sum_{y\in[N/(VV^{\prime})]}\left|\operatorname*{\mathbb{E}}_{z\in[(N/W_{d})^{1/d}(VV^{\prime})^{-1}]}e(-a_{(j,V^{\prime})}(y)V^{\prime}\cdot\widetilde{P}_{[Vr^{\prime}+r,VV^{\prime}]}(z))\right.\\\
\left.\varphi_{({j}+\widetilde{P}_{[r,V]}(r^{\prime}),V^{\prime})}(y+\widetilde{P}_{[Vr^{\prime}+r,VV^{\prime}]}(z))\vphantom{\operatorname*{\mathbb{E}}_{z\in[(N/W_{d})^{1/d}(VV^{\prime})^{-1}]}}\right|\geq\exp(-\log(1/\delta)^{O_{C_{1},P}(1)})N/(VV^{\prime})$

and for each $j\in[V^{\prime}]$, the restriction $\varphi_{(j,V^{\prime})}$ is
a $1$-bounded, degree-$k$ nilsequence of complexity
$\exp(\log(1/\delta)^{O_{C_{1},P}(1)})$ on a
$\log(1/\delta)^{O_{C_{1},P}(1)}$-dimensional nilmanifold.

###### Proof.

The proof consists of massaging the expression
$\Lambda^{\prime}(a,\widetilde{f_{1}},\widetilde{f_{2}})$, with the help of
the same techniques as in the proof of Theorem 4.1, until the structure of $a$
along arithmetic progressions becomes apparent. We fix $C_{1}>0$ and let all
constants depend on $C_{1},P$ without notating the dependence explicitly.

Step 1: Replacing $\widetilde{f_{2}}$ by a box norm obstruction.

Our first objective is to use Proposition 5.1 in conjunction with relevant box
norm inverse theorems and stashing to replace $\widetilde{f_{2}}$ by a
“structured” function. By Proposition 5.1, we have the lower bound

$\|\widetilde{f_{2}}\|_{({\mathbf{e}}_{2}-{\mathbf{e}}_{1})\cdot[\pm
N/V],\;{\mathbf{e}}_{1}\cdot[\pm N/V]}^{4}\gg\delta^{O(1)}(N/V)^{2}.$

The stashing argument gives

$\|\mathcal{D}^{\prime}_{2}(a,\widetilde{f_{1}})\|_{({\mathbf{e}}_{2}-{\mathbf{e}}_{1})\cdot[\pm
N/V],\;{\mathbf{e}}_{1}\cdot[\pm N/V]}^{4}\gg\delta^{O(1)}(N/V)^{2},$

for the dual function

$\mathcal{D}^{\prime}_{2}(a,\widetilde{f_{1}})(x,y):=\operatorname*{\mathbb{E}}_{z\in[(N/W_{d})^{1/d}V^{-1}]}e(a(y-\widetilde{P}_{[r,V]}(z))x)\\\
\widetilde{f_{1}}(x+\widetilde{P}_{[r,V]}(z),y-\widetilde{P}_{[r,V]}(z))1_{[N/V]}(y),$

where we were able to insert the term $1_{[N/V]}$ because $\widetilde{f_{2}}$
is supported on $[N/V]^{2}.$ By the inverse theorem for the $U^{1}\times
U^{1}$-box norm (Lemma A.7), there are $1$-bounded functions
$b_{1},b_{2}:{\mathbb{Z}}\to{\mathbb{C}}$ such that

$\sum_{x,y}\operatorname*{\mathbb{E}}_{z\in[(N/W_{d})^{1/d}V^{-1}]}b_{1}(y)b_{2}(x+y)e(a(y-\widetilde{P}_{[r,V]}(z))x)\\\
\widetilde{f_{1}}(x+\widetilde{P}_{[r,V]}(z),y-\widetilde{P}_{[r,V]}(z))1_{[N/V]}(y)\gg\delta^{O(1)}(N/V)^{2},$

and the presence of the $1_{[N/V]}(y)$ term lets us assume that $b_{1}$ is
supported on $[N/V]$. The change of variables $y\mapsto
y+\widetilde{P}_{[r,V]}(z)$ gives

$\sum_{x,y}\operatorname*{\mathbb{E}}_{z\in[(N/W_{d})^{1/d}V^{-1}]}e(a(y)x)\widetilde{f_{1}}(x+\widetilde{P}_{[r,V]}(z),y)\\\
b_{1}(y+\widetilde{P}_{[r,V]}(z))b_{2}(x+y+\widetilde{P}_{[r,V]}(z))\gg\delta^{O(1)}(N/V)^{2}.$

We observe that $b_{2}(x+y+\widetilde{P}_{[r,V]}(z))$ is a function of
$(x+\widetilde{P}_{[r,V]}(z),y)$. Shifting $x\mapsto
x-\widetilde{P}_{[r,V]}(z)$ and setting
$\widetilde{f_{1}}^{\prime}(x,y):=e(a(y)x)\widetilde{f_{1}}(x,y)b_{2}(x+y)$,
we get

$\displaystyle\sum_{x,y}\operatorname*{\mathbb{E}}_{z\in[(N/W_{d})^{1/d}V^{-1}]}e(-a(y)\widetilde{P}_{[r,V]}(z))\widetilde{f_{1}}^{\prime}(x,y)b_{1}(y+\widetilde{P}_{[r,V]}(z))\gg\delta^{O(1)}(N/V)^{2}.$

Recall that $\widetilde{f_{1}}^{\prime}$ is 1-bounded and supported on
$[N/V]^{2}$. Using the triangle inequality in the $x$\- and $y$-variables, we
can eliminate $\widetilde{f_{1}}^{\prime}$ entirely and obtain

$\displaystyle\sum_{y\in[N/V]}\mathopen{}\left|\operatorname*{\mathbb{E}}_{z\in[(N/W_{d})^{1/d}V^{-1}]}e(-a(y)\widetilde{P}_{[r,V]}(z))b_{1}(y+\widetilde{P}_{[r,V]}(z))\mathclose{}\right|\gg\delta^{O(1)}N/V.$

We have thus reduced matters to analyzing the auxiliary operator

(21)
$\displaystyle\Lambda^{\prime\prime}(b_{1}):=\sum_{y\in[N/V]}\mathopen{}\left|\operatorname*{\mathbb{E}}_{z\in[(N/W_{d})^{1/d}V^{-1}]}e(-a(y)\widetilde{P}_{[r,V]}(z))b_{1}(y+\widetilde{P}_{[r,V]}(z))\mathclose{}\right|.$

Step 2: Replacing $b_{1}$ by a nilsequence.

Our next goal is to show that $\Lambda^{\prime\prime}$ can be controlled by a
Gowers norm of $b_{1}$; this will let us replace $b_{1}$ by a nilsequence (at
least on arithmetic progressions of not-too-small difference). To obtain
Gowers norm control, we observe that $\Lambda^{\prime\prime}$ is amenable to a
standard PET argument. Let $b_{3}:{\mathbb{Z}}\to{\mathbb{C}}$ be a
$1$-bounded function supported on $[N/V]$ such that

$\Lambda^{\prime\prime}(b_{1})=\sum_{y}b_{3}(y)\operatorname*{\mathbb{E}}_{z\in[(N/W_{d})^{1/d}V^{-1}]}e(-a(y)\widetilde{P}_{[r,V]}(z))b_{1}(y+\widetilde{P}_{[r,V]}(z))\gg\delta^{O(1)}N/V.$

Shifting $y\mapsto y-\widetilde{P}_{[r,V]}(z)$, stashing, and shifting back
$y\mapsto y+\widetilde{P}_{[r,V]}(z)$, we find that

$\sum_{y}\overline{b_{3}(y)}\operatorname*{\mathbb{E}}_{z\in[(N/W_{d})^{1/d}V^{-1}]}e(a(y)\widetilde{P}_{[r,V]}(z))\widetilde{b}_{1}(y+\widetilde{P}_{[r,V]}(z))\gg\delta^{O(1)}N/V,$

where

$\widetilde{b}_{1}(y):=\operatorname*{\mathbb{E}}_{z\in[(N/W_{d})^{1/d}V^{-1}]}e(-a(y-\widetilde{P}_{[r,V]}(z))\widetilde{P}_{[r,V]}(z))b_{3}(y-\widetilde{P}_{[r,V]}(z))1_{[N/V]}(y).$

Note that the indicator function $1_{[N/V]}(y)$ can be included since $b_{1}$
is supported on this set. Now, using the Cauchy–Schwarz inequality to double
the $z$-variable $d+1$ times (in the style of PET), we eliminate $b_{3}(y)$
and the exponential involving $a(y)$; we obtain

$\sum_{y,h_{1},\ldots,h_{d+1}}\mu_{(N/W_{d})^{1/d}V^{-1}}(h_{1},\ldots,h_{d+1})\\\
\operatorname*{\mathbb{E}}_{z\in[(N/W_{d})^{1/d}V^{-1}]}\prod_{{\underline{\epsilon}}\in\\{0,1\\}^{d+1}}{\mathcal{C}}^{|{\underline{\epsilon}}|}\widetilde{b}_{1}(y+\widetilde{P}_{[r,V]}(z+{\underline{\epsilon}}\cdot{\underline{h}}))\gg\delta^{O(1)}N/V.$

By [16, Proposition 10.1] and the formula
$V_{d}=\beta_{d}\beta_{1}^{d-2}V^{d-1}W^{d-1}$, we have

$\displaystyle\left\|\widetilde{b}_{1}\right\|_{U^{k+1}(V_{d}\cdot[\pm
N/(VV_{d})])}^{2^{k+1}}\gg\delta^{O(1)}N/V$

for some integer $k=O(1)$. Take $V^{\prime}=V^{O(1)}$ to be the smallest
positive integer power of $V$ such that $V_{d}|\beta_{d}\beta_{1}V^{\prime}$.
Since $\beta_{1},\;\beta_{d}=O(1)$, we can apply parts (iv) and (vi) of Lemma
3.4 to replace the boxes $V_{d}\cdot[\pm N/(VV_{d})]$ by $V^{\prime}\cdot[\pm
N/(VV^{\prime})]$, obtaining

$\displaystyle\left\|\widetilde{b}_{1}\right\|_{U^{k+1}(V^{\prime}\cdot[\pm
N/(VV^{\prime})])}^{2^{k+1}}\gg\delta^{O(1)}N/V.$

Splitting the domain of $\tilde{b}_{1}$ into arithmetic progressions of
difference $V^{\prime}$, we find using the popularity principle that

$\displaystyle\left\|(\tilde{b}_{1})_{(j,V^{\prime})}\right\|_{U^{k+1}([\pm
N/(VV^{\prime})])}^{2^{k+1}}\gg\delta^{O(1)}N/(VV^{\prime})$

for an $\Omega(\delta^{O(1)})$-proportion of $j\in[V^{\prime}]$. The
$U^{k+1}$-inverse theorem [24, Theorem 1.2] tells us that for each such
$j\in[V^{\prime}]$, there is a $1$-bounded666$1$-boundedness is not mentioned
in the statement of [24, Theorem 1.2]; however, the control on the Lipschitz
norms of $\varphi_{j}$ ensures that the nilsequences coming from [24, Theorem
1.2] can be rescaled to be $1$-bounded at an acceptable loss of the factor
$\exp(-\log(1/\delta)^{O(1)})$ in the lower bound. degree-$k$ nilsequence
$\varphi_{j}$ of complexity $\exp(\log(1/\delta)^{O(1)})$ on an
$O(\log(1/\delta)^{O(1)})$-dimensional nilmanifold (see Definition B.9 for the
definition of a nilsequence and its complexity) such that

$\displaystyle\sum_{y}(\tilde{b}_{1})_{(j,V^{\prime})}(y)\varphi_{j}(y)\geq\exp(-\log(1/\delta)^{O(1)})N/(VV^{\prime}).$

For each remaining value of $j\in[V^{\prime}]$, set $\varphi_{j}:=0$. Thus,
$\varphi_{j}$ is a $1$-bounded degree-$k$ nilsequence of complexity
$\exp(\log(1/\delta)^{O(1)})$ on an $O(\log(1/\delta)^{O(1)})$-dimensional
nilmanifold for each $j\in[V^{\prime}]$.

Define $\varphi:{\mathbb{Z}}\to{\mathbb{C}}$ by setting
$\varphi_{(j,V^{\prime})}(y)=\varphi(V^{\prime}y+j)$ to equal $\varphi_{j}(y)$
for each $j\in[V^{\prime}]$ and $y\in{\mathbb{Z}}$, so that

$\displaystyle\sum_{y}\tilde{b}_{1}(y)\varphi(y)\geq\exp(-\log(1/\delta)^{O(1)})N/V.$

Expanding the definition of $\widetilde{b}_{1}$, shifting $y\mapsto
y+\widetilde{P}_{[r,V]}(z)$, and using the triangle inequality to eliminate
$b_{3}$, we obtain

$\displaystyle\sum_{y\in[N/V]}\left|\operatorname*{\mathbb{E}}_{z\in[(N/W_{d})^{1/d}V^{-1}]}e(-a(y)\widetilde{P}_{[r,V]}(z))\varphi(y+\widetilde{P}_{[r,V]}(z))\right|\geq\exp(-\log(1/\delta)^{O(1)})N/V.$

Since $\varphi$ is a nilsequence only when restricted to arithmetic
progressions of common difference $V^{\prime}$, we also split the ranges of
$y$ and $z$ into arithmetic progressions of common difference $V^{\prime}$.
This gives

$\operatorname*{\mathbb{E}}_{j,r^{\prime}\in[V^{\prime}]}\sum_{y\in[N/(VV^{\prime})]}\left|\operatorname*{\mathbb{E}}_{z\in[(N/W_{d})^{1/d}(VV^{\prime})^{-1}]}e(-a_{(j,V^{\prime})}(y)V^{\prime}\cdot\widetilde{P}_{[Vr^{\prime}+r,VV^{\prime}]}(z))\right.\\\
\left.\varphi_{({j}+\widetilde{P}_{[r,V]}(r^{\prime}),V^{\prime})}(y+\widetilde{P}_{[Vr^{\prime}+r,VV^{\prime}]}(z))\vphantom{\operatorname*{\mathbb{E}}_{z\in[(N/W_{d})^{1/d}(VV^{\prime})^{-1}]}}\right|\geq\exp(-\log(1/\delta)^{O(1)})N/(VV^{\prime}),$

as desired. ∎

Notice that the last step of splitting into progressions introduced a factor
of $V^{\prime}$ in the first term; this arises essentially because we
$V^{\prime}$-tricked the exponential function.

##  6\. Nilsequence application

In the previous section, we arrived at expressions of the form

(22)
$\displaystyle\sum_{y\in[N/\tilde{V}]}\left|\operatorname*{\mathbb{E}}_{z\in[(N/W_{d})^{1/d}\tilde{V}^{-1}]}e(\tilde{a}(y)\cdot\widetilde{P}_{[\tilde{r},\tilde{V}]}(z))\tilde{\varphi}(y+\widetilde{P}_{[\tilde{r},\tilde{V}]}(z))\vphantom{\operatorname*{\mathbb{E}}_{z\in[(N/W_{d})^{1/d}\tilde{V}^{-1}]}}\right|$

with

$\displaystyle\tilde{V}=VV^{\prime},\quad\tilde{r}=Vr^{\prime}+r,\quad\tilde{\varphi}=\varphi_{({j}+\widetilde{P}_{[r,V]}(r^{\prime}),V^{\prime})},\quad\textrm{and}\quad\tilde{a}=-a_{(j,V^{\prime})}V^{\prime},$

where $\tilde{\varphi}$ is a nilsequence. This section is devoted to
extracting information about the phase $a$ using the largeness of (22). The
main underlying machinery comes from the equidistribution results of [21]. We
refer the reader to Appendix B for definitions and notation related to
nilsequences.

Our main technical input is the following result, which is the special case
$\ell=1$ of [21, Theorem 3].

######  Theorem 6.1.

For every $k>0$ there is a constant $C=C(k)>0$ such that the following holds.
Let $G/\Gamma$ be a nilmanifold of degree $k$, step $s$, complexity at most
$M$, and dimension $m$, with associated filtration $G_{\bullet}$. Let
$\delta\in(0,1/10)$, and let $N>(M/\delta)^{Cm^{C}}$ be an integer. Let
$F:G/\Gamma\to\mathbb{C}$ be a $1$-bounded $M$-Lipschitz function with a
vertical character $\xi$ satisfying $0<|\xi|\leq M/\delta$.

Suppose $g\in\mathrm{poly}(\mathbb{Z},G)$ with

$\mathopen{}\left|\operatorname*{\mathbb{E}}_{n\in[N]}F(g(n)\Gamma)\mathclose{}\right|\geq\delta.$

Then there exist $0<r\leq\mathrm{dim}(G/[G,G])$ and horizontal characters
$\eta_{1},\dots,\eta_{r}$ of size at most $(M/\delta)^{O_{k}(m)^{O_{k}(1)}}$
satisfying

$\|\eta_{i}\circ g\|_{C^{\infty}[{N}]}\leq(M/\delta)^{O_{k}(m)^{O_{k}(1)}},$

and $\xi$ annihilates all $(s-1)$-fold commutators of elements in the subgroup
$G^{\prime}:=\bigcap_{i=1}^{r}\mathrm{ker}(\eta_{i})$.

The use of this theorem is that it allows one to iteratively “reduce” the step
of $g$.

In the following proposition, we let $\tilde{V}_{d}$ denote the leading
coefficient of $\widetilde{P}_{[\tilde{r},\tilde{V}]}$.

######  Proposition 6.2.

Let $s,k\in{\mathbb{N}}$ with $s\leq k$. For every $C_{1}>0$ there exist
constants $C_{2}=C_{2}(C_{1},P,k),\;C_{3}=C_{3}(C_{1},P,k)>1$ such that the
following holds. Let $G/\Gamma$ be a nilmanifold of degree $k$, step $s$,
complexity at most $M\geq 2$, and dimension $m\in{\mathbb{N}}$, with
associated filtration $G_{\bullet}$, and let
$g\in\operatorname{poly}({\mathbb{Z}},G)$. Let $\delta\in(0,1/10)$, and let
$F:G/\Gamma\to\mathbb{C}$ be a $1$-bounded $M$-Lipschitz function with a
vertical character $\xi$ satisfying $0<|\xi|\leq M/\delta$. Let $\tilde{V}\leq
W^{C_{1}}$ be a nonnegative integer power of $W$, let
$\tilde{r}\in[\tilde{V}]$, and let
$N\geq\tilde{V}_{d}\tilde{V}^{C_{2}}(M/\delta)^{2C_{2}dm^{C_{2}}}$ be an
integer. Lastly, let $A\subseteq[N/\tilde{V}]$ and $B\subseteq{\mathbb{Z}}$ be
nonempty arithmetic progressions of common difference at most $M/\delta$
satisfying

(23) $\displaystyle|B|\geq
C_{2}\cdot(N/(\tilde{V}\tilde{V}_{d}))^{1/d}(M/\delta)^{-C_{2}m^{C_{2}}}.$

If

(24) $\sum_{y\in A}\left|\operatorname*{\mathbb{E}}_{z\in
B}e(\tilde{a}(y)\cdot\widetilde{P}_{[\tilde{r},\tilde{V}]}(z))F(g(y+\widetilde{P}_{[\tilde{r},\tilde{V}]}(z))\Gamma)\vphantom{\operatorname*{\mathbb{E}}_{z\in[(N/W_{d})^{1/d}\tilde{V}^{-1}]}}\right|\geq\delta|A|,$

then the following holds with $T:=|B|^{d}\tilde{V}_{d}$.

  * •

When $s>1$: There exists a factorization
$g(n)=\varepsilon(n)g^{\prime}(n)\gamma(n)$, where $\varepsilon$ is
$((M/\delta)^{C_{3}m^{C_{3}}},T)$-smooth, $g^{\prime}$ takes values in an
$(M/\delta)^{C_{3}m^{C_{3}}}$-rational normal subgroup $G^{\prime}$ of $G$
such that $G^{\prime}/\mathrm{ker}(\xi)$ has step at most $s-1$, and $\gamma$
is $(M/\delta)^{C_{3}m^{C_{3}}}$-rational.

  * •

When $s=1$ and $k>1$: There is a polynomial
$p(n)=\sum_{j=0}^{k}\alpha_{j}n^{j}$ such that $F(g(n)\Gamma)=e(p(n))$, and
there is a positive integer $q\leq C_{3}\delta^{-C_{3}}$ such that
$\left\|q\alpha_{j}\right\|_{\mathbb{R}/\mathbb{Z}}\leq
C_{3}\delta^{-C_{3}}/T^{j}$ for all $j\geq 2$.

  * •

When $s=1$ and $k=1$: There are a phase $\alpha\in\mathbb{R}/\mathbb{Z}$ and a
positive integer $q\leq C_{3}\delta^{-C_{3}}$ such that
$\left\|q\tilde{a}(y)-\alpha\right\|_{\mathbb{R}/\mathbb{Z}}\leq
C_{3}\delta^{-C_{3}}/T$ for at least $C_{3}\delta^{C_{3}}|A|$ values of $y\in
A$.

We remark that in the third case, the pigeonhole principle trivially provides
some $\alpha$ such that
$\left\|\widetilde{a}(y)-\alpha\right\|_{\mathbb{R}/\mathbb{Z}}\leq
C_{3}\delta^{-C_{3}}/T$ for at least $2C_{3}\delta^{-C_{3}}|A|/T$ values of
$y$; the proposition improves the quantity $2C_{3}\delta^{-C_{3}}|A|/T$ by a
factor of around $\delta^{O(1)}T$, which is quite substantial since $|B|$ is
large in applications.

###### Proof.

We fix $C_{1}>0$ and let all constants depend on $C_{1},P,k$ (and hence also
on $s$ since $s\leq k$). We address the three bullet-pointed cases one-by-one.

Case 1: $s>1$.

Suppose first that $s>1$. By the pigeonhole principle, there is some $y_{0}\in
A$ such that

(25) $\displaystyle\mathopen{}\left|\operatorname*{\mathbb{E}}_{z\in
B}e(\tilde{a}(y_{0})\widetilde{P}_{[\tilde{r},\tilde{V}]}(z))F(g(y_{0}+\widetilde{P}_{[\tilde{r},\tilde{V}]}(z))\Gamma)\mathclose{}\right|\geq\delta.$

Since $\xi$ is nonzero, there is some $g_{s}\in G_{(s)}$ such that
$\xi(g_{s})=a(y_{0})$. Now define the polynomial sequence
$\tilde{g}:\mathbb{Z}\to G$ (with respect to the same filtration
$G_{\bullet}$) via

$\tilde{g}(n):=g_{s}^{n}g(y_{0}+n).$

Since $\mathrm{poly}(\mathbb{Z},G)$ is closed under pointwise multiplication,
we have $\tilde{g}\in\mathrm{poly}(\mathbb{Z},G)$. Notice that

$\pi_{\mathrm{horiz}}(\tilde{g}(n))=\pi_{\mathrm{horiz}}(g(y_{0}+n))$

since $g_{s}^{n}\in G_{(s)}$ has image zero in the horizontal torus. The
identity

$F(\tilde{g}(n)\Gamma)=e(\tilde{a}(y_{0})n)F(g(y_{0}+n)\Gamma)$

then lets us rewrite (25) as

$\mathopen{}\left|\operatorname*{\mathbb{E}}_{z\in
B}F(\tilde{g}(\widetilde{P}_{[r,V]}(z))\Gamma)\mathclose{}\right|\geq\delta.$

Now, consider the filtration $(\mathbb{Z}_{i})_{i=0}^{\infty}$ on $\mathbb{Z}$
given by

$\mathbb{Z}_{i}=\begin{cases}\mathbb{Z}&\text{if $i\leq d$},\\\ 0&\text{if
$i>d$};\end{cases}$

with respect to this filtration, we have
$\widetilde{P}_{[\tilde{r},\tilde{V}]}\in\operatorname{poly}(\mathbb{Z},\mathbb{Z})$.
By [43, Theorem 1.6.9], the composition
$\tilde{g}\circ\widetilde{P}_{[\tilde{r},\tilde{V}]}(z)$ is a polynomial
sequence on $G$ with a slightly modified filtration (now of degree $dk$).

Since

$|B|\geq
C_{2}\cdot(N/(\tilde{V}\tilde{V}_{d}))^{1/d}(M/\delta)^{-C_{2}m^{C_{2}}}\geq
C(M/\delta)^{C_{2}m^{C_{2}}}$

and $C_{2}>0$ can be chosen to be sufficiently large, Theorem 6.1 gives us
horizontal characters $\eta_{1},\ldots,\eta_{r}$ of size
$O((M/\delta)^{O(m)^{O(1)}})$ (for some $0<r\leq\mathrm{dim}(G/[G,G])$) such
that each $\eta_{i}$ satisfies

(26)
$\|\eta_{i}\circ\tilde{g}\circ\widetilde{P}_{[\tilde{r},\tilde{V}]}\|_{C^{\infty}[|B|]}\ll(M/\delta)^{O(m)^{O(1)}},$

and such that $\xi$ annihilates all $(s-1)$-fold commutators of elements of
$G^{\prime}:=\bigcap_{i=1}^{r}\ker(\eta_{i})$. Since

(27) $\displaystyle|B|\geq
C_{2}\cdot(N/(\tilde{V}\tilde{V}_{d}))^{1/d}(M/\delta)^{-C_{2}m^{C_{2}}}\geq
C_{2}\tilde{V}^{(C_{2}-1)/d}$

and $C_{2}>0$ is sufficiently large, Lemma C.3 tells us that

$\|\eta_{i}\circ\tilde{g}\|_{C^{\infty}[T]}\ll(M/\delta)^{O(m)^{O(1)}}$

for each $\eta_{i}$ (recall that $T=|B|^{d}\tilde{V}_{d}$). Since

(28) $\displaystyle|y_{0}|\leq N/\tilde{V}\ll(M/\delta)^{O(m)^{O(1)}}T$

by (23), Lemma C.2 further implies that each

$\|\eta_{i}\circ g\|_{C^{\infty}[T]}\ll(M/\delta)^{O(m)^{O(1)}}$

(where the $O(1)$ in this inequality may differ from the $O(1)$ in the
preceding inequality). The conclusion of the proposition now follows from [21,
Lemma A.1].

Case 2: $s=1,k>1$.

Now suppose that $s=1$. Since $s=1$, there is a polynomial
$p(n)=\sum_{j=0}^{k}\alpha_{j}n^{j}$ such that $F(g(n)\Gamma)=e(p(n))$.
Substituting this into (24) and pigeonholing in $y$ gives that

$\mathopen{}\left|\operatorname*{\mathbb{E}}_{z\in[B]}e\left(\tilde{a}(y_{0})\widetilde{P}_{[\tilde{r},\tilde{V}]}(z)+\sum_{j=0}^{k}\alpha_{j}(y_{0}+\widetilde{P}_{[\tilde{r},\tilde{V}]}(z))^{j}\right)\mathclose{}\right|\geq\delta$

for some $y_{0}\in A$. Weyl’s inequality (see, e.g., [11, Lemma 4.4]) tells us
that there is a positive integer $q\ll\delta^{-O(1)}$ such that

$\displaystyle\left\|q\cdot
R(y_{0}+\widetilde{P}_{[\tilde{r},\tilde{V}]}(z))\right\|_{C^{\infty}[|B|]}\ll\delta^{-O(1)}.$

for $R(n):=p(n)+\tilde{a}(y_{0})(n-y_{0})$. Applying Lemma C.3 with (28) and
then Lemma C.2 with (27), we find that
$\left\|q\alpha_{j}\right\|_{\mathbb{R}/\mathbb{Z}}\ll\delta^{-O(1)}/T^{j}$
for all $j\geq 2$. (We do not make use of the conclusion that
$\left\|q(\tilde{a}(y_{0})+\alpha_{1})\right\|_{\mathbb{R}/\mathbb{Z}}\ll\delta^{-O(1)}/T$.)
This concludes the proof of the proposition in the second case.

Case 3: $s=k=1$.

Finally, suppose that $s=1$ and moreover $k=1$. Then there are
$\alpha_{0},\alpha_{1}\in\mathbb{R}/\mathbb{Z}$ such that
$F(g(n)\Gamma)=e(\alpha_{1}n+\alpha_{0})$. Now (24) reads

$\sum_{y\in
A}\mathopen{}\left|\operatorname*{\mathbb{E}}_{z\in[B]}e(\tilde{a}(y)\widetilde{P}_{[\tilde{r},\tilde{V}]}(z)+\alpha_{1}(y+\widetilde{P}_{[\tilde{r},\tilde{V}]}(z)))\mathclose{}\right|\geq\delta|A|.$

The popularity principle provides at least $\delta|A|/2$ values of $y\in|A|$
such that

$\displaystyle\mathopen{}\left|\operatorname*{\mathbb{E}}_{z\in[B]}e(R_{y}\circ\widetilde{P}_{[\tilde{r},\tilde{V}]}(z))\mathclose{}\right|\geq\delta/2,$

where $R_{y}(n):=(\tilde{a}(y)+\alpha_{1})n$. Hence, by Weyl’s inequality, we
have

$\left\|q_{y}R_{y}\circ\widetilde{P}_{[\tilde{r},\tilde{V}]}\right\|_{C^{\infty}(|B|)}\ll\delta^{-O(1)}$

for some positive integer $q_{y}\ll\delta^{-O(1)}$. Lemma C.3 then gives
$\left\|q_{y}R_{y}\right\|_{C^{\infty}(T)}\ll\delta^{-O(1)}$, which is
tantamount to

$\left\|q_{y}(\tilde{a}(y)+\alpha_{1})\right\|_{\mathbb{R}/\mathbb{Z}}\ll\delta^{-O(1)}/T.$

Pigeonholing in $y$, we can find $q$ such that this bound holds for
$\gg\delta^{O(1)}|A|$ values of $y\in A$. ∎

###  6.1. Completing the proof of Proposition 4.4

We are now in a position to complete the proof of Proposition 4.4. We let all
constants depend on $P$. By Proposition 5.2, there exist a positive integer
$k=O(1)$, a positive integer power $V^{\prime}=V^{O(1)}$, and a function
$\varphi:{\mathbb{Z}}\to{\mathbb{C}}$ such that for each $j\in[V^{\prime}]$,
the restriction $\varphi_{(j,V^{\prime})}$ is a $1$-bounded, degree-$k$
nilsequence of complexity $\exp(\log(1/\delta)^{O(1)})$ on a
$\log(1/\delta)^{O(1)}$-dimensional nilmanifold. Moreover, we have

$\operatorname*{\mathbb{E}}_{j,r^{\prime}\in[V^{\prime}]}\sum_{y\in[N/(VV^{\prime})]}\left|\operatorname*{\mathbb{E}}_{z\in[(N/W_{d})^{1/d}(VV^{\prime})^{-1}]}e(-a_{(j,V^{\prime})}(y)V^{\prime}\cdot\widetilde{P}_{[Vr^{\prime}+r,VV^{\prime}]}(z))\right.\\\
\left.\varphi_{({j}+\widetilde{P}_{[r,V]}(r^{\prime}),V^{\prime})}(y+\widetilde{P}_{[Vr^{\prime}+r,VV^{\prime}]}(z))\vphantom{\operatorname*{\mathbb{E}}_{z\in[(N/W_{d})^{1/d}(VV^{\prime})^{-1}]}}\right|\geq\exp(-\log(1/\delta)^{O(1)})N/(VV^{\prime}).$

By the popularity principle, there exists $r^{\prime}\in[V^{\prime}]$ and a
set $\mathcal{V}\subseteq[V^{\prime}]$ of size
$|\mathcal{V}|\geq\exp(-\log(1/\delta)^{O(1)})V^{\prime}$ such that for each
$j\in\mathcal{V}$, we have the bound

(29)
$\displaystyle\sum_{y\in[N/\tilde{V}]}\left|\operatorname*{\mathbb{E}}_{z\in[(N/W_{d})^{1/d}\tilde{V}^{-1}]}e(\tilde{a}_{(j,V^{\prime})}(y)\cdot\widetilde{P}_{[\tilde{r},\tilde{V}]}(z))\tilde{\varphi}_{j}(y+\widetilde{P}_{[\tilde{r},\tilde{V}]}(z))\vphantom{\operatorname*{\mathbb{E}}_{z\in[(N/W_{d})^{1/d}\tilde{V}^{-1}]}}\right|\geq\eta
N/\tilde{V},$

where $\eta=\exp(-\log(1/\delta)^{O(1)})$ and

$\displaystyle\tilde{V}=VV^{\prime},\quad\tilde{r}=Vr^{\prime}+r,\quad\tilde{a}(y)=-a(y)V^{\prime},\quad\textrm{and}\quad\tilde{\varphi}_{j}(y)=\varphi_{({j}+\widetilde{P}_{[r,V]}(r^{\prime}),V^{\prime})}(y).$

Fix $j\in\mathcal{V}$. We will iteratively apply Proposition 6.2. This will
let us first reduce to the case where (29) holds with $\tilde{\varphi}_{j}$
replaced by a degree-$1$ nilsequence on a $1$-dimensional nilmanifold, and
then deduce that the phase function $\tilde{a}_{(j,V^{\prime})}$ is nearly
constant for a positive proportion of $y$’s. Our proof proceeds by iteratively
reducing the step of the nilmanifold underlying $\tilde{\varphi}_{j}$. At each
stage, we will have parameters $\eta,A,B,g,G/\Gamma$, and $F$. Since the step
is initially at most $\log(1/\delta)^{O(1)}$ and we decrease the step at each
stage, there are at most $\log(1/\delta)^{O(1)}$ stages. Keeping track of how
our bounds degrade at each stage, we can guarantee that throughout the
iterative process we always have the bounds

$\displaystyle\eta\geq\exp(-\log(1/\delta)^{O(1)}),\quad
N\gg\tilde{V}_{d}\tilde{V}^{\Omega(1)}\eta^{-O(m)^{O(1)}},\quad|A|\gg\eta^{O(m)^{O(1)}}\frac{N}{\tilde{V}},$
$\displaystyle|B|\gg\eta^{O(m)^{O(1)}}(N/(\tilde{V}\tilde{V}_{d}))^{1/d},\quad
T=|B|^{d}\tilde{V}_{d}\gg\eta^{O(m)^{O(1)}}\frac{N}{\tilde{V}},$
$\displaystyle M\ll\eta^{-O(m)^{O(1)}},\quad\text{ and }\quad
m\ll\log(1/\delta)^{O(1)}.$

We remind the reader that $m,M$ stand for dimension and complexity of the
underlying nilmanifold, and we observe that the frequently appearing quantity
$\eta^{O(m)^{O(1)}}$ is of the shape $\exp(-\log(1/\delta)^{O(1)})$. Our lower
bound $N\gg V^{\Omega(1)}\exp(\log(1/\delta)^{\Omega(1)})$ guarantees that the
iteration will not halt before the claimed result is proven.

We begin with $A=[N/\tilde{V}]$ and
$B=[(N/(\tilde{V}\tilde{V}_{d}))^{1/d}]=[(N/W_{d})^{1/d}\tilde{V}^{-1}]$. We
also start with $\eta\asymp\exp(-\log(1/\delta)^{O(1)})$, for which the lower
bound in (29) holds.

Step 1: Fourier-expanding $F$.

In order to apply Proposition 6.2, we will first Fourier-expand the function
$F$. Suppose that $F:G/\Gamma\to\mathbb{C}$ is an $M$-Lipschitz function on a
nilmanifold $G/\Gamma$ of complexity $M$, and that

(30) $\sum_{y\in A}\mathopen{}\left|\operatorname*{\mathbb{E}}_{z\in
B}e(\tilde{a}_{(j,\tilde{V})}(y)\widetilde{P}_{[\tilde{r},\tilde{V}]}(z))F(g(y+\widetilde{P}_{[\tilde{r},\tilde{V}]}(z))\Gamma)\mathclose{}\right|\geq\eta|A|.$

By [21, Lemma A.6], we can Fourier-expand $F$ along the
$G^{\prime}_{(s)}$-torus as

$\tilde{F}=\sum_{|\xi|\leq(M/\eta)^{O(m)^{O(1)}}}F_{\xi}+O((\eta/M)^{O(m)^{O(1)}}),$

where each $F_{\xi}$ is an $(M/\eta)^{O(m)^{O(1)}}$-Lipschitz vertical
character of frequency $\xi$. By replacing $\eta$ with
$(\eta/M)^{O(m)^{O(1)}}$, we may assume that $F=F_{\xi}$ and that $F$ is
$1$-Lipschitz. Thus, we have

(31) $\sum_{y\in A}\mathopen{}\left|\operatorname*{\mathbb{E}}_{z\in
B}e(\tilde{a}_{(j,\tilde{V})}(y)\widetilde{P}_{[\tilde{r},\tilde{V}]}(z))F(g(y+\widetilde{P}_{[\tilde{r},\tilde{V}]}(z))\Gamma)\mathclose{}\right|\gg(\eta/M)^{O(m)^{O(1)}}|A|$

(The purpose of these manipulations is to replace the function $F$ in (30) by
a vertical character.) Finally, we relabel $(\eta/M)^{O(m)^{O(1)}}$ as simply
$\eta$ so our hypothesis becomes

(32) $\sum_{y\in A}\mathopen{}\left|\operatorname*{\mathbb{E}}_{z\in
B}e(\tilde{a}_{(j,\tilde{V})}(y)\widetilde{P}_{[\tilde{r},\tilde{V}]}(z))F(g(y+\widetilde{P}_{[\tilde{r},\tilde{V}]}(z))\Gamma)\mathclose{}\right|\gg\eta|A|.$

Step 2: Applying Proposition 6.2.

Proposition 6.2 applied to (32) supplies a factorization $g=\varepsilon
g^{\prime}\gamma$, where $\gamma$ is an $(M/\eta)^{O(m)^{O(1)}}$-rational
sequence, $\varepsilon$ is an $((M/\eta)^{O(m)^{O(1)}},T)$-smooth sequence,
and $g^{\prime}$ is a sequence lying in an $(M/\eta)^{O(m)^{O(1)}}$-rational
subnilmanifold $G^{\prime}/\Gamma^{\prime}$ of step $\leq s-1$ for some normal
subgroup $G^{\prime}\subseteq G$ with lattice
$\Gamma^{\prime}:=G^{\prime}\cap\Gamma$. Since $\varepsilon$ is
$((M/\eta)^{O(m)^{O(1)}},T)$-smooth, it is also $(\sigma^{-1},|A|)$-smooth for
some $\sigma=(\eta/M)^{O(m)^{O(1)}}$.

Step 3: Pigeonholing in a subprogression.