text:
\begin{document}

\title{The C*-algebra of a minimal homeomorphism of zero mean dimension}

\author{George A. Elliott}
\address{Department of Mathematics, University of Toronto, Toronto, Ontario, Canada~\ M5S 2E4}
\email{elliott@math.toronto.edu}

\author{Zhuang Niu}
\address{Department of Mathematics, University of Wyoming, Laramie, WY, 82071, USA.}
\email{zniu@uwyo.edu}

\begin{abstract}
Let $X$ be an infinite compact metrizable space, and let $\sigma: X\to X$ be a minimal homeomorphism. Suppose that $(X, \sigma)$ has zero mean topological dimension. The associated C*-algebra $A=\mathrm{C}(X)\rtimes_\sigma\mathbb Z$ is shown to absorb the Jiang-Su algebra $\mathcal Z$ tensorially, i.e., $A\cong A\otimes\mathcal Z$. This implies that $A$ is classifiable when $(X, \sigma)$ is uniquely ergodic.

Moreover, without any assumption on the mean dimension, it is shown that $A\otimes A$ always absorbs the Jiang-Su algebra.
\end{abstract}

\maketitle

\setcounter{tocdepth}{1}

\section{Introduction}

Recently, Toms and Winter proved that a simple C*-algebra arising from a $\Int$-action on a compact metrizable space of finite dimension absorbs the Jiang-Su C*-algebra $\mathcal Z$ (\cite{TW-Dym}, \cite{TW-Dym-1}). (This definitive result followed much earlier work, e.g., \cite{LP-Dym}.) As shown in \cite{GK-Dyn}, some condition is necessary. (Presumably, mean dimension zero!)

In the present note we show that the condition of finite dimension can be replaced by the weaker condition that the dynamical system has mean dimension zero, as defined in \cite{Lindenstrauss-Weiss-MD} (Definition \ref{MD-def} below): More precisely,
\theoremstyle{plain}
\newtheorem*{thm-nocount}{Theorem}
\begin{thm-nocount}
Let $X$ be an infinite compact metrizable space, and let $\sigma: X\to X$ be a minimal homeomorphism. If $(X, \sigma)$ has mean dimension zero, then the C*-algebra $A=\mathrm{C}(X)\rtimes_{\sigma}\mathbb Z$ absorbs the Jiang-Su algebra $\mathcal Z$ tensorially.
\end{thm-nocount}
The same classification consequences as shown in \cite{TW-Dym} and \cite{TW-Dym-1} in the case that $\Kzero$ separates traces hold also in the present setting. See Corollary \ref{z-clasn}.

Moreover, the tensor product of the C*-algebras of two arbitrary minimal homeomorphisms (without any assumption on the mean dimension) is Jiang-Su stable:
\begin{thm-nocount}
Let $(X_1, \sigma_1)$ and $(X_2, \sigma_2)$ be minimal dynamical systems, where $X_1$ and $X_2$ are infinite compact metrizable spaces. Consider the C*-algebras $$A_1=\mathrm{C}(X_1)\rtimes_{\sigma_1}\Int \quad \textrm{and}\quad A_{2}= \mathrm{C}(X_2)\rtimes_{\sigma_2}\Int.$$
Then $$A_{1}\otimes A_{2}\cong (A_{1}\otimes A_{2})\otimes\mathcal Z.$$
\end{thm-nocount}

