vector then we can express it as $n_{i}^{\prime}=\sum_{s}c_{s}n_{s}$, where
the $n_{s}$ are as above. Then

$\displaystyle|N^{e}n_{i}^{\prime}|^{2}=|\sum_{s}c_{s}N^{e}n_{s}|^{2}=\sum_{s}|c_{s}N^{e}n_{s}|^{2}\leq(1/2+\eta)\sum_{s}|c_{s}|^{2}=1/2+\eta$
(23)

and consequently

$\displaystyle|(1-N^{e})n_{i}^{\prime}|^{2}\geq 1/2-\eta.$ (24)

Note that if $n_{i}\in\mathcal{N}_{i}\ominus\mathcal{N}_{i}^{\prime}$ then
$n_{i}$ is expressed as linear combination of the $n_{s}$ with
$|N^{e}n_{s}|^{2}>1/2+\eta$ and hence the opposite inequalities hold:

$\displaystyle|N^{e}n_{i}|>\sqrt{1/2+\eta}$ (25)

and

$\displaystyle|(1-N^{e})n_{i}|<\sqrt{1/2-\eta}.$ (26)

See that the definition of $N_{i}^{\prime}$ is intended to remove a part of
$\mathcal{N}_{i}$ that has large projection onto
$\mathcal{N}_{i-1}\oplus\mathcal{N}_{i+1}$. This is not quite enough control
of the orthogonality to give a result like Equation (2), but, along with
$\|Y_{i+1}^{\prime}N_{i}Y_{i-1}^{\prime}\|<1/2-\chi/2$, it will suffice for
our purposes.

######  Definition 14.10.

Let $\mathcal{U}\subset\mathcal{R}$ be defined as the orthogonal complement of
the span of
$\bigcup_{i\,even}\mathcal{N}_{i}\cup\bigcup_{i\,odd}\mathcal{N}_{i}^{\prime}$.
Then let $\mathcal{W}=A\mathcal{U}\subset\mathcal{X}$ and $P$ project onto
$\mathcal{W}$.

######  Remark 14.11.

$\mathcal{U}^{\perp}$ is expressed as the _direct_ sum
$\bigoplus_{i\,odd}\mathcal{N}_{i+1}\oplus\mathcal{N}_{i}^{\prime}$, because
these subspaces are linearly independent.

We show that this is a direct consequence of the fact that
$\|N_{i+2}^{\prime}N_{i+1}N_{i}^{\prime}\|\leq\frac{1}{2}-\frac{\chi}{2}$ and
how when constructing $\mathcal{N}_{i}^{\prime}$ we “cut out” the part of
$\mathcal{N}_{i}$ that is almost parallel to the image of $N^{e}$. Note that
this linear independence is also a consequence of the first inequality in the
following lemma. This does not show that all the subspaces $\mathcal{N}_{i}$
or $\mathcal{N}_{i}^{\prime}$ are nonzero.

We show the linear independence as follows. Suppose that
$n_{i}\in\mathcal{N}_{i}$ for $i$ even and $n_{i}\in\mathcal{N}_{i}^{\prime}$
such that

$\displaystyle\sum_{i\,even}n_{i}=-\sum_{i\,odd}n_{i}.$ (27)

By nonconsecutive orthogonality, Equation (27) shows that

$\displaystyle\sum_{i\,even}|n_{i}|^{2}=|\sum_{i\,even}n_{i}|^{2}=|\sum_{i\,odd}n_{i}|^{2}=\sum_{i\,odd}|n_{i}|^{2}.$
(28)

However, applying $1-N^{e}$ to Equation (27) also shows that for $i$ odd

$0=|\sum_{i\,even}(1-N^{e})n_{i}|^{2}=|\sum_{i\,odd}(1-N^{e})n_{i}|^{2}.$

Following the calculation below in Equation (29), we see that

$|((1-N^{e})n_{i},(1-N^{e})n_{i+2})|=|(Y_{i+2}^{\prime}N_{i+1}Y_{i}^{\prime}n_{i},n_{i+2})|\leq\|Y_{i+2}^{\prime}N_{i+1}Y_{i}^{\prime}\||n_{i}||n_{i+2}|.$

So, by Equation 4,

$0=|\sum_{i\,odd}(1-N^{e})n_{i}|^{2}\geq(1-2(1/2-\chi/2))\sum_{i\,odd}|(1-N^{e})n_{i}|^{2}\geq\chi(1/2-\eta)\sum_{i\,odd}|n_{i}|^{2}.$

This implies that $n_{i}=0$ for $i$ odd and hence $n_{i}=0$ for all $i$ by
Equation (28).

######  Lemma 14.12.

There are constants $C_{1}=C_{1}(\chi,\eta)\geq 1$ and
$\alpha=\alpha(\chi,\eta)\in(0,1)$ such that for any
$y_{i}\in\mathcal{Y}_{i}$, there are (unique) $n^{i}_{j}\in\mathcal{N}_{j}$
for $j$ even and $n^{i}_{j}\in\mathcal{N}_{j}^{\prime}$ for $j$ odd such that
$U^{\perp}y_{i}=\sum_{j}n^{i}_{j}$ and $|n_{j}^{i}|\leq
C_{1}\alpha^{|i-j|}|y_{i}|$.

Consequently, for $c_{\alpha}=(1+\alpha+\alpha^{-1})$ and
$C_{2}=c_{\alpha}C_{1},\|Y_{j}UY_{i}\|\leq C_{2}\alpha^{|i-j|}.$

###### Proof.

Note that for the proof of the first part, it will be important to consider
different values of $|n_{j}^{i}|$ for the same unit vector
$n_{j}^{i}/|n_{j}^{i}|$. So, for the proof we will write
$n_{j}^{i}=a_{j}^{i}m_{j}^{i}$, where $m_{j}^{i}$ is always a unit vector
(even if $|a_{j}^{i}|=|n_{j}^{i}|=0$).

We first prove the second result. Note that because $C_{2}\geq 1/\alpha$, the
result is trivial for $|i-j|\leq 1$. If $|i-j|\geq 2$ then $\mathcal{Y}_{i}$
and $\mathcal{Y}_{j}$ are orthogonal, so $Y_{j}UY_{i}=-Y_{j}U^{\perp}Y_{i}$.
Then with the first result, we know that for a unit vector
$y_{i}\in\mathcal{Y}_{i}$ we can write $U^{\perp}y_{i}=\sum_{k}n_{k}^{i}$
where $n^{i}_{k}\in\mathcal{N}_{k}$ for $k$ even,
$n^{i}_{k}\in\mathcal{N}_{k}^{\prime}$ for $k$ odd, and $|n_{k}^{i}|\leq
C_{1}\alpha^{|i-k|}$. Then

$|Y_{j}U^{\perp}y_{i}|=|\sum_{k}Y_{j}n_{k}^{i}|\leq|n_{j-1}^{i}|+|n_{j}^{i}|+|n_{j+1}^{i}|\leq
c_{\alpha}C_{1}\alpha^{|i-j|}.$

So, we now prove the first part. Let $y_{i}\in\mathcal{Y}_{i}$. By definition
of $U^{\perp}$, we can write $U^{\perp}y_{i}$ as a linear combination of unit
vectors $m^{i}_{j}\in\mathcal{N}_{j}$ for $j$ even and
$m^{i}_{j}\in\mathcal{N}_{j}^{\prime}$ for $j$ odd. Removing some elements
from $\mathbb{N}\cap[1,n_{b}]$ we obtain a set $S$ such that
$\\{m_{s}^{i}\\}_{s\in S}$ is linearly independent. Note that by the previous
remark, we are simply assuring that
$\mathcal{N}_{s},\mathcal{N}_{s}^{\prime}\neq 0$ for all $s\in S$.

What we want to do is to take advantage of the properties
$\mathcal{N}_{s}^{\prime}$. Because $N^{e}\leq U^{\perp}$, we will isolate the
$a_{s}^{i}$ for $s$ odd by applying $(1-N^{e})$ to our representation of
$U^{\perp}y_{i}$. This gives
$(1-N^{e})U^{\perp}y_{i}=\sum_{s\,odd}a_{s}^{i}(1-N^{e})m_{s}^{i}$. We want to
find relationships between the inner products of the terms
$(1-N^{e})m_{s}^{i}$ for $s$ odd and use them to obtain control of the
$a^{i}_{s}$ for $s$ odd. We then extend this control to $s$ even.

We focus on $s,t$ odd. The first statement of Lemma 14.5 implies that
$N_{a}N_{b}=0$ if $|a-b|\geq 2$. Consequently
$(1-N^{e})m_{s}^{i}=(1-N_{s-1}-N_{s+1})m_{s}^{i}=m_{s}^{i}-N_{s-1}m_{s}^{i}-N_{s+1}m_{s}^{i}\in\mathcal{N}_{[s-1,s+1]}$.
So, if $((1-N^{e})m_{s}^{i},(1-N^{e})m_{t}^{i})\neq 0$ then
$\operatorname{dist}([s-1,s+1],[t-1,t+1])\leq 1$ and since $s,t$ are odd, we
have $|s-t|\leq 2$. In the case $s=t$, we have $|(1-N^{e})m_{s}^{i}|^{2}\geq
1/2-\eta$ by Equation (24).

For $|s-t|=2$, we can assume that $t=s+2$. Then, roughly speaking, the only
contribution to the inner product comes from the orthogonality of the ranges
of $N_{s+1}N_{s}^{\prime}$ and $N_{s+1}N_{s+2}^{\prime}$ which will give some
control by the last statement of Lemma 14.5. In more detail, we have the
orthogonal decomposition,
$m_{s}^{i}=Y_{s-1}^{\prime}m_{s}^{i}+Y_{s+1}^{\prime}m_{s}^{i}+(1-Y_{s-1}^{\prime}-Y_{s+1}^{\prime})m_{s}^{i}$
from which we can set $c_{s}=|Y_{s-1}^{\prime}m_{s}^{i}|$ and
$d_{s}=|Y_{s+1}^{\prime}m_{s}^{i}|$ so that $c_{s}^{2}+d_{s}^{2}\leq 1$.
Recall that $t=s+2$ so $N_{s+1}=N_{t-1}$ and using the fact that the
$Y_{a}^{\prime}$ commute we see that

$\displaystyle|((1-$ $\displaystyle
N^{e})m_{s}^{i},(1-N^{e})m_{s+2}^{i})|=|((1-N^{e})m_{s}^{i},m_{s+2}^{i})+((1-N^{e})m_{s}^{i},N^{e}m_{s+2}^{i})|$
$\displaystyle=|(1-N^{e})m_{s}^{i},m_{s+2}^{i})|=((1-N_{s-1}-N_{s+1})m_{s}^{i},m_{s+2}^{i})|$
$\displaystyle=|(N_{s+1}m_{s}^{i},m_{s+2}^{i})|=|(Y_{s+2}^{\prime}Y_{s+1}^{\prime}N_{s+1}Y_{s+1}^{\prime}Y^{\prime}_{s}m_{s}^{i},m_{s+2}^{i})|$
$\displaystyle=|((Y_{s+2}^{\prime}N_{s+1}Y^{\prime}_{s})Y_{s+1}^{\prime}m_{s}^{i},Y_{s+1}^{\prime}m_{s+2}^{i})|$
$\displaystyle\leq
d_{s}c_{s+2}\|Y_{s+2}^{\prime}N_{s+1}Y_{s}^{\prime}\|\leq(1/2-\chi/2)d_{s}c_{s+2}.$
(29)

Then because
$(1-N^{e})U^{\perp}y_{i}=\sum_{s\,odd}a_{s}^{i}(1-N^{e})m_{s}^{i}$, for any
odd $t$ we have

$\left((1-N^{e})m^{i}_{t},(1-N^{e})U^{\perp}y_{i}-\sum_{s\,odd}a^{i}_{s}(1-N^{e})m^{i}_{s}\right)=0$

so

$((1-N^{e})m^{i}_{t},(1-N^{e})U^{\perp}y_{i})=\sum_{s\,odd}a^{i}_{s}((1-N^{e})m^{i}_{t},(1-N^{e})m^{i}_{s}).$

We express this as a matrix equation, but first list the odd elements $s$ in
$S$ in increasing order $s_{1},s_{2},\dots$. We let $x$ be some small positive
number, which we will choose later. Then setting
$\vec{v}_{k}=\frac{2(1+x)}{1-2\eta}((1-N^{e})m^{i}_{s_{k}},(1-N^{e})U^{\perp}y_{i})$,
$\vec{a}_{l}=a^{i}_{s_{l}}$, and
$M_{k,l}=\frac{2(1+x)}{1-2\eta}((1-N^{e})m^{i}_{s_{k}},(1-N^{e})m^{i}_{s_{l}}))$,
we get $M\vec{a}=\vec{v}$. Once we show that $M$ is invertible, we will obtain
a representation of $\vec{a}$ as $M^{-1}\vec{v}$ and then will use the
properties of $M$ to get control of the $a_{s}^{i}$.

Note that the scaling factor is so that the bounds on the diagonal entries of
$M$ are much clearer. In particular, by construction $M$ is a tridiagonal
self-adjoint matrix and we have the inequalities:
$M_{k,k}\geq\frac{2(1+x)}{1-2\eta}(1/2-\eta)=1+x\geq(c_{s_{k}}^{2}+d_{s_{k}}^{2})+x$
and $|M_{k,k+1}|\leq\frac{(1+x)(1-\chi)}{(1-2\eta)}d_{s_{k}}c_{s_{k+1}}$ if
$s_{k+1}=s_{k}+2$ and $M_{k,k+1}=0$ otherwise.

Now, because $\eta<\chi/4$, we have that $x=\frac{\chi}{2-2\chi}>0$ so
$M_{k,k}\geq 1+x$ and $|M_{k,k+1}|\leq d_{s_{k}}c_{s_{k+1}}$. By Lemma 4.4,
$M-xI$ is positive, so all the eigenvalues of $M$ are at least $x$.
Proposition 4.2 shows that there are constants
$\tilde{C}>0,\tilde{\alpha}\in(0,1)$ such that
$|(M^{-1})_{l,k}|\leq\tilde{C}\tilde{\alpha}^{|l-k|}$ and these constants only
depend on $x$ and an upper bound on the spectrum of $M$, which can be taken to
be $7(1+x)/(1-2\eta)$.

Now, $N^{e}$ and $U^{\perp}$ commute and
$U^{\perp}m^{i}_{s_{k}}=m^{i}_{s_{k}}$ so we see that

$U^{\perp}(1-N^{e})m^{i}_{s_{k}}=(1-N^{e})U^{\perp}m^{i}_{s_{k}}=(1-N^{e})m^{i}_{s_{k}}\in\mathcal{N}_{[s_{k}-1,s_{k}+1]}\subset\mathcal{Y}_{[s_{k}-1,s_{k}+1]}.$

Because
$\vec{v}_{k}=\frac{2(1+x)}{1-2\eta}((1-N^{e})m^{i}_{s_{k}},U^{\perp}y_{i})$
and $y_{i}\in\mathcal{Y}_{i}$, we see that $\vec{v}_{k}=0$ for $|s_{k}-i|\geq
3$. The increasing sequence of odd integers $s_{1},s_{2},\dots$ might have
gaps. These gaps cause $M$ to be a block diagonal matrix, each block being a
tridiagonal matrix. Then $M^{-1}$ also has this same block structure with
exponential decay of the entries away from the diagonal. We illustrate this
with the example that $s_{1}=5,s_{2}=7,s_{3}=11,s_{4}=13,s_{5}=15$ and so $M$
has the following block structure:

