is a nilmanifold of dimension $d$, complexity $M$, degree $K$, and $g(n)$ is a
polynomial sequence on $G$ with $g(n)\Gamma$ periodic. Suppose we may write
$g(n)=\epsilon g_{1}(n)\gamma(n)$ with $g_{1}(0)=\gamma(0)=\mathrm{id}_{G}$,
$g_{1}$ has image in a $Q$-rational subgroup $G^{\prime}$ of $G$ and $\gamma$
is $Q$-rational. Then either $N\ll(MQ)^{O_{k}(d)^{O_{k}(1)}}$ or there exists
some $g^{\prime}$ and $\gamma^{\prime}$ such that $g(n)=\epsilon
g^{\prime}(n)\gamma^{\prime}(n)$ where $g^{\prime}$ is $N$-periodic and has
image in $G^{\prime}$, and the image of $\gamma^{\prime}$ lies in $\Gamma$.

###### Proof.

Since $\gamma$ is $Q$-rational, it follows from [13, Lemma B.14] that
$\gamma(H\cdot)$ has image in $\Gamma$ for some positive integer
$H\ll(MQ)^{O_{k}(d)^{O_{k}(1)}}$. Suppose it is not true that
$N\ll(MQ)^{O_{k}(d)^{O_{k}(1)}}$. Then letting $H^{\prime}$ be the
multiplicative inverse of $H$ modulo $N$, it follows that

$g(H^{\prime}Hn)=g(n)\gamma_{1}(n)$

for some polynomial sequence $\gamma_{1}$ where $\gamma_{1}(n)\in\Gamma$ for
all $n$. In addition, we see that $g_{1}(H\cdot)\Gamma$ is $N$-periodic since
$\gamma(H\cdot)$ has image in $\Gamma$ and $g$ is $N$-periodic. Hence,
$g_{1}(H^{\prime}H\cdot)\Gamma$ is $N$-periodic. Thus,

$g(H^{\prime}Hn)=g(n)\gamma_{1}(n)=\epsilon
g_{1}(H^{\prime}Hn)\gamma(H^{\prime}Hn).$

Letting $g^{\prime}(n)=g_{1}(H^{\prime}Hn)$ and
$\gamma^{\prime}(n)=\gamma(H^{\prime}Hn)\gamma_{1}(n)^{-1}$, we obtain the
desired result. ∎

We will also need the following two lemmas about periodic nilsequences:

######  Lemma A.4.

periodictorus Let $g\colon\mathbb{Z}\to\mathbb{R}/\mathbb{Z}$ be a polynomial
of degree $k$ with $g$ periodic modulo $N>k!$ a prime. Then
$\|g\|_{C^{\infty}[N]}=0$.

###### Proof.

This follows from [22, Lemma 1.4.1]. ∎

Before we state the below lemma, we recall [13, Definition 4.1] of $g_{2}(n)$
given a polynomial sequence $g(n)$ with $g(0)=\mathrm{id}_{G}$:
$g_{2}(n)=g(n)g(1)^{-n}$.

######  Lemma A.5.

periodic Let $N>100$ be prime and $G/\Gamma$ be a nilmanifold of degree $k$
and $g\in\mathrm{poly}(\mathbb{Z},G)$ with $g(n)\Gamma$ be a periodic modulo
$N$ with $N$ larger than $k!$. Then for any horizontal characters $\eta\colon
G/[G,G]\to\mathbb{R}$ and $\eta^{2}\colon G_{2}/[G,G_{2}]\to\mathbb{R}$, we
have (abusively descending $g$)

$\|N\eta\circ g\|_{C^{\infty}[N]}=0\text{ and }\|k!^{2}N\eta^{2}\circ
g\|_{C^{\infty}[N]}=0$

###### Proof.

The first part of the statement follows from periodictorus. For the second
part, we recall the definition of $G^{\square}:=G\times_{G_{2}}G$ and
$\Gamma^{\square}:=\Gamma\times_{G_{2}\cap\Gamma}\Gamma$, from [13, Definition
4.2] (see also the proof of twostepcase). For $h\in\mathbb{N}$, we define
$g_{h}(n)=(\\{g(1)^{h}\\}^{-1}g_{2}(n+h)g(1)^{-n}\\{g(1)^{h}\\},g(n))$. It
follows that $g_{h}(n)\Gamma^{\square}$ is $N$-periodic.

Let $\eta$ be a horizontal character on $G^{\square}$. By [13, Lemma A.3], we
may decompose $\eta(g^{\prime},g)=\eta^{1}(g)+\eta^{2}(g^{\prime}g^{-1})$
where $\eta^{1}\colon G/[G,G]\to\mathbb{R}$ and $\eta^{2}\colon
G_{2}/[G_{2},G]\to\mathbb{R}$. Hence,

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

We see that $\eta^{1}(g(n))\equiv 0\pmod{1/N}$, and
$\eta^{2}([g(1)^{n},\\{g(1)^{h}\\}])=\eta^{2}([g(1)^{n},[g(1)^{h}]])\equiv
0\pmod{1/N}$. Hence, it follows that letting $Q(n)=\eta^{2}(g_{2}(n))$, we
have that

$Q(n+h)-Q(n)-Q(h)\equiv 0\pmod{1/N}.$

Let

$Q(n)=\sum_{i\geq 2}\alpha_{i}{n\choose i}.$

We see from Vandermonde’s identity that

${n+h\choose i}=\sum_{0\leq t\leq i}{n\choose t}{h\choose i-t}$

so

$Q(n+h)=\sum_{t=0}^{k}{n\choose t}\sum_{k\geq
i\geq\max(t,2)}\alpha_{i}{h\choose i-t}$ $Q(n+h)-Q(n)-Q(h)={n\choose
1}\sum_{i\geq 2}^{k}\alpha_{i}{h\choose i-1}+\sum_{t=2}^{k}{n\choose
t}\sum_{k\geq i>t}\alpha_{i}{h\choose i-t}.$

It follows that for each $t\geq 2$,

$\sum_{k\geq i>t}\alpha_{i}{h\choose i-t}\equiv 0\pmod{1/(k!N)}$

and from Pólya’s classification of integer polynomials [20], it follows that
$\alpha_{i}\equiv 0\pmod{k!N}$. In addition, we see that

$\sum_{i\geq 2}^{k}\alpha_{i}{h\choose i-1}\equiv 0\pmod{1/(k!N)}$

which also implies that $\alpha_{2}\equiv 0\pmod{k!N}$. Changing bases of $Q$
to monomials $n^{I}$ instead of binomials ${n\choose I}$ costs another factor
of $k!$, so

$\|k!^{2}N\eta^{2}\circ g\|_{C^{\infty}[N]}=0.$

∎

######  Remark A.1.

Note that it is not necessarily true that $g((10^{k}k)!n)$ has all of its
coordinates with denominator $N$ as the following example shows:

$g(n)=\begin{pmatrix}1&a\alpha&a\beta&a\alpha\beta\\\ 0&1&0&\beta\\\
0&0&1&\alpha\\\ 0&0&0&1\end{pmatrix}^{n}$

with $a\in\mathbb{Z}$, $\alpha,\beta\in\widehat{\mathbb{Z}/N\mathbb{Z}}$. One
can check that if $G$ is the group where we replace
$a\alpha,b\beta,\alpha,\beta,a\alpha\beta$ with arbitrary real numbers, and
$\Gamma$ is the subgroup where all of the corresponding entries are integers,
then $g(n)\Gamma$ is $N$-periodic if $\alpha$ and $\beta$ have denominator
$N$. Note that this example corresponds to the $N$-periodic bracket polynomial
$n\mapsto e(a\\{\alpha n\\}\\{\beta n\\})$. The example also shows that if we
were to add a quadratic part to the upper right corner of $g$, in order for
the nilsequence to stay $N$-periodic, the coefficient of the quadratic part
must have denominator $N$. This is equivalent to saying that if we were to add
higher order parts to $g$, then the horizontal component of $g_{2}$ must have
denominator $N$, as the lemma claims.

##  Appendix B Fourier compleity lemmas

The purpose of this section is to collect results needed in Section 3 and
Section 8 regarding “Fourier expansion” lemmas for bracket polynomials. Before
we state and prove them, we require the following definition.

######  Definition B.1.

We define the $L^{p}[N]$ (likewise $L^{p}([N]\times[H])$) $\delta$-_Fourier
complexity_ of a function $f:[N]\to\mathbb{C}$ to be the infimum of all $L$
such that

$f(n)=\sum_{i}a_{i}e(\xi_{i}n)+g$

where $\|g\|_{L^{p}[N]}\leq\delta$ and $\sum_{i}|a_{i}|=L$.

######  Lemma B.1 (Fourier Complexity Lemma).

onevarfouriercomplexity Let

$\alpha_{1},\dots,\alpha_{d},\beta_{1},\dots,\beta_{d},\gamma_{1},\dots,\gamma_{d},\gamma_{1}^{\prime},\dots,\gamma_{d}^{\prime}\in\mathbb{R}$

and let $\delta>0$ a real number and $N>0$ an integer. Then either
$N\ll(\delta/2^{d}k)^{-O(d)^{2}}$ or else

