of intervals is $k$-adapted to the sequence $a=(a_{n})_{n\in\mathbb{Z}}$, if
for every $\underline{h}=(h_{1},\ldots,h_{k})\in\mathbb{Z}^{k}$, the limit

(B.1) $c_{\underline{h}}({\bf
I},a)\triangleq\lim_{N\to\infty}\frac{1}{|I_{N}|}\sum_{n\in
I_{N}}\prod_{\epsilon\in\\{0,1\\}^{k}}a_{n+h_{1}\epsilon_{1}+\cdots+h_{k}\epsilon_{k}}=\lim_{N\to\infty}\frac{1}{|I_{N}|}\sum_{n\in
I_{N}}\prod_{\epsilon\in\\{0,1\\}^{k}}a_{n+\epsilon\cdot\underline{h}}$

exists. Note that every sequence of intervals whose lengths tend to infinity
admits a subsequence which is adapted to the sequence
$a=(a_{n})_{n\in\mathbb{N}}$.

######  Definition B.1.

Suppose that ${\bf I}=(I_{N})_{N\in\mathbb{N}}$ is $k$-adapted to
$a=(a_{n})_{n\in\mathbb{Z}}$. We define

(B.2) $\interleave a\interleave_{{\bf
I},k}\triangleq\left(\lim_{H\to\infty}\frac{1}{H^{k}}\sum_{\underline{h}\in[0,H-1]^{k}}c_{\underline{h}}({\bf
I},a)\right)^{1/2^{k}}.$

######  Remark B.2.

Suppose that ${\bf I}=(I_{N})_{N\in\mathbb{N}}$ is $k$-adapted to
$a=(a_{n})_{n\in\mathbb{Z}}$. Using a variant of Furstenberg’s correspondence
principle, one can show that there exist a t.d.s. $(X,T)$, a transitive point
$w$, a continuous function $f$ on $X$, and a $T$-invariant Borel probability
measure $\mu$ on $X$ such that $a_{n}=f(T^{n}w)$ for all $n\in\mathbb{Z}$ and
for $\underline{h}=(h_{1},\ldots,h_{k})\in\mathbb{Z}^{k}$,

(B.3) $c_{\underline{h}}({\bf
I},a)=\int_{X}\prod_{\epsilon\in\\{0,1\\}^{k}}f(T^{\epsilon\cdot\underline{h}}x)d\mu(x).$

See Subsection 4.2 of [22] or [23, Proposition 22.1] for details about this
fact. Thus

$\begin{split}\interleave a\interleave_{{\bf
I},k}&=\left(\lim_{H\to\infty}\frac{1}{H^{k}}\sum_{\underline{h}\in[0,H-1]^{k}}c_{\underline{h}}({\bf
I},a)\right)^{1/2^{k}}\\\
&=\left(\lim_{H\to\infty}\frac{1}{H^{k}}\sum_{\underline{h}\in[0,H-1]^{k}}\int_{X}\prod_{\epsilon\in\\{0,1\\}^{k}}f(T^{\epsilon\cdot\underline{h}}x)d\mu(x)\right)^{1/2^{k}}\\\
&=\interleave f\interleave_{k}.\end{split}$

It follows that $\interleave a\interleave_{{\bf I},k}$ is well-defined. We
need an equivalent definition of $\interleave a\interleave_{{\bf I},k}$. By
Appendix A of [3] or [23, Theorem 8.26], we have

$\interleave
f\interleave_{k}=\left(\lim_{H_{1}\to\infty}\frac{1}{H_{1}}\sum_{h_{1}=1}^{H_{1}}\cdots\lim_{H_{k}\to\infty}\frac{1}{H_{k}}\sum_{h_{k}=1}^{H_{k}}\int_{X}\prod_{\epsilon\in\\{0,1\\}^{k}}f(T^{h_{1}\epsilon_{1}+\cdots+h_{k}\epsilon_{k}}x)d\mu(x)\right)^{1/2^{k}}.$

It follows that

(B.4) $\interleave a\interleave_{{\bf
I},k}=\left(\lim_{H_{1}\to\infty}\frac{1}{H_{1}}\sum_{h_{1}=1}^{H_{1}}\cdots\lim_{H_{k}\to\infty}\frac{1}{H_{k}}\sum_{h_{k}=1}^{H_{k}}c_{\underline{h}}({\bf
I},a)\right)^{1/2^{k}}.$

Note that by symmetry, the order of $H_{1},\ldots,H_{k}$ is not important in
the left side of the equation (B.4). We will use this equation later.

######  Theorem B.3.

[22, Corollary 2.14] Let $a=(a_{n})_{n\in\mathbb{N}}$ be a bounded sequence of
real numbers, and ${\bf I}=(I_{N})_{N\in\mathbb{N}}$ be a sequence of
intervals that is $k$-adapted to this sequence for some $k\geq 2$. Suppose
that $\interleave a\interleave_{{\bf I},k}=0$. Then for every bounded
$(k-1)$-step nilsequence $(u_{n})_{n\in\mathbb{Z}}$ we have

$\lim_{N\to\infty}\frac{1}{|I_{N}|}\sum_{n\in I_{n}}a_{n}u_{n}=0.$

We will prove a result more general than Theorem 7.6.

######  Theorem B.4.

Let $(X,\mathcal{X},\mu,T)$ be a m.p.s. and $k\geq 2$ be an integer. Let
$(\phi_{n}(x))_{n\in\mathbb{Z}}$ be a uniformly bounded sequence of
$\mu$-measurable functions such that, for $\mu$-almost every $x\in X$, the
sequence $(\phi_{n}(x))_{n\in\mathbb{Z}}$ is a $(k-1)$-step nilsequence. Then
for all integral polynomials $p_{1},\ldots,p_{d}$ and for all
$f_{1},\ldots,f_{d}\in L^{\infty}(X,\mu)$, the averages

(B.5)
$\frac{1}{N-M}\sum_{n=M}^{N-1}\phi_{n}(x)f_{1}(T^{p_{1}(n)}x)f_{2}(T^{p_{2}(n)}x)\cdots
f_{d}(T^{p_{d}(n)}x)$

converge in $L^{2}(X,\mu)$ as $N-M\to\infty$.

Moreover, if the integral polynomials $p_{1},\ldots,p_{d}$ are essentially
distinct and $\mathbb{E}(f_{j}|\mathcal{Z}_{\infty}(T))=0$ for some
$j\in\\{1,2,\ldots,d\\}$, then the averages (B.5) converge to $0$ in
$L^{2}(X,\mu)$.

###### Proof.

Without loss of generality, assume that $f_{1},\ldots,f_{d}\in
L^{\infty}(X,\mu)$ with $\|f_{j}\|_{\infty}\leq 1$ for $j=1,\ldots,d$. And we
assume that integral polynomials $p_{1},\ldots,p_{d}$ are essentially distinct
and non-constant with $p_{1}(0)=\cdots=p_{d}(0)=0$.

Step 1. For all non-zero distinct $c_{1},\ldots,c_{d}\in\mathbb{Z}$ and for
all $f_{1},\ldots,f_{d}\in L^{\infty}(X,\mu)$, if $\interleave
f_{j}\interleave_{k+d}=0$ for some $j\in\\{1,\ldots,d\\}$, then the averages

(B.6)
$\frac{1}{N-M}\sum_{n=M}^{N-1}\phi_{n}(x)f_{1}(T^{c_{1}n}x)f_{2}(T^{c_{2}n}x)\cdots
f_{d}(T^{c_{d}n}x)$

converge to 0 in $L^{2}(X,\mu)$ as $N-M\to\infty$.

In order to prove that (B.6) converges to $0$, it suffices to show that every
sequence of intervals ${\bf I}=(I_{N})_{N\in\mathbb{N}}$ whose lengths
$|I_{N}|$ tend to infinity, admits a subsequence ${\bf
I}^{\prime}=(I_{N}^{\prime})_{N\in\mathbb{N}}$ such that

(B.7) $\frac{1}{|I_{N}^{\prime}|}\sum_{n\in
I_{N}^{\prime}}\phi_{n}(x)f_{1}(T^{c_{1}n}x)f_{2}(T^{c_{2}n}x)\cdots
f_{d}(T^{c_{d}n}x)\longrightarrow 0,\ N\to\infty,\ \text{in $L^{2}(X,\mu)$}.$

For $x\in X$, we write $a(x)=(a_{n}(x))_{n\in\mathbb{N}}$ for the sequence
defined by

$a_{n}(x)=f_{1}(T^{c_{1}n}x)f_{2}(T^{c_{2}n}x)\cdots f_{d}(T^{c_{d}n}x).$

For every $\underline{h}=(h_{1},\ldots,h_{k})\in\mathbb{Z}^{k}$ , we study the
averages

$\frac{1}{|I_{N}|}\sum_{n\in
I_{N}}\prod_{\epsilon\in\\{0,1\\}^{k}}a_{n+h_{1}\epsilon_{1}+\cdots+h_{k}\epsilon_{k}}(x).$

Note that

(B.8)
$\begin{split}a_{n+h_{1}\epsilon_{1}+\cdots+h_{k}\epsilon_{k}}(x)&=\Big{(}\prod_{\epsilon\in\\{0,1\\}^{k}}T^{c_{1}(h_{1}\epsilon_{1}+\cdots+h_{k}\epsilon_{k})}f_{1}\Big{)}(T^{c_{1}n}x)\ldots\\\
&\quad\quad\quad\quad\quad\Big{(}\prod_{\epsilon\in\\{0,1\\}^{k}}T^{c_{d}(h_{1}\epsilon_{1}+\cdots+h_{k}\epsilon_{k})}f_{d}\Big{)}(T^{c_{d}n}x).\end{split}$

Thus by Lemma 2.6777In Lemma 2.6, $I_{N}=[0,N-1]$. It holds for any ${\bf
I}=(I_{N})_{N\in\mathbb{N}}$, a sequence of intervals whose lengths $|I_{N}|$
tend to infinity [23, Proposition 21.7].

