# Quantitative concatenation
for polynomial box norms

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.

We prove PET and quantitative concatenation results for general
multidimensional polynomial progressions, with at most polynomial losses in
the parameters. In the companion paper [14], we use these estimates to obtain
an explicit upper bound on the size of a set in $[N]^{2}$ lacking
nondegenerate progressions of the form $(x,y),(x+P(z),y),(x,y+P(z))$, where
$P\in\mathbb{Z}[z]$ is any fixed polynomial with an integer root of
multiplicity $1$.

##  1\. Introduction

One of the starting points of arithmetic combinatorics is Roth’s Theorem [30],
which says that every subset of the natural numbers with positive upper Banach
density contains a nontrivial $3$-term arithmetic progression
$x,\;x+z,\;x+2z$. Szemerédi [33] famously extended this result to $\ell$-term
arithmetic progressions for all $\ell$. The farthest-reaching generalization
of this line of work is the Polynomial Szemerédi Theorem of Bergelson and
Leibman [3], which asserts that positive-upper-Banach-density subsets of
${\mathbb{Z}}^{D}$ always contain nontrivial “polynomial progressions” under
certain weak local conditions on the polynomials involved.

The quantitative bounds from Roth’s original proof of his theorem have been
improved many times, most recently by Kelley and Meka [13]. Szemerédi provided
effective, albeit enormous, bounds for his theorem, and Gowers’ work [9] on
obtaining more “reasonable” bounds inaugurated the field of higher-order
Fourier analysis, where recent developments have led to improved bounds for
Szemerédi’s Theorem [20]. The proof of Bergelson and Leibman [3], by contrast,
uses ergodic-theoretic methods and is completely ineffective. Obtaining
quantitative (and “reasonable”) bounds for the Bergelson–Leibman Theorem is a
difficult problem that was highlighted by Gowers e.g. in [8].

In an early development, Sárközy [31, 32] obtained quantitative bounds for
nonlinear polynomial progressions of length two. Green [11] and Prendiville
[28] later studied other particular examples of polynomial progressions, but
their methods do not have obvious applications to larger families of
polynomial progressions. Building on work of Peluse [21], Peluse and
Prendiville [24] gave an effective polynomial Szemerédi theorem for the
progression $x,\;x+z,\;x+z^{2}$. Peluse [22] then extended this method to
obtain reasonable bounds for polynomial progressions involving polynomials
with distinct degrees. Quite a few quantitative polynomial Szemerédi theorems
[2, 12, 15, 16, 17, 19, 18, 27] have been proven in recent years, and our work
[14] can be seen as progress in this direction.

Most arguments in this line of research have begun by using the PET induction
scheme of Bergelson [1] to show that the counting operator for the associated
polynomial progression is bounded by an appropriate Gowers norm or, more
generally, an appropriate box norm.111For the definitions of the concepts
appearing in the introduction, including Gowers norms, box norms and
multiplicative derivatives, we refer the reader to Section 3. The details of
the PET induction scheme are elucidated in Section 4. Green and Tao [10]
showed that iterated applications of the Cauchy–Schwarz inequality in the
style of Gowers [7, 9] suffice to give Gowers-norm-control for positive-
complexity linear configurations in any number of dimensions. For
$1$-dimensional polynomial progressions in the finite-field setting, a naïve
application of the PET argument produces the required norm-control. For
example, if the counting operator

$\displaystyle\sum_{x,z\in{\mathbb{Z}}/N{\mathbb{Z}}}f_{0}(x)f_{1}(x+z)f_{2}(x+z^{2})$

is large for some $1$-bounded functions
$f_{0},f_{1},f_{2}:{\mathbb{Z}}/N{\mathbb{Z}}\to{\mathbb{C}}$ (where $N$ is a
large prime), then a short PET argument gives that the Gowers norm
$\left\|f_{2}\right\|_{U^{3}({\mathbb{Z}}/{\mathbb{N}}{\mathbb{Z}})}$ is also
large, with polynomial dependences. In the integer setting, by contrast, the
PET argument alone does not suffice. If the counting operator

$\displaystyle\sum_{x,z\in{\mathbb{Z}}}f_{0}(x)f_{1}(x+z)f_{2}(x+z^{2})$

is large for some $1$-bounded functions
$f_{0},f_{1},f_{2}:{\mathbb{Z}}\to{\mathbb{C}}$ supported on
$[N]:=\\{1,\ldots,N\\}$ for some large $N\in{\mathbb{N}}$, then PET gives only
the largeness of the quantity

$\displaystyle\sum_{h_{1},h_{2}\in[N^{1/2}]}\sum_{m_{1},m_{2},m_{3}\in[N^{1/2}]}\sum_{x}\Delta_{h_{1}m_{1},h_{2}m_{2},(h_{1}+h_{2})m_{3}}f_{2}(x).$

This expression is essentially an average of many “arithmetic box norms” along
progressions with common differences

(1) $\displaystyle h_{1},h_{2},h_{1}+h_{2}.$

For more complicated $1$-dimensional polynomial progressions, the common
differences arising are multilinear polynomials in parameters
$h_{1},h_{2},\ldots$. At this point, it is desirable to “concatenate” these
norms into a single Gowers norm of higher degree, so that one can use the
numerous techniques involving the inverse theory of the Gowers norms.

The first such concatenation result was proven by Tao and Ziegler [34]. Their
approach was infinitary, however, and gave no quantitative bounds on the
losses incurred while passing from an average of box norms to a single
concatenated Gowers norm. In [23, 24], Peluse and Prendiville developed a
different approach that could provide quantitative bounds222See also [26], in
which Peluse, Prendiville and Shao extend the quantitative concatenation
approach from [24] to obtain Gowers-norm-control for the configuration
$(x_{1},x_{2}),\;(x_{1}+z,x_{2}),\;(x_{1},x_{2}+z^{2})$.. They showed, among
other things, that the averages of box norms arising from applying PET to
$1$-dimensional polynomial progressions

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

can be concatenated into a single Gowers norm that control the counting
operator for (2) with only polynomial losses. This concatenation result was
instrumental in their proof of quantitative bounds for subsets of $[N]$
lacking progressions (2) in the case where
$P_{1},\ldots,P_{\ell}\in{\mathbb{Z}}[z]$ have distinct degrees.

The situation is even more complicated in higher dimensions. Consider, for
example, the multidimensional polynomial pattern

(3) $(x_{1},x_{2}),(x_{1}+z^{2}+z,x_{2}),(x_{1},x_{2}+z^{2}+z).$

This time, we would like to show that if

(4)
$\displaystyle\sum_{x_{1},x_{2},z\in{\mathbb{Z}}}f_{0}(x_{1},x_{2})f_{1}(x_{1}+z^{2}+z,x_{2})f_{2}(x_{1},x_{2}+z^{2}+z)$

is large for some $1$-bounded functions
$f_{0},f_{1},f_{2}:{\mathbb{Z}}\to{\mathbb{C}}$ supported on $[N]^{2}$, then
so is333Naturally, we also want to obtain the largeness of certain averages of
box norms of $f_{0},f_{1}$, in which the role of
$\\{{\mathbf{e}}_{2},{\mathbf{e}}_{2}-{\mathbf{e}}_{1}\\}$ is played by
$\\{{\mathbf{e}}_{1},{\mathbf{e}}_{2}\\}$ and
$\\{{\mathbf{e}}_{1},{\mathbf{e}}_{1}-{\mathbf{e}}_{2}\\}$ respectively.

$\displaystyle\sum_{h_{1},\ldots,h_{2t}\in{\mathbb{Z}}}\sum_{x_{1},x_{2}\in{\mathbb{Z}}}\Delta_{h_{1}{\mathbf{e}}_{2},\ldots,h_{t}{\mathbf{e}}_{2},h_{t+1}({\mathbf{e}}_{2}-{\mathbf{e}}_{1}),\ldots,h_{2t}({\mathbf{e}}_{2}-{\mathbf{e}}_{1})}f_{2}(x_{1},x_{2})$

for some positive integer $t=O(1)$, where ${\mathbf{e}}_{1},{\mathbf{e}}_{2}$
are the usual coordinate vectors in $\mathbb{Z}^{2}$. (From here, one can hope
to use degree-lowering arguments to decrease $t$ to its optimal value.) The
usual PET argument gives control of (4) by an average of degree-$7$ box norms
of $f_{2}$ in the directions

(5) $\displaystyle
2(h_{2}+h_{3})({\mathbf{e}}_{2}-{\mathbf{e}}_{1})+2h_{1}{\mathbf{e}}_{2},\
2h_{2}({\mathbf{e}}_{2}-{\mathbf{e}}_{1})+2h_{1}{\mathbf{e}}_{2},\
2h_{3}({\mathbf{e}}_{2}-{\mathbf{e}}_{1})+2h_{1}{\mathbf{e}}_{2},$
$\displaystyle 2h_{1}{\mathbf{e}}_{2},\
2(h_{2}+h_{3})({\mathbf{e}}_{2}-{\mathbf{e}}_{1}),\
2h_{2}({\mathbf{e}}_{2}-{\mathbf{e}}_{1}),\
2h_{3}({\mathbf{e}}_{2}-{\mathbf{e}}_{1}).$

In contrast to the single-dimensional examples described above, this example
requires us to concatenate an average of many box norms involving linear
combinations of _two_ principal directions
${\mathbf{e}}_{2},{\mathbf{e}}_{2}-{\mathbf{e}}_{1}$ into a single box norm
involving these two principal directions. More generally, in the study of
multidimensional polynomial progressions

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

for some choice of
${\textbf{P}}_{1},\ldots,{\textbf{P}}_{\ell}\in{\mathbb{Z}}^{D}[z]$, one is
confronted with the task of concatenating averages of box norms along

(7)
$\displaystyle{\textbf{C}}_{1}(h_{1},\ldots,h_{r}),\ldots,{\textbf{C}}_{s}(h_{1},\ldots,h_{r}),$

for some _multilinear_ polynomials
${\textbf{C}}_{1},\ldots,{\textbf{C}}_{s}\in{\mathbb{Z}}^{D}[h_{1},\ldots,h_{r}]$
that arise from the application of PET to (6); the goal is to obtain control
by a single box norm, which usually involves several principal directions.

Let us compare the directions in (1) with the directions in (5). The
polynomial directions in (1), as examined by Peluse and Prendiville, are all
multiples of the same principal direction in ${\mathbb{Z}}$. The polynomial
directions in (6), by contrast, are linear combinations of the two principal
directions ${\mathbf{e}}_{2}-{\mathbf{e}}_{1},{\mathbf{e}}_{2}$ that come from
the leading coefficients of the polynomials in (3) and their pairwise
differences. Thus the problem of quantitative concatenation of box norms gains
a layer of difficulty when one passes from the $1$-dimensional setting of
Peluse and Prendiville to the multidimensional setting.

The goal of this paper is to prove a new quantitative concatenation result
that is robust enough to handle the averages of polynomial box norms output by
the PET argument for multidimensional polynomial progressions. This results in
the following box-norm-control for general multidimensional polynomial
progressions.

######  Theorem 1.1.

Let $d,\ell\in{\mathbb{N}}$. There exists a positive integer $t=O_{d,\ell}(1)$
such that the following holds. Let $D,N\in{\mathbb{N}}$ and $\delta>0$ satisfy
$N\gg_{d,D,\ell}\delta^{-O_{d,\ell}(1)}$, and let
${\textbf{P}}_{1},\ldots,{\textbf{P}}_{\ell}\in{\mathbb{Z}}^{D}[z]$ be
polynomials of the form
${\textbf{P}}_{j}(z)=\sum_{i=0}^{d}{\boldsymbol{\beta}}_{ji}z^{i}$ with
coefficients of size $O(1)$. Then for all $1$-bounded functions
$f_{0},\ldots,f_{\ell}:{\mathbb{Z}}^{D}\to{\mathbb{C}}$ supported on
$[N]^{D}$, the bound

(8)
$\displaystyle\mathopen{}\left|\sum_{{\textbf{x}}\in{\mathbb{Z}}^{D}}\operatorname*{\mathbb{E}}_{z\in[N^{1/d}]}f_{0}({\textbf{x}})\cdot
f_{1}({\textbf{x}}+{\textbf{P}}_{1}(z))\cdots
f_{\ell}({\textbf{x}}+{\textbf{P}}_{\ell}(z))\mathclose{}\right|\geq\delta
N^{D}$

implies that

(9)
$\displaystyle\left\|f_{j}\right\|_{\\{({\boldsymbol{\beta}}_{jd_{jj^{\prime}}}-{\boldsymbol{\beta}}_{j^{\prime}d_{jj^{\prime}}})\cdot[\pm
N^{d_{jj^{\prime}}/d}]:\;j^{\prime}\in[0,\ell],\;j^{\prime}\neq
j\\}^{t}}^{2^{\ell t}}\gg_{d,D,\ell}\delta^{O_{d,\ell}(1)}N^{D}$

for all $j\in[0,\ell]$, where
$d_{jj^{\prime}}=\deg({\textbf{P}}_{j}-{\textbf{P}}_{j^{\prime}})$ and
${\textbf{P}}_{0}=\mathbf{0}$.

Informally, Theorem 1.1 asserts that every multidimensional polynomial
progression can be controlled, with polynomial losses, by a single box norm of
bounded degree along the “correct” boxes. Let us explain in words why the box
norm in (9) is what one “should” expect, and specifically why it involves
intervals of length $\asymp N^{d_{jj^{\prime}}/d}$ in the directions
${\boldsymbol{\beta}}_{jd_{jj^{\prime}}}-{\boldsymbol{\beta}}_{j^{\prime}d_{jj^{\prime}}}$.
Consider the special case where all of the $f_{i}$’s except for
$f_{j},f_{j^{\prime}}$ are the constant function $1$.444Obviously, such
functions do not satisfy the assumption of being supported on $[N]^{D}$, but
this example can be modified slightly to fit the assumptions of the more
general Theorem 1.6 below. Shifting
${\textbf{x}}\mapsto{\textbf{x}}-{\textbf{P}}_{j^{\prime}}(z)$, we find that
(8) simplifies to

$\displaystyle\sum_{{\textbf{x}}\in{\mathbb{Z}}^{D}}\operatorname*{\mathbb{E}}_{z\in[N^{1/d}]}f_{j^{\prime}}({\textbf{x}})f_{j}({\textbf{x}}+{\textbf{P}}_{j}(z)-{\textbf{P}}_{j^{\prime}}(z))\geq\delta
N^{D}.$

The polynomial ${\textbf{P}}_{j}-{\textbf{P}}_{j^{\prime}}$ has degree
$d_{jj^{\prime}}$ and leading coefficient
${\boldsymbol{\beta}}_{jd_{jj^{\prime}}}-{\boldsymbol{\beta}}_{j^{\prime}d_{jj^{\prime}}}$.
Applying the classical van der Corput inequality $d_{jj^{\prime}}$ times
removes the lower-order terms of ${\textbf{P}}_{j}-{\textbf{P}}_{j^{\prime}}$
and (more or less) results in the inequality

$\displaystyle\sum_{{\textbf{x}}\in{\mathbb{Z}}^{D}}\operatorname*{\mathbb{E}}_{h_{1},\ldots,h_{d_{jj^{\prime}}}\in[N^{1/d}]}f_{j}({\textbf{x}})f_{j}({\textbf{x}}+d!({\boldsymbol{\beta}}_{jd_{jj^{\prime}}}-{\boldsymbol{\beta}}_{j^{\prime}d_{jj^{\prime}}})h_{1}\cdots
h_{d_{jj^{\prime}}})\gg_{d_{jj^{\prime}}}\delta^{O_{d_{jj^{\prime}}}(1)}N^{D}.$

One can use iterated applications of the Cauchy–Schwarz inequality to replace
the monomial $h_{1}\cdots h_{d_{jj^{\prime}}}$ with a single variable ranging
over $[N^{d_{jj^{\prime}}/d}]$, and this morally gives the largeness of a box
norm of $f_{j}$ along the progression
$({\boldsymbol{\beta}}_{jd_{jj^{\prime}}}-{\boldsymbol{\beta}}_{j^{\prime}d_{jj^{\prime}}})\cdot[\pm
N^{d_{jj^{\prime}}/d}]$. The large multiplicity $t$ appearing in Theorem 1.1
is an artifact of the large number of applications of the Cauchy–Schwarz
inequality in both the PET induction scheme and the concatenation arguments.

For $D>1$, the results of Theorem 1.1 and the more general Theorem 1.6 below
are completely novel. For $D=1$, they recover Peluse’s concatenation result
[23, Theorem 6.1] and also address some configurations that are not covered by
Peluse’s work.

######  Example 1.2.

As an example of a 1-dimensional configuration not covered by [23, Theorem
6.1], take $x,\;x+x^{2},\;x+2z^{2},\;x+2z^{2}+z$. If

$\displaystyle\Bigl{|}\sum_{x\in{\mathbb{Z}}}\operatorname*{\mathbb{E}}_{z\in[N^{1/2}]}f_{0}(x)f_{1}(x+z^{2})f_{2}(x+2z^{2})f_{3}(x+2z^{2}+z)\Bigr{|}\geq\delta
N,$

then Theorem 1.1 (combined with standard properties of box norms listed in
Lemma 3.5) gives a positive integer $t=O(1)$ for which

$\displaystyle\left\|f_{0}\right\|_{U^{t}([\pm
N])}^{2^{t}},\left\|f_{1}\right\|_{U^{t}([\pm
N])}^{2^{t}}\gg\delta^{O(1)}N\quad\text{and}\quad\left\|f_{2}\right\|_{U^{t}([\pm
N^{1/2}])}^{2^{t}},\left\|f_{3}\right\|_{U^{t}([\pm
N^{1/2}])}^{2^{t}}\gg\delta^{O(1)}N.$

The disparity in the scales of these Gowers norms comes from the polynomials
$2z^{2},\;2z^{2}+z$ having the same leading coefficient: Since the difference
of these polynomials is a linear polynomial that ranges over an interval of
length $\asymp N^{1/2}$ rather than $\asymp N$, the shifting parameters in the
Gowers norms controlling $f_{2}$ and $f_{3}$ must be at the smaller scale
$N^{1/2}$. For configurations like this in which several polynomials have the
same leading coefficients, [23, Theorem 6.1] does not give any nontrivial box-
norm-control, so our result is novel in this case. We remark as a side note
that such restricted Gowers norms are often difficult to use in applications
because the inverse theorem for the $U^{t}([\pm N^{1/2}])$-norm involves
correlations with $(t-1)$-step nilsequences on short intervals of length
$\asymp N^{1/2}$, with no discernible global (i.e., scale-$N$) structure.

When the polynomials ${\textbf{P}}_{j}$ have distinct degrees, the conclusion
of Theorem 1.1 radically simplifies.

######  Corollary 1.3.

Let $d,\ell\in{\mathbb{N}}$. There exists a positive integer $t=O_{d,\ell}(1)$
such that the following holds. Let $D,N\in{\mathbb{N}}$ and $\delta>0$ satisfy
$N\gg_{d,D,\ell}\delta^{-O_{d,\ell}(1)}$, let
${\textbf{v}}_{1},\ldots,{\textbf{v}}_{\ell}\in{\mathbb{Z}}^{{D}}$ be nonzero
vectors of size $O(1)$, and let $P_{1},\ldots,P_{\ell}\in{\mathbb{Z}}[z]$ be
polynomials with coefficients of size $O(1)$ and degrees

$\displaystyle 1\leq\deg P_{1}<\cdots<\deg P_{\ell}=d.$

Then for all $1$-bounded functions
$f_{0},\ldots,f_{\ell}:{\mathbb{Z}}^{D}\to{\mathbb{C}}$ supported on
$[N]^{D}$, the bound

$\displaystyle\mathopen{}\left|\sum_{{\textbf{x}}\in{\mathbb{Z}}^{D}}\operatorname*{\mathbb{E}}_{z\in[N^{1/d}]}f_{0}({\textbf{x}})\cdot
f_{1}({\textbf{x}}+{\textbf{v}}_{1}P_{1}(z))\cdots
f_{\ell}({\textbf{x}}+{\textbf{v}}_{\ell}P_{\ell}(z))\mathclose{}\right|\geq\delta
N^{D}$

implies that

$\displaystyle\left\|f_{\ell}\right\|_{U^{t}({\textbf{v}}_{\ell}\cdot[\pm
N])}^{2^{t}}\gg_{d,D,\ell}\delta^{O_{d,\ell}(1)}N^{D}.$

######  Example 1.4.

In particular, Corollary 1.3 recovers the Gowers-norm-control obtained by
Peluse and Prendiville in [24]: It shows that if

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

then $\left\|f_{2}\right\|_{U^{t}([\pm N])}^{2^{t}}\gg\delta^{O(1)}N$ for some
positive integer $t=O(1)$.

