# Efficient equidistribution of periodic nilsequences and applications

James Leng  Department of Mathematics, UCLA, Los Angeles, CA 90095, USA
<EMAIL_ADDRESS>
###### Abstract.

This is a companion paper to [13]. We deduce an equidistribution theorem for
periodic nilsequences and use this theorem to give two applications in
arithmetic combinatorics. The first application is quasi-polynomial bounds for
a certain complexity one polynomial progression, improving the iterated
logarithm bound previusly obtained. The second application is a proof of the
quasi-polynomial $U^{4}[N]$ inverse theorem. In work with Sah and Sawhney, we
obtain improved bounds for sets lacking nontrivial $5$-term arithmetic
progressions.

##  1\. Introduction

In [13], the author gave a proof of improved bounds for the equidistribution
of nilsequences. The author found that the Ratner-type factorization theorem
was inefficient for quantitative higher order Fourier analysis. In attempting
to salvage that theorem, the author proved an equidistribution theorem for a
$G_{(s)}$-vertical character. An informal version of that equidistribution
theorem is as follows (the precise statement can be found in [13, Theorem 3]).

######  Theorem 1 (Informal Equidistribution Theorem).

Let $G/\Gamma$ is a nilmanifold and $F(g(n)\Gamma)$ is a nilsequence with $F$
a $G_{(s)}$-vertical character with nonzero frequency $\xi$. Suppose

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

Then $F$ is “morally” a step $\leq s-1$ nilsequence with “good bounds.”

Here, “good bounds” denotes bounds whose exponents are polynomial in the
dimension of the nilmanifold. Since nilsequences may be Fourier expanded into
nilcharacters via [13, Lemma A.7], it follows that such a theorem can recover
an equidistribution theorem for all nilsequences with good bounds. In this
article, we shall consider the analogue of this equidistribution theorem for
periodic nilsequences along with applications of that theorem.

###  1.1. Main Results

Our first main result is the following equidistribution theorem with better
bounds (see Section 2 and [13, Section 2] for undefined notions).

######  Theorem 2.

mainresult1 Let $\delta\in(0,1/10)$, $N>100$ prime, and $G/\Gamma$ be a
nilmanifold of step $s$, degree $k$, dimension $d$, and complexity at most
$M$. Furthermore, let $F(g(n)\Gamma)$ be a periodic nilsequence modulo $N$
with $F$ a $G_{(s)}$ vertical character with frequency $\xi$ with $|\xi|\leq
M/\delta$. Suppose

$|\mathbb{E}_{n\in\mathbb{Z}/N\mathbb{Z}}F(g(n)\Gamma)|\geq\delta.$

Then either $N\ll(M/\delta)^{O_{k}(d^{O_{k}(1)})}$ or there exists horizontal
characters $\eta_{1},\dots,\eta_{r}$ of size at most
$(M/\delta)^{O_{k}(d^{O_{k}(1)})}$ with $1\leq r\leq\mathrm{dim}(G/[G,G])$
such that

$\|\eta_{i}\circ g\|_{C^{\infty}[N]}=0$

and such that any $s$ elements $w_{1},\dots,w_{s}\in
G^{\prime}:=\bigcap_{i=1}^{r}\mathrm{ker}(\eta_{i})$ satisfies

$\xi([[[w_{1},w_{2}],w_{3}],\dots,w_{s}])=0.$

######  Remark 1.1.

This theorem is proven by black-boxing [13, Theorem 3] (via an argument due to
Candela and Sisask [2]; see also, [12, 10, 11]). However one main motivation
of the article is to dicuss the proof in 3 simpler cases (with self contained
proofs) which were crucial in developing the proof in [13].

Our second main result is the following.

######  Theorem 3.

mainresult2 Let $N$ be a large prime, $P,Q\in\mathbb{Z}[x]$ be linearly
independent with $P(0)=Q(0)=0$, and let $A\subseteq\mathbb{Z}_{N}$ be a subset
such that $A$ contains no configuration of the form
$(x,x+P(y),x+Q(y),x+P(y)+Q(y))$ with $y\neq 0$. Then

$|A|\ll_{P,Q}N\exp(-\log^{c_{P,Q}}(N)).$

This will be proven using a similar method as in [12], with input from
mainresult1 rather than [7]. Our final result is the quasi-polynomial
$U^{4}(\mathbb{Z}/N\mathbb{Z})$ inverse theorem.

######  Theorem 4.

mainresult4 Suppose $f\colon\mathbb{Z}/N\mathbb{Z}\to\mathbb{C}$ is a one-
bounded function with

$\|f\|_{U^{4}(\mathbb{Z}/N\mathbb{Z})}\geq\delta.$

Then there exists a nilmanifold $G/\Gamma$ with degree at most $3$, dimension
$\log(1/\delta)^{O(1)}$, complexity $O(1)$, and a nilsequence $F(g(n)\Gamma)$
on the nilmanifold with $F$ $1$-Lipschitz such that

$|\mathbb{E}_{n\in[N]}f(n)F(g(n)\Gamma)|\geq\exp(-\log(1/\delta)^{O(1)}).$

Since the initial version of this paper, this result and work with Sah and
Sawhney on improved bounds for $5$-term arithmetic progressions [15] have been
generalized in work with Sah and Sawhney [17] to the quasi-polynomial
$U^{s+1}[N]$ inverse theorem and sets lacking nontrivial $k$-term arithmetic
progressions [16]. The article can thus be treated as a “stepping-stone” for
the more general [13] and [17].

###  1.2. Discussion on the proof of the $U^{4}(\mathbb{Z}/N\mathbb{Z})$
inverse theorem

mainresult4 will be proven using a very similar method as in [8], with input
from twostepcase instead of [7] which simplifies the argument somewhat. The
advantage of the approach of [8] is that it avoids the use of “$1\%$
quadratics” that Gowers and Milicevic [4] and Manners [18] consider. We
instead consider a “$1\%$ linear” equation, which is substantially simpler.

Our primary improvement over [8] is the “sunflower” and “linearization” steps
which correspond to Sections 7 and 8 of that article. In [8], the authors
prove these steps by invoking the _Ratner-type factorization theorem_ , which
given a nilmanifold of dimension $d$ involves $O(d)$ iterations of the
Leibman-type theorem of Green and Tao [7, Theorem 2.9]. The sunflower and
linearization steps are also proven iteratively, with the number of iterations
being $O(d)$. Altogether, their proof involves $O(d^{2})$ many iterations of
the quantitative Leibman theorem of [7]. We are able to do each of the
“sunflower” and “linearization” steps in one single application of
twostepcase. The proofs given here are refinements of the proofs given in [8].
For instance, the proof of the sunflower step (sunflower) relies on the
Furstenberg-Weiss commutator argument used in [8] (but adapted to the setting
of [13, Theorem 8]) and the proof of linearization step (linearizationstep) is
similar to that of [8] in that it also relies on the Balog-Szemerédi-Gowers
theorem and a Freiman type theorem, though we use the refinement of the theory
due to Sanders [21].

###  1.3. Organization of the paper

In Section 2, we will define notation we need in addition to the notation in
[13]. Sections 3-5 will delve into examples and simple cases of the proof of
mainresult1, in order to motivate the proof of [13, Theorem 3]. In Sections 3,
we will prove an equidistribution theorem for degree two periodic bracket
polynomials. In Section 4, we will prove the degree two periodic case of
mainresult1. In Section 5, we will prove the full two-step case of
mainresult1. We will prove mainresult1 in Section 6 (by black-boxing [13,
Theorem 3]). We will prove mainresult2 in Section 7, and mainresult4 in
Section 8.

In Appendix A, we will deduce some auxiliary lemmas, used in Sections 3 and 4.
In Appendix B, we will collect and prove some lemmas on bracket polynomials;
these will be useful in Sections 3 and 8. Finally, in Appendix C, we will
include a different proof than the one suggested in Section 3 of a key lemma
of the equidistribution theory: the _refined bracket polynomial lemma_. We
believe this proof is somewhat more intuitive and offers more motivation for
the statement of the lemma than the proof presented in [13], which is cleaner.

###  1.4. Acknowledgements

We would like to thank Terry Tao for advisement and for suggesting a simpler
proof of the refined bracket polynomial lemma than the proof the author
initially came up with, which is present in Appendix C. We would also like to
thank Ashwin Sah and Mehtaab Sawhney for their interest in the author’s work
and being helpful and extremely supportive of the author. In particular, the
persistent questions of Ashwin Sah and Mehtaab Sawhney in the author’s work
led the author to realize a mistake in Section 8 in an earlier version of the
document. When the author presented a fix to them, they pointed out that there
is a more efficient way to “Pigeonhole” in the proof of sunflower which lead
to the quasi-polynomial bounds in mainresult4 instead of bounds of the shape
of $\exp(-\exp(O(\log\log(1/\delta)^{2})))$ that the author had in a previous
version. We are immensely grateful to them for communicating this point with
the author and allowing the author to write up their argument here. We would
in addition like to thank Ben Green and Sarah Peluse for helpful discussions.
The author is supported by an NSF Graduate Research Fellowship Grant No.
DGE-2034835.

##  2\. Notation

We shall use the notation in [13], with a few differences, which we shall
describe below.

######  Definition 2.1 (Periodic nilsequences).

Given a nilmanifold $G/\Gamma$ and an integer $N$, a polynomial sequence
$g\in\text{poly}(\mathbb{Z},G)$, and a Lipschitz function
$F:G/\Gamma\to\mathbb{C}$, we say $F(g(n)\Gamma)$ is a _periodic nilsequence
modulo $N$_ if $g(n+N)\Gamma=g(n)\Gamma$ for each $n\in\mathbb{Z}$.

######  Definition 2.2 (Smoothness norms).

Given a polynomial $p\colon\mathbb{Z}\to\mathbb{R}$ with
$p(n)=\sum_{i=0}^{d}\alpha_{i}n^{i}$, we write

$\|p\|_{C^{\infty}[N]}=\sup_{1\leq i\leq
d}N^{i}\|\alpha_{i}\|_{\mathbb{R}/\mathbb{Z}}.$

The reason we work with the above definition of $C^{\infty}$ norm rather than
the definition in [13] involving binomial coefficients is that this definition
is better adapted to polynomials $p\colon\mathbb{Z}/N\mathbb{Z}\to\mathbb{T}$,
which appear in the analysis of periodic nilsequences.

We shall also use $c(\delta)$ as in [13] as any quantity
$\gg(\delta/M)^{O_{k,\ell}(d)^{O_{k,\ell}(1)}}$; here, since we will be
working with single parameter nilsequences, we will always have $\ell=1$.

##  3\. Bracket polynomial heuristics

In this section, we shall deduce an equidistribution theorem for a periodic
degree two bracket polynomial. Such a polynomial is of the form

$e(\phi(n)):=e(-(\alpha_{1}n[\beta_{1}n]+\cdots+\alpha_{d}n[\beta_{d}n])+P(n))$

with $\phi(n+N)\equiv\phi(n)\pmod{1}$ and $\alpha_{i},\beta_{i}$ are rational
with denominator $N$. Such a function is _not_ a nilsequence but can be
written as $F(g(n)\Gamma)$ where $F\colon G/\Gamma\to\mathbb{C}$ is only
piecewise Lipschitz on a degree two nilmanifold $G/\Gamma$. To realize this,
we require the following definitions.

######  Definition 3.1 (Elementary two-step nilmanifold).

We shall define the _elementary two-step nilmanifold_ of dimension $2d+1$.
Define

$G=\begin{pmatrix}1&\mathbb{R}&\cdots&\cdots&\mathbb{R}\\\
0&1&\cdots&0&\mathbb{R}\\\ 0&0&1&\cdots&\mathbb{R}\\\ 0&0&0&\ddots&\vdots\\\
0&0&0&\cdots&1\end{pmatrix}$

and

$\Gamma=\begin{pmatrix}1&\mathbb{Z}&\cdots&\cdots&\mathbb{Z}\\\
0&1&\cdots&0&\mathbb{Z}\\\ 0&0&1&\cdots&\mathbb{Z}\\\ 0&0&0&\ddots&\vdots\\\
0&0&0&\cdots&1\end{pmatrix}$

equipped with the lower central series filtration. We write this in
coordinates as

$(x_{1},\dots,x_{d},y_{1},\dots,y_{d},z).$

We furthermore define the _horizontal component_ as

$\psi_{\mathrm{horiz}}(x_{1},\dots,x_{d},y_{1},\dots,y_{d},z):=(\vec{x},\vec{y})$

and the _vertical component_ as
$\psi_{\mathrm{vert}}(x_{1},\dots,x_{d},y_{1},\dots,y_{d},z):=z$.

We also define an elementary bracket quadratic below.

######  Definition 3.2 (Elementary bracket quadratic).

Consider $G/\Gamma$ an elementary two-step nilmanifold of dimension $2d+1$.
Given real numbers $\alpha_{1},\dots,\alpha_{d},\beta_{1},\dots,\beta_{d}$,
and $P$ a quadratic polynomial, we define the _elementary polynomial sequence_
associated to $(\vec{\alpha},\vec{\beta},P)$ via
$g(n)=(\alpha_{1}n,\dots,\alpha_{d}n,\beta_{1}n\cdots,\beta_{d}n,P(n))$. Note
that $G/\Gamma$ has the fundamental domain of $(-1/2,1/2]^{2d+1}$ via the map

$(x_{1},\dots,x_{d},y_{1},\dots,y_{d},z)\mapsto(\\{x_{1}\\},\dots,\\{x_{d}\\},\\{y_{1}\\},\dots,\\{y_{d}\\},\\{z-\vec{x}\cdot[\vec{y}]\\}).$

We can thus define the function $F:G/\Gamma\to\mathbb{C}$ as

$F((x_{1},\dots,x_{d},y_{1},\dots,y_{d},z)\Gamma)=e(-\sum_{i=1}^{d}x_{i}[y_{i}]+z).$

We see that

$F(g(n)\Gamma)=e(-\alpha_{1}n[\beta_{1}n]+\cdots+\alpha_{d}n[\beta_{d}n]+P(n));$

we define an _elementary bracket quadratic_ associated to
$(\vec{\alpha},\vec{\beta},P)$ as $F(g(n)\Gamma)$. We say that the two-step
bracket quadratic is _periodic_ modulo $N$ if $g(n+N)\Gamma=g(n)$.

We next define the asymmetric bilinear form of an elementary two-step
nilmanifold.

######  Definition 3.3 (Bilinear form of an elementary two-step nilmanifold).

