Appendix A. Conventions regarding nilsequences and effective equidistribution

We begin this appendix by giving the precise definition of the complexity of a nilmanifold; this definition is exactly as in [ Reference Tao and Teräväinen37 , definition 6·1].

We, furthermore, require that this data obeys the following conditions:

1. (1) for $1\le i,j\le m$ , one has Lie algebra relations

   \[[X_i,X_j] = \sum_{i,j \lt k\le m}c_{ijk}X_k\]
   for rational numbers $c_{ijk}$ of height at most K (we will often refer to these as the Lie bracket structure constants);

2. (2) for each $1\le i\le s$ , the Lie algebra $\log G_i$ is spanned by $\{X_j\colon m-\dim(G_i) \lt j\le m\}$ ; and

3. (3) the subgroup $\Gamma$ consists of all elements of the form $\exp\!(t_1X_1)\cdots\exp\!(t_{m}X_{m})$ with $t_i\in \mathbb{Z}$ .

We note that the conditions imply $[G,G_s]=\mathrm{Id}_G$ , i.e., $G_s$ is contained in the center of G (commutes with every element).

Next, we will define polynomial sequences in filtered nilpotent groups. This concrete definition is equivalent (by [ Reference Green and Tao11 , lemma 6·7]) to the one given in [ Reference Green and Tao11 ].

Definition A·2. We adopt the conventions of Definition A·1. Let G be a filtered nilpotent group of degree s. A function $g\colon\mathbb{Z}\to G$ is a polynomial sequence if there exist elements $g_i\in G_{i}$ for $i=0,\ldots,s$ such that

\begin{equation*}g(n)=g_0g_1^{\binom{n}{1}}\cdots g_s^{\binom{n}{s}},\end{equation*}

where $\binom{n}{i}={1}/{i!}\prod_{j=0}^{i-1}(n-j)$ , for all $n\in\mathbb{Z}$ . We say a polynomial sequence g(n) is N-periodic with respect to a lattice $\Gamma$ if

\[g(n)g(n+N)^{-1}\in \Gamma\]

for all $n\in \mathbb{Z}$ .

We will denote the set of polynomial sequences $g\colon\mathbb{Z}\to G$ relative to the filtration $G_\bullet$ of G by $\operatorname{poly}(\mathbb{Z},G_\bullet)$ . It turns out that $\operatorname{poly}(\mathbb{Z},G_\bullet)$ is a group under the natural multiplication of sequences–this is due to Lazard [ Reference Lazard19 ] and Leibman [ Reference Leibman20, Reference Leibman21 ].

Now we can define Mal’cev coordinates, the explicit metrics on G and $G/\Gamma$ used in our work, and the precise definition of the Lipschitz norm of functions on $G/\Gamma$ . These definitions are exactly as in [ Reference Green and Tao11 , appendix A].

Definition A·3. We adopt the conventions of Definition A·1. Given a Mal’cev basis $\mathcal{X}$ and $g\in G$ , there exists $(t_1,\ldots,t_m)\in \mathbb{R}^{m}$ such that

\[g = \exp\!(t_1X_1 + t_2X_2+\ldots t_mX_m).\]

We define Mal’cev coordinates of first kind $\psi_{\exp}=\psi_{\exp,\mathcal{X}}\colon G\to\mathbb{R}^m$ for g relative to $\mathcal{X}$ by

\[\psi_{\exp}(g) \;:\!=\; (t_1,\ldots,t_m).\]

Given $g\in G$ there also exists $(u_1,\ldots,u_m)\in \mathbb{R}^m$ such that

\[g = \exp\!(u_1X_1)\cdots\exp\!(u_mX_m),\]

and we define the Mal’cev coordinates of second kind $\psi=\psi_{\mathcal{X}}\colon G\to\mathbb{R}^m$ for g relative to $\mathcal{X}$ by

\[\psi(g) \;:\!=\; (u_1,\ldots, u_m).\]

We then define a metric $d = d_{\mathcal{X}}$ on G by

\begin{align*} & d(x,y) \;:\!=\;\\[5pt] & \inf\bigg\{\sum_{i=1}^{n}\min(\lVert\psi(x_ix_{i+1}^{-1})\rVert,\lVert\psi(x_{i+1}x_{i}^{-1})\rVert)\colon n\in\mathbb{N}, x_1,\ldots,x_{n+1}\in G, x_1 = x, x_{n+1} = y\bigg\},\end{align*}

where $\lVert\cdot\rVert$ denotes the $\ell^\infty$ -norm on $\mathbb{R}^m$ , and define a metric on $G/\Gamma$ by

\[d(x\Gamma,y\Gamma) = \inf_{\gamma,\gamma'\in\Gamma}d(x\gamma,y\gamma').\]

Furthermore, for any function $F\colon G/\Gamma\to\mathbb{C}$ , we define

\[\lVert F\rVert_{\mathrm{Lip}} \;:\!=\; \lVert F\rVert_{\infty} + \sup_{\substack{x,y\in G/\Gamma \\ x\neq y}}\frac{|F(x)-F(y)|}{d(x,y)}.\]

We recall the notion of a horizontal character and the notion of a function F having a vertical frequency; our definitions are exactly as in [ Reference Green and Tao11 , definitions 1·5, 3·3, 3·4, 3·5].

Definition A·4. Given a filtered nilmanifold $G/\Gamma$ , the horizontal torus is defined to be

\[(G/\Gamma)_{\mathrm{ab}}\;:\!=\;G/[G,G]\Gamma.\]

A horizontal character is a continuous homomorphism $\eta\colon G\to\mathbb{R}/\mathbb{Z}$ that annihilates $\Gamma$ ; such characters may be equivalently viewed as characters on the horizontal torus. A horizontal character is nontrivial if it is not identically zero.

Furthermore, if the nilmanifold $G/\Gamma$ has degree s, the vertical torus is defined to be

\[G_s/(G_s\cap \Gamma).\]

A vertical character is a continuous homomorphism $\xi\colon G_s\to\mathbb{R}/\mathbb{Z}$ that annihilates $\Gamma\cap G_s$ . Setting $m_s = \dim G_s$ , one may use the last $m_s$ coordinates of the Mal’cev coordinate map to identify $G_s$ and $G_s/(G_s\cap \Gamma)$ with $\mathbb{R}^{m_s}$ and $\mathbb{R}^{m_s}/\mathbb{Z}^{m_s}$ , respectively. Thus, we may identify any vertical character $\xi$ with a unique $k\in \mathbb{Z}^{m_s}$ such that $\xi(x) = k\cdot x$ under this identification $G_s/(\Gamma\cap G_s) \cong \mathbb{R}^{m_s}/\mathbb{Z}^{m_s}$ . We refer to k as the frequency of the character $\xi$ , we write $|\xi| \;:\!=\;\lVert k\rVert_{\infty}$ to denote the magnitude of the frequency $\xi$ , and say that a function $F\colon G/\Gamma\to\mathbb{C}$ has a vertical frequency $\xi$ if

\[F(g_s\cdot x) = e(\xi(g_s))F(x)\]

for all $g_s\in G_s$ and $x\in G/\Gamma$ .

Appendix B. Explicit dimension dependence for Schmidt’s polynomial recurrence

We now prove the explicit version of Schmidt’s polynomial recurrence (Proposition 3·7). The proof we provide is essentially verbatim from [ Reference Green and Tao13 , appendix A]. For those familiar with the proof presented there, the use of theta functions is unrelated to the fact that one is finding small fractional parts of quadratic polynomials. Roughly speaking, the theta function is only used as a smooth approximation of the neighbourhood of points in a lattice which has nice Fourier properties.