$e(k_{1}\\{\alpha_{1}n+\gamma_{1}\\}\\{\beta_{1}n+\gamma_{1}^{\prime}\\}+k_{2}\\{\alpha_{2}n+\gamma_{2}\\}\\{\beta_{2}n+\gamma_{2}^{\prime}\\}+\cdots
k_{d}\\{\alpha_{d}n+\gamma_{d}\\}\\{\beta_{d}n+\gamma_{d}^{\prime}\\})$

has $L^{1}([N])$-$\delta$-Fourier complexity at most
$(\delta/2^{d}k)^{-O(d^{2})}$ for $|k_{i}|\leq k$ integers. Furthermore, if
$\alpha_{i},\beta_{i}$ are rational with denominator $N$ and $N$ is prime,
then the phases in the Fourier expansion can also be taken to be rational with
denominator $N$ (and consequently $g$ is periodic modulo $N$).

###### Proof.

Let

$\phi(n,h)=k_{1}\\{\alpha_{1}n+\gamma_{1}\\}\\{\beta_{1}n+\gamma_{1}^{\prime}\\}+k_{2}\\{\alpha_{2}n+\gamma_{2}\\}\\{\beta_{2}n+\gamma_{2}^{\prime}\\}+\cdots
k_{d}\\{\alpha_{d}n+\gamma_{d}\\}\\{\beta_{d}n+\gamma_{d}^{\prime}\\}.$

The function $e(\phi(n,h))$ resembles a degree one nilsequence on a torus
$\mathbb{T}^{2d}$ except with possible discontinuities at the endpoints
$x_{i}=\frac{1}{2}\pmod{1}$. To remedy this possible issue, we must set
ourselves in a position so that the endpoints contribute very little to the
$L^{1}([N])$ norm. In the periodic nilsequences case, this will end up being
true since $N$ is prime and $\alpha_{i}$ and $\beta_{i}$ will always have
denominator $N$. In this case, one can multiply $e(\phi(n))$ by smooth cutoff
supported supported in $(-1/2,1/2)$ and equal to one on
$[-1/2+(\delta/2^{d}k),1/2-(\delta/2^{d}k)]^{2d}$ of derivative at most
$(\delta/2^{d}k)^{-1}$ and Fourier expand everything. The terms for which we
have ignored from taking cutoff contribute an $L^{1}([N])$ norm at most
$\delta/2^{d-1}$ since
$\\{n\in[N]:\|\alpha_{i}n-\frac{1}{2}\|_{\mathbb{R}/\mathbb{Z}}<\delta\\}$ has
at most $2\delta N$ many elements (and similarly for each $\beta_{i}$) since
each $\alpha_{i}$ has denominator $N$. Since each Fourier phase is an integer
combination of the $\alpha_{i}$’s and $\beta_{i}$’s, it follows that each
element of the Fourier expansion is rational of denominator $N$. Thus, we have
obtained the desired Fourier complexity bounds with the desired properties.
For the sake of this paper, we will only need the periodic case; for
completeness sake, we give a proof of the more general Fourier complexity
lemma.

In the general case, this is proven via an induction on dimensions procedure
so our goal is to show that this does not lead to double exponential losses in
parameters. This involves carefully quantifying the procedure in [8, Appendix
E] and making sure that losses are only single exponential in dimension.
Morally, the reason why we are able to obtain single exponential bounds in
dimension is that we only desire equidistribution on each of the phases
$\alpha_{i},\beta_{i}$ individually, and not the joint equidistribution in
$\mathbb{R}^{2d}$; this makes it so that the bounds don’t feed back into
themselves in iteration. For example, in the case where $N$ is prime and each
$\alpha_{i}$ are equal, the suggested procedure works without any further
modification since $\alpha n$ for $\alpha$ nonzero is well-equidistributed in
$S^{1}$. Let $1>\epsilon>0$ be a quantity to be determined later. If
$\\{n\in[N]:\|\alpha_{1}n+\gamma_{1}-\frac{1}{2}\|_{\mathbb{R}/\mathbb{Z}}<\epsilon\\}$
has more than $\sqrt{\epsilon}N$ many elements, then an application of
Vinogradov’s Lemma shows that there exists some integer
$q_{1}\leq\sqrt{\epsilon}^{-1}$ such that
$\|q_{1}\alpha_{1}\|_{\mathbb{R}/\mathbb{Z}}\leq
100\frac{\sqrt{\epsilon}}{H}$. We now divide $[N]$ into progressions of common
difference $q_{1}$ such that on each progression, $\\{\alpha_{1}n\\}$ varies
by at most $\epsilon^{1/2}$. This can be done as follows:

  * •

First, divide $[N]$ into progressions of common difference $q_{1}$.

  * •

On each progression, we have that $\alpha_{1}n$ varies by at most
$\sqrt{\epsilon}$ modulo $1$; however, it is possible that
$\\{\alpha_{1}n+\gamma_{1}\\}$ “lapped over” $1/2$ along the progression, so
we must divide each progression into two subprogressions, one before
$\\{\alpha_{1}n\\}$ lapped over $1/2$ and one after it lapped over $1/2$.

  * •

The number of progressions we obtain is at most $200q_{1}$.

Thus, we may divide $[N]=\bigsqcup P_{i}$ into such progressions. We shall
want to “prune out” the small progressions and write $[N]=\bigsqcup
P_{i}\sqcup E$ where $P_{i}^{\prime}$ are sufficiently large and $E$ is a
small error. If $|P_{i}|\leq\epsilon^{1+1/2}N$, then we include it in $E$ and
otherwise, we do nothing. Thus, we can ensure that
$|P_{i}|\geq\epsilon^{1+1/2}N$ and $|E|\leq 200q_{1}\epsilon^{1+1/2}N\leq
200\epsilon N$.

We now iterate in the following manner: if
$\\{n\in[N]:\|\alpha_{2}n+\gamma_{2}-\frac{1}{2}\|_{\mathbb{R}/\mathbb{Z}}<\epsilon\\}$
has more than $\sqrt{\epsilon}N$ many elements, then (assuming that $\epsilon$
is sufficiently small) there exists a progression $P$ (as in the decomposition
above) such that $\\{h\in
P:\|\alpha_{2}n+\gamma_{2}-\frac{1}{2}\|_{\mathbb{R}/\mathbb{Z}}<\epsilon\\}$
has more than $\frac{\sqrt{\epsilon}}{2}|P|$ many elements, then writing
$P=q_{1}\cdot[N_{1}]+r_{1}$, it follows that there are more than
$\frac{\sqrt{\epsilon}}{2}N_{1}$ many elements in
$\\{n\in[N_{1}]:\|q_{1}\alpha_{2}n+\gamma\|_{\mathbb{R}/\mathbb{Z}}<\epsilon\\}$
for some $\gamma$. Letting $n$ and $m$ be two such elements, it follows that
$\|q_{1}\alpha_{2}(n-m)\|_{\mathbb{R}/\mathbb{Z}}\leq\|-\gamma-
q_{1}\alpha_{2}m\|_{\mathbb{R}/\mathbb{Z}}+\|q_{1}\alpha_{2}n+\gamma\|_{\mathbb{R}/\mathbb{Z}}\leq
2\epsilon$, so there are more than $\frac{\sqrt{\epsilon}}{2}|P|$ many
elements such $n\in[N_{1}]$ such that
$\|q_{1}\alpha_{2}\|_{\mathbb{R}/\mathbb{Z}}<2\epsilon$. Thus, (assuming that
$N$ is sufficiently large with respect to $\epsilon$) there exists some
$q_{2}\leq 2\sqrt{\epsilon}^{-1}$ such that
$\|q_{1}q_{2}\alpha_{2}\|_{\mathbb{R}/\mathbb{Z}}\leq\frac{200\sqrt{\epsilon}}{|P|}$.
We now continue down a similar path, dividing each $P_{i}$ into
subprogressions instead of dividing $[N]$ into subprogressions, this time
obtaining an error set of size at most $4\epsilon|P_{i}|$.

Under an iteration (making sure to choose $\epsilon$ so that
$\frac{\sqrt{\epsilon}}{200^{2d}}>\epsilon$), we would obtain at most
$\epsilon^{-d}200^{2d}$ many progressions each of size at least
$\epsilon^{3d}N$ and common difference at most $\epsilon^{-d}$ such that

  * •

either $n\mapsto\\{\alpha_{i}n+\gamma_{i}\\}$ or
$n\mapsto\\{\beta_{i}n+\gamma_{i}^{\prime}\\}$ varies by at most
$\epsilon^{1/2}$ on each progression;

  * •

or the set
$\\{n\in[N]:\|\alpha_{i}n+\gamma_{i}-\frac{1}{2}\|_{\mathbb{R}/\mathbb{Z}}<\epsilon\\}$
has at most $\sqrt{\epsilon}N$ many elements (or similarly the set
$\\{n\in[N]:\|\beta_{i}n+\gamma_{i}^{\prime}-\frac{1}{2}\|_{\mathbb{R}/\mathbb{Z}}<\epsilon\\}$
has at most $\sqrt{\epsilon}N$ many elements);