$\begin{pmatrix}M_{1,1}&M_{1,2}&&&\\\ M_{2,1}&M_{2,2}&&&\\\
&&M_{3,3}&M_{3,4}&\\\ &&M_{4,3}&M_{4,4}&M_{4,5}\\\
&&&M_{5,4}&M_{5,5}\end{pmatrix}.$

When bounding $a^{i}_{s_{l}}$ we can restrict to the block of $M$ in which
$s_{l}$ lies. Let this block be $s_{a},\dots,s_{b}$. Then for $a\leq
k,k^{\prime}\leq b$, $|s_{k}-s_{k^{\prime}}|=2|k-k^{\prime}|$. We also have
the inequality

$||s_{l}-i|-|s_{l}-s_{k}||\leq|s_{k}-i|.$

So,

$\displaystyle|a^{i}_{s_{l}}|$ $\displaystyle\leq\sum_{a\leq k\leq
b}|(M^{-1})_{l,k}||\vec{v}_{k}|\leq\frac{2(1+x)}{1-2\eta}|y_{i}|\sum_{\begin{subarray}{c}a\leq
k\leq b\\\ |s_{k}-i|\leq 2\end{subarray}}|(M^{-1})_{l,k}|\leq$
$\displaystyle\frac{2(1+x)}{1-2\eta}\tilde{C}|y_{i}|\sum_{|s_{k}-i|\leq
2}\tilde{\alpha}^{|s_{l}-s_{k}|/2}\leq\frac{2(1+x)}{1-2\eta}3\tilde{C}|y_{i}|\alpha^{-1}\tilde{\alpha}^{|s_{l}-i|/2}=:\tilde{\tilde{C}}\alpha^{|s_{l}-i|}|y_{i}|.$

Now, we can use the smallness of the odd coefficients to deduce the smallness
of the even coefficients. If $j$ is even and $|i-j|\geq 2$, because
$Y_{j}y_{i}=0$ we see that because the $m_{k}^{i}$ are unit vectors,

$\displaystyle|a_{j}^{i}|$
$\displaystyle=\left|Y_{j}(\sum_{s\,even}a_{s}^{i}m_{s}^{i})\right|=\left|Y_{j}(y_{i}-\sum_{s\,odd}a_{s}^{i}m_{s}^{i})\right|=|Y_{j}(a_{j-1}^{i}m_{j-1}^{i}+a_{j+1}^{i}m_{j+1}^{i})|$
$\displaystyle\leq\tilde{\tilde{C}}(\alpha^{|i-j|+1}+\alpha^{|i-j|-1})=\tilde{\tilde{C}}(\alpha+\alpha^{-1})\alpha^{|i-j|}.$

Setting $C_{1}=\tilde{\tilde{C}}(\alpha+\alpha^{-1})$, we obtain the result. ∎

##  15 Properties of $\mathcal{U}$ and $\mathcal{W}$

We prove some properties of $\mathcal{U}$ and $\mathcal{W}$ here that will be
used to complete the proof of Lemma 7.1. We begin with the first property that
was motivated by Section 12.

This result is stated (albeit with a different exponent of $l_{b}$) in [1] and
the proof is based on that in [1], supplemented by adjustments from [3].

######  Lemma 15.1.

There is a(n explicit) constant $C_{3}$ depending only on $\eta$ such that for
$l_{b}$ large and $u\in\mathcal{U}$,

$|Au|\geq\sqrt{\frac{1}{C_{3}l_{b}}}|u|.$

It suffices that $l_{b}$ is large enough that
$n_{b}T(l_{b})<((1-\sqrt{1-\eta})/6)^{2}$ and also large enough specified by
Lemma 14.2.

###### Proof.

Recall that $|Au|=(u,\rho u)$. It suffices to show that there is a constant
$C<1$ such that for $w$ in the range of $E_{[0,1/l_{b}]}(\rho)$, $|Uw|\leq
C|w|$. This is because if this is so then using the orthonormal
eigendecomposition of $\rho$ expressed in bra-ket notation
$\rho=\sum_{\lambda}\lambda|v_{\lambda}\rangle\langle v_{\lambda}|$ gives

$\displaystyle(u,\rho u)$
$\displaystyle\geq\frac{1}{l_{b}}\sum_{\lambda>1/l_{b}}|(v_{\lambda},u)|^{2}=\frac{1}{l_{b}}|E_{(1/l_{b},\infty)}(\rho)u|^{2}=\frac{1}{l_{b}}(|u|^{2}-|E_{[0,1/l_{b}]}(\rho)u|^{2})$
$\displaystyle=\frac{1}{l_{b}}(|u|^{2}-\max_{|v|=1}|(v,E_{[0,1/l_{b}]}(\rho)u)|^{2})=\frac{1}{l_{b}}\left(|u|^{2}-\max_{E_{[0,1/l_{b}]}(\rho)v=v,|v|=1}|(v,u)|^{2}\right)$
$\displaystyle\geq\frac{1}{l_{b}}(|u|^{2}-C^{2}|u|^{2})=\frac{1-C^{2}}{l_{b}}|u|^{2}.$
(30)

If $w$ is in the range of $E_{[0,1/l_{b}]}(\rho)$, we have
$n_{i}\in\mathcal{N}_{i}$, satisfying Item 3 of Lemma 14.5. Because
$U^{\perp}\geq N^{e},N_{i}^{\prime}$, we see that $Un_{i}=0$ for $i$ even and
$Un_{i}=U(N_{i}-N_{i}^{\prime})n_{i}$ for $i$ odd. Now, like in the proof of
Lemma 14.12, we will obtain control of the terms $n_{i}$ for $i$ odd and then
extend this control to the rest of terms. The difficulty is that there is no
clear way to obtain an approximate decomposition as below of $w\sim
w^{even}+w^{odd}$ that are approximately (for $l_{b}$ or $n_{b}$ large)
orthogonal. So, we work around this.

Let $w^{even}=\sum_{i\,even}n_{i}$ and $w^{odd}=\sum_{i\,odd}n_{i}$, so $w$ is
approximately equal to $w^{even}+w^{odd}$, as $|w-w^{even}-w^{odd}|\leq
T(l_{b})\sqrt{n_{b}}|w|$. Also,

$|Uw-Uw^{odd}|=|U(w-\sum_{i}n_{i})|\leq|w-\sum_{i}n_{i}|\leq
T(l_{b})\sqrt{n_{b}}|w|.$

For $s=1,3$, let $[s]$ be the set of all natural numbers equivalent to $s$
modulo four. Define $w^{1}$ and $w^{3}$ by
$w^{s}=\sum_{i\in[s]}(N_{i}-N_{i}^{\prime})n_{i}$. So, $w^{s}$ is expressed as
a series of orthogonal vectors and such that
$U(w^{1}+w^{3})=U(N_{i}-N_{i}^{\prime})w^{odd}=Uw^{odd}$.

Now because $(w^{1},w^{3})=0$,

$\displaystyle|U^{\perp}$
$\displaystyle(w^{1}+w^{3})|^{2}=|U^{\perp}w^{1}|^{2}+|U^{\perp}w^{3}|^{2}+2\operatorname{Re}(U^{\perp}w^{1},w^{3})$
$\displaystyle\geq|U^{\perp}w^{1}|^{2}+|U^{\perp}w^{3}|^{2}-2|(Uw^{1},Uw^{3})|\geq|U^{\perp}w^{1}|^{2}+|U^{\perp}w^{3}|^{2}-|Uw^{1}|^{2}-|Uw^{3}|^{2}.$

By Equation (25), for a unit vector
$n\in\mathcal{N}_{i}\ominus\mathcal{N}_{i}^{\prime}$ we know that
$|U^{\perp}n|^{2}\geq|N^{e}n|^{2}>1/2+\eta$. We can apply this to
$n=(N_{i}-N_{i}^{\prime})n_{i}$. So, if $i,j\in[s]$ are not equal then
$|i-j|\geq 4$. Then if $n_{i}\in\mathcal{N}_{i}$ then
$U^{\perp}(N_{i}-N_{i}^{\prime})n_{i}=(N_{i+1}+N_{i-1})(N_{i}-N_{i}^{\prime})n_{i}\in\mathcal{N}_{[i-1,i+2]}$
and hence $U^{\perp}(N_{i}-N_{i}^{\prime})n_{i}\perp
U^{\perp}(N_{i}-N_{i}^{\prime})n_{j}$. This implies that

$\displaystyle|U^{\perp}w^{s}|^{2}$
$\displaystyle=|\sum_{i\in[s]}U^{\perp}(N_{i}-N_{i}^{\prime})n_{i}|^{2}=\sum_{i\in[s]}|U^{\perp}(N_{i}-N_{i}^{\prime})n_{i}|^{2}$
$\displaystyle\geq(1/2+\eta)\sum_{i\in[s]}|(N_{i}-N_{i}^{\prime})n_{i}|^{2}=(1/2+\eta)|w^{s}|^{2}.$

Therefore,

$\displaystyle 0$ $\displaystyle\leq
2(|U^{\perp}w^{s}|^{2}-(1/2+\eta)|w^{s}|^{2})=2|U^{\perp}w^{s}|^{2}-|w^{s}|^{2}-2\eta|w^{s}|^{2}$
$\displaystyle=|U^{\perp}w^{s}|^{2}-|Uw^{s}|^{2}-2\eta|w^{s}|^{2}.$

Hence we obtain $|U^{\perp}(w^{1}+w^{3})|^{2}\geq
2\eta(|w^{1}|^{2}+|w^{3}|^{2})=2\eta|w^{1}+w^{3}|^{2}$, so

$\displaystyle|Uw|$
$\displaystyle\leq|U(w^{1}+w^{3})|+T(l_{b})\sqrt{n_{b}}|w|\leq\sqrt{1-2\eta}|w^{1}+w^{3}|+T(l_{b})\sqrt{n_{b}}|w|$
$\displaystyle=\sqrt{1-2\eta}|w^{odd}|+T(l_{b})\sqrt{n_{b}}|w|.$

Now, we now will try to give an upper bound of $|Uw|$ in terms of $|w|$ based
on the cases when $|N^{e}w|$ is small and when it is not really that small.
When $|N^{e}w|/|w|$ is not too small, we can use

$|Uw|=|U(1-N^{e})w|\leq|(1-N^{e})w|=\sqrt{|w|^{2}-|N^{e}w|^{2}}.$

When $|N^{e}w|/|w|$ is small, we remember the third equation of Item 3 of
Lemma 14.5 which gives
$|w^{even}|\leq\sqrt{|N^{e}w||w|+T(l_{b})\sqrt{n_{b}}|w|^{2}}$ and hence by
what we have done:

$\displaystyle|Uw|$
$\displaystyle\leq\sqrt{1-2\eta}|w^{odd}|+T(l_{b})\sqrt{n_{b}}|w|\leq\sqrt{1-2\eta}|w-w^{even}|+(1+\sqrt{1-2\eta})T(l_{b})\sqrt{n_{b}}|w|$
$\displaystyle\leq\sqrt{1-2\eta}|w|+\sqrt{1-2\eta}\sqrt{|N^{e}w||w|+T(l_{b})\sqrt{n_{b}}|w|^{2}}+2T(l_{b})\sqrt{n_{b}}|w|$
$\displaystyle\leq\sqrt{1-2\eta}(1+\sqrt{|N^{e}w|/|w|})|w|+(\sqrt{1-2\eta}\sqrt[4]{n_{b}}+2\sqrt{n_{b}})\sqrt{T(l_{b})}|w|,$

if we impose $T(l_{b})\leq 1$. Recall that $\eta<\chi/4<1/4$ and consider
$p=\left(\sqrt{\frac{1-\eta}{1-2\eta}}-1\right)^{2}$. Then $p>0$ and because
$\eta<3/7$, $p<1$. Then for $|N^{e}w|\leq p|w|$, the latter estimate gives
$|Uw|\leq\sqrt{1-\eta}|w|+3\sqrt{n_{b}T(l_{b})}|w|$. If $|N^{e}w|>p|w|,$ then
the first estimate gives $|Uw|\leq\sqrt{1-p^{2}}|w|$.

So, picking $l_{b}$ large enough that
$3\sqrt{n_{b}T(l_{b})}<(1-\sqrt{1-\eta})/2$ and we obtain $C_{3}$ using (30)
and $C=\max\left(\frac{1+\sqrt{1-\eta}}{2},\sqrt{1-p^{2}}\right)$. ∎

Note that, as discussed above, this result implies that $A$ is injective on
$\mathcal{U}$. Other consequence are the following inequalities.

######  Lemma 15.2.

For $l_{b}$ large (determined by Lemma 14.2 and Lemma 15.1), we have:

  1. 1.

For $w\in\mathcal{W}$, there are $x_{i}\in\mathcal{X}_{i}$ such that
$w=\sum_{i}x_{i}$ and

$|w|\geq\sqrt{\frac{1}{C_{3}l_{b}}}\sqrt{\sum_{i}|x_{i}|^{2}}.$

  2. 2.

Let $x\in\mathcal{X}$ and $y\in\mathcal{Y}$ such that $x=Ay$. Then

$|(1-P)x|\leq C_{4}\sqrt{\frac{G(l_{b})}{l_{b}}}|y|,$

where
$C_{4}=C_{1}\sqrt{2c_{\alpha}}\left(\displaystyle\frac{1+\alpha}{1-\alpha}\right).$

  3. 3.

Let $x\in\mathcal{X}$ and $x_{i}\in\mathcal{X}_{i}$ such that
$x=\sum_{i}x_{i}$, then

$|(1-P)x|\leq C_{4}\sqrt{\frac{G(l_{b})}{l_{b}}}\sqrt{\sum_{i}|x_{i}|^{2}}$

###### Proof.

For the proof of the first item, note that for $w\in\mathcal{W}$, there is a
(unique) $u\in\mathcal{U}$ such that $w=Au$ so

$|w|\geq\sqrt{\frac{1}{C_{3}l_{b}}}|u|.$

Now, $\mathcal{U}\subset\mathcal{R}$, so there are orthogonal
$r_{i}\in\mathcal{R}_{i}$ (because the spaces themselves are orthogonal) such
that $\sum_{i}r_{i}=u$, hence $|u|^{2}=\sum_{i}|r_{i}|^{2}$. Now,
$w=Au=\sum_{i}Ar_{i}$, so if we set $x_{i}=Ar_{i}\in\mathcal{X}_{i}$, we
obtain $w=\sum_{i}x_{i}$. Because $A$ is an isometry when restricted to each
$\mathcal{R}_{i}$, $|x_{i}|=|r_{i}|$ hence we obtain the estimate

$|w|\geq\sqrt{\frac{1}{C_{3}l_{b}}}|u|=\sqrt{\frac{1}{C_{3}l_{b}}}\sqrt{\sum_{i}|r_{i}^{2}|}=\sqrt{\frac{1}{C_{3}l_{b}}}\sqrt{\sum_{i}|x_{i}^{2}|}.$

We now prove the second statement. Because $x\in\mathcal{X}$, there is a
$y\in\mathcal{Y}(=\mathcal{R})$ such that $x=Ay$. Because we chose $n_{b}$
odd, we can express $y$ as the orthogonal set $\sum_{i\,odd}y_{i}$ with
$y_{i}=Y_{i}y$. We find $n_{j}^{i}\in\mathcal{N}_{j}$ for $j$ even (resp.
$\mathcal{N}_{j}^{\prime}$ for $j$ odd) such that
$U^{\perp}y_{i}=\sum_{j}n_{j}^{i}$ and $|n_{j}^{i}|\leq
C_{1}\alpha^{|i-j|}|y_{i}|$. The idea is that because $\alpha^{|i-j|}$ has
exponential decay, the following estimate is like that of an approximation of
the identity.

