# A Quantitative Bound For Szemerédi’s Theorem for a Complexity One Polynomial
Progression over $\mathbb{Z}/N\mathbb{Z}$

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

Let $N$ be a large prime and $P,Q\in\mathbb{Z}[x]$ two linearly independent
polynomials with $P(0)=Q(0)=0$. We show that if a subset $A$ of
$\mathbb{Z}/N\mathbb{Z}$ lacks a progression of a form of
$(x,x+P(y),x+Q(y),x+P(y)+Q(y))$, then

$|A|\leq O\left(\frac{N}{\log_{(O(1))}(N)}\right)$

where $\log_{C}(N)$ is an iterated logarithm of order $C$ (e.g.,
$\log_{2}(N)=\log\log(N)$). To establish this bound, we adapt Peluse’s (2018)
degree lowering argument to the quadratic Fourier analysis setting to obtain
quantitative bounds on the true complexity of the above progression. Our
method also shows that for a large class of polynomial progressions, if one
can establish polynomial-type bounds on the true complexity of those
progressions, then one can establish polynomial-type bounds on Szemerédi’s
theorem for that type of polynomial progression.

##  1\. Introduction

Szemerédi’s theorem states that given $k$ and any subset $S$ of the natural
numbers with positive upper density, there exists a $k$-term arithmetic
progression in $S$. The $k=3$ case of Szeméredi’s theorem was proved in 1953
by Roth [R] using Fourier analysis and the density increment argument. The
general case was first proved in 1975 by Szemerédi [S]. Shortly after,
Furstenberg [F] gave a proof using ergodic theory in 1977. In 1998, Timothy
Gowers [G2] gave a proof in the similar spirit as Roth, also using Fourier
analysis and the density increment argument as well as introducing what is now
known as the field higher order fourier analysis. New proofs of Szemerédi’s
theorem were given by Green and Tao [GT3] using higher order Fourier analysis.

###  1.1. Polynomial Progressions

Beyond Szemerédi’s theorem, one can ask a similar question about polynomial
progressions, rather than linear progressions. For instance, if a subset of
the natural numbers has positive density, then does it necessarily have to
contain the progression of the form $(x,x+y,x+y^{2})$? This was answered
affirmatively by Furstenberg and Weiss [FW], whose proof followed
Furstenberg’s ergodic theoretic techniques. Later, Bergelson and Liebman [BL]
generalized this to essentially all polynomial ergodic averages. A key
disadvantage to ergodic theoretic proofs is that they don’t obviously give
quantitative bounds, and though they can be rephrased to give quantitative
bounds, those bounds are usually very poor.

In a related problem, one can ask if $\mathbb{Z}/N\mathbb{Z}$ doesn’t contain
a progression of the form $(x,x+y,x+y^{2})$, then how large can it be?
Bourgain and Chang [BC] proved that if $N$ is prime, such a set can be of size
at most $N^{1-\delta}$ for some positive $\delta>0$. Dong, Li, and Sawin [DLS]
subsequently proved that a similar result as Bourgain and Chang but with $y$
and $y^{2}$ replaced by two linearly independent polynomials $P_{1}(y)$ and
$P_{2}(y)$ with $P_{1}(0)=P_{2}(0)=0$. In a breakthrough paper in 2019, Peluse
[P1] showed using a degree lowering strategy that for $P_{i}$ that are
linearly independent such that $P_{i}(0)=0$, and if a subset $S$ doesn’t
contain a progression of the form $(x,x+P_{1}(y),\dots,x+P_{n}(y))$, then
$|S|\leq N^{1-\gamma}$ for some $\gamma>0$ that only depends on
$P_{1},\dots,P_{n}$.

Peluse’s method was later adapted by Peluse and Prendiville [PP1], [PP2] and
by Peluse [P2] in the integer case, where they were able to give a Fourier
analytic and density increment proof of the following: if $P_{1},\dots,P_{n}$
have distinct degree and $P_{1}(0)=\cdots=P_{n}(0)=0$, and a subset of
$\\{1,\dots,N\\}$ doesn’t contain a progression of the form
$(x,x+P_{1}(y),\dots,x+P_{n}(y))$, then it has size at most
$\frac{N}{\log\log(N)^{c}}$ for some constant $c$ depending only on the
polynomials. A key difference between the integer case and the
$\mathbb{Z}/N\mathbb{Z}$ case is the uneven averaging between $x$ and $y$: in
the integer case, one averages along $x$ from $1$ to $N$ and along $y$ from
$1$ to $\min_{i}N^{1/\deg{P_{i}}}$. This is in essence why the integer case
was only adapted towards polynomials with distinct degree rather than all
linearly independent polynomials.

For the $\mathbb{Z}/N\mathbb{Z}$ case of the problem, some non-linearly
independent and multi-dimensional progressions were studied by Kuca [K3],
[K4], both relying on the degree lowering method.

###  1.2. The True Complexity Problem

A problem related to the above body of work is the true complexity problem. In
his proof of Szemerédi’s theorem [G2], Gowers showed that

$\mathbb{E}_{x,y\in\mathbb{Z}/N\mathbb{Z}}f_{1}(x)f_{2}(x+y)f_{3}(x+2y)\cdots
f_{k}(x+(k-1)y)\leq\|f_{i}\|_{U^{k-1}}$

for all $k\geq 1$ where $\|\cdot\|_{U^{s}}$ is the Gowers $U^{s}$ norm, and
$\mathbb{E}$ an expectation (see section 2 for definitions). More generally,
given vector spaces $V,W$ over a finite field and linear forms
$\phi_{1},\dots,\phi_{\ell}:V\to W$, $f_{i}:W\to\mathbb{C}$ one-bounded
functions, one can ask the following:

######  Question.

For each $1\leq j\leq\ell$, does there exist $s$ and some positive function
$c$, which only depends on the linear forms $(\phi_{i})_{i=1}^{\ell}$ that
goes to zero as its parameter goes to zero such that

$|\mathbb{E}_{v\in V}\prod_{i=1}^{\ell}f_{i}(\phi_{i}(v))|\leq
c(\|f_{j}\|_{U^{s}})?$

######  Question.

If such $s$ and $c$ exist, what is the smallest value of $s$ for which this
occurs?

Green and Tao showed in [GT4] that such an $s$ exists with $c$ some
polynomial. Gowers and Wolf [GW1], [GW2] observed that if $P$ is some
$\ell$-variable polynomial with no multivariate monomials such that
$P(\phi_{1},\dots,\phi_{\ell})=0$, then $s$ is lower bounded by the
$\deg_{x_{j}}(P)+1$, where $\deg_{x_{j}}(P)$ is the $x_{j}$ degree of $P$, and
thus conjectured and proved in a large number of cases that such an $s$ is the
smallest value of $s$. This conjecture was proven to be true in all cases by
the combined work of [GW1], [GW2], [GW3] [GT3], [A]. Recently, Manners [M]
gave an “elementary” proof yielding polynomial bounds for the true complexity
conjecture for a large family of cases.

As with Szemerédi’s Theorem, one may ask a similar true complexity problem for
polynomial progressions. Kuca [K1], [K2] used Green and Tao’s arithmetic
regularity lemma [GT3] on the true complexity problem for polynomial
progressions.

###  1.3. Main New Results

Let $P,Q\in\mathbb{Z}[x]$ be linearly independent polynomials, with
$P(0)=Q(0)=0$,

$\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)),$
$\Lambda^{1}(f,g,k,p)=\mathbb{E}_{x,y,z}f(x)g(x+y)k(x+z)p(x+y+z).$

A special case of Kuca’s work is the following (see section 2 for notation):

######  Theorem 1 ([K1, Theorem 1.3]).

kuca1 If $f,g,k,p:\mathbb{Z}/N\mathbb{Z}\to\mathbb{C}$ are one-bounded and

$|\Lambda(f,g,k,p)|\geq\delta$

then there exists $c_{P,Q}(\delta)>0$ such that

$\|f\|_{U^{2}}\geq c(\delta).$

and that

######  Theorem 2 ([K1, Theorem 9.1]).

kuca2 Let $f,g,k,p:\mathbb{Z}/N\mathbb{Z}\to\mathbb{C}$. Then

$\Lambda(f,g,k,p)=\Lambda^{1}(f,g,k,p)+o_{N\to\infty}(1).$

We will show the following:

######  Theorem 3.

count Let $N$ be a prime and
$f,g,k,p\colon\mathbb{Z}/N\mathbb{Z}\to\mathbb{C}$ are one-bounded. Then

$\Lambda(f,g,k,p)=\Lambda^{1}(f,g,k,p)+O\left(\frac{1}{\log_{(O(1))}(N)}\right).$

To prove this, we prove

######  Theorem 4.

gowers Suppose $N$ is a prime,
$f,g,k,p\colon\mathbb{Z}/N\mathbb{Z}\to\mathbb{C}$ are one-bounded, and
$|\Lambda(f,g,k,p)\geq\epsilon$. Then either
$\epsilon\ll\frac{1}{\log_{(O(1))}(N)}$ or

$\|p\|_{U^{2}}\geq c(\epsilon).$

where $c(x)=1/\exp_{O(1)}(x^{-1})$ is an iterated exponential which iterates
$O(1)$ times.

Usually, to prove quantitative bounds on Szemerédi-type theorems, one proves a
Gowers uniformity estimate combined with the density increment argument. One
can prove Gowers uniformity estimates for polynomials. However, as observed in
[Pr2], it can be difficult to adapt the density increment argument to
polynomials, and it’s not clear how any Gowers uniformity estimate, other than
a $U^{1}$ type estimate can help control progressions on polynomials. One can
view count and the work of Frantzikinakis, Peluse, Prendiville, Kuca [Fr1],
[P1], [P2], [PP1], [PP2], [K3], [K4] as suggesting that the role of Gowers
uniformity estimates in polynomial progressions is to facilitate the reduction
of quantitatively counting polynomial progressions by analogous linear
progressions, and then quantitatively counting those linear progressions using
tools we already have. However, the reduction towards counting a linear
progression turns out to require Gowers uniformity estimates of low
uniformity. For instance, Peluse [P1] required a $U^{1}$ type estimate to
prove the main theorem, and it turns out that our proof of count will require
a $U^{2}$ type bound such as gowers.

In fact, we will show via a weak regularity lemma that gowers implies count.
Our strategy for the proof of gowers follows Peluse’s degree lowering
strategy, adapted using the $U^{3}$ inverse theorem of Green and Tao [GT1] in
place of the $U^{2}$ inverse theorem.

Note that an immediate corollary of count is

######  Corollary.

Suppose a subset $A$ of $\mathbb{Z}/N\mathbb{Z}$ lacks progressions of the
form $(x,x+P(y),x+Q(y),x+P(y)+Q(y))$. Then
$|A|\leq\frac{N}{\log_{(O(1))}(N)}$.

###### Proof.

Applying count to $f=g=k=p=1_{A}$, it follows that
$\Lambda(f,g,k,p)=\|1_{A}\|_{U^{2}}^{4}+O(1/\log_{(O(1))}N)$. Let $\delta$ be
the density of $A$. Then using the fact that

$\delta=\|1_{A}\|_{U^{1}}\leq\|1_{A}\|_{U^{2}}$

it follows that if $\Lambda>0$, then $\|1_{A}\|_{U^{2}}\leq
O\left(\frac{1}{\log_{(O(1))}(N)}\right)$ implying that

$\delta\leq O\left(\frac{1}{\log_{(O(1))}(N)}\right).$

∎

Another corollary is the following:

######  Corollary (Borys Kuca private communication, see also [K1, Proposition
12.9]).

Coro Suppose that

$|\mathbb{E}_{x,y}f(x)g(x+y)k(x+2y)p(x+y^{2})|\geq\epsilon.$

Then either $\epsilon\ll\frac{1}{\log_{O(1)}(N)}$ or

$\min(\|f\|_{U^{2}},\|g\|_{U^{2}},\|k\|_{U^{2}},\|p\|_{u^{3}})\geq
1/\exp_{O(1)}(\epsilon^{-1})$

where

$\|p\|_{u^{3}}=\sup_{\alpha,\beta}|\mathbb{E}_{x}p(x)e(\alpha x^{2}+\beta
x)|.$

Although our proof is written in terms of nilsequences, one can in principle
write the argument entirely in terms of bracket polynomials (which we outline
in section 3) and use much of the bracket polynomial arithmetic done in [GT5].

###  1.4. Further Work

kuca1 and kuca2 are actually special cases of Kuca’s results in [K1] and [K2].
Kuca was able to prove the following: if $(x+P_{1}(y),\dots,x+P_{n}(y))$ is a
zero set of a homogeneous polynomial, that is, there exists
$(a_{i})_{i=1}^{n}$, and $d$ such that $\sum_{i}a_{i}(x+P_{i}(y))^{d}=0$, then
the quantitative count is controlled by the true complexity of the polynomial
progression $(x+P_{1}(y),\dots,x+P_{n}(y))$. We believe that the methods here
extend towards analogous results as count as those found in [K1] for
polynomial patterns of true complexity one, among other progressions
considered by Kuca. For example, we conjecture that somewhat similar methods
to the methods in this paper can be used to establish the following:

######  Conjecture 1.