(B.9) $\begin{split}&\limsup_{N\to\infty}\Big{\|}\frac{1}{|I_{N}|}\sum_{n\in
I_{N}}\prod_{\epsilon\in\\{0,1\\}^{k}}a_{n+h_{1}\epsilon_{1}+\cdots+h_{k}\epsilon_{k}}(x)\Big{\|}_{L^{2}(X,\mu)}\\\
&\quad\quad\leq C\min_{1\leq j\leq
d}\interleave\Big{(}\prod_{\epsilon\in\\{0,1\\}^{k}}T^{c_{j}(h_{1}\epsilon_{1}+\cdots+h_{k}\epsilon_{k})}f_{j}\Big{)}\interleave_{d},\end{split}$

where $C$ is a positive constant only depending on $c_{1},\ldots,c_{d}$. By
[20, Theorem 1.1] the averages

$\frac{1}{|I_{N}|}\sum_{n\in
I_{N}}\prod_{\epsilon\in\\{0,1\\}^{k}}a_{n+h_{1}\epsilon_{1}+\cdots+h_{k}\epsilon_{k}}(x)$

converge in $L^{2}(X,\mu)$. As a consequence, a subsequence of this sequence
of averages converges $\mu$-almost everywhere. This subsequence depends on the
parameter $\underline{h}$, but since there are only countably many such
parameters, by a diagonal argument we can find a subsequence ${\bf
I}^{\prime}=(I_{N}^{\prime})_{N\in\mathbb{N}}$ such that for $\mu$-almost
every $x\in X$ the limit

(B.10) $c_{\underline{h}}({\bf
I}^{\prime},a(x))=\lim_{N\to\infty}\frac{1}{|I_{N}^{\prime}|}\sum_{n\in
I_{N}}\prod_{\epsilon\in\\{0,1\\}^{k}}a_{n+h_{1}\epsilon_{1}+\cdots+h_{k}\epsilon_{k}}(x)$

exists for every choice of
$\underline{h}=(h_{1},\ldots,h_{k})\in\mathbb{Z}^{k}$. This means that, for
$\mu$-almost every $x\in X$, the sequence of intervals ${\bf I}^{\prime}$ is
$k$-adapted to the sequence $a(x)=(a_{n}(x))_{n\in\mathbb{N}}$. By (B.9),

(B.11) $\big{\|}c_{\underline{h}}({\bf
I}^{\prime},a(x))\big{\|}_{L^{2}(X,\mu)}\leq C\min_{1\leq j\leq
d}\interleave\Big{(}\prod_{\epsilon\in\\{0,1\\}^{k}}T^{c_{j}(h_{1}\epsilon_{1}+\cdots+h_{k}\epsilon_{k})}f_{j}\Big{)}\interleave_{d}.$

Let $\Phi_{H}=[1,H_{1}]\times\cdots\times[1,H_{k}]$,
$H_{1},\ldots,H_{k}\in\mathbb{N}$. Assume that $\interleave
f_{j}\interleave_{k+d}=0$ for some $j\in\\{1,2,\ldots,d\\}$. Then by (B.11)

(B.12)
$\begin{split}&\quad\big{\|}\frac{1}{|\Phi_{H}|}\sum_{\underline{h}\in\Phi_{H}}c_{\underline{h}}({\bf
I}^{\prime},a(x))\big{\|}_{L^{2}(X,\mu)}\leq\frac{1}{|\Phi_{H}|}\sum_{\underline{h}\in\Phi_{H}}\big{\|}c_{\underline{h}}({\bf
I}^{\prime},a(x))\big{\|}_{L^{2}(X,\mu)}\\\
&\leq\frac{1}{|\Phi_{H}|}\sum_{\underline{h}\in\Phi_{H}}C\interleave\Big{(}\prod_{\epsilon\in\\{0,1\\}^{k}}T^{c_{j}(h_{1}\epsilon_{1}+\cdots+h_{k}\epsilon_{k})}f_{j}\Big{)}\interleave_{d}\\\
&=C\cdot\frac{1}{H_{1}}\sum_{h_{1}=1}^{H_{1}}\ldots\frac{1}{H_{k}}\sum_{h_{k}=1}^{H_{k}}\interleave\Big{(}\prod_{\epsilon\in\\{0,1\\}^{k}}T^{c_{j}(h_{1}\epsilon_{1}+\cdots+h_{k}\epsilon_{k})}f_{j}\Big{)}\interleave_{d}.\end{split}$

Now we have

$\begin{split}&\limsup_{H_{k}\to\infty}\frac{1}{H_{k}}\sum_{h_{k}=1}^{H_{k}}\interleave\Big{(}\prod_{\epsilon\in\\{0,1\\}^{k}}T^{c_{j}(h_{1}\epsilon_{1}+\cdots+h_{k}\epsilon_{k})}f_{j}\Big{)}\interleave_{d}\\\
\leq&\limsup_{H_{k}\to\infty}\Big{(}\frac{1}{H_{k}}\sum_{h_{k}=1}^{H_{k}}\interleave\Big{(}\prod_{\epsilon\in\\{0,1\\}^{k}}T^{c_{j}(h_{1}\epsilon_{1}+\cdots+h_{k}\epsilon_{k})}f_{j}\Big{)}\interleave_{d}^{2^{d}}\Big{)}^{1/2^{d}}\\\
=&\limsup_{H_{k}\to\infty}\Big{(}\frac{1}{H_{k}}\sum_{h_{k}=1}^{H_{k}}\interleave(\prod_{\epsilon\in\\{0,1\\}^{k-1}}T^{c_{j}(h_{1}\epsilon_{1}+\cdots+h_{k-1}\epsilon_{k-1})}f_{j})T^{c_{j}h_{k}}\cdot\\\
&\quad\quad\quad\quad\quad\quad\quad(\prod_{\epsilon\in\\{0,1\\}^{k-1}}T^{c_{j}(h_{1}\epsilon_{1}+\cdots+h_{k-1}\epsilon_{k-1})}f_{j})\interleave_{d}^{2^{d}}\Big{)}^{1/2^{d}}\\\
\leq&\limsup_{H_{k}\to\infty}|c_{j}|^{\frac{1}{2^{d}}}\Big{(}\frac{1}{|c_{j}|H_{k}}\sum_{l=1}^{|c_{j}|H_{k}}\interleave(\prod_{\epsilon\in\\{0,1\\}^{k-1}}T^{c_{j}(h_{1}\epsilon_{1}+\cdots+h_{k-1}\epsilon_{k-1})}f_{j})T^{l}\cdot\\\
&\quad\quad\quad\quad\quad\quad\quad(\prod_{\epsilon\in\\{0,1\\}^{k-1}}T^{c_{j}(h_{1}\epsilon_{1}+\cdots+h_{k-1}\epsilon_{k-1})}f_{j})\interleave_{d}^{2^{d}}\Big{)}^{\frac{1}{2^{d}}}\\\
=&|c_{j}|^{1/2^{d}}\interleave\Big{(}\prod_{\epsilon\in\\{0,1\\}^{k-1}}T^{c_{j}(h_{1}\epsilon_{1}+\cdots+h_{k-1}\epsilon_{k-1})}f_{j}\Big{)}\interleave_{d+1}^{2},\end{split}$

where the inequality holds by using the inequality
$(\frac{1}{N}\sum_{n=1}^{N}B_{n}^{k_{1}})^{1/k_{1}}\leq(\frac{1}{N}\sum_{n=1}^{N}B_{n}^{k_{2}})^{1/k_{2}}$,
for all $B_{1},\ldots,B_{N}>0$ and $k_{1}\leq k_{2}\in\mathbb{N}$, the last
equality is by Lemma 2.4.

Similarly, we have

$\begin{split}&\limsup_{H_{k-1}\to\infty}\frac{1}{H_{k-1}}\sum_{h_{k-1}=1}^{H_{k-1}}\limsup_{H_{k}\to\infty}\frac{1}{H_{k}}\sum_{h_{k}=1}^{H_{k}}\interleave\Big{(}\prod_{\epsilon\in\\{0,1\\}^{k}}T^{c_{j}(h_{1}\epsilon_{1}+\cdots+h_{k}\epsilon_{k})}f_{j}\Big{)}\interleave_{d}\\\
&\quad\leq|c_{j}|^{1/2^{d}}\limsup_{H_{k-1}\to\infty}\frac{1}{H_{k-1}}\sum_{h_{k-1}=1}^{H_{k-1}}\interleave\Big{(}\prod_{\epsilon\in\\{0,1\\}^{k-1}}T^{c_{j}(h_{1}\epsilon_{1}+\cdots+h_{k-1}\epsilon_{k-1})}f_{j}\Big{)}\interleave_{d+1}^{2}\\\
&\quad\leq|c_{j}|^{1/2^{d}}\limsup_{H_{k-1}\to\infty}\left(\Big{(}\frac{1}{H_{k-1}}\sum_{h_{k-1}=1}^{H_{k-1}}\interleave\Big{(}\prod_{\epsilon\in\\{0,1\\}^{k-1}}T^{c_{j}(h_{1}\epsilon_{1}+\cdots+h_{k-1}\epsilon_{k-1})}f_{j}\Big{)}\interleave_{d+1}^{2^{d+1}}\Big{)}^{1/2^{d+1}}\right)^{2}\\\
&\quad\leq|c_{j}|^{1/2^{d}}\Big{(}|c_{j}|^{1/2^{d+1}}\interleave\Big{(}\prod_{\epsilon\in\\{0,1\\}^{k-2}}T^{c_{j}(h_{1}\epsilon_{1}+\cdots+h_{k-2}\epsilon_{k-2})}f_{j}\Big{)}\interleave_{d+2}^{2}\Big{)}^{2}\\\
&\quad=|c_{j}|^{1/2^{d-1}}\interleave\Big{(}\prod_{\epsilon\in\\{0,1\\}^{k-2}}T^{c_{j}(h_{1}\epsilon_{1}+\cdots+h_{k-2}\epsilon_{k-2})}f_{j}\Big{)}\interleave_{d+2}^{2^{2}}.\end{split}$

Repeating this progress several times, we have

$\limsup_{H_{1}\to\infty}\frac{1}{H_{1}}\sum_{h_{1}=1}^{H_{1}}\cdots\limsup_{H_{k}\to\infty}\frac{1}{H_{k}}\sum_{h_{k}=1}^{H_{k}}\interleave\Big{(}\prod_{\epsilon\in\\{0,1\\}^{k}}T^{a_{j}(h_{1}\epsilon_{1}+\cdots+h_{k}\epsilon_{k})}f_{j}\Big{)}\interleave_{d}\leq|c_{j}|^{\frac{1}{2^{d-k+1}}}\interleave
f_{j}\interleave_{d+k}^{2^{k}}.$

