p^{\prime}(\epsilon):=\operatorname{ess\,sup}\sup_{k_{m}\in\mathbb{Z},k_{m}-S^{\prime}(\epsilon,k)\geq
g_{\epsilon}(S^{\prime}(\epsilon,k))}\mathbb{P}_{t}\left\\{\left|\det\left(\begin{bmatrix}\mathbf{C}e^{-(k_{1}I+t_{k_{1}})\mathbf{A_{c}}}\\\
\vdots\\\ \mathbf{C}e^{-(k_{m-1}I+t_{k_{m-1}})\mathbf{A_{c}}}\\\
\mathbf{C}e^{-(k_{m}I+t)\mathbf{A_{c}}}\end{bmatrix}\right)\right|<\epsilon^{2}\prod_{1\leq
i\leq
m}e^{-k_{i}I\cdot\lambda_{i}}|\mathcal{F}_{S^{\prime}(\epsilon,k)}\right\\}.$
(159)

Here, given $\mathcal{F}_{S^{\prime}(\epsilon,k)}$, $k_{1},\cdots,k_{m-1}$,
$t_{k_{1}},\cdots,t_{k_{m-1}}$, $S^{\prime}(\epsilon,k)$ are all fixed, we
took the supremum over $k_{m}$ such that $k_{m}-S^{\prime}(\epsilon,k)\geq
g_{\epsilon}(S^{\prime}(\epsilon,k))$, and $t$ is a uniform random variable on
$[0,T]$ which we computed the probability over.

Since $k_{m}\geq
S^{\prime}(\epsilon,k)+g_{\epsilon}(S^{\prime}(\epsilon,k))\geq
k_{m-1}+g_{\epsilon}(k_{m-1})$, and by (158), (b) implies
$cof_{m,m}\left(\begin{bmatrix}\mathbf{C}e^{-(k_{1}I+t_{k_{1}})\mathbf{A_{c}}}\\\
\vdots\\\ \mathbf{C}e^{-(k_{m}I+t_{k_{m}})\mathbf{A_{c}}}\\\
\end{bmatrix}\right)\geq\epsilon\prod_{1\leq i\leq
m-1}e^{-k_{i}I\cdot\lambda_{i}}$, by Lemma 16 we have
$\lim_{\epsilon\downarrow 0}p^{\prime}(\epsilon)=0$.

Denote $S^{\prime\prime}(\epsilon,k):=\lceil
S^{\prime}(\epsilon,k)+g_{\epsilon}(S^{\prime}(\epsilon,k))\rceil$. From (ii)
of Lemma 16 we know $g_{\epsilon}(k)\lesssim 1+\log(k+1)$ for all
$\epsilon>0$. Therefore, by (c) and Lemma 5 we have

$\displaystyle\lim_{\epsilon\downarrow
0}\exp\limsup_{s\rightarrow\infty}\sup_{k\in\mathbb{Z}^{+}}\frac{1}{s}\log\mathbb{P}\\{S^{\prime\prime}(\epsilon,k)-k=s\\}\leq
p_{e}.$ (160)

Denote a stopping time

$\displaystyle S^{\prime\prime\prime}(\epsilon,k)$
$\displaystyle:=\inf\left\\{n\geq S^{\prime\prime}(\epsilon):\beta[n]=1\mbox{
and
}\left|\det\left(\begin{bmatrix}\mathbf{C}e^{-(k_{1}I+t_{k_{1}})\mathbf{A_{c}}}\\\
\vdots\\\ \mathbf{C}e^{-(k_{m-1}I+t_{k_{m-1}})\mathbf{A_{c}}}\\\
\mathbf{C}e^{-(nI+t_{n})\mathbf{A_{c}}}\\\
\end{bmatrix}\right)\right|\geq\epsilon^{2}e^{-nI\cdot\lambda_{m}}\prod_{1\leq
i\leq m-1}e^{-k_{i}I\cdot\lambda_{i}}\right\\}.$ (161)

Since $\beta[n]$ and $t_{n}$ are independent processes, for
$S^{\prime\prime\prime}(\epsilon,k)=n$ to hold, $\beta[n]=1$ and the
determinant of (161) has to be large enough. By (159), we already know the
probability for the determinant not being large enough is upper bounded by
$p^{\prime}(\epsilon)$. Therefore, given that
$S^{\prime\prime\prime}(\epsilon,k)\geq n$, the probability that
$S^{\prime\prime\prime}(\epsilon,k)\neq n$ is upper bounded by
$(p_{e}+(1-p_{e})p^{\prime}(\epsilon))$ — (erasure) or (not erased but small
determinant). Thus, for all $s\in\mathbb{Z}^{+}$, we have

$\displaystyle\operatorname{ess\,sup}\mathbb{P}\\{S^{\prime\prime\prime}(\epsilon,k)-S^{\prime\prime}(\epsilon,k)\geq
s|\mathcal{F}_{S^{\prime\prime}(\epsilon,k)}\\}\leq\left(p_{e}+\left(1-p_{e}\right)p^{\prime}(\epsilon)\right)^{s}.$

Since we know $\lim_{\epsilon\downarrow 0}p^{\prime}(\epsilon)=0$, we have

$\displaystyle\lim_{\epsilon\downarrow
0}\exp\limsup_{s\rightarrow\infty}\operatorname{ess\,sup}\frac{1}{s}\log\mathbb{P}\\{S^{\prime\prime\prime}(\epsilon,k)-S^{\prime\prime}(\epsilon,k)=s|\mathcal{F}_{S^{\prime\prime}(\epsilon,k)}\\}\leq
p_{e}.$ (162)

By applying Lemma 6 to (160) and (162), we can conclude that

$\displaystyle\lim_{\epsilon\downarrow
0}\exp\limsup_{s\rightarrow\infty}\sup_{k\in\mathbb{Z}^{+}}\frac{1}{s}\log\mathbb{P}\\{S^{\prime\prime\prime}(\epsilon,k)-k=s\\}\leq
p_{e}.$

Therefore, if we denote
$S(\epsilon,k):=S^{\prime\prime\prime}(\epsilon^{\frac{1}{2}},k)$,
$S(\epsilon,k)$ satisfies all the conditions of the claim. ∎

Before we prove Lemma 2, we will first prove the following lemma which allows
to merge two Jordan blocks associated with the same eigenvalue into one Jordan
block.

###### Lemma 18

Let $\mathbf{A}$ be a Jordan block matrix with an eigenvalue
$\lambda\in\mathbb{C}$ and a size $m\in\mathbb{N}$, i.e.
$\mathbf{A}=\begin{bmatrix}\lambda&1&\cdots&0\\\ 0&\lambda&\cdots&0\\\
\vdots&\vdots&\ddots&\vdots\\\ 0&0&\cdots&\lambda\\\ \end{bmatrix}$.
$\mathbf{C}$ and $\mathbf{C^{\prime}}$ are $1\times m$ matrices such that

$\displaystyle\mathbf{C}=\begin{bmatrix}c_{1}&c_{2}&\cdots&c_{m}\end{bmatrix}$
$\displaystyle\mathbf{C^{\prime}}=\begin{bmatrix}c^{\prime}_{1}&c^{\prime}_{2}&\cdots&c^{\prime}_{m}\end{bmatrix}$
(163)

where $c_{i},c^{\prime}_{i}\in\mathbb{C}$ and $c_{1}\neq 0$.
For all $k\in\mathbb{R}$ and $m\times 1$ matrices
$\mathbf{X}=\begin{bmatrix}x_{1}\\\ x_{2}\\\ \vdots\\\ x_{m}\end{bmatrix}$ and
$\mathbf{X^{\prime}}=\begin{bmatrix}x^{\prime}_{1}\\\ x^{\prime}_{2}\\\
\vdots\\\ x^{\prime}_{m}\end{bmatrix}$, there exists $\mathbf{T}$ such that

$\displaystyle(i)\mathbf{T}\mbox{ is an upper triangular matrix.}$
$\displaystyle(ii)\mathbf{C}e^{k\mathbf{A}}\mathbf{X}+\mathbf{C^{\prime}}e^{k\mathbf{A}}\mathbf{X^{\prime}}=\mathbf{C}e^{k\mathbf{A}}\left(\mathbf{X}+\mathbf{T}\mathbf{X^{\prime}}\right)$

Moreover, the diagonal elements of $\mathbf{T}$ are
$\frac{c_{1}^{\prime}}{c_{1}}$.

###### Proof:

The proof is an induction on $m$, the size of the $\mathbf{A}$ matrix. The
lemma is trivial when $m=1$. Thus, we can assume the lemma is true for $m$ as
an induction hypothesis, and consider $m+1$ as the dimension of $\mathbf{A}$.

$\displaystyle\mathbf{C}e^{k\mathbf{A}}\mathbf{X}+\mathbf{C^{\prime}}e^{k\mathbf{A}}\mathbf{X^{\prime}}$
$\displaystyle=\mathbf{C}\begin{bmatrix}e^{k\lambda}&\frac{k}{1!}e^{k\lambda}&\cdots&\frac{k^{m}}{m!}e^{k\lambda}\\\
0&e^{k\lambda}&\cdots&\frac{k^{m-1}}{(m-1)!}e^{k\lambda}\\\
\vdots&\vdots&\ddots&\vdots\\\ 0&0&\cdots&e^{k\lambda}\\\
\end{bmatrix}\mathbf{X}+\mathbf{C^{\prime}}\begin{bmatrix}e^{k\lambda}&\frac{k}{1!}e^{k\lambda}&\cdots&\frac{k^{m}}{m!}e^{k\lambda}\\\
0&e^{k\lambda}&\cdots&\frac{k^{m-1}}{(m-1)!}e^{k\lambda}\\\
\vdots&\vdots&\ddots&\vdots\\\ 0&0&\cdots&e^{k\lambda}\\\
\end{bmatrix}\mathbf{X^{\prime}}$
$\displaystyle=\mathbf{C}\begin{bmatrix}e^{k\lambda}&\frac{k}{1!}e^{k\lambda}&\cdots&\frac{k^{m}}{m!}e^{k\lambda}\\\
0&e^{k\lambda}&\cdots&\frac{k^{m-1}}{(m-1)!}e^{k\lambda}\\\
\vdots&\vdots&\ddots&\vdots\\\ 0&0&\cdots&e^{k\lambda}\\\
\end{bmatrix}\mathbf{X}$
$\displaystyle+\left(\frac{c_{1}^{\prime}}{c_{1}}\mathbf{C}+\begin{bmatrix}0&c_{2}^{\prime}-\frac{c_{1}^{\prime}}{c_{1}}c_{2}&\cdots&c_{m+1}^{\prime}-\frac{c_{1}^{\prime}}{c_{1}}c_{m+1}\end{bmatrix}\right)\begin{bmatrix}e^{k\lambda}&\frac{k}{1!}e^{k\lambda}&\cdots&\frac{k^{m}}{m!}e^{k\lambda}\\\
0&e^{k\lambda}&\cdots&\frac{k^{m-1}}{(m-1)!}e^{k\lambda}\\\
\vdots&\vdots&\ddots&\vdots\\\ 0&0&\cdots&e^{k\lambda}\\\
\end{bmatrix}\mathbf{X^{\prime}}$
$\displaystyle=\mathbf{C}\begin{bmatrix}e^{k\lambda}&\frac{k}{1!}e^{k\lambda}&\cdots&\frac{k^{m}}{m!}e^{k\lambda}\\\
0&e^{k\lambda}&\cdots&\frac{k^{m-1}}{(m-1)!}e^{k\lambda}\\\
\vdots&\vdots&\ddots&\vdots\\\ 0&0&\cdots&e^{k\lambda}\\\
\end{bmatrix}\left(\mathbf{X}+\frac{c_{1}^{\prime}}{c_{1}}\mathbf{X^{\prime}}\right)$
$\displaystyle+\begin{bmatrix}0&c_{2}^{\prime}-\frac{c_{1}^{\prime}}{c_{1}}c_{2}&\cdots&c_{m}^{\prime}-\frac{c_{1}^{\prime}}{c_{1}}c_{m}\end{bmatrix}\begin{bmatrix}e^{k\lambda}&\frac{k}{1!}e^{k\lambda}&\cdots&\frac{k^{m}}{m!}e^{k\lambda}\\\
0&e^{k\lambda}&\cdots&\frac{k^{m-1}}{(m-1)!}e^{k\lambda}\\\
\vdots&\vdots&\ddots&\vdots\\\ 0&0&\cdots&e^{k\lambda}\\\
\end{bmatrix}\mathbf{X^{\prime}}$
$\displaystyle=\mathbf{C}\begin{bmatrix}e^{k\lambda}&\frac{k}{1!}e^{k\lambda}&\cdots&\frac{k^{m}}{m!}e^{k\lambda}\\\
0&e^{k\lambda}&\cdots&\frac{k^{m-1}}{(m-1)!}e^{k\lambda}\\\
\vdots&\vdots&\ddots&\vdots\\\ 0&0&\cdots&e^{k\lambda}\\\
\end{bmatrix}\left(\begin{bmatrix}0\\\ 0\\\ \vdots\\\
x_{m+1}+\frac{c_{1}^{\prime}}{c_{1}}x^{\prime}_{m+1}\end{bmatrix}+\begin{bmatrix}x_{1}+\frac{c_{1}^{\prime}}{c_{1}}x^{\prime}_{1}\\\
x_{2}+\frac{c_{1}^{\prime}}{c_{1}}x^{\prime}_{2}\\\ \vdots\\\
0\end{bmatrix}\right)$
$\displaystyle+\begin{bmatrix}c_{2}^{\prime}-\frac{c_{1}^{\prime}}{c_{1}}c_{2}&c_{3}^{\prime}-\frac{c_{1}^{\prime}}{c_{1}}c_{3}&\cdots&c_{m+1}^{\prime}-\frac{c_{1}^{\prime}}{c_{1}}c_{m+1}\end{bmatrix}\begin{bmatrix}e^{k\lambda}&\frac{k}{1!}e^{k\lambda}&\cdots&\frac{k^{m-1}}{(m-1)!}e^{k\lambda}\\\
0&e^{k\lambda}&\cdots&\frac{k^{m-2}}{(m-2)!}e^{k\lambda}\\\
\vdots&\vdots&\ddots&\vdots\\\ 0&0&\cdots&e^{k\lambda}\\\
\end{bmatrix}\begin{bmatrix}x_{2}^{\prime}\\\ x_{3}^{\prime}\\\ \vdots\\\
x_{m+1}^{\prime}\\\ \end{bmatrix}$
$\displaystyle=\mathbf{C}\begin{bmatrix}e^{k\lambda}&\frac{k}{1!}e^{k\lambda}&\cdots&\frac{k^{m}}{m!}e^{k\lambda}\\\
0&e^{k\lambda}&\cdots&\frac{k^{m-1}}{(m-1)!}e^{k\lambda}\\\
\vdots&\vdots&\ddots&\vdots\\\ 0&0&\cdots&e^{k\lambda}\\\
\end{bmatrix}\begin{bmatrix}0\\\ 0\\\ \vdots\\\
x_{m+1}+\frac{c_{1}^{\prime}}{c_{1}}x^{\prime}_{m+1}\end{bmatrix}$
$\displaystyle+\begin{bmatrix}c_{1}&c_{2}&\cdots&c_{m}\end{bmatrix}\begin{bmatrix}e^{k\lambda}&\frac{k}{1!}e^{k\lambda}&\cdots&\frac{k^{m-1}}{(m-1)!}e^{k\lambda}\\\
0&e^{k\lambda}&\cdots&\frac{k^{m-2}}{(m-2)!}e^{k\lambda}\\\
\vdots&\vdots&\ddots&\vdots\\\ 0&0&\cdots&e^{k\lambda}\\\
\end{bmatrix}\begin{bmatrix}x_{1}+\frac{c_{1}^{\prime}}{c_{1}}x^{\prime}_{1}\\\
x_{2}+\frac{c_{1}^{\prime}}{c_{1}}x^{\prime}_{2}\\\ \vdots\\\
x_{m}+\frac{c_{1}^{\prime}}{c_{1}}x^{\prime}_{m}\end{bmatrix}$
$\displaystyle+\begin{bmatrix}c_{2}^{\prime}-\frac{c_{1}^{\prime}}{c_{1}}c_{2}&c_{3}^{\prime}-\frac{c_{1}^{\prime}}{c_{1}}c_{3}&\cdots&c_{m+1}^{\prime}-\frac{c_{1}^{\prime}}{c_{1}}c_{m+1}\end{bmatrix}\begin{bmatrix}e^{k\lambda}&\frac{k}{1!}e^{k\lambda}&\frac{k}{2!}e^{k\lambda}&\cdots&\frac{k^{m-1}}{(m-1)!}e^{k\lambda}\\\
0&e^{k\lambda}&\frac{k}{1!}e^{k\lambda}&\cdots&\frac{k^{m-2}}{(m-2)!}e^{k\lambda}\\\
\vdots&\vdots&\vdots&\ddots&\vdots\\\ 0&0&0&\cdots&e^{k\lambda}\\\
\end{bmatrix}\begin{bmatrix}x_{2}^{\prime}\\\ x_{3}^{\prime}\\\ \vdots\\\
x_{m+1}^{\prime}\\\ \end{bmatrix}$
$\displaystyle=\mathbf{C}\begin{bmatrix}e^{k\lambda}&\frac{k}{1!}e^{k\lambda}&\cdots&\frac{k^{m}}{m!}e^{k\lambda}\\\
0&e^{k\lambda}&\cdots&\frac{k^{m-1}}{(m-1)!}e^{k\lambda}\\\
\vdots&\vdots&\ddots&\vdots\\\ 0&0&\cdots&e^{k\lambda}\\\
\end{bmatrix}\begin{bmatrix}0\\\ 0\\\ \vdots\\\
x_{m+1}+\frac{c_{1}^{\prime}}{c_{1}}x^{\prime}_{m+1}\end{bmatrix}$
$\displaystyle+\begin{bmatrix}c_{1}&c_{2}&\cdots&c_{m}\end{bmatrix}\begin{bmatrix}e^{k\lambda}&\frac{k}{1!}e^{k\lambda}&\cdots&\frac{k^{m-1}}{(m-1)!}e^{k\lambda}\\\
0&e^{k\lambda}&\cdots&\frac{k^{m-2}}{(m-2)!}e^{k\lambda}\\\
\vdots&\vdots&\ddots&\vdots\\\ 0&0&\cdots&e^{k\lambda}\\\
\end{bmatrix}\left(\begin{bmatrix}x_{1}+\frac{c_{1}^{\prime}}{c_{1}}x^{\prime}_{1}\\\
x_{2}+\frac{c_{1}^{\prime}}{c_{1}}x^{\prime}_{2}\\\ \vdots\\\
x_{m}+\frac{c_{1}^{\prime}}{c_{1}}x^{\prime}_{m}\end{bmatrix}+\begin{bmatrix}t^{\prime}_{1,1}&t^{\prime}_{1,2}&\cdots&t^{\prime}_{1,m}\\\
0&t^{\prime}_{2,2}&\cdots&t^{\prime}_{2,m}\\\ \vdots&\vdots&\ddots&\vdots\\\
0&0&\cdots&t^{\prime}_{m,m}\end{bmatrix}\begin{bmatrix}x_{2}^{\prime}\\\
x_{3}^{\prime}\\\ \vdots\\\ x_{m+1}^{\prime}\\\ \end{bmatrix}\right)$ (164)
$\displaystyle=\mathbf{C}\begin{bmatrix}e^{k\lambda}&\frac{k}{1!}e^{k\lambda}&\cdots&\frac{k^{m}}{m!}e^{k\lambda}\\\
0&e^{k\lambda}&\cdots&\frac{k^{m-1}}{(m-1)!}e^{k\lambda}\\\
\vdots&\vdots&\ddots&\vdots\\\ 0&0&\cdots&e^{k\lambda}\\\
\end{bmatrix}\left(\begin{bmatrix}0\\\ 0\\\ \vdots\\\
x_{m+1}+\frac{c_{1}^{\prime}}{c_{1}}x^{\prime}_{m+1}\end{bmatrix}+\begin{bmatrix}x_{1}+\frac{c_{1}^{\prime}}{c_{1}}x^{\prime}_{1}\\\
x_{2}+\frac{c_{1}^{\prime}}{c_{1}}x^{\prime}_{2}\\\ \vdots\\\
0\end{bmatrix}+\begin{bmatrix}t^{\prime}_{1,1}&t^{\prime}_{1,2}&\cdots&t^{\prime}_{1,m}\\\
0&t^{\prime}_{2,2}&\cdots&t^{\prime}_{2,m}\\\ \vdots&\vdots&\ddots&\vdots\\\
0&0&\cdots&0\end{bmatrix}\begin{bmatrix}x_{2}^{\prime}\\\ x_{3}^{\prime}\\\
\vdots\\\ x_{m+1}^{\prime}\\\ \end{bmatrix}\right)$
$\displaystyle=\mathbf{C}\begin{bmatrix}e^{k\lambda}&\frac{k}{1!}e^{k\lambda}&\cdots&\frac{k^{m}}{m!}e^{k\lambda}\\\
0&e^{k\lambda}&\cdots&\frac{k^{m-1}}{(m-1)!}e^{k\lambda}\\\
\vdots&\vdots&\ddots&\vdots\\\ 0&0&\cdots&\frac{k}{1!}e^{k\lambda}\\\
0&0&\cdots&e^{k\lambda}\\\ \end{bmatrix}\left(\begin{bmatrix}x_{1}\\\ x_{2}\\\
\vdots\\\ x_{m+1}\\\
\end{bmatrix}+\begin{bmatrix}\frac{c^{\prime}_{1}}{c_{1}}&t^{\prime}_{1,1}&\cdots&t^{\prime}_{1,m}\\\
0&\frac{c^{\prime}_{1}}{c_{1}}&\cdots&t^{\prime}_{2,m}\\\
\vdots&\vdots&\ddots&\vdots\\\
0&0&\cdots&\frac{c^{\prime}_{1}}{c_{1}}\end{bmatrix}\begin{bmatrix}x^{\prime}_{1}\\\
x^{\prime}_{2}\\\ \vdots\\\ x^{\prime}_{m+1}\\\ \end{bmatrix}\right)$

where (164) follows from the induction hypothesis. The lemma is true. ∎

Now, we are ready to prove Lemma 2.

###### Proof:

The proof is an induction on $m$, the size of matrix $\mathbf{A_{c}}$. Remind
that here $\mathbf{C}$ can be a general matrix, so we use the definitions of
$\mathbf{A_{c}},\mathbf{C}$ given as (67), (68).

(i) When $m=1$,

In this case, the system is scalar, and the lemma is trivially true. A
rigorous proof goes as follows: Since $(\mathbf{A_{c}},\mathbf{C})$ is
observable, we can find a $1\times l$ matrix $\mathbf{L}$ such that
$\mathbf{L}\mathbf{C}$ is not zero. Then,
$(\mathbf{A_{c}},\mathbf{L}\mathbf{C})$ is observable, and the lemma is
reduced to Lemma 17.

(ii) We will assume that the lemma holds for $(m-1)$-dimensional systems as an
induction hypothesis, and prove the lemma holds for $m$.

The proof goes in three steps. First, we reduce the system to reducing a
system with scalar observations to apply Lemma 17. Then, we estimate one of
the states, and subtract the estimation from the system — this procedure is
known as successive decoding in information theory. Now, the system reduces to
the $(m-1)$-dimensional one, so we apply the induction hypothesis.

For this, we define $\mathbf{x}:=\begin{bmatrix}\mathbf{x_{1,1}}\\\
\mathbf{x_{1,2}}\\\ \vdots\\\ \mathbf{x_{\mu,\nu_{\mu}}}\end{bmatrix}$ where
$\mathbf{x_{i,j}}$ are $m_{i,j}\times 1$ vectors, and
$(\mathbf{x_{1,\nu_{1}}})_{m_{1,\nu_{1}}}$ as the $m_{1,\nu_{1}}$th element of
$\mathbf{x_{1,\nu_{1}}}$. We also define $(\mathbf{x})_{k}$ as the $k$th
element of a vector $\mathbf{x}$ in general. Here, $\mathbf{x}$ can be thought
as the states of the system. We first decode
$(\mathbf{x_{1,\nu_{1}}})_{m_{1,\nu_{1}}}$, and decode the remaining elements
in $\mathbf{x}$.

$\bullet$ Reduction to Systems with Scalar Observations: By Lemma 17, we
already know that the lemma is true for systems with scalar observations.
Therefore, we will reduce the general systems with vector observations to
system with scalar observations.

###### Claim 2

There exist
$\mathbf{L},\mathbf{C^{\prime}},\mathbf{A^{\prime}},\mathbf{x^{\prime}}$ that
satisfies the following conditions.
(i) $\mathbf{L}$ is a $1\times l$ row vector.
(ii) $\mathbf{A^{\prime}}$ is a $m^{\prime}\times m^{\prime}$ square matrix
given in a Jordan form. The eigenvalues of $\mathbf{A^{\prime}}$ belong to
$\\{\lambda_{1}+j\omega_{1},\cdots,\lambda_{\mu}+j\omega_{\mu}\\}$ which is
the set of the eigenvalues of $\mathbf{A}$. The first Jordan block of
$\mathbf{A^{\prime}}$ is equal to $\mathbf{A_{1,\nu_{1}}}$.
(iii) $\mathbf{C^{\prime}}$ is a $l\times m^{\prime}$ matrix and
$(\mathbf{A^{\prime}},\mathbf{L}\mathbf{C^{\prime}})$ is observable.
(iv) $\mathbf{x^{\prime}}$ is a $m^{\prime}\times l$ column vector.
$(\mathbf{x^{\prime}})_{m_{1,\nu_{1}}}=(\mathbf{x_{1,\nu_{1}}})_{m_{1},\nu_{1}}$.
(v)
$\mathbf{L}\mathbf{C}e^{-k\mathbf{A_{c}}}\mathbf{x}=\mathbf{L}\mathbf{C^{\prime}}e^{-k\mathbf{A^{\prime}}}\mathbf{x^{\prime}}$.

What this claim implies is the following. By multiplying the matrix
$\mathbf{L}$ to the vector observations, we can reduce the vector observations
to the scalar observations. However, the resulting system may not be
observable any more. Therefore, we will carefully design $\mathbf{L}$ matrix
and reduced system matrices $\mathbf{A^{\prime}}$, $\mathbf{C^{\prime}}$, so
that the system remains observable even with a scalar observation and the
information about $(\mathbf{x_{1,\nu_{1}}})_{m_{1,\nu_{1}}}$ remains intact.