######  Example 1.5.

Corollary 1.3 also recovers the Gowers-norm-control obtained by Peluse,
Prendiville and Shao in [26]: It shows that if

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

then $\left\|f_{2}\right\|_{U^{t}({\mathbf{e}}_{2}\cdot[\pm
N])}^{2^{t}}\gg\delta^{O(1)}N^{2}$ for some positive integer $t=O(1)$.

It is often desirable for technical reasons to consider polynomial
progressions with “$W$-tricked” polynomials whose coefficients grow (in a
controlled way) with the parameter $N$. We in fact prove the following more
general version of Theorem 1.1 which is flexible enough to accommodate
$W$-tricks.

######  Theorem 1.6.

Let $d,\ell\in{\mathbb{N}}$. There exists a positive integer $t=O_{d,\ell}(1)$
such that the following holds. Let $D,K,N,V\in{\mathbb{N}}$ and $\delta>0$
satisfy

$\delta^{-O_{d,\ell}(1)}\ll_{d,D,\ell}K\ll_{d,D,\ell}(N/V)^{1/d},$

and let ${\textbf{P}}_{1},\ldots,{\textbf{P}}_{\ell}\in{\mathbb{Z}}^{D}[z]$ be
polynomials of the form
${\textbf{P}}_{j}(z)=\sum_{i=0}^{d}{\boldsymbol{\beta}}_{ji}z^{i}$ with
coefficients at most $V$.555In the sense that for every $j,i$, each coordinate
of ${\boldsymbol{\beta}}_{ji}$ is at most $V$ in absolute value, or
equivalently that ${\boldsymbol{\beta}}_{ji}\in[\pm V]^{D}$. Then for all
$1$-bounded functions $f_{0},\ldots,f_{\ell}:{\mathbb{Z}}^{D}\to{\mathbb{C}}$
supported on $[N]^{D}$, the bound

$\displaystyle\mathopen{}\left|\sum_{{\textbf{x}}\in{\mathbb{Z}}^{D}}\operatorname*{\mathbb{E}}_{z\in[K]}f_{0}({\textbf{x}})\cdot
f_{1}({\textbf{x}}+{\textbf{P}}_{1}(z))\cdots
f_{\ell}({\textbf{x}}+{\textbf{P}}_{\ell}(z))\mathclose{}\right|\geq\delta
N^{D}$

implies that

(10)
$\displaystyle\left\|f_{j}\right\|_{\\{({\boldsymbol{\beta}}_{jd_{jj^{\prime}}}-{\boldsymbol{\beta}}_{j^{\prime}d_{jj^{\prime}}})\cdot[\pm
K^{d_{jj^{\prime}}}]:\;j^{\prime}\in[0,\ell],\;j^{\prime}\neq
j\\}^{t}}^{2^{\ell t}}\gg_{d,D,\ell}\delta^{O_{d,\ell}(1)}N^{D}$

for all $j\in[0,\ell]$, where
$d_{jj^{\prime}}=\deg({\textbf{P}}_{j}-{\textbf{P}}_{j^{\prime}})$ and
${\textbf{P}}_{0}=\mathbf{0}$.

When ${\textbf{P}}_{1},\ldots,{\textbf{P}}_{\ell}$ are all
${\mathbb{Z}}^{D}$-multiples of a single integer polynomial, Theorem 1.6
reduces to the following.

######  Corollary 1.7.

Let $d,\ell\in{\mathbb{N}}$. There exists a positive integer $t=O_{d,\ell}(1)$
such that the following holds. Let $D\in{\mathbb{N}}$, let
${\textbf{v}}_{0},\ldots,{\textbf{v}}_{\ell}\in{\mathbb{Z}}^{{D}}$ be nonzero
vectors of size $O(1)$ (with ${\textbf{v}}_{0}=\mathbf{0}$), and let
$P\in{\mathbb{Z}}[z]$ be a degree-$d$ polynomial with leading coefficient
$\beta_{d}$. Then for all $N\in{\mathbb{N}}$ and $1$-bounded functions
$f_{0},\ldots,f_{\ell}:{\mathbb{Z}}^{D}\to{\mathbb{C}}$ supported on
$[N]^{D}$, the bound

$\displaystyle\mathopen{}\left|\sum_{{\textbf{x}}\in{\mathbb{Z}}^{D}}\operatorname*{\mathbb{E}}_{z\in[(N/\beta_{d})^{1/d}]}f_{0}({\textbf{x}})\cdot
f_{1}({\textbf{x}}+{\textbf{v}}_{1}P(z))\cdots
f_{\ell}({\textbf{x}}+{\textbf{v}}_{\ell}P(z))\mathclose{}\right|\geq\delta
N^{D}$

implies that

$\displaystyle\left\|f_{j}\right\|_{\\{\beta_{d}({\textbf{v}}_{j}-{\textbf{v}}_{j^{\prime}})\cdot[\pm
N/\beta_{d}]:\;j^{\prime}\in[0,\ell],\;j^{\prime}\neq j\\}^{t}}^{2^{\ell
t}}\gg_{d,D,\ell}\delta^{O_{d,\ell}(1)}N^{D}$

for all $j\in[0,\ell]$.

######  Example 1.8.

If $D=1$ and ${\textbf{v}}_{j}=j$, Corollary 1.7 tells us that

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

implies that

$\displaystyle\min_{j\in[0,\ell]}\left\|f_{j}\right\|^{2^{t}}_{U^{t}(\beta_{d}\cdot[\pm
N/\beta_{d}])}\gg_{d,\ell}\delta^{O_{d,\ell}(1)}N$

for some positive integer $t=O_{d,\ell}(1)$, where we recall that $\beta_{d}$
is the leading coefficient of $P$. This improves on the Gowers-norm-control
obtained by Prendiville in [28] and recovers the global Gowers-norm-control
used by Peluse, Sah and Sawhney in [27].

######  Example 1.9.

If $\ell=D=2$ and ${\textbf{v}}_{j}={\mathbf{e}}_{j}$, Corollary 1.7 tells us
that

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

implies that

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

for some positive integer $t=O(1)$. This result serves as the starting point
for our companion paper [14].

Our new concatenation result (the key ingredient in the proof of Theorem 1.6)
is the following.

######  Theorem 1.10.

Let $r,s\in{\mathbb{N}}$. There exists a positive integer $t=O_{r,s}(1)$ such
that the following holds. Let $d,D,H,M,N,V\in{\mathbb{N}}$ and $\delta>0$
satisfy

$\displaystyle d\leq r,\quad\delta^{-O_{\ell,r,s}(1)}\ll_{D,r,s}H\leq
M\quad\textrm{and}\quad H^{d}MV\leq N,$

and let
${\textbf{C}}_{1},\ldots,{\textbf{C}}_{s}\in{\mathbb{Z}}^{D}[h_{1},\ldots,h_{r}]$
be multilinear polynomials
${\textbf{C}}_{j}({\underline{h}})=\sum\limits_{{\underline{u}}\in\\{0,1\\}^{r}}{\boldsymbol{\gamma}}_{j{\underline{u}}}{\underline{h}}^{\underline{u}}$
of degree at most $d$ and with coefficients at most $V$. Then for all
$1$-bounded functions $f:{\mathbb{Z}}^{D}\to{\mathbb{C}}$ supported on
$[N]^{D}$, the bound

$\displaystyle\operatorname*{\mathbb{E}}_{{\underline{h}}\in[\pm
H]^{r}}\left\|f\right\|_{{\textbf{C}}_{1}({\underline{h}})\cdot[\pm
M],\ldots,{\textbf{C}}_{s}({\underline{h}})\cdot[\pm M]}^{2^{s}}\geq\delta
N^{D}$

implies that

$\displaystyle\left\|f\right\|_{E_{1}^{t},\ldots,E_{s}^{t}}^{2^{st}}\gg_{D,r,s}\delta^{O_{r,s}(1)}N^{D},$

where

$\displaystyle
E_{j}=\sum_{{\underline{u}}\in\\{0,1\\}^{d}}{\boldsymbol{\gamma}}_{j{\underline{u}}}\cdot[\pm
H^{|{\underline{u}}|+1}].$

###  1.1. 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 Sarah Peluse, Mehtaab Sawhney, and Terry Tao for
helpful discussions and for comments on a draft of this paper.

##  2\. Proof strategy

Because the proofs of our main results are rather technical, we will begin
with an informal discussion of how our techniques apply to a few simplified
examples.

The proof of Theorem 1.6 begins with PET induction, a complexity-reduction
argument that allows us to control the counting operator of a polynomial
progression by an average of box norms. While PET arguments are now standard
and have been carried out in many places (see, e.g., [1, 3, 5, 23, 28]), we
need to keep careful track of the structure of the polynomial differencing
parameters ${\textbf{C}}_{j}$ that are output by PET. In general, the input of
PET is the counting operator lower bound

$\displaystyle{\sum_{{\textbf{x}}\in{\mathbb{Z}}^{D}}\operatorname*{\mathbb{E}}_{z\in[N^{1/d}]}f_{0}({\textbf{x}})\cdot
f_{1}({\textbf{x}}+{\textbf{P}}_{1}(z))\cdots
f_{\ell}({\textbf{x}}+{\textbf{P}}_{\ell}(z))}\geq\delta N^{D},$

for some polynomials
${\textbf{P}}_{1},\ldots,{\textbf{P}}_{\ell}\in{\mathbb{Z}}^{D}[z]$ of degree
at most $d$ and some $1$-bounded functions $f_{0},\ldots,f_{\ell}$ supported
on $[N]^{D}$. The output of PET is then that the average of box norms

(11) $\displaystyle\operatorname*{\mathbb{E}}_{{\underline{h}}\in[\pm
N^{1/d}]^{r}}\left\|f\right\|_{{{\textbf{C}}_{1}({\underline{h}})\cdot[\pm
N^{1/d}]},\ldots,{{\textbf{C}}_{s}({\underline{h}})\cdot[\pm
N^{1/d}]}}^{2^{s}}\gg\delta^{O(1)}N^{D}$

is also large. (Here and elsewhere, we allow all $O(1)$ terms to depend on
$d,\ell$.) Two crucial properties of this output are that the polynomials
${\textbf{C}}_{1},\ldots,{\textbf{C}}_{s}\in{\mathbb{Z}}^{D}[h_{1},\ldots,h_{r}]$
appearing above are multilinear and that their coefficients are
$O(1)$-multiples of the leading coefficients of
${\textbf{P}}_{1},\ldots,{\textbf{P}}_{\ell}$ and of their pairwise
differences. This PET argument is carried out in detail in Section 4.

Sections 5–8 are then devoted to the proof of Theorem 1.10, our main
concatenation result, which we will focus on in the remainder of this sketch.
To differentiate between the ranges of the various parameters, let us rewrite
(11) as

(12) $\displaystyle\operatorname*{\mathbb{E}}_{{\underline{h}}\in[\pm
H]^{r}}\left\|f\right\|_{{{\textbf{C}}_{1}({\underline{h}})\cdot[\pm
M]},\ldots,{{\textbf{C}}_{s}({\underline{h}})\cdot[\pm M]}}^{2^{s}}\gg\delta
N^{D},$

where we have set $H:=M:=N^{1/d}$ and replaced $\delta^{O(1)}$ with $\delta$.
(It will later be convenient to be able to consider slightly different values
of $H,M$.)

We begin with the very simplest example, namely, where $d=2$, $D=s=r=1$, and
${\textbf{C}}_{1}(h)=h$, so that our hypothesis is

$\operatorname*{\mathbb{E}}_{h\in[\pm H]}\left\|f\right\|^{2}_{h\cdot[\pm
M]}\gg\delta N.$

Ignoring smoothing terms, we can expand this as

$\operatorname*{\mathbb{E}}_{h\in[\pm H]}\operatorname*{\mathbb{E}}_{m\in[\pm
M]}\sum_{x\in\mathbb{Z}}f(x)\overline{f(x+hm)}.$

If the quantity $hm$ ranged over $[\pm HM]$ uniformly as $h,m$ ranged, then we
could replace $hm$ by a new variable $t$ and conclude that
$\left\|f\right\|_{[\pm HM]}^{2}\gg\delta N$. This is of course not the case,
but our goal will be to reach a similar situation. Exchanging the order of
summation and applying the Cauchy–Schwarz inequality twice, we obtain

$\operatorname*{\mathbb{E}}_{h_{1},h_{2},h_{3},h_{4}\in[\pm
H]}\operatorname*{\mathbb{E}}_{m_{1},m_{2},m_{3},m_{4}\in[\pm
M]}\sum_{x\in{\mathbb{Z}}}f(x)\overline{f(x+h_{1}m_{1}+h_{2}m_{2}+h_{3}m_{3}+h_{4}m_{4})}\gg\delta^{4}N.$

An elementary number-theoretic argument (see Corollary 7.2 below) tells us
that the quantity $h_{1}m_{1}+h_{2}m_{2}+h_{3}m_{3}+h_{4}m_{4}$ assumes each
value $t\in[\pm 4HM]$ at most $O(H^{3}M^{3})$ times as
$h_{1},h_{2},h_{3},h_{4},m_{1},m_{2},m_{3},m_{4}$ range; in other words, this
quantity is nearly uniformly distributed, in the sense of being very anti-
concentrated. The idea behind the lemma is that for most fixed choices of the
$h_{i}$’s, the expression is well-distributed as the $m_{i}$’s range; more
precisely, this is the case unless $\gcd(h_{1},h_{2},h_{3},h_{4})$ is big or
all of the $h_{i}$’s are small, and there are very few such “bad” choices.
Together with the triangle inequality, this fact implies (after some work)
that

$\operatorname*{\mathbb{E}}_{t\in[\pm
4HM]}\mathopen{}\left|\sum_{x\in{\mathbb{Z}}}f(x)\overline{f(x+t)}\mathclose{}\right|\gg\delta^{O(1)}N.$

Using the Cauchy–Schwarz inequality to remove the absolute value gives

$\operatorname*{\mathbb{E}}_{t\in[\pm
4HM]}\sum_{x,s\in{\mathbb{Z}}}f(x)\overline{f(x+t)}\overline{f(x+s)}f(x+s+t)\gg\delta^{O(1)}N^{2}.$

Since $f$ is supported on $[N]$, we can restrict the $s$-variable to $[-N,N]$
(say), and renormalizing gives

$\left\|f\right\|^{4}_{[\pm 4HM],[\pm N]}=\operatorname*{\mathbb{E}}_{t\in[\pm
4HM]}\operatorname*{\mathbb{E}}_{s\in[\pm
N]}\sum_{x\in{\mathbb{Z}}}f(x)\overline{f(x+t)}\overline{f(x+s)}f(x+s+t)\gg\delta^{O(1)}N.$

So we have successfully concatenated the differencing sets $[\pm H],[\pm M]$
into a single differencing set $[\pm 4HM]$, at the cost of introducing an
additional differencing over $[\pm N]$. Using monotonicity properties of box
norms (see Lemma 3.5 below), we can “trim” $[\pm 4HM],[\pm N]$ and replace
each of them with a copy of $[\pm HM]$.

For our next example, take $d=3$, $r=2$, $D=s=1$, and
${\textbf{C}}_{1}(h_{1},h_{2})=h_{1}h_{2}$, so that our hypothesis is

$\operatorname*{\mathbb{E}}_{h_{1},h_{2}\in[\pm
H]}\left\|f\right\|^{2}_{h_{1}h_{2}\cdot[\pm M]}\gg\delta N.$

Expanding the left-hand side and using the Cauchy–Schwarz inequality to
duplicate the differencing parameters, as in the first example, gives

$\operatorname*{\mathbb{E}}_{h_{11},\ldots h_{14}\in[\pm
H]}\operatorname*{\mathbb{E}}_{h_{21},\ldots h_{24}\in[\pm
H]}\operatorname*{\mathbb{E}}_{m_{1},\ldots,m_{4}\in[\pm
M]}\sum_{x\in\mathbb{Z}}\\\
f(x)\overline{f(x+h_{11}h_{21}m_{1}+h_{12}h_{22}m_{2}+h_{13}h_{23}m_{3}+h_{14}h_{24}m_{1})}\gg\delta^{4}N.$

If the quantity
$h_{11}h_{21}m_{1}+h_{12}h_{22}m_{2}+h_{13}h_{23}m_{3}+h_{14}h_{24}m_{1}$ were
nearly uniformly distributed on its range $[\pm H^{2}M]$, then we could
replace it by a single new variable ranging over $[\pm H^{2}M]$ and conclude
as in the first example. But this quantity fails to be sufficiently anti-
concentrated, essentially because it is too often divisible by squares of
small primes. The solution to this problem is to apply the Cauchy–Schwarz
inequality several more times in order to replace each term $h_{2j}m_{j}$ with
the expression

$h_{2j1}m_{j1}+h_{2j2}m_{j2}+h_{2j3}m_{j3}+h_{2j4}m_{j4}$

(at the cost of degrading the power of $\delta$, which we do not care about).
As the variables range, this expression is nearly uniformly distributed on
$[\pm 4HM]$ (as in the previous example), and so with an acceptably small loss
we can replace it by a new variable $t_{j}$ that ranges over $[\pm 4HM]$. In
turn, the expression

$h_{11}t_{1}+h_{12}t_{2}+h_{13}t_{3}+h_{14}t_{4}$

is nearly uniformly distributed on $[\pm 16H^{2}M]$, and we conclude as in the
first example.

This strategy of constructing large “expanding” polynomials with nested
equidistribution properties suffices to handle the general case where $s=1$
and ${\textbf{C}}_{1}$ is a monomial. When ${\textbf{C}}_{1}$ is not a
monomial, we must show that several multilinear expressions are simultaneously
nearly uniformly distributed. For example, with $d=3$, $r=D=2$, $s=1$, and
${\textbf{C}}_{1}(h_{1},h_{2})=h_{1}h_{2}{\mathbf{e}}_{1}+h_{1}{\mathbf{e}}_{2}=(h_{1}h_{2},h_{1})$,
our hypothesis

$\operatorname*{\mathbb{E}}_{h_{1},h_{2}\in[\pm
H]}\left\|f\right\|^{2}_{(h_{1}h_{2}{\mathbf{e}}_{1}+h_{1}{\mathbf{e}}_{2})\cdot[\pm
M]}\gg\delta N$

leads to the bound

(13) $\operatorname*{\mathbb{E}}_{\begin{subarray}{c}h_{i}\in[\pm H]:\\\
i\in[4]\end{subarray}}\;\operatorname*{\mathbb{E}}_{\begin{subarray}{c}h_{ij}\in[\pm
H]:\\\
i,j\in[4]\end{subarray}}\;\operatorname*{\mathbb{E}}_{\begin{subarray}{c}m_{ij}\in[\pm
M]:\\\ i,j\in[4]\end{subarray}}\;\sum_{{\textbf{x}}\in\mathbb{Z}^{2}}\\\
f({\textbf{x}})\overline{f\Bigl{(}{\textbf{x}}+\Bigl{(}\sum_{i\in[4]}h_{i}\sum_{j\in[4]}h_{ij}m_{ij}\Bigr{)}{\mathbf{e}}_{1}+\Bigl{(}\sum_{i\in[4]}h_{i}\sum_{j\in[4]}m_{ij}\Bigr{)}{\mathbf{e}}_{2}\Bigr{)}}\gg\delta^{O(1)}N^{2}$

after the usual Cauchy–Schwarz maneuvers, so we wish to show that the
${\mathbf{e}}_{1}$\- and ${\mathbf{e}}_{2}$-coefficients are simultaneously
equidistributed. The first step is showing that for each $i\in[4]$, the
expressions

$\sum_{j\in[4]}h_{ij}m_{ij},\quad\sum_{j\in[4]}m_{ij}$

are simultaneously equidistributed. Dropping the $i$’s from the indices, we
need to show that for each pair $(n_{0},n_{1})\in[\pm 4M]\times[\pm 4HM]$, the
system of equations

$m_{1}+m_{2}+m_{3}+m_{4}=n_{0},\quad
h_{1}m_{1}+h_{2}m_{2}+h_{3}m_{3}+h_{4}m_{4}=n_{1}$

has at most $O(H^{3}M^{2})$ solutions. (Here $H^{3}M^{2}=H^{4}M^{4}/(HM\cdot
M)$.) The new idea here is that we can solve for $m_{1}$ in the second
equation and make a substitution into the first equation, which (after
regrouping) yields

$(h_{2}-h_{1})m_{2}+(h_{3}-h_{1})m_{3}+(h_{4}-h_{1})m_{4}=n_{1}-h_{1}n_{0}.$