conj1 Let $P_{1},\dots,P_{s}\in\mathbb{Z}[x]$ be linearly independent
polynomials that vanish at zero. Let
$f_{\omega}:\mathbb{Z}/N\mathbb{Z}\to\mathbb{C}$ be one-bounded functions for
each $\omega\in\\{0,1\\}^{s}$. Let $0\leq t\leq s$ natural numbers. Then

$\mathbb{E}_{x,y}\prod_{\omega\in\\{0,1\\}^{s}:|\omega|=t}f_{\omega}(x+\omega\cdot
P(y))=\mathbb{E}_{x,h_{1},\dots,h_{s}}\prod_{\omega\in\\{0,1\\}^{s}:|\omega|\leq
t}f_{\omega}(x+\omega\cdot h)+O\left(\frac{1}{\log_{(O(1))}(N)}\right).$

Here, $P(y)=(P_{1}(y),P_{2}(y),\dots,P_{s}(y))$,
$\omega=(\omega_{1},\dots,\omega_{s})$, and $\omega\cdot
P(y)=\sum_{i=1}^{s}\omega_{i}P_{i}(y)$.

######  Conjecture 2.

conj2 Let $P_{1},\dots,P_{s}\in\mathbb{Z}[x]$ be linearly independent
polynomials that vanish at zero. Let
$f_{\omega}:\mathbb{Z}/N\mathbb{Z}\to\mathbb{C}$ be one-bounded functions. Let

$\Lambda_{s,t}(f_{\omega})=\mathbb{E}_{x,y}\prod_{\omega\in\\{0,1\\}^{s}:|\omega|\leq
t}f_{\omega}(x+\omega\cdot P(y)).$

Suppose

$|\Lambda_{s,t}(f_{\omega})|\geq\delta.$

Then either

$\delta\leq 1/\log_{O(1)}(N)$

or

$\|f_{\omega}\|\geq 1/\exp_{O(1)}(\delta^{-1}).$

A corollary of conj1 is the following:

######  Conjecture 3.

conj3 Let $P_{1},\dots,P_{s}\in\mathbb{Z}[x]$ be linearly independent
polynomials that vanish at zero. Suppose a subset
$A\subseteq\mathbb{Z}/N\mathbb{Z}$ lacks the progression $(x+\omega\cdot
P(y))_{\omega\in\\{0,1\\}^{s}:|\omega|\leq t}$ with $y$ nonzero. Then

$|A|\leq O\left(\frac{N}{\log_{O(1)}(N)}\right).$

###### Proof assuming conj1.

Letting $f_{\omega}=1_{A}$, we obtain that

$\mathbb{E}_{x,y}\prod_{\omega\in\\{0,1\\}^{s}:|\omega|=t}f_{\omega}(x+\omega\cdot
P)\geq\|1_{A}\|_{U^{s}}^{2^{s}}+O\left(\frac{1}{\log_{(O(1))}(N)}\right)\geq\|1_{A}\|_{U^{1}}^{2^{s}}+O\left(\frac{1}{\log_{(O(1))}(N)}\right)$

which immediately implies that

$|A|\leq O\left(\frac{N}{\log_{O(1)}(N)}\right).$

∎

We shall prove in section 4 that conj2 implies conj1. It seems of interest to
locate an argument similar to [M] for polynomial progressions of true
complexity at least 1, which would possibly yield a polynomial type bound on
the Gowers uniformity estimate, proving conj2 or gowers but with polynomial
bounds, and thus getting polynomial bounds for the errors in conj1 and count.

In addition to the discrete setting, the degree lowering argument has been
adapted by [Fr2] and [BM] in the ergodic setting. It seems of interest to know
whether the higher order analogue of degree lowering as in this paper
generalizes in the ergodic setting.

###  1.5. Bounds

As we iteratively apply the $U^{3}$ inverse theorem, our bounds for the true
complexity problem are in nature iterated exponential (which results in
iterated logarithm bound for the Szemerédi type theorem). Each iteration of
the degree lowering argument results in two additional iterated logarithms. As
an example, if $P(y)=y$ and $Q(y)=y^{2}$, then the bound has roughly $10$
logarithms. If $P(y)=y^{2}$ and $Q(y)=y^{3}$, then the bound has roughly $64$
logarithms. Even if we have a polynomial or a quasi-polynomial type bound on
the $U^{3}$ inverse theorem with $\log(\delta^{-1})^{O(1)}$ type bound on the
dimension of the nilmanifold, our bounds would still likely to be iterated
exponential because our equidistribution lemma (equidistribution) is too
inefficient: since the number of times we apply the van der Corput lemma is on
the order of the dimension of the nilmanifold, the bounds end up being double
exponential in the dimension of the nilmanifold. If the bounds were only
single exponential in the dimension of the nilmanifold (i.e. used a more
efficient way to prove equidistribution results for bracket polynomials), and
if there were polynomial or quasi-polynomial bounds on the $U^{3}$ inverse
theorem with $\log(\delta^{-1})^{O(1)}$-type bound on the dimension, we would
obtain quasi-polynomial type bounds for our main theorems. We hope to address
this issue in future work.

###  1.6. Acknowledgements

We would like to thank Terence Tao for valuable guidance and detailed comments
on previous drafts, Tim Austin, Jaume de Dios, Asgar Jamneshan, Redmond
McNamara, Minghao Pan, and Rushil Raghavan for helpful comments and
conversations, and Raymond Chu for encouragement. Thanks also to Borys Kuca
for helpful comments and bringing the author’s attention to Coro. The author
is supported by the National Science Foundation Graduate Research Fellowship
Program under Grant No. DGE-2034835.

##  2\. Notation

In this document, we use the following conventions.

  * •

$N$ is a very large prime.

  * •

If $A$ is a set and $f:A\to\mathbb{C}$, then $\mathbb{E}_{x\in
A}f=\frac{1}{|A|}\sum_{x\in A}f(x)$. If $A$ is not specified, then the
expectation is meant to be over $\mathbb{Z}/N\mathbb{Z}$.

  * •

We will often shorthand $\mathbb{E}_{h_{1},h_{2},\dots,h_{s}}=\mathbb{E}_{h}$.

  * •

$\widehat{\mathbb{Z}/N\mathbb{Z}}$ will consist of phases $\xi\in
S^{1}=\\{z\in\mathbb{C}:|z|=1\\}$ with denominator $N$.

  * •

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

  * •

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

  * •

The discrete Fourier transform is defined as
$\hat{f}(\xi)=\mathbb{E}_{x}f(x)e^{2\pi ix\xi}$.

  * •

$\|\hat{f}\|_{\ell^{1}}=\sum_{\xi\in\widehat{\mathbb{Z}/N\mathbb{Z}}}|\hat{f}(\xi)|$.

  * •

$e(x)=e^{2\pi ix}$.

  * •

We say that $f=O(g)$, $f\ll g$, $g\gg f$ if $f\leq Cg$ for some constant $C$.
We also write $f\sim g$ if $C_{1}f\leq g\leq C_{2}f$ for positive constants
$C_{1},C_{2}$.

  * •

$O(1)$ can and will depend on the Gowers uniformity parameter $s$ in $U^{s}$
(defined below) and the specific polynomial progression considered. It will
not depend on anything else.

  * •

$\log_{(O(1))}$ is an iterated logarithm iterated $O(1)$ times. Likewise,
$\exp_{O(1)}(x)$ is an exponential function iterated $O(1)$ times.

  * •

If $f:\mathbb{Z}/N\mathbb{Z}\to\mathbb{C}$ is a function and
$\alpha\in\mathbb{C}$, then $\Delta_{\alpha}f(x)=\overline{f(x+\alpha})f(x)$.

  * •

If $f:\mathbb{Z}/N\mathbb{Z}\to\mathbb{C}$ is a function, and
$h=(h_{1},\dots,h_{s})$ a vector, we define

$\Delta_{h}f=\Delta_{h_{1}}\Delta_{h_{2}}\cdots\Delta_{h_{s}}f$

  * •

If $f:\mathbb{Z}/N\mathbb{C}\to\mathbb{C}$ is a function, we define

$\|f\|_{L^{p}}=\left(\mathbb{E}_{x\in\mathbb{Z}/N\mathbb{Z}}|f(x)|^{p}\right)^{1/p}$
$\|f\|_{\ell^{p}}=\left(\sum_{x\in\mathbb{Z}/N\mathbb{Z}}|f(x)|^{p}\right)^{1/p}.$

  * •

We define $C^{k}f$ as a conjugating operator applied $k$ times, with
$Cf=\hat{f}$, $C^{2}=C\circ C$, $C^{k}=C\circ C^{k-1}$.

  * •

We use the convention $\\{0,1\\}^{s}_{*}=\\{0,1\\}^{s}\setminus 0^{s}$ where
$0^{s}=00000\cdots 0$ with there being $s$ zeros appearing in the string.

For $f:\mathbb{Z}/N\mathbb{Z}\to\mathbb{C}$, the Gowers $U^{s}$ norm is the
following quantity

$\|f\|_{U^{s}}^{2^{s}}=\mathbb{E}_{x,h_{1},h_{2},\dots,h_{s}}\prod_{\omega\in\\{0,1\\}^{s}}C^{|\omega|}f(x+\omega\cdot
h)=\mathbb{E}_{x\in\mathbb{Z}/N\mathbb{Z},h\in\mathbb{Z}/N\mathbb{Z}^{s}}\Delta_{h}f(x).$

The Gowers norm was first defined in [G2], where it was also proved to be a
norm and have the following Cauchy-Schwarz like identity:

######  Lemma 2.1 (Cauchy-Schwarz-Gowers Inequality).

cauchyschwarzgowers Let $(f_{\omega})_{\omega\in\\{0,1\\}^{s}}$ be a set of
functions defined on $\mathbb{Z}/N\mathbb{Z}$, then

$\mathbb{E}_{x,h_{1},\dots,h_{s}}\prod_{s\in\\{0,1\\}^{s}}C^{|\omega|}f_{\omega}(x+\omega\cdot
h)\leq\prod_{\omega\in\\{0,1\\}^{s}}\|f_{\omega}\|_{U^{s}}^{2^{s}}.$

If $s=2$, it turns out that

$\|f\|_{U^{2}}=\|\hat{f}\|_{\ell^{4}}$

so by Plancherel and Hölder’s inequality, we have

######  Theorem 5 ($U^{2}$ Inverse Theorem).

u2 We have

$\|f\|_{U^{2}}^{4}\leq\|f\|_{L^{2}}^{2}\|\hat{f}\|_{L^{\infty}}^{2}.$

We will now go over some notation regarding nilmanifolds. This notation is
fairly standard, and appears in, for instance [GT2] and [TT]. Let $G_{\circ}$
be a filtered nilpotent Lie group and $\Gamma$ a discrete co-compact subgroup.
The Lie algebra $\mathfrak{g}$ of the nilpotent Lie group is adapted with a
Mal’cev basis, $X_{1},\dots,X_{d}$ with $d$ the dimension of $G$ with $\Gamma$
corresponding to integer combinations of $X_{i}$. We will assume that the
Mal’cev basis satisfies a nesting property: that is,

$[\mathfrak{g},X_{i}]\subseteq\text{span}(X_{i+1},\dots,X_{m}).$

Suppose

$[X_{i},X_{j}]=\sum_{k}c_{ijk}X_{k}$

with $c_{ijk}$ rational. A polynomial sequence is a sequence
$g\colon\mathbb{Z}\to G$ of the form

$g(n)=g_{0}g_{1}^{n}g_{2}^{{n\choose 2}}g_{3}^{{n\choose 3}}\cdots
g_{s}^{{n\choose s}}$

where $g_{i}\in G_{i}$, and a polynomial nilsequence is a sequence of the form
$F(g(n)\Gamma)$ where $F\colon G/\Gamma\to\mathbb{C}$ is a Lipschitz function
and $g$ is a polynomial sequence. A treatment of polynomial sequences can be
found in, e.g., [T1]. Factoring $g(0)=\\{g(0)\\}[g(0)]$ where
$[g(0)]\in\Gamma$ and $\\{g(0)\\}$ is bounded, and observing that

$F(g(n)\Gamma)=F(\\{g(0)\\}\cdot\\{g(0)\\}^{-1}g(n)[g(0)]^{-1}\Gamma)$

it follows that we may replace $F(g(n)\Gamma)$ with
$\tilde{F}(\tilde{g}(n)\Gamma)$ such that

$\tilde{F}=F(\\{g(0)\\}\cdot)$ $\tilde{g}(n)=\\{g(0)\\}^{-1}g(n)[g(0)]^{-1}.$

Thus, we may assume that $g(0)=Id$. Note that $\\{g(0)\\}$ being bounded
ensures that the Lipschitz norm of $\tilde{F}$ does not blow up. The degree of
the polynomial sequence is the degree of the filtration of the nilpotent Lie
group. The complexity of the nilmanifold is the minimum $M$ for which all
numerators and denominators of $c_{ijk}$ are less than $M$ in absolute value.
If $F:G/\Gamma\to\mathbb{C}$ is a Lipschitz function, we may Fourier expand
$F$ along the vertical torus $G_{s}/(G_{s}\cap\Gamma)$ to obtain

$F(x)=\sum_{\xi}F_{\xi}\hskip 7.22743pt,F_{\xi}=\int_{G_{s}/(\Gamma\cap
G_{s})}\overline{\xi}(g_{s})F(g_{s}x\Gamma)dg_{s}$