Recall that $\rho$ is tridiagonal (with respect to the spaces
$\mathcal{R}_{i}$) so $(n^{i_{1}}_{j_{1}},\rho n^{i_{2}}_{j_{2}})=0$ if
$|j_{1}-j_{2}|\geq 2$. We now finish the proof of the second statement of the
lemma with the following estimate

$\displaystyle|(1-P)$ $\displaystyle
x|^{2}=|(1-P)AU^{\perp}y|^{2}=|A\sum_{i}U^{\perp}y_{i}|^{2}$
$\displaystyle=|A\sum_{i}\sum_{j}n_{j}^{i}|^{2}=(\sum_{i_{1}}\sum_{j_{1}}n_{j_{1}}^{i_{1}},\rho\sum_{i_{2}}\sum_{j_{2}}n_{j_{2}}^{i_{2}})=\sum_{i_{1},j_{1},i_{2},|j_{2}-j_{1}|\leq
1}(n_{j_{1}}^{i_{1}},\rho n_{j_{2}}^{i_{2}})$
$\displaystyle\leq\sum_{i_{1},j_{1},i_{2},|j_{2}-j_{1}|\leq
1}(n_{j_{1}}^{i_{1}},\rho n_{j_{1}}^{i_{1}})^{1/2}(n_{j_{2}}^{i_{2}},\rho
n_{j_{2}}^{i_{2}})^{1/2}=\frac{2G(l_{b})}{l_{b}}\sum_{i_{1},j_{1},i_{2},|j_{2}-j_{1}|\leq
1}|n_{j_{1}}^{i_{1}}||n_{j_{2}}^{i_{2}}|$
$\displaystyle\leq\frac{2C_{1}^{2}G(l_{b})}{l_{b}}\sum_{i_{1},j_{1},i_{2},|j_{2}-j_{1}|\leq
1}\alpha^{|i_{1}-j_{1}|}|y_{i_{1}}|\alpha^{|i_{2}-j_{2}|}|y_{i_{2}}|$
$\displaystyle\leq\frac{2c_{\alpha}C_{1}^{2}G(l_{b})}{l_{b}}\sum_{i_{1},i_{2},j_{1}}\alpha^{|i_{1}-j_{1}|}|y_{i_{1}}|\alpha^{|i_{2}-j_{1}|}|y_{i_{2}}|$
$\displaystyle=\frac{2c_{\alpha}C_{1}^{2}G(l_{b})}{l_{b}}\sum_{j}\left(\sum_{i}\alpha^{|i-j|}|y_{i}|\right)^{2}=\frac{2c_{\alpha}C_{1}^{2}G(l_{b})}{l_{b}}\|\alpha^{|i|}\ast|y_{i}|\|_{L^{2}(\mathbb{Z})}^{2}$
$\displaystyle\leq\frac{2c_{\alpha}C_{1}^{2}G(l_{b})}{l_{b}}\|\alpha^{|i|}\|_{L^{1}(\mathbb{Z})}^{2}\||y_{i}|\|_{L^{2}(\mathbb{Z})}^{2}=\frac{2c_{\alpha}C_{1}^{2}G(l_{b})}{l_{b}}\left(\frac{1+\alpha}{1-\alpha}\right)^{2}|y|^{2},$

where we have used Minkowski’s inequality (Theorem 1.2.10 in [55]) and

$\|\alpha^{|i|}\|_{L^{1}(\mathbb{Z})}=1+2\alpha\sum_{i\geq
0}\alpha^{i}=1+\frac{2\alpha}{1-\alpha}=\frac{1+\alpha}{1-\alpha}.$

The last statement of the lemma follows from the second, because we can pick
$r_{i}\in\mathcal{R}_{i}$ such that $Ar_{i}=x_{i}$ so then
$|r_{i}|^{2}=|x_{i}|^{2}$. Setting $y=\sum_{i}r_{i}$ gives $Ay=x$ and
$|y|^{2}=\sum_{i}|r_{i}|^{2}$ so that

$|(1-P)x|\leq
C_{4}\sqrt{\frac{G(l_{b})}{l_{b}}}|y|=C_{4}\sqrt{\frac{G(l_{b})}{l_{b}}}\sqrt{\sum_{i}|r_{i}|^{2}}=C_{4}\sqrt{\frac{G(l_{b})}{l_{b}}}\sqrt{\sum_{i}|x_{i}|^{2}}.$

∎

##  16 Verifying Items 1, 2, and 3.

This section completes the proof of Lemma 7.1. Note the similarities between
the calculations for the spaces $\tilde{\mathcal{X}}_{i}$ in Section 8.

We first verify Item 1: $\|P^{\perp}P_{\mathcal{V}_{1}}\|\leq\epsilon_{1}$.
Let $v\in\mathcal{V}_{1}$. We will find a particular $x\in\mathcal{X}$ such
that $|v-x|$ is small and hence apply the third item of Lemma 15.2 to

$|(1-P)v|\leq|(1-P)(v-x)|+|(1-P)x|.$

Because
$\sum_{i}\tau_{i}=\sum_{i}{\mathcal{F}}^{0,\kappa}_{\omega(i)}(J)S_{1}=S_{1}$,
there is a $\textbf{x}\in\mathbb{C}^{d}$ such that
$v=S_{1}\textbf{x}=\sum_{i}\tau_{i}\textbf{x}$. Because $S_{1}$ is an isometry
$|v|=|\textbf{x}|$. Then $x_{i}=\tau_{i}(1-Z_{i})\textbf{x}\in\mathcal{X}_{i}$
and

$|v-\sum_{i=0}^{n_{win}}x_{i}|^{2}=|\sum_{i=0}^{n_{win}}\tau_{i}Z_{i}\textbf{x}|^{2}\leq
2\sum_{i=0}^{n_{win}}|\tau_{i}Z_{i}\textbf{x}|^{2}\leq
2\lambda_{min}(n_{win}+1)|\textbf{x}|^{2}=2\lambda_{min}(n_{win}+1)|v|^{2},$

where the constant $2$ comes from the calculation in equation (1), because the
ranges of $\tau_{i}$ and $\tau_{j}$ are nonconsecutively orthogonal.

Because $x_{i}=\tau_{i}(1-Z_{i})\textbf{x}$, we have that

$\sum_{i}|x_{i}|^{2}\leq\sum_{i}|\tau_{i}\textbf{x}|^{2}=\sum_{i\,odd}|\tau_{i}\textbf{x}|^{2}+\sum_{i\,even}|\tau_{i}\textbf{x}|^{2}=|\sum_{i\,odd}{\mathcal{F}}^{0,\kappa}_{\omega(i)}(J)v|^{2}+|\sum_{i\,even}{\mathcal{F}}^{0,\kappa}_{\omega(i)}(J)v|^{2}\leq
2|v|^{2},$

because the functions ${\mathcal{F}}^{0,\kappa}_{\omega(i)}(t)$ have
nonconsecutively disjoint supports so
$\|\sum_{i\,even}{\mathcal{F}}^{0,\kappa}_{\omega(i)}(J)\|$,
$\|\sum_{i\,odd}{\mathcal{F}}^{0,\kappa}_{\omega(i)}(J)\|\leq 1$. Then by the
third item of Lemma 15.2, we have that

$\displaystyle|(1-P)v|$
$\displaystyle\leq|(1-P)\sum_{i}x_{i}|+|v-\sum_{i}x_{i}|\leq
C_{4}\sqrt{\frac{G(l_{b})}{l_{b}}}\sqrt{\sum_{i}|x_{i}|^{2}}+\sqrt{2\lambda_{min}(n_{win}+1)}|v|$
$\displaystyle\leq\left(C_{4}\sqrt{\frac{2G(l_{b})}{l_{b}}}+\sqrt{2\lambda_{min}(n_{win}+1)}\right)|v|.$
(31)

We verify Item 2: $\|(1-P)JP\|\leq\epsilon_{1}$. Let $w\in\mathcal{W}$. There
is a $u\in\mathcal{U}\subset\mathcal{Y}$ such that $w=Au=AUu$. Write $u$ as
the orthogonal sum $\sum_{i\,odd}y_{i}$, where $y_{i}=Y_{i}u$. Then

$(1-P)Jw=\sum_{i}(1-P)JAUy_{i}.$

Now, we want to use the following two facts. First, each $\mathcal{X}_{k}$ is
approximately an eigenspace for $J$ with eigenvalue $\omega(k)$ so each
$\mathcal{Y}_{i}=\mathcal{X}_{[(i-1)l_{b},(i+1)l_{b})}$ (except $i=n_{b}$,
where it is $\mathcal{X}_{[(i-1)l_{b},n_{win}]}$ having length less than
$4l_{b}$) is also an approximate eigenspace with eigenvalue $\omega(il_{b})$.
Second, there is exponential decay for $Y_{j}UY_{i}$. Then we note that each
$AUy_{i}\in\mathcal{W}$ so $(1-P)J(AUy_{i})=(1-P)[J-\omega(il_{b})](AUy_{i})$.
This is the place that we use any special property of the projection $P$,
because we then remove it by using $\|1-P\|\leq 1$. This has a similar feel to
the proof of the second item of Lemma 15.2.

In more detail, by Lemma 14.12 let $y_{j}^{i}=Y_{j}Uy_{i}\in\mathcal{Y}_{j}$
for $j$ odd so $Uy_{i}=\sum_{j\,odd}y_{j}^{i}$ and $|y_{j}^{i}|\leq
C_{2}\alpha^{|i-j|}|y_{i}|$. Then

$\displaystyle|(1-$ $\displaystyle
P)Jw|^{2}=\left|\sum_{i}(1-P)[J-\omega(il_{b})]AUy_{i}\right|^{2}=\left|(1-P)\sum_{i}\sum_{j\,odd}[J-\omega(il_{b})]Ay_{j}^{i}\right|^{2}$
$\displaystyle\leq\left|\sum_{i}\sum_{j\,odd}[J-\omega(il_{b})]Ay_{j}^{i}\right|^{2}=\sum_{i_{1},i_{2}}\,\sum_{j_{1},j_{2}\,odd}\left([J-\omega(i_{1}l_{b})]Ay_{j_{1}}^{i_{1}},[J-\omega(i_{2}l_{b})]Ay_{j_{2}}^{i_{2}}\right).$

Note $Ay_{j}^{i}\in\mathcal{X}_{[(j-1)l_{b},(j+1)l_{b})}$ for $j<n_{b}$. The
following work all applies when $j=n_{b}$ except that the upper limits for
intervals and sums are both $n_{win}$. Because $\mathcal{X}_{k}$ is a subspace
of the range of ${\mathcal{F}}^{0,\kappa}_{\omega(k)}(J)$, we see that both
the $\mathcal{X}_{k}$ and the $J(\mathcal{X}_{k})$ are nonconsecutively
orthogonal. Consequently, we continue our calculation as

$\displaystyle|(1-P)$ $\displaystyle
Jw|^{2}\leq\sum_{\begin{subarray}{c}i_{1},i_{2}\\\
j_{1}\,odd\end{subarray}}\sum_{\begin{subarray}{c}j_{2}\,odd\\\
|j_{2}-j_{1}|\leq
2\end{subarray}}\left([J-\omega(i_{1}l_{b})]Ay_{j_{1}}^{i_{1}},[J-\omega(i_{2}l_{b})]Ay_{j_{2}}^{i_{2}}\right).$
(32)

We now estimate $|[J-\omega(il_{b})]Ay_{j}^{i}|^{2}$. Because
$y_{j}^{i}\in\mathcal{Y}_{j}=\mathcal{R}_{[(j-1)l_{b},(j+1)l_{b})}$, we write
it as an orthogonal sum $\sum_{k=(j-1)l_{b}}^{(j+1)l_{b}-1}r_{k}$ for
$r_{k}\in\mathcal{R}_{k}$. We then obtain

$|[J-\omega(il_{b})]Ay_{j}^{i}|^{2}=\left|[J-\omega(il_{b})]\sum_{k}Ar_{k}\right|^{2}=\sum_{k_{1},k_{2}}\left([J-\omega(il_{b})]Ar_{k_{1}},[J-\omega(il_{b})]Ar_{k_{2}}\right).$

Note that $J-\omega(k)$ restricted to $\mathcal{X}_{k}$ has norm bounded by
$\kappa$. Now, $\mathcal{R}_{k}\subset\mathcal{Y}_{j}$ for some $j$ so

$\displaystyle|[J-\omega(il_{b})]Ar_{k}|$
$\displaystyle\leq|[J-\omega(k)]Ar_{k}|+|\omega(k)-\omega(jl_{b})||Ar_{k}|+|\omega(il_{b})-\omega(jl_{b})||Ar_{k}|$
$\displaystyle\leq
2\kappa(1+(1+|i-j|)l_{b})|Ar_{k}|=2\kappa(1+(1+|i-j|)l_{b})|r_{k}|.$

Let $C_{i,j}:=2\kappa(1+(2+|i-j|)l_{b})$ to account for the cases $j<n_{b}$
and $j=n_{b}$. So, keeping in mind that the range of $k$, (we can define
$r_{k}=0$ outside this range) we see that

$\displaystyle|[J-$
$\displaystyle\omega(il_{b})]Ay_{j}^{i}|^{2}=\sum_{k_{1}}\sum_{|k_{1}-k_{2}|\leq
1}\left([J-\omega(il_{b})]Ar_{k_{1}},[J-\omega(il_{b})]Ar_{k_{2}}\right)$
$\displaystyle\leq C_{i,j}^{2}\sum_{k_{1}}\sum_{|k_{1}-k_{2}|\leq
1}|r_{k_{1}}||r_{k_{2}}|=C_{i,j}^{2}\sum_{\sigma=-1}^{1}\sum_{k_{1}}|r_{k}||r_{k+\sigma}|$
$\displaystyle\leq
C_{i,j}^{2}\sum_{\sigma=-1}^{1}\left(\sum_{k}|r_{k}|^{2}\right)^{1/2}\left(\sum_{k}|r_{k+\sigma}|^{2}\right)^{1/2}$
$\displaystyle\leq
3C_{i,j}^{2}\sum_{k}|r_{k}|^{2}=3C_{i,j}^{2}|y_{j}^{i}|^{2}.$

Using $2\sqrt{3}\kappa(1+(2+|i-j|)l_{b}))\leq 2\sqrt{3}(\kappa
l_{b})(3+|i-j|)=:K(3+|i-j|)$ and $C_{\alpha}=\max_{x}(|x|+3)\alpha^{|x|/2}$,
we insert our above calculations into Equation (16) to get

