Let $R\ll(M/\eta)^{O(m)^{O(1)}}$ be the period777We use here [21, Lemma B.14],
which says that if $\gamma$ is $Q$-rational, then it is
$O(Q^{O(1)})$-periodic. of $\gamma$. We now pigeonhole in subprogressions
$A^{\prime}$ of $A$ and $B^{\prime}$ of $B$, of common difference $R$ and
lengths

$(\eta/M)^{O(m)^{O(1)}}|A|\ll|A^{\prime}|\leq\sigma|A|\eta^{2}\quad\text{and}\quad(\eta/M)^{O(m)^{O(1)}}|B|\ll|B^{\prime}|\leq\sigma|B|\eta^{2},$

to find some such $A^{\prime},B^{\prime}$ such that

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

Recall that we have the factorization

$g(y+\widetilde{P}_{[\tilde{r},\tilde{V}]}(z))=\varepsilon(y+\widetilde{P}_{[\tilde{r},\tilde{V}]}(z))g^{\prime}(y+\widetilde{P}_{[\tilde{r},\tilde{V}]}(z))\gamma(y+\widetilde{P}_{[\tilde{r},\tilde{V}]}(z)).$

The term $\gamma(y+\widetilde{P}_{[\tilde{r},\tilde{V}]}(z))\Gamma$ is
constant for $y\in A^{\prime}$ and $z\in B^{\prime}$ because
$A^{\prime},B^{\prime}$ have common difference $R$. Thus, there is some
$\gamma_{0}\in G$ such that for such $y,z$, our factorization can be written
as

$\varepsilon(y+\widetilde{P}_{[\tilde{r},\tilde{V}]}(z))g^{\prime}(y+\widetilde{P}_{[\tilde{r}\tilde{V}]}(z))\gamma_{0},$

up to right-multiplication by $\Gamma$. By the smoothness properties of
$\varepsilon$, we have

$\displaystyle
d_{G/\Gamma}(\varepsilon(y+\widetilde{P}_{[\tilde{r},\tilde{V}]}(z)),\varepsilon_{0})\leq\left(\sigma^{-1}/|A|\right)\cdot|A^{\prime}|\leq\eta^{2}\leq\eta/4,$
$\displaystyle\textrm{and}\quad
d_{G/\Gamma}(\varepsilon_{0},\mathrm{id}_{G})\leq\sigma^{-1}\ll(M/\eta)^{O(m)^{O(1)}}$

for some $\varepsilon_{0}\in G$. Then, by the triangle inequality (recall that
$F$ has Lipschitz constant at most $1$), we have

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

By [21, Lemma B.6], we can write $\gamma_{0}=\\{\gamma_{0}\\}[\gamma_{0}]$
where $[\gamma_{0}]\in\Gamma$ and $|\psi(\\{\gamma_{0}\\})|\leq\frac{1}{2}$.
Expanding

$\varepsilon_{0}g^{\prime}(y+\widetilde{P}_{[\tilde{r},\tilde{V}]}(z))\gamma_{0}=\varepsilon_{0}\\{\gamma_{0}\\}(\\{\gamma_{0}\\}^{-1}g^{\prime}(y+\widetilde{P}_{[\tilde{r},\tilde{V}]}(z))\\{\gamma_{0}\\})[\gamma_{0}]$

and setting $\tilde{F}:=F|_{G^{\prime}}(\varepsilon_{0}\\{\gamma_{0}\\}\cdot)$
(this function is $O((M/\eta)^{O(m)^{O(1)}})$-Lipschitz by [21, Lemma B.4]),
we deduce from the normality of $G^{\prime}$ in $G$ that

$\\{\gamma_{0}\\}^{-1}g^{\prime}(y+\widetilde{P}_{[\tilde{r},\tilde{V}]}(z))\\{\gamma_{0}\\}\in\mathrm{poly}(\mathbb{Z},G^{\prime})$

and that

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

Step 4: Completing the iteration.

We continue the iteration by redefining

$\displaystyle A\leadsto A^{\prime},\quad B\leadsto B^{\prime},\quad
g(n)\leadsto\\{\gamma_{0}\\}^{-1}g^{\prime}(n)\\{\gamma_{0}\\},$
$\displaystyle G/\Gamma\leadsto
G^{\prime}/\Gamma^{\prime},\quad\eta\leadsto(\eta/M)^{O(m)^{O(1)}},\quad\text{
and }\quad F\leadsto\tilde{F}.$

Step 5: The special case $s=1$.

When $s=1$ and $k\geq 2$, we have $F(g(n)\Gamma)=e(p(n))$ for some
$p(n)=\sum_{j=0}^{k}\alpha_{j}n^{j}\in\mathbb{R}[n]$. Applying Proposition
6.2, we see that there exists some $q\ll\eta^{-O(m)^{O(1)}}$ such that

$\|q\alpha_{j}\|_{\mathbb{R}/\mathbb{Z}}\ll\frac{(M/\eta)^{O(m)^{O(1)}}}{T^{j}}\quad\textrm{for
all}\quad 2\leq j\leq k.$

Notice that when $n$ is restricted to an arithmetic progression of difference
$q$, the function $\sum_{j=2}^{k}\alpha_{j}n^{j}$ is slowly-varying and $p(n)$
is very close to a constant plus $\alpha_{1}n$ . Combining this with the
pigeonholing argument from Step 2, which lets us replace $A,B$ by arithmetic
progressions of difference $q$, we reduce to the case where $k=1$.

Finally, when $s=1$ and $k=1$, the last case of Proposition 6.2 gives for each
$j\in{\mathcal{V}}$ a positive integer
$q_{j}\ll\eta^{-O(m)^{O(1)}}\leq\exp(\log(1/\delta)^{O(1)})$ and a phase
$\tilde{\alpha}_{j}\in{\mathbb{R}}/{\mathbb{Z}}$ such that

$\displaystyle\|q_{j}(\tilde{a}_{(j,\tilde{V})}(y)+\tilde{\alpha}_{j})\|_{\mathbb{R}/\mathbb{Z}}$
$\displaystyle=\|q_{j}({a}_{(j,\tilde{V})}(y)V^{\prime}-\tilde{\alpha}_{j})\|_{\mathbb{R}/\mathbb{Z}}\ll\frac{(M/\eta)^{O(m)^{O(1)}}}{T}$
$\displaystyle\ll\frac{(M/(\delta\eta))^{O(m)^{O(1)}}\tilde{V}}{N}\leq\exp(\log(1/\delta)^{O(1)})\frac{\tilde{V}}{N}$

for at least $\exp(-(\log(1/\delta))^{O(1)})N/\tilde{V}$ values of
$y\in[N/\tilde{V}]$. Pigeonholing in the residue classes modulo $q_{j}$, we
can find some
$\alpha_{j}\in\\{\frac{\tilde{\alpha_{j}}+\kappa_{j}}{q_{j}}:\kappa_{j}\in[q_{j}]\\}$
such that

$\displaystyle\|{a}_{(j,\tilde{V})}(y)V^{\prime}-{\alpha}_{j}\|_{\mathbb{R}/\mathbb{Z}}\leq\exp(\log(1/\delta)^{O(1)})\frac{\tilde{V}}{N}$

holds for at least $\exp(-(\log(1/\delta))^{O(1)})N/\tilde{V}$ values of
$y\in[N/\tilde{V}]$. For $j\notin{\mathcal{V}}$, we define $\alpha_{j}$
arbitrarily. This completes the proof of Proposition 4.4.

##  7\. Finishing the argument

Recall that

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

where $\nu(z)=d^{-1}1_{[N]}(z)(N/z)^{(d-1)/d}$. Our goal in this section is to
compare $\Lambda^{W}$ with $\Lambda^{{\mathrm{Model}}}$. We already know from
Theorem 4.1 that $\Lambda^{W}$ is controlled by suitable degree-$2$ box norms
of $f_{0},f_{1},f_{2}$, and we now show that the same holds for
$\Lambda^{\mathrm{Model}}.$

######  Proposition 7.1.

Let $\delta\in(0,1/10)$, let $N\in{\mathbb{N}}$, and let
$f_{0},f_{1},f_{2}:{\mathbb{Z}}^{2}\to{\mathbb{C}}$ be $1$-bounded functions
supported on $[N]^{2}$. If

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

then $\left\|f_{0}\right\|^{4}_{{\mathbf{e}}_{1}\cdot[\pm
N],\;{\mathbf{e}}_{2}\cdot[\pm
N]},\left\|f_{1}\right\|^{4}_{{\mathbf{e}}_{1}\cdot[\pm
N],\;({\mathbf{e}}_{2}-{\mathbf{e}}_{1})\cdot[\pm
N]},\left\|f_{2}\right\|^{4}_{{\mathbf{e}}_{2}\cdot[\pm
N],\;({\mathbf{e}}_{2}-{\mathbf{e}}_{1})\cdot[\pm
N]}\gg_{d}\delta^{O_{d}(1)}N^{2}$.

###### Proof.

We will replace $\nu$ by a smoother weight function that is easier to work
with. Let $\varepsilon>0$ be a small parameter to be chosen later, and let
$\varphi:{\mathbb{Z}}\to[0,1]$ be a $4\varepsilon^{-1}$-Lipschitz function
that equals $1$ on $[2\varepsilon N,(1-\varepsilon)N-1]$ and vanishes outside
of $[\varepsilon N,N-1]$. Define the cut-off weight function

$\nu_{\varepsilon}(z):=d^{-1}(N/(z+1))^{(d-1)/d}\varphi(z).$

Then $\nu_{\varepsilon}$ equals $\nu$ away from the boundary of $[N]$, and we
have the $\ell^{1}$-bound

$\sum_{z\in{\mathbb{Z}}}\mathopen{}\left|\nu_{\varepsilon}(z)-\nu(z)\mathclose{}\right|\ll\varepsilon^{1/d}N.$

Our construction of $\nu_{\varepsilon}$ ensures that it is
$O\mathopen{}\left(\varepsilon^{-3}N^{-1}\mathclose{}\right)$-Lipschitz.
Define the function $g:{\mathbb{R}}/{\mathbb{Z}}\to[0,1]$ by setting
$g(z):=\varepsilon^{1-1/d}\nu_{\varepsilon}(zN)$ for $0\leq z<1$; it follows
that $g$ is $O\mathopen{}\left(\varepsilon^{-3}\mathclose{}\right)$-Lipschitz.
By [26, Lemma 4.1], there is a trigonometric polynomial
$h:{\mathbb{R}}/{\mathbb{Z}}\to[0,1]$ of the form

$h(x)=\sum_{m\ll\varepsilon^{-10}}a(m)e(mx),$

with each $|a_{m}|\leq 1$, such that

$\left\|g-h\right\|_{\infty}\leq\varepsilon.$

Unwinding the various definitions, we see that

$\mathopen{}\left|\nu_{\varepsilon}(z)-\varepsilon^{1/d-1}\sum_{m\ll\varepsilon^{-10}}a(m)e(mz/N)\mathclose{}\right|\leq\varepsilon^{1/d}$

for all $z\in[N]$. This, combined with our earlier $\ell^{1}$-bound, implies
that $\Lambda^{{\mathrm{Model}}}(f_{0},f_{1},f_{2})$ differs by at most
$O\mathopen{}\left(\varepsilon^{1/d}N^{3}\mathclose{}\right)$ from

$\displaystyle\sum_{x,y}\sum_{z\in[N]}f_{0}(x,y)f_{1}(x+z,y)f_{2}(x,y+z)\cdot\varepsilon^{1/d-1}\sum_{m\ll\varepsilon^{-10}}a(m)e(mz/N).$

In particular, if we set $\varepsilon$ to be a sufficiently small constant
times $\delta^{d}$, then the latter quantity has absolute value at least
$\delta N^{3}/2$. Applying the triangle inequality and distributing the phases
$e(mz/N)$, we obtain

$\sum_{m\ll\delta^{-10d}}\mathopen{}\left|\sum_{x,y}\sum_{z\in[N]}f_{0}(x,y)f_{1}^{(m)}(x+z,y)f_{2}^{(m)}(x,y+z)\mathclose{}\right|\gg\delta^{2d}N^{3},$

where

$f_{1}^{(m)}(x,y):=f_{1}(x,y)e(mx/N)\quad\text{and}\quad
f_{2}^{(m)}(x,y):=f_{2}(x,y)e(-mx/N)$

are still $1$-bounded functions supported on $[N]$. Pigeonholing, we find some
$m$ such that

$\mathopen{}\left|\sum_{x,y}\sum_{z\in[N]}f_{0}(x,y)f_{1}^{(m)}(x+z,y)f_{2}^{(m)}(x,y+z)\mathclose{}\right|\gg\delta^{12d}N^{3},$

and then the desired norm-control on $f_{0}$ follows from the usual
Cauchy–Schwarz maneuvers. The norm-control on $f_{1},f_{2}$ follows
analogously. ∎

We are finally ready to show that $\Lambda^{W}$ and $\Lambda^{\mathrm{Model}}$
are always close together.

######  Proposition 7.2.

There exists $C=C(P)>0$ such that the following holds. Let
$f_{0},f_{1},f_{2}:{\mathbb{Z}}^{2}\to{\mathbb{C}}$ be $1$-bounded functions
supported on $[N]^{2}$. If $N,W$ satisfy $N\geq CW^{C}$ and
$W\geq\exp\exp(\log(1/\delta)^{C})$, then

$\displaystyle|\Lambda^{W}(f_{0},f_{1},f_{2})-\Lambda^{\mathrm{Model}}(f_{0},f_{1},f_{2})|<\delta
N^{2}.$

###### Proof.

We let all constants depend on $P$. Define the “difference” counting operator

$\displaystyle\Lambda^{*}(f_{0},f_{1},f_{2}):=\Lambda^{W}(f_{0},f_{1},f_{2})-\Lambda^{\mathrm{Model}}(f_{0},f_{1},f_{2})$

and the dual function

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

Assume for the sake of contradiction that

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

then stashing gives

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

and we conclude by the triangle inequality that either

$\displaystyle|\Lambda^{W}({\mathcal{D}}_{0}^{*}(f_{1},f_{2}),f_{1},f_{2})|\geq\delta^{2}N^{2}/2\quad\textrm{or}\quad|\Lambda^{\mathrm{Model}}({\mathcal{D}}_{0}^{*}(f_{1},f_{2}),f_{1},f_{2})|\geq\delta^{2}N^{2}/2.$

According to which of these inequalities holds, we apply either Theorem 4.1 or
Proposition 7.1 and Lemma 3.4(vi) to find a positive integer power
$V=W^{O(1)}$ for which

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

As usual, we must pass to arithmetic progressions of difference $V$ before
using the $U^{1}\times U^{2}$-inverse theorem. Write
$g_{0,j_{1},j_{2}}:=({\mathcal{D}}_{0}^{*}(f_{1},f_{2}))_{(j_{1},j_{2},V)}$,
so that

$\displaystyle\operatorname*{\mathbb{E}}_{j_{1},j_{2}\in[V]}\left\|g_{0,j_{1},j_{2}}\right\|_{{\mathbf{e}}_{1}\cdot[\pm
N/V],\;{\mathbf{e}}_{2}\cdot[\pm
N/V]}^{4}\geq\exp(-\log(1/\delta)^{O(1)})(N/V)^{2}.$

The inverse theorem for the $U^{1}\times U^{1}$-box norm (Lemma A.7) gives
$1$-bounded functions
$b_{1,j_{1},j_{2}},b_{2,j_{1},j_{2}}:\mathbb{Z}\to\mathbb{C}$, for each
$j_{1},j_{2}\in[V]$, such that

$\displaystyle\operatorname*{\mathbb{E}}_{j_{1},j_{2}\in[V]}\sum_{x,y}g_{0,j_{1},j_{2}}(x,y)b_{1,j_{1},j_{2}}(x)b_{2,j_{1},j_{2}}(y)\geq\exp(-\log(1/\delta)^{O(1)})(N/V)^{2}.$

