text:
\begin{document}

\parskip=0.35\baselineskip
\baselineskip=1.2\baselineskip

\title{Connected Components of Spaces of Surface Group Representations II}

\author{Nan-Kuo Ho}
\address{The Fields Institute, Toronto, Canada }
\address{ Department of
Mathematics, National Cheng-Kung University, Taiwan}
\email{nho@fields.utoronto.ca \\ nankuo@mail.ncku.edu.tw}

\author{Chiu-Chu Melissa Liu}
\address{Department of Mathematics \\ Harvard University}
\email{ccliu@math.harvard.edu}

\keywords{ surface group representations}

\subjclass{53}
\date{September 21, 2004}

\begin{abstract}
In \cite{HL1}, we discussed the connected
components of the space of surface group representations for any
compact connected semisimple Lie group and any closed
compact (orientable or nonorientable) surface. In this sequel,
we generalize the results in \cite{HL1} in two directions:
we consider general compact connected Lie groups, and we
consider all compact surfaces, including the ones
with boundaries. We also interpret our results in terms
of moduli spaces of flat connections over compact surfaces.
\end{abstract}
\maketitle

\section{introduction}
In \cite{G2}, W. M. Goldman computed the number of connected components of
spaces of surface group representations $\hol$ for $G=PSL(2,\C)$
or $PSL(2,\R)$, and $\Si$ is a Riemann surface of genus bigger
than $1$. In the same paper, he also made a conjecture for the
general connected complex semisimple Lie group $G$ that there is a
bijection between $\pi_0(\hol/G)$ and
$H^2(\Si,\pi_1(G))\cong\pi_1(G)$, where the $G$-action on $\hol$ is induced
by the conjugate action of $G$ on itself. This conjecture was proved by J. Li in \cite{li}.

In \cite{HL1}, we computed $\pi_0(\hol/G)$ for any compact connected
semisimple Lie group $G$ and any closed (orientable or nonorientable) surface
$\Si$ with negative Euler characteristic, except for the connected sum of a
torus and a Klein bottle.  The first goal of this note is to generalize
the results in \cite{HL1} to general compact connected Lie groups.
The result for orientable surfaces is known:

\begin{tm}\label{thm:irzero}
Let $\Si$ be a connected, closed, compact, orientable surface with genus $\ell>0$.
Let $G$ be a compact connected Lie group, and let $G_{ss}=[G,G]$ be the
maximal connected semi-simple subgroup of $G$.
Then there is a bijection
$$
\pi_0(\hol/G)\to \pi_1(G_{ss}).
$$
\end{tm}
The group $\pi_1(G_{ss})$ in Theorem \ref{thm:irzero} is a finite abelian group.
As we will explain in Section \ref{sec:moduli}, a proof of Theorem
\ref{thm:irzero} can be extracted from \cite{ym}. In this note,
we will give another proof of Theorem \ref{thm:irzero}, and
derive the following result for non-orientable surfaces:

\begin{tm}\label{thm:rzero}
Let $\Si$ be a closed, compact, nonorientable surface which is
homeomorphic to the connected sum of $m$ copies of the real
projective plane, where $m\neq 1,2,4$. Let $G$ be a compact
connected Lie group. Then there is a bijection
$$
\pi_0(\hol/G)\to \pi_1(G)/2\pi_1(G)
$$
where $2\pi_1(G)$ denote the subgroup
$\{k^2\mid k\in\pi_1(G)\}$ of the abelian group $\pi_1(G)$.
\end{tm}

The group $\pi_1(G)/2\pi_1(G)$ in Theorem \ref{thm:rzero} fits in
the following short exact sequence of abelian groups:
$$
1\to \pi_1(G_{ss})/2\pi_1(G_{ss})\to \pi_1(G)/2\pi_2(G)\to
(\Z/2\Z)^{\dim H}\to 1
$$
where $G_{ss}=[G,G]$ and $H$ is the connected component of the identity
of the center of $G$. In particular, $\pi_1(G)/2\pi_1(G)$ is a finite
abelian group.

Theorem \ref{thm:irzero} and Theorem \ref{thm:rzero}
generalize the case where $G$ is semisimple considered in
\cite{HL1} and the case where $G_{ss}$ is simply connected
considered in \cite{HL2}.

The second goal of this note is to generalize the above results
to compact surfaces with boundaries. The same question becomes trivial
in this case:  $\pi_1(\Si)$ is a free group when $\Si$ is a compact
surface with nonempty boundary, so $\hol$ and $\hol/G$ are connected
for any compact connected Lie group $G$. However, the question
becomes interesting when we impose some boundary conditions.
Let $\Si$ be a (possibly nonorientable) compact surface with boundary
components $B_1,\ldots, B_r$. Let
\begin{equation}\label{eqn:holC}
\holC=
\{\phi\in \hol\mid \phi([B_j])\in \cC_j\}
\end{equation}
where $[B_j]\in \pi_1(\Si)$ and $\Cr$ are conjugacy classes in $G$, also known as
{\em markings} in this context. Note that (\ref{eqn:holC})
reduces to $\hol$ when $r=0$. The conjugate action of $G$ on itself
induces a $G$-action on $\holC$. We will compute
$$
\pi_0(\holC/G)=\pi_0(\holC).
$$

For orientable surfaces, we have
\begin{tm}\label{thm:izero}
Let $\Si$ be a connected, closed, compact, orientable surface with $\ell>0$
handles and $r>0$ boundary components.
Let $G$ be a compact connected Lie group, and let $G_{ss}=[G,G]$ be the
maximal connected semi-simple subgroup of $G$.
Then
$$
\holC/G
$$
is nonempty iff $d_1\cdots d_r\in G_{ss}$ for some
(and therefore for all) $(d_1,\ldots,d_r)\in \Ct$.
For any conjugacy classes $\Cr$ of $G$ such that $d_1\cdots d_r\in G_{ss}$
for some $(d_1,\ldots, d_r)\in\Ct$, there is a bijection
$$
\pi_0(\holC/G)\to \pi_1(G_{ss})/J_{\Cr}
$$
where $J_{\Cr}$ is a subgroup of $\pi_1(G_{ss})$ defined
in Section \ref{sec:conjugate}.
\end{tm}

Let $\Si$ and $G$ be as Theorem \ref{thm:izero}.
By Theorem \ref{thm:izero}, when $G$ is semisimple and simply connnected,
for example, $SU(n)\,(n\geq 2)$, $Spin(n)\,(n\geq 3)$, $Sp(n)\,(n\geq 1)$,
$\holC/G$ is nonempty and connected  for any conjugacy classes $\Cr$;
when $G$ is not semisimple and $G_{ss}$
is simply connected, for example, $U(n)$ or compact torus, $\holC/G$ is either
empty or connected. When $G=SO(n)\, (n\geq 3)$, $\holC/G$ is nonempty
and has either one or two connected components. We will see later that for
generic conjugacy classes $\Cr$ in $SO(n)$, $J_{\Cr}$ is trivial, and in
that case $\holC/G$ has two connected components.

For nonorientable surfaces, we have
\begin{tm}\label{thm:nonzero}
Let $\Si$ be a connected, compact, nonorientable surface which is
homeomorphic to the connected sum of a sphere with $r$ holes and
$m$ copies of the real projective plane, where $m\neq 1,2,4$.
Let $G$ be a compact connected Lie group. Then there is a bijection
$$
\pi_0(\holC/G)\to \pi_1(G)/J'_{\Cr}
$$
where $J'_{\Cr}$ is the subgroup of $\pi_1(G)$ generated by
$2\pi_1(G)$ and $J_{\Cr}$.
\end{tm}

Note that $\pi_1(G)/J'_{\Cr}$ is the quotient group of the finite
abelian group $\pi_1(G)/2\pi_1(G)$. Let $\Si$ and $G$ be
as in Theorem \ref{thm:nonzero}. When $G$ is semisimple and simply
connected, for example,
 $SU(n)\, (n\geq 2)$, $Spin(n)\,(n\geq 3)$, $Sp(n)\,(n\geq 1)$,
$\hol/G$ is nonempty and connected for any conjugacy classes
$\Cr$ in $G$. When $G=U(n)$, $\pi_1(G)=\Z$ and
$J_{\Cr}\subset \pi_1(G_{ss})$ is
trivial, so $\holC/G$ has two connected components.
When  $G=SO(n)$, we have
$$
\pi_1(G)/J'_{\Cr}=\pi_1(G_{ss})/J_{\Cr}
$$
since $\pi_1(G_{ss})=\pi_1(G)=\Z/2\Z$ and $2\pi_1(G)$ is trivial, so
the answer is the same as in the orientable case.

Our proofs of the above results rely on a result of Alekseev, Malkin, and Meinrenken
on group-valued moment maps (Fact \ref{thm:fiber}).

The rest of this paper is organized as follows. In Section \ref{sec:pre}, we give some
preliminaries on the structure of compact Lie groups and introduce some
definitions. In Section \ref{sec:special}, we derive
Theorem \ref{thm:irzero}--\ref{thm:nonzero} under the additional assumption that $G$
is simply connected. The general case is treated in Section
\ref{sec:general}: the results for orientable surfaces (Theorem
\ref{thm:irzero} and Theorem \ref{thm:izero}) are proved in Section
\ref{sec:orientable}, and the results for nonorientable surfaces (Theorem
\ref{thm:rzero} and Theorem \ref{thm:nonzero}) are proved in Section \ref{sec:nonorientable}.
In Section \ref{sec:moduli}, we give a geometric interpretation of
the above results to the moduli spaces of flat bundles over compact surfaces.

\section{Preliminaries}\label{sec:pre}

\subsection{Compact connected Lie groups}\label{sec:compact}
Let $G$ be a compact connected Lie group. Let $G_{ss}=[G,G]$ be its
commutator group. Then $G_{ss}$ is the maximal connected semisimple
subgroup of $G$. Let $H$ be the connected component of the identity
of the center $Z(G)$ of $G$. Then $H$ is a compact torus.
The map $\phi: H\times G_{ss}\to G=HG_{ss}$
given by $(h,g)\mapsto hg$ is a finite cover which is also a group
homomorphism. The kernel of $\phi$ is isomorphic to $D=H\cap G_{ss}\subset Z(G_{ss})$,
which is a finite abelian group. Note that $G_{ss}$ is a normal subgroup
of $G$, and the quotient
$$
G/G_{ss}\cong H/D
$$
is a compact torus.

Let $\rho_{ss}:\tG_{ss}\to G_{ss}$ be the
universal covering map which is also a group homomorphism. Then $\tG_{ss}$ is
a compact, connected, simply connected Lie group, and
$\Ker(\rho_{ss})$ is a subgroup of $Z(\tG_{ss})$.

Let $\fg$ and $\fh$ be the Lie algebras of $G$ and $H$ respectively,
and let $\exp_H:\fh\to H$ be the exponential map. The map
$$
\rho: \tG=\fh\times \tG_{ss} \to G
$$
given by
$$
(X,g)\to \exp_H(X)\rho_{ss}(g)
$$
is the universal covering map which is also a group homomorphism.
Here we give a group structure for $\fh$ the addition operation in
the vector space $\fh$ and $0$ as the identity element for the
group structure. Notice that $\tG$ is not compact.
 Let $\pi_1: H\to H/D$ and $\pi_2: G_{ss}\to G_{ss}/D$ be
natural projections. Then
$$
\pi_1\circ \exp_H :\fh\to H/D\cong G/G_{ss}
$$
is the universal covering map which is also a group homomorphism, and
$$
\check{\Lambda}=\Ker(\pi_1\circ\exp_H)\cong \pi_1(G/G_{ss})\cong \Z^{\dim H}.
$$
We have
\begin{eqnarray*}
\Ker(\rho) &=& \{ (X,g)\in \fh\times \tG_{ss}\mid \exp_H(X)\rho_{ss}(g)=e\}\\
&& \subset \check{\Lambda} \times \Ker(\pi_2\circ\rho_{ss})\subset
\check{\Lambda}\times Z(\tG_{ss}) \subset \fh\times Z(\tG_{ss})=Z(\tG).
\end{eqnarray*}

The map $(X,g)\mapsto X$ defines a surjective group homomorphism
$p:\Ker(\rho)\to \check{\Lambda}$. The kernel of $p$ is
$\{0\}\times \Ker(\rho_{ss})\cong \Ker(\rho_{ss})$. So
we have an exact  sequence of abelian groups
\begin{equation}\label{eqn:kernel}
1\to \Ker(\rho_{ss})\to \Ker(\rho)\to \check{\Lambda}\to 1,
\end{equation}
which can be rewritten as
\begin{equation}
1\to \pi_1(G_{ss})\to \pi_1(G)\to \pi_1(G/G_{ss})\to 1.
\end{equation}
where $\pi_1(G_{ss})$ is a finite abelian group, and
$$
\pi_1(G/G_{ss})=\pi_1(H/D)\cong \Z^{\dim H}.
$$

\subsection{Conjugacy classes}\label{sec:conjugate}
Let $G$ be a connected Lie group with center $Z(G)$.
Given $a\in G$, let $G\cdot a$ denote the orbit of $a$ of the
conjugate action of $G$ on itself. The left multiplication
by $z\in Z(G)$ gives a bijection $G\cdot a \to G\cdot (za)$.
Given a conjugacy class $\cC=G\cdot a$ and $z\in Z(G)$, let
$z\cC$ denote the conjugacy class $G\cdot (za)$.

Let $K$ be a subgroup of $Z(G)$. Let $K$ acts on $G$ by left multiplication.
This $K$-action on $G$ commutes with the conjugate action of $G$ and induces
a $K$-action on $Con(G)$, the set of conjugacy classes of $G$.
Given a conjugacy $\cC\in Con(G)$, let $K_{\cC}$ denote the stabilizer
of $\cC$ under the $K$-action on $Con(G)$. It is straightforward to check that
$K_{\cC}=K_{z\cC}$ for any $\cC\in Con(G)$ and $z\in Z(G)$.

Now let $G$ be a compact connected Lie group, and let
$\rho:\tG\to G$ be as in Section \ref{sec:compact}.
Then $\tG$ is a noncompact connected Lie group.
The following is obviously true.
\begin{lm}\label{thm:ss}
Let $K=\Ker\rho\subset Z(\tG)=\fh\times Z(\tG_{ss})$, and let
$\tilde{K}=\Ker(\rho_{ss})\subset Z(\tG_{ss})$. Then any
conjucay class $\cD\in Con(\tG)$ is of the form
$$
\cD=\{X\}\times \tilde{\cC}
$$
for some $X\in \fh$ and $\tilde{\cC}\in Con(\tG_{ss})$, and we have
$$
K_\cD= \{0\}\times \tilde{K}_{\tilde{\cC}}
\subset \{0\}\times \Ker(\rho_{ss}).
$$
\end{lm}

Given a conjugacy class $\cC$ in $G$, each connected
component of $\rho^{-1}(\cC)$ is a conjugacy class of $\tG$. Let
$\cD$ be a connected component of $\rho^{-1}(\cC)$. Then
$\cD\to \cC$ is a covering map of finite degree. Actually,
the degree of $\cD\to \cC$ is equal to the cardinality of
the subgroup $K_\cD$ of $\{0\}\times \Ker(\rho_{ss})\cong \pi_1(G_{ss})$.
Let
$$
J_{\Cr}\subset \{0\}\times \Ker(\rho_{ss})\cong \pi_1(G_{ss})
$$
be the subgroup generated by $K_{\cD_1}, \ldots, K_{\cD_r}$, where
$\cD_j$ is a connected component of $\rho^{-1}(\cC_j)$. Note that
the definition of $J_{\Cr}$ does not depend on the choices of $\cD_1,\ldots,\cD_r$
because any connected component of $\rho^{-1}(\cC_j)$ is of the
form $z\cD_j$ for some $z\in Z(\tG)$ and $K_{z\cD_j}= K_{\cD_j}$.