$\displaystyle|(1$ $\displaystyle-P)Jw|^{2}\leq
K^{2}\sum_{\begin{subarray}{c}i_{1},i_{2}\\\
j_{1}\,odd\end{subarray}}\sum_{\begin{subarray}{c}j_{2}\,odd\\\
|j_{2}-j_{1}|\leq
2\end{subarray}}(3+|i_{1}-j_{1}|)(3+|i_{2}-j_{2}|)|y_{j_{1}}^{i_{1}}||y_{j_{2}}^{i_{2}}|$
$\displaystyle\leq(C_{2}K)^{2}\sum_{\begin{subarray}{c}i_{1},i_{2}\\\
j_{1}\,odd\end{subarray}}\sum_{\begin{subarray}{c}j_{2}\,odd\\\
|j_{2}-j_{1}|\leq
2\end{subarray}}(3+|i_{1}-j_{1}|)(3+|i_{2}-j_{2}|)|y_{i_{1}}|\alpha^{|i_{1}-j_{1}|}|y_{i_{2}}|\alpha^{|i_{2}-j_{2}|}$
$\displaystyle\leq
c_{\alpha}(C_{\alpha}C_{2}K)^{2}\sum_{j\,odd}\,\sum_{i_{1},i_{2}}|y_{i_{1}}|\alpha^{|i_{1}-j|/2}|y_{i_{2}}|\alpha^{|i_{2}-j|/2}=c_{\alpha}(C_{\alpha}C_{2}K)^{2}\sum_{j\,odd}\,\left(\sum_{i}|y_{i}|\alpha^{|i-j|/2}\right)^{2}$
$\displaystyle\leq
c_{\alpha}(C_{\alpha}C_{2}K)^{2}\left(\frac{2+\alpha}{2-\alpha}\right)^{2}\sum_{k}|y_{k}|^{2}=c_{\alpha}K^{2}C_{\alpha}^{2}C_{2}^{2}\left(\frac{2+\alpha}{2-\alpha}\right)^{2}|u|^{2}=:(K_{\alpha}\kappa
l_{b}|u|)^{2}.$

Because $u\in\mathcal{U}$ with $w=Au$, Lemma 15.1 shows that

$|(1-P)Jw|\leq\kappa l_{b}K_{\alpha}\sqrt{C_{3}l_{b}}|w|=Const.\kappa
l_{b}^{3/2}|w|.$

Now, for the third item, we use the alternate characterization in Remark 7.3.
So, let $w\in\mathcal{W}$ and we will bound $P_{\mathcal{V}_{L}}(w)$. Now, by
Lemma 15.2, we can write $w=\sum x_{i}$, $x_{i}\in\mathcal{X}_{i}$ such that

$\displaystyle\sqrt{\sum_{i}|x_{i}|^{2}}\leq\sqrt{C_{3}l_{b}}|w|.$ (33)

We will bound each $P_{\mathcal{V}_{L}}(x_{i})$ using the Lieb-Robinson
estimates. Let $\hat{B}$ be a position operator on $\mathcal{B}$ being $jI$ on
$\mathcal{V}_{j}$. Then $J$ is tridiagonal with respect to these blocks so it
satisfies the conditions of Corollary 6.7 with $\Delta=2$. So,

$\|P_{\mathcal{V}_{L}}{\mathcal{F}}^{0,\kappa}_{\omega(i)}(J)P_{\mathcal{V}_{1}}\|\leq\int_{|k|\geq\frac{L-1}{2e^{2}}}|\hat{\mathcal{F}}_{0}^{0,\kappa}(k)|dk+\|\hat{\mathcal{F}}_{0}^{0,\kappa}\|_{L^{1}(\mathbb{R})}e^{-\frac{L-1}{2}}.$

By equations (17) and (20) and the definition of $\kappa$,

$\|P_{\mathcal{V}_{L}}{\mathcal{F}}^{0,\kappa}_{\omega(i)}(J)P_{\mathcal{V}_{1}}\|\leq\int_{|k|\geq\frac{L-1}{e^{2}n_{win}}}|\hat{\mathcal{F}}_{0}^{0,1}(k)|dk+\|\hat{\mathcal{F}}_{0}^{0,1}\|_{L^{1}(\mathbb{R})}e^{-\frac{L-1}{2}}=S(L),$

as defined in Section 3. Now, since $x_{i}\in\mathcal{X}_{i}$, we have that
there are $\textbf{x}_{i}\in\mathbb{C}^{d}$ such that
$x_{i}={\mathcal{F}}^{0,\kappa}_{\omega(i)}(J)S_{1}(1-Z_{i})\textbf{x}_{i}$.
We can pick $\textbf{x}_{i}$ in the kernel of $Z_{i}$ so that
$x_{i}={\mathcal{F}}^{0,\kappa}_{\omega(i)}(J)S_{1}\textbf{x}_{i}$, with
$S_{1}\textbf{x}_{i}\in\mathcal{V}_{1}$ and
$|x_{i}|^{2}=(\tau_{i}^{\ast}\tau_{i}\textbf{x}_{i},\textbf{x}_{i})\geq\lambda_{min}|\textbf{x}_{i}|^{2}=\lambda_{min}|S_{1}\textbf{x}_{i}|^{2}$.
So,

$|P_{\mathcal{V}_{L}}x_{i}|=|P_{\mathcal{V}_{L}}{\mathcal{F}}^{0,\kappa}_{\omega(i)}(J)S_{1}\textbf{x}_{i}|\leq
S(L)|S_{1}\textbf{x}_{i}|\leq\frac{S(L)}{\lambda_{min}^{1/2}}|x_{i}|.$

By Equation (33), we have

$|P_{\mathcal{V}_{L}}(w)|\leq\sqrt{n_{win}+1}\left(\sum_{i=0}^{n_{win}}|P_{\mathcal{V}_{L}}(x_{i})|^{2}\right)^{1/2}\leq
S(L)\sqrt{\frac{C_{3}(n_{win}+1)l_{b}}{\lambda_{min}}}|w|.$

So that we have gotten our estimates, we write $n_{b}\sim L^{\beta_{0}}$,
$n_{win}\sim L^{\beta_{1}}/F(L)$, $\lambda_{min}\sim
1/(L^{\beta_{2}}(n_{win}+1))\sim F(L)/L^{\beta_{1}+\beta_{2}}$, for
$\beta_{0},\beta_{1},\beta_{2}>0,$ and in the definition of $n_{win}$ we had
$\beta_{1}\leq 1$. Recall that $l_{b}\sim n_{win}/n_{b}\sim
L^{\beta_{1}-\beta_{0}}/F(L),\kappa\sim F(L)/L^{\beta_{1}}$.

We then get

$\epsilon_{3}\leq\sqrt{G(L^{\beta_{1}-\beta_{0}}/F(L))F(L)}L^{\beta_{0}/2-\beta_{1}/2}+L^{-\beta_{2}/2},$
$\epsilon_{4}\leq
Const.\frac{F(L)}{L^{\beta_{1}}}\left(\frac{L^{\beta_{1}-\beta_{0}}}{F(L)}\right)^{3/2}\sim
Const.\frac{L^{\beta_{1}/2-3\beta_{0}/2}}{F(L)^{1/2}},$

and

$\epsilon_{5}\leq Const.S(L)\sqrt{\frac{(n_{win}+1)l_{b}}{\lambda_{min}}}\sim
Const.\frac{S(L)}{F(L)^{3/2}}L^{3\beta_{1}/2+\beta_{2}/2-\beta_{0}/2}.$

So, if $\epsilon_{3}$ and $\epsilon_{4}$ have similar rates, because we are
assuming that $G(l)$ and $F(L)$ grow slower than any polynomial, we get
$\beta_{0}-\beta_{1}=\beta_{1}-3\beta_{0}=-\beta_{2}$, hence
$\beta_{0}=\beta_{1}/2$. This gives a rate of $L^{-\beta_{1}/4}$. However,
since $\beta_{1}\leq 1$, the best that this gives us is $L^{-1/4}$, which is
why we pick $\beta_{1}=1$. We pick $\beta_{2}=1/2$ and $\beta_{0}=1/2$. We get
$\gamma_{2}=1/4$.

This ends the proof of Lemma 7.1.

##  17 Constructive Aspects

A main issue with finding nearby commuting matrices numerically given some
pair of almost commuting matrices is that we would need to find matrices that
_exactly_ commute. Even if our algorithm generates commuting matrices in a
“pure” mathematical sense, we might only ever generate nearly commuting
matrices (although they might have a much small commutator than the original
pair of almost commuting matrices). Moreover, we might not be able to
distinguish numerically between an algorithm that actually solves this problem
and one that does not.

Also, there is also not an obvious way of solving this problem in a “brute
force” manner. However, if we are guaranteed that a matrix/matrices satisfying
certain properties exists/exist then we might be satisfied with an
approximation of a solution within a certain error. In particular, we
formulate Lin’s theorem and the non-constructive part of Hastings’
construction in terms of inequalities that determine an open set of some
parameterizable set of matrices. We first begin with discussing a pair of
nearly diagonal matrices.

We first begin with discussing parameterizations of unitaries and subspaces.
The introduction to [42] includes applications of parameterizations of
unitaries and also some references to other parameterizations. [42] includes
parameterizations of unitary matrices and projections on $\mathbb{C}^{n}$.
Continuing that approach, Theorem 2 in [43] gives parameterizations777There
are MATLAB functions written for these parameterizations of $\mathcal{U}(n)$
and $\mathcal{SU}(n)$ on Mathworks’ website ([44]). of all special unitary
matrices $\mathcal{SU}(n)$. [43] contains a representation of
$U(\lambda)\in\mathcal{SU}(n)$ in terms of the “parameterization matrix”
$\lambda\in M_{n}(\mathbb{R})$ as products of matrices of the form
$e^{iA\lambda_{i,j}}$ where $A$ is self-adjoint. The parameterization is for
$\lambda\in\Lambda:=[0,\pi/2]^{\frac{n^{2}-n}{2}}\times[0,\pi]^{\frac{n^{2}-n}{2}}\times[0,2\pi]^{n}.$
This implies that

$\|U(\lambda)-U(\mu)\|\leq\sum_{i,j}|\lambda_{i,j}-\mu_{i,j}|.$

Define

$\epsilon(A,B,U)=\max(\|UAU^{\ast}-\operatorname{diag}(UAU^{\ast})\|,\|UBU^{\ast}-\operatorname{diag}(UBU^{\ast})\|)$

and

$\epsilon(A,B)=\min_{U\in\mathcal{SU}(n)}\epsilon(A,B,U).$

Then the inequality

$\|\operatorname{diag}(B)\|=\|\sum_{k=1}^{n}|e_{k}\rangle B\langle
e_{k}|\|\leq n\|B\|$

suggests that finding a minimizer for $\epsilon(A,B)$ becomes harder to
calculate as $n$ grows.

Specifically, if $U_{0}$ is a minimizer in the definition of $\epsilon(A,B)$
then for any $U\in\mathcal{SU}(n)$,

$|\epsilon(A,B,U_{0})-\epsilon(A,B,U)|\leq 2(1+n)\|U_{0}-U\|.$

This implies that if we choose an explicit $\frac{\varepsilon}{2(1+n)}$-dense
subset $\Lambda_{0}$ of $\Lambda$ with respect to the $\ell^{1}$ norm, then we
are guaranteed to have a $\lambda_{0}\in\Lambda_{0}$ such that
$|\epsilon(A,B,U_{0})-\epsilon(A,B,U(\lambda_{0}))|\leq\varepsilon$ by just
searching through all elements of $\Lambda_{0}$.

This shows that, in principle, we can find a close commuting pair
$A^{\prime},B^{\prime}$ near $A,B$ according to the following reformulation of
Lin’s theorem.

($Q^{\prime\prime\prime}$): For $A,B$ self-adjoint contractions with small
commutator, there is a unitary matrix $U$ such that $UAU^{\ast},UBU^{\ast}$
are (jointly) nearly diagonal.

######  Proposition 17.1.

Lin’s theorem and ($Q^{\prime\prime\prime}$) are equivalent.

###### Proof.

That is, suppose $A,B$ have nearby self-adjoint commuting matrices
$A^{\prime},B^{\prime}$. Then pick $U$ to be a unitary matrix such that
$UA^{\prime}U^{\ast},UB^{\prime}U^{\ast}$ are diagonal. Then
$\|UAU^{\ast}-UA^{\prime}U^{\ast}\|=\|A-A^{\prime}\|,\|UBU^{\ast}-UB^{\prime}U^{\ast}\|=\|B-B^{\prime}\|$.

If we have a $U$ such that $UAU^{\ast},UBU^{\ast}$ are nearly diagonal, then
there are diagonal $D_{A},D_{B}$ such that $U^{\ast}D_{A}U,U^{\ast}D_{B}U$
commute and $\|U^{\ast}D_{A}U-A\|,\|U^{\ast}D_{B}U-B\|$ are small. ∎

The following is a “constructive bootstrap” which provides a brute force
algorithm for giving a projection $P$ with certain constraints along the lines
of ($Q^{\prime}$), ($Q^{\prime\prime}$) or Lemmas 7.1, 7.4, or 12.1. These
results show that _if_ there exists a projection satisfying certain
inequalities and then using a parameterization, we can demonstrate a nearby
projection that also satisfies slightly weaker inequalities.

######  Lemma 17.2.

For any $\epsilon\in(0,1)$, there is a $\delta>0$ such that if $A,B$ are self-
adjoint matrices with $\|A\|,\|B\|\leq 1$ and $\|[A,B]\|\leq\delta$ then we
can construct a projection $P$ such that $\|[P,B]\|\leq\epsilon$ and
$E_{[-1,-1/2]}(A)\leq P\leq 1-E_{[1/2,1]}(A)$.

###### Proof.

Apply Lemma 12.1 with $\epsilon/2$ instead of $\epsilon$. This means that the
$\delta>0$ (which is undetermined) for this lemma will be less than the
$\delta$ gotten by applying Lemma 12.1 without being able to construct the
projection.

Consider the set $\mathfrak{P}$ of projections in $M_{n}(\mathbb{C})$ such
that $E_{[-1,-1/2]}(A)\leq P\leq 1-E_{[1/2,1]}(A)$. (Note that this set
depends only on $A$.) What Lemma 12.1 states is that

$M(\delta)=\max_{A,B\in
B(M_{n}(\mathbb{C})_{sa}),\|[A,B]\|<\delta}\min_{P\in\mathfrak{P}}\|[P,B]\|<\epsilon/2.$

An algorithm for finding a $P$ in $\mathfrak{P}$ such that
$\|[P,B]\|\leq\epsilon$ is to find projections $P_{1},\dots,P_{m}$ in
$\mathfrak{P}$ such that
$B_{P_{k}}(\epsilon/4)=\\{P\in\mathfrak{P}:\|P-P_{k}\|<\epsilon/4\\}$ cover
$\mathfrak{P}$. Once this is done, we note that by searching through the
$P_{k}$, we can find one such that $\|P_{k}-P\|<\epsilon/4$ and hence
$\|[P_{k},B]\|\leq 2\|P_{k}-P\|+\|[P,B]\|\leq\epsilon.$

The projections $P_{1},\dots,P_{m}$ can be found as follows. Let
$u_{1},\dots,u_{r}$; $u_{r+1},\dots,u_{s-1}$; and $u_{s},\dots,u_{n}$ be
orthonormal bases for the ranges of $E_{[-1,-1/2]}(A),E_{(-1/2,1/2)}(A)$, and
$E_{[1/2,1]}(A)$, respectively. Let $U$ be the unitary matrix with columns
$u_{i}$.