Define the weights

$\displaystyle\tilde{\nu}(z):=\frac{N}{(N/W_{d})^{1/d}}1_{\widetilde{P}([(N/W_{d})^{1/d}])}(z)\quad\textrm{and}\quad\nu^{*}:=\tilde{\nu}-\nu,$

so that

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

and

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

Then

$\operatorname*{\mathbb{E}}_{j_{1},j_{2},r\in[V]}\sum_{x,y}\operatorname*{\mathbb{E}}_{z\in[N/V]}b_{1,j_{1},j_{2}}(x)b_{2,j_{1},j_{2}}(y)\\\
f_{1,j_{1}+r,j_{2}}(x+z,y)f_{2,j_{1},j_{2}+r}(x,y+z)\nu^{*}_{r}(z)\geq\exp(-\log(1/\delta)^{O(1)})(N/V)^{2},$

where $f_{l,j_{1},j_{2}}:=(f_{l})_{(j_{1},j_{2},V)}$ and
$\nu^{*}_{r}:=\nu^{*}_{(r,V)}$.

We will now deduce the largeness of the norm
$\left\|\nu^{*}\right\|_{U^{2}(V\cdot[\pm N/V])}$, in contradiction with the
Fourier-uniformity estimate from Proposition E.1. After shifting $x\mapsto
x-z$, we use the Cauchy–Schwarz inequality and Lemma 3.3 in order to double
$z$, obtaining

$\operatorname*{\mathbb{E}}_{j_{1},j_{2},r\in[V]}\sum_{x,y,h_{1}}\operatorname*{\mathbb{E}}_{z\in[N/V]}\mu_{N^{\prime}/V}(h_{1})\Delta_{-h_{1}}b_{1,j_{1},j_{2}}(x-z)\\\
\Delta_{h_{1}({\mathbf{e}}_{2}-{\mathbf{e}}_{1})}f_{2,j_{1}+r,j_{2}}(x-z,y+z)\Delta_{h_{1}}\nu^{*}_{r}(z)\geq\exp(-\log(1/\delta)^{O(1)})(N/V)^{2}$

for any positive integer $N^{\prime}\leq\exp(-\log(1/\delta)^{O(1)})N$.
Shifting $(x,y)\mapsto(x+z,y-z)$ and repeating this maneuver gives

$\displaystyle\operatorname*{\mathbb{E}}_{r\in[V]}\left\|\nu^{*}_{r}\right\|_{U^{2}([\pm
N^{\prime}/V])}^{4}=\operatorname*{\mathbb{E}}_{r\in[V]}\sum_{z,h_{1},h_{2}}\mu_{N^{\prime}/V}(h_{1},h_{2})\Delta_{h_{1},h_{2}}\nu^{*}_{r}(z)\geq\exp(-\log(1/\delta)^{O(1)})N/V.$

Choosing $N^{\prime}\asymp\exp(-\log(1/\delta)^{C})N$ for a sufficiently large
constant $C>0$, we can use Lemma 3.4(iv) to replace $N^{\prime}$ with $N$ and
obtain the norm-control

$\displaystyle\left\|\nu^{*}\right\|_{U^{2}(V\cdot[\pm
N/V])}^{4}=\sum_{r\in[V]}\left\|\nu^{*}_{r}\right\|_{U^{2}([\pm
N/V])}^{4}\geq\exp(-\log(1/\delta)^{O(1)})N.$

But Proposition E.1 and Lemma A.4 tell us that

$\displaystyle\left\|\nu^{*}\right\|_{U^{2}(V\cdot[\pm N/V])}^{4}\ll N/w^{c}$

for some constant $c>0$ depending only on $P$. Hence
$w\leq\exp(\log(1/\delta)^{O(1)})$ and so
$W\leq\exp\exp(\log(1/\delta)^{O(1)})$, which contradicts the assumption on
$W$ as long as the $O(1)$ term is sufficiently large. ∎

We are finally ready to conclude the proof of Theorem 1.1.

###### Proof of Theorem 1.1.

It suffices to prove the result with $N$ replaced by $WN$. Let
$A\subseteq[WN]^{2}$ be a set with density $\gamma$. By the pigeonhole
principle, there exist $j_{1},j_{2}\in[\beta_{1}^{2}W]$ such that the set

$B:=\\{(x,y)\in[N]^{2}:\beta_{1}^{2}W(x,y)+(j_{1},j_{2})\in A\\}$

has size at least $\gamma N^{2}$. Since $\nu(z)\geq d^{-1}$ pointwise for
$z\in[N]$, the supersaturation result (Proposition F.2) tells us that

$\Lambda^{\mathrm{Model}}(1_{B},1_{B},1_{B})\geq
d^{-1}\exp(-\exp(\gamma^{-c^{\prime}}))N^{2}$

for some absolute $c^{\prime}>0$. Setting
$\delta:=\exp(-\exp(\gamma^{-c^{\prime}}))/(2d)$, we obtain from Proposition
7.2 that

$\Lambda^{W}(1_{B},1_{B},1_{B})\gg_{P}\exp(-\exp(\gamma^{-c^{\prime}}))N^{2}$

for any $W\geq\exp\exp(\log(1/\delta)^{\Omega_{P}(1)})$ satisfying

$\displaystyle
N\gg_{P}W^{\Omega_{P}(1)}\geq\exp\exp(\log(1/\delta)^{\Omega_{P}(1)})\geq\exp\exp\exp(\Omega_{P}(\gamma^{-c^{\prime}})).$

In particular, the set $B$ contains nontrivial configurations
$(x,y),\;(x+\widetilde{P}(z),y),\;(x,y+\widetilde{P}(z))$, and hence the set
$A$ contains nontrivial configurations of $(x,y),\;(x+P(z),y),\;(x,y+P(z))$.
This completes the proof. ∎

We will now deduce Corollary 1.3.

###### Proof of Corollary 1.3.

It suffices to prove the result with $N$ replaced by $WN$. Let
$A\subseteq[WN]$ be a set of density $\gamma$. By the pigeonhole principle,
there exists $j\in[\beta_{1}^{2}W]$ such that the set

$B:=\\{x\in[N]:\beta_{1}^{2}Wx+j\in A\\}$

has size at least $\gamma N$. Since $\nu(z)\geq d^{-1}$ pointwise for
$z\in[N]$, a standard Varnavides-style supersaturation version of the result
of Kelley and Meka [15] tells us that

$\sum_{x}\mathbb{E}_{z\in[N]}1_{B}(x)1_{B}(x+z)1_{B}(x+2z)\geq
d^{-1}\exp(-\log(1/\gamma)^{C^{\prime}})N$

for some absolute constant $C^{\prime}>0$.

Consider the set

$B^{\prime}:=\\{(x,y)\in[2N]^{2}:y-x\in B\\},$

and note that

$N\sum_{x}1_{B}(x)1_{B}(x+z)1_{B}(x+2z)\asymp\sum_{x,y}1_{B^{\prime}}(x,y)1_{B^{\prime}}(x+z,y)1_{B^{\prime}}(x,y+z)$

for each $z\in[N]$. Using this correspondence and applying Proposition 7.2
with $\delta:=\exp(-\log(1/\gamma)^{C^{\prime}})/(10d)$, we conclude that

$\sum_{x}\mathbb{E}_{z\in[(N/W_{d})^{1/d}]}1_{B}(x)1_{B}(x+\widetilde{P}(z))1_{B}(x+2\widetilde{P}(z))\gg_{P}\exp(-\log(1/\gamma)^{O_{P}(1)})N$

as long as $W\geq\exp\exp(\log(1/\delta)^{\Omega_{P}(1)})$ satisfies

$\displaystyle
N\gg_{P}W^{\Omega_{P}(1)}\geq\exp\exp(\log(1/\delta)^{\Omega_{P}(1)})\geq\exp\exp(\log(1/\gamma)^{\Omega_{P}(1)}).$

In particular, the set $B$ contains nontrivial configurations
$x,\;x+\widetilde{P}(z),\;x+2\widetilde{P}(z)$, and hence the set $A$ contains
nontrivial configurations $x,\;x+P(z),\;x+2P(z)$. This completes the proof. ∎

##  Appendix A Inverse theorems for box norms

We require inverse theorems for several box norms and directional Gowers norms
that arise in our arguments. Although these results are more or less standard,
we include statements and proofs here for ease of reference.

###  A.1. $U^{1}$-inverse theorems

Heuristically, a function has large degree-$1$ Gowers norm in the direction v
if it correlates with a function that is periodic in the v-direction. Since we
are working with norms in which the differencing parameters $h$ are
constrained to lie in intervals, making this heuristic precise is somewhat
delicate. In particular, we need the “length” of the differencing parameter to
be sufficiently large relative to the size of the support of the function in
question, where “sufficiently large” depends on the quality of the lower bound
on the Gowers norm. This issue does not appear for higher-degree box norms
since Lemma 3.4(iv) allows us to manipulate the lengths of boxes at will.

We start with the $U^{1}$-inverse theorem for functions on ${\mathbb{Z}}$.

######  Lemma A.1 ($1$-dimensional $U^{1}$-inverse theorem).

Let $\delta\in(0,1]$ and $N,N^{\prime}\in{\mathbb{N}}$ with
$N^{\prime}\geq\delta^{-1/2}N\geq\delta^{-1}$. If
$f:{\mathbb{Z}}\to\mathbb{C}$ is a $1$-bounded function supported on $[N]$,
then

$\displaystyle\left\|f\right\|_{[\pm N^{\prime}]}^{2}\geq\delta
N\quad\Longrightarrow\quad\mathopen{}\left|\sum_{x}f(x)\mathclose{}\right|\gg\delta^{1/4}N.$

###### Proof.

By definition, we have

$\displaystyle\left\|f\right\|_{[\pm
N^{\prime}]}^{2}=\sum_{x,x^{\prime}\in[N]}\mu_{N^{\prime}}(x^{\prime}-x)f(x)\overline{f(x^{\prime})}.$

The idea is that since $N^{\prime}$ is sufficiently large relative to $N$, we
have $\mu_{N^{\prime}}(x-x^{\prime})\approx 1/(2N^{\prime}-1)$ for all
$x,x^{\prime}\in[N]$. More precisely, since $f$ is $1$-bounded and
$N^{\prime}\geq\delta^{-1/2}N\geq N$, we can make the crude comparison

$\displaystyle\mathopen{}\left|(2N^{\prime}-1)\left\|f\right\|_{[N^{\prime}]}^{2}-\sum_{x,x^{\prime}}f(x)\overline{f(x^{\prime})}\mathclose{}\right|$
$\displaystyle\leq\sum_{x,x^{\prime}\in[N]}\mathopen{}\left|(2N^{\prime}-1)\mu_{N^{\prime}}(x^{\prime}-x)-1\mathclose{}\right|$
$\displaystyle=\frac{1}{2N^{\prime}-1}\sum_{x,x^{\prime}\in[N]}|x-x^{\prime}|$
$\displaystyle\leq\frac{N^{2}(N-1)}{2N^{\prime}-1}\leq\delta^{1/2}N^{2}/2.$

Hence

$\displaystyle\mathopen{}\left|\sum_{x}f(x)\mathclose{}\right|^{2}=\sum_{x,x^{\prime}}f(x)\overline{f(x^{\prime})}$
$\displaystyle\geq(2N^{\prime}-1)\delta N-\delta^{1/2}N^{2}/2$
$\displaystyle\geq(3/2)\delta^{1/2}N-\delta N\gg\delta^{1/2}N^{2}$

since $N\geq\delta^{-1/2}$. ∎

######  Lemma A.2 ($2$-dimensional $U^{1}$-inverse theorem).

Let $\delta\in(0,1]$ and $N,N^{\prime}\in{\mathbb{N}}$ with
$N^{\prime}\geq(\delta/2)^{-1/2}N\geq 2\delta^{-1}$, and let
$f:{\mathbb{Z}}^{2}\to\mathbb{C}$ be a $1$-bounded function supported on
$[N]^{2}$. Then

$\left\|f\right\|^{2}_{{\mathbf{e}}_{1}\cdot[\pm N^{\prime}]}\geq\delta
N^{2}\;\Longrightarrow\;\text{$\sum_{x,y}f(x,y)b(y)\gg\delta^{5/4}N^{2}$ for
some $1$-bounded $b:{\mathbb{Z}}\to{\mathbb{C}}$};$
$\left\|f\right\|_{{\mathbf{e}}_{2}\cdot[\pm N^{\prime}]}^{2}\geq\delta
N^{2}\;\Longrightarrow\;\text{$\sum_{x,y}f(x,y)b(x)\gg\delta^{5/4}N^{2}$ for
some $1$-bounded $b:{\mathbb{Z}}\to{\mathbb{C}}$};$

and

$\left\|f\right\|^{2}_{({\mathbf{e}}_{2}-{\mathbf{e}}_{1})\cdot[\pm
N^{\prime}]}\geq\delta
N^{2}\;\Longrightarrow\;\text{$\sum_{x,y}f(x,y)b(x+y)\gg\delta^{5/4}N^{2}$ for
some $1$-bounded $b:{\mathbb{Z}}\to{\mathbb{C}}$}.$

###### Proof.

We begin with the first statement; the second follows by symmetry. For each
$y\in{\mathbb{Z}}$, define the function $f_{y}:{\mathbb{Z}}\to{\mathbb{Z}}$
via $f_{y}(x):=f(x,y)$. Then we have the identity

$\left\|f\right\|_{{\mathbf{e}}_{1}\cdot[\pm
N^{\prime}]}^{2}=\sum_{y\in[N]}\left\|f_{y}\right\|_{[\pm N^{\prime}]}^{2}.$

The popularity principle supplies at least $\delta N/2$ values of $y\in[N]$
for which $\left\|f_{y}\right\|_{[\pm N^{\prime}]}^{2}\geq\delta N/2$.
Applying Lemma A.1 for each such $y$ and using nonnegativity for the remaining
$y$’s, we find that

$\sum_{y\in[N]}\mathopen{}\left|\sum_{x\in{\mathbb{Z}}}f(x,y)\mathclose{}\right|\gg\delta
N\cdot\delta^{1/4}N.$

Adding $1$-bounded fudge factors $b(y)$ to remove the absolute values, we
obtain

$\sum_{x,y}f(x,y)b(y)\gg\delta^{5/4}N^{2},$

as desired.

The proof of the third statement goes similarly. This time, we foliate
$[N]^{2}$ using $1$-dimensional arithmetic progressions with common difference
${\mathbf{e}}_{2}-{\mathbf{e}}_{1}$; each such arithmetic progression
intersects $[N]^{2}$ in at most $N$ elements. Applying the popularity
principle and Lemma A.1, and then removing the absolute values as in the first
statement, we arrive at the desired conclusion. ∎

###  A.2. Unnormalized box norms

To prove inverse theorems for higher-degree box norms, it is often easier to
start with unnormalized box norms. Given
${\textbf{v}}_{1},\ldots,{\textbf{v}}_{s}\in{\mathbb{Z}}^{D}$, we define the
_unnormalized box norm_ of a compactly supported function
$f:{\mathbb{Z}}^{D}\to{\mathbb{C}}$ along
${\textbf{v}}_{1},\ldots,{\textbf{v}}_{s}$ to be

$\displaystyle\left\|f\right\|_{{\textbf{v}}_{1},\ldots,{\textbf{v}}_{s}}$
$\displaystyle:=\mathopen{}\left(\sum_{{\textbf{x}},h_{1},\ldots,h_{s}}\Delta_{{\textbf{v}}_{1}h_{1},\ldots,{\textbf{v}}_{s}h_{s}}f({\textbf{x}})\mathclose{}\right)^{1/2^{s}}.$

