$\displaystyle\sum_{{\underline{h}}\in{\mathbb{Z}}^{r}}\mu_{H}({\underline{h}}){\sum_{{\textbf{x}}\in{\mathbb{Z}}^{D}}\operatorname*{\mathbb{E}}_{z\in[K]}f_{0}({\textbf{x}})\cdot\prod_{j=1}^{s}f_{j}({\textbf{x}}+{\textbf{b}}_{j}({\underline{h}})z)}\gg_{d,D,\ell}\delta^{O_{d,\ell}(1)}N^{D}.$

The power of $\delta$ depends only on the number of iterations of Lemma 4.3;
in particular, it is independent of $D$.

Since the family ${\mathcal{Q}}_{r}$ descends from ${\mathcal{P}}$, the
polynomials ${\textbf{b}}_{1},\ldots,{\textbf{b}}_{s}$ are all distinct. Lemma
4.4 then implies that

$\displaystyle\sum_{{\underline{h}}\in{\mathbb{Z}}^{r}}\mu_{H}({\underline{h}})\operatorname*{\mathbb{E}}_{{\underline{m}},{\underline{m}}^{\prime}\in[\pm
M]^{s}}\sum_{{\textbf{x}}\in{\mathbb{Z}}^{D}}\Delta^{\prime}_{{{\textbf{C}}_{1}({\underline{h}})},\ldots,{{\textbf{C}}_{s}({\underline{h}})};({\underline{m}},{\underline{m}}^{\prime})}f_{1}({\textbf{x}})\gg_{d,D,\ell}\delta^{O_{d,\ell}(1)}N^{D},$

where ${\textbf{C}}_{1},\ldots,{\textbf{C}}_{s}$ are the polynomials
${\textbf{b}}_{1},{\textbf{b}}_{1}-{\textbf{b}}_{2},\ldots,{\textbf{b}}_{1}-{\textbf{b}}_{s}$.
Since
$\mu_{H}({\underline{h}})\leq\frac{\mathbf{1}_{[-2H,2H]^{r}}({\underline{h}})}{(4H+1)^{r}}$
pointwise and the inner average is nonnegative (by virtue of being an average
of box norms), the inequality in the conclusion of the proposition follows
after we replace $H$ with $H/2$.

That the polynomials ${\textbf{C}}_{1},\ldots,{\textbf{C}}_{s}$ are nonzero is
a consequence of the distinctness of
${\textbf{b}}_{1},\ldots,{\textbf{b}}_{s}$, which in turn is a consequence of
the tuple ${\mathcal{Q}}_{r}$ being normal. The form of
${\textbf{C}}_{1},\ldots,{\textbf{C}}_{s}$ is then a consequence of the
properties (i)-(iii) from Definition 4.5.

We now address the case where ${\textbf{P}}_{1}$ does not have the largest
degree. Then some other ${\textbf{P}}_{m}$ has the largest degree, and we can
translate ${\textbf{x}}\mapsto{\textbf{x}}-{\textbf{P}}_{m}(z)$ so that

$\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))\\\
=\sum_{{\textbf{x}}\in{\mathbb{Z}}^{D}}\operatorname*{\mathbb{E}}_{z\in[K]}f_{0}({\textbf{x}}-{\textbf{P}}_{m}(z))\cdot\prod_{\begin{subarray}{c}j\in[\ell]\end{subarray}}f_{j}({\textbf{x}}+{\textbf{P}}_{j}(z)-{\textbf{P}}_{m}(z)).$

We set

$\displaystyle\tilde{{\textbf{P}}}_{j}=\begin{cases}{\textbf{P}}_{j}-{\textbf{P}}_{m},\;&j\neq
m,\\\ -{\textbf{P}}_{m},\;&j=m,\end{cases}$

so that $\tilde{{\textbf{P}}}_{1}$ has the largest degree among the
$\tilde{{\textbf{P}}}_{j}$’s and we can apply the argument above (after
exchanging $f_{0}$ and $f_{m}$). The desired result now follows from the
observation that

(29)
$\displaystyle\\{{\textbf{P}}_{1},{\textbf{P}}_{1}-{\textbf{P}}_{j}:j\in[2,\ell]\\}\quad\textrm{and}\quad\\{\tilde{{\textbf{P}}}_{1},\tilde{{\textbf{P}}}_{1}-\tilde{{\textbf{P}}}_{j}:j\in[2,\ell]\\}$

are identical as sets and hence these families of polynomials have the same
leading coefficients. ∎

##  5\. Model example: concatenation of degree-$1$ box norms

To illustrate some of the ideas that go into the proof of Theorem 1.10, we
start with a model concatenation result for averages of degree-$1$ box norms.

######  Proposition 5.1.

Let $d,D,r\in{\mathbb{N}}$ with $d\leq r$. Let $\delta>0$ and
$H,M,N\in{\mathbb{N}}$ satisfy

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

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

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

implies that

$\displaystyle\left\|f\right\|_{[\pm
N]^{D},E}^{4}\gg_{D,r}\delta^{O_{r}(1)}N^{D},$

where

(32) $\displaystyle
E=\sum_{{\underline{u}}\in\\{0,1\\}^{r}}{\boldsymbol{\gamma}}_{\underline{u}}\cdot[\pm
H^{|{\underline{u}}|}M].$

We observe that the multiset $E$ is a generalized arithmetic progression
spanned by the coefficients ${\boldsymbol{\gamma}}_{\underline{u}}$, and that
the length of the interval corresponding to the coefficient
${\boldsymbol{\gamma}}_{\underline{u}}$ is of the same order of magnitude as
the maximum value of the monomial ${\underline{h}}^{\underline{u}}m$.
Moreover, if ${\boldsymbol{\gamma}}_{\underline{u}}=\textbf{0}$, i.e., the
monomial ${\underline{h}}^{\underline{u}}$ does not appear in the polynomial
C, then the corresponding term does not contribute to the set $E$.

######  Example 5.2.

To illustrate the content of Proposition 5.1 with a specific example, we
consider the polynomial

${\textbf{C}}(h_{1},h_{2})={\mathbf{e}}_{1}h_{1}h_{2}+{\mathbf{e}}_{2}h_{1}=(h_{1}h_{2},h_{1}),$

where $D=2$, $H=M=N^{1/3}$; for simplicity, we take $N$ to be a perfect cube.
Proposition 5.1 tells us that if

$\displaystyle\sum_{x_{1},x_{2},m}\operatorname*{\mathbb{E}}_{h_{1},h_{2}\in[\pm
N^{1/3}]}\mu_{N^{1/3}}(m)f(x_{1},x_{2})\overline{f(x_{1}+h_{1}h_{2}m,x_{2}+h_{1}m)}\geq\delta
N^{2},$

or equivalently

$\displaystyle\sum_{{\textbf{x}},m}\operatorname*{\mathbb{E}}_{{\underline{h}}\in[\pm
N^{1/3}]^{2}}\mu_{N^{1/3}}(m)f({\textbf{x}})\overline{f({\textbf{x}}+({\mathbf{e}}_{1}h_{1}h_{2}+{\mathbf{e}}_{2}h_{1})m)}\geq\delta
N^{2},$

then

$\displaystyle\sum_{{\textbf{x}}}\operatorname*{\mathbb{E}}_{{\mathbf{n}}_{1},{\mathbf{n}}^{\prime}_{1}\in[\pm
N]^{2}}\operatorname*{\mathbb{E}}_{{\mathbf{n}}_{2},{\mathbf{n}}^{\prime}_{2}\in[\pm
N]\times[\pm
N^{2/3}]}\Delta^{\prime}_{({\mathbf{n}}_{1},{\mathbf{n}}_{1}^{\prime}),\;({\mathbf{n}}_{2},{\mathbf{n}}^{\prime}_{2})}f({\textbf{x}})\gg\delta^{O(1)}N^{2}.$

Writing ${\mathbf{n}}_{2}=(n_{21},n_{22})$ and
${\mathbf{n}}_{2}^{\prime}=(n_{21}^{\prime},n_{22}^{\prime})$, we see that the
variables $n_{21},n_{21}^{\prime}$ correspond to the monomial $h_{1}h_{2}$
(equivalently, to the coefficient ${\underline{u}}=(1,1)$) and hence run along
the coefficient ${\mathbf{e}}_{1}$ of $h_{1}h_{2}$ in C; the variables
$n_{22},n_{22}^{\prime}$ correspond to the monomial $h_{1}$ (equivalently, to
${\underline{u}}=(1,0)$) and therefore run along the coefficient
${\mathbf{e}}_{2}$ of $h_{1}$ in C.

In applications, we usually want to discard the directions that correspond to
lower-degree terms in the original polynomial, such as the direction
${\mathbf{e}}_{1}$ corresponding to the index $(1,0)$ in the example above. We
accomplish this using Lemma 3.5, and obtain the following streamlined version
of Proposition 5.1.

######  Corollary 5.3.

Let $d,D,r\in{\mathbb{N}}$ with $d\leq r$. Let $N\in{\mathbb{N}}$ and
$\delta>0$ satisfy $N\gg_{D,r}\delta^{-O_{r}(1)}$, and let
${\textbf{C}}({\underline{h}})=\sum\limits_{{\underline{u}}\in\\{0,1\\}^{r}}{\boldsymbol{\gamma}}_{\underline{u}}{\underline{h}}^{\underline{u}}\in{\mathbb{Z}}^{D}[h_{1},\ldots,h_{r}]$
be a multilinear polynomial of degree $d$ with coefficients of size $O(1)$.
Then for all $1$-bounded functions $f:{\mathbb{Z}}^{D}\to{\mathbb{C}}$
supported on $[N]^{D}$, the lower bound

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

implies that

$\displaystyle\left\|f\right\|_{({\boldsymbol{\gamma}}_{\underline{u}}\cdot[\pm
N])^{2}}^{4}\gg_{D,r}\delta^{O_{r}(1)}N^{D}$

for each ${\underline{u}}\in\\{0,1\\}^{r}$ with $|{\underline{u}}|=d$ and
${\boldsymbol{\gamma}}_{\underline{u}}\neq\textbf{0}$.

###### Proof.

Proposition 5.1 applied with $H=M=N^{1/(d+1)}$ gives

$\displaystyle\left\|f\right\|_{[\pm
N]^{D},E}^{4}\gg_{D,r}\delta^{O_{r}(1)}N^{D},$

where $E$ is as in (32). Since the coefficients
${\boldsymbol{\gamma}}_{\underline{u}}$ have size $O(1)$, we can find vectors
${\textbf{v}}_{1},\ldots,{\textbf{v}}_{k}\in{\mathbb{Z}}^{D}$ (with $k<D$) of
size $O(1)$ such that the set

$\displaystyle\\{{\boldsymbol{\gamma}}_{\underline{u}}:\;{\underline{u}}\in\\{0,1\\}^{r},\;|{\underline{u}}|=d,{\boldsymbol{\gamma}}_{\underline{u}}\neq\textbf{0}\\}\cup\\{{\textbf{v}}_{1},\ldots,{\textbf{v}}_{k}\\}$

generates a subgroup in ${\mathbb{Z}}^{D}$ of index $O(1)$. Hence there exists
a positive integer such that

$\displaystyle C\cdot[\pm
N/C]^{D}\subseteq\sum_{\begin{subarray}{c}{\underline{u}}\in\\{0,1\\}^{r},\\\
|{\underline{u}}|=d\end{subarray}}{\boldsymbol{\gamma}}_{\underline{u}}\cdot[\pm
CN]+\sum_{i=1}^{k}{\textbf{v}}_{i}\cdot[\pm CN],$

and so by successively applying properties (vii), (iv), (v) and (vi) of Lemma
3.5, we get

$\displaystyle\left\|f\right\|_{E^{\prime},E}^{4}\gg_{D,r}\delta^{O_{r}(1)}N^{D}$

for

$\displaystyle
E^{\prime}=\sum_{\begin{subarray}{c}{\underline{u}}\in\\{0,1\\}^{r},\\\
|{\underline{u}}|=d\end{subarray}}{\boldsymbol{\gamma}}_{\underline{u}}\cdot[\pm
N].$

To conclude from here, we pick a single ${\underline{u}}$ and apply Lemma
3.5(v). ∎

Corollary 5.3 allows us to upgrade the conclusion of Example 5.2 to

$\displaystyle\sum_{{\textbf{x}}}\operatorname*{\mathbb{E}}_{n_{1},n_{1}^{\prime},n_{2},n_{2}^{\prime}\in[\pm
N]}\Delta^{\prime}_{(n_{1}{\mathbf{e}}_{1},n^{\prime}_{1}{\mathbf{e}}_{1}),\;(n_{2}{\mathbf{e}}_{1},n_{2}^{\prime}{\mathbf{e}}_{1})}f({\textbf{x}})\gg\delta^{O(1)}N^{2}.$

###  5.1. Sketch of the proof of Proposition 5.1

We now outline the proof of Proposition 5.1 in order to present the logic
behind our concatenation argument in a relatively simple setting. This is an
expanded version of the overview given in Section 2. The argument gets
considerably more complicated in the setting of box norms of degree greater
than $1$, so the reader may find the simplified argument useful for grasping
the main ideas. In the sketch, we use as a black box some technical results
that will be derived in later sections. . Suppose that (31) holds. Expanding
the definition of the box norm gives us

$\displaystyle\operatorname*{\mathbb{E}}_{{\underline{h}}\in[\pm
H]^{r}}\operatorname*{\mathbb{E}}_{m,m^{\prime}\in[\pm
M]}\sum_{{\textbf{x}}}\Delta^{\prime}_{({\textbf{C}}({\underline{h}})m,{\textbf{C}}({\underline{h}})m^{\prime})}f({\textbf{x}})\geq\delta
N^{D}.$

Shifting ${\textbf{x}}\mapsto{\textbf{x}}-{\textbf{C}}({\underline{h}})m$,
replacing $m^{\prime}-m$ by $m$, and changing the order of summation, we get

$\displaystyle\sum_{\textbf{x}}f({\textbf{x}})\operatorname*{\mathbb{E}}_{{\underline{h}}\in[\pm
H]^{r}}\sum_{m}\mu_{M}(m)\overline{f({\textbf{x}}+{\textbf{C}}({\underline{h}})m)}\geq\delta
N^{D}.$

We will use several applications of the Cauchy–Schwarz inequality to replace
the polynomial ${\textbf{C}}({\underline{h}})m$ by one with better
equidistribution properties: Specifically, we want to replace it by a
polynomial in a larger number of variables that does not assume any particular
value more than a constant multiple of the “expected” number of times. Each
application of the Cauchy–Schwarz inequality, which increases the number of
variables, can be understood as a “smoothing” of the polynomial differencing
parameter.

Step 1: Replacing ${\textbf{C}}({\underline{h}})m$ by a polynomial with better
equidistribution properties.

Applying the Cauchy–Schwarz inequality in x, we double the ${\underline{h}},m$
variables and obtain

$\displaystyle\sum_{\textbf{x}}\operatorname*{\mathbb{E}}_{{\underline{h}}_{1},{\underline{h}}_{2}\in[\pm
H]^{r}}\sum_{m_{1},m_{2}}\mu_{M}(m_{1},m_{2})f({\textbf{x}}+{\textbf{C}}({\underline{h}}_{1})m_{1})\overline{f({\textbf{x}}+{\textbf{C}}({\underline{h}}_{2})m_{2})}\geq\delta^{2}N^{D},$

then we shift
${\textbf{x}}\mapsto{\textbf{x}}-{\textbf{C}}({\underline{h}}_{1})m_{1}$ to
get

$\displaystyle\sum_{\textbf{x}}f({\textbf{x}})\operatorname*{\mathbb{E}}_{{\underline{h}}_{1},{\underline{h}}_{2}\in[\pm
H]^{r}}\sum_{m_{1},m_{2}}\mu_{M}(m_{1},m_{2})\overline{f({\textbf{x}}+{\textbf{C}}({\underline{h}}_{2})m_{2}-{\textbf{C}}({\underline{h}}_{1})m_{1})}\geq\delta^{2}N^{D}.$

Applying the Cauchy–Schwarz inequality in x again gives

$\sum_{\textbf{x}}\operatorname*{\mathbb{E}}_{\begin{subarray}{c}{\underline{h}}_{1},{\underline{h}}_{2},\\\
{\underline{h}}_{3},{\underline{h}}_{4}\in[\pm
H]^{r}\end{subarray}}\sum_{\begin{subarray}{c}m_{1},m_{2},\\\
m_{3},m_{4}\end{subarray}}\mu_{M}(m_{1},m_{2},m_{3},m_{4})\\\
f({\textbf{x}}+{\textbf{C}}({\underline{h}}_{2})m_{2}-{\textbf{C}}({\underline{h}}_{1})m_{1})\overline{f({\textbf{x}}+{\textbf{C}}({\underline{h}}_{4})m_{4}-{\textbf{C}}({\underline{h}}_{3})m_{3})}\geq\delta^{4}N^{D},$

and, after changing variables
${\textbf{x}}\mapsto{\textbf{x}}-({\textbf{C}}({\underline{h}}_{2})m_{2}-{\textbf{C}}({\underline{h}}_{1})m_{1})$,
$m_{2}\mapsto-m_{2},m_{3}\mapsto-m_{3}$, we obtain

$\operatorname*{\mathbb{E}}_{\begin{subarray}{c}{\underline{h}}_{1},{\underline{h}}_{2},\\\
{\underline{h}}_{3},{\underline{h}}_{4}\in[\pm
H]^{r}\end{subarray}}\sum_{\begin{subarray}{c}m_{1},m_{2},\\\
m_{3},m_{4}\end{subarray}}\mu_{M}(m_{1},m_{2},m_{3},m_{4})\\\
\sum_{x}f({\textbf{x}})\overline{f\mathopen{}\left({\textbf{x}}+{\textbf{C}}({\underline{h}}_{1})m_{1}+{\textbf{C}}({\underline{h}}_{2})m_{2}+{\textbf{C}}({\underline{h}}_{3})m_{3}+{\textbf{C}}({\underline{h}}_{4})m_{4}\mathclose{}\right)}\geq\delta^{4}N^{D}.$

Thus, at the cost of increasing the power of $\delta$ in our lower bound, we
have replaced ${\textbf{C}}({\underline{h}})m$ by the polynomial

$\displaystyle\sum\limits_{i\in[4]}{\textbf{C}}({\underline{h}}_{i})m_{i}={\textbf{C}}({\underline{h}}_{1})m_{1}+{\textbf{C}}({\underline{h}}_{2})m_{2}+{\textbf{C}}({\underline{h}}_{3})m_{3}+{\textbf{C}}({\underline{h}}_{4})m_{4},$

which is more uniformly distributed in its range than the original polynomial
${\textbf{C}}({\underline{h}})m$.

However, this new polynomial is still not quite as equidistributed as we want.
For instance, if
${\textbf{C}}({\underline{h}})={\mathbf{e}}_{1}h_{1}h_{2}+{\mathbf{e}}_{2}h_{1}$
(as in Example 5.2), then the new polynomial

$\displaystyle{\mathbf{e}}_{1}(h_{11}h_{21}m_{1}+h_{12}h_{22}m_{2}+h_{13}h_{23}m_{3}+h_{14}h_{24}m_{4})$
$\displaystyle+{\mathbf{e}}_{2}(h_{11}m_{1}+h_{12}m_{2}+h_{13}m_{3}+h_{14}m_{4})$

is still not equidistributed in its “natural” range ${\mathbf{e}}_{2}\cdot[\pm
4H^{2}M]+{\mathbf{e}}_{1}\cdot[\pm 4HM]$. The reason is that

$g=\gcd(h_{11}h_{21},h_{12}h_{22},h_{13}h_{23},h_{14}h_{24})$

is quite large for many $h$’s. For example, if $p\ll H^{\Omega(1)}$ is prime,
then $p^{2}|g$ with probability $\approx(3/p^{2}-2/p^{3})^{4}$, which is much
larger than the probability $\approx(1/p^{2})^{4}$ that $p^{2}$ divides the
$\gcd$ of four uniformly random integers of size $\asymp H^{2}$. This means
that the ${\mathbf{e}}_{2}$-coordinate of the polynomial will be a multiple of
$p^{2}$ disproportionately often as the $h$’s and $m$’s range.

To eliminate this arithmetic obstruction in the general setting of Proposition
5.1, we use more applications of the Cauchy–Schwarz inequality to increase the
number of the variables $h_{2i},\ldots,h_{ri}$ and uniformize the polynomial
further; after enough duplications of variables using the Cauchy–Schwarz
inequality, the resulting polynomial will be equidistributed in its natural
range. Writing ${\underline{h}}_{i}=(h_{1i},\tilde{{\underline{h}}}_{i})$, we
now apply the Cauchy–Schwarz inequality twice in x and $h_{1i}$ to obtain

$\operatorname*{\mathbb{E}}_{(h_{i_{1}})_{i_{1}\in[4]}\in[\pm
H]^{4}}\operatorname*{\mathbb{E}}_{(\tilde{{\underline{h}}}_{i_{1}i_{2}})_{i_{1},i_{2}\in[4]}\in[\pm
H]^{16(r-1)}}\sum_{(m_{i_{1}i_{2}})_{i_{1},i_{2}\in[4]}}\mu_{M}((m_{i_{1}i_{2}})_{i_{1},i_{2}})\\\
\sum_{\textbf{x}}f({\textbf{x}})\overline{f\Bigl{(}{\textbf{x}}+\sum_{\begin{subarray}{c}i_{1},i_{2}\in[4]\end{subarray}}{\textbf{C}}(h_{1i_{1}},\tilde{{\underline{h}}}_{i_{1}i_{2}})m_{i_{1}i_{2}}\Bigr{)}}\geq\delta^{16}N^{D}.$

We continue in this manner: Applying the Cauchy–Schwarz inequality twice in
the variables

${\textbf{x}},h_{1i_{1}},h_{2i_{1}i_{2}},\ldots,h_{(l-1)i_{1}\cdots i_{l-1}}$

for each $l=3,4,\ldots,r$ (as in the $l=2$ step just illustrated; the $l=1$
step appeared at the very beginning of the proof), and bounding the Fejér
kernels pointwise, we arrive at the bound