\begin{ex}\label{ex:so}
$G=SO(3)=G_{ss}$, $\tG=Spin(3)=\tG_{ss}$ ,and $\rho_{ss}=\rho:\tG\ra G$.
We view $Spin(3)$ as a subset of the real Clifford algebra $C_3$.
Choose a maximal torus $T$ of $SO(3)$ as follows:
$$
T=\{
R_\theta=\left(\begin{array}{ccc}
 \cos\theta & -\sin\theta & 0\\
\sin\theta & \cos\theta & 0\\
 0 & 0 & 1
\end{array}\right)\mid  -\pi\leq \theta \leq \pi \}\cong U(1)
$$
Then
$$
\tT=\rho^{-1}(T)=\{\eta_\phi=\cos\phi-\sin\phi e_1 e_2\mid -\pi\leq
\phi\leq \pi\} \cong U(1)
$$
is a maximal torus of $Spin(3)$. We have $\rho(\eta_\phi)=R_{2\phi}$,
so $\rho|_{\tT}:\tT\to T$ can be identified with
$$
s:U(1)\to U(1),\ \ u\mapsto u^2.
$$

Let $W=\{\pm 1\}$ be the Weyl group of $SO(3)$ which is also the Weyl
group of $Spin(3)$. Then $W$ acts on $SO(3)$ and $Spin(3)$ by
$(-1)\cdot R_\theta = R_{-\theta}$ and $(-1)\cdot \eta_\phi=\eta_{-\phi}$,
respectively. Let $\cC_\theta \in Con(SO(3))$ be the conjugacy
class represented by $R_\theta \in T\subset SO(3)$, and let
$\cD_\phi \in Con(Spin(3))$ be the conjugacy class represented
by $\eta_\phi \in\tT\subset Spin(3)$. Then
\begin{eqnarray*}
Con(SO(3))=T/W
&=&\{\cC_\theta \mid 0\leq \theta \leq \pi\}\cong [0,\pi]\\
Con(Spin(3))=\tT/W
&=&\{\cD_\phi\mid 0\leq \theta \leq \pi \}\cong [0,\pi]
\end{eqnarray*}
$\rho|_{\tT}:\tT\to T$ induces a map $\hat{\rho}: \tT/W \to T/W$ which
can be identified with
$$
\hat{s}:[0,\pi]\to [0,\pi],\ \
\phi \mapsto\left\{ \begin{array}{ll}
2\phi & 0\leq \phi \leq \frac{\pi}{2}\\
2(\pi-\phi)& \frac{\pi}{2} \leq \phi \leq \pi.
\end{array}\right.
$$
So for $\theta \in [0,\pi]$, we have
$\hat{\rho}^{-1}(\cC_\theta)=\{\cD_{\frac{\theta}{2}},
\cD_{\pi-\frac{\theta}{2}}\}$. Note that $\hat{\rho}^{-1}(\cC_\theta)$
consists of two conjugacy classes unless $\cC_\theta=\cC_\pi$, which
is represented by
$$
R_\pi=\left(\begin{array}{ccc}
-1 & 0 & 0\\
0 & -1 & 0\\
0 & 0 & 1
\end{array}
\right).
$$
In this case, $\hat{\rho}^{-1}(\cC_\pi)$ consists of a single
conjugacy class $\cD_{\frac{\pi}{2}}$.
So for $\theta \in [0,\pi], \theta\neq \pi$,
$\rho^{-1}(\cC_\theta)=\cD_{\frac{\theta}{2}}\cup
\cD_{\pi-\frac{\theta}{2}} \to \cC_\theta$ is the trivial
(disconnected) double cover, while
$\rho^{-1}(\cC_{\pi})=\cD_{\frac{\pi}{2}}\to \cC_\pi$ is
a connected nontrivial double cover.

Let $K=\{\pm 1\}=\Ker(\rho_{ss})=\Ker(\rho)$. Then $K$ acts on
$\tT$ by $(-1)\cdot \eta_\phi = -\eta_\phi = \eta_{\phi-\pi}$.
So $K$ acts on $Con(Spin(3))$ by $(-1)\cdot \cD_\phi =
\cD_{\phi-\pi} = \cD_{\pi-\phi}$, i.e.,
$(-1)\cdot \phi =\pi-\phi$ under the identification
$Con(Spin(n))\cong [0,\pi]$. It is clear from the
the above explicit description that for $\phi\in[0,\pi]$,
$$
K_{D_\phi}=\left\{\begin{array}{ll}
\{    1\},& \textup{ if  }\phi \neq\frac{\pi}{2},\\
\{\pm 1\},& \textup{ if  }\phi =\frac{\pi}{2}.
\end{array}\right.
$$
Then for
$\Cr\in Con(SO(3))$,
$$
J_{\Cr}
=\left\{\begin{array}{ll}
\{    1\},& \textup{ if none of }\Cr\textup{ is equal to }\cC_{\pi},\\
\{\pm 1\},& \textup{ if one of  }\Cr\textup{ is equal to }\cC_{\pi}.
\end{array}\right.
$$

\end{ex}

The analysis in Example \ref{ex:so} can be generalized to show that
$J_{\Cr}$ is trivial for generic conjugacy classes
$\Cr\in Con(SO(n))$, $n\geq 3$.

\subsection{Representation varieties}
\label{sec:variety}

\begin{df}\label{def:variety}
Let $G$ be a connected Lie group.
Given nonnegative integers $\ell, r$ such that $(\ell,r)\neq(0,0)$ and conjugacy
classes $\Cr\in Con(G)$, define
\begin{eqnarray*}
\Phi_{G,\ell,r}^{\Cr}: && G^{2\ell}\times\Ct \longrightarrow G\\
&&(a_1,b_1,\ldots,a_\ell,b_\ell,d_1,\ldots,d_r)
\mapsto \prod_{i=1}^\ell [a_i,b_i]\prod_{j=1}^r d_j.
\end{eqnarray*}
Let $\Phi_{G,0,0}:\{e\}\to G$ be the inclusion of the trivial subgroup.

Given nonnegative integers $\ell,r$, conjugacy classes $\Cr\in Con(G)$,
and $z\in Z(G)$, define
\begin{eqnarray*}
&&\Xz= \left(\Phi_{G,\ell,r}^{\Cr}\right)^{-1}(z)\\
& & \Xo\\
&=&\{ (a_1,b_1,\ldots,a_\ell,b_\ell,d_1,\ldots,d_r,c)
      \in G^{2\ell}\times\Ct\times G \mid
      \prod_{i=1}^\ell[a_i,b_i] \prod_{j=1}^r d_j c^2 =z\}\\
& & \Xt\\
&=&\{ (a_1,b_1,\ldots,a_\ell,b_\ell,d_1,\ldots,d_r,c_1,c_2)
      \in G^{2\ell}\times\Ct\times G^2 \mid
      \prod_{i=1}^\ell[a_i,b_i] \prod_{j=1}^r d_j c_1^2 c_2^2 =z\}
\end{eqnarray*}
\end{df}

Since $G$ is a Lie group and any conjugacy class of $G$ is a homogeneous
space, for any nonnegative integers $\ell,r$ and $i=1,2,3$
$$
G^{2\ell}\times \Ct \times G^i
$$
is a manifold (it is a point when $\ell=r=i=0$). In this topology,
$X^{\ell,r,i}_G(\Cr;z)$ is a closed subset.
Let $X^{\ell,r,i}_G(\Cr;z)$ be equipped with the induced topology
as a closed subset of $X^{\ell,r,i}_G(\Cr;z)$.

Let $\slr$ be the compact, connected, orientable surface with $\ell$ handles and $r$
boundary components $B_1,\ldots, B_r$, where $\ell, r$ are nonnegative integers.
Let $\sone$ be the connected sum of $\slr$ and $\RP^2$, and let
$\stwo$ be the connected sum of $\slr$ and a Klein bottle.
Any compact surface is of the form $\lri$, where $\ell,r$ are nonnegative
integers and $i=0,1,2$. It is orientable iff $i=0$; it is closed iff $r=0$.
Then $\Hom_{\Cr}(\pi_1(\lri),G)$ can be identified with $X^{\ell,r,i}_G(\Cr;e)$.

\section{Simply connected case} \label{sec:special}

In this section, we consider a compact, connected, simply connected Lie group
$G$. In particular, $G$ is semisimple.

\begin{fact}[{\cite{dhm}}]\label{thm:fiber}
Let $G$ be a compact, connected, simply connected Lie group.
Let $\ell$ be a positive integer, and let $\Cr$ be any conjugacy
classes in $G$. Then for any $g\in G$, $(\Phi_{G,\ell,r}^{\Cr})^{-1}(g)$
is nonempty and connected.
\end{fact}

\begin{rem}
The reason of Fact \ref{thm:fiber} is that $\{ G^{2\ell}\times\Ct, \Phi_{G,\ell,r}^{\Cr}\}$
is a quasi-Hamiltonian system and thus the preimage of the
moment map $\Phi_{G,\ell,r}^{\Cr}$ is nonempty and connected under the above assumption of $G$.
\end{rem}

We will derive the following result from Fact \ref{thm:fiber}.
\begin{pro}\label{thm:connected}
Let $G$ be a compact, connected, simply connected Lie group.
Let $\ell$ be a positive integer, let $r$ be a nonnegative integer,
let $\cC_1,\ldots,\cC_r$ be any conjugacy classes in $G$, and let
$z\in Z(G)$.  Then
$$
\Xz,\ \ \Xo
$$
are nonempty and connected;
$$
\Xt
$$
is nonempty, and is connected if $\ell>1$.
\end{pro}

\paragraph{\bf Proof}
By Fact \ref{thm:fiber},
$$
\Xz=\left(\Phi_{G,\ell,r}^{\Cr}\right)^{-1}(z).
$$
is nonempty and connected. In the rest of the proof,
we will consider $\Xo$ and $\Xt$.

We fix a maximal torus $T$ in $G$.
For $r=0$, let $s\in T$ be a square root of $z$. For $r>0$,
$T\cap \cC_j$ is nonempty for
$j=1,\ldots,r$. We fix $t_j\in T\cap \cC_j$, and let
$s\in T$ be a square root of $(t_1\cdots t_r)^{-1}z$.

Consider maps
\begin{eqnarray*}
Q_1:X_G^{\ell,r,1}(\Cr;z) &\to& G\\
(a_1,b_1,\ldots,a_\ell,b_\ell,d_1,\ldots,d_r, c)&\mapsto& c\\
Q_2:X_G^{\ell,r,2}(\Cr;z) &\to& G^2\\
(a_1,b_1,\ldots,a_\ell,b_\ell,d_1,\ldots,d_r, c_1,c_2)&\mapsto& (c_1,c_2)
\end{eqnarray*}
By Fact \ref{thm:fiber}, $Q_1^{-1}(c)$ is nonempty and connected for any $c\in
G$, and $Q_2^{-1}(c_1,c_2)$ is nonempty and connected for any $(c_1,c_2)\in G^2$.
So  $X_G^{\ell,r,1}(\Cr;z)$ and $X_G^{\ell,r,2}(\Cr;z)$ are  nonempty. We
will show that
\begin{enumerate}
\item For any $c_0\in G$ there is a path
      $\gamma_1:[0,1]\to X_G^{\ell,r,1}(\Cr;z)$  such that
      $\gamma_1(0)\in Q^{-1}_1(s)$ and $\gamma_1(1)\in Q^{-1}_1(c_0)$.
\item If $\ell>1$, then for any $(c_1,c_2)\in G^2$ there is a path
      $\gamma_2:[0,1]\to X_G^{\ell,r,2}(\Cr;z)$  such that
      $\gamma_2(0)\in Q_2^{-1}(s,e)$ and $\gamma_2(1)\in Q_2^{-1}(c_1,c_2)$.
\end{enumerate}
This will complete the proof.

Given $c_0, c_1, c_2\in G$,  there exist $g_0,g_1,g_2\in G$ such that
$g_i^{-1} c_i g_i\in T$. Let $\fg$ and $\ft$ be the Lie algebras of $G$ and $T$,
respectively. Let $\exp:\fg\to G$ be the exponential map.
Then there exist $\xi_0,\xi_1,\xi_2\in\ft$ such that
$$
s^{-1}g_0^{-1} c_0 g_0=\exp (\xi_0),\ \
s^{-1}g_1^{-1} c_1 g_1=\exp (\xi_1),\ \
g_2^{-1} c_2 g_2=\exp (\xi_2).
$$
Let $W$ be the Weyl group of $G$, and let $w\in W$ be a Coxeter element (cf:\cite{Hu}).
The linear map $w:\ft\to \ft$ has no eigenvalue equal to $1$,
so there exists $\xi_i'\in\ft$ such that $w\cdot \xi_i'-\xi_i'=\xi_i$.
Recall that $W=N(T)/T$, where $N(T)$ is the normalizer of $T$ in $G$,
so $w=aT\in N(T)/T$ for some $a\in G$. We have
$$
a\exp(t\xi_i')a^{-1} \exp(-t\xi_i')=\exp(t\xi_i)
$$
for any $t\in \R$.

The group $G$ is connected, so there exists a path $\tg_i:[0,1]\to G$ such that
$\tg_i(0)=e$ and $\tg_i(1)=g_i$, where $i=0,1,2$. Define $\gamma_1:[0,1]\longrightarrow
G^{2\ell}\times \Ct \times G$ by
$$
\gamma_1(t)=(a(t), b(t), e,\ldots,e, d_1(t),\ldots,d_r(t), c(t)),
$$
where
\begin{eqnarray*}
a(t)&=&\tg_0(t) a \tg_0(t)^{-1}, \\
b(t)&=&\tg_0(t)\exp(-2t\xi_0')\tg_0(t)^{-1}, \\
d_j(t)&=& \tg_0(t) t_j \tg_0(t)^{-1},\ \ j=1,\ldots,r\\
c(t)&=& \tg_0(t) s \exp(t\xi_0)\tg_0(t)^{-1}.
\end{eqnarray*}
Then the image of $\gamma_1$ lies in $X_G^{\ell,r,1}(\Cr;z)$,
$$
\gamma_1(0)=(a,e,e,\ldots,e,t_1,\ldots,t_r,s)\in Q_1^{-1}(s),
$$
and
\begin{eqnarray*}
\gamma_1(1)&=&(g_0ag_0^{-1}, g_0\exp(-2\xi_0')g_0^{-1}, e,\ldots,e,
 g_0 t_1g_0^{-1},\ldots, g_0 t_r g_0^{-1},\\
&& g_0s\exp(\xi_0) g_0^{-1}=c)\in Q_1^{-1}(c_0).
\end{eqnarray*}

For $\ell>1$, define $\gamma_2:[0,1]\longrightarrow
G^{2\ell}\times \Ct \times G^2$ by
$$
\gamma_2(t)=(a_1(t), b_1(t),a_2(t),b_2(t), e,\ldots,e, d'_1(t),\ldots,d'_r(t), c_1(t),c_2(t)),
$$
where
\begin{eqnarray*}
a_1(t)&=&\tg_2(t) a \tg_2(t)^{-1}, \\
b_1(t)&=&\tg_2(t)\exp(-2t\xi_2')\tg_2(t)^{-1}, \\
a_2(t)&=&\tg_1(t) a \tg_1(t)^{-1}, \\
b_2(t)&=&\tg_1(t)\exp(-2t\xi_1')\tg_1(t)^{-1}, \\
d'_j(t)&=&\tg_1(t)t_j\tg_1(t)^{-1},\ \ j=1,\ldots,r,\\
c_1(t)&=& \tg_1(t)s\exp(t\xi_1)\tg_1(t)^{-1},\\
c_2(t)&=& \tg_2(t)\exp(t\xi_2)\tg_2(t)^{-1}.
\end{eqnarray*}
Then the image of $\gamma_2$ lies in $X_G^{\ell,r,2}(\Cr;z)$,
$$
\gamma_2(0)=(a,e,a,e,e,\ldots,e,t_1,\ldots,t_r,s,e)\in Q^{-1}(s,e),
$$
and
\begin{eqnarray*}
\gamma_2(1)&=&(g_2ag_2^{-1}, g_2\exp(-2\xi_2')g_2^{-1},
           g_1 a g_1^{-1}, g_1\exp(-2\xi_1') g_1^{-1},
       e,\ldots,e,\\
 & & g_1 t_1 g_1^{-1},\ldots,g_1t_rg_1^{-1}, c_1,c_2)\in Q^{-1}(c_1,c_2).\ \ \Box
\end{eqnarray*}

\bigskip

Recall that
$$
\Hom_{\Cr}(\pi_1(\lri),G)\cong X_G^{\ell,r,i}(\Cr;e)
$$
for $i=0,1,2$. So Proposition \ref{thm:connected} implies
that Theorem \ref{thm:irzero}--\ref{thm:nonzero}
hold when $G$ is simply connected:
\begin{cor}\label{thm:simply}
Let $G$ be a compact, connected, simply connected Lie group.
Let $\ell$ be a positive integer, let $r$ be a nonnegative integer,
let $\cC_1,\ldots,\cC_r$ be any conjugacy classes in $G$, and let
$z\in Z(G)$.  Then
$$
\Hom_{\Cr}(\pi_1(\slr),G)/G,\ \
\Hom_{\Cr}(\pi_1(\sone),G)/G
$$
are nonempty and connected;
$$
\Hom_{\Cr}(\pi_1(\stwo),G)/G,
$$
is nonempty, and is connected if $\ell>1$.
\end{cor}

\section{General case}\label{sec:general}

\subsection{Orientable surfaces}\label{sec:orientable}

Let $G, G_{ss}, H, D$ be as in Section \ref{sec:compact}, and
let $\pi:G\to G/G_{ss}=H/D$ be the projection. Then
$\pi$ descends to a map $\hat{\pi}: Con(G) \to H/D$. Let
$\pi_1:H\to H/D$ be the natural projection. We have the
following observation.
\begin{lm}\label{thm:image}
Let $G$ be a compact connected Lie group. Let $\ell$ be a positive integer.
Then
$$
\im(\Phi_{G,\ell,0})=G_{ss}.
$$
For $r>0$, we have
$$
\im(\Phi^{\Cr}_{G,\ell,r})= hG_{ss}
$$
where $h\in H$, $\pi_1(h)=\hat{\pi}(\cC_1)\cdots \hat{\pi}(\cC_r)\in H/D$.
\end{lm}

\paragraph{\bf Proof}
It is obvious from the definition that $\im\left(\Phi_{G,\ell,0}\right)\subset G_{ss}$.
Conversely, given $g\in G_{ss}$, let $\tg\in \tG_{ss}$ be a preimage of $g$
under $\rho_{ss}:\tG_{ss}\to G_{ss}$. By Fact \ref{thm:fiber}, there exist
$\ta,\tb\in \tG_{ss}$ such that $[\ta,\tb]=\tg$. Let $a=\rho_{ss}(\ta)$ and
$b=\rho_{ss}(\tb)$. Then
$$
g=[a,b]=\Phi_{G,\ell,0}(a,b,e,\ldots,e)\in \im\left(\Phi_{G,\ell,0}\right).
$$
So $G_{ss}\subset \im(\Phi_{G,\ell,0})$.

It follows from the above $r=0$ case that  $\im(\Phi^{\Cr}_{G,\ell,r})=G_{ss}$
if $\cC_j\subset G_{ss}$ for $j=1,\ldots, r$. In general, $\cC_j=G\cdot g_j$
for some $g_j\in G$, and $g_j=h_j g_j'$ for some $h_j\in H$ and $g_j'\in
G_{ss}$. We have $\cC_j= h_j\cC_j'$, where
$\cC_j'= G\cdot g_j'=G_{ss}\cdot g_j'\subset G_{ss}$, and
$\pi_1(h_j)=\hat{\pi}(\cC_j)$. So
\begin{equation}\label{eqn:CinGss}
\im(\Phi_{G,\ell,r}^{\cC_1',\ldots,\cC_r'})=G_{ss}.
\end{equation}
From the definition of $\Phi_{G,\ell,r}^{\cC_1,\ldots,\cC_r}$, one
sees that (\ref{eqn:CinGss}) implies
$$
\im(\Phi_{G,\ell,r}^{h_1\cC_1',\ldots,h_r\cC_r'})=h_1\cdots h_rG_{ss},
$$
or equivalently,
$$
\im(\Phi_{G,\ell,r}^{\Cr})=h G_{ss},
$$
where $h=h_1\cdots h_r\in H$ and $\pi_1(h_1\cdots
h_r)=\hat{\pi}(\cC_1)\cdots\hat{\pi}(\cC_r)$. $\ \ \Box$.

Let $\Cr$ be conjugacy classes of $G$. From the proof of
Lemma \ref{thm:image}, $\cC_j=h_j\cC_j'$ for some $h_j\in H$
and some conjugacy class $\cC_j'\subset G_{ss}$.
Recall that
$$
\Hom_{\Cr}(\pi_1(\Si^{\ell,r}_0),G)\cong X^{\ell,r,0}_G(\Cr;e)
=\left(\Phi^{\Cr}_{G,\ell,r}\right)^{-1}(e).
$$
By Lemma \ref{thm:image},
$\left(\Phi^{\Cr}_{G,\ell,r}\right)^{-1}(e)$ is nonempty iff $h_1\cdots
h_r\in D$. Note that if $d_1\cdots d_r\in G_{ss}$ for some
$(d_1,\ldots,d_r)\in \Ct$, then $h_1\cdots h_r\in D$ and
$d_1\cdots d_r\in G_{ss}$ for {\em all} $(d_1,\ldots,d_r)\in\Ct$.
So we have
\begin{lm}\label{thm:empty}
Let $G$ be a compact connected Lie group, and let
$\ell,r$ be positive integers. Then
$\Hom_{\Cr}(\pi_1(\Si^{\ell,r}_0,G))/G$ is nonempty iff
$d_1\cdots d_r\in G_{ss}$ for some (and therefore for all)
$(d_1,\dots,d_r)\in \Ct$.
\end{lm}

Let $\Cr$ be conjugacy classes in $G$ such that $d_1\cdots d_r\in G_{ss}$
for some $(d_1,\ldots,d_r)\in \Ct$.
From the above discussion, $\cC_j=h_j\cC_j'$ for some $h_j\in H$,
$\cC_j\subset G_{ss}$, and  $h=h_1\cdots h_r\in D$. Note that we
may replace $h_1$ and $\cC'_1$ by $h^{-1}h_1\in H$ and
$h\cC'_1\subset G_{ss}$, respectively, so we may assume that
$h_1\cdots h_r =e$. The diffeomorphism
$$
G^{\ell}\times\cC_1'\times\cdots\times\cC_r'
\longrightarrow G^{\ell}\times \Ct
$$
given by
$$
(\ab,d_1,\ldots,d_r)\mapsto (\ab, h_1d_1,\ldots,h_rd_r)
$$
induces an isomorphism of topological spaces
$$
X^{\ell,r,0}_G(\cC_1',\ldots,\cC'_r;e)\longrightarrow
X^{\ell,r,0}_G(\Cr;e).
$$
So
$$
\Hom_{\cC_1',\cdots,\cC_r'}(\pi_1(\Si^{\ell,r}_0),G)/G
\cong \Hom_{\Cr}(\pi_1(\Si^{\ell,r}_0),G)/G.
$$

From the above discussion, Theorem \ref{thm:izero} follows from Lemma \ref{thm:empty}
and Theorem \ref{thm:orientable}.
\begin{thm}\label{thm:orientable}
Let $G$ be a compact connected Lie group, and let $G_{ss}=[G,G]$ be the
maximal connected semisimple subgroup of $G$. Let $\ell, r$ be positive
integers, and let $\Cr$ be conjugacy classes of $G$ such that
$\cC_j\subset G_{ss}$ for $j=1,\ldots,r$. Then there is a bijection
$$
\pi_0(\Hom_{\Cr}(\pi_1(\Si^{\ell,r}_0),G))\longrightarrow \pi_1(G_{ss})/J_{\Cr}
$$
where $J_{\Cr}$ is defined as in Section \ref{sec:conjugate}.
\end{thm}
\paragraph{\bf Proof}
Let $\rho:\tG\to G$ and $\rho_{ss}:\tG_{ss}\to G_{ss}$ be  universal
coverings, as before. Let $\cD_j$ be a connected component of $\rho^{-1}(\cC_j)$.
Recall from Section \ref{sec:conjugate} that
$\cD_j$ is a conjugacy class of $\tG=\fh\times\tG_{ss}$, and
$\rho_j:\cD_j \to \cC_j$ is a finite cover of degree $|K_{\cD_j}|$,
where $K_{\cD_j}$ is a subgroup of
$\{0\}\times \Ker(\rho_{ss})\cong \pi_1(G_{ss})$.
$J_{\Cr}$ is the subgroup of $\{0\}\times \Ker(\rho_{ss})$ generated by $K_{\cD_1},\cdots, K_{\cD_r}$.
In the rest of this proof,  we will identify $\Ker(\rho_{ss})$ with $\{0\}\times \Ker(\rho_{ss})$.
Let
$$
P=\rho^{2\ell}\times \rho_1\times\cdots\times \rho_r:\tG^{2\ell}\times
\cD_1\times\cdots\times\cD_r
\to G^{2\ell}\times\Ct.
$$

Define
$$
o:\Hom_{\Cr}(\pi_1(\Si^{\ell,r}_0),G)\cong  X^{\ell,r,0}_G(\Cr;e)\to \Ker(\rho_{ss})/J_{\Cr}
$$
by
\begin{equation}\label{eqn:zero-o}
(a_1,b_1,\ldots,a_\ell,b_\ell,d_1,\ldots,d_r) \mapsto
\left[\prod_{i=1}^\ell [\ta_i,\tb_i]\prod_{j=1}^r \td_j \right]
\end{equation}
where
$$
(\ta_1,\tb_1,\ldots, \ta_\ell,\tb_\ell,
\td_1,\ldots,\td_r)\in P^{-1}(a_1,b_1,\ldots,a_\ell,b_\ell,d_1,\ldots,d_r),
$$
and $[k]$ denotes the image of $k\in \Ker(\rho_{ss})$ under the natural
projection $\Ker(\rho_{ss})\to \Ker(\rho_{ss})/J_{\Cr}$.
Note that the definition (\ref{eqn:zero-o}) does not depend on
the choice of $(\ta_1,\tb_1,\ldots,\ta_\ell, \tb_\ell,\td_1,\ldots,\td_r)$
because $\Ker\rho\subset Z(\tG)$ and
$$
\rho_j^{-1}(d_j)=\{ k\td_j\mid k\in K_{\cD_j}\}.
$$
The map $o$ descends to a continuous map
$$
\bar{o}:\Hom_{\Cr}(\pi_1(\Si^{\ell,r}_0),G)/G
\to\Ker(\rho_{ss})/J_{\Cr}.
$$

It is easy to check that $P$ restricts to a surjective map
$$
X_{\tG}^{\ell,r,0}(\cD_1,\ldots,\cD_r;k)
\cong \fh^{2\ell}\times X_{\tG_{ss}}^{\ell,r,0}(\cD_1,\ldots,\cD_r;k)
\longrightarrow o^{-1}([k])
$$
for any $k\in \Ker(\rho_{ss})$. By Fact \ref{thm:fiber},
$X_{\tG_{ss}}^{\ell,r,0}(\cD_1,\ldots,\cD_r;k)$
is nonempty and connected for any $k\in \Ker(\rho_{ss})$.
So $o^{-1}([k])$ and $\bar{o}^{-1}([k])$ are nonempty and connected
for each $[k]\in K/J_{\Cr}$. This completes the proof. $\ \ \Box$.

\bigskip

Finally, Theorem \ref{thm:irzero} follows immediately from Theorem
\ref{thm:orientable} because $\Hom(\pi_1(\Si^{\ell,0}_0),G)/G$ can
be identified with $\Hom_{\{e\}}(\pi_1(\Si^{\ell,1}_0),G)/G$ and
$J_{\{e\}}$ is trivial.

\subsection{Nonorientable surfaces}\label{sec:nonorientable}
Let $G, G_{ss}, H,D$ be defined as in Section \ref{sec:compact}, and
let $\Cr$ be $r>0$ conjugacy classes of $G$. We have seen in Section
\ref{sec:orientable} that $\cC_j=h_j\cC_j'$ for some $h_j\in H$ and
some conjugacy class $\cC_j'\subset G_{ss}$.
Let $s\in H$ be a square root of $h_1\cdots h_r$.
The diffeomorphism
\begin{eqnarray*}
 G^{2\ell}\times \Ct\times G &\longrightarrow
& G^{2\ell}\times \cC'_1\times\cdots\times\cC'_r\times G\\
(a_1,b_1,\ldots,a_\ell,b_\ell,d_1,\ldots,d_r,c) &\mapsto&
(a_1,b_1,\ldots,a_\ell,b_\ell,h_1^{-1} d_1,\ldots, h_r^{-1} d_r,sc)
\end{eqnarray*}
induces a homeomorphism of (topological) subspaces
$$
X_G^{\ell,r,1}(\Cr;e)\to X_G^{\ell,r,1}(\cC_1',\ldots,\cC_r';e).
$$
Similarly,
the diffeomorphism
\begin{eqnarray*}
 G^{2\ell}\times \Ct\times G^2
&\longrightarrow& G^{2\ell}\times \cC_1'\times\ldots\times\cC_r' \times G^2\\
(a_1,b_1,\ldots,a_\ell,b_\ell,d_1,\ldots,d_r,c_1,c_2) &\mapsto&
(a_1,b_1,\ldots,a_\ell,b_\ell,h_1^{-1} d_1,\ldots, h_r^{-1} d_r,c_1,sc_2)
\end{eqnarray*}
induces a homeomorphism
$$
X_G^{\ell,r,2}(\Cr;e)\to X_G^{\ell,r,2}(\cC'_1,\ldots,\cC'_r;e).
$$
So we have
$$
\Hom_{\Cr}(\pi_1(\Si^{\ell,r}_i),G)\cong
\Hom_{\cC_1',\cdots,\cC_r'}(\pi_1(\Si^{\ell,r}_i),G)
$$
for $\ell,r>0$ and $i=1,2$. Therefore, Theorem \ref{thm:nonzero}
follows from Theorem \ref{thm:nonorientable}.
\begin{thm}\label{thm:nonorientable}
Let $\rho:\tG\to G$ and $K=\Ker\rho\cong \pi_1(G)$ be defined as in Section \ref{sec:compact}.
Let $r$ be a positive integer, and let $\cC_1,\ldots,\cC_r$ be conjugacy
classes of $G$ such that $\cC_j\subset G_{ss}$ for $j=1,\ldots,r$.
Then for $\ell\geq i$, where $i=1,2$, there is a bijection
$$
\pi_0(\Hom_{\Cr}(\pi_1(\Si^{\ell,r}_i),G))\cong K/J'_{\Cr}
$$
where $J'_{\Cr}$ is the subgroup of $K$ generated by $J_{\Cr}$ and $2K=\{k^2\mid k\in K\}$.
\end{thm}

\begin{rem}
Notice that there is no condition on the conjugacy class for the moduli space to be nonempty.
\end{rem}

\paragraph{\bf Proof}
Let $\cD_j$ be a connected component of $\cC_j$. Since $\cC_j\subset G_{ss}$,
we may choose $\cD_j$ such that $\cD_j\subset \{0\}\times \tG_{ss}\subset \fh\times\tG_{ss}=\tG$.
Recall that $\rho_j:\cD_j\to \cC_j$ is a finite cover with degree $|K_{\cD_j}|$, and
$J_{\Cr}$ is the subgroup of $K$ generated by $K_{\cD_1},\cdots,K_{\cD_r}$.
Set
\begin{eqnarray*}
&P_1=\rho^{2\ell}\times \rho_1\times\cdots\rho_r\times \rho:&\tG^{2\ell}\times
\cD_1\times\cdots\times\cD_r\times \tG
\to G^{2\ell}\times\Ct\times G\\
&P_2=\rho^{2\ell}\times \rho_1\times\cdots\rho_r\times \rho^2:&\tG^{2\ell}\times
\cD_1\times\cdots\times\cD_r\times \tG^2
\to G^{2\ell}\times\Ct\times G^2
\end{eqnarray*}
For $i=1,2$ we define
$$
o:X^{\ell,r,i}_G(\Cr;e)\to K/J'_{\Cr}
$$
as follows. For $i=1$, $o$ is given by
\begin{equation}\label{eqn:one-o}
(a_1,b_1,\ldots,a_\ell,b_\ell,d_1,\ldots,d_r,c) \mapsto
\left[\prod_{i=1}^\ell [\ta_i,\tb_i]\prod_{j=1}^r \td_j \tc^2\right]
\end{equation}
where
$$
(\ta_1\tb_1,\ldots,\ta_\ell,\tb_\ell,
\td_1,\ldots,\td_r,\tc) \in P_1^{-1}(a_1,b_1,\ldots,a_\ell,b_\ell,d_1,\ldots,d_r,c),
$$
and $[k]$ denotes the image of $k$ under the natural projection $K\to
K/J'_{\Cr}$. For $i=2$, $o$ is given by
\begin{equation}\label{eqn:two-o}
(a_1,b_1,\ldots,a_\ell,b_\ell,d_1,\ldots,d_r,c_1,c_2) \mapsto
\left[\prod_{i=1}^\ell [\ta_i,\tb_i]\prod_{j=1}^r \td_j\tc_1^2\tc_2^2\right]
\end{equation}
where
$$
(\ta_1\tb_1,\ldots,\ta_\ell,\tb_\ell, \td_1,\ldots,\td_r,\tc_1,\tc_2) \in
P_2^{-1}(a_1,b_1,\ldots,a_\ell,b_\ell,d_1,\ldots,d_r,c_1,c_2),
$$
Note that the definitions (\ref{eqn:one-o}), (\ref{eqn:two-o}) do not
depend on the choices of
$$
(\ta_1,\tb_1,\ldots,\ta_\ell,\tb_\ell,\td_1,\ldots,\td_r,\tc),\ \
(\ta_1,\tb_1,\ldots,\ta_\ell, \tb_\ell,\td_1,\ldots,\td_r,\tc_1,\tc_2)
$$
respectively. The map $o$ descends to a continuous map
$$
\bar{o}:\Hom_{\Cr}(\pi_1(\Si^{\ell,r}_i,G)/G\to K/J'_{\Cr}
$$
where $i=1,2$.

For $i=1,2$, it is easy to check that $P_i$ restricts to  a surjective map
$$
X_{\tG}^{\ell,r,i}(\cD_1,\ldots,\cD_r;(X,z))
\cong \fh^{2\ell+i-1}\times X_{\tG_{ss}}^{\ell,r,i}(\cD_1,\ldots,\cD_r;z)
\longrightarrow o^{-1}([(X,z)])
$$
for any $(X,z)\in K\subset H\times Z(\tG_{ss})$. By Fact \ref{thm:fiber},
$X_{\tG_{ss}}^{\ell,r,i}(\cD_1,\ldots,\cD_r;z)$
is nonempty and connected if $\ell\geq i$. So $o^{-1}([k])$ is
nonempty and connected if $\ell\geq i$. This completes the proof.  $\ \ \Box$

\bigskip

Finally, Theorem \ref{thm:rzero} follows directly from Theorem
\ref{thm:nonorientable} because $\Hom(\pi_1(\Si^{\ell,0}_i),G)/G$
can be identified with $\Hom_{\{e\}}(\pi_1(\Si^{\ell,1}_i),G)/G$
and $J_{\{e\}}$ is trivial.

\section{Moduli spaces of flat principal $G$-bundles} \label{sec:moduli}

Let $G$ be a compact connected Lie group, and let $\Si$ be a compact
surface. Recall from Section \ref{sec:variety}
that any compact surface is of the form $\Si^{\ell,r}_{i}$
for some nonnegative integers $\ell,r$ and $i=0,1,2$.

A principal $G$-bundle $P$ over a compact surface $\Si$ is trivial
iff it admits a cross section. The obstruction classes $O_n(P)\in H^n(\Si;\pi_{n-1}(G))$ are
obstructions to the existence of a cross section of $P$. They are topological
invariants of $P$. For a surface, the only obstructions are $O_1$ and
$O_2$. Here we consider connected Lie groups so the first obstruction class
$O_1$ is trivial and we are left with the second obstruction class $O_2$
only.

Let $\Prin_G(\Si)$ denote the moduli space of topological principal $G$
bundles over $\Si$. Then $P\mapsto O_2(P)$ defines a bijection
$$
O_2:\Prin_G(\Si)\to H^2(\Si;\pi_1(G))
$$
where
$$
H_2(\lri;\pi_1(G))=\left\{\begin{array}{ll}
\pi_1(G), &  r=i=0,\\
\pi_1(G)/2\pi_1(G), & r=0, i=1,2,\\
0 & r>0.
\end{array}\right.
$$

We first consider the case  $r>0$. From the above discussion,
every principal $G$-bundle over $\lri$ is trivial.
The space of connections on the trivial bundle $\lri\times G$ can be
identified with $\Omega^1(\lri,\fg)$, the space of $\fg$-valued 1-forms on $\lri$.
Let $\Hol_j:\Omega^1(\lri,\fg)\to G$ be the holonomy around the boundary $B_j$.
Given conjugacy classes $\Cr$ of $G$, let
$$
\mlri=\frac{\{A\in\Omega^1(\lri,\fg)\mid F_A=0, \Hol_j(A)\in\cC_j\textup{ for }
  j=1,\ldots, r\} }{C^\infty(\lri,G)}
$$
be the moduli space of gauge equivalence classes of flat connections
on $\lri\times G$ with holonomy around $B_j$ in $\cC_j$.
With suitable choices of orientation on $B_j$, we have
$$
\mlri\cong \Hom_{\Cr}(\pi_1(\Si^{\ell,r}_i),G)/G.
$$
So in Theorem \ref{thm:izero} and Theorem \ref{thm:nonzero},
we may replace $\holC/G$ by $\cM_G(\Si;\Cr)$.

We next consider the case $r=0$.  A principal $G$-bundle on $\Si^{\ell,0}_i$
may be topologically nontrivial. Let $\cM_G(\Si^{\ell,0}_i)$ be the moduli
space of gauge equivalence classes of flat $G$-bundles on $\Si^{\ell,0}_i$.
Here a flat $G$-bundle is a principal $G$-bundle together with a flat $G$
connection.
Then
$$
\cM_G(\Si^{\ell,0}_i)\cong \Hom(\pi_1(\Si^{\ell,0}_i), G)/G.
$$
Let
$$
F: \Hom(\pi_1(\Si^{\ell,0}_i),G)/G\to \Prin_G(\Si^{\ell,0}_i),
$$
be the map which sends a flat $G$-bundle to its underlying topological
principal $G$-bundle. The discussion in \cite[Appendix A]{HL1} shows that
the map
$$
O_2\circ F:\Hom(\pi_1(\Si^{\ell,0}_i),G)/G\to H^2(\Si^{\ell,0}_i;\pi_1(G))
$$
coincides with
$$
\bar{o}:\Hom_{\{e\}}(\pi_1(\Si^{\ell,1}_i),G)/G\cong\Hom(\pi_1(\Si^{\ell,0}_i),G)/G
\to H^2(\Si^{\ell,0}_i;\pi_1(G))$$ defined in the proofs of Theorem \ref{thm:orientable}
and Theorem \ref{thm:nonorientable} in Section \ref{sec:general}. See \cite[Appendix A]{HL1}
for various interpretations of the obstruction map.

Given a topological principal $G$-bundle $P$ over $\Si$, let
$\cM(P)$ denote the moduli space of flat $G$-connections on $P$.
Note that the subgroup $\pi_1(G_{ss})$ of $\pi_1(G)$
consists of torsion elements in $\pi_1(G)$. From the above discussion, our proof
of Theorem \ref{thm:orientable} gives the following statement:
\begin{tm}\label{thm:orientableM}
Let $\Si$ be a connected, closed, compact, orientable surface with
genus $\ell>0$. Let $G$ be a compact connected Lie group, and let
$P$ be a principal $G$-bundle over $\Si$. Then $\cM(P)$ is
nonempty if and only if the obstruction class $O_2(P)\in
H^2(\Si;\pi_1(G))\cong \pi_1(G)$ is a torsion element. In this
case, $\cM(P)$ is connected.
\end{tm}

Similarly, our proof of Theorem \ref{thm:nonorientable} gives the following statement:
\begin{tm}\label{thm:nonorientableM}
Let $\Si$ be a closed, compact, orientable surface which
is homeomorphic to $m$ copies of the real projective plane.
Let $G$ be a compact connected Lie group, and let $P$ be a
principal $G$-bundle over $\Si$. Then $\cM(P)$ is nonempty.
Moreover, $\cM(P)$ is connected if $m\neq 1,2,4$.
\end{tm}

Note that Theorem \ref{thm:orientableM} implies Theorem \ref{thm:irzero},
and Theorem \ref{thm:nonorientableM} implies Theorem \ref{thm:rzero}.
We now outline a proof of Theorem \ref{thm:orientableM} extracted from
\cite{ym}. Let $\Si$, $G$ be as in Theorem \ref{thm:orientableM}, and let
$P$ be a principal $G$-bundle over $\Si$. By \cite[Proposition 6.16]{ym},
$P$ possesses a central Yang-Mills connection. It is proved in
\cite[Section 10]{ym} that the semi-stable stratum, which
is an open and nonempty subset in the space of all $G$-connections on $P$,
contains a unique connected component of the space of Yang-Mills connections
on $P$. This connected component consists of central Yang-Mills
connections on $P$. It is proved in \cite[Section 12]{ym} that central Yang-Mills
connections on $P$ achieve the absolute minimum of Yang-Mills functional on
$P$. This absolute minimum is a topological invariant $L(P)$ of $P$ which
vanishes iff $O_2(P)\in\pi_1(G)$ is a torsion element.
The $G$-bundle $P$ admits a flat $G$-connection iff $L(P)=0$,
and in this case, the space of flat $G$-connections on $P$ is the space
of central Yang-Mills connections on $P$.  This proves Theorem
\ref{thm:orientableM}.

\paragraph{\bf Acknowledgments:}
It is a pleasure to thank L. Jeffrey, E. Meinrenken, and E. Xia for their suggestions and help
during the preparation of this note.


text:
\begin{document}
\bibliographystyle{revtex}

\title{Motion Caused by Magnetic Field in Lobachevsky Space}

\author{V.V. Kudryashov, Yu.A. Kurochkin, E.M. Ovsiyuk and V.M. Red'kov }
 \affiliation{B.I. Stepanov Institute of Physics,
National Academy of Sciences of Belarus,\\  68 Nezavisimosti Ave.,
220072 Minsk, Belarus}

\begin{abstract}
 We study   motion of  a relativistic particle  in the
3-dimensional Lobachevsky space  in the presence of an external
magnetic field which is  analogous to  a constant uniform magnetic
field in the Euclidean space. Three integrals of motion are found
and equations of motion are solved exactly in the special
cylindrical coordinates. Motion on surface  of the cylinder of
constant radius is considered in detail.
\end{abstract}

\keywords{Lobachevsky space, magnetic field, Lagrange equations }

\pacs{ 02.40-k, 03.50-z }

\maketitle

\section{INTRODUCTION}

The description of a particle behavior in a constant uniform
magnetic field is one of the basic problems in theoretical
physics.  As well known in the case of the Euclidean space, this
problem is exactly solved in the classical [1] and  quantum [2,3]
mechanics. Recently the generalization of the quantum mechanical
solution to the case of the Lobachevsky space was given [4,5].

 In the  present paper, an exact  description of a relativistic
 motion of a classical particle in an external magnetic field will
 be constructed on  the background
of the hyperbolic Lobachevsky $H_{3}$ space.
 This result  can be  used to describe the behavior of the charged
particles in macroscopic magnetic field in the context of
astrophysics.

\section{THE LAGRANGE EQUATIONS AND INTEGRALS OF MOTION}

We start with a metric of the Lobachevsky space in the special
cylindrical coordinates [6]:

\begin{eqnarray}
 dS^{2} = c^{2} dt^{2} -   \cosh^{2} (z / \rho) \; d r^{2}\nonumber \\
  -
\rho^{2} \cosh^{2} (z / \rho) \; \sinh^{2} (r / \rho) \;
 d \phi^{2}  - dz^{2} \; ,
 \nonumber
 \\
z \in ( - \infty , + \infty ), \quad r \in [0, +\infty ) , \quad
\phi \in [0, 2 \pi ] \; ,
 \label{1}
 \end{eqnarray}
 where $\rho$ is a curvature radius. The curvilinear coordinates
$(r, \phi,z)$ of the three-dimensional Lobachevsky space are
connected with quasi-Cartesian coordinates of the comprehending
four-dimensional pseudo-Euclidean space by relations

\begin{eqnarray}
 u_{1} = \rho \; \cosh(z / \rho)  \; \sinh(r / \rho)
\; \cos \phi \; , \nonumber \\
  u_{2} = \rho \; \cosh(z /
\rho) \; \sinh(r / \rho) \; \sin \phi \; , \nonumber \\
 u_{3} = \rho \;
\sinh(z / \rho) \; ,
\nonumber
\\
  u_{0} = \rho \; \cosh (z / \rho) \; \sinh
(r / \rho) \;,
\nonumber
\\
 u_{0}^{2} -
u_{1}^{2} - u_{2}^{2} - u_{3}^{3} = \rho^{2} \; , \quad u_{0} = +
\sqrt{\rho^{2}  + {\bf u}^{2} } \;  .
 \label{2}
\end{eqnarray}

The given metric determines the explicit expression for a squared
particle velocity

\begin{eqnarray}
\epsilon = \left({dz \over dt}\right)^{2} + \cosh^{2} (z / \rho )
\left({dr \over dt}\right)^{2} \nonumber \\
+ \cosh^{2} (z / \rho )\rho^{2} \sinh^{2} (r / \rho)
 \left({d \phi \over d t}\right)^{2}  .
\label{3}
\end{eqnarray}

In accordance with [4,5] we define a potential for a magnetic
field in the following form

\begin{equation}
A_{\phi} = - \rho^{2} B \; [ \; \cosh(r / \rho) -1 ]\; .
\label{4}
\end{equation}
This potential generalizes  a potential for a constant uniform
magnetic field with a strength $B$ in the Euclidean space when we
choose the direction of the field as the $z$ axis and use the
usual cylindrical coordinates. The potential (3) is the solution
of Maxwell's equations in the Lobachevsky space. Here these
equations are reduced to a single equation

\begin{eqnarray}
 {1 \over \sqrt{-g}}
{\partial \over \partial x^{r} }\sqrt{-g} \; F^{r \phi} = 0 \;,
\nonumber
\end{eqnarray}

\noindent
where

\begin{eqnarray}
 F_{\phi r} =
\partial_{\phi}A_{r} - \partial_{r} A_{\phi} \; ,
\nonumber
\\
 \sqrt{-g} =   \cosh^{2} (z / \rho) \; \sinh(r /  \rho ) \; .
\nonumber
\end{eqnarray}

The relativistic Lagrangian for a particle in above magnetic field
is of the form

\begin{eqnarray}
L = -mc^{2} \; \sqrt{1 - {\epsilon \over c^{2}}}\nonumber \\
 + \frac{e B \rho^{2}}{c}    [ \cosh(r / \rho) -1 ] \; \left({d \phi
\over d t}\right)\; . \label{5}
\end{eqnarray}

Then the  Lagrange equations of the second order are expressed as

\begin{eqnarray}
{d^{2} r \over dt^{2} } + 2  \; \tanh (z / \rho)  \; \left(dz
\over dt\right) \; \left(dr \over dt \right)
 = \rho \; \sinh (r / \rho)   \nonumber \\
\times  \left [ \; \cosh  (r / \rho) \; \left(d \phi \over
dt\right) + {\omega \over \cosh^{2} (z / \rho )} \; \right ]
\left(d \phi \over dt \right)  \; ,
\label{6}
\end{eqnarray}

\begin{eqnarray}
{d \over dt}\; \left [ \rho^{2}\;  \sinh^{2}(r / \rho ) \;
\cosh^{2} (z / \rho)\; \left(d \phi \over dt \right) \right.
 \nonumber \\
\left.  + \omega \rho^{2}\; (\; \cosh (r / \rho) -1 ) \right ] = 0
\; , \label{7}
\end{eqnarray}

\begin{eqnarray}
 {d^{2} z \over d t^{2}} -  {1 \over \rho } \; \cosh (z /
\rho) \; \sinh (z / \rho) \nonumber \\
\times \left  [\; \left({dr \over dt}\right)^{2} + \rho^{2} \;
\sinh^{2}(r /  \rho)\; \left({d \phi \over d t} \right)^{2} \;
\right ] =0 \; .
\label{8}
\end{eqnarray}
Here we have introduced notation for a quantity

\begin{equation}
\omega =
 {eB \over mc } \;  \sqrt{1 - {\epsilon \over c^{2}}} \; .
\label{9}
\end{equation}

The squared velocity $\epsilon$ is the integral of motion for the
considered system in the Lobachevsky space as the usual squared
velocity is the integral of motion in the Euclidean space.

It is obvious that a quantity

\begin{eqnarray}
I = \omega \rho^{2}\; [\; \cosh (r / \rho) -1 ] \nonumber
\\ + \rho^{2}\; \sinh^{2}(r / \rho ) \; \cosh^{2} (z / \rho)\; \left(d
\phi \over dt \right)   \label{10}
\end{eqnarray}
is conserved. This integral of motion is the generalization of the
usual angular momentum.

At last it is simply to verify that in addition to the conserved
quantities $\epsilon$  and   $I$, third quantity

\begin{equation}
A = \cosh^{4} (z /  \rho ) \left [  \left({dr \over dt}\right)^{2}
+ \rho^{2} \; \sinh^{2} (r /  \rho ) \left({d \phi \over
dt}\right)^{2}  \right ] \;
\label{11}
\end{equation}
is the integral of motion, at $\rho \rightarrow \infty$  it tends
to the squared velocity of motion perpendicular to $z$ axis.

\section{INTEGRATION OF THE EQUATIONS OF MOTION}

It should be stressed that the use of the special cylindrical
coordinates allows us to find the simple analytical expressions
for three integrals of motion. In the presence of these conserved
quantities it is easily to perform transition from the initial
equations of the second order (5) - (7) to the following equations
of the first order:

\begin{equation}
\left({dz \over dt}\right)^{2} = \epsilon - {A \over \cosh^{2} (z
/ \rho )} \; ,
\label{12}
\end{equation}

\begin{equation}
 \left({dr \over dt}\right) ^{2} = {A \over \cosh^{4} (z /
\rho )}\;  - { [  I - \omega \rho^{2}  (  \cosh (r / \rho ) -1 )
\;  ]^{2} \over \ cosh^{4} (z / \rho ) \rho^{2}
 \sinh^{2} (r / \rho )} \;   ,
\label{13}
\end{equation}

\begin{equation}
 {d \phi \over d t} = { I - \omega \rho^{2}\; (\;
\cosh (r / \rho ) -1 ) \over  \rho^{2} \;
 \sinh^{2}(r / \rho ) \;
\cosh^{2} (z / \rho ) } \; . \label{14}
\end{equation}

First of all we consider Eq. (12). The sign of the quantity
$\epsilon -A$ determines the character of solution.

If $\epsilon > A $, then  we have the explicit expressions for the
coordinate

\begin{equation}
\sinh (z(t) / \rho ) = \pm \; \sqrt{1 - {A \over \epsilon } }\;
\sinh ( \sqrt{\epsilon}  (t - t_{0})/ \rho )  \label{15}
\end{equation}
and the velocity

\begin{equation}
{d z(t) \over dt} = \pm \; \sqrt{ \epsilon - { A \epsilon \over
 (\epsilon - A) \; \sinh^{2} (\sqrt{\epsilon} (t- t_{0})/\rho) + \epsilon }}
 \;.
\label{16}
\end{equation}
In this case a particle passes through the point $z = 0$ with
velocity $dz /  dt = \pm \sqrt{\epsilon -A}$.

If $\epsilon < A $, then  we have other explicit expressions for
the coordinate

\begin{equation}
\sinh (z(t) / \rho ) = \pm \; \sqrt{{A \over \epsilon } -1 }\;
\cosh( \sqrt{\epsilon} (t - t_{0})/\rho) \label{17}
\end{equation}
and the velocity

\begin{equation}
{d z(t) \over dt} = \pm \; \sqrt{ \epsilon - { A \epsilon \over
 (A -\epsilon) \; \sinh^{2} (\sqrt{\epsilon} (t- t_{0})/ \rho) + A }} \; .
\label{18}
\end{equation}
In this case the particle moves either in the region

\begin{eqnarray}
\sinh (z / \rho ) >  \sinh (z_+ / \rho ) = \sqrt{A/ \epsilon -1}
\nonumber
\end{eqnarray}
or in the region
\begin{eqnarray}
\sinh (z / \rho ) <  \sinh (z_- / \rho ) = - \sqrt{A/ \epsilon
-1}.
\nonumber
\end{eqnarray}
In other words there is the repulsion at the points $z_-$ and
$z_+$ leading to existence of the forbidden region for motion.

It should be noted that  velocity along $z$ axis is constant in
the case of the Euclidean space ($\rho \rightarrow \infty$)
 whereas  velocity along $z$ axis is variable in the case of the
Lobachevsky space.

From the equations (12) - (14) it is seen that after obtaining the
explicit dependence $z(t)$, the further solution of the problem is
reduced to the following integrations

\begin{eqnarray}
\int { \rho  \sinh (r / \rho ) \; dr \over \sqrt{w(r)}}\nonumber \\
 =
 \pm \; \int {dz \over  \cosh(z / \rho )\; \sqrt{ \epsilon  \cosh^{2} (z / \rho ) - A }} \; ,
\label{19}
\end{eqnarray}

\begin{equation}
\phi - \phi_{0} =  \pm  \int {  [ I - \omega \rho^{2} ( \cosh (r /
\rho ) -1  )  ] \; d r  \over \rho \; \sinh  (r / \rho )
\sqrt{w(r) }} \; , \label{20}
\end{equation}
where

\begin{eqnarray}
 w(r)=A \rho^{2} \sinh^{2} (r / \rho ) - [ I -
\omega \rho^{2} \;
 (  \cosh(r / \rho ) - 1  )  ] ^{2}.
\nonumber
\end{eqnarray}

 Both formula (19) for the dependence $r(z)$  and formula
(20) for the dependence $\phi (r)$   give the particle orbit.

Now we examine the connection of $\phi$ and $r$ in detail. The
integration in (20) leads to the following relation

\begin{eqnarray}
(I + \omega  \rho^{2})  \cosh (r / \rho )  - \omega \;\rho^2
\nonumber \\
= \sqrt{C} \;\rho \sinh (r / \rho )  \cos (\phi - \phi_{0}) \; ,
\label{21}
\end{eqnarray}
where

\begin{equation}
C = A - \rho^{2} \omega^{2} + \frac{1}{\rho^{2}}(I  + \omega
\rho^2)^{2} \; . \label{22}
\end{equation}

A quantity $C$ as function of $A$ and $I$ is the integral of
motion and has the form

\begin{eqnarray}
C =  \cosh^{4} (z /  \rho )\;  \left({dr \over dt}\right)^{2} +
\rho^{2} \; \sinh^{2} (r / \rho) \nonumber \\
\times \left [\; \cosh (r / \rho ) \;\; \cosh^{2} (z /  \rho) \;
\left(d \phi \over dt\right) + \omega \; \right ]^{2} \; ,
\label{23}
\end{eqnarray}
$$
C \geq 0 \; .
$$

\section{THE  MOTION ON THE CYLINDRICAL SURFACE}

Let us compare formula (21) with the well known formula

\begin{eqnarray}
\cosh (R / \rho ) \; \cosh (r / \rho ) - \cosh (r_{0} / \rho )
\nonumber \\
= \sinh (R / \rho )\; \sinh(r / \rho) \; \cos (\phi - \phi_{0})
\label{24}
\end{eqnarray}
describing in the Lobachevsky space  a circle of radius $r_{0}$,
if a distance between a circle center and the origin of
coordinates is $R$. Formulas (21) and (24) coincide, if the
parameters $R$ and $r_0$ are connected with the integrals of
motion $A$ and $I$ by the relations

\begin{equation}
\cosh (r_{0} / \rho ) = {1 \over  \sqrt{1 - A / \omega^{2}
\rho^{2} }} \; ,
\label{25}
\end{equation}
\begin{equation}
 \cosh (R / \rho ) = { I + \omega \rho^{2} \over  \omega
\rho^{2}   \sqrt{1 - A / \omega^{2} \rho^{2}}} \; . \label{26}
\end{equation}

We emphasize that the expressions (25) and (26) become sensible,
if the inequality

\begin{equation}
 A < \omega^{2} \rho^{2}
\label{27}
\end{equation}
is accomplished. Then in the $(r, \phi)$ - projection, a particle
moves along the circle. The circle center is shifted with respect
to the origin. Taking into account a motion in the $z$ direction
we get a complete  motion on the cylindrical surface.
 The  coincidence of a coordinate origin and a circle center
 corresponds to the zeroth value of the integral of motion $C$. In
 this case a $z$ axis coincides with a  cylinder axis.

 The transition to this coordinate system leads to the considerable
 simplification. From the condition $C=0$  we see that

\begin{equation}
{dr \over dt } = 0 \; , \quad (r = r_{0}) \; ,
\label{28}
\end{equation}

\begin{equation}
  {d \phi \over d t} = - { \omega \over  \cosh (r_{0} / \rho)\; \cosh^{2} (z / \rho ) } \; .
 \label{29}
 \end{equation}

In this case the integrals of motion $A$ and $I$ are expressed via
the circle radius $r_0$  as follows

 \begin{equation}
A = \omega^{2} \rho^{2} \; \tanh^{2} (r_{0} / \rho )\; ,
\label{30}
\end{equation}
\begin{equation}
  I = \omega \rho^{2} \; \left[ \; {1 \over
\cosh (r_{0} / \rho )}  -1 \right] \; . \label{31}
\end{equation}
Taking into account the relations (15) - (18) we get the explicit
formulas  describing evolution of an angle  and an angular
velocity.

If $\epsilon > A$, we obtain the following expressions

 \begin{eqnarray}
 \phi(t) - \phi_{0} =   {- \omega \rho \over
\cosh (r_{0} / \rho ) \; \sqrt{A} } \nonumber \\
\times  \mbox{artanh}\; \left [ \; \sqrt{{A \over \epsilon } } \;
\tanh ( \sqrt{\epsilon} (t - t_{0} )/ \rho ) \; \right ] \; ,
\label{32}
\end{eqnarray}

\begin{equation}
{d \phi (t) \over dt } =  { - \omega \epsilon \over  \cosh (r_{0}
/ \rho )  [(\epsilon - A)  \sinh^{2} (\sqrt{\epsilon}(t - t_{0})/
\rho ) + \epsilon ]}
\\[2mm]
\label{33}
\end{equation}
and if $\epsilon < A$, we obtain other expressions

 \begin{eqnarray}
 \phi(t) - \phi_{0} =   {- \omega \rho \over \cosh \;(r_{0} /
\rho ) \; \sqrt{A} }
\nonumber
\\
 \times \mbox{artanh} \; \left [ \; \sqrt{{\epsilon
\over  A } } \; \tanh ( \sqrt{\epsilon}  (t - t_{0} )/ \rho ) \;
\right ] \; ,
\label{34}
\end{eqnarray}

\begin{equation}
{d \phi (t) \over dt } =  { - \omega \epsilon \over  \cosh (r_{0}
/ \rho ) [(A- \epsilon ) \; \sinh^{2} (\sqrt{\epsilon} (t -
t_{0})/ \rho ) + A  ]} \; .\label{35}
\end{equation}

In the case of the Euclidean space the angular velocity is
constant whereas in the case of the Lobachevsky space the angular
velocity is variable and tends to zero at $t \rightarrow \infty$.

\section{Conclusion}

In conclusion several additional  remarks should be given. It can
be shown that the formula (21)  for trajectories in the form $F(r,
\phi)=0$ describes not only the motions on cylindrical surfaces,
shifted or not with respect to the initial axis $z$, but also
describes  motions infinite in radial variable $r$. So, there
exist two  different classes of trajectories, finite and infinite
in radial variable.

Besides, it can be  demonstrated that the potential of the
magnetic field (4)  is invariant
 with respect to shifts in  the Lobachevsky
space in the plane perpendicular to the axis $z$. This symmetry
underlies the structure of two families  of  possible solutions of
the equations of motion,  providing us with a transitivity group
acting
 within two classes of motions.

 All results can be extended to a spherical  Riemann model $S_{3}$
 on the base of the metric
 \begin{eqnarray}
 dS^{2} = c^{2} dt^{2} -   \cos^{2} (z / \rho) \; d r^{2}\nonumber \\
  -
\rho^{2} \cos^{2} (z / \rho) \; \sin^{2} (r / \rho) \;
 d \phi^{2}  - dz^{2} \; ,
 \nonumber
 \\
z \in [ - \pi / 2, + \pi / 2  ] , \quad r \in [0, +\pi ] , \quad
\phi \in [0, 2 \pi ] \
 \label{36}
 \end{eqnarray}
and a potential for a magnetic field   in $S_{3}$ according to

\begin{equation}
A_{\phi} =  \rho^{2} B \; [ \; \cos(r / \rho) -1 ]\; .
\label{37}
\end{equation}

\section{Acknowledgments}

  The authors are grateful to E.~A. Tolkachev for valuable comments and useful
  discussion. This work has been supported by the Belarusian
  Republican Foundation for Fundamental Research (Project No.
  F09D - 009).

config: arxiv


TITLE: Anyone to solve $ \int_0^{\infty} \Big[ (k+1) + (n-k-1) e^{\alpha x} \Big] ^{-2} \alpha x e^{\alpha x} dx $
QUESTION [2 upvotes]: I'm trying to solve the following formula, but my calculus is quite unhandsome.
$$
\int_0^{\infty} \Big[ (k+1) + (n-k-1) e^{\alpha x} \Big] ^{-2} \alpha x e^{\alpha x} dx
$$
I tried:
$$
\int_0^{\infty} \Big[ (k+1) + (n-k-1) e^{\alpha x} \Big] ^{-2} \alpha x e^{\alpha x} dx = \int_0^{\infty} \Big[ (k+1) + (n-k-1) e^{y} \Big] ^{-2} (y/\alpha) e^{y} dy
$$
And somewhat felt that it looks related to logistic function.
Can anybody give some hints?

REPLY [2 votes]: With observing
$$\dfrac{d}{d\alpha}\left(\dfrac{1}{(k+1)+(n-k-1)e^{\alpha x}}\right)=\dfrac{-(n-k-1)xe^{\alpha x}}{\left((k+1)+(n-k-1)e^{\alpha x}\right)^2}$$
then the desire integral is
\begin{align}
I
&=\dfrac{\alpha}{-(n-k-1)}\int_0^\infty\dfrac{-(n-k-1)xe^{\alpha x}}{\left((k+1)+(n-k-1)e^{\alpha x}\right)^2}dx\\
&=\dfrac{\alpha}{-(n-k-1)}\dfrac{d}{d\alpha}\int_0^\infty\dfrac{1}{(k+1)+(n-k-1)e^{\alpha x}}dx\\
&=\dfrac{\alpha}{-(n-k-1)}\dfrac{d}{d\alpha}\int_0^\infty\dfrac{e^{-\alpha x}}{(k+1)e^{-\alpha x}+(n-k-1)}dx\\
&=\dfrac{1}{-\alpha(k+1)(n-k-1)}\ln\dfrac{n-k-1}{n}\end{align}

REPLY [2 votes]: Well, we have (assuming that the integral exists):
$$\mathcal{I}_{\space\text{n}}\left(\text{k},\alpha\right):=\int_0^\infty\frac{\alpha\cdot x\cdot\exp\left(\alpha\cdot x\right)}{\left(1+\text{k}+\exp\left(\alpha\cdot x\right)\cdot\left(\text{n}-\text{k}-1\right)\right)^2}\space\text{d}x\tag1$$
Now, first of all let:
 1. $$\beta_1:=1+\text{k}\tag2$$
 2. $$\beta_2:=\text{n}-\text{k}-1\tag3$$
So, we can rewrite equation $\left(1\right)$ as follows:
$$\mathcal{I}_{\space\text{n}}\left(\text{k},\alpha\right)=\int_0^\infty\frac{\alpha\cdot x\cdot\exp\left(\alpha\cdot x\right)}{\left(\beta_1+\exp\left(\alpha\cdot x\right)\cdot\beta_2\right)^2}\space\text{d}x=\alpha\cdot\int_0^\infty\frac{x\cdot\exp\left(\alpha\cdot x\right)}{\left(\beta_1+\exp\left(\alpha\cdot x\right)\cdot\beta_2\right)^2}\space\text{d}x\tag4$$
Now, substitute $\text{u}:=\exp\left(\alpha\cdot x\right)$, so we get:
$$\mathcal{I}_{\space\text{n}}\left(\text{k},\alpha\right)=\alpha\cdot\frac{1}{\alpha^2}\cdot\lim_{\text{p}\to\infty}\int_1^{\exp\left(\alpha\cdot\text{p}\right)}\frac{\ln\left(\text{u}\right)}{\left(\beta_1+\text{u}\cdot\beta_2\right)^2}\space\text{d}\text{u}\tag5$$
Using IBP:
$$\mathcal{I}_{\space\text{n}}\left(\text{k},\alpha\right)=\frac{1}{\alpha\cdot\beta_2}\cdot\left\{\text{Z}+\lim_{\text{p}\to\infty}\int_1^{\exp\left(\alpha\cdot\text{p}\right)}\frac{1}{\text{u}\cdot\left(\beta_1+\text{u}\cdot\beta_2\right)}\space\text{d}\text{u}\right\}\tag6$$
Where:
$$\text{Z}:=\lim_{\text{p}\to\infty}\left[-\frac{\ln\left(\text{u}\right)}{\beta_1+\text{u}\cdot\beta_2}\right]_1^{\exp\left(\alpha\cdot\text{p}\right)}\tag7$$
Assuming that $\alpha\in\mathbb{R}$, we can write:
$$\text{Z}=-\lim_{\text{p}\to\infty}\frac{\alpha\cdot\text{p}}{\beta_1+\exp\left(\alpha\cdot\text{p}\right)\cdot\beta_2}=0\tag8$$
So, we can rewrite equation $\left(6\right)$ as follows:
$$\mathcal{I}_{\space\text{n}}\left(\text{k},\alpha\right)=\frac{1}{\alpha\cdot\beta_2}\lim_{\text{p}\to\infty}\int_1^{\exp\left(\alpha\cdot\text{p}\right)}\frac{1}{\text{u}\cdot\left(\beta_1+\text{u}\cdot\beta_2\right)}\space\text{d}\text{u}=$$
$$\frac{1}{\alpha\cdot\beta_1\cdot\beta_2}\cdot\lim_{\text{p}\to\infty}\left[\ln\left|\frac{\text{u}}{\beta_1\cdot\left(\beta_1+\text{u}\cdot\beta_2\right)}\right|\right]_1^{\exp\left(\alpha\cdot\text{p}\right)}=$$
$$\frac{1}{\alpha\cdot\beta_1\cdot\beta_2}\cdot\lim_{\text{p}\to\infty}\left\{\ln\left|\frac{\exp\left(\alpha\cdot\text{p}\right)}{\beta_1\cdot\left(\beta_1+\exp\left(\alpha\cdot\text{p}\right)\cdot\beta_2\right)}\right|-\ln\left|\frac{1}{\beta_1\cdot\left(\beta_1+\beta_2\right)}\right|\right\}=$$
$$\frac{1}{\alpha\cdot\beta_1\cdot\beta_2}\cdot\lim_{\text{p}\to\infty}\ln\left|\frac{\left(\beta_1+\beta_2\right)\cdot\exp\left(\alpha\cdot\text{p}\right)}{\beta_1+\exp\left(\alpha\cdot\text{p}\right)\cdot\beta_2}\right|\tag9$$


TITLE: _Actually_ hearing the shape of a drum
QUESTION [8 upvotes]: The problem of hearing the shape of a drum is well known as a mathematical problem.
But what about as a problem of (1) physics and (2) human perception?
Suppose you have the kind of membrane used with a kettle drum but without the kettle.  One musician tries to adjust the pitch and loudness, etc., so that the square one and the circular one sound as similar as possible; an opposing musician is allowed to hear but not to see, and tries to identify the round one and the square one by the sound.  And so on with other shapes.
And if unaided human perception doesn't work, how much analysis can be done with electronic gadgets?
Later note: I find a comment below, saying this isn't actually a mathematical question.  As I pointed out below, an answer might bear upon the mathematics. A simple-minded stereotype says mathematics can shed light on the things it's applied to, but not vice-versa. But that is known to be an error.

REPLY [2 votes]: The solution of any initial problem for a vibrating drum can be represented as a superposition of natural modes (i.e. eigen-modes). The corresponding eigen-values would be referred to as the natural frequencies. When you kick the drum you end up exciting one or several eigen-modes. The specific amplitudes of these modes depend on your initial condition (the way you kick the drum). However, realistic loading would tend to happen relatively slowly and, therefore, result in higher-frequency modes having smaller amplitudes. The resulting sound would normally be dominated by one of the lowest-frequency modes of the drum, with the higher-frequency modes contributing to the resulting timbre.
Suppose that you have a round drum. Its sound, for the majority of realistic initial conditions, will be dominated by its lowest frequency eigen-mode. Hence, someone trying to make an audibly-indistinguishable square drum will first have to match their lowest natural frequencies. However, there is absolutely no reason why this would also match their second and higher natural frequencies. Thus, such drums would have the same "dominant" tone, but different timbre, making them easily distinguishable even by untrained ear.
However, if you are allowed to change the shape in a wider range, say, consider rectangular drums, you will be able to match 2 (for rectangle), 3, and more lowest modes (for more complicated shapes). The resulting timbre of these drums can be made much closer to each other and, at some point, untrained, or even trained, ear will become unable to tell the difference.
Keep in mind that I implicitly assumed here that the we can always reproduce the specific distribution of the amplitudes of natural modes for both drums. This means, however, that to achieve the same sound you are likely to need to kick different drums in a different fashion.


text:
\begin{document}

\title{Age-Based Coded Computation for\\
Bias Reduction in Distributed Learning
\thanks{This work was supported in part by the Marie Sklodowska-Curie Action SCAVENGE (grant agreement no. 675891), and by the European Research Council (ERC) Starting Grant BEACON (grant agreement no. 677854).}
}

	\author[1]{Emre Ozfatura}
	\author[2]{Baturalp Buyukates}
	\author[1]{Deniz Gunduz}
	\author[2]{Sennur Ulukus}
	\affil[1]{\normalsize Department of Electrical and Electronic Engineering, Imperial College London, UK}
	\affil[2]{\normalsize Department of Electrical and Computer Engineering, University of Maryland, MD, USA}

\maketitle
\begin{abstract}
Coded computation can be used to speed up distributed learning in the presence of straggling workers. Partial recovery of the gradient vector can further reduce the computation time at each iteration; however, this can result in biased estimators, which may slow down convergence, or even cause divergence. Estimator bias will be particularly prevalent when the straggling behavior is correlated over time, which results in the gradient estimators being dominated by a few fast servers. To mitigate biased estimators, we design a \emph{timely} dynamic encoding framework for partial recovery that includes an ordering operator that changes the codewords and computation orders at workers over time. To regulate the recovery frequencies, we adopt an \emph{age} metric in the design of the dynamic encoding scheme. We show through numerical results that the proposed dynamic encoding strategy increases the timeliness of the recovered computations, which as a result, reduces the bias in model updates, and accelerates the convergence compared to the conventional static partial recovery schemes.
\end{abstract}

\section{Introduction}
One of the main factors behind the success of machine learning algorithms is the availability of large datasets for training. However, as datasets become ever larger, the required computation becomes impossible to execute in a single machine within a reasonable time frame. This computational bottleneck can be overcome by  distributed learning across multiple machines,  called {\em workers}. \\
\indent Gradient descent (GD) is the most common approach in supervised learning, and can be easily distributed. By employing a {\em parameter server} (PS) type framework \cite{PSGD4}, the dataset can be divided among workers, and at each iteration, workers compute  gradients based on their local data, which can be aggregated by the PS. However, slow, so-called {\em straggling}, workers are the Achilles heel of distributed GD (DGD) since the PS has to wait for all the workers to complete an iteration. A wide range of straggler-mitigation strategies have been proposed in recent years \cite{UCCT.1, UCCT.3, UCCT.4, UCCT.6, UCCT.7, CC.1, CC.2, CC.3, CC.4, CC.5, Yang19, CC.6, CC.8, CC.11, CC.17, CC.18, CC.AG1, entropy}. The main notion is to introduce redundancy in the computations assigned to each worker, so that fast workers can compensate  for the stragglers.\\
\indent Most of the coded computation solutions for straggler mitigation suffers from two drawbacks: First, they allow each worker to send a single message per iteration, which results in the under-utilization of computational resources \cite{entropy}. Second, they recover the full gradient at each iteration, which may unnecessarily increase the average completion time of an iteration. Multi-message communication (MMC) strategy addresses the first drawback by allowing each worker to send multiple messages per-iteration, thus, seeking a balance between computation and communication latency \cite{CC.2,CC.5,CC.11,CC.13,CC.23,CC.33, UCUT.4,UCCT.6}. \cite{icassp-ext} addresses the second drawback by combining coded computation with partial recovery (CCPR) to provide a trade-off between the average completion time of an iteration and the  accuracy of the recovered gradient estimate.

If the straggling behavior is not independent and identically distributed over time and workers, which is often the case in practice, the gradient estimates recovered by the CCPR scheme become biased. For example, this may happen when a worker straggles over multiple iterations. Regulating the recovery frequency of the partial computations to make sure that each partial computation contributes to the model updates as equally as possible is critical to avoid biased updates. We use the age of information (AoI) metric to track the recovery frequency of partial computations.

AoI has been proposed to quantify the data freshness over systems that involve time-sensitive information \cite{Kaul12a}. AoI studies aim to guarantee timely delivery of time-critical information to receivers. AoI has found applications in queueing and networks, scheduling and optimization, and reinforcement learning (see the survey in \cite{SunSurvey}). Recently, \cite{Buyukates19c} considered the age metric in a distributed computation system that handles time-sensitive computations, and \cite{Yang19a} introduced an age-based metric to quantify the staleness of each update in a federated learning system. In our work, we associate an age to each partial computation and use this age to track the time passed since the last time each partial computation has been recovered.

In this paper, we design a dynamic encoding framework for the CCPR scheme that includes a timely dynamic order operator to prevent biased updates, and improve the performance. The proposed scheme increases the timeliness of the recovered partial computations by changing the codewords and their computation order over time. To regulate the recovery frequencies, we use \textit{age of the partial computations} in the design of the dynamic order operator. We show by numerical experiments on a linear regression problem that the proposed dynamic encoding scheme increases the timeliness of the recovered computations, results in less biased model updates, and as a result, achieves better convergence performance compared to the conventional static encoding framework.

\begin{figure}
\centering
\includegraphics[scale=0.4]{erasure.eps}
\caption{Illustration of  partial recovery in a naive distributed computation scenario with 6 workers, 2 of which are stragglers.}
\label{erasure}
\vspace{-0.5cm}
\end{figure}

\section{System Model and Problem Formulation}
For completeness, we first present the coded computation framework and the CCPR scheme.
\subsection{DGD with Coded Computation }
We focus on the least-squares linear regression problem, where the loss function is the empirical mean squared error
\begin{equation}
L(\boldsymbol{\theta}) \triangleq \frac{1}{2N}\sum_{i=1}^{N}(y_{i}-\mathbf{x}_{i}^{T}\boldsymbol{\theta})^{2},
\label{loss}
\end{equation}
where $\mathbf{x}_{1},\ldots,\mathbf{x}_{N} \in \mathbb{R}^{d}$
are the data points with corresponding labels $y_{1},\ldots,y_{N} \in \mathbb{R}$, and $\boldsymbol{\theta}\in \mathbb{R}^{d}$ is the parameter vector. The optimal parameter vector can be obtained iteratively by using the gradient descent (GD) method
\begin{equation}
\boldsymbol{\theta}_{t+1}=\boldsymbol{\theta}_{t}-\eta_{t} \nabla_{\boldsymbol{\theta}} L(\boldsymbol{\theta}_{t}),
\end{equation}
 where $\eta_{t}$ is the learning rate and $\boldsymbol{\theta}_{t}$ is the parameter vector at the $t$th iteration. Gradient of the loss function in (\ref{loss}) is
 \begin{equation}
 \nabla_{\boldsymbol{\theta}} L(\boldsymbol{\theta_t}) = \mathbf{X}^{T} \mathbf{X} \boldsymbol{\theta}_{t}-\mathbf{X}^{T}\mathbf{y},
 \label{grad_comp}
 \end{equation}
 where $\mathbf{X}=[\mathbf{x}_{1},\ldots,\mathbf{x}_{N}]^{T}$ and
$\mathbf{y}=[y_{1},\ldots,y_{N}]^{T}$. In (\ref{grad_comp}), only $\boldsymbol{\theta}_{t}$ changes over iterations. Thus, the key computational task at each iteration is the  matrix-vector multiplication of $\mathbf{W}\boldsymbol{\theta}_{t}$, where $\mathbf{W}\defeq\mathbf{X}^{T}\mathbf{X}\in\mathbb{R}^{d\times d}$. To speed up GD, execution of this multiplication can be distributed across $K$ \textit{workers}, by simply dividing $\mathbf{W}$ into $K$ equal-size disjoint submatrices. However, under this naive approach, computation time is limited by the {\em straggling} workers \cite{CC.1}.

Coded computation is used to tolerate stragglers by encoding the data before it is distributed among workers to achieve certain redundancy. That is, with coded computation, redundant partial computations are created such that the result of the overall computation can be obtained from a subset of the partial computations. Thus, up to certain number of stragglers can be tolerated since the PS can recover the computation result without getting partial results from all workers. Many coded computation schemes, including MDS \cite{CC.1,CC.2,CC.8}, LDPC \cite{CC.3}, and rateless codes \cite{CC.23} and their various variants have been studied in the literature.

\subsection{Coded Computation with Partial Recovery (CCPR)}
In naive uncoded distributed computation for gradient computation, straggling workers result in erasures in the gradient vector as illustrated in Fig.~\ref{erasure}. The main motivation behind the coded computation schemes is to find the minimum number of responsible workers to guarantee the recovery of the gradient vector without any erasures. Alternatively, the CCPR scheme \cite{icassp-ext} allows erasures on the gradient vector to reduce the computation time while controlling the number of erasures to guarantee certain accuracy for the gradient estimate.

\indent To enable  partial recovery, we focus on a linear code structure such that $\mathbf{W}$ is initially divided into $K$ disjoint submatrices $\mathbf{W}_{1},\ldots,\mathbf{W}_{K}\in\mathbb{R}^{d/K\times d}$. Then, $r$ coded submatrices, $\tilde{\mathbf{W}}_{i,1},\ldots,\tilde{\mathbf{W}}_{i,r}$, are assigned to each worker $i$ for computation, where each coded matrix $\tilde{\mathbf{W}}_{i,j}$ is a linear combination of $K$ submatrices, i.e.,
\begin{equation}
\tilde{\mathbf{W}}_{i,j}=\sum_{k\in[K]}\alpha^{(i)}_{j,k}\mathbf{W}_{k}.
\end{equation}
 Following the initial encoding phase, at each iteration $t$, the $i$th worker performs the computations $\tilde{\mathbf{W}}_{i,1}\boldsymbol{\theta}_{t},\ldots,\tilde{\mathbf{W}}_{i,r}\boldsymbol{\theta}_{t}$ in the given order, and sends the results one by one as soon as they are completed. In the meantime, the PS collects coded computations from all the workers until it successfully recovers $(1-q) \times 100$ percent of the gradient entries. Parameter $q$ denotes the {\em tolerance},  which is a design parameter and can be chosen according to the learning problem. In the scope of this work, we utilize the random circularly shifted (RCS) code \cite{icassp-ext}, which allows workers to change codewords over time. In a broad sense, in RCS codes, $\mathbf{W}$ is divided into $K$ submatrices $\mathbf{W}_{1},\ldots,\mathbf{W}_{K}\in\mathbb{R}^{d/K\times d}$ and those submatrices are concatenated to form $\bar{\mathbf{W}}=[\mathbf{W}_{1},\ldots,\mathbf{W}_{K}]$. Then an assignment matrix, showing assigned submatrices to each worker, is formed by operating random circular shifts on $\bar{\mathbf{W}}$. Once the assignment matrix is established, codewords for each worker $i$ can be constructed by combining those submatrices in the $i$th column according to a certain order.

 Next, we illustrate how RCS codes can be adapted to timely dynamic encoding.

\subsection{ Partial Recovery and Timely Dynamic Encoding}\label{dynamic_enc}
Dynamic encoding process consists of three phases namely; {\em data partition}, {\em ordering} and {\em encoding}, where the corresponding operators are denoted by $D(\cdot)$, $O(\cdot)$ and $E(\cdot)$, respectively.
Data partition operator distributes the submatrices $\mathcal{W}=\left\{\mathbf{W}_{1},\ldots,\mathbf{W}_{K}\right\}$ among the workers such that
\begin{equation}
D_{i}(\mathcal{W},M): \mathcal{W} \mapsto  \mathcal{W}_{i},~~ \vert \mathcal{W}_{i}\vert \leq M,
\end{equation}
where, $M$ is a given memory constraint and $\mathcal{W}_{i}$ is the set of assigned submatrices to the $i$th worker. We assume that operator $D(\cdot)$ is executed, for each worker, only once before the process, and thus  set $\mathcal{W}_{i}$ remains the same over the iterations.
The order operator $O(\cdot)$ is used to form an ordered set from the initial set $\mathcal{W}_{i}$ for encoding, i.e.,
\begin{equation}
O_{i,t}(\mathcal{W}_{i}): \mathcal{W}_{i} \mapsto  \tilde{\mathcal{W}}_{i,t},
\end{equation}
where $\tilde{\mathcal{W}}_{i,t}$ is an ordered set representing the order of computation at each iteration $t$ for the $i$th worker. We remark  that unlike the data partition operator, order operator may change over time. These two operators together can be represented by an assignment matrix $\mathbf{A}_{t}$, whose $i$th column is given by $\tilde{\mathcal{W}}_{i,t}$.

Once the assignment matrix $\mathbf{A}_{t}$ is fixed, the encoding process is executed according to a {\em degree vector} $\mathbf{m}$, which identifies the degree of each codeword based on its computation order. Encoding is executed for each worker independently. The encoder operator $E(\cdot)$ maps the ordered set of data (submatrices) to ordered set of codewords of size $L$, where $L$ is the length of $\mathbf{m}$, i.e.,
\begin{equation}
E_{i,t}(\tilde{\mathcal{W}}_{i,t},\mathbf{m}): \tilde{\mathcal{W}}_{i,t} \mapsto  \tilde{\mathcal{C}}_{i,t}=\left\{\mathbf{C}^{t}_{i,1},\ldots,\mathbf{C}^{t}_{i,L}\right\}.
\end{equation}

\begin{figure}[t]
	\centering  \includegraphics[width=0.9\columnwidth]{age_evol.eps}

	\caption{Sample age evolution of partial computation $\mathbf{W}_k\boldsymbol{\theta}$. Time $t$ marks the beginning of iteration $t+1$. $\mathbf{W}_k\boldsymbol{\theta}$ is recovered at iterations $t$ and $t+4$. }
	\label{fig:age_evol}
	\vspace{-0.5cm}
\end{figure}

The encoding operator first divides set $\tilde{\mathcal{W}}_{i,t}$ into $L$ disjoint subsets, $\mathcal{W}^{t}_{i,1},\ldots,\mathcal{W}^{t}_{i,L}$,  such that $\vert\mathcal{W}^{t}_{i,l}\vert=\mathbf{m}(l)$. Then, at iteration $t$, the coded submatrix of the $i$th worker with computation order $\ell$, denoted by $\mathbf{C}^{t}_{i,\ell}$, is constructed as
\begin{equation}
\mathbf{C}^{t}_{i,\ell}=\sum_{\mathbf{W}_{k}\in\mathcal{W}^{t}_{i,\ell}}\mathbf{W}_{k}.
\end{equation}

An example assignment matrix $\mathbf{A}_{t}$ is given below for $K=20$ and $M=6$:
 \begin{equation}
\mathbf{A}_{t}=
  \begin{bmatrix}
  {\color{blue}\mathbf{W}_{1}} & {\color{blue}\mathbf{W}_{2}} & {\color{blue}\mathbf{W}_{3}} & \dots  & {\color{blue}\mathbf{W}_{20}} \\
  {\color{red}\mathbf{W}_{4}}\ & {\color{red}\mathbf{W}_{5}} & {\color{red}\mathbf{W}_{6}} & \dots  & {\color{red}\mathbf{W}_{3}} \\
  {\color{red}\mathbf{W}_{11}} & {\color{red}\mathbf{W}_{12}} & {\color{red}\mathbf{W}_{13}} & \dots  & {\color{red}\mathbf{W}_{10}}\\
  {\color{brown}\mathbf{W}_{15}} & {\color{brown}\mathbf{W}_{16}} & {\color{brown}\mathbf{W}_{17}} & \dots  & {\color{brown}\mathbf{W}_{14}} \\
  {\color{brown}\mathbf{W}_{6}} & {\color{brown}\mathbf{W}_{7}} & {\color{brown}\mathbf{W}_{8}} & \dots  & {\color{brown}\mathbf{W}_{5}} \\
  {\color{brown}\mathbf{W}_{18}} & {\color{brown}\mathbf{W}_{19}} & {\color{brown}\mathbf{W}_{20}} & \dots  & {\color{brown}\mathbf{W}_{17}}\\
  \end{bmatrix}.\label{rcsc_dist}
 \end{equation}

The elements of the assignment matrix $\mathbf{A}_{t}$ are colored  to illustrate the first step of the encoding operator, for  $\mathbf{m}=[1, 2, 3]$, where colors blue, red and yellow represent the submatrices used to generate the first, second, and third codewords, respectively. The encoding phase for the first worker at iteration $t$ is illustrated below:
 \begin{equation}
\tilde{\mathcal{W}}_{1,t} =
  \begin{bmatrix}
  {\color{blue}\mathbf{W}_{1}} \\
  {\color{red}\mathbf{W}_{4}} \\
  {\color{red}\mathbf{W}_{11}} \\
  {\color{brown}\mathbf{W}_{15}} \\
  {\color{brown}\mathbf{W}_{6}} \\
  {\color{brown}\mathbf{W}_{18}} \\
  \end{bmatrix} \rightarrow
  \tilde{\mathcal{C}}_{1,t} =

  \begin{bmatrix}
   \mathbf{W}_{1} \\
   \mathbf{W}_{4} + \mathbf{W}_{11} \\
   \mathbf{W}_{15} + \mathbf{W}_{6} + \mathbf{W}_{18}\\
  \end{bmatrix}.\label{encoding_exp}
 \end{equation}
With this code, the worker first computes $\mathbf{W}_{1}\boldsymbol{\theta}_t$ and sends the result directly to the PS. Then, it computes $(\mathbf{W}_{4} + \mathbf{W}_{11})\boldsymbol{\theta}_t$ sends the result to the PS. Finally, it computes $(\mathbf{W}_{15} + \mathbf{W}_{6} + \mathbf{W}_{18})\boldsymbol{\theta}_t$ and sends the result to the PS.

Next, we formally state the problem using the data partition, ordering and encoding operators.

\subsection{Problem Definition}
The recovery of a partial computation $\mathbf{W}_k\boldsymbol{\theta}$ at iteration $t$ depends on the data partition $\left\{ D_i\right\}_{i\in[K]}$, ordering decisions $\left\{ O_{i,t}\right\}_{i\in[K]}$, encoding decisions $\left\{ E_{i,t}\right\}_{i\in[K]}$, computation delay statistics of the workers, $\mathbf{d}_t$, and the tolerance $q$, i.e.,
\begin{equation}
\mathbf{r}_t=R(D, O_t, E_t, d_t,q),
\end{equation}
where $R$ is the recovery operation that returns a vector $\mathbf{r}_t$ which demonstrates the recovered partial computations such that $\mathbf{r}_t(k) = 1$ if $\mathbf{W}_k\boldsymbol{\theta}_{t}$ is recovered at the PS for $k\in[K]$.\\
\indent In the partial recovery approach, without any further control on the assigned computations, operators are fixed throughout the training process. Thus, recovered submatrix indices may be correlated over time and some partial computations may not be recovered at all. We note that this kind of recovery behavior may lead to divergence especially when $q$ is large, since the updates become biased. Our goal is to introduce a dynamic approach for the coded computation/partial recovery procedure to regulate the recovery frequency of each partial computation. For this, we first introduce an age-based performance metric.

We define the age of partial computation $\mathbf{W}_k\boldsymbol{\theta}$ at iteration $t$, denoted by $a_{k,t}$, as the number of iterations  since the last time the PS recovered  $\mathbf{W}_k\boldsymbol{\theta}$. The age for each partial computation is updated at the end of each iteration in the following way
\begin{equation}\label{age_update}
    a_{k,t+1} =
    \begin{cases}
     a_{k,t}+1, & \text{if $\mathbf{r}_t(k) = 0$} \\
      1,        & \text{if $\mathbf{r}_t(k) = 1$}
    \end{cases}.
  \end{equation}

A sample age evolution of a partial computation is shown in Fig. \ref{fig:age_evol}. Here, partial computation $\mathbf{W}_k\boldsymbol{\theta}$ is recovered at iterations $t$ and $t+4$. The average age of the partial computation $\mathbf{W}_k\boldsymbol{\theta}$ over the training interval of $T$ iterations is
\begin{align}
    a_k = \frac{1}{T}\sum^{T}_{t=1} a_{k,t}.
\end{align}

In order to make sure that each submatrix contributes to the model update as equally as possible during the training period, our goal is to keep the age of each partial computation under a certain threshold  $a_{th}$. Thus, our objective is
 \begin{equation}
 \min_{\Pi(D,O,E)} \frac{1}{T}\sum^{T}_{t=1}\frac{1}{K}\sum^{K}_{k=1}\mathbbm{1}_{\left\{a_{t,k}>a_{th}\right\}}, \label{obj_fcn}
 \end{equation}
where $\mathbbm{1}_{x}$ is the indicator function that returns 1 if $x$ holds, 0 otherwise. Here, $a_{th}$ is a design parameter that determines the desired freshness level for the partial computations and can be adjusted according to the learning problem. We note that the problem in (\ref{obj_fcn}) is over all data partitions, ordering and encoding policies, thereby is hard to optimally solve. Instead of solving (\ref{obj_fcn}) exactly, we introduce a timely dynamic ordering technique that can be used to regulate the recovery frequency of the partial computations.

\section{Solution Approach: Timely Dynamic Ordering}

In this section, we introduce timely dynamic ordering to better regulate the ages of partial computations and to avoid biased updates. We keep the data partition and encoding operators fixed and change only the ordering operator dynamically. This timely dynamic ordering is implemented by employing a vertical circular shift in the assignment matrix. With this, we essentially change the codewords and their computation order, which in turn, changes the recovered indices.

We first employ fixed vertical shifts for dynamic ordering. Then, we will dynamically adjust the shift amount based on the ages of the partial computations.

\subsection{Fixed Vertical Shifts}

In this code, which we call RCS-1, we employ one vertical shift for each worker at each iteration. That is, the order operator becomes
\begin{equation}\label{vertical_shift}
O_{i,t}(\mathcal{W}_{i}): \mathcal{W}_{i} \mapsto circshift(\mathcal{W}_{i}, mod(t,L)),
\end{equation}
where $circshift$ is  the circular shift operator and $mod(x,y)$ is a modulo operator returning the remainder of $x/y$. By using vertical shifts, coded computations transmitted to the PS from a particular worker change over time to prioritize certain partial computations. For example, if worker $1$ employs the ordered set $\tilde{\mathcal{W}}_{1,t}$ and codewords $\tilde{\mathcal{C}}_{i,t}$ specified in (\ref{encoding_exp}) at iteration $t$, after applying one vertical shift, its computation order and codewords at iteration $t+1$, are given by
 \begin{equation}
  \tilde{\mathcal{W}}_{1,t+1}=
    \begin{bmatrix}
  {\color{blue}\mathbf{W}_{4}} \\
  {\color{red}\mathbf{W}_{11}} \\
  {\color{red}\mathbf{W}_{15}} \\
  {\color{brown}\mathbf{W}_{6}} \\
  {\color{brown}\mathbf{W}_{18}} \\
  {\color{brown}\mathbf{W}_{1}} \\
  \end{bmatrix} \rightarrow
   \tilde{\mathcal{C}}_{i,t+1}=

  \begin{bmatrix}
   \mathbf{W}_{4} \\
   \mathbf{W}_{11} +\mathbf{W}_{15} \\
   \mathbf{W}_{6} + \mathbf{W}_{18} + \mathbf{W}_{1}\\
  \end{bmatrix}.
 \end{equation}

Here, we see that, at iteration $t$, the worker prioritizes the computation of $\mathbf{W}_1\boldsymbol{\theta}$, while in the next iteration computation of $\mathbf{W}_4\boldsymbol{\theta}$ is prioritized. We note that, in this method, the shift amount is fixed to one shift at each iteration, and is independent of the ages of the partial computations.

Next, we introduce an age-based vertical shift scheme to control the order of computations.

\subsection{Age-Based Vertical Shifts}

In this code, which we call RCS-adaptive,
we choose the vertical shift amount based on the current ages of the partial computations. That is, instead of shifting by $1$ at each iteration, the shift amount changes across iterations based on the ages of the partial computations. To effectively avoid biased updates, we focus on recovering the partial computations with the highest age at the current iteration, that is, the computations that have not been recovered in a while.
In line with the problem in (\ref{obj_fcn}), we term the partial computations with age higher than the threshold $a_{th}$ as aged partial computations, which need to be recovered as soon as possible. To this end, a vertical shift amount is selected that places the maximum number of aged partial computations in the first position in the non-straggling workers' computation order so that they have a higher chance of recovery in the next iteration. In particular, to determine the shift amount in iteration $t+1$, the PS  considers the computation order at the workers that have returned at least one computation in the previous iteration and determines a shift which places maximum number of aged partial computations in the first order in these workers. Upon determining the shift amount, every worker's assignment matrix is shifted by that amount in the next iteration. For example, if the age-based shift amount is $3$ in iteration $t+1$, then the first user has
 \begin{equation}
  \tilde{\mathcal{W}}_{1,t+1}=
    \begin{bmatrix}
  {\color{blue}\mathbf{W}_{15}} \\
  {\color{red}\mathbf{W}_{6}} \\
  {\color{red}\mathbf{W}_{18}} \\
  {\color{brown}\mathbf{W}_{1}} \\
  {\color{brown}\mathbf{W}_{4}} \\
  {\color{brown}\mathbf{W}_{11}} \\
  \end{bmatrix} \rightarrow
   \tilde{\mathcal{C}}_{i,t+1}=

  \begin{bmatrix}
   \mathbf{W}_{15} \\
   \mathbf{W}_{6} +\mathbf{W}_{18} \\
   \mathbf{W}_{1} + \mathbf{W}_{4} + \mathbf{W}_{11}\\
  \end{bmatrix}.
 \end{equation}

Here, in iteration $t+1$, the first worker prioritizes the computation of $\mathbf{W}_{15}\boldsymbol{\theta}$.

\section{Numerical Results}

In this section, we provide numerical results for comparing the proposed age-based partial computation scheme to alternative static schemes using a model-based scenario for computation latencies. For the simulations, we consider a linear regression problem over synthetically created training and test
datasets, as in \cite{CC.4}, of size of $2000$ and $400$, respectively. We also assume that the size of the model $d = 1000$ and the number of workers $K = 40$ while each worker can return $L=3$ computations with $\mathbf{m}=[1,2,3]$. A single simulation includes $T=400$ iterations. For all simulations, we use learning rate $\eta = 0.1$. To model the computation delays at the workers, we adopt the model in \cite{entropy}, and assume that the probability of completing $s$ computations at any worker, performing $s$ identical matrix-vector multiplications, by time $t$ is given by
\begin{equation}\label{exp_compute}
  F_s(t) \triangleq
  \begin{cases}
    1-e^{-\mu(\frac{t}{s}-\alpha)}, & \text{if $t \geq s\alpha$} \\
    0, & \text{otherwise}.
  \end{cases}
\end{equation}

First, we consider an extreme scenario in the straggling behavior, where we assume there are $15$ persistent stragglers that are fixed for all the $T=400$ iterations which do not complete any partial computations. For the non-persistent stragglers, we set $\mu = 10$ and $\alpha = 0.01$.\footnote{To simulate the straggling behavior in our simulations, we take $\alpha=10$ for the persistent stragglers so that effectively they do not complete any partial computations.} In Fig.~\ref{fig:1}, we set the tolerance level $q=0.3$, such that at each iteration the PS aims at recovering $28$ of the total $40$ partial computations. We see that the proposed timely dynamic encoding strategy with one vertical shift at each iteration, RCS$-1,$ achieves a significantly better convergence performance than the conventional static encoding with RCS. When the ages of partial computations are taken into consideration in determining the order of computation at each iteration with the proposed RCS-adaptive scheme with an age threshold of $a_{th} = 2$, we observe a further improvement in the convergence performance.

\begin{figure}[t]
	\centering  \includegraphics[width=0.7\columnwidth]{03tolerance_convergence_logy.eps}

	\caption{Test accuracy (log-scale) vs. number of iterations with $q=0.3$ and $15$ persistent stragglers.}
	\label{fig:1}
	\vspace{-0.2cm}
\end{figure}
\begin{figure}[t]
	\centering  \includegraphics[width=0.7\columnwidth]{03tolerance_meanage_bars.eps}

	\caption{Average ages of the partial computations with $q=0.3$ and $15$ persistent stragglers.}
	\label{fig:2}
	\vspace{-0.2cm}
\end{figure}
\begin{figure}[t]
	\centering  \includegraphics[width=0.7\columnwidth]{acc_results_ageth2and3_logscale.eps}

	\caption{Test accuracy (log-scale) vs. number of iterations with $q=0.3$ and straggling behavior based on a 2-state Markov chain with a state transition probability of $p=0.05$.}
	\label{fig:14}
	\vspace{-0.2cm}
\end{figure}
\begin{figure}[t]
	\centering  \includegraphics[width=0.7\columnwidth]{02tolerance_convergence_unc111_logy.eps}

	\caption{Test accuracy (log-scale) vs. number of iterations for the uncoded scheme with $q=0.2$ and $15$ persistent stragglers.}
	\label{fig:6.5}
	\vspace{-0.2cm}
\end{figure}

An interesting observation comes from Fig.~\ref{fig:2}, where we plot the average ages of the partial computations. While the proposed timely dynamic encoding strategy does not result in a better average age performance for every single partial computation, it targets the partial computations with the highest average age (see computation tasks $2$, $10$, and $26$ in Fig.~\ref{fig:2}). By utilizing the dynamic order operator, we essentially lower the average age of the partial computations with the worst age performance at the expense of slight increase in that of the some remaining partial computations. As expected, age-based vertical shift strategy further lowers the average ages of the partial computations. Here, we can draw parallels with this result and \cite{Jiang18d}, which shows that as long as each component is received every $p$ iterations, the distributed SGD can maintain its asymptotic convergence rate. From Fig.~\ref{fig:2}, we can see that the proposed vertical shift operator guarantees that on average each task is received every $3$ iterations, since the yellow bar in Fig.~\ref{fig:2} is less than $3$ for each partial computation.

We note that in Figs.~\ref{fig:1} and~\ref{fig:2} the performance gap between RCS-1 and RCS-adaptive schemes is narrow. This shows that the randomness introduced by a fixed vertical shift is already quite helpful in mitigating the biased updates with less stale partial computations.

In Table~\ref{table1}, we look at the value of the objective function in (\ref{obj_fcn}) when $a_{th}=2$ with $\mu = 10$ and $\alpha = 0.01$ for varying tolerance levels in the case of fixed $15$ persistent stragglers throughout all the iterations. We observe that, for each tolerance level $q$, when RCS-1 is employed, we achieve a better performance than the static RCS scheme, whereas the age-based vertical shift method RCS-adaptive results in the best performance. This is because the RCS-adaptive scheme specifically targets the computational tasks that have average age higher than the threshold $a_{th}$ to effectively create less biased model updates where each partial computation contributes to the learning task more uniformly.
\begin{table}[t]
\centering
\vspace{2 mm}
\begin{tabular}{ |c|c|c|c|c|c| }
\hline
Tolerance level & RCS & RCS-1  & RCS-adaptive \\
\hline
$q=0.1$ & $0.0261$ & $0.0180$ & $0.0156$  \\
\hline
$q=0.2$& $0.0681$ & $0.0476$ & $0.0451$  \\
\hline
$q=0.3$& $0.1316$ & $0.0970$ & $0.0919$ \\
\hline
\end{tabular}
\vspace{1 mm}
\caption{ \label{table1} The value of the objective function in (\ref{obj_fcn}) when $a_{th} = 2$ for varying tolerance levels $q$.}
\vspace{-5 mm}
\end{table}

Second, we consider a more realistic scenario and model the straggling behavior of workers based on a two-state Markov chain: a slow state $s$ and a fast state $f$, such that computations are completed faster when a worker is in state $f$. This is similar to the Gilbert-Elliot service times considered in \cite{Yang19, Buyukates20a}. Specifically, in (\ref{exp_compute}) we have rate $\mu_f$ in state $f$ and rate $\mu_s$ in state $s$ where $\mu_f > \mu_s$. We assume that the state changes only occur at the beginning of each iteration with probability $p$; that is, with probability $1-p$ the state stays the same. A low switching probability $p$ indicates that the straggling behavior tends to stay the same in the next iteration. In Fig.~\ref{fig:14}, we set $p=0.05$, $q=0.3$, $\alpha = 0.01$, $\mu_S = 2$, and $\mu_f = 10$ and let $15$ workers start at the slow state, i.e., initially we have $15$ straggling workers. We note that with $15$ initial stragglers and $p=0$ we recover the setting considered in Fig.~\ref{fig:1}. We observe in Fig.~\ref{fig:14} that the proposed timely dynamic encoding strategy improves the convergence performance even though the performance improvement is less compared to the setting in Fig.~\ref{fig:1}. This is because, in this scenario, the straggling behavior is less correlated over iterations, which results in less biased model updates even for the static RCS scheme. Further, we see in Fig.~\ref{fig:14} that the RCS-adaptive scheme with $a_{th} =3$ performs the best, whereas the RCS-1 scheme outperforms the RCS-adaptive scheme when $a_{th} =2$. This shows that the age threshold $a_{th}$ needs to be tuned to get the best performance from the RCS-adaptive scheme.

Even though we focus on the distributed coded computation scenario in this work, the proposed dynamic order operator can be applied when the computations are assigned to workers in an uncoded fashion as well. To see the performance in the case of uncoded computations with MMC, we set $\mathbf{m}=[1,1,1]$ and $q=0.2$ and consider the same setup as in Fig.~\ref{fig:1}. In Fig.~\ref{fig:6.5}, we observe that the static partial recovery scheme fails to converge since if coding is not implemented along with partial recovery, model updates are highly biased in the presence of persistent stragglers. However, when the dynamic order operator is employed, particularly the age-aware vertical shifts with $a_{th}=1$, convergence is achieved.

\section{Conclusion}
MMC and partial recovery are two strategies designed to enhance the performance of coded computation employed for straggler-aware distributed learning. The main drawback of the partial recovery strategy is biased model updates that are caused when the straggling behaviors of the workers are correlated over time. To prevent biased updates, we introduce a timely dynamic encoding strategy which changes the codewords and their computation order over time. We use an age metric to regulate the recovery frequencies of the partial computations. By conducting several experiments on a linear regression problem, we show that dynamic encoding, particularly an age-based encoding strategy, can significantly improve the convergence performance compared to conventional static encoding schemes. Although our main focus is on coded computation, the advantages of the proposed strategy are not limited to the coded computation scenario. The proposed timely dynamic encoding strategy can be utilized for coded communication and uncoded computation scenarios as well.

\bibliographystyle{unsrt}
\bibliography{IEEEabrv,lib_v5,refs.bib}

\end{document}


TITLE: Finding equation of a circle given three non - collinear points
QUESTION [2 upvotes]: A circle is given which passes through three non collinear points $(x_1,y_1),(x_2,y_2),(x_3,y_3)$ then prove that equation of this circle is given by
$$\begin{vmatrix}
x^2+y^2&x&y&1\\
x_1^2+y_1^2&x_1&y_1&1\\
x_2^2+y_2^2&x_2&y_2&1\\
x_3^2+y_3^2&x_3&y_3&1\\
\end{vmatrix} = 0$$
It is just like one of answers to this question Finding an equation of circle which passes through three points
I would like to know how we get to this determinant and I have no idea from where I can start?

REPLY [0 votes]: The quadratic form $Ax^2+By^2+Cxy+Dx+Ey+F=0$ represents always a conic (eventualy degenerate in two right lines if it is a product of two linear equations) and it represents a circle if and only if $A=B\ne0$ and $C=0$. Then for a circle  we have the equation
$$A(x^2+y^2)+Dx+Ey+F=0$$  When we want a circle passing through three non collinear points $(x_i,y_i)$ we have a linear system of three equations  whose solution gives the three values $ a=\dfrac{D}{A}, b=\dfrac{E}{A}, c=\dfrac{F}{A}$ of the required circle.
But when we want to have the equation of the circle without getting explicitely $a,b,c$ we consider the linear system of four equations with three unknowns $a,b,c$
$$(x^2+y^2)+ax+by+c=0\\(x_1^2+y_1^2)+ax_1+by_1+c=0\\(x_2^2+y_2^2)+ax_2+by_2+c=0\\(x_3^2+y_3^2)+ax_3+by_3+c=0$$
and it is well known that the condition of compatibility of this four equations is that its determinant be equal to zero. In other words, making more explicitely, we have  the matricial equation
$$\begin{pmatrix}
x^2+y^2&x&y&1\\
x_1^2+y_1^2&x_1&y_1&1\\
x_2^2+y_2^2&x_2&y_2&1\\
x_3^2+y_3^2&x_3&y_3&1\\
\end{pmatrix}\cdot\begin{pmatrix}1\\a\\b\\c\end{pmatrix}=\begin{pmatrix}0\\0\\0\\0\end{pmatrix}$$
There are two evident solutions, $(0,0,0,0)$ and $(1,a,b,c)$ so the determinant must be equal to $0$ because if not then the solution should be unique.