Let $\mathfrak{P}^{\prime}$ be the set of projections in
$M_{n^{\prime}}(\mathbb{C})$, where $n^{\prime}=s-r-1$. This set can be
parameterized according to [42]. We want to find projections
$P_{k}^{\prime}\in\mathfrak{P}^{\prime}$ such that open balls
$B_{P_{k}^{\prime}}^{\prime}(\epsilon/4)=\\{P\in\mathfrak{P}^{\prime}:\|P-P_{k}\|<\epsilon/4\\}$
cover $\mathfrak{P}^{\prime}$. The parameterization from [42] of projections
of dimension $m$ is gotten by forming the matrix $S_{m}\in M_{n^{\prime}}$
whose columns are $e_{1},\dots,e_{m}$ and multiplying this on the left by
parameterized unitary matrices $U_{CS}$, expressed as the product of
$2m(n^{\prime}-m)$ many matrices of the form $e^{iA\lambda_{i,j}}$ where $A$
is self-adjoint. These are the same unitaries as before, except with a
restriction on the parameterization matrix, so as to effectively give
$\lambda\in[0,2\pi]^{m(n^{\prime}-m)}\times[0,\pi/2]^{m(n^{\prime}-m)}$. As
before, we would need a subset of this parameterization space that is
$\epsilon/4\sqrt{n^{\prime}}$-dense with respect to the $\ell^{1}$ norm.

We do this for all dimensions $m\leq n^{\prime}$ to obtain finitely many
projections $P_{k}^{\prime}$. Then set

$P_{k}=U\begin{pmatrix}I_{r}&&\\\ &P_{k}^{\prime}&\\\
&&I_{n-s}\end{pmatrix}U^{\ast}.$

We then let $P$ be a minimizer of

$\min_{k}\|[P_{k},B]\|\leq\epsilon.$

This concludes the construction. ∎

##  18 Almost commuting Hermitian and Normal matrices

Continuing the discussion in Section 2, Davidson in [5] also provided an
absorption result which is a weakened version of Lin’s theorem and also
different formulations of Lin’s theorem which are discussed in Section 7. The
absorption result is [5]’s Theorem 0.1 which states that for $A,B\in
M_{n}(\mathbb{C})$ self-adjoint, there exist commuting self-adjoint $C,D\in
M_{n}(\mathbb{C})$ with $\|C\|\leq\|A\|,\|D\|\leq\|B\|$ and commuting
$A^{\prime},B^{\prime}\in M_{2n}(\mathbb{C})$ such that

$\|A\oplus C-A^{\prime}\|,\|B\oplus D-B^{\prime}\|\leq 25\|[A,B]\|^{1/2}.$

In 1988, Choi, using the signature of matrices as an invariant, provided a
result similar to that of [5] of an almost commuting self-adjoint diagonal
matrix and weighted shift operator where there are no nearby commuting
matrices at all.

Earlier in 1983, Voiculescu provided the elementary counter-example for Lin’s
theorem for unitary matrices (we take the form used in [13]):

$U_{n}=\begin{pmatrix}\omega_{n}&&&\\\ &\omega_{n}^{2}&&\\\ &&\ddots&\\\
&&&\omega_{n}^{n}\end{pmatrix},\;\;\;V_{n}=\begin{pmatrix}0&&&&1\\\ 1&0&&\\\
&1&0&&\\\ &&\ddots&&\\\ &&&1&0\end{pmatrix},$

where $\omega_{n}=e^{2\pi i/n}$ is the principal $n$th root of unity. Using an
argument involving spectral projections and a result of Halmos concerning the
unilateral shift, he showed that the variant of Lin’s theorem where one
requires that the contractions be unitary, rather than Hermitian, is false.
This example, like many of the other explicit counter-examples, involves a
diagonal and weighted shift matrices. Moreover, after his proof of the result,
Voiculescu framed the problem of Lin’s theorem in terms of liftings of a
$\ast$-homomorphism $C(X)\to\mathscr{A}/\mathscr{J}$ to a map
$C(X)\to\mathscr{A}$ and hypothesized (correctly) that the second homology of
the two-sphere $S^{2}$ might have played a role in his counter-example (which
is trivial for the $2$-torus $T^{2}=S^{1}\times S^{1}$) hence “it seems rather
improbable that these examples will have direct bearing on the problem of
self-adjoint operators.”

Taking up the ideas of Voiculescu concerning liftings, Loring in 1988 in [12]
investigated almost commuting unitary matrices using $K$-theory. Loring proved
a counter-example similar to that of Davidson and conjectured that if the
$K$-theoretic obstruction vanished then there is a lifting. As an example, he
provided an illustrative absorption result similar to that of [5]’s for
Voiculescu’s unitaries where taking the direct sum with some unitary matrices
$C,D$ removes the $K$-theoretic obstruction so that there are nearby commuting
unitary matrices. In particular, he proved that there are commuting unitaries
$U,V$ such that $\|U_{n^{2}}\oplus U_{n^{2}}-U\|,\|V_{n^{2}}\oplus
V_{n^{2}}^{\ast}-V\|\leq 4\pi/n$.

Then in 1989, Exel and Loring in [13] provided an elementary winding number
argument showing that there are no commuting matrices at all that are nearby
Voiculescu’s unitaries. This winding number involved taking straight line
paths $U(t),V(t)$ from Voiculescu’s unitaries $U,V$ to any given commuting
matrices $U^{\prime},V^{\prime}$ and calculating for each $t$, the path
sending $r\in[0,1]$ to

$\gamma_{t}(r)=\det((1-r)U(t)V(t)+rV(t)U(t)).$

Using that $[U(1),V(1)]=[U^{\prime},V^{\prime}]=0$, that
$\|[U,V]\|=|1-\omega_{n}|$, and elementary properties about winding numbers in
the punctured plane, Exel and Loring obtain their result with an explicit
bound on how close $U^{\prime},V^{\prime}$ can be to $U,V$.

Later in [14] in 1991, Exel and Loring showed that a $K$-theoretic invariant
and the winding number invariant discussed above are the same (when $[U,V]$ is
small). The $K$-theoretic invariant is similar to Choi’s invariant in that it
is the signature of a matrix formed from $U$ and $V$.

Section 1 of [9] formulates various almost commuting - nearly commuting
problems under certain “geometric” restrictions. These examples include the
two that are directly related to the primary reformulations of Lin’s theorem
that was not discuss:

  1. 1.

The geometry of a square, which is
$\\{(x_{1},x_{2})\in\mathbb{R}^{2}:|x_{1}|,|x_{2}|\leq 1\\}$, giving rise to
almost commuting Hermitian $H_{1},H_{2}$ with $\|H_{1}\|,\|H_{2}\|\leq 1$, and

  2. 2.

The geometry of the disk, which is $\\{z\in\mathbb{C}:|z|\leq 1\\}$, giving
rise to an almost normal $N$ with $\|N\|\leq 1$.

Some other examples (which we will discuss below) are that of almost commuting
Hermitian and unitary matrices (which is related to the geometry of a
cylinder/anulus) and two almost commuting unitaries (the geometry of the
torus). The latter does not always have nearby commuting matrices, but [11]
showed that if both unitaries have a spectral gap then one obtains nearby
commuting unitaries. The proof given there involves using a matrix logarithm
to reduce the unitary matrices with a spectral gap into Hermitian matrices.
Similarly, an almost commuting Hermitian $A$ and unitary $B$ are nearly
commuting and the proof in [9] takes $N=AB$ as an “almost polar decomposition”
of the almost normal matrix $N$.

Both of the geometries discussed above (and more general geometries) are
addressed by Enders and Shulman in [30] providing a dimensional and cohomology
criterion for liftings in the spirit of Voiculescu’s comment in [28]. In this
section we discuss an approach to a few of these types of results following
the ideas presented in previous sections.

We make some remarks on the continuity of $f:\mathbb{R}\to\mathbb{C}$ or
$f:\mathbb{C}\to\mathbb{C}$ as a function on normal matrices. A continuous
function $f$ of a complex variable is operator continuous (see Proposition
II.2.3.3 of [54]). It is important to note that the operator modulus of
continuity of $f$ is bounded below by the modulus of continuity of $f$ as a
function of a real/complex variable. The proof in [54] shows that the operator
modulus of continuity can be chosen independent of the $C^{\ast}$-algebra. See
[35] for a more detailed analysis of the operator modulus of continuity. As
seen in a remark before Lemma 5.2 of [35], which references proofs given in
Section 10 of [36], if $f$ is a continuous function, then its operator modulus
of continuity is equivalent to its “commutator modulus of continuity”. That
is,

$\Omega_{f,\mathfrak{F}}(\delta)=\sup\\{\|f(A)-f(B)\|:A,B\mbox{
normal};\sigma(A),\sigma(B)\subset\mathfrak{F};\|A-B\|\leq\delta\\}$

is equivalent to

$\Omega_{f,\mathfrak{F}}^{\flat}(\delta)=\\{\|[f(A),R]\|:A\mbox{
normal},\sigma(A)\subset\mathfrak{F},R\mbox{ self-adjoint},\|R\|\leq
1,\|[A,R]\|\leq\delta\\}.$

For a summary of Operator Lipschitz functions and the norm
$\|-\|_{\operatorname{OL}(\mathbb{R})}$ see [34]. Note that
$\|f\|_{\operatorname{OL}(\mathbb{R})}\leq C_{f}$, which can be seen by using
the Fourier representation of $f$ and
$\|e^{ikx}\|_{\operatorname{OL}(\mathbb{R})}=|k|$ from [34]. Although $f$
being a Lipschitz function of a real/complex variable does not ensure that $f$
is Operator Lipschitz, its operator Lipschitz constant is at least its
Lipschitz constant. [34] discusses how $f$ being a Hölder continuous function
of a real variable guarantees that it is Operator Hölder continuous with an
equivalent (depending on the Hölder exponent) norm.

We present a naïve non-proof that given two commuting self-adjoint
contractions $A_{1},A_{2}$ that almost commute with the self-adjoint
contraction $B$, there exist commuting self-adjoint
$A_{1}^{\prime},A_{2}^{\prime},B^{\prime}$ that are close to $A_{1},A_{2},B$,
respectively. The idea is that because $[A_{1},A_{2}]=0$, we can
simultaneously diagonalize these matrices and hence there exists a self-
adjoint matrix $A$ whose eigenspaces are subspaces of the eigenspaces of
$A_{1}$ and the eigenspaces of $A_{2}$. Therefore, we can write
$A_{1}=f_{1}(A),A_{2}=f_{2}(A)$ for some continuous functions
$f_{1},f_{2}:\mathbb{R}\to\mathbb{R}$. We hope that $[A,B]$ is small so that
there are commuting $A^{\prime},B^{\prime}$ near $A$ and $B$, respectively and
that if we define
$f_{1}(A^{\prime})=A_{1}^{\prime},f_{2}(A^{\prime})=A_{2}^{\prime}$ then
$A_{1}^{\prime}$ is near $A_{1}$ and $A_{2}^{\prime}$ is near $A_{2}$. It is a
given that $A_{1}^{\prime},A_{2}^{\prime},B^{\prime}$ all commute, but the
other “hopes” are not guaranteed to be realizable. The first issue is the
commutator of $[A,B]$ might not be small. The second issue is that we might
not have control of how close $A_{i}^{\prime}=f_{i}(A^{\prime})$ is to $A_{i}$
if the functions $f_{i}$ depend on the original matrix $A$.

Exploring an example more in line with what we will be doing, suppose that the
spectrum of a normal matrix $N$ is a subset of the graph
$\\{(x,f(x)):x\in[-1,1]\\}$, where we identify $\mathbb{R}^{2}$ with
$\mathbb{C}$. If $f$ is a continuous function, then set
$A_{1}=(N+N^{\ast})/2$, $A_{2}=(N-N^{\ast})/2i$. There are commuting Hermitian
$A_{1}^{\prime},B^{\prime}$. Because $A_{2}=f(A_{1})$, setting
$A_{2}^{\prime}=f(A_{1}^{\prime})$ makes
$N^{\prime}=A_{1}^{\prime}+iA_{2}^{\prime}$ normal and close to $N$ because
$\|A_{2}-A_{2}^{\prime}\|=\|f(A_{1})-f(A_{1}^{\prime})\|$. We then have that
$N,B$ are nearly commuting.

What we mean by “a nice function” is that either we have one fixed continuous
function $f$ or we have a family operator equicontinuous functions
$\mathfrak{F}$ from which we pick $f$. For instance, we might want to choose a
sequence of functions $f_{n}$ that are uniformly operator Lipschitz.

To illustrate how the above naive construction can fail, consider $N$ to have
spectrum in $[0,1]^{2}$. We can perturb $N$ (very) slightly so the spectrum is
in $\\{(\frac{k+\epsilon j}{n},\frac{j}{n}):-n\leq k,j\leq n\\}$ for some
small $\epsilon>0$. Then an interpolating function $f$ will display behavior
like a saw-tooth function like with slope at least $\epsilon$ and hence has
growing operator modulus of continuity. A notable example of Davidson in [5]
is of a weighted shift operator in $M_{n}(\mathbb{C})$ (where $n-1$ is a
square) that is almost normal and almost commutes with a diagonal Hermitian
matrix. Following his use of [31], one sees that we get a normal matrix that
is unitarily equivalent to $\bigoplus_{k=0}^{M}c_{k}S_{d_{k}}$, where $S_{m}$
is a cyclic permutation matrix of length $m$;
$M=2\left\lfloor\frac{\sqrt[4]{n-2}}{2}\right\rfloor$; $n\geq 16^{4}+2=65538$;
$d_{k}\geq M/2$; and $c_{k}=\frac{M-k}{M}$. This normal matrix has spectrum in
the union of concentric circles of radii $c_{k}$ centered at the origin. The
limit points of its spectrum as $n\to\infty$ is the entire unit disk. [5]
proved that this normal matrix and a Hermitian matrix do not have nearby
commuting matrices.

A way that the above construction works is if the spectrum of $N$ lies within
a simple curve $\Gamma$ with distinct endpoints such that there is a closed
(and bounded) interval $I=[-a,a]$ and continuous functions
$f:I\to\Gamma\subset\mathbb{C}$ and $g:\mathbb{C}\to I$ such that $f$ is a
bijection and $g\circ f=\operatorname{id}_{I}$. Then if $N$ almost commutes
with $B$, $A=g(N)$ almost commutes with $B$ as discussed above. Then nearby
$A,B$ there are commuting Hermitian $A^{\prime},B^{\prime}$. Scaling
$A^{\prime}$ by a number slightly less than $1$ if necessary as in [9], we can
assume that the spectrum of $A$ is in $I$. Setting $N^{\prime}=f(A^{\prime})$,
we see that $N^{\prime}$ commutes with $B^{\prime}$ and

$\|N^{\prime}-N\|=\|f(A^{\prime})-f(A)\|$

is small when $\|[N,B]\|$ is small. If $\Gamma$ is the disjoint union of such
curves, then one can proceed in a similar way by forming block matrices gotten
by collecting the spectrum lying in different curves.

We will explore how a type of one-dimension spectrum of a normal matrix $N$
can guarantee that if $N$ and a Hermitian matrix $A$ almost commute, then
there are nearby commuting normal and Hermitian matrices. We first approach
the situation of an almost commuting Hermitian contraction $A$ and unitary
$U$.

######  Proposition 18.1.

Let $A$ be a Hermitian contraction and $U$ unitary. Then if $A,U$ are almost
commuting, they are nearly commuting (with the same asymptotic rates as in
Theorem 1.)

###### Proof.

Let $\delta=\|[A,U]\|$. Picking $\Delta=\delta^{\gamma_{0}}$, we apply
Corollary 6.4 to obtain a finite range (of distance $\Delta$ with respect to
the normal $U$) $H$ such that $\|A-H\|\leq Const.\delta^{1-\gamma_{0}}$ and
$\|[H,N]\|\leq Const.\delta^{\gamma_{0}}$.

Recall that in Section 7, where we have $B$ self-adjoint, we partitioned its
spectrum into intervals much larger than $\Delta$. We used the tridiagonal
nature of $H$ by grouping together eigenvalues of $B$ so as to apply Lemma 7.4
to a “pinching” of $H$ by certain projections to obtain the subspaces
$\mathcal{W}$.