and an error set $E$ of size at most $200^{2d}\epsilon 2N$. For the
$\alpha_{i}$’s or $\beta_{i}$’s that lie in the second case, we introduce a
smooth cutoff $\varphi_{j}$ of derivative at most $\epsilon^{-1}$ in the
dimensions that correspond to the $\alpha_{i}$’s or $\beta_{i}$’s. Thus,
letting $F(\vec{x},\vec{y})=e(k_{1}x_{1}y_{1}+\cdots+k_{d}x_{d}y_{d})$ and
letting the above decomposition be $[N]=\bigsqcup_{i}P_{i}\sqcup E$, it
follows that we may express

$e(\phi(n,h))=F(\\{\alpha n\\},\\{\beta n\\})=\varphi(\\{\alpha n\\},\\{\beta
n\\})F(\\{\alpha n\\},\\{\beta n\\})+O_{L^{1}([N]),\leq 1}(2d\epsilon^{1/2})$

where $O_{L^{1}([N]),\leq C}(k)$ denotes a function in $L^{1}([N])$ whose norm
is at most $Ck$ (i.e., $\leq 1$ denotes that the implicit constant is $\leq
1$). We now take

$\phi(\\{\alpha n\\},\\{\beta n\\})F(\\{\alpha n\\},\\{\beta
n\\})=\sum_{i}1_{P_{i}}(n)\varphi(\\{\alpha n\\},\\{\beta n\\})F(\\{\alpha
n\\},\\{\beta n\\})+O_{L^{1}([N]),\leq 1}(200^{2d}2\epsilon).$

For each of the remaining phases $\alpha_{i}$, $\beta_{j}$ that are not
covered by first case in the above bulleted points, we may take some phase
$\alpha_{i}^{0}$ or $\beta_{j}^{0}$ such that
$|\\{\alpha_{i}n+\gamma_{i}\\}-\\{\alpha_{i}^{0}\\}|\leq\epsilon^{1/2}$.
Making sure to choose $\epsilon$ so that $k\epsilon^{1/2}<1/100$, it follows
that we may replace $F(\\{\alpha n\\},\\{\beta n\\})$ by some
$\tilde{F}(\\{\alpha n\\},\\{\beta n\\})$ which is equal to
$\\{\alpha_{i}^{0}\\}$ and $\\{\beta_{j}^{0}\\}$ on please $i$ in the
$\vec{x}$ variable and place $j$ in the $\vec{y}$ variable. We thus have

$\sum_{i}1_{P_{i}}(n)\varphi(\\{\alpha n\\},\\{\beta n\\})F(\\{\alpha
n\\},\\{\beta n\\})$ $=\sum_{i}1_{P_{i}}(n)\varphi(\\{\alpha n\\},\\{\beta
n\\})\tilde{F}(\\{\alpha n\\},\\{\beta n\\})+O_{L^{\infty}([N]),\leq
1}(2dk\epsilon^{1/2})$

(here, we are also implicitely using the inequality
$|e(\epsilon)-1|\leq|\epsilon|$). Now, each $P_{i}$ can be written as a
product of $P_{i}^{1}\times P_{i}^{2}$ (one in $h$ variable, one in $n$
variable). We may also write $P_{i}^{j}$ as a product of an interval $1_{I}$
and some $1_{n\equiv a\pmod{q}}$. The interval we can approximate in
$L^{1}[N]$ (or respectivly, $L^{1}[N]$) with a $g(n/N)$ where $g$ is a
Lipschitz function with norm at most $\epsilon^{-1/2}$ up to an error of at
most $2\epsilon^{1/2}|I|$. Each $1_{n\equiv a\pmod{q}}$ can also be thought of
as a Lipschitz function on the torus with norm at most $q$ (which in our case
will be at most $\epsilon^{-d}$). Thus, we may write:

$\sum_{i}\tilde{F}_{P_{i}}(\\{\alpha n\\},\\{\beta n\\})+O_{L^{1}([N]),\leq
1}(4\epsilon^{1/2})$

where each $\tilde{F}_{P_{i}}$ is a product of $\tilde{F}$ and $g$ and
$1_{n\equiv a\pmod{q}}$ functions associated to the progression $P_{i}$ and
has Lipchitz norm at most $(2d+4)\epsilon^{-1/2}$ and is defined on a $2d+4$
dimensional torus $\mathbb{R}^{2d+4}/\mathbb{Z}^{2d+4}$. Fourier expanding
each $\tilde{F}_{P_{i}}$ via [13, Lemma A.6] (taking
$\delta=\frac{\epsilon^{d+3/2}}{3(2d+4)200^{2d}}$), we obtain

$\sum_{i}\tilde{F}_{P_{i}}(\\{\alpha n\\},\\{\beta
n\\})=\sum_{\xi}a_{\xi}e(\xi\cdot n)+O_{L^{\infty}([N]),\leq 1}(\epsilon)$

where (in fact we can take $|a_{\xi}|\leq 1$)

$\sum_{\xi}|a_{\xi}|\leq O(\epsilon)^{-O(d)^{2}}.$

Summing up all the errors together gives an $L^{1}([N])$ error of at most
$O(dk\epsilon^{1/2})$. Now choosing $\epsilon$ so that (each of the conditions
we placed on $\epsilon$ are satisfied before and) $dk\epsilon^{1/2}\ll\delta$,
we obtain the claim. ∎

######  Lemma B.2 (Bilinear Fourier Complexity Lemma).

bilinearfouriercomplexity Let

$\alpha_{1},\dots,\alpha_{d},\beta_{1},\dots,\beta_{d},\gamma_{1},\dots,\gamma_{d},\gamma_{1}^{\prime},\dots,\gamma_{d}^{\prime}\in\mathbb{R}$

and let $\delta>0$ a real number and $N,H>0$ integers. Then either
$N\ll(\delta/3^{d}k)^{-O(d)^{2}}$, or $H\ll(\delta/3^{d}k)^{-O(d)^{2}}$ or
else

$e(k_{1}\\{\alpha_{1}h+\gamma_{1}\\}\\{\beta_{1}n+\gamma_{1}^{\prime}\\}+k_{2}\\{\alpha_{2}h+\gamma_{2}\\}\\{\beta_{2}n+\gamma_{2}^{\prime}\\}+\cdots
k_{d}\\{\alpha_{d}n+\gamma_{d}\\}\\{\beta_{d}h+\gamma_{d}^{\prime}\\})$

has $L^{1}([N]\times[H])$-$\delta$-Fourier complexity at most
$(\delta/3^{d}k)^{-O(d^{2})}$ for $|k_{i}|\leq k$ real. Furthermore, if $N,H$
are prime and $\alpha_{i}$ are rational with denominator $N$ and $\beta_{i}$
are rational with denominator $H$, then the phases in the Fourier expansion
can be taken to be $e(cn+dh)$ where $c$ is rational with denominator $N$ and
$d$ is rational with denominator $H$.

###### Proof.

The proof is very similar to that of onevarfouriercomplexity. Let

$\phi(n,h)=k_{1}\\{\alpha_{1}h+\gamma_{1}\\}\\{\beta_{1}n+\gamma_{1}^{\prime}\\}+k_{2}\\{\alpha_{2}h+\gamma_{2}\\}\\{\beta_{2}n+\gamma_{2}^{\prime}\\}+\cdots
k_{d}\\{\alpha_{d}h+\gamma_{d}\\}\\{\beta_{d}n+\gamma_{d}^{\prime}\\}.$

The function $e(\phi(n,h))$ resembles a degree one nilsequence on a torus
$\mathbb{T}^{2d}$ except with possible discontinuities at the endpoints
$x_{i}=\frac{1}{2}\pmod{1}$. To remedy this possible issue, we must set
ourselves in a position so that the endpoints contribute very little to the
$L^{1}([N]\times[H])$ norm. This is not problematic if $H=N$ and
$\alpha_{i},\beta_{i}$ are rational with denominator $N$ with $N$ prime. By
arguing similarly as onevarfouriercomplexity, we obtain the desired conclusion
in this case.

Let $1>\epsilon>0$ be a quantity to be determined later. If
$\\{h\in[H]:\|\alpha_{1}h+\gamma_{1}-\frac{1}{2}\|_{\mathbb{R}/\mathbb{Z}}<\epsilon\\}$
has more than $\sqrt{\epsilon}H$ many elements, then an application of
Vinogradov’s Lemma shows that there exists some integer
$q_{1}\leq\sqrt{\epsilon}^{-1}$ such that
$\|q_{1}\alpha_{1}\|_{\mathbb{R}/\mathbb{Z}}\leq
100\frac{\sqrt{\epsilon}}{H}$. We now divide $[H]$ into progressions of common
difference $q_{1}$ such that on each progression, $\\{\alpha_{1}h\\}$ varies
by at most $\epsilon^{1/2}$. This can be done as follows:

  * •

First, divide $[H]$ into progressions of common difference $q_{1}$.

  * •

On each progression, we have that $\alpha_{1}h$ varies by at most
$\sqrt{\epsilon}$ modulo $1$; however, it is possible that
$\\{\alpha_{1}h+\gamma_{1}\\}$ “lapped over” $1/2$ along the progression, so
we must divide each progression into two subprogressions, one before
$\\{\alpha_{1}h\\}$ lapped over $1/2$ and one after it lapped over $1/2$.

  * •