$\operatorname*{\mathbb{E}}_{(h_{1i_{1}})_{i_{1}\in[4]}\in[\pm
H]^{4}}\cdots\operatorname*{\mathbb{E}}_{(h_{ri_{1}\cdots
i_{r}})_{i_{1},\ldots,i_{r}\in[4]}\in[\pm
H]^{4^{r}}}\operatorname*{\mathbb{E}}_{(m_{i_{1}\cdots
i_{r}})_{i_{1},\ldots,i_{r}\in[4]}\in[\pm 2M]^{4^{r}}}\\\
\Bigl{|}\sum_{\textbf{x}}f({\textbf{x}})\overline{f\Bigl{(}{\textbf{x}}+\sum_{\begin{subarray}{c}i_{1},\ldots,i_{r}\in[4]\end{subarray}}{\textbf{C}}(h_{1i_{1}},\ldots,h_{ri_{1}\cdots
i_{r}})m_{i_{1}\cdots i_{r}}\Bigr{)}}\Bigr{|}\gg_{r}\delta^{4^{r}}N^{D}.$

Step 2: Applying the equidistribution properties of the new polynomial.

We have now replaced ${\textbf{C}}({\underline{h}})m$ by the massive
polynomial

(33)
$\sum_{\begin{subarray}{c}i_{1},\ldots,i_{r}\in[4]\end{subarray}}{\textbf{C}}(h_{1i_{1}},\ldots,h_{ri_{1}\cdots
i_{r}})m_{i_{1}\cdots i_{r}}\\\
=\sum_{i_{1},\ldots,i_{r}\in[4]}{\boldsymbol{\gamma}}_{\underline{u}}\sum_{\begin{subarray}{c}i_{1}\in[4]\end{subarray}}h_{1i_{1}}^{u_{1}}\sum_{\begin{subarray}{c}i_{2}\in[4]\end{subarray}}h_{2i_{1}i_{2}}^{u_{2}}\cdots\sum_{\begin{subarray}{c}i_{r}\in[4]\end{subarray}}h_{ri_{1}\cdots
i_{r}}^{u_{r}}m_{i_{1}\cdots i_{r}}.$

For instance, if
${\textbf{C}}({\underline{h}})={\mathbf{e}}_{1}h_{1}h_{2}+{\mathbf{e}}_{2}h_{1}$
(as in Example 5.2), then the polynomial (33) equals

$\displaystyle{\mathbf{e}}_{1}\sum_{i_{1},i_{2}\in[4]}h_{1i_{1}}h_{2i_{1}i_{2}}m_{i_{1}i_{2}}+{\mathbf{e}}_{2}\sum_{i_{1},i_{2}\in[4]}h_{1i_{1}}m_{i_{1}i_{2}}.$

The crucial point is that for a generic choice of $h$’s, the subpolynomials of
(33) corresponding to different ${\underline{u}}$’s are simultaneously well
distributed in their ranges. This result on simultaneous equidistribution is
one of the new inputs of this paper, and we outsource its exact statement and
proof to Proposition 7.5. For now, however, let us briefly explain how this
good distribution property of the polynomial (33) arises from its “multiscale”
structure. For a generic choice of $h_{ri_{1}\cdots i_{r}}$, the polynomial

$\Bigl{(}\sum_{\begin{subarray}{c}i_{r}\in[4]\end{subarray}}m_{i_{1}\cdots
i_{r}},\sum_{\begin{subarray}{c}i_{r}\in[4]\end{subarray}}h_{ri_{1}\cdots
i_{r}}m_{i_{1}\cdots i_{r}}\Bigr{)}$

is well distributed in its range; this allows us to essentially replace both
sums by new variables $t_{i_{1}\cdots i_{r-1}0}$ and $t_{i_{1}\cdots
i_{r-1}1}$ ranging over $[\pm 4M],[\pm 4HM]$ respectively. Then for a generic
choice of $h_{(r-1)i_{1}\cdots i_{r-1}}$, the polynomial

$\displaystyle\Bigl{(}\sum_{i_{r-1}\in[4]}t_{i_{1}\cdots
i_{r-1}0},\sum_{i_{r-1}\in[4]}t_{i_{1}\cdots
i_{r-1}1},\sum_{i_{r-1}\in[4]}h_{(r-1)i_{1}\cdots i_{r-1}}t_{i_{1}\cdots
i_{r-1}0},\sum_{i_{r-1}\in[4]}h_{(r-1)i_{1}\cdots i_{r-1}}t_{i_{1}\cdots
i_{r-1}1}\Bigr{)}$

is well distributed in its range $[\pm 16M]\times[\pm 16HM]\times[\pm
16HM]\times[\pm 16H^{2}M]$, and so on.161616For this to happen, we need for
each $l\in[r]$ to sum over at least $3$ indices $i_{l}$; we sum over $4$ since
the Cauchy–Schwarz inequality doubles the number of variables each time.
Because of this iterative scheme, it suffices to to show that (33) is well
distributed in its range for $r=1$, and this can be accomplished using
elementary counting arguments.

For $l\in[r]$ and $\eta>0$, define the set

${\mathcal{H}}_{l,\eta}=\\{(h_{li_{1}\cdots
i_{l}})_{i_{1},\ldots,i_{l}\in[4]}\in[\pm H]^{4^{l}}:\;|h_{li_{1}\cdots
i_{l}}-h_{li^{\prime\prime}_{1}\cdots i^{\prime\prime}_{l}}|\geq\eta H,\\\
\gcd(h_{li_{1}\cdots i_{l}}-h_{li^{\prime\prime}_{1}\cdots
i^{\prime\prime}_{l}},h_{li^{\prime}_{1}\cdots
i^{\prime}_{l}}-h_{li^{\prime\prime}_{1}\cdots
i^{\prime\prime}_{l}})\leq\eta^{-1}\\\ \textrm{for {all}
distinct}\;(i_{1},\ldots,i_{l}),\;(i^{\prime}_{1},\ldots,i^{\prime}_{l}),\;(i^{\prime\prime}_{1},\ldots,i^{\prime\prime}_{l})\in[4]^{l}\\}.$

This is a set of tuples $(h_{li_{1}\cdots i_{l}})_{i_{1},\ldots,i_{l}}$ whose
coordinates are not too close to each other and do not have large common
factors. It is not difficult to show that for a small $\eta>0$, a generic
tuple in $[\pm H]^{4^{l}}$ belongs to this set. Indeed, taking
${\mathcal{H}}_{l}:={\mathcal{H}}_{l,c\delta^{1/c}}$ for sufficiently small
$c=c(r)>0$, we have by Lemma 7.8 that all but a
$O_{r}(\delta^{4^{r}})$-proportion of the elements of $[\pm H]^{4^{l}}$ lie in
${\mathcal{H}}_{l}$, and hence

$\operatorname*{\mathbb{E}}_{(h_{1i_{1}})_{i_{1}\in[4]}\in[\pm
H]^{4}}\cdots\operatorname*{\mathbb{E}}_{(h_{ri_{1}\cdots
i_{r}})_{i_{1},\ldots,i_{r}\in[4]}\in[\pm
H]^{4^{r}}}\operatorname*{\mathbb{E}}_{(m_{i_{1}\cdots
i_{r}})_{i_{1},\ldots,i_{r}\in[4]}\in[\pm 2M]^{4^{r}}}\\\
\prod_{l\in[r]}\mathbf{1}_{{\mathcal{H}}_{l}(h_{(li_{1}\cdots
i_{l})_{i_{1},\ldots,i_{l}}})}\cdot\Bigl{|}\sum_{\textbf{x}}f({\textbf{x}})\overline{f\Bigl{(}{\textbf{x}}+\sum_{\begin{subarray}{c}i_{1},\ldots,i_{r}\in[4]\end{subarray}}{\textbf{C}}(h_{1i_{1}},\ldots,h_{ri_{1}\cdots
i_{r}})m_{i_{1}\cdots i_{r}}\Bigr{)}}\Bigr{|}\gg_{r}\delta^{4^{r}}N^{D}.$

We have thus excluded the $h^{\prime}s$ whose coefficients are close to each
other or have large common factors.

For $(n_{\underline{u}})_{\underline{u}}\in{\mathbb{Z}}^{2^{r}}$, let

${\mathcal{N}}((n_{\underline{u}})_{{\underline{u}}})=\operatorname*{\mathbb{E}}_{(h_{1i_{1}})_{i_{1}\in[4]}\in[\pm
H]^{4}}\cdots\operatorname*{\mathbb{E}}_{(h_{ri_{1}\cdots
i_{r}})_{i_{1},\ldots,i_{r}\in[4]}\in[\pm
H]^{4^{r}}}\operatorname*{\mathbb{E}}_{(m_{i_{1}\cdots
i_{r}})_{i_{1},\ldots,i_{r}\in[4]}\in[\pm 2M]^{4^{r}}}\\\
\prod_{l\in[r]}\mathbf{1}_{{\mathcal{H}}_{l}((h_{li_{1}\cdots
i_{l}})_{i_{1},\ldots,i_{l}})}\cdot\prod_{{\underline{u}}\in\\{0,1\\}^{r}}\mathbf{1}\Bigl{(}\sum_{\begin{subarray}{c}i_{1}\in[4]\end{subarray}}h_{1i_{1}}^{u_{1}}\cdots\sum_{\begin{subarray}{c}i_{r}\in[4]\end{subarray}}h_{ri_{1}\cdots
i_{r}}^{u_{r}}m_{i_{1}\cdots i_{r}}=n_{\underline{u}}\Bigr{)},$

so that

(34)
$\displaystyle\sum_{(n_{\underline{u}})_{\underline{u}}}{\mathcal{N}}((n_{\underline{u}})_{\underline{u}})\cdot\Bigl{|}\sum_{\textbf{x}}f({\textbf{x}})\overline{f\Bigl{(}{\textbf{x}}+\sum_{{\underline{u}}\in\\{0,1\\}^{r}}{\boldsymbol{\gamma}}_{\underline{u}}n_{\underline{u}}\Bigr{)}}\Bigr{|}\gg_{r}\delta^{4^{r}}N^{D}.$

The quantity ${\mathcal{N}}((n_{\underline{u}}))$ is the normalized count of
$\mathopen{}\left({\underline{h}}_{1i_{1}},\ldots,{\underline{h}}_{ri_{1}\cdots
i_{r}},{\underline{m}}_{i_{1}\cdots i_{r}}\mathclose{}\right)$ such that for
each ${\underline{u}}\in\\{0,1\\}^{r}$, the subpolynomial associated with
${\boldsymbol{\gamma}}_{\underline{u}}$ in (33) equals $n_{\underline{u}}$.
The key equidistribution result on the polynomial (33) is the assertion that
the normalised count ${\mathcal{N}}$ satisfies the pointwise bound

(35)
$\displaystyle{\mathcal{N}}((n_{\underline{u}})_{\underline{u}})\ll_{r}\delta^{-O_{r}(1)}M^{-2^{r}}H^{-r2^{r-1}}.$

This bound is a special case of Proposition 7.5 to be derived later on.

Let us explain why the bound (35) is of the right order of magnitude. Note
first that ${\mathcal{N}}((n_{\underline{u}})_{\underline{u}})=0$ unless each
$|n_{\underline{u}}|\leq C_{\underline{u}}H^{|{\underline{u}}|}M$ for some
$C_{\underline{u}}>0$. Defining

$\displaystyle
E_{0}=\left\\{(n_{\underline{u}})_{{\underline{u}}\in\\{0,1\\}^{r}}:\;n_{\underline{u}}\in[-C_{\underline{u}}H^{|{\underline{u}}|}M,C_{\underline{u}}H^{|{\underline{u}}|}M],\;{\underline{u}}\in\\{0,1\\}^{r}\right\\},$

we observe that

$\displaystyle|E_{0}|\asymp_{r}\prod_{{\underline{u}}\in\\{0,1\\}^{r}}(H^{|{\underline{u}}|}M)=M^{2^{r}}H^{r2^{r-1}}$

and note that the exponents agree with those in (35). Combining these
observations with (34) and (35), we get

$\displaystyle\operatorname*{\mathbb{E}}_{(n_{\underline{u}})_{\underline{u}}\in
E_{0}}\Bigl{|}\sum_{\textbf{x}}f({\textbf{x}})\overline{f\Bigl{(}{\textbf{x}}+\sum_{{\underline{u}}\in\\{0,1\\}^{r}}{\boldsymbol{\gamma}}_{\underline{u}}n_{\underline{u}}\Bigr{)}}\Bigr{|}\gg_{r}\delta^{O_{r}(1)}N^{D}.$

Defining

$\displaystyle
E_{1}=\sum_{{\underline{u}}\in\\{0,1\\}^{r}}{\boldsymbol{\gamma}}_{\underline{u}}\cdot[\pm
C_{\underline{u}}H^{|{\underline{u}}|}M],$

we have

$\displaystyle\operatorname*{\mathbb{E}}_{{\mathbf{n}}\in
E_{1}}\Bigl{|}\sum_{\textbf{x}}f({\textbf{x}})\overline{f\mathopen{}\left({\textbf{x}}+{\mathbf{n}}\mathclose{}\right)}\Bigr{|}\gg_{r}\delta^{O_{r}(1)}N^{D}.$

Using the Cauchy–Schwarz inequality to remove the absolute value and recalling
that $f$ is supported on $[N]^{D}$, we obtain

$\operatorname*{\mathbb{E}}_{{\mathbf{n}}\in
E_{1}}\operatorname*{\mathbb{E}}_{{\mathbf{s}}\in[\pm
N]^{D}}\sum_{\textbf{x}}f({\textbf{x}})\overline{f({\textbf{x}}+{\mathbf{s}})f({\textbf{x}}+{\mathbf{n}})}f({\textbf{x}}+{\mathbf{s}}+{\mathbf{n}})\gg_{r}\delta^{O_{r}(1)}N^{D}.$

Two further applications of the Cauchy–Schwarz inequality to double
${\mathbf{n}},{\mathbf{s}}$ let us introduce Fejér kernels, and we get

$\left\|f\right\|^{4}_{E_{1},[\pm N]^{D}}\gg_{r}\delta^{O_{r}(1)}N^{D}.$

To conclude the proof, we use Lemma 3.5(vi) to replace $E_{1}$ by $E$.

##  6\. Concatenation of averages of higher-degree seminorms

In the previous section, we showed how to concatenate an average of degree-$1$
box norms with polynomial directions. The argument becomes significantly more
complicated when we deal with higher-degree box norms. In the degree-$1$
setting, applying the Cauchy–Schwarz inequality (as in the proof of
Proposition 5.1) did not cause the degree of the box norm to increase. This
pleasant property ceases to hold in the setting of higher-degree box norms;
rather, each application of the Cauchy–Schwarz and Gowers-Cauchy–Schwarz
Inequalities will involve passing to norms of much higher degree. The
objective of the present section is to carry out this higher-degree argument.
As noted in the proof outline, this stage of the concatenation arguments works
for any box norms, not necessarily those that come out of PET and involve
polynomials. To emphasize the robustness of this part of the concatenation
argument, we phrase the results in this section in a more abstract setting of
an average of box norms on an arbitrary finitely generated abelian group $G$.
We will thus deal with expressions of the form

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

where $I$ is a finite indexing set and $H_{1i},\ldots,H_{si}\subseteq G$ are
finite nonempty multisets for each $i\in I$. In our applications, the set $I$
will be ${\underline{h}}\in[\pm H]^{r}$, and the multisets
$H_{1i},\ldots,H_{si}$ for $i\in I$ will be the sets

${\textbf{C}}_{1}({\underline{h}})\cdot[\pm
M],\ldots,{\textbf{C}}_{s}({\underline{h}})\cdot[\pm M]$

for ${\underline{h}}\in[\pm H]^{r}$.

The following lemma will serve as the basis for the concatenation argument.

######  Lemma 6.1.

Let $A,\delta>0$, let $s\in{\mathbb{N}}$, let $G$ be a finitely generated
abelian group, let $I$ be a finite indexing set, and let
$H_{i},K_{1i},\ldots,K_{si}\subseteq G$ be finite multisets for each $i\in I$.
Suppose that $B\subseteq G$ is a set satisfying

$\displaystyle|\operatorname{supp}(B+B-B)|\leq A|B|.$

Then for all $1$-bounded functions $f$ supported on $B$, the bound

$\displaystyle{\operatorname*{\mathbb{E}}_{i\in
I}\left\|f\right\|_{H_{i},K_{1i},\ldots,K_{si}}^{2^{s+1}}}\geq\delta|B|$

implies that

$\displaystyle\operatorname*{\mathbb{E}}_{i_{0},i_{1}\in
I}\left\|f\right\|_{K_{1i_{0}},\ldots,K_{si_{0}},K_{1i_{1}},\ldots,K_{si_{1}},H_{i_{1}}-H_{i_{0}}}^{2^{2s+1}}\gg_{A,s}\delta^{2^{2s+1}}|B|.$

In applications, we will take $B=[N]^{D}$ and $A=3^{D}$ since

$\operatorname{supp}(B+B-B)=[2-N,2N-1]^{D}.$

###### Proof.

Let $K_{i}:=K_{1i}\times\cdots\times K_{si}$. The alternative formula (17) for
box norms yields

$\displaystyle\operatorname*{\mathbb{E}}_{i\in
I}\sum_{x}\sum_{\begin{subarray}{c}{\underline{k}}\in
K_{i}\end{subarray}}\sum_{h\in
H_{i}}\mu_{K_{i}}({\underline{k}})\mu_{H_{i}}(h)\Delta_{{\underline{k}},h}f(x)\geq\delta|B|.$

We expand

$\displaystyle\Delta_{{\underline{k}},h}f(x)=f(x)\overline{f(x+h)}\Delta_{{\underline{k}}}^{*}\Delta_{h}f(x),$

where
$\Delta_{{\underline{k}}}^{*}f(x)=\prod_{{\underline{\epsilon}}\in\\{0,1\\}^{s}\setminus\\{0\\}}{\mathcal{C}}^{|{\underline{\epsilon}}|}f(x+{\underline{\epsilon}}\cdot{\underline{k}})$,
and change the order of summation to get

$\displaystyle\sum_{x}f(x)\operatorname*{\mathbb{E}}_{i\in
I}\sum_{\begin{subarray}{c}{\underline{k}}\in K_{i}\end{subarray}}\sum_{h\in
H_{i}}\mu_{K_{i}}({\underline{k}})\mu_{H_{i}}(h)\overline{f(x+h)}\Delta^{*}_{{\underline{k}}}\Delta_{h}f(x)\geq\delta|B|.$

An application of the Cauchy–Schwarz inequality in $x$ gives

$\displaystyle\sum_{x}\operatorname*{\mathbb{E}}_{i_{0},i_{1}\in
I}\sum_{\begin{subarray}{c}{\underline{k}}_{0}\in K_{i_{0}},\\\
{\underline{k}}_{1},\in
K_{i_{1}}\end{subarray}}\sum_{\begin{subarray}{c}h_{0}\in H_{i_{0}},\\\
h_{1}\in
H_{i_{1}}\end{subarray}}\mu_{K_{i_{0}}}({\underline{k}}_{0})\mu_{K_{i_{1}}}({\underline{k}}_{1})\mu_{H_{i_{0}}}(h_{0})\mu_{H_{i_{1}}}(h_{1})\overline{f(x+h_{0})}f(x+h_{1})$
$\displaystyle\Delta^{*}_{{\underline{k}}_{0}}\Delta_{h_{0}}f(x)\overline{\Delta^{*}_{{\underline{k}}_{1}}\Delta_{h_{1}}f(x)}\geq\delta^{2}|B|.$

We crucially observe that for each fixed $i_{0},i_{1}\in I$ and $h_{0}\in
H_{i_{0}},h_{1}\in H_{i_{1}}$, the average

(36) $\displaystyle\sum_{x}\sum_{\begin{subarray}{c}{\underline{k}}_{0}\in
K_{i_{0}},\\\ {\underline{k}}_{1},\in
K_{i_{1}}\end{subarray}}\mu_{K_{i_{0}}}({\underline{k}}_{0})\mu_{K_{i_{1}}}({\underline{k}}_{1})f(x+h_{0})\overline{f(x+h_{1})}\Delta^{*}_{{\underline{k}}_{0}}\Delta_{h_{0}}f(x)\overline{\Delta^{*}_{{\underline{k}}_{1}}\Delta_{h_{1}}f(x)}$

is a box inner product of $1$-bounded functions along
$K_{1i_{0}},\ldots,K_{si_{0}},K_{1i_{1}},\ldots,K_{si_{1}}$, with
$f(x+h_{0})\overline{f(x+h_{1})}$ being the term with multi-index
$\underline{0}$. Moreover, since $f$ is supported on $B$, the summand in (36)
vanishes unless

$\displaystyle
x+h_{j},\;x+{\underline{\epsilon}}_{j}\cdot{\underline{k}}_{j},\;x+{\underline{\epsilon}}_{j}\cdot{\underline{k}}_{j}+h_{j}\in
B\quad\textrm{for all}\quad
j\in\\{0,1\\},\;{\underline{\epsilon}}_{j}\neq\underline{0}.$

In particular, if all of these elements lie in $B$, then we also have

$x+{\underline{\epsilon}}_{0}\cdot{\underline{k}}_{0}+{\underline{\epsilon}}_{1}\cdot{\underline{k}}_{1}+h_{0}=(x+{\underline{\epsilon}}_{0}\cdot{\underline{k}}_{0}+h_{0})+(x+{\underline{\epsilon}}_{1}\cdot{\underline{k}}_{1}+h_{1})-(x+h_{1})\in
B+B-B$

for any
${\underline{\epsilon}}_{0},{\underline{\epsilon}}_{1}\in\\{0,1\\}^{s}\setminus{\\{0\\}}$,
and so we can introduce the term

(37)
$\displaystyle\prod_{\begin{subarray}{c}{\underline{\epsilon}}_{0},{\underline{\epsilon}}_{1}\in\\{0,1\\}^{s}\setminus{\\{0\\}}\end{subarray}}\mathbf{1}_{B+B-B-
h_{0}}(x+{\underline{\epsilon}}_{0}\cdot{\underline{k}}_{0}+{\underline{\epsilon}}_{1}\cdot{\underline{k}}_{1})$