where $\xi:G_{s}/(G_{s}\cap\Gamma)\to\mathbb{C}^{*}$ are the characters. These
$F_{\xi}$ are known as nilcharacters of frequency $\xi$ and satisfy
$F_{\xi}(g_{s}x)=\xi(g_{s})F_{\xi}(x)$ for $g_{s}\in G_{s}$. Nilcharacters
aren’t unique in general, but are unique up to “lower order factors.” A formal
treatment of these nilcharacters is found in [GTZ].

Nilmanifolds also have horizontal characters, that is, elements of the dual
group $G/[G,G]\Gamma$, known as the horizontal torus. This group is well-
defined because $G/[G,G]$ is abelian. Letting $X_{1},X_{2},\dots,X_{m}$ denote
the Mal’cev basis components for the horizontal torus, and letting

$\text{horiz}(g)=\sum_{i=1}^{m}\alpha_{i}X_{i}$

for an element $g\in G/\Gamma$ where $\text{horiz}(g)$ is the horizontal torus
component of $g$, we see that each horizontal character $\eta$ may be
described as $\eta(g)=k\cdot\alpha$ in Mal’cev coordinates. We let $|\eta|$
denote the $\ell^{\infty}$ norm of the vector $k$. Note that the Lipschitz
norm of $\eta$ is roughly equal to $|\eta|$.

The $U^{3}$ norm is not known to have quite as nice of an interpretation as
the $U^{2}$ norm, but we also have a “$U^{3}$ inverse theorem,” a statement of
which found in u3. A helpful example of a nilmanifold that the reader can
consider are the various Heisenberg groups. In fact, since the nilmanifold in
the $U^{3}$ inverse theorem is basically a high dimensional Heisenberg
nilmanifold, all of the nilpotent Lie groups we will encounter in this paper
are essentially subgroups of various high dimensional Heisenberg groups.

##  3\. An Overview of the Proof

###  3.1. gowers implies count

One way to estimate

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

would be to Fourier expand

$p(x)=\sum_{\xi}\hat{p}(\xi)e(-\xi x)$

so that

$\Lambda(f,g,k,p)=\mathbb{E}_{x,y}\sum_{\xi}\hat{p}(\xi)f(x)e(\xi
x)g(x+P(y))e(-\xi(x+P(y)))k(x+Q(y))e(-\xi(x+Q(y))).$

By the previous work on linearly independent polynomial progressions [BC],
[DLS], [P1], we have the following:

######  Theorem 6.

poly Let $P_{1}(y),P_{2}(y),\dots,P_{n}(y)\in\mathbb{Z}[x]$ be linearly
independent polynomials with $P_{i}(0)=0$ and let
$f_{i}:\mathbb{Z}/N\mathbb{Z}\to\mathbb{C}$ be one-bounded functions. Then
there exists $\delta>0$ depending only on $P_{i},\dots,P_{n}$ such that

$\mathbb{E}_{x,y}\prod_{i=1}^{n}f_{i}(x+P_{i}(y))=\prod_{i=1}^{n}\mathbb{E}[f_{i}]+O(N^{-\gamma}).$

Thus,

$\Lambda(f,g,k,p)=\mathbb{E}_{\xi}\hat{p}(\xi)\mathbb{E}_{x}f(x)e(\xi
x)\mathbb{E}_{y}g(y)e(-\xi y)\mathbb{E}_{z}h(z)e(-\xi
z)+O(\|\hat{p}\|_{\ell^{1}}N^{-\gamma})$
$=\mathbb{E}_{x,y,z}f(x)g(x+y)k(x+z)p(x+y+z)+O(\|\hat{p}\|_{\ell^{1}}N^{-\gamma}).$

As $p(x)$ can equal $e(\alpha x^{2})$, the $\ell^{1}$ norm of $\hat{p}$ can be
quite large; larger than $N^{\gamma}$. However, we may use regularity applied
to the $L^{\infty}$ norm of the Fourier transform to decompose
$p=p_{a}+p_{b}+p_{c}$ with $\|\widehat{p_{a}}\|_{\ell^{1}}\ll N^{\gamma_{1}}$
with $\gamma_{1}<\gamma$, $p_{b}$ having small $L^{1}$ norm, and
$\|\widehat{p_{c}}\|_{L^{\infty}}$ small while $\|p_{c}\|_{L^{\infty}}$ can be
controlled so that the contribution of $\Lambda(f,g,k,p_{c})$ can be estimated
to be small. The necessary estimate on $\Lambda(f,g,k,p_{c})$ would follow
from gowers.

Thus, we may write

$\Lambda(f,g,k,p)\approx\Lambda^{1}(f,g,k,p_{a}).$

We will also be able to show that

$\Lambda^{1}(f,g,k,p)\approx\Lambda^{1}(f,g,k,p_{a}).$

Putting everything together, it follows that

$\Lambda(f,g,k,p)\approx\Lambda^{1}(f,g,k,p).$

Thus, it suffices to prove gowers.

###  3.2. A Sketch of gowers

We prove gowers via the following strategy: we first prove an initial Gowers
uniformity estimate on $p$: bounding $|\Lambda(f,g,k,p)|$ by $\|p\|_{U^{s}}$
for some $s$, and then use a degree lowering procedure to lower the parameter
$s$ one by one until it becomes two. To prove the Gowers uniformity estimate,
we use the PET induction procedure of Bergelson and Liebman [BL].

It turns out to be useful to consider the following model problem: showing
control of $\Lambda(f,g,k,p)$ by the $U^{2}$ norm of $f,g,k$ if $p$ is some
genuine quadratic phase $p(x)=e(\alpha x^{2}+\beta x)$ with $\alpha,\beta$
both having denominator $N$. Noticing that

$(x+P(y)+Q(y))^{2}=(x+P(y))^{2}+(x+Q(y))^{2}-x^{2}+2P(y)Q(y)$
$x+P(y)+Q(y)=(x+P(y))+(x+Q(y))-x$

we obtain

(1)
$\Lambda(f,g,k,p)=\mathbb{E}_{x,y}\tilde{f}(x)\tilde{g}(x+P(y))\tilde{k}(x+Q(y))e(2\alpha
P(y)Q(y))$

where

$\tilde{f}(x)=f(x)e(-\alpha x^{2}-\beta x),\hskip
7.22743pt\tilde{g}(x)=g(x)e(\alpha x^{2}+\beta x),\hskip
7.22743pt\tilde{k}(x)=e(\alpha x^{2}+\beta x)k(x).$

By observing that $\alpha P(y)Q(y)=\alpha(x+P(y)Q(y))-\alpha x$, applying poly
to the progression $(x,x+P(y),x+Q(y),x+2P(y)Q(y))$, we may bound, up to some
small error, $\Lambda(f,g,k,p)$ by the $U^{1}$ norm of $e(\alpha x)$, which is
zero if $\alpha$ is nonzero. This implies that if $\Lambda(f,g,k,p)$ is larger
than the small error, then $\alpha$ must be zero. Thus, applying poly again,
we may bound (1) by

$|\mathbb{E}\tilde{f}(x)||\mathbb{E}\tilde{g}(x)||\mathbb{E}\tilde{k}(x)|\leq\|f\|_{U^{2}}\|g\|_{U^{2}}\|k\|_{U^{2}}.$

In a slightly more general case, we take $p$ to be bracket polynomials of the
form $B(n,m)=\sum_{i}a_{i}\\{\alpha_{i}n\\}\\{\beta_{i}m\\}$ where
$\\{\cdot\\}=x-[x]$ where $[x]$ is the nearest integer to $x$ where we round
up (e.g. $[1.5]=2$). Notice that

$B(n+h,m)\equiv B(n,m)+B(h,m)+R(h,m,n)$

where $R(h,m,n)$ contains terms that look like $\\{\alpha n\\}\\{\beta
m\\},\\{\alpha(n+h)\\}\\{\beta m\\},or\\{\alpha h\\}\\{\beta m\\}$. These
terms are degree one nilsequences and can be Fourier expanded into terms that
look like, for instance, $e(a\alpha n+b\beta m)$. Although it’s not true that

$B(x+P(y)+Q(y),x+P(y)+Q(y))\equiv B(x+P(y),x+P(y))+B(x+Q(y),x+Q(y))$
$-B(x,x)+B(P(y),Q(y))+B(Q(y),P(y))\pmod{1}$

the remaining terms are degree one bracketed phases, and can be Fourier
expanded. The key difference between the simplified case of taking our phase
to be a globally quadratic phase and the bracket polynomial phase is the
analysis of the equidistribution of $B(P(y),Q(y))+B(Q(y),P(y))$. We
essentially show in equidistribution that if $B(P(y),Q(y))+B(Q(y),P(y))$ fails
to equidistribute, which will end up being the case, then the phase $B(y,y)$
is essentially a degree two nilsequence on a degree one nilmanifold. The phase
$e(B(y,y))$ can thus be Fourier expanded and we are essentially in the
globally quadratic case.

Doing the above for bracket polynomials is, modulo some technical details,
enough to establish the main theorem, but in an effort to make the argument
cleaner and more generalizable, we’ve written the argument in terms of
nilsequences. In this case, “bracket polynomials” become “nilcharacters.” We
may exploit the “parallelopiped structure” of nilmanifolds to write a
nilsequence $F(g(n)\Gamma)$ as a linear combination of “dual nilsequences”:

$F(g(n)\Gamma))=\sum_{\alpha}\prod_{\omega\in\\{0,1\\}^{3}_{*}}C^{|\omega|-1}F_{\omega,\alpha}(g(n+h\cdot\omega)\Gamma)+O(\epsilon).$

In fact, an averaging argument shows that if $F$ is a nilcharacter of some
frequency $\xi$, then all the $F_{\omega,\alpha}$ can be taken to be
nilcharacters of the same frequency, so in a sense, nilcharacters are self
dual. See dualus for more details. Substituting in $n=x+P(y)+Q(y)$,
$h_{1}=-P(y)$, $h_{2}=-Q(y)$, $h_{3}=-x$, we’ve effectively realized the
identity

$B(x+P(y)+Q(y),x+P(y)+Q(y))\approx B(x+P(y),x+P(y))+B(x+Q(y),x+Q(y))$
$-B(x,x)+B(P(y)+Q(y),P(y)+Q(y))-B(P(y),P(y))-B(Q(y),Q(y))\pmod{1}$

in the abstract nilmanifold setting. We may then argue as in the bracket
polynomial setting.

One more remark about the proof: a common technique used throughout the proof
is stashing, as coined by Freddie Manners in [M]. It informally states that
for any sort of quantitative count

$\Lambda(f_{1},\dots,f_{t})=\mathbb{E}_{x_{1},\dots,x_{u}}f_{1}(\phi_{1}(x))f_{2}(\phi_{2}(x))\cdots
f_{t}(\phi_{t}(x))$

if we can show that $|\Lambda(f_{1},\dots,f_{t})|\leq\|f_{1}\|_{U^{s}}$ for
any one-bounded $f_{i}$, then defining a “dual function”

$\mathcal{D}(f_{2},\dots,f_{t})=\mathbb{E}_{v=\phi_{1}^{-1}(x_{1},\dots,x_{u})}f_{2}(\phi_{2}(x))\cdots
f_{t}(\phi_{t}(x))$

then

$|\Lambda(f_{1},\dots,f_{t})|``\leq"\|\mathcal{D}(f_{2},\dots,f_{t})\|_{U^{s}}^{1/2}.$

Usually this would follow from a simple application of Cauchy-Schwarz. For
instance, if

$\Lambda(f_{1},f_{2},f_{3})=\mathbb{E}_{x,y}f_{1}(x)f_{2}(x+y)f_{3}(x+y^{2})$

then if we define

$\mathcal{D}(f_{1},f_{2})=\mathbb{E}_{y}f_{1}(x-y^{2})f_{2}(x+y-y^{2})$

it follows that

$|\Lambda(f_{1},f_{2},f_{3})|^{2}\leq\mathbb{E}_{x}\mathcal{D}(f_{1},f_{2})\overline{\mathcal{D}(f_{1},f_{2})}=\Lambda(\overline{f_{1}},\overline{f_{2}},\mathcal{D}(f_{1},f_{2})).$

Thus, a slogan the reader can keep in mind is that proving Gowers uniformity
for a function $f$ in a count $\Lambda$ implies proving Gowers uniformity for
its dual function.

##  4\. From True Complexity to Szemerédi’s Theorem

###  4.1. Deducing count from gowers

We begin this section with the following:

######  Lemma 4.1.

reduce Let $f,g,k\colon\mathbb{Z}/N\mathbb{Z}\to\mathbb{C}$ be one-bounded and
$p\colon\mathbb{Z}/N\mathbb{Z}\to\mathbb{C}$. We have

$\Lambda(f,g,k,p)=\Lambda^{1}(f,g,k,p)+O(\|\hat{p}\|_{\ell^{1}}N^{-\gamma})$

for some $\gamma>0$.

###### Proof.

Fourier expanding, we see that

$p(x)=\sum_{\xi}\hat{p}(\xi)e(-\xi x)$

so that