Combining with (B.12), we have

(B.13)
$\begin{split}&\quad\limsup_{H_{1}\to\infty}\cdots\limsup_{H_{k}\to\infty}\big{\|}\frac{1}{|\Phi_{H}|}\sum_{\underline{h}\in\Phi_{H}}c_{\underline{h}}({\bf
I}^{\prime},a(x))\big{\|}_{L^{2}(X,\mu)}\\\
&\leq\limsup_{H_{1}\to\infty}\frac{1}{H_{1}}\sum_{h_{1}=1}^{H_{1}}\cdots\limsup_{H_{k}\to\infty}\frac{1}{H_{k}}\sum_{h_{k}=1}^{H_{k}}C\interleave\Big{(}\prod_{\epsilon\in\\{0,1\\}^{k}}T^{c_{j}(h_{1}\epsilon_{1}+\cdots+h_{k}\epsilon_{k})}f_{j}\Big{)}\interleave_{d}\\\
&\leq C|c_{j}|^{\frac{1}{2^{d-k+1}}}\cdot\interleave
f_{j}\interleave_{d+k}^{2^{k}}.\end{split}$

By Remark B.2,

$\interleave a\interleave_{{\bf
I}^{\prime},k}=\left(\lim_{H_{k}\to\infty}\frac{1}{H_{k}}\sum_{h_{k}=1}^{H_{k}}\cdots\lim_{H_{1}\to\infty}\frac{1}{H_{1}}\sum_{h_{1}=1}^{H_{1}}c_{\underline{h}}({\bf
I}^{\prime},a)\right)^{1/2^{k}}.$

Thus by Hölder inequality and by (B.13), we get

$\begin{split}&\quad\left\|\interleave a\interleave_{{\bf
I}^{\prime},k}\right\|^{2^{k}}_{L^{2}(X,\mu)}=\left(\int_{X}\interleave
a\interleave_{{\bf
I}^{\prime},k}^{2}d\mu\right)^{2^{k-1}}\leq\int_{X}\interleave
a\interleave_{{\bf I}^{\prime},k}^{2^{k}}d\mu\\\
&=\int_{X}\left(\lim_{H_{k}\to\infty}\frac{1}{H_{k}}\sum_{h_{k}=1}^{H_{k}}\cdots\lim_{H_{1}\to\infty}\frac{1}{H_{1}}\sum_{h_{1}=1}^{H_{1}}c_{\underline{h}}({\bf
I}^{\prime},a)\right)d\mu\\\
&=\lim_{H_{1}\to\infty}\ldots\lim_{H_{k}\to\infty}\int_{X}\left(\frac{1}{H_{1}}\sum_{h_{1}=1}^{H_{1}}\cdots\frac{1}{H_{k}}\sum_{h_{k}=1}^{H_{k}}c_{\underline{h}}({\bf
I}^{\prime},a)\right)d\mu\\\
&\leq\limsup_{H_{1}\to\infty}\cdots\limsup_{H_{k}\to\infty}\big{\|}\frac{1}{|\Phi_{H}|}\sum_{\underline{h}\in\Phi_{H}}c_{\underline{h}}({\bf
I}^{\prime},a(x))\big{\|}_{L^{2}(X,\mu)}\\\
&\overset{\eqref{app8}}{\leq}C|c_{j}|^{\frac{1}{2^{d-k+1}}}\cdot\interleave
f_{j}\interleave_{d+k}^{2^{k}}.\end{split}$

Hence we have

(B.14) $\Big{\|}\interleave a(x)\interleave_{{\bf
I}^{\prime},k}\Big{\|}_{L^{2}(X,\mu)}\leq
C^{\frac{1}{2^{k}}}|c_{j}|^{\frac{1}{2^{d+1}}}\cdot\interleave
f_{j}\interleave_{d+k}=0.$

Thus for $\mu$-a.e. $x\in X$, $\interleave a(x)\interleave_{{\bf
I}^{\prime},k}=0$. By Theorem B.3, we have

$\frac{1}{|I_{N}^{\prime}|}\sum_{n\in I_{N}^{\prime}}\phi_{n}(x)a_{n}(x)\to
0,N\to\infty,\ \mu\text{-almost everywhere},$

and (B.7) is proved. This completes the proof of Step 1.

Step 2. For all all non-zero distinct $a_{1},\ldots,a_{d}\in\mathbb{Z}$ and
for all $f_{1},\ldots,f_{d}\in L^{\infty}(X,\mu)$, the averages

$\frac{1}{N-M}\sum_{n=M}^{N-1}\phi_{n}(x)f_{1}(T^{a_{1}n}x)f_{2}(T^{a_{2}n}x)\cdots
f_{d}(T^{a_{d}n}x)$

converge in $L^{2}(X,\mu)$ as $N-M\to\infty$.

By Step 1, for all non-zero distinct $a_{1},\ldots,a_{d}\in\mathbb{Z}$ and for
all $f_{1},\ldots,f_{d}\in L^{\infty}(X,\mu)$, if $\interleave
f_{j}\interleave_{k+d}=0$ for some $j\in\\{1,\ldots,d\\}$, then the averages

$\frac{1}{N-M}\sum_{n=M}^{N-1}\phi_{n}(x)f_{1}(T^{a_{1}n}x)f_{2}(T^{a_{2}n}x)\cdots
f_{d}(T^{a_{d}n}x)$

converge to 0 in $L^{2}(X,\mu)$. Thus we can restrict to the case where
$f_{j},1\leq j\leq d$, is measurable with respect to $\mathcal{Z}_{m}$ for
some $m\in\mathbb{N}$.

By Remark 2.18-(2), for every $\epsilon>0$ there exists $\widetilde{f}_{j}\in
L^{\infty}(X,\mu)$ such that $\widetilde{f}_{j}$ is
$\mathcal{Z}_{m}$-measurable and
$\|f_{j}-\widetilde{f}_{j}\|_{L^{1}(X,\mu)}<\epsilon,1\leq j\leq d$, and for
$\mu$-almost all $x\in X$ the sequence
$(\widetilde{f}_{j}(T^{n}x))_{n\in\mathbb{Z}}$ is an $m$-step nilsequence.
Thus
$(\Psi_{n}(x))_{n\in\mathbb{Z}}=\Big{(}\prod_{j=1}^{d}\widetilde{f}_{j}(T^{a_{j}n}x)\Big{)}_{n\in\mathbb{Z}}$
is a nilsequence. Therefore, it suffices to show the existence in
$L^{2}(X,\mu)$ of the limit

$\lim_{N\to\infty}\frac{1}{N}\sum_{n=0}^{N-1}\phi_{n}(x)\Psi_{n}(x).$

This follows from Theorem 2.8 since both are nilsequences. The proof of Step 2
is complete.

Step 3. For all non-zero distinct $a_{1},\ldots,a_{d}\in\mathbb{Z}$ and
essentially distinct non-linear integral polynomials $p_{1},\ldots,p_{s}$ for
all $f_{1},\ldots,f_{d},g_{1},\ldots,g_{s}\in L^{\infty}(X,\mu)$, there is
some $m\in\mathbb{N}$ such that if $\interleave g_{j}\interleave_{m}=0$ for
some $j\in\\{1,\ldots,s\\}$, then the averages

(B.15) $\frac{1}{N-M}\sum_{n=M}^{N-1}\phi_{n}(x)f_{1}(T^{a_{1}n}x)\cdots
f_{d}(T^{a_{d}n}x)\cdot g_{1}(T^{p_{1}(n)}x)\cdots
g_{s}(T^{p_{s}(n)}x)\rightarrow 0$

in $L^{2}(X,\mu)$ as $N-M\to\infty$.

In order to prove (B.15), it suffices to show that every sequence of intervals
${\bf I}=(I_{N})_{N\in\mathbb{N}}$ whose lengths $|I_{N}|$ tend to infinity,
admits a subsequence ${\bf I}^{\prime}=(I_{N}^{\prime})_{N\in\mathbb{N}}$ such
that

(B.16) $\frac{1}{|I_{N}^{\prime}|}\sum_{n\in
I_{N}^{\prime}}\phi_{n}(x)f_{1}(T^{a_{1}n}x)\cdots f_{d}(T^{a_{d}n}x)\cdot
g_{1}(T^{p_{1}(n)}x)\cdots g_{s}(T^{p_{s}(n)}x)\rightarrow 0,\ N\to\infty$

in $L^{2}(X,\mu)$.

For $x\in X$, we write $b(x)=(b_{n}(x))_{n\in\mathbb{N}}$ for the sequence
defined by

$b_{n}(x)=f_{1}(T^{a_{1}n}x)\cdots f_{d}(T^{a_{d}n}x)\cdot
g_{1}(T^{p_{1}(n)}x)\cdots g_{s}(T^{p_{s}(n)}x).$

For every $\underline{h}=(h_{1},\ldots,h_{k})\in\mathbb{Z}^{k}$ , we study the
averages

(B.17) $\frac{1}{|I_{N}|}\sum_{n\in
I_{N}}\prod_{\epsilon\in\\{0,1\\}^{k}}b_{n+h_{1}\epsilon_{1}+\cdots+h_{k}\epsilon_{k}}(x).$

Let $D=\\{\underline{h}=(h_{1},\ldots,h_{k})\in\mathbb{Z}^{k}:$
$p_{j}(n+h_{1}\epsilon_{1}+\cdots+h_{k}\epsilon_{k}),1\leq j\leq
s,\epsilon\in\\{0,1\\}^{k}$ are essentially distinct integral polynomials
$\\}\subset\mathbb{Z}^{k}$. By [26, Lemma 6.1], if $p_{1},p_{2}$ are two
essentially distinct integral polynomials of degree $\geq 2$, then there is a
positive constant $L$ depending on $p_{1},p_{2}$ such that whenever
$k_{1},k_{2}\in\mathbb{Z}$ with $|k_{1}-k_{2}|\geq L$, the integral
polynomials $p_{i_{1}}(n+k_{j_{1}})-p_{i_{1}}(k_{j_{1}})$ and
$p_{i_{2}}(n+k_{j_{2}})-p_{i_{2}}(k_{j_{2}})$ in one variable $n$ are
essentially distinct for each
$(i_{1},j_{1})\neq(i_{2},j_{2})\in\\{1,2\\}\times\\{1,2\\}$. By this fact, it
is easy to see that $D$ has zero density in $\mathbb{Z}^{k}$.