If $D=1$ and ${\textbf{v}}_{1}=\cdots={\textbf{v}}_{s}=1$, we also set
$\left\|f\right\|_{U^{s}}:=\left\|f\right\|_{{\textbf{v}}_{1},\ldots,{\textbf{v}}_{s}}$.
The following lemma relates unnormalized and normalized box norms.

######  Lemma A.3 (Relating normalized and unnormalized box norms).

Let $s\geq 2$, let $D,H_{1},\ldots,H_{s}\in{\mathbb{N}}$, and let
${\textbf{v}}_{1},\ldots,{\textbf{v}}_{s}\in{\mathbb{Z}}^{D}$. For any
compactly supported function $f:{\mathbb{Z}}^{D}\to{\mathbb{C}}$, we have

$\displaystyle\left\|f\right\|_{{\textbf{v}}_{1}\cdot[\pm
H_{1}],\ldots,{\textbf{v}}_{s}\cdot[\pm
H_{s}]}^{2^{s}}\leq\prod_{i=1}^{s}\frac{1}{2H_{i}-1}\cdot\left\|f\right\|_{{\textbf{v}}_{1},\ldots,{\textbf{v}}_{s}}^{2^{s}}.$

###### Proof.

Using the inductive formula for box norms, the pointwise bound $\mu_{H}(h)\leq
1/(2H-1)$, and nonnegativity, we have

$\displaystyle\left\|f\right\|_{{\textbf{v}}_{1}\cdot[\pm
H_{1}],\ldots,{\textbf{v}}_{s}\cdot[\pm H_{s}]}^{2^{s}}$
$\displaystyle=\sum_{h_{2},\ldots,h_{s}}\mu_{H_{2}}(h_{2})\cdots\mu_{H_{s}}(h_{s})\left\|\Delta_{{\textbf{v}}_{2}h_{2},\ldots,{\textbf{v}}_{s}h_{s}}f\right\|_{{\textbf{v}}_{1}\cdot[\pm
H_{1}]}^{2}$
$\displaystyle\leq\prod_{i=2}^{s}\frac{1}{2H_{i}-1}\cdot\sum_{h_{2},\ldots,h_{s}}\left\|\Delta_{{\textbf{v}}_{2}h_{2},\ldots,{\textbf{v}}_{s}h_{s}}f\right\|_{{\textbf{v}}_{1}\cdot[\pm
H_{1}]}^{2}$
$\displaystyle=\prod_{i=2}^{s}\frac{1}{2H_{i}-1}\cdot\sum_{h_{1}}\mu_{H_{1}}(h_{1})\left\|\Delta_{{\textbf{v}}_{1}h_{1}}f\right\|_{{\textbf{v}}_{2},\ldots,{\textbf{v}}_{s}}^{2^{s-1}}$
$\displaystyle\leq\prod_{i=1}^{s}\frac{1}{2H_{i}-1}\cdot\left\|f\right\|_{{\textbf{v}}_{1},\ldots,{\textbf{v}}_{s}}^{2^{s}};$

note that the applications of nonnegativity crucially used the assumption
$s\geq 2$. ∎

###  A.3. $U^{2}$-inverse theorems

The starting point for $U^{2}$-inverse theorems is the following well-known
$1$-dimensional result (see, e.g., [30, Lemma 2.4]).

######  Lemma A.4 ($1$-dimensional $U^{2}$-inverse theorem).

Let $\delta\in(0,1]$ and $H,N\in{\mathbb{N}}$ with $\delta N\leq H\leq N$. If
$f:{\mathbb{Z}}\to\mathbb{C}$ is a $1$-bounded function supported on $[N]$,
then

$\displaystyle\left\|f\right\|_{[\pm H],[\pm H]}^{4}\geq\delta
N\quad\Longrightarrow\quad\text{$\sum_{x}f(x)e(ax+b)\gg\delta^{3/2}N$ for some
$a,\;b\in{\mathbb{R}}/{\mathbb{Z}}$}.$

###### Proof.

By Lemma A.3 and the assumption $H\geq\delta N$, we have
$\left\|f\right\|_{U^{2}}^{4}\gg\delta^{3}N^{3}$. Fourier inversion and
Plancherel’s Identity give

$\left\|f\right\|_{U^{2}}^{4}=\left\|\hat{f}\right\|_{4}^{4}\leq\left\|\hat{f}\right\|_{2}^{2}\cdot\left\|\hat{f}\right\|_{\infty}^{2}=\left\|f\right\|_{2}^{2}\cdot\left\|\hat{f}\right\|_{\infty}^{2}\leq
N\cdot\left\|\hat{f}\right\|_{\infty}^{2}.$

Hence $\left\|\hat{f}\right\|_{\infty}\gg\delta^{3/2}N$, which is equivalent
to the conclusion of the lemma. ∎

######  Lemma A.5 ($2$-dimensional $U^{2}$-inverse theorem).

Let $\delta\in(0,1]$ and $H,N\in{\mathbb{N}}$ with $\delta^{-O(1)}\ll\delta
N\leq H\leq N$, and let $f:{\mathbb{Z}}^{2}\to\mathbb{C}$ be a $1$-bounded
function supported on $[N]^{2}$. Then

$\displaystyle\left\|f\right\|_{({\mathbf{e}}_{1}\cdot[\pm
H])^{2}}^{4}\geq\delta N^{2}\quad\Longrightarrow\quad$
$\displaystyle\sum_{x,y}f(x,y)e(a(y)x+b(y))\gg\delta^{3/2}N^{2}$
$\displaystyle\text{for some $1$-bounded
$a,\;b:{\mathbb{Z}}\to{\mathbb{R}}/{\mathbb{Z}}$};$
$\displaystyle\left\|f\right\|^{4}_{({\mathbf{e}}_{2}\cdot[\pm
H])^{2}}\geq\delta N^{2}\quad\Longrightarrow\quad$
$\displaystyle\sum_{x,y}f(x,y)e(a(x)y+b(x))\gg\delta^{3/2}N^{2}$
$\displaystyle\text{for some $1$-bounded
$a,\;b:{\mathbb{Z}}\to{\mathbb{R}}/{\mathbb{Z}}$}.$

This lemma follows from Lemma A.4 just as Lemma A.2 follows from Lemma A.1.

###  A.4. $U^{1}\times U^{1}$-inverse theorems

Let ${\textbf{v}}_{1},{\textbf{v}}_{2}\in{\mathbb{Z}}^{2}$ be vectors such
that
$\langle{\textbf{v}}_{1},{\textbf{v}}_{2}\rangle_{{\mathbb{Z}}}={\mathbb{Z}}^{2}$.
Then the unnormalized box norm along ${\textbf{v}}_{1},{\textbf{v}}_{2}$ can
be written as

$\displaystyle\left\|f\right\|_{{\textbf{v}}_{1},{\textbf{v}}_{2}}$
$\displaystyle=\mathopen{}\left(\sum_{m,m^{\prime},n,n^{\prime}}f({\textbf{v}}_{1}m+{\textbf{v}}_{2}n)\overline{f({\textbf{v}}_{1}m^{\prime}+{\textbf{v}}_{2}n)f({\textbf{v}}_{1}m+{\textbf{v}}_{2}n^{\prime})}f({\textbf{v}}_{1}m^{\prime}+{\textbf{v}}_{2}n^{\prime})\mathclose{}\right)^{1/4}$

and satisfies the following inverse theorem.

######  Lemma A.6 (Inverse theorem for the unnormalized $U^{1}\times
U^{1}$-norm).

Let ${\textbf{v}}_{1},{\textbf{v}}_{2}\in{\mathbb{Z}}^{2}$ be vectors of
length $O(1)$ satisfying
$\langle{\textbf{v}}_{1},{\textbf{v}}_{2}\rangle_{{\mathbb{Z}}}={\mathbb{Z}}^{2}$,
and let $N\in{\mathbb{N}}$. If $f:{\mathbb{Z}}^{2}\to{\mathbb{C}}$ is a
$1$-bounded function supported on $[N]^{2}$, then there are $1$-bounded
functions $b_{1},b_{2}:{\mathbb{Z}}\to{\mathbb{C}}$ such that

$\displaystyle\left\|f\right\|_{{\textbf{v}}_{1},{\textbf{v}}_{2}}^{4}\ll
N^{2}\cdot\sum_{m,n}f({\textbf{v}}_{1}m+{\textbf{v}}_{2}n)b_{1}(m)b_{2}(n).$

###### Proof.

The pigeonhole principle gives some $n^{\prime}\in{\mathbb{Z}}$, necessarily
of size $O(N)$, such that

$\displaystyle\left\|f\right\|_{{\textbf{v}}_{1},{\textbf{v}}_{2}}^{4}\ll
N\mathopen{}\left|\sum_{m,m^{\prime},n}f({\textbf{v}}_{1}m+{\textbf{v}}_{2}n)\overline{f({\textbf{v}}_{1}m^{\prime}+{\textbf{v}}_{2}n)f({\textbf{v}}_{1}m+{\textbf{v}}_{2}n^{\prime})}f({\textbf{v}}_{1}m^{\prime}+{\textbf{v}}_{2}n^{\prime})\mathclose{}\right|.$

Let
$S:=\\{m^{\prime}\in{\mathbb{Z}}:\;{\textbf{v}}_{1}m^{\prime}+{\textbf{v}}_{2}n^{\prime}\in[N]^{2}\\}$.
Then $|S|\ll N$, and the result follows upon setting
$b_{1}(m):=\overline{f({\textbf{v}}_{1}m+{\textbf{v}}_{2}n^{\prime})}$ and
letting $b_{2}(n)$ be equal to $\operatorname*{\mathbb{E}}_{m^{\prime}\in
S}\overline{f({\textbf{v}}_{1}m^{\prime}+{\textbf{v}}_{2}n)}f({\textbf{v}}_{1}m^{\prime}+{\textbf{v}}_{2}n^{\prime})$
times a suitable complex number of norm $1$ that makes the expression in the
absolute value positive. ∎

Combining this lemma with Lemma A.3 immediately gives the following result for
unnormalized box norms.

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

Let $\delta\in(0,1]$ and $H,N\in{\mathbb{N}}$ with $\delta N\leq H\leq N$. Let
$f:{\mathbb{Z}}^{2}\to\mathbb{C}$ be a $1$-bounded function supported on
$[N]^{2}$. Then

$\displaystyle\left\|f\right\|_{{\mathbf{e}}_{1}\cdot[\pm
H],\;{\mathbf{e}}_{2}\cdot[\pm H]}^{4}\geq\delta
N^{2}\quad\Longrightarrow\quad$
$\displaystyle\sum_{x,y}f(x,y)b_{1}(x)b_{2}(y)\gg\delta^{3}N^{2}$
$\displaystyle\text{for some $1$-bounded
$b_{1},b_{2}:{\mathbb{Z}}\to{\mathbb{C}}$};$
$\displaystyle\left\|f\right\|_{{\mathbf{e}}_{1}\cdot[\pm
H],\;({\mathbf{e}}_{2}-{\mathbf{e}}_{1})\cdot[\pm H]}^{4}\geq\delta
N^{2}\quad\Longrightarrow\quad$
$\displaystyle\sum_{x,y}f(x,y)b_{1}(x+y)b_{2}(y)\gg\delta^{3}N^{2}$
$\displaystyle\text{for some $1$-bounded
$b_{1},b_{2}:{\mathbb{Z}}\to{\mathbb{C}}$};$
$\displaystyle\left\|f\right\|_{{\mathbf{e}}_{2}\cdot[\pm
H],\;({\mathbf{e}}_{2}-{\mathbf{e}}_{1})\cdot[\pm H]}^{4}\geq\delta
N^{2}\quad\Longrightarrow\quad$
$\displaystyle\sum_{x,y}f(x,y)b_{1}(x)b_{2}(x+y)\gg\delta^{3}N^{2}$
$\displaystyle\text{for some $1$-bounded
$b_{1},b_{2}:{\mathbb{Z}}\to{\mathbb{C}}$}.$

###  A.5. $U^{2}\times U^{1}$-inverse theorem

Recall that our degree-lowering result Theorem 4.1 is based on replacing
“$U^{2}\times U^{1}$-obstructions” with “$U^{1}\times U^{1}$-obstructions”. We
are finally ready to give a precise characterization of the former
obstructions.

######  Lemma A.8.

Let $\delta\in(0,1]$ and $H,N\in{\mathbb{N}}$ with $\delta^{O(1)}\ll\delta
N\leq H\leq N$, and let $f:{\mathbb{Z}}^{2}\to\mathbb{C}$ be a $1$-bounded
function supported on $[N]^{2}$. Then

$\displaystyle\|f\|_{{\mathbf{e}}_{1}\cdot[\pm H],\;{\mathbf{e}}_{1}\cdot[\pm
H],\;{\mathbf{e}}_{2}\cdot[\pm H]}^{8}\geq\delta
N^{2}\Longrightarrow\sum_{x,y}f(x,y)g(x)e(a(y)x+b(y))\gg\delta^{O(1)}N^{2}$
$\displaystyle\text{for some $1$-bounded $g:{\mathbb{Z}}\to{\mathbb{C}}$ and
phase functions $a,b:{\mathbb{Z}}\to{\mathbb{R}}/{\mathbb{Z}}$};$
$\displaystyle\|f\|_{{\mathbf{e}}_{1}\cdot[\pm H],\;{\mathbf{e}}_{2}\cdot[\pm
H],\;{\mathbf{e}}_{2}\cdot[\pm H]}^{8}\geq\delta
N^{2}\Longrightarrow\sum_{x,y}f(x,y)g(y)e(a(x)y+b(x))\gg\delta^{O(1)}N^{2}$
$\displaystyle\text{for some $1$-bounded $g:{\mathbb{Z}}\to{\mathbb{C}}$ and
phase functions $a,b:{\mathbb{Z}}\to{\mathbb{R}}/{\mathbb{Z}}$}.$

###### Proof.

We only prove the first statement as the other can be proved by swapping the
roles of $x$ and $y$. The inductive formula for box norms gives

$\delta^{8}N^{2}\leq\|f\|_{{\mathbf{e}}_{1}\cdot[\pm
H],\;{\mathbf{e}}_{1}\cdot[\pm H],\;{\mathbf{e}}_{2}\cdot[\pm
H]}^{8}=\sum_{h}\mu_{H}(h)\|\Delta_{h{\mathbf{e}}_{2}}f\|_{{\mathbf{e}}_{1}\cdot[\pm
H],\;{\mathbf{e}}_{1}\cdot[\pm H]}^{4}.$

By Lemma A.5, there are phases
$\alpha(y,y+h),\;\beta(y,y+h)\in\mathbb{R}/\mathbb{Z}$ such that

$\sum_{x,y,h}\mu_{H}(h)\Delta_{h{\mathbf{e}}_{2}}f(x,y)e(\alpha(y,y+h)x+\beta(y,y+h))\gg\delta^{O(1)}N^{2}$

and the summand is real and nonnegative for each fixed $h,y$. In particular,
we have

$\sum_{x,y,h}\Delta_{h{\mathbf{e}}_{2}}f(x,y)e(\alpha(y,y+h)x+\beta(y,y+h))\gg\delta^{O(1)}N^{3}.$

Replacing the variable $h$ with the variable $z:=y+h$, we get

$\sum_{x,y,z}f(x,y)\overline{f(x,z)}e(\alpha(y,z)x+\beta(y,z))\gg\delta^{O(1)}N^{3}.$

The pigeonhole principle gives an integer $|z_{0}|\ll N$ such that

$\sum_{x,y}f(x,y)\overline{f(x,z_{0})}e(\alpha(y,z_{0})x+\beta(y,z_{0}))\gg\delta^{O(1)}N^{2}.$

The lemma now follows upon setting

$g(x):=\overline{f(x,z_{0})},\quad a(y):=\alpha(y,z_{0}),\quad\text{and}\quad
b(y):=\beta(y,z_{0}).$