into (36) without changing the value of the expression. The purpose of
inserting this term is to ensure that if we view (36) as an inner product
along $K_{1i_{0}},\ldots,K_{si_{0}},K_{1i_{1}},\ldots,K_{si_{1}}$, then the
functions evaluated at
$x+{\underline{\epsilon}}_{0}\cdot{\underline{k}}_{0}+{\underline{\epsilon}}_{1}\cdot{\underline{k}}_{1}$
with ${\underline{\epsilon}}_{0},{\underline{\epsilon}}_{1}\neq\underline{0}$
have support of size bounded by $|\operatorname{supp}(B+B-B)|$, and hence by
$A|B|$ by our assumption.

We now apply the Gowers-Cauchy–Schwarz inequality to (36) twisted by the
product (37) to obtain

$\displaystyle\operatorname*{\mathbb{E}}_{i_{0},i_{1}\in
I}\sum_{x}\sum_{\begin{subarray}{c}{\underline{k}}_{0}\in K_{i_{0}},\\\
{\underline{k}}_{1}\in
K_{i_{1}}\end{subarray}}\mu_{K_{i_{0}}}({\underline{k}}_{0})\mu_{K_{i_{1}}}({\underline{k}}_{1})\operatorname*{\mathbb{E}}_{\begin{subarray}{c}h_{0}\in
H_{i_{0}},\\\ h_{1},\in
H_{i_{1}}\end{subarray}}\Delta_{{\underline{k}}_{0},{\underline{k}}_{1}}(f(x+h_{0})\overline{f(x+h_{1})})\gg_{A,s}\delta^{2^{2s+1}}|B|,$

or equivalently

$\displaystyle\operatorname*{\mathbb{E}}_{i_{0},i_{1}\in
I}\sum_{x}\operatorname*{\mathbb{E}}_{\begin{subarray}{c}{\underline{k}}_{0},{\underline{k}}^{\prime}_{0}\in
K_{i_{0}},\\\ {\underline{k}}_{1},{\underline{k}}^{\prime}_{1}\in
K_{i_{1}}\end{subarray}}\operatorname*{\mathbb{E}}_{\begin{subarray}{c}h_{0}\in
H_{i_{0}},\\\ h_{1},\in
H_{i_{1}}\end{subarray}}\Delta^{\prime}_{({\underline{k}}_{0},{\underline{k}}_{0}^{\prime}),({\underline{k}}_{1},{\underline{k}}_{1}^{\prime})}(f(x)\overline{f(x+h_{1}-h_{0})})\gg_{A,s}\delta^{2^{2s+1}}|B|$

after we expand the kernels $\mu_{K_{i_{0}}},\mu_{K_{i_{1}}}$ and change
variables $x\mapsto x-h_{0}$. Using the Cauchy–Schwarz inequality to double
the variables $h_{0},h_{1}$ yields

$\displaystyle\operatorname*{\mathbb{E}}_{i_{0},i_{1}\in
I}\sum_{x}\operatorname*{\mathbb{E}}_{\begin{subarray}{c}{\underline{k}}_{0},{\underline{k}}^{\prime}_{0}\in
K_{i_{0}},\\\ {\underline{k}}_{1},{\underline{k}}^{\prime}_{1}\in
K_{i_{1}}\end{subarray}}\operatorname*{\mathbb{E}}_{\begin{subarray}{c}h_{0},h_{0}^{\prime}\in
H_{i_{0}},\\\ h_{1},h_{1}^{\prime}\in
H_{i_{1}}\end{subarray}}\Delta^{\prime}_{({\underline{k}}_{0},{\underline{k}}_{0}^{\prime}),({\underline{k}}_{1},{\underline{k}}_{1}^{\prime}),(h_{1}-h_{0},h_{1}^{\prime}-h_{0}^{\prime})}f(x)\gg_{A,s}\delta^{2^{2s+2}}|B|.$

This expression is now an average (indexed by $i_{0},i_{1}$) of box norms
along $K_{i_{0}},K_{i_{1}},H_{i_{1}}-H_{i_{0}}$. The inductive formula for box
norms gives the claimed bound

$\displaystyle\operatorname*{\mathbb{E}}_{i_{0},i_{1}\in
I}\left\|f\right\|_{K_{1i_{0}},\ldots,K_{si_{0}},K_{1i_{1}},\ldots,K_{si_{1}},H_{i_{1}}-H_{i_{0}}}^{2^{2s+1}}\gg_{A,s}\delta^{2^{2s+2}}|B|.$

We reiterate our convention that $H_{i_{1}}-H_{i_{0}}$ denotes the Minkowski
sum counted with multiplicity and in particular is itself a multiset. ∎

By repeatedly applying Lemma 6.1, we derive the following concatenation
result, whose proof follows closely that of [16, Proposition 2.3].

######  Proposition 6.2 (Concatenation of box norms, version I).

Let $A,\delta>0$, let $s\in{\mathbb{N}}$, let $G$ be a finitely generated
abelian group, let $I$ be a finite indexing set, and let
$H_{1i},\ldots,H_{si}\subseteq G$ be finite multisets for each $i\in I$.
Suppose that $B\subseteq G$ is a set satisfying

$\displaystyle|\operatorname{supp}(B+B-B)|\leq A|B|.$

Then for all $1$-bounded functions $f$ supported on $B$, the bound

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

implies that

$\displaystyle\operatorname*{\mathbb{E}}_{\begin{subarray}{c}i_{\underline{\epsilon}}\in
I,\\\
{\underline{\epsilon}}\in\\{0,1\\}^{s}\end{subarray}}\left\|f\right\|_{\begin{subarray}{c}\\{H_{ji_{\underline{\epsilon}}}-H_{ji_{{\underline{\epsilon}}^{\prime}}}:\
j\in[s]\
{\underline{\epsilon}},{\underline{\epsilon}}^{\prime}\in\\{0,1\\}^{s}\\\
\mathrm{with}\
(\epsilon_{1},\ldots,\epsilon_{s-j})=(\epsilon^{\prime}_{1},\ldots,\epsilon^{\prime}_{s-j}),\
\epsilon_{s+1-j}=1,\
\epsilon^{\prime}_{s+1-j}=0\\}\end{subarray}}^{2^{d}}\gg_{A,s}\delta^{O_{s}(1)}|B|,$

where $d$ is the degree of the box norms on the left-hand side.

Since the indices ${\underline{\epsilon}},{\underline{\epsilon}}^{\prime}$ are
always distinct, the multiset
$H_{ji_{\underline{\epsilon}}}-H_{ji_{{\underline{\epsilon}}^{\prime}}}$ is
usually more uniformly distributed than both of the multisets
$H_{ji_{\underline{\epsilon}}},H_{ji_{{\underline{\epsilon}}^{\prime}}}$.

###### Proof.

The proof of Proposition 6.2 relies on a gradual concatenation of the
“unconcatenated” multisets $H_{1i},\ldots,H_{si}$ using Lemma 6.1. We
repeatedly use the inductive formula for box norms in order to reinterpret the
average in such a way that successive applications of Lemma 6.1 concatenate
the multisets $H_{1i},\ldots,H_{si}$ one by one.

Starting with (38), we apply Lemma 6.1 to bound

(39) $\displaystyle\operatorname*{\mathbb{E}}_{i_{0},i_{1}\in
I}\left\|f\right\|_{H_{1i_{0}},\ldots,H_{(s-1)i_{0}},H_{1i_{1}},\ldots,H_{(s-1)i_{1}},H_{si_{1}}-H_{si_{0}}}^{2^{2s-1}}\gg_{A,s}\delta^{O_{s}(1)}|B|.$

Instead of having $s$ unconcatenated multisets indexed by $i$, we now have
$s-1$ unconcatenated multisets indexed by $i_{0}$ and another $s-1$
unconcatenated multisets indexed by $i_{1}$, together with the concatenated
multiset $H_{si_{1}}-H_{si_{0}}$. Even though the total number of multisets
has nearly doubled, we have made progress because the number of unconcatenated
multisets for each index $i_{0},i_{1}$ decreased by $1$.

At the next stage of the argument, we will apply Lemma 6.1 twice to
concatenate $H_{(s-1)i_{0}}$ and then $H_{(s-1)i_{1}}$. As a consequence, the
two indices $i_{0},i_{1}$ will be replaced by four indices
$i_{00},i_{01},i_{10},i_{11}$, and for each of them we will have exactly $s-2$
unconcatenated multisets. We will continue in this manner: At each stage, the
number of indices $i_{\underline{\epsilon}}$ will double, but the number of
unconcatenated multisets with each index $i_{\underline{\epsilon}}$ will
decrease by $1$. Eventually, after $s$ steps, we will be left with $2^{s-1}$
unconcatenated multisets $H_{1i_{\underline{\epsilon}}}$, and $2^{s-1}$
applications of Lemma 6.1 will allow us to concatenate them all without
producing any new unconcatenated multisets. This will finish the argument.

To illustrate this general strategy, let us see in detail what happens at the
second stage, i.e., after we have obtained the bound (39). Using the induction
formula for box norms, we can express (39) as

$\operatorname*{\mathbb{E}}_{i_{1}\in
I}\operatorname*{\mathbb{E}}_{\begin{subarray}{c}h_{1i_{1}},h_{1i_{1}}^{\prime}\in
H_{1i_{1}}\end{subarray}}\cdots\operatorname*{\mathbb{E}}_{\begin{subarray}{c}h_{(s-1)i_{1}},h_{(s-1)i_{1}}^{\prime}\in
H_{(s-1)i_{1}}\end{subarray}}\\\ \operatorname*{\mathbb{E}}_{i_{0}\in
I}\left\|\Delta^{\prime}_{(h_{1i_{1}},h_{1i_{1}}^{\prime}),\ldots,(h_{(s-1)i_{1}},h_{(s-1)i_{1}}^{\prime})}f\right\|_{H_{1i_{0}},\ldots,H_{(s-1)i_{0}},H_{si_{1}}-H_{si_{0}}}^{2^{s}}\gg_{A,s}\delta^{O_{s}(1)}|B|.$

For each fixed
$i_{1},h_{1i_{1}},h_{1i_{1}}^{\prime},\ldots,h_{(s-1)i_{1}},h_{(s-1)i_{1}}^{\prime}$,
we apply Lemma 6.1 separately to each average over $i_{0}$, obtaining

$\operatorname*{\mathbb{E}}_{i_{1}\in
I}\operatorname*{\mathbb{E}}_{\begin{subarray}{c}h_{1i_{1}},h_{1i_{1}}^{\prime}\in
H_{1i_{1}}\end{subarray}}\cdots\operatorname*{\mathbb{E}}_{\begin{subarray}{c}h_{(s-1)i_{1}},h_{(s-1)i_{1}}^{\prime}\in
H_{(s-1)i_{1}}\end{subarray}}\operatorname*{\mathbb{E}}_{i_{00},i_{01}\in
I}\\\
\left\|\Delta^{\prime}_{(h_{1i_{1}},h_{1i_{1}}^{\prime}),\ldots,(h_{(s-1)i_{1}},h_{(s-1)i_{1}}^{\prime})}f\right\|_{\begin{subarray}{c}H_{1i_{00}},\ldots,H_{(s-2)i_{00}},H_{1i_{01}},\ldots,H_{(s-2)i_{01}},\\\
H_{(s-1)i_{01}}-H_{(s-1)i_{00}},H_{si_{1}}-H_{si_{00}},H_{si_{1}}-H_{si_{01}}\end{subarray}}^{2^{2s-1}}\gg_{A,s}\delta^{O_{s}(1)}|B|.$

Using the inductive formula for box norms and swapping the indices of
$\Delta^{\prime}$ and the box norm, we can rearrange this to get

$\operatorname*{\mathbb{E}}_{i_{00},i_{01}\in
I}\operatorname*{\mathbb{E}}_{\begin{subarray}{c}h_{1i_{00}},h_{1i_{00}}^{\prime}\in
H_{1i_{00}},\\\ h_{1i_{01}},h_{1i_{01}}^{\prime}\in
H_{1i_{01}}\end{subarray}}\cdots\operatorname*{\mathbb{E}}_{\begin{subarray}{c}h_{(s-1)i_{00}},h_{(s-1)i_{00}}^{\prime}\in
H_{(s-1)i_{00}},\\\ h_{(s-1)i_{01}},h_{(s-1)i_{01}}^{\prime}\in
H_{(s-1)i_{01}}\end{subarray}}\\\ \operatorname*{\mathbb{E}}_{i_{1}\in
I}\left\|\Delta^{\prime}_{\begin{subarray}{c}(h_{1i_{00}},h_{1i_{00}}^{\prime}),\ldots,(h_{(s-2)i_{00}},h_{(s-2)i_{00}}^{\prime})\\\
(h_{1i_{01}},h_{1i_{01}}^{\prime}),\ldots,(h_{(s-2)i_{01}},h_{(s-2)i_{01}}^{\prime}),\\\
(h_{(s-1)i_{01}}-h_{(s-1)i_{00}},h^{\prime}_{(s-1)i_{01}}-h^{\prime}_{(s-1)i_{00}})\end{subarray}}f\right\|_{\begin{subarray}{c}H_{1i_{1}},\ldots,H_{(s-1)i_{1}},\\\
H_{si_{1}}-H_{si_{00}},H_{si_{1}}-H_{si_{01}}\end{subarray}}^{2^{s+1}}\gg_{A,s}\delta^{O_{s}(1)}|B|.$

By Lemma 6.1 applied separately to each average over $i_{1}\in I$, we have

$\operatorname*{\mathbb{E}}_{\begin{subarray}{c}i_{00},i_{01},\\\
i_{10},i_{11}\in
I\end{subarray}}\operatorname*{\mathbb{E}}_{\begin{subarray}{c}h_{1i_{00}},h_{1i_{00}}^{\prime}\in
H_{1i_{00}},\\\ h_{1i_{01}},h_{1i_{01}}^{\prime}\in
H_{1i_{01}}\end{subarray}}\cdots\operatorname*{\mathbb{E}}_{\begin{subarray}{c}h_{(s-1)i_{00}},h_{(s-1)i_{00}}^{\prime}\in
H_{(s-1)i_{00}},\\\ h_{(s-1)i_{01}},h_{(s-1)i_{01}}^{\prime}\in
H_{(s-1)i_{01}}\end{subarray}}\\\
\left\|\Delta^{\prime}_{\begin{subarray}{c}(h_{1i_{00}},h_{1i_{00}}^{\prime}),\ldots,(h_{(s-2)i_{00}},h_{(s-2)i_{00}}^{\prime})\\\
(h_{1i_{01}},h_{1i_{01}}^{\prime}),\ldots,(h_{(s-2),i_{01}},h_{(s-2),i_{01}}^{\prime}),\\\
(h_{(s-1)i_{01}}-h_{(s-1)i_{00}},h^{\prime}_{(s-1)i_{01}}-h^{\prime}_{(s-1)i_{00}})\end{subarray}}f\right\|_{\begin{subarray}{c}H_{1i_{10}},\ldots,H_{(s-2)i_{10}},H_{1i_{11}},\ldots,H_{(s-2)i_{11}},\\\
H_{(s-1)i_{11}}-H_{(s-1)i_{10}},H_{si_{10}}-H_{si_{00}},H_{si_{11}}-H_{si_{00}},\\\
H_{si_{10}}-H_{si_{01}},H_{si_{11}}-H_{si_{01}}\end{subarray}}^{2^{2s+1}}\\\
\gg_{A,s}\delta^{O_{s}(1)}|B|.$

Another application of the inductive formula for box norms lets us write this
as

$\displaystyle\operatorname*{\mathbb{E}}_{\begin{subarray}{c}i_{00},i_{01},\\\
i_{10},i_{11}\in
I\end{subarray}}\left\|f\right\|_{\begin{subarray}{c}H_{1i_{00}},\ldots,H_{(s-2)i_{00}},H_{1i_{01}},\ldots,H_{(s-2)i_{01}},\\\
H_{1i_{10}},\ldots,H_{(s-2)i_{10}},H_{1i_{11}},\ldots,H_{(s-2)i_{11}},\\\
H_{(s-1)i_{01}}-H_{(s-1)i_{00}},H_{(s-1)i_{11}}-H_{(s-1)i_{10}},\\\
H_{si_{10}}-H_{si_{00}},H_{si_{11}}-H_{si_{00}},\\\
H_{si_{10}}-H_{si_{01}},H_{si_{11}}-H_{si_{01}}\end{subarray}}^{2^{4s-2}}\gg_{A,s}\delta^{O_{s}(1)}|B|,$

which can be expressed more compactly as

$\displaystyle\operatorname*{\mathbb{E}}_{\begin{subarray}{c}i_{00},i_{01},\\\
i_{10},i_{11}\in
I\end{subarray}}\left\|f\right\|_{\begin{subarray}{c}\\{H_{ji_{\underline{\epsilon}}}:\
{\underline{\epsilon}}\in\\{0,1\\}^{2},\ j=1,\ldots,s-2\\},\\\
\\{H_{(s-1)i_{\underline{\epsilon}}}-H_{(s-1)i_{{\underline{\epsilon}}^{\prime}}}:\
{\underline{\epsilon}},{\underline{\epsilon}}^{\prime}\in\\{0,1\\}^{2}\
\mathrm{with}\ \epsilon_{1}=\epsilon^{\prime}_{1},\ \epsilon_{2}=1,\
\epsilon^{\prime}_{2}=0\\},\\\
\\{H_{si_{\underline{\epsilon}}}-H_{si_{{\underline{\epsilon}}^{\prime}}}:\
{\underline{\epsilon}},{\underline{\epsilon}}^{\prime}\in\\{0,1\\}^{2}\
\mathrm{with}\ \epsilon_{1}=1,\
\epsilon^{\prime}_{1}=0\\}\end{subarray}}^{2^{4s-2}}\gg_{A,s}\delta^{O_{s}(1)}|B|.$

We have thus successfully concatenated all of the multisets
$H_{(s-1)i_{\underline{\epsilon}}}$ and $H_{si_{\underline{\epsilon}}}$.

At the next stage, we concatenate the multisets
$H_{(s-2)i_{\underline{\epsilon}}}$. Applying Lemma 6.1 and the induction
formula for box norms four times (as in the previous stage), each time to an
average over $i_{00},i_{01},i_{10},i_{11}$ (respectively), we arrive at the
inequality

$\displaystyle\operatorname*{\mathbb{E}}_{\begin{subarray}{c}i_{{\underline{\epsilon}}}\in
I,\\\
{\underline{\epsilon}}\in\\{0,1\\}^{3}\end{subarray}}\left\|f\right\|_{\begin{subarray}{c}\\{H_{ji_{\underline{\epsilon}}}:\
{\underline{\epsilon}}\in\\{0,1\\}^{3},\ j=1,\ldots,s-3\\},\\\
\\{H_{ji_{\underline{\epsilon}}}-H_{ji_{{\underline{\epsilon}}^{\prime}}}:\
j=s-2,s-1,s,\
{\underline{\epsilon}},{\underline{\epsilon}}^{\prime}\in\\{0,1\\}^{3}\\\
\mathrm{with}\
(\epsilon_{1},\ldots,\epsilon_{s-j})=(\epsilon^{\prime}_{1},\ldots,\epsilon^{\prime}_{s-j}),\
\epsilon_{s+1-j}=1,\
\epsilon^{\prime}_{s+1-j}=0\\}\end{subarray}}^{2^{d^{\prime}}}\gg_{A,s}\delta^{O_{s}(1)}|B|,$

where $d^{\prime}$ is the degree of the box norms on the left-hand side. This
time, we have successfully concatenated the multisets
$H_{(s-2)i_{\underline{\epsilon}}}$. At the next step, eight applications of
Lemma 6.1 and the induction formula for box norms allow us to concatenate
multisets $H_{(s-3)i_{\underline{\epsilon}}}$. Continuing the argument in this
manner, we arrive at the conclusion of the proposition after a total of

$\displaystyle 1+2+2^{2}+\cdots+2^{s-1}=2^{s}-1$

applications of Lemma 6.1 and the induction formula for box norms. ∎

We now present two corollaries of Proposition 6.2 which are better suited for
applications in ${\mathbb{Z}}^{D}$. In what follows, we order the set
$\\{0,1\\}^{s}$ lexicographically. Identifying $\\{0,1\\}^{s}$ with $[2^{s}]$,
we obtain the following corollary.

######  Corollary 6.3 (Concatenation of box norms, version II).

Let $A,D,s,N\in{\mathbb{N}}$, let $I$ be a finite indexing set, and let
$H_{ji}\subseteq[\pm AN]^{D}$ be finite nonempty multisets for each $i\in I$
and $j\in[s]$. Then for all $1$-bounded functions
$f:{\mathbb{Z}}^{D}\to{\mathbb{C}}$ supported on $[N]^{D}$, the bound

$\displaystyle\operatorname*{\mathbb{E}}_{i\in
I}\left\|f\right\|_{H_{1i},\ldots,H_{si}}^{2^{s}}\geq\delta N^{D}$

implies that

(40)
$\displaystyle\operatorname*{\mathbb{E}}_{\begin{subarray}{c}k_{1},\ldots,k_{t}\in
I\end{subarray}}\left\|f\right\|_{\\{H_{jk_{i_{1}}}-H_{jk_{i_{2}}}:\ j\in[s],\
0<i_{1}<i_{2}\leq t\\}}^{2^{d}}\gg_{A,D,s}\delta^{O_{s}(1)}N^{D},$

where $t=2^{s}$ and $d$ is the degree of the box norms on the left-hand side.

###### Proof.

Proposition 6.2 immediately implies that