So, we do the same here: we partition the spectrum of $U$ into arcs $I_{i}$ by
forming $n_{win}\sim\Delta^{-\gamma_{1}}/2\pi$ many intervals, where
$0<\gamma_{1}<1$. This gives the subspaces $\mathcal{B}_{i}$ on which $H$
restricted is block tridiagonal with many blocks and on which $U$ takes on
potentially many eigenvalues, but all in the interval $I_{i}$. For $H$
projected onto $\mathcal{B}_{i}$, we then obtain the almost invariant
subspaces $\mathcal{W}_{i}$ satisfying the properties specified in Lemma 7.4
including
$\tilde{\mathcal{B}}_{i}=\mathcal{W}_{i}^{\perp}\oplus\mathcal{W}_{i+1}\subset\mathcal{B}_{i}\oplus\mathcal{B}_{i+1}$.
We then have that $\tilde{\mathcal{B}}_{i}$ is almost invariant for $H$. This
construction is essentially identical, with the key distinction that although
there are “first” and “last” subspaces, we index the spaces $\mathcal{B}_{i}$
cyclically and must (at least for our construction to work) define
$\tilde{\mathcal{B}}_{n_{cut}}=\mathcal{W}_{n_{cut}}^{\perp}\oplus\mathcal{W}_{n_{cut}+1}=\mathcal{W}_{n_{cut}}^{\perp}\oplus\mathcal{W}_{1}=\tilde{\mathcal{B}}_{0}.$

Let $U^{\prime}$ be a multiple of the identity on $\tilde{\mathcal{B}}_{i}$,
with the multiple being the center of the arc $I_{i}$. We project $H$ onto the
$\tilde{\mathcal{B}}_{i}$ to obtain $H^{\prime}$ and we conclude. ∎

Note that we then obtain a stronger form of Osborne’s result in [11] only
requiring one matrix to have a spectral gap. We only need to transform one
unitary into a Hermitian matrix, but we use a modification of a fractional
linear transformation instead.

######  Proposition 18.2.

Fix $\theta\in(0,2\pi)$. Then for unitaries $U,V$ where $V$ has a spectral gap
of angular radius $\theta$, there are nearby commuting unitaries
$U^{\prime},V^{\prime}$. If $\epsilon=\epsilon(\delta)$ derived from Lin’s
theorem for a unitary and self-adjoint pair, then

$\max(\|U-U^{\prime}\|,\|V-V^{\prime}\|)\leq
2\epsilon\left(\frac{\|[U,V]\|}{1-\cos\theta}\right).$

###### Proof.

Just as in [11], we can multiply $V$ by a phase so that the spectral gap is
centered at $1$. Set $f_{\theta}(x)=\frac{x-i}{x+i}$ and
$g_{\theta}(z)=i\frac{1+z}{1-z}$. A simple calculation (or a simple comparison
to fractional linear transformations in [56]) shows that $f_{\theta}$ maps
$\mathbb{R}$ to the unit circle and $g_{\theta}$ maps the unit circle to
$\mathbb{R}$ as its inverse. Writing $\alpha=e^{i\varphi}$, one can see that

$g_{\theta}(e^{i\varphi})=-\frac{\sin\varphi}{1-\cos\varphi}.$

We set $W=g_{\theta}(V)$. We then have $\|W\|\leq 1$ and using
$\frac{x+1}{x-1}=1+\frac{2}{x-1}$ we see that

$\displaystyle\|[U,W]\|$ $\displaystyle=2\|[U,(V-1)^{-1}]\|\leq
2\|(V-1)^{-1}\|\|(V-1)U(V-1)^{-1}-U\|$ $\displaystyle\leq
2\|(V-1)^{-1}\|^{2}\|[U,V-1]\|\leq\frac{1}{1-\cos\theta}\|[U,V]\|.$

We then can find nearby commuting $U^{\prime},W^{\prime}$ where $U^{\prime}$
is unitary and $W^{\prime}$ is self-adjoint. Then
$V^{\prime}=f_{\theta}(W^{\prime})$ is unitary and we have

$\displaystyle\|V-V^{\prime}\|$
$\displaystyle\leq\|(W-i)(W+i)^{-1}-(W^{\prime}-i)(W^{\prime}+i)^{-1}\|$
$\displaystyle=2\|(W+i)^{-1}-(W^{\prime}+i)^{-1}\|\leq 2\|W-W^{\prime}\|$

by the resolvent identity calculation in Example 1 of [34]. Then we have
$\|V-V^{\prime}\|\leq 2\epsilon\left(\frac{\delta}{1-\cos\theta}\right).$ ∎

Now we can attempt to do the same sort of construction for a normal matrix $N$
whose spectrum belongs to some set $\Gamma$. We define the following condition
on a $\Gamma\subset\mathbb{C}$, but note that it is not necessarily optimal.

($\ast$): $\Gamma$ will be the union of finitely many simple curves
$\Gamma^{k}$ which include their two endpoints. Let $\\{z_{1},\dots,z_{n}\\}$
be the endpoints of the $\Gamma^{k}$. The curves $\Gamma^{k}$ are not
permitted to intersect except at the endpoints. A closed closed curve can be
included in this framework by picking two points on the curve and break the
curve into two simple curves sharing two distinct endpoints.

Let $\Delta_{0},C_{s}>0,\gamma_{1}\in(0,1)$ and $0<\Delta<\ell_{s}/2$, where
$\ell_{s}=\ell_{s}(\Delta)\sim\Delta^{\gamma_{s}}$. The constants
$C^{k},\ell^{k}$ have the same restrictions as $C_{s},\ell_{s}$, respectively.
Let
$\Gamma^{k,\Delta}=\Gamma^{k}\setminus\bigcup_{s}B_{\ell_{s}}(z_{s}),\tilde{\Gamma}^{k,\Delta,s}=(B_{l_{s}}(z_{s})\cap\Gamma^{k})\setminus
B_{l_{s}/2}(z_{s})$.

We require the following properties to hold for $\Delta\leq\Delta_{0}$:

  1. 1.

If $z_{s}$ is not an endpoint of $\Gamma^{k}$, then
$\operatorname{dist}(z_{s},\Gamma^{k})\geq\ell_{s}$.

  2. 2.

If $z_{s}$ is an endpoint of $\Gamma^{k}$, then $\Gamma^{k}$ only intersects
$\partial B_{\ell_{s}}(z_{s})$ in a single point.

  3. 3.

$\operatorname{dist}(\tilde{\Gamma}^{k,\Delta},\tilde{\Gamma}^{k^{\prime},\Delta}\cup\Gamma^{k^{\prime},\Delta})\geq(1-\delta_{k,k^{\prime}})\Delta$.

  4. 4.

Suppose that $\Gamma^{k}$ has endpoints $z_{s_{1}}$ and $z_{s_{2}}$. There is
a partition of $\Gamma^{k}$ into disjoint consecutive arcs
$A^{k,\Delta}_{1},\dots,A^{k,\Delta}_{r^{k,\Delta}}\subset\Gamma^{k,\Delta}$
satisfying the following properties:

    1. (a)

$\frac{1}{C^{k}}\ell^{k}\leq\operatorname{diam}(A^{k,\Delta}_{i})\leq
C^{k}\ell^{k}$.

    2. (b)

$\operatorname{dist}(A^{k,\Delta}_{i},A^{k,\Delta}_{i^{\prime}})\geq(1-\delta_{i,i^{\prime}})\Delta$.

    3. (c)

Each $A^{k,\Delta}_{i}$ can be broken up into consecutive subarcs
$A^{k,\Delta}_{i,j}$ each satisfying
$\operatorname{diam}(A^{k,\Delta}_{i,j})\leq C^{k}\Delta$ and
$\operatorname{dist}(A^{k,\Delta}_{i,j},A^{k,\Delta}_{i,j^{\prime}})\geq(1-\delta_{j,j^{\prime}})\Delta.$

    4. (d)

If $z_{s}$ is an endpoint of $\Gamma^{k}$ then there is a unique value
$i_{s}^{k}$ of $i$ and $j_{s}^{k}$ of $j$ so that $A^{k,\Delta,s}_{i,j}$ is
within a distance of $\Delta$ from $B_{\ell_{s}}(z_{s})$. One of the endpoints
of this subarc will then be on $\partial B_{\ell_{s}}(z_{s})$.

How small that $\Delta$ needs to be will depend on how close the $\Gamma^{k}$
are near and away from $z_{j}$. It is necessarily the case that if there are
many $\Gamma^{k}$ with endpoint $z_{s}$, then $l/\Delta$ must be large. This
is illustrated by Figure 4 below, in particular how visually near the
intersection point one can compare the size of the black “dot” formed by the
intersection of line segments depicted with positive width.

Figure 5: For a given $r>0$, compare how far one has to move from the point of
intersection so that each line is at least a distance of $r$ from the other
lines. Figure 6:  $\Gamma^{k,\Delta}$ is depicted in blue, $\partial
B_{l_{j}}(z_{j})$ in red, and $\Gamma^{k,\Delta}\cap B_{l_{s}}(z_{s})$ in
black. Although not all end points are shared by multiple curves $\Gamma^{k}$
in general, it is this case in the illustration above.

We then have the following:

######  Proposition 18.3.

Let $N$ be normal with spectrum in $\Gamma$ satisfying $(\ast)$ and $A$ self-
adjoint. Then if $A,N$ are almost commuting, they are nearly commuting.

###### Proof.

Let $\delta=\|[A,N]\|$. We apply the argument earlier to obtain $H$ finite
range with respect to $N$ of distance $\Delta\sim\delta^{\gamma_{0}}$ such
that $\|A-H\|\leq Const.\delta^{1-\gamma_{0}},\|[H,N]\|\leq Const.\delta$.
Recall $(\ast)$.

Let $\mathcal{B}^{k,\Delta}_{i}$, $\mathcal{V}^{k,\Delta}_{i,j}$ be the range
of the spectral projection of $N$ onto $A^{k,\Delta}_{i}$,
$A^{k,\Delta}_{i,j}$, respectively. We then obtain
$\mathcal{W}^{k,\Delta}_{i}$ which are subspaces of the
$\mathcal{B}^{k,\Delta}_{i}$, satisfy
$\mathcal{V}^{k,\Delta,s}_{i,1}\subset\mathcal{W}^{k,\Delta}_{i}\perp{\mathcal{V}}^{k,\Delta,s}_{i,r^{k,\Delta,s}_{i}}$,
and are almost invariant under
$P_{\mathcal{B}^{k,\Delta}_{i}}HP_{\mathcal{B}^{k,\Delta}_{i}}$. Let
$\mathcal{W}^{k,\Delta,\perp}_{i}=\mathcal{B}^{k,\Delta}_{i}\ominus\mathcal{W}^{k,\Delta}_{i}$.

We now need to deal with the subspace $\mathcal{B}^{\Delta,s}$ projected onto
by $E_{B_{l_{s}}(z_{s})}(N)$. The issue is that because $z_{s}$ can be the
endpoint of multiple curves $\Gamma^{k}$, we have to use a slightly different
approach to form almost invariant subspaces of $\mathcal{B}^{\Delta,s}$ so
that everything works out. This is the only part of the proof where one uses a
“two dimensional” grouping of eigenvalues of $N$ (using “polar coordinates”).

Fix an endpoint $z_{s}$. Let $S_{1}=B_{\ell_{s}/2}(z_{s})$,
$S_{i}^{k}=\Gamma^{k}\cap B_{(i-1)\Delta+\ell_{s}/2}(z_{s})\setminus
B_{(i-2)\Delta+\ell_{s}/2}(z_{s})$, $S_{r^{\Delta,s}}^{k}=\Gamma^{k}\cap
B_{l_{s}}(z_{s})\setminus B_{(r^{\Delta,s}-1)\Delta+\ell_{s}/2}(z_{s})$, where
$\ell_{s}/2-1<r^{\Delta,s}\Delta\leq\ell_{s}/2$. What we do is break
$\mathcal{B}^{\Delta,s}$ into orthogonal subspaces
$\mathcal{V}^{\Delta,s}_{1},\mathcal{V}^{k,\Delta,s}_{2},\dots,\mathcal{V}^{k\Delta,s}_{r^{\Delta,s}}$
by letting $E_{S_{1}}(N)$ project onto $\mathcal{V}^{\Delta,s}_{1}$ and
$E_{S_{i}^{k}}(N)$ project onto $\mathcal{V}^{k,\Delta,s}_{i}$ for $1<i\leq
r^{\Delta,s}$. Consider
$H^{\Delta,s}=P_{\mathcal{B}^{\Delta,s}}HP_{\mathcal{B}^{\Delta,s}}$ as a
block matrix with respect to the subspaces
$\mathcal{V}^{\Delta,s}_{1},\mathcal{V}^{k,\Delta,s}_{2},\dots,\mathcal{V}^{k\Delta,s}_{r^{\Delta,s}}$.

For each $k$, we restrict $H$ to
$\mathcal{B}^{k,\Delta,s}=\mathcal{V}^{\Delta,s}_{1}\oplus\bigoplus_{i=2}^{r^{\Delta,s}}\mathcal{V}^{k,\Delta,s}_{i}$
to obtain $H^{k,\Delta,s}$. $H^{k,\Delta,s}$ is tridiagonal with respect to
the subspaces
$\mathcal{V}^{\Delta,s}_{1},\mathcal{V}^{k,\Delta,s}_{2},\dots,\mathcal{V}^{k\Delta,s}_{r^{\Delta,s}}$
which correspond to a set covering $\Gamma^{k}\cup S_{1}$ in
$B_{\ell_{s}}(z_{s})$. Then there is a subspace
$\mathcal{W}^{\Delta,s}_{k}\subset\mathcal{B}^{k,\Delta,s}$ that is almost
invariant under $H^{k,\Delta,s}$ such that
$\mathcal{V}^{k,\Delta,s}_{r^{\Delta,s}}\subset\mathcal{W}^{\Delta,s}_{k}\perp\mathcal{V}^{\Delta,s}_{1}$.

Figure 7: The point $z_{s}$ is an endpoint for
$\Gamma^{1},\Gamma^{2},\Gamma^{3},$ and $\Gamma^{4}$. The small tick marks are
the intersections of circles centered at $z_{s}$ of radii $i\Delta$. The
almost invariant subspaces $\mathcal{W}^{\Delta,s}_{k}$ are illustrated in red
and $\mathcal{W}^{\perp}_{\Delta,s}$ in blue. Although these subspaces do not
necessarily lie entirely within the span of the illustrated eigenspaces of
$N$, $\mathcal{W}^{\perp}_{\Delta,s}$ contains all eigenspaces of $N$ within
distance $l_{s}/2$ of $z_{s}$ and $\mathcal{W}^{\Delta,s}_{k}$ contains the
eigenspaces depicted by part of the (red) spectrum near the large tick marks.