∎

##  Appendix B Nilsequence definitions

This section contains (mostly standard) definitions pertaining to
nilsequences.

######  Definition B.1 ($(t-1)$-fold commutator).

For elements $g_{1},\dots,g_{t}$ of a group $G$, we define

$[g_{1},g_{2},\dots,g_{t}]:=[[[g_{1},g_{2}],g_{3}],\dots,g_{t}].$

We will call any such commutator a _$(t-1)$ -fold commutator_ of the elements
$g_{1},\dots,g_{t}$.

We now introduce the lower central series.

######  Definition B.2.

The _lower central series_ of a nilpotent Lie group $G$ is the sequence of
nested subgroups $G=G_{(0)}=G_{(1)}\supseteq G_{(2)}\supseteq G_{(3)}\cdots$
where $G_{(i)}:=[G,G_{(i-1)}]$ for $i\geq 1$. The step of $G$ is the smallest
integer $s$ such that $G_{(s+1)}=\mathrm{Id}_{G}$.

Recall that the _height_ of the rational number $a/b$ (for $a,b$ coprime
integers) is $\max(|a|,|b|)$. We will now define a nilmanifold.

######  Definition B.3 (Nilmanifold).

A _nilmanifold_ of degree $k$, step $s$, complexity at most $M$, and dimension
$m$ consists of the following data:

  1. (i)

an $s$-step connected and simply connected nilpotent real Lie group $G$ and a
discrete cocompact subgroup $\Gamma$ of $G$;

  2. (ii)

a _filtration_ $G_{\bullet}=(G_{i})_{i=0}^{\infty}$ of nested subgroups
$G=G_{0}=G_{1}\supseteq G_{2}\supseteq\cdots$ such that
$G_{i}=\\{\mathrm{Id}_{G}\\}$ for all $i>k$ and $[G_{i},G_{j}]\subseteq
G_{i+j}$ for all $i,j$; and

  3. (iii)

a _Mal’cev basis_ , i.e., a basis $\\{X_{1},\dots,X_{m}\\}$ of the Lie algebra
$\mathfrak{g}:=\log(G)$.

We furthermore require the data to satisfy the following conditions:

  1. (i)

For $1\leq i,j\leq m$, we have

$[X_{i},X_{j}]=\sum_{l>\max(i,j)}a_{ijl}X_{l}$

for some rational numbers $a_{ijl}$ of height at most $M$.

  2. (ii)

For $m_{i}:=\text{dim}(G_{i})$, we have
$\log(G_{i})=\text{span}\\{X_{j}:m-m_{i}<j\leq m\\}$.

  3. (iii)

Each element $g\in G$ can be expressed uniquely as
$\exp(t_{1}X_{1})\exp(t_{2}X_{2})\cdots\exp(t_{m}X_{m})$ with
$t_{1},\dots,t_{m}\in\mathbb{R}$; we let $\psi:g\mapsto(t_{1},\ldots,t_{m})$
denote the associated _coordinate map_ from $G$ to $\mathbb{R}^{m}$.

  4. (iv)

$\Gamma$ consists of precisely the elements $g$ for which
$\psi(g)\in\mathbb{Z}^{m}$.

A Mal’cev basis that satisfies the last three of these conditions is said to
be adapted to the filtration $G_{\bullet}$.

Note that condition (ii) implies that each $G_{i}$ is closed, connected, and
simply connected.

The lower central series (as defined above) gives the so-called standard
filtration on a nilpotent Lie group $G$, and we emphasize that there are
filtrations other than the standard filtration. The standard filtration on $G$
is “minimal” in the sense that any other filtration $(G_{i})$ satisfies
$G_{i}\supseteq G_{(i)}$ for each $i\in{\mathbb{N}}$ [43, Exercise 1.6.2].

A nilmanifold can be endowed with a metric as follows.

######  Definition B.4 (Metric on a nilmanifold).

Given a nilmanifold $G/\Gamma$ with coordinate map $\psi$, we define a metric
$d_{G}$ on $G$ to be the right-invariant metric

$d_{G}(x,y):=\inf\left\\{\sum_{i=1}^{n}\min\\{|\psi(x_{i}x_{i-1}^{-1})|,|\psi(x_{i-1}x_{i}^{-1})|\\}:x_{0}=x,x_{n}=y\right\\}.$

Setting
$d(x\Gamma,y\Gamma):=\inf\\{d(x^{\prime},y^{\prime}):x^{\prime}\Gamma=x\Gamma,y^{\prime}\Gamma=y\Gamma\\}$,
we obtain a metric on $G/\Gamma$.

This metric makes $G/\Gamma$ into a compact metric space and hence can be used
to define the Lipschitz parameter of a function on $G/\Gamma$.

######  Definition B.5 (Lipschitz norm).

Let $(X,d_{X})$ be a metric space. The _Lipschitz constant_ of a function
$F\colon X\to\mathbb{C}$ is the quantity

$\sup_{x\neq y\in X}\frac{|F(x)-F(y)|}{d_{X}(x,y)},$

and the _Lipschitz norm_ of $F$ is

$\|F\|_{\mathrm{Lip}(X)}:=\|F\|_{L^{\infty}(X)}+\sup_{x\neq y\in
X}\frac{|F(x)-F(y)|}{d_{X}(x,y)}.$

If $\|F\|_{\mathrm{Lip}(X)}\leq M$, then we say that $F$ is an _$M$ -Lipschitz
function_.

An important property of Lipschitz functions on a nilmanifold is that they can
be approximated by finite linear combinations of vertical characters (as
defined below).

We now turn to polynomial sequences.

######  Definition B.6 (Polynomial sequences).

Let $G$ be an $s$-step connected and simply connected nilpotent real Lie group
with a degree-$k$ filtration $(G_{i})_{i=0}^{\infty}$. The set
$\mathrm{poly}(\mathbb{Z},G)$ of _polynomial sequences_ to $G$ consists of the
maps $g\colon\mathbb{Z}\to G$ of the form

$g({n})=\prod_{{i}=0}^{k}g_{{i}}^{\binom{{n}}{{i}}}$

for some $g_{i}\in G_{i}$. It is known (see, e.g., [14, Chapter 14]) that
$\mathrm{poly}(\mathbb{Z},G)$ forms a group under pointwise multiplication.

Our next definition is a smoothness norm on real polynomials that captures the
extent to which their coefficients are close to integers.

######  Definition B.7 (Smoothness norm).

Let $p(x)=\sum_{j=0}^{D}\alpha_{j}x^{j}\in\mathbb{R}[x]$ be a polynomial of
degree $D$. Its _smoothness norm_ at scale $T>0$ is defined to be

$\left\|p\right\|_{C^{\infty}[T]}:=\max_{1\leq j\leq
D}T^{j}\left\|\alpha_{j}\right\|_{\mathbb{R}/\mathbb{Z}}.$

Note that this definition of smoothness is written using the monomial basis,
which differs slightly from [21, Definition 2.2]. By [21, Lemma A.10], these
notions are equivalent up to a multiplicative factor of $O_{D}(1)$.

Two important special classes of polynomial sequences on $G$ are those whose
coefficients are “rational” and those which grow slowly and remain “close” to
the identity.

######  Definition B.8 (Rational and smooth sequences).

Given $Q\in{\mathbb{N}}$, we say an element $g$ of $G$ is _rational with
height $Q$_ (or _$Q$ -rational_) if $g^{Q}\in\Gamma$. We say that a polynomial
sequence $\gamma$ on $G$ is _$Q$ -rational_ if $\gamma({n})$ is $Q$-rational
for each ${n}\in\mathbb{Z}$.

We say that a polynomial sequence $\varepsilon$ on $G$ is _$(K,{T})$ -smooth_
if for each $n\in{\mathbb{Z}}$, we have

$d_{G}(\varepsilon(n+1),\varepsilon(n))\leq K/T\quad\text{ and }\quad
d_{G}(\varepsilon(0),\mathrm{id}_{G})\leq K.$

We are finally ready to define a nilsequence.

######  Definition B.9 (Nilsequence).

A _nilsequence_ of complexity $M$ is a sequence
$\varphi:{\mathbb{Z}}\to{\mathbb{C}}$ of the form $\varphi(n)=F(g(n)\Gamma)$,
where $g$ is a polynomial sequence on $G$ and $F\colon G/\Gamma\to\mathbb{C}$
is an $M$-Lipschitz function on a nilmanifold $G/\Gamma$ of complexity $M$.

We now shift gears and discuss horizontal and vertical characters on
$G/\Gamma$.

######  Definition B.10 (Horizontal and vertical components).

The _horizontal component_ of $G$ is $G/G_{(2)}=G/[G,G]$, and the _vertical
component_ of $G$ is $G_{(s)}$.888In [11], the vertical component is defined
to be $G_{\ell}$ where $G_{\ell}$ is the smallest nontrivial element of the
filtration of $G$. We let $\pi_{\mathrm{horiz}}\colon G\to G/G_{(2)}$ denote
the quotient map. We use $d_{\mathrm{horiz}}$ and $d_{(s)}$ to denote the
dimensions of $G/G_{(2)}$ and $G_{(s)}$, respectively.

We remark that $G/[G,G]\Gamma$, often called the _horizontal torus_ , is
isomorphic to the torus $({\mathbb{R}}/{\mathbb{Z}})^{d_{\mathrm{horiz}}}$;
the Mal’cev basis adapted to $G/\Gamma$ provides an isomorphism. Horizontal
characters come from characters of the horizontal torus, as follows.

######  Definition B.11 (Horizontal character).

A _horizontal character_ on $G/\Gamma$ is a continuous homomorphism
$\eta\colon G\to\mathbb{R}$ such that $\eta(\Gamma)\subseteq\mathbb{Z}$.

Note that since $\mathbb{R}$ is abelian, every horizontal character $\eta$
annihilates $[G,G]$ and hence descends to a character on the horizontal torus.
Since the characters of $({\mathbb{R}}/{\mathbb{Z}})^{d_{\mathrm{horiz}}}$
correspond to elements of ${\mathbb{Z}}^{d_{\mathrm{horiz}}}$, our choice of
Mal’cev basis provides a correspondence between horizontal characters of
$G/\Gamma$ and elements of ${\mathbb{Z}}^{d_{\mathrm{horiz}}}$. More
explicitly, each $\eta$ is of the form $\eta(g)=k\cdot\psi(g)$ for some
$k\in{\mathbb{Z}}^{d_{\mathrm{horiz}}}$.

We will also require the notion of a vertical character.

######  Definition B.12 (Vertical character).

Let $H$ be a connected, simply connected subgroup of the center $Z(G)$ which
is _rational_ in the sense that $H\cap\Gamma$ is cocompact in $H$, and let
$\eta:H\to{\mathbb{R}}$ be a continuous homomorphism such that
$\eta(H\cap\Gamma)\subseteq{\mathbb{Z}}$. We say that a function
$F:G/\Gamma\to{\mathbb{C}}$ is an _$H$ -vertical character_ with _frequency_
$\eta$ if

$F(gx)=e(\eta(g))F(x)$

for all $g\in H$ and $x\in G/\Gamma$. We refer to a $G_{(s)}$-vertical
character as simply a _vertical character_.

Horizontal and vertical characters come with natural notions of size.

######  Definition B.13 (Size of a character).

If $\eta$ is a horizontal character on $G/\Gamma$ associated with the element
$k\in({\mathbb{R}}/{\mathbb{Z}})^{d_{\mathrm{horiz}}}$, then the _size_ (or
_modulus_) of $\eta$, denoted $|k|$ or $\|k\|_{\infty}$, is the $L^{\infty}$
norm of the vector $k$.

Let $H$ be a rational subgroup of the center $Z(G)$, and let $\xi\colon
H/(H\cap\Gamma)\to\mathbb{R}/\mathbb{Z}$ be a homomorphism. The _size_ (or
_modulus_) of $\xi$, denoted $|\xi|$, is the Lipschitz constant of the
function $x\mapsto e(\xi(x))$ on $H/(H\cap\Gamma)$. Equivalently,

$|\xi|:=\sup_{x\neq y\in
H/(H\cap\Gamma)}\frac{|e(\xi(x))-e(\xi(y))|}{d_{G/\Gamma}(x,y)}.$

Finally, we will need quantitative measures of rationality for subspaces and
subgroups.

######  Definition B.14 (Rational subspace).

Let $V$ be a vector space with a basis $\mathcal{B}$, and let $W$ be a
subspace of $V$. We say that $W$ is _at most $Q$-rational_ if $W$ has a basis
$\mathcal{B}^{\prime}$ such that each $w_{j}\in\mathcal{B}^{\prime}$ can be
written as

$w_{j}=\sum_{v_{i}\in\mathcal{B}}a_{ji}v_{i}$

for some rationals $a_{ji}$ of height at most $Q$.

######  Definition B.15 (Rational subgroup and subnilmanifold).

Let $G/\Gamma$ be a nilmanifold with Mal’cev basis $\mathcal{X}$. A connected
and simply connected subgroup $H\subseteq G$ is $Q$-rational if
$\mathfrak{h}:=\log(H)$ is $Q$-rational with respect to $\mathfrak{g}$ with
the basis $\mathcal{X}$. Define $\Gamma^{\prime}:=H\cap\Gamma$. We then say
that the nilmanifold $H/\Gamma^{\prime}$, equipped with the filtration
$H_{\bullet}=(H_{i})_{i=0}^{\infty}$ given by $H_{i}:=G_{i}\cap H$, is a
$Q$-rational subnilmanifold of $G/\Gamma$.

######  Remark.

If $H$ is a $Q$-rational subgroup of $G$, then by [22, Lemma B.12] there
exists a $Q^{O_{k}(m^{O(1)})}$-rational Mal’cev basis for $H/(\Gamma\cap H)$.

##  Appendix C Fraction-comparison estimates

In this section, we prove elementary “fraction-comparison estimates” in the
style of [34] (see, e.g., the proof of Proposition 5.6 there). These estimates
are useful in the nilsequences part of our argument. While the first two
lemmas are straightforward, the third makes use of some important properties
of $V$-tricked polynomials. Recall the smoothness norms from Definition B.7.

######  Lemma C.1.

Let $D,Q,T\in{\mathbb{N}}$, let $R\in{\mathbb{R}}[z]$ be a polynomial of
degree $D$, and let $a,b\in{\mathbb{Z}}$ with $|a|\leq QT$ and $0<|b|\leq Q$
nonzero. Then the polynomial $\tilde{R}(z):=R(a+bz)$ satisfies

$\|b^{D}R\|_{C^{\infty}[T]}\ll_{D}Q^{D-1}\|\tilde{R}\|_{C^{\infty}[T]}.$

###### Proof.

Assume that $\|\tilde{R}\|_{C^{\infty}[T]}\leq M$; we will show that
$\|b^{D}R\|_{C^{\infty}[T]}\ll_{D}Q^{D-1}M$. Write
$R(z)=\sum_{i=0}^{D}\alpha_{i}z^{i}$. Then

$\displaystyle\tilde{R}(z)=R(a+bz)=\sum_{i=0}^{D}\alpha_{i}(a+bz)^{i}=\sum_{i=0}^{D}\alpha_{i}\sum_{j=0}^{i}{i\choose
j}b^{j}z^{j}a^{i-j}=\sum_{j=0}^{D}b^{j}z^{j}\sum_{i=j}^{D}\alpha_{i}{i\choose
j}a^{i-j}.$

The assumption $\|\tilde{R}\|_{C^{\infty}[T]}\leq M$ means that

(34) $\displaystyle\left\|b^{j}\cdot\sum_{i=j}^{D}\alpha_{i}{i\choose
j}a^{i-j}\right\|_{\mathbb{R}/\mathbb{Z}}\leq M/T^{j}$