For all $\underline{h}\in D$, since
$p_{j}(n+h_{1}\epsilon_{1}+\cdots+h_{k}\epsilon_{k}),1\leq j\leq
s,\epsilon\in\\{0,1\\}^{k}$ are essentially distinct integral polynomials with
degree $\geq 2$, by Theorem 4.1 there is some integer $m$ (depending only on
the weight of polynomials $\\{p_{1},\ldots,p_{s}\\}$) such that (B.17)
converges to $0$ in $L^{2}(X,\mu)$.

Similar to the proof of Step 1, there exists a subsequence ${\bf
I}^{\prime}=(I_{N}^{\prime})_{N\in\mathbb{N}}$ such that for $\mu$-almost
every $x\in X$ the limit

(B.18) $c_{\underline{h}}({\bf
I}^{\prime},b(x))=\lim_{N\to\infty}\frac{1}{|I_{N}^{\prime}|}\sum_{n\in
I_{N}}\prod_{\epsilon\in\\{0,1\\}^{k}}b_{n+h_{1}\epsilon_{1}+\cdots+h_{k}\epsilon_{k}}(x)=0$

for every choice of $\underline{h}=(h_{1},\ldots,h_{k})\in D$. This means
that, for $\mu$-almost every $x\in X$, the sequence of intervals ${\bf
I}^{\prime}$ is $k$-adapted to the sequence $b(x)=(b_{n}(x))_{n\in\mathbb{N}}$
and $c_{\underline{h}}({\bf I}^{\prime},b(x))=0$ for every
$\underline{h}=(h_{1},\ldots,h_{k})\in D$. Therefore for $\mu$-a.e. $x\in X$

$\interleave b(x)\interleave_{{\bf
I}^{\prime},k}=\left(\lim_{H\to\infty}\frac{1}{H^{k}}\sum_{\underline{h}\in[0,H-1]^{k}}c_{\underline{h}}({\bf
I}^{\prime},b(x))\right)^{1/2^{k}}=0,$

since $D$ has zero density in $\mathbb{Z}^{k}$. By Theorem B.3, we have

$\frac{1}{|I_{N}^{\prime}|}\sum_{n\in I_{N}^{\prime}}\phi_{n}(x)b_{n}(x)\to
0,N\to\infty,\ \mu\text{-almost everywhere},$

and (B.16) is proved. This completes the proof of Step 3.

Step 4. For all non-zero distinct $a_{1},\ldots,a_{d}\in\mathbb{Z}$ and
essentially distinct non-linear integral polynomials $p_{1},\ldots,p_{s}$ for
all $f_{1},\ldots,f_{d},g_{1},\ldots,g_{s}\in L^{\infty}(X,\mu)$, the averages

(B.19) $\frac{1}{N-M}\sum_{n=M}^{N-1}\phi_{n}(x)f_{1}(T^{a_{1}n}x)\cdots
f_{d}(T^{a_{d}n}x)\cdot g_{1}(T^{p_{1}(n)}x)\cdots g_{s}(T^{p_{s}(n)}x)$

converge in $L^{2}(X,\mu)$ as $N-M\to\infty$.

By Step 3, for all non-zero distinct $a_{1},\ldots,a_{d}\in\mathbb{Z}$ and
essentially distinct non-linear integral polynomials $p_{1},\ldots,p_{s}$ for
all $f_{1},\ldots,f_{d},g_{1},\ldots,g_{s}\in L^{\infty}(X,\mu)$, there is
some $m\in\mathbb{N}$ such that if $\interleave g_{j}\interleave_{m}=0$ for
some $j\in\\{1,\ldots,s\\}$, then the averages

(B.20) $\frac{1}{N-M}\sum_{n=M}^{N-1}\phi_{n}(x)f_{1}(T^{a_{1}n}x)\cdots
f_{d}(T^{a_{d}n}x)\cdot g_{1}(T^{p_{1}(n)}x)\cdots g_{s}(T^{p_{s}(n)}x)$

converge to 0 in $L^{2}(X,\mu)$. Thus we can restrict to the case where
$g_{j},1\leq j\leq s$, is measurable with respect to $\mathcal{Z}_{m}$ for
some $m\in\mathbb{N}$.

By Remark 2.18-(2), for every $\epsilon>0$ there exists $\widetilde{g}_{j}\in
L^{\infty}(X,\mu)$ such that $\widetilde{g}_{j}$ is
$\mathcal{Z}_{m}$-measurable and
$\|g_{j}-\widetilde{g}_{j}\|_{L^{1}(X,\mu)}<\epsilon,1\leq j\leq s$, and for
$\mu$-almost all $x\in X$ the sequence
$(\widetilde{g}_{j}(T^{n}x))_{n\in\mathbb{Z}}$ is an $m$-step nilsequence. By
[31, Proposition 3.14] or [23, Theorem 14.15], for $\mu$-almost all $x\in X$
the sequence $(\widetilde{g}_{j}(S^{p_{j}(n)}x))_{n\in\mathbb{Z}}$ is a
$(m\deg{p_{j}})$-step nilsequence for $1\leq j\leq s$. Let
$X_{1}\in\mathcal{X}$ be a full measure subset of $X$ for which this property
holds. Thus
$(\Psi_{n}(x))_{n\in\mathbb{Z}}=\Big{(}\prod_{j=1}^{s}\widetilde{g}_{j}(T^{a_{j}n}x)\Big{)}_{n\in\mathbb{Z}}$
is a nilsequence. Therefore, it suffices to show the existence in
$L^{2}(X,\mu)$ of the limit

$\lim_{N\to\infty}\frac{1}{N}\sum_{n=0}^{N-1}\phi_{n}(x)\Psi_{n}(x)f_{1}(T^{a_{1}n}x)\cdots
f_{d}(T^{a_{d}n}x)$

This follows from Step 2 since $\phi_{n}(x)\Psi_{n}(x)$ is a nilsequence. The
whole proof is complete. ∎

##  Appendix C A lemma about topological models

The proof of the following result was outlined in [16]. So for completeness,
we give a proof here, following the proof of [17, Theorem 5.15] and [19,
Theorem 2.15]. Theorem C.1 is a little stronger than Theorem 8.6.

######  Theorem C.1.

Let $(X,\mathcal{X},\mu,T)$ be a m.p.s. and let
$\\{f_{k}\\}_{k\in\mathbb{N}}\subseteq L^{\infty}(X,\mu)$. Then there is a
t.d.s. $(X^{\prime},T^{\prime})$, a $T^{\prime}$-invariant measure
$\mu^{\prime}$ and an isomorphism
$\psi:(X,\mathcal{X},\mu,T)\rightarrow(X^{\prime},\mathcal{B}(X^{\prime}),\mu^{\prime},T^{\prime})$
such that for all $k\in\mathbb{N}$,
$f^{\prime}_{k}=f_{k}\circ\psi^{-1}\pmod{\mu^{\prime}}$, where
$f_{k}^{\prime}\in C(X^{\prime})$.

###### Proof.

Without loss of generality, we assume that $f_{k}$ is real-valued function for
all $k\in\mathbb{N}$. For each $k\in\mathbb{N}$, since $f_{k}\in
L^{\infty}(X,\mu)$, there is an interval $[a_{k},b_{k}]\subseteq\mathbb{R}$
and a measurable function $g_{k}:X\rightarrow[a_{k},b_{k}]$ such that
$f_{k}(x)=g_{k}(x)$ for $\mu$-a.e. $x\in X$. Let
$\\{I^{(k)}_{i}\\}_{i\in\mathbb{N}}$ be a countable base of $[a_{k},b_{k}]$.
Let $B^{(k)}_{i}=g_{k}^{-1}(I^{(k)}_{i}),i\in\mathbb{N}$. Then
$\bigcup_{k\in\mathbb{N}}\\{B^{(k)}_{i}\\}_{i\in\mathbb{N}}$ is a countable
subset of $\mathcal{X}$.

Now choose a sequence $\\{A_{n}\\}_{n\in\mathbb{N}}$ of distinct elements of
$\mathcal{X}$ such that:

  1. (1)

The sequence $\\{A_{n}\\}_{n\in\mathbb{N}}$ is dense in the measure algebra
$(\mathcal{X},\mu)$, and separate points of $X$ (i.e. for every $x\neq
x^{\prime}$ there is an $A_{n}$ with $x\in A_{n}$ but $x^{\prime}\not\in
A_{n}$);

  2. (2)

$\\{A_{n}\\}_{n\in\mathbb{N}}$ is invariant under $T$, i.e. there is a
permutation $\theta:\mathbb{N}\rightarrow\mathbb{N}$ such that
$T^{-1}A_{n}=A_{\theta(n)}$;

  3. (3)

$\bigcup_{k\in\mathbb{N}}\\{B^{(k)}_{i}\\}_{i\in\mathbb{N}}\subseteq\\{A_{n}\\}_{n\in\mathbb{N}}$.

Let $\mathcal{A}$ be the countable algebra generated by
$\\{A_{n}\\}_{n\in\mathbb{N}}$. Now put $X^{\prime}=\\{0,1\\}^{\mathbb{N}}$,
$\mathcal{X}^{\prime}=\mathcal{B}(X^{\prime})$ and $A_{n}^{\prime}=\\{\xi\in
X^{\prime}:\xi(n)=\xi_{n}=1\\}$. For every $N\in\mathbb{N}$, let $\mu_{N}$ be
the probability measure defined on the finite space $\\{0,1\\}^{N}$ by

$\mu_{N}(A^{\prime}_{n_{1}}\cap A^{\prime}_{n_{2}}\cap\cdots\cap
A^{\prime}_{n_{s}})=\mu(A_{n_{1}}\cap A_{n-2}\cap\cdots\cap A_{n_{s}}),1\leq
n_{1}<n_{2}<\ldots<n_{s}\leq N.$