The number of progressions we obtain is at most $200q_{1}$.

Thus, we may divide $[H]=\bigsqcup P_{i}$ into such progressions. We shall
want to “prune out” the small progressions and write $[H]=\bigsqcup
P_{i}\sqcup E$ where $P_{i}^{\prime}$ are sufficiently large and $E$ is a
small error. If $|P_{i}|\leq\epsilon^{1+1/2}H$, then we include it in $E$ and
otherwise, we do nothing. Thus, we can ensure that
$|P_{i}|\geq\epsilon^{1+1/2}N$ and $|E|\leq 200q_{1}\epsilon^{1+1/2}H\leq
200\epsilon H$.

We now iterate in the following manner: if
$\\{h\in[H]:\|\alpha_{2}h+\gamma_{2}-\frac{1}{2}\|_{\mathbb{R}/\mathbb{Z}}<\epsilon\\}$
has more than $\sqrt{\epsilon}H$ many elements, then (assuming that $\epsilon$
is sufficiently small) there exists a progression $P$ (as in the decomposition
above) such that $\\{h\in
P:\|\alpha_{2}h+\gamma_{2}-\frac{1}{2}\|_{\mathbb{R}/\mathbb{Z}}<\epsilon\\}$
has more than $\frac{\sqrt{\epsilon}}{2}|P|$ many elements, then writing
$P=q_{1}\cdot[H_{1}]+r_{1}$, it follows that there are more than
$\frac{\sqrt{\epsilon}}{2}N_{1}$ many elements in
$\\{h\in[H_{1}]:\|q_{1}\alpha_{2}h+\gamma\|_{\mathbb{R}/\mathbb{Z}}<\epsilon\\}$
for some $\gamma$. Letting $n$ and $m$ be two such elements, it follows that
$\|q_{1}\alpha_{2}(n-m)\|_{\mathbb{R}/\mathbb{Z}}\leq\|-\gamma-
q_{1}\alpha_{2}m\|_{\mathbb{R}/\mathbb{Z}}+\|q_{1}\alpha_{2}n+\gamma\|_{\mathbb{R}/\mathbb{Z}}\leq
2\epsilon$, so there are more than $\frac{\sqrt{\epsilon}}{2}|P|$ many
elements such $h\in[H_{1}]$ such that
$\|q_{1}\alpha_{2}\|_{\mathbb{R}/\mathbb{Z}}<2\epsilon$. Thus, (assuming that
$N$ is sufficiently large with respect to $\epsilon$) there exists some
$q_{2}\leq 2\sqrt{\epsilon}^{-1}$ such that
$\|q_{1}q_{2}\alpha_{2}\|_{\mathbb{R}/\mathbb{Z}}\leq\frac{200\sqrt{\epsilon}}{|P|}$.
We now continue down a similar path, dividing each $P_{i}$ into
subprogressions instead of dividing $[N]$ into subprogressions, this time
obtaining an error set of size at most $4\epsilon|P_{i}|$.

Under an iteration (making sure to choose $\epsilon$ so that
$\frac{\sqrt{\epsilon}}{200^{2d}}>\epsilon$), we would obtain at most
$\epsilon^{-d}200^{2d}$ many progressions each of size at least
$\epsilon^{3d}NH$ and common difference at most $\epsilon^{-d}$ such that

  * •

either $h\mapsto\\{\alpha_{i}h+\gamma_{i}\\}$ or
$n\mapsto\\{\beta_{i}n+\gamma_{i}^{\prime}\\}$ varies by at most
$\epsilon^{1/2}$ on each progression;

  * •

or the set
$\\{h\in[H]:\|\alpha_{i}h+\gamma_{i}-\frac{1}{2}\|_{\mathbb{R}/\mathbb{Z}}<\epsilon\\}$
has at most $\sqrt{\epsilon}H$ many elements (or similarly the set
$\\{n\in[N]:\beta_{i}n+\gamma_{i}^{\prime}-\frac{1}{2}\|_{\mathbb{R}/\mathbb{Z}}<\epsilon\\}$
has at most $\sqrt{\epsilon}N$ many elements);

and an error set $E$ of size at most $200^{2d}\epsilon 2NH$. For the
$\alpha_{i}$’s or $\beta_{i}$’s that lie in the second case, we introduce a
smooth cutoff $\varphi_{j}$ of derivative at most $\epsilon^{-1}$ in the
dimensions that correspond to the $\alpha_{i}$’s or $\beta_{i}$’s. Thus,
letting $F(\vec{x},\vec{y})=e(k_{1}x_{1}y_{1}+\cdots+k_{d}x_{d}y_{d})$ and
letting the above decomposition be $[N]\times[H]=\bigsqcup_{i}P_{i}\sqcup E$,
it follows that we may express

$e(\phi(n,h))=F(\\{\alpha h\\},\\{\beta n\\})=\varphi(\\{\alpha h\\},\\{\beta
n\\})F(\\{\alpha h\\},\\{\beta n\\})+O_{L^{1}([N]\times[H]),\leq
1}(2d\epsilon^{1/2})$

where $O_{L^{1}([N]\times[H]),\leq C}(k)$ denotes a function in
$L^{1}([N]\times[H])$ whose norm is at most $Ck$ (i.e., $\leq 1$ denotes that
the implicit constant is $\leq 1$). We now take

$\phi(\\{\alpha h\\},\\{\beta n\\})F(\\{\alpha h\\},\\{\beta
n\\})=\sum_{i}1_{P_{i}}(n,h)\varphi(\\{\alpha h\\},\\{\beta n\\})F(\\{\alpha
h\\},\\{\beta n\\})+O_{L^{1}([N]\times[H]),\leq 1}(200^{2d}2\epsilon).$

For each of the remaining phases $\alpha_{i}$, $\beta_{j}$ that are not
covered by first case in the above bulleted points, we may take some phase
$\alpha_{i}^{0}$ or $\beta_{j}^{0}$ such that
$|\\{\alpha_{i}h+\gamma_{i}\\}-\\{\alpha_{i}^{0}\\}|\leq\epsilon^{1/2}$.
Making sure to choose $\epsilon$ so that $k\epsilon^{1/2}<1/100$, it follows
that we may replace $F(\\{\alpha h\\},\\{\beta n\\})$ by some
$\tilde{F}(\\{\alpha h\\},\\{\beta n\\})$ which is equal to
$\\{\alpha_{i}^{0}\\}$ and $\\{\beta_{j}^{0}\\}$ on please $i$ in the
$\vec{x}$ variable and place $j$ in the $\vec{y}$ variable. We thus have

$\sum_{i}1_{P_{i}}(n,h)\varphi(\\{\alpha h\\},\\{\beta n\\})F(\\{\alpha
h\\},\\{\beta n\\})$ $=\sum_{i}1_{P_{i}}(n,h)\varphi(\\{\alpha h\\},\\{\beta
n\\})\tilde{F}(\\{\alpha h\\},\\{\beta n\\})+O_{L^{\infty}([N]\times[H]),\leq
1}(2dk\epsilon^{1/2})$

(here, we are also implicitely using the inequality
$|e(\epsilon)-1|\leq|\epsilon|$). Now, each $P_{i}$ can be written as a
product of $P_{i}^{1}\times P_{i}^{2}$ (one in $h$ variable, one in $n$
variable). We may also write $P_{i}^{j}$ as a product of an interval $1_{I}$
and some $1_{n\equiv a\pmod{q}}$. The interval we can approximate in
$L^{1}[N]$ (or respectivly, $L^{1}[H]$) with a $g(n/N)$ where $g$ is a
Lipschitz function with norm at most $\epsilon^{-1/2}$ up to an error of at
most $2\epsilon^{1/2}|I|$. Each $1_{n\equiv a\pmod{q}}$ can also be thought of
as a Lipschitz function on the torus with norm at most $q$ (which in our case
will be at most $\epsilon^{-d}$). Thus, we may write:

$\sum_{i}\tilde{F}_{P_{i}}(\\{\alpha h\\},\\{\beta
n\\})+O_{L^{1}([N]\times[H]),\leq 1}(4\epsilon^{1/2})$

where each $\tilde{F}_{P_{i}}$ is a product of $\tilde{F}$ and $g$ and
$1_{n\equiv a\pmod{q}}$ functions associated to the progression $P_{i}$ and
has Lipchitz norm at most $(2d+4)\epsilon^{-1/2}$ and is defined on a $2d+4$
dimensional torus $\mathbb{R}^{2d+4}/\mathbb{Z}^{2d+4}$. Fourier expanding
each $\tilde{F}_{P_{i}}$ via [13, Lemma A.5] (taking
$\delta=\frac{\epsilon^{d+3/2}}{3(2d+4)200^{2d}}$), we obtain

$\sum_{i}\tilde{F}_{P_{i}}(\\{\alpha h\\},\\{\beta
n\\})=\sum_{\xi}a_{\xi}e(\xi\cdot(n,h))+O_{L^{\infty}([N]\times[H]),\leq
1}(\epsilon)$

where (in fact we can take $|a_{\xi}|\leq 1$)

$\sum_{\xi}|a_{\xi}|\leq O(\epsilon)^{-O(d)^{2}}.$