$\displaystyle\Lambda(f,g,k,p)$
$\displaystyle=\sum_{\xi}\hat{p}(\xi)\mathbb{E}_{x,y}f(x)g(x+P(y))k(x+Q(y))e(-\xi(x+P(y)+Q(y)))$
$\displaystyle=\sum_{\xi}p(\xi)\mathbb{E}_{x,y,z}f(x)e(\xi
x)g(x+y)e(-\xi(x+y))k(x+z)e(-\xi(x+z))+O(\|\hat{p}\|_{\ell^{1}}N^{-\gamma})$
$\displaystyle=\mathbb{E}_{x,y,z}f(x)g(x+y)k(x+z)p(x+y+z)+O(\|\hat{p}\|_{\ell^{1}}N^{-\gamma})$

where the second equality follows from poly. ∎

We use the following regularity lemma due to Peluse [P1], a proof of which can
be found in [PP3, Appendix A]:

######  Lemma 4.2.

regularity Let $f\colon\mathbb{Z}/N\mathbb{Z}\to\mathbb{C}$ be a function with
$L^{2}$ norm is at most $1$ and $\|\cdot\|$ any norm on
$(\mathbb{Z}/N\mathbb{Z})^{\mathbb{C}}$,
$\epsilon_{1},\epsilon_{2},\epsilon_{3},\epsilon_{4}>0$ be such that
$\epsilon_{2}^{-1}\epsilon_{3}+\epsilon_{4}^{-1}\epsilon_{1}\leq\frac{1}{2}$.
Then we may write

$f=f_{a}+f_{b}+f_{c}$

where $f_{1},f_{b},f_{c}\colon\mathbb{Z}/N\mathbb{Z}\to\mathbb{C}$ obey the
bounds

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

and $\|\cdot\|^{*}$ denotes the dual norm of $\|\cdot\|$.

Applying the lemma on $p$ with the norm being the $L^{\infty}$ of the Fourier
transform,

$\Lambda(f,g,k,p)=\Lambda(f,g,k,p_{a})+\Lambda(f,g,k,p_{b})+\Lambda(f,g,k,p_{c}).$

The second term is bounded by

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

Using gowers, the last term either satisfies

$|\Lambda(f,g,k,p_{c})|\leq\epsilon_{3}^{-1}O\left(\frac{1}{\log_{O(1)}(N)}\right)$

or it satisfies

$|\Lambda(f,g,k,p_{c})|\leq\epsilon_{3}^{-1}|\lambda(f,g,k,\epsilon_{3}p_{c})|\leq\epsilon_{3}^{-1}c_{1}(\|\epsilon_{3}p_{c}\|_{u^{2}}^{1/2})=\epsilon_{3}^{-1}c_{1}(\epsilon_{3}^{1/2}\epsilon_{4})$

where $c_{1}$ is an iterated logarithm function of the form
$c_{1}(x)=\frac{1}{\log_{O(1)}(x^{-1})}$. By reduce, the first term is bounded
by

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

We thus have

$\Lambda(f,g,k,p)=\Lambda^{1}(f,g,k,p_{a})+O(N^{-\delta}\epsilon_{1}^{-1})+O(\epsilon_{3}^{-1}c(\epsilon_{3}^{1/2}\epsilon_{4}))+\epsilon_{2}+\epsilon_{3}^{-1}O\left(\frac{1}{\log_{O(1)}(N)}\right).$

Doing the same procedure for $\Lambda^{1}(f,g,k,p)$, we see that

$\Lambda^{1}(f,g,k,p)=\Lambda^{1}(f,g,k,p_{a})+O(N^{-\delta}\epsilon_{1}^{-1})+O(\epsilon_{3}\epsilon_{4})+\epsilon_{2}.$

Thus,

$\Lambda(f,g,k,p)=\Lambda^{1}(f,g,k,p)+O(N^{-\delta}\epsilon_{1}^{-1})+O(\epsilon_{3}^{-1}c(\epsilon_{3}^{1/2}\epsilon_{4}))+O(\epsilon_{3}\epsilon_{4})+\epsilon_{2}+\epsilon_{3}^{-1}O\left(\frac{1}{\log_{O(1)}(N)}\right).$

Picking $\epsilon_{3}\ll\epsilon_{2}=O(\log_{C}(N))^{-1})$ for $C$ large
enough, $\epsilon_{4}\sim N^{-\gamma}$, $\epsilon_{1}\ll\epsilon_{4}$, we
obtain a bound of size

$\mathbb{E}_{x,y}f(x)g(x+P(y))k(x+Q(y))p(x+P(y)+Q(y))=\mathbb{E}_{x,y,z}f(x)g(x+y)k(x+z)p(x+y+z)$
$+O\left(\frac{1}{\log_{(O(1))}(N)}\right).$

This completes the proof of count.

###  4.2. Deducing conj1 from conj2

To generalize the deduction of count from gowers, we can no longer rely on the
Fourier transform. Instead, we use dual $U^{s}$ functions. Indeed, as observed
by [M], correlating with dual functions tends to give more information than
just correlating with functions. In this case, dual functions offer enough
information that we can deduce conj2 from conj1. It is helpful to think of the
dual $U^{s}$ norm as follows:

$\|f\|_{U^{s}}^{*}``\approx"\inf_{(f_{\omega,i})\in(\mathbb{Z}/N\mathbb{Z})^{\\{0,1\\}^{s}_{*}};\|f_{\omega,i}\|_{\infty}=1}\\{\sum_{i}|a_{i}|:\sum_{i}a_{i}\mathcal{D}_{U^{s}}(f_{\omega,i})=f\\}$

where

$\mathcal{D}_{U^{s}}(f_{\omega})(x)=\sum_{h_{1},\dots,h_{s}}\prod_{\omega\in\\{0,1\\}^{s}_{*}}f_{\omega}(x+h\cdot\omega).$

While the above statement is not true, the $U^{s}$ norm does have a rather
obvious inverse theorem:

######  Proposition 4.1.

usinverse Suppose $f:\mathbb{Z}/N\mathbb{Z}\to\mathbb{C}$ is a one-bounded
function with $\|f\|_{U^{s}}\geq\delta$. Then there exists a dual $U^{s}$
function $D_{U^{s}}((f_{\omega})_{\omega\in\\{0,1\\}^{s}_{*}})$ such that with
$f_{\omega}$ one-bounded functions

$|\langle f,D_{U^{s}}(f_{\omega})\rangle|\geq\delta^{2^{s}}.$

In addition, [G1] gives a procedure for converting an inverse theorem into a
regularity lemma. Using that procedure on regularity, we have the following:

######  Lemma 4.3.

regularity2 Let $f:\mathbb{Z}/N\mathbb{Z}\to\mathbb{C}$ be a function with
$L^{2}$ norm at most one, $\epsilon_{1},\dots,\epsilon_{4}$ be as in
regularity, $\eta>0$. Then there exists a decomposition $f=f_{1}+f_{2}+f_{3}$
where

$f_{1}=\sum_{j}a_{j}D_{U^{s}}((f_{\omega,j})),\hskip
7.22743pt\sum_{j}|a_{j}|\leq\eta(\epsilon_{1}\eta)^{-2^{s}}$
$\|f_{2}\|_{L^{1}}\leq\epsilon_{2}+\eta$
$\|f_{3}\|_{L^{\infty}}\leq\epsilon_{3}^{-1},\hskip
7.22743pt\|f_{3}\|_{U^{s}}\leq\epsilon_{4}.$

###### Proof.

Apply regularity for the norm $\|\cdot\|_{U^{s}}$ to obtain a decomposition

$f=g_{1}+g_{2}+g_{3}.$

We shall desire a decomposition

$g_{1}=\sum_{j}a_{j}D_{U^{s}}((f_{\omega,j}))+h$

where $h$ has relatively small $\ell^{1}$ norm. To do this, we follow the
argument in [G1, Section 3.2]. If a decomposition doesn’t exist with

$\sum_{j}|a_{j}|\leq\eta(\epsilon_{1}\eta)^{-2^{s}}$
$\|h\|_{\ell^{1}}\leq\eta$

then by Hahn-Banach (or rather, by [G1, Corollary 3.2]), there exists a linear
functional $\ell:\mathbb{Z}/N\mathbb{Z}\to\mathbb{C}$ such that
$\langle\ell,D_{U^{s}}((f_{\omega}))\rangle<\eta^{-1}(\epsilon_{1}\eta)^{2^{s}}$
for all dual $U^{s}$ functions, $\langle g_{1},\ell\rangle>1$, and
$\|\ell\|_{L^{\infty}}\leq\eta^{-1}$. However, $\langle g_{1},\ell\rangle>1$
implies that $\|\ell\|_{U^{s}}\geq\epsilon_{1}$. By usinverse, this implies
that

$\langle\ell,\mathcal{D}_{U^{s}}(f_{\omega})\rangle\geq\eta^{-1}(\epsilon_{1}\eta)^{2^{s}}$

which is a contradiction. Hence, such a decomposition exists, and letting

$f_{1}=g_{1}-h,f_{2}=g_{2}+h,f_{3}=g_{3}$

we obtain the desired result. ∎

For $P=(P_{1},\dots,P_{s})$ where its components are linearly independent and
$P_{i}(0)=0$, $s\geq t$ let

$\Lambda_{s,t}((f_{\omega}))=\mathbb{E}_{x,y}\prod_{\omega\in\\{0,1\\}^{s}:|\omega|\leq
t}f_{\omega}(x+\omega\cdot P)$
$\Lambda^{1}_{s,t}((f_{\omega}))=\mathbb{E}_{x,h_{1},\dots,h_{s}}\prod_{\omega\in\\{0,1\\}^{t}:|\omega|\leq
t}f_{\omega}(x+\omega\cdot h).$

We shall give a proof that conj2 implies conj1 via a double induction on $s$
and $t$. Specifically, we show that $(s,t-1)$ implies $(s,t)$ and $(t,t-1)$
implies $(t,t)$. The base case follows from poly.

$(s,t-1)$ implies $(s,t)$
For each $\omega^{\prime}$ with $|\omega^{\prime}|=t$, we use regularity2 for
the $U^{t}$ norm to decompose

$f_{\omega^{\prime}}=f_{\omega^{\prime},1}+f_{\omega^{\prime},2}+f_{\omega^{\prime},3}.$

The point is that in the dual function

$D_{U^{t}}(g_{\omega^{\prime}})(x+\omega^{\prime}\cdot
P(y))=\mathbb{E}_{h_{1},\dots,h_{t}}\prod_{\omega\in\\{0,1\\}^{t}_{*}}g_{\omega^{\prime}}(x+\omega^{\prime}\cdot
P(y)+\omega\cdot h),$

letting $j_{\omega^{\prime},1},\dots,j_{\omega^{\prime},t}$ being the indices
of the nonzero components of $\omega^{\prime}$, we can make the change of
variables $h_{i}\mapsto h_{i}-P_{j_{\omega^{\prime},i}}(y)$ to essentially
eliminate the $x+\omega^{\prime}\cdot P(y)$ term, and reduce to the $(s,t-1)$
case. As in the deduction of count from gowers, it follows that the main term
reduces to the the setting of $(s,t-1)$.

######  Lemma 4.4.

cscomplexity Let $(f_{\omega})_{\omega\in\\{0,1\\}^{s}}$ be one-bounded
functions on $\mathbb{Z}/N\mathbb{Z}$. For $\omega$ with $|\omega|=t$, we have

$|\Lambda_{s,t}^{1}(f_{\omega})|\leq\|f_{\omega}\|_{U^{t}}$

###### Proof.

This follows from the Cauchy-Schwarz-Gowers inequality (cauchyschwarzgowers)
along the variables $x$ and $h_{i}$’s where $\omega$ appear in. ∎

Letting

$\epsilon_{1}\ll\epsilon_{4}=O((\log_{C_{1}}(N))^{-1}),\epsilon_{2}\ll\epsilon_{3}=O((\log_{C_{2}}(N))^{-1}),\eta=\epsilon_{1}$

with $C_{1},C_{2}$ sufficiently large, and $c$ a small constant, we obtain
that

$\Lambda_{s,t}(f_{\omega,1})=\Lambda^{1}_{s,t}(f_{\omega,1})+O\left(\frac{1}{\log_{O(1)}(N)}\right)$

and the other terms involving $f_{\omega,2}$ and $f_{\omega,3}$ are of order
$O\left(\frac{1}{\log_{O(1)}(N)}\right)$. In addition,

$\Lambda^{1}_{s,t}(f_{\omega,1})=\Lambda^{1}(f_{\omega})+O\left(\frac{1}{\log_{O(1)}(N)}\right)$

as well. Thus,

$\Lambda_{s,t}(f_{\omega})=\Lambda^{1}_{s,t}(f_{\omega})+O\left(\frac{1}{\log_{O(1)}(N)}\right)$

$(t,t-1)$ implies $(t,t)$
The proof is essentially the same as above. We use regularity2 on the function
$f_{1^{t}}$ to decompose

$f_{1^{t}}=f_{1^{t},1}+f_{1^{t},2}+f_{1^{t},3}$

with

$f_{1^{t},1}=\sum_{i}a_{j}D_{U^{t}}((f_{\omega,j})),$

$f_{1^{t},2}$ has small $\ell^{1}$ norm, and $f_{1^{t},3}$ has controlled
$L^{\infty}$ norm and small $U^{s}$ norm. As above, we have