$\displaystyle\operatorname*{\mathbb{E}}_{\begin{subarray}{c}i_{\underline{\epsilon}}\in
I,\\\
{\underline{\epsilon}}\in\\{0,1\\}^{s}\end{subarray}}\left\|f\right\|_{\begin{subarray}{c}\\{H_{ji_{\underline{\epsilon}}}-H_{ji_{{\underline{\epsilon}}^{\prime}}}:\
j\in[s]\
{\underline{\epsilon}},{\underline{\epsilon}}^{\prime}\in\\{0,1\\}^{s}\\\
\mathrm{with}\
(\epsilon_{1},\ldots,\epsilon_{s-j})=(\epsilon^{\prime}_{1},\ldots,\epsilon^{\prime}_{s-j}),\
\epsilon_{s+1-j}=1,\
\epsilon^{\prime}_{s+1-j}=0\\}\end{subarray}}^{2^{d^{\prime}}}\gg_{A,D,s}\delta^{O_{s}(1)}N^{D},$

where $d^{\prime}$ is the degree of the box norms on the left-hand side.
Ordering $\\{0,1\\}^{s}$ lexicographically and identifying it with
$[2^{s}]=[t]$ in an order-preserving way, we obtain a subset
${\mathcal{K}}_{0}\subseteq[t]\times[t]$ such that

$\displaystyle\operatorname*{\mathbb{E}}_{\begin{subarray}{c}k_{1},\ldots,k_{t}\in
I\end{subarray}}\left\|f\right\|_{\begin{subarray}{c}\\{H_{jk_{i_{1}}}-H_{jk_{i_{2}}}:\;j\in[s],\
({i_{1}},{i_{2}})\in{\mathcal{K}}_{0}\\}\end{subarray}}^{2^{d^{\prime}}}\gg_{A,D,s}\delta^{O_{s}(1)}N^{D}.$

Note that
${\mathcal{K}}_{0}\subseteq\\{(i_{1},i_{2})\in[t]\times[t]:i_{1}<i_{2}\\}$.
Our next goal is to replace ${\mathcal{K}}_{0}$ by the full set
${\mathcal{K}}=\\{(i_{1},i_{2})\in[t]\times[t]:\;i_{1}<i_{2}\\}$. By the
assumption on the multisets $H_{ji}$, we have

$[N]^{D}-(H_{jk_{1}}-H_{jk_{2}})\subseteq(-2AN,(2A+1)N]^{D},$

and so

$\mathopen{}\left|\operatorname{supp}([N]^{D}-(H_{jk_{1}}-H_{jk_{2}}))\mathclose{}\right|\leq(4A+1)^{D}N^{D}\ll_{A,D}N^{D}.$

The corollary follows from this observation and repeated applications of Lemma
3.5(iii), the monotonicity property for box norms. ∎

The next corollary will let us take the directions in the concatenated box
norms to be arbitrarily long sums of the original directions rather than just
double sums (as in Corollary 6.3).

######  Corollary 6.4 (Iterated concatenation of box norms).

Let $A,D,s,N\in{\mathbb{N}}$, and let $\ell$ be a power of 2. Let $I$ be a
finite indexing set, and let $H_{ji}\subseteq[\pm AN]^{D}$ be symmetric
multisets for each $i\in I$ and $j\in[s]$. Then for all $1$-bounded functions
$f:{\mathbb{Z}}^{D}\to{\mathbb{C}}$ supported on $[N]^{D}$, the bound

$\displaystyle\operatorname*{\mathbb{E}}_{i\in
I}\left\|f\right\|_{H_{1i},\ldots,H_{si}}^{2^{s}}\geq\delta N^{D}$

implies that

(41)
$\displaystyle\operatorname*{\mathbb{E}}_{\begin{subarray}{c}k_{1},\ldots,k_{t}\in
I\end{subarray}}\left\|f\right\|_{\\{H_{jk_{i_{1}}}+\cdots+H_{jk_{i_{\ell}}}:\
j\in[s],\ 1\leq i_{1}<\cdots<i_{\ell}\leq
t\\}}^{2^{d}}\gg_{A,D,\ell,s}\delta^{O_{\ell,s}(1)}N^{D},$

for some $t=O_{\ell,s}(1)$, where $d$ is the degree of the box norms on the
left-hand side.

It will be useful later that the indices $i_{1},\ldots,i_{\ell}$ in the sum

$\displaystyle H_{jk_{i_{1}}}+\cdots+H_{jk_{i_{\ell}}}$

in (41) are all distinct. The assumption of the symmetry of the multisets
$H_{ji}$ (meaning that $H_{ji}=-H_{ji}$)) in the corollary is not necessary,
and we include it only so that we do not have to keep track of the minus signs
in the expressions $H_{jk_{i_{1}}}+\cdots+H_{jk_{i_{\ell}}}$.

###### Proof.

The proof proceeds by induction on $\ell$, which we recall ranges over powers
of 2. For $\ell=1$, the claim is trivial, and for $\ell=2$, the lower bound

(42)
$\displaystyle\operatorname*{\mathbb{E}}_{\begin{subarray}{c}k_{1},\ldots,k_{t_{1}}\in
I\end{subarray}}\left\|f\right\|_{\\{H_{jk_{i_{1}}}+H_{jk_{i_{2}}}:\ j\in[s],\
0<i_{1}<i_{2}\leq t_{1}\\}}^{2^{d_{1}}}\gg_{A,D,s}\delta^{O_{s}(1)}N^{D},$

where $t_{1}=2^{s}$ and $d_{1}={{t_{1}}\choose{2}}$ is the degree of the box
norms appearing, follows from Corollary 6.3 and the fact that the sets
$H_{ji}$ are symmetric. We will now prove the case $\ell=4$, and which will
make the induction scheme for larger $\ell$ clear.

To prove the result for $\ell=2$, we apply the case $\ell=1$ to (42), taking
$(k_{1},\ldots,k_{t_{1}})\in I^{t_{1}}$ in place of $i\in I$. This gives

(43) $\displaystyle\operatorname*{\mathbb{E}}_{\begin{subarray}{c}k_{il}\in
I:\\\
i\in[t_{1}],\;l\in[t_{1}^{\prime}]\end{subarray}}\left\|f\right\|_{\begin{subarray}{c}\\{H_{jk_{i_{1}l_{1}}}+H_{jk_{i_{2}l_{1}}}+H_{jk_{i_{1}l_{2}}}+H_{jk_{i_{2}l_{2}}}:\\\
j\in[s],\;0<i_{1}<i_{2}\leq t_{1},\;0<l_{1}<l_{2}\leq
t_{1}^{\prime}\\}\end{subarray}}^{2^{d_{1}^{\prime}}}\gg_{A,D,s}\delta^{O_{s}(1)}N^{D},$

where $t_{1}^{\prime}=2^{d_{1}}$ and $d_{1}^{\prime}$ is the degree of the box
norms appearing. Reindexing $(i,l)\in[t_{1}]\times[t_{1}^{\prime}]$ as
$i\in[t_{2}]$ and using the monotonicity property and the assumption on
$H_{ji}$, we argue as in the proof of Corollary 6.3 that

$\displaystyle\operatorname*{\mathbb{E}}_{\begin{subarray}{c}k_{1},\ldots,k_{t_{2}}\in
I\end{subarray}}\left\|f\right\|_{\\{H_{jk_{i_{1}}}+\cdots+H_{jk_{i_{4}}}:\
j\in[s],\ 0<i_{1}<\cdots<i_{4}\leq
t_{1}\\}}^{2^{d_{2}}}\gg_{A,D,s}\delta^{O_{s}(1)}N^{D},$

where $d_{2}$ is the degree of the box norms appearing. We continue in the
same manner for larger $\ell$. ∎

##  7\. Equidistribution estimates for concatenation

The purpose of this section is to obtain upper bounds on the number of
solutions to systems of multilinear equations that appear in connection with
the manipulations in Section 8. These results will culminate in Proposition
7.5, which is precisely the ingredient needed to complete the proof of Theorem
1.10.

The starting point for our argument is the following simple lemma.

######  Lemma 7.1 (Bound on solutions to linear congruences).

Let $\ell\geq 2$, let $h_{1},\ldots,h_{\ell}$ be positive integers, and let
$M\in{\mathbb{N}}$. Then

$\displaystyle\max_{t\in{\mathbb{Z}}}\sum_{m_{1},\ldots,m_{\ell-1}\in[\pm
M]}\mathbf{1}_{h_{\ell}\mathbb{Z}+t}(h_{1}m_{1}+\cdots+h_{\ell-1}m_{\ell-1})\ll_{\ell}M^{\ell-1}\frac{\gcd(h_{1},\ldots,h_{\ell})}{h_{\ell}}+M^{\ell-2}.$

###### Proof.

First, we observe that if $(m^{\prime}_{1},\ldots,m^{\prime}_{\ell-1})\in[\pm
M]^{\ell-1}$ is a solution to the congruence

$\displaystyle h_{1}m_{1}+\cdots+h_{\ell-1}m_{\ell-1}\equiv t\pmod{h_{\ell}},$

then every other solution in $[\pm M]^{\ell-1}$ takes the form
$(m_{1},\ldots,m_{\ell-1})=(m^{\prime}_{1}+m^{\prime\prime}_{1},\ldots,m^{\prime}_{\ell}+m^{\prime\prime}_{\ell})$,
where $(m^{\prime\prime}_{1},\ldots,m^{\prime\prime}_{\ell})$ is a solution to
the homogeneous congruence

$\displaystyle h_{1}m_{1}+\cdots+h_{\ell-1}m_{\ell-1}\equiv 0\pmod{h_{\ell}}$

and $m^{\prime\prime}_{i}\in[\pm M]-m^{\prime}_{i}\subseteq[\pm 2M]$.
Therefore, it suffices to prove the $t=0$ case of the lemma (at the cost of
changing the implicit constant in the conclusion of the lemma).

We proceed by induction on $\ell$. For the base case $\ell=2$, we have

$h_{2}|h_{1}m_{1}\iff\frac{h_{2}}{\gcd(h_{1},h_{2})}|m_{1},$

and hence

$\sum_{m_{1}\in[\pm M]}\mathbf{1}_{h_{2}\mathbb{Z}}(h_{1}m_{1})\ll
M\frac{\gcd(h_{1},h_{2})}{h_{2}}+1$

(where $+1$ is the boundary term).

For the induction step, write

$\sum_{m_{1},\ldots,m_{\ell-1}\in[\pm
M]}\mathbf{1}_{h_{\ell}\mathbb{Z}}(h_{1}m_{1}+\cdots+h_{\ell-1}m_{\ell-1})=\\\
\sum_{m_{1},\ldots,m_{\ell-2}\in[\pm M]}\sum_{m_{\ell-1}\in[\pm
M]}\mathbf{1}_{h_{\ell}\mathbb{Z}-(h_{1}m_{1}+\cdots+h_{\ell-2}m_{\ell-2})}(h_{\ell-1}m_{\ell-1}).$

The crucial observation is that the inner summand vanishes if
$h_{1}m_{1}+\cdots+h_{\ell-2}m_{\ell-2}$ is not a multiple of
$g:=\gcd(h_{\ell-1},h_{\ell})$. Now suppose that $g$ does divide
$h_{1}m_{1}+\cdots+h_{\ell-2}m_{\ell-2}$; the induction hypothesis tells us
that this occurs for at most

$O_{\ell}\mathopen{}\left(M^{\ell-2}\frac{\gcd(h_{1},\ldots,h_{\ell})}{g}+M^{\ell-3}\mathclose{}\right)$

choices of $m_{1},\ldots,m_{\ell-2}$, where we have used the identity

$\gcd(h_{1},\ldots,h_{\ell-2},\gcd(h_{\ell-1},h_{\ell}))=\gcd(h_{1},\ldots,h_{\ell}).$

For each such choice of $m_{1},\ldots,m_{\ell-2}$, we have

$\mathbf{1}_{h_{\ell}\mathbb{Z}-(h_{1}m_{1}+\cdots+h_{\ell-2}m_{\ell-2})}(h_{\ell-1}m_{\ell-1})=\mathbf{1}_{(h_{\ell}/g)\mathbb{Z}-(h_{1}m_{1}+\cdots+h_{\ell-2}m_{\ell-2})/g}((h_{\ell-1}/g)m_{\ell-1}).$

Now the $\ell=2$ case of the proposition tells us that the sum over
$m_{\ell-1}$ has size

$O\mathopen{}\left(M\frac{\gcd(h_{\ell-1}/g,h_{\ell}/g)}{h_{\ell}/g}+1\mathclose{}\right)=O\mathopen{}\left(M\frac{g}{h_{\ell}}+1\mathclose{}\right)$

since $\gcd(h_{\ell-1}/g,h_{\ell}/g)=1$ by the definition of $g$. Combining
these two observations and using $\gcd(h_{1},\ldots,h_{\ell})\leq g\leq
h_{\ell}$, we bound

$\sum_{m_{1},\ldots,m_{\ell-1}\in[\pm
M]}\mathbf{1}_{h_{\ell}\mathbb{Z}}(h_{1}m_{1}+\cdots+h_{\ell-1}m_{\ell-1})\ll_{\ell}M^{\ell-1}\frac{\gcd(h_{1},\ldots,h_{\ell})}{h_{\ell}}+M^{\ell-2},$

as desired. ∎

######  Corollary 7.2 (Bound on solutions to linear equations).

Let $\ell\geq 2$, let $h_{1},\ldots,h_{\ell}$ be positive integers, and let
$M\in{\mathbb{N}}$. Then

$\displaystyle\max_{t\in{\mathbb{Z}}}\sum_{m_{1},\ldots,m_{\ell}\in[\pm
M]}\mathbf{1}(h_{1}m_{1}+\cdots+h_{\ell}m_{\ell}=t)\ll_{\ell}M^{\ell-1}\frac{\gcd(h_{1},\ldots,h_{\ell})}{h_{\ell}}+M^{\ell-2}.$

We will later apply this corollary with

$\displaystyle\max_{i\in[\ell]}|h_{i}|\leq H\leq
M,\quad\gcd(h_{1},\ldots,h_{\ell})\leq\eta^{-1},\quad\textrm{and}\quad
h_{\ell}\geq\eta H$

(for small positive $\eta$), in which case the right-hand side is
$\ll_{\ell}\eta^{-2}M^{\ell-1}H^{-1}$.

###### Proof.

For each choice of $m_{1},\ldots,m_{\ell-1}$, there is at most one value of
$m_{\ell}$ satisfying $h_{1}m_{1}+\cdots+h_{\ell}m_{\ell}=t$, so we can bound

$\displaystyle\sum_{m_{1},\ldots,m_{\ell}\in[\pm
M]}\mathbf{1}_{h_{1}m_{1}+\cdots+h_{\ell}m_{\ell}=t}\leq\sum_{m_{1},\ldots,m_{\ell-1}\in[\pm
M]}\mathbf{1}_{h_{\ell}{\mathbb{Z}}+t}(h_{1}m_{1}+\cdots+h_{\ell-1}m_{\ell-1});$

here we have an inequality instead of an equality because on the right-hand
side we have thrown out the constraint $m_{\ell}\in[\pm M]$. The result now
follows from Lemma 7.1. ∎

In order to state our more general results, we require a bit of notation.
Define

(44)
$\displaystyle{\mathcal{K}}_{t,\ell,r}:=\\{(k_{li})_{\begin{subarray}{c}(l,i)\in[r]\times[\ell]\end{subarray}}\in[t]^{r\ell}:\;1\leq
k_{l1}<\cdots<k_{l\ell}\leq t\;\;\textrm{for\; all}\;\;l\in[r]\\}$

to be the collection of admissible tuples of indices. For $l\in[r]$ and
$\eta>0$, also define

(45) ${\mathcal{H}}_{l,\eta}:=\\{(h_{lk_{1}\cdots
k_{l}})_{k_{1},\ldots,k_{l}\in[t]}\in[\pm H]^{t^{l}}:\;|h_{lk_{1}\cdots
k_{l}}-h_{lk^{\prime\prime}_{1}\cdots k^{\prime\prime}_{l}}|\geq\eta H,\\\
\gcd(h_{lk_{1}\cdots k_{l}}-h_{lk^{\prime\prime}_{1}\cdots
k^{\prime\prime}_{l}},h_{lk^{\prime}_{1}\cdots
k^{\prime}_{l}}-h_{lk^{\prime\prime}_{1}\cdots
k^{\prime\prime}_{l}})\leq\eta^{-1}\\\ \textrm{for\;
distinct}\;(k_{1},\ldots,k_{l}),\;(k^{\prime}_{1},\ldots,k^{\prime}_{l}),\;(k^{\prime\prime}_{1},\ldots,k^{\prime\prime}_{l})\in[t]^{l}\\}$

to be the set of tuples of $h$’s whose pairwise differences are not too small
and whose greatest common divisors are not too big. The following lemma, which
lets us establish anti-concentration results on many pairs of “scales”
simultaneously, will turn out to be the key component of the proof of
Proposition 7.5 below.

######  Lemma 7.3.

Let $\eta>0$ and $H,M,l,\ell,r,s,t\in{\mathbb{N}}$ satisfy $H\leq M$,
$3\leq\ell\leq t$, and $l\leq r$. Let ${\mathcal{K}}={\mathcal{K}}_{t,\ell,r}$
be as in (44) and ${\mathcal{H}}={\mathcal{H}}_{l,\eta}$ be as in (45). Then

$\operatorname*{\mathbb{E}}_{\begin{subarray}{c}h_{lk_{1}\cdots k_{l}}\in[\pm
H]:\\\
k_{1},\ldots,k_{l}\in[t]\end{subarray}}\;\mathbf{1}_{{\mathcal{H}}}((h_{lk_{1}\cdots
k_{l}})_{k_{1},\ldots,k_{l}})\cdot\prod_{i_{1},\ldots,i_{l-1}\in[\ell]}\;\prod_{j\in[s]}\;\prod_{{\underline{k}}\in{\mathcal{K}}}\;\prod_{u_{l+1},\ldots,u_{r}\in\\{0,1\\}}\\\
\max_{\begin{subarray}{c}n_{0},n_{1}\in{\mathbb{Z}}\end{subarray}}\;\operatorname*{\mathbb{E}}_{\begin{subarray}{c}|m_{i_{l}}|\leq
H^{u_{l+1}+\cdots+u_{r}}M:\\\
i_{l}\in[\ell]\end{subarray}}\;\mathbf{1}\Bigl{(}\sum\limits_{i_{l}\in[\ell]}m_{i_{l}}=n_{0}\Bigr{)}\cdot\mathbf{1}\Bigl{(}\sum\limits_{i_{l}\in[\ell]}h_{lk_{1i_{1}}\cdots
k_{li_{l}}}m_{i_{l}}=n_{1}\Bigr{)}\\\
\ll_{l,\ell,r,s,t}\eta^{-2^{r-l+1}s\ell^{l-1}|{\mathcal{K}}|}M^{-2^{r-l+1}s\ell^{l-1}|{\mathcal{K}}|}H^{-(r-l+1)2^{r-l}s\ell^{l-1}|{\mathcal{K}}|}.$

######  Example 7.4.

We will illustrate the content of this lemma and the method of proof for
$r=2$, $l=1$, $t=4$, $\ell=3$, $s=1$ before supplying the proof in the general
case. Letting

$\displaystyle{\mathcal{K}}^{\prime}=\\{(1,2,3),\;(1,2,4),\;(1,3,4),\;(2,3,4)\\}\quad\textrm{so\;
that}\quad{\mathcal{K}}={\mathcal{K}}^{\prime}\times{\mathcal{K}}^{\prime}$

and $|{\mathcal{K}}|=16$, and renaming $h_{1k_{1i_{1}}}$ as simply
$h_{k_{i}}$, we can express the conclusion of the lemma as

$\operatorname*{\mathbb{E}}_{\begin{subarray}{c}h_{1},h_{2},h_{3},h_{4}\in[\pm
H]\end{subarray}}\;\mathbf{1}_{{\mathcal{H}}}(h_{1},h_{2},h_{3},h_{4})\cdot\big{(}\prod_{{\underline{k}}\in{\mathcal{K}}^{\prime}}\;\prod_{u_{2}\in\\{0,1\\}}\max_{\begin{subarray}{c}n_{0},n_{1}\in{\mathbb{Z}}\end{subarray}}\\\
\operatorname*{\mathbb{E}}_{\begin{subarray}{c}|m_{1}|,|m_{2}|,|m_{3}|\leq
H^{u_{2}}M\end{subarray}}\;\mathbf{1}(m_{1}+m_{2}+m_{3}=n_{0})\cdot\mathbf{1}(h_{k_{1}}m_{1}+h_{k_{2}}m_{2}+h_{k_{3}}m_{3}=n_{1})\big{)}^{4}\\\
\ll\eta^{-64}M^{-64}H^{-64},$

where the fourth power comes from the fact that we are splitting

$\prod\limits_{(k_{1i_{1}},k_{2i_{2}})_{i_{1},i_{2}\in[3]}\in{\mathcal{K}}}=\prod\limits_{(k_{1i_{1}})_{i_{1}\in[3]}\in{\mathcal{K}}^{\prime}}\;\prod\limits_{(k_{2i_{2}})_{i_{2}\in[3]}\in{\mathcal{K}}^{\prime}}$

and the terms in the product are independent of $k_{2i_{2}}$ (so the product
over ${\underline{k}}\in{\mathcal{K}}^{\prime}$ above corresponds to the
product over $(k_{1i_{1}})_{i_{1}\in[3]}\in{\mathcal{K}}^{\prime}$ while the
fourth power corresponds to the product over
$(k_{2i_{2}})_{i_{2}\in[3]}\in{\mathcal{K}}^{\prime}$). Our normalized count
can then be expanded as

$\operatorname*{\mathbb{E}}_{\begin{subarray}{c}h_{1},h_{2},h_{3},h_{4}\in[\pm
H]\end{subarray}}\;\mathbf{1}_{{\mathcal{H}}}(h_{1},h_{2},h_{3},h_{4})\cdot\big{(}\prod_{{\underline{k}}\in{\mathcal{K}}^{\prime}}\;\max_{\begin{subarray}{c}n_{00},n_{01},n_{10},n_{11}\in{\mathbb{Z}}\end{subarray}}\\\
\operatorname*{\mathbb{E}}_{\begin{subarray}{c}|m_{01}|,|m_{02}|,|m_{03}|\leq
M,\\\ |m_{11}|,|m_{12}|,|m_{13}|\leq
HM\end{subarray}}\;\mathbf{1}\begin{pmatrix}m_{01}+m_{02}+m_{03}=n_{00},\\\
m_{11}+m_{12}+m_{13}=n_{01}\end{pmatrix}\cdot\mathbf{1}\begin{pmatrix}h_{k_{1}}m_{01}+h_{k_{2}}m_{02}+h_{k_{3}}m_{03}=n_{10},\\\
h_{k_{1}}m_{11}+h_{k_{2}}m_{12}+h_{k_{3}}m_{13}=n_{11}\end{pmatrix}\big{)}^{4}.$