Summing up all the errors together gives an $L^{1}([N]\times[H])$ error of at
most $O(dk\epsilon^{1/2})$. Now choosing $\epsilon$ so that (each of the
conditions we placed on $\epsilon$ are satisfied before and)
$dk\epsilon^{1/2}\ll\delta$, we obtain the claim. ∎

We will also need a related lemma below:

######  Lemma B.3 (“Trivial” Fourier Complexity Lemma).

trivialfouriercomplexity Let $a,\alpha\in\mathbb{R}^{d}$m $1/10>\delta>0$
real, and $N>0$ a prime. Suppose that $a$ and $\alpha$ are rational with
denominator $N$. Then either $N\ll\delta^{-O(d)^{O(1)}}$ or

$e(a_{1}\\{\alpha_{1}n\\}+\cdots+a_{d}\\{\alpha_{d}n\\})$

has $L^{1}[N]$ $\delta$-Fourier complexity at most $\delta^{-O(d)^{O(1)}}$ and
one can take the phases in the definition of Fourier complexity to be rational
with denominator $N$.

###### Proof.

We separate $a=[a]+\\{a\\}$. Thus,

$a_{1}\\{\alpha_{1}n\\}+\cdots+a_{d}\\{\alpha_{d}n\\}\equiv([a]\cdot\alpha)n+\\{a\\}\cdot\\{\alpha
n\\}\pmod{1}.$

The function $e(\\{a\\}\cdot\\{\alpha n\\}+[a]\cdot\alpha n)$ resembles a
function on $\mathbb{R}^{d+1}/\mathbb{Z}^{d+1}$ which is smooth everywhere
except on the boundary. To remedy this issue, we multiply this function by a
smooth cutoff $\phi$ which is supported in $(-1/2,1/2)$ and equal to one on
$[-1/2+(\delta/4d),1/2+(\delta/4d)]$ (and has derivative at most
$8d^{2}/\delta$). The point is that outside the support of $\phi$, the measure
of $((\\{\alpha n\\})_{n\in\mathbb{R}^{d}/\mathbb{Z}^{d}},\alpha n)$ is at
most $\delta/2$, and when we multiplied by $\phi$, the function becomes smooth
with Lipschitz constant at most $O(8d^{3}/\delta)$. Thus, Fourier expanding
this function, we notice that the Fourier phases are an integer linear
combination of the $\alpha_{i}$’s, which ensures both the Fourier complexity
and the rational with denominator $N$ properties of the Fourier expansion. ∎

######  Remark B.1.

Again, one can prove this lemma in general, not assuming that $\alpha_{i}$
have denominator $N$; we did not do so since this is rather cumbersome.

We need one last Fourier complexity lemma.

######  Lemma B.4 (Fourier Complexity Lemma II).

FourierComplexity2 Either $\delta^{-O(d)^{O(1)}}\geq N$ or one may write

$e(\sum_{i}\\{a_{i}(\vec{n})\\}\\{b_{i}(\vec{m})\\})=\sum_{\alpha,\beta\in\frac{1}{2}\mathbb{Z}^{2d},|\alpha|,|\beta|\leq\delta^{-O(d)^{O(1)}}}a_{\alpha,\beta}e(\alpha\cdot\\{a_{i}(\vec{n})\\}+\beta\cdot\\{b_{i}(\vec{m})\\})+O_{\leq
1}(\delta)$

where $|a_{\alpha,\beta}|\leq 1$.

###### Proof.

We follow the procedure in [8, Appendix E]. We take the function
$f:[-1,1]^{2d}\to\mathbb{C}$ by defining it to be
$e(\sum_{i=1}^{d}x_{i}y_{i})$ on $[-1/2,1/2]$ and extending it to a function
on $[-1,1]$ with compact support. We then Fourier expand this function and
plug in $x_{i}=\\{a_{i}(\vec{n})\\}$ and $y_{i}=\\{b_{i}(\vec{m})\\}$ and
finish. ∎

##  Appendix C A proof of the refined bracket polynomial lemma

In this section, we shall give another proof of the refined bracket polynomial
lemma from [13], although our proof is more complicated and our bounds are
slightly weaker (and for brevity, we only prove the single parameter case). We
believe that our proof better motivates the statement of the refined bracket
polynomial lemma and would like to emphasize that the bounds obtained here are
single exponential in dimension, and thus are enough for any application here
as well as for [13]. Below is the version of the refined bracket polynomial
lemma we work with.

######  Lemma C.1 (Single Variable Refined Bracket Polynomial Lemma).

refinedappendix1 Let $N,\delta,M,K>0$ be fixed with $0<\delta<1/10$ and
$a,\alpha\in\mathbb{R}^{d}$ and $\beta\in\mathbb{R}$, with $|a|\leq M$.
Suppose there are at least $\delta N$ many $n\in[N]$ such that

$\|\beta+a\cdot\\{\alpha n\\}\|_{\mathbb{R}/\mathbb{Z}}\leq\frac{K}{N}.$

Then either $N\ll(MK/\delta)^{O(d)^{O(1)}}$ or else there exists $d\geq r\geq
0$, $w_{1},\dots,w_{r}\in\mathbb{Z}^{d}$ and
$\eta_{1},\dots,\eta_{d-r}\in\mathbb{Z}^{d}$ such that $w_{i},\eta_{j}$ are
linearly independent, $|w_{i}|,|\eta_{j}|\leq(\delta/M)^{-O(d)^{O(1)}}$,
$\langle w_{i},\eta_{j}\rangle=0$, and

$|w_{i}\cdot a|\leq\frac{(\delta/MK)^{-O(d)^{O(1)}}}{N}$
$\|\eta_{j}\cdot\alpha\|_{\mathbb{R}/\mathbb{Z}}\leq\frac{(\delta/MK)^{-O(d)^{O(1)}}}{N}.$

As in [13, Section 3] and below in Section 3, we deduce the above from the
following:

######  Lemma C.2.

refineddenominator Let $N,\delta,M,K>0$ be fixed with $0<\delta<1/10$ and
$a,\alpha\in\mathbb{R}^{d}$ and $\beta\in\mathbb{R}$, with $|a|\leq M$ and
$\alpha$ having denominator $N$. Suppose there are at least $\delta N$ many
$n\in[N]$ such that

$\|\beta+a\cdot\\{\alpha n\\}\|_{\mathbb{R}/\mathbb{Z}}\leq\frac{K}{N}.$

Then either $N\ll(MK/\delta)^{O(d)^{O(1)}}$ or else there exists $d\geq r\geq
0$, $w_{1},\dots,w_{r}\in\mathbb{Z}^{d}$ and
$\eta_{1},\dots,\eta_{d-r}\in\mathbb{Z}^{d}$ such that $w_{i},\eta_{j}$ are
linearly independent, $|w_{i}|,|\eta_{j}|\leq(\delta/M)^{-O(d)^{O(1)}}$,
$\langle w_{i},\eta_{j}\rangle=0$, and

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

We deduce this from:

######  Lemma C.3.

refinedappendix2 Let $N,N_{1},\delta,M,K>0$ fixed with $0<\delta<1/10$, $M>1$,
and $a,\alpha\in\mathbb{R}^{d}$ and $\beta\in\mathbb{R}$, with $|a|\leq M$ and
$\alpha$ having denominator $N_{1}$, a prime. Suppose there are at least
$\delta N$ many $h\in[N]$ such that

$|\mathbb{E}_{n\in[N]}e(\beta n+an\cdot\\{\alpha h\\})|\geq K^{-1}.$

Then either $N\ll(MK/\delta)^{O(d)^{O(1)}}$ or else there exists $d\geq r\geq
0$, $w_{1},\dots,w_{r}\in\mathbb{Z}^{d}$ and
$\eta_{1},\dots,\eta_{d-r}\in\mathbb{Z}^{d}$ such that $w_{i},\eta_{j}$ are
linearly independent, with $\langle w_{i},\eta_{j}\rangle=0$,
$|w_{i}|,|\eta_{j}|\leq(\delta/M)^{-O(d)^{O(1)}}$, and

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

###### Proof of refinedappendix1 assuming refinedappendix2.

We note that

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

implies that for $n\in[N_{1}]$ with $N_{1}\leq\epsilon N$ implies (since
$\sqrt{(\cos(x)-1)^{2}+\sin(x)^{2}}\leq|x|$ which rearranges to
$|x|/2\geq|\sin(x/2)|$) that

$|e(\beta n+an\cdot\\{\alpha h\\})-1|\leq\frac{nK}{N}\leq\epsilon K.$

This implies that

$\mathbb{E}_{n\in N_{1}}|e(\beta n+an\cdot\\{\alpha
h\\})-1|^{2}\leq\epsilon^{2}K^{2}$

so expanding out and bounding $\text{Re}(a)\leq|a|$, we have

$2-2|\mathbb{E}_{n\in[N_{1}]}e(\beta n+an\cdot\\{\alpha
h\\})|\leq\epsilon^{2}K^{2}$

and thus

$|\mathbb{E}_{n\in[N_{1}]}e(\beta n+an\cdot\\{\alpha h\\})|\geq
1-\frac{\epsilon^{2}K^{2}}{2}.$

Letting $\epsilon=K^{-1}$ gives us