###### Proof:

Since the first columns of
$\mathbf{C_{1,1}},\mathbf{C_{1,2}},\cdots,\mathbf{C_{1,\nu_{1}}}$ are linearly
independent, there exists a $1\times l$ matrix $\mathbf{L}$ such that the
first elements of
$\mathbf{L}\mathbf{C_{1,1}},\mathbf{L}\mathbf{C_{1,2}},\cdots,\mathbf{L}\mathbf{C_{1,\nu_{1}-1}}$
are zeros and the first element of $\mathbf{L}\mathbf{C_{1,\nu_{1}}}$ is non-
zero. Then, we can observe that

$\displaystyle\mathbf{L}\mathbf{C}e^{-k\mathbf{A_{c}}}\mathbf{x}$
$\displaystyle=\mathbf{L}\begin{bmatrix}\mathbf{C_{1,1}}&\cdots&\mathbf{C_{\mu,\nu_{\mu}}}\end{bmatrix}\begin{bmatrix}e^{-k\mathbf{A_{1,1}}}&\cdots&0\\\
\vdots&\ddots&\vdots\\\
0&\cdots&e^{-k\mathbf{A_{\mu,\nu_{\mu}}}}\end{bmatrix}\begin{bmatrix}\mathbf{x_{1,1}}\\\
\vdots\\\ \mathbf{x_{\mu,\nu_{\mu}}}\end{bmatrix}$
$\displaystyle=\mathbf{L}\mathbf{C_{1,1}}e^{-k\mathbf{A_{1,1}}}\mathbf{x_{1,1}}+\mathbf{L}\mathbf{C_{1,2}}e^{-k\mathbf{A_{1,2}}}\mathbf{x_{1,2}}+\cdots+\mathbf{L}\mathbf{C_{\mu,\nu_{\mu}}}e^{-k\mathbf{A_{\mu,\nu_{\mu}}}}\mathbf{x_{\mu,\nu_{\mu}}}$
(165)

Remind that the Jordan blocks $\mathbf{A_{i,1}},\cdots,\mathbf{A_{i,\nu_{i}}}$
correspond to the same eigenvalue. We will merge these Jordan blocks into one
Jordan block. However, since the size of Jordan blocks
$\mathbf{A_{i,1}},\cdots,\mathbf{A_{i,\nu_{i}}}$ are distinct, we will extend
the small Jordan block to the size of the largest one by adding zero elements.
Let the dimension of $\mathbf{A_{i,\bar{\nu}_{i}}}$ be the largest among
$\mathbf{A_{i,1}},\cdots,\mathbf{A_{i,\nu_{i}}}$, and $m_{i,\bar{\nu}_{i}}$ be
the corresponding dimension. Then, we define $\mathbf{\bar{C}_{i,j}}$ as a
matrix where the first $m_{i,\bar{\nu}_{i}}-m_{i,j}$ vectors are all zeros,
and the remaining vectors are the same as those of $\mathbf{C_{i,j}}$.
$\mathbf{\bar{A}_{i,j}}$ is defined as the same matrix as
$\mathbf{{A}_{i,\bar{\nu}_{i}}}$. $\mathbf{\bar{x}_{i,j}}$ is defined as a
column vector whose first $m_{i,\bar{\nu}_{i}}-m_{i,j}$ elements are all
zeros, and the remaining elements are those of $\mathbf{x_{i,j}}$.

Then, by the construction, we know

$\displaystyle\eqref{eqn:lem:idontknow}=\mathbf{L}\mathbf{\bar{C}_{1,1}}e^{-k\mathbf{\bar{A}_{1,1}}}\mathbf{\bar{x}_{1,1}}+\mathbf{L}\mathbf{\bar{C}_{1,2}}e^{-k\mathbf{\bar{A}_{1,2}}}\mathbf{\bar{x}_{1,2}}+\cdots+\mathbf{L}\mathbf{\bar{C}_{\mu,\nu_{\mu}}}e^{-k\mathbf{\bar{A}_{\mu,\nu_{\mu}}}}\mathbf{\bar{x}_{\mu,\nu_{\mu}}}.$
(166)

Furthermore, $\mathbf{A_{1,\nu_{1}}}=\mathbf{\bar{A}_{1,\nu_{1}}}$,
$\mathbf{C_{1,\nu_{1}}}=\mathbf{\bar{C}_{1,\nu_{1}}}$,
$\mathbf{x_{1,\nu_{1}}}=\mathbf{\bar{x}_{1,\nu_{1}}}$. The first elements of
$\mathbf{L}\mathbf{\mathbf{C_{1,1}}},\mathbf{L}\mathbf{\mathbf{C_{1,2}}},\cdots,\mathbf{L}\mathbf{C_{1,\nu_{1}-1}}$
are zeros and the first element of $\mathbf{L}\mathbf{C_{1,\nu_{1}}}$ is non-
zero.

Now, we get the same dimension systems
$(\mathbf{\bar{A}_{i,1}},\mathbf{L}\mathbf{\bar{C}_{i,1}})$, $\cdots$,
$(\mathbf{\bar{A}_{i,\nu_{i}}},\mathbf{L}\mathbf{\bar{C}_{i,\nu_{i}}})$.
However, none of them might be observable. Thus, we will truncate the matrices
to make sure that at least one of them is observable. Remind that since
$\mathbf{L}\mathbf{\bar{C}_{i,j}}$ is a row vector and
$\mathbf{\bar{A}_{i,j}}$ is a single Jordan block, the system is observable as
long as the first element of $\mathbf{L}\mathbf{\bar{C}_{i,j}}$ is not zero.
Thus, we will truncate the matrices until we see at least one nonzero element
among the first elements of $\mathbf{L}\mathbf{\bar{C}_{i,1}}$, $\cdots$,
$\mathbf{L}\mathbf{\bar{C}_{i,\nu_{i}}}$. Let $k_{i}$ be the smallest number
such that at least one of the $k_{i}$th elements of
$\mathbf{L}\mathbf{\bar{C}_{i,1}},\cdots,\mathbf{L}\mathbf{\bar{C}_{i,\nu_{i}}}$
becomes nonzero, and let $\mathbf{L}\mathbf{\bar{C}_{i,\nu_{i}^{\star}}}$ be
the vector that achieves the minimum.

Then, we will reduce the dimensions of
$(\mathbf{\bar{A}_{i,j}},\mathbf{L}\mathbf{\bar{C}_{i,j}})$ by truncating the
first $(k_{i}-1)$ vectors. Define $\mathbf{C_{i,j}^{\prime}}$ as a matrix
obtained by removing the first $(k_{i}-1)$ columns from
$\mathbf{\bar{C}_{i,j}}$, $\mathbf{A_{i,j}^{\prime}}$ as a matrix obtained by
removing the first $(k_{i}-1)$ rows and columns from $\mathbf{\bar{A}_{i,j}}$,
and $\mathbf{x_{i,j}^{\prime}}$ as a matrix obtained by removing the first
$(k_{i}-1)$ elements from $\mathbf{\bar{x}_{i,j}}$.

Then, by the construction, the resulting systems
$(\mathbf{A_{i,\nu_{i}^{\star}}^{\prime}},\mathbf{L}\mathbf{C_{i,\nu_{i}^{\star}}^{\prime}})$
are observable. We can also see that $\nu_{1}^{\star}=\nu_{1}$,
$\mathbf{C_{1,\nu_{1}^{\star}}^{\prime}}=\mathbf{\bar{C}_{1,\nu_{1}}}=\mathbf{C_{1,\nu_{1}}}$,
$\mathbf{A_{1,\nu_{1}^{\star}}^{\prime}}=\mathbf{\bar{A}_{1,\nu_{1}}}=\mathbf{A_{1,\nu_{1}}}$,
and
$\mathbf{x^{\prime}_{1,\nu_{1}^{\star}}}=\mathbf{\bar{x}_{1,\nu_{1}}}=\mathbf{x_{1,\nu_{1}}}$.
In words, the Jordan block $\mathbf{A_{1,\nu_{1}}}$ was not affected by the
above manipulations. Moreover, by the construction, the first elements of
$\mathbf{L}\mathbf{C^{\prime}_{1,1}},\cdots,\mathbf{L}\mathbf{C^{\prime}_{1,\nu_{1}-1}}$
are all zero.

Denote
$\mathbf{C^{\prime}}:=\begin{bmatrix}\mathbf{C^{\prime}_{1,\nu_{1}^{\star}}}&\mathbf{C^{\prime}_{2,\nu_{2}^{\star}}}&\cdots&\mathbf{C^{\prime}_{\mu,\nu_{\mu}^{\star}}}\end{bmatrix}$
and
$\mathbf{A^{\prime}}:=diag\\{\mathbf{A^{\prime}_{1,\nu_{1}^{\star}}},\mathbf{A^{\prime}_{2,\nu_{2}^{\star}}},\cdots,\mathbf{A^{\prime}_{\mu,\nu_{\mu}^{\star}}}\\}$.
Then, (165) can be written as follows:

$\displaystyle\eqref{eqn:lem:idontknow}$
$\displaystyle=\mathbf{L}\mathbf{C^{\prime}_{1,1}}e^{-k\mathbf{A^{\prime}_{1,1}}}\mathbf{x^{\prime}_{1,1}}+\mathbf{L}\mathbf{C^{\prime}_{1,2}}e^{-k\mathbf{A^{\prime}_{1,2}}}\mathbf{x^{\prime}_{1,2}}+\cdots+\mathbf{L}\mathbf{C^{\prime}_{\mu,\nu_{\mu}}}e^{-k\mathbf{A^{\prime}_{\mu,\nu_{\mu}}}}\mathbf{x^{\prime}_{\mu,\nu_{\mu}}}$
$\displaystyle=\mathbf{L}\mathbf{C^{\prime}_{1,\nu_{1}^{\star}}}e^{-k\mathbf{A^{\prime}_{1,\nu_{1}^{\star}}}}(\mathbf{x^{\prime}_{1,\nu_{1}^{\star}}}+\sum_{j\in\\{1,\cdots,\nu_{1}\\}\setminus\nu_{1}^{\star}}\mathbf{T_{1,j}}\mathbf{x_{1,j}^{\prime}})+\cdots$
$\displaystyle\quad+\mathbf{L}\mathbf{C^{\prime}_{\mu,\nu_{\mu}^{\star}}}e^{-k\mathbf{A^{\prime}_{\mu,\nu_{\mu}^{\star}}}}(\mathbf{x^{\prime}_{\mu,\nu_{\mu}^{\star}}}+\sum_{j\in\\{1,\cdots,\nu_{\mu}\\}\setminus\nu_{\mu}^{\star}}\mathbf{T_{\mu,j}}\mathbf{x_{\mu,j}^{\prime}})$
(167)
$\displaystyle=\begin{bmatrix}\mathbf{L}\mathbf{C^{\prime}_{1,\nu_{1}^{\star}}}&\cdots&\mathbf{L}\mathbf{C^{\prime}_{1,\nu_{\mu}^{\star}}}\end{bmatrix}\begin{bmatrix}e^{-k\mathbf{A^{\prime}_{1,\nu_{1}^{\star}}}}&\cdots&0\\\
\vdots&\ddots&\vdots\\\
0&\cdots&e^{-k\mathbf{A^{\prime}_{\mu,\nu_{\mu}^{\star}}}}\end{bmatrix}\underbrace{\begin{bmatrix}\mathbf{x^{\prime}_{1,\nu_{1}^{\star}}}+\sum_{j\in\\{1,\cdots,\nu_{1}\\}\setminus\nu_{1}^{\star}}\mathbf{T_{1,j}}\mathbf{x_{1,j}^{\prime}}\\\
\vdots\\\
\mathbf{x^{\prime}_{\mu,\nu_{\mu}^{\star}}}+\sum_{j\in\\{1,\cdots,\nu_{\mu}\\}\setminus\nu_{\mu}^{\star}}\mathbf{T_{\mu,j}}\mathbf{x_{\mu,j}^{\prime}}\end{bmatrix}}_{:=\mathbf{x^{\prime}}}$
$\displaystyle=\mathbf{L}\mathbf{C^{\prime}}e^{-k\mathbf{A^{\prime}}}\mathbf{x^{\prime}}$
(168)

where (167) follows from Lemma 18. Here, we can easily see that
$\mathbf{A^{\prime}}$ satisfies the condition (ii) of the claim, and
$(\mathbf{A^{\prime}},\mathbf{L}\mathbf{C^{\prime}})$ is observable since each
$(\mathbf{A_{i,\nu_{i}^{\star}}^{\prime}},\mathbf{L}\mathbf{C_{i,\nu_{i}^{\star}}^{\prime}})$
is observable.

Moreover, by Lemma 18, we know that
$\mathbf{T_{1,1}},\cdots,\mathbf{T_{1,\nu_{1}-1}}$ are upper triangular
matrices whose diagonal elements are zeros. Therefore,
$(\mathbf{x^{\prime}})_{m_{1,\nu_{1}}}=(\mathbf{x_{1,\nu_{1}}^{\prime}})_{m_{1,\nu_{1}}}=(\mathbf{x_{1,\nu_{1}}})_{m_{1,\nu_{1}}}$.
Therefore, the condition (iv) of the claim is also satisfied. ∎

$\bullet$ Decoding $(\mathbf{x_{1,\nu_{1}}})_{m_{1,\nu_{1}}}$: Now, we reduced
the system to a system with a scalar observation. Then, we can apply Lemma 17
to decode $(\mathbf{x_{1,\nu_{1}}})_{m_{1,\nu_{1}}}$.

###### Claim 3

We can find a polynomial $p^{\prime}(k)$ and a family of stopping time
$\\{S^{\prime}(\epsilon,k):k\in\mathbb{Z^{+}},\epsilon>0\\}$ such that for all
$\epsilon>0$, $k\in\mathbb{Z}^{+}$ there exist $k\leq
k_{1}<k_{2}<\cdots<k_{m^{\prime}}\leq S^{\prime}(\epsilon,k)$ and
$\mathbf{M_{1}^{\prime}}$ satisfying:
(i) $\beta[k_{i}]=1$ for $1\leq i\leq m^{\prime}$
(ii) $\mathbf{M_{1}^{\prime}}\begin{bmatrix}\mathbf{L}&0&\cdots&0\\\
0&\mathbf{L}&\cdots&0\\\ \vdots&\vdots&\ddots&\vdots\\\
0&0&\cdots&\mathbf{L}\end{bmatrix}\begin{bmatrix}\mathbf{C}e^{-(k_{1}I+t_{k_{1}})\mathbf{A}}\\\
\mathbf{C}e^{-(k_{2}I+t_{k_{2}})\mathbf{A}}\\\ \vdots\\\
\mathbf{C}e^{-(k_{m^{\prime}}I+t_{k_{m^{\prime}}})\mathbf{A}}\\\
\end{bmatrix}\mathbf{x}=(\mathbf{x_{1,\nu_{1}}})_{m_{1,\nu_{1}}}$
(iii)
$\left|\mathbf{M_{1}^{\prime}}\right|_{max}\leq\frac{p^{\prime}(S^{\prime}(\epsilon,k))}{\epsilon}e^{\lambda_{1}S^{\prime}(\epsilon,k)I}$
(iv) $\lim_{\epsilon\downarrow
0}\exp\limsup_{s\rightarrow\infty}\sup_{k\in\mathbb{Z^{+}}}\frac{1}{s}\log\mathbb{P}\\{S^{\prime}(\epsilon,k)-k=s\\}\leq
p_{e}$.

This claim is showing that there exist an estimator
$\mathbf{M_{1}^{\prime}}diag\\{\mathbf{L},\cdots,\mathbf{L}\\}$ which can
estimate the state $(\mathbf{x_{1,\nu_{1}}})_{m_{1,\nu_{1}}}$ with
observations at time $k_{1},\cdots,k_{m}$.

###### Proof:

By the construction, $(\mathbf{A^{\prime}},\mathbf{L}\mathbf{C^{\prime}})$ is
observable and $\mathbf{L}\mathbf{C^{\prime}}$ is a row vector. Thus, by Lemma
17 we can find a polynomial $p^{\prime}(k)$ and a family of stopping time
$\\{S^{\prime}(\epsilon,k):k\in\mathbb{Z^{+}},\epsilon>0\\}$ such that for all
$\epsilon>0$, $k\in\mathbb{Z}^{+}$ there exist $k\leq
k_{1}<k_{2}<\cdots<k_{m^{\prime}}\leq S^{\prime}(\epsilon,k)$ and
$\mathbf{M^{\prime}}$ satisfying:
(i) $\beta[k_{i}]=1$ for $1\leq i\leq m^{\prime}$
(ii)
$\mathbf{M^{\prime}}\begin{bmatrix}\mathbf{L}\mathbf{C^{\prime}}e^{-(k_{1}I+t_{k_{1}})\mathbf{A^{\prime}}}\\\
\mathbf{L}\mathbf{C^{\prime}}e^{-(k_{2}I+t_{k_{2}})\mathbf{A^{\prime}}}\\\
\vdots\\\
\mathbf{L}\mathbf{C^{\prime}}e^{-(k_{m^{\prime}}I+t_{k_{m^{\prime}}})\mathbf{A^{\prime}}}\\\
\end{bmatrix}=\mathbf{I}$
(iii)
$\left|\mathbf{M^{\prime}}\right|_{max}\leq\frac{p^{\prime}(S^{\prime}(\epsilon,k))}{\epsilon}e^{\lambda_{1}S^{\prime}(\epsilon,k)I}$
(iv) $\lim_{\epsilon\downarrow
0}\exp\limsup_{s\rightarrow\infty}\sup_{k\in\mathbb{Z^{+}}}\frac{1}{s}\log\mathbb{P}\\{S^{\prime}(\epsilon,k)-k=s\\}\leq
p_{e}$.

Let $\mathbf{M^{\prime}_{1}}$ be the $m_{1,\nu_{1}}$th row of
$\mathbf{M^{\prime}}$. Then,

$\displaystyle\mathbf{M^{\prime}_{1}}\begin{bmatrix}\mathbf{L}&0&\cdots&0\\\
0&\mathbf{L}&\cdots&0\\\ \vdots&\vdots&\ddots&\vdots\\\
0&0&\cdots&\mathbf{L}\end{bmatrix}\begin{bmatrix}\mathbf{C}e^{-(k_{1}I+t_{k_{1}})\mathbf{A_{c}}}\\\
\mathbf{C}e^{-(k_{2}I+t_{k_{2}})\mathbf{A_{c}}}\\\ \vdots\\\
\mathbf{C}e^{-(k_{m^{\prime}}I+t{k_{m^{\prime}}})\mathbf{A_{c}}}\\\
\end{bmatrix}\mathbf{x}=\mathbf{M^{\prime}_{1}}\begin{bmatrix}\mathbf{L}\mathbf{C}e^{-(k_{1}I+t_{k_{1}})\mathbf{A_{c}}}\mathbf{x}\\\
\mathbf{L}\mathbf{C}e^{-(k_{2}I+t_{k_{2}})\mathbf{A_{c}}}\mathbf{x}\\\
\vdots\\\
\mathbf{L}\mathbf{C}e^{-(k_{m^{\prime}}I+t_{k_{m^{\prime}}})\mathbf{A_{c}}}\mathbf{x}\\\
\end{bmatrix}$
$\displaystyle=\mathbf{M^{\prime}_{1}}\begin{bmatrix}\mathbf{L^{\prime}}\mathbf{C^{\prime}}e^{-(k_{1}I+t_{k_{1}})\mathbf{A^{\prime}}}\mathbf{x^{\prime}}\\\
\mathbf{L^{\prime}}\mathbf{C^{\prime}}e^{-(k_{2}I+t_{k_{2}})\mathbf{A^{\prime}}}\mathbf{x^{\prime}}\\\
\vdots\\\
\mathbf{L^{\prime}}\mathbf{C^{\prime}}e^{-(k_{m^{\prime}}I+t_{k_{m^{\prime}}})\mathbf{A^{\prime}}}\mathbf{x^{\prime}}\\\
\end{bmatrix}(\because Claim~{}\ref{claim:dummy}\mbox{ (v)})$
$\displaystyle=\mathbf{M^{\prime}_{1}}\begin{bmatrix}\mathbf{L^{\prime}}\mathbf{C^{\prime}}e^{-(k_{1}I+t_{k_{1}})\mathbf{A^{\prime}}}\\\
\mathbf{L^{\prime}}\mathbf{C^{\prime}}e^{-(k_{2}I+t_{k_{2}})\mathbf{A^{\prime}}}\\\
\vdots\\\
\mathbf{L^{\prime}}\mathbf{C^{\prime}}e^{-(k_{m^{\prime}}I+t_{k_{m^{\prime}}})\mathbf{A^{\prime}}}\\\
\end{bmatrix}\mathbf{x^{\prime}}=(\mathbf{x^{\prime}})_{m_{1,\nu_{1}}}=(\mathbf{x_{1,\nu_{1}}})_{m_{1,\nu_{1}}}(\because
Claim~{}\ref{claim:dummy}\mbox{ (iv)}).$ (169)

∎

$\bullet$ Subtracting $(\mathbf{x_{1,\nu_{1}}})_{m_{1,\nu_{1}}}$ from the
observations: Now, we have an estimation for
$(\mathbf{x_{1,\nu_{1}}})_{m_{1,\nu_{1}}}$. We will remove it from the system.
$\mathbf{A^{\prime\prime}}$,$\mathbf{C^{\prime\prime}}$ and
$\mathbf{x^{\prime\prime}}$ are the system matrices after the removal.
Formally, $\mathbf{A^{\prime\prime}}$,$\mathbf{C^{\prime\prime}}$ and
$\mathbf{x^{\prime\prime}}$ are obtained by removing $\sum_{1\leq
i\leq\nu_{i}}m_{1,i}$th row and column from $\mathbf{A_{c}}$, removing
$\sum_{1\leq i\leq\nu_{i}}m_{1,i}$th row from $\mathbf{C}$ and removing
$\sum_{1\leq i\leq\nu_{i}}m_{1,i}$th component from $\mathbf{x}$ respectively.

Obviously, $\mathbf{A^{\prime\prime}}\in\mathbb{C}^{(m-1)\times(m-1)}$ and
$\mathbf{C^{\prime\prime}}\in\mathbb{C}^{l\times(m-1)}$. Moreover, since the
last element of the Jordan block $\mathbf{A_{1,\nu_{1}}}$ is removed and the
observability only depends on the first element,
$(\mathbf{A^{\prime\prime}},\mathbf{C^{\prime\prime}})$ is observable. Denote
$\lambda_{1}^{\prime\prime}+\omega_{1}^{\prime\prime}$ be the eigenvalue of
$\mathbf{A^{\prime\prime}}$ with the largest real part. Then, trivially
$\lambda_{1}^{\prime\prime}\leq\lambda_{1}$.

The new system $(\mathbf{A^{\prime\prime}},\mathbf{C^{\prime\prime}})$ and the
original system $(\mathbf{A},\mathbf{C})$ are related as follows. Denote the
$\sum_{1\leq i\leq\nu_{i}}m_{1,i}$th column of
$\mathbf{C}e^{-k\mathbf{A_{c}}}$ as $\mathbf{R}(k)$. Then, we have

$\displaystyle\mathbf{C}\mathbf{e^{-k\mathbf{A_{c}}}}\mathbf{x}-\mathbf{R}(k)(\mathbf{x_{1,\nu_{1}}})_{m_{1,\nu_{1}}}$
$\displaystyle=\mathbf{C^{\prime\prime}}\mathbf{e^{-k\mathbf{A^{\prime\prime}}}}\mathbf{x^{\prime\prime}}$
(170)

which can be easily proved from the block diagonal structure of
$\mathbf{A_{c}}$. We can further see that there exists a polynomial
$p^{\prime\prime\prime}(k)$ such that $\left|\mathbf{R}(k)\right|_{max}\leq
p^{\prime\prime\prime}(k)e^{-k\lambda_{1}}$.

$\bullet$ Decoding the remaining element of $\mathbf{x}$: We decoded and
subtracted the state $(\mathbf{x_{1,\nu_{1}}})_{m_{1,\nu_{1}}}$ from the
system. Now, we can apply the induction hypothesis to the remaining
$(m-1)$-dimensional system and estimate the remaining states.

By induction hypothesis, for given $S^{\prime}(\epsilon,k)$, we can find
$m^{\prime\prime}\in\mathbb{Z}$ and a polynomial $p^{\prime\prime}(k)$ and a
family of stopping time
$\\{S^{\prime\prime}(\epsilon,S^{\prime}(\epsilon,k)):S^{\prime}(\epsilon,k)\in\mathbb{Z^{+}},0<\epsilon<1\\}$
such that for all $0<\epsilon<1$ there exist
$S^{\prime}(\epsilon,k)<k_{m^{\prime}+1}<\cdots<k_{m^{\prime\prime}}\leq
S^{\prime\prime}(\epsilon,S^{\prime}(\epsilon,k))$ and a
$(m-1)\times(m^{\prime\prime}-m^{\prime})l$ matrix $\mathbf{M^{\prime\prime}}$
satisfying the following conditions:
(i) $\beta[k_{i}]=1$ for $m^{\prime}+1\leq i\leq m^{\prime\prime}$
(ii)
$\mathbf{M^{\prime\prime}}\begin{bmatrix}\mathbf{C^{\prime\prime}}e^{-(k_{m^{\prime}+1}I+t_{k_{m^{\prime}+1}})\mathbf{A^{\prime\prime}}}\\\
\mathbf{C^{\prime\prime}}e^{-(k_{m^{\prime}+2}I+t_{k_{m^{\prime}+2}})\mathbf{A^{\prime\prime}}}\\\
\vdots\\\
\mathbf{C^{\prime\prime}}e^{-(k_{m^{\prime\prime}}I+t_{k_{m^{\prime\prime}}})\mathbf{A^{\prime\prime}}}\\\
\end{bmatrix}=\mathbf{I}_{(m-1)\times(m-1)}$
(iii)
$\left|\mathbf{M^{\prime\prime}}\right|_{max}\leq\frac{p^{\prime\prime}(S^{\prime\prime}(\epsilon,S^{\prime}(\epsilon,k)))}{\epsilon}e^{\lambda_{1}^{\prime\prime}S^{\prime\prime}(\epsilon,S^{\prime}(\epsilon,k))I}$
(iv) $\lim_{\epsilon\downarrow
0}\exp\limsup_{s\rightarrow\infty}\operatorname{ess\,sup}\frac{1}{s}\log\mathbb{P}\\{S^{\prime\prime}(\epsilon,S^{\prime}(\epsilon,k))-S^{\prime}(\epsilon,k)=s|\mathcal{F}_{S^{\prime}(\epsilon,k)}\\}\leq
p_{e}$
where $\mathcal{F}_{n}$ is the $\sigma$-field generated by
$\beta[0],\cdots,\beta[n]$ and $t_{0},\cdots,t_{n}$.