Now, $P_{\mathcal{W}^{\Delta,s}_{k}}\leq E_{\tilde{\Gamma}^{k,\Delta,s}}(N)$
so not only are the subspaces $\mathcal{W}^{\Delta,s}_{k}$ orthogonal for
different values of $k$, but $H^{\Delta,s}$ maps $\mathcal{W}^{\Delta,s}_{k}$
into $\mathcal{W}^{\Delta,s}_{k}\oplus\mathcal{V}^{\Delta,s}_{1}$ due to the
assumption on the distance between the $\tilde{\Gamma}^{k,\Delta,s}$ for
different values of $k$. Hence, $H^{\Delta,s}$ is equal to $H^{k,\Delta,s}$ on
$\mathcal{W}^{\Delta,s}_{k}$ and $H^{\Delta,s}(\mathcal{W}^{\Delta,s}_{k})$ is
perpendicular to $\mathcal{W}^{\Delta,s}_{k^{\prime}}$ for $k^{\prime}\neq k$
since $\mathcal{W}^{\Delta,s}_{k^{\prime}}\perp\mathcal{V}^{\Delta,s}_{1}$ by
construction. Then we find that $\mathcal{W}^{\Delta,s}_{k}$ are almost
invariant under $H^{\Delta,s}$ because

$\displaystyle(1-P_{\mathcal{W}^{\Delta,s}_{k}})H^{\Delta,s}P_{\mathcal{W}^{\Delta,s}_{k}}=P_{\mathcal{B}^{k,\Delta,s}\ominus\mathcal{W}^{\Delta,s}_{k}}H^{k,\Delta,s}P_{\mathcal{W}^{\Delta,s}_{k}}$

has small norm.

Let
$\mathcal{W}^{\perp}_{\Delta,s}=\mathcal{B}^{\Delta,s}\ominus\bigoplus_{k}\mathcal{W}^{\Delta,s}_{k}$.
Because $H^{s,\Delta}$ is Hermitian, we have broken $\mathcal{B}^{\Delta,s}$
into almost invariant subspaces
$\mathcal{W}^{\Delta,s}_{k},\mathcal{W}^{\perp}_{\Delta,s}$.

We now form the new basis of subspaces $\tilde{\mathcal{B}}$. This is a simple
process, but its explanation is complicated by the fact that because of parity
issues, we cannot just say “join $\mathcal{W}$’s with $\mathcal{W}^{\perp}$’s”
as before. We let the subspaces $\tilde{\mathcal{B}}$ include three types of
subspaces. The first subspaces that we include are
$\mathcal{W}^{\perp}_{\Delta,s}$. The other “$\mathcal{W}$” subspaces contain
a “${\mathcal{V}}$” subspace which has to be matched with its neighboring
“${\mathcal{V}}$” subspace. One of the subspaces
$\mathcal{W}^{k,\Delta}_{i},\mathcal{W}^{k,\Delta,\perp}_{i}$ contains that
subspace $\mathcal{V}^{k,\Delta}_{i_{s}^{k},j_{s}^{k}}$, call this subspace
$\mathcal{W}_{i_{s}^{k},j_{s}^{k}}$. We then include the subspace
$\mathcal{W}_{i_{s}^{k},j_{s}^{k}}\oplus\mathcal{W}^{\Delta,s}_{k}$. We also
include the direct sums of the remaining consecutive subspaces
$\mathcal{W}^{k,\Delta,\perp}_{i}\oplus\mathcal{W}^{k,\Delta}_{i+1}$.

Having defined the subspaces $\tilde{\mathcal{B}}$, we proceed to defining the
nearby commuting matrices. We define $N^{\prime}$ to be the normal matrix that
is block identity picking an eigenvalue from the arcs (or union of arcs) that
we used to make the spaces $\tilde{\mathcal{B}}$. We then have
$\|N-N^{\prime}\|\leq 4\max_{s}C_{s}\ell_{s}$ and $N^{\prime}$ commutes with
$H^{\prime}=\sum_{\tilde{\mathcal{B}}}P_{\tilde{\mathcal{B}}}HP_{\tilde{\mathcal{B}}}$
which is close to $H$. ∎

##  19 Macroscopic Observables

The notion of almost commuting operators associated to observables being near
actually commuting operators is discussed and used in a paper by von Neumann,
translation provided in [49]. A specific passage in the beginning of the
article states:

> Still, it is obviously factually correct that in macroscopic measurements
> the coordinates and momenta are measured simultaneously – indeed, the idea
> is that that becomes possible through the inaccuracy of the macroscopic
> measurement, which is so great that we need not fear a conflict with the
> uncertainty relations.
> …
> We believe that the following interpretation is the correct one: in a
> macroscopic measurement of coordinate and momentum (or two other quantities
> that cannot be measured simultaneously according to quantum mechanics),
> really two physical quantities are measured simultaneously and exactly,
> which however are not exactly coordinate and momentum. They are, for
> example, the orientations of two pointers or the locations of two spots on
> photographic plates– and nothing keeps us from measuring these
> simultaneously and with arbitrary accuracy, only their relation to the
> really interesting physical quantities ($q_{k}$ and $p_{k}$) is somewhat
> loose, namely the uncertainty of this coupling required by the laws of
> nature corresponds to the uncertainty relation[.]

Von Neumann then proceeds to discuss various aspects of this. Directly related
to this topic of quantum statistical mechanics is the idea of macroscopic
observables (“macroscopic measurements” in the above quote) as defined and
discussed in Section II B. of [50].

Two almost commuting self-adjoint matrices are nearby actually commuting
matrices. However, such a definitive statement is not true for more than two
almost commuting matrices under the operator norm as discussed in previous
sections. It is true under other norms as discussed in Section 2. Moreover,
Ogata in [7] provided a proof for the special case of arbitrarily many
macroscopic observables with the operator norm “because of their nice
thermodynamic structure”.

We phrase the result in terms of the operators $T_{N}:M_{n}(\mathbb{C})\to
M_{n^{N}}(\mathbb{C})$ defined by:

$T_{N}(A)=\frac{1}{N}\sum_{k=0}^{N-1}I_{n}^{\otimes(N-1-k)}\otimes A\otimes
I_{n}^{\otimes k}.$

Because $\left[I_{n}^{\otimes(N-1-j)}\otimes A\otimes I^{\otimes
j},I_{n}^{\otimes(N-1-k)}\otimes B\otimes I_{n}^{\otimes k}\right]$ equals $0$
if $j\neq k$ and equals $I_{n}^{\otimes(N-1-k)}\otimes[A,B]\otimes I^{\otimes
k}$ if $j=n$, we see that

$\displaystyle[T_{N}(A),T_{N}(B)]=\frac{1}{N}T_{N}([A,B]).$ (34)

Also, for $U\in M_{n}(\mathbb{C})$ unitary,

$\displaystyle T_{N}(UAU^{\ast})=U^{\otimes N}T_{N}(A)(U^{\ast})^{\otimes N}.$
(35)

With that said, we have that for any collection of matrices, applying $T_{N}$
to them as $N\to\infty$ gives a sequence of collections of almost commuting
matrices. Ogata’s result implies:

######  Theorem 19.1.

For $A_{1},\dots,A_{m}\in M_{n}(\mathbb{C})$ self-adjoint, let
$H_{i,N}=T_{N}(A_{i})$. Then there are commuting matrices $Y_{i,N}\in
M_{n^{N}}(\mathbb{C})$ so that $\|H_{i,N}-Y_{i,N}\|\to 0$ as $N\to\infty$.

######  Remark 19.2.

This result is nonconstructive. Note that Ogata’s result in [7] is only stated
in terms of odd $N$, in slightly different notation. However, because

$\displaystyle T_{N+1}(A)=\frac{N}{N+1}(T_{N}(A)\otimes I_{n}+I_{n}\otimes
T_{N}(A)),$ (36)

we can set

$Y_{i,2\tilde{N}}=\frac{2\tilde{N}-1}{2\tilde{N}}(Y_{i,2\tilde{N}-1}\otimes
I_{n}+I_{n}\otimes Y_{i,2\tilde{N}-1})$

so that since there are nearby commuting matrices for $N$ odd, we have the
same result for $N$ even.

We now list some properties of $T_{N}$. When $A$ is diagonalizable, we see
that

$\displaystyle\sigma(T_{N}(A))=\frac{1}{N}\sum_{k=0}^{N-1}\sigma(A).$ (37)

Thus, the spectrum of $T_{N}(A)$ is a discrete approximation of the convex
hull of $\sigma(A)$. This shows that the methods discussed in Section 18 will
not apply in general for $m\geq 3$. As a consequence of Equation (37), $T_{N}$
is a positive linear map. $T_{N}$ also respects the $\ast$ operation. However,
$T_{N}$ is not multiplicative so is not a $C^{\ast}$-algebra homomorphism.

However, because of Equation (37), $\|T_{N}(A)\|=\|A\|$ when $A$ is normal and
in general $\|T_{N}(A)\|\leq\|A\|$ by definition. Applying

$\|A\|\leq\|\operatorname{Re}A\|+\|\operatorname{Im}A\|\leq 2\|A\|$

to $T_{N}(A)$, we see that

$\displaystyle\frac{1}{2}\|A\|\leq\|T_{N}(A)\|\leq\|A\|.$ (38)

Consequently, $T_{N}$ is injective.

Two questions we ask are:

  1. 1.

What properties of $T_{N}$ imply that there are nearby commuting matrices?

  2. 2.

How much special structure for the $Y_{i,N}$ can be ensured?

Discussing some of the properties of $T_{N}$, note that

$\displaystyle\|T_{N}(A)\otimes I_{n}-I_{n}\otimes
T_{N}(A)\|=\frac{1}{N}\|A\otimes I^{\otimes N}-I^{\otimes N}\otimes
A\|=O\left(1/N\right).$ (39)

Suppose that we define $F_{N}(A)\in M_{k_{N}}(\mathbb{C})$ to satisfy

$\displaystyle\|F_{N}(A)\otimes I_{k_{N}}-I_{k_{N}}\otimes F_{N}(A)\|=o(1)$
(40)

as $N\to\infty$. If the $F_{N}(A_{i})$ are self-adjoint, they are then
unitarily equivalent to $D_{i}=$
$\operatorname{diag}(a_{N,1}^{i},\dots,a_{N,k_{N}}^{i})$. Because

$\max_{i,j}|a_{N,i}-a_{N,j}|=\|D\otimes I_{k_{N}}-I_{k_{N}}\otimes D\|=o(1),$

defining $Y_{N}^{i}=a_{N,1}^{i}I_{k_{N}}$ shows that the $F_{N}(A_{i})$ are
nearly commuting.

Although this implies that they are almost commuting, there is a more direct
proof of this:

$\displaystyle\|\,[F_{N}(A),F_{N}(B)]\,\|$
$\displaystyle=\|\,[F_{N}(A),F_{N}(B)]\otimes
I_{k_{N}}]\,\|=\|\,[F_{N}(A)\otimes I_{k_{N}},F_{N}(B)\otimes I_{k_{N}}]\,\|$
$\displaystyle=\|\,[I_{k_{N}}\otimes F_{N}(A),F_{N}(B)\otimes
I_{k_{N}}]\,\|+o(1)=o(1).$

This, of course, was a trivial example. The key property from (40) being used
was that the identity matrix $I_{k_{N}}$ has the same dimension as $F_{N}(A)$.
If you write out an eigenbasis $v_{1},\dots,v_{2}$ for $F_{N}(A)$ then the
basis $v_{i}\otimes v_{j}$ (with the lexicographic ordering) causes the
eigenvalues for $F_{N}(A)\otimes I_{k_{N}}$ to be
$a_{1},\dots,a_{1},a_{2},\dots,a_{2},\dots,a_{k_{N}},\dots,a_{k_{N}}$ and the
eigenvalues of $I_{k_{N}}\otimes F_{N}(A)$ to be
$a_{1},a_{2},\dots,a_{k_{N}},a_{1},\dots,a_{k_{N}},\dots,a_{1},\dots,a_{k_{N}}$.
Each sublist has length $k_{N}$. So, we are listing each of the $k_{N}$
eigenvalues $k_{N}$ times, but in different ways.

However, if the number $n$ of repetitions is much smaller than the number
$k_{N}$ of eigenvalues then the condition

$\|F_{N}(A)\otimes I_{n}-I_{n}\otimes F_{N}(A)\|=o(1)$

is not as strong. In particular, the condition that we have for macroscopic
observables is

$\|T_{N}(A)\otimes I_{n}-I_{n}\otimes T_{N}(A)\|=O(1/N).$

Now, in what we will see is relevant later, we can write this as

$\displaystyle\|T_{N}(A)\otimes I_{n}-I_{n}\otimes
T_{N}(A)\|=O(1/\log(k_{N}))$ (41)

because $k_{N}=n^{N}$.

Although we already know that the $T_{N}(A_{i})$ are almost commuting, if we
require slightly more than (41), then we can obtain almost commutativity from
this equality. Consider

$\displaystyle\|F_{N}(A)\otimes I_{n}-I_{n}\otimes
F_{N}(A)\|=o(1/\log(k_{N})).$ (42)

We only look at $k_{N}=n^{c_{N}}$. With this condition, we note that

$F_{N}(A)\otimes I_{k_{N}}=F_{N}(A)\otimes I_{n}^{\otimes
c_{N}}=I_{n}^{\otimes c_{N}}\otimes
F_{N}(A)+c_{N}o(1/\log(k_{N}))=I_{k_{N}}\otimes F_{N}(A)+o(1).$

So as before, $F_{N}(A_{1}),\dots,F_{N}(A_{m})$ almost commute.

An open question is if an inequality like (42) or even (41) along with perhaps
the other properties listed above that $T_{N}$ satisfies is enough to ensure
that that $F_{N}(A_{1}),\dots,F_{N}(A_{m})$ nearly commute.

We now attempt to address the second question that we posed above. We first
note that if $v_{1},\dots,v_{k}$ is a basis for $M_{n}(\mathbb{C})$ then
$v_{i_{1}}\otimes\cdots\otimes v_{i_{N}}$ form a basis for
$M_{n}(\mathbb{C})^{\otimes N}$. There is a natural action of an element
$\sigma$ of the symmetric group $S^{N}$ on the basis by:

$\sigma\cdot(v_{i_{1}}\otimes\cdots\otimes
v_{i_{N}})=v_{\sigma(i_{1})}\otimes\cdots\otimes v_{\sigma(i_{N})}.$

We then obtain a representation of $S^{N}$. For any matrix $A\in
M_{n}(\mathbb{C})$, $T_{N}(A)$ commutes with the representation.

A natural question that we might ask is if we can ensure that the $Y_{i,N}$
also commute with the representation. If we are only looking at $m=2$ (so
$i=1,2$) then we can apply Lin’s theorem to obtain this result as follows.
Because $T_{N}(A_{i})$ commute with the representation we see that all
elements of the unital $C^{\ast}$-algebra
${\mathscr{C}}_{N}=C^{\ast}(\\{T_{N}(A_{i})\\}|_{i=1}^{m},I_{n^{N}})$ commute
with the representation. By the characterization of finite dimensional
$C^{\ast}$-algebras (see Theorem III.1.1 of [53]), we see that
${\mathscr{C}}_{N}\cong\bigoplus_{\ell}M_{k_{\ell}}(\mathbb{C})$
isometrically. Then there are self-adjoint matrices $A_{i,N,\ell}$ such that
$T_{N}(A_{i})\sim\bigoplus_{\ell}A_{i,N,\ell}$.

We know that $A_{1,N,\ell},A_{2,N,\ell}$ almost commute with commutator
bounded in norm by $\|T_{N}(A_{1}),T_{N}(A_{2})\|$, so by Lin’s theorem we
obtain nearby commuting matrices $A_{i,N,\ell}^{\prime}$. Then we obtain
commuting $Y_{i,N}\sim\bigoplus_{\ell}A_{i,N,\ell}^{\prime}$ that are close to
$T_{N}(A_{i})$, commute, and lie in ${\mathscr{C}}_{N}$. Hence, we showed that
there are nearby commuting matrices $Y_{i,N}$ that commute with the
representation.