$|\mathbb{E}_{n\in[N_{1}]}e(\beta n+an\cdot\\{\alpha h\\})|\geq\frac{1}{2}.$

Thus, applying refinedappendix2, we obtain linearly independent
$w_{1},\dots,w_{r}$ and $\eta_{1},\dots,\eta_{d-r}$ such that

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

as desired. ∎

It remains to deduce refinedappendix2. Before we do so, we offer an informal
description of the argument.

###  C.1. A brief description of the argument

Since the proof of the refined bracket polynomial lemma is rather complicated,
we will give a simplified description of them here. Suppose

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

where where $a,\alpha,\beta$ are as in iterationlemma. An attempt to prove
these refined bracket polynomial lemmas comes by iterating [7, Proposition
5.3]. The conclusion of [7, Proposition 5.3] shows that either $|a|\approx 0$
or there exists some integer vector $\eta\ll_{\delta,M}1$ such that
$\|\eta\cdot\alpha\|_{\mathbb{R}/\mathbb{Z}}=0$. Let us assume for simplicity
that the first coordinate of $\eta$, denoted as $\eta_{1}$ is equal to $1$. We
thus have

$\alpha_{1}+\eta_{2}\alpha_{2}+\eta_{3}\alpha_{3}+\cdots+\eta_{d}\alpha_{d}\equiv
0\pmod{1}.$

Thus, we have

$\|\tilde{a}\cdot\\{\alpha h\\}+\gamma
h+\beta+a_{1}P(h)\|_{\mathbb{R}/\mathbb{Z}}\approx 0$

where
$\tilde{a}=(0,a_{2}\eta_{1}-a_{1}\eta_{2},a_{3}\eta_{1}-a_{1}\eta_{3},\dots,a_{d}\eta_{1}-a_{1}\eta_{d})$
and

$P(h)=\\{\alpha_{1}h\\}+\eta_{2}\\{\alpha_{2}h\\}+\cdots+\eta_{d}\\{\alpha_{d}h\\}.$

$P(h)$ takes at most $2d|\eta|$ many values so by Pigeonholing in one of those
values, we can iterate this procedure to obtain a qualitative analogue of
refinedappendix1.

There are two problems that occur if one tries to iterate in that manner. The
first problem is that $|\tilde{a}|$ might be far larger than $|a|$ causing us
to need to increase the parameter $M$ when we apply iterationlemma again. We
certainly have the bound of $|\tilde{a}|\leq 2|a||\eta|$, but this is not good
enough for our iteration. An inspection of the bounds in iterationlemma shows
that this does give an iteration which would lead to double exponential bounds
in dimension, which is problematic for us. The second problem is that when we
Pigeonhole $h$ in one of the values of the expression $P(h)$, we will have a
density decrease _at best_ of $\delta\mapsto\delta^{2}$. This would also
iterate to bounds double exponential in dimension.

To overcome the first issue, we use the geometry of numbers. Using Minkowski’s
first theorem, one can show that the nonzero vector $\eta$ must lie in a small
tube pointed in the direction of $a$. This can be used to guarantee that upon
iteration, the size of $a$ doesn’t actually get bigger, but rather gets
smaller. This is because if $\eta$ lies in a tube of width $\epsilon$ in the
direction of $a$, we write

$\eta=ta+O_{\leq 1}(\epsilon)$

(where $O_{\leq 1}$ denotes that the implicit constant is $\leq 1$) then

$\eta_{i}=ta_{i}+O_{\leq 1}(\epsilon).$

Thus

$\eta_{1}a_{i}-a_{1}\eta_{i}=O_{\leq 2}(|a|\epsilon).$

Incidentally, something similar can also be shown using Green and Tao’s method
in [7, Proposition 5.3] of Fourier analysis. A use of the Fourier uncertainty
principle on something similar to the function $F(x)$ constructed in the proof
of [7, Proposition 5.3] also shows that the nonzero vector $\eta$ must lie in
a tube in the direction of $a$, though due to irregularities with the Fourier
transform, one cannot guarantee that the tube has as small width as what we
guarantee using Minkowski’s first theorem. This would lead to a slight
increase in the size of $a$, rather than a decrease that Minkowski’s theorem
guarantees. Fortunately, the increase in $a$ is small enough for the argument
to still carry through.

To overcome the second issue, we observe that for each $j$, $\\{h:P(h)=j\\}$
behaves like a Bohr set in that it has “bounded Fourier complexity.” If we
Pigeonhole in $h$, we lose this information. In order to utilize this
information, we convert the problem from refinedappendix1 to refinedappendix2.
This will allow us to use via bilinearfouriercomplexity the fact that
$e(a_{1}nP(h))=e(\\{a_{1}n\\}P(h))$ (the equality follows since $P(h)$ takes
integer values) has bounded Fourier complexity. This will allow us to transfer
the losses obtained from $\delta$ to losses in $K$. The variable $K$ will turn
out to iterate far better than $\delta$ does, because we can “remember”
bracket polynomials of the form $\\{a_{1}n\\}P(h)$ from previous steps of the
iteration (so on step $j$, we will deal $j$ many bracket polynomials that
resemble $\\{a_{1}n\\}P_{1}(h)+\cdots+\\{a_{j}n\\}P_{j}(h)$), so the variable
$K$ doesn’t actually increase iteratively but increases like
$K_{j}=(K_{1}/(\delta_{j}/3^{d}M2d))^{-O(jd)^{3}}$ where $K_{j}$ is the value
of $K$ in the $j$th step of the iteration. We are now ready for the deduction
of the refined bracket polynomial lemma.

###  C.2. Deduction of refinedappendix2:

We state the lemma which we iterate with.

######  Lemma C.4.

iterationlemma Let $a,\alpha\in\mathbb{R}^{d}$ and $N,N_{1},K,\delta>0$ with
$N_{1}$ a prime integer and $\alpha$ having denominator $N_{1}$,
$\delta<1/10$. Suppose there are at least $\delta N_{1}$ many $h\in[N_{1}]$
such that

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

Then either $N\ll(\delta/3^{d}dM)^{-O(1)}$ or
$N_{1}\ll(\delta/3^{d}dM)^{-O(1)}$ or $(\delta/3^{d}Md)^{4d}\|a\|_{\infty}\leq
K/N$ or there exists an integer vector $\eta$ of size at most
$(\delta/3^{d}Md)^{-O(d)}$ in a $(\delta/3^{d}Md)$-tube in the direction of
$a$ such that $\|\eta\cdot\alpha\|_{\mathbb{R}/\mathbb{Z}}=0$.

######  Remark C.1.

The fact that $\eta$ lies in a small tube in the direction of $a$ is crucial
for our iteration and is the chief difference between this lemma and the
bracket polynomial lemma [7, Proposition 5.3] of Green and Tao.

###### Proof.

Suppose

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

If $(\delta/3^{d}Md)^{4d}\|a\|_{\infty}\geq K/N$, then

$\|\beta+a\cdot\\{\alpha
h\\}\|_{\mathbb{R}/\mathbb{Z}}<\|a\|_{\infty}(\delta/3^{d}Md)^{4d}.$

By the Pigeonhole principle, there exists $\delta/dM$ proportion of $h$ and
some integer $\ell$ such that

$\beta+a\cdot\\{\alpha h\\}=\ell+O_{<1}(\|a\|_{\infty}(\delta/3^{d}Md)^{4d})$

and by Pigeonholing in a sign pattern, we see that there exists a
$\delta/3^{d}dM$ proportion of $h$ such that

$\beta+a\cdot\\{\alpha h\\}=\ell+O_{<1}(\|a\|_{\infty}(\delta/3^{d}Md)^{4d})$

and $\\{\alpha h\\}$ has the same sign. Taking the difference of any two
$h$’s, we see that

(1) $|a\cdot\\{\alpha h\\}|<2\|a\|_{\infty}(\delta/3^{d}Md)^{4d}.$

Let $T$ be the tube of width $(\delta/3^{d}Md)^{2}$ and length
$2^{2d+1}d^{d}\sqrt{d\pi}C(\delta/3^{d}M2d)^{-2d}$ in the direction of $a$. By
Minkowski’s first theorem, there exists a lattice point $\eta$ inside $T$.
Multiplying (1) by $t$ so that $ta$ is $(\delta/3^{d}Md)^{2}$-close to $\eta$,
we see that $t\leq 2^{d+1}(\delta/3^{d}Md)^{-2d}d/\|a\|_{\infty}$ so

$|\eta\cdot\\{\alpha h\\}|=O_{\leq
2}(2^{2d+1}d^{d}\sqrt{d\pi}C(\delta/3^{d}Md)^{2d}+(\delta/3^{d}Md)^{2})$

which if
$(\delta/3^{d}Md)<2(2^{2d+1}d^{d}\sqrt{d\pi}C(\delta/3^{d}Md)^{2d}+(\delta/3^{d}Md)^{2})$,
which happens if $\delta\ll_{C}1$, then this implies that
$\|\eta\cdot\alpha\|_{\mathbb{R}/\mathbb{Z}}=0$. ∎

###  C.3. Iterating iterationlemma

To iterate this, we define some notation. On step $j$ of the iteration, we
will work with the following setup:

  * •

We have