Let $\mu^{\prime}_{N}$ be any extension of $\mu_{N}$ to a Borel probability
measure on $X^{\prime}$. Let $\mu_{N_{j}}^{\prime}\to\mu^{\prime},j\to\infty$
be a weak∗ convergence subsequence. The measure $\mu^{\prime}$ satisfies the
equalities above for all finite sequences $n_{1}<n_{2}<\ldots<n_{s}$, i.e.

$\mu^{\prime}(A^{\prime}_{n_{1}}\cap A^{\prime}_{n_{2}}\cap\cdots\cap
A^{\prime}_{n_{s}})=\mu(A_{n_{1}}\cap A_{n-2}\cap\cdots\cap A_{n_{s}}),\
\forall 1\leq n_{1}<n_{2}<\ldots<n_{s}.$

The map $\Psi(A_{n}^{\prime})=A_{n},\forall n\in\mathbb{N}$ can be extended to
an isomorphism of measure algebra
$\Psi:(\mathcal{A}^{\prime},\mu^{\prime})\rightarrow(\mathcal{A},\mu)$, where
$\mathcal{A}^{\prime}$ is the sub-algebra of
$\mathcal{X}^{\prime}=\mathcal{B}(X^{\prime})$ determined by
$\\{A_{n}^{\prime}\\}_{n\in\mathbb{N}}$. The permutation $\theta$ defines a
homeomorphism $T^{\prime}:X^{\prime}\rightarrow X^{\prime},\xi\mapsto
T^{\prime}\xi$, where

$(T^{\prime}\xi)_{n}=\xi_{\theta(n)},\ \forall n\in\mathbb{N}.$

Since $T^{-1}A_{n}=A_{\theta(n)}$, by the definition of $T^{\prime}$ it
follows that $(T^{\prime})^{-1}A^{\prime}_{n}=A^{\prime}_{\theta(n)}$. Thus we
have that $T^{\prime}:X^{\prime}\rightarrow X^{\prime}$ is measure-preserving,
and $(X^{\prime},\mathcal{X}^{\prime},\mu^{\prime},T^{\prime})$ is a m.p.s.

Next define a map

$\psi:X\rightarrow X^{\prime},\ \big{(}\psi(x)\big{)}_{n}=1_{A_{n}}(x).$

Since the sequence $\\{A_{n}\\}_{n\in\mathbb{N}}$ separates points of $X$,
$\psi$ is a Borel 1-1 map of $X$ into $X^{\prime}$ with $\Psi=\psi^{-1}$. Let
$X_{0}^{\prime}=\psi(X)$. By Lusin-Souslin Theorem [33, Corollary 15.2],
$X_{0}^{\prime}$ is a Borel subset of $X^{\prime}$ and $\psi$ is a Borel
isomorphism of $X$ with $X_{0}^{\prime}$. Note that
$\mu(X)=\mu^{\prime}(X_{0}^{\prime})=1$ and $(\psi\circ
T)(x)=(T^{\prime}\circ\psi)(x),\forall x\in X$. Thus
$\psi:(X,\mathcal{X},\mu,T)\rightarrow(X^{\prime},\mathcal{X}^{\prime},\mu^{\prime},T^{\prime})$
is an isomorphism.

Now for each $k\in\mathbb{N}$,
$f^{\prime}_{k}=g_{k}\circ\psi^{-1}:X^{\prime}\rightarrow[a_{k},b_{k}]$, we
have that for each $i\in\mathbb{N}$,

$(f_{k}^{\prime})^{-1}(I^{(k)}_{i})=(g_{k}\circ\psi^{-1})^{-1}(I^{(k)}_{i})=\psi(g_{k}^{-1}(I^{(k)}_{i}))=\psi(B^{(k)}_{i})\in\\{A_{n}^{\prime}\\}_{n\in\mathbb{N}}$

is an open subset of $X^{\prime}$. Since $\\{I^{(k)}_{i}\\}_{i\in\mathbb{N}}$
be a countable base of $[a_{k},b_{k}]$, $f_{k}^{\prime}$ is continuous. Note
that each $k\in\mathbb{N}$, $f_{k}(x)=g_{k}(x)$ for $\mu$-a.e. $x\in X$, and
it follows that $f^{\prime}_{k}(x^{\prime})=f_{k}\circ\psi^{-1}(x^{\prime})$
for $\mu^{\prime}$-a.e. $x^{\prime}\in X^{\prime}$. The proof is complete. ∎

## References

  * [1] I. Assani and R. Moore, Extension of Wiener-Wintner double recurrence theorem to polynomials, J. Anal. Math., 134 (2018), no. 2, 597–613.
  * [2] V. Bergelson, Weakly mixing PET, Ergodic Theory Dynam. Systems, 7 (1987), 337–349.
  * [3] V. Bergelson, Combinatorial and Diophantine applications of ergodic theory, Appendix A by A. Leibman and Appendix B by Anthony Quas and Máté Wierdl. Handbook of dynamical systems. Vol. 1B, 745–869, Elsevier B. V., Amsterdam, 2006.
  * [4] V. Bergelson, B. Host and B. Kra, Multiple recurrence and nilsequences. With an appendix by Imre Ruzsa, Invent. Math., 160 (2005), 261–303.
  * [5] V. Bergelson and A. Leibman, Polynomial extensions of van der Waerden’s and Szemerédi’s theorems, J. Amer. Math. Soc., 9 (1996), 725–753.
  * [6] J. Bourgain, Pointwise ergodic theorems for arithmetic sets. With an appendix by the author, H. Furstenberg, Y. Katznelson and D, S. Ornstein, Inst. Hautes études Sci. Publ. Math. No. 69 (1989), 5–45.
  * [7] J. Bourgain, Double recurrence and almost sure convergence, J. Reine Angew. Math., 404 (1990), 140–161.
  * [8] Q. Chu, N. Frantzikinakis and B. Host, Ergodic averages of commuting transformations with distinct degree polynomial iterates, Proc. Lond. Math. Soc., 102 (2011), no. 5, 801–842.
  * [9] T. de la Rue, Notes on Austin’s multiple ergodic theorem, arXiv:0907.0538
  * [10] J. Derrien and E. Lesigne, Un théorème ergodique polynomial ponctuel pourles endomorphismes exacts et les K-systèmes, Ann. Inst. H. Poincaré Probab. Statist., 32 (1996), no.6, 765–778.
  * [11] P. Dong, S. Donoso, A. Maass, S. Shao and X. Ye, Infinite-step nilsystems, independence and complexity, Ergodic Theory Dynam. Systems, 33 (2013), 118-143.
  * [12] N. Frantzikinakis, Furstenberg systems of Hardy field sequences and applications, J. Analyse Math., 147 (2022), 333-372.
  * [13] N. Frantzikinakis and B. Host, The logarithmic Sarnak conjecture for ergodic weights, Ann. of Math. (2), 187 (2018), no. 3, 869–931.
  * [14] N. Frantzikinakis and B. Host, Multiple recurrence and convergence without commutativity, arXiv:2111.01518, to appear in Journal of the London Mathematical Society.
  * [15] H. Furstenberg, Disjointness in ergodic theory, minimal sets, and a problem in Diophantine approximation, Math. Systems Theory, 1 (1967), 1–49.
  * [16] H. Furstenberg, Ergodic behavior of diagonal measures and a theorem of Szemerédi on arithmetic progressions, J. Anal. Math., 31 (1977), 204–256.
  * [17] H. Furstenberg, Recurrence in ergodic theory and combinatorial number theory, M. B. Porter Lectures. Princeton University Press, Princeton, N.J., 1981.
  * [18] H. Furstenberg and B. Weiss,  A mean ergodic theorem for $\frac{1}{N}\sum_{n=1}^{N}f(T^{n}x)g(T^{n^{2}}x)$, Convergence in ergodic theory and probability (Columbus, OH, 1993), 193–227, Ohio State Univ. Math. Res. Inst. Publ., 5, de Gruyter, Berlin, 1996.
  * [19] E. Glasner, Ergodic theory via joinings, Mathematical Surveys and Monographs, 101. American Mathematical Society, Providence, RI, 2003\. xii+384 pp.
  * [20] B. Host and B. Kra, Nonconventional averages and nilmanifolds, Ann. of Math., 161 (2005), 398–488.
  * [21] B. Host and B. Kra, Convergence of polynomial ergodic averages, Israel J. Math., 149 (2005), 1–19.
  * [22] B. Host and B. Kra, Uniformity norms on $l^{\infty}$ and applications, J. Anal. Math., 108 (2009), 219–276.
  * [23] B. Host and B. Kra, Nilpotent Structures in Ergodic Theory, Mathematical Surveys and Monographs 236, AMS, 2018.
  * [24] B. Host, B. Kra and A. Maass, Nilsequences and a structure theory for topological dynamical systems, Adv. Math. 224 (2010), 103–129.
  * [25] W. Huang, S. Shao and X. Ye, Pointwise convergence of multiple ergodic averages and strictly ergodic models, J. Anal. Math., 139 (2019), no. 1, 265–305.
  * [26] W. Huang, S. Shao and X. Ye, Topological dynamical systems induced by polynomials and combinatorial consequences, preprint, 2022.
  * [27] R.I. Jewett, The prevalence of uniquely ergodic systems, J. Math. Mech., 19 (1969/1970), 717–729.
  * [28] W. Krieger, On unique ergodicity, Proceedings of the Sixth Berkeley Symposium on Mathematical Statistics and Probability (Univ. California, Berkeley, Calif., 1970/1971), Vol. II: Probability theory, pp. 327–346, Univ. California Press, Berkeley, Calif., 1972.
  * [29] A. Leibman, Pointwise convergence of ergodic averages for polynomial sequences of rotations on a nilmanifold, Ergodic Theory Dynam. Systems, 25 (2005), 201–213.
  * [30] A. Leibman, Pointwise convergence of ergodic averages for polynomial actions of ${\mathbb{Z}}^{d}$ by translations on a nilmanifold, Ergodic Theory Dynam. Systems, 25 (2005), 215–225.
  * [31] A. Leibman,  Convergence of multiple ergodic averages along polynomials of several variable, Israel J. Math., 146 (2005), 303–315.
  * [32] A. Kanigowski, J. Kułaga-Przymus, M. Lemańczyk and T. de la Rue, On arithmetic functions orthogonal to deterministic sequences, Preprint, arXiv:2105.11737
  * [33] A. S. Kechris, Classical descriptive set theory, Graduate Texts in Mathematics, 156. Springer-Verlag, New York, 1995.
  * [34] D. Ornstein, Factors of Bernoulli shifts are Bernoulli shifts, Adv. Math., 5 (1970), 349–364.
  * [35] B. Krause, M. Mirek and T. Tao, Pointwise ergodic theorems for non-conventional bilinear polynomial averages, Ann. of Math. (2) 195 (2022), no. 3, 997–1109.
  * [36] W. Parry, Ergodic properties of affine transformations and flows on nilmanifolds, Amer. J. Math., 91 (1969), 757–771.
  * [37] W. Parry, Topics in Ergodic Theory, Cambridge Tracks in Mathematics, Cambridge University Press, Cambridge-New York, 1981.
  * [38] S. Shao and X. Ye, Regionally proximal relation of order $d$ is an equivalence one for minimal systems and a combinatorial consequence, Adv. Math. 231 (2012), 1786–1817.
  * [39] E. Szemerédi, On sets of integers containing no $k$ elements in arithmetic progression, Acta Arith., 27 (1975), 199–245.
  * [40] J. P. Thouvenot, Une classe de systèmes pour lesquels la conjecture de Pinsker est vraie, (French) Israel J. Math., 21 (1975), 208–214.
  * [41] M. Walsh, Norm convergence of nilpotent ergodic averages, Ann. of Math., 175 (2012), 1667–1688.
  * [42] B. Weiss, Strictly ergodic models for dynamical systems, Bull. Amer. Math. Soc., (N.S.) 13 (1985), 143–146.
  * [43] T. Ziegler, Universal characteristic factors and Furstenberg averages, J. Amer. Math. Soc., 20 (2007), no.1, 53–97.