Our previous arguments imply that for each of the $O(H)$ choices for $h_{1}$,
this equation has at most $O(H^{2}M^{2})$ solutions
$(h_{2},h_{3},h_{4},m_{2},m_{4},m_{4})$. Such a solution can be extended to at
most one choice of $m_{1}$ (sometimes there are no choices for $m_{1}$ because
we constrained it to lie in $[\pm M]$), so in total we have at most
$O(H^{3}M^{2})$ solutions, as desired.

Using the first step, we replace
$\sum_{j\in[4]}h_{ij}m_{ij},\sum_{j\in[4]}m_{ij}$ with new variables
$t_{i},t^{\prime}_{i}$ ranging over $[\pm 4HM],[\pm 4M]$, respectively, and it
remains to show that the expressions

$\sum_{i\in[4]}h_{i}t_{i},\quad\sum_{i\in[4]}h_{i}t^{\prime}_{i}$

are simultaneously equidistributed. These expressions are individually
identical to the expressions that we discussed above, but they are coupled in
the sense that the variables $h_{i}$ appear in both expressions. It turns out
that the few “bad” choices of $h_{1},h_{2},h_{3},h_{4}$ are now too costly
because they lead to concentration in both expressions. The solution to this
problem is to eliminate the bad choices before counting solutions: We can
throw out the bad tuples $(h_{1},h_{2},h_{3},h_{4})$ in (13) at the cost of
degrading the implicit constant in the inequality.

To apply this type of multiscale analysis to multilinear expressions whose
degrees differ by more than $1$, we introduce dummy expressions at the
intermediate degrees and then run the above argument for pairs of expressions
with consecutive degrees. The genericity assumption on the $h$’s is an
essential technical element. The details, which are quite delicate, are
carried out in Section 7.

Further difficulties arise for $s>1$. In the $s=1$ case, we iteratively used
the Cauchy–Schwarz inequality to double certain variables. When $s>1$, this
maneuever also increases the number of multilinear expressions that must be
simultaneously equidistributed—which in turn potentially requires further
applications of the Cauchy–Schwarz inequality to replace these new expressions
by ones with good equidistribution properties. Using arguments originally
developed by the second author [16] for concatenation in the finite-field
setting, we show in Section 6 that this process can be satisfactorily
controlled. This part of our proof uses no information about the “polynomial”
nature of our box-norm parameters, and it ends up being convenient to carry
out the argument in the more general setting of averages of box norms

(14) $\displaystyle\operatorname*{\mathbb{E}}_{i\in
I}\left\|f\right\|_{H_{1i},\ldots,H_{si}}^{2^{s}},$

where $H_{1i},\ldots,H_{si}$ for $i\in I$ are arbitrary finite multisets of a
finitely generated abelian group $G$ that are contained in a bounded dilate of
the support of $f$. We also believe that this level of generality might be
useful for future extensions of our concatenation argument to other settings.

The key idea for handling (14), elucidated in Lemma 6.1, is to use the
Cauchy–Schwarz and Gowers–Cauchy–Schwarz Inequalities in order to control (14)
by

$\displaystyle\operatorname*{\mathbb{E}}_{i_{0},i_{1}\in
I}\left\|f\right\|_{H_{1i_{0}}-H_{1i_{1}},H_{2i_{0}},H_{2i_{1}}\ldots,H_{si_{0}},H_{si_{1}}}^{2^{2s-1}};$

we see that the multiset $H_{1i}$ got replaced by a potentially much better
distributed multiset $H_{1i_{0}}-H_{1i_{1}}$ at the cost of doubling the
number of remaining multisets. Iterating this procedure many times, we can
control (14) by an analogous expression in which each multiset $H_{ji}$ is
replaced by many iterated multisets of the form
$H_{ji_{1}}+\cdots+H_{ji_{\ell}}$. In the first example discussed above, this
process corresponds to replacing $hm$ by
$h_{1}m_{1}+h_{2}m_{2}+h_{3}m_{3}+h_{4}m_{4}$, and we have already established
that the latter expression enjoys better equidistribution properties.

The last step of our argument, described in Section 8, specializes this
general concatenation result to our “polynomial” setting and shows how it can
be massaged to lead to the types of systems of multilinear equations described
above. The results from Section 6 allow us to replace the boxes
${\textbf{C}}_{j}({\underline{h}})\cdot[\pm M]$ in (12) by iterated sums

(15)
$\displaystyle\sum_{i_{1},\ldots,i_{r}=1}^{\ell}{\textbf{C}}_{j}(h_{1i_{1}}\cdots
h_{ri_{1}\cdots i_{r}})\cdot[\pm M].$

Each such box generates a system of multilinear equations, corresponding to
the monomials in the polynomial ${\textbf{C}}_{j}$. The arguments from Section
7 then give that if
${\textbf{C}}_{j}({\underline{h}})=\sum\limits_{{\underline{u}}\in\\{0,1\\}^{r}}{\boldsymbol{\gamma}}_{j{\underline{u}}}{\underline{h}}^{\underline{u}}$,
then (15) is uniformly distributed in the box
$\sum\limits_{{\underline{u}}\in\\{0,1\\}^{d}}{\boldsymbol{\gamma}}_{j{\underline{u}}}\cdot[\pm
H^{|{\underline{u}}|+1}]$. This concludes the proof of Theorem 1.10.

In Section 9, we combine the conclusions of Theorem 1.10 with the output of
PET to prove Theorem 1.6. In doing so, we use the important observation from
PET that the coefficients of the polynomials ${\textbf{C}}_{j}$ are
$O(1)$-multiples of the leading coefficients of the polynomials
${\textbf{P}}_{1},\ldots,{\textbf{P}}_{\ell}$ and their pairwise differences.

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

Concatenation of general box norms (Corollary 6.4) Concatenation of polynomial
box norms (Proposition 8.1) Equidistribution for multilinear systems
(Proposition 7.5) Quantitative concatenation (Theorem 1.10) PET induction
(Proposition 4.8) Final box-norm-control (Theorem 1.6) Figure 1. The main
steps and logical implications in the proof of Theorem 1.6.

###  2.1. Comparison with previous approaches

Our argument deviates in several ways from previous concatenation arguments in
the literature: the quantitative concatenation arguments of Peluse and
Prendiville [23, 24, 29] for $1$-dimensional polynomial progressions over
${\mathbb{Z}}$; the second author’s quantitative concatenation arguments for
multidimensional polynomial progressions over finite fields [16]; and the
original qualitative argument of Tao and Ziegler [34], together with its later
development in the context of ergodic theory (e.g., [5]).

One difference between our argument and the approach of Peluse and Prendiville
[23, 24, 29] lies in the order of carrying out two major maneuvers, namely,
duplicating variables using the Cauchy–Schwarz inequality, and replacing a
multilinear polynomial like $h_{1}m_{1}+h_{2}m_{2}+h_{3}m_{3}+h_{4}m_{4}$ by a
new variable using equidistribution properties. As described in the sketch
above, our argument clearly separates these two operations: First, we apply
the Cauchy–Schwarz inequality many times to convert the original average (12)
into one where each arithmetic progression
${\textbf{C}}_{j}({\underline{h}})\cdot[\pm M]$ can be replaced by a
generalized arithmetic progression
${\textbf{C}}_{j}({\underline{h}}_{1})\cdot[\pm
M]+\cdots+{\textbf{C}}_{j}({\underline{h}}_{\ell})\cdot[\pm M]$ (interpreted
as a multiset). Only then do we show that the massive system of multilinear
forms arising out of this procedure is equidistributed in its range. In [23,
24, 29], these two steps are intertwined: Applications of the Cauchy–Schwarz
inequality are followed by equidistribution results for intermediate systems
of bilinear forms, then more applications of the Cauchy–Schwarz inequality,
and so on. While the approach of Peluse and Prendiville has the advantage of
using “simpler” equidistribution inputs (only systems of bilinear forms
appear), our approach has the advantages of clarity and of generality. In
particular, we are able to obtain quantitative concatenation results
(Corollaries 6.3 and 6.4) for averages of arbitrary box norms in arbitrary
finitely-generated abelian groups; these more closely resemble the qualitative
statements in the work of Tao and Ziegler [34].

Another important point of difference is the choice of induction scheme. In
[23], Peluse begins the induction with degree-$2$ box norms as the base case
(see [23, Lemma 5.5]), and she treats degree-$1$ box norms separately ([23,
Lemma 5.4]). The strategy in [24, 29] is organized the same way. Here, in
order to concatenate averages of degree-$2$ box norms, Peluse and Prendiville
apply an inverse theorem for $2$-dimensional box norms and then remove the
resulting structured functions using their periodicity properties. For us,
degree-$1$ box norms serve as the base case, which we analyze using a simple
application of the Cauchy–Schwarz inequality. Consequently, our approach is
more elementary and requires neither inverse theory nor periodicity
properties.

Furthermore, dealing with multidimensional progressions forces us to keep
careful track—more so than in [23]—of how polynomial coefficients change
during the PET procedure. Compared with the approach of [23], our coefficient-
tracking scheme666Our scheme is strongly inspired by a similar scheme from
[5], but it improves on the latter in that we are able to identify fewer (and
more relevant) properties that need to be tracked throughout PET. records more
information about lower-degree terms of polynomials. It is precisely this
extra information that allows Theorems 1.1 and 1.6 to extend Peluse’s result
even in the single-dimensional setting (see Example 1.2).

Last but not least, whereas Peluse and Prendiville use basic Fourier analysis
on several occasions, our argument is entirely carried out on the physical
side. In particular, we do not use Fourier analysis in replacing
equidistributed expressions like $h_{1}m_{1}+h_{2}m_{2}+h_{3}m_{3}+h_{4}m_{4}$
by a new variable.

The relationship between our argument and the recent quantitative
concatenation result over the finite fields by the second author [16] is more
complex. As already mentioned, our concatenation argument consists of two big
steps: handling averages of box norms (14) along arbitrary multisets by means
of the Cauchy–Schwarz inequality, and establishing equidistribution results
for systems of multilinear equations. The first of these steps is largely
based on an analogous argument from [16], and its adaptation to the integer
setting requires only minor technical modifications. The two approaches
deviate in the second step, in which we replace each monomial $h_{1}\cdots
h_{r}m$ by a new variable. This task is much simpler in the finite-field
setting because the monomial expression in question is already very uniformly
distributed; the integer setting requires several new ideas.

Like Tao and Ziegler [34], we ultimately prove a concatenation result for
general averages of box norms (14) (see Corollary 6.3). The methods, however
are completely different. Tao and Ziegler proceed by qualitatively analyzing
the interactions among the dual functions implicit in the definition of box
norms. Our proof of Corollary 6.3, by contrast, gives some truth to the
stereotype that higher-order Fourier analysis largely consists of clever
applications of the Cauchy–Schwarz inequality. Tao and Ziegler obtain better
control on the degree of the “concatenated” box norms, but their conclusion is
purely qualitative.

##  3\. Definitions and preliminaries

###  3.1. Basic notation

We write
${\mathbb{N}},{\mathbb{N}}_{0},{\mathbb{Z}},{\mathbb{R}},{\mathbb{C}}$ for the
sets of positive integers, nonnegative 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\\}$, abbreviating $[1,N]$
as $[N]$ and $[-N,N]$ as $[\pm N]$.

To facilitate the reading of the paper, we fix the uses of various letters.
The letter $d$ denotes the maximum degree of polynomials under consideration;
$D$ is the dimension of the ambient space ${\mathbb{Z}}^{D}$ in which we work;
$K$ measures the range of the polynomial variable $z$; $\ell$ is the length of
the polynomial family, and later on it also denotes the number of summands in
concatenated box norms; $N$ refers to the size of the support of the
functions; $r$ is the number of parameters $h_{1},\ldots,h_{r}$, and $H$
concerns their range; $s,t$ denote the degrees of box norms appearing in the
arguments; and $V$ bounds the size of polynomial coefficients.

We write ${\textbf{x}}=(x_{1},...,x_{D})$ for an element of ${\mathbb{Z}}^{D}$
(for some fixed $D\in{\mathbb{N}}$) as $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 usually write ${\underline{h}}=(h_{1},\ldots,h_{r})$ for a tuple of length
$r$, and we denote its $\ell^{1}$-norm by
$|{\underline{h}}|:=|h_{1}|+\cdots+|h_{r}|$. For
${\underline{u}}\in{\mathbb{N}}_{0}^{r}$, we let
$\operatorname{supp}({\underline{u}}):=\\{i\in[r]:\;u_{i}>0\\}$ and get the
monomial ${\underline{h}}^{\underline{u}}:=h_{1}^{u_{1}}\cdots h_{r}^{u_{r}}$.
Given ${\underline{h}},{\underline{h}}^{\prime}\in{\mathbb{Z}}^{r}$ and
${\underline{\epsilon}}\in\\{0,1\\}^{r}$, we also set
${\underline{h}}^{\underline{\epsilon}}:=(h_{1}^{\epsilon_{1}},\ldots,h_{r}^{\epsilon_{r}})$,
where $h_{i}^{\epsilon_{i}}:=h_{i}$ if $\epsilon_{i}=0$ and
$h_{i}^{\epsilon_{i}}:=h_{i}^{\prime}$ if $\epsilon_{i}=1$.

We frequently work with multisets.

######  Definition 3.1 (Multisets).

For a finite multiset $X$, we write $|X|$ for the total number of elements in
$X$, counted with multiplicity. We use $\operatorname{supp}(X)$ to denote the
set of elements appearing in $X$ with strictly positive multiplicity. With
regard to containment of multisets, we write $X\subseteq Y$ if the set
$\operatorname{supp}(X)$ is contained in the set $\operatorname{supp}(Y)$, and
we denote $X\leq Y$ if each element of $\operatorname{supp}(X)$ has
multiplicity at least as large in $Y$ as in $X$. Lastly, for multisets $X,Y$,
we define the sumset $X+Y$ to be the Minkowski sum of $X,Y$ with
multiplicities: The multiplicity of the element $z$ in $X+Y$ is $|\\{(x,y)\in
X\times Y:\;z=x+y\\}|$. Equivalently, the weight function of $X+Y$ is the
convolution of the weight functions of $X,Y$. Note that $|X+Y|=|X|\cdot|Y|$.
The difference set $X-Y$ is defined analogously.

######  Definition 3.2 (Indicator function).

We use $\mathbf{1}(E)$ to denote the indicator function of an event $E$. For
instance, $\mathbf{1}(a+b=c)$ is the function (of $a,b,c$) that equals $1$
when $a+b=c$ and equals $0$ when $a+b\neq c$. For a multiset $E$, we also
abbreviate $\mathbf{1}(x\in\operatorname{supp}(E))$ by $\mathbf{1}_{E}(x)$.

Let $X$ be a nonempty multiset. If $X$ is finite, 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
$\left\|f\right\|_{\infty}:=\sup\limits_{x\in X}|f(x)|\leq 1$.

We use the following standard asymptotic notation. If $f,g:X\to{\mathbb{C}}$,
with $g$ taking positive real values, we denote $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$. If the constant $C$ depends on a parameter, we record this
dependence with a subscript. Lastly, we write $f\asymp g$ if $f\ll g$ and
$f\gg g$.

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

###  3.2. Van der Corput Inequalities

If $G$ is a finitely generated abelian group and $E\subseteq G$ is a finite
and nonempty multiset, we define the Fejér kernel

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

and also $\mu_{E}(h_{1},\ldots,h_{r})=\mu_{E}(h_{1})\cdots\mu_{E}(h_{r})$.
Summing over $h$, we easily observe that $\sum_{h}\mu_{E}(h)=1$. Moreover, if
there is some $C>0$ such that every element of $E$ has multiplicity at most
$C\frac{|E|}{|\operatorname{supp}(E)|}$, then we also have the pointwise bound
$0\leq\mu_{E}(h)\leq\mathbf{1}_{E-E}(h)\cdot\frac{C}{|\operatorname{supp}(E)|}$.777The
lower bound is obvious; for the upper bound, write
$\displaystyle\mu_{E}(h)=\mathbf{1}_{E-E}(h)\cdot\frac{1}{|E|^{2}}\sum_{h_{1}\in
E}\sum_{h_{2}\in E}\mathbf{1}(h_{2}=h_{1}+h),$ and notice that the sum over
$h_{2}$ is bounded by the maximum multiplicity of an element of $E$. When
$E=[\pm H]$, we use the shorthand notation

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

This definition differs slightly from those in [23, 24, 25, 28] 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 record several versions of the standard van der Corput inequality. The
proof of the following basic version is standard (see, e.g., [28, Lemma 3.2]).

######  Lemma 3.3 (van der Corput inequality, version 1).

Let $f:{\mathbb{Z}}\to{\mathbb{C}}$ be $1$-bounded, and let
$H,K\in{\mathbb{N}}$. Then:

  1. (i)

(Symmetric van der Corput inequality)

$\displaystyle\mathopen{}\left|\operatorname*{\mathbb{E}}_{z\in[K]}f(z)\mathclose{}\right|^{2}\leq\frac{K+2H}{K}\operatorname*{\mathbb{E}}_{h,h^{\prime}\in[\pm
H]}\frac{1}{K}\sum_{z\in([K]-h)\cap([K]-h^{\prime})}f(z+h)\overline{f(z+h^{\prime})}.$

  2. (ii)

(Asymmetric van der Corput inequality)

$\displaystyle\mathopen{}\left|\operatorname*{\mathbb{E}}_{z\in[K]}f(z)\mathclose{}\right|^{2}\leq\frac{K+2H}{K}\sum_{h}\mu_{H}(h)\frac{1}{K}\sum_{z\in[K]\cap([K]-h)}f(z)\overline{f(z+h)}.$

Of course, it does not make sense to take $H\geq K$ since $[K]\cap([K]-h)$ is
empty whenever $|h|\geq K$.

In applications, we will use the following corollary of Lemma 3.3.

######  Lemma 3.4 (van der Corput inequality, version 2).

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

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

then

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

and

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

###### Proof.

We prove only the second inequality since the proof of the first is almost
identical. Since $K-|[K]\cap([K]-h)|\leq|h|\leq H\leq\frac{\delta^{2}}{4}K$,
we have

$\displaystyle\mathopen{}\left|\sum_{h}\mu_{H}(h)\sum_{z\in[K]}f(z)\overline{f(z+h)}-\sum_{h}\mu_{H}(h)\sum_{z\in[K]\cap([K]-h)}f(z)\overline{f(z+h)}\mathclose{}\right|\leq\frac{\delta^{2}}{4}K.$

It then follows Lemma 3.3 and the assumption (16) that

$\displaystyle{\sum_{h}\mu_{H}(h)\operatorname*{\mathbb{E}}_{z\in[K]}f(z)\overline{f(z+h)}}\geq\frac{K}{K+2H}\mathopen{}\left|\operatorname*{\mathbb{E}}_{z\in[K]}f(z)\mathclose{}\right|^{2}-\frac{\delta^{2}}{4}\geq\frac{\delta^{2}}{4},$

as desired. ∎

###  3.3. Box norms

In this section, we summarize the theory of box norms on an arbitrary finitely
generated abelian group $G$; throughout, we write $\sum_{x}:=\sum_{x\in G}$.
Given $h,h^{\prime}\in G$ and a finitely supported function
$f:G\to{\mathbb{C}}$, we define the (multiplicative) discrete derivatives
$\Delta_{h}f(x):=f(x)\overline{f(x+h)}$ and
$\Delta^{\prime}_{(h,h^{\prime})}f(x):=f(x+h)\overline{f(x+h^{\prime})}$.
Similarly, compositions of such discrete derivatives are given by

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

where again ${\mathcal{C}}z=\overline{z}$ for $z\in{\mathbb{C}}$. We will
later also use the notation

$\displaystyle\Delta^{\prime}_{\alpha_{1},\ldots,\alpha_{s};({\underline{h}},{\underline{h}}^{\prime})}:=\Delta^{\prime}_{(\alpha_{1}h_{1},\alpha_{1}h_{1}^{\prime}),\ldots,(\alpha_{s}h_{s},\alpha_{s}h_{s}^{\prime})}$

for ${\underline{h}},{\underline{h}}^{\prime}\in G^{s}$. For finite multisets
$E_{1},\ldots,E_{s}\subseteq G$, 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}}_{h_{1},h_{1}^{\prime}\in
E_{1}}\cdots\operatorname*{\mathbb{E}}_{h_{s},h_{s}^{\prime}\in
E_{s}}\sum_{x}\Delta^{\prime}_{(h_{1},h_{1}^{\prime}),\ldots,(h_{s},h_{s}^{\prime})}f(x)\mathclose{}\right)^{1/2^{s}}.$

We can equivalently express this as

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