$f_{1^{t},1}(x+P_{1}(y)+\cdots+P_{t}(y))=\sum_{j}a_{j}\mathbb{E}_{h_{1},\dots,h_{t}}\prod_{\omega\in\\{0,1\\}^{t}_{*}}f_{\omega,j}(x+P_{1}(y)+\cdots+P_{t}(y)+\omega\cdot
h).$

Making a change of variables $h_{1}\mapsto h_{1}-P_{1}(y),\dots,h_{t}\mapsto
h_{t}-P_{t}(y)$, it follows that we have gotten rid of the
$x+P_{1}(y)+\cdots+P_{t}(y)$ term and we are in the realm of the $(t,t-1)$
case. Choosing

$\epsilon_{1}\ll\epsilon_{4}=O((\log_{C_{1}}(N))^{-1}),\epsilon_{2}\ll\epsilon_{3}=O((\log_{C_{2}}(N))^{-1}),\eta=\epsilon_{1}$

with $C_{1}$ and $C_{2}$ sufficiently large and $c$ sufficiently small would
ensure that our error terms are sufficiently small, thereby letting us
conclude that

$\Lambda_{t,t}(f_{\omega,1})=\Lambda^{1}_{t,t}(f_{\omega,1})+O\left(\frac{1}{\log_{O(1)}(N)}\right)$

and since the terms $f_{\omega,2}$, $f_{\omega,3}$ are either small or have
small Gowers norm, it follows that

$\Lambda_{t,t}(f_{\omega})=\Lambda^{1}_{t,t}(f_{\omega})+O\left(\frac{1}{\log_{O(1)}(N)}\right).$

##  5\. PET Induction

Our first step towards the proof of gowers is proving an initial Gowers norm
estimate. We do this by using PET induction, due to Bergelson and Liebman in
[BL]. A proof can be found in [Pr2] (see also [Pr1]).

######  Lemma 5.1.

pet1 There exists some $s$, $c$, $\zeta>0$ such that

$|\Lambda(f,g,k,p)|\ll\min(\|f\|_{U^{s}},\|g\|_{U^{s}},\|k\|_{U^{s}},\|p\|_{U^{s}})^{c}+O(N^{-\zeta})$

for all one-bounded functions $f,g,k,p$.

######  Remark.

If $P(y)=y^{2}$ and $Q(y)=y^{3}$, we may take an upper bound of $s$ to be
$34$.

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

######  Lemma 5.2.

pet2 Let $f,g,k,p$ be one-bounded functions. Then there exists $s,c,\zeta>0$
not depending on $f,g,k,p$ such that

$|\Lambda^{2}(f,g,k,p))|\ll\min(\|f\|_{U^{s}},\|g\|_{U^{s}},\|k\|_{U^{s}})^{c}+O(N^{-\zeta}).$

###### Proof.

By Cauchy-Schwarz on $y$, we have

$|\Lambda^{2}(f,g,k,p)|\leq\mathbb{E}_{x,y,h}\Delta_{h}f(x)\Delta_{h}g(x+P(y))\Delta_{h}k(x+Q(y)).$

Here, $\Delta_{h}f(x)=\overline{f(x+h)}f(x)$ (see section 2 for notation). We
use PET induction to bound the above by

$\mathbb{E}_{h}\|\Delta_{h}f\|_{U^{s}}^{c}+O(N^{-\zeta_{1}})\ll\|f\|_{U^{s+1}}^{c^{\prime}}+O(N^{-\zeta}).$

The other cases for $g,k$ are similar. ∎

Thus, by pet1, we may bound

$|\Lambda(f,g,k,p)|\ll\|p\|_{U^{s}}^{O(1)}+O(N^{-\zeta_{1}})$

Let

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

Then by Cauchy-Schwarz (see the discussion on stashing in section 3), it
follows that

$|\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}}^{O(1)}+O(N^{-\zeta})$

where the last inequality follows by invoking pet1. By using repeating the
stashing argument, gowers thus follows from the following:

######  Theorem 7 (Degree Lowering).

degreelowering Let $s\geq 2$. If

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

then either $\delta\ll 1/\exp_{O(1)}(N^{-1})$ or

$\|p\|_{U^{s}}\geq c^{\prime}(\delta)$

where $c^{\prime}$ is an iterated exponential function.

######  Remark.

We may in fact take $c^{\prime}$ to be an order two iterated exponential
function. Since this makes the notation much more cumbersome, we choose not to
do so here.

An important tool in the degree lowering argument is the following, due to
Peluse [P1, Lemma 5.1] (see e.g. the proof of [Pr1, Lemma 6.3] for a more
refined formulation):

######  Lemma 5.3 (Dual-Difference Interchanging).

dual Let $f_{0}:\mathbb{Z}/N\mathbb{Z}\to\mathbb{C}$,
$f_{1},f_{2},\dots,f_{m}:(\mathbb{Z}/N\mathbb{Z})^{2}\to\mathbb{C}$ be one-
bounded functions, $F(x)=\mathbb{E}_{y}f_{0}(y)\prod_{i}f_{i}(x,y)$, and
$s\geq 2$. Then

$\|F\|_{U^{s}}^{2^{s+1}}\leq\mathbb{E}_{h}\|F_{h}\|_{U^{s-1}}^{2^{s-1}}$

where

$F_{h}(x)=\mathbb{E}_{y}\prod_{i}\Delta_{h}f_{i}(x,y)$

where if $h=(h_{1},\dots,h_{t})$,
$\Delta_{h}f_{i}(x,y)=\prod_{\omega\in\\{0,1\\}^{t}}C^{|\omega|}f_{i}(x+\omega\cdot
h,y)$. As a consequence, for $t\geq 0$,

$\|F\|_{U^{t+3}}^{2^{2t+3}}\leq\mathbb{E}_{h_{1},\dots,h_{t}}\|F_{h}\|_{U^{3}}^{8}.$

###### Proof.

We have

$\|F\|_{U^{s}}^{2^{s}}=\mathbb{E}_{x,h_{1},\dots,h_{s}}\mathbb{E}_{y\in\mathbb{Z}/N\mathbb{Z}^{\\{0,1\\}^{s}}}\prod_{i}\prod_{\omega\in\\{0,1\\}^{s}}C^{|\omega|}[f_{i}(x+\omega\cdot
x,y_{\omega})f_{0}(y_{\omega})].$

By Cauchy-Schwarz to eliminate the factor
$[\prod_{\omega\in\\{0,1\\}^{s}}f_{0}(y_{\omega})][\prod_{\omega\in\\{0,1\\}^{s}:\omega_{s}=0}f_{i}(x+h\cdot\omega)]$,
we have

$\|F\|_{U^{s}}^{2^{s+1}}\leq\mathbb{E}_{x,y,h}\mathbb{E}_{h_{s},h_{s}^{\prime}}\prod_{\omega\in\\{0,1\\}^{s-1}}\prod_{i=1}^{m}C^{|\omega|-1}[\overline{f_{i}(x+h\cdot\omega+h_{s},y_{\omega})}f_{i}(x+h\cdot\omega+h_{s}^{\prime},y_{\omega})].$

Finally, making a change of variables $h_{s}\mapsto h_{s}-h_{s}^{\prime}$ and
$x\mapsto x-h_{s}^{\prime}$ we have the desired inequality

$\|F\|_{U^{s}}^{2^{s+1}}\leq\sum_{h}\|F_{h}\|_{U^{s-1}}^{2^{s-1}}.$

To deduce the inequality

$\|F\|_{U^{t+3}}^{2^{2t+3}}\leq\mathbb{E}_{h_{1},\dots,h_{t}}\|F_{h}(x)\|_{U^{3}}^{8},$

we use induction on $t$. This is obvious for $t=0$. Suppose the above
inequality holds for $t$. Then

$\|F\|_{U^{t+4}}^{2^{2t+5}}=(\|F\|_{U^{t+4}}^{2^{t+5}})^{2^{t}}$

We see that

$\|F\|_{U^{t+4}}^{2^{t+5}}\leq\mathbb{E}_{h}\|F_{h}\|_{U^{t+3}}^{2^{t+3}}$

so by Hölder’s inequality and induction,

$(\|F\|_{U^{t+4}}^{2^{t+5}})^{2^{t}}\leq\mathbb{E}_{h}\|F_{h}\|_{U^{t+3}}^{2^{2t+3}}\leq\mathbb{E}_{h_{1},\dots,h_{t+1}}\|F_{h}\|_{U^{3}}^{8}.$

∎

######  Remark.

This lemma is actually a slightly stronger variant of [P1, Lemma 5.1], where
Peluse does not include the $f_{0}(y)$ term. The proofs of dual and of [P1,
Lemma 5.1] are essentially identical, though.

Let the notation and hypotheses be as in degreelowering. Let

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

By dual, we see that

$\mathbb{E}_{h_{1},\dots,h_{s-2}}\|\mathcal{D}_{h}(f,g,k)\|_{U^{3}}^{8}\gg\delta^{O(1)}.$

By the pigeonhole principle, it follows that for at least $\delta^{2}$ of the
$h$’s,

$\|\mathcal{D}_{h}(f,g,k)\|_{U^{3}}\geq\delta^{O(1)}.$

Applying the $U^{3}$ inverse theorem u3 and Fourier approximating via
lipfourier $\mathcal{D}_{h}(f,g,k)$ correlates with a nilcharacter
$F_{h}(m_{h}(n)\Gamma)$ of frequency $\xi_{h}$ with
$|\xi_{h}|\leq\delta^{-O(r)^{O(1)}}$, with the nilmanifold having dimension
$r$ at most $\delta^{-O(1)}$. By dualus we may essentially replace
$F(m_{h}(n)\Gamma)$ with its dual

$G_{h,\ell}(x)=\prod_{\omega\in\\{0,1\\}^{3}_{*}}C^{|\omega|-1}F_{h,\omega}(m_{h}(x+\ell\cdot\omega)\Gamma)$

where $m_{h}$ is the nilsequence, and each $F_{\omega,h}$ is a nilcharacter of
frequency $\xi_{h}$. By dividing by the Lipschitz norm, we may assume that
$F_{h}$ and $F_{h,\omega}$ are of Lipschitz norm one. Thus, we have

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

and

$\mathbb{E}_{h_{1},\dots,h_{s-2}}|\langle\mathcal{D}_{h}(f,g,k),G_{h,\ell}(x)\rangle|^{8}\gg\exp(-\delta^{-C})$

for some possibly large $C>0$.

##  6\. Equidistribution of the Nilcharacter

Let $\epsilon=\exp(-\delta^{-C})$. We separate each term in the sum into two
cases: for each $h$, either

$|\langle\mathcal{D}_{h}(f,g,k)(x),G_{h,\ell}(x)\rangle|^{8}<\epsilon^{2}$

or

$|\langle\mathcal{D}_{h}(f,g,k)(x),G_{h,\ell}(x)\rangle|^{8}\geq\epsilon^{2}.$

The former case contributes a relatively small portion to the sum, so we only
need to analyze the latter case. It is here where it is apparent why we work
with a dual nilsequence instead of a nilsequence. Indeed, the identity

$(x+P(y)+Q(y))^{2}=(x+P(y))^{2}+(x+Q(y))^{2}-x^{2}+2P(y)Q(y)$

is a reflection of the fact that if

$\partial_{h_{1},h_{2},h_{3}}\phi(x)=0$

for all $x,h_{1},h_{2},h_{3}$, i.e.,

$\phi(x+h_{1}+h_{2}+h_{3})-\phi(x+h_{1}+h_{2})-\phi(x+h_{1}+h_{3})-\phi(x+h_{2}+h_{3})+\phi(x+h_{1})+\phi(x+h_{2})+\phi(x+h_{3})-\phi(x)=0$

then

$\phi(P(y)+Q(y))-\phi(x+P(y)+Q(y))-\phi(P(y))-\phi(Q(y))+\phi(x+P(y))+\phi(x+Q(y))+\phi(0)-\phi(x)=0$

by substituting $P(y)$ in place of $h_{1}$, $Q(y)$ in place of $h_{2}$, and
$-x$ in place of $h_{3}$. Thus, letting $\ell_{1}=-P(y)$, $\ell_{2}=-Q(y)$,
and $\ell_{3}=-x$, we obtain

$|\mathbb{E}_{x,y}f_{1}(x)g_{1}(x+P(y))k_{1}(x+Q(y))K(y)|\geq\epsilon^{O(1)}$

with

$f_{1}(x)=F_{110,h}(m_{h}(x)\Gamma)\Delta_{h}f(x),$
$g_{1}(x)=\overline{F}_{010,h}(m_{h}(x)\Gamma)\Delta_{h}g(x),$
$k_{1}(x)=\overline{F}_{100,h}(m_{h}(x)\Gamma)\Delta_{h}k(x).$
$K(x)=F_{001,h}(m_{h}(P(y)+Q(y))\Gamma)\overline{F_{011,h}}(m_{h}(P(y))\Gamma)\overline{F_{101,h}}(m_{h}(Q(y))\Gamma)$

By pet2, we may bound the above by $\|k\|_{U^{t}}$ for some $t$. Letting

$\mathcal{D}(f_{1},g_{1})(x)=\mathbb{E}_{y}f_{1}(x-Q(y))g_{1}(x+P(y)-Q(y))K(y)$

it follows from Cauchy-Schwarz that