Thus, for each $(h_{1},h_{2},h_{3},h_{4})\in{\mathcal{H}}$ and
${\underline{k}}\in{\mathcal{K}}^{\prime}$, we are left with bounding the
number of solutions to the system

$\displaystyle m_{01}+m_{02}+m_{03}=n_{00}\quad\textrm{and}\quad
h_{k_{1}}m_{01}+h_{k_{2}}m_{02}+h_{k_{3}}m_{03}=n_{10},$ $\displaystyle
m_{11}+m_{12}+m_{13}=n_{01}\quad\textrm{and}\quad
h_{k_{1}}m_{11}+h_{k_{2}}m_{12}+h_{k_{3}}m_{13}=n_{11}.$

Using the equations on the left to solve for $m_{03}$ and $m_{13}$ and
substituting the resulting expressions into the equations on the right reduces
the system to

$\displaystyle(h_{k_{1}}-h_{k_{3}})m_{01}+(h_{k_{2}}-h_{k_{3}})m_{02}$
$\displaystyle=n_{0}$
$\displaystyle(h_{k_{1}}-h_{k_{3}})m_{11}+(h_{k_{2}}-h_{k_{3}})m_{22}$
$\displaystyle=n_{1}$

for $n_{0}=n_{10}-h_{k_{3}}n_{00}$ and $n_{1}=n_{11}-h_{k_{3}}n_{01}$, and
each of these two equations can then be handled separately using Corollary 7.2
and the assumptions on $(h_{1},h_{2},h_{3},h_{4})\in{\mathcal{H}}_{1}$.

The exponent $64$ comes from the fact that the numbers
$n_{00},n_{01},n_{10},n_{11}$ lie in the intervals

$\displaystyle n_{00}\in[\pm 3M],\quad n_{01},n_{10}\in[\pm 3HM],\quad
n_{11}\in[\pm 3H^{2}M]$

and hence there are $\asymp H^{4}M^{4}$ possibilities for the quadruple
$(n_{00},n_{01},n_{10},n_{11})$. Because of the assumption on
$(h_{1},h_{2},h_{3},h_{4})$, we can use Corollary 7.2 to ensure that the
quadruple $(n_{00},n_{01},n_{10},n_{11})$ is roughly equidistributed in the
appropriate box as the $m$’s range; in particular, the probability of hitting
each individual quadruple $(n_{00},n_{01},n_{10},n_{11})$ is

$O((M^{-2}\eta^{-1}/(\eta H))\cdot((HM)^{-2}\eta^{-1}/(\eta
H)))=O(\eta^{-4}H^{-4}M^{-4}).$

Raising this quantity to the power $4$ (because $|{\mathcal{K}}^{\prime}|=4$),
we see that the expression in parentheses above is
$O(\eta^{-16}H^{-16}M^{-16})$, and raising this to the power $4$ gives the
desired exponent $64$.

###### Proof of Lemma 7.3.

We let all implicit constants depend on $l,\ell,r,s,t$. Using the equation
$\sum\limits_{i_{l}\in[\ell]}{m}_{i_{l}}=n_{0}$ we can substitute
$m_{\ell}=n_{0}-\sum\limits_{i_{l}\in[\ell-1]}{m}_{i_{l}}$ into the equation

$\sum\limits_{\begin{subarray}{c}i_{l}\in[\ell]\end{subarray}}h_{lk_{1i_{1}}\cdots
k_{li_{l}}}{m}_{i_{l}}=n_{1},$

so that our normalized count is bounded by

$\operatorname*{\mathbb{E}}_{\begin{subarray}{c}h_{lk_{1}\cdots k_{l}}\in[\pm
H]:\\\
k_{1},\ldots,k_{l}\in[t]\end{subarray}}\;\mathbf{1}_{{\mathcal{H}}}((h_{lk_{1}\cdots
k_{l}})_{k_{1},\ldots,k_{l}})\cdot\prod_{i_{1},\ldots,i_{l-1}\in[\ell]}\;\prod_{j\in[s]}\;\prod_{{\underline{k}}\in{\mathcal{K}}}\;\prod_{u_{l+1},\ldots,u_{r}\in\\{0,1\\}}H^{-(u_{l+1}+\cdots+u_{r})}M^{-1}\\\
\max_{\begin{subarray}{c}n\in{\mathbb{Z}}\end{subarray}}\;\operatorname*{\mathbb{E}}_{\begin{subarray}{c}|m_{i_{l}}|\leq
H^{u_{l+1}+\cdots+u_{r}}M:\\\
i_{l}\in[\ell-1]\end{subarray}}\mathbf{1}\Bigl{(}\sum\limits_{i_{l}\in[\ell-1]}(h_{lk_{1i_{1}}\cdots
k_{li_{l}}}-h_{lk_{1i_{1}}\cdots
k_{(l-1)i_{l-1}}k_{l\ell}})m_{i_{l}}=n\Bigr{)},$

where we have set $n=n_{1}-n_{0}h_{lk_{1i_{1}}\cdots
k_{(l-1)i_{l-1}}k_{l\ell}}$. By Corollary 7.2, the inner max is in turn
bounded by

$H^{-(u_{l+1}+\cdots+u_{r})}M^{-1}\frac{\gcd(h_{lk_{1i_{1}}\cdots
k_{(l-1)i_{l-1}}k_{li_{l}}}-h_{lk_{1i_{1}}\cdots
k_{(l-1)i_{l-1}}k_{l\ell}}:\;i_{l}\in[\ell-1])}{\max(h_{lk_{1i_{1}}\cdots
k_{(l-1)i_{l-1}}k_{li_{l}}}-h_{lk_{1i_{1}}\cdots
k_{(l-1)i_{l-1}}k_{l\ell}}:\;i_{l}\in[\ell-1])}$

as long as $\ell\geq 3$ and $H\leq M$. Due to our assumption on the set
${\mathcal{H}}$, the $\gcd$ in the numerator is at most $\eta^{-1}$ and the
maximum in the denominator is at least $\eta H$, so we can bound our
normalized count by

$\displaystyle\ll\operatorname*{\mathbb{E}}_{\begin{subarray}{c}h_{lk_{1}\cdots
k_{l}}\in[\pm H]:\\\
k_{1},\ldots,k_{l}\in[t]\end{subarray}}\;\prod_{i_{1},\ldots,i_{l-1}\in[\ell]}\;\prod_{j\in[s]}\;\prod_{{\underline{k}}\in{\mathcal{K}}}\;\prod_{u_{l+1},\ldots,u_{r}\in\\{0,1\\}}\eta^{-2}M^{-2}H^{-1-2(u_{l+1}+\cdots+u_{r})}$
$\displaystyle\ll\eta^{-2^{r-l+1}s\ell^{l-1}|{\mathcal{K}}|}M^{-2^{r-l+1}s\ell^{l-1}|{\mathcal{K}}|}H^{-(r-l+1)2^{r-l}s\ell^{l-1}|{\mathcal{K}}|}.$

∎

The next result, in which we we establish simultaneous anti-concentration for
expressions on many scales, is the main estimate of this section. It gives an
upper bound on the number of solutions to the systems of multilinear equations
that naturally appear while concatenating box norms in the proof of Theorem
1.10.

######  Proposition 7.5 (Solutions to systems of multilinear equations).

Let $\eta>0$, let $\ell,r,s,t\in{\mathbb{N}}$ with $3\leq\ell\leq t$, and let
$H,M\in{\mathbb{N}}$ with $H\leq M$. Let
${\mathcal{K}}={\mathcal{K}}_{t,\ell,r}$ be as in (44), and for each
$l\in[r]$, let ${\mathcal{H}}_{l}:={\mathcal{H}}_{l,\eta}$ be as in (45). Then

$\max_{\begin{subarray}{c}n_{j{\underline{k}}{\underline{u}}}\in{\mathbb{Z}}:\;j\in[s],\\\
{\underline{k}}\in{\mathcal{K}},\;{\underline{u}}\in\\{0,1\\}^{r}\end{subarray}}\;\operatorname*{\mathbb{E}}_{\begin{subarray}{c}m_{j{\underline{k}}i_{1}\cdots
i_{r}}\in[\pm M]:\\\
j\in[s],\;{\underline{k}}\in{\mathcal{K}},\;i_{1},\ldots,i_{r}\in[\ell]\end{subarray}}\operatorname*{\mathbb{E}}_{\begin{subarray}{c}h_{lk_{1}\cdots
k_{l}}\in[\pm H]:\\\
k_{1},\ldots,k_{r}\in[t],\;l\in[r]\end{subarray}}\;\Bigl{(}\prod_{l\in[r]}\mathbf{1}_{{\mathcal{H}}_{l}}((h_{lk_{1}\cdots
k_{l}})_{k_{1},\ldots,k_{l}\in[t]})\Bigr{)}\\\
\prod_{j\in[s]}\;\prod_{\begin{subarray}{c}{\underline{k}}\in{\mathcal{K}}\end{subarray}}\prod_{\begin{subarray}{c}{\underline{u}}\in\\{0,1\\}^{r}\end{subarray}}\mathbf{1}\Bigl{(}\sum\limits_{i_{1},\ldots,i_{r}\in[\ell]}h_{1k_{1i_{1}}}^{u_{1}}\cdots
h_{rk_{1i_{1}}\cdots k_{ri_{r}}}^{u_{r}}m_{j{\underline{k}}i_{1}\cdots
i_{r}}=n_{j{\underline{k}}{\underline{u}}}\Bigr{)}\\\
\ll_{\ell,r,s,t}\eta^{-O_{\ell,r,s,t}(1)}M^{-2^{r}s|{\mathcal{K}}|}H^{-r2^{r-1}s|{\mathcal{K}}|}.$

(Here, the superscript $u$’s are exponents, not indices.)

On a first read, the reader may wish to consider the case $t=\ell$, so that
${\mathcal{K}}$ consists of only one element, $k_{li_{l}}$ can be replaced by
$k_{l}$, and the product
$\prod_{\begin{subarray}{c}{\underline{k}}\in{\mathcal{K}}\end{subarray}}$
disappears.

In the applications of Proposition 7.5 to Theorem 1.10, $s$ is fixed and
$\ell$ (the number of terms in each equation) can be taken as large as we
want, whereas we have no control over $t$, which grows with $\ell$ and will
typically be much larger than $\ell$.

Before proving Proposition 7.5, we illustrate the statement with several
examples.

######  Example 7.6.

If $s=1$, i.e., we are using Proposition 7.5 to concatenate an average of
degree-$1$ box norms, then we will always have $t=\ell$, whence
$|{\mathcal{K}}|=1$. Suppose that $t=\ell=3$ and $r=2$, i.e., we are dealing
with a system of equations coming from concatenating an average

$\displaystyle\operatorname*{\mathbb{E}}_{h_{1},h_{2}\in[\pm
H]}\left\|f\right\|_{({\boldsymbol{\beta}}_{00}+{\boldsymbol{\beta}}_{10}h_{1}+{\boldsymbol{\beta}}_{01}h_{2}+{\boldsymbol{\beta}}_{11}h_{1}h_{2})\cdot[\pm
M]}^{2}.$

The resulting system consists of equations of the form

$h_{11}^{u_{1}}(h_{211}^{u_{2}}m_{11}+h_{212}^{u_{2}}m_{12}+h_{213}^{u_{2}}m_{13})+h_{12}^{u_{1}}(h_{221}^{u_{2}}m_{21}+h_{222}^{u_{2}}m_{22}+h_{223}^{u_{2}}m_{23})\\\
+h_{13}^{u_{1}}(h_{231}^{u_{2}}m_{31}+h_{232}^{u_{2}}m_{32}+h_{233}^{u_{2}}m_{33})={n_{u_{1}u_{2}}}$

for $(u_{1},u_{2})\in\\{0,1\\}^{2}$. Since $n_{u_{1}u_{2}}$ lies in $[\pm
9H^{u_{1}+u_{2}}M]$, we expect to get a cancellation on the order of

$\displaystyle\ll\prod_{u_{1},u_{2}\in\\{0,1\\}}H^{-(u_{1}+u_{2})}M^{-1}=H^{-4}M^{-4},$

and modulo the powers of $\eta$, this is indeed what Proposition 7.5 gives.

######  Example 7.7.

Suppose now that $r=1$, $s=4$, $t=6$, and $\ell=4$, so that
$|{\mathcal{K}}|=15$. Then we have a system of $30$ equations, which we can
group into $15$ pairs of equations

$\displaystyle
m_{{\underline{k}}1}+m_{{\underline{k}}2}+m_{{\underline{k}}3}+m_{{\underline{k}}4}=n_{{\underline{k}}0}\quad\textrm{and}\quad
m_{{\underline{k}}1}h_{k_{1}}+m_{{\underline{k}}2}h_{k_{2}}+m_{{\underline{k}}3}h_{k_{3}}+m_{{\underline{k}}4}h_{k_{4}}=n_{{\underline{k}}1}$

corresponding to the $15$ tuples

${\underline{k}}\in{\mathcal{K}}=\\{(k_{1},k_{2},k_{3},k_{4}):\;1\leq
k_{1}<k_{2}<k_{3}<k_{4}\leq 6\\}.$

Each $n_{{\underline{k}}0}$, $n_{{\underline{k}}1}$ gives cancellation of
order $\asymp M^{-1},\asymp H^{-1}M^{-1}$ (respectively), so the total
cancellation will be of order $\asymp H^{-15}M^{-30}$ (modulo powers of
$\eta$, which we ignore here for the simplicity of exposition). We remark that
this example does not figure in the proof of Theorem 1.10 (but nonetheless is
covered by Proposition 7.5).

Let us see how the heuristics from the preceding two examples extend to the
general case. For each $(j,{\underline{k}},{\underline{u}})$, we expect the
value $n_{j{\underline{k}}{\underline{u}}}$ to be distributed fairly uniformly
in an interval $[\pm
C_{j{\underline{k}}{\underline{u}}}H^{u_{1}+\cdots+u_{r}}M]$ for some
$C_{j{\underline{k}}{\underline{u}}}>0$; the key uniform distribution property
follows from Corollary 7.2 and the fact that the tuples $(h_{lk_{1}\cdots
k_{l}})_{k_{1},\ldots,k_{l}}$ lie in the sets ${\mathcal{H}}_{l}$. So for each
$(j,{\underline{k}},{\underline{u}})$ we get a cancellation of the order of

(46) $\displaystyle\asymp_{r}(H^{-(u_{1}+\cdots+u_{r})}M^{-1}),$

which is (up to constants) the probability that a uniformly random element of
the interval $[\pm
C_{j{\underline{k}}{\underline{u}}}H^{u_{1}+\cdots+u_{r}}M]$ assumes any given
value. The powers of $\eta$ in the bound come from restricting the variables
$h_{l}$ to the admissible ranges ${\mathcal{H}}_{l}$, and using Corollary 7.2
to bound solutions for $h$’s in this range. The final bound then follows upon
taking the product of (46) over all $j\in[s],{\underline{u}}\in\\{0,1\\}^{r}$,
and ${\underline{k}}\in{\mathcal{K}}$.

###### Proof of Proposition 7.5.

We let all implicit constants depend on $\ell,r,s,t$. The proof goes by
induction on $r$. The $r=1$ case is the content of Lemma 7.3. The induction
step is in general quite notationally complicated, so, to make it more
palatable, we first present the case $r=2$.

The case $r=2$.

In this case, our claimed bound takes the form

$\max_{\begin{subarray}{c}n_{j{\underline{k}}00},\;n_{j{\underline{k}}01},\\\
n_{j{\underline{k}}10},\;n_{j{\underline{k}}11}\in{\mathbb{Z}}:\\\
j\in[s],\;{\underline{k}}\in{\mathcal{K}}\end{subarray}}\;\operatorname*{\mathbb{E}}_{\begin{subarray}{c}m_{j{\underline{k}}i_{1}i_{2}}\in[\pm
M]:\\\
j\in[s],\;{\underline{k}}\in{\mathcal{K}},\;i_{1},i_{2}\in[\ell]\end{subarray}}\operatorname*{\mathbb{E}}_{\begin{subarray}{c}h_{1k_{1}},h_{2k_{1}k_{2}}\in[\pm
H]:\\\
k_{1},k_{2}\in[t]\end{subarray}}\;\mathbf{1}_{{\mathcal{H}}_{1}}((h_{1k_{1}})_{k_{1}})\cdot\mathbf{1}_{{\mathcal{H}}_{2}}((h_{2k_{1}k_{2}})_{k_{1},k_{2}})\\\
\prod_{j\in[s]}\;\prod_{\begin{subarray}{c}{\underline{k}}\in{\mathcal{K}}\end{subarray}}\prod_{\begin{subarray}{c}{\underline{u}}\in\\{0,1\\}^{2}\end{subarray}}\mathbf{1}\Bigl{(}\sum\limits_{i_{1},i_{2}\in[\ell]}h_{1k_{1i_{1}}}^{u_{1}}h_{2k_{1i_{1}}k_{2i_{2}}}^{u_{2}}m_{j{\underline{k}}i_{1}i_{2}}=n_{j{\underline{k}}{\underline{u}}}\Bigr{)}\\\
\ll\eta^{-O(1)}M^{-4s|{\mathcal{K}}|}H^{-4s|{\mathcal{K}}|}.$

For each $(j,{\underline{k}})\in[s]\times{\mathcal{K}}$, we have the system of
four equations

$\displaystyle\sum\limits_{i_{1},i_{2}\in[\ell]}m_{j{\underline{k}}i_{1}i_{2}}$
$\displaystyle=n_{j{\underline{k}}00}$
$\displaystyle\sum\limits_{i_{1},i_{2}\in[\ell]}h_{1k_{1i_{1}}}m_{j{\underline{k}}i_{1}i_{2}}$
$\displaystyle=n_{j{\underline{k}}10}$
$\displaystyle\sum\limits_{i_{1},i_{2}\in[\ell]}h_{2k_{1i_{1}}k_{2i_{2}}}m_{j{\underline{k}}i_{1}i_{2}}$
$\displaystyle=n_{j{\underline{k}}01}$
$\displaystyle\sum\limits_{i_{1},i_{2}\in[\ell]}h_{1k_{1i_{1}}}h_{2k_{1i_{1}}k_{2i_{2}}}m_{j{\underline{k}}i_{1}i_{2}}$
$\displaystyle=n_{j{\underline{k}}11}.$

This system is quadratic in the $h$ variables, and our goal is to decouple it
into two separate systems that are linear in $h$. We accomplish this by
introducing two dummy variables

$\displaystyle
t_{i_{1}j{\underline{k}}0}=\sum_{i_{2}\in[\ell]}m_{j{\underline{k}}i_{1}i_{2}}\quad\textrm{and}\quad
t_{i_{1}j{\underline{k}}1}=\sum_{i_{2}\in[\ell]}h_{2k_{1i_{1}}k_{2i_{2}}}m_{j{\underline{k}}i_{1}i_{2}}$

and renaming $t_{i_{1}i_{2}j{\underline{k}}}=m_{j{\underline{k}}i_{1}i_{2}}$.
Let us mention the motivation for choosing these variables. The above system
of four equations has three different scales: The first is at scale $\asymp
M$, the second and third are at scale $\asymp HM$, and the fourth is at scale
$\asymp H^{2}M$. In order to apply the two-scale result from Lemma 7.3, we
want to think of the fourth equation as having scale $\asymp H(HM)$, where the
$HM$ here “matches” the scale of the third equation. This is precisely the
role played by the second set of dummy variables, which is at scale $\asymp
HM$. The first set of dummy variables, at scale $\asymp M$, pertains to the
first and second equations, and the two sets of dummy variables are chosen in
such a way that they are related at consecutive scales as in Lemma 7.3.

Thus, solving the original system is equivalent to solving

$\displaystyle\sum_{i_{1}\in[\ell]}t_{i_{1}j{\underline{k}}0}=n_{j{\underline{k}}00}\quad\textrm{and}\quad\sum_{i_{1}\in[\ell]}h_{1k_{1i_{1}}}t_{i_{1}j{\underline{k}}0}=n_{j{\underline{k}}10}$
$\displaystyle\sum_{i_{1}\in[\ell]}t_{i_{1}j{\underline{k}}1}=n_{j{\underline{k}}01}\quad\textrm{and}\quad\sum_{i_{1}\in[\ell]}h_{1k_{1i_{1}}}t_{i_{1}j{\underline{k}}1}=n_{j{\underline{k}}11},$

together with

$\displaystyle\sum_{i_{2}\in[\ell]}t_{i_{1}i_{2}j{\underline{k}}}=t_{i_{1}j{\underline{k}}0}\quad\textrm{and}\quad\sum_{i_{2}\in[\ell]}h_{2k_{i_{1}}k_{i_{2}}}t_{i_{1}i_{2}j{\underline{k}}}=t_{i_{1}j{\underline{k}}1}\quad\textrm{for\;
each}\quad i_{1}\in[\ell],$

where the variables $t_{i_{1}j{\underline{k}}0}$ and
$t_{i_{1}j{\underline{k}}1}$ have ranges $[\pm\ell M]$ and $[\pm\ell HM]$,
respectively. Converting the expectation over the $m$’s to a sum, we see that
our normalized count is bounded by $O(M^{-s\ell^{2}|{\mathcal{K}}|})$ times