after shifting $x\mapsto x-h^{\prime}_{1}-\cdots-h_{s}^{\prime}$ and removing
the extraneous averages over $h^{\prime}_{1},\ldots,h^{\prime}_{s}$. If a
multiset $E$ repeats $s$ times, we often write $E^{s}$ instead of listing it
$s$ times, and we also write
$\left\|f\right\|_{U^{s}(E)}=\left\|f\right\|_{E^{s}}$, calling it the
degree-$s$ Gowers norm of $f$ along $E$.

For functions $f_{\underline{\epsilon}}$ indexed by
${\underline{\epsilon}}\in\\{0,1\\}^{s}$, we also define the
Gowers–Cauchy–Schwarz inner product (or box inner product) along
$E_{1},\ldots,E_{s}$ to be

$\displaystyle\langle(f_{\underline{\epsilon}})_{{\underline{\epsilon}}\in\\{0,1\\}^{s}}\rangle_{E_{1},\ldots,E_{s}}$
$\displaystyle:=\operatorname*{\mathbb{E}}_{h_{1},h_{1}^{\prime}\in
E_{1}}\cdots\operatorname*{\mathbb{E}}_{h_{s},h_{s}^{\prime}\in
E_{s}}\sum_{x}\prod_{{\underline{\epsilon}}\in\\{0,1\\}^{s}}{\mathcal{C}}^{|{\underline{\epsilon}}|}f_{\underline{\epsilon}}(x+(\underline{1}-{\underline{\epsilon}})\cdot{\underline{h}}+{\underline{\epsilon}}\cdot{\underline{h}}^{\prime})$
$\displaystyle=\sum_{x,h_{1},\ldots,h_{s}}\mu_{E_{1}}(h_{1})\cdots\mu_{E_{s}}(h_{s})\prod_{{\underline{\epsilon}}\in\\{0,1\\}^{s}}{\mathcal{C}}^{|{\underline{\epsilon}}|}f_{\underline{\epsilon}}(x+{\underline{\epsilon}}\cdot{\underline{h}}).$

The classical Gowers–Cauchy–Schwarz inequality888Even though this result is
usually stated only for sets, exactly the same proof works for multisets. then
states that

$\displaystyle\langle(f_{\underline{\epsilon}})_{{\underline{\epsilon}}\in\\{0,1\\}^{s}}\rangle_{E_{1},\ldots,E_{s}}\leq\prod_{{\underline{\epsilon}}\in\\{0,1\\}^{s}}\left\|f_{\underline{\epsilon}}\right\|_{E_{1},\ldots,E_{s}}.$

Box norms satisfy a number of well known properties, listed in the following
lemma.

######  Lemma 3.5 (Properties of box norms).

Let $\delta>0$, let $d,s\in{\mathbb{N}}$, let $G$ be a finitely generated
abelian group, and let $E_{1},\ldots,E_{s}\subseteq G$ be finite and nonempty
multisets. Let $f:G\to{\mathbb{C}}$ be 1-bounded and supported on a finite
nonempty set $B$. Then the following properties hold:

  1. (i)

(Inductive formula) For any $k\in[s]$, we have

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

  2. (ii)

(Permutation invariance) For any permutation $\sigma:[s]\to[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 $|\operatorname{supp}(B-E_{s})|\leq C|B|$ for some $C>0$,
then

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

  4. (iv)

(Enlarging the sets) If $s\geq 2$ and $E^{\prime}_{i}\subseteq G$ is a finite
multiset satisfying $E^{\prime}_{i}\geq 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 dimensions of boxes)999Although in this and the next property we
have taken a single parameter $d$, setting some $H_{ij}$’s to be $0$ lets us
apply these results to the case where different boxes $E_{i}$ have different
dimensions. Let $d^{\prime}_{i}\in[d_{i}]$ for $i\in[s]$, and let

$\displaystyle E_{i}=\sum_{j\in[d_{i}]}\beta_{ij}\cdot[\pm
H_{ij}]\quad\textrm{and}\quad
E_{i}^{\prime}=\sum_{j\in[d^{\prime}_{i}]}\beta_{ij}\cdot[\pm H_{ij}]$

for some $\beta_{ij}\in G$ and $H_{ij}\in{\mathbb{N}}_{0}$. Then

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

  6. (vi)

(Trimming the lengths of boxes) Let

$\displaystyle E_{i}=\sum_{j\in[d]}\beta_{ij}\cdot[\pm
H_{ij}]\quad\textrm{and}\quad
E_{i}^{\prime}=\sum_{j\in[d]}\beta_{ij}\cdot[\pm\kappa_{ij}H_{ij}]$

for some $\beta_{ij}\in G$, $\kappa_{ij}>0$, and $H_{ij}\in{\mathbb{N}}_{0}$.
Then

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

for $\kappa=\max_{i,j}\kappa_{ij}.$

  7. (vii)

(Passing to sub-arithmetic progressions) Suppose that

$\displaystyle E_{i}=\sum_{j\in[d]}\beta_{ij}\cdot[\pm
H_{ij}]\quad\textrm{and}\quad
E_{i}^{\prime}=\sum_{j\in[d]}q_{ij}\beta_{ij}\cdot[\pm H_{ij}/q_{ij}]$

for some $\beta_{ij}\in G$ and $q_{ij},H_{ij}\in{\mathbb{N}}$ satisfying
$q_{ij}\ll_{d,s}\delta^{2^{s}}H_{ij}$ for all $i,j$. Then

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

In applications, we will take $G={\mathbb{Z}}^{D}$, $B=[N]^{D}$, and
$E_{i},E^{\prime}_{i}$ will be generalized arithmetic progressions of bounded
dimension (interpreted appropriately as multisets).

###### Proof.

The first two properties are standard, and we omit the proofs. For the third
property, we expand the definition of
$\left\|f\right\|_{E_{1},\ldots,E_{s-1}}$ and introduce an extra averaging
over $E_{s}$ to obtain

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

The term $f(x+h_{1}+\cdots+h_{s})$ in
$\Delta^{\prime}_{(h_{1},h_{1}^{\prime}),\ldots,(h_{s-1},h_{s-1}^{\prime})}f(x+h_{s})$
vanishes unless $x+h_{1}+\cdots+h_{s-1}\in B-E_{s}$, so we can introduce the
indicator function $\mathbf{1}_{B-E_{s}}(x+h_{1}+\cdots+h_{s-1})$ into the
expression above without altering its value. Applying the Cauchy–Schwarz
inequality then gives

$\displaystyle\delta^{2}|B|^{2}\leq\left\|f\right\|_{E_{1},\ldots,E_{s-1}}^{2^{s}}$
$\displaystyle\leq\operatorname*{\mathbb{E}}_{h_{1},h_{1}^{\prime}\in
E_{1}}\cdots\operatorname*{\mathbb{E}}_{h_{s-1},h_{s-1}^{\prime}\in
E_{s-1}}\sum_{x}\mathbf{1}_{B-E_{s}}(x+h_{1}+\cdots+h_{s-1})$
$\displaystyle\qquad\times\operatorname*{\mathbb{E}}_{h_{1},h_{1}^{\prime}\in
E_{1}}\cdots\operatorname*{\mathbb{E}}_{h_{s},h_{s}^{\prime}\in
E_{s}}\sum_{x}\Delta^{\prime}_{(h_{1},h_{1}^{\prime}),\ldots,(h_{s},h_{s}^{\prime})}f(x)$
$\displaystyle\leq C|B|\cdot\left\|f\right\|_{E_{1},\ldots,E_{s}}^{2^{s}},$

and the claim follows.

For the fourth property, we write

$\displaystyle\left\|f\right\|_{E_{1},\ldots,E_{s}}^{2^{s}}=\operatorname*{\mathbb{E}}_{h_{1},h_{1}^{\prime}\in
E_{1}}\cdots\operatorname*{\mathbb{E}}_{h_{s-1},h_{s-1}^{\prime}\in
E_{s-1}}\sum_{x}\mathopen{}\left|\operatorname*{\mathbb{E}}_{h_{s}\in
E_{s}}\Delta^{\prime}_{(h_{1},h_{1}^{\prime}),\ldots,(h_{s-1},h_{s-1}^{\prime})}f(x+h_{s})\mathclose{}\right|^{2}.$

Using the assumption $s\geq 2$ and nonnegativity, we can extend the averages
over $E_{1},\ldots,E_{s-1}$ to $E_{1}^{\prime},\ldots,E_{s-1}^{\prime}$ and
upper-bound the previous expression by

$\displaystyle\mathopen{}\left(\frac{|E_{1}^{\prime}|\cdots|E_{s-1}^{\prime}|}{|E_{1}|\cdots|E_{s-1}|}\mathclose{}\right)^{2}\cdot\operatorname*{\mathbb{E}}_{h_{1},h_{1}^{\prime}\in
E_{1}^{\prime}}\cdots\operatorname*{\mathbb{E}}_{h_{s-1},h_{s-1}^{\prime}\in
E_{s-1}^{\prime}}\sum_{x}\mathopen{}\left|\operatorname*{\mathbb{E}}_{h_{s}\in
E_{s}}\Delta^{\prime}_{(h_{1},h_{1}^{\prime}),\ldots,(h_{s-1},h_{s-1}^{\prime})}f(x+h_{s})\mathclose{}\right|^{2}.$

We can replace average over $E_{s}$ with an average over $E_{s}^{\prime}$
using the same maneuver.

To prove the fifth property, we start with the case $s=1$. Dropping the index
$i$, we can write

$\displaystyle\left\|f\right\|_{E}^{2}=\sum_{x}\operatorname*{\mathbb{E}}_{\begin{subarray}{c}h^{\prime}_{j}\in[\pm
H_{j}]:\\\
{j\in[d]}\end{subarray}}f\mathopen{}\left(x+\sum_{j\in[d]}\beta_{j}h_{j}^{\prime}\mathclose{}\right)\operatorname*{\mathbb{E}}_{\begin{subarray}{c}h_{j}\in[\pm
H_{j}]:\\\
{j\in[d]}\end{subarray}}\overline{f\mathopen{}\left(x+\sum_{j\in[d]}\beta_{j}h_{j}\mathclose{}\right)}.$

Using the Cauchy–Schwarz inequality to double the variables
$(h_{j})_{j\in[d^{\prime}]}$, we bound

$\left\|f\right\|_{E}^{4}\leq|B|\cdot\operatorname*{\mathbb{E}}_{\begin{subarray}{c}h_{j}\in[\pm
H_{j}]:\\\
{j\in[d^{\prime}+1,d]}\end{subarray}}\sum_{x}\operatorname*{\mathbb{E}}_{\begin{subarray}{c}h_{j},h^{\prime}_{j}\in[\pm
H_{j}]:\\\
{j\in[d^{\prime}]}\end{subarray}}f\mathopen{}\left(x+\sum_{j\in[d^{\prime}+1,d]}\beta_{j}h_{j}+\sum_{j\in[d^{\prime}]}\beta_{j}h_{j}\mathclose{}\right)\\\
\overline{f\mathopen{}\left(x+\sum_{j\in[d^{\prime}+1,d]}\beta_{j}h_{j}+\sum_{j\in[d^{\prime}]}\beta_{j}h_{j}^{\prime}\mathclose{}\right)}.$

Shifting $x\mapsto x-\sum\limits_{j\in[d^{\prime}+1,d]}\beta_{j}h_{j}$, we can
ignore the contribution of $j\in[d^{\prime}+1,d]$ altogether, and we obtain

$\displaystyle\left\|f\right\|_{E}^{4}$
$\displaystyle\leq|B|\cdot\sum_{x}\operatorname*{\mathbb{E}}_{\begin{subarray}{c}h_{j},h^{\prime}_{j}\in[\pm
H_{j}]:\\\
{j\in[d^{\prime}]}\end{subarray}}f\mathopen{}\left(x+\sum_{j\in[d^{\prime}]}\beta_{j}h_{j}\mathclose{}\right)\overline{f\mathopen{}\left(x+\sum_{j\in[d^{\prime}]}\beta_{j}h_{j}^{\prime}\mathclose{}\right)}=|B|\cdot\left\|f\right\|_{E^{\prime}}^{2}.$

We now consider the case $s>1$. The induction formula for box norms, the
Cauchy–Schwarz inequality, and the $s=1$ case give

$\displaystyle\left\|f\right\|_{E_{1},\ldots,E_{s}}^{2^{s+1}}$
$\displaystyle\leq\operatorname*{\mathbb{E}}_{h_{1},h_{1}^{\prime}\in
E_{1}}\cdots\operatorname*{\mathbb{E}}_{h_{s-1},h_{s-1}^{\prime}\in
E_{s-1}}\left\|\Delta^{\prime}_{(h_{1},h_{1}^{\prime}),\ldots,(h_{s-1},h_{s-1}^{\prime})}f\right\|_{E_{s}}^{4}$
$\displaystyle\leq|B|\cdot\operatorname*{\mathbb{E}}_{h_{1},h_{1}^{\prime}\in
E_{1}}\cdots\operatorname*{\mathbb{E}}_{h_{s-1},h_{s-1}^{\prime}\in
E_{s-1}}\left\|\Delta^{\prime}_{(h_{1},h_{1}^{\prime}),\ldots,(h_{s-1},h_{s-1}^{\prime})}f\right\|_{E^{\prime}_{s}}^{2}$
$\displaystyle=|B|\cdot\left\|f\right\|_{E_{1},\ldots,E_{s-1},E^{\prime}_{s}}^{2^{s}}.$

Performing the same procedure with $E_{s-1}$ in place of $E_{s}$ gives

$\displaystyle\left\|f\right\|_{E_{1},\ldots,E_{s}}^{2^{s+2}}\leq|B|^{2}\cdot\left\|f\right\|_{E_{1},\ldots,E_{s-1},E^{\prime}_{s}}^{2^{s+1}}\leq|B|^{3}\cdot\left\|f\right\|_{E_{1},\ldots,E_{s-2},E^{\prime}_{s-1},E^{\prime}_{s}}^{2^{s}},$

and continuing in this manner gives

$\displaystyle\left\|f\right\|_{E_{1},\ldots,E_{s}}^{4^{s}}\leq|B|^{2^{s}-1}\cdot\left\|f\right\|_{E^{\prime}_{1},\ldots,E^{\prime}_{s}}^{2^{s}},$

from which the result promptly follows.

To prove the sixth property, we first set

$\displaystyle
E^{\prime\prime}_{i}=\sum_{j\in[d]}\beta_{ij}\cdot[\pm\varepsilon_{ij}H_{ij}]$

for parameters $\varepsilon_{ij}>0$ to be chosen later. As in the proof of the
fifth property, we begin with the $s=1$ case and drop the index $i$. Note that
for every $\varepsilon>0$ and $1$-bounded function
$g:{\mathbb{Z}}\to{\mathbb{C}}$, we have

(19) $\displaystyle\mathopen{}\left|\operatorname*{\mathbb{E}}_{h\in[\pm
H]}g(h)-\operatorname*{\mathbb{E}}_{h\in[\pm
H]}\operatorname*{\mathbb{E}}_{h^{\prime}\in[\pm\varepsilon
H]}g(h+h^{\prime})\mathclose{}\right|\leq 2\varepsilon.$

Hence we can approximate

$\displaystyle\left\|f\right\|_{E}^{2}$
$\displaystyle=\sum_{x}\operatorname*{\mathbb{E}}_{\begin{subarray}{c}h_{j},h^{\prime}_{j}\in[\pm
H_{j}]:\\\
{j\in[d]}\end{subarray}}f\mathopen{}\left(x+\sum_{j\in[d]}\beta_{j}h_{j}^{\prime}\mathclose{}\right)\overline{f\mathopen{}\left(x+\sum_{j\in[d]}\beta_{j}h_{j}\mathclose{}\right)}$
$\displaystyle=\sum_{x}\operatorname*{\mathbb{E}}_{\begin{subarray}{c}h_{j},h^{\prime}_{j}\in[\pm
H_{j}]:\\\
{j\in[d]}\end{subarray}}f\mathopen{}\left(x+\sum_{j\in[d]}\beta_{j}h_{j}^{\prime}\mathclose{}\right)\operatorname*{\mathbb{E}}_{\begin{subarray}{c}h^{\prime\prime}_{j}\in[\pm\varepsilon_{j}H_{j}]:\\\
{j\in[d]}\end{subarray}}\overline{f\mathopen{}\left(x+\sum_{j\in[d]}\beta_{j}(h_{j}+h^{\prime\prime}_{j})\mathclose{}\right)}+O_{d}(\varepsilon|B|),$

where $\varepsilon:=\max_{j}\varepsilon_{j}$. By the Cauchy–Schwarz inequality
in all variables except $h^{\prime\prime}_{j}$, we get

$\left\|f\right\|_{E}^{4}\leq|B|\cdot\sum_{x}\operatorname*{\mathbb{E}}_{\begin{subarray}{c}h_{j}\in[\pm
H_{j}],\\\
h^{\prime}_{j},h^{\prime\prime}_{j}\in[\pm\varepsilon_{j}H_{j}]:\;{j\in[d]}\end{subarray}}f\mathopen{}\left(x+\sum_{j\in[d]}\beta_{j}(h_{j}+h^{\prime}_{j})\mathclose{}\right)\\\
\overline{f\mathopen{}\left(x+\sum_{j\in[d]}\beta_{j}(h_{j}+h^{\prime\prime}_{j})\mathclose{}\right)}+O_{d}(\varepsilon|B|^{2}).$

Shifting the variable $x\mapsto x-\sum_{j\in[d]}\beta_{j}h_{j}$ gives

$\displaystyle\left\|f\right\|_{E}^{4}$
$\displaystyle\leq|B|\cdot\sum_{x}\operatorname*{\mathbb{E}}_{\begin{subarray}{c}h^{\prime}_{j},h^{\prime\prime}_{j}\in[\pm\varepsilon_{j}H_{j}]:\\\
{j\in[d]}\end{subarray}}f\mathopen{}\left(x+\sum_{j\in[d]}\beta_{j}h^{\prime}_{j}\mathclose{}\right)\overline{f\mathopen{}\left(x+\sum_{j\in[d]}\beta_{j}h^{\prime\prime}_{j}\mathclose{}\right)}+O_{d}(\varepsilon|B|^{2})$
$\displaystyle=|B|\cdot\left\|f\right\|_{E^{\prime\prime}}^{2}+O_{d}(\varepsilon|B|^{2}).$

Iterating this argument for higher-degree norms as in the proof of (v) gives

$\displaystyle\left\|f\right\|_{E_{1},\ldots,E_{s}}^{4^{s}}\leq|B|^{2^{s}-1}\cdot\left\|f\right\|_{E_{1}^{\prime\prime},\ldots,E_{s}^{\prime\prime}}^{2^{s}}+O_{d,s}(\varepsilon|B|^{2^{s}}),$

where $\varepsilon:=\max_{i,j}\varepsilon_{ij}$, so

$\displaystyle\left\|f\right\|_{E_{1},\ldots,E_{s}}^{2^{s}}\geq\delta|B|\quad\Longrightarrow\quad\left\|f\right\|_{E_{1}^{\prime\prime},\ldots,E_{s}^{\prime\prime}}^{2^{s}}\geq(\delta^{2^{s}}-C_{d,s}\varepsilon)|B|$

for some constant $C_{d,s}>0$. If the $\kappa_{ij}$’s are sufficiently small,
namely, if $\kappa:=\max_{i,j}\kappa_{ij}\leq\delta^{2^{s}}/(2C_{d,s})$, then
we apply the above bound directly with $\varepsilon_{ij}=\kappa_{ij}$.
Otherwise, we first decrease the lengths of boxes, setting
$\varepsilon_{ij}=\min(\delta^{2^{s}}/(2C_{d,s}),\kappa_{ij})$ for all $i,j$,
and then use (iv) to enlarge the boxes from $E^{\prime\prime}_{i}$ to
$E^{\prime}_{i}$, which gives

$\displaystyle\left\|f\right\|_{E_{1}^{\prime},\ldots,E_{s}^{\prime}}^{2^{s}}\geq\mathopen{}\left(\prod_{\begin{subarray}{c}i\in[s],\;j\in[d]\end{subarray}}\frac{\varepsilon_{ij}^{2}}{\kappa_{ij}^{2}}\mathclose{}\right)\left\|f\right\|_{E_{1}^{\prime\prime},\ldots,E_{s}^{\prime\prime}}^{2^{s}}$
$\displaystyle\gg_{d,s}\delta^{2^{s}}\cdot(\delta^{2^{s}}/\kappa)^{2ds}|B|.$

Combining these two cases yields the desired bound.

For the last property, we first observe that for positive integers $H,q,u$,
the sets $[\pm H]$ and $\bigcup\limits_{u=0}^{q-1}(u+q\cdot[\pm H/q])$ differ
in at most $2q$ “boundary” elements. Hence, if $(x_{i})_{i\in\mathbb{Z}}$ is a
$1$-bounded sequence of complex numbers, then