\section{Mean topological dimension and the small boundary property}
Let $X$ be a compact metrizable space, and let $\sigma: X\to X$ be a homeomorphism. (These objects will be fixed throughout the paper.)
\begin{defn}[\cite{Lindenstrauss-Weiss-MD}]\label{MD-def}
The mean topological dimension of $(X, \sigma)$ is defined by
$$\mathrm{mdim}(X, \sigma)=\sup_{\alpha}\lim_{N\to\infty}\frac{1}{N}\mathcal{D}(\alpha\vee\sigma(\alpha)\vee\cdots\vee\sigma^{N-1}(\alpha)),$$
where the dimension of the finite open cover $\beta$, $\mathcal D(\beta)$, is the number $\max\{\mathrm{ord}(\beta');\ \beta'\preceq \beta\}$. (By the order of a cover $\beta$ is meant the number $\mathrm{ord}(\beta)=-1+\sup_x\sum_{U\in\beta} 1_U(x)$.)
\end{defn}

\begin{defn}[\cite{Lindenstrauss-Weiss-MD}]
For each set $E\subseteq X$, the orbit capacity of $E$, denoted by $\mathrm{ocap}(E)$, is defined to be
$$\mathrm{ocap}(E)=\lim_{N\to\infty}\frac{1}{N}\sup \{\chi_{E}(x)+\cdots+ \chi_{E}(\sigma^{N-1}(x));\ x\in X\}.$$
The system $(X, \sigma)$ is said to have the small boundary property (SBP) if for any $x\in X$ and any open neighborhood $U$ of $x$, there is a neighborhood $V$ in $U$ such that $\mathrm{ocap}(\partial V)=0$.
\end{defn}

\begin{thm}[\cite{Lindenstrauss-Weiss-MD}, \cite{Lind-MD}]
If $\sigma$ is minimal, then $(X, \sigma)$ has zero mean topological dimension if and only if it has the small boundary property.
\end{thm}

\begin{prop}[Proposition 5.3 of \cite{Lindenstrauss-Weiss-MD}]\label{small-intsct}
If $(X,T)$ has the SBP, then for every open cover $\alpha$ of $X$ and every $\eps>0$, there is a partition of unity $\phi_j: X\to [0, 1]$ ($j=1, ..., \abs{\alpha}$) subordinate to $\alpha$
such that

$$\mathrm{ocap}(\bigcup_{j=1}^{\abs{\alpha}}\phi_j^{-1}((0, 1)))<\eps.$$

\end{prop}

\section{The C*-algebra of a homeomorphism and its large subalgebras}\label{Strut-AY}
Suppose that $X$ as above is an infinite set and $\sigma$ as above is minimal.  Let us denote by $\sigma$ also the automorphism of $\mathrm{C}(X)$ defined by $$\sigma(f)=f\circ\sigma^{-1},\quad \forall f\in \mathrm{C}(X).$$
Consider the crossed product C*-algebra
$$A=\mathrm{C}(X)\rtimes_\sigma\Int=\textrm{C*}\{f, u;\ ufu^*=\sigma(f),\ f\in \mathrm{C}(X)\}.$$
Fix $y\in X$, and then consider the sub-C*-algebra
$$A_y=\textrm{C*}\{f, ug;\ f, g\in\mathrm{C}(X),\ g(y)=0\}\subseteq A.$$
Let $Y$ be a closed neighborhood of $y$ in $X$. Consider the sub-C*-algebra
$$A_Y=\textrm{C*}\{f, ug;\ f, g\in\mathrm{C}(X),\ g|_Y=0\}\subseteq A_y.$$
It is clear that $A_{Y_1}\subseteq A_{Y_2}$ if $Y_1\supseteq Y_2$, and $A_y$ is the inductive limit of $A_{Y_i}$ if $\bigcap Y_i=\{y\}$.

Consider the first return times
$$\{j\in \mathbb N\cup \{0\};\ \textrm{$\sigma^j(x)\in Y$ but $\sigma^i(x)\notin Y$, $1\leq i\leq j-1$ for some $x\in Y$}\}.$$
Since $\sigma$ is minimal and $X$ is compact, this set of numbers is finite; let us write it as
$$J_1<J_2<\cdots <J_K$$
for some $K\in\mathbb N$.
Note that since $X$ is a infinite set and $\sigma$ is minimal, the first return time $J_1$ can be arbitrarily large if $Y$ is sufficiently small.

For each $1\leq k\leq K$, consider the (locally compact---see below) subset of $X$
$$Z_k=\{x\in Y;\  \textrm{$\sigma^{J_k}(x)\in Y$ but $\sigma^i(x)\notin Y$ for any $1\leq i\leq J_k-1$}\}.$$
Then the sets
$$\{\{Z_1, \sigma(Z_1), ..., \sigma^{J_1-1}(Z_1)\}, ..., \{Z_k, \sigma(Z_k), ..., \sigma^{J_k-1}(Z_k)\}\}$$
(which are naturally grouped as shown) form a partition of $X$. This is often called a Rokhlin partition.

\begin{lem}[\cite{Lin-Q-RSA}]
With notation as above, one has that, for each $1\leq k\leq K$,\\

$\mathrm{(1)}$ the set $Z_1\cup\cdots\cup Z_k$ is closed (and so $Z_k$ is locally compact),\\

$\mathrm{(2)}$ the set $\overline{Z_k}\cap (Z_1\cup\cdots\cup Z_{k-1})$ is the disjoint union of the subsets
$$W=\partial Z_k\cap Z_{t_1}\cap\sigma^{-J_{t_1}}(Z_{t_2})\cap\cdots\cap\sigma^{-(J_{t_1}+\cdots+J_{t_{s-1}})}(Z_{t_s}),$$ where $J_{t_1}+\cdots +J_{t_{s-1}}+J_{t_s}=J_k$.

\end{lem}

A fairly explicit description of the subalgebra $A_Y$ of the crossed product, which in fact is a C*-algebra of type I,  was obtained by Q.~Lin (\cite{Lin-Q-RSA}). It is a subhomogeneous algebra, of order at most $J_k$.

\begin{thm}[\cite{Lin-Q-RSA}]\label{Lin-Sub}
With notation as above, one has that the C*-algebra $A_Y$ is isomorphic to the sub-C*-algebra of $\bigoplus_{k=1}^K \textrm{M}_{J_k}(\textrm{C}(\overline{Z_k}))$ consisting of the elements $(F_1, ..., F_k)$ with
\begin{displaymath}
F_k|_{W}=
\left(
\begin{array}{cccc}
F_{t_1}|_{W} & & & \\
& F_{t_2}\circ\sigma^{J_{t_1}}|_{W} & &\\
& & \ddots &\\
& & & F_{t_s}\circ\sigma^{J_{t_s-1}}|_{W}
\end{array}
\right)
\end{displaymath}
whenever
$$W=\partial Z_k\cap Z_{t_1}\cap\sigma^{-J_{t_1}}(Z_{t_2})\cap\cdots\cap\sigma^{-(J_{t_1}+\cdots+J_{t_{s-1}})}(Z_{t_s})\neq\O,$$ where $J_{t_1}+\cdots +J_{t_{s-1}}+J_{t_s}=J_k$.

Moreover, for any $f, g\in\mathrm{C}(X)$ with $g|_Y=0$, the images of $f, ug\in A_Y$ in this identification are
\begin{equation}\label{id-01}
f=\bigoplus_{k=1}^K
\left(
\begin{array}{cccc}
f\circ \sigma|_{\overline{Z_k}} & & & \\
& f\circ \sigma^2|_{\overline{Z_k}} & &\\
& & \ddots &\\
& & & f\circ \sigma^{J_k}|_{\overline{Z_k}}
\end{array}
\right)\in \bigoplus_{k=1}^K \textrm{M}_{J_k}(\textrm{C}(\overline{Z_k}))
\end{equation}
and
\begin{equation}\label{id-02}
ug=\bigoplus_{k=1}^K
\left(
\begin{array}{cccc}
0 & & & \\
g\circ \sigma|_{\overline{Z_k}}& 0& & \\
&  \ddots& \ddots &\\
& & g\circ \sigma^{J_k-1}|_{\overline{Z_k}} & 0
\end{array}
\right)\in \bigoplus_{k=1}^K \textrm{M}_{J_k}(\textrm{C}(\overline{Z_k})),
\end{equation}
respectively.
\end{thm}

The sub-C*-algebra $A_y$ in $A$ is a typical example of a large sub-C*-algebra.
\begin{defn}[\cite{NCP-LAlg}, \cite{A-NCP-LAlg}]
Let $A$ be an infinite dimensional simple separable unital C*-algebra. A unital sub-C*-subalgebra $B\subseteq A$ is said to be large in $A$ if for every
$m\in \mathbb{Z}_{>0}$, $a_1, a_2, ..., a_m\in A$, $\eps>0$, $x\in A^+$ with $\norm{x}=1$, and $y\in B^+\setminus\{0\}$, there are $c_1, c_2, ..., c_m\in A$ and $g\in B$ such that:
\begin{itemize}
\item[(1)] $0 \leq g \leq 1$.
\item[(2)] For $j=1, 2, ..., m$ we have $\norm{c_j-a_j}<\eps$.
\item[(3)] For $j=1, 2, ..., m$ we have $(1-g)c_j, c_j(1-g)\in B$.
\item[(4)] $g\preceq_B y$.
\item[(5)] $\norm{(1-g)x(1-g)}>1-\eps$.
\end{itemize}
Moreover, if
\begin{itemize}
\item[(6)] for $j=1, 2, ..., m$ we have $\norm{ga_j-a_jg}<\eps$,
\end{itemize}
then the sub-C*-algebra $B$ is said to be centrally large in $A$.
\end{defn}

\begin{thm}[Archey-Phillips \cite{A-NCP-LAlg}]
The C*-algebra $A_y$ is centrally large in $A$.
\end{thm}

\begin{thm}[Archey-Phillips \cite{A-NCP-LAlg}]\label{CLalg-prod}
If $B_1\subseteq A_1$ and $B_2\subseteq A_2$ are centrally large sub-C*-algebras, then the tensor product sub-C*-algebra $$B_1\otimes_{\mathrm{min}}B_2\subseteq A_1\otimes_{\mathrm{min}}A_2$$ is centrally large in the tensor product.
\end{thm}

We will use the following property of centrally large sub-C*-algebras.
\begin{thm}[Archey-Phillips \cite{A-NCP-LAlg}]
Let $B\subseteq A$ be a nuclear centrally large sub-C*-algebra of $A$. If $B\cong B\otimes\mathcal Z$, then $A\cong A\otimes\mathcal Z$.
\end{thm}

\section{The C*-algebra of a minimal homeomorphism of mean dimension zero }

Let $S$ be a subhomogeneous C*-algebra, with dimensions of irreducible representations $d_1<d_2<\cdots<d_n$. The dimension ratio of $S$ is defined as
$$\mathrm{dimRatio}(S)=\max\{\frac{\mathrm{dim}(\mathrm{Prim}_{d_1}(S)}{d_1}, \frac{\mathrm{dim}(\mathrm{Prim}_{d_2}(S)}{d_2}, ..., \frac{\mathrm{dim}(\mathrm{Prim}_{d_n}(S)}{d_n}  \},$$
where $\mathrm{dim}(\cdot)$ denotes the topological covering dimension.

By Proposition 2.13 (together with 2.5 and 2.9) of \cite{Phill-RSA1}, if the primitive ideal spaces of $S$ have finite dimension, then the C*-algebra $S$ has a recursive subhomogeneous decomposition,
$$S\cong\left[\cdots\left[\left[C_0\oplus_{C_1^{(0)}}C_1\right]\oplus_{C_2^{(0)}}C_2\right]\cdots\right]\oplus_{C_l^{(0)}}C_l,$$
with $C_k=\mathrm{C}(X_k, \mathrm{M}_{n(k)})$ for compact Hausdorff spaces $X_k$ and positive integers $n(k)$, and with $C_k^{(0)}=\mathrm{C}(X_k^{(0)}, \mathrm{M}_{n(k)})$ for compact subsets $X_k^{(0)}\subseteq X_k$ (possibly empty) such that
$$\frac{\mathrm{dim}(X_k)}{n(k)}\leq \mathrm{dimRatio}(S),\quad 0\leq k\leq l.$$
(See \cite{Phill-RSA1} for more details on recursive subhomogeneous C*-algebras.)

In this section, it will be shown (using Theorem \ref{Lin-Sub} indirectly) that if $(X, \sigma)$ has zero mean dimension (and, as understood, $\sigma$ is minimal), then the large subalgebra $A_y$ can be locally approximated by subhomogeneous C*-algebras with arbitrarily small dimension ratio (see Theorem \ref{lc-app}).

As a consequence of this, it follows (on applying the large subalgebra technique---see \cite{NCP-LAlg}) that the crossed product C*-algebra $\mathrm{C}(X)\rtimes_\sigma\Int$ absorbs the Jiang-Su algebra $\mathcal Z$, the main result of this paper.

Of the following three lemmas (Lemmas \ref{small-nbhd}, \ref{uni-sep}, and \ref{cont-field}), only the first concerns dynamical systems. The other two are elementary C*-algebra results, at least the second of which, a case of the Stone-Weierstrass Theorem, is known.

\begin{lem}\label{small-nbhd}
Let $Y\subseteq X$ be a closed subset with nonempty interior. Denote by $Z_1, ..., Z_K$ the bases of the Rokhlin towers generated by $Y$, and by $J_1<J_2<\cdots<J_K$ the first return times of $Z_1, Z_2, ..., Z_K$, respectively. There is an open set $U\supseteq Y$ such that for each $1\leq k\leq K$, one has
$$\frac{1}{J_k}(\chi_{U}(x)+\chi_U(\sigma(x))+\cdots+ \chi_U(\sigma^{J_k-1}(x)))\leq \frac{1}{J_1},\quad x\in Z_{k}.$$
\end{lem}
\begin{proof}
Note that by definition the inequality holds with $Y$ in place of $U$. (So, the question is to extend this in some sense by continuity to a neighborhood---we propose to do this by induction on $k$.)

Since $Y$ is closed, and the sets
$$Y, \sigma(Y), ..., \sigma^{J_1-1}(Y)$$
are pairwise disjoint, there is an open set $U\supseteq Y$ such that
$$U, \sigma(U), ..., \sigma^{J_1-1}(U)$$
are pairwise disjoint. In particular,
$$\frac{1}{J_1}(\chi_{U}(x)+\chi_U(\sigma(x))+\cdots+ \chi_U(\sigma^{J_1-1}(x)))\leq \frac{1}{J_1},\quad x\in Z_{1}.$$

Let $2\leq k\leq K$, and assume that we have constructed an open set $U\supseteq Y$ such that
for any $1\leq i\leq k-1$,
\begin{equation}\label{ind-asptn}
\frac{1}{J_i}(\chi_{U}(x)+\chi_U(\sigma(x))+\cdots+ \chi_U(\sigma^{J_i-1}(x)))\leq \frac{1}{J_1},\quad x\in Z_{i}.
\end{equation}
Let us construct another open neighborhood of $Y$, still to be denoted by $U$ (just shrink!), such that \eqref{ind-asptn} holds for $i=k$.

First, pick an open neighborhood $U'$ of $Y$ such that $\overline{U'}\subseteq U$. Let
$x\in \overline{Z_{k}}\cap (Z_{1}\cup\cdots\cup Z_{k-1})$. If
$$x\in W=\overline{Z_{k}}\cap Z_{t_1}\cap\sigma^{-J_{t_1}}(Z_{t_2})\cap\cdots\cap \sigma^{-(J_{t_1}+\cdots+J_{t_{s-1}})}(Z_{t_s}),$$
where $J_{t_1}+\cdots+J_{t_{s-1}}+J_{t_s}=J_k,$
then the orbit of $x$ is
$$\underbrace{x, \sigma(x),...,\sigma^{J_{t_1}-1}(x)}_{\textrm{in tower $Z_{t_1}$}}, \underbrace{\sigma^{J_{t_1}}(x), ..., \sigma^{J_{t_2}}(\sigma^{J_{t_1}}(x))}_{\textrm{in tower $Z_{t_2}$}}, ...,  \underbrace{\sigma^{J_{t_1}+\cdots+J_{t_{s-1}}}(x), ..., \sigma^{J_{t_s}}(\sigma^{J_{t_1}+\cdots+J_{t_{s-1}}}(x))}_{\textrm{in tower $Z_{t_s}$}}.$$
By the induction hypothesis \eqref{ind-asptn}, one has
$$
\frac{1}{J_k}(\chi_{U}(x)+\chi_U(\sigma(x))+\cdots+ \chi_U(\sigma^{J_k-1}(x)))\leq \frac{1}{J_1},
$$
and therefore, there is a neighborhood $V_x$ of $x$ such that
\begin{equation}
\frac{1}{J_k}(\chi_{U'}(z)+\chi_{U'}(\sigma(z))+\cdots+ \chi_{U'}(\sigma^{J_k-1}(z)))\leq \frac{1}{J_1},\quad z\in V_x.
\end{equation}
Hence, there is an open set $E$ such that $$\overline{Z_{k}}\cap (Z_{1}\cup\cdots\cup Z_{k-1})\subseteq E$$ and
\begin{equation}\label{small-bd}
\frac{1}{J_k}(\chi_{U'}(z)+\chi_{U'}(\sigma(z))+\cdots+ \chi_{U'}(\sigma^{J_k-1}(z)))\leq \frac{1}{J_1},\quad z\in E.
\end{equation}
Replace $U$ by $U'$ and still denote it by $U$. Since $Z_{1}\cup\cdots\cup Z_{k-1}\cup Z_{k}$ is a closed set, one has that
$$\overline{Z_{k}}\setminus Z_{k}\subseteq \overline{Z_{k}}\cap (Z_{1}\cup\cdots\cup Z_{k-1}),$$
and hence $\overline{Z_{k}}\setminus Z_{k}\subseteq E.$
In particular,
$$\overline{Z_{k}}\setminus E = Z_{k}\setminus E ,$$
and $Z_{k}\setminus E$ is a compact set.

For any point $x$ in $Z_{k}\setminus E$, one can shrink $U$ further so that
\begin{equation}\label{small-comp-loc}
\frac{1}{J_k}(\chi_{\overline{U}}(x)+\chi_{\overline{U}}(\sigma(x))+\cdots+ \chi_{\overline{U}}(\sigma^{J_k-1}(x)))\leq \frac{1}{J_1}.
\end{equation}
Note that \eqref{small-comp-loc} holds for a neighborhood of $x$. Since $Z_{k}\setminus E$ is compact, there is an open neighborhood $U$ of $Y$ such that
\begin{equation}\label{small-comp}
\frac{1}{J_k}(\chi_{U}(x)+\chi_{U}(\sigma(x))+\cdots+ \chi_{U}(\sigma^{J_k-1}(x)))\leq \frac{1}{J_1},\quad x\in Z_{k}\setminus E.
\end{equation}
Together with \eqref{small-bd}, one has
\begin{equation}
\frac{1}{J_k}(\chi_{U}(x)+\chi_{U}(\sigma(x))+\cdots+ \chi_{U}(\sigma^{J_k-1}(x)))\leq \frac{1}{J_1},\quad x\in Z_{k},
\end{equation}
as desired.
\end{proof}

\begin{lem}\label{uni-sep}
Consider $n\times n$ matrices
$$A:=\mathrm{diag}\{a_1, ..., a_n\},\quad B:=\mathrm{diag}\{b_1, ..., b_n\}$$
\begin{displaymath}
C:=\left(
\begin{array}{cccc}
0 &    &  & \\
c_1 & 0  &  &  \\
 & \ddots  & \ddots & \\
 &    & c_{n-1} & 0
\end{array}
\right)
\quad
\textrm{and}
\quad
D:=\left(
\begin{array}{cccc}
0 &    &  & \\
d_1 & 0  &  &  \\
 & \ddots  & \ddots & \\
 &    & d_{n-1} & 0
\end{array}
\right),
\end{displaymath}
where $0<c_i, d_i\leq 1$.  If the pair $(A, C)$ is unitarily equivalent to pair $(B, D)$, then
$$a_i=b_i,\ c_j=d_j,\quad 1\leq i\leq n, 1\leq j\leq n-1 .$$
\end{lem}
\begin{proof}
Let $W\in\mathrm{M}_n(\Comp)$ be a unitary such that
$$W^*AW=B\quad\textrm{and}\quad W^*CW=D.$$
For each $1\leq k\leq n$, one has $W^*((C^*)^kC^k)W=(D^*)^kD^k$, and
a functional calculus argument shows that
$$W^*(e_1+\cdots +e_k)W=e_1+\cdots + e_k,\quad 1\leq k\leq n,$$
where $e_i$ is the $i$th standard rank-one projection.
This implies that
$$W^*e_iW=e_i,\quad 1\leq i\leq n.$$

Since $W^*AW=B$, it follows that
$$W^*e_iAe_iW=e_iBe_i,\quad 1\leq i\leq n,$$
and hence $$a_i=b_i,\quad 1\leq i\leq n.$$
A similar argument shows that
$c_i=d_i,$ $1\leq i\leq n.$
\end{proof}

\begin{lem}\label{cont-field}
Let $Z$ be a second countable locally compact Hausdorff space, and let $S$ be a sub-C*-algebra of $\mathrm{M}_n(\mathrm{C_0}(Z))$. Suppose that there is a surjective continuous map $\xi: Z\to\Delta$ such that
\begin{enumerate}
\item\label{cond-sep} $\xi(x_1)=\xi(x_2)$ if and only if $\pi_{x_1}|_S$ is unitarily equivalent to $\pi_{x_2}|_S$,
\item\label{cond-cont} for any $g\in S$, if $\xi(x_n)\to\xi(x)$, then $g(x_n) \to g(x)$, and
\item\label{cond-full} $\pi_x(S)=\mathrm{M}_n(\mathbb C)$, for any $x\in Z$.
\end{enumerate}
Then $S\cong\mathrm{M}_m(\mathrm{C}_0(\Delta))$.
\end{lem}
\begin{proof}
For each $f\in S$, define a function $\tilde{f}: \Delta\to \mathrm{M}_n(\Comp)$ by
$$\tilde{f}(z)=f(x),\quad\textrm{if $\xi(x)=z$}.$$
By Condition \eqref{cond-cont}, $\tilde{f}$ is well defined, and $\tilde{f}$ is continuous. Moreover, $\tilde{f}$ vanishes at infinity. As if $z_n\in\Delta$ with $z_n\to\infty$, since $\xi$ is surjective, there are $x_n\in Y$ with $\xi(x_n)=z_n$.
Then $x_n\to\infty$. Otherwise, there is a subsequence, say $(x_{n_k})$, converging to a point $x\in Z$. Since $\xi$ is continuous, one has that $z_{n_k}=\xi(x_{n_k})\to\xi(x)$, which contradicts the assumption $z_n\to\infty$. Hence $\tilde{f}(z_n)=f(x_n)\to 0$, and $\tilde{f}\in \mathrm{M}_n(\mathrm{C_0}(\Delta))$.

Moreover, it is clear that the map $f\to\tilde{f}$ is an injective homomorphism, and thus one can regard $S$ as a sub-C*-algebra of $\mathrm{M}_n(\mathrm{C_0}(\Delta))$. It follows from Conditions \eqref{cond-sep} and \eqref{cond-full} that $S$ is a rich sub-C*-algebra of $\mathrm{M}_n(\mathrm{C_0}(\Delta))$ in the sense of Dixmier (11.1.1 of \cite{Dix-Book}), and therefore $S=\mathrm{M}_m(\mathrm{C}_0(\Delta))$ by Proposition 11.1.6 of \cite{Dix-Book} (or, it follows from Theorem 7.2 of \cite{Kap-SCalg}).
\end{proof}

\begin{thm}\label{lc-app}
Let $X$ be an infinite compact metrizable space, and let $\sigma$ be a minimal homeomorphism. Suppose that $(X, \sigma)$ has topological mean dimension zero. Let $$\{f_1, f_2, ..., f_n, g_1, g_2, ..., g_m\}\subseteq \mathrm{C}(X)$$ with $g_i(W)=\{0\}$, $i=1, ..., m$, for some open set $W$ containing $y$. Then, for any $\eps>0$, there is a closed neighborhood $Y$ of $y$ contained in $W$ such that the finite subset
$$\{f_1, f_2, ..., f_n, ug_1, ug_2, ..., ug_m\}$$
of $A_Y$, where $u$ is the canonical unitary of the crossed product, is approximated to within $\eps$ by a subhomogeneous C*-algebra $S$ in $A_Y$ with dimension ratio at most $\eps$.
\end{thm}
\begin{proof}
Let $\eps>0$ be arbitrary. Choose a finite open cover
$$\alpha=\{U_1, U_2, ..., U_{\abs{\alpha}}\}$$
of $X$ such that
\begin{equation}\label{eq-small-nbhd}
\abs{f_i(x)-f_i(y)} < \eps\quad\mathrm{and}\quad \abs{g_j(x)-g_j(y)} < \eps,\quad x, y\in U_i,\  1\leq i\leq\abs{\alpha}.
\end{equation}
Since $(X, \alpha)$ is minimal and has mean dimension zero, it has SBP, and therefore by Proposition \ref{small-intsct}, there is a partition of unity $\{\phi_U;\ U\in\alpha \}$ subordinate to $\alpha$ and $T\in\mathbb N$ such that
\begin{equation}\label{sm-fctn}
\frac{1}{N}(\chi_{E}(x)+\chi_{E}(\sigma(x))+\cdots+\chi_E(\sigma^{N-1}(x)))<\frac{\eps}{\abs{\alpha}+1},\quad x\in X,\  N\geq T,
\end{equation}
where $E=\bigcup_{U\in\alpha}\phi_U^{-1}((0, 1))$.

Choose the closed neighborhood $Y$ of $y$ in $W$ as follows: the Rokhlin partition
$$\{\{Z_1, \sigma(Z_1), ..., \sigma^{J_1-1}(Z_1)\}, ..., \{Z_k, \sigma(Z_k), ..., \sigma^{J_k-1}(Z_k)\}\}$$
corresponding as in Section \ref{Strut-AY} to $Y$ should satisfy
$$J_1\geq\max\{\frac{\abs{\alpha}+1}{\eps}, T\}.$$
By Lemma \ref{small-nbhd}, there is an open set $V$ such that $Y\subseteq V$, and
for any $1\leq k\leq K$,
\begin{equation}\label{sm-H}
\frac{1}{J_k}(\chi_{V}(x)+\chi_{V}(\sigma(x))+\cdots+\chi_V(\sigma^{J_k-1}(x)))\leq \frac{1}{J_1}<\frac{\eps}{\abs{\alpha}+1},\quad x\in Z_{k}.
\end{equation}
Choose a continuous function $H: X\to [0, 1]$ such that
$$H^{-1}(0)=Y\quad\textrm{and}\quad H^{-1}(1)\supseteq (X\setminus V).$$
Since $Y\subseteq W$, without loss of generality, we may assume that $V\subseteq W$, and then
$$Hg_j=g_j,\quad 1\leq j\leq m.$$

Let us show that the sub-C*-algebra
$$S:=\textrm{C*}\{\phi_U, uH;\ U\in\alpha \}\subseteq A_Y,$$
together with the closed set $Y$,
satisfies the conditions of the theorem.

For each $U\in\alpha$, pick a point $x_U\in U$. Then, by \eqref{eq-small-nbhd}, for each $f_i$, $1\leq i\leq n$,  one has
\begin{equation*}
\norm{f_i-\sum_{U\in \alpha} f_i(x_{U})\phi_U} \leq  \sup_{x\in X}\sum_{U\in \alpha} \abs{f(x)-f_i(x_{U})}\phi_U(x)<\eps;
\end{equation*}
and for each $g_j$, $1\leq j\leq m$, one has
\begin{eqnarray*}
\norm{ug_j-uH\sum_{U\in \alpha} g_j(x_{U})\phi_U}&=&\norm{uHg_j-uH\sum_{U\in \alpha} g_j(x_{U})\phi_U}\\
&\leq &\norm{g_j-\sum_{U\in \alpha} g_j(x_{U})\phi_U}\\
&<&\eps.
\end{eqnarray*}
This shows the approximate inclusion
$$\{f_1, f_2, ..., f_n, ug_1, ug_2, ..., ug_m\} \subseteq_\eps S.$$

Finally, let us show that $\mathrm{dimRatio}(S)<\eps$. For each $1\leq k\leq K$, consider the algebra
$$\textrm{M}_{J_k}(\mathrm{C}(\overline{Z_{k}}))$$
of Theorem \ref{Lin-Sub},
and consider the map
$$\xi_k: \overline{Z_{k}}\to\mathbb R^{(\abs{\alpha}+1)J_k-1}$$ defined by
\begin{equation}\label{defn-xi}
\xi_k(x) \mapsto ((\Phi\circ\sigma(x), \Phi\circ\sigma^2(x),..., \Phi\circ\sigma^{J_k}), (H\circ\sigma(x), ..., H\circ\sigma^{J_k-1}(x))),
\end{equation}
where the map $\Phi: \overline{Z_k}\to\Real^{\abs{\alpha}}$ is defined by $$\Phi=\bigoplus_{U\in\alpha}\phi_U.$$

By \eqref{sm-fctn} and \eqref{sm-H}, the image of $Z_k$ under $\xi_k$ is contained in the set
$$\{(t_1, t_2, ..., t_{(\abs{\alpha}+1)J_k-1})\in [0, 1]^{(\abs{\alpha}+1)J_k-1};\ \textrm{at most ${\eps} J_k$ of the $t_i$ are not $0$ or $1$}\},$$
which has dimension at most $\eps J_k-1$ (as it is a union of simplices with at most $\eps J_k$ vertices). Therefore, $\xi_k(Z_k)$ has dimension at most $\eps J_k$. For convenience,  write $\xi_k(Z_k)=\Delta_k$. We have
$$\mathrm{dim}(\Delta_k)<\eps J_k.$$

For each $x\in Z_k$, the evaluation map $\pi_x$ on $A_Y$ is an irreducible representation of $A_Y$ with dimension $J_k$. Consider the restriction of $\pi_x$ to $S$. Note that for any $x_1, x_2\in Z_{k}$, if
$$\xi_k(x_1)=\xi_k(x_2),$$
 then, by the definition of $\xi_k$, one has
$$\phi_U\circ\sigma^{i}(x_1)=\phi_U\circ\sigma^{i}(x_2)\quad\textrm{and}\quad H\circ\sigma^{j}(x_1)=H\circ\sigma^{j}(x_2),$$
where $U\in \alpha, 1\leq i\leq J_k, 1\leq j\leq J_k-1.$
By \eqref{id-01} and \eqref{id-02} of Theorem \ref{Lin-Sub}, one has that
$$\pi_{x_1}(\phi_U)=\pi_{x_2}(\phi_U)\quad\textrm{and}\quad \pi_{x_1}(uH)=\pi_{x_2}(uH),\quad U\in \alpha.$$
Since $S$ is the sub-C*-algebra generated by $\phi_U$, $U\in {\alpha}$, and $uH$, one has
\begin{equation}\label{eq-rep}
\pi_{x_1}|_S=\pi_{x_2}|_S.
\end{equation}
Moreover, for any $g\in S$, $x\in Z_k$, and any sequence $(x_n)$ in $Z_k$, if $\xi_k(x_n)\to\xi_k(x)$, then
\begin{equation}\label{thm-cond-02-pre}
\pi_{x_n}(g) \to \pi_x(g).
\end{equation}

For any $x\in Z_{k}$, the representation
$\pi_x|_S$ is irreducible on $S$ (hence has dimension $J_k$). In fact, let us consider the image of $uH$ under $\pi_x$, which is
\begin{displaymath}
w:=\left(
\begin{array}{cccc}
0 &    &  & \\
H(\sigma(x)) & 0  &  &  \\
 & \ddots  & \ddots & \\
 &    & H(\sigma^{J_k-1}(x)) & 0
\end{array}
\right)\in \pi_x(S).
\end{displaymath}
Noting that $H^{-1}(0)=Y$ and $x\in Z_k$, one has
\begin{equation}\label{non0}
H(\sigma^i(x))\neq 0, \quad  1\leq i \leq J_k-1.
\end{equation}
Then the C*-algebra generated by $w$ is the full matrix algebra $\mathrm{M}_{J_k}(\mathbb C)$, and the restriction of $\pi_x$ to $S$ must be irreducible. In particular,
\begin{equation}\label{thn-cond-03-pre}
\pi_x(S)=\mathrm{M}_{J_k}(\Comp).
\end{equation}
Therefore, one has that the dimension of an irreducible representation of $S$ must be $J_k$ for some $k$, and each irreducible representation $S$ with dimension $J_k$ is the restriction of $\pi_x$ for some $x\in Z_{k}$.

Let $x_1, x_2\in Z_k$.
One asserts that
\begin{equation}\label{lem-cond-01-pre}
\textrm{$\pi_{x_1}|_S$ and $\pi_{x_2}|_S$ are unitarily equivalent if and only if $\xi_k(x_1)=\xi_k(x_2)$}.
\end{equation}

If $\xi_k(x_1)=\xi_k(x_2)$, then, as shown above, one has
$$\pi_{x_1}|_{S}=\pi_{x_2}|_S.$$
In particular, $\pi_{x_1}|_S$ and $\pi_{x_2}|_S$ are unitarily equivalent.

Now, assume that $\pi_{x_1}|_S$ and $\pi_{x_2}|_S$ are unitarily equivalent. Pick $\phi_U$, and consider the pair $(\phi_U, uH)$. Again, by  \eqref{id-01} and \eqref{id-02} of Theorem \ref{Lin-Sub}, one has that
\begin{displaymath}
\pi_{x_1}(\phi_U)=
\left(
\begin{array}{ccc}
\phi_U(\sigma(x_1)) & & \\

 & \ddots &\\
 & & \phi_U(\sigma^{J_k}(x_1))
\end{array}
\right),\ \
\pi_{x_1}(uH)=
\left(
\begin{array}{cccc}
0 & & & \\
H(\sigma(x_1))& 0& & \\
&  \ddots& \ddots &\\
& & H(\sigma^{J_k-1}(x_1)) & 0
\end{array}
\right),
\end{displaymath}
and
\begin{displaymath}
\pi_{x_2}(\phi_U)=
\left(
\begin{array}{ccc}
\phi_U(\sigma(x_2)) & & \\

 & \ddots &\\
 & & \phi_U(\sigma^{J_k}(x_2))
\end{array}
\right),\ \
\pi_{x_1}(uH)=
\left(
\begin{array}{cccc}
0 & & & \\
H(\sigma(x_2))& 0& & \\
&  \ddots& \ddots &\\
& & H(\sigma^{J_k-1}(x_2)) & 0
\end{array}
\right).
\end{displaymath}
Since $\pi_{x_1}$ and $\pi_{x_2}$ are assumed to be unitarily equivalent, the pair of matrices $(\pi_{x_1}(\phi_U), \pi_{x_1}(uH))$ is unitarily equivalent to the pair of matrices $(\pi_{x_2}(\phi_U), \pi_{x_2}(uH))$. By \eqref{non0}, one may apply Lemma \ref{uni-sep} to obtain
$$\phi_U(\sigma^i(x_1))= \phi_U(\sigma^i(x_2))\quad\textrm{and}\quad H(\sigma^j(x_1))= H(\sigma^j(x_2)),\quad 1\leq i\leq J_k, 1\leq j\leq J_k-1.$$ Applying this argument for all $U\in \alpha$, one has that
$$\phi_U(\sigma^i(x_1))= \phi_U(\sigma^i(x_2))\quad\textrm{and}\quad H(\sigma^j(x_1))= H(\sigma^j(x_2)),\quad U\in\alpha, 1\leq i\leq J_k, 1\leq j\leq J_k-1,$$
and this implies (by the construction of the map $\xi_k$; see \eqref{defn-xi})
$$\xi_k(x_1)=\xi_k(x_2).$$
This proves the assertion.

Since any irreducible representation of $S$ is contained in a irreducible representation of $A_Y$, and $\{\pi_x;\  x\in Y\}$ are all of the irreducible representations of $A_Y$, one has that the dimensions of the irreducible representations of $S$ have to be $J_1, J_2, ..., J_K$, and the map $\xi$ induces a bijection between $\mathrm{Prim}_{J_k}(S)$ and $\Delta_k$ for each $1\leq k\leq K$. Then the subquotient with $J_k$-dimensional representations of $S$, denoted by $S_k$, is a sub-C*-algebra of the subquotient with $J_k$-dimensional representations of $A_Y$, which is canonically isomorphic to $\mathrm{M}_{J_k}(\mathrm{C}_0(Z_k))$. By \eqref{lem-cond-01-pre}, one has that for any $x_1, x_2\in Z_k$,
\begin{equation}\label{lem-cond-01}
\textrm{$\pi_{x_1}|_{S_k}$ is unitarily equivalent to $\pi_{x_2}|_{S_k}$ if and only if $\xi_k(x_1)=\xi_k(x_2)$}.
\end{equation}
By \eqref{thm-cond-02-pre}, one has that
for any $g\in S_k$, any $x\in Z_k$, and any sequence $(x_n)$ in $Z_k$, if $\xi_k(x_n)\to\xi_k(x)$, then
\begin{equation}\label{lem-cond-02}
\pi_{x_n}(g) \to \pi_x(g).
\end{equation}
Therefore, the conditions of Lemma \ref{cont-field} are satisfied for the sub-C*-algebra $S_k$ of $\mathrm{M}_{J_k}(\mathrm{C}_0(Z_k))$, and it follows that
$$S_k\cong\mathrm{M}_{J_k}(\mathrm{C}_0(\Delta_k)).$$
This implies that  $$\mathrm{Prim}_{J_k}(S)=\mathrm{Prim}(S_k)=\Delta_k,$$ and hence
$$\mathrm{dim}(\mathrm{Prim}_{J_k}(S))= \mathrm{dim}(\Delta_k)<\eps J_k.$$
In particular, one has
$$\textrm{dimRatio}(S)<\eps,$$
as desired.
\end{proof}

\begin{thm}\label{lc-app-w}
Let $X$ be an infinite compact metrizable space, and let $\sigma: X\to X$ be a minimal homeomorphism. If $(X, \sigma)$ has mean dimension zero, then the C*-algebra $A_y$ is a locally approximately subhomogeneous C*-algebra with slow dimension growth.
\end{thm}
\begin{proof}
This follows directly from Theorem \ref{lc-app}.
\end{proof}

\begin{thm}\label{Z-stb}
Let $X$ be an infinite compact metrizable space, and let $\sigma: X\to X$ be a minimal homeomorphism. If $(X, \sigma)$ has mean dimension zero, then the C*-algebra $A=\mathrm{C}(X)\rtimes_{\sigma}\mathbb Z$ absorbs the Jiang-Su algebra $\mathcal Z$ tensorially.
\end{thm}
\begin{proof}
By Theorem \ref{lc-app-w}, the C*-algebra $A_y$ is locally approximated by subhomogeneous C*-algebras with arbitrarily small dimension ratio. By Lemma 5.8 and Lemma 5.10 of \cite{Niu-MD}, the Cuntz semigroups of $A_y$ and $A_y\otimes\mathcal Z$ are isomorphic, and therefore $A_y\cong A_y\otimes\mathcal Z$ by Corollary 7.4 of \cite{Winter-Z-stable-02}. Since $A_y$ is centrally large in $A$ in the sense of D.~Archey and N.~C.~Phillips, by \cite{A-NCP-LAlg}, the nuclear C*-algebra $A$ also satisfies $A\cong A\otimes\mathcal Z$.
\end{proof}

\begin{cor}\label{z-clasn}
Let $(X, \sigma)$ be a minimal system with mean dimension zero, where $X$ is infinite. Consider $A=\mathrm{C}(X)\rtimes_{\sigma}\mathbb Z$. Suppose that the projections of $A$ separates traces. Then $A$ belongs to the class of $\mathcal Z$-stable rationally AH algebras, and hence is classifiable. In particular, $A$ is classifiable if $(X, \sigma)$ is uniquly ergodic.
\end{cor}
\begin{proof}
Since $(X, \sigma)$ has mean dimension zero, the C*-algebra $A$ is Jiang-Su stable by Corollary \ref{Z-stb}. By \cite{TW-Dym} and \cite{TW-Dym-1}, the C*-algebra $A$ is rationally AH. Therefore it is covered by the classification theorem of \cite{Winter-Z}, \cite{Lin-App}, \cite{L-N}.
\end{proof}

\section{The tensor products}

In this section, let us show that the tensor product of the crossed product C*-algebras of minimal homeomorphisms is  $\mathcal Z$-stable (Theorem \ref{prod-prod}). In particular, this implies that Toms growth rank (\cite{Toms-GR}) of any crossed product C*-algebra $\mathrm{C}(X)\rtimes_\sigma\Int$ with $(X, \sigma)$ is minimal is at most two. This also shows that the examples of Giol and Kerr (\cite{GK-Dyn}) are prime among the C*-algebras of  minimal homeomorphisms.

\begin{thm}\label{lc-app-mdA}
Let $X$ be an infinite compact metrizable space, and let $\sigma$ be a minimal homeomorphism. Let $$\{f_1, f_2, ..., f_n, g_1, g_2, ..., g_m\}\subseteq \mathrm{C}(X)$$ with $g_i(W)=\{0\}$, $i=1, ..., m$, for some open set $W$ containing $y$. Then, for any $\eps>0$, there is $R>0$ such that for any $J\in\mathbb{N}$, there is a closed neighborhood $Y$ of $y$ contained in $W$ such that the finite subset
$$\{f_1, f_2, ..., f_n, ug_1, ug_2, ..., ug_m\}$$
of $A_Y$, where $u$ is the canonical unitary of the crossed product, is approximated to within $\eps$ by a subhomogeneous C*-algebra $S$ in $A_Y$ with dimension ratio at most $R$, and with the dimension of each irreducible representation at least $J$.
\end{thm}

\begin{proof}
The proof is a slight modification of the proof of Theorem \ref{lc-app}.

Let $\eps>0$ be arbitrary. Choose a finite open cover
$$\alpha=\{U_1, U_2, ..., U_{\abs{\alpha}}\}$$
of $X$ such that
\begin{equation}\label{eq-small-nbhd}
\abs{f_i(x)-f_i(y)} < \eps\quad\mathrm{and}\quad \abs{g_j(x)-g_j(y)} < \eps,\quad x, y\in U_i,\  1\leq i\leq\abs{\alpha}.
\end{equation}
Then $$R=\abs{\alpha}+1$$
is the desired constant.

Let $J \in\mathbb N$ be arbitrary. Choose the closed neighborhood $Y$ of $y$ in $W$ as follows: the Rokhlin partition
$$\{\{Z_1, \sigma(Z_1), ..., \sigma^{J_1-1}(Z_1)\}, ..., \{Z_k, \sigma(Z_k), ..., \sigma^{J_k-1}(Z_k)\}\}$$
corresponding as in Section \ref{Strut-AY} to $Y$ should satisfy
$$J_1\geq J.$$

Pick an open set  $V$ such that $Y\subseteq V\subseteq W$, and pick a continuous function $H: X\to [0, 1]$ such that
$$H^{-1}(0)=Y\quad\textrm{and}\quad H^{-1}(1)\supseteq (X\setminus V).$$
Since $Y\subseteq W$, without loss of generality, we may assume that $V\subseteq W$, and then
$$Hg_j=g_j,\quad 1\leq j\leq m.$$

Choose a partition of unity $\{\phi_U: U\in\alpha\}$ subordinated to $\alpha$.

Let us show that the sub-C*-algebra
$$S:=\textrm{C*}\{\phi_U, uH;\ U\in\alpha \}\subseteq A_Y,$$
together with the closed set $Y$,
satisfies the conditions of the theorem (for $R$ and $J$).

For each $U\in\alpha$, pick a point $x_U\in U$. Then, by \eqref{eq-small-nbhd}, for each $f_i$, $1\leq i\leq n$,  one has
\begin{equation*}
\norm{f_i-\sum_{U\in \alpha} f_i(x_{U})\phi_U} \leq  \sup_{x\in X}\sum_{U\in \alpha} \abs{f(x)-f_i(x_{U})}\phi_U(x)<\eps;
\end{equation*}
and for each $g_j$, $1\leq j\leq m$, one has
\begin{eqnarray*}
\norm{ug_j-uH\sum_{U\in \alpha} g_j(x_{U})\phi_U}&=&\norm{uHg_j-uH\sum_{U\in \alpha} g_j(x_{U})\phi_U}\\
&\leq &\norm{g_j-\sum_{U\in \alpha} g_j(x_{U})\phi_U}\\
&<&\eps.
\end{eqnarray*}
This shows that
$$\{f_1, f_2, ..., f_n, ug_1, ug_2, ..., ug_m\} \subseteq_\eps S.$$

Let us show that $\mathrm{dimRatio}(S)\leq R$. For each $1\leq k\leq K$, consider the algebra
$$\textrm{M}_{J_k}(\mathrm{C}(\overline{Z_{k}}))$$
of Theorem \ref{Lin-Sub},
and consider the map
$$\xi_k: \overline{Z_{k}}\to\mathbb R^{(\abs{\alpha}+1)J_k-1}$$ defined by
\begin{equation}\label{defn-xi-non-md0}
\xi_k(x) \mapsto ((\Phi\circ\sigma(x), \Phi\circ\sigma^2(x),..., \Phi\circ\sigma^{J_k}), (H\circ\sigma(x), ..., H\circ\sigma^{J_k-1}(x))),
\end{equation}
where the map $\Phi: \overline{Z_k}\to\Real^{\abs{\alpha}}$ is defined by $$\Phi=\bigoplus_{U\in\alpha}\phi_U.$$
It is clear that image of $\xi_k(Z_k)$ has dimension at most $(\abs{\alpha}+1)J_k-1$. Then an argument similar to that of Theorem \ref{lc-app} shows that the irreducible representations of $S$ have dimension
$$J_1<J_2<\cdots<J_K,$$
and that
$$\mathrm{dim}(\mathrm{Prim}_{J_k}(S))\leq (\abs{\alpha}+1)J_k-1.$$
Therefore,
$$\mathrm{dimRatio}(S)< \abs{\alpha}+1=R,$$
and the dimension of each irreducible representation of $S$ is at least $J$ (note that $J\leq J_1$).
\end{proof}

\begin{lem}\label{disj-prod}
Let $C$ and $S$ be subhomogeneous C*-algebras, and let $m_0, n_0, m_1, n_1$, and $d$ be natural numbers satisfying $m_0m_1=n_0n_1=d$ and $m_0\neq n_0$. Assume that $C$ has irreducible representations of dimensions $m_0$ and $n_0$, and that $S$ has irreducible representations of dimensions $m_1$ and $n_1$. Consider the subsets $E$ and $F$ of $X:=\mathrm{Prim}_d(C\otimes S)$ defined by
$$E=\{\rho: \rho=\pi_0\otimes\pi_1,\ \pi_0\in \mathrm{Prim}_{m_0}(C),\ \pi_1\in \mathrm{Prim}_{m_1}(S)\}$$
and
$$F=\{\rho: \rho=\pi_0\otimes\pi_1,\ \pi_0\in \mathrm{Prim}_{n_0}(C),\ \pi_1\in \mathrm{Prim}_{n_1}(S)\}.$$
Then the closures of $E$ and $F$ (in $X$) are disjoint. In particular, the sets $E$ and $F$ are relatively closed subsets of $X$.
\end{lem}

\begin{proof}
Assuming the contrary, there would be $(\pi_k^{0}\otimes\pi_k^{1})$ converging to $\pi_\infty^{(0)}\otimes \pi_\infty^{(1)}$ in $\mathrm{Prim}_d(C\otimes S)$, where
$$\pi_k^0\in\mathrm{Prim}_{m_0}(C),\ \pi_k^1\in\mathrm{Prim}_{m_1}(S),\quad k=1, 2, ...$$
and
$$\pi_\infty^0\in\mathrm{Prim}_{n_0}(C),\ \pi_\infty^1\in\mathrm{Prim}_{n_1}(S),\quad k=1, 2, ...\ .$$
Without loss of generality, one may assume that $m_0<n_0$ (hence $m_1>n_1$).

For any $c\otimes s\in C\otimes S$, consider the sequence
$$\mathrm{Tr}((\pi_k^{0}\otimes\pi_k^{1})(c\otimes s))=\mathrm{Tr}(\pi_k^{0}(c)\otimes\pi_k^{1}(s))=\mathrm{Tr}(\pi_k^{0}(c))\cdot \mathrm{Tr}(\pi_k^{1}(s)),\quad k=1, 2, ...$$
Since $(\pi_k^{0}\otimes\pi_k^{1}) \to \pi_\infty^{(0)}\otimes \pi_\infty^{(1)}$ in $\mathrm{Prim}_d(C\otimes S)$, one has
$$\mathrm{Tr}(\pi_k^{0}(c))\cdot \mathrm{Tr}(\pi_k^{1}(s))\to \mathrm{Tr}(\pi_\infty^{0}(c))\cdot \mathrm{Tr}(\pi_\infty^{1}(s)),\quad k\to\infty.$$
Setting $s=1_S$, one has that
\begin{equation}\label{tr-conv}
\mathrm{Tr}(\pi_k^{0}(c))\to \frac{n_1}{m_1}\cdot \mathrm{Tr}(\pi_\infty^{0}(c)),\quad k\to\infty,\ c\in C.
\end{equation}
Note that $(\pi_k^0)\subseteq \mathrm{Prim}_{m_0}(C)$, $\pi_\infty^0\in \mathrm{Prim}_{n_0}(C)$, and $m_0<n_0$. There is $c\in C$ such that
$$\pi_\infty^0(c)\neq 0\quad\textrm{but}\quad \pi(c)=0,\quad \pi\in\mathrm{Prim}_{m_0}(C).$$ In particular,
$$\pi_k^0(c)=0,\quad k=1, 2, ...\ .$$
But this contradicts to \eqref{tr-conv}.
\end{proof}

\begin{lem}\label{dimR-prod}
Let $C$ and $S$ be unital subhomogeneous C*-algebras, and let $J$ be a natural number such that each irreducible representation of $C$ or $S$ has dimension at least $J$. Then
$$\mathrm{dimRatio}(C\otimes S)\leq \frac{\mathrm{dimRatio}(C)+\mathrm{dimRatio}(S)}{J}.$$
\end{lem}
\begin{proof}
Let $d$ be any natural number. Then
$$\mathrm{Prim}_d(C\otimes S)=\bigsqcup_{mn=d}(\mathrm{Prim}_{m}(C) \times \mathrm{Prim}_n(S)).$$
By Lemma \ref{disj-prod}, each $\mathrm{Prim}_{m}(C) \times \mathrm{Prim}_n(S)$ is relatively close in $\mathrm{Prim}_d(C\otimes S)$, and then one has
\begin{eqnarray*}
\mathrm{dim}(\mathrm{Prim}_d(C\otimes S)) &=&\max_{mn=d}\{\mathrm{dim}(\mathrm{Prim}_m(C)\times\mathrm{Prim}_n(S))\}\\
&\leq&\max_{mn=d}\{\mathrm{dim}(\mathrm{Prim}_m(C))+\mathrm{dim}(\mathrm{Prim}_n(S))\}.
\end{eqnarray*}
This implies
\begin{eqnarray*}
\frac{\mathrm{dim}(\mathrm{Prim}_d(C\otimes S))}{d} & \leq & \max_{d=mn}\{\frac{\mathrm{dim}(\mathrm{Prim}_m(C))+\mathrm{dim}(\mathrm{Prim}_n(S))}{d}\} \\
&=& \max_{d=mn}\{\frac{\mathrm{dim}(\mathrm{Prim}_m(C))}{m}\cdot\frac{1}{n}+\frac{\mathrm{dim}(\mathrm{Prim}_n(S))}{n}\cdot\frac{1}{m}\} \\
&\leq & \max_{d=mn}\{\mathrm{dimRatio}(C)\cdot\frac{1}{n}+\mathrm{dimRatio}(S)\cdot\frac{1}{m}\}\\
&\leq & \frac{\mathrm{dimRatio}(C)+\mathrm{dimRatio}(S)}{J},
\end{eqnarray*}
as desired.
\end{proof}

\begin{lem}\label{prod-sgd}
Let $A$ and $B$ be C*-algebras satisfying the following: For any finite subset $\mathcal F$ of $A$ (or $B$) and any $\eps>0$, there is $R>0$ (which depends on $\mathcal F$ and $\eps$) and a sequence of unital sub-C*-algebras $(S_n)$ such that
\begin{enumerate}
\item each $S_n$ is a subhomogeneous C*-algebra with $\mathrm{dimRatio}(S_n)\leq R$,
\item each $S_n$ approximately contains $\mathcal F$ up to $\eps$, and
\item $d_n\to\infty$ as $n\to\infty$, where $d_n$ is the smallest dimension of the irreducible representations of $S_n$.
\end{enumerate}
Then $A\otimes B$ can be locally approximated by subhomogeneous C*-algebras with slow dimension growth.
\end{lem}
\begin{proof}
It is enough to show that for any finite subsets $\F\subseteq A$, $\mathcal G\subseteq B$, and any $\eps\in(0, 1)$, there is a subhomogeneous C*-algebra $D$ in $A\otimes B$ such that $\mathcal F\otimes \mathcal G\subseteq_\eps D$ and $\mathrm{dimRatio}(D)<\eps$.

Without loss of generality, one may assume that each element of $\mathcal F$ and $\mathcal G$ has norm one. By the assumptions, there are subhomogeneous C*-algebras $C\subseteq A$ and $S\subseteq B$ such that
$$\mathrm{dimRatio}(C)\leq R\quad\textrm{and}\quad \F\subseteq_{\frac{\eps}{4}} C,$$
and
$$\mathrm{dimRatio}(S)\leq R\quad\textrm{and}\quad \mathcal G\subseteq_{\frac{\eps}{4}} S,$$
and, furthermore, the dimension of each irreducible representation of $C$ or $S$ is at least $\frac{2R}{\eps}$. Then consider the C*-algebra
$$D:=C\otimes S.$$

By Lemma \ref{dimR-prod}, one has
$$\mathrm{dimRatio}(D)\leq \eps.$$
A straightforward calculation also shows that
$$\mathcal F\otimes\mathcal G\subseteq_{\eps} D,$$
and this finishes the proof.
\end{proof}

\begin{prop}\label{prod-Lalg}
Let $(X_1, \sigma_1)$ and $(X_2, \sigma_2)$ be minimal systems, where $X_1$ and $X_2$ are infinite. Fix $y_1\in X_1$ and $y_2\in X_2$, and consider the large sub-C*-algebras $$A_{y_1}\subseteq \mathrm{C}(X_1)\rtimes_{\sigma_1}\Int \quad \textrm{and}\quad A_{y_2}\subseteq \mathrm{C}(X_2)\rtimes_{\sigma_2}\Int.$$
Then $$A_{y_1}\otimes A_{y_2}\cong (A_{y_1}\otimes A_{y_2})\otimes\mathcal Z.$$
\end{prop}
\begin{proof}
By Theorem \ref{lc-app-mdA} and Lemma \ref{prod-sgd}, the C*-algebra $A_{y_1}\otimes A_{y_2}$ is locally approximated by subhomogeneous C*-algebras with slow dimension growth, and therefore it absorbs the Jiang-Su algebra tensorially.
\end{proof}

\begin{thm}\label{prod-prod}
Let $(X_1, \sigma_1)$ and $(X_2, \sigma_2)$ be minimal systems, where $X_1$ and $X_2$ are infinite compact metrizable spaces. Consider the C*-algebras $$A_1=\mathrm{C}(X_1)\rtimes_{\sigma_1}\Int \quad \textrm{and}\quad A_{2}= \mathrm{C}(X_2)\rtimes_{\sigma_2}\Int.$$
Then $$A_{1}\otimes A_{2}\cong (A_{1}\otimes A_{2})\otimes\mathcal Z.$$
In particular, the crossed product C*-algebra of a minimal homeomorphism has Toms growth rank (\cite{Toms-GR}) at most 2.
\end{thm}
\begin{proof}
By Proposition \ref{prod-Lalg}, the C*-algebra $A_{y_1}\otimes A_{y_2}$ absorbs the Jiang-Su algebra $\mathcal Z$. By Lemma \ref{CLalg-prod}, $A_{y_1}\otimes A_{y_2}$ is centrally large in $A_1\otimes A_2$. By \cite{NCP-LAlg}, the nuclear C*-algebra $A_1\otimes A_2$ absorbs the Jiang-Su algebra.
\end{proof}

\begin{rem}
Note that $$A_1\otimes A_2\cong \mathrm{C}(X_1\times X_2)\rtimes_{\sigma}\Int^2,$$
where the action of $\Int^2$ on $X_1 \times X_2$ is given by $$\sigma_{(m, n)}(x_1, x_2)=(\sigma_1^m(x_1), \sigma_2^n(x_2)).$$ In particular, Theorem \ref{prod-prod} implies that for minimal actions of $\mathbb Z$ on $X_1$ and $X_2$ the crossed product C*-algebra $\mathrm{C}(X_1\times X_2)\rtimes_{\sigma}\Int^2$ always absorbs the Jiang-Su algebra.
\end{rem}

\bibliographystyle{plainurl}


TITLE: To show a certain endomorphism ring is an algebra
QUESTION [0 upvotes]: Let $A$ be an algebra over a field $K$ of finite dimension. Let $M$ be a finitely generated $A$-module. My question is about the ring ${\rm End}_A(M)$ of $A$-endomorphisms of $M$. I want to show that it is a $K$-algebra.
To show that $K$ lies in the center of ${\rm End}_A(M)$, I look at the ring homomorphism $K\to {\rm End}_A(M): \alpha\mapsto \alpha 1_M$, where $1_M$ is the identity mapping on $M$. I can show that $\alpha1_M$ commutes with every $f\in {\rm End}_A(M)$. But is this map 1-1? How can I show that if $\alpha1_M=0$ then $\alpha=0$?

REPLY [1 votes]: Hint: if $f\colon K\to R$ is a ring homomorphism (mapping $1$ to $1$) and $R$ is not a zero ring, then $f$ is one-to-one whenever $K$ is a field.


TITLE: Evaluate the series $\sum_{k\geq 1} \frac{1}{2^k k^2}$
QUESTION [9 upvotes]: How to prove that
$$\sum_{k\geq 1} \frac{1}{2^k k^2}=\frac{\pi^2}{12}-\frac{1}{2}\log(2)^2$$
without using the well-known $\operatorname{Li}_2\left( \frac{1}{2} \right)$ ?
Edited : Thanks for L.F , but I should have made it clear that I want an answer using only series manipulations .

REPLY [6 votes]: Apply Euler Series Transformation to the series
$$
\frac{\pi^2}{12}=\sum_{k=0}^\infty\frac{(-1)^k}{(k+1)^2}\tag{1}
$$
which yields
$$
\begin{align}
\frac{\pi^2}{12}
&=\sum_{n=0}^\infty2^{-n-1}\sum_{k=0}^n\binom{n}{k}\frac{(-1)^k}{(k+1)^2}\tag{2}\\
&=\sum_{n=0}^\infty2^{-n-1}\frac1{n+1}\sum_{k=0}^n\binom{n+1}{k+1}\frac{(-1)^k}{k+1}\tag{3}\\
&=\sum_{n=0}^\infty2^{-n-1}\frac1{n+1}\sum_{k=0}^n\sum_{j=0}^n\binom{j}{k}\frac{(-1)^k}{k+1}\tag{4}\\
&=\sum_{n=0}^\infty2^{-n-1}\frac1{n+1}\sum_{j=0}^n\sum_{k=0}^n\binom{j+1}{k+1}\frac{(-1)^k}{j+1}\tag{5}\\
&=\sum_{n=0}^\infty2^{-n-1}\frac1{n+1}\sum_{j=0}^n\frac1{j+1}\tag{6}\\
&=\sum_{n=1}^\infty2^{-n}\frac1{n}\sum_{j=1}^n\frac1j\tag{7}\\
&=\sum_{n=1}^\infty\frac{H_n}{n2^n}\tag{8}
\end{align}
$$
Use the series for $\log(2)=-\log\left(1-\frac12\right)$
$$
\log(2)=\sum_{m=1}^\infty\frac1{k2^k}\tag{9}
$$
and square to get
$$
\begin{align}
\log(2)^2
&=\sum_{m=1}^\infty\sum_{n=1}^\infty\frac1{mn2^{m+n}}\tag{10}\\
&=\sum_{m=1}^\infty\sum_{n=1}^\infty\frac1{m(m+n)2^{m+n}}+\frac1{n(m+n)2^{m+n}}\tag{11}\\
&=2\sum_{m=1}^\infty\sum_{n=1}^\infty\frac1{m(m+n)2^{m+n}}\tag{12}\\
&=2\sum_{m=1}^\infty\sum_{n=m+1}^\infty\frac1{mn2^n}\tag{13}\\
&=2\sum_{m=1}^\infty\sum_{n=m}^\infty\frac1{mn2^n}-2\sum_{m=1}^\infty\frac1{m^22^m}\tag{14}\\
&=2\sum_{n=1}^\infty\sum_{m=1}^n\frac1{mn2^n}-2\sum_{m=1}^\infty\frac1{m^22^m}\tag{15}\\
&=2\sum_{n=1}^\infty\frac{H_n}{n2^n}-2\sum_{m=1}^\infty\frac1{m^22^m}\tag{16}\\
&=\frac{\pi^2}{6}-2\sum_{m=1}^\infty\frac1{m^22^m}\tag{17}
\end{align}
$$
Therefore,
$$
\sum_{m=1}^\infty\frac1{m^22^m}=\frac{\pi^2}{12}-\frac12\log(2)^2\tag{18}
$$

Explanation
$\hphantom{0}(2)$ Euler Series Transformation
$\hphantom{0}(3)$ $\binom{n+1}{k+1}=\frac{n+1}{k+1}\binom{n}{k}$
$\hphantom{0}(4)$ $\binom{n+1}{k+1}=\sum_{j=0}^n\binom{j}{k}$
$\hphantom{0}(5)$ $\binom{j+1}{k+1}=\frac{j+1}{k+1}\binom{j}{k}$
$\hphantom{0}(6)$ $\sum_{k=0}^j(-1)^k\binom{j+1}{k+1}=1$
$\hphantom{0}(7)$ $j\mapsto j-1$ and $n\mapsto n-1$
$\hphantom{0}(8)$ collect $H_n$
$(10)$ multiply the series
$(11)$ $\frac1{mn}=\frac1{m(m+n)}+\frac1{n(m+n)}$
$(12)$ use symmetry
$(13)$ $n\mapsto n-m$
$(14)$ add and subtract the terms for $m=n$
$(15)$ change order of summation
$(16)$ collect $H_n$
$(17)$ use $(8)$


TITLE: Hoffman and Kunze, linear algebra Chapter 2 sec 2.3 exercise 11
QUESTION [4 upvotes]: Let $V$ be the set of all $2\times 2$ matrices $A$ with complex entries which satisfy $A_{11}+A_{22}=0.$
(a) Show that $V$ is a vector space over $\mathbb{R.}$ (This was easy.)
(b) Find a basis for this vector space.
Since the matrix should be of the form $\begin{bmatrix}a+ib & p+iq\\c+id&-a-ib\end{bmatrix}a,b,c,d,p,q\in \mathbb{R.}$ I think $\{\begin{bmatrix}1 & 0\\0&-1\end{bmatrix},\begin{bmatrix}i & 0\\0&-i\end{bmatrix},\begin{bmatrix}0 & 0\\1&0\end{bmatrix},\begin{bmatrix}0 & 0\\i&0\end{bmatrix},\begin{bmatrix}0 & 1\\0&0\end{bmatrix},\begin{bmatrix}0 & i\\0&0\end{bmatrix}\}$ would do as a basis.
(c) Let $W$ be the set of all matrices $A$ in $V$ such that $A_{21}=-\overline{A_{12}}.$ Prove that $W$ is a subspace of $V$ and find a basis for $W.$
Since the matrix should be of the form $\begin{bmatrix}a+ib & p+iq\\-p+iq&-a-ib\end{bmatrix}a,b,p,q\in \mathbb{R.}$ I think the basis would be $\{\begin{bmatrix}1 & 0\\0&-1\end{bmatrix},\begin{bmatrix}i & 0\\0&-i\end{bmatrix},\begin{bmatrix}0 & 1\\-1&0\end{bmatrix},\begin{bmatrix}0 & i\\i&0\end{bmatrix}\}$.

I want to know if the the basis vectors are correct. Are there any redundant ones or vectors which I am missing out?

REPLY [1 votes]: You should be able to tell at least whether the elements of that set you call basis are linearly independent over the reals $\;\Bbb R\;$ ...and they are.
Now take any element $\;A\in V\;$ , so that you can write
$$A=\begin{pmatrix}a&b\\c&\!-a\end{pmatrix}\;,\;\;a,b,c\in\Bbb C$$
Observe that you can write $\;A\;$ as a linear combination of the set you give, so this is in fact a basis.
Another way Using the above general form for an element $\;A\in V\;$ , it is clear that $\;a,b,c\;$ can be anything in $\;\Bbb C\;$ , and this gives us a space of real dimension $\;2\cdot3=6\;$ , so your six elements are a basis indeed.
Can you also see now why for the other part you got a basis as well?


TITLE: How to find $ \sum_{n=1}^{\infty}\tan^{-1}\frac{2}{n^{2}} $
QUESTION [0 upvotes]: Consider a sequence
$$ s_{n}=\sum_{r=1}^{n}\tan^{-1}\frac{2}{r^{2}} .$$
then we have
$$ \frac{1}{2}\sum_{r=1}^{n}\frac{2}{r^{2}} \leq s_{n} \ \leq \sum_{r=1}^{n}\frac{2}{r^{2}}
\\\Rightarrow \frac{\pi^{2}}{6} \leq \lim_{n \to \infty}s_{n}\leq\frac{\pi^{2}}{3} $$
But how to attack to find the exact value of this limit? Anyone please?

REPLY [8 votes]: Here is a hint:  $$\frac{2}{r^2} = \frac{2}{1 + (r^2 - 1)} = \frac{(r+1) - (r-1)}{1 + (r+1)(r-1)},$$ and $$\tan^{-1} \alpha - \tan^{-1} \beta = \tan^{-1} \frac{\alpha - \beta}{1 + \alpha \beta}.$$


TITLE: Can a Mach number be defined for a hot gas fluid element using its own temperature and velocity?
QUESTION [1 upvotes]: I know that the ratio of an object's speed to the local sound speed is called the Mach number:
$$M = \frac{v}{c_s}$$
where
$$c_s = \sqrt{\frac{\gamma kT}{\mu m_p}}$$
I have always thought of the Mach number in a macroscopic sense (e.g., aircraft in the atmosphere) where the ambient sound speed is used (rather than using the object's own average temperature to compute some "internal" sound speed). However, suppose we have a Lagrangian fluid simulation with unresolved macroscopic gas particles as in the case of astrophysical simulations (e.g., each gas particle has a mass of 1000 solar masses).
Can we define the Mach number of an unresolved macroscopic gas particle using its own temperature to compute the sound speed? What would it mean physically to compare the overall bulk velocity of the unresolved particle to its own internal sound speed (the velocity at which sound waves propagate "within" it)?
How would we interpret this "internal" Mach number? Perhaps that if the unresolved particle's velocity is much larger than its own sound speed (given its temperature), we may expect to see complicated substructure (shocks, etc.) if we could increase the resolution of our simulation?

REPLY [1 votes]: I have always thought of the Mach number in a macroscopic sense (e.g., aircraft in the atmosphere) where the ambient sound speed is used (rather than using the object's own average temperature to compute some "internal" sound speed).

The speed of sound in a gas is defined as:
$$
C_{s}^{2} = \frac{ \partial P }{ \partial \rho } \tag{0}
$$
where $P$ is the thermal pressure and $\rho$ is the mass density.  In an ideal gas, one can assume the pressure is adiabatic or isothermal or any number of things depending on the system.  If we assume the gas is adiabatic, then $P \propto \rho^{\gamma}$ where $\gamma$ is the polytropic index.  Then Equation 0 goes to:
$$
C_{s}^{2} = \frac{ \gamma P }{ \rho } \tag{1}
$$

Can we define the Mach number of an unresolved macroscopic gas particle using its own temperature to compute the sound speed?

In general, most approximations for the thermal pressure explicitly depend upon the temperature.  So yes, we often do use the particle temperature to define the speed of sound of the gas.

What would it mean physically to compare the overall bulk velocity of the unresolved particle to its own internal sound speed (the velocity at which sound waves propagate "within" it)?

Objects moving in the fluid faster than the local speed of sound can generate a shock wave.  A single particle moving faster than $C_{s}$ will not generate a shock wave, as a shock wave requires the bulk response of the system.

How would we interpret this "internal" Mach number?

The sonic Mach number in a collisionally mediated fluid like Earth's atmosphere is the relevant Mach number as it describes the speed of communication of the system.  I am not sure what is meant by "internal" here.

Perhaps that if the unresolved particle's velocity is much larger than its own sound speed (given its temperature), we may expect to see complicated substructure (shocks, etc.) if we could increase the resolution of our simulation?

All fluids are made up of individual particles/molecules, which exhibit velocity distribution functions (VDFs).  The VDFs are modeled as being continuous functions like the Maxwellian.  In all of these cases, there will be particles with peculiar speeds that exceed the local speed of sound by construction/definition, i.e., if you introduce an artificial cutoff in the VDF at the sound speed, you will have to change/update the sound speed (which will be smaller) and again you will have individual particles moving faster than the sound speed.

However, suppose we have a Lagrangian fluid simulation with unresolved macroscopic gas particles as in the case of astrophysical simulations (e.g., each gas particle has a mass of 1000 solar masses).

You can get shock waves just fine in fluid simulations so long as you properly handle the nonlinear steepening terms (i.e., $\mathbf{V} \cdot \nabla \mathbf{V}$) and so called stiff solutions and you have the proper scale lengths resolved (e.g., mean free path in a collisionally mediated fluid).  Technically, I think fluid simulations treat individual particles as massless though, do they not?  That is, they only deal with bulk velocity moments not individual particle motions.  This is why I say they should be able to handle supersonic motions.


text:
\begin{document}

\title{A Multi-Agent Primal-Dual Strategy for Composite Optimization over Distributed Features

}

\author{\IEEEauthorblockN{Sulaiman A. Alghunaim}
\IEEEauthorblockA{\textit{Department of Electrical Engineering} \\
\textit{Kuwait University}\\
\textit{Kuwait} \\
salghunaim@ucla.edu}
\and
\IEEEauthorblockN{Ming Yan}
\IEEEauthorblockA{\textit{Departments of CMSE \& Math} \\

\textit{Michigan State University}\\
\textit{East Lansing, MI, USA} \\
myan@msu.edu}
\and
\IEEEauthorblockN{ Ali H. Sayed}
\IEEEauthorblockA{\textit{School of Engineering} \\
\textit{Ecole Polytechnique Federale de Lausanne} \\
\textit{Switzerland}\\
ali.sayed@epfl.ch}
}
\maketitle

\begin{abstract}
This work studies multi-agent sharing optimization problems with the objective function being the sum of smooth local functions plus a convex (possibly non-smooth) function coupling all agents. This scenario arises in many machine learning and engineering applications, such as regression over distributed features and resource allocation. We reformulate this problem into an equivalent saddle-point problem, which is amenable to decentralized solutions. We then propose a proximal primal-dual algorithm and establish its linear convergence to the optimal solution when the local functions are strongly-convex. To our knowledge, this is the first linearly convergent decentralized algorithm for multi-agent sharing problems with a general convex (possibly non-smooth) coupling function.
\end{abstract}

\begin{IEEEkeywords}
Decentralized composite optimization, primal-dual methods, linear convergence, distributed learning.
\end{IEEEkeywords}

\section{Introduction}
 We consider $K$ agents connected through a graph. Each agent can only send and receive information from its immediate neighbors. Its goal is to find its corresponding solution, denoted by $w^\star_k \in \real^{Q_k}$, of the following coupled multi-agent optimization problem:
\eq{
 \min_{w_1,\cdots,w_K} \quad   \sum_{k=1}^K J_k(w_k)+g\Big(\sum_{k=1}^K B_k w_k \Big), \label{min-generally-coupled}
}
where the smooth function $J_k:\real^{Q_k} \rightarrow \real$ and the matrix $B_k \in \real^{E \times Q_k}$ are known by agent $k$ only, and $g:\real^{E} \rightarrow \real \cup \{+ \infty\}$ is a convex possibly non-smooth function known by all agents. Problem \eqref{min-generally-coupled} is the sharing formulation, where the agents own different variables but are coupled through the function $g$. Problems of the form \eqref{min-generally-coupled} appear in many machine learning applications, such as regression over distributed features~\cite{boyd2011admm,sundhar2012new}, dictionary learning over distributed models~\cite{chen2014dictionary}, and clustering in graphs~\cite{hallac2015network}. They also appear in engineering applications, including smart grid control~\cite{chang2014distributed} and network utility maximization~\cite{palomar2006tutorial}. For a general convex function $g$,  centralized algorithms for \eqref{min-generally-coupled} have been shown to achieve global linear convergence if the matrix $[B_1, \cdots,B_K]$  has full row rank and $\sum\limits_{k=1}^K J_k(w_k)$ is strongly-convex~\cite{chen2013aprimal,dhingra2018proximal,deng2016global}.  On the other hand, {\em decentralized} algorithms have only been shown to converge linearly under stricter conditions than centralized ones.  In this work, we aim toward closing the gap in linear convergence between centralized and decentralized algorithms for problem~\eqref{min-generally-coupled}.

{\bf Literature Review.} Sharing problems have been studied in different fields and date back to studies in economics~\cite{walras1896} --see the discussion in~\cite{boyd2011admm}. The earliest center-free algorithm to solve such problems dates back to~\cite{ho1980class}. Decentralized solutions for the sharing formulation~\eqref{min-generally-coupled} have only been shown to achieve global linear convergence for special cases and under stricter conditions compared to the centralized ones as we now explain. The works~\cite{necoara2013random,doan2017distributed,nedic2018improved,xu2018dual} establish linear convergence for resource allocation formulations, where $g$ is an indicator function of zero (i.e., $g(x)=0$ if $x= 0$ and $\infty$ otherwise) and $B_k=I$, for smooth and strongly-convex local costs. The work~\cite{yang2019distributed} also establishes linear convergence for resource allocation problems in the presence of simple local constraints (i.e., $\underline{w} \leq w_k\leq \overline{w}$), but under stronger assumptions on the costs such as twice differentiability of $J_k$ and knowledge of the conjugate function of $J_k$. The works~\cite{chang2015multi,alghunaim2018proximal} establish linear convergence for special cases with $g$ being an indicator function of zero; moreover, each $B_k$ is required to have full row rank in~\cite{chang2015multi} or satisfy a certain rank condition in~\cite{alghunaim2018proximal}. The works \cite{ying2018supervised,he2018cola} establish linear convergence for strongly convex objectives and a smooth coupling function $g$.

Note that problem \eqref{min-generally-coupled} recovers the consensus problem~\cite{tsitsiklis1986distributed,nedic2009distributed,sayed2014nowbook} if we choose $g$ such that it returns zero when $w_1=\cdots=w_K$ and $\infty$ otherwise. In this case, the matrix $B=[B_1, \cdots,B_K]$ is sparse and encodes the communication graph between agents. The works~\cite{sun2019convergence,alghunaim2019linearly,alghunaim2019decentralized} studied linear convergence of consensus problems in the presence of a common non-smooth term, which is not applicable for the sharing problem. Different from the consensus problem, the matrix $B$ in the sharing problem is not necessarily sparse, and $B_k$ is a private matrix known by agent $k$ only.  Thus, solution methods for these two problems are different \cite{boyd2011admm}.
To the best of our knowledge, establishing linearly convergent algorithms for the {\em sharing} problem~\eqref{min-generally-coupled} with a general convex $g$ are still missing.

{\bf Contribution.}  As mentioned before, there is a theoretical gap between centralized and decentralized algorithms for the sharing problem~\eqref{min-generally-coupled}. In this work, we propose a decentralized algorithm for~\eqref{min-generally-coupled} and establish its linear convergence to the global solution. The derivation of our algorithm is based on reformulating \eqref{min-generally-coupled} into an equivalent problem that is amenable to decentralized solutions. This technique motivates the derivation of many other decentralized algorithms.

{\bf Notation.}  We let $\|x\|^2_{D}=x\tran Dx$ for a square matrix $D$. The symbol $I_S$ denotes the identity matrix of size $S$, and $S$ is removed when there is no confusion. The symbol $\one_N$ denotes the $N \times 1$ vector with all entries being one. The Kronecker product of two matrices is denoted by $A\otimes B$.  We use ${\rm col}\{x_k\}_{k=1}^{K}$ to denote a column vector formed by stacking $x_1,\cdots, x_K$ on top of each other and $\text{blkdiag}\{X_k\}_{k=1}^{K}$ to denote a block diagonal matrix consisting of diagonal blocks $\{X_k\}$.  The subdifferential $\partial f(x)$ of a function $f$ at $x$ is the set of all subgradients.
The proximal operator of a function $f(x)$ with step-size $\mu$ is  $
{\rm prox}_{\mu f}(x)= \argmin\limits_u \ f(u)+{1 \over 2 \mu} \|x-u\|^2$.
The conjugate of a function $f$ is defined as $f^*(v)=\sup\limits_{x} \ v\tran x -f(x)$. A differentiable function $f$ is $\delta$-smooth and $\nu$-strongly-convex if $\|\grad f(x)-\grad f(y)\| \leq \delta \|x-y\|$ and $(x-y)\tran \big(\grad f(x)-\grad f(y)\big) \geq \nu \|x-y\|^2$, respectively, for any $x$ and $y$.

\section{Saddle-Point Reformulation}
In this section, we provide the main assumption on the objective and explain how \eqref{min-generally-coupled} is reformulated into an equivalent saddle-point problem.  We introduce the quantities:
\begin{subequations}
\eq{
\sw &\define {\rm col}\{w_1, \cdots,w_K\} \in \real^Q, ~ Q \textstyle \define \sum_{k=1}^K Q_k, \\
\cJ(\sw) &\define \textstyle \sum_{k=1}^K J_k(w_k), \\
B &\define  \begin{bmatrix}
B_1 & \cdots & B_K
\end{bmatrix} \in \real^{E \times Q}.  \label{B_cen}
}
\end{subequations}
Then, problem \eqref{min-generally-coupled} can be rewritten as:
\eq{
\min_{\ssw} \quad   \cJ(\sw)+g\left(B \sw \right).
\label{primal_reformulated}
}
Throughout this work, the following assumption holds.
\begin{assumption} \label{assump:cost}
{ {\bf (Objective Functions)} Problem \eqref{primal_reformulated} has a solution $\sw^\star$, and the function $\cJ:\real^{Q} \rightarrow \real$ is $\delta$-smooth
and $\nu$-strongly-convex with $0<\nu\leq\delta$. Moreover, the function $g:\real^{E} \rightarrow \real \cup \{+ \infty\}$ is proper lower semi-continuous and convex, and there exists $\sw \in \real^Q$ such that $B\sw$ belongs to the relative interior domain of $g$.   }
\end{assumption}
Under Assumption \ref{assump:cost}, strong duality holds \cite[Corollary 31.2.1]{rockafellar1970convex}, and problem \eqref{primal_reformulated} is equivalent to the following saddle-point problem \cite[Proposition 19.18]{bauschke2011convex}:
\eq{ \boxed{
\min_{\ssw} \max_{y} \quad   \cJ(\sw)+ y\tran B \sw  -g^*(y)} \label{saddle_point_cen}
}
where $y$ is the dual variable and  $g^*$ is the conjugate function of $g$. A primal-dual pair $(\sw^\star, y^\star)$ is  optimal if, and only if, it satisfies the optimality conditions \cite[Proposition 19.18]{bauschke2011convex}:
\begin{subequations} \label{KKT}
\eq{
-B\tran y^\star & = \grad \cJ(\sw^\star)  \label{kkt1}, \\
B \sw^\star & \in   \partial g^*(y^\star) \label{kkt2}.
}
\end{subequations}
Directly solving \eqref{saddle_point_cen} does not result in a decentralized algorithm. This is because the dual variable $y$ couples all agents, and these algorithms would require a centralized unit to compute the dual update. Therefore, further reformulations are needed to derive a decentralized solution.
\section{Decentralized Reformulation}
In this section, we reformulate \eqref{saddle_point_cen} into another equivalent saddle-point problem that can be solved in a decentralized manner.
Since the dual variable $y$ couples all agents, we introduce local copies of $y$ at all agents. Let $y_k$ denote a local copy of $y$ at agent $k$.
In addition, we introduce the following  network quantities:
\begin{subequations}
\eq{
\sy&\define {\rm col}\{y_k\}_{k=1}^K  \in \real^{EK},\quad\cG^*(\ssy)\define{1 \over K}  \sum_{k=1}^K g^*(y_k), \nonumber \\
\cB_d&\define{\rm blkdiag}\{B_k\}_{k=1}^K\in \real^{EK\times Q},\nonumber
}
\end{subequations}
and the symmetric matrix $\cL \in \real^{EK \times EK}$ such that:
\eq{
\cL \sy =0 \iff y_1=\cdots =y_K. \label{consensus_matrix}
}
 Consider the saddle-point problem:
\eq{
\boxed{ \min_{\ssw,\ssx} \max_{\ssy}  \quad   \cJ(\sw)+ \ssy\tran \cB_d \sw+\ssy\tran \cL \ssx -\cG^*(\sy) } \label{saddle_point_dec}
}
with an optimal solution $(\sw^\star,\ssx^\star,\ssy^\star)$ satisfying \cite{bauschke2011convex}:
\begin{subequations} \label{kkt_dec}
\eq{
-\cB_d\tran \sy^\star &=\grad\cJ(\sw^\star),  \label{kkt1_dec} \\
\cL \sy^\star&=   0, \label{kkt2_dec} \\
 \cB_d \sw^\star+\cL \ssx^\star & \in    \partial \cG^*(\sy^\star). \label{kkt3_dec}
}
\end{subequations}
 Problem \eqref{saddle_point_dec} can be solved in a decentralized manner because the matrix $\cL$ encodes the network sparsity structure and the matrix $\cB_d$ is block diagonal. We now show that problems \eqref{saddle_point_dec} and \eqref{saddle_point_cen} are equivalent.

\begin{lemma} {\bf (Saddle-Point)} \label{lemma_kkt_dec}
If $(\sw^\star,\ssx^\star,\ssy^\star)$ satisfies the optimality condition \eqref{kkt_dec}, then it holds that $\sy^\star=\one_K \otimes y^\star$ with $(\sw^\star, y^\star)$ satisfying the optimality condition \eqref{KKT}.
\end{lemma}
\begin{proof}
From equations \eqref{consensus_matrix} and \eqref{kkt2_dec}, we have that $\sy^\star= \one_K \otimes y^\star$ for some $y^\star$. Thus, equation \eqref{kkt1_dec} can be written as:
\eq{
-\cB_d\tran \sy^\star=-B\tran y^\star =\grad\cJ(\sw^\star). \label{lklk1}
}
Multiplying \eqref{kkt3_dec} by $\one_K\tran \otimes I_E$ and using $\sy^\star= \one_K \otimes y^\star$ gives:
\eq{
&(\one_K\tran \otimes I_E)\cB_d \sw^\star+(\one_K\tran \otimes I_E)\cL \ssx^\star & \in   (\one_K\tran \otimes I_E) \partial \cG^*(\sy^\star) \nnb
&\Longrightarrow  B \sw^\star \in \partial g^*(y^\star), \label{lklk2}
}
where we used the fact that $(\one_K\tran \otimes I_E)\cL=0$, which holds from \eqref{consensus_matrix}. From equations \eqref{lklk1} and \eqref{lklk2}, we see that $(\sw^\star, y^\star)$ satisfies the optimality condition \eqref{KKT}.
\end{proof}

\section{Decentralized Strategy}
In this section, we propose an algorithm to solve \eqref{saddle_point_dec} and show how to implement it in a decentralized manner.
\subsection{General Algorithm}

Let $\sw_{-1},\sy_{-1}$ be any values and $\ssx_{-1}=0$. The iteration is:
\begin{subequations} \label{alg_dec}
\eq{
\sw_i&=\sw_{i-1}-\mu_w \grad \cJ(\sw_{i-1})-\mu_w \cB\tran_{d} \sy_{i-1}, \label{W_update_alg} \\
\ssz_{i}&= \sy_{i-1}+\mu_y \cB_{d}  \sw_i  + \cL \ssx_{i-1}, \label{Z_update_alg} \\
\ssx_{i} &= \ssx_{i-1}- \cL \ssz_{i}, \label{X_update_alg} \\
\sy_i&= {\rm prox}_{\mu_y \cG^*}(\bar{\cA} \ssz_{i}), \label{Y_update_alg}
}
\end{subequations}
where $\bar{\cA}=\bar{A} \otimes I_E$ with $\bar{A} \in \real^{K \times K}$ satisfying Assumption \ref{assump:matrix}.
\begin{assumption} \label{assump:matrix}
{ {\bf (Combination Matrices)}  We assume that $\bar{A}$ is a primitive symmetric doubly-stochastic matrix. Moreover, we assume that the matrix $\cL$ satisfies condition \eqref{consensus_matrix} and

\begin{align}      0<I-\cL^2,
\quad   \bar{\cA}^2 \leq I-\cL^2. \label{AleqL_assump}

\end{align}}
\end{assumption}
The condition on $\bar{A}$ can be easily satisfied for any undirected connected network -- see~\cite{sayed2014nowbook}. Note that the eigenvalues of $\bar{\cA}$ belong to $(-1,1]$. Given $\bar{\cA}$, there are many choices for $\cL$. For instance, we can let $\cL^2=I-\bar{\cA}^2$ and check whether $I-\cL^2$ is positive definite or not. If it is positive definite, then the assumption is satisfied. If not, we can let $\cL^2=c(I-\bar{\cA}^2)$ for any $c\in(0,1)$.
Although many choices for $\cL$ and $\bar\cA$ are possible, due to space considerations, we only focus on one choice in this work.

We first construct a primitive symmetric doubly-stochastic matrix $A=[a_{sk}]\in \real^{K\times K}$ such that $a_{sk}=0$ if two agents $s$ and $k$ are not connected through an edge. Then, we let $\bar A = 0.5(I+A)$, which is also a primitive symmetric doubly-stochastic matrix. In this case, the eigenvalues of $\bar\cA$ belong to $(0,1]$, and we can let $\cL^2=I-\bar\cA$, which satisfies Assumption \ref{assump:matrix}. We now show how to implement \eqref{alg_dec} using these choices.

\subsection{Proximal Exact Dual Diffusion (PED$^2$)} \label{sec_dual_prox_diff}
 From \eqref{Z_update_alg}--\eqref{X_update_alg}, it holds that, for all $i\geq 1$,
\eq{
\hspace{-1mm }  \ssz_{i}& \hspace{-0.25mm }  = \hspace{-0.25mm }  (I-\cL^2) \ssz_{i-1}+ \sy_{i-1}-\sy_{i-2}+\mu_y \cB_{d}  (\sw_i -\sw_{i-1}).
}
It eliminates $\ssx_i$, and we can rewrite \eqref{alg_dec} as

\eq{
\hspace{-1mm } \sw_i&=\sw_{i-1}-\mu_w \grad \cJ(\sw_{i-1})-\mu_w \cB\tran_{d} \sy_{i-1},  \nonumber\\
\hspace{-1mm } \ssz_{i}&  =(I-\cL^2) \ssz_{i-1}+ \sy_{i-1}-\sy_{i-2}+\mu_y \cB_{d}  (\sw_i -\sw_{i-1}),\nonumber\\
\hspace{-1mm } \phi_i &=  \bar{\cA} \ssz_{i},   \nonumber\\
\hspace{-1mm } \sy_i&= {\rm prox}_{\mu_y \cG^*}(\phi_i ).\nonumber
}

With our choice of $\bar\cA$ and $\cL$, the $k$-th block in the vectors can be updated by agent $k$. Let $w_{k,-1},~y_{k,-1}$ be any values and $\phi_{k,-1}=\psi_{k,-1}$. For each agent $k$, repeat for $i \geq 0$:
\begin{subequations} \label{exac_proxdiff_dual}
\eq{
w_{k,i}&=w_{k,i-1}-\mu_w \grad J_k(w_{k,i-1})-\mu_w B_k\tran y_{k,i-1}, \\
\psi_{k,i}&= y_{k,i-1}+\mu_y B_{k}  w_{k,i}, \\
z_{k,i} &= \phi_{k,i-1}+\psi_{k,i}-\psi_{k,i-1}, \\
\phi_{k,i}&= \sum_{s \in \cN_k}\bar{a}_{sk} z_{s,i}, \\
y_{k,i}&= {\rm prox}_{\mu_y/K g^*}(\phi_{k,i}).
}
\end{subequations}

\section{Linear Convergence Result}
In this section, we establish the linear convergence of~\eqref{alg_dec}.  We first show that the fixed-point of \eqref{alg_dec} is optimal.
\begin{lemma} {\bf (Fixed Point)} \label{lemma_optimiality}
A  fixed-point $(\sw^o,\ssx^o,\ssy^o, \ssz^o)$ of \eqref{alg_dec} exists, i.e.,
\begin{subequations} \label{optimality_conditions}
\eq{
0&=\grad\cJ(\sw^o) + \cB_d\tran \sy^o, \label{optimality1} \\
\ssz^o&= \sy^o+\mu_y \cB_{d}  \sw^o  + \cL \ssx^o, \label{optimality2} \\
 0&=\cL \ssz^o,  \label{optimality3} \\
 \sy^o&= {\rm prox}_{\mu_y \cG^*}(\bar{\cA} \ssz^o). \label{optimality4}
}
\end{subequations}
Also, for any fixed-point $(\sw^o,\ssx^o,\ssy^o, \ssz^o)$, it holds that $\sy^o=\one_K \otimes y^o$ with $(\sw^o, y^o)$ satisfying the optimality condition \eqref{KKT}.
\end{lemma}
\begin{proof}
Given an optimal solution $(\sw^\star,y^\star)$ of~\eqref{saddle_point_cen} that satisfies \eqref{KKT}, we let $\sw^o \define \sw^\star$ and $\sy^o \define \sy^\star=\one_K\otimes y^\star$. Then, \eqref{optimality1} holds because of \eqref{kkt1_dec}. We define
\eq{
\ssz^o \define \one_K\otimes (y^\star+ {\mu_y\over K}B\sw^\star)\define \one_K\otimes z^o,\label{lem111}
}
which satisfies condition \eqref{optimality3}.
Because of the construction of $\bar{\cA}$ and~\eqref{optimality3}, we have $\bar{\cA} \ssz^o= \ssz^o$, and  equation~\eqref{optimality4} is equivalent to $\ssz^o-\sy^o \in \mu_y \partial \cG^*(\sy^o)$.  Thus, using the definition of $\cG^*$,  equation~\eqref{optimality4}  holds from \eqref{kkt2} and \eqref{lem111}. Finally, we construct $\ssx^o$ such that \eqref{optimality2} holds. To see this, note that
\eq{
& (\one_K^\top\otimes I_E)(\ssz^o- \sy^o-\mu_y \cB_{d}  \sw^o ) \nnb
 = & K (z^o-y^o)-\mu_y B \sw^o \overset{\eqref{lem111}}{=}0
}
The above equation implies that $\ssz^o- \sy^o-\mu_y \cB_{d}  \sw^o $ belongs to the range space of $\cL$ (null space of $(\one_K^\top\otimes I_E)$). Thus, there exists $\ssx^o$ such that \eqref{optimality2} holds.

Now, if $(\sw^o,\ssx^o,\ssy^o, \ssz^o)$ is a fixed-point of \eqref{alg_dec}, then we have $\ssz^o=\one_K\otimes z^o$ because of~\eqref{optimality3}. Therefore, $\bar{\cA} \ssz^o= \ssz^o$, and~\eqref{optimality4} shows that $\ssy^o=\one_K \otimes y^o$. Combining~\eqref{optimality2} and~\eqref{optimality4}, we have $\cB_d\sw^o+{1\over \mu_y}\cL\ssx^o\in\partial \cG^*(\ssy^o)$. Therefore, $(\sw^o,y^o)$ satisfies~\eqref{KKT}, which follows from Lemma \ref{lemma_kkt_dec}.

\end{proof}
Note from \eqref{X_update_alg} that if $\ssx_{-1}=0$, then $\ssx_{1} = - \cL \ssz_{1}$ belongs to the range space of $\cL$. Consequently, $\{\ssx_i\}_{i \geq 0}$ will always remain in  the range space of $\cL$. By following similar arguments to~\cite[Lemma 2]{alghunaim2019linear}, we can always assume that $(\sw^o,\ssx^o,\ssy^o,\ssz^o)$ is a fixed-point with $\ssx^o$ in the range space of $\cL$ because adding a vector in the null space of $\cL$ to $\ssx^o$ does not change the optimality condition. To analyze the algorithm \eqref{alg_dec}, we consider the error quantities:
\begin{subequations}
\eq{
\tsw_i&=\sw_i-\sw^o, \ &\tsy_i&=\ssy_i-\ssy^o, \nonumber\\
\tsz_i&=\ssz_i-\ssz^o, \ &\tsx_{i}&=\ssx_i-{\ssx}^o. \nonumber
}
\end{subequations}
From \eqref{alg_dec} and \eqref{optimality_conditions}, the error quantities evolve as:
\begin{subequations}
\eq{
\tsw_i&=\tsw_{i-1}-\mu_w (\grad \cJ(\sw_{i-1})-\grad \cJ(\sw^o))-\mu_w \cB\tran_{d} \tsy_{i-1}, \label{err_w}\\
\tsz_{i}&= \tsy_{i-1}+\mu_y \cB_{d}  \tsw_i  + \cL \tsx_{i-1}, \label{err_z} \\
\tsx_{i} &= \tsx_{i-1}- \cL \tsz_{i}, \label{err_x} \\
\tsy_i&= {\rm prox}_{\mu_y \cG^*}(\bar{\cA} \ssz_{i})-{\rm prox}_{\mu_y \cG^*}(\bar{\cA} \ssz^o). \label{err_y}
}
\end{subequations}
To state our main result, we note that condition \eqref{AleqL_assump} implies that  $0 \leq \cL^2 < I$. Therefore, $0<\underline{\sigma}(\cL)<1$, where  $\underline{\sigma}(\cL)$ denotes the smallest {\em non-zero} singular value of $\cL$. Let $\sigma_{\max}(\cL)$ denote the largest singular value of $\cL$. The following result establishes the linear convergence of the algorithm \eqref{alg_dec}.
\begin{theorem}\label{thm_lin_con}{\bf (Linear Convergence)}
Let Assumptions \ref{assump:cost} and \ref{assump:matrix} hold. Assume that each $B_k$ has full row rank. If the step-sizes $\mu_w$ and $\mu_y$ are strictly positive and satisfy
\eq{
\mu_w \leq \tfrac{2}{ \delta +\nu}, \quad \mu_y < \tfrac{2 \delta \nu}{(\delta+\nu)\sigma_{\max}^2(\cB_d)}, \label{step_size_c}
}
then it holds that $
\|\tsw_i\|^2 \leq \gamma^i
 C_o$ for all $i \geq 0$
and some $C_o\geq0$ where
\eq{
\gamma=\max & \bigg\{ \frac{1- {2\mu_w \delta \nu \over \delta+\nu}}{ 1-\mu_y \mu_w \sigma_{\max}^2(\cB_d)},1-\mu_w \mu_y\lambda_{\min}(\cB_d\cB_d\tran), \nnb
& \quad1-\underline{\sigma}^2(\cL) \bigg\}<1,
}
with $\lambda_{\min}(\cB_d\cB_d\tran)$ being the smallest eigenvalue of $\cB_d\cB_d\tran$.
\end{theorem}
\begin{proof}
See Appendix \ref{app-thmproof}.
\end{proof}
This theorem shows that the proposed algorithm has linear convergence for non-smooth $g$ if $B_k$ has full row rank. Centralized algorithms can achieve linear convergence when $B=[B_1 \ \cdots \ B_k]$ has full row rank. We leave it to future work to verify whether decentralized algorithms can also achieve linear convergence under the same condition.
\begin{remark}[\sc Semi-strongly-convex] {\rm
Since \eqref{saddle_point_cen} has the same form as \eqref{saddle_point_dec}, it can be solved with existing algorithms. Thus, one can utilize existing algorithms to derive other decentralized  solutions for problem \eqref{saddle_point_dec}. However, existing linear convergence results \cite{chen2013aprimal,dhingra2018proximal,deng2016global} require the saddle-point to be strongly-convex with respect to (w.r.t.) the primal-variable. Problem \eqref{saddle_point_dec} is only strongly-convex w.r.t. the primal block vector $\sw$ but not strongly-convex w.r.t. to the whole variable ${\rm col}\{\sw,\ssx\}$. Therefore, the linear convergence results from \cite{chen2013aprimal,dhingra2018proximal,deng2016global} are not applicable in our setup. }
\end{remark}
\section{Numerical Simulation}
In this section, we apply algorithm \eqref{exac_proxdiff_dual}  to solve the following problem:
\eq{
\min_{w_1,\cdots, w_K} \quad  \frac{1}{2}  \sum_{k=1}^K  w_k\tran R_k w_k + r_k\tran w_k, \ \ s.t. \ \sum_{k=1}^K w_k \leq b.
}
This problem fits into \eqref{min-generally-coupled} with $B_k=I$ and $g(x)=0$ if $x \leq  b$ and $\infty$ otherwise. We randomly generate positive-definite matrices $R_k \in \real^{10 \times 10}$ and vectors $r_k \in \real^{10}$. The entries of the vector $b$ are uniformly chosen between $(0,1)$. The combination matrix $A$ is generated using the Metropolis rule \cite{sayed2014nowbook}. We consider a randomly generated network with $K=20$ agents shown on the left side of Fig.~\ref{fig:sim}. The simulation result is shown on the right side of Fig.~\ref{fig:sim}, where the linearized prox-ascent algorithm is:
\begin{subequations} \label{alg_prox_ascent}
\eq{
\sw_i&=\sw_{i-1}-\mu_w \grad \cJ(\sw_{i-1})-\mu_w B\tran \lambda_{i-1}, \\
\lambda_i&= {\rm prox}_{\mu_y g^*}(\lambda_{i-1}+\mu_y B  \sw_i).
}
The plot clearly shows PED$^2$~\eqref{exac_proxdiff_dual} converges linearly in this setup, and it is slightly slower than the centralized algorithm \eqref{alg_prox_ascent}.
\end{subequations}
\vspace{-5mm}
\begin{figure}[H]
\centering
	\includegraphics[width=\linewidth]{simfig.pdf}
\caption{ \small  The network topology used in the simulation and squared error $\|\sw_i-\sw^\star\|^2$ evolution of the proposed PED$^2$ \eqref{exac_proxdiff_dual} and the centralized algorithm \eqref{alg_prox_ascent} with $\mu_w=0.03$ and $\mu_y=2$.} \label{fig:sim}
\end{figure}

\section{Conclusion}
We studied the sharing problem \eqref{min-generally-coupled}, where agents are coupled through a convex possibly non-smooth composite function. To solve \eqref{min-generally-coupled} in a decentralized manner, we  reformulated it into an equivalent saddle-point problem. We then proposed a proximal decentralized algorithm and established its linear convergence. To our knowledge, this is the first {\em decentralized} linear convergence result for the multi-agent sharing problem \eqref{min-generally-coupled} with a general non-smooth coupling function.

\bibliographystyle{IEEEtran}
\bibliography{myref_review}

\appendices
\section{Proof of Theorem \ref{thm_lin_con}} \label{app-thmproof}
The following lemma establishes a useful equality, whose proof is omitted due to space limitations.
\begin{lemma} {\bf (Equality)} \label{lemma_equality}
Assume that the step-sizes $\mu_w$ and $\mu_y$ are strictly positive. The iterates of \eqref{alg_dec} satisfy:
\eq{
&\|\tsw_i\|^2_{I-\mu_y \mu_w \cB_d\tran \cB_d}+c_y\|\tsz_{i} \|_{I-\cL^2}^2+c_y\|\tsx_{i}\|^2 \nonumber \\
= &  \|\tsw_{i-1}-\mu_w (\grad \cJ(\sw_{i-1})-\grad \cJ(\sw^o))\|^2 \nnb
&  +c_y\|\tsy_{i-1}\|_{I-\mu_w \mu_y \cB_d\cB_d\tran}^2+ c_y\|\tsx_{i-1}\|_{I-\cL^2}^2, \label{equal_lemma}
}
where $c_y=\mu_w / \mu_y$. \qed
\end{lemma}
It can be verified that
\eq{
&\|\tsw_{i-1}-\mu_w (\grad \cJ(\sw_{i-1})-\grad \cJ(\sw^o))\|^2 \nnb
\leq& \big(1- \tfrac{2\mu_w \delta \nu}{ \delta+\nu}\big) \|\tsw_{i-1}\|^2 \nnb
\leq& \left({1- {2\mu_w \delta \nu \over \delta+\nu} \over 1-\mu_y \mu_w \sigma_{\max}^2(\cB_d)}\right) \|\tsw_{i-1}\|_{I-\mu_w \mu_y \cB_d\tran \cB_d}^2. \label{bound_grad_W}
}
where the first inequality holds under Assumption \ref{assump:cost} for  $\mu_w \leq {2 \over \delta+\nu}$ -- see \cite{nesterov2013introductory}. The second inequality holds if $I-\mu_y \mu_w \cB_d\tran \cB_d$ is positive definite.
Let
\eq{
\gamma_1 \define {1- {2\mu_w \delta \nu \over \delta+\nu} \over 1-\mu_y \mu_w \sigma_{\max}^2(\cB_d)}.
}
Then, we have $\gamma_1<1$ if $\mu_y < {2 \delta \nu \over (\delta+\nu)\sigma_{\max}^2(\cB_d)}$.
 Since the proximal mapping is nonexpansive, it holds from \eqref{err_y} that:
\eq{
\|\tsy_i\|^2&= \|{\rm prox}_{\mu_y \cG^*}(\bar{\cA} \ssz_{i})-{\rm prox}_{\mu_y \cG^*}(\bar{\cA} \ssz^o)\|^2 \nnb
&\leq \|\bar{\cA} \tsz_i\|^2= \| \tsz_i\|_{\bar{\cA}^2}^2 \leq  \|\tsz_i\|_{I-\cL^2}^2, \label{bound_Y_Z}
}
where the last inequality holds due to Assumption~\ref{assump:matrix}. Since each $B_k$ has full row rank, it holds that
\eq{
0< \lambda_{\min}(\cB_d\cB_d\tran)I \leq \cB_d\cB_d\tran }
where $\lambda_{\min}(\cdot)$ denotes the smallest eigenvalue of its argument. Therefore,
\eq{
\|\tsy_{i-1}\|_{I-\mu_w \mu_y \cB_d\cB_d\tran}^2 \leq \big(1-\mu_w \mu_y\lambda_{\min}(\cB_d\cB_d\tran)\big)\|\tsy_{i-1}\|^2.  \label{bound_yy}
}
Finally, since $\ssx_{-1}=0$ and ${\ssx}^o$ are in the range space of $\cL$, the error quantity $\tsx_{i-1}$ always belongs to the range space of $\cL$. This implies that $\|\tsx_{i-1}\|_{\cL^2}^2 \geq \underline{\sigma}^2(\cL) \|\tsx_{i-1}\|^2$ where $\underline{\sigma}^2(\cL)$ denotes the minimum non-zero singular value of $\cL$  -- see \cite[Lemma 1]{alghunaim2019linear}. Therefore,
\eq{
\|\tsx_{i-1}\|_{I-\cL^2}^2 \leq (1-\underline{\sigma}^2(\cL)) \|\tsx_{i-1}\|^2 \label{bound_xx}
}
 Substituting the bounds \eqref{bound_grad_W}, \eqref{bound_Y_Z}, \eqref{bound_yy}, and \eqref{bound_xx} into \eqref{equal_lemma} gives:
\eq{
&\|\tsw_i\|^2_{I-\mu_y \mu_w \cB_d\tran \cB_d}+c_y\|\tsy_{i} \|^2+c_y\|\tsx_{i}\|^2 \nnb
& \leq  \gamma_1 \|\tsw_{i-1}\|_{I-\mu_y \mu_w \cB_d\tran \cB_d}^2+\gamma_2 c_y\|\tsy_{i-1}\|^2 +  \gamma_3 c_y\|\tsx_{i-1}\|^2, \label{last_inq}
}
where $\gamma_2 \define  1-\mu_w \mu_y\lambda_{\min}(\cB_d\cB_d\tran)$ and $\gamma_3 \define  1-\underline{\sigma}^2(\cL)$. Under the step-size conditions given in \eqref{step_size_c},
 it holds that $I-\mu_y \mu_w \cB_d\tran \cB_d>0$ and $\gamma=\max\{\gamma_1,\gamma_2,\gamma_3\}<1$. Moreover, we have that $(1-\mu_y \mu_w \sigma_{\max}^2(\cB_d)) \|\tsw_i\|^2 \leq \|\tsw_i\|^2_{I-\mu_y \mu_w \cB_d\tran \cB_d}$. Let
\eq{
C_o= {\|\tsw_{-1}\|_{I-\mu_y \mu_w \cB_d\tran \cB_d}^2+ c_y\|\tsy_{-1}\|^2 +   c_y\|\tsx_{-1}\|^2  \over 1-\mu_y \mu_w \sigma_{\max}^2(\cB_d)}.
}
Iterating inequality \eqref{last_inq}  yields the result.

\end{document}

config: arxiv


TITLE: Maxwell-Faraday Equation and Electric Fields
QUESTION [1 upvotes]: I have a question regarding, as the title says, this equation: $\nabla \times \textbf{E}=-\frac{\partial \textbf{B}}{\partial{t}}$
So, the above equation says that the curl of an electric field is proportional to the rate of change of a magnetic field. However, since electric fields have a potential associated with them (i.e. voltage), they should be conservative and thus have 0 curl.
Then this would mean that all magnetic fields are constant in time. This seems like a very strong result, though, and one that I never hear mentioned at that. So is my assumption above wrong? Or am I just misunderstanding the equation?

REPLY [3 votes]: In fact, for dynamic fields, $\vec E$ is NOT generated by a scalar potential, and instead, is generated by the equation ${\vec E} = - {\vec\nabla}\phi - \frac{\partial{\vec A}}{\partial t}$, where $\vec A$ is the magnetic vector potential, which is related to the magnetic field by ${\vec B} = {\vec \nabla} \times {\vec A}$
Of course, these relations are just a clever way of capturing:
$$\begin{align}
{\vec \nabla}\times {\vec E} &= - {\vec \nabla} \times \left(\vec \nabla \phi\right) - {\vec \nabla} \times \frac{\partial {\vec A} }{\partial t}\\
&= - 0 - \frac{\partial}{\partial t}{\vec \nabla}\times {\vec A}\\
&= -\frac{\partial {\vec B}}{\partial t}
\end{align}
$$
So, I've kind of just restated your question back at you.

REPLY [3 votes]: (Originally posted as a comment):
The flaw is actually implicit in the statement that all electric fields are generated by a potential, $\mathbf{E}=-\nabla\phi$. In fact, that's only valid for electrostatics. Actual time-varying electric/magnetic fields are not necessarily conservative.
For example, when a decreasing magnetic flux is passing through a metal ring, the electrons will start cycling through the ring and the metal will heat up (slightly). If the electric field were truly conservative ($\mathbf{E}=-\nabla\phi$), then by the fundamental theorem of calculus the path integral around the ring ought to vanish, and so no work would be done upon traversing the loop, and so the electrons would have no motivation to move.
But experimentally, we find otherwise, and thus from that you have no choice but to conclude that $\mathbf{E}$ is not conservative.
See also this question.


TITLE: Who first noted that entries in the powers of an adjacency matrix of a graph count the number of walks on the graph?
QUESTION [7 upvotes]: The Wikipedia article on powers of an adjacency matrix presently (as of 2022) notes the neat combinatorial fact that, given an adjacency matrix $A$ of some graph, entries of the $n$th power of the adjacency matrix, $A^n_{ij}$, count the number of $n$-length walks from $i$ to $j$.  The Wikipedia article further relates this to the problem of counting the number of triangles in said graph by dividing the trace of $A^3$ by $6$, and determining the distance between two nodes in an undirected, unweighted graph.
The Wikipedia article does not name these as lemmas or theorems or corollaries, and states them with only the briefest outline of the proof.

Are these folk results, or is there any other interesting history behind who first formulated and proved them?

These are very nice and fun statements to prove, but I'm curious to know if there's anything else to say about their history.
(I am especially interested in how quantum computers could efficiently explore spectral properties of certain large adjacency matrices of certain large graphs, as, by linearity, exponentiation of the spectrum corresponds to exponentiation of the given adjacency matrix - which then corresponds to counting various walks on the graph.)

REPLY [2 votes]: In 1949, social psychologist Leon Festinger and mathematicians R. Duncan Luce and Albert Perry (all working together) published papers introducing the idea in application to social psychology.
They divide this into two papers. One, more sociological, is The analysis of sociograms using matrix algebra by Festinger. This one carefully explains how matrix multiplication works for $A^2$, then does the whole thing again for $A^3$, then finally remarks:

It is apparent that these matrices may also be raised to higher powers to obtain the four-step or five-step or even more indirect connections among the members of a group.

The second paper is A method of matrix analysis of group structure by Luce and Perry. This one presents the result more abstractly and gives a proof. Paragraph 3.01 states:

In $X^n$ the entry ${x_{ij}}^{(n)} = c$ if and only if there are $c$ distinct $n$-chains from $i$ to $j$ (for proof see §5.04). Thus, if in the fifth power of a matrix of data $X$ we find that the number of $9$ occurs in the third row of the seventh column, we may conclude that there are $9$ distinct $5$-chains from element $3$ to element $7$.

Some results later on in the paper also mention something about the diagonal entries of the cube of the matrix, which ought to count triangles, but the results are confusingly phrased.

It is, of course, possible that matrix powers of graphs were known to graph theorists before they were known to sociologists, but I don't have any evidence of this. Bracketing the time window above from both sides, we have:

König's 1936 textbook Theorie der endlichen und unendlichen Graphen, which does define adjacency matrix of graphs, and presents several results on the determinants of the adjacency matrix, but does not even consider products or powers of these matrices. I consider the result on counting walks simpler and more likely to appear in a textbook, so this is some evidence that it was not yet known to graph theorists in 1936.
Berge's Graphs and Hypergraphs (I read the 1973 translation of the French textbook published in 1970) gives the following in Chapter 4, Section 5 (Counting paths):

Corollary 1. If $G$ is a graph and $A$ is its associated matrix, the general coefficient $p^i_j$ of the matrix $P = A^k$ (the product of $A$ with itself $k$ times) equals the number of distinct paths of length $k$ from $x_i$ to $x_j$ in $G$.

It would be interesting to see if Berge's 1958 book Théorie des graphes et ses applications contains this result, but I've been unable to check.


TITLE: Calculating matrix norm
QUESTION [0 upvotes]: I'm trying to follow the lecture notes for a dynamical systems class, and they say the norm of  $$\begin{bmatrix}0 & -3 \mu x_2^2\\-3 \mu x_1^2 & 0\end{bmatrix}$$ is $3 \mu x_1^2 x_2^2$.  How exactly did they compute that?
Thanks!

REPLY [3 votes]: I think this is a misprint. To begin with, if $\mu<0$, $3\mu x_1^2x_2^2$ can be negative, which is an impossible norm value. Even if $\mu>0$, since we can take $x_1=0$ and $x_2\not=0$ as the initial conditions, the initial norm value $3\mu x_1^2x_2^2$ would be zero but the matrix is not. Again, this is impossible.

REPLY [1 votes]: There are several ways to define a matrix norm but according the result you give, we use, for $A\in\mathcal{M}_n(\mathbb{C})$:
$$||A||=\max_{\lambda\in \mathrm{sp}(A^*A)}(\sqrt{|\lambda|}),$$
where $\mathrm{sp}(A)$ is the spectrum of the matrix $A$.
We have
$$A^*A=\begin{bmatrix}9\mu^2x_2^4 & 0\\ 0 & 9\mu^2x_2^4\end{bmatrix}$$
so
$$||A||=\max(3|\mu| x_1^2,3|\mu| x_2^2).$$


TITLE: Cauchy sequences are bounded
QUESTION [0 upvotes]: As $\{x_n\}$ is a Cauchy sequence, there exists a positive integer $N$, such that for any $n \geq N$ and $m \geq N$, $d(x_n,x_m) \lt 1$; that is, $|x_n-x_m| \lt 1$.  Put $M = |x_1| + |x_2| + |x_3| + ... + |x_N |+ 1$.  Then $|x_n| \lt M, $ for all n in the set of Natural numbers.
I don't understand how this can be a bound, won't this sum approach infinity since it's an infinite sequence?  I know another way to prove this is to let $M=max\{|x_1|, |x_2|, |x_3|, ..., |x_N| + 1 \}$, but I can't figure out how to derive this from $|x_n| \lt 1 + |x_N|$.

REPLY [1 votes]: $N$ is fixed and
$$M=|x_1|+|x_2|+|x_3|+\cdots+|x_N|+1$$
is a finite sum.


text:
\section{Limit Points of Infinite Subset of Finite Complement Space}
Tags: Limit Points, Finite Complement Topology

\begin{theorem}
Let $T = \struct {S, \tau}$ be a [[Definition:Finite Complement Space|finite complement space]].
Let $H \subseteq S$ be an [[Definition:Infinite Set|infinite]] [[Definition:Subset|subset]] of $S$.
Then every point of $S$ is a [[Definition:Limit Point of Set|limit point]] of $H$.
\end{theorem}

\begin{proof}
Let $U \in \tau$ be any [[Definition:Open Set (Topology)|open set]] of $T$.
From [[Infinite Subset of Finite Complement Space Intersects Open Sets]], we have that $U \cap H$ is [[Definition:Infinite Set|infinite]] {{iff}} $H$ is [[Definition:Infinite Set|infinite]].
Let $x \in S$.
Then every [[Definition:Open Set (Topology)|open set]] $U$ in $T$ such that $x \in U$ also contains an [[Definition:Infinite Set|infinite number]] of points of $H$ other than $x$.
Thus, by definition, $x$ is a [[Definition:Limit Point of Set|limit point]] of $H$.
{{qed}}
\end{proof}

config: wiki


TITLE: What reason is there to conjecture that every finite string is really in the decimal expansion of $\pi$?
QUESTION [8 upvotes]: One of my students asked me this, and it occurred to me that I had never really questioned it.
Apparently, it is only conjectured but widely believed that the decimal expansion in base $10$ of $\pi$ contains all finite strings of the numerals $0$ through $9$.
Am I even accurate that the conjecture is widely accepted? Regardless, what is the rationale for this belief? Do any good heuristics exist? It seems perfectly logical (dare I say likely) that, just maybe, the string 2347529384759748975847523462346435664900060906, for example, never occurs. The conjecture seems absurdly strong, to me.
And just because a separate question would be ridiculous: does this conjecture extend to other famous transcendental numbers? Is it indeed conjectured that this is a property of transcendental numbers in general?

REPLY [5 votes]: $\pi$ is generally (though weakly) believed to be normal; that is, its infinite sequence of digits, in any base $b$, contain all $1$-digit sequences with density $1/b$, all $2$-digit sequences with density $1/b^2$, all $3$-digit sequences with density $1/b^3$, and so forth.  In particular, this is believed to be true of $\pi$ in base $10$, for somewhat general reasons:

All real numbers are normal, except for a set that is of Lebesgue measure zero.  Roughly speaking, real numbers are normal with probability $1$.  However, it is in general challenging to prove that a given number is normal (other than those numbers "designed" to be normal), and $\pi$ is no exception.
Empirical studies on the digit sequence of $\pi$ (in base $10$, as far as I know) have revealed no statistical tendencies that violate normality.

If $\pi$ is normal, then the weaker assertion that it contains any finite digit sequence at least once (let alone contains it as frequently as any other digit sequence of the same length) is true as a consequence.  As far as I know, there is no intermediate property that is proved of $\pi$, so the question remains open.


TITLE: complex coordinates of perpendicular chords on unit circle
QUESTION [0 upvotes]: I am faced with the following problem..
Consider three points $A (a), B (b), C(c)$ on the unit circle $|a|= |b|= |c|=1$. Find the complex coordinates of the point $D (d)$, where $D$ also lies on the unit circle & $AD \perp BC$.
Here's what I did:
By the first condition, $|d|=1$. We can think this like a cartesian coordinate system where the coordinates of $z$ are $ (\Re (x), \Im (x))$. So the perpendicular condition gives us $\frac{\Im (d)- \Im (a)}{\Re (d) - \Re (a)} \frac{\Im (b) - \Im (c)}{\Re (b) - \Re (c)}= -1$. But how do i continue from here? I am trying to find $d$ explicitly in terms of $a, b, c$. Expanding this looks huge.
Thanks.

REPLY [0 votes]: a point $D$ on $BC$ can be written as $d = (1-t)b + tc$ for some real number $t.$ now we will use the fact that $a$ and $b$ are orthogonal iff $a\bar b + \bar a b = 0.$ we need $t$ so that $AD$ is orthogonal to $BC,$ so
$$[(1-t)b + tc - a][\bar b-\bar c] + [(1 -t)\bar b + t \bar c - \bar a](b- c) = 0 $$
can you take it from here?
if you want the point $D$ on the circumference such that $AD$ and $BC$ are orthogonal then just use $$(a-d)(\bar b - \bar c) + (\bar a - \bar d)(b -c) = 0$$ and the fact that $\bar d = \frac{1}{d}$ to get a quadratic equation for $d.$
solving for $d$ you find $d = a, d = \dfrac{b - c}{a(\bar b - \bar c)}.$ the second is the you want.
check: suppose $a = i, b = -1, c = 1,$ then we know $d = -i.$ let us check the formula for $d = -2/(-2i) = -i$