$\|\mathcal{D}(f_{1},g_{1})\|_{U^{t}}\gg\epsilon^{O(1)}.$

By dual and the $U^{2}$ inverse theorem (u2), it follows that

$\mathbb{E}_{h\in\mathbb{Z}/N\mathbb{Z}^{t-2}}|\mathbb{E}\Delta_{h}f_{1}(x-Q(y))\Delta_{h}g_{1}(x+P(y)-Q(y))e(\alpha_{h}x)|\gg\epsilon^{O(1)}.$

This is where we use previous results on linearly independent progressions of
[BC], [DLS], and [P1]:

######  Theorem 8 ([DLS], [P1], [P3]).

peluse Let $f,g,p\colon\mathbb{Z}/N\mathbb{Z}\to\mathbb{C}$ be one-bounded
functions. Then

$\mathbb{E}_{x,y}f(x)g(x+P(y))p(x+Q(y))=\mathbb{E}f\mathbb{E}g\mathbb{E}p+O(N^{-\gamma})$

for some $\gamma>0$.

Thus, we may assume that $\alpha_{h}=0$ up to an error of $N^{-\gamma}$ which
is much smaller than any error we will obtain. It follows that

$\|f_{1}\|_{U^{t-1}}\gg\epsilon^{O(1)}.$

Letting

$\mathcal{D}(g_{1},k_{1})(x)=\mathbb{E}_{y}g_{1}(x+P(y))k_{1}(x+Q(y))K(y)$

we have by the stashing argument,

$\|\mathcal{D}(g_{1},k_{1})\|_{U^{t-1}}\gg\epsilon^{O(1)}.$

Thus, by dual, it follows that

$\mathbb{E}_{h\in\mathbb{Z}/N\mathbb{Z}^{t-2}}\|\mathcal{D}_{h}(g_{1},k_{1})\|_{U^{1}}^{2}\gg\epsilon^{O(1)}.$

This implies that

$\|k_{1}\|_{U^{t-1}}\gg\epsilon^{O(1)}.$

We may thus iterate this procedure until

$\|f_{1}\|_{U^{2}}\gg\epsilon^{O(1)}$

and thus

$\|k_{1}\|_{U^{2}}\gg\epsilon^{O(1)}$
$\|\mathcal{D}(f_{1},g_{1})\|_{U^{2}}\gg\epsilon^{O(1)}.$

This time, however, we must account for the term $K(y)$. Thus, there exists
$\alpha$ such that

$|\mathbb{E}_{x,y}f_{1}(x)g_{1}(x+P(y))e(\alpha Q(y))K(y)|\gg\epsilon^{O(1)}.$

By Fourier expanding $f_{1}$ and $g_{1}$ and applying the Cauchy-Schwarz
inequality, it follows that

$\displaystyle|\mathbb{E}_{x,y}f_{1}(x)g_{1}(x+P(y))e(\alpha Q(y))K(y)|$
$\displaystyle\leq\left|\mathbb{E}_{x,y}\sum_{\beta}\widehat{f_{1}}(\beta)\overline{\widehat{g_{1}}}(\beta)e(\alpha
Q(y)+\beta P(y))K(y))\right|$
$\displaystyle\leq\max_{\beta}|\mathbb{E}_{y}e(\alpha Q(y)+\beta P(y))K(y)|$

It follows that there exists some $\beta$ such that

$|\mathbb{E}_{y}e(\alpha Q(y)+\beta P(y))K(y)|\gg\epsilon^{O(1)}.$

######  Lemma 6.1 (Equidistribution Lemma).

equidistribution Let $F_{1},F_{2},F_{3}$ be nilcharacters of frequencies $\xi$
with Lipschitz norm at most $\delta^{-O(r)^{O(1)}}$ on an $r$-dimensional two-
step nilmanifold $G/\Gamma$. Let $g(n)\Gamma$ be a degree two polynomial
nilsequence modulo $N$ with $g(0)=Id$. Suppose for
$\alpha,\beta\in\widehat{\mathbb{Z}/N\mathbb{Z}}$,

$\left|\mathbb{E}_{y\in\mathbb{Z}/N\mathbb{Z}}e(\alpha Q(y)+\beta
P(y))F_{1}(g(P(y)+Q(y)))\overline{F_{2}}(g(P(y)))\overline{F_{3}}(g(Q(y)))\right|\geq\delta.$

Then at least one of the following occurs:

  * •

$\delta^{-\exp(O(r)^{O(1)})}\ll N$.

  * •

$F_{i}(g(n)\Gamma)$ (while itself is degree two) is equal to a nilsequence on
an abelian, dimension $O(r)$, and complexity at most
$\delta^{-\exp(O(r)^{O(1)})}$ nilmanifold (i.e. $F_{i}(g(n)\Gamma)$ has
Lipschitz norm at most $\delta^{-\exp(O(r)^{O(1)})}$ on said nilmanifold).

###### Proof.

We shall prove this via induction on $r$. If $r=1$, then the nilmanifold is
automatically abelian, so we are done. If $\xi=0$, then we are automatically
done since $F_{i}(g(n)\Gamma)$ lies in a degree one nilmanifold. First, we
shall eliminate that $e(\beta P(y))$ and $e(\alpha Q(y))$ terms. To do so,
pick two elements $h_{1},h_{2}\in[G,G]$ whose Mal’cev coordinates have
denominator $N$ such that $\xi(h_{1})=\alpha$, $\xi(h_{2})=\beta$. We shall
then modify $F_{1}(g(n)\Gamma)$ to $F_{1}(\tilde{g}_{1}(P(y))\Gamma)$ and
$F_{2}(\tilde{g}_{2}(Q(y)))$ by inserting $h_{1}^{n}$ and $h_{2}^{n}$ into the
polynomial sequence $g$. The horizontal torus Mal’cev basis components of $g$,
$\tilde{g}_{1}$, and $\tilde{g}_{2}$ are all equal because
$h_{1},h_{2}\in[G,G]$. Thus, $g$ lies in a degree one nilmanifold if and only
if $\tilde{g}_{1}$ and $\tilde{g}_{2}$ lie in a degree one nilmanifold.
Observe that
$(g(P(y)+Q(y))\Gamma,\tilde{g}_{1}(P(y))\Gamma,\tilde{g}_{2}(Q(y))\Gamma)$
lies in the subnilmanifold $H/\Lambda$ where

$H=\\{(g_{1},g_{2},g_{3})\in G^{3}:g_{1}^{-1}g_{2}g_{3}\in[G,G]\\},\hskip
7.22743pt\Lambda=H\cap\Gamma^{3}.$

Observe that $[H,H]=[G^{3},G^{3}]$. To see this, we see that $[H,H]$ contains
$(1,h,h)$, $(h,h,1)$, and $(h,1,h)$ for $h\in[G,G]$. Since $[G,G]$ is abelian,
(by an abelian Furstenberg-Weiss type argument) it follows that
$[H,H]=[G^{3},G^{3}]$. Letting $T$ be the Horizontal torus of $G/\Gamma$, it
follows that the horizontal Torus of $H/\Lambda$ is $\\{(x,y,z)\in
T^{3}:x+y=z\\}$. It follows that

$\int_{H/\Lambda}F_{1}\otimes F_{2}\otimes F_{3}(h)dhdy=0$

since $\xi\neq 0$. Thus, by quantitative equidistribution on nilmanifolds
(quantnil), it follows that there exists horizontal characters
$\eta_{1},\eta_{2}$ on $G$, at least one of which is nonzero and whose
Lipschitz constants are at most $\delta^{-\exp(O(r)^{O(1)})}$, such that