$\mathopen{}\left|\operatorname*{\mathbb{E}}_{h\in[\pm
H]}x_{h}-\operatorname*{\mathbb{E}}_{u\in[0,q-1]}\operatorname*{\mathbb{E}}_{h\in[\pm
H/q]}x_{qh+u}\mathclose{}\right|\\\
\leq\frac{2q}{2H+1}+\mathopen{}\left|\frac{1}{2H+1}-\frac{1}{(2\left\lfloor
H/q\right\rfloor+1)q}\mathclose{}\right|(2\left\lfloor
H/q\right\rfloor+1)q\leq\frac{3q+1}{2H+1}.$

For the proof proper of the last property, we start with the case $s=1$.
Approximating each box $\beta_{ij}\cdot[\pm H_{ij}]$ by the union of boxes
$\beta_{ij}\cdot(u_{j}+q_{j}\cdot[\pm H_{j}/q_{j}])$ indexed by
$u_{j}\in[0,q_{j}-1]$ and applying the estimate above, we get

$\displaystyle\left\|f\right\|_{E}^{2}$
$\displaystyle=\operatorname*{\mathbb{E}}_{\begin{subarray}{c}u_{j},u_{j}^{\prime}\in[0,q_{j}-1]:\\\
j\in[d]\end{subarray}}\sum_{x}\operatorname*{\mathbb{E}}_{\begin{subarray}{c}h_{j},h^{\prime}_{j}\in[\pm
H_{j}/q_{j}]:\\\
{j\in[d]}\end{subarray}}f\mathopen{}\left(x+\sum_{j\in[d]}\beta_{j}(q_{j}h_{j}+u_{j})\mathclose{}\right)$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\overline{f\mathopen{}\left(x+\sum_{j\in[d]}\beta_{j}(q_{j}h_{j}^{\prime}+u_{j}^{\prime})\mathclose{}\right)}+O_{d}(\varepsilon|B|)$

for $\varepsilon:=\max_{j\in[d]}\frac{q_{j}}{H_{j}}$. We pigeonhole in
$u_{j},u_{j}^{\prime}$ and apply the Cauchy–Schwarz inequality to get

$\displaystyle\left\|f\right\|_{E}^{4}\leq\left\|f\Bigl{(}\cdot+\sum_{j\in[d]}\beta_{j}u_{j}\Bigr{)}\right\|_{E^{\prime}}^{2}\cdot\left\|f\Bigl{(}\cdot+\sum_{j\in[d]}\beta_{j}u_{j}^{\prime}\Bigr{)}\right\|_{E^{\prime}}^{2}+O_{d}(\varepsilon|B|^{2}).$

The translation-invariance of box norms then gives
$\left\|{f}\right\|_{E^{\prime}}^{2}\geq(\delta-
O_{d}(\sqrt{\varepsilon}))|B|$. The statement for general $s$ follows
inductively, using the inductive formula for box norms. ∎

##  4\. PET induction scheme

In this section, we begin the study of the counting operators

(20)
$\displaystyle\sum_{{\textbf{x}}\in{\mathbb{Z}}^{D}}\operatorname*{\mathbb{E}}_{z\in[K]}f_{0}({\textbf{x}})\cdot
f_{1}({\textbf{x}}+{\textbf{P}}_{1}(z))\cdots
f_{\ell}({\textbf{x}}+{\textbf{P}}_{\ell}(z))$

associated with families
${\mathcal{P}}=({\textbf{P}}_{1},\ldots,{\textbf{P}}_{\ell})$ of essentially
distinct polynomials in ${\mathbb{Z}}^{D}[z]$ (where “essentially distinct”
means that all polynomials and their pairwise differences are nonconstant).
For instance, in this notation the configuration

$\displaystyle(x_{1},x_{2}),\;(x_{1}+z^{2}+z,x_{2}),\;(x_{1},x_{2}+z^{2}+z)$

can be rewritten as
${\textbf{x}},{\textbf{x}}+{\mathbf{e}}_{1}(z^{2}+z),{\textbf{x}}+{\mathbf{e}}_{2}(z^{2}+z)$
and corresponds to the family
${\mathcal{P}}=\\{{\mathbf{e}}_{1}(z^{2}+z),{\mathbf{e}}_{2}(z^{2}+z)\\}$.

We present here the standard PET induction scheme which allows us to bound the
counting operator (20) by an average of box norms. These box norms can be seen
as “local” in the sense that the differencing parameters lie in intervals of
length $\asymp N^{1/d}$, where $d=\max_{j}\deg{\textbf{P}}_{j}$. This is the
first step in showing that multidimensional polynomial progressions are
controlled by a single “global” box norm. Combining arguments from [5, 35], we
obtain a precise description of the directions of the box norms; in
particular, we show that they come from the coefficients of the polynomials
${\textbf{P}}_{j}$ and their differences. We start with a simple example in
Section 4.1 that will motivate the argument in the general case. In Section
4.2, we set up the formalism that we need for this purpose and derive various
properties of the polynomial families that appear in the PET induction scheme.
We then assemble bits and pieces from Section 4.2 in order to prove
Proposition 4.8, the main result of this section.

The material in this subsection is not novel, and various parts of it can be
found in previous works on the subject (in [5, 23, 28, 35], _inter alia_).

###  4.1. Example of PET

Consider the counting operator

$\displaystyle\Lambda(f_{0},f_{1},f_{2}):=\sum_{{\textbf{x}}\in{\mathbb{Z}}^{2}}\operatorname*{\mathbb{E}}_{z\in[K]}f_{0}({\textbf{x}})f_{1}({\textbf{x}}+{\boldsymbol{\beta}}_{12}z^{2}+{\boldsymbol{\beta}}_{11}z)f_{2}({\textbf{x}}+{\boldsymbol{\beta}}_{22}z^{2}+{\boldsymbol{\beta}}_{21}z),$

and suppose that

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

for some $1$-bounded functions
$f_{0},f_{1},f_{2}:{\mathbb{Z}}^{2}\to{\mathbb{C}}$ supported on $[N]^{2}$. To
avoid degenerate cases, we assume that
${\boldsymbol{\beta}}_{12},{\boldsymbol{\beta}}_{12}-{\boldsymbol{\beta}}_{22}\neq\textbf{0}$,
and that
$({\boldsymbol{\beta}}_{22},{\boldsymbol{\beta}}_{21})\neq(\textbf{0},\textbf{0})$.

Our goal in this section is to work out the PET argument for this specific
example before delving into it more abstractly. The goal of the PET argument
is to pass from the counting operator for a polynomial progression to an
average of box norms of one of the functions in the configuration (say,
$f_{1}$). This is achieved in a finite number of steps, in each of which we
apply the Cauchy–Schwarz inequality (to remove terms that do not depend on
$z$), the van der Corput inequality (to double the variable $z$) and a change
of variables (to bring the progression into a form where some functions are
independent of $z$). That this procedure ends in finite time follows from the
fact that at each step, we reduce the (appropriately measured) complexity, or
type, of the polynomial progression.

For this particular example, we will need three applications of the
aforementioned procedure to reduce the progression to an average of box norms
of $f_{1}$.

Step 1

We apply the Cauchy–Schwarz inequality in x; since $f_{0}$ is independent of
$z$ and has $L^{2}$-norm at most $N$, we can bound

$\displaystyle\sum_{{\textbf{x}}}\mathopen{}\left|\operatorname*{\mathbb{E}}_{z\in[K]}f_{1}({\textbf{x}}+{\boldsymbol{\beta}}_{12}z^{2}+{\boldsymbol{\beta}}_{11}z)f_{2}({\textbf{x}}+{\boldsymbol{\beta}}_{22}z^{2}+{\boldsymbol{\beta}}_{21}z)\mathclose{}\right|^{2}\geq\delta^{2}N^{2}.$

For the $\Omega(\delta^{2}N^{2})$ values of ${\textbf{x}}\in[N]^{2}$ for which
the absolute value above is at least $\delta^{2}N^{2}/2$, we then apply the
van der Corput inequality (Lemma 3.4) with $H\ll\delta^{8}K$; this has the
effect of doubling $z$ and gives

$\sum_{{\textbf{x}},h_{1}}\mu_{H}(h_{1})\operatorname*{\mathbb{E}}_{z\in[K]}f_{1}({\textbf{x}}+{\boldsymbol{\beta}}_{12}z^{2}+{\boldsymbol{\beta}}_{11}z)\overline{f_{1}({\textbf{x}}+{\boldsymbol{\beta}}_{12}(z+h_{1})^{2}+{\boldsymbol{\beta}}_{11}(z+h_{1}))}\\\
f_{2}({\textbf{x}}+{\boldsymbol{\beta}}_{22}z^{2}+{\boldsymbol{\beta}}_{21}z)\overline{f_{2}({\textbf{x}}+{\boldsymbol{\beta}}_{22}(z+h_{1})^{2}+{\boldsymbol{\beta}}_{21}(z+h_{1}))}\gg\delta^{2}N.$

We now want to bring the configuration into a form where one copy of $f_{2}$
has an argument independent of $z$; then this copy of $f_{2}$ can be removed
at the subsequent step of the argument. Shifting
${\textbf{x}}\mapsto{\textbf{x}}-{\boldsymbol{\beta}}_{22}z^{2}+{\boldsymbol{\beta}}_{21}z$,
we obtain

$\sum_{{\textbf{x}},h_{1}}\mu_{H}(h_{1})\operatorname*{\mathbb{E}}_{z\in[K]}f_{1}({\textbf{x}}+({\boldsymbol{\beta}}_{12}-{\boldsymbol{\beta}}_{22})z^{2}+({\boldsymbol{\beta}}_{11}-{\boldsymbol{\beta}}_{21})z)\\\
\overline{f_{1}({\textbf{x}}+({\boldsymbol{\beta}}_{12}-{\boldsymbol{\beta}}_{22})z^{2}+(2{\boldsymbol{\beta}}_{12}h_{1}+{\boldsymbol{\beta}}_{11}-{\boldsymbol{\beta}}_{21})z+{\boldsymbol{\beta}}_{12}h_{1}^{2}+{\boldsymbol{\beta}}_{11}h_{1})}\\\
f_{2}({\textbf{x}})\overline{f_{2}({\textbf{x}}+2{\boldsymbol{\beta}}_{22}h_{1}z+{\boldsymbol{\beta}}_{22}h_{1}^{2}+{\boldsymbol{\beta}}_{21}h_{1})}\gg\delta^{2}N^{2}.$

This new progression (or, rather, family of progressions indexed by $h_{1}$)
may not look simpler than the original one, but it is: Whereas the original
progression involved two quadratic101010in $z$ (the degree of a polynomial in
this section always refers to the degree in $z$) polynomials with distinct
leading coefficients ${\boldsymbol{\beta}}_{12},{\boldsymbol{\beta}}_{22}$,
the new progression involves two quadratic polynomials with the same leading
coefficient ${\boldsymbol{\beta}}_{12}-{\boldsymbol{\beta}}_{22}$ (which is
nonzero by assumption), as well as a linear polynomial. The decrease in the
number of quadratic polynomials with distinct leading coefficients is what
makes this progression “less complex” than the original one.

Step 2

Once again, we apply the Cauchy–Schwarz inequality in ${\textbf{x}},h_{1}$.
This time, this has the effect of removing one of the two instances of
$f_{2}$, giving

$\sum_{{\textbf{x}},h_{1}}\mu_{H}(h_{1})\left|\operatorname*{\mathbb{E}}_{z\in[K]}f_{1}({\textbf{x}}+({\boldsymbol{\beta}}_{12}-{\boldsymbol{\beta}}_{22})z^{2}+({\boldsymbol{\beta}}_{11}-{\boldsymbol{\beta}}_{21})z)\right.\\\
\overline{f_{1}({\textbf{x}}+({\boldsymbol{\beta}}_{12}-{\boldsymbol{\beta}}_{22})z^{2}+(2{\boldsymbol{\beta}}_{12}h_{1}+{\boldsymbol{\beta}}_{11}-{\boldsymbol{\beta}}_{21})z+{\boldsymbol{\beta}}_{12}h_{1}^{2}+{\boldsymbol{\beta}}_{11}h_{1})}\\\
\left.\overline{f_{2}({\textbf{x}}+2{\boldsymbol{\beta}}_{22}h_{1}z+{\boldsymbol{\beta}}_{22}h_{1}^{2}+{\boldsymbol{\beta}}_{21}h_{1})}\vphantom{\operatorname*{\mathbb{E}}_{z\in[K]}}\right|^{2}\gg\delta^{4}N^{2}.$

The van der Corput inequality (Lemma 3.4) then gives

$\sum_{{\textbf{x}},h_{1},h_{2}}\mu_{H}(h_{1},h_{2})\operatorname*{\mathbb{E}}_{z\in[K]}f_{1}({\textbf{x}}+({\boldsymbol{\beta}}_{12}-{\boldsymbol{\beta}}_{22})z^{2}+({\boldsymbol{\beta}}_{11}-{\boldsymbol{\beta}}_{21})z)\\\
\overline{f_{1}({\textbf{x}}+({\boldsymbol{\beta}}_{12}-{\boldsymbol{\beta}}_{22})(z+h_{2})^{2}+({\boldsymbol{\beta}}_{11}-{\boldsymbol{\beta}}_{21})(z+h_{2}))}\\\
\overline{f_{1}({\textbf{x}}+({\boldsymbol{\beta}}_{12}-{\boldsymbol{\beta}}_{22})z^{2}+(2{\boldsymbol{\beta}}_{12}h_{1}+{\boldsymbol{\beta}}_{11}-{\boldsymbol{\beta}}_{21})z+{\boldsymbol{\beta}}_{12}h_{1}^{2}+{\boldsymbol{\beta}}_{11}h_{1})}\\\
{f_{1}({\textbf{x}}+({\boldsymbol{\beta}}_{12}-{\boldsymbol{\beta}}_{22})(z+h_{2})^{2}+(2{\boldsymbol{\beta}}_{12}h_{1}+{\boldsymbol{\beta}}_{11}-{\boldsymbol{\beta}}_{21})(z+h_{2})+{\boldsymbol{\beta}}_{12}h_{1}^{2}+{\boldsymbol{\beta}}_{11}h_{1})}\\\
\overline{\Delta_{2{\boldsymbol{\beta}}_{22}h_{1}h_{2}}f_{2}({\textbf{x}}+2{\boldsymbol{\beta}}_{22}h_{1}z+{\boldsymbol{\beta}}_{22}h_{1}^{2}+{\boldsymbol{\beta}}_{21}h_{1})}\gg\delta^{4}N^{2}.$

We want to make the remaining instances of $f_{2}$ independent of $z$. To this
end we shift111111If ${\boldsymbol{\beta}}_{22}=\textbf{0}$, then this term
can be removed before applying the Cauchy–Schwarz inequality, and we can
proceed directly to the change of variables performed in Step 3 below.
${\textbf{x}}\mapsto{\textbf{x}}-2{\boldsymbol{\beta}}_{22}h_{1}z$, which
gives

$\sum_{{\textbf{x}},h_{1},h_{2}}\mu_{H}(h_{1},h_{2})\operatorname*{\mathbb{E}}_{z\in[K]}f_{1}({\textbf{x}}+({\boldsymbol{\beta}}_{12}-{\boldsymbol{\beta}}_{22})z^{2}+(-2{\boldsymbol{\beta}}_{22}h_{1}+{\boldsymbol{\beta}}_{11}-{\boldsymbol{\beta}}_{21})z)\\\
\overline{f_{1}({\textbf{x}}+({\boldsymbol{\beta}}_{12}-{\boldsymbol{\beta}}_{22})(z+h_{2})^{2}+(-2{\boldsymbol{\beta}}_{22}h_{1}+{\boldsymbol{\beta}}_{11}-{\boldsymbol{\beta}}_{21})z+{\textbf{a}}_{1}(h_{1},h_{2}))}\\\
\overline{f_{1}({\textbf{x}}+({\boldsymbol{\beta}}_{12}-{\boldsymbol{\beta}}_{22})z^{2}+(2({\boldsymbol{\beta}}_{12}-{\boldsymbol{\beta}}_{22})h_{1}+{\boldsymbol{\beta}}_{11}-{\boldsymbol{\beta}}_{21})z+{\textbf{a}}_{2}(h_{1},h_{2}))}\\\
{f_{1}({\textbf{x}}+({\boldsymbol{\beta}}_{12}-{\boldsymbol{\beta}}_{22})(z+h_{2})^{2}+(2({\boldsymbol{\beta}}_{12}-{\boldsymbol{\beta}}_{22})h_{1}+{\boldsymbol{\beta}}_{11}-{\boldsymbol{\beta}}_{21})z+{\textbf{a}}_{3}(h_{1},h_{2}))}\\\
\overline{\Delta_{2{\boldsymbol{\beta}}_{22}h_{1}h_{2}}f_{2}({\textbf{x}}+{\textbf{a}}_{4}(h_{1},h_{2}))}\gg\delta^{4}N^{2}$

for some polynomials ${\textbf{a}}_{j}$ in $h_{1},h_{2}$, the exact form of
which is irrelevant for us. Even though the configuration has increased in
length (this is an unfortunate aspect of the PET argument), it has become less
complex in the sense that all of the quadratic polynomials now have the same
leading coefficient, and there is no linear polynomial left (as contrasted
with the previous step, where we still had one polynomial linear in $z$). We
are ready for the last step, in which we will remove $f_{2}$ altogether.

Step 3

Proceeding as before, we apply the Cauchy–Schwarz inequality in
${\textbf{x}},h_{1},h_{2}$ to get

$\sum_{{\textbf{x}},h_{1},h_{2}}\mu_{H}(h_{1},h_{2})\left|\operatorname*{\mathbb{E}}_{z\in[K]}f_{1}({\textbf{x}}+({\boldsymbol{\beta}}_{12}-{\boldsymbol{\beta}}_{22})z^{2}+(-2{\boldsymbol{\beta}}_{22}h_{1}+{\boldsymbol{\beta}}_{11}-{\boldsymbol{\beta}}_{21})z)\right.\\\
\overline{f_{1}({\textbf{x}}+({\boldsymbol{\beta}}_{12}-{\boldsymbol{\beta}}_{22})(z+h_{2})^{2}+(-2{\boldsymbol{\beta}}_{22}h_{1}+{\boldsymbol{\beta}}_{11}-{\boldsymbol{\beta}}_{21})z+{\textbf{a}}_{1}(h_{1},h_{2}))}\\\
\overline{f_{1}({\textbf{x}}+({\boldsymbol{\beta}}_{12}-{\boldsymbol{\beta}}_{22})z^{2}+(2({\boldsymbol{\beta}}_{12}-{\boldsymbol{\beta}}_{22})h_{1}+{\boldsymbol{\beta}}_{11}-{\boldsymbol{\beta}}_{21})z+{\textbf{a}}_{2}(h_{1},h_{2}))}\\\
\left.\vphantom{\operatorname*{\mathbb{E}}_{z\in[K]}}{f_{1}({\textbf{x}}+({\boldsymbol{\beta}}_{12}-{\boldsymbol{\beta}}_{22})(z+h_{2})^{2}+(2({\boldsymbol{\beta}}_{12}-{\boldsymbol{\beta}}_{22})h_{1}+{\boldsymbol{\beta}}_{11}-{\boldsymbol{\beta}}_{21})z+{\textbf{a}}_{3}(h_{1},h_{2}))}\right|^{2}\gg\delta^{8}N^{2}.$

An application of Lemma 3.4 then gives