Then,

$\displaystyle\mathbf{x^{\prime\prime}}$
$\displaystyle=\mathbf{M^{\prime\prime}}\begin{bmatrix}\mathbf{C^{\prime\prime}}e^{-(k_{m^{\prime}+1}I+t_{k_{m^{\prime}+1}})\mathbf{A^{\prime\prime}}}\\\
\mathbf{C^{\prime\prime}}e^{-(k_{m^{\prime}+2}I+t_{k_{m^{\prime}+2}})\mathbf{A^{\prime\prime}}}\\\
\vdots\\\
\mathbf{C^{\prime\prime}}e^{-(k_{m^{\prime\prime}}I+t_{k_{m^{\prime\prime}}})\mathbf{A^{\prime\prime}}}\\\
\end{bmatrix}\mathbf{x^{\prime\prime}}$
$\displaystyle=\mathbf{M^{\prime\prime}}\begin{bmatrix}\mathbf{C}e^{-(k_{m^{\prime}+1}I+t_{k_{m^{\prime}+1}})\mathbf{A_{c}}}\mathbf{x}-\mathbf{R}(k_{m^{\prime}+1}I+t_{k_{m^{\prime}+1}})(\mathbf{x_{1,\nu_{1}}})_{m_{1,\nu_{1}}}\\\
\mathbf{C}e^{-(k_{m^{\prime}+2}I+t_{k_{m^{\prime}+2}})\mathbf{A_{c}}}\mathbf{x}-\mathbf{R}(k_{m^{\prime}+2}I+t_{k_{m^{\prime}+2}})(\mathbf{x_{1,\nu_{1}}})_{m_{1,\nu_{1}}}\\\
\vdots\\\
\mathbf{C}e^{-(k_{m^{\prime\prime}}I+t_{k_{m^{\prime\prime}}})\mathbf{A_{c}}}\mathbf{x}-\mathbf{R}(k_{m^{\prime\prime}}I+t_{k_{m^{\prime\prime}}})(\mathbf{x_{1,\nu_{1}}})_{m_{1,\nu_{1}}}\\\
\end{bmatrix}$ (171)
$\displaystyle=\mathbf{M^{\prime\prime}}\left(\begin{bmatrix}\mathbf{C}e^{-(k_{m^{\prime}+1}I+t_{k_{m^{\prime}+1}})\mathbf{A_{c}}}\\\
\mathbf{C}e^{-(k_{m^{\prime}+2}I+t_{k_{m^{\prime}+2}})\mathbf{A_{c}}}\\\
\vdots\\\
\mathbf{C}e^{-(k_{m^{\prime\prime}}I+t_{k_{m^{\prime\prime}}})\mathbf{A_{c}}}\\\
\end{bmatrix}\mathbf{x}-\begin{bmatrix}\mathbf{R}(k_{m^{\prime}+1}I+t_{k_{m^{\prime}+1}})\\\
\mathbf{R}(k_{m^{\prime}+2}I+t_{k_{m^{\prime}+2}})\\\ \vdots\\\
\mathbf{R}(k_{m^{\prime\prime}}I+t_{k_{m^{\prime\prime}}})\\\
\end{bmatrix}(\mathbf{x_{1,\nu_{1}}})_{m_{1,\nu_{1}}}\right)$
$\displaystyle=\mathbf{M^{\prime\prime}}\left(\begin{bmatrix}\mathbf{C}e^{-(k_{m^{\prime}+1}I+t_{k_{m^{\prime}+1}})\mathbf{A_{c}}}\\\
\mathbf{C}e^{-(k_{m^{\prime}+2}I+t_{k_{m^{\prime}+2}})\mathbf{A_{c}}}\\\
\vdots\\\
\mathbf{C}e^{-(k_{m^{\prime\prime}}I+t_{k_{m^{\prime\prime}}})\mathbf{A_{c}}}\\\
\end{bmatrix}\mathbf{x}-\begin{bmatrix}\mathbf{R}(k_{m^{\prime}+1}I+t_{k_{m^{\prime}+1}})\\\
\mathbf{R}(k_{m^{\prime}+2}I+t_{k_{m^{\prime}+2}})\\\ \vdots\\\
\mathbf{R}(k_{m^{\prime\prime}}I+t_{k_{m^{\prime\prime}}})\\\
\end{bmatrix}\mathbf{M_{1}^{\prime}}\begin{bmatrix}\mathbf{L}&0&\cdots&0\\\
0&\mathbf{L}&\cdots&0\\\ \vdots&\vdots&\ddots&\vdots\\\
0&0&\cdots&\mathbf{L}\end{bmatrix}\begin{bmatrix}\mathbf{C}e^{-(k_{1}I+t_{k_{1}})\mathbf{A_{c}}}\\\
\mathbf{C}e^{-(k_{2}I+t_{k_{2}})\mathbf{A_{c}}}\\\ \vdots\\\
\mathbf{C}e^{-(k_{m^{\prime}}I+t_{k_{m^{\prime}}})\mathbf{A_{c}}}\\\
\end{bmatrix}\mathbf{x}\right)$ (172)
$\displaystyle=\mathbf{M^{\prime\prime}}\begin{bmatrix}-\begin{bmatrix}\mathbf{R}(k_{m^{\prime}+1}I+t_{k_{m^{\prime}+1}})\\\
\mathbf{R}(k_{m^{\prime}+2}I+t_{k_{m^{\prime}+2}})\\\ \vdots\\\
\mathbf{R}(k_{m^{\prime\prime}}I+t_{k_{m^{\prime\prime}}})\\\
\end{bmatrix}\mathbf{M_{1}^{\prime}}\begin{bmatrix}\mathbf{L}&0&\cdots&0\\\
0&\mathbf{L}&\cdots&0\\\ \vdots&\vdots&\ddots&\vdots\\\
0&0&\cdots&\mathbf{L}\end{bmatrix}&\mathbf{I}\end{bmatrix}\begin{bmatrix}\mathbf{C}e^{-(k_{1}I+t_{k_{1}})\mathbf{A_{c}}}\\\
\mathbf{C}e^{-(k_{2}I+t_{k_{2}})\mathbf{A_{c}}}\\\ \vdots\\\
\mathbf{C}e^{-(k_{m^{\prime\prime}}I+t_{k_{m^{\prime\prime}}})\mathbf{A_{c}}}\\\
\end{bmatrix}\mathbf{x}$

where (171) follows from (170), and (172) follows from the condition (ii) of
Claim 3.Therefore, we can recover the remaining states of $\mathbf{x}$.

Moreover, we have

$\displaystyle\left|\mathbf{M^{\prime\prime}}\begin{bmatrix}-\begin{bmatrix}\mathbf{R}(k_{m^{\prime}+1}I+t_{k_{m^{\prime}+1}})\\\
\mathbf{R}(k_{m^{\prime}+2}I+t_{k_{m^{\prime}+2}})\\\ \vdots\\\
\mathbf{R}(k_{m^{\prime\prime}}I+t_{k_{m^{\prime\prime}}})\\\
\end{bmatrix}\mathbf{M_{1}^{\prime}}\begin{bmatrix}\mathbf{L}&0&\cdots&0\\\
0&\mathbf{L}&\cdots&0\\\ \vdots&\vdots&\ddots&\vdots\\\
0&0&\cdots&\mathbf{L}\end{bmatrix}&\mathbf{I}\end{bmatrix}\right|_{max}$
$\displaystyle\lesssim\left|\mathbf{M^{\prime\prime}}\right|_{max}\cdot\max\left\\{\left|\begin{bmatrix}\mathbf{R}(k_{m^{\prime}+1}I+t_{k_{m^{\prime}+1}})\\\
\mathbf{R}(k_{m^{\prime}+2}I+t_{k_{m^{\prime}+2}})\\\ \vdots\\\
\mathbf{R}(k_{m^{\prime\prime}}I+t_{k_{m^{\prime\prime}}})\\\
\end{bmatrix}\right|_{max}\left|\mathbf{M_{1}^{\prime}}\right|_{max}\left|\mathbf{L}\right|_{max},1\right\\}$
$\displaystyle\lesssim\frac{p^{\prime\prime}(S^{\prime\prime}(\epsilon,S^{\prime}(\epsilon,k)))}{\epsilon}e^{\lambda_{1}^{\prime\prime}S^{\prime\prime}(\epsilon,S^{\prime}(\epsilon,k))I}\max\left\\{p^{\prime\prime\prime}(k_{m^{\prime\prime}}I+t_{k_{m^{\prime\prime}}})e^{-\lambda_{1}(k_{m^{\prime}+1}I+t_{k_{m^{\prime}+1}})}\cdot\frac{p^{\prime}(S^{\prime}(\epsilon,k))}{\epsilon}e^{\lambda_{1}S^{\prime}(\epsilon,k)I}\cdot\left|\mathbf{L}\right|_{max},1\right\\}$
$\displaystyle\lesssim\frac{\bar{p}(S^{\prime\prime}(\epsilon,S^{\prime}(\epsilon,k)))}{\epsilon^{2}}e^{\lambda_{1}S^{\prime\prime}(\epsilon,S^{\prime}(\epsilon,k))I}\
(\because S^{\prime}(\epsilon,k)<k_{m^{\prime}+1}<k_{m^{\prime\prime}}\leq
S^{\prime\prime}(\epsilon,S^{\prime}(\epsilon,k)),\
\lambda_{1}^{\prime\prime}\leq\lambda_{1})$

for some polynomial $\bar{p}(k)$. Since for some $\bar{\bar{p}}(k)$

$\displaystyle\left|\mathbf{M_{1}^{\prime}}\right|_{max}\leq\frac{p^{\prime}(S^{\prime}(\epsilon,k))}{\epsilon}e^{\lambda_{1}S^{\prime}(\epsilon,k)I}\leq\frac{\bar{\bar{p}}(S^{\prime\prime}(\epsilon,S^{\prime}(\epsilon,k)))}{\epsilon^{2}}e^{\lambda_{1}S^{\prime\prime}(\epsilon,S^{\prime}(\epsilon,k))I}$

and we can recover $\mathbf{x}$ from $\mathbf{x^{\prime\prime}}$ and
$(\mathbf{x_{1,\nu_{1}}})_{m_{1,\nu_{1}}}$, there exists $\mathbf{M}$ and a
polynomial $p(k)$ such that

$\displaystyle\mathbf{M}\begin{bmatrix}\mathbf{C}e^{-(k_{1}I+t_{k_{1}})\mathbf{A_{c}}}\\\
\vdots\\\
\mathbf{C}e^{-(k_{m^{\prime\prime}}I+t_{k_{m^{\prime\prime}}})\mathbf{A_{c}}}\end{bmatrix}=\mathbf{I}_{m\times
m}$

and

$\displaystyle\left|\mathbf{M}\right|_{max}\leq\frac{p(S^{\prime\prime}(\epsilon,S^{\prime}(\epsilon,k)))}{\epsilon^{2}}e^{\lambda_{1}S^{\prime\prime}(\epsilon,S^{\prime}(\epsilon,k))I}.$

Moreover, since

$\displaystyle\lim_{\epsilon\downarrow
0}\exp\limsup_{s\rightarrow\infty}\operatorname{ess\,sup}\log\mathbb{P}\\{S^{\prime\prime}(\epsilon,S^{\prime}(\epsilon,k))-S^{\prime}(\epsilon,k)|\mathcal{F}_{S^{\prime}(\epsilon,k)}\\}\leq
p_{e}$

and

$\displaystyle\lim_{\epsilon\downarrow
0}\exp\limsup_{s\rightarrow\infty}\sup_{k\in\mathbb{Z^{+}}}\log\mathbb{P}\\{S^{\prime}(\epsilon,k)-k\\}\leq
p_{e},$

by Lemma 6

$\displaystyle\lim_{\epsilon\downarrow
0}\exp\limsup_{s\rightarrow\infty}\sup_{k\in\mathbb{Z^{+}}}\log\mathbb{P}\\{S^{\prime\prime}(\epsilon,S^{\prime}(\epsilon,k))-k\\}\leq
p_{e}.$

Therefore, by putting
$S(\epsilon,k):=S^{\prime\prime}(\epsilon^{\frac{1}{2}},S^{\prime}(\epsilon^{\frac{1}{2}},k))$,
$S(\epsilon,k)$ satisfies all the conditions of the lemma. ∎

###  X-E Lemmas about the Observability Gramian of Discrete-Time Systems

Now, we will consider the discrete-time systems discussed in Section VI. Like
the continuous time case, we start from a simpler case when $\mathbf{C}$ is a
row vector and $\mathbf{A}$ has no eigenvalue cycles. The definitions
corresponding to (90) for the row vector case are given as follows: Let
$\mathbf{A}$ be a $m\times m$ Jordan form matrix and $\mathbf{C}$ be $1\times
m$ row vector which can be written as

$\displaystyle\mathbf{A}=diag\\{\mathbf{A_{1,1}},\mathbf{A_{1,2}},\cdots,\mathbf{A_{1,\nu_{1}}},\cdots,\mathbf{A_{\mu,1}},\cdots,\mathbf{A_{\mu,\nu_{\mu}}}\\}$
(173)
$\displaystyle\mathbf{C}=\begin{bmatrix}\mathbf{C_{1,1}},\mathbf{C_{1,2}},\cdots,\mathbf{C_{1,\nu_{1}}},\cdots,\mathbf{C_{\mu,1}},\cdots,\mathbf{C_{\mu,\nu_{\mu}}}\end{bmatrix}$
(174) where $\mathbf{A_{i,j}}$ is a Jordan block with eigenvalue
$\lambda_{i,j}e^{j2\pi\omega_{i,j}}$ and size $m_{i,j}$ $\displaystyle\quad
m_{i,1}\leq m_{i,2}\leq\cdots\leq m_{i,\nu_{i}}\mbox{ for all }i=1,\cdots,\mu$
$\displaystyle\quad\lambda_{i,1}=\lambda_{i,2}=\cdots=\lambda_{i,\nu_{i}}\mbox{
for all }i=1,\cdots,\mu$
$\displaystyle\quad\lambda_{1,1}>\lambda_{2,1}>\cdots>\lambda_{\mu,1}\geq 1$
$\displaystyle\quad\\{\lambda_{i,1},\cdots,\lambda_{i,\nu_{i}}\\}\mbox{ is
cycle with length $\nu_{i}$ and period $p_{i}$}$ For all
$(i,j)\neq(i^{\prime},j^{\prime})$,
$\omega_{i,j}-\omega_{i^{\prime},j^{\prime}}\notin\mathbb{Q}$
$\mathbf{C_{i,j}}$ is a $1\times m_{i,j}$ complex matrix and its first element
is non-zero $\displaystyle\quad\mbox{$\lambda_{i}e^{j2\pi\omega_{i}}$ is
$(i,i)$ element of $\mathbf{A}$}.$

Here, we can notice that $\mathbf{A}$ has no eigenvalue cycles since
$\omega_{i,j}-\omega_{i^{\prime},j^{\prime}}\notin\mathbb{Q}$ for all
$(i,j)\neq(i^{\prime},j^{\prime})$, and $\mathbf{C}$ is a row vector. By
Theorem 6, the condition that the first elements of $\mathbf{C_{i,j}}$ are
non-zero corresponds to the observability condition of
$(\mathbf{A},\mathbf{C})$ since $\mathbf{C}$ is a row vector.

Let’s state lemmas which parallel Lemma 10 and Lemma 12. In fact, the proofs
of the lemmas are very similar to those of Lemma 10 and Lemma 12 and we omit
the proofs here.

###### Lemma 19

Let $\mathbf{A}$ and $\mathbf{C}$ be given as (173) and (174). Then, there
exists a polynomial $p(k)$ such that for all $\epsilon>0$ and $0\leq
k_{1}\leq\cdots\leq k_{m}$, if

$\displaystyle\left|\det\left(\begin{bmatrix}\mathbf{C}\mathbf{A}^{-k_{1}}\\\
\mathbf{C}\mathbf{A}^{-k_{2}}\\\ \vdots\\\
\mathbf{C}\mathbf{A}^{-k_{m}}\end{bmatrix}\right)\right|\geq\epsilon\prod_{1\leq
i\leq m}\lambda_{i}^{-k_{i}}$

then

$\displaystyle\left|\begin{bmatrix}\mathbf{C}\mathbf{A}^{-k_{1}}\\\
\mathbf{C}\mathbf{A}^{-k_{2}}\\\ \vdots\\\ \mathbf{C}\mathbf{A}^{-k_{m}}\\\
\end{bmatrix}\right|_{max}\leq\frac{p(k_{m})}{\epsilon}\lambda_{1}^{k_{m}}$

###### Proof:

It can be easily proved in a similar way to Lemma 10 ∎

###### Lemma 20

Let $\mathbf{A}$ and $\mathbf{C}$ be given as (173) and (174). Define
$a_{i,j}$ and $C_{i,j}$ as the $(i,j)$ element and cofactor of
$\begin{bmatrix}\mathbf{C}\mathbf{A}^{-k_{1}}\\\
\mathbf{C}\mathbf{A}^{-k_{2}}\\\ \vdots\\\
\mathbf{C}\mathbf{A}^{-k_{m}}\end{bmatrix}$ respectively. Then there exists
$g_{\epsilon}(k):\mathbb{R}^{+}\rightarrow\mathbb{R}^{+}$ and
$a\in\mathbb{R}^{+}$ such that for all $\epsilon>0$ and $k_{1},\cdots,k_{m}$
satisfying

$\displaystyle(i)0\leq k_{1}<k_{2}<\cdots<k_{m}$
$\displaystyle(ii)k_{m}-k_{m-1}\geq g_{\epsilon}(k_{m-1})$
$\displaystyle(iii)g_{\epsilon}(k)\leq a(1+\log(k+1))$
$\displaystyle(iv)\left|\sum_{m-m_{\mu}+1\leq i\leq
m}a_{m,i}C_{m,i}\right|\geq\epsilon\prod_{1\leq i\leq
m}{\lambda_{i}}^{-k_{i}}$

the following inequality holds:

$\displaystyle\left|\det\left(\begin{bmatrix}\mathbf{C}\mathbf{A}^{-k_{1}}\\\
\mathbf{C}\mathbf{A}^{-k_{2}}\\\ \vdots\\\ \mathbf{C}\mathbf{A}^{-k_{m}}\\\
\end{bmatrix}\right)\right|\geq\frac{1}{2}\epsilon\prod_{1\leq i\leq
m}{\lambda_{i}}^{-k_{i}}.$

###### Proof:

It can be easily proved in a similar way to Lemma 12. ∎

Like the continuous-time case, these lemmas reduce questions about the inverse
of the observability Gramian to questions about the determinant of the
observability Gramian.

###  X-F Uniform Convergence of Sequences satisfying Weyl’s criterion
(Discrete-Time Systems)

As we did in the continuous-time case, we will prove that the determinant of
the observability matrix is large enough regardless of the erasure pattern.
The main difference from the continuous-time case of Appendix X-C is the
measure that must be used. While we used the Lebesgue measure to measure the
bad event —the event that the determinant of the observability matrix is
small—, we use the counting measure in this section.

The main idea of this section is approximating aperiodic deterministic
sequences by random variables using ergodic theory [15]. The necessary and
sufficient condition for a sequence to behave like uniformly distributed
random variables in $[0,1]$ is known as Weyl’s criterion. We first state a
general ergodic theorem, and derive the Weyl’s criterion as a corollary.

######  Theorem 11 (Koksma and Szusz inequality [15])

Consider a $s$-dimensional sequence
$\mathbf{x_{1}},\mathbf{x_{2}},\cdots\in\mathbb{R}^{s}$, and let
$\alpha:=(\alpha_{1},\cdots,\alpha_{s})$ and
$\beta:=(\beta_{1},\cdots,\beta_{s})$. For any positive integer $m$, we have

$\displaystyle\sup_{0\leq\alpha_{i}<\beta_{i}\leq
1}\left|\frac{A\left([\mathbf{\alpha},\mathbf{\beta});N,\\{\mathbf{x_{n}}\\}\right)}{N}-\prod_{1\leq
i\leq s}(\beta_{i}-\alpha_{i})\right|\leq
2s^{2}3^{s+1}\left(\frac{1}{m}+\sum_{\mathbf{h}\in\mathbb{Z}^{s},0<|\mathbf{h}|_{\infty}\leq
m}\frac{1}{r(\mathbf{h})}\left|\frac{1}{N}\sum_{1\leq n\leq
N}e^{2\pi\sqrt{-1}\left<\mathbf{h},\mathbf{x_{n}}\right>}\right|\right)$

where

$\displaystyle
A\left([\mathbf{\alpha},\mathbf{\beta});N,\\{\mathbf{x_{n}}\\}\right):=\sum_{1\leq
n\leq
N}\mathbf{1}\left\\{\mathbf{x_{n}}\in[\alpha_{1},\beta_{1})\times[\alpha_{2},\beta_{2})\cdots\times[\alpha_{s},\beta_{s})\right\\}$
(175) $\displaystyle r(\mathbf{h}):=\prod_{1\leq j\leq s}\max\\{|h_{j}|,1\\}.$

###### Proof:

See [15] for the proof. ∎