$\|\eta_{1}(\tilde{g}_{1}(P(y)))+\eta_{2}(\tilde{g}_{2}(Q(y))\|_{C^{\infty}[N]}\leq\delta^{-\exp(O(r)^{O(1)})}.$

Since $\tilde{g}_{1}$ and $\tilde{g}_{2}$ have the same horizontal torus
components as $g$, we have

$\|\eta_{1}(g(P(y)))+\eta_{2}(g(Q(y)))\|_{C^{\infty}[N]}\leq\delta^{-\exp(O(r)^{O(1)})}$

and in fact, as observed by quant, since $\tilde{g}_{1}$ and $\tilde{g}_{2}$
are both periodic modulo $N$, we have

$\|\eta_{1}(\tilde{g}_{1}(P(y))+\eta_{2}(\tilde{g}_{2}(Q(y)))\|_{C^{\infty}[N]}=0$

so

$\|\eta_{1}(g(P(y))+\eta_{2}(g(Q(y)))\|_{C^{\infty}[N]}=0.$

Since $P$ and $Q$ are linearly independent, there exists two binomial
coefficients ${x\choose d}$ and ${x\choose e}$ such that the coefficients
$c_{P,d}$, $c_{P,e}$, $c_{Q,d}$, $c_{Q,e}$ of $P$ and $Q$ of ${x\choose d}$
and ${x\choose e}$ form an invertible matrix. This does not mean that the
matrix is invertible over $\mathbb{Z}$, but this does mean that if

$\eta_{1}(g)c_{P,d}+\eta_{2}(g)c_{Q,d}\equiv 0\pmod{1}$
$\eta_{1}(g)c_{Q,e}+\eta_{2}(g)c_{Q,e}\equiv 0\pmod{1}$

then a multiple of $\eta_{1}(g)$ and $\eta_{2}(g)$, which only depends on $P$
and $Q$, are both zero modulo $1$. Absorbing them both into $\eta_{1}$ and
$\eta_{2}$, we have demonstrated the existence of horizontal characters
$\eta_{1},\eta_{2}$ with $0\leq|\eta_{i}|\leq\delta^{-\exp(O(r)^{O(1)})}$, at
least one of which is nonzero, such that

$\|\eta_{1}(g(P(y)))\|_{C^{\infty}[N]}=\|\eta_{2}(g(Q(y)))\|_{C^{\infty}[N]}=0.$

Thus, the orbit $g(n)\Gamma$ lies on some lower dimensional submanifold of
$G/\Gamma$. We want the orbit to lie on a lower dimensional nilmanifold, but
there is a slight technical obstruction: the “periodic part” of the
nilsequence can be nonzero. More specifically, $\eta_{i}(g)$ can be nonzero.
To overcome this technicality, we split $g(y)=g_{1}(y)g_{2}(y)$ and $g_{1}(y)$
lying on the lower dimensional subgroup $G^{1}$ where $G^{1}=\\{g\in
G:\eta_{i}(g)=0\\}$ whose discrete subgroup is $\Gamma^{1}=\Gamma\cap G^{1}$,
and $g_{2}(y)$ is rational with denominator at most
$\delta^{-\exp(O(r)^{O(1)})}$. To eliminate the rational part, we make a
change of variables $y\mapsto ay$ with $|a|\ll\delta^{-\exp(O(r)^{O(1)})}$
something that cancels out the denominator. This preserves the sum since
$g(y)\Gamma=g(y\pmod{N})\Gamma$. We have thus converted our nilsequence
$F_{1}\otimes F_{2}\otimes F_{3}(g(P(y)+Q(y)),g(P(y)),g(Q(y)))$ to a
polynomial sequence $F_{1}\otimes F_{2}\otimes
F_{3}(g_{1}(aP(y)+aQ(y)),g_{1}(aP(y)),g_{1}(aQ(y)))$ on a lower dimensional
nilmanifold $H^{1}/\Lambda^{1}$ of complexity at most
$\delta^{-\exp(O(r)^{O(1)})}$ with

$H^{1}=\\{(g_{1},g_{2},g_{3})\in(G^{1})^{3}:g_{1}^{-1}g_{2}g_{3}\in[G^{1},G^{1}]\\},\hskip
7.22743pt\Lambda^{1}=H^{1}\cap(\Gamma^{1})^{3}.$

If the nilmanifold is not abelian, then the commutator subgroup
$[G^{1},G^{1}]$ is a nontrivial subgroup of $[G,G]$, so $F_{i}$ is still a
nilcharacter of frequency $\xi$. If $\xi$ annihilates $[G^{1},G^{1}]$, then
$F_{i}(g_{1}(ay))$ descends to a subgroup on a polynomial sequence of degree
two on a degree one nilmanifold and we are essentially done. Otherwise, we
argue as before, picking $h_{1},h_{2}\in[G^{1},G^{1}]$ with denominator $N$
such that $\xi(ah_{1})=\alpha$, $\xi(ah_{2})=\beta$ and absorbing the
$e(\alpha P(y))$ term into $F_{2}(g_{1}(aP(y))\Gamma^{1})$ and the $e(\beta
Q(y))$ term into $F_{3}(g_{1}(aQ(y))\Gamma^{1})$ and repeating the arguments.
Note that since $F$ is $\Gamma$ invariant, it is $\Gamma^{1}$-invariant, so
$F_{i}(\cdot\Gamma^{1})$ makes sense. In addition, while $g_{1}(a\cdot)\Gamma$
is evidently periodic modulo $N$, one can observe that
$g_{1}(a\cdot)\Gamma^{1}$ is also periodic modulo $N$. To see this, observe
that for two $g_{1},g_{2}\in G^{1}$ which descend to the same element in
$G/\Gamma$ satisfies $g_{1}\gamma_{1}=g_{2}$ for some $\gamma_{1}\in\Gamma$.
From this, one can easily see that $\gamma_{1}\in\Gamma^{1}$ since
$g_{1},g_{2}\in G^{1}$.

Reasoning inductively, and using the fact that from lip that $F_{i}$ are
Lipschitz of norm $\delta^{-\exp(O(r)^{O(1)})}$ on the lower dimensional
nilmanifolds it follows that $g(an)\Gamma=g_{1}(an)\Gamma$ with
$g_{1}(n)\Gamma^{1}$ eventually being contained in a degree one nilmanifold
$G^{1}/\Gamma^{1}$ of complexity at most $\delta^{-\exp(O(r)^{O(1)})}$ and
$a\ll\delta^{-\exp(O(r)^{O(1)})}$ (see argument below for discussion on bounds
from the induction). Letting $n\equiv bk\pmod{N}$ with $b\equiv
a^{-1}\pmod{N}$, we see that $g(k)\Gamma=g_{1}(abk)\Gamma=g_{1}(abk)\Gamma$.
This gives the desired result since a $\Gamma$-invariant function is
automatically $\Gamma^{1}$-invariant.

Here, we provide an analysis of the bounds from the induction. Let
$(L_{d},M_{d})$ be the Lipschitz norm of $F$ and the complexity of the
nilmanifold we are working with at stage $d$ of the induction. Analyzing the
induction, we have $M_{d+1}=M_{d}(\delta/L_{d})^{-\exp(cr^{C})}$ and by lip,
$L_{d}=M_{d}^{C_{1}}$ for absolute constants $c,C,C_{1}$ and thus
$M_{d+1}=M_{d}^{1+\exp(cr^{C})}\delta^{-\exp(r^{C})}\leq
M_{d}^{\exp(cr^{C_{2}})}$ for $d>2$. Since we have $M_{0}=O(1)$ and our
induction is carried out $r_{1}=O(r)$ times, this gives
$M_{r_{1}}=(\delta/M_{0})^{-\exp(cr^{C_{2}})^{r_{1}}}=(\delta/M_{0})^{-\exp(r_{1}r^{C_{2}})}$,
which is indeed $\delta^{-\exp(O(r)^{O(1)})}$. The constant $a$ is at most
$M_{d+1}^{C_{3}r}$ for some constant $C_{3}$, so as long as $a$ is less than
$N$, it is relatively prime to $N$, and the argument carries out. This occurs
whenever $\delta^{-\exp(O(r)^{O(1)})}$ is much less than $N$. ∎

Thus, by equidistribution, $F_{h}(m_{h}(n)\Gamma)$ is a polynomial nilsequence
of degree two on a one-step, complexity $\epsilon^{-\exp(O(r)^{O(1)})}$, and
dimension $O(r)^{O(1)}$ manifold. To see how, by equidistribution
$F_{\omega,h}(m_{h}(n)\Gamma)$ is a nilmanifold on a one-step nilmanifold.
Either $m_{h}(n)\Gamma$ lies on the nilmanifold, or there exists a two-step
nilmanifold for which $\xi_{h}$ annihilates the commutator. In either case,
$F_{h}(m_{h}(n)\Gamma)$ is a nilsequence of Lipschitz norm at most
$\epsilon^{\exp(O(r)^{O(1)})}$ on a one-step nilmanifold. We may thus fourier
expand via lipfourier to obtain that there exists some phases
$\alpha_{h},\beta_{h}\in\widehat{\mathbb{Z}/N\mathbb{Z}}$ such that

(1)
$\mathbb{E}_{h}|\langle\mathcal{D}_{h}(f,g,k),e(\beta_{h}x^{2}+\alpha_{h}x)\rangle|^{8}\gg\epsilon^{\exp(O(r)^{O(1)})}.$

Thus, writing

$\beta_{h}(x+P(y)+Q(y))^{2}=\beta_{h}((x+P(y))^{2}+\beta_{h}(x+Q(y))^{2}-\beta_{h}x^{2}+2\beta_{h}P(y)Q(y))$

and

$\alpha_{h}(x+P(y)+Q(y))=\alpha_{h}(x+P(y))+\alpha_{h}(x+Q(y))-\alpha_{h}x,$

we have from (1) that

$\mathbb{E}_{h_{1},\dots,h_{s-1}}|f_{2}(x)g_{2}(x+P(y))k_{2}(x+Q(y))e(\beta_{h}2P(y)Q(y))|^{8}\gg\epsilon^{\exp(O(r)^{O(1)})}$

where

$f_{2}(x)=\Delta_{h}f(x)e(-\beta_{h}x^{2}-\alpha_{h}x),\hskip
7.22743ptg_{2}(x)=\Delta_{h}g(x)e(\beta_{h}x^{2}+\alpha_{h}x),\hskip
7.22743ptk_{2}(x)=\Delta_{h}k(x)e(\beta_{h}x^{2}+\alpha_{h}x).$

By poly, it follows that the above is negligible if $\beta_{h}$ is nonzero.
Thus, we may assume that $\beta_{h}=0$, so by peluse, we may bound the left
hand side above by

$\mathbb{E}_{h_{1},\dots,h_{s-2}}|\mathbb{E}_{x}\Delta_{h}f(x)e(\alpha_{h}x)|^{4}.$

Applying Cauchy-Schwarz (i.e. observing that $|\langle f,e(\alpha
x)\rangle|\leq\|f\|_{U^{2}}$), it follows that

$\|f\|_{U^{s}}\gg\epsilon^{\exp(O(r)^{O(1)})}.$

Defining

$\mathcal{D}(g,k,p)(x)=\mathbb{E}_{y}g(x+P(y))k(x+Q(y))p(x+P(y)+Q(y))$

it follows from Cauchy-Schwarz (the stashing argument) that

$|\Lambda(f,g,k,p)|^{2}\leq\mathbb{E}_{x}\mathcal{D}(g,k,p)\overline{\mathcal{D}(g,k,p)}$
$\|\mathcal{D}(g,k,p)\|_{U^{s}}\gg\epsilon^{\exp(O(r)^{O(1)})}$

so by dual, there exists $\beta_{h}$ such that

$\mathbb{E}_{h_{1},\dots,h_{s-2}}|\langle\mathcal{D}_{h}(g,k,p)(x),e(\beta_{h}x)\rangle|^{2}\gg\epsilon^{\exp(O(r)^{O(1)})}$

Writing
$\beta_{h}x=\beta_{h}(x+P(y))+\beta_{h}(x+Q(y))-\beta_{h}(x+P(y)+Q(y))$, it
follows that

$\mathbb{E}_{h_{1},\dots,h_{s-2}}|\mathbb{E}_{x,y}\Delta_{h}g(x+P(y))e(\beta_{h}(x+P(y)))\Delta_{h}k(x+Q(y))e(\beta_{h}(x+Q(y)))\Delta_{h}p(x+P(y)+Q(y))$
$e(-\beta_{h}(x+P(y)+Q(y)))|\gg\epsilon^{\exp(O(r)^{O(1)})}.$

Applying peluse once again, this is bounded by

$\mathbb{E}_{h_{1},\dots,h_{s-2}}|\mathbb{E}_{x}e(-\beta_{h}(x))p(x)|^{2}$

and using Cauchy-Schwarz, it follows that

$\|p\|_{U^{s}}\gg\epsilon^{\exp(O(r)^{O(1)})}.$

This completes the proof of degreelowering and thus the proof of gowers.

##  Appendix A $U^{3}$ inverse theorem

One key tool we use to deal with Lipschitz functions on nilmanifolds is the
following Fourier expansion lemma.

######  Lemma A.1.

lipfourier Let $f$ be a Lipschitz function on a Torus $\mathbb{T}^{d}$ with
Lipschitz constant $L$ and let $\epsilon>0$. Then there exists a function $g$
on $\mathbb{T}^{d}$ such that

$g(x)=\sum a_{i}e(n_{i}x)$

with

$\sum_{i}|a_{i}|<O(C^{d}(\epsilon(L+1))^{-1})$

and

$\|f(x)-g(x)\|_{\infty}\leq\epsilon.$

###### Proof.

([T1, Proposition 1.1.13]) Let

$K_{R}(x_{1},\dots,x_{d})=\prod_{j=1}^{d}\frac{1}{R}\left(\frac{\sin(\pi
Rx_{j})}{\sin(\pi x_{j})}\right)^{2}$

be the Fejer kernel and let

$F_{R}f(x)=\sum_{k}m_{R}(k_{1},\dots,k_{d})\hat{f}(k)e(kx)$

with

$m_{R}(k)=\int
f(y)K_{R}(x-y)=\prod_{j=1}^{d}\left(1-\frac{|k_{j}|}{R}\right)_{+}.$

Then

$|K_{R}(x)|\leq
C^{d}\prod_{j=1}^{d}R(1+R\|x_{j}\|_{\mathbb{R}/\mathbb{Z}})^{-2}$ $\int
K_{R}(x)dx=1$

so

$\|F_{R}f(x)-f(x)\|_{\infty}\leq C^{d}(L+1)R^{-d}.$

Choosing $R$ to be roughly $\frac{C(L+1)^{1/d}}{\epsilon^{1/d}}$, and using
the fact that $m_{R}\leq 1$, it follows that

$\|F_{R}f(x)-f(x)\|_{\infty}\leq\epsilon$
$\sum_{i}|a_{i}|\leq\frac{C^{d}(L+1)}{\epsilon}.$

∎

The form the $U^{3}$ inverse theorem we will use is the following [JT, Theorem
1.10] (see also [GT4, Theorem 10.4]):

######  Theorem 9.

u3 Let $G$ be a finite additive group, $0<\eta\leq\frac{1}{2}$, and let
$f:G\to\mathbb{C}$ be a 1-bounded function with

$\|f\|_{U^{3}}\geq\eta.$

Then there exists a natural number $N\ll\eta^{-O(1)}$, a polynomial map
$g:G\to H(\mathbb{R}^{N})/H(\mathbb{Z}^{N})$, and a Lipschitz function
$F:H(\mathbb{R}^{N})/H(\mathbb{Z}^{N})\to\mathbb{C}$ of norm
$O(\exp(\eta^{-O(1)}))$ such that

$|\mathbb{E}_{x\in G}f(x)\overline{F}(g(x))|\gg\exp(-\eta^{-O(1)}).$

Here, $H(\mathbb{R}^{N})/H(\mathbb{Z}^{N})$ is essentially an
$O(N)$-dimensional Heisenberg nilmanifold and is defined in [JT].

The $U^{3}$ inverse theorem implies that if $\|f\|_{U^{3}}\geq\delta$, then
there exists a nilcharacter $F(g^{n}\Gamma)$ such that

$|\mathbb{E}_{x}f(x)F(g^{n}\Gamma)|\geq\exp(-\delta^{-O(1)}).$

However, for our application, it is useful for our function to correlate with
a dual-like $U^{3}$ nilcharacter rather than just a nilsequence on a two-step
nilmanifold. Of course, we can always approximate a Lipschitz function as a
sum of nilcharacters via lipfourier. We shall demonstrate below that in some
sense, an $s$-step nilcharacter is equal to its $U^{s+1}$-dual. We will need
the following lemma:

######  Lemma A.2.

word Let $G$ be a $s$-step nilpotent Lie group and $\Gamma$ a discrete co-
compact subgroup. For each $(x_{\omega})_{\omega\in\\{0,1\\}^{s+1}}$ in
$HK^{s+1}(G/\Gamma)$, there exists a smooth function $P$ of the coordinates
$(x_{\omega})_{\omega\in\\{0,1\\}^{s+1}_{*}}$ with
$P((x_{\omega})_{\omega\in\\{0,1\\}^{s+1}_{*}})=x_{0^{s+1}}$.

Here, $HK^{s+1}(G/\Gamma)$ is the Host-Kra nilmanifold. One can find relevant
definitions and treatments in e.g., [GT4, Appendix E] or [T1, Chapter 1.5].
For instance, the proof of the above lemma can be found in [GT4, Appendix E].

######  Lemma A.3 (Dual $U^{s}$ function decomposition, [GT4, Essentially
Proposition 11.2]).

dualus Let $F(x)$ be a nilcharacter of frequency $\xi$ and Lipschitz norm at
most $M$ on a nilmanifold $G/\Gamma$ of step $s$, dimension $r$, and
complexity at most $M$. Let $g(n)$ be a polynomial sequence on $G$. We may
decompose

$F(g(n)\Gamma)=\sum_{\alpha}\prod_{\omega\in\\{0,1\\}^{s+1}_{*}}C^{|\omega|-1}F_{\omega,\alpha}(g(n+h\cdot\omega)\Gamma)+O(\epsilon)$

for all $h$ where there are $O(M/\epsilon)^{O(r)^{O(1)}}$ in the sum and
$F_{\omega,\alpha}$ have Lipschitz norm $O(M/\epsilon)^{O(r)^{O(1)}}$, and
$F_{\omega,\alpha}$ are nilcharacters of frequency $\xi$.

###### Proof.

By word, combined with a partition of unity onto boxes and Fourier expanding
as suggested by [TT], it follows that for any
$(x_{\omega})_{\omega\in\\{0,1\\}^{s+1}}$ in the Host-Kra nilmanifold,

$F(x_{0^{s+1}})=\sum_{\alpha}\prod_{\omega\in\\{0,1\\}^{s+1}_{*}}C^{|\omega|-1}F_{\alpha,\omega}(x_{\omega})+O(\epsilon).$

with the prescribed bounds in the above lemma. Since the Host-Kra nilmanifold
is (by definition) invariant under face transformations, it is invariant by
shifting $x_{0^{s+1}}$ by $g_{s}\in G_{s}$ and $x_{\omega}$ by
$g_{s}^{(-1)^{|\omega|}}$. As a result,

$F(x_{0^{s+1}})=\sum_{\alpha}\overline{\xi(g_{s})}C^{|\omega_{1}|-1}F_{\alpha,\omega_{1}}(x_{\omega_{1}}g_{s}^{(-1)^{|\omega_{1}|}})\prod_{\omega\neq\omega_{1}}C^{|\omega|-1}F_{\alpha,\omega}(x_{\omega})+O(\epsilon).$

Integrating in $g_{s}$, and Fourier expanding $F_{\alpha,\omega_{1}}$ into
vertical characters, it follows that we may assume that
$F_{\alpha,\omega_{1}}$ has vertical frequency $\xi$ for all $\omega_{1}$. The
lemma follows. ∎

##  Appendix B Quantitative Equidistribution on Nilmanifolds

In this section, we shall state the necessary lemmas for the proof of
equidistribution. We shall work with the following conventions of nilmanifolds
(some of which we recalled from the introduction), many of which can be found
in [GT2].

######  Definition.

Let $G_{\circ}$ be a filtered nilpotent Lie Group with $\Gamma$ a discrete
cocompact subgroup. Suppose $X_{1},\dots,X_{n}$ is a Mal’cev basis of $G$ with
integer linear combinations of $X_{i}$ being sent to $\Gamma$ under the
exponential map. Let $\mathfrak{g}$ be the Lie algebra of $G$.

  * •

The dimension of $G$, denoted $m$ is the dimension of $G$.

  * •

The nonlinearity dimension, denoted $m_{*}$, is the dimension of $G_{2}$ minus
the dimension of $G/[G,G]$.

  * •

We will assume that the Mal’cev basis satisfies a nesting property: that is,

$[\mathfrak{g},X_{i}]\subseteq\text{span}(X_{i+1},\dots,X_{m}).$

  * •

Suppose

$[X_{i},X_{j}]=\sum_{k}c_{i,j,k}X_{k}$

with $c_{i,j,k}=\frac{a}{b}$ a rational. The complexity of a Nilmanifold is
the maximum of all $\max(|a|,|b|)$.

In [GT2], Green and Tao prove the following

######  Theorem 10 ([GT2, Theorem 2.9]).

Let $m,d\geq 0$, $0<\delta<\frac{1}{2}$, and $N\geq 1$. Suppose that $G$ is an
$m$-dimensional nilmanifold together with a filtration $G_{\circ}$ with
complexity at most $\frac{1}{\delta}$. Suppose that
$g\in\text{Poly}(\mathbb{Z},G_{\circ})$ is such that $(g(n)\Gamma)$ is not
$\delta$-equidistributed. Then there is a horizontal character $\eta$ with
$0<|\eta|\leq\delta^{-O_{m,d}(1)}$ such that

$\|\eta\circ g\|_{C^{\infty}[N]}\ll\delta^{-O_{m,d}(1)}.$

######  Lemma B.1 ( [GT2, Lemma A.17]).

lip Suppose $G^{\prime}\subseteq G$ be a closed subgroup whose Mal’cev basis
is a rational combination of the Mal’cev basis of $G$ but with numerator and
denominator at most $Q$. Let $d$ be the metric on $G/\Gamma$ and $d^{\prime}$
be an adapted metric on $G^{\prime}/\Gamma^{\prime}$. Then

$d^{\prime}\ll Q^{O(1)}d.$

Thus, an $L$-Lipschitz function on $G$ is an $O(M^{O(1)}L)$-Lipschitz function
on $G^{\prime}$. The following is due to [TT]:

######  Lemma B.2.

quantnil Let $m\geq m_{*}\geq 0$ be integers, $0<\delta<\frac{1}{2}$, $N\geq
1$. Let $G/\Gamma$ be a filtered nilmanifold of degree $d$, nonlinearity
dimension $m_{*}$, dimension $m$, and complexity at most $\frac{1}{\delta}$.
Let $g:\mathbb{Z}\to G$ be a polynomial sequence. If $(g(n)\Gamma)_{n\in[N]}$
is not $\delta$-equidistributed, then there exists a horizontal character
$\eta$ with $0<|\eta|\leq\delta^{-\exp((m+m_{*})^{C_{d}})}$ such that

$\|\eta(g)\|_{C^{\infty}[N]}\leq\delta^{-\exp((m+m_{*})^{C_{d}})}$

In fact, following an observation of [K1], if $g:\mathbb{Z}/N\mathbb{Z}\to
G/\Gamma$ is a polynomial sequence, then one can say something even more: by
taking averages up to $N,2N,3N,4N,\dots$, and observing that the
$C^{\infty}[N]$ norm of the horizontal character does not depend on the $N$,
we in fact have that

$\|\eta(g)\|_{C^{\infty}[N]}=0.$

Thus,

######  Lemma B.3.

quant Let $m\geq m_{*}\geq 0$ be integers, $0<\delta<\frac{1}{2}$, $N\geq 1$.
Let $G/\Gamma$ be a filtered nilmanifold of degree $d$, nonlinearity dimension
$m_{*}$, dimension $m$, and complexity at most $\frac{1}{\delta}$. Let
$g:\mathbb{Z}\to G$ be a polynomial sequence whose quotient map $g(n)\Gamma$
is periodic modulo $N$, a large prime. If $g(n)\Gamma$ is not
$\delta$-equidistributed, then there exists a horizontal character $\eta$ with
$0<|\eta|\leq\delta^{-\exp((m+m_{*})^{C_{d}})}$ such that

$\|\eta(g)\|_{C^{\infty}[N]}=0$

## References

  * [A] D. Altman, _On a Conjecture of Gowers and Wolf_. https://arxiv.org/abs/2106.15437.

  * [BC] J. Bourgain and M-C. Chang _Nonlinear Roth type theorems in finite fields_. Isr. J. Math. 221, 853-867 (2017). https://doi.org/10.1007/s11856-017-1577-9

  * [BL] V. Bergelson and A. Liebman, _Polynomial Extensions of van der Waerden?s and Szemerédi’s Theorems_. JAMS. 09: 725-253 (1996)

  * [BLL] V. Bergelson, A. Liebman, and E. Lesigne, _Intersective Polynomials and Polynomial Szemerédi theorem_. Advances in Mathematics, Elsevier, 2008, 219 (1), pp.369-388.

  * [BM] A. Best and A. Ferré Moragues. _Polynomial ergodic averages for certain countable ring actions_. https://arxiv.org/abs/2105.04008

  * [DLS] D. Dong, X. Li, W. Sawin, _Improved Estimates for Polynomial Roth Type Theorems in Finite Fields_. JAMA 141, 689-705 (2020)

  * [F] H. Furstenberg, _Ergodic Behavior of Diagonal Measures and a Theorem of Szemerédi on Arithmetic Progressions_. Journal d’Analyse Mathématique volume 31, 204-256 (1977)

  * [Fr1] N. Frantzikinakis, _Multiple Ergodic Averages for Three Polynomials and Applications_. Transactions of the American Math Society. 360: 5435-5475 (2006).

  * [Fr2] N. Frantzikinakis, _Joint Ergodicity of Sequences_. https://arxiv.org/abs/2102.09967

  * [FW] H. Furstenberg and B. Weiss. _A mean ergodic theorem for $\frac{1}{N}\sum_{n=1}^{N}f(T^{n})g(T^{n^{2}})$._ _Convergence in ergodic theory and probability_. 193-227 (1996).

  * [G1] W.T. Gowers. _Decompositions, Approximate Structure, Transference, and the Hahn-Banach Theorem_. Bull. Lond. Math. Soc., 42(4):573-606, 2010.

  * [G2] W.T. Gowers, _A New Proof of Szemerédi’s Theorem_. GAFA. 11, 465-588 (2001)

  * [GT1] B. Green and T. Tao, _An Inverse Theorem for the Gowers $U^{3}$ Norm_. https://arxiv.org/pdf/math/0503014.pdf. Proc. Edinb. Math. Soc., 51(1):73-153, 2008.

  * [GT2] B. Green and T. Tao, _The Quantitative Behavior of Polynomial Orbits on Nilmanifolds_. Ann. of Math (2), 171 (3): 1753-1850, 2010

  * [GT3] B. Green, T. Tao _An Arithmetic Regularity Lemma, Associated Counting Lemma, and Applications_. Bolyai Soc. Math. Stud.. 21:261?334, 2010.

  * [GT4] B. Green and T. Tao, _Linear Equations in Primes_. Ann. of Math. 171:1753?1850, 2010

  * [GT5] B. Green and T. Tao, _An inverse theorem for the Gowers $U^{4}$ norm_. Glasg. Math. J., 53(1):1-50, 2011.

  * [GTZ] B. Green, T. Tao, and T. Ziegler _An inverse theorem for the Gowers $U^{s+1}[N]$-norm_. Ann. of Math. 176: 1231-1372 (2012)

  * [GW1] W.T. Gowers and J. Wolf, _Linear forms and higher-degree uniformity for functions on $\mathbb{F}_{p}^{n}$_. GAFA, Springer Verlag, 2011, 21 (1), pp.36-69.

  * [GW2] W.T. Gowers and J. Wolf, _Linear forms and quadratic uniformity for functions on $\mathbb{Z}/N\mathbb{Z}$_. Journal d’Analyse Mathématique. Vol 115.

  * [GW3] W.T. Gowers and J. Wolf, _Linear Forms and Higher-Degree Uniformity for Functions On $\mathbb{F}_{p}^{n}$_. GAFA. 21: 36-69 (2011).

  * [JT] A. Jamneshan and T. Tao, _The inverse theorem for the $U^{3}$ Gowers uniformity norm on arbitrary finite abelian groups: Fourier-analytic and ergodic approaches_, https://arxiv.org/abs/2112.13759

  * [K1] B. Kuca, _True Complexity of Polynomial Progressions in Finite Fields_. Proceedings of the Edinburgh Mathematical Society. 64:448-500 (2021)

  * [K2] B. Kuca, _On Several Notions of Complexity of Polynomial Progressions_. _Ergodic Theory and Dynamical Systems_ , 1-55. doi:10.1017/etds.2021.171

  * [K3] B. Kuca, _Multidimensional polynomial Szemerédi theorem in finite fields for polynomials of distinct degrees_. https://arxiv.org/abs/2103.12606

  * [K4] B. Kuca, _Further bounds in the polynomial Szemerédi theorem over finite fields_. Acta Arithmetica 198 (2021), 77-108.

  * [M] F. Manners, _True Complexity and Iterated Cauchy-Schwarz_ , https://arxiv.org/abs/2109.05731

  * [P1] S. Peluse, _Polynomial Szemerédi Theorem in Finite Fields_. Duke Math. J. 168 (2019), no. 5, 749-774.

  * [P2] S. Peluse, _Bounds for Sets with no Polynomial Progressions_. Forum Math. Pi 8 (2020), e16.

  * [P3] S. Peluse, _Three-term polynomial progressions in subsets of finite fields_. Israel J. Math. 228 (2018), no. 1, 379-405.

  * [Pr1] S. Prendiville, _The Inverse Theorem for The Nonlinear Roth Configuration: an Exposition_. https://arxiv.org/abs/2003.04121

  * [Pr2] S. Prendiville _Quantitative Bounds in the Polynomial Szemerédi Theorem: the Homogeneous Case_. Discrete Analysis (2017)

  * [PP1] S. Peluse and S. Prendiville, _Quantitative Bounds in the Nonlinear Roth Theorem_. https://arxiv.org/abs/1903.02592.

  * [PP2] S. Peluse and S. Prendiville _A Polylogarithmic Bound in the Nonlinear Roth Theorem_. International Mathematics Research Notices (to appear).

  * [PP3] S. Peluse and S. Prendiville _Quantitative Bounds in the Nonlinear Roth Theorem (version 1)_. https://arxiv.org/abs/1903.02592v1

  * [R] K. Roth, _On Certain Sets of Integers_. Journal of the London Math Society. s1.28: 104-109 (1953).

  * [S] E. Szemerédi, _On Sets of Integers Containing no $k$ Elements in Arithmetic Progression_. Proceedings of the International Congress of Mathematicians. Vancouver, 1974

  * [T1] T. Tao, _Higher Order Fourier Analysis_. Graduate Studies in Mathematics. Vol 42. AMS, Providence, RI, 2012.

  * [T2] T. Tao, _Cut Norms and Degree Lowering_ , https://terrytao.wordpress.com/2020/03/08/cut-norms-and-degree-lowering/

  * [T3] T. Tao, _The Gowers uniformity norm of order $1+$_, https://terrytao.wordpress.com/2021/07/25/the-gowers-uniformity-norm-of-order-1/

  * [TT] T.Tao and J. Teräväinen, _Quantitative Bounds for Gowers Uniformity of the Möbius and von Mangoldt Functions_ , https://arxiv.org/abs/2107.02158

  * [TV] T. Tao and V. Vu, _Additive Combinatorics_. Canbridge Studies in Advanced Mathematics. 105 (2006).