# Hyperdimensional Hashing: A Robust and Efficient Dynamic Hash Table

Mike Heddes, Igor Nunes, Tony Givargis, Alexandru Nicolau and Alex Veidenbaum
Department of Computer Science, University of California,
IrvineIrvineCaliforniaUnited States of America mheddes, igord, givargis,
nicolau<EMAIL_ADDRESS>
(2022)

###### Abstract.

Most cloud services and distributed applications rely on hashing algorithms
that allow dynamic scaling of a robust and efficient hash table. Examples
include AWS, Google Cloud and BitTorrent. Consistent and rendezvous hashing
are algorithms that minimize key remapping as the hash table resizes. While
memory errors in large-scale cloud deployments are common, neither algorithm
offers both efficiency and robustness. Hyperdimensional Computing is an
emerging computational model that has inherent efficiency, robustness and is
well suited for vector or hardware acceleration. We propose Hyperdimensional
(HD) hashing and show that it has the efficiency to be deployed in large
systems. Moreover, a realistic level of memory errors causes more than 20%
mismatches for consistent hashing while HD hashing remains unaffected.

hyperdimensional computing, brain-inspired computing, consistent hashing,
rendezvous hashing, distributed hash tables, cloud computing, load balancing,
web caching.

††journalyear: 2022††copyright: rightsretained††conference: Proceedings of the
59th ACM/IEEE Design Automation Conference (DAC); July 10–14, 2022; San
Francisco, CA, USA††booktitle: Proceedings of the 59th ACM/IEEE Design
Automation Conference (DAC) (DAC ’22), July 10–14, 2022, San Francisco, CA,
USA††doi: 10.1145/3489517.3530553††isbn: 978-1-4503-9142-9/22/07††ccs:
Networks Cloud computing††ccs: Computer systems organization Reliability††ccs:
Computing methodologies Massively parallel algorithms

##  1\. Introduction

An important problem in many cloud services and distributed network
applications is the process of mapping requests to available resources.
Example systems include: load balancing in cloud data centers, web caching,
peer-to-peer (P2P) services, and distributed databases. Difficulty arises in
such highly dynamic systems because resources join and leave the cluster at
any time, due for example to cloud elasticity (Al-Dhuraibi et al., 2017),
server failures, or availability of peers in a P2P network. It is often
desirable to distribute requests evenly among resources and to minimize the
number of redistributed requests when a resource joins or leaves. A non-
uniform mapping results in overloading of resources and critical failure
points.

The simplest hash table solves the mapping problem using modular hashing.
Despite having a great lookup time complexity of $\mathcal{O}(1)$, a change in
table size (number of available resources) requires virtually all requests to
be redistributed due to the modulo operation (more details in Section 2).
Consistent hashing (Karger et al., 1997) and rendezvous hashing (Thaler and
Ravishankar, 1998) are alternative hashing algorithms that minimize
redistribution when the hash table is resized. They prevent resource
overloading at the cost of increased lookup time—$\mathcal{O}(\log n)$ and
$\mathcal{O}(n)$ respectively.

However, we show that when considered in a dynamic environment subject to
errors and failures (i.e., noise), the performance of consistent hashing and
rendezvous hashing in minimizing the number of redistributed requests
degrades. Noise can be introduced in many aspects of a system. We focus on
memory errors which can for instance be caused by soft errors in the form of
single event upsets (SEU), multi-cell upsets (MCUs) or hard errors (Hwang et
al., 2012; Sridharan and Liberty, 2012). MCUs, or burst errors, occur during a
single event and are becoming more common as the feature size decreases. For
22 nm technology MCUs are estimated to be 45% of all SEUs (Ibe et al., 2010).
Moreover, analysis of memory failures in Google’s data centers revealed that
each year a third of the machines experiences a memory error (Schroeder et
al., 2009). More robust hashing alternatives make it possible for cloud
providers to perform fewer memory swaps, reducing operation cost.

Hyperdimensional Computing (HDC) is an inherently robust emerging
computational model developed by Kanerva (Kanerva, 2009) inspired by
neuroscience. HDC tries to emulate brain-like computing by representing
information using high-dimensional random vectors, called hypervectors. This
representation shares qualities from biological neural systems such as
robustness and efficiency. Representation and transformations of data in HDC
are performed over hypervectors of fixed dimensions, allowing for massive
parallelism.

Fueled by the demonstrated properties of HDC and the aforementioned
limitations of current hashing algorithms, we propose Hyperdimensional (HD)
hashing, a new HDC-based dynamic hashing algorithm. HD hashing scales
similarly to consistent hashing while proving to be much more efficient than
rendezvous hashing. HDC’s highly parallelizable operations have been exploited
in recent research, showing that special hardware can make HD hashing far
superior in efficiency (more details in Sec. 2.3). Moreover, we show that our
algorithm is significantly more robust against noise. With 512 servers and a
10-bit MCU, HD hashing is unaffected while rendezvous and consistent hashing
mismatch 4% and 12% of requests, respectively. With MCUs becoming more common
this poses a risk for critical failures.

Our second contribution is a novel HDC encoding for representing a circle in
hyperdimensional space, we call these circular-hypervectors. They are a core
component of HD hashing as they provide the mechanism for mapping requests to
servers.

##  2\. Background

###  2.1. Consistent Hashing

Consistent hashing is a common way of distributing requests among a changing
population of servers (Mirrokni et al., 2018; Stoica et al., 2003) (often
times, the problem and the technique are referred to as consistent hashing
indistinctly). The algorithm, which gave rise to Akamai (Nygren et al., 2010),
is used in many other real-world large scale applications such as Dynamo on
Amazon Web Services (DeCandia et al., 2007) and Google Cloud Platform
(Eisenbud et al., 2016).

To describe consistent hashing, let $h(\cdot)$ denote a hash function that
takes requests as inputs (in practice an IP address or unique identifier, for
example) and $S=\\{s_{1},\dots,s_{n}\\}$ a set of servers. In modular hashing,
a request $r$ is simply assigned to $s_{i}$ where $i=h(r)\bmod n$. Instead,
consistent hashing maps both requests and servers uniformly to the unit
interval $[0,1]$, which is interpreted as a circular interval. Thereafter,
each request is assigned to the first server that succeeds it in the circle in
clockwise order. This assignment is usually done in $\mathcal{O}(\log n)$ time
using binary search.

###  2.2. Rendezvous Hashing

The basic idea of rendezvous hashing (Thaler and Ravishankar, 1998), also
known as highest random weight (HRW) hashing, is very simple. Given a hash
function $h(\cdot)$ that takes as input a server and a request, each request
$r$ is assigned to the server $s_{i}$ where:

$\displaystyle s_{i}=\underset{s\in S}{\arg\max}\;h(s,r)$

Each assignment is therefore done in $\mathcal{O}(n)$ time, since it is
necessary to compute the hash of the request paired with each server in the
system in order to compute the maximum value. In practice, Rendezvous hashing
is used less often than consistent hashing, despite distributing the requests
more uniformly, because of the increased time complexity.

###  2.3. Hyperdimensional Computing

From a comparative study of computing in animal brains and computer logic
circuits (Kanerva, 2009), Hyperdimensional Computing (HDC) emerged as a robust
and efficient alternative computation model. The central observation is that
large circuits are fundamental to the brain’s computation. HDC incorporates
this notion by computing with 10,000-bit words (hypervectors), instead of
8-to-64-bit.

Such hyperspaces (short for hyperdimensional spaces) have properties that
explain certain rich brain properties that are otherwise difficult to
reproduce on computers. For example, hypervectors encode information
holographically, meaning that each of the thousands of bits contains the same
amount of information, ensuring inherent robustness (Kanerva, 2009; Wu et al.,
2018).

In addition to representation, the other crucial part of a computer system is
information manipulation, or arithmetic. The arithmetic in HDC is based on
well-defined operations between hypervectors, such as addition (bundling),
multiplication (binding) and permutation. Another important function is
information comparison, which in HDC usually means measuring the similarity
between hypervectors using the inverse Hamming distance or the cosine
similarity. All those operations are typically dimension-independent,
providing an opportunity for massive parallelism (Li et al., 2016; Rahimi et
al., 2017).