for each $1\leq j\leq D$. In particular the $j=D$ instance of (34) gives

$\left\|b^{D}\alpha_{D}\right\|_{{\mathbb{R}}/{\mathbb{Z}}}\leq M/T^{D}.$

Next, the $j=D-1$ instance of (34) gives

$\left\|b^{D-1}(\alpha_{D-1}+Da\alpha_{D})\right\|_{{\mathbb{R}}//Z}\leq
M/T^{D-1};$

multiplying the expression in
$\left\|\cdot\right\|_{{\mathbb{R}}/{\mathbb{Z}}}$ by $b$ and using the
triangle inequality (and the assumption on the sizes of $a,b$), we find that

$\left\|b^{D}\alpha_{D-1}\right\|_{{\mathbb{R}}/{\mathbb{Z}}}\leq
QM/T^{D-1}+D(QT)(M/T^{D})\ll_{D}QM/T^{D-1}.$

Continuing inductively in this manner, we find that

$\left\|b^{D}\alpha_{j}\right\|_{{\mathbb{R}}/{\mathbb{Z}}}\ll_{D}Q^{D-j}M/T^{j}\leq
Q^{D-1}M/T^{j}$

for each $1\leq j\leq D$, as desired. ∎

For ease of reference we record the following special case of this lemma.

######  Lemma C.2.

Let $D,T\in{\mathbb{N}}$, and let $R\in{\mathbb{R}}[z]$ be a polynomial of
degree $D$. If $|y_{0}|\leq QT$ and

$\|R(y_{0}+\cdot)\|_{C^{\infty}[T]}\leq Q,$

then

$\|R\|_{C^{\infty}[T]}\ll_{D}Q^{D}.$

Recall that we are interested in the $V$-tricked polynomial

$\widetilde{P}_{[r,V]}(z):=\frac{\widetilde{P}(Vz+r)-\widetilde{P}(r)}{V},$

where $V=W^{O_{P}(1)}$ is a nonnegative integer power of $W$ and $r\in[V]$; as
mentioned previously, $\widetilde{P}_{[r,V]}$ has integer coefficients, zero
constant term and degree $d\geq 2$. Let us denote the coefficient of $z^{i}$
in $\widetilde{P}_{[r,V]}(z)$ by
$V_{i}\in\mathbb{Z}[W,V,r,\;\beta_{1},\ldots,\;\beta_{d}]$. We record that

$V_{d}=\beta_{d}\beta_{1}^{d-2}W^{d-1}V^{d-1}$

and that $V_{1}$ is equal to $1$ plus $W$ times some integer-coefficient
polynomial in $W,V,r,\;\beta_{1},\ldots,\;\beta_{d}$. Thus, if every prime
factor of $\beta_{1}\beta_{d}$ also divides $W$ (which is the case for $w$
larger than an absolute constant depending only on $P$), then $V_{1}$ is
equivalent to $1$ modulo every prime dividing $V_{d}$ and we have

$\gcd(V_{d},V_{1})=1.$

The following lemma tells us that precomposing a polynomial with
$\widetilde{P}_{[r,V]}$ cannot significantly decrease its (properly
normalized) smoothness norm.

######  Lemma C.3.

Let $D\in{\mathbb{N}}$. For every $C_{1}>0$ there exists a constant
$C_{2}=C_{2}(C_{1},D,P)>0$ such that the following holds. Let $V\leq
W^{C_{1}}$ be a nonnegative integer power of $W$, let $r\in[V]$, and let
$T,Q\in{\mathbb{N}}$. Let $R\in\mathbb{R}[z]$ be a polynomial of degree $D$.
Assume that every prime factor of $\beta_{1}\beta_{d}$ also divides $W$. If

$\|R\circ\widetilde{P}_{[r,V]}\|_{C^{\infty}[(T/V_{d})^{1/d}]}\leq Q$

and $T>C_{2}W^{C_{2}}$, then

$\|R\|_{C^{\infty}[T]}\leq C_{2}Q.$

The scales of these smoothness norms come from the estimate
$\widetilde{P}_{[r,V]}((T/V_{d})^{1/d})\asymp T$.

###### Proof.

We fix $C_{1}>0$ and let all the constants depend on $P$ and $D$. The proof
proceeds by induction on the degree $D$, where the base case $D=0$ holds
vacuously. For the induction step, write $R(z)=\sum_{i=0}^{D}\alpha_{i}z^{i}$.
Recall that $\widetilde{P}_{[r,V]}(z)=V_{d}z^{d}+\cdots+V_{1}z$. We compute

$\displaystyle R(\widetilde{P}_{[r,V]}(z))$
$\displaystyle=\sum_{i=0}^{D}\alpha_{i}(V_{d}z^{d}+\cdots+V_{1}z)^{i}$
$\displaystyle=\sum_{i=0}^{D}\alpha_{i}\sum_{j_{1}+\cdots+j_{d}=i}\binom{i}{j_{1},\ldots,j_{d}}(V_{1}z)^{j_{1}}\cdots(V_{d}z^{d})^{j_{d}}$
$\displaystyle=\sum_{k=0}^{dD}z^{k}\sum_{i=0}^{D}\alpha_{i}\sum_{{\underline{j}}\in\mathcal{P}(i,k)}\binom{i}{j_{1},\ldots,j_{d}}V_{1}^{j_{1}}\cdots
V_{d}^{j_{d}},$

where $\mathcal{P}(i,k)$ denotes the set of tuples
$\underline{j}=(j_{1},\ldots,j_{d})$ of nonnegative integers satisfying
$j_{1}+\cdots+j_{d}=i$ and $j_{1}+2j_{2}+\cdots+dj_{d}=k$. The assumption
$\|R\circ\widetilde{P}_{[r,V]}\|_{C^{\infty}[(T/V_{d})^{1/d}]}\leq Q$ tells us
that

(35)
$\left\|\sum_{i=0}^{D}\alpha_{i}\sum_{{\underline{j}}\in\mathcal{P}(i,k)}\binom{i}{j_{1},\ldots,j_{d}}V_{1}^{j_{1}}\cdots
V_{d}^{j_{d}}\right\|_{\mathbb{R}/\mathbb{Z}}\leq Q(V_{d}/T)^{k/d}$

for each $1\leq k\leq dD$. Let $E_{k}$ denote the expression inside
$\|\cdot\|_{\mathbb{R}/\mathbb{Z}}$ in (35).

We will show that $\|\alpha_{D}\|_{\mathbb{R}/\mathbb{Z}}\leq Q/T^{D}$. Since
$E_{dD}=\alpha_{D}V_{d}^{D}$, Equation (35) for $k=dD$ tells us that

$\left\|\alpha_{D}V_{d}^{D}\right\|_{\mathbb{R}/\mathbb{Z}}\leq
Q(V_{d}/T)^{D},$

and hence there is some integer $n$ such that

(36) $|\alpha_{D}-n/V_{d}^{D}|\leq Q/T^{D}.$

We will aim to show that $n$ is divisible by $V_{d}^{D}$. To accomplish this,
we will find a second rational approximation for $\alpha_{D}$ using a
denominator that is coprime to $V_{d}^{D}$. To begin, we have
$E_{1}=\alpha_{1}V_{1}$. Next, $E_{2}=\alpha_{2}V_{1}^{2}+\alpha_{1}V_{2}$,
and so

$V_{1}E_{2}-V_{2}E_{1}=V_{1}^{3}\alpha_{2}.$

We continue with
$E_{3}=\alpha_{3}V_{1}^{3}+\alpha_{2}(2V_{1}V_{2})+\alpha_{1}V_{3}$ and

$V_{1}^{2}E_{3}-2V_{2}(V_{1}E_{2}-V_{2}E_{1})-V_{1}V_{3}E_{1}=V_{1}^{5}\alpha_{3}.$

Continuing inductively in this manner, we obtain a positive integer $\gamma$
and polynomials $s_{1},\ldots,s_{d}\in\mathbb{Z}[V_{1},\ldots,V_{d}]$ such
that

$s_{1}E_{1}+\cdots+s_{d}E_{d}=V_{1}^{\gamma}\alpha_{D}$

holds (as an identity in the formal variables
$V_{1},\ldots,V_{d},\alpha_{1},\ldots,\alpha_{D}$); note that the $s_{i}$’s
depend only on the parameters $d,D$. The crucial point for the induction is
that $E_{k}$ (for $1\leq k\leq D$) equals $\alpha_{k}V_{1}^{k}$ plus a linear
combination of $\alpha_{k-1},\ldots,\alpha_{1}$ with coefficients in
$\mathbb{Z}[V_{1},\ldots,V_{d}]$.

Recalling that $V_{i}=O(W^{d-1}V^{d-1})=O(W^{O(1)})$ and applying (35) for
$1\leq k\leq D$, we find that

$\left\|V_{1}^{\gamma}\alpha_{D}\right\|_{\mathbb{R}/\mathbb{Z}}=O(QW^{O(1)}/T^{1/d}).$

Thus there is an integer $n^{\prime}$ such that

$\mathopen{}\left|\alpha_{D}-n^{\prime}/V_{1}^{\gamma}\mathclose{}\right|=O(QW^{O(1)}/T^{1/d}).$

Comparing this with (36) gives

$\mathopen{}\left|n/V_{d}^{D}-n^{\prime}/V_{1}^{\gamma}\mathclose{}\right|=O(QW^{O(1)}/T^{1/d}).$

Now we must have

$n/V_{d}^{D}=n^{\prime}/V_{1}^{\gamma}$

since otherwise we would have
$\mathopen{}\left|n/V_{d}^{D}-n^{\prime}/V_{1}^{\gamma}\mathclose{}\right|\geq
1/(V_{d}^{D}V_{1}^{\gamma})$, which (due to the constraint on $T$) is not of
size $O(QW^{O(1)}/T^{1/d})$. Since $V_{1},V_{d}$ are coprime, we conclude that
$n$ is divisible by $V_{d}^{D}$, and (36) tells us that

$\left\|\alpha_{D}\right\|_{\mathbb{R}/\mathbb{Z}}\leq Q/T^{D},$

as desired.

We claim that

$\left\|\alpha_{D}(\widetilde{P}_{[r,V]})^{D}\right\|_{C^{\infty}[(T/V_{d})^{1/d}]}=O(Q).$

Indeed, since each $V_{i}\ll(WV)^{d-1}\ll V_{d}$, we see that the
$z^{i}$-coefficient of $(\widetilde{P}_{[r,V]})^{D}$ has size $\ll V_{d}^{D}$.
Then for each $0\leq i\leq dD$, the distance from the $z^{i}$-coefficient of
$\alpha_{D}(\widetilde{P}_{[r,V]})^{D}$ to the nearest integer is at most

$\ll(Q/T^{D})\cdot V_{d}^{D}\leq(V_{d}/T)^{i/d}Q;$

this establishes the claim. Hence

$\left\|(R\circ\widetilde{P}_{[r,V]})-\alpha_{D}(\widetilde{P}_{[r,V]})^{D}\right\|_{C^{\infty}[(T/V_{d})^{1/d}]}=O(Q),$

and the lemma follows from the induction hypothesis. ∎

##  Appendix D Sárközy-type results

The goal of this section is to make precise the heuristic that

(37)
$\displaystyle\sum_{\textbf{x}}\operatorname*{\mathbb{E}}_{z\in[(N/V_{d})^{1/d}]}f_{0}({\textbf{x}})f_{1}({\textbf{x}}+{\textbf{v}}\widetilde{P}_{[r,V]}(z))\approx\sum_{{\textbf{x}}}\operatorname*{\mathbb{E}}_{z\in[N]}f_{0}({\textbf{x}})f_{1}({\textbf{x}}+{\textbf{v}}z),$

where $V=W^{O_{P}(1)}$ is a nonnegative integer power of $W$, $r\in[V]$ (in
particular, if $V=1$, then $r=0$ and hence
$\widetilde{P}_{[r,V]}=\widetilde{P}$), and $V_{i}$’s are the coefficients of
$\widetilde{P}_{[r,V]}$. We use circle-method arguments to make this heuristic
precise. These arguments originated in work of Sárközy [37, 38], and we will
more closely follow a method due to Green [12].

Throughout this section, define $K:=(N/V_{d})^{1/d}$, so that
$|\widetilde{P}_{[r,V]}(z)|\ll_{P}N$ for $z\in[K]$. For
$\xi\in{\mathbb{R}}/{\mathbb{Z}}$, we also let

$\displaystyle S(\xi):=\sum_{z\in[K]}e(\xi\widetilde{P}_{[r,V]}(z))$

denote the Fourier transform of the (multi)set $\widetilde{P}_{[r,V]}([K])$.

###  D.1. Circle method preliminaries

The first step towards (37) is showing that the counting operator for a
$2$-point polynomial progression is always controlled by the major arcs of its
arguments. Let us make a few more definitions. Let $\varepsilon>0$ be a
constant to be determined later. For coprime $0\leq a<q\leq K^{\varepsilon}$,
we define the _major arc_

$\displaystyle\mathfrak{M}_{a,q}:=\left\\{\xi\in{\mathbb{R}}/{\mathbb{Z}}:\;\mathopen{}\left|\xi-\frac{a}{q}\mathclose{}\right|\leq
K^{-(d-\varepsilon)}\right\\}.$

As long as $\varepsilon<1/3$, the intervals $\mathfrak{M}_{a,q}$ are disjoint.
So we partition ${\mathbb{R}}/{\mathbb{Z}}$ into the _major arcs_
$\mathfrak{M}$ and the _minor arcs_ $\mathfrak{m}$, where

$\displaystyle\mathfrak{M}:=\bigcup_{\begin{subarray}{c}1\leq a\leq q\leq
K^{\varepsilon},\\\
\gcd(a,q)=1\end{subarray}}\mathfrak{M}_{a,q}\quad\textrm{and}\quad\mathfrak{m}:=({\mathbb{R}}/{\mathbb{Z}})\setminus\mathfrak{M}.$

A key input for controlling the minor arcs is the following classical lemma
that upper-bounds the even moments of $F$ (see, e.g., [47, Corollary 14.2]).

######  Lemma D.1 (Crude bound on even moments of $F$).

There exists some positive integer $s_{0}(d)>d$ such that for all $s\geq
s_{0}(d)$ and $\eta>0$, we have

$\displaystyle\int_{{\mathbb{R}}/{\mathbb{Z}}}\mathopen{}\left|S(\xi)\mathclose{}\right|^{2s}\;d\xi\ll_{\eta}K^{2s-d+\eta}.$

The following lemma is a generalization of [34, Lemma B.4], and it follows
from a nearly identical proof, which we omit.

######  Lemma D.2 (Minor arc control).

Let $s_{0}(d)$ be as in Lemma D.1, and let $s>s_{0}(d)$ be a positive integer.
There exists an absolute $C=C(d)\geq 1$ such that for all
$\varepsilon\in(0,1)$ and positive integers $K\gg_{d,\varepsilon}1$, if the
coefficients of $\widetilde{P}_{[r,V]}$ have size at most $K^{\varepsilon/4}$,
then we have the pointwise bound

$\displaystyle\sup_{\xi\in\mathfrak{m}}|S(\xi)|\leq K^{1-\varepsilon/C}$

as well as the $L^{2s}$-bound

$\displaystyle\int_{\mathfrak{m}}\mathopen{}\left|S(\xi)\mathclose{}\right|^{2s}\ll_{s,\varepsilon}K^{2s-d-\varepsilon/C}.$

In order to handle the major arcs, we start with the following classical
decomposition result for $F$ (see e.g. [46, Corollary 5.2]).

######  Lemma D.3.

Let $0<\varepsilon<1/3$ and $0\leq a<q\leq K^{\varepsilon}$ with $a,q$
coprime. If $\xi\in\mathfrak{M}_{a,q}$, then

$\displaystyle
S(\xi)=\operatorname*{\mathbb{E}}_{u\in[q]}e(a\widetilde{P}_{[r,V]}(u)/q)\int_{0}^{K}e\mathopen{}\left(\mathopen{}\left(\xi-\frac{a}{q}\mathclose{}\right)\widetilde{P}_{[r,V]}(z)\mathclose{}\right)dz+O(K^{2\varepsilon}).$

We recall that the assumption $\varepsilon<1/3$ ensures the disjointness of
the major arcs.

In what follows, let

$S(a,q):=\operatorname*{\mathbb{E}}_{u\in[q]}e(a\widetilde{P}_{[r,V]}(u)/q)=\operatorname*{\mathbb{E}}_{u\in{\mathbb{Z}}/q{\mathbb{Z}}}e(a\widetilde{P}_{[r,V]}(u)/q)$

be the exponential sum appearing in Lemma D.3. The following lemma gives
bounds on $S(a,q)$ for various values of $a,q$. It is inspired by [4, Lemma
5.3]; the proof is almost identical, so we omit it.

######  Lemma D.4.

Let $1\leq a<q$ be coprime positive integers. Then

$\displaystyle|S(a,q)|\ll_{\eta,P}q^{\eta-1/d}\quad\textrm{for\;
every}\quad\eta>0.$

Moreover, $S(a,q)=0$ whenever $\gcd(q,W)>1$.

Next, we upper-bound the integral appearing in Lemma D.3. It essentially
follows from the van der Corput Lemma (e.g., [41, pp. 332]) and we omit the
proof.

######  Lemma D.5.

We have

$\displaystyle\mathopen{}\left|\int_{0}^{K}e(\xi\widetilde{P}_{[r,V]}(z))\;dz\mathclose{}\right|\ll_{P}1+|\xi|^{-1/d}V_{d}^{-1/d}.$

Combining the previous three lemmas, we can finally upper-bound the
contribution of the major arcs.

######  Lemma D.6 (Major arc control).

For $s>d$ and $\varepsilon\in(0,1/10]$, we have

$\displaystyle\int_{\mathfrak{M}}\mathopen{}\left|S(\xi)\mathclose{}\right|^{2s}\;d\xi\ll_{P,s}\frac{K^{2s-d}}{V_{d}}$

as long as $K\geq V_{d}^{2}$.

We recall that the parameter $\varepsilon$ figures implicitly in the
definition of the major arcs $\mathfrak{M}$; since the left-hand side of the
inequality in the lemma is non-decreasing as $\varepsilon$ increases, the
important point is that we can take $\varepsilon$ bounded away from $0$.

###### Proof.

We let all constants depend on $P,s$. Applying Lemma D.3, integrating over all
of the major arcs, and changing variables $\xi\mapsto\xi+a/q$ on each
$\mathfrak{M}_{a,q}$, we have

$\int_{\mathfrak{M}}\mathopen{}\left|S(\xi)\mathclose{}\right|^{2s}\;d\xi=\Bigl{(}1_{(a,q)=(0,1)}+\sum_{\begin{subarray}{c}1\leq
a<q\leq K^{\varepsilon},\\\
\gcd(a,q)=1\end{subarray}}|S(a,q)|^{2s}\Bigr{)}\cdot\int_{-K^{-d+\varepsilon}}^{K^{-d+\varepsilon}}\mathopen{}\left|\int_{0}^{K}e\mathopen{}\left({\xi}\widetilde{P}_{[r,V]}(z)\mathclose{}\right)\,dz\mathclose{}\right|^{2s}\,d\xi\\\
+O\Bigl{(}1_{(a,q)=(0,1)}+\sum_{\begin{subarray}{c}1\leq a<q\leq
K^{\varepsilon},\\\
\gcd(a,q)=1\end{subarray}}1\Bigr{)}(K^{2s-1-d+3\varepsilon}).$

We bound the terms in the expression above one by one, starting with the
contribution of the sums $S(a,q)$. For every $\eta>0$, we can bound

$\displaystyle 1_{(a,q)=(0,1)}+\sum_{\begin{subarray}{c}1\leq a<q\leq
K^{\varepsilon},\\\
\gcd(a,q)=1\end{subarray}}|S(a,q)|^{2s}\ll_{\eta}1+\sum_{\begin{subarray}{c}1\leq
a<q\leq K^{\varepsilon},\\\
\gcd(a,q)=1\end{subarray}}q^{\eta-2s/d}\ll_{\eta}1+K^{\varepsilon(\eta+2-2s/d)},$

where the first inequality follows from an application of Lemma D.4 with
$2\eta s$ in place of $\eta$, and the second bound follows from trivially
estimating the number of $a$’s in $1\leq a<q$ by $q$ and then trivially
bounding $q\leq K^{\varepsilon}$. Importantly, this expression is $O(1)$ as
long as $s>d$ and $\eta<2/d$. Since there are no further restrictions on the
choice of $\eta$, we can take any $\eta$ in the range above.

To bound the contribution of the integral, we split it over $\xi$ at
$K^{-d}/V_{d}$, obtaining

$\int_{-K^{-d+\varepsilon}}^{K^{-d+\varepsilon}}\mathopen{}\left|\int_{0}^{K}e\mathopen{}\left(\xi\widetilde{P}_{[r,V]}(z)\mathclose{}\right)dz\mathclose{}\right|^{2s}d\xi\\\
\leq\int_{-K^{-d}/V_{d}}^{K^{-d}/V_{d}}K^{2s}\,d\xi+2\int_{K^{-d}/V_{d}}^{1}\mathopen{}\left|\int_{0}^{K}e\mathopen{}\left(\xi\widetilde{P}_{[r,V]}(z)\mathclose{}\right)dz\mathclose{}\right|^{2s}\,d\xi.$

The first term can be bounded trivially by $K^{2s-d}/V_{d}$. To bound the
second term, we apply Lemma D.5, which gives

$\displaystyle\int_{K^{-d}/V_{d}}^{1}\mathopen{}\left|\int_{0}^{K}e\mathopen{}\left(\xi\widetilde{P}_{[r,V]}(z)\mathclose{}\right)dz\mathclose{}\right|^{2s}\,d\xi$
$\displaystyle\ll\int_{K^{-d}/V_{d}}^{1}|\xi|^{-2s/d}V_{d}^{-2s/d}d\xi\ll\frac{K^{2s-d}}{V_{d}},$

where we use Lemma D.5 to bound the integrand and the assumption $s>d$ to
ensure that the exponent is of the right order.

Lastly, the error term is at most

$\displaystyle\ll\Bigl{(}1_{(a,q)=(0,1)}+\sum_{\begin{subarray}{c}1\leq
a<q\leq K^{\varepsilon},\\\
\gcd(a,q)=1\end{subarray}}1\Bigr{)}K^{2s-1-d+3\varepsilon}\ll
K^{2s-1-d+5\varepsilon},$

which can be bounded by $\ll K^{2s-d}/V_{d}$ since $K\geq V_{d}^{2}$ and
$\varepsilon\leq 1/10$. ∎

We summarize the computations performed in this section in the result below.

######  Proposition D.7 (Even moment bound).

There exists $s_{1}(d)\in{\mathbb{N}}$ and $C=C(d)>0$ such that if $s\geq
s_{1}(d)$ and $N\geq V_{d}^{C}$, then

$\displaystyle\int_{{\mathbb{R}}/{\mathbb{Z}}}|S(\xi)|^{2s}\;d\xi\ll_{P,s}\frac{K^{2s}}{N}.$

###### Proof.

Let $s_{1}(d)=\max(s_{0}(d),d+1)$, where $s_{0}$ comes from Lemma D.2 and
$d+1$ is the smallest possible $s$ allowed by Lemma D.6. We fix $s>s_{1}(d)$
and let all the implicit constants depend on $P,s$. We split
${\mathbb{R}}/{\mathbb{Z}}$ into major and minor arcs with $\varepsilon=1/10$.
Then we can use Lemma D.2 to bound the minor arc contribution as

$\displaystyle\int_{\mathfrak{m}}|S(\xi)|^{2s}\;d\xi\ll
K^{2s-d-\varepsilon/C_{1}}$

where $C_{1}>0$ is the constant from Lemma D.2. Since $N=K^{d}V_{d}$, this can
be bounded by $\ll\frac{K^{2s}}{N}$ as long as $V_{d}\leq
K^{\varepsilon/C_{1}}$, which we can assume by taking the implicit constant in
$N\geq V_{d}^{\Omega(1)}$ to be sufficiently large. We also implicitly use the
assumption $N\geq V_{d}^{\Omega(1)}$ to ensure that $K^{\varepsilon/4}\geq
V_{d}$ so that the assumption on the coefficients of $\widetilde{P}_{[r,V]}$
in Lemma D.2 is satisfied. To bound the major arc contribution by the same
final expression, we simply apply Lemma D.6.

∎

###  D.2. Applications to Sárközy-type estimates

We are now ready to show that counting operators for Sárközy-type
configurations are controlled by the major arcs of their arguments.

######  Proposition D.8.

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

(38)
$\displaystyle\mathopen{}\left|\sum_{x}\operatorname*{\mathbb{E}}_{z\in[K]}f_{0}(x)f_{1}(x+\widetilde{P}_{[r,V]}(z))\mathclose{}\right|\geq\delta
N,$

then for every $i=0,1$ there exist phases
$\xi_{i}\in{\mathbb{R}}/{\mathbb{Z}}$ and positive integers
$q_{i}\ll_{C_{1},P}\delta^{-O_{C_{1},P}(1)}$ such that
$\left\|q_{i}\xi_{i}\right\|_{{\mathbb{R}}/{\mathbb{Z}}}\ll_{C_{1},P}\delta^{-O_{C_{1},P}(1)}/N$
and $|\widehat{f_{i}}(\xi_{i})|\gg_{C_{1},P}\delta^{O_{C_{1},P}(1)}N$.

###### Proof.

We fix $C_{1}>0$ and let all constants depend on $P$. We prove the bound only
for $i=0$, since one can then deduce the result for $i=1$ by shifting
$x\mapsto x-\widetilde{P}_{[r,V]}(z)$ and exchanging the roles of
$f_{0},f_{1}$. Our first goal is to show that the largeness of (38) implies
the largeness of some Fourier coefficient of $f_{0}$, and then we use the
fraction comparison argument to deduce that this Fourier coefficient must be a
major arc.

Define the mutliset $E:=\\{\widetilde{P}_{[r,V]}(z):\;z\in[K]\\}$, so that our
assumption can be expressed as

$\displaystyle\mathopen{}\left|\sum_{x,z}f_{0}(x)f_{1}(x+z)1_{E}(z)\mathclose{}\right|\geq\delta
NK.$

Note that $F=\widehat{1_{E}}$. Now, Fourier-expanding, extracting the largest
Fourier coefficient, and applying the triple Hölder inequality (with exponents
$\frac{2s}{s-1},2,2s$) followed by Parseval’s Identity, we get

$\displaystyle\delta NK$
$\displaystyle\leq\left\|\widehat{f_{0}}\right\|_{\infty}^{1/s}\cdot\int_{{\mathbb{R}}/{\mathbb{Z}}}|\widehat{f_{0}}(\xi)|^{1-1/s}\cdot|\widehat{f_{1}}(\xi)|\cdot|F(\xi)|\;d\xi$
$\displaystyle\leq\left\|\widehat{f_{0}}\right\|_{\infty}^{1/s}\cdot\left\|f_{0}\right\|^{1-1/s}_{2}\cdot\left\|f_{1}\right\|_{2}\cdot\mathopen{}\left(\int_{{\mathbb{R}}/{\mathbb{Z}}}|F(\xi)|^{2s}\;d\xi\mathclose{}\right)^{1/(2s)}$

for any $s\geq 2$. We can trivially bound
$\left\|f_{0}\right\|^{1-1/s}_{2}\cdot\left\|f_{1}\right\|_{2}\leq
N^{(2s-1)/(2s)}$, and Proposition D.7 gives

$\displaystyle\int_{{\mathbb{R}}/{\mathbb{Z}}}|S(\xi)|^{2s}\;d\xi\ll\frac{K^{2s}}{N}$

for any $s$ sufficiently large in terms of $d$. Combining all these bounds
together, we get the bound
$\left\|\widehat{f_{i}}\right\|_{\infty}\gg\delta^{O(1)}N$, i.e. we have shown
that the Sárközy configuration is controlled by Fourier analysis.

Now, let
$\tilde{f}_{0}=\operatorname*{\mathbb{E}}_{z\in{K}}\overline{f_{1}}(x+\widetilde{P}_{[r,V]}(z))$.
Stashing, we can replace $f_{0}$ by $\tilde{f}_{0}$ in (38) at the cost of
squaring $\delta$ in the lower bound. Together with the just proved Fourier
control, this gives us

$\displaystyle\mathopen{}\left|\sum_{x}\operatorname*{\mathbb{E}}_{z\in[K]}\overline{f_{1}}(x+\widetilde{P}_{[r,V]}(z))e(-\xi
x)\mathclose{}\right|\gg\delta^{O(1)}N$

for some $\xi\in{\mathbb{R}}/{\mathbb{Z}}$. Shifting $x\mapsto
x-\widetilde{P}_{[r,V]}(z)$, splitting the sums over $x$ and $z$, and using
$\left\|f_{1}\right\|_{1}\leq N$, we get that

$\displaystyle\mathopen{}\left|\sum_{x}f_{1}(x)e(\xi
x)\mathclose{}\right|\gg\delta^{O(1)}N\quad\textrm{and}\quad\mathopen{}\left|\operatorname*{\mathbb{E}}_{z\in[K]}e(-\xi\widetilde{P}_{[r,V]}(z))\mathclose{}\right|\gg\delta^{O(1)}.$

It remains to show that $\xi$ is a major arc. By Weyl’s inequality (e.g. [11,
Lemma 4.4]), the second inequality can only hold if there exists a positive
integer $q\ll\delta^{-O(1)}$ for which
$\left\|q\xi\widetilde{P}_{[r,V]}\right\|_{C^{\infty}[K]}\ll\delta^{-O(1)}$.
The result then follows from Lemma C.3. ∎

The following two corollaries make precise the heuristic (37).

######  Corollary D.9.

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

$\displaystyle\mathopen{}\left|\sum_{x}\operatorname*{\mathbb{E}}_{z\in[K]}f_{0}(x)f_{1}(x+\widetilde{P}_{[r,V]}(z))\mathclose{}\right|\geq\delta
N,$

then for each $i\in\\{0,1\\}$ there exists a positive integer
$q_{i}\ll_{C_{1},P}\delta^{-O_{C_{1},P}(1)}$ such that

$\displaystyle\operatorname*{\mathbb{E}}_{u\in[\pm
N]}\mathopen{}\left|\operatorname*{\mathbb{E}}_{z\in[N^{\prime}]}f_{i}(u+q_{i}z)\mathclose{}\right|\gg_{C_{1},P}\delta^{O_{C_{1},P}(1)}\quad\textrm{for\;
all}\quad 1\leq N^{\prime}\ll_{C_{1},P}\delta^{O_{C_{1},P}(1)}N.$

###### Proof.

We fix $C_{1}>0$ and let all constants depend on $P$. We just proof the claim
for $i=1$, as the other case follows by symmetry. By Proposition D.8, there
exist a phase $\xi\in{\mathbb{R}}/{\mathbb{Z}}$ and a positive integer
$q\ll\delta^{-O(1)}$ such that
$\left\|q\xi\right\|_{{\mathbb{R}}/{\mathbb{Z}}}\ll\delta^{-O(1)}/N$ and

$\displaystyle\mathopen{}\left|\sum_{x}f_{1}(x)e(\xi
x)\mathclose{}\right|\gg\delta^{O(1)}N.$

Set $N^{\prime}_{0}\asymp\delta^{C}N$ for some $C>1$ to be chosen later, and
let $N^{\prime}\in[N^{\prime}_{0}]$ be arbitrary. Introducing an extra
averaging over arithmetic progressions of length $N^{\prime}$ and common
difference $q$ gives

$\displaystyle\mathopen{}\left|\sum_{u}\operatorname*{\mathbb{E}}_{z\in[N^{\prime}]}f_{1}(u+qz)e(\xi(u+qz))\mathclose{}\right|\gg\delta^{O(1)}N.$

The triangle inequality gives

$\sum_{u}\mathopen{}\left|\operatorname*{\mathbb{E}}_{z\in[N^{\prime}]}f_{1}(u+qz)e(\xi
qz)\mathclose{}\right|\gg_{d}\delta^{O_{d}(1)}N.$

We have

$|e(\xi qz)-1|\leq|z|\cdot\left\|\xi
q\right\|_{{\mathbb{R}}/{\mathbb{Z}}}\ll\delta^{-O(1)}N^{\prime}/N$

for all $z\in[N^{\prime}]$, so, with $C$ sufficiently large, we obtain

$\sum_{u}\mathopen{}\left|\operatorname*{\mathbb{E}}_{z\in[N^{\prime}]}f_{1}(u+qz)\mathclose{}\right|\gg\delta^{O(1)}N.$

Finally, since $f_{1}$ is supported on $[N]$, there is no contribution from
$u$’s outside of $[\pm N]$, and we get

$\displaystyle\operatorname*{\mathbb{E}}_{u\in[\pm
N]}\mathopen{}\left|\operatorname*{\mathbb{E}}_{z\in[N^{\prime}]}f_{1}(u+qz)e(\xi
u)\mathclose{}\right|\gg\delta^{O(1)},$

as desired. ∎

We now deduce a multidimensional version of this corollary.

######  Corollary D.10.

For every $C_{1}>0$ there exists $C_{2}=C_{2}(C_{1},P)>0$ such that the
following holds. Let $\delta\in(0,1/10)$, let $V\leq W^{C_{1}}$ be a
nonnegative integer power of $W$, let $r\in[V]$, and let $N\geq
C_{2}V_{d}^{C_{2}}\delta^{-C_{2}}$ be an integer. Let $D\in{\mathbb{N}}$, and
let ${\textbf{v}}\in{\mathbb{Z}}^{D}$ have coordinates of size $O(1)$. If
$f_{0},f_{1}:{\mathbb{Z}}^{D}\to{\mathbb{C}}$ are $1$-bounded functions
supported on $[N]^{D}$ satisfying

$\displaystyle\mathopen{}\left|\sum_{\textbf{x}}\operatorname*{\mathbb{E}}_{z\in[K]}f_{0}({\textbf{x}})f_{1}({\textbf{x}}+{\textbf{v}}\widetilde{P}_{[r,V]}(z))\mathclose{}\right|\geq\delta
N^{D},$

then for each $i\in\\{0,1\\}$ there exists a positive integer
$q_{i}\ll_{C_{1},D,P}\delta^{-O_{C_{1},D,P}(1)}$ such that

$\displaystyle\sum_{\textbf{x}}\mathopen{}\left|\operatorname*{\mathbb{E}}_{z\in[N^{\prime}]}f_{i}({\textbf{x}}+q_{i}{\textbf{v}}z)\mathclose{}\right|\gg_{C_{1},D,P}\delta^{O_{C_{1},D,P}(1)}N^{D}\quad\textrm{for\;
all}\quad 1\leq N^{\prime}\leq\delta^{O_{C_{1},D,P}(1)}N.$

###### Proof.

We fix $C_{1}>0$ and let all constants depend on $D$ and $P$. We just proof
the claim for $i=1$, as the other case follows by symmetry. Introducing an
extra averaging over ${\textbf{v}}\cdot[N]$ gives

$\displaystyle\sum_{\textbf{x}}\mathopen{}\left|\sum_{y\in[N]}\operatorname*{\mathbb{E}}_{z\in[K]}f_{0}({\textbf{x}}+{\textbf{v}}y)f_{1}({\textbf{x}}+{\textbf{v}}(y+\widetilde{P}_{[r,V]}(z)))\mathclose{}\right|\geq\delta
N^{D+1}.$

Since the coordinates of v have size $O(1)$, the functions
${\textbf{x}}\mapsto f_{0}({\textbf{x}}+{\textbf{v}}y)$ vanish whenever
$|{\textbf{x}}|\gg N$ as $y$ ranges over $[N]$. Pigeonholing in x, we can
therefore find $\Omega(\delta N^{D})$ values ${\textbf{x}}\in{\mathbb{Z}}^{D}$
for which

(39)
$\displaystyle\mathopen{}\left|\sum_{y\in[N]}\operatorname*{\mathbb{E}}_{z\in[K]}f_{0}({\textbf{x}}+{\textbf{v}}y)f_{1}({\textbf{x}}+{\textbf{v}}(y+\widetilde{P}_{[r,V]}(z)))\mathclose{}\right|\gg\delta
N,$

and so the previous corollary gives us positive integers
$q_{\textbf{x}}\ll\delta^{-O(1)}$ and $\delta^{O(1)}N\ll
N^{\prime}_{0,{\textbf{x}}}\leq N$ such that

$\displaystyle\operatorname*{\mathbb{E}}_{u\in[\pm
N]}\mathopen{}\left|\operatorname*{\mathbb{E}}_{z\in[N^{\prime}_{\textbf{x}}]}f_{1}({\textbf{x}}+{\textbf{v}}(u+q_{\textbf{x}}z))\mathclose{}\right|\gg\delta^{O(1)}$

for all $N^{\prime}_{\textbf{x}}\in[N^{\prime}_{0,{\textbf{x}}}]$. We set
$N^{\prime}_{0}:=\min_{\textbf{x}}N^{\prime}_{0,{\textbf{x}}}$ to eliminate
the dependence on x, where the minimum is taken over the $\Omega(\delta
N^{D})$ good values ${\textbf{x}}\in{\mathbb{Z}}^{D}$. Since the lower bounds
on $N^{\prime}_{0,{\textbf{x}}}$ are independent on x, we deduce that
$N^{\prime}_{0}\gg\delta^{O(1)}N$. Similarly, since there are only
$O(\delta^{-O(1)})$ choices of $q_{\textbf{x}}$, the pigeonhole principle
produces some $q\ll\delta^{-O(1)}$ for which

$\displaystyle\sum_{\textbf{x}}\operatorname*{\mathbb{E}}_{u\in[\pm
N]}\mathopen{}\left|\operatorname*{\mathbb{E}}_{z\in[N^{\prime}]}f_{1}({\textbf{x}}+{\textbf{v}}(u+qz))\mathclose{}\right|\gg\delta^{O(1)}N^{D}$

for all $N^{\prime}\leq N^{\prime}_{0}$. The result follows upon shifting
${\textbf{x}}\mapsto{\textbf{x}}-{\textbf{v}}u$. ∎

##  Appendix E Fourier uniformity of difference of weights

The purpose of this section is to show that the weight $\nu^{*}$ from the
proof of Proposition 7.2 is highly Fourier-uniform on arithmetic progressions
of difference $V$. Our argument is a slight modification of the proof of [34,
Lemma B.8]. Recall that the leading term of $\widetilde{P}(z)$ is
$W_{d}z^{d}$, where $W_{d}=\beta_{d}\beta_{1}^{d-2}W^{d-1}$, and our weights
are

$\displaystyle\tilde{\nu}(z)=\frac{N}{(N/W_{d})^{1/d}}1_{\widetilde{P}([(N/W_{d})^{1/d}])}(z)=N^{(d-1)/d}W_{d}^{1/d}\sum_{z^{\prime}\in[(N/W_{d})^{1/d}]}1_{\widetilde{P}(z^{\prime})}(z),$
$\displaystyle\nu(z)=d^{-1}1_{[N]}(z)(N/(z+1))^{(d-1)/d},\quad\text{and}\quad\nu^{*}(z)=\tilde{\nu}(z)-\nu(z).$

The following proposition captures the main estimate.

######  Proposition E.1.

For every $C_{1}>0$ there exists $C_{2}=C_{2}(C_{1},P),\;c=c(C_{1},P)>0$ such
that the following holds. If $V\leq W^{C_{1}}$ is a nonnegative integer power
of $W$ and $N\geq W^{C_{2}}$, then

$\max_{r\in[V]}\max_{\theta\in\mathbb{R}/\mathbb{Z}}\mathopen{}\left|\sum_{z\in\mathbb{Z}}e(\theta
z)\nu^{*}(Vz+r)\mathclose{}\right|\ll_{C_{1},P}\frac{N}{Vw^{c}}.$

Notice that the trivial bound (from the triangle inequality) is $\ll N/V$; our
gain is in the (relatively modest) $w^{-c}$ term.

###### Proof.

We fix $C_{1}>0$ and let all the constants depend on $C_{1}$ and $P$. Hensel’s
Lemma and the identity $\widetilde{P}(z)\equiv z\\!\\!\pmod{W}$ ensure that
for each $r\in[V]$ there is a unique $r^{\prime}\in[V]$ such that
$\widetilde{P}(r^{\prime})\equiv r\\!\\!\pmod{V}$. It follows that
$\widetilde{P}(z^{\prime})\equiv r\\!\\!\pmod{V}$ if and only if
$z^{\prime}\equiv r^{\prime}\\!\\!\pmod{V}$, so

$\displaystyle\sum_{z}e(\theta z)\tilde{\nu}(Vz+r)$
$\displaystyle=N^{(d-1)/d}W_{d}^{1/d}\sum_{z}e(\theta
z)\sum_{z^{\prime}\in[(N/W_{d})^{1/d}]}1_{\widetilde{P}(z^{\prime})}(Vz+r)$
$\displaystyle=N^{(d-1)/d}W_{d}^{1/d}\sum_{z^{\prime}\in[(N/W_{d})^{1/d}V^{-1}]}e\mathopen{}\left(\theta\frac{\widetilde{P}(Vz^{\prime}+r^{\prime})-r}{V}\mathclose{}\right).$

Substituting $z$ for $z^{\prime}$ and $V\theta$ for $\theta$, and then
multiplying both $\tilde{\nu}$ and $\nu$ by $e(\theta r)$, we find that it
suffices to prove the inequality

$\left|N^{(d-1)/d}W_{d}^{1/d}\sum_{z\in[(N/W_{d})^{1/d}V^{-1}]}e(\theta\widetilde{P}(Vz+r^{\prime}))\right.\\\
\left.-d^{-1}\sum_{z\in[N/V]}(N/(Vz+r))^{(d-1)/d}e(\theta(Vz+r+1))\right|\ll\frac{N}{Vw^{c}}$

for all $r\in[V]$ and $\theta\in{\mathbb{R}}/{\mathbb{Z}}$.

We will require different arguments when $V\theta$ is in a minor arc, when it
is in the major arc around $0$, and when it is in a major arc not around
$0$.999These major and minor arcs are different from the major and minor arcs
in Appendix D.

We first analyze when the contribution of $\nu$ can be large. By summation by
parts, we have that

$d^{-1}\mathopen{}\left|\sum_{z\in[N/V]}(N/(Vz+r+1))^{(d-1)/d}e(\theta(Vz+r))\mathclose{}\right|$

equals

$\displaystyle
d^{-1}\mathopen{}\left|\sum_{z\in[N/V]}(N/(Vz+r+1))^{(d-1)/d}e(\theta
Vz)\mathclose{}\right|$
$\displaystyle\qquad\qquad\ll\sum_{t\in[N/V-1]}\left(\left(\frac{N}{Vt+r+1}\right)^{(d-1)/d}-\left(\frac{N}{V(t+1)+r+1}\right)^{(d-1)/d}\right)\mathopen{}\left|\sum_{z\in[t]}e(V\theta
z)\mathclose{}\right|$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad+\mathopen{}\left|\sum_{z\in[N/V]}e(V\theta
z)\mathclose{}\right|$
$\displaystyle\qquad\qquad\ll\sum_{t\in[N/V-1]}(N/V)^{(d-1)/d}t^{(1-2d)/d}\min\left\\{t,\frac{1}{\left\|V\theta\right\|_{\mathbb{R}/\mathbb{Z}}}\right\\}+\min\left\\{N/V,\frac{1}{\left\|V\theta\right\|_{\mathbb{R}/\mathbb{Z}}}\right\\}$
$\displaystyle\qquad\qquad\ll\frac{(N/V)^{(d-1)/d}}{\left\|V\theta\right\|_{\mathbb{R}/\mathbb{Z}}^{1/d}}+\min\left\\{N/V,\frac{1}{\left\|V\theta\right\|_{\mathbb{R}/\mathbb{Z}}}\right\\},$

where in the second-to-last line we split the sum at
$t=1/\|V\theta\|_{\mathbb{R}/\mathbb{Z}}$. This quantity is $\ll N/(Vw^{c})$
unless $\left\|V\theta\right\|_{\mathbb{R}/\mathbb{Z}}<Vw^{cd}/N$.

We now analyze when the contribution of $\tilde{\nu}$ can be large. By [11,
Proposition 4.3] and [21, Lemma A.10], we have

$\mathopen{}\left|N^{(d-1)/d}W_{d}^{1/d}\sum_{z\in[(N/W_{d})^{1/d}V^{-1}]}e(\theta\widetilde{P}(Vz+r^{\prime}))\mathclose{}\right|\ll\frac{N}{Vw^{c}}$

unless there is some positive integer $q\ll w^{O(c)}$ such that

(40)
$\displaystyle\left\|q\theta\widetilde{P}(V\cdot+r^{\prime})\right\|_{C^{\infty}[(N/W_{d})^{1/d}V^{-1}]}\ll
w^{O(c)}.$

Let $R(z):=q\theta(Vz+\widetilde{P}(r^{\prime}))$, so that
$R\circ\widetilde{P}_{[r^{\prime},V]}(z)=q\theta\widetilde{P}(Vz+r^{\prime})$.
Setting $T=N/V$ and recalling that $V_{d}=W_{d}V^{d-1}$, we can write the
estimate (40) as

$\displaystyle\left\|R\circ\widetilde{P}_{[r^{\prime},V]}\right\|_{C^{\infty}[(T/V_{d})^{1/d}]}\ll
w^{O(c)}.$

Lemma C.3 then gives

$\displaystyle\left\|qV\theta\right\|_{{\mathbb{R}}/{\mathbb{Z}}}\ll\frac{Vw^{O(c)}}{N}.$

Hence the $\tilde{\nu}$-contribution is $\ll N/(Vw^{c})$ unless there is some
positive integer $q\ll w^{O(c)}$ such that
$\left\|qV\theta\right\|_{\mathbb{R}/\mathbb{Z}}\ll Vw^{O(c)}/N$.

Comparing the outputs of the previous two paragraphs, we see that the
conclusion of the proposition holds in the “minor arc” case where there is no
$q\ll w^{O(c)}$ such that $\left\|qV\theta\right\|_{\mathbb{R}/\mathbb{Z}}\ll
Vw^{O(c)}/N$. Henceforth, we assume that we are in the “major arc” case where
there is some $q\ll w^{O(c)}$ such that
$\left\|qV\theta\right\|_{\mathbb{R}/\mathbb{Z}}\leq Vw^{O(c)}/N$. In this
case, we write

$V\theta=a/q+\theta^{*},$

where $a,q$ are coprime integers with $1\leq q\ll w^{O(c)}$, and

$|\theta^{*}|\ll Vw^{O(c)}/N\leq(N/W_{d})^{1/(4d)}V^{-4}$

(say). Since the implicit constant in the term $w^{O(c)}$ depends only on $d$,
choosing $c$ sufficiently small (depending on $d$) guarantees that $q<w$.

First, assume that $q>1$. The $\nu$-contribution is $\ll N/(Vw^{c})$. To
handle the $\tilde{\nu}$-contribution, we use Lemma D.3 with
$Q(z)=\widetilde{P}_{[r^{\prime},V]}(z)$, $K=(N/W_{d})^{1/d}V^{-1}$, and
$\varepsilon=1/4$ to express

$\sum_{z\in[(N/W_{d})^{1/d}V^{-1}]}e(\theta\widetilde{P}(Vz+r^{\prime}))\\\
=e(\theta\widetilde{P}(r^{\prime}))\operatorname*{\mathbb{E}}_{u\in[q]}e((a/q)\widetilde{P}_{[r^{\prime},V]}(u))\int_{0}^{(N/W_{d})^{1/d}V^{-1}}e(\theta^{*}\widetilde{P}_{[r^{\prime},V]}(x))\,dx\\\
+O((N/W_{d})^{1/(2d)}V^{-1/2}).$

Since $q$ is smaller than $w$, it shares a prime factor with $W$, and so Lemma
D.4 tells us that the average
$\operatorname*{\mathbb{E}}_{u\in[q]}e((a/q)\widetilde{P}_{[r^{\prime},V]}(u))$
vanishes. Hence

$N^{(d-1)/d}W_{d}^{1/d}\sum_{z\in[(N/W_{d})^{1/d}V^{-1}]}e(\theta\widetilde{P}(Vz+r^{\prime}))\ll
N/(Vw^{c})$

(with room to spare) by the assumption that $N$ is larger than a suitable
power of $V$.

Finally, assume that $q=1$, in which case $a=0$ and
$\left\|V\theta\right\|_{\mathbb{R}/\mathbb{Z}}\ll Vw^{O(c)}/N$. We will break
the sum in the $\nu$-contribution into intervals and show that each one
approximately cancels out with a single summand from the
$\tilde{\nu}$-contribution. Since

$\widetilde{P}_{[r^{\prime},V]}(z)-W_{d}V^{d-1}z^{d}\ll V^{O(1)}z^{d-1}$

and

$\displaystyle\widetilde{P}(r^{\prime})-r=Vu\quad\textrm{for some integer
}|u|\ll W_{d}V^{d-1},$

we have

$\mathopen{}\left|\sum_{z\in[(N/W_{d})^{1/d}V^{-1}]}(e(\theta\widetilde{P}(Vz+r^{\prime}))-e(\theta(W_{d}V^{d}z^{d}+r)))\mathclose{}\right|\ll
V^{O(1)}.$

This lets us simplify the $\tilde{\nu}$-contribution by removing lower-order
terms, and it suffices to show that

$\left|N^{(d-1)/d}W_{d}^{1/d}e(\theta
r)\sum_{z\in[(N/W_{d})^{1/d}V^{-1}]}e(\theta W_{d}V^{d}z^{d})\right.\\\
\left.-d^{-1}\sum_{z\in[N/V]}(N/(Vz+r+1))^{(d-1)/d}e(\theta(Vz+r))\right|\ll\frac{N}{Vw^{c}}.$

We break the second sum into intervals of the form

$I_{z}=[A_{z},B_{z}]:=[W_{d}V^{d-1}z^{d},W_{d}V^{d-1}(z+1)^{d}-1]$

with length $|I_{z}|=W_{d}V^{d-1}dz^{d-1}(1+O(z^{-1}))$ for
$z\in[(N/W_{d})^{1/d}V^{-1}]$. For $t\in I_{z}$, we bound

$\displaystyle\mathopen{}\left|\mathopen{}\left(\frac{N}{Vt+r+1}\mathclose{}\right)^{(d-1)/d}-\mathopen{}\left(\frac{N}{VA_{z}}\mathclose{}\right)^{(d-1)/d}\mathclose{}\right|$
$\displaystyle\ll\mathopen{}\left|\frac{N}{Vt+r+1}-\frac{N}{VA_{z}}\mathclose{}\right|\cdot\mathopen{}\left(\frac{N}{VA_{z}}\mathclose{}\right)^{-1/d}$
$\displaystyle\leq\mathopen{}\left|\frac{VA_{z}-Vt-r-1}{Vt+r+1}\mathclose{}\right|\cdot\mathopen{}\left(\frac{N}{VA_{z}}\mathclose{}\right)^{(d-1)/d}$
$\displaystyle\ll\frac{|I_{z}|}{A_{z}}\cdot\mathopen{}\left(\frac{N}{VA_{z}}\mathclose{}\right)^{(d-1)/d}\ll
z^{-1}\mathopen{}\left(\frac{N}{VA_{z}}\mathclose{}\right)^{(d-1)/d}$

and

(41) $\displaystyle\mathopen{}\left|e(\theta\cdot Vt)-e(\theta\cdot
VA_{z})\mathclose{}\right|\leq\left\|V\theta\right\|_{{\mathbb{R}}/{\mathbb{Z}}}\cdot|I_{z}|\ll\frac{V^{O(1)}}{N^{1/d}}\ll
N^{-1/(2d)}$

as long as $N\gg V^{\Omega(1)}$. Summing over $t\in I_{z}$, we obtain the key
estimate

$\displaystyle d^{-1}\sum_{t\in I_{z}}(N/(Vt+r+1))^{(d-1)/d}e(\theta(Vt+r))$
$\displaystyle\qquad\qquad=e(\theta r)d^{-1}\sum_{t\in
I_{z}}(N/(VA_{z}))^{(d-1)/d}e(\theta VA_{z})(1+O(N^{-1/2d}+z^{-1}))$
$\displaystyle\qquad\qquad=e(\theta
r)W_{d}V^{d-1}z^{d-1}(N/(W_{d}V^{d}z^{d}))^{(d-1)/d}e(\theta
W_{d}V^{d}z^{d}))(1+O(N^{-1/2d}+z^{-1}))$ $\displaystyle\qquad\qquad=e(\theta
r)N^{(d-1)/d}W_{d}^{1/d}e(\theta W_{d}V^{d}z^{d})(1+O(N^{-1/2d}+z^{-1})).$