Here, we can see $A([\alpha,\beta);N,\\{\mathbf{x_{n}})$ is the counting
measure of the event that a sequence falls in the set $[\alpha,\beta)$. The
theorem tells us that the counting measure is close to the Lebesgue measure of
the set $[\alpha,\beta)$ uniformly over all $\alpha,\beta$.

Using this theorem, we can easily derive181818The original Weyl’s criterion is
shown for only one sequence. But, here we extend Weyl’s criterion to a family
of sequences. For this, we state a generalized theorem of the Weyl’s criterion
and prove it. the Weyl’s criterion for a family of sequences.

###### Definition 16

Consider a family of $s$-dimensional sequences
$\mathcal{J}=\\{(\mathbf{x_{1,\sigma}},\mathbf{x_{2,\sigma}},\cdots):\sigma\in
J,x_{i,\sigma}\in\mathbb{R}^{s}\\}$. Here, the index set for the sequences,
$J$, can be infinite. If for all
$\mathbf{h}\in\mathbb{Z}^{s}\setminus\\{\mathbf{0}\\}$,

$\displaystyle\lim_{N\rightarrow\infty}\sup_{\sigma\in\mathcal{J}}\left|\frac{1}{N}\sum_{1\leq
n\leq N}e^{j2\pi\left<\mathbf{h},\mathbf{x_{n,\sigma}}\right>}\right|=0$

then the family of sequences is said to satisfy Weyl’s criterion.

######  Theorem 12 (Weyl’s criterion [15])

Consider a family of $s$-dimensional sequences
$\mathcal{J}=\\{(\mathbf{x_{1,\sigma}},\mathbf{x_{2,\sigma}},\cdots):\sigma\in
J,x_{i,\sigma}\in\mathbb{R}^{s}\\}$, which satisfy the Weyl’s criterion. Then,
this family of sequences satisfies

$\displaystyle\lim_{N\rightarrow\infty}\sup_{\sigma\in\mathcal{J}}\sup_{0\leq\alpha_{i}<\beta_{i}\leq
1}\left|\frac{A\left([\mathbf{\alpha},\mathbf{\beta});N,\\{\mathbf{x_{n,\sigma}}\\}\right)}{N}-\prod_{1\leq
i\leq s}(\beta_{i}-\alpha_{i})\right|=0,$

where the definition of
$A\left([\mathbf{\alpha},\mathbf{\beta});N,\\{\mathbf{x_{n,\sigma}}\\}\right)$
is given in (175).

###### Proof:

By Theorem 11, for any positive integer $m$, we have

$\displaystyle\sup_{\sigma\in\mathcal{J}}\sup_{0\leq\alpha_{i}<\beta_{i}\leq
1}\left|\frac{A\left([\mathbf{\alpha},\mathbf{\beta});N,\\{\mathbf{x_{n,\sigma}}\\}\right)}{N}-\prod_{1\leq
i\leq s}(\beta_{i}-\alpha_{i})\right|$ (176)
$\displaystyle\leq\sup_{\sigma\in\mathcal{J}}2s^{2}3^{s+1}\left(\frac{1}{m}+\sum_{0<|\mathbf{h}|_{\infty}\leq
m}\frac{1}{r(\mathbf{h})}\left|\frac{1}{N}\sum_{1\leq n\leq N}e^{2\pi
j\left<\mathbf{h},\mathbf{x_{n,\sigma}}\right>}\right|\right)$ (177)

To prove the theorem, it is enough to show that for all $\delta>0$ there
exists $N^{\prime}$ such that for all $N>N^{\prime}$

$\displaystyle\sup_{\sigma\in\mathcal{J}}\sup_{0\leq\alpha_{i}<\beta_{i}\leq
1}\left|\frac{A\left([\mathbf{\alpha},\mathbf{\beta});N,\\{\mathbf{x_{n,\sigma}}\\}\right)}{N}-\prod_{1\leq
i\leq s}(\beta_{i}-\alpha_{i})\right|<\delta.$ (178)

Let’s choose $m:=\frac{4s^{2}3^{s+1}}{\delta}$ so that

$\displaystyle\frac{2s^{2}3^{s+1}}{m}<\frac{\delta}{2}.$ (179)

Once we fix $m$, there are only $(2m+1)^{s}$ number of
$\mathbf{h}\in\mathbb{Z}^{s}$ such that $|\mathbf{h}|_{\infty}\leq m$.
Furthermore, by the definition of Weyl’s criterion, we can find
$N^{\prime\prime}$ such that for all $N>N^{\prime\prime}$,

$\displaystyle\sup_{\sigma\in\mathcal{J}}\left|\frac{1}{N}\sum_{1\leq n\leq
N}e^{j2\pi\left<\mathbf{h},\mathbf{x_{n,\sigma}}\right>}\right|<\frac{1}{(2m+1)^{s}2s^{2}3^{s+1}}\frac{\delta}{2}.$
(180)

Thus, we can find $N^{\prime\prime}$ such that for all $N>N^{\prime\prime}$
the following holds:

$\displaystyle 2s^{2}3^{s+1}s^{m+1}\max_{0<|\mathbf{h}|_{\infty}\leq
m}\sup_{\sigma\in\mathcal{J}}\left|\frac{1}{N}\sum_{1\leq n\leq
N}e^{j2\pi\left<\mathbf{h},\mathbf{x_{n,\sigma}}\right>}\right|<\frac{\delta}{2}$
(181)

Therefore, by plugging (179), (181) into (177), we can prove (178). Thus, the
theorem is true. ∎

Since we are mainly interested in the fractional part of sequences, it will be
helpful to denote $\left<x\right>:=x-\lfloor x\rfloor$. Although
$\left<\mathbf{x},\mathbf{y}\right>$ is the inner product between two vectors,
these two definitions can be distinguished by counting the number of
arguments. Let’s consider some specific sequences, and see whether they
satisfies the Weyl’s criterion.

###### Example 1

$\left(\left<\sqrt{2}n\right>,\left<\sqrt{3}n\right>\right)$ satisfies Weyl’s
criterion and
$\left(\left<\sqrt{2}n\right>,\left<(\sqrt{2}+\sqrt{3})n\right>\right)$ does
too.
$\left(\left<\sqrt{2}n\right>,\left<\left(\sqrt{2}+0.5\right)n\right>\right)$
does not satisfy Weyl’s criterion and neither does
$\left(\left<\sqrt{2}n\right>,\left<\frac{\sqrt{2}}{2}n\right>\right)$.

Therefore, among general sequences in the form of
$(\left<\omega_{1}n\right>,\left<\omega_{2}n\right>,\cdots,\left<\omega_{m}n\right>)$,
there are sequences which satisfy Weyl’s criterion and others do not. However,
the following lemma reveals all sequences can be written as linear
combinations of basis sequences which satisfy Weyl’s criterion. This idea is
very similar to that linear-algebraic concepts like linear decomposition and
basis.

###### Lemma 21

Consider an $m$-dimensional sequence
$(\left<\omega_{1}n\right>,\left<\omega_{2}n\right>,\cdots,\left<\omega_{m}n\right>)$.
Then, there exists $k\leq m$ and $p\in\mathbb{N}$ such that

$\displaystyle\omega_{i}=\frac{q_{i,0}}{p}+\sum_{1\leq j\leq
k}q_{i,j}\gamma_{j}$

where

$\displaystyle q_{i,j}\in\mathbb{Z},$
$\displaystyle(\left<\gamma_{1}n\right>,\left<\gamma_{2}n\right>,\cdots,\left<\gamma_{k}n\right>)\mbox{
satisfies Weyl's criterion.}$

###### Proof:

Before the proof, we can observe the following two facts.

First, since as long as $\left<\mathbf{h},\mathbf{w}\right>$ is not an
integer,

$\displaystyle\frac{1}{N}\sum_{1\leq n\leq
N}e^{j2\pi\left<\mathbf{h},(\left<\omega_{1}n\right>,\left<\omega_{2}n\right>,\cdots,\left<\omega_{m}n\right>)\right>}=\frac{1}{N}\frac{e^{j2\pi(h_{1}\omega_{1}+h_{2}\omega_{2}+\cdots+h_{m}\omega_{m})}\left(1-e^{j2\pi
N(h_{1}\omega_{1}+h_{2}\omega_{2}+\cdots+h_{m}\omega_{m})}\right)}{1-e^{j2\pi(h_{1}\omega_{1}+h_{2}\omega_{2}+\cdots+h_{m}\omega_{m})}},$

the statement that the sequence
$(\left<\omega_{1}n\right>,\left<\omega_{2}n\right>,\cdots,\left<\omega_{m}n\right>)$
does not satisfy Weyl’s criterion is equivalent to there being
$h_{1},h_{2},\cdots,h_{m}\in\mathbb{Z}$ that are not identically zero and make

$\displaystyle
h_{1}\omega_{1}+h_{2}\omega_{2}+\cdots+h_{m}\omega_{m}\in\mathbb{Z}.$ (182)

The second observation is that if
$(\left<\omega_{1}n\right>,\left<\omega_{2}n\right>,\cdots,\left<\omega_{m}n\right>)$
satisfies Weyl’s criterion then for all $a_{1},\cdots,a_{m}\in\mathbb{N}$,
$(\left<\frac{\omega_{1}}{a_{1}}n\right>,\left<\frac{\omega_{2}}{a_{2}}n\right>,\cdots,\left<\frac{\omega_{m}}{a_{m}}n\right>)$
also satisfies Weyl’s criterion. To see this, suppose
$(\left<\frac{\omega_{1}}{a_{1}}n\right>,\left<\frac{\omega_{2}}{a_{2}}n\right>,\cdots,\left<\frac{\omega_{m}}{a_{m}}n\right>)$
did not satisfy Weyl’s criterion. Then, by (182) there would exist
$(h_{1},h_{2},\cdots,h_{m})\in\mathbb{Z}^{m}\setminus\\{\mathbf{0}\\}$ such
that
$h_{1}\frac{\omega_{1}}{a_{1}}+h_{2}\frac{\omega_{2}}{a_{2}}+\cdots+h_{m}\frac{\omega_{m}}{a_{m}}\in\mathbb{Z}$.
So, $\frac{h_{1}\prod_{1\leq i\leq
m}a_{i}}{a_{1}}{\omega_{1}}+\frac{h_{2}\prod_{1\leq i\leq
m}a_{i}}{a_{2}}{\omega_{2}}+\cdots+\frac{h_{m}\prod_{1\leq i\leq
m}a_{i}}{a_{m}}{\omega_{m}}\in\mathbb{Z}$ as well as $(\frac{h_{1}\prod_{1\leq
i\leq m}a_{i}}{a_{1}},\cdots,\frac{h_{m}\prod_{1\leq i\leq
m}a_{i}}{a_{m}})\in\mathbb{Z}^{m}\setminus\\{\mathbf{0}\\}$. But since
$(\left<\omega_{1}n\right>,\left<\omega_{2}n\right>,\cdots,\left<\omega_{m}n\right>)$
would not satisfy Weyl’s criterion, this causes a contradiction.

Now, we will prove the lemma by induction on $m$.

(i) When $m=1$,

If $\left<\omega_{1}n\right>$ satisfies Weyl’s criterion, the lemma is
trivially true by selecting $\gamma_{1}=\omega_{1}$ and $q_{1,1}=1$. If
$\left<\omega_{1}n\right>$ does not satisfy Weyl’s criterion, then by (182),
$\omega_{1}$ is a rational number. So we can find $q_{1,0}$ and $p$ such that
$\omega_{1}=\frac{q_{1,0}}{p}$, and set the $k=0$.

(ii) Assume that the lemma is true for $m-1$.

If
$(\left<\omega_{1}n\right>,\left<\omega_{2}n\right>,\cdots,\left<\omega_{m}n\right>)$
satisfies Weyl’s criterion, the lemma follows by selecting $k=m$,
$\gamma_{i}=\omega_{i}$ and $q_{i,i}=1$.

If
$(\left<\omega_{1}n\right>,\left<\omega_{2}n\right>,\cdots,\left<\omega_{m}n\right>)$
does not satisfy Weyl’s criterion, by (182) there exists
$(h_{1},h_{2},\cdots,h_{m})\in\mathbb{Z}^{m}\setminus\\{\mathbf{0}\\}$ and
$h\in\mathbb{Z}$ such that
$h_{1}\omega_{1}+h_{2}\omega_{2}+\cdots+h_{m}\omega_{m}=h$. Without loss of
generality, let’s say $h_{1}\neq 0$. Then

$\displaystyle\omega_{1}=-\frac{h_{2}}{h_{1}}\omega_{2}-\frac{h_{3}}{h_{1}}\omega_{3}-\cdots-\frac{h_{m}}{h_{1}}\omega_{m}+\frac{h}{h_{1}}.$
(183)

By induction hypothesis, we know that there exists $k^{\prime}\leq m-1$,
$p^{\prime}\in\mathbb{N}$, $q_{i,j}^{\prime}\in\mathbb{Z}$,
$\gamma_{i}^{\prime}$ such that

$\displaystyle\omega_{2}=\frac{q_{2,0}^{\prime}}{p^{\prime}}+\sum_{1\leq j\leq
k^{\prime}}q_{2,j}^{\prime}\gamma_{j}^{\prime}$ $\displaystyle\vdots$
$\displaystyle\omega_{m}=\frac{q_{m,0}^{\prime}}{p^{\prime}}+\sum_{1\leq j\leq
k^{\prime}}q_{m,j}^{\prime}\gamma_{j}^{\prime}.$ (184)

where
$(\left<\gamma_{1}^{\prime}n\right>,\left<\gamma_{2}^{\prime}n\right>,\cdots,\left<\gamma_{k}^{\prime}n\right>)$
satisfies Weyl’s criterion. Therefore, by plugging (184) to (183) we can find
$q^{\prime}_{1,j}\in\mathbb{Z}$ such that

$\displaystyle\omega_{1}=\frac{q^{\prime}_{1,0}}{|h_{1}\cdot
p^{\prime}|}+\sum_{1\leq i\leq
k}q^{\prime}_{1,i}\frac{\gamma_{i}^{\prime}}{h_{1}}.$

By the second observation,
$(\left<\frac{\gamma_{1}^{\prime}}{h_{1}}n\right>,\left<\frac{\gamma_{2}^{\prime}}{h_{1}}n\right>,\cdots,\left<\frac{\gamma_{k}^{\prime}}{h_{1}}n\right>)$
satisfies Weyl’s criterion, so we can use $p=|h_{1}\cdot p^{\prime}|$ and
$\gamma_{i}=\frac{\gamma_{i}^{\prime}}{h_{1}}$ to show that the lemma also
holds for $m$.

Therefore, by induction the lemma is true. ∎

Now, we can decompose the sequences into basis sequences which satisfy Weyl’s
criterion, and so behave like uniform random variables. The main difference
from the uniform convergence discussion of Appendix X-C is the number of
random variables. In other words, in continuous-time systems with random
jitter, only one random variable is introduced at each sample for the random
jitter. However, this is not the case in discrete-time systems.

Let $\mathbf{A_{1}}=\begin{bmatrix}e^{j\sqrt{2}}&0\\\
0&e^{j2\sqrt{2}}\end{bmatrix}$,
$\mathbf{A_{2}}=\begin{bmatrix}e^{j\sqrt{2}}&0\\\
0&e^{j\sqrt{3}}\end{bmatrix}$, $\mathbf{C}=\begin{bmatrix}1&1\end{bmatrix}$.
The row of the observability gramian of $(\mathbf{\mathbf{A_{1}}},\mathbf{C})$
is
$\mathbf{C}\mathbf{A_{1}}^{n}=\begin{bmatrix}e^{j\sqrt{2}n}&e^{j2\sqrt{2}n}\end{bmatrix}$.
In this case, the elements of $\mathbf{C}\mathbf{A_{1}}^{n}$ do not satisfy
Weyl’s criterion. Thus, it can be approximated by
$\begin{bmatrix}e^{jX}&e^{j2X}\end{bmatrix}$ where $X$ is uniform in
$[0,2\pi]$, which involves only one random variable.

However, the row of the observability gramian of
$(\mathbf{\mathbf{A_{2}}},\mathbf{C})$ is
$\mathbf{C}\mathbf{A_{2}}^{n}=\begin{bmatrix}e^{j\sqrt{2}n}&e^{j\sqrt{3}n}\end{bmatrix}$
whose elements satisfy Weyl’s criterion. Thus, it can be approximated by
$\begin{bmatrix}e^{jX_{1}}&e^{jX_{2}}\end{bmatrix}$ where $X_{1}$, $X_{2}$ are
independent uniform random variables in $[0,2\pi]$, which involves two random
variables.

Therefore, the lemmas derived in Appendix X-C have to be generalized to
multiple random variables, and then the multiple random variables can be used
to model deterministic sequences.

Intuitively, adding more randomness should not cause any problems, so
generalization to multiple random variables must be possible. We first extend
Lemma 14 which was written for a single random variable to multiple random
variables.

###### Lemma 22

Let $\mathbf{X}$ be $(X_{1},X_{2},\cdots,X_{\nu})$ where $X_{i}$ are i.i.d.
random variables whose distribution is uniform between $0$ and $2\pi$. Let
$\mathbf{k_{1}},\mathbf{k_{2}},\cdots,\mathbf{k_{\mu}}\in\mathbb{R}^{\nu}$ be
distinct. Then, for strictly positive $\gamma$, $\Gamma$ $(\gamma\leq\Gamma)$,
and $m\in\\{1,\cdots,\mu\\}$

$\displaystyle\sup_{|a_{m}|\geq\gamma,|a_{i}|\leq\Gamma,a_{i}\in\mathbb{C}}\mathbb{P}\\{|\sum^{\mu}_{i=1}a_{i}e^{j<\mathbf{k_{i}},\mathbf{X}>}|<\epsilon\\}\rightarrow
0\mbox{ as }\epsilon\downarrow 0.$

###### Proof:

We will prove the lemma by induction on $\nu$, the number of random variables.

(i) When $\nu=1$. The lemma reduces to Lemma 14.

(ii) Let’s assume the lemma is true for $1,\cdots,\nu-1$.

Without loss of generality, we can assume $m=1$ by symmetry. We will prove the
lemma by dividing into cases based on $\mathbf{k_{i}}$. Let the $j$th
component of $\mathbf{k_{i}}$ be denoted as $k_{ij}$.

First, consider the case when $k_{1,1}=k_{2,1}=\cdots=k_{\mu,1}$. Then,

$\displaystyle\sup_{|a_{1}|\geq\gamma,|a_{i}|\leq\Gamma}\mathbb{P}\\{|\sum^{\mu}_{i=1}a_{i}e^{j<\mathbf{k_{i}},\mathbf{X}>}|<\epsilon\\}=\sup_{|a_{1}|\geq\gamma,|a_{i}|\leq\Gamma}\mathbb{P}\\{|\sum^{\mu}_{i=1}a_{i}e^{j\sum_{1\leq
j\leq\nu}k_{i,j}X_{j}}|<\epsilon\\}$
$\displaystyle=\sup_{|a_{1}|\geq\gamma,|a_{i}|\leq\Gamma}\mathbb{P}\\{|e^{jk_{1,1}X_{1}}|\cdot|\sum^{\mu}_{i=1}a_{i}e^{j\sum_{2\leq
j\leq\nu}k_{i,j}X_{j}}|<\epsilon\\}$
$\displaystyle=\sup_{|a_{1}|\geq\gamma,|a_{i}|\leq\Gamma}\mathbb{P}\\{|\sum^{\mu}_{i=1}a_{i}e^{j\sum_{2\leq
j\leq\nu}k_{i,j}X_{j}}|<\epsilon\\}\rightarrow 0\ (\because\mbox{induction
hypothesis}).$

Second, consider the case when $k_{i,1}\neq k_{j,1}$ for some $i,j$. Without
loss of generality, we can assume that $k_{1,1}=k_{2,1}=\cdots=k_{\mu_{1},1}$
and $k_{1,1}\neq k_{j,1}$ for all $\mu_{1}<j\leq\mu$. Then, for all
$\epsilon^{\prime}>0$, we have

$\displaystyle\sup_{|a_{1}|\geq\gamma,|a_{i}|\leq\Gamma}\mathbb{P}\\{|\sum^{\mu}_{i=1}a_{i}e^{j<\mathbf{k_{i}},\mathbf{X}>}|<\epsilon\\}$
$\displaystyle=\sup_{|a_{1}|\geq\gamma,|a_{i}|\leq\Gamma}\mathbb{P}\\{|\sum^{\mu_{1}}_{i=1}a_{i}e^{j<\mathbf{k_{i}},\mathbf{X}>}+\sum^{\mu}_{i=\mu_{1}+1}a_{i}e^{j<\mathbf{k_{i}},\mathbf{X}>}|<\epsilon\\}$
$\displaystyle\leq\sup_{|a_{1}|\geq\gamma,|a_{i}|\leq\Gamma}\mathbb{P}\\{|\sum^{\mu_{1}}_{i=1}a_{i}e^{j<\mathbf{k_{i}},\mathbf{X}>}+\sum^{\mu}_{i=\mu_{1}+1}a_{i}e^{j<\mathbf{k_{i}},\mathbf{X}>}|<\epsilon\Big{|}|\sum^{\mu_{1}}_{i=1}a_{i}e^{j\sum_{2\leq
j\leq\nu}k_{i,j}X_{j}}|\geq\epsilon^{\prime}\\}+\mathbb{P}\\{|\sum^{\mu_{1}}_{i=1}a_{i}e^{j\sum_{2\leq
j\leq\nu}k_{i,j}X_{j}}|<\epsilon^{\prime}\\}$
$\displaystyle=\sup_{|a_{1}|\geq\gamma,|a_{i}|\leq\Gamma}\mathbb{P}\\{|(\sum^{\mu_{1}}_{i=1}a_{i}e^{j\sum_{2\leq
j\leq\nu}k_{i,j}X_{j}})e^{jk_{1,1}X_{1}}+\sum^{\mu}_{i=\mu_{1}+1}a_{i}e^{j<\mathbf{k_{i}},\mathbf{X}>}|<\epsilon\Big{|}|\sum^{\mu_{1}}_{i=1}a_{i}e^{j\sum_{2\leq
j\leq\nu}k_{i,j}X_{j}}|\geq\epsilon^{\prime}\\}$
$\displaystyle+\mathbb{P}\\{|\sum^{\mu_{1}}_{i=1}a_{i}e^{j\sum_{2\leq
j\leq\nu}k_{i,j}X_{j}}|<\epsilon^{\prime}\\}$
$\displaystyle\leq\sup_{|a^{\prime}_{1}|\geq\epsilon^{\prime},|a^{\prime}_{i}|\leq\mu\Gamma}\mathbb{P}_{X_{1}}\\{|a^{\prime}_{1}e^{jk_{1,1}X_{1}}+\sum^{\mu}_{i=\mu_{1}+1}a^{\prime}_{i}e^{jk_{i,1}X_{1}}|<\epsilon\\}+\sup_{|a_{1}|\geq\gamma,|a_{i}|\leq\Gamma}\mathbb{P}\\{|\sum^{\mu_{1}}_{i=1}a_{i}e^{j\sum_{2\leq
j\leq\nu}k_{i,j}X_{j}}|<\epsilon^{\prime}\\}.$

Therefore, by the induction hypothesis (since the first term has only one
random variable, and the second term has $\nu-1$ random variables)

$\displaystyle\lim_{\epsilon\rightarrow
0}\sup_{|a_{1}|\geq\gamma,|a_{i}|\leq\Gamma}\mathbb{P}\\{|\sum^{\mu}_{i=1}a_{i}e^{j<\mathbf{k_{i}},\mathbf{X}>}|<\epsilon\\}$
$\displaystyle\leq\lim_{\epsilon^{\prime}\rightarrow
0}\lim_{\epsilon\rightarrow
0}\sup_{|a^{\prime}_{1}|\geq\epsilon^{\prime},|a^{\prime}_{i}|\leq\mu\Gamma}\mathbb{P}\\{|a^{\prime}_{1}e^{jk_{1,1}X_{1}}+\sum^{\mu}_{i=\mu_{1}+1}a^{\prime}_{i}e^{jk_{i,1}X_{1}}|<\epsilon\\}+\sup_{|a_{1}|\geq\gamma,|a_{i}|\leq\Gamma}\mathbb{P}\\{|\sum^{\mu_{1}}_{i=1}a_{i}e^{j\sum_{2\leq
j\leq\nu}k_{i,j}X_{j}}|<\epsilon^{\prime}\\}$ $\displaystyle=0.$

Therefore, the lemma is true. ∎

Now, we will consider a deterministic sequence in the form of
$(<\omega_{1}n>,\cdots,<\omega_{\mu}n>)$. As we have shown in Lemma 21, this
sequence can be thought of as a linear combination of basis sequences which
satisfy Weyl’s criterion. Thus, we can approximate the deterministic sequence
as a linear combination of multiple uniform random variables considered in
Lemma 22.

###### Lemma 23

Let $\omega_{1},\omega_{2},\cdots,\omega_{\mu}$ be real numbers such that
$\omega_{i}-\omega_{j}\notin\mathbb{Q}$ for all $i\neq j$. Then, for strictly
positive numbers $\gamma$ and $\Gamma$ $(\gamma\leq\Gamma)$, and
$m\in\\{1,\cdots,\mu\\}$

$\displaystyle\lim_{\epsilon\downarrow
0}\lim_{N\rightarrow\infty}\sup_{|a_{m}|\geq\gamma,|a_{i}|\leq\Gamma,k\in\mathbb{Z}}\frac{1}{N}\sum^{N}_{n=1}\mathbf{1}\\{|\sum^{\mu}_{i=1}a_{i}e^{j2\pi\omega_{i}(n+k)}|<\epsilon\\}\rightarrow
0.$

###### Proof:

By Lemma 21, $\omega_{i}$ can be written as
$\left<\mathbf{q_{i}},\mathbf{\rho}\right>$ where
$\mathbf{q_{i}}=(q_{i,0},q_{i,1},\cdots,q_{i,r})\in\mathbb{Z}^{r+1}$,
$\mathbf{\rho}=(\frac{1}{s},\rho_{1},\cdots,\rho_{r})\in\mathbb{R}^{r+1}$ and
$s\in\mathbb{N}$. Here,
$(\left<\rho_{1}n\right>,\left<\rho_{2}n\right>,\cdots,\left<\rho_{r}n\right>)$
satisfies Weyl’s criterion. Since $\omega_{i}-\omega_{j}\notin\mathbb{Q}$ for
all $i\neq j$,
$(q_{i,1},q_{i,2},\cdots,q_{i,r})\neq(q_{j,1},q_{j,2},\cdots,q_{j,r})$.

For given $k,N,M\in\mathbb{N}$, and $m_{1},\cdots,m_{r}\in\\{1,\cdots,M\\}$,
define a set $S_{m_{1},\cdots,m_{r}}$ as191919Notice that the definition of
$S_{m_{1},\cdots,m_{r}}$ also depends on $k,N,M$ as well as
$m_{1},\cdots,m_{r}$. However, we omit the dependence on $k,N,M$ in the
definition for simplicity.

$\displaystyle\left\\{n\in\\{1,\cdots,N\\}:\frac{m_{1}-1}{M}\leq\left<\rho_{1}(n+k)\right><\frac{m_{1}}{M},\cdots,\frac{m_{r}-1}{M}\leq\left<\rho_{r}(n+k)\right><\frac{m_{r}}{M}\right\\}.$

Then, for all $k,N,M\in\mathbb{N}$ and $\epsilon>0$, we have the following:

$\displaystyle\sum^{N}_{n=1}\mathbf{1}\\{|\sum^{\mu}_{i=1}a_{i}e^{j2\pi\omega_{i}(n+k)}|<\epsilon\\}$
$\displaystyle=\sum^{N}_{n=1}\sum_{1\leq m_{1}\leq M,\cdots,1\leq m_{r}\leq
M}\mathbf{1}\\{|\sum^{\mu}_{i=1}a_{i}e^{j2\pi\omega_{i}(n+k)}|<\epsilon,n\in
S_{m_{1},\cdots,m_{r}}\\}$ $\displaystyle\leq\sum^{N}_{n=1}\sum_{1\leq
m_{1}\leq M,\cdots,1\leq m_{r}\leq M}\mathbf{1}\\{\min_{n\in
S_{m_{1},\cdots,m_{r}}}|\sum^{\mu}_{i=1}a_{i}e^{j2\pi\omega_{i}(n+k)}|<\epsilon,n\in
S_{m_{1},\cdots,m_{r}}\\}$ $\displaystyle=\sum^{N}_{n=1}\sum_{1\leq m_{1}\leq
M,\cdots,1\leq m_{r}\leq M}\mathbf{1}\\{\min_{n\in
S_{m_{1},\cdots,m_{r}}}|\sum^{\mu}_{i=1}a_{i}e^{j2\pi\omega_{i}(n+k)}|<\epsilon\\}\cdot\mathbf{1}\\{n\in
S_{m_{1},\cdots,m_{r}}\\}.$ (186)

Moreover, we also know by the definitions of $\mathbf{q_{i}}$ and
$\mathbf{\rho}$,

$\displaystyle\sum^{\mu}_{i=1}a_{i}e^{j2\pi\omega_{i}(n+k)}$
$\displaystyle=\sum^{\mu}_{i=1}a_{i}e^{j2\pi\left<\mathbf{q_{i}},\mathbf{\rho}\right>(n+k)}$
$\displaystyle=\sum^{\mu}_{i=1}a_{i}e^{j2\pi\left(\frac{q_{i,0}}{s}(n+k)+q_{i,1}\rho_{1}(n+k)+\cdots+q_{i,r}\rho_{r}(n+k)\right)}$
$\displaystyle=\sum^{\mu}_{i=1}a_{i}e^{j2\pi\left(\frac{q_{i,0}}{s}(n+k)+q_{i,1}\left<\rho_{1}(n+k)\right>+\cdots+q_{i,r}\left<\rho_{r}(n+k)\right>\right)}(\because
q_{i,j}\in\mathbb{Z}).$

Thus, by defining $\mathbf{X_{m_{1},\cdots,m_{r}}}$ as a random vector which
is uniformly distributed over
$[\frac{m_{1}-1}{M},\frac{m_{1}}{M})\times\cdots\times[\frac{m_{r}-1}{M},\frac{m_{r}}{M})$
and $\mathbf{q_{i}^{\prime}}=(q_{i,1},q_{i,2},\cdots,q_{i,r})$,
$\mathbf{\rho^{\prime}}=(\rho_{1},\rho_{2},\cdots,\rho_{r})$, we can conclude

$\displaystyle\max_{n\in
S_{m_{1},\cdots,m_{r}}}|\sum^{\mu}_{i=1}a_{i}e^{j2\pi\omega_{i}(n+k)}|$
$\displaystyle=\max_{n\in
S_{m_{1},\cdots,m_{r}}}|\sum^{\mu}_{i=1}a_{i}e^{j2\pi\left(\frac{q_{i,0}}{s}(n+k)+q_{i,1}\left<\rho_{1}(n+k)\right>+\cdots+q_{i,r}\left<\rho_{r}(n+k)\right>\right)}|$
$\displaystyle\geq|\sum^{\mu}_{i=1}a_{i}e^{j2\pi\left(\frac{q_{i,0}}{s}(n+k)+\left<\mathbf{q_{i}^{\prime}},\mathbf{X_{m_{1},\cdots,m_{r}}}\right>\right)}|\quad
a.e.$ (187)

By (187), (186) can be upper bounded as follows:

$\displaystyle\eqref{eqn:dis:geo1:1}\leq\sum^{N}_{n=1}\sum_{1\leq m_{1}\leq
M,\cdots,1\leq m_{r}\leq M}\mathbb{P}\\{\min_{n\in
S_{m_{1},\cdots,m_{r}}}|\sum^{\mu}_{i=1}a_{i}e^{j2\pi\omega_{i}(n+k)}|-\max_{n\in
S_{m_{1},\cdots,m_{r}}}|\sum^{\mu}_{i=1}a_{i}e^{j2\pi\omega_{i}(n+k)}|$
$\displaystyle+|\sum^{\mu}_{i=1}a_{i}e^{j2\pi\left(\frac{q_{i,0}}{s}(n+k)+\left<\mathbf{q_{i}^{\prime}},\mathbf{X_{m_{1},\cdots,m_{r}}}\right>\right)}|<\epsilon\\}\cdot\mathbf{1}\\{n\in
S_{m_{1},\cdots,m_{r}}\\}$ $\displaystyle=\sum^{N}_{n=1}\sum_{1\leq m_{1}\leq
M,\cdots,1\leq m_{r}\leq M}\mathbb{P}\\{\min_{n\in
S_{m_{1},\cdots,m_{r}}}|\sum^{\mu}_{i=1}a_{i}e^{j2\pi\left(\frac{q_{i,0}}{s}(n+k)+\left<\mathbf{q_{i}^{\prime}},\mathbf{\rho^{\prime}}\right>(n+k)\right)}|-\max_{n\in
S_{m_{1},\cdots,m_{r}}}|\sum^{\mu}_{i=1}a_{i}e^{j2\pi\left(\frac{q_{i,0}}{s}(n+k)+\left<\mathbf{q_{i}^{\prime}},\mathbf{\rho^{\prime}}\right>(n+k)\right)}|$
$\displaystyle+|\sum^{\mu}_{i=1}a_{i}e^{j2\pi\left(\frac{q_{i,0}}{s}(n+k)+\left<\mathbf{q_{i}^{\prime}},\mathbf{X_{m_{1},\cdots,m_{r}}}\right>\right)}|<\epsilon\\}\cdot\mathbf{1}\\{n\in
S_{m_{1},\cdots,m_{r}}\\}$ $\displaystyle\leq\sum^{N}_{n=1}\sum_{1\leq
m_{1}\leq M,\cdots,1\leq m_{r}\leq M}\max_{0\leq
s^{\prime}<s}\mathbb{P}\\{\min_{n\in
S_{m_{1},\cdots,m_{r}}}|\sum^{\mu}_{i=1}a_{i}e^{j2\pi\left(\frac{s^{\prime}}{s}+\left<\mathbf{q_{i}^{\prime}},\mathbf{\rho^{\prime}}\right>(n+k)\right)}|-\max_{n\in
S_{m_{1},\cdots,m_{r}}}|\sum^{\mu}_{i=1}a_{i}e^{j2\pi\left(\frac{s^{\prime}}{s}+\left<\mathbf{q_{i}^{\prime}},\mathbf{\rho^{\prime}}\right>(n+k)\right)}|$
$\displaystyle+|\sum^{\mu}_{i=1}a_{i}e^{j2\pi\left(\frac{s^{\prime}}{s}+\left<\mathbf{q_{i}^{\prime}},\mathbf{X_{m_{1},\cdots,m_{r}}}\right>\right)}|<\epsilon\\}\cdot\mathbf{1}\\{n\in
S_{m_{1},\cdots,m_{r}}\\}$ $\displaystyle\leq\sum^{N}_{n=1}\sum_{1\leq
m_{1}\leq M,\cdots,1\leq m_{r}\leq M}\sum_{0\leq
s^{\prime}<s}\mathbb{P}\\{\min_{n\in
S_{m_{1},\cdots,m_{r}}}|\sum^{\mu}_{i=1}a_{i}e^{j2\pi\left(\frac{s^{\prime}}{s}+\left<\mathbf{q_{i}^{\prime}},\mathbf{\rho^{\prime}}\right>(n+k)\right)}|-\max_{n\in
S_{m_{1},\cdots,m_{r}}}|\sum^{\mu}_{i=1}a_{i}e^{j2\pi\left(\frac{s^{\prime}}{s}+\left<\mathbf{q_{i}^{\prime}},\mathbf{\rho^{\prime}}\right>(n+k)\right)}|$
$\displaystyle+|\sum^{\mu}_{i=1}a_{i}e^{j2\pi\left(\frac{s^{\prime}}{s}+\left<\mathbf{q_{i}^{\prime}},\mathbf{X_{m_{1},\cdots,m_{r}}}\right>\right)}|<\epsilon\\}\cdot\mathbf{1}\\{n\in
S_{m_{1},\cdots,m_{r}}\\}.$ (188)

Here, we have

$\displaystyle\max_{n\in
S_{m_{1},\cdots,m_{r}}}|\sum^{\mu}_{i=1}a_{i}e^{j2\pi\left(\frac{s^{\prime}}{s}+\left<\mathbf{q_{i}^{\prime}},\mathbf{\rho^{\prime}}\right>(n+k)\right)}|$
$\displaystyle=\max_{n\in
S_{m_{1},\cdots,m_{r}}}|\sum^{\mu}_{i=1}a_{i}e^{j2\pi\left(\frac{s^{\prime}}{s}+q_{i,1}\left<\rho_{1}(n+k)\right>+\cdots+q_{i,r}\left<\rho_{r}(n+k)\right>\right)}|(\because
q_{i,j}\in\mathbb{Z})$
$\displaystyle\leq\sup_{0\leq\Delta_{i}<\frac{1}{M}}|\sum^{\mu}_{i=1}a_{i}e^{j2\pi\left(\frac{s^{\prime}}{s}+q_{i,1}\frac{m_{1}-1}{M}+\cdots+q_{i,r}\frac{m_{r}-1}{M}+q_{i,1}\Delta_{1}+\cdots+q_{i,r}\Delta_{r}\right)}|$
$\displaystyle=\sup_{0\leq\Delta_{i}<\frac{1}{M}}|\sum^{\mu}_{i=1}a_{i}e^{j2\pi\left(\frac{s^{\prime}}{s}+q_{i,1}\frac{m_{1}-1}{M}+\cdots+q_{i,r}\frac{m_{r}-1}{M}\right)}+a_{i}e^{j2\pi\left(\frac{s^{\prime}}{s}+q_{i,1}\frac{m_{1}-1}{M}+\cdots+q_{i,r}\frac{m_{r}-1}{M}\right)}$
$\displaystyle\quad(-1+\cos
2\pi(q_{i,1}\Delta_{1}+\cdots+q_{i,r}\Delta_{r})+j\sin
2\pi(q_{i,1}\Delta_{1}+\cdots+q_{i,r}\Delta_{r}))|$
$\displaystyle\leq|\sum^{\mu}_{i=1}a_{i}e^{j2\pi\left(\frac{s^{\prime}}{s}+q_{i,1}\frac{m_{1}-1}{M}+\cdots+q_{i,r}\frac{m_{r}-1}{M}\right)}|$
$\displaystyle+\sum^{\mu}_{i=1}|a_{i}e^{j2\pi\left(\frac{s^{\prime}}{s}+q_{i,1}\frac{m_{1}-1}{M}+\cdots+q_{i,r}\frac{m_{r}-1}{M}\right)}|$
$\displaystyle\cdot(\sup_{0\leq\Delta_{i}<\frac{1}{M}}|-1+\cos
2\pi(q_{i,1}\Delta_{1}+\cdots+q_{i,r}\Delta_{r})|+\sup_{0\leq\Delta_{i}<\frac{1}{M}}|\sin
2\pi(q_{i,1}\Delta_{1}+\cdots+q_{i,r}\Delta_{r})|)$
$\displaystyle\leq|\sum^{\mu}_{i=1}a_{i}e^{j2\pi\left(\frac{s^{\prime}}{s}+q_{i,1}\frac{m_{1}-1}{M}+\cdots+q_{i,r}\frac{m_{r}-1}{M}\right)}|+4\pi\sum^{\mu}_{i=1}|a_{i}|\sup_{0\leq\Delta_{i}<\frac{1}{M}}|q_{i,1}\Delta_{1}+\cdots+q_{i,r}\Delta_{r}|$
(189)
$\displaystyle\leq|\sum^{\mu}_{i=1}a_{i}e^{j2\pi\left(\frac{s^{\prime}}{s}+q_{i,1}\frac{m_{1}-1}{M}+\cdots+q_{i,r}\frac{m_{r}-1}{M}\right)}|+\frac{4\pi\Gamma}{M}\sum^{\mu}_{i=1}\sum^{r}_{j=1}|q_{i,j}|.(\because\mbox{We
assumed }|a_{i}|\leq\Gamma)$

where (189) comes from the fact that $|\sin x|\leq|x|$ and $|-1+\cos
x|\leq|x|$ for all $x\in\mathbb{R}$.

Likewise, we also have

$\displaystyle\min_{n\in
S_{m_{1},\cdots,m_{r}}}|\sum^{\mu}_{i=1}a_{i}e^{j2\pi\left(\frac{s_{i}^{\prime}}{s}+\left<\mathbf{q_{i}^{\prime}},\mathbf{\rho^{\prime}}\right>(n+k)\right)}|$
$\displaystyle\geq|\sum^{\mu}_{i=1}a_{i}e^{j2\pi\left(\frac{s_{i}^{\prime}}{s}+q_{i,1}\frac{m_{1}-1}{M}+\cdots+q_{i,r}\frac{m_{r}-1}{M}\right)}|-\frac{4\pi\Gamma}{M}\sum^{\mu}_{i=1}\sum^{r}_{j=1}|q_{i,j}|.$

Therefore,

$\displaystyle\sup_{\frac{m_{i}-1}{M}\leq{\left<\rho_{i}(n+k)\right>}<\frac{m_{i}}{M}}|\sum^{\mu}_{i=1}a_{i}e^{j2\pi\left(\frac{s_{i}^{\prime}}{s}+\left<\mathbf{q_{i}^{\prime}},\mathbf{\rho^{\prime}}\right>(n+k)\right)}|-\inf_{\frac{m_{i}-1}{M}\leq{\left<\rho_{i}(n+k)\right>}<\frac{m_{i}}{M}}|\sum^{\mu}_{i=1}a_{i}e^{j2\pi\left(\frac{s_{i}^{\prime}}{s}+\left<\mathbf{q_{i}^{\prime}},\mathbf{\rho^{\prime}}\right>(n+k)\right)}|$
$\displaystyle\leq\frac{8\pi\Gamma}{M}\sum^{\mu}_{i=1}\sum^{r}_{j=1}|q_{i,j}|.$

By selecting $M$ such that
$\frac{8\pi\Gamma}{M}\sum^{\mu}_{i=1}\sum^{r}_{j=1}|q_{i,j}|\leq\epsilon$,
(188) is upper bounded by

$\displaystyle\eqref{eqn:dis:geo1:3}\leq\sum^{N}_{n=1}\sum_{1\leq m_{1}\leq
M,\cdots,1\leq m_{r}\leq M}\sum_{0\leq
s^{\prime}<s}\mathbb{P}\\{|\sum^{\mu}_{i=1}a_{i}e^{j2\pi\left(\frac{s^{\prime}}{s}+\left<\mathbf{q_{i}^{\prime}},\mathbf{X_{m_{1},\cdots,m_{r}}}\right>\right)}|<2\epsilon\\}\cdot\mathbf{1}\\{n\in
S_{m_{1},\cdots,m_{r}}\\}.$ (190)

Since $(\left<\rho_{1}n\right>,\cdots,\left<\rho_{k}n\right>)$ satisfies
Weyl’s criterion, by Theorem 12

$\displaystyle\lim_{N\rightarrow\infty}\sup_{k\in\mathbb{Z}}\frac{1}{N}\sum^{N}_{n=1}\mathbf{1}\\{n\in
S_{m_{1},\cdots,m_{r}}\\}=\frac{1}{M^{r}}.$ (191)

Therefore, if we let $\mathbf{X}$ be a $1\times r$ random vector whose
distribution is uniform on $[0,1)^{r}$, by (190) and (191)

$\displaystyle\lim_{N\rightarrow\infty}\sup_{|a_{m}|\geq\gamma,|a_{i}|\leq\Gamma,k\in\mathbb{Z}}\frac{1}{N}\sum^{N}_{n=1}\mathbf{1}\\{|\sum^{\mu}_{i=1}a_{i}e^{j2\pi\omega_{i}(n+k)}|<\epsilon\\}$
$\displaystyle\leq\sup_{|a_{m}|\geq\gamma,|a_{i}|\leq\Gamma,k\in\mathbb{Z}}\sum_{1\leq
m_{1}\leq M,\cdots,1\leq m_{r}\leq M}\sum_{0\leq
s^{\prime}<s}\mathbb{P}\\{|\sum^{\mu}_{i=1}a_{i}e^{j2\pi\left(\frac{s^{\prime}}{s}+\left<\mathbf{q_{i}^{\prime}},\mathbf{X_{m_{1},\cdots,m_{r}}}\right>\right)}|<2\epsilon\\}\cdot\frac{1}{M^{r}}$
(192)
$\displaystyle\leq\sup_{|a_{m}|\geq\gamma,|a_{i}|\leq\Gamma,k\in\mathbb{Z}}\sum_{0\leq
s^{\prime}<s}\mathbb{P}\\{|\sum^{\mu}_{i=1}a_{i}e^{j2\pi\left(\frac{s^{\prime}}{s}+\left<\mathbf{q_{i}^{\prime}},\mathbf{X}\right>\right)}|<2\epsilon\\}(\because\mbox{definitions
of }\mathbf{X_{m_{1},\cdots,m_{r}}},\mathbf{X})$
$\displaystyle\leq\sup_{|a_{m}|\geq\gamma,|a_{i}|\leq\Gamma}s\cdot\mathbb{P}\\{|\sum^{\mu}_{i=1}a_{i}e^{j2\pi\left(\left<\mathbf{q_{i}^{\prime}},\mathbf{X}\right>\right)}|<2\epsilon\\}.(\because
e^{j2\pi\frac{s^{\prime}}{s}}\mbox{ only rotates the phase.})$ (193)

Since $\mathbf{q_{i}^{\prime}}$ are distinct, by Lemma 22, (193) goes to 0 as
$\epsilon\downarrow 0$. ∎

So far, we put the restriction that $|a_{i}|\leq\Gamma$. However, the
functions are growing as $|a_{i}|$ increases. Therefore, Lemma 23 holds even
after we remove such restrictions. The proof is similar to that of Lemma 15.

###### Lemma 24

Let $\omega_{1},\omega_{2},\cdots,\omega_{\mu}$ be real numbers such that
$\omega_{i}-\omega_{j}\notin\mathbb{Q}$ for all $i\neq j$. Then, for strictly
positive numbers $\gamma$, and any $m\in\\{1,\cdots,\mu\\}$

$\displaystyle\lim_{\epsilon\downarrow
0}\lim_{N\rightarrow\infty}\sup_{|a_{m}|\geq\gamma,a_{i}\in\mathbb{C},k\in\mathbb{Z}}\frac{1}{N}\sum^{N}_{n=1}\mathbf{1}\\{|\sum^{\mu}_{i=1}a_{i}e^{j2\pi\omega_{i}(n+k)}|<\epsilon\\}\rightarrow
0.$

###### Proof:

The proof is by induction on $\mu$, the number of terms in the inner sum.

(i) When $\mu=1$.

Denote $a^{\prime}_{1}$ as $\gamma\frac{a_{1}}{|a_{1}|}$. Then,

$\displaystyle\lim_{N\rightarrow\infty}\sup_{|a_{1}|\geq\gamma,k\in\mathbb{Z}}\frac{1}{N}\sum^{N}_{n=1}\mathbf{1}\\{|a_{1}e^{j2\pi\omega_{1}(n+k)}|<\epsilon\\}$
(194)
$\displaystyle=\lim_{N\rightarrow\infty}\sup_{|a_{1}|\geq\gamma,k\in\mathbb{Z}}\frac{1}{N}\sum^{N}_{n=1}\mathbf{1}\\{|\frac{\gamma}{|a_{1}|}a_{1}e^{j2\pi\omega_{1}(n+k)}|<\frac{\gamma}{|a_{1}|}\epsilon\\}$
$\displaystyle\leq\lim_{N\rightarrow\infty}\sup_{|a^{\prime}_{1}|=1,k\in\mathbb{Z}}\frac{1}{N}\sum^{N}_{n=1}\mathbf{1}\\{|a^{\prime}_{1}e^{j2\pi\omega_{1}(n+k)}|<\epsilon\\}(\because\frac{\gamma}{|a_{1}|}\leq
1)$ (195)

By Lemma 23, (195) converges to $0$ as $\epsilon\downarrow 0$. Thus, (194)
converges to $0$ as $\epsilon\downarrow 0$.

(ii) As an induction hypothesis, we assume the lemma is true until $\mu-1$.

To prove the lemma for $\mu$, it is enough to show that for all $\delta>0$
there exists $\epsilon(\delta)>0$ such that

$\displaystyle\lim_{N\rightarrow\infty}\sup_{|a_{m}|\geq\gamma,k\in\mathbb{Z}}\frac{1}{N}\sum^{N}_{n=1}\mathbf{1}\\{|\sum^{\mu}_{i=1}a_{i}e^{j2\pi\omega_{i}(n+k)}|<\epsilon(\delta)\\}<\delta.$

By the induction hypothesis, for all $m^{\prime}\neq m$ we can find
$\epsilon_{m^{\prime}}(\delta)>0$ such that

$\displaystyle\lim_{N\rightarrow\infty}\sup_{|a_{m^{\prime}}|\geq\gamma,k\in\mathbb{Z}}\frac{1}{N}\sum^{N}_{n=1}\mathbf{1}\\{|\sum_{1\leq
i\leq\mu,i\neq
m}a_{i}e^{j2\pi\omega_{i}(n+k)}|<\epsilon_{m^{\prime}}(\delta)\\}<\delta.$
(196)

Let $\kappa(\delta):=\min\left\\{\min_{m^{\prime}\neq
m}\left\\{\frac{\epsilon_{m^{\prime}}(\delta)}{2\gamma}\right\\},1\right\\}$.
By Lemma 23, there exists $\epsilon^{\prime}(\delta)>0$ such that

$\displaystyle\lim_{N\rightarrow\infty}\sup_{|a_{m}|\geq\gamma,|a_{i}|\leq\frac{\gamma}{\kappa(\delta)},k\in\mathbb{Z}}\frac{1}{N}\sum^{N}_{n=1}\mathbf{1}\\{|\sum^{\mu}_{i=1}a_{i}e^{j2\pi\omega_{i}(n+k)}|<\epsilon^{\prime}(\delta)\\}<\delta.$
(197)

Set
$\epsilon(\delta):=\min\left\\{\epsilon^{\prime}(\delta),\min_{m^{\prime}\neq
m}\left\\{\frac{\epsilon_{m^{\prime}}(\delta)}{2}\right\\}\right\\}$. Then, we
have

$\displaystyle\lim_{N\rightarrow\infty}\sup_{|a_{m}|\geq\gamma,k\in\mathbb{Z}}\frac{1}{N}\sum^{N}_{n=1}\mathbf{1}\\{|\sum^{\mu}_{i=1}a_{i}e^{j2\pi\omega_{i}(n+k)}|<\epsilon(\delta)\\}$
$\displaystyle\leq\lim_{N\rightarrow\infty}\max\\{\sup_{|a_{m}|\geq\gamma,\frac{|a_{i}|}{|a_{m}|}\leq\frac{1}{\kappa(\delta)},k\in\mathbb{Z}}\frac{1}{N}\sum^{N}_{n=1}\mathbf{1}\\{|\sum^{\mu}_{i=1}a_{i}e^{j2\pi\omega_{i}(n+k)}|<\epsilon({\delta})\\},$
$\displaystyle\max_{m^{\prime}\neq
m}\sup_{|a_{m}|\geq\gamma,\frac{|a_{m^{\prime}}|}{|a_{m}|}\geq\frac{1}{\kappa(\delta)},k\in\mathbb{Z}}\frac{1}{N}\sum^{N}_{n=1}\mathbf{1}\\{|\sum^{\mu}_{i=1}a_{i}e^{j2\pi\omega_{i}(n+k)}|<\epsilon(\delta)\\}\\}$
$\displaystyle=\max\\{\lim_{N\rightarrow\infty}\sup_{|a_{m}|\geq\gamma,\frac{|a_{i}|}{|a_{m}|}\leq\frac{1}{\kappa(\delta)},k\in\mathbb{Z}}\frac{1}{N}\sum^{N}_{n=1}\mathbf{1}\\{|\sum^{\mu}_{i=1}a_{i}e^{j2\pi\omega_{i}(n+k)}|<\epsilon({\delta})\\},$
$\displaystyle\max_{m^{\prime}\neq
m}\lim_{N\rightarrow\infty}\sup_{|a_{m}|\geq\gamma,\frac{|a_{m^{\prime}}|}{|a_{m}|}\geq\frac{1}{\kappa(\delta)},k\in\mathbb{Z}}\frac{1}{N}\sum^{N}_{n=1}\mathbf{1}\\{|\sum^{\mu}_{i=1}a_{i}e^{j2\pi\omega_{i}(n+k)}|<\epsilon(\delta)\\}\\}.$
(198)

Let $a^{\prime}_{i}:=\frac{\gamma}{|a_{m}|}a_{i}$. Then, the first term in
(198) is upper bounded by

$\displaystyle\lim_{N\rightarrow\infty}\sup_{|a_{m}|\geq\gamma,\frac{|a_{i}|}{|a_{m}|}\leq\frac{1}{\kappa(\delta)},k\in\mathbb{Z}}\frac{1}{N}\sum^{N}_{n=1}\mathbf{1}\\{|\sum^{\mu}_{i=1}a_{i}e^{j2\pi\omega_{i}(n+k)}|<\epsilon({\delta})\\}$
$\displaystyle=\lim_{N\rightarrow\infty}\sup_{|a_{m}|\geq\gamma,\frac{|a_{i}|}{|a_{m}|}\leq\frac{1}{\kappa(\delta)},k\in\mathbb{Z}}\frac{1}{N}\sum^{N}_{n=1}\mathbf{1}\\{|\sum^{\mu}_{i=1}\frac{\gamma}{|a_{m}|}a_{i}e^{j2\pi\omega_{i}(n+k)}|<\frac{\gamma}{|a_{m}|}\epsilon({\delta})\\}$
$\displaystyle=\lim_{N\rightarrow\infty}\sup_{|a^{\prime}_{m}|=\gamma,|a^{\prime}_{i}|\leq\frac{\gamma}{\kappa(\delta)},k\in\mathbb{Z}}\frac{1}{N}\sum^{N}_{n=1}\mathbf{1}\\{|\sum^{\mu}_{i=1}a^{\prime}_{i}e^{j2\pi\omega_{i}(n+k)}|<\frac{\gamma}{|a_{m}|}\epsilon({\delta})\\}$
$\displaystyle\leq\lim_{N\rightarrow\infty}\sup_{|a^{\prime}_{m}|=\gamma,|a^{\prime}_{i}|\leq\frac{\gamma}{\kappa(\delta)},k\in\mathbb{Z}}\frac{1}{N}\sum^{N}_{n=1}\mathbf{1}\\{|\sum^{\mu}_{i=1}a^{\prime}_{i}e^{j2\pi\omega_{i}(n+k)}|<\epsilon({\delta})\\}(\because\frac{\gamma}{|a_{m}|}\leq
1)$
$\displaystyle\leq\lim_{N\rightarrow\infty}\sup_{|a^{\prime}_{m}|=\gamma,|a^{\prime}_{i}|\leq\frac{\gamma}{\kappa(\delta)},k\in\mathbb{Z}}\frac{1}{N}\sum^{N}_{n=1}\mathbf{1}\\{|\sum^{\mu}_{i=1}a^{\prime}_{i}e^{j2\pi\omega_{i}(n+k)}|<\epsilon^{\prime}(\delta)\\}(\because\epsilon^{\prime}\geq\epsilon)$
$\displaystyle<\delta.(\because\eqref{eqn:limmax2})$ (199)

Let $a^{\prime\prime}_{i}:=\frac{\gamma}{|a_{m^{\prime}}|}a_{i}$. Then, the
second term in (198) is upper bounded by

$\displaystyle\lim_{N\rightarrow\infty}\sup_{|a_{m}|\geq\gamma,\frac{|a_{m^{\prime}}|}{|a_{m}|}\geq\frac{1}{\kappa(\delta)},k\in\mathbb{Z}}\frac{1}{N}\sum^{N}_{n=1}\mathbf{1}\\{|\sum^{\mu}_{i=1}a_{i}e^{j2\pi\omega_{i}(n+k)}|<\epsilon({\delta})\\}$
$\displaystyle=\lim_{N\rightarrow\infty}\sup_{|a_{m}|\geq\gamma,\frac{|a_{m^{\prime}}|}{|a_{m}|}\geq\frac{1}{\kappa(\delta)},k\in\mathbb{Z}}\frac{1}{N}\sum^{N}_{n=1}\mathbf{1}\\{|\sum^{\mu}_{i=1}\frac{\gamma}{|a_{m^{\prime}}|}a_{i}e^{j2\pi\omega_{i}(n+k)}|<\frac{\gamma}{|a_{m^{\prime}}|}\epsilon({\delta})\\}$
$\displaystyle\leq\lim_{N\rightarrow\infty}\sup_{|a_{m}|\geq\gamma,\frac{|a_{m^{\prime}}|}{|a_{m}|}\geq\frac{1}{\kappa(\delta)},k\in\mathbb{Z}}\frac{1}{N}\sum^{N}_{n=1}\mathbf{1}\\{|\sum^{\mu}_{i=1}\frac{\gamma}{|a_{m^{\prime}}|}a_{i}e^{j2\pi\omega_{i}(n+k)}-\frac{\gamma}{|a_{m^{\prime}}|}a_{m}e^{j2\pi\omega_{m}(n+k)}|<\frac{\gamma}{|a_{m^{\prime}}|}\epsilon({\delta})+\frac{\gamma}{|a_{m^{\prime}}|}|a_{m}|\\}$
$\displaystyle\leq\lim_{N\rightarrow\infty}\sup_{|a_{m}|\geq\gamma,\frac{|a_{m^{\prime}}|}{|a_{m}|}\geq\frac{1}{\kappa(\delta)},k\in\mathbb{Z}}\frac{1}{N}\sum^{N}_{n=1}\mathbf{1}\\{|\sum^{\mu}_{i=1}\frac{\gamma}{|a_{m^{\prime}}|}a_{i}e^{j2\pi\omega_{i}(n+k)}-\frac{\gamma}{|a_{m^{\prime}}|}a_{m}e^{j2\pi\omega_{m}(n+k)}|<\epsilon_{m^{\prime}}(\delta)\\}$
(200)
$\displaystyle\leq\lim_{N\rightarrow\infty}\sup_{|a_{m^{\prime}}^{\prime\prime}|=\gamma,k\in\mathbb{Z}}\frac{1}{N}\sum^{N}_{n=1}\mathbf{1}\\{|\sum_{1\leq
i\leq\mu,i\neq
m}a_{i}^{\prime\prime}e^{j2\pi\omega_{i}(n+k)}|<\epsilon_{m^{\prime}}(\delta)\\}(\because\mbox{definition
of }a_{i}^{\prime\prime})$
$\displaystyle<\delta.(\because\eqref{eqn:limmax3})$ (201)

Here, (200) is justified as follows:

$\displaystyle\frac{\gamma}{|a_{m}^{\prime}|}\epsilon(\delta)+\frac{\gamma}{|a_{m}^{\prime}|}|a_{m}|$
(202)
$\displaystyle\leq\frac{\gamma}{|a_{m}|}\epsilon(\delta)+\gamma\kappa(\delta)(\because\frac{|a_{m^{\prime}}|}{|a_{m}|}\geq\frac{1}{\kappa(\delta)}\mbox{,
and by definition }\kappa(\delta)\leq 1)$ (203)
$\displaystyle\leq\epsilon(\delta)+\gamma\kappa(\delta)(\because|a_{m}|\geq\gamma)$
(204)
$\displaystyle\leq\frac{\epsilon_{m^{\prime}}(\delta)}{2}+\frac{\epsilon_{m^{\prime}}(\delta)}{2}.(\because\mbox{definitions
of }\epsilon(\delta),\kappa(\delta))$ (205)

Therefore, by plugging (199) and (201) into (198),we get

$\displaystyle\lim_{N\rightarrow\infty}\sup_{|a_{m}|\geq\gamma,k\in\mathbb{Z}}\frac{1}{N}\sum^{N}_{n=1}\mathbf{1}\\{|\sum^{\mu}_{i=1}a_{i}e^{j2\pi\omega_{i}(n+k)}|<\epsilon(\delta)\\}<\delta,$

which finishes the proof. ∎

Now, we will generalize Lemma 24 by introducing polynomial terms. First, we
prove that a set of polynomials is uniformly bounded away from $0$ when there
is nonzero coefficient.

###### Lemma 25

For all $n\in\mathbb{N}$, $n^{\prime}\in\mathbb{Z}^{+}$,
$m\in\\{1,\cdots,n\\}$, $\gamma>0$ and $k>0$,

$\displaystyle\lim_{T\rightarrow\infty}\sup_{|a_{m}|\geq\gamma,a_{i}\in\mathbb{C}}\frac{|\\{x\in(0,T]:|\sum^{n}_{i=-n^{\prime}}a_{i}x^{i}|<k\\}|_{\mathbb{L}}}{T}=0$

where $|\cdot|_{\mathbb{L}}$ is the Lebesgue measure of the set.

###### Proof:

Let $X$ be a uniform random variable on $(0,1]$. Then, we have

$\displaystyle\sup_{|a_{m}|\geq\gamma}\frac{|\\{x\in(0,T]:|\sum^{n}_{i=-n^{\prime}}a_{i}x^{i}|<k\\}|_{\mathbb{L}}}{T}$
$\displaystyle=\sup_{|a_{m}|\geq\gamma}\frac{|\\{x\in(0,T]:|\sum^{n}_{i=-n^{\prime}}a_{i}\frac{x^{i}}{T^{m}}|<\frac{k}{T^{m}}\\}|_{\mathbb{L}}}{T}$
$\displaystyle=\sup_{|a_{m}|\geq\gamma}\frac{|\\{x\in(0,T]:|\sum^{n}_{i=-n^{\prime}}a_{i}\left(\frac{x}{T}\right)^{i}|<\frac{k}{T^{m}}\\}|_{\mathbb{L}}}{T}$
$\displaystyle=\sup_{|a_{m}|\geq\gamma}|\\{x\in(0,1]:|\sum^{n}_{i=-n^{\prime}}a_{i}x^{i}|<\frac{k}{T^{m}}\\}|_{\mathbb{L}}$
$\displaystyle=\sup_{|a_{m}|\geq\gamma}\mathbb{P}\\{|\sum^{n}_{i=-n^{\prime}}a_{i}X^{i}|<\frac{k}{T^{m}}\\}$
$\displaystyle=\sup_{|a_{m+n^{\prime}}|\geq\gamma}\mathbb{P}\\{|\sum^{n+n^{\prime}}_{i=0}a_{i}X^{i}|<\frac{kX^{n^{\prime}}}{T^{m}}\\}$
$\displaystyle\leq\sup_{|a_{m+n^{\prime}}|\geq\gamma}\mathbb{P}\\{|\sum^{n+n^{\prime}}_{i=0}a_{i}X^{i}|<\frac{k}{T^{m}}\\}.(\because
0<X\leq 1\mbox{ w.p. 1})$

Therefore, by Lemma 15

$\displaystyle\lim_{T\rightarrow\infty}\sup_{|a_{m}|\geq\gamma,a_{i}\in\mathbb{C}}\frac{|\\{x\in[0,T]:|\sum^{n}_{i=-n^{\prime}}a_{i}x^{i}|<k\\}|_{\mathbb{L}}}{T}$
$\displaystyle=\lim_{T\rightarrow\infty}\sup_{|a_{m+n^{\prime}}|\geq\gamma,a_{i}\in\mathbb{C}}\mathbb{P}\\{|\sum^{n+n^{\prime}}_{i=0}a_{i}X^{i}|<\frac{k}{T^{m}}\\}=0,$

which finishes the proof. ∎

The following lemma shows that the above lemma still holds even if we change
Lebesgue measure to counting measure.

###### Lemma 26

For all $n\in\mathbb{N}$, $n^{\prime}\in\mathbb{Z}^{+}$,
$m\in\\{1,\cdots,n\\}$, $\gamma>0$ and $k>0$,

$\displaystyle\lim_{N\rightarrow\infty}\sup_{|a_{m}|\geq\gamma,a_{i}\in\mathbb{C}}\frac{|\\{x\in\\{1,\cdots,N\\}:|\sum^{n}_{i=-n^{\prime}}a_{i}x^{i}|<k\\}|_{\mathbb{C}}}{N}=0$

where $|\cdot|_{\mathbb{C}}$ implies the counting measure of the set, the
cardinality of the set.

###### Proof:

First, we will prove the following claim which relates Lebesgue measure with
counting measure.

###### Claim 4

Let $f:\mathbb{R^{+}}\rightarrow\mathbb{R}$ be a $\mathcal{C}^{\infty}$
function with $l$ local maxima and minima. Then,

$\displaystyle\left|\left\\{x\in[1,N]:f(x)>0\right\\}\right|_{\mathbb{L}}\leq\left|\left\\{x\in\\{1,\cdots,N\\}:f(x)>0\right\\}\right|_{\mathbb{C}}+3l+2.$

###### Proof:

Since $f(x)$ is a continuous function with $l$ local maxima and minima, we can
prove that there exist $l^{\prime}\leq l+1$, $s_{i}$ and $t_{i}$ $(1\leq i\leq
l^{\prime})$ such that

$\displaystyle\left\\{x\in\\{1,\cdots,N\\}:f(x)>0\right\\}=\\{s_{1},s_{1}+1,\cdots,s_{1}+t_{1}\\}\cup\cdots\cup\\{s_{l^{\prime}},s_{l^{\prime}}+1,\cdots,s_{l^{\prime}}+t_{l^{\prime}}\\}.$

One way to justify this is by contradiction, i.e. if we assume
$l^{\prime}>l+1$, there should exist more than $l$ local maxima and minima by
the mean value theorem. Moreover, since the number of local maxima and minima
is bounded by $l$, we have

$\displaystyle\left|\left\\{x\in[1,N]:f(x)>0\right\\}\right|_{\mathbb{L}}$
$\displaystyle\leq\left|[s_{1}-1,s_{1}+t_{1}+1]\right|_{\mathbb{L}}+\cdots+\left|[s_{l^{\prime}}-1,s_{l^{\prime}}+t_{l^{\prime}}+1]\right|_{\mathbb{L}}+l$
$\displaystyle\leq(t_{1}+2)+\cdots+(t_{l^{\prime}}+2)+l$
$\displaystyle\leq\left|\left\\{x\in\\{1,\cdots,N\\}:f(x)>0\right\\}\right|_{\mathbb{C}}+2l^{\prime}+l$
$\displaystyle\leq\left|\left\\{x\in\\{1,\cdots,N\\}:f(x)>0\right\\}\right|_{\mathbb{C}}+3l+2.$

Thus, the claim is true. ∎

To prove the lemma, let $a_{i}=a_{R,i}+ja_{I,i}$ where
$a_{R,i},a_{I,i}\in\mathbb{R}$. Then,

$\displaystyle|\sum^{n}_{i=-n^{\prime}}a_{i}x^{i}|<k$ (207)
$\displaystyle(\Leftrightarrow)|\sum^{n+n^{\prime}}_{i=0}a_{i-n^{\prime}}x^{i}|<kx^{n^{\prime}}$
(208)
$\displaystyle(\Leftrightarrow)(\sum^{n+n^{\prime}}_{i=0}a_{R,i-n^{\prime}}x^{i})^{2}+(\sum^{n+n^{\prime}}_{i=0}a_{I,i-n^{\prime}}x^{i})^{2}<k^{2}x^{n^{\prime}}.$
(209)

Since
$k^{2}x^{2n^{\prime}}-(\sum^{n+n^{\prime}}_{i=0}a_{R,i-n^{\prime}}x^{i})^{2}-(\sum^{n+n^{\prime}}_{i=0}a_{I,i-n^{\prime}}x^{i})^{2}$
is a continuous function with at most $2(n+n^{\prime})$ local maxima and
minima, by the claim we have

$\displaystyle\lim_{N\rightarrow\infty}\sup_{|a_{m}|\geq\gamma,a_{i}\in\mathbb{C}}\frac{|\\{x\in\\{1,\cdots,N\\}:|\sum^{n}_{i=0}a_{i}x^{i}|<k\\}|_{\mathbb{C}}}{N}$
$\displaystyle\leq\lim_{N\rightarrow\infty}\sup_{|a_{m}|\geq\gamma,a_{i}\in\mathbb{C}}\frac{|\\{x\in[1,N]:|\sum^{n}_{i=0}a_{i}x^{i}|<k\\}|_{\mathbb{L}}+6(n+n^{\prime})+2}{N}$
$\displaystyle=\lim_{N\rightarrow\infty}\sup_{|a_{m}|\geq\gamma,a_{i}\in\mathbb{C}}\frac{|\\{x\in(0,N]:|\sum^{n}_{i=0}a_{i}x^{i}|<k\\}|_{\mathbb{L}}}{N}=0\
(\because Lemma~{}\ref{lem:dis:leb})$

Therefore, the lemma is proved. ∎

Now, we merge Lemma 26 with Lemma 24 to prove that Lemma 27 still holds even
after we introduce polynomial terms to the functions.

###### Lemma 27

Let $\omega_{1},\omega_{2},\cdots,\omega_{\mu}$ be real numbers such that
$\omega_{i}-\omega_{j}\notin\mathbb{Q}$ for all $i\neq j$. Then, for strictly
positive numbers $\gamma$,

$\displaystyle\lim_{\epsilon\downarrow
0}\lim_{N\rightarrow\infty}\sup_{|a_{1\nu_{1}}|\geq\gamma,a_{ij}\in\mathbb{C},k\in\mathbb{Z}}\frac{1}{N}\sum^{N}_{n=1}\mathbf{1}\left\\{\left|\sum^{\mu}_{i=1}\left(\sum^{\nu_{i}}_{j=0}a_{ij}n^{j}\right)e^{j2\pi\omega_{i}(n+k)}\right|<\epsilon\right\\}\rightarrow
0.$

###### Proof:

To prove the lemma, it is enough to show that for all $\delta>0$, there exist
$\epsilon>0$ and $N\in\mathbb{N}$ such that

$\displaystyle\sup_{|a_{1\nu_{1}}|\geq\gamma,a_{ij}\in\mathbb{C},k\in\mathbb{Z}}\frac{1}{N}\sum^{N}_{n=1}\mathbf{1}\left\\{\left|\sum^{\mu}_{i=1}\left(\sum^{\nu_{i}}_{j=0}a_{ij}n^{j}\right)e^{j2\pi\omega_{i}(n+k)}\right|<\epsilon\right\\}<\delta.$
(210)

Since $\mu$ is finite, by Lemma 24, there exist $\epsilon^{\prime}>0$ and
$M\in\mathbb{N}$ such that

$\displaystyle\max_{d\in\\{1,\cdots,\mu\\}}\left(\sup_{k\in\mathbb{Z},a_{i}\in\mathbb{C},|a_{d}|\geq
1}\frac{1}{M}\sum_{c=1}^{M}\mathbf{1}\left\\{\left|\sum^{\mu}_{i=1}a_{i}e^{j2\pi\omega_{i}(c+k)}\right|<\epsilon^{\prime}\right\\}\right)<\frac{\delta}{2}.$
(211)

By Lemma 26, there exists $B^{\prime}\in\mathbb{N}$ such that

$\displaystyle\sup_{|a_{1\nu_{1}}^{\prime}|\geq\gamma}\frac{\left|\left\\{b\in\\{1,\cdots,B^{\prime}\\}:\left|\sum^{\nu_{1}}_{j=0}a_{1j}^{\prime}b^{j}\right|\leq
2\right\\}\right|_{\mathbb{C}}}{B^{\prime}}<\frac{\delta}{4}.$ (212)

Define
$\kappa^{\prime}:=\frac{2\sum^{\mu}_{i=1}\sum^{\nu_{i}}_{j=1}\sum^{j}_{k=1}{{j}\choose{k}}}{\epsilon^{\prime}}$.
By Lemma 26, there exists $B^{\prime\prime}\in\mathbb{N}$ such that

$\displaystyle\sum_{1\leq i\leq\mu,1\leq j\leq\nu_{i},1\leq k\leq
j}\sup_{|a_{k}|=1}\frac{|\\{b\in\\{1,\cdots,B^{\prime\prime}\\}:\kappa^{\prime}\geq|\sum^{\nu_{i}-j+k}_{j^{\prime}=-j+k}a_{j^{\prime}}b^{j^{\prime}}|\\}|_{\mathbb{C}}}{B^{\prime\prime}}<\frac{\delta}{4}.$
(213)

Define $B:=\max(B^{\prime},B^{\prime\prime})$. We will show that the choice of
$\epsilon=\epsilon^{\prime}$ and $N=M\cdot B$ satisfies (210).

$\displaystyle\sup_{|a_{1\nu_{1}}|\geq\gamma,a_{ij}\in\mathbb{C},k\in\mathbb{Z}}\frac{1}{N}\sum^{N}_{n=1}\mathbf{1}\left\\{\left|\sum^{\mu}_{i=1}\left(\sum^{\nu_{i}}_{j=0}a_{ij}n^{j}\right)e^{j2\pi\omega_{i}(n+k)}\right|<\epsilon\right\\}$
$\displaystyle=\sup_{|a_{1\nu_{1}}|\geq\gamma,a_{ij}\in\mathbb{C}}\frac{1}{N}\sum^{N}_{n=1}\mathbf{1}\left\\{\left|\sum^{\mu}_{i=1}\left(\sum^{\nu_{i}}_{j=0}a_{ij}n^{j}\right)e^{j2\pi\omega_{i}n}\right|<\epsilon\right\\}(\because
e^{j2\pi\omega_{i}k}\mbox{ can be absorbed into the $a_{ij}$.})$
$\displaystyle=\sup_{|a_{1\nu_{1}}|\geq\gamma,a_{ij}\in\mathbb{C}}\frac{1}{B\cdot
M}\sum^{B-1}_{b=0}\sum^{M}_{c=1}\mathbf{1}\left\\{\left|\sum^{\mu}_{i=1}\left(\sum^{\nu_{i}}_{j=0}a_{ij}(bM+c)^{j}\right)e^{j2\pi\omega_{i}(bM+c)}\right|<\epsilon\right\\}(\because
n\mbox{ is rewritten as $bM+c$.})$
$\displaystyle=\sup_{|a_{1\nu_{1}}|\geq\gamma,a_{ij}\in\mathbb{C}}\frac{1}{B\cdot
M}\sum^{B-1}_{b=0}\sum^{M}_{c=1}\mathbf{1}\left\\{\left|\sum^{\mu}_{i=1}\left(\sum^{\nu_{i}}_{j=0}a_{ij}\left((bM)^{j}+\sum^{j}_{k=1}{{j}\choose{k}}(bM)^{j-k}c^{k}\right)\right)e^{j2\pi\omega_{i}(bM+c)}\right|<\epsilon\right\\}$
$\displaystyle\leq\sup_{|a_{1\nu_{1}}|\geq\gamma,a_{ij}\in\mathbb{C}}\frac{1}{B\cdot
M}\sum^{B-1}_{b=0}\sum^{M}_{c=1}\mathbf{1}\left\\{\left|\sum^{\mu}_{i=1}\left(\sum^{\nu_{i}}_{j=0}a_{ij}(bM)^{j}\right)e^{j2\pi\omega_{i}(bM+c)}\right|<\epsilon+\sum^{\mu}_{i=1}\sum^{\nu_{i}}_{j=1}|a_{ij}|\sum^{j}_{k=1}{{j}\choose{k}}(bM)^{j-k}c^{k}\right\\}$
$\displaystyle\leq\sup_{|a_{1\nu_{1}}|\geq\gamma,a_{ij}\in\mathbb{C}}\frac{1}{B\cdot
M}\sum^{B-1}_{b=0}\sum^{M}_{c=1}\mathbf{1}\left\\{\left|\sum^{\mu}_{i=1}\left(\sum^{\nu_{i}}_{j=0}a_{ij}(bM)^{j}\right)e^{j2\pi\omega_{i}(bM+c)}\right|<\epsilon+\sum^{\mu}_{i=1}\sum^{\nu_{i}}_{j=1}\sum^{j}_{k=1}|a_{ij}|{{j}\choose{k}}(bM)^{j-k}M^{k}\right\\}$
(214)
$\displaystyle\leq\sup_{|a_{1\nu_{1}}|\geq\gamma,a_{ij}\in\mathbb{C}}\frac{1}{B\cdot
M}\sum^{B-1}_{b=0}\sum^{M}_{c=1}\mathbf{1}\Bigg{\\{}\left|\sum^{\mu}_{i=1}\left(\frac{\sum^{\nu_{i}}_{j=0}a_{ij}(bM)^{j}}{M_{b}}\right)e^{j2\pi\omega_{i}(bM+c)}\right|<$
$\displaystyle\frac{\epsilon}{M_{b}}+\frac{\sum^{\mu}_{i=1}\sum^{\nu_{i}}_{j=1}\sum^{j}_{k=1}|a_{ij}|{{j}\choose{k}}(bM)^{j-k}M^{k}}{M_{b}}\Bigg{\\}}$
$\displaystyle\leq\sup_{|a_{1\nu_{1}}|\geq\gamma,a_{ij}\in\mathbb{C}}\frac{1}{B}\sum^{B-1}_{b=0}\Bigg{\\{}\frac{1}{M}\sum^{M}_{c=1}\mathbf{1}\Bigg{\\{}\left|\sum^{\mu}_{i=1}\left(\frac{\sum^{\nu_{i}}_{j=0}a_{ij}(bM)^{j}}{M_{b}}\right)e^{j2\pi\omega_{i}(bM+c)}\right|<\epsilon\Bigg{\\}}$
$\displaystyle+\mathbf{1}\Bigg{\\{}\frac{\epsilon}{M_{b}}+\frac{\sum^{\mu}_{i=1}\sum^{\nu_{i}}_{j=1}\sum^{j}_{k=1}|a_{ij}|{{j}\choose{k}}(bM)^{j-k}M^{k}}{M_{b}}\geq\epsilon\Bigg{\\}}\Bigg{\\}}$
$\displaystyle\leq\sup_{|a_{1\nu_{1}}|\geq\gamma,a_{ij}\in\mathbb{C}}\frac{1}{B}\sum^{B-1}_{b=0}\Bigg{\\{}\frac{1}{M}\sum^{M}_{c=1}\mathbf{1}\Bigg{\\{}\left|\sum^{\mu}_{i=1}\left(\frac{\sum^{\nu_{i}}_{j=0}a_{ij}(bM)^{j}}{M_{b}}\right)e^{j2\pi\omega_{i}(bM+c)}\right|<\epsilon\Bigg{\\}}$
$\displaystyle+\mathbf{1}\Bigg{\\{}\frac{\epsilon}{M_{b}}\geq\frac{\epsilon}{2}\Bigg{\\}}+\mathbf{1}\Bigg{\\{}\frac{\sum^{\mu}_{i=1}\sum^{\nu_{i}}_{j=1}\sum^{j}_{k=1}|a_{ij}|{{j}\choose{k}}(bM)^{j-k}M^{k}}{M_{b}}\geq\frac{\epsilon}{2}\Bigg{\\}}\Bigg{\\}}$
(215)

where
$M_{b}:=\max_{i}\left\\{\left|\sum^{\nu_{i}}_{j=0}a_{ij}\left(bM\right)^{j}\right|\right\\}$
and when $M_{b}=0$ the value of the indicator function is set to be $0$ since
in this case, the indicator function of (214) is already $0$.

First, let’s prove that the first term of (215) is small enough. For all
$a_{ij}\in\mathbb{C}$ such that $|a_{1\nu_{1}}|\geq\gamma$ and
$b\in\\{0,\cdots,B\\}$, we have

$\displaystyle\frac{1}{M}\sum^{M}_{c=1}\mathbf{1}\Bigg{\\{}\left|\sum^{\mu}_{i=1}\left(\frac{\sum^{\nu_{i}}_{j=0}a_{ij}(bM)^{j}}{M_{b}}\right)e^{j2\pi\omega_{i}(bM+c)}\right|<\epsilon\Bigg{\\}}$
(216)
$\displaystyle\leq\max_{d\in\\{1,\cdots,\mu\\}}\left(\sup_{k\in\mathbb{Z},a_{i}\in\mathbb{C},|a_{d}|\geq
1}\frac{1}{M}\sum_{c=1}^{M}\mathbf{1}\left\\{\left|\sum^{\mu}_{i=1}a_{i}e^{j\omega_{i}(c+k)}\right|<\epsilon\right\\}\right)$
(217) $\displaystyle(\because\mbox{By the definition of $M_{b}$,
$\left|\frac{\sum^{\nu_{i}}_{j=0}a_{ij}(bM)^{j}}{M_{b}}\right|=1$ for some
$i$})$ (218)
$\displaystyle<\frac{\delta}{2}.(\because\eqref{eqn:dis:target2})$ (219)

Let’s prove that the second term of (215) is small enough.

$\displaystyle\sup_{|a_{1\nu_{1}}|\geq\gamma}\frac{\left|\left\\{b\in\\{1,\cdots,B\\}:M_{b}<2\right\\}\right|_{\mathbb{C}}}{B}$
$\displaystyle\leq\sup_{|a_{1\nu_{1}}|\geq\gamma}\frac{\left|\left\\{b\in\\{1,\cdots,B\\}:\left|\sum^{\nu_{1}}_{j=0}a_{1j}(bM)^{j}\right|<2\right\\}\right|_{\mathbb{C}}}{B}(\because\mbox{definition
of $M_{b}$})$
$\displaystyle\leq\sup_{|a_{1\nu_{1}}^{\prime}|\geq\gamma}\frac{\left|\left\\{b\in\\{1,\cdots,B\\}:\left|\sum^{\nu_{1}}_{j=0}a_{1j}^{\prime}b^{j}\right|<2\right\\}\right|_{\mathbb{C}}}{B}(\because\mbox{putting
$a_{1j}^{\prime}:=a_{1j}M^{j}$ and $M$ goes to infinity.})$
$\displaystyle<\frac{\delta}{4}.(\because\eqref{eqn:dis:target3})$ (220)

Now, we will prove that the third term of (215) is small enough.

$\displaystyle\sup_{|a_{1\nu_{1}}|\geq\gamma,a_{ij}\in\mathbb{C}}\frac{1}{B}\sum_{b=0}^{B-1}\mathbf{1}\Bigg{\\{}\frac{\sum^{\mu}_{i=1}\sum^{\nu_{i}}_{j=1}\sum^{j}_{k=1}|a_{ij}|{{j}\choose{k}}(bM)^{j-k}M^{k}}{M_{b}}\geq\frac{\epsilon}{2}\Bigg{\\}}$
(221)
$\displaystyle\leq\sup_{|a_{1\nu_{1}}|\geq\gamma,a_{ij}\in\mathbb{C}}\frac{1}{B}\sum_{b=0}^{B-1}\mathbf{1}\Bigg{\\{}(\sum^{\mu}_{i^{\prime}=1}\sum^{\nu_{i^{\prime}}}_{j^{\prime}=1}\sum^{j^{\prime}}_{k^{\prime}=1}{{j^{\prime}}\choose{k^{\prime}}})\cdot\max_{1\leq
i\leq\mu,1\leq j\leq\nu_{i},1\leq k\leq
j}|a_{ij}|(bM)^{j-k}M^{k}\geq\frac{\epsilon}{2}{M_{b}}\Bigg{\\}}$ (222)
$\displaystyle\leq\sum_{1\leq i\leq\mu,1\leq j\leq\nu_{i},1\leq k\leq
j}\sup_{|a_{1\nu_{1}}|\geq\gamma,a_{ij}\in\mathbb{C}}\frac{1}{B}\sum_{b=0}^{B-1}\mathbf{1}\Bigg{\\{}\kappa^{\prime}|a_{ij}|(bM)^{j-k}M^{k}\geq
M_{b}\Bigg{\\}}$ (223) $\displaystyle\leq\sum_{1\leq i\leq\mu,1\leq
j\leq\nu_{i},1\leq k\leq
j}\sup_{|a_{1\nu_{1}}|\geq\gamma,a_{ij}\in\mathbb{C}}\frac{1}{B}\sum_{b=0}^{B-1}\mathbf{1}\Bigg{\\{}\kappa^{\prime}|a_{ij}|(bM)^{j-k}M^{k}\geq|\sum^{\nu_{i}}_{j^{\prime}=0}a_{ij^{\prime}}(bM)^{j^{\prime}}|\Bigg{\\}}(\because\mbox{definition
of $M_{b}$})$ (224) $\displaystyle\leq\sum_{1\leq i\leq\mu,1\leq
j\leq\nu_{i},1\leq k\leq
j}\sup_{|a_{1\nu_{1}}|\geq\gamma,a_{ij}\in\mathbb{C}}\frac{1}{B}\sum_{b=0}^{B-1}\mathbf{1}\Bigg{\\{}\kappa^{\prime}\geq|\sum^{\nu_{i}}_{j^{\prime}=0}\frac{a_{ij^{\prime}}(bM)^{j^{\prime}}}{|a_{ij}|b^{j-k}M^{k}}|\Bigg{\\}}$
(225) $\displaystyle\leq\sum_{1\leq i\leq\mu,1\leq j\leq\nu_{i},1\leq k\leq
j}\sup_{|a_{k}|=1}\frac{1}{B}\sum_{b=0}^{B-1}\mathbf{1}\Bigg{\\{}\kappa^{\prime}\geq|\sum^{\nu_{i}-j+k}_{j^{\prime}=-j+k}a_{j^{\prime}}b^{j^{\prime}}|\Bigg{\\}}$
(226) $\displaystyle<\frac{\delta}{4}.(\because\eqref{eqn:dis:target4})$ (227)

Therefore, by (219), (220), (227), we can see
$\eqref{eqn:dis:geofinal:1}<\delta$, which finishes the proof. ∎

###  X-G Proof of Lemma 3

In this section, we will merge the properties about the observability Gramian
shown in Appendix X-E with the uniform convergence of Appendix X-F, and prove
Lemma 3 of page 3.

Just as we did in Appendix X-D, we must first prove the following lemma which
tells that the determinant of the observability Gramian is large except a
negligible set under a cofactor condition the Gramian matrix. The proof of the
lemma is very similar to that of Lemma 16.

###### Lemma 28

Let $\mathbf{A}$ and $\mathbf{C}$ be given as (173) and (174). Define
$a_{i,j}$ and $C_{i,j}$ as the $(i,j)$ element and cofactor of
$\begin{bmatrix}\mathbf{C}\mathbf{A}^{-k_{1}}\\\ \vdots\\\
\mathbf{C}\mathbf{A}^{-k_{m-1}}\\\ \mathbf{C}\mathbf{A}^{-n}\end{bmatrix}$
respectively. Then, there exists a family of functions
$\\{g_{\epsilon}:\epsilon>0,g_{\epsilon}:\mathbb{R}^{+}\rightarrow\mathbb{R}^{+}\\}$
satisfying:
(i) For all $\epsilon>0$, $k_{1}<k_{2}<\cdots<k_{m-1}$ and
$|C_{m,m}|\geq\epsilon\prod_{1\leq i\leq m-1}\lambda_{i}^{-k_{i}}$, the
following is true.

$\displaystyle\lim_{N\rightarrow\infty}\sup_{k\in\mathbb{Z},k-k_{m-1}\geq
g_{\epsilon}(k_{m-1})}\frac{1}{N}\sum_{n=k+1}^{k+N}\mathbf{1}\left\\{\left|\det\left(\begin{bmatrix}\mathbf{C}\mathbf{A}^{-k_{1}}\\\
\vdots\\\ \mathbf{C}\mathbf{A}^{-k_{m-1}}\\\
\mathbf{C}\mathbf{A}^{-n}\end{bmatrix}\right)\right|<\epsilon^{2}\lambda_{m}^{-n}\prod_{1\leq
i\leq m-1}\lambda_{i}^{-k_{i}}\right\\}\rightarrow 0\mbox{ as
}\epsilon\downarrow 0.$

(ii) For each $\epsilon>0$, $g_{\epsilon}(k)\lesssim 1+\log(k+1)$.

###### Proof:

By Lemma 20, we can find a function $g^{\prime}_{2\epsilon^{2}}(k)$ such that
for all $0\leq k_{1}<k_{2}<\cdots<k_{m-1}<n$ satisfying:
(i) $n-k_{m-1}\geq g^{\prime}_{2\epsilon^{2}}(k_{m-1})$
(ii) $g^{\prime}_{2\epsilon^{2}}(k)\lesssim 1+\log(k+1)$
(iii) $\left|\sum_{m-m_{\mu}+1\leq i\leq m}a_{m,i}C_{m,i}\right|\geq
2\epsilon^{2}\lambda_{m}^{-n}\prod_{1\leq i\leq{m-1}}\lambda_{i}^{-k_{i}}$
the following inequality holds:

$\displaystyle\left|\det\left(\begin{bmatrix}\mathbf{C}\mathbf{A}^{-k_{1}}\\\
\vdots\\\ \mathbf{C}\mathbf{A}^{-k_{m-1}}\\\ \mathbf{C}\mathbf{A}^{-n}\\\
\end{bmatrix}\right)\right|$
$\displaystyle\geq\epsilon^{2}\lambda_{m}^{-n}\prod_{1\leq
i\leq{m-1}}\lambda_{i}^{-k_{i}}.$

Let $g_{\epsilon}(k)$ be $g^{\prime}_{2\epsilon^{2}}(k)$. Then, we have

$\displaystyle\sup_{k\in\mathbb{Z},k-k_{m-1}\geq
g_{\epsilon}(k_{m-1})}\frac{1}{N}\sum_{n=k+1}^{k+N}\mathbf{1}\left\\{\left|\det\left(\begin{bmatrix}\mathbf{C}\mathbf{A}^{-k_{1}}\\\
\vdots\\\ \mathbf{C}\mathbf{A}^{-k_{m-1}}\\\
\mathbf{C}\mathbf{A}^{-n}\end{bmatrix}\right)\right|<\epsilon^{2}\lambda_{m}^{-n}\prod_{1\leq
i\leq m-1}\lambda_{i}^{-k_{i}}\right\\}$
$\displaystyle\leq\sup_{k\in\mathbb{Z},k-k_{m-1}\geq
g_{\epsilon}(k_{m-1})}\frac{1}{N}\sum_{n=k+1}^{k+N}\mathbf{1}\left\\{\left|\sum_{m-m_{\mu}+1\leq
i\leq m}a_{m,i}C_{m,i}\right|<2\epsilon^{2}\lambda_{m}^{-n}\prod_{1\leq i\leq
m-1}\lambda_{i}^{-k_{i}}\right\\}$ (228)
$\displaystyle=\sup_{k\in\mathbb{Z},k-k_{m-1}\geq
g_{\epsilon}(k_{m-1})}\frac{1}{N}\sum_{n=k+1}^{k+N}\mathbf{1}\left\\{\left|\sum_{m-m_{\mu}+1\leq
i\leq m}\frac{a_{m,i}}{\lambda_{m}^{-n}}\frac{C_{m,i}}{\epsilon\prod_{1\leq
i\leq m-1}\lambda_{i}^{-k_{i}}}\right|<2\epsilon\right\\}$
$\displaystyle\leq\sup_{k\in\mathbb{Z},|b_{m}|\geq
1}\frac{1}{N}\sum_{n=k+1}^{k+N}\mathbf{1}\left\\{\left|\sum_{m-m_{\mu}+1\leq
i\leq m}b_{i}\frac{a_{m,i}}{\lambda_{m}^{-n}}\right|<2\epsilon\right\\}$ (229)

where (228) is by the definition of $g_{\epsilon}(k)$ and Lemma 20, and (229)
is by $|C_{m,m}|\geq\epsilon\prod_{1\leq i\leq m-1}\lambda_{i}^{-k_{i}}$.

Let $\mathbf{C_{\mu,\nu_{\mu}}}$ denoted in (174) be
$\begin{bmatrix}c^{\prime}_{1}&\cdots&c^{\prime}_{m_{\mu,\nu_{\mu}}}\end{bmatrix}$.
Moreover,

$\displaystyle\mathbf{A_{\mu,\nu_{\mu}}}^{-n}$
$\displaystyle=\begin{bmatrix}(\lambda_{\mu,\nu_{\mu}}e^{j2\pi\omega_{\mu,\nu_{\mu}}})^{-n}&{{-n}\choose{1}}(\lambda_{\mu,\nu_{\mu}}e^{j2\pi\omega_{\mu,\nu_{\mu}}})^{-n-1}&\cdots&{{-n}\choose{m_{\mu,\nu_{\mu}}-1}}(\lambda_{\mu,\nu_{\mu}}e^{j2\pi\omega_{\mu,\nu_{\mu}}})^{-n-m_{\mu,\nu_{\mu}}+1}\\\
0&(\lambda_{\mu,\nu_{\mu}}e^{j2\pi\omega_{\mu,\nu_{\mu}}})^{-n}&\cdots&{{-n}\choose{m_{\mu,\nu_{\mu}}-2}}(\lambda_{\mu,\nu_{\mu}}e^{j2\pi\omega_{\mu,\nu_{\mu}}})^{-n-m_{\mu,\nu_{\mu}}+2}\\\
\vdots&\vdots&\ddots&\vdots\\\
0&0&\cdots&(\lambda_{\mu,\nu_{\mu}}e^{j2\pi\omega_{\mu,\nu_{\mu}}})^{-n}\end{bmatrix}.$

Thus, we can see that

$\displaystyle a_{m,m}$ $\displaystyle=\sum_{1\leq i\leq
m_{\mu,\nu_{\mu}}}c^{\prime}_{i}{-n\choose
m_{\mu,\nu_{\mu}}-i}(\lambda_{\mu,\nu_{\mu}}e^{j2\pi\omega_{\mu,\nu_{\mu}}})^{-n-m_{\mu,\nu_{\mu}}+i}.$

Therefore,

$\displaystyle\frac{a_{m,m}}{\lambda_{m}^{-n}}$ $\displaystyle=\sum_{1\leq
i\leq m_{\mu,\nu_{\mu}}}c^{\prime}_{i}{-n\choose
m_{\mu,\nu_{\mu}}-i}\lambda_{\mu,\nu_{\mu}}^{-m_{\mu,\nu_{\mu}}+i}(e^{j2\pi\omega_{\mu,\nu_{\mu}}})^{-n-m_{\mu,\nu_{\mu}}+i}.$

Moreover, when $a_{m,i}$ is considered as a function of $n$,
$n^{m_{\mu,\nu_{\mu}}-1}e^{-j2\pi\omega_{\mu,\nu_{\mu}}n}$ term is only shown
up in $\frac{a_{m,m}}{\lambda_{m}^{-n}}$ among
$\frac{a_{m,m-m_{\mu}+1}}{\lambda_{m}^{-n}},\cdots,\frac{a_{m,m}}{\lambda_{m}^{-n}}$,
and the associated coefficient is
$\frac{c_{1}^{\prime}(-1)^{m_{\mu,\nu_{\mu}}-1}}{(m_{\mu,\nu_{\mu}}-1)!}\lambda_{\mu,\nu_{\mu}}^{-m_{\mu,\nu_{\mu}}+1}e^{j2\pi\omega_{\mu,\nu_{\mu}}(-m_{\mu,\nu_{\mu}}+1)}$.

Let
$c^{\prime}:=\frac{|c_{1}^{\prime}|}{(m_{\mu,\nu_{\mu}}-1)!}\lambda_{\mu,\nu_{\mu}}^{-m_{\mu,\nu_{\mu}}+1}$.
Then, (229) can be upper bounded as follows:

$\displaystyle\eqref{eqn:lem:detail2:1}$
$\displaystyle\leq\sup_{k\in\mathbb{Z},|a_{\nu_{\mu},m_{\mu,\nu_{\mu}}}|\geq
c^{\prime}}\frac{1}{N}\sum^{k+N}_{n=k+1}\mathbf{1}\left\\{\left|\sum_{1\leq
i\leq\nu_{\mu}}\left(\sum_{1\leq j\leq
m_{\mu,i}}a_{ij}n^{j-1}\right)e^{j2\pi(-\omega_{\mu,i})n}\right|<2\epsilon\right\\}$
$\displaystyle=\sup_{k\in\mathbb{Z},|a_{\nu_{\mu},m_{\mu,\nu_{\mu}}}|\geq
c^{\prime}}\frac{1}{N}\sum^{N}_{n=1}\mathbf{1}\left\\{\left|\sum_{1\leq
i\leq\nu_{\mu}}\left(\sum_{1\leq j\leq
m_{\mu,i}}a_{ij}(n+k)^{j-1}\right)e^{j2\pi(-\omega_{\mu,i})(n+k)}\right|<2\epsilon\right\\}$
$\displaystyle\leq\sup_{k\in\mathbb{Z},|a_{\nu_{\mu},m_{\mu,\nu_{\mu}}}|\geq
c^{\prime}}\frac{1}{N}\sum^{N}_{n=1}\mathbf{1}\left\\{\left|\sum_{1\leq
i\leq\nu_{\mu}}\left(\sum_{1\leq j\leq
m_{\mu,i}}a_{ij}n^{j-1}\right)e^{j2\pi(-\omega_{\mu,i})(n+k)}\right|<2\epsilon\right\\}$
(230)

The last inequality comes from the fact that the coefficient of
$n^{m_{\mu,\nu_{\mu}}-1}$ is the same for both $\sum_{1\leq j\leq
m_{\mu,\nu_{\mu}}}a_{\nu_{\mu},j}(n+k)^{j-1}$ and $\sum_{1\leq j\leq
m_{\mu,\nu_{\mu}}}a_{\nu_{\mu},j}n^{j-1}$.

By Lemma 15, we get

$\displaystyle\lim_{N\rightarrow\infty}\sup_{k\in\mathbb{Z},|a_{\nu_{\mu},m_{\mu,\nu_{\mu}}}|\geq
c^{\prime}}\frac{1}{N}\sum^{N}_{n=1}\mathbf{1}\left\\{\left|\sum_{1\leq
i\leq\nu_{\mu}}\left(\sum_{1\leq j\leq
m_{\mu,i}}a_{ij}n^{j-1}\right)e^{j2\pi(-\omega_{\mu,i})(n+k)}\right|<2\epsilon\right\\}\rightarrow
0\mbox{ as }\epsilon\downarrow 0.$

Therefore, by (230) we can say that

$\displaystyle\lim_{N\rightarrow\infty}\sup_{k\in\mathbb{Z},k-k_{m-1}\geq
g_{\epsilon}(k_{m-1})}\frac{1}{N}\sum_{n=k+1}^{k+N}\mathbf{1}\left\\{\left|\det\left(\begin{bmatrix}\mathbf{C}\mathbf{A}^{-k_{1}}\\\
\vdots\\\ \mathbf{C}\mathbf{A}^{-k_{m-1}}\\\
\mathbf{C}\mathbf{A}^{-n}\end{bmatrix}\right)\right|<\epsilon^{2}\lambda_{m}^{-n}\prod_{1\leq
i\leq m-1}\lambda_{i}^{-k_{i}}\right\\}\rightarrow 0\mbox{ as
}\epsilon\downarrow 0$

which finishes the proof. ∎

Based on the previous lemma, the properties of p.m.f. tails shown in Section
X-A and the properties of the observability Gramian discussed in Section X-E,
we can prove Lemma 3 for the case when the system has no eigenvalue cycles.
Moreover, we will prove a lemma with multiple systems. This will turn out to
be helpful in proving Lemma 3 for the general systems with eigenvalue cycles.

Consider pairs of matrices
$(\mathbf{A_{1}},\mathbf{C_{1}}),(\mathbf{A_{2}},\mathbf{C_{2}}),\cdots,(\mathbf{A_{r}},\mathbf{C_{r}})$
defined as follows:

$\mathbf{A_{i}}$ is a $m_{i}\times m_{i}$ Jordan form matrix and
$\mathbf{C_{i}}$ is a $1\times m_{i}$ row vector (231) Each $\mathbf{A_{i}}$
has no eigenvalues cycles and $(\mathbf{A_{i}},\mathbf{C_{i}})$ is observable
$\lambda_{j}^{(i)}e^{j2\pi\omega_{j}^{(i)}}$ is $(j,j)$ element of
$\mathbf{A_{i}}$
$\displaystyle\lambda_{1}^{(i)}\geq\lambda_{2}^{(i)}\geq\cdots\geq\lambda_{m_{i}}^{(i)}\geq
1.$

Then, the following lemma holds.

###### Lemma 29

Consider systems
$(\mathbf{A_{1}},\mathbf{C_{1}}),(\mathbf{A_{2}},\mathbf{C_{2}}),\cdots,(\mathbf{A_{r}},\mathbf{C_{r}})$
given as (231). Then, we can find a polynomial $p(k)$ and a family of random
variable $\\{S(\epsilon,k):k\in\mathbb{Z}^{+},\epsilon>0\\}$ such that for all
$\epsilon>0$, $k\in\mathbb{Z}^{+}$ and $1\leq i\leq r$ there exist $k\leq
k_{i,1}<k_{i,2}<\cdots<k_{i,m_{i}}\leq S(\epsilon,k)$ and $\mathbf{M_{i}}$
satisfying the following conditions:
(i) $\beta[k_{i,j}]=1$ for $1\leq i\leq\mu$ and $1\leq j\leq m_{i}$
(ii) $\mathbf{M_{i}}\begin{bmatrix}\mathbf{C_{i}}\mathbf{A_{i}}^{-k_{i,1}}\\\
\mathbf{C_{i}}\mathbf{A_{i}}^{-k_{i,2}}\\\ \vdots\\\
\mathbf{C_{i}}\mathbf{A_{i}}^{-k_{i,m_{i}}}\end{bmatrix}=\mathbf{I}$
(iii)
$|\mathbf{M_{i}}|_{max}\leq\frac{p(S(\epsilon,k))}{\epsilon}(\lambda_{1}^{(i)})^{S(\epsilon,k)}$
(iv) $\lim_{\epsilon\downarrow
0}\exp\limsup_{s\rightarrow\infty}\sup_{k\in\mathbb{Z}^{+}}\frac{1}{s}\log\mathbb{P}\\{S(\epsilon,k)-k=s\\}=p_{e}$.

###### Proof:

By Lemma 19, instead of the condition (ii) and (iii) it is enough to prove
that

$\displaystyle\left|\det\left(\begin{bmatrix}\mathbf{C_{i}}\mathbf{A_{i}}^{-k_{i,1}}\\\
\mathbf{C_{i}}\mathbf{A_{i}}^{-k_{i,2}}\\\ \vdots\\\
\mathbf{C_{i}}\mathbf{A_{i}}^{-k_{i,m_{i}}}\\\
\end{bmatrix}\right)\right|\geq\epsilon\prod_{1\leq j\leq
m_{i}}(\lambda_{j}^{(i)})^{-k_{i,j}}.$

Therefore, it is enough to prove the following claim:

###### Claim 5

We can find a family of stopping times
$\\{S(\epsilon,k):k\in\mathbb{Z}^{+},\epsilon>0\\}$ such that for all
$\epsilon>0$, $k\in\mathbb{Z}^{+}$ and $1\leq i\leq r$ there exist $k\leq
k_{i,1}<k_{i,2}<\cdots<k_{i,m_{i}}\leq S(\epsilon,k)$ satisfying the following
condition:
(a) $\beta[k_{i,j}]=1$ for $1\leq i\leq\mu$ and $1\leq j\leq m_{i}$
(b) $\left|\det\left(\begin{bmatrix}\mathbf{C_{i}}\mathbf{A_{i}}^{-k_{i,1}}\\\
\mathbf{C_{i}}\mathbf{A_{i}}^{-k_{i,2}}\\\ \vdots\\\
\mathbf{C_{i}}\mathbf{A_{i}}^{-k_{i,m_{i}}}\\\
\end{bmatrix}\right)\right|\geq\epsilon\prod_{1\leq j\leq
m_{i}}(\lambda_{j}^{(i)})^{-k_{i,j}}$
(c) $\lim_{\epsilon\downarrow
0}\exp\limsup_{s\rightarrow\infty}\sup_{k\in\mathbb{Z}^{+}}\frac{1}{s}\log\mathbb{P}\left\\{S(\epsilon,k)-k=s\right\\}\leq
p_{e}$.

Before we prove the above claim, we first prove the claim for a single system.

###### Claim 6

We can find a family of stopping times
$\\{S_{1}(\epsilon,k):k\in\mathbb{Z}^{+},\epsilon>0\\}$ such that for all
$\epsilon>0$ and $k\in\mathbb{Z}^{+}$ there exist $k\leq
k_{1}^{\prime}<k_{2}^{\prime}<\cdots<k_{m_{1}}^{\prime}\leq S_{1}(\epsilon,k)$
satisfying the following condition:
(a’) $\beta[k_{j}^{\prime}]=1$ for $1\leq j\leq m_{1}$
(b’)
$\left|\det\left(\begin{bmatrix}\mathbf{C_{1}}\mathbf{A_{1}}^{-k_{1}^{\prime}}\\\
\mathbf{C_{1}}\mathbf{A_{1}}^{-k_{2}^{\prime}}\\\ \vdots\\\
\mathbf{C_{1}}\mathbf{A_{1}}^{-k_{m_{i}}^{\prime}}\\\
\end{bmatrix}\right)\right|\geq\epsilon\prod_{1\leq j\leq
m_{1}}(\lambda_{j}^{(1)})^{-k_{j}^{\prime}}$
(c’) $\lim_{\epsilon\downarrow
0}\exp\limsup_{s\rightarrow\infty}\sup_{k\in\mathbb{Z}^{+}}\frac{1}{s}\log\mathbb{P}\left\\{S_{1}(\epsilon,k)-k=s\right\\}\leq
p_{e}$.

$\bullet$ Proof of Claim 6: The proof of Claim 6 is an induction on $m$.

(i) First consider the case $m_{1}=1$.

In this case, $\mathbf{A_{1}}$ and $\mathbf{C_{1}}$ is scalar, so denote
$\mathbf{A_{1}}:=\lambda_{1}^{(1)}e^{j2\pi\omega_{1}^{(1)}}$ and
$\mathbf{C_{1}}:=c_{1}$. Since we only care about small enough $\epsilon$, let
$\epsilon\leq|c_{1}|$. Denote $S_{1}(\epsilon,k):=\inf\\{n\geq
k:\beta[n]=1\\}$ and $k_{1}^{\prime}=S_{1}(\epsilon,k)$. Then,
$\beta[k_{1}^{\prime}]=1$ and
$\left|\det\left(\begin{bmatrix}c_{1}(\lambda_{1}^{(1)}e^{j2\pi\omega_{1}^{(1)}})^{-k_{1}^{\prime}}\end{bmatrix}\right)\right|=|c_{1}|(\lambda_{1}^{(1)})^{-k_{1}^{\prime}}\geq\epsilon(\lambda_{1}^{(1)})^{-k_{1}^{\prime}}$.
Moreover, since $S_{1}(\epsilon,k)-k$ is a geometric random variable with
probability $1-p_{e}$,

$\displaystyle\exp\limsup_{s\rightarrow\infty}\sup_{k\in\mathbb{Z}^{+}}\log\mathbb{P}\left\\{S_{1}(\epsilon,k)-k=s\right\\}=p_{e}.$

Therefore, $S_{1}(\epsilon,k)$ satisfies all the conditions of the claim.

(ii) As an induction hypothesis, we assume the claim is true for $m_{1}-1$ and
prove the claim hold for $m_{1}$.

Denote $\mathbf{A_{1}^{\prime}}$ be a $(m_{1}-1)\times(m_{1}-1)$ matrix
obtained by removing $m_{1}$th row and column of $\mathbf{A_{1}}$. Likewise,
$\mathbf{C_{1}^{\prime}}$ is a $1\times(m_{1}-1)$ vector obtained by removing
$m_{1}$th element of $\mathbf{C_{1}}$. Then, we can observe that

$\displaystyle\det\left(\begin{bmatrix}\mathbf{C_{1}^{\prime}}\mathbf{A_{1}^{\prime}}^{-k_{1}^{\prime}}\\\
\vdots\\\
\mathbf{C_{1}^{\prime}}\mathbf{A_{1}^{\prime}}^{-k_{m_{1}-1}^{\prime}}\end{bmatrix}\right)=cof_{m_{1},m_{1}}\left(\begin{bmatrix}\mathbf{C_{1}}\mathbf{A_{1}}^{-k_{1}^{\prime}}\\\
\vdots\\\ \mathbf{C_{1}}\mathbf{A_{1}}^{-k_{m_{1}}^{\prime}}\\\
\end{bmatrix}\right)$

where $cof_{i,j}(\mathbf{A})$ implies the cofactor matrix of $\mathbf{A}$ with
respect to $(i,j)$ element.

By the induction hypothesis, we can find a stopping time
$S_{1}^{\prime}(\epsilon,k)$ such that there exist $k\leq
k_{1}^{\prime}<k_{2}^{\prime}<\cdots<k_{m_{1}-1}^{\prime}\leq
S_{1}^{\prime}(\epsilon,k)$ satisfying:
(a”) $\beta[k_{j}^{\prime}]=1$ for $1\leq j\leq m_{1}-1$
(b”)
$\left|\det\left(\begin{bmatrix}\mathbf{C_{1}^{\prime}}\mathbf{A_{1}^{\prime}}^{-k_{1}^{\prime}}\\\
\vdots\\\
\mathbf{C_{1}^{\prime}}\mathbf{A_{1}^{\prime}}^{-k_{m_{1}-1}^{\prime}}\end{bmatrix}\right)\right|\geq\epsilon\prod_{1\leq
j\leq m_{1}-1}(\lambda_{j}^{(1)})^{-k_{j}^{\prime}}$
(c”) $\lim_{\epsilon\downarrow
0}\exp\limsup_{s\rightarrow\infty}\sup_{k\in\mathbb{Z}^{+}}\frac{1}{s}\log\mathbb{P}\left\\{S_{1}^{\prime}(\epsilon,k)-k=s\right\\}\leq
p_{e}$.

Let $\mathcal{F}_{i}$ be a $\sigma$-field generated by
$\beta[0],\cdots,\beta[i]$ and
$g_{\epsilon}:\mathbb{R}^{+}\rightarrow\mathbb{R}^{+}$ be the function of
Lemma 28. Denote a random variable $d(\epsilon,N)$ as following:

$\displaystyle
d(\epsilon,N):=\sup_{k\in\mathbb{Z},k-S_{1}^{\prime}(\epsilon,k)\geq
g_{\epsilon}(S_{1}^{\prime}(\epsilon,k))}\frac{1}{N}\sum_{n=k+1}^{k+N}\mathbf{1}\left\\{\left|\det\left(\begin{bmatrix}\mathbf{C_{1}}\mathbf{A_{1}}^{-k_{1}^{\prime}}\\\
\vdots\\\ \mathbf{C_{1}}\mathbf{A_{1}}^{-k_{m_{1}-1}^{\prime}}\\\
\mathbf{C_{1}}\mathbf{A_{1}}^{-n}\end{bmatrix}\right)\right|<\epsilon^{2}(\lambda_{m_{1}}^{(1)})^{-n}\prod_{1\leq
j\leq
m_{1}-1}(\lambda_{j}^{(1)})^{-k_{j}}|\mathcal{F}_{S_{1}^{\prime}(\epsilon,k)}\right\\}.$

Since (b”) implies
$cof_{m_{1},m_{1}}\left(\begin{bmatrix}\mathbf{C_{1}}\mathbf{A_{1}}^{-k_{1}^{\prime}}\\\
\vdots\\\ \mathbf{C_{1}}\mathbf{A_{1}}^{-k_{m_{1}-1}^{\prime}}\\\
\mathbf{C_{1}}\mathbf{A_{1}}^{-n}\\\
\end{bmatrix}\right)\geq\epsilon\prod_{1\leq j\leq
m_{1}-1}(\lambda_{i}^{(1)})^{-k_{j}^{\prime}}$, by Lemma 28 we have

$\displaystyle\lim_{\epsilon\downarrow
0}\lim_{N\rightarrow\infty}\operatorname{ess\,sup}d(\epsilon,N)=0.$

Denote
$S_{1}^{\prime\prime}(\epsilon,k):=S_{1}^{\prime}(\epsilon,k)+g_{\epsilon}(S_{1}^{\prime}(\epsilon,k))$.
From (ii) of Lemma 28 we know $g_{\epsilon}(k)\lesssim 1+\log(k+1)$ for all
$\epsilon>0$. Therefore, by Lemma 5 we have

$\displaystyle\lim_{\epsilon\downarrow
0}\exp\limsup_{s\rightarrow\infty}\sup_{k\in\mathbb{Z}^{+}}\frac{1}{s}\log\mathbb{P}\\{S_{1}^{\prime\prime}(\epsilon,k)-k=s\\}\leq
p_{e}.$ (232)

Denote a stopping time

$\displaystyle
S_{1}^{\prime\prime\prime}(\epsilon,k):=\inf\left\\{n>S_{1}^{\prime\prime}(\epsilon,k):\beta[n]=1\mbox{
and
}\left|\det\left(\begin{bmatrix}\mathbf{C_{1}}\mathbf{A_{1}}^{-k_{1}^{\prime}}\\\
\vdots\\\ \mathbf{C_{1}}\mathbf{A_{1}}^{-k_{m_{1}-1}^{\prime}}\\\
\mathbf{C_{1}}\mathbf{A_{1}}^{-n}\\\
\end{bmatrix}\right)\right|\geq\epsilon^{2}(\lambda_{m_{1}}^{(1)})^{-n}\prod_{1\leq
j\leq m_{1}-1}(\lambda_{j}^{(1)})^{-k_{j}^{\prime}}\right\\}.$

Since $\beta[n]$ is a Bernoulli process,

$\displaystyle\mathbb{P}\\{S_{1}^{\prime\prime\prime}(\epsilon,k)-S_{1}^{\prime\prime}(\epsilon,k)\geq
N|\mathcal{F}_{S_{1}^{\prime\prime}(\epsilon,k)}\\}\leq
p_{e}^{N(1-d(\epsilon,N))}.$

Therefore,

$\displaystyle\lim_{\epsilon\downarrow 0}\exp\limsup_{N\rightarrow
0}\operatorname{ess\,sup}\frac{1}{N}\log\mathbb{P}\\{S_{1}^{\prime\prime\prime}(\epsilon,k)-S_{1}^{\prime\prime}(\epsilon,k)\geq
N|\mathcal{F}_{S_{1}^{\prime\prime}(\epsilon,k)}\\}\leq\lim_{\epsilon\downarrow
0}\lim_{N\rightarrow\infty}\operatorname{ess\,sup}p_{e}^{1-d(\epsilon,N)}\leq
p_{e}$

i.e.

$\displaystyle\lim_{\epsilon\downarrow 0}\exp\limsup_{s\rightarrow
0}\operatorname{ess\,sup}\frac{1}{s}\log\mathbb{P}\\{S_{1}^{\prime\prime\prime}(\epsilon,k)-S_{1}^{\prime\prime}(\epsilon,k)=s|\mathcal{F}_{S_{1}^{\prime\prime}(\epsilon,k)}\\}\leq
p_{e}.$ (233)

By applying Lemma 6 to (232) and (233), we can conclude that

$\displaystyle\lim_{\epsilon\downarrow
0}\exp\limsup_{s\rightarrow\infty}\sup_{k\in\mathbb{Z}^{+}}\frac{1}{s}\log\mathbb{P}\\{S_{1}^{\prime\prime\prime}(\epsilon,k)-k=s\\}\leq
p_{e}.$

Therefore, if we denote
$S_{1}(\epsilon,k):=S_{1}^{\prime\prime\prime}(\epsilon^{\frac{1}{2}},k)$,
$S_{1}(\epsilon,k)$ satisfies all the conditions of Claim 6.

$\bullet$ Proof of Claim 5: By recursive use of Claim 6, we can find stopping
times $S_{2}(\epsilon,k),\cdots,S_{r}(\epsilon,k)$ such that for all
$\epsilon>0$ and $2\leq i\leq r$ there exist
$S_{i-1}(\epsilon,k)<k_{i,1}<k_{i,2}<\cdots<k_{i,m_{i}}\leq S_{i}(\epsilon,k)$
satisfying the following condition:
(a) $\beta[k_{i,j}]=1$ for $1\leq j\leq m_{i}$
(b) $\left|\det\left(\begin{bmatrix}\mathbf{C_{i}}\mathbf{A_{i}}^{-k_{i,1}}\\\
\mathbf{C_{i}}\mathbf{A_{i}}^{-k_{i,2}}\\\ \vdots\\\
\mathbf{C_{i}}\mathbf{A_{i}}^{-k_{i,m_{i}}}\\\
\end{bmatrix}\right)\right|\geq\epsilon\prod_{1\leq j\leq
m_{i}}(\lambda_{j}^{(i)})^{-k_{i,j}}$
(c) $\lim_{\epsilon\downarrow
0}\exp\limsup_{s\rightarrow\infty}\operatorname{ess\,sup}\frac{1}{s}\log\mathbb{P}\\{S_{i}(\epsilon,k)-S_{i-1}(\epsilon,k)=s|\mathcal{F}_{S_{i-1}(\epsilon,k)}\\}\leq
p_{e}$.

Then, by Lemma 6

$\displaystyle\lim_{\epsilon\downarrow
0}\exp\limsup_{s\rightarrow\infty}\sup_{k\in\mathbb{Z}^{+}}\frac{1}{s}\log\mathbb{P}\\{S_{r}(\epsilon,k)-k=s\\}\leq
p_{e}.$

Therefore, if we denote $S(\epsilon,k):=S_{r}(\epsilon,k)$, $S(\epsilon,k)$
satisfies all the conditions of Claim 5. Thus, Claim 5 is true and the lemma
is also true. ∎

We prove some properties about matrices which will be helpful in the proof of
Lemma 3.

###### Lemma 30

Let $\mathbf{A}$ and $\mathbf{A^{\prime}}$ be Jordan block matrices with
eigenvalues $\lambda,\alpha\lambda(\alpha\neq 0)$ respectively and the same
size $m\in\mathbb{N}$, i.e. $\mathbf{A}=\begin{bmatrix}\lambda&1&\cdots&0\\\
0&\lambda&\cdots&0\\\ \vdots&\vdots&\ddots&\vdots\\\
0&0&\cdots&\lambda\end{bmatrix}$ and
$\mathbf{A^{\prime}}=\begin{bmatrix}\alpha\lambda&1&\cdots&0\\\
0&\alpha\lambda&\cdots&0\\\ \vdots&\vdots&\ddots&\vdots\\\
0&0&\cdots&\alpha\lambda\end{bmatrix}$. Then, for all $n\in\mathbb{Z}$

$\displaystyle\mathbf{A^{\prime}}^{n}=\begin{bmatrix}\alpha^{-(m-1)}&0&\cdots&0\\\
0&\alpha^{-(m-2)}&\cdots&0\\\ \vdots&\vdots&\ddots&\vdots\\\
0&0&\cdots&1\end{bmatrix}\mathbf{A}^{n}\begin{bmatrix}\alpha^{n+(m-1)}&0&\cdots&0\\\
0&\alpha^{n+(m-2)}&\cdots&0\\\ \vdots&\vdots&\ddots&\vdots\\\
0&0&\cdots&\alpha^{n}\end{bmatrix}.$

###### Proof:

$\displaystyle\mathbf{A^{\prime}}^{n}$
$\displaystyle=\begin{bmatrix}(\alpha\lambda)^{n}&{n\choose
1}(\alpha\lambda)^{n-1}&{n\choose 2}(\alpha\lambda)^{n-2}&\cdots&{n\choose
m}(\alpha\lambda)^{n-(m-1)}\\\ 0&(\alpha\lambda)^{n}&{n\choose
1}(\alpha\lambda)^{n-1}&\cdots&{n\choose m-1}(\alpha\lambda)^{n-(m-2)}\\\
0&0&(\alpha\lambda)^{n}&\cdots&{n\choose m-2}(\alpha\lambda)^{n-(m-3)}\\\
\vdots&\vdots&\vdots&\ddots&\vdots\\\
0&0&0&\cdots&(\alpha\lambda)^{n}\end{bmatrix}$
$\displaystyle=\begin{bmatrix}\alpha^{-(m-1)}&0&0&\cdots&0\\\
0&\alpha^{-(m-2)}&0&\cdots&0\\\ 0&0&\alpha^{-(m-3)}&\cdots&0\\\
\vdots&\vdots&\vdots&\ddots&\vdots\\\ 0&0&0&\cdots&1\end{bmatrix}$
$\displaystyle\cdot\begin{bmatrix}\alpha^{n+m-1}\lambda^{n}&{n\choose
1}\alpha^{n-1+m-1}\lambda^{n-1}&{n\choose
2}\alpha^{n-2+m-1}\lambda^{n-2}&\cdots&{n\choose
m}\alpha^{n-(m-1)+m-1}\lambda^{n-(m-1)}\\\
0&\alpha^{n+m-2}\lambda^{n}&{n\choose
1}\alpha^{n-1+m-2}\lambda^{n-1}&\cdots&{n\choose
m-1}\alpha^{n-(m-2)+m-2}\lambda^{n-(m-2)}\\\
0&0&\alpha^{n+m-3}\lambda^{n}&\cdots&{n\choose
m-2}\alpha^{n-(m-3)+m-3}\lambda^{n-(m-3)}\\\
\vdots&\vdots&\vdots&\ddots&\vdots\\\
0&0&0&\cdots&\alpha^{n}\lambda^{n}\end{bmatrix}$
$\displaystyle=\begin{bmatrix}\alpha^{-(m-1)}&0&0&\cdots&0\\\
0&\alpha^{-(m-2)}&0&\cdots&0\\\ 0&0&\alpha^{-(m-3)}&\cdots&0\\\
\vdots&\vdots&\vdots&\ddots&\vdots\\\ 0&0&0&\cdots&1\end{bmatrix}$
$\displaystyle\cdot\begin{bmatrix}\alpha^{n+m-1}\lambda^{n}&{n\choose
1}\alpha^{n+m-2}\lambda^{n-1}&{n\choose
2}\alpha^{n+m-3}\lambda^{n-2}&\cdots&{n\choose m}\alpha^{n}\lambda^{n-m}\\\
0&\alpha^{n+m-2}\lambda^{n}&{n\choose
1}\alpha^{n+m-3}\lambda^{n-1}&\cdots&{n\choose
m-1}\alpha^{n}\lambda^{n-(m-1)}\\\
0&0&\alpha^{n+m-3}\lambda^{n}&\cdots&{n\choose
m-2}\alpha^{n}\lambda^{n-(m-2)}\\\ \vdots&\vdots&\vdots&\ddots&\vdots\\\
0&0&0&\cdots&\alpha^{n}\lambda^{n}\end{bmatrix}$
$\displaystyle=\begin{bmatrix}\alpha^{-(m-1)}&0&0&\cdots&0\\\
0&\alpha^{-(m-2)}&0&\cdots&0\\\ 0&0&\alpha^{-(m-3)}&\cdots&0\\\
\vdots&\vdots&\vdots&\ddots&\vdots\\\ 0&0&0&\cdots&1\end{bmatrix}$
$\displaystyle\cdot\begin{bmatrix}\lambda^{n}&{n\choose
1}\lambda^{n-1}&{n\choose 2}\lambda^{n-2}&\cdots&{n\choose m}\lambda^{n-m}\\\
0&\lambda^{n}&{n\choose 1}\lambda^{n-1}&\cdots&{n\choose
m-1}\lambda^{n-(m-1)}\\\ 0&0&\lambda^{n}&\cdots&{n\choose
m-2}\lambda^{n-(m-2)}\\\ \vdots&\vdots&\vdots&\ddots&\vdots\\\
0&0&0&\cdots&\lambda^{n}\end{bmatrix}\cdot\begin{bmatrix}\alpha^{n+(m-1)}&0&0&\cdots&0\\\
0&\alpha^{n+(m-2)}&0&\cdots&0\\\ 0&0&\alpha^{n+(m-3)}&\cdots&0\\\
\vdots&\vdots&\vdots&\ddots&\vdots\\\ 0&0&0&\cdots&\alpha^{n}\end{bmatrix}$
$\displaystyle=\begin{bmatrix}\alpha^{-(m-1)}&0&\cdots&0\\\
0&\alpha^{-(m-2)}&\cdots&0\\\ \vdots&\vdots&\ddots&\vdots\\\
0&0&\cdots&1\end{bmatrix}\mathbf{A}^{n}\begin{bmatrix}\alpha^{n+(m-1)}&0&\cdots&0\\\
0&\alpha^{n+(m-2)}&\cdots&0\\\ \vdots&\vdots&\ddots&\vdots\\\
0&0&\cdots&\alpha^{n}\end{bmatrix}$

This finishes the proof. ∎

###### Lemma 31

Let $\mathbf{A}$ be a Jordan block with eigenvalue $\lambda$ and dimension
$m\times m$. Then, the Jordan decomposition of the matrix $\mathbf{A}^{k}$ for
$k\in\mathbb{N}$ is $\mathbf{U}\mathbf{\Lambda}\mathbf{U}^{-1}$ where
$\mathbf{U}$ is an invertible upper triangular matrix —so the diagonal
elements of $\mathbf{U}$ are non-zero— and $\mathbf{\Lambda}$ is a Jordan
block with eigenvalue $\lambda^{k}$ and dimension $m\times m$.

###### Proof:

We can see that $\mathbf{A}^{k}$ is a upper triangular toeplitz matrix whose
diagonal elements are $\lambda^{k}$. Thus,
$\det(s\mathbf{I}-\mathbf{A}^{k})=(s-\lambda^{k})^{m}$ and all eigenvalues of
$\mathbf{A}^{k}$ are $\lambda^{k}$. Moreover, the rank of
$\mathbf{A}^{k}-\lambda^{k}\mathbf{I}$ is $m-1$. Thus, $\mathbf{\Lambda}$ has
to be a Jordan block matrix with eigenvalue $\lambda^{k}$ and dimension
$m\times m$.

Moreover,
$Ker\left(\left(\mathbf{A}-\lambda^{k}\mathbf{I}\right)^{p}\right)\supseteq
span\\{\mathbf{e_{1}},\mathbf{e_{2}},\cdots,\mathbf{e_{p}}\\}$. Therefore,
$i$th column of $\mathbf{U}^{-1}$ has to belong to the vector space
$\\{\mathbf{e_{1}},\cdots,\mathbf{e_{i}}\\}$ and $\mathbf{U}^{-1}$ is upper
diagonal matrix. Here, the existence of Jordan form of arbitrary matrix
guarantee the invertibility of $\mathbf{U}$. Therefore, $\mathbf{U}$ is also
upper triangular matrix and the invertibility condition of an upper triangular
matrix is its diagonal elements are non-zero. ∎

###### Lemma 32

Let $\mathbf{A}$ be a Jordan block matrix with eigenvalue
$\lambda\in\mathbb{C}$ and size $m\in\mathbb{N}$, i.e.
$\mathbf{A}=\begin{bmatrix}\lambda&1&\cdots&0\\\ 0&\lambda&\cdots&0\\\
\vdots&\vdots&\ddots&\vdots\\\ 0&0&\cdots&\lambda\\\ \end{bmatrix}$.
$\mathbf{C}$ and $\mathbf{C^{\prime}}$ are $1\times m$ matrices such that

$\displaystyle\mathbf{C}=\begin{bmatrix}c_{1}&c_{2}&\cdots&c_{m}\end{bmatrix}$
$\displaystyle\mathbf{C^{\prime}}=\begin{bmatrix}c^{\prime}_{1}&c^{\prime}_{2}&\cdots&c^{\prime}_{m}\end{bmatrix}$
(234)

where $c_{i},c^{\prime}_{i}\in\mathbb{C}$ and $c_{1}\neq 0$.
For all $k\in\mathbb{R}$ and $m\times 1$ matrices
$\mathbf{X}=\begin{bmatrix}x_{1}\\\ x_{2}\\\ \vdots\\\ x_{m}\end{bmatrix}$ and
$\mathbf{X^{\prime}}=\begin{bmatrix}x^{\prime}_{1}\\\ x^{\prime}_{2}\\\
\vdots\\\ x^{\prime}_{m}\end{bmatrix}$, there exists $\mathbf{T}$ such that

$\displaystyle(i)\mathbf{T}\mbox{ is an upper triangular matrix.}$
$\displaystyle(ii)\mathbf{C}\mathbf{A}^{k}\mathbf{X}+\mathbf{C^{\prime}}\mathbf{A}^{k}\mathbf{X^{\prime}}=\mathbf{C}\mathbf{A}^{k}\left(\mathbf{X}+\mathbf{T}\mathbf{X^{\prime}}\right)$

Moreover, the diagonal elements of $\mathbf{T}$ are
$\frac{c_{1}^{\prime}}{c_{1}}$.

###### Proof:

Similar to Lemma 18. ∎

Now, we can prove Lemma 3.

###### Proof:

We will prove the lemma by an induction on $m$, the dimension of the system.
Remind that here we are using the definitions of (90), (91) for the system
matrices $\mathbf{A}$, $\mathbf{C}$, $\mathbf{A_{i}}$, $\mathbf{C_{i}}$,
$\cdots$.

(i) When $m=1$,

In this case, the lemma reduces to the scalar problem and is trivially true.
Precisely, if we choose $S_{1}(\epsilon,k)$ as $\inf\\{s\geq k:\beta[s]=1\\}$,
we can check all the conditions of the lemma are satisfied.

(ii) Now, we will assume the lemma is true when the system dimension is $m-1$
as an induction hypothesis, and prove the lemma holds for the system with
dimension $m$.

Let $\mathbf{x_{i,j}}$ be a $m_{i,j}\times 1$ column vector, and $\mathbf{x}$
be $\begin{bmatrix}\mathbf{x_{1,1}}\\\ \mathbf{x_{1,2}}\\\ \vdots\\\
\mathbf{x_{\mu,\nu_{\mu}}}\end{bmatrix}$. Here, $\mathbf{x}$ can be thought as
the state of the system, and $\mathbf{x_{i,j}}$ corresponds to the states
associated with the Jordan block $\mathbf{A_{i,j}}$. Remind that
$\mathbf{A_{1,1}}$ is the Jordan block with the largest eigenvalue and size.

The purpose of this proof is following: By Lemma 29, we already know that the
lemma holds for systems with scalar observations and without eigenvalue
cycles. Therefore, we first reduce the system to one with scalar observations
and without eigenvalue cycles. To reduce the system to the one without
eigenvalue cycles, we will use down-sampling ideas (polyphase decomposition)
form signal processing [2]. To reduce the system to the one with scalar
observations, we will multiple a proper post-processing matrix which combines
vector observations to scalar observations. Then, we estimate the $m_{1,1}$th
element of $\mathbf{x_{1,1}}$, which associated with the largest eigenvalue.
Then, we subtract the estimation from the system. The resulting system becomes
a $(m-1)$-dimensional system, and by the induction hypothesis, we can estimate
the remaining states. As we mentioned before, this idea is called successive
decoding in information theory [31].

Let’s start from the down-sampling and reduction to scalar observation
systems.

$\bullet$ Down-sampling the System by $p$ and Reduction to Scalar Observation
Systems: The main difficulty in estimating the $m_{1,1}$th element of
$\mathbf{x_{1,1}}$ is the periodicity of the system. To handle this
difficulty, we down sample the system. Let $p=\prod_{1\leq i\leq\mu}p_{i}$.
Remind that in (91), $p_{i}$ was the period of each eigenvalue cycles. We can
see when the system is down sampled by $p$, the resulting system becomes
aperiodic. Thus, we can reduce the original periodic system to $p$ number of
aperiodic systems.

We can further reduce vector observation systems to scalar observation
systems. Thus, the system reduces to aperiodic system with scalar
observations, and by Lemma 29 we can estimate the $m_{1,1}$th element of
$\mathbf{x_{1,1}}$.

Since we are using induction for the proof, we can focus on the first
eigenvalue cycle of the system.

Let $T_{1},\cdots,T_{R}$ be all the sets $T$ such that
$T:=\\{t_{1},\cdots,t_{|T|}\\}\subseteq\\{0,1,\cdots,p_{1}-1\\}$ and

$\displaystyle\begin{bmatrix}\mathbf{C_{1}}\mathbf{A_{1}}^{-t_{1}}\\\
\mathbf{C_{1}}\mathbf{A_{1}}^{-t_{2}}\\\ \vdots\\\
\mathbf{C_{1}}\mathbf{A_{1}}^{-t_{|T|}}\end{bmatrix}\text{ is full rank.}$
(235)

Here, the definition of $\mathbf{A_{1}}$ and $\mathbf{C_{1}}$ is given in (91)
and
$\begin{bmatrix}\mathbf{C_{1}}diag\\{\alpha_{1,1},\cdots,\alpha_{1,\nu_{1}}\\}^{-t_{1}}\\\
\mathbf{C_{1}}diag\\{\alpha_{1,1},\cdots,\alpha_{1,\nu_{1}}\\}^{-t_{2}}\\\
\vdots\\\
\mathbf{C_{1}}diag\\{\alpha_{1,1},\cdots,\alpha_{1,\nu_{1}}\\}^{-t_{|T|}}\end{bmatrix}$
is also full rank. The number of such sets, $R$, is finite since $p_{1}$ is
finite.

Therefore, for each $T_{r}:=\\{t_{r,1},\cdots,t_{r,|T_{r}|}\\}$ $(1\leq r\leq
R)$, we can find a matrix $\mathbf{L_{r}}$ such that

$\displaystyle\mathbf{L_{r}}\begin{bmatrix}\mathbf{C_{1}}diag\\{\alpha_{1,1},\cdots,\alpha_{1,\nu_{1}}\\}^{-t_{r,1}}\\\
\mathbf{C_{1}}diag\\{\alpha_{1,1},\cdots,\alpha_{1,\nu_{1}}\\}^{-t_{r,2}}\\\
\vdots\\\
\mathbf{C_{1}}diag\\{\alpha_{1,1},\cdots,\alpha_{1,\nu_{1}}\\}^{-t_{r,|T_{i}|}}\\\
\end{bmatrix}=\mathbf{I}.$

Denote
$\begin{bmatrix}\mathbf{L_{t_{r,1},r}}&\mathbf{L_{t_{r,2},r}}&\cdots&\mathbf{L_{t_{r,|T_{r}|},r}}\end{bmatrix}$
be the first row of $\mathbf{L_{r}}$ where $\mathbf{L_{t,r}}$ are $1\times l$
matrices. Then,

$\displaystyle\begin{bmatrix}\mathbf{L_{t_{r,1},r}}&\mathbf{L_{t_{r,2},r}}&\cdots&\mathbf{L_{t_{r,|T_{r}|},r}}\end{bmatrix}\begin{bmatrix}\mathbf{C_{1}}diag\\{\alpha_{1,1},\cdots,\alpha_{1,\nu_{1}}\\}^{-t_{r,1}}\\\
\mathbf{C_{1}}diag\\{\alpha_{1,1},\cdots,\alpha_{1,\nu_{1}}\\}^{-t_{r,2}}\\\
\vdots\\\
\mathbf{C_{1}}diag\\{\alpha_{1,1},\cdots,\alpha_{1,\nu_{1}}\\}^{-t_{r,|T_{r}|}}\\\
\end{bmatrix}=\begin{bmatrix}1&0&\cdots&0\end{bmatrix}.$ (236)

We also extend this definition of $\mathbf{L_{q,r}}$ to all
$q\in\\{0,\cdots,p-1\\},r\in\\{1,\cdots,R\\}$ by putting
$\mathbf{L_{q,r}}:=\mathbf{L_{q(\mod p_{1}),r}}$ for $q\geq p_{1}$. Then, we
can easily check that (236) still holds as long as $t_{r,i}$ remains the same
in $\mod p_{1}$.

###### Claim 7

For given $q\in\\{0,\cdots,p-1\\}$ and $r\in\\{1,\cdots,R\\}$, let
$\mathbf{L_{q,r}}\mathbf{C_{1}}$ be not $\mathbf{0}$. Then, there exists
$\mathbf{\bar{C}_{q,r}}$, $\mathbf{\bar{A}_{q,r}}$, $\mathbf{\bar{U}_{q,r}}$,
$\mathbf{\bar{x}_{q,r}}$ that satisfies the following conditions:
(i) $\mathbf{\bar{A}_{q,r}}$ is a
$\bar{\bar{m}}_{q,r}\times\bar{\bar{m}}_{q,r}$ square matrix given in a Jordan
form. The eigenvalues of $\mathbf{\bar{A}_{q,r}}$ belong to
$\\{\lambda_{1,1}^{p},\lambda_{2,1}^{p},\cdots,\lambda_{\mu,1}^{p}\\}$, and no
two different Jordan blocks have the same eigenvalue. Therefore,
$\mathbf{\bar{A}_{q,r}}$ has no eigenvalue cycles. Furthermore, the first
Jordan block(left-top) of $\mathbf{\bar{A}_{q,r}}$ is a $m_{1,1}\times
m_{1,1}$ Jordan block associated with eigenvalue $\lambda_{1,1}^{p}$.
(ii) $\mathbf{\bar{C}_{q,r}}$ is a $1\times\bar{\bar{m}}_{q,r}$ row vector and