$\sum_{{\textbf{x}},h_{1},h_{2},h_{3}}\mu_{H}(h_{1},h_{2},h_{3})\operatorname*{\mathbb{E}}_{z\in[K]}f_{1}({\textbf{x}}+({\boldsymbol{\beta}}_{12}-{\boldsymbol{\beta}}_{22})z^{2}+(-2{\boldsymbol{\beta}}_{22}h_{1}+{\boldsymbol{\beta}}_{11}-{\boldsymbol{\beta}}_{21})z)\\\
\overline{f_{1}({\textbf{x}}+({\boldsymbol{\beta}}_{12}-{\boldsymbol{\beta}}_{22})(z+h_{3})^{2}+(-2{\boldsymbol{\beta}}_{22}h_{1}+{\boldsymbol{\beta}}_{11}-{\boldsymbol{\beta}}_{21})(z+h_{3}))}\\\
\overline{f_{1}({\textbf{x}}+({\boldsymbol{\beta}}_{12}-{\boldsymbol{\beta}}_{22})(z+h_{2})^{2}+(-2{\boldsymbol{\beta}}_{22}h_{1}+{\boldsymbol{\beta}}_{11}-{\boldsymbol{\beta}}_{21})z+{\textbf{a}}_{1}(h_{1},h_{2}))}\\\
{f_{1}({\textbf{x}}+({\boldsymbol{\beta}}_{12}-{\boldsymbol{\beta}}_{22})(z+h_{2}+h_{3})^{2}+(-2{\boldsymbol{\beta}}_{22}h_{1}+{\boldsymbol{\beta}}_{11}-{\boldsymbol{\beta}}_{21})(z+h_{3})+{\textbf{a}}_{1}(h_{1},h_{2}))}\\\
\overline{f_{1}({\textbf{x}}+({\boldsymbol{\beta}}_{12}-{\boldsymbol{\beta}}_{22})z^{2}+(2({\boldsymbol{\beta}}_{12}-{\boldsymbol{\beta}}_{22})h_{1}+{\boldsymbol{\beta}}_{11}-{\boldsymbol{\beta}}_{21})z+{\textbf{a}}_{2}(h_{1},h_{2}))}\\\
{f_{1}({\textbf{x}}+({\boldsymbol{\beta}}_{12}-{\boldsymbol{\beta}}_{22})(z+h_{3})^{2}+(2({\boldsymbol{\beta}}_{12}-{\boldsymbol{\beta}}_{22})h_{1}+{\boldsymbol{\beta}}_{11}-{\boldsymbol{\beta}}_{21})(z+h_{3})+{\textbf{a}}_{2}(h_{1},h_{2}))}\\\
{f_{1}({\textbf{x}}+({\boldsymbol{\beta}}_{12}-{\boldsymbol{\beta}}_{22})(z+h_{2})^{2}+(2({\boldsymbol{\beta}}_{12}-{\boldsymbol{\beta}}_{22})h_{1}+{\boldsymbol{\beta}}_{11}-{\boldsymbol{\beta}}_{21})z+{\textbf{a}}_{3}(h_{1},h_{2}))}\\\
\overline{f_{1}({\textbf{x}}+({\boldsymbol{\beta}}_{12}-{\boldsymbol{\beta}}_{22})(z+h_{2}+h_{3})^{2}+(2({\boldsymbol{\beta}}_{12}-{\boldsymbol{\beta}}_{22})h_{1}+{\boldsymbol{\beta}}_{11}-{\boldsymbol{\beta}}_{21})(z+h_{3})+{\textbf{a}}_{3}(h_{1},h_{2}))}\\\
\gg\delta^{8}N^{2}.$

Shifting

${\textbf{x}}\mapsto{\textbf{x}}-({\boldsymbol{\beta}}_{12}-{\boldsymbol{\beta}}_{22})z^{2}-(-2{\boldsymbol{\beta}}_{22}h_{1}+{\boldsymbol{\beta}}_{11}-{\boldsymbol{\beta}}_{21})z,$

we end up with

$\sum_{{\textbf{x}},h_{1},h_{2},h_{3}}\mu_{H}(h_{1},h_{2},h_{3})\operatorname*{\mathbb{E}}_{z\in[K]}f_{1}({\textbf{x}})\overline{f_{1}({\textbf{x}}+2({\boldsymbol{\beta}}_{12}-{\boldsymbol{\beta}}_{22})h_{3}z+{\textbf{a}}_{1}(h_{1},h_{2},h_{3}))}\\\
\overline{f_{1}({\textbf{x}}+2({\boldsymbol{\beta}}_{12}-{\boldsymbol{\beta}}_{22})h_{2}z+{\textbf{a}}_{2}(h_{1},h_{2},h_{3}))}{f_{1}({\textbf{x}}+2({\boldsymbol{\beta}}_{12}-{\boldsymbol{\beta}}_{22})(h_{2}+h_{3})z+{\textbf{a}}_{3}(h_{1},h_{2},h_{3}))}\\\
\overline{f_{1}({\textbf{x}}+2{\boldsymbol{\beta}}_{12}h_{1}z+{\textbf{a}}_{4}(h_{1},h_{2},h_{3}))}{f_{1}({\textbf{x}}+(2({\boldsymbol{\beta}}_{12}-{\boldsymbol{\beta}}_{22})h_{3}+2{\boldsymbol{\beta}}_{12}h_{1})z+{\textbf{a}}_{5}(h_{1},h_{2},h_{3}))}\\\
{f_{1}({\textbf{x}}+(2({\boldsymbol{\beta}}_{12}-{\boldsymbol{\beta}}_{22})h_{2}+2{\boldsymbol{\beta}}_{12}h_{1})z+{\textbf{a}}_{6}(h_{1},h_{2},h_{3}))}\\\
\overline{f_{1}({\textbf{x}}+(2({\boldsymbol{\beta}}_{12}-{\boldsymbol{\beta}}_{22})(h_{2}+h_{3})+2{\boldsymbol{\beta}}_{12}h_{1})z+{\textbf{a}}_{7}(h_{1},h_{2},h_{3}))}\gg\delta^{8}N^{2}.$

for some polynomials ${\textbf{a}}_{j}$ in $h_{1},h_{2},h_{3}$. The important
point about this new expression is that it is an average, indexed by
$(h_{1},h_{2},h_{3})$, of counting operators for the $8$-point linear (in $z$)
configurations

$\displaystyle{\textbf{x}},\;{\textbf{x}}+2({\boldsymbol{\beta}}_{12}-{\boldsymbol{\beta}}_{22})h_{3}z,\;{\textbf{x}}+2({\boldsymbol{\beta}}_{12}-{\boldsymbol{\beta}}_{22})h_{2}z,\;{\textbf{x}}+2({\boldsymbol{\beta}}_{12}-{\boldsymbol{\beta}}_{22})(h_{2}+h_{3})z,$
$\displaystyle{\textbf{x}}+2{\boldsymbol{\beta}}_{12}h_{1}z,\;{\textbf{x}}+(2({\boldsymbol{\beta}}_{12}-{\boldsymbol{\beta}}_{22})h_{3}+2{\boldsymbol{\beta}}_{12}h_{1})z,\;{\textbf{x}}+(2({\boldsymbol{\beta}}_{12}-{\boldsymbol{\beta}}_{22})h_{2}+2{\boldsymbol{\beta}}_{12}h_{1})z,$
$\displaystyle{\textbf{x}}+(2({\boldsymbol{\beta}}_{12}-{\boldsymbol{\beta}}_{22})(h_{2}+h_{3})+2{\boldsymbol{\beta}}_{12}h_{1})z;$

as such, each of these configurations can be controlled individually by a
certain degree-$7$ box norm as in Lemma 4.4 below, using Gowers’ original
argument for controlling arithmetic progressions by Gowers norms [7, 9].
Gowers’ argument, which we abstain from showing here, consists of $7$ more
applications of the Cauchy–Schwarz and van der Corput Inequalities, together
with changes of variables, and its output is the norm-control

$\displaystyle\sum_{h_{1},h_{2},h_{3}}\mu_{H}(h_{1},h_{2},h_{3})\left\|f_{1}\right\|^{2^{7}}_{\begin{subarray}{c}2({\boldsymbol{\beta}}_{12}-{\boldsymbol{\beta}}_{22})h_{3}\cdot[\pm
M],\;2({\boldsymbol{\beta}}_{12}-{\boldsymbol{\beta}}_{22})h_{2}\cdot[\pm
M],\\\
2({\boldsymbol{\beta}}_{12}-{\boldsymbol{\beta}}_{22})(h_{2}+h_{3})\cdot[\pm
M],\;2{\boldsymbol{\beta}}_{12}h_{1}\cdot[\pm M],\\\
(2({\boldsymbol{\beta}}_{12}-{\boldsymbol{\beta}}_{22})h_{3}+2{\boldsymbol{\beta}}_{12}h_{1})\cdot[\pm
M],\\\
(2({\boldsymbol{\beta}}_{12}-{\boldsymbol{\beta}}_{22})h_{2}+2{\boldsymbol{\beta}}_{12}h_{1})\cdot[\pm
M],\\\
(2({\boldsymbol{\beta}}_{12}-{\boldsymbol{\beta}}_{22})(h_{2}+h_{3})+2{\boldsymbol{\beta}}_{12}h_{1})\cdot[\pm
M]\end{subarray}}\gg\delta^{2^{10}}N^{2}$

for any $M\ll\delta^{2^{10}}K$. The important points about this average of box
norms are that the directions

$\displaystyle
2({\boldsymbol{\beta}}_{12}-{\boldsymbol{\beta}}_{22})h_{3},\;2({\boldsymbol{\beta}}_{12}-{\boldsymbol{\beta}}_{22})h_{2},\;2({\boldsymbol{\beta}}_{12}-{\boldsymbol{\beta}}_{22})(h_{2}+h_{3}),$
$\displaystyle
2{\boldsymbol{\beta}}_{12}h_{1},\;2({\boldsymbol{\beta}}_{12}-{\boldsymbol{\beta}}_{22})h_{3}+2{\boldsymbol{\beta}}_{12}h_{1},\;2({\boldsymbol{\beta}}_{12}-{\boldsymbol{\beta}}_{22})h_{2}+2{\boldsymbol{\beta}}_{12}h_{1},$
$\displaystyle
2({\boldsymbol{\beta}}_{12}-{\boldsymbol{\beta}}_{22})(h_{2}+h_{3})+2{\boldsymbol{\beta}}_{12}h_{1}$

in the average of box norms above depend only on the leading coefficients of
the polynomials ${\textbf{P}}_{1},{\textbf{P}}_{1}-{\textbf{P}}_{2}$, and that
they are linear polynomials in $h_{1},h_{2},h_{3}$ (for a general polynomial
family ${\mathcal{P}}$, the directions will be multilinear polynomials in
$h_{i}$ of degree one smaller than the degree of ${\mathcal{P}}$).
Understanding these directions for a general polynomial family is an important
(even if tedious) task, on which we embark now.

###  4.2. Setting up the induction scheme

In order to carry out the PET argument in general, we first need to set up
some notation that allows us to talk about general multidimensional polynomial
progressions. Let $d,D,\ell,r,s\in{\mathbb{N}}$, and let
${\underline{h}}:=(h_{1},\ldots,h_{r})$ be a tuple of length $r$. All of the
polynomial families that we shall consider will take the following form.

######  Definition 4.1 (Normal polynomial family).

Let ${\mathcal{Q}}=({\textbf{Q}}_{1},\ldots,{\textbf{Q}}_{s})$ be a family of
polynomials in ${\mathbb{Z}}^{D}[z,{\underline{h}}]$ of degree at most $d$. We
call ${\mathcal{Q}}$ normal if the polynomials
${\textbf{Q}}_{1},\ldots,{\textbf{Q}}_{s}$ are nonzero and distinct,
${\textbf{Q}}_{1}$ has highest degree (with respect to the variable $z$), and
${\textbf{Q}}_{1}(0,{\underline{h}}),\ldots,{\textbf{Q}}_{s}(0,{\underline{h}})$
are the zero polynomial for all ${\underline{h}}\in{\mathbb{Z}}^{r}$.

Let ${\mathcal{P}}=({\textbf{P}}_{1},\ldots,{\textbf{P}}_{\ell})$ be a normal
family of polynomials in ${\mathbb{Z}}^{D}[z]$ of degree at most $d$. Without
loss of generality, we can assume that $\deg{\textbf{P}}_{1}=d$. We denote the
coefficients of the polynomials ${\textbf{P}}_{j}$ by
${\textbf{P}}_{j}(z)=\sum_{i=1}^{d}{\boldsymbol{\beta}}_{ji}z^{i}$, and we
also set ${\textbf{P}}_{0}:=\mathbf{0}$ and
${\boldsymbol{\beta}}_{0i}:=\mathbf{0}$. During the PET argument, we will
subject ${\mathcal{P}}$ to an iterated application of the following operation.

######  Definition 4.2 (van der Corput operation).

Let ${\mathcal{Q}}=({\textbf{Q}}_{1},\ldots,{\textbf{Q}}_{s})$ be a normal
family of polynomials in ${\mathbb{Z}}^{D}[n,{\underline{h}}]$. Given
$m\in[s]$, we define the new polynomial family

$\displaystyle\partial_{m}{\mathcal{Q}}:=$
$\displaystyle(\sigma_{h_{r+1}}{{\textbf{Q}}}_{1}-{{\textbf{Q}}}_{m},\ldots,\sigma_{h_{r+1}}{{\textbf{Q}}}_{s}-{{\textbf{Q}}}_{m},{{\textbf{Q}}}_{1}-{{\textbf{Q}}}_{m},\ldots,{{\textbf{Q}}}_{s}-{{\textbf{Q}}}_{m})^{*},$

where
$\sigma_{h_{r+1}}{\textbf{Q}}(z,{\underline{h}}):={\textbf{Q}}(z+h_{r+1},{\underline{h}})-{\textbf{Q}}(h_{r+1},{\underline{h}})$
and the ∗ operation removes all zero polynomials and all but the first copy of
each polynomial that appears multiple times.

We refer to the operation ${\mathcal{Q}}\mapsto\partial_{m}{\mathcal{Q}}$ as a
van der Corput operation on ${\mathcal{Q}}$ since the new family
$\partial_{m}{\mathcal{Q}}$ will arise from ${\mathcal{Q}}$ via an application
of the van der Corput inequality. It is through this operation that we obtain
a new polynomial family from ${\mathcal{Q}}$ at each step of the PET induction
scheme.

The following lemma shows how we can use the Cauchy–Schwarz and van der Corput
Inequalities, together with changes of variables, to pass from the family
${\mathcal{Q}}$ to the family $\partial_{m}{\mathcal{Q}}$ at each step of PET.

######  Lemma 4.3.

Let $d,D,m,\ell,r,s\in{\mathbb{N}}$, and let ${\mathcal{P}}$ be a normal
family of polynomials in ${\mathbb{Z}}^{D}[z]$ of degree at most $d$. Let
${\mathcal{Q}}=\\{{\textbf{Q}}_{1},\ldots,{\textbf{Q}}_{s}\\}$ be a normal
family of polynomials in ${\mathbb{Z}}^{D}[z,{\underline{h}}]$ with
$\deg{\textbf{Q}}_{1}>1$, and suppose that ${\mathcal{Q}}$ and
$\partial_{m}{\mathcal{Q}}$ both descend from ${\mathcal{P}}$. Let $\delta>0$
and $H,K,N\in{\mathbb{N}}$ be parameters satisfying
$H\leq\frac{\delta^{2}}{4}K$. Then for any $1$-bounded functions
$f_{0},\ldots,f_{\ell}:{\mathbb{Z}}^{D}\to{\mathbb{C}}$ supported on $[N]^{D}$
and any ${\underline{h}}\in{\mathbb{Z}}^{s}$, the lower bound

$\displaystyle\mathopen{}\left|\sum_{{\textbf{x}}\in{\mathbb{Z}}^{D}}\operatorname*{\mathbb{E}}_{z\in[K]}f_{0}({\textbf{x}})f_{1}({\textbf{x}}+{\textbf{Q}}_{1}(z,{\underline{h}}))\cdots
f_{s}({\textbf{x}}+{\textbf{Q}}_{s}(z,{\underline{h}}))\mathclose{}\right|\geq\delta
N^{D}$

implies that

$\displaystyle\sum_{h_{r+1}}\mu_{H}(h_{r+1})\sum_{{\textbf{x}}\in{\mathbb{Z}}^{D}}\operatorname*{\mathbb{E}}_{z\in[K]}\prod_{{\textbf{Q}}\in\partial_{m}{\mathcal{Q}}}f_{{\textbf{Q}}}({\textbf{x}}+{\textbf{Q}}(z,{\underline{h}},h_{r+1}))\geq\frac{\delta^{2}}{4}N^{D}$

for some $1$-bounded functions $f_{\textbf{Q}}:{\mathbb{Z}}\to{\mathbb{C}}$
with $f_{\partial_{h_{r+1}}{\textbf{Q}}_{1}-{\textbf{Q}}_{m}}=f_{1}$.

The property $f_{\partial_{h_{r+1}}{\textbf{Q}}_{1}-{\textbf{Q}}_{m}}=f_{1}$
is crucial for letting us keep track of the function $f_{1}$ over the course
of the PET procedure.

###### Proof.

First, we make the important observation that all the polynomials

(21)
$\displaystyle\sigma_{h_{r+1}}{{\textbf{Q}}}_{2}-{{\textbf{Q}}}_{m},\ldots,\sigma_{h_{r+1}}{{\textbf{Q}}}_{s}-{{\textbf{Q}}}_{m},{{\textbf{Q}}}_{1}-{{\textbf{Q}}}_{m},\ldots,{{\textbf{Q}}}_{s}-{{\textbf{Q}}}_{m}$

are distinct from $\sigma_{h_{r+1}}{{\textbf{Q}}}_{1}-{{\textbf{Q}}}_{m}$
since all of the polynomials in ${\mathcal{Q}}$ are distinct from
${\textbf{Q}}_{1}$. In making this deduction, we crucially use the assumption
that ${\textbf{Q}}_{1}$ is nonlinear in $z$, since otherwise
${{\textbf{Q}}}_{1}-{{\textbf{Q}}}_{m}$ and
$\sigma_{h_{r+1}}{{\textbf{Q}}}_{1}-{{\textbf{Q}}}_{m}$ would be the same
(note that the $\sigma$ operation removes terms independent of $z$, so were
${{\textbf{Q}}}_{1}$ linear, it would remove entirely the shift by $h_{r+1}$).
Consequently, when we apply the $*$ operation, we do not delete any polynomial
from (21) on account of its agreeing with
$\sigma_{h_{r+1}}{{\textbf{Q}}}_{1}-{{\textbf{Q}}}_{m}$. The conclusion of the
lemma then follows from an application of the Cauchy–Schwarz and van der
Corput Inequalities, together with the change of variables
${\textbf{x}}\mapsto{\textbf{x}}-{{\textbf{Q}}}_{m}(z)-{\textbf{Q}}_{1}(h_{r+1},{\underline{h}})$,
which ensures that
$f_{\partial_{h_{r+1}}{{\textbf{Q}}}_{1}-{{\textbf{Q}}}_{m}}=f_{1}$. ∎

We deal with the linear case differently.

######  Lemma 4.4.

Let $\ell,D\in{\mathbb{N}}$, and let
${\boldsymbol{\alpha}}_{1},\ldots,{\boldsymbol{\alpha}}_{\ell}\in{\mathbb{Z}}^{D}$
be nonzero vectors with ${\boldsymbol{\alpha}}_{0}=\mathbf{0}$. Let $\delta>0$
and $K,M,N\in{\mathbb{N}}$ be parameters with
$M\ll_{\ell}\delta^{O_{\ell}(1)}K$. Then for any $1$-bounded functions
$f_{0},\ldots,f_{\ell}:{\mathbb{Z}}^{D}\to{\mathbb{C}}$ supported on
$[N]^{D}$, the lower bound

$\displaystyle\mathopen{}\left|\sum_{{\textbf{x}}\in{\mathbb{Z}}^{D}}\operatorname*{\mathbb{E}}_{z\in[K]}f_{0}({\textbf{x}})\cdot\prod_{j\in[\ell]}f_{j}({\textbf{x}}+{\boldsymbol{\alpha}}_{j}z)\mathclose{}\right|\geq\delta
N^{D}$

implies that

$\displaystyle\operatorname*{\mathbb{E}}_{{\underline{m}},{\underline{m}}\in[\pm
M]^{\ell}}\sum_{{\textbf{x}}\in{\mathbb{Z}}^{D}}\Delta^{\prime}_{{\boldsymbol{\alpha}}_{j}-{\boldsymbol{\alpha}}_{0},\ldots,{\boldsymbol{\alpha}}_{j}-{\boldsymbol{\alpha}}_{j-1},{\boldsymbol{\alpha}}_{j}-{\boldsymbol{\alpha}}_{j+1},\ldots,{\boldsymbol{\alpha}}_{j}-{\boldsymbol{\alpha}}_{\ell};({\underline{m}},{\underline{m}}^{\prime})}f_{j}({\textbf{x}})\geq\frac{\delta^{2^{\ell}}}{4^{2^{\ell}-1}}N^{D}$

for each $j\in[0,\ell]$.

###### Proof.

Since the hypothesis of the lemma is invariant under permutations of the
functions $f_{1},\ldots,f_{\ell}$, it suffices to consider the case $j=1$. We
proceed by induction on $\ell$. Applying the Cauchy–Schwarz and van der Corput
Inequalities, we get

$\displaystyle\operatorname*{\mathbb{E}}_{m_{1},m_{1}^{\prime}\in[\pm
M]}\sum_{{\textbf{x}}\in{\mathbb{Z}}^{D}}\operatorname*{\mathbb{E}}_{z\in[K]}\prod_{j\in[\ell]}\Delta^{\prime}_{({\boldsymbol{\alpha}}_{j}m_{1},{\boldsymbol{\alpha}}_{j}m_{1}^{\prime})}f_{j}({\textbf{x}}+{\boldsymbol{\alpha}}_{j}z)\geq\frac{\delta^{2}}{4}N^{D}.$