Computational efficiency is one of the core motivations aimed at since the
conception of HDC and it is envisioned for and expected to reach full
potential in specialized hardware (Kanerva, 2009). In addition to the just
mentioned parallelizability, optimizations such as in-memory processing
promise to further increase the computational efficiency of HDC (Imani et al.,
2017a). Schmuck et al. (Schmuck et al., 2019) apply a series of hardware
techniques to optimize HDC, such as on-the-fly rematerialization of
hypervectors and special memory architectures, to improve chip area and
throughput at the same time. Particularly important to substantiate the claims
we make in this paper about efficiency (see Section 3), they demonstrate an
FPGA implementation that uses deep adder trees to perform inference in a
single clock-cycle.

##  3\. Hyperdimensional Hashing

HD hashing, illustrated in Figure 1, draws inspiration from consistent and
rendezvous hashing, but seeks a solution that is both robust and efficient by
translating the problem into a hyperdimensional computing task.

Figure 1.  Illustration of the operation of HD hashing. In this example, after
encoding each of the three servers and two requests to a circular-hypervector,
$r_{1}$ is assigned to server $s_{3}$, which is the server whose hyperspace
representation is closest to its. Likewise, $r_{2}$ is assigned to $s_{2}$.
Note that, unlike consistent hashing, the direction of rotation does not
matter.

Let $S=\\{s_{1},\dots,s_{k}\\}$ be a set of $k$ servers,
$R=\\{r_{1},\dots,r_{\ell}\\}$ a set of $\ell$ requests and
$C=\\{\mathbf{c}_{1},\dots,\mathbf{c}_{n}\\}$ a set of $n>k$ hypervectors. We
also denote by $h(\cdot)$ a hash function that takes as input a server or
request. The process of adding servers to the system in HD hashing is similar
to consistent hashing, but instead of mapping them to a unit interval (see
Sec. 2.1), HD hashing assigns (or ”encodes” in HDC terminology) each server to
a hypervector. To distribute requests among servers, HD hashing also encodes
each request. Let us represent this encoding by the function
$\mathrm{Enc}:S\cup R\to C$. Then, HD hashing encodes every server and request
as follows:

(1) $\mathrm{Enc}\left(x\right)\;=\;C\big{[}h(x)\bmod n\big{]}$

where $x$ is either a server or a request and $C\left[h(x)\bmod n\right]$
denotes the hypervector at position $h(x)\bmod n$ in $C$.

With all servers and requests encoded to the hyperspace, each request $r_{i}$
is mapped to server $s_{j}$, such that:

(2) $s_{j}\;=\;\underset{s\in
S}{\arg\max}\;\delta\big{(}\mathrm{Enc}(s),\mathrm{Enc}(r_{i})\big{)}$

where $\delta$ is a given similarity metric between a pair of hypervectors
such as inverse Hamming distance or the cosine similarity. The operation above
is the one mentioned in Section 2.3, and it is called inference due to the
first applications of HDC in learning tasks. This is exactly the operation
that Schmuck et al. (Schmuck et al., 2019) show to be optimizable to the
extreme of a single clock-cycle in special hardware. In other words, by using
hardware accelerators for HDC each mapping in HD hashing could be executed in
$\mathcal{O}(1)$ time.

One remaining, but crucial, question is: how do we create the set of
hypervectors $C$? Similar to consistent hashing, we map servers and requests
onto a circle. We then map the request to the server that is assigned to the
nearest node on the circle according to Eq. 2. To accomplish this, we
introduce circular-hypervectors as a way of representing a circle in
hyperspace such that the closer a node is on the circle the more similar its
hypervector. More properties of circular-hypervectors and the process to
create them are described in the next section.

##  4\. Circular-Hypervectors

To understand circular-hypervectors we first describe random and level-
hypervectors, both types are used to represent information in hyperspace, a
process called encoding. Encoding strategies have already been proposed for
various types of input data, such as images (Manabat et al., 2019), time
series (Imani et al., 2017b) and text (Najafabadi et al., 2016). The process
usually starts by generating a set of randomly sampled hypervectors that
represent discrete atomic pieces of information (e.g. discretized amplitudes
of a signal, values of a feature, symbols or identifiers). From these so-
called basis-hypervectors more complex objects like the ones listed above can
be encoded by combining and manipulating the basis-hypervectors using
bundling, binding and permutation operations.

The basis-hypervectors can be correlated with each other depending on what
they represent. For example, consider temperature. Clearly there is a stronger
correlation between closer temperatures. On the other hand, for symbols such
as letters, this correlation does not necessarily exist. Naturally, the most
successful encoding techniques are able to translate these correlations into
hyperspace. For this reason, categorical data (letters for example) are
encoded with independently and uniformly sampled random-hypervectors, while
scalar information (e.g. temperature) is represented using level-hypervectors
(Rahimi et al., 2016).

Level-hypervectors are created by quantizing an interval to $m$ levels and
assigning a hypervector to each. The similarity between hypervectors is
proportional to the distance between the intervals. This correlation is
achieved by assigning a random $d$-dimensional hypervector to the first
interval, and after this, subsequent intervals are obtained by flipping $d/m$
random bits at each interval. As a result, the last hypervector is completely
dissimilar to the first one.

Figure 2.  Pairwise cosine similarities between hypervectors $i$ and $j$
within different sets of 12 basis-hypervectors. An alternative visualization
in which each hypervector is represented by a node is shown below. The colors
indicate the similarity with the yellow reference node.

Circular-hypervectors are an extension to level-hypervectors that eliminate
the discontinuity in similarity between the last and first interval, as
visualized in the similarity profiles in Figure 2. By removing the
discontinuity, the hypervectors become a set with circular correlation.

The procedure for generating circular-hypervectors, illustrated in Figure 3
and detailed in Algorithm 1, starts with a single random-hypervector,
uniformly sampled from the hyperspace of dimension $d$ (generated by the
function random_hypervector($d$) in the algorithm). From there, inspired by
the creation of the level-hypervectors, a sequence of transformations (T) are
made to create $n/2$ level correlated hypervectors. Such transformations
consist of XORing (also called binding in HDC, represented by the symbol
$\oplus$) with what we name transformation-hypervectors ($\mathbf{t}$), which
are placed in a queue ($Q$). The second half of hypervectors are then obtained
by performing backward transformations (T-1): the transformation-hypervectors
are popped from $Q$ (first-in-first-out) and sequentially bound to the current
vector in order to generate the next one.

Figure 3.  Illustration of the process to create circular-hypervectors. The
curved arrows represent transformation-hypervectors being inserted in/removed
from $Q$.

1

Input : Two integers $n$ and $d$.111For ease of understanding, this version
assumes that $n$ is even. To generate a set of odd cardinality of circular-
hypervectors, simply generate $2n$ and return just
$\\{\mathbf{c}_{1},\mathbf{c}_{3},\mathbf{c}_{5},\dots,\mathbf{c}_{2n}\\}$.

Output : A set $\\{\mathbf{c}_{1},\dots,\mathbf{c}_{n}\\}$ of $n$
$d$-dimensional circular-hypervectors.

2

Define an empty queue $Q$ // Transformation Hv Queue

3 $\mathbf{c}_{1}\leftarrow$ random_hypervector($d$)

/* Perform forward transformations (T) */

4 for  _$i\in\\{2,\ldots,\frac{n}{2}\\}$_ do

$\mathbf{t}\leftarrow\mathbf{0}^{d}$ // $d$-dimensional zeros vector

5 Flip $d/m$ random bits of $\mathbf{t}$

6 $\mathbf{c}_{i}\leftarrow\mathbf{c}_{i-1}\oplus\mathbf{t}$

7 Enqueue$(Q,\mathbf{t})$

/* Perform backwards transformations (T-1) */

8 for  _$i\in\\{\frac{n}{2}+1,\dots,n\\}$_ do

9 $\mathbf{t}\leftarrow$ Dequeue$(Q)$

10 $\mathbf{c}_{i}\leftarrow\mathbf{c}_{i-1}\oplus\mathbf{t}$

return $\\{\mathbf{c}_{1},\dots,\mathbf{c}_{n}\\}$

Algorithm 1 Creation of circular-hypervectors Figure 4.  Average request
handling duration as the number of servers in the pool increases. Figure 5.
Percentage of mismatched requests when a number of bit errors occur.

##  5\. Results and Discussion

###  5.1. Experimental setup

We have created a purpose build emulation framework to empirically verify our
results. The emulator consists of two modules, a hash table and a generator.
The generator emulates the requests from the outside world being sent to the
hash table. The hash table module reads incoming requests from a buffer and
uses a hashing algorithm to map them to an available server. Servers are added
and removed using two special case requests, a join and leave request,
respectively, with a unique identifier of the server. This functional emulator
can be used to determine the computational efficiency of various hashing
algorithms as well as their robustness to memory errors as we will describe
next.

Since we do not have access to specialized HDC hardware and building the
hardware is outside the scope of our work we had to implement the HDC
operations using commodity hardware. To closely match the parallel nature of
HDC hardware, we decided to implement HDC operations on a GPU. We used an
Nvidia TITAN Xp GPU with 3840 cores and 12 GB of memory. The GPU’s
communication overhead was reduced by performing mappings in batches of 256
requests.

Each test was performed with different numbers of servers in the pool, going
up to 2048. This scale is enough to show the results and trends of interest,
but it is important to emphasize that like the other methods HD hashing can
scale to much larger clusters, and even be used hierarchically (standard way
to scale such hashing systems (Wang and Ravishankar, 2009; Shen et al., 2006))
to handle extremely high numbers of servers.

###  5.2. Efficiency

We executed each hashing function in our emulator to empirically determine its
computational efficiency. First the generator sends $n$ join requests to add
available servers to the hash table module. Then, the generator sends 10,000
requests and tracks the wall-time. From this we determine the average time to
handle a request.

Figure 6.  The discrepancy between the distribution of requests per server
obtained by each algorithm and the uniform distribution, for different numbers
of servers and bit errors, measured with the Pearson’s $\chi^{2}$ statistical
test.