Given an elementary two-step nilmanifold $G/\Gamma$ of dimension $d$, we can
define the associated _asymmetric bilinear—_ form
$\omega\colon(\mathbb{R}^{2d})^{2}\to\mathbb{R}$ as follows. If
$u_{1}=(\vec{x},\vec{y}),u_{2}((\vec{z},\vec{w})\in(\mathbb{R}^{2d})^{2}$, we
define

$\omega(u_{1},u_{2})=\vec{x}\cdot\vec{w}-\vec{y}\cdot\vec{z}.$

Finally, we require the following lemma, whose proof we omit (see periodic).

######  Lemma 3.1.

periodiclemma If $F(g(n)\Gamma)$ is an $N$-periodic elementary bracket
quadratic, and if $g(n)=(\vec{\alpha}n,\vec{\beta}n,P)$ with $P=an^{2}+bn+c$,
then $\vec{\alpha},\vec{\beta}$ are rational with denominator $N$, and $a$ is
rational with denominator $2N$.

We are now ready to state the equidistribution theorem for degree two bracket
polynomials.

######  Theorem 5.

twostepbracket Let $\delta\in(0,1/10)$ and $N>10$ a prime, and $G/\Gamma$ an
elementary two-step nilmanifold of dimension $2d+1$ with bilinear form
$\omega$, and $F(g(n)\Gamma)$ an elementary two-step bracket quadratic.
Suppose

$|\mathbb{E}_{n\in[N]}F(g(n)\Gamma)|\geq\delta.$

Then one of the following holds.

  * •

$N\ll\delta^{-O(d^{O(1)})}$;

  * •

or there exists some $0\leq r\leq 2d$ and $w_{1},\dots,w_{r}$ and
$\eta_{1},\dots,\eta_{2d-r}$ all linearly independent vectors in
$\mathbb{Z}^{2d}$ with $\langle w_{i},\eta_{j}\rangle=0$ and such that

$\|\eta_{i}\cdot\psi_{\mathrm{horiz}}(g)\|_{C^{\infty}[N]}=0\text{ and
}\|\omega(w_{i},\psi_{\mathrm{horiz}}(g))\|_{C^{\infty}[N]}=0.$

######  Remark 3.1.

Observing that $\omega$ is nondegenerate on the first $2d$ coordinates, we see
that $\omega$ is a _symplectic form_ on $\mathbb{R}^{2d}$. This theorem then
states that $\psi_{\mathrm{horiz}}(g)$ lies on a _isotropic subspace_ $V$ of
$\omega$; that is, a subspace $V$ with $\omega(V,V)=0$. To see this, note that
if $v,w\in V$, it suffices to show that $\omega(v,w)=0$. Since $\eta_{i}$
annihilates $v$, it may be spanned by $w_{j}$’s, and because
$\omega(w_{j},w)=0$, it follows that $\omega(v,w)=0$.

###  3.1. Proof of twostepbracket

Let

$g(n)=(\alpha_{1}n,\dots,\alpha_{d}n,\beta_{1}n,\dots,\beta_{d}n,P(n)).$

Since

$\alpha_{i}n[\beta_{i}n]=(\\{\alpha_{i}\\}+[\alpha_{i}])n[(\\{\beta_{i}\\}+[\beta_{i}])n]=\\{\alpha_{i}\\}n[\\{\beta_{i}n\\}]+\\{\alpha_{i}\\}[\beta_{i}]n^{2}\pmod{1},$

we may reduce to the case where $|\alpha_{i}|,|\beta_{i}|\leq\frac{1}{2}$ by
modifying $P$. Applying the van der Corput inequality, there exists
$\delta^{O(1)}N$ many $h\in[N]$ such that

(3.1) $|\mathbb{E}_{n\in[N]}e(\phi(n+h)-\phi(n))|\geq\delta^{O(1)}.$

We next observe that if $\alpha$ and $\beta$ are arbitrary, then

$\alpha(n+h)[\beta(n+h)]-\alpha n[\beta n]=\alpha n[\beta h]+\alpha h[\beta
n]+[\text{Lower order terms}]$

where “lower order terms” denote a sum of $O(1)$ terms of the form $\\{\alpha
n\\}\\{\beta n\\},\\{\alpha h\\}\\{\beta n\\}$, $\\{\alpha h\\}\\{\beta h\\}$,
$\\{\alpha n\\}\\{\beta h\\}$. The key observation is that each of the
functions

$e(\\{\alpha n\\}\\{\beta n\\}),e(\\{\alpha h\\}\\{\beta n\\}),\text{ and
}e(\\{\alpha n\\}\\{\beta h\\})$

are functions on $\mathbb{T}^{2}$ in $(\\{\alpha n\\},\\{\beta n\\})$,
$(\\{\alpha h\\},\\{\beta n\\})$, and $(\\{\alpha n\\},\\{\beta h\\})$,
respectively, and thus may be Fourier expanded into terms such as (say)
$e(k_{1}\\{\alpha n\\}+k_{2}\\{\beta n\\})=e(k_{1}\alpha n+k_{2}\beta n)$.
Note that we have “removed” a bracket. Such a heuristic is made precise in
onevarfouriercomplexity and bilinearfouriercomplexity.

We may further analyze

$\alpha n[\beta h]=\alpha n(\beta h-\\{\beta h\\}),\alpha h[\beta n]=\\{\alpha
h\\}(\beta n-\\{\beta n\\})$

and so

$\alpha(n+h)[\beta(n+h)]-\alpha n[\beta n]=\alpha\beta nh+[(\alpha n,\beta
n),(\\{\alpha h\\},\\{\beta h\\})]+[\text{Lower order terms}]$

where $[(x,y),(z,w)]=xw-yz$. Thus, letting $\beta$ denote the coefficient the
quadratic term of the vertical component of $g$, we have

(3.2) $|\mathbb{E}_{n\in[N]}e(2\beta
nh-n\omega(\psi_{\mathrm{horiz}}(g),\\{\psi_{\mathrm{horiz}}(g)\\})+\text{[Lower
order terms]})|\geq\delta^{O(1)}.$

By onevarfouriercomplexity, bilinearfouriercomplexity, we thus have for real
$\gamma$ of denominator $N$ that

$|\mathbb{E}_{n\in\mathbb{Z}_{N}}e(\gamma
nh-n\omega(\psi_{\mathrm{horiz}}(g),\\{\psi_{\mathrm{horiz}}(g)\\})+\gamma
n)|\geq\delta^{O(d^{O(1)})}.$

By periodiclemma and letting $\alpha=\psi_{\mathrm{horiz}}(g)$ and $a$ equal
to vector induced by $a\cdot y=\omega(\psi_{\mathrm{horiz}}(g),y)$, we have

(3.3) $\|a\cdot\\{\alpha h\\}+\beta+\gamma h\|_{\mathbb{R}/\mathbb{Z}}=0.$

for $\delta^{O(d^{O(1)})}N$ many $h\in[N]$. In the next subsection, we prove a
crucial Diophantine approximation result for this hypothesis.

###  3.2. The refined bracket polynomial lemma

We have the following lemma.

######  Lemma 3.2 (Refined bracket polynomial lemma).

periodicrefined Let $\delta\in(0,1/10)$ and $N>100$ be prime. Suppose
$a,\alpha\in\mathbb{R}^{d}$, $a$ and $\alpha$ are rational with denominator
$N$, $|a|\leq M$, and

$\|\beta+a\cdot\\{\alpha h\\}\|_{\mathbb{R}/\mathbb{Z}}=0$

for $\delta N$ many $h\in[N]$. The either $N\ll(\delta/d^{d}M)^{-O(1)}$ or
$K/N\geq 1/10$ or else there exists linearly independent $w_{1},\dots,w_{r}$
and $\eta_{1},\dots,\eta_{d-r}$ in $\mathbb{Z}^{d}$ with size at most
$(\delta/d^{d}M)^{-O(1)}$ such that $\langle w_{i},\eta_{j}\rangle=0$,

$\|\eta_{j}\cdot\alpha\|_{\mathbb{R}/\mathbb{Z}}=0,\text{ and }|w_{i}\cdot
a|=\frac{(\delta/M)^{-O(1)}d^{O(d)}K}{N}.$

######  Remark 3.2.

The name “refined bracket polynomial lemma” is derived from the analogous
“bracket polynomial lemma” of [7, Proposition 5.3].

This lemma can be proved via the following lemma by applying $K=1/N^{2}$.

######  Lemma 3.3.

magicargument Let $\delta\in(0,1/10)$ and $N>100$ be prime. Suppose
$a,\alpha\in\mathbb{R}^{d}$ and $\alpha$ is rational with denominator $N$,
$|a|\leq M$, and

$\|\beta+a\cdot\\{\alpha h\\}\|_{\mathbb{R}/\mathbb{Z}}<K/N$

for $\delta N$ many $h\in[N]$. The either $N\ll(\delta/d^{d}M)^{-O(1)}$ or
$K/N\geq 1/10$ or else there exists linearly independent $w_{1},\dots,w_{r}$
and $\eta_{1},\dots,\eta_{d-r}$ in $\mathbb{Z}^{d}$ with size at most
$(\delta/d^{d}M)^{-O(1)}$ such that $\langle w_{i},\eta_{j}\rangle=0$,

$\|\eta_{j}\cdot\alpha\|_{\mathbb{R}/\mathbb{Z}}=0,\text{ and }|w_{i}\cdot
a|=\frac{(\delta/M)^{-O(1)}d^{O(d)}K}{N}.$

The magicargument is proved in [13, Lemma 3.4]. We will give another proof of
this lemma with worse bounds in Appendix C. Although our bounds there are
worse, they are sufficient for twostepbracket and for any application of the
refined bracket polynomial lemma in (the one-variable case of) [13]. A
corollary of this lemma is the following.

######  Corollary 3.1.

bracketpolynomialcorollary Let $\delta\in(0,1/10)$ and $N>100$ be prime.
Suppose $a,\alpha\in\mathbb{R}^{d}$ are rationals with $N$, $|a|\leq M$,
$\beta,\gamma\in\mathbb{R}$ with $\beta$ rational with denominator $N$, and

$\|\gamma+a\cdot\\{\alpha h\\}+\beta h\|_{\mathbb{R}/\mathbb{Z}}=0$

for $\delta N$ many $h\in[N]$. Then either $N\ll(d\delta/M)^{-O(d)^{O(1)}}$ or
there exists linearly independent $w_{1},\dots,w_{r}$ and
$\eta_{1},\dots,\eta_{d-r}$ such that $\langle w_{i},\eta_{j}\rangle=0$ and

$\|\eta_{j}\cdot\alpha\|_{\mathbb{R}/\mathbb{Z}}=0,\hskip
7.22743pt\|w_{i}\cdot a\|_{\mathbb{R}/\mathbb{Z}}=0.$

###### Proof.

We define $\tilde{a}=(a,1)\in\mathbb{R}^{d+1}$ and
$\tilde{\alpha}=(\alpha,\beta)\in\mathbb{R}^{d+1}$. Invoking periodicrefined,
there exists $w_{1},\dots,w_{r}$ and $\eta_{1},\dots,\eta_{d+1-r}$ such that
$|w_{i}(\tilde{a})|=0$,
$\|\eta_{j}(\tilde{\alpha})\|_{\mathbb{R}/\mathbb{Z}}=0$. We denote
$w_{i}=(u_{i},v_{i})$ and $\eta_{j}=(\mu_{j},\nu_{j})$ where
$u_{i}\in\mathbb{R}^{d}$ and $\mu_{j}\in\mathbb{R}^{d}$ for each $i$ and $j$.
Suppose $\nu_{1}\neq 0$. Let $\tilde{\eta_{j}}=\nu_{j}\mu_{1}-\mu_{j}\nu_{1}$.
We see that $\|\tilde{\eta_{j}}(\mu)\|_{\mathbb{R}/\mathbb{Z}}=0$. We claim
that the $\tilde{\eta_{j}}$’s are independent of each other. Suppose there
exists some $a_{i}$ such that

$\sum_{i\neq 1}a_{i}(\nu_{i}\mu_{1}-\mu_{i}\nu_{1})=0.$

We can rewrite this sum as

$\mu_{1}\left(\sum_{i\neq 1}a_{i}\nu_{i}\right)+\sum_{i\neq
1}(-a_{i}\nu_{1})\mu_{i}=0.$

Letting these coefficients of $\mu_{i}$ be $c_{i}$, we see that

$\sum_{i}c_{i}\nu_{i}=\nu_{1}\left(\sum_{i\neq
1}a_{i}\nu_{i}\right)-\sum_{i\neq 1}a_{i}\nu_{1}\nu_{i}=0.$

Thus, each of these coefficients are zero, and since $\nu_{1}$ is nonzero,
$a_{i}=0$. Thus, $\tilde{\eta_{j}}$’s are independent of each other. We next
claim that $\tilde{\eta_{j}}$ are orthogonal to the $u_{i}$’s. This is because

$\tilde{\eta_{j}}\cdot u_{i}=\nu_{j}\mu_{1}\cdot u_{i}-\nu_{1}\mu_{j}\cdot
u_{i}$ $\eta_{j}\cdot w_{i}=\mu_{j}\cdot u_{i}+\nu_{j}\cdot v_{i}=0$
$\eta_{1}\cdot w_{i}=\mu_{1}\cdot u_{i}+\nu_{1}\cdot v_{i}=0$

so subtracting the second and third equations gives that the first equation is
equal to zero. Finally, we claim that the $u_{i}$’s are linearly independent
of each other. To see this, note that $(u_{i},v_{i})$ are orthogonal to
$(\tilde{\eta_{j}},0)$ and $(\mu_{1},\nu_{1})$. Since $(0,1)$ is not
orthogonal to $(\mu_{1},\nu_{1})$, it follows that $(u_{i},v_{i})$ cannot span
$(0,1)$, so $(u_{i},v_{i}),(0,1)$ are linearly independent of each other,
which implies that $u_{i}$ are linearly independent of each other.

If $\nu_{i}\neq 0$ for some $i$, we let $\nu_{i}$ play the role of $\nu_{1}$
in the above argument. If $\nu_{i}=0$ for all $i$, we observe that $\mu_{j}$
are all linearly independent and that
$\|\mu_{j}\cdot\alpha\|_{\mathbb{R}/\mathbb{Z}}=0$. In addition, since
$v_{i}\cdot 1\in\mathbb{Z}$, we have
$\|w_{i}\cdot\tilde{a}\|_{\mathbb{R}/\mathbb{Z}}=\|u_{i}\cdot
a\|_{\mathbb{R}/\mathbb{Z}}=0$. Hence, choosing a linearly independent subset
of the $u_{i}$’s, we finish. ∎

We are now ready to finish the proof of twostepbracket.

###  3.3. Finishing the proof

We return to (3.3). Applying bracketpolynomialcorollary, we obtain
$w_{1},\dots,w_{r},\eta_{1},\dots,\eta_{d-r}$ such that

$\|w_{i}\cdot a\|_{\mathbb{R}/\mathbb{Z}}=0\text{ and
}\|\eta_{j}\cdot\alpha\|_{\mathbb{R}/\mathbb{Z}}=0.$

Unwinding the definitions of $a$ and $\alpha$ gives twostepbracket.

##  4\. The degree two nilsequence case

Having discussed bracket polynomial heuristics, we now turn to the degree-two
two-step nilsequence case. Our proof follows that of [7] which applies the van
der Corput inequality and performs an analysis of the resulting nilsequence on
the group

$G^{\square}:=G\times_{G_{2}}G:=\\{(g^{\prime},g)\in G^{2}:g^{\prime}g^{-1}\in
G_{2}\\}.$

Properties of $G^{\square}$ can be found in [13, Lemma A.3, Lemma A.4]. The
reader is encouraged to observe parallels between this section and the
previous section. We now state the main theorem of this section:

######  Theorem 6.

twostepcase Let $N$ be a prime, $\delta\in(0,1/10)$, and $G/\Gamma$ a two-step
nilmanifold of dimension $d$, complexity $M$, equipped with the lower central
series filtration. Furthermore, let $F(g(n)\Gamma)$ be a periodic nilsequence
modulo $N$ on $G/\Gamma$ with $F$ a $1$-Lipschitz vertical character of
nonzero frequency $|\xi|\leq M/\delta$. Suppose

$|\mathbb{E}_{n\in[N]}F(g(n)\Gamma)|\geq\delta.$

Then either $N\ll(\delta/M)^{-O(d)^{O(1)}}$ or there exists some integer
$d_{\mathrm{horiz}}\geq r\geq 0$ and elements
$w_{1},\dots,w_{r}\in\Gamma/(\Gamma\cap[G,G])$ and horizontal characters
$\eta_{1},\dots,\eta_{d_{\mathrm{horiz}}-r}$ all bounded by
$(\delta/M)^{-O(d)^{O(1)}}$ such that

  * •

$\psi_{\mathrm{horiz}}(w_{i})$’s are linearly independent of each other and
$\eta_{j}$’s are linearly independent of each other and
$\langle\eta_{j},w_{i}\rangle=0$ for all $i$ and $j$.

  * •

We have

$\|\xi([w_{i},g])\|_{C^{\infty}[N]}=0$ $\|\eta_{j}\circ
g\|_{C^{\infty}[N]}=0.$

It’s worth noting that the subgroup $\tilde{G}=\\{g\in
G:\eta_{j}(g)=0,[w_{i},g]=\mathrm{id}_{G}\forall i,j\\}$ is an abelian
subgroup of $G$ since given two elements $g,h\in\tilde{G}$, we see that since
$\eta_{j}(h)=0$ and $w_{i}$ and $\eta_{j}$ are orthogonal, it follows that the
horizontal component of $h$ can be spanned by the $w_{i}$’s, so to verify that
$[g,h]=0$, it just suffices to verify that $[w_{i},g]=\mathrm{id}_{G}$, which
is true by definition. In fact, by [13, Lemma A.9], each abelian rational
subgroup of $G$ is a subgroup of some group of this form. Combining this lemma
with factorization, we obtain the following.

######  Corollary 4.1.

twostepcor Let $N$ be a prime, $0<\delta<\frac{1}{10}$, $G/\Gamma$ be a two-
step nilmanifold of dimension $d$, complexity $M$, and equipped with the
standard filtration. Furthermore, let $F(g(n)\Gamma)$ be a periodic
nilsequence modulo $N$ on $G/\Gamma$ with $F$ a $1$-Lipschitz vertical
character of nonzero frequency $|\xi|\leq M/\delta$. Suppose $G/\Gamma$ has a
one-dimensional vertical torus, and

$|\mathbb{E}_{n\in[N]}F(g(n)\Gamma)|\geq\delta.$

Then either $N\ll(\delta/M)^{-O(d)^{O(1)}}$ or we can write
$g(n)=\epsilon(n)g_{1}(n)\gamma(n)$ where $\epsilon$ is constant, $g_{1}(n)$
lies on an abelian subgroup of $G$ with rationality
$(\delta/M)^{-O(d)^{O(1)}}$ and the image of $\gamma$ lies inside $\Gamma$.

###### Proof of twostepcase..

We first make a few preliminary reductions. By [13, Lemma 2.1], we may reduce
to the case that $g(0)=\mathrm{id}_{G}$ and $|\psi(g(1))|\leq\frac{1}{2}$.

Suppose

$|\mathbb{E}_{n\in[N]}F(g(n)\Gamma)|\geq\delta.$

Using the van der Corput inequality, we see that there are $\delta^{O(1)}N$
many $h$’s such that for each such $h$,

(4.1)
$|\mathbb{E}_{n\in[N]}F(g(n+h)\Gamma)\overline{F(g(n)\Gamma)}|\geq\delta^{O(1)}.$

We recall (once again) from [13, Definition 4.1, 4.2] the definitions

$G\times_{G_{2}}G=\\{(g^{\prime},g):g^{\prime}g^{-1}\in G_{2}\\}=G^{\square}$
$\Gamma\times_{\Gamma\cap
G_{2}}\Gamma=\\{(\gamma,\gamma^{\prime}):\gamma^{\prime}\gamma^{-1}\in
G_{2}\\}:=\Gamma^{\square}$

and $g_{2}(n)=g(n)g(1)^{-n}$. By defining
$F_{h}(x,y)=F(\\{g(1)^{h}\\}x)\overline{F(y)}$, the nonlinear part
$g_{2}(n)=g(n)g(1)^{-n}$, and
$g_{h}(n)=(\\{g(1)^{h}\\}^{-1}g_{2}(n+h)g(1)^{n}\\{g(1)^{h}\\},g_{2}(n)g(1)^{n})$,
we see that

$|\mathbb{E}_{n\in[N]}F_{h}(g_{h}(n)\Gamma)|\geq\delta^{O(1)}.$

One can verify that equipping $G^{\square}$ with the lower central series
filtration, $g_{h}\in\mathrm{poly}(\mathbb{Z},G^{\square})$, and that
$F_{h}(g_{h}(n)\Gamma^{\square})$ is a periodic nilsequence. Since $F_{h}$ is
invariant under $G_{2}^{\triangle}$, the diagonal subgroup of $G_{2}^{2}$, and
since $[G^{\square},G^{\square}]=G_{2}^{\triangle}$ it follows that $F_{h}$
descends to a function $\overline{F_{h}}$ on
$\overline{G^{\square}}:=G^{\square}/G_{2}^{\triangle}$, which is a one-step
nilpotent group. By [13, Lemma A.6] we may approximate $\overline{F_{h}}$ by

$\overline{F_{h}}=\sum_{|\eta|\leq
c(\delta)^{-1}}F_{h,\eta}+O_{L^{\infty}}(c(\delta))$

with $F_{h,\eta}$ $c(\delta)^{-1}$-Lipschitz vertical characters with
frequency $\eta$.

We now analyze characters on $\overline{G^{\square}}$. Such a character lifts
to a horizontal character on $G^{\square}$ which annihilates
$G_{2}^{\triangle}$. By [13, Lemma A.3] that we may decompose
$\eta(g_{2}g_{1},g_{1})=\eta(g_{1},g_{1})+\eta(g_{2},id)=\eta^{1}(g_{1})+\eta^{2}(g_{2})$
with $g_{1}\in G$ and $g_{2}\in G_{2}$ where $\eta^{1}$ and $\eta^{2}$ are
horizontal characters of size at most $c(\delta)^{-1}$. In order to emphasize
that $\eta^{2}$ “lies in the $x_{2}-x_{1}$ direction”, we shall write
$\eta^{2}$ as $\eta^{2}\otimes\overline{\eta^{2}}$. Since $F$ is a frequency
$\xi$ on $G_{2}$, we expect $F_{h,\eta}$ to also be of frequency
$\xi\otimes\overline{\xi}$ on $G_{2}^{2}/G_{2}^{\triangle}$. This may not
necessarily be true as written above, but we may average over
$G_{2}^{2}/G_{2}^{\triangle}$ as follows:

$\overline{F_{h}}(x)=\int_{G_{2}^{2}/G_{2}^{\triangle}}\tilde{F}_{h}(g_{2}x\Gamma)e(-\xi\otimes\overline{\xi}(g_{2}))dg_{2}=\sum_{|\eta^{\prime}|\leq
c(\delta)^{-1}}F_{h,\eta^{\prime}}+O_{L^{\infty}}(c(\delta)).$

The point is that $(\eta^{\prime}-\xi\otimes\overline{\xi})(G_{2}^{2})=0$.
Here, note that we have abusively lifted $\eta^{\prime}$ to a horizontal
character on $G\times_{G_{2}}G_{2}/G_{2}^{\triangle}$ and
$\xi\otimes\overline{\xi}$ to a character on $G_{2}^{2}$ that annihilates
$G_{2}^{\triangle}$. By applying the Pigeonhole principle, there exists one
frequency $\eta^{\prime}$ independent of $h$ such that for $c(\delta)N$ many
$h\in\mathbb{Z}/N\mathbb{Z}$,

(4.2)
$|\mathbb{E}_{n\in\mathbb{Z}/N\mathbb{Z}}F_{\eta^{\prime}}(g(n)\Gamma)|\geq
c(\delta).$

Since $G$ was two-step, $G\times_{G_{2}}G$ is one-step, so decomposing
$\eta^{\prime}(g^{\prime},g)=\eta_{1}(g)+\xi(g^{\prime}g^{-1})$, (4.2) is
equivalent to the fact that

(4.3)
$|\mathbb{E}_{n\in[N]}e(n\eta_{1}(g(1))+\xi(g_{2}(n+h)g_{2}(n)^{-1})+\xi([\\{g(1)^{h}\\},g(1)^{n}]))|\geq(\delta/M)^{O(d)^{O(1)}}$

for $c(\delta)N$ many elements $h\in[N]$.

We claim that $\xi([g(1),[g(1)^{h}])$ is rational with denominator $N$. To see
this, note that

$\xi([g(1),\\{g(1)^{h}\\}])=\xi([g(1),[g(1)^{h}]]),$

and since $\xi([g(1),[g(1)^{h}]])^{N}=\xi([g(1)^{N},[g(1)^{h}]])=0$, it
follows that $\xi([g(1),[g(1)^{h}])$ is rational with denominator $N$. From
(4.3) and periodic, we have for some $\beta,\gamma\in\mathbb{R}$ with $\beta$
rational with denominator $AN$ for some $A=O_{k}(1)$,

$\|\beta n+\gamma+\xi([g(1),\\{g(1)^{h}\\}])\|_{\mathbb{R}/\mathbb{Z}}=0.$

We can write

$\xi([g(1),\\{g(1)^{h}\\}])=\langle(C-C^{t})g(1),\\{g(1)^{h}\\}\rangle=\langle
a,\\{\alpha h\\}\rangle$

where $C-C^{t}$ is the antisymmetric matrix representing the commutator
identity in the horizontal torus. Note that $C-C^{t}$ has height at most $M$.
This suggests that we should’ve made a change of variables $n\mapsto M_{1}n$
in (4.1) (using the fact that $M_{1}$ has a modular inverse mod $N$ since $N$
is prime) for some $M_{1}\leq AM^{d}$ which is a multiple of the denominator
of each entry of $C-C^{t}$ and $A$,

$|\mathbb{E}_{n\in[N]}F(g(M_{1}n)\Gamma)|\geq\delta.$

Thus, after applying the change of variables, we can assume that $a$,
$\alpha$, and $\beta$ have denominator $N$. Applying
bracketpolynomialcorollary and noticing that $C-C^{t}$ is antisymmetric, we
obtain $w_{i}$’s and $\eta_{j}$’s which are linearly independent,
$\eta_{j}(w_{i})=0$, $\|M_{1}\xi([w_{i},g])\|_{\mathbb{R}/\mathbb{Z}}=0$, and
$\|\eta_{j}(g)\|_{\mathbb{R}/\mathbb{Z}}=0$. Using the fact that $N$ is prime,
we obtain $\|\xi([w_{i},g])\|_{\mathbb{R}/\mathbb{Z}}=0$. This completes the
proof of twostepcase. ∎

##  5\. The two-step polynomial sequence case

In the previous section, we observed that in the two-step case, applying van
der Corput once landed us in the group $\overline{G^{\square}}$, which was
one-step. In general, this may not be true, even in the two-step polynomial
sequence case. This is exhibited by the following example in bracket
polynomial formalism. Consider

$\alpha n^{2}[\beta n].$

Differentiating once in $h$ gives a top term of

$2\alpha nh[\beta n]+\alpha n^{2}[\beta h].$

Here, we see that the term $2\alpha nh[\beta n]$ is still a “bracket term” in
$n$. Hence, our proof divides into two cases.

  * •

The first case is what happens when $\overline{G^{\square}}$ is one-step. This
would correspond to centralcase and in bracket polynomial formalism, what
happens when the bracket polynomial is of the form

$\sum_{i=1}^{d}\alpha_{i}n[\beta_{i}n]+P(n)$

for $P$ a (not necessarily degree two) polynomial.

  * •

The second case is what happens when $\overline{G^{\square}}$ is not one-step.
We have not isolated a specific lemma for that case, for its proof occupies
much of twosteppolynomial. In bracket polynomial formalism, this corresponds
to a bracket polynomial of the form

$\sum_{i=1}^{d}P_{i}(n)[Q_{i}(n)]+R(n)$

where $P_{i},Q_{i}$ are polynomials with at least one with degree larger than
one and $R$ is a polynomial.

We now state the main theorem of this section.

######  Theorem 7.

twosteppolynomial Let $\delta\in(0,1/10)$, $N>100$ prime, and $G/\Gamma$ a
two-step nilmanifold of dimension $d$, complexity $M$, and degree $k$.
Furthermore, let $F(g(n)\Gamma)$ be a periodic nilsequence modulo $N$ on
$G/\Gamma$ with $F$ a $1$-Lipschitz vertical character with nonzero frequency
$|\xi|\leq M/\delta$. Suppose

$|\mathbb{E}_{n\in[N]}F(g(n)\Gamma)|\geq\delta.$

Then either $N\ll(\delta/M)^{-O_{k}(d)^{O_{k}(1)}}$ or else there exists some
integer $d_{\mathrm{horiz}}\geq r\geq 1$ elements $w_{1},\dots,w_{r}\in\Gamma$
with $\psi_{horiz}(w_{1}),\dots,\psi_{horiz}(w_{r})$ linearly independent,
linearly independent horizontal characters $\eta_{1},\dots,\eta_{d_{horiz}-r}$
with $|w_{i}|,|\eta_{j}|\leq(\delta/M)^{-O_{k}(d)^{O_{k}(1)}}$,
$\langle\eta_{j},w_{i}\rangle=0$, and

$\|\xi([w_{i},g])\|_{C^{\infty}[N]},\|\eta_{j}\circ g\|_{C^{\infty}[N]}=0.$

It turns out that the proof of the two-step polynomial sequence case breaks
down naturally into two cases: one where $\xi([G_{2},G])=0$ and one where
$\xi([G_{2},G])=\mathbb{R}$. This is analogous to the two cases considered in
[13, Section 4]. We start with the case of when $\xi([G_{2},G])=0$ first.

######  Lemma 5.1.

centralcase Let $\delta\in(0,1/10)$, $N>100$ prime, and $G/\Gamma$ be a two-
step nilmanifold of dimension $d$, complxity $M$, and degree $k$ with
$\xi([G_{2},G])=0$. Furthermore, let $F(g(n)\Gamma)$ be a periodic nilsequence
modulo $N$ on $G/\Gamma$ with $F$ a $1$-Lipschitz vertical character with
nonzero frequency $|\xi|\leq M/\delta$. Suppose

$|\mathbb{E}_{n\in[N]}F(g(n)\Gamma)|\geq\delta.$

Then either $N\ll(M/\delta)^{O_{k}(d^{O_{k}(1)})}$ or else there exists some
integer $d_{\mathrm{horiz}}\geq r\geq 1$, elements
$w_{1},\dots,w_{r}\in\Gamma$ with
$\psi_{\mathrm{horiz}}(w_{1}),\dots,\psi_{\mathrm{horiz}}(w_{r})$ linearly
independent, and linearly independent horizontal characters
$\eta_{1},\dots,\eta_{d_{horiz}-r}$ with
$|w_{i}|,|\eta_{j}|\leq(M/\delta)^{O_{k}(d^{O_{k}(1)})}$,
$\langle\eta_{j},w_{i}\rangle=0$, and

$\|\xi([w_{i},g])\|_{C^{\infty}[N]},\|\eta_{j}\circ g\|_{C^{\infty}[N]}=0.$

###### Proof.

By [13, Lemma 2.2], we may reduce to the case of when $g(0)=1$ and
$|\psi(g(1))|\leq 1/2$. We proceed similarly as the proof of twostepcase with
one key difference. Instead of Fourier expanding along the vertical torus, we
Fourier expand along the $G_{2}$-torus. By [13, Lemma A.6], we may decompose

$F=\sum_{|\alpha|\leq c(\delta)^{-1}}F_{\alpha}+O(c(\delta))$

where $\alpha$ is a $G_{2}$-vertical frequency. By averaging over $G_{(2)}$,
we may write

$F(x)=\int F(g_{2}x)e(-\xi(g_{2}))dg_{2}=\sum_{|\beta|\leq
c(\delta)^{-1}}F_{\beta}+O(c(\delta))$

where crucially, $(\beta-\xi)(G_{(2)})=0$.

Once again, we apply the van der Corput inequality

$|\mathbb{E}_{n\in[N]}F(g(n)\Gamma)\overline{F(g(n+h)\Gamma)}|\geq\delta^{2}$

for $\delta^{2}N$ many $h\in[N]$. Then letting $g_{2}(n):=g(n)g(1)^{-n}$ be
the nonlinear part of $g$, we denote

$g_{h}(n)=(\\{g(1)^{h}\\}^{-1}g_{2}(n+h)g(1)^{n}\\{g(1)^{h}\\},g(n))$

and $F_{h}(x,y)=\overline{F}(\\{g(1)^{h}\\}x)F(y)$. By [13, Lemma A.3], we see
that $g_{h}$ lies inside $G^{\square}$ and $F_{h}(g_{h}(n))$ descends to
$\tilde{F}_{h}(\tilde{g}_{h}(n)\overline{\Gamma^{\square}})$ a nilsequence on
$\overline{G^{\square}}$. Since $g(n)\Gamma$ is periodic modulo $N$, it
follows that $g_{h}(n)\Gamma\times\Gamma$ is periodic modulo $N$ and thus
$g_{h}(n)\Gamma\times_{G_{2}\cap\Gamma}\Gamma$ is also periodic modulo $N$,
and so $\tilde{g}_{h}(n)\overline{\Gamma^{\square}}$ is periodic modulo $N$.
The hypothesis then rearranges to

$|\mathbb{E}_{n\in[N]}\tilde{F_{h}}(\tilde{g_{h}}(n)\overline{\Gamma^{\square}})|\geq\delta^{2}$

for $\delta^{2}N$ many $h\in[N]$. Making a change of variables for some
integer $1\leq M_{1}\leq(10^{k}k)!M^{d}$

$|\mathbb{E}_{n\in[N]}\tilde{F_{h}}(\tilde{g_{h}}(M_{1}n)\overline{\Gamma^{\square}})|\geq\delta^{2}$

By [13, Lemma A.3], it follows that $F_{h}$ has Lipschitz norm at most
$M^{O(1)}$ on $G^{\square}$, $G^{\square}$ is abelian; we now repeat a similar
procedure as in the proof of twostepcase,approximating $\tilde{F}_{h}$ by
$F_{\eta,h}$ where $(\eta-\xi\otimes\overline{\xi})(G_{(2)})=0$, Pigeonholing
in $\eta$ so it is $h$-independent.

Again, we decompose via [13, Lemma A.3]
$\eta(g_{2}g_{1},g_{1})=\eta^{1}(g_{1})+\eta^{2}(g_{2})$ with $g_{1}\in G$ and
$g_{2}\in G_{2}$. It thus follows that

$|\mathbb{E}_{n\in\mathbb{Z}/N\mathbb{Z}}e(\eta^{1}(g(M_{1}n))+\eta^{2}(g_{2}(M_{1}n+h))-\eta^{2}(g_{2}(M_{1}n))+\xi([g(1)^{M_{1}n},\\{g(1)^{h}\\}]))|\geq
c(\delta)$

for $c(\delta)N$ many $h\in\mathbb{Z}/N\mathbb{Z}$. Thus, by classical results
in Diophantine approximation (e.g., [13, Lemma A.11]),

$\|\eta^{1}(g(M_{1}n))+\eta^{2}(g_{2}(M_{1}n+h))-\eta^{2}(g_{2}(M_{1}n))+\xi([g(1)^{M_{1}n},\\{g(1)^{h}\\}])\|_{C^{\infty}[N]}=0.$

Expanding $\eta^{2}(g_{2}(M_{1}n+h))$ out, applying the hypothesis, and
applying Vinogradov’s lemma to eliminate the coefficients of $nh^{i}$ for
$i>1$ (see also [13, Lemma 4.2]), we see that there exists $\beta$ and
$\gamma$ such that

$\|\beta
h+\xi([g(1)^{M_{1}n},\\{g(1)^{h}\\}])+\gamma\|_{\mathbb{R}/\mathbb{Z}}=0$

The point of making the change of variables is so that by periodic, the
coefficients of $g_{2}(M_{1}\cdot)$ have denominator $N$, and
$\xi([g(1)^{M_{1}n},\\{g(1)^{h}\\}])$ consists of $\langle an,\\{\alpha
h\\}\rangle$ where $a$ and $\alpha$ have denominator $N$. Applying
bracketpolynomialcorollary and using the fact that $N$ is prime yields
$w_{i}$’s and $\eta_{j}$’s which satisfy the conclusions of the lemma. ∎

We now address the case of when $\xi([G_{2},G])=\mathbb{R}$. The key fact to
keep in mind in the below proof is that if $G_{(2)}$ is one-dimensional, then
$[G_{2},G]=[G,G]$.

###### Proof of twosteppolynomial.

By [13, Lemma 2.3], we may assume that $G_{(2)}$ is one-dimensional. If
$G_{2}$ lies in the center of $G$, we may apply centralcase to finish.

At this point, the proof of [7] Fourier expands $F$ into $G_{k}$-vertical
characters and reduces to a nilsequence on $\overline{G^{\square}}$ of degree
$k-1$. In our proof, we wish to preserve information of $F$ being a
$G_{(2)}$-vertical character in some way. This can be done by modifying the
filtration. For $k\geq\ell>2$, we replace $G_{\ell}$ with $G_{\ell}G_{(2)}$.
Then since $G_{(2)}$ is in the center of $G$, this gives a filtered
nilmanifold; by [13, Lemma B.12], there exists a Mal’cev basis which makes
this filtered nilmanifold of complexity at most $c(\delta)^{-1}$.

As in previous arguments, at the cost of replace $\delta$ with $c(\delta)$ and
increasing the Lipschitz constant of $F$ to $c(\delta)^{-1}$, we may replace
$F$ with a $G_{k}$-vertical character of frequency $\eta$ with
$(\eta-\xi)(G_{(2)})=0$.

By the van der Corput inequality, we have for $c(\delta)N$ many $h$’s

$|\mathbb{E}_{n\in[N]}F(g(n+h)\Gamma)\overline{F(g(n)\Gamma)}|\geq c(\delta).$

Defining

$g_{h}(n)=(\\{g(1)^{h}\\}^{-1}g_{2}(n+h)g(1)^{n}\\{g(1)^{h}\\},g_{2}(n)g(1)^{n})$

and $F_{h}(x,y)=F(\\{g(1)^{h}\\}x)\overline{F(y)}$, it follows that

$|\mathbb{E}_{n\in[N]}F_{h}(g_{h}(n))|\geq\delta^{O(1)}.$

As before, by [13, Lemma A.3, Lemma A.4], $g_{h}$ is a periodic polynomial
sequence on $G^{\square}$. By [13, Lemma A.3], this group has the filtration
$(G\times_{G_{2}}G)_{i}=G_{i}\times_{G_{i+1}}G_{i}$ with
$(G\times_{G_{2}}G)_{k}=G_{k}^{\triangle}$. However, $F_{h}$ is
$G_{k}^{\triangle}$-invariant, so descends via a quotient by
$G_{k}^{\triangle}$ to a degree $d-1$ nilsequence
$\tilde{F}_{h}(\overline{g_{h}}(n)\overline{\Gamma^{\square}})$. The
observation to make is that $\tilde{F}_{h}$ is a nilcharacter of frequency
$\xi\otimes\overline{\xi}$ on $\overline{G^{\square}}$. This is because
$[G_{2},G]=[G,G]$ so $(\overline{G^{\square}})_{(2)}=G_{(2)}\times
G_{(2)}/G_{k}^{\triangle}$. Applying the induction hypothesis, we have for
linearly independent horizontal characters $\eta_{1},\dots,\eta_{d^{\prime}}$
and elements
$w_{1},\dots,w_{d_{horiz,\overline{G^{\square}}}-d^{\prime}}\in\overline{\Gamma^{\square}}$
such that
$\psi_{horiz,\overline{G^{\square}}}(w_{1}),\dots,\psi_{horiz,\overline{G^{\square}}}(w_{d_{horiz,\overline{G^{\square}}}-d^{\prime}})$
are linearly independent and for each $i,j$, and $c(\delta)N$ many $h\in[N]$
that

$\|\xi\otimes\overline{\xi}([w_{i},\tilde{g_{h}}(n)])\|_{C^{\infty}[N]}=0$
$\|\eta_{j}\circ\tilde{g_{h}}(n)\|_{C^{\infty}[N]}=0.$

where $\tilde{g_{h}}$ is the projection of $g_{h}$ to $G^{\square}$. Abusively
lifting $\eta_{j}$ to be horizontal characters on $G^{\square}$ and lifting
$w_{j}$ to be elements in $\Gamma^{\square}$ and appending elements
$z_{1},\dots,z_{\ell}$ in $G_{k}^{\triangle}\cap\Gamma^{\square}$ to the set
of $w_{i}$’s such that
$\overline{\exp(z_{1})},\dots,\overline{\exp(z_{\ell})}$ span
$G_{k}^{\triangle}/[G^{\square},G^{\square}]$, we see that

  * •

since $G_{k}^{\triangle}/[G^{\square},G^{\square}]$ can be naturally
identified with its Lie algebra which can be identified via the Mal’cev
coordinates as the orthogonal complement within $G_{k}^{\triangle}$ of
$[G^{\square},G^{\square}]$, that we can take $z_{1},\dots,z_{\ell}$ to be
size at most $c(\delta)^{-1}$, and thus
$w_{1},\dots,w_{d_{horiz,G^{\square}}-d^{\prime}}$ also has size at most
$c(\delta)^{-1}$;

  * •

Since $\eta_{1},\dots,\eta_{d^{\prime}}$ annihilates $G_{k}^{\square}$, they
span the annihilators of $w_{1},\dots,w_{d_{horiz,G^{\square}}-d^{\prime}}$.

Hence, we have for each $i,j$

$\|\xi\otimes\overline{\xi}([w_{i},g_{h}(n)])\|_{C^{\infty}[N]}=0$
$\|\eta_{j}\circ g_{h}(n)\|_{C^{\infty}[N]}=0.$

By [13, Lemma A.3], we may write $w_{i}=(u_{i}v_{i},u_{i})$ and decompose
$\eta_{j}(g^{\prime},g)=\eta_{j}^{1}(g)+\eta_{j}^{2}(g^{\prime}g^{-1})$ so

$\displaystyle\eta_{j}(g_{h}(n))$
$\displaystyle=\eta_{j}^{1}(g(n))+\eta_{j}^{2}(g_{2}(n+h)g_{2}(n)^{-1})$
$\displaystyle\eta_{j}(w_{i})$
$\displaystyle=\eta_{j}^{1}(u_{i})+\eta_{j}^{2}(v_{i})=0$
$\displaystyle\xi\otimes\overline{\xi}([w_{i},g_{h}(n)])$
$\displaystyle=\xi\otimes\xi^{-1}(([u_{i},g(n)],[u_{i}v_{i},g(n)][u_{i}v_{i},g_{2}(n+h)g_{2}(n)^{-1}])$
$\displaystyle=\xi([v_{i},g(n)]+[u_{i}v_{i},g_{2}(n+h)g_{2}(n)^{-1}])$

Not here we are crucially using that $[G_{2},G]=[G,G]$, so $\beta_{j}$
annihilates $[G,G]$. By expanding out the polynomial
$[u_{i}v_{i},g_{2}(n+h)g_{2}(n)^{-1}]$, and grouping coefficients, and
applying a polynomial Vinogradov-type lemma (e.g., [13, Lemma A.11]; see also
[13, Lemma 4.2]), it follows that

$\|\eta_{j}^{1}\circ
g\|_{C^{\infty}[N]},\|\xi([v_{i},g])\|_{C^{\infty}[N]},\|\eta_{j}^{2}\circ
g_{2}\|_{C^{\infty}[N]},\|\xi([u_{i}v_{i},g_{2}])\|_{C^{\infty}[N]}=0.$

Note that here we must use the fact that $N$ is prime and the fact that
$g_{2}$ has horizontal component with denominator $N$ to eliminate the
binomial coefficients that come from expanding out $g_{2}(n+h)g_{2}(n)^{-1}$.
Let $\tilde{G}=\\{g\in G:\eta_{j}^{1}\circ g=0,[v_{i},g]=0\\}$ and
$\tilde{G}_{2}=\\{g\in\tilde{G}\cap
G_{2},\eta_{j}^{2}(g)=0,[u_{i}v_{i},g]=0\\}$. We note that
$[G,G]\subseteq\tilde{G}$ and $G_{2}$ and also that $\eta_{j}^{2}([G,G])=0$.
Hence, (abusing notation) the sequence of subgroups
$\tilde{G}_{i}=\tilde{G}_{2}\cap G_{i}$ for $i>2$ and
$\tilde{G}_{0}=\tilde{G}_{1}=\tilde{G}$ form a filtration.

We claim that $[\tilde{G},\tilde{G}_{2}]=0$. To show this, we let
$\tilde{H}=\tilde{G}^{\square}$ and we claim that $\tilde{H}$ is Abelian. To
see this, note that each element of $\tilde{H}$ of the form $(gg_{2},g)$
satisfies $\eta_{j}^{1}(g)+\eta_{j}^{2}(g_{2})=0$ and
$[v_{i},g]+[u_{i}v_{i},g_{2}]=0$. Since
$\eta_{j}^{1}(u_{i})+\eta_{j}^{2}(v_{i})=0$ for each $i,j$, it follows that
$(gg_{2},g)$ can be generated by $(u_{i}v_{i},u_{i})$ modulo $[G,G]^{2}$.
However, for any other $(hh_{2},h)$ in $\tilde{H}$, we have
$\xi\otimes\overline{\xi}[(u_{i}v_{i},u_{i}),(hh_{2},h)]=0$. Hence $\tilde{H}$
is Abelian. Finally, we have
$\xi\otimes\overline{\xi}([(g,g),(hg_{2},h)])=\xi([g,g_{2}])=0$ whenever
$g\in\tilde{G}$ and $g_{2}\in\tilde{G}_{2}$. This shows that
$\xi([\tilde{G},\tilde{G}_{2}])=0$ and since $[G,G]$ is one-dimensional,
$[\tilde{G},\tilde{G}_{2}]=0$. Thus, by factorization and removerational, we
may write $g(n)=g^{\prime}(n)\gamma^{\prime}(n)$ where $\gamma^{\prime}(n)$
has image in $\Gamma$ and $g^{\prime}(n)$ has image in $G^{\prime}$. We see
that

$g^{\prime}(1)^{n}\equiv g(1)^{n}\gamma^{\prime}(1)^{n}\pmod{[G,G]}$

and by abusing notation,

$g^{\prime}_{2}(n)\equiv g_{2}(n)\gamma^{\prime}_{2}(n)\pmod{[G,G]}.$

Since $\eta_{j}$ and $\xi([u_{i}v_{i},\cdot])$ both annihilate $[G,G]$, we see
that

$\|\eta_{j}\circ
g^{\prime}_{2}\|_{C^{\infty}[N]},\|\xi([u_{i}v_{i},g^{\prime}_{2}])\|_{C^{\infty}[N]}=0.$

Thus, by factorization2, and removerational, we can write
$g(n)\Gamma=g_{1}(n)\Gamma$ with $g_{1}\in\text{poly}(\mathbb{Z},\tilde{G})$.
Finally, we apply centralcase and [13, Lemma A.9] to $g_{1}(n)$ to find
linearly independent $\alpha_{1},\dots,\alpha_{d^{\prime}}$ of size at most
$c(\delta)^{-1}$ with the property that

$\|\alpha_{i}\circ g\|_{C^{\infty}[N]}=\|\alpha_{i}\circ
g_{1}\|_{C^{\infty}[N]}=0$

and such that if $w,w^{\prime}$ are elements in $\Gamma/([G,G]\cap\Gamma)$
that are orthogonal to each of the $\alpha_{i}$’s, then
$\xi([w,w^{\prime}])=0$. To satisfy the second conclusion, we invoke
factorization and removerational to find a factorization
$g_{1}(n)=g_{1}^{\prime}(n)\gamma(n)$ where $g_{1}^{\prime}$ lies in the
kernel of $\alpha_{i}$ for all $i$ and $\gamma$ lies in $\Gamma$. It follows
that $g_{1}^{\prime}$ lies in the subspace generated by orthogonal elements to
$\alpha_{i}$’s. Thus, for any $w\in\Gamma/(\Gamma\cap[G,G])$ orthogonal to all
of the $\alpha_{i}$’s, it follows that

$\|\xi([w,g_{1}^{\prime}(n)\Gamma])\|_{C^{\infty}[N]}=\|\xi([w,g_{1}(n)])\|_{C^{\infty}[N]}=\|\xi([w,g(n)])\|_{C^{\infty}[N]}=0.$

By [13, Lemma A.8], we may choose elements
$w_{1},\dots,w_{d_{horiz}-d^{\prime}}$ inside $\Gamma$ whose size is at most
$c(\delta)^{-1}$ and such that their projections to $\Gamma/([G,G]\cap\Gamma)$
are linearly independent and are orthogonal to the $\alpha_{i}$. To verify
size bounds, we must verify that the projection of the Mal’cev coordinates of
$w_{i}$ to the orthogonal complexity of $[\mathfrak{g},\mathfrak{g}]$ is
bounded by $c(\delta)^{-1}$. This follows from invoking [13, Lemma A.7] to
construct a $c(\delta)^{-1}$-rational basis for the orthogonal to
$[\mathfrak{g},\mathfrak{g}]$ and constructing $c(\delta)^{-1}$-rational basis
for $[\mathfrak{g},\mathfrak{g}]$ and rewriting the Mal’cev coordinates of
$w_{i}$ in terms of linear combinations of these bases and projecting to the
dimensions where $[\mathfrak{g},\mathfrak{g}]=0$. By Cramer’s rule we can
ensure that if we write $w_{i}$ terms of these linear combinations, all
components are rational with height at most $c(\delta)^{-1}$. ∎

##  6\. The general periodic case

Recall the following theorem. See 2

###### Proof.

As the direct proof of this theorem is no shorter than the proof in [13], we
shall only give a proof of this assuming [13, Theorem 3]. We see from
hypothesis that

$|\mathbb{E}_{n\in[MN]}F(g(n)\Gamma)|\geq\delta$

for each $M$. Invoking [13, Theorem 3], we find $\eta_{1},\dots,\eta_{r}$ such
that

$\|\eta_{i}\circ g\|_{C^{\infty}[MN]}\leq c(\delta)^{-1}$

and such that $s$ elements $w_{1},\dots,w_{s}\in
G^{\prime}:=\bigcap_{i=1}^{r}\text{ker}(\eta_{i})$ satisfies

$\xi([w_{1},\dots,w_{s}])=0.$

Sending $M$ to infinity, we see that

$\|\eta_{i}\circ g\|_{C^{\infty}[MN]}=0$

as desired. ∎

##  7\. The complexity one polynomial Szemerédi theorem

We now deduce mainresult2. Fix $P(x)$ and $Q(x)$ to be linearly independent
polynomials. For functions $f,g,h,k\colon\mathbb{Z}/N\mathbb{Z}\to\mathbb{C}$,
define

$\Lambda(f,g,k,p):=\mathbb{E}_{x,y}f(x)g(x+P(y))k(x+Q(y))p(x+P(y)+Q(y)).$

and

$\Lambda^{1}(f,g,j,p):=\mathbb{E}_{x,y,z}f(x)g(x+y)k(x+z)p(x+y+z).$

We will show the following:

######  Theorem 8.

asymptotic There exists some $c_{P,Q}$ such that for any one-bounded
$f,g,k,p$, we have

$\Lambda(f,g,k,p)=\Lambda^{1}(f,g,k,p)+O\left(\frac{1}{\exp(\log^{c_{P,Q}}(N))}\right).$

To see how this implies mainresult2, suppose the set $A$ has no nontrivial
configuration of the form $(x,x+P(y),x+Q(y),x+P(y)+Q(y))$. Then

$|\Lambda(1_{A},1_{A},1_{A},1_{A})|\leq\frac{1}{N}.$

We have
$|\Lambda^{1}(1_{A},1_{A},1_{A},1_{A})|=\|1_{A}\|_{U^{2}(\mathbb{Z}/N\mathbb{Z})}^{4}\geq\|1_{A}\|_{U^{1}(\mathbb{Z}/N\mathbb{Z})}^{4}=\alpha^{4}$
where $\alpha$ is the density of $A$ in $\mathbb{Z}/N\mathbb{Z}$. asymptotic
then implies that

$\alpha\ll O\left(\frac{1}{\exp(\log^{c_{P,Q}}(N))}\right)$

as desired.

The proof of asymptotic will closely follow the proof of [12, Theorem 3]. To
prove this theorem, we prove the following inverse-type theorem:

######  Theorem 9.

polynomialinverse Suppose $|\Lambda(f,g,k,p)|\geq\delta$. Then either
$N\ll\exp(\log^{O_{P,Q}(1)}(1/\delta))$ or
$\|p\|_{U^{2}}\gg\exp(-\log^{O_{P,Q}}(1/\delta))$.

Let us assume for a moment that we can prove polynomialinverse. We shall
deduce asymptotic. For arbitrary one-bounded $p$, we invoke [12, Lemma 4.2] to
decompose $p=p_{a}+p_{b}+p_{c}$ with

$\|\hat{p_{a}}\|_{\ell^{1}}\leq\epsilon_{1}^{-1},\|p_{b}\|_{L^{1}}\leq\epsilon_{2},\|p_{c}\|_{L^{\infty}}\leq\epsilon_{3}^{-1},\|\hat{p_{c}}\|_{L^{\infty}}\leq\epsilon_{4}$

where $\epsilon_{1},\dots,\epsilon_{4}$ will be chosen later and satisfy
$\epsilon_{1}\epsilon_{4}^{-1}+\epsilon_{2}^{-1}\epsilon_{3}\leq\frac{1}{2}$.
We thus have

$\Lambda(f,g,k,p)=\Lambda(f,g,k,p_{a})+\Lambda(f,g,k,p_{b})+\Lambda(f,g,k,p_{c}),$
$\Lambda(f,g,k,p_{a})=\Lambda^{1}(f,g,k,p_{a})+O(N^{-\delta}\epsilon_{1}^{-1}),$

and

$|\Lambda(f,g,k,p_{b})|\leq\epsilon_{2}.$

To control $|\Lambda(f,g,k,p_{c})$, we invoke polynomialinverse which states
that either

$|\Lambda(f,g,k,p_{c})|\ll\epsilon_{3}^{-1}\exp(-\log^{c_{P,Q}}(N))$

or

$\displaystyle|\Lambda(f,g,k,p_{c})|$
$\displaystyle\leq\epsilon_{3}^{-1}|\lambda(f,g,k,\epsilon_{3}p_{c})|$
$\displaystyle\leq\epsilon_{3}^{-1}\exp(-\log^{C_{P,Q}}(\|\epsilon_{3}\hat{p_{c}}\|_{L^{\infty}}^{-1/2}))$
$\displaystyle=\epsilon_{3}^{-1}\exp(-\log^{C_{P,Q}}(\epsilon_{3}^{-1/2}\epsilon_{4}^{-1/2})).$

Choosing $\epsilon_{1}=N^{\alpha}$,
$\epsilon_{3}=\exp(-\log^{c^{\prime}_{P,Q}}(N))$,
$\epsilon_{4}=N^{-\alpha^{\prime}}$ for $\alpha^{\prime}>\alpha$, we see that

$\exp(-\log^{C_{P,Q}}(\epsilon_{3}^{-1/2}\epsilon_{4}^{-1}))\ll_{\epsilon}\exp(-(\alpha^{\prime}/2-\epsilon)^{C_{P,Q}}\log^{C_{P,Q}}(N)).$

Thus, choosing $\epsilon_{3}$ to be larger than both
$\exp(-\log^{c_{P,Q}}(N))$ and
$\exp(-(\alpha^{\prime}-\epsilon)^{C_{P,Q}}\log^{C_{P,Q}}(N))$, and
$\epsilon_{2}$ to be less than $\epsilon_{3}$ but also of the form
$\exp(-\log^{1/O_{P,Q}(1)}(N))$, we have the desired estimate of

$\Lambda(f,g,k,p)=\Lambda^{1}(f,g,k,p_{a})+O(\exp(-\log^{c_{P,Q}}(N))).$

The decomposition we chose also allows us to prove the same estimates of
$\Lambda^{1}$, with $\Lambda$ replaced with $\Lambda^{1}$, and one of the
estimates being

$|\Lambda^{1}(f,g,k,p_{c})|\leq\epsilon_{3}^{-1/2}\|\hat{p_{c}}\|_{L^{\infty}}^{1/2}\leq\epsilon_{3}^{-1/2}\epsilon_{4}^{1/2}\ll_{\epsilon}N^{-\alpha^{\prime}/2+\epsilon}.$

Thus, we can also show that

$\Lambda^{1}(f,g,k,p)=\Lambda^{1}(f,g,k,p_{a})+O(\exp(-\log^{c_{P,Q}}(N)))$

which gives

$\Lambda(f,g,k,p)=\Lambda^{1}(f,g,k,p)+O(\exp(-\log^{c_{P,Q}}(N)))$

as desired. It thus remains to prove polynomialinverse.

###  7.1. Proof of polynomialinverse

We will show the following:

######  Proposition 7.1.

degreelowering Given functions $f,g,k:\mathbb{Z}/N\mathbb{Z}\to\mathbb{C}$, we
define

$\mathcal{D}(f,g,k)(x)=\mathbb{E}_{y}f(x-P(y)-Q(y))g(x-Q(y))k(x-P(y)).$

Let $s\geq 2$. If $f,g,k:\mathbb{Z}/N\mathbb{Z}\to\mathbb{C}$ are one-bounded
and

$\|\mathcal{D}(f,g,k)\|_{U^{s+1}(\mathbb{Z}/N\mathbb{Z})}\geq\delta,$

then either $\delta\ll\exp(-\log^{1/O_{P,Q}(1)}(N))$ or
$\|f\|_{U^{s}(\mathbb{Z}/N\mathbb{Z})}\gg\exp(-\log^{O_{P,Q}}(1/\delta))$.

First, assuming this is true, by [12, Lemma 5.1, Lemma 5.2], for some
$s=s_{P,Q}$, we have

$|\Lambda(f,g,k,p)|\leq\|p\|_{U^{s}(\mathbb{Z}/N\mathbb{Z})}+O(N^{-1/O_{P,Q}(1)}).$

Thus,

$|\Lambda(f,g,k,p)|\leq\left(\mathbb{E}_{x}|\mathcal{D}(f,g,k)|^{2}\right)^{1/2}=|\Lambda(\overline{f},\overline{g},\overline{k},\mathcal{D}(f,g,k))|^{1/2}\leq\|\mathcal{D}(f,g,k)\|_{U^{s}(\mathbb{Z}/N\mathbb{Z})}^{O(1)}+O(N^{-\zeta})$

for some $\zeta$ that depends only on $P$ and $Q$. Thus, if we can show
degreelowering, this will in turn imply by an iterative argument
polynomialinverse. For the remainder of the argument, we will now indicate how
to make improvements in [12]. The first improvement we apply is the Sanders
$U^{3}$ inverse theorem (see [14, Appendix A] for how to deduce the improved
$U^{3}$ inverse theorem from [21]), where we end up with

(7.1)
$\mathbb{E}_{h_{1},\dots,h_{s-2}}|\langle\mathcal{D}_{h}(f,g,k),F_{\vec{h}}(m_{h}(x)\Gamma)\rangle|\gg\exp(-\log^{O(1)}(1/\delta))$

instead of the inferior

$\mathbb{E}_{h_{1},\dots,h_{s-2}}|\langle\mathcal{D}_{h}(f,g,k),F_{\vec{h}}(m_{h}(x)\Gamma)\rangle|^{8}\gg\exp(-\delta^{-O(1)}).$

We will then set $\epsilon=\exp(-\log^{O(1)}(1/\delta))$ and continue as usual
in the argument until [12, Lemma 6.1]. We now highlight the improvement to
[12]. Instead of invoking [12, Lemma 6.1], we invoke the following
quantitative improvement to [12, Lemma 6.1]:

######  Lemma 7.1.

Let $\delta\in(0,1/10)$, $N>100$ be prime, and $G/\Gamma$ be a two-step
nilmanifold of dimension $d$, complexity $M$, and degree $k$ equipped with the
standard filtration and let $g(n)\in\mathrm{poly}(\mathbb{Z},G)$ with
$g(n)\Gamma$ periodic modulo $N$. Furthermore, let $F_{1},F_{2},F_{3}$ be
$1$-Lipschitz functions on $G/\Gamma$ with the same nonzero frequency $\xi$.
If

$|\mathbb{E}_{n\in[N]}F_{1}(g(P(n))\Gamma)F_{2}(g(Q(n))\Gamma)\overline{F_{3}(g(P(n)+Q(n))\Gamma)}e(\alpha
P(n)+\beta Q(n))|\geq\delta$

for some frequencies $\alpha,\beta\in\widehat{\mathbb{Z}/N\mathbb{Z}}$, then
either $N\ll(\delta/M)^{-O_{P,Q}(d^{O_{P,Q}(1)})}$ or there exists
$w_{1},\dots,w_{r}\in\Gamma$ with
$\psi_{\mathrm{horiz}}(w_{1}),\dots,\psi_{\mathrm{horiz}}(w_{r})$ linearly
independent and linearly independent horizontal characters
$\eta_{1},\dots,\eta_{d-1-r}$ such that
$|w_{i}|,|\eta_{j}|\leq(\delta/M)^{-O_{P,Q}(d^{O_{P,Q}(1)})}$,
$\langle\eta_{j},w_{i}\rangle=0$ for all $i,j$, and

$\|\xi([w_{i},g])\|_{C^{\infty}[N]}=\|\eta_{j}\circ g\|_{C^{\infty}[N]}=0.$

###### Proof.

The first part of the argument is similar to the first part of the argument in
[12, Lemma 6.1]. We first use the fact that $F$ is a nilcharacter of nonzero
frequency to absorb $\alpha P(n)$ and $\beta Q(n)$ to the vertical component
of $g(P(n))$ and $g(Q(n))$, respectively to obtain $g_{1}(P(n))$ and
$g_{2}(Q(n))$. Since the conclusion only depends on the horizontal component
of $g$, and since the horizontal component of $g_{1}$ and $g_{2}$ agree with
$g$, it follows that we can assume that both $g_{1}$ and $g_{2}$ are $g$ and
$\alpha,\beta=0$. Let $H$ denote the subgroup of $G^{3}$ consisting of
elements $\\{(g_{1},g_{2},g_{3}):g_{1}g_{2}g_{3}^{-1}\in[G,G]\\}$. We claim
that $[H,H]=[G,G]^{3}$. By definition, we see that for $h\in[G,G]$ that
$(1,h,h)$ and $(h,1,h)$, and $(h,h,h^{4})$ lies inside $[H,H]$ (the last fact
is true because
$[(g_{1},g_{1},g_{1}^{2}),(h_{1},h_{1},h_{1}^{2})]=([g_{1},h_{1}],[g_{1},h_{1}],[g_{1},h_{1}]^{4})$).
This yields that $(1,1,h^{2})$ lies inside $[H,H]$, and because of
connectedness and simple connectedness, it follows that $(1,1,h)\in[H,H]$. We
can verify from there that $[H,H]=[G,G]^{3}$.

We were given the polynomial sequence

$(g(P(n)),g(Q(n)),g(P(n)+Q(n)))$

on $H$. Since $F_{i}$ are nilcharacters of frequency $\xi$ on $H$,
$F_{1}\otimes F_{2}\otimes F_{3}$ is a nilcharacter on $H$ of frequency
$(\xi,\xi,-\xi)$. Taking a quotient of $H$ by the kernel of $(\xi,\xi,-\xi)$,
which is $(x,y,x+y)$, we obtain that the center is of the form $(x,x,-x)$ with
$(x,y,z)$ being projected to $(x+y-z)(1,1,1)$. Let $H_{1}$ denote the subgroup
with the one dimensional vertical directions. Applying twosteppolynomial, we
obtain $w_{1},\dots,w_{r}$ and $\eta_{1},\dots,\eta_{d-r}$ such that $\langle
w_{i},\eta_{j}\rangle=0$ and
$\eta_{j}\circ(g(P(n)),g(Q(n)),g(P(n)+Q(n)))\equiv 0\pmod{1}$, and
$\xi([w_{i},g(P(n)),g(Q(n)),g(P(n)+Q(n))])\equiv 0\pmod{1}$. Denoting
$\eta_{j}=(\alpha_{j},\beta_{j})$ and $w_{i}=(u_{i},v_{i},u_{i}v_{i})$ and the
action $\eta_{j}(w_{i}):=\alpha_{j}(u_{i})+\beta_{j}(v_{i})$, we see that

$\|\xi([v_{i},g(P(n))])+\xi([u_{i},g(Q(n))])\|_{C^{\infty}[N]}\equiv
0\pmod{1}$ $\|\alpha_{j}(g(P(n)))+\beta_{j}(g(Q(n)))\|_{C^{\infty}[N]}\equiv
0\pmod{1}.$

Since $P$ and $Q$ are linearly independent, it follows that there exists some
coefficients $c_{k}x^{k}$, $c_{\ell}x^{\ell}$ of $P$, and $d_{k}x^{k}$ and
$d_{\ell}x^{\ell}$ of $Q$ such that $c_{k}d_{\ell}-d_{k}c_{\ell}\neq 0$. Thus,
the conditions become

$c_{k}\xi([u_{i},g(1)])+d_{k}\xi([v_{i},g(1)])\equiv 0\pmod{1}$
$c_{\ell}\xi([u_{i},g(1)])+d_{\ell}\xi([v_{i},g(1)])\equiv 0\pmod{1}$

which implies since $\alpha$ has denominator $N$ which is prime that
$\xi([u_{i},g(1)])\equiv 0\pmod{1}$ and $\xi([v_{i},g(1)])\equiv 0\pmod{1}$.
Similarly, we have $\alpha_{j}(g(1))\equiv 0\pmod{1}$ and
$\beta_{j}(g(1))\equiv 0\pmod{1}$. Let $\tilde{G}:=\\{g\in
G:\xi([v_{i},g])=0,\xi([u_{i},g])=0,\alpha_{j}(g)=0,\beta_{j}(g)=0\forall
i,j\\}$. We claim that $\tilde{G}$ is abelian, from whence the Lemma would
follow from an application of [13, Lemma A.9]. This amounts to showing that
for any $g,h\in\tilde{G}$ that $[g,h]=\mathrm{id}_{G}$. For such $g$, $(g,g)$
is annihilated by $(\alpha_{j},\beta_{j})$, and since
$\alpha_{j}(u_{i})+\beta_{j}(v_{i})=0$, it follows that $(g,g)$ can be written
as a combination of $(u_{i},v_{i})$ modulo $[G,G]^{2}$. It follows that
$[(g,g),(h,h)]=\mathrm{id}_{G}$, and thus $[g,h]=\mathrm{id}_{G}$. ∎

to obtain that the image of $m_{h}$ under the kernel of $\xi$ lies in an
abelian subnilmanifold of rationality at most $\epsilon^{-O(r)^{O(1)}}$ where
this time $r=\log^{O(1)}(1/\epsilon)$. We can then Fourier expand
$F_{\vec{h}}(m_{h}(x)\Gamma)$ in 7.1 as in the argument after [12, Lemma 6.1]
to eventually obtain

$\|p\|_{U^{s}(\mathbb{Z}/N\mathbb{Z})}\gg\epsilon^{O(r)^{O(1)}}$

which gives the desired estimate for degreelowering. This completes the proof
of asymptotic.

##  8\. The $U^{4}(\mathbb{Z}/N\mathbb{Z})$ inverse theorem

We now prove mainresult4. We restate it for the reader’s convenience. See 4
The hypothesis implies that

$\mathbb{E}_{h}\|\Delta_{h}f\|_{U^{3}}^{8}\geq\delta^{16}.$

An application of the inverse theorem of Sanders [21] combined with the
argument of [5, Theorem 10.9] (see also [14, Appendix A]) gives the following:

######  Theorem 10.

bracketpolynomialu3 There exists some real number $c>0$ with the following
property: if $c>\eta>0$ and $f\colon\mathbb{Z}/N\mathbb{Z}\to\mathbb{C}$ be
one-bounded with

$\|f\|_{U^{3}(\mathbb{Z}/N\mathbb{Z})}\geq\eta.$

Then there exists a constant $C>0$, a subset
$S\subseteq\widehat{\mathbb{Z}/N\mathbb{Z}}$ with $|S|\leq\log(1/\eta)^{C}$
and a phase $\phi\colon\mathbb{Z}/N\mathbb{Z}\to\mathbb{R}$ such that

$\phi(n)=\sum_{\alpha,\beta\in S}a_{\alpha,\beta}\\{\alpha\cdot
n\\}\\{\beta\cdot n\\}+\sum_{\alpha\in S}a_{\alpha}\\{\alpha\cdot n\\}$

with $\alpha_{i},\beta_{i}\in S$ and $a_{i}\in\mathbb{R}$ and

$|\mathbb{E}_{n\in[N]}f(n)e(\phi(n))|\geq\exp(-\log(1/\eta)^{C}).$

This implies that for a family of degree two periodic bracket polynomials
$\chi_{h}(n)$ with at most $\log(1/\delta)^{O(1)}$ many bracketed phases that
for a subset $H\subseteq\mathbb{Z}_{N}$ with $|H|\geq\delta^{O(1)}N$ that for
any $h\in H$,

$|\mathbb{E}_{n}\Delta_{h}f(n)\chi_{h}(n)|\geq\delta^{\log(1/\delta)^{O(1)}}.$

We will now use [8, Proposition 6.1]:

######  Proposition 8.1.

additivequadruples Let $f_{1},f_{2}\colon\mathbb{Z}/N\mathbb{Z}\to\mathbb{C}$
be one-bounded and $H\subseteq\mathbb{Z}/N\mathbb{Z}$ a set of cardinality
$\eta N$ such that for each $h\in H$,

$|\mathbb{E}_{n\in\mathbb{Z}/N\mathbb{Z}}f_{1}(n)f_{2}(n+h)\chi_{h}(n)|\geq\delta.$

Then for at least $\eta^{8}\delta^{4}N^{3}/2$ many quadruples
$(h_{1},h_{2},h_{3},h_{4})$ in $H$ satisfying $h_{1}+h_{2}=h_{3}+h_{4}$,

$|\mathbb{E}_{n\in\mathbb{Z}/N\mathbb{Z}}\chi_{h_{1}}(n)\chi_{h_{2}}(n+h_{1}-h_{4})\overline{\chi_{h_{3}}(n)\chi_{h_{4}}(n+h_{1}-h_{4})}|\gg\eta^{4}\delta^{2}.$

###### Proof.

We follow [8, Proposition 6.1]. We extend $\chi_{h}$ to be zero for $h\not\in
H$. The condition implies that

$\mathbb{E}_{h}1_{H}(h)|\mathbb{E}_{n}f_{1}(n)f_{2}(n+h)\chi_{h}(n)|^{2}\gg\delta^{2}\eta.$

Expanding out, we obtain

$\mathbb{E}_{h}1_{H}(h)\mathbb{E}_{n,n^{\prime}}f_{1}(n)\overline{f_{1}(n^{\prime})}f_{2}(n+h)\overline{f_{2}(n^{\prime}+h)}\chi_{h}(n)\overline{\chi_{h}(n^{\prime})}\gg\delta^{2}\eta.$

Making a change of variables $h=m-n$, $n^{\prime}=n+k$, we obtain

$\mathbb{E}_{m,n,k}1_{H}(m-n)f_{1}(n)\overline{f_{1}(n+k)}f_{2}(m)\overline{f_{2}}(m+k)\Delta_{k}\chi_{m-n}(n)\gg\delta^{2}\eta.$

Applying Cauchy-Schwarz twice, we obtain

$\mathbb{E}_{k,m,n,m^{\prime},n^{\prime}}1_{H}(m-n)\Delta_{k}\chi_{m-n}(n)$
$\overline{1_{H}(m^{\prime}-n)\Delta_{k}\chi_{m^{\prime}-n}(n)1_{H}(m-n^{\prime})\Delta_{k}\chi_{m-n^{\prime}}(n^{\prime})}1_{H}(m^{\prime}-n^{\prime})\Delta_{k}\chi_{m^{\prime}-n^{\prime}}(n^{\prime})\gg\eta^{4}\delta^{8}.$

This can be rewritten as

$\mathbb{E}_{h_{1}+h_{2}=h_{3}+h_{4}}|1_{H}(h_{1})\chi_{h_{1}}(n)1_{H}(h_{2})\chi_{h_{2}}(n+h_{1}-h_{4})\overline{1_{H}(h_{3})\chi_{h_{3}}(n)1_{H}(h_{4})\chi_{h_{4}}(n+h_{1}-h_{4})}|^{2}\gg\eta^{4}\delta^{8}$

as desired. ∎

We thus have that for at least $\delta^{O(\log(1/\delta))^{O(1)}}N^{3}$ many
additive quadruples, that is quadruples $(h_{1},h_{2},h_{3},h_{4})$ with
$h_{1}+h_{2}=h_{3}+h_{4}$, we have

$|\mathbb{E}_{n}\chi_{h_{1}}(n)\chi_{h_{2}}(n+h_{1}-h_{4})\overline{\chi_{h_{3}}(n)\chi_{h_{4}}(n+h_{1}-h_{4})}|\geq\delta^{\log(1/\delta)^{O(1)}}.$

The remainder of this section is devoted to the following.

  * 1.

Defining nilcharacters and giving constructions of three-step nilpotent Lie
groups. We will show that we can take $\chi_{h}(n)=F(g_{h}(n)\Gamma)$ for some
_Fourier expanded nilcharacter_ $F(g_{h}(n)\Gamma)$ (to be defined in Section
8.1). This occupies Sections 8.1 and 8.2

  * 2.

Analyzing the above inequality to glean structure out of $\chi_{h}$ on some
dense subset of $\mathbb{Z}_{N}$. This will involve a “sunflower-type
decomposition”, and a “linearization argument.” These are analogous to [8,
Section 7, Section 8]. This argument occupies Sections 8.3 and 8.4 and is
almost all of the improvement over [8].

  * 3.

Insert this structure to deduce the inverse theorem. This will comprise of the
“symmetry and integration steps.” This is analogous to [8, Section 9] and we
essentially follow their argument. This argument will take place in Section
8.5.

Before we proceed, we shall specify some notation.

######  Definition 8.1 (Lower order terms).

lowerorderterms The quantity $[\text{Lower order terms}]$ denotes a sum of
$d^{O(1)}$ quantities of the following form:

  * •

$a\\{\alpha_{h}n\\}\\{\beta_{h}n\\}$ or $a\\{\alpha h\\}\\{\beta n\\}$ or
$a\\{\alpha h_{i}\\}\\{\beta n\\}$

  * •

$a_{h}\\{\alpha_{h}n\\}$ or $a_{h_{i}}\\{\alpha_{h_{i}}n\\}$

  * •

$\alpha h$

where all instances of $\alpha,\beta\in\mathbb{R}$ are rational with
denominator $N$ and $|a|\leq\exp(\log(1/\delta)^{O(1)})$.

The point of lower order terms is that they can be eliminated via
onevarfouriercomplexity and bilinearfouriercomplexity. We will also use the
following shorthand.

######  Definition 8.2 (Equal up to lower order terms).

shorthandequal We say that $a\equiv b$ if $a=be([\text{Lower order terms}])$.

###  8.1. Bracket polynomials and Fourier expanded nilcharacters

In this section, we give precise definitions for notation for bracket
polynomials we work with. We refer the reader to [13, Section 2] for various
notions of Mal’cev bases.

######  Definition 8.3 (Periodic fourier expanded nilcharacter).

Given a degree two two-step nilmanifold $G/\Gamma$ with one-dimensional
vertical torus, we define a _Fourier expanded nilcharacter_ , which we will
shorten as _nilcharacter_ on $G/\Gamma$ as follows. Write
$\mathcal{X}=\\{X_{1},\dots,X_{d-1},Y\\}$ as the Mal’cev basis for $G/\Gamma$.
Then letting $g(n)$ a polynomial sequence on $G/\Gamma$ with $g(n)\Gamma$
periodic modulo $N$ and $\psi(g(n))=(\alpha_{1}n,\dots,\alpha_{d-1}n,P(n))$ we
let111We note by calculations done in [6, Appendix B] that this is indeed a
function on $G/\Gamma$.

$F(g(n)\Gamma)=e(-k\sum_{i<j}C_{[i,j]}\alpha_{i}n[\alpha_{j}n]+kP(n))$

where $C_{[i,j]}Y=[X_{i},X_{j}]$ with $C_{[i,j]}$ an integer bounded by $Q$.
We denote $k$ to be the _frequency_ of $F$. We define $\omega=k[\cdot,\cdot]$
as the _associated asymmetric bilinear form_ on
$\text{Span}(X_{1},\dots,X_{d-1})$ to $F$.

As the proof will perform many “change of bases”, we require the following
lemma.

######  Lemma 8.1.

changeofvar Let $Q\geq 2$ and $G/\Gamma$ be a two-step nilmanifold with Malcev
basis $\mathcal{X}=\\{X_{1},\dots,X_{d-1},Y\\}$ of complexity $Q$. Let
$\mathcal{X}^{\prime}=\\{X_{1}^{\prime},\dots,X_{d-1}^{\prime},Y\\}$ be a
basis of $\mathfrak{g}$ with $X_{i}^{\prime}$ a $Q$-integer combination of
elements in $\mathcal{X}$. Then the following hold.

  * •

Letting
$\tilde{\Gamma}=\\{\exp(t_{1}X_{1}^{\prime})\exp(t_{2}X_{2}^{\prime})\cdots\exp(t_{d}X_{d}^{\prime})\exp(sY):t_{1},\dots,t_{d},s\in\mathbb{Z}\\}$,
$G/\tilde{\Gamma}$ is a nilmanifold equipped with a Mal’cev basis
$\mathcal{X}^{\prime}$ of complexity $Q^{O(d^{O(1)})}$.

  * •

If $F(g(n)\Gamma)$ is a Fourier-expanded nilcharacter on $G/\Gamma$, then
there exists a periodic Fourier-expanded nilcharacter
$\tilde{F}(\tilde{g}(n)\tilde{\Gamma})$
$F(g(2n)\Gamma)=F(\tilde{g}(n)\tilde{\Gamma})e(\text{[Lower order terms]})$
with frequency $k=4$.

###### Proof.

We first show the first item. We first note that since $\mathcal{X}$ is a
Mal’cev basis,
$[\exp(X_{i}),\exp(X_{j})]=\exp([X_{i},X_{j}])\in\exp(\mathbb{Z}Y)$, so the
structure constants of the Mal’cev basis $\mathcal{X}$ are integers. This
implies that $\exp([X_{i}^{\prime},X_{j}^{\prime}])\in\exp(\mathbb{Z}Y)$ so
$\tilde{\Gamma}$ is a group. Since we may find a bounded fundamental domain
for $G/\tilde{\Gamma}$, it follows by Bolzano-Weierstrass and the Whitney
embedding theorem that it is compact. Also, by Cramer’s rule,
$\mathcal{X}^{\prime}$ has complexity $Q^{O(d^{O(1)})}$.

We now turn to the second item. Let

$\psi_{\mathcal{X}}(g(n))=(\alpha_{1}n,\dots,\alpha_{d}n,P(n))$

and

$\psi_{\mathcal{X}^{\prime}}(g(n))=(\tilde{\alpha}_{1}n,\dots,\tilde{\alpha}_{d-1}n,P(n))$

Note that we have

$\sum_{i}\tilde{\alpha_{i}}X_{i}^{\prime}=\sum_{i}\tilde{\alpha_{i}}\sum_{j}a_{ij}X_{j}=\sum_{j}\left(\sum_{i}a_{ij}\tilde{\alpha_{i}}\right)X_{j}$

with $a_{ij}$ integers at most $Q$, so

$\alpha_{j}=\sum_{i}a_{ij}\tilde{\alpha_{i}}.$

In addition, we have (for a vector-valued [Lower order terms])

$\sum_{i}\tilde{\alpha_{i}}X_{i}^{\prime}=\sum_{j}\alpha_{j}X_{j}$

and

$\sum_{i}[\tilde{\alpha_{i}}n]X_{i}^{\prime}=\sum_{i}[\tilde{\alpha_{i}}n]\sum_{j}a_{ij}X_{j}=\sum_{j}[\alpha_{j}n]X_{j}+[\text{Lower
order terms}]\cdot\mathcal{X}.$

By the identity

$\alpha n[\beta n]-\beta n[\alpha n]\equiv\alpha\beta n^{2}+2\alpha n[\beta
n]\pmod{1}$

it follows that there exists quadratic polynomials $P_{1}$ and $P_{2}$ such
that

$F(g(n)\Gamma)=e(-k/2\sum_{i,j}[\sum_{i}\alpha_{i}nX_{i},\sum_{i}[\alpha_{i}n]X_{i}]+P_{1}(n)+[\text{Lower
order terms}])$

and

$F(g(n)\Gamma)=e(-k/2\sum_{i,j}[\sum_{i}\tilde{\alpha_{i}}nX_{i}^{\prime},\sum_{i}[\tilde{\alpha_{i}}n]X_{i}^{\prime}]+P_{2}(n)+[\text{Lower
order terms}]).$

It follows that letting $Q=P_{2}-P_{1}$ and

$\psi_{\mathcal{X}^{\prime}}(\tilde{g}(n))=(\tilde{\alpha}_{1}n,\dots,\tilde{\alpha}_{d}n,Q(n)),$

we obtain (the purpose of working with $2n$ being that it cancels out with the
factor of $\frac{1}{2}$ present in $k/2$)

$F(g(2n))=F(\tilde{g}(n)\tilde{\Gamma})e(\text{[Lower order terms]}).$

By considering a modular inverse $m$ of $2$, and modifying $\tilde{g}(n)$ to
be

$((\tilde{\alpha}_{1}2m)n,\dots,(\tilde{\alpha}_{d}2m)n,Q(2mn))$

it follows that $Q(2m\cdot)$ is divisble by $2$, and since the leading
coefficient of the bracket part of $\tilde{F}(\tilde{g})$ is divisible by $4$,
it follows that we can take our frequency to be $k=4$. ∎

Finally, we will need a lemma that converts a bracket polynomial to a Fourier
expanded nilcharacter.

######  Lemma 8.2.

u3fourierexpandednilcharacter Let
$\alpha_{1},\dots,\alpha_{d},\beta_{1},\dots,\beta_{d}\in\mathbb{R}$ be
rationals with denominator $N$ and define a function
$\phi\colon\mathbb{Z}/N\mathbb{Z}\to\mathbb{R}$ via

$\phi(n)=\sum_{i=1}^{d}a_{\alpha,\beta}\\{\alpha\cdot n\\}\\{\beta\cdot
n\\}+\sum_{\alpha\in S}a_{\alpha}\\{\alpha\cdot n\\}.$

Then there exists a Fourier expanded nilcharacter $F(g(n)\Gamma)$ of
complexity $2$ and frequency $1$ such that

$e(\phi(n))=F(g(n)\Gamma)e([\text{Lower order terms}]).$

###### Proof.

An application of the $U^{3}$ inverse theorem gives us a bracket polynomial of
the form

$\sum_{i}a_{i}\\{\alpha_{i}n\\}\\{\beta_{i}n\\}.$

We write

$a_{i}\\{\alpha_{i}n\\}\\{\beta_{i}n\\}=[a_{i}](\alpha_{i}n-[\alpha_{i}n])(\beta_{i}n-[\beta_{i}n])+\\{a_{i}\\}\\{\alpha_{i}n\\}\\{\beta_{i}n\\}.$

Defining

$G=\begin{pmatrix}1&\mathbb{R}&\cdots&\cdots&\mathbb{R}\\\
0&1&\cdots&0&\mathbb{R}\\\ 0&0&1&\cdots&\mathbb{R}\\\ 0&0&0&\ddots&\vdots\\\
0&0&0&\cdots&1\end{pmatrix},$
$\Gamma=\begin{pmatrix}1&\mathbb{Z}&\cdots&\cdots&\mathbb{Z}\\\
0&1&\cdots&0&\mathbb{Z}\\\ 0&0&1&\cdots&\mathbb{Z}\\\ 0&0&0&\ddots&\vdots\\\
0&0&0&\cdots&1\end{pmatrix},$

with $G$ $2d+1$ dimensional and $X_{1},\dots,X_{d}$ represent the coordinates
(from left to right) of the first row and $X_{d+1},\dots,X_{2d}$ the
coordinates (from top to bottom), and $Y$ the last coordinate, we see that a
bracket polynomial of the form
$[a_{i}](\alpha_{i}n-[\alpha_{i}n])(\beta_{i}n-[\beta_{i}n])+\\{a_{i}\\}\\{\alpha_{i}n\\}\\{\beta_{i}n\\}$
can be realized (up to lower order terms periodic in $N$) as a Fourier
expanded nilcharacter on $G/\Gamma$ with $d$ being proportional to the number
of brackets in the sum. ∎

Thus, we may assume that $\chi_{h}(n)=F(g_{h}(n)\Gamma)$ for some Fourier
expanded nilcharacter of frequency $4$.

###  8.2. Three-step nilmanifold constructions

This section is meant to give explicit constructions of (approximate)
nilsequences certain degree $3$ bracket polynomials. It is meant to be skimmed
on first reading.

######  Lemma 8.3.

Let
$\alpha_{1},\dots,\alpha_{k},\beta_{1},\dots,\beta_{k},\gamma_{1},\dots,\gamma_{k},\alpha_{1}^{\prime},\dots,\alpha_{k}^{\prime},\beta_{1}^{\prime},\dots,\beta_{k}^{\prime}\in\mathbb{R}$.
Consider

$e(-\sum_{j=1}^{k}\alpha_{j}n\\{\beta_{j}n\\}\\{\gamma_{j}n\\}-\sum_{j=1}^{\ell}\alpha_{j}^{\prime}n^{2}\\{\beta_{j}^{\prime}n\\}).$

There exists a nilmanifold $G/\Gamma$ of degree $3$, complexity $O(1)$, and
dimension $O(k)$, and an approximate nilsequence $F(g(n)\Gamma)$ with $F$
$O(d)$-Lipschitz outside of the boundary of the standard fundamental domain
$\psi^{-1}((-1/2,1/2]^{d})$ of $G/\Gamma$ such that

$F(g(n)\Gamma)=e(-\sum_{j=1}^{k}\alpha_{j}n\\{\beta_{j}n\\}\\{\gamma_{j}n\\}-\sum_{j=1}^{\ell}\alpha_{j}^{\prime}n^{2}\\{\beta_{j}^{\prime}n\\}).$

###### Proof.

We give two proofs. The first will follow[8]. We let the free $3$-step Lie
group:

$G=\\{e_{1}^{t_{1}}e_{2}^{t_{2}}e_{3}^{t_{3}}e_{21}^{t_{21}}e_{211}^{t_{211}}e_{31}^{t_{31}}e_{311}^{t_{311}}e_{32}^{t_{32}}e_{322}^{t_{322}}e_{212}^{t_{212}}e_{312}^{t_{312}}e_{213}^{t_{213}}e_{313}^{t_{313}}e_{323}^{t_{323}}\\}$

where the $t_{i},t_{ij},t_{ijk}$ range over $\mathbb{R}$ and with the
relations $[e_{i},e_{j}]=e_{ij}$ and $[[e_{i},e_{j}],e_{k}]=e_{ijk}$ and the
Jacobi identity

$[[e_{i},e_{j}],e_{k}][[e_{j},e_{k}],e_{i}][[e_{k},e_{i}],e_{j}]=1.$

We also take the lattice $\Gamma$ to be the subgroup of the above group where
the $t_{i},t_{ij},t_{ijk}$ range over $\mathbb{Z}$. Letting
$s_{i},s_{ij},s_{ijk}$ be the coordinates in the fundamental domain of
$G/\Gamma$, we see that

$s_{i}=\\{t_{i}\\},s_{ij}=\\{t_{ij}-t_{i}[t_{j}]\\},s_{ijk}=\\{t_{ijk}-t_{ik}[t_{j}]-t_{ij}[t_{i}]+t_{i}[t_{j}][t_{k}]\\}.$

Thus, this expresses $e_{1}^{\alpha n}e_{2}^{\beta n}e_{3}^{\gamma n}$ as
$e([\alpha n][\beta n]\gamma n)$ with a bunch of lower order terms that we can
take care of using the construction from earlier parts.

The second proof follows [9]. Let $G_{1}$ be the subgroup of the above matrix
group we constructed which is generated by the elements where only the first
(top) row is nonzero. This can be generated by elements $x_{i}$, which
correspond to elements where only the $i$th element (from the left) of the
first row is nonzero, and $z$ which represents the rightmost coordinate of the
first row. Let $y_{i}$ be the $i+1$th element (starting from the top) of the
last column (from the left). The approximate nilsequence we desire to
replicate is thus

$g(n)=x_{1}^{\alpha_{1}n\\{\beta_{1}n\\}}\cdots
x_{k}^{\alpha_{1}n\\{\beta_{1}n\\}}x_{k+1}^{\alpha_{1}^{\prime}n^{2}}\cdots
x_{k+\ell}^{\alpha_{\ell}^{\prime}n^{2}}$ $y_{1}^{\gamma_{1}n}\cdots
y_{k}^{\gamma_{k}n}y_{k+1}^{\beta_{1}^{\prime}n}\cdots
y_{k+\ell}^{\beta_{\ell}^{\prime}n}$

and $F(x\Gamma)=e(\\{z-x[y]\\})$. To define this to be a three-step
nilsequence, we define a group $H=\langle x_{1},x_{2},\dots,x_{k},z\rangle$
and we consider the semidirect product $G\ltimes H$ with the action being
conjugation. We define the action $\rho^{k}$ of $\mathbb{R}^{k}$ on $G\ltimes
H$ by $\rho(t)(g,g_{1}):=(gg_{1}^{t},g_{1})$, and finally consider
$G^{\prime}=\mathbb{R}^{k}\rtimes_{\rho^{k}}(G\ltimes H)$. One can check that
this is a three-step nilpotent Lie group with respect to the lower central
series. We now define
$\Gamma^{\prime}=\mathbb{Z}\rtimes_{\rho^{k}}(\Gamma\ltimes(H\cap\Gamma))$ and
consider the polynomial sequence

$g^{\prime}(n)=(0,(x_{k+1}^{\alpha_{1}^{\prime}n^{2}}\cdots
x_{k+\ell}^{\alpha_{\ell}^{\prime}n^{2}}y_{1}^{\gamma_{1}n}\cdots
y_{k}^{\gamma_{k}n}\cdots y_{k+\ell}^{\beta_{\ell}^{\prime}n},$
$x_{1}^{\alpha_{1}n}\cdots
x_{k}^{\alpha_{k}n}),(\beta_{1}n,\beta_{2}n,\dots,\beta_{k}n),(id,id)).$

and the function

$F^{\prime}((t,(g,g^{\prime}))\Gamma^{\prime})=F(g\Gamma).$

It follows then that

$g^{\prime}(n)\Gamma^{\prime}=(\\{\beta_{1}n\\},\dots,\\{\beta_{k}n\\},(g(n),x_{1}^{\alpha_{1}n}\cdots
x_{k}^{\alpha_{k}n}))\Gamma^{\prime}$

so that

$F^{\prime}(g^{\prime}(n)\Gamma^{\prime})=e(-\sum_{j}\alpha_{j}n\\{\beta_{j}n\\}[\gamma_{j}n]-\sum_{j}\alpha_{j}^{\prime}n^{2}[\beta_{j}^{\prime}n]).$

Finally, to complete the nilmanifold construction, we use
$[\gamma_{j}n]=\gamma_{j}n-\\{\gamma_{j}n\\}$ and
$[\beta_{j}^{\prime}n]=\beta_{j}^{\prime}n-\\{\beta_{j}^{\prime}n\\}$ and
apply a very similar nilmanifold construction to the remaining terms we get
under this expansion. ∎

###  8.3. Sunflower type decomposition

We will now deduce one of the primary improvements to [8]. This corresponds to
[8, Section 7].

####  8.3.1. A few reductions

We now make a set of reductions. Our first claim is that

$\chi_{h_{1}}(n)\chi_{h_{2}}(n+h_{1}-h_{4})\overline{\chi_{h_{3}}(n)\chi_{h_{4}}(n+h_{1}-h_{4})}$

is a Fourier expanded nilcharacter. To see this, by standard bracket
polynomial manipulations (see e.g., [8] and Section 3), we have

$\chi_{h_{2}}(n+h_{1}-h_{4})\overline{\chi_{h_{4}}(n+h_{1}-h_{4})}\equiv\chi_{h_{2}}(n)\overline{\chi_{h_{4}}(n)}e(\alpha_{h_{1},h_{2},h_{3},h_{4}}n^{2}+\beta_{h_{1},h_{2},h_{3},h_{4}}n+f(h)).$

Next, we observe that by tensoring two free nilcharacters together, as in
adjoining them $n\mapsto\chi_{1}(n)\chi_{2}(n)$ forms a free nilcharacter as
well by taking a product of the corresponding nilsequences
$F_{1}(g_{1}(n)\Gamma_{1})F_{2}(g_{2}(n)\Gamma_{2})=\tilde{F}(\tilde{g}(n)\tilde{\Gamma})$
with $\tilde{F}(x,y)=F_{1}(x)F(y)$, $\tilde{G}=G_{1}\times
G_{2}/\text{ker}(Y_{1}+Y_{2})$ where $Y_{i}$ is the vertical component of
$G_{i}$. Let $\pi:G_{1}\times G_{2}\to\tilde{G}$ be the quotient map. We note
that induced asymmetric bilinear form on $\tilde{G}$ is
$k_{1}\omega_{1}+k_{2}\omega_{2}$ where $k_{i}$ is the frequency of $F_{i}$.
We thus have $\tilde{g}=\pi(g_{1}(n),g_{2}(n))$ and
$\tilde{\Gamma}=\pi(\Gamma_{1}\times\Gamma_{2})$. Finally, we observe that
modifying the quadratic term does not change whether or not a function is a
free nilcharacter. Hence, we’ve realized

$\chi_{h_{1}}(n)\chi_{h_{2}}(n+h_{1}-h_{4})\overline{\chi_{h_{3}}(n)\chi_{h_{4}}(n+h_{1}-h_{4})}$

as a free nilcharacter on
$G^{(4)}:=G^{4}/\mathrm{ker}(Y_{1}+Y_{2}-Y_{3}-Y_{4})$.

####  8.3.2. Sunflower iteration

If $\chi_{h}(n)=F(g_{h}(n)\Gamma)$, we define
$\tilde{\chi_{h}}(n)=F(g_{h}(n)\Gamma)\psi(g_{h}(n)\Gamma)$ where $\psi$ is a
smooth cutoff function on the horizontal torus
$\mathbb{R}^{d}/\mathbb{Z}^{d}\cong[-1/2,1/2)^{d}$ supported on
$[-1/2+\delta^{O(d)^{O(1)}},1/2-\delta^{O(d)^{O(1)}}]^{d}$, it follows that

$\|\chi_{h}-\tilde{\chi}_{h}\|_{L^{1}[N]}\leq\delta^{O(d^{O(1)})},$

so we may replace $\chi_{h}$ with $\tilde{\chi}_{h}$ at the cost of shrinking
the right hand side of the inequality by a bit (but will still appear as
$\delta^{O(d)^{O(1)}}$).

For simplicity, we shall relabel the $\delta^{\log(1/\delta)^{O(1)}}$ as just
$\delta$ and $\tilde{\chi}_{h}$ as simply $\chi_{h}$ for the remainder of this
section. Similarly to [8], for some subset $H\subseteq\mathbb{Z}_{N}$, $h\in
H$ we let

  * •

$\Xi$ will denote the phases of the Fourier expanded nilcharacter;

  * •

$\Xi_{h}$ be the $h$-dependent phases of the Fourier expanded nilcharacter;

  * •

$\Xi_{*}$ be the $h$-independent phases as $h$;

  * •

$\Xi_{h}^{G}$ be the subgroup in $G$ generated by the $h$-dependent
dimensions;

  * •

and $\Xi_{*}^{G}$ the subgroup of $G$ generated by the $h$-independent
dimensions.

Given a nilmanifold $G/\Gamma$ with Mal’cev basis $(X_{1},\dots,X_{d-1},Y)$
for the lower central series filtration with one-dimensional vertical
component, and a polynomial sequence of the form
$\psi(g(n))=(\alpha_{1}n,\dots,\alpha_{d-1}n,P(n))$, we denote

$\psi_{horiz}(g(n))=\sum_{i}\alpha_{i}X_{i}.$

We shall also write

$\psi_{horiz}(g)\equiv\sum_{i}\beta_{i}X_{i}\pmod{\Gamma}$

to signify that $\psi_{horiz}(g)$ is equal to $\sum_{i}\beta_{i}X_{i}$ up to
an element in the $\mathbb{Z}$-span of $(X_{1},\dots,X_{d-1})$. We are finally
ready to state the sunflower step.

######  Lemma 8.4.

sunflower Suppose for $\delta|H|^{3}$ many additive quadruples
$(h_{1},h_{2},h_{3},h_{4})$ inside $H^{4}$ with $|H|\geq\delta N$ that

$|\mathbb{E}_{n\in[N]}\chi_{h_{1}}(n)\chi_{h_{2}}(n+h_{1}-h_{4})\overline{\chi_{h_{3}}(n)\chi_{h_{4}}(n+h_{1}-h_{4})}|\geq\delta.$

Then there exists a subset $H^{\prime}\subseteq H$ such that
$|H^{\prime}|\geq\delta^{O(d)^{O(1)}}|H|$ and for each $h\in H^{\prime}$,
there exists some $r>0$ and fixed $\alpha_{1},\dots,\alpha_{r}$ such that
denoting
$\psi_{horiz}(G)=\mathrm{span}(X_{1},\dots,X_{k},Z_{1},\dots,Z_{\ell})$ the
Mal’cev basis with complexity at most $\delta^{-O(d)^{O(1)}}$, there exists
some integer $|q|\leq\delta^{-O(d)^{O(1)}}$ and some ordering of the Mal’cev
basis $(X_{1},\dots,X_{k},Z_{1},\dots,Z_{\ell})$ such that denoting

$\psi_{horiz}(g_{h})=\sum_{i}\xi_{h}^{i}X_{i}+\sum_{j}\xi_{*}^{j}Z_{j}$

, we have

$g_{h}(q\cdot)\equiv\alpha_{1}X_{1}+\cdots+\alpha_{r}X_{r}+\xi_{h}^{r+1}Y_{r+1}+\cdots+\xi_{h}^{k}Y_{k}+\xi_{*}^{1}Z_{1}+\cdots+\xi_{*}^{\ell}Z_{\ell}\pmod{\Gamma}.$

where $X_{1},\dots,X_{r},Y_{r+1},\dots,Y_{k},Z_{1},\dots,Z_{\ell}$ are
linearly independent and each $Y_{j}$ is a $\delta^{-O(d)^{O(1)}}$-rational
combination of $X_{i}$’s and we have that the asymmetric bilinear form
$\omega$ restricted to $\mathrm{span}(Y_{1},\dots,Y_{k})$ vanishes.

######  Remark 8.1.

This lemma will be used (following the procedure in Section 7.2 to change
bases $(X_{1},\dots,X_{k},Z_{1},\dots,Z_{\ell})$ to
$(X_{1}.\dots,X_{r},Y_{r+1},\dots,Y_{k},Z_{1},\dots,Z_{\ell})$ and reordering
so that $Y_{i}$’s appear before the $X_{i}$’s and the $Z_{i}$’s) with the
“new” $X_{i}$’s consisting of $Y_{r+1},\dots,Y_{k}$ and the “new” $Z_{j}$’s
consisting of $X_{1},\dots,X_{r},Z_{1},\dots,Z_{\ell}$. Additionally, since we
can accomplish this lemma in one single application of [13, Theorem 8], it
follows that we do not need to consider $h$-independent phases in the
hypothesis for our argument of the main theorem.

###### Proof.

Let $\omega$ denote the asymmetric bilinear form associated to $G/\Gamma$
representing the commutator bracket. Let $d=k+\ell+1$ be the dimension of $G$.
Let $G_{(4)}=\\{x\in G^{(4)}:\text{the }Z_{i}\text{ components of }x\text{ are
equal}\\}$. The commutator bracket on $G^{(4)}$ is of the form
$\omega_{1}+\omega_{2}-\omega_{3}-\omega_{4}$ where $\omega_{i}$ represents
the commutator bracket on the $i$th coordinate of $G^{4}$. We let
$\tilde{\omega}$ be the restriction of that commutator bracket to $G_{(4)}$.
Then by twostepcor, and Pigeonholing in $(h_{1},h_{2},h_{3},h_{4})$, one can
find a $\delta^{-O(d)^{O(1)}}$-rational subspace $V$ with
$\tilde{\omega}(V,V)=0$ such that for a set $R$ of at least
$\delta^{O(d)^{O(1)}}N^{3}$ many additive quadruples
$(h_{1},h_{2},h_{3},h_{4})$, (up to an integer shift possibly depending on
$h_{1},h_{2},h_{3},h_{4}$)
$\psi_{horiz}(g_{h_{1}},g_{h_{2}},g_{h_{3}},g_{h_{4}},g_{*})$ lies in $V$. Let
$V_{123}=\pi_{123}(V)$ be the projection into the first three coordinates and
the $h$-independent coordinate and $V_{124}=\pi_{124}(V)$ be the projection of
$V$ into the first, second, and fourth coordinates and the $h$-independent
coordinate. We write

$V_{123}=\\{(g_{1},g_{2},g_{3},g_{*}):\eta_{h_{1}}(g_{1})+\eta_{h_{2}}(g_{2})+\eta_{h_{3}}(g_{3})+\eta_{*}(g_{*})=0\forall\eta=(\eta_{h_{1}},\eta_{h_{2}},\eta_{h_{3}},\eta_{*})\in
S\\}$

where $S$ consists of linearly independent integer vectors. Similarly, we
write

$V_{124}=\\{(g_{1},g_{2},g_{4},g_{*}):\eta_{h_{1}}^{\prime}(g_{1})+\eta_{h_{2}}^{\prime}(g_{2})+\eta_{h_{4}}^{\prime}(g_{4})+\eta_{*}^{\prime}(g_{*})=0\forall\eta^{\prime}=(\eta_{h_{1}}^{\prime},\eta_{h_{2}}^{\prime},\eta_{h_{4}}^{\prime},\eta_{*}^{\prime})\in
S^{\prime}\\}.$

Since $V$ is $\delta^{-O(d)^{O(1)}}$-rational, it follows that $V_{123}$ is
also $\delta^{-O(d)^{O(1)}}$-rational, so by Cramer’s rule (e.g., [13, Lemma
A.8]), it follows that we may take all $\eta_{h_{i}}$,
$\eta_{h_{i}}^{\prime}$, $\eta_{*}$, $\eta_{*}^{\prime}$ to be of size
$\delta^{-O(d)^{O(1)}}$. Let

$W_{1}=\\{v\in\text{span}(X_{1},\dots,X_{k}):(v,0,0,0)\in V_{123}\\}$
$W_{2}=\\{v\in\text{span}(X_{1},\dots,X_{k}):(v,0,0,0)\in V_{124}\\}.$

Note that $v$ lies in $W_{1}$ if and only if $\eta_{h_{1}}(v)=0$ for all
$\eta\in S$ and similarly $w\in W_{2}$ if and only if
$\eta_{h_{1}}^{\prime}(w)=0$ for all $\eta^{\prime}\in S^{\prime}$.
Furthermore, since $\tilde{\omega}(V,V)=0$, and $v\in W_{1}$ and $w\in W_{2}$,
it follows that $(v,0,0,0)\in V_{123}$ lifts to $(v,0,0,z,0)$ and
$(w,0,0,0)\in V_{124}$ lifts to $(w,0,z^{\prime},0,0)$ for elements
$z,z^{\prime}\in\text{span}(Z_{1},\dots,Z_{\ell})$. Thus, denoting $\tilde{v}$
and $\tilde{w}$ these lifts, we have
$0=\tilde{\omega}(\tilde{v},\tilde{w})=\omega(v,w)$. Hence
$\omega(W_{1},W_{2})=0$. Let $W=W_{1}\cap W_{2}$. Note that an element $w\in
W$ if and only if for each $\eta\in S$ and $\eta^{\prime}\in S^{\prime}$ that
$\eta_{h_{1}}(w)=0$ and $\eta_{h_{1}}^{\prime}(w)=0$.

By the Pigeonhole principle, there are thus $\delta^{O(d)^{O(1)}}N$ many
$h_{1}$ which is part of at least $\delta^{O(d)^{O(1)}}N^{2}$ additive
quadruples $(h_{1},h_{2},h_{3},h_{4})$ in $R$. Thus, there are at least
$\delta^{O(d)^{O(1)}}N^{5}$ many elements
$(h_{1},h_{2},h_{3},h_{2}^{\prime},h_{4}^{\prime})$ such that
$(h_{1},h_{2},h_{3},h_{1}+h_{2}-h_{3})\in R$ and
$(h_{1},h_{2}^{\prime},h_{1}+h_{2}^{\prime}-h_{4}^{\prime},h_{4}^{\prime})\in
R$. By the Pigeonhole principle, there exists choices $(h_{2},h_{3})$ and
$(h_{2}^{\prime},h_{4}^{\prime})$ such that there are at least
$\delta^{O(d)^{O(1)}}N$ many $h_{1}$ with
$(h_{1},h_{2},h_{3},h_{1}+h_{2}-h_{3})\in R$ and
$(h_{1},h_{2}^{\prime},h_{1}+h_{2}^{\prime}-h_{4}^{\prime},h_{4}^{\prime})\in
R$. Let $H^{\prime}$ denote this set of $h_{1}$’s.

Let the projection to $h_{1}$ component of elements in $S\cup S^{\prime}$ be
$(\tilde{\eta}^{1},\dots,\tilde{\eta}^{r})$ and suppose without a loss of
generality that $\tilde{\eta}^{i}$ are linearly independent. Let us assume
without a loss of generality that $\tilde{\eta}^{1},\dots,\tilde{\eta}^{r}$
are Gaussian eliminated and (after possibly reordering the variables) are in
row-reduced echelon form. This can be done while keeping similar bounds for
these elements. Noticing that $h_{2},h_{3},h_{2}^{\prime},h_{4}^{\prime}$ are
fixed, there exists fixed $h$-independent phases $\alpha_{1},\dots,\alpha_{r}$
such that for each $h\in H^{\prime}$, we have

$\tilde{\eta}^{i}(g_{h})+\alpha_{i}\equiv 0\pmod{1}.$

By scaling $g_{h}(\cdot)$ by $q$, we may assume that the first nonzero
component of $\tilde{\eta}^{i}$ is an integer. Thus (since
$\tilde{\eta}^{1},\dots,\tilde{\eta}^{r}$ are in row-reduced echelon form), we
may write

$\psi_{horiz}(g_{h}(q\cdot))\equiv\alpha_{1}X_{1}+\cdots+\alpha_{r}X_{r}+\xi_{h}^{r+1}Y_{r+1}+\cdots+\xi_{h}^{k}Y_{k}+\xi_{*}^{1}Z_{1}+\cdots+\xi_{*}^{\ell}Z_{\ell}\pmod{\Gamma}$

as prescribed in the lemma. We claim that $Y_{j}\in W$ for each $j$. This is
because $\tilde{\eta}^{1},\dots,\tilde{\eta}^{r}$ are in row-reduced echelon
form so if

$g=\sum_{j}g_{j}X_{j}$

and $\tilde{\eta}^{i}(g)=0$, then we may write

$\tilde{\eta}^{i}(qg)=\sum_{j}g_{j}Y_{j}.$

Since $Y_{j}$’s are linearly independent, the set of all such $g$’s have the
same span as the set of the $Y_{j}$’s and we note that
$W=\bigcap_{i=1}^{r}\text{ker}(\tilde{\eta}^{i})$. Hence the result. ∎

Thus, we have:

######  Proposition 8.2 (Sunflower decomposition).

There exists a set $H$ of size at most

$\delta^{\log(1/\delta)^{O(1)}}N$

and associated Fourier expanded nilcharacters $\chi_{h}(n)$ associated to $h$
on a ($h$-independent) nilmanifold $G/\Gamma$ such that

$|\mathbb{E}_{n\in\mathbb{Z}_{N}}\Delta_{h}\tilde{f}(n)\chi_{h}(n)|\geq\delta^{\log(1/\delta)^{O(1)}}$

for some function $\tilde{f}=f(y\cdot)$ where $y$ is an integer relatively
prime to $N$, and the frequency set of $\chi_{h}$ decomposes as $\Xi_{h}$, an
$h$-dependent set, and $\Xi_{*}$, an $h$-independent set both of size at most
$\log(1/\delta)^{O(1)}$ such that $\omega(\Xi_{h}^{G},\Xi_{h}^{G})=0$.

###  8.4. Linearization

We begin with the following lemma:

######  Lemma 8.5.

bracketlinear Suppose $H\subseteq\mathbb{Z}_{N}$ and
$f:H\to(\widehat{\mathbb{Z}_{N}})^{d}$ has $\delta N^{3}$ additive quadruples
it preserves. Then on a subset of $H$ of size at least
$\exp(-O(\log^{4}(1/\delta)))N$, $f$ can be written as
$f(n)=(f_{1}(n),\dots,f_{d}(n))$

$f_{j}(n)=\sum_{i=1}^{\ell}a_{ij}\\{\alpha_{i}(n-k)\\}$

where $a_{ij}\in\mathbb{R}$, $\alpha_{i}\in\widehat{\mathbb{Z}_{N}}$, $k$ an
integer, and $\ell\leq O(\log^{O(1)}(1/\delta))$.

###### Proof of bracketlinear.

Balog-Szemerédi-Gowers [3, Proposition 7.3] (or rather as it is stated [5,
Theorem 5.2]) shows that we may pass to a subset $H^{\prime}$ of size
$\delta^{O(1)}N$ where denoting $\Gamma$ to be the graph of $f$ restricted to
$H^{\prime}$, we have $|\Gamma+\Gamma|\leq\delta^{-O(1)}|\Gamma|$. To continue
the proof of bracketlinear, we need the following lemma:

######  Lemma 8.6.

expandingfreiman There exists a subset $H^{\prime\prime}\subseteq H^{\prime}$
of cardinality at least $\delta^{O(1)}N$ such that $f$ is a $8$-Freiman
homomorphism.

###### Proof of expandingfreiman.

We follow the proof of [5, Lemma 9.2]. Let $\Gamma$ be the graph of $f$. Let
$A\subseteq(\widehat{\mathbb{Z}_{N}})^{d}$ be the set of all $\xi$ such that
$(0,\xi)\in 8\Gamma-8\Gamma$. Since $\Gamma$ is a graph, it follows that
$|\Gamma+A|=|\Gamma||A|$. On the other hand,
$|\Gamma+A|\leq|9\Gamma-8\Gamma|\leq\delta^{-O(d)}N$. This tells us that
$|A|\leq\delta^{-O(1)}$. By [5, Lemma 8.3], we may find a set
$T\subseteq\mathbb{Z}_{N}^{d}$ with $|T|\leq O(\log_{2}(1/\delta))$ such that
$A\cap B(T,1/4)=\\{0\\}$ where
$B(T,1/4)=\\{\xi\in\widehat{\mathbb{Z}_{N}}^{d}:\|t(\xi)\|_{\mathbb{R}/\mathbb{Z}\forall
t\in T}<1/4\\}$.

Let $\Psi:\widehat{\mathbb{Z}_{N}}^{d}\to(\mathbb{R}/\mathbb{Z})^{T}$ be the
homomorphism $\Psi(\xi)=(t(\xi))_{t\in T}$. We may cover
$(\mathbb{R}/\mathbb{Z})^{T}$ by $2^{6|T|}\leq 2^{6}\delta^{-O(1)}$ many cubes
of side length $\frac{1}{64}$. Since $|\Gamma|\geq\delta N$, it follows that
there exists some cubes $Q$ for which

$\Gamma^{\prime}:=\\{(h,f(h))\in\Gamma:\Psi(f(h))\in Q\\}$

has cardinality $\delta^{O(1)}N$. By linearity of $t$, it follows that if
$(0,\xi)\in 8\Gamma^{\prime}-8\Gamma^{\prime}$ then
$\|t(\xi)\|_{\mathbb{R}/\mathbb{Z}}\leq\frac{16}{64}$, so $\xi\in B(T,1/4)$.
On the other hand, $\xi$ also lies in $A$, so $\xi=0$ by construction of $T$.
This allows us to conclude that $4\Gamma^{\prime}-4\Gamma^{\prime}$ is a
graph, or in other words, $f$ is an $8$-Freiman homomorphism on
$H^{\prime\prime}$, the projection of $\Gamma^{\prime}$ to the first
coordinate. ∎

Since $f$ is an $8$-Freiman hoomorphism on $H^{\prime\prime}$, $f$ is a
Freiman homomorphism on $2H^{\prime\prime}-2H^{\prime\prime}$, which by [21]
and [19, Proposition 27] contains a Bohr set $B=B(S,\rho)$ where
$|S|\leq\log(1/\delta)^{O(1)}$ and $\rho\geq\delta^{C}$ for some constant
$C>0$. Thus, $f$ restricts to a Freiman homomorphism on a Bohr set
$f:B\to(\widehat{\mathbb{Z}/N\mathbb{Z}})^{d}$. We now require the following
lemma which is essentially [5, Proposition 10.8] to finish the proof of
bracketlinear:

######  Lemma 8.7.

bohrbracket Suppose $f:B\to\widehat{\mathbb{Z}/N\mathbb{Z}}$ is a Freiman
homomorphism. Then letting $B_{\epsilon}=B(S,\rho\epsilon)$, it follows that
on $B_{|S|^{-O(|S|)}}$, one can write

$f(n)=\sum_{i}a_{i}\\{\alpha_{i}n\\}+\gamma$

where each $\alpha_{i}\in S$.

###### Proof of bohrbracket.

By [5, Proposition 10.5], $B$ contains a symmetric proper generalized
arithmetic progression
$P=\\{\ell_{1}n_{1}+\cdots+\ell_{d^{\prime}}n_{d^{\prime}}:n_{i}\in[-N_{i},N_{i}]\\}$
with $1\leq d^{\prime}\leq|S|$ such that $P$ contains $B_{|S|^{-O(|S|)}}$ and
$(\\{\alpha\ell_{i}\\})_{\alpha\in\mathbb{R}^{S}}$ are linearly independent.
It follows that we may write

$f(\ell_{1}n_{1}+\cdots+\ell_{d}n_{d})=n_{1}f(\ell_{1})+\cdots+n_{d}f(\ell_{d})+f(0)=n_{1}k_{1}+\cdots+n_{d}k_{d}+\gamma.$

Let $\Phi:B\to\mathbb{R}^{S}$ be $\phi(x)=(\\{\alpha x\\})_{\alpha\in S}.$ We
see that

$\Phi(\ell_{1}n_{1}+\cdots+\ell_{d^{\prime}}n_{d^{\prime}})=n_{1}\Phi(\ell_{1})+\cdots+n_{d}\Phi(\ell_{d^{\prime}}).$

Since $\Phi(\ell_{i})$ are linearly independent, it follows that (by scaling
up a vector in the orthogonal complement of $\Phi(\ell_{j})$ for $j\neq i$ but
not in the orthogonal complement of $\Phi(\ell_{i})$ for all $i$) there exists
a vector $u_{i}$ such that
$u_{i}\cdot\Phi(\ell_{1}n_{1}+\cdots+\ell_{d^{\prime}}n_{d^{\prime}})=\ell_{i}$.
Thus, writing $u_{i}=(u_{i\alpha})_{\alpha\in S}$, we see that

$\ell_{i}=\sum_{\alpha\in S}u_{i\alpha}\\{\alpha x\\}.$

The lemma follows from this. ∎

Thus, each component of $f$ agrees with a bracket linear function with at most
$d$ many phases on $B_{d^{-O(d)}}$. By the Pigeonhole principle, there exists
some $x_{0}$ such that $|(x_{0}+B_{1/2})\cap H|\geq\delta^{O(1)}N$ where
$B_{1/2}$ is the $\frac{1}{2}$-dilation of $B$ (say regularized as well). Let
$A=(x_{0}+B)\cap H$. Then for $h,h^{\prime}\in A$, we have
$(h-h^{\prime},f(h)-f(h^{\prime}))$ lies inside
$\Gamma^{\prime}-\Gamma^{\prime}$, so
$f(x_{0}+h)-f(x_{0}+h^{\prime})=f(h-h^{\prime})$, so there exists $\xi_{0}$
such that $f(x_{0}+h)=\xi_{0}+f(h)$. Thus, there exists some set of size at
least $\delta^{O_{\epsilon}(\log^{3+\epsilon}(1/\delta))}N$ such that $f$ is a
bracket polynomial with $\log^{3+\epsilon}(1/\delta)$ many bracket phases. ∎

We will also need the following lemma:

######  Lemma 8.8 (Cauchy-Schwarz inequality for energy).

CSenergy We have the following:

$E(A_{1},A_{2},A_{3},A_{4})\leq
E(A_{1})^{1/4}E(A_{2})^{1/4}E(A_{3})^{1/4}E(A_{4})^{1/4}.$

###### Proof.

We see that

$E(A_{1},A_{2},A_{3},A_{4})=\frac{1}{N^{3}}\sum_{z\in(A-C)\cap(B-D)}|A\cap(C+z)||B\cap(D+z)|.$

By Cauchy-Schwarz, we may bound this by

$\sqrt{\left(\frac{1}{N^{3}}\sum_{z\in
A-C}|A\cap(C+z)|^{2}\right)\left(\frac{1}{N^{3}}\sum_{z\in
B-D}|B\cap(D+z)|^{2}\right)}.$

We see by [24, Lemma 2.9] that

$\frac{1}{N^{3}}\sum_{z\in A-C}|A\cap(C+z)|^{2}=E(A,C)\leq
E(A)^{1/2}E(C)^{1/2}$

and similarly

$\frac{1}{N^{3}}\sum_{z\in B-D}|B\cap(D+z)|^{2}=E(B,D)\leq
E(B)^{1/2}E(D)^{1/2}.$

∎

We now prove the linearization step:

######  Lemma 8.9.

linearizationstep Suppose

$|\mathbb{E}_{n\in[N]}\chi_{h_{1}}(n)\chi_{h_{2}}(n+h_{1}-h_{4})\overline{\chi_{h_{3}}(n)\chi_{h_{4}}(n+h_{1}-h_{4})}|\geq\delta.$

and that $\omega(\Xi_{h}^{G},\Xi_{h}^{G})=0$. Then there exists a set
$S\subseteq\widehat{\mathbb{Z}_{N}}$ such that $|S|\leq\log(1/\delta)^{O(1)}$
and a subset $H^{\prime}\subseteq H$ with
$|H^{\prime}|\geq\log(1/\delta)^{O(1)}$ such that for each $h\in H^{\prime}$
there exists some $k\in\mathbb{Z}_{N}$ such that denoting $\xi_{h}^{struc}$ as
a generic element of the form

$\xi_{h}^{struc}=\sum_{\alpha\in S}a_{\alpha}\\{\alpha(h-k)\\}$

where $a_{\alpha}\in\mathbb{R}$ so that each $h\mapsto\\{\alpha(h-k)\\}$ is a
Freiman homomorphism on $H^{\prime}$, we may write for some appropriate
integer scaler $q$ with $|q|\leq\delta^{-O(d)^{O(1)}}$ and some $r>0$, such
that if

$\psi_{horiz}(g(n))=\sum_{i}\xi_{h}^{i}nX_{i}+\sum_{j}\xi_{*}^{j}nZ_{j},$

we have (for some ordering of the basis
$(X_{1},\dots,X_{k},Z_{1},\dots,Z_{\ell})$),

$\psi_{horiz}(g_{h}(qn))\equiv\sum_{j\leq
r}\xi_{h}^{struc,j}nX_{j}+\sum_{j>r}\xi_{h}^{j}nY_{j}+\sum_{j\geq
r_{1}}\xi_{*}^{j}n\tilde{Z}_{j}\pmod{\Gamma}$

where $\tilde{Z}_{j}$ is a $\delta^{-d^{O(1)}\log(1/\delta)^{O(1)}}$-integer
span of $Z_{j}$ and $Y_{j}$ is the
$\delta^{-d^{O(1)}\log(1/\delta)^{O(1)}}$-integer span of the $X_{i}$’s and
the $X_{i},Y_{i},\tilde{Z}_{i}$ are linearly independent and the restriction
of $\omega(Y_{i},\tilde{Z}_{j})=0$ for each $i$ and $j$.

###### Proof.

By using various bracket polynomial identities, we may rewrite

$\chi_{h_{1}}(n)\chi_{h_{2}}(n)\overline{\chi_{h_{3}}(n)\chi_{h_{4}}(n)}$

as a free nilcharacter of the form $\tilde{\chi}_{h_{1},h_{2},h_{3},h_{4}}(n)$
which has the same free nilcharacter of $\chi_{h}$ except that at each phase
$\xi_{h}$, we replace it with
$\xi_{h_{1}}+\xi_{h_{2}}-\xi_{h_{3}}-\xi_{h_{4}}$ and there are no phases of
the form $\xi_{*}^{i}n[\xi_{*}^{j}n]$. Thus, there exists some
$\alpha_{h_{1},h_{2},h_{3},h_{4}}^{\prime}$ and
$\beta_{h_{1},h_{2},h_{3},h_{4}}^{\prime}$ such that

$|\mathbb{E}_{n\in[N]}\tilde{\chi}_{h_{1},h_{2},h_{3},h_{4}}(n)e(\alpha^{\prime}_{h_{1},h_{2},h_{3},h_{4}}n^{2}+\beta^{\prime}_{h_{1},h_{2},h_{3},h_{4}}n)|\geq\delta^{O(d)^{O(1)}}.$

Let $g_{h_{1},h_{2},h_{3},h_{4}}$ denote the nilsequence corresponding to
$\chi_{h_{1},h_{2},h_{3},h_{4}}$ and [13, Theorem 8] shows that (up to an
integer shift), $g_{h_{1},h_{2},h_{3},h_{4}}$ lies in a subspace $V$ such that
$\omega^{\prime}(V,V)=0$ where $\omega$ is the asymmetric bilinear form
corresponding to $G/\Gamma$ and
$\omega^{\prime}(X_{i},X_{j})=\omega(X_{i},X_{j})$ and
$\omega^{\prime}(X_{i},Z_{j})=\omega(X_{i},Z_{j})$, and
$\omega^{\prime}(Z_{i},Z_{j})=0$ (this last fact reflects there being no terms
of the form $\xi_{*}^{i}[\xi_{*}^{j}]$). Letting
$\eta^{i}=(\eta^{i}_{h},\eta^{i}_{*})$ be linearly independent and span the
annihilators of $V$. We have

$\eta^{i}(g_{h_{1},h_{2},h_{3},h_{4}})=\eta^{i}_{h}(\xi_{h_{1}}+\xi_{h_{2}}-\xi_{h_{3}}-\xi_{h_{4}})+\eta^{i}_{*}(\xi_{*})\equiv
0\pmod{1}.$

Thus, by a combination of CSenergy and bracketlinear, there exists a subset
$H^{\prime}$ of $H$ of size at least $\delta^{(d\log(1/\delta))^{O(1)}}|H|$
such that for each $h\in H^{\prime}$, $\eta^{i}_{h}(\xi_{h})$ is of the
prescribed bracket polynomial form (and is a Freiman homomorphism) and such
that for many additive quadruples, we have

$\eta^{i}_{h}(\xi_{h_{1}}+\xi_{h_{2}}-\xi_{h_{3}}-\xi_{h_{4}})+\eta^{i}_{*}(\xi_{*})\equiv
0\pmod{1}.$

Let $w\in\text{span}_{\mathbb{Z}}(X_{1},\dots,X_{k})$ be orthogonal to all of
the $\eta^{i}_{h}$. It follows that $(w,0)$ is orthogonal to $\eta^{i}$ and
thus $w\in V$. Hence

$\omega^{\prime}(w,g_{h_{1},h_{2},h_{3},h_{4}})=\omega(w,g_{*})\equiv
0\pmod{1}$

where $g_{*}$ is the $h$-independent part of $g_{h_{1},h_{2},h_{3},h_{4}}$.
Choosing such $w_{1},\dots,w_{s}$ of size at most
$\delta^{-d^{O(1)}\log(1/\delta)^{O(1)}}$ to be in the span of the orthogonal
subspace of the $\eta_{i}^{h}$’s, and reducing $r$ when necessary, we may
assume that $\omega(w_{i},\cdot)$ are linearly independent relations and that
$\omega(w_{i},g_{*})\equiv 0\pmod{1}$. Let $W$ be the subspace of
$\psi_{horiz}(G)$ defined as $\\{x:\eta^{i}_{h}(x)=0,\omega(w_{j},x)=0\forall
i,j\\}$. It follows that if $x,y\in W$ and $x$ lies in the span of $X_{i}$’s
then $\omega(x,y)=0$. This is because $x\in W$ implies that
$\eta^{i}_{h}(x)=0$, so $x$ can be generated by a combination of the
$w_{j}$’s. However, $\omega(w_{j},y)=0$. Hence, $\omega(x,y)=0$. Writing
$\nu_{1},\dots,\nu_{s}$ to be the relations defined by $\omega(w_{j},\cdot)$,
we have that

$\eta_{i}^{h}(g_{h})+\xi_{h}^{struc,i}\equiv 0\pmod{1}$ $\nu_{j}(g_{*})\equiv
0\pmod{1}.$

We assume that $\eta_{i}$’s and $\nu_{j}$’s are written (after possibly
reordering variables) in row-reduced echelon form. Thus, writing

$\psi_{horiz}(g_{h})=\sum_{i}\xi_{h}^{i}X_{i}+\sum_{j}\xi_{*}^{j}Z_{j}$

and scaling $g_{h}$ by an appropriate integer, it follows that there exists
some integer $q\leq\delta^{-(\log(1/\delta)d)^{O(1)}}$ such that taking the
linear relations above into account, we may write

$\psi_{horiz}(g_{h}q)\equiv\sum_{i\leq
r}\xi_{h}^{struc,i}X_{i}+\sum_{i>r}\xi_{h}^{i}Y_{i}+\sum_{j}\tilde{\xi}_{*}^{j}\tilde{Z}_{j}\pmod{\Gamma}$

where $\tilde{Z}_{j}$ is a $\delta^{-(d\log(1/\delta))^{O(1)}}$-integer
combination of $Z_{j}$’s and $Y_{i}$ is a
$\delta^{-(d\log(1/\delta))^{O(1)}}$-integer combination of the $X_{i}$’s and
that the combination of $X_{i},Y_{i},Z_{i}$ are linearly independent and
$\xi^{struc,i}_{h}$ are of the bracket polynomial form as specified above, and
that $Y_{i}$ and $\tilde{Z}_{j}$ lie inside $W$. The last property we can
guarantee because the subspace
$\\{x\in\text{span}(X_{1},\dots,X_{k}):\eta_{h}^{i}(x)=0\\}$ is spanned by
$Y_{i}$’s and the subspace
$\\{x\in\text{span}(Z_{1},\dots,Z_{\ell}):\nu_{j}(x)=0\\}$ is spanned by
$\tilde{Z}_{j}$’s. The result follows. ∎

######  Remark 8.2.

This proof can be made entirely free of use of “bracket polynomial identities”
and “Fourier complexity lemmas.” In particular, the step where we take our
modified bracket polynomial $g_{h_{1},h_{2},h_{3},h_{4}}$ and replace it with
$g_{h}$ but with $\xi_{h}$ replaced with
$\xi_{h_{1}}+\xi_{h_{2}}-\xi_{h_{3}}-\xi_{h_{4}}$ is unnecessary. One can
quotient by the subspace of
$\\{\xi_{h_{1}}+\xi_{h_{2}}-\xi_{h_{3}}-\xi_{h_{4}}=0\\}$ and argue that any
horizontal character on $G_{(4)}$ that annihilates that subspace must be of
the form

$\eta^{i}(\xi_{h_{1}},\xi_{h_{2}},\xi_{h_{3}},\xi_{h_{4}},\xi_{*})=\eta^{i}_{h}(\xi_{h_{1}}+\xi_{h_{2}}-\xi_{h_{3}}-\xi_{h_{4}})+\eta^{i}_{*}(\xi_{*}).$

By another application of the procedure in Section 8.2, we may thus write

$\psi(g_{h}(n))=(\xi_{h}^{1}n,\dots,\xi_{h}^{\ell}n,\xi_{*}^{1}n,\dots,\xi_{*}^{k}n,0,0,\dots,0,P_{h}(n))$

where $\xi_{h}^{i}$ is of the form specified by the Lemma above and
$\xi_{*}^{j}$ is $h$-independent and the $0$’s represent the coordinates
$Z_{1},\dots,Z_{r_{1}-1}$ which we eliminated in the above lemma.

This linearizes the entire bracket polynomial except for the vertical phase
$P_{h}(n)$. We write $P_{h}(n)=\alpha_{h}n^{2}+\beta_{h}n-P_{h}(1)n-{n\choose
2}\sum_{i<j}C_{[i,j]}g^{i}g^{j}$ where $(g^{1},\dots,g^{k+\ell})$ is the
ordering

$(\xi_{h}^{1},\dots,\xi_{h}^{\ell},\xi_{*}^{1},\dots,\xi_{*}^{k}).$

We note that the Mal’cev coordinates of $g_{h}(1)^{n}$ is

$(\xi_{h}^{1}n,\dots,\xi_{h}^{\ell}n,\xi_{*}^{1}n,\dots,\xi_{*}^{k}n,P_{h}(1)n+\frac{1}{2}{n\choose
2}\sum_{i<j}C_{[i,j]}g^{i}g^{j}).$

To linearize the quadratic term in $P_{h}(n)$, it thus suffices to linearize
$\alpha_{h}$ since if $i$ and $j$ correspond to some bases $X_{i^{\prime}}$
and $X_{j^{\prime}}$, then $[X_{i^{\prime}},X_{j^{\prime}}]=C_{[i,j]}=0$. We
aim to linearize $\alpha_{h}$. It turns out that we do not need to linearize
the linear term in $P_{h}(n)$ since we will be able to eliminate it via the
symmetry argument. First we show that $\alpha_{h}$ is rational with
denominator $2N$. To show this, we essentially follow the procedure in
periodic. Consider the sequence

$\tau_{k}(g_{h}(n))\Gamma\times\Gamma=(g_{h}(n+k),g_{h}(n))\Gamma\times\Gamma=(g_{h}(1)^{n}g_{h}^{nlin}(n+k)[\\{g_{h}(1)^{k}\\}^{-1},g(1)^{-n}],g(1)^{n})\Gamma\times\Gamma$

where $g_{h}^{nlin}(n)=g_{h}(n)g_{h}(1)^{-n}$. This restricts to a sequence in
$G\times_{G_{2}}G/(\Gamma\times_{G_{2}\cap\Gamma}\Gamma)$. Since
$(g_{h}(n+k),g_{h}(n))\Gamma\times\Gamma$ is periodic, so is
$(g_{h}(1)^{n}g_{h}^{nlin}(n+k)[\\{g_{h}(1)^{k}\\}^{-1},g(1)^{-n}],g_{h}(1)^{n})\Gamma\times\Gamma$
and its restriction. By [13, Lemma A.3], each horizontal character $\eta$ on
$G\times_{G_{2}}G$ decomposes as
$\eta(g,g^{\prime})=\eta_{1}(g)+\eta_{1}(g^{\prime}g^{-1})$ where $\eta_{1}$
is a horizontal character on $G$ and $\eta_{2}$ is a character on
$G_{2}/[G_{2},G]=G_{2}$. Since $\tau_{k}$ is periodic modulo $N$, it follows
that for any $\eta_{2}$, that

$\eta_{2}(g_{h}^{nlin}(n+k))-\eta_{2}(g_{h}^{nlin}(n))+\eta_{2}([\\{g_{h}(1)^{k}\\},g_{h}(1)^{n}])\equiv
0\pmod{1/N}.$

Since $\\{g_{h}(1)^{k}\\}[g_{h}(1)^{k}]=g_{h}(1)^{k}$ and
$[g_{h}(1)^{k},g_{h}(1)^{n}]=0$, it follows that

$\eta_{2}([\\{g_{h}(1)^{k}\\},g_{h}(1)^{n}])=\eta_{2}([[g_{h}(1)^{k}]^{-1},g_{h}(1)^{n}]).$

Since the image of $g_{h}(1)^{n}$ under the quotient map $G\mapsto G/[G,G]$
lies inside $\Gamma/[G,G]$, it follows that

$\eta_{2}([[g_{h}(1)^{k}]^{-1},g_{h}(1)^{n}])\equiv 0\pmod{1/N}.$

Thus,

$\eta_{2}(g_{h}^{nlin}(n+k))-\eta_{2}(g_{h}^{nlin}(n))\equiv\eta_{2}(2\alpha_{h}nk)+f(k)\equiv
0\pmod{1/N}$

for any $\eta_{2}$ and some function $f$. Hence, $\alpha_{h}$ is rational with
denominator $2N$. Thus, using periodicity to scale $n$ by $2n$, we may work
with $g_{h}(2n)$ instead of $g_{h}(n)$ so we may assume that $\alpha_{h}$ is
rational with denominator $N$.

To linearize $\alpha_{h}$, we apply the linearization argument one more time,
obtaining that there exists
$\delta^{\log(1/\delta)^{O(\log\log(1/\delta))}}N^{3}$ many additive
quadruples $(h_{1},h_{2},h_{3},h_{4})$ such that

$\mathbb{E}_{n\in\mathbb{Z}/N\mathbb{Z}}e(\alpha_{h_{1}}n^{2}+\alpha_{h_{2}}(n+h_{1}-h_{4})^{2}+\beta_{h_{1},h_{2},h_{3},h_{4}}n-\alpha_{h_{3}}n^{2}-\alpha_{h_{4}}(n+h_{1}-h_{4})^{2})\geq\delta^{\log(1/\delta)^{O(1)}}$

for some phase
$\beta_{h_{1},h_{2},h_{3},h_{4}}\in\widehat{\mathbb{Z}/N\mathbb{Z}}$. This
implies that

$\alpha_{h_{1}}+\alpha_{h_{2}}\equiv\alpha_{h_{3}}+\alpha_{h_{4}}\pmod{1}.$

Arguing as above, this implies that there exists some subset
$H^{\prime}\subseteq H$ and $k\in\mathbb{Z}/N\mathbb{Z}$ such that for each
$h\in H^{\prime}$,

$\alpha_{h}=\sum_{i=1}^{d^{\prime}}a_{i}\\{\alpha_{i}(h-k)\\}$

with $(\alpha_{i})_{i=1}^{d^{\prime}}\in\widehat{\mathbb{Z}/N\mathbb{Z}}$ and
$d^{\prime}\leq\log(1/\delta)^{O(1)}$. This linearizes $\alpha_{h}$. Thus, we
have the following.

######  Lemma 8.10 (Linearization).

linearizationargument There exists a subset
$H^{\prime}\subseteq\mathbb{Z}_{N}$ of size at least
$\delta^{O(\log(1/\delta))^{O(1)}}N$ such that the following holds:

  * •

For each $h\in H^{\prime}$, there exists an associated periodic Fourier
expanded nilcharacter $\chi_{h}$ for each $h\in H^{\prime}$, $\chi_{h}$ is the
exponential of a bracket polynomial with at most $\log(1/\delta)^{O(1)}$ terms
which include

$\xi_{*}^{i}n[\xi_{h}^{j}n],\xi_{h}^{j}n[\xi_{*}^{i}n]$

and a single term of the form

$\xi_{h}^{struc}n^{2}$

where $\xi_{h}^{j}$, and $\xi_{h}^{struc}$ are of the form

$\sum_{\alpha\in S}a_{\alpha}\\{\alpha(h-k)\\}$

where $a_{\alpha}\in\mathbb{R}$, $S\subseteq\widehat{\mathbb{Z}_{N}}$ is a
subset of size at most $\log(1/\delta)^{O(1)}$, and
$\xi_{h}^{j},\xi_{h}^{struc},\xi_{*}$ are all rational with denominator $N$
and $H^{\prime}\subseteq k+B(S,\delta^{O(1)})$.

  * •

There exists some nonzero $y\in\mathbb{Z}_{N}$ such that

$|\mathbb{E}_{n\in[N]}\Delta_{h}f(yn)\chi_{h}(n)|\geq\delta^{O(\log(1/\delta))^{O(1)}}.$

Note that we may unwind the scaling of $f$ by making a change of variables
$n\mapsto pm$ where $p$ is the modular inverse of $y$. We can then absorb the
factor of $p$ in the frequencies of $\chi_{h}$.

###  8.5. Symmetry and integration argument

Thus, we have obtained that (essentially) $\Delta_{h}f(x)$222We will assume
here that we have unwinded the scaling of $\tilde{f}$ so we work with $f$.
correlates with sums of terms of the form

$\left(\sum_{i=1}^{\ell}a_{i}\\{\alpha_{i}(h-k)\\}n\right)[\beta n]$

and

$\beta n\left[\sum_{i=1}^{\ell}a_{i}\\{\alpha_{i}(h-k)\\}n\right].$

Writing $[\beta n]=\beta n-\\{\beta n\\}$, it follows up to lower order terms
modulo $1$, we may write the first one as

$\sum_{i=1}^{\ell}a_{i}\beta n^{2}\\{\alpha_{i}(h-k)\\}-\\{\beta
n\\}\sum_{i=1}^{\ell}a_{i}n\\{\alpha_{i}(h-k)\\}$

and the second one as (up to lower order terms modulo $1$)

$\\{\beta n\\}\sum_{i=1}^{\ell}a_{i}n\\{\alpha_{i}(h-k)\\}.$

The point of these computations is to illustrate that for our situation, each
of the $\alpha_{i}$’s and the $\beta$ will lie in $\widehat{\mathbb{Z}_{N}}$,
so the phases in brackets will be periodic modulo $N$. We may also translate
our set $H$ by $k$ to eliminate the $k$ term.

It follows that $\Delta_{h+k}f$ correlations with a bracket polynomial of the
form $e(3T(h,n,n)+B(n)+\theta_{h}n)$ where

$T(x,y,z):=\sum_{j=1}^{d}\\{\alpha_{j}x\\}\frac{\beta_{j}}{6}y\\{\gamma_{j}z\\}+\\{\alpha_{j}x\\}\frac{\beta_{j}}{6}z\\{\gamma_{j}y\\}+\sum_{j=1}^{d}\frac{\alpha_{j}^{\prime}}{3}\\{\beta_{j}^{\prime}x\\}yz$

with $\alpha_{j},\gamma_{j},\beta_{j}^{\prime}\in\widehat{\mathbb{Z}_{N}}$ and
$B(n)$ is a degree two bracket polynomial of at most $2d$ phases and is of the
form $B(n)=\sum_{j=1}^{d}\lambda_{j}n[\mu_{j}n]$ (and $\theta_{h}n$ should be
thought of as a “lower order term”). We wish to show that $f$ correlates with
a degree three bracket polynomial. One important observation is that this form
is trilinear on the Bohr set with frequencies
$S:=\\{1/N,\alpha_{1},\dots,\alpha_{d},\gamma_{1},\dots,\gamma_{d},\beta_{1}^{\prime},\dots,\beta_{d}^{\prime}\\}$
and radius, say $1/10$ ($1/N$ is added to $S$ to ensure that $T$ is genuinely
trilinear on the Bohr set with frequencies of $S$ and radius $1/10$).

We will now give a sketch of this step. By hypothesis, we only have local
linearity in the first variable. Let us assume for simplicity that $T$ is
trilinear. We wish to write $3T(h,n,n)$ as a combination of
$T(n+h,n+h,n+h)-T(n,n,n)$ plus lower order terms in $n$. If this can be done,
then we may absorb the $T(n,n,n)$ and the $T(n+h,n+h,n+h)$ into $f(n)$ and
$f(n+h)$, respectively, obtaining that

$\mathbb{E}_{h}\|f_{1}(n)f_{2}(n+h)\|_{U^{2}}\gg_{\epsilon}1$

for $f_{1}$ a product of $f$ and bracket cubics. We can deduce that $f_{1}$
has large $U^{3}$ norm, so applying the $U^{3}$ inverse theorem, we can
conclude the $U^{4}$ inverse theorem.

The only thing preventing us from showing this is that we have three terms
$T(h,n,n)+T(n,h,n)+T(n,n,h)$, which may not necessarily be equal. Since we
symmetrized the last two variables of $T$, we may assume that the latter two
terms are equal. It is not actually possible to show that all three terms are
equal, but rather, it is possible to show that the difference of two of them
are of “lower order,” in the sense of being a two-step in $n$ and $h$ (or one
step in $n$).

To show that $T$ is symmetric in its first two variables, we go back to the
hypothesis

$\mathbb{E}_{h}|\mathbb{E}_{n}\Delta_{h+k}f(n)\chi_{h}(n)|^{2}\geq\delta^{O(\log(1/\delta))^{O(1)}}.$

For simplicity, we will relabel the right hand side as simply $\delta$. By [8,
Proposition 6.1], it follows that

$\mathbb{E}_{h_{1}+h_{2}=h_{3}+h_{4}}|\mathbb{E}_{n}\chi_{h_{1}}(n)\chi_{h_{2}}(n+h_{1}-h_{4})\overline{\chi_{h_{3}}(n)\chi_{h_{4}}(n+h_{1}-h_{4})}|^{2}\geq\delta^{O(1)}$

or for some one-bounded function $b(h_{1},h_{2},h_{3},h_{4})$:

$\mathbb{E}_{h_{1}+h_{2}=h_{3}+h_{4}}\mathbb{E}_{n}\chi_{h_{1}}(n)\chi_{h_{2}}(n+h_{1}-h_{4})\overline{\chi_{h_{3}}(n)\chi_{h_{4}}(n+h_{1}-h_{4})}b(h_{1},h_{2},h_{3},h_{4})\geq\delta^{O(1)}$

Writing $\chi_{h}(n)=e(3T(h,n,n)+\theta_{h}n)$ and using trilinearity and
making a change of variables $(h_{1},h_{2},h_{3},h_{4})=(h,h+x+y,h+y,h+x)$, we
obtain eventually (after Pigeonholing in $h$) that

$|\mathbb{E}_{n,x,y}e(-6(T(x,y,n))b(n,x)b(n,y)b(n,x+y)b(x,y)|\gg\delta^{O(1)}$

for one-bounded functions $b$ as in Gowers’ notation [3] (where we identify
$\mathbb{Z}/N\mathbb{Z}$ with the interval $[-(N-1)/2,(N-1)/2]$). Applying
Cauchy-Schwarz in $x$ and $n$ gives

$|\mathbb{E}_{n,x,y,y^{\prime}}e(-6(T(x,y-y^{\prime},n))b(n,y^{\prime})b(n,y)b(n,x+y)b(n,x+y^{\prime})b(x,y,y^{\prime})|\gg\delta^{O(1)}.$

Making a change of variables $z=x+y+y^{\prime}$, we obtain

$|\mathbb{E}_{n,z,y,y^{\prime}}e(-6(T(z-y-y^{\prime},y-y^{\prime},n))b(n,y^{\prime})b(n,y)b(n,z-y)b(n,z-y^{\prime})b(z,y,y^{\prime})|\gg\delta^{O(1)}.$

Pigeonholing in $z$ and using trilinearity again, we obtain

$|\mathbb{E}_{n,y,y^{\prime}}e(-6(T(y,y^{\prime},n)-T(y^{\prime},y,n)))b(n,y)b(n,y^{\prime})b(y,y^{\prime})|\geq\delta^{O(1)}.$

From here, we see that these one-bounded functions are of “lower order”
compared to the top term $e(T(y,y^{\prime},n)-T(y^{\prime},y,n))$; this allows
us to conclude either with an application of the equidistribution theorem, or
via some Bohr set argument similar to [8] that
$T(y,y^{\prime},n)-T(y^{\prime},y,n)$ is “lower order” as well, implying that
$T$ is symmetric in the first two variables up to lower order. This argument
can either be made rigorous using a combination of bracket polynomial
arithmetic argument and the equidistribution theorem found here, or by a Bohr
set argument similar to the flavor of [8]. We opt for the latter approach,
since it is overall less annoying in the $U^{4}$ case though we imagine that
the other approach generalizes better than the approach we opt for.

######  Remark 8.3.

In [8], the authors work with the density assumption that there exists many
additive quadruples $(h_{1},h_{2},h_{3},h_{4})$ such that

$\mathbb{E}_{n}\chi_{h_{1}}(n)\chi_{h_{2}}(n+h_{1}-h_{4})\overline{\chi_{h_{3}}(n)\chi_{h_{4}}(n+h_{1}-h_{4})}$

is large. Because of this, they need a further tool involving the bilinear
Bogolyubov argument333The author was unable to understand their argument at
the point where they use the bilinear Bogolyubov-type theorem; however, one
can also follow their argument and use [19] to finish and obtain desirable
quantitative bounds.. We remove the use of bilinear Bogolyubov by taking
advantage of additional averaging from the hypothesis

$\mathbb{E}_{h_{1}+h_{2}=h_{3}+h_{4}}|\mathbb{E}_{n}\chi_{h_{1}}(n)\chi_{h_{2}}(n+h_{1}-h_{4})\overline{\chi_{h_{3}}(n)\chi_{h_{4}}(n+h_{1}-h_{4})}|^{2}\geq\delta^{O(1)}$

rather than the density hypothesis of additive quadruples.

We begin with the following lemma:

Thus, by applying FourierComplexity2 and onevarfouriercomplexity (or rather
the procedure of onevarfouriercomplexity) and making the above manipulations,
we may simplify

$\mathbb{E}_{h_{1}+h_{2}=h_{3}+h_{4}}|\mathbb{E}_{k,n}\chi_{h_{1}}(n)\chi_{h_{2}}(n+h_{1}-h_{4})\overline{\chi_{h_{3}}(n)\chi_{h_{4}}(n+h_{1}-h_{4})}|^{2}\geq\delta^{O(1)}$

to

$|\mathbb{E}_{n,y,y^{\prime}}e(-6(T(y,y^{\prime},n)-T(y^{\prime},y,n)))b(n,y)b(n,y^{\prime})b(y,y^{\prime})|\geq\delta^{O(d)^{O(1)}}.$

Let us relabel $y^{\prime}$ to $x$, so we instead end up with

$|\mathbb{E}_{n,y,z}e(6(T(x,y,n)-T(y,x,n)))b(n,x)b(n,y)b(x,y)|\geq\delta^{O(d)^{O(1)}}.$

####  8.5.1. Bohr sets

In the remainder of the proof, we will need to do various arithmetic
operations over Bohr sets. In this section, we formulate notation we will use
for Bohr sets.

######  Definition 8.4.

Given a subset $S\subseteq\widehat{\mathbb{Z}_{N}}$, and a real number
$\rho\in(0,1/2)$, we denote the _Bohr set_ with frequencies $S$ and radius
$\rho$ to be $B(S,\rho):=\\{x\in\mathbb{Z}_{N}:\|\alpha
x\|<\rho\forall\alpha\in S\\}$.

A Bohr set is _regular_ if whenever $\epsilon\leq\frac{1}{100|S|}$,

$|B(S,\rho)|(1-100|S|\epsilon)\leq|B(S,\rho(1+\epsilon))|\leq|B(S,\rho)|(1+100|S|\epsilon).$

It was shown by Bourgain in [1] that regular Bohr sets are ubiquitous in the
sense that there exists $\rho^{\prime}\in[\rho/2,\rho]$ such that
$B(S,\rho^{\prime})$ is regular. If $S$ and $\rho$ are specified, we will
shorten $B(S,\rho)$ to be $B$. Given a real number $\epsilon$ so that
$\epsilon\rho\in(0,1)$, we will denote by $B_{\epsilon}$ as
$B(S,\epsilon\rho)$. We will also define the “norms”

$\|n\|_{S}=\sup_{\alpha\in S}\|\alpha n\|_{\mathbb{R}/\mathbb{Z}}.$

####  8.5.2. Finishing the symmetry argument

Recall that we defined

$S=\\{1/N,\alpha_{1},\dots,\alpha_{d},\gamma_{1},\dots,\gamma_{d},\beta_{1}^{\prime},\dots,\beta_{d}^{\prime}\\}.$

Let $B=B(S,\rho)$ be the Bohr set where all of the frequencies in $B$ are the
bracket frequencies of $T$ where $\rho$ is selected in $[1/10,1/5]$ such that
$B(S,\rho)$ is regular. It follows that Pigeonholing in one of those
translations, we have for some $n_{0},x_{0},y_{0}$ that

$\sum_{n\in n_{0}+B,x\in x_{0}+B,y\in y_{0}+B}e(6(T(x,y,n)-$
$T(y,x,n)))b(n,x)b(n,y)b(x,y)|\gg N^{3}2^{-O(d)}\delta^{O(d)^{O(1)}}.$

Making a change of variables, we have

$\mathbb{E}_{n,x,y\in B}e(6(T(x-x^{0},y-y^{0},n-n_{0})$
$-T(y-y^{0},x-x^{0},n-n_{0})))b(n,x)b(n,y)b(x,y)\gg\delta^{O(d)^{O(1)}}.$

Expanding out the bracket polynomials as
$T(x-x^{0},y-y^{0},n-n_{0})=T(x,y,n)+[\text{lower order terms}]$ (with the
point of the lower order terms depending on fewer variables after applying a
Fourier complexity lemma), and similarly for $T(y-y^{0},x-x^{0},n-n_{0})$ and
applying FourierComplexity2, we therefore obtain

$\mathbb{E}_{n,x,y\in
B}e(6(T(x,y,n)-T(y,x,n)))b(n,x)b(n,y)b(x,y)|\gg\delta^{O(d)^{O(1)}}.$

Fix elements $a,b,c\in B_{1/|S|100}=B(S,\rho/|S|100)$. It then follows that if
$f$ is one-bounded, then

$\mathbb{E}_{n\in B}f(n)=\mathbb{E}_{n\in
B}\mathbb{E}_{k\in[-K,K]}f(n+ka)+O\left(K\frac{|S|\|a\|_{S}}{\rho}\right)$

whenever $K\leq\frac{\rho}{|S|\|a\|_{S}}$. We may thus write for $a,b,c\in
B_{\delta^{O(d)^{O(1)}}/100|S|}$ that

$|\mathbb{E}_{n,x,y\in
B}\mathbb{E}_{k_{1}\in[-K_{1},K_{1}],k_{2}\in[-K_{2},K_{2}],k_{3}\in[-K_{3},K_{3}]},e(6(T(x+k_{1}a,y+k_{2}b,n+k_{3}c)$
$-T(y+k_{2}b,x+k_{1}a,n+k_{3}c)))b(n+k_{3}c,x+k_{1}a)b(n+k_{3}c,y+k_{2}b)b(x+k_{1}a,y+k_{2}b)|\gg\delta^{O(d)^{O(1)}}$

for $K_{1}\leq\frac{\delta^{O(d)^{O(1)}}\rho}{\|a\|_{S}}$,
$K_{3}\leq\frac{\delta^{O(d)^{O(1)}}\rho}{\|b\|_{S}}$,
$K_{3}\leq\frac{\delta^{O(d)^{O(1)}}\rho}{\|c\|_{S}}$. We note that if $f$ is
locally linear on a Bohr set, and if $n+ka$ lies inside the Bohr set for each
$k\in[-K,K]$ (say for $K$ significantly larger than $2$), then we may write
$f(n+ka)=f(n)+kf(a)$. Thus, we may write $T(x+k_{1}a,y+k_{2}b,n+k_{3}c)$ as a
polynomial in the variables $k_{1},k_{2},k_{3}$ with top term
$k_{1}k_{2}k_{3}T(a,b,c)$ and similarly, we may write
$T(y+k_{2}b,x+k_{1}a,n+k_{3}c)$ as a polynomial in $k_{1},k_{2},k_{3}$ with
top term $k_{1}k_{2}k_{3}T(b,a,c)$. We will now Pigeonhole in values $n,x,y$
so that

$\mathbb{E}_{k_{1}\in[-K_{1},K_{1}],k_{2}\in[-K_{2},K_{2}],k_{3}\in[-K_{3},K_{3}]},e(6(T(x+k_{1}a,y+k_{2}b,n+k_{3}c)-T(y+k_{2}b,x+k_{1}a,n+k_{3}c)))$
$b(k_{1},k_{3})b(k_{1},k_{2})b(k_{2},k_{3})|\gg\delta^{O(d)^{O(1)}}.$

Thus, applying trilinearity of $T$, we obtain

$\mathbb{E}_{k_{i}\in[-K_{i},K_{i}]}e(6k_{1}k_{2}k_{3}(T(a,b,c)-T(b,a,c)))b(k_{1},k_{3})b(k_{1},k_{2})b(k_{2},k_{3})|\gg\delta^{O(d)^{O(1)}}.$

Let $\alpha=6(T(a,b,c)-T(b,a,c))$. Applying Cauchy-Schwarz three times to
eliminate all of the $b$’s gives

$|\mathbb{E}_{k_{i},k_{i}^{\prime}\in[-K_{i},K_{i}]}e(\alpha
P(k_{1},k_{2},k_{3},k_{1}^{\prime},k_{2}^{\prime},k_{3}^{\prime}))|\gg\delta^{O(d)^{O(1)}}$

where

$P(k_{1},k_{2},k_{3},k_{1}^{\prime},k_{2}^{\prime},k_{3}^{\prime})=k_{1}k_{2}k_{3}-k_{1}^{\prime}k_{2}k_{3}-k_{1}k_{2}^{\prime}k_{3}-k_{1}k_{2}k_{3}^{\prime}+k_{1}^{\prime}k_{2}^{\prime}k_{3}+k_{1}^{\prime}k_{2}k_{3}^{\prime}+k_{1}k_{2}^{\prime}k_{3}^{\prime}-k_{1}^{\prime}k_{2}^{\prime}k_{3}^{\prime}.$

Pigeonholing in $k_{1}^{\prime},k_{2}^{\prime},k_{3}^{\prime}$, we obtain

$|\mathbb{E}_{k_{i}\in[-K_{i},K_{i}]}e(\alpha k_{1}k_{2}k_{3}+[\text{Lower
Order Terms}])|\gg\delta^{O(d)^{O(1)}}.$

This gives us by multidimensional polynomial equidistribution theorem [23,
Proposition 7] that there exists some $q=q_{a,b,c}\leq\delta^{-O(d)^{O(1)}}$
such that

$\|q\alpha\|_{\mathbb{R}/\mathbb{Z}}\ll\frac{\delta^{-O(d)^{O(1)}}}{K_{1}K_{2}K_{3}}.$

This implies via a geometry of numbers argument as in [6, Lemma 11.4] or in
[14, Lemma 7.5] that denoting $\epsilon=\delta^{O(d)^{O(1)}}$ that if
$a,b,c\in B_{\epsilon^{O(d)^{O(1)}}}$, then for some $q\leq\epsilon^{-1}$
independent of $a,b,c$, that

$\|6q(T(a,b,c)-T(b,c,a))\|_{\mathbb{R}/\mathbb{Z}}\leq\|a\|_{S}\|b\|_{S}\|c\|_{S}\delta^{-O(d)^{O(1)}}.$

This gives the symmetry result. The rest, now, is putting everything together.

####  8.5.3. Integrating the result

We go back to the hypothesis

$\mathbb{E}_{h}|\mathbb{E}_{n\in\mathbb{Z}_{N}}\Delta_{h+k}f(n)\chi_{h}(n)|^{2}\geq\delta^{O(d)^{O(1)}}.$

We first claim that there exists some $h_{0}\in H$ such that
$H\cap(h_{0}+B_{\delta^{O(1)}})$ has size at least $\delta^{O(d)^{O(1)}}N$. To
show this, we observe (following [8, p. 33]) that

$\sum_{n\in[N]}1_{H}*1_{B^{\prime}}*1_{B^{\prime}}(n)1_{H}(n)=\sum_{n\in[N]}(1_{H}*1_{B^{\prime}}(n))^{2}\geq\left(\sum_{n\in[N]}1_{H}*1_{B^{\prime}}(n)\right)^{2}/N\geq\delta\rho_{1}^{2d}N^{3}$

with $B^{\prime}=B_{\delta^{O(1)}/2}$. On the other hand, we have that
$1_{B^{\prime}}*1_{B^{\prime}}(n)\leq|B_{\delta^{O(1)}}|1_{B_{\delta^{O(1)}}}(n)\leq
N1_{B_{\delta^{O(1)}}}(n)$. Hence, by the Pigeonhole principle, such $h_{0}$
exists. Thus, taking $H^{\prime}=(H-h_{0})\cap B$, it follows that for each
$h^{\prime}\in H^{\prime}$,

$\mathbb{E}_{h^{\prime}\in
B_{\delta^{O(1)}}}|\mathbb{E}_{n}\overline{f(n)}f(n+k+h_{0}+h^{\prime})e(3T(h_{0}+h^{\prime},n,n)+\theta_{h_{0}+h^{\prime}}n)|^{2}\geq\delta.$

We may use local trilinearity of $T$ and relabeling $\overline{f}=f_{1}$ and
$f_{2}=f(h_{0}+k+\cdot)$, we have (after adjusting $\theta$ a bit)

$\mathbb{E}_{h\in
B_{\delta^{O(1)}}}|\mathbb{E}_{n}f_{1}(n)f_{2}(n+h)e(3T(h,n,n)+\theta_{h}n)|^{2}\geq\delta^{O(d)^{O(1)}}.$

Pigeonoling $n$ to be in a Bohr set $B_{\delta^{O(1)}}$ and adjusting the
radius so that it is regular, we have by the various bracket polynomial
manipulations from previous sections that for some phases
$\tilde{\theta}_{h}\in\widehat{\mathbb{Z}_{N}}$,

$\mathbb{E}_{h}|\mathbb{E}_{n\in
B_{\delta^{O(1)}}}\tilde{f}_{1}(n)\tilde{f}_{2}(n+h)e(3T(h,n,n)+\tilde{\theta}_{h}n)|^{2}\geq\delta^{O(d)^{O(1)}}$

where $\tilde{f}_{i}$ are products of $f$ and at most $O(d)$ many degree $\leq
2$ bracket polynomials which are periodic in $n$ and $h$ modulo $N$.
Pigeonholing in $n$ and $h$ in a smaller Bohr set $B_{\delta^{O(d)^{O(1)}}}$
gives

$\mathbb{E}_{h\in B_{\delta^{O(d)^{O(1)}}}}|\mathbb{E}_{n\in
B_{\delta^{O(d)^{O(1)}}}}\tilde{f}_{1}(n+n_{0}+h+h_{0})\tilde{f}_{2}(n+n_{0})e(3T(h+h_{0},n+n_{0},n+n_{0})+\tilde{\theta_{h}}^{1}n)|^{2}\geq\delta^{O(d)^{O(1)}}.$

The point is that on $B_{\delta^{O(1)}}$, $T$ is genuinely trilinear, so by
FourierComplexity2, we may write
$3T(h+h_{0},n+n_{0},n+n_{0})=3T(h,n+n_{0},n+n_{0})$ plus a lower order bracket
quadratic term in $n$, which we can absorb in $\tilde{\theta_{h}}^{1}$ and in
$\tilde{f}_{1}$. We may also write
$3T(h,n+n_{0},n+n_{0})=3T(h,n,n)+3T(h,n_{0},n)+3T(h,n,n_{0})+3T(h,n_{0},n_{0})$,
but noting that $T$ is symmetric in the last two variables, we have

$3T(h,n_{0},n)+3T(h,n,n_{0})=3T(n+h,n+h,n_{0})-3T(n,n,n_{0})-3T(h,h,n_{0}).$

In addition, using that $6q(T(h,n,n)-T(n,h,n))\equiv
O(\delta^{O(d)^{O(1)}})\pmod{1}$, it follows that

$6qT(h,n,n)\equiv 2q(T(n+h,n+h,n+h)-T(n,n,n)-T(h,h,h)-T(h,n,h)$
$-T(n,h,h)-T(h,h,n))+O(\delta^{O(d)^{O(1)}})\pmod{1}.$

This suggests that we should rewrite the argument as follows: let
$\ell\equiv(6q)^{-1}\pmod{N}$. We start with

$\mathbb{E}_{h}|\mathbb{E}_{n}\Delta_{h}f(n)\chi_{h}(n)|^{2}\geq\delta^{O(d)^{O(1)}}.$

Instead of Pigeonholing in $B_{\delta^{O(1)}}$ By Pigeonholing on a translate
of $\ell^{-1}B_{\delta^{O(1)}}$, we obtain:

$\mathbb{E}_{h}|\mathbb{E}_{n\in\ell^{-1}B_{\delta^{O(1)}}}\tilde{f}_{1}(n)\tilde{f}_{2}(n+h)e(3T(6q\ell
h,6q\ell n,6q\ell n)+\tilde{\theta}_{h}n)|^{2}\gg\delta^{O(d)^{O(1)}}.$

We may then argue as before, finally obtaining $e((6q)^{3}3T(\ell h,\ell
n,\ell
n))=e(\tilde{T}(n+h,n+h,n+h)-\tilde{T}(n,n,n)+\tilde{\theta}_{h}^{3}n+\alpha)+O(\delta^{O(d)^{O(1)}})$.
Absorbing the $n+h$ terms into $f(n+h+n_{0}+h_{0})$ and the $n$ terms into
$f(n+n_{0})$ and applying trivialfouriercomplexity on the terms
$\tilde{T}(n,h,h)$, $\tilde{T}(h,n,h)$, and $\tilde{T}(h,h,n)$, we obtain

$\mathbb{E}_{h}\|F_{1}(n+h)F_{2}(n)\|_{U^{2}([N])}^{2}\geq\delta^{O(d)^{O(1)}}$

for functions $F_{1}$ and $F_{2}$ where $F_{2}$ is a product of $f$ and $O(d)$
many degree $\leq 3$ bracket polynomials. Using the Cauchy-Schwarz-Gowers
inequality, combined with the results above on three-step nilmanifold
constructions gives us that there exists some approximate degree $\leq 3$
nilsequence $F(g(n)\Gamma)$ of dimension at most $O(d)^{O(1)}$ and complexity
at most $\delta^{-O(d)^{O(1)}}$ such that

$|\mathbb{E}_{n\in[N]}\Delta_{h}f(n)F(g(n)\Gamma)|\geq\delta^{O(d)^{O(1)}}.$

We may also smooth out $F1_{B}$ as follows: writing
$1_{B_{\delta^{O(d)^{O(1)}}}}(n)=1_{U}((\alpha n)_{\alpha\in S})$ where $U$ is
the open set
$\\{\|x_{i}\|_{\mathbb{R}/\mathbb{Z}}<\rho\delta^{O(d)^{O(1)}}\\}$ where
$B=B(S,\rho)$, we let $\phi$ be a smooth cutoff function on
$\mathbb{R}^{|S|}/\mathbb{Z}^{|S|}$ supported on an $\epsilon$-neighborhood of
$U$. By regularity, (assuming $\epsilon$ is sufficiently small)
$\phi(n)F(g(n)\Gamma)=1_{B}(n)F(g(n)\Gamma)+O_{L^{1}[N]}(\epsilon)$. One can
check that $\phi(n)F(g(n)\Gamma)$ is smooth on a three-step nilmanifold of
complexity $O(1)$ and $\phi$ can be chosen in a way so that
$\phi(n)F(g(n)\Gamma)$ has Lipschitz parameter at most $O(d\epsilon^{-1})$.
Letting $\epsilon=\delta^{O(d)^{O(1)}}$, we obtain the desired correlation
with a Lipschitz-smooth nilsequence of parameter at most
$\delta^{-O(d)^{O(1)}}$. One can then divide by the Lipschitz constant to
ensure a Lipschitz parameter of $1$.

Substituting $\delta$ with $\delta^{O(\log(1/\delta))^{O(1)}}$ and $d$ with
$O(\log(1/\delta))^{O(1)}$ gives us mainresult4.

##  Appendix A Further auxiliary lemmas

In this section, we shall state auxiliary lemmas we use in the proof of our
main theorem. Most of these results come from [7]. The first two lemmas are
similar to [7, Proposition 9.2] and [7, Lemma 7.9], respectively.

######  Lemma A.1 (Factorization lemma I).

factorization Let $G/\Gamma$ be a nilmanifold of dimension $d$, complexity
$M$, and degree $k$ and let $g\in\mathrm{poly}(\mathbb{Z},G)$ with
$g(n)\Gamma$ be $N$-periodic. Suppose $\eta_{1},\dots,\eta_{r}$ are a set of
linearly independent nonzero horizontal characters of size at most $L$ with
$\|\eta_{i}\circ g\|_{C^{\infty}[N]}=0$ for each character $i$. Then there
exists a factorization $g(n)=\epsilon(n)g_{1}(n)\gamma(n)$ where $\epsilon$ is
constant, $g_{1}$ is a polynomial sequence in

$\tilde{G}=\bigcap_{i=1}^{r}\operatorname{ker}(\eta_{i}),$

and $\gamma\in\mathrm{poly}(\mathbb{Z},G)$ is a
$(ML)^{O_{k}(d^{O_{k}(1)})}$-rational. If $g(0)=\mathrm{id}_{G}$, then we may
take and $\epsilon(0)=\gamma(0)=\mathrm{id}_{G}$.

###### Proof.

By setting $\epsilon(n)=g(0)$, we may work with the assumption that
$g(0)=\mathrm{id}_{G}$. We may thus write in coordinates that

$\psi(g(n))=\sum_{i}{n\choose i}t_{i}$

where $t_{i}$ are vectors representing the coordinates of the degree $i$
component of $g$ in Mal’cev coordinates. By Cramer’s rule, we may pick a
rational vector $v$ with height at most $(ML)^{O(d^{2})}$ such that
$\eta_{i}\cdot v=\eta_{i}\cdot\psi(g(n))$. We define a polynomial sequence
$\gamma$ with

$\psi(\gamma(n))=\sum_{i\geq 1}{n\choose i}v_{i}.$

Thus, the polynomial sequence $g_{1}(n):=g(n)\gamma(n)^{-1}$ lies inside
$\tilde{G}$ and by construction $\gamma(n)\Gamma$ is
$(ML)^{O_{k}(d)^{O_{k}(1)}}$-rational. ∎

Before we state the next lemma, we recall the definition of $g_{2}$ from [13,
Definition 4.1] via given a polynomial sequence
$g\in\mathrm{poly}(\mathbb{Z},G)$, we define $g_{2}(n):=g(n)g(1)^{-n}$.

######  Lemma A.2 (Factorization lemma II).

factorization2 Let $G/\Gamma$ be a nilmanifold of dimension $d$, complexity
$M$, and degree $k$ and let $g\in\mathrm{poly}(\mathbb{Z},G)$ with
$g(n)\Gamma$ be $N$-periodic. Suppose $\eta_{1},\dots,\eta_{r}$ are a set of
linearly independent nonzero horizontal characters on $G_{2}$ which annihilate
$[G,G]$ of size at most $L$ with $\|\eta_{i}\circ g_{2}\|_{C^{\infty}[N]}=0$
for each character $i$. Then we may write $g(n)=\epsilon(n)g_{1}(n)\gamma(n)$
where $\epsilon$ is constant, $g_{1}(n)\in\mathrm{poly}(\mathbb{Z},\tilde{G})$
with $\tilde{G}$ given the filtration

$\tilde{G}_{0}=\tilde{G}_{1}=G,\tilde{G}_{2}=\bigcap_{i=1}^{r}\operatorname{ker}(\eta_{i}),\text{
and }\tilde{G}_{i}=\tilde{G}_{2}\cap G_{i}$

for all $i\geq 2$, and $\gamma$ is $(ML)^{O_{k}(d^{O(1)})}$-rational, and
$g_{1}(0)=\gamma(0)=1$.

###### Proof.

By setting $\epsilon(n)=g(0)$, we may assume that $g(0)=\mathrm{id}_{G}$. We
write in Mal’cev coordinates that

$\psi_{G_{2}}(g_{2}(n))=\sum_{i\geq 2}{n\choose i}t_{i}$

where $t_{i}$ are vectors representing the coordinates of the degree $i$
component of $g$ in Mal’cev coordinates. By Cramer’s rule, we may pick a
rational vector $v$ in $G_{2}$ with height at most $(ML)^{O(r)^{2}}$ such that
$\eta_{i}\cdot v=\eta_{i}\cdot\psi(g(n))$ and such that the linear component
of $v$, i.e., the first $d-d_{1}$ components when written as Mal’cev bases, is
zero. We define $\gamma$ via

$\psi(\gamma(n))=\sum_{i\geq 2}{n\choose i}v_{i}.$

By construction, $\gamma$ is $(ML)^{O_{k}(d^{O_{k}(1)})}$-rational. We now
define $g_{1}(n)=g(n)\gamma(n)^{-1}$. We observe that

$g_{1,2}(n)=g_{1}(n)g_{1}(1)^{-n}=g_{2}(n)\gamma(n)^{-1}\pmod{[G,G]}$

so $g_{1}(n)\in\mathrm{poly}(\mathbb{Z},\tilde{G})$ as desired. ∎

######  Lemma A.3 (Removing the Rational Term).

removerational Suppose $N$ is prime and $Q$ is an integer. Suppose $G/\Gamma$