After translating
${\textbf{x}}\mapsto{\textbf{x}}-{\boldsymbol{\alpha}}_{\ell}z$, we obtain the
result immediately in the case $\ell=1$, and for $\ell>1$ we invoke the case
$\ell-1$ after observing that

$({\boldsymbol{\alpha}}_{1}-{\boldsymbol{\alpha}}_{\ell})-({\boldsymbol{\alpha}}_{j}-{\boldsymbol{\alpha}}_{\ell})={\boldsymbol{\alpha}}_{1}-{\boldsymbol{\alpha}}_{j}.$

∎

Our next goal is to describe the properties of ${\mathcal{P}}$ that are
preserved by the van der Corput operation. Let
${\mathcal{Q}}=({\textbf{Q}}_{1},\ldots,{\textbf{Q}}_{s})$ be a normal family
of polynomials in ${\mathbb{Z}}^{D}[z,{\underline{h}}]$, and write

(22)
$\displaystyle{\textbf{Q}}_{j}(z,{\underline{h}})=\sum_{i=1}^{d}{\boldsymbol{\gamma}}_{ji}({\underline{h}})z^{i}$

for some ${\boldsymbol{\gamma}}_{ji}\in{\mathbb{Z}}[{\underline{h}}]$. In
other words, the ${\boldsymbol{\gamma}}_{ji}$’s are the coefficients of
${\textbf{Q}}_{j}$ as a polynomial in $z$, and they are themselves polynomials
in ${\underline{h}}$. For $j,j^{\prime}\in[0,s]$, also define

$d_{jj^{\prime}}:=\max\\{i\in[d]:\;{\boldsymbol{\gamma}}_{ji}({\underline{h}})\neq{\boldsymbol{\gamma}}_{j^{\prime}i}({\underline{h}})\\}$

to be the degree of ${\textbf{Q}}_{j}-{\textbf{Q}}_{j^{\prime}}$ as a
polynomial in $z$, where we set ${\textbf{Q}}_{0}:=\mathbf{0}$ and
${\boldsymbol{\gamma}}_{0i}:=\mathbf{0}$ for all $i\in{\mathbb{N}}_{0}$. We
want to show that if ${\mathcal{Q}}$ is a family obtained from ${\mathcal{P}}$
at some stage of the PET induction scheme, then the polynomials
${\boldsymbol{\gamma}}_{ji}$ preserve several useful properties.

######  Definition 4.5 (Descendent family of polynomials).

A normal family ${\mathcal{Q}}=({\textbf{Q}}_{1},\ldots,{\textbf{Q}}_{s})$ of
polynomials in ${\mathbb{Z}}^{D}[z,{\underline{h}}]$ descends from
${\mathcal{P}}$ if for each $j\in[s]$, the polynomials
${\boldsymbol{\gamma}}_{ji}$ in (22) can be expressed as121212The multinomial
coefficient
$\displaystyle{{{u_{1}+\cdots+u_{r}+i}\choose{u_{1},\ldots,u_{r}}}}=\frac{(u_{1}+\cdots+u_{r}+i)!}{u_{1}!\cdots
u_{r}!\cdot i!}$ is the coefficient of
${\underline{h}}^{{\underline{u}}}z^{i}=h_{1}^{u_{1}}\cdots
h_{r}^{u_{r}}z^{i}$ in $(z+h_{1}+\cdots+h_{r})^{i+u_{1}+\cdots+u_{r}}$.

(23)
$\displaystyle{\boldsymbol{\gamma}}_{ji}({\underline{h}})=\sum_{\begin{subarray}{c}{\underline{u}}\in{\mathbb{N}}_{0}^{r},\\\
|{\underline{u}}|\leq
d-i\end{subarray}}{{{u_{1}+\cdots+u_{r}+i}\choose{u_{1},\ldots,u_{r}}}}({\boldsymbol{\beta}}_{w_{j{\underline{u}}}(|{\underline{u}}|+i)}-{\boldsymbol{\beta}}_{w_{{\underline{u}}}(|{\underline{u}}|+i)}){\underline{h}}^{\underline{u}}$

for some indices
$w_{{\underline{u}}},w_{j{\underline{u}}}\in\\{0,\ldots,\ell\\}$ satisfying
the following properties:

  1. (i)

(Coefficients of ${\textbf{Q}}_{1}$) $w_{1{\underline{u}}}=1$ for all
${\underline{u}}$.

  2. (ii)

(Multilinearity) For each $j$, the polynomial
${\boldsymbol{\gamma}}_{1d_{1j}}-{\boldsymbol{\gamma}}_{jd_{1j}}$ (the leading
coefficient of ${\textbf{Q}}_{1}-{\textbf{Q}}_{j}$ as a polynomial in $z$) is
multilinear in ${\underline{h}}$.

  3. (iii)

(Leading coefficients) For each $j$ and ${\underline{u}}$, the vector
${\boldsymbol{\beta}}_{1(|{\underline{u}}|+d_{1j})}-{\boldsymbol{\beta}}_{w_{j{\underline{u}}}(|{\underline{u}}|+d_{1j})}$
is nonzero only if it is the leading coefficient of
${\textbf{P}}_{1}-{\textbf{P}}_{w_{j{\underline{u}}}}$.

The rationale behind recording the particular properties listed in Definition
4.5 is as follows. The normality of the family ensures that the progression
does not become degenerate131313A degenerate family would be one in which the
difference of some two polynomials is independent of $z$; such a family is
“bad” because successive applications of the Cauchy–Schwarz and van der Corput
Inequalities would not allow us to separate the functions corresponding to
these polynomials. and that the polynomial with index $1$ continues to have
the highest degree (which is essential for the function originally evaluated
at ${\textbf{x}}+{\textbf{P}}_{1}(z)$ not to disappear at an intermediate step
of PET). The general form of the polynomials ${\boldsymbol{\gamma}}_{ji}$
ensures that the coefficients of the ${\textbf{Q}}_{j}$’s and their pairwise
differences are bounded multiples of the coefficients of the
${\textbf{P}}_{j}$’s and their differences. The property (i) guarantees that
we do not lose information about the coefficients of ${\textbf{P}}_{1}$ while
carrying out PET. The multilinearity of the polynomials
${\boldsymbol{\gamma}}_{1d_{1j}}-{\boldsymbol{\gamma}}_{jd_{1j}}$ given in
(ii) will be crucial in our concatenation argument since, as we show in
Section 7, bounding the number of solutions to systems of multilinear
equations is much simpler than obtaining bounds for general systems of
polynomial equations. Lastly, property (iii) ensures that the coefficients of
${\boldsymbol{\gamma}}_{1d_{1j}}-{\boldsymbol{\gamma}}_{jd_{1j}}$ come from
only the leading coefficients of
${\textbf{P}}_{1},{\textbf{P}}_{1}-{\textbf{P}}_{2},\ldots,{\textbf{P}}_{1}-{\textbf{P}}_{\ell}$,
and so the end product of PET will not depend on the lower-degree
coefficients.

We note several consequences of Definition 4.5:

  1. (i)

If ${\mathcal{Q}}$ descends from ${\mathcal{P}}$, then the formulas (22) and
(23) jointly ensure that the polynomials in ${\mathcal{Q}}$ cannot have their
total degree in $z,h_{1},\ldots,h_{r}$ greater than $d$.

  2. (ii)

${\mathcal{P}}$ descends from itself: Since $r=0$, the only choice of
${\underline{u}}$ is $\underline{0}$, and one can set $w_{j\underline{0}}=j$
and $w_{\underline{0}}=0$ for each $j\in[\ell]$.

  3. (iii)

The multilinearity in (ii) tells us that only ${\underline{u}}$’s in
$\\{0,1\\}^{r}$ can contribute to
${\boldsymbol{\gamma}}_{1d_{1j}}-{\boldsymbol{\gamma}}_{jd_{1j}}$, so the
multinomial coefficients simplify and we have

$\displaystyle{\boldsymbol{\gamma}}_{1d_{1j}}({\underline{h}})-{\boldsymbol{\gamma}}_{jd_{1j}}({\underline{h}})=\sum_{\begin{subarray}{c}{\underline{u}}\in\\{0,1\\}^{r},\\\
|{\underline{u}}|\leq
d-d_{1j}\end{subarray}}\frac{(|{\underline{u}}|+d_{1j})!}{d_{1j}!}\cdot({\boldsymbol{\beta}}_{1(|{\underline{u}}|+d_{1j})}-{\boldsymbol{\beta}}_{w_{j{\underline{u}}}(|{\underline{u}}|+d_{1j})}){\underline{h}}^{\underline{u}}.$

  4. (iv)

As a special case of (iii), if the leading coefficient of ${\textbf{P}}_{1}$
differs from the leading coefficients of
${\textbf{P}}_{2},\ldots,{\textbf{P}}_{\ell}$, then for each $j$, the
polynomial ${\boldsymbol{\gamma}}_{1d_{1j}}-{\boldsymbol{\gamma}}_{jd_{1j}}$
is a multilinear, homogeneous polynomial of degree $d-d_{1j}$, and the
expression for the polynomials
${\boldsymbol{\gamma}}_{1d_{1j}}-{\boldsymbol{\gamma}}_{jd_{1j}}$ further
simplifies to

$\displaystyle{\boldsymbol{\gamma}}_{1d_{1j}}({\underline{h}})-{\boldsymbol{\gamma}}_{jd_{1j}}({\underline{h}})=\sum_{\begin{subarray}{c}{\underline{u}}\in\\{0,1\\}^{r},\\\
|{\underline{u}}|=d-d_{1j}\end{subarray}}\frac{d!}{d_{1j}!}\cdot({\boldsymbol{\beta}}_{1d}-{\boldsymbol{\beta}}_{w_{j{\underline{u}}}d}){\underline{h}}^{\underline{u}}.$

  5. (v)

If the leading coefficient of ${\textbf{P}}_{1}$ is the same as the leading
coefficient of some ${\textbf{P}}_{j}$ for $2\leq j\leq\ell$, then the
polynomial ${\boldsymbol{\gamma}}_{1d_{1j}}-{\boldsymbol{\gamma}}_{jd_{1j}}$
ceases to be homogeneous and of degree $d-d_{1j}$; for instance, if
${\mathcal{P}}=\\{z^{2}+z,z^{2}\\}$, then
$\partial_{2}{\mathcal{P}}=\\{(2h+1)z,2hz,z\\}$ descends from ${\mathcal{P}}$,
but $2h+1$ fails to be homogeneous and the polynomial $1$ has degree
$0<1=d-d_{12}$.

The descendent family obtained during the van der Corput operation admits more
properties: For instance, the coefficients
$w_{j{\underline{u}}},w_{\underline{u}}$ can be shown to satisfy
$w_{j{\underline{u}}}=w_{j{\underline{u}}^{\prime}}$ and
$w_{\underline{u}}=w_{{\underline{u}}^{\prime}}$ whenever
$\operatorname{supp}({\underline{u}})=\operatorname{supp}({\underline{u}}^{\prime})$
(here, $\operatorname{supp}({\underline{u}}):=\\{i\in[r]:\;u_{i}>0\\}$; this
property has been observed in [6, Definition 5.5 (P3)] and used in this paper
in the proof of [6, Proposition 5.7]). However, the use of this observation
has been superseded in our paper by the use of property (ii) from Definition
4.5; this property previously appeared implicitly in [23, 35].

The following lemma ascertains that the van der Corput operation preserves the
abovementioned properties inherited by ${\mathcal{Q}}$ from ${\mathcal{P}}$ by
virtue of descending from ${\mathcal{P}}$.

######  Proposition 4.6.

Let $d,D,\ell,r,s\in{\mathbb{N}}$, and let
${\mathcal{P}}=({\textbf{P}}_{1},\ldots,{\textbf{P}}_{\ell})$ be a normal
family of polynomials in ${\mathbb{Z}}^{D}[z]$ with coefficients given by
${\textbf{P}}_{j}(z)=\sum_{i=1}^{d}{\boldsymbol{\beta}}_{ji}z^{i}$. Suppose
that the family ${\mathcal{Q}}=({\textbf{Q}}_{1},\ldots,{\textbf{Q}}_{s})$ of
polynomials in ${\mathbb{Z}}^{D}[z,{\underline{h}}]$ descends from
${\mathcal{P}}$. Then the family $\partial_{m}{\mathcal{Q}}$ also descends
from ${\mathcal{P}}$ for each $m\in[s]$ for which
$\sigma_{h_{r+1}}{{\textbf{Q}}}_{1}-{{\textbf{Q}}}_{m}$ has the highest degree
(as a polynomial in $z$) among the elements of $\partial_{m}{\mathcal{Q}}$.

###### Proof.

We first note that the family $\partial_{m}{\mathcal{Q}}$ is normal: The
application of the $*$ operation ensures that the polynomials of the family
are nonzero and distinct, and the assumption in the proposition ensures that
the first polynomial in the family has the highest degree (in $z$).

We now check that $\partial_{m}{\mathcal{Q}}$ satisfies the three properties
of a descendent family. Since ${\mathcal{Q}}$ is a descendent family, the
polynomials ${\textbf{Q}}_{j}$ satisfy the formulas (22) and (23) for some
indices $w_{j{\underline{u}}},w_{\underline{u}}$ with
$w_{1{\underline{u}}}=1$. Using the binomial theorem, we can expand

$\displaystyle{\textbf{Q}}_{j}(z+h_{r+1})$
$\displaystyle=\sum_{i=0}^{d}\sum_{\begin{subarray}{c}{\underline{u}}\in{\mathbb{N}}_{0}^{r},\\\
|{\underline{u}}|\leq
d-i\end{subarray}}{{{u_{1}+\cdots+u_{r}+i}\choose{u_{1},\ldots,u_{r}}}}({\boldsymbol{\beta}}_{w_{j{\underline{u}}}(|{\underline{u}}|+i)}-{\boldsymbol{\beta}}_{w_{{\underline{u}}}(|{\underline{u}}|+i)}){\underline{h}}^{\underline{u}}(z+h_{r+1})^{i}$
$\displaystyle=\sum_{i=0}^{d}\sum_{\begin{subarray}{c}{\underline{u}}\in{\mathbb{N}}_{0}^{r},\\\
|{\underline{u}}|\leq
d-i\end{subarray}}{{{u_{1}+\cdots+u_{r}+i}\choose{u_{1},\ldots,u_{r}}}}({\boldsymbol{\beta}}_{w_{j{\underline{u}}}(|{\underline{u}}|+i)}-{\boldsymbol{\beta}}_{w_{{\underline{u}}}(|{\underline{u}}|+i)}){\underline{h}}^{\underline{u}}\sum_{l=0}^{i}{{{i}\choose{l}}}h_{r+1}^{i-l}z^{l}.$

Changing the order of summation of $i$ and $l$, setting $u_{r+1}:=i-l$, and
using the identity

$\displaystyle{{{u_{1}+\cdots+u_{r+1}+l}\choose{u_{1},\ldots,u_{r+1}}}}={{{u_{1}+\cdots+u_{r}+u_{r+1}+l}\choose{u_{1},\ldots,u_{r}}}}{{{u_{r+1}+l}\choose{l}}},$

we obtain

${\textbf{Q}}_{j}(z+h_{r+1})=\sum_{l=0}^{d}z^{l}\sum_{\begin{subarray}{c}({\underline{u}},u_{r+1})\in{\mathbb{N}}_{0}^{r+1},\\\
|{\underline{u}}|+u_{r+1}\leq
d-l\end{subarray}}{{{u_{1}+\cdots+u_{r+1}+l}\choose{u_{1},\ldots,u_{r+1}}}}\\\
({\boldsymbol{\beta}}_{w_{j{\underline{u}}}(|{\underline{u}}|+u_{r+1}+l)}-{\boldsymbol{\beta}}_{w_{{\underline{u}}}(|{\underline{u}}|+u_{r+1}+l)}){\underline{h}}^{\underline{u}}h_{r+1}^{u_{r+1}}.$

Hence

(24)
${\textbf{Q}}_{j}(z+h_{r+1})-{\textbf{Q}}_{m}(z)=\sum_{l=0}^{d}z^{l}\sum_{\begin{subarray}{c}({\underline{u}},u_{r+1})\in{\mathbb{N}}_{0}^{r+1},\\\
|{\underline{u}}|+u_{r+1}\leq
d-l\end{subarray}}{{{u_{1}+\cdots+u_{r+1}+l}\choose{u_{1},\ldots,u_{r+1}}}}\\\
({\boldsymbol{\beta}}_{w_{j({\underline{u}},u_{r+1})}(|{\underline{u}}|+u_{r+1}+l)}-{\boldsymbol{\beta}}_{w_{({\underline{u}},u_{r+1})}(|{\underline{u}}|+u_{r+1}+l)}){\underline{h}}^{\underline{u}}h_{r+1}^{u_{r+1}},$

where we set $w_{j({\underline{u}},u_{r+1})}:=w_{j{\underline{u}}}$ and

$\displaystyle
w_{({\underline{u}},u_{r+1})}:=\begin{cases}w_{\underline{u}},\;&u_{r+1}>0,\\\
w_{m{\underline{u}}},\;&u_{r+1}=0.\end{cases}$

In particular, we have $w_{1({\underline{u}},u_{r+1})}=w_{1{\underline{u}}}=1$
by the induction hypothesis, and so $\partial_{m}{\mathcal{Q}}$ satisfies
property (i).

To show properties (ii) and (iii), we need to compare
$\sigma_{h_{r+1}}{{\textbf{Q}}}_{1}(z,{\underline{h}})-{{\textbf{Q}}}_{m}(z,{\underline{h}})$
with other polynomials in $\partial_{m}{\mathcal{Q}}$ and examine the leading
coefficients of these differences (as polynomials in $z$). There are three
cases to investigate. First, we check (ii) and (iii) for differences of the
form

(25)
$(\sigma_{h_{r+1}}{{\textbf{Q}}}_{1}(z,{\underline{h}})-{{\textbf{Q}}}_{m}(z,{\underline{h}}))-(\sigma_{h_{r+1}}{{\textbf{Q}}}_{j}(z,{\underline{h}})-{{\textbf{Q}}}_{m}(z,{\underline{h}}))\\\
=\sum_{i=1}^{d_{1j}}({\boldsymbol{\gamma}}_{1d_{1j}}({\underline{h}})-{\boldsymbol{\gamma}}_{jd_{1j}}({\underline{h}}))(z+h_{r+1})^{i}-({\textbf{Q}}_{1}(h_{r+1},{\underline{h}})-{\textbf{Q}}_{j}(h_{r+1},{\underline{h}})),$

where the terms ${{\textbf{Q}}}_{m}(z,{\underline{h}})$ cancel out. The
leading coefficient of this expression (interpreted as a polynomial in $z$) is
${\boldsymbol{\gamma}}_{1d_{1j}}({\underline{h}})-{\boldsymbol{\gamma}}_{jd_{1j}}({\underline{h}})$,
the same as the leading coefficient of the polynomial
${\textbf{Q}}_{1}-{\textbf{Q}}_{m}$, and this is multilinear by assumption.
For (iii), we need to show that the nonzero vectors
${\boldsymbol{\beta}}_{1(|{\underline{u}}|+u_{r+1}+d_{1j})}-{\boldsymbol{\beta}}_{w_{j({\underline{u}},u_{r+1})}(|{\underline{u}}|+u_{r+1}+d_{1j})}$
are leading coefficients of the polynomials
${\textbf{P}}_{1}-{\textbf{P}}_{w_{j({\underline{u}},u_{r+1})}}$. If
$u_{r+1}=0$, then this follows immediately from the formula

$\displaystyle{\boldsymbol{\beta}}_{1(|{\underline{u}}|+u_{r+1}+d_{1j})}-{\boldsymbol{\beta}}_{w_{j({\underline{u}},u_{r+1})}(|{\underline{u}}|+u_{r+1}+d_{1j})}={\boldsymbol{\beta}}_{1(|{\underline{u}}|+d_{1j})}-{\boldsymbol{\beta}}_{w_{j{\underline{u}}}(|{\underline{u}}|+d_{1j})}$

and the assumption on ${\mathcal{Q}}$, while if $u_{r+1}=1$, then

$\displaystyle{\boldsymbol{\beta}}_{1(|{\underline{u}}|+u_{r+1}+d_{1j})}-{\boldsymbol{\beta}}_{w_{j({\underline{u}},u_{r+1})}(|{\underline{u}}|+u_{r+1}+d_{1j})}={\boldsymbol{\beta}}_{1(|{\underline{u}}|+d_{1j}+1)}-{\boldsymbol{\beta}}_{w_{j{\underline{u}}}(|{\underline{u}}|+d_{1j}+1)}=\mathbf{0}$