The lemma follows by summing over $z\in[(N/W_{d})^{1/d}V^{-1}]$ and noting
that

$\mathopen{}\left|\sum_{z\in[(N/W_{d})^{1/d}V^{-1}]}N^{(d-1)/d}W_{d}^{1/d}(N^{-1/2d}+z^{-1})\mathclose{}\right|\ll\frac{N}{Vw^{c}},$

again with room to spare since $W$ is sufficiently small compared to $N$. ∎

##  Appendix F Supersaturation

The purpose of this short section is to prove a supersaturation result for
corners. We apply Varnavides’ now-standard trick from [45] to Shkredov’s
result on corners [39].

######  Theorem F.1 ([39]).

There exists a constant $c>0$ such that the following holds: If
$A\subseteq[N]^{2}$ has size $\delta N^{2}$ for some $\delta\in(0,1/10)$ and
$N\geq\exp\exp(\delta^{-c})$, then $A$ contains a nontrivial corner.

######  Proposition F.2.

There exists a constant $c^{\prime}>0$ such that the following holds: If
$A\subseteq[N]^{2}$ has size $\delta N^{2}$ for some $\delta\in(0,1/10)$ and
$N\geq\exp\exp(\delta^{-c^{\prime}})$, then $A$ contains at least
$(\exp(-\exp(\delta^{-c^{\prime}})))N^{3}$ nontrivial corners.