Definition B·1. Suppose that $\Lambda$ is a lattice of full rank in $\mathbb{R}^d$ . The dual lattice, denoted $\Lambda^\ast$ , is $\Lambda^{\ast} = \{\xi\in \mathbb{R}^d\colon\xi\cdot m\in \mathbb{Z}\text{ for all } m\in \Lambda\}$ . For any $t \gt 0$ and $x\in \mathbb{R}^d$ , we define

\[\Theta_{\Lambda}(t,x) \;:\!=\; \sum_{m\in \Lambda}e^{-\pi t\lVert x-m\rVert_2^2}.\]

Finally define

\[A_{\Lambda} \;:\!=\; \Theta_{\Lambda^{\ast}}(1,\vec{0}) = \sum_{\xi\in \Lambda^{\ast}}e^{-\pi\lVert\xi\rVert_2^2} = \det(\Lambda)\sum_{m\in \Lambda}e^{-\pi \lVert m\rVert_2^2}.\]

We next need a version of Weyl’s inequality; we take the statement from [ Reference Green and Tao11 , proposition 4·3].

Proposition B·2. There exists $C = C(k) \gt 0$ such that the following holds. Suppose that $g\colon\mathbb{Z}\to\mathbb{R}$ is a polynomial of degree k and $\delta\in(0,1/2)$ . If $N\ge\delta^{-C}$ and

\[\big|\mathbb{E}_{n\in [N]}e(g(n))\big|\ge \delta\]

then there exists a positive integer $\ell$ such that $\ell\le\delta^{-C}$ and

\[\lVert\ell g\rVert_{C^{\infty}[N]}\le\delta^{-C}.\]

Remark. For a polynomial $P(n)=a_0+\cdots+a_kn^k$ , we have $\lVert P\rVert_{C^\infty[N]}=\max_{0 \lt i\le k}N^i\lVert a_i\rVert_{\mathbb{R}/\mathbb{Z}}$ .

A crucial object of study for $\alpha\in\mathbb{R}^d$ will be

\[F_{\Lambda,\alpha}(N) \;:\!=\; \det(\Lambda)\mathbb{E}_{|n|\le N}\Theta_{\Lambda}(1,n^k\alpha) = \sum_{\xi\in \Lambda^{\ast}}e^{-\pi \lVert\xi\rVert_2^2}\mathbb{E}_{|n|\le N}e(n^k\xi\cdot \alpha);\]

the final equality is a consequence of the Poisson summation formula (cf. [ Reference Green and Tao13 , (A·3), (A·5)]).

The following appears as [ Reference Green and Tao13 , lemma A·5 (i),(ii),(iii)] except with trivial modification for the differing degree.

Proof. We prove each of the items in turn. For the first item, note that $\Theta_\Lambda \gt 0$ so

\[F_{\Lambda,\alpha}(N)=\det(\Lambda)\frac{\sum_{|n|\le N}\Theta_{\Lambda}(1,n^k\alpha)}{2\lfloor N\rfloor+1}\ge \det(\Lambda)\frac{\sum_{|n|\le cN}\Theta_{\Lambda}(1,n^k\alpha)}{2\lfloor N\rfloor+1}\ge\frac{c F_{\Lambda,\alpha}(cN)}{2}.\]

For the second item, if $q \gt N$ note that

\[F_{\Lambda,\alpha}(N)=\det(\Lambda)\mathbb{E}_{|n|\le N}\Theta_{\Lambda}(1,n^k\alpha)\ge \det(\Lambda)\frac{\Theta(1,\vec{0})}{2N+1}\ge \frac{F_{\Lambda,q^k\alpha}(N/q)}{3q}.\]

For $q\le N$ , we have

\[F_{\Lambda,\alpha}(N)=\det(\Lambda)\frac{\sum_{|n|\le N}\Theta_{\Lambda}(1,n^k\alpha)}{2\lfloor N\rfloor+1}\ge \det(\Lambda)\frac{\sum_{|n|\le N/q}\Theta_{\Lambda}(1,n^k\cdot q^k\alpha)}{2\lfloor N\rfloor+1}\ge \frac{F_{\Lambda,q^k\alpha}(N/q)}{4q}.\]

We now handle the final item; let $X \;:\!=\; \lVert n^k\alpha -m\rVert_2$ , $\widetilde{X} = \lVert n^k\widetilde{\alpha}-m\rVert_2$ , and note that $|X-\widetilde{X}|\le \lVert n^k(\alpha-\widetilde{\alpha})\rVert_2\le \varepsilon$ . We have that $4\pi + \pi(1+\varepsilon)^2\widetilde{X}^2\ge \pi X^2$ for all $X\ge 0$ and $\widetilde{X}\in[X\pm\varepsilon]$ ; the inequality is trivial for $X\le 2$ and for $X\ge 2$ we have that $(1+\varepsilon)(X-\varepsilon) - X = \varepsilon (X-(1+\varepsilon))\ge 0$ . Therefore

\[e^{-\pi X^2}\ge e^{-4\pi}\cdot e^{-\pi (1+\varepsilon)^2\widetilde{X}^2} = e^{-4\pi}\cdot e^{-\pi \lVert n^k(1+\varepsilon)\alpha - (1+\varepsilon)m\rVert_2^2}.\]

Summing over $m\in \Lambda$ and $|n|\le N$ , the desired result follows.

The key point (which is identical to [ Reference Green and Tao13 , lemma A·6] modulo citing Weyl’s inequality for higher degree polynomials) is noting that if $F_{\Lambda,\alpha}(N)$ is small then there exists a vector in $\Lambda^{\ast}$ which is nearly orthogonal to $\alpha$ .

Proof. We claim that it suffices to prove that if $F_{\Lambda,\alpha}(N)\le 1/2$ , then there exists $q\ll A_{\Lambda}^{C}$ and a vector

\[\lVert\xi\rVert_2\ll \sqrt{d} + \sqrt{\log A_{\Lambda}}\text{ and } \lVert q\xi \cdot \alpha\rVert_{\mathbb{R}/\mathbb{Z}}\ll A_{\Lambda}^{C}N^{-k}.\]

Note that the shortest vector in $\Lambda^{\ast}$ is easily seen to be $\gg A_{\Lambda}^{-1}$ by considering the contribution to $A_{\Lambda}$ by scalar multiples of the shortest vector. Therefore $\xi$ is a multiple of $\widetilde{\xi}$ which is primitive, we have $\lVert\xi\rVert_2/\lVert\widetilde{\xi}\rVert_2\ll (\sqrt{d} + \sqrt{\log A_{\Lambda}})A_{\Lambda}$ , and therefore q can be replaced by $q' = q\lVert\xi\rVert_2/\lVert\widetilde{\xi}\rVert_2 \ll (\sqrt{d} + \sqrt{\log A_{\Lambda}})A_{\Lambda}\cdot A_{\Lambda}^{C}\ll d\cdot A_{\Lambda}^{C+1}.$ This gives the desired result.

Let $M = 4(\sqrt{d} + \sqrt{\log A_{\Lambda}})$ and note that