$\displaystyle\max_{\begin{subarray}{c}n_{j{\underline{k}}00},\;n_{j{\underline{k}}01},\\\
n_{j{\underline{k}}10},\;n_{j{\underline{k}}11}\in{\mathbb{Z}}:\\\
j\in[s],\;{\underline{k}}\in{\mathcal{K}}\end{subarray}}\;\operatorname*{\mathbb{E}}_{\begin{subarray}{c}h_{1k_{1}}\in[\pm
H]:\\\
k_{1}\in[t]\end{subarray}}\;\mathbf{1}_{{\mathcal{H}}_{1}}((h_{1k_{1}})_{k_{1}})\sum_{\begin{subarray}{c}t_{i_{1}j{\underline{k}}0}\in[\pm\ell
M],\\\ t_{i_{1}j{\underline{k}}1}\in[\pm\ell HM]:\\\
j\in[s],\;{\underline{k}}\in{\mathcal{K}},\;i_{1}\in[\ell]\end{subarray}}$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\Big{(}\prod_{j\in[s]}\;\prod_{\begin{subarray}{c}{\underline{k}}\in{\mathcal{K}}\end{subarray}}\prod_{\begin{subarray}{c}{\underline{u}}\in\\{0,1\\}^{2}\end{subarray}}\mathbf{1}\Bigl{(}\sum\limits_{i_{1}\in[\ell]}h_{1k_{1i_{1}}}^{u_{1}}t_{i_{1}j{\underline{k}}u_{2}}=n_{j{\underline{k}}{\underline{u}}}\Bigr{)}\Big{)}$
$\displaystyle\qquad\qquad\qquad\times\Big{(}\operatorname*{\mathbb{E}}_{\begin{subarray}{c}h_{2k_{1}k_{2}}\in[\pm
H]:\\\
k_{1},k_{2}\in[t]\end{subarray}}\;\mathbf{1}_{{\mathcal{H}}_{2}}((h_{2k_{1}k_{2}})_{k_{1},k_{2}})\sum_{\begin{subarray}{c}t_{i_{1}i_{2}j{\underline{k}}}\in[\pm
M]:\\\
j\in[s],\;{\underline{k}}\in{\mathcal{K}},\;i_{1},i_{2}\in[\ell]\end{subarray}}$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\prod_{i_{1}\in[\ell]}\prod_{j\in[s]}\;\prod_{\begin{subarray}{c}{\underline{k}}\in{\mathcal{K}}\end{subarray}}\prod_{\begin{subarray}{c}u_{2}\in\\{0,1\\}\end{subarray}}\mathbf{1}\Bigl{(}\sum\limits_{i_{2}\in[\ell]}h_{2k_{1i_{1}}k_{2i_{2}}}^{u_{2}}t_{i_{1}i_{2}j{\underline{k}}}=t_{i_{1}j{\underline{k}}u_{2}}\Bigr{)}\Big{)};$

we will deal first with the system involving the variables $h_{2k_{1}k_{2}}$
and then with the system involving the variables $h_{1k_{1}}$. Note that

$\displaystyle\sum_{\begin{subarray}{c}t_{i_{1}i_{2}j{\underline{k}}}\in[\pm
M]:\\\
j\in[s],\;{\underline{k}}\in{\mathcal{K}},\;i_{1},i_{2}\in[\ell]\end{subarray}}\prod_{i_{1}\in[\ell]}\prod_{j\in[s]}\;\prod_{\begin{subarray}{c}{\underline{k}}\in{\mathcal{K}}\end{subarray}}\prod_{\begin{subarray}{c}u_{2}\in\\{0,1\\}\end{subarray}}\mathbf{1}\Bigl{(}\sum\limits_{i_{2}\in[\ell]}h_{2k_{1i_{1}}k_{2i_{2}}}^{u_{2}}t_{i_{1}i_{2}j{\underline{k}}}=t_{i_{1}j{\underline{k}}u_{2}}\Bigr{)}$
$\displaystyle\qquad=\prod_{i_{1}\in[\ell]}\prod_{j\in[s]}\;\prod_{\begin{subarray}{c}{\underline{k}}\in{\mathcal{K}}\end{subarray}}\sum_{\begin{subarray}{c}t_{i_{1}i_{2}j{\underline{k}}}\in[\pm
M]:\\\
i_{2}\in[\ell]\end{subarray}}\;\mathbf{1}\Bigl{(}\sum\limits_{i_{2}\in[\ell]}t_{i_{1}i_{2}j{\underline{k}}}=t_{i_{1}j{\underline{k}}0}\Bigr{)}\cdot\mathbf{1}\Bigl{(}\sum\limits_{i_{2}\in[\ell]}h_{2k_{1i_{1}}k_{2i_{2}}}t_{i_{1}i_{2}j{\underline{k}}}=t_{i_{1}j{\underline{k}}1}\Bigr{)}.$

Thus, we have

$\displaystyle\operatorname*{\mathbb{E}}_{\begin{subarray}{c}h_{2k_{1}k_{2}}\in[\pm
H]:\\\
k_{1},k_{2}\in[t]\end{subarray}}\;\mathbf{1}_{{\mathcal{H}}_{2}}((h_{2k_{1}k_{2}})_{k_{1},k_{2}})\sum_{\begin{subarray}{c}t_{i_{1}i_{2}j{\underline{k}}}\in[\pm
M],\\\
j\in[s],\;{\underline{k}}\in{\mathcal{K}},\;i_{1},i_{2}\in[\ell]\end{subarray}}$
$\displaystyle\qquad\qquad\qquad\qquad\prod_{i_{1}\in[\ell]}\prod_{j\in[s]}\;\prod_{\begin{subarray}{c}{\underline{k}}\in{\mathcal{K}}\end{subarray}}\prod_{\begin{subarray}{c}u_{2}\in\\{0,1\\}\end{subarray}}\mathbf{1}\Bigl{(}\sum\limits_{i_{2}\in[\ell]}h_{2k_{1i_{1}}k_{2i_{2}}}^{u_{2}}t_{i_{1}i_{2}j{\underline{k}}}=t_{i_{1}j{\underline{k}}u_{2}}\Bigr{)}$
$\displaystyle\qquad\qquad=\operatorname*{\mathbb{E}}_{\begin{subarray}{c}h_{2k_{1}k_{2}}\in[\pm
H]:\\\
k_{1},k_{2}\in[t]\end{subarray}}\;\mathbf{1}_{{\mathcal{H}}_{2}}((h_{2k_{1}k_{2}})_{k_{1},k_{2}})\prod_{i_{1}\in[\ell]}\prod_{j\in[s]}\;\prod_{\begin{subarray}{c}{\underline{k}}\in{\mathcal{K}}\end{subarray}}$
$\displaystyle\qquad\qquad\qquad\qquad\sum_{\begin{subarray}{c}t_{i_{1}i_{2}j{\underline{k}}}\in[\pm
M]:\\\
i_{2}\in[\ell]\end{subarray}}\;\mathbf{1}\Bigl{(}\sum\limits_{i_{2}\in[\ell]}t_{i_{1}i_{2}j{\underline{k}}}=t_{i_{1}j{\underline{k}}0}\Bigr{)}\cdot\mathbf{1}\Bigl{(}\sum\limits_{i_{2}\in[\ell]}h_{2k_{1i_{1}}k_{2i_{2}}}t_{i_{1}i_{2}j{\underline{k}}}=t_{i_{1}j{\underline{k}}1}\Bigr{)}.$

Lemma 7.3 applied with $l=r=2$ allows us to bound this expression by

$O(\eta^{-O(1)}M^{s\ell^{2}|{\mathcal{K}}|-2s\ell|{\mathcal{K}}|}H^{-s\ell|{\mathcal{K}}|}).$

Similarly, the count of solutions to the system involving the variables
$h_{1k_{1}}$ is

$\displaystyle\max_{\begin{subarray}{c}n_{j{\underline{k}}00},\;n_{j{\underline{k}}01},\\\
n_{j{\underline{k}}10},\;n_{j{\underline{k}}11}\in{\mathbb{Z}}:\\\
j\in[s],\;{\underline{k}}\in{\mathcal{K}}\end{subarray}}\;\operatorname*{\mathbb{E}}_{\begin{subarray}{c}h_{1k_{1}}\in[\pm
H]:\\\
k_{1}\in[t]\end{subarray}}\;\mathbf{1}_{{\mathcal{H}}_{1}}((h_{1k_{1}})_{k_{1}})\sum_{\begin{subarray}{c}t_{i_{1}j{\underline{k}}0}\in[\pm\ell
M],\\\ t_{i_{1}j{\underline{k}}1}\in[\pm\ell HM]:\\\
j\in[s],\;{\underline{k}}\in{\mathcal{K}},\;i_{1}\in[\ell]\end{subarray}}$
$\displaystyle\qquad\qquad\qquad\prod_{j\in[s]}\;\prod_{\begin{subarray}{c}{\underline{k}}\in{\mathcal{K}}\end{subarray}}\prod_{\begin{subarray}{c}{\underline{u}}\in\\{0,1\\}^{2}\end{subarray}}\mathbf{1}\Bigl{(}\sum\limits_{i_{1}\in[\ell]}h_{1k_{1i_{1}}}^{u_{1}}t_{i_{1}j{\underline{k}}u_{2}}=n_{j{\underline{k}}{\underline{u}}}\Bigr{)}$
$\displaystyle\qquad\leq\operatorname*{\mathbb{E}}_{\begin{subarray}{c}h_{1k_{1}}\in[\pm
H]:\\\
k_{1}\in[t]\end{subarray}}\;\mathbf{1}_{{\mathcal{H}}_{1}}((h_{1k_{1}})_{k_{1}})\prod_{j\in[s]}\;\prod_{\begin{subarray}{c}{\underline{k}}\in{\mathcal{K}}\end{subarray}}\prod_{\begin{subarray}{c}u_{2}\in\\{0,1\\}\end{subarray}}$
$\displaystyle\qquad\qquad\qquad\max_{n_{0},n_{1}\in{\mathbb{Z}}}\;\sum_{\begin{subarray}{c}t_{i_{1}j{\underline{k}}u_{2}}\in[\pm\ell
H^{u_{2}}M]:\\\
i_{1}\in[\ell]\end{subarray}}\mathbf{1}\Bigl{(}\sum\limits_{i_{1}\in[\ell]}t_{i_{1}j{\underline{k}}u_{2}}=n_{0}\Bigr{)}\cdot\mathbf{1}\Bigl{(}\sum\limits_{i_{1}\in[\ell]}h_{1k_{1i_{1}}}t_{i_{1}j{\underline{k}}u_{2}}=n_{1}\Bigr{)},$

and this can be bounded by

$O(\eta^{-O(1)}M^{2s\ell|{\mathcal{K}}|-4s|{\mathcal{K}}|}H^{s\ell|{\mathcal{K}}|-4s|{\mathcal{K}}|})$

using the case $l=1,r=2$ of Lemma 7.3. Note that the big centered equations
had an _inequality_ rather than an _equality_ because we interchanged the
$\max$ with the sums and products.

Combining these two bounds and the normalising factor
$O(M^{-s\ell^{2}|{\mathcal{K}}|})$, we bound the overall normalised count by

$\displaystyle\ll
M^{-s\ell^{2}|{\mathcal{K}}|}\cdot\mathopen{}\left(\eta^{-O(1)}M^{s\ell^{2}|{\mathcal{K}}|-2s\ell|{\mathcal{K}}|}H^{-s\ell|{\mathcal{K}}|}\mathclose{}\right)\cdot\mathopen{}\left(\eta^{-O(1)}M^{2s\ell|{\mathcal{K}}|-4s|{\mathcal{K}}|}H^{s\ell|{\mathcal{K}}|-4s|{\mathcal{K}}|}\mathclose{}\right)$
$\displaystyle=\eta^{-O(1)}M^{-4s|{\mathcal{K}}|}H^{-4s|{\mathcal{K}}|},$

as claimed.

The case $r>2$.

We handle the case $r>2$ similarly. For $l\in[r]$,
$i_{1},\ldots,i_{l}\in[\ell]$, $j\in[s]$, ${\underline{k}}\in{\mathcal{K}}$,
${\underline{u}}\in\\{0,1\\}^{r}$, we define the auxiliary variable

$\displaystyle t_{i_{1}\cdots
i_{l}j{\underline{k}}{\underline{u}}}=\sum\limits_{i_{l+1},\ldots,i_{r}\in[\ell]}h_{(l+1)k_{1i_{1}}\cdots
k_{(l+1)i_{l+1}}}^{u_{l+1}}\cdots h_{rk_{1i_{1}}\cdots
k_{ri_{r}}}^{u_{r}}m_{j{\underline{k}}i_{1}\cdots i_{r}}$

at scale $H^{u_{l+1}+\cdots+u_{r}}M$. Notice that $t_{i_{1}\cdots
i_{l}j{\underline{k}}{\underline{u}}}$ depends on only the coordinates
$u_{l+1},\ldots,u_{r}$ of ${\underline{u}}$ and that the $t$’s satisfy the
relation

(47) $\displaystyle t_{i_{1}\cdots
i_{l}j{\underline{k}}{\underline{u}}}=\sum_{i_{l+1}\in[\ell]}h_{(l+1)k_{1i_{1}}\cdots
k_{(l+1)i_{l+1}}}^{u_{l+1}}t_{i_{1}\cdots
i_{l+1}j{\underline{k}}{\underline{u}}}.$

Iterating (47) through intermediate scales, we see that for each $j\in[s]$ and
${\underline{k}}\in{\mathcal{K}}$, we can rewrite

$\displaystyle\sum_{\begin{subarray}{c}m_{j{\underline{k}}i_{1}\cdots
i_{r}}\in[\pm M]:\\\
i_{1},\ldots,i_{r}\in[\ell]\end{subarray}}\mathbf{1}\Bigl{(}\sum\limits_{i_{1},\ldots,i_{r}\in[\ell]}h_{1k_{1i_{1}}}^{u_{1}}\cdots
h_{rk_{1i_{1}}\cdots k_{ri_{r}}}^{u_{r}}m_{j{\underline{k}}i_{1}\cdots
i_{r}}=n_{j{\underline{k}}{\underline{u}}}\Bigr{)}$
$\displaystyle\qquad\qquad\qquad=\sum_{\begin{subarray}{c}|t_{i_{1}j{\underline{k}}{\underline{u}}}|\ll
H^{u_{2}+\cdots+u_{r}}M:\\\
i_{1}\in[\ell]\end{subarray}}\mathbf{1}\Bigl{(}\sum\limits_{i_{1}\in[\ell]}h_{1k_{1i_{1}}}^{u_{1}}t_{i_{1}j{\underline{k}}{\underline{u}}}=n_{j{\underline{k}}{\underline{u}}}\Bigr{)}$
$\displaystyle\qquad\qquad\qquad\times\sum_{\begin{subarray}{c}|t_{i_{1}i_{2}j{\underline{k}}{\underline{u}}}|\ll
H^{u_{3}+\cdots+u_{r}}M:\\\
i_{1},i_{2}\in[\ell]\end{subarray}}\;\prod_{i_{1}\in[\ell]}\mathbf{1}\Bigl{(}\sum\limits_{i_{2}\in[\ell]}h_{2k_{1i_{1}}k_{2i_{2}}}^{u_{2}}t_{i_{1}i_{2}j{\underline{k}}{\underline{u}}}=t_{i_{1}j{\underline{k}}{\underline{u}}}\Bigr{)}$
$\displaystyle\qquad\qquad\qquad\times\cdots\times\sum_{\begin{subarray}{c}|t_{i_{1}\cdots
i_{r}j{\underline{k}}{\underline{u}}}|\leq M:\\\
i_{1},\cdots,i_{r}\in[\ell]\end{subarray}}\;\prod_{i_{1},\ldots,i_{r-1}\in[\ell]}\mathbf{1}\Bigl{(}\sum\limits_{i_{r}\in[\ell]}h_{rk_{1i_{1}}\cdots
k_{ri_{r}}}^{u_{r}}t_{i_{1}\cdots
i_{r}j{\underline{k}}{\underline{u}}}=t_{i_{1}\ldots
i_{r-1}j{\underline{k}}{\underline{u}}}\Bigr{)},$

where we note that $t_{i_{1}\cdots
i_{r}j{\underline{k}}{\underline{u}}}=m_{j{\underline{k}}i_{1}\cdots i_{r}}$.
Hence our normalized count is bounded by $O(M^{-s\ell^{r}|{\mathcal{K}}|})$
times

$\displaystyle\max_{\begin{subarray}{c}n_{j{\underline{k}}{\underline{u}}}\in{\mathbb{Z}}:\;j\in[s],\\\
{\underline{k}}\in{\mathcal{K}},\;{\underline{u}}\in\\{0,1\\}^{r}\end{subarray}}\;\operatorname*{\mathbb{E}}_{\begin{subarray}{c}h_{1k_{1}}\in[\pm
H]:\\\
k_{1}\in[t]\end{subarray}}\;\mathbf{1}_{{\mathcal{H}}_{1}}((h_{1k_{1}})_{k_{1}})\sum_{\begin{subarray}{c}|t_{i_{1}j{\underline{k}}{\underline{u}}}|\ll
H^{u_{2}+\cdots+u_{r}}M:\;j\in[s],\\\
{\underline{k}}\in{\mathcal{K}},\;u_{2},\ldots,u_{r}\in\\{0,1\\},\;i_{1}\in[\ell]\end{subarray}}$
$\displaystyle\qquad\qquad\qquad\qquad\Big{(}\prod_{j\in[s]}\;\prod_{\begin{subarray}{c}{\underline{k}}\in{\mathcal{K}}\end{subarray}}\;\prod_{\begin{subarray}{c}u_{1},\ldots,u_{r}\in\\{0,1\\}\end{subarray}}\mathbf{1}\Bigl{(}\sum\limits_{i_{1}\in[\ell]}h_{1k_{1i_{1}}}^{u_{1}}t_{i_{1}j{\underline{k}}{\underline{u}}}=n_{j{\underline{k}}{\underline{u}}}\Bigr{)}\Big{)}$
$\displaystyle\qquad\qquad\times\operatorname*{\mathbb{E}}_{\begin{subarray}{c}h_{2k_{1}k_{2}}\in[\pm
H]:\\\
k_{1},k_{2}\in[t]\end{subarray}}\;\mathbf{1}_{{\mathcal{H}}_{2}}((h_{2k_{1}k_{2}})_{k_{1},k_{2}})\;\sum_{\begin{subarray}{c}|t_{i_{1}i_{2}j{\underline{k}}{\underline{u}}}|\ll
H^{u_{3}+\cdots+u_{r}}M:\;j\in[s],\\\
{\underline{k}}\in{\mathcal{K}},\;u_{3},\ldots,u_{r}\in\\{0,1\\},\;i_{1},i_{2}\in[\ell]\end{subarray}}$
$\displaystyle\qquad\qquad\qquad\qquad\Big{(}\prod_{i_{1}\in[\ell]}\;\prod_{j\in[s]}\;\prod_{\begin{subarray}{c}{\underline{k}}\in{\mathcal{K}}\end{subarray}}\;\prod_{\begin{subarray}{c}u_{2},\ldots,u_{r}\in\\{0,1\\}\end{subarray}}\mathbf{1}\Bigl{(}\sum\limits_{i_{2}\in[\ell]}h_{2k_{1i_{1}}k_{2i_{2}}}^{u_{2}}t_{i_{1}i_{2}j{\underline{k}}{\underline{u}}}=t_{i_{1}j{\underline{k}}{\underline{u}}}\Bigr{)}\Big{)}$
$\displaystyle\qquad\qquad\times\cdots\times\operatorname*{\mathbb{E}}_{\begin{subarray}{c}h_{rk_{1}\cdots
k_{r}}\in[\pm H]:\\\
k_{1},\ldots,k_{r}\in[t]\end{subarray}}\;\mathbf{1}_{{\mathcal{H}}_{r}}((h_{rk_{1}\cdots
k_{r}})_{k_{1},\ldots,k_{r}})\;\sum_{\begin{subarray}{c}|t_{i_{1}\cdots
i_{r}j{\underline{k}}{\underline{u}}}|\leq M:\;j\in[s],\\\
{\underline{k}}\in{\mathcal{K}},\;i_{1},\ldots,i_{r}\in[\ell]\end{subarray}}$
$\displaystyle\qquad\qquad\qquad\qquad\prod_{i_{1},\ldots,i_{r-1}\in[\ell]}\;\prod_{j\in[s]}\;\prod_{\begin{subarray}{c}{\underline{k}}\in{\mathcal{K}}\end{subarray}}\;\prod_{\begin{subarray}{c}u_{r}\in\\{0,1\\}\end{subarray}}\mathbf{1}\Bigl{(}\sum\limits_{i_{r}\in[\ell]}h_{rk_{1i_{1}}\cdots
k_{ri_{r}}}^{u_{r}}t_{i_{1}\cdots
i_{r}j{\underline{k}}{\underline{u}}}=t_{i_{1}\cdots
i_{r-1}j{\underline{k}}{\underline{u}}}\Bigr{)}.$

As in the case $r=2$, we have decoupled our original system of degree-$r$
multilinear equations into $r$ smaller systems, each consisting of a pair of
multilinear equations at consecutive scales. We will next use Lemma 7.3 to
bound the counts of solutions for these subsystems individually, starting from
the system involving the variables $h_{rk_{1}\cdots k_{r}}$. The count of
solutions to this system can be rephrased as

$\operatorname*{\mathbb{E}}_{\begin{subarray}{c}h_{rk_{1}\cdots k_{r}}\in[\pm
H]:\\\
k_{1},\ldots,k_{r}\in[t]\end{subarray}}\;\mathbf{1}_{{\mathcal{H}}_{r}}((h_{rk_{1}\cdots
k_{r}})_{k_{1},\ldots,k_{r}})\prod_{i_{1},\ldots,i_{r-1}\in[\ell]}\;\prod_{j\in[s]}\;\prod_{\begin{subarray}{c}{\underline{k}}\in{\mathcal{K}}\end{subarray}}\\\
\sum_{\begin{subarray}{c}|t_{i_{1}\cdots
i_{r}j{\underline{k}}{\underline{u}}}|\leq M:\\\
i_{r}\in[\ell]\end{subarray}}\
\prod_{\begin{subarray}{c}u_{r}\in\\{0,1\\}\end{subarray}}\mathbf{1}\Bigl{(}\sum\limits_{i_{r}\in[\ell]}h_{rk_{1i_{1}}\cdots
k_{ri_{r}}}^{u_{r}}t_{i_{1}\cdots
i_{r}j{\underline{k}}{\underline{u}}}=t_{i_{1}\cdots
i_{r-1}j{\underline{k}}{\underline{u}}}\Bigr{)},$