###### Proof.

Let $M:=\exp\exp((\delta/2)^{c})$, where $c$ is the constant from Theorem F.1.
For each $1\leq d\leq N/(3M)$ and ${\textbf{u}}\in[-d(M-1),N-1]^{2}$, define
the set

$\lambda(d,{\textbf{u}}):=A\cap({\textbf{u}}+d\cdot[M]^{2}).$

For fixed $d$, each element of $A$ is contained in exactly $M^{2}$ of the sets
$\lambda(d,{\textbf{u}})$, so

$\sum_{\textbf{u}}|\lambda(d,{\textbf{u}})|=M^{2}|A|=\delta M^{2}N^{2}.$

Say that the pair $(d,{\textbf{u}})$ is _good_ if
$|\lambda(d,{\textbf{u}})|\geq(\delta/2)M^{2}$, and let $X(d)$ denote the
number of u’s such that $(d,{\textbf{u}})$ is good. We can bound

$\delta M^{2}N^{2}=\sum_{\textbf{u}}|\lambda(d,{\textbf{u}})|\leq
X(d)M^{2}+(N+d(M-1))^{2}\cdot(\delta/2)M^{2},$

and so (for instance)

$X(d)\geq\delta N^{2}-(\delta/2)(N+N/3)^{2}=(\delta/9)N^{2}.$