Consider von Neumann’s comments which occur just before the passage that is
quoted above about phase space for the purposes of Quantum statistical
mechanics.

> But the phase space cannot be formed in quantum mechanics, since a
> coordinate $q_{k}$ and the corresponding momentum $p_{k}$ are never
> simultaneously measurable; instead, their probable errors (spreads) $\Delta
> q_{k}$ and $\Delta p_{k}$ are always related according to the uncertainty
> relation $\Delta q_{k}\Delta p_{k}\geq\hbar/2$. Moreover, it is impossible
> to specify, for a state of the system, two intervals $I$, $J$ so that, with
> certainty, $q_{k}$ lies in $I$ and $p_{k}$ in $J$ (even if the product of
> their lengths is much bigger than $\hbar/2$) – thus, not only the continuous
> phase space but also a discrete partition thereof into cells is meaningless!

In accordance with the above quote, we do not provide nearby commuting
matrices $Y_{1,N},Y_{2,N}$ that are able to respect the eigenspaces of both
$T_{N}(A_{1})$ and $T_{N}(A_{2})$. However, we can assure that one of the
$Y_{i,N}$ can respect the eigenspaces of $T_{N}(A_{i})$.

At the end of Section 1.1., von Neumann discusses macroscopic measurements and
a partitioning of the spectrum which we formulate in terms of our problem as
follows. We can partition the spectrum of the operator $T_{N}(A_{1})$ into
disjoint intervals which we can view as the different results of macroscopic
measurements because only so much accuracy can be attained for such a system.
What we look for is that the eigenvectors of $Y_{1,N}$ of eigenvalue $\lambda$
are expressed as the span of only eigenvectors of $T_{N}(A_{1})$ with
eigenvalues near $\lambda$. This means that a measurement of our nearby
observable corresponds to a superposition of states with nearby values for the
original operator $T_{N}(A_{1})$. Naturally, by the uncertainty principle, we
do not expect the same to be true for $Y_{2,N}$ for the same choice of nearby
commuting matrices.

We focus in on the above construction of nearby commuting operators $Y_{i,N}$
that commute with the representation of the symmetric group. The spectrum of
$T_{N}(A_{i})$ can be expressed as $\bigcup_{\ell}\sigma(A_{i,N,\ell})$ by the
$C^{\ast}$-algebra isomorphism. Then instead of “just” applying Lin’s theorem,
we can apply a proof of Lin’s theorem using $(Q^{\prime})$ as described in
Section 7 (see Remark 7.5) with $A=A_{1,N,\ell}$ and $B=A_{2,N,\ell}$ to
obtain $A_{i,N,\ell}^{\prime}$ where the eigenspaces of
$A_{1,N,\ell}^{\prime}$ are subspaces of local spans of eigenspaces of
$A_{1,N,\ell}$. Then form $Y_{i,N}\sim\bigoplus_{\ell}A_{i,N,\ell}^{\prime}$.
If we partition the eigenvalues of $Y_{1,N}$ into disjoint intervals, then
this corresponds to nonconsecutively disjoint intervals covering the spectrum
of $T_{N}(A_{1})$ with the property we discussed above.

An open question is if any of the above structure for the $Y_{i,N}$ can be
maintained when $m\geq 3$.

One way to reformulate the problem is to consider
${\mathscr{A}}_{N}=T_{N}(M_{n}(\mathbb{C}))\subset M_{n^{N}}(\mathbb{C})$. To
show that given any finite collection of Hermitian matrices
$A_{1},\dots,A_{m^{\prime}}$, the $T_{N}(A_{i})$ have nearby commuting
counterparts, it suffices to choose a basis $A_{1},\dots,A_{m}$ for
$M_{n}(\mathbb{C})$ of Hermitian contractions. If we have a contraction
$\tilde{A}\in{\mathscr{A}}_{N}$, then there is a unique $A\in
M_{n}(\mathbb{C})$ so that $T_{N}(A)=\tilde{A}$ and by Equation (38),
$\|A\|\leq 2$. Because the $A_{i}$ are a basis, we have $A=\sum_{i}c_{i}A_{i}$
and by the finite dimensionality, $\max_{i}|c_{i}|\leq C=C(n)$. Thus setting
$Y=\sum_{i}c_{i}Y_{i,N}$, we obtain that $Y$ lies in the span of the $Y_{i,N}$
and $\|Y-T_{N}(A)\|\leq nC\max_{1\leq i\leq N}\|T_{N}(A_{i})-Y_{i,N}\|$, which
converges to zero as $N\to\infty$.

Ogata’s result assures that as $N\to\infty$, ${\mathscr{A}}_{N}$ grows closer
to some commuting subspace of $M_{n^{N}}(\mathbb{C})$. Expanding what was said
in Section 17, finding the matrices $Y_{i,N}$ is equivalent to finding a
minimizer (or an approximate minimizer) to

$\displaystyle\min_{U\in\mathcal{U}(n^{N})}\max_{A\in
B_{{\mathscr{A}}_{N}}}\|UAU^{\ast}-\operatorname{diag}(UAU^{\ast})\|$ (43)

which is equivalent to

$\displaystyle\min_{U\in\mathcal{U}(n^{N})}\max_{1\leq i\leq
m}\|UT_{N}(A_{i})U^{\ast}-\operatorname{diag}(UT_{N}(A_{i})U^{\ast})\|.$ (44)

Continuing the previous approach, because $T_{N}$ is an injection, we could
consider the normed Lie algebra
$\tilde{\mathscr{A}}_{N}=(M_{n}(\mathbb{C}),[-,-]_{N},\|\|_{N})$, where
$A\in\tilde{\mathscr{A}}_{N}$ is identified with $T_{N}(A)$. In that way, by
(38), $\|A\|_{N}$ is equivalent to $\|A\|$ and $[-,-]_{N}=\frac{1}{N}[-,-]$.
So, we can easily see that because the Lie bracket converges to zero as
$N\to\infty$, all bounded sets of elements are almost commuting. However,
because for each $N$, $\|-\|_{N}$ is equivalent to $\|-\|$, there are not any
matrices that do not commute that will be nearby almost commuting matrices in
$\mathscr{A}_{N}$. This shows that to find any nearby commuting matrices, we
would need to embed the Lie algebra into a larger space. An open question is
if this larger space can be $\mathscr{C}_{N}$ as a strictly smaller
$C^{\ast}$-subalgebra of $M_{n^{N}}(\mathbb{C})$.

ACKNOWLEDGEMENTS. The author would like to thank Eric A. Carlen for
introducing the problem to the author and continued guidance during the
writing and revising of this paper and Matthew Hastings for some corrections
of and clarifications concerning [1].

This research was partially supported by NSF grant DMS 1501007.

## References

  * [1] M. Hastings. Making Almost Commuting Matrices Commute. Version 4. https://arxiv.org/abs/0808.2474
  * [2] M. Hastings. Making Almost Commuting Matrices Commute. Commun. Math. Phys. 291, 321–345 (2009)
  * [3] Matthew Hastings. Personal Communication.
  * [4] H. Lin. Almost commuting self-adjoint matrices and applications. Fields. Inst. Commun. 13, 193 (1995).
  * [5] K. Davidson. Almost Commuting Hermitian Matrices. Math. Scand. 56 (1985), 222-240.
  * [6] C. Pearcy and A. Shields. Almost Commuting Matrices. Journal of Functional Analysis. 33, 332-338 (1979).
  * [7] Y. Ogata. Approximating macroscopic observables in quantum spin systems with commuting matrices. Journal of Functional Analysis. Vol. 264, Issue 9, 1 May 2013, pp 2005-2033.
  * [8] T. Loring and A. Sørensen. Almost-Commuting Self-Adjoint Matrices - The Real and Self-Dual Cases. Reviews in Mathematical Physics, 28(07): 1650017, 2016.
  * [9] M. Hastings and T. Loring. Almost commuting matrices, localized Wannier functions, and the quantum Hall effect. J. Math. Phys. 51, 015214 (2010). https://doi.org/10.1063/1.3274817
  * [10] I. Kachkovskiy and Y. Safarov. Distance to Normal Elements in $C^{\ast}$-Algebras of Real Rank Zero. https://arxiv.org/abs/1403.2021
  * [11] T. Osborne. Almost Commuting Unitaries with Spectral Gap are Near Nearly Commuting Matrices. https://arxiv.org/abs/0809.0602
  * [12] T. Loring. $K$-theory and Asymptotically Commuting Matrices. Can. J. Math., Vol. XL, No. 1, 1988, pp. 197-216.
  * [13] R. Exel and T. Loring. Almost Commuting Unitary Matrices. Proc. Amer. Math. Soc. Vol. 106, No. 4, 1989.
  * [14] R. Exel and T. Loring. Invariants of Almost Commuting Unitaries.
  * [15] H. Lin. Almost Commuting Unitaries and Classification of Purely Infinite Simple $C^{\ast}$-Algebras. Journal of Functional Analysis, 10 May 1998, Vol.155(1) pp.1-24.
  * [16] P. Friis and M. Rørdam. Almost commuting self-adjoint matrices - a short proof of Huaxin Lin’s theorem. J. reine angew. Math 479 (1996). 121-131.
  * [17] S. Szarek. On Almost Commuting Hermitian Operators. Rocky Mountain Journal of Mathematics. Vol. 20, No. 2, Spring 1990.
  * [18] C. Davis. The Rotation of Eigenvectors by a Perturbation. Journal of Mathematical Analysis and Applications 6, 159-173 (1963) https://doi.org/10.1016/0022-247X(63)90001-5
  * [19] M. Said. Almost Commuting Elements in Non-Commutative Symmetric Operator Spaces. Dissertation.
  * [20] C. Jordan. Essai sur la géoméacutrie à $n$ dimensions.
  * [21] J. Dixmier. Position relative de deux variétés linéaires fermées dans un espace de Hilbert.
  * [22] P. Halmos. Two Subspaces.
  * [23] P. Halmos. Some unsolved problems of unknown depth about operators on Hilbert space Proceedings of the Royal Society of Edinburgh, 76A, 67-76, 1976. https://doi.org/10.1017/S0308210500019491
  * [24] P. Rosenthal. Are Almost Commuting Matrices Near Commuting Matrices? The American Mathematical Monthly, Vol. 76, No. 8 (Oct., 1969), pp. 925-926.
  * [25] W. Luxemburg and R. Taylor. Almost Commuting Matrices are near Commuting Matrices.
  * [26] J. Bastian and K Harison. Subnormal Weighted Shifts and Asymptotic Properties of Normal Operators Proc. Amer. Math. Soc. 42 (1974), 475-479. https://doi.org/10.1090/S0002-9939-1974-0380491-X
  * [27] I. Berg and C. Olsen. A note on Almost Commuting Matrices. Michigan Math. J. Volume 21, Issue 4 (1975), 377-383.
  * [28] D. Voiculescu. Asymptotically commuting finite rank unitary operators without commuting approximants. Acta Sci. Math. (Szeged) 45:1-4(1983), 429-431 1983\.
  * [29] K. Davison and S. Szarek. Chapter 8 Local Operatorn Theory, Random Matrices, and Banach Spaces of Handbook of the Geometry of Banach Spaces Vol 1. 2001\.
  * [30] D. Enders and T. Shulman. Almost Commuting Matrices, Cohomology, and Dimension.
  * [31] I. Berg. On Approximation of Normal Operators by Weighted Shifts.
  * [32] S. Demko, W. Moss, and P. Smith. Decay Rates for Inverses of Band Matrices. Mathematics of Computation, 43(168), 491-499. (1984) doi:10.2307/2008290
  * [33] O. Bratteli and D. Robinson. Operator Algebras and Quantum Statistical Mechanics. Volume 1. 1979.
  * [34] A. B. Aleksandrov and V. Peller. Operator Lipschitz functions. 2016 Russ. Math. Surv.71 605.
  * [35] A.B. Aleksandrova, V.V. Peller. Estimates of operator moduli of continuity. Journal of Functional Analysis 261 (2011) 2741–2796.
  * [36] A. B. Aleksandrov and V. V. Peller. Operator Hölder-Zygmund Functions. https://arxiv.org/abs/0907.3049
  * [37] C. Davis and W. Kahan. The Rotation of Eigenvectors by a Perturbation. III. SIAM J. Numer. Anal., 7(1), 1–46. https://doi.org/10.1137/0707001
  * [38] R. Bhatia, C. Davis, and A. McIntosh. Perturbation of Spectral Subspaces and Solution of Linear Operator Equations. Linear Algebra and its Applications. 52/53:45-67 (1983) https://doi.org/10.1016/0024-3795(83)80007-X
  * [39] R. Bhatia and P. Rosethal. How and Why to Solve the Operator Equation $AX-XB=Y.$ https://doi.org/10.1112/S0024609396001828
  * [40] R. Bhatia, C.Davis and P. Koosis. An extremal problem in Fourier analysis with applications to operator theory. https://doi.org/10.1016/0022-1236(89)90095-5
  * [41] L. Glebsky. Almost commuting matrices with respect to normalized Hilbert-Schmidt norm. https://arxiv.org/abs/1002.3082
  * [42] C. Spengler, M. Huber, and B. C. Hiesmayr. A composite parameterization of unitary groups, density matrices and subspaces. https://arxiv.org/abs/1004.5252
  * [43] Spengler, M. Huber, and B. C. Hiesmayr. Composite parameterization and Haar measure for all unitary and special unitary groups.
  * [44] C. Spengler. Composite parameterization of unitary groups. https://www.mathworks.com/matlabcentral/fileexchange/30990-composite-parameterization-of-unitary-groups
  * [45] M. Benzi and G. Golub. Bounds for the Entries of Matrix Functions with Applications to Preconditioning. BIT Numerical Mathematics (1999) 39: 417. https://doi.org/10.1023/A:1022362401426
  * [46] S. Pironio. et al. Device-independent quantum key distribution secure against collective attacks. 2009 New J. Phys.11 045021
  * [47] D. Nagaj, P. Wocjan, Y. Zhang. Fast Amplification of QMA. https://arxiv.org/abs/0904.1549
  * [48] A. Prakash. Quantum Algorithms for Linear Algebra and Machine Learning. Dissertation. https://www2.eecs.berkeley.edu/Pubs/TechRpts/2014/EECS-2014-211.html
  * [49] J. von Neumann. Proof of the ergodic theorem and the H-theorem in quantum mechanics Translation of: Beweis des Ergodensatzes und des H-Theorems in der neuen Mechanik Eur. Phys. J. H35, 201–237 (2010).
  * [50] D. Poulin. Macroscopic observables. Physical Review A 71, 022102 (2005).
  * [51] M. Andelić and C. da Fonseca. Sufficient conditions for positive definiteness of tridiagonal matrices revisited. https://doi.org/10.1007/s11117-010-0047-y
  * [52] C. Davis. Generators of the Ring of Bounded Operators. Proc. Amer. Math. Soc. Vol. 6, No. 6 (Dec., 1955), pp.970-972.
  * [53] K. Davidson. $C^{\ast}$-Algebras by Example. AMS. 1996.
  * [54] B. Blackadar. Operator Algebras - Theory of $C^{\ast}$-Algebras and von Neumann Algebras. Springer-Verlag. Berlin Heidelberg. 2006.
  * [55] L. Grafakos. Classical Fourier Analysis. 2nd. Edition. 2008.
  * [56] E. Stein and R. Shakarchi. Complex Analysis. Princeton University Press. 2003.