and bounded by
$\ll\eta^{-O(1)}M^{s\ell^{r}|{\mathcal{K}}|-2s\ell^{r-1}|{\mathcal{K}}|}H^{-s\ell^{r-1}|{\mathcal{K}}|}$
using the case $l=r$ of Lemma 7.3. Similarly, the count corresponding to the
system involving the variables $h_{(r-1)k_{1}\cdots k_{r-1}}$ can be rephrased
as

$\operatorname*{\mathbb{E}}_{\begin{subarray}{c}h_{(r-1)k_{1}\cdots
k_{r-1}}\in[\pm H]:\\\
k_{1},\ldots,k_{r-1}\in[t]\end{subarray}}\;\mathbf{1}_{{\mathcal{H}}_{r-1}}((h_{(r-1)k_{1}\cdots
k_{r-1}})_{k_{1},\ldots,k_{r-1}})\prod_{i_{1},\ldots,i_{r-2}\in[\ell]}\;\prod_{j\in[s]}\;\prod_{\begin{subarray}{c}{\underline{k}}\in{\mathcal{K}}\end{subarray}}\;\prod_{\begin{subarray}{c}u_{r}\in\\{0,1\\}\end{subarray}}\\\
\sum_{\begin{subarray}{c}|t_{i_{1}\cdots
i_{r-1}j{\underline{k}}{\underline{u}}}|\ll H^{u_{r}}M:\\\
i_{r-1}\in[\ell]\end{subarray}}\
\prod_{\begin{subarray}{c}u_{r-1}\in\\{0,1\\}\end{subarray}}\mathbf{1}\Bigl{(}\sum\limits_{i_{r-1}\in[\ell]}h_{(r-1)k_{1i_{1}}\cdots
k_{(r-1)i_{r-1}}}^{u_{r-1}}t_{i_{1}\cdots
i_{r-1}j{\underline{k}}{\underline{u}}}=t_{i_{1}\cdots
i_{r-2}j{\underline{k}}{\underline{u}}}\Bigr{)}$

and bounded by

$\displaystyle\ll\eta^{-O(1)}M^{2s\ell^{r-1}|{\mathcal{K}}|-s\ell^{r}|{\mathcal{K}}|-4s\ell^{r-1}|{\mathcal{K}}|}H^{s\ell^{r-1}|{\mathcal{K}}|-4s\ell^{r-1}|{\mathcal{K}}|}$

with the help of the case $l=r-1$ of Lemma 7.3. Continuing in this manner and
combining the results, we can bound our initial normalized count by

$\displaystyle\ll
M^{-s\ell^{r}|{\mathcal{K}}|}\cdot\prod_{l\in[r]}\eta^{-O(1)}M^{2^{r-l}s\ell^{l}|{\mathcal{K}}|-2^{r-l+1}s\ell^{l-1}|{\mathcal{K}}|}$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad
H^{(r-l)2^{r-l-1}s\ell^{l}|{\mathcal{K}}|-(r-l+1)2^{r-l}s\ell^{l-1}|{\mathcal{K}}|},$

where in each $l$-multiplicand, the negative exponents of $\eta,M,H$ come from
an application of Lemma 7.3 to bound the count of solutions to the system
involving the variables $h_{lk_{1}\cdots k_{l}}$ and the positive exponents
come from counting the admissible values of the variables $t_{i_{1}\cdots
i_{l}j{\underline{k}}{\underline{u}}}$. The telescoping nature of the
exponents leads to cancellations: The exponents of $M$ and $H$ cancel out as

$\displaystyle-s\ell^{r}|{\mathcal{K}}|+(s\ell^{r}|{\mathcal{K}}|-2s\ell^{r-1}|{\mathcal{K}}|)+\cdots+(2^{r-1}s\ell|{\mathcal{K}}|-2^{r}s|{\mathcal{K}}|)=-2^{r}s|{\mathcal{K}}|,$
$\displaystyle-s\ell^{r-1}|{\mathcal{K}}|+(s\ell^{r-1}|{\mathcal{K}}|-4s\ell^{r-2}|{\mathcal{K}}|)+\cdots+((r-1)2^{r-2}s\ell|{\mathcal{K}}|-r2^{r-1}s|{\mathcal{K}}|)=-r2^{r-1}s|{\mathcal{K}}|,$

respectively, yielding the desired final bound

$\displaystyle\ll\eta^{-O(1)}M^{-2^{r}s|{\mathcal{K}}|}H^{-r2^{r-1}s|{\mathcal{K}}|}.$

∎

The last result in this section ensures that the set ${\mathcal{H}}_{l,\eta}$
fills almost all of $[\pm H]^{t^{l}}$ when $\eta>0$ is small.

######  Lemma 7.8.

Let $\eta>0$, $H,l,t\in{\mathbb{N}}$, and let
${\mathcal{H}}={\mathcal{H}}_{l,\eta}$ be as in (45). Then all but an
$O_{l,t}(\eta)$-proportion of the elements of $[\pm H]^{t^{l}}$ lie in
${\mathcal{H}}$.

###### Proof.

Setting $k=(k_{1},\ldots,k_{l})$ and $h_{k}=h_{lk_{1},\ldots,k_{l}}$, we can
rewrite

$\displaystyle{\mathcal{H}}=\\{(h_{k})_{k\in[t^{l}]}\in[\pm H]^{t^{l}}:\;$
$\displaystyle\gcd(h_{k}-h_{k^{\prime\prime}},h_{k^{\prime}}-h_{k^{\prime\prime}})\leq\eta^{-1},$
$\displaystyle|h_{k}|\geq\eta H\;\textrm{for all
distinct}\;k,k^{\prime},k^{\prime\prime}\in[t^{l}]\\}.$

We will show that there are very few elements of $[\pm H]^{t^{l}}$ failing
each condition for membership in ${\mathcal{H}}$, and then we will use the
union bound to conclude that $[\pm H]^{t^{l}}\setminus{\mathcal{H}}$ is small.
For the gcd condition, we estimate

$\displaystyle\operatorname*{\mathbb{E}}_{h,h^{\prime},h^{\prime\prime}\in[\pm
H]}\mathbf{1}\mathopen{}\left(\gcd(h-h^{\prime\prime},h^{\prime}-h^{\prime\prime})\geq\eta^{-1}\mathclose{}\right)$
$\displaystyle\ll\operatorname*{\mathbb{E}}_{h,h^{\prime}\in[\pm
2H]}\mathbf{1}\mathopen{}\left(\gcd(h,h^{\prime})\geq\eta^{-1}\mathclose{}\right)$
$\displaystyle\ll\frac{1}{H^{2}}\sum_{g=\eta^{-1}}^{2H}\sum_{h,h^{\prime}\in[\pm
2H]}\mathbf{1}\mathopen{}\left(g|h,h^{\prime}\mathclose{}\right)$
$\displaystyle\ll\frac{1}{H^{2}}\sum_{g=\eta^{-1}}^{2H}(H/g)^{2}$
$\displaystyle=\sum_{g=\eta^{-1}}^{2H}\frac{1}{g^{2}}\ll\eta.$

For the size condition, we note that $|h|<\eta H$ for an $O(\eta)$-fraction of
$h\in[\pm H]$. The conclusion of the lemma now follows from the union bound. ∎

##  8\. Concatenation along polynomials

In this section, we combine the conclusions of the previous two sections in
order to complete the proof of Theorem 1.10. First, we specialize the results
of Section 6 to averages of polynomial box norms.

######  Proposition 8.1.

Let $d,r,s\in{\mathbb{N}}$ with $d\leq r$, and let $\ell$ be a power of $2$.
There exists a positive integer $t=O_{\ell,r,s}(1)$ such that the following
holds. Let $\delta>0$ and $D,H,M,N,V\in{\mathbb{N}}$ satisfy $H^{d}MV\leq N$,
and let
${\textbf{C}}_{1},\ldots,{\textbf{C}}_{s}\in{\mathbb{Z}}^{D}[{\underline{h}}]$
be polynomials of degree at most $d$ with coefficients of size at most $V$.
Then for all $1$-bounded functions $f:{\mathbb{Z}}^{D}\to{\mathbb{C}}$
supported on $[N]^{D}$, the bound

(48) $\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\operatorname*{\mathbb{E}}_{\begin{subarray}{c}h_{lk_{1}\cdots
k_{l}}\in[\pm H]:\\\
l\in[r],\;k_{1},\ldots,k_{r}\in[t]\end{subarray}}\left\|f\right\|_{\begin{subarray}{c}\\{\sum_{i_{1},\ldots,i_{r}=1}^{\ell}{\textbf{C}}_{j}(h_{1k_{1i_{1}}},\ldots,h_{rk_{1i_{1}}\cdots
k_{ri_{r}}})\cdot[\pm M]:\\\
j\in[s],\;{\underline{k}}\in{\mathcal{K}}\\}\end{subarray}}^{2^{w}}\gg_{D,\ell,r,s}\delta^{O_{\ell,r,s}(1)}N^{D},$

where ${\mathcal{K}}={\mathcal{K}}_{t,\ell,r}$ and $w$ is the degree of the
box norms appearing.

###### Proof.

The proof consists of several applications of Corollary 6.4. First, we apply
it with the indexing set ${\underline{h}}\in[\pm H]^{r}$ to obtain a natural
number $t_{1}=O_{\ell,s}(1)$ such that

$\displaystyle\operatorname*{\mathbb{E}}_{{\underline{h}}_{1},\ldots,{\underline{h}}_{t_{1}}\in[\pm
H]^{r}}\left\|f\right\|_{\begin{subarray}{c}\\{{\textbf{C}}_{j}({\underline{h}}_{k_{11}})\cdot[\pm
M]+\cdots+{\textbf{C}}_{j}({\underline{h}}_{k_{1\ell}})\cdot[\pm M]:\\\
j\in[s],\;1\leq k_{11}<\cdots<k_{1\ell}\leq
t_{1}\\}\end{subarray}}^{2^{w_{1}}}\gg_{D,\ell,s}\delta^{O_{\ell,s}(1)}N^{D},$

where $w_{1}$ is the degree of the box norms appearing.

For the second application of Corollary 6.4, we write
${\underline{h}}_{k}=(h_{1k},\tilde{{\underline{h}}}_{1k})$ and take the
indexing set to be the set of tuples
$(\tilde{{\underline{h}}}_{11},\ldots,\tilde{{\underline{h}}}_{1t_{1}})\in[\pm
H]^{(r-1)t_{1}}$. Then Corollary 6.4, applied separately for each fixed choice
of $h_{11},\ldots,h_{1t_{1}}$, gives $t_{2}=O_{\ell,s}(1)$ for which

$\operatorname*{\mathbb{E}}_{\begin{subarray}{c}h_{1k_{1}}\in[\pm H]:\\\
k_{1}\in[t_{1}]\end{subarray}}\;\operatorname*{\mathbb{E}}_{\begin{subarray}{c}\tilde{{\underline{h}}}_{1k_{1}k_{2}}\in[\pm
H]^{r-1}:\\\
k_{1}\in[t_{1}],\;k_{2}\in[t_{2}]\end{subarray}}\;\left\|f\right\|_{\begin{subarray}{c}\\{{\textbf{C}}_{j}(h_{1k_{11}},\tilde{{\underline{h}}}_{1k_{11}k_{21}})\cdot[\pm
M]+\cdots+{\textbf{C}}_{j}(h_{1k_{11}},\tilde{{\underline{h}}}_{1k_{11}k_{2\ell}})\cdot[\pm
M]\\\
+\cdots+{\textbf{C}}_{j}(h_{1k_{1\ell}},\tilde{{\underline{h}}}_{1k_{1\ell}k_{21}})\cdot[\pm
M]+\cdots+{\textbf{C}}_{j}(h_{1k_{1\ell}},\tilde{{\underline{h}}}_{1k_{1\ell}k_{2\ell}})\cdot[\pm
M]:\\\ j\in[s],\;1\leq k_{11}<\cdots<k_{1\ell}\leq t_{1},\;1\leq
k_{21}<\cdots<k_{2\ell}\leq t_{2}\\}\end{subarray}}^{2^{w_{2}}}\\\
\gg_{D,\ell,s}\delta^{O_{\ell,s}(1)}N^{D},$

where $w_{2}$ is the degree of the box norms appearing.

For the next step, we similarly write
$\tilde{{\underline{h}}}_{1k_{1}k_{2}}=(h_{2k_{1}k_{2}},\tilde{h}_{2k_{1}k_{2}})$
and take our indices to be the tuples
$(\tilde{h}_{2k_{1}k_{2}})_{k_{1}\in[t_{1}],k_{2}\in[t_{2}]}\in[\pm
H]^{(r-2)t_{1}t_{2}}$. Applying Corollary 6.4 separately for each
$h_{1k_{1}},h_{2k_{1}k_{2}}\in[\pm H]$, with
$k_{1}\in[t_{1}],k_{2}\in[t_{2}]$, we obtain $t_{3}=O_{\ell,s}(1)$ for which

$\operatorname*{\mathbb{E}}_{\begin{subarray}{c}h_{1k_{1}}\in[\pm H]:\\\
k_{1}\in[t_{1}]\end{subarray}}\;\operatorname*{\mathbb{E}}_{\begin{subarray}{c}h_{1k_{1}k_{2}}\in[\pm
H]:\\\
k_{1}\in[t_{1}],\;k_{2}\in[t_{2}]\end{subarray}}\;\operatorname*{\mathbb{E}}_{\begin{subarray}{c}\tilde{{\underline{h}}}_{2k_{1}k_{2}k_{3}}\in[\pm
H]^{r-2}:\\\
k_{1}\in[t_{1}],\;k_{2}\in[t_{2}],\;k_{3}\in[t_{3}]\end{subarray}}\\\
\left\|f\right\|_{\begin{subarray}{c}\\{\sum_{i_{1},i_{2},i_{3}=1}^{\ell}{\textbf{C}}_{j}(h_{1k_{1i_{1}}},h_{2k_{1i_{1}}k_{2i_{2}}},\tilde{{\underline{h}}}_{2k_{1i_{1}}k_{2i_{2}}k_{3i_{3}}})\cdot[\pm
M]:\\\ j\in[s],\;1\leq k_{l1}<\cdots<k_{l\ell}\leq
t_{l},\;l\in[3]\\}\end{subarray}}^{2^{w_{3}}}\\\
\gg_{D,\ell,s}\delta^{O_{\ell,s}(1)}N^{D},$

where $w_{3}$ is the degree of the box norms appearing. Continuing in this
fashion $r-2$ more times, we obtain $t_{3},\ldots,t_{r}=O_{\ell,r,s}(1)$ such
that

$\displaystyle\operatorname*{\mathbb{E}}_{\begin{subarray}{c}h_{lk_{1}\cdots
k_{l}}\in[\pm H]:\\\
l\in[r],\;k_{l}\in[t_{l}]\end{subarray}}\;\left\|f\right\|_{\begin{subarray}{c}\\{\sum_{i_{1},\ldots,i_{r}=1}^{\ell}{\textbf{C}}_{j}(h_{1k_{1i_{1}}},\ldots,h_{rk_{1i_{1}}\cdots
k_{ri_{r}}})\cdot[\pm M]:\\\ j\in[s],\;1\leq k_{l1}<\cdots<k_{l\ell}\leq
t_{l},\;l\in[r]\\}\end{subarray}}^{2^{w_{r}}}\gg_{D,\ell,r,s}\delta^{O_{\ell,r,s}(1)}N^{D},$

where $w_{r}$ is the degree of the box norms appearing.

Although this inequality is just as useful as the conclusion of the
proposition, it will later be notationally convenient to replace the $t_{l}$’s
with a single parameter. Setting $t=\max(t_{1},\ldots,t_{r})$ and noting that
the coordinates of the polynomial

$\sum_{i_{1},\ldots,i_{r}=1}^{\ell}{\textbf{C}}_{j}(h_{1k_{1i_{1}}},\ldots,h_{rk_{1i_{1}}\cdots
k_{ri_{r}}})$

are at most $O_{d,r,\ell}(VH^{d})$ for all valid choices of the $h$’s, we
deduce that

$\displaystyle\sum_{i_{1},\ldots,i_{r}=1}^{\ell}{\textbf{C}}_{j}(h_{1k_{1i_{1}}},\ldots,h_{rk_{1i_{1}}\cdots
k_{ri_{r}}})\cdot[\pm M]\subset[-AN,AN]^{D}$

for some $A=O_{d,\ell,r,s}(1)$; it is here that we are using the assumption on
the coefficients of ${\textbf{C}}_{1},\ldots,{\textbf{C}}_{s}$ and the bound
$H^{d}MV\leq N$. We then deduce the result from the monotonicity property of
box norms (Lemma 3.5(iii)). ∎

We will finally use Proposition 8.1, together with the equidistribution
results from Section 7, to prove Theorem 1.10, which we restate for
convenience.

######  Theorem (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}].$

###### Proof.

We let all implicit constants depend on $D,\ell,r,s$171717and also on $d$,
which, however, is bounded by $r$ and note that the powers of $\delta$
appearing in the proof will be independent of $D$. We also let
${\mathcal{K}}={\mathcal{K}}_{t,\ell,r}$, which we recall from Section 7 is
the set of admissible tuples of indices

$\displaystyle{\mathcal{K}}=\\{(k_{li})_{\begin{subarray}{c}(l,i)\in[r]\times[\ell]\end{subarray}}\in[t]^{r\ell}:\;1\leq
k_{l1}<\cdots<k_{l\ell}\leq t\;\;\textrm{for\; all}\;\;l\in[r]\\}.$

By Proposition 8.1, there is some positive integer $t=O(1)$ (independent of
$D$) for which

(49)
$\displaystyle\operatorname*{\mathbb{E}}_{\begin{subarray}{c}h_{lk_{1}\cdots
k_{l}}\in[\pm H]:\\\
l\in[r],\;k_{1},\ldots,k_{r}\in[t]\end{subarray}}\left\|f\right\|_{\begin{subarray}{c}\\{\sum\limits_{i_{1},\ldots,i_{r}\in[\ell]}{\textbf{C}}_{j}(h_{1k_{1i_{1}}},\ldots,h_{rk_{1i_{1}}\cdots
k_{ri_{r}}})\cdot[\pm M]:\\\
j\in[s],\;{\underline{k}}\in{\mathcal{K}}\\}\end{subarray}}^{2^{w}}\gg\delta^{O(1)}N^{D},$

where $w$ is the degree of the box norms appearing. We will now make use of
our equidistribution estimates. It is necessary first to restrict to “generic”
tuples of the $h$’s.

Recall from (45) the definition of the set of tuples
${\mathcal{H}}_{l,\eta}\subset[\pm H]^{t^{l}}$, which by Lemma 7.8 contains
all but an $O(\eta)$-proportion of the elements of $[\pm H]^{t^{l}}$. Write
${\mathcal{H}}_{l}={\mathcal{H}}_{l,\eta}$ and take $\eta=c\delta^{1/c}$ for
some $c>0$ sufficiently small that the contribution of tuples
$(h_{lk_{1}\cdots k_{l}})_{k_{1},\ldots,k_{l}}\in[\pm
H]^{l^{t}}\setminus{\mathcal{H}}_{l}$ is at most half (say) of the lower bound
in (49). Removing such “bad” tuples of $h$’s and expanding (49), we obtain

(50) $\operatorname*{\mathbb{E}}_{\begin{subarray}{c}h_{lk_{1}\cdots
k_{l}}\in[\pm H]:\\\
l\in[r],\;k_{1},\ldots,k_{r}\in[t]\end{subarray}}\;\mathopen{}\left(\prod_{l\in[r]}\mathbf{1}_{{\mathcal{H}}_{l}}((h_{lk_{1}\cdots
k_{l}})_{k_{1},\ldots,k_{l}})\mathclose{}\right)\sum_{\begin{subarray}{c}m_{j{\underline{k}}i_{1}\cdots
i_{r}}\in[\pm M]:\\\
j\in[s],\;{\underline{k}}\in{\mathcal{K}},\;i_{1},\ldots,i_{r}\in[\ell]\end{subarray}}\mu_{M}((m_{j{\underline{k}}i_{1}\cdots
i_{r}})_{j,{\underline{k}},i_{1},\ldots,i_{r}})\\\
\sum_{x}\Delta_{\begin{subarray}{c}\\{\sum\limits_{i_{1},\ldots,i_{r}\in[\ell]}{\textbf{C}}_{j}(h_{1k_{1i_{1}}},\ldots,h_{rk_{1i_{1}}\cdots
k_{ri_{r}}})m_{j{\underline{k}}i_{1}\cdots i_{r}}:\\\
j\in[s],\;{\underline{k}}\in{\mathcal{K}}\\}\end{subarray}}\;f(x)\gg\delta^{O(1)}N^{D}.$

For each $j\in[s]$, ${\underline{k}}\in{\mathcal{K}}$,
${\underline{u}}\in\\{0,1\\}^{r}$, we introduce dummy variables

(51) $\displaystyle
n_{j{\underline{k}}{\underline{u}}}=\sum\limits_{i_{1},\ldots,i_{r}\in[\ell]}h_{1k_{1i_{1}}}^{u_{1}}\cdots
h_{rk_{1i_{1}}\cdots k_{ri_{r}}}^{u_{r}}m_{j{\underline{k}}i_{1}\cdots i_{r}}$

at scale $H^{u_{1}+\cdots+u_{r}}M$, and we define