Hence the total number of good pairs $(d,{\textbf{u}})$ (for all $d$) is at
least $(\delta/(27M))N^{3}$. Theorem F.1 tells us that if $(d,{\textbf{u}})$
is good, then $\lambda(d,{\textbf{u}})$ contains a nontrivial corner. Finally,
each nontrivial corner is contained in at most $M^{3}$ such sets
$\lambda(d,{\textbf{u}})$ (there are at most $M$ choice of $d$ and then at
most $M^{2}$ choices of u), so we conclude that the number of nontrivial
corners in $A$ is at least

$\frac{\delta}{27M^{4}}N^{3}\geq(\exp(-\exp(\delta^{-c^{\prime}})))N^{3}$

with a suitable choice of $c^{\prime}>0$. ∎

## References

  * [1] V. Bergelson and A. Best.  On the polynomial Szemerédi theorem in finite commutative rings.  Preprint 2023, arXiv:2303.17928.
  * [2] 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.
  * [3] J. Bourgain and M.-C. Chang.  Nonlinear Roth type theorems in finite fields.  Israel J. Math., 221:853–867, 2017.
  * [4] J. Chapman and S. Chow.  Generalised Rado and Roth criteria.  Ann. Sc. Norm. Super. Pisa Cl. Sci., 2023.
  * [5] D. Dong, X. Li, and W. Sawin.  Improved estimates for polynomial Roth type theorems in finite fields.  J. Anal. Math., 141:689–705, 2020.
  * [6] H. Furstenberg.  Ergodic behavior of diagonal measures and a theorem of Szemerédi on arithmetic progressions.  J. Anal. Math., 31(1):204–256, 1977.
  * [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.  A new proof of Szemerédi’s theorem.  Geom. Funct. Anal., 11(3):465–588, 2001.
  * [9] B. Green.  An argument of Shkredov in the finite field setting.  Available at http://www.dpmms.cam.ac.uk/~bjg23/.
  * [10] B. Green.  Finite field models in additive combinatorics.  Surveys in combinatorics 2005, London Math. Soc. Lecture Note Ser., 237:1–27.
  * [11] B. Green and T. Tao.  The quantitative behaviour of polynomial orbits on nilmanifolds.  Ann. of Math., 175:465–540, 2012.
  * [12] B.J. Green.  On arithmetic structures in dense sets of integers.  Duke Math. J., 114:215–238, 2002.
  * [13] R. Han, M. T. Lacey, and F. Yang.  A polynomial Roth theorem for corners in finite fields.  Mathematika, 67(4):885–896, 2021.
  * [14] B. Host and B. Kra.  Nilpotent structures in ergodic theory.  AMS, 2018.
  * [15] 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.
  * [16] N. Kravitz, B. Kuca, and J. Leng.  Quantitative concatenation for polynomial box norms, 2024.  manuscript.
  * [17] B. Kuca.  Further bounds in the polynomial Szemerédi theorem over finite fields.  Acta Arith., 198:77–108, 2021.
  * [18] B. Kuca.  Multidimensional polynomial patterns over finite fields: Bounds, counting estimates and Gowers norm control.  Adv. Math., 448:109700, 2024.
  * [19] B. Kuca.  Multidimensional polynomial Szemerédi theorem in finite fields for polynomials of distinct degrees.  Israel J. Math., 259:589–620, 2024.
  * [20] M.T. Lacey and W. McClain.  On an argument of Shkredov on two-dimensional corners.  Online J. Anal. Comb., 2, 2007.
  * [21] J. Leng.  Efficient Equidistribution of Nilsequences.  Preprint 2023, arXiv:2312.10772.
  * [22] J. Leng.  Efficient equidistribution of periodic nilsequences and applications.  Preprint 2023, arXiv:2306.13820.
  * [23] 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.
  * [24] J. Leng, M. Sawhney, and A. Sah.  Quasipolynomial bounds on the inverse theorem for the Gowers $U^{s+1}[N]$-norm.  Preprint 2024, arXiv:2402.17994.
  * [25] F. Manners.  True complexity and iterated Cauchy-Schwarz.  Preprint 2018, arXiv:2109.05731.
  * [26] M. Ortega and S. Prendiville.  Extremal Sidon sets are Fourier uniform, with applications to partition regularity.  J. Théor. Nombres Bordeaux, 35(1):115–134, 2023.
  * [27] S. Peluse.  Finite field models in arithmetic combinatorics – twenty years on.  arXiv:2312.08100.
  * [28] S. Peluse.  Three-term polynomial progressions in subsets of finite fields.  Israel J. Math., 228:379–405, 2018.
  * [29] S. Peluse.  On the polynomial Szemerédi theorem in finite fields.  Duke Math. J., 168(5):749–774, 2019.
  * [30] S. Peluse.  Bounds for sets with no polynomial progressions.  Forum Math. Pi, 8, 2020.
  * [31] S. Peluse and S. Prendiville.  Quantitative bounds in the non-linear Roth theorem.  Preprint 2019, arXiv:1903.02592.
  * [32] S. Peluse and S. Prendiville.  A polylogarithmic bound in the nonlinear Roth theorem.  Int. Math. Res. Not., 2020.  rnaa261.
  * [33] S. Peluse, S. Prendiville, and X. Shao.  Bounds in a popular multidimensional nonlinear Roth theorem, 2024.  manuscript.
  * [34] S. Peluse, A. Sah, and M. Sawhney.  Effective bounds for Roth’s theorem with shifted square common difference.  Preprint 2023, arXiv:2309.08359.
  * [35] S. Prendiville.  Quantitative bounds in the polynomial Szemerédi theorem: the homogeneous case.  Discrete Anal., 5, 2017.  34 pp.
  * [36] K. F. Roth.  On certain sets of integers.  J. Lond. Math. Soc., 28(1):104–109, 1953.
  * [37] A. Sárközy.  On difference sets of sequences of integers. I.  Acta Math. Hungar., 31(1-2):125–149, 1978.
  * [38] A. Sárközy.  On difference sets of sequences of integers. III.  Acta Math. Hungar., 31:355–386, 1978.
  * [39] I. D. Shkredov.  On a generalization of Szemerédi’s theorem.  Proc. Lond. Math. Soc., 93(3):723–760, 2006.
  * [40] I. D. Shkredov.  On a problem of Gowers.  Izv. Math., 70(2):385–425, 2006.
  * [41] E. Stein.  Harmonic Analysis: Real-variable Methods, Orthogonality and Oscillatory Integrals.  Princeton University Press, 1993.
  * [42] E. Szemerédi.  On sets of integers containing $k$ elements in arithmetic progression.  Acta Arith., 27(1):199–245, 1975.
  * [43] T. Tao.  Higher order Fourier analysis.  AMS, 2012.
  * [44] T. Tao and J. Teräväinen.  Quantitative bounds for Gowers uniformity of the Möbius and von Mangoldt functions.  J. Eur. Math. Soc, 2023.
  * [45] P. Varnavides.  On certain sets of positive density.  J. Lond. Math. Soc., s1-34(3):358–360, 1959.
  * [46] T. Wooley.  Analytic number theory: introduction to the circle method and its application, 2023.  Lecture notes available at https://www.math.purdue.edu/~twooley/2023ant/2023antnotes.pdf.
  * [47] T. Wooley.  Nested efficient congruencing and relatives of Vinogradov’s mean value theorem.  Proc. Lond. Math. Soc., 118(4):942–1016, 2019.