$|\mathbb{E}_{n\in[N]}e((\tilde{a}_{j})n\cdot\\{\alpha h\\}+P_{j}(n,h))|\geq
K^{-1}$

for $\delta_{j}N^{\prime}$ many $h\in\mathbb{Z}/N^{\prime}\mathbb{Z}$ where
$P_{j}(n,h)$ denotes a bracket polynomial in $n$ and $h$ with at most $O(jd)$
many lower order terms each of the form

$a\\{\alpha h+\beta\\}\\{\alpha^{\prime}n+\beta^{\prime}\\}.$

  * •

There will also exist $0^{\prime},\dots,(j-1)^{\prime}$, distinct integers in
$\\{1,\dots,d\\}$ representing the components of a vector in $\mathbb{R}^{d}$.

  * •

We will require $|\tilde{a}_{j}|\leq M_{j}$ and having components
$0^{\prime},1^{\prime},\dots,(j-1)^{\prime}$ equal to zero.

  * •

There will exist linearly independent vectors in $\mathbb{Z}^{d}$
$\eta^{1},\dots,\eta^{j}$, with $\eta^{k}$ having size at most
$(\delta_{k}/3^{d}dM_{j})^{-O(d)}$ and $\eta^{k}$ having zero components
$0^{\prime},\dots,(k-1)^{\prime}$ equal to zero with the property that
$\|\eta^{k}\cdot\alpha\|_{\mathbb{R}/\mathbb{Z}}=0$.

  * •

The base case of the iteration will have $j=0$ with $(\tilde{a}_{0})=a$,
$P_{0}=0$, $\delta_{0}=\delta$, and $M_{0}=M$.

Thus, in order to carry out the iteration given the data in step $j$, we must
construct

$P_{j+1},M_{j+1},\delta_{j+1},\eta^{j+1},(\tilde{a}_{j+1}),\text{ and
}j^{\prime}.$

We will also be considering additional parameters $K_{j}$ and $q_{j}$, which
we will construct in the argument.

Step 1: Constructing $\delta_{j+1}$ and $K_{j}$. Applying
bilinearfouriercomplexity with
$\delta=\min(\delta_{j}^{2}/4,K^{-2}/4)=K^{-2}/4$ to $P_{j}(n,h)$ and denoting

$f(n,h)=e((\tilde{a})_{j}n\cdot\\{\alpha h\\}+P_{j}(n,h))$

we may find $g(n,h)$ of Fourier complexity at most
$(K/(\delta/3^{d}M2d))^{O(jd)^{3}}$ such that

$\mathbb{E}_{h}\mathbb{E}_{n}|f(n,h)-e((\tilde{a})_{j}n\cdot\\{\alpha
h\\})g(n,h)|\leq K^{-2}/4.$

Thus, by Markov’s inequality, for at least $\delta_{j}N_{j}/2$ many $h$, we
have

$|\mathbb{E}_{n}f(n,h)-e((\tilde{a})_{j}n\cdot\\{\alpha h\\})g(n,h)|\leq
K^{-1}/2.$

Thus, by the triangle inequality, and using the fact that $g$ has bounded
Fourier complexity, we obtain phases $\xi$ and $\zeta$ such that

$|\mathbb{E}_{n}e((\tilde{a})_{j}n\cdot\\{\alpha h\\}+\xi n+\zeta
h)|\geq(K/(\delta_{j}/3^{d}M_{j}2d))^{-O(jd)^{3}}.$

for $\frac{\delta_{j}}{2}N^{\prime}$ many $h$. We let
$\delta_{j+1}=\frac{\delta_{j}}{2}$. Thus, it follows that

$\|(\tilde{a})_{j}\cdot\\{\alpha
h\\}+\xi\|_{\mathbb{R}/\mathbb{Z}}\leq\frac{(K/(\delta_{j}/3^{d}M_{j}2d))^{-O(jd)^{3}}}{N}:=\frac{K_{j}}{N}.$

Step 2: Constructing $\eta^{j+1}$. We now apply iterationlemma with $K=K_{j}$,
$N=N$, and $N_{1}=N^{\prime}$. We obtain either

  * •

two degenerate cases of when $N$, or
$N^{\prime}\ll(\delta_{j}/3^{d}dM_{j})^{-O(1)}$;

  * •

or $(\delta_{j}/3^{d}M_{j}2d)^{4d}\|(\tilde{a})_{j}\|_{\infty}\leq K_{j}/N$,
in which case we end the iteration (see subsection below);

  * •

or some integer vector $\eta^{j+1}$ inside the tube of width
$(\delta_{j}/3^{d}M_{j}2d)$ around $(\tilde{a})_{j}$ of size at most
$(\delta_{j}/3^{d}M_{j}2d)^{-O(d)}$ and with zero components in its
$0^{\prime},\dots,(j-1)^{\prime}$th coordinates and such that

$\|\eta^{j+1}\cdot\alpha\|_{\mathbb{R}/\mathbb{Z}}=0.$

Step 3: Constructing $j^{\prime}$, $\tilde{a}_{j+1}$, $q_{j+1}$, and
$P_{j+1}$. Pick some $j^{\prime}$ so that the $j^{\prime}$th component of
$\eta^{j+1}$, which we denote by $\eta^{j+1}_{j^{\prime}}$ is nonzero. Since
modular inverses exist for nonzero elements modulo
$\mathbb{Z}/N^{\prime}\mathbb{Z}$, we may replace $h$ by
$\eta^{j+1}_{j^{\prime}}k$. Since this is rather cumbersome, we write
$\eta^{j+1}_{j^{\prime}}$ as $q_{j+1}$. Thus, writing

$\\{\alpha q_{j+1}k\\}=q_{j+1}\\{\alpha k\\}-(q_{j+1}\\{\alpha k\\}-\\{\alpha
q_{j+1}k\\})$

we see that denoting the $i\neq j^{\prime}$ component of $(\tilde{a})_{j+1}$
to be $(\tilde{a}_{i})_{j}q_{j+1}-(\tilde{a}_{j^{\prime}})_{j}\eta^{j+1}_{i}$
and the $j^{\prime}$th component equal to zero,

$(\tilde{a})_{j}n\cdot\\{\alpha
q_{j+1}k\\}\equiv(\tilde{a})_{j+1}\cdot\\{\alpha k\\}+$
$\\{(\tilde{a})_{j}n\\}\cdot(-q_{j+1}\\{\alpha k\\}+\\{\alpha
q_{j+1}k\\})+\\{(\tilde{a}_{j^{\prime}})_{j}n\\}\left(q_{j+1}\\{\alpha_{j^{\prime}}k\\}+\sum_{i\neq
j^{\prime}}\eta^{j+1}_{i}\\{\alpha_{i}k\\}\right)\pmod{1}.$

Thus,

$(\tilde{a})_{j}n\cdot\\{\alpha
h\\}+P_{j}(n,h)\equiv(\tilde{a})_{j+1}n\cdot\\{\alpha
k\\}+P_{j+1}(n,k)\pmod{1}$

where

$P_{j+1}(n,k)=P_{j}(n,q_{j+1}k)+$
$\\{(\tilde{a})_{j}n\\}\cdot(-q_{j+1}\\{\alpha k\\}+\\{\alpha
q_{j+1}k\\})+\\{(\tilde{a}_{j^{\prime}})_{j}n\\}\left(q_{j+1}\\{\alpha_{j^{\prime}}k\\}+\sum_{i\neq
j^{\prime}}\eta^{j+1}_{i}\\{\alpha_{i}k\\}\right).$

Step 4: Constructing $M_{j+1}$. We lastly construct $M_{j+1}$. We claim that
one can take $M_{j+1}=M_{j}$. Since $\eta^{j+1}$ lies in a
$(\delta_{j}/3^{d}M_{j}2d)$-tube around $(\tilde{a})_{j}$, there exists some
real number $t$ such that

$\eta^{j+1}=t(\tilde{a})_{j}+O_{\leq 1}(\delta_{j}/3^{d}M_{j}2d)$

and so for each $i$,

$\eta_{j^{\prime}}^{j+1}=t(\tilde{a}_{j^{\prime}})_{j}+O_{\leq
1}(\delta_{j}/3^{d}M_{j}2d)$ $\eta_{i}^{j+1}=t(\tilde{a}_{i})_{j}+O_{\leq
1}(\delta_{j}/3^{d}M_{j}2d).$

Multiplying the first equation by $(\tilde{a}_{i})_{j}$ and the second
equation by $(\tilde{a}_{j^{\prime}})_{j}$ and subtracting the two, we obtain

$|\eta_{j^{\prime}}^{j+1}(\tilde{a}_{i})_{j}-\eta_{i}^{j+1}(\tilde{a}_{j^{\prime}})_{j}|\leq
2|a|\delta_{j}/3^{d}M_{j}2d\leq 1\leq M_{j}.$

Step 5: Gathering up all the relevant data. We thus have

$(\delta_{j+1},M_{j+1},K_{j})=(\delta_{j}/2,M_{j},(K/(\delta_{j}/3^{d}M_{j}2d))^{-O(jd)^{3}}).$

Under iteration in $d$, we obtain

(C.1) $\delta_{j}\geq\delta/2^{d},M_{j}=M,\text{ and
}K_{j}\leq(K/(\delta_{j}/3^{d}M_{j}2d))^{-O(d^{6})}.$