\begin{align*}1/2&\le |F_{\Lambda,\alpha}(N) - 1| = \bigg|\sum_{\xi\in \Lambda^{\ast}\setminus\{0\}}e^{-\pi \lVert\xi\rVert_2^2}\mathbb{E}_{|n|\le N}e(n^k\xi\cdot \alpha)\bigg|\\&\le \sum_{\substack{\xi\in \Lambda^{\ast}\\ \lVert\xi\rVert_2\ge M}}e^{-\pi \lVert\xi\rVert_2^2} + \bigg(\sup_{\substack{\xi\in \Lambda^{\ast}\\ \lVert\xi\rVert_2\le M}}\Big|\mathbb{E}_{|n|\le N}e(n^k\xi\cdot \alpha)\Big|\bigg)\cdot \sum_{\xi\in \Lambda^{\ast}}e^{-\pi \lVert\xi\rVert_2^2}\\&\le e^{-\pi M^2/2}\sum_{\xi\in \Lambda^{\ast}}e^{-\pi \lVert\xi\rVert_2^2/2} + A_{\Lambda}\sup_{\substack{\xi\in \Lambda^{\ast}\\ \lVert\xi\rVert_2\le M}}\Big|\mathbb{E}_{|n|\le N}e(n^k\xi\cdot \alpha)\Big|\\&= e^{-\pi M^2/2}2^{d/2}\det(\Lambda)\sum_{m\in \Lambda}e^{-2\pi \lVert m\rVert_2^2} + A_{\Lambda}\sup_{\substack{\xi\in \Lambda^{\ast}\\ \lVert\xi\rVert_2\le M}}\Big|\mathbb{E}_{|n|\le N}e(n^k\xi\cdot \alpha)\Big|\\&\le 1/4 + A_{\Lambda}\sup_{\substack{\xi\in \Lambda^{\ast}\\ \lVert\xi\rVert_2\le M}}\Big|\mathbb{E}_{|n|\le N}e(n^k\xi\cdot \alpha)\Big|,\end{align*}

where the equality follows from Poisson summation. We therefore have that

\[\Big|\mathbb{E}_{|n|\le N}e(n^k\xi\cdot \alpha)\Big|\ge 1/(4A_{\Lambda})\]

and the result follows from Proposition B·2 as desired.

The following appears as [ Reference Green and Tao13 , lemma A·7].

Lemma B·5. Let $\Lambda'\subseteq\mathbb{R}^{d-1}$ and $\Lambda\subseteq\mathbb{R}^d$ be full-rank lattices with $\Lambda'\subseteq \Lambda$ , embedding $\mathbb{R}^{d-1}$ in $\mathbb{R}^d$ by putting 0 in the final coordinate. Suppose that $\alpha\in\mathbb{R}^d$ and $\alpha'\in\mathbb{R}^{d-1}$ satisfy $\alpha-\alpha'\in \Lambda$ . Then