because the leading coefficient
${\boldsymbol{\gamma}}_{1d_{1j}}({\underline{h}})-{\boldsymbol{\gamma}}_{jd_{1j}}({\underline{h}})$
is independent of $h_{r+1}$.

Second, we let $d_{1}$ denote the degree of ${\textbf{Q}}_{1}$ in $z$ and
expand

(26)
$\displaystyle(\sigma_{h_{r+1}}{{\textbf{Q}}}_{1}(z,{\underline{h}})-{{\textbf{Q}}}_{m}(z,{\underline{h}}))-({{\textbf{Q}}}_{1}(z,{\underline{h}})-{{\textbf{Q}}}_{m}(z,{\underline{h}}))$
$\displaystyle\qquad\qquad\qquad\qquad\qquad=\sum_{i=1}^{d_{1}}{\boldsymbol{\gamma}}_{1i}({\underline{h}})\mathopen{}\left((z+h_{r+1})^{i}-z^{i}\mathclose{}\right)-{\textbf{Q}}_{1}(h_{r+1},{\underline{h}})$
$\displaystyle\qquad\qquad\qquad\qquad\qquad=\sum_{i=1}^{d_{1}}\sum_{l=1}^{i-1}{\boldsymbol{\gamma}}_{1i}({\underline{h}}){{{i}\choose{l}}}h_{r+1}^{i-l}z^{l}$
$\displaystyle\qquad\qquad\qquad\qquad\qquad=\sum_{l=1}^{d_{1}-1}z^{l}\sum_{i=l+1}^{d_{1}}{\boldsymbol{\gamma}}_{1i}({\underline{h}}){{{i}\choose{l}}}h_{r+1}^{i-l};$

the leading coefficient here is
$d_{1}h_{r+1}{\boldsymbol{\gamma}}_{1d_{1}}({\underline{h}})$, corresponding
to $l=d_{1}-1,i=d_{1}$. The polynomial
${\boldsymbol{\gamma}}_{1d_{1}}({\underline{h}})$ is the leading coefficient
of ${\textbf{Q}}_{1}$, so it is multilinear by assumption, and hence
$d_{1}h_{r+1}{\boldsymbol{\gamma}}_{1d_{1}}({\underline{h}})$ is multilinear
as well. Thus (ii) holds. To show property (iii), we first observe that the
coefficient of ${\underline{h}}^{\underline{u}}$ in
${\boldsymbol{\gamma}}_{1d_{1}}({\underline{h}})$ is
$\frac{(|{\underline{u}}|+d_{1})!}{d_{1}!}({\boldsymbol{\beta}}_{1(|{\underline{u}}|+d_{1})}-{\boldsymbol{\beta}}_{w_{{\underline{u}}}(|{\underline{u}}|+d_{1})})$
(where we use implicitly property (i)). Therefore, the coefficient of
${\underline{h}}^{\underline{u}}h_{r+1}$ in
$d_{1}h_{r+1}{\boldsymbol{\gamma}}_{1d_{1}}({\underline{h}})$ is

$\frac{(|{\underline{u}}|+d_{1})!}{(d_{1}-1)!}({\boldsymbol{\beta}}_{1(|{\underline{u}}|+d_{1})}-{\boldsymbol{\beta}}_{w_{{\underline{u}}}(|{\underline{u}}|+d_{1})})\\\
=\frac{(|({\underline{u}},1)|+(d_{1}-1))!}{(d_{1}-1)!}({\boldsymbol{\beta}}_{1(|({\underline{u}},1)|+(d_{1}-1))}-{\boldsymbol{\beta}}_{w_{({\underline{u}},1)}(|({\underline{u}},1)|+(d_{1}-1))}).$

By the induction hypothesis, if
${\boldsymbol{\beta}}_{1(|{\underline{u}}|+d_{1})}-{\boldsymbol{\beta}}_{w_{{\underline{u}}}(|{\underline{u}}|+d_{1})}$
is nonzero, then it is the leading coefficient of
${\textbf{P}}_{1}-{\textbf{P}}_{w_{{\underline{u}}}}$, and hence

$\displaystyle{\boldsymbol{\beta}}_{1(|({\underline{u}},1)|+(d_{1}-1))}-{\boldsymbol{\beta}}_{w_{({\underline{u}},1)}(|({\underline{u}},1)|+(d_{1}-1))}={\boldsymbol{\beta}}_{1(|{\underline{u}}|+d_{1})}-{\boldsymbol{\beta}}_{w_{{\underline{u}}}(|{\underline{u}}|+d_{1})}$

is also nonzero and the leading coefficient of
${\textbf{P}}_{1}-{\textbf{P}}_{w_{({\underline{u}},1)}}={\textbf{P}}_{1}-{\textbf{P}}_{w_{{\underline{u}}}}$.

It remains to consider

$\displaystyle(\sigma_{h_{r+1}}{{\textbf{Q}}}_{1}(z,{\underline{h}})-{{\textbf{Q}}}_{m}(z,{\underline{h}}))-({{\textbf{Q}}}_{j}(z,{\underline{h}})-{{\textbf{Q}}}_{m}(z,{\underline{h}}))$

for $j\neq 1$; we split this case into two subcases. If
${\boldsymbol{\gamma}}_{1d_{1}}({\underline{h}})\neq{\boldsymbol{\gamma}}_{jd_{1}}({\underline{h}})$,
then the leading coefficient equals
${\boldsymbol{\gamma}}_{1d_{1j}}({\underline{h}})-{\boldsymbol{\gamma}}_{jd_{1j}}({\underline{h}})={\boldsymbol{\gamma}}_{1d_{1}}({\underline{h}})-{\boldsymbol{\gamma}}_{jd_{1}}({\underline{h}})$.
This is the leading coefficient of ${\textbf{Q}}_{1}-{\textbf{Q}}_{j}$, so it
is multilinear by assumption, and property (iii) holds for the same reason as
it held for (25).

Otherwise,
${\boldsymbol{\gamma}}_{1d_{1}}({\underline{h}})={\boldsymbol{\gamma}}_{jd_{1}}({\underline{h}})$,
in which case the leading coefficient equals

(27) $\displaystyle
d_{1}h_{r+1}{\boldsymbol{\gamma}}_{1d_{1}}({\underline{h}})+{\boldsymbol{\gamma}}_{1(d_{1}-1)}({\underline{h}})-{\boldsymbol{\gamma}}_{j(d_{1}-1)}({\underline{h}}),$

where

$\displaystyle{\boldsymbol{\gamma}}_{1(d_{1}-1)}({\underline{h}})-{\boldsymbol{\gamma}}_{j(d_{1}-1)}({\underline{h}})=\begin{cases}{\boldsymbol{\gamma}}_{1d_{1j}}({\underline{h}})-{\boldsymbol{\gamma}}_{jd_{1j}}({\underline{h}}),\;&\textrm{if}\quad
d_{1j}=d_{1}-1,\\\ \mathbf{0},\;&\textrm{if}\quad d_{1j}<d_{1}-1.\end{cases}$

The term $d_{1}h_{r+1}{\boldsymbol{\gamma}}_{1d_{1}}({\underline{h}})$ is
multilinear by the same argument as in the previous case. The term
${\boldsymbol{\gamma}}_{1(d_{1}-1)}({\underline{h}})-{\boldsymbol{\gamma}}_{j(d_{1}-1)}({\underline{h}})$
is trivially multilinear when $d_{1j}<d_{1}-1$, and its multilinearity follows
from the assumption on ${\mathcal{Q}}$ when $d_{1j}=d_{1}-1$ (since then it is
the leading coefficient of ${\textbf{Q}}_{1}-{\textbf{Q}}_{j}$). Hence (27) is
multilinear as well.

It remains only to prove property (iii) in this very last case, namely, to
show that if the coefficient of the monomial
${\underline{h}}^{\underline{u}}h_{r+1}^{u_{r+1}}$ in (27) is nonzero, then it
is an appropriate scalar multiple of the leading coefficient of the polynomial
${\textbf{P}}_{1}-{\textbf{P}}_{w_{j({\underline{u}},u_{r+1})}}={\textbf{P}}_{1}-{\textbf{P}}_{w_{j{\underline{u}}}}$.
If $u_{r+1}=1$, then the coefficient of
${\underline{h}}^{\underline{u}}h_{r+1}^{u_{r+1}}$ in (27) is the same as in
$d_{1}h_{r+1}{\boldsymbol{\gamma}}_{1d_{1}}({\underline{h}})$, and the claim
follows by the same reasoning as in the case of (26). Otherwise, $u_{r+1}=0$,
and the coefficient ${\underline{h}}^{\underline{u}}h_{r+1}^{u_{r+1}}$ in (27)
comes fully from
${\boldsymbol{\gamma}}_{1d_{1j}}({\underline{h}})-{\boldsymbol{\gamma}}_{jd_{1j}}({\underline{h}})$.
The result then follows by the same argument as one used to prove property
(iii) for (25). ∎

The next result ensures that we reach a family of linear polynomials after a
bounded number of van der Corput operations; this fact is the foundation of
all PET induction schemes.

######  Proposition 4.7.

Let $d,D,r,s\in{\mathbb{N}}$, let ${\mathcal{P}}$ be a normal family of
polynomials in ${\mathbb{Z}}^{D}[z]$ of degree at most $d$, and let
${\mathcal{Q}}$ be a normal family of polynomials in
${\mathbb{Z}}^{D}[z,{\underline{h}}]$ of length $s$ that descends from
${\mathcal{P}}$. There exist a nonnegative integer $r^{\prime}=O_{d,s}(1)$ and
positive integers $m_{1},\ldots,m_{r^{\prime}}$ such that the family
${\mathcal{Q}}_{i}:=\partial_{m_{i}}\cdots\partial_{m_{1}}{\mathcal{Q}}$
descends from ${\mathcal{P}}$ for each $i\in[r^{\prime}]$ and, moreover, the
elements of ${\mathcal{Q}}_{r^{\prime}}$ are linear in $z$.

We remark that $r^{\prime}$ is independent of the dimension $D$ of the
underlying space.

###### Proof.

Let ${\mathcal{Q}}:=({\textbf{Q}}_{1},\ldots,{\textbf{Q}}_{s})$. As usual, we
expand each ${\textbf{Q}}_{j}$ as in (22) and say that its leading coefficient
is ${\boldsymbol{\gamma}}_{ji}\in{\mathbb{Z}}^{D}[{\underline{h}}]$ for the
largest $i\in[d]$ with ${\boldsymbol{\gamma}}_{ji}\neq\mathbf{0}$. Let
$d^{\prime}$ be the maximum degree of
${\textbf{Q}}_{j},\ldots,{\textbf{Q}}_{s}$ as a polynomial in $z$; since
${\mathcal{Q}}$ descends from ${\mathcal{P}}$ and is normal, necessarily
$1\leq d^{\prime}\leq d$. For $l\in[d^{\prime}]$, let $w_{l}$ denote the
number of distinct leading coefficients of the degree-$l$ polynomials in
${\mathcal{Q}}$. We then define $w=(w_{1},\ldots,w_{d^{\prime}})$ to be the
type of ${\mathcal{Q}}$, and we order the types colexicographically.141414That
is, we have $w>w^{\prime}$ if $w_{l}>w^{\prime}_{l}$ for the largest $l$ with
$w_{l}\neq w^{\prime}_{l}$.

Since the family ${\mathcal{Q}}$ is normal and has positive length, we have
$w>(0,\ldots,0)$; let $l$ be the smallest index for which $w_{l}\neq 0$. We
define a parameter $m_{1}$ as follows. If $l<d^{\prime}$, then we choose an
arbitrary $m_{1}\in[s]$ with $\deg{\textbf{Q}}_{m_{1}}=l$. If $l=d^{\prime}$
(i.e., all of the polynomials in ${\mathcal{Q}}$ have degree $d^{\prime}$ as
polynomials in $z$) and $w_{d^{\prime}}>1$, then we choose an arbitrary
$m_{1}\in[s]$ such that ${\textbf{Q}}_{m_{1}}$ and ${\textbf{Q}}_{1}$ have
different leading coefficients. Finally, if $l=d^{\prime}$ and
$w_{d^{\prime}}=1$ (i.e., all of the polynomials have the same leading term),
then we choose ${m_{1}}=1$. A standard calculation shows that in each case the
new family ${\mathcal{Q}}_{1}=\partial_{m_{1}}{\mathcal{Q}}$ has type

$w^{\prime}=(w^{\prime}_{1},\ldots,w^{\prime}_{l-1},w_{l}-1,w_{l+1},\ldots,w_{d^{\prime}})<w,$

for some $0\leq w^{\prime}_{1},\ldots,w^{\prime}_{l-1}\leq 2s$, and the
polynomial $\partial_{h}{\textbf{Q}}_{1}-{\textbf{Q}}_{m_{1}}$ has the maximum
degree among the polynomials in ${\mathcal{Q}}_{1}$. It follows from
Proposition 4.6 that ${\mathcal{Q}}_{1}$ descends from ${\mathcal{P}}$.

We now iterate this algorithm. Since each decreasing sequence of types
$w^{0}>w^{1}>w^{2}>\cdots$ with $w^{0}=w$ eventually reaches a type
$w^{r^{\prime}}=(w^{r^{\prime}}_{1},0,\ldots,0)$ for some
$r^{\prime}=O_{d^{\prime},s}(1)=O_{d,s}(1)$ and
$w^{r^{\prime}}_{1}=O_{r^{\prime},s}(1)=O_{d,s}(1)$, the algorithm terminates
after $O_{d,s}(1)$ steps, and we obtain the conclusion of the proposition. ∎

We remark that in the existing literature, the type of a polynomial family is
often expressed as a matrix rather than a (row) vector, with different
coordinates in ${\mathbb{Z}}^{D}$ giving rise to different rows in the matrix
(see e.g. [3, 4, 6]). This bookkeeping is excessive, however; as the above
proof illustrates, the type-reduction proceeds in the same way regardless of
$D$, and the number of steps does not depend on $D$. The argument is even more
robust: The number of steps would in fact be the same if we considered
polynomial families over any integral domains with characteristic either equal
to $0$ or sufficiently large in terms of the degrees of the polynomials and
the order of their coefficients.151515In the small-characteristic case, there
may be additional degeneracies. For instance, a term $\beta_{d}z^{d}$ may
reduce eventually to a term $\beta_{d}dz^{d-1}h$, and if the underlying ring
has characteristic dividing $\beta_{d}d$, then this term vanishes, which
requires a more refined treatment. Other complications arise if the underlying
ring has zero divisors. See [2] for an example of a PET argument dealing with
the latter issue.

In the example discussed in Section 4.1, the original family has type $(0,2)$
(or $(1,1)$ if ${\boldsymbol{\beta}}_{22}=\textbf{0}$; we ignore this case for
now). The new families obtained in steps 1, 2, and 3 have types $(1,1)$,
$(0,1)$ and $(7,0)$ (respectively).

###  4.3. Bounds by averages of box seminorms

Having presented the PET induction scheme in detail, we are ready now to show
that the counting operator (20) is controlled by an average of box norms whose
directions can be described in terms of the coefficients of the polynomials
appearing in the multidimensional polynomial progression and the coefficients
of differences of these polynomials. We no longer assume that
${\textbf{P}}_{1}$ has the highest degree among
${\textbf{P}}_{1},\ldots,{\textbf{P}}_{\ell}$.

######  Proposition 4.8 (PET bound for polynomials).

Let $d,\ell\in{\mathbb{N}}$. There exist positive integers $r,s=O_{d,\ell}(1)$
such that the following holds. Let $\delta>0$ and $D,H,K,M,N,\in{\mathbb{N}}$
satisfy $H,M\ll_{d,D,\ell}\delta^{O_{d,\ell}(1)}K$. Let
${\textbf{P}}_{1},\ldots,{\textbf{P}}_{\ell}\in{\mathbb{Z}}^{D}[z]$ be
essentially distinct polynomials with degrees at most $d$ and coefficients
${\textbf{P}}_{j}(z)=\sum_{i=0}^{d}{\boldsymbol{\beta}}_{ji}z^{i}$. Then for
any $1$-bounded functions
$f_{0},\ldots,f_{\ell}:{\mathbb{Z}}^{D}\to{\mathbb{C}}$, the lower bound

$\displaystyle\mathopen{}\left|\sum_{{\textbf{x}}\in{\mathbb{Z}}^{D}}\operatorname*{\mathbb{E}}_{z\in[K]}f_{0}({\textbf{x}})\cdot
f_{1}({\textbf{x}}+{\textbf{P}}_{1}(z))\cdots
f_{\ell}({\textbf{x}}+{\textbf{P}}_{\ell}(z))\mathclose{}\right|\geq\delta
N^{D}$

implies that

$\displaystyle\operatorname*{\mathbb{E}}_{{\underline{h}}\in[\pm
H]^{r}}\left\|f_{1}\right\|_{{{\textbf{C}}_{1}({\underline{h}})}\cdot[\pm
M],\ldots,{{\textbf{C}}_{s}({\underline{h}})\cdot[\pm
M]}}^{2^{s}}\gg_{d,D,\ell}\delta^{O_{d,\ell}(1)}N^{D},$

where
${\textbf{C}}_{1},\ldots,{\textbf{C}}_{s}\in{\mathbb{Z}}^{D}[{\underline{h}}]$
are nonzero multilinear polynomials depending only on
${\textbf{P}}_{1},\ldots,{\textbf{P}}_{\ell}$, and they take the form

(28)
$\displaystyle{\textbf{C}}_{j}({\underline{h}})=\sum_{\begin{subarray}{c}{\underline{u}}\in\\{0,1\\}^{r},\\\
|{\underline{u}}|\leq
d-1\end{subarray}}(|{\underline{u}}|+1)!\cdot({\boldsymbol{\beta}}_{1(|{\underline{u}}|+1)}-{\boldsymbol{\beta}}_{w_{j{\underline{u}}}(|{\underline{u}}|+1)}){\underline{h}}^{\underline{u}}$

for some indices $w_{j{\underline{u}}}\in[0,\ell]$ (with
${\boldsymbol{\beta}}_{0(|{\underline{u}}|+1)}:=\mathbf{0}$). Moreover, each
nonzero vector
${\boldsymbol{\beta}}_{1(|{\underline{u}}|+1)}-{\boldsymbol{\beta}}_{w_{j{\underline{u}}}(|{\underline{u}}|+1)}$
from (28) is the leading coefficient of
${\textbf{P}}_{1}-{\textbf{P}}_{w_{j{\underline{u}}}}$.

We typically apply Proposition 4.8 with $K\asymp_{d}(N/V)^{1/d}$ for
$V:=\max_{j,i}|{\boldsymbol{\beta}}_{ji}|$, as this provides the maximum
possible range for which ${\textbf{P}}_{j}(z)\in[\pm N]^{D}$ for all
$j\in[\ell]$ and $z\in[K]$. Since we do not place any special assumptions on
${\textbf{P}}_{1}$, the role of $f_{1}$ in the conclusion can be replaced by
any of the functions $f_{0},\ldots,f_{\ell}$ (with an appropriate modification
of the formulas for (28)). For $f_{2},\ldots,f_{\ell}$, this is obvious by
symmetry, whereas for $f_{0}$ this follows after shifting
${\textbf{x}}\mapsto{\textbf{x}}-{\textbf{P}}_{m}$ for some arbitrary
$m\in[\ell]$ and observing (as in the proof of Proposition 4.8 below) that the
resulting collections of polynomials (29) are identical.

###### Proof.

We will proceed under the assumption that ${\textbf{P}}_{1}$ has the largest
degree among the ${\textbf{P}}_{j}$’s; at the end we will describe the
necessary modifications in the general case.

Proposition 4.7 provides $r=O_{d,\ell}(1)$ and
$m_{1},\ldots,m_{r}\in{\mathbb{N}}$ such the families
${\mathcal{Q}}_{i}=\partial_{m_{i}}\cdots\partial_{m_{1}}{\mathcal{P}}$ all
descend from ${\mathcal{P}}$ and ${\mathcal{Q}}_{r}$ is linear in $z$. Let

$\displaystyle{\textbf{b}}_{1}({\underline{h}})z,\ldots,{\textbf{b}}_{s}({\underline{h}})z$

be the elements of ${\mathcal{Q}}_{r}$. Since the van der Corput operation at
most doubles the length of a polynomial family, we have
$s:=|{\mathcal{Q}}_{r}|\leq 2^{r}|{\mathcal{P}}|\ll_{d,\ell}1$. Applying Lemma
4.3 inductively to each of ${\mathcal{Q}}_{0},\ldots,{\mathcal{Q}}_{r-1}$
(with ${\mathcal{Q}}_{0}:={\mathcal{P}}$), we deduce that