###  C.4. End of the iteration and completing the proof of refinedappendix2

Suppose we ended the iteration on step $m$. This is the case where
$(\delta_{m}/3^{d}M_{m}2d)^{4d}\|(\tilde{a})_{m}\|_{\infty}\leq K_{m}/N$. We
note that $(\tilde{a})_{m}$ has each of its components linear in $a$ with
coefficients in $\mathbb{Z}$. Let $w_{1}^{m}\cdot
a,\dots,w_{j},\dots,w_{d}^{m}\cdot a$ be its components where we omit index
$j$ if $j\in\\{0^{\prime},\dots,(m-1)^{\prime}\\}$. We can show by induction
on $k\leq m$ that

  * 1.

We can take for each $i\not\in\\{0^{\prime},\dots,k^{\prime}\\}$ that
$w^{k+1}_{i}=q_{k+1}w_{i}^{k}-\eta^{k+1}_{i}w_{k^{\prime}}^{k}$ and;

  * 2.

if $\eta^{j}\cdot x=0$ for all $j=1,\dots,k$, then one can write
$q_{1}q_{2}\cdots
q_{k}x=\sum_{i\not\in\\{0^{\prime},\dots,(k-1)^{\prime}\\}}w_{i}^{k}x_{i}.$

For the base case, one can simply take $w_{i}^{0}=e_{i}$, which is the unit
vector with $0$’s in all its components and a $1$ in its $i$th component. The
second point of the statement obviously holds. For the first point, note that
$(\tilde{a}_{i})_{1}=q_{1}a_{i}-\eta^{1}_{i}a_{0^{\prime}}$. Noting that
$a_{i}=a\cdot e_{i}$ and $a_{0^{\prime}}=a\cdot e_{0^{\prime}}$, the first
point of the claimed statement follows. Supposing the induction hypothesis
holds for $k\geq 0$, we see that

$q_{1}\cdots
q_{k}x=\sum_{i\not\in\\{0^{\prime},\dots,(k-1)^{\prime}\\}}w_{i}^{k}x_{i}.$

We see that since $\eta^{k+1}\cdot x=0$ (and $\eta^{k+1}$ has no coefficients
in $\\{0^{\prime},\dots,(k-1)^{\prime}\\}$) that we may write
$q_{k+1}x_{k^{\prime}}=\sum_{i\not\in\\{0^{\prime},\dots,k^{\prime}\\}}-\eta^{k+1}_{i}x_{i}$,
we see that we may write

$q_{1}\cdots
q_{k+1}x=\sum_{i\not\in\\{0^{\prime},\dots,k^{\prime}\\}}(q_{k+1}w_{i}^{k}-\eta^{k+1}_{i}w_{k^{\prime}}^{k})x_{i}.$

We in addition see that the $i$th component of $(\tilde{a})_{k}$ is
$q_{k+1}(\tilde{a}_{i})_{k-1}-\eta^{k+1}_{i}(\tilde{a}_{k^{\prime}})_{k-1}$
and since $(\tilde{a}_{i})_{k}=w^{k}_{i}\cdot a$, we see that we can take
$w^{k+1}_{i}=q_{k+1}w_{i}^{k}-\eta^{k+1}_{i}w_{k^{\prime}}^{k}$. The induction
argument follows.

Hence, the subspace of annihilators of $\eta^{1},\dots,\eta^{m}$ is lies in
the span of $\\{w_{j}^{m}\\}_{j\not\in\\{0^{\prime},\dots,(m-1)^{\prime}\\}}$.
This tells us by dimension counting reasons that the annihilators of
$\eta^{1},\dots,\eta^{m}$ coincide with the subspace spanned by
$\\{w_{j}^{m}\\}_{j\not\in\\{0^{\prime},\dots,(m-1)^{\prime}\\}}$ and shows
that $\\{w_{j}^{m}\\}_{j\not\in\\{0^{\prime},\dots,(m-1)^{\prime}\\}}$ are
linearly independent and are annihilated by $\eta^{1},\dots,\eta^{m}$. The
inductive argument also shows that
$|w_{i}^{k}|\leq(\delta_{j-1}/3^{d}M_{k}2d)^{-O(dk)}$. Finally, we note that
$(\delta_{m}/3^{d}M_{m}2d)^{4d}\|(\tilde{a})_{m-1}\|_{\infty}\leq K_{m}/N$
implies that for all $j$,

$|w_{j}^{m}\cdot a|\leq\frac{(2K\delta^{-1}M_{m}3^{d})^{O(m^{4}d^{4})}}{N}.$

Letting the $w_{i}$’s be these $w_{i}^{m}$’s, and noting from (C.1) that the
bounds on $\delta_{j}$, $M_{j}$ and $K_{j}$ are well-controlled
refinedappendix2 follows.

######  Remark C.2.

One can make the further reduction of taking $a$ to have prime denominator in
refineddenominator. This would mean that we are in the substantially simpler
case of bilinearfouriercomplexity where all the phases have prime denominator.
We chose not to make this reduction since we wished to present
bilinearfouriercomplexity in full generality.

## References

  * [1] J. Bourgain, _On triples in arithmetic progression_ , Geom. Funct. Anal. 9 (1999), 968–984.
  * [2] Pablo Candela and Olof Sisask, _Convergence results for systems of linear forms on cyclic groups and periodic nilsequences_ , SIAM J. Discrete Math. 28 (2014), 786–810.
  * [3] W. T. Gowers, _Arithmetic progressions in sparse sets_ , Current developments in mathematics, 2000, Int. Press, Somerville, MA, 2001, pp. 149–196.
  * [4] W. T. Gowers and L Milićević, _A quantitative inverse theorem for the $U^{4}$ norm over finite fields_, arXiv:1712.00241.
  * [5] B. Green and T. Tao, _An inverse theorem for the Gowers $U^{3}(G)$ norm_, Proc. Edinb. Math. Soc. (2) 51 (2008), 73–153.
  * [6] B. Green and T. Tao, _Quadratic uniformity of the Möbius function_ , Ann. Inst. Fourier (Grenoble) 58 (2008), 1863–1935.
  * [7] B. Green and T. Tao, _The quantitative behaviour of polynomial orbits on nilmanifolds_ , Ann. of Math. (2) 175 (2012), 465–540.
  * [8] B. Green, T. Tao, and T. Ziegler, _An inverse theorem for the Gowers $U^{4}$-norm_, Glasg. Math. J. 53 (2011), 1–50.
  * [9] Ben Green, Terence Tao, and Tamar Ziegler, _An inverse theorem for the Gowers $U^{s+1}[N]$-norm_, Ann. of Math. (2) 176 (2012), 1231–1372.
  * [10] Borys Kuca, _True complexity of polynomial progressions in finite fields_ , Proc. Edinb. Math. Soc. (2) 64 (2021), 448–500.
  * [11] Borys Kuca, _On several notions of complexity of polynomial progressions_ , Ergodic Theory Dynam. Systems 43 (2023), 1269–1323.
  * [12] J. Leng, _A Quantitative Bound For Szemerédi’s Theorem for a Complexity One Polynomial Progression over $\mathbb{Z}/n\mathbb{Z}$_, arXiv:2205.05540.
  * [13] James Leng, _Efficient equidistribution of nilsequences_ , arXiv:2312.10772.
  * [14] James Leng, _Improved Quadratic Gowers Uniformity for the Möbius Function_ , arXiv:2212.09635.
  * [15] James Leng, Ashwin Sah, and Mehtaab Sawhney, _Improved bounds for five-term arithmetic progressions_ , arXiv:2312.10776.
  * [16] James Leng, Ashwin Sah, and Mehtaab Sawhney, _Improved Bounds for Szemerédi’s Theorem_ , manuscript.
  * [17] James Leng, Ashwin Sah, and Mehtaab Sawhney, _Quasipolynomial bounds for the inverse theorem for the Gowers $U^{s+1}[N]$-norm_, manuscript.
  * [18] F. Manners, _Quantitative bounds in the inverse theorem for the Gowers ${U}^{s+1}$-norms over cyclic groups_, arXiv:1811.00718.
  * [19] L Milićević, _Bilinear bogolyubov argument in abelian groups_ , arXiv:2109.03093.
  * [20] Georg Pólya, _Über ganze ganzwertige funktionen_ , Nachrichten von der Gesellschaft der Wissenschaften zu Göttingen, Mathematisch-Physikalische Klasse 1920 (1920), 1–10.
  * [21] T. Sanders, _On the Bogolyubov-Ruzsa lemma_ , Anal. PDE 5 (2012), 627–655.
  * [22] T. Tao, _Higher order Fourier analysis_ , Graduate Studies in Mathematics, vol. 142, American Mathematical Society, Providence, RI, 2012.
  * [23] Terence Tao, _Equidistribution for multidimensional polynomial phases_ , 2015, https://terrytao.wordpress.com/2015/08/06/equidistribution-for-multidimensional-polynomial-phases/.
  * [24] Terence Tao and Van H. Vu, _Additive combinatorics_ , Cambridge Studies in Advanced Mathematics, vol. 105, Cambridge University Press, Cambridge, 2010, Paperback edition [of MR2289012].