\[F_{\Lambda,\alpha}(N)\ge \frac{\det(\Lambda)}{\det(\Lambda')}F_{\Lambda',\alpha'}(N).\]

We now combine Lemma B·4 and Lemma B·5 exactly as in [ Reference Green and Tao13 , proposition A·8].

Lemma B·6. There exists $C = C(k) \gt 0$ such that the following holds. Suppose $\alpha\in \mathbb{R}^d$ and $\Lambda\subset \mathbb{R}^d$ is full rank. If $N \gt (dA_{\Lambda})^C$ and $F_{\Lambda,\alpha}(N)\le 1/2$ , then there exist $\Lambda'\subseteq \mathbb{R}^{d-1}$ , $\alpha'\in \mathbb{R}^{d-1}$ , and $N'\gg N(dA_{\Lambda})^{-C}$ such that

\begin{align*}A_{\Lambda'} &\ll (\sqrt{d} + \sqrt{\log A_{\Lambda}})A_{\Lambda},\\F_{\Lambda,\alpha}(N)&\ge(dA_{\Lambda})^{-C}F_{\Lambda',\alpha'}(N^{\ast}).\end{align*}

Proof. By Lemma B·4 we have that there exist primitive $\xi\in \Lambda^{\ast}\setminus\{0\}$ and $q\ll dA_{\Lambda}^{C}$ such that

\[\lVert\xi\rVert_2\ll \sqrt{d} + \sqrt{\log A_{\Lambda}}\text{ and } \lVert q\xi \cdot \alpha\rVert_{\mathbb{R}/\mathbb{Z}}\ll A_{\Lambda}^{C}N^{-k}.\]

By applying a rotation to both $\alpha$ and $\Lambda$ , we may assume that $\xi = \xi_de_d$ . Note that $|\xi_d|\gg A_{\Lambda}^{-1}$ and $\lVert\xi\cdot q^k\alpha\rVert_{\mathbb{R}/\mathbb{Z}}\ll d A_{\Lambda}^{O(1)}N^{-k}$ . Thus there exists $\beta\in \mathbb{R}^d$ such that $\beta\cdot \xi \in \mathbb{Z}$ and

\[\lVert\beta-q^k\alpha\rVert_{2}\le |\xi_d|^{-1}\lVert\xi\cdot q^k\alpha\rVert_{\mathbb{R}/\mathbb{Z}}\ll d A_{\Lambda}^{O(1)}N^{-k}.\]

We take $N_{\ast} \gg (dA_{\Lambda})^{-O(1)}N$ such that $\lVert\beta-q^k\alpha\rVert_{2}\le N_{\ast}^{-k}/d$ . We have that

\begin{align*}F_{\Lambda,\alpha}(N)&\gg (dA_{\Lambda})^{-O(1)}F_{\Lambda,\alpha}(N^{\ast})\gg (dA_{\Lambda})^{-O(1)}F_{\Lambda,q^k\alpha}(N^{\ast}/q)\\&\gg (dA_{\Lambda})^{-O(1)}F_{(1+1/d)\Lambda,(1+1/d)\beta}(N^{\ast}/q),\end{align*}

where we have applied the first, second, and then third item of Lemma B·3. Let $\pi\colon(x_1,\ldots,x_d)\to(x_1,\ldots,x_{d-1})$ and take $\alpha' = (1+1/d)\pi(\beta)$ , $\Lambda' = \pi((1+1/d)\Lambda)$ , and $N' = N^{\ast}/q$ . (That $\Lambda'$ is a lattice uses that $\xi$ is primitive.) Finally by Lemma B·5,

\[F_{(1+1/d)\Lambda,(1+1/d)\beta}(N^{\ast}/q)\ge \frac{\det((1+1/d)\Lambda)}{\det(\Lambda')}\cdot F_{\Lambda',\alpha'}(N') = ((1+1/d)\xi_d)F_{\Lambda',\alpha'}(N')\]

and using the lower bound on $|\xi_d|$ we have the desired lower bound on $F_{\Lambda,\alpha}(N)$ . For the upper bound of $A_{\Lambda'}$ , by positivity of the exponential function we have

\[\frac{A_{\pi(\Lambda)}}{\det(\pi(\Lambda))}\le \frac{A_{\Lambda}}{\det(\Lambda)}\]

and therefore

\[A_{\Lambda'}\le (1+1/d)^{d}A_{\pi(\Lambda)}\le eA_{\Lambda}\frac{{\det(\pi(\Lambda))}}{\det(\Lambda)} = eA_{\Lambda}\cdot \lVert\xi\rVert_2\]

as desired.

Iterating Lemma >B·6 exactly as is done in [ Reference Green and Tao13 , proposition A·9] (see arXiv version for a corrected statement) yields the following.

Proposition B·7. There exists $C = C(k) \gt 0$ such that the following holds. Let $\Lambda\subseteq \mathbb{R}^d$ be a lattice of full rank with $\det(\Lambda)\ge 1$ . Then for any integer N we have

\[F_{\Lambda,\alpha}(N)\gg d^{-Cd^2}A_{\Lambda}^{-Cd}.\]

We now prove Proposition 3·7; our deduction once again is identical to [ Reference Green and Tao13 , proposition A·2].

Proof of Proposition 3·7. Let R be a quantity to be chosen later; $R\gg d^3$ throughout. Let $\Lambda \;:\!=\; R\mathbb{Z}^d$ and $A_{\Lambda} = R^d(\sum_{m\in R\mathbb{Z}}e^{-\pi m^2})^d\le 2^{O(d)}R^d$ . This along with Proposition B·7 implies that

\[F_{\Lambda,\alpha}(N)\gg R^{-O(d^2)}\]

or

\[\mathbb{E}_{|n|\le N}\sum_{m\in R\mathbb{Z}^d}e^{-\pi\lVert n^k\alpha - m\rVert_2^2}\gg R^{-O(d^2)}.\]

For $N\gg (2R)^{\Omega(d^2)}$ , there is $n\in \{1,\ldots N\}$ such that

\[\sum_{m\in R\mathbb{Z}^d}e^{-\pi\lVert n^k\alpha - m\rVert_2^2}\gg R^{-O(d^2)}.\]

If $\lVert n^k\alpha - m\rVert_2\ge \sqrt{R}$ for all $m\in R\mathbb{Z}^d$ , we have

\begin{align*}\sum_{m\in R\mathbb{Z}^d}e^{-\pi\lVert n^k\alpha - m\rVert_2^2}&\le e^{-\pi R/2}\sum_{m\in R\mathbb{Z}^d}e^{-\pi\lVert n^k\alpha - m\rVert_2^2/2}\\&= e^{-\pi R/2} \frac{2^{d/2}}{\det(\Lambda)}\sum_{\xi\in \Lambda^{\ast}}e^{-2\pi \lVert\xi\rVert_2^2}\exp\!(\xi\cdot n^k\alpha)\\&\le e^{-\pi R/2} \frac{2^{d/2}A_{\Lambda}}{\det(\Lambda)} \ll e^{-\pi R/2} 2^{O(d)}.\end{align*}

This is a contradiction; thus if $N\ge (2R)^{\Omega(d^2)}$ and $R\gg d^3$ then there exists $1\le n\le N$ such that

\[\lVert n^k\alpha_j\rVert_{\mathbb{R}/\mathbb{Z}}\le 1/\sqrt{R}\]

for all $j=1,\ldots, d$ . The result follows upon taking $R = N^{c/d^2}$ for an appropriately small constant c (if N is small enough that $R\gg d^3$ fails to hold, the result is trivial).

Appendix C. Constructing an periodic nilsequence with integral structure constants

For technical reasons, it will be advantageous to construct nilsequences where the underlying nilmanifold has structure constants which are integral (and in fact divisible by a sufficient fixed integer). This follows via a straightforward lifting procedure where one replaces the underlying Mal’cev basis $\{e_1,\ldots,e_{\dim(G)}\}$ for $\Gamma$ with $\{e_1^{L},\ldots,e_{\dim(G)}^{L}\}$ for a sufficiently large constant L. This is primarily to avoid needing various fractional part identities in the proof of Proposition 2·3.

Lemma C·1. Fix an integer $K\ge 1$ . Suppose we are given a degree s nilmanifold $G/\Gamma$ with dimension d and complexity M and $F\colon G/\Gamma\to \mathbb{C}$ with Lipschitz norm bounded by L (with respect to the metric $d_{G/\Gamma}$ ).

There exist $\widetilde{\Gamma},\widetilde{F}$ such that $\widetilde{F}\colon G/\widetilde{\Gamma}\to\mathbb{C}$ such that for any $g\in G$ we have

\[F(g\Gamma) = \widetilde{F}(g\widetilde{\Gamma}).\]

Furthermore we have that $\widetilde{\Gamma}$ has a Mal’cev basis $\widetilde{X}$ with all Lie bracket structure constants (the values $c_{ijk}$ in Definition A·1) being integral and divisible by K, that $G/\widetilde{\Gamma}$ (with $\widetilde{X}$ ) has complexity bounded by $O_s(K)\cdot\exp\!(O(M))$ , and that F has Lipschitz norm bounded by $L\cdot (K\cdot \exp\!(O(M)))^{O_{s}(d^{O_s(1)})}$ .

We also require that the Lie algebra relations are appropriately filtered, corresponding to the containments $[G_i,G_j]\subseteq G_{i+j}$ .

We take $\widetilde{\mathcal{X}} = \{R\cdot X_1,\ldots,R\cdot X_d\} =: \{\widetilde{X_1},\ldots,\widetilde{X_d}\}$ for a large positive integer R to be chosen later. We take $\widetilde{\Gamma} = \langle \exp\!(RX_i) \rangle$ and claim that $\widetilde{\mathcal{X}}$ is a valid Mal’cev basis for $G,\widetilde{\Gamma}$ . All conditions for verifying a Mal’cev basis are trivial for us except for the fourth bullet point. The key point is verifying that every element of the subgroup generated by elements $\exp\!(RX_i)$ can be presented in the desired form.

We take $R = C_s \cdot \operatorname{lcm}(1,\ldots,M)\cdot K$ for some appropriate positive integer $C_s$ . Note that

\[[\widetilde{X}_i,\widetilde{X}_j] = \sum_{i,j \lt k\le m}c_{ijk}\cdot R^2X_k = \sum_{i,j \lt k\le m}(Rc_{ijk})\widetilde{X_k}.\]

The crucial point here is that $Rc_{ijk}\in C_s\mathbb{Z}$ by construction. Let $e_i = \exp\!(X_i)$ and suppose we have a word in $\widetilde{\Gamma}$ given by

\[w = e_{i_1}^{\pm R}e_{i_2}^{\pm R}\cdots e_{i_t}^{\pm R},\]

where each $\pm$ denotes an appropriate sign. Note $e_i^R=\exp\!(\widetilde{X}_i)$ . We first use the Baker–Campbell–Hausdorff formula to write

\[w=\exp\bigg(\sum_{j=1}^dw_j\widetilde{X}_j\bigg).\]

Note that $w_j\in\mathbb{Z}$ since the Lie bracket structure constants $Rc_{ijk}$ are in $C_s\mathbb{Z}$ , and Baker–Campbell–Hausdorff only goes to finite height due to the bounded step of the nilpotent Lie group. Now we iteratively pull out a single Mal’cev basis element “one at a time”. We have

\[\exp\!(\!-\!w_1\widetilde{X}_1)w=\exp\!(\!-\!w_1\widetilde{X}_1)\exp\bigg(\sum_{j=1}^dw_j\widetilde{X}_j\bigg)=\exp\bigg(\sum_{j=2}^dw_j'\widetilde{X}_j\bigg)\]

for some $w_j'\in\mathbb{Z}$ using Baker–Campbell–Hausdorff again. Note that we have eliminated use of $\widetilde{X}_1$ in the right side (which uses the observation that $c_{ijk}=0$ if $k\le\max(i,j)$ ). We iterate this, obtaining

\[\bigg(\prod_{j=d}^1\exp\!(\!-\!w_j^\ast\widetilde{X}_j)\bigg)w=\exp\!(0)=\mathrm{id}_G\]

for appropriate $w_j^\ast\in\mathbb{Z}$ (note that the product has decreasing indices left-to-right). Solving for w gives the result. This completes the proof that $\widetilde{\mathcal{X}}$ is a valid Mal’cev basis.

Now we define $\widetilde{F}$ and verify various claims regarding bounds. Note that $G/\widetilde{\Gamma}$ clearly has complexity bounded by O(RM) which is as desired. Since $\widetilde{\Gamma}\subseteq \Gamma$ , we may lift F from $G/\Gamma$ to $\widetilde{F}$ on $G/\widetilde{\Gamma}$ in the obvious manner, composing with a quotient. It suffices to verify that this does not ruin the Lipschitz norm. Let $M' = \exp\!(O(M))\cdot O_s(K)$ ; we have that the diameter of $G/\widetilde{\Gamma}$ is bounded by $(M')^{O_s(d^{O_s(1)})}$ (cf. [ Reference Green and Tao11 , lemma A·16] with explicit dimension dependence [ Reference Leng22 , lemma B·8]). Since $\lVert\widetilde{F}\rVert_\infty=\lVert F\rVert_\infty\le\lVert F\rVert_{\mathrm{Lip}}\le L$ , it suffices to consider points which are within $d_{G/\widetilde{\Gamma}}$ distance $\varepsilon$ when verifying the Lipschitz bound for $\widetilde{F}$ as long as we are willing to lose a factor of $\varepsilon^{-1}$ .

Note that $d_{G,\widetilde{\mathcal{X}}}(x,y)=(1/R)d_{G,\mathcal{X}}(x,y)$ since Mal’cev coordinates of the second kind in $\mathcal{X},\widetilde{\mathcal{X}}$ differ by a factor of R. Now consider $x,y\in G/\widetilde{\Gamma}$ such that $d_{G/\widetilde{\Gamma}}(x,y)\le(M')^{-O_s(d^{O_s(1)})}$ . There exist representatives of $\widetilde{x}$ and $\widetilde{y}$ for x and y with respect to $\widetilde{\Gamma}$ such that

\[d_{G/\widetilde{\Gamma}}(x,y) = d_{G,\widetilde{\mathcal{X}}}(\widetilde{x},\widetilde{y})\text{ and }d_{G,\widetilde{\mathcal{X}}}(\widetilde{x},\mathrm{Id}_G) + d_{G,\widetilde{X}}(\widetilde{y},\mathrm{Id}_G)\le(M')^{O_s(d^{O_s(1)})}.\]

Additionally, we claim that since x, y are sufficiently close in $G/\widetilde{\Gamma}$ , we find that

\[d_{G/\Gamma}(\widetilde{x}\Gamma,\widetilde{y}\Gamma)=d_{G,\mathcal{X}}(\widetilde{x},\widetilde{y}).\]

The argument is as follows. If this is not true, then there is $\gamma\in\Gamma\setminus\{0\}$ with $d_{G,\mathcal{X}}(\widetilde{x},\widetilde{y}\gamma) \lt d_{G,\mathcal{X}}(\widetilde{x},\widetilde{y})$ . By approximate left-invariance of the metric on G ([ Reference Green and Tao11 , lemma A·5] with explicit dimension dependence [ Reference Leng22 , lemma B·4]) we see

\[d_{G,\mathcal{X}}(\widetilde{y}^{-1}\widetilde{x},\gamma)\le(M')^{O_s(d^{O_s(1)})}Rd_{G/\widetilde{\Gamma}}(x,y)\le(M')^{O_s(d^{O_s(1)})}\varepsilon.\]

Additionally,

\[d_{G,\mathcal{X}}(\widetilde{y}^{-1}\widetilde{x},\mathrm{id}_G)\le(M')^{O_s(d^{O_s(1)})}\varepsilon.\]

The triangle inequality yields

\[d_{G,\mathcal{X}}(\gamma,\mathrm{id}_G)\le(M')^{O_s(d^{O_s(1)})}\varepsilon.\]

Now, the metric is comparable to the $L^\infty$ distance in second kind Mal’cev coordinates up to a factor of $(M')^{O_s(d^{O_s(1)})}$ ([ Reference Green and Tao11 , lemma A·4] with explicit dimension dependence [ Reference Leng22 , lemma B·3]) as long as $\varepsilon$ is sufficiently small here, so we find

\[1\le(M')^{O_s(d^{O_s(1)})}\varepsilon.\]

This as a contradiction as long as we take sufficiently small $\varepsilon$ (which will be admissible in the bounds we need). Finally,

\begin{align*}|\widetilde{F}(x\widetilde{\Gamma})-\widetilde{F}(y\widetilde{\Gamma})|&=|F(\widetilde{x}\Gamma)-F(\widetilde{y}\Gamma)|\le Ld_{G/\Gamma}(\widetilde{x},\widetilde{y})=Ld_{G,\mathcal{X}}(\widetilde{x},\widetilde{y})=LRd_{G,\widetilde{\mathcal{X}}}(\widetilde{x},\widetilde{y})\\[5pt] &=LRd_{G/\widetilde{\Gamma}}(x,y)\end{align*}

and we are done.

Having constructed a nilsequence with integral Lie bracket structure constants, it will also prove useful to construct a nilsequence which is additionally periodic. For this purpose, we quantify a construction of Manners [ Reference Manners24 ] which demonstrates that one may lift a nilsequence along a subset of the support. We first give a quantified version of [ Reference Manners24 , theorem 1·5].

Proposition C·2. There is an integer $C_s\ge 1$ so that the following holds. Fix an integer $K\ge 1$ . Suppose we have a degree s nilmanifold $G/\Gamma$ with complexity M and $F\colon G/\Gamma\to\mathbb{C}$ with Lipschitz norm L. Furthermore suppose we have a polynomial sequence $g\colon\mathbb{Z}\to G$ and a smooth function $\phi\colon\mathbb{R}/\mathbb{Z}\to[0,1]$ with $\operatorname{supp}(\phi)\in [(3K)^{-1},(2K)^{-1}]$ .

There exists a degree s nilmanifold $\widetilde{G}/\widetilde{\Gamma}$ with a polynomial sequence $\tilde{g}\colon\mathbb{Z}\to \widetilde{G}$ such that

\[\widetilde{F}(\widetilde{g}(x)) = \phi(x/N) F(g(x \;\mathrm{mod}\;N)),\]

where $x \;\mathrm{mod}\;N$ is interpreted to lie in $\{0,\ldots,N-1\}$ . Furthermore we may assume:

1. (i) $\widetilde{G}/\widetilde{\Gamma}$ has complexity bounded by $O_K(1)^{O_s(1)} + O_s(M)$ and dimension at most $O_s(d)$ ;

2. (ii) $\widetilde{F}$ has Lipschitz norm bounded by $L\cdot O_{\phi,K}(M^{O_s(d^{O_s(1)})})$ ;

3. (iii) $\widetilde{g}(n)^{-1}\widetilde{g}(n+N)\in\widetilde{\Gamma}$ for all $n\in\mathbb{Z}$ ;

4. (iv) if all Lie bracket structure constants of $G/\Gamma$ are integers divisible by K then the Lie bracket structure constants of $\widetilde{G}/\widetilde{\Gamma}$ are contained in $K(C_s)^{-1}\mathbb{Z}$ .

Given this we deduce a variant of the $U^4$ -inverse theorem from Theorem 1·3. This argument is essentially a combination of Lemma C·1, Proposition C·2, and the argument of [ Reference Manners24 , theorem 1·4].

Theorem C·3. Suppose we have an integer $K\ge 1$ . There exists a constant $C=C_K \gt 0$ such that the following holds. Let N be prime, let $\delta \gt 0$ , and suppose that $f\colon\mathbb{Z}/N\mathbb{Z}\to\mathbb{C}$ is a 1-bounded function with

\[\lVert f\rVert_{U^4(\mathbb{Z}/N\mathbb{Z})}\ge\delta.\]

There exists a degree 3 nilsequence $F(g(n)\Gamma)$ such that it has dimension bounded by $(\!\log\!(1/\delta))^{C}$ , complexity bounded by $O_K(1)$ , such that F is 1-Lipschitz, and such that

\[\big|\mathbb{E}_{n\in[N]} f(n)\overline{F(g(n)\Gamma)}\big|\ge1/\exp\!((\!\log\!(1/\delta))^{C}).\]

Furthermore, all Lie bracket structure constants of G (the $c_{ijk}$ in Definition A·1) are integers divisible by K, $g(n)g(n+N)^{-1}\in\Gamma$ for all $n\in\mathbb{Z}$ , and $g(0) = \operatorname{id}_G$ .

Remark. In all our applications, we will take $K = 12$ .

We deduce Theorem C·3 from Proposition C·2; this is essentially as in the proof of [ Reference Manners24 , theorem 1·4].

Proof of Theorem C·3. By adjusting constants appropriately, we may assume that N is larger than an absolute constant (and for small N apply the $U^2$ -inverse theorem noting all Lie bracket structure constants for an abelian nilmanifold are 0).

We take a partition of unity of $\mathbb{R}/\mathbb{Z}$ denoted $\phi_1,\ldots,\phi_{20K}\colon\mathbb{R}/\mathbb{Z}\to\mathbb{R}$ such that $\operatorname{supp}(\phi_j)\subseteq[j/(20K),j/(20 K) + 1/(10K)]\;\mathrm{mod}\;1$ . We abusively denote $\phi_i\colon\mathbb{Z}/N\mathbb{Z}\to\mathbb{R}$ via $\phi_i(n) \;:\!=\; \phi_i(n/N)$ . Recalling that $\lVert\cdot\rVert_{U^4(\mathbb{Z}/N\mathbb{Z})}$ is a norm, we have

\[\lVert f\rVert_{U^4(\mathbb{Z}/N\mathbb{Z})}\le \sum_{i=1}^{20K}\lVert\phi_i f\rVert_{U^4(\mathbb{Z}/N\mathbb{Z})}.\]

Thus there exists an index k such that $\lVert\phi_k f\rVert_{U^k(\mathbb{Z}/N\mathbb{Z})}\ge \delta/(20 K)$ . Applying a translation, we may assume that $\operatorname{supp}(\phi_k f)$ is contained in $[\lceil N/(3K)\rceil,\lfloor N/(2K)\rfloor] \;\mathrm{mod}\;N$ .

Applying Theorem 1·3, we have that there exists degree 3 nilsequence $F_1(g_1(n)\Gamma_1)$ on $G/\Gamma_1$ with complexity O(1), dimension $(\!\log\!(1/\delta))^{O(1)}$ , and Lipschitz constant 1 such that

\[|\mathbb{E}_{n\in [N]}\phi_k(n/N) f(n) \overline{F_1(g_1(n)\Gamma)}|\ge 1/\exp\!((\!\log\!(1/\delta))^{O(1)}).\]

By Lemma C·1, we may construct $\Gamma_2,F_2$ with Lie bracket structure constants for $G/\Gamma_2$ being integers divisible by $K\cdot C_s$ (where $s=3$ ) such that

\[|\mathbb{E}_{n\in [N]}\phi_k(n/N) f(n) \overline{F_2(g(n)\Gamma_2)}|\ge 1/\exp\!((\!\log\!(1/\delta))^{O(1)}).\]

Furthermore $G/\Gamma_2$ has complexity bounded by O(K) and $F_2$ has Lipschitz norm bounded by $(2K)^{O(d^{O(1)})}$ . Next, we may write

\[\mathbb{E}_{n\in [N]}\phi_k(n/N) f(n) \overline{F_2(g_2(n)\Gamma_2)} = \mathbb{E}_{n\in [N]} f(n) \overline{\phi_k(n/N) F_2(g_2(n)\Gamma_2)}\]

and apply Proposition C·2 to $\phi(x/N) F_2(g_2(x)\Gamma_2)$ . In particular, we obtain $F_3$ , $G_3$ , $\Gamma_3$ , and $g_3(n)$ such that

\[\mathbb{E}_{n\in [N]} f(n) \overline{\phi_k(n/N) F_2(g_2(n)\Gamma_2)} = \mathbb{E}_{n\in\mathbb{Z}/N\mathbb{Z}} f(n) \overline{F_3(g_3(n)\Gamma)}\]

with $F_3$ having Lipschitz norm $(O_K(1))^{O(d^{O(1)})}$ , $G_3/\Gamma_3$ having complexity $O_K(1)$ , $g_3(n)$ being N-periodic, and all Lie structure constants divisible by K.

Note that we do not necessarily have $g_3(0) \neq \operatorname{id}_{G_3}$ . This may be repaired by defining $g(n) = \{g_3(0)\}^{-1}g_3(n)g_3(0)^{-1}\{g_3(0)\}$ where $\{g_3(0)\}^{-1}g_3(0) = [g_3(0)]\in \Gamma_3$ and $\{g_3(0)\}$ has Mal’cev coordinates of the second kind bounded by $1/2$ . Taking

\[F(x\Gamma_3) \;:\!=\; F_3(\{g_3(0)\}x\Gamma_3)\]

we have

\[\mathbb{E}_{n\in\mathbb{Z}/N\mathbb{Z}} f(n) \overline{F_3(g_3(n)\Gamma_3)} = \mathbb{E}_{n\in\mathbb{Z}/N\mathbb{Z}} f(n) \overline{F(g(n)\Gamma_3)}.\]

As left-multiplication by bounded elements preserves the metric up to an admissible multiplicative factor ([ Reference Leng22 , lemma B·4]), we find that F has Lipschitz norm $(O_K(1))^{O(d^{O(1)})}$ . Thus, rescaling F to have Lipschitz norm 1 will keep the correlation sufficiently large. Furthermore as left-multiplying a fixed element and right-multiplying a fixed element in $\Gamma_3$ does not change whether our polynomial sequence is N-periodic on $G_3/\Gamma_3$ this completes the proof.

We now prove Proposition C·2. We use the construction of Manners [ Reference Manners24 , theorem 1·5]; we modify the construction slightly to match the definition of filtration used in this paper.

Proof of Proposition C·2. Step 1. Setup and constructing the proposed Mal’cev basis. We consider the given degree s nilpotent Lie group G with filtration

\[G=G_0 = G_1\geqslant G_2\geqslant\cdots\geqslant G_s\geqslant\operatorname{Id}_G.\]

Let $\mathfrak{g}_j=\log_G(G_j)$ .

For $i\ge 0$ , let $G^{+i}$ denote the prefiltration $G_i\geqslant G_{i+1}\geqslant G_{i+2}\geqslant\cdots \geqslant G_s\geqslant\operatorname{Id}_G$ . Let $H_i = \operatorname{poly}(\mathbb{Z},G^{+i})$ , where we define polynomial sequences with respect to prefiltrations as in [ Reference Green, Tao and Ziegler15 , definition B·1] with the prefiltration $\mathbb{Z}\geqslant\mathbb{Z}\geqslant\{0\}\geqslant\cdots$ on the domain $\mathbb{Z}$ (see also [ Reference Green and Tao11 , p. 28], which includes the formal definition of prefiltrations).

By the Filtered Lazard–Leibman theorem of Green, Tao and Ziegler [ Reference Green, Tao and Ziegler15 , proposition B·6], $H_i$ are not only groups but also can be given the prefiltration

\begin{align*}H_0&\geqslant H_1\geqslant H_2\geqslant\cdots\geqslant H_s\geqslant\operatorname{Id}_{H_0}.\end{align*}

This implies that one has the genuine filtration

\[H_1=H_1\geqslant H_2\geqslant\cdots\geqslant H_s\geqslant\operatorname{Id}_{H_0}.\]

We now define the semidirect product $H_i\rtimes\mathbb{R}$ by defining a group operation $\ast$ via

\[(x\mapsto g(x),t)\ast (x\mapsto g'(x),t') = (x\mapsto g(x + t')g'(x),t+t').\]

Note that this is slightly different than that given in the work of Manners [ Reference Manners24 ], since we take right-quotients by the cocompact subgroup, and in fact this is rather the opposite group of the semidirect product of the opposite groups (but we suppress such notational dependence). The semidirect product in question is embedding $t\in\mathbb{R}$ as the “shift by t” automorphism. Additionally, we abusively identify $g\in\operatorname{poly}(\mathbb{Z},G^{+i})$ with a function $\mathbb{R}\to G^{+i}$ defined by using Taylor expansion and then allowing the argument to vary over reals instead of integers using the Lie group structure; this extension is unique due to a generalisation of the identity theorem.

One can easily prove that

\[H_0\rtimes\mathbb{R}\geqslant H_1\rtimes\mathbb{R}\geqslant H_2\rtimes\{0\}\geqslant\cdots\geqslant H_s\rtimes\{0\}\geqslant\operatorname{Id}_{H_0\rtimes\mathbb{R}}\]

is a prefiltration; this follows immediately from the proof given in [ Reference Host and Kra17 , proposition 14]. (The only nontrivial aspect involves the $\rtimes\mathbb{R}$ component, and it is not too hard to show that it suffices to check relevant properties at the level of the generators $(\operatorname{id}_{H_0},t)$ since we have the above prefiltration on $H_0$ .)

Let $X_1,\ldots,X_d$ denote the Mal’cev basis on the Lie algebra associated to G (which is adapted to the s-step filtration given at the beginning). We construct the desired Mal’cev basis for $H_0\rtimes\mathbb{R}$ as follows:

1. (i) Let $Z = (0,K)$ ;

2. (ii) let $Y_{i, k} = (n \mapsto \binom{n}{k}X_i, 0)$ ; if $X_i\in \mathfrak{g}_j\setminus \mathfrak{g}_{j+1}$ define the level of $Y_{i,k}$ to be $j-k$ . We restrict attention to $Y_{i,k}$ of nonnegative level and level at most s. (Note that there are no contributions with $j=0$ .)

3. (iii) we order the Mal’cev basis left-to-right by increasing level; within level we order with increasing k, and then in increasing order of i. Z is inserted as the first element of level 1.

Remark. By Taylor expansion (see [ Reference Green, Tao and Ziegler15 , lemma B·9]) we see that this is a Lie basis of the necessary group, filtered with respect to the desired prefiltration. Note that a priori the Lie algebra of $\operatorname{poly}(\mathbb{Z},G^{+0})$ is some abstract space, but we can utilise the embedding $H_0=\operatorname{poly}(\mathbb{Z},G^{+0})\hookrightarrow G^{\mathbb{Z}}$ and the corresponding representation of Lie algebras to yield the above form of writing elements of the tangent space.

Our goal is now to verify that the discrete cocompact subgroup $\widetilde{\Gamma} = \operatorname{poly}(\mathbb{Z},\Gamma)\rtimes (K\mathbb{Z})$ is the push-forward of $\mathbb{Z}^{\dim(\widetilde{G})}$ for Mal’cev coordinates of the second kind. This algorithmic proof will also immediately verify the remaining property of the Mal’cev basis (regarding rationality of the Lie bracket structure constants). After this, we will give the necessary nilsequence lifting construction and verify the necessary properties.

Step 2. Verifying Mal’cev properties modulo the semidirect product. We first prove that the $Y_{i,k}$ graded as above form a Mal’cev basis for

\[H_0\geqslant H_1\geqslant H_2\geqslant\cdots\geqslant H_s\geqslant\operatorname{Id}_{H_0}\]

with discrete cocompact subgroup $\Gamma'=\operatorname{poly}(\mathbb{Z},\Gamma)$ . We proceed by induction upwards by step. Note that handling the final step is trivial as the group $H_s$ is abelian.

Assume the inductive hypothesis that $H_{j+1}\cap\Gamma'$ is the image of the integer lattice in Mal’cev coordinates of the second kind (which necessarily uses only those basis elements of level at least $j+1$ ). Using Taylor expansion (see [ Reference Green, Tao and Ziegler15 , lemma B·9]), we may write an element $H_{j}\cap\Gamma'$ as

(C·1) \begin{equation}n\mapsto \prod_{i=0}^{s-j}g_{i+j}^{\binom{n}{i}},\end{equation}

where $g_i\in G_{i+j}\cap \Gamma$ . ( $g_i\in\Gamma$ easily follows from our polynomial lying in $\Gamma'=\operatorname{poly}(\mathbb{Z},\Gamma)$ sequence.)

Now, for our given value of j, we prove by an induction on $\ell$ that the set of polynomials of the form

\[n\mapsto \prod_{i=0}^{s-j}g_{i+j}^{\binom{n}{i}}\]

with $g_{i+j}\in G_{i+j+1}\cap \Gamma$ for $0\le i\le\ell$ and $g_i\in G_{i+j}\cap\Gamma$ for $\ell+1\le i\le s-j$ is generated by the level $j+1$ elements and the largest $s-j-\ell$ “types” of level j elements of the Mal’cev basis for $H_0$ . (Here “types” means in the sense of the parameter k we used to define the ordering on the $Y_{i,k}$ above.) The case $\ell = s-j$ is exactly the above inductive assumption regarding $H_{j+1}\cap\Gamma'$ , and the case $\ell=0$ is exactly what we need to complete the (outer) induction.

We now suppose that this is known for some $s-j\ge\ell\ge 1$ , and wish to prove the result for $\ell-1$ . We may write

\[\bigg(n\mapsto \prod_{i=0}^{s-j}g_{i+j}^{\binom{n}{i}}\bigg) = \bigg(n\mapsto \prod_{i=0}^{\ell-1}g_{i+j}^{\binom{n}{i}}\bigg) \bigg(n\mapsto g_{\ell + j}^{\binom{n}{\ell}}\bigg)\bigg(n\mapsto \prod_{i=\ell + 1}^{s-j}g_{i+j}^{\binom{n}{i}}\bigg)=ABC,\]

where A, B, C are defined in the obvious way. Note that $A\in H_{j+1}\cap\Gamma'$ . We may write $g_{\ell+j} = \prod_{r}\exp\!(t_rX_r)$ for $t_r\in\mathbb{Z}$ and $X_r\in \mathfrak{g}_{\ell+j}$ . Note that

\[D^{-1}B=\bigg(\prod_{r}\bigg(n\mapsto \exp\!(t_rX_r)^{\binom{n}{\ell}}\bigg)\bigg)^{-1}\bigg(n\mapsto g_{\ell + j}^{\binom{n}{\ell}}\bigg) \in H_j\cap\Gamma',\]

where D is defined in the obvious way. The Taylor expansion of the polynomial $(D^{-1}B)C$ (in a similar form to (C·1)) trivially has its coordinates of index $0,\ldots,\ell-1$ being the identity (plugging in the values $n=0,1,\ldots,\ell-1$ ). The $\ell$ th Taylor coordinate is in $G_{\ell + j + 1}\cap\Gamma'$ , considering the value $n=\ell$ . Thus

\[ABC=D(D^{-1}AD)(D^{-1}BC),\]

where $D^{-1}BC$ has the form

\[n\mapsto\prod_{i=\ell}^{s-j}g_{i+j}'^{\binom{n}{i}}\]

for $g_{i+j}'\in G_{i+j}\cap\Gamma$ and additionally $g_{\ell+j}'\in G_{\ell+j+1}\cap\Gamma$ .

Note that $D^{-1}BC$ is of the correct form of Taylor series to apply the inductive hypothesis (since $g_{\ell+j}'\in G_{\ell+j+1}$ ), yielding

\[D^{-1}BC=\prod_{\mu\in M}\exp\!(t_\mu X_\mu)\cdot F=EF,\]

where M ranges over the $s-j-\ell$ “types” of level j elements of the Mal’cev basis of $H_0$ , from $\ell+1$ to $s-j$ inclusive, and is arranged in the correct order within the product E, and $F\in H_{j+1}\cap\Gamma'$ . Finally, we may write

\[ABC=DE(E^{-1}(D^{-1}AD)E\cdot F),\]

and note that $H_{j+1}$ is normal in $H_0$ due to the original prefiltration we established, so we find $E^{-1}(D^{-1}AD)E\in H_{j+1}\cap\Gamma'$ . Thus we have

\[ABC=DEF',\]

where D, E form the necessary ordered product for the Mal’cev second kind representation, and $F'\in H_{j+1}\cap\Gamma'$ . Finally, we recall the induction hypothesis for $H_{j+1}\cap\Gamma'$ to finish.

Step 3. Semidirect product and Lie bracket structure constants. We now handle the generator Z. Note that given an element $(p,t)\in\operatorname{poly}(\mathbb{Z},\Gamma)\rtimes (K\mathbb{Z})$ , we may write

\[(p,t) = (\operatorname{id}_{G},t) \ast (p, 0)\]

and therefore if Z was the highest element of the ordering (which would correspond to a situation where the filtration contains $H_1\rtimes\{0\}$ instead of $H_1\rtimes\mathbb{R}$ ) we would easily be done. Instead, though, it is inserted right before the Mal’cev basis components for $H_1$ . Note however that

\[(\operatorname{id}_{G},-K)\ast(p^{-1},0)\ast(\operatorname{id}_{G},K)\ast(p,0)=(p^{-1},-K)\ast(p,K)=(x\mapsto p^{-1}(x+K)p(x),0)\]

and recall that derivatives of polynomials in $H_j\cap\operatorname{poly}(\mathbb{Z},\Gamma)$ are in $H_{j+1}\cap\operatorname{poly}(\mathbb{Z},\Gamma)$ due to the definitions of the shifted filtrations on G. Therefore we may commute $(\operatorname{id}_G,t)$ across the product of the level 0 terms in the representation above, and we will introduce only terms of level 1 and higher (and they will lie in $\widetilde{\Gamma}$ ). Then using the Mal’cev representation for $H_1\cap\Gamma'$ finishes. This completes our discussion that the generators listed form a Mal’cev basis.

We now compute the Lie bracket structure constants associated to the Mal’cev basis. We will compute all structure constants via the identity

\begin{align*}[V,W] &= \frac{d}{ds}\frac{d}{dt} \exp\!(sV)\exp\!(tW)\exp\!(\!-\!sV)\exp\!(\!-\!tW)\bigg|_{u,v=0}\end{align*}

which holds for any Lie group and the associated Lie bracket.

We first compute the constants associated with Z. Note that

\begin{align*}[Y_{i,k},Z] &= \frac{d}{dt_0}\frac{d}{dt_1}\big(n\mapsto \exp\!(t_0X_i)^{\binom{n}{k}},0\big)(\operatorname{id}_G,Kt_1)\big(n\mapsto \exp\!(t_0X_i)^{-\binom{n}{k}},0\big)(\operatorname{id}_G,-Kt_1)\bigg|_{t_0,t_1=0}\\&=\frac{d}{dt_0}\frac{d}{dt_1}\big(n\mapsto\exp\!(t_0X_i)^{\binom{n}{k}-\binom{n-Kt_1}{k}},0\big)\bigg|_{t_0,t_1=0}\\& = \log_{H_0\rtimes\mathbb{R}}\bigg(n\mapsto\exp\!(X_i)^{-\frac{d}{dt_1}\binom{n-Kt_1}{k}\big|_{t_0=0}},0\bigg)=\bigg(n\mapsto-\frac{d}{dt_1}\binom{n-Kt_1}{k}X_i\bigg|_{t_1=0},0\bigg),\end{align*}

where the last line follows from considering the relationship between the differential structure on $H_0$ and on G (which allows us to “implicitly differentiate in the obvious way”). The coefficients of $({d}/{dt_1})\binom{n-Kt_1}{k}\big|_{t_1=0}$ are all integer multiples of $K^t/k!$ for $1\le t\le k-1$ . We may easily express this in terms of various $Y_{i,k'}$ for $k' \lt k$ , and the structure constants clearly have the desired form, lying in $K(C_s)^{-1}\mathbb{Z}$ for an appropriate integer $C_s$ .

We next compute the structure constants associated with two polynomials. Notice that

\begin{align*}&[Y_{i,k},Y_{j,\ell}]\\&= \frac{d}{dt_1}\frac{d}{dt_2}\big(n\mapsto \exp\!(t_1X_i)^{\binom{n}{k}},0\big)\big(n\mapsto \exp\!(t_2X_j)^{\binom{n}{\ell}},0\big)\big(n\mapsto \exp\!(t_1X_i)^{-\binom{n}{k}},0\big)\\ &\quad \times \big(n\mapsto \exp\!(t_2X_j)^{-\binom{n}{\ell}},0\big)\bigg|_{t_1,t_2=0}\\&=\frac{d}{dt_1}\frac{d}{dt_2} \bigg(n\mapsto \exp\bigg(t_1t_2\binom{n}{k}\binom{n}{\ell}[X_i,X_j]\bigg),0\bigg)\bigg|_{t_1,t_2=0}\\&=\bigg(n\mapsto\binom{n}{k}\binom{n}{\ell}[X_i,X_j],0\bigg).\end{align*}

The second equality follows from using Baker–Campbell–Hausdorff to multiply the polynomial sequences (as pointwise functions, say) and collapse them, and then noting that we may discard terms with higher powers than $t_1^1$ and $t_2^1$ . The only relevant remaining term is the $t_1t_2$ which has the claimed form.

Note that as $\binom{n}{k}\binom{n}{\ell}$ is an integer-valued polynomial, by Polya’s classification of integer polynomials [ Reference Pólya27 ], it follows that this may be written as an integral combination of binomial coefficients with coefficients bounded by $O_s(1)$ . We obtain a representation in terms of various $Y_{i',k'}$ where $k'\le k+\ell$ and $X_{i'}$ shows up in the expansion of $[X_i,X_j]$ . We are done with this part of the proof, which includes verifying the well-definedness of various lifted filtrations, Mal’cev bases, and also the rationality properties of the Lie bracket structure constants.

Step 4. Lifting the nilsequence and checking quantitative dependences. We now actually define the desired function. We are given a polynomial sequence g(x) and we define $q(x) = g(xN/K)$ . We define

\[\widetilde{g}(x) = (q,0)\ast(\operatorname{id}_G,Kx/N).\]

Note that $\widetilde{g}(x)$ is N-periodic as $\widetilde{g}(x+N)=\widetilde{g}(x)\ast(\operatorname{id}_G,K)$ . We now define $\widetilde{F}$ on $\operatorname{poly}(\mathbb{R},G)/\operatorname{poly}(\mathbb{Z},\Gamma)\times [0,K)$ via

\[\widetilde{F}(x\cdot \operatorname{poly}(\mathbb{Z},\Gamma),t) = \phi(t/K)\cdot F(x(0)\Gamma).\]

This extends uniquely to $H_0\rtimes\mathbb{R}$ if we enforce right- $\widetilde{\Gamma}$ -invariance, which yields

\[\widetilde{F}(x\cdot \operatorname{poly}(\mathbb{Z},\Gamma),t) = \phi(\{t/K\})\cdot F(x(\!-\!K\lfloor t/K\rfloor)\Gamma).\]

That $\widetilde{F}$ is appropriately Lipschitz and that we can then descend this construction to a proper filtration will be checked last.