${\mathcal{N}}({\underline{n}})=\operatorname*{\mathbb{E}}_{\begin{subarray}{c}m_{j{\underline{k}}i_{1}\cdots
i_{r}}\in[\pm M]:\\\
j\in[s],\;{\underline{k}}\in{\mathcal{K}},\;i_{1},\ldots,i_{r}\in[\ell]\end{subarray}}\;\operatorname*{\mathbb{E}}_{\begin{subarray}{c}h_{lk_{1}\cdots
k_{l}}\in[\pm H]:\\\
l\in[r],\;k_{1},\ldots,k_{r}\in[t]\end{subarray}}\;\mathopen{}\left(\prod_{l\in[r]}\mathbf{1}_{{\mathcal{H}}_{l}}((h_{lk_{1}\cdots
k_{l}})_{k_{1},\ldots,k_{l}})\mathclose{}\right)\\\
\prod_{j\in[s]}\;\prod_{\begin{subarray}{c}{\underline{k}}\in{\mathcal{K}}\end{subarray}}\prod_{\begin{subarray}{c}{\underline{u}}\in\\{0,1\\}^{r}\end{subarray}}\mathbf{1}\mathopen{}\left(\sum\limits_{i_{1},\ldots,i_{r}\in[\ell]}h_{1k_{1i_{1}}}^{u_{1}}\cdots
h_{rk_{1i_{1}}\cdots k_{ri_{r}}}^{u_{r}}m_{j{\underline{k}}i_{1}\cdots
i_{r}}=n_{j{\underline{k}}{\underline{u}}}\mathclose{}\right).$

In words, the kernel ${\mathcal{N}}({\underline{n}})$ is the probability that
(51) is satisfied when the $m$’s are chosen (independently, uniformly) at
random from $[\pm M]$ and the tuples of $h$’s are chosen (independently,
uniformly) at random from the sets ${\mathcal{H}}_{l}$. Inserting the
definition of ${\mathcal{N}}({\underline{n}})$ into (50) and applying the
triangle inequality gives us the neat bound

$\displaystyle\sum_{\begin{subarray}{c}n_{j{\underline{k}}{\underline{u}}}\ll
H^{|{\underline{u}}|}M:\\\
j\in[s],\;{\underline{k}}\in{\mathcal{K}},\;{\underline{u}}\in\\{0,1\\}^{r}\end{subarray}}{\mathcal{N}}({\underline{n}})\cdot\mathopen{}\left|\sum_{\textbf{x}}\Delta_{\\{\sum_{\begin{subarray}{c}{\underline{u}}\in\\{0,1\\}^{r}\end{subarray}}{\boldsymbol{\gamma}}_{j{\underline{u}}}n_{j{\underline{k}}{\underline{u}}}:\;j\in[s],\;{\underline{k}}\in{\mathcal{K}}\\}}f({\textbf{x}})\mathclose{}\right|\gg\delta^{O(1)}N^{D}.$

The kernel ${\mathcal{N}}$ is supported on the tuples
$(n_{j{\underline{k}}{\underline{u}}})_{j,{\underline{k}},{\underline{u}}}$
satisfying $n_{j{\underline{k}}{\underline{u}}}\ll H^{|{\underline{u}}|}M$, of
which there are

$\displaystyle\ll\prod_{j\in[s]}\prod_{{\underline{k}}\in{\mathcal{K}}}\prod_{{\underline{u}}\in\\{0,1\\}^{r}}H^{|{\underline{u}}|}M\ll
M^{2^{r}s|{\mathcal{K}}|}H^{r2^{r-1}s|{\mathcal{K}}|}.$

It is at this point that we crucially incorporate the bound

(52)
$\displaystyle{\mathcal{N}}({\underline{n}})\ll\delta^{-O(1)}M^{-2^{r}s|{\mathcal{K}}|}H^{-r2^{r-1}s|{\mathcal{K}}|}$

provided by Proposition 7.5 to get the estimate

$\displaystyle\operatorname*{\mathbb{E}}_{\begin{subarray}{c}n_{j{\underline{k}}{\underline{u}}}\ll
H^{|{\underline{u}}|}M:\\\
j\in[s],\;{\underline{k}}\in{\mathcal{K}},\;{\underline{u}}\in\\{0,1\\}^{r}\end{subarray}}\mathopen{}\left|\sum_{\textbf{x}}\Delta_{\\{\sum_{\begin{subarray}{c}{\underline{u}}\in\\{0,1\\}^{r}\end{subarray}}{\boldsymbol{\gamma}}_{j{\underline{u}}}n_{j{\underline{k}}{\underline{u}}}:\;j\in[s],\;{\underline{k}}\in{\mathcal{K}}\\}}f({\textbf{x}})\mathclose{}\right|\gg\delta^{O(1)}N^{D}.$

From here, we use the Cauchy–Schwarz inequality to remove the absolute value
and introduce Fejér kernels, and then use Lemma 3.5(vi) to trim the boxes (as
in the end of the proof sketch of Proposition 5.1). To conclude the proof, we
use Lemma 3.5 to replace the differencing with respect to $[\pm N]^{D}$ by a
differencing with respect to one of the boxes $E_{j}$; by the monotonicity of
box norms, we can also increase the multiplicity of every other $E_{i}$ by
$1$, and we conclude the theorem with $t+1$ in place of $t$. ∎

##  9\. Proof of Theorem 1.6

We conclude by deriving Theorem 1.6 from Proposition 4.8 (the output of PET)
and Theorem 1.10 (the concatenation result). Assume that

$\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}.$

Proposition 4.8 gives us $r,s=O_{d,\ell}(1)$ and nonzero $r$-variable
multilinear polynomials
${\textbf{C}}_{1},\ldots,{\textbf{C}}_{s}\in{\mathbb{Z}}^{D}[{\underline{h}}]$
(depending only on ${\textbf{P}}_{1},\ldots,{\textbf{P}}_{\ell}$) of degree at
most $d-1$, such that

$\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}$), for which

$\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}$

holds for all $\delta^{-O_{d,\ell}(1)}\ll_{d,D,\ell}H\leq
M\ll_{d,D,\ell}\delta^{O_{d,\ell}(1)}K$. Furthermore, by property (iii) of
Definition 4.5,
${\boldsymbol{\beta}}_{1(|{\underline{u}}|+1)}-{\boldsymbol{\beta}}_{w_{j{\underline{u}}}(|{\underline{u}}|+1)}$
is the leading coefficient of
${\textbf{P}}_{1}-{\textbf{P}}_{w_{j{\underline{u}}}}$, which implies that

$\displaystyle\deg({\textbf{P}}_{1}-{\textbf{P}}_{w_{j{\underline{u}}}})=|{\underline{u}}|+1.$

By Theorem 1.10 (with $d-1$ in place of $d$), there exists
$t_{0}=O_{d,\ell}(1)$ such that

$\displaystyle\left\|f\right\|_{E_{10}^{t_{0}},\ldots,E_{s0}^{t_{0}}}^{2^{st_{0}}}\gg_{d,D,\ell}\delta^{O_{d,\ell}(1)}N^{D}$

for the boxes

$\displaystyle
E_{j0}=\sum_{\begin{subarray}{c}{\underline{u}}\in\\{0,1\\}^{r},\\\
|{\underline{u}}|\leq
d-1\end{subarray}}d_{1w_{j{\underline{u}}}}!\cdot({\boldsymbol{\beta}}_{1d_{1w_{j{\underline{u}}}}}-{\boldsymbol{\beta}}_{w_{j{\underline{u}}}d_{1w_{j{\underline{u}}}}})\cdot[\pm
H^{d_{1w_{j{\underline{u}}}}}]$

as long as $H^{d-1}MV\leq N$. We now set $H=M\asymp_{d,D,\ell}\delta^{c}K$ for
a suitably large constant $c=c_{d,\ell}>0$, which, together with the
assumption on the size of $K$, ensures that the aforementioned conditions on
$H,M$ are satisfied. Using parts (iv)-(vi) of Lemma 3.5, we perform the
following operations on each box $E_{j0}$: Remove all of the directions making
up $E_{j0}$ except for one direction corresponding to a (nonzero) highest-
degree monomial; enlarge $H$ to $K$ (at the loss of the factor
$O_{d,D,\ell}(\delta^{O_{d,\ell}(1)})$ in the lower bound); and remove the
factor $d_{1w_{j{\underline{u}}}}!$. In total, we replace each box $E_{j0}$ by

$\displaystyle({\boldsymbol{\beta}}_{1d_{1w_{j{\underline{u}}}}}-{\boldsymbol{\beta}}_{w_{j{\underline{u}}}d_{1w_{j{\underline{u}}}}})\cdot[\pm
K^{d_{1w_{j{\underline{u}}}}}]$

for some $w_{j{\underline{u}}}\neq 1$. The theorem now follows, with
$t=t_{0}\ell$, from the monotonicity property of box norms, where we have
implicitly used the bound

$\displaystyle|({\boldsymbol{\beta}}_{1d_{1w_{j{\underline{u}}}}}-{\boldsymbol{\beta}}_{w_{j{\underline{u}}}d_{1w_{j{\underline{u}}}}})\cdot
K^{d_{1w_{j{\underline{u}}}}}|\ll_{D}VK^{d_{1w_{j{\underline{u}}}}}\ll_{d,D,\ell}VK^{d}\leq
N.$

##  10\. One more PET result

In the last section, we prove one more result required in our companion paper
[14].

######  Proposition 10.1.

Let $d,r\in{\mathbb{N}}$ with $d\geq 2$, and let $P\in{\mathbb{Z}}[z]$ be a
polynomial of degree $d$ with coefficients of size at most $V$. There exists a
positive integer $t=O_{d,r}(1)$ such that the following holds. Let $\delta>0$
and $K,N\in{\mathbb{N}}$ satisfy
$\delta^{-O_{d,r}(1)}\ll_{d,r}K\ll_{d,r}(N/V)^{1/d}$. Then for every
$1$-bounded function $f:{\mathbb{Z}}\to{\mathbb{C}}$ supported on $[N]$, the
bound

(53)
$\displaystyle\sum_{h_{1},\ldots,h_{r}}\mu_{K}({\underline{h}})\sum_{x}\operatorname*{\mathbb{E}}_{z\in[K]}\prod_{{\underline{\epsilon}}\in\\{0,1\\}^{r}}{\mathcal{C}}^{|{\underline{\epsilon}}|}f(x+P(z+{\underline{\epsilon}}\cdot{\underline{h}}))\geq\delta
N$

implies that

$\displaystyle\left\|f\right\|_{U^{t}(\beta_{d}\cdot[\pm
N/\beta_{d}])}^{2^{t}}\gg_{d,r}\delta^{O_{d,r}(1)}N,$

where $\beta_{d}$ is the leading coefficient of $P$.

###### Proof.

Write $P(z)=\sum_{i=0}^{d}\beta_{i}z^{i}$. Setting

$\displaystyle
P_{\underline{\epsilon}}(z,{\underline{h}}):=P(z+{\underline{\epsilon}}\cdot{\underline{h}})-P({\underline{\epsilon}}\cdot{\underline{h}}),$

we first show that the family
${\mathcal{Q}}:=\\{P_{\underline{\epsilon}}:\;{\underline{\epsilon}}\in\\{0,1\\}^{r}\\}$
(ordered so that $P_{\underline{1}}$ comes first) descends from
${\mathcal{P}}=\\{P-P(0)\\}$. Indeed, ${\mathcal{Q}}$ is normal, for which it
is crucial that $d\geq 2$, since otherwise
$P_{\underline{\epsilon}}(z,{\underline{h}})=\beta_{1}z$ for every
${\underline{\epsilon}}$, as the contributions of ${\underline{h}}$ are
absorbed into the term not depending on $z$. Moreover, a simple computation
gives that

$\displaystyle P_{\underline{\epsilon}}(z,{\underline{h}})$
$\displaystyle=\sum_{i=0}^{d}z^{i}\sum_{\begin{subarray}{c}{\underline{u}}\in{\mathbb{N}}_{0}^{r}:\;|{\underline{u}}|\leq
d-i,\\\
\operatorname{supp}({\underline{u}})\subseteq\operatorname{supp}({\underline{\epsilon}})\end{subarray}}{{|{\underline{u}}|+i}\choose{{\underline{u}}}}\beta_{|{\underline{u}}|+i}{\underline{h}}^{\underline{u}},$

and hence the formula (23) holds with
$w_{{\underline{\epsilon}}{\underline{u}}}=\mathbf{1}(\operatorname{supp}({\underline{u}})\subseteq\operatorname{supp}({\underline{\epsilon}}))$
and $w_{\underline{u}}=0$. This immediately implies property (i) from
Definition 4.5. One also sees that for distinct
${\underline{\epsilon}},{\underline{\epsilon}}^{\prime}\in\\{0,1\\}^{r}$, the
leading coefficient of
$P_{\underline{\epsilon}}-P_{{\underline{\epsilon}}^{\prime}}$ as a polynomial
in $z$ is
$d\beta_{d}({\underline{\epsilon}}-{\underline{\epsilon}}^{\prime})\cdot{\underline{h}}$.
In particular, the leading coefficient of
$P_{\underline{\epsilon}}-P_{{\underline{\epsilon}}^{\prime}}$ is a
multilinear homogeneous polynomial of degree $1$. This gives property (ii) of
Definition 4.5, and property (iii) follows since $\beta_{d}$ is the leading
coefficient of $P$. Hence ${\mathcal{Q}}$ indeed descends from
${\mathcal{P}}$. This allows us to use Proposition 4.7 to find positive
integers $r^{\prime}=O_{d,r}(1)$ and $m_{1},\ldots,m_{r^{\prime}}$ such that
${\mathcal{Q}}^{\prime}=\partial_{m_{r^{\prime}},\ldots,m_{1}}{\mathcal{Q}}$
is linear in $z$ and has size $s:=|{\mathcal{Q}}^{\prime}|\ll_{d,r}1$.

Since Proposition 4.7 also gives that ${\mathcal{Q}}^{\prime}$ descends from
${\mathcal{P}}$, the members of ${\mathcal{Q}}^{\prime}$ are multilinear
homogeneous polynomials of degree $d-1$ (homogeneity follows from remark (iv)
below Definition 4.5). Letting
${\underline{h}}=(h_{1},\ldots,h_{r^{\prime\prime}})$ from now on with
$r^{\prime\prime}:=r+r^{\prime}$, we can enumerate the elements of
${\mathcal{Q}}^{\prime}$ as

$\displaystyle b_{1}({\underline{h}})z,\ldots,b_{s}({\underline{h}})z,$

where

$\displaystyle b_{j}({\underline{h}})=\sum_{{\underline{u}}\in
I_{j}}d!\beta_{d}{\underline{h}}^{\underline{u}}$

and the sets
$I_{j}\subseteq\\{{\underline{u}}\in\\{0,1\\}^{r^{\prime\prime}}:\;|{\underline{u}}|=d-1\\}$
for $j\in[s]$ are distinct and nonempty.

Applying the Cauchy-Schwarz and van der Corput Inequalities $r^{\prime}$ times
to (53) much like181818Technically, the expression (53) differs from the one
in Proposition 4.8 in that in (53), we have an extra averaging over
$h_{1},\ldots,h_{r}$ upfront. However, the argument for obtaining the bound in
terms of an average of box norms for the averaged expression in (53) goes
exactly the same way as in Proposition 4.8. Check e.g. the proof of [17,
Corollary 4.3] starting from (14) to see why such averaged counting operators
are no harder to analyze than ones without an additional average over
$h_{1},\ldots,h_{r}$ upfront. The applications of the Cauchy-Schwarz and van
der Corput Inequalities give us new shifting parameters
$h_{r+1},\ldots,h_{r^{\prime\prime}}$; hence the polynomial parameters
${\underline{h}}=(h_{1},\ldots,h_{r^{\prime\prime}})$ come from combining the
“old” $h_{1},\ldots,h_{r}$ with the “new”
$h_{r+1},\ldots,h_{r^{\prime\prime}}$. in the proof of Proposition 4.8, we
deduce the bound

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

valid for all $H\ll_{d,\ell}\delta^{O_{d,\ell}(1)}K$. Theorem 1.10 combined
with Lemma 3.5(v) gives a positive integer $t=O_{d,r}(1)$ for which

$\displaystyle\left\|f\right\|_{U^{t}(d!\beta_{d}\cdot[\pm
H^{d}])}^{2^{t}}\gg_{d,r}\delta^{O_{d,r}(1)}N.$

Properties (iii) and (vii) of Lemma 3.5 allow us to replace the progression
$d!\beta_{d}\cdot[\pm H^{d}]$ with $\beta_{d}\cdot[\pm N/\beta_{d}]$ upon
taking
$H\asymp_{d,\ell}\delta^{O_{d,\ell}(1)}K\asymp_{d,\ell}\delta^{O_{d,\ell}(1)}N/V$,
giving the claimed result.

∎

## References

  * [1] V. Bergelson.  Weakly mixing PET.  Ergodic Theory Dynam. Systems, 7(3):337–349, 1987.
  * [2] V. Bergelson and A. Best.  On the polynomial Szemerédi theorem in finite commutative rings.  Preprint 2023, arXiv:2303.17928.
  * [3] V. Bergelson and A. Leibman.  Polynomial extensions of van der Waerden’s and Szemerédi’s theorems.  J. Amer. Math. Soc., 9:725–753, 1996.
  * [4] Q. Chu, N. Frantzikinakis, and B. Host.  Ergodic averages of commuting transformations with distinct degree polynomial iterates.  Proc. Lond. Math. Soc., 102:801–842, 2011.
  * [5] S. Donoso, A. Ferré-Moragues, A. Koutsogiannis, and W. Sun.  Decomposition of multicorrelation sequences and joint ergodicity.  Ergodic Theory Dynam. Systems, 44(2):432–480, 2024.
  * [6] S. Donoso, A. Koutsogiannis, and W. Sun.  Seminorms for multiple averages along polynomials and applications to joint ergodicity.  J. Anal. Math., 146(1):1–64, 2022.
  * [7] W. T. Gowers.  A new proof of Szemerédi’s theorem for arithmetic progressions of length four.  Geom. Funct. Anal., 8:529 – 551, 1998.
  * [8] W. T. Gowers.  Arithmetic progressions in sparse sets.  In Current developments in mathematics, pages 149–196. Int. Press, 2000.
  * [9] W. T. Gowers.  A new proof of Szemerédi’s theorem.  Geom. Funct. Anal., 11(3):465–588, 2001.
  * [10] B. Green and T. Tao.  Linear equations in primes.  Ann. of Math., 171:1753–1850, 2010.
  * [11] B.J. Green.  On arithmetic structures in dense sets of integers.  Duke Math. J., 114:215–238, 2002.
  * [12] R. Han, M. T. Lacey, and F. Yang.  A polynomial Roth theorem for corners in finite fields.  Mathematika, 67(4):885–896, 2021.
  * [13] Z. Kelley and R. Meka.  Strong bounds for 3-progressions.  In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), pages 933–973, 2023.
  * [14] N. Kravitz, B. Kuca, and J. Leng.  Corners with polynomial side length, 2024.  manuscript.
  * [15] B. Kuca.  Further bounds in the polynomial Szemerédi theorem over finite fields.  Acta Arith., 198:77–108, 2021.
  * [16] B. Kuca.  Multidimensional polynomial patterns over finite fields: Bounds, counting estimates and Gowers norm control.  Adv. Math., 448:109700, 2024.
  * [17] B. Kuca.  Multidimensional polynomial Szemerédi theorem in finite fields for polynomials of distinct degrees.  Israel J. Math., 259(2):589–620, 2024.
  * [18] J. Leng.  Efficient equidistribution of periodic nilsequences and applications.  Preprint 2023, arXiv:2306.13820.
  * [19] J. Leng.  A quantitative bound for Szemerédi’s theorem for a complexity one polynomial progression over ${\mathbb{Z}}/N{\mathbb{Z}}$.  Disrete Anal., 5, 2024.  33 pp.
  * [20] J. Leng, M. Sawhney, and A. Sah.  Improved bounds for Szemerédi’s theorem.  Preprint 2024, arXiv:2402.17995.
  * [21] S. Peluse.  Three-term polynomial progressions in subsets of finite fields.  Israel J. Math., 228:379–405, 2018.
  * [22] S. Peluse.  On the polynomial Szemerédi theorem in finite fields.  Duke Math. J., 168(5):749–774, 2019.
  * [23] S. Peluse.  Bounds for sets with no polynomial progressions.  Forum Math. Pi, 8, 2020.
  * [24] S. Peluse and S. Prendiville.  Quantitative bounds in the non-linear Roth theorem.  Preprint 2019, arXiv:1903.02592.
  * [25] S. Peluse and S. Prendiville.  A polylogarithmic bound in the nonlinear Roth theorem.  Int. Math. Res. Not., 2020.  rnaa261.
  * [26] S. Peluse, S. Prendiville, and X. Shao.  Bounds in a popular multidimensional nonlinear Roth theorem, 2024.  manuscript.
  * [27] S. Peluse, A. Sah, and M. Sawhney.  Effective bounds for Roth’s theorem with shifted square common difference.  Preprint 2023, arXiv:2309.08359.
  * [28] S. Prendiville.  Quantitative bounds in the polynomial Szemerédi theorem: the homogeneous case.  Discrete Anal., 5, 2017.  34 pp.
  * [29] S. Prendiville.  The inverse theorem for the nonlinear Roth configuration: an exposition, 2020.  Preprint 2020, arXiv:2003.04121.
  * [30] K. F. Roth.  On certain sets of integers.  J. Lond. Math. Soc., 28(1):104–109, 1953.
  * [31] A. Sárközy.  On difference sets of sequences of integers. I.  Acta Math. Hungar., 31(1-2):125–149, 1978.
  * [32] A. Sárközy.  On difference sets of sequences of integers. III.  Acta Math. Hungar., 31:355–386, 1978.
  * [33] E. Szemerédi.  On sets of integers containing $k$ elements in arithmetic progression.  Acta Arith., 27(1):199–245, 1975.
  * [34] T. Tao and T. Ziegler.  Concatenation theorems for anti-Gowers uniform functions and Host- Kra characteristic factors.  Discrete Anal., 13, 2016.  61 pp.
  * [35] K. Tsinas.  Joint ergodicity of Hardy field sequences.  Trans. Amer. Math. Soc., 376:3191–3263, 2023.