For various numbers of $n$, ranging from 2 to 2048 in powers of 2 the results
are shown in Figure 4. The $\mathcal{O}(n)$ time complexity of rendezvous
hashing is clearly evident as is the superior computational efficiency of
consistent hashing with respect to rendezvous hashing. Our HDC implementation
using commodity hardware has a very similar scaling profile to consistent
hashing. This confirms our belief that HDC hardware can appropriately be
simulated by a GPU. However, as highlighted in Section 3, we expect the use of
HDC accelerators to reduce the request handling time to a constant with the
extreme of a single clock-cycle.

###  5.3. Robustness

As motivated before, the other main goal of HD hashing is to be a robust
alternative to consistent and rendezvous hashing. In order to assess the
performance of each hashing algorithm in an environment subject to noise, two
experiments were performed using the emulator’s noise injection capabilities.
The first and most important, whose results are in Figure 5, shows how the
ability of each technique to map keys to the correct value degrades when a
certain number of bits in memory are randomly flipped. Ibe et al. (Ibe et al.,
2010) show that for 22 nm technology, 4-bit and 8-bit bursts occur 10% and 1%
of the time, respectively. Moreover, errors within a machine are found to be
strongly correlated, if a machine experienced an error it is 13-228 times more
likely to experience another error in the same month (Schroeder et al., 2009).
To capture such features of a realistic scenario, we test each hashing
technique in the range of 0 to 10 bit flips.

In our experiments, HD hashing confirmed our expectations, turning out to be
far superior as none of the requests sent were matched to the wrong server.
Meanwhile, in both consistent and rendezvous hashing an increasing percentage
of mismatches occur, depending on the noise level.

In the second experiment we tested how uniform the distribution of requests
among servers is and how uniform they remain when bits of the hash values are
randomly inverted. For evaluation, we used the following Pearson’s chi-squared
test (Greenwood and Nikulin, 1996) to measure goodness of fit between our
observed frequency distribution and the uniform distribution:

$\displaystyle\chi^{2}=\sum_{s_{i}\in
S}\frac{\big{(}R\left(s_{i}\right)-E\big{)}^{2}}{E}$

where $R(s_{i})$ is the number of requests mapped to server $s_{i}$ by the
algorithm and $E=\frac{|R|}{|S|}$ is the uniformity expectation where $|R|$
and $|S|$ are the total number of requests and servers, respectively. The
results, illustrated in Figure 6, show that not only does HD hashing
distribute requests more uniformly than consistent hashing in an ideal
scenario, but also that the presence of bit errors worsens the uniformity of
consistent hashing even more, while that of HD hashing remains intact. To make
the plot more readable, we omit the rendezvous hashing result. Note, from the
description of the algorithm in Section 2.2, that rendezvous hashing is based
only on the output of the hash function, that is, a pseudo-random number.
Therefore, its assignment is perfectly (pseudo-) uniform and is not affected
by bit errors. Rendezvous hashing, however, still suffers from mismatches and
the method has less applicability due to its lower efficiency as illustrated
in Figures 5 and 4, respectively.

##  6\. Future work

Besides being a central component of our work, circular-hypervectors provide a
way to represent periodic information that has not been available in the HDC
literature thus far. Consider, for example, the seasons of the year, clearly
there is a periodic relationship between them. Several other time-related
examples can be listed such as hours of a day or days of a week, as well as
other angular data such as directions, geolocation or color spaces. Whether
this can be used to improve data representation in HDC, for instance in
machine learning applications, is a promising direction of future work.

Our method can utilize the work by Schmuck et al. (Schmuck et al., 2019) that
shows how HDC accelerators can optimize server lookup (inference in HDC) to a
single clock-cycle. Realizing an implementation of the HD hashing algorithm in
special hardware is future work.

##  7\. Conclusion

We propose Hyperdimensional (HD) hashing—a novel algorithm based on
Hyperdimensional Computing (HDC) which allows dynamic scaling of the hash
table with minimal rehashing, a problem found in some of the most popular web
applications. Through an emulation framework, we compare our method with
consistent and rendezvous hashing and the experimental results show that HD
hashing is the only approach that guarantees both efficiency and robustness.
HD hashing scales similar to consistent hashing, while both are significantly
more efficient than rendezvous hashing. Consistent hashing suffers from more
than 20% mismatches with a realistic level of memory errors, which are common
in large-scale cloud systems, while HD hashing remains unaffected. This
superior level of tolerance to bit errors reduces the chance of critical
failures in load balancing and web caching systems, among others.

## Acknowledgment

This work was supported in part by a UCI Seed grant for Artificial
Intelligence Research for Precision Health.

## References

  * (1)
  * Al-Dhuraibi et al. (2017) Yahya Al-Dhuraibi et al. 2017\.  Elasticity in cloud computing: state of the art and research challenges.  _IEEE Transactions on Services Computing_ 11, 2 (2017), 430–447.
  * DeCandia et al. (2007) Giuseppe DeCandia et al. 2007\.  Dynamo: Amazon’s highly available key-value store.  _ACM SIGOPS Operating Systems Review_ 41, 6 (2007), 205–220.
  * Eisenbud et al. (2016) Daniel E Eisenbud et al. 2016\.  Maglev: A fast and reliable software network load balancer. In _USENIX Symposium on Networked Systems Design and Implementation (NSDI)_. 523–535.
  * Greenwood and Nikulin (1996) Priscilla E Greenwood and Michael S Nikulin. 1996.  _A guide to chi-squared testing_. Vol. 280.  John Wiley & Sons.
  * Hwang et al. (2012) Andy A Hwang et al. 2012\.  Cosmic rays don’t strike twice: understanding the nature of DRAM errors and the implications for system design.  _ACM SIGPLAN Notices_ 47, 4 (2012), 111–122.
  * Ibe et al. (2010) Eishi Ibe et al. 2010\.  Impact of scaling on neutron-induced soft error in SRAMs from a 250 nm to a 22 nm design rule.  _IEEE Transactions on Electron Devices_ 57, 7 (2010), 1527–1538.
  * Imani et al. (2017a) Mohsen Imani et al. 2017a.  Ultra-efficient processing in-memory for data intensive applications. In _Design Automation Conference (DAC)_. IEEE, 1–6.
  * Imani et al. (2017b) Mohsen Imani et al. 2017b.  Voicehd: Hyperdimensional computing for efficient speech recognition. In _International Conference on Rebooting Computing (ICRC)_. IEEE, 1–8.
  * Kanerva (2009) Pentti Kanerva. 2009\.  Hyperdimensional computing: An introduction to computing in distributed representation with high-dimensional random vectors.  _Cognitive computation_ 1, 2 (2009), 139–159.
  * Karger et al. (1997) David Karger et al. 1997\.  Consistent hashing and random trees: Distributed caching protocols for relieving hot spots on the world wide web. In _ACM Symposium on Theory of Computing (STOC)_. 654–663.
  * Li et al. (2016) Haitong Li et al. 2016\.  Hyperdimensional computing with 3D VRRAM in-memory kernels: Device-architecture co-design for energy-efficient, error-resilient language recognition. In _International Electron Devices Meeting (IEDM)_. IEEE, 16–1.
  * Manabat et al. (2019) Alec Xavier Manabat et al. 2019\.  Performance analysis of hyperdimensional computing for character recognition. In _International Symposium on Multimedia and Communication Technology (ISMAC)_. IEEE, 1–5.
  * Mirrokni et al. (2018) Vahab Mirrokni et al. 2018\.  Consistent hashing with bounded loads. In _Symposium on Discrete Algorithms (SIAM)_. SIAM, 587–604.
  * Najafabadi et al. (2016) Fateme Rasti Najafabadi et al. 2016\.  Hyperdimensional computing for text classification. In _Design, Automation Test in Europe Conference Exhibition (DATE), University Booth_. 1–1.
  * Nygren et al. (2010) Erik Nygren et al. 2010\.  The akamai network: a platform for high-performance internet applications.  _ACM SIGOPS Operating Systems Review_ 44, 3 (2010), 2–19.
  * Rahimi et al. (2016) Abbas Rahimi et al. 2016\.  Hyperdimensional biosignal processing: A case study for EMG-based hand gesture recognition. In _International Conference on Rebooting Computing (ICRC)_. IEEE, 1–8.
  * Rahimi et al. (2017) Abbas Rahimi et al. 2017\.  High-dimensional computing as a nanoscalable paradigm.  _Transactions on Circuits and Systems I: Regular Papers_ 64, 9 (2017), 2508–2521.
  * Schmuck et al. (2019) Manuel Schmuck et al. 2019\.  Hardware optimizations of dense binary hyperdimensional computing: Rematerialization of hypervectors, binarized bundling, and combinational associative memory.  _Journal on Emerging Technologies in Computing Systems (JETC)_ 15, 4 (2019), 1–25.
  * Schroeder et al. (2009) Bianca Schroeder et al. 2009\.  DRAM errors in the wild: a large-scale field study.  _ACM SIGMETRICS Performance Evaluation Review (PER)_ 37, 1 (2009), 193–204.
  * Shen et al. (2006) Haiying Shen et al. 2006\.  Cycloid: A constant-degree and lookup-efficient P2P overlay network.  _Performance Evaluation_ 63, 3 (2006), 195–216.
  * Sridharan and Liberty (2012) Vilas Sridharan and Dean Liberty. 2012.  A study of DRAM failures in the field. In _International Conference on High Performance Computing, Networking, Storage and Analysis (SC)_. IEEE, 1–11.
  * Stoica et al. (2003) Ion Stoica et al. 2003\.  Chord: a scalable peer-to-peer lookup protocol for internet applications.  _IEEE/ACM Transactions on Networking_ 11, 1 (2003), 17–32.
  * Thaler and Ravishankar (1998) David G Thaler and Chinya V Ravishankar. 1998.  Using name-based mappings to increase hit rates.  _IEEE/ACM Transactions on Networking_ 6, 1 (1998), 1–14.
  * Wang and Ravishankar (2009) Wei Wang and Chinya V Ravishankar. 2009.  Hash-based virtual hierarchies for scalable location service in mobile ad-hoc networks.  _Mobile Networks and Applications_ 14, 5 (2009), 625–637.
  * Wu et al. (2018) Tony F Wu et al. 2018\.  Brain-inspired computing exploiting carbon nanotube FETs and resistive RAM: Hyperdimensional computing case study. In _International Solid-State Circuits Conference (ISSCC)_